Enhanced Bilevel Optimization via Bregman Distance
- URL: http://arxiv.org/abs/2107.12301v1
- Date: Mon, 26 Jul 2021 16:18:43 GMT
- Title: Enhanced Bilevel Optimization via Bregman Distance
- Authors: Feihu Huang and Heng Huang
- Abstract summary: 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.
- Score: 104.96004056928474
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization has been widely applied many machine learning problems
such as hyperparameter optimization, policy optimization and meta learning.
Although many bilevel optimization methods more recently have been proposed to
solve the bilevel optimization problems, they still suffer from high
computational complexities and do not consider the more general bilevel
problems with nonsmooth regularization. In the paper, thus, we propose a class
of efficient bilevel optimization methods based on Bregman distance. In our
methods, we use the mirror decent iteration to solve the outer subproblem of
the bilevel problem by using strongly-convex Bregman functions. Specifically,
we propose a bilevel optimization method based on Bregman distance (BiO-BreD)
for solving deterministic bilevel problems, which reaches the lower
computational complexities than the best known results. We also propose a
stochastic bilevel optimization method (SBiO-BreD) for solving stochastic
bilevel problems based on the stochastic approximated gradients and Bregman
distance. Further, we propose an accelerated version of SBiO-BreD method
(ASBiO-BreD) by using the variance-reduced technique. Moreover, we prove that
the ASBiO-BreD outperforms the best known computational complexities with
respect to the condition number $\kappa$ and the target accuracy $\epsilon$ for
finding an $\epsilon$-stationary point of nonconvex-strongly-convex bilevel
problems. In particular, our methods can solve the bilevel optimization
problems with nonsmooth regularization with a lower computational complexity.
Related papers
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
Bilevel optimization is widely applied in many machine learning tasks such as hyper learning, meta learning and reinforcement learning.
We propose an efficient Hessian/BiO method with the optimal convergence $frac1TT) under some mild conditions.
We conduct some some experiments on the bilevel game hyper-stationary numerical convergence.
arXiv Detail & Related papers (2024-07-25T07:25:06Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
We propose a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem.
Our approach is a fully single-loop method that approximates the hypergradient using only two matrix-vector multiplications per iteration.
Our analysis demonstrates that the proposed algorithm achieves the best-known convergence rate for bilevel optimization algorithms.
arXiv Detail & Related papers (2023-11-15T13:29:49Z) - 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 Penalty-based Bilevel Gradient Descent Method [40.27047651949238]
We tackle the bilevel problem through the lens of the penalty method.
We propose the penalty-based bilevel gradient descent (PBGD) algorithm.
Experiments showcase the efficiency of the proposed PBGD algorithm.
arXiv Detail & Related papers (2023-02-10T11:30:19Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
We propose a novel adaptive federated bilevel optimization algorithm (i.e.,AdaFBiO) to solve the distributed bilevel optimization problems.
AdaFBiO uses the unified adaptive matrices to flexibly incorporate various adaptive learning rates to update variables in both UL and LL problems.
We provide a convergence analysis framework for our AdaFBiO algorithm, and prove it needs the sample of complexity of $tildeO(epsilon-3)$ with communication complexity of $tildeO(epsilon-2)$ to obtain an $
arXiv Detail & Related papers (2022-11-02T13:55:47Z) - 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) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
This thesis provides a comprehensive convergence rate analysis for bilevel optimization algorithms.
For the problem-based formulation, we provide a convergence rate analysis for AID- and ITD-based bilevel algorithms.
We then develop acceleration bilevel algorithms, for which we provide shaper convergence analysis with relaxed assumptions.
arXiv Detail & Related papers (2021-07-31T22:05:47Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
Bilevel optimization has attracted increased interest in machine learning due to its many applications.
We provide a useful analysis framework for both the constrained and unconstrained optimization.
arXiv Detail & Related papers (2021-06-21T20:16:40Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems.
MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
arXiv Detail & Related papers (2021-02-15T07:10:33Z) - 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.