Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms

Summary

The present work studies the last iterate convergence of learning algorithms in zero sum games. Existing results have shown that although OMWU and OGDA both enjoy the $O(1/T)$ ergodic convergence rate, their best existing last iterate convergence rates exhibit a nontrivial gap. This paper constructs a particular hard example showing that such a gap is due to a fundamental limitation of the OMWU algorithm, rather than the sub-optimality of existing analysis. From this hard example, the key insight is that fast last iterate convergence requires learning algorithms to forget the past.

Strengths

This paper is very cool. Last iterate convergence is an important problem for learning in games, and this paper naturally motivates it by the existing theoretical and empirical gap between OMWU and ODGA. To tackle this problem, the paper then presents a particularly nontrivial analysis on the learning dynamics of Optimistic FTRL in games, despite the appeared simplicity of the constructed example. The takeaway message on the importance of forgetting is elegant, which might inspire future works on algorithm design. I also appreciate the graphical illustration on the learning dynamics, which makes the very technical proof intuitively easier to understand. Related works seem to be thoroughly discussed. Frankly speaking, the analysis in this paper is quite involved, so I only have a high level understanding of the proof while struggling on the details. However, as far as I can see, the high level intuition makes sense, and the numerical experiments are quite helpful.

Weaknesses

This paper is already strong in my opinion, so I don't have any major complaint. One possible aspect to improve is the presentation. There are certain parts in the analysis that are particularly involved, so it might be better to write less quantitatively in the main paper, and leave those parts to the appendix. For example, Assumption 2 and the discussion right after it. I would also appreciate a further simplified proof sketch, specifically, more words and less math.

Questions

Some minor comments: - In line 51-51 it is quoted from (van Erven, 2021) that FTRL is conventionally believed to be better than OMD. From the perspective of online convex optimization, I feel this is actually a bit more nuanced, as the examples I'm aware of (where FTRL beats OMD) concern time varying learning rates, which is different from the constant learning rates considered in this paper. - The wording of Theorem 2 could be improved.

Rating

8

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

Limitations are adequately addressed.

Summary

The paper investigates the last-iterate convergence properties of several classes of algorithms employed in zero-sum matrix games. As a core contribution, it is shown that a large class of iteration rules can not exhibit instance-independent convergence in zero-sum games of dimension 2. The result is further generalized to larger dimensions.

Strengths

The paper tackles an important problem and makes a potentially significant contribution to our understanding of learning dynamics in zero-sum matrix games. I think the results are rigorously developed, and while I did not verify the details of all the proofs, they seem to be correct.

Weaknesses

The concept of a "forgetful algorithm" could be made more explicit, perhaps as a definition. It is not clear to me what property makes an algorithm forgetful by construction. An explicit definition (if it is possible at all) could greatly clarify the work. As a possible weakness, the stated negative results apply to a particular class of algorithms (OFTRL) and potentially might be sidestepped. The formulation of the main theorems could be clarified or perhaps simplified. For instance, theorem 2 has a rather complicated statement, which to my understanding just means either the duality gap can not go to zero (in which case it can be stated as such directly), or the duality gap can not go to zero uniformly (in which case item 1 should have a statement "over all possible loss matrices"). I think one weakness of the paper is the presentation/organization. I found it difficult to follow the main ideas and the main contribution of the paper. For instance, the generalization to higher dimensions, while interesting, seems to be a minor contribution from a theoretical perspective, while significant space is dedicated to its proof ideas.

Questions

Is it possible to extract a "forgetfulness" property for an arbitrary learning algorithm that must imply the algorithm has slow last iterate convergence? Are there significant differences between Theorems 1 and 2 to warrant stating them separately? Upon first read, it was difficult to understand what the main difference was, and Theorem 2 seems to be a corollary of Theorem 1 looking at the proof in the appendix.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

See weaknesses.

Summary

This paper shows a limitation of optimistic multiplicative weights (OMWU) with a fixed learning rate: the last-iterate convergence rate can be arbitrarily large, depending on a game-dependent constant in normal form games. This demonstrates that the current upper bounds on convergence are not loose and that there is a real barrier to this dynamic. Broader Context: Optimistic online learning algorithms play an important role in solving games. The average iterates of OMWU have been shown to converge in zero-sum games at a rate of 1/T, which is better than the non-optimistic counterpart. Another important algorithm in this context is the online gradient descent ascent (OGDA), which has been shown to have last-iterate convergence of O(1/sqrt{T}), where the constant hides polynomial dependence on the problem parameters. Last-iterate convergence is a desirable property in the context of games. Since OMWU is a central tool for solving games, understanding its limitations is a fundamental question. This paper reveals an inherent limitation of OMWU (and more generally, for some algorithms within the optimistic FTRL framework), showing that OGDA might sometimes enjoy better last-iterate convergence. The main property responsible for this limitation is the "lack of forgetfulness."

Strengths

The paper answers a fundamental question in the "learning in games" community (solving games using online learning dynamics). I like also the presentation of the paper. For example, the authors made an effort to explain the intuition behind the construction of the hard game.

Weaknesses

My only criticism is the following: It might be the case that OMWU can have good last-iterate convergence when using changing learning rates. These are sometimes used to avoid such an issue of forgetfulness. (But I believe that analyzing fixed learning rate is a significant contribution on its own)

Questions

Do you think using time-dependent learning rates might improve the last-iterate convergence of OMWU? If so, maybe it's worth discussing it or writing it as a limitation.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

See the above.

Summary

The authors, through some hard instances of games study the fundamental differences in convergence of broadly two classes of algorithms which are OOMD and OFTRL. Particular algorithms of interest include the OGDA and the OMWU algorithm respectively. They show that OFTRL (in particular OMWU) necessarily exhibits slow last-iterate convergence and this leads to it having an undesirable dependence on the underlying game.

Strengths

This paper seems to capture an important property that differentiates the likes of algorithms such as OGDA and OMWU, two extremely popular optimistic algorithms known to achieve last-iterate convergence in zero-sum games. Now this paper mounts further evidence of ``slowness" of OWMU and that it is unavoidable to have game dependent constants appearing in the guarantees! I think this is an important finding for this area.

Weaknesses

This is a focused study on showing certain properties of a class of algorithms such as OFTRL and OOMD. In general it is not clear if some of the results apply to every regularizer satisfying the assumptions or to the particular ones of interest such as Euclidean, Entropic etc. Beyond a few clarifications which I have asked in the next section, I do not think there are major weaknesses.

Questions

1) Please clarify whether Assumptions 1 and 2 are satisfied by the specific regularizers such as entropic, euclidean and log or general regularizers that are 1-strongly convex wrt to $l_2$ norm. 2) Does the hard example still hold with vanishing step sizes? 3) Is the high-dimensional example applicable only for the specific regularizers mentioned.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

yes.

Response to the Rebuttal

I thank the authors for the clarifications and the experiments with vanishing step sizes. I will maintain my already positive score.