Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
This work provides a method to tailor optimization algorithms for high-stakes applications like control systems, offering incremental improvements by balancing worst-case guarantees with practical performance.
The paper addresses the challenge of improving average-case performance of linearly convergent optimization algorithms on specific problem instances while preserving worst-case guarantees, by characterizing all modifications to update rules that maintain convergence properties. It demonstrates effectiveness on ill-conditioned linear equations and model predictive control, showing improved performance within tight iteration budgets.
In high-stakes engineering applications, optimization algorithms must come with provable worst-case guarantees over a mathematically defined class of problems. Designing for the worst case, however, inevitably sacrifices performance on the specific problem instances that often occur in practice. We address the problem of augmenting a given linearly convergent algorithm to improve its average-case performance on a restricted set of target problems - for example, tailoring an off-the-shelf solver for model predictive control (MPC) for an application to a specific dynamical system - while preserving its worst-case guarantees across the entire problem class. Toward this goal, we characterize the class of algorithms that achieve linear convergence for classes of nonsmooth composite optimization problems. In particular, starting from a baseline linearly convergent algorithm, we derive all - and only - the modifications to its update rule that maintain its convergence properties. Our results apply to augmenting legacy algorithms such as gradient descent for nonconvex, gradient-dominated functions; Nesterov's accelerated method for strongly convex functions; and projected methods for optimization over polyhedral feasibility sets. We showcase effectiveness of the approach on solving optimization problems with tight iteration budgets in application to ill-conditioned systems of linear equations and MPC for linear systems.