Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds
We consider the optimization problem of an expensive-to-evaluate black-box function, in which we can obtain noisy function values in parallel. For this problem, parallel Bayesian optimization (PBO) is a promising approac…
Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs
Robust MDPs (RMDPs) can be used to compute policies with provable worst-case guarantees in reinforcement learning. The quality and robustness of an RMDP solution are determined by the ambiguity set---the set of plausible…
Bayesian InferencePositionreinforcement-learningReinforcement Learning+1On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
This thesis rigorously studies fundamental reinforcement learning (RL) methods in modern practical considerations, including robust RL, distributional RL, and offline RL with neural function approximation. The thesis fir…
Offline RLreinforcement-learningReinforcement LearningReinforcement Learning (RL)PAC-Bayesian Offline Contextual Bandits With Guarantees
This paper introduces a new principled approach for off-policy learning in contextual bandits. Unlike previous work, our approach does not derive learning principles from intractable or loose bounds. We analyse the probl…
Generalization BoundsMulti-Armed BanditsNo-Regret Bayesian Optimization with Unknown Hyperparameters
Bayesian optimization (BO) based on Gaussian process models is a powerful paradigm to optimize black-box functions that are expensive to evaluate. While several BO algorithms provably converge to the global optimum of th…
Bayesian Optimization