We are pleased to welcome UofT alumnus and current MIT PhD candidate Shuvomoy Das Gupta as our first student seminar speaker of 2023. Please join us in person on January 9 for a coffee and his wonderful talk.
Abstract: We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing optimal first-order methods for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal optimization method as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a customized branch-and-bound algorithm. By directly confronting the nonconvexity, BnB-PEP offers significantly more flexibility and removes the many limitations of the prior methodologies. Our customized branch-and-bound algorithm, through exploiting specific problem structures, outperforms the latest off-the-shelf implementations by orders of magnitude, accelerating the solution time from hours to seconds and weeks to minutes. We apply BnB-PEP to several setups for which the prior methodologies do not apply and obtain methods with bounds that improve upon prior state-of-the-art results. Finally, we use the BnB-PEP methodology to find proofs with potential function structures, thereby systematically generating analytical convergence proofs. (Joint work with Prof. Bart Van Parys and Prof. Ernest K. Ryu)
Paper link: https://arxiv.org/abs/2203.07305
Code: https://github.com/Shuvomoy/BnB-PEP-code
Speaker Bio: Shuvomoy Das Gupta is a fourth-year Ph.D. student at the MIT Operations Research Center. His research focuses on developing efficient algorithms for large-scale optimization and machine learning. He obtained his M.A.Sc. from the ECE Department at the University of Toronto in 2016 and then worked as a researcher at the Research & Technology Department of Thales Canada for three years. His M.A.Sc. research on energy-efficient railway timetables has been applied to the largest installed base of communication-based train control systems worldwide. Previously, he obtained a Bachelor of Science in Electrical and Electronic Engineering from the Bangladesh University of Engineering and Technology.