# Data-Driven Performance Guarantees for Classical and Learned Optimizers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 60 of its 103 references that are in the map.
- First posted on arXiv 22 Apr 2024.

## Builds on (most cited first, 30 of 60)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Plug-and-Play Methods Provably Converge with Properly Trained Denoisers](https://mlsanity.com/paper/1905.05406/) (2019)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds](https://mlsanity.com/paper/1808.10038/) (2018)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [VeLO: Training Versatile Learned Optimizers by Scaling Up](https://mlsanity.com/paper/2211.09760/) (2022)
- [Deep Unfolding for Communications Systems: A Survey and Some New Directions](https://mlsanity.com/paper/1906.05774/) (2019)
- [Unrolled Optimization with Deep Priors](https://mlsanity.com/paper/1705.08041/) (2017)
- [Online Mixed-Integer Optimization in Milliseconds](https://mlsanity.com/paper/1907.02206/) (2019)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Learning for Constrained Optimization: Identifying Optimal Active Constraint Sets](https://mlsanity.com/paper/1802.09639/) (2018)
- [Learning Warm-Start Points for AC Optimal Power Flow](https://mlsanity.com/paper/1905.08860/) (2019)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Accelerating Quadratic Optimization with Reinforcement Learning](https://mlsanity.com/paper/2107.10847/) (2021)

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

- [Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding](https://mlsanity.com/paper/2512.01565/) (2025)
- [Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms](https://mlsanity.com/paper/2508.00775/) (2025)
- [Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees](https://mlsanity.com/paper/2601.07665/) (2026)
- [Learning Over-Relaxation Policies for ADMM with Convergence Guarantees](https://mlsanity.com/paper/2604.26932/) (2026)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

We introduce a data-driven approach to analyze the performance of continuous optimization algorithms using generalization guarantees from statistical learning theory. We study classical and learned optimizers to solve families of parametric optimization problems. We build generalization guarantees for classical optimizers, using a sample convergence bound, and for learned optimizers, using the Probably Approximately Correct (PAC)-Bayes framework. To train learned optimizers, we use a gradient-based algorithm to directly minimize the PAC-Bayes upper bound. Numerical experiments in signal processing, control, and meta-learning showcase the ability of our framework to provide strong generalization guarantees for both classical and learned optimizers given a fixed budget of iterations. For classical optimizers, our bounds are much tighter than those that worst-case guarantees provide. For learned optimizers, our bounds outperform the empirical outcomes observed in their non-learned counterparts.