# PAC-Bayesian Learning of Optimization Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 63 references that are in the map.
- First posted on arXiv 20 Oct 2022.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Plug-and-Play ADMM for Image Restoration: Fixed Point Convergence and Applications](https://mlsanity.com/paper/1605.01710/) (2016)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [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)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds](https://mlsanity.com/paper/1808.10038/) (2018)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [Plug-and-Play Priors for Bright Field Electron Tomography and Sparse Interpolation](https://mlsanity.com/paper/1512.07331/) (2015)
- [An Online Plug-and-Play Algorithm for Regularized Image Reconstruction](https://mlsanity.com/paper/1809.04693/) (2018)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [Plug-and-Play Unplugged: Optimization Free Reconstruction using Consensus Equilibrium](https://mlsanity.com/paper/1705.08983/) (2017)
- [Regularization by Denoising via Fixed-Point Projection (RED-PRO)](https://mlsanity.com/paper/2008.00226/) (2020)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Maximal Sparsity with Deep Networks?](https://mlsanity.com/paper/1605.01636/) (2016)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Convergence of constant step stochastic gradient descent for non-smooth non-convex functions](https://mlsanity.com/paper/2005.08513/) (2020)
- [Graphical Convergence of Subgradients in Nonconvex Optimization and Learning](https://mlsanity.com/paper/1810.07590/) (2018)
- [Controlling Neural Networks via Energy Dissipation](https://mlsanity.com/paper/1904.03081/) (2019)
- [Total Deep Variation: A Stable Regularizer for Inverse Problems](https://mlsanity.com/paper/2006.08789/) (2020)

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

- [Deep Unfolding: Recent Developments, Theory, and Design Guidelines](https://mlsanity.com/paper/2512.03768/) (2025)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [From Learning to Optimize to Learning Optimization Algorithms](https://mlsanity.com/paper/2405.18222/) (2024)
- [A Generalization Result for Convergence in Learning-to-Optimize](https://mlsanity.com/paper/2410.07704/) (2024)

## Abstract (arXiv)

We apply the PAC-Bayes theory to the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-bounds) and explicit trade-off between a high probability of convergence and a high convergence speed. Even in the limit case, where convergence is guaranteed, our learned optimization algorithms provably outperform related algorithms based on a (deterministic) worst-case analysis. Our results rely on PAC-Bayes bounds for general, unbounded loss-functions based on exponential families. By generalizing existing ideas, we reformulate the learning procedure into a one-dimensional minimization problem and study the possibility to find a global minimum, which enables the algorithmic realization of the learning procedure. As a proof-of-concept, we learn hyperparameters of standard optimization algorithms to empirically underline our theory.