High-probability complexity bounds for stochastic non-convex minimax optimization

Authors: yassine  laguel
yasa  syed
necdet serhat aybat
mert  gürbüzbalaban
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 00:18:29

Abstract: Stochastic smooth nonconvex minimax problems are prevalent in machine learning, e.g., GAN training, fair classification, and distributionally robust learning. Stochastic gradient descent ascent (GDA)-type methods are popular in practice due to their simplicity and single-loop nature. However, there is a significant gap between the theory and practice regarding high-probability complexity guarantees for these methods on stochastic nonconvex minimax problems. Existing high-probability bounds for GDA-type single-loop methods only apply to convex/concave minimax problems and to particular non-monotone variational inequality problems under some restrictive assumptions. In this work, we address this gap by providing the first high-probability complexity guarantees for nonconvex/PL minimax problems corresponding to a smooth function that satisfies the PL-condition in the dual variable. Specifically, we show that when the stochastic gradients are light-tailed, the smoothed alternating GDA method can compute an $\varepsilon$-stationary point within $\mathcal{O}(\frac{\ell \kappa^2 \delta^2}{\varepsilon^4} + \frac{\kappa}{\varepsilon^2}(\ell+\delta^2\log({1}/{\bar{q}})))$ stochastic gradient calls with probability at least $1-\bar{q}$ for any $\bar{q}\in(0,1)$, where $\mu$ is the PL constant, $\ell$ is the Lipschitz constant of the gradient, $\kappa=\ell/\mu$ is the condition number, and $\delta^2$ denotes a bound on the variance of stochastic gradients. We also present numerical results on a nonconvex/PL problem with synthetic data and on distributionally robust optimization problems with real data, illustrating our theoretical findings.

Main paper: 
 introduction: 
 Minimax optimization problems arise frequently in machine learning (ML) applications; indeed, constrained optimization problems such as deep learning with model constraints [24] , dictionary learning [10, 57] or matrix completion [28] can be recast as a minimax optimization problem through Lagrangian duality. Other applications include but are not limited to the training of GANs [59] , fair learning [72] , supervised learning [61, 49, 51, 74] , adversarial deep learning [75] , game theory [54, 58] , robust optimization [4, 3] , distributionally robust learning [46, 75, 24] , meta-learning [70] and multi-agent reinforcement learning [15] . Many of these applications can be reformulated in the following minimax form:EQUATIONwhere f : R d1 × R d2 → R is a smooth function, i.e., differentiable with a Lipschitz gradient; f can possibly be nonconvex in x and nonconcave in y. First-order primal-dual (FOPD) methods have been the leading computational approach for computing low-to-medium-accuracy stationary points for these problems because of their cheap iterations and mild dependence of their overall complexities on the problem dimension and data size [9, 8, 36] . In the context of FOPD methods, there are two key settings for (1):(i) the deterministic setting, where the partial gradients ∇ x f and ∇ y f are exactly available, (ii) the stochastic setting, where we have only access to (inexact) stochastic estimates of the partial gradients, in which case the problem in ( 1) is called a stochastic minimax problem.It can be argued that the stochastic setting is more relevant to modern machine learning applications where gradients are typically estimated randomly from mini-batches of data, or sometimes intentionally perturbed with random noise to ensure data privacy [14, 34, 1] .Convex and nonconvex minimax optimization. In the convex case (when f is convex2 in x and concave in y), several approaches have been considered including Variational Inequalities (VIs) and primal-dual algorithms, see. e.g. [29, 20, 5, 67, 12, 73, 60, 11] and the references therein. One disadvantage of using the VI approach for solving minimax problems (by identifying the signed gradient map G(x, y)≜ [∇ x f (x, y) ⊤ , -∇ y f (x, y) ⊤ ] ⊤ as the corresponding operator in the VI) is that one needs to set the primal and dual stepsize to be the same. This can be restrictive in applications where f exhibits different smoothness properties in the primal (x) and dual (y) block coordinates -this is often the case in distributionally robust learning [73] , adversarial learning [43] and in the Lagrangian reformulations of constrained optimization problems that involve many constraints [47] .The gap function G(x k , y k ) ≜ sup x,y f (x k , y) -f (x, y k ), and the squared distance to the set of saddle points D(x k , y k ) ≜ min{∥x k -x ⋆ ∥ 2 + ∥y k -y ⋆ ∥ 2 | (x ⋆ , y ⋆ ) is a saddle point} are standard metrics for assessing the quality of the output z k = (x k , y k ) generated by an FOPD algorithm after k iterations among many others [35, 73, 20] . In the nonconvex setting, i.e., when f is nonconvex in x, the aim is to compute a stationary point. Let M(x k , y k ) denote a measure for the stationarity of iterates (x k , y k ); a common metric is the norm of the gradient, i.e., M(x k , y k ) ≜ ∥∇f (x k , y k )∥ and its variants such as ∥∇Φ(x k )∥ when f is strongly concave in y, where Φ(•) = max y f (•, y) denotes the primal function -for other metrics and relation between them, see [62] . There are several algorithms that admit (gradient) complexity guarantees for computing a stationary point of nonconvex minimax problems under various strong concavity, concavity or weak concavity-type assumptions in the y variable -see the references in [62] .In this paper, we consider smooth nonconvex-PL (NCPL) problems where f is a smooth function such that it is possibly nonconvex in x and it satisfies the Polyak-Lojasiewicz (PL) condition in y.The PL condition is a weaker assumption (milder condition) than strong concavity in y -in fact, PL condition in the dual does not even require quasi-concavity. NCPL problems constitute a rich class of problems arising in many ML applications including but not limited to fair classification [48] , robust neural network training with dual regularization [48, eqn. (14) ], overparametrized systems and neural networks [42] , linear quadratic regulators [17] , smoothed Lasso problems [23] subject to constraints, distributionally robust learning with ℓ 2 regularization in the dual [72] , deep AUC maximization [68] and covariance matrix learning with Wasserstein GANs [52] . For deterministic NCPL problems, the alternating gradient descent ascent (AGDA) method and its smoothed version (smoothed AGDA) have the complexity of O(κ 2 /ϵ 2 ) and O(κ/ϵ 2 ), respectively, for finding a point (x, ỹ) satisfying ∥∇f (x, ỹ)∥ ≤ ϵ as shown in [70, 66] . Here κ ≜ ℓ/µ is the condition number, where ℓ is the Lipschitz constant of the gradient, and µ is the PL constant. For Catalyst-AGDA, [66] shows also the rate O(κ/ϵ 2 ) for deterministic NCPL problems.In expectation and high-probability bounds. Most of the existing guarantees in the literature for stochastic FOPD algorithms are provided in expectation, i.e., a bound on the number of iterations k (or the stochastic gradient evaluations) is provided for E[G(x k , y k )] ≤ ε or E[D(x k , y k )] ≤ ε to hold (see, e.g., [73, 72, 29] and the references therein). Yet having such guarantees on average does not allow to control tail events, i.e., even if E[G(x k , y k )] is small, G(x k , y k ) can still be arbitrarily large with a non-zero probability. To this end, high-probability guarantees have been considered in the literature [35, 64, 20, 32, 22] . These results allow to control the risk associated with the worst-case tail events as they specify how many iterations would be sufficient to ensure G(x k , y k ) is sufficiently small for any given failure probability q ∈ (0, 1). To derive high-probability bounds, one common approach involves running the algorithm in parallel multiple times and strategically selecting an optimal output to convert in-expectation bounds into high-probability guarantees [62, 37] .Alternatively, advanced concentration inequalities can be employed under light-tail assumptions to control noise accumulation across iterates without requiring multiple runs [53, 27] . For saddle point problems, we note that existing high-probability bounds mostly apply to the monotone VI setting, or to strongly convex/strongly concave (SCSC) minimax problems. To our knowledge, high-probability guarantees for nonconvex minimax problems are non-existent in the literature, even for nonconvex/strongly concave (NCSC) problems with the exception of trivial loose bounds one can obtain by a standard application of Markov's inequality (see Remark 13 for details). In particular, we note that the existing VI literature with high-probability bounds on non-monotone operators such as star-co-coercive operators [20, 55] , do not apply to NCSC problems. 3New high-probability bounds for NCPL optimization. To address these shortcomings, we focus on developing high-probability guarantees for NCPL problems. Among the existing algorithms in the stochastic NCPL setting [64] , stochastic gradient descent ascent (SGDA) methods and their variants are quite popular for ML applications, e.g., training GANs and adversarial learning, as SGDA is easy to implement due to its single-loop structure. Guarantees in expectation for stochastic NCSC problems are well supported by the literature -see [72, 63, 40, 6, 31, 30, 44, 66, 33, 39] and the references therein. To our knowledge, among single-loop methods for NCPL problems, the best guarantees in expectation are given by the smoothed alternating gradient descent ascent (sm-AGDA) method [66] , which can compute an almost stationary point(x, ỹ) satisfying E[∥∇f (x, ỹ)]∥ ≤ ε in O(ℓκ 2 δ 2 /ε 4 + ℓκ/ε 2 ) stochastic gradient calls, where δ 2 is an upper bound on the variance of the stochastic gradients. In this work, we consider the sm-AGDA algorithm, and to our knowledge we provide the first-time high-probability bounds (using a single-loop method that does not resort to restarts and parallel runs) for the minimax problem (1) in the NCSC and NCPL settings. More precisely, we focus on a purely stochastic regime in which data streams over time which renders the use of mini-batch schemes or running the method in parallel impractical; therefore, approaches based on Markov's inequality [62] are no longer applicable (see also Remark 13) .Contributions. Our contributions are threefold:• We present the first high-probability complexity result for the sm-AGDA algorithm in the NCPL setting by building upon a Lyapunov function first introduced in [70] for nonconvex-concave problems. Later, for the same Lyapunov function, state-of-the-art complexity bounds in expectation are provided for the NCPL setting in [66] . In this paper, we derive a novel descent property for this Lyapunov function in the almost sure sense (Theorem 7 and Corollary 8), allowing us to develop useful concentration arguments for it to derive high-probability bounds. Our Lyapunov analysis not only sheds light on the convergence properties of sm-AGDA, but also guides the parameter selection for sm-AGDA. Specifically, we show that sm-AGDA can compute an almost stationary point (x, ỹ) satisfying ∥∇f (x, ỹ)∥ ≤ ε with probability 1 -q ∈ (0, 1) withinT ε,q = O ℓκ 2 δ 2 ε 4 + κ ε 2 ℓ + δ 2 log(1/q) stochastic gradient calls. The lower complexity bound of Ω( 1 ε 2 + 1 ε 4 )for NCSC problems [38, 71] in expectation (see also [63, 72] ) suggests that our high-probability bound for sm-AGDA is tight in terms of its dependence on ε. Furthermore, to our knowledge, these are the first high-probability guarantees for any algorithm in the NCPL setting.• Under light-tail (sub-Gaussian) assumption on the gradient noise (Assumption 3), which is common in the literature [35, 32, 19] , we develop a new concentration result (Theorem 9) that can be of independent interest. From this concentration inequality, we observe that the cost of strengthening the existing complexity result in expectation to a high-probability one is relatively low, i.e., in the final complexity, the probability parameter q only appears in an additive term that scales with ε -2 . Consequently, this represents a non-dominant overhead compared to the ε -4 term already present in state-of-the-art expectation bounds [66] .Algorithm Complexity Problem Metric NC? Epoch-GDA [64] † O δ 2 µsε log(1/q) SCSC G(z k ) ✗ Clipped-SGDA [20] ‡ Õ max ℓ µs , δ 2 µsε log 1 ε log (κ/q) SCSC D(z k ) ✗ Clipped-SEG [20] ♭ Õ max ℓ µs , δ 2 µsε log 1 ε log (κ/q) SCSC D(z k ) ✗ Stochastic APD [35] ▷ * O ℓ log 1 ε µs + (1+log(1/ q))δ 2 log(1/ε) µs ε SCSC D(z k ) ✗ Mirror-Prox [32] * O max ℓD 2 ε 2 , σ 2 D 2 ε 2 log (1/q) MCMC G(z k ) ✗ Clipped-SGDA [20] ♯ Õ max{ 1 ε , δ 2 R 2 ε 2 } log (1/q) MCMC GR(z k ) ✗ Clipped-SEG [20] Õ max ℓR 2 ε , σ 2 R 2 ε 2 log (1/q) MCMC GR(z k ) ✗ sm-AGDA [Our Paper, Coro. 14)] * O ℓκ 2 δ 2 ε 4 + κ ε 2 ℓ + δ 2 log(1/q) NCPL 1 k+1 k j=0 ∥∇f (zj )∥ 2Table 1 : Summary of the high-probability bounds for minimax problem classes when the gradient of f is Lipschitz (with parameter ℓ) and stochastic gradient variance is bounded by δ 2 . The second column reports the complexity (number of calls to stochastic gradient oracle) required to achieve the (stationarity) metric reported in the fourth column to be at most ε with probability 1 -q ∈ (0, 1); Õ(•) ignores some logarithmic terms. Here, µs is the strong convexity constant, µ is the PL constant, andκ ≜ ℓ/µ. Let G(z) ≜ [∇xf (z) ⊤ , -∇yf (z) ⊤ ] ⊤ with z = (x, y) and zk = 1 K+1 K j=0 zj , G(z) ≜ max {z∈Z} ⟨G(z), z -z * ⟩,where Z is the domain of the problem with diameter D ∈ (0, +∞], and G R (z) ≜ max {z∈Z:∥z-z * ∥≤R} ⟨G(z), z -z * ⟩ where z * = (x ⊤ * , y ⊤ * ) ⊤ is a stationary point. The third column reports the minimax problem class. The fifth column indicates whether the results supports nonconvexity, i.e., whether f can be a smooth function nonconvex in x. † [64] is a two-loop method. ‡ Applicable to quasi-strongly monotone G that is star-co-coercive around z * and supports heavy-tailed gradients. ♭ Applicable to quasi-strongly monotone G and supports heavy-tailed gradients. ▷ Supports proximal steps to handle non-smooth convex penalty. ♯ Applies to monotone G that is star-co-coercive around z * . * Makes a light-tail assumption (Ass. 3).• Third, we provide experiments that illustrate our theoretical results. We first provide an example of an NCPL-game with synthetic data and then focus on distributionally robust optimization problems with real data, illustrating the performance of the sm-AGDA in terms of high-probability guarantees.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] The abstract and the introduction reflect the paper's contributions and scope accurately. In fact, we provide adequate references to the results from our paper for the claims in the so that the paper's contributions and scope are easier to understand. 
preliminaries and technical background: 
 Stationarity metric. We consider the minimax problem in (1) for f : R d1 × R d2 → R such that f is smooth (Assumption 1) and f (x, •) satisfies the PL property for all x ∈ R d1 (Assumption 2); moreover, we also assume that we only have access to unbiased stochastic estimates of ∇f such that the stochastic error G(x, y, ξ) -∇f (x, y) has a light tail (Assumption 3) for any (x, y), where G(x, y, ξ) denote the stochastic estimate of ∇f (x, y) and ξ denotes the randomness in the estimator.Our aim is to compute a (ε x , ε y )-stationary point (x, ỹ) for (1) such that ∥∇ x f (x, ỹ)∥ ≤ ε x and ∥∇ y f (x, ỹ)∥ ≤ ε y . We also call (x, ỹ) an ε-stationary point if ∥∇f (x, ỹ)∥ ≤ ε. Clearly, whenever (x, ỹ) is (ε x , ε y )-stationary, then it is also ε-stationary for ε = (ε 2 x + ε 2 y ) 1/2 . Smoothed alternating gradient descent ascent (sm-AGDA): The method can be considered as an inexact proximal point method and was introduced in [70] . More specifically, in each iteration of sm-AGDA, given a proximal center z t and the current iterate (x t , y t ), the method computes the next iterate (x t+1 , y t+1 ) using a stochastic gradient descent ascent step on a regularized function f :EQUATIONFollowing the stochastic alternating gradient descent ascent (stochastic AGDA) steps, the proximal center at iteration t, i.e., z t , is updated as shown in Algorithm 1, where G x (x t , y t , ξ x t+1 ) and G y (x t+1 , y t , ξ y t+1 ) denote conditionally unbiased stochastic estimators of the gradients ∇ x f (x t , y t ) and ∇ y f (x t+1 , y t ). Throughout the analysis we assume that ∇f is Lipschitz, which is standard in the study of first-order optimization algorithms for smooth minimax problems; see, e.g., [72, 73, 75, 63] . Assumption 1. (Lipschitz gradient) For all (x 1 , y 1 ), (x 2 , y 2 ) ∈ R d1 × R d2 , there exists ℓ > 0∥∇ x f (x 1 , y 1 ) -∇ x f (x 2 , y 2 )∥ ≤ ℓ(∥x 1 -x 2 ∥ + ∥y 1 -y 2 ∥) (3) ∥∇ y f (x 1 , y 1 ) -∇ y f (x 2 , y 2 )∥ ≤ ℓ(∥x 1 -x 2 ∥ + ∥y 1 -y 2 ∥).(4) The following condition, known as Polyak-Łojaciewicz (PL) condition is weaker than assuming strong concavity in y, and does not even necessitate f to be even quasi-concave in the y variable. It holds in many ML applications including those in [48, 48, 42, 17, 23, 72, 68, 52, 66] . Assumption 2. (PL condition in y) For every x ∈ R d1 , max y∈R d 2 f (x, y) has a non-empty solution set and a finite optimal value. Moreover, there exists µ > 0 such that:EQUATIONWe assume that we have only access to stochastic estimates G x (x t , y t , ξ x t+1 ) and G y (x t+1 , y t , ξ y t+1 ) of the partial gradients ∇ y f (x k , y k ) and ∇ x f (x t+1 , y t ), where ξ x t+1 and ξ y t+1 are random variables defined on a probability space (Ω, P), i.e., the source of randomness in the gradient estimates. Note that sm-AGDA has Gauss-Seidel updates, i.e., the stochastic estimate of the partial gra-Algorithm 1 sm-AGDA Input: (x 0 , y 0 , z 0 ), τ 1 , τ 2 > 0, β ∈ [0, 1], p ≥ 0 for t = 0, 1, 2, . . . , T -1 do x t+1 = x t -τ 1 [G x (x t , y t , ξ x t+1 ) + p(x t -z t )] y t+1 = y t + τ 2 G y (x t+1 , y t , ξ y t+1 ) z t+1 = z t + β(x t+1 -z t ) end for Output: choose (x, ỹ) uniformly from {(x t , y t )} T -1 t=0 dient G y (x t+1 , y t , ξ y t+1) is evaluated at the updated point (x t+1 , y t ) instead of (x t , y t ). To capture the sequential information flow, we next introduce the natural filtrations that represent all the information available before an update: Let ξ x t and ξ y t be revealed sequentially in the natural order of the sm-AGDA updates, i.e., ξx 1 → ξ y 1 → ξ x 2 → ξ y 2 → ξ x 3 → • • •, and let (F x t ) t≥1 and (F y t ) t≥1 denote the associated filtration 4 , i.e., let F y 0 ≜ {∅, Ω}, andEQUATIONIntroducing multiple filtrations to represent the sequential information flow is common in the study of stochastic algorithms with Gauss-Seidel updates -see, e.g., papers on stochastic ADMM, and [7, 69] ; and we follow the same approach. Consider the gradient noise (errors) at time t ∈ N:∆ x t ≜ G x (x t , y t , ξ x t+1 ) -∇ x f (x t , y t ), ∆ y t ≜ G y (x t+1 , y t , ξ y t+1 ) -∇ y f (x t+1 , y t ). Finally, we also assume that the gradient noise is unbiased conditionally on the past information and that it admits a light (sub-Gaussian) tail. Assumption 3. (Light tail) For any t ≥ 0, there exists scalars δ x , δ y > 0 such thatEQUATIONEQUATIONFor developing high-probability bounds in the learning context, it is common to assume that gradient estimates are sub-Gaussian [32, 35, 18] . While this assumption may not always hold (see e.g. [25, 56] ), it often holds when gradients are estimated via mini-batching, as a consequence of the central limit theorem. It will also hold when the gradient noise is bounded. Additionally, adoption of differential privacy mechanisms within gradient-based schemes [14, 34, 1] , to enhance data privacy, results frequently in sub-Gaussian gradient errors.3 High-probability bounds for sm-AGDAFor analyzing sm-AGDA, similar to [66, 70] , we consider the following Lyapunov function:EQUATIONwhere P (z) and Ψ(•; z) denote the saddle point value and the dual function value, respectively, of the auxiliary problem min x max y f (x, y; z) for any fixed z and f defined in (2), i.e., Ψ(y; z) ≜ minx∈R d 1f (x, y; z) and P (z) ≜ minEQUATIONNext, we introduce a natural assumption, commonly made in the literature [66, 65] . Without this assumption, there are pathological cases where primal function Φ(x) may be unbounded leading to divergence of gradient-based methods; an example would be f (x, y) = -x 2 -y 2 in dimension one.Assumption 4. Consider the primal function Φ : R d1 → R, i.e., Φ(x) = max y∈R d 2 f (x, y). There existsx * ∈ R d1 such that Φ * ≜ Φ(x * ) = min x∈R d 1 Φ(x).Under Assumption 4, it immediately follows that V t ≥ Φ * for all t ∈ N -since P (z) -Ψ(y, z) ≥ 0, f (x, y; z) -Ψ(y; z) ≥ 0 and P (z) ≥ Φ * for all x, y, z. We will next study the change V t -V t+1 in the Lyapunov function and show that an approximate descent property holds. First, we need two key lemmas that characterize the evolution of f (x t , y t ; z t ) and Ψ(y t ; z t ) over the iterations. Lemma 5. Suppose Assumptions 1, 2, 3 and 4 hold. Consider sm-AGDA given in Alg. 1 with τ 1 ∈ (0, 1 p+ℓ ] and β ∈ (0, 1]. For any t ∈ N, we have:f (xt+1, yt+1; zt+1) -f (xt, yt; zt) ≤ - τ1 2 ∥∇x f (xt, yt; zt)∥ 2 + τ2 1 + ℓ 2 τ2 ∥∇yf (xt+1, yt)∥ 2 + τ1((p + ℓ)τ1 -1)⟨∆ x t , ∇x f (xt, yt; zt)⟩ + p + ℓ 2 τ 2 1 ∥∆ x t ∥ 2 + τ2(1 + ℓτ2)⟨∇yf (xt+1, yt), ∆ y t ⟩ - p 2β ∥zt -zt+1∥ 2 + ℓτ 2 2 2 ∥∆ y t ∥ 2 .Proof. The proof is provided in Appendix B.1.From Assumption 1, when p > ℓ, the auxilliary function f (•, y; z) is (p -ℓ)-strongly convex for any fixed y, z; hence, there is a unique minimizer for every y, z fixed, denoted byEQUATIONi.e., Ψ(y, z) = f (x * (y, z), y; z). In the rest of the paper, we will take p > ℓ and exploit this property.The following lemma characterizes the change in the dual function Ψ. Lemma 6. Suppose Assumptions 1, 2, 3 and 4 hold. Consider the sm-AGDA iterate sequence {(x t , y t , z t )} t∈N for p > ℓ. For any t ∈ N, it holds thatΨ(y t+1 ; z t+1 ) -Ψ(y t ; z t ) ≥τ 2 ⟨∇ y f (x * (y t , z t ), y t ), ∇ y f (x t+1 , y t )⟩ + τ 2 ⟨∇ y f (x * (y t , z t ), y t ), ∆ y t ⟩ - L Ψ 2 τ 2 2 ∥∇ y f (x t+1 , y t )∥ 2 + 2⟨∇ y f (x t+1 , y t ), ∆ y t ⟩ + ∥∆ y t ∥ 2 + p 2 ⟨z t+1 -z t , z t+1 + z t -2x * (y t+1 , z t+1 ) ,where L Ψ ≜ ℓ 1 + p+ℓ p-ℓ and the map x * (•, •) is defined by (11) . Proof. The proof is provided in Appendix B.2.The next result provides an approximate descent property on the Lyapunov function. Its proof builds on Lemmas 5 and 6 and a descent property on the function P (given in Lemma 15 of the Appendix); and leverages smoothness properties of the functions f and Ψ and the map (y, z) → x * (y, z) as well as the strong convexity of f with respect to x. Theorem 7. Suppose Assumptions 1, 2, 3 and 4 hold. Consider the sm-AGDA algorithm with parameters p > ℓ, β ∈ (0, 1], τ 1 ∈ (0, 1 p+ℓ ] and τ 2 > 0 chosen such thatEQUATIONfor some constants {c i } 8 i=1 ⊂ R that are explicitly given in Appendix C, which may depend on ν, as well as the problem and sm-AGDA parameters that can be chosen such that c 1 , c 2 , c 3 > 0.Proof. The proof is given in Appendix C.With some specific choice of parameters in sm-AGDA, we can obtain simplifications to the coefficients {c i } 8 i=1 from Theorem 7 (explicitly given in Appendix C). As such, this yields the following corollary.Corollary 8. Under the premise of Theorem 7, let p = 2ℓ, τ 1 ∈ (0, 1 3ℓ ], τ 2 = τ1 48 , β = αµτ 2 for α ∈ (0, 1 406 ]. Then, Ãt+1-Ãt τ1 ≤ -Bt + Ct+1 + Dt+1 for all t ∈ N, where ν = 12 τ1ℓ andÃt ≜ τ1Vt, Bt ≜ τ1 5 ∥∇x f (xt, yt; zt)∥ 2 + τ2 8 ∥∇yf (x * (yt, zt), yt)∥ 2 + βp 8 ∥xt -zt∥ 2 , Ct+1 ≜ 192βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 + 4ℓ ν + 4c0ℓ 2 + 2c ′ 0 β 2 τ 2 1 + (p + ℓ)τ1 -1 τ1 ⟨∇x f (xt, yt; zt), ∆ x t ⟩ +τ2⟨(1 + ℓτ2 + 2LΨτ2) ∇yf (xt, yt) -2∇yf (x * (yt, zt), yt), ∆ y t ⟩, Dt+1 ≜ 2ℓτ 2 1 ∥∆ x t ∥ 2 + 8ℓτ 2 2 ∥∆ y t ∥ 2 .Proof. The proof is given in Appendix D.Next, we provide a concentration inequality which will be key to obtain our high-probability bounds. Theorem 9. Let {F t } t∈N be a filtration on (Ω, F, P). Let A t , B t , C t , D t be four stochastic processes adapted to the filtration such that there exist σ C , σ D > 0 and τ 1 > 0 such that for all t ∈ N: (i)B t ≥ 0, (ii) E[e λCt+1 | F t ] ≤ e λ 2 σ 2 C Bt for all λ > 0, (iii) E[e λDt+1 | F t ] ≤ e λσ 2 D for all λ ∈ 0, 1 σ 2 D and (iv) At+1-At τ1 ≤ -B t + C t+1 + D t+1 .Then, for any q ∈ (0, 1], we haveP τ1 2 T -1 t=0 Bt ≤ (A0 -AT ) + τ1σ 2 D T + 2τ1 max{2σ 2 C , σ 2 D } log 1 q ≥ 1 -q.Proof. The proof is provided in Appendix E.Remark 10. While the above concentration inequality seems tailored to the analysis of sm-AGDA, it can also aid in deriving high probability bounds for many other first-order methods for nonconvex minimax problems that outputs a randomized iterate; indeed, the majority of existing Lyapunov arguments in the nonconvex setting are built upon constructing telescoping sums in line with Theorem 9, e.g., stochastic alternating GDA [66] for NCPL minimax problems and optimistic GDA [45] for strongly convex-strongly concave problems.We next present our main result which provides a high-probability bound on the sm-AGDA iterates.The main idea of the proof is to apply Theorem 9 to the processes introduced in Corollary 8. Theorem 11. In the premise of Corollary 8, sm-AGDA iterates (x t , y t ) for τ 1 ≤ 1 3ℓ satisfyP 1 T T -1 t=0 ∥∇xf (xt, yt)∥ 2 + κ∥∇yf (xt, yt)∥ 2 ≤ Qq,T , ≥ 1 -q, ∀ T ∈ N, ∀ q ∈ (0, 1],for someQ q,T = O κ(∆0+b0) τ1T + κ(δ 2 x + δ 2 y ) τ 1 ℓ + 1 T log 1 q explicitly stated in Appendix F, where ∆ 0 ≜ Φ(z 0 ) -Φ * , b 0 ≜ 2 sup x,y { f (x 0 , y; z 0 ) -f (x, y 0 ; z 0 )}.Proof Sketch. Let the stochastic processes A t , B t , C t , D t in Theorem 9 be chosen asA t = Ãt , B t = Bt , C t = Ct , D t = Dtwhere Ãt , Bt , Ct , Dt are defined in Corollary 8 and τ 1 > 0 be the primal stepsize in sm-AGDA; according to Corollary 8, we haveAt+1-At τ1 ≤ -B t + C t+1 + D t+1 for t ∈ N. Since ∆ xt and ∆ y t admit sub-Gaussian tails, it can be shown that the conditions of Theorem 9 are satisfied for some appropriate constants σ 2 C and σ 2 D . Therefore, Theorem 9 implies a tail bound on T -1 t=0 Bt . Using the relation between f and f , one can also show that ∥∇x f (x t , y t )∥ 2 + κ∥∇ y f (x t , y t )∥ 2 = O( Bt ), for all t ∈ N. This last inequality allows to translate the tail bound forT -1 t=0 Bt to a tail bound for T -1 t=0 ∥∇ x f (x t , y t )∥ 2 + κ∥∇ y f (x t , y t )∥ 2 .The details of the proof is provided in Appendix F of the supplementary material.Remark 12. Suppose sm-AGDA, given in Alg. 1, is run for T iterations, and it outputs a randomly selected iterate (x U , y U ), where the random iteration index U is chosen uniformly at random from the set {0, 1, . . . , T -1}, i.e., P(U = t) = 1/T for t = 0, 1, . . . , T -1. Theorem 11 implies thatP ∥∇xf (xU , yU )∥ 2 + κ∥∇yf (xU , yU )∥ 2 ≤ Qq,T ≥ 1 -q.Furthermore, in comparison with existing complexity bounds in expectation for sm-AGDA [66] , our quantile bound requires only an overhead of order O(ε -2 log(1/q)). Unless q is very small, this is typically negligible in comparison to the O(ε -4 ) already present in rates in expectation.Remark 13. In contrast to high-probability bounds derived from standard Markov-type arguments, our approach achieves significantly better scaling with respect to both q and ϵ. Specifically, consider an oracle that can generate a sample (x, ŷ) with E[∥∇f (x, ŷ)∥] ≤ ϵ after G(ϵ) iterations/stochastic samples. In particular, [66] shows that one can takeG(ϵ) = O ℓκ 2 δ 2 ϵ 4 + κℓ ϵ 2for the sm-AGDA algorithm assuming the variance of the stochastic gradient is bounded by δ 2 . A naive high-probability bound could be constructed by ensuring E[∥∇f (x, ŷ)∥] ≤ q • ϵ and applying Markov's inequality to yield an ϵ-stationary point with probability at least 1 -q. However, this approach results in a complexity bound of G(qϵ) = O ℓκ 2 δ 2 q4 ϵ 4 + κℓ q2 ϵ 2 , leading to a significantly worse dependence on q than ours. Alternatively, following the rationale in [19, 62] , to generate a high-probability bound, one can run the sm-AGDA algorithm m = Ω(log(1/q)) times in parallel; where in each run we generate an ε/2-solution and among the solutions, we select the one with the smallest estimated gradient norm. This would require mG(ϵ) = O log(1/q) ℓκ 2 δ 2 ϵ 4 + log(1/q) κℓ ϵ 2iterations/stochastic samples.In this approach, the logarithmic term log 1 q multiplies the high-order O( 1 ε 4 ) term, whereas in our approach it only affects the second-order O( 1 ε 2 ) term. Therefore, our results scale better with respect to q and ε. In addition, such a (multiple) parallel run approach, is often impractical in streaming/online settings, where data arrives sequentially, and real-time processing is essential. Corollary 14. Under the premise of Theorem 11, consider running the sm-AGDA method for some fixed number of iterations T ∈ N with parameters chosen asτ 1 = min 1 3ℓ , 48 √ ∆0+b0 √ T ℓδ 2and τ 2 = τ 1 /48 where δ 2 ≜ δ 2 x + δ 2 y . Then, for any q ∈ (0, 1), sm-AGDA can compute an (ε, ε/ √ κ) stationarity point with probability at least 1 -q when the number of iterations T is fixed toT ε,q = O (∆0+b0)ℓκ ε 2 + δ 2 log( 1 q )κ ε 2 + δ 2 (∆0+b0)ℓκ 2 ε 4which requires T ε,q stochastic gradient calls.Proof. This is a direct consequence of Theorem 11, a proof is provided in Appendix G.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Although we provide the first high-probability bounds for nonconvex/PL minimax problems to the best of our knowledge, there may still be some room to improve the condition number κ dependency based on the existing lower complexity bounds [38, 71] in expectation, unless the lower complexity bounds are loose. Also, we acknowledged that for the distributionally robust optimization experiment our assumptions do not all hold (which is a limitation); but that our results are still predictive of the practical performance. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] All assumptions are clearly stated or referenced in the statement of any theorem, we provide a sketch of the proof of our main theorem. 
numerical illustrations: 
 In this section, we illustrate the performance of sm-AGDA. We consider an NCPL problem with synthetic data, as well as a nonconvex DRO problem using real datasets. For synthetic experiments, we used an ASUS Laptop model Q540VJ with 13th Generation Intel Core i9-13900H using 16GB RAM and 1TB SSD hard drive. For the DRO experiments, we used a high-performance computing cluster with automatic GPU selection (NVIDIA RTX 3050, RTX 3090, A100, or Tesla P100) based on GPU availability, ensuring optimal use of computational resources. Synthetic experiments on an NCPL game. We consider the following NCPL problem:EQUATIONwhich can be interpreted as a game between two players [48, 35] where m 1 , m 2 > 0 are constants and the symmetric matrix K is set randomly, similar to the standard bilinear game setting considered in [35] . More specifically, we set K = 10 K/∥ K∥, K = (M + M ⊤ )/2 where M is a d × d matrix with entries being i.i.d centered Gaussian having variance σ 2 . This problem is nonconvex in x (without satisfying the PL condition in x). Though the exact gradient is known, we consider a stochastic gradient oracle, which returns noisy gradients similar to the setting of [35, 11, 16, 2] , i.e., for eachiteration t ∈ {0, ..., T -1}, G x (x t , y t ; ξ x t+1 ) = ∇ x f (x t , y t ) + ξ x t+1 and G y (x t+1 , y t , ξ y t+1 ) = ∇ y f (x t+1 , y t ) + ξ y t+1 , with (ξ x t+1 ) t≥0 iid ∼ N (0, δ 2 I d1 ) and (ξ y t+1 ) t≥0 iid ∼ N (0, δ 2 I d2) where I d is the d × d identity matrix and δ 2 is some constant variance. This setting satisfies all our assumptions, and our high-probability results (Theorem 11 and Coro. 14) are applicable. In this experiment, we fixd 1 = d 2 = 30, and m 1 = m 2 = δ 2 = σ 2 = 1. The solution to this problem is (x * , y * ) = (0, 0).Experimental results. The parameters of the problem are explicitly available as µ = 2m 2 , and ℓ = max{12m 1 , 8m 2 , ∥K∥}. To illustrate Theorem 11, we set β = τ2µ 1600 , τ 2 = τ1 48 , p = 2ℓ and we considered two cases: τ 1 = 1 3ℓ (long step) and τ 1 = 1 12ℓ (short step) to explore the behavior of sm-AGDA for different stepsizes. We generated N = 25 sample paths for T = 10, 000 iterations, and on the left panel of Fig. 1 , for each iteration t, we report the average of M κ (t) ≜ ∥∇ x f (x t , y t )∥ 2 + κ∥∇ y f (x t , y t )∥ 2 over N = 25 realizations corresponding to different sample paths, and the shaded region depicts the range statistic, i.e., for every fixed iteration t, we shade the vertical line between the maximum and minimum values of M κ (t) for the 25 paths. On the right panel of Fig. 1 , we also report the squared distance, I(t) ≜ ∥x t -x * ∥ 2 + ∥y t -y * ∥ 2 , in a similar manner. We observe that the range statistic for M κ (t) diminishes to a value inversely proportional to T as t → T ; this is inline with our theoretical results in Theorem 11. The existence of sinusoidal terms in the minimax objective is a source for oscillatory behavior in these figures. As t → T , both M κ (t) and I(t) exhibit oscillations, of which amplitude are smaller for the small step size compared to the large step-size -at the expense of a slower convergence; the iterate paths are not as oscillatory. For T = 10, 000 and τ 1 = 1 3ℓ fixed, we next consider the path averagesX T ≜ 1 T T -1 t=0 M κ (t). Indeed, based on 1000 sample paths, each for T = 10, 000 iterations, we compare the empirical quantiles of X T with the theoretical upper bound Q q,T on its quantiles (implied by Theorem 11). Figure 2 shows the cumulative distribution function (CDF) of the empirical distribution alongside the theoretical explicit upper bound Q q,T for the stationarity measure ∥∇ x f (x U , y U ) + κ∇ y f (x U , y U )∥ with U uniform over {1, . . . , T }. The details of the empirical quantile estimation are provided Appendix I due to space considerations. We observe that the empirical CDF has a sigmoid-like shape, while the theoretical quantiles that lie above display a concave form. This difference may arise because the theoretical quantile bounds Q q,T are designed to capture the worst-case behavior across the class of NCPL problems, whereas this specific NCPL example may not represent the worst-case scenario. Distributionally Robust nonconvex Logistic Regression. We consider the DRO problem minEQUATIONwhere ℓ j (x; a j , b j ) = log 1 + exp -b j a ⊤ j x denotes the logistic loss tied to an input-output pair (a j , b j ) ∈ R d1 × {-1, 1}, and r(x) = λ 1 d1 i=1 ωx 2 i 1+ωx 2 i a primal regularization for the learning modelx ∈ R d1 . We allow the distribution y ∈ Y ≜ {y ∈ R d2 : y ≥ 0, 1 ⊤ y = 1} to deviate from the uniform distribution u ≜ 1 d2 1 where 1 denotes the vector of ones, and we penalize the distance between y and u through the regularization map g : y → λ2d2 2 ∥y -u∥ 2 . We set the regularization parameters as ω = 10, λ 1 = 10e -4 , and λ 2 = 1. Since r is nonconvex with a Lipschitz gradient and g is strongly convex, this is an NCSC problem. Datasets, Algorithms and Hyperparameters. We consider three standard datasets for this problem, which are summarized as follows: The sido0 dataset [50] has d 1 = 4932 and d 2 = 12678. The gisette dataset [26] has d 1 = 5000 and d 2 = 6000. Finally, the a9a dataset [13] has d 1 = 123 and d 2 = 32561. We compare the performances of sm-AGDA against two other baselines that achieve state-of-the-art performance in expectation for these datasets [72] . Specifically, we evaluate SAPD+, which is a two-loop method where the subproblems are solved by the SAPD algorithm [73] , and SMDAVR, a variance reduced extension of SMDA algorithm [31] . Since ( 14) is constrained, we augment sm-AGDA with a projection step in the update of the y variable onto the d 2 -dimensional simplex and adopt the analogous stationarity metric ∥∇ x f (x t , y t )∥ 2 + ∥P Y ∇ y f (x t , y t )∥ 2 for constrained problems where P Y is a projection to the dual domain Y . For all datasets, the primal stepsize τ 1 of sm-AGDA is tuned via a grid-search over {10 -k , 1 ≤ k ≤ 4}. The dual stepsize τ 2 is set as τ 2 = τ1 48 . Similarly, β is estimated through a grid-search over {10 -k , 3 ≤ k ≤ 5}. The parameter p is also tuned similarly on a grid, our code is provided as a supplementary document for the details. For other methods, our hyperparameters are tuned in accordance with [72] . Experimental results. In Figure 2 , we plot histograms of our stationarity metric, across 200 runs in a logarithmic scale. We report the stationarity measure both in early phase of the training (i.e. t = 20 epochs), and in later phases (i.e. t = 550 epochs for gisette and t = 250 epochs for a9a and sido0). Our theoretical results are presented for unconstrained problems in the dual, therefore they are not directly applicable to the DRO problem where the dual domain is constrained. That being said, we observe that they are still predictive of performance in the DRO setting. More specifically, Figure 2 is supportive of our high-probability complexity bounds for sm-AGDA, in the sense that the distribution of the stationarity metric for sm-AGDA tends to concentrate. Notably, it outperforms the concentration behaviour of the other baselines. Furthermore, we observe that histograms for all baselines hardly evolve after 20 epochs. This is consistent with previous experiments carried on these datasets [72] where performance was measured in terms of the decay of the average loss and its standard deviation. As such, we conclude that sm-AGDA performs better both in the early phase and the later stage. In our experience, we observed sm-AGDA could accomodate larger stepsizes compared to the other algorithms, which may have contributed to its good performance.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] We uploaded our code as a supplementary material, and explained in detail how our experiments are performed. All the datasets we use are well-known benchmark datasets and we provided the adequate references to them. 
conclusion: 
 Existing high-probability bounds only apply to convex/concave minimax problems or non-monotone variational inequality problems under restrictive assumptions to our knowledge. We close this gap by providing the first high-probability complexity guarantees for nonconvex/PL minimax problems satisfying the PL-condition in the dual variable for the sm-AGDA method. We also provide numerical results for an NCPL example and for nonconvex distributionally robust logistic regression.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] We explain the experimental setup in detail and provide the code, the datasets are well-known benchmark sets that are publicly available and we provided the adequate references. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Our numerical experiments section has all the details. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] In the experiments, we compare the histogram of the solutions found by multiple algorithms. This has more resolution than standard approaches that has the average performance (as an average over the algorithm runs) and the standard deviation over the runs; because one can visualize the behavior (histogram) of all runs. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? 
 
 Appendix: The organization of the Appendix is as follows:• In Section A, we summarize the key notations that are used throughout the main paper and the Appendix.• In Section B, we provide the proofs of Lemmas from Section 3 that were used for deriving the approximate Lyapunov descent property.• In Section C, we present the proof of Theorem 7 which provides an approximate descent property in terms of the Lyapunov function for the sm-AGDA iterates.• In Section D, we provide the proof of Corollary 8, which studies particular choice of parameters within Theorem 7.• In Section E we present a proof of Theorem 9 which provides a concentration inequality.• In Section F, we provide the proof of Theorem 11 which yields high-probability results for the sm-AGDA algorithm.• In Section G, we provide a proof of Corollary 14 that provides a high-probability (iteration) complexity bound for the sm-AGDA iterates.• In Section H, we present supplementary lemmas that were used to derive the results.• In Section I, we provide further details about numerical experiments.The key notations that will be used throughout the Appendix is as follows:• f (x, y; z) = f (x, y) + p 2 ∥x -z∥ 2 denotes the auxiliary problem. • Ψ(y; z) = min x f (x, y; z) is the dual function of the auxiliary problem.• Φ(x; z) = max y f (x, y; z) is the primal function of the auxiliary problem.• P (z) = min x max y f (x, y; z) is the optimal value of the primal problem min x Φ(x; z)• x * (y, z) = argmin x f (x, y; z) for given y, z in the auxiliary function.• x * (z) = argmin x Φ(x; z) is the unique optimal solution to the auxiliary primal problem.• Y * (z) = argmax y Ψ(y; z) is the set of optimal solutions to the auxiliary dual problem.• y + (z) = y + τ 2 ∇ y f (x * (y, z), y) denotes an update in y in the direction of the gradient of the dual function, i.e., along the direction ∇Ψ(y; z) = ∇ y f (x * (y, z), y).• Ĝx (x, y, ξ; z) ≜ G x (x, y, ξ) + p(x -z)• ∆ x t = G x (x t , y t , ξ x t+1 ) -∇ x f (x t , y t) and ∆ y t = G y (x t+1 , y t , ξ y t+1 ) -∇ y f (x t+1 , y t ) denote the gradient error, i.e., the difference between the stochastic estimates of the partial gradients and the exact partial gradients.B.1 Proof of Lemma 5 Lemma 5. Suppose Assumptions 1, 2 and 3 hold. Consider sm-AGDA, stated in Algorithm 1, with τ 1 ∈ (0, 1 p+ℓ ] and β ∈ (0, 1]. For any t ∈ N, we have:f (xt+1, yt+1; zt+1) -f (xt, yt; zt) ≤ - τ1 2 ∥∇x f (xt, yt; zt)∥ 2 + τ2 1 + ℓ 2 τ2 ∥∇yf (xt+1, yt)∥ 2 - p 2β ∥zt -zt+1∥ 2 + τ1((p + ℓ)τ1 -1)⟨∆ x t , ∇x f (xt, yt; zt)⟩ + τ2(1 + ℓτ2)⟨∆ y t , ∇yf (xt+1, yt)⟩ + p + ℓ 2 τ 2 1 ∥∆ x t ∥ 2 + ℓτ 2 2 2 ∥∆ y t ∥ 2 .Proof. Since, f (•, y; z) is (p + ℓ)-smooth, we havef (x t+1 , y t ; z t ) -f (x t , y t ; z t ) ≤ ⟨x t+1 -x t , ∇ x f (x t , y t ; z t )⟩ + p + ℓ 2 ∥x t+1 -x t ∥ 2 = -τ 1 ⟨ Ĝx (x t , y t ; z t ), ∇ x f (x t , y t ; z t )⟩ + p + ℓ 2 τ 2 1 ∥ Ĝx (x t , y t ; z t )∥ 2 . = ( p + ℓ 2 τ 2 1 -τ 1 )∥∇ x f (x t , y t ; z t )∥ 2 -(τ 1 + (p + ℓ)τ 2 1 )⟨∆ x t , ∇ x f (x t , y t ; z t )⟩ + p + ℓ 2 ∥∆ x t ∥ 2 ,where last equality follows from Ĝx (x t , y t ; z t ) = ∇ x f (x t , y t ; z t ) + ∆ x t . Hence, for τ 1 ≤ 1 p+ℓ , we have f (x t+1 , y t ; z t ) -f (x t , y t ; z t )EQUATIONSimilarly, we observe that for all, ∇ y f (x, y; z) = ∇ y f (x, y), for all x, y, z, which together with the smoothness of f (x, •) implies f (x t+1 , y t+1 ; z t ) -f (x t+1 , y t ; z t )EQUATIONwhere we used again the identity G y (x t+1 , y t , ξ y t+1 ) = ∇ y f (x t+1 , y t ; z t ) + ∆ y t . Finally, we observe from the sm-AGDA update rule z t+1 -EQUATIONwhere we used 0 < β ≤ 1. Therefore, summing up (15), ( 16), ( 17) yields the claim.Lemma 6. Suppose Assumptions 1, 2 and 3 hold, and p ≥ ℓ. Then, for any t ∈ N,Ψ(y t+1 ; z t+1 ) -Ψ(y t ; z t ) ≥ τ 2 ⟨∇ y f (x * (y t , z t ), y t ), ∇ y f (x t+1 , y t )⟩ + τ 2 ⟨∇ y f (x * (y t , z t ), y t ), ∆ y t ⟩ - L Ψ 2 τ 2 2 ∥∇ y f (x t+1 , y t )∥ 2 + 2⟨∇ y f (x t+1 , y t ), ∆ y t ⟩ + ∥∆ y t ∥ 2 + p 2 ⟨z t+1 -z t , z t+1 + z t -2x * (y t+1 , z t+1 ) ,where L Ψ ≜ ℓ 1 + p+ℓ p-ℓ and the map x * (•, •) is defined in (11) .Proof. By Lemma 19, Ψ is L Ψ -smooth in y for any given z ∈ R d1 . Then, using ∇ y Ψ(y t ; z t ) = ∇ y f (x * (y t , z t ), y t ), we obtainEQUATION) Furthermore, by definition of Ψ, we also haveEQUATIONSumming ( 18) and ( 19), we conclude.Before we move on to the proof of Theorem 7, we first provide a result from [70, 64] that quantifies the change in the function P over the iterations. We also provide its proof for the sake of completeness. Lemma 15 (Lemma B.7 in [70] ). Suppose Assumptions 1, 2 and 3 hold. Consider the sm-AGDA iterate sequence (x t , y t , z t ) t∈N for p > ℓ, and let Y * (z) ≜ argmax y Ψ(y; z) denote the set of maximizers of Ψ(•, z) for given z. For any t ∈ N and y * (z t+1 ) ∈ Y * (z t+1 ), it holds thatP (z t+1 ) -P (z t ) ≤ p 2 ⟨z t+1 -z t , z t+1 +z t -2x * (y * (z t+1 ), z t )⟩.Proof. Let y * (z t+1 ) ∈ Y * (z t+1 ) and y * (z t ) ∈ Y * (z t ) be two arbitrary maximizers. We haveP (z t+1 ) -P (z t ) = min x max y f (x, y; z t+1 ) -min x max y f (x, y; z t ) = max y min x f (x, y; z t+1 ) -max y min x f (x, y; z t ) = Ψ(y * (z t+1 ); z t+1 ) -Ψ(y * (z t ); z t ) ≤ Ψ(y * (z t+1 ); z t+1 ) -Ψ(y * (z t+1 ); z t ) = f (x * (y * (z t+1 ), z t+1 ), y * (z t+1 ); z t+1 ) -f (x * (y * (z t+1 ); z t ), y * (z t+1 ); z t ) ≤ f (x * (y * (z t+1 ), z t ), y * (z t+1 ); z t+1 ) -f (x * (y * (z t+1 ); z t ), y * (z t+1 ); z t ) = p 2 (z t+1 -z t ) ⊤ [z t+1 +z t -2x * (y * (z t+1 ), z t )].The first and the third equality above hold by the definition of P (z) and Ψ(y; z) functions; on the other hand, for the second equality, one needs strong duality to hold. This interchange is valid and can be justified by the simple fact that f is strongly convex in x (therefore, it satisfies the PL condition in x), and it also satisfies the PL condition in y according to our assumption 2. It has been established in [65, Lemma 2 .1] that the double-sided PL property allows one for the min-max switch.Equipped with this lemma, the stage is set to prove Theorem 7 from Section 3. We first restate an extended version of this theorem, where the constants {c i } 8 i=1 are provided explicitly. Theorem 7. Suppose Assumptions 1, 2, 3 and 4 hold. Consider the sm-AGDA algorithm with parameters p > ℓ, β ∈ (0, 1], τ 1 ∈ (0, 1 p+ℓ ] and τ 2 > 0 chosen such thatc 0 ≜ -τ 2 2 ℓν + τ 2 1 - ℓ 2 τ 2 -L Ψ τ 2 ≥ 0, c ′ 0 ≜ p 3β - 2p 2 p -ℓ + 48β p 3 (p -ℓ) 2 ≥ 0for some constant ν > 0, where L Ψ = ℓ 1 + p+ℓ p-ℓ . Then,EQUATION)where the coefficients c 1 to c 8 have the following forms:c1 = τ1 2 -2 1 (p -ℓ) 2 + τ 2 1 c0ℓ 2 + ℓ ν + 48βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 -c ′ 0 β 2 + ℓ 6 (1 + ℓτ2 + 2LΨτ2) τ 2 1 , c2 = c0 2 - 24βp (p -ℓ)µ 1 + τ2 2pℓ p -ℓ 2 , c3 = c ′ 0 β 2 /2, c4 = -192βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 + 4ℓ ν + 4c0ℓ 2 + 2c ′ 0 β 2 τ 2 1 -(p + ℓ)τ1 -1 τ1, c5 = -τ2(1 + ℓτ2 + 2LΨτ2), c6 = 2τ2, c7 = -96βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 + 2ℓ ν + p + ℓ 2 + 2c0ℓ 2 + ℓ 6 (1 + ℓτ2 + 2LΨτ2) + c ′ 0 β 2 τ 2 1 , c8 = -48βp p + ℓ p -ℓ 2 + ℓ 2 + LΨ+3ℓ(1 + ℓτ2 + 2LΨτ2) τ 2 2 .Furthermore, the sm-AGDA parameters can be chosen such that c 1 , c 2 , c 3 > 0.Proof. Combining the inequalities in Lemmas 5, 6 and 15 gives us a lower bound of the form:EQUATIONfor any y * (z t+1 ) ∈ Y * (z t+1 ) appearing in A 3 , whereA 1 = τ 1 2 ∥∇ x f (x t , y t ; z t )∥ 2 + τ 2 1 - ℓ 2 τ 2 -L Ψ τ 2 ∥∇ y f (x t+1 , y t )∥ 2 + p 2β ∥z t -z t+1 ∥ 2 , A 2 = 2τ 2 ⟨∇ y f (x * (y t , z t ), y t ) -∇ y f (x t+1 , y t ), ∇ y f (x t+1 , y t )⟩, A 3 = 2p⟨z t+1 -z t , x * (y * (z t+1 ), z t ) -x * (y t+1 , z t+1 )⟩ A 4 = -τ 1 ((p + ℓ)τ 1 -1)⟨∇ x f (x t , y t ; z t ), ∆ x t ⟩, A 5 = ⟨ 2τ 2 ∇ y f (x * (y t , z t ), y t ) -τ 2 (1 + ℓτ 2 + 2L Ψ τ 2 )∇ y f (x t+1 , y t ), ∆ y t ⟩, A 6 = - p + ℓ 2 τ 2 1 ∥∆ x t ∥ 2 - ℓτ 2 2 2 ∥∆ y t ∥ 2 -L Ψ τ 2 2 ∥∆ y t ∥ 2 .Next, we provide lower bounds for several terms in the above inequality, including A 2 , A 3 , A 5 , ∥∇ y f (x t+1 , y t )∥ 2 and ∥z t+1 -z t ∥ 2 . At the end, using these bounds within ( 21), we will be able to establish a descent property for {V t }, which will allow to apply our concentration result (Theorem 9) for deriving the desired high probability bounds.Lower bound for A 2 . Using Cauchy-Schwarz inequality and ℓ-smoothness of f , we haveA 2 ≥ -2τ 2 ∥∇ y f (x * (y t , z t ), y t ) -∇ y f (x t+1 , y t )∥∥∇ y f (x t+1 , y t )∥ ≥ -2τ 2 ℓ∥x t+1 -x * (y t , z t )∥∥∇ y f (x t+1 , y t )∥ ≥ -τ 2 2 ℓν∥∇ y f (x t+1 , y t )∥ 2 -ℓν -1 ∥x t+1 -x * (y t , z t )∥ 2 , ∀ν > 0,where last line follows from Young's inequality. Thus, by Lemma 20, we obtain for any ν > 0EQUATION)Lower bound for A 3 . By Cauchy-Schwarz inequality and Lemma 21,A 3 = 2p⟨z t+1 -z t , x * (y * (z t+1 ), z t ) -x * (y * (z t+1 ), z t+1 )⟩ + 2p⟨z t+1 -z t , x * (y * (z t+1 ), z t+1 ) -x * (y t+1 , z t+1 )⟩ ≥ -2p∥z t+1 -z t ∥∥x * (y * (z t+1 ), z t ) -x * (y * (z t+1 ), z t+1 )∥ + 2p⟨z t+1 -z t , x * (y * (z t+1 ), z t+1 ) -x * (y t+1 , z t+1 )⟩ ≥ - 2p 2 p -ℓ ∥z t+1 -z t ∥ 2 + 2p⟨z t+1 -z t , x * (y * (z t+1 ), z t+1 ) -x * (y t+1 , z t+1 )⟩.Hence, using Young's inequality, for all β > 0, we obtainEQUATION)We now lower bound the second term on the right-hand side of (23) . First, note that we have x * (y * (z t+1 ), z t+1 ) = x * (z t+1 ), which follows from the fact that min x max y f (x, y; z) = max y min x f (x, y; z) for all z since f is strongly convex in x and satisfies the PL condition in Assumption 2. Hence, using the inequalityN i=1 w i 2 ≤ N N i=1 ∥w i ∥ 2, which holds for any{w i } ∈ R d1 and N ≥ 1, we get ∥x * (y * (z t+1 ), z t+1 ) -x * (y t+1 , z t+1 )∥ 2 ≤ 4∥x * (z t+1 ) -x * (z t )∥ 2 + 4∥x * (z t ) -x * (y + t (z t ), z t )∥ 2 +4∥x * (y + t (z t ), z t ) -x * (y t+1 , z t )∥ 2 + 4∥x * (y t+1 , z t ) -x * (y t+1 , z t+1 )∥ 2. By Lemma 21 and Lemma 23, we observe that4∥x * (z t+1 ) -x * (z t )∥ 2 + 4∥x * (y t+1 , z t ) -x * (y t+1 , z t+1 )∥ 2 ≤ 8p 2 (p -ℓ) 2 ∥z t+1 -z t ∥ 2 .Using Lemma 24, we also have4∥x * (z t ) -x * (y + t (z t ), z t )∥ 2 ≤ 4 (p -ℓ)µ 1 + τ 2 2pℓ p -ℓ 2 ∥∇ y f (x * (y t , z t ), y t )∥ 2 .Finally, using Lemma 18, we get4∥x * (y + t (z t ), z t ) -x * (y t+1 , z t )∥ 2 ≤ 4 p + ℓ p -ℓ 2 ∥y + t (z t ) -y t+1 ∥ 2 = 4 p + ℓ p -ℓ 2 τ 2 2 ∥∇ y f (x * (y t , z t ), y t ) -G y (x t+1 , y t , ξ y t+1 )∥ 2 = 4 p + ℓ p -ℓ 2 τ 2 2 ∥∇ y f (x * (y t , z t ), y t ) -(∇ y f (x t+1 , y t ) + ∆ y t )∥ 2 , ≤ 4 p + ℓ p -ℓ 2 τ 2 2 2ℓ 2 ∥x * (y t , z t ) -x t+1 ∥ 2 + 2∥∆ y t ∥ 2 ,where the last inequality stems from the ℓ-smoothness of f . In view of Lemma 20, we may further upper bound the above quantity as follows:4∥x * (y + t (zt), zt) -x * (yt+1, zt)∥ 2 ≤ 16 p + ℓ p -ℓ 2 ℓ 2 τ 2 1 τ 2 2 1 τ 2 1 (p -ℓ) 2 + 1 ∥∇x f (xt, yt; zt)∥ 2 + 2⟨∇x f (xt, yt; zt), ∆ x t ⟩ + ∥∆ x t ∥ 2 + 8 p + ℓ p -ℓ 2 τ 2 2 ∥∆ y t ∥ 2 .Summing up the three intermediate inequalities we established above, we obtain∥x * (y * (z t+1 ), z t+1 ) -x * (y t+1 , z t+1 )∥ 2 ≤ 8p 2 (p -ℓ) 2 ∥z t+1 -z t ∥ 2 + 4 (p -ℓ)µ 1 + τ 2 ℓ + τ 2 ℓ(p + ℓ) p -ℓ 2 ∥∇ y f (x * (y t , z t ), y t )∥ 2 + 16 p + ℓ p -ℓ 2 ℓ 2 1 τ 2 1 (p -ℓ) 2 + 1 τ 2 1 τ 2 2 ∥∇ x f (x t , y t ; z t )∥ 2 + 32 p + ℓ p -ℓ 2 ℓ 2 τ 2 1 τ 2 2 ⟨∇ x f (x t , y t ; z t ), ∆ x t ⟩ + 16 p + ℓ p -ℓ 2 ℓ 2 τ 2 1 τ 2 2 ∥∆ x t ∥ 2 + 8 (p + ℓ) 2 (p -ℓ) 2 τ 2 2 ∥∆ y t ∥ 2 .In conclusion for A 3 , using (23) and the above inequality, we obtain after some rearrangementEQUATIONLower bound for A 5 . Below we first bound ⟨∇ y f (x t+1 , y t ), ∆ y t ⟩, i.e.,⟨∇yf (xt+1, yt), ∆ y t ⟩ = ⟨∇yf (xt, yt), ∆ y t ⟩ + ⟨∇yf (xt+1, yt) -∇yf (xt, yt), ∆ y t ⟩ ≤ ⟨∇yf (xt, yt), ∆ y t ⟩ + 1 12τ2ℓ ∥∇yf (xt+1, yt) -∇yf (xt, yt)∥ 2 + 3τ2ℓ∥∆ y t ∥ 2 ≤ ⟨∇yf (xt, yt), ∆ y t ⟩ + ℓτ 2 1 12τ2 ∥ Ĝx(xt, yt, ξ x t+1 ; zt)∥ 2 + 3τ2ℓ∥∆ y t ∥ 2 ≤ ⟨∇yf (xt, yt), ∆ y t ⟩ + ℓτ 2 1 6τ2 ∥∇x f (xt, yt; zt)∥ 2 + ℓτ 2 1 6τ2 ∥∆ x t ∥ 2 + 3τ2ℓ∥∆ y t ∥ 2 ,where the first inequality follows from Young's inequality, the second inequality follows from ∇yf being ℓ-smooth and the update rule xt+1 = xt -τ1 Ĝx(xt, yt, ξ x t+1 ; zt), and in the third inequality we use ∆ x t = Ĝx(xt, yt, ξ x t+1 ; zt) -∇x f (xt, yt; zt). Thus, since -τ2(1 + ℓτ2 + 2LΨτ2) < 0, for any τ2 > 0, we obtainEQUATIONLower bound for ∥∇yf (xt+1, yt)∥ 2 . Using Lemma 20 we can lower bound ∥∇yf (xt+1, yt)∥ 2 as follows:∥∇yf (xt+1, yt)∥ 2 ≥ 1 2 ∥∇yf (x * (yt, zt), yt)∥ 2 -∥∇yf (xt+1, yt) -∇yf (x * (yt, zt), yt)∥ 2 ≥ 1 2 ∥∇yf (x * (yt, zt), yt)∥ 2 -ℓ 2 ∥xt+1 -x * (yt, zt)∥ 2 ≥ 1 2 ∥∇yf (x * (yt, zt), yt)∥ 2 -2ℓ 2 τ 2 1 1 τ 2 1 (p -ℓ) 2 + 1 ∥∇x f (xt, yt; zt)∥ 2 + 2⟨∇x f (xt, yt; zt), ∆ x t ⟩ + ∥∆ x t ∥ 2 .We observe that ∥∇yf (xt+1, yt)∥ 2 appears in both A1 and the lower bound given in (22) for A2; hence, grouping the two terms together and using the definition of c0 ≥ 0, we getEQUATION)Lower bound for ∥zt+1 -zt∥ 2 . Since zt+1 = zt + β(xt+1 -zt) for some β > 0, we observe that:∥zt+1 -zt∥ 2 = β 2 ∥xt+1 -zt∥ 2 = β 2 ∥xt -zt -τ1 Ĝx(xt, yt, ξ x t+1 ; zt)∥ 2 ≥ β 2 1 2 ∥xt -zt∥ 2 -τ 2 1 ∥ Ĝx(xt, yt, ξ x t+1 ; zt)∥ 2 ,and since Ĝx(xt, yt, ξ x t+1 ; zt) = ∇x f (xt, yt; zt) + ∆ x t , we obtain∥zt -zt+1∥ 2 ≥ β 2 2 ∥xt -zt∥ 2 -β 2 τ 2 1 ∥∇x f (xt, yt; zt)∥ 2 -2β 2 τ 2 1 ⟨∇x f (xt, yt; zt), ∆ x t ⟩ -β 2 τ 2 1 ∥∆ x t ∥ 2 .Note that ∥zt+1 -zt∥ 2 appears in both A1 and the lower bound given in (24) for A3; hence, grouping the two terms together and using the definition of c ′ 0 ≥ 0 Using (27), we obtainp 2β - p 6β - 2p 2 p -ℓ -48β p 3 (p -ℓ) 2 ∥zt+1 -zt∥ 2 = c ′ 0 ∥zt+1 -zt∥ 2 ≥ -c ′ 0 β 2 τ 2 1 ∥∇x f (xt, yt; zt)∥ 2 + c ′ 0 β 2 2 ∥xt -zt∥ 2 -2c ′ 0 β 2 τ 2 1 ⟨∇x f (xt, yt; zt), ∆ x t ⟩ -c ′ 0 β 2 τ 2 1 ∥∆ x t ∥ 2 .We conclude by combining all these lower bounds, i.e., the claimed Lyapunov descent inequality follows directly from summing ( 21), ( 22), ( 24), ( 25), ( 26) and (27) . Finally, it follows after straightforward computations that there exist choice of sm-AGDA parameters which yield c1, c2, c3 > 0 while satisfying the conditions c0 ≥ 0 and c ′ 0 ≥ 0; in fact Corollary 8 provides such sm-AGDA parameters explicitly. This completes the proof.The lower bound provided in Theorem 7 resembles the descent property we require for our concentration result in Theorem 9. To allow for its proper application, we develop a stepsize policy inspired by [66] .Corollary 8. Under the premise of Theorem 7, consider the parameters p = 2ℓ,τ 1 ∈ (0, 1 3ℓ ], τ 2 = τ1 48 , β = αµτ 2 for any α ∈ (0, 1 406 ]. Then, Ãt+1-Ãt τ1 ≤ -Bt + Ct+1 + Dt+1 for all t ∈ N, where ν = 12 τ1ℓ and Ãt ≜ τ1Vt, Bt ≜ τ1 5 ∥∇x f (xt, yt; zt)∥ 2 + τ2 8 ∥∇yf (x * (yt, zt), yt)∥ 2 + βp 8 ∥xt -zt∥ 2 Ct+1 ≜ 192βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 + 4ℓ ν + 4c0ℓ 2 + 2c ′ 0 β 2 τ 2 1 + (p + ℓ)τ1 -1 τ1 ⟨∇x f (xt, yt; zt), ∆ x t ⟩ +τ2⟨(1 + ℓτ2 + 2LΨτ2) ∇yf (xt, yt) -2∇yf (x * (yt, zt), yt), ∆ y t ⟩, Dt+1 ≜ 2ℓτ 2 1 ∥∆ x t ∥ 2 + 8ℓτ 2 2 ∥∆ y t ∥ 2 .Proof. In view of Theorem 7, it suffices to prove that setting p = 2ℓ, τ 1 ∈ (0, 1 3ℓ ], τ 2 = τ1 48 , β = αµτ 2 for for some positive α ≤ 1 406 and ν = 12 τ1ℓ leads to both c 0 ≥ 0 and c ′ 0 ≥ 0; furthermore, we also need to show that this choice of parameters implies the following lower bounds:(i) c 1 ≥ τ1 5 , (ii) c 2 ≥ τ2 8 , (iii) c 3 ≥ pβ 8 , (iv) c 7 ≥ -2ℓτ 2 1 , (v) c 8 ≥ -8ℓτ 2 2 .First, we show that our parameter choice implies that c 0 , c ′ 0 ≥ 0. Noting that L Ψ = 4ℓ, using τ 1 ≤ 1 3ℓ , we may bound c 0 from above and below as follows:EQUATIONMoreover, since β = αµτ 2 and τ 2 ≤ 1 144ℓ , we get β ≤ α 144 using κ ≥ 1. Hence, for α ≤ 1 406 ,EQUATIONwhere the last inequality follows from α ≤EQUATION]. Next, we prove bounds on c 1 , c 2 , c 3 , c 7 , c 8 separately.Proof of part (i). Since p = 2ℓ, ν = 12 τ1ℓ and τ 1 ≤ 1 3ℓ , we first observe that 2ℓ νEQUATIONFurthermore, using τ 2 = τ1 48 , and β = αµτ 2 , we obtainEQUATIONwhere last line follows from the fact that µ/ℓ ≤ 1 andτ 3 2 ℓ 2 τ1 = τ 2 1 ℓ 2 48 3 ≤ 1 144 2 •48, in which we used τ 1 ≤ 1 3ℓ .Since τ 2 ≥ c 0 ≥ 0 and -2ℓ 2 1 (p-ℓ) 2 + τ 2 1 ≥ -20 9 , using τ 2 = τ1 48 , we obtainEQUATIONUsingEQUATION)UsingEQUATIONCombining equations ( 29), ( 30), (31) , (32) and (33) , we obtainEQUATIONfor α ≤ 1 406 < 2.4, which completes the proof of part (i).Proof of part (ii). Due to our parameter choice, we first note thatEQUATIONwhere last line follows from τ 2 ≤ 1 144ℓ and α ≤ 1 406 . Finally, (27) implies that c0 2 ≥ τ2 4 ; hence,c 2 ≥ 1 4 -1 8 τ 2 = τ2 8 .Proof of part (iii). We have shown that c ′ 0 ≥ p 4β ; hence, c 3 ≥ pβ 8 .Proof of part (iv). According to (27) , τ 2 ≥ c 0 ; hence, we deduce thatEQUATIONwhere the last inequality follows from τ 2 ≤ 1 144ℓ . Furthermore, we note thatEQUATIONwith the last inequality following also from µ ℓ ≤ 1 and τ 2 ≤ 1 144ℓ . We also note that- 2ℓ ν - p + ℓ 2 = - ℓτ 1 6 + 3 2 ℓ ≥ - 14 9 ℓ.Finally, since c ′ 0 ≤ p 3β according to (28) , we getEQUATIONwhere we used τ 2 ≤ 1 144ℓ . Thus, since α ∈ (0, 1), it follows from (36) , (37) , (38) and ( 32) that c 7 ≥ -ℓτ Proof of part (v). For c 8 , we may simply observe thatc 8 = -48βp p + ℓ p -ℓ 2 + ℓ 2 + L Ψ + 3ℓ(1 + ℓτ 2 + 2L Ψ τ 2 ) τ 2 2 = -864αµτ 2 + 1 2 + 4 + 3 (1 + ℓτ 2 + 2L ψ τ 2 ) ℓτ 2 2 ≥ -6α µ ℓ + 1 2 + 4 + 3 1 + 1 144 + 8 144 ℓτ 2 2 ≥ -8ℓτ 2 2 ,where we used µ/ℓ ≤ 1, L Ψ = 4ℓ, τ 2 ≤ 1 144ℓ , and α < 1 20 .Theorem 9. Let {F t } t∈N be a filtration on (Ω, F, P). Let A t , B t , C t , D t be four stochastic processes adapted to the filtration such that there exist σ C , σ D > 0 and τ 1 > 0 such that for all t ∈ N: (i)B t ≥ 0, (ii) E[e λCt+1 | F t ] ≤ e λ 2 σ 2 C Bt for all λ > 0, (iii) E[e λDt+1 | F t ] ≤ e λσ 2 D for all λ ∈ 0, 1 σ 2 Dand (iv) At+1-At τ1 ≤ -B t + C t+1 + D t+1 . Then, for any q ∈ (0, 1], we haveP τ1 2 T -1 t=0 Bt ≤ (A0 -AT ) + τ1σ 2 D T + 2τ1 max{2σ 2 C , σ 2 D } log 1 q ≥ 1 -q.Proof. For some fixed γ > 0, letS T ≜ γ T -1 t=0 B t -(A 0 -A T )with the convention that S 0 ≜ 0. For any T ∈ N, we haveS T +1 = γ T t=0 B t -(A 0 -A T +1 ) = γ T -1 t=0 B t -(A 0 -A T ) + γB T -(A T -A T +1 ) = S T + γB T -(A T -A T +1 ) = S T + (γ -τ 1 )B T + τ 1 B T -(A T -A T +1 ) ≤ S T + (γ -τ 1 )B T + τ 1 C T +1 + τ 1 D T +1 ,where the inequality follows from condition (iv) of the hypothesis. Hence, for any 0 < λ ≤ 1 2τ1σ 2and any T ∈ N:E[e λS T +1 | F T ] ≤ E[e λS T e λ(γ-τ1)B T e λτ1C T +1 e λτ1D T +1 | F T ] ≤ e λS T e λ(γ-τ1)B T E[e 2λτ1C T +1 | F T ] 1 2 E[e 2λτ1D T +1 | F T ] 1 2 ≤ e λS T e λ(γ-τ1)B T e 4λ 2 τ1 2 σ 2 C B T 1 2 e 2λτ1σ 2 D 1 2 = e λS T e λ(γ-τ1+2τ1 2 λσ 2 C )B T e λτ1σ 2 D ,where the first inequality follows from Cauchy-Schwarz and in the second one we use (ii) and (iii) of the hypothesis. Fixing γ = τ 1 /2 yields for all 0 < λ ≤ 1 4τ1σ 2:γ -τ 1 + 2τ 1 2 λσ 2 C = τ 1 - 1 2 + 2λσ 2 C τ 1 ≤ 0.Therefore, for 0 < λ ≤ min1 4τ1σ 2 C , 1 2τ1σ 2 D, using B T ≥ 0 by (i) of the hypothesis, we getE[e λS T +1 | F T ] ≤ e λS T e λτ1σ 2 D ,and rolling this recursion backwards and noting S 0 = 0 yields:E[e λS T ] ≤ e λτ1σ 2 D T ;thus, using a Chernoff bound, we getP(S T > t) ≤ E[e λS T ]e -λt ≤ e λ(τ1σ 2 D T -t) .Since for q ∈ (0, 1],e λ(τ1σ 2 D T -t) ≤ q ⇐⇒ t ≥ τ 1 σ 2 D T - 1 λ log(q),we haveP τ 1 2 T -1 t=0 B t ≤ (A 0 -A T ) + τ 1 σ 2 D T - 1 λ log(q) ≥ 1 -q.The claim follows by taking λ = 1 2τ1 min 12σ 2 C , 1 σ 2 D .Theorem 11. In the premise of Corollary 8, sm-AGDA iterates (x t , y t ) for τ 1 ≤ 1 3ℓ satisfyP 1 T T -1 t=0 ∥∇xf (xt, yt)∥ 2 + κ∥∇yf (xt, yt)∥ 2 ≤ Qq,T , ≥ 1 -q, ∀ T ∈ N, ∀ q ∈ (0, 1],for someQ q,T = O κ(∆0+b0) τ1T + κ(δ 2 x + δ 2 y ) τ 1 ℓ + 1 T log 1 q explicitly stated in Appendix F, where ∆ 0 ≜ Φ(z 0 ) -Φ * , b 0 ≜ 2 sup x,y { f (x 0 , y; z 0 ) -f (x, y 0 ; z 0 )}.As a first step, we provide a helper lemma that shows that our concentration result (Theorem (6) , and they satisfy the conditions of Theorem 9 with the following constants:(i) σ 2 C = τ 1 (240δ 2 x + 32δ 2 y ), (ii) σ 2 D = 16ℓτ 2 1 δ 2 x + 64ℓτ 2 2 δ 2 y .Proof. The fact that A t , B t , C t , D t are measurable with respect to F t = F y t for any t ∈ N follows directly from the definition of F t . Note that x t and y t are also F t -measurable for all t ∈ N. We prove part (i) and part (ii) separately.(i). First, recall that C t+1 = Ct+1 = -c 4 ⟨∇ x f (x t , y t ; z t ), ∆ x t ⟩ -⟨c 5 ∇ y f (x t , y t ) + c 6 ∇ y f (x * (y t , z t ), y t ), ∆ y t ⟩. We would like to show that E[e λCt+1 | F t ] ≤ e λ 2 σ 2 CBt for all λ > 0. From Assumption 3, we note that for any λ ≥ 0:E exp λ⟨-c 4 ∇ x f (x t , y t ; z t ), ∆ x t ⟩ | F t ≤ exp 8λ 2 c 2 4 ∥∇ x f (x t , y t ; z t )∥ 2 δ 2 x ,where we used [35, Lemma 3] . Now, given the value of c 4 in Theorem 7 and the convexity of t → t 2 , we havec 2 4 ≤ 5 192βp p+ℓ p-ℓ 2 ℓ 2 τ 2 2 τ 2 1 2 + 5τ 2 1 (p + ℓ)τ 1 -1 2 + 5 4ℓ ν τ 2 1 2 + 5 4c 0 ℓ 2 τ 2 1 2 + 5 2c ′ 0 β 2 τ 2 1 2 .Now, leveraging the stepsize policy specified in Corollary 8, since α ∈ (0, 1), using (37) we get5 192βp p + ℓ p -ℓ 2 ℓ 2 τ 2 2 τ 2 1 2 ≤ 20 • α 12 3 ℓτ 2 1 2 ≤ 20 • α 3 • 12 3 2 τ 2 1 ≤ τ 2 1 4 . Similarly, as τ 1 ≤ 1 3ℓ , have |(p + ℓ)τ 1 -1)| ∈ [0, 1], which implies 5τ 2 1 (p + ℓ)τ 1 -1 2 ≤ 5τ 2 1 .Since ν = 12 τ1ℓ , we haveEQUATION4 . Furthermore, using (27), we haveEQUATION4 . Finally, (38) and α ∈ (0, 1) imply thatEQUATIONMoreover, noting ∆ y t is revealed after ∆ x t , using [35, Lemma 3] again along with the inequality ∥u + v∥ ≤ 2∥u∥ 2 + 2∥v∥ 2 , we have:EQUATIONwhere the last line follows from 0 < 1 + ℓτ 2 + 2L Ψ τ 2 ≤ 1 + 1 144 + 8 144 ≤ 2. Thus, since ∆ y t is revealed after ∆ x t , using ( 39) and ( 41) together with the tower property of the conditional expectations, we getEQUATIONFinally, observe that∥∇ y f (x t , y t )∥ -∥∇ y f (x * (y t , z t ), y t )∥ ≤ ∥∇ y f (x t , y t ) -∇ y f (x * (y t , z t ), y t )∥ ≤ ℓ∥x t -x * (y t , z t )∥ ≤ ℓ p -ℓ ∥∇ x f (x t , y t ; z t )∥,where in the last inequality we used the (p -ℓ)-strong convexity of f (•, y t ; z t ) and the fact that we have ∇ fx (x * (y t , z t ), y t ; z t ) = 0. Therefore, since p = 2ℓ, we obtainEQUATIONPlugging this inequality into (42) yieldsE exp -λ c 4 ⟨∇ x f (x t , y t ; z t ), ∆ x t ⟩ + ⟨c 5 ∇ y f (x t , y t ) + c 6 ∇ y f (x * (y t , z t ), y t ), ∆ y t ⟩ ≤ exp λ 2 48τ 2 1 δ 2 x + 128τ 2 2 δ 2 y ∥∇ x f (x t , y t ; z t )∥ 2 + 192λ 2 τ 2 2 δ 2 y ∥∇ y f (x * (y t , z t ), y t )∥ 2 ≤ exp λ 2 max 5 τ1 48τ 2 1 δ 2 x + 128τ 2 2 δ 2 y , 1536λ 2 τ 2 δ 2 y B t ≤ exp λ 2 τ 1 240δ 2 x + 32δ 2 y B t ,where the last inequality follows from τ 2 = τ1 48 .Proof of part (ii). Recall thatD t+1 ≜ Dt+1 = 2ℓτ 2 1 ∥∆ x t ∥ 2 + 8ℓτ 2 2 ∥∆ y t ∥ 2 . We would like to show that E[e λDt+1 | F t ] ≤ e λσ 2 D for all λ ∈ 0, 1 σ 2 Dfor some σ D > 0. First, observe that for any λ > 0such that λ ≤ min{ 1 16ℓτ 2 1 δ 2 x , 1 64ℓτ 2 2 δ 2 y }, we have E[e λDt+1 | F t ] = E e 2λℓτ 2 1 ∥∆ x t ∥ 2 +8λℓτ 2 2 ∥∆ y t ∥ 2 ≤ E e 4λℓτ 2 1 ∥∆ x t ∥ 2 1 2 E e 16λℓτ 2 2 ∥∆ y t ∥ 2 1 2 ≤ e 32λℓτ 2 1 δ 2 x 1 2 e 128λℓτ 2 2 δ 2 y 1 2 ≤ e λ(16ℓτ 2 1 δ 2 x +64ℓτ 2 2 δ 2 y ), where we used [35, Lemma 2] in the second inequality.Before completing the proof of Theorem 11, we provide another lemma that gives a lower bound on B in terms of the squared norm of the partial gradients, based on our choice of sm-AGDA parameters. Lemma 17. For any t ∈ N, we haveEQUATIONProof. Since ∇ x f (x t , y t ; z t ) = ∇ x f (x t , y t ) + p(x t -z t ), using ∥a + b∥ 2 ≤ 2∥a∥ 2 + 2∥b∥ 2 , we get∥∇ x f (x t , y t )∥ 2 ≤ 2∥∇ x f (x t , y t ; z t )∥ 2 + 2p 2 ∥x t -z t ∥ 2 .Hence, together with (43) and the definition of B t , we obtain∥∇ x f (x t , y t )∥ 2 + κ∥∇ y f (x t , y t )∥ 2 ≤ (2 + 2κ)∥∇ x f (x t , y t ; z t )∥ 2 + 2κ∥∇ y f (x * (y t , z t ), y t )∥ 2 + 2p 2 ∥x t -z t ∥ 2 ≤ max (2 + 2κ) • 5 τ 1 , 2κ • 8 τ 2 , 2p 2 • 8 βp B t ≤ max 20κ τ 1 , 16κ τ 2 , 32ℓ β B t .with the last inequality following from κ ≥ 1.We may now provide our proof for Theorem 11.Proof of Theorem 11. According to Lemma 16, the processes A t , B t , C t , and D t defined in the statement of Lemma 16 satisfy the conditions of Theorem 9 if we set τ 1 as the primal stepsize of sm-AGDA. Therefore, for any q ∈ [0, 1),P τ 1 2 T -1 t=0 B t ≤ τ 1 (V 0 -V T ) + τ 1 σ 2 D T + 2τ 1 max 2σ 2 C , σ 2 D log 1 q ≥ 1 -q.Thus, dividing by τ1 2 T and using Lemma 17, we can conclude that with the probability at least 1 -q, the following event holds:EQUATIONFinally, we can relate the potential gap V 0 -V T to the primal suboptimality, i.e., ∆ 0 , and to the duality gap, i.e., b 0 /2 = sup x,y { f (x 0 , y; z 0 ) -f (x, y 0 ; z 0 ), at the initialization, following the same arguments provided in [66] . More precisely, for V (x, y, z) ≜ f (x, y; z) -2Ψ(y, z) + 2P (z), we first observe thatEQUATION)where last line follows from f (x, y; z) -Ψ(y, z) ≥ 0 for all y, z and P (z) -Ψ(y, z) ≥ 0 for all y, z. Since p = 2ℓ, we also note that P (z 0 ) = min I Further Details about Figure 2 In this section, we provide further details about how the empirical and theoretical quantiles are estimated in Figure 2 and are compared.Generation of the theoretical quantiles Q q,T . For any given q ∈ (0, 1), estimating an upper bound on q,T requires estimating an upper bound on the quantity ∆ 0 + b 0 based on Theorem 11.Other constants such as r 1 , r 2 , r 3 , ℓ, and µ are explicitly known in the setting of this experiment based on the NCPL game where T = 10,000 is fixed.First, we set the initial point (x 0 , y 0 ) randomly, where each component of x 0 and y 0 is sampled uniformly from the interval [-20, 20], and we set z 0 = x 0 . We then estimate an upper bound on the quantity ∆ 0 + b 0 numerically based on a grid search, resulting in ∆ 0 + b 0 = 12. Second, we generate a linear mesh I m with a grid size m = 0.0002 over the interval [0, 1]. For q ∈ I m , we calculate Q q,T based on Theorem 11. Third, we generate a sequence of quantiles Q Im,T . These quantiles are used to create a CDF via linear interpolation using the scipy.interpolate package's interp1d function in Python. Note that this quantile sequence generates a CDF over the values Q Im,T .Generation of the empirical quantiles of the random variable X T . We generate 1,000 samples {X (i)T } 1000 i=1 from the sample paths corresponding to the NCPL game with T = 10,000, where X T = 1 T T t=1 ∥∇ x f (x t , y t )∥ 2 + κ∥∇ y f (x t , y t )∥ 2 represents the path averages of the gradients. Quantiles for this sequence were generated over I m using NumPy's quantile generator in Python, ensuring alignment with the mesh over which the theoretical quantiles were generated. Evidently, our theoretical quantiles dominate the empirical quantiles pointwise, demonstrating that in the challenging NCPL regime, our theory provides empirically verifiable guarantees on the tail behavior of the random variable X T .Comparison of quantiles. We plotted the CDF corresponding to the theoretical quantiles Q q,T over the values of the empirical quantiles using a common mesh grid over the range of the empirical averages of the sample paths. In other words, we scaled the quantiles Q q,T with an affine transformation so that their range matches the range of the empirical quantiles. This affine scaling preserves the shape of the distribution corresponding to the theoretical quantiles and allows for better visualization.f : R d → R ∪ {+∞} is called (merely) convex, if f (tx1(1 -t)x2) ≤ t f (x1) + (1 -t) f (x2) for every x1, x2 ∈ R d and t ∈ [0,1] with the convention that α ≤ +∞ for all α ∈ R.For example, when ∇f is smooth (Lipschitz and continuously differentiable) and the signed gradient map G(x, y) is star-cocoercive with constant ℓ > 0 around a stationary point (x * , y * ), then by[21, Lemma C.6], the operator Id -2 ℓ G(x, y) is non-expansive around (x * , y * ); thus, the Jacobian of G at (x * , y * ) has non-negative eigenvalues implying f is merely convex/merely concave around (x * , y * ), i.e., f cannot be NCSC.Given a random variable ξ, σ(ξ) denotes the σ-algebra generated by ξ; moreover, given two σ-algebras, Σ1 and Σ2, abusing the notation, σ(Σ1, Σ2) denotes the σ-algebra generated by Σ1 ∪ Σ2. 


Decision: This paper addresses the high probability convergence of the Gradient Descent-Ascent-type method for stochastic nonconvex minimax optimization. The problem studied is PL in the max variable and hence the inner problem is computationally "easy" to solve. Having easy inner problem and working with the dual function makes the problem easier than some other settings to analyze (in min-max optimization). By deriving high probability bounds, the paper extend previous results that only provided bounds in expectation. The analysis also introduces a new concentration bound  that might be of independent interest.  The paper includes numerical experiments comparing their studied algorithms with existing methods. 

Some reviewers found the theoretical techniques (particularly the concentration bounds) not significantly novel, as it follows existing bounds/techniques. Some reviewers believe that the paper could benefit from a deeper comparison with related works, especially regarding the differences between the current and prior analyses.  There were also some concern that the algorithmic contributions have limited insight into new theoretical developments beyond those already present in the literature.

Overall, the paper is borderline. While the paper makes contributions to the theoretical understanding of GDA-type algorithms for min-max optimization, addressing the above concerns could strengthen its impact.

Reviews: review: paper_summary: paper_summary: The authors derive a high probability bound for convergence of a stochastic gradient descent-ascent method over a nonconvex (PL class) of functions. Specifically, they analyze the sm-AGDA algorithm, which previously only had a bound in expectation, and show a similarly tight high probability bound when gradient noise is assumed subgaussian. The authors provide two experimental settings demonstrating that the distribution of these iterates over multiple runs converge as expected for the algorithm.
strength_weakness: strength_weakness: * While I understand that the bound in Thm 10 over the average gradient norms motivates the random sampling of iterates in the sm-AGDA algorithm, it still seems like practically the best thing to do in Fig. 1 is to take the last iterate (or at least sample over some last window of iterates). Is there a straightforward way to come up with a similar high probability bound on the last iterate? 

* I'd maybe like to see more discussion about how the analysis in this paper differs from that in the original sm-AGDA work [63]. At least for some previous work I've seen with high probability bounds for convex optimization, oftentimes the actual modification required to go from expectation to high probability is fairly minor (i.e. just boils down to bounding the summation of Subgaussian noise terms).

* I like the first set of experiments but a bit confused at the purpose of the second. I don't quite understand comparing concentration properties of other methods if the analysis only applies to one algorithm. Maybe if the authors highlighted what unique components of the sm-AGDA algorithm might give it better quantile convergence properties than others this would make more sense.

If the authors can address some of these concerns I am willing to raise my score to a more solid accept

Other Minor Notes:
* DRO abbreviation in line 238 not defined initially
* [63] and [64] appear to be referencing the same paper
* Line 306 and 311 appear to be referencing the wrong figure
questions: questions: * As mentioned in remark 11 this bound appears to be pretty tight compared to the bound in expectation. Do you think if this type of analysis was applied to other existing algorithms you would get similarly tight bounds?
limitations: limitations: The authors clearly state their assumptions.
paper_summary: paper_summary: This paper considers the important open problem of stochastic smooth nonconvex minimax optimization. This paper proposes single-loop stochastic GDA method, which was known to be practically desirable but had no theoretical complexity compared to other non-single-loop methods with better complexies on nonconvex minimax problems. The analysis in this work fills some of above gap, provides the first high-probability complexity for nonconvex minimax while assuming a PL condition on dual variable, and proves assuming light tailed stochastic gradients GDA converges to a near stationary point with a certain complexity. Numerical results on NCPL game with synthetic data and distributionally-robust optimization with real data shows the proposed sm-AGDA outperforms existing algorithms SAPD+ and SMDAVR.
strength_weakness: strength_weakness: 1. Font size at the end of Page 8, and entire Page 9 are smaller than the required size. 

2. There is not much algorithm novelty from [68].
questions: questions: 1. What are the existing best-known complexities of (possibly non-single-loop) algorithms on nonconvex minimax problem?

2. Can you compare in more details (overall problem class, overall algorithm, assumptions, complexity order dependencies) of your complexity result compared with [64]? 

3. Does each of your assumption (PL condition, etc.) hold for both of your numerical experiments?

**Updates: 

The authors' rebuttal addressed every question very well. I have increased my score from 6 to 7.
limitations: limitations: N/A
paper_summary: paper_summary: The authors build upon earlier works to prove a high probability upper bound, that is linear in variance of the stochastic gradients, on the number of stochastic gradient calls of smoothed alternating GDA method.
strength_weakness: strength_weakness: Focusing only on their concentration bound, which they claim is of independent interest and is the crux of their high probability bounds: the bound in Theorem 9 (which is fairly customized and not easy to state) follows like any other chernoff/chebychev type bound - using Markov type inequality after exponentiation; and I don't see any novelty in their theoretical ideas/techniques here. Perhaps I have missed something, if so the authors can clarify it.
questions: questions: see weaknesses
limitations: limitations: Theory paper, no concerns
paper_summary: paper_summary: This paper investigates the stochastic non-convex minimax optimization problem $\min_x \max_y f(x,y)$ where the function $f$ is smooth, then nonconvex in $x$ and PL in $y$. The authors presented a high probability analysis for the smoothed alternating gradient descent ascent (sm-AGDA) method. This analysis is based on a Lyapunov function from prior work for non-convex concave setting. Also, under a light-tail assumption on the gradient noise, the authors developed a concentration result. Finally, they include experiments of nonconvex-PL setting with synthetic data and then distributionally robust optimization problems with real data.
strength_weakness: strength_weakness: 1. While the authors cited some results in expectation for the similar setting, I think it is important to compare the (Markov) high probability bounds obtained by these expectation results with the results obtained in this paper. If the results are not better, then the contribution is limited. 

Also I don't get what the authors meant by "More precisely, we focus on a purely stochastic regime in which data streams over time which renders the use of mini-batch schemes or running the method in parallel impractical; therefore, approaches based on Markov’s inequality [59] are no longer applicable." (line 99-101). 

2. In the theorems and lemma, the values $\tau_1, \tau_2, \tau, \bar{\tau}$ is really confusing. Do you need to pick specific values for the step sizes, if so, what is $\tau_2$? Are $\tau$ and $\bar{\tau}, \tau_1$ the same?

Update: I thank the authors for the rebuttal. I keep my recommendation the same, as changing to high probability bound from expectation results is somewhat expected.
questions: questions: Why in the experiments the authors compare with SAPD+ and SMDAVR, not the methods in Table 1?
limitations: limitations: NA
paper_summary: paper_summary: This paper proves a high probability convergence bound and almost sure convergence for stochastic smoothed AGDA method for minimax problems in nonconvex-PL setting. This is the first high probability guarantee and almost sure convergence guarantee in this nonconvex setting.
strength_weakness: strength_weakness: See Questions.
questions: questions: 1. The algorithm and analysis are built upon the approaches in 63 and 68. Could the authors provide more insights on the novelty of the proof compared to 63 and 68?
2. Is it possible to extend this analysis to other settings like the nonconvex-concave setting?
3. Can this analysis be extended to other algorithms such as stochastic GDA?
4. Missing references: 
[1]. Shen et al   Stochastic gradient descent ascent for federated minimax optimization
[2]  Zheng et al Universal gradient descent ascent method for nonconvex-nonconcave minimax optimization 
[3].  Ozdaglar et al What is a good metric to study the generalization of minimax learners
[4] Li et al Nonsmooth-nonconvex-nonconcave minimax optimization: primal-dual balancing and iteration complexity analysis
limitations: limitations: N/A

Comments: title: Response to authors
comment: > We mentioned Thm 9 to be of independent interest, not because it is particularly hard to prove but because it acts as a useful inequality potentially applicable to other algorithms like stochastic AGDA and stochastic gradient descent (SGD).

I have increased the score, but please clarify the above in the main body of the paper, so that your contributions are clear.
Thanks for the response. I will keep my score.
I believe the authors addressed all 5 of my questions very well. I hope the authors will add those valuable discussions in the appendix. Based on the rebuttal, I update my score from 6 to 7.