Online Min-max Problems with Non-convexity and Non-stationarity
Authors: Yu Huang
Yuan Cheng
Yingbin Liang
Longbo Huang
Venue: Accepted by TMLR ()

Abstract: Online min-max optimization has recently gained considerable interest due to its rich applications to game theory, multi-agent reinforcement learning, online robust learning, etc. Theoretical understanding in this field has been mainly focused on convex-concave settings. Online min-max optimization with nonconvex geometries, which captures various online deep learning problems, has yet been studied so far. In this paper, we make the first effort and investigate online nonconvex-strongly-concave min-max optimization in the nonstationary environment. We first introduce a natural notion of  local Nash equilibrium (NE)-regret, and then propose a novel algorithm coined TSODA to achieve the optimal regret. We further generalize our study to the setting with stochastic first-order feedback, and show that a variation of TSODA can also achieve the same optimal regret in expectation. Our theoretical results and the superior performance of the proposed method are further validated by empirical experiments. To our best knowledge, this is the first exploration of efficient online nonconvex min-max optimization.

Published in Transactions on Machine Learning Research (07/2023)
Online Min-max Problems with Non-convexity and Non- stationarity
Yu Huang"
Institute for Interdisciplinary Information Sciences
Tsinghua Universily
Yuan Cheng"
cy16@mail ustc. edu.co
University of Science and Technology of China
Yingbin Liang
liong.899 889 389@osus edu
Department of Electrical and Computer Engineering The Ohio State University
Longbo Huang
longiohaaung eduu.cr
Institule for Interdisciplsnary Information Sciences Tsinghua University
Reviewed on OpenReview: https: // openreview. forum? id= TdzQtbLeVU
Abstract
Online min-max optimization has recently gained considerable interest due to its rich ap- plications to game theory, multi-agent reinforcement learning, online robust learning, etc. Theoretical understanding in this field has been mainly focused on convex-concave settings. Online min-max optimization with nonconvex gcometrics, which captures various online deep learning problems, has yet been studied so far. In this paper, we make the first effort and investigate online nonconvex-strongly-com ary environment. We first introduce natural notion of local Nash equilibrium (NE)-rogret, and then propose novel algorithu coined TSODA to achieve the optimal regret. We fur- ther generalize our study to the setting with stochastic first-order feedback, and show that a variation of TSODA can also achieve the same optimal regret in expectation. Our theo- retical results and the superior performance of the proposed method are further validated by empirical experiments. To our best knowledge, this the first exploration of efficient online nonconvex min-max optimization.
min-max optimization in the nonstation-
1 Introduction
Online optimization (Cesa-Biae -iianchi & Lugosi, 2006) is powerful paradigm for modeling many applications that require decision making based on information available sequentially. Specially, at each time instance, an online player needs to make a decision based on the history information, and then receives a feedback (which can be a possibly adversarial and nonstationary reward or loss value) that may be used in the future. There have been extensive studies this field for various scenarios, such as online convex optimization (Shalev- Shwartz, 2012; Hazan et al., 2016), online bilevel optimization (TaaoonnTTaaaaaaaa (Tarzanagh Balzano, 2022), online federated learning (Chen et al., 2020), etc. Recently, the online min-max (i.e., saddle point) problem has gained considerable interest due to its broad applications in game theory (Roy et al,, 2019; Zhang et al., 2022). multi-agent reinforcement learning (Buşoniu et al., 2010; Zhang et al., 2021), online robust learning (Gabrel et al., 2014; Ben- Tal et al., 2015), to name a few.
On the theoretical side, a line of works have explored provably efficient algorithms for online min-me max optimization. Specifically, Cardoso al. (2019); Fiez al. (2021); Immorlica et al. (2019); Zhang et al. (2022) considered the zero-sum matrix games where the online objective function takes bilinear form.
"Equal Contributions 1 "Corresponding author

---

Published in Transactions on Machine Learning Research (07/2023)
Rivera al. (2018); Roy et al. (2019) studied more general online min-max problem, where the objective is strongly-convex and strongly-concave. Noarov et al. (2021) focused on multi-objective online min-max games, where the reward is convex-concave in each coordinate.
Despite many efforts so far, existing literature on online min-max optimization has mainly focused on on- line convex-concave problems and did not take nonconvexity into consideration. However, in practice, nonconvexity occurs very often in online min-max problems, particularly those that apply deep neural networks (DNNs) for decision making. For instance, in the time-varying two-player zero-sum stochastic games (Mertens & Neyman, 1981; Roy et al., 2019; Zhang et al., 2022), where the payoffs change with time, the policies are modcled by DNNs with strong regularization, and hence the online objective function is nonconversstroog/yyooomaa
Motivated by the aforementioned practical problems, the goal of this paper is to take the first step towards exploring the online paccovex--trrongy-cooee min-max problem with dynamic (and hence non- stationary) loss functions. Due the nonconvexity and nonstationarily nature of the problem, two new challenges arise as explain below.
First, how to define an appropriate notion of regret for the nonstationary environment under the online nonconver setting? The standard notion of Nash Equilibrium (NE)-regret, e.g., Rivera et al. (2018) for online convex-concave problems, which quantifies the difference between the cumulative loss of players and the min-max value of the cumulative payoff loss, is highly unreasonable for nonconvex-concant setting, since the min-max comparator is intractable for a nonconvex-coneave function. Hence, new surrogate for regret is in demand.
Second, with desirable notion of regret, how to design efficient algorithms? A natural strategy to handle the nonstationarity is that at each round, the decision maker first learns a good enough decision based on history losses and then applies it to the adversarial loss of current round. Two key difficulties will arise during this process. First, how to identify a good docision? In nonconvex min-max problems, a good decision usually refers to a stalionary point. The slandard definition of a stationary point involves an oplimization oracle, which is unknown to the decision maker. Thus the decision maker needs to find a surrogate to identify a near stationary point at cach round. Second, when applying the decision based history information to the adversarial loss, mismatch errors arise due to the variability of the environment, which motivates the need for nonstationarity measures.
1.1 Our contributions
In this paper, we handle the aforementioned challenges by introducing new regret measure and develop- ing efficient algorithms for online nonconvex min-max problem with optimal regret guarantees. The main contributions are highlighted below.
We first introduce novel notion of dynamic regret for online nonconvex-strongy-coom min-max problem, called local Nash equilibrium (NE)-regret, which jointly captures the nonconvexity, nonstationarity, and min-max nature of our problem.
Based on the regret notion, we propose an efficient online min-max optimization algorithm, named Smoothed Online gradient Descent Ascent (TSODA). The main idea underlying TSODA is output a near-stationary point at each round by performing two-timescale gradient descent ascent and utilizing a specially designed stop criterion component.
We show that the local NE-regret of TSODA scales 0 ( with iteration complexity of O(Tw), where T represents the total number of rounds and w denotes the size of the sliding window used to define local NE-regret. Such result matches the Q T regret lower bound and the order of iteration complexity of (Tw) provided in Hazan et al. (2017a) for online minimization (where we set the maximization to be over a singleton). Thus, TSODA achieves the optimal performance for online nonconvex-strrogly-oonnae min-max optimization.
We further generalize our study to the setting with stochastic first-order feedback and show that a variation of TSODA also achieve regret of 0 )
2

---

Published in Transactions on Machine Learning Research (07/2023)
We verify our theoretical results and demonstrate the effectiveness of our algorithm through several empirical experiments on real-world datasets.
To our best knowledge, this is the first study on online nonconvex min-mas max optimization with theoretical charactorization of the regret performance.
1.2 Related Work
Online Min-max Optimization. Recently, online min-max optimization, also known as online saddle- point game, has emerged as an interesting optimization framework, and has been studied under various settings. More specifically, the zero-sum matrix game considers the special case that the function is bilinear with a payoff matrix At: where the objective function is given by f((x,y) = x A.y. Several works, for example, Cardoso et al. (2019); Fiez et al. (2021); Immorlica et al. (2019); Zhang
al. (2022) proposed and analyzed algorithms with respect to different notions of regret. For more general objective functions, Rivera et al. (2018); Roy et al. (2019) studied the case where the loss function ft is setongly-convex-stroe concave. Very recently, Noarov et al. (2021) formulated a general multi-objective framework, where the goal is to minimize the maximum coordinate of the cumulative vector-values loss with convex-concave function in every coordinate. We emphasize that all of the above studies did not consider nonconvexity in their objective functions, which is the focus of our study here.
Online Nonconvex Optimization. As online nonconvex optimization an active rescarch area, var- ious works have taken different approaches to handle the nonconvexity. Assuming access to an offline nonconvex optimization oracle to approximate minimizers of perturbed nonconvex functions, Suggala & Netrapalli (2020); Agarwal et al. (2019) studied the performance of "follow the perturbed leader" (FTPL) algorithm (Kalai & Vempala, 2005), and their regrets are all static regret. Further, Hazan et al. (2017a); Hallak et al. (2021); Aydore et al. (2019) considered online nonconvex problems under nonstationary en- vironments, and utilized sliding windows method with window size w. They proposed different notions of dynamic regrets and algorithms, and achievod an order of 0 _ according regret notions. Additionally, Hélion et al. (2020) studied online nonconvex optimization with imperfect feedback. Except first-order opti- mization, Héliou et al. (2020); Roy et al. (2022) considered zeroth-order online nonconvex optimization and Lesage-Landry et al. (2020) studied second-order online nonconvex optimization.
Offline Min-max Optimization. There is rich literature that studies a diverse set of algorithms for min-max optimization with nonconvexity in the offline setting. We next describe only those studies highly relevant to our study here. One celebrated approach is the nested-loop type algorithm (Rafique et al., 2021; Nouiched et al., 2019; Thekumparampil et al., 2019; Kong & Monteiro, 2021), where the outer loop can be treated as an inexact gradient descent on a nonconvex function while the inner-loop aims to find an approximate solution to the maximization problem (sce Lin et al. (2020a) and references therein for good collection of such studies). Another approach, manifesting in the recent works of Lu et al. (2020) and Lin et al. (2020a) considers less complicated single-loop structures. Specifically, the two-timescale GDA analyzed in Lin et al. (2020a) is closest to the implementation at each round of our proposed TSODA method. But it not straightforward to generalize the design to the online setting, and our analysis of the new local NE-regret for online optimization is also very different from such a oflline min-max problem.
1.3 Notations
[T] é T). We use bold lower-case letters to denote vectors in x, y, and denote its forn as ||- We use calligraphic upper case letters to denote sets as in V, and use the notation Py to denote projections onlo the set. For a differentiable function o(-) IRm + R, we let ( denote the gradient of & at x. For a function -(. : R x y + R of two variables, [xf(x. y) (or f y)) denotes the partial gradient of f with respoct to the first variable (or the sccond variable) at the point (x,y). We also use ff y) to denote the full gradient at (x,y) where fx(x,) = (V*f(x, y), y)). Finally, we use the notation O(-) and 2(-) to hide constant factors which are independent of problem parameters.
3

---

Published in Transactions on Machine Learning Research (07/ 2003)
2
Problem Setup
We consider solving the following online min-max (i.e., saddle-point) problem:
m maxyey f((x,y), E [T]
(1)
where fo RT x R" + R is generally nonconver in x but concave in y and where Y is convex set, Such choice of unbounded x and bounded y is commonly used in existing analysis for nonconvex-coneave problems (Lin et al., 2020a; Li et al., 2022; Yang et al., 2022). In our work, such an assumption brings the technical convenience by allowing us to control of, = ||vt,e (x9) - yy at round t = (see Section 6.2 for details). At each round & [7], the environment first incurs loss function Jz. Without knowing the knowledge of ft. the x-learner and y-learner are tasked with predicting x and y: respectively to solve eq. (1) based on loss functions up to round t - 1, i.c., (f()==)- The learners then observe the function fe(-) and sulfer a loss of Yt).
The following regularity assumptions for ft are made throughout the entire paper: Assumption 1 (Smoothness). fo is f-smooth Vt E [T], i.e., v(x,y), y'), it holds that [V - ff((',)') S éll (x, y) y')l-
Assumption 2 (Strong Concavity). The function fc(x,-) is u-strongly concave Vt [T], t.e., given x E R"" Vy,y', i holds that fx(x,y) S Sa y') + (VyJt (x, - lly - -yll Assumption (Boundness). The set y is a convex and bounded set with diameter D 2 0. There exists M 0, s.t. [xx(x,)) S M, Vt [T]xx x E 1.".
The above assumptions are standard in the literature of online learning (Hazan et al., 2017b) and min-max optimization (Lin et al., 2020a;b). While our analysis primarily focuses on the nonconvexity of x, it is worth mentioning that our approach can be extended to the nonconvex-coneave setting by employing a weaker condition for y, as discussed in Lin et al. (2020a).
When the loss ft is fixed for all 6, our framework specializes to the standard nonconver--trongg-oooccee min-max optimization (Lin et al., 2020a;b). Putting into the context of online min-max optimization, our formulation is similar to those in Roy et al. (2019); Rivera et al. (2018); Zhang et al. (2022), where they studied only the case where ft is convex-coneave. However, their standard regret minimization and equilibrium computation will be computationally infeasible for general nunconvex-stoong--oooeae losses. Next, we provide motivating example for the online nonconvex-concant min-max optimization problem that we study here.
Motivating Application. Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) are a popular machine learning model, in which a generator network Gx(+) playes against a discriminator network D2(.) via a min-max formulation given by:
1 Ep-past log Dy(P)
1
min max yx
+ - Be-paoue log (1 - 11 (Gx(
2
2
In practice, GANs are commonly trained with deep architectures, where both the discriminator and the generator are deep neural networks, making GANs hard to optimize and analyze. To address such a challenge, it is theoretically sound to consider an intermediate setting also arising in many real-world scenarios, called GANs with semi-shallow architectures (Grnarova et al., 2017; Moghadam et al., 2021), where the generator Gx(+) is any arbitrary deep neural network and the discriminator (-(-) consists of a single layer network. Such an architecture naturally yields a nonconvex-concavee game, i.e., M (x, y) is nonconvex in x and concave in y. Furthermore, there is a growing demand for GANs to handle time-varying scenarios (Mogren, 2016; Esteban et al., 2017; Yoon et al., 2019), such as time-series data, where generated samples should preserve the temporal dynamics of the data. This requires the GAN's model parameters to be updated in real-time to adapt to the changes in the data distribution,, which leads to an online selling where the objective function (x, changes over time t. Therefore, by combining the above facts, the training of time-varying GANs can be captured by online nonconvex-concave min-max problems. Solving such a type of problems has the potential to advance the field of generative models, particularly in scenarios where the data distribution changes over time.
4

---

Published in Transactions on Machine Learning Research (07/2023)
3 How to Measure the Performance?
3.1 Local Nash Equilibrium (NE)-Regret
We introduce new definition of local regret that suits online ronconvessttongy--onccre min-max prob- lemss Our new metric is motivated by the online nonconvex oplimization literalure; see for example Hazan et al. (2017a); Hallak et al. (2021). Specifically, for each t, we first define the smoothed functions of ft over a sliding-window of size w as:
(x, def 1 (e
(2)
For notation convenience, we treat fx as 0 for all t < O. Morcover, since the averaging preserves strongly- convexily, which implies Fe, is strongly-concave in y, the maximization problem maxyey Fr,w (x, can be solved efficiently. Then, we can naturally define the following function:
(x) def maxyey yx)
(3)
The overall goal of online min- max optimization can be viewed as online minimization over the above defined (-),o() function. Thus, we define the following regret metric with respect to (-,,(().
Definition 1 (Local Nash Equilibrium (NE)-Regret). Let ft be sequence of functions satisfying Assumption 1-3, with (.) defined in eq. (3)- The w-local Nash Equilibrium (NE))Regrel is defined as:
def Σ
VV (x),,(
(4)
Vbr. well-defined since Pt,w differentiable for nonconyex-stronglyycomm 2020a). We next. justify the above notion of the local NE-regret from three aspects.
min-max problem (Lin al.,
Why Norm of Gradient as Metric? At each round t of the nonconvex-concave min-max optimization problem, the objective function can be expressed as minxex" I (x),, where (-)-) = maxyey fe(:.)) is generally nonconvex, and hence finding the global minimum for (x( is NP hard. A common surrogate for the global min-max literature is the notion of e-stationary
minimum of I2 in the offline suuconvex-ttrongyycoone point (Lin et al., 2020a;b) for differentiable rr i.c., an output x such that ||VT,(x)]]? < c. If c O, then x is stationary point. Therefore, it is reasonable leverage such a norm of gradient as the optimality criterion for online nonconvex-coneave min-max optimization.
Why Sliding-windee window Averaging? The motivation behind the window averaging is two-fold: (i) Fr.. and Lr,w represent the average performance during the window, which is widely adopted to handle noises and fluctuations when the environment and the loss function ft encounter mild perturbations and variations. For instance, when each loss function fz is an unbiased noisy realization of some f, the expected gradient norm of a randomly selected update inside the window optimization literature (Bottou et al., 2018) and can reduce the variation caused by noises. Such smoothed notion is also common practice in the field of online nonconvex optimization' (Hazan et al., 2017a; Hallak et al., 2021; Aydore et al., 2019; Zhuang et al., 2020). (ii) In practice, the average performance of system is typical and intuitive notion commonly used to evaluate real-world applications. Suppose decision maker in a time-varying environment (with loss functions fi) has only finite term memory w. Then she naturally wishes to find the best decision based on the entire finite term memory and will choose the average loss function Fr, and tt,w as the performance metrics. As another example, if the environment varies a periodic manner, such an average performance metric during a whole period is naturally adopted in time scries forecasting problems.
standard measure in the nonconvex stochastic
Why Capturing the Dynamic Nature? It is desirable that the regret can capture how well the players adapt their actions to the best decision at each round if the environment is nonstationary and changes over lime. In the well-studied online convex-concave setting, the not of dynamic NE-regrel (Roy et al., 2019; Zhang et al., 2022) is defined for this purpose, since its definition of |E fe (x..)))
IT we view y to singleton, the local NE-regret degenerates to local regret proposed Hazan et al. (2017a).
5

---

Published in Transactions on Machine Learning Research (07/2023)
El= m maxyey f( y)] evaluates the gap to the min-max comparator at each round instead of the min-max solution of the sum of functions over all rounds. For the nonconvex min-max setting, the best min-max comparator at each round can be set as the stationary point of the window function (,, which has zero gradient. Hence, our local regret in eq. (4) can be interpreted as evaluating the gap between (, and its comparator (which equals zero gradient) at each round, and thus implicitly captures the player's adaption to the dynamic setting. In the special brrnngly-ovvee-strongg-ooooo
case, under some mild continuity conditions, a lower local NE-regret with w I implies lower dynamic NE-regret. We provide concrete toy example in Appendix A to illustrate this relationship.
3.2 Variability of Environment
Intuitively, if the environment (and hence the loss function fi) changes drastically over time, it will be hard to obtain meaningful guarantees efficiently. To handle this problem, dynamic (Roy et al., 2019; Zhang et al., 2022) or local (Hallak et al., 2021) regret serves as better performance metrics to take the changing environ- ment into consideration. Such notions typically rely on certain nonstationarity measures of the environment in order to reflect how the system dynamics affects the performance. Therefore, in this subsection, we in- troduce such mcasures of variation for loss functions, which will be crucial in our analysis and capture the nonstationarity of our online min-max settings.
Definition 2 (Variation of Sliding-wintd window). Let us denote (x) arg maxyey (x, We define the sollowing Iwo types of sliding-winee window varialion:
VIT 1
[
sup
V (x. - Vxfi- (x. (x)) 11?,
(5)
x
:=1
T
V =
sup X
Vyff (x,) Vyfi- (x. 1|2
(6)
t=1
Remark 1. [T] primarily measures the drift of ft and fe-w in x, considering that the y-players for these models are determined by x through (-). On the other hand, V2[2] further quantifies the changes of the maximum players for -x, and Fx- -), i.e yi.. and vł-1,w. Therefore, by considering both [ and V (T), we can jointly capture the variations in the environments of the online min-max problem. Remark 2. Clearly, [T[ and [2[ are O(T) if the gradients of fa are bounded and can be zero in the oflline setting, i.., T = 1. A key observation is that if the loss function encounters a periodic shift with certain period length of wx, i.c., fetw- ft, then for w w" and 2 w, we have ft = ft-w and yi.w = 1 which is implied by the fact that Fl+1, Fw As a consequence, for well-tuned w 4 T, the sliding- variations could be considerably smaller compared to T, especially [T] V2[ Oww) in the above case.
4 TSODA:
Online Gradient Descent Ascent
In this section, present proposed method, named time-Smoothed Online gradient Descent Ascent (TSODA), for online nonooveerstrrnn//-oooawa problem, and we show that our approach is capable of efficiently achieving a favorable local NE-regret bound.
4.1 Proposed Algorithm
At the high-level, our algorithm plays following the-leader iterates, aiming to find a suitable approximating stationary point at each round using two-timescale gradient descent ascent (GDA). At cach round t, TSODA performs gradient descent over the variable x with the stepsize 7 and gradient ascent over the variable y with the stepsize T/y on function Fr,m (x, y) until the following Stop Condition is satisfied. Then, TSODA observes the loss function fe+1 be used in the next round. The pseudocode of TSODA is summarized in Algorithm 1.
Stop Condition 1. The terminating condition for Algorithm 1
2x + (1 + -01s) ) Ily+11 - -Py (y+41 + fy Vy Fe, (X441, 1 |/ Fe. (x41), ( Fly
8² 2n (7)

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm Time-Smmother Online Gradient Descent Ascent (TSODA)
Input: window size w 2 1, stepsizes (7,) tolerance 8 >>< Initialization: (x)
1: for t == 1 to T' do
Predict Yz). Observe the cost function ft R R + Set (Xe+1, (x)
repeat
X++1 Xt-1 1ix VxLi. (x++1)
6: Y++1 Py (yt+1 + Fy Ft (x41):
7: until Equation (7) in Stop Condition holds
8: end for
Discussions about Stopping Criterion. Due to the online nature, the design of the stopping condition is to guarantee that the learner outputs a good Xe+1 with small local regret at round 6, i.e,, |[ (x++))ll is small enough. However, in contrast to general online nonconvex games (Hazan et al., 2017a), where the first-order information is available, we do not have direct access to the first-order oracle of ut,w- To circumvent this issue, we adopt the global error bound condition from the seminal paper (Drusvyatskly & Lewis, 2018) to translate conditions on (x into restrictions on tractable V Vt.. Specifically, prove that Dz (X++1) is upper bounded by the left-hand side (LHS) of inequality in Stop Condition I (see Lemma 6.1). Therefore, alternatively we can utilize the accessible information of F to terminate the inmer-loop iterations at time I.
Last-iterate Guarantee. At each round f, the stop condition will be triggered only when the local regret of last iteration is small enough. Such last- itt-iierate type guarantee is different by nature from existing min-max results (Lin et al., 2020b;a), which are only guaranteed visit e-stationary point within certain number of iterations, i.c., where the return & is uniformly drawn from previous iterations. Crucially, will establish the total iteration bound (see Theorem 2) in the next subsection, which indicates that such last-iterate type outputs can be obtained efficiently. Furthermore, since the stopping criterion leads to stronger guarantee, our result is incomparable with former offline iteration complexity in the special case that T ==
offline nourooneex-ttrongyy-oooeee
4.2 Theoretical Guarantees
In this subsection, we provide the regret and computational complexity guarantecs of our algorithm under local NE-regret and highlight several connections with the existing results from offline min-max optimization and online nonconvex problem.
Theorem (Local NE Regret Minimization). Let l/p denote the condition number. Under Assump- tions 1-3, and letting the stepsizes be chosen 1xx θ (1/13() and ny = (11Ee), then Algorithm 1 enjoys the following local NE-regret bound:
JANE ( = ET V (x
3/ (T8+
+ [T]). (w-1)a
(NW)²
Theorem (lteration Bound). Let 7 denole the tolal vamber of ilerations incurred by Algorithom 1. Then can be upper bounded
MM
R TT
2²
376
1152
(w 1)282 V2[T].
82
8²
Furthermore, the number of first-order gradient calls is bounded by O(wT).
Theorems and 2 together reveal the trade-off between the impact of sliding-window size w on the regret and the computational complexity, where larger w leads to smaller regret bound but incurs more gradient calls.
Robustness of TSODA. Our results in Theorems and are expressed in terms of variation measures [T[ and (T( of the environment introduced in Section 3.2. If make the same assumption similar to

---

Published in Transactions on Machine Learning Research (07/2023)
that in Hazan et al. (2017a) that the gradient of fo is bounded, the above theorems provide a robust guarantee for TSODA; namely, no matter how the environment changes at each round, TSODA always ensures Of ( local NE-regret with O(Tw) iterations since V and [2[ are O(T) by definitions. Therefore, the regret can be made sublinear in T if w is selected accordingly. Interestingly, depending on the degree of nonstationarily, TSODA is capable of achieving even smaller local Ee--regee.Particulaar as we discussed in Remark 2, for the scenario that ft is periodic with period w < T, [T] = V O(w).
Optimality of Regret Bound. Note that the basic online nonconvex minimization problem can be viewed special case of our online nonconvex min-max problem, if f( y) takes values independent of y. In such degenerate case, our local NE-regret is equivalent to the local regret analyzed in Hazan et al. (2017a); Hallak et al. (2021). Consequently, the adversarial example that incurs the local regret of S2( +5 constructed in Hallak et al. (2021) can also serve as a worst case example for our online noncovex min- max setting. Moreover, under the same assumption made Hazan et al. (2017a) (which more restrictive than our assumption here), we achiove robust regret upper bound of O = (as discussed in the previous paragraph), which matches the worst-case lower bound, indicating that our bound Theorem 1 for online nonconvex min-max problem is optimal.
Comparison to offline min-max optimization. When the environment is fixed, i.c. fo = or or with wo = 1, our problem specializes to offline min-max optimization and [T] = 12 = O will disappear from our results. Therefore, an immediate implication from our theorems is that GDA is guaranteed to find e-stationary point with O(x (3) iteration complexity. The best known complexity bound for GDA in offline min-max optimization is ? (Lin et al., 2020a). However, as we discussed in Section 4.1, TSODA aims to output with last-iterate type guarantee, which is stronger notion than that considered in Lin et al. (2020a), where GDA are only guaranteed to visit an e-stationary point within certain number of iterations. Thus, these results are not directly comparable.
5 TSODA with Stochastic First-order Oracle
In this section, we extend our online min-max framework to an online stochastic version. This setting is motivated by the fact that, in real world application, such as training a neural network, an oracle with access to the gradient of loss function is hard to reach. Instead, a stochastic first-order oracle (SFO) is used to approximate the ground truth gradient. Similar settings have been studied in Nemirovski et al. (2009); Hazan et al. (2017a); Hallak et al. (2021). Specifically, the formal SFO definition is as follows.
Definition (Stochastic first-order oracle). A stochastic first-order oracle (SFO) is a function S, such that, given a point yx _² V, a random seed C, and a smooth function h: 1 x x + R satisfies:
(.,, is an unbiased estimate of Vh(x,y): (((S(x,:(,,h) y)(x,y)) 0; (x,, h) has variance bounded by 0² > 00:0 :
y)lx s <0
5.1 Proposed Algorithm
With the above definition of SFO, we introduce the stochastic version of Algorithm 1, named TSODA-SFO (see Algorithm 2). Similarly, TSODA-SFO also follows the-leader iterates using two-time scale GDA. Taking the noise brought by SFO into consideration, nested loops and special stopping criterion (Stop Condition 2) are modified accordingly. Specially, (i) SFO results in different coefficients in stop criterion compared to TSODA. (ii) The stopping criterion in TSODA-SFO only ensures that (f is bounded by the threshold plus the variation of SFO. But the variation here does not play an important role, since sliding windows serve variance reduction purpose to reduce the variation in the final expected regret.
Stop Condition 2. The terminating condition for Algorithm 2 is:
2 (122 fly
(0(1+(17)) 2x +0 + (n2) 11vt -py-PyCoe (v² + +, 112 1| < 62/330 62/3w²
(8)
8

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm 2 TSODA with Stochastic First-order Oracle (TSODA-SFO)
Input: window size w 2 1, stepsizes T)), tolerance 8 >> 0 Initialization: (1) 1: for t = 1 to T' do
Cost function ft IR x R R is updated;
Sample V (x), So/u (xi,
4: Set Vi (x) = 11-11 (x), fv- (xr. - V Yr)
5: Set x² = X4, yi = yr, Gx = FxFi, Ye), Gy = FyFi, (t), h ==
6:
while Equation (8) in Stop Condition 2 is not satisfied do
7:
Xi ++1
t xf -7x x.1
k+1 + +Py (yt tny.y. Yt
8:
9:
Sample (x((xt+) Vt k+l] f Se (x++1
Sx(x .Y fi) for i w ,
k+l k+t
10: Set Gk++1 (Gh+), l w Ei=c-u+1 ff(( (x(x+)),+++)
11: k 2 k+
12: end while
13: Xe+1 = xf, Ye+1 = ył, and F (X441, G
14: end for
5.2 Theoretical Guarantees
Denote 7r as the number of iterations of inner-loop at round and thus T =i= т.- Given the SFO and the inner-loop termination condition in eq. (8), one immodiate question is whether Algorithm 2 terminates in finite time. To this end, first establish that for each round 1, the inner-loop terminates with finite iterations Tt provided that å is not too small (recall that ö is the tolerance for stopping criterion).
Theorem (Finite Tteration with SFO). Let l/p denote the condition number, and let the slepsizes be chosen as Txx θ (1/x²L) and fly (LLEE). Under Assumptions 1-3, for any t [T], if 8, w and satisfy
then and T are finite with high probability. Specially, when K E R. is large enough, P(T, > K) = (1/K).
that 8² = 0 x <F'00²
With the finite step stopping guarantee on hand, we next characterize the performance of TSODA-SFO with expected local NE-regret formally in terms of w, T, V [T], V2[7].
Theorem 4 (Expected Local RegRet with SFO). Under the setting of Theorem 3, TSODA-SFO enjoys the following expected local NE regret bound:
382 (300m²+9)o²
E
T 1 w²
3xs (w- 172
[2[T]
+
w [T).
Beyond the previous regret analysis, we next provide an upper bound the overall iteration complexity of SODA-SFO. Similar to Li & Orabona (2019); Hallak et al. (2021), adopt the following stronger boundness assumption the SFO to control the noise caused by SFO calls in the stochastic settings.
Assumption 4. Given any point (x Rm y, random seed Ç, and smooth function h: R x Y, the SFO defined in Definition satisfys that |[S(x, y: h. vh(x,y) < o2.
Remark 3. We remark here that Theorems 3 and 4 do not require Assumption 4, and Theorem provide the finite itcration guarantce with high probability and Thcorem provides an upper bound for expected regret. able to provide
With Assumption 4, which is slightly stronger than the assumplions in Defiiitio 3, the following deterministic bound iterations and the number of SFO calls as in Theorem 5. Furthermore, Thcorem 5 can provide deterministic guarantees rather than high probability guarantees because Assumption 4 controls the variation of noise in an absolute and deterministic manner.
9

---

Published in Transactions on Machine Learning Research (07/2023)
Theorem 5 (Iterations and SFO calls bounds). Under the setting of Theorem 3 and Assumption 4, and suppose that 8² > 8064x202. Then the total number of iteralions salisfies
2MT
96 +
72t
V [T 2
1 172
32
1x
62
2688x*02)
Furthermore, the namber of SFO colls is bounded by (WT)).
The above results also provide a robust guarantee for TSODA-SFO, where TSODA-SFO achieves expected regret of O ( with at most O(Tw) iterations and hence O(Tw²) calls of SFO, as long as [ and [ scale with O(T). Following the similar discussions from Remark 2 and Section 4.2, such condition can hold with relaxed assumptions depending on nonstationarity.
Specially, the variance of SFO defined in Definition 3 zero, then SFO reduces to perfect first order feedback. Hence, as discussed in Section 4.2, the adversarial example provided by Hazan et al. (2017a) is also applicable to the stochastic setting, and thus indicates that the expected regret ((,zz) reaches optimality. If the set y is a singleton, online nonconvex min-max problem with SFO reduces to the online nonconvex problem with SFO. In this case, the term consisting of [2[]] will disappear in our analysis, and our theorems recover the results in Hallak et al. (2021).
6 Proof Overview
In this section, will outline the regret and iteration analyses for TSODA (Theorems and 2).
6.1 Key Ideas in the Proof of Theorem
We can directly decompose the local NE-regret E by Cauchy-Schwarz inequality as follows:
T
T
JANE
<
3
V 2 2
(x:)11
+3
33)
V F. 1 (x., Vi,w
(x:))
1=1
Optimization error
Variability of
3
V V (Xt, VxSe-w (xe, Vi,w (xx)) 11?
Variability of In the following part, we will interpret each error term and provide a high-level overview of how to control them.
Optimization error. This term arises due to the overarching strategy of TSODA, which is to perform two-
timescale GDA at each round in order to seek an approximate stationary point of Ft (-). The following key lemma shows that if Stop Condition is satisfied, then (x.,)) < 82
= when TSODA enters the t-th round. This implies that the optimization error can be controlled by 378² w²
Lemma 6.1. Given pair yx E R V, for t [T] and 0, it holds that
lly - Py (y + ty Fr (x, 2 (x, 2* - (1 + (IN)) (((++11)))
V (x)1 52
(- T/y
Variability x and y. These errors occur since the model (fr-)) used for evaluating (x,, y:) is different from the training model (feo) which corresponds to the level of the variation in the environment. i). The variability of x can be directly bounded by the sliding-window variation [ by definition. ii). We show in Lemma B.1 that (x, is f-smooth and (-) is k-Lisschitz, and hence the variability of y 3w2
can further bounded by (w--17 1j2 Vyfe (xe, Vi. (x:)) fi- (x., Ni. (x:) 112, which is coutrolled by [T]..)
10

---

Published in Transactions on Machine Learning Research (07 (07/2023)
6.2 Key Ideas of Theorem 2
The proof of Theorem 2 can be divided into two parts: the inner-loop and outer-loop analysis.
Inner-loop Analysis. Denote the sequence generated in the inner-loop at time t E [ 1] by
x Xt: X A+1 + x 1/x Vx (x),))); ny Vy (xf,v())
y = yo.
Yt xtt Py (y
Let Ti be the number of times the gradient update is executed at the t-th iteration. For convenience, denote Tr O. Note that x = Xx+1 and y = ye+1- such a two time-scale sctting, i.c. 7/x # By: the movement of x slower than yt: and the x-Lipschilzness of (+) indicates that (x,( also moves slowly. The inner-loop of TSODA can be viewed as conducting gradient ascent on a strongly-concalt function FL (xf, :), which changes slowly. Following the standard analysis of offline nonconvex min-max optimization Lin et al. (2020b), we can establish the following descent property:
7x 8
Te-
9 Vx (x). ||" (6nl))lly!?** - -2(1 S (De, (xx) De,w (x++1)) + 0% 2
(9)
1=0
where 81,, Vi (xq)
2212 measures the distance between yp and the optimal solution for y-player given
xf at the beginning of round t. Notice that the LHS of eq. (9) is the quantity in Stop Condition 1 when
Tly = 2. Since TSODA performs GDA at round t only when Stop Condition does not meet, we can further lower-bound the LHS of eq. (9) by
Th 8 5²
2wa Tt, and obtain
O
S ( (xx) P1 (X++1)) 90 o,
(10)
16w2
Outer-loop Analysis. By decomposing (x)) Σt (1), (x1)= obtain:
T 1, (XI-1)) and rearranging terms,
Pi (x)( & (x,,(((+1))
(I. (x (x
(11)
w
Substituting eq. (10) over l E [T] into the above inequality, we obtain
0x r
1
96 T
(fi (xx)) - fi-w vi (xx))) (xT)
1
16w
W
2
(=1
V
1/2
The V1 term can be bounded by considering the boundness of fi. As for the V2 term, we upper bound 80 for f >>> using [yy (xt)) - yē-1, (xxa)l + Ily? (xxe) y! This quantity can be further controlled by the sliding- window variation in y and the tolerance ô in Stop Condition 1 separately. Note that 8 can be directly bounded by D, which the diameter of y.
Significance of Techniques. Based on the sketch of the analysis provided this section, we can now delve into the technical differences between our work and the general online nonconvex games, specifically the work presented in Hazan et al. (2017a). One key difference is that lack direct access to the first-order oracle of &r,w, whereas such information is available in Hazan et al. (2017a). Consequently, while our outer-loop analysis draws inspiration from Hazan et al. (2017a), we must address the challenge of limited knowledge of the first-order oracle and develop novel stop conditions tailored to the min-max setting. More importantly, our inner loop features a more intricate min-max structure, which requires further technical development to handle the dynamics of two players. The analysis presented in Hazan et al. (2017a), which focuses on a single player, cannot be directly extended to our setting. As a result, specialized techniques for min-max optimization must be employed to analyze the iteration complexity in the inner loop.
11

---

Published in Transactions on Machine Learning Research (07 2203)
0.1
0.1
2-
20
Rova
W--
Runk
W
10
4.
Time Horizon
Time Horizon
Time Horzon
Time Hoxizon
(a)
MNIST
(b) Fashion-MNIST
Figure 1: Performance of TSODA with different window size: average regret Ravg round.
1.3
TSODA
TSODA
TSODA GmlineGDmax
TSODA
onlineGDmax
orlinnGDmaa
gradbonn calls
onlineGDmax
gradlon
0:00
graatoonn
6.00
Aucrage Acc
Average Acc
Average Acc
(a) MNIST
(b) Mashi
Figure 2: Comparison of TSODA and onlineGDmax: number of gradient calls vs. average accuracy.
7 Experiments
In this section, we evaluate the efficiency of the proposed TSODA algorithm and verify the theoretical results through numerical simulations.
We consider the min-max problem of training an empirical Wasserstein robustness model (WRM) (Sinha et al., 2017), which has the following form":
min max L(x,y; & Σ (xxxx))s), - 7 -y-ll]] (E.,Z))ED
(12)
x for
where E is the cross-cntropy loss function, N is the number of training samples, x is the network parameter, (Ei, E 'D corresponds to the i-th data sample and label, respectively, and is the adversarial sample N corresponding to &,. Denote {y:) as y.
Training Settings. The real-world datasets we consider are MNIST (Deng, 2012) and Fashion- MNIST (Xiao et al., 2017), each containing 60k samples. We simulate the online WRM model as follows. We randomly split the given dataset into T pieces [D.] and the learner sequentially receives D. At each round t, yr(x,y) = L(x, y: D:). We choose = 100 for the online setting. The network architecture mainly follows Sinha el al. (2017), which consists of three convolution blocks with filters of size x 8, 6 x and 5 x 5 respectively activated by ELU function (Clevert et al., 2015), then followed by fully connected layer and softmax output. Furthermore, we set the adversarial perturbation 7 {0.4, 1.3), which is consistent with Sinha et al. (2017).
Metrics. Since we do not have access to the first-order oracle of V in practice, two alternative per- formance metries are considered, which capture the essence of the online setting and are consistent with the definition of our local NE-regret. The first metric is the stronger notion we utilize in the stop cri- terion, which provides an upper bound for (xx:)(( Observing that the projected gradient of y does not change significantly in experiments, we only compute V y+ll and report the average Ravg و E (x,,,, The sccond metric is the average accuracy, where we evaluate the test accuracy of output (x,, from the last round on the newly coming D, and report the average from round 1 to L.
of these at each round t, which serves as an approximation of 2 (
The Effect of Window Size with different w. It can be obscrved that as w increases from 2 to 10, the local regret becomes smaller, which verifies the bound in Theorem 1 and justifies the usage of large window size.
In Figure 1, plot Ravg of TSODA on MNIST and Fashion-MNIST
Note that we can choose sufficiently large 7 to make the maximization part strongly-coneave.
12

---

Published in Transactions on Machine Learning Research (07/2023)
TSODA vs. Baseline Algorithm. To further investigate the performance of TSODA, conduct exper- iments to compare it with baseline algorithm. Note that to our best knowledge, there has been existing formal studies on the performance of any developed algorithm for online nonconvex min-max problems. Here, we consider a bascline algorithm, which is a natural extension of the well-known offline min-max method GDmax (Jin al., 2020) to the online framework, named orlineGDmaz: Specifically, onlineGDmax replaces the inner-loop procodure of TSODA by the nested-loop GDmax, i.c., at each iteration in the inner-loop of round i, onlineGDDaxx will firstly maximize the function by multi-step gradient ascent for y, which is 10 steps in our setting, and then perform one-step GD for Typically, the stepsizes for GDmax are chosen to be equal, i.c. 1/x = -y (Sinha et al., 2017). In Figure 2, TSODA achieves similar accuracy to onlineGDmax but with significantly fewer gradient calls, which demonstrates the efficiency of our approach.
8 Conclusions
This paper provides the first analysis for the online nonconvex-concav min-max optimization problem. We introduced a novel notion of local Nash Equilibrium regret to capture the nonconvexity and nonstationary of the environment. We developed and analyzed algorithms TSODA and its stochastic version with respect the proposed notions of regret, establishing favorable regret and complexity guarantecs. Furthermore, we conduct experiments with real-world data to validate the theoretical statements and show its superiority in practice.
Acknowledgments
The work of Yu Huang and Longbo Huang is supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108403,, and Tsinghua Precision Medicine Foundation 10001020109.
References
Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pp. 18 29. PMLR, 2019.
Sergul Aydore, Tianhao Zhu, and Dean P Foster. Dynamic local regret for non-convex online forecasting. Advances in neural information processing systems, 32, 2019.
Aharon Ben-Tal, Flad Hazan, Tomer Koren, and Shie Mannor. Oracle-based robust optimization via online learning. Operations Research, 63(3):628 638, 2015.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 2018.
Lucian Buşoniu, Robert Babuška, and Bart De Schutter, Multi-agent reinforcement learning: An overview. Innovations in multi-agent systems and applications-1, 1, pp. 183-221, 2010.
Adrian Rivera Cardoso, Jacob D. Abernethy, He Wang, and Huan Xu. Compoting against nash equilibria in adversarially changing zero-sum games. In JCML, 2019.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference Big Data (Big Data), pp. 14.24. IEEE, 2020.
Djnrk-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprinl XXii:1511.07288 2015.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2916):14 2012.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathemalics of Operations Research, 43(3):919 9491 2018.
Cristóbal Esteban, Stephanie L Hyland, and Gunnar Rätsch. Real-valued (medical) time series generation with recurrent conditional gans. arXiv preprinl or Xiv: Rfv:1706002633 2017.
Tanner Fiez, Ryann Sim, Stratis Skoulakis, Georgios Piliouras, and Lillian RailifT. Online learning in periodic zero-sum games. Advances in Newral Information Processing Systems, 34:10313-10033 2021.
Virginie Gabrel, Cécile Murat, and Aurélie Thicle. Recent advances in robust optimization: An overview. European journal of operational research, 235(3):471-483,) 2014.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint 14X6::100..280 2014.
Paulina Grnarova, Kfir Y Levy, Aurelien Lucchi, Thomas Hofmann, and Andreas Krause. An online learning approach generative adversarial networks. arXiv preprint arXiv:1 03269, 2017.
Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via a proximal-gradient approach. In International Conference on Machine Learning, pp. 4008- 4017. PMLR, 2021.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. In Interna- tional Conference on Machine Learning, pp. 1443-1441. PMLR, 2017a.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games. In Doina Precup and Yee Whye Tch (cds.), Proceedings of the 94th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1433-1441. PMLR, 06 11 Aug 2017b. URL https://proceedi: www.iin...mm.....m.............e mwr.mrrrrseeeeee Sasss//70/hazan11 html.
Elad Hazan al. Introduction to online convex optimization. Foundations and Trends0 in Optimázation, 2 (3-4):157-325) 2016.
Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non-convex opti- mization with imperfect feedback. Advonces in Neural Information Processing Systems, 33:17224 17235, 2020.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Alcksandrs Slivkins. Adversarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 219. IEEE, 2019.
Chi Jin, Pranccth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconcave minimax optimization? In International conference on machine learning, pp. 4880-4889. PMLR, 2020.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-33) 307, 2005.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex- concave max problems. SIAM Journal on Optimization, 31(4):2558- 2555225555- 2021.
Antoine Assage-Landry Joshua Taylor, and Iman Shames. Second-order online nonconvex optimization. IEFF Transactions on Aulomatic Control, 66(10):4866-45 4884-4477, 2020.
Xiang Li, Junchi Yang, and Niao He. Tiada: time-scale adaptive algorithm for nonconvex minimax optimization. arXiv preprint arXiv:2210. 17478. 2022.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Pro- ceedings of Machine Learning Research, pp. 983 983-992 992. PMLR, 2019. URL http://proceedings.. mlr. press/v89/1 11 19c. html.
14

---

Published in Transactions on Machine Learning Research (07/2023)
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex- minimax problems. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6083 6093. PMLR, 13-18 Jul 2020a. URL https://prrceeedings wwtpiiiinnn.........e.ee.e www.mmllrrreee.. wtt.pppssw//////naaaaoo.oo
Tianyi Lin, Chi Jin, and Michael Jordan. Near-optirnal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738 2779. PMLR, 2020b.
Songtao Lu, Toannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions Signal Processing, 68:3676 3691, 2020.
J-F Mertens and Abraham Neyman. Stochastic games. International Journal of Game Theory, 10(2):53 66, 1981.
Monireh Mohebbi Moghadam, Bahar Boroomand, Mohammad Jalali, Arman Zareian, Alireza Daeijavad, Mohammad Hossein Manshaci, and Marwan Krunz. Game of gans: Gamo-theorctical models for generative adversarial networks. Xixiv preprint orXiv:2106. 06976, 2021.
Olof Mogren, C-rnn-gan: Continuous recurrent neural networks with adversarial training. arXiv preprint arXiv:1611.09900 2016.
Arkadi Nemirovski, Anatoli B. Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 19(4):1574-1609 2009. doi: 10.1137/070704277. URL stttps//doi..oo 1177/7777077/77
Georgy Noarov, Mallesh Pai, and Aaron Roth. Online multiobjective minimax optimization and applications. arXiv preprint ar (rXi:2208.00837 2021.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-come concave min-man maxx optimiza- tiom: provable algorithms and applications machine learning. Optimization Methods and Software, pp. 1-35, 2021.
A. Pallares Rivera, He Wang, and Huan Xu. The online saddle point problem and online convex optimization with knapsacks. arXiv: Machine Learning, 2018.
Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra. Online and bandit algorithms for nonstationary stochastic saddle-point optimization. ArXio, abs/ abs/1191..01698 2019.
Abhishek Roy, Krishnakumar Balasubramanian, Saced Ghadimi, and Prasant Mohapatra. Stochastic zeroth- order optimization under nonstationarity and nonconvexity. Journal of Machine Learning Research, 23 (64):1-47, 2022.
Shai Shalev-Shwarte Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2): 107-194, 2012. doi: 10.1561/2200000018. URL http::///oa..rrgg/...555////0000
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certilying some distributional robust- ness with principled adversarial training, arXiv preprint arXiv: 111.::171100011,, 2017.
Arun Sai Suggala and Pranecth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. Algorithmic Learning Theory, pp. 845 861. PMLR, 2020.
Davoud Atace Tarzanagh and Laura Balzano. Online bilevel optimization: Regret analysis of online alter- nating gradient methods. ar Xiv preprint 20x::2207.02829, 2022.
15

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking
machine learning algorithms. arXiv preprint 1XXi:1108.077/ 2017.
Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parancter-agnostic nonconvex minimax optimization. arXie preprint rxXx:2206.00745. 2022.
Jinsung Yoon, Daniel Jarrett, and Mihaela Van der Schaar. Time-series generative adversarial networks. Advances in neural information processing systems, 32, 2019.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview theories and algorithms. Handbook of Reinforcement Learning and Control, pp. 321-384, 2021.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero- sum games. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 26772 26808. PMLR, 2022.
URL https: http:ss:///rooceinng..... mlr. press/vv62 2aa.1//22han2aan.. html.
Zhenxun Zhuang, Yunlong Wang, Kezi Yu, and Songlao Lu. No-regret non-convex online mela-learning. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 3942-3946. IEEE, 2020.
Appendices
A Concrete Toy Example for Section 3.1
16
B Missing Proof of Section
17
B.1 Technical Lemma
17
B.2 Local Regret: Proof of Theorem
19
B.3 Oracle Queries: Proof of Theorem 2
20
B.4 Proof of Theorem 2
22
C Missing Proof of Section
23
C.1 Finite Iteration: Proof of Theorem 3
24
C.2 Local Regret: Proof of Theorem
28
C.3 Tteration and SFO Calls Bound: Proof of Theorem
30
A Concrete Toy Example for Section 3.1
Consider a two-player game characterized by time-varying loss functions {f For any E [T], we define the function as:
f((x,y) =ax² - biy² {
-xx2-bry'
(13)
16

---

Published in Transactions on Machine Learning Research (07/2023)
Here, both a and by strictly positive. It is evident that ft is strongly-convex with respect and strongly-concave with respect to We can straightffrwwrdde compute the min-max value of the problem minxeR maxye[-1,1] yx to be 0, which corresponds to the optimal solution (x,,,, = (0,
Referencing Zhang et al. (2022), the dynamic Nash Equilibrium (NE)-regret is defined as:
T
T
R (T) = Σ fo (x)
Σ
min max f((x,)))- xER yE[-1,1]
We further simplify by setting yr = arg max y fx(, y), as the maximization problem can be effi- ciently solved even in our nonconvex-strrngly-oom (plln(T) E ax27.
setting. Then, for ft defined in eq. (13), we obtain
On the other hand, when w = 1, V (x+) X4, then the local NE-regret
T V (x:)11==
7 _
n (T)
a
1=1
Combining these results, obtain:
T a -
Re (T)
(T)
O2
min 0t t=1
1=1
where C m at
is some positive constant.
From the above derivations, it is clear that in this specific toy case, a lower local NE-regret implies a lower dynamic Ne-regret.
B Missing Proof of Section 4
B.1
Technical Lemma
Recall that (x) maxyey (x, y) and (x) arg maxyey (x, In this section, we first present some technical lemmas characterize the structure of the function D and yi, in the nonconvex- strongly-concan setting, which will be essential throughout the analysis.
Lemma B.1. (.) is (E kl)-smooth with (.) Fx (t) Also, ()) is k- n-Tiipschitz.
Proof. Since the averaging maintains strongly-noncooccavity and smoothness, i.e. Fr. (x, y) is still p-strongly- concave in y and f-smooth. Thus, the proof directly follow Lemma 4.3 in Lin et al. (2020a) and omit the details.
Furthermore, we derive the following lemma to provide the smoothness property of y (x) with respect to t. In other words, given any fixed x, the movement of (x) when changes can be controlled by the variability of environment of the sliding window.
Lemma B.2. For any x E Tmm", / (T), it holds that
(x
(x))
I (x) (x)
p(w
Proof. By the optimality of (x) and vi (x), for Vx, have
- -y- (x)) VyFi, (x. Vi. (x)) 50,V
(14)
(y - y vf_, (x) T Fr (x. ,x 50, Vy E..
(15)
17

---

Published in Transactions on Machine Learning Research (07/2023)
Summing up Equation (14) with y vi-1, (x) and Equation (15) with y (x) yields that
( (x) Vi, (V 1x (x))) 0.
(16)
By the definition of Pt, (x, we have
V Pt (X, - (i-
w-1
w-1
Vxfi-i(x. (x))
=
w
im0
im0
1
(X, (x, ( (x))
w-1 (xx (x (x)))
(17)
Since for any t and fixed x, the f((x.)) is p.strongly-conccve,, we have
(yi-1, - (x)
(x.
+ 44 (1 (x)) s O.
(18)
Plug Equations (17) and (18) into Equation (16), then have
(y 11 (x) Vi, (x)) 1
(x, (x, (x))
w 1 /1l - yi vi (x)) 0.
+
As result.
w lly² Vi (x)
< (yi (x) (x)) 1 { V (x.
(x (x))
K [1 yi (x)ll V ft,
(x, (x, y (x)) (
where the last inequality follows from Cauchy-Schwartz inequality. Finally, by some algebra manipulation, finish the proof following
V St Vi, (x)) Vy yx
|lyi- - (x) s
1(w
The next lemma provides upper bound for the gradient norm of v in term of Vi which justifies our design of stop conditions. Lemma B.3. Given pair (x.y) E mm
V, for t E [T] and w > 0, it holds that
(
2k
+ () + (1x) Ily Py (y + my Vy Pr, (x, x))
I (x)1 <2
Fly
+ 2 V Fw 21.
Proof. By Cauchy-Sehward inequality, have
| (x)ll2 <2 V ar (x) Vx Fx, x)12+ + Fx (x.
22 ly 2.00 (x) y/2 + V F. (x, 1
18

---

Published in Transactions on Machine Learning Research (07 (07/2023)
where the last inequality holds by combining Lemma B.1 and the fact that Fi,u is ê-smooth.
To proceed the analysis, we need an important result about global error condition for proximal gradient algorithrs from Drusvyatskiy & Lewis (2018), which is presented in Lemma B.4 for completeness. Since -x, is y-strongly-concan over y, we have
(x,,) 2 (z) M lyy (z)
which implics (x,-) satisfies the quadratic growth condition. Then applying Lemma B.4, obtain the error bound condition for (x, -) also holds. Specifically, in our setting, μe, 3 = l, and Gr degenerates to the projected gradient mapping with t = Bly Therefore.
(x)
-yl
_ + m1 kny) - Ily Py (y + fly Fi (x, 1
2
f/y
2x
+ 1)(1 + Eny) 1ly - (y + +y Fy (x,
Eny
Thus, we complete the proof.
Lemma B.4 (Restate of Corollary 3.6 in Drusvyatskiy & Lewis (2018)). Consider closed, concer function 9: Rd + R and a C -moolhh conver function f R + R with B-Lápschilz continuous gradient. Denole the prozimal mapping:
1 prox (x) argmin g(()) 2 lly 2r1? VER"
2t
and the prox-gradient mapping:
(x) = (x prox (x (V
Suppose that the function = I + has nonemply set S of minimizers and consider the following conditions:
(Quadratic growth)
(xx) 2 8² + dist? for all x E lo 4" +
(19)
(Ervor bound condition)
dist(x, 7 (z)())
is volid for all x E l +v]
(20)
Then properly (19) implies properly (20) with 7 (2a 1 + 1) (1 + at). Conversely, condition (20) implies
condition (19) with any E (0,--1).
B.2 Local Regret: Proof of Theorem
Proof of Theorem 1. Recall the definition of &t,w and notice that
1 Σ
(x,,, (f((x,)) (x,)(
(x)
max yEy w
f(x.y)
max ye)
w
Then
19

---

Published in Transactions on Machine Learning Research (07 (022))
V 2, (x+)] (x.
(x+))]| (xx)))
1x (X), (x+)) + V VxFi- (Xe, Vi, (xx)) Vx Vx
1
+ (Vxft (x,, N (xx)) - Vxfi-w (xc, (xx))
3x²
< 3 V [x1 + (w- 1)² Vyyf (xe,, Vi (xx)) fi (i-,, (xt) 1|
3 Vxft (x,, (i,) Vxfe-w (x.. (xx)) 11?,
+ 2
(21)
where the second term in last inequality follows from that
- (x
< flly (xx) -i- (x,)
( Vyft, (x, (x,((()) Vy (x. NZ- (x))
(w -
where (a) implied by Lemma B.2. Moreover, for the first term in Equation (21), by Lemma B.3, and the stop condition, obtain
V (xx)11 < w²
Summing over t = 1,... T, and combining the definition of variation mcasures [ and V2[T), then we have
T
(T82 + (kW)
R NE (T) = Σ (x, < w (w 1)2 V + V.lz)).
B.3 Oracle Queries: Proof of Theorem
Denote the sequence generated in the inner-lopp time [T' 1] by
x X x k+1 x Tx VxFi, (xf v:)) y y y k+1 +- Py (y: My Fe, (xf x()
Let T. be the number of times the gradient update is executed the 1-th iteration. Note that x" Xx+1 and y yr+1-
B.3.1 Supporting Lemmas
We present three key lemmas which are important step descent lemmas. In this section, we focus on a crucial quantity, of., = I|y"... (xx) - - which are useful for the subsequent analysis. Throughout our analysis, we choose 7xx 5x37 and F/y = z.
Lemma B.5. Denote the total ileration of inmer-loop at round with 1 < t S T - 1. For convenience,
let Tr = O. For 0 < k < - 1, we have
Lew (xf $ (xx) - - 1xx x() VxFi, (xt.
Bxl2 86
(22)
2
mm
20

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Proof. Since Le,w is (e + smooth and e kl I 2kl, for any x, E R", we have
1 0 (xt) Dr (x) - (xt -x) V (x) S ke l|xt x||?
1/x Vx Plugging x+ x -
Pron (x, y) yields that.
21 (xt) St (x) 1/e 11 (x1 + n V VePrew (x, x)1
+ (VxFi, (x, Pe (x)) T Vx (x,
By Young's inequality, have
t. (x)) T Vxl't,u (x, (VxFr, (x, V 2.
VxPri (x, V (x) 1| + V (x, 112
2
Since V (x) FxFi, (x, (x)), have
Fi f, (x,y) V (x) 11? S E Vi, (x)]??
Putting these pieces together, we obtain
21,0 (xt) 5 (x) ( - xz) l1 Vxl's (x,
+ Th 12 lly (x)
Lemma B.6. For any k 2 O, the following statement holds true,
2 6ot
lyy k+1 11b+1-10
-x - (4
(23)
Proof. By Young's inequality, we have
lly?+1 y/11² 5 211ly vi (xt) 112 + +21lyi, (x+) yt112
2(1 1 + 2 8t (4 k
18%
Lemma B.7. Let 8/, yy (xx) yt
1211 ||? the following statement holds true,
8/ S (1 2x 0b. + 2xx 12 V Fe (xt ,, 111
Proof.
Since fx(x.)) is p-strongly concave and my = 1/e, we have
lly (x xf11 < (1 1 1
By Young's incquality, we have
1 2(x - - Iiyi,w (xx-1) yt + (1+ 2(n 1))llyi, (xt) vi (xf-1) 11?
2x - Ilyi.. (x y22l12 + 2x|1srt... (xt) vi (xx² 112
2x
(1 o + 2 (x+) vi (x+ 1) 1|?
(24)
21

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
Since (-) is N-- w-Lisschitz, we have
V (x+)
Ni,w (x,
112
S
2k
2 |
1|= = 2n²1 Vx Pr 1 )11
8-1
Thus, plug into eq. (24)
8/ 1,00
1
+
2n 1/x
Vx VxFe,un (x, 1x(_-111_0 ",, 1,, 1112
2
B.4 Proof of Theorem 2
Proof of Theorem 2. Denote 7 7= 1- 2x.
from Lemma B.7 and using telescoping we have
k-
(22 11?
8 S 02 + 2x
Σ p k-1
Fx
(25)
Specially, for > 1,
= 1ly!
Vi, (x,))1
1,00
< 2 Vi-1,w
(x-11 ( ||1 + 211y|_1 (x (x ||
8
2
V fxxf(xx (x (x))))) V y-fi-w (x 1 (
Pw2
p²(w - 1)2
Then plug Equation (25) into Equations (22) and (23) from Lemmas B.5 and B.6, and sum over outer loop number.
1xx
Ral 2x m2t
VxFi.u
(xx.x²))
s Fe (xx) -Dr,w (xe+1) + NoTzel 8%.0.
2
j=0
lyttt 11 < (8n 4)0%,.. + (16
8 )ns
-1-1
Σ
VxPe, (x).xt)( 1
11x
1=0
j=0
Letting 1xx
8: we have
V Fr (x1.xi))²
8
(D) (xx)
De,w (x++1)) + Sxel2 02
(26)
7xx
it 1!? < (8k - (n))) 00
+
VxFe, (x2.5.) /|2
(27)
4
3=0
Therefore add Equation (26)
and Equation (27) x M -
we have
7x
1
(x(, xx)) + (6nl) y21l3]
96
V Fr
< (B (x+) De (X++1)) +
2 k,
(28)
8
==0
22

---

Published in Transactions on Machine Learning Research (07 (07/202) /203)
Denote Pu,w (x) = 0, notice that
T
(XT)
2 ( - (xx-1x)
2 f, (x+) - 2011,0(x=)) +
2 (1) 1
Fr F (x,, Vi-1, (x1)))
T
+
(x4. (xx)) +
Σ
( (0)1 - (x)-1))
1=
2
T
T
Σ
(fi(x,,
(x))) fe-w (Xe, ()) +
Σ
( (0-11 (xi) (x
t=2
where (i) follows from that y2- 12 (xi) is the maximizer of F1 (X,,
By some algebra, we have
T-1
Σ
2t (xt) 2 (x
(i. (x)) - (i. (xT)
Sum Equation (28) over L, we have
7x 8
8²
Tx
2w
T
16w
V Fr (x2.x2)) 1| + (ne) +2
-x! x212
t= 3=0
T
98 T
Pi, (xi)
P1 (x++1)) +
Σ
50
1,
2
1=1
T
(f.(xe, - ft-w (x1, yi, (x))) DT (XT+1)
==1
97
96
[2[T] + DED
20w
p
1)2
2MT
9T
9
9ED
M
[2[T]
1
26w
1²
1)2
Hence
+ 376 2T
wa
T
82
+ 1152
(w 1)282
12 +
82
C Missing Proof of Section 5
We first make some notation in Algorithm 2 clearly here, Gh = 1 Ei ( [exx+t,,++)) V V. (x/++ .tt x+l) (VxF..(xx 6+1 .f!t)) V. Fl, (xt k+1
.y v)+1)). And for casimplification, we denote
y y for any t 2 тe-
23

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Before our theoretical analysis of Algorithm 2 and proof of Section 5, define the filtration in Algorithm 2 formally to describe clearly what is known and what is unknown at certain stage.
Definition 4 (Filtration). For any t 2 we denote filtration Fi to be the a-fields that corresponds to the randomness of all gradient feedback up to stage t 1-1 and the decision of ft at stage t. In particular, Ft but doesn't include V Ye), V (x). For any f. 2 1, 2 1, we denote filration FC to be the o-fields that corresponds to the randomness of all gradient feedback up to the k-th iteration in line at stage t in Algorithm 2. In particular, F includes fi, x yr. (x,, (((x .yt ([t"")] -- and Gū-) but doesn't include G., (V (1)x yf)li---w-1
includes St, Xt. and V 1.
C.1 Finite Iteration: Proof of Theorem
C.1.1 Supporting Lemmas
Generally speaking, the lemmas in this section extends lemmas in Appendix B.3.1 to noisy setting, We first provide a descend lemma for Lt. (x) in each iteration of inner loop.
Denote To the total iteration of inner-loop at stage t and ot = || (xx) 1/11? for s k TT
Lemma C.1.
o Fr (x 5 w, (xt)
Ix x() V x ww (x, + nx B
V (x,y) - Vx (x, 11
Proof. Since Lr is (l + ke)- km)-smooth, for any x, x E RRm, we have
20 (x+) - Pr (x) - (x+ - x) V (x) S Ael ||x x||
Set x+ xf+ k+1 = xf, we have xt x = xftt xf -nx Feee
which yeilds that
11,00 (x S $1 1 (xt) 1xx Fr. (xt,x/)
vt) 112 + n V (xi,yt) 1|²
+ 1xx (VxFe,w (xf, xpt) V (xx)) T vxPe, (xt
(29)
By Young's inequality, have
Fix vZ) - V V (x+1) Fxlrra (²) F (xx (xx,y") yt) Vele w (xc)) 112 + | Fi, (x) y!!) 1|2
2
21 Fi - VxFew (xf,y.) 112 + 2/ VxFi, (xf,y.) - V (xf) 1|?
V (t) ())ll 1|2
+ 2
(30)
Since V (xt) VxFi. (xe yi, (x):),, we have
V Fr (xf v!) V (xf) 112 S &lly? (x7)11
(31)
Putting Equations (29) to (31) together, we obtain
tr (x) S (xx) [ - =2xee || 1 Ft,.. (xf ||²
+ 7x 12 Ily;" (xx + V Fe (xf Few (xt, 1p.
24

---

Published in Transactions on Machine Learning Research (07/2023)
The next lemma characterizes the descent property of distance to the maximizer yi.w- Lemma C.2. Let or = ||yi.w (xx) - -ttll the following statement holds true,
8k 1,
<
1 - 4x
oe + 8n n X (x)) .vz 11?
2k
V Fi (x - yt -) - V F (xf5-1
y 1)
Proof. Since f(x,)) .) is p-strongly concave and By = 1/E, we have
1 (x 1!
Vi. (x) 4-1 ') - Py (y, k- + fly V x Fi (xt k-1 .tt ")]
Iy (x) (x(-1)-- Py (y:-1 + Fly V VxFi, (xL
k-1 .8t ()(11))
+Py (y: + my Vx Fr. (x, k-1 "yx(-1) - Py (yr - + By V (x yy -x( 1|
(x--1
S (1 +
1
11 (xx- 1) - -Py (x²-1
1 + My Vx Fr Fi, (x)
2(N5 1)
+(1+2(x-11) Py) t VxFeewx) 1 1yy -y? 1 + VaPin l 1))l
< (1 - _ / +
2x -
VxPL, k- k-1 .t -) - (xtx -1 yx y11
(32)
2x
By Young's incquality, we have
8t, 1 1 2(2k 1)
|1xi, (x - y1
+ (1 + 2(2k - 1)) ())),, (x+² - -ii (x 1|2
4K -1
11xi,w (xx-1) y²11 + 4x<ly (xt) - vi. (x 11?
2(2k - 1)
0/ + 4m|ly/ (xx) - (xx 1) 112
4x
2x
V (x,
.52 - (x - .xt 111
gz
Since (-) is niiisciii we have
M| (xt) - viw 1) S 2n2 - x²-111
22x 2 (x. (x ,t
Thus, plug into
8k
<
1
s + 81 2 / Ft, (x,
-1 111
t,
4k
2x
V Fr
(x ..ا - Vz (x. .y.- -/1
L2
The next lemma shows that updates over y can be controlled by ot. plus a noisy term. Lemma C.3. For any k 2 0, the following statement holds true,
Ily! +++ 1!11? < (4 - 16 +
4k
V VyFo,ur (x/.
y..) (xt
25

---

Published in Transactions on Machine Learning Research (07 2022)
Proof. By Young's inequality, have
|yy 1y++11 - 1²1 2 2
+ Viw (x:) 112 + 221yi, (xt) - y1112
1
4x
$ 2(1
+ 2
f,w0
+
|1 V Fe,er (x). - Vx (x
2x
- (4
_
16
+
4k
K
where (i) follows from Equation (32).
C.1.2 Proof of Theorem 3
Proof. From Lemma C.1
8k 1,
5k-1 + 8n 1 Fr.ur (xx-- , 11
4k
2k
F
(x 1,r,,,,,,-- -イ - Vx Fx. ")1-
Denote 7 7= dx
Given Fk-1 we have
b 8-1 1-j Fx (x2.x)))1
0r S /o
01100 +
8 2
k-1
2k
Σ
? k-1-
Vx
(x, yt) - Vx (x
+
1=0
(1)
$ ? D²
+
32x=m20
+
2x
Σ
h-1
V Vi - xx
(33)
3w2
g2
where the first term of (i) follows from that y is bounded with D, and the second term of (i) follows from the stopping criterion of Algorithm 2 and Σ5=o k- k-1-j < 4k.
Notice that for any fixed &, k and j E [k - 1],
E
V Fr.
(x/ yt) Vx F. no ( x()
Fr (x/ x., vt) VxD (x /11 [
E
E
V
1
Σ [van(x)))))) - Fi
= F
E
k==t-
1
E
E
pi
W2
i=t-w
(181)
(34)
F
2
3
where (i) follows from the property of conditional expectation, (ii) follows from that the SFO calls in line 9 of Algorithm 2 is independent and (iii) follows from definition of SFO and filtration Fi-
Thus take expectation over two sides of Equation (33), we have
E Tott.u < *2² + 32k 222
8k200
(35)
3n
26

---

Published in Transactions on Machine Learning Research (07 2022)
Then by Lemma C.2
Pi. (xx)
22 (x
2 ( ( - T kL) || [ VxFFew (x) xt))
2
7/ la C.
Fr, (xf VxFee (xf 11?
151ex
1 VVPPt, Ft, (x):x() 11
32
Th 81,00
V (xf yt)
VxFi, (xf 112.
(36)
By Lemma C.3
15 k e Emoo
+
15
V Fr,
(xF, yt)
Fx x/)
151x
211x k+1 - -yt11.
(37)
4e
32
Sum Equation (36) and Equation (37), have
15 x2 l xx o
15
L (x+) 2r,0 (x(-1)
+
V Fr (x/ x2)
Vx Fx
>
15nx x
(1x?
k+1 yt11 1|
Fe (x) vt) 11²)
32
The 2 bt,
(x/+
VxFr. (xt vt) 1|
Rearranging the term, we have
11 (x+) Dr,w0 (x/+1)
157x
x (2n²(²
(lll 11 - -y.
12+ 2
V (x (xt.);))²²)
2 32
15
5x² 1
+1 1i (xi Vx (x/, 112.
(38)
18
Take expectation over both sides of Equation (38), plug into Equation (35) and follow from the similar step of Equation (34), we have
E 4 1,
(x.)
Dt.w
(xf-1)
52
2x
(x*D2+
32x
32xtng02
8k2
15
+1)
o²
32w²
3
Rw0
w
Because 7= 1- <
there exist constant K such that 7 D2 < max
122x" 322""'2
8x202 Bu s.
Thus for le 2 K,
4x
3w
have
E 2 (xt)
- 2r,w (x [x(+))]
02
9k²0²
15
0²
5n 22 T/x
+
32n12
3n02
48
3
25
45x 4
15
o²
256u²
wd
48
3
27

---

Published in Transactions on Machine Learning Research (07/2023)
when 8² >
230 bw
16+))a) 257
we set a
267,6 6 256
45x
(15
o² o +1)
+
0.
Then for K 2 K we have
2M 2 E
P1,w xx
1r (xx 11]
K
(i,w (x+) - 12,00 (x(++ 1x(
=
E
k
K
E
De,w (x,) Di, (x Ti 2 k
P(1 < x1+)
k=
K
2 a
Σ
P P(T 2 +
k=k
2 a
Σ
P K) = a (K- P(P(T K),
k=
where the third equation follows from the Optional Stopping Theorem. Consequently, we have To is finite probability, which implies that Σi= 72 finite in probability since it is the finite of finite variables in probability.
C.2 Local Regret: Proof of Theorem 4
Proof of Theorem 4. Following from Equation (21), we have
V (xx)11= Vx Fr,
Ni, (x:)))1
3x²
< 3 3 (x+)12 + -w-1) 1)2
Vy (Xe, (xi() Vysr-w (Xc, (x:)) 1|2
3 क VxJi Yi. (x:)) Vxle-m (Xes (x (x:)) 112
(39)
For the first term
0 - am (x:)11
V4
< 3 V
3 V
I +3 (
< 38 y
+ 3 V
V
28

---

Published in Transactions on Machine Learning Research (07/202) 2203)
Consider [ 1
|| (x 1 vi- 1
(1) 2N
+ +1) + Eyy ) - 1, |
Eyy
2x
21 Prly
+1)2(1 Eny 1| -Py (y: +
2x
+ 2( Enyy
+ 11) + kny) Py (ye + myy (x - Py (yz + my Fi (
(1))
2x
2( Exty
+ +)) + ( Py (yx + f1 7
+ 2( 2x
+ 1) + )2 m (yF (x "">'"
Eny
where (i) follows from Lemma B.4 similar to Lemma B.3 and (ii) follows from the project operator is a contraction.
Then
(x))]
2x
6 Fly
()²(1 Eny) [|y;]|111111 - Py (yz + ny FL + (
+ +6(2k Eny)² (2()221111))1 by )2 V Fi
- )|
+3 Vx Fi 1,
V Fi
|
(1) 8²
2 + 6(2x + Bnly (1 + byy 2
+3 Ft (x 1 V F. (x wd!1!
(40)
where (1) follows from Stop Condition of inner-loop.
Plug Equation (40) into Equation (39) and sum over t, we have
R (T)
Σ
V Lr (xx))1
T
382
+ +8(22 + bnty +
2²
1=1
+
Vx
Fr- 1,
x (x y -
3n
+
V
(x
(x. Vyft (x (x(=t)) 1|
1)2
Vxle
T(-
- Vx (x
2
3782
3n2
3
+
w²
(w 1)2
2
T
Σ
18(2 + )1 + bny) 2
( y( (x
1=1
||
+ 9
(41)
29

---

Published in Transactions on Machine Learning Research (07 2203)
Notice that for any E [T],
V Ft-1,
N
(
E +
E
(x
Fi-1"
(-1
= E E
E
Σ
1-1
w²
(1)
Ey
E
Vyl((x
M1t) -
12
ist
(184)
o²
E
w2
w
u2
(42)
where (i) follows from the property of conditional expectation, (tt) follows from that the SFO calls in line 9 of Algorithm& 2 is independent and (iii) follows from definition of SFO. Similarly, for any t, we have
o²
E
V 1, x
(x
(43)
w
Plug Equations (42) and (43) into Equation (41), we have
E m
NE (T)
=
E
(x:)1]
1=1
37
3n?
3 V + (18(2x + (ny) + (ny) + 9) To2
+
V [T]
w²
(w - 11)
2
w
3T
3R?
(360x² + 9) To²
Vel
[T]
V
w2
(w- - 1)3
w
C.3 Iteration and SFO Calls Bound: Proof of Theorem 5
Proof of Theorem 5. From Lemma C.1
(1-
st-1 + 8 V Fe. (x/ ,y! 1112
<
4k
2x
V
(x
(xt- (x - V. Fx (x + ||
Denote 7= 1 J.
Given F, we have
4x
VxFr.. (1
5 < N
00,00
+
81 2
Σ G b--s
1=0
4-1 k-
+
2x
Ex -
(44)
p
1=0
Then by Lemma C.2
22 (xf 1) < Di (xx) - ( 1/x
122- x( | Fe, (xf (xf 1??
+ t2 5/ + || x Ft, (x Fr (xf 112
(45)
30

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Then plugging Equation (44) into Equation (45) and summing up them over k = 0, ...,,,777 Tt
1, we have
74
$ 11,10 (x7") S f2,00 (xp)
(
(22
T2x
kl)
Fe. xt)ll
+ 1 6²
?
k=
k=0
7-
k 1
V VxFe.w (x2.x21)
+ 8k 3
j
1=0
k-1
Σ
VxF ( (x)
+ 26
k=0
i=0
71
+
// (x v() vxFi, (x) 1|?
I 21 (x²) - -1 - r - 32x 122
F (xf.
k=0
+ l b,w +8n2 Mx 11)
V X 1, (xf yt) (x
k=0
where the last inequality follows from that E nh over and k.
122 S 4n and changing the order of summation
Rearranging the terms, we have
nn - 32x 1/x
V Fr (xf
2
S 11,00 (xx)
De (x++1) + 4ritpe l2 0%.
+ (8x21) Th + +1)
V Ft - V (xx
By Lemma C.3
Ilytt1 2² < (4 1
16%
+
4k
V Vx (xf
(xf
K
Then
ly! - -t'l1 < (16k- 4)6%,u. 128x
V Fi (xf
1x
k=
+ 36k² 7+-1
VxF - rt)1l
Notice that 0,00 I 22 and for any t 1 2
60, = 1ly.- yi (x?))12
2 Tt-1 v2-1, (x - (x
vi, (x
< 2n
||y -Py (y Bl -y 112
2
V yi,
Vyfi-w (x xx(""))) ))
p²( 1)2
82
2
p2(w - 1)2 Vyl(([]] (x.
Vylto (x 11
31

---

Published in Transactions on Machine Learning Research (07 2022)
Letting 1/x
and fy 2. we have
32x22
Σ k=
V 12 (x,,
2 (De, (x+) - Dr,m (xx+1) +
16
64xo22 88.00
7/xx
7
640
Σ
| Fi ,t)
(x
(46)
7
k=0
T--
2 (
(mm + () e15)) 2 lly
2x
7--1
Σ k=0 Fly
1²112
Σ 72(ne) 21y
< 72(mz))(166)
4)8 +9
Vx Fr
(xt
k=
2596
VxPa -
(47)
Am
Therefore add Equation (46) x10ng and Equation (47) X we have
Vxle (x2,v))11 +2 (
(
2x + +)((1 + (my) ) -
1/
f1y
k=U
160
( ( (xt)
De (X++1)) + 1152 13 60 6%.0
7
V v.) - Vx Fx x Σ
+ 2
(48)
Denote (x) = 0, notice that
(XT)
1o (x:) - p 1,0
Σ De - -x + Σ
D (x))) - p, (x--
t=
(F Vin 1. (Xe, Yi (x+))
T
(L. Si (t (xx)) +
1 ( - (x--1))
t=2
T
(I. - -Sal))----rll
+
( (x)
11-1,,(x1-111
where (i) follows from that vi-1, (x1) is the maximizer of F. (x,,
By some algebra, we have
T
1
T w (xx)) - (x(+1) <
(ix(x, so- (x.) P (X
32

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Sum Equation (48) over and take expectation, we have
82
0²
3
2688x*
4
T
T
71-1
Vx Fl (x xt) +2 ( 2x
+1 + k1rr) )
2
lyy
- yt11
1/x
F/y
T
V F (x vt) (x, y. /11
2
k=0
11,00 (xx)
De.e (x++1)) 11521 22 $22
50
(x741 +152m 222 (T 1T-2 1)82
(i. - fo- (x,, Yi. (x:))) (x
w
T
VyJt-w(xx T1-1 N 1xx + D2
11 - 1)2
1=2
2
288T
28
382
2304mx 362
+ M
+
V2[T + x
w2
12(w-
1)2
where the first inequality follows from Assumption
Thus
1
2MT w
TT
# v 1)2
72fm
1/2 [T)
2 +
SED* "
32
1x
2688k+02) 02)
33


Reviews:
[{"review_id": "SxIU5wDeB3", "reviewer": "Reviewer_zzmX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The considered problem is interesting.\n\n- To the best of my knowledge, the analyses in this paper are correct.\n\n**Weaknesses:**\n\n- My understanding is that the definition of the \"local Nash equilibrium regret\" might be problematic, which I will discuss in detail below.\n\n- This paper does not have any experiment results, which might be crucial to understand the robustness of the proposed algorithms to possible parameter misspecification.\n\n- The writing of this paper can be further improved.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies online nonconvex-concave min-max optimization problem. Specifically, its contributions are threefold:\n\n1) This paper has introduced a new notion of regret, which is referred to as \"local Nash equilibrium regret\".\n\n2) This paper has developed an algorithm, referred to as SODA; it has also developed its stochastic version (SODA-SFO)\n\n3) This paper has analyzed SODA and SODA-SFO. In particular, it has provided both regret bounds (Theorem 1, Theorem 4) and complexity guarantees (Theorem 2, Theorem 3, Theorem 5).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**1) About the \"local Nash equilibrium regret\":** My main concern is that the definition of the \"local Nash equilibrium regret\" might be problematic. In particular, I think it has the following issues: first, even if the Nash equilibrium (NE) regret developed in (Rivera et al. 2018) might be problematic. In particular, if the x-learner and the y-learner cooperate, they can achieve small NE-regret at (x, y) that is far away from the min-max optimal solution. However, this definition does not prevent the x-learner and the y-learner from cooperation. This seems to be problematic. Moreover, this NE-regret measures the **performance distance** (due to the absolute value), rather than the **performance loss**. This also seems to be problematic. I am wondering if this metric can be cheated by an algorithm in some practical problems?\n\nThe \"local Nash equilibrium (NE) regret\" seems to be more problematic. Specifically, as its name indicates, it is based on the magnitudes of the gradients (local information), rather than performance loss or distance. Intuitively, it measures how close the solution is to a stationary point (even a very bad stationary point). I am also wondering if this metric can be cheated by an algorithm in some problems?\n\nI fully understand that the NE regret was developed in previous literature and the authors are following existing work. But still, I hope the authors can further clarify these issues in a revision since the regret definition is crucial for this paper.\n\n**2) Experiment results:** I recommend the authors to add some experiment results to the paper. In particular, the proposed algorithms take several parameters, including the window size $w$, the step sizes $\\eta_x$ and $\\eta_y$, and the tolerance $\\delta$. Theoretical results further show that the optimal choices of the step sizes depend on parameters like $\\ell$ and $\\mu$, **which are typically unknown in practice**. Thus, I think it is necessary to demonstrate some experiment results to illustrate the robustness of the proposed algorithms to possible misspecification of these parameters.\n\nI recommend the authors to run SODA and/or SODA-SFO on one or two practical problems and sweep over $w$ and the step sizes. The experiment results should demonstrate if the proposed algorithms are robust to possible misspecification of the algorithm parameters.\n\n**3) Writing:** Overall, the writing of this paper is pretty good. However, I recommend the authors to add proof sketches for key results (e.g. Theorem 1) to the main body of the paper so that the readers can get the high-level idea of the analysis without diving into the appendices.\n\n\n\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CKSJ0q1kn5", "reviewer": "Reviewer_mpMY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Strength__\n\nOverall correct result statements and proofs. Clear structure and writing. Clear assumption and result statements. Adequate justifications for choosing the local NE regret with a preset time window over the existing NE regret notion in online convex-concave minimax problems. Checked all proofs and did not find severe flaws.\n\n__Weaknesses__\n\nOne main point to address is whether the nonconvex-strongly-concave setting is indeed practically motivated. It would be good to have a few simple, structured, practically motivated examples (or references that suggest these) of decision-making problems that are not well captured by existing settings but fit the new nonconvex-strongly-concave setting of this paper. Arguably, \"online deep learning\" is very broad and breaks every assumption. They don't have to satisfy all assumptions but should really demonstrate the value/meaningfulness of the nonconvex-strongly-concave setting. For example, some previous papers (on different problem settings) have included such brief discussions:\n- Immorlica et al. (https://arxiv.org/pdf/1811.11881.pdf) has a dynamic pricing example and a pointer to Badanidiyuru et al. (2018) for their BwK problem setting.\n- Agarwal et al. (http://proceedings.mlr.press/v99/agarwal19a/agarwal19a.pdf) discusses the implication of their results to non-convex games and, in particular, GANs. They also emphasized the relevance of the more broader area of online learning in games at the very beginning.\n\nSee Requested Changes for further questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper studies an online minimax optimization problem, where the objective function is nonconvex in $x$ but strongly concave in $y$. The authors propose a new performance metric, local Nash equilibrium (NE)-regret, which extends the commonly used metric for offline nonconvex-strongly-concave minimax optimization. The authors also define total-variation-type measures to quantify the variability of the environment within a time window. On top of these settings, the authors propose the (deterministic) SODA algorithm, which is OGDA but using the time-window average $F_{t, w}$ as the objective function. Then, the authors establish theoretical guarantees, that is, bounds on the local NE regret and the total number of iterations, where the latter is proportional to the total number of gradient oracle calls. Furthermore, the authors consider the setting of a stochastic first-order oracle (being unbiased & having bounded variance) instead of having full function gradient access. For this setting, they propose a variant of the algorithm, SODA-SFO, and establish its tractability, regret guarantee, and iteration bound.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Definition 2 & Remark 1:\nNote that the first few terms in (5) won’t be 0 under the periodicity assumption. Therefore, $V_{x,w}[T] = V_{y,w}[T] = 0$ is false, unless you define $f_{-1}$, $f_{-2}$ etc. as having periodical values instead of 0. But these are currently defined as $0$ in Section 3.1 and this is used throughout. If you keep the definition of $f_{-1} = f_{-2} = \\dots = 0$, then under periodicity, the variation would likely be $O(w)$, which is ok if period length $ = w \\ll T$.\n\nIn proof of Lemma A.3: \nCan you elaborate the use of the global error bound condition in Drusvyatskiy & Lewis (2018)? I think the RHS of the last inequality in the proof of A.3 is wrong. It looks like a copy-paste error. \nIt should instead be the first term in the RHS of the first inequality in this proof, aka norm of the prox-gradient (projected gradient) mapping. In addition, please further elaborate the use of the global error bound condition in the proof as it’s a key result for this lemma and hence for this work. Corollary 3.6 in D&L (2018) seems to be the right result you are using. You might want to restate it in your notation as a separate lemma. The deduction should be: strong convexity (concavity) of $F_{t,w}(x, \\cdot)$ ⇒ quadratic growth ⇒ error bound condition with RHS being the norm of the prox-gradient mapping.\n\nThe term \"regret\" suggests a comparison with a better objective value in hindsight from an optimal policy. I would really name $R_{w-NE}$ as \"aggregate time-window averaged leader gradient residuals\". You can keep the existing name, but may need to explain how it's indeed a \"regret\"-type metric. Maybe: In the special convex-concave case, a lower $w$-local NE regret (defined in this paper) implies a lower NE regret (defined in Rivera et al., 2018).\n\nWriting suggestions (take them at your discretion)\n\nMaybe: $R_{w-NE}$ → $R^{\\rm NE}_{w}$\n\nIn the paragraph starting with \"Why sliding window averaging?\": … a typical notion that people are interested in real-world applications (there might need to be another “in” after “interested”; in general I would avoid phrases like “people are interested in”; try using “a typical/intuitive notion commonly used in practice”)\n\nSection 3.2 Remark 1: For the well-timed $w$ (“the” → “a”)\n\nSection 3.2 Remark 1: could be considerably small (small → smaller)\n\nProof of Lemma A.1: Since the averaging maintains the strongly-nonconcavity and smoothness” (no “the”)\n\nProof of Lemma A.2: strongly-convave (typo)\n\nProof of Lemma A.2: in term of notions about $\\nabla F_{t,w}$ (remove “notions about”)\n\nSection 5.2: \nYou may want to start this section by “Given the SFO and the inner-loop termination condition in line 6 of Algorithm 2, one immediate question is whether Algorithm 2 terminates in finite time. To this end, we first establish that…”; Also computation tractable → computationally tractable; you may simply remove the last clause “which justifies that …”.\n\n __expectation__ local NE-regret vs. __expected__ local NE-regret?\n\nTheorem 3: $\\tau_t$ and $\\tau$ is → $\\tau_t$ and $\\tau$ are\n\nParagraph under Theorem 4:\n“Beyond finite stopping…” Fix this sentence. Maybe start this paragraph as “Beyond …, we next provide an upper bound on the overall iteration complexity of SODA-SFO. Similar to Li & Orabona … , we adopt the following stronger boundedness assumption on the SFO.”\n", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HVMuC6kkFB", "reviewer": "Reviewer_bH6d", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \nOne of the strengths of this work is the significance of the problem it addresses, as non-convexity and non-stationary environments are commonly encountered in real-world applications. The authors' proposed solution for the problem is complete. Additionally, the paper is well-written, with clear explanations of the problem, its motivation, the proposed solution, and its extension.\n\n### Weaknesses\nThere are several weaknesses in this work that should be addressed.\n1. The function $f_t$ with non-convex $x$ and strongly concave $y$ seems somewhat artificial. While the authors argue that this kind of problem can arise in time-varying two-player zero-sum stochastic games, where the policies are modeled by DNNs with strong regularization, it is not clear whether this is a common problem in real-world applications.\n2. The parameter $x$ is unbounded while $y$ is bounded, and the intuition behind this choice is not fully explained.\n3. The definitions of the non-stationarity measures $V_{x,w}[T]$ and $V_{y,w}[T]$ lack intuition. It is not clear why the gradient of $f_{t-w}$ is measured by $y_{t,w}^*(x)$ with a mismatch in the time index, nor is it clear why the analogous quantity in $V_{y,w}[T]$ is in terms of $y_{t-1,w}^*(x)$ but not $y_{t,w}^*(x)$ as in $V_{x,w}[T]$.\n4. The algorithm shares high similarity with [Hazan et al., 2017] (ICML 2017) Efficient Regret Minimization in Non-Convex Games, but without necessary comparison and discussion, where [Hazan et al., 2017] mainly focuses on the standard online learning setting with only one player. \n5. The extension to the stochastic first-order oracle also appears in the [Hazan et al., 2017].\nOverall, addressing these weaknesses could improve the clarity and impact of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considered the problem of online mix-max optimization, expressed as $\\min_x \\max_y f_t(x,y)$. The paper differs from existing works in two important aspects: \n- firstly, the function $f_t$ is time-varying, reflecting the changing nature of non-stationary environments;\n- secondly, $f_t$ is non-convex in $x$ and strongly concave in $y$, which presents unique challenges in solving the problem. \n\nTo address this problem, the authors introduce a new performance measure, referred to as the local NE-regret, as well as two non-stationarity measures for the variation of gradients. The authors propose an algorithm called SODA, which guarantees $O(T/w^2)$ local NE-regret with $O(T w)$ gradient oracle complexity, where $w$ represents the size of the window, a hyper-parameter in the algorithm. Finally, the authors extend their results to stochastic first-order feedback.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are several major concerns that should be resolved before acceptance. Other minor comments would be also helpful for improving the paper.\n\n1.\t(Major) The authors should provide more intuition and motivation for the artificial definitions and formulations to make this work more convincing to readers. This would require a careful examination of how these definitions and formulations relate to real-world applications.\n2.\t(Major) It is necessary that the authors could discuss the difference between this work and the [Hazan et al., 2017] in terms of techniques. Are there some fundamental difficulties in extending the results of [Hazan et al., 2017]?\n3.\t(Minor) Are there some unique challenges in extending the results to the stochastic first-order oracle?\n4.\t(Minor) In Section 1.1, when illustrating the main contributions of this work, $w$ is not defined yet.\n5.\t(Minor) At the beginning of Section 1.2: $f_t(x,y) = x^T A_t y$, but not $f_t(x,y) = x^T A_t y_t$.\n6.\t(Minor) The line before Definition 1: a missing space before ‘Thus’.\n7.\t(Minor) In my opinion, removing the definition of the NE-regret of [Rivera et al., 2018] and the dynamic NE-regret of [Zhang et al., 2022] may be better. The authors could directly discuss the reason for choosing the gradient norm as the performance and why it can capture the dynamic nature. The current statements are a little confusing.\n8.\t(Minor) The authors could consider changing the abbreviation of their algorithm from \"SODA\" to avoid confusion with the top TCS conference of the same name.\n", "broader_impact_concerns": "The work is mostly theoretical and the broader impact discussion is not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors consider online nonconvex-strongly-concave min-max optimization in the nonstationary environment. They use local Nash equilibrium (NE)-regret as the performance measure, and propose a new algorithm named as TSODA to achieve the optimal regret. Furthermore, the authors extend their result to the setting with stochastic first-order feedback. Some experiments are done to evaluate the performance of the proposed algorithm.

The paper makes significant contributions to online nonconvex-strongly-concave min-max optimization. After discussions, all the reviewers are generally positive with this paper. But there still exist several issues to be addressed:
(a) More justifications of the "local Nash equilibrium regret”;

(b) A more accurate title;

(c) More comparisons with Lin et al. (2020a).

Decision: Accept (poster)