Contextual Stochastic Bilevel Optimization

• URL: http://arxiv.org/abs/2310.18535v1
• Date: Fri, 27 Oct 2023 23:24:37 GMT
• Title: Contextual Stochastic Bilevel Optimization
• Authors: Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, Daniel Kuhn
• Abstract summary: 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)
• Score: 50.36775806399861
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This framework extends classical stochastic bilevel optimization when the lower-level decision maker responds optimally not only to the decision of the upper-level decision maker but also to some side information and when there are multiple or even infinite many followers. It captures important applications such as meta-learning, personalized federated learning, end-to-end learning, and Wasserstein distributionally robust optimization with side information (WDRO-SI). Due to the presence of contextual information, existing single-loop methods for classical stochastic bilevel optimization are unable to converge. To overcome this challenge, we introduce an efficient double-loop gradient method based on the Multilevel Monte-Carlo (MLMC) technique and establish its sample and computational complexities. When specialized to stochastic nonconvex optimization, our method matches existing lower bounds. For meta-learning, the complexity of our method does not depend on the number of tasks. Numerical experiments further validate our theoretical results.

Related papers

• Pareto Set Prediction Assisted Bilevel Multi-objective Optimization [2.3293561091456283]
  We address problems with multiple objectives (BLMOP) at both levels. The proposed approach is competitive across a range of problems, including both deceptive and non-deceptive.
  arXiv  Detail & Related papers  (2024-09-05T08:04:11Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  Traditional gradient-based bi-level optimization algorithms are ill-suited to meet the demands of large-scale applications. We introduce $(textFG)2textU$, which achieves an unbiased approximation of the meta gradient for bi-level optimization. $(textFG)2textU$ is inherently designed to support parallel computing, enabling it to effectively leverage large-scale distributed computing systems.
  arXiv  Detail & Related papers  (2024-06-20T08:21:52Z)
• SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity [5.046146134689904]
  We show that there is no gap in complexity analysis between bilevel and single-level optimization when implementing SPABA. We propose several other bi-loop or nested bi-level algorithms to improve the state of complexity analysis.
  arXiv  Detail & Related papers  (2024-05-29T05:36:03Z)
• FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
  Many contemporary ML problems fall under nested bilevel programming that subsumes minimax and compositional optimization. We propose FedNest: A federated alternating gradient method to address general nested problems.
  arXiv  Detail & Related papers  (2022-05-04T17:48:55Z)
• 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)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• A Gradient Method for Multilevel Optimization [8.80899367147235]
  We have developed a gradient-based algorithm for multilevel $n$ levels based on Franceschi et al.'s idea. As far as we know, this is one of the first algorithms with some theoretical guarantee for multilevel optimization.
  arXiv  Detail & Related papers  (2021-05-28T16:22:10Z)
• A Single-Timescale Stochastic Bilevel Optimization Method [34.868681953242934]
  This paper develops a new method for a class of bilevel problems that we term Single-Timescale stochAstic BiEl optimization (STABLE) method. To achieve an $epsilon$-stationary point of the bilevel problem, STABLE requires $cal O(epsilon-2)$ samples in total; and to achieve an $epsilon$-optimal solution in the strongly convex case, STABLE requires $cal O(epsilon-1)$ samples.
  arXiv  Detail & Related papers  (2021-02-09T06:35:30Z)
• 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.