PAC-Bayesian Learning of Optimization Algorithms

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.

@inproceedings{SO23,
  title        = {PAC-Bayesian Learning of Optimization Algorithms},
  author       = {M. Sucker and P. Ochs},
  year         = {2023},
  editor       = {F. Ruiz and J. Dy and J-W. van de Meent},
  booktitle    = {International Conference on Artificial Intelligence and Statistics},
  series       = {Proceedings of Machine Learning Research},
  volume       = {206},
  pages        = {8145--8164}
}