Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope-based Reformulation
Xiaoning Bai, Shangzhi Zeng, Jin Zhang, Lezhi Zhang · 2024
Read Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope-based Reformulation by Xiaoning Bai, Shangzhi Zeng, Jin Zhang, Lezhi Zhang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18929.txt.
Introduction
Xiaoning Bai, Shangzhi Zeng, Jin Zhang, and Lezhi Zhang published this mathematics paper in 2024. It solves bilevel optimization problems, where one optimization sits inside another: choosing hyperparameters, for instance, means the outer choice is judged by an inner model's fit. Exact inner solutions at every step make such problems painfully slow.
Their algorithm reshapes the problem using the Moreau envelope, a smoothing device, then alternates gradient steps between levels. Crucially, the inner problem is solved only approximately at each round, which is where the speed comes from. The authors prove the method settles at stationary points, and, under a standard regularity condition, that the whole sequence converges rather than wandering. Tests include a toy problem and hyperparameter tuning for a sparse group regression model, where the method behaved as theory promised. The work targets machine learning pipelines where bilevel structure is unavoidable.
Catalog record
| CREATOR | Xiaoning Bai, Shangzhi Zeng, Jin Zhang, Lezhi Zhang |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope-based Reformulation. Thanks: This work was supported by the National Key R&D Program of China (2023YFA1011400), the National Natural Science Foundation of China (12326605, 12222106, 12501429) and the Shenzhen Fundamental Research Program (20250530150024003). Xiaoning Bai, Shangzhi Zeng, Jin Zhang, Lezhi Zhang Abstract In this paper, we study a class of bilevel optimization problems where the lower-level problem is a convex composite optimization model, which arises in various applications, including bilevel hyperparameter selection for regularized regression models. To solve these problems, we propose an Alternating Gradient-type algorithm with Inexact Lower-level Solutions (AGILS) based on a Moreau envelope-based reformulation of the bilevel optimization problem. The proposed algorithm does not require exact solutions of the lower-level problem at each iteration, improving computational efficiency. We prove the convergence of AGILS to stationary points and, under the Kurdyka-Łojasiewicz (KL) property, establish its sequential convergence. Numerical experiments, including a toy example and a bilevel hyperparameter selection problem for the sparse group Lasso model, demonstrate the effectiveness of the proposed AGILS. Keywords: Bilevel optimization, hyperparameter selection, inexact, alternating gradient descent, convergence, sparse group Lasso 1 Introduction Bilevel optimization problems are a class of hierarchical optimization problems where the feasible region is implicitly defined by the solution set of a lower-level optimization problem. In this work, we focus on a bilevel optimization problem which has a convex composite lower-level problem, \displaystyle\min\limits_{x\in X,y\in Y} \displaystyle F(x,y) (1) \displaystyle{\rm s.t.} \displaystyle y\in S(x), where S(x) denotes the set of optimal solutions to the lower-level problem: \min\limits_{y\in Y}\ \varphi(x,y):=f(x,y)+g(x,y). (2) Here, X\subset{\mathbb{R}}^{n} and Y\subset{\mathbb{R}}^{m} are closed convex sets, f(x,y):{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}} is smooth and convex with respect to y on Y for any x\in X , and g(x,y):{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}} is convex but potentially nonsmooth with respect to y on Y for any x\in X . Additionally, we assume that g(x,\cdot):{\mathbb{R}}^{m}\rightarrow{\mathbb{R}} is proximal-friendly, enabling efficient evaluation of its proximal operator. Bilevel optimization originates from economic game theory, particularly the Stackelberg game [ 55 ] , and has since found diverse applications in economics [ 16 , 31 , 45 ] , transportation [ 19 , 44 ] , and machine learning [ 8 , 28 , 36 , 39 , 63 ] . Notably, many hyperparameter optimization problems can be modeled as bilevel optimization problems with a convex composite lower-level problem as in ( 2 ). Bilevel optimization has been extensively studied, with monographs [ 18 , 21 , 22 , 20 ] providing a comprehensive overview of its methodologies and applications. For bilevel problems where all defining functions are smooth, the first-order optimality conditions are used to reformulate the problem as a mathematical program with equilibrium constraints (MPEC); see, e.g., [ 2 , 6 , 43 , 51 ] . However, this approach often encounters difficulties when applied to larger-scale problems or those involving non-smooth lower-level functions, such as those with regularization terms. Smoothing techniques have also been proposed to address nonsmooth issues in specific applications, such as hyperparameter optimization [ 1 , 50 ] . Another widely used approach for reformulating bilevel optimization problems is based on the value function [ 52 , 62 ] . Specifically, the bilevel problem is reformulated as the following equivalent problem, ({\rm VP})\quad\quad\min\limits_{x\in X,y\in Y}\ F(x,y)\quad{\rm s.t.}\quad\ \varphi(x,y)-v(x)\leq 0, (3) where v(x):=\inf_{\theta\in Y}\varphi(x,\theta) is the value function of the lower-level problem. Under the partial calmness condition, Newton-type methods have been developed for this reformulation [ 26 , 27 , 35 ] . For fully convex lower-level problems, (VP) can be treated as a difference-of-convex (DC) program, as studied in [ 61 ] , which led to applications in bilevel hyperparameter tuning problems [ 29 ] . Subsequently, [ 30 ] extended these ideas to settings where the fully convex assumption is relaxed, introducing a Moreau envelope-based reformulation and corresponding algorithms. In recent years, bilevel optimization has garnered significant attention within the machine learning community, driving the development of various methods and algorithms. Among these, gradient-based approaches have emerged as particularly effective due to their simplicity and efficiency [ 28 , 39 , 63 ] . Many of these methods are built upon the computation of hypergradient or its approximation, especially in cases where the lower-level problem is smooth and strongly convex. The strong convexity of the lower-level problem guarantees the uniqueness of its solution, facilitating hypergradient computation [ 10 , 17 , 25 , 32 , 33 , 34 ] . Among these, [ 33 ] proposed a two-timescale single-loop stochastic gradient algorithm (TTSA) that efficiently tackles smooth bilevel problems. In addition, recent works have proposed gradient-based approaches based on the value function reformulation (VP) of bilevel problems, see, e.g., [ 37 , 38 , 41 , 42 , 53 ] . These approaches typically require smoothness conditions for the lower-level problem. Notably, [ 42 ] first proposed first-order penalty methods for finding \epsilon -KKT solutions of (VP) via solving a minimax optimization problem. A key challenge in gradient-type algorithms derived from the value function reformulation is the computation of the gradient or subgradient of the value function at each iteration [ 29 , 61 ] . This involves solving the corresponding lower-level problem, even when the gradient exists, as in the case where \nabla v(x)=\nabla_{x}\varphi(x,y^{*}(x)) , with y^{*}(x)=\arg\min_{\theta\in Y}\varphi(x,\theta) ( [ 15 , Remark 4.14] ). However, exactly solving the lower-level problem at each iteration can be computationally expensive, potentially limiting the efficiency of the algorithm. In cases where the lower-level problem satisfies uniformly strong convexity or a global PL condition, recent works [ 38 , 41 ] use inexact solutions to the lower-level problem, replacing the exact solution y^{*}(x) in the gradient computation, constructing an approximation to the value function gradient. But, when the lower-level problem lacks uniform strong convexity or a global PL condition, constructing an approximation to \nabla v using inexact lower-level solutions becomes challenging. Specifically, using an inexact lower-level solution y_{k} with arbitrarily small first-order residual (i.e., \|\nabla_{y}\varphi(x_{k},y_{k})\|\rightarrow 0 ) can still result in a fixed gap between the approximate gradient \nabla_{x}\varphi(x_{k},y_{k}) and the true gradient \nabla v(x_{k}) , even as k\rightarrow\infty . As an illustrative example, consider the following simple lower-level problem, \min_{y\in\mathbb{R}}\varphi(x,y):=xy^{2}, (4) where x,y\in\mathbb{R} . For x>0 , y^{*}(x)=0 , so v(x)=0 and \nabla v(x)=0 . However, for any vanishing sequence \epsilon_{k}\rightarrow 0 , consider sequences x_{k}={\epsilon_{k}}/{2} and y_{k}=1 . Here, y_{k} is an inexact stationary point to ( 4 ) for x=x_{k} , with a small first-order residual \|\nabla_{y}\varphi(x_{k},y_{k})\|=\epsilon_{k} , which can be arbitrarily small as k\rightarrow\infty . Despite this, the gradient approximation \nabla_{x}\varphi(x_{k},y_{k}) will still have a constant gap to the true gradient \nabla v(x_{k}) , since \|\nabla_{x}\varphi(x_{k},y_{k})-\nabla v(x_{k})\|=1 even as k\rightarrow\infty . This example demonstrates the difficulty of constructing accurate value function gradient approximations and developing gradient-type algorithms with inexact solutions to the lower-level problem for bilevel optimization when the lower-level problem does not have uniformly strong convexity. To overcome this challenge, in this paper, we consider the following Moreau envelope-based reformulation of the bilevel optimization problem ( 1 ), first introduced in [ 30 ] , ({\rm VP})_{\gamma}\quad\quad\min\limits_{x\in X,y\in Y}\ F(x,y)\quad{\rm s.t.}\quad\ \varphi(x,y)-v_{\gamma}(x,y)\leq 0, (5) where v_{\gamma}(x,y) is the Moreau envelope associated with the lower-level problem, v_{\gamma}(x,y):=\inf\limits_{\theta\in Y}\varphi(x,\theta)+\frac{1}{2\gamma}\|\theta-y\|^{2}, (6) where \gamma>0 . When