# Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2024.

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

- [On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery](https://mlsanity.com/paper/2410.13981/) (2024)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding](https://mlsanity.com/paper/2512.01565/) (2025)
- [A Generalization Result for Convergence in Learning-to-Optimize](https://mlsanity.com/paper/2410.07704/) (2024)
- [VERSE: Verified Self-Evolving Optimizer for Agent Harnesses](https://mlsanity.com/paper/2610.02616/) (2026)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

We use the PAC-Bayesian theory for 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-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones derived from a (deterministic) worst-case analysis. The results rely on PAC-Bayesian bounds for general, possibly unbounded loss-functions based on exponential families. Then, we reformulate the learning procedure into a one-dimensional minimization problem and study the possibility to find a global minimum. Furthermore, we provide a concrete algorithmic realization of the framework and new methodologies for learning-to-optimize, and we conduct four practically relevant experiments to support our theory. With this, we showcase that the provided learning framework yields optimization algorithms that provably outperform the state-of-the-art by orders of magnitude.