Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis
Authors: Yifan Yang
Hao Ban
Minhui Huang
Shiqian Ma
Kaiyi Ji
Venue: ICLR 2025 Poster (2025)
Keywords: Bilevel Optimization
Tuning-Free
Adaptive Optimization
Primary area: optimization

Abstract: Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require $\mathcal{O}(\frac{1}{\epsilon})$ and $\mathcal{O}(\frac{1}{\epsilon}\log^4(\frac{1}{\epsilon}))$ iterations to find an $\epsilon$-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. 
To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.

Published as a conference paper at ICLR 2025
TUNING-FREE BILEVEL OPTIMIZATION: NEW ALGO- RITHMS AND CONVERGENCE ANALYSIS
Yifan Yang', Hao Ban', Minhui H Shiqian Ma², Kaiyi Ji'
University at Buffalo, Meta,, 3 Rice University lyyang99, haoban, kaiyiji @bu f fa Falo...... edu, "mhhuangemeta. com, @sqma@rice.co edu
ABSTRACT
Bilevel optimization has recently attracted considerable attention due to its abun- dant applications in machine learning problems. However, cxisting methods rely on prior knowledge of problem parameters determine stepsizes, resulting in signifi- cant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features simpler fully single- loop structure that updates three variables simultaneously with theory-motivated joint design of adaptive stepsizes for all variables. We provide comprehensive convergence analysis for both al algorithms and show that D-TFBO and S-TFBO respectively require ( and O log (+)) iterations to find an e-accurate station- ary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely climinate the need for stepsize tuning, while achieving theoretical guarantees.
INTRODUCTION
Bilevel optimization has gained considerable attention recently due to its widespread use in various
machine learning applications, such as meta-learning (Franceschi et al. 2018 Bertinetto et al. 2018
Rajeswaran et al. 2019). hyperparameter optimization (Shaban al. [019]] Feurer Hutter 2019)
reinforcement learning (Konda & Tsitsiklis) (2000) HHnn et 20023)) robotics Wang et al. (2024).
communication Ji & Ying 2022) and federated learning Tarzanagh et al. (2022). In this paper, we
study a standard bilevel optimization problem that takes the following mathematical formulation:
min ((x) = = [(x y (x)) ZERds
s.t. (x) = arg min 9(x, v). yER
where f and g are jointly continuously differentiable outer (upper-level) and inner (lower-level) functions. In this paper, we focus on the nonconvex-stronglyycomve setting, where the lower-level function is strongly convex w.r.t. y and the outer function ((z) is possibly nonconvex.
Recent years have witnessed the rapid development of bilevel optimization algorithms, which can be categorized into approximate implicit differentiation (AID) (Ji et al. 2021 Dagréou et al. 20022) based, iterative differentiation (ITD) (ji al., 2022, Grazzi al. (020) based, and falue-function based (K won et al.) 2023, Liu et al.) 2021a) approaches. However, these methods often require substantial effort to tune a couple of hyperparameters like stepsizes, which typically depend on unknown problem parameters (such as Lipschitzness parameters, strong convexity parameters, and optimal function values). This emphasizes the importance of adaptive and tuning-free methods in bilevel optimization. In this paper, algorithm is considered tuning if it does not need to know the problem parameters in advance but can still achieve almost the same convergence rate guarantee as its well-tuned counterpart using this information. Despite several recent efforts

---

Antonakopoulos al. Published as a conference paper at ICLR 2025
to reduce dependence problem-specifie parameters (Fan al., 2024
2024), developing a fully tuning-free bilevel optimization algorithm remains an open challenge. For instance. Faat et al. 22024) utilizes Polyak's s stepsizes to automate both inner and outer updates but still requires information such as gradient I Lipschitzness parameters and optimal lower-level function values. Similarly, Antonakopoulos
al. (024)) introduces "on-the-fly" accumulation strategy for (hyper)gradient norms, which removes the reliance on inner and outer gradient Lipschitzness parameters but still depends on the strong convexity parameter for the inner AdaNGD-type updates.
This paper aims to close this gap by introducing two novel fully tuning-free bilevel optimization algo- rithms named D-TFBO and S-TFBO (where D and S represent double- and singlc-loop approaches), along with comprehensive convergence analysis demonstrating their competitive performance compared to existing well-tuned approaches (which tune their hyperparameters like stepsizes based on the problem parameters). Our key contributions are outlined below.
Our algorithms are inspired by the "inverse of cumulative gradient norms" strategy introduced by Xie et al. (2020); Ward et al. (2020), adapting the stepsizes based on accumulated (hyper)gradient norms. D-TFBO utilizes two optimization sub-loops: one for solving the inner problem and another for addressing a linear system (LS), which approximates the bessian-inverre-vetttee product of each hypergradient. Unlike previous approaches, D-TFBO introduces cold-start adaptive stepsizes that accumulate gradients exclusively within the sub-loops. This method establishes tighter lower bound on stepsizes, improving gradient complexity. In contrast, S-TFBO adopts a single-loop structure, where all variables are updated simultaneously in each iteration. Rather than applying the "inverse of cumulative gradient norms" uniformly to all updates, our error analysis motivates joint design of adaptive stepsizes for y. and x, which correspond to solving the inner problem, I.S, and outer problem, respectively. For instance, the stepsize for is coupled with that for y. while the stepsize for depends on both y and v.
Compared to the well-tuned AID methods Di et al. (2022), our D-TFBO method achieves the same O( 1
T convergence rate. Similarly, our S-TFBO method attains an O convergence rate, matching that of well-tuned counterparts, up polylogarithmic factors. The complexity analysis shows that D-TFBO and S-TFBO require ((4)) and ( gradient computations, respectively, to reach an c-accurate stationary point. This comparison differs from the observation in well- tuned bilevel optimization, where double-loop approaches generally achieve lower gradient complexity than single-loop methods (Ji et al. 2022). This is because the inner tuning-free solver requires ( more iterations than well-tuned methods to achieve e-level accuracy.
The theoretical analysis is inspired by the two-stage framework in Xie et al. (2020); Ward et al. (020)), where the stages describe the relationship between the stepsizes and certain constants that depend on the problem parameters. However, exploring this technical framework in bilevel problems is far more challenging because the stages for analyzing each stepsize interact with those for other stepsizes, resulting in intertwined multi-stage dynamics across different variables. For instance, the error analysis for the updates on v must account for the accumulated gradient norms from the updates on y. This motivates to couple the stepsize for e with the adaptive stepsize for to prevent the propagation of accumulated errors. In addition, our analysis requires establishing precise upper and lower bounds for all stepsizes to ensure convergence results that match those achieved under well-tunee stepsizes.
We validate the effectiveness of our methods through experiments on regularization selection, data hyper-cleaning, and coreset selection for continual learning. The results show that our methods perform comparably to existing well-tuned methods. More importantly, our methods demonstrate greater robustness to different initial stepsizes, due to the tuning-free design.
2 RELATED WORK
Bilevel Optimization. Bilevel optimization, initially introduced by Bracken McGill (173). has been extensively studied for decades. Early works (Hansen et al. 1992] Shi et al. 2005) approached the bilevel problem from a constrained optimization perspective. More recently, gradient-based methods have gained significant attention for their efficiency and effectiveness. Among these, Approximate Implicit Differentiation (AID) methods (Domke 2012; Liao et al.) 20188: et al. 2021 Dagréou et al. 2202) leverage the implicit derivation of the hypergradient by approximating it through the solution of a linear system. In contrast, Iterative Differentiation (ITD) methods (Maclaurin et al.) 2015: Franceschi et al. 2017) estimate the hypergradient using automatic differentiation, employing
2

---

Published as a conference paper at ICLR 2025
either forward reverse mode. Recently, range of stochastic bilevel methods have been developed and analyzed, using techniques such as Neumann series (Chen et al. [022] Ji et al.] 2021 recursive
momentum Yaang et al. [021 Guo & Yang 202I), and variance reduction (Yang et al. 2021). Another class of methods formulates the lower-level problem as a
constraint
(Kwon et al. 2023 Wang et al. 2023), , enabling the solution of bilevel problems without the need for second-order gradients. A more detailed discussion of related work can be found in the Appendix.
Adaptive and Tuning-free Algorithms. Adaptive gradient descent has achieved remarkable success and is widely studied and applied in modern machine learning. Early adaptive algorithms trace back line search methods, such as backtracking (Goldstein) 1962), and Polyak's stepsize (Polyak) 1969), both of which have inspired numerous recent variants (Armijo 1966 Bello Cruz & Nghia
2016 Salzo 2017: Vaswani et al. 2019, Hazan Kakade 2019 Loizou et al. 2021 OOrieto et al.
2022). To reduce the computational cost of line search and avoid the reliance on an unknown optimal
function value, the Marzilai-Borwerr stepsize (Barzilai & Borwein [988] Raydan
[993] Dai &
Liao 2002) was introduced, drawing inspiration from quasi-Newton schemes. Normalized gradient descent (Cortés 2006; Nesterov 2013] Murray et al. 2019) preserves the direction of the gradient while ignoring its magnitude, removing the need for prior knowledge about the function. Duchi et al. (201T) and MMMMahan & Streeter (2010) pioneered AdaGrad, an adaptive gradient based method, which proved efficient in solving online convex optimization problems. AdaGrad rapidly evolved for deep learning applications, giving rise to numerous methods, including popular variants like Adam DDederikk 2014; Reddi al., 2018 Luo et al. 2019 Xie al., 2024). RMSprop (Ticleman & Hinton 2012), and Adadelta (Zeiler 2012). Specifically, normalized versions of AdaGrad, such as
AdaNGD, k (Levy 2017), AcceleGrad (Levy et al. 2018). and AdaGrad-Norn (Ward et al.) 2020 Xie
et al. 2020). introduced adaptive stepsizes that require no problem- problem-specific parameters, making them tuning-free approaches. Recent work by Maladkar al. (2024) further established lower bounds for minimizing the deterministic gradient -noom. Additional methods, such as Lipschitz contact approximation (Malitsky& & Mishchenko 2020) and restart techniques (Marumo & Takeda 2024).
have also been explored. A more comprehensive discussion refers to Khaled & Jin (2024).
Adaptive and Tuning-free Bilevel Algorithms. Instead of focusing on single-level problems, Huang & Huang 2021)) extended Adam to bilevel optimization algorithms. Fan al. (2024) introduced adaptive stepsizes for bilevel problems, based on Polyak's 's stepsize and line search techniques. Most recently, (Antonykoonno et al. (2024) proposed novel framework that applies adaptive normalized gradient descent to the strongly convex inner problem and HaaGGrd-Noona to the nonconvex outer problem, allowing the algorithm to update adaptively with fewer problem-specifie parameters.
ALGORITHM
3.1 STANDARD BILEVEL OPTIMIZATION
A key challenge in bilevel optimization is calculating the hypergradient ( which, according to the implicit function theorem, is given by:
VΦ = V (x)) - V. o (r (x)) [V, V.g (o (x)) (at
when g is twice differentiable, V yug is continuously differentiable and the Hessian V V.Vaga y (x)) invertible. In practice, y (z) is not directly accessible, and one often use an iterative algorithm to obtain an estimate ý instead. Since computing the Hessian inverse is prohibitively expensive, more efficient way to approximate the ioiiian-invere--eee product in the above hypergradient (*)
by solving the following linear system:
min R(x, ú. v) V Vog(2,0)) o v',
Similarly, an iterative algorithm is usually deployed to obtain an approximate solution i of the problem in eq. (2). Given the approximates ğ and 0, the variable is then updated with hypergradient estimate given by
f ú, 0) v=,(=,)) V. (x v)o.
Standard bilevel optimization approaches select the stepsizes for updating y. v, and x based on problem-specific parameters, such Lipschitzness and strong convexity parameters (Dagréou et al.
3

---

Published as a conference paper at ICLR 2025
Algorithm Double-loop Tuning-Free Bilevel Optimizer (D-TFBO)
1: Imput: initialization zo. y0- vo. (xp
0. 10
0, 7o total iteration rounds T, and by cu
2: for 0,1, T
21-1 3: p= 0, set yf V 1
Pt
1
if 0 and yo, no otherwise
4: while vV,, ot 1 Fy do
5:
1pt1= = 2 + Vvgg(as.
y!
vi 2
Vug(Te. p= p=p+1
6:
end while
7:
P==P
8:
while [(,, V ef]l do
9:
Tot1 74 VoR(ee, M1 " wf)11, o8th = of 7041
Ve Vellar u ,,)), q 4
10:
end while
11:
Q: =
12: ai41 = ot (V Vi , I.. Jo41 = =n
1
V Vala, ,0))
13:
end for
2022 al. 2021 2022
However, these parameters are often difficult to obtain or approximate in practice, leading to significant tuning efforts. This challenge motivates the development of adaptive bilevel optimization algorithms that require less to no tuning.
3.2
EXISTING ADAPTIVE BILEVEL OPTIMIZATION METHODS
Among the existing adaptive bilevel methods, the most closely related to this work are Fan al. (2024) and /Antonakopoulos et al. (202)). Fan et al. (2024) utilizes Polyak's stepsizes and a line search to automate the stepsizes for both inner and outer updates. AAttonaooooulos al. (2024) applies AdaNGD (Levy) 2017) to solve the inner problem and updates x using the inverse of cumulative hypergradient norms, where the hypergradient norms approximated via gradient mapping (Nesterov 2013) with Fenchel coupling (Mertikopoulos & Sandholm 2016).
However, these methods are not entirely tuning-free. For instance, the initialization of Polyak's stepsizes in Fan et al. (2024) depends on Lipschitzness parameters, strong convexity parameters, and the optimal lower-level function values. While the line search approach in Fan et al.) (2024) bypasses the need for problem-specee
parameters, it lacks theoretical convergence guarantees. Similarly, Antonakopoulos et al. (2024) requires the strong convexity parameter for the inner AdaNGD updates.
3.3 DOUBLE-LOOP TUNING-FREE BILEVEL OPTIMIZATION- D-TFBO
As shown in Algorithm 1 our D-TFBO method follows double-looy loop structure, where two sub-loops of iterations are used to solve the lower-level and linear system problems. In the first sub-loop, we employ the idea of "inverse of cumulative gradient norm" design the adaptive updates as
1/
Vi
V Vyg(an (2e.3
vE), with 8 = B2 o9g(r, 12
Apt1
It can be seen from Algorithm| thhat our D-TFBO algorithm employs stopping criterion based on the gradient norm: || Vyg(,, vt 1l2 < Ey. where (defaulted to 1/ll for convergence analysis) is independent of problem parameters. The rationale behind this design is that if the stopping criterion not met (i.e., || 11,9(Iz y! I| > c,),, the accumulation 3, of gradient norms continues to increase. This increase causes the stepsize 1 to decrease to a value at which a descent in the optimality gap is guaranteed. similar stopping criterion applies the updates of og when solving the linear system.
Notably, both sub-loops utilize warm-start variable values but reset the stepsizes at each iteration (cold-start stepsizes). The warm-start variables ensure that the initial point is reasonably close the optimal solution, while the cold-start scheme guarantees stepsizes to achieve stronger lower bounds. Finally, the update of z, is based on the accumulation of hypergradient estimates V ff y/ uft).
Remark (Extension to a tunable version with problem-parameter parameter- free tuning coefficients.). Al- though A designed as tuning free method, tunable version with the flexibility to preset hyperparameters can still achieve the same convergence rate and gradient complexity. The stepsizes for far, y, v) be set (nz/ /a,, my/ my/3p, Mo/"% / and the sub-loops stopping criteria be set to
4

---

Published as a conference paper at ICLR 2025
Algorithm 2 Single-loop Tuning-Free Bilevel Optimizer (S-TFBO)
1: Input: initialization zo. flo doa, do 2 1, Ao > 0, 7o > O, number of iteration rounds T
2: for = 1, ....
do 3: S 1 V oa wOll
4: rét = 7 + I R(a,, yt, ve) 1
5: 9t+1 max m (3 7++1)
6: 0i41 oi -IV ye, mlll
yt41 Yt Pr-1 V vug( yr
8: Vt+1 = Ut 1 V. R( Vt, Uz)
P++1
9: 1++1 01119
10:
end for
AGy/ (Ty/T,C,/TT JT where (T Ty The cy. Cy) are configurable hyperparameters that independent of the problem parameters such as strong-convexte and Lipschitzness parameters.
3.4 SINGLE-LLOPP TUNING-FREE BILEVEL. OPTIMIZATION- S-TFBO
The two sub-loops in D-TFBO may complicate the implementation, and increase the number of iterations meet the stopping criterion. In this section, propose much simpler fully single-loop tuiing-free bilevel optimization method named S-TFBO, as described Algorithm
The design of stepsizes in Algorithm 2 follows similar idea in Algorithm [ In each iteration t, we update dig, Be, "/t as accumulations of gradient norms of V., Vyg. and V.R from the previous I iterations. We then update variables Yt, 1 and 2e simultaneously with adaptive stepsizes Be (8. [ However, the stepsizes for o and a are not straightforward and require careful designs guided by our theoretical analysis, as elaborated below.
Design stepsize for vt.- Instead of simply using 1, we introduce 71'' stepsize. This adjustment is necessary because V,,R(zr, Ut. vt) involves the approximation error llv: y" [z,) Since this error is proportional VV yt)ll using 3 helps control this error and prevents from exploding after accumulation, as validated in our theoretical analysis later.
ma. as the
_1_- as the stepsize for updating where the coupled Design of stepsize for øt. Similarly, we use 0,9i
factor b
is introduced to mitigate the approximation errors from the y/. and 14 updates, leading to more stable convergence.
Remark (Extension a tunable version with problem-paan laateem--prammter--iii tuning coefficients.). Sim- ilarly to Remark ! Algorithm can extend to a tunable version with the same convergence rate and gradient complexity. The stepsizes for {z, y. u) can be set as htr/pp Ny 9t. no/ (4,), where {Nx, Ny Not are configurable hyperparameters that are independent of the problem parameters.
4 THEORETICAL ANALYSIS
4.1 TECHNICAL CHALLENGES
Compared to existing single-level tuning-free approaches, fully tuning-free bilevel optimization poses unique challenges that have not been addressed well.
Compared to single-level problems, bilevel problems involve interdependent variable updates, resulting in more complex and interconnected stepsize designs.
The stages for analyzing each stepsize interact with those of other stepsizes, leading to inter- twined multi stati--tage dynamics across various variables.
The optimization error of each variable can accumulate (hyper)gradient norms from previous iterations due to the adaptive stepsize designs, complicating the error analysis.
In Section 4.2
we introduce the standard definitions and assumptions. Next, in Section 4.3 and 4.4 provide detailed convergence analysis, explaining how we address the above challenges.

---

Published as a conference paper at ICLR 2025
4.2 ASSUMPTIONS AND DEFINITIONS
We make the following definitions and assumptions for outer- and inner-objective functions, as also adopted by Ghadimi & Wang (2018); Chen et al. (2022); Khanduri al. (2021).
Definition 1. A mapping f L-Lipschitz continuous if (1(((=)) f(22)l S L||z] - x2 for Vz1. 22-
Since the outer objective function ((x) is non-convex, we aim find an e-accurate stationary point, as defined below.
Definition 2. An output Tt of an algorithm is the e-accurate stationary point of the funcctooo (x)) if (=)]=
where (0,1). Assumption 1. Functions (xr y) and g(ar, y) are twice continuously differentiable and g(x, y) is μ strongly convex w.r.t for x E RR=, E Rdv.
The following assumption imposes the Lipschitz continuity on the outer and inner functions and their derivatives.
Assumption 2. Function f(x v) is L,po-Lipschitz continuous; the gradients f v) and V Vg( y) are L.f.1 and L.pp-sisch continuous, respectively; the second-order gradients Vz (z, y) and V yy((,, y) are LLipschis continuous.
Rather than directly using the Lipschitz continuity parameters bounds gradients-whie which can cause dimensional inconsistencies during logarithmic operations we offer the following remark:
Remark 3. Assumption
2 indicates that there exist parameters Ciz, Cly, Coey and C. such that [V,, v)ll C/a, of y)ll Cfy, V V yg(zz, (z, v) S Cg., and [V (1 Uill - Cown'
Assumption 3. There exists R such that inf ((x) N
Next, we present the main convergence theorems for Algorithm 1 and Algorithm 2 along with key propositions that provide insights into these theorems. A proof sketch is provided in Appendix
4.3 CONVERGENCE AND COMPLEXITY ANALYSIS FOR ALGORITHM
Firstly, we explain the two-stage framework used in our analysis.
Proposition 1. Suppose the iteration rounds to update {x, y. o} are (Ti, Ta} and {ar, Br, 7: generated by Algorithm 1 or For any C. 2 Cog, Ce Bo C₂ 2 Yo. have
(a) either os S for any < Tú, 3kg < Ti such that oi, Ca. ak1+1 Cai
(b) either Br C3 for any t < T2, 3ke T2 such that BNg - Cg. Bkz+1 Cgi
(c) either " S C2 for any S Ts. or 3kg S T3 such that 7ha S Cyp 7ka+1 > C.p.
The analysis for each stepsize divided into two cases. Let us take (a) as an illustration example. Case 1: the accumulation a, of gradient norms is bounded by a constant C. before the end of the iteration. In this case, the average gradient norm square can be bound as T which decreases with Ti. Case 2: the accumulation at, exceeds Ca. and hence a experiences two stages: in stage 1, at < Ca. and in stage 2, 04 > C.. The eгror analysis for stage is similar to that of case 1. In stage 2, the stepsizes are small enough to show the gradient norm decreases via a descent lemma.
C²
Proposition 2. Recall that for tch iteration, the sub-loops in Algorithm 1 aim find y, and of: such that V V99( vi )|2 S Ey and [ V,,((r, vi',, .. )| Ev. Under Assumptions we have
log (gg(C//88
Binx log
L2 13 (3max C3)
Pt
log(1 + Cz)/C3)
Ey
log( C2/
C (Tima Ciy)
Jmmax log
Q. log(1 + 6,/ cx/C??) C?2)
+
1
where (Cp, C. Bmass "max are denied in eq.
eg.
22 eq.
29 in the Appendix, respectively.

---

Published as a conference paper at ICLR 2025
Ennoosttion@provviieo upper bounds Pt and Qt. which correspond to the total numbers of iterations of the two sub-loops. This result is the same as that of the standard AdaGrad- convex setting Xie al. (2020). For the sub-loop for y, in Case 1 above, the loop terminates within log(C%/ (///////olgg (log(1 + cu/ C2)) steps; and in Case 2, it takes at most log C3/ (8)) /log(1 + fg/C%) steps for stage and at most
in the strongly
log log(Lg.) (8max - Cg)/Ey) for stage 2. For ey small enough, it can be seen that Pe takes an order of 1/... which is typically larger than those obtained with well-tuned stepsizes. Based on this proposition, we can derive the following convergence results.
Theorem 1. Suppose Assumptions 2
satisfied. By setting Ey 1/T and E. 1/T, the iterates generated by Algorithm satisfy
Ci + 2c1) = 0 (
(..))
T
T
where Co and 01 are constants defined in eq. 5 and eq. (3 respectively.
Corollary 1. Under the same setting Theorem to achieve an c-accurate stationary point, Algo- Qe = (11ec) and the gradient complexity (i.e,, the number of rithm / needs = (()/c), {Pt,
gradient evaluations) is Gc(c) = ((1/2).
Theorem shows that the convergence rate of Algorithm I matches that of the standard double-loop bilevel algorithms (Ji et al. 2021 2022). According to Proposition 2 the sub-loops for updating y and require (T/Eg) iterations ensure ey-level approximation accuracy, which worse than the (1) results achieved by well-tuned bilevel optimization methods. This is because more iterations are needed to ensure high accuracy in both sub-loops, due to the lack of information about the Lipschitz parameters and strong convexity parameters. Consequently, the gradient complexity of our D-TFBO method worse than those of well-tuned double-loop methods by an order of 1 1/c.
4.4 CONVERGENCE AND COMPLEXITY ANALYSIS FOR ALGORITHM 2
Differently from D-TFBO that uses sub-loops achieve high-accurate y and e iterates, the main challenge for analyzing S-TFBO lies in dealing with the accumulated approximations errors for updating all variables over iterations. In the following propositions. we will show how we upper- bound such cumulative approximation errors and lower-bound the adaptive stepsizes.
First, we present descent result for the objective function (--).
Proposition 3. Under Assumptions 7 for Algorithm 2 suppose the total iteration number is T. No matter K1 in Proposition I exists or not, always have
(((24))) (xx)) S 2014119441
20141PP411 (1-
L as+11p+1 Vug(sr
) [[V Ve, ex)1
2
Lg L1.))
La V V.R(as, ye, v.)
1
2/12
112
P
act199+11
422 act19e+11
If in addition, k in Proposition exists, then for 2 kn, we further have
1
1
((x141) - (xx))) s
|[
IV ye, vell
2014199441
401+14p441
2
Lgg2Osy + Lsa)
V Veo(ae v1ll
L' 12|
R(2,, Vo 12
+
1
+
2/²2
112
P
act194+1
n22 act19e+11
where :: max {2(C7, 12,2/12 +1,,)b, V2C
It can be seen from Proposition that derive two distinct forms of descent results for the objective function based on the relationship between a++1 and C. (whose form is specified in eq. (41) in the appendix). Their key difference that the second inequality tighter for the case t 2 by eliminating a term of 1 VV Be, 22) Both upper bounds consist of two parts: (i) the
approximation errors y and o; (ii) the descent term - (=,(())))' / //ll////////////// (a4419411) It can be seen that there exists a trade-off: a smaller axpe: leads to notable descent, but larger approximation errors. However, due the
Mr 1= 1 [V. We, v. /
induced by the updates
7

---

Published as a conference paper at ICLR 2025
lack of information about the problem parameters, the value of ari; remains unknown, making infeasible to determine the optimal trade-off. Instead, we adjust this trade-off based on an overall bound on the descent and approximation errors, derived by telescoping all descent inequalities.
Next, we investigate the upper bounds on the summations of the positive error terms in Proposition B
Proposition 4. Under Assumptions I 2 for any 0 S kg t. for the positive error terms in Proposition 3
we have the upper bounds in terms of logarithmic functions as
Vug(ER. u1)1
V yky 2xll
I a2 log(t + b2
S 0g log(t + 1) + by.
[k+1
Pk+1
k= Ko
where 02 b2, ag. by are defined in eq.
75 in the Appendix.
suppose the total iteration rounds T. For any case in Proposition 7 we have the upper-bound of Pi and 04, in Algorithm
Proposition 5. Under Assumptions 7
Pr a1 log(t) + b1. at SCa + (as log(t) + b4 + 4((((1)) inf + (()))
where a1, bn are defined in eq. 665 and as, by are defined in eq. (79 in the Appendix.
Proposition 4 provides the upper bounds on the accumulated positive error terms Proposition and Proposition 3 shows that the cumulative gradient norms for all variables increase only logarithmically. By rearranging the terms and taking the average, we have the upper bound for the average squared hypergradient norm + - || (x+)]l? establishing the final convergence rate of Algorithm as shown in the following theorem and corollary.
Theorem 2. Suppose Assumptions
723 are satisfied. The iterates generated by Algorithm 2
satisfy
T
Σ T
2T ( (a + by + 1444(((0))) inf ((x))) (a1 lTg(T) [ b,)
1
100
+ Ca (a log(T) bu + 4 (( inf (xx)) (01 log(T) + bi) = 0 log 10g' (T)
00 441 eq. 65 eq. (79 in the Appendix.
T
where {Co, 01 by, as ba] = 01) are defined in eq.
Corollary 2. Under the setting Theorem achieve c-accurate stationary point, Algo-
rithm 2 needs T ( (2)) and the gradient complexity is Gc(e) O(² log" log((!)) (t)).
Theorem shows that the proposed 2 achieves convergence rate of O(log (T) and gradient complexity of ( 5 log"t (t)), both of which nearly match the results in Ji et al. 2022) of the standard well-tuned bilevel optimization methods up to polylogarithmic factors.
Remark 4. Note that the difference of in gradient complexity between double-loop and single-loop methods has not been observed in previous works on well-tuned bilevel optimization. This difference stems from the design of the sub-loops. In previous double-loop works, carefully selected stepsizes are used to ensure that the iterates of each sub-loop converge linearly, up to an approximation error caused by the shift in However, due to the precise control of stepsizes, tuning-free approaches can only guarantee a sub-linear convergence for each sub-loop (as shown in Proposition
5 EXPERIMENTS
In this section, evaluate the effectiveness of our proposed algorithm practical applications including regularization selection, data hyper-cleaning (Franceschi et al.) 2017). and coreset selection for continual learning (Hao et al., 2024). Our implementation based on the benchmark provided in Dagréou et al.) (2022) Had et al. (2024) respectively. Please refer to Appendix ( for more details about practical implementation, experiment configurations, and additional plots.
5.1 REGULARIZATION SELECTION
The selection of regularization be framed as bilevel optimization problem, where the inner objec- tive focuses on optimizing the model parameters on the training set Sy = {(dtrain grrain) h sigsn while the outer objective aims determine the best regularization term À the validation set
8

---

Published as a conference paper at ICLR 2025
Sy ((djal yf " Disssm Denote the model parameters by 8 Rº" and regularization term by E I2,, then the outer and inner problems can be formulated as
f(0,A) 1 Σ U((do), ), g(0,
2.rain), - Σ ((ddrain 3/ ), 0) + R(0, A),
where the loss (((d,: v:), 0) log(1 + exp(_y,d, 0), and R(0, = exp(Axe ) represents the regularization, where each element 0% is regularized with strength exp(Ax). We compare our proposed algorithm with benchmark bilevel algorithms including AmIGO (Arbel & Mairal 2022).
BSA (Ghadimi & Wang 2018). FSLA (Li et al. 2022), MRBO (Yang al. 2021). SOBA Dagréou
et al. 2022). StocBiO (Ji et al. 202Th. SUSTAIN (Khanduri et al. 2021). TTSA (Hong et al. 2023b).
VRBO Yang et al. 2021 the Covtype dataset. More details are provided in Appendix B
0.85
Ami20
0.50
Amio0
0.50
BSA
0.89
B5A
FSLA
193
50BA
50BA
0.50
0.87
S00:BC
0.45
VRBC
0.40
5-1180
5:180
D-1150
0.35
D-TTRO
0.84
0.30
0.62
20
25
Iterations
Iterations
(a) Covtype
(b) MNIST
Figure 1: Comparison with other bilevel methods. (a) Regularization selection on Covtype dataset. (b) Data hyper-cleaning on MNIST dataset.
As shown in Figure Ia| our D-TFBO achieves the fastest convergence rate, while S-TFBO converges slightly more slowly but remains comparable other well-tuned methods.
5.2 DATA CLEANING
The training set Sr (ddfrain , rrann Jisign have been corrupted in this scenario, where the label of a data sample could be replaced by a random label with a certain probability p. It is important to note that we do not have prior knowledge about which data samples have been corrupted. The objective is to develop a model that can effectively fit the corrupted training set while performing well on the clean validation set Sy = {[dgat ) We conduct experiments the MNIST dataset, where we aim to learn a set of weights X, one for each training sample, in addition to the model parameters 0. Hence, the outer and inner problems are
[(0,A)=
= m j=1
1 m
Σ ((dd)'t (u, ),0); ((0,))= = ni Σ
(As)) ((dtrinn ,y, ./ train), ),rin),)) + C/10113
where (-) is sigmoid function, C' is a regularization constant, and loss function (((d, y;), 1/(1 + exp(-y:d, 0)). Ideally, would like the weights to be for the corrupted sample and for the clean sample. More details can be found in Appendix
B We compare the performance with other bilevel optimization methods including AmIGO (Arbel & Mairal, 2022). BSA (Ghadimi & Wang 2018), FSLA (Li et al. 2022), MRBO (Yang et al. 2021), SOBA (Dagréou et al. 2022), StocBiO (Ji 202T). ), SUSTAIN (Khanduri et al. [2021). VRBO (Yang et al., 2021). The results presented in
al.
Figure 1b demonstrate that our algorithms achieve convergence rate comparable to other baselines.
5.3
CORESET SELECTION FOR CONTINUAL. LEARNING
Coreset selection aims to improve training efficiency by selecting a subset of the most informative data samples, which can be used as an approximation of the entire dataset. Thus, the model that minimizes the loss on the coreset can also minimize the loss on the entire dataset. Following the design in HHo al. (2024), we apply the proposed algorithms to coreset selection for continual learning. The inner problem learns model parameters 6, and the outer problem determines the distribution À (0 < Ag) < and |A]] 1) over the entire dataset
S(0,)) = Σ ((0)) CR(A) s(0,)) = Σ A0)(()),
9

---

Published as a conference paper at ICLR 2025
Table I: Results on Split CIFARI00. The best and second best results are in bold and underlined.
Balanced
Imbalanced
Method
Ar
FGTT
Ar
FGTr
k-means features
57.82=00.69
0.070=+0.003
45.44=0.76
0.037++0.002
k-means embedding
59.77=0.24
0,06110.0001
43.91=0.15
0,044110.001
Uniform Sampling
58.99=0.54
0.07411.004
44.73=0.11
0.03310.007
iCaRL
60.74_1.09
0.04410.026
44.25-2.04
0.042-100099
Grad Matching
59.17=0.38
0.067=0.003
45.44=0.64
0.038+00001
GCR
58.73=00.3
0.073=0.013
44.48=0.05
0.035=0.005
Greedy Coresct
59,39=0.16
0.066=0.017
43.80=0.01
0.039=0.007
PBCS
25.64
0.062-10.001
39.87
0.07611.011
BCSR
6..40
0.051
47.30 0.57
0.022
S-TFBO
08.95
0.046=0.009
45.78=0.70
0.036=0.005
D-TFBO
59.54=0.45
0.041=0.005
46.68=0.72
0.029=0.002
Table 2: Experiment results of sensitivity analysis on Split CIFARIO0. The initial values refer to the constant learning rates in BCSR or 00.90.% in S-TFBO and D-TFBO.
Method
initial =
initial =
initial = 6
initial = 8
Relative Average Change
BCSR
59.42
56.25
58.75
57.55
5.8% 0.4%
S-TFBO
58.85
58,55
58.69
58.47
D-TFBO 59.71
59.62
59.11
59.08
0.3%
where n is the sample size, C' is a constant, Aya) is the i-th entry. R(A) = Σ B(A + 5z) denotes the smoothed top-K regularizer, where is constant and z ~ NO, 1). App is the i-th largest component. The regularizer encourages the distribution have K non-zero entries, corresponding to the size of the selected coreset. Following Zhou et al. (202)), we use the Split CIFAR 100 dataset and conduct experiments the balanced and imbalanced scenarios. We compare the proposed algorithms with various methods, including k-means features (Nguyen et al. 2018). k-means embedding (Sener Savarese 2018). Uniform Sampling, iCaRL (Rebuffi al. 2017), Grad Matching (Campbell & Broderick 2019). GCR (Tiwari et al. 2022), Greedy Coreset (Borsos et al.) 20200) PBCS (Zhou et al. 2022), and BCSR (Hao et al. (024). with the last three being bilevel optumization-bnn based methods. We evaluate the performance using the average accuracy and forgetting measure across all tasks after learning task T. The former is defined Ar = ΣT= aT,,, where dr,; is the test accuracy of the i- th task after learning task T. The latter is defined as FGT, = T Σ = [maxxee,....1- -1- (aj, ar,,)] The results are shown in Table Each experiment is repeated three times and the average is reported. can be observed that our D-TFBO achieves the best FGTT under the balanced setting and the second-best performance under the imbalanced setting.
Sensitivity analysis w.r.t. different initial learning rates. The tuning-free design provides another benefit. The proposed algorithms demonstrate more robustness compared to the Hao al. (2024). We conduct a simple sensitivity analysis under the balanced setting, regarding the learning rates in the inner and outer loops. Specifically, we set the initial learning rates in Hao al. (2024) and ag, fb. Yo in S-TFBO and D-TFBO for the inner and outer loops to {2, 4, 6, 8). where the original values are set to 5. We run one experiment for each learning rate. Further, we compare the changes average accuracy Ar. We also compute the average and report the relative change compared to the results presented in Table
6 CONCLUSION
We introduce two fully tuning-free bilevel optimization algorithms, D-TFBO and S-TFBO. Both methods adaptively update stepsizes without requiring prior knowledge of problem parameters, while achieving convergence rates comparable to their well-tuned counterparts. The experimental results show that our tuning-fres free design performs comparably to existing well-tuned methods and is more robust initial stepsizes. We anticipate that the proposed algorithms and the developed analysis can be extended to the stochastic setting, and the proposed algorithms may be applied to other applications such meta-learning, few-shot learning, and fair machine learning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Yifan Yang, Hao Ban and Kaiyi Ji were partially supported by NSF grants CCF-2311274 and ECCS- 2326592. Shiqian Ma was supported in part by NSF grants CCF-2311275, ECCS-2326591 and ONR grant N00014-24-1-2705.
REFERENCES
Kimon Antonakopoulos, Shoham Sabach, Luca Viano, Mingyi Hong, and Volkan Cevher. Adaptive bilevel optimization. ICLR revision, 2024.
Michael Arbel Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In International Conference on Learning Representations, 2022.
Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1): 14::141444,, 1988.
José Yunier Bello Cruz and Tran TA Nghia. On the convergence of the Barward-baekwart splitting method with linesearches. Optimization Methods and Software, 31(6):1209-12388 1238, 2016.
Luca Bertinetto, Joao F Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. International Conference on Learning Representations, 2018.
7alán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33: 1889999444, 2020.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357,22 2015.
Trevor Campbell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. Journal of Machine Learning Research, 20(15): 2019.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In Proceedings The 25th International Conference on Artificial Intelligence and Statistics, 2022.
Jorge Cortés.
Finite-time time convergent gradient flows with applications to network consensus. Auto- 2000, 2006.
matica,
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-2671 2022.
Yu-Hong Dai and Li-Zhi Liao. R-linear convergence of the barzilai and borwein gradient method. IMA Journal of numerical analysis, 22(1):1-10, 2002.
Kingma Diederik. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Justin Domke. Generic methods for optimization- modeling. In Artificial Intelligence and Statistics, pp.
PMLR, 2012.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
11

---

Published as a conference paper at ICLR 2025
Chen Fan, Gaspard Choné-Ducare Mark Schmidt, and Christos Thrampoulidis. Bisls/sps: Auto-tune step sizes for stable bi-level optimization. Advances in Neural Information Processing Systems, 36, 2024.
Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated Machine Learning, pp. 3-33. Springer, Cham, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proc. International Conference on Machine Learning, pp. 1126-1135, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-basse based hyperparameter optimization. In International Conference on Machine Learning (ICML), pp. 1165-1173, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riceardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learming. In International Conference on Machine Learning (ICMI.., pp. 1568-1577, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.022446, 2018
Allen A Goldstein. Cauchy's method of minimization. Numerische Mathematik, 4(1):146 1500 1962.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint
2016.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp. 3748-375 PMLR, 2020.
Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint 11x.x:2000002266, 2021.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and- rules for linear bilevel programming. SIAM Journal Scientific and Statistical Computing, 335):1194-1211 1992.
Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. Advances in Neural Information Processing Systems, 36, 2024.
Elad Hazan and Sham Kakade. Revisiting the polyak step size. arXiv preprint 190000105..00333 2019.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023a.
Mingyi Hong. Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1)1147-180 2023b.
Feihu Huang and Heng Huang. Biadam: Fast adaptive bilevel optimization methods. arXiv preprint arXiv:2106.11396 2021.
Kaiyi Ji and Lei Ying. Network utility maximization with general and unknown utility functions: A distributed, data-driven bilevel optimization approach. Submitted, 2022.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference Machine Learning, pp. 4882 4892. PMLR, 2021.
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. Advances in Neural Information Processing Systems, 35:3011-3023 2022.
Ahmed Khaled and Chi Jin. Tuning-fres free stochastic optimization. In Forty-first International Conference Machine Learning, 2024.
12

---

Published as a conference paper at ICLR 2025
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via couble-momenumm Advances in neural information processing systems, 34:30271-30233 2021.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, pp. 1008-1014, 2000.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. A fully first-order method for stochastic bilevel optimization. pp. 18083-18113 2023.
Kfir Levy. Online offline conversions, universality and adaptive minibatch sizes. Advances in Neural Information Processing Systems, 30, 2017.
Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. Advances in Neural Information Processing Systems, 31, 2018.
Junyi Li. Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with
theoretical guarantee. arXiv preprint arXiv:2009. 000600,09,00600, 2020.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp.
7434,, 2022.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent paok-propagatton. In International Conference Machine Learning, pp. 3082-3091. PMLR, 2018.
Bo Liu, Mao Ye. Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35: 17248-17262, 2022.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, 2020.
Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-biit based interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning, 2021a.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34: 8662-8675, 2021b.
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. International Conference on Artificial Intelligence and Statistics, pp. 1306-1314 PMLR, 2021.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differenniation. In International Conference on Artificial Intelligence and Statistics, pp. 1540-1552. PMLR, 2020.
Liangehen Luo, Yuanhao Xiong, and Yan Liu. Adaptive gradient methods with dynamic bound of learning rate. In International Conference Learning Representations, 2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- -based hyperparameter optimization through reversible learning. In International conference on machine learning, pp. 2113-2122. PMLR, 2015.
Devyani Maladkar, Ruichen Jiang, and Aryan Mokhtari. Convergence analysis of adaptive gradient methods under refined smoothness and noise assumptions. arXiv preprint arXiv:2406.04592. 2024.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna- fional Conference on Machine Learning, pp. 6702-6612, PMLR, 2020.
13

---

Published as a conference paper at ICLR 2025
Naoki Marumo and Akiko Takeda. Parameter- free accelerated gradient descent for nonconvex minimization. SIAM Journal on Optimization, 34(2):2093-2120 2024.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint urXiv:1002.40 1002.4908, 2010.
Panayotis Mertikopoulos and William H Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297-1324, 2016.
Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64(11):4818 4824, 2019.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course, volume 87. Springer
Science & Business Media, 2013.
Cuong V. Nguyen, Yingzhen Li, Thang D. Bui, and Richard E. Turner. Variational continual learning. In International Conference on Learning Representations, 2018.
Antonio Orvicto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. Advances in Neural Information Processing Systems, 35:26943-26999 2022.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pp. 737-746. PMLR, 2016.
Boris Teodorovich Polyak. Minimization of nonsmooth functionals. Zhurnal Vychislitel noi Matem- atiki Matematicheskoi Fiziki, 93):509--521, 1969.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-lcarning with implicit gradients. In Advances Neural Information Processing Systems, pp. 113-124, 2019.
Marcos Raydan. On the barzilai and borwein choice of steplength for the gradient method. IMA Journal of Numerical Analysis, 13(3):321-326, 1993.
Sylvestre-Alviss Alviie Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Shoham Sabach and Shimrit Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
Saverio Salzo. The variable metric forward-backward splitting algorithm under mild differentiability assumptions. SIAM Journal on Optimization, 27(4):2153-2181, 2017.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back propaagaatnion for bilevel optimization. International Conference on Artificial Intelligence and Statistics, pp. 1723 1732, 2019.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In Proceedings of the 40th International Conference on Machine Learning, pp. 30992-31015, 2023.
Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63, 2005.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-295, 2017.
14

---

Published as a conference paper at ICLR 2025
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pp. 21 21146-21173 179. PMLR, 2022.
Tijmen Tieleman and Geoffrey Hinton. Rmsprop: Divide the gradient by running average of its recent magnitude. coursera: Neural networks for machine learning. COURSERA Neural Networks Mach. Learn, 17, 2012.
Rishabh Tiwari, Krishnateja Killamsetty, Rishabh Iyer, and Pradeep Shenoy. Ger: Gradient coreset based replay buffer selection for continual learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 908, 2022.
Sharan Vaswani, Aaron Mishkin. Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019.
Chen Wang, Kaiyi Ji, Junyi Geng, Zhongqiang Ren, Taimeng Fu, Fan Yang, Yifan Guo, Haonan He, Xiangyu Chen, Zitong Zhan, et al. Imperative learning: A self-supervised neural-symbolic learning framework for robot autonomy. arXiv preprint urXiv:2406.16055 2024.
Xiaoyu Wang, Rui Pan, Renjie Pi, and Tong Zhang. Effective bilevel optimization via minimax reformulation. arXiv preprint arXiv:2305. 2023.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1-30, 2020.
Xingyu Xie, Pan Zhou, Huan Li, Zhouchen Lin, and Shuicheng Yan. Adan: Adaptive nesterov momentum algorithm for faster optimizing deep models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In International conference on artificial intelligence and statistics, pp. 1475-1485, PMLR, 2020.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 14:13700-13682, 2021.
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. SimFBO: Towards simple, flexible and communication- efficient federated bilevel learning. Advances in Neural Information Processing Systems, 36. 2024.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212.577, 2012.
Xiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin, Zonghao Chen, and Tong Zhang. Probabilistic bilevel coreset selection. In International Conference on Machine Learning, pp. 27287-27302 PMLR, 2022.
15

---

Published as a conference paper at ICLR 2025
Supplementary material
A ADDITIONAL DISCUSSION ON RELATED WORK
A. 1 COMPARISON WITH THE EXISTING BILEVEL METHOPS
We compare the proposed D-TFBO and S-TFBO with standard bilevel methods in Table Notably, both D-TFBO and S-TFBO achieve (nearly) equivalent convergence rate other methods without requiring additional tuning.
Convergence Rate T
Gradient Complexity
Hyperparameterrs Tune
Algorithm
Sub-loop K
AID-BIO Ji al. 2021
0(1)
O(2)
ITD-BiO (Ji et al.
2021
(log({))
O logg(()))
SOBA (Dagréou al.
2022
((1)
(
O(2)
D-TFBO (this paper)
((2)
(
S-TFBO (this paper)
O(1)
O Io))
O log (t))
Table Comparison of the proposed Luiig--free methods with existing standard bilevel optimization methods.
A.2 THE NECESSITY OF THE ITERATION NUMBER T
It is possible to eliminate the dependence on the knowledge of iteration T in S-TFBO. In detail, we can modify the "for" loop in S-TFBO (Algorithm 2 to a "repeat until convergence" structure, as in Marumo & Takeda (024), and this allows S-TFBO to converge any targeted e-stationary point without the knowledge of total iteration number T. However, D-TFBO (Algorithm]] [T] requires the sub-loop stopping criteria to be set e, 0 ( c. O which depends prior knowledge of T. Thus, D-TFBO may not be feasible.
A.3 SUPPLEMENTARY RELATED WORK ON BILEVEL OPTIMIZATION
Initially introduced by Bracken & McGill 1973). bilevel optimization has been extensively studied for decades. Early works (Hansen al. 1992; Shi et al. 2005 Gould et al. 2016 Sinha al. 2017)
solved the bilevel problem from a constrained optimization perspective. More recently, gradient- based bilevel methods have gained significant attention for their efficiency and effectiveness in addressing machine learning problems. Among them, approaches based on Approximate Implicit Differentiation
(AID) (Domke 2012 Liao al. 2018 Pedregosa 2016 Lorraine et al.) 20220; Grazzi al. 2020
Ji et al.) 2021: Arbel & Mairal 2022 Hong et al. (202bb) exploit the implicit derivation of the
hypergradient, approximating by solving a linear system.
On the other hand, approaches based on Iterative Differentiation (ITD) (Maclaurin et al. 2015 Franceschi et al.] 2017]] Finn al. 2017 Shaban et al., 2019 Grazzi et al.) (0200 estimate the hypergradient by employing automatic differentiation, utilizing either forward or reverse mode.
series stochastic bilevel approaches has been developed and analyzed recently, utilizing Neumann series (Chen et al.] [2022 Ji et al. [021] Arbel & Mairal (202), recursive momentum (Yang et al.
2021 Huang Huang. 2021 Guo Yang (021), and variance reduction (Yang al. 2021
Dagréou et | 2022). etc. For the lower-level problem with multiple solutions, several approaches
were proposed based on upper- and lower-level gradient aggregation (Sabach & Shteen| 2017; Liu
et al. 2020: Li al. 2020), barrier types of regularization (Liu et al. 202 (022), penalty-based formulatin lations (Shen& & Chen 2023), primal-dual techniques (Sow et al. 20022.. and dynamic system-
based methods (Liu et al. 2021b). Another class of approaches formulated the lower-level problem
as a based constraint (Kwon et al. 2023 Wang et al. 2023) to solve bilevel problems
without second-order gradients.
16

---

Published as a conference paper at ICLR 2025
B SPECIFICATIONS OF EXPERIMENTS
B. PRACTICAL GUIDELINE
In practice, D-TFBO ensures higher accuracy, as shown most of our experiments but is harder to implement and the sub-loops cause the waiting time to update S-TFBO achieves slightly worse performance but it has advantages such as simple implementation and no waiting time for updating æ.
As practical guidance for practitioners, D-TFBO is well-suited for scenarios requiring high accuracy, while S-TFBO preferable for simpler implementation and no waiting time when updating the objective variable.
B.2 PRACTICAL IMPLEMENTATION
For regularization selection and data hyper-cleaning, we use the benchmark provided in Dagréou et al. (2022). For coreset selection, we use the codebase from Hao et al. (2024). We implement D-TFBO using "for loops" as an approximation, since the magnitude of [[ Rx,, y, v) Algorithm [ varies across different experiments. Specifically, the number of loops for updating y and v in regulanization selection and data hyper-cleaning are both set 10, while the numbers of loops for updating y and in coreset selection are and 3, respectively.
AmA50
Amt5O
0.50
B5A
B5A
15LA
FSLA
0.55
MB80
MA80
505A
S0BA
$0..80
Stac0
0.45
SUSTAN
SU6T4N
VI20
6.10
VI80
5-1F20
0.35
5-7P0
D.TP8
0.84
D-TFB0
0.30
10
20
100
Time [sec]
Time [sec]
(a) Covtype
(b) MNIST
Figure Comparison of running time on regularization selection and data hyper-cleaning.
B.3 CONHIGURATION
We adopt the default configuration for regularization selection and data hyper-cleaning. The batch size 64. The maximum iterations are 2048 and 512. respectively. The data corruption ratio in hyper-cleaning is 0.I. For coreset selection, we also use the default configuration except for the leaning rates, due to the tuning-fii design. The on, So. and Yu values are set to 5.
2.50
2.50
BCSR
2.2
D-TBC
Upper loss
1.75
3.75
1.50
1.50
1.25
0.75
0.75
0.50
0.50
3000
5000
8000
Task
Time [sec]
(a) Task
(b) Running time
Figure 3: The upper loss of coreset selection.
17

---

Published as a conference paper at ICLR 2025
B.4 ADDITIONAL RESULTS
For regularization and data hyper-cleaning, we also present the loss curves regarding running time in Figure 2 Our methods exhibit faster running time than other baselines on the Covtype dataset. For coreset selection, we adopt the default settings of initial values, such as the constant learning rates in BCSR and ag. 3g. To S-TFBO and D-TFBO, all set to 5. We re-ran the methods on Split-CIFARI00 100 under the balanced scenarios and recorded the loss and running time. The loss curves regarding task and running time are shown in Figure Following Hao al. (2024). we plot the loss value every 5 mini-batches. The loss decreases gradually but increases when new task is encountered. Additionally, S-TFBO converges faster than BCSR (Hao et al. 2024), while D-TFBO performs comparably to BCSR (Hao et al. 2024).
C PROOF SKETCH
The proofs of Propositions In this section, we present a high level proof sketch that outlines the convergence and gradient complexity analysis of Algorithm and Algorithm 2 emphasizing the key challenges and our technical innovations.
and 5 can be found in Lemma
respectively.
Proof sketch of Algorithm
Step 1:
We first discuss the two-stage framework in our problem in Lemma 4 and we develop two forms of descent lemma of the objective function in Lemma 7 based on the two stages of ag in Lemma
Step 2: We developed upper bounds of a, under the two stages in Lemma
Step 3: We provide the maximum iteration numbers for the sub-loops approximating y (ar)) and 0" (z1).
Step 4: Combining the results in Step and Step 2, we telescope and take the average of the inequalities in the descent lemma of the objective function, then obtain the convergence rate.
Step 5: Combining the maximum iteration numbers in Step 3 and convergence rate in Step 4, we obtain the gradient computation complexity to find c-stationary point. Then the proof is complete.
Proof sketch of Algorithm 2:
Step 1: We first discuss the two-stage framework in our problem in Lemma and we develop two forms descent lemma of the objective function in Lemma based on the two stages of a, in Lemma
Step 2: We develop a rough upper bound of two important components in the descent lemma in R(v. where l2 and 13 represents the
Lemma 11 Σi=
[V and Σ kk=kg Pp41
B2+1
second stage in Lemma
Step 3: Following the results in Step 2 and the upper bound of in Lemma 10 we obtain a two-way relationship between (P+11 and Σ Ei=o f which further indicates the logarithmic upper bounds of both terms in Lemma 15 and Lemma
16
respectively.
Step 4: Incorporating the results from Step into the rough bounds from Step 2, we can also obtain logarithmic upper bounds Σt=h,
[[V.ger..))1 and Ek=ks [V..R((r.. IlI in Lemma
Be+1
Pk+1
Step 5: We rearrange the terms in Lemma 11 and incorporate in the results Step 4, we obtain two forms of the upper bound of a, in Lemma 17.
Step 6: Combining the results in Steps 3, 4, 5, we telescope and take the average of the inequalities in the descent lemma of the objective function, then we obtain the convergence rate.
Step 7: Without sub-loops, via the convergence rate in Step 6, we can directly obtain the gradient computation complexity to find e-stationary point. Then the proof is complete.
18

---

Published as a conference paper at ICLR 2025
D
PROOFS OF PRELIMINARY LEMMAS
Lemma
WWrd et al. (2020)
Lemma 3.2). For any non-negative ai,.., ar, and d1 2 1, we have
Σ
log
Σ a1 +1.
(4)
-=
Lemma 2. Under Assumptions 1 2 we have basic properties as follows:
(a) ((x) is La-smooth w.r. a, where La == (L5.1 + LnaCty )1+
Caay
P
(b) y" (z) is Ly-Lipschitz continuous w.E. 2, where Ly = Cony,
(c) the gradient estimator [ y, v) is (I122 + l1g,1) -Lipschitz continuous w.r.t. (x, y). and Lg Liipschtz continuous w.r.t. o;
(d) v fl v) can be bounded as [Z. w)ll S Co ||v|| Cz..
Proof. The proof of (a) and (b) refer to Ghadimi & Wang 2018). For (c), under Assumption 2 we have
[V/(1,,31, 0) V5(2, W2, w)1l S V (0(,, V. V Vug(22 82)1 ||a||
+ + f v2)l
< < + [ z2 + 11 - y2ll)
[V - (I m2)
|| - m2ll = L |1 021l-
By Assumption 2 and Remark 3. we can easily prove (d) as
(.,( w) < V (z s)ll ||aa| + [Vz((, S Cony |u + Ct. Then the proof is complete.
Lemma 3. Under Assumptions as follows:
we have basic properties of linear system function R in eq.
(a) R(x y, v) is p-strongly convex and
w.r.l. v; (b) V, 6) is 2L1.2 + Liipschit continuous w.r.f. (x, v);
(c) V. R(R, v. v) can be bounded as || U,) s Co., |||||| + Cz,
(d) 0 (x) in eq. 2 can be bounded as [10()))] s Stx, and 6* (x, y) == arg min, M(x, v) can also be bounded as 1|0* (1, (e.v))l & Ciy;
#
(e) o² (x) is L, Lu-Lipschitz continuous W.E. and 0" (I., v) is L--Lisschitz continuous w.E.t where L, = L1.1
Ciy (1 + Iy) and L., == Lea + Cs. Lyg
n²
Proof. First all, since V. V, R(, y, = v, V Vyg(z, y), we know ul 1 V V (zg Thus,
according to Assumption 2 we have
VV. V. v1), V, V. y. e2)1
VV V lll -2ll S Cavy 1lu2 -222l-
Then (a) is proved. Next, by using Lipschitz continuity in Assumption 2 have
V R(21, v) V.R(22, y2, w)ll < V V 1z6z v1) - v. V.g v2)1 ||l||| V (z1, vn) - (=
+
(L + 1,1)((121 2zll + 1l v2ll.
19

---

Published as a conference paper at ICLR 2025
Then (b) is proved. By Assumption
we can easily prove (c) as
(V, v)ll & V1 V y0(2,
||l|| + wfffe,,,) - 1orr || + Cs..
Next, for i (z, y), we have
V.R(I, 8 0", V, () - -v,(a))) = 0,
which indicates that
Cl /
(1: s)1l =I V b0, V ( w)|l - [ V (0( 111 VV ())) -
VV.
Since o² (z) is a special case as (2) = 0r (z. yn (z)). (d) is proved. The proof of the first part of (e)
can refer to Lemma 4 in Yang et al. 2024); for the second part, we have
| (a, v1) 6' (z, 02)ll
= =|[V, v.. (V,(a,) [2
vz)l
Vo (V,
v..((r,
+ V vn)) "V, ||
1 11v1 vall Cf | (1
11
L
Cj. C Ilvl
yall-
f n²²
Thus, the second part of (e) is proved and the proof of Lemma 3 is complete.
Lemma 4. Suppose the iteration rounds to update (r, y, r) are {Ti, T2, Ta} and (ar, Ber Veh are
generated by Algorithm or For any C. Z -oo, Cg 2 Bo, C2 7o. have
(a) either as < for any S T1, or 3kg S Ti such that ak, S Ca, aki+1 > Cai
(b) either 3, S C3 for any t 1 T2, or 3kg < T2 such that 9kz < Cg. Beg+1 > Cg:
(c) either " S for any
any 1 < T3, or 3kg < T3 such that 7kg S Cny 7hat1 > Cr:
Proof. The proof resembles the Lemma 4.1 in Ward et al. (2020). Here we only prove part (a), and the other two are similar. Note that if ar; Ca. then there must exist k S T' such that ak, S Ca. akit1 > Ca. because Ca 2 og and the sequence {a+} is monotonically increasing. Otherwise, we have at S or, I C. for any < Ti. This completes the proof of part (a).
20

---

Published as a conference paper at ICLR 2025
E PROOF OF THEOREM 1
We define some notation for convenience before proving Theorem
E.
NOTATION
Here, we define the following constants thresholds for parameters Sp. Yas ar in Algorithm 1
Co == max {2Lg, ao), Cp == max (L.. 90): Cy: == max {Cavv: }0
(5)
E.2 PROOFS OF PRELIMINARY LEMMAS
Lemma 5, Under Assumptions 2 for any t 2 in Algorithm
7 have
llvl* v" (x,)
yy 122
10
0* (1t, (Ft, >|l
co
where Ey and Eu are sub-loop stopping criteria in Algorithm
Proof. For the ke iteration, according to the stop criteria of the sub-loops, we have
| Vzg vi )12 S Ey. V vi: 222')1" S Ev.
By using Assumptions
we have
llu." y" (1x)) -
Vug(or, v..)) (0((F,)"((1)))) 1 by
1
1/ - 8* (x )1
_/2
1
V
R 8/ (1:1)= V V, vi¹ a0 (o ()) 1
n22
1
since 1/ (Vgg y (x+)))1
0 and V R
(2t, Vi 0 (zt, Vi "f )] 0. Thus, the proof is complete.
Lemma 6. Under Assumptions 22
2 for any 1 Algorithm have [ ye o0 )|ا² <
Say C?
Oj. where Cf =
1C3,)
Proof. For the ken iteration, we have [V vf 0012
<2 / Vf Pt -f "0' ( || + 2 2 ve 6 (xr, 1)
2 V. (eg (z,, v/ (2) - 80 (xc, 1| 2| V. Vug(a, De Pt 10 (t - v, f( Ve )
< V. v.gl v1 )1( 1: 0 (a 2h
p I| + 2 V. v vgg(z,, Me )0 (x.. - vyl ue )|
(4) 20 2C cv
1C2, o2,
+ 407,,
2²
2
where (a) uses Assumption
Remark Lemma and Lemma 5
Then, the proof is complete.
E.3 DESCENT IN OBJECTIVE FUNCTION
Lemma 7. Under Assumptions 2 for Algorithm
7 suppose the total iteration number is T. No
matter by in Lemma 4 exists or not, we always have
((I+t)) (4()))
1
[V
(1-
La 20141
[V ,
é'
204+1
201+1
204+1
(6)
in addition, kn in Lemma 4 exists, then for t KT, we further have
((x441) <Φ(x))
1
1
VV We
Q 11
é'
20r+11
4ac+1
201+1
where é' = (ey 6v) and i= max (2(
T2
C2
12) v2Com..
Nun
21

---

Published as a conference paper at ICLR 2025
Proof. From Lemma 2 have ((x) is Lg- smooth. So we can apply the descent lemma to d
((1++1) (2(x)) + (V xs+1 - x²) + La
|| - xel1?
2
1 (v)())); (Mr, vi u/ (1)))
Lx
=0(x))
a++11
20
-1(x)) 201+1
1
[V
1
Vf
(0 V1 1/2 )12
20
+ 201+1
[ - Vs(E,, 2r
(f "11) (8)
20
where the approximation error
[ - V (x vf ur )1?
= ( /² (z:)
ve 0, )1
(x.)) VI "t (=i))]
2 (m.) v ( u )1?
4 V Vyg((rr (a)) (z.) - v, V v [1. vi (m)))
4
V.J (2:)) - V,f(2, v + 2| v, ve -x)) e1
2
09, L2.2
12,11 11v." y (x))) 20 Mxv 11 0' (s:)]l
112
Og 122
<4
+ 17,1) 1l n (wx)) + 10 syy 11 o* (Ir, wa )1 402yy 110 (ar, o² (xx))l
42
Gj 12222
+ Lř + c I' l1v1 y (x=))] 40 11 6' y1 211
4²
<L (1ly. n (2x))l 11 0 (ar,, (z:))
(9)
where (a) uses Assumption 2 Remark
3 and Lemma 3 (b) uses 00x1) 6t (2r, (x:)) and
Lemma 3 By using Lemma we have
L (e, + Ex) =:
(x.)) - Vf v of ||
< 122
(10)
By plugging eq.
10 into eq.
8 we obtain
Now if in addition, k; Lemma exists. then for t > k1, we have a141 Co 2 2Lg. From (6) we can immediately obtain 77. Thus, the proof is complete.
E.4 THE BOUND OF at.
Lemma 8. Under Assumptions
2 suppose the number of total iteration rounds in Algorithm
is T. If there exists kı < T described in Lemma 4 we have
C2 <C.,
S Kii
2te'
0: SC, + 2c0 +
12 k1
On
where we define
L2
Co = -2((())) inf (()) +
(11)
20
When such kn does not exist, we have a C. for any T.
Proof. According to Lemma 4 the proof can be split into the following three cases.
Case 1: if oer Ca. for any / < T, have the upper bound of a++1 as 06+1 Ca.
22

---

Published as a conference paper at ICLR 2025
Case 2: if cer Cas there exists 1 S T described in Lemma 4 Then have the upper bound of ac+1 as a1+1 I Ca for any < kj.
Case 3: in the remaining proof, we only consider and explore the case b S t S ' when oT Ca.
From Lemmal 7 for 2 ki, we have
o ( (p()))) 2ax+1
1
, 11 + 2ax+1
4ax+1
which indicates that
[ Dk UK u
M1
S - - ((x+1)) + 2
0k+1
0x+1
By taking summation over k: = ki,..., ,,, we have
f U .uk 111
26'
($(#)) ((Fx++1) +
0k++
Or++1
k=k1
k=ki
2
=4 ( ((((++1))
+
(12)
a++1
k=R1
For ((xx,), by telescoping 66. we get
h-
L
(xx,)) (10)))
(0))))
(13)
4a
20
Plugging eq. 13) into eq.
12
we obtain
Va Uk
)
<4(0b2o) - inf (n)) +
-- Ls | [V
Σ
ve 2=)0
2
0h+1
ah+1
k=k1
k=
La Σki
| Vf
veth 20 11
2
<4(2((0)) im)) +
ag
<4(4(z0) inf ((x)) Lea
+ 2(1 +
an
an
L2
2(1 + 1)e'
<4(0(zv)) inf (x)) +
+
(14)
ag
Inspired by Ward et al. (2020) and using telescoping, we have
(x,, ve 2 111
04+1 =0
a1+1 + a4
[ Pt 11 )|
Q
Sa.
a++1
[ Uk , U/
Pe Qu )12
Sak,
ax+1
k=ki
<Ca + (2))))) - inf ((x)) + L2
2(t + 1)e
+
an
0g
Thus, the proof is complete.
23

---

Published as a conference paper at ICLR 2025
E.5 CONVERGENCE ANALYSIS OF SUB-LOOPS
Lemma 9. Recall that for the tu iteration, the sub-loops in Algorithm aim to find vi and ui
such that V Vag(Ze, ut )12 S Ey and V RRRR ,0,, ,,(²))12 S Ev. Here prove that
log log(C3/88)
Amax log
L L - CB)
Pt Ps
(15a)
log(1 +zy
1
Ey C2 (Tmex - Cn)
log(C,//i)
QisQ'=
+
Tmax
log
(15b)
log(1 + t,// CG)
1
6v
where Pmax == C3 + 1g +
20 ot
p²ag + 2 loog(Cs/ - 1) and Tmax == Cg + C guw
2
8C4 + 1ogg(Cn/70) + 1).
Proof. The proof is split into the following two parts.
Part maximum number for convergence of g vf+).
Inspired by Xie al. (2020), split the analysis into the following two cases.
Case 1: 22 does not exist before we find P.. This indicates 3r. < Cg. Referring to Lemma 2 in Xie
1og(C2/93)
et al. 2020), we have Pa < log(1 log(1=c,/C3) and therefore the desired upper bound for P, holds. This /og(
can be proved follows. If P. log()+<,/Cg
have the following result.
8/ = pp 1 Vg Vr 111
| V (, Vi 211
P (1
BP.-1
300 II
P--1
(1
V Vug(Te, vz 111
$8
p=0
2
1 +
by
2 Cz.
(16)
C3
This contradicts 3p. < Cg.
Case 2: 122 exists and Pt 2 12. Here we have Bbg C'g and 3ks+1 Cp.
1og(C3/88) log( (m(ltry/C3)
Firstly, we prove 12 S
log( CC) Similar to Case 1, if 12
following eq. by
replacing Pt with f2, have
Ey k/ C3
32 2 38
1+
C3.
which contradicts 3k, < Cg.
Secondly, referring to Lemma 3 in Xie et al. 2020). we have the bound of 1| 22:))) as
l Ao yy yx(x))11
V Vyg( (vt, -
11
to
y" (x=e)
8k2
-11v -1 3¹ (xx)))1
V Vyg(ze, v1
12
2 k2
1/2
(xx).
V
Vyg(ze,
Bbg
(a)
Vygl(ur Wt
102
< 1 1---- 3² (xx)))1 +
|| Vyg((ee - (xx))
Bko
Bkg g.
24

---

Published as a conference paper at ICLR 2025
Vug(z
U1 ko
11
< <1Ivt= y- (xx))1 +
Ely8 y² xxxx))11
+
Dz+1
p=
(6)
S -11B1- 1 -3((2))1
Veg 1/3
+
p k=
V 20 (2,, 1/1112/88
p=0
(0)
V (F vf 112
2211v6-11 y² (z+-11)) + 211y" (Ix-1) 3d (2 + log
+
B
(d) 26y
2C2
[2 11 V-- 1
p Q: 101 )|
V V (Fe, of 112
S
gry
log
+11
112
pPaj
38
(c) 25y
202 9j
AsN p2aB
2lgg(C))))) +1,
(17)
122
where (a) uses Assumptions
(b) refers to the warm start of yp: (c) uses Lemma I (d) uses (e) follows from Lemma and 3rr S Cg.
2
Lemmas and 5
Last, following Xie et al. 2020). for all P > k2 we have the bound of llvε - y" (2re) as
= P- y" (x:))11 + VV 1)12
2(v1 - 1" (w+), Vng(Ers Vi 1)
llve" - (xx))))
B7
3p
3p (2 (2- [
<11y, P-1 30 (x:))12
(vp-1 - Vog(Ie. v1-)
3p
1116 1-1 35 (x:))1
3p (ve" p- - -1' (xz),, Vyg(Fe.ve ((
(6)
2 (1 gP 11 P-1 vxxx))12
2 MI /r 110t22 v
(2) Se MP 12)
22g
2C Of
+ +2 logg(Ca/ +1):
+
(18)
422 pZag
where (a) uses Br 2 C3 2 1 (b) uses Assumption (c) follows from 3p Co > L, م
and 1 - m - for < m < 1; (d) refers to eq.
17 Inspired by Lemma 4 in Xie et al. 20220).
we have the upper-bound of 3p as
IV Vyg( P 112 < Brg +
V Vag )2
Bp = 3p
(19)
Bp + 8p-1
Bpt1
p=
To further bound the last term of the right-hand side of eq. following result:
119
using Assumption 2
we have the
llv!" - v² (xx))1
V Vyy(e,, V1 )112
2(vt r1 - (I1), V Vyg(Er, vi 11)
- -1lvh-- - -,"((x)))
B7.
Bp
(0)
V (w v
2)1
2 uf (1) (
8 <1182" P-1 - ->(()))
87.
BpLg.1
(6)
I V2 Vi P 11
<1lv6-1 y² 3xx)))12-
|| 12 yf') 1
<11i.0 - 3² (2,))1
(20)
Sp+ Lg.1
k=
25

---

Published as a conference paper at ICLR 2025
where (a) uses Assumptions 12 (b) refers to 3p Cg 2 Lg.1. 1. By rearranging eq. 20 and using
eq. (17 we have
V Vag 111
S وو 1 (xx)))1 -lve v
8pt1
|1
(x+))1
20 gan o7
2gg
+
+ 2 (ogg(Cs/P)) )
(21)
112
12a0
Plugging eq. (1 into eq.
19
we obtain the upper-bound of 3p as
Bp S C3
+ Lg1
20 112
+
202
Bay of
+ 2 log((23/ +1) =: Bmax.
(22)
2
Then, by plugging eq.
22 into eq.
18
we have the upper bound of ll - y² (x+))l as
202 OZy Cf
lovf (2,)l S e (P
2ey
2 2log(Ca/86) +1)
(23)
12ag
(gg(C%//3)
Recall we have the upper bound 22 v
Note that Pt defined in 15a satisfies
Towl (eellee//C0
Amux
p' lig
log (Lg1 (3max - Cg)/En)-
1
By replacing P with in eq.
23 we have
|I Vygg(r ue 111 < 12, - (x:))1 S - Bene I (Amax C3) S Cy.
Therefore, P. S P' and this completes the proof of 15a
Part HI: maximum number for convergence of R(E,, vi 22))
Similarly Part I, we split the analysis into the following two cases.
Case 1: K3 does not exist before we find Q.. This indicates Qq. < CT. Then we have Q: < (0g(0)/0))))) log(1 log(1+c./0c)
1=g(C2//0)
we have the following result. Otherwise, if Q2 2 log(1+(./Cg)
3.. - + R(x,, vi 21 y1-2
V R(,, Ui 2.
222--1112
2
[1+
QQ:
12
Q
VV Rr,, Vi 21 1112
,0
270 2
II
|
7Q.-1
q=0
Q
270
2
1
+
> C2.
This contradicts yO, < Cz.
Case 2: ka exists and Q: 2 1z. Here we have 7hg S C.yy and Nktt1 > Czy
Firstly, we have hig < 1og(C(,170)
log(O /20) Tog(I+r./ /C2
Tog( +r. Similar to Case 1, if Ki
following eq. (16 by
replacing Qt with k3, we have
Ey k3
22 2 7
(1
>
22
which contradicts 7k Cy:
26

---

Published as a conference paper at ICLR 2025
Secondly, referring to Lemma 3 in Xie et al. (2020), we have the bound of 1oo 2² e2x2))1 as following:
V R(1,, yi" ./ -
8 (Ie: vf.²) ||
|| ||050 80 (xe: v.. )1(
1/ As-1
Vkg
V R(ee, we, 12a-1)
ka- 1 0r (ar. Vi 11( +
= 1/4
Ykk
2 (0 M 0 (11, ve )r V R(y, Vi u/ 21
Yka
V V,,R( Ve 1t
Po Kig 2
Ag 1
0" (1 }|( +
1/2
Tki
2
Ve Bi 11 - - V R( (It, Ui 7.00 (f )) 1?
Kk
9yy
V R(re, ve u/c
Aa-
00 (xt. )1?
+
Yks
V. R(I,, Vi (1))
<1108 8* (F )1
Iks
R( vi 129112/788
1 11000 ( ))1
Ek=0
V Ro Vi ,.)))11/7
(0) P1-1
S 1/
00 (30-11 >1 + 2 80 (55--1,9611 - 00 ( ve |1
+ log
V R vf ot |1 /// +1
<2 <2|10/11
Pr-
0* ( (x1-1) 11 -. I| + 4 11 (Io- 21))) "F)'
1--1
ka-1 1
+ log
IV R( vi o/ =f311/788 +1
9=0
(4) 26,
8C2
Ju
+ 2log(Cr/70) +1,
(24)
42
4²2
P. = 0: (b) refers to the warm start of of; (c) where (a) uses Lemma 3 and V V. (z,, y Pt 0* (oe, V/2
uses Lemmal] [
(d) follows from Lemma 3 and Tik S C.,
Last, similar to Part I, for all Q > K3, we explore the bound of 1|e - u² (2x))] as 10 - 6* 6"(ee, v6 )1
V R..R y y c, )1
-11 -1108- - 50 (xx ue )12
2412 8-1 80 (ot, Pt),
V. R(
yr
Pt ,0 (1-)
7Q
(0)
< <1108 2-1 1 0'(2 (Ze, v2: )11
_
1
2
9vv
(of 0-1
-0 60' ). V V. v. 10 0 1)
TQ
7Q
(h)
1- 8$ (ot, v/ )12
1
(08
8r (0 ). B. .0--1)
7Q
22 (1- # 1100-1 - -0 Ve' ('r)) )||²
70
(8)
#(Q k/3//10 11:20 8² (xt, vt )1
27

---

Published as a conference paper at ICLR 2025
(c) Se p(Q k2)/10 -1Q-ka)/7a
2gy n12
803 +2log(Cy/10)
Ju
(4//10) + +1),
(25)
where (a) uses Lemma 3 (b) follows from TQ > C. 2 C 9yN' (c) uses V v,R(a , v())) = 0
and Lemma 3 (d) follows from TQ 2 C. 2 C 9uu 2 and m S e for 0 < m < 1; (e) uses
eq. (24). Similar to eq. (9.. we have the upper-bound of sQ as
R( vi ,0, Q 11?
Re ve 21
QQ = -Q-1+
S 7kg
(26)
QQ 7Q-1
74+1
To further bound the last term on the right-hand side of eq.
[26). we can have the following result:
|V R( V1 2 Q ']12
|1 8* (x v. )11
- v || -
2008 8 00 w/ ), V R(r, Di
7Q
(0)
10 10--1 8" (x,, )1
V R..
R(x, Mi
Pt Q
)12
1Q
2 V R.l(a ve ,u; 1 - V. (2,, Vi 00 (2 21. |]
12 Co
(6)
V Ro Vi
Pt ,24 .00--11 )1 2
$ 8-1 6 (Ft, )1
7Q Cgv
V R(EE ve eiil
Na 0" (x ve )1
(27)
1o+1 C9p
where (a) uses Lemma 3 (b) refers to Ta 2 2C, 2 Cayy By rearranging eq. we have
27 and using eq.
V R( u0?))
SCou (1
0" (21 v.
2
00 0" a. 111))
7/+1
8C2
<C
22y n12
+ n²
2lgg(C,,/7) + +1)
(28)
Plugging eq. (33 into eq. 20
we obtain the upper-bound of ga as
SC2
20g 12
log(( + +1) =: Ymax-
7Q S C, + Cg.
+
+
(29)
1²
Then, we have the upper bound of 1109 80 (at; vi 122 as
8C2
||o@ - 8 (2 ve )1 Se -lQ. ham
2cy 112
fn. + 2 log((,//7)) +1) +1).
(30)
n2a
1og(C2//61)
Recall we have the upper bound K3 I log(I+e.//C C2] Note that Q' defined in 15b satisfies
Q' 2 kg + Timax log (C2 Abv (7mmxx - Cr)/ex).
By replacing Q with Q' in eq.
30 we have
6* )/ V R(z,, yf of 2|1 < c (
< <e-n(Q' u(( (u((('ka)))))) -ka/ ("inx C.y) S Ey.
Therefore, Q S Q' and this completes the proof of (1bb.. Thus, the proof is complete.
28

---

Published as a conference paper at ICLR 2025
E.6 PROOF OF THEOREM 1
Here we suppose the total iteration round is T. According to Lemma 4 the proof can be split into the following two cases.
Case 1: k does not exist. Based on Lemma we have or S Ca. Then by Lemma
we have
[ S 2()(2))) - -0(x(()))))))))))))))))))) +
IV of 0z (22
a++1
2a
a++1
where e' is defined in Lemma 7 By taking the average, we have
(++)))1
(b(zo) ((T))
Le 1
V v.. .00 f/)
+ T t=0
T-1 é'
T
at+1
T
20 T
a4+1
1=
1
inf (x)) + L 2 (nf
(31)
T
20
a0
T
1
where op is defined by eq.
11) in Lemma
Case 2: 1 exists.
For 1 according to Lemma
we still have
[ 2( (xx) (1²+11) 20
La
(V vi of o
e'
(32)
a++1
a++1
For L 2 ki, we have at C.. Using Lemma
we have
[
< 2 ((((()))((((441))) + e'
(33)
a++1
as+1
By merging eq.
32 and eq.
33
and taking an average from t = O...., T 1, we have
k
T
[V
a1+1
T 1=
a1+1
T
a++1
t=
T
T-1
2
S T
( (I0o) - -((xr) +
Vf
B
12 T
20 T
a++1
1=
7
1 2(((zz)) - inf ((x)
Lo
02
a
Co
é'
(34)
20
2
000
a0
where co is defined in Lemma This result is the same as eq. 2, we have
3I.. Thus, for both Case 1 and Case
T-1
(x:)))
1
T
v+(x)))
L. ( 2(0(z))) inf -inf +
< T
T
QT
T
a1+1
2a
1=
which indicates that
L2O2
<
T
2 -in +
20
0g
aT
0
(a) 1
(2 (2(0(a)) - inf (())) + La C2
Te
T
20
ag
L2
2T'
C. + 4( inf +(x)) +
(35)
=
ag
agg
where (a) uses Lemma To achieve the 0 ( convergence rate, we need d' ((/TT) in eq. 35
This can be guaranteed by taking (y = 11/T and 6, = =//T, which implies (see Lemma
1 T
2
Lg LT21) +1 1.2 1.2
2
(36)
P
2
29

---

Published as a conference paper at ICLR 2025
For symbol convenience, here define
1 2 Lo2Cl, L12) 1 13 11) I2 +
21.²
c + ag 4?
(37)
p
n2
where is defined in eq.
11I.. Thus, we can obtain
(C + 201
0 )
T [
T
T
Thus, Theorem 1
is proved.
E.7 COMPLEXITY ANALYSIS OF ALGORITHM| 1 (PROOF OF COROLLARY
Recall in Theorem
we take = 1/T, cv 1/T, and we obtain
1
(C + 2c1) [o(x:)|
T
T
1=
To achieve e-accurate stationary point, we need
vD(21)1 < (C + 201)
Se ie., T= O(1/e)
(38)
T t=
T
Recall in Lemma 9 we have
()g(0)/)))
Bmnx log
1g ( -cp)
P. < log(1 (1 + :2g/O))
+
Cy
log (C3/38)
3max log
TL2 (8max - C2)
log(1 + +e) log )
+
log(1 + 1/C/T)
1
When is sufficiently small, we have
+ log (t)) = ( + log (t)) O(1/e).
Pt P 0
(39)
log(1 +e)
Similarly, we have
Q: =-=0 log(1+ [ (1og/11+ log (t)) 0 log (t)) O(1/c).
(40)
+e)
We denote Gc(c) the gradient complexity, then we have
Gc(E) = T' max(ft + Qc) = 0(1/e).
Therefore Corollary I is proved.
30

---

Published as a conference paper at ICLR 2025
F PROOF OF THEOREM 2
We define some notation for convenience before proving Theorem 2
F.1 NOTATION
Below, define several preset constants for notational convenience their first use. We first define some Lipschitzness parameters for ((x) as
L (L,11 + I1g2C(1) (2 )
Bay
1
L : m {2
lo 122
C 12
L +
L771)
.22CAu ANN
Next, we define the following constants as thresholds for parameters Bk. Yk. ag. as
2L4 400
Ca := max
a
C. max { -u+ Lg
2uLg11
So. 64a 1
r Lug1
PC
C max 22(u= Comu)
Yo, 64a 1, CoNN
1 Caus
C. C Cyy
(41)
where the constant og detined as
os : (-(( A(p Canu) + 8) Lg + bsa)²² +1)
(n + 1 2sg
MCaus
4(1x + Mu Tig.)
T1ge00s + t1/))²
1(p + )
1² Lg
pC 70
F.2 A ROUGH BOUND 2k
Lemma 10. Under Assumptions for any t 2 O in Algorithm 2 we have ||vell S
L2 x
/2C Vt.
Proof. By strong convexity of g in Assumption I we have
Pl 2
V Vg (Tx. (x
(o yn)ek
V y1 Σ
2 V (xx.
1=1
V. W. Uhs 22 +
Σ 2 v Vf (4]12
k=1
k=
2 2 2tC
which indicates that for any 1 0, ||ve|| can be bounded
(2 + 21C7,)
(2pt+1 + 21C7,)
< V2(pm11 + VFC,,)
||
(42)
1
Then the proof is complete.
31

---

Published as a conference paper at ICLR 2025
F.3 DESCENT OBJECTIVE FUNCTION
Lemma 1I. Under Assumptions 7 2 for Algorithm
suppose the total iteration number is T. No
malter ky in Lemma 4 Aexists or not, we always have
$ ((x-1)) (1()))
(1-
L
|1 (2t, Ve, we)l
204+19t41
201+14t+1
act194+1
T,2
2
Ly + +baa))
Voggar Bill
1.a
V.R( Vt. 12)l
+ 2/²²
+
a1419141
122
01414t+11
(43)
If in addition, hn in Lemma f exists, then for t hi, we further have
1
(I++1) (x(e))
| - 10r+19++1 |
(It,
Me, vz)ll
200+119t41
2
Tt + L.,.1)
27
L V. R(re, Ve, ut)l
1
+
2/²2
122
00419941
4²2
0++ 19+1
(44)
where L = max {2(
+ +17,1)
/2Cgvuh
4
Proof. From Lemma we have ((x) is Lg smooth. So we can apply the descent lemma to & as
Lxp
(12241) <1))))) + (V 2441 xza)
|1c411 xell?
2
1
L
=(())
(2.. + (V A
I [Te, v/)
a4t194+1
20 20
-((1))
[+(x))] 2014189441
| (II, Vt, v:)l
20141
L
2004 [V((x;)
+
[Vf Ne. 0.)1 (45)
20
and the approximation error
(V.) (f 1z)
v / (I (1z) (x:) V VS vr, 2
(xx) - f (z+, Ve, u (0, - Vf Mes )1
V, Vug (2 (zt) (z))) (xx)
V, Vgg( (x))))
+ 4 V (1t, (z:) Vyf y0l 2 V Vyg(ze, (e -x)))
G 1.2
<4
+ 13,11 I1ye y" (xx))1 + 20 2n 1lue 0" (2
42
<T.2 (llve (z:) 12 + ||0, u² (ax (1)))
(46)
where the third inequality used results from Lemma 3 By plugging eq. (46) into eq. 445 we have
(I+-1) ((x)))
1
2014144411 (1
Lg
Mt, v),1
200+1
a1419441
(11v - y² (xx)) + Ilue 2² (2+))12))
(47)
19441
Note that g(ø, y) is j--strongly convex in y and R(I, v) is p-strongly convex in v. So here we can bound the approximation gaps llve (2;))1 + e| o (x:) by [/ v1 )12 and R[Te, Be, 22 as
llve-" (xx))1 + lIve v² (xx))1
32

---

Published as a conference paper at ICLR 2025
1
V V 31) - V y (xx))
V.R(Ee.M...) - V R(,,, v- (xx))
12
V 134 Me )1² +
2 V. R( Vt, 21)1
12a
2
V (Tt Me, v² (x1) (zH
112
2
[ +b,
L5,1 ) l1 - (xx)]l
V
Veg )1 +
V R(x,, Me, 2 1t)1 +
112
112
1 2
T.g,2tte + Ln,)
2 V Me, w))l
V V w0)l +
(48)
122
P
122
where (a) and (d) use the strong convexity;
and V. 2. y (x), (x)) 0: (c) uses Lemma 3 By plugging eq. (48) into eq. 47 we obtain
(b) and (d) result from Vug (2, y" (x))
eq. (43
Now if in addition, k in Lemma 4 exists, then for / 2 k1s we have 0++1 C. 2 2L0/ From we can immediately obtain Thus, the proof is complete.
Note that to further explore the bounds of the right- hand side of eq. 43 and eq.
44) in the above
lemma, we next show the (summed) bounds of [[V and RV..
B6-1
(Pr-1
Lemma 12. Under Assumptions 7 for Algorithm
2 suppose the total iteration rounds is T. If k2 in Lemma 4 exists within T iterations, for all integer E (k2, T), we have
Vug(TR,
(μ + Cg1)
(4 18
(e 1
yee mx)
Bk41
2²
pby
a441
k=b2
k=
Proof. For by <t < T, we have 3ke S Cgg and B:41 Cg. For any positive scalar Net1. using
Young's 's inequality, we have
[1 - y² (a--1) S (1 Aet1)ll - (x:))1 + (1+ Xea1
1 1
[110 1L)lll
y (11+1))2 (49)
For the first term on the right hand side of eq.
449 we have
Ilue+1 - y (22))
- 1106 Bet1
Veg(Ee,)1) - y" (1z))(
1
2
-Ily=
y" (2))1++ +
(ye (xx), Vyg(zs,81))
32
Bi41
(0)
2
1
11ue - (xx)))1
+ Be41 Br+1
| Vy v1)1
Bet1 (H + L..1)
1 g.
(b)
211lig.1
1
11 (x,)11
V Vug(22, v1)1
(50)
Be+1(u+ Lg.1)
3 + 4g,1)
where (a) uses Lemma 3.11 in Bubeck et (2015); (b) follows from 8.41 2 C3 2 p + I. By
plugging eq. (50) into eq. 49 we have
||v++1 y² (11+
2pLg.1
<(1 + Set11)
1 Be+ (11 + Lg.1)
11ve v² (x:)11 (1 + det1) Be4rl Lg.1)
V Vyg(ze, wcl1
+ 1 1)1b Ilu" (xx) - y² (112.)
(51)
de+1
By rearranging the terms in eq. (11) we have
(1+det1) 3 + L V Vog(a,,
33

---

Published as a conference paper at ICLR 2025
(1 + det1)
(1 1-
2uLgt1
11ve - y² (xx))] 11 - yd (x
Bet (11 + l(g.1)
(1 1
110 (xr) -V (12+1))1
Act1
We take
det1
2
Since Bi+1 Cs 2
20kar1 #
in eq. (41) we have det1 S 1. Then
we have
V yz 1=)1l
5(1 + )(+1) |1 "yg(orr31)l1
Br+1
Bo+1
[( + 1.g.1) (llye- y (xxe)) - -Ilue+1 - yf (x=++1))²)
+ 2(μ + l( 110 (x+)) (x(++1))1
d-1
(a + L.g.) - y² (xx))) - -Ilyc+1 - 1/" (1++1))
+ (a + 12 110" (2xx) '² (x(++))11
plyy11
(4)
- (p + Lg,1) (11v 1y (xt))1 11 - of (1²4
+ (n + I2
pLg. || s++1ll? 11?
where (a) uses Lemma
2
Summing the above inequality over is = ke...., t, we have
V Vyg(ak.Bu)l
B141
k=kg
Vyg(Ee. Uxll
Bx+1
k==g--
S(p + Lg.1)llbkk - -0 (2 (p+ + 1
BK+1llEx
2x+1ll2
p
k=
(a) 11 + I.g.1
||
Vyg(okk 11, 110 V Vog( 11. 2:
112
(N + 122
Gk+1
/ (Ixx yk. Ux)1
ax+1 p
k=
11 + Ly.1
(n + 12
I far. Uk. u4)ll
-1
Uk. 11)2211)11 1)11
112
pla.1
of 1P441
k=
(6) (1 + Lg. 133
(++ + 1
IV Mb. 22)11
12
phn11
a7+1PK41
k=
(e) (1 + C3
(nt + Igg1) I
(μ+ + 1I Ly
| f Mee 02)ll
(52)
2
1P0
pbgd
PP411k
k=
where (a) uses Assumption (b) results from || (1
< Bh S Cz: (c) denotes
PP = max (Bo, ).). Then, the proof is complete.
Lemma 13. Under Assumptions] for Algorithm
2 suppose the total iteration rounds T. If kg in Lemma 4 exists within T iterations, for all integer E ka, T), we have
V a R(xx, yk. 12)
34

---

Published as a conference paper at ICLR 2025
4(4 + C LigaCte + +113.)) ) 4(p + +Cg C2
11
112
4(u (an))( (u+ bigiliy (192011 + Tuga1
2 kg
V [ yke 11
+
Ly11100
ax+1
1==
4(1 + +c L2
[ Uk: vx)1l
PC On
ak+1
k=ks-1
A(1t + Cguu )
+88
(
[TaaChh + 11s,1
2
VV VZ 91)1
+
11Cgu 9vy
112
3x+1
Proof. For Kis St < T, we have N41 > Cy. For any positive scalar det1, using Young's inequality,
we have
| - 6² (I++1)11 < (1 + ) (x,))1 - + (1
tea1 ) I|ee (xx) 0" 0x(x2+1)1 (53)
For the first term on the right hand side of eq. 133 we have
1| 2x=)))
-||0r 1p++1
V. R(rs Wc: vz) v² (az)]]
2
-1luz u- (xx))l
IV... yh, wx]1
(vr u0--vaaa (xx), V. V.R(s,, (c.)), (54)
Pi+1
Pt+1
For the last term of the right- hand side of eq. 54 we have
{wee v² (xxe, V R(x,, v1, 0t))
(vx v² (x V. Me, vo) V V.li(a ye, v
(vt "² (zt), V V. Me, 1² (x+) v R(R, (II), (x:)))
(0)
1
MC 1lue - 0² (x,)))?
V. R(Ra,, Br, v2) V.R( (z)
# + Cavv
1
Can
# + Oauu
||
NI We, 60 (xx)) - v (x))))
2g00gm
110e vi(x)))
2( + Cgmu
(
V VuR(EE, Dr, v2)1 + V..((rr Me, v² (xx))
2( + Comu)
11 C..
# + Cgvy
V R.RR,, 11, 10 (x+)) V. R(a, (xx) ( (xx))]?
1C Auu
Ilve - 0" (2x))1
2(p + Comu)
1
MC 9uz
V Mer ut)1
1l 1² (xx))1
2(μ + Camu)
2(u + Cann)
11 Cauy Vo (Ie, Bes u² (2+)) -R.((E y (x)), x0 (x:)
+ Cggn
2410 Sww
(d)
1
MC Gov
R. Ve. 12)1
+ ((on)) |1 1i4-v" (1ve-(((xa)) (xx))2
2(p + Cgmu))
2(1++
+ # Caun
) (T.g22llu (x+))l + T.g,1 1.9.)31111 - 3 (x.))1
+ 11 + Caun
35

---

Published as a conference paper at ICLR 2025
(4)
1
PC
$ 2( + Cguu)
VV R(ae, Mc. ve)l
1 - v² (x,))l
2(μ + Cavv
+ + Cavn
To + 11,.1
2
1iVe - y1 (x+))
(55)
16 Cga
2yCgoo
-ala- where (a) follows from Lemma 3.11 Bubeck et al. 2015); (b) uses -Ila - b11 - -| + |||
since I|a - + b1|2 I 2|la- - b + 2| : (c) uses V. R y (xt), u² (x²)) = 0: (d) and (e) follow
from Lemma 3 Plugging eq. (55) into eq. (54). we have
|1e+1 8² (ate)1?
PC 9vy
1
1lee 0 (xx))1
(1 (Anv))fe41
F++1
Ps+1
++ Cavs
2
H + Cgux
C
L9220r + +I.s.1)
1
+
+
llve y" (1x))1
11 Csv
NC
1
D1+1
pC
2( + Cany)Pen 110e - 8 (xx))1
1
V R(r. vill
(n Covr }
2
H u+
(1a2Ohh + 11g.1
2
1
+
llye y (x:))1
(56)
11
Buv
P
Ft+1
where (a) follows from PP+-1 2 m+1 2 Ciyy 2 2(μ + Cguy). Combining eq. 56) with eq. 53 we have
11:41 0² (1c+1))11
HC Suv
5(1+ + )esi)
11ue v² (xr)]1
(1r + Ogvy )Pett
-(1 + set1)
VoB(Iee (e, u1)l
2(p + Comd)pet
+ 1 + Cgus
[1gaCt + 11s11) )
2 1 lIve y² (xx))11
+ (1 + setz)
+ Can
yeC
gp+1
+ (1+ det1
1100 - (11++1111
(57)
By rearranging the terms in eq. (7 we have
(1 + )et1)
V R( Dr, St, 11
2(1 + Con))ppH
pC
5(1+ + deti)
(1-
11ve v² (xx))12-
- -1lue41 - ((((+)))l)
(e+ Camn
2
+ 1 + C
(Lo:2 + -1 91+1
+ (1 + )et1)
Ilve 1" (x+)11
11 +C
pC
+ (1 de41
1 [((()))) - -ee))-u(( (1((++11)11
(58)
We now take det1 =
pC (utCoyy
Since s4t1 2 7+1 2 C2 2
pC C
in eq. 41 we have
det1 S 1. Then we get
R(a,, Ve, 12)
<(1 + Se41) | R(ae, Ve, 12
Pp41
PP41
(0)
22( + Coyy) (1lve
10 (xx)))
1 - (5(+1)1))))
2
1 + Cavv +C )
"llve (z=))1
+ 1(p + Cooo)
+
+ 1ss1)
#+ Coup
MC
1
40441
36

---

Published as a conference paper at ICLR 2025
2(x CCooo) (1+
(# + Conaleeas 1 1/ |as x2t1ll?
22 + Covy) - (xx))1 - 11e41 - -0((4411)1)
A(H + Cavel +8) ) I + Liss) 2 llve (ws))
1C
1
sP+1
4(p + Cgus) Looppt
1 - retill?
(59)
pCavv
where (a) multiplies both sides of eq. 558) by 2( + Cg.u) and uses det1 S 1; (b) uses pu+1 2
HCoun Take summation of eq. (59) and we have
T++1 2 Ci 2
p+C
V R(Kes Wes We. vz)1
Pk+1
km
V Re m2l
Pk41
k=
<2( + Coyy Uka-1 (Irkg +)]l 4(x+ + Conu )
Σ
pC
k=ka-1
4(u + Couul2
+8) Lig2Ctu + Legal
11 2 (ow)ll
+
MC
k=ks-1
Gp++
4(u+ +
)any)a
[x yk. )ll
$2( + Comu)luka-1 (1kkg-))ll -))1
PC
1441
Am
A(w + Couul? +8)
LigaCtyy
Iog.1
Σ
I1ya
(xx))
pC
1
k=ks-1
Gk++
22( + Covv)llka (1kkg-))l
1)l1
4(1 + )
Σ
IV yk, wll
pC
1
lmm
A(p Couu)²
+8)
LigaCty + Liga2
Σ
I|yk 4 (#x))1
PC
11
Be+1
(0) S 2(x + Cavu)llka-1 (1kk 1)]1
4(E + )onu)
[V yk. 12
MC
P++1
km
Coun)?
+8) Tng
+ +111)) ) 2²
V vk)
Vog(En, y² (1
Σ
MC
1
km
(6)
1l1 + Comn
[... We. v2
5 2(u + Cavy (opy))lkkg-> 0kg---11 x² (2rkg =)]1++
MC
a
kmkk
A(1 + Conu) +8)
Log20ts + L1.11
)²1 32a
MC
B241
k=kg
(0)(( + Covv)
|. -1 11, 11 1kg
V.
V.R(oks R( Mhs (0kk
112
4(H + Comn)
V yk, Ua)) a2r1Pet11
HC
k=
4(1 + Coyn }2
Lg + Lz.1 ) )21 Σ
IV Veg 11
+8)
MC9on
/
Be41
(8) A(k Cavv) 12
|V Ri V (Z1z-2), v² (x)g R. 1, Uhs 11 (x
37

---

Published as a conference paper at ICLR 2025
4(u + Cauu)
| ReRRs -ky Ukg 1kg- V. V. (Ibg-1))]1
1² 161 + Camu 12
ACpuv
024111+11
k=
4(1 + Couu
+
LaaeCty + L1,11 )²1 12
Σ
V vk)l
But1
h=
(e) 4(p + Cany)
(LgaCty + +Ts.1)
11ykg-1 - (x (1)1-1)11
122
161 + Camu)
(V 1, 111 Ukg -1)12+ + Affr + Cauu) 2
V ya, vz)ll?
1²
HCpyy
0
k=
444++ + Cavu
LLaaa + Ls.1 )²1
IV Veg( MIl
+ 8)
(60)
1
Be+1
k=kg-1
where (a) uses Assumption 1 (b) results from (z 0; (c) uses the strong convexity in (d) uses V.R(a,y (z), or (z)) 0; (e) follows from Lemmal
Lemma
Our next step is bounding 11y y¹ (rky 1)12 on the right hand side of eq. 60 in two cases. The
first case is Bkg I Cg. In this case, by using strong convexity of g and the definition of Bkg we can easily have
1
11 - y² (rrks
S
99 [kky
1. 1.
(rkss))))
1
1
B2
C2
V 1.
<
(61)
12a 122
The second case is 3kg > Cg. This indicates that k2 exists and K3 > k2 based on Lemma 4
By
2ubg.1 plugging A Bag-1 Lg.s)
into eq. (1). and noting Abg-1 $ 1, we have
11---1 44 < -118kg-2- " (whg 2)]? (u Lg,2) ||8" (1kg-2) -y" (1)3
{e + Lg,3 ) L || 115k3-2-100 - - 113-11?
|1 - nn (4kk-2))
(μ + Lg,
[V 22 Uki 2, Ukg 11
-1lmbg- nn (wng 2))l 2)1?
#وg11
0 12
(1r + T. ?
V fTrks 22 Ukk 22 Uks -
S1bakg 2 4n (2kg 2)1
0 184k -1
(μ + Lg
V 2, Ukg 2, Ukg 2)
< <1u0g-2 4² (xx 2)1
pLg.1990
(μ + 2
kg [V Ue, vIll
<118k2211 1² (# 1111
pLg.1400
1=
ch n +
(p + L3
| vx))
(62)
where (a) uses Lemma (b) uses eq. 61 by replacing ka by K2 since 3R, < Cp (see Lemma 4. By
combining eq. (61) and eq. 62 we obtain a general upper bound of [| y² 1)] as
C3 + (u + L Kg
V yk, 1z
1 y (1e3 < 112
(63)
of
k=
38

---

Published as a conference paper at ICLR 2025
where define k=m 4 0 for any and non-negative sequence {4x) )- By plugging eq. (63 into eq. 660 and using V. R( Ukg 11g I
n S Cg. we have
R( Uk 12)l
9h+1
Nia
4(1r
Log2t + tn.))
A(u+ Con Cg
+
111
u22
4(4 + Com 1u+ Lgallly T19220g
2 ls
V fZk, Uk: uxl1
+ Leg.1)
Σ
10th 1.g.1140
1
Ao No
4(1 Covo 22
[ yk: mk)l
p.C, Buv Cr
ak+1
lmmkg-
(Au Cavu
2
+8
+ I1s.1
E konks-
p.Cavy
1
122
8k+1
Then, the proof is complete.
Supported by Lemma 12 and Lemma
13
we derive upper bounds of 3g and 9r-
Lemma 14. Suppose the total iteration rounds of Algorithm 2 is T. Under Assumptions 7 Lemma exists within T iterations, we have
2 lo2 in
BBt1 SCp,
1 << kz
Be+1 s <(O+ +
(e (a+ Lg
(a+ I1g )
(n 12g Cgg
V (axx yks uz)11 ux)
kz.
122
1440
ab+1
kz
When such l2 does not exist, Be41 S C3 holds for any T.
Proof. According Lemma the proof can be split into the following three cases.
Case 1: 12 does not exist: In this case, based on Lemma we have 3r I Cg. and hence 34+1 S C3 for any / < T because 3r is non-decreasing with
Case 2: 222 exists and < k2s In this case, based on Lemma we have 8++1 S C3.
Case 3: h exists and 2 l2z Inspired by Ward al. (020) and using telescoping, we have
y xz. 31
Bc+1 =β,- +
se 1 + 3z
V v (Ft, 12
3 +
B.41
V Vyg(EKK 91)1
< <0b² +
Bx+1
km
(a)
(n + C3
+ (μ + L., 12,
(μ + 133
| Mk: 1x))11
Co
12
100
pbg.
a
k kz
(64)
where (a) uses lemma 12 Thus, the proof is complete.
Lemma 15. Under Assumptions least one of ko and ka in Lemma bound of y as
suppose the total iteration rounds of Algorithm 2 is T. If at exists, denote Kmin min ka). Then have the upper
Pt: SCip
< kimini
pp Saj log(t) + bi,
> Kmins
39

---

Published as a conference paper at ICLR 2025
where a1, bj defined as
Czan b+bb Cs. + =00)
bi == 40p log (1 (1+
0g = 600:
+ 4ao log(C () + 4ao + 2bn, (65)
Cgay â
in which we define constants
V2
J2C
ā
b:=
P ((4)) (4iu + CaNN )2
1
+ 8)
2 1²
+1
(1 L2
1
1p
4(u + Cavr Mi + L2
Lg + +1.s11
4(H + C L.
1 L.
HC
bo Cs + C. 1(1 + Cove JB3
Tggats + Lsa
1(p + Cov CG 41a
1
1
Alp Couu)* +88
2
C2
+ L.g.1)
Bo)
112
30
(Alu Caux)2
( T1s1) )
(1++
Lg
(u+ + 12
+ +8)
+1
(66)
y1Covv
122
112
p1.g.1900
When such l2 and ky do not exist, we have s S for all 1 S.
Proof. To begin with, we first show the following result as the first two lines of eq. 664) since Br and Tt are positive and increasing monotonically with f, we can easily have
S min ( min 18:75
= (6 + 1 - max{ 72+1 (6) + max
@ (B)+1 + 1241 (B) + (pž+1 - -g))
where (a) uses the definition 1pr max }t.. Similar eq. (64). have
2 5(B.4 (32) + (n241 72) = V Vgl v:)1 + | R(x,, Be. 12)1
which indicates that
9441 Sipt + VVg((r (0)1
R. Vt, u1)1
iPt1 + Pe Vyg(Er,9()1
Pi+1 PPt
|V R(ae, Yes w4)
Sipt +
+
Be41 + Br
Pt+l
Sip + Vog(sr,.
I R(xe, Vts 11)1
(67)
Bit1
Pc+1
Note that, to simplify the proof, we define En kkzm la 0 for any > n and non-negative sequence {4 According to the definitions 22 and K3 in Lemma 4 the proof can be split into the following four cases.
Case neither k2 nor K3 exists: for any E (0,7), we can easily have st = max 7h S max max(Cs, (C,,C,) C.p.
Case 2: lo exists but hig does not: by using the third line of eq. 644, for any E (0, T), we have
V Vyg(æk 2x)l1 + Ciyy
Pt+1 S B-1 + T-- s C'
(68)
Bk+1
k=
[vg(mmmmm)]1 0 for any t < 12- B
where we take 1k=k2
40

---

Published as a conference paper at ICLR 2025
Case 3: by exists but 22 does not: from the second line of eq. (67 for any E (0, we have
Vvg(Er Be)ll
VV Dc. 1z)l
Pe+1 50
+
Be+1
BB
PP++1
V Vug(Eks 8k)l2
RuRR Uks uk)ll
S4ka +
Bk+1 + BR
pk+11
J= km
k=
V Vug (2k yxl11
I 2k yke ull
5.kk + Ykk +
Br41 + Bx
pk++1
k=
k=
( BB+1 Yhis
V R( yk.
ux
+
1P++1
k=ka
R( ykr
53.+1 + C. +
Ph++1
k=ka
V ( 3k 112
ICg + CC +
(69)
g
where (a) uses the second line of eq. (67; and we take Σ Ek=ks (b) uses the first line of eq. (64). Case 4: both 222 and kg exist: from the third line of eq. 69 for any / E (0, we have
V Re for any ks;
Px+1
V V Uk)l
V R(ak Mk: 0x)
iP++1
Sike
+ Tkk +
Ba+1
pk+1
k=ka
k=
(a)
ky
V (oRk uk 211112
V War 11?
|| o. R(rk, Mes ux)ll
S 9kk
+ +Cr +
Bk+1
B6+1
Pk+1
k=
k=ks
|V ( 1oll
V. V(R(( Wk, 1x)
=Cp + Ci +
(70)
Bk+1
gk++1
k=ka
km
where (a) uses the third line of eq. (64 and take Dk-11 [V -0 when ly 2 ks.
Eisk [[)0 = 0 for any t < 12 and Σ A= (e.. 0 for any < kg. It is Bx11
7611
easy see that the upper bound of (p++1 in eq. 770p is the largest among all cases. Thus, in the remaining proof, we only explore the upper bound yo: in Case
To further explore the bound of iPs, need to some auxiliary results and bounds. So we split them into three parts as follows.
Part I: an auxiliary bound of Σ
||
of41
To further explore Case 4, we begin with common term Σt Ek=
| ( for any ko t.
Recall in Lemma 10 we have
V2 Pk+1 +
V2C Vk =: app+1 + bVT.
|e |1
<
μ
where a and refer to eq. 166
According to Lemma
since ag 2 1, for any integer / 0, we have
V yk. 11
[ Uk. 12
k=
f yks 2x)1 +03
< log
41

---

Published as a conference paper at ICLR 2025
(a)
S log
Cgy app+1 + Cgn bykk + + + +1
Ce,,ppp44 + Cg. bV + C₁2 -00)) 2) ) +
< <log
k=0
-2 log
C Mxp 0:p+11 + Car bv + Cs + 00 +1
k=U
$2
+ (1Cgs) aptt1 + Cg., but C₁ + au) +
=2log(t + 1) + log (Cor, 0ftt1 + Cg.n bVt + Cf= + an) +
Stlog(t + 2 log gn 04r41 g,y + Cf + an) oo)vt +1
<3 [++++++1 2 log( C Szy 0pt41 C b + Cf + an) + 1, (71)
where (a) follows from Remark 3 and Lemma
Therefore, we obtain the upper bound of W for any kn S in eq. (71 Part is completed.
10
Ei=to
4441
Part II: more general bound of Σ
V V
Ax+1
In Lemma 12 show the bound of Σ
Ek=ke
Vegloe.eel when kS exists. In Part II, we further Bet1
provide a rough bound of Σx R
V.g(av..))l
for any potential s T. Firstly, if 2 k2, it is easy
Be+1
to have
IV Vog(En wk)l
3k+1
Be+1
k=
secondly, if &e < k2. we have
|V Vo 11)1
V g yx)ll
V Vy yk)l1
Bk+1
8k+1
Bk+1
k=
k=
12-1
Vg )1?
V (2gg yk)l Bx41
k=
30
82
3
V w 112
80
3R+1
k=kg
C3
-
| (IK 11211
30
Ba+1
k=bz
C
V VI v1l)
B0 +
3
Bk41
k=
Combining these two situations, since Cg 2 So,
for any & < t. we have
Vyg((k, 1x1)1
C2
Vyg(TR. U1)1
<
Bu
B+41
B0
Ba+1
k=ka
C
(n + Lg IC3
(μ + 13
9o
Bu
12
1P0
(n + L2
f Uk. 21
(72)
pLgg11
0f+19P441
42

---

Published as a conference paper at ICLR 2025
where (a) uses Lemma 12 Thus, Part II is completed.
Part III: the bound of O in Case 4.
Here, we explore the upper bound of fo: in Case 4. Recalling eq. 70). we have
Σ
II Vg 21?
Dk, (k, ux)1 = Cg + + = =Cp-
Pit1 SCp + Cy +
Bu+1
Pk+1
K=
for S Kmin == min ka). For 1 > kimin we have
Vugl 2ill
Roaa ua, villl
iP+1 SC3 + Cr +
Ba41
pk++1
k=R2
km
(a)
Vug(an well
2 CR + Cy +
Bann
A=
4(1 Co
(Lg.aCt + t.s..)
4(u + Coun
11a
1
11a
4(1 + Mow + Lonidly
kg
faa uk, enll 2241
+ Lis.
Σ
1
k=k2
4(u + Covy) 12
MC Or
ab44
kmmg-11
A(μ + Covu)
Lo + I1s.1)
2
V Vog( 2
+8)
HCOov
112
Ba+1
k=ks-
(0)
4(1 Cava)²
I Vog(Ee )11
+ +8)
+ +1p,1)
Σ
pCCov
112
BE+1
kmn
1(1 C3
Tyg20s, + +
1(1 Copy)
Cp + CC
+
1et Alu Cany
1
112
+ +8)
(L9x + L.s.))
)
C3
Bb)
PC
12
30
4(# + Mowy b
V fa 8k. en )l
+1g.11
L9,000
1(p + Oggy) 112
MC Or
ax+1
km 1
4(p + Couu)"
+ +8)
Lg + 1 21
(u + 2 plgga2
[a yk ox) 12411
+1
PC
1
1s2
4(p MN Ligaadly [Tig20s Lg
(Vf(F,,
a
k
1(p + Comy) 122
+
Σ
MC Cr
ab41
k=
4(H + Cavn )3
LarOse
4(p + Crvy
Cp + +
+ +
+
11
1a
Mu Coun +8) (
+ +bsa)
)
C/2
30)
PConu
112
30
A(u + Covu +88 (L192 L5d)
1
+ Lg,1
(u + 1 1100
+1
pC
1
A(p+ Conn
+))
+ 8)
+ L
2
+
(μ + 23
43

---

Published as a conference paper at ICLR 2025
1(1 Cavy Lig
[gg2Osy +br.))
V (ak, Mks v=)l
16 19900000
ac+1
4(1 + Coyy
p0 70
k=
4(1 + 10'
TygaOta + +
4(1 Couy
Cp + C +
+
1e
1²
A(w Coyu) +8)
(
121
C3
+ (Is..))
(80)
pCssn
1²
30
Mfs Mus Covu
+ Lng L1.))
12
+1]
(n (w++
Lg,a
(1 + 1.
4²
122
(4)
:00
Σ
+ to
abt1
kmmin (k2-1183-11)
1V yu, wwll
<ag
au bu
ab41
A mina (12.)k))
(e)
$.00
3log(t 1) 22og (pe.2
Gonp Oso
00
2log(C ). +1 + 00 bu.
(73)
Cozy a
where (a) uses Lemma 13 (b) uses the first line in eq.
72
by replacing ht with kg 1; (c)
results from eq. p52p; (d) refers eq. (66); (e) uses eq. (
Since min (k2, kig) S T, have
(P++ 2 min(Ca C2 2 max (axx)44j, 1}, which indicate that
(i) if Sag S 1, we have
4a log(((+)) log(pp+11)
Pit1
I Pt+1i
2
2
(ii) if Sag 1, we have
Pt+1 44g log(sf++1) = 94+1 - 8ay log( (P+1) 2 Sao SaolVPut ( log( (P(+1)) 2 0.
Combining (i) and (ii), we have 4ao log((((1) 90+1-
Then we obtain
3 llg(( - 1) log 9441 + Car, b C, Cs, + au
1 Sag
+ log(Corr a) ( + an bn
Coupa
1+ Cary b + Cs5 + +a0
Sag
3 llog(t - 1) 20ggg(((4))) 2log
+ +2log(Co.n a) + + ao + bo
Cony
+ log(Co.. a) a)+1 ao + bo. Cozy b Cfa + +000
2 9941 + 3log(t +)+
1+
Cany a
which indicates that
Pt+1 I6ap log(t + 1) + 4ap log (1 (1 Cony b C₁ + +00)
+ 40g Manlog(C, log(C a) + 4ag + 2bp
C a
Jay
01 log(t + 1) + b1.
(74)
where (a) refers to eq. 665 Thus, Part IIII is completed and the proof of this lemma is completed.
Lemma 16. Under Assumptions 7 2 of logarithmic functions as
for any integer ko E (0,1), we have the upper bounds in terms
V f Me: 12)ll
llgg( + 1) + C2,
ak+1
IV
Vgg(I 1w)il
S a2 log(t 1) b2.
9x41
44

---

Published as a conference paper at ICLR 2025
R( yks uxlll
I 0g log(t + 1) + b3.
pk+1
kg
where referring to eq. (65)
eq. 66
C2. 02 b2, ag by are defined as
:=2 log (Cazy aai + Caey abı
Cony b Csa as)
+
5(p L2
b2 (1 + L2
C
(Hr + Lg.i
(1 Lg
Bo
+
30
112
20( + Cam Liga)
Tig,O0s + 11111
2
20( Cavy)
)
ag =
1
HO Or
Min+Cow! + +8)
Tig20tu + 1.111)
22
PC
1
4².
C
4(u + Coyn (
4/u Coon
L5,1) 2
70
To
16t
1
12
A(u Camu)(u+ Do (Tagalt
M( Couy) ) I
+ L$,)
11g100000
1
MC Cr
C2
A(w= + Couu)
( + +8)
+ 2 4²
(75)
pCass
Proof. Based on the logarithmic-functin form bound in Lemma 15 logarithmie-funeti form bounds the components in Lemma IT the following 3 parts.
we can further have the
Part I: the bound of Σ
| ((( in terms of logarithmic function. 0241
Firstly, bound Σ Ek= eq.
|/ fee for arbitrary Ko < Back to eq. (11), by plugging in o2
74
we have
[V yk. 22
a
<3 log(t 1) 2 log(C 0ptt1 Cg., b+ b Cr + +w)) +
$ log(( + 1) + 2 log (Co,, σaj log(t + Cor, ābj + C + C₁2 + ao) +
<3 + +1 + 2 log (Cg,, (t + 1) + Bay ab + +C b C₁ + 0o) +1
<3 <og(t 1) + 2 log ((C) Uxn daj + C abı + Mxn b+ C₁. + ap) + 1)) +
<5 log(t (t 1) 2 log (C,a,, daj + C Can ābi C.., b + C₁ oo) +1
( 5 log(t + 1) + C2.
(76)
where (a) results from eq.
774: (b) refers to eq.
75
Part H: the bound of Σ
V V19(#n.9))1 in terms of logarithmic function.
De+1
Secondly, we bound Ei
We split this part into two cases using Lemma
Be+1
Case 1: If Br+1 & Cg., we have
V v&))12
Eisho IV Vog 11
82
B2
C3
18
C2
<
30 <
bz.
Bk41
30
30
Bo
Bn
Rem Roo
Case 2: If 33-1 > Cg. we have 2s 5 1, where ho refers to Lemma which indicates
Then we can use eq.
72
V (o 1=
8x41
45

---

Published as a conference paper at ICLR 2025
C
(1 + Lg
(n + L2g
(1 Lg
| Ve.
30 +
112
11
p
ak+1
5(x
L2
(1 Lg
L2
C2
(
Lg.a)
(u +
L2
log(t +
30
plgg110s
80
1²
1110
5 E. log(t + +1) bz.
(77)
where the second inequality uses (6). and (a) refers to eq.
75
Since the upper bound of Case 2 is
larger, we take eq. (77) as our final result.
Part III: the bound of) Σ V we.elll in terms of logarithmic function.
Ph11
Last, we bound Σi=ko V.
We split this part into two cases using Lemma
Pk+1
Case 1: 7+41 I Cy, we have
IV. yke, un)l
Eisko
V R(Ek, yk. uk)l
C2
7o
C²
7o
S
by.
Pk+1
Pu
Y
Case 2: If m++1 Cy, we have k3 S t, where K3 refers to Lemma
| V. Mes 22)ll
pk+1
k=
V R,NK Uh, uk) 112
V N.R RRRa ykr Uk))k)) ux)l
pkt1
PP++1
k=kb
k=ka
(6) C2
4(1 + Cgnn
CB
Ty + +Ls..)
2
4(p + Conn
2
7o +
+
70
1r2
112
4(u + Conn) Lgn)liy
(Ig,200 + L1,11
ha-2
VV Dle 2x)
+
Lg.100
H
a
km Rog
4(1 + Cynn 2
[ yk, Uk)1
pC 9ou Cr
ab+1
km
A(p + Comn
)2
19 + +1111
21
VV Votre,
+
+8)
Σ
MC
112
Bk+1
h=
(e)
C2
A(p + CBNN ( (Lg2 + t1..1)
4(p + 0z
70 +
+
70
H 4(2 + Mu 1.
42
(1y220 + lzf.1)
4(p Comy)
(5 (olgg (lo((+++) + 11+ 02)
119,101190
110gus Cr
4(2 + Coou) +
(
(HanC + +1(g,)
)² 21a
(az (oglog((+1) +b2)
MC9gm
(d) aa log(t + 1) b3:
(78)
where (a) allows Σks kg V... = when An > K3: (b) uses C, 2 To and Lemma 13 (c)
kk ky
2t+1
follows from eq. (66 and eq. (77); (d) refers eq. (75). Since the upper bound of Case 2 is larger,
we take eq. 78 as our final result.
Thus, the proof is complete.
Next, we show the upper bound of oz.
46

---

Published as a conference paper at ICLR 2025
Lemma 17 (The upper bound of at). Under Assumptions 7 2 3 suppose the number of total iteration rounds in Algorithm T. If there exists 1 I T described in Lemma 4 we have
at SCa:
t S ki;
ar SC. + log()) by + 4(((20)) inf ((x)) -in((()))))+ 9r,
2 Kn
where da, by defined as
20
2
Ty + +1,,1)
4L2az
a4 12Ca.
1+
112
1r²Ca
44 1.
2L
1
2
Lgg0ss
+ [
4L'b3
+
2L
C2
(79)
112
48
00
and the upper bound of Pp: == max (3r, 7 refers to Lemmal 15 have 04 S for any S T.
When such does not exist, we
Proof. According Lemma
4 the proof can be split into the following three cases.
Case 1: if oTr S Ca. for any & < T, we have the upper bound of 044+1 as 0+++1 S Ca.
Case 2: if or Ca, there exists k; S T described in Lemma Then we have the upper bound of 0+++1 as 0:411 < C. for any < k1.
Case 3: in the remaining proof, we only consider and explore the case k SIS when or > Ca.
From Lemma 11 for & 2 K1, we have
((x++1) (d(T))
[+(xx)11
IV V yk. un)l
200+1
4ax+ Pk+1
2
L9 + 4/1)²
V (vg(ERk
I V VuR(ak Mke vk)ll
+
1
2p
112
1
112
1441
which indicates that
| [ Me, 1xll
< 4(0(Tk)) - +((x++1))
01+11ft+1
2
2
T9220te + Lsp11
Vug(zk, 11
4I²
V R(RK yk. uxl1 Uk.Uk)1 0k+11Pk+1
+ n2
1
122
0x+19R+11
112
By taking summation, we have
ff yk. ux)l
034114411
21.2
2 Ig
27
1
V
<4($(xk)) - inf (()) +
1
Σ
Cr
1²2
Pk-1
km
Ai.
R(T Mk: 112
(80)
C.C. k=ki
gk+1
For (Ir,),, by telescoping eq.
(3 in Lemma
we
L
V (z We, 12
((T,,) (20)
+
04418
2
k=0
2
2
L Lz,1)
V Veg(ze. vi)l
+
1+
2n
112
p
0411
1,2
k
V
R( yr, w2)11
+
(81)
2
01419441
k=0
47

---

Published as a conference paper at ICLR 2025
By plugging eq. (81) into eq. (80) have
[T Me. rx)ll
ak+1Pk+1
km
20
(
2
2
1
V
<1((()))
inf (c)) +
1
lzg.1
C=
112
pk+1
k=0
4
V R(ak: y/o 12)l1
21. C₂
+
Ca k=
9h+1
90
2
ag
<4(0(z0)
inf (xx)) + C2
2T.²
1+
2
Tgg25s
+151)
2
Σ
V
112
Bk+1
k=0
4I2
V Vul(ak y/k, v2)l12
2L
C
4 p²20a
Ph+11
P6 ag
k=
(a)
((0()))
inf (xx) + C²
2L2
1+
2
Tng.2 L1,1) )}
(12
(a2 log(t + 1) + b2)
422
4L"
2L$
C
(ag log(l + 1) + bn)
+
1.
40
=.0 log(t + 1) b4 4 (x)) inf (xx))
(82)
where (a) plugs in eq. 77 and eq. 78)) (b) refers eq. 79)
This immediately implies
[V(kx, Mh, 12
< aas log(t + + by + 4((( - inf ((x))) 90+1-
(83)
ak+1
Similarly, we can have the upper bound of a++1
f yk. uk)
a++1 Saa,
ax+1
k=
<Ca + log(t + 1) + by + 4((((o)) inf ((x))) pit1. ((2))))[tt.
(84)
Then the upper bound of 01+1 is proved.
F.4 PROOF OF THEOREM 2
Here we still assume the total iteration rounds of Algorithm 2 is T, According to Lemma 4 the proof be split into the following two cases.
Case 1: If or < Ca. then by Lemma and Lemma 17 (x:))))
we have
L
<2( - (00+1)) + aft
A f Vi, v))l
ac419t+1
2 n
2 12
I + Ls.1)
Vyg(Ee, yell ye)l
V.R(2, Dt, v))l
+
1
1
01419
112
0++14
By taking the average, we have
[V((2))
La
7
(b())) - (x(T))
+
Σ
|| A (2t. vz)ll
0441
T
t=
2
1g + LL.1)
27
V Vog vell
+
1
1
112
112
T
01+19Ptt
48

---

Published as a conference paper at ICLR 2025
2L
T-1
V T,R(aa Øt yc. 11
+
1
T
0+ 1p++1
1=0
2
((xr)) + C2
((o))
T
Tagio
+
1.2
1
2
L + L5A1)
Σ
Vo But1
1paTT
112
21.
V R. yh, 1)l
+
91+1
Lg
(20) - inf (x)) + Totro
T
1
2
Ls + 1.s.1 ) (a2 (a2 log(T) + b2)
+
1
112
21.²
(a3 (oglog(T) + bz)
22o0T
2T a4 (og(g(T) by + ((((zo)) - inf in))())))
(85)
where (a) uses Lemma 16 with ku
Case 2: If or > Ca. by Lemma 4 there exists l S To such that ag, S Ca. abi+1 > Ca.
Then for t kj when or Ca. from Lemma
we have
Lx
[((()))) +
Vr, 22)1
ar419141
af+182+1
1
Lgg2Cre + T.sa)
27
V Vog(2s, will
2L V. Ve, 01)l
+
1
+
+ 1²2
112
0++19
04+19t+1
For 2 ki when or >> Ca. from Lemma 11 have (2(22)1
<2(4(x)) (((+11)
04419441
2
2 42
L + Ly.) 2] | Vug(Es (.))(
2
V(,( yrs 112
1
1+
n
1941
112
01411pt41
By taking the average, we can merget
< k1 and t 2 k1 as
k
[++(2))1
T-1
(
+ T t=k1
T
04119141
T 1=0 a1+1P
a++1i141
k -1
T.g
1
$ T
(((kk))
+
fx Ve. v2 11
T
1=u
2
Lg + T.fa)
2
1
V (z 2
+
1
112
112
11
T
1=0
2[2
k-
V. Rea, Vi, 12l
+
112
ac+19t+11
1=0
+
(D(Ik,)
- -((r))
T
2
27
1
V V,g 11
+
1+
112
1
1441
49

---

Published as a conference paper at ICLR 2025
20 T 112
Vo Mr, 2)ll
+
T
Ox+ 1 Pr+1
t=
2
Li +
ki
5
(8(z0)
inf (xx)
V fa Mr, wt)1
x
agpi T
t=
1
2
Lu + +T,g,1)
27
1
v (zt, w1
+
1+
12
122
0+14
2L
V R(x,, ye, 11
112
T
02++1
s 2 (0(zn) - inf (xx)
2
Lo
R1 (ar, Mr, 21)l
+
agr0
1
2
Lgg2Ose + L1,11
Vig ye )1
+
1+
uRooT
1122
Pc-1
2D²
R. ye, 26)))
+ 22a0T
9i+1
1=0
(a) 2
C2C2
(2ra))
inf (1:) +
T
Taj
1
2
T.g2205 + L121) )] (a2 log(T) + b2)
+
1+
u2aoT
112 H
2L
+ 4 T
(1g (oglog(T) + bzz)
04 (og( + b4 + 4 4(0(2z) - inf (x)))
(86)
27
where (a) uses Lemma 16 by plugging in kn- = 0.
Note that Case and Case indicate the same result. Thus, we have
1
<
aas log))(() + b, + 4(0(z)) inf o(z))) oTPT
2T
(a) 1
2T 04 log(()) 64 + 4(((2)) inf pxx)) ptt
+ +Ca (og + by + ((0(z)) inf (x))) (o)
(8) 1
$ 2T [ (oggo bu + ( inf ((x))) (0r log(T) + b,)²
+ C (ar + b, ( inf (z)) (a1 log(T) + b1)
=0 log (T))
T
where (a) follows from Lemma 17 (b) results from Lemma 15 Thus, the proof is finished.
F.5 COMPLEXITY ANALYSIS OF ALGORITHM 2 (PROOF OF COROLLARY
Recall in Theorem 2 we know that there exist constant M such that
T-1
M log't (T)
vo(2=)1
<
T
T
1=
50

---

Published as a conference paper at ICLR 2025
When set the iteration number T M. log log'(24 (A)) and assume the constant N = 124, have log' (T) (T)
M log" ( MN log' (
MN log"( M
[log(V) + log( () + (log M ))
N log' (#)
M
(n [og((N + 2 2log( dI
N log( M.)
where (a) follows from the inequality log(log( M 1) - / log( M 5 for sufficiently small e; (b) holds because log 2 log( Ad) I N' log( Au) for N = 12a and is sufficiently small. Thus, to MN log = O log' (E)). and the gradient
achieve c-accurate stationary point, we require
complexity is given by Ge(e) = 22(T) = O log" log((2))
51


Reviews:
[{"review_id": "uH067qQDGn", "reviewer": "Reviewer_uEX3", "summary": "This paper has proposed two tuning-free algorithms for stochastic bilevel optimization, D-TFBO and S-TFBO, which eliminates the need for stepsize tuning that depends on problem-specific parameters. D-TFBO follows a double-loop structure, while S-TFBO utilizes a fully single-loop approach with a joint design of adaptive stepsizes. Convergence rates for both methods are established, and numerical results on data hyper-cleaning, regularization selection, and coreset selection validate the effectiveness of the proposed algorithms.", "questions": "This paper proposes two versions of tuning-free bilevel algorithms. It appears that the single-loop algorithm offers better gradient complexity, while the double-loop algorithm demonstrates superior empirical performance. Could the authors comment on the reasons for this discrepancy—such as whether it stems from a less tight convergence rate for the double-loop method or something else? Additionally, guidance on when to choose the double-loop versus single-loop version would be helpful for practioner.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Parameter tuning is challenging in bilevel optimization, as bilevel problems typically involve more hyperparameters than single-level learning. This paper presents two versions of tuning-free methods with both theoretical guarantees and experimental validation, making it a valuable contribution to the bilevel optimization community. \n\nTheoretical guarantees for the proposed methods are solid, and the numerical performance demonstrates a clear advantage, showcasing the effectiveness of these approaches.", "weaknesses": "This paper addresses only deterministic bilevel optimization, leaving it unclear whether the proposed technique is robust in stochastic settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e7Ra7q72f5", "reviewer": "Reviewer_wFAr", "summary": "The paper introduces tuning-free bilevel optimization algorithms to eliminate the need for prior knowledge of problem-specific parameters. Theoretical convergence is derived for methods and experiments are provided.", "questions": "1. How would the methods extend to more general bilevel problems?\n2. Could you update citations from arXiv preprints to published versions where available?\n3. How does the performance of these tuning-free methods compare directly to well-tuned bilevel optimization algorithms in terms of convergence rate?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper provides a detailed convergence analysis for the algorithms.", "weaknesses": "While I understand the importance of addressing tuning-free bilevel optimization, the main technical novelty of this work is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "flOJGkgnye", "reviewer": "Reviewer_ZFyM", "summary": "In this paper, the authors introduce two tuning-free algorithms, D-TFBO and S-TFBO to solve bilevel problems. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the \"inverse of cumulative gradient norms'' strategy. S-TFBO features a simpler fully singleloop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. The authors demonstrate that D-TFBO and S-TFBO respectively require $\\mathcal{O}(1/\\epsilon)$ and $\\mathcal{O}(1/\\epsilon \\log^4 (1/\\epsilon))$ iterations to reach an $\\epsilon$-accurate stationary point. The methods are the first to eliminate the need for stepsize tuning while achieving theoretical guarantees.", "questions": "1. I do not understand the proposed observations in Remarks 1 and 2. The authors could discuss these observations in greater depth, such as by providing more detailed explanations in the main theorems and experiments.\n\n2. I would like to know whether the proposed algorithm can work without the prior knowledge of the total number of iterations $T$ (cf. Weakness 1).\n\n3. I would like to observe the progression of the loss function over time in the experimental results.\n\n4. For other questions, please see the weaknesses above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and is easy to read.\n\n2. This paper introduce two tuning-free algorithms, D-TFBO and S-TFBO to solve bilevel problems, which eliminate the need for stepsize tuning while achieving theoretical guarantees.\n\n3. The complexity bounds of the proposed method (nearly) match their well-tuned counterparts using the information of problem parameters.", "weaknesses": "1. My primary concern is the update mode of the proposed algorithms. Many tuning-free algorithms do not require prior knowledge of the total number of iterations $T$ (e.g., [1]). However, this is not a significant drawback for me, as addressing bilevel problems with tuning-free algorithms in this context seems to be new.\n\n2. The literature review should comprehensively compare the complexity results and the corresponding problem settings with other methods in a table.\n\n[1] Marumo, Naoki, and Akiko Takeda. \"Parameter-free accelerated gradient descent for nonconvex minimization.\" SIAM Journal on Optimization 34.2 (2024): 2093-2120.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nxPIWPbMRX", "reviewer": "Reviewer_fFYc", "summary": "This paper studies parameter-free algorithms for solving BLO, where the lower level problem is strongly convex and the upper level problem can be nonconvex. The authors propose two tuning-free algorithms that achieve the nearly same rate of the state of the art without knowing the parameter. The stationarity measure is the standard hyper gradient norm. Numerical experiments are conducted to show the effectiveness of the proposed methods.", "questions": "Non.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper combines the parameter free methodology with BLO, which is a good direction to explore.\n\n2.The convergence rates achieved by proposed methods are nearly optimal.", "weaknesses": "1. Under the strong convexity of the lower level problem, the BLO is similar to single level problems. This is due to the fact that there is a unique solution $y^*(x)$ for the lower-level problem given an arbitrary upper-level variable $x$, and then the BLO is reduced to the single level problem $\\min_{x}\\phi(x)=f(x,y^*(x))$. Even further, the gradient of $\\phi$ can be computed, as presented in Sec. 3.1 of this paper. Given this, the authors should point out the novelty of the techniques used in this paper compared with single-level parameter-free methods.\n\n2. Second-order information is needed for each iteration, which is computationally expensive. The authors may discuss how to approximate the used hessian matrix or a furture direction to develop methods that are both tuning-free and hessian-free.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)