Abstract: First-order methods (FOMs) are optimization algorithms that can be described and analyzed using the values and (sub)gradients of the functions to be minimized. FOMs are the main workhorses for modern large-scale optimization and machine learning due to their low iteration costs, minimal memory requirements, and dimension-independent convergence guarantees. As the data revolution continues to unfold, the pressing demand for faster FOMs has become the key problem in today’s big data era. To that goal, we present Branch-and-Bound Performance Estimation Programming (BnB-PEP), the first unified methodology for constructing optimal (provably fastest) FOMs for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal FOM as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a custom branch-and-bound algorithm. Our open-source custom branch-and-bound algorithm, through exploiting specific problem structures, outperforms the latest off-the-shelf software by orders of magnitude, accelerating the solution time to discover the optimal FOMs from hours to seconds and weeks to minutes. We apply BnB-PEP to several practically relevant convex and nonconvex setups and obtain FOMs with bounds that improve upon prior state-of-the-art results. Furthermore, we use the BnB-PEP methodology to find proofs with potential function structures, thereby systematically generating analytical convergence proofs. Recently, BnB-PEP has helped pave the way for some fundamental results in optimization: (i) novel momentum-free accelerated gradient descent methods that broke with decades of conventional wisdom (ii) the optimal FOM for constrained convex optimization that outperforms the celebrated FISTA algorithm by Beck and Teboulle, and (iii) the first non-asymptotic convergence theory for the widely used nonlinear conjugate gradient methods. (joint work with Bart Van Parys and Ernest K. Ryu)

 

Paper link: https://arxiv.org/pdf/2203.07305

Topic:

Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods