A Framework for Bilevel Optimization on Riemannian Manifolds

• URL: http://arxiv.org/abs/2402.03883v2
• Date: Sat, 02 Nov 2024 05:41:49 GMT
• Title: A Framework for Bilevel Optimization on Riemannian Manifolds
• Authors: Andi Han, Bamdev Mishra, Pratik Jawanpuria, Akiko Takeda,
• Abstract summary: We introduce a framework for solving bilevel optimization problems. We present several hypergradient estimation strategies and analyze their estimation errors. We extend our framework to encompass bilevel optimization and incorporate the use of general retraction.
• Score: 16.15440177316457
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has gained prominence in various applications. In this study, we introduce a framework for solving bilevel optimization problems, where the variables in both the lower and upper levels are constrained on Riemannian manifolds. We present several hypergradient estimation strategies on manifolds and analyze their estimation errors. Furthermore, we provide comprehensive convergence and complexity analyses for the proposed hypergradient descent algorithm on manifolds. We also extend our framework to encompass stochastic bilevel optimization and incorporate the use of general retraction. The efficacy of the proposed framework is demonstrated through several applications.

Related papers

• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method [10.239769272138995]
  We propose a novel approach to solve problems in machine learning.<n>We introduce two strategies for updating the random submanifold.<n>We show how our approach can be generalized to a wide variety of problems.
  arXiv  Detail & Related papers  (2025-05-18T11:46:44Z)
• A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization [4.703514158152835]
  Bilevel has recently attracted significant attention in machine learning due to its wide range of applications and advanced hierarchical optimization capabilities.<n>We propose a plug-and-play framework named BO for developing and analyzing bilevel optimization methods.
  arXiv  Detail & Related papers  (2025-05-02T13:26:43Z)
• qNBO: quasi-Newton Meets Bilevel Optimization [26.0555315825777]
  Bilevel optimization, addressing challenges in hierarchical learning tasks, has gained significant interest in machine learning. We introduce a general framework to address these computational challenges in a coordinated manner. Specifically, we leverage quasi-Newton algorithms to accelerate the resolution of the lower-level problem while efficiently approximating the inverse Hessian-vector product.
  arXiv  Detail & Related papers  (2025-02-03T05:36:45Z)
• Bayesian Optimization of Bilevel Problems [0.0]
  This paper focuses on bilevel optimization where both upper-level and lower-level functions are black boxes and expensive to evaluate. We propose a Bayesian Optimization framework that models the upper and lower-level functions as Gaussian processes over the combined space of upper and lower-level decisions. Our experimental results demonstrate that the proposed algorithm is highly sample-efficient and outperforms existing methods in finding high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-24T15:55:30Z)
• Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
  This paper introduces a novel gradient-based approach for multilevel optimization. Our method significantly reduces computational complexity while improving both solution accuracy and convergence speed. To the best of our knowledge, this is one of the first algorithms to provide a general version of implicit differentiation.
  arXiv  Detail & Related papers  (2024-10-15T06:17:59Z)
• 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)
• 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)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization [3.867143522757309]
  This work is on constrained large-scale non-constrained optimization where the constraint set implies a manifold structure. We propose a new second-order saddleian optimization algorithm, aiming at improving convergence and reducing computational cost.
  arXiv  Detail & Related papers  (2023-02-22T00:37:44Z)
• 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)
• 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)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling. We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• A Generic Descent Aggregation Framework for Gradient-based Bi-level Optimization [41.894281911990554]
  We develop a novel Bi-level Descent Aggregation (BDA) framework for bi-level learning tasks. BDA aggregates hierarchical objectives of both upper level and lower level. We propose a new proof recipe to improve the convergence results of conventional gradient-based bi-level methods.
  arXiv  Detail & Related papers  (2021-02-16T06:58:12Z)
• 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.