Alternating Mirror Descent for Constrained Min-Max Games
Authors: Andre Wibisono
Molei Tao
Georgios Piliouras
Venue: NeurIPS 2022 Accept (2022)
Keywords: Min-max games
regret bound
mirror descent
alternating method
Hamiltonian
symplectic integrator

Abstract: In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as an alternating discretization of a skew-gradient flow in the dual space, and use tools from convex optimization and modified energy function to establish an $O(K^{-2/3})$ bound on its average regret after $K$ iterations. This quantitatively verifies the algorithm's  better behavior than the simultaneous version of mirror descent algorithm, which is known to diverge and yields an $O(K^{-1/2})$ average regret bound. In the special case of an unconstrained setting, our results recover the behavior of alternating gradient descent algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).

Alternating Mirror Descent for Constrained Min-Max Games
Andre Wibisono
Molei Tao Department of Mathematics
Department of Computer Science
Yale University andre. satre.wibisonn@yylee edu
Georgia Institute of Technology mtao@gatech. edu
Georgios Piliouras
Engineering Systems and Design Singapore University of Technology and Design georgios@sutd. edu.
Abstract
In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as alternating discretization of skew- grwddeteient flow in the dual space, and use tools from convex optimization and modified energy function to establish an O(K-2/3) bound on its average regret after K iterations. This quantitatively verifies the algorithm's 's better behavior than the simultaneous version of mirror descent algorithm, which is known diverge and yields an O(K-1/3) average regret bound. In the special case of an unconstrained setting, our results recover the behavior of alternating gradient descent algorithm for zero-sum games which was studied in 2
Introduction
Multi-agent systems are ubiquitous in many applications and have gained increasing importance in practice, from the classical problems in economics and game theory, to the modern applications in machine learning, in particular via the emergence of learning strategies that can be formulated as min- max games, such as the generative adversarial networks (GANs), robust optimization, reinforcement multi-agent systems, interaction between the agents can exhibit nontrivial global behavior, even when each agent individually follows simple action such as a greedy, optimization-diee -rrivennnndreennnnoon strategy 7 S M This emergence of complex behavior has been recognized one source of difficulties in understanding and controlling the global behavior of multi-agent game dynamics 2 [5]
learning, and many others [[]
16 23
Even in the basic setting of unconstrained two-player zero-sum game with bilinear payoffs, this emergence of non-trivial behavior already presents some difficulties. It now well-known that each player follows classical greedy strategy, such as gradient descent, and if they make their actions simultaneously. then their joint trajectories diverge away from equilibrium and lead to increasing regret; however, the average iterates still converge to the equilibrium and yield vanishing average regret with decreasing step size 66 marked contrast to the case of single-agent optimization, in which greedy strategies guaranteed to converge. This leads to variations the greedy strategy to correct the diverging behavior and help
& 7 This behavior challenges our intuition and is in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the trajectories to converge to equilibrium, for example via optimistic or extragradient versions of gradient descent [TC 17. which can be seen as approximations of the proximal (implicit) gradient descent 19
Another variation of the basic greedy strategy is when each player follows gradient descent, but they make their actions in an alternating fashion (i.e. one at a time, rather than simultancously), as studied in [2]. This technique is particularly useful for machine learning applications where the state of the system can be very large with several billions of parameters as one does not need extra memory to store intermediate variables, required both by simultaneous updates as well as extra-grast -xtra-gradieet methods. The resulting alternating gradient descent algorithm has a markedly different behavior than in the simultaneous case. As shown in (2). the trajectories of alternating gradient descent turn out to cycle (stay in a bounded orbit), rather than converging to or diverging away from equilibrium. This behavior mimics the ideal setting of continuous-time dynamics, which is the limit as the step size goes to 0, in which case the orbit of the two players cycles around the equilibrium and exactly preserves the "energy function", which in this case is defined to be the distance to the equilibrium point, achieving average regret bound O(T after (continuous) time T [ In discrete time, alternating gradient descent does not exactly conserve the energy function; instead, conserves a modified energy function, which is perturbation of the true energy function with a correction term which is proportional to the step size. This implies that alternating gradient descent has a constant regret for any step size, and thus yields an average regret bound of O(K-!) after K iterations, which matches the continuous-ting behavior; see 2 for more details.
The results above raise the question of what we can say in the constrained setting, when each agent can choose an action from a constrained set. An instance of natural occurrences of such constraints is when mixed strategies are used, which corresponds to probability simplex constraint. One popular strategy, inspired by optimization techniques, is that each agent now plays the mirror descent algorithm for constrained minimization of their own objective function. Mirror descent is closely related to the Follow the Regularized Leader (FTRL) algorithm online learning, which has Hamiltonian structure in continuous time 4 1 In the idealized continuous-time setting, if both players follow the continuous- titmueeuuu-teeeeeee version of mirror descent dynamics, then their trajectories cycle around the equilibrium, and conserve an "energy function"" in the dual space, which is now defined to be the sum of the dual functions of the regularizers; this leads to a constant regret, and yields OT--1) average regret bound after (continuous) time T [ In this harder constrained setting, one would hope to weave a single thread connecting in an intuitive manner the behavior of continuous dynamics with multiple distinct diseretizations. In discrete time, if the two players follow the simultancous version of mirror descent, then their trajectories diverge from equilibrium, and yields a (K31/22) bound on the average regret. If both players follow the proximal (implicit) mirror descent algorithm, then as we show their trajectories converge to the equilibrium, resulting in simple a O(K average regret bound, which matches the contimuous-time behavior. While the O(K-1) average regret bound is known to extend to general games (55 under clairvoyant multiplicative weights updates, which is a closely related algorithm to proximal mirror descent, such methods require coordination among the players to solve the implicit update. Nevertheless, there are simpler variations such as the optimistic or extra-gradient which can get Ö(K-1) convergence rates in general games y where Ô hides polylogarithmic dependence.
In this paper, we propose and study the alternating mirror descent algorithm for two-player zero-sum constrained bilinear game, in which the two players take turns make their moves following the mirror descent algorithm. We show that the total regret of the two players can be expressed in terms of modified energy function, which generalizes the modified energy function in the unconstrained setting (see Theorem 4.5). Recall in the unconstrained setting, the modified energy function is exactly preserved (2] In the constrained setting, we prove bound on the growth of the modified energy under third-order smoothness assumption on the energy function (see Theorem 4.4p. This yields an OKK 2/3) bound on the average regret of the alternating mirror descent algorithm, which improves on the classical ((K average regret bound of the simultaneous mirror descent algorithm.
As an analysis tool, we study alternating mirror descent algorithm as an alternating discretization of a skew-gradient flow. In continuous time, we can study the continuous-time mirror descent dynamics in the dual space; this dynamics corresponds to the skew-gradient flow of the energy function, which conserves the energy and explains the cycling behavior, as we explain in Section [ In discrete time, since the energy function is convex, the forward discretization of the skew skew-gradient
2

---

flow is proved to increase energy; this corresponds to the diverging behavior of the simultaneous mirror descent algorithm; see Section[B.] In contrast, the backward (implicit) discretization of the skew-gradient flow is proved to decrease energy; this corresponds to the converging behavior of the proximal/clairvoyant learning; see Section B.2 Finally, as in the unconstrained case, the alternating discretization of the flow follows the continuous-time dynamics more closely, leading to improved bounds.
Another reason that we expect the alternating mirror descent algorithm to work well is a connection to symplectic integrators. In the special case when the payoff matrix in the bilinear game is the identity matrix the continuous-ting time mirror descent dynamics becomes a Hamiltonian flow, i.e. it has a symplectic structure, and the energy function becomes the Hamiltonian function that generates the flow (hence conserved). In discrete time, the alternating mirror descent algorithm corresponds to the symplectic Fuler discretization in the dual space, which also conserves the symplectic structure. A remarkable feature of symplectic integrators is that they exhibit good energy conservation property until exponentially long time [2]. Recently, symplectic integrators as well as connections between algorithms and continuous-time dynamics, have been shown to be highly relevant in the optimization settings for design of accelerated methods 14
30
20 Specifically, by preserving specific PS
continuous symmetries of the flow, symplectic integrators stabilize the dynamics and allow for larger step sizes for fixed accuracy in the long run. This intuition gives a geometric interpretation to "acceleration". Our novel connection between game theory, alternating mirror descent dynamics and symplectic integrators opens the door for further cross-ferts coos-fertilization between these areas.
2 Preliminaries
In this paper we study the two-player zero-sum game with bilinear payoff:
min max pl Aq.
pEP OEQ
Here P C R and Q C R" are closed convex sets which represent the domains of the actions that each player can make, and E _mxx is an arbitrary payoff matrix. When the first player plays an action p E P and the second player plays E Ey=1 Asj. which they want to minimize; while the second player receives loss -p Ag. which they want to minimize (equivalently, the second player wants to maximize their utility pT Aq).
Q, the first player receives loss p Ag
An objective of the game to reach the Nash equilibrium, which is pair (p", E P x that satisfies, for all (p. 9) E P X Q:
Aq S (T')T Ag" Sp Sp_Aa Ag".
By von Neumann's 's min-max theorem (2). Nash equilibrium always exists (but is not necessarily unique) as long as P and Q are compact, which is the case here.
One way to measure convergence to equilibrium is via the duality gap dg: P x Q + IR given by dg(p, q) = -max QEQ
p
Aq
Aiim p Ag.
PEP
One can check that dg(p. q) 2 for all (p. E P P Q, and moreover, dg(p", ,q") = 0 if and only if (p". .q") is a Nash equilibrium.
In the execution of the zero-sum game, each player follows some algorithm in discrete time (or some dynamics in continuous time). Depending on the precise specification of what algorithms they play and how they play it, the iterates of the actions (Pk, 4s) may not converge to the Nash equilibrium. However, we expect the average iterates (pK, πK) to converge the Nash equilibrium, as measured by the duality gap: dg(pk, : .K) + 0 as K + cc. Furthermore, typically the duality gap of the average iterates are related the average regret of the two players. Therefore, if both players follow a no-regret algorithm (so the average regret vanishes asymptotically), then their average iterates converge to Nash equilibrium. Thus, we are interested in bounding the rate at which the average regret of the two players converges to 0. See Section 3.2 for more details.
When the payoff matrix is arbitrary, the dynamics has non-canonical Hamiltonian structure.
3

---

Unconstrained case. A special case is the unconstrained setting when P = R" and Q I... Here the equilibrium at 0). A natural strategy is for each player to follow gradient descent to minimize their own loss functions. As explained in the introduction, the behaviors of the iterates can vary depending on how the two players take the actions: If they both follow simultaneous gradient descent, then the iterates diverge; if they follow simultaneous proximal gradient descent, then the iterates converge; if they follow continuous-ting gradient flow, then the iterates cycle; finally, if they follow alternating gradient descent, then the iterates cycle and conserve modified energy function.
Constrained case. The main question we address in this paper is whether the different behaviors we observe in the unconstrained setting above carry over to the constrained setting, when P & R or Q C Rn (or both) are proper subsets of the Euclidean space. As an example, we may consider P Am and @ = A., where A. = {I E R. I; 2 0. -im 24 = }} is the probability simplex in Rmm, and similarly A., is the probability simplex in IR"; these correspond to the setting where each player chooses a random action among a set of discrete choices. However, our analyses and results hold for general constraint sets.
In this constrained setting, a natural strategy is for each player to follow constrained greedy method, instead of using gradient descent. Following techniques in optimization, we consider the case when each player follows the mirror descent algorithm (11 minimize their own loss functions over their constrained domains.
Mirror descent set-up. We assume that on the domain P C R we have a strictly convex regularizer function Φ: P > Ie which is a Legendre function (26 which means Φ continuously differentiable. || |((() - oo as p approaches the boundary öP of P, and V is bijection from P to the range Vo(P) S R". Here the gradient Vo(p) E I is the vector of partial derivatives.
Let D2: P x + R be the Bregman divergence of c, defined by
Dp(p. = <(p) <(p) (Vo()).--) p)
where (u. v) = TTu v is the fg-inner product. Since & is strictly convex, we have that (p p) 2 O, and (p, 0 if and only if p p. Note that Bregman divergence is not necessarily symmetric: in general, () + p)) The idea of mirror descent [2]] is to use the Bregman divergence (p p) measure "distance" (albeit asymmetric) from p p on P. For example, the unconstrained setting when P Rm if we choose <(p) _/2 |lp13 where ||pl| p is the (squared)
2--nomm, then the Bregman divergence recovers the standard disttaanc (p. p) 1 llp 2l2. which is symmetric. On the other hand, if Am C R and we choose (p)) >x p; log to be negative entropy, then the Bregman divergence is the relative entropy or the Kullback-Leibllr
divergence: (v, = Σ pr log P: which is not symmetric.
Similarly, we assume that on the domain Q C R." we have a strietly convex regularizer function vi: Q IR. which is a Legendre function, so is continuously differentiable, [[Vx((q)] + oc as + aQ and Vib is a bijection from Q to the range (+(()) C R". Let De: : Q x Q + be the
Bregman divergence of s) defined by (s 7) (4)) (()) (Vv(ū). q Φ)
3 Algorithm: Alternating Mirror Descent
We consider the Alternating Mirror Descent (AMD) algorithm where each player follows the mirror descent algorithm to minimize their own loss function, and they perform the updates in an alternating fashion (one at a time).
Concretely, the AMD algorithm starts from an arbitrary initial position (po, no) E P x Q. At each iteration & 2 O, suppose the players are at position (pk, qx) E P x Q. Then in the next iteration k + 1, they update their position to:
Pk+1 = arg min pep {
p T Aqu 1/ D. pk)
(1a)
M++1 arg min r
Pk+ Ph Ag + 2.
(Ib)

---

where 17 O is step size. Observe the first player (the player) makes the update first using the current value qui then the second player (the q player) updates using the new value Pk+1- We assume both players can solve the update equations ( which is the case because they can choose the convex regularizers Φ, Mh. Observe that we can write the optimality condition for AMD as:
Vo(pu+1) = Vo(pk) - -nAqs V (g+(++1) = (v(()) + +nA* Pk+11
(2a)
(2b)
In Section we interpret AMD an alternating discretization of skew-gradien flow in dual space.
3.1 Continuous- Time Motivation: Skew-Gradient Flow
One way to derive the alternating mirror descent algorithm ① is as a discretization of what we call the "kew-gradient flow in continuous time. Concretely, let us define the dual functions (convex conjugate) of the convex regularizers x² IR" + and v²": IR" - IR given by:
('(x) = sup (p. σ) - x(p)
pEP
w (v) sup (g. y) 21)
Q
We call I and RR' (the domains of Ø² and 1/²) as the dual space. Recall that the gradient of the dual function is the inverse map of the original gradient: VØ" (Vo) and V (Vb)
Given (Pk: qx) E P Q, we define the dual variables (IR, yk Ru by:
Th = Vo(pk) V& Ve((g))
Pk = VΦ" (**(
Qk (y))).
Suppose (px, qu) P Q evolves following AMD D.. so they satisfy the optimality condition ?
Then the dual variables (Ii, Wee E gm+" evolve by the following algorithm:
Tk+1 = 2k 7AV 1 (yk)
(3a)
Vk+1 = + 7 (*k+1).
(3b)
We refer to AMD update in the dual space 3 above as the alternating method.
Continuous- limit. Observe that as the step size 7 O, the update equation for AMD in the dual space recovers the following continuous-time dynamics for (X,, Y,) E RM
X, = - - (Yr)
(4a)
Y, A vo*(X))
(4b)
Here X, = d _x,, is the time derivative. We call the dynamics by the energy function:
4 as the skew-gradient flow, generated
dt
H v) (z)x) + (v))
(5)
particular feature of the keewggradient flow that it preserves the energy function over time:
HX,,, Y,) = (X,,, Yo)
for all 2 O; see Section for further detail.
AMD in dual space alternating discretization of skew-gradient flow. We view the update equation ( as performing an alternating discretization of the Keedienddeent flow 4 Since the energy function is separable, these updates explicit, and correspond performing alternating mirror descent in the dual space 3 See Section 4.1 for more detail.
3.2 Regret Analysis of Alternating Mirror Descent
To measure the performance of the algorithm, we can analyze the regret of each player, which is the gap between their observed losses and the best loss they could have achieved in hindsight, using fixed (static) action. We define the regret of the alternating mirror descent algorithm (I as follows.
5

---

Regret definition. From iteration k to iteration & + 1 of the algorithm, there are two half steps that happen: The first player updates from Pk to Pk+11 (while the second player at qı)), then the second player updates from qs to @k++1 (while the first player is at pk+1). Thus, the first player observes Qk twice: once when the first player at Pk, and once when they are at p&+1- Therefore, we define the regret of the first player after K iterations, with respect to static action P. to be:
K-1
K-1
R1 (p)
= Σ
Pk + Pk+1
Aqk
Σ Aqa. k=0
(6)
2
k=0
Similarly, the second player observes Pk++1 twice: once when the second player is at qu. and once when they are 9++1. Therefore, we define the regret of the second player after K iterations, with respect to static action q E Q, to be:
K-1 R2, (q) == Σ Pk+1 Aq
K-1 Pk+t
IK + 9k-11
EpE+ k=0
2
Note that in the unconstrained case, this recovers the regret definition of the alternating gradient descent algorithm of [ (up factor of & for normalization).
We define the cumulative regret of both players after K iterations, with respect to static actions (p. 9) E P Q. to be:
Rx g) == R1,x(1) (p) (q)
Finally, we define the total regret of both players after K iterations be the best cumulative regret in hindsight:
RK == sup (px))eXx
RK(p,9).
Regret and duality gap.
We define the average iterates of the players after K iterations to be:
PK
Σ Pk+1
and
@K
Σ 4k-
K
Note that we shift the index of the first player by one, since the second player moves after the first player. Then observe that the total regret is related to the duality gap of the average iterates. We provide the proof of Lemma 3.1 in Section C.I.I
Lemma 3.1. Under the above definitions, for any K 1,
1 K
1 2K (P) Ago - PK Aqæ).
dg(px. [K)
RK
(8)
If are in the constrained case with bounded domains, then the last term in ( is bounded, so the behavior of the duality gap is controlled by the growth of the total regret Rx-
Bound on regret. If both players follow the alternating mirror descent algorithm with smooth convex regularizers, then we can bound the total regret Rx as in Theorem 3.2 below. The proof uses the interpretation of alternating mirror descent as alternating discretization of the skew-gradien flow, and a relation between the total regret and the change in the modified energy function, as we explain in Section 4.333 Smoothness of the regularizers allow us to control the discretization error, which translates to a bound on the regret. We provide the proof of Theorem 3.2 in Section C.1.2
Here || is an arbitrary norm, We define the operator norm of (z)(2) (which is a 3-tensor) by ||V |lop = sup||a|s- V (x)((, U, v]]. Let Omax be the maximum singular value of A.
Theorem 3.2. Assume P and Q are bounded, so ||p|| < M and ||q]| S M for all p E P, P Q for some 0 < M < 0o. Assume the dual functions o² and 1/* are M -smmotth of order 3, which means (Vo''(V S M and V (Vv(g))) llop I M for all p E P. q Q. Suppose both players follow alternating mirror descent ① with step size
0 from (Pu. (o.qu) P x Q. Then the total
regret at iteration with respect to any strategy (p. g) E P x Q is bounded by:
Rx g) Dolp-Po) + Dp(g.00 go)
4 403 M1
2 K.
n
3

---

In particular, suppose we start from (po, qu) with sup Ds(p. Po) < and sup (g go) < co.
pEP
qEQ
Given a horizon K, with step size r = ( (K-1///,, the total regret is
R O(K))))
In the Fuclidean case, Theorem 3.2 recovers Theorem 2]. Theorem 3.2 also holds when P, are probability simplices with entropy regularizers, if we start from Po. 9u with full support.
By Lemma 3.1
and Theorem
we have the following corollary (proof in Section
Corollary 3.3.
Assume the same assumption as Theorem 3.2 2
If both players follow the altrratingg
mirror descent
1 with step size O(K-1/3) then the duality gap of the average iterates decays
as dg(px, 4x) O(K-2/3)
Compare the result above with the simultaneous mirror descent algorithm for min-max games, which has the classical OKK-)/2) convergence in the duality gap of the average iterates, thus highlighting the advantage of using the alternating mirror descent algorithm (at the cost of a third-order smoothness assumption for the analysis).
Skew-Gradient Flow and Discretization
In this section we discuss the kkew-gradient flow and its discretization. We apply this to analyze the alternating mirror descent algorithm in the dual space R x R
Recall in the dual space, we have the dual functions of the convex regularizers f : 6² R
and g 4² 1 R. We define the energy function H: Rm+ by:
H(x,y) = f(z) gVv
for all = (x, v) E IR' x R". Note f = 6= and g * are convex, being convex conjugate functions. Furthermore, since we assume and yb are strictly convex, / and g differentiable. Therefore, И is a differentiable convex function.
Let IR (g(+t))x(maa)) be the skew-symmetric matrix:
A
-AT
where recall A mR is the payoff matrix for the min-max game.
We consider the skew-gradient flow generated by the energy function H and the skew-symmetric matrix J. which is the solution to the differential equation:
2, = (V.)
(9)
starting from an arbitrary Ze E Rm+n If we write Z, (X,, Yi), then the components follow the skew-gradient flow dynamics as in 4
x; = - Y, = A
A feature of the skew-gradient flow is that since the velocity is orthogonal to the gradient of the energy function, the skew-gradient flow preserves energy function. (In contrast, recall the usual gradient flow 2, (Z.) decreases the energy function.)
Lemma 4.1. Along the skew- rredierad flow 3. H(Z)) = (Z))) for all 2 0.
Proof. We can check that the energy function H(2)) has zero time derivative along the flow
d
H(z)) (Z,) 2,)
(2.),,, -V
(10)
dl
where the last equality above holds because T defines a zero quadratic form.
Some our results below hold for general skew-symmetric matrix (not necessarily in block structure). For simplicity, we focus on the separable case above for the min-max game application.
In continuous time, the skew-gradient flow dynamics t preserves the energy function. In discrete time, the behavior of the energy function can vary depending the discretization method used.
7

---

Forward Discretization. A forward discretization of akew-gradient flow corresponds to the two players performing the simultaneous mirror descent algorithm for constrained min-max game. Since the energy function is convex, it is monotonically increasing along the forward method, and it is increasing exponentially fast if is strongly convex. See Section for details.
Backward Discretization. A backward discretization of skew-gradient flow corresponds to the two players performing the simultaneous proximal mirror descent algorithm for constrained min-max game. Since the energy function is convex, it is monotonically decreasing along the backward method, and it decreasing exponentially fast if H is strongly convex. See Section B.2 for details.
4.1 Alternating Discretization Skew-Gradient Flow
The alternating discretization of the skew-gradient flow performs the updates one component at time, using the forward method for the first component (x) and the backward method for the second component (y), resulting in the update equation:
Tk+1 = I nAV, y H (IR+1,
yk+1 y/ + 1 V H (2 2k..
Since the energy function (xx = fz) + gv)) is separable, this yields an explicit update equation:
F441 22 7v ((v))
(11a)
Mk++ = y/: - n V
(11b)
For the min-max game application, this corresponds the alternating mirror descent update in the dual space B
In contrast to either the forward the backward discretization, this alternating discretization tracks the continuous-ting time dynamics more closely, and thus we can bound the deviation in the energy function better. To explain result, we introduce the notion of modified energy function.
4.1.1 Modified Energy Function
Given a step size 17 > 0, we define the modified energy function H,: Rm+n - R by:
Hz(;) H()) - (V/(s)
(12a)
7 2 AVg())
= =
(12b)
for = (x, Rm++, Note that when f and y are quadratic functions, this recovers the definition of the modified energy function in 2
Recall the Bregman divergence (=' = H(=') - H(z) (2H(2), 2) is not necessarily
symmetric. We define the Bregman commutator CH: IR 1 x Rmtn + IR as a measure of the
non-commutativity of Bregman divergence:
Ca(2',2) = ((Dn('', DH(2,2')) = =H(z') H(2) (V V
Observe that when H(z) = 1²2 M is a quadratic function (for any positive definite matrix M)), then D (x',2) (2 - TT - 2) = (2, 2') is symmetric, and thus Cz((2'22 = 0. Conversely, if the Bregman commutator vanishes: (z', = O, then H must be a quadratic function; see Lemma A. in Section A.2.I We can also bound the Bregman commutator under third-order smoothness; see Lemma A.2 in Section A.2..
We show that along the alternating method, the modified energy changes by precisely the Bregman commutator; we provide the proof in Section B.3.2]
Lemma 4.2. Let 2
(Ik, yx) evolve following the alternating method
Then for any k
(x((x+1) Hz((x) CH(24+1, zk).
(13)

---

As a corollary, if H is quadratic- in which case the Bregman commutator vanishes then the modified energy function is conserved along the alternating method. This recovers the main result of (2) for the unconstrained min-max game. We provide the proof of Corollary 4.3 in Section B.3.1
Corollary 4.3. Suppose H is a quadratic function. Along the alternating method for any k 2 0:
H=x(x) (20)
4.1.2 Bound under Third-Order Smoothness
Under smoothness assumptions on H, we can deduce the following bound on the modified energy function. Let || Il be an arbitrary norm in R with dual norm Il- Recall say H is L-Lipschitz if H=²)) - H (=)l < LI|=' - all for all 2, z' E Rm+n, equivalently, (z)ll+ I L. We say H is M-smooth of order 3 if H is three-times differentiable, and | (z) olop I M for all E Rm= where || Ilop is the operator norm. Then we have the following bound. We provide the proof of Theorem 4.4 in Section B.3.3 We note the following result holds without assuming convexity of H.
Theorem 4.4. Assume that H is L1- Li-Lipschitz and Ly Lm-shhoth of order 3. Let mmax be the maximum singular value of A. Along the alternating method (11, for any 1) 2 and at any iteration O:
(2,(2k) H2,(2o)
S
1 amax L3 L 1 k.
T2
As an example, the function (=) log >x e + log > m j=1 e em satisfies the assumptions of
Theorem 4. with respect to - |l norm: see Example A.3 in Section A In our min-max game
application, this function arises from using the entropy regularizer on the probability simplex.
4.1.3 Regret of Alternating Mirror Descent in terms of Modified Energy
We now consider the constrained min-max game application where H y) = f(x) + gy) with = 6² and g = 6. Given (p. q) E P x 2, let z (x, y) E Rm+-n be the dual variables, where V Vp(p) and y = Vbb(g). Then we can write the cumulative regret of alternating mirror descent in terms of the difference of the modified energy. We provide the proof of Theorem 4.5 in Section [8.3.4
Theorem 4.5. Let (Pk: qx) evolve following the alternating mirror descent algorithm ① with any step size 1) > O, and let 2 = (Ix: yis be the dual variables. We can write the cumulative regret of the two players with respect any (p. 9) E P Q as:
Rx (p. q) = 1 (Dn - Dn(=x,2) + H,(:K) - Hz)()))
Since H is convex, we can further bound DH (=K, z) 2 0, so from the above we get:
Rk(p. q) S ") (D# 2) + Hy (zx) H2,()))).
The first term in the bound above is constant that only depends on the initial point. we assume the domains are bounded, then this first term is also bounded. Thus, to control the cumulative regret, we need to bound the increase in the modified energy, which we can do via Theorem 4.4 under third-order smoothness. Completing this step yields the proof of Theorem 3.2
see Section
5 Discussion
In this paper we study the alternating mirror descent algorithm for constrained min-max games, and showed that it achieves a better regret bound than the classical simultaneous mirror descent. Our results extend the findings of 2 from the unconstrained to the constrained setting. We have utilized an interpretation of alternating mirror descent as an alternating discretization of the skew-gradien flow in the dual space, and linked the total regret of the players with the growth of the modified energy function. Our analysis highlights the connections between min-max games and Hamiltonian structures, which helps pave the way toward a closer interplay between classical numerical methods and modern algorithmic questions motivated by machine learning applications.
Our results leave many interesting open questions. First, our bound in Theorem 4.4 grows with the number of iterations, and does not yield constant regret as in the unconstrained case. In the special case of identity payoff matrix, in which the skew-gradient flow dynamics has Hamiltonian and symplectic structure, we conjecture that for sufficiently nice energy functions, the iterates of the

---

alternating method stay uniformly bounded, as in the unconstrained setting. In the Appendix, we provide some empirical evidence supporting this conjecture. Resolving this question requires making concrete classical bounds from numerical methods, which may be of independent interest.
Second, we have focused the simple case of two-player bilinear game, which already presents non-trivial behavior. It would be interesting to understand the more general setting of multi-player games with general payoff's, which the notion of ""alternating" play can take many possible forms. It would also be interesting to study the asynchronous setting in which the players make their moves in decentralized randomized fashions. This will help us understand and control the global behavior of multi-agen aggett systems and how they emerge from simple local or individual strategies.
Acknowledgements
We thank the reviewers for helpful comments and discussions on the paper. This research/project is supported in part by the National Research Foundation, Singapore and DSO National Laboratories under its AI Singapore Program (AISG Award No: AISG-RRP-2000-00 ALIAS grant, grant PIESGP-AI-2E AI-2020-01, AME
NRF 2018 Fellowship
NRF-NRFF2018 0--07, Programmatic Fund (Grant No.A20H6b0151 from the Agency for Science, Technology and Research (A (A*R)AR) and Provost's Chair Professorship grant RGEPPV2101.
References
[1] Gabriel Andrade, Rafael Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. In Conference on Learning Theory, pages 159-185. PMLR, 2021.
[2] James P Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory, pages 391-407. PMLR, 2020.
[3] James P. Bailey and Georgios Piliouras. Multiplicative weights update zero-sum games. In ACM Conference Economics and Computation, 2018
[4] James Bailey and Georgios Piliouras. Multi-agent learning in network zero-sum games is a Hamiltonian system. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, page 233-241, Richland, SC, 2019, International Foundation for Autonomous Agents and Multiagent Systems.
[5] Giancarlo Benettin and Antonio Giorgilli. On the hamiltonian interpolation of near-to-the identity symplectic mappings with application to symplectic integration algorithms. Journal of Statistical Physies, 74(5):1117-111 1994.
[6] Nikolo Cesa-Bianchi and Gabor Lugoisi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[7] Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807-834. PMLR, 2019.
[8] Thiparat Chotibut, Fryderyk Falniowski, Michal Misiurewicz, and Georgios Piliouras. The route to chaos in routing games: When is price of anarchy too optimistic? Advances Neural Information Processing Systems, 33:766-777, 2020.
[9] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 2021.
[10] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
[11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.
10

---

[12] E. Hairer, C. Lubich, and G. Wanner. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer. Berlin Heidelberg New York, second edition, 2006.
[13] J. Hofbauer. Evolutionary dynamics for bimatrix games: A hamiltonian system? J. of Math. Biology, 34:675-683 1996.
[14] Michael Jordan. Dynamical, symplectic and stochastic perspectives on gradient-based op- timization. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 523-549. World Scientific, 2018.
[15] Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. ICLR, 2021.
[16] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[17] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the (xtra(-gradient)) mile. In ICLR, 2019.
[18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages
SIAM, 2018.
[19] 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.
[20] Michael Muehlebach and Michael I Jordan. Optimization with momentum: Dynamical, control- theoretic, and symplectic perspectives. Journal of Machine Learning Research, 22(73):1-50, 2021.
[21] A.S. Nemirovskii and D.B. Yudin. Problem Complexity and Method Efficiency Optimization.
A Wiley-Interscience publication. Wiley, 1983.
[22] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[23] Shayegan Omidshafiei, Christos Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau. Wojeiech M Czarnecki, Marc Lanctot, Julien Perolat, and Remi Munos. a-rank: Multi-agent evaluation by evolution. Scientific reports, 9(1):1-29, 2019.
[24] Christos Papadimitriou and Georgios Piliouras. Game dynamics as the meaning of a game.
ACM SIGecom Exchanges, 16(2):53-63, 2019.
(25) Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via Clairvoyant Multiplicative Weights Update. arXiv preprint arXiv:2111.14737 2021.
[26] R. Tyrrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.
[27] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-666 2020.
[28] Molei Tao and Tomoki Ohsawa. Variational optimization on lie groups, with examples of leading (generalized) eigenvalue problems. In International Conference on Artificial Intelligence and Statistics, pages 4269-4280. PMLR, 2020.
[29] John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100:295-300. 1928.
11

---

[30] Andre Wibisono, Ashia C Wilson, and Michael Jordan. A variational perspective on accelerated methods optimization. Proceedings of the National Academy of Sciences, 17734)) E7358, 2016.
12


Reviews:
[{"review_id": "iiQGFIGaaST", "reviewer": "Reviewer_x9Yh", "summary": "The paper considers alternating mirror descent of bilinear 2-player zero-sum games in the constrained setting where each player can play within a compact and convex set. It is shown through a suitable reduction to the skew gradient flow dynamics that the average iterates converges to a Nash equilibrium at a speed K^{-2/3} where K is the no. of iterations.\n\n", "questions": "- In general, you need to explain what is the role of your assumptions formulated in Thm 3.2 (both boundedness and smoothness of third derivative), in order to prove your results, e.g., as compared to simultaneous mirror descent.\nNo comments whatsoever are provided in the main body of the paper, which is a bit awkward.\n- L. 330. Where are you using within Thm 4.4 the assumptions of Thm 3.2 ?\n\n- Regret definition: I'm not sure why regret is defined that way (with two consecutive iterates), I'm not sure I can buy the argument that one player sees the other player's iterate twice. Does it make any difference if we replace (p_k+p_{k+1})/2 in (6) by p_k only [and same for (7)] ?\n\n\nMinor points:\n- L. 45 the the\n- L. 235, pls define ||.||_op  (it is only defined in L. 313)\n- L. 250: pls check/rephrase this sentence\n- L. 303 and 316: Eq (11) does not seem to exist (or, at least, I cannot find it) ", "limitations": "Limitations are described in the concluding section and in the checklist. I would have liked to see a more thorough discussion of the limitations implied by the assumptions in Thm 3.2.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the paper is very well written\n- the analysis is carried out with care and clarity\n- the extension to the constrained case is interesting, yet, see below\n\nWeaknesses:\n- The assumptions on boundedness of Bregman divergence(s) are a bit clashing with your assumptions of phi and psi being Legendre. For instance, your result does not seem to apply to the case where the domain P and Q are the probability simplex and the divergence is KL, as KL is unbounded.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V7BQW5on8Xh", "reviewer": "Reviewer_SuUA", "summary": "The authors study alternating mirror descent updates for constrained bilinear zero sum games.  Using alternating updates rather than simultaneous updates, the average regret of the method is $O(K^{-2/3})$ for $K$ iterations in comparison to the known  $O(K^{-1/2})$ regret for simultaneous updates. Unlike simultaneous updates, the iterates do not diverge, but rather maintain a constant energy, like the continuous time dynamics that motivate the approach.", "questions": "It seems this work does not handle mirror descent in it's more general form because there is no projection and the constraints need to be handled via the domain of the regularizer through the Legendre condition.  Does this work for natural constraints like polytopes?\n\nRelated nitpick(Line 149): Mirror Descent and FTRL are not the same in online learning; these are actually different when constraints are involved that require projection.", "limitations": "There are no societal limitations of the work, but limitations of some of the assumptions could probably be tackled more directly.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Bilinear zero sum games are a fundamental primitive in game theory and machine learning so improved understanding is inherently valuable.\n- The $O(K^{-2/3}) average regret bound appears to be novel and state of the art for constrained bilinear zero sum games.\n- The connections to continuous time dynamics are very useful for gaining intuition on why alternation is useful and the energy analysis is very elegant.\n- While the regret notion in this paper is a bit nonstandard, it is well justified in it's connection to the duality gap.\n\nWeaknesses:\n-The third order smoothness condition seems potentially reasonable, but does not seem completely standard and maybe should include more discussion. The analysis relies heavily on this.  The example provided for entropy regularization is appreciated here though, but perhaps more examples should be included.\n\n- The domain of the regularizer seems to need to be the constraint set itself, which is not in general necessary for mirror descent.  This avoids having to deal with Bregman projection but weakens the result as the set of constraints that can be handled is much less general.\n\n- I'm not sold on the setting.  While it's interesting having an understanding of this natural update, alternating updates requires coordination between both players, so it's not completely clear why the backward discretization (proximal mirror descent or clairvoyant multiplicative weights) is actually a problem given this gets $O(K^{-1})$ regret.\n\n- The paper is a mirror descent based generalization of [2].  It seems like the main challenge involved in generalizing this is a nonzero Bregman commuter.  This seems like a fairly minor extension with the third order smoothness assumption.\n\n[2] Bailey, James P., Gauthier Gidel, and Georgios Piliouras. \"Finite regret and cycles with fixed step-size via alternating gradient descent-ascent.\" Conference on Learning Theory. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GQMQpxqfoN", "reviewer": "Reviewer_hLz6", "summary": "This paper studies the regret of alternating mirror descent in constrained min-max bilinear two player games. The authors prove that when both players employ this algorithm, they enjoy a regret of $$O(K^{-2/3})$$. This work builds on previous work [1], in which the  authors prove a constant regret for the class of two player zero sum games in the unconstrained setting.", "questions": "I would like to ask the authors some clarifying questions. \nIn lines 150-153 the authors say that the function $\\phi$ needs to be continuously differential error, $|| \\phi(p)|||\\to\\infty$ as p approaches the boundary of $P$ and $\\nabla \\phi$ is a bijection from $P$ to the range $\\nabla\\phi(P)\\subseteq \\mathbb{R}^m$.  If I am not mistaken, this means that we cannot $\\phi$ to be for example $1/2||p||^2$ which would lead to the projected gradient descent algorithm. Which are the choices that are actually permitted?\n\nFurthermore, in section for you consider that the energy function separable. Even though you claim that this is not necessary and the function H could be anything, it’s not clear to me how the updates would be performed in this case. Building on this, in theorem 4.4 you give an example of a function which is not separable and no example of a function that it is. Which are the energy functions that are actually satisfy the assumptions present in theorem 4.4 and are decomposable? ", "limitations": "This paper has no negative societal impact to my knowledge.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is in general well written and has a nice flow. The techniques used are quite interesting and extend the ideas presented in [1] to the constrained setting. \nHowever, considering the existence of the results for general-sum multiplayer games  and the result presented in [2], in which the authors prove that when players run Optimistic Dual Average with an adaptive step size (which is easy to deduce that also holds for a step size of the order $1/\\sqrt{T}$) then they enjoy constant regret in the class of all convex-concave zero sum games, which includes the bilinear case. \n\n[1]: Bailey, James P., Gauthier Gidel, and Georgios Piliouras. \"Finite regret and cycles with fixed step-size via alternating gradient descent-ascent.\" Conference on Learning Theory. PMLR, 2020.\n\n[2]: Hsieh, Yu-Guan, Kimon Antonakopoulos, and Panayotis Mertikopoulos. \"Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium.\" Conference on Learning Theory. PMLR, 2021.\n\nMinor comments:\nLine 45: double “the”", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept