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

• URL: http://arxiv.org/abs/2404.03290v1
• Date: Thu, 4 Apr 2024 08:24:57 GMT
• Title: Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation
• Authors: Michael Sucker, Jalal Fadili, Peter Ochs,
• Abstract summary: We use the PAC-Bayesian theory for the setting of learning-to-optimize. We present the first framework to learn optimization algorithms with provable generalization guarantees. Our learned algorithms provably outperform related ones derived from a (deterministic) worst-case analysis.
• Score: 4.239829789304117
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learning via Surrogate PAC-Bayes [13.412960492870996]
  PAC-Bayes learning is a comprehensive setting for studying the generalisation ability of learning algorithms. We introduce a novel principled strategy for building an iterative learning algorithm via the optimisation of a sequence of surrogate training objectives. On top of providing that generic recipe for learning via surrogate PAC-Bayes bounds, we (i) contribute theoretical results establishing that iteratively optimising our surrogates implies the optimisation of the original generalisation bounds.
  arXiv  Detail & Related papers  (2024-10-14T07:45:50Z)
• A Generalization Result for Convergence in Learning-to-Optimize [4.112909937203119]
  Conventional convergence guarantees in optimization are based on geometric arguments, which cannot be applied to algorithms. We are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our knowledge, we are the first to prove the best of our
  arXiv  Detail & Related papers  (2024-10-10T08:17:04Z)
• Data-Driven Performance Guarantees for Classical and Learned Optimizers [2.0403774954994858]
  We introduce a data-driven approach to analyze the performance of continuous optimization algorithms. We study classical and learneds to solve families of parametric optimization problems.
  arXiv  Detail & Related papers  (2024-04-22T02:06:35Z)
• Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
  Preference-based Reinforcement Learning (PbRL) is a paradigm in which an RL agent learns to optimize a task using pair-wise preference-based feedback over trajectories. We propose a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired.
  arXiv  Detail & Related papers  (2023-05-29T15:00:09Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations. The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
  arXiv  Detail & Related papers  (2023-02-02T22:16:49Z)
• Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice [54.03076395748459]
  A central question in the meta-learning literature is how to regularize to ensure generalization to unseen tasks. We present a generalization bound for meta-learning, which was first derived by Rothfuss et al. We provide a theoretical analysis and empirical case study under which conditions and to what extent these guarantees for meta-learning improve upon PAC-Bayesian per-task learning bounds.
  arXiv  Detail & Related papers  (2022-11-14T08:51:04Z)
• PAC-Bayesian Learning of Optimization Algorithms [6.624726878647541]
  We apply the PAC-Bayes theory to the setting of learning-to-optimize. We learn optimization algorithms with provable generalization guarantees (PAC-bounds) and explicit trade-off between a high probability of convergence and a high convergence speed. Our results rely on PAC-Bayes bounds for general, unbounded loss-functions based on exponential families.
  arXiv  Detail & Related papers  (2022-10-20T09:16:36Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees [77.67258935234403]
  We provide a theoretical analysis using the PAC-Bayesian framework and derive novel generalization bounds for meta-learning. We develop a class of PAC-optimal meta-learning algorithms with performance guarantees and a principled meta-level regularization.
  arXiv  Detail & Related papers  (2020-02-13T15:01:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.