# A Nonstochastic Control Approach to Optimization

arXiv: https://arxiv.org/abs/2301.07902 · HTML: https://mlsanity.com/paper/2301.07902/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 62 references that are in the map.
- First posted on arXiv 19 Jan 2023.

## Builds on (most cited first, 29 of 29)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/1703.04782/) (2017)
- [Learned Optimizers that Scale and Generalize](https://mlsanity.com/paper/1703.04813/) (2017)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [VeLO: Training Versatile Learned Optimizers by Scaling Up](https://mlsanity.com/paper/2211.09760/) (2022)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Learning to Optimize Neural Nets](https://mlsanity.com/paper/1703.00441/) (2017)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [Practical tradeoffs between memory, compute, and performance in learned optimizers](https://mlsanity.com/paper/2203.11860/) (2022)
- [A Closer Look at Learned Optimization: Stability, Robustness, and Inductive Biases](https://mlsanity.com/paper/2209.11208/) (2022)
- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [Introduction to Online Control](https://mlsanity.com/paper/2211.09619/) (2022)
- [Non-Stochastic Control with Bandit Feedback](https://mlsanity.com/paper/2008.05523/) (2020)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Online Control of Unknown Time-Varying Dynamical Systems](https://mlsanity.com/paper/2202.07890/) (2022)
- [Guarantees for Tuning the Step Size using a Learning-to-Learn Approach](https://mlsanity.com/paper/2006.16495/) (2020)
- [Average-case Acceleration for Bilinear Games and Normal Matrices](https://mlsanity.com/paper/2010.02076/) (2020)
- [Optimizing Optimizers: Regret-optimal gradient descent algorithms](https://mlsanity.com/paper/2101.00041/) (2020)

## Built on by (most cited first, 4 of 4)

- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances](https://mlsanity.com/paper/2310.02246/) (2023)

## Abstract (arXiv)

Selecting the best hyperparameters for a particular optimization instance, such as the learning rate and momentum, is an important but nonconvex problem. As a result, iterative optimization methods such as hypergradient descent lack global optimality guarantees in general. We propose an online nonstochastic control methodology for mathematical optimization. First, we formalize the setting of meta-optimization, an online learning formulation of learning the best optimization algorithm from a class of methods. The meta-optimization problem over gradient-based methods can be framed as a feedback control problem over the choice of hyperparameters, including the learning rate, momentum, and the preconditioner. Although the original optimal control problem is nonconvex, we show how recent methods from online nonstochastic control using convex relaxations can be used to overcome the challenge of nonconvexity, and obtain regret guarantees against the best offline solution. This guarantees that in meta-optimization, given a sequence of optimization problems, we can learn a method that attains convergence comparable to that of the best optimization method in hindsight from a class of methods.