Moreau Envelope Based Difference-of-weakly-Convex Reformulation and
Algorithm for Bilevel Programs
- URL: http://arxiv.org/abs/2306.16761v2
- Date: Sat, 20 Jan 2024 16:41:48 GMT
- Title: Moreau Envelope Based Difference-of-weakly-Convex Reformulation and
Algorithm for Bilevel Programs
- Authors: Lucy L. Gao, Jane J. Ye, Haian Yin, Shangzhi Zeng, Jin Zhang
- Abstract summary: We present an innovative single-level difference of weakly convex reformulation based on the envelope of the lower-level problem.
We further develop a sequentially convergent Inexact Proximal Difference of Weakly Convex Algorithm (iP-DwCA)
- Score: 10.875233844414465
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel programming has emerged as a valuable tool for hyperparameter
selection, a central concern in machine learning. In a recent study by Ye et
al. (2023), a value function-based difference of convex algorithm was
introduced to address bilevel programs. This approach proves particularly
powerful when dealing with scenarios where the lower-level problem exhibits
convexity in both the upper-level and lower-level variables. Examples of such
scenarios include support vector machines and $\ell_1$ and $\ell_2$ regularized
regression. In this paper, we significantly expand the range of applications,
now requiring convexity only in the lower-level variables of the lower-level
program. We present an innovative single-level difference of weakly convex
reformulation based on the Moreau envelope of the lower-level problem. We
further develop a sequentially convergent Inexact Proximal Difference of Weakly
Convex Algorithm (iP-DwCA). To evaluate the effectiveness of the proposed
iP-DwCA, we conduct numerical experiments focused on tuning hyperparameters for
kernel support vector machines on simulated data.
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) - Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
This research presents a method to meet requirements through the minimization objective function of the RPM algorithm.
A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate.
Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
arXiv Detail & Related papers (2024-05-14T13:28:57Z) - Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions [9.518010235273785]
We present a novel fully Liploop Hessian-inversion-free algorithmic framework for bilevel optimization.
We show that by a slight modification of our approach our approach can handle a more general multi-objective robust bilevel optimization problem.
arXiv Detail & Related papers (2023-06-21T07:32:29Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields.
Recent results have shown that simple alternating iteration-based iterations can match interest owing to convex lower-level objective.
arXiv Detail & Related papers (2023-06-04T17:54:11Z) - Value Function Based Difference-of-Convex Algorithm for Bilevel
Hyperparameter Selection Problems [5.940592509070767]
We develop a sequentially convergent Value based Difference-of-Convex Function Algorithm with inexactness (VF-iDCA)
Our experiments confirm our theoretical findings and show that the proposed VF-iDCA yields superior performance when applied to tune hyperparameters.
arXiv Detail & Related papers (2022-06-13T08:51:10Z) - 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) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
Bilevel optimization is a problem of minimizing a value function which involves the arg-minimum of another function.
We introduce a novel framework, in which the solution of the inner problem, the solution of the linear system, and the main variable evolve at the same time.
We demonstrate that SABA, an adaptation of the celebrated SAGA algorithm in our framework, has $O(frac1T)$ convergence rate, and that it achieves linear convergence under Polyak-Lojasciewicz assumption.
arXiv Detail & Related papers (2022-01-31T18:17:25Z) - Inexact bilevel stochastic gradient methods for constrained and
unconstrained lower-level problems [0.0]
Two-level formula search optimization has become instrumental in a number of machine learning contexts.
New low-rank bi-level gradient methods are developed that do not require second-order derivatives.
arXiv Detail & Related papers (2021-10-01T18:20:14Z) - 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 Value-Function-based Interior-point Method for Non-convex Bi-level
Optimization [38.75417864443519]
Bi-level optimization model is able to capture a wide range of complex learning tasks with practical interest.
We propose a new interior Bi-level Value-based Interior-point scheme, we penalize the regularized value function of the lower level problem into the upper level objective.
arXiv Detail & Related papers (2021-06-15T09:10: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)
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.