Direct Synthesis of Iterative Algorithms With Bounds on Achievable Worst-Case Convergence Rate
This work provides a new framework for designing optimization algorithms with guaranteed worst-case performance, benefiting the machine learning and optimization communities by enabling the discovery of algorithms with stronger convergence guarantees.
The authors propose a method to directly synthesize iterative first-order optimization algorithms with provable worst-case convergence rate bounds, outperforming previous approaches that only optimize over fixed-structure algorithms with limited memory.
Iterative first-order methods such as gradient descent and its variants are widely used for solving optimization and machine learning problems. There has been recent interest in analytic or numerically efficient methods for computing worst-case performance bounds for such algorithms, for example over the class of strongly convex loss functions. A popular approach is to assume the algorithm has a fixed size (fixed dimension, or memory) and that its structure is parameterized by one or two hyperparameters, for example a learning rate and a momentum parameter. Then, a Lyapunov function is sought to certify robust stability and subsequent optimization can be performed to find optimal hyperparameter tunings. In the present work, we instead fix the constraints that characterize the loss function and apply techniques from robust control synthesis to directly search over algorithms. This approach yields stronger results than those previously available, since the bounds produced hold over algorithms with an arbitrary, but finite, amount of memory rather than just holding for algorithms with a prescribed structure.