Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization
Authors: Liang Zhang
Junchi YANG
Amin Karbasi
Niao He
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Reproducibility
Convex Optimization
Minimax Optimization
Saddle-Point Problem

Abstract: Algorithmic reproducibility measures the deviation in outputs of machine learning algorithms upon minor changes in the training process. Previous work suggests that first-order methods would need to trade-off convergence rate (gradient complexity) for better reproducibility. In this work, we challenge this perception and demonstrate that both optimal reproducibility and near-optimal convergence guarantees can be achieved for smooth convex minimization and smooth convex-concave minimax problems under various error-prone oracle settings. Particularly, given the inexact initialization oracle, our regularization-based algorithms achieve the best of both worlds -- optimal reproducibility and near-optimal gradient complexity -- for minimization and minimax optimization. With the inexact gradient oracle, the near-optimal guarantees also hold for minimax optimization. Additionally, with the stochastic gradient oracle, we show that stochastic gradient descent ascent is optimal in terms of both reproducibility and gradient complexity. We believe our results contribute to an enhanced understanding of the reproducibility-convergence trade-off in the context of convex optimization.

Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization
Liang Zhang"
Junchi Yang"
ETH Zurich & Max Planck Institute liang. zhang@inf. ethz. ch
ETH Zurich junchi yang@inf. weceeiinfehhh...mmmmm ethz. ch
Amin Karbasi
Niao He
Yale University & Google Research amin, carbasi@yale..o. edu
ETH Zurich
niao. aco.neeinf... .ethz. ch
Abstract
Algorithmic reproducibility measures the deviation in outputs of machine learning algorithms upon minor changes in the training process. Previous work suggests that first-order methods would need to trade-off convergence rate (gradient complexity) for better reproducibility. In this work, challenge this perception and demon- strate that both optimal reproducibility and near-optimal convergence guarantees be achieved for smooth convex minimization and smooth convex-concave minimax problems under various error- error-prone oracle settings. Particularly, given the inexact initialization oracle, regularization-Be based algorithms achieve the best of both worlds - optimal reproducibility and near-optimal gradient complexity for minimization and minimax optimization. With the inexact gradient oracle, the near-optimal guarantees also hold for minimax optimization. Additionally, with the stochastic gradient oracle, we show that stochastic gradient descent ascent is optimal in terms of both reproducibility and gradient complexity. We believe our results contribute to an enhanced understanding the reproducibilityccovveeg trade-off in the context of convex optimization.
Introduction
In the realm of machine learning, improving model performance remains a primary focus; however, this alone falls short when comes to the practical deployment of algorithms. There has been a growing emphasis on the development of machine learning systems that prioritize trustworthiness and reliability. Central to this pursuit is the concept of reproducibility [38] (64. which requires algorithms yield consistent outputs, in the face of minor changes to the training environment. Unfortunately,
lack of reproducibility has been reported across various domains [TO 40
41 (64), posing significant
challenges the integrity and dependability of scientific research. Notably, empirical studies in Henderson et al. [43) have revealed that reproducing baseline algorithms in reinforcement learning formidable task due both inherent sources (c.g., random seeds, environment properties) and external sources (e.g., hyperparameters, codebases) of non-determinism These findings underscore the criticality of having access to the relevant code and data, as well sufficient documentation of experimental details, to ensure reproducibility in machine learning algorithms.
Instead of considering the irreproducibility issue solely from an empirical perspective, Ahn al. initiated the theoretical study of reproducibility in machine learning as an inherent characteristic of the algorithms themselves. They focus first-order algorithms for convex minimization problems and
Equual Contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Algorithmic reproducibility (Def. 3 and gradient complexity for algorithms in the smooth convex minimization setting given inexact deterministic oracles (Def. D Here, "LB" stands for lower-bound and a A b denotes min(a, b). For the inexact gradient oracle, 6 - O(c) is required for GD to be e-optimal and ā I O(e%/4 is required for Algo.
Inexact Initialization
Inexact Gradient
Algorithm
Convergence
Reproducibility
Convergence
Reproducibility
GD
0(1/c)
0(83)
0(1(c)
0(8%(2)
AGD
0(1VV)
0(822119)
Algo.
(Thm.
3.3
3.5
Ó(1/V)
O(82)
Ó(1/V7)
(
LB 61
((1/VE)
12(02) 2(1/VE) 52(62/e2)
define reproducibility as the deviation outputs of independent runs of the algorithms, accounting for sources of irreroduuibility captured by inexact or noisy oracles. In particular, they consider three practical error-prone operations, including inexact initialization, inexact gradient computation due to numerical errors, and stochastic gradient computation due to sampling or shuffling. When restricting the outputs to be e-optimal and assuming the level of inexactness that could cause irreproducibility is bounded by 8, they establish both lower and upper reproducibility bounds of (stochastic) gradient descent for all three settings. The lower-bounds indicate the existence of intrinsic irreproducibility for any first-order algorithms, while the matching upper-bounds suggest that (stochastic) gradient descent already achieves optimal reproducibility.
An important question arises regarding whether there is a fundamental trade-off between repro- ducibility and convergence speed algorithms. For example, the case of inexact initialization, the optimally reproducible algorithm [1, gradient descent (GD), is known to be strictly sub-optimal in terms of gradient complexity for smooth convex minimization problems [61]. On the other hand, the optimally convergent algorithm, Nesterov's accelerated gradient descent (AGD) 660,, suffers from worse reproducibility bound [6]. The situation becomes more intricate in the case of inexact gradient computation. A natural question that we aim to address in this paper is: Can we achieve the best of both worlds- optimal convergence and reproducibility?
On another front, while minimization problems can effectively model and explain the behavior of many traditional machine learning systems, recent years have witnessed surge of applications that are formulated as minimax optimization problems. Important examples include generative adversarial networks (GANs) 377, robust optimization (54), and reinforcement learning (25). Despite a wealth of convergence theory for various minimax optimization algorithms, extensive empirical evidence suggests that these algorithms can be hard to train in practice [67 4 [33: the training procedure can be very unstable (23) and highly sensitive to changes of hyper-parameters. Motivated by such issues, we initiate the theoretical study of algorithmic reproducibility in minimax optimization. The second question that we aim address in this paper is: What the fundamental limits of reproducibility for minimax optimization algorithms and their convergence- reproducibility trade-offs? We will focus on smooth convex-concane minimax optimization convergene--eprroduibbbbii first step, where the irteproducibility issue comes from either inexact initialization, inexact gradient computation, or stochastic gradient computation.
1.1 Our Contributions
Our main contributions are two-fold:
First, we propose Algorithm [ which solves regularized version of the smooth convex minimization problem. This algorithm achieves both optimal algorithmic reproducibility of (82)) and near optimal gradient complexity of D(1/ve] under the 5-inexact initialization oracle. Table provides comparison with GD and AGD. Our results rely on the key observation that solutions to strongly-
Throouhoout the paper, Ô hides additional logarithmic factors. We claim netr-optimality of the result when it is optimal up to logarithmic terms.

---

Table 2: Algorithmic reproducibility (Def. 6 and gradient complexity for algorithms in the smooth convex-concave minimax setting given inexact deterministic oracles (Def. + Here, "LB" stands for lower-bound and a A denotes min(a,
a, b). For the inexact gradient oracle, à < O(c) is required for
GDA, EG, and Algo. to be c-optimal, and ò I O(e²)
) is required for Algo. The diameter D in
Assumption 4.1 is trivial upper-bound
bound for reproducibility in all cases.
Inexact Initialization
Inexact Gradient
Algorithm
Convergence
Reproducibility
Convergence
Reproducibility
GDA (Thm. 4.2
o(1/²)
O
o(1/e)
0(83/2)
EG (Thm. 4.3
((1/c)
0 A (82 + 1/2))
O(1/e)
0 A 11/22)
Algo.
2
(Thm. 4.4
4.6
((1/e)
O(82)
((Le))
0(82/e2
Algo.
3
(Thm. 4.7
4.8
Õ(L/E)
0(69)
((1e))
0(6%/²)
LB
663
Lem.
B.3
2(1/e)
((62))
221/e)
1266//2)
convex regularized problems are unique, allowing algorithms that converge close to the minimizers to be reproducible. This highlights the effectiveness of regularization in achieving near-optimal convergence without compromising reproducibility.
Second, we extend the notion of reproducibility to smooth convex-concave minimax optimization ! under inexact initialization and inexact gradient oracles. We establish the first reproducibility analysis for commonly-use minimax optimization algorithms such as gradient descent ascent (GDA) and Extragradient (EG) 48 Our results indicate that they either sub-optimal in terms of convergence or reproducibility. To address this, we propose two new algorithms (Algorithm algooithm@aand]] and 3 which utilize regularization techniques achieve optimal algorithmic reproducibility and near-optimal gradient complexity. The summarized results are presented in Table 2 Additional numerical experiments showcasing the effectiveness of our algorithms can be found in Appendix [ Although smooth convex- concave minimax optimization is nonsmooth in its primal form, our results indicate an improved reproducibility compared to the result of general nonsmooth convex problems [T] by leveraging the additional minimax structure. Lastly, in the case of stochastic gradient oracle, we show stochastic GDA can simultancously attain both optimal convergence and optimal reproducibility.
1.2 Related Works
(Reproducibility) Previous works that study reproducibility in machine learning are mostly on the empirical side. They either conduct experiments to report irreproducibility issues in
Related Notions.
the community 440 43 18 64), or propose practical tricks to improve reproducibility [69 77 56 19].
Ahn et al. initiated the theoretical study of reproducibility in convex minimization problems as a property of the algorithm itself. (Replicability) In an independent work, Impagliazzo et al. 45 proposed the notion of replicability statistical learning, where an algorithm is replicable if its outputs on two i.i.d. datasets are exactly the same with high probability. Its connection to generalization and differential privacy [29] established in Bun et al. (1 and Kalavasis et al. [47 Replicable algorithms are proposed in the context of stochastic bandits
100 and clustering [3
(Stability) Depending on the context, the term stability may have different meanings. In empirical studies 4 (2] instability often refers issues such oscillations failure converge during training. In learning theory, algorithmic stability 17 measures the deviation in an algorithm's outputs for finite-sum problems when single item in the input dataset is replaced by an i.i.d. in-distribution sample. The concept receives increasing attention as it implies dimension- inpennioonindependenn generalization bounds of gradient-basee based methods for both minimization [42
[] 6 and minimax [33 49 [6]
problems. the area of differential equations [13] and variational inequalities [32]. stability is also
examined as a property of the solution set in response perturbations in the problem conditions.
In this work, we consider the notion of reproducibility that characterizes the behavior algorithms
upon slight perturbations in the training. We defer the task of establishing intrinsic connections
3

---

among related notions to future work. The most closely related concept is algorithmic stability, where the analysis is similar to reproducibility under the inexact deterministic gradient oracle. Attia and Koren [ showed the stability of AGI (60) grows exponentially with the number of iterations. Later, this is improved to quadratic dependence 7 based on a similar idea as ours that leverages stability of solutions to strongly-convex minimization problems [68] [4]. However, since there is no inexactness of the gradients in their setting, it is possible to ensure outputs that are arbitrarily close to the optimal solution. Given the presence of inexact gradients in our case, the convergence is only limited to a neighborhood of the optimal solution, which makes the problem more challenging. The trade-off between stability and convergence was investigated in Chen et al. [24). Their results suggest that a faster algorithm has to be less stable, and vice versa. However, we show the feasibility
of achieving both optimal reproducibility and near-optimal convergence simultaneously in the setting we considered.
Minimax Optimization. Existing literature on minimax optimization primarily focuses on con- vergence analysis across various settings. For instance, there are studies on the strongly-convex- strongly-concave case 57), convex-concave case (59 [3] and (incoovex((srrongyyycomm
case (52 [7]. The lower complexity bounds have also been established for these settings [80] (50 (77).
Our work aims design reproducible algorithms while maintaining the optimal oracle complexities achieved in these previous works.
Inexact Gradient Oracles. series of works investigate the convergence properties of first-order methods under deterministic inexact oracles for minimization 26 27 28 and minimax [70] problems. However, their inexact oracles differ from ours, and our focus more on reproducibility. In recent years, there has been increasing interest in studying biased stochastic gradient oracles as well, where the bias arises from various sources such as problem structure [44], compression [14] or Byzantine failure [15] in distributed learning, and tradient-free optimization [62]. These biases can also contribute to irreproducibility, and this direction would be an interesting avenue of research.
Regularization Technique. The central algorithmic insight driving improvements towards obtaining both optimal convergence and reproducibility is the regularization technique, which is commonly used in the optimization literature. One important use case is boost convergence by leveraging known and good convergence properties of algorithms on smooth strongly-convex functions for solving convex and nonsmooth problems, see e.g., [5T] 3 74], just to name few. In addition, the regularization technique has also been demonstrated to be use ful in improving stability and generalization (76 77 enhancing sensitivity and privacy guarantees 34 78 etc. In this paper, we
provide another important use case by showing an improved convergene--eprroducibii trade-off.
2 Preliminaries in Algorithmic Reproducibility
Notation. We use ||||| to represent the Euclidean norm. Ie(z) denotes the projection of x onto
the set C. A function h :: S + R is f-smooth if it is differentiable and its gradient Vh satisfies
[[Vh(z)) Vh(x2)]| < El|ar] - v2l for any 21, 22 in the domain S E Rdd A function g S + IR convex if g(0r) + (1 a))22) S ag(z1) ) + (1 ())((z))) for any a E [0, 1] and x1, E S. If
satisfies ((x) (f/ |>=1| being convex with j >> O, then it is p-strongly-conver Similarly, a
function g : S + ER concave if -g convex, and p-strongly-coneave if -g is p-strongly-conver
Ahn et al. I studied the algorithmic reproducibility for convex minimization problems minzex F F(x). measured by the (e, d) -deviation bound of an algorithm A. Here, ö denotes the size of errors in the oracles that can lead to different outputs in independent runs of the same algorithm. The notion of reproducibility also requires A to produce c-optimal solutions, avoiding trivial outputs.
Definition 1. Three different inexact oracle models are considered: (i) a d-inexact initialization oracle that returns a starting point xo E X such that ||zz - uol 2 < 8²/4 for some reference point My E X. (ii) 8-inexact deterministic gradient orucle that returns an inexact gradient G(x) such that [[VF(=)= - G(z)]12 < 82 for the true gradient VF(z), (dit) a 8 d-inexact stochastic gradient oracle that returns unbiased gradient estimate fz(x; {) such that E fx: {) VF < 8
Definition 2. A point á E X is an e-pttmal solution if F(t) minzex F(x:) S in the deterministic setting, or TE [+)) mingex F(x)= S in the stochastic setting, where the expectation taken over all the randomness in the gradient oracle and in the algorithm that outputs &.

---

Definition 3. The (e, devviaiin || 2112 is used to measure the reproducibility of an algorithm A with e-optimal solutions & and F', where è and E' are outputs of two independent runs of the algorithm A given d-inexact oracle in Definition [
We expand the definitions of reproducibility to encompass minimax optimization problems:
min max F(z,y). xE yEy
Our goal is to find the saddle point (x" 3/") of the function F(x. y). such that F(x", y) S F(x" I F(x,y") holds for all (x,y) E X y. The optimality of a point (#, ÿ) can be assessed by its duality gap, defined as m F(2, y) minzex F(z, 9). In the minimax setting, we analyze reproducibility under the following inexact oracle models.
(i) a 6- 6-inexact initialization |1y/ - -vol2 I 8² /4 for some reference point (uo, Ho) E X x V, (iz) a 8-inexact deterministic gradient oracle that returns an inexact gradient G(z,3) = (2; y), Gz 3)) at any querying point (x,y) E X x y such that F y) G(z, y)ll S 8 for the true gradient VF y) = (V, y). FzF(z, y)), (iii) a 5-inexact stochastic gradient oracle that returns an unbiased gradient estimate V far, (V, [V,f(z: (z, y: E), fz y: E)) such that Eg f g) VF y) S 8².
Definition 4. Three different inexact oracle models are considered:
oracle that returns a starting point (Io, yo) E X' x y such that I|z0 - - +
Definition 5. point (át 1) E X x Y is e-saddle point solution if its duality gap satisfies that
max F y) mingex F(x, 9) I in the deterministic setting, or its weak duality gap satisfies that maxyey EE [F (2. y)] minzex B[F (z, 0)] S in the stochastic setting.
Definition 6. The (e, -dvvviiano ||0 2' + || 1/'1 is used to measure the reproducibility of an algorithm A with e-saddle points (2. 8) and g') where (á, 9) and (#' f/) are outputs of two independent runs of the algorithm A given 6-inexact oracle in Definition
The optimal convergence rates are well-understood for the convex optimization problems, including convex minimization [6] and convex-concave minimax optimization 663. Ahn et al. (1 provided the theoretical lower-bounds of reproducibility for convex minimization problems, which can be extended to convex-concave minimax problems well (Lemma B.3). We say an algorithm achieves optimal reproducibility if its reproducibility upper-bounds match the established theoretical lower-bounds.
3 Deterministic Gradient Oracle for Minimization Problems
In this section, we consider convex minimization problems of the form
min xEX
F(z),
where X' is convex and closed set. We focus on the standard smooth and convex setting as detailed in Assumption Our goal is to find an c-optimal point as in Definition Ahn et al. M showed that the optimal convergence rate and reproducibility can be achieved at the same time using stochastic gradient descent (SGD) for the stochastic gradient oracle model. In the deterministic case, they showed GD achieves the optimal reproducibility, albeit with a sub-optimal convergence rate [1). Considering the instability of accelerated gradient descent (AGD) (26 28 6). Ahn et al. M conjectured that ((1/e) gradient complexity is necessary to attain the optimal reproducibility.
Assumption 3.1. The function F is convex and t-smooth. We have access to initial points zo that are D-close to an optimal solution, ie.,, -|-- - xoll² < D)2 for some x² E arg minzex F(x).
We introduce a generic algorithmic framework outlined in Algorithm I that solves a quadratically regularized auxiliary problem (+) using base algorithm A with initialization zg until an accuracy of e, is reached. Our key insight is that since the optimal solution for strongly convex problems is unique, the reproducibility of the outputs from the regularized problem can be easily guaranteed. Note that the regularization parameter r' presents a trade-offt as r increases, the auxiliary problem can be solved more efficiently, but the obtained solution deviates further from the original solution.
We will show that Algorithm [ acchevess a near-optimal complexity of ((1/ve), along with optimal reproducibility under an inexact initialization oracle and slightly sub-optimal reproducibility under an inexact deterministic gradient oracle. This finding disproves the conjecture I that 2( /e) complexity is necessary to achieve optimal reproducibility.
5

---

Algorithm 1 Reproducible Algorithmic Framework for Convex Minimization Problems
Input: Regularization parameter r > 0, accuracy c > O, base algorithm A. initial point zy E X. Apply A to approximately solve the r-stronglyyconnex and (E + r--smooth problem
24 f arg min (x) = F(x) + a| 20l??
(+)
DEA
such that the optimality gap
F+
min (x) S E zE
Output: Fy-
3.1 Inexact Initialization Oracle
We first examine the behavior of Algorithm [ with access exact deterministic gradients but given different initializations. Starting from two distinct initial points 2p and Tó such that ||00- 2/12 I 82, we want to control the deviation between the final outputs 2r and sr of the algorithm. The following contraction property is essential to attain optimal reproducibility.
Lemma 3.2. Let x, = arg minzex((((aa + (r/2)]l - xool3) and (xt) = arg min (F(x) + (r/2)][= - =) When F is convex, it holds that || (xxt) 2 < 1 2all? for any r >> 0.
This indicates the optimal solutions are reproducible up to 8 Consequently, if we can solve the auxiliary problem (*) to a high accuracy E,, we can ensure the final output o, is reproducible. The selection of exhibits trade-off: smaller value increases complexity, yet brings the output closer to the reproducible x;. We characterize the complexity and reproducibility of Algorithm by carefully choosing the parameters and 6,,
Theorem 3.3. Under Assumption 3.1 Aand given an inexact initialization oracle, Algorithm 7 with r c/c G, (c/2) min(1, 8² (4D))} and AGD (6T] as base algorithum A outputs an c-optimal point x, with (EED2T)) gradient complexity, and the reproducibility is || x4 1 < 482.
This theorem implies that we can simultaneously achieve the near-optimal complexity of VVD/ and optimal reproducibility of (8²), which improves over the O /e) complexity of GD 0. In fact, when combined with any base algorithm that solves the auxiliary problem, Algorithm | attains optimal reproducibility. However, using AGD as the base algorithm results in the best complexity. To the best of our knowledge, this is the only algorithm capable of achieving the best of both worlds. Previously, Attia and Koren 66) proved that the algorithmic reproducibility (referred to as initialization stability in their study) of Nesterov's AGD is ((82g"vv*) when the initialization is o"-apart.
Remark 1. Adding regularization is a common and useful technique in the optimization literature. Our algorithmic framework solves one auxiliary regularized strongly-convex problem, which is referred to as classical regularization reduction in Allen-Zhu and Hazan 3 Algorithm Iis biased and requires the knowledge of and D to control the biased term introduced by the regularization term. The convergence guarantee also has an additional sub-optimal logarithmic term. Allen-Zhu algorithm, where sequence of auxiliary regularized
i
and Hazan (3] proposed to use double- strongly-convex problems with decreasing regularization parameters are solved. The vanishing regularization ensures the algorithm is unbiased, and the resulting convergence guarantee requires no knowledge of c and does not have an additional logarithmic term. Similar idea could apply to our case as well, and the task of bridging such gaps is deferred to future work.
3.2 Inexact Deterministic Gradient Oracle
We further study the algorithmic reproducibility and gradient complexity of Algorithm I under the inexact gradient oracle model that returns an inexact gradient G(z) E B such that GG(x) V F(x))] S 52 at any query point E X. From the inexact gradient oracle of F, we can construct an inexact gradient oracle for the auxiliary problem F,: G. = G(x) + r(x - zn) which satisfies the condition (x) (=)))) = [[G(z) F2 < 82 To solve the auxiliary problem, we consider AGD with an inexact oracle (Inexact-AGD) as proposed by Devolder et al. 27]. The
proposition below establishes its convergence behavior.

---

Proposition 3,4. Consider mingex Fr(2), where F, is r-ssrrongly-coover and (E ((r)) smooth. Given an inexact gradient oracle that returns G,(x) such that [|,,(z) (x) < 62, starting from
Yo To, AGD with the following update rule
1
J++1 =Ixx
111
2( rr)
(Inexact-AGD)
96+1 = x++1 + 2 Vr|(e+
(0 - -x,),
+ vr/(e+r)
-T - for 0,1, ,
L, satisfies that
T r
28 (2] 1 +2++
)
Fx(T))FF(x)) S exp
(F((0)) - Fx(x;) +
4 -11000 x;1 +V T (etr
+
2 2
where n is the unique minimizer of (x).
This proposition suggests that Inexact- converges to a neighborhood with a radius of O / //2)
around the optimal value. We note that convergence to the exact solution is unattainable for algorithms employing inexact gradients [27 (28) and the size of this neighborhood is important in determining the reproducibility of dr.
Theorem 3.5. Under Assumption oracle in Desimition Algorithm base algorithm outputs (68² D (2e") + + point I, with ((VED=/e gradient complexity, and the reproducibility is - x,,1² < (662/6/3))
3 with 0 < < eSSDD LD2 and given an inexact deterministic gradient with r = </D², e, = 682 6D2D3 (2)(2 and Inexact-AGD as
Ahn et al. ① showed that GD achieves optimal reproducibility of (882/22) and complexity of (1/ec) when S O(t). Our results indicate that reproducibility of O (6/2)/5/2) and a near-optimal complexity of ((1/Ve) can be attained when s O(E3/4). We conjecture that this suboptimal reproducibility bound is inevitable for the proposed framework given the lower bound result in Devolder et al. (27) for algorithms under a (6, e, p)-inexact oracle associated with E-smooth μu- strongly-conven functions. Further discussions are provided in Appendix A.2] Moreover, we point out that for minimizing E-smooth and p-strongly-convex functions, Proposition 3.4jaaradyy implies that Inexact-AGD attains the optimal reproducibility of O(min <}) and the optimal complexity of Ö(VE/n E/j) when the problem well-conditioned. improving over the (l/p)) complexity in the previous work MI.
Remark 2. In Appendix D we demonstrate the effectiveness of Algorithm T on quadratic mini- mization problem equipped with an inexact gradient oracle. The results are plotted in Figure in the appendix. We observe that the reproducibility can be greatly improved when adding regularization, with only a small degradation in the convergence performance.
4 Deterministic Gradient Oracle for Minimax Problems
In this section, we address the minimax optimization problem of the form
min max F(x, y): zE yEy
where X and y are convex compact sets. We focus on the standard smooth and convex-concave setting as detailed in Assumption 4.1 We aim find an e-saddle point (át, 9) such that its duality gap satisfies max F(2,g) y) - m F(z g) S e. Here, the assumption that the domains are convex and bounded ensures the existence of the saddle point when the objective convex-coneave [73] We focus on minimax problems equipped with inexact initialization oracles and inexact deterministic gradient oracles as defined in Definition We first show that two classical algorithms, gradient descent ascent (GDA) and Extragradient (EG) 48 (22, are either sub-optimal in convergence or sub- optimal in reproducibility, which mirrors the minimization setting. Based on the same regularization idea, we propose two new frameworks in Algorithm 2 and 3 that successfully attain near-optimal convergence and optimal reproducibility at the same time.
Assumption 4.1. For all y E y, F(.,)) yy is convex, and for all E X, F(x,))
.) is concave. Furthermore, F is t-smooth on the domain x ). Additionally, both X and y have diameter of D. This means that || 22 2 < D2 and || 22ll2 < D2 for all 21, E X and yı, 1/2 y
7

---

The optimal gradient complexity to find e-saddle point under such assumptions is (1/cc) [63]. Since the minimax problem reduces minimization problem on X' when the domain y is restricted to be a singleton, the reproducibility lower-bounds []] for smooth convex minimization hold as lower-bounds for smooth convex-concan minimax optimization as well. That is, (2())) under the inexact initialization oracle, and (2(82/<²) under the inexact gradient oracle (see Lemma B.3) We now present the convergence rate and reproducibility bounds of GDA (see Algorithm and EG (see Algorithm 5)
the average iterate (ĀT. Ur) output by GDA with stepsize 1/(VVT) after T (1/22) iterations is an c-saddle point. Furthermore, the reproducibility of the output is (i) O(82) under d-inexact initialization oracle; (ti) 0(82/67) under d-inexact deterministic gradient oracle if S (e)).
Theorem 4.2. (GDA) Under Assumption 4.1
Theorem 4.3. (Extragradient) Under Assumption 4.1 the average iterate 20r+1/2:0r+1/// output
by EG with stepsize 1ff after T = O(/e)) iterations is an e-saddle point. Furthermore, the reproducibility of this output is (i) (mmnn602et) , +11+/. +/6,, D²)) under ~-inexact initialization oracle; (fi) (minn(8ee)) ,1/2, D²}) under 5-inexact deterministic gradient oracle if Σ O(c)-
While GDA can achieve optimal reproducibilityy it converges with a sub-optimal complexity of (L)/2). On the other hand, EG achieves an optimal (1/e) complexity but is not optimally reproducible. Further details on this are provided in Appendix B In Appendix [B3.4] we also demonstrate that EG, through an alternative parameter selection, can achieve optimal reproducibility sub-optimal rate (11/e//2). The question that remains open is how to simultaneously attain both optimal reproducibility and gradient complexity. To address this, we have developed two algorithmic frameworks with near-optimal guarantees, one based regularization and the other based on proximal point methods 666 12]
4.1 Regularization Helps!
Algorithm 2 Reproducible Algorithmic Framework for Convex-Concave Minimax Problems
Input: Regularization parameter 0, accuracy e, > O, base algorithm A, initialization (xo. Mo). Apply A to inexactly solve the --strooll--oovvex-ttoorlyyyooooe
and (6 + r)-smooth problem
(Er, + min max (x, == F(x, v) = xoll2 ZEX vEy
_ 1ly 3o113
2
such that V(z, y) E X x V,
V2Fr Ur) (α, - x) VyFr(ar:)t)) Torr y) S ex.
(2)
Output: (Ir. U+).
We demonstrate that adding regularization is sufficient to achieve near-optimal guarantees for smooth minimax problems. The general framework is summarized in Algorithm 2 where a base algorithm A is applied to solve regularized auxiliary problem which is strongly- convexx in and strongly-concawe in y. For the inexact initialization case, we show that an optimal reproducibility bound of (822) and a near-optimal convergence rate of ((1/c) can be attained simultaneously.
Theorem 4.4. Under Assumption 4.1 And given an inexact initialization oracle, Algorithm witt r r= =eD e, = e. minn1, 62 /(8D))) and EG as buse algorithm A outputs a (2e) -aaddd point (I,, Mr) with Ō(EL²/E) gradient
gradieen complexity, and the reproducibility is 482.
Consider a 8-inexact deterministic gradient oracle that returns G(æ,, v) = (G (x, y), Gz(r, y)). First note (z, .) = (G, +r(x -xo)) Gy (Ir, y) -r(y- yo)) is d-inexact gradient for the auxiliary problem R We now characterize the convergence behavior of EG with this d-inexact gradient oracle, referred as Inexact-EG to solve the auxiliary problem.
Lemma 4.5. Consider mingex maxzey Fr y). where F, y) is cerronglycoovve-sstoon
concave and (E + r-)smotth. Given an inexact gradient oracle that returns G, v) such that [I, (x, y) < 82, Inexact-EB EG with stepsize 1/(2(E + r)) satisfies
T r
(1120- - 21 + 1l300 - 3r,12) + 882 2
r E+r + ! :
||> - 112 + l/rr - 1 < exp
(88
8

---

where (27, v.) is the unique saddle point of (r
This lemma implies that Inexact-EG converges linearly to a neighborhood of size (622/²2) around the saddle point, which can be translated to the inaccuracy measure in (2) with e, (6/rr) utilizing
Lemma C.5 It is worth emphasizing that the size of this neighhorhood is critical for achieving
optimal reproducibility, and the dependency on in the above convergence rate is key for attaining
near-optimal complexity. Stonyakin et al. [70] analyzed Mirror-Prox [59] with restarts for strongly-
monotone variational inequalities under different inexact oracle (see Devolder et al. [27 and 770
Example 6.1] for its relationship with the inexactness notion of ours), Compared to Inexact-EG, their two-loop structure of the restart scheme more complicated to implement.
Theorem 4.6. Under Assumption 4.1 with < c S LD2 and given an inexact gradient oracle, A with = =c/D², 4 = ( and Inexact-EG as base algorithm A outputs an (ee+)/c)- saddle point with ((ED2/e) /c) gradient complexity, and the reproducibility is O )
Remark 3. Some numerical experiments on a bilinear matrix game with inexact gradient information are provided in Appendix [ regularized framework in Algorithm A efffetiively improves the reproducibility of the base algorithm.
(see Figure 2}. With a small degradation in the convergence speed, the
The theorem indicates that optimal reproducibility O and near-optimal gradient complexity (L/cc) can be achieved when 8 S {EE)). Note by Theorem 4.2 and 4.3 GDA and EG can find e-saddle points when S (c). Next, we introduce an alternative algorithmic framework that preserves the optimal reproducibility and attains the near-optimal complexity as long as 5 S O(e).
4.2 Inexact Proximal Point Method
We propose a two-loop inexact proximal point framework, presented in Algorithm 3 which can achieve both near-optimal gradient complexity and optimal algorithmic reproducibility. Compared to Algorithm 2 the regularization parameter 1/a (()) does not depend on the target accuracy and the diameter D, and the center of the regularization term is the last iterate (It, yt) instead of the initial point. Since the auxiliary problem is soooonggy-oooee-tttoogy-------
and 26-smooth with condition number being (1), a wider range of base algorithms can be used to achieve the optimal complexity than solving the problem in Algorithm 2 where the condition number is ((1/e).
Algorithm 3 Inexact Proximal Point Method for Convex-Concave Minimax Problems
Input: Stepsize a > 0, accuracy > 0, algorithm A, initialization (æo. 3o), iteration number T. for t 0, 1. T Apply A to inexactly solve the smooth stooglyy-oomee--sttoggyyyyooeoee problem
-11 do
1
(I.41, + min max F((z, y) = F(x,y) zER yEy
||
11112
2a 1y 3ell
2a
such that V(z, v) X y
V.Fi( (0++1 - x)- VyFi(Ce41, (Mtt1 - v) S ē.
Output: (5T+1, = (1/T) ETd (144),
Theorem 4.7. Under Assumption 7.land given a 8-inexact initialization oracle in Definition 4 with 8 < ((1/Ve), Algorithm 3 with é 3 82 (2 and a = 1/6 outputs an O(e)-saddle point after T O(1ec) iterations, and the reproducibilityy is 982.
Remark 4. The required accuracy for the auxiliary problem is ( Given that the auxiliary problem is E-strongly-come -owvee-tttooooo--y--oe--------ee such as EG, GDA, and Optimistic GDA (55 can find a point that satisfies the stopping criterion within (log(1 / (/(6))) iterations. As a result, the total gradient complexity Ó(1/e). In contrast, using GDA as the base algorithm in Algorithm will lead to a sub-optimal gradient complexity.
strongly--ooccve and 28-smooth, various linearly convergent algorithms
Theorem 4.8. Under Assumption 4.7 and given 5-inexact deterministic gradient oracle in Definition
with < Oe)), Algorithm 3 with S O()) and a = 1/E outputs an O(e) O(e)-saddle point after T (1/e)) iterations, and the reproducibility is ( )

---

Remark 5. This theorem requires solving the auxiliary problem with a 6-inexact gradient oracle. In addition Inexact-EGG presented in Lemma 4.3 we show in Appendix C.I that GDA with inexact gradients ([nexact-GDAA) can also converge linearly to the optimal point up to (622) error. Thus the total complexity is ((1/c) (1)() using both Inexact-FG and Inexact-GIAA.
Stochastic Gradient Oracle for Minimax Problems
To provide a complete picture, in this section, we consider the stochastic minimax problem:
min max F(z, v) [ (x; {),,
xEx yey
where the expectation is taken a random vector Ç. We have access to ô-inexact stochastic gradient oracle that can return unbiased gradients V fz, y) with a bounded variance 8² at each point (z. We consider the popular algorithm called stochastic gradient descent ascent (SGDA). The convergence behaviors of SGDA for the stochastic minimax problem ( are well-known in various settings. However, due to the randomness in the gradient oracle, independent runs of SGDA may lead to different outputs even with the same parameters. Following Definition 6 establish the (e, dedevattinn of SGDA in the theorem below.
we further
Theorem 5.1. Under Assumptions 4.7 and given an inexact stochastic gradient oracle in Definition 4
with = (1). the average iterates (ār, (L/T) -i Bi) of SGDA with stepsize (teT)
after T = (1)/2) iterations is an (cc)-stationary point and the reproducibility is O (c2T).
The (11/²) sample complexity of SGDA is known to be optimal when the objective F(x, v) is convex-concave 46). Moreover, our results suggest that SGDA is also optimally reproducible, as the lower- of (2(62/(=2))))) for convex minimization problems [ is also valid for minimax optimization according to our discussions in Lemma B.3
6 Conclusion
In this work, instead of solely focusing on convergence performance, we investigate another crucial property of machine learning algorithms,, i.e., algorithms should be reproducible against slight pertur- bations. We provide the first algorithms to simultancously achieve optimal algorithmic reproducibility and near-optimal gradient complexity for both smooth convex minimization and smooth convex- concave minimax problems under various inexact oracle models. We focus on the convex case as a first step since it is the most basic and fundamental setting in optimization. We believe a solid understanding of the reproducibility in convex optimization will shed insights for that of the more challenging nonconvex optimization. Note that some of the analysis and techniques used in this paper can be extended to the smooth nonconvex setting. aligning with the stability analysis for nonconvex objectives 42 44). The proposed regularized framework can be applied to nonconvex functions as well using the convergence analysis of regularization or proximal point-based methods (2] 774.. However, the non-expansiveness property in Lemma 3.2 that is essential for the reprodueibility analysis will not hold any more without the convexity assumption. One potential way alleviate it is to impose additional structural assumptions on the gradients such as negative comonotonicity [39]. We leave detailed study of the reproducibility in nonconvex optimization to future work.
Other possible improvements of our results include deriving optimal reproducibility with an acceler- ated convergence rate for smooth convex minimization problems under the inexact gradient oracle, removing the additional logarithmic terms the complexity of our algorithms using techniques in Allen-Zhu and Hazan 3 studying the reproducibility under the presence of mixed inexact oracles, and extending the results to nonsmooth settings. Another interesting direction is to design simpler and more direct methods with both optimal reproducibility and convergence guarantees. A possible way is to directly unwrap the regularized algorithmic framework I 2 leading to Tikhonov regularization g anchoring methods [75].
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable suggestions. Liang Zhang gratefully ac- knowledges funding from the Max Planck ETH Center for Learning Systems (CLS). Amin Karbasi
10

---

acknowledges funding in direct support of this work from NSF (IS--1855032, ONR (N00014- 19-1-2406), and the Al Institute for Learning-Enabled Optimization Scale (TILOS). Niao He is supported by ETH research grant, NCCR Automation, and Swiss National Science Foundation Project Funding No. 200021-207543.
References
[1] Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil Shamir. Reproducibility in optimization: Theoretical framework and limits. Advances in Neural Infor- mation Processing Systems, 35, 2022.
[2] Zeyuan Aluen-Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems, 31, 2018.
[3] Zeyuan Allen-Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives. Advances in Neural Information Processing Systems, 29, 2016.
[4] Martin Arjovsky and Leon Bottou. Towards principled methods for training generative adver- sarial networks. In International Conference on Learning Representations, 2017.
[5] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pages 214-223, PMLR, 2017.
[6] Amit Attia and Tomer Koren. Algorithmic instabilities of accelerated gradient descent. Advances Neural Information Processing Systems, 34: 1214-1214, 2021.
[7] Amit Attia and Tomer Koren. Uniform stability for first-order empirical risk minimization. In Conference on Learning Theory, pages 3313-3332. PMLR, 2022.
[8] Hedy Attouch, Zaki Chbani, and Hassan Riahi. Combining fast inertial dynamics for convex optimization with Tikhonov regularization. Journal of Mathematical Analysis and Applications, 15692),1065-1094, 2018.
[9] James P Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games, In Proceedings of the ACM Conference on Economics and Computation, pages 321-338 2018.
[10] Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533:452 2016.
[11] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4391, 2020.
[12] Heinz H Bauschke, Patrick L Combettes, al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[13] Richard Bellman. Stability theory of differential equations. Courier Corporation, 2008.
[14] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 12410, 2020.
[15] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learn- ing with adversaries: Byzantine tolerant gradient descent. Advances Neural Information Processing Systems, 30, 2017.
[16] Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Mathematical Programming, pages 1-43, 2023.
[17] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 22499-526, 2002.
[18] Xavier Bouthillier, César Laurent, and Pascal Vincent. Unreproducible research reproducible. In International Conference on Machine Learning, pages 725-734. PMLR, 2019.
11

---

[19] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019.
[20] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-3577 2015.
[21] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability. privacy, and adaptive generalization. In Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, pages 520-527, 52,,2227,033
[22] Tatjana Chavdarova, Matteo Pagliardini, Sebastian U Stich, François Fleuret, and Martin Jaggi. Taming GANs with lookahead-minmar In International Conference Learning Representations, 2021.
[23] Tong Che, Yanran Li, Athul Jacob, Yoshua Bengio, and Wenjie Li. Mode regularized generative adversarial networks. In International Conference on Learning Representations, 2017.
[24] Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv:184..01 1804.0169,, 2018.
[25] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED; Convergent reinforcement learning with nonlinear function approximation. In Interna- tional Conference on Machine Learning pages 1 1125-112 1134. PMLR, 2018.
[26] Alexandre d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Optimization,
2008
[27] Olivier Devolder, François Glineur, Yurii Nesterov, et al. First-order methods with inexact oracle: the strongly-convex case. CORE Discussion Papers, 2013016:47, 2013.
[28] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming. 146:37-75, 2014.
[29] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- fions and Trends@ in Theoretical Computer Science, 9(3-4):21144) 2014.
[30] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In International Conference on Learning Representations, 2023.
[31] Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Repli- cable clustering. arXiv preprint arXiv:2302. 2023.
[32] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and com- plementurity problems. Springer, 2003.
[33] Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, pages 3174-3185. PMLR, 2021.
[34] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[35] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. In International Conference Learning Representations, 2019.
[36] Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julies and loannis Mitliagkas. Negative momentum for improved game dynamies. In International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR, 2019.
12

---

[37] Ian Goodfellow, Jean Pouget-Abadig Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances Neural Information Processing Systems, 27, 2014.
[38] Steven N Goodman, Daniele Fanelli, and John PA Ioannidis. What does research reproducibility mean? Science Translational Medicine, 8(341):341ps 12-341p21p 1p441ps1221 2016.
[39] Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient-baser methods beyond monotonicity: the case of negative comonotonicity. In International Conference on Machine Learning, pages PMLRR, 2023.
[40] Odd Erik Gundersen and Sigbjøm Kjensmo. State of the art: Reproducibility in artificial intelligence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[41] Benjamin Haibe-Kains, George Alexandru Adam, Ahmed Hosny, Farnoosh Khodakarami, Levi Waldron, Bo Wang, Chris McIntosh, Anna Goldenberg, Anshul Kundaje, Casey S Greene, et al. Transparency and reproducibility in artificial intelligence. Nature, (6677829):4--66 2020.
[42] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225- 1234. PMLR, 2016.
[43] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[44] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems, 33:2759-227 27700, 2020.
[45] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Pruceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 818-831, 2022.
[46] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational incqualities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[47] Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguisha- bility learning algorithms. In International Conference on Machine Learming, volume 202, pages
PMLR, 2023.
[48] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[49] Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pages 6175-6186. PMLR, 2021.
[50] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for noncomvex-sttrogllyycomm
min-max optimization. Advances in Neural Information Process- ing Systems, 34:1792-1804, 2021.
[51] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion. Advances in Neural Information Processing Systems, 28, 2015.
[52] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concat minimax problems. In International Conference Machine Learning, pages 6083-6093. PMLR, 2020.
[53] Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are GANs created equal? large-scale study. Advances in Neural Information Processing Systems, 31, 2018.
13

---

[54] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations, 2018.
[55] Panayotis Mertikopoulos, Christos Papadimitrion, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2700-27021 SIAM, 2018.
[56] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. Advances in Neural Information Processing Systems, 30, 2017.
[57] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR. 2020.
[58] Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-321,, 2020.
[59] Arkadi Nemirovski. Prox-method with rate of convergence (11/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[60] Yurii Nesterov, method for solving a convex programming problem with convergence rate O(1/k²). In Soviet Mathematics. Doklady, volume 27, pages 367-372, 1983.
[61] Yurü Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[62] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
[63] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1-2):1-35, 2021.
[64] Joelle Pineau, Philippe Vincent-Lamary Koustuv Sinha, Vincent Larivière, Alina Beygelzimer, Florence d' Alché Buc, Emily Fox, and Hugo Larochelle. Improving reproducibility machine learning research (A report from the NeurlPS 2019 reproducibility program). The Journal of Machine Learning Research, 22(1):7459-744) 2021.
[65] Tyrrell Rockafellar. Monotone operators associated with problems. Nonlinear Functional Analysis, 18(part 1):397-407, 1970.
and minimax
[66] R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
[67] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. Advances in Neural Information Processing Systems, 29, 2016.
[68] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In Conference on Learning Theory, volume 2, page 5, 2009.
[69] Shamir and Lorenzo Coviello. Anti-distillation: Improving reproducibility of deep networks. arXiv preprint arXiv:2010.09923 2020.
[70] Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky, Alexander Titov, and Mohammad Alkousa. Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle. Journal of Optimization Theory and Applications, 194(3):98--0113 2022.
[71] Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
14

---

[72] Paul Tseng, On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252. 1995.
[73] John Von Neumann. On the theory of games of strategy. Contributions the Theory of Games, 4:13-42, 1959.
[74] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. Advances in Neural Information Processing Systems, 33:5667-5678, 2020.
[75] TaeHo Yoon and Ereest K Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k²) rate on squared gradient norm. In International Conference on Machine Learning, pages 12098-12109. PMLR, 2021.
[76] Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, pages 568-576. PMLR, 2021.
[77] Junyu Zhang, Mingyi Hong. and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1-2)9011-935 2022.
[78] Liang Zhang, Kiran K Thekumparampil, Sewoong Oh, and Niao He. Bring your own algo- rithm for optimal differentially private stochastic minimax optimization. Advances in Neural Information Processing Systems, 35:35174-35187, 2022.
[79] Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey Hinton. Lookahead optimizer: steps forward, 1 step back. Advances in Neural Information Processing Systems, 32, 2019.
[80] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of sonconvex-strongly-conee minimax optimization. In Uncertainty in Artificial Intelligence. pages 482-492. PMLR, 2021.
15

---

Contents
Introduction
1.1
Our Contributions
Related Works
2
Preliminaries in Algorithmic Reproducibility
Deterministic Gradient Oracle for Minimization Problems
Inexact Initialization Oracle
3.2
Inexact Deterministic Gradient Oracle
4
Deterministic Gradient Oracle for Minimax Problems
Regularization Helps!
Inexact Proximal Point Method
Stochastic Gradient Oracle for Minimax Problems
10
6
Conclusion
10
Near-optimal Guarantees in the Minimization Case
17
Inexact Initialization Oracle
17
Inxact Deterministic Gradient Oracle
18
B
Preliminary Results in the Minimax Case
22
B.1 Lower-bounds for Reproducibility
23
Guarantees of Gradient Descent Ascent
23
B.2.1
General Analysis
23
B.2.2
Inexact Initialization Oracle
24
B.2.3
Inexact Deterministic Gradient Oracle
25
B.2.4
Stochastic Gradient Oracle
26
B.3
Guarantees of Extragradient
................................
27
B.3.1
General Analysis
27
B.3.2
Inexact Initialization Oracle
29
B.3.3
Inexact Deterministic Gradient Oracle
29
B.3.4
More Discussions
31
Near-optimal Guarantees in the Minimax Case
32
Useful Lemmas
32
Regularization Helps!
35
Inexact Initialization Oracle
35
Inexact Deterministic Gradient Oracle
36
Inexact Proximal Point Method
36
16

---

33,
General Analysis
37
2
Inexact Initialization Oracle
37
Inexact Deterministic Gradient Oracle
38
D Numerical Experiments
38
A Near-optimal Guarantees in the Minimization Case
This section provides proof for the near-optimal guarantees of Algorithm in the minimization case. We start with some commonly-use -uedd facts that follow from basic algebraic calculations. See Bauschke al. [12 for example.
Lemma A.1. The following facts will be used the analysis. For any vectors a, E Rd,, holds that
(i) 2a b ||a|l ||b]] ||a b1]²
(ii) 2a b ||a - ||a|22 ||a|2
(iit) - y|la|12 |1b1| < 2a 7/laal2 + 11b11 by > 0,
(iv) I| + (1 n)66(² + 7 1)) b112 - nllall + (1 - n)]bb?? Vn E R.
A.1 Inexact Initialization Oracle
This section contains proof of Lemma 3.2 and Theorem 3.3 for the near-optimal guarantees of Algorithm in the inexact initialization case.
Proof of Lemmaa 3.2 By the optimality conditions of xe and (at),, we have that for any x X,
(VF()))+r(e) - 20)) (r x;) 2 0, (VF((<;))) + r((=;)()))))) -0))) (a' (x;)) 0.
Taking x' = x and (x;)) the above equation, we obtain that
(x:- - (x;))) [1;F(x;;) + r(=; =o)) - (VF + r((x;) - rbb))) s 0.
Since VF monotone when F is convex, rearranging terms, we get
(-; (VF()) VF(())))))+ + +r|1= (x)111 rla, (x,)²) (Ir x/6)
2 r| r||æ, - (xt))1 r(a; (x))) (xo -/)--
Given r > 0, this means
| - 21 < ( (x;)²) (xo - 2%))
< || - (xx) ( - 2'1l-
Dividing both sides by ||=; (x:)'l], the proof is complete.
By converging sufficiently close to the optimal solution, we can ensure Algorithm is reproducible. The near-optimal convergence rate is achieved using AGD 660 as the base algorithm.
first analyze the convergence guarantee. Let x E arg mingex F(x) be one minimizer of F(x), and x; arg mingex (x(x) be the unique minimizer of F,(x). By the definition of (x), we have that
Proof of Theurem 3.3
F(x,) F(x") = Fx,x,) _ ||,,- =oll² Fx(x")
+ 2 || ro
< Fx Fx(x") 2 $1100 11
< (x,) Fx12;) "1100= -o-o=oll"
rD2 SG 2
17

---

and r will be selected later. For reproducibility, we proceed as
2 - - 2|,,, - =;,1 + || - (2 + [1x;)) - =1,1
< 5 + 2 2e,
where we use the optimality condition of x. by r-strong-coovexitty of F, (z)):
z I x; 2 (x+) Fx(x,)
S 6,
the optimality condition of (aty and Lemma 3.2 Setting
8
D
6, 2
min
4
we guarantee that F(x)) F()) and ||,, - xx 26. The gradient complexity of AGD to
achieve e,- approximation error on the function value gap of an é-smooth and (e+ r)-sronnyy convex function is (e(((++r)/ log(1/e,)) = ((VeD2/e) where O hides logarithmic terms.
A.2 Inexact Deterministic Gradient Oracle
This section contains proof of Lemma 3.4 and Theorem 3.5 for the guarantees in the inexact de-
terministic gradient case. We first study the convergence behavior of AGD (60] for smooth and strongly-convex functions under the inexact gradient oracle. For the sake of simplieity and to enable a general analysis, we slightly abuse notation here to consider the optimization problem
min (x))
#EX
where & + satisfies the following assumption. Assumption A.2. f(x is t-smooth and p-strongly convex on the closed convex domuin X.
We consider the inexact gradient oracle defined below (referred to 5-oracle in this section).
Definition 7. (6-oracle) At any querying point x E X, the 6-oracle returns a vector g(ø) E Rd such that [[ V f(=)|² < 8², where V fzx is the true gradient of f(x).
In previous work, Devolder al. 27 define different inexact oracle that is motivated the exact first-order oracle and study the convergence behavior of first-order algorithms including AGD. Definition 8. ((8, f. ora-le (27)) At any querying point x E X, the (6, l, poralle returns approx- imate first-order information (fs.e. (æ), (x),,,()) such that for any y E X.
P 2 I1 - v/l
v1l S f(v) - (Ja. (x) (x) - x)) S 2 || y| + 8.
The lemma below characterizes that the oracles can be transformed into each other (adapted from Devolder et al. (27 (2)).
Lemma A.3. Under Assumption A.2 A 8-oracle can be transformed (8' E. (e,j"'--raaa -oracle with = (1/(2)) + 1/2)52, l' 22, and j = p/2. A (6, E, (1) -oracle can be transformed to a d' -oracle for 8' defined 7
Proof. Given a 6-oracle that returns g(x) at any point x E X, we construct a (8', El, p'''')rraclee as
S (x) f(x)
96 ee (x) g(x).
By (-smoothness of (xx and fact (iii) in Lemma we have that
( [() V)(x) (y x) 2 v112
= f(x) g(x)) (y-z) + (Vf(z) - -(x))] (v - x) 111== v112
(5)
s f()) g(x) + E|| b|1² + 8²
28
18

---

Similarly by jesttrng convexity of f()) and fact (iid) in Lemma A.1 we have that
flv) 2 f()) Vf(z) (y x) トー -z y11
f(x) + ((z) (u x) (Vf(z) g(xx)) T (y x) + 1 1| y11
2 f()) g(x) T (y x)
M | v
8²
Combined the above two equations together, obtain that
# |a - ull S s(v)) (f(z)
8² + )(x))((( (u x))
S f|1 - y11²
28 +
This concludes the proof of the first part. For the second part, given a (6, l, po--ll in Definition g we construct a -oracl as follows: g(x) = g6.e. (x). Taking y = x in Definition we obtain x.
f0,),(x)) & f(x) - (s) +
Therefore, by strong--onvexity f(x), we have that Va, y-
f(v) 2 f(x) Vf(z) x) + 1
2 | - yl1
2 Jan + V (v x) + 2 r y11²
Combined with the second part of Definition
we obtain that V Vxr
e | y| 2 +
(Vf(x) g8.6, (1)) (y 5)
2
Then by a similar proof as for the convex case in Devolder et al. _ (x) and = + (ot
28 Let A(x) = Vf(x)
for r(x) maxfr E R
r ( A E X}. We have that
V28(e -))
when V Ve-u Sr(a),
[Vf(=) - (x),l S
l e- r(z)+ + r(x)²
5
(7)
otherwise.
2
Since we use g(x) = I.. (x), the proof is complete.
Devolder al. 227 prove that AGD equipped with (ő, e, -oracele in Definition converges ((6i////)nneiihbbrhooo the optimal solution with accelerated rate ((ve/p):
((TT) - 50 exp - V
L
where ZT is the output of Ttepp AGD and f" the optimal value. They further establish a lower- bound showing tightness of the O6b error for any first-order methods with accelerated rate.
Here, we are interested in the performance of AGD under the 5-oracle in Definition 7 the transformation in Lemma A.3] we choose the parameters in AGD follows:
Motivated by
Je+1
TIx
1/t g(v)))
(8)
2 - VufE
Met1
I1-1 +
(#141 Iz).
2 + Vuft
The results can implied by Devolder et 27 together with Lemma A.3 We provide detailed proof in the following for completeness of the paper.
19

---

Lemma AA. Under Assumption A.2 Let x" be the unique minimizer of f (z) and k. = t/ be the condition number. Given an inexact ò-oracle in Definition
7
Starting from yo 2g. AGD with
updates 8 for & = 0,
converges with
[(T)) - f(x") S exp (-2vk) (f(2o) - ((x=)))((x)++) + 11100 -11]=) vT(
T
+ 2 8². p
Proof. By 5 in the proof of Lemma A.3 we have that
f(1(11) S f()) ( (x1+1 - 3e) + fl| - yell2 + 8²
2l
Similarly by 66 we know for any x X,
8²
f(x) 2 f(v) + g(ve) T (x - Ve) + 21100 well?
f
Combing the above two results, for any x X, we have
f(x+11) - f(x)= = f(x++1) - f(v)) + fV+) - f(x)
I g(v)) T (IE+11 - x) + f||0111 - vell² 11
|1
3e11 +
28 + 8²
4
S 2f( - y1) (0re11 - x) + ell02+1 we11
1
|| - well2
+
82
4
28
= -11 - vall2 20(x++11 - v1h) T (x - ye)
4
H
|| 1el1?
1
82
2
p1)
where in the last inequality we use the optimality condition of the projection step such that V x E X.
T
21 s(wi)) (or x1+1) 1) 2 O.
5t- - V/ +
Let A = 1/(2VK)= Vn/(4f). Setting v, and x²' in the above equation, we get
(1 (1=0)(((2(4)) - (ax)) S -E(1 0)ل 1= + 20(1 ()(++11 - we)
(Ite
ye)
4 (1 0)||,> w011 + (1 - 0)
1
1
82
28 11
((((F++1) - [(x0)) S -10 - yell + (x((1 - -1)) (s= - -ve)
1 - - yoll + 0
28 + 82.
Let A, = f(x)) - -(x²) 2 O. Summing the above two up, by fact (i) in Lemma A. I obtain
A+t1 (1 0) < - -ellze+1 -1 20(x1+11 - ve) (T)(((())) ((1 0)ar + Ox v1)
" 001 -vel
4
4 0)1|=r 1el12 +
1
+ 8²
1
4
28
-lluv- (1 0)z, Ox
- -l|
(1
0)xr= 0x2
H _01110- - 1011 4
// (1 0))|2a 1el12 +
1
+
1
5².
4
28
Let Ou,- = Ft - (1- - 0) for 1. 2 1. From the update
g of AGD, we observe
(1 + 0)y = (1 + 0)ara + (1 ( xt-1)
2.rr (1 - 0)
Fz + ou,-
20

---

Rearranging terms, we can get x = (1 + f)yl - Bu, and thus
Vt - (1 0).r+ = Yt (1 - 0)((1 + 0)yr 844)
y/t ((1 -0²)yr (1 - 0)0ce)
=((0y: + (1 -)))).
is easy to verify that the above also holds when uy = Zo = you Since LB2 = p/4, we have that
A+11 - (1 - -
$ 4
M 1100 + (1 flue- x²112 1² |luet1 x²112 M
0||22* y y1l12+ + ( 1 1
82
4
22 1
" [1(1 0) xx²) + O(ve- - x² x²)11 }11- ~ -llue-1 - xx 211 = 011x²*
y 11112 +
1
+
82
28
$ 4
H (1 - 0) llue x=11 111 4
H
|1e11 201
1
82,
28 1
where we use fact (iv) in Lemma
A.1
Rearranging terms, we then obtain
A 1141 - x x01 s (1 (0))))()) (A + llllus - x x²11²) + 26 1
(2)
+ 1 )
Unrolling the recursion, we have that
f(rr) - f(=)(( s AT 1 |lur ==
4
$ (1 0)7( (Ao + 111o - x x²(1²) + ((1 - 0)T +...+ (1 - 0) + 1)
2/4 +
1
)
28 11
<exp(- 0T) ( f(00) - -((²) + 1luo 22(1²) + 1//
1
1
1
+ 8²
21
exp
2/R (f(Z)) -((²)) + 1 x²(l²) + V
T
? + 82
1
where we use the fact that + 1 S e", An R.
Lemma 3.4 immediately follows from Lemma A.4 With the above results at hand, are ready to show proof of Theorem 3.5 below.
Proof of Theorem For the convergence guarantee, similarly the perturbed initialization case in for x² E mig F(x) and x;;- = arg mingex F, (z)) we have that
rD²
F(x,) F(x*) < F.(x,) Fx +
2
For the reproducibility guarantee, using wwwssrrong-ooveexiie of F,(x),, we can obtain that || - 2121l S ||,,, +1 + || 2'11l
- -(. (x)))
-
Applying Lemma 3.4. if (Inexact-AGD) is used as the base algorithm A and xr is the output given initialization you 2g after T iterations, since r = c/D² < E, we know that
F.(x,) - ( (x
$ exp
T 2\
(F,( F,(x;) + - [|]00o=;;1PP) + V
e+r 1
2
82
E+r
r
e
T
r
Fr Fx(x)) F+(2;) + - |1:00 -x;13) + 582
< exp
2 2
2
2ya
21

---

When setting T = to/ this means the algorithm converges to F, (=,,))FF((3))) Fx(()) S 682 (2)(2ra) and ||,, xtl I 125² (2/(2rb). Therefore, since = c/D?, have that
F(x,) F(x²) s o 82
63/2 +c)
and the reproducibility is |0.- < (
The results suggest that to achieve e-approximation error on the function value gap, need to set ō < O()5/)), which is smaller regime compared to d s (ee) in the previous work [ when S 1. Furthermore, optimal reproducibility ((6"/<²) is not attained. We observe from the proof that the additional ((V in the last term of the error bound in Lemma leads to this degradation. Since we set r = O(e) to balance the convergence rate and approximation error introduced through regularization, this factor can be O(VI/c). Based on the houur-bound in Devolder et al. [27] for (6, f, porclle such that this O faytoo is unavoidable for an accelerated convergence rate and the transformation between the two inexact oracles in Lemma A.3 we thus make the conjecture here that the above results cannot be further improved. Algorithms that achieve optimal convergence and reproducibility under this setting require better designs and we leave it for future work.
B Preliminary Results in the Minimax Case
In this section, we provide proof of some preliminary results in the minimax setting. We start with proof of the lower-bounds in Lemma B.3 Sub-optimal guarantees of gradient descent ascent (GDA)
the deterministic case, as well as optimal guarantees of stochastic gradient descent ascent (SGDA),
are provided in Section B.2 Sub-optimal results of Extragradient (EG) are proved in Section B.3
Before that, we introduce some notations and helpful lemmas that will be used in the analysis. We let (ar, v) and VF = F(r, y); ,,, u)) for simplicity of the notation in the remaining of the paper. The following results will be frequently used.
Lemma B.1. Under Assumption 4.1 the operator F monotone and E-Lipschitz That is, V21, R2 E X x V. ((F((2)) FF(2))) $ =1 - z2l and FVF(2)) F()))) (21 - 22) 2 0. Moreover Vz E x y, [[F(())] S where we define L == min| VF(=*) V2ED minimum taking w.r.t. any saddle point =² (x",1²) of F(x, v).
Proof. Lipschitzness of F directly follows from t-smoothness of F(z, v). The fact that FF is monotone when F(x, y) is convex-concave is well-known in the literature (e.g., see Theorem in Rockafellar (65). For the last statement, taking any saddle point 2", we have that Ve X x 3,
(F)()) < [+F((=)) + [[ FF(2")I
< |[>((> + =*
The proof is complete since the domain X and y have diameter of D.
Lemma B.2. Under Assumption 4.1 For some integer 2 1, let 2, = (Iz, Vt ) fort = , and žτ = (wT, ØT) = (1/T) > o (I,, wc). If V= E X x V. (1/T) > D FF())) T =) S
then it satisfies that max,ey (IT.y) minaex F(x, (T) S 6.
Proof. Since F(x,)) is convex-concave, we get that Vz = (x, 1) E X x Y
F(x,,y) F(x, v.) = v) - F(r,, vc) + F (xt, Ve) (a, 91)
< V.F v1 ( - x) - V, F(r,, v1 (yx y) F= (zt z).
Summing up from t = to T - 1 and dividing both sides by T. by Jensen's inequality, we have that
T-1 FF(z)
F( v) - F(x, F2) S T
-2)
t=
<.
Taking y arg maX.ey F(Er, v) and r arg min Flu, ((u,Tr), we conclude the proof.
22

---

B.1 Lower-bounds for Reproducibility
The lower-bounds follow from the minimization setting 1.
Lemma B.3. For smooth convex-concave minimux optimization under Assumption 4.1 the repro- ducibility, i.e., (e, (e,8))-evian -'deiiiat,nn, of any algorithm A is at least (i) (2)))) for the inexact initialization oracle; (ti) (2(82 /e) ) the deterministic inexact gradient oracle; (iti) (2(22((Te)) () the stochas- tic gradient oracle, where T is the total number of iterations of the algorithm.
Proof. The lower-bound of reproducibility in Ahn et al. [ for smooth convex minimization problems also a valid lower-bound for smooth convex-concave minimax problems. To show this, we consider a special case of the minimax problem ① where the domain ) is a singleton, i.e., y = {uo}} for some yo- Then the original smooth convex-concaw minimax problem minzex maXgey F(x, y) is equivalent to the smooth convex minimization problem mingex fo). For all three inexact oracles, let (0. ú) and (á', j be the c-approximate outputs of independent two runs of the same algorithm, i.e., the duality gap can be upper-bounded by e, then the reproducibility || 4/'1 + ||i 02 || - 1'11 since y D' yo- Moreover, & and j' are also e-approximate solutions of the function F(x, Uo) based on the definition of duality gap. Thus the lower-bound in the minimization setting 1 directly implies the lower-boudd in the minimax setting. To be specifie, the lower-bound is: (i) !(62) for the inexact initialization case; (ii) (2(62 / for the inexact deterministic gradient case; and (vii) (162 (T))) for the stochastic gradient case.
B.2 Guarantees of Gradient Descent Ascent
This section provides proof of Theorem 4.2 for the sub-optimal guarantees of GDA the deterministic setting and Theorem [he for the optimal guarantees of SGDA in the stochastic setting. We first provide a general analysis and then expand it for three different inexact oracles subsequent sections.
B.2.1 General Analysis
Algorithm 4 Gradient Descent Ascent
Input: Stepsize a > 0, initialization (Do, yo). number of iterations > 0. for t 0, 1....I T
do
Mr+1 = 1y + V F, (F11111)) 8t)). Te+1 (x VV (Ir, 1/1)
Output: (Ār, (T) = (1/T) Ei (Ie.
We consider (stochastic) gradient descent ascent (GDA/SGDA) outlined in Algorithm 4 for solving minimax problems ( or 33) The algorithm iteratively updates the variables 2; and Yt using exact gradients V Fæ,,, Vt),, inexact gradients G(I,, yr), stochastic gradients V fx,, yri Ex) based on
different types of the inexact oracles in Definition 4
We first analyze the behavior of GDA with access to exact gradients. It is well-known that the last iterate of GDA can diverge even for bilinear functions [55] 36). and the average iterates converge with sub-optimal rate O(1/VT). We provide proof for completeness.
Lemma B.4. Under Assumption 4.1 (ĀT, .r) of GDA converges with
When setting the stepsize to 1/(EVT), the average iterates
LT + 122(
max F(T v) min F(x, (T) vEy
xEx
VT
This suggests (11/²) gradient complexity is required to achieve c-saddle point.
Proof. Recall (ar, and FF(=)) (V, F(t, -V V F(x,, The GDA updates in Algorithm 4 can be simplified to
2111 -
(9)
23

---

Since the projection step is nonexpansive [1], we have that 42 = (a,y) E X x x
|| =1 - || aV/((z) =|12
2 2||
(z (2)-2) TT
a² (VF((2)
Rearranging terms and using Lemma
B.1 we can obtain that
aL?
VF(=) (2+ 2) <
[1 =1|² - || -213) +
2x
2
Taking summation from / to and dividing both sides by T. by Lemma B.2 we thus have
aT? max F (fT, min F(x, (r) - aT 2 øEX
D2
NEY
When setting a = 1/(EVT), this means the complexity is required to be 2 (LD2 + L2 (2/(2))) to achieve c-saddle point such that maxzey F(Fr. v) minzex F(x, (r) S..
Lemma B.5. Under Assumption 4.1 the GDA update g is (1 a² (2 exxpansive. That is, if
(Te+1, 11+1) is obtained through -step of the update given (Z and (1441:643) is obtained given (Ie V'J, we have that
| 22+1112 Iluet1 s
s (1 a2 x/111 l1ye 3/113).
Proof. Recall 24 = (Iee, M1)) and 2/ (x/, v/). By the updates of GDA 9 we get that
|| - 2441 112 $ 11(2: 24) a(VF(z)) (2,) VF(2)))
< || - =/[1? =
=1)
< (1 +11+aa2 (112 x1 + 11u. - -
where we use the fact that the projection step nonexpansive and Lemma B.1
B.2.2 Inexact Initialization Oracle
Theorem B.6 (Restate Theorem 4.2 part (i)). Under Assumptions 4.1 The average iterate (ØT, of GDA satisfies maX F(IT y) min F(x, ÿT) S (e) with complexity = (1/e)) if
setting stepsize a = 1/V/T)). The reproducibility, iee. (e, --deviaaaoonn between oulputs (āT, ØT) and (T/r v/) of two independent runs given different initialization is [ 17 1 7 - (
Proof. The convergence analysis directly follows from Lemma B For the reproducibility analysis,
by Lemma B.5 and the choice that = 1/(EVT), we have that for = 1.2, ... , 1,
| - 2/11² + 1lve 22 < (1 + 2 (1 - 1/2=11 + Il - -/6-1113))
1 + T
(1| - 221=112 + || - Voo 11?)
1 1) (11 - -6612 1l - 3/612))
The above also trivially holds for t = 0. Therefore, by Jensen's 's inequality, obtain that
| 1/ + 1: 11
(1|3,
x1112 - 11 2111
T 1=0
1
1 +)²
$ 8
The choice of a is to avoid exponential dependence on l in the reproducibility bound.
24

---

B.2.3 Inexact Deterministic Gradient Oracle
When only given an inexact gradient oracle in Definition 4 the updates of GDA become
-t+1 = 1x - aG()))
(10)
where we let G(z)) (Ze, yo). (2,, for the inexact gradients.
Theorem B.7 (Restate Theorem 4.2 part (ti)). Under Assumptions 4.1 Given an inexact determin-
istic gradient oracle in Definition 4 with å < Oc)). The average iterate (ØT. ÿr of GDA satisfies maxyey F(āT, v) - minzex F (at DT) S (c)) with complexity T = (11122) if setting stepsize
a=1/(EVT) Furthermore, the reproducibility is || Fy 112 + llrr - Vr 112 I (())
Proof. We first show the optimization guarantee. By the GDA updates in (TO) and Definition 4 such that || Fzz) - 22 S 82, have that for any (a, 9) E X y
|| =11² < || =||2 2a (
s || - =||2 - 22 ( (2--2) 2a |
2a + 2a 2 (F(())) - T (2= (F(2)11 (11)
< {| 2 2² 22 22 +2 2a20
Taking summation from f to T 1, obtain that
T-1
(F(z) Tx: - =) 1 -an-2 =1/
+ +a(L2 +2) + V28D.
T 1=
2aT
Supposing 8 S </(2/2D and setting a = 1/(lv/ T), by Lemma B.2 this means
max F(T, v) min Fxx ūT) 2 LD2 + (L² + 8//
vEY
VT
2
e-saddle point guaranteed when T c/6² for some constant 2 4(ED2 + (12 82)
We then prove the reproducibility guarantee. Let { and { be the trajectories of two independent runs of GDA with the same initial point 20 E X y and stepsize 0. By the GDA updates (IO) and Lemma B.5 we have that
||
2441ll |l S (1(2 2/) a(G(2)) -G()))
< (1 - =1) - -a( a(FF(z)) FF(2))) + 2nd
(12)
S v + 28 1|| - z + 200.
Since the initialization = = is the same, we obtain that for any t = .., -1,
|| 2411 ( (V1+ a2 1 -661 + 2ad [+ [1+V1+026 .... (V1+ 0202) )
1-1
20d Σ (1 + a2
< 200 ((1 + 12/2
The above also holds for = 0 denoting Σn1 = 0. Setting a = 1/(EVT), the reproducibility is
| 17 ll F+ <
1
Σ
(1|2, 11112
11y. v/1lz)
T
20
T-1 a2))
(1
Σ
T
t=0
4e
8²T,
3
which is 0(62/27 when T =c/e² required in the convergence analysis of GDA.
25

---

B.2.4 Stochastic Gradient Oracle
For the stochastic minimax problem with access to stochastic gradient oracle in Definition 4 SGDA updates for 0,1, T
-++1 Txxx(== - (=EGE))))
(13)
where f((r (V (ae, vii 5i), vff veit)) and {E
17-1 are i..d. samples.
Proof of Theorem 5.7 We first show the convergence guarantee. By the SGDA updates in 13 given all the information up iteration and taking expectation with respect to & we have V2 X x V,
Eq. | 2||² / 2| 2||² 2aE f(=) (J) (z =)] =)] ((z
2 21|² F2 (z. 2) + (f
Taking full expectation, rearranging terms, and summing up from / = 0 to 1, we have that
E E (F(z)
10022==)] (z)- - 10---p =||
-3)
ax + 6
2aT
Therefore, by slightly modifying the proof of Lemma
B.2 through taking expectations, and then
setting arg minuex [E[ (u, ūr)] and arg e.
[[ (TT, 2)J, we get
D²
aLL²
max E [ v) - min ([ BT)] yEy
v at
sEX
2
We obtain that maxyey [F y)] min [L ūr) S (LD2 + (L2 + (2)) if the inexactness 8 O(1,, and set = 1/((ET), T 1/e..
We then show the reproducibilitty guarantee. For two independent runs of SGDA 13 with output { )/ and {=()==1: by Lemma B.5 we have that for any / = 0, 1, T
E [e.,c11><1 - 2/1
s B|| 24) a(Vf(z(;)) (f(4)
= || z/1l²² - 20((F(()) VF(= [ (z+ - z/) + {)(E))))
= || z/11? - 22 (F((F(() - TF(=()))(<) -x) + FF(2111
a
v)(+)()) - -VF((z) FF(2)))
< + 2 211 4a
Unrolling the recursion, noticing 20 = 2 we have that for any 0, ... ,TT -1
E| - 2||l < 4a 8
2111
a1+
Since 2 1/2, we know a 1/(((T) $1/(e(T). The reproducibility is thus
-[ I
17
| - x1ll2 + 11ve x/
T
28
T-1t-1 1-1
Σ
(1 + a²Ry
T
1=0
4a T-1
|+ T
T t=1
< aT
2e 8²
1 2T'
The last step uses the choice of a such that aT 12
26

---

B.3
Guarantees of Extragradient
This section provides proof of Theorem 4.3 for the sub-optimal guarantees of Extragradient (EG).
B.3.1 General Analysis
Algorithm 5 Extragradient
Input: Stepsize a > initialization (xo, yo), number of iterations T > 0.
for 1 = 0, 1,
do
1++1/2 [y + a v, (at Yt)),
1(+1/2 -Ixx(x; aV Fxtt, Ut))-
M++1 11 + vV
Ze+1 [Ix(1, aV, ( 1++1/2)),
Output: (#1+1/2:81 0/41/2) = (1/T) - 30-1122))-1/2)
For deterministic smooth convex-concave minimax optimization, Extragradient [88 72 (EG), sum-
marized in Algorithm achieves the optimal (1/ee) convergence rate. When only given inexact gradients or stochastic gradients, the true gradients are just replaced by G(a,, y1) or V fx,, yei Et).
We provide proof of its (1/cc) convergence for completeness. The proof is standard in the literature, e.g., see Nemirovski (59) or Section 4.5 of Bubeck (20).
Lemma B.8. Under Assumption 4.1 When setting the stepsize to a 1/8, the average iterates UUT+1/2:TT+1/2 of EG converges with
LD2 T
max F(#T+1/2.V) min F(x, F(r,0r+1/22 yEY
=EX
This suggests (1/e)) gradient complexity is required to achieve e-saddle point.
Proof. Recall 2, (z+, y/) and VF(22) (V,F(z,. v.), V FFF( Algorithm 5 can be simplified to
The EG updates in
2++1/2 Ixxy( aFF(2)))
(14)
2+11 = - FVF((=1))))
By fact (x) in Lemma A.1 we have that for any E X' V.
|| - 2112 + || - 2112 - || - =1|2 = 2( - 21) T (2141 - =2
I 2a F T 2411),
where we use the optimality condition of the projection step such that (Ilc(u) - u) Tu)(( (v (l-lllc())) 2 Vu E C. For the same reason, we can obtain that
|| 21 2 + ||2+1/22 2+11 1| 1|ze
241112 2(2441/2 21) (34+1/2 22+1)
< 220FF(z) 2441/2)-
Summing up the above two inequalities, we get
|| - =112 || - = -1 2=11 || - 2141 1 2a 22V 2Q T (z 2++1)
- -2aFF(z)) (Et+1 - -24112)
-1 || 12//22220 -2112 || 2+11 + 2a F -2-4111111)
+ (FF(()) - FF(E(41/2) [(t+)(221111111 2141/2).
(15)
According to Lemma B.I we can obtain
(vF(=.) - (F(++1122) [( #141/2) < f|1 - -+41/21111 2441/21
<
22 - 211//21 + || 2211/2112
2
2
27

---

Therefore, rearranging terms, by the choice of stepsize I 1/6, we have V2 E &' x ),
(F(++1122) (z++1/2 - 2)
1
(1 =|| 112-1-21)
2a =c+1/2
21112 -2e11
1241/2
2t+1|1
2a
2a
+ (VF(2)) (F(2++1/2)) (2++1 - 2x+1/2)
1
$ 2a
(I|= - =|12 - || - =213)-
112441/2- - -2112
|| - 2+112
2a
2
2a
2
1
$
(|| - 1|f-||z-11 - -- =113).
2a
(16)
Taking summation from to 1, by Lemma B.2 we have
1 - 2|12
max
F(TT+1/2:1) min Flx ((2,0r+1/2) S yEy
sEx
2nT
Since ||20- = < 2D and 1/e, the proof is complete.
The following results are motivated from Boob and Guzmán 16.
Lemma B.9. Under Assumption 4.1 Let z++1 (E++1. 1h+1) be obtained through 1-step of EG update 14 given 2 = (Ie, )t), and Z141 obtained given zy. Setting a S 1/C, then we have
|| +|-11 1| +/|l a.
Proof. For any (r E X x V. we define an operator Pa(.) X x y - X x y as (z( = Ixxxy(2; (VF(2)), and the EG updates can be written as 2441 = (P,(P,, When
the stepsize a 1/l, the operator Ps, (-) is nonexpansive, i... V21, 22 X x X
(x)) - Pa, (22)) S allVF((2) Fz(22)
S afll=1 - =2|l
< -| =211-
Since the domain X' x >'' is nonempty bounded closed convex set, by Theorem 4.19 in Bauschke et al. [2]. nonexpansive operator Pz, (.) admits fixed points. Denote one fixed point as u, E x y
such that 4 = xx a F())) = Pz, (u.). The nonexpansiveness of Pz, (.) implies
|| uell = (P' (=)) - Pa, (Pa, (u)))
$ (al))11z =wll
(17)
S l² afl
< L.
The same holds true for 2(+1 and 14 = P=ę (u4) defined for 2/. As a result, we can obtain that
| 2(+1l1 $ || - well ||u, - will 1|u4 24+1ll
(18)
< || - wiلl a.
By optimality conditions of Ut
xxxxy(= a a F(.))) and i/ Ixxs -
obtain that for any 2, / E X' x y
(u: - 2t aFF(u)) -0) u) 0.
(14 - 2 + a ( (x'- - 2 O.
Taking = = u/ and = ur and using the fact that FF is monotone by Lemma B. we obtain that
Ilue 2/112 < (ut 24) T (z+ 2 a a(FF(u)) VF(+)) (w. u()
< ||u u. w 2/1l-
Combined with 18 the proof is complete since l|ue - < 1| z
28

---

Remark 6. We can alternatively derive the relation between ||22-1 14t1ll and || 241 as follows:
[ 1
< 1| - z/1² 20(2: - (VF A4 (F(+211))) + + 4 (/2
s || =/12+ 20ll|2= - = 1/222 | 1/21/
$ (1 2al v a2 + a (² )) =/Il"
= (1+alVV1+a2) a2 22 - 21I?
Here, we use Lemma B. and B.5 The above results will lead to reproducibility that grows with O(c"), which is similar to the results of AGD for the minimization setting (6].
B.3.2 Inexact Initialization Oracle
Theorem B.10 (Restate Theorem 4.3 part (t)). Under Assumptions 4.1 The average iterate
(ØT+1/2 1/2, +1/2) of EG satisfies maxyey FLTT-1/22 y) mingex F Fx, VT+1/2) I O(c) with
complexity T == (11cc) if setting stepsize a 1/f. Furthermore, the reproducibility. i.e., (c,
deviation between outputs of two independent runs of EG given different initialization is ||
E 1+1/2 |1
1/41/211 O(min[82e 88 + 11/2,
Proof. The convergence part directly follows from Lemma B.8 with T = c/c for some constant e 2 LD2 For reproducibility, by Lemma B.5 B.9 and the stepsize a = =1/f, we have that for
t= 1=,,, 7-1, 1,
| 2221//212 + 11Be+1/2 1/21/21 $ (1+ 2²²²) (1|2: x'112 + 11 3/11²)
$ 2(1 261l + -2
2L < 8 7
The above also holds for = 0. Therefore, by Jensen's 's inequality, we obtain
|0r+1/22 22///211 + ||/r+1/2 1/41/211 2
[1441/2 - 2/41/2212 + 11ve41/2 1/+2/211))
T
0=
2 T
2L
<
8
T 1=0
161.2
$ 48
T2
362
Alternatively, by Remark 6 we know that || - "41// 122 < 2(1 + v2)2182, and thus the
reproducibility is ||2 7/11/2 1l2 + |l 1/21 / <c(e 82). The proof is complete
by taking the minimum between the two results and replacing T with e/c.
B.3.3 Inexact Deterministic Gradient Oracle
When only given inexact gradient (G2 (Fe, v.), (Tt, y:)). the updates of EG becomes
Z+11/2 = xxxxy(2 - aG((z)),
2r4 xxx - aG(z411/)))
where exact gradients F()) in [4] are replaced by G(zz) = (Go(z,, vc). -Gy(It. y:)).
Theorem B.11 (Restate Theorem 4.3 part (ii)). Under Assumptions 4.1 Given an inexact deter-
ministic gradient oracle in Definition with ó < O(e). The average iterate (IT+1/2, 2//1 of EG satisfies max,ey F F(ØT+1/2.8) m F(x, 1T+1/2) S O(c) with complexity T. O(1/c) if setting stepsize 1/E. Furthermore, the reproducibility is O 1/).)
29

---

Proof. Let (24) G(z)) FF(2)) We know ||4 I 8 by Definition 4
Using 15 in the
proof of Lemma B.8 have that 42 E X V.
|| - =112 <
2 - =112= - || =1l
| - 2+41 12 20G((z41/2) =11122)
2a(((2)) - (((2+1122) (2+1 2++1/2)
1|2 - z|12 || 2=11
114+1/2 - - 12 2a F T( - E241/2)
- (F(() - (F((2+1122)
(21+1 - -x+1/2) + 2a 2a (2)(121122) T - (2-2411/2)
(z)) (z(+1/22) (z++1 -2++1/2)
$ 2 - 2/1² || 2112 - ||2+1/22 - 2+1 12 2a V F (z 21+1/2)
20 (VF(2) FF(z+11/2) (= (=6-1 - 2aoD.
(19)
The above is the same 15 up additional error in O(6). Following the same proof after with a = 1/e, we obtain that
15
WD2
max F(T1+1/2.1) - min F(x,0r+1/2) S T +3V28D.
yEY
When < <<((6DD and T c/c for some constant e 2 22T2 /e, we get e-saddle point.
We then show the reproducibility guarantee. Let u, 1xxxy(= -FF(uu)) be the same as in the proof of Lemma B.9 Similarly to (17). we have that
|
well S aalG((2-112) FF(u))
S aal ((((F(241122) - VP(w))l + +0(1((2+4122) (F(41/22)
S 24|12+1/22 4il + ad
S <a2ll(((z)) - Flu)ll + ad
S 5a2f1= - + (1 + al)ad
S ff (1 af)ad.
As result, the same as 18 since a = 1 1/e, we can obtain that Vt = 0,1,...,7 1.
| 211 s -
al)ad
< 1(2a3 2 L 2(1
2t
< L L + 25).
Therefore, by Jensen's inequality and 112 in Section B.2.3 for the guarantee of GDA, we know
1
| 2'1112212 11ur+1/2
0/41/211
[1441/2 - [1141/2~2<44/al 2'(41/212 + ||1641/2 1641/211
((1 + a²(2)11z, - =111² 40282)
$ T 1=
Σ
(2t² (L + +202 + +82)
128
321
<
2
+
T + 8²
3/2
382
82
30

---

Note that 7 = c/c and I (c).. Thus the reproducibility is O(1/e), Alternatively by Remark and similarly [12. we have that
||=0-1 - =1+111
1 || =1/112 + 2alf|2 - 2411122+1122 1111/211 az 22+1/2 - 2/+1/21 + 2ad
2
$ (I 0282
|| - z1|2 + 4a2ld (1+0lv1+ || 15-44 21l + 4042262 + 2008
(1 1 a
|| - -2/1l= + 2a0(1 + at)
= =(1+ V1+ 2| 2/1l +
8
Thus ||x+1//2 - 1/21 I v21l - z/1l + 28/E & 5/e) and the reproducibility e4)2
The proof is complete by taking the minimum between the two results.
B.3.4 More Discussions
In this section, we show that Extragradient can also be optimally reproducible by a different selection of parameters. Although it will suffer from sub-optimal convergence rate (11/2/22 instead of (L/ee), this is still an improvement on the (11/c²) rate of GDA.
Theorem B.12. Under Assumptions
4.1 The average iterate (/T+1/2, DT+1 of EG satisfies maxyey F(TT+1/2: v) min F(x, 1T+1 O(c) with complexity T (12) if setting stepsize = min (2))
The reproducibility is (
Proof. The same Section B.3.2 by the choice of stepsize such that o S 8/262, we obtain
|TT+1/2 z 1/22 1r+112 - 1T+1/211 S
(6 22)
1=0
< 48 + (2
< 4(L2 +188
+1)8.
By Lemma B.8
when the stepsize $ 1/e, we have that
D aT
max F(IT+1/2.8) yEy
min F(x, 0T+1/2) S
=EX
LD2
(2
T T2/3
This means a 0(1/651/2,3/2) convergence rate with reproducibility O(82). In the case 6 = 0(1), the gradient complexity is (1//3/2)
Theorem B.13. Under Assumptions 4.1 Given inexact deterministic gradient oracle in Definition
4 with ō < Oe)). The average iterate (TT+1/2, D1+1122 of EG satisfies max F F(11+1/2.0)
minzex F(x, (T+1/2) I O(c) with complexity T ((1/(eV8) if setting stepsize
(in()/),(6/(2E)))1)
The reproducibility is (
Proof. The same Section B.3.3 since al < 1 and a² < 8/((22), we have that
T-1
| 222 + UT+1122 - 2T < 282 +
(2a 3e2 L + 2
T
< <8 (22Ll
+ 222 + +8
< 88(12+9)0
31

---

When the stepsize S 1/e, we also have
D22
max
F( - min Fl, yEy
(r+1/2)
S
wT + +3V28D
sEA
LD²
+ V2ED2
T TV8 + +322DD.
To guarantee Occ)-saddle point, we need to ensure s Oc) and aT = c/c for some constant c. This means a ((L((EV)) convergence rate with reproducibility ( Since < O(e), the gradient complexity is ((1/25/2).
Finally, we want mention that the analysis can also be extended to reproducibility under stochastic gradient oracle and stability of Extragradient [16] that matches with SGDA. We will not provide all details here. The key to select stepsize and the error term (T) that appears according to Lemma B.9 Moreover, we also acknowledge that it is unclear whether the analysis of EG is tight since the specific lower-bound unknown. We leave this problem for future exploration.
balance the convergence ((L/(aII)) in Lemma B.8
C Near-optimal Guarantees in the Minimax Case
This section discusses near-optimal guarantees for algorithmic reproducibility and gradient complexity in smooth convex-concave minimax optimization.
C.1 Useful Lemmas
We first establish the convergence behavior of gradient descent ascent (GDA) and Extragradient (EG) [48] for smooth and droogly-convex--trome -oovex-stronglyyconcvee (SC-SC) functions under the inexact gradient oracle in Definition 4 For the sake of simplicity and enable a general analysis, we slightly abuse notation here to consider the minimax optimization problem
min max fx, y). ZE yEy
where / x y > TR satisfies the following assumption. Assumption C.1. The function fz. y) is E-moooth and srarongly-comve--strnnnyyyyoooo closed convex domain X x V.
on the
Assumption C.2. We assume the existence of an inexact gradient oracle that returns a vector
g(2, y) (g. v). 9y (z. v)) any querying point (x. X y such that [ y) g(x, 2 < 82 where V f(z
(V.f(x,) v), Vyf(r, y)) is the true gradient at (x. v)-
The lemma below shows the convergence behavior of GDA under the inexact gradient oracle presented above, also referred to as Inexact-GDA
Lemma C.3. Under Assumption C.I Let 2- (x", E X y be the unique saddle point of f(x y) and Denote 2, = (xt, yt and g(2)) = (9x( Ut), By (.))...).. Starting from 2a E X x y, GDA that
f be the condition number. Given inexact gradient oracle in Assumption C.2
updates for = 0,
1,
21+1 = =xxxx((-a((a))
-
(Inexact-GDA)
with stepsize 1// (1((2)) converges with
(-
T
(1 + 8²
|22 2" 112 < exp
||:0 2 8k²
12
(2 112
vz). - V vt)). It holds that x* = xxxx(== pvf(z*) since the saddle point problem and the projection problem share the same optimality condition when f(,, y) is convex-concave (see Proposition 1.4.2 in Facchinei and Pang (32)) such that
Proof. Let ff(+) = (V.f(xt,
vf(=*) z²) 2 0, Vz (z.v) E X V
32

---

Therefore, similarly to 11 by the GDA updates, we have
| 201 [[ xx - -(g(1))))) 1xxx((' - -af
$ [((2 - =*) - ((((z)) {)())))]1
= 1 == =²(0==2(0(zz) V)((=))
-²) + a {1
is Since of is mooooon is p-s-trooglly-conee coreeeeoooo---onle-y-e-e-e
[66 35 i...
V2n, 22 E X' )/ (V/(a)) (/) (2) 1 22) |=|= - =2|1? we have that
(Ø(z) - (x-===))>)>>))))))))))))-) = (x= -x=)) -0z))= v(2x)) 1---" =*)
2 Ml2 ==11² =-122-8l1= 2*1l
" 1 1 z²112
8²
2p
where we use Assumption C.2 such that ( (z()) S 5 and fact (iii) in Lemma A.1 by E-smoothness of faz y), we can obtain that
Then
(10(z)) f=(=")) - 21))(2) (= I 26 12 - ==1
{)(2")1
Combining all three results together, when choosing the stepsize a = 1/(4()), we get that
| - =11 - (1 - az + )1) 2
2²1
+
a +
2a²
8²
/
(00)
1
8²
1
1
211
+
+
8x2
102
2x
Unrolling the recursion, we thus obtain
2|
==112
T
82
1 (1
T-1
1
||00 - =112 +
+ +...
1
Sxi2
482
2n²
8K²
SX²2
T
2
I <xxp
||:0 - 101 +
+
8².
8K
f2
122
This means OIa)) convergence rate to O(52) neighborhood, where k = E/ is the condition number.
The lemma below establishes the convergence performance of EG under Assumption C.I and
Lemma C.4. Under Assumption C.I Let (x* (x*,"")= X y be the unique saddle point of f(z. v) and k. == e/p be the condition number. Given an inexact gradient oracle in Assumption
C.2 Denote 2; (It, Vt) and g(2))
(g. v1), (2(,,, Starting from zo E X V.
Extragradient that updates for t = 0, 0. 1,
1/2 = 1xxxy - ag(z)),
(Inexact-EG)
1+ = Ix - (
with stepsize a = 1/(2f) converges with
T
882 2 !
1
1| x" 201 < exp
1100 211
+
8K
1 l
1
Proof. Let fz()) (V=f( vt). -V -Vf v() and A(x)) z(2+) - (z()). By 15 in the
proof of Lemma B.8 setting 2 = ",, we have that,
|| - 12 < || 1=1 - 1/ 24 12 11-4411/2-21111 2 2a V f (2 - 241122
- + +2a(Vf(z)) - (f(2+1122) ( (21-1111111111 2211/2) + 20A(2+1122) (x" -x--220 22+112)
+ +2a(A(z) - A(z(-12)) (2441- - =4+1/2)
(21)
33

---

By srong-convexiiyysstorgg concuvityy of the function f(z, v), we know that
2 (1241/22 + V 2F/(#1112 T (x" Fx+1/2) +
1
T1+1/2 - x x=1,,
2
4
-f(441/2. v²) 2 - (1141/22 V 1 (y² - 1/+41/2) + |1V+11/2 y²1
2
Summing up the above two inequalities, using the definition of saddle points, we have
(((++1/2) (=* - 241/2) + A (2(+1/2) (=" - 2(+1/2)
S (24122) - [(1++1/2,)) 4²)
"
|| - ==11l + (2211122) (x" =#+112)
2
< 2-21
1 11 - =='12 (|A -241///
(22)
1 1122+1/2- -2" 82
P
8²
S -1 =0112 - || 2//1/2
8
1
where we use fact (iit) in Lemma A.1 and 2|
2=1 S 21|2 2411221 + +1/++211 2/|22+11/22 2¹11?. By we also have that
smoothness of f(x, y) and fact (iir) in Lemma
A.
(VI(z)) - v (=(+1/22) (ze+1 2+1/2) + (A(z)) (==(-122) (44-1/2)(((4411 2411/2)
$ fl|2 - 2+ 1/ 2++1 1/21 + 28- | 1+21l
(23)
L
28
1 2 1/11/2 1 el|22+1 1/+1/211 1/ {
Plugging (22 and 23 back into (2I). choosing a = 11((2),, we obtain that
|=111 =012
10X
|| 2=112
pa
al)
|2+1/22
zell
2
(2-1)
(1 2al) (al)||z-1 2/-122 21+1l 112 2a02
(24)
11
(1
11
|| - x=112 ==12
(1² 11
82
- :
8P
1
Unrolling the recursion, since + 17 S e", Vnn R, we get that
|| 1=1 <
/1
T
20
z= ==
8² 2
+
1+
(1 88
11
+...
(1-
1
T-1
86
i
11
8P
< (1
T
||
2" 211
8
2 1
1
This means a O(k) convergence rate to a (82) neighborhood, where K = E/u is the condition number.
Lemma 4.5 directly follows from Lemma C.4 jobsevving that G(x,, y) +rx- xo. yo - yy is 8-inexact gradient of F, (z. y). Next, we provide a useful lemma showing how to satisfy the stopping criteria for the auxiliary smooth SC-SC sub- brobleroolmmmt in Algorithm 2 when presented with inexact gradients.
The results are motivated from Yang et al. (74).
Lemma C.5. Under Assumption C.1 and C.2 Suppose the domain and y have a diameter of D.
Denote x² = (x",") yy) be the unigue saddle point of fxry). For any = (ă, () E X x D, we let ğ(E) (g. ú). By (ā, (.,0) 0)) and define [3] ([i) ())) for 2f to be
[ 3 xxxy
which is obtained through step of GDA starting from & with inexact gradients. Denote the true gradient as ([]gg) (V=f([*), (0))) - [yf((()s, ()). Then we have that Vz (x, v)
X x y
V T ([)) - 2) => 2" + 228D (2+ (2+v2)
+3
34

---

Moreover, it also holds that ||[2| 20 - (1+ v2e/3)112 2- 8(1/ v2/8).
Proof. We construct "ghost" point & = (fr1, 01) X x to be
$ xxxx ( 1
-(1))))))
21 can be regarded as performing one update of inexact-EG with stepsize 1/8 starting from 2. Therefore, by (16) and (19) in the convergence analysis of EG, since 1/B s 1/e, we obtain that Zzz = (x, v) E X V
3 (( T ((E)s - 2) 1 2 21 - z|I?
2 21121 - 211² + +3/2DD
2 T ( â - 2) + +3/28D
< (11 ||| + | 20 11 2 21 =1l 3V2DD.
By 24 in the proof of Lemma C.4 since 3 2 20 and μ S we have that
2
25
2 - 2² & | = 1 +
+
38
3p
Therefore, we can obtain that |1 2 $ || =11 + 2 / B8 + /28 /Bn, and thus,
f((l))) ([=]a 2) S 223 211 + 2 11) + +3V2DD
23 V
- 2/2 - =11 288 22
3
/
For the last statement, since [ is obtained through 1-step of GDA with inexact gradients, by 20 in the proof of GDA for SC-SC problems before, we have that
[|[3],- =0112 S (1 11+
28
(
2
|| =0 2 82
+ 32
B²
Bp
Therefore, we obtain that ||[=], 21 s (1 + v20/3)112 - 21 8(L 22/3).
The above lemma also applies to the case when exact gradients are available setting d 0 and [i]s xxxxy 2 [f())) for the true gradients Vf(2). This implies the stopping criteria
ff(3)((2-)) S V2 E X x y in Algorithm and can be translated to || 10 < ( which can be satisfied within (log(1/2)) complexity using Lemma C.3 and C.4 with = 0 (or existing results in Tseng 722 or Facchinei and Pang
C.2 Regularization Helps!
Proof of Theorem 4.4 and 4.6 for the near-optimal guarantees of Algorithm i provided here.
C.2.1 Inexact Initialization Oracle
We also use (zo, yo) as the initialization point when solving the auxiliary strongly-conver problem. Note that the gradient steps starting from (Io, 30) remain the same on F(r,, 3) and (2(2,)) v).
Proof of Theorem 4.4
We first show the convergence guarantee. Let z, (Er,ye). By fact (i) in
Lemma A.
we have that Vz = (xr,)) E X' x ),
F((,) (2r 2) (V.,(t))) - r(zr - 20)) (2r 2)
-FF,(Z)) T (z- -2) - =0 =||2
_ ||
20
2r z|12
(25)
S 5 +rD?
35

---

According to Lemma B.2 this means maXyEy F(zr, y) mingex F(z, Ur) S + +rD
We then show the reproducibility guarantee. Denote the saddle point of F, (x, y) given (xo, yo) as
(2o (17,3,)) v.),, and the saddle point of (x, y) = F(x, y) + (r/2)]læ - %o12 (r/2) 36ll given
(ro= 16) ((x)), (u,))) By Lemma B.4 in Appendix B.3 of Zhang et al. 78 we have that
|| (2 + ll (И,\1² < ||5 --10== =1612 lyo v61l?
Let 2, (Ir, yr), 2 (2 yt) and 20 (zo, yo) for simplicity of the notation. 2y, (z,)' and 26 can be defined in the same way, Similarly to the minimization case, we have
|r #1
< || 2,11
|| (=t II(=)) - -
2er
5 + 2
where we use - (2) <
||20- 2bll S 5 and optimality of 2 by r sooong-onvexity-strrrgg concavity (SC-SC) of (2. y) (the same holds true for 2 and (2+) as well):
2 ||,,, 11
= - vill & Fr v.) - Fg (2 v,) + Fa (1)
r
2
I max F2 (1,, v) yey
min F, Fx Ur)
=EX
S tr.
Thus setting = </D² and 6 = 6. min (1,82/(88*)) we guarantee that max F(x y) mingex Fax y-) 2e and ||,-- -
12 + y/- 11 < 48 Applying Lemma C.5 with d the complexity using Extragradient (EG) 772 37 to achieve e,rer on (E+ r) smoohh minimax optimization is (((f/r++)) log(1 /c,) Ö(ED2 /c), where Ô hides logarithmic terms. I1
C.2.2 Inexact Deterministic Gradient Oracle
This section contains proof of Theorem 4.6 for the near-optimal guarantees in the inexact deterministic gradient case, The proof is based on Lemma 4.5 (restated and proved as Lemma C.4 in Section C.I and Lemma C,5
Proof of Theorem 4.6
For the convergence guarantee, the same 25 we have that
max F FZ v) - min F(z, Ur) S er + r
yEy
For the reproducibility guarantee, we can obtain that
|| 2 S ||ا, 2 || 2/11-
Let žy be the output of T-sepp Extragradient with initialization zo. By Lemma 4.5
we have that
T r
882 (
1 ) +
|| - 2111 & exp
1 - -
8 +r
(rr r
T r
1682
I exp
||20 21
16
p2
Setting T 2 (32f/r) log(rD/8) r r= e/ this means the algorithm converges to ||вT 2 <
3V/e)(6/ee. Therefore, according to Lemma C.5 if we choose 2, [2T]2r. since LD2 /e,
guarantee that ||,, 2 < 3(2v2 + 1)D (8/c) and that
max F F( - min F(x, yr) 4((2+7) LD2 e +3v2 0D oD +c. yEY
+3v2)oD+
#EX
The reproducibility is || 2 < 36(9 + (89)2))
C.3
Inexact Proximal Point Method
Proof of Theorem and 4.8 for the guarantees of Algorithm is provided in this section.
36

---

C.3.1 General Analysis
We first analyze the convergence of the inexact proximal point method (Inexact-PPM), Given initial- ization (Io, Bo) and > 0, for 0, 1,... , 1, each step of Inexact-PPM is
1
1 110-1111-
( 1141) an inexact solution to min max Fr(xx, v) F(x, v) #EX yEy
2a || xell
11 well
2nx
Lemma C.6. we run Inexact-PPM and make sure that for each sub-problem (F((2+1) T (z++1-
2) S é for all = (x.y) E X x V, where 2+41 = (x++1.1t+1) and A (F((z))))
(V (V2 Bt+1), Fe
then we have Vz E X
1 2/12
max F ((TT+1,8) 3) min F(z, +T+1) - yEY
+
ZER
2nTI
Proof. The proof is similar to Proposition 7 in Mokhtari et al. 2 = E X' y and any = 0, 1.... T
158 The same as 225 for any
1, we have that
T
V F((*+1)) (#++1 =) = V Pir(z+11
(2r+1 - xn) (2++1 =x)
1
1
122 - =2112
12441 - =112
-21--4 | +VA((44)) (2+11
(2((2)4))(244111111)) -2) 2)
2a
20
2a
1
12
211
| 2112 +
20
20x
Taking summation from to and dividing both sides by T, we conclude that
(2-1 - -2) - - 2|
+ é.
T
2aT
t=0
The proof is completed by Lemma
B.2
C.3.2 Inexact Initialization Oracle
This section provides proof of Theorem
Let 2T+1 = (8T+1. (1/T") Σt= (#441 By Lemma C.6 and the choice that a 1/f, ē = 8² 22) we immediately have
Proof of Theorem 4.7
ED2
28
max F (#T+1. yEy
min F2x, (T+1) #EX
21
O(1/T) convergence rate is guaranteed for d < O(VT)) Note that the condition number of (2:, v) 01) when a = 1/2. Therefore, to guarantee an e-saddle point of F(x,, y), a total complexity of O log( (1/))) (((1e) log( (/(E))) is sufficient for various algorithms including GDA 32 and EG 772 applying Lemma with 6 = 0.
Let 2, = (xi, 3() ) be the unique saddle point of Fe y) with proximal center 24, and (2t) be the saddle point when the proximal center is 24. For the reproducibility guarantee, similarly Section C.2.1
we can obtain that
2+1 - 2/-1ll 1ll < || - 2/
+ ||
(2t + +1(+))) - 2(+1ll
27
(26)
|| z/'1 + 2/ e
where we use Lemma B.4 in Zhang et al. 78 and (1/a)-SC-SC of Fi y):
1
(F(()))) T( 21) 2 M vi) ( v1+1) + 2a
| 2i11
2 2
|| - 21
37

---

Therefore, by induction, we have that for any t = 1.2, .
2
1| 211l $ ||:0 - -61l \ !
5 20 t
T
S 36.
The reproducibility is then || - 2/4 2 < 952 using Jensen's inequality.
C.3.3
Inexact Deterministic Gradient Oracle
For Theorem 4.8 we provide proof when using GDA as the base algorithm. According Lemma EG can also be applied here with similar argument.
C.4
Proof of Theorem When setting a 1/e, the auxiliary problem is E-strongly-cooveex-ttnnggg concave and 26-smooth. Let K be the output of K-step GDA with initialization =! on the minimax
problem millaex maxyey Fr(, v) at iteration l. Denote its saddle point as zz. By Lemma K 2 32 log(88 D2 (332)), we have that
C,3 if
K 32
902
1|
11 & exp
12
2, 112 +
4
38
- g
By Lemma C.5
we can thus set 2x+1 = 1 120 and guarantee that
(i(()))) (z++1 2) < (4v6 5v6++ V2 X x y
According to Lemma C.6 then have
LD2 T
max yEY
F(ZT+1.8) min FIx (1+1) S + 218D.
ZEX
When 5 S c/(42D). 2 20 required to obtain an c-saddle point, and the total gradient complexity TK = (64ED² /c) log(8 D2 (33*)) = Ö(1/)) with Ô hiding logarithmic terms.
We then show the reproducibility guarantee. From Lemma C,5 we know that || 2, <
+1+ 22 z1 + /25/e - 4.58/4. By (26). we have that
96
|| z |l
|| +1|
E
By induction, we conclude that || < (t((6)), and thus the reproducibility is -
818212 32"2).
D Numerical Experiments
Some numerical experiments that demonstrate the effectiveness of regularization to improve repro- ducibility are provided in this section. We test the algorithms on two problems: a minimization problem with a quadratic objective and a minimax problem with bilinear objective. The experiments conducted on a single local machine.
Minimization. We first compare the performance of gradient descent (GD), accelerated gradient descent (AGD), Algorithm 1 with GD the hase algorithm (Reg-GD), and Algorithm with AGD as the base algorithm (Reg-AGD) on a quadratic minimization problem
min 2
Ax 611
Here, d with each entry sampled from the Gaussian distribution with mean and standard deviation 10 and A dxd is random positive semi-definite matrix with rank d - that makes
38

---

Function Value
Deviation in Trajectory
104
AGD
AGD
GD
GD
10
10a
Reg-AGD
Reg-AGD
Reg-GD
102
Reg-GD
10
100
102.
10-1
10-2
10
101
102 # Iterations
10
104
100
101
102
10a
10
# Iteerations
Figure I: Comparisons among GD, AGD, and their regularized version on the quadratic minimization problem with 6-inexact gradients. The left figure plots the convergence behavior and the right shows the reproducibility. Both axes are plotted utilizing a logarithmic scale.
sure the problem is convex but not strongly-convex, To be specific, we let A = UEUT where U is random orthogonal matrix drawn from the Haar distribution, and E is diagonal matrix with entry being 0 and the others uniformly sampled from [0.1, 10). This ensures that the problem is smooth with parameter smaller than 100.
We implement an inexact gradient oracle that returns A (Ar- - + ôe where e E Rd is an all- one vector and 8 RR controls the inexactness level. We the aforementioned four algorithms with this inexact gradient oracle on both convergence performance measured by function value and reproducibility performance measured by the deviation compared to the trajectory obtained from using the true gradient when 8 = 0. In the experiments, we let d = 100 and 5 = 0.1. For all four algorithms, we set the number of iterations be 10000, and the stepsize be 0.01 based on the fact that the smoothness parameter is at most 100. For the regularization-be regularization parameter of the auxiliary problem to 0.05. All other parameters are set according to the theoretically suggested values. The results are illustrated in Figure
methods, we set the
In Figure [ we AGD converges faster than GD, but the deviation in iterates is much larger. When introducing regularization, i.e., Reg-AGD, the reproducibility guarantee is greatly improved with only small degradation in the convergence performance. It is worth mentioning that Reg- GDg also has smaller deviation bound compared to GD. All the results align with our theoretical analysis. Changing the inexactness level or the random seed for sampling the matrix and the vector does not influence the phenomenon too much, so we do not report the results with different selections.
Minimax. We also test the performance gradient descent ascent (GDA), Extragradient (EG), and their regularized counterparts (Reg-GDA and Reg-EG) in Algorithm on bilinear matrix game
min max x ATAy. xEX yEy
Here, A E Rddxd is generated the Rd ||=||| D} and y {y E Rd ||v|| < D} are d-dimensional balls with diameter 2D measured by the Euclidean norm. The projection onto these balls can be easily achieved. We implement an inexact gradient oracle that returns Ay + de and A x: + de for the partial gradients w.r.t. and respectively, where e Rdd is an all-one vector and E controls the inexactness level.
in the quadratic minimization example, X {ar
We test the aforementioned four algorithms with this inexact gradient oracle on both convergence performance measured by the duality gap (computable due bounded domain) and reproducibility performance measured by the deviation compared to the trajectory obtained from using the true
39

---

Duality Gap
Deviation in Trajectory
102
10²-
104
10
10
EG
10
GDA
10
GDA
Reg-EG
Reg-EG
10-3
Reg-GDA
Reg-GDA
100
10a
102
10a
104
100
10a
102
103
10a
# Iterations
# Itterations
Figure 2: Comparisons among GDA, EG, and their regularized version on the bilinear matrix game with 8-inexact gradients. The left figure plots the convergence behavior and the right shows the reproducibility. Both axes are plotted utilizing logarithmic scale.
gradient when 8 = 0. In the experiments, we let d = 500 and å = 0.1. For all four algorithms, set the number of iterations to be T = 10000, and the stepsize 0.1 for EG, 0.05 for Reg-EG, 0.001 for GDA, and 0.0001 for Reg- GDg. The choice of stepsizes here adheres our theoretical analysis noticing that the smoothness parameter is no larger than 10. Larger stepsize for GDA will make the trajectory easily diverge. For the regularization-based methods, we the regularization parameter of the auxiliary problem to 0.05. The results are plotted in Figure 2 regularization to improve the reproducibility of the algorithms. Reg-EG largely reduces the deviation of EG even with respect to magnitude (note the figure is logarithmically scaled), with only a small degradation in terms of the convergence speed.
We see again the effectiveness of
40


Reviews:
[{"review_id": "tC82NsK3D2", "reviewer": "Reviewer_MNe7", "summary": "In this paper, the authors introduce a novel algorithmic framework that can achieve near optimal convergence while preserving optimal reproducibility, for minimizing smooth convex objectives and minimax optimization of convex-concave objectives. Here, reproducibility under inexact initialization oracles, inexact deterministic gradient oracles, and inexact stochastic gradient oracles are considered. The key idea is to optimize a regularized strongly convex objective ( or Strongly convex - strongly concave objective for minimax optimization) using a given base algorithm, and bounding the error introduced by the regularization. The authors derive convergence and reproducibility guarantees that match or improve existing guarantees for different base algorithms applied to the proposed framework.", "questions": "* What kind of modifications to the proposed algorithmic framework or the assumptions on the objectives will allow this framework (or similar framework) being applied to the non-convex setting?\n\n* Intuitively, why it is necessary to consider the constrained optimization setting for minimax optimization when obtaining these results given using the proposed framework?", "limitations": "This work only considers convex (convex-concave) setting, and some convergence results contain logarithmic factors, which are recognized by the authors in the conclusion. In addition to these, this work considers a constrained minimax optimization setting, which might limit the applicability of the corresponding results in practical applications.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper discuss about theoretically improving the trade-off between optimal convergence and optimal reproducibility of algorithms, which is an important emerging research area.\n\n* The paper is fairly easy to read, and the methods and results are presented in a clear manner.\n\n* Using the proposed algorithmic framework, the authors show, contrary to what was previously believed, that accelerated gradient descent (AGD) method can achieve near optimal convergence preserving optimal reproducibility, which seems like a non-trivial and interesting result.", "weaknesses": "* The paper covers only convex (convex-concave) objective minimization (minimax optimization), which prevents the results of this paper being applied to many applications where reproducibility is a challenge (e.g. reinforcement learning) as mentioned in the introduction of the paper.\n\n* The paper considers a constrained optimization setting for minimax optimization, while most applications of optimization, such as machine learning, will be deployed in an unconstrained setting. This might again prevent these results being applied to many practical applications.\n\n* The dependence of the convergence bounds on the diameter of $\\mathcal{X}$ and $\\mathcal{Y}$ in Theorems 4.4. and 4.6 makes the corresponding bounds too loose when $\\mathcal{X}$ and $\\mathcal{Y}$ are significantly large.\n\nMinor comments\n\n* Using $x^*_{r’}$ to denote  $\\underset{x\\in\\mathcal{X}}{\\operatorname{argmax}}\\\\{ F(x) + (r/2) \\Vert x - x_0'  \\Vert^2\\\\}$, it might suggest $x^*_{r’}$ corresponds to the optimum when $r’$ is used as the regularization parameter, which can be a bit confusing.\n\n* Introduction of Assumptions 3.1 and 4.1 seems abrupt, and some discussion on the assumption (e.g. their implications and how these assumptions compare with prior work) seems missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the questions. Here are some clarifications.\n\n1. **The convexity assumption on the objectives.**\n\n> The paper only covers convex objectives. What kind of modifications to the proposed algorithmic framework or the assumptions on the objectives will allow the results to be applied to the nonconvex setting?\n\nWe focus on the convex case as a first step since it is the **most basic and fundamental** setting in optimization. We believe a solid understanding of the reproducibility in convex optimization will also shed insights for that of the more challenging nonconvex optimization. Note that some of the analysis and techniques used in this paper can be extended to the smooth nonconvex setting. For example, to track the difference between iterates along the trajectory of GD/GDA, we would obtain $\\Vert z\\_{t+1} - z\\_{t+1}'\\Vert \\leq (1+\\alpha\\ell)\\Vert z\\_t - z\\_t'\\Vert$ without assuming convexity. The error can still be controlled when the stepsize $\\alpha$ is small enough. For the proposed framework, extension to nonconvex functions is also possible. See [All18] and [Yan+20] for the convergence analysis of regularization/proximal point-based methods for nonconvex functions in the minimization and minimax settings respectively. However, for the reproducibility analysis, the non-expansiveness property, e.g., Lemma 3.2, will not hold any more without the convexity assumption. One potential way to alleviate it is to assume the negative comonotonicity [Gor+23] of the gradients. We leave a detailed study of the nonconvex setting to future work.\n\n2. **The constrained optimization setting.**\n\n> The paper considers a constrained optimization setting for minimax optimization. Why is it necessary? Also, the dependence of the convergence bounds on the diameter of the constrained set makes the corresponding bounds too loose.\n\nThe assumption that the domain $\\mathcal{X}$ and $\\mathcal{Y}$ are convex and compact for the minimax problems is to ensure the **existence of the saddle point**, as suggested by von Neumann's minimax theorem. The dependence on the diameters in the convergence bounds of convex-concave minimax problems is actually **inevitable** according to the lower bound in [OX21]. However, the reproducibility of the proposed framework under the inexact gradient setting crucially depends on the convergence guarantees of the sub-problems to the optimal solutions, which will introduce diameter dependence. It would be interesting to see whether such dependence in reproducibility can be relaxed.\n\n3. **Other questions.**\n\n* **Notation.** Thanks for the suggestion. We will change the notation to $(x_r^*)'$ to avoid confusion.\n\n* **Assumptions 3.1 and 4.1.**  The assumptions (convexity, smoothness, and bounded initial solution/ bounded domain)  are **standard** in the convex optimization literature. We will add more discussions to introduce them.\n\n* **The logarithmic factors.** The logarithmic factor comes from the complexity of inexactly solving the strongly-convex sub-problems and is common for inexact proximal point type methods. It could be possible to remove such term by directly unwrapping the proposed framework to obtain a single-loop algorithm, with a much more involved and less intuitive analysis.\n\n**References**\n\n* **[All18]** Zeyuan Allen-Zhu. How to make the gradients small stochastically:\nEven faster convex and nonconvex SGD. Advances in Neural In-\nformation Processing Systems, 2018.\n\n* **[Yan+20]** Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. Advances in Neural\nInformation Processing Systems, 2020.\n\n* **[Gor+23]** Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity. International Conference on Machine Learning, 2023.\n\n* **[OX21]** Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 2021."}, {"review_id": "X4MQD7Ox3c", "reviewer": "Reviewer_u7gX", "summary": "The paper studies the problem of reproducibility in convex optimization. The notion of reproducibility, borrowed from prior work, measures the \"stability\" of the output of a procedure under noisy initialization or gradient computation. For the smooth convex setting, they design an algorithm based on running accelerated gradient descent on a regularized objective, which achieves optimal reproducibility and convergence rate. This answers an open question from prior work. The authors further extend their results to the minmax optimization setting deriving many new results.", "questions": "Please answer the questions posed in the weekaneses.", "limitations": "The work is limited to a certain notion of reproducility, used only in one prior work, and thus which may or may not be the definition as the area matures. Further, even though the authors identify two sources of instability: initialization and gradient computation, they are studied separately. A unified analysis can perhaps reflect more about the practical aspects.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Reproducibility has become an important topic in modern machine learning. Since (convex) optimization is the dominant algorithmic paradigm for modern ML, it is imporant to formulate and study reproducibility in optimization. The topic of the paper thus is important and timely.\n\n2. The paper obtains the optimal bounds on convergence and reproducibility for the smooth convex setting, something which prior work conjectured to be unattainable. This is an important contribution. Further, they managed to also get optimal, and non-trivial rates for the minmax optimization, a setting which has received considerable attention lately.\n\n 3. The paper is well written. Granted that it covers a lot of algorithms and results, the writing is to the point and the flow of ideas is natural.", "weaknesses": "1. About the definition of reproducibility: since this is a new field, I presume that the community has not yet agreed upon a definition. However, it seems to me that the only paper using the definition in this paper is the prior work of Ahn et al. Does adhering to this definition indeed reflect reprodubility in practice, in some sense? Even in optimization settings, there are other sources of instability not accounted for in the analysis, for instance, truncation and rounding due to the finite precision. Is adhering to reproducility (say with respect to initialization) and disregarding potential numerical instability arising in other steps give some meaningful in practice?\n\n2. Related to the above, some experiments demonstrating usefulness of the framework would strengthen the paper. In the current version, there are no experiments.\n\n3. The underlying idea is very simple and has been used many a times in (related) prior works -- regularization makes the problem strongly convex and thus aids leasds to (various forms of) stability. Nonetheless, the authors build on this to provide non-trivial bounds for many settings.\n\n4. Some technical details, which I presume are in prior work,  are not covered in the main text. Something that confused me is how to define  \"optimal reroducibility\", which is referred many a times in the paper. Some text explaining it, perhaps in the preliminaries will be helpful.\n\n5. What if we consider an inexact initialization as well as inexact grdient, with the same $\\delta$ say -- is it possible to say something about this from the algorithms proposed?\n\n6. The authors analyze a number of algorithms in the minmax setting, as a result this part of the paper looks rather dense with Thm statements.  Some organization of what is to come will help the reader. From my understanding, Alg3, Inexact Proximal Point Method, strictly improves over all others? If yes, this should be conveyed early on in this section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable suggestions.\n\n1. **Definition of reproducibility.**\n\n> Does this definition indeed reflect reproducibility in practice? There are other sources of instability not accounted for in the analysis. Is disregarding potential numerical instability arising in other steps still meaningful in practice? Moreover, some experiments would strengthen the paper.\n\nWe agree with the reviewer that there is no consensus on what is the right mathematical notion of reproducibility in the community. It would be impossible to find a perfect definition that accounts for all sources of instability in practice. In our humble opinion,  the current definition adopted in our paper is a meaningful one and at least partially reflects practical needs. Here, the source of irreproducibility is modeled by inexact oracles and reproducibility is defined to be the deviation in algorithms' outputs under such inexact oracles. The numerical instability in practice can be modeled as inexact updates $x\\_{t+1} = x\\_t - \\alpha\\nabla F(x\\_t) + \\delta$ where $\\delta$ represents all errors coming from truncation and rounding due to the finite precision. This could fit into the inexact gradient oracle model that we considered as $x\\_{t+1} = x\\_t - \\alpha(\\nabla F(x\\_t) + \\delta')$. Hence, our analysis could also apply to such sources of numerical instability. \n\n2. **Lack of experiments.** \n\n> Some experiments demonstrating the usefulness of the framework would strengthen the paper. In the current version, there are no experiments.\n\nWe are afraid that the reviewer might have missed checking our appendix in the supplementary material, where we have already provided some toy numerical experiments in Appendix D (along with Python codes in the supplementary material) to showcase the effectiveness of regularization on improving reproducibility for both minimization and minimax optimization.  We kindly note that the supplementary material can be found in the zip folder. \n\n\n3. **The underlying idea is simple.**\n\n> The underlying idea is very simple and has been used many times in related works. Nonetheless, the authors build on this to provide non-trivial bounds for many settings.\n\nWe take simplicity rather as a compliment especially when the simple algorithm yields the optimal guarantees.  Although the idea of regularization has been developed before, they are often used for different purposes, e.g., to boost convergence [68], to improve stability [5], or to enhance privacy guarantees [71]. We provide an important use case of the regularization technique by showing an improved convergence-reproducibility trade-off.\n\n4 and 6. **Organization of the paper.**\n\n> Some text explaining \"optimal reproducibility\" perhaps in the preliminaries will be helpful; The authors analyze a number of algorithms in the minimax setting. Some organization of what is to come will help the reader; Algorithm 3 should be conveyed early on in this section.\n\nThanks for the suggestion. For \"optimal reproducibility\", we mean the algorithm attains the lower bound of reproducibility established in Ahn et al. We will add more discussions about it in the preliminaries section. In the minimax setting, the aim of providing analysis of GDA/EG is to mirror what is known in the minimization setting, i.e., the optimally reproducible algorithm GD converges sub-optimally, while the optimally convergent algorithm AGD is not reproducible. This motivates us to study whether both optimal results can be achieved at the same time. Following the same idea as the minimization setting, we also propose Algorithm 2 for minimax problems. Finally, since the inexact proximal point algorithm already achieves near-optimal convergence for smooth convex-concave minimax problems (but not for minimization problems), it is possible to have Algorithm 3 that strictly improves all the others. We will add organization paragraphs and more discussions at the beginning of sections.\n\n5. **Combination of different oracle settings.**\n\n> What if we consider both the inexact initialization oracle as well as the inexact gradient oracle? A unified analysis can perhaps reflect more on the practical aspects.\n\nThanks for the interesting question. It is possible and immediate to extend the current definition to consider both errors at the same time, and the resulting bounds will simply be the **summation of the two**. Taking gradient descent as a simple example, the deviation in iterates will be\n\n$$\\Vert x\\_t-x\\_t'\\Vert \\leq \\Vert x\\_0 - x\\_0'\\Vert + 2\\alpha\\delta t,$$\n\nwhere $\\Vert x\\_0 - x\\_0'\\Vert$ is the inexactness of initialization, $\\delta$ is the inexactness of gradients, and $\\alpha$ is the stepsize. This expression successfully unifies both inexact oracles and recovers either one by setting the other source of error to 0. The same holds true for the proposed regularization framework. We will add a discussion about this in our revision."}, {"review_id": "T9fc3UpAqG", "reviewer": "Reviewer_jCKW", "summary": "The paper considers the problem of ensuring reproducibility in convex optimization. It builds on a recent framework for understanding reproducibility initiated by Ahn et al. The paper considers both minimization and minimax optimization (the latter being a new setting investigated in this work). The key results of the paper are the following:\n\n1. Minimization problems: The paper shows an improvement in the convergence-reproducibility tradeoffs under inexact initialization and inexact gradients compared to the results of Ahn et al. For inexact initialization, the paper shows that an L2 regularized version of AGD simultaneously obtains optimal convergence and optimal reproducibility. For inexact gradients, the same algorithm obtains sub-optimal reproducibility but with optimal convergence.\n\n2. Minimax optimization: L2 regularized versions of existing algorithms achieve optimal reproducibility and near-optimal gradient complexity. Similar to Ahn et al., SGD attains optimal reproducibility and convergence under a stochastic gradient oracle.", "questions": "Overall, this paper makes a good contribution on a relevant problem and I don't have any major concerns or questions. Some other suggestions are included above.", "limitations": "These are discussed adequately.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem of developing reproducible optimization algorithms is well-motivated and relevant. Various empirical studies have shown that randomness in initialization, training, data augmentation and numerical instabilities can lead to models which make significantly different predictions on test points.\n\n2. The paper demonstrates a valuable algorithmic principle of using L2 regularization to ensure reproducibility. All the results in the paper (apart from those for a stochastic gradient oracle) are obtained by incorporating L2 regularization into prior algorithms. The results strongly suggest that there could be deeper connections between stability and reproducibility, since L2 regularization is also a similarly useful techniques for ensuring algorithmic stability. Investigating this could be an interesting direction of future work.\n\n3. The paper improves stronger bounds across a number of settings compared to prior work. It also demonstrates that suspected instability issues of AGD are not a barrier to obtaining reproducibility guarantees for it. The paper also broadens the study of reproducibility to minimax optimization, with a similar message for it.", "weaknesses": "1. The writing of the paper is decent overall, but could do with some improvements. The paper does not motivate reproducibility adequately on its own. Some of the comments seem to concern reproducibility in science broadly rather than the particular issues which concern reproducibility in modern ML. Since the paper has a lot of different results, some more intuition behind the specific bounds that are obtained could be useful. For example, the paper could comment on the reproducibility obtained in different settings and why these bounds arise from the algorithm.\n\n2. Though I can understand that there is not too much space given the number of results, some intuition for the technical ideas which go into the bounds would be good as well. In particular, what are the main ideas behind extending reproducibility to minimax optimization? Does the intuition for why L2 regularization works for reproducibility in minimization mostly carry over and give the bounds for minimax optimization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and insightful suggestions.\n\n1. **Writing of the paper.**\n\n> The paper does not motivate reproducibility adequately on its own. Since the paper has a lot of different results, some more intuition behind the specific bounds and technical ideas obtained could be useful.\n\nWe will try our best to motivate why reproducibility needs to be studied and provide more intuition about our results. For now, in addition to the theoretical work of Ahn et al. [1], we provide a set of previous empirical works on reproducibility to justify that reproducibility has become an important topic in modern machine learning, e.g., [40] for reproducibility issues in reinforcement learning and [59] for a report of NeurIPS 2019 reproducibility program.\n\nAlthough there are lots of different results in the paper, we think the main motivations and insights behind them are **consistent**.\n\n* For the smooth convex minimization setting, previous work suggests that GD is optimally reproducible but converges sub-optimally, while AGD converges optimally but is not reproducible. There seems to be a fundamental trade-off between convergence speed and reproducibility of algorithms. This motivates us to study whether it is possible to attain both optimal convergence and reproducibility at the same time.\n\n* For the smooth convex-concave minimax setting, we observe a similar behavior of GDA and EG that mirrors the minimization setting, and we also ask the same question here.\n\nThe reason why GD/GDA can be optimally reproducible is that the gradient descent step is **non-expansive** when the objective is smooth and convex. When introducing certain momentum or extrapolation step to accelerate convergence speed, such non-expansiveness property often disappears, which makes the optimally convergent algorithms AGD/EG not reproducible. The main idea behind our (near)-optimal algorithmic framework to simultaneously attain the best of the two worlds is to add regularization and leverage **uniqueness and stability of the solutions to strongly-convex problems** (or the non-expansiveness of proximal point steps), e.g., Lemma 3.2. As a result, it is possible to improve the reproducibility of optimally convergent algorithms through convergence on the strongly-convex sub-problems while selecting the regularization parameter small enough to avoid too much approximation error introduced by the regularization term.\n\n2. **Extension to minimax optimization.**\n\n> What are the main ideas behind extending reproducibility to minimax optimization? Does the intuition for why regularization works for reproducibility in minimization mostly carry over to minimax optimization?\n\nThe intuition and technical ideas to use regularization mostly carry over from minimization to minimax optimization. In particular, similarly to Lemma 3.2, the saddle point $(x\\_r^\\*, y\\_r^\\*)$ of the strongly-convex-strongly-concave (SC-SC) function $F(x,y) + (r/2)\\Vert x - x\\_0\\Vert^2 - (r/2)\\Vert y - y\\_0\\Vert^2$ is also unique and satisfies that\n\n$$\\Vert x\\_r^\\* - (x\\_r^\\*)'\\Vert^2 + \\Vert y\\_r^\\* - (y\\_r^\\*)'\\Vert^2 \\leq \\Vert x\\_0 - x\\_0'\\Vert^2 + \\Vert y\\_0 - y\\_0'\\Vert^2.$$\n\nAs a result, by converging closely enough on the SC-SC sub-problem, this property of the optimal solution can be leveraged to obtain the optimal reproducibility guarantee. In addition, the smooth SC-SC minimax problems can be solved efficiently by a large class of algorithms, which at the same time maintains fast convergence guarantees. More interestingly, since the (inexact) proximal point method already attains the (near)-optimal convergence rate for the smooth convex-concave minimax problems, it is possible for Algorithm 3 to be optimally reproducible and convergent at the same time for minimax problems. The same framework cannot be used to improve the trade-offs in the minimization setting because of its sub-optimal convergence for smooth convex minimization problems."}, {"review_id": "m2AOOPoGQq", "reviewer": "Reviewer_FHMd", "summary": "The authors investigate the reproducibility problem of algorithms that solve convex and convex-concave minimax optimization problems.  They propose new methods with better reproducibility guarantees while maintaining the theoretical state-of-the-art convergence rates.", "questions": ".", "limitations": ".", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "*I want to acknowledge that I got this paper for review **after the deadline**, so I didn't have much time to check every detail, especially the proof.*\n\nThe idea of using regularization is good. It leads to new theoretical state-of-the-art convergence rates and reproducibility guarantees. This is a solid contribution to the NeurIPS community.\n\n", "weaknesses": "1. The new method requires $\\epsilon$ and the distance $D$ between the starting point $x_0$ and $x^*.$ (e.g. Theorem 3.3.) I am not sure that the previous methods in Table 1 need these parameters. Do the authors discuss these important limitations?\n2. Algorithm 1 is a well-known method in the optimization community. For instance, see https://arxiv.org/pdf/1603.05642.pdf. It is called \"regularization technique\" or \"regularization reduction.\" I believe that the authors should cite the previous works that consider Algorithm 1.\n3. Wrong citation [55] in Theorem 3.3. The paper [55] doesn't provide an analysis of AGD for strongly convex functions. It is better to cite any of Nesterov's books.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for positive feedback and valuable suggestions. We will mention the limitations that our algorithm requires knowledge of $\\epsilon$ and $D$, whereas previous methods do not. We will also add and correct the citations following the reviewer's suggestion. Thanks for the pointers."}, {"review_id": "ozQNDuUJzg", "reviewer": "Reviewer_hiCP", "summary": "The authors proposed and studied optimization algorithms in both the convex and the convex-concave minimax setting, where both the criteria of convergence and reproducibility are measured. The authors provided upper bounds on these criteria for the proposed algorithms that matches nearly all of the lower bounds. \n\nWhile I'm not an expert on this subject (and I leave the judgement of correctness to other experts in this area), I believe this work has reached satisfying results, and I would recommend accept. ", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The upper bounds on convergence and reproducibility matches nearly all of the known lower bounds. \n2. The presentation of the work is quite clean and readable. ", "weaknesses": "N/A ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the contribution of this work."}, {"review_id": "MjLvhVnUwd", "reviewer": "Reviewer_r2W7", "summary": "This work proposes optimization algorithms that achieve optimal convergence rate and reproducibility for the settings of convex optimization and convex-concave minimax settings. This work settled some of the open questions from the previous work, and extend the results to the minimax setting.", "questions": "- Regarding the O(delta^2/\\eps^{2/5}) bound on the reproducibility, do you have some intuitions as to why improving upon this would be difficult? Even if it's a heuristic argument, it would help readers understand the main challenge.", "limitations": "- They discussed them well in the conclusion section.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Clear presentation.\n- Novel technical contributions.\n- Strong theoretical results and cleanly written proofs.", "weaknesses": "- Overall, the presentation is very clear, and the results are rigorous, and I didn't see any major weaknesses.\n- Some details about Inexact-EG would have been helpful since it seems like a new method developed in this work. In particular, is it a direct extension of Devolder et al. to the minimax setting?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the expert reviewer for recognizing our contribution and for the very positive feedback.\n\n1. **Details about Inexact-EG.**\n\n> Inexact-EG seems like a new method developed in this work. Is it a direct extension of Devolder et al. to the minimax setting?\n\nExtragradient (EG) is proposed by Korpelevich in 1976 and becomes popular in the minimax literature. Devolder et al. introduce an inexact oracle in the context of smooth convex minimization problems that is different from the inexact gradient oracle considered in this work. We provide a detailed discussion about the relationship between the two oracles in Appendix A.2. In this work, we analyze the Extragradient method under the inexact gradient oracle. Since the method does not use the true gradients but some inexact gradients, we denote it as Inexact-EG. In this sense, Inexact-EG is neither a new method nor a direct extension of Devolder et al. to the minimax setting.\n\n2. **Sub-optimal reproducibility of Inexact-AGD.**\n\n> Are there any intuitions why improving upon the $\\mathcal{O}(\\delta^2/\\epsilon^{2.5})$ reproducibility of AGD would be difficult?\n\nThe reproducibility of the proposed framework depends on how accurately the strongly-convex sub-problem is solved. According to the lower bounds in Devolder et al., it is only possible to guarantee convergence to a neighborhood of the optimal point when the oracle has certain inexactness, and the size of this neighborhood depends on the condition number $\\kappa:=\\ell/\\mu$. Since the strongly-convex parameter $\\mu$ of our sub-problems is in the order of $\\epsilon$ to ensure convergence to the original convex problem, we introduce additional $\\epsilon$-dependence in the reproducibility as well. We argue improving upon such dependence could be difficult as a result of the lower bounds provided in Devolder et al. More discussions can be found in Appendix A.2. Probably a different algorithm design is required to attain optimal reproducibility of AGD."}]

Author rebuttal:

Meta-review: All reviewers are in unanimous agreement that this paper holds strong technical strength, leading them to recommend its acceptance. Given the compelling endorsement from the reviewers, I recommend accepting it as a spotlight paper.

In addition, I would like to encourage the authors to enhance the presentation of the paper by thoroughly incorporating the reviewers' suggestions and feedback.
Decision: Accept (spotlight)