Adaptive Extra-Gradient Methods for Min-Max Optimization and Games
Authors: Kimon Antonakopoulos
Veronica Belmega
Panayotis Mertikopoulos
Venue: ICLR 2021 Poster (2021)
Keywords: min-max optimization
games
mirror-prox
adaptive methods
regime agnostic methods

Abstract: We present a new family of min-max optimization algorithms that automatically exploit the geometry of the gradient data observed at earlier iterations to perform more informative extra-gradient steps in later ones.
Thanks to this adaptation mechanism, the proposed method automatically detects whether the problem is smooth or not, without requiring any prior tuning by the optimizer.
As a result, the algorithm simultaneously achieves order-optimal convergence rates, \ie it  converges to an $\varepsilon$-optimal solution within $\mathcal{O}(1/\varepsilon)$ iterations in smooth problems, and within $\mathcal{O}(1/\varepsilon^2)$ iterations in non-smooth ones. Importantly, these guarantees do not require any of the standard boundedness or Lipschitz continuity conditions that are typically assumed in the literature; in particular, they apply even to problems with singularities (such as resource allocation problems and the like). This adaptation is achieved through the use of a geometric apparatus based on Finsler metrics and a suitably chosen mirror-prox template that allows us to derive sharp convergence rates for the methods at hand.

Published as a conference paper at ICLR 2021
METHODS FOR MIN-MAX OPTIMIZATION AND GAMES
ADAPTIVE
Kimon Antonakopoulos
E. Veronica Belmega ETIS/ENSEA
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP LIG, 38000 Grenoble, France kimon. antonakopoulos@iniia.a
Univ. de Peryy-Pontiie--CNRS, France be belmega@ensea.ff fr
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France Criteo Al Lab panayotis momayotis.mertikppeee mertikopoolloseimgg..r fr
ABSTRACT
We present a new family of min-max optimization algorithms that automatically exploit the geometry of the gradient data observed at earlier iterations to perform more informative extra-gradient steps in later ones. Thanks to this adaptation mechanism, the proposed method automatically detects whether the problem is smooth or not, without requiring any prior tuning by the optimizer. As result, the algorithm simultancously achieves order-optimal convergence rates, i.e., it con- verges to e-optimal solution within O(1/e) iterations in smooth problems, and within O(1/E") iterations in non-smooth ones. Importaatr... these guarantees do not require any of the standard boundedness Lipschitz continuity conditions that are typically assumed in the literature; in particular, they apply even to problems with singularities (such resource allocation problems and the like). This adaptation is achieved through the use of a geometric apparatus based on Finsler metrics and a suitably chosen mirror-prox template that allows us derive sharp convergence rates for the methods at hand.
INTRODUCTION
The surge of recent breakthroughs in generative adversarial networks (GANs) [20], robust reinforce- ment learning [41], and other adversarial learning models [27] has sparked renewed interest in the theory of min-max optimization problems and games. this broad setting, it has become empirically clear that, ceteris paribus, the simultaneous training of two (or more) antagonistic models faces drastically new challenges relative to the training of a single one. Perhaps the most prominent of these challenges is the appearance of cycles and recurrent (or
chaotic) behavior in min-max games. This has been studied extensively in the context of learning in bilinear games, in both continuous [16. 31, 40] and discrete time [12, 18, 19, 32), and the methods proposed overcome recurrence typically focus on mitigating the rotational component of min-max games. The method with the richest history in this context is the extra- gradient (EG) algorithm of Korpelevich [25] and its variants. The EG algorithm exploits the Lipschitz smoothness of the problem and, if coupled with a Polyak-Ruppen averaging scheme, achieves an (1/7)) rate of convergence in smooth, convex-concave min-mat problems [35]. This rate is known to be tight [34, 39] but, in order to achieve it, the original method requires the problem's is Lipschitz constant to be known in advance. the problem is not Lipschitz smooth (or the algorithm is run with vanishing step-size schedule), the method's 's rate of convergence drops to O(1/ vT).
Our contributions. Our aim in this paper is to provide an algorithm that automatically adapts to smooth / non-smooth min-max problems and games, and achieves order-optimal rates in both classes without requiring any prior tuming by the optimizer. scheme, which call AdaProx, and which exploits gradient data observed earlier iterations to perform more informative extra gradient steps in later ones. Thanks to this mechanism, and to the best of our knowledge, AdaProx is the first algorithm that simultaneously achieves the following:
this regard, we propose a flexible algorithmic

---

Published as a conference paper at ICLR 2021
EG [24, 25, 35]
GRAAL [29]
GMP [47]
AMP [1, 17]
BL [2]
ADAPROX [OURS]
TARAMETER-GGNOSS
X
PARTALL
PARTIAL
RATE INTERPOLATION
X
UNBOUNDED DOMAIN
X
X
X
X
SINGULARITIES
X
X
X
X
Table Overview related work. For the purposes of this table, "parameter-agnostic" means that method does not require prior knowledge the parameterss of the problem il was designed solve (Lipschitz modulus, domain diameter, etc.); "rate interpolation" means the algorittmm's convergence rale is O(1/T) or O(1/ vT) smooth n'noonnnmooo problems respectively; "unbounded domain" is self-explanatory: and, finally, "singularities" means that the problem's defining vector field may blow up at a boundary point the problem's domain.
1. An O(1 VT) convergence rate in non-smooth problems and O(I/T) in smooth ones.
2. Applicability to min-max problems and games where the standard boundedness / Lipschitz continuity conditions required in the literature do not hold.
3. Convergence without prior knowledge of the problem's parameters (e.g., whether the problem's 's defining vector field is smooth or not, its smoothness modulus if it is, etc.).
Our proposed method achieves the above by fusing the following ingredients: a) a family of local norms a Finsler metric capturing any singularities in the problem at hand; b) suitable mirror-prox template; and c) an adaptive step-size policy in the spirit of Rakhlin & Sridharan [43]. We also show that, under suitable coherence assumption, the sequence of iterates generated by the algorithm converges, thus providing an appealing alternative to iterate averaging in cases where the method's "last iterate" is more appropriate (for instance, if using AdaProx to solve monooonee problems).
Related works. There have been several works improving on the guarantees of the original extra- gradient/mirror-pee proxx template. We review the most relevant of these works below; for convenience, we also tabulate these contributions in Table above. Because many of these works appear in the literature variational inequalities [15], we also use this language in the sequel. In unconstrained problems with an operator that is locally Lipschitz continuous (but not necessarily globally so), the golden ratio algorithm (GRAAL) [29] achieves convergence without requiring prior knowledge of the problem's Lipschitz parameter. However, GRAAL provides no rate guarantees for non-smooth problems and hence, fortiori, interpolation guarantees either. By contrast, such guarantees are provided in problems with a bounded domain by the generalized mirror-pros (GMP) algorithm of [47] under the umbrella of Hölder continuity. Still, nothing is known about the convergence of GMP in problems with singularities (i.e.. when the problem's 's defining vector field blows up at boundary point of the problem's 's domain). Singularities of this type were treated in a recent series of papers [1, 17, 48] by means of a "Bregman continuity" or "Lipschitz- like" condition. These methods are order-optimal the smooth case, without requiring any knowledge of the problem's smoothness modulus. On the other hand, like GRAAL (but unlike GMP), they do not provide any rate interpolation guarantees between smooth and non-smooth problems. Another method that simultaneously achieves an O11 vT) rate in non-smooth problems and an (I/T)) rate in smooth ones is the recent algorithm of Bach & Levy [2]. The BL algorithm employs adaptive. AdaGrad- like step-size policy which allows the method to interpolate between the two regimes and this, even with noisy gradient feedback. On the negative side, the BI. algorithm requires bounded domain with a (Bregman) diameter that is known in advance; as a result, its theoretical guarantees do not apply unbounded problems. In addition, the BL algorithm makes crucial use of boundedness and Lipschitz continuity; extending the BL method beyond this standard framework is a highly non-trivial endeavor which formed big part of this paper's 's motivation.
GRAAL/ /MMP
2 PROBLEM SETUP AND BLANKET ASSUMPTIONS
We begin in this section by reviewing some basics for min-may problems and games.
2.1. Min-max/
Min-max/Saddle-poinn Saddle-point problems.
A min-max game is a saddle-point problem of the form
min max C(O, ())
(SP)
A deD
2

---

Published as a conference paper at ICLR 2021
where O & are convex subsets of some ambient real space and L: θ Rs the problem's 's loss function. In the tame-theorettic interpretation of (SP), the player controlling 0 seeks to minimize [(0, Φ) for any value of the maximization variable o. while the player controlling seeks to maximize [(0, Φ) for any value of the minimization variable 6. Accordingly, solving (SP) consists of finding a
Nash equilibrium (NE), i.e., action profile (I", x0) O & such that
(1) By the minimax theorem of von Neumann [49], Nash equilibria are guaranteed to exist when O, @ are compact and L is convex-concave (i.e., convex in I and concave in Φ). Much of our paper is motivated by the question of calculating a Nash equilibrium (0', (0","") ) of (SP) in the context of von Neumann's ' theorem; we expand on this below.
[ .)) S C(6 .0) [(,, Φ") for all I E O, o E ②
2.2. Games. Going beyond the min-max setting, a continuous game in normal form is defined as follows: First, consider a finite set of players N = .I..... N), each with their own action space K, R4 (assumed convex but possibly not closed). During play, each player selects an action x; from KG with the aim of minimizing a loss determined by the ensemble x == (x); . xx) of all players' actions. In more detail, writing I.C := II, K2 for the game's 's total action space, we assume that the loss incurred by the i-th player (x(x; x-)), where f; K. - R the player's loss function. In this context, a Nash equilibrium is any action profile x" E K. that is unilaterally stable, i.e.
(,xx;xx)) S x(xxx for all E K,, and all N.
(NE)
If each KC is compact and & is convex in x, existence of Nash equilibria is guaranteed by the theorem of Debreu [13]. Given that a min-max problem can be seen
two-player zero-sum game with
= 6 = CC von Neumann's 's theorem may in turn be seen as a special case of Debreu's: ss in the sequel. we describe a first-order characterization of Nash equilibria that encapsulates both. In most cases of interest, the players' loss functions are individually subdifeernntiable on a subset X' of IC with ri s X S K. [21, 44]. This means that there exists a (possibly discontinuous) vector field Vy: X - Rd such that
(2) for all x E X' E IC and all i N [21]. In the simplest case, if C; is differentiable at x, then Vx(x) can be interpreted as the gradient of & with respect to x;. The raison d' d'ètre of the more general definition (2) is that it allows us to treat non-smooth loss functions that are common in machine learning (such as I. r.-guluarr losses). We make this distinction precise below:
x(x/xx))) 2 x,xx)))) + (Vi(x),
x -x;)
1. If there is no continuous vector field Vi(x) satisfying (2), the game is called non-smooth.
2. If there is a continuous vector field Vi(x) satisfying (2), the game is called smooth.
Remark. We stress here that the adjective "smooth" refers to the game itself: for instance, if ((x) = [x] for x E R. the game is not smooth and any V satisfying (2) is discontinuous at O. In this regard, the above boils down to whether the (individual) subdifferential of each & admits a continuous selection.
2.3. Resource allocation and equilibrium problems. The notion of a Nash equilibrium captures the unilateral minimization of the players' individual loss functions. In many pratical cases of interest, a notion of equilibrium is still relevant, even though it is not necessarily attached to the minimization of individual loss functions. Such problems are known as "equilibrium problems"' [15. 26]: to avoid unnecessary generalities, we focus here on a relevant problem that arises in distributed computing architectures (such as GPU clusters and the like). To state the problem, consider distributed computing grid consisting of N parallel processors that serve demands arriving at rate of p per unit of time (measured e.g., in flop/s). If the maximum processing rate of the i-th node is μi, (without overelocking), and jobs are buffered and served on a first-come, first-served (FCFS) basis, the mean time required to process a unit demand at the i-th node is given by the Kleinrock M/M/1 response function r₃(x;) = 1/(44 - x;), where x; denotes the node's 's load [5]. Accordingly, the set of feasible loads that can be processed by the grid is X == [(x,,... xw) 0 S x; < Pi: X1 + + Xy = p). In this context, a load profile x' E X' is said to be balanced if no infinitesimal process can be better served by buffering it at a different node [38]; formally, this amounts to the so-called Wardrop equilibrium condition
,x,)) S Tx)x for all i, j E N with x > O.
(WE)
We note here crucial difference between (WE) and (NE): if we view the grid's computing nodes as "players", the constraint Σ, x = means that there no allowable unilateral deviation xxx:x";) + (xxx".) with x; x/. As result, (NE) is meaningless requirement for this equilibrium problem.
3

---

Published as a conference paper at ICLR 2021
As discuss below, this resource allocation problem will require the full capacity of our framework.
2.4. Variational inequalities. tional inequality of the form
Importantly, all the above problems can be restated as a varia-
Find x² E X' such that (V(x",,x-x") for all X.
(VI)
In the above, X's convex subset of Rd (not necessarily closed) that represents the problem's is domain. The problem's s defining vector field V: X' - R is then given as follows: In min-mav problems and games, V is any field satisfying (2); otherwise. in equilibrium problems of the form (WE), the components of V are Vi = T, (we leave the details of this verification to the reader). This equivalent formulation is quite common in the literature on min-max/ / equilibrium problems [14, 15, 26, 30), and it is often referred to the "vector field formulation" [3, 8, 23]. Its usefulness lies in that it allows us to abstract away from the underlying came-theoretie complications (multiple indices, individual subdifferentials, etc.) and provides a unifying framework for a wide range of problems in machine learning, signal processing, operations research, and many other fields [15, 45]. For this reason, our analysis will focus almost exclusively solving (VT), and will treat V and X' S R d = Σ, d; as the problem's 's primitive data.
2.5. Merit functions and monotonicity. widely used assumption in the literature on equilibrium problems and variational inequalities is the monotonicity condition
(V(x) -(x), 2
0 for all x, e X.
(Mon)
In single-player games, monotonicity is equivalent to convexity of the optimizer's 's loss function; in min-max games, it is equivalent to L being convex-concan [26]; etc. the absence of monotonicity, approximating equilibrium is PPAD-hard [11], so we will state most of our results under (Mon).
Now, to assess the quality of a candidate solution & e X, we will employ the restricted merit merit function
( = sepxec (V (Vx), x-xx--..... x))
where the "test domain" C is nonempty convex subset of X [15, 24, 37J. The motivation for this is provided by the following proposition:
Proposition 1. Let C be a nonempty convex subset of X. Then: a) Gā) 0 whenever & E C; and b) if (i) = 0 and C contains a neighborhood of &, then is a solution of (VI).
Proposition generalizes an earlier characterization by Nesterov [37] and justifies the use of Gxpe as merit function for (VT); to streamline our presentation, we defer the proof to the paper's supplement. Moreover, to avoid trivialities, we will also assume that the solution set X of (VI) nonempty and we will reserve the notation x" for solutions of (VI). Together with monotonicity, this will be our only blanket assumption.
3 THE EXTRA-GRADIENT ALGORITHM AND IT' LIMITS
Perhaps the most widely used solution method for games and variational inequalities (VIs) is the extra-gradient (EG) algorithm of Korpelevich [25] and its variants [28, 42, 43]. This algorithm has rich history in optimization, and it has recently attracted considerable interest in the fields of machine learning and AI, see e.g., [8, 12, 18, 22, 23, 32, 33] and references therein.
In its simplest form, for problems with closed domains, the algorithm proceeds recursively as
1/2 II(,- V.,
X = II(,, y, ViV1+1/2),
(EG)
where I[xx) arg min || x|| is the Euclidean projection on X, V, == v(X,) for = 1,3/2,.... and y, > 0, the method's step-size. Then, running (EG) for T iterations, the algorithm returns the "ergodic average"
ΣJ 7:
X7
(4)
Σ/
In this setting, the main guarantees for (EG) date back to [35] and can be summarized as follows:
4

---

Published as a conference paper at ICLR 2021
Extra- gradient, unluned (erg. average)
Extm-graddvet, tomed (org. averape)
UniPron (erg. average)
0.5
0.0
0.0
-0.5
-055
-05
1.0
100
The behavior of (EG) in the bilineur min-max problem L(6. 66 with 6.6 [-1. 1j. Given the clipping [-1. IJ. this problem is smooth with L I: instead, in the unconstrained case, both (BD) and (LC) fail. Still. even in the constrained case, running (EG) with step-size only slightly above the I/L bound (L = y 1.04) results in a dramatic convergence failure (left plot). Tuning the step-size of (EG) resolves this problem (center), but constant step-size makes the algorithm unnecessarily conservative towards the end. The proposed AdaProx algorithm automatically exploits previous gradient data perform more informative extra-gradient steps later ones, thus achieving faster convergence without tuning.
Figure 1:
1. For non-smooth problems (discontinuous V): Assume V is bounded, i.e., there exists some such that
[[(())] s M for all x X. Then, if (EG) is run with step-size of the form y x 1/ Vi, we have
(BD)
Gapc(Xy) VT).
(5)
2. For smooth problems (continuous V): Assume V is L-Lipschitz continuous, i.e.
[[V(x) v(x) < -||x- x'|1 for all x, X. Then, if (EG) is run with constant step-size y 1/L, we have
(L.C)
Gape 0(177)
(6)
Remark. the above, II-Il is tacitly assumed to be the standard Euclidean norm. Non-Euclidean considerations will play crucial role in the sequel, but they
necessary for the moment.
Importantly, the distinction between smooth and non-smooth problems cannot be lifted: the bounds (5) and (6) are tight in their respective problem classes and they cannot be improved without further assumptions [34, 39]. Moreover, we should also note the following:
1. The algorithm changes drastically from the non-smooth to the smooth case: non-smoothness requires 7, x 1/ Vi, but such a step-size cannot achieve fast O(1/T) rate.
2. If (EG) is run with constant step-size, must be known in advance; otherwise, running (EG) with an ill-adapted step-size (y > 1/L) could lead to non-convergence.
We illustrate this failure of (EG) in Fig. 1. As we discussed in the introduction, our aim in the sequel will be to provide a single, adaptive algorithm that simultaneously achieves the following: a) an order-optimal O(1 vT) convergence rate in non-smooth problems and O(//T) in smooth ones; b) convergence in problems where the boundedness Lipschitz continuity conditions (BD) / (LCC no longer hold; and c) achieves all this without prior knowledge of the problem's 's parameters.
4 RATE INTERPOLATION: THE EUCLIDEAN CASE
As prelude to our main result, we provide in this section an adaptive version of (EG) that achieves the "best of both worlds" in the Euclidean setting of Section 3, i.c., O(1/ VT) convergence rate in problems satisfying (BD), and an O1//T) rate in problems satisfying (LC). Our starting point the observation that, if the sequence X, produced by (EG) converges to solution of (VI), the difference
8, == ||V Vill (IV(((+1/2) v(X)Il

---

Published as a conference paper at ICLR 2021
must itself become vanishingly small if V is (Lipschitz) continuous. On the contrary, if V is discontinuous, this difference may remain bounded away from zero (consider for example the L' loss E(x) |xt near O). Based on this observation, consider the adaptive step-size policy:
Y+1 1/ 1
(8)
The intuition behind (8) is as follows: If V is not smooth and lim on 6, > 0, then y, will vanish at O(1/ Vf) rate, which is the optimal step-size schedule for problems satisfying (BD) but not (LC). Instead, if V satisfies (LC) and X, converges to a solution x' of (VI), it is plausible to expect that the infinite series Σ, 0² is summable, in which case the step-size y, will not vanish as r - co. Furthermore, since 6, defined in terms of successive gradient differences, automatically exploits the variation of the gradient data observed up to time so it can be expected to adjust to the "local" Lipschitz constant of around a solution x" of (VI).
Our step policy and motivation are similar in spirit to the "predictable sequence" approach of [43]. For now, we only state (without proof) our main result for problems satisfying (BD) or (LC). Theorem 1. Suppose V satisfies (Mon), let C be a compact neighborhood of a solution of (VI), and let H = xu - xlI² If (EG) is run with the adaptive step-size policy (8), we have:
Ga o H + 4M log(1 4M²T)
a) V satisfies (BD):
(9a)
VT
b) If satisfies (LC): Gape (X,) O(HTT)
(9b)
Theorem 1 (which is proved in the sequel special case of Theorem 2) should be compared to
the corresponding results of Bach & Levy [2]. In the non-smooth case, [2] provides bound of the form OaMDD/ vT) with D² max - min,ex/|xx| (recall that [2] only treats problems with bounded domain), and a Max|M/Mo. Mo/MM where Mo is initial estimate of M. The worst-case value of a is O(M) when good estimates are not readily available; in this regard, (9a) essentially replaces the O()) constant of Bach & Levy [2] by O(M). Since 1) in problems with an unbounded domain, Theorem 1 provides a significant improvement in this regard.
In terms of L, the smooth guarantee of [2] is O(d2 /T), the multiplicative constant in the bound also becomes infinite in problems with an unbounded domain. In our case, D is replaced by H (which is also finite) times an additional multiplicative constant which is increasing in M and L (but is otherwise asymptotic, so it is not included in the statement of Theorem 1). This removes an additional limitation in the results of [2]; in the next sections we drop even the Euclidean regularity requirements (BD)/LC), and we provide a rate interpolation result that does not require either condition.
5 FINSLER REGULARITY
To motivate our analysis outside the setting of (BDY(LC), consider the vector field
V,(x) = (μ4 x-> + 1|x > 0J, i= I.
(10)
which corresponds to the distributed computing problem of Section 2.3 plus a regularization term designed to limit the activation of computing nodes at low loads. Clearly, we have ||V(x)] + co whenever x; 0+, so (BD) and (LC) both fail (the latter even if 1 0). On the other hand, if we consider the "local" norm ||+||.. = E (14 xx) loy,, we have [|V()) s d + a Σ so V is bounded relative to ll- This observation motivates the use of a local as opposed global norm, which we define formally as follows:
Definition 1. A Finsler metric on convex subset of Rd a continuous function F: XXR - R, which satisfies the following properties for all x X and all z, e Rd:
1. Subadditivity: F(x; + 2') $ F(x;2) + F(x;z).
2. Absolute homogeneity: F(x; Az) = ())((; for all A ee R.
3. deffiiee-deiniteeness:: F(x; 2) z with equality if and only if 2 0.
Given a Finsler metric on X. the induced primal/ dual local norms on X' are respectively defined as ||e| max((u, F(x; z) 1)
|| F(x: z) and
(11)

---

Published as a conference paper at ICLR 2021
for all x E X' and all z, u E R We will also say that Finsler metric on X' is regular when | = 1 + OlIx' - x!I.) for all x, x' E X, U E R Finally, for simplicity, we will also assume in the sequel that I1-Il, 2 yi-ll for some v 0 and all x E X (this last assumption is for convenience only, as the norm could be redefined to Il-II. < ||+l + vl|-Il without affecting our theoretical analysis).
When A' is equipped with regular Finsler metric above, we will say that it is Finsler space. Example 5.1. Let F(x; = ||c|| where |I-II denotes the reference norm of X' = R Then the properties of Definition are satisfied trivially.
Example 5.2. For more interesting example of a Finsler structure, consider the set X' = (0, 1] and the metric I|æl|, = max//z//x,, e R", x E X. In this case ||u|l,,- = Σi=1 xıloi| for all v E R and the only property of Definitionn that remains to be proved is that of regularity. To that end, we have
|| || s lo:l 1 x,| Σ x/lill 1x xx//x/ s |oll, 1|xx' - x|ls-
(12)
Hence, by dividing by [|llx,.. we readily get //loll,.lllll,. + ||x x'Ila i.e., IH-l is regular in the sense of Definition 1. As we discuss in the sequel, this metric plays an important role for distributed computing problems of the form presented in Section 2.3.
With all this in hand, we will say that a vector field V: X - Rd is
1. Metrically bounded if there exists some M such that
[|V(*)) s M for all x E X.
(MB)
2. Metrically smooth there exists some L. > such that
[[V(x') - V(x)l==, z 4|xx - xllxx for all x',x X.
(MS)
The notion of metric boundedness//mootthess extends that of ordinary boundedness/Lipsee
continuity to Finsler context; note also that, even though neither side of (MS) is unilaterally symmetric under the change x ++ x', the condition (MS) as a whole is. Our next example shows that this extension is proper, i... (BD)/LC) may both fail while (MB)/MS) both hold:
Example 5.3. Consider the change of variables x; me 1 - x//1;; in the resource allocation problem 1) for the transformed field (10) under this change of variables, we readily get Vi(x) - -00 as - 0*; as a result, both (BD) and (LC) fail to hold for any global norm on Rd. Instead, under the local norm |kll max//l//x; x,, we have:
of Section 2.3. Then, writing V/(x) -(1/x))
1. For all A 2 0, V satisfies (MB) with M d(1 d): IIV(x),,, $ EX x -1/x/////// + 2) d(1 + 1).
2. For = 0, V satisfies (MS) with L. = d: indeed, for all xx E X, we have
[|V(x) v(X).... Σn i=
1
1 - x
- xil
Xi
S d max;
dllx' x|lx-- (13)
Xi
X
6 THE ADAPROX ALGORITHM AND ITS GUARANTEES
The method. We are now in position to define family of algorithms that is capable of interpolat- ing between the optimal monooth/non-smoon either (BD) (I.)..To do so, the key steps in approach will be to (i) equip X' with suitable Finsler structure (as in Section 5) and (ii) replace the Fuclidean projection in (EG) with a suitable "Bregman proximal" step that is compatible with the chosen Finsler structure on X. We begin with the latter (assuming that X' is equipped with an arbitrary Finsler structure):
convergence rates for solving (VI) without requiring
Definition 2. We say that Rdd - R U (oo) a Fregman-Finshee function on X' if:
1. h is convex, lower semi-continuout (l.s.c.), cl(dom h)) cl(A'), and dom 0h = X.
2. The subdifferential of admits continuous selection Vh(x) e āh(x) for all E X.
3. h is strongly convex, i.e., there exists some K > such that h(x') 2 h(x) + (Vh(x), - x) + F1Ix' - xII
(14)
for all E X' and all x E dom h.
7

---

Published as a conference paper at ICLR 2021
The Bregman divergence induced by h is defined for all E X, x' E dom h as
D(x',x) h(x²) h(x) (Vh(x), x' x)
(15)
and the associated prox-mapping is defined for all x X' and E Rd as
P,(y) = arg min x x'> + D(x', xx)..
(16)
Definition 2 is fairly technical, so some clarifications are in order. First, to connect this definition with the Euclidean setup of Section 4, the prox-mapping (16) should be seen as the Bregman equivalent of a Fuclidean projection step, i.e., g) s* P.(y). Second, a key difference between Definition and other definitions of Bregman functions in the literature [4, 6, 7, 9, 24, 36. 37, 46] is that h is assumed strongly convex relative to a local norm not a global norm. This "locality" will play a crucial role in allowing the proposed methods adapt to the geometry of the problem. For concreteness, provide below an example that expands further on Examples 5.2 and 5.3:
Example 6.1. Consider the local norm ||]| max/2a//x; on X' = (0, 11 and let h(x) = Σ 1/x, on (0, 1I We then have
xi)
D(x,x) = Σ
Σ (1-
x
1|x
xxl
(17)
1=1
ie., h is 1-strongly convex relative to II-lle on X.
With all this is in place, the extra extra-gradient method can be adapted to our current setting as follows:
X (xx(->VV,)
6, || [|V Villx
Y++1 1/ V E E
(AdaProx)
X,+1 (xx(-%
with V, = 1,32,.... as in Section 3. In words, this method builds on the template of (EG) by (i) replacing the Euclidean projection with mirror step; (ii) replacing the global norm in (8) with a dual Finsler norm evaluated at the algorithm's 's leading state X,+1/2-
Convergence speed.
With all this in hand, main result for AdaProx can be stated follows:
Theorem 2. Suppose V satisfies (Mon), let C be a compuct neighborhood of a solution of (VI), and sel H suprec D(x, X1) Then, the AdaProx algorithm enjoys the guarantees:
Gapc o H + M2 1/K)2 + log(1 + (1
a) If V satisfies (MB):
(18a)
VT
b) If V satisfies (MS):
(18b)
For the constants that appear in Eq. (18), we refer the reader to the discussion following Theorem 1. Moreover, we defer the proof of Theorem 2 to the paper's supplement. We only mention here that its key element is the determination of the asymptotic behavior of the adaptive step-size policy y, in the non-smooth and smooth regimes, i.c., under (MB) and (MS) respectively. At very high level, (MB) guarantees that the difference sequence ö, is bounded, which implies in turn that Σ Y; = S VT) and eventually yields the bound (18a) for the algorithm's 's ergodic average Xy. On the other hand, if (MS) kicks in, we have the following finer result:
Lemma 1. Assume V satisfies (MS). Then, a) Yt decreases monotonically strictly positive limit You lo y; > 0; and b) the sequence 6, is square summable: in particular. E 6, 11/y2 - 1.
By means of this lemma (which we prove in the paper's 's supplement), it follows that Σx Y, Y T Q(T); hence it ultimately follows that AdaProx enjoys an O(ITT) rate of convergence under (MS).
Trajectory convergence. In complement to Theorem 2, we also provide trajectory convergence result that governs the actual iterates of the AdaProx algorithm:
Theorem 3. Suppose that (V(x), x²) < O whenever x" is a solution of (VI) and x is not. If. in addition, V satisfies (MB) or (MS), the iterates X, of AdaProx converge solution of (VI).
8

---

Published as a conference paper at ICLR 2021
Convergence Speed (stochastic gradients)
Convergence Speed (stochastic grudients)
10.
0.01
Extra gradient (sapeli overta))
Eatri-gradict (samplc instleed
0.001
Extra gradient interval
gradiett (casf ansvall
Badt-Lory (smppe evengee)
Bach-Lors (smppl avemage
0.0001
Badt-llory (isef, imsesal)
Bach Lery lover inteval)
averagy)
Unilbes compleauungg
0.00011
UniProx (pont interall
UniPves (coef, intevall
100
1000
103
1000
Figure 2: Numerical comparison between the extra-gradient (EG), Bach-Levy (BL) and AdaProx algorithms (red circles, green squares und blue triangles respectively). The figure on the left shows the methods' convergence in 100 x 100 bilinear game; the one the right shows the methods' convergence in non-ccomex/non-coomnyy covariance learning problem. In both cases, the parameters of the EG and BL algorithms have been tuned with a grid search (AdaProx has parameters tune). All curves have been averaged over S 100 sample runs, and the 95% confidence interval is indicated by the shaded area.
The importance of this result is that, in many practical applications (especially in non-monotone problems), it is more common to harvest the "last iterate" of the method (X,) rather than its ergodic average (Xr); as such, Theorem 3 provides a certain justification for this design choice.
The proof of Theorem 3 relies on non-standard arguments, so we relegate it to the supplement. Structurally, the first step is show that X, visits any neighborhood of solution point x² X' infinitely often (this is where the coherence assumption (V(x), x x²) is used). The second is to use this trapping property in conjunction with a suitable "energy inequality" to establish convergence via the use of quasi-Fejér technique as in [10]; this part is detailed in separate appendix.
7 NUMERICAL EXPERIMENTS
We conclude in this section with a numerical illustration of the convergence properties of AdaProx in two different settings: a) bilinear min-max games; and b) simple Wasserstein GAN in the spirit of Daskalakis et al. [12] with the aim of learning an unknown covariance matrix.
Bilinear min-max games. For our first set of experiments, we consider min-max game of the form of the form [(e, 6) = (0 - T o²) with 6, E R 100 and A E R 100 x R 100 (drawn i.i.d. component-wise from a standard Gaussian). To test the convergence of AdaProx beyond the "full gradient" framework, we ran the algorithm with stochastic gradient signals of the form V, +(X)+ U, where U, is drawn i.i.d. from a centered Gaussian distribution with unit covariance matrix. We then plotted in Fig. 2 the squared gradient norm [|V(&)))I of the method's ergodic average Xy after T iterations (so values closer to zero are better). For benchmarking purposes, we also ran the extra- gradient (EG) and Bach-Levy (BL) algorithms [2] with the same random seed for the simulated gradient noise. The step-size parameter of the EG algorithm was chosen as y: = 0.025/ Vi, whereas the BL algorithm was run with diameter and gradient bound estimation parameters Dg = and Mo 2.5 respectively (both determined after hyper-parameter search since the only theoretically allowable values are Do = My = co; interestingly, very large values for Do and Mn did not yield good results). The experiment was repeated S 100 times, and AdaProx gave consistently faster rates.
Covariance matrix learning.
Going a step further, consider the covariance learning game
((0 Φ) = Er-Noolxx 0x] BB. 0 [T6z). 0, E Rd x Rd.
(19)
The goal here is to generate data drawn from centered Gaussian distribution with unknown covari- ance Σ; in particular, this model follows the Wasserstein GAN formulation of Daskalakis et al. [12] with generator and discriminator respectively given by G(z) = Az and D(x) = xx oxx (no clipping). For the experiments, we took d 100, a mini-batch of = 128 samples per update, and we ran the EG, BL and AdaProx algorithms as above, tracing the square norm of V as a measure of convergence. Since the problem is non- monotone, there several disjoint equilibrium components so the algorithms' behavior is considerably more erratic; however, after this initial warm-up phase, AdaProx again gave the faster convergence rates.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
This research was partially supported by the COST Action CA16228 "European Network for Game Theory" (GAMENET) and the French National Research Agency (ANR) in the framework of the grants ORACLESS AAR-16-CE33-0004-00
and ELIOT (ANR-18-CE400 18-CE40-0030 and FAPESP 2018/12579-7), the "Investissements d'avenir" program LANR-15-IDEX the LabEx PERSYVAL YVAL (ANR-11-LABX-002500),, and MIAI Grenoble Alpes (ANR-19-P31A-000))
REFERENCES
[1] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox algorithm for variational inequalities with singular operators. In NewrlPS '19; Proceedings the 33rd International Conference on Neural Information Processing Systems, 2019.
[2] Francis Bach and Kfir Ychuda Levy. A universal algorithm for variational incqualities adaptive to smoothness and noise. In COLT 11: Proceedings of the 32nd Annual Conference on Learning Theory, 2019.
[3] David Balduzzi. Schasticn Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Gracpel. The mechanies of n-player differentiable games. ICML '18: Proceedings of the 35th International Conference Machine Learning, 2018.
[4] Amir Beck and Mare Tehoulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3165)1677175, 2003.
[5] Dimitri P. Bertsekas and Robert Gallager. Data Networks. Prentice Hall, Englewood Cliffs, NJ, 2 edition, 1992.
[6] Lev M. Bregman. The relaxation method of finding the comuton point of cunvex sets and its applicatioo to the solution of problems in convex programming. USSR Computational Mathematics and Muthenatical Physics, 7(3):200-2 217, 1967.
[7] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8 (3-4):231-358, 2015.
[8] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, Simon Lacuste-Julien. Reducing noise in GAN training with variance reduced extragradient. In NewrlPS '19; Proceedings of the 33rd International Conference on Neural Information Procexsing Systems, 2019.
[9] Gong Chen and Mare Teboulle. Convergence analysis of proximal- like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-543, August 1993.
[10] Patrick I.. Combettes. Fejéria analysis of some optimization algorithms. In Dan Butnariu, Yair Censor, and Simeon Reich (eds.), Inherendl Parallel Algorithms Feasibility and Optimization and Their Applications, pp. 115-152. Elsevier, New York, NY, USA, 2001.
[1]] Constantinos Daskalakis, Paul W. Goldberg, and Christos Papadimitriou. The complexity of computing Nash equilibrium. SIAM Journal on Computing. 39(1):195-259, 2009.
[12] Constantinus Duskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR 18: Proceedings of the 2018 International Conference on Learning Represensations, 2018.
[13] Gérard Debreu. A social equilibrium existence theurem. Proceedings of the National Academy of Sciences of the USA, 38(10)886-89) 893, October 1952.
[14] Francisco Facchinei and Christian Kanzow. Generalized Nash equilibrium problems. 4OR, 5():173-210, September 2007.
[15] Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Scries in Operations Rescarch. Springer, 2003.
[16] Lampros Flokas. Emmanouil Vasileios Vlatakis- Gkaragkounis, and Georgios Piliourus. Poincaré recurrence, cycles and spurious equilibria in cradient-descent-asee Proceedings of the 33rd International Conference on Neural Information Prucessing Systems, 2019.
for non-convex non-concave zero-sum games. In NewrlPS '19:
[17] A.V. Gasnikov, P.F. Dvurechensky, F.S. Stonyakin, and A.A. Titov. An adaptive proximal method for variational inequalities. Computational Mathematics and Mathematical Physics, 59:836-841, 2019.
[18] Gauthier Gidel, Hugo Berard, Gačtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational incquality perspective on generative adversarial networks. ICLR 19: Proceedings of the 2019 International Conference on Learning Representations 2019.
[19] Gauthier Gidel, hane Askari Iemmaat, Mohammad Pezehisk, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and loannis Mitliagkas. Negative momentum for improved game dynamics. In AISTATS '1: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
[20] Ian J. Goodfellow. Jean Pouget-Abadis Mchdi Mirza, Bing Xu. David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS '14: Proceedings of the 28th International Conference Neural Information Processing Systems, 2014,
[21] Jean San-ttptiste Hiriart-Umutt and Claude Lemaréchal. Fundamentals of Convex Analysis. Springer, Berlin, 2001.
10

---

Published as a conference paper at ICLR 2021
[22] Yu-Guan Hsich, Franck lutzeler. Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. NeurIPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 6936-6946, 2019.
[23] Yu-Guan Hsich, Franck lutzeler, Jéróme Malick, and Panayotis Mertikopoulos. Explore aggressively, update con- servatively: Stochastic extragradient methods with variable stepsize scaling, https://arxiv. http:///axxiv..gg/ab//////// 10162, 2020.
[24] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochostic Systems, 1(1):17-58, 2011.
[25] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonom, Mat. Metody, 12: 747-756, 1976.
[26] Rida Laraki, Jérôme Remault, and Sylvain Sorin, Mathematical Foundations of Game Theory, Universitext. Springer, 2019.
[27] Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR '18: Proceedings of the 2018 International Conference on Learning Representations, 2018.
[28] Yura Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization. 25(1 5:502-520, 2015.
[29] Yura Malitsky, Golden ratio algorithms for variational incqualitics. Mathematical Programmiing 2019.
[30] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payot!' functions. Mathematical Progranmiing 173(1-2):465550 January 2019.
[31] Panayotis Mertikopoulos, Christos 11. Papadimitriou. and Georgios Piliouras. Cycles in adversarial regularized learning. In SODA 'I8: Proceedings of the 29th annual ACM- Symposhun on Discrete Algorithmss 2018.
[32] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati. Chuan- Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR '19: Proceedings of the 2019 International Conference Learning Representations, 2019.
[33] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate O(1/k) for optimistic gradient and extra-gradient methods smooth convex-concave saddle point problems. https://arxiss www.ivv.or///////// /1906. 00116..1111.ppp.. 2019.
[34] Arkadi Semen Nemirovski. Information- based complexity of linear operator equations. Journal of Complexity, 8(2y: 153-175, 1992.
[35] Arkadi Semen Nemirovski. Prox-method with rate of convergence O(I/r) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15 (1):229-21,, 2004.
[36] Arkadi Semen Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on Optimization, 19(4):1574-160) 2009.
[37] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems, Mathe- matical Programming, 19992):319-44, 2007.
[38] Noam Nisan, Tim Roughgarden, Éva Tardos, and V. V. Vazirani (eds.). Algorithuicc Game Theory. Cambridge University
Press, 2007.
[39] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Progranming. 2019. URL https://doi.coo wtt..orrr....ee..1111..1 0007//11107-019-000 420- 0.
[40] Georgios Piliouras and Jeff S. Shamma. Optimization despite chaos: Convex relaxations to complex limit via Poincaré recurrence, In SODA '14 Proceedings of the 25th annual ACM-SIAM Symposiuon on Discrete Algorithous, 2014.
[41] Levrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In ICML '1: Proceedings of the 34th International Conference on Machine Learning, 2017.
[42] Leunid Denisovich Popos, A modification of the Srrow-Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5)885-848, 1980.
[43] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Tn NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Systems, 2013.
[44] Ralph Tyreell Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
[45] Gesualdo Scutari, Francisco Facchinei, Daniel Pérez Palomar, and Jong-Shi Shi Pang, Convex optimization, game theory, and variational inequality theory in multiuser communication systems. IEEE Signal Process. Mag., 27(3):35 49, May
2010.
[46] Shai Shalev-Shwartz Online learning and online convex optimization. Foundations and Trends in Machine Learning. 4 12): 2011.
[47] Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky, Mohammad Alkousa, and Alexander Titov, Generalized mirror prox for monotone variational incqualities: Universality and inexact oracle. https://arxitss http://aawvvvo./r/eee/// wttpr/wwwwoo//////e/eeee 05140, 2018.
11

---

Published as a conference paper at ICLR 2021
[48] Fedor Stonyakin, Alexander Gasnikov, Alexander Tyurin. Dmitry Pasechnyuk, Artem Agafonov, Pavel Dvurechensky. Darina Dvinskikh, Alexey Kroshnin, Victorya Piskunova. Inexact model: framework for optimization and variational incqualities. https////aai...r/abb/////// 09990 2019.
[49] John von Neumann. Zur Theorie der Gesellschattsspile. Muthematische Annalen, 100:295-320, 1928. Translated by Bargmann "On Theury Games of Strategy" Tucker and Luce, editors, Contributions Theory Games volume Annals of Mathematics Studies, pages 13-42, 1957, Princeton University Press, Princeton.
12


Reviews:
[{"review_id": "pMUi-93tzte", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors propose a variant of the extragradient method that i) achieves optimal convergence in the smooth and nonsmooth regimes, ii) allows one to work with singular operators. The paper is written very well and as far as I could check, mathematics is correct (apart from minor details which are easy to fix). Most importantly, in their analysis the authors use a new tool to work with unbounded operators, which may be of interest in its own right.\n\n\nAlthough I applaud authors for the use of innovative tools in their analysis, I would like to raise some concerns for a possible discussion.  Mostly, I am not so happy with the practical side of the paper:\n\n1) No concrete important problems intractable before by the standard extragradient but tractable by the proposed version.\n\n2) Quite bad constants. I think at some point the authors forgot one extra $M$ (see my detailed comment below), but even without it the rates are good asymptotically but bad if constants are written explicitly. I like that the authors did provide explicit formulas, but still feel that some discussion about it might be appropriate. Also I think it would help to have explicit constants in the (MS) case, though I understand that it is harder.\nFor example, no doubts that the rate interpolation is a great property. On the other hand, for the extragradient choosing right steps between $1/L$ or $1/\\sqrt{t}$ does not seem to be so difficult, especially if this choice will appear to be much faster in practice.\n\n3) Discussion of how to choose a Finsler metric is missing (apart from simple examples). For example, what if $V$ is well-defined but not Lipschitz, like $V(x) = \\exp(x)$? It is not Lipschitz, so looking at Table 1, a reader can think that this case is covered by the proposed analysis. However, it will be cowered only when a suitable $F$ is given, which (i) a non-trivial problem by itself, (ii) probably not even achievable in principle for all such $V$. In other words, can we prove that for any such $V$ described above there exist a suitable $F$? I doubt it, since an unbounded domain must matter here.\n\n4) I feel like the authors unconsciously push me to suspect that the proposed algorithm will not perform well in most cases. First, as I said above, large constants in the rate and omitted discussion of it. Second, not so illuminating numerical results (Figure 2). I believe the algorithm was designed not for solving unconstrained minimax problem. This problem is too easy for any solver (and to be fair, the comparison with other algorithms was quite limited). Where are some demonstrations of its performance for hard problems (with singular operator)? If not a real world problem, then at least the ones that motivated this paper. Not that even Example 5.3 is not very interesting, since for $V(x) = -(1/x_1, \\dots)$ and $X=(0,1]$ the solution will be $x=(1,\\dots)$, thus the singularity at zero unlikely will play any role. For instance, what about convex minimization with barriers $\\min f(x) - \\log x$ on $(0,1]$?\n\nIndependently of this, I am in favor of proposed analysis.  I think theoretical contribution is much more important here and it is OK for now if a practical performance still lacks behind. However, it would be nice and helpful to warn readers about possible obstacles and also to motivate them for further research.\n\n\nBelow I list some issues I found. Most of them are minor, but some not.\n\n\n1. page 1 \"Originally applied to variational inequalities\": I may be wrong, but I think originally it was applied to saddle point problems, though the extension is of course mostly a change of notation.\n\n2. page 1 \"if coupled with an iterate averaging scheme -- the mirror-prox...\": Not sure what the authors mean. The mirror-prox template is not needed for getting an ergodic $O(1/T)$ rate. Why do we need mirror updates for that?\n\n3. page 2, Contribution #3 \"Off-the-shelf\": I cannot entirely agree with it. While this is definitely true for rate interpolation, for addressing Lipschitz continuity this is not true. The proposed algorithm still requires a Bregman-Finsler function as an input. In other words, it requires a user to find such a function and verify one of conditions (MB) or (MS). The user just does not need a precise values of $M$ or $L$, which is good of course.\n\n4. page 2 \"As an extra feature of our analysis, we also show that the sequence of iterates...\": I would not call this as an extra feature, usually it is one of the essential algorithm's attributes in continuous optimization. Moreover, it is not entirely true, since it requires another assumption that is impossible to verify in practice.\n\n5. page 3: I think adding  \"there exists $i$\" or \"for all $i$\"  will help to make a definition of smooth/nonsmooth games more clear.\n\n6. page 3, Proposition 1: its formulation is ambiguous at the moment. Should this inequality hold for any collection of vector fields $V$ or is it sufficient to have only one?\n\n7. Eq. (8):  1 in the denominator. How sensitive is it? Obviously, it should matter for the convergence in the end.\n8. L is not present in Eq. (9b)\n\n9. page 6: How standard is the given definition of a regular Finsler metric? It is worth to add the reference, if it is standard.\n\n10. page 6 \"The KL loss is well-defined...\" I didn't understand this sentence. How is it defined when $x = 0$?\n\n11. page 6 \"and the only axiom left to verify is...\" I got an impression from above that regularity is not an axiom, but just and an additional property that is good to have.\n\n12. page 6 \"the norm could be redefined to ... without affecting our results\": I am not sure how valid is this remark. First, we should distinguish theoretical results and practical. For theory I agree, though it was needed only for Theorem 2, not Theorem 3, which possibly may be highlighted. For practical purposes though it might be undesirable to change the norm, since we want $h$ to be strongly convex w.r.t. this norm. And if we start to change $h$, then our algorithmic update will be more expensive, etc. Also it is not clear whether $V$ will still satisfy (MB) or (MS): the dual norm will be also different.\n\n13. page 6 \"Metrically smooth\" definitions is not clear: it is not symmetric to $x, x'$. Maybe some discussion?\n\n14. page 6, Example 5.3: $V$ is not monotone, thus it contradicts to the \"blanket assumption\". Considering $V$ with $-$ will be better.\n\n15. page 7 \"Second, the main difference between Definition 2 and other definitions of Bregman proximal mappings\": I think the authors meant Bregman function, the definition of the proximal mapping is standard.\n\n16. I think it is better to mention all assumptions in the statements (even just as abbreviation or references). Currently, they are put everywhere in the paper. For a reader who wants to quickly skim the main results but will not read a full paper it will be quite helpful.\n\n17. page 7, Th.2: Is set $C$ is fixed or not? The same for a solution $x^*$. And of course the condition is a bit strange.\n\n18. Why not to swap Th.2 and 3? The latter is more important and doesn't require an additional assumption. The former looks more like a side result.\n\n19. page 8, Figure 2: What does it mean tuned or untuned for Extragradient? Larger step? Why do we care about it, isn't it obvious that the algorithm should diverge? Why not to take $\\gamma =\\frac{1}{|A|}$? How $A$ was generated? It is worth to have a better accuracy for plots in right picture. How the problems in right were generated is not clear. If $V$ was contaminated by noise, does it imply that $V$ is not monotone?\n\n20. page 8, \"... Fig. 2 confirms that UniProx can provide a fruitful template for adaptive min-max optimization methods that attain optimal rates in smooth/non-smooth problems.\" Two plots for a smooth problem unlikely can confirm a smooth case and certainly not a non-smooth one.\n\n21. page 12, Lemma B.1. Note that there wasn't given a definition of Bregman function, but only Bregman-Finsler one.\n\n22. page 12, \" if and only if $t=0$\": why? what if $p=x$. Next sentence: $\\psi$ is a function and not a continuous selection. Next: what does it mean for $\\phi$ to be differentiable at $t=0$ or $t=1$?\n\n23. page 13: I don't think notation $X^\\circ$ was introduced before. What is a local Bregman function?\n\n24. page 13: I did not understand how condition (C.2) is more general. Note that the definition of regularity uses asymptotic language, that is when $|x'-x|_x \\to \\infty$. The condition (C.2) is global on the other hand. Of course, there is some intersection of two conditions, but not in general. Maybe instead of regularity, the authors should consider (C.2) definition from the very beginning.\n\n25. Lemma C.1, page 14. I have some difficulties with the proof of this lemma. First, I didn't understand the first sentence: why changing the reference point from $X_t$ to $X_{t+1/2}$ will be sufficient for us? Second, I did not understand the derivation (C.7). Apparently the authors use condition (C.2) but they forgot an extra factor in the RHS, i.e, there should be $M$ next to $\\beta$. This will worsen the final bound of course.\n\n26. Lemma D.1: In the main part the authors use notation $\\gamma_\\infty$ instead of $\\alpha$.\n\n27. page 16, Eq.(D.12): it should be $\\gamma_{T+1}^2$ in the LHS.\n\n28. I think that parts of the proof of Lemma D.1 can be reused in the proof of Theorem 3.\n\n29. Eq. (D.22): the RHS should be divided over $\\sum \\gamma_t$.\n\n30. page 18, \"Hence, $\\gamma_t$ is non-increasing...\". This fact is definitely not a consequence of the equation above. Also the equation below should have $\\gamma_{t+1}^2$.\n\n31. page 18, \"For the second term...\": that term should be have a dual norm (star is missing). Also everywhere below.\n\n32. page 18: It makes sense to recall what $C$ is. Note that (C.13) for this is good, but (C.4) is not, since it uses a different reference point. Do we actually need (C.4)? Also probably having a set $\\mathcal{C}$ and a constant $C$ in the same proof is not the best notation choice.\n\n33. page 18, \"we have the following upper-bound\": lower.\n\n34. page 18, Eq. (D.30): Note that in the original statement of Th.3 there were exact constants in $O()$.\n\n35. page 18, Eq.(D.31): Why do we need this equation? I think we should apply Lemma D.1 to Eq.(D.24). Otherwise it is not clear how the bound for the gap follows.\n\n36. page 19: I didn't understand (Eq.D.32). Why $\\mathrm{dom} (V) = \\mathrm{dom} (h)$ and why not just use the same compactness argument as above? Also, it should be $p$ and not $x^*$.\n\n37. page 19, (Eq.D.34): $\\gamma_t^2$ is redundant.\n\n38. page 20, (Eq.E.4): $t$ and $j$ are mixed.\n\n39. page 20, Eq. E.8-E.10: Almost the same things are already proven in Lemma C.1. The explanations there are also more transparent.\n\n40. page 21: Wrong reference in Remark 2.\n\n41. page 21: Proposition E.1: Why now equilibrium set and not a solution set?\n\n42. page 21: I think both in the statement of Prop E.1 and in Eq.(E.19) the extra condition from Th.2 should be mention. Otherwise I don't understand how E.19 was obtained.\n\n43. page 21: Summation in Eq.(E.20) should start not from $t=1$. Liminf in E.19 means that that inequality holds for all $t$ starting from $t=t_0$.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "k3iqgx5Mjht", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors present an adaptive stepsize strategy for extragradient in order to recover both the ergodic 1/sqrt(T) in the nonsmooth case and 1/T in the smooth case (without the knowledge of the Lipchitz constant). The presented method is rather simple but seems effective both in theory and in practice.\n\nThe paper is well written: the motivation, context, and basic definitions are especially clear. The algorithm is intersting and the analysis seems sound. I'm in favor of acceptance.\n\nConcerns\n---------\n\n* Could the authors comment on X in 2.3? To be compatible with the projection as used in the EG, it probably has to be closed and known in advance. With the inclusion between K and its relative interior, this seems to imply that K has to be closed somehow. \n\n* The auhors mention that their stepsize strategy adapts to local Lipschitz constants but since the points are uniformly averaged since iteration 1, the local geometry may be a bit lost. Would it be possible to do some kind of restarting to mitigate this effect?\n\n* I have troubles understanding the statemeent of Theorem 2, notably what does gap(*)<0 means or what are the implication of C being relatively closed and disjoint.\n\n\n\nMinor Comments:\n- First paragraph: 9 citations in a single pair of brackets is not so informative, please consider breaking it down to smaller bits organized bu great topics. (Same remark at the beginning of Section 3).\n- Caption of Table 1: algortihm -> algorithm\n- In related works: the notions of \"interpolation\" (as defined in the caption of Tab.1) and \"divergent operators\" (in the sense of coercive at the boundary?) may not be so clear to the reader. An additional explanation in the text or a footnote would be appreciated. \n- Below (8), I think the authors mean \"lim inf \\delta_t >0\" and not \"lim inf \\gamma_t >0\"\n- The examples sometime end with a small triangle, sometimes not.\n- It is a small detail but gamma_t is defined in (8) but gamma_{t+1} is defined in (UniProx), this could be made uniform.\n- Could the authors comment on the computability of the proximal mapping (16)? Since X may not be closed, there may be problems at the border. This is probably handled by h as in the example but I am not sure it is implied by the conditions (eg the stong convexity in the local metric). \n- Fig. 2 right appears poorly when printed.\n- I would have appreciated a last-iterate vs Average iterate behavior comparison as well as locally smooth/nonsmooth examples in the experiments. (For instance, instead of the stochastic case which seems a bit off topic).\n- Parts of the proof in the appendix could be more detailed:\n-- Precise that you use regularity in C.7\n-- When you use Fenchel-Young, you introduce a K without explicitly mentioning it (eg D.8 or D.22).\n-- Precise the derivations between D.26 and D.27 (precise that Lemma C.1 is used)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "auFhGwZG6S9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper propose a novel algorithm that solves the min-max problems and games based on the extra gradient (EG) framework. One of the main goal of this paper is to achieve the optimal convergence rate for both smooth/nonsmooth setttings without assuming the Lipchitz continuity/boundedness conditions. A \"Bregman-Proximal\" step was introduced to take place of the traditional Euclidean norm projection norm to depict the geometry or the smoothness properties of the problem. Furthermore, the authors adopt an adaptive step size scheme into the \"Mirror-Prox\" step to achieve the optimal convergence rate under both settings. \n\nStrengths: \n+ Achieves the optimal convergence rate in both the smooth case without the Lipchitz continuity assumptions ($O(1/T)$) and the non-smooth case without the boundedness assumption ($O(1/\\sqrt{T})$)\n+ \"Off-the-shelf\" design frees the users from tuning parameters\n+ The main improvement over previous Bregmen Mirror Prox algorithms (K Antonakopoulos 2019) is the novel nonsmooth analysis under the MB condition\n\nWeaknesses:\n- The authos made an effort to show evaluation results on a basic synthetic example, but this is less challenging.\n- Some of the details in the experimental sections are missing, for example the choice of the matrix A.\n- The analysis of the convergence rate of a mirror step under the MB condition is an application of the techniques in AMP\n\nIn summary, the UnixProx algorithm achieves the optimal $1/T$ convergence or $1/\\sqrt{T}$ convergence under the smooth/nonsmooth settings, while it does not require Lipchitz/Boundedness assumptions, which is applicable to problems without prior knowledge of the objective smoothness. This work can potentially help in solving games and reinforcement learning problems. However, the authors are encouraged to provide more experimental results to illustrate the practical impact of relaxing the assumptions.\n\nQuestion:\ncan the convergence result in Theorem 1 be interpreted as the convergence result in Theorem 4 when K goes to $\\infty$?\nWithout the adaptive step size mechanism designed in your paper, will the same convergence rate still hold under the same assumption? Will the same result hold with constant step size or for example $\\gamma_t = 1/\\sqrt{t}$?", "extra_scores": {}, "extra_text": {}}, {"review_id": "7SePegHKcJ", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary. \nThis work proposed a stepsize for the extragradient/mirror-prox method that works both in smooth and non-smooth settings. The stepsize is based on the empirical values of gradient/operator differences, and mirror maps are used to allow for non-euclidian geometry such as KL divergence. The paper offers us three convergence results: 1 bound for the extragradient update (no mirror map) and 2 bounds for the mirror-prox update (convergence of iterates without a rate and convergence of the restricted gap with rates). The theory is followed by simple randomly-generated problems, which is ok for justifying the theory but can't serve a significant contribution on its own. \nOverall, I enjoyed reading this paper and would recommend it for acceptance if not for two issues: 1) it seems to have low relevance to ICLR and I think it will not get much attention; 2) the stepsize is by definition upper-bounded by 1, and therefore will be suboptimal whenever the optimal stepsize is larger than 1.\n\n### Relevance\nThe paper starts off with a number of interesting applications: GANs, reinforcement learning and adversarial learning. Unfortunately, it's never explained how the proposed algorithms are relevant to these applications. I think it's fine that the theory is derived for monotone operators, since many algorithms designed for convex objectives often work on nonconvex problems as well. However, unlike the algorithm of Bach and Levy, the one presented here does not allow for stochastic gradients, which is crucial in practice. And it seems to me that the motivation in the introduction is disconnected from the rest of the paper, for instance, it's not obvious why the projection step in (EG) plays any role.\nI'm particularly confused by the importance of the \"Non-Lips. / Unbounded\" property of the stepsize. For instance, Table 1 mentions as an application the D-design, which is not a minmax problem, it's a minimization problem [1] (please correct me if you meant something else). Another example is the KL minimization problem, which is again not a minmax problem, and I do not see why it's of any relevance to the conference. I also think that this problem can be solved by methods from [1, 2] (depending on if it's smooth or not) Finally, the problem in Example 5.3 is also not motivated in this paper. Can the authors elaborate on its importance or give an example of some intereseting problem with minmax/VI structure?\n\n### Suboptimality of the stepsize\nThe constant 1 in the stepsize, namely in the denominator in Equation (8), makes me skeptical about the method's universality. Due to this choice, we always have gamma_t <= 1, which might not be a good choice. Let's say we take an objective with smoothness constant L=10^(-4), then one can use stepsize gamma_t = 10^4, so the proposed stepsize will be quite suboptimal. I think the reason the authors used constant 1 is that it allows them to claim that the method is parameter-agnostic, but the cost of this choice is that it's not really adaptive. To make it adaptive to the problem properties (smoothness or gradient bound), one needs to have some problem-dependent constant in the denominator, but this means we exchanged one parameter (the stepsize itself) for another (the constant in the denominator).\n\nThe fact that the stepsize monotonically decreases is another flaw. RMSprop and Adam have been more successful than Adagrad exactly for this reason, and at least for GRAAL the stepsize can increase even close to the end of the training. In terms of GANs, it has been mentioned in several works, for example [3, 4, 5] that extragradient updates work better when combined with Adam stepsizes.\n\nThis is why I have strong doubts about the universality of the stepsize and tend to suggest rejection of this paper.\n\n#### Minor issues:\nWhat is a \"divergent operator\"? This term does not seem to be introduced anywhere. Moreover, one of the references for its importance (the authors mention [1, 21, 55]), [21], has a wrong title (the correct one is \"An Adaptive Proximal Method for Variational Inequalities\").\n\nThe experiments are only a small contribution as they are only given to support the theory, but I still think it would be better if the authors provided their code.\n\nIn Lemma 1 of the main part, the authors use the notation $\\gamma_{\\infty}$, but in the appendix, they use $\\alpha$. Please make the notation consistent.\n\nAfter formulating Lemma 1, the authors write \"UniProx enjoys an accelerated O(1/T) rate of convergence under (MS)\". I find the word \"accelerated\" to be confusing since O(1/T) is the standard rate under (MS), I suggest the authors clarify this place.\n\nTypos:\nWhen going from Equation (D.19) to Equation (D.21), you forgot to divide the right-hand side by $\\sum_{t=1}^T \\gamma_t$.\nPage 18: \"we readily get that under (MB) we get that:\" -> \"we readily get that under (MB):\"\nPage 22: \"Therefore, y letting T\" -> \"by letting\"\nIn the proof of Lemma F.1: \"The lemma will proved by induction\" -> \"will be proved\"\n\n[1] Lu et al., \"Relatively-Smooth Convex Optimization by First-Order Methods, and Applications\"\n[2] Lu, \"\"Relative-Continuity\" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent\"\n[3] Gidel et al., \"A variational inequality perspective on generative adversarial networks\"\n[4] Mishchenko et al., \"Revisiting Stochastic Extragradient\"\n[5] Chavdarova et al., \"Reducing noise in GAN training with variance reduced extragradient\"", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new step size rule for the extragradient/mirror-prox algorithm, building upon and improving the results of Bach & Levy for the deterministic convex-concave setups. The proposed adaptation of EG/Mirror-prox -- dubbed AdaProx in the submitted paper -- has the rate interpolation property, which means that it provides order-optimal rates for both smooth and nonsmooth problems, without any knowledge of the problem class or the problem parameters for the input instance. The paper also demonstrates that the same algorithm can handle certain barrier-based problems, using regularizers based on the Finsler metric.

The consensus of the reviews was that the theory presented in the paper is solid and interesting. The main concerns shared by a subset of the reviews were regarding the practical usefulness of the proposed method. In particular, the method exhibits large constants in the convergence bounds and cannot handle stochastic setups. Further, the empirical evidence provided in the paper was deemed insufficient to demonstrate the algorithm's competitiveness on learning problems. If possible, the authors are advised to provide more convincing empirical results in a revised version, or, alternatively, to tone down the claims regarding the practical performance of the method.
Decision: Accept (Poster)