PAC-Bayesian Learning of Optimization Algorithms
This work addresses the need for reliable and efficient optimization algorithms in machine learning, offering a novel theoretical framework with empirical validation, though it is incremental in building on existing PAC-Bayes ideas.
The paper tackles the problem of learning optimization algorithms with provable generalization guarantees by applying PAC-Bayes theory, resulting in algorithms that outperform deterministic worst-case methods even in convergence-guaranteed limits.
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.