Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization
Authors: Junchi YANG
Xiang Li
Niao He
Venue: NeurIPS 2022 Accept (2022)
Keywords: Nonconvex optimization
minimax optimization
adaptive algorithm

Abstract: Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability – requiring no a priori knowledge about problem-specific parameters nor tuning of learning rates. However, when it comes to nonconvex minimax optimization, direct extensions of such adaptive optimizers without proper time-scale separation may fail to work in practice. We provide such an example proving that the simple combination of Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge if the primal-dual stepsize ratio is not carefully chosen; hence, a fortiori, such adaptive extensions are not parameter-agnostic. To address the issue, we formally introduce a Nested Adaptive framework, NeAda for short, that carries an inner loop for adaptively maximizing the dual variable with controllable stopping criteria and an outer loop for adaptively minimizing the primal variable. Such mechanism can be equipped with off-the-shelf adaptive optimizers and automatically balance the progress in the primal and dual variables. Theoretically, for nonconvex-strongly-concave minimax problems, we show that NeAda with AdaGrad stepsizes can achieve the near-optimal $\widetilde{O}(\epsilon^{-2})$ and $\widetilde{O}(\epsilon^{-4})$ gradient complexities respectively in the deterministic and stochastic settings, without prior information on the problem's smoothness and strong concavity parameters. To the best of our knowledge, this is the first algorithm that simultaneously achieves near-optimal convergence rates and parameter-agnostic adaptation in the nonconvex minimax setting. Numerically, we further illustrate the robustness of the NeAda family with experiments on simple test functions and a real-world application.


Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization
Junchi Yang"
Xiang Li
Department of Computer Science ETH Zurich, Switzerland yang@in.. ethz. ch
Department of Computer Science ETH Zurich, Switzerland xiang. li@inff ethz. ch
Niao He
Department of Computer Science ETH Zurich, Switzerland niao.he@ing wwwineenn...... waanfethar ethz. ch
Abstract
Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability requiring no priori knowledge about problem-specific parameters nor tuning of learning rates. How- ever, when it comes to nonconvex minimax optimization, direct extensions of such adaptive optimizers without proper tine-ccale separation may fail to work in practice. We provide such example proving that the simple combination Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge the primal-dual stepsize ratio is not carefully chosen; hence, fortiori, such adaptive extensions are not parameter-agnostic. To address the issue, we formally introduce Nested Adaptive framework, NeAda for short, that carries inner loop for adaptively maximizing the dual variable with controllable stopping criteria and an outer loop for adaptively minimizing the primal variable. Such mechanism be equipped with off- the-shelf adaptive optimizers and automatically balance the progress in the primal and dual variables. Theoretically, for sercconvex-stronglee concave minimax problems, we show that NeAda with AdaGrad stepsizes can achieve the near-optimal (( and Ō(e gradient complexities respectively in the deterministic and stochastic settings, without prior information on the problem's smoothness and strong concavity parameters. To the best of our knowledge, this is the first algorithm that simultaneously achieves near-optimal convergence rates and perameter-agnoose adaptation in the nonconvex minimax setting. Numerically, we further illustrate the robustness the NeAda family with experiments on simple test functions and real-world application.
Introduction
Adaptive gradient methods, whose stepsizes and search directions are adjusted based on past gradients, have received phenomenal popularity and are proven successful in variety of large-scale machine learning applications. Prominent examples include AdaGrad [77] RMSProp [3I, AdaDelta (84),
Adam 411. and AMSGrad [69,, just name few. Their empirical success is especially pronounced for nonconvex optimization such as training deep neural networks. Besides improved performance, being parameter-agnosticc is another important trait of adaptive methods. Unlike (stochastic) gradient descent, adaptive methods often do not require a priori knowledge about problem-specific parameters
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(such as Lipschitz constants, smoothness, etc.) On the theoretical front, some adaptive methods can achieve nearly the same convergence guarantees as (stochastic) gradient descent Recently, adaptive methods have sprung up for minimax optimization:
69
min max f(x,, y) A (1,
wERd yEy
where f is (-Lipschitz smooth jointly in x and y. y is closed and convex, and 5 is a random vector. Such problems have found numerous applications in generative adversarial networks (GANs) (25 4
Wasserstein GANs
4 generative adversarial imitation learning [2), reinforcement learning 14 60
adversarial training
poomiin-adverarrti training of neural networks 21 etc.
common practice is to simply combine adaptive stepsizes with popular minimax optimization algorithms such as Gradient Descent Ascent (GDA), extragradient method (EG) and the like; see worth noting that these methods are reported successful in some applications suffer from training instability. In recent years, theoretical behaviors of such adaptive methods are extensively studied for convex-concave minimax optimization; see e.g..
e.g..
123
2 2
yet at other times
6 3
[I [8 72 [2] [58 [5]. However, for minimax optimization in the important nonconvex regime,
little theory related to adaptive methods is known.
Unlike the
setting, a key challenge for nonconvex minimax optimization lies in the necessity of a problem-specific time-scale separation of the learning rates between the min-player
and max-player when GDA or EG methods are applied, as proven in [2 50 70
Σ. This makes the design of adaptive methods fundamentally different from and more challenging than nonconvex minimization. Several recent attempts 28
studied adaptive methods for nonconvex-strongly- concave minimax problems; yet. they all require explicit knowledge of the problems' smoothness and strong concavity parameters to maintain stepsize ratio proportional to the condition number. Such a requirement evidently undermines the parameter-agnostic trait of adaptive methods. This then raises couple of interesting questions: (1) Without a moblem-deepedent stepsize ratio, does simple combination of GDA and adaptive stepsizes still converge? (2) Can we design an adaptive algorithm for nonconvex minimax optimization that is truly parameter-agnostee and provably convergent?
33 [4]
In this paper, we address these questions and make the following key contributions:
We investigate two generic frameworks for adaptive minimax optimization: one is simple (non-nested) adaptive framework, which performs one step of update of x and simulta- neously with adaptive gradients; the other is Nested Adaptive (NeAda) framework, which performs multiple updates of y after one update of each with adaptive gradients. Both frameworks allow flexible choices of adaptive mechanisms such as Adam, AMSGrad and AdaGrad. We provide an example proving that the simple adaptive framework can fail to converge without setting an appropriate stepsize ratio; this applies to any of the adap- tive mechanisms mentioned above, even in the noiseless setting. In contrast, the NeAda framework is less sensitive to the stepsize ratio, as numerically illustrated in Figure
We provide the convergence analysis for a representative of NeAda that uses AdaGrad stepsizes for x and a convergent adaptive optimizer for y, in terms of conconvex-strongly concave minimax problems. Notably, the convergence of this general scheme does not require to know any problem parameters and does not assume the bounded gradients. We demonstrate that NeAda is able to achieve Ō(c²?) oracle complexity for the deterministic setting and ( -4) for the stochastic setting to converge to e-stationary point, matching best known bounds. To the best of our knowledge, this seems to be the first adaptive framework for nonconvex minimax optimization that is provably convergent and parameter-agnostic
We further make two complementary contributions, which can be of independent interest. First, we propose a general AdaGrad-type stepsize for strongly-convex problems without knowing the strong convexity parameters, and derive a convergence rate comparable to SGD, It can serve as a subroutine for NeAda. Second, we provide a high probability convergence result for the primal variable of NeAda under a subGaussian assumption.
FFor distinction, we use saarameter-ggnottie to describe algorithms that do not ask for groblem-specingg parameters in setting their stepsizes or hyperparameters; we refer to "adaptive algorithms" as methods whose stepsizes are based the previously observed gradients.

---

AMSCnd NeAda AMSGrad
AdaGrad
NoAdo-Adamm
NeAda-AdaGral
NeAda-GD
(a)
(b) rb)==
(c) r
(d) r
Figure Comparison between the two families of non-nested and nested adaptive methods on
function [ar y) = fØ²² + 2xy - 2x with deterministic gradient oracles. r= /1/ o is pre-fixed
learning rate ratio.
Finally, numerically validate the robustness of the NeAda framework on several test functions compared to the non-nested adaptive framework, and demonstrate the effectiveness of the NeAda framework distributionally robust optimization task with real dataset.
1.1 Related work
Adaptive algorithms. Duchi et al. 17 and Streeter and McMahan for convex online learning and achieve (v)T) regrets. Li and Orabona 4 and Ward et al. [79
introduce AdaGrad
show an ()e=4) complexity for AdaGrad in the nonconvex stochastic optimization. There extensive number of works on AdaGrad-type methods; to list few, 159
Another aggressive stepsizes of exponential moving average of the past
65
family of algorithms uses gradients, such as Adam 41 and RMSProp B1 Reddi et al. 699 point out the non-convergence of Adam and provide remedy with non-inoneen con-increasing stepsizes. There is surge in the study of Adam- type algorithms due to their popularity in the deep neural network training
S3 11] Some work provides the convergence results for adaptive methods in the strongly-convex optimization 778 44 62
Line search and stochastic line search are another effective strategy that can detect the objective's Notably, many adaptive algorithms are
curvature and have received much attention 75 parameter-agnostie
76
Nonconvex minimax optimization. Stationary convergence of GDA in NC-SC setting was first provided by Lin et al. (50). showing O oracle complexity and ( sample complexity with minibatch. Recently, Chen et al. 110) and Yang et al. [22 achieve this sample complexity in the stochastic setting without minibatch. GDmax a double loop algorithm that maximizes the dual variable to certain accuracy. It achieves nearly the same complexity GDA 64. Sebbouh et al. 70 recently discuss the relation between the two-time-sene and number of inner steps for GDmax. Very recently, Li et al. 47 show that time-scale separation is necessary for GDA to converge to Stackelberg equilibrium. Besides NC-SC setting, some work provides convergent algorithms when the objective is (non-strongly) concave about the dual variable 85
55 81. sanconvex-nonconee (PL) condition 19 All algorithms mentioned above require prior knowledge about problem parameters, such as smoothness modulus, strong concavity modulus, and noise variance.
regime is only explored under some special structure [53 15 such as
There exist many adaptive and parameter- agnostic methods designed for convex-concave minimax optimization special case monotone 58 15]. Most of them combine extragradient method, mirror prox 633 the like, with AdaGrad mechanism. Liu al. [52] and Dou and Li [16] relax convexity-
Adaptíve algorithms in minimax optimization.
variational inequality [ 3 II 72
22
concavity assumption to the regime where Minty variational inequality (MVI) has a solution. In these settings, time-scale separation of learning rates is not required even for non-adaptive algorithms. For nonconvex-stronge -tronngyy-concvee problems, Huang and Huang 33 Huang et al. [64] Guo et al. [28 propose adaptive methods, which set the learning rates based on knowledge about smoothness and strong-concavie modulus and the bounds for adaptive stepsizes.
3

---

2 Non-nested and nested adaptive methods
In this section, investigate two generic frameworks that can incorporate most existing adaptive methods into minimax optimization. We remark that many variants encapsulated in these two families are already widely used in practice, such training of GAN (24, distributionally robust optimization 77I. etc. These two frameworks, coined as non-nested and nested adaptive methods, can be viewed as adaptive counterparts of GDA and GDmax. We aim illustrate the difference between these two adaptive families, even though GDA and GDmax are often considered "twins".
Non-nested adaptive methods. In Algorithm I non-nested methods update the primal and dual variables in a symmetric way. Weighted gradients mi and m. are the moving average of the past stochastic gradients with the momentum parameters 3 and (3V. The effective stepsizes of and y are 17" /o and n// ///y // where the division taken coordinate-wise. We refer to 17" and n as learning rates, and 2iz 27 are some average of squared past gradients through function v. Many popular choices of adaptive stepsizes are captured in this framework, see also [69]:
(GDA) B = 0; ab (oo, fo Vimo) =1 (AdaGrad)
B O; vb (wo. 19 = + Σ 92.
1=
(Adam) &i (oo, (9, (oo) = = u0 + (1-7)
Σ 1=0
7 96.
(AMSGrad) & (vn, 10))= max
?
m+
Up + (1 (1-?)
91
m O...,t
Algorithm Non-nested Adaptive Method
Algorithm 2 Nested Adaptive (NeAda) Method
Input: zo and yo
1: Input: zo and yú
2: for t = 0, 1, 2.... do
2: for f 2, do
3: sample &, and let
3: for k: = 0, 1, until stopping criterion is
of V F yei Ex) and - V, y Ve:
satisfied do
4: sample et and gh,x = (a ett
4: // update the first moment
5:
m f+1 3 (1 3")
mf+1 m (1 3r and
6:
uy kkt = -b"l (vi,0: flo,, )21
m f + (1 - )")
7:
Vi k+1 vi + 7p" m
Vo
5: // update the second moment
8: end for
o = vi (1p. (( and ey vi (ng, ()
9: 11+ 1i/x-1 and m m m m
10: sample &t and of = Va F F(xe, vi [e,
6:
// update variables
11:
m m + (1 fa
1t+1 Et-
m and
12: of = vb (1ō {(g))
Mt+1 Ve +
13:
F++1 F2
mf+1
7: end for
14: end for
Nested adaptive (NeAda) methods. NeAda, presented in Algorithm 2 has nesting inner loop to maximize y until some stopping criterion is reached (see details in Section 3). Instead of using a fixed number of inner iterations or a fixed target accuracy as in GDmax [50 NeAda gradually increases the accuracy of the inner loop as the outer loop proceeds to make fully adaptive.
We refer to the ratio between two learning rates, i.e. 17 /n7", as the two-time-scale. The current analysis of GDA in nonconvex-strooglyy-oom conocaaveggyyoocvveeeeeee setting requires two-time-scale be proportional with the condition number λ = 1/1,, where and jr are Lipschitz smoothness and strongly-concavin We provide example showing that the
-depeneen two-time-scale is necessary for GDA and most non-nested methods even in the deterministic setting.
modulus 50 8
Lemma 2.1. Consider the function f(I, v) - -12²2 + Lay
12 x² in the deterministic setting, Let 2
rmy" 17"h (1) GDA will not converge to the stationary point when r < L2:
T-1
VaI(IT.TT) = v.J( vo)
II
[ + 1/" (L2 r)]

---

(2) Assume the averaging function x² and at are the same, and satisfy that for any т, if uî = and (2 T( )2 then of+1 T With 3 =,, vij are commonly used in practice), non-nested adaptive method will not converge when r S L,
v and mi = (which
T-1
LTf
V=f(xT,yT) 2 Vaf(zo yo)
II
(1-
U2
t=
When = L, Vaf(Fr.))) (=f(xo. yo) for all t.
Remark 1. Most popular adaptive stepsizes we mentioned before, such as Adam, AMSGrad and AdaGrad, have averaging functions satisfying the assumption in the lemma. Any point on the line LE is a stationary point for the above function, and the distance from point to this line is proportional its gradient norm, so the divergence gradient norm will also implies that of iterates. In the proof. we will also show that the averaged or best iterate will still diverge under the same condition. The lemma implies that for any given time-scale r, there exists a problem for which the non-nested algorithm does not converge to the stationary point, so they are not parumeter-agnostee
We compare non-nested and nested methods combined with different stepsizes schemes: Adam, AMSGrad, AdaGrad and fixed stepsize, on the function: - - + 2xy 2x². _ In the experiments of this section, we halt the inner loop when the (stochastic) gradient about y smaller than 1/t or the number iteration is greater than 1. We observe from Figure T that the thresholds for the non-convergence of non-nested methods (r = for adaptive methods and as predicted by the lemma. Although the adaptive methods admit smaller two-time-scale threshold than GDA this example, it is not universal phenomenon from our experiments in Section 4 Interestingly, nested adaptive methods are robust to different two-time-scales and always have the trend to converge to the stationary point.
for GDA) are exactly
3 Convergence Analysis of NeAda-AdaGrad
In this section, reveal the secret behind the robust performance of NeAda by providing the convergence guarantee for a representative member in the family. For sake of simplicity and clarity, we mainly focus on NeAda with AdaGrad. Adam-type mechanism can suffer from non-convergence already for nonconvex minimization despite its good performance in practice, Our result also sheds light on the analysis of other more sophisticated members such AMSGrad in the family.
NeAda-AdaGrad: Presented Algorithm NeAda-AdaGrad adopts the scalar AdaGrad scheme [3 for the r-uupdate in the outer loop and uses mini-hatch in the stochastic setting. For the inner loop for maximizing y, we run some adaptive algorithm for maximizing until some easily checkable stopping criterion is satisfied. We suggest two criteria here: at t-th outer loop: (I) the squard gradient mapping norm about is smaller than 1/(t+ + 1) in the deterministic setting, (II) the number of inner loop iterations reaches / 1 in the stochastic setting.
Algorithm 3 NcAAa-AAaGrad
1: Input: (zo, 1)1) No 0, 0,
2: for 0, 2.., do
3: from Vt-1 run an adaptive algorithm A for maximizing ((x,,) to obtain yr
(a) stopping criterion (deterministic): stop when - - Projj (v, + vyf(z v.))
+
(b) stopping criterion (stochastic): stop after + inner loop iterations.
4:
1++1 = 14 +
M Li=1
Σ
V V.F( Mt) where M are i.idd samples
5: Tt+1 2t
M
Di=l
V F( (Mat.1e:: (t)
6:
end for
For the purpose of theoretical analysis, mainly focus on the minimax problem of the form M under the nonconvex-strowe strongly strongly-concave concave (NC-SC) setting formally stated in the following assumptions.
Note that for other nonconvex minimax optimization beyond the NC-SC setting, even the convergence of adn-adaptive gradient methods has not been fully understood.
5

---

Assumption 3.1 (Lipschitz smoothness). There exists positive constant >> 0 such that max { [VV=]] (21.)) m1) v.. (12, (12, ,I (11,1)) ) Vyd (12. } & [[][=] =2ll + Il
y/a ll]
holds for all 21, 22,42 F 91. 1/2 V.
Assumption 3.2 (Strong-coneavity in y). There exists p > 0 such that: ((x.v) 2 (1, v2) + (Vyf(z, v1). - y2) + fl - y2ll2 3 Va E R. 91,92 E y.
For simplicity of notation, define = 1/11 the condition number, ((x) maxyey f(x,, y) as the primal function, and y (x()) arg maxy [(x y) as the optimal w.r.t x. Since the objective is
nonconvex about 2; we aim at finding e-stationary point (Te, Vr) such that R|| [ (Te, yt)ll Il s
and Eily- y (x+)]l < e, where the expectation is taken over the randomness in the algorithm.
3.1 Convergence in deterministic and stochastic settings
Assumption 3.3 (Stochastic gradients). FzF wi 3) and P yi are unbiased stochastic estimators of v J y) and y v) and have variances bounded by 0² 2 0.
(2,
We assume the unbiased stochastic gradients have the variance o², and the problem reduces to the deterministic setting when O. Now provide general analysis of the convergence for any adaptive optimizer used in the inner loop.
Theorem 3.1. Define the expected cumulative suboptimality of inner loops as E
E
Flu "x0""(0""""""
Under Assumptions 3.1
3.2
and 3.3
the output from Algorithm 3 satisfies
1=
2/00
1
2(A+E)
+ o
VA+E (A+
E
T
VT
VT
(MT)
where A
2A
kln, ( VI 2ndn)) [1+21 2log (Poly (T, n. V H. 0o 1. )-
7
Remark 2. The general analysis is built upon milder assumptions than existing work on AdaGrad in nonconvex optimization, not requiring either bounded gradient in [79 or prior knowledge about the smoothness modulus in (48). This theorem implies the algorithm attains convergence for the nonconvex variable x with any constant rj > and vo > that does not depend on any problem parameter, it is parameter-agnonte
Remark 3. Another benefit of this analysis is that the variance appears in the leading term T 7, which means the convergence rate can interpolate between the deterministic and stochastic settings. It implies a complexity of ((--2) in the deterministic setting and ((E in the stochastic setting for the primal variable long the accumulated suboptimality for the inner-loops & is Õ(1), regardless of the batch size M. However, M can control the number of outer loops and there affect the sample complexity for the dual variable.
In the next two theorems, we derive the total complexities, in the deterministic and stochastic settings, of finding e-stationary point by controlling the cumulative suboptimality & in Theorem 3. for subroutine A with specific convergence rate. In fact, we can also use any off-the-shelf adaptive optimizer for solving the inner maximization problem up to the desired accuracy. Note that (stochastic) GDmax fixes each inner-loop's s accuracy or steps to be related with μ., & and so that & can be easily bounded 50 64 In contrast, since do not have access to the problem parameters and Algorithm 3 gradually increases the inner-loop accuracy. In the proof of the following theorems, we will show that with our proposed stopping criteria and desired subroutines, & is bounded by Olog T).
Theorem 3.2 (deterministic). Suppose we have linearly-convergent subroutine A maximizing any strongly concave function h(-))
Ilu"~ - -- a1-
12
where y² is k-th iterate, yf is the optimal solution, and > O and 0 < 02 1 are constants that can depend on the parameters of h. Under the same setting as Theorem 3.1 with = 0, for Algorithm with M and a subroutine under stopping criterion there exists t" < Ô (c
such that (Ze- yc-) is e-stationary point. Therefore, the total gradient complexity is Ö 2)

---

Remark 4. This complexity is optimal in up to logarithmic term [86]. similar to GDA (50H. Note that many adaptive and aarameter-agnosee algorithms can achieve the linear rate when solving smooth and strongly concave maximization problems; to list a few, gradient ascent with backtracking
line-search (Z5), SC-AdaNGD (44) and polyak stepsize [30 54 66] [ Here we can also pick more
general subproblem accuracy in criterion that only needs to scale with 1/t.
Theorem 3.3 (stochastic). Suppose have wubb-linerryyconnveee
subroutine A for maximizing
any strongly concave function h(-): after K- = k+ 1 iterations
Blyy* - y y01 b b1 y 111 b2
k
where y is k-th iterate, y² is the optimal solution, and bi by O are constants that can depend on the parameters of h. Under the same setting as Theorem 3.1 for Algorithm 3 wiit M = -² and
subroutine A under the stopping criterion I, there exists t" S Ô (c-2) such that (Iz=, yt-) is an e-stationary point. Therefore, the total stochastic gradient complexity is O (c-
Remark 5. This Ô (c- complexity is nearly optimal in the dependence of t for stochastic NC-SC problems [16]. Here we set M = -2 for the simplicity of exposition, and a similar result also holds for gradually increasing M. The sublinear rate specified above for solving the stochastic strongly convex subproblem can be achieved by several existing parameter-agnoste algorithms under some additional assumptions, such as FREEREXMOMENTUX (T2) and Boin-Betting AL3 Parameter-free SGD ( is partially parameter-agnostee that only requires the stochastic gradient bound rather than parameter. Mukkamala and Hein [62] and Wang el al. 178) introduce the
the strongly-covvent variants of AdaGrad, RMSProp and Adam for strongly-comee online learning. but they need to know both gradient bounds and crongly-convexite parameter for setting stepsizes. We will show in the next subsection that AdaGrad with a slower decaying rate is parameter-agnostic We note that the analysis of this theorem is not the simple gluing of the outer loop and inner loop complexity, but requires more sophisticated control of the cumulative suboptimality E.
With the popularity of computational resource demanding deep neural networks, in both minimization and minimax applications, people find high probability guarantees for a single run of an algorithm useful 40 49]. Given the lack of such guarantee in the minimax optimization, we provide a high probability convergence result for FeAdd-AdaGrai in Appendix C which shows a similar sample complexity as Theorem 3.3 under the subGaussian noise.
3.2 Generalized AdaGrad for strongly-convex subproblem
We now introduce the generalized AdaGrad for minimizing strongly convex objectives, which can serve an adaptive subroutine for Algorithm g
without requiring knowledge the strongly convex parameter. We analyze it for the more general online convex optimization setting: at each round t, the learner updates its decision I₁, then it suffers loss fz() and receives the sub-gradient of fi. The generalized AdaGrad, described in Algorithm g keeps the cumulative gradient norm d/ and takes the stepsize n/ of with decaying rate AdaGrad 73] when a = 1, it reduced to the scalar version of SC-AdaGrad (2)
(0, When
1/2, it reduces to the scalar version of
Theorem 3.4. Consider Algorithm 4 for online convex optimization and assume that (i) fe is continuous and u-strongly convex, (ii) X convex and compact with diameter D; (ii) I|gell S G for every f. Then for O < a < 1 with any 7) > O, the regret of Algorithm g satisfies:
T-1 - - ZEX
I-a
S ca + da Up Σ
11
max
'Levy 44 needs to know the diameter of y. Hazan and Kakade k0. Loizou et al. kEl Orvieto et al. M
use polyak stepsize which requires knowledge of the minimum or lower bound of the function value. AdaGrad achieves the linear rate if the learning rate is smaller than (1/()) and O(1/k) rate otherwise [8] FFREEREXMOMENTE
(2) and Coin-Betting (3) can achieves Olog k/k) convergence rate when the stochastic gradient is bounded in y. If the subroutine has additional logarithmic dependence, it suffices to run the subroutine for log f (t) times using criterion II (see Appendix B
7

---

Algorithm 4 Generalized AdaGrad for Strongly-convex Online Learning
1: Input: 20, vo > and < 1.
2: for = 2,. do
3: receive 9: E (2s(
4: 1r+1 = + ||
5: 1e++1 Px Tr
6: end for
AMSGrad
AdaGrad
Noada-Adam
NeAda AMSGrad
NeAda-AdaGrad
NeAda-GD
57e 180 MET
(a) 0.01
(b) r = 0.03
(c) = 0.05
Figure Comparison between the two families of non-nested and nested adaptive methods on McCromick function with stochastic gradient oracles. = 0.01, 17" 0.01 and
17² ///"".
for with n 2 2p"
G²
T-1 E ( s ca + da log up + Σ 1alll TEX
T-1
max
where Co and da are constants depending on the problem parameters, a and np.
The theorem implies a logarithmic regret for the case a = 1, but the stepsize needs knowledge about problem's 's parameters μ and G: similar results shown for SC-AdaGrad 62 and SAdam (78). When a < 1, the algorithm becomes parameter-agnostic and attains an O(Tl-a) regret. Such parameter-agnootic phenomenon for smaller decaying rates also observed for SGD in stochastic optimization [20]. Proving the regret bound for the generalized AdaGrad with a < in the online setting is challenging, since the adversarial Se can lead "sudden" change in the stepsize. In the proof, we bound the possible number of times such "sudden" change could happen.
To the best of our knowledge, this is the first regret bound for adaptive methods with general decaying rates in the strongly convex setting. By maline-to-bated conversion [38], it can be converted to O(T-a) rate in the strongly convex stochastic optimization. Xie al. XD prove the (1/TT) convergence rate, or a linear convergence rate when the smoothness parameter known, for AdaGrad with a 1/2 in this setting, but under strong assumption Restricted Uniform Inequality of Gradients (RUIG) - that requires the loss function with respect to each sample to satisfy the error bound condition with some probability.
Experiments
To evaluate the performance of NeAda, we conducted experiments on simple test functions and real-world application of distributional robustness optimization (DRO). In all cases, we compare NeAda with the nos-nested adaptive methods using the same adaptive schemes. For notational simplicity, all figure legends, we label the non-nested methods with the names of the adaptive mechanisms used. We observe from all our experiments that: 1) while non-nested adaptive methods can diverge without the proper two-time-scale, NeAda with adaptive subroutine always converges; 2) when the non non-nested method converges, NeAda can achieve comparable or even better performance.

---

009
Manos Off -0 of
of
00-
Nabdbedaas for tull
Toa Xocei
15
143
Artiss
08
Alarr (4"
(181)
100
USD
2000
2000
4l0o Agrafleus calls
520 1030
8000
1000
2000
3300
2000 @ggaaBlerr cill
4001
1000
500
7001
(a) Test Accuracy
(b) Training Loss
Figure 3: Experimental results of distributional robustness optimization task on synthetic dataset.
4.1 Test functions
In Section 2 we have compared NeAda with non-nested methods on a quadratic function in Figure ! and the observations match Lemma 2.1 Now we consider more complicated function that is composed of McCormick function in x, a bilinear term, and a quadratic term in y.
5 f(x, v) sin( + x2) + (21 x²)² 2 マ 1 + T2 (vi vτ)
For this function, we compare the adaptive frameworks in the stochastic setting with Gaussian noise. As demonstrated in Figure 2 small, e.g., 17 /n 0.01, non-nested Adam, AMSGrad and GDA
non-nested methods are sensitive to the selection of the two-time-scale. When the learning rate ratio all fail to converge. We observe that GDA converges when the ratio reaches 0.03, while non-nested Adam and AMSGrad still diverge until 0.05. Although non non-nested adaptive methods require a smaller ratio than GDA in Lemma 2.1 this example illustrates that adaptive algorithms sometimes can be more sensitive the time separation. In comparison, NeAda with adaptive subroutine always converges regardless of the learning rate ratio.
4.2 Distributional robustness optimization
To justify the effectiveness of NeAda on real-world applications, we carried out experiments on distributionally robust optimization 771 where the primal variable is the model weights to be learned by minimizing the empirical loss while the dual variable is the adversarial perturbed inputs. The dual variable problem targets finding perturbations that maximize the empirical loss but not far away from the original inputs. Formally, for model weights x and adversarial samples we have:
" Σ f((,y)) 7 -
min
max Vol
f(z v), where f(a,y) n
where n the total number of training samples, v, is the i-th original input and fa is the loss function for the i-th sample. 7 is trade-off parameter between the empirical loss and the magnitude of and following use both stopping criterion I with
perturbations. When y is large enough, this problem is nonconvex wwwoooveesstoogll-coneeee the same setting [ 70,, we set r = 1.3. For NeAda, stochastic gradient and criterion II in our experiments. For the results, we report the training loss and the test accuracy adversarial samples generated from fast gradient sign method (FGSM) [26]. FGSM can be formulated as Tadv = I + c sign (v=((x), where is the noise level. To get reasonable test accuracy, NeAda with Adam as subroutine compared with Adam with fixed 15 inner loop iterations, which is consistent with the choice of inner loop steps in 77. and such choice obtains much better test accuracy than the completely non-nested Adam. Our experiments include synthetic dataset and MNIST with code modified from 56
Results on Synthetic Dataset. We use the same data generation process as in 71). The inputs are 2-dimensional i.i.d. random Guassian vectors, i.e., I; (0, I2), where 12 is the 2 x 2 identity matrix. The corresponding y4 is defined as y sign(]|=::le V2). Data points with norm in range

---

(a) c 0.1
(b) E 0.05
(c) 0.02
(d) loss
Figure 4: Results of distributional robustness optimization task on MNIST. is the noise level.
(v2/1.3, 1.3v2) are removed to make the classification margin wide. 10000 training and 4000 test data points are generated for our experiments. The model we use a three-layer MLP with ELU activations.
As shown in Figure 5(a] when the learning rates are set different scales, ie., 17" = 0.01, 0.08 (red curves in the figure), both methods achieve reasonable test errors. In this case, NeAda has higher test accuracy and reaches such accuracy faster than Adam. we change the learning rates to the same scale, i.e., ryth 0.01, n7² = 0.01 (blue curves in the figure), NeAda retains good accuracy while Adam drops to an unsatisfactory performance. This demonstrates the adaptivity and less-sensitivity to learning rates of NeAda. In addition, Figure 3(b illustrates the convergence speeds on the loss function, and NeAda (solid lines) always decreases the loss faster than Adam. Note that Adam with the same learning rates converges to a lower loss but suffers from overfitting, as shown in Figure ((a) that its test accuracy is only about 68%.
Results MNIST Dataset. For MNIST, we use convolutional neural network with three convolutional layers and one final fully-connected layer. Following each convolutional layer, ELU activation and batch normalization are used.
We compare NeAda with Adam under three different noise levels and the accuracy is shown in Figures (a) to (C)
Under all noise levels, NeAda outperforms Adam with the same learning rates. When we have proper time-scale separation (the red curves), both methods achieve good test accuracy. and AdA achieves higher accuracy and converges faster. After we change to the same learning rates for the primal and dual variables (the blue curves), the accuracy drop of NeAda slighter compared to Adam, especially when 0.1. As for the training loss shown in Figure [dd NeAda (the solid curves) is always faster at the beginning. We also observed that with proper time-scale separation, NeAda reaches lower loss.
5 Conclusion
Both non-nested and nested adaptive methods are popular in nonconvex minimax problems, e.g., the training of GANs. In this paper, we demonstrate that non-nested algorithms may fail to converge when the time-scale separation is ignorant of the problem parameter even when the objective is strongly-concave in the dual variable with noiseless gradients information. We propose fixes to this problem with family of nested Setorithms-NeAAeee that nests the max oracle of the dual variable under an inner loop stopping criterion. The proper stopping criterion will help to balance the outer loop progress and inner loop accuracy. Adda-rd attains the near-optimal complexity without setting. It can be a
a priori knowledge of problem parameters in the sarcoovee-strongyy-oooo future direction design parameter-agnostic algorithms for nonconvex-concave minimax problems or more general regimes by leveraging recent progress in nonconvex minimax optimization and the adaptive analysis in this paper. Another interesting direction investigate the convergence behavior of Adam-type algorithms with general decaying rates in the strongly convex online optimization.
Acknowledgement
This work was supported by an ETH Research Grant funded through the ETH Zurich Foundation.
10

---

References
[1] K. Antonakopoulos. Adaptive extra-gradient methods for min-max optimization and games. In ICLR, volume page 2021.
[2] K. Antonakopoulos and P. Mertikopoulos. Adaptive first-order methods revisited: Convex minimization without lipschitz requirements. NeurIPS, 34, 2021.
[3] K. Antonakopoulos, V. Belmega, and P. Mertikopoulos, An adaptive mirror-prox method for variational inequalities with singular operators. NeurIPS, 32, 2019.
[4] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In ICML, pages 214-223, PMLR, 2017.
[5] P. Auer, N. Cesa-Bianchi, and C. Gentile. Adaptive and self-confident on-line learning algo- rithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
[6] F. Bach and K. Y. Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. In COLT, pages 164-194. PMLR, 2019.
[7] A. Beck. First-order methods in optimization. SIAM, 2017.
[8] R. I. Bot and A. Böhm. Alternating proximal-gradice steps for (stochastic) nonconvex-coneave minimax problems. arXiv preprint arXiv:2007.13605, 2020.
[9] Y. Carmon and O. Hinder. Making sgd parameter-free. arXiv preprint arXiv:2205.02160) 2022.
[10] T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. NeurlPS, 34, 2021.
[11] X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In ICLR, 2019.
[12] A. Cutkosky and K. A. Boahen. Stochastic and adversarial online learning without hyperparam eters. In NeurIPS, volume 30, 2017.
[13] A. Cutkosky and F. Orabona. Black-box reductions for parameter-free online learning in banach spaces. In COLT, pages 1493-1529, PMLR, 2018.
[14] B. Dai, N. He, Y. Pan, B. Boots, and L. Song. Learning from conditional distributions via dual embeddings. In AISTATS, pages 1458-1467, PMLR, 2017.
[15] J. Diakonikolas. Halpern iteration for near-optimal and parameter-free free monotone inclusion and strong solutions to variational inequalities. COL.T, pages 1428-1451. PMIR, 2020.
[16] Z. Dou and Y. Li. On the one-sided convergence of adam- type algorithms in non-convex non-concave min-max optimization. arXiv preprint arXiv:2 1099. 14213, 2021.
[17] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[18] A. Ene and H. L. Nguyen. Adaptive and universal algorithms for variational inequalities with optimal convergence. arXiv preprint arXiv:2010.07799, 2020.
[19] T. Fiez, I. Ratliff, E. Mazumdar, E. Faulkner, and A. Narang. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. NeurIPS, 34, 2021.
[20] X. Fontaine, V. De Bortoli, and A. Durmus. Convergence rates and approximation results for sgd and its continuous-timm counterpart. COLT, pages 1965-2058. PMLR, 2021.
[21] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and Lempitsky. adversildverssarill training of neural networks. The journal of machine learning research, 17(1):2096-208) 2016.

---

[22] A. V. Gasnikov, P. Dvurechensky, F. S. Stonyakin, and A. A. Titov. An adaptive proximal method for variational inequalities. Computational Mathematics and Mathematical Physies, 59 (5):836-84) 841, 2019.
[23] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In ICLR, 2019.
[24] I. Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprint arXiv:1701.00166, 2016.
[25] I. Goodfellow, J. Pouget-Abadie, M. Mirza, Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. NeurlPS, 27, 2014.
[26] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572,220 2014.
[27] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of wasserstein gans. NeurIPS, 30, 2017.
[28] Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. A novel convergence analysis for algorithms of the adam family and beyond. arXiv preprint arXiv:2104. 14840, 2021.
[29] N. J. Harvey, C. Liaw, and S. Randhawa. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv preprint arXiv: 1909.00843, 2019.
[30] E. Hazan and S. Kakade. Revisiting the polyak step size. arXiv preprint wrXiv:1905.003// 2019.
[31] G. Hinton, N. Srivastava, and K. Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. 2012.
[32] J. Ho and S. Ermon. Generative adversarial imitation learning. NewrlPS, 29, 2016.
[33] F. Huang and H. Huang. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. arXiv preprint arXiv:2106. 16101, 2021.
[34] F. Huang, X. Wu, and H. Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. NeurlPS, 34, 2021.
[35] Jain, D. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. In COLT, pages 1752-1755. PMLR, 2019.
[36] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.003336 2019.
[37] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68 (2):1229, 2021.
[38] S. M. Kakade and A. Tewari. On the generalization ability of online strongly convex program- ming algorithms. NeurlPS, 21, 2008
[39] A. Kavis, K. Y. Levy, F. Bach, and V. Cevher. Unixgrad: universal, adaptive algorithm with optimal guarantees for constrained optimization. NeurIPS, 32, 2019.
[40] A. Kavis, K. Y. Levy, and V. Cevher. High probability bounds for class of nonconvex algorithms with adagrad stepsize. In ICLR, 2022.
[41] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[42] S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler approach to obtaining an (I/t) conver- gence rate for the projected stochastic subgradient method. arXiv preprint arXiv: 1 20002, 2012.
[43] Y. LeCun. The mnist database of handwritten digits. http://yann lecun. com/exdb/nnist// 1998.
12

---

[44] K. Levy. Online to offline conversions, universality and adaptive minibatch sizes. NewrIPS, 30, 2017.
[45] K. Y. Levy, A. Yurtsever, and V. Cevher. Online adaptive methods, universality and acceleration. NeurIPS, 31, 2018.
[46] H. Li, Y. Tian, J. Zhang, and A. Jadbabaie. Complexity lower bounds for nonconvex-stronglly concave min-max optimization. NeurIPS, 34, 2021.
[47] H. Li, F. Farnia, S. Das, and A. Jadbabaie, On convergence of gradient descent ascent: tight local analysis. In ICML, pages 12717-12740. PMLR, 2022.
[48] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In AISTATS, pages 983-992 PMLR, 2019.
[49] X. Li and F. Orabona. high probability analysis of adaptive SGD with momentum. CoRR, abs/2007. 14294, 2020.
[50] T. Lin, C. Jin, and Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML, pages 6083-6093, PMLR, 2020.
[51] L. Liu, H. Jiang, P. He, W. Chen, X. Liu, Gao, and J. Han. On the variance of the adaptive learning rate and beyond. In ICLR, 2020.
[52] M. Liu, Y. Mroueh, J. Ross, W. Zhang, Cui, P. Das, and Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In ICLR, 2020.
[53] M. Liu, H. Rafique, Q. Lin, and T. Yang. First-order convergence theory for weakly-convers weakly-concave min-max problems. Journal of Machine Learning Research, 22 22(169):1-34 2021.
[54] N. Loizou, S. Vaswani, H. Laradji, and S. Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In AISTATS, pages 1306- 1314. PMLR, 2021.
[55] S. Lu, I. Tsaknakis, M. Hong, and Y. Chen. Hybrid block successive approximation for one- sided non-convex min-max problems: algorithms and applications. IEEE Transactions Signal Processing, 68:3676-3691, 2020.
[56) L. Lv. principled adversarial training". deproouciig--eertiffabbbli
Reproducing "certifying some
robustness with https: https://githie //tp://bbbtt.. Lts//oouuussssse
distributional
robustsssssssssssssssussssssssss 2019.
[57] L. Madden, E. Dall' Anese, and Becker. High-probability convergence bounds for non-convex stochastic gradient descent. arXiv preprint arXiv:2006.05610, 2020.
[58] Y. Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming,
1 184(1):383-410, 2020.
[59] H. B. McMahan and M. Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv: 2010.
[60] A. Modi, Chen, A. Krishnamurthy, N. Jiang, and A. Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.070035, 2021.
[61] E. Moulines and F. Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. NeurlPS, 24, 2011.
[62] M. C. Mukkamala and M. Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In ICML, pages
PMLR, 2017.
[63] A. Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251 2004.
13

---

[64] M. Nouiched, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving class of non- convex min max-mmxxea games using iterative first order methods. NeurIPS, 32, 2019.
[65] Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
[66] A. Orvieto, S. Lacoste-Julien, and Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. arXiv preprint urXiv:2205.0458. 2022.
[67] J.-S. Pang. A posteriori error bounds for the linearly-constrained variational inequality problem. Mathematics of Operations Research, 12(3):474-44, 1987.
[68] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In ICML, pages 1571-1578, 2012.
[69] S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In ICLR, 2018.
[70] O. Sebbouh, M. Cuturi, and G. Peyré. Randomized stochastic gradient descent ascent. In A/STATS, pages 2941-2969, PMLR, 2022.
[71] A. Sinha, H. Namkoong, and J. C. Duchi. Certifying some distributional robustness with principled adversarial training. In ICLR, 2018.
[72] F. Stonyakin, A. Gasnikov, P. Dvurechensky, M. Alkousa, and A. Titov. Generalized mirror prox for monotone variational inequalities: Universality and inexact oracle. arXiv preprint arXiv:1806.0511 2018.
[73] M. Streeter and H. McMahan. Less regret via online conditioning. arXiv preprint
1002::1002.4800 2010.
[74] F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. In ICLR, 2018.
[75] S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. NeurIPS, 32, 2019.
[76] S. Vaswani, F. Kunstner, I. H. Laradji, S. Y. Meng, M. W. Schmidt, and S. Lacoste-Julies Adaptive gradient methods converge faster with over-parameterization (and you can do line-search). ArXiv, 0bbs22006006833 2020.
[77] S. Vaswani, B. Dubois- and R. Babanezhad. Towards noise-adaptive, problem-adaptivy stochastic gradient descent. arXiv preprint arXiv:2110. 2021.
[78] G. Wang, S. Lu, Q. Cheng, W.-w. Tu, and L. Zhang. Sadam: A variant of adam for strongly convex functions. ICLR, 2020.
[79] R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In ICML, pages 6677-6686. PMLR, 2019.
[80] Y. Xie, X. Wu, and R. Ward. Linear convergence of adaptive stochastic gradient descent. In AISTATS, pages 1475-1485. PMLR, 2020.
[81] J. Yang, S. Zhang, N. Kiyavash, and N. He. catalyst framework for minimax optimization. NeurlPS, 33:5667-5678, 2020.
[82] J. Yang. A. Orvieto, A. Lucchi, and N. He. Faster single-loop algorithms for minimax optimiza- tion without strong concavity. In AISTATS, pages 5485-55177 PMLR, 2022.
[83] M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimization. NeurlPS, 31, 2018
[84] M. Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 12Xi::1112.70.) 2012.
14

---

[85] J. Zhang, P. Xiao, R. Sun, and Z. Luo. A single-loop smoothed gradient descent- algorithm for nonconvex-coneee min-max problems. NeurIPS, 33:7377-7389, 2020.
[86] Zhang, J. Yang. Guzmán, Kiyavash, and N. He. The complexity of nonconvex-strongly. concave minimax optimization. In UAI, pages 482-492. PMLR, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We con- sider our work fundamental research on optimization and there is no foreseeable societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include the code in supplemental materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] Our experiments do not require large resource of computation.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] In the experiment section.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes] We include our code in supplemental materials.
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "m0NzWmQwfxe", "reviewer": "Reviewer_MNNk", "summary": "This paper proposes an adaptive algorithm for non-convex-strongly-concave minimax optimization, where the step size does not depend on the problem parameters, e.g., $L$ of $L$-smoothness, and $\\mu$ of $\\mu$-strong concavity.\nThe algorithm has two loops: in the inner loop, the corresponding strongly-concave problem of $y$ given $x$ is approximately optimized by executing an off-the-shelf adaptive algorithm for a sufficiently number of iterations; while in the outer loop, an adaptive gradient descent step is used to update $x$.\n", "questions": "see above", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic of developing adaptive methods with theoretical guarantees is interesting. However, at the current point, I hesitate to recommend the acceptance for the following reasons, and I would like to get some clarifications.\n\n1. While I understand the goal in this paper is to get an adaptive algorithm that does not need the knowledge of the problem parameters, getting a stationary-point guarantee on x for the class of non-convex-strongly-concave minimax optimization via applying adaptive methods on both x and y seems a bit straightforward to me, in my opinion. It would be more helpful for the evaluation if the challenge in the design and analysis of the algorithm can be highlighted.\n\n2. Remark 2 for Theorem 3.1 says \"the algorithm attains convergence for the nonconvex variable x with any choice of $\\eta >0$\".\nBut from line 185, if we set $\\eta = T$, then $A=\\Omega (T)$ and therefore the second term \n$\\frac{\\sqrt{A+ ...} }{\\sqrt{T}}$\non the r.h.s. of the bound of the expected gradient norm in Theorem 3.1 will be $\\Omega(1)$. So the convergence does not hold for any step size $\\eta$.\n\n\n3. The purpose of introducing Algorithm 4 is not clear to me. Remark 5 mentions that FreeFREXMomenetum and Coin-Betting can be used for the inner loop of Algorithm 2. Given this, what is the point of having Algorithm 4? \n\n\n4. (The first inequality on Page 22) How to get the last term on the r.h.s. of the first inequality on Page 22, i.e., $2 \\kappa^2 \\\\| x_t - x_{t+1} \\\\|^2$? \nIt seems to me that the last term arises from bounding the last term on the last inequality on Page 21, i.e., by bounding $\\\\| y^*(x_t) -  y^*(x_{t+1}) \\\\|^2$. How to use Lemma A.1 to get the result?\n\n\nMinor:\n\nThere seems a typo in the definition of Assumption 3.2, i.e., $\\nabla_x f(x,y_2)$ <- $\\nabla_y f(x,y_2)$.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NAfeFuw09dj", "reviewer": "Reviewer_VNUE", "summary": "Contribution summary:\nThe authors investigate two frameworks for adaptive minimax optimization: one is a simple (non-nested) adaptive framework, which performs one step of update of x and y simultaneously with adaptive gradients; the other is the nested adaptive (NeAda) framework and\nprovide the convergence analysis for a representative of NeAda that uses AdaGrad step size. In addition, there are two other complementary contributions which are a proposed AdaGrad step size and high probability convergence results. The authors also include empirical results for comparison with existing algorithms.", "questions": "N/A", "limitations": "See weaknesses.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- First adaptive nonconvex minimax optimization algorithm? There exists literature for adaptive minimax optimization but not for nonconvex.\n- The existing NCSC optimization algorithm has O(1/eps^2) oracle complexity and O(1/eps^4) sampling complexity. While the algorithm achieved the same rate, it does not require knowledge of the parameters like existing algorithms. The analysis of the algorithms does not follow trivially from existing literature. Some results such as theorem 3.1 also do not require common assumptions such as bounded gradient.\n- Showed an example where GDA/non-nested methods does not work without prior knowledge of the parameters.\n\n\nWeaknesses:\nIt incorporates AdaGrad step size which is widely known, but it seems the theoretical contribution is significant enough.\n\nThe algorithm does not necessary converge faster existing algorithms but it does have the advantage of being robust.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H2asX4Wq_sG", "reviewer": "Reviewer_2KvC", "summary": "The paper proposes an adaptive framework, called NeAda, for solving nonconvex-strongly concave (NC-SC) minimax problems which achieves the best-known rates both in the deterministic and stochastic settings up to logarithmic factors, while being agnostic to the problem parameters. These results are achieved when the NeAda framework is run with AdaGrad for the minimizing player. They also provide a set of independent but complementary results such as non-convergence of gradient descent ascent, the high probability convergence of NeAda-AdaGrad and regret bounds for a generalized parameter-agnostic AdaGrad template. The authors also provide a set of experiments demonstrating advantages of their framework.", "questions": "__Small comments:__\n- Theorem 3.1 is referred to as Lemma 3.1 in line 199. It is referred to as a \"lemma\" in multiple places in the paper.\n- What is $\\xi_t$ in Algorithm 4, line 4?\n\n__Questions:__\n- Lemma 2.1 provides divergence result in terms of the last iterates. I wonder whether there would be any conditions on the learning rate ratios that implies divergence when we consider the average iterates.\n- As far as I understand, Ne-Ada framework proposes a concrete parameter-agnostic subroutine for the _minimizing_ player with adaptive step-sizes, however, it assumes the existence of a parameter-agnostic linearly-convergent algorithm $\\mathcal A$ without proposing a proof for a particular algorithm $\\mathcal A$. Is there any linearly-convergent parameter-agnostic algorithm that works under the precise set of assumptions that the authors propose in the Theorem statement 3.1?\n- Although the analysis of NeAda requires a linearly-convergent algorithm to achieve the almost-optimal rates, the regret rate in Theorem 3.4 does not imply that Algorithm 4 converges linearly. Hence it may not satisfy the theorem statement. Is there an immediate extension of the regret rate in Theorem 3.4 that would yield a linear rate in the offline setting? To my knowledge there is no such conversion scheme.\n", "limitations": "One comments I have is with respect to subroutine $\\mathcal A$ in Algorithm 3. Authors talk about some candidates but there is no clear discussion of whether any such algorithm satisfies the set of assumptions of Theorem 3 while being parameter-agnostic. I would suggest to have a more thorough discussion on this. Other than that, I think authors discuss the limitations and shortcomings of their results with respect to the literature.\n\nTo my knowledge, this work does not seem to have any potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Note__: _I was assigned to the paper as an emergency reviewer, therefore I haven’t had long enough time to have a detailed look at the paper and the supplementary. My score is given with caution based on the points that I am confused about. I am willing to engage in discussions with the authors and possibly update my score accordingly. In case I made mistakes or misinterpreted anything while evaluating the work, please indicate them for me so that I will provide a better review and fair judgment of the paper._\n\nThe paper is structured in a good way; listing the contributions early on and building upon the idea of parameter-freeness. The possible empirical advantages of the nested framework that runs for multiple ascent iteration per update of the minimizing player are also presented to have a nice basis for the theoretical claims.\n\nThe proposed setting with the set of assumptions relaxes some of the restrictive assumptions in the literature, one of which is the removal of bounded stochastic gradients assumption. This assumption appears frequently in the analysis of adaptive AdaGrad-type methods and its removal is a good step forward in my opinion.\n\nLemma 2.1 provides a set of nice but fairly expectable results (with analogous results known for convex-concave setting). With Figure 1, I think it complements one of the main arguments around the learning rate ratios and shows how NeAda framework is less sensitive to ill-approximation of such a ratio.\n\nPresentation of Theorems 3.1, 3.2 and 3.3 are accompanied with relevant remarks and clarifications. The convergence rate is noise-adaptive, which I think is important.\n\nAs an independent results, Theorem 3.4 is a nice contribution in terms of parameter-free online learning and adaptive regret bounds for strongly convex losses.\n\nExperimental results are somewhat encouraging; Figure 2 demonstrates possible scenarios where the nested algorithm proves useful, while Figure 3 gives some clues about the performance improvements it would offer for optimization/generalization tasks.\n\n--\n\nFrom the very beginning, it must be clarified for which adaptive algorithms the paper provides the convergence analysis and rates under the nested structure. The first bullet point at line 56 suggests that NeAda framework provably works with multiple adaptive algorithms, whereas the paper focuses on AdaGrad and its theoretical behavior. Although the second bullet point clearly states that the almost-optimal rates are achieved for NeAda-AdaGrad, I would suggest to make it clear at all parts of the paper that theoretical results are presented for NeAda-AdaGrad only.\n\nThe statement of Theorem 3.2 is not precise enough; it is not clear what quantities are bounded and how it implies the total sample complexity (e.g., no clear reference to $\\mathcal E$). I would suggest the same for Theorem 3.3. I believe using the versions from the appendix, or some modification of theirs, would be better. \n\nThe quantity $\\mathcal E$ is actually a crucial part of the total sample complexity, and I would suggest to talk about it before Theorem 3.1. This would give some grounds for the results in Theorem 3.2 and 3.3 while explaining implications of the convergence rate in Theorem 3.1\n\nOne important contribution of this paper is enabling any linearly-convergent algorithms for strongly convex-minimization to be used in the NeAda-AdaGrad algorithm. However, this also creates a problem. From my understanding, parameter-agnostic property depends on the subroutine $\\mathcal A$ and its properties. As long as there exists a parameter-free algorithm that converges linearly under the assumptions of Theorem 3.1 for strongly convex minimization problems, the claims hold. However, I am not sure whether such an algorithm exists. Could the authors please clarify this point for me? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept