TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization
Authors: Xiang Li
Junchi YANG
Niao He
Venue: ICLR 2023 poster (2023)
Keywords: optimization
minimax optimization
adaptive algorithm

Abstract: Adaptive gradient methods have shown their ability to adjust the stepsizes on the fly in a parameter-agnostic manner, and empirically achieve faster convergence for solving minimization problems. When it comes to nonconvex minimax optimization, however, current convergence analyses of gradient descent ascent (GDA) combined with adaptive stepsizes require careful tuning of hyper-parameters and the knowledge of problem-dependent parameters. Such a discrepancy arises from the primal-dual nature of minimax problems and the necessity of delicate time-scale separation between the primal and dual updates in attaining convergence. In this work, we propose a single-loop adaptive GDA algorithm called TiAda for nonconvex minimax optimization that automatically adapts to the time-scale separation. Our algorithm is fully parameter-agnostic and can achieve near-optimal complexities simultaneously in deterministic and stochastic settings of nonconvex-strongly-concave minimax problems. The effectiveness of the proposed method is further justified numerically for a number of machine learning applications.

Published as a conference paper at ICLR 2023
TIADA: A TIME-SCALE ADAPTIVE ALGORITHM FOR NONCONVEX MINIMAX OPTIMIZATION
Xiang Li, Junchi Yang, Niao He
Department of Computer Science, ETH Zurich, Switzerland (xiang. li, junchi yang, niao. he ) @inf. ethz.ch
ABSTRACT
Adaptive gradient methods have shown their ability to adjust the stepsizes the fly in a parameter-agnostic manner, and empirically achieve faster convergence for solving minimization problems. When it comes nonconvex minimax optimiza- tion, however, current convergence analyses of gradient descent ascent (GDA) combined with adaptive stepsizes require careful tuning of hyper-parameters and the knowledge of problem-dependen parameters. Such a discrepancy arises from the primal-dual nature of minimax problems and the necessity of delicate time- scale separation between the primal and dual updates in attaining convergence. In this work, we propose a single-loop adaptive GDA algorithm called TiAda for nonconvex minimax optimization that automatically adapts to the time-scale sep- aration. Our algorithm fully complexities simultaneously in deterministic and stochastic settings of nonconvex- strongly-concave minimax problems. The effectiveness of the proposed method is further justified numerically for number of machine learning applications.
-egnostt- and can achieve near-optimal
INTRODUCTION
Adaptive gradient methods, such AdaGrad (Duchi al. 2011 Adam (Kingma & Ba, 2013) and AMSGrad (Reddi et al.) 2018), have become the default choice of optimization algorithms in many machine learning applications owing their robustness hyper-parameter selection and fast em- pirical convergence. These advantages are especially prominent in nonconvex regime with success in training deep neural networks (DNN). Classic analyses of gradient descent for smooth functions require the stepsize to be less than 2/7, where is the smoothness parameter and often unknown for complicated models like DNN. Many adaptive schemes, usually with diminishing stepsizes based on cumulative gradient information, hyper- parameter tuning (Ward et al., 20200] Xie et al. 2020). Such tuning- free algorithms are called parameter-agnostee as they do not require any prior knowledge of problem-specifh parameters, e.g., the smoothness or strong-convexity parameter.
adapt to such parameters and thus reducing the burden of
In this work, aim to bring the benefits of adaptive stepsizes to solving the following problem: min max [(x y) Rger [F(x, y: E)]
ZER4 yEy
where P is an unknown distribution from which we can drawn i.i.d. samples, y C Rd is closed and convex, and f Rdd x Rd + R is nonconvex in x. We call the primal variable and y the dual variable. This minimax formulation has found vast applications in modern machine learning, notably generative adversarial networks (Goodfellww et al. 2014 Arjovsky al., (017). adversar- ial learning (Goodfellow et al. 2015 Miller et al. 2020). reinforcement learning (Dai et al. 2017]
train- ing (Ganin et al. 2016)). etc. Albeit theoretically underexplored, adaptive methods widely de- combination with popular minimax optimization algorithms such as (stochastic) gradient descent ascent (GDA), extragradient (EG) (Korpelevich) 1976), and optimistic GDA (Popov) 1980 Rakhlin & Sridharan 2013); see, e.g., (Gulrajani et al. Daskalaki et al. 2018 Mishchenko al. 2020 Reisizadeh et al. 2020), just to list few.
Modi et al., (2021) 1b. sharpness-aware minimization (Foret et al. 202T). Nomain-adversane
ployed in these applications
While it seems natural to directly extend adaptive stepsizes to minimax optimization algorithms, a recent work by Yang et al. (2022a) pointed out that such schemes may not always converge without

---

Published as a conference paper at ICLR 2023
TIAGa
1144 MaGrod
TiMTa
Stage
Boge
AdaCCed
-15
100-
1/ee
-30
Stage I?
wie t//rf nuchos 1/f
0:25-
8030
Strallon tale
(a) trajectory
(b) effective stepsize ratio
(c) convergence
Figure I:
Comparison between TiAda and vanilla GDA with AdaGrad stepsizes (labeled as Ada- Grad) the quadratic function ( with L = 2 under a poor initial stepsize ratio, i.c., 17"
/np" ////// 5.
Here, Ti. and nj are the effective stepsizes respectively for x and y, and x. is the condition numbe (a) shows the trajectory of the two algorithms and the background color demonstrates the function value f(x, y). In (b), while the effective stepsize ratio stays unchanged for AdaGrad, TiAda adapts to the desired time-scale separation 1/x, which divides the training process into two stages. In (c), after entering Stage II, TiAda converges fast, whereas AdaGrad diverges.
knowing problem-dee roolemmdeppendent parameters. Unlike the case of minimization, convergent analyses of GDA and EG for nonconvex minimax optimization are subject to time-scale separation (Bog & Böhm 2020: Lin al. 2020a, (Sebbouh et al.. 2022 Yang al. 2022b) the stepsize ratio of primal and dual variables needs to be smaller than a problem-dependent threshold - which is re- cently shown to be necessary even when the objective is strongly concave in y with true gradients (Li iet al. 2022). Moreover, Yang et al. (2022a) showed that GDA with standard adaptive stepsizes, that chooses the stepsize of each variable based only on the (moving) average of its own past gradients, fails to adapt to the time-scale separation requirement. Take the following conconvex-strongle concave function as concrete example:
1
I
f(x, v) = -" + Lay 2 xx
where > constant. Yang et al. (2022a) proved that directly using adaptive stepsizes like AdaGrad, Adam and AMSGrad will fail to converge if the ratio of initial stepsizes of and (denoted as 17" and 17²) is large. We illustrate this phenomenon in Figures [[a]] and [[c] where
AdaGrad diverges. To sum up, adaptive stepsizes designed for minimization, are not time-scale adaptive for minimax optimization and thus not parameter-agnostic.
To circumvent this time-scale separation bottleneck. YYnng et al. (2022a) introduced an adaptive al- gorithm, NeAda, for problem (T) with nonconvex-strowe wwwreee--stooggy-coneteee
objectives. NeAda is a two-loop algorithm built upon GDmax (Lin et al. (220a) that after one primal variable update, updates the dual variable for multiple steps until a stopping criterion is satisfied in the inner loop. Although the algorithm is agnostic the smoothness and strong-concavity parameters, there are several lim- itations that may undermine its performance in large-scale training: (a) In the stochastic setting, it gradually increases the number of inner loop steps (k steps for the k-th outer loop) improve the inner maximization problem accuracy, resulting in a possible waste of inner loop updates if the maximization problem is already well solved; (b) NeAda needs large batchsize of order 52 (e ²) to achieve the near-optimal convergence rate in theory; (c) It is not fully adaptive to the gradient noise, since it deploys different strategies for deterministic and stochastic settings.
In this work, we address all of the issues above by proposing TiAda (Time-scale Adaptive Algo- rithm), a single-loop algorithm with time-scale adaptivity for minimax optimization. Specifically, one of our major modifications is setting the effective stepsize, i.e., the scale of (stochastic) gradient used in the updates, of the primal variable to the reciprocal of the maximum between the primal and dual variables' second moments, i.e., the sums of their past gradient norms. This ensures the effective stepsize ratio of and being upper bounded by a decreasing sequence, which eventually reaches the desired time-scale separation. Taking the test function (2) as example, Figure T illus- trates the time-scale adaptivity of TiAda: In Stage I, the stepsize ratio quickly decreases below the threshold: in Stage II, the ratio is stabilized and the gradient norm starts converge fast.
We focus on the minimax optimization I that is strongly-concave in y, since other nonconvex regimes are far less understood even without adaptive stepsizes. Moreover, near stationary point
Pleasse refer to Section 2 for formal definitions of initial stepsize and effective stepsize. Note that the initial stepsize ratio, 1f" /n7", does not necessarily equal the first effective stepsize ratio, n/ /1/-
2

---

Published as a conference paper at ICLR 2023
may not exist in nonnonecev (NC-NC) problems and finding first-order local minimax point is already PPAD PPAD-complete (Daskalakis et al. 2021). We consider a constraint for the dual variable, which is common in convex optimization with adaptive stepsizes (Levy 2017 Levy al.) 2018) and in the minimax optimization with non-adaptive stepsizes (Lin et al. 2020a). In summary, contributions are follows:
We introduce the first single-loop and fully parameter-agnostic adaptive algorithm, TiAda, for nonconvex- wwtneeee-ttoogly-coccaaa (NC-SC) minimax optimization. It adapts to the necessary time- scale separation without large batchsize or any knowledge of problem-dependant parameters or target accuracy. TiAda finds e-stationary point with an optimal complexity of O (E-2) in the deterministic case, and a near-optimal sample complexity of O (c-(4+)) for any small > in the stochastic case. It shaves off the extra logarithmic terms in the complexity of NeAda with AdaGrad stepsize for both primal and dual variables (Yang et al. 2022a). TiAda is proven to be noise-adaptive, which is the first of its kind among nonconvex minimax optimization algorithms.
While TiAda based on AdaGrad stepsize, we generalize TiAda with other existing adaptive schemes, and conduct experiments on several tasks. The tasks include 1) test functions by Yang jt al.] (2022a) for showing the nonconvergence of GDA with adaptive schemes under poor initial stepsize ratios, 2) distributional robustness optimization (Sinha et al.) 2018) MNIST dataset with a NC-SC objective, and 3) training the NC-NC generative adversarial networks on CIFAR- 10 dataset. In all tasks, show that TiAda converges faster and is more robust compared with NeAda or GDA with other existing adaptive stepsizes.
1.1 RELATED WORK
Adaptive gradient methods. AdaGrad brings about an adaptive mechanism for gradient-based optimization algorithm that adjusts its stepsize by keeping the averaged past gradients. The original AdaGrad was introduced for online convex optimization and maintains coordinate- -wise stepsizes. In nonconvex stochastic optimization,
GlaGrad-Norm with one learning rate for all directions is shown
to achieve the same complexity as SGD (Ward et al. 2020 Li & Orabona 2019), even with the high probability bound (Kavis et al.] [022]] Li & Orabona 2020). In comparison, RMSProp (Hinton) al. 2012) and Adam (Kingma& Ba| 2015) use the decaying moving average of past gradients, but may suffer from divergence (Reddi et al. 2018). Many variants of Adam are proposed. and wide family of them, including AMSGrad, are provided with convergence guarantees (Zhou et al.) 2018 Chen et al. |018 Défossez et al. 2020; Zhang et al. (022b)). One of the distinguishing traits of adaptive algorithms is that they can achieve order-optimal rates without knowledge about the problem parameters, such smoothness and variance of the noise, even in nonconvex optimization
(Ward et al. 2020 Levy et al. 2021 Kavis et al. 2019).
Adaptive minimax optimization algorithms. The adaptive stepsize schemes naturally tended to minimax optimization, both in theory and practice, notably in the training of GANs (Good-)
fellow 2016 Gidel al., 2018). In the convex-concave regime, several adaptive algorithms designed based on EG and AdaGrad stepsize, and they inherit the parameter-agnostic characteristic al. 2019). In sharp contrast, when the objective function is nonconvex about one variable, most existing adaptive algorithms require knowledge of the prob- lem parameters (Huang & Huang 2021 Huang et al. |021 Guo al. 2021). Very recently, was proved that a parameter-dependent ratio between two stepsizes is necessary for GDA in NC-SC minimax problems with non- adaptive stepsize (Li et al. 2022) and most existing adaptive stepsizes (Yang et al. 2022a). Heusel et al. (2017) shows the two-time-scaled GDA with non-adaptive stepsize or Adam will converge, but assuming the existence of an asymptotically stable attractor.
(Bach& & Levy 2019 Antonakopoulos
Other NC-SC minimax optimization algorithms. In the NC-SC setting, the most popular algo- rithms are GDA and GDmax, in which one primal variable update followed by one or multiple steps of dual variable updates. Both of them can achieve (c-22) complexity in the deterministic setting and ( sample complexity in the stochastic setting Lin et al. 2020al Chen et al. 2021 Nouiehed et al. 22199: Yang et al. (020)), which are not improvable in the dependency on given the
existing lower complexity bounds (Zhang et al. 2021 Li et al. 2021). Later, several works further improved the dependency
the condition number with more complicated algorithms in determin- istic (Yang et al. [202bb] Lin et al.) (2020b) and stochastic settings (Zhang et al.) 2022a). All of the algorithms above do not adaptive stepsizes and rely on knowledge of the problem parameters.
3

---

Published as a conference paper at ICLR 2023
1.2 NOTATIONS
We denote as the smoothness parameter, μ1 as the strong-concavity parameter, whose formal def- initions will be introduced in Assumptions 3.1 and 3.2 and = 1/ as the condition number. We assume access to stochastic gradient oracle returning V x F(r, y: E V Par, yi E) For the mini- max problem T we denote y (x) := arg max f(z, y) as the solution of the inner maximization problem, & (x)) == f(z, y (x)) as the primal function, and P-(-) as projection operator onto set y. For notational simplicity, we will use the name of an existing adaptive algorithm to refer to the sim- ple combination of GDA and it, i.e., setting the stepsize of GDA that adaptive scheme separately for both and y. For instance "AdaGrad" for minimax problems stands for the algorithm that uses AdaGrad stepsizes separately for x and y GDA.
METHOD
We formally introduce the TiAda method in Algorithm I and the major difference with AdaGrad lies in line [ Like AdaGrad, TiAda stores the accumulated squared (stochastic) gradient norm of the primal and dual variables in of and v². respectively. We refer to syper-parameters ry" and 1/ as the initial stepsizes, and the actual stepsizes for updating in line ass effective stepsizes which are denoted by ny and r/.. TiAda adopts effective stepsizes 17." = ry", maxx {2 u }" and n/
/ (v841) while AdaGrad uses 1f" (vi+1) 1/2 and n// (v/++))) 1/2 In Section 3 our theoretical analysis suggests to choose a > 1/2 > B. We will also illustrate in the next subsection that the max structure and different a, 3 make our algorithm adapt to the desired time-scale separation.
For simplicity of analysis, similar to AdaGrad-Norm /Ward et al. 2020), we use the norms of gradi- ents for updating the effective stepsizes. more practical coordinate- wise variant that can be used for nigh-dimensional models is presented in Section
Algorithm TiAda (Time-scale Adaptive Algorithm)
1: Input: (No, yo). o0 > 0. o
> 0. 17 > 0, > 0,0 and a > 3..
2: for t 0, 1, 2.... do
3: sample i.i.d. E and S.. and let of V.F(Ie, ye: ve: ( and 9.¹ Fu ye: E
4: oft1 = of + | 2 and u = v.. + 11
5: Ft+1 Ft max (111))111 F. of and vct1 Py Ut (
n7
6: end for
2.1 THE TIME-SCALE ADAPTIVITY OF TIADA
Current analyses of GDA with non-adaptive stepsizes require the time-scale, 1/f /v/ to be smaller than threshold depending on problem constants such as the smoothness and the strong-concavity parameter (Lin et al. 2020al Yang et al. 2022b). The intuition is that we should not aggressively up- date æ if the inner maximization problem has not yet been solved accurately, i.c., we have not found good approximation of y" (x)). Therefore, the effective stepsize of x should be small compared with that of y. It is tempting to expect adaptive stepsizes to automatically find a suitable time-scale separation. However, the quadratic example (2) given by Yang al. (2022a) shattered the illusion. In this example, the effective stepsize ratio stays the same along the run of existing adaptive algo- rithms, including AdaGrad (see Figure [(b]. Adam and AMSGrad, and they fail to converge if the initial stepsizes are not carefully chosen (see Yang et al. (2022a) for details). As of and vf only separately contain the gradients of and y, the effective stepsizes of variables in these adaptive methods depend on their own history, which prevents them from cooperating to adjust the ratio.
Now we explain how TiAda adapts to both the required time-scale separation and small enough stepsizes. First, the ratio of our modified effective stepsizes is upper bounded by decreasing sequence when a > 3:
Th T// max (1/41) 3 1a
/ (v/t1)) / (1/41) nu (u a9
17"
(3)
n?
/ (u)) (1++1)"
(a-2))--3"
4

---

Published as a conference paper at ICLR 2023
as ei is the sum of previous gradient norms and is increasing. Regardless of the initial stepsize ratio /"/n", we expect the effective stepsize ratio to eventually drop below the desirable threshold for convergence. On the other hand, the effective stepsizes for the primal and dual variables are also upper bounded by decreasing sequences, 7/" 11 and v/²/ (1[+11) respectively. Similar to AdaGrad, such adaptive stepsizes will reduce to small enough, e.g., (1/(), to ensure convergence.
Another way to look at the effective stepsize of x is
(pi+1) a max ( "++13 max (wft 1 )a (v++1)
T
If the gradients of y are small (i.e., 21 2f+1). meaning the inner maximization problem is well solved, then the first factor becomes 1 and the effective stepsize of x is just the second factor, similar the AdaGrad updates. If the term "/41 dominates over of41 the first factor would be smaller than 1, allowing to slow down the update of x and waiting for a better approximation of y (x))
To demonstrate the time-scale adaptivity of TiAda, we conducted experiments on the quadratic mini- max example (2) with L, 2. As shown in Figure [(b) while the effective stepsize ratio of AdaGrad stays unchanged for this particular function, TiAda progressively decreases the ratio. According to Lemma 2.1 of Yang et al. (2022a), 1/ks is the threshold where GDA starts converge. We label the time period before reaching this threshold as Stage I, during which as shown Figure [(c] the gradient norm for TiAda increases. However,
as it enters Stage II, i.e., when the ratio drops below 1/K, TiAda converges fast to the stationary point. In contrast, since the stepsize ratio of AdaGrad never reaches this threshold, the gradient norm keeps growing.
3 THEORETICAL ANALYSIS OF TIADA
In this section, study the convergence of TiAda under NC-SC setting with both deterministic and stochastic gradient oracles. We make the following assumptions to develop our convergence results.
Assumption 3.1 (smoothness). Function f(z, y) is I-smooth (1 > 0) in both x and y. that is, for any 01 E Rd and y1. y2 E V, we have
max (IIV un) - (x2 U2)ll. y v1) V (x2, M2)ll) S <1[[= - x2ll + 11y1 y2ll) Assumption 3.2
in y). Function f(2, y) is cetrongly-concave (μ > 0) in y. that
is, for any x E IRd and yı, U2 E Y, we have
1 Il y2ll 2
fx, 2 fx, V2) + (V,f(x, /1 y2)
Assumption 3.3 (interior optimal point). For any E Rd y² (xx is in the interior y.
Remark 3.1. The last assumption ensures Vzf(z, y (x)) = 0, which is important for AdaGrad-lit like stepsizes that use the sum of squared norms of past gradients in the denominator. If the gradient about is not 0 at (xx),, the stepsize will keep decreasing even near the optimal point, leading to slow convergence. This assumption could be potentially alleviated by using generalized AdaGrad stepsizes (Bach & Levy 2019).
We aim to find a near stationary point for the minimax problem 1 Here, (xr is defined to be an stationary point if V y)ll < and Vy v). < in the deterministic setting, or V ffr, (x, 22 < 2 and (2) < ²² in the stochastic setting, where the expectation is taken over all the randomness the algorithm. This stationarity notion can be easily translated to the near-stationarity of the primal function Φ(z)) max v) (Yang et al. 2022b). Under our analyses, TiAda is able to achieve the optimal O (c-2) complexity in the deterministic setting and
near-optimal O (E (c(()))) sample complexity for any small ő > 0 in the stochastic setting.
3.1 DETERMINISTIC SETTING
In this subsection, we assume to have access to the exact gradients of (())), and therefore we can replace V. F Mes EE) and V,, F,F,, we (. by VzJ (xt, we) and V (x2, 91) in Algorithm
5

---

Published as a conference paper at ICLR 2023
Algorithm Twith deterministic gradient oracles satisfies that for any 0 < 3 < a < 1, after T iterations,
Theorem 3.1 (deterministic setting). Under Assumptions 3.7 3.7tol 3.3
3.3
T-1
1 7 (
Ive +
(uffln S E
This theorem implies that for any initial stepsizes, TiAda finds e-stationary point within O (c--2) iterations. Such complexity is comparable to that of nonadaptive methods, such as vanilla GDA (Lin al.] 2020a), and is optimal in the dependency of e (Zhang et al. 2021). Like NeAda (Yang al. 2022a). TiAda does not need any prior knowledge about 1s and but improves over NeAda by removing the logarithmic term in the complexity. Notably, we provide a unified analysis for wide range of a and 8, while most existing literature on AdaGrad-like stepsizes only validates a specific hyper-parameter, e.g., a = 1/2 minimization problems (Ward et al. 2020
Kavis et al. 2019).
3.2 STOCHASTIC SETTING
In this subsection, assume the access to stochastic gradient oracle, that returns unbiased noisy gradients, Fi, y: {) and F, g). Also, we make the following additional assumptions. Assumption 3.4 (stochastic gradients). For {a, y}, we have Eg FV, y, E)] V=f(z, v). In addition, there exists a constant G such that =F y. E)Il S G any z E Rd and y E y
Assumption 3.5 (bounded primal function value). There exists a constant 4 max E IR such that for any x E Rdd (x) is apper bounded by 4 maxx
Remark 3.2. The bounded gradients and function value are assumed in many works on adaptive algorithms (Kavis et al. 2022; Levy et al. 2021). This implies the domain of y is bounded, which also assumed in the analyses of AdaGrad (Levy) 2017 2017 Levy et al. 2018). In neural networks with rectified activations, because of its scale- inverinnv property (Dinh et al.] (017). imposing boundedness of y does not affect the expressiveness. Wasserstein GANs (Arjovsky et al. 2017) also use projections on the critic to restrain the weights on a small cube around the origin.
Assumption 3.6 (second order Lipschitz continuity for y). For any I1, 22 E Rd and y1 y2 E V, there exists constant L such that V of 31) V2 2 y2)ll S L [[ z2l + 11 y/ l)
and V f (#1, y1) - bf (2-2. y2)ll S L (1|=1 x2ll + 1l y/ll).
Remark 3.3. Chen et al. (2021) also impose this assumption to achieve the optimal O (c- com- plexity for GDA with non-adaptive stepsizes for solving NC-SC minimax problems. Together with Assumption 3.3 we can show that y-) is smooth. Nevertheless, without this assumption, Lin et al. 2020a) only show a worse complexity of O (E-5) for GDA without large batchsize.
Theorem 3.2 (stochastic setting). Under Assumptions 3.7 to 3.6 Algorithm 7 with stochastic gra- dient oracles satisfies that for any 0 < B < a < after T iterations,
T-1
Σ IIV w01l + Σ Dy
< 20 1 +T + 1211477 +1--1+1-)) 3).
1=0
TiAda can achieve the complexity arbitrarily close to the optimal sample complexity. O (E-1) Li
al. 202T), 1), by choosing a and 3 arbitrarily close to 0.5. Specifically, TiAda achieves complexity
of O
a 0.5 + 8/(8 25) and 3 = 0.5 5/(8 + 28)- Notably, this matches the complexity of NeAda with AdaGrad stepsizes for both variables (Yang
(T+)) for any small 8 0 if
et al. 2022a). NeAda may attain Ō complexity with more complicated subroutines for y.
Theorem 3.2 implies that TiAda fully agnostic to problem parameters, e.g. J.. and a. GDA with non-adaptive stepsizes (Lin et al. 2020a) and vanilla single-loop adaptive methods (Huang & Huang 202T], such as AdaGrad and A AMSGrad, all require knowledge of these parameters. Compared with the only parameter-agnostic algorithm, NeAda, our algorithm has several advantages. First, TiAda is a single-loop algorithm, while NeAda (Yang et al. 2022a) needs increasing inner-loop steps and a huge batchsize of order Ω2 () to achieve its best complexity. Second, our stationary guarantee is for [x, 2) < e², which is stronger than E|| V (I. y)ll S guarantee in NeAda. Last but not least, although NeAda does not need to know the exact value of variance a in the stochastic setting when 0, AeAda uses different stopping criterion for the inner loop in the deterministic

---

Published as a conference paper at ICLR 2023
setting when 0. so it still needs partial information about a. In comparison, TiAda achieves the (near) optimal complexity in both settings with the same strategy.
Consistent with the intuition of time-scale adaptivity in Section 2.1 the convergence result can be derived in two stages. In Stage I, according to the upper bound of the ratio in Equation (3), we expect the term 1/ (+ 0- ) reduces constant e, a desirable time-scale separation. This means that 2 has to grow to nearly (1/c) In Stage II, when the time-scale separation is satisfied, TiAda converges at speed specified in Theorem 3.2 This indicates that the proximity between and [ affects the speed trade-off between Stage and II. When a and 3 are close, we have a faster overall convergence rate close to the optimality, but suffer from longer transition phase in Stage I. albeit by only a constant term. We also present an empirical ablation study on the convergence behavior with different choices of and [3 in Appendix A.2
Remark 3.4. In TiAda, the update of requires to know the gradients of y (or e.41). However, in some applications that concern about privacy, one player might not access the information about the other player (Koller & Pfeffer 1995| Foster & Young 2006) [H et al.] (016). Therefore, also consider variant of TiAda without taking the maximum of gradient norms, i.e. setting the effective stepsize of x in Algorithm|| to r/" 12 This variant achieves sub-optimal com-
plexity of Ö (e-s). This result further justifies the importance of coordination between adaptive stepsizes of two players for achieving faster convergence in minimax optimization. The algorithm
and convergence results are presented in Appendix C.4
4 EXPERIMENTS
In this section, we first present extensions of TiAda that accommodate other adaptive schemes be- sides AdaGrad and are more practical deep models. Then we present empirical results of TiAda and compare it with (i) simple combinations of GDA and adaptive stepsizes, which are commonly used in practice, and (ii) NeAda with different adaptive mechanisms (Yang et al.) (022a). Our experiments include test functions proposed by Yang al. (2022a), the NC-SC distributional ro- bustness optimization (Sinha et al. 2018), and training the NC-NC Wasserstein GAN with gradient penalty (Gulrajani et al. 2017). We believe that this not only validates our theoretical results but also shows the potential of our algorithm in real-world scenarios. To show the strength of being aaramster-agnostic of TiAda, in all the experiments, merely select = 0.6 and 8 0.4 without further tuning those two nyper-parameters. All experimental details including the neural network structure and hyper-parameters are described in Appendix A.
4.1 EXTENSIONS TO OTHER ADAPTIVE STEPSIZES AND HIGH-DIMENSIONES MODEL.
Although we design TiAda upon AdaGrad-Norm, it is easy and intuitive to apply other adaptive schemes like Adam and AMSGrad. To do so, for 2 E {x,y), we replace the definition of of and oft1 in line and
and 4 of Algorithm tto
- = (ma (I. 3:))) i=0
gi = -B (1
(E),, wi4
vs:
where {B;} is the momentum parameters and & is the second moment function. Some common stepsizes that fit in this generalized framework can be seen in Table the appendix. Since Adam is widely used in many deep learning tasks, we also implement generalized TiAda with Adam stepsizes in our experiments for real-world applications, and we label it "TiAda-Adam".
Besides generalizing TiAda to accommodate different stepsize schemes, for high-dimensional mod- els, we also provide coordinate- version of TiAda. Note that we cannot simply change ev- erything in Algorithm [ to be coordinate-wist because we use the gradients of y in the stepsize of z and there are no corresponding relationships between the coordinates of x and y. Therefore, in light of our intuition in Equation (4) we use the global accumulated gradient norms to dynamically adjust the stepsize of x. Denote the second moment (analogous to v Algorithm [ for the i-th
coordinate of x at the 1-th step vi41, and globally vi+1 := Σd V441, We also use similar notations for y. Then, the update for the i-th parameter, i.e., xt and y², can be written as
r/+1 x² max ) vit1 ví
(ofZ))
9" V ve f(x, Vt)
(1f2).))
Vy (1)
(u)4).))
7

---

Published as a conference paper at ICLR 2023
17"
30.74
Tikl
377
Akdall
1058
2012
Boy ml
(a) r
(b) r 1/2
(c) r 1/4
(d) r 1/8
Milhed
17
17
Nolde AoaCie
201
2018
28/0 2000
(c) r 1/0.01
(f) r 1/0.03
(g) r = 1/0.05
(h) ablation study
Comparison of algorithms test functions. r r= /n is the initial stepsize ratio. In the first row, we use the quadratic function (2) with L = under deterministic gradient oracles. For the second row, test the methods the McCormick function with noisy gradients.
Figure 2:
Our results in the following subsections provide strong empirical evidence for the effectiveness of these TiAda variants, and developing convergence guarantees for them would be interesting future work. We believe our proof techniques for TiAda, together with existing convergence results for coordinate-wise AdaGrad and AMSGrad (Zhou et al.] (018:) Chen et al. 2018 Défossez al. 2020), can shed light on the theoretical analyses of these variants.
4.2
TEST FUNCTIONS
Firstly, we examine TiAda on the quadratic function (2) that shows the non-convergence of simple combinations of GDA and adaptive stepsizes (Yang et al., 2022a). Since our TiAda based on AdaGrad, we compare it to GDA with AdaGrad stepsize and NeAda-AdaGrad (Yang et al. 2022a). The results are shown in the first row Figure 2 When the initial ratio poor, TiAda and NeAda- AdaGrad always converge while AdaGrad diverges. NeAda also suffers from slow convergence when the initial ratio is poor, e.g., and 1/2 after 2000 iterations. In contrast, TiAda automatically balances the stepsizes and converges fast under all ratios.
For the stochastic case, we follow Yang et al. (2022a) and conduct experiments on the McCormick function which is more complicated and 2-dimensional: f(x, y) (2)))) + (z1
-x2)² - 3 + 1/2 (vî + v2) TiAda consistently outperforms AdaGrad and Adddaad as demonstrated in the second row of Figure 2 regardless of the initial ratio. In this function, we
also run an ablation study on the effect of our design that uses max-operator in the update of x. We compare TiAda with and its variant without the max-operator, TiAda without MAX (Algorithm 2 in the appendix) whose effective stepsizes of x are 1/"/ (vē+1) According to Figure 2(h) TiAda converges smaller gradient norms under all configurations of a and B.
4.3 DISTRIBUTIONAL ROBUSTNESS OPTIMIZATION
In this subsection, we consider the distributional robustness optimization (Sinha et al. target training the model weights, the primal variable xr to be robust to the perturbations in the image inputs, the dual variable y. The problem can be formulated as:
2018). We
1
min
max
f((x.)) - 711y, 12
(5)
8= yr .f.. Val nE
where f, is the loss function of the i-th sample, v; is the i-th input image, and y is the corresponding perturbation. There are total of samples and y is a trade-off hyper-parameter between the original loss and the penalty of the perturbations. If y is large enough, the problem is NC-SC.
We conduct the experiments the MNIST dataset (LeCun 1998). In the left two plots of Figure 3 we compare TiAda with AdaGrad and AeAda-AddGrad in terms of convergence. Since it is common in practice to update y 15 times after each update (Sinha et al. 2018) for better generalization error,
8

---

Published as a conference paper at ICLR 2023
2006
2000
(a) x²' 0, = 0.05
(b) 1r 0.1, 71"h
0.1
(c) 0.001, 1"
(d) v" 0.001, 77' 0.001
Figure 3: Comparison of the algorithms on distributional robustness optimization 5). We use in the legend indicate the number of inner loops. Here we present two sets of stepsize configurations for the comparisons of AdaGrad-liin extensive experiments on larger ranges of stepsizes, and will be shown that TiAda is the best among all stepsize combinations in our grid.
and Adam-like algorithms. Please refer to Appendix A..3 for
we implement AdaGrad using both single and 15 iterations inner loop (update of y)- In order to show that TiAda is more robust to the initial stepsize ratio, we compare two sets of initial stepsize configurations with two different ratios. In both cases, TiAda outperforms NeAda and AdaGrad, especially when 1f 1/ 0.1, the performance gap is large. In the right plots of Figure 3 the Adam variants are compared. this case, we find that TiAda is not only faster, but also more stable comparing Adam with one inner loop iteration.
4.4 GENERATIVE ADVERSARIAL NETWORKS
Another successful and popular application of minimax optimization is generative adversarial networks. In this task, a discriminator (or critic) is trained to distinguish whether an image is from the dataset. At the same time, generator is mutually trained to synthesize sam- ples with the same distribution as the training dataset so as to fool the discriminator. We use WGAN-GP al. 2017). which imposes the dis-
4.5
5.5
Tidela-dddan (of.ny" 0.01)
loss (Gulrajani 1-Lipschitz function, with CIFAR-10 criminator to be a dataset (Krizhevsky et al. 2009) in our experiments.
Aulem (o" of 0.00)
2.-
(0000))
Adam (or or (.006)
20-
Titda-Adem (of-
Jolun (w". 0.001)
Since TiAda is a single-loop algorithm, for fair com-
5000
10000
L5000 20000)
25000 33000 35000 40000
parisons, also update the discriminator only once for each generator update in Adam. In Figure 4 we plot the inception scores (Salimans al. 2016) of TiAda-Adam
Thgrulinnt calls.
Figure 4: Inception score WGAN-GP.
and Adam under different initial stepsizes. We use the same color for the same initial stepsizes, and different line styles to distinguish the two methods, i.e., solid lines for TiAda-Adam and dashed lines for Adam. For all the three initial stepsizes we consider, TiAda-Adam achieves higher in- ception scores. Also, TiAda-Adam different solid lines at the end of training is smaller than the dashed lines.
more robust to initial stepsize selection, as the gap between
CONCLUSION
In this work, we bring in adaptive stepsizes to nonconvex minimax problems parameter-agnostic manner. We designed the first time-scale adaptive algorithm, TiAda, which progressively adjusts the effective stepsize ratio and reaches the desired time-scale separation. TiAda also noise adaptive algorithm for
and does not require large batchsizes compared with the existing parameter-agnose nonconvex minimax optimization. Furthermore, TiAda able to achieve optimal and near-optimal complexities respectively wtih deterministic and stochastic gradient oracles. We also empirically showcased the advantages of TiAda over NeAda and GDA with adaptive stepsizes on several tasks, including simple test functions, well NC-SC and NC-NC real-world applications. It remains an interesting problem to study whether TiAda can escape stationary points that are not local optimum, like adaptive methods for minimization problems (Staib al. 2019).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENT
We thank Dr. Anas Barakat and anonymous reviewers for their valuable feedback. The work is supported by ETH research grant and Swiss National Science Foundation (SNSF) Project Funding No. 200021-207343.
REFERENCES
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox method for variational inequalities with singular operators. NeurIPS, 32, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In ICML, pp. 214-223. PMLR, 2017.
Francis Bach and Kfir Y Levy. A universal algorithm for variational inequalities adaptive to smooth- ness and noise. Conference on Learning Theory, pp. 164-194. PMLR, 2019.
Radu Ioan Bot and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. arXiv preprint wxXiv22077.1665, 2020.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. 2021.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 02941, 2018
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. AISTATS, pp. 1458-1467. PMLR, 2017.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In /CLR, 2018
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478. 2021.
Alexandre Défosse7, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02339 2020.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In ICML, pp. 1019-1028. PMLR, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awar minimiza- tion for efficiently improving generalization. ICLR, 2021.
Dean Foster and Hobart Peyton Young. Regret testing: Learning to play nash equilibrium without knowing you have opponent. Theoretical Economics, 1(3):341-36,, 2006.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The journal of machine learning research, 17(1):099-2030, 2016.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint 2018.
Ian Goodfellow. Nips 2016 tutorial: Generative adversarial networks. /70100170 2016.
arXiv preprint
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Farlee Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. NeurlPS, 27, 2014.
10

---

Published as a conference paper at ICLR 2023
Ian J Goodffllow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Green9. Pytorch code for gan models, httpss//gthubb.ccm//eeees/////pp 2018.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. NeurlPS, 30, 2017.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms the adam family, arXiv preprint arXiv:2112.03459, 2021.
He He. Jordan Boyd-Graber Kevin Kwok, and Hal Daumé III. Opponent modeling in deep rein- forcement learning. In ICMI,, pp. 1804-1813, PMLR, 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012.
Feihu Huang and Heng Huang. Adagda: Faster adaptive gradient descent ascent methods for mini- max optimization. arXiv preprint arXiv:2106. 16101, 2021.
Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. NeurIPS, 14:1111111144 2021.
Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher: Unixgrad: universal, adaptive algorithm with optimal guarantees for constrained optimization. NeurlPS, 32, 2019.
Ali Kavis, Kfir Levy, and Volkan Cevher. High probability bounds for class of nonconvex algo- rithms with adagrad stepsize. In ICLR, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Daphne Koller and Avi Pfeffer. Generating and solving imperfect information games, In IJCAI, pp- 1185-1193, Citeseer, 1995.
Galina Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun, com/exdb/mnist// 1998.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. NeurlPS, 30, 2017.
Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. NeurIPS, 34:20571-20588 2021.
Kfrr Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceler- ation. NeurlPS, 31, 2018.
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex- strongly-concave min-max optimization. NewrIPS, 34:1792-1804 2021.
Haochuan Li, Farzan Farnia, Subhro Das, and Ali Jadbabaie. On convergence of gradient descent ascent: A tight local analysis. In ICML, pp. 12717-12740. PMLR, 2022.
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, pp. 983- 992. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2023
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007. 14294, 2020.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave mini- max problems. In ICML, pp. 6083-6093. PMLR, 2020a.
Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738-2779. PMLR, 2020b.
Louis
Lv.
Reproducing "certifying
distributional robustness with prin-
https://github com/ Lonn/Louis-udd, oappppoaa....tttaaaaaaaaaaaaaaaa
cipled adversarial training".
2019.
David Miller, Zhen Xiang, and George Kesidis. Adversarial learning targeting deep neural network classification: comprehensive review of defenses against attacks, Proceedings of the IEEE, 108 (3):402-4333 2020.
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revis- iting stochastic extragradient. In International Conference Artificial Intelligence and Statistics, pp. 4573-4582. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. NewrIPS, 32, 2019.
Leonid Denisovich Popov. A modification of the arrow-hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-88) 888,, 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Confer- ence on Learning Theory, pp. 993-1019. PMLR, 2013.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR, 2018.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Sys- fems, 33:21554-21565. 2020.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. NeurIPS, 29, 2016.
Othmane Sebbouh, Marco Cuturi, and Gabriel Peyré. Randomized stochastic gradient descent as- cent. In AISTATS, pp. 9941-2969, PMLR, 2022.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. ICLR, 2018
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. In International Conference on Machine Learning, pp. 5956- 5965. PMLR. 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: convergen over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9047-9076 2020.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient
descent. In AISTATS, pp. 1475-1485. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2023
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems, 33:1 2020.
Junchi Yang. Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostic noncon- vex minimax optimization. NeurIPS, 2022a.
Junchi Yang, Antonio Orvicto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In AISTATS, pp. 5485-5517. PMLR, 2022b.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-strongll -arnnveee-strogllyyocccyee minimax optimization. In Uncertainty in Artificial Intelligence, pp- 482 492. PMLR, 2021.
Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for conconvex-concat minimax problems. arXiv preprint arXiv:2205. 15084, 2022a.
Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. arXiv preprint arXiv:2208.090 2022b.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 2018.
A
SUPPLEMENTARY TO EXPERIMENTS
Table 1: Stepsize schemes fit in generalized TiAda. See also Yang al. (022a
Algorithms
first moment parameter 3e
second moment function (vo, {ut} )=))
AdaGrad (TiAda)
B 0
Uo Ei=o uf
GDA
Bg = 0
Adam
0 < 3 <
r Up + (1 7) Ei= u2 maxm=o....t ? m+ vo + (1 ?) Σm 7 mm
AMSGrad
0 3r <
A.1 EXPERIMENTAL DETAILS
In this section, will summarize the experimental settings and hyper-parameters used. As men- tioned, since we try to develop parameter-agnostic algorithm without tuning the hyper-parameters much, if not specified, we simply use a 0.6 and 0.4 for all experiments. For fair comparisons, we used the same hyper-parameterss when comparing our TiAda with other algorithms.
Test Functions For Figure and the first row of Figure 2 we conduct experiments on problem (2) with 2. We use initial stepsize 17 0.2 and initial point (1, 0.01) for all runs. As for the we chose 17" 0.01, and the noises added the gradients are from pero-mean Gaussian distribution with variance 0.01.
McCormick function used in the second row of Figure 2
Distributional Robustness Optimization For results shown in Figures and 7 we adapt code from Lv (2019), and used the same hyper-parameter setting as Sinha et al. (2018); Sebbouh et al. 20022) i.c., ? = 1.3. The model we used a three layer convolutional neural network (CNN) with final fully-connected layer. For each layer, batch normalization and ELU activation are used. The width of each layer is (32, 64, 128, 512). The setting is the same as Sinha et al. (2018); Yang et al. 2022a). We set the batchsize 128, and for the dike-like optimizers, including Adam, NeAda- Adam and TiAda-Adam, we use B = 0.9, B2 = 0.999 for the first moment and second moment parameters.
13

---

Published as a conference paper at ICLR 2023
Generative Adversarial Networks For this part, we the code adapted from Green9
2018
To produce the results Figure 4 a four layer CNN and a four layer CNN with transpose convo- lution layers used respectively for the discriminator and generator. Following similar setting as Daskalakis et al. (2018), we set batchsize as 512, the dimension of latent variable as 50 and the weight of gradient penalty term 10-1 For the Adam-like optimizers, set &1 0.5, 82 0.9. To get the inception score, we feed the pre-trained inception network with 8000 synthesized samples.
A.2 ABLATION STUDY ON CONVERGENCE BEHAVTOR WITH DIFFERENT AND
2 to study the effect and 3 on the convergence behavior of TiAda. As discussed in Sections and 3.2, we refer to the period before the stepsize ratio reduce to the convergence threshold as Stage I, and the period after that Stage II. In order to accentuate the difference between these two stages, we pick a large initial stepsize ratio rf" /n/" = 20. We compare 4 different pairs of a and 3: {0.59, 0.6, 0.61, 0.62) and / 1- From Figure we observed that soon as TiAda enters Stage II, the norm of gradients start to drop. Moreover, the closer a and & are to 0.5, the more time TiAda remains in Stage which confirms the intuitions behind our analysis in Section 3.2
We conduct experiments on the quadratic minimax problem with of hyper-parameters
400
2.50
0.59
0.6
0.81
300-
0.59
1.00-
i//"n" 1/x
0.62
250
0.61
0.6
100
200
0.62
0.50
150-
100
0.25
50-
20000
30000 40000 #gradientt calls
20000
30000 40000 #gradient calls
60000
(a) effective stepsize ratio
(b) convergence
Figure 5: Illustration of the effect of a and 3 the two stages in TiAda's time-scale adaptation process. We set = 1 a. The dashed line on the right plot represents the first iteration when the effective stepsize ratio is below 1/k.
A.3 ADDITIONAL EXPERIMENTS ON DISTRIBUTIONAL ROBUSTNESS OPTIMIZATION
We use a grid of stepsize combinations to evaluate TiAda and compare it with NeAda and GDA with corresponding adaptive stepsizes. For AdaGrad- algorithms, we use {0.1, 0.05, 0.01, 0.0005} for both v7 and 17", and the results are reported Figure 6 For Adam-like algorithms, we use (0.001, 0.0005, 0.0001} for 17 and {0.1, 0.05, 0.005, 0.001 for ry", and the results are shown in F We note that since Adam uses the reciprocal of the moving average of gradient norms, it is extremely unstable when the gradients are small. Therefore, Adam-like algorithms often experience instability when they are near stationary points.
B HELPER LEMMAS
Lemma B.1 (Lemma A.2 in Yang et al. 2022a)). numbers, œ1 and 1. Then have
Let æ1, ET be sequence of non-negative real
21
1
14

---

Published as a conference paper at ICLR 2023
Tidk
Todi
Tidda
Titda
30
137
2010
(a) 17" = 0.1, = 0.1
(b) ,フ 0.1, 0.05
(c) 1)" = 0.1, 0.01
(d) Λr" = 0.1, 0.005
80
ool
(e) 11 = 0.05, 77 0.1
(l) 17" 0.05, 7 0.05
(g) 17" 0.05, xy 0.01
(h) xr' 0.05, 17 0.005
Acalied
17'
2ypdbia cl
(i) 8z 0.01, xp 0.1
( 17" 0.01, 0.05
(k) 17 0, 0.01
1y 0.01, x7 0.005
10-
137
13-1
(m) 17 0.005, n
(n) ny" 0.005, 17" (0) 1²² 0.005, 17" 0.01 (p) 17" 0.005, xy" 0.005
Figure 6: Gradient norms in æ of AdaGrad algorithms on distributional robustness optimiza- tion 5 We use in the legend to indicate the number of inner loops.
When = 1, we have
Ei=n 24
S 1 log
Ei=r
I1
Lemma B.2 (smoothness of Φ (-) and Lipschitzness of y-)- Lemma 4.3 in Lin et al. 2020a
Under Assumptions 3.1 and 3.2 we have ((.) is (1 + smooth with ( Vef xz y (x)),
and y (-) k-Lischhitz.
Lemma B.3 (smoothness of y (.). Lemma 2 in Chen et al. 2021 ). Under Assumptions 3. [(L+ba)
3.2
and 3.6 have that with L L+LK
n²
VV (x2)) S 11 x2ll-
C PROOFS
For notational convenience in the proofs, we denote the stochastic gradient as V Vx v1) and VyJ wt). Also denote y² = 3² (Ize,, Tt mf It.
(,,,)) " x²
min ((r), and A T maxx Φ². We use 1 as the indicator function.
15

---

Published as a conference paper at ICLR 2023
477
13"
( n 0.001, 0.1
(b) 11 0.001, n 0.05
(c) r7" = 0.001. 0.005
(d) 17 0.001, 7 0.001
1774
17 0.0000, 17 U.1
(l) 07 0.000G, 17 0.05
11 0.0000, T 0.005
(h)
D. D.00OG, 7
0.001
13.
0.0001.
0.0001,
(k)
0.9001,
9.005
(1) ./a 0.0001, 27 0.001
Figure 7: Gradient norms in x Adam-like algorithms on distributional robustness optimization (5) We use i in the legend to indicate the number of inner loops.
C.1 PROOF OF THEOREM 3.1
We present a formal version of Theorem 3.1
Theorem C.1 (deterministic setting). Under Assumptions 3.7 to 3.3 Algorithm 7 with deterministic gradient oracles satisfies that for any 0 < B < a < 1, after iterations,
V=r(( max (5C1, Σ
where
2_
4nle(2-a) -1000--))1-0 w/)/2
2xd
C = o0 +
+
6(1 -a) (18) (06))a-1 2a-1
12021 +
1- 2a
12ne1
C105
20/ca1/ (1-a)(1 (ogge)))) 1/2/2
I-a
C1C41)
+
1/"
+
e(1 ()) (2g))a--0 20-
12a- 921 +
1 2x +
12a-
2A c1Cs
C14471
2kle Dxle(1-2a+11)) (1 (1)
2xl
C2 = 00 +
+
e(1 2a + B) (1z)) 20-1 12a21 +
(1 20) (1:7) 12as1
11th (vT)
1-20+9
1 2a +
C4 (177)2
1-3
1-1120+33 (1+
C5
12 1<c1
(v
1-20+
2a +
2A + 01es
8kle(1-log v///1
4e (1- (0) v01/1
+
1/th (uf)
1/4
e (1z))
e e(wg) ((zg)2--1 2a-
4caa (17²)² c(1-9)(1- (11/(1a))
C5
1 12a21,
(108
e(1 B) (vg) 2a 2a-
(a
16

---

Published as a conference paper at ICLR 2023
17
Arp
with A = ((x1) - Φ²
c1
np
y
a-
C2 = max
u+t + 17 (#r (1u++1) +11
C3 = 4(m+
112
1
+
(0%
np
C2
1/8
C4 = (n +1) 1)
(vt)a
2n²
+ (u + 1)m²
18
1
17"h 17 (v0)
n
C2
c3 +
+
1- B
In addition, denoting the above upper bound for 1 ( w1)l
as C3. we have
T-1
(
1 log C3 - log vo
C c1-2x+8
))
r
Σ Wf ( ca
(ug) (0))2a-B11 12a-321 + 1- 2a B 1 2a-9<1
Proof.
Let us start from the smoothness of the primal function D(-). By Lemma B.2
((12+1)
S <0((x)) "It ( (
((x)) 7h V= M1 11( (V V
+ V (,,,,)))) wt))
s ((x)) 7o V f 11
?) [ +
Tt
V fIz, v1) V (1))] + (..
2
((x))
V 2 f (z,, 3/ )1( + kln II v
81 31)11
+ 2
V ( va) -
2
nj
((x))
V f (2,, )1 | M1
V Va v1) v
2
2 max foz 1: u
< ((r))
T
V [ )l k4 (
VaI( v.) (+(x))1
2
2 (
a-8 (2/+1)
<1(()))
11
V fz, 31 )1 klpp || 1 11)1
+
V (2t.
2
2 (v))
(0/+1)
< (xx)
1ht | fx 3t)l + kln? V 101l
nx²²
Yell Vell f 11
2
21yd
(1%) )a-B
where the second to last inequality, we used the strong-concavity (x.,)) V f v1) - (2(2))) I lllye vE'l s V vill
Telescoping and rearranging the terms, have
(x),
T
(#(o)) Φ*)
+2kl
T/ V
Yell V v fx g())
11th (w%) a-
4$
t=
2n1n
2
V Vzf(xr, 31 + Σ 7t v,,(
max
{ut+1s 1/41]
20
2kdn
T-1
24 +
2a V T w=)1
+c
Σ
Yel V 2t)ll
t= (1i+z)
t=0
+ log ui
log up
(いz)) (=2))1-20 1-20
T-1
< 24 + 2ndn""
12a21 +
12ac1
+ Σ
rell V of 111.
(vg)
(1z)2--1
2a-1
1- 2a
1=
(6)
17

---

Published as a conference paper at ICLR 2023
We proceed to bound Ei= VellV (I vtll Let to be the first iteration such that (v% 8
2o = max
un
11" (1 +1) 11}. x+1
We have o%/ S ci2 and for 2 to.
yet1 - -Vi+lll
< (1+ + 1131++ 1/4 - 1+ Xx
|| - 12
118e vēl1 + (1)9)2
Vu B0ll+ + 2np
$ (1+ Ar)
(ye - De, V f Be))
(v24.1)
(u/+1) )3
+ 1 1 |ii41 11
where A > 0 will be determined later. For (-smooth and p-strongly convex function g(z), according to Theorem 2.1.12 in Nesterov| (2003), we have
al
1 V
(Vg(v) Vg(y), v)
1 + ||
y11
1Vo(())
Therefore,
Term
< (1 (1) (11-
257a yal
11ye -1 +
(1p2))
2np
1/ V (f ((o(ee))))))
(n 1) (1)+1)
(n + 1) (v)+1) 26
B
Let A
(u+(((((2)) nd
Note that de > O after lg- Then
22
Term
1751 pll
(17²)2
2np
1 (1 1) (11+2))
11v. 1211" + +1+ Ao)
Var w.)l
(utt1)
25
(μ + 1) (2)t1))
(178)2
207
|1y vill2 + (1+ Xx)
V (o,,211))11
(1 23
(n + 1) ))
(n)
As + de 2 1 and (1% 2 7 + 1), we have term
n (a+t)(( 3 Putting them back,
we can get
|t+1 Vitall" ?
17
V Vyf(z, + (1+ 1 ),)
18 vi 11?
11 - 1/2
(n 1) (vit1)
3
170
(1 + 1) 11
1/:e 1/
1 Vy (1,,,))))
| -1011"
(n + (vlta)
178pu
(a + 1)x² (uiti) )
17
< 1/: - wi 1/1
Vy 1=
||000:111 2xel?
( 1) (v%
3
172
(n + 1)r2 (1%t2)
m/ [a v.)1.
1 - 1/
1
Vyf(ar
(++1) + (v
pl
18

---

Published as a conference paper at ICLR 2023
Then, by telescoping, we have
E
Tp
V (o
will S |uve - vi.11 112
+
T
(1 + 1)n² 1v%
)
1/2 V (Te, Ve )
(n + 1) (ub+1)
rp0ll
to
to
For the first term in the RHS, using Young's inequality with T to be determined later, we have
|uto - viol 11 s 2/ Mto - Dio - 11 +
2/1 - -io
2/ (Vio-1 + 7o- 1 V y.J (T Meo
W6- 1| 1 + Vi. -ig-1l1 11
2/ yto 1 7 V 8 ( ( ylu vi - 1| + 21137, vio
|t 1 -2--11 2 + 7/0
| // (I 11, )11²) + 2 22lu/, Vio
M1o
1
V n /
11 y10 110 )) 2 + 2
(2 110 -
+ 2 1/o Wio-1
1
1. 1)l + 2/1b%. -V6-11l 1|
yto
122
1
v% + 21107, -vio-111
10
112
1
77
1/8 C2 + +21l8/ v1o =12
42
(1%) 8
1
1/8 + 2n:111rt0 - -112
(ug) 13 11
1
1/B + +2R2 1 111001111
<4
123
(u 8
2x (1(+2) 8
1/8
nia V (2 ybo
422
(4%)
(u))
Combined with Equation
77. we have
1
(1)+1)
3
< 4(1 +1)
1
+
1
022
1/3
+ +1++)
(
(1g) + (n + On2
2x²
(ot41) )a > [ 111)
112
63
By adding terms from to to and n"00"" from both sides, we have (1g)²
n
| Vz
(o 3
(1/t1)
< C3 +
(2%+1) 8 1 (. + Σ
1p"
| (I2,
(ug)) 3
(vit1)
B
< 0g + 1"00
(o%41) 8 m V (x m0l
+ noeg
to
17
V
( (x))
V
(oh))
(1
3
(uft= 0
t=t=
5 + T.ee
(o/+1) 8 n/ V. 111 +
17"
1-9
+
Uso
(1g))
1 1-
19

---

Published as a conference paper at ICLR 2023
T-1
S C3 +
C4
(u)+1) )
(x2 +
TT
(1))
B
03 + 17
02
11
ca (11
Va v1)
(0))
9
3
1=0 max 1
1/+11
2cx
C2 1- 3
03 + 77
1
+op (11²)
V (
5
(vi+1)
20-8
1 log uz - log vo
(0)) (v7)1-20 1-299
S c + c1 (17")
120- 021 +
- 2a + B 12a-B<1
(vg) 2a 8-1
The LHS can be bounded by (17)1-0 by Lemma B.I above:
Then we get two useful inequalities from
E rell V (1t, scs c4 (177)3
1+log of log vo.
(vz) jau 01
12 821
(1z)
1-20-B
12
-21-
cs cr) <
[loog -oogen--ooga log (1z)2 (1
22-1221 + (1g)) -20
2000- 120 120--B1 ))
T-B
(8)
Now bring it back to Equation 66. we get
Σ 7c fx
(1+ (ug)2a-1 2a-1
+ log up log ug
(1
24 + 2xdn""
12a21 +
1 2a 12ac1
1+
log log o log vo
(17) 1-2
+ c100 + ((c)((1))
120-021 021
12a--<11 -<1
(og) 5a-
1 2a +
For the LHS, we have
T-1 1
T-1 u1)1
V V
Σ
V Vx fx b1)l
t=
max
U841
u(+1)
T
11
V x (x+,
max {u7. v
From here, by combining two incqualites above and noting that Σ. a vill S u.g can already conclude that [[ (VVa/(<e, w:) = O(). Now we will provide an explicit bound. We consider two cases:
(1)
If o S of, then
T
| Vaf((r,, 2012
1=0
24 (u7)
(w7)) (1 +1+10 log of log vo))
(u bog)i-a
2nd
12021 +
1- 2a 12021
(vg) 2a-1
C1Cs (uF)
(VF) (1 + log of log vo)
120-821 821 + (v:))
at+
+ C1c41""
-12--33 B<1
1/
(og)
20-)22-B11
2c 3
20

---

Published as a conference paper at ICLR 2023
2 (uf)
(ug)
(2i))
log ej - log vo)
(ef) (ug) 1-
2nd
12 +
1 20
11
(v)
2a
1 - 2a
+ CsCs (uT)
(UT) (uf)
(UT)
(1 + log oj log vo)
120 A21 + (wT) 1-
+ c1cm1
-2 BE1
(v0)
2a-
1 2a 3
2 (u
22(1-a)(1-lop) 16)/2
e(1 - a) (2)) 2a (1
Lta
(uz)
2xd
2222 + - 20 12a21
11
C1Cs (uf)
1te 2e 2e log 10)/2 (2f)
2
120-821 821 + (v7) -a78
C1CM7"
120 BKl
17
c(1 a) (2
20 20-8-1
2a
+
(9)
where we used x (c log for x > 0, m > and c R in the last inequality. Also, if
O < a, < and b; are positive constants, and S Σi= b, then we get S n " 61((-a,.) Now consider of the in the previous statement, and note that the LHS of Equation (9) equals vij vg Then we can get
2A4
(x)e(1-a)(1 (1-oo_)))1)))))) 1/1/
1-a
2xl a/
2 S 50% +
+5
12021 +5
120c
11th
c(1 a) (v/g (1g)2--1
I 2a
C1
20 el)-a))1 log 1/2
C1C47/"
5
11
5
e(1 a) (1g) 2 3-1
1 12n 12--321
821
+5
1 2a +
12
9-1-
(10)
Note that the RHS is constant and also upper bound for ETD V
(2) If of S vz. then we can use the upper bound for uy from Equation 8).
We now discuss two
cases:
1. 2o + B. Then we have
T-1
V [=f(=,,))))
t=0
2A + cics
+ log vif. - log vo
(uf)
+ C1e41 (17)2-2at9
+ 2xd
12021 +
12ac1
11"
(og) 20-1
1 2xx
1 2a + 3
C1 (17²) (o7) (07)1- 1-204 (
T
C5 +
1- 2a + 3
2A4 c 2kl
1+ log 1p log
C/T2
17th (ug) (1g)1-221 1-2043
(mz) 2a-1 (1z) (17)2a-1
1-20 12021 +
(1 2xx (og)0
12021
+ 1 2a +
C5
C4 (17²)
(vT) 1
1-22-+
11
1-8
(ug) 20+
1 2x +
2 + C165
e(1 (1-2a+33) (1-
C1047
2kd
20-1 12021
(1 2a) (1g) 12021
+
1/2h
(vg)
c(1 - 2a + 3) (2gf)
2a +
-
C5
C4 (172)²
(w)) 1- 22- a-20+31a
+
(ug)
28+8
1 2α +
Note that since > 83 we have
1 1 2a + 3 (1 2a + 8)a
(1 - aja
a(3 - a) 1-
<
1
<1.
1
21

---

Published as a conference paper at ICLR 2023
Therefore, with the same reasoning as Equation
10
(Vr,(x1,)))1 27
100
2 + 4.00
C/CATT"
2kle -2a+ -logg
2xl
12021 +
12a41
17th
(vg) 1 1-20++
1 20 + B
e(1 2α + 3) (vg) (uz)2a- 20
(1-20) (vg)
C4 (17²)2
1-11-2043)1+
C5 (ug)
+
+ 20
2a + 3
which gives us constant RHS.
2a 2 1+ B. Then we have
V V f22, 8111
0=0
2A4 + cies
2nd (1 + log oij
log v0)
C1 (1 + log oz - log v0)
11
(og)
20-1
(vg 2a 2--3-1
C4 (1)²)² (1 log us log v0)
1
Cs +
(1g) 2a--311 3-1
2 + cJCs
21rl (1 + log 17 log v0)
C1 (1 log oi log v6)
17th (vg) 1/4
(uz) 20-1
(vz) 1/4
(v 2a 8-1 (v7) 1/4
C5
(1)²)² (1 + log 17
log uB)
(17)
(2g) (133
(og) 20 B (uf)
11-81
2 + c10s
SAle 1//g
e (v1)) 2012) + 4c/ ( (1-log log v01/4
17th (v7) 1/4
e (vg) 20 B-1 20-B-1
12x
4cza (17²)² 2 e(1 (11-8)(1-)))) (10(1110 o5 15)/(4))
C5
((7)) 1/2
91 (ug)
e(1 B) (vz) 20 200-8-1 3-1
which implies
T
V. f w1)1 S ur
t=0
2 + c
4ct 6l log 1/1/4
2
11th (1z) 1/4
10
((1g)2011
e (vg)) 20-1811
a (17²)² ell (11-8)(1-1og) vz) v5)/(a())
T-
C5
+ 2n
e(1 3) (v 200))21111111
(vg)
Now we also get only a constant on the RHS.
Summarizing all the cases, we finish the proof.
C.2 INTERMEDIATE LEMMAS FOR THEOREM
Lemma C.I. Under the same setting as Theorem 3.2 for t to to t and any X > 0, S.
I| 1/+1l1 (1 Ar) || vill St.
22

---

Published as a conference paper at ICLR 2023
then have
E
(f(x) - f(z (())
E
Σ
-
1Iue
vill2
1
|b++1 364 11²)
2
2% + Ax)
Lf=to+1
Ti
Ve
20) 11
Se
+ E
+E
2 + Ac)
Proof. Letting d
2(0841) )a we have
1n7"
1b+1 - Vi+ 11+ 11?
$ (1 + Xx) 11++1 - 11 S.
= (1 + xx)
Py (/ + V f wi) - -vil + S
U/ + Ya V (ae: 3/4) - v/¹ 1/1? + St
Σ (1 + Ax)
[lu+ vill + 7² V y [3 v0)l 1|"
+ 27 VyJ (t), vi) + St
= (1 + Xx)
= (1 + X₂)
[1u: - yill 1?? + 7? V of (0 20)1
+ 22 ( (.F((..))).) vi
+ 701lle - vē 11 mellye - vē 12) + St
By multiplying 7((+),)) and rearranging the terms, we can get
2 Vy we), vi vt) - ullys - wE
1 1 70 1i 11
7e(1 + 2,) ||ve+1 vitill + ys (o 8i)||
S.
+
7/2
7e(1 + X.)
By telescoping from t = to to t1 1, we have
yf (2t, vt), -wr) 2
w1)
" l1ye vī 12)
4-11
4--1
<
1 Yoll
1i - v/
11u441 - vitill?
+
+
V
(2, 80
27:
21x + 2x)
2
t=to++
t=
t
S
+ (1
X.)
t=to
Now we take the expectation and get
E
LHS)
> E
Σ Eey
[((V)]((r.)))) ve)
1 live
2a ]|²]]
2
(V (V,s(zt,) we) _/2 l1 wt1l2)
E
Σ
(f( fa ((0)
where we used strong-concavity in the last inequality.
23

---

Published as a conference paper at ICLR 2023
Lemma C.2. Under the same setting as Theorem 3.2
if ef S Cfr t O....,u to 1. then
have
(f(ss (x)e..))) (1)).3a))
E
E
Ra-1
1 Yell
1ive v1
11441 Vi 1
E
10
Y
V VoJ
(1e, 91) w0)l
2%
72(2 + vrve)
2
x2 (Nnr& C 2020)
(1)1)
+ log uia
log vo
(1to
1-2a
1a20.5 +
1a<0.
2p (1j1)
(vg)
20-1
2a
Proof. By Young's inequality, we have
| vita 21 < 101 vi11 + (1 (1+1)) d1
1
| - vīl1
Then letting d 2" and by Lemma C.1
we have
E
(f v2) - f( Bc))
E
7044
115t - 11
|ut41 vēe vi+1l1²) 11²)
27
7e(2 + mm))
1=0
to
11²
I + uore
2
E
V
E
|| will?
2
(2 + pare)
We now remain bound the last term:
1+ pm
E
1 vill"
(2 w))))
+ #3))
E
|| 2/
27
punl (v++1)
1
+ (105t1) 29
E
1l v2 11
2p (172))
u C1
20
to
1o - 36:13
E
24 (111)²
By Lemma B.2 we have
60-1
biq
vill2
x
|1 2x,1
1=0
V..
VIr ve)l
1/1
1=0
8q-1
V VaF( 2
22 (17))
max foe 18t1]
2c
I n² (17))
Σ
Var
Ver(
(uZ+))
2a
24

---

Published as a conference paper at ICLR 2023
S n² (17²)
vo
+
to 1
Vx I (Te, 3/8))
2
(vf) 20
2a
1=
(+1)
(v)t 1-2a
1 + log Vig
log V0
S k (17²)
1.20.5 +
1 c00.5
(2
1 2a
where we applied Lemma B.1 in the last inequality. Bringing back this result, we finish the proof.
Lemma C.3. Under the same setting Theorem 3.2 to is the first iteration such that vto+1 > C, then we have
E
(f vt)
(ares ye))
Yel! 111ee - -vāll²
1
|1e+1 - Vitill% )
T-11
Yt
<
E
+ E
V y
(1ez,
27
(2 + mn)))
2
tm
G2 (17))2
(17²)²
[107)
+
parad (1 2a-3
2(1 wn) (1z))-
E
2x² (17²)
E
V 8011
1 ny
4km7" G2
E
(11))0
11 (1Tp)²² C20-20
(vg)
17 (vg)
Proof. By the Lipschitzness of y" (-) as in Lemma B.2
we have
|| vit2 _| -Ilye+1 v1ll" + 1, vi+all 2 + 2(Be+1 - v. 4i+1)
< Ilue+1 11 + x2n1 V v ve)
+ +2(Ue+1 vi vi vl+11
- llue+1 - vill + x²m
V (It, ve)
-2 231+11 - -vi) Vy (xx) (xx+1 Iz)
(C)
+ 2 (V++1 - vi) (vi Vi+l + (xp) (Ie+1 - -xa)
(D)
For Term C. by the Saaichy-Shwwazznne and Lipschitzness of y (-),
- 2 - v²)² Vy (are) (#++1 - =xa)
-2n (11+1 - = T Vy (are) V V= + 21 (M1+1 vi) (x)) (v (v
- v (xiss m11)
$2m0 - yī ||| Vy (z) V a. (x). + 2n (1141 - yt) T Vyy (x1) (Vaf(zen ve) - Vef( (1))
$ <21lutc+ - yf |nme V f (T., yell + 27 (ye+1 - vt') (xz) ( [x) vt) (xl(
2 2 A
< AMllut+1 - 12
V (I 12 + 2n (31-1 - vi) Vy (x,) (v (V.f(ze. - -aan)--v.ae vaf(In.Vi)
where we used Young's s inequality in the last step and d > 0 will be determined later.
For Term
D according to
and the smoothness of (+) as shown in Lemma B.3
2 (ye+1 - vi¹ (vē Viti + Vy)(xa) (#e+1 -x:))
< 2|| - 2t Illlv - -v + Vy (2xe (Ie+1 - æ:]l
< 211 - will
2 || - 22
25

---

Published as a conference paper at ICLR 2023
=mm vEll] V v ( wi)l
< Lnj Ilye111 vEllG. - || [ we)
=LG*n2
L
< 2 11ue+1-22
vill
V V.J( we)
2r
where in the last step we used Young's inequality and r > 0. Therefore, in total, we have
=
I
| 14 1 de
111e-1 vf122 +
1²2 + 2T
n/
V v. ve)
x2nz
V (a
27 (1/441 - vi'² Vy (x+)
(V (1rs Me) V Vx 113)
X
Note that we can upper bound me by
17
1
T max { (0 1t1s
(u241)
I
(ug)a
and
rf
Ne S
I (uf))
(v(+1))
(1(+2)
0- (ubtz)
(u1t1)
which, plugged into the previous result, implies
1 Ae + TDG² (177)
I
V V 9r ||
| - Bitall s
110e11 - 12:11 +
1²2 +
vi²
(xx) 2a-3 (u(t1)
2r
R² n2n12
V (2 ye)l
217 (v1+1 vt)² Vy (xt) (xy(
(Vzfle, Vzf(z1 ve)
d
2 and get
Now we choose Xe-
pay a(v7,1) )
and
||
Bitall?
L (1F)2
ni V Vz [ mx) |
<
1
1luet1 - -1,1 n²2
2 (vi+1)*
1
pml (ui) 2a-B
4x²
(u/+1)
3 th
V V (Ir, (1)1 + 2ne (ye+1 - -v²² (x1) ( -V
Then Lemma C.I
gives us
E
(f( vi) [are
(1)) ye))
<
E
11yl - vi11
1
|10+1 - vitill )
+ E
T
7t
V y
(Ce, w1
27e
(2 + mm)))
2
Am to
1
D2G² (177)
V VaI (or
E
x²
Ye + 117)))
20- uM (un)
T 4n² (1/+1)
8
+E
mi
| 2 11
(2(2 + papp
f=
26

---

Published as a conference paper at ICLR 2023
T
277 (2 + 1%))
E
(Ve+1 - v2) Vy (xp(
V V ve) - Vaf( Wt
1=
(G)
Now we proceed to bound each term.
Term B
S R² T2G (17²)²
T-
ni
V 2 fo wi)l" 11?
Term
E
wap (ug) 2a-0
27/0
T.2G2 (1p²)2
(1(+)())))))))) 3
V Fz w1 12)
R²²
+
E
ump (1 20-5
2xp max (oe41 2 1 20
T.2 (1p²)²
(1²))((()))))))))))))))))))))(
(1
8
R²
E
V V v1)
AMP (u 2
217" (u/+1) 8
(ubt2)
a-
(1it1) )a
T2G² (17²)²
(11922
V (a 9i 112)
R²
E
Σ
MMP (n)) 2a-B
271² (2))
(uft1)
t=
22
T.202 (11²)²
(1)²)²
(ug) +
vo
T-1
Va Var me) VorTorreao))"))
HaP (u 2
2m (a))a-
(v8+1)
2² L² (17)²
(17²)² 2
E (17))
kap (w 2a
2(1 a ) (18)a=
where we used Lemma B.I the last step.
Term
8 n (1++1)
2k
Term
F
E
V V (Z (x)
L=fo
2x² (172)²
(v)+1) 20
1 2a | v (2), 2011
1 (1p1)2
max
2ith (2t+11
(+1)
2x (17²)²
y
233
E 1 (
(++
V Fz )1
20
(1+1
2x (173)
T-1
E
V V.. (Ie, will
1 (17²)²
(00 (v)o+1)
2a-28
t=
2x² (17)²
V 1V (
E
# ()p2)² 23 23
1=
Term For simplicity, denote m, := (2++)) (y+41 - ut) Vyy(x)) (V=((z)))) - -v.
2
Since y (-) is re-Lipschitz as in Lemma B.2 |meel can be upper bounded as
|mel
|luet1 vf 1 (1x)) v f 26e +IV (21.)))))) will
7/
< ||ut+1 - vill (( (1)) mem 11 [IV
7
27

---

Published as a conference paper at ICLR 2023
Py U + n Vofala vi) - vill [| + (1
1/ + ' V (2 vo) will (//vaTtee.0) we) + 11 [[ (e))
71
(Iv- will + 7o V V. will ([VaT(oe, 1. will
71
I1 y 1r + || 70 V (x wnll) (1Va wn) + +IV (IV will
74
2Gk
G +
G
-T-1
(x0)3
Also note that y and +++1 does not depend on E2', so Egy [me] = O. Next, we look at Term G
Term
G
T
T-1
E
Tho
T
Th- me +
Σ
(m) 7/- m,
11
t1t++
T-1
T-1
rf
M
+
1BEF Th-
[me]] +
(Mt-1 - ne) (-ma)
(u))
ayaa a
-
112
E
M
+
(M--1 mp) M
(u))
t=
2n7
M (ug))
n
4Km G2 Ty (1g)
(17)
(o
Summarizing all the results, we finish the proof.
Lemma C.4. Under the same setting as Theorem 3.2 we have
7014
1
|| - vitz1l()
E
l1ve
27
72 + m1)))
(o
G²
(23G) 12 G²
212
+3 (112) T
4/1 T
- +2 (11))
2 2-88'
Proof.
T
E
Yel
1lye - vi
1
|1 - sit 112)
2/r
72(2 + wn:)
t=0
1.2 (1)
/1
1840
20 +
(v
3
(00))s
llve 1v21?
2170
2
2M
2
(xx))² 2pm7
8
1=1
(18) )² G2
1
T-1
(o(+1)
)²
mm
(op)g)
|
2p22
201
2
(H)
28

---

Published as a conference paper at ICLR 2023
For Term wee will bound it using the same strategy in (Yang et al. 2022a). The general idea to show that 1x -n (u positive for only a constant number times. If the term positive iteration t, then we have
(1l+2) 0
(vt)² pm
V y. 1it 201 11') 8
(uf)) unn
up +
2
Vo (1:z, 300
(op))
1+
(uf))
2
3
Vo (a 22)
S (vf)
1
(ut))
1477) 2
of
3 V y ( Me)
(11)
(u 1-8
2
where in the last inequality we used Bernoulli's inequality. By rearranging the terms, we have the two following conditions
V y M (KT,
2D (w
1-8
un 20
(v)) (v²)1~B
1-8
(o (w
1-8
V fx y
29G
pmp
pap
This indicates that at each time the term is positive, the gradient must be large enough and the accumulated gradient norm, i.e., b/ must be small enough. Therefore, we can have at most
28G
T
23
constant number of iterations when the term is positive. When the term is positive, it is also upper bounded by using the result from Equation
9 V V
vi)
107" (u/+11 15
(o/t) 11 - vi
11 - vē 11
2
(1 1-8
3G2
(1g)1=B 11 - vill
BG2
V f v6)1
12 (og) 1-8
3G
S 11 (18)1=
which is constant. In total, Term H bounded by
(23G) - G2
2 +3 ()p) +1 2-2)
Bringing it back, we get the desired result.
29

---

Published as a conference paper at ICLR 2023
Lemma C.5. Under the same setting as Theorem 3.2
for any constant C, have
Σ
(f(z), f(22, (00)
2n²
(17²)2
V (.I, u1)2
(17)) 1-87
E
E
(171))²
22022/19
2(1 33
1=0
1
Tpu
4 G²
(1)))
+
+
IE
1
(u/))
179 (u
x²
(NON C
+ 2C29) (1)9)²
1 + log ui
log vi
(ug)
+
E
20.5 +
la<0.5
24 (12²)
(2 20-1
1 2a
Gº (17²)²
)17²))
(17)
+
R +
wny (uz)2a-1 20-B
2(1 a ) (vi) (13)a
a-
( G
(23G) - G2
+
2p22110
4
-
(np)
D 2-25
Proof. By Lemma C.2 and Lemma
have for any constant C,
E
(f(ze vt) - fxt, 3c))
1 1
|1 Mitalle)
<
E
11 12
2%
(2 um)
2x² (1)
E
21
v. (Te, ve)
E
Σ
V fzr, w1l1
2
(17²² (2a-23
2² Cu + 20)3) (17
1 log u7 log vg
(u4)--20
+
24 2n
E
(1g)2 20
120.5
2xx
1 la<0.5
LBG² (1TT)
(17²))
+
n²
pal (wg) 20-13
2(1 ()) (1z)a-
E
(17)
+
1
n
ARTy" G²
EE
(wz)
(u
179t
(1g)
The first term can be bounded by Lemma
For the second term, we have
E
E
2
1+1
Σ
V Vuller w6
<
2
(v(+1)
t=
1)"
1-3
E
(w
2(1
3
where the last inequality follows from Lemma
B.1
Then the proof is completed.
C.3 PROOF THEOREM 3.2
We present formal version of Theorem
3.2
30

---

Published as a conference paper at ICLR 2023
Theorem C.2 (stochastic setting). Under Assumptions 3.1 3.6 dient oracles satisfies that for any < 3 < after iterations,
Algorithm 7 with stochastic gra-
T
E
V [
T
1=
4A
Lº (1F)2
2/x (1)²))
G2(1-a)
+
+
162
1
1-a
1
pnn (1z) 2a-
(1 (1-a)m² (ug)a
T
np
16lk2 1/ G2(L+-0
+
+
(1 (1-37T8
11
(uğ)
Tp (1)) T1
2x C + +20A0))
(n²))
1 + log T2 log %o
a20.5 + (2(1-20)
+
(1 2a lac0.5
(1))²
(uf) (1g)2a117
2x² (v)) G²
IK (23G)
- 6
+
1TPT
uI +3 (171) (1)) +2 (v/)) 2-2 T
and
T
E
V vf (ze, v1)l
3
(nTT)
T-1
G2-
8lkn G2+23
$
E
V of (Te, v1)1
+ (1- 3)T8
+
(118)²
C2a-29
T
11
(v
1p"h (x²) T1-3
3
(108 C 2020)
(11)²
(1+ + log TG2
1
log 2i
12-1o
(n2)2
(uz) (2 2 T
la 2055 +
(1 - 2a:) la<0.5
2 G2 (11²)²
I (17²)² G2-20 20
(wg) G²
(23G) I' G2
K
+
puj (ug) 2a-3
(1 a)m (u))
a0)a--8p To
WTP
44 +3 (17²) 1-3
(v)) (1g)) 2- T
Proof. By smoothness of the primal function, we have
2 (x++1) (xx)) < - 7) (z))z,) VaI( - tNTR V Va 80) 1t)
By multiplying on both sides and taking the expectation w.r.t. the noise of current iteration, have
n
(1141)) (Tx1)
E
? V V. (2 yz) ["]
S <<(x(())) Var vc)) + LaF
n) V (ot, vo 12
V f( w1ll + (V=f(x). v Vzf ve)) + IRE
$ V 2. f(,, 21 V (z, (4.) v
+ 2
V Vzl( v=)1l + IrE
me V. Var ve)
Vaf(rr 1212
| ( 9e) (xx))) + I+E
17' V V= wel
2
2
Summing over 0 1, rearranging and taking total expectation, we get
E
V a (2., w:
31

---

Published as a conference paper at ICLR 2023
T
2 (x+)
D (x(+11)
7
S 21
+ 21xE
V
+
V (T,,
(xx{))
2=0
(12)
Term
(xx)) ((x++1)
((50)
((Fr)
T-1
(1)
(1-
1
2
2E
((re))
770
111-1
9/1
76-1
S 2E
max
4*
+
T
T-1
4 max
1
-1
me-1
t=1
AΦ
AΦ
2E
= 2
max u77,
1p
Term J
T P-1
||]
T-
1f
V (Ze, w1 2
2(k
E T/
V ( yr)
21xE
max {oft 18+11
< 21xTT" E
V
(
(ut+1)
a
V F we) 11)
< 21krn E
40
(uf)
(1 )m
1=0
21xmr" T
E
Term K
According the smoothness of f(xe, +), have
T
T
(f(xe, - f f (il.
Vxf(Ir.))) - v4()))
- PE
11ve
yē
<
21rE
Σ
where the last inequality follows the strong-concavigg of y. Now we
C 8lk3 (17²)² a (17²²
20-
and apply Lemma C.5 in total, we have
V (nt, 20l
<
E
V ff 2=)11
+ 2B
AΦ
max {ut, 14
+ 1
21 2
E (
1-a
17
E (nn) 100
(1
1pt
81 G2
E [10))0]]
+
+
+
3
11
(u))
7/0t
(v
A Cu + 2022)
(1)²)2
log ui
logon
1.20. + (1z)
+
E
1- 2a 1a<0.5
(n
(1g) 2a-1
x² D2G² (1p2)
LE (2
22 (1 G2
+
aml (1 28
(1
a)y' (uy)a-p)
E (wf)
(17))-a)
1-
+
32

---

Published as a conference paper at ICLR 2023
In (233) 1 G²
+ 2p. T- (1)²) 1- (v0) (r0))-231 2-2
It remains to bound (17)) for 2 E {a, yt and m 2 0:
(07) mh < (TG²)
Bringing back, we conclude our proof.
C.4 TIÄDA WITHOUUT ACCESSING OPPONENT'S GRADIENTS
The effective stepsize of x requires the knowledge of gradients of y, i.e., 1441. At the end of we discussed the situation when such information is not available. Now formally introduce the algorithm and present the convergence result.
Section 3
Algorithm TiAda without MAX
1: Input: (Zo, (o), 2/ > 0, o/ > O. > O, 0 > O, 0, 0 and > B.
2: for 1, do
3: sample i.i.d. CP and E² and let de = V F(
yei 57) and ot = F(r,, ye: E
4: o oz |"" and U14 12 11","1
5: Ftt1 Tt (vfan) of and Ve+1 Py
1/2 +
(v241)
y
6: end for
Theorem C.3 (stochastic). Under Assumptions 3.7
3.2
3.4 and 3.5
Algorithm 2 with stochastic
gradient oracles satisfies that for any 0 < B 1, after T iterations,
T 1
E
V=f(
20
21xT 22 G2-2a
(vg)) G2
(28G) 12 G2
1
G222-22
+
TT
(1 a)
4p 7 (118) + +2 (ug)2-28
T 2(1 BYTB
(1p²)2²² x2
(1p²)22²
log G.T - log vi) G48
G2-1a+48
22 ap u(np)
(vg) 20- 2
1a20.5
(1 -1 2a)
1a<05
and
T
E
V y (Zr, 21)1
T
(x
G²
(23G) 1'o G²
1
G22
umy
4/ 4p (11²) - (1y)
(mg) 2-
T
((77))22²
R2
2 (172)) R3
(1 (1+ log G2T log ui)
G48
G 22-4
1.20.5 + (1 2n 22
1. 1.
(1g)²
1721
(111)2
(w 20
1 2B
-2
Remark C.1. The best rate achievable is (c-6) by choosing a 1/2 and 8 = 1/3.
Proof. Lemmas C.I and C.4 can be directly used here because they do not have expand the effective stepsize of x, i.e., 7/-- This also the case for the beginning part of Appendix C.3 the proof of Theorem 3.2 up to Equation (12). However,
need to bound Terms (. ( and (K) in
Equation (12) differently. According to our assumption on bounded stochastic gradients, we know
that uzf and my. are both upper bounded by TG2, which we will use throughout the proof.
33

---

Published as a conference paper at ICLR 2023
Term UI
((x+)= - ((x+1))
$(10)
((FT)
(1-
1
2
2F
(1x+)
1/0
112-1
111
M--1
$ max
Φ+
1
1
2E
+
max
170
-1
Th-1
AΦ
AΦ
2A
2E
2E
(u
17
Term (J)
T
V (1 y1 1|/
21x
E
Te
22 'E
1=0
< 21
(1gga
v
+
T-1
Σ
1v++1)
)a
V (are m1) l')
[²]
1=
2|,7j"
E
(nT)
1-a
21 G² G2-2a71--
Term K
According to the smoothness and strong- of f :), we have
T
V=](I,, (xx))
< IE
Σ 11ve
vill?
< 21
(f(r,, - 1 (xr,, (1r..20))
To bound the RHS, we use Young's inequality and have
| - vi s (1+ Ae]1 v1 + 1+ 1.) | - vīl1?
Then applying Lemma
C.1 with d 2
Hiee gives us
(f(xe. f(r (.2e
E
7ef4
1116 - -vill
136+1 - Vi+ 11²)
2%/
12(2 + mvx)
T-1
+ 2
E
V Vyr( ue)
||
+E
||
1/
7' + un:)
t=0
t=0
(1.)
(M)
where the first term is O (1) according to Lemma follow.
C.4
The other two terms can be bounded as
Term
1
Σ
T-1
varlon.wo)l
7
(u8)2-8)
G2 -
<
2
(ug))
3
(1t+1)
)
2(1
3)
2(1 3)
t=
Term M
+ 2 (ul11)
(1
(1 + 2x)
34

---

Published as a conference paper at ICLR 2023
T
29
11 - y8 11
(v))) 1p0
1+1
0
1
R
(w)))
|
(18)) 1p
R²
R²
29
Σ
(18) 3
K(Pp)
1p
(17) x2
(1r)) x²
(17)
29
V (xx y1
(o8)* 3 1p
1(
(oit1)
2a
t=)
(17") x2
(1r") x²
+ log
log e
(17) (17) 1-20
(wt))
1020.5 +
10<0.5
(vg)² 1/2
u(np)2
2a
- 2a
(173) x2
(17) x²
(1 + log G2T log vg)
G43728
G 12-4444811-200 -2x+222
1020.5 +
1a<0.5
(1))) Tp
(vg) 2a
1 2ax
where we used the the Lipschitzness y (.) in the third incquality. Summarizing all the terms, we finish the proof.
35


Reviews:
[{"review_id": "zbo7ShwtKGO", "reviewer": "Reviewer_hniQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an algorithm named TiAda which is a time-scale adaptive algorithm for non-convex-strongly-convex (NC-SC) minimax problems. The algorithm is a single loop and problem-specific parameter agnostic one, which are improvements over the related prior work. The authors provide insight into the design of the algorithm, theoretically analyze the algorithm and empirically validate its usefulness of the algorithm.  The authors also provide some generalization of TiAda to other adaptive methods and empirically validate their usefulness against related baselines.\n", "summary_of_the_review": "The paper proposes a parameter-agnostic adaptive algorithm for solving NC-SC minimax problem. The authors have identified a gap in the literature in this regard and have provided a somewhat novel contribution. The authors provide the intuition as to why their solution addresses the prevailing issues, and theoretically and empirically justify their claims. The algorithm seems to be robust to the hyperparameter choices required by the algorithm, as per the results shown by the authors. The empirical results provided by the authors suggest the proposed methods outperform related baselines. There are some issues regarding the experimental setup in some of the empirical results, as mentioned above under “Weaknesses”. Furthermore, the theoretical results do not improve the prior work in the stochastic setting.\n", "strength_and_weaknesses": "**Strengths:**\n\n1. The proposed method improves upon the main related prior work such as similar implementation in deterministic and stochastic cases (agnostic to the noise level in the gradient). It does not need complex subroutines in the inner loop update for termination.\n2. The work provides extensive validation of the proposed method against related baselines, in their experimental setting, and provides an ablation over some proposed algorithm-specific parameters.\n3. The intuition of the work is clear and the paper is easy to follow.\n\n**Weaknesses:**\n\n1. The rate obtained in Theorem 3.2 is worse compared to state-of-the-art Na-Ada. Could you explain the reason behind this worse rate?\n2. It is unclear how the list of values for r is chosen for results in Figure 2. What is the reason for choosing different orders of ratios for the two other experiments? It seems like NeAda would perform better for smaller choices of r. Furthermore, how was $\\eta_x$ (or $\\eta_y$) chosen for these experiments?\n3. It is not clear why Na-Ada is not included in GAN simulation in Figure 4. \n4. Some typos in the text (e.g. definition in Assumption 3.2). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qWmJLwSMCX", "reviewer": "Reviewer_K2fD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a single-loop adaptive gradient-based algorithm for solving nonconvex-strongly-concave problem with provably efficiency. Previous works only consider directly applying adaptive update scheme to x and y separately thus break the time-scale separation rule which is vital for guaranteeing the convergence. In this paper, the author proposed to adopt a more conservative stepsize for x so that the time-scale separation rule can be followed. The method is simple but effective. The author provide both theoretical and empirical result to verify the effectiveness of their proposed algorithm.", "summary_of_the_review": "Overall this paper is well-written and easy to follow. The algorithm proposed in this paper is also very interesting and intuitive. The only weakness of this paper is its sample complexity result in the stochastic setting, which could either caused by the nature of the algorithm or the proof technique. I will give borderline accept score for now. If the author can address such an issue later I will consider further increase my score.", "strength_and_weaknesses": "Strength:\n(1) It seems to be the first provably efficient adaptive gradient-type algorithm in the non-convex-strongly-concave optimization\n(2) The technique proof is solid and the method is very nature and intuitive\n(3) This paper provides sufficient empirical evidences\n\nWeakness:\nThe major weakness is the sample complexity result in the stochastic setting, which is slightly worse than the standard result (standard is $\\epsilon^{-4}$ and this paper gives $\\epsilon^{-4-\\delta}$). It seems that this additional $\\delta$ is caused by the single-loop structure and the stepsize scheme thus is hard to improve. I notice that in the experiments the value of $\\delta$ is not very small, which means that in theoretical the convergence rate is much worse than SOTA.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZIAI-TYoh0T", "reviewer": "Reviewer_Grdi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose a single-loop adaptive GDA algorithm called TiAda for nonconvex minimax optimization that automatically adapts to the time-scale separation. The algorithm is parameter-agnostic and can achieve near-optimal complexities simultaneously in deterministic and stochastic settings of nonconvex strongly-concave minimax problems. The effectiveness of the proposed method is further justified numerically for a number of machine learning applications.", "summary_of_the_review": "The authors propose a single-loop adaptive GDA algorithm for nonconvex minimax optimization that automatically adapts to the time-scale separation. Only some simple experiment are conducted to verify the algorithm effectiveness. ", "strength_and_weaknesses": "Strength: adaptive stepsizes to nonconvex minimax problems in a parameter-agnostic manner.  \n\n\nWeaknesses: experiment is too simple to verify the algorithm effectiveness. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UXhu1ldwrv4", "reviewer": "Reviewer_1pAx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Finding an approximate stationary point of a nonconvex(-strongly-concave) minimax problem usually requires the knowledge of problem-dependent parameters, especially the step-size ratio between $x$ and $y$. The most relevant method, named NeAda, is the first parameter-agnostic (adaptive) gradient method for nonconvex minimax problems, but this is double-loop, does not have the optimal complexity, and has several other drawbacks as mentioned in the paper. This paper thus proposes a single-loop parameter-agnostic (two-time-scale) adaptive gradient method, named TiAda, which resolves aforementioned drawbacks of NeAda. There already exist single-loop two-time-scale adaptive gradient methods, but they only work with the knowledge of the problem-dependent parameters. The main new ingredient of the TiAda is having the effective step-size ratio of $x$ and $y$ being upper bounded by a decreasing sequence, making the ratio eventually decrease below the step-size ratio threshold. TiAda (with theoretical result) and other adaptive variants are found to work well in practice.", "summary_of_the_review": "This paper constructed a single-loop two-time-scale parameter-agnostic adaptive gradient method, named TiAda, for nonconvex  minimax problems, which resolves issues with the first existing parameter-agnostic method, named NeAda. This TiAda method is a simple modification of existing two-time-scale adaptive gradient methods for minimax problems, but it is quite effective both in theory and practice. I believe this work is an important step towards resolving the non-convergence in practical minimax problems.", "strength_and_weaknesses": "- S1: The method is parameter agnostic.\n- S2: This achieves the optimal complexity for the deterministic case, and the near-optimal complexity for the stochastic case, which improves upon those of NeAda.\n- S3: This can be easily generalized to accommodate other existing adaptive schemes.\n- W1: Although $\\alpha$ and $\\beta$ are chosen to be $0.6$ and $0.4$ as a default throughout the experiment, they are hyper-parameters that might ask for tuning in other practical problems.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster