Effective Bilevel Optimization via Minimax Reformulation
- URL: http://arxiv.org/abs/2305.13153v2
- Date: Sun, 19 Nov 2023 09:10:43 GMT
- Title: Effective Bilevel Optimization via Minimax Reformulation
- Authors: Xiaoyu Wang, Rui Pan, Renjie Pi and Tong Zhang
- Abstract summary: We propose a reformulation of bilevel optimization as a minimax problem.
Under mild conditions, we show these two problems are equivalent.
Our method outperforms state-of-the-art bilevel methods while significantly reducing the computational cost.
- Score: 21.895955762949885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has found successful applications in various machine
learning problems, including hyper-parameter optimization, data cleaning, and
meta-learning. However, its huge computational cost presents a significant
challenge for its utilization in large-scale problems. This challenge arises
due to the nested structure of the bilevel formulation, where each
hyper-gradient computation necessitates a costly inner optimization procedure.
To address this issue, we propose a reformulation of bilevel optimization as a
minimax problem, effectively decoupling the outer-inner dependency. Under mild
conditions, we show these two problems are equivalent. Furthermore, we
introduce a multi-stage gradient descent and ascent (GDA) algorithm to solve
the resulting minimax problem with convergence guarantees. Extensive
experimental results demonstrate that our method outperforms state-of-the-art
bilevel methods while significantly reducing the computational cost.
Related papers
- A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [60.91397373464365]
We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints.
We demonstrate its effectiveness on two well-known real-world applications.
arXiv Detail & Related papers (2024-06-14T15:59:36Z) - 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) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
We propose a communication-efficient algorithm, named FedBiOAcc.
We prove that FedBiOAcc-Local converges at the same rate for this type of problems.
Empirical results show superior performance of our algorithms.
arXiv Detail & Related papers (2023-02-13T21:28:53Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
Bilevel optimization has been developed with large-scale high-dimensional data.
This paper considers a constrained bilevel problem with convex and non-differentiable approximations.
arXiv Detail & Related papers (2023-02-03T19:34:56Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
We present a single-loop algorithm named SLEDGE (Single-Loop-E Gradient Estimator) for periodic convergence.
Unlike existing methods, SLEDGE has the advantage of versatility; (ii) second-order optimal, (ii) in the PL region, and (iii) smaller complexity under less of data.
arXiv Detail & Related papers (2022-09-01T11:05:26Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem.
Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
arXiv Detail & Related papers (2022-03-01T18:20:01Z) - 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) - 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.