Data-Driven Performance Guarantees for Classical and Learned Optimizers

• URL: http://arxiv.org/abs/2404.13831v2
• Date: Tue, 21 May 2024 21:13:04 GMT
• Title: Data-Driven Performance Guarantees for Classical and Learned Optimizers
• Authors: Rajiv Sambharya, Bartolomeo Stellato,
• Abstract summary: 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.
• Score: 2.0403774954994858
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We introduce a data-driven approach to analyze the performance of continuous optimization algorithms using generalization guarantees from statistical learning theory. We study classical and learned optimizers to solve families of parametric optimization problems. We build generalization guarantees for classical optimizers, using a sample convergence bound, and for learned optimizers, using the Probably Approximately Correct (PAC)-Bayes framework. To train learned optimizers, we use a gradient-based algorithm to directly minimize the PAC-Bayes upper bound. Numerical experiments in signal processing, control, and meta-learning showcase the ability of our framework to provide strong generalization guarantees for both classical and learned optimizers given a fixed budget of iterations. For classical optimizers, our bounds are much tighter than those that worst-case guarantees provide. For learned optimizers, our bounds outperform the empirical outcomes observed in their non-learned counterparts.

Related papers

• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand. We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
  We show that gradient-based and high-level LLMs can effectively collaborate a combined optimization framework. In this paper, we show that these complementary to each other and can effectively collaborate a combined optimization framework.
  arXiv  Detail & Related papers  (2024-05-30T06:24:14Z)
• Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation [4.239829789304117]
  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.
  arXiv  Detail & Related papers  (2024-04-04T08:24:57Z)
• Principled Preferential Bayesian Optimization [22.269732173306192]
  We study the problem of preferential Bayesian optimization (BO) We aim to optimize a black-box function with only preference feedback over a pair of candidate solutions. An optimistic algorithm with an efficient computational method is then developed to solve the problem.
  arXiv  Detail & Related papers  (2024-02-08T02:57:47Z)
• A General Framework for User-Guided Bayesian Optimization [51.96352579696041]
  We propose ColaBO, the first Bayesian-principled framework for prior beliefs beyond the typical kernel structure. We empirically demonstrate ColaBO's ability to substantially accelerate optimization when the prior information is accurate, and to retain approximately default performance when it is misleading.
  arXiv  Detail & Related papers  (2023-11-24T18:27:26Z)
• Learning to Generalize Provably in Learning to Optimize [185.71326306329678]
  Learning to optimize (L2O) has gained increasing popularity, which automates the design of optimizees by data-driven approaches. Current L2O methods often suffer from poor generalization performance in at least two folds. We propose to incorporate these two metrics as flatness-aware regularizers into the L2O framework.
  arXiv  Detail & Related papers  (2023-02-22T01:17:31Z)
• Optimizer Amalgamation [124.33523126363728]
  We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance? First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent. In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
  arXiv  Detail & Related papers  (2022-03-12T16:07:57Z)
• Integrated Optimization of Predictive and Prescriptive Tasks [0.0]
  We propose a new framework directly integrating predictive tasks under prescriptive tasks. We train the parameters of predictive algorithm within a prescription problem via bilevel optimization techniques.
  arXiv  Detail & Related papers  (2021-01-02T02:43:10Z)
• 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)

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.