Cornell Young Researchers Workshop 2022
Shuvomoy Das Gupta
October 6-8, 2022
You have landed on this page, because you have scanned the QR code of my poster for Cornell Young Researchers Workshop 2022 😃.
Hello! I am very grateful that my research interests you 😊! In this page, I want to briefly provide you with some resources regarding my poster. Please feel free to send me an email 📧 to sdgupta@mit.edu if you have any questions regarding the poster, or if you just want to say hi!
Table of contents
BnB-PEP paper
The poster (pdf here) is based on the following paper.
Shuvomoy Das Gupta, Bart P.G. Van Parys, and Ernest K. Ryu, “Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods”, 2022. [pdf] [code]
A detailed YouTube video describing the paper is below.
Materials to learn about PEP
BnB-PEP builds on PEP (performance estimation problem). I am very excited about PEP in general, so I want to tell you more about it!
Papers
The performance estimation methodology, initiated by Drori and Teboulle in [1], formulates the worst case-performance of an optimization method as an optimization problem itself and upper bounds this performance through a semidefinite program (SDP) "relaxation. Taylor, Hendrickx, and Glineur then showed in [2] that the SDP formulation is tight (not a relaxation) through the notion of "convex interpolation". Taylor, Hendrickx, and Glineur subsequently extended PEP to composite convex optimization in [3]. There are many more fantastic papers on PEP, but we can start learning about PEP by studying those three first:
[1] Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: A novel approach. Mathematical Programming, 145(1-2):451–482, 2014. (link: https://arxiv.org/pdf/1206.3209.pdf
[2] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1-2):307–345, 2017. (link: https://arxiv.org/pdf/1502.05666.pdf)
[3] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27(3):1283–1313, 2017. (link: https://arxiv.org/pdf/1512.07516.pdf)
Blog
If you are interested to learn about PEP more informally without reading the papers above first, a gentle introduction is the following blog post by Adrien Taylor:
[1] A. B. Taylor, Computer-aided analyses in optimization
Video presentation
After the blog, a very nice video presentation by Adrien Taylor is available at this link. The slides for his talk is available here.
A more advanced talk by Adrien Taylor on constructing optimal first-order optimization methods in convex optimization using PEP is below.