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

Understand

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.