Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
Authors: Xiaochuan Gong
Jie Hao
Mingrui Liu
Venue: NeurIPS 2025 poster ()
Keywords: hierarchical optimization
adaptive algorithms
stochastic optimization
Primary area: optimization

Abstract: Hierarchical optimization refers to problems with interdependent decision variables and objectives, such as minimax and bilevel formulations. While various algorithms have been proposed, existing methods and analyses lack adaptivity in stochastic optimization settings: they cannot achieve optimal convergence rates across a wide spectrum of gradient noise levels without prior knowledge of the noise magnitude. In this paper, we propose novel adaptive algorithms for two important classes of stochastic hierarchical optimization problems: nonconvex-strongly-concave minimax optimization and nonconvex-strongly-convex bilevel optimization. Our algorithms achieve sharp convergence rates of $\widetilde{O}(1/\sqrt{T} + \sqrt{\bar{\sigma}}/T^{1/4})$ in $T$ iterations for the gradient norm, where $\bar{\sigma}$ is an upper bound on the stochastic gradient noise. Notably, these rates are obtained without prior knowledge of the noise level, thereby enabling automatic adaptivity in both low and high-noise regimes. To our knowledge, this work provides the first adaptive and sharp convergence guarantees for stochastic hierarchical optimization. Our algorithm design combines the momentum normalization technique with novel adaptive parameter choices. Extensive experiments on synthetic and deep learning tasks demonstrate the effectiveness of our proposed algorithms.

Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
Xiaochuan Gong George Mason University xgong20gmu. edu
Jie Hao George Mason University jhao60gmu. edu
Mingrui Liu George Mason University mingruil@gmu. edu
Abstract
Hierarchical optimization refers to problems with interdependent decision variables and objectives, such as minimax and bilevel formulations. While various algorithms have been proposed, existing methods and analyses lack adaptivity in stochastic optimization settings: they cannot achieve optimal convergence rates across wide spectrum of gradient noise levels without prior knowledge of the noise magnitude. In this paper, propose novel adaptive algorithms for two important classes stochastic hierarchical optimization problems: bonconvex-stronglyy-oom minimax optimization and nonconvex-strongly conove bilevel optimization. Our algorithms achieve sharp convergence rates of Õ(1/VT + //4 in T itera- tions for the gradient norm, where ō is an upper bound on the stochastic gradient noise. Notably, these rates are obtained without prior knowledge of the noise level, thereby enabling automatic adaptivity in both low and high-noise regimes. To our knowledge, this work provides the first adaptive and sharp convergence guarantees for stochastic hierarchical optimization. Our algorithm design combines the mo- mentum normalization technique with novel adaptive parameter choices. Extensive experiments on synthetic and deep learning tasks demonstrate the effectiveness of our proposed algorithms.
Introduction
Hierarchical optimization refers class of optimizztiinn problems characterized by nested structures in their objectives or constraints, such minimax optimization [6] 64 50 and bilevel optimiza- tion (5] [3]. These problems have wide applications machine learning. For example, minimax optimization is the foundation for adversarial learning [27] and AUC maximization [75] [3], while
bilevel optimization central meta-learning
[9 and hyperparameter optimization 20 18 In
this paper, we are interested in solving two classes of stochastic hierarchical optimization problems. The first class is the nonconvex-strowe
minimax problem !
min max [(x v) == Rg_D [F y E)), RER yERdy
where D is an unknown distribution where one can sample from, and f(x, v) is nonconvex in æ and strongly concave in y. The second class the noncomeex-strongly-comm
bilevel problem in (
min (xx) == f(x, (x)). s.t., y² (x) = =ag min g( v). mgRdz
Rdy
where D,, and D, are unknown distributions where one can sample from, f(z v) Eg-D,, [F(x, E)] nonconvex in x and g(x,y) = Bę=D, [G(r,, y: is strongly convex in y.
We call the upper-level variable and the lower-level variable. Note that the bilevel problem in
degenerates to the minimax problem
when g = -f and then ((x) = max yER*> f(x y).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

There are various algorithms designed for the minimax problem and the bilevel problem in
29 28 However, existing algorithms and analyses lack adaptivity to various levels of stochastic gradient noise: their convergence rates remain suboptimal in various noise regimes unless the noise level is known priori (see Appendix [or discussion and details). In contrast, such an adaptivity guarantee is achieved in single-level stochastic
the stochastic setting 64 50 47 22 40 33
45
optimization [48 67 42 17 [66 2] by AdaGrad-typ algorithms [60] 14]. This naturally motivates
us to study the following question:
How can we design adaptive gradient algorithms for stochastic hierarchical optimization problems ① and (2) that achieve convergence rates automatically adapting to the level of stochastic gradient noise, without requiring prior knowledge of this noise?
Designing such algorithms in stochastic hierarchical optimization presents significant challenges. In particular, applying AdaGrad-type algorithms (e.g., AdaGrad-Norm (67] simultaneously the upper- and lower-level variables will introduce complicated randomness dependency issues due to AdaGrad stepsizes. These dependencies are difficult to handle analytically without imposing strong assumptions such as bounded stochastic gradients or bounded function values [47]. However, such assumptions undermine the algorithm's 's ability to adapt effectively in various noise regimes.
In this paper, we address these challenges by developing novel adaptive algorithms for solving [ and (2), respectively. Unlike standard AdaGrad-type algorithms [67], the key innovation of our approach lies in combining the momentum normalization technique [T] with novel adaptive parameter choices. A distinetive feature of our method is the dynamic adjustment of the momentum parameter based on online estimates of the stochastic gradient variance. This adaptive momentum directly informs our stepsize scheme, enabling improved convergence across both high- and low-noise regimes without requiring prior knowledge of the noise level. The primary challenge in analyzing the convergence of our proposed algorithms is simultancously controlling the upper-level and lower-level errors under time-varying parameters, including adaptive momentum and stepsizes, while maintaining adaptivity in the presence of unknown stochastic noise. Our main contributions are summarized as follows.
We propose two new adaptive algorithms, namely Ada-Minimax and Ada-BiO, for solv- ing the nonconvex-strong- -ttrooo-coocnneee minimax optimization problem (T) and the nonconvex- strongly-convex bilevel optimization problem (2) respectively. Both algorithms leverage the momentum normalization technique and adaptively set the momentum parameter, along with carefully designed adaptive stepsizes for both upper- and lower-level variables. To our knowledge, adaptive algorithms of this type that distincts from standard AdaGrad approaches are novel within both stochastic single-level and hierarchical optimization problems.
We obtain high probability convergence rate of Õ(1/VT Vo/T!/t) in T iterations for the gradient norm (here Ö(.) compresses poly-logarithmic factors and the failure probability 5 E (0, 1)), where ō denotes an upper-bound on the stochastic gradient noise. Notably, our algorithms automatically adapt to both high- and low-noise regimes without requiring prior knowledge of the noise levels.
We empirically validate our theoretical results through a synthetic experiment and various deep learning tasks, including deep AUC maximization and hyperparameter optimization. Our results demonstrate that our proposed algorithms consistently outperform existing adaptive gradient methods as well as well-tuned non-adaptive baselines.
2
Related Work
Minimax Optimization. Early works on minimax optimization focused on convex- concave set-
tings and developed first-order algorithms with convergence guarantees [61] 63 4]
62). The minimax optimization was pioneered by (64.
study of first-order algorithms for nonconvex-conent
Subsequent works improved convergence rates under various assumptions [53 68 59,, proposed single-loop algorithms [50] 29 71 and relaxed the concavity requirement on the maximization vari- able 669 |1 (5222222222 4 Some recent efforts have incorporated adaptive gradient methods into minimax 70. However, none of these approaches provide convergence guarantees that adapt across different levels of stochastic gradient noise in
optimization 51
47
38
settings. a type of hierarchical optimization problem where optimization task (i.c., upper-level problem) is constrained by another optimization task
Bilevel Optimization. Bilevel optimization
K

---

(i.e., lower-level problem). The first nonasymptotic convergence guarantees for bilevel optimization problems were established by [22), followed by a growing body of work that established improved
complexity bounds under various assumptions [4 40
g 12
28 72
33
25
24
12
36
45
65
57
58]. More recently, a few studies have explored bilevel optimization algorithms with
adaptive step sizes [15
I 73 37.. However, these methods are either restricted to the deterministic
setting N 73 or fail to adapt to a broad range of stochastic gradient noise levels [15 37 26
in
Sunconvex--tronnlyy-ee
bilevel optimization problems.
refer to a class of first-order algorithms where the stepsizes are computed based on the historical stochastic gradients, and they are empirically effective for training deep neural networks. The theoretical guarantees of adaptive gradient algorithmss for single-level optimization problems are extensively studied and
Adaptive Gradient Algorithms. Adaptive gradient algorithms 60
14 66
well-understood in the literature
48
56
46
16] Extensions of adaptive methods
to minimax [51 47 38 70] and bilevel optimization
37
26
I
73 have also been proposed.
However, none of these works establish theoretical guarantees for adaptivity to unknown stochastic minimax nonconvex--tronnily-conwe bilevel optimization problems, as achieved by our proposed algorithms in this work.
gradient noise levels in nonconvex-strongly
3 Preliminaries
Notations. Denote || || as the Euclidean norm. We use the standard O(-). +(), notations, with ( ((.) hiding logarithmic factors. Throughout, with slight abuse of notation,
use F, to denote the filtration (i.e., o-algebra) generated by stochastic queries up to iteration I,
and E-|] B[- Fi] to denote the conditional expectation with respect Fr,, for all algorithms. A function h is said to be L-smooth if V/V)(>) Vh(y)ll I L|| yll for all 2; y E Rd. We
additionally assume that all objective functions are bounded from below, i.e,, f == inf, f(x) > 000
(Section 5.1 and &- inf, (xx) -o (Sections 3.1 and 3.2).
Settings. Let y" = arg max yER" [(xr,) y) for ① and y" y²()) = arg min yER g(x, y) for (2
Define the objective funcctinn (xx) = f(z, (x)) for both minimax and bilevel optimization. Recall from Section I that the bilevel problem reduces to the minimax problem I when g = -f. The goal of this paper is to minimize +.
3.1 Assumptions for Nonconvex-Strongyy-Coo Coneavee Minimax Optimization
Assumption 3.1. The objective function f is L-smooth in (z, y) and f(x, -) is p-strongly concave.
Assumption 3.2. (i) The gradient oracle unbiased, i.e., E[V (xx, | xr v) = V v). (ii) With probability one, the following holds: a S || Fxx vi E) - V=I v) o. with 0
and VV FIz, y E) (x, y) S Gg-
Remark: Assumptions 3.1 and [ i.2 are standard in the minimax optimization literature 50 74, 29
The main extra assumption we make is Assumption (.): the stochastic gradient noise is lower bounded and -ounded (with probability one), which may appear somewhat unusual. However, this assumption holds naturally in the additive noise setting used in certain nonconvex optimization scenarios, such escaping saddle points with isotropic noise [21], where the stochastic gradient noise is sampled uniformly from the unit sphere and therefore has a nonzero magnitude with probability one. We also empirically validate this assumption, as shown in Appendix L In the noiseless case, we have o₂ = az = 0, and og- = O.
3.2 Assumptions for Nonconvex- Sertoovvee-Stoolly-Coooee Bilevel Optimization
Assumption 3.3. The objective functions ff and satisfy: (i) f is L-smooth in (z, y): for every x, E.
[f g)ll S Ly.0 and V/V (x, y: E) S ly.o- (ii) For every x, 9(x.-) is -tronnly convex for Ny > 0 and g is 1g.1 -smoohh in (I,z). (ii) g is twice continuously differentiable, and V2 v2 2
are .p.s-hips in (xr, v)-
Remark: Assumption the condition V Fy Vi 5) < 1y.0 is essential for deriving f v)
3.3 is standard the bilevel optimization literature 40
45
22
33
Notably,
E E (z. y: e)ll s o E.3 (see Appendix E. for the definition of V fx, y {)), where & plays similar role to
in Lemma
3

---

oz in Assumption 3.2 for minimax optimization. Under these assumptions, the objective function + =smooohh: please refer to Lemma E.T in Appendix E for the definition of Lp and further details.
Assumption 3.4. All stochastic estimators are unbiased, and almost surely satisfy (i) || F( y:
Var y)ll I oy; (ii) Fl, v) V w)ll S ay (iii) GZ, () V (g S
0.11 (iv) 2 G(a yi () - V
(ا vlll S g222 (v) V G(z, yr () V my (z, w)ll S 0,25 (vi)
[V](2, ur E E [ OIll zΦ. where Vf(z, wi E) is defined in Equation (39
Remark: Assumption 3.4 (v) assumes the noise in the stochastic gradient and Hcssian//acobian bounded with probability one. This is a commonly used assumption establish high probability guarantees or handle generalized-smookk objective functions in the single-level optimization literature
78 77.. as well as for stochastic bilevel optimization under the unbounded smoothness setting 33 25 Assumption 3i4 vi) is a stochastic gradient noise lower bound for the bilevel optimiza-
[46
2
39
tion problem, sharing similar spirit to Assumption (.2 Note that Assumption 3.2 is empirically verified in Appendix L Under Assumption 3.4 we also have [ (a, yi {) E|V [[r, yi E < o where the definition of og can found Equation (44 See the detailed proof in Lemma
E.3
Additional Notations. In the subsequent analysis, we denote Kg == 0/a in Section 5.1 (single-level optimization), fig == /g/ in Section 4.2 (minimax optimization). and No = F in Section 4.3 (bilevel optimization). We also adopt the convention 0/0 == 1.
4
Algorithms and Main Results
4.1 Main Challenges and Algorithm Design
Main Challenges. While numerous adaptive gradient algorithms with adaptivity to stochastic gradient noise are developed in single-level optimization 48 67
36 2]. designing algorithms with such an adaptive guarantee in hierarchical optimization is nontrivial. The main challenges lies in the following two aspects. First, designing such an algorithm in hierarchical optimization requires careful balance between the upper- and lower-level update [29 [4, (O)), which is difficult
42
to achieve without the knowledge of the noise magnitude of stochastic gradient. Second, applying AdaGrad-type type algorithms (e.g., AdaGrad- Norm (67) simultaneously to the upper- and lower-level variables will introduce complicated randomness dependency issues due to AdaGrad stepsizes (2), which are difficuult to handle unless strong assumptions (c.g., bounded stochastic gradient, bounded function value) are imposed as in [47].
Algorithm Design. To address these main challenges, our proposed algorithms leverage the nor- malized stochastic gradient descent (SGD) with momentum for the upper-level variable [1]] with a noise-aware adaptive momentum parameter and carefully crafted adaptive stepsize schemes for both levels. The momentum parameter automatically estimates the level of noise in the stochastic gradients on the fly, and this estimate is used to construct the stepsizes to maintain a balanced progress across both levels. These adaptive mechanisms, together with the momentum normalization technique, not only improve optimization stability but also make the theoretical convergence analysis more tractable. In particular, our proposed adaptive algorithms, namely Ada-Minimax and Ada-BiO, are designed for the minimax problem (I) and the bilevel problem (2) respectively. Both algorithms achieve sharp and adaptive convergence rates of D(1/VT + Vo for the gradient norm, where denotes an upper bound on the stochastic gradient noise. We describe our methods in Algorithms T and 2 with novel parameter choices in Equations 3 and (4). Their respective convergence guarantees stated
in Theorems 4.1 and 4.2
Adaptive Parameter Choices. For simplicity, let az 1 - Br. In particular, for both Algorithms ]
and we set Ott, a/, Na.t, Tn,t as follows:
0f a² + Et
(3)
a2 + k= 11 - 12
Et
I1 gz. 112 + 11 1|
7/0
11
1/
Vi
and
ny.t
V12 12 Σt - |l
4

---

Algorithm Adaptive Algorithm for Minimax Optimization (Ada-Minimax)
Algorithm Adaptive Algorithm for Bilevel Op- timization (Ada-BiO)
1: Input: 91. = V (1I,
1: Input: 21, 91. my = (1(21,31:E1)
2: for 1.....2 do
for 1.... do
3: my = f1m,-1+ (1- 3r)g
3: = -mm4-1 + 8e)
4: #t+1 2t 7/ I
4: #++1 = It 7/x, [|m
5: Mr+-1 Vt + 19.t
yt+1 = Yt 1y.19v.
6: end for
6: end for
In the above formulas, the terms Is.t, Is.1, and gy.t carry different meanings; the subsequent sections (Sections 4.2 and 4.3) for their precise definitions. For simplicity, we set Te 7 = 1j in analysis of Algorithms I and (see Theorems 4.1 and 4.2) It is worth noting that this condition is not necessary for establishing convergence, as only affects the universal constants in the rate.
4.2 Adaptive Algorithm for Minimax Optimization
Our proposed algorithm Ada-Minimax is presented in Algorithm The algorithm updates the upper-level variable using normalized SGD with momentum [T] with adaptive and parameter-free choices for the momentum parameter and learning rates. The lower-level variable is updated by AdaGrad-Norm. In Equations (3) and (4), Ix.t F yei Et). 92,t Fx ye: Et), and
Gy.1 V Fzz, yri Et), with Et, St being independent samples.
Intuitively, the term Eiz 19g..k - Is.,ell in the denominator of is designed to approximate the variance term o Tp as in []]] and this choice is partly inspired by AdaGrad-Nomn [14 2 Additionally, using af instead of a in the design of 7,, effectively controls the ratio T2, 72,//y,, and facilitates establishing Lemma 5.7 It is worth noting that Assumption 3.2 plays crucial role in
deriving tight, high-probability upper and lower bounds for both Σ k== Ir,k Lemma 5.5) for details.
Iz. 1|2
and see
Theorem 4.1. Under Assumptions 3.7 and 3.2 and the parameter choices in Equations and let o₂ T then for any E (0, 1/7), it holds with probability at least 76 that
[D(x:))
Om wa
a²+
I22
(4D2 +0222++2777)) +2D+)
1/4
VT
12122
1/4
22V2T220
T1/4 (50?) 1/4
1
+ T3/8
12212
where Cm = ((K2) and D) are defined in Equations
24 and (38) respectively.
Remark: Theorem 4.1 demonstrates that Ada-Minimax achieves a rate of Ö(Vā, in the stochastic setting (a. 0) and ((I/VT) rate in the deterministic setting (ā. 0). More importantly, our bound achieves the same bound of normalized SGD with momentum under known stochastic gradient variance [II]: it automatically interpolates between sharp rates in both high-noise and low- noise regimes without the knowledge of noise level. Specifically, the convergence rate improves from Ö(1/T1/4) to faster Ö(1/VT) when o. is sufficiently small, namely ã. (()vTT) Notably, this automatic rate interpolation does require prior knowledge of any problem-dependent parameters, and our proposed Ada-Minimax algorithm is fully parameter-free. In contrast, AiAda (47) does not exhibit such a bound in the low-noise regime (c.g., o. = O(I/VT)), and its convergence rate is not optimal with respect to o. in the stochastic setting since their convergence rate (c.g.. Theorem 3.2 in (47) does not explicitly depend on og. See detailed proof of Theorem in Appendix [ A comparison of adaptive methods for minimax optimization is also presented in Table [
4.3 Adaptive Algorithm for Bilevel Optimization
Our proposed algorithm Ada-Bio presented in Algorithm 2
The overall framework closely resembles that of Algorithm The upper-level variable is updated using normalized SGD with
5

---

Table 1: Comparison of Adaptive Methods for Minimax Optimization
Mothal
Saking
Assumpiiins
High Produbiliyy
Complesiy
RAde
Determiniios Theurno 3.1]
Assurption in
011/33)
RAde
Stochallc Thooeen 3.2]
Assurption to a
Olpsay()) (I
Ada Mr-Minnex Deiemiatic & Stochartic hhormm in this workd
Assimptions 3.1 and 3.3 this work
00/22 + 22 10./299
Table 2: Comparison of Adaptive Methods for Bilevel Optimization
Metiod
Setting
Assamptions
High Probubility
Complexity
S:TFBO 23
Detemminitti (3 Theceen
Assupption to 3 A3
(
AdeWWio
Devemimttic Stochaatic (Thoorm this Assumptions 1.3 work
On/vT 22 vo
momentum I employing adaptive choices for the momentum parameter and learning rate. This
approach differs from those of [33 25). where fixed, non-adaptive momentum parameters and
learning rates are used. The lower-level variable is updated via AdaGrad-Norm. Here in Equations (3)
and ( S2,t = V (1 yr: Ec). Ha.t - (aa,, Mri E.). and Jy, 1 VyG(ar, yri (t), where Vf(x, y; E)
denotes the Neumann series approximation (see Appendix E.1 for further details), with & E/ being independent samples.
Theorem 4.2. Under Assumptions 3.3 and 3.4
and the parameter choices in Equations and
for any 5 E (0, 1/7), choose N Z 2log(1/(1 (or0ll11-PPPP.01)1 Po)l
3logT
holds with probability least 1 75 that
1
T
Cb a
12
1/4
5
a
(4D2gg
9.1
T
VT
p2nz2
1
Do 2V g.l
1/4
+ T1/4 (45 + +0g 02.1 1/4
+
T3/8
122112
where C = Ö(r)), D. and og are defined in Equations (44
44 and 46 respectively.
Remark: Theorem 4.2 shows that Ada-Bio achieves sharp rate of Ö((ā), 1 ///// in the stochastic setting, where all noise terms introduced in Assumption 3.4 are positive. Moreover, it obvious that Ada-Bio implicitly adapts to the noise level; in the noiseless case (where all noise parameters in Assumption 3.4 vanish), Ada-Bio Bio automatically recovers the near-optimal Õ(L/VT) rate. To the best of our knowledge. Theorem 4.2 provides the first sharp and adaptive convergence guarantee for stochastic bilevel optimization without any prior knowledge of the noise parameters specified in Assumption 3.4 In fact, we only require the knowledge of (gg. lg. and T due to the construction of Neumann series. See detailed proof of Theorem 4.2 in Appendix A comparison of adaptive methods for bilevel optimization is also presented in Table
5 Theoretical Analysis
In this section, we provide the convergence analysis for Algorithms and 2 with the adaptive parameter choices in Equations 3 and A We begin in Section 5. b. analyzing an adaptive version of normalized SGD with momentum (Algorithm optimization setting, where we establish a convergence rate of Ô(1 + Vō //4)) where ē is an upper bound on the stochastic gradient noise. We then extend this novel framework for the upper-level analysis in both minimax and bilevel optimization, combining it with a generalized AdaGrad-Noo analysis in the (strongly) convex case (2] under time shift for the lower-level variables, presented in Section 5.2
3) in the nonconvex stochastic (single-level)
Due to space limitations, defer the full proofs to Appendices C to E
5.1 Adaptive Normalized SGD with Momentum
With a slight abuse of notation, we consider minimizing an objective function f(x) = E F (ax E
We start with analyzing adaptive normalized SGD with momentum presented in Algorithm 3 where
G denotes the upper bound the stochastic gradient norm, and a, satisfy < a 1.

---

Algorithm 3 Adaptive Normalized SGD with Momentum (Ada-NSGDM)
I: Input: 3 my V
2: for t = 1...., T do
3: my -mm--1 (1 3t)g
4: 2++1 2t 17 |meel
5: end for
V (z; ft). This algorithm builds on the method introduced by [II], with the key difference being that we incorporate both an adaptive momentum parameter 3r and an adaptive stepsize nhs each of which varies across iterations. In particular, let = 1- Be and we set and 1)t as
T aya VE
0t
and
(5)
V / + g 9x
1
where 9: VF(r; (t) and Le, E are independent samples. We will make the following assumptions. Assumption 5.1. The objective function f is L-smooth.
Assumption 5.2. The gradient oracle is unbiased, i.c., ([VF(x;; x] = Vf(xx, and with probability one, satisfies < FF;;; Vf())] <
Before proceeding, we introduce the definition of Ka and to, which will be frequently used throughout the subsequent analysis. Specifically, we define (with the convention 0/0 = 1)
f0/a 11
α 0 σ = 0
g and to max 2,
A1 (6) co B1 (8)
Kg
Co
(6)
4 2
c
where Ar(:) and (+) are logarithmic factors (double-log in T) defined in Lemma A.1
We now present the main lemmas necessary to establish Theorem [.6 All of these lemmas rely on Assumptions 5.1 and 5.2, unless explicitly stated otherwise. The full proof of these lemmas are
deferred to Appendix B The following lemma is a standard recursion for the momentum deviation.
Lemma 5.3. Define
m4 mf and 4 9:- (xx)). Further, let St
For all 2 1, it holds that
= B2.é + Ek- B(R+1) Brr
In order to obtain high probability bound for || we need the following technical lemma, which leverages the concentration bound introduced in [55] Lemma 2.4] and tools from linear programming (see Lemma F.5 in Appendix (F) to resolve the difficulties arising from statistical dependency among ar 3r, and Ez.
Lemma 5.4. Les & 04 S at S ā. and < B: S 3: S Br. where ae, āz, Bi. and B, are independent of Ft. Then with probability at least
25, it holds for all t that
2 < ā / 1232lop log 27 4)
Ei (k+1): a
Next, we provide sigh-probability lower and upper bounds for a and 8,, which help us to derive tight upper bound for the right-hand side of Equation (7) (see Lemma G.2 in Appendix G Our analysis relies the martingale technique developed by (6]. which uses empirical Bernstein concentration bound introduced by [35]. Recall the definition to as Equation (6). 5.5jma555jindicatt that o and B, reliably approximate the optimal momentum parameter settings after to ilerations: they are both upper- and lower-bounded by quantities of the same order, even without prior knowledge the noise level a.
Lemma 5.5. With probability at least 1 - 8, for all 1 T.
a
0. ā. = 1(t < to)
1(t 2 to).
Va² + 4
Va +
a
a
Ilt 2 to) = 8. x
3
V a o2t
Va² 47
7

---

Now we are ready the present our main theorem regarding Algorithm
Theorem 5.6. Under Assumptions [.7 and the parameter choices in Equation 5 for any 5 E 1/3), it holds with probabiliry at least 35 that
C (
2 Vari
Σ
T
VT
where C= ((K2) is defined in Equation
19
Remark: To our knowledge, this is the first adaptive convergence guarantee for normalized SGD with momentum. Algorithm 3 achhevess a rate of Ó(1/T"/#) in the stochastic setting and ((1/VT) in the deterministic setting. This ante-interpolation occurs automatically without requiring any prior knowledge of wroblem-dependee parameters. We emphasize that Theorem [5.6] builds a general analytical framework for proving Theorems
and 4.2 See Appendix B for detailed proofs.
5.2 Proof Sketch of Theorems 4.1 and
In this section, we present a unified lower-level analysis applicable to both minimax and bilevel optimization. Recall from Sections and that the bilevel optimization problem (2) reduces to the minimax optimization problem [ when = =ff. Therefore, we analyze line of Algorithm using the function g and stochastic gradient descent (instead of the original f and stochastic gradient ascent): M/+1 3/2 77,,1y.ts where 9y.t = VyG(TT yr: Ee) V F(r,, ye: Et). Note that the following lemma Leemma5577 well as Lemmas C.I and Appendix C are applicable the
proofs of both Theorems 4.1 and 4.2
The following lemma provides high-probability guarantees for the lower-level estimation error, which are crucial for controlling and bounding the (hyper)gradient bias. The core of our result generalizes the AdaGrad-Norm analysis developed for convex settings by [2], accommodating steration-dependen shifts induced by the upper-level variable and incorporating our novel adaptive parameter choices as detailed in Equations (3) and (4) and Sections 4.2 and 4.3
Lemma 5.7. With probability at least 1 46, for all
= maxks: 1l
vill S D, and
1u vell < 12212
2 +D2 222
(8)
1l -illl < ((V2DL+ V V2Dott/4).
1
(9)
[m]
where D is defined in Equation 24 and a o.y for Algorithm 7 and a = 0g.1 for Algorithm
Combining the upper-level analysis framework introduced in Section [5. with the lower-level es- timation eтrоr bounds (i.e.. bounds on the gradien/hypeegradienn estimation bias) established in Lemma 5.7 we can prove Theorems 4.1 and 4.2 similarly to how we derived Theorem 5.6 The
complete proofs are deferred to Appendices to
6 Experiments
In this section, we empirically evaluate our proposed algorithms on three tasks, including syn- thetic test functions (Section 6.1), dcep AUC maximization (Section 6.2).. and hyperparameter optimization (Appendix KK. addition, we further test the robustness of our algorithms by vary- ing several key parameters (e.g.. initial learning rates, initial momentum parameter), which is wwwweiooomniieeeeee Mit///nuuuiuuM--aaba.....
included in Section 6.3 The code is available at
adaptive- adaptive-hierarchee hhw.aarccicll-oppiiiaaaiooo
6.1 Synthetic Experiments
We conduct synthetic experiments on simple one-dimensional function [ax, y) = cos cos or ay - 1 which satisfies the nonconvex-stronngyy-oomm minimax optimization setting. It is straightforward to

---

Cradiant Nom: K-altay
Credient Nom: R. K-adanl
Gradient Norm: ia - EnAl
Grediest Norm: i, Ku-alos
Mieees
de
dde
25
1.
2.5
23
530
200
330
100
600
38
500
380 33393333
12:
3330 3330
2005 2003
(8)
(b)
20
(c) 0 50
(d) 100
Figure Synthetic experiments on a 1-dimensional function for minimax optimization.
Training
Training AUC
Made
6,00
0.00
6.40
0.03
6.9
55
1093
2206
400
1003
7400
10.00
1890
(a) Training AUC
(b) Test AUC
(c) Training AUC vs. Time
(d) Test AUC vs. Time
Figure 2: 2-layer Transformer for deep AUC maximization imbalanced Sentiment140 dataset.
verify that (²(x) = x, ((x) = (())) = cos x + 1=²2 and (2(z)= = sin σ. To simulate stochastic gradients, we add Gaussian noise sampled from (0 demonstrated in Figure II, proposed method, ada-Minimax. consistently outperforms TiAda [47] across various noise magnitudes. These results clearly illustrate our algorithm's 's adaptivity to noise levels: specifically, the noise magnitude decreases, convergence. Notably, under high-noise regimes (e.g.. a = 100), TiAda fails to converge even after extensive parameter tuning, whereas our algorithm successfully converges. The hyperparameter settings are included in Appendix !
from.W(0, o²) ) to the ground-truth gradients. As
algorithm automatically achieves faster
6.2 Deep AUC Maximization
The Area Under the ROC Curve (AUC) is performance measure of classifiers 31 32 which is
widely used in the imbalanced data classification setting. Deep AUC Maximization (DAM)
[79] 76]
is paradigm for learning a deep neural network by maximizing the AUC score of the model
on a dataset. Recent studies 75 76, 53 have shown great success of deep AUC maximization in
various domains (e.g., medical image classification and drug discovery). Following 75 maximization can be formulated as a minimax problem.
54 53
AUC
min max f(w, a, a) BE_D[F((wwrr a, b, we MERRd((.MM)RR OER
(10)
where F(w, a, 2) = (1 p)) (ph((w; a:) [y== - -p)((;;ww (=== - p(1 - pp)a u is the parameter of a deep neu- ral network (e.g., a two-layer transformer as the predictive model), h(w;;)) is the score function parameterized by w with the input data x, E (ar, .) is random sample from training set D with input x and a binary label y E (-1, The imbalanced ratio is the proportion of the positive samples in the training set. Therefore, (w, a, b) and a are primal and dual variables respectively.
a)<[|v=1]] + p(h(w;; x) - b) + 2(1
To verify the effectiveness of our proposed Algorithm D we run a practical variant (refer to Ap- pendix D of our algorithm in deep AUC maximization experiments on imbalanced text classification, and compare with other minimax baselines, including SGDA [50]. PDSM (0), and an adaptive minimax algorithm TiAda [47). We first construct the imbalanced binary classification dataset Sentiment 40 [23] (under Creative Commons Attribution 4.0 License). The practical variant of our algorithm replaces the term Ei= ||9r. - A= in Equation (3) with Σi= I|gz, 92. ||2 where -- denotes the gradient of computed at the previous iteration (i.e., (k- 1)-th iteration). Additionally, we modify the step size from 7/x.t = 7 / / /vt to T2., = 72 /a, / (note that this change does not affect the convergence of Algorithm D In this subsection, with slight abuse of notation, The to denote n /T. Following the data setting in (76), we randomly remove

---

Training
Training
Traniing
Training Pacchary
1-4
Sd
6.
1.5
66
66
Rauce
Esech
Esech
Epeci
(a) Robustness of a
(b) Robustness of TJs
(c) Robustness of T/y
(d) Robustness of
Figure 3: Robustness of hyperparameters.
positive samples (labeled as 1) from the training set until the proportion of positive samples exactly 0.9 (i.e., p 0.9). In the experiment, adopt a two-layer transformer the classifier with the hidden size of 4096 and the output dimension of 2. The hyperparameter settings of each baseline and experimental details are described Appendix J The comparison results of training and test curve over 50 epochs are shown in Figure 2 From subfigures (a) and (b), our algorithm Ada-Minimax shows 20% higher training AUC and 2% higher test AUC than the best compared algorithm PDSM. From running time curve (c) and (d), our algorithm demonstrates the fastest convergence rate than other baselines.
6.3 Hyperparameter Robustness Analysis
investigate the robustness of our method to the hyperparameters a, Th las and by varying each parameter independently while keeping others fixed, as shown in Figure Specifically, Figure 3 indicates that changing a within the range [0.1, 2.0] has minimal impact on convergence speed and final AUC performance. In Figure 3)), varying fyy between 0.001 and 0.05 yield nearly overlapping curves after the initial training stage. Similarly, Figure 3))) shows that varying The from 0.001 to 0.01 affects only early-stage training dynamics without compromising the final performance; however, increasing 7, to 0.05 results in a noticeable decline the final training AUC. Lastly, Figure 3] illustrates that the algorithm maintains consistent performance across wide range of y values [0.01, 2.0]. Therefore, these results demonstrate that our algorithm exhibits strong robustness across broad ranges of these hyperparameters, significantly reducing the time required for hyperparameter tuning in practice.
Conclusion
We introduced two novel adaptive algorithms for sonconvex-stronglyyconcee minimax optmization and nonconvex-strongly-comt
bilevel optimization. Both algorithms achieve sharp and adaptive convergence rates: they automatically adapt to unknown variance in stochastic gradient estimates. Our approach leverages the momentum normalization framework along with novel adaptive schemes for jointly setting the momentum parameter and the learning rate. Experimental results validate and support our theoretical analyses. One limitation of our work is the assumption that the stochastic gradient noise is cower-boundee In future work, we aim to remove this assumption while maintaining the sharp convergence guarantees.
Acknowledgements
We would like to thank the anonymous reviewers for their helpful comments. We would like thank Francesco Orabona and El Mehdi Saad for helpful discussions about the concentration inequalities. This work has been supported by the Presidential Scholarship, the ORIEI seed funding, and the IDIA P3 fellowship from George Mason University, and NSF award #2436217, #2425687. The Computations were run on Hopper, a research computing cluster provided by the Office of Research Computing at George Mason University (URL: https///ore.mmu.cdu
10

---

References
[1] Kimon Antonakopoulos, Shoham Sabach, Luca Viano, Mingyi Hong, and Volkan Cevher. Adaptive bilevel optimization, 2024.
[2] Amit Attia and Tomer Koren. Sgd with adagrad stepsizes: full adaptivity with high probability unknown parameters, unbounded gradients and affine variance. In International Conference on Machine Learning, pages 1 147-11771. PMLR, 2023.
[3] Dimitris Bertsimas and John N Tsitsiklis, Introduction to linear optimization, volume 6. Athena scientific Belmont, MA, 1997.
[4] Radu Ioan Bot and Axel Böhm. Alternating graddienn steps for (stochastic) nonconvex- concave minimax problems. SIAM Journal on Optimization, 33(3):1884-191 2023.
[5] Jerome Bracken and James McGill, Mathematical programs with optimization problems in the constraints. Operations reseurch, 21(1):37-44, 1973.
[6] Yair Carmon and Oliver Hinder. Making sgd parameter-free. In Conference on Learning Theory, pages 2360-2388 PMLR, 2022.
[7] Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.00712 2023.
[8] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescee method for stochastic bilevel optimization. In International Conference Artificial Intelligence and Statistics, pages 2466-2488. PMLR, 2022.
[9] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 0222224425307 2021.
[10] Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2.366. /2067, 2023.
[11] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International Conference on Machine Learning, pages 1860022688 PMLR, 2020.
[12] 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-2677 10, 2022.
[13] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
[14] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Reseurch, 12(1ul)2121--119, 201 1.
[15] Chen Fan, Gaspard Choné- Ducasse, Mark Schmidt, and Christos Thrampoulidis. Bisls/sps: Auto-tune step sizes for stable li-le optimization. Advances in Neural Information Processing Systems, 36:5014:44 0400014-40 50172, 2023.
[16] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.065500 2023.
[17] Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pages 313-355. PMLR, 2022.
[18] Matthias Feurer and Frank Hutter. Hyperparameter optimization. Automated machine learning: Methods, systems, challenges, pages 3-33, 2019.
[19] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. International conference on machine learning, pages 1126-1 135.. PMLR, 2017.
11

---

[20] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165-1173, 2017.
[21] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle ooline stochastic gradient for tensor decomposition. In Conference on learning theory, pages 797-842. PMLR, 2015.
[22] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018
[23] Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervi- sion. CS224N project report, Stanford, 1(12):2009, 2009.
[24] Xiaochuan Gong, Jie Hao, and Mingrui Liu. An accelerated algorithm for stochastic bilevel optimization under unbounded smoothness. arXiv preprint arXiv:2409. (0:::2499//2/22 2024.
[25] Xiaochuan Gong, Jie Hao, and Mingrui Liu. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In Forty-fors International Conference on Machine Learning, 2024.
[26] Xiaochuan Gong, Jie Hao, and Mingrui Liu. On the convergence of adam-type algorithm for bilevel optimization under unbounded smoothness. arXiv preprint arXiv:2503.03908 2025.
[27] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint vrXiv:1412.65722 2014.
[28] Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic
variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266. 2021.
[29] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On stochastic moving- average estimators for non-convex optimization. arXiv preprint arXiv:2104.1444: 2021.
[30] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. Unified convergence analysis for adaptive optimization with moving average estimator. Machine Learning, 114(4):1-51, 2025.
[31] James A Hanley and Barbara J McNeil. The meaning and use of the area under receiver operating characteristic (roc) curve. Radiology, 143(1):29-33) -9, 1982.
[32] James A Hanley and Barbara McNeil. A method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology, 148(3):839-88) 833, 1983.
[33] Jie Hao, Xiaochuan Gong, and Mingrui Liu. Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis. In The Twelfth International Conference on Learning Representations, 2024.
[34] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[35] Steven Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 1952):0055-1080, 2021.
[36] Quanqi Hu. Yongjian Zhong, and Tianbao Yang. Multi-block min max bilevel optimization with applications in multi-task deep AUC maximization. arXiv preprint arXiv:2206.0022 2022.
[37] Feihu Huang, Junyi Li, and Shangqian Gao. Biadam: Fast adaptive bilevel optimization methods. arXiv preprint arXiv:2106.11 11396, 2021.
12

---

[38] Feihu Huang, Xidong Wu, and Zhengmian Hu. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. International Conference on Artificial Intelligence and Statistics, pages 2365-2389. PMLR, 2023.
[39] Maor Ivgi. Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465-14499. PMLR, 2023.
[40] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference machine learning, pages 11882-4892 PMLR, 2021.
[41] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 111):17-58, 2011.
[42] Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. arXiv preprint 2xXi::2044.02833, 2022.
[43] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang.
A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271-30283,, 2021.
[44] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014.
[45] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning. pages 18083-18113 PMLR, 2023.
[46] Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assumptions. arXiv preprint arXiv:2304. 13972, 2023.
[47] Xiang Li, Junchi Yang, and Niao He. Tiada: A time-scale adaptive algorithm for nonconvex minimax optimization. arviv preprint arXiv:2210.17477: 2022.
[48] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics, pages 983-992. PMLR, 2019.
[49] Xin Li and Dan Roth. Learning question classifiers. In COLING 2002: The 19th International Conference on Computational Linguistics, 2002.
[50] Tianyi Lin, Chi Jin, and Michael Jordan. minimax problems. In International conference on machine learning, pages 6083-6093. PMIR, 2020.
On gradient descent ascent for nonconvex-coneave
[51] Mingrui Liu, Youssef Mrouch, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference on Learning Representations, 2020.
[52] Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly-convex- hewelyyooooeeeeeell-ooooooe weakly-concave min-max problems. Journal of Machine Learning Research, 22(169):1 34, 2021.
[53] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. International Conference on Learning Represenaations, 2020.
[54] Mingrui Liu, Xiaoxuan Zhang, Zaiyi Chen, Xiaoyu Wang, and Tianbao Yang. Fast stochastic auc maximization with o (Vnn)-convergence rate. In International Conference on Machine Learning, pages 3195-3203, 2018.
[55] Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal non-convex stochastic optimization under generalized smoothness. arXiv preprint
2023.
13

---

[56] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning. pages 21894411914 PMLR, 2023.
[57] Songtao Lu. Slm: A smoothed first-order lagrangian method for structured constrained non- convex optimization. Advances in Neural Information Processing Systems, 36:80414-80454, 2023.
[58] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal Optimization, 34(2):1977-1969, 2024.
[59] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic noncomeex-strongly-coom Information Processing Systems, 33:20566-20577, 2020.
minimax problems. Advances in Neural
[60] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint 100.44400,,4908,, 2010.
[61] Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[62] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[63] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Progrumming, 109(2)311-334, 2007.
[64] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimiza- tion: Provable algorithms and applications in machine learning. Optimization Methods and Software, 2020.
[65] Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05188, 2023.
[66] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop, coursera: Neural networks for machine learning. University of Toronto, Technical Report, 6, 2012.
[67] Rachel Ward, Xiaoxia Wu, and Leon Bottou, Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1-30, 2020.
[68] Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for min-max optimization. Advances in Neural Information Processing 33:57m 33:5789-58000, 2020.
[69] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class of nonconnex--nnncooenn minimax problems. Advances in Neural Information Processing Systems, 33:1153-1165, 2020.
[70] Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostic non- convex minimax optimization. Advances Neural Information Processing Systems, 35:1 1202- 11216, 2022.
[71] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pages 5485-5517. PMLR, 2022.
[72] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 13:10--016622 2021.
[73] Yifan Yang, Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. Tuning-fres bilevel optimiza- tion: New algorithms and convergence analysis. arXiv preprint 241.522410.05140, 2024.
14

---

[74] Zhenhuan Yang, Yan Lok Ko, Kush R Varshney, and Yiming Ying. Minimax AUC faimess: Efficient algorithm with provable convergence. arXiv preprint arX1v:2208.10451, 2022.
[75] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In Advances in Neural Information Processing Systems, pages 451-459, 2016.
[76] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep maximization: A new surrogate loss and empirical studies on medical image classification. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 3040-3049, 2021.
[77] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 2020.
[78] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference Learning Representations, 2020.
[79] Peilin Zhao, Rong Jin, Tianbao Yang, and Steven Hoi. Online auc maximization. In Proceedings of the 28th international conference machine learning (ICML-II), pages 233 240, 2011.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Every claim made in the abstract is specified section of the paper, including algorithm design and analysis Section and experiments Section 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of our work in Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
We provide both assumptions and proofs in Section 3 and Appendices B D
and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The experimental details are specified in Section 6 and Appendices Io
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer:
[Yes]
The code and data are attached as supplementary material with instructions for reproducibility.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pp cc/public/guu geoggudddde//oeebbinnin htt.SSbbbiiiiooooiiiiiooooii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are included in Section and Appendices too
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[No]
Justification:
We only run once due to limited computational budget and resource.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
18

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The hardware specification is described in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have read and conformed to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field of Machine Learning from algorithmic and theoretical aspects. We do see any direct paths to negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not involve the release of any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our paper uses existing text classification datasets and are cited in Section and their licenses are mentioned.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
22

---

Contents
Introduction
2
Related Work
Preliminaries
Assumptions for Nonconvaa-Sronelyy-Conavv Minimax Optimization
3.2
Assumptions for Nonconvex-Sttroggly-Cooee Bilevel Optimization
Algorithms and Main Results
4.1
Main Challenges and Algorithm Design
Adaptive Algorithm for Minimax Optimization
Adaptive Algorithm for Bilevel Optimization
5
Theoretical Analysis
5.1
Adaptive Normalized SGD with Momentum
Proof Sketch Theorems land
6
Experiments
6.1
Synthetic Experiments
6.2
Deep AUC Maximization
6.3
Hyperparameter Robustness Analysis
10
Conclusion
10
Martingale Concentration Bounds and Basic Inequalities
24
Proofs of S.c
24
Technical Lemmas
24
2
Proof of Theorem 5.6
27
Proof of Section 5.2
27
Proof of Lemma 5.7
30
Analysis of Algorithm]
33
Technical Lemmas
33
D.2 Proof of Theorem
34
Analysis of Algorithm
35
Neumann Series
35
Technical Lemmas
36
Proof of Theorem
Linear Programming Basics
38
23

---

Useful Algebraic Facts
41
H Discussion on Existing Algorithms for Minimax Optimization
49
Experimental Settings for Synthetic Experiments
49
J Experimental Settings for Deep AUC Maximization
49
Experiments for Hyperparameter Optimization
49
Experiments for Verifying Assumptions
50
A Martingale Concentration Bounds and Basic Inequalities
Lemma A.1 (6) Corollary IJ). Let X, be adapted to Fs such that [xa & with probabilit I for all
t. Then, for every E 10, and any X, E Fi-1 such that Xel I with probability 1,
Pr 3 < 00:
Σ(x, E[X, Fo-1l) 2 A(()) Exx, (()= +B(0) SSt.
S 8,
SSt.
where A,(o) 16 log
60 (og( and B, 16 10g
( log (61)
Lemma A.2 (55 Lemma 2.4]). Suppose X1...., Xy is martingale difference sequence adapted
filtration Fi,...:- Fr in Hilbert space such that |X,|l s R₁ almost surely for some R₃ Fi-1- Then for any E (0, 1), with probability at least 1 6, for any fixed we have
Σ X
log Σ R2.
Proof of Lemma A.2 The proof concludes by setting R2 E F in 15
Lemma 2.4].
Lemma A.3 (22 Lemma 4)), Let 91.....9r Rd be an arbitrary sequence of vectors, and let Go O. For all 2 1, define
G. =
G +
12
==1
Then
Σ
T
gg
12
<
2
T'
11
12,
and
T 11
< 2 log
GT
G.
G
Go
1=1
Lemma A.4 (22
Lemma 6)). For Ada-NSGDM (Algorithm))
3 we have
Σ
||
< C1
log [1
25
L + SLAIT)
(II)
G
72
1=1
where A fx11 f
B Proofs of Section 5.1
B.1 Technical Lemmas
Lemma 5.3. Define & = m, - m (2x) and - vf(()). Further, let S, = -f(zz-))VV((z)
For all > it holds that
= B2 + E 3(R+1) BrrS
24

---

Proof of Lemma
5.3 The proof follows from a straightforward calculation:
& my f24a
- + (1 - -:)9 (x+)
(e vf(x=-1)) + (1 Be)(E: Vf(xa)) - Vf(az))
B + (1-3 B,S,-
Unrolling the recursion and using 04 = - 3g yields the result.
Lemma 5.A. Ler S Qr S at S a. and 3g 3. S Br. where or at, Gt. and B. are independent of Fr. Then with probability at least 1 - 25, it holds for all t S T that
Enm Metnaea S ō 8o 32 21" Ei (
Proof of Lemma 5.4
Define Thet B(4+1y: and ((i,)) (3 33isi,, 2 25j Then for
all S 4
1(++)) = Thtt S Thet S Tke= = 1(++))=
(12)
By Lemma F.5 there exists set (o,ne, with each bi satisfying either 6iz, = 2e, or
biz = Tj for every pair (i.j), such that
ΣΣ =
(g)
1=3 5=2
Applying Lemma A.2 with X; = e,. 2j= bi
E5 5, for all S T,
and Rs = ō
Σj=
by 19
E Fi-1,, and using
a union bound over I, with probability least
21
i-1
ΣΣ i=3
Ess
S 4
log
8
Σ
(13)
j=2
j=2
Applying Lemma A.2 again with X3 t with probability at least 8, for all S ST
Ej and R2
bi E R. and using union bound over i,
i-1
2T i-1
b S
S log
Σ
(b
1))
(14)
5
j=2
Combing Equations
13 and (44, with probability at least 26 (via a union bound), for all t S T,
ΣΣ
Ma G) < 16 log
27 (2
8
1=
27
27
16 log
Σ (3,4), < 16 log
Σ 22
8
where the second inequality uses
big 5 Tz.e Hence, with probability least 1 28,
+-1
Σ B(1+1)aaa
Σ
2 11 +2
2=
1=3
2T
1 g2 +2llog
02
k=2
27 1 + 32 log
02
8
Plugging in the definition of Fe.s in Equation
12] yields the result.
25

---

Lemma 5.5. With probability at least 1 - 8, for all t TT
a
2z _ a x ae I[t to) +
a
I[t to),
va² + 47
Va² +
1
T(t to) = & - 8 3
a² + 02t g2t
va 4
Proof of Lemma 5.5 Consider the case 0 << g I o. By Assumption 5.2 and Young's ' inequality,
11 Ixll S 2 l1gn vf(x=)]] + ll vf(xx))1 - 4
(15)
1==1
We proceed to derive high probability lower bound for Σ 11 - 1| - Denote of = Ex-illlg
V fxx)) Let Ze
= 19 - gell 20 then {Zi a martingale difference sequence since
E [Z] E |1 3.11 - 20?1
E |||a (x,,))) + l Vs(x)]]] 2(g. V -V/=))) 20
= 0.
Using Assumption 5.2
and Young's inequality again, we have
Z 2 ?
and Z, S 2
(x(x)) + 211 - vf(xz)] - - 462 -20?
This implics that
Z S max {20,: 40 - -20 = 402 -20
where the last equality is due to a S ō almost surely. Define X, Ze/(40² 100-2201 207)), then |x, S 1 with prohability 1. Applying Lemma A. with the X,, we defined and X,, 0, for any d (0, 1), with probability at least 8, for all S.
Σ X
A,(5) Σ x B,( S (A(()) ++ B,(5),
(16)
where the last inequality uses Ek= X < / since |&| < 1. Recall the definition of lo and op as in Equation (6) (ta is the solution to the equation Ar t + Br (6) = cftt), for all 2 to.
o²t
VAr(8) -1+ B(()) S V Ar(()) 1+ (r) < cgl = 2 20
Then, expanding Equation 16 and using the above condition yields that, with probability at least 1 8, for all to ST
1 12 20
att
1gg
G 2
(17)
462
2
46
20
We conclude the proof by combining Equations 15 and 17] and noting that the results also hold for
the case 0 0.
Lemma B.1 (Descent Lemma). Under Assumptions 5.1
5.1 and 5.2
define é m, fx(()), then
L
f(x++1) E f(x)) - n [xx)) + 2n. +
2
Further, define A f(z1)= f*, taking summation and rearranging have
T m [V[[(a)
L
+ ne
||Eell
Σ
m
2
1=1
26

---

B.2 Proof of Theorem 5.6
Before proving Theorem 5.6 let us define (recall the definition Ki and to in Equation 6 here
Rg = 5/g in single-level optimization)
60 (og()))))
A = f(11) - f" to = max 2.8 (32kg -30xg + 7) log
(18)
C= Ai + 4njō (vo 1 ev/ia (1+2/o/u)) Lnp² (1 log 7)
(19)
+ 2// + 32 log(27/0)) (100 - 22ve2 2//ro (1 1 σ + a
+ 4441² 1t) 1) (1 [1 eVio 1 0/a) + e(vFio + 2k. log log?)) T)
Jorany Theorem 5.6. Under Assumptions 5.7 and 5.2 and the parameter choices in Equation (5) for any
E 1031 it holds with probability at least 35 that
+
Σ
C
(()
/ V
2 VaTuA1
T
where C = (K22) is defined in Equation
19
Proof of Theorem 5.6 Without loss of generality, assume to is integer (see definition in G.2 with probability at least 1 1-30
Equation (6)) By Lemmas 5.3 to 5.5
B.
and
L
Mc Vf(x))l s A +
Mell&ll
Σ
m
2
T
T.
< 1 + 2
B2alLall+
Σ B(at)aaakk
+
S
+
m
2
t=1
k=2
t=1
(1+ log
27
L T
< < + +2>
71
32.0 +o
(k+1):t
at + Z
Bk:07k-1
+
m/
1=1
k=
k=2
1=1
Ln7²
$ A1 + 4njō
(voo 11 + E/ (1+2V0/o)
(1 + log
+2 32 32gog(2T/8) (to- (+ 2//50 (1 (1+2 2//
σ aVengalog]
4Tap (1o- - 1) (1 (1+e/Ro 11+2/0/0 + +elvno + 2xd log T)
C,
where the third inequality uses ||& = |||||| s ā and || = [[V[ -V(xx)) S L and the last inequality is due to the definition of C. Then, using Mi 2 71 fort ST,
T
Σ
EmIVV((a) Σ m [f(x:)] sc
Therefore, with probability at least 1 36.
T
Tm S C(a² + 402T)
C < n
VT + 2
T Σ
n/aT
Valia
C Proof of Section 5.2
The core of our result this section generalizes the AdaGrad-Norm analysis developed for convex settings by 22 accommodating iteration-dependent shifts induced by the upper-level variable and
27

---

incorporating our novel adaptive parameter choices as detailed in Equations (3) and (4) and Sec-
tions 4.2 and 4.3 In particular, Lemmas C.I and C.2 are direct applications of 2 Lemmas 15 and
16]. whereas Lemma
5.7 extends
[2] Lemma 13] to account for time shifts.
Recall from Sections and 3 that the bilevel optimization problem 2 reduces the minimax optimization problem ① when = -f. Therefore, we analyze line of Algorithm [ using the function 9 and stochastic gradient descent (instead of the original and stochastic gradient ascent):
9t+11 - Tl..99.. where Gy.t Vr,G(r,, Mri {t) - -V, v yri &t). Note that the following
lemmas (Lemmas) 5.7 and are applicable to the proofs of both Theorems and 4.2
Additional Notations. Let y y" (x=1 and de = 11y. yr ||. Define de = max de. the proof
below, a "decorrelated step size" given by
fg
7
where Gy.t
72 +
19..112
G
v + V Vz voll
k==1
Lemma C.1. Let d; maxfde, 77. Then with probability at least - 25, it holds that for all t s T,
E Nuck (V Vog(IKKNV) Iu.k. yk 4i)
S 2/l ((8/))g(44)) Σ
kyyk- V Vug( 9y. + 02 (0/66//og(11) (4T))
and
2 My.k Vyg(Ex.
Iu.ks yk -4h)
S 22 Ar(8/ log((T))
dy Vyg yk) go.ul13 + 2 (6/l//))))));
kSt
where A.(-) and Bi(+) are defined in Lemma Algorithm 2
A.I and a By for Algorithm Jand = 0g1 for
Proof of Lemma C.1 In order to invoke Lemma A.1 we will replace yv V with version which
is scaled and projected to the unit ball. We denote a, = 2n and s; log(d; /d/dd/))))))))))))())))))) + 1. Thus,
de S d' S as. I 2d. Since ||ık+41 - Vi+ill S llyk - vtll + n for all s, de S d1 7 - 1) and
1 S 8, S [log(1)] +1 log(4T). Defining the projection to the unit ball, π1 (xx) x/ max (1, ||=1]]
Yk oe 1I
y/ Vi
age
as.
Note that
M (V Vyg(a,, vk) ky.kk 1l S 7g.00.
(20)
Thus,
do VV Vogl vk)
ky.k. Uk V%r
My.k (V Vyg(ar. wk) gyck) II
yk Vk
7g.00a.
17.00
as:
km
Ny V ggg (k Uk) gg.k))
Yk yk ass
111
(21)
11,000
fg Vyg(IRK yk)
Iv.k)
Uk yk as
max 15s5 [[g))4))
II,
7y.00
Let (() be defined as
(+) fg.k ( Vug(zk. 4k)
Iy.k)
1/k yk
7y.00
ag
28

---

for some Then k is martingale difference sequence since
1 Vyg(
Ex X k = 0.
Also note that (6) < 1 with probability 1. Using Lemma A.1 with the X(()) we defined and X; 0, for any and E (0, 1), with probability at least 8', for T.
Σ x
(+) k
Ar(8))
[ Be(8').
We can upper bound (X(
Ny. V Vyg(Ts vk)
9y.k 11? (mw.000)2
2
(xx
yk Vk
I11
W7 x V (2 8kk
(2
9y 112
(1y.000)2
1IV Vo yh) - gy. 112
(Ng.w0r)2
where the first inequality uses Bauchy-Schwarl inequality, the second inequality is due to [II < 1, and the last inequality uses fy.k S 7y.k-1. Thus, returning to Equation (2I multiplied by 77.000..
with probability at least 1 - 8' log (og(4T") (union bound for all 1 I S [log(4]).).
ni 1y (2
Mo. Work 9k) gy.ki Uk vit) S 0g.00a. (8)) SSt
|I Vug(#k: uk) - gy.k + Be(8').
As as S 2d,, picking 8' = =8/ log(4T), with probability at least 1-6, 8,
My (V Vygl Uk) Bu.k. Uk
vi)
(22)
S 2d, A4(6/log(11)
Σ ny R ViVVVg(a yk) 9y. 112 + o2 log (4
Similarly, replacing 0g.6 by i and 19.00 by v in Equation 20 and using 0g.k-1 S. 7y.0 yields that, with probability at least 1
following the analysis above,
Mr (Vgg(ok. vk) - I9.ks 8k - -v%)
(23)
s 2d; / AA(6/1log(41) Σ
Thik-illV Vog 2y. + og (,010))((((
log(4T))
k
$ 2dd, Ar(0/ ((0//)
n2 Σ
11 V 3n) gy 11 + ni 2 (8 log (47").
kSt
We conclude by applying union bound over the events (Equations
22 and 23
Lemma C.2. With probability at least 1 for all ST
o 2T
2n2
T
Σ 2 1 Vyg(IKK yR) - 0y. < SC2 = 2n2 log 1+
+
log
2-
72
where yy for Algorithm Man and 1 for Algorithm
Proof Lemma C.2 The proof concludes by applying Lemma 16) with 7/s-1 = 1ly 1
V Vf(xs) Veg(z Lk. Wk). 9o Ky,k, a
0g.1, and no 77.00 n/7.
0
29

---

C.1 Proof of Lemma 5.7
Before proving Lemma 5.7 let define
nL? u
n72
df 1
!
C1
(um
+ + 7)(1 + log 7)
(24)
7
4(1 + 12/mmm/22
16
Am 1+
AT
1/=0² Br(o)
1/2
?
72
where A,),, (()), C1 C2 are defined in Lemmas A.I
A.4 and
C.2
respectively
Lemma 5.7. With probability least 1 46, for all S de
maxps:
1l
vkll S D, and
ykk viel2 I 12713 [4D2L2+ 10012+211 2Dy+ +2V2DOVI
(8)
1lyk - yill I ((VEDL+ Vt v2Dot
1
(9)
pm
where defined in Equation and o for Algorithm Aadd a 0g.1 for Algorithm
Proof of Lemma 5.7 Rolling single step of SGD,
|k++1 v2ll = |1y/ - y 2 20,, Wo. Uk yh) + vg 119
Since f(zk, :) is p-strongly convex, then
-2 (9y,k) l/ uk) 2n, (V VI wx.), yb v%) + & (V Fogg(a yx) Jy.kr We 21)
S 2umly 11 yAll2 + 27y. (V Vag( yk) Ju.ko yk vk).
Hence,
llux+1 - vil 12 S (1 2)mg.x)llvx= - yill + 277.k k (V (oK Meo - Iv.k. Us vi) + 1l..119..l1
By Young's s inequality and Lemma D.I
why.k 1
|l 112 S + myg.))) vill2 1
11 2ē11
$ (m vill 2(1 + (og.k)o.k (V Vog(EK. Mk)
Iv.k. Uk 9%%
+ (1 + p0y. (l (1
L2
122
Summing from = to 6, applying Lemma A.4 and using 7z S m// Vk.
18++1 - 11+ $ 11y1 - 21 x vill?
(1+ + po M7,
11 +
1²
R=1
L
+ 2
(Ny. + (ng Vgg(EE yk) - I9.ks 3k
vk2 +
122
k=1
k=
T221²
< 11y1 vil1
Σ wmy vill? (1 o)
(1 log T)
n22
2
+ 2
( wny (V Vyg mN) Io.ks 2k
(25)
122
pllyk
(A)
(B)
Bounding (A). In order to create a martingale we replace N9.6 = n/ G G2 +
11g 122 with
iy.k n//
G2 k + || Veg(z,, [ then
Mu.k (V Vog(zk. vk)) Do.k Uk (A1) Σ
vk)
n..k (V Vyg(#k. uk) -y.k. Uk -vh)
(26)
1=1
A=1
30

---

Ty.t )1. (Vak))/Vvg(aaaa 1=1
(o Mk) - go.k. Uk yk.
Observe that
VC g V ux)11 V Go - + 11 ?1?
My Vy,al = 11
C& g + 11 11? Gy 1 V Vuglerr 2/ )11
11 Vogg(ar yx)l12 11 112
S1 v Vo 2 11y Ce u VI un (F yx))11)112 (v C2 1A 11 / / B.8-1 + |1 (eg yx)) m=))
V1 V ue) Iy. (1( V 4 (v wx)l + (190,(1))
1
V G. + 11 V G2 v + v )1
G -. + 119 + v G9 n.h-1 + Vog(Ik yx:)
[Vgg(Tkr gy
(27)
V G2 1 + 11sy.all2 C0 - + V (F
Thus,
My.k - yg( yk) 90.ks Uk - yk) 5
(V
Ma.1
0g.k/l Vug(TKK - 9y.x11d,
1=11
k=1
dg
Mu. Vaglll Uke) - gv.kll
k=1
I1 Vog(( un) 2y.
ndg
G2 w-k- + 11 G - V1 (I Mx))l
km
de
Ty |I Vug -
(28)
k=1
Combing Equations
26 and
(28 with Lemma C.I
with probability at least 1 - 26,
d,
(A1) s
my V Vyglzn. yk) 9v.x
(29)
17
k=1
+ 2d,
Ar log((T))
Σ n2 V ( wk) g3.x 2 (o08/))g(4T).
Similarly,
(A2) = Σ N (V (V Vyg(rk) Mk) - 9y.ks - wh) =
T (V Vyg(#x, -
-y.k. Mkk
-yx)
(30)
km
km
Tly. - -ni (i. (V v.) - Iu.ks U2 vk.
Using Equation (2
Σ Uh - )2, (v o (xx, vk) - gy.ks Uk - vk) S
Mg.k + mo IM - fy. Vyg(gkr. yk) 9v.x
R=1
k=1
$ 2ny odg
Iyy - My V Vyg(zk. vk)) - gy.bol
IV
Vyg(Ek, (k) - 11
< 22 undd
Ge p + 11 GGak- + V (xg yx)l
31

---

21y..0
yg V VTg(TK. Mk)
9v.k
(31)
Combing Equations 330 and 31 with Lemma C.1
with probability least 1 26,
(A2) 2pmyoode
Ty.k V (IRK yke) ly.
(32)
"
22 A.(5/ log(T))
Σ 1 V 9y.k 1/g,002,((0/ log( log(4T))
Hence, due to (A) S 2((1) 2(A2) and Equations 29 and 32
with probability least 26,
(4) 2(1 + 24my, dd
1y Vo Ukk) 1y.x112
+4(1 + pm7g,1) dd,
A log(47)) Σ VV y Mk) go.kil² 12 02 log(47)))
Using < /2/22-1022 + 12/2.
vk) smxel1)) )² d?
4(1 + 2 d (A)
Σ Mg.k-1 V Veg(
n?
16(1 um,
Ac(ō/ log(/))))))
Σ
11. ( B.(6/oo((()
kSt
d
4(1 + 22
112
Tg V Vyg(En, Mc) - g0.el12 +
n72
16(1 + pmy .)
A,(o/log(4T))
Σ
II Veglll/Vll(a..... uk) my +120000 o (7:(5/og((4T)
Ast
Under a union bound with Lemma
C.2
with probability at least 1 - 46,
d;
4(1 + 2pmy,o)
1
(A) $
+
+ 16(1 + mny.o)? (Ac(6/ log(44))) + o2 log (og(())))
2
4
d
4(1 + 4um
1
+
+ 16(1 + mny.0)2 (Ar + 00 2 Br()))
4
Bounding (B). By the definitions of 7x and f3.
V22 2 + Σx ===1 11
na
7a
(1+
Σ
<
(33)
k
Mank
k. a² + Dmm 1192.0 I2. + 11 2
nia
m( + 7)
(1 +log T)-
(34)
1
Then
1
me.k
I2 7)
B
(1 + log T). 3
j.g.
k=
Thus, returning to Equation
25 and using the definition of D, with probability at least 1 - 46,
L
L'm2
(1 + log 1") + L²n(a + 7)
dun <
+ de
+
01 + 42
(1 + log 7")
2
3
32

---

4(1 + 2pm
r²2 +
+ 1-16(1 + pmg,0)² (Ar(6)C2 + n2 Br(o))
4
d
D 2
(35)
We induction show that with probability at least 1 48, df D for all 1 S +
Note that for t = 1, di = di < D Assume ds S D2 for all k I t < T; then for k = = 1
di+1 I d + D2 /2 S D2 due Equation 35). Thus, d+++ max ( d d D
We proceed to prove Equations and (9. Rearranging Equation 25 de S D2, with probability at least
using Equation
35 and
46
d
D
ul
vEll =
+
D2.
D2.
(36)
2 2
1=1
Using 14, Ty,t for k S t
D
DV +
DV
+ 2024 - 21 Ek=1 11
1B8k
vill2
pllyt
107
1=1
D 2 + 20²t
V2DL
Σ ya -
where the second inequality uses Young's inequality and Assumption 3.1 and the last inequality is due to Va + S Vā vb for a, b O. Solving the inequality gives
1 ( V2DD+ + v D p7+++ (1++V
1lye- 1E12 um
which implies that
1
v 12ll <
[AD2L2 +DD 2v2DoVi).
122722
and
1 v Vt
ly will S
Σ
1uu
V2DL+ + D (r v2oVi)
Lmd
k=1
1
((V2DL + vDT) V + v2Dot1/4.
<
pm
D Analysis of Algorithm 1
D.I. Technical Lemmas
Lemma D.1 ([50, Lemma 4.3]). Under Assumption 3.1 3 (z) is L/p-sihch and ((x) is (n smooth.
Lemma D.2. Define & = m, VQ(2,), c Vnf(z,, v.) v2(x,), and e, = Izzt vaf(Er))))
Further, let S. = ( V For all 1 2 1, it holds that
& B21d1 + Σ B(11)).0kk
8(+1))
Σ Sk
k=
k=2
33

---

Proof of Lemma D.2 The proof follows from a straightforward calculation:
& m, (Z+)
-1 + (1 31)9x.t (
Be(éi-1 ( (1 Be)(e + c, + Vb(xz)) v
Bi (1 32 (1 - - B,St.
Unrolling the recursion and using 0₂ = 1 - 5, yields the result.
Lemma D.3 (Descent Lemma). Under Assumptions
3.1 and 3.2
define & == m4
(x)(2,), then
((x++1) S (x1)) M/,, V Mlell (u+ + L)
2/
Further, define A = ((x)) 4², taking summation and rearranging we have
T
ne Ileell + (μ + L)L
T Σ
Ma (b(x:) v A + Σ
2/r
1=1
D.2 Proof of Theorem 4.1
Before proving Theorem 4.1 us define (recall the definition of HG and to in Equation Kig 0z/gz in minimax optimization)
here
A = =((x1) -4, to max { 2,8 (32x² 30x² + 7) log
60 601og(67)
(37)
8
Cm A 4n0 (Vlo- (Vlo-12 - 1- 1+1 (1 [1 [1+22 2/ 2//02/1))
(μ + L)
(1 log
24r
+ 2// + 32 32log(2T
(16- 110-1+ 2evto - -2 (1+ 2/22//2 2/0z/a)
Tx + a
4(u + L)
(to (10-1e (1+2V0 + +elvFo + 2n5 log T'
1
n(a n(a+7) 7) (1 (1+10g
LDV
1(0x 0)
(38)
1
2nLD
((to - 11) 2(to -1)
2) (1+2/ /z///
3
2Lx
1 For (1+2 (
(2 (V22DL+ VDz) + 22Do + log (T) I(ax > 0).
p0Zz
Theorem 4.1. Under Assumptions 3.1 and 3.2 and the parameter choices in Equations
and (4)
let o₂ = By then for any E (0, 1/ TT. it holds with probability at least 78 that
T
Cm T
L
(4(())) v
a²
+
(AD2L2+2DD)
T
VT
12122
1/4
22/222 Do
(502) 1/4
+ T3/6
12112
71/4
where Cm ((()) and are defined in Equations and 38 respectively.
Proof of Theorem 4./ Without loss of generality,
we assume to is integer (see definition in with probability least 1 78,
Equation 66) By Lemmas D.2
D.3
G.2 and
G.3
(μ L)L
nnd vo(x:)] SA +2
nn lell +
2/a
34

---

3 A +
Σ
T
32lllēi1| +
Σ
+
Σ
B a
+ + Berll + (u L)L
Σ
T
nz
21
1=1
k=2
1=1
$ A1 + 2
Σ
T
1)t
/2ell611+ +
Σ
Bkot ||&all| Σ
+ +2 n
Σ
91441)
(0+ + L)
Σ
T
12,0
2
2/c
1=1
k=2
k=
t=1
k=
t=1
(vio- -I 1 1-11-11 tevio (1 (1+2Voz/a)
(n + T,)
$ A + 4npx
(1 T)
24
+ 20 1 + +22 (og((2/0)) (10- 110-1+2ev ++2eell - 2 2/m (1 (1+ 21+2v/o (oVoo/a)) ) ox + +3 a log log T)
4u1 + L)LD²
(6-1+e//ri (1 (1=2/os/a) + elvrro + 2 log T)
1
+
V.V.
(1+10g T(ō =0)
2n
(11o - -1)3/2- 1) + 2( - 2) (1 (1+2
(1+2/0//a
3
2La (1+20 250 (1 (1+2Voz/a) (2 (V2D+++D7) + /2Do (1 + log T)) I(0= > 0)
+
HLx
Cm.
Then, using Ta na for S T,
Mr |T ((x))) S Σ No (V/x)\ S C..
Therefore, by Lemma
5.7 with probability at least 1 - 78,
1/4
Om
COVT
2
[o(+))l V
a²
Σ
I1
-e.e11 + llsvell?
TM.T
naa
Cm WavT
T
1/4
a= + 400 + oT + 1,2
Σ
1lve - yt 1|2
t=1
Om
I
1/4
2 a2+ 46 TT + +0 oT +
4, 2D + 2DDy+2V2D00 22V2DaVTT)
WavT
1121p2
Cm
1
p22p2 UDLL2++DD
L
1/1
22/222 Doy 122112
+ T (452 + 02)
1
a +
+
Wa
T3/6
Setting og = og completes the proof.
E
Analysis of Algorithm 2
E.1
Neumann Series
For bilevel optimization problems with lower-level strong convexity, we estimate the hypergradient (x(x)= = VzJ(x, y" (x)) - V y (x))] oe v ( V
via the Neumann series approach 22
(z V, y: G(r,y: (0) Hyy VgF(2,
(39)
where the matrix Hy defined by
V2 My
G(z yr c(m
H 1g,1
(40)
1g.1
n= j=1
35

---

and the set of random variables & is defined as ..... Ç : ( _ ( D) with (1²) = (5(m.1) ((am)) for 2 0.
In addition, define the gradient approximation of + as
f(,,,) fz v) va V ( y) -/- (v,
(41)
E.2 Technical Lemmas
Lemma E.1 (22 Lemma 2.2]). Under Assumptions 3.3 and 3.4 we huve
lV <=))))] Lylly x" (z)ll,
l1 (x1) V" (22)) Ly | x2l1,
(v1) (+((2)) & Tr x22l.
where the constants Ly, Lys LF are defined as
1.11
+ 1000
1022 + 19.1
1..1
f == 4,11 +
Tug
(42)
Mg
Hg
Mg
Hg
1 + Ls)
4.00
(1.22 +
LF = 14,1 +
(43)
Mg
Mi
Hg
Lemma E.2 ([2 Lemma 3.2]. 34
Lemma 1D.
Under Assumptions
3.3 and
3.4
we have
| S [yylll S
1
[[ bv,l(,,)]
E[HHyull
Mg
Pg
l
2 (1-
N
(V - E us Ill
1gg
Lemma E.3. Under Assumptions
3.3 and 3.4 we have
1,00002
21 1(0g,2 * 0) +
[V E: - E[V E)ll S 0s = =0
+
(44)
M4
M4
Hg
Proof of Lemmaa
E.3
By triangle inequality,
- ((x,
- - ( ( -,,,))
< [}V,F(,,);E) - V + 1V G(r,
- Veno(e ((,
+ |/ my (x, v) vy - F H wy V (( 0 + V2 by | (l v v))l)))1
By Assumptions 3.3 and 3.4 and Lemma
E.2 we have
x. 3: v=f(x.v)) 5oz-
and
(V my G(r,y: (0) V
< 1 G(I,y: 11 1,00 Fg
and
2 22yg( (z, 1) -[
20
1100,22 + 0),
and
1g.103
2 22 (V, F(.,v:
(r,(r,)))
Mgg
Hence, using the definition of T as Equation
44
we obtain
1.00
21 2
10,101
|V ( EVVS(>, 9i S oa Fg
(0 + 0)
Fg
Fg
36

---

and e, 9r,t 119,1 Further, let (2 (2(2)). For all z holds that (z()))
Lemma E.4. Define & = m, ( c Vf(x,, (z))) c== E1-11ge,11 fxr, yc).
é =32 +
Σ
Σ B1+tTa
Σ B +
Sk.
k=
k=
Proof of Lemma
E.4
The proof follows from straightforward calculation:
& = m4
(x()))
B1m4-1 (1 9e)92,t (2()z))
Bi(0-1 + (( + (1 9c)(c c V+((:)) (
- (1 f: (1 ( + (1 - 3:) B.S,.
Unrolling the recursion and using 0g = 1 - 3, yields the result.
Lemma E.5 (Descent Lemma). Under Assumptions
3.3 and 3.4 define m VD(21).
then
LF
((1++1) S (xx) 7 (+(x))) 2 12,1l
2
Further, define A = ((x1) 4², taking summation and rearranging we have
LF
T
ne Vo(z))) S A1 + Σ na |& +
E.3 Proof of Theorem
Before proving Theorem 4.2 let us define (recall the definition of Kig, lo, and σ in Equations (6) and 44 here Nig 0 ao in bilevel optimization)
660 (00log(6))
}
A (xx)) - 0³ to max 2,8 (32 - -30x3 7) log
(45)
Lpnp
C. = A + Anjō VVo - + tevio
(1 2+22/0 (22/00/1)
+
+ (1+1og7) T)
2
+ 20/ 1 32 log(2T/8)
(16-1+ +2Veo - 2//F. Ko
1 2 /o/la
os + a
+ 4Lrn/
10 10-1-+e 1evroo
1+2 00/01 + +elVKo + 2kxo) log T
20, + [,,DD/
m(++7) (1 + log
T(ōØ T(oØ=0) =0)
(46)
3/4g
DD
((1 - -1)3/2 2(10 - 2) Die. (1+2 2+22/0//a
+ 2
1+22 (1+2 10/0 ))
(2(V2Dl,,) + VD) + gD + log T))
I( > 0).
Theorem 4.2. Under Assumptions'
3.3 and 3.4
4and the parameter choices in Equations 3 and (4).
for any E (0, 1/7), choose N Z 2log(1/ 3log(1/11P5//,n)) P3, it holds with probability at least 1 75 that
3log
T
C
L2 a +
1/4
vo(x))) <
VT
p2ip
2 21 Do
1/4
+ T1/4 (40g + o2 o2.) 1/4
+
T3/8
122
where Co Ō(Kt), D. and og defined in Equations
(24
44) and (46 respectively.
37

---

Proof of Theorem 4.2 Without loss of generality, we assume to is an integer (see definition in with probability at least 76,
Equation (6). By Lemmas E.4 E.5
and
G.3
LF
72 (d(ill - A +2
ne +
2 Ns,t
t=1
t=1
1
A
Σ
11,,1
B2sll +
Σ B(++1):CaRE
+
Σ
B
k=
I.
T
+
Σ
+ +
Bkeell Skill
+
Σ
Nzst
2
k=2
[=1
< S + 4n0 (vlo= - 1 evi Krr
1 [1 (122/00// 30/la)
+
LEn
(1 + (1+1og T)
2
(( 10 - 1 2//ro
+ 20V 1 + 32 (og(2/7)))
(1 2 11+2/0011
0o + (og
+ 4LF
10 1
[+ 1122/001 20/0
+ +elVKo + 2xia) log π
2/210/22/
(1- (1-1))) 1g,11
N
+ [ (1,D//
ma++2) (1 + +og T)
I(āp = 0)
3/gg
LD ((to - -1)3/2 1) 2(to- -2),, (1+2/00la (0/0
3
2
(1 (1 (1+2 (oo/o//aa
( + +DT) + g, (1 + +log logT)) Maa > 0)
+
CC..
Then, using Ba 2 B, for ST
T
T Nr. V V s Σ No. (2((1)) S C..
Therefore, by Lemma 5.7 with probability at least 1 - -75
1/4
1
C. CLVT
[o(x:))
S TnN,T
a²
11
0r.el1 + |log.el?
T
n
t=1
1/4
Co
a² a2+44%% T + 02
12
11ye vi 122
WavT
9.1
1=1
1/4
Co
p2 9.l
a² a +o2T + 22
(DD21g 9.1
2Dy + 2222Do.. IVT)
11292
a/aa
C.
VT
1
a²
22q22
12
9.1
(4
9.1
+ 22x))
1/4
+
73/8
1
22/22, Do
12212
1/4
T1/4
1
(45
+
0g,1)
) 1/4
F Linear Programming Basics
Definition F.1 (General Form of Linear Programming problem can be written as
3
Section 1.1]). The linear programming
min zER
c Jar
(47)
s.t.,
Ax 2
38

---

Definition F.2 (33 Definition 2.1]). A polyhedron is set that can be described in the form
{a R Ar 2 b). where R2 is matrix and I" is vector.
Definition F.3 (3 Definition 2.6]). Let P be a polyhedron. vector P is an extreme point of P if cannot find two vectors y, P, both different from scalar À E [0, 1], such that I Ay + (1 2)
Theorem F.4 (13) Theorem 2.8)), Consider the linear programming problem of minimizing cf x over a polyhedron Suppose that has at least one extreme point. Then, either the optimal cost equal to -C, there exists extreme point which is optimal.
Lemma F.5. Assume 9t S aq S Or and 0 S 3: B. S Br. Further, let & E Rd and denote
Thtt = a Tk.t = 1k+1)): and Iktt = ( There exists set ( with each Dig, satisfying either Viz Pilli or big, = Ni, for every pair (i, such that
ΣΣ
mer & )g)
=
1=
Proof of Lemma FS
Consider the following constrained optimization problem:
ΣΣ nh
max
Tt
(48)
1=3 1=2
s.t.,
0c a S ai,
B.SB.
Vi S t.
relaxed version of problem 48 is:
ΣΣ (e
max
(49)
i=3j=2
s.t.,
26 S ni S Ri,
St.
Moreover, problem (49) is equivalent to:
min "
(50)
$= 1=
s.t., 26. S ni S
Vi
Now we proceed to verify that
(a) A relaxed version of Equation 50 namely Equation (53 is linear programming problem of minimizing of xr over a polyhedron P. for some Gr, Tz, Pr:
(b) Pt has at least one extreme point;
(c) The optimal cost of Equation (50p is not equal to -o0.
Fact (a) We first define few notations. Define Cijy Tight, bis big,e and the index set I,
Cj - (ei, G/),
Tija Th. Yii
bija = Nale.
bys = Ta.
Ie = 3
Let x, Pt be defined as
C32 : C((t-1)
132.2
a = (=(c))igeee
Zt = (Znt,))( =
P-= fat
A 2 bc).
11(t-1))t
(51)
39

---

where A,, by are defined as
ba2
1),
b. = (buse)aaNEE.
A.
b,
bp
b32,4
be(t-1),4 1),f-
(52)
According to Definition E. the optimization problem in Equation 50p can be relaxed into the following linear programming formulation (with potentially higher objective value):
min c, 24
(53)
s.t., A 2 by.
Fact (b) We will show that the set of extreme points of Pt is
S, {
(182. 12,1) T Dige bige Dij, big.t for 2 2 <ssiis]]
(=) Let 24 = [bšz, 11, T S. Check that A, 2 b. thus क, E P.. Assume there exists 2, E Pi (both different from 2τ) and a scalar À E (0, 1), such that Ay + (1 -1-10 A)z. Note that least one element of y differs from the corresponding element in 2₁, denote this element by Uej. where (i E I. We consider the following two cases:
If Vij Fej.t bij,t, then
Zig Zij.t AWaii Zij.t
bij.t-
1-1
This implies that 2 & Pt since A E bi.
If yij < Tija bij, then
Zij.t XWAi
Zig 1
Dij, bij,r-
This implies that & Pt since Ar= z b..
Therefore, & Pt in both cases. By Definition F33 We is extreme point of Pt.
( (=) ) Assume there exists some Fe E Pt such that oe & Sc. Then there must be least one element of 2t, denoted by Fij.e, satisfying Tijat # bija and zijat * big. Let y, and differ only in the ij-th element, and define Vijs Zig as
Vi Zij min { bije, bej.r Iija] and Vij -zj, min (ziga big.t bige Wej.z
Then y, z P. since A.y 2 by and A,z 2 b. Note that x. (y 2)/2, hence by Definition E3 We not an extreme point of Pt.
Fact (c) is finite, then
). <
ΣΣ
i=3 2=2
3=3 1=2
1=3
Hence,
The m.C.ele
Combining Fact (a) Fact (b)
Fact (c) and using Theorem F4
we know that there exists extreme
point x E S such that
bi (- (())))))) = cTaj < cJ x
Wa (-(r)((((rr)e)))
40

---

Therefore, for problem 53
fet Ez).
3=3
2=3
We conclude the proof by noting that problem 53 relaxed version of problem (48)
G Useful Algebraic Facts
Lemma G.I. Let p E (0, 1] and 1). Further, let a, b E N22 with S b, and c, cI 02 0.
(a) have
b II - (1+ S
bc) -1
exx
c(1 4)
t=0
(b) 1fp q and 01 C2, then
Σ (1+ cit) 1/2 1/2
II (1+k)))))))
4/2
(1+a0))
(1 + (a - -1)022
$ 6
(a (a-1) 11 (a 1)02) exp
22 - q)
(c) Ifc 02 and (p q) + (a 1)c2) < 1/2, then
(
Σ (1+ II (1 (1+ 2 k=t+1
(1+ (b ()++))))-
02(1 - ②)
Proof of Lemma
G.1 We prove the results individually.
Lemma G.1(a)
Using exp(-2) and the monotonicity of (1 ct)
b
1/tt (1 cl) cl)
b+1
- (1+ +1) s exp
E (1+ S sexp
1
c(1 (1-9) ((1 + ac) 1-9 (1 + (b + 1)6)
exp
1
S exp
((1 + ac)) 1- -- (1 + bc) 9)
(0)
c(1 - q)
Lemma G.1(b) By Lemma G.I(a)
(1+ II - (1 c2k)
(1+ (c2)) (c2)) 1-9 (1+a0))*
b
(1 + cit) 9/2 (-(1+ c21)
Σ
I exxp
c2(1
Cz(1
1=a
Using the monotonicity of (I + -/ -//2/ exp
(Itegt)l-g c2(1-9]
and Ci S c2
Σ t=a
(1+ 1/2
- 1- < 1
(-11+ o2t)
p
(1 (1+ctt) 9/2 1/2 (0
(11 c2t)l-g dt
c2(1-10 -
a-1
41

---

"
(1+ c2t)
(1+ cst) ( 1-9
(1 + c2t) 9/20- (2 exp
dt
(1+ cittu/2
02(1 9)
0-1
bo2)
[1+ 022) 12
(1 + c2l) 2/ c21)
c2(1 (2 9)
dl
(1 bo1)0// )o/2
a-1
0 1/2
(L (=+22))1-9
(2l) 1/2 1 exp
dl.
C2(1 - ②)
We continue to bound term (I). By partial integration and q.
(1+ (a 1)02))=-9 (1=)))))))))
(- (1+ bez) [1+bb2)
I= (a - P) (a - 1)02) exp
6b= + bo2) exp
c2(1 - 9)
C2(1 - 9)
a-1 (1- { - pez + -02)
(1 (1+ +22))=111 (1 + c2t) 1122 Pexp ([(+
exp
dt
2
c2(1 -q)
(1 + (a 1)02)) 1-9 1)02))-11 )
(1+ + bc2) boz) 1-9 02(1 9)
S (a- 1) P(1 + (a 1)cy) exp
bb + bc2) exp
c2 9)
-(h 1 + pc2 qC2
(1 + be2)
/"
(1 c²t) 0/ 8 exp
c2t) c2t) dt.
.--1
02(1 4)
Rearranging it yields
(a 1) + (a- 1
1/22) (121) exp
(L+(a-1)eg)) -b-(1 bo2 90/ exp
(1+bey)'
c2(1-9)
c2(1-9)
1+
f + pc2 2
(1 + bo2)
(1 (a (lc-1)c=--4 1-9
(1+(m=))c)--
(a 1) (c-)))o00
c(1 (1--)) 9)
Thus, we obtain
(1 (1+ 1-9
C2 9/2
Σ
att=)t 1/2 II (1 (1 (1+c2)) S exp
c2(1 - 9)
C7
1=0
k=
9/2
(1+ 1-1
(1 + (a 1)02)²
(a 10 +1+ (a 1) exp
C2 (1-))
Lemma G.I(c). Using - x S exp(-x))
b (1+a)t) II (1- (1 c2k) s
S exp ( -1+
[u+cctt)Pessp
Σ (1 +1 (2)+)))
t=o
k=t+1
k=1
Using the monotonicity of (1 + c2k) 9, we have
s cxp (-), r+1
(1+ (1+ (b+ 1)02)²
exp Σ (1 + c2
= -exp (1 (2k))
C2 9)
1=1
and
eexp (f((+ (1+ c2k) Tckk < Sexp
(1 (2+22))²-
Σ (1 + (2g)))
exp
02(1 - 1)
P
Due to 01 S C2 and the monotonicity of [too?)
we continue to bound
b
t
(1++
Σ (1+
Σ (1 + (1+c2)) c2k)
< Σe (1+c)t)PPas)
(11+g(11))
c2(1-
42

---

c21)
(1 + P
c2(1 - (_ea(1
(2))
ci 1)p
(1 + bo2)
(1+)2t) 1-9 -1
Σ
(1 c2t) (2t) P exx
(1 bei ) t=a
c2(1 9)
p Σ
(1 (1+c2t) -
(1+ c2l) (1+
Pexp
C
C2(1 9)
Ama
Denote htt) as
(1+ +Lt))))²-
h(() = (1 + p exp
C2(1 - 9)
By simple calculation,
(1 cgt) 1-9
-1 c2t))_g-1
h'(t) (-po2 + (1 +1t 9)) (1 + -2 p-1
exp
C2 -4))
Define f as
f (pc2) - -
C2
Note that h(t) monotonically decreasing for t S t and monotonically increasing for tl.
If 112 S a, then
(1 + (1++2))PPex)
6
11+ c2(1 -1 c2
(1
/
b+1 (1 (1+ cxp
(1 (1++ dt.
$
c2(1 - 9)
a
If S 1 < b, then
b
(1 + c2t) (1+2)))-0-11 02(1 -9) 4)
[t
(lt)
Σ + (2t) -
(1 (2t
C2(1 - -q)
t=
[t]
b+1
(1+ (2)
(1+ (1+) Pexp
dt
C2(1 - 9)
b+1
(L+ (2+c2t)²-
(1+ exp
dt.
c2(1 9)
a-1
If 4 2 b, then
(1+ (1++21)) (1t C2(1 - 9)
I" (2+ Ja-1
(1 (1+ -1 dt.
(11) exp
C2(1 - 9)
Therefore, based on the three cases above,
(1 c22) (1+ Σ (1 + -2t))-Pepp (
b+1 (1 (1+ c2t)
( dt =:
C2(1 (1 - 4)
02(1 - 9)
a-1
We proceed to upper bound the integral l'. By partial integration and (p- (D-q)(+(a-11)o)) < 1/2.
b+1 (1+ + (20z))
(1+ + -21))-9-11 1 dt
I'
P(1+))2 c2t)=22)0) exxp
02(1 - 9)
a-1
(b- (1+
(1+())))02)-- -11 1)
(1 (a - 1)c2) (1+ (a - 1)02) (1-)))1)))---- 1)
= (1 + (b 1-22) cxp
c2(1 - 9)
c2(1 - 9)
b+1
(1 12())-19-- 199 dt
+ (p - 4)
(1 + c2t) exp
cz(1 - 4)
0-1
43

---

(1+ 1002-11)))0---1110
(1 (a 1)02) 1-
< (1+ (1+))))))) exp
(1 + (a- - 1)02))
c2(1 - 9)
c2 9)
b-1
(1 [2t)² - dt
+ + 9) + (a- - 1)02)
(1+ e2t) P
C2(1 -=)
a-1
9)
(1 1)02) ()022)=-1-1 (++1+)0)))
(1 + (a 1)02)= -
S (1 (b+ 1002)) exp
- + (a 1)02) 1 exx
C2 - ②)
C2 9)
(1 (1t22))1-911 dl.
+ 2 2/ a-1
(1+c2l) exp
C2(1 - 4)
Rearranging it yields
(1+ 1)c2)) 1-9 (1+
1' s' 2(1 + (b+ 1)02)9
c2(1 - 9)
Therefore,
b II (1- (1+ + c2k)
(1+ P
k=t+1
(1 + 02) ) (1 + (b + 1)02)
(1 (1+ -
eep
Σ
(1 + o exp
c2(1
C2(1 9)
[=
(1 +1+c2) 02) 1-9 (1 + (b + 1)02)
exp
r'
c2(1 -
02
(1 02)
1-9 1
$ 2
(1+ (b + 1)02) 9 exp
C1
22 1 ④)
Lemma G.2. For all t 2 1. let ar Be The and Ri be defined as in Equations (5) and (6):
α
TV
10/0
@ > 0
01
B. = ags
ne
Vi
and
Kig
1
σ 0
ua² + k==1 11 5x112
Then with probability at least we have
(a) For to Σt Ba:t /ir ((a- 103-1222/0//(aa111
(b) Σt= 11:32. 5 2n
(To -I- (1+2v07a))
(c) Σt M1 Ek= 32
(1+1):t a
S 1) (0 - 11 22 to -2/Ro (1 (122/0/a) + +3 log 1(0 > 0).
(d) Σt= Tht 2km2 mh - BBae S 2n² (lo- -001 1)
Et
(1 (1+2 (1)--1(1+ (1+e/Ro
+ ee(fr, + 2x log T).
(e) ΣT. &h S () log
Proof of Lemma G.2 We prove the results individually. Without loss of generality, we assume to is with probability at least - 8, we have o; S aa S āg and 3 I B - 3r_
an integer. By Lemma 5.5
Lemma G.2(a) Consider the case where 0 < g S G. Apply Lemma G.1(b) with = 2 to. b = T.
p= 1/2, c 8² g²/a², and C2 45 //2/a²
T
2
1/1
V1 4002 / + 4(a 1)02/0²
Σ Bart S 1 (a- 11/2 1/2 1+ a
(a (0-1) 1))
exp
20 /22
1=a
44

---

I 2 (a (a- 1)-1/2 (1+ + 2//0/ 1)1/1) exp(1)
25 ((a 1)- (a- + 2 ///0(( - 1)-1/4) s enjevKo (1 + 2 +++V///)
where the second inequality uses (1 + x) 1/4 < - x 1/4 and the last inequality is due to 2 to 2 2. The bound also holds for the case where g
0.
Lemma G.2(b) Apply Lemma G.2(a) with = lo.
T
Σ t=to
nrBre S 27jev Ko (1 (1+2/8/a) (to - 11) < Fo (1+2/5/a)
Hence, using 7/t S / and 3e 1,
T
4-11
T
T
m
B21
n n2:2
+
Σ
n1.2a S 21i(vtu -1 - 1) +
Σ
Te
1=1
1=1
to
t=
S 2n
Vto - 1 -
+ en Roo (1+2/0/a)
Lemma G.2(C) Consider the case where 0- <0 S σ. Apply
Lemma G. (c) with a = to, t.
p= 1, g 1/2, C1 = d² /a², and C2 40 /a²,
12 0²
4 (t (t+
-1/2
VI+ + 102 402
Σ (KP(k+)) S
1+
a²
exp
25 25²//a
Ammo
472
-1/2
452
-1/4
12ex2
1+
-1)
V12eni
1 2t (t+1)
az
Using the definition of Th-
0²
-1/4
1/2 (
472 (1+ o²
-1/4
Σ Th t=
B2
(et1)a
o
S 1
1
a
(1 1)
k=to
t=
3 Veno
S 31/ log
00
t=
Thus,
to-1
(k+1)a of
1/1
1k+1)=
a
+
The
a
k=2
tmfo
7
T
1
VI
1]t
(h-
1)r
ot
+
B
1=1
t=ta
A=
k=
T
T
nto - 1) + vto - 2
neB
+
32
1k+ ot
1=10
1=tp
k=
s </1 - 1) + 20ee - -2/Kia (1+2/0/0
+ +3IVeksa -1 log T
n to 1 1-22++2tt 2e-2ett
- -eevoo2240 2 (1 [1+2 2 0/a)
+ +
where the first inequality uses n S n/Vt, the second inequality is due to va va+b5 S Va + vb for a, b 2 O, and the third inequality uses Lemma G.2(a)
For the case a = ā = 0, we have ar = 1 and 3, = 0, hence Σt= my Ei
B B af =
45

---

Lemma G.2(d)
We have
T
to-1
1
T
118
1 BRat
Bact
+
Σ
1/t
T/K-
Bkat
2=
t=1
k=
1=
k=
to
{-1
to
T
v
11
Vk
+
1)t
T]k 1 Best
T)t
Σ m 1 13at
k=1
h=
t=
k=tu+1
s 2n 1) + ntt
1)
Σ
Begit +
Σ Σ
1kat
1=/
t=to
k=
T
s 207 - 1) + 21) e(to - 1o (1+2/0/a)) +
Σ
T
Σ
1
t=
k=t++1
where the first inequality uses Y)t S n// Vt, the second inequality is due to Y) S v, and the last inequality uses Lemma G.2(a) We continue bound the last term above:
T Σ
Σ t=
7k 1
Σ
Σ
kmta++1
to k=t++1
k=to+11
tm
2nevKo Kog
Σ
1/--1 ((k- 11--1 2 (/1a(k-1)-1//) 1)-1/4)
k=ta-1
T-1
< 2ne Kg
Σ
+
Fook
Kork
k=lo
S 2n e No +2/ log
where the first inequality uses Lemma G.2(a) and the second inequality is due to m) = /// Vi 7/ Vt. Therefore,
Σ T 1 s 20/ (l e(lo 1)Voo (1 (1+2///a) + e(Vroo + 2xx log
Lemma G.2(e) By the definition of n/ and the fact that ag 1,
r² S log t
Σ
mh
Lemma G.3. For all t 2 1, let or Br, and na be defined as in Equations 33 and (4) (see Sections 4.2 and 4.3, and let et be defined as Lemma D.2 for minimax optimization and in Lemma E.4 for bilevel optimization:
Vef((ze v4(z)) VV[ v.) V
(minimaxx (bilevel)
B, = at Ef
at
Va² + Ek=1
11 In
and Na.t 1/
d
a
a2 + + 11g x1 + 119
vt
Then with probability at least 1 - 48. we have
n(a + 7) (0++7)(1+(0)) (1+ T)
Σ nrat
Σ 1(
LD
I(ō, = 0)
46

---

2DLD
(too-)3/22 - 1)) 2(to 2 2)LDne (1+ (1+ (1+2/ou/a)
3
vD1) + v2Do (ogg)+)og))))))) ()) 1l 20), 2La (1+2e ( (L+2Vo./a)) (2
udu
where (with slight abuse of notation for L) L L,
5z Ta 2z. By for Algorithm 7
and L -= -,1,,, Us. = Cs. 01 = 9.1 for Algorithm 2
Proof Lemma G.3 We consider the cases @u 0u and ou S u. separately.
Case Cu Ja 0. In this case,
and T) = TV
= 1,
30 = 0. o¹ =
α
Vi
Va² + Ek= |1
By Assumption 3.1
|&fl = V y1)
<D(x;)] - Ellye of ||. Thus,
T Σ n
T Σ
T
B(HDIaEEE P
The The anellane!!
Bll S L
nn 22 Il-
t=1
t=1
Using Cauchy-Schwarz inequality and Equations
33 and 36).
with probability at least - 46,
n(a + 7) (1 + log T).
Σ
na nelllve vēll
Σ
el 3/12 s DV
P
1=1
Hence,
T na.t
11aa + 7)
Σ
S L
(oglog T).
(54)
Case 0 < Tu Jw. By triangle inequality.
Σ Na,t
Σ BURtI)aa
$
Σ
No,t Σ
3 Qu+n)aakle > na Σ
B(rt)aaally. vill- -vil-
tm
k=2
k=2
Then with probability at least 1 - 46,
to
Σ T
3
31k+1):aullun
will
Σ nost Σ 304
vill +
Σ T/ Σ 11 11yx vill
1=2
t=o
tg-1
T
to
T
D
the +
Σ
Nas
Σ
B14t2):a1111 - VEll + Σ
ns Σ 3(k+1): - yill
1=1
t=to
k=2
t=
k=to
2nD
((to 1)3/2 - -1) + (to 2) Σ
Σ
Mxxt Σ B(04)) vill
$ 3
t=to
t=
Aato
2n
((to 1)3/2 1) + 2(to - DiD (1+ 11+2Von//r
Σ
nx,t
1(.+1aaakll vill-
3
t=to
k=to
Swapping the order of summation for the last term, and applying Lemma G.2(a)
T
Σ Nz.t Σ Bu04120all vill
vill
Σ
ne
Annto
k=to
t=k
Σ
vill
Ma,k
Σ
k=to
t=k+1
47

---

T
Ork 0x 1lyk - wEll
Tvak vk
+ +2ne voo (1 (1+ 2v /o/////aa)) k 1-111
k=to
n1
(1 + Rev Kro (1 (1+2/on/o))
Σ k k-3//1113 - -Vall.
0u
k=to
Using summation by parts Σ
ar
b(-1) = arbs anbb- -100--=11 (at+1 ar)be with ar 3-44
and be- = Ek= Ilye
Vkll-
T
k: 3/4 11ve -1 S 3/-3/4
3/4
11
V + Σ
(1 (/- - (1 1)-314
Σ
11 - Di
k
km
t=1
km
T
T-1
< T 3/4
T/33/4
Σ
1l wVell +
7/4
1g will
k=1
t=1
k=1
T-1 VVT) Vt + 22D0
1 T 3/4 3/3
((V2DL+ (VDDD++DD))) VT /2Do//8/4)
3
Σ 1=1
7-1 ((V2DL+ VDT)
+ 4pm
1
((V2NL+ VDT) T- + v2Doi) + 4um
(4 (4(VDD++ vDn + 22Dai + log
(d)
(2 (m]
2
(2DD+ DD)) + 22Do (1 + +og
where the second incquality uses t 3/4 (++ 1)-3/4 - 3t 3/-7/4 /4/ and the third inequality is due to 3/4
Lemma 5.7 Therefore,
Σ
T
Σ B
S 3 ((to - 11/3/2 - 1) + 2(to - 2)LDne (1 (1+2/oml0 0m/a)
21
1=1
k=2
2La
+ (I+ 20 Ko 1 1422ou//0 (2 (V2DL+ + + (2Dor(1+1og') (55)
Combining Equations
54 and (5p.
we obtain
n(a (1 I(ō = 00)
Σ
Nr,t
Σ
S LDV
1
k=
22LLD
+
((to- - -1)3/2 119/2-1)-0 2(40 - 2)LDne (1 (1+ 14-2Von1 om/aa
1)
3
2La
( (1+2Vo./a)) (22VVV+++ vD*) + v2Do + log l)g
+
I(a, > 0).
10a
Lemma G.4. For all t 2 1, let at Bn Ne,t. and ex be defined as in Equations and Lemma E.4 for bilevel optimization (see Section 4.3
3 and
B: at c²= Ex-1lgr.e V f v.),
at Va² Ei=
11 22,
and na,t a/
d4 =
a
a2 +
+Ek 11ge,t - 21 + 11 1
vl
Then we have
T
2 14.00100 (1
My N 1g.1
Σ nz
Σ
<
3pg
k=2
48

---

Proof of Lemma C.4
By triangle inequality and Lemma E.2
T
Σ
B(1+1)aa
B(
A=2
(1-12))
(1-
Hg
N
T
Bikttaa
Hy
9111
1=1
k=
1g 1.0
(1-
Hg
(t
1)
Hg
1
Vt
1=1
2// $
(1-
(1-
Ug
N
3/g
g,1
where the third inequality uses Ne S // Vl and or Bi
1.
H Discussion on Existing Algorithms for Minimax Optimization
minimax optimization, TiAda 47 is the only work that attempts to be noise-adaptive. However, their convergence guarantees in the stochastic setting depend only upper bounds of the stochastic gradient norm and the function value (e.g., Assumption 3.4, 3.5, and Theorem 3.2 in (77), rather than the actual noise level stochastic gradients. Consequently, TiAda does not achieve optimal convergence in terms of the dependency stochastic gradient variance.
Among existing algorithms for nonconvex-sttronlyy-coom
I Experimental Settings for Synthetic Experiments
For synthetic experiments, we tune hyperparameters for each baseline using a grid search and report their best results. Both the parameter a used in the momentum parameter estimate (3) and the
base learning rates (1z 1hy) are tuned within the set (0.5, 1.0, 1.5, 2.0, 4.0, 5.0). We use the
following parameter choices for various noise magnitude: for a = a 2.0, 7/- = =3.0, By = 3.0
for Ada-Minimax, and Л = 4.0, fly = 4.0 for TiAda; for a 20, a 2.0, 1/- =1.5, By = 1.5 for
Ada-Minimax and T/e 2.0, Fy 2.0 for TiAda; for 50, a = 3.0, 7/2 =2.0, 77 2.0 for
Ada-Minimax and 1)x 2.0, fl = 2.0 for TiAda; for = 100, 5.0, 7/e = =3.0, fly 3.0 for
Ada-Minimax and 1/2 2.5, T/y = 2.5 for TiAda. Other hyperparameters TiAda are set to
default choices suggested in [7).
Experimental Settings for Deep AUC Maximization
For fair comparison, we tune hyperparameters for each baseline using grid search and report their best results. The base learning rates (Ne Myy are tuned within the range of [0.001, 0.1]. Specif- ically, we select (Ne, my) = (0.1, 0.05) for SGDA, (0.01, 0.1) for PDSM, 0.05) for TiAda, and (0.01, 0.01) for Ada-Minimax. The exponential hyperparameters (a. 3) for TiAda follow the original settings in their paper, i.e., (0.6, 0.4). For Ada- ada-Minimax, the parameters (a, 7) are tuned within a E {0.1, 0.5, 1.0, 2.0} and E {0.01, 0.1, 1.0, 2.0}, resulting in the optimal choice (ar,7) = (0.5, 0.1).
K Experiments for Hyperparameter Optimization
In this section, we consider hyperparameter optimization on the TREC text classification dataset 49 provided under the Creative Commons Attribution 4.0 License. We formulate the hyperparameter optimization problem as follows:
min
1
Σ ((w)(A);
s.t. wi w²(A) (A) arg min
Σ SED.
[(w:()) + >
1201)1
D
Drr
DED
49

---

Training ACC
Test ACC
0.8
0.8
Vraining ACC
0.6
0.5
0.5
0.4
1780
0.2
1750
Ado 810
Ado 850
10
40
50
10
40
50
Epoch
Epoch
Training
(h)
Figure 4: Comparison of BERT model hyperparameter optimization.
where C(w; E) denotes the loss function, w represents model parameters, and is the regularization hyperparameter. Here, Du and Val denote the training and validation datasets, respectively. In our experiments, we employ BERT model with 4 self-attention layers, each comprising 4 attention heads, followed by fully-connected layer with output dimension of 6, corresponding to the six classification categories. The model is trained from scratch for 50 epochs. We compare our algorithm's 's training and test performance against the tuning-free bilevel optimization (TFBO) method proposed by [73]. For TFBO, we conduct a grid search to select optimal initial values for the upper-level learning rate orp, lower-level learning rate So, and linear system learning rate yp within the range [1.0 x 10-5, 10.0], and set them to (0.01, 0,1,0.0......... 0.1.. For Ada-BiO, we similarly perform hyperparameter tuning
the parameters (Ne Myy 0, 7) within the range [1.0 10-5, 1.0), selecting the optimal values (1.0 x 10-5 0.5, 1.0, 0.1) for evaluation.
The training and test accuracy curves are illustrated in Figure 4 TFBO fails to converge because is originally designed for deterministic scenarios, rendering it ineffective for stochastic settings. In contrast, Ada-BiO demonstrates rapid convergence terms training accuracy and consistently achieves superior test performance.
L Experiments for Verifying Assumptions
We empirically verify Assumption 3.2 ii), which states that the noise of the stochastic gradient satisfies
g, F(I, y: { - (z, y) ã. with Ø. > 0. Specifically, following the experimental
setup for deep AUC maximization described in Section 6.22 we compute the exact gradient VzJ( y) the entire validation dataset with fixed model parameters and hyperparameters. Similarly, we compute the stochastic gradient V. Frx, y: E but using randomly sampled mini-batch from the validation set. We observe that the empirical maximal and minimal noise levels are o, 210.71 and 0.21, respectively, thus confirming that practical stochastic gradient noise indeed bounded from both sides.
after each training epoch by averaging the gradients
50


Reviews:
[{"review_id": "eDRt7dWsa1", "reviewer": "Reviewer_pyyb", "summary": "This paper proposes novel adaptive algorithms for nonconvex-strongly-concave min-max and nonconvex-strongly-convex bilevel stochastic optimization problems. The algorithms achieve sharp convergence rates without requiring prior knowledge of the noise level. The proposed method combines momentum normalization with an adaptive stepsize scheme and shows strong empirical performance on synthetic and deep learning tasks.", "questions": "- I could not find the convergence rates for existing methods in this manuscript. Therefore, I could not compare the convergence rate of the proposed methods. Please provide the explicit form of convergence rates for existing methods.\n\n- Are the experimental results in Figures 1 and 2 obtained with multiple trials? If not, please conduct the experiments using multiple trials.\n\n- In Section 6.1, the authors insist that Ada-Mimimax consistently outperformed TiAda. However, I could not confirm it from Figure 1. Is the performance gap significant?\n\n- In Algorithms 1 and 2, the update y_t does not use momentum while the update of x_t does. Could you provide the reason?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\nThis paper proposes an adaptive stepsize scheme for bilevel stochastic optimization problems and provides the theoretical analysis deriving the convergence rate. The originality and quality of these points are sufficient. \n\nWeakness:\nThe experimental evaluation of the proposed method is not significant.", "was_revised": true, "final_justification": "I reviewed the response from the authors and decide to maintain my current score.", "rebuttal": "**Q1. I could not find the convergence rates for existing methods in this manuscript. Therefore, I could not compare the convergence rate of the proposed methods. Please provide the explicit form of convergence rates for existing methods.**\n\n**A1.** Thank you for your suggestion. We have included comparison tables for adaptive algorithms in minimax and bilevel optimization in Tables 1 and 2, respectively, where the assumptions and convergence rates of existing methods and our proposed methods are explicitly presented.\n\n**Table 1: Comparison of Adaptive Algorithms for Minimax Optimization.**\n\n| Method        | Setting                                      | Assumptions                                         | High Probability | Complexity                                                                 |\n|---------------|-----------------------------------------------|-----------------------------------------------------|------------------|----------------------------------------------------------------------------|\n| TiAda         | Deterministic [1, Theorem 3.1]  | Assumptions 3.1 to 3.3 in [1]          |                  | $O(1/\\sqrt{T})$                                                            |\n| TiAda         | Stochastic [1, Theorem 3.2]     | Assumptions 3.1 to 3.6 in [1]          | ❌               | $O(\\text{poly}(G) \\cdot (T^{\\frac{\\alpha-1}{2}} + T^{-\\frac{\\alpha}{2}} + T^{\\frac{\\beta-1}{2}} + T^{-\\frac{\\beta}{2}}))^{1}$ |\n| Ada-Minimax   | Deterministic & Stochastic (Theorem 4.1, this work) | Assumptions 3.1 and 3.2 in this work          | ✅               | $\\widetilde{O}(1/\\sqrt{T} + \\bar{\\sigma}_x^{1/4}/T^{3/8} + \\sqrt{\\bar{\\sigma}_x}/T^{1/4})$                      |\n\n1. $G$ denotes the upper bound on the stochastic gradient norm, and $\\alpha, \\beta$ satisfy $0 < \\beta < \\alpha < 1$.\n\n\n**Table 2: Comparison of Adaptive Algorithms for Bilevel Optimization.**\n\n| Method     | Setting                                           | Assumptions                                        | High Probability | Complexity                                                                 |\n|------------|----------------------------------------------------|----------------------------------------------------|------------------|----------------------------------------------------------------------------|\n| S-TFBO     | Deterministic [4, Theorem 2]       | Assumptions 1 to 3 in [4]           |                  | $\\widetilde{O}(1/\\sqrt{T})$                                                |\n| Ada-Bio    | Deterministic & Stochastic (Theorem 4.2, this work) | Assumptions 3.3 and 3.4 in this work             | ✅               | $\\widetilde{O}(1/\\sqrt{T} + \\sigma\\_{g,1}^{1/4}/T^{3/8} + (\\sqrt{\\bar{\\sigma}\\_{\\phi}}+\\sqrt{\\sigma\\_{g,1}})/T^{1/4})$ |\n\n&#8203;\n\n**Q2. Are the experimental results in Figures 1 and 2 obtained with multiple trials? If not, please conduct the experiments using multiple trials.**\n\n**A2.** We have conducted the experiments using 5 different random seeds. The hyperparameter settings and experimental details are included in Appendices I and J. See Tables 3 and 4 for details. \n\n**Table 3: Gradient norm $\\\\|\\nabla\\Phi(x_t)\\\\|$ evaluated at the last step.**\n\n| Method       | $\\sigma = 0$               | $\\sigma = 20$                | $\\sigma = 50$                | $\\sigma = 100$               |\n|--------------|-----------------------------|-------------------------------|-------------------------------|-------------------------------|\n| TiAda        | $0.0193_{\\pm 0.0000}$      | $0.1657_{\\pm 0.1052}$        | $0.5437_{\\pm 0.5332}$        | $0.9394_{\\pm 0.8541}$        |\n| Ada-Minimax  | $0.0163_{\\pm 0.0000}$      | $0.0555_{\\pm 0.0319}$        | $0.1198_{\\pm 0.1095}$        | $0.1644_{\\pm 0.1391}$        |\n\n**Table 4: The final training/test AUC with 5 runs.**\n\n| Method       | Training AUC               | Test AUC                 |\n|--------------|-----------------------------|-------------------------------|\n| SGDA  | $0.7435_{\\pm 0.0424}$      | $0.6970_{\\pm 0.0251}$     |\n| PDSM  | $0.7765_{\\pm 0.0050}$      | $0.7133_{\\pm 0.0072}$     |\n| TiAda        | $0.6127_{\\pm 0.0138}$      | $0.6152_{\\pm 0.0010}$      |\n| Ada-Minimax  | $0.9284_{\\pm 0.0252}$      | $0.7331_{\\pm 0.0196}$     |\n\n&#8203;\n\n**Q3. In Section 6.1, the authors insist that Ada-Mimimax consistently outperformed TiAda. However, I could not confirm it from Figure 1. Is the performance gap significant?**\n\n**A3.** In the regime where $\\sigma$ is large (e.g., $\\sigma = 50, 100$), Ada-Minimax converges faster than TiAda, with a significant performance gap. When $\\sigma$ is smaller or there is no noise (e.g., $\\sigma = 0, 20$), the gap is smaller or the two algorithms perform similarly.\n\nIn the revised version of the paper, we will tone down this statement to: \"Ada-Minimax outperforms in the large variance regime and performs comparably to TiAda in the small variance regime.\"\n\n&#8203;\n\n**Q4. In Algorithms 1 and 2, the update $y_t$ does not use momentum while the update of $x_t$ does. Could you provide the reason?**\n\n**A4.** Since the lower-level problem is strongly concave in minimax optimization and strongly convex in bilevel optimization, using momentum for the update of $y_t$ does not help improve the convergence rate. However, updating $x_t$ without momentum necessitates either imposing additional assumptions [1] or using large batch sizes to achieve sharp convergence rates, as shown in prior works [2,3]. Specifically, [2] and [3] require batch sizes of $M = \\Theta(\\max(1, \\kappa \\sigma^2 \\epsilon^{-2}))$ (see Theorem 4.5 in [2]) and $B = O(\\epsilon^{-1})$ (see Section 4.2 in [3]) to achieve $O(\\epsilon^{-4})$ convergence rate for nonconvex-strongly-concave minimax problems and $\\widetilde{O}(\\epsilon^{-4})$ for nonconvex-strongly-convex bilevel problems, respectively. These requirements are often impractical in real-world applications.\n\nIn contrast, incorporating momentum with normalization in the update of $x_t$ not only provably eliminates the need for large batch sizes on nonconvex upper-level objectives in both problem settings, but also simplifies the analysis of the lower-level estimation error. In particular, the shift in the lower-level optimal solution, $\\\\|y_{t+1}^\\*-y_t^\\*\\\\|$, can be bounded by $L\\eta_{x,t}/\\mu$ due to the normalization step, which is critical in establishing the bound in Lemma 5.7 (see proofs in Appendix C for details).\n\n&#8203;\n\n[1] Li, Xiang, Junchi Yang, and Niao He. \"TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization.\" In The Eleventh International Conference on Learning Representations, 2023.\n\n[2] Lin, Tianyi, Chi Jin, and Michael Jordan. \"On gradient descent ascent for nonconvex-concave minimax problems.\" In International conference on machine learning, pp. 6083-6093. PMLR, 2020.\n\n[3] Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Bilevel Optimization: Convergence Analysis and Enhanced Design.\" In International Conference on Machine Learning, pp. 4882-4892. PMLR, 2021.\n\n[4] Yang, Yifan, Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. \"Tuning-free bilevel optimization: New algorithms and convergence analysis.\" In The Thirteenth International Conference on Learning Representations, 2025."}, {"review_id": "QE2ay15npn", "reviewer": "Reviewer_TL2T", "summary": "This paper presents novel adaptive algorithms for stochastic hierarchical optimization, focusing on nonconvex-strongly-concave minimax and nonconvex-strongly-convex bilevel problems. The proposed methods achieve state-of-the-art convergence rates without requiring prior knowledge of gradient noise levels, overcoming a key limitation in existing approaches. The technical innovation combines momentum normalization for upper-level variables with a carefully designed adaptive stepsize scheme for both levels, providing the first theoretically guaranteed noise-adaptive solution for these challenging optimization problems. Experimental evaluations on both synthetic benchmarks and real-world deep learning tasks demonstrate the superior performance of our approach compared to existing methods.", "questions": "Question1: The challenges section should clarify the algorithmic goals (e.g., noise-adaptive convergence? hyperparameter robustness?) and explicitly link them to the listed challenges. For example:\n\n1.1 Why is \"update balance\" critical for the goal? Does imbalance cause divergence or slow convergence?\n\n1.2 How does \"randomness dependency\" hinder theoretical guarantees (e.g., broken Martingale conditions)?\n\n1.3 Please contrast with single-level optimization to highlight the unique hierarchical difficulties.\n\nQuestion2: The authors state that the minimax problem (1) is a special case of the bilevel problem (2) when g=−f. However, the paper subsequently develops separate algorithms for each class. Could the authors clarify:\n\n2.1 Why a unified bilevel algorithm cannot naturally handle the minimax case by setting g=−f? \n\n2.2 Are there fundamental differences between the two problem classes that necessitate distinct algorithmic treatments (e.g., convergence guarantees, hyperparameter tuning, or practical performance)?\n\nQuestion3: Regarding Theorems 1 and 2, I notice that both convergence results contain the parameter \\eta, while the corresponding Algorithms 1 and 2 actually employ two distinct step sizes (\\eta_{x} for upper-level variables and \\eta_{y} for lower-level variables). Could the authors please clarify what \\eta specifically represents in each theorem statement. A clear explanation of this notation choice would significantly improve the theoretical rigor and readability of the paper.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper makes significant algorithmic contributions by developing the first theoretically guaranteed noise-adaptive methods for stochastic hierarchical optimization problems. The novel combination of momentum normalization for upper-level variables with adaptive stepsizes for both levels represents an important technical advancement and could inspire future research in the field.\n\nWeaknesses:\nThe paper contains several unclear key formulations, for example, the 'Main Challenges' section fails to clearly articulate the fundamental objectives of the algorithm design (e.g., achieving noise-adaptive convergence, ensuring hyperparameter robustness). This omission makes it difficult to evaluate whether the subsequently listed challenges are indeed the most critical barriers to these objectives.", "was_revised": true, "final_justification": "I thank the authors for their thorough response, I wil maintain my score.", "rebuttal": "**Q1. The challenges section should clarify the algorithmic goals (e.g., noise-adaptive convergence? hyperparameter robustness?) and explicitly link them to the listed challenges. For example: 1) Why is \"update balance\" critical for the goal? Does imbalance cause divergence or slow convergence? 2) How does \"randomness dependency\" hinder theoretical guarantees (e.g., broken Martingale conditions)? 3) Please contrast with single-level optimization to highlight the unique hierarchical difficulties.**\n\n**A1.** The update balance is critical to establish guarantees for the lower-level estimation error, see Lemma 5.7 and its proof in Appendix C for details. Technically, this balance is captured by the term $\\eta_{x,t}^2 / \\eta_{y,t}$, and we aim to ensure that $\\sum_{k=1}^{t} \\eta_{x,k}^2 / \\eta_{y,k} = \\widetilde{O}(1)$ to provide tight upper bounds for the lower-level estimation error. This condition is essential for guaranteeing convergence in both minimax and bilevel optimization problems. If $\\eta_{x,t}$ and $\\eta_{y,t}$ are not properly chosen, the resulting imbalance may lead to slow convergence or even divergence in these hierarchical settings.\n\nThe complex randomness dependencies arising from both the upper- and lower-level variables do hinder the theoretical guarantees in [1], unless strong assumptions such as bounded stochastic gradients and bounded function values (see Assumptions 3.4 and 3.5 in [1]) are imposed. These assumptions are essential for their proofs of [1, Theorem 3.2], as illustrated in [1, Lemmas C.3–C.5] in [1, Appendix C.2]. In contrast, our newly proposed method updates $x_t$ using normalized SGD with momentum and $y_t$ using AdaGrad-Norm, rather than applying AdaGrad-Norm to both updates, to avoid such strong assumptions. Moreover, we develop a novel high-probability analysis to address the challenges posed by statistical dependencies among the momentum parameters $\\alpha_t$, $\\beta_t$, and the stochastic gradient noise $\\epsilon_t$, as detailed in our Lemmas 5.4 and 5.5 (see proofs in Appendix B.1).\n\nThe main challenges in establishing adaptive guarantees for hierarchical optimization lie in two key aspects. First, designing adaptive algorithms for hierarchical problems requires carefully balancing the updates of the upper- and lower-level variables, which is particularly challenging without prior knowledge of the stochastic gradient noise magnitude. Second, the statistical dependencies introduced by the upper- and lower-level updates necessitate the development of a new high-probability analysis to achieve sharp and adaptive convergence rates in hierarchical settings.\n\n**Q2. The authors state that the minimax problem (1) is a special case of the bilevel problem (2) when $g=-f$. However, the paper subsequently develops separate algorithms for each class. Could the authors clarify: 1) Why a unified bilevel algorithm cannot naturally handle the minimax case by setting $g=-f$? 2) Are there fundamental differences between the two problem classes that necessitate distinct algorithmic treatments (e.g., convergence guarantees, hyperparameter tuning, or practical performance)?**\n\n**A2.** The unified algorithmic framework presented in Algorithm 2 can, in fact, handle both minimax problems (by setting $g = -f$) and bilevel problems. However, since minimax problems jointly optimize the same objective function with respect to both $x$ and $y$, we can design a simpler method as presented in Algorithm 1. Specifically, Algorithm 1 (for minimax optimization problem) directly uses the stochastic gradient $g_{x,t} = \\nabla_x F(x_t, y_t; \\xi_t)$ to update the momentum $m_t$ and the upper-level variable $x_t$, rather than relying on the hypergradient estimator $g_{x,t} = \\bar{\\nabla} f(x_t, y_t; \\bar{\\xi}_t)$ used in Algorithm 2 (for bilevel optimization problem).\n\nAs a result, the proposed Ada-Minimax method in Algorithm 1 is fully parameter-free (see the remark below Theorem 4.1) and does not require prior knowledge of $\\mu$, $L$, or $T$, which would otherwise be needed for the construction of the Neumann series in Algorithm 2 for bilevel problems.\n\nThere are no fundamental differences between the two problem classes that necessitate distinct algorithmic treatments. In fact, we provide a unified analytical framework in Section 5 to establish convergence guarantees for both Algorithms 1 and 2 (see Theorems 4.1 and 4.2). The only minor distinction lies in the handling of hypergradients (rather than stochastic gradients) and the additional bias terms introduced by the Neumann series construction in Algorithm 2. Moreover, the hyperparameters that require tuning are essentially the same for both algorithms, with the exception of the parameter $N$ in the Neumann series used in Algorithm 2. In practice, we set $N = 3$ by default, which has been shown to work well in previous studies [2, 3].\n\n**Q3. Regarding Theorems 1 and 2, I notice that both convergence results contain the parameter $\\eta$, while the corresponding Algorithms 1 and 2 actually employ two distinct step sizes ($\\eta_x$ for upper-level variables and $\\eta_y$ for lower-level variables). Could the authors please clarify what $\\eta$ specifically represents in each theorem statement. A clear explanation of this notation choice would significantly improve the theoretical rigor and readability of the paper.** \n\n**A3.** Thank you for catching this issue, and we apologize for the ambiguity. In Theorems 4.1 and 4.2 (corresponding to Algorithms 1 and 2), we actually set the free parameters as $\\eta_x=\\eta_y=\\eta$ for simplicity. It is worth noting that this condition is not necessary for establishing convergence, it only affects the universal constants in the rate. \n\n&#8203;\n\n[1] Li, Xiang, Junchi Yang, and Niao He. \"TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization.\" In The Eleventh International Conference on Learning Representations, 2023.\n\n[2] Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Bilevel Optimization: Convergence Analysis and Enhanced Design.\" In International Conference on Machine Learning, pp. 4882-4892. PMLR, 2021.\n\n[3] Hao, Jie, Xiaochuan Gong, and Mingrui Liu. \"Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis.\" In The Twelfth International Conference on Learning Representations, 2024."}, {"review_id": "xCVh8efM2E", "reviewer": "Reviewer_59Af", "summary": "This paper introduces new adaptive stochastic optimization algorithms for hierarchical problems (specifically minimax and bilevel optimization) that automatically adjust to the noise in the data. The authors identify that existing methods for stochastic convex optimization and hierarchical optimization do not achieve optimal convergence across different noise regimes unless the noise level is known in advance. In response, the paper proposes two algorithms (dubbed Ada-Minimax and Ada-BiO) that leverage a momentum normalization technique combined with adaptive step-size tuning. These methods guarantee sharp convergence rates of $\\tilde{O}(1/\\sqrt{T} + \\sqrt{\\bar{\\sigma}}/T^{1/4})$ for the gradient norm, matching known lower bounds and thus achieving optimal statistical performance in both low-noise and high-noise settings. Notably, the algorithms require no prior knowledge of the noise distribution or magnitude, handling both well-specified and misspecified noise models seamlessly.", "questions": "NA.", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper provides a novel theoretical result by achieving adaptive convergence rates in hierarchical stochastic optimization. It is the first work to guarantee optimal rates across different noise regimes without tuning to noise level, addressing a clear gap in the literature.\n\n2. Each major claim is supported either by a theorem or an experiment. The authors prove their convergence rate results under clear assumptions and also include a comparison to existing methods to highlight where those fail to adapt. The presence of both theory and experiments strengthens confidence that the contributions are sound and not merely of theoretical interest.\n\n3. Despite the theoretical nature, the paper demonstrates strong practical performance. Empirical results on a range of tasks show the new algorithms outperform traditional baselines (both adaptive and non-adaptive) in convergence speed and stability.\n\nWeaknesses:\n\n1. Due to the technical depth of the contribution, some parts of the paper are dense. The theoretical sections (e.g. proofs and algorithm analysis) involve intricate analysis of two-level optimization with time-varying parameters. This could make it challenging for non-experts to follow all details.\n\n2. The adaptive guarantees are proven under certain assumptions (e.g. the lower-level problem is strongly convex or concave, smoothness of objectives, and bounded noise variance). These conditions limit the scope of the results. I understand that these assumptions are standard in this field. However, it somehow makes the theoretical analysis deviate from the realistic scenarios.", "was_revised": true, "final_justification": "I received author's response and decide to maintain my current score.", "rebuttal": "**Q1. Due to the technical depth of the contribution, some parts of the paper are dense. The theoretical sections (e.g. proofs and algorithm analysis) involve intricate analysis of two-level optimization with time-varying parameters. This could make it challenging for non-experts to follow all details.**\n\n**A1.** Thank you for your suggestions. In Algorithms 1 and 2, we update $x_t$ using normalized SGD with momentum and $y_t$ using AdaGrad-Norm, with momentum parameters $\\alpha_t$ and learning rates $\\eta_{x,t}$ and $\\eta_{y,t}$ defined in Eqs. (3) and (4). These parameter choices are motivated by the goal of estimating variance through differences between independently sampled gradients, thus enabling sharp and adaptive convergence rates without requiring prior knowledge of the noise level (or other problem-dependent parameters).\n\nFor the theoretical analysis of Theorems 4.1 and 4.2 (corresponding to Algorithms 1 and 2), we begin by analyzing the adaptive normalized SGD with momentum (Algorithm 3) in the nonconvex stochastic single-level optimization setting, as described in Section 5.1. In Theorem 5.6, we establish a sharp noise-adaptive convergence rate of $\\widetilde{O}(1/\\sqrt{T} + \\sqrt{\\bar{\\sigma}}/T^{1/4})$. A key component of this result involves applying concentration inequalities and linear programming techniques to derive tight bounds for the momentum deviation $\\\\|m_t - \\nabla F(x_t)\\\\|$ (Lemma 5.4) and the momentum parameters (Lemma 5.5). The upper-level analyses for both minimax and bilevel problems then follow as straightforward extensions of this single-level framework.\n\nNext, we provide a unified analysis of the lower-level estimation error applicable to both minimax and bilevel optimization in Lemma 5.7 (Section 5.2). This result is critical for controlling the bias in (hyper)gradient estimation. Specifically, it extends the AdaGrad-Norm analysis developed for convex settings in [1] to account for the shift induced by $x_t$, while incorporating our novel adaptive parameter choices from Eqs. (3) and (4). Note that setting $g = -f$ in the bilevel problem reduces it to the minimax formulation.\n\nFinally, by combining the upper-level analysis framework from Section 5.1 with the lower-level estimation error bounds developed in Section 5.2 (i.e., bounds on the gradient and hypergradient estimation bias), we derive Theorems 4.1 and 4.2.\n\nIn the revised version, we will reorganize the paper and include more intuition and high-level explanations of the theoretical proofs and algorithm analysis in Sections 4 and 5 to improve readability and make the paper easier to follow.\n\n**Q2. The adaptive guarantees are proven under certain assumptions (e.g. the lower-level problem is strongly convex or concave, smoothness of objectives, and bounded noise variance). These conditions limit the scope of the results. I understand that these assumptions are standard in this field. However, it somehow makes the theoretical analysis deviate from the realistic scenarios.**\n\n**A2.** These assumptions are indeed standard in the fields of minimax and bilevel optimization; see [2, 3, 4, 5, 6] and the assumptions therein. In fact, many practical applications, such as meta-learning, naturally satisfy these assumptions, including strong convexity of the lower-level problem as the lower-level variable often represents the last layer of neural networks [3, 7].\n\n&#8203;\n\n[1] Attia, Amit, and Tomer Koren. \"SGD with AdaGrad stepsizes: Full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance.\" In International Conference on Machine Learning, pp. 1147-1171. PMLR, 2023.\n\n[2] Li, Xiang, Junchi Yang, and Niao He. \"TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization.\" In The Eleventh International Conference on Learning Representations, 2023.\n\n[3] Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Bilevel Optimization: Convergence Analysis and Enhanced Design.\" In International Conference on Machine Learning, pp. 4882-4892. PMLR, 2021.\n\n[4] Ghadimi, Saeed, and Mengdi Wang. \"Approximation methods for bilevel programming.\" arXiv preprint arXiv:1802.02246 (2018).\n\n[5] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.\" Advances in Neural Information Processing Systems 34 (2021): 25294-25307.\n\n[6] Hong, Mingyi, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. \"A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.\" SIAM Journal on Optimization 33, no. 1 (2023): 147-180.\n\n[7] Raghu, Aniruddh, Maithra Raghu, Samy Bengio, and Oriol Vinyals. \"Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML.\" In The Eighth International Conference on Learning Representations, 2020."}, {"review_id": "ouNthBgcA4", "reviewer": "Reviewer_kf2Z", "summary": "This paper studies nonconvex–strongly-concave minimax and bilevel optimization problems and proposes adaptive algorithms that adjust to the gradient noise level, whether it is in a high- or low-noise regime.", "questions": "1. The convergence results are established for cases where the noise level (i.e., variance of the stochastic gradient) may vary over iterations, covering both low- and high-noise regimes. Does the first experiment (Figure 1) reflect such a setting? If not, it would be informative to include a comparison between TiAda and the proposed method under these conditions.\n        \n2. I was wondering whether this approach might be extendable to the nonconvex–concave settings. Since momentum-based methods are sometimes effective in maximizing concave objective, it seems possible that such an extension could work.\n\n3. Since the theoretical results (e.g., Thm 5.6) hold with high probability, it may be beneficial to include confidence intervals in the experimental plots to better illustrate the results.\n\n4. In [1], the convergence of the expected gradient is established in expectation, without relying on probability bounds. In contrast, the results in the present paper (e.g., Theorem 4.1) show that the (deterministic) sum of gradients converges with high probability. Can the current analysis similarly be extended to guarantee convergence in expectation, without relying on high-probability bounds? Alternatively, could the authors clarify which result provides a stronger guarantee?\n\n[1] Xiang Li, YANG Junchi, and Niao He. Tiada: A time-scale adaptive algorithm for nonconvex minimax\noptimization. In The Eleventh International Conference on Learning Representations.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The theoretical results look solid and this paper is well-organized. \n2. The paper proposes an adaptive algorithm that achieves sharp convergence rates in both nonconvex–strongly-concave minimax and bilevel optimization, without requiring prior knowledge of problem-specific parameters such as smoothness constants or noise variance. \n3. The method automatically adapts to different noise regimes, and the convergence results smoothly interpolate between the optimal rates for both high- and low-noise settings.\n\nWeaknesses: The theoretical results look solid but not strong since they only provide high probability convergence rather than convergence in expectation or almost sure convergence.", "was_revised": true, "final_justification": "1. My main concern was the significance of the theoretical results presented in the paper, and the authors have addressed this clearly in A.4.\n2. In addition, they provided experimental results on a time-varying example, which I had hoped to see included in the paper.\n3. Authors also clarified the applicability of their results to relaxed settings, which further strengthened the contribution.\nOverall, I believe the clarity and completeness of the paper will be significantly improved in the revised version, and I have raised my score accordingly.", "rebuttal": "**Q1. The convergence results are established for cases where the noise level (i.e., variance of the stochastic gradient) may vary over iterations, covering both low- and high-noise regimes. Does the first experiment (Figure 1) reflect such a setting? If not, it would be informative to include a comparison between TiAda and the proposed method under these conditions.**\n\n**A1.** Thank you for your insightful question. We conducted experiments using time-varying stochastic gradient noise sampled from $\\mathcal{N}(0, \\sigma_t^2)$ where $\\sigma_t = \\sigma(1+\\sin t)$ at the $t$-th iteration. We run the experiments using 5 different random seeds and the results are presented in Table 1. Both the momentum parameter $\\alpha$, the base learning rates $(\\eta_x, \\eta_y)$, and $\\gamma$ are tuned over the set $\\\\{0.1, 0.5, 1.0, 2.0, 3.0, 4.0, 5.0\\\\}$. We use the following parameter settings for different noise magnitudes:\n- For $\\sigma = 20$: Ada-Minimax: $\\alpha = 5.0$, $\\eta_x = 1.0$, $\\eta_y = 1.0$; TiAda: $\\eta_x = 4.0$, $\\eta_y = 4.0$. Run for $T=1000$ iterations.\n- For $\\sigma = 30$: Ada-Minimax: $\\alpha = 5.0$, $\\eta_x = 1.0$, $\\eta_y = 1.0$; TiAda: $\\eta_x = 2.0$, $\\eta_y = 2.0$. Run for $T=2500$ iterations.\n\n**Table 1: Gradient norm $\\\\|\\nabla\\Phi(x_t)\\\\|$ evaluated at the last step.**\n\n| Method       | $\\sigma = 20$                  | $\\sigma = 30$                  |\n|--------------|--------------------------------|---------------------------------|\n| TiAda        | $0.4451_{\\pm 0.4218}$          | $0.1796_{\\pm 0.1429}$           |\n| Ada-Minimax  | $0.0418_{\\pm 0.0390}$          | $0.1153_{\\pm 0.0873}$           |\n\n\n&#8203;\n\n**Q2. I was wondering whether this approach might be extendable to the nonconvex–concave settings. Since momentum-based methods are sometimes effective in maximizing concave objective, it seems possible that such an extension could work.**\n\n**A2.** If we further assume that \"$y \\in \\mathcal{Y} \\subseteq \\mathbb{R}^{d_y}$ and $\\mathcal{Y}$ is a convex and bounded set with diameter $D \\geq 0$\" as stated in [1, Assumption 4.2], and modify line 5 of our Algorithm 1 to $y_{t+1} = \\mathcal{P}\\_{\\mathcal{Y}}(y_t + \\eta_{y,t} g_{y,t})$, and also replace our current convergence measure with the gradient of the Moreau envelope (see Definition 3.5 and Lemma 3.6 in [1]), then it becomes possible to extend our algorithmic framework to the nonconvex-concave setting. \n\nWe outline this as a high-level technical idea and leave the detailed theoretical analysis for future work. In particular, Theorem D.2 (the full version of Theorem 4.10) in [1] shows that the choices of $\\eta_x$ and $\\eta_y$ depend on the noise level $\\sigma$. The requirement for prior knowledge of $\\sigma$ and other problem-dependent parameters could potentially be removed by employing our adaptive parameter choices defined in Eqs. (3) and (4), possibly with adjusted powers in the denominators to asymptotically match the orders of $\\eta_x$ and $\\eta_y$ specified in Theorem D.2 of [1].\n\n&#8203;\n\n**Q3. Since the theoretical results (e.g., Thm 5.6) hold with high probability, it may be beneficial to include confidence intervals in the experimental plots to better illustrate the results.**\n\n**A3.** We have conducted the experiments using 5 different random seeds. The hyperparameter settings and experimental details are included in Appendices I and J. See Tables 2 and 3 for details.\n\n**Table 2: Gradient norm $\\\\|\\nabla\\Phi(x_t)\\\\|$ evaluated at the last step.**\n\n| Method       | $\\sigma = 0$               | $\\sigma = 20$                | $\\sigma = 50$                | $\\sigma = 100$               |\n|--------------|-----------------------------|-------------------------------|-------------------------------|-------------------------------|\n| TiAda        | $0.0193_{\\pm 0.0000}$      | $0.1657_{\\pm 0.1052}$        | $0.5437_{\\pm 0.5332}$        | $0.9394_{\\pm 0.8541}$        |\n| Ada-Minimax  | $0.0163_{\\pm 0.0000}$      | $0.0555_{\\pm 0.0319}$        | $0.1198_{\\pm 0.1095}$        | $0.1644_{\\pm 0.1391}$        |\n\n**Table 3: The final training/test AUC with 5 runs.**\n\n| Method       | Training AUC               | Test AUC                 |\n|--------------|-----------------------------|-------------------------------|\n| SGDA  | $0.7435_{\\pm 0.0424}$      | $0.6970_{\\pm 0.0251}$     |\n| PDSM  | $0.7765_{\\pm 0.0050}$      | $0.7133_{\\pm 0.0072}$     |\n| TiAda        | $0.6127_{\\pm 0.0138}$      | $0.6152_{\\pm 0.0010}$      |\n| Ada-Minimax  | $0.9284_{\\pm 0.0252}$      | $0.7331_{\\pm 0.0196}$     |\n\n&#8203;\n\n**Q4. In [2], the convergence of the expected gradient is established in expectation, without relying on probability bounds. In contrast, the results in the present paper (e.g., Theorem 4.1) show that the (deterministic) sum of gradients converges with high probability. Can the current analysis similarly be extended to guarantee convergence in expectation, without relying on high-probability bounds? Alternatively, could the authors clarify which result provides a stronger guarantee?**\n\n**A4.** We would like to clarify that our high-probability result is stronger than the in-expectation result in [2]. Notably, [2] assumes almost surely bounded stochastic gradient noise implicitly: their [2, Assumption 3.4] implies $\\\\|\\nabla_zF(x,y;\\xi) - \\nabla_zf(x,y)\\\\|\\leq \\\\|\\nabla_zF(x,y;\\xi)\\\\| + \\\\|\\nabla_zf(x,y)\\\\| \\leq 2G$, where $G$ is the upper bound on the stochastic gradient norm. This indicates that the noise is almost surely bounded by $2G$, and thus their analysis relies on a light-tailed noise assumption, similar to ours.\n\nIn fact, a high-probability bound always implies an in-expectation bound; see Lemma A.3 in [3] for details. By applying Lemma A.3 in [3], we can derive an in-expectation bound of $\\frac{4}{\\sqrt{\\log(2/\\delta)}}\\cdot\\text{RHS} = \\widetilde{O}(1/\\sqrt{T} + \\sqrt{\\bar{\\sigma}_x}/T^{1/4})$, where RHS denotes the right-hand side of the bound in our Theorem 4.1. This expectation bound is comparable to that of [2] up to a $\\text{polylog}(1/\\delta)$ factor in the worst case. However, our bound is noise-adaptive, whereas their bound in [2, Theorem 3.2] depends on the stochastic gradient norm bound $G$. \n\nConversely, while an in-expectation bound in [2] can be converted into a high-probability bound using Markov's inequality, this approach results in a looser dependency on the failure probability $\\delta$, specifically yielding a bound that scales with $O(1/\\delta)$. In contrast, our analysis yields a high-probability bound that depends only on $O(\\log(1/\\delta))$, and is therefore much tighter.\n\n&#8203;\n\n[1] Lin, Tianyi, Chi Jin, and Michael Jordan. \"On gradient descent ascent for nonconvex-concave minimax problems.\" In International conference on machine learning, pp. 6083-6093. PMLR, 2020.\n\n[2] Li, Xiang, Junchi Yang, and Niao He. \"TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization.\" In The Eleventh International Conference on Learning Representations, 2023.\n\n[3] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014."}]

Author rebuttal:

Meta-review: This paper presents new adaptive algorithms for nonconvex–strongly-concave min-max problems and nonconvex–strongly-convex bilevel stochastic optimization. The proposed methods achieve sharp convergence rates without requiring prior knowledge of the noise level. By integrating momentum normalization with an adaptive step-size scheme, the approach demonstrates strong empirical performance on both synthetic benchmarks and deep learning tasks.

From a technical perspective, the paper combines momentum normalization for the upper-level variables with a carefully designed adaptive step-size scheme for both levels, yielding the first theoretically guaranteed noise-adaptive solution for these challenging optimization problems. I believe the paper merits acceptance. Nonetheless, it could be further strengthened by improving the empirical evaluation and presentation in the final version. In particular, I encourage the authors to address the reviewers’ feedback in the final version of the paper, with particular emphasis on:

1-Improving the presentation of the key challenges in the analysis.

2-Discussing the limitations of the analysis.

3-Including experiments that evaluate performance under varying noise levels.
Decision: Accept (poster)