Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization
Authors: Aniket Das
Bernhard Schölkopf
Michael Muehlebach
Venue: NeurIPS 2022 Accept (2022)
Keywords: Minimax Optimization
Smooth Games
Nonconvex-Nonconcave Minimax Optimization
Sampling without Replacement
Random Reshuffling
Shuffle Once
Incremental Gradient
Gradient Descent Ascent
Proximal Point Method
Alternating Gradient Descent Ascent

Abstract: We analyze the convergence rates of stochastic gradient algorithms for smooth finite-sum minimax optimization and show that, for many such algorithms, sampling the data points \emph{without replacement} leads to faster convergence compared to sampling with replacement. For the smooth and strongly convex-strongly concave setting, we consider gradient descent ascent and the proximal point method, and present a unified analysis of two popular without-replacement sampling strategies, namely \emph{Random Reshuffling} (RR), which shuffles the data every epoch, and \emph{Single Shuffling} or \emph{Shuffle Once} (SO), which shuffles only at the beginning. We obtain tight convergence rates for RR and SO and demonstrate that these strategies lead to faster convergence than uniform sampling. Moving beyond convexity, we obtain similar results for smooth nonconvex-nonconcave objectives satisfying a two-sided Polyak-\L{}ojasiewicz inequality. Finally, we demonstrate that our techniques are general enough to analyze the effect of \emph{data-ordering attacks}, where an adversary manipulates the order in which data points are supplied to the optimizer. Our analysis also recovers tight rates for the \emph{incremental gradient} method, where the data points are not shuffled at all.

Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization
Aniket Das
Bernhard Schölkopf
Indian Institute of Technology Kanpur aniketd@iitk.c in
Max Planck Institute for Intelligent Systems bs@tuebingen. mpg. de
Michael Muehlebach
Max Planck Institute for Intelligent Systems michaeln@tuubbinen mpg. de
Abstract
We analyze the convergence rates of stochastic gradient algorithms for smooth finite-sum minimax optimization and show that, for many such algorithms, sam- pling the data points without replacement leads to faster convergence compared to sampling with replacement. For the smooth and strongly convex-strongly concave setting, we consider gradient descent ascent and the proximal point method, and present unified analysis of two popular vithouttrepllcemeet sampling strategies, namely Random Reshuffling (RR), which shuffles the data every epoch, and Single Shuffling Shuffle Once (SO), which shuffles only the beginning. We obtain tight convergence rates for RR and SO and demonstrate that these strategies lead to faster convergence than uniform sampling. Moving beyond convexity, we obtain similar results for smooth nonconvex-nowe comconvex-nonconcave objectives satisfying a two-sided Dolyak-Lojasiewice inequality. Finally, we demonstrate that our techniques are general enough to analyze the effect of data-ordering attacks, where an adversary manipulates the order which data points are supplied to the optimizer. Our analysis also recovers tight rates for the incremental gradient method, where the data points are not shuffled at all.
Introduction
The approximate solution of large-scale optimization problems using first-order stochastic gradient methods constitutes one of the foundations of classical machine learning. However, emerging problems in machine learning go beyond pattern recognition and involve real-world decision making, where learning algorithms interact with unknown or even adversarial environments or are deployed in multi-agent settings. Decision making in such environments often involves solving minimax optinization problem of the form miny max, F(x, y), whose analysis has been a focus of research mathematics, economics, and theoretical computer science [38, 13, 10]. Recent examples of its applications in machine learning include adversarial learning [32, 52, 6]. reinforcement learning [30, 58, 11, 42], imitation learning [14, 24), and generative adversarial networks [18, 2]. In most of these applications, the objective F(x,y y) has finite-sum structure, i.c. F(x, y) 1/n E fx
where n denotes the size of the dataset and each component function fr denotes the objective associated with the 7th data point. The resultant problem is known finite-sum minimax optimization:
*Currently at Google Research. Contact: ketd@ googl..oolecoom
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1 E y).
min max XER YERdy n2
When n is large and the fi's are differentiable (which holds for most applications), approximate solutions to (1) are computed using stochastic gradient algorithms. These algorithms typically sample an index i E [n] at each iteration as per some specified sampling routine, and use the gradients of fi to compute the next iterate. Among these methods, perhaps the simplest and most commonly used algorithm is Stochastic Gradient Descent Ascent (SGDA), a natural extension of Stochastic Gradient Descent (SGD) for minimax optimization.
Similar to the stochastic optimization literature, analysis of stochastic minimax optimization often assumes that, at every iteration, the index is sampled uniformly with replacement. Analysis of the resulting algorithm closely parallels the analysis of SGD, and relies on the fact that uniform sampling leads to unbiased gradient estimates. Recent works [20, 31] have also extended this paradigm to i.id uniform sampling of mini-batches. While uniform sampling assumptions simplify theoretical analysis, practical implemennatiinss of these algorithms often deviate from this paradigm, and instead incorporate various heuristics, which are often empirically found to improve runtime. A common and notable heuristic is replace uniform sampling by procedures that perform multiple passes over the entire dataset, and in each such pass (called an epoch), sample the data points without replacement. Thus, each data point sampled exactly once in every epoch. These procedures are generally implemented using one of the following approaches:
Random Reshuffling (RR): Uniformly sample random permutation of [n] at the start of every epoch, and process the data points within that epoch as per the order specified by the permutation.
Single Shuffling or Shuffle Once (SO): Uniformly sample random permutation at the beginning and reuse across all epochs to order the data points.
Incremental Gradient (IG): Do not permute the data points at all and follow fixed deterministic data ordering for every epoch.
Sampling without replacement is ubiquitous in both stochastic minimization [7, 48, 4] and stochastic minimax optimization [18, 2] as it often exhibits faster runtime than uniform sampling. However, these empirical benefits come at the cost of limited theoretical understanding, due to the absence of provably unbiased gradient estimates.
It is well known in the optimization literature that SGD with replacement has a tight rate of (1//kk) for smooth and strongly convex minimization [44, 25], where n is the number of component functions and K denotes the number of epochs. On the contrary, recent works on SGD without replacement for smooth and strongly convex minimization [1, 36, 34, 39] show that both RR and SO achieve non-asymptotic rate of Ö(I/nk²), once the number of epochs K is larger than a certain threshold Ko (usually polynomial in the condition number), and thereby converge faster than SGD with replacement. These rates match the lower bound of ((1/nk3) for RR and SO established in prior works [43, 48), modulo logarithmic factors. For RR, prior works have also established a similar O(L/nK²) rate for nonconvex objectives satisfying the While the asymptotic behavior of IG has been known to the community for long time in both smooth and mon-hh settings [5, 37], non-asymptotic O(1/3* convergence rates have been established quite recently [34, 39, 22], and are complemented by a matching ((1/K?) lower bound [48].
(PL) inequality [1. 34).
1.1 Contributions
Although the empirical benefits of sampling without replacement have been substantiated for min- imization, analysis of these methods for minimax optimization have received much less attention, despite being widely prevalent in many applications. Our work aims to fill this gap by analyzing these methods for minimax optimization. To this end, main contributions are follows:
Unified analysis of RR and SO for smooth strongly convex-strongly concave problems: We analyze RR and SO in conjunction with simultaneous Gradient Descent Ascent (GDA), calling the resulting algorithms GDA-RR and GDA-SO, respectively. Assuming the components f; are smooth and F is strongly convex-strongly concave, we present unified analysis of GDA-RR/SO and establish convergence rate of ((exp( - K/5k²) + 1/nk3) for both (where k is the condition
2

---

number). Comparing with lower bounds, we show that our rates are nearly tight, i.c., they differ from the lower bound only by an exponentially decaying term. Moreover, when K 2 10x² log(n' K), the convergence rate matches the lower bounds for GDA-RR/SO, modulo logarithmic factors, and also converges provably faster than SGDA with replacement. Under the same setting, we obtain similar guarantees for the RR and SO variants of the Proximal Point Method (PPM), named PPM-RR and PPM-SO respectively. Our analysis for both GDA-RR/SS and PPM-RR/SO is general enough to cover smooth strongly monotone finite-sum variational inequalities, which covers minimization, minimax optimization, and multiplayer games.
We consider class of nonconvex-nonconcen problems where the objective F satisfies a fwo-sided Polyak-tojjssewwiz inequality. For such problems, we propose an algorithm that combines RR with two-timescale Alternating Gradient Descent Ascent (AGDA), which we call AGDA-RR. We show that AGDA-RR has a nearly tight convergence rate of O(exp(-K//3000 /365x") + 1/nk2) when the gradient variance is uniformly bounded. When K 2 730k3 1og(n this rate matches the lower bound (modulo logarithmic factors) and improves on the best known rates of with-replacement algorithms for this class of problems.
RR for smooth two-sided PE. objectives:
Minimax optimization under data ordering attacks: Our techniques for analyzing RR/SO general- ize to the analysis of finite-sum minimax optimization under data ordering attacks [51]. These attacks target the inherent randomness assumptions of stochastic gradient algorithms, significantly increasing training time and reducing model quality, only by manipulating the order in which the algorithm receives data points, without performing any data contamination. To model these attacks, we propose the Adversarial Shuffling (AS) setup, where the data points are shuffled every epoch by computa- tionally unrestricted adversary. In this setup, we show that GDA and PPM (now called GDA-AS and PPM-AS) have a convergence rate of concave objectives, and AGDA (now called AGDA-AS) has a rate of ((ex((KK ((xxp()(3355²') /365m²² + 1/K²) for two-sided PL objectives. We note that, compared RR and SO, the convergence rate worsens by a factor of 1/n for large enough K. When n is large (true for most applications), this slowdown significantly impacts convergence and thus, theoretically justifies the empirical observations in prior work [51]. We also establish that our analysis in the AS regime also applies to the Incremental Gradient (IG) variants of these algorithms (namely GDA-IG, PPM-IG, and AGDA-IG), and use this to show that our obtained rates for GDA-RR and AGDA-RR are nearly tight.
for smooth strongly convex-strongl,
To the best of our knowledge, our work is the first to: 1) analyze RR, SO, and IG for strongly monotone unconstrained variational inequalities, 2) analyze RR and IG for a class of nonconvex-nonconcayy minimax problems, 3) provably demonstrate the advantages of sampling without replacement for both these settings and justify its empirical benefits in wide variety of problems ranging from minimization, minimax optimization to smooth multiplayer games, 4) analyze sampling without replacement under data-ordering attacks. Furthermore, unlike prior works on sampling without replacement for minimax optimization [55, 33], which are restricted to random reshuffling and require the component functions to be convex-concave, Lipschitz, and smooth, our analysis does not impose any restrictions on the components fa other than smoothness, allowing them to be arbitrary nonconvex -onoonevx-nnnooccveee functions.
2 Notation and Preliminaries
We work with Euclidean spaces (Rd, (..-)) equipped with the standard inner product (2) and the induced norm [x]. For any x E Rd and y E Rdd, we denote z = (xxy) E Rd where dl = dx + dy- Moreover, for any 2 = yI) ) E Rd and Z2 = (x2, y2) E IRd (Z), 22) = (x1, + (y Y2) and |z 2 = | 2 + |y - Whenever 2 y) is clear from the context, we write yxx as f(z). We use S. to denote the set of all permutations of [m] = {I...., nn. For any matrix A, its operator norm is denoted by |A| = suppi|=1 Axx] We use the O notation to characterize the dependence of our convergence rates on n and K, suppressing numerical and problem-specife constants such as K. ,4, a, etc. Additionally, we use the Ô notation to suppress logarithmic factors of n and K.
Our work studies finite-sum minimax optimization (1). Solutions to (1) are known as global minimax points of F = 1/m Σn_ fi, which we assume to always exist. We also assume that the components fi are continuously differentiable, and hence, the same applies to F. This allows us to define the
3

---

gradient operators w, R + Rd and V R2 - R as follows:
"
wx y)
-yyl(xx)))) vxx,))
1 Σ
We also impose the following smoothness assumption on the components fi.
Assumption 1 (Component Smoothness). The component functions fü are I-smooth, i.e., each gradient operator wi is I-Lipschitz
(wx(Z)) we (x()))) S |z2 z1/.
Consequently, the operator u is also 1-Lipschitz, ie., F is I-smooth.
3 Analysis for Strongly Convex-Strongly Concave Objectives
In this section, we analyze two very popular without-replacemmnt algorithms for finite-sum minimax optimization, Gradient Descent Ascent (GDA) without replacement and Proximal Point Method (PPM) without replacement. For each of these, we present a unified analysis of the Random Reshuffling (RR) and Shuffle Once (SO) variants (called GDA-RR/SO and PPM-RR/SO respectively). For fixed K > 0, GDA-RR/SO approximately solves (1) by iterating over the entire dataset for K epochs, and within each epoch, uses the operators w; perform the following iterative update:
z f - - aw (z Vi E [r]].
(2)
where Th is a uniformly sampled random permutation of [n] and 0 < a < <1/l is a constant step-size. GDA-RR resamples тı at the start of every epoch, whereas GDA-SO samples it only once in the beginning. The details of both algorithms are presented in Algorithm 1. The Proximal Point Method without replacement is closely related algorithm which, instead of performing gradient descent-style updates within an epoch, solves the following implicit update equation for z;
z aw,, (1) (z() Vi [r]].
As before, Th is resampled at every epoch for PPM-RR, and sampled once and fixed for all epochs for PPM-SO. We present the details in Algorithm 2. The /-smoothness of w; along with the choice of a < 1/1 ensures that z is uniquely defined, since it is fixed point of the contraction mapping ((z) _ OwT,, (i) (z). This method is actually generalization of the (stochastic) proximal point method for minimization problems, and is popular for problems where (3) can be solved easily or in closed form. We refer the readers to Rockafellar [47], Patrascu and Necoara [41] for review of this method and its connections the original proximal point method for minimization.
3.1 Setting
We analyze GDA-RR/SO and PPM-RR/SO for smooth finite-sum strongly convex-strongly concave (or SC-SC) objectives. This allows to formulate the minimax optimization problem for F as root finding problem for the gradient operator v, as described below.
Assumption 2 (Strong Convexity- -ttrong Concavity). The objective F is μa strongly convex- convex-strongly concave (or SC-SC), i.e., F(,, is u-strongly convex for any y IR and -F is p-strongly corvex for any x E Rdx
Assumption has the following consequences for the gradient operator v:
Lemma 1. Let F' satisfy Assumptions I and 2. Then, the gradient operator v j-strongly monotone:
(v(zz) v(zz), z1 zz) 2 / |z1 zzl" V Zı Z2 E Rd.
Furthermore, (1) admits a unique solution z", which also the unique solution of v(z') =
Lemma 1 allows us to recast (1) for SC-SC objectives as the following root finding problem:
Find z E IRd such that v(z) 1/n wi(z) = 0.
(4)

---

Algorithm 1: GDA-RR/SO/AS
Algorithm 2: PPM-RR/SO/AS
Input :Number of epochs K, step-size > 0, and initialization Zo
Input :Number of epochs K, step-size a 0, and initialization Zo
Initialize 2 <- Zg
Initialize zg <- Zo
SO: Sample ~ (S,,)
SO: Sample Uniform(S.)
for k E [K] do
for k E [K] do
RR: Sample ты Uniform(S,)
RR: Sample Tı ~ Uniform(S.))
SO: T f-
SO: 7k t-1
AS: Adversary chooses E Sn.
AS: Adversary chooses 7 E Sn
for i E [n] do
for i E [r]] do
Solve the implicit update for z where, z 2 (o)x())
z f z (w) (2f-1)
end
end
20 k+1
f- z
20 k+1
2
end
end
Figure I: GDA-RR/SO/AS and PPM-RR/SO/AS for solving (4). Violet lines denote steps that are only performed for RR, Olive lines denote the same for SO and Magenta for AS.
Problem (4) is more general than SC-SC minimax optimization, and is a special case of strongly monotone variational incqualities [13] without constraints. Notably, (4) includes the Nash Equilibrium problem for unconstrained multiplayer games with smooth strongly convex objectives [50] and is sometimes called a finite-sum unconstrained variational inequality in the literature [31]. We also highlight that smooth strongly convex optimization is a special case of (4). However, unlike the optimization setting, is longer restricted to be the gradient of strongly convex function, which, as we shall see, has important consequences for the attainable convergence rates of our algorithms.
3.2 Analysis RR/SO
We now state the expected last-iterate convergence guarantees for Algorithms 1 and 2 for solving (4), where the expecation taken over the stochasticity of the sampled permutation(s).
Theorem 1 (Convergence of GDA-RR/SO and PPM-RR/SO). Consider Problem (4) for the μ- strongly monotone operator v(z)=11) 1/1 Ei (;(z) where each wi is I-Lipschitz, but not necessarily monotone. Let z denote the unique root v. Then, there exists a step-size a S #/sml? for which both GDA-RR/SO and PPM-RR/SO satisfy the following for any K 2 1:
2+ 2p² + 8k2 0 log" (lu(z)) 12 Ô(e K/om² +1/nk?),
ElIz K+1 -z" 2-19 2e
K/S.²
Zo 2o--z"p
12nK2
where k= = 1/1 is the condition number and o? = 1/1 Ei ( is the gradient variance at z".
We present an outline for GDA-RR/SO and defer the full proof to Appendix C.2 (for GDA- RR/SO) and Appendix D.2 (for PPM-RR/SO). Furthermore, we recall that the updates of GDA-RR/SO given by 2 2 (z) (2)
Proof.
We begin with the following key insight from earlier works on sampling without replacement for minimization [23, 1, 37, 22]: for small enough step-sizes, the epoch iterates z of GD without replacement approximately follow the trajectory of full-batch gradient descent. To this end, we derive the following epoch-level update rule for GDA-RR/SO by linearizing (1) (z{,) around z":
k+1 z
Hz z" + r
(5)
where Hy| 1 napu/2 and Fg = Σi Ar,(0) Ej=1 (z") with A S l/ The term ry encapsulates the noise of the stochastic gradient updates accumulated over an entire epoch. To ensure convergence, we control the influence of the noise term r& by using standard properties of wethouttreplaacement sample means to show that E[[rx|"]= < on then complete the proof by unrolling (5) for K epochs, substituting the upper bounds for [Ha] and []] wherever necessary, and setting a min(u/ 5ml2 2 (og((v(z)) (2//K/p)) p/)KK)).
of /4 for both RR and SO. We
5

---

As we show in Appendix C, the update rule (5) resembles the linearized update rule of full batch GDA with added noise. In fact, for n Fa 0 and thus. we recover the rates of full-batch GDA. Expressing GID-RR/SOO (and later AS) as noisy full-batch GDA in this fashion is a central component of our unified analysis, and relies on the fact that Σ (r (z*) = A Tı E Sn, which is specific to sampling without replacement. Comparing to SGDA with replacement, we note that sampling the components i.id. uniformly as u(i) ~ Uniform( [rz]) gives rise to an additional noise term ap& in the update rule, where ps: ">imi Wa(t) (z*) vanishes only in expecation, and has variance of [E| | || no?. Subsequently, the dominant noise term for SGDA updates is ((a2no?) whereas that of GDA-RR/SO is O(a o²). which qualitatively demonstrates the implicit variance reduction of sampling without replacement. As we shall see in the complete proof, this allows RR/SO
to converge faster (for large enough K) by carefully selecting a.
L
Comparison with lower bounds: Since smooth strongly convex minimization is a special case of (4), the (?) lower bound established in prior works [48, 43] for smooth strongly convex minimization using GD with RR/SO also applies to GDA-RR/SO. Comparing with this lower bound, we note that the convergence rate of GDA-RR/SO is nearly tight, i.e., it differs from the lower bound only by an exponentially decaying term. In fact, for K 2 10k²² log(n!/2K3 the convergence rate becomes O()/nk²), which precisely matches the lower bound, modulo logarithmic factors.
Comparison with uniform sampling: Similarly, the (2(1/KK) lower bound of SGD with re- placement for smooth and strongly convex functions [44] also applies to SGDA with replacement. On the contrary, both GDA-RR and GDA-SO converge with a faster rate of Ó(1/nk²) when K 2 10x² K)) Thus, GDA-RR/SO provably outperform SGDA with replacement (modulo logarithmic factors) when K 2 10n.2 (og(n//2K) As we show in Appendix C.2, the X² dependence of this inequality cannot be improved for constant step-sizes. A similar argument also applies to stochastic PPM. To the best of our knowledge, the fastest known convergence rate for stochastic PPM is O(1/nK) for minimizing smooth strongly convex functions [41]. Hence, Theorem suggests that PPM-RR/SO enjoy faster (l)nk33 convergence rate for both minimization and minimax optimization when K 2 10x² log(n /2 K).
3.3 Analysis in the Adversarial Shuffling Regime
We now consider
minimax optimization algorithms in an adversarial setting. We focus on novel class of training-time time attacks known as data ordering attacks proposed by Shumailov et al. [51]. These attacks differ from standard data-perturbation attacks [19] and exploit the fact that most implementations of stochastic gradient optimizers do not verify whether the permutation Tk is truly sampled at random. Shumailov et al. [51] propose three distinct attack strategies, namely, batch reordering, which changes the order in which mini-batches are supplied to the algorithm, batch reshuflling, which changes the order in which individual data points are supplied, and replacing which prevents certain data points from being observed by the algorithm by consistently replacing them with other data points in the training set.
We analyze the convergence of without-replacemmen GDA and PPM under batch reshuffling attacks. To this end, we consider an adversarial modification of RR/SO where the permutations Tke instead of being sampled by the algorithm, are now selected by an adversary using a strategy unknown the algorithm. We also the assume that, while choosing Tk, the adversary is computationally unrestricted and has complete knowledge of all the components wi, the minimax point z", and the iterates z! observed so far. We call this setup Adversarial Shufflig (AS) and obtain convergence rates of GDA and PPM (named GDA-AS and PPM-AS) when solving (4). Thus, our analysis naturally holds for minimization, minimax optimization as well as finite-sum multiplayer games. The details are stated in Algorithms and 2, respectively. Our last iterate convergence guarantees are deterministic and hold uniformly over any sequence of permutations Ti...., TK that the adversary can choose.
Theorem 2 (Convergence of GDA-AS and PPM-AS). Consider Problem (4) for the p-strongly mono- tone operator v(z) = 11/n Ei wi(z) where each w; is I-Lipschitz, but not necessarily monotone.
Let z" denote the unique root of v. Then, there exists step-size a S 1//mt for which both GDA-AS and PPM-AS satisfy the following for any K 2
20 8a-27 z 24 24² + 24x² 0² log 3 (1((Z)) K/H) = =ō(e k/ +/5x2+1/K3),
20?
K+1 2u
22 <e
K/bn²
max
Ti..... EG,
2 K2

---

where K. o² are as defined in Theorem I and :...... TK are the permutations chosen by the adversary.
Convergence rates of IG and comparison with lower bounds: We note that the Incremental Gradient and the Incremental Proximal Point Methods, which do not shuffle the data, are a special case of EDA-AS/PPM-AS with Ti,.... TKK id. Thus, Theorem 2 also gives us convergence rates for GDA-IG/PPM-IG, Moreover, since GDA-AS generalizes GDA-IG and (4) covers minimization, the ((1/22) lower bound of IG established in prior works [48] for smooth strongly convex minimization also applies to GDA-AS. Thus, our obtained rate for GDA-AS is nearly tight and matches the lower bound (modulo logarithmic factors) for K 2 10k² (.).
Effectiveness of batch reshuffling: When K 2 10k² log (). O(1/K3) becomes the dominant term in the convergence rate of AS. This is worse than that of RR/SO by factor of 1/n and causes a significant slowdown in convergence. since, in many applications, the dataset size n is much larger than K. Thus, our analysis justifies the effectiveness of batch reshuffling attacks in reducing model aceuracy and increasing training time, which is empirically verified by Shumailov et al. [51].
4 RR for Two-Sided PL Objectives
We now analyze RR for a class of smooth nonconvex-nonconen problems where the objective F satisfies a two-sided Polyak Enjasiewicz inequality, first proposed in Yang et al. [54]. We denote this function class as 2PE. and formally state the assumption as follows.
Assumption 3 (Two-sided Polyak Lojasiewicz Inequality or 2Pt. condition). For any x E Rdx, y E Rd,, the sets arg maxy F(x, y) and arg ming F(x.y) are non-empty. Furthermore, there exist positive constants μ1, P2 such that F satisfies the following:
F(x. ?) [F
- min F(x,y)), FyF,xy)) 2 2p22 max - y(x,y)] *ER*
yER"y
The 2PL condition is satisfied in several practical settings, including, but not limited to, robust least squares [12]. imitation learning for linear quadratic regulators [14, 8), and various other problems in reinforcement learning and robust control [11, 8]. Clearly, any SC-SC function is 2PE. However, 2PL functions need not be SC-SC, or even convex-concave. We refer the readers to Yang et al. [54] for a detailed discussion of the 2PL. class and its applications.
Analysis of RR for 2PL. objectives challenging not only due to wertonvexity-oonnoncavvee but also because F may not have a unique minimax point. Indeed, as we demonstrate in Appendix 1, it is possible to construct 2PE functions where the set of minimax points is an unbounded proper subset of S Hence, the notion of gradient variance at the minimax point, which we used in our earlier analyses, is no longer meaningful. To overcome this, we impose the following assumption.
Assumption 4 (Bounded Gradient Variance). There exists a positive constant such that the component gradient operators wi satisfy the following for any z E R2,
1/n
(x(()) -1(2)= < o²
4.1 Analysis of AGDA-RR and AGDA-AS
In order establish the provable benefits of RR for smooth finite-sum minimax optimization of 2PL. objectives, we propose the Alternating Gradient Descent Ascent with Random Reshuffling (AGDA- RR) algorithm. AGDA-RR achieves near-optimal convergence guarantees for 2PL objectives by combining RR with alternating updates [17, 57, 3] and timescale separation [29, 15, 16), two ideas that have been very useful for improving convergence and stability in sunconvex-nonconeee optimization. Within each epoch k E [K] AGDA RR uniformly samples random permutation 7k- makes one full pass over the dataset, and performs gradient descent (with RR) updates for the variable x using the permutation Tи- This is followed by sampling another permutation тr and performing gradient ascent (with RR) updates for y using the permutation тą. The detailed procedure is stated in Algorithm 3. We also analyze variant of AGDA-RR in the adversarial shuffling setting, which we call AGDA-AS. The procedure, as described Algorithm 4, almost identical to AGDA-RR, except that the permutations Tę and rT. are chosen by an adversary.
minimax
7

---

Algorithm 3: AGDA-RR
Algorithm 4: AGDA-AS
Input :Number of epochs K, step-sizes 0 > 0, and initialization (Xo,oo)
Input :Number of epochs K, step-sizes
0, > 0, and initialization (Xo
Initialize vo) <- (o)
Initialize yd) +- (X)
for k [K] do
for k E [K] do Adversary chooses permutation E Sn
Sample permutation T Sp.
for n do
for
n do x VVxfr (,
- aVxfn (xf v.))
end
end
Sample permutation T E Sn for In| do y y + V (
Adversary chooses a permutation Th Sn for i [n] do y y + 8V ( yt
end
end
(x0 yY x+ t yx)
(x)
yo x+1) t (x yii)
end
end
Before presenting a convergence analysis, we highlight that the absence unique minimax point prevents us from using the squared distance to the optimum use the Lyapunov function VA TRd -> which was previously suggested by Yang et al. [54]. We begin by first defining the best response function @ RRd + R and its minimum 4 as follows,
Lyapunov function. To this end, we
4 (x)
max F)x,y), 4* min ((x) min max F(x,y). yER
XE
xER* yeRdy
Assumption ensures that & is well defined and the existence of a global minimax point guarantees that & is finite. Subsequently, for any À > O, we define the Lyapunov function Va as
(x = [ - 4- + ({ - F(x,y)].
By definition of 4, VA is non-negative for any À O and V Vx(z) 0 if and only if z minimax point of F. Hence, we present our convergence proof's for AGDA-RR and AGDA-AS in terms of Vx.
Theorem 3 (Convergence AGDA-RR/AS), Let Assumptions 1, 3, and 4 hold and let 1 = 73/2 /243. Then, there exists step-size S 1/smpl such that for B = 1jo, AGDA-RR satisfies the following for 1/10 and any K 1:
(2 K [+))] Se K/actn3 Vx(za) + + cx 2 log" (V. (V (n2 = ÖŌe K/acon² + 1/nK32),
PinK22
where k. = max(4/m1 )/2) and c: > O is a constant independent of K. M2, o². Under the same
setting, AGDA--S satisfies the following (é O is constant independent of K. jn, 112 o²):
<e K/aaan Vx Vx PI + ČK 0 log" 2og (Vx(Z))) (Z,) =Ō(e K/s0on +1/K2),
VA K+ K+1 +
max T. T..T AK ER.,
M1K2
where 71, TK TK are the permutations chosen by the adversary.
Convergence Saddle Point: As demonstrated in Appendix E.4, the convergence guarantec of Theorem 3, which is presented in terms of VA. can be easily translated into an equivalent convergence guarantee in terms of dist(z, ) where Z" denotes the set of saddle points of F. In particular, Theorem implies the following convergence guarantee for AGDA-RR:
E d'dist(z K+1 .Z-)² Ō(e K/Snbn² 1/nk2),
as well as the following convergence rate for AGDA-AS:
dist(2 K+1 22,2 Ō(e K/Jose" + 1/k3),
max
ES,
Comparison with lower bounds: Strongly convex minimization is special case of 2PE. minimax optimization, since minimizing the strongly convex function f equivalent to minimax optimization of the 2PE function F(x,y) f(x) (y.)). In fact, the iterates of AGDA-RR for F are exactly

---

327
CP47
(a) GDA
(b) PPM
(c) AGDA
Figure 2: Relative distance the epoch iterates from the global minimax point (i.e. |2 - 12 2o
2 vs k). The solid lines are the average over 50 runs and the shaded regions are 95% confidence intervals. The y-axis of 3a is on a linear scale whereas that of 3b and 3c on a logarithmic scale.
that of GD with RR for f. Hence, the ((1/nk²²) lower bound for strongly convex minimization using GD with also applies to AGDA-RR. Thus our convergence rate for AGDA-RR nearly tight and matches the lower bound (modulo logarithmic factors) for K 730 log(n' K). Similarly, the Incremental Gradient version of AGDA is a special case of AGDA-AS with T1, Ti,.... TK * id and hence, AGDA-AS nearly tight and matches the (2(1 K2) lower bound (modulo logarithmic factors) for K 2 730n. log( K').
Comparison with stochastic AGDA: Similarly, the (((1nK)) lower bound of SGD with replacement also holds for the Stochastic AGDA algorithm [54], which samples the component functions with replacement and performs two-timescale alternating updates similar AGDA-RR. Hence, Theorem demonstrates that AGDA-RR provably outperforms stochastic AGDA when K > 730k log(n
Bounded iterate assumption Assumption 4 is also used in analyzing RR for PL function mini- mization [34]. In this setting, an alternative bounded iterate assumption, which assumes that all the iterates
x lie within a compact set, has also been used [1]. As shown Appendix E.2, our proof of Theorem 3 easily adapts to this assumption. In the absence of either assumption, Li et al. [28] use time-varying step-sizes to obtain asymptotic O(1/K* K²) rates for RR on PE (and more generally for KE) minimization.
5
Experiments
evaluate our theoretical results by benchmarking on finite-sum SC-SC quadratic minimax games. This class of problems appears in several applications such as reinforcement learning [11], robust regression, [12] and online learning [26]. The objective F and the components fi are given by:
F(x,y) = 1/n Σ [x(x,)) ((x.y)>>x770 1 x x Jy Tyy,
1=1
f(x,y) = = x"xxxxxx'xxx"
y uf'x viyy.
where A and C are strictly positive definite. We generate the components fi randomly, such that Ex u; = Em= V; and the expected singular values are larger than that of and C. This ensures that the bilinear coupling term x" By sufficiently strong, since a weak coupling practically reduces to quadratic minimization, which has already been investigated in prior works. Finally, to investigate how the presence nonconvex nonconcave components impacts convergence, few randomly chosen fi's are allowed to be nonconvex-nomcoocaav quadraties. For each algorithm analyzed the text, we benchmark sampling without replacement against uniform sampling by running each method for 100 epochs using constant step-sizes that selected independently for each method via grid search. Further details regarding the setup is discussed Appendix G.
We present our results in Figure 2, where we plot the relative distance of the epoch iterates from the minimax point, defined as 1z) -21122 12112//z0- 1//00-20 z² 2=1², averaged over independent runs. In agreement with theoretical findings, sampling without replacement consistently outperforms uniform sampling

---

300
CP47
(a) GDA
(b) PPM
(c) AGDA
Figure 3: Convergence of GDA, PPM and AGDA averaged over 20 random instances. Shaded regions
represent 95% confidence intervals.
across all three setups. Furthermore, to demonstrate our observations are not particular to one specific instance, we repeat the experiment for 20 independently sampled quadratic games, and for each instance, perform independent runs of each algorithm and plot the average relative distance of the epoch iterates from the minimax point. The results, presented in Figure 3, substantiates the superior convergence of sampling without replacement across multiple instances.
Conclusion
We derived near optimal convergence rates for several wiphout-replacement stochastic gradient algorithms for finite-sum minimax optimization, and demonstrated that they converge faster than algorithms that use uniform sampling. We considered two problem classes, strongly convex-strongly concave problems (generalized to unconstrained strongly monotone variational incqualities) and nonconvex- noncomvex-nonconcan nonconccve problems with two-sided PE. objectives. We also formally defined adversarial shuffling. where an attacker can control the order in which data points are supplied to the optimizer, and analyzed minimax optimization this regime. Interesting future directions include the analysis of inexact proximal point methods, more general function classes, and time-varying step-sizes.
Acknowledgements and Disclosure of Funding
Michael Muchlebach and Bernhard Schölkopf thank the German Research Foundation and the Branco Weiss Fellowship, administered ETH Zurich, for the generous support.
References
[1] K. Ahn, C. Yun, and S. Sra. SGD with shuffling: Optimal rates without component convexity and large epoch requirements. In Advances in Neural Information Processing Systems, 2020.
[2] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In Proceedings of the International Conference on Machine Learning, 2017.
[3] P. Bailey, G. Gidel, and G. Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Proceedings of the Conference on Learning Theory, 2020.
[4] Y. Bengio. Practical recommendations for gradient- based training of deep architectures. Neural Networks: Tricks the Trade: Second Edition, 2012.
[5] D. P. Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimiza- tion: A survey. Report LIDS 2848, Laboratory for Information and Decision Systems, MIT, 2011.
[6] Bose, Gidel, Berard, Cianflone, P. Vincent, S. Lacoste-Julien, and W. Hamilton. Adversarial example games. In Advances in Neural Information Processing Systems, 2020.
10

---

[7] L. Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the Symposium on Learning and Data Science, 2009.
[8] Q. Cai, M. Hong, Y. Chen, and Z. Wang. On the global convergence of imitation learning: A case for linear quadratic regulator. 10X1:4190,,3367, 2019.
[9] W. G. Cochran. Sampling Techniques. Wiley, 1977.
[10] C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the ACM SIGACT Symposium the Theory of Computing, 2021.
[11] S. S. Du, J. Chen, Li, L. Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation, In Proceedings of the International Conference on Machine Learning. 2017.
[12] L. El Ghaoui and H. Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 1997.
[13] Facchinei and J.-S. Pang. Finite-dimensional variational inequalities and complementarity problems. Springer Science & Business Media, 2007.
[14] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. Proceedings of the International Conference on Machine Learning, 2018.
[15] T. Fiez and L. Ratifff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference on Learning Representations, 2021.
[16] T. Fiez, L. Ratliff, E. Mazumdar, E. Faulkner, and A. Narang. Global convergence to local min- max equilibrium classes of nonconvex zero-sum games. In Advances in Neural Information Processing Systems, 2021.
[17] G. Gidel, R. Hemmat, M. Pezeshki, L. Priol, G. Huang, S. Lacoste-Julien, and I. Mitliagkas. Negative momentum for improved game dynamics. In Proceedings of the International Confer- ence on Artificial Intelligence and Statistics, 2019.
[18] J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, 2014.
[19] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[20] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. SGD: General analysis and improved rates. In Proceedings of the International Conference Machine Learning. 2019.
[21] M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 2019.
[22] M. Gürbüzbalaban, A. Ozdaglar, and A. Parrilo, Convergence rate of incremental gradient and incremental Newton methods. SIAM Journal on Optimization, 2019.
[23] Haochen and S. Sra. Random shuffling beats SGD after finite epochs. In Proceedings of the International Conference on Machine Learning, 2019.
[24] J. Ho and S. Ermon. Generative adversarial imitation learning. In Advances in Neural Informa- tion Processing Systems, 2016.
[25] Jain, D. Nagaraj, and Netrapalli. Making the last iterate of SGD information theoretically optimal. In Proceedings of the Conference on Learning Theory, 2019.
[26] W. Koolen, Malek, and P. L.. Bartlett. Efficient minimax strategies for square loss games. In Advances in Neural Information Processing Systems, 2014.

---

[27] Z. Lai and L.-H. Lim. Recht-Re noncommutative arithmetic- geometric mean conjecture is false. In Proceedings of the International Conference on Machine Learning, 2020.
[28] X. Li, A. Milzarek, and Qiu. Convergence of random reshuffling under the Kurdyka- Lojasiewicz inequality. arXiv:2110.04926,, 2021.
[29] T. Lin, C. Jin, and M. I. Jordan, On gradient descent ascent for nonconvex-coneavy minimax problems. In Proceedings of the International Conference on Machine Learning, 2020.
[30] M. Littman. Markov games framework for multi-agent reinforcement learning. In Proceed- ings of the International Conference on Machine Learning. 1994.
[31] N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In Advances in Newral Information Processing Systems, 2021.
[32] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant adversarial attacks. Proceedings of the International Conference on Learning Representations, 2018.
[33] C. Maheshwari, C.-Y. Chiu, E. Mazumdar, S. Sastry, and L. Ratliff. Zeroth-order methods for convex-concays minmax problems: applications to decision deeendeed risk minimization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022.
[34] K. Mishchenko, A. Khaled, and P. Richtárik. Random reshuffting: simple analysis with vast improvements. In Advances in Neural Information Processing Systems, 2020.
[35] K. Mishchenko, A. Khaled, and P. Richtárik. Proximal and federated random reshuffling. In Proceedings of the International Conference on Machine Learning, 2022.
[36] D. Nagaraj, P. Jain, and P. Netrapalli. SGD without replacement: smooth convex functions. In Proceedings of the International Conference Machine Learning, 2019.
sharper rates for general
[37] A. Nedic and D. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. In Proceedings of the IEEE Conference on Decision and Control, 1999.
[38] J. v. Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1944.
[39] L. M. Nguyen, Q. Tran-Dinh, D. T. Phan, P. H. Nguyen, and M. Dijk. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 2021.
[40] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving class of non- convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, 2019.
[41] A. Patrascu and I. Necoara. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. Journal of Machine Learning Research, 2018
[42] A. Rajeswaran, I. Mordatch, and V. Kumar. A game theoretic framework for model based reinforcement learning. In Proceedings of the International Conference on Machine Learning. 2020.
[43] S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. In Proceedings of the International Conference on Machine Learning, 2020.
[44] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the International Conference on Machine Learning. 2012.
[45] B. Recht and C. Re. Toward a noncommutative arithmetic-geometrce mean inequality: Conjec- tures, case-studies, and consequences. In Proceedings of the Conference on Learning Theory, 2012.
12

---

[46] J. Rice. Mathematical Statistics and Data Analysis. Wadsworth, 1988.
[47] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal Control and Optimization, 1976.
[48] I. Safran and O. Shamir. How good is SGD with random shuffling? In Proceedings of the Conference Learning Theory, 2020.
[49] I. Safran and O. Shamir. Random shuffling beats SGD only after many epochs ill-conditioned problems. In Advances in Neural Information Processing Systems, 2021.
[50] G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang. Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 2010.
[51] I. Shumailov, Z. Shumaylov, D. Kazhdan, Y. Zhao, N. Papernot, M. A. Erdogdu, and R. J. Anderson. Manipulating SGD with data ordering attacks. In Advances in Neural Information Processing Systems, 2021.
[52] A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled ad- versarial training. In Proceedings of the International Conference on Learning Representations, 2018.
[53] T. H. Tran, L. M. Nguyen, and Q. Tran-Dinh. SMG: A shuffling gradient-based method with momentum. In Proceedings of the International Conference on Machine Learning, 2021.
[54] Yang, N. Kiyavash, and N. He. Global convergence and variance reduction for class of nonconvex-nonconcan minimax problems. In Advances in Neural Information Processing Systems, 2020.
[55] Y. Yu, T. Lin, E. Mazumdar, and I. Jordan. Fast distributionally robust learning with variance reduced min-max optimization. In Proceedings of the International Conference Artificial Intelligence and Statistics, 2022.
[56] C. Yun, S. Rajput, and S. Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022.
[57] G. Zhang, P. Poupart, and Y. Yu. Optimality and stability in non-convex smooth games. Journal of Machine Learning Research, 2022.
[58) K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Limitations such as structural assumptions on the function class and noise variance are clearly stated wherever appropriate.
(c) Did you discuss any potential negative societal impacts of your work? [No] The work is purely of a theoretical nature and analyzes existing algorithms that are already widely prevalent.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are stated in Sections 2, and 4.
(b) Did you include complete proofs of all theoretical results? [Yes] A proof sketch of the main result is presented in Section 3.2 while full proofs are deferred to the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] They are included the supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Key details are specified in Section 5 and further details are specified in the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All results reported with 95% confidence intervals. (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]. These details are provided in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "v6Eaewj9L15", "reviewer": "Reviewer_R12f", "summary": "This paper considers finite sum minimax optimization problems. The authors propose to use gradient descent ascent/proximal point method with RR and AS data sampling schemes. They obtain iteration complexity results for both strongly convex-strongly concave or 2PL functions, matching the state-of-the-art ones for minimization problems. ", "questions": "I have the following major concerns\n\n1. By checking the proof of Theorem 1, I can understand that the main difficulty (or let's say the main difference to the existing analysis of RR) lies in rewriting the GDA-RR update as a GDA form. The authors may highlight this difficulty clearly in the main context to show the technical difficulty as other parts are really similar to the existing RR analysis. \n\n2. Lemma B.3 is quite important for establishing the $O(1/nK^2)$ result. It fully utilizes the randomness of random shuffling in terms of expectation. However, such a lemma (as I know) was already used in [1, Lemma 1]. I would highly recommend the authors clearly state this reference in their Lemma B.3. Citing this existing lemma rather than reinventing it is also welcome. \n\n3. Is it possible to remove the bounded variance assumption in 2PL case? It seems that this assumption is removed for random shuffling algorithm in KL inequality setting (more general than PL as I know) in a recent paper [5]. \n\n4. In 2PL setting, is it possible to use dist$(z,Z^*)$ as the Lyapunov function, where $Z^*$ is the set of saddle points? If not, what is the underlying difficulty? \n\n5. The authors should give a more comprehensive literature review of the RR algorithm. Some immediately related references: 1) The very pioneering papers [2]-[3].  2) [4], which studies RR with momentum. 3) [5], which studies RR in KL inequality setting. 4) [6], which shows the limitation of RR under bad conditioning. 5) [7], which applies to federated learning setting. More related works are welcome. It is important to put this paper in the correct position in the literature. Potential comparisons between this paper and the existing literature will also be appreciated. \n\n[1] Mishchenko, K., Khaled, A., & Richtárik, P. (2020). Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 17309-17320.\n\n[2] Recht, B., & Ré, C. (2012, June). Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory (pp. 11-1). JMLR Workshop and Conference Proceedings.\n\n[3] Gürbüzbalaban, M., Ozdaglar, A., & Parrilo, P. (2015). Why Random Reshuffling Beats Stochastic Gradient Descent. arXiv preprint arXiv:1510.08560.\n\n[4] Tran, T. H., Nguyen, L. M., & Tran-Dinh, Q. (2020). SMG: A Shuffling Gradient-Based Method with Momentum. arXiv preprint arXiv:2011.11884.\n\n[5] Li, X., Milzarek, A., & Qiu, J. (2021). Convergence of random reshuffling under the kurdyka-{\\L} ojasiewicz inequality. arXiv preprint arXiv:2110.04926.\n\n[6] Safran, I., & Shamir, O. (2021). Random shuffling beats SGD only after many epochs on ill-conditioned problems. Advances in Neural Information Processing Systems, 34, 15151-15161.\n\n[7] Mishchenko, K., Khaled, A., & Richtárik, P. (2021). Proximal and federated random reshuffling. arXiv preprint arXiv:2102.06704.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-Strength\nThis paper provides (nearly) optimal expected iteration complexity bounds for both strongly convex-strongly concave or 2PL functions.\n\n-Weakness\nSee comments below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "hfFZuMurO_j", "reviewer": "Reviewer_4yKG", "summary": "The authors derive convergence rates for stochastic gradient algorithms for finite-sum minimax optimization *without replacement*. They consider both (1) the smooth and strongly convex-strongly concave setting, and (2) 2-sided Polyak-Lojasiewicz inequality setting. The rates are better than the convergence rates for the with-replacement algorithms and match known lower bounds (up to logarithmic factors) when the epoch number K is large (as a function of the condition number). Specifically, the authors show the following.\n\n* For convex-concave objectives, gradient descent ascent (GDA) as well as the proximal point method (PPM) achieve rates of $\\tilde O(\\sigma_*^2/(nK^2))$ for $K=\\Omega(\\kappa^2)$, where $K$ is the number of epochs, $\\sigma_*^2$ is the gradient variance, $n$ is the number of terms in the sum, and $\\kappa$ is the condition number.\n* For 2-sided PL objectives, similar results hold for $K=\\Omega(\\kappa^3)$.\n* The convergence rates are slowed by a factor of $n$ to $\\tilde O(\\sigma^2/K^2)$ when the data is adversarially shuffled, which is tight (up to log factors).\n\nThe proofs proceed by linearizing the update around the minimax point, then controlling the noise term using the variance of without-replacement sample means.\n", "questions": "Given that the same convergence rate is obtained for RR/SO, is there a reason to prefer one over the other?\n\nWhy do 2-sided PL objectives necessitate a different algorithm from convex-concave objectives?\n\nThe axes in Figure 3 are hard to read.\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors present a unified analysis of stochastic gradient algorithms for finite-sum minimax optimization without replacement, that works for many variants (GDA vs. PPM, random reshuffling vs. shuffle once vs. adversarial shuffling). The rates indeed show the benefit of sampling without replacement. The extension to adversarial shuffling is particularly interesting as it quantifies the effect of a data-ordering attack. The paper is clear and well-organized.\n\nThe results are not particularly surprising since they parallel the existing results for optimization, though it remains valuable to work out the results for minimax optimization.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RWSHDIxuoMA", "reviewer": "Reviewer_KJCr", "summary": "Authors analyze variants of stochastic gradient descent ascent (SGDA) methods without replacement to solve minimax first order optimization. Authors claim that, despite all the studies about stochastic methods with replacement, enforcing a pass over the whole set of data at each epoch is a better choice. This has first been shown empirically, and the reason why methods with replacement have been the center of interest is because of the underlying assumptions that ease the theoretical study.\nTherefore, methods without replacement lately received some interest, and first theoretical results arose for minimization problem.\nThis paper proposes a proof of the gain of speed of SGDA's convergence on minimax problems in the \"no replacement\" regime.\n\nThe different studied variations of the algorithm are:\n- the way to order data: reshuffling at each epoch, shuffling once for all, or ordering arbitrarily removing the stochasticity aspect of the algorithm;\n- the way to perform descent and ascent: simultaneously or not.\n\nThere are also 2 different studied setting. In both of them, the objective function (expressed as an average of \"component\" functions) is assumed smooth. The difference between the 2 settings lies in the assumption made on the component functions:\n- first, assuming that all component functions are strongly convex- strongly concave;\n- then, assuming that they verify a 2 sided PL inequality instead.\n\nAdditional assumptions are one of these:\n- bounded variance of gradients at optimum;\n- uniformly bounded variance of gradients.\n\nAuthors claim bounds improvements with respect to the \"with replacement\" case, and tight guarantees in their setting.", "questions": "- l.75: I think it is worth adding the word \"smooth\" as well. This is present in introduction, but it might be worth repeating it here in boldface as for the other assumptions. (Same in line 89)\n- l.199: typo \"comparison\".\n- l.254: typo \"regulators\".\n- l.674: here, we need to add the assumption of twice differentiability.\n- l.675: typo in index when defining $J_{\\tau_k(i)}$. The one that is defined might be useful for the proximal based method, but not the one studied here.\n- l.709: I suggest an intermediate line of computation here. Especially since the counter $j$ is reused for another sum. After first equality, the product is developed into a sum over some new counter $l$, then we can commute sum over $j$ and sum over $l$, and finally $j$ becomes $t_1$ merging the 2 last sums. But $l$ has been renamed $j$ which can be confusing.\n- l.714: there is a missing $n$ in the LHS.\n- l.719: There are a lot of loose inequalities here. Isn't there any way to take advantage of tighter inequalities? Getting a weaker constraint on $\\alpha$ for instance. It seems that the only gain will be constant. But isn't it interesting optimizing them?\n- l.740: typo: the sum counter must go up to $n$.", "limitations": "The only limitations are the assumptions which are clearly stated.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- this paper brings new results of convergence and theoretical support of observed phenomenons.\n- Moreover, guarantees are obtained under very weak assumptions and for various variants, even in adversarial setting.\n- Finally, results are well presented and literature review is extensive although I cannot be sure if exhaustive as I am not very familiar with minimax related literature.\n\nWeakness:\nI noticed unclear statements related on O usage. This notation has a precise mathematical meaning, namely $a_n = O(b_n)$ when there exists a constant $C$ such that $a_n \\leq C b_n$ holds for all $n$. Therefore, we have to be clear which variables are varying and which are fixed. In this paper, several variables are introduced and guaranteed bounds depend on $l$, $\\mu$, $n$, $K$, $\\sigma$ (or $\\sigma_*$) and $\\|z_0 - z^* \\|$. One has to be clear using the O notation which of these are considered as fixed by the problem and which are varying in the O.\nFor instance, when looking at results of Thm 1 which are summed up in line 79 of the introduction, since $\\mu, l$ disappeared from the second term and $\\|z_0 - z^*\\|$ from the first one, we can conclude that they are considered as constants of the problem, that are fixed at first and only the other variables can vary up to infinity.\nTo be clear, I also assume that $\\sigma$ is fixed when I read some O(1/nK^2) in line 68 for example.\nBut I cannot know from this article whether we are interested by asymptotical behavior of the rate when $K$ tends to infinity, or also when $n$ grows:\n- If $n$ is a fixed constant of the problem, therefore, O(1/nK^2) = O(1/K^2) and all the discussion about having this $n$ or not depending on the adversarial setting or not has to be done on the accurate bound, not using the O notation.\n- If we are interested in the variation of $n$, I don't agree on the fact that $exp(-K / 5\\kappa^2) + \\sigma_*^2/nK^2 = O(1/nK^2)$. Indeed, if we fix $K$ and make $n$ tends to infinity, the RHS tends to 0 but not the LHS, which makes the domination of the LHS by the RHS impossible. Authors specifically asked that $K = \\Omega(\\kappa^2)$, but first, this assumption does not have any impact on the O notation as $\\kappa$ is fixed, and moreover, we can rewrite $exp(-K / 5\\kappa^2) + \\sigma_*^2/nK^2 = 1/K^2 [ K^2 exp(-K / 5\\kappa^2) + \\sigma_*^2/n ]$ and bound the term into brackets. Its maximum is reached for $K = 10 \\kappa^2$ and leads to $100\\kappa^4 exp(-2) + \\sigma_*^2/n $, which is not a $O(1/n)$ if $n$ is not a $O(1)$. This is a $O(1)$ and leads to a $O(1/K^2)$ rate, not $O(1/nK^2)$.\nAnd this can never change with additional assumption of the form $K = \\Omega(\\kappa^{\\{\\text{some exponent}\\}})$. One would need to enforce a relation between $K$ and $n$ in order to expect an improvement. For example, with $K \\geq 5\\kappa^2 (1 + \\varepsilon) log(n)$ for any $\\varepsilon>0$, the statement comes true.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EKoV0tupZ-N", "reviewer": "Reviewer_b3Wj", "summary": "The paper shows the convergence of stochastic GDA with random reshuffling (RR), shuffle once (SO) and adversarial shuffling (AS) for strongly-convex-strongly-concave min-max problems. It also extends to the two-sided PL condition with alternating GDA. ", "questions": "Questions:\n\n(a) PPM has an implicit step. Extragradient and PPM are always considered closely related. Is it possibly to extend to extragradient with RR? Usually PPM allows large stepsize (arbitrary large in deterministic setting) for convex optimization. Does it allow larger stepsize for PPM here?\n\n(b) What is the technical novelty compared to RR in minimization?\n\nminor comments:\n\n(a) I suggest to include $\\kappa$ for the 1/K^2 terms in the contribution part. \n\n(b) I suggest to use $\\Vert \\cdot \\Vert$ for norm\n", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength: the paper is easy to follow and well-organized. \n\nweakness: the techniques for RR has already been established for strongly-convex optimization. It is not surprising to extend it to strongly-convex-strongly-concave minmax problems. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept