Non-Convex Bilevel Optimization with Time-Varying Objective Functions

• URL: http://arxiv.org/abs/2308.03811v2
• Date: Wed, 8 Nov 2023 23:59:25 GMT
• Title: Non-Convex Bilevel Optimization with Time-Varying Objective Functions
• Authors: Sen Lin, Daouda Sow, Kaiyi Ji, Yingbin Liang, Ness Shroff
• Abstract summary: We propose an online bilevel optimization where the functions can be time-varying and the agent continuously updates the decisions with online data. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions.
• Score: 57.299128109226025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.

Related papers

• Online Nonconvex Bilevel Optimization with Bregman Divergences [3.237380113935023]
  We introduce an online bilevel (SOB) method for updating outer-level variables using an average of recent variance rates. This approach is superior to the setting offline bilevel (OBO) as rates of hyperlevel benchmarks highlight the superior performance and efficiency.
  arXiv  Detail & Related papers  (2024-09-16T17:01:27Z)
• Reinforced In-Context Black-Box Optimization [64.25546325063272]
  RIBBO is a method to reinforce-learn a BBO algorithm from offline data in an end-to-end fashion. RIBBO employs expressive sequence models to learn the optimization histories produced by multiple behavior algorithms and tasks. Central to our method is to augment the optimization histories with textitregret-to-go tokens, which are designed to represent the performance of an algorithm based on cumulative regret over the future part of the histories.
  arXiv  Detail & Related papers  (2024-02-27T11:32:14Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
  Bilevel problems consist of two nested sub-problems, called the outer and inner problems, respectively. We investigate the implicit bias of gradient-based algorithms for bilevel optimization. We show that the inner solutions obtained by warm-start BLO can encode a surprising amount of information about the outer objective.
  arXiv  Detail & Related papers  (2022-12-28T18:57:46Z)
• Asynchronous Distributed Bilevel Optimization [20.074079852690048]
  We propose Asynchronous Distributed Bilevel (ADBO) algorithm to tackle bilevel optimization problems. The complexity of ADBO to obtain the $epsilon$-stationary point is upper bounded by $mathcalO(frac1epsilon 2)$.
  arXiv  Detail & Related papers  (2022-12-20T07:44:48Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Computationally Efficient High-Dimensional Bayesian Optimization via Variable Selection [0.5439020425818999]
  We develop a new computationally efficient high-dimensional BO method that exploits variable selection. Our method is able to automatically learn axis-aligned sub-spaces, i.e. spaces containing selected variables. We empirically show the efficacy of our method on several synthetic and real problems.
  arXiv  Detail & Related papers  (2021-09-20T01:55:43Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• JUMBO: Scalable Multi-task Bayesian Optimization using Offline Data [86.8949732640035]
  We propose JUMBO, an MBO algorithm that sidesteps limitations by querying additional data. We show that it achieves no-regret under conditions analogous to GP-UCB. Empirically, we demonstrate significant performance improvements over existing approaches on two real-world optimization problems.
  arXiv  Detail & Related papers  (2021-06-02T05:03: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.