Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.


strengths_and_weaknesses: Strengths:
- the paper is very well written
- the analysis is carried out with care and clarity
- the extension to the constrained case is interesting, yet, see below

Weaknesses:
- 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.

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.
No comments whatsoever are provided in the main body of the paper, which is a bit awkward.
- L. 330. Where are you using within Thm 4.4 the assumptions of Thm 3.2 ?

- 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)] ?


Minor points:
- L. 45 the the
- L. 235, pls define ||.||_op  (it is only defined in L. 313)
- L. 250: pls check/rephrase this sentence
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 
However, 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. 

[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.

[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.

Minor comments:
Line 45: double “the”
questions: I would like to ask the authors some clarifying questions. 
In 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?

Furthermore, 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
- Bilinear zero sum games are a fundamental primitive in game theory and machine learning so improved understanding is inherently valuable.
- The $O(K^{-2/3}) average regret bound appears to be novel and state of the art for constrained bilinear zero sum games.
- The connections to continuous time dynamics are very useful for gaining intuition on why alternation is useful and the energy analysis is very elegant.
- While the regret notion in this paper is a bit nonstandard, it is well justified in it's connection to the duality gap.

Weaknesses:
-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.

- 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.

- 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.

- 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.

[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.
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?

Related 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.
review_title: null

Meta-review: metareview: The paper studies the regret of alternating mirror descent in constrained bilinear 2-player zero-sum games 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.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.
The reviewers agreed during the post-discussion that this is a non-trivial paper that extends known results to the constrained setting in some meaningful way (yet, paying the price of some extra assumptions and limitations on the algorithms played by the two players).
To the authors: Please follow the reviewers' suggestions to improve presentation (like, more context and more discussion about the limitations of these results).
confidence: Less certain
Decision: Accept