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

Thank you for the positive review and the constructive comments on the presentation. We will incorporate your suggestions in the revised version of the paper. Specifically, we will update the flow in section 3 and make Assumption 2, the discussion, and the proof sketch more reader-friendly. Below, we answer your questions.

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

A: Thank you for raising this point! We will add a remark for this claim in the revised paper. We also conjecture that slow last-iterate convergence rates for OFTRL algorithms persist even for time-varying learning rates. In particular, we conjecture that our hard example works for decreasing step sizes. In the rebuttal PDF, we provide numerical experiment results for AadGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. However, a time-dependent learning rate that occasionally increases the step size or other periodic learning rate schedules might be able to address the issue of non-forgetfulness. We will discuss time-varying step sizes in the next version of the paper. We leave the question of how time-varying step sizes affect the last-iterate convergence rates of OFTRL algorithms as an interesting and important open question.

Q2: The wording of Theorem 2 could be improved.

A: Thank you for the comment! We actually accidentally omitted the term “there is no function $f$ such that” before “... the corresponding learning dynamics” in the statement. We will improve the wording in the revised version.

Thank you for acknowledging that we made a significant contribution to an important question and for the constructive comments on the presentation. We will incorporate your suggestions and improve the presentation in the next version of the paper. Below, we address your questions.

Q1: Is it possible to extract a "forgetfulness" property for an arbitrary learning algorithm that must imply the algorithm has slow last iterate convergence?

A: Our paper aims to understand the slow last-iterate convergence of OMWU and, more generally, OFTRL-type and certain Optimistic OMD-type algorithms. Our proof and hard game instances build on the intuition that these algorithms lack forgetfulness: they do not forget the past quickly and play actions that performed well in the past, even if their recent performance is bad (see also Lines 70-99 in the Introduction). We are the first to connect the intuitive idea of forgetfulness to last-iterate convergence. Even without a formal definition of “forgetfulness”, we believe that this intuitive connection with last-iterate convergence is a novel contribution.

Putting the finger exactly on a formal, precise definition of forgetfulness appears to be challenging. We did try, but found it rather difficult. For example, our first attempt was to define it as any algorithm that is "mean-based", that is, the decision at each time depends on the past gradients solely through their mean. Such algorithms give equal weights to all past observations and are thus intuitively not forgetful. However, we quickly realized that while this covers all FTRL algorithms, it does not even cover their optimistic version (OFTRL, which is our main focus). We hope this convinces the reviewer that finding a formal and general definition for the lack of forgetfulness could be non-trivial. At any rate, the “lack of forgetfulness” is just an intuitive explanation for the phenomenon. We view our most important (and surprising) result to be the fact that all known OFTRL variants have these convergence issues. It would be interesting to come up with a formal definition that captures a broader class of algorithms, though that seems difficult and we leave it as future work.

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

A: We clarify that Theorem 2 is indeed a corollary of Theorem 1. Thank you for pointing it out; we will make it clear in the next version of the paper. Theorem 1 is a more technical theorem that states the OFTRL learning dynamics have a constant duality gap even after $1/\delta$ steps. Theorem 2 is a more high-level theorem that states OFTRL learning dynamics cannot have a last-iterate convergence rate that solely depends on the dimension and the time. Thus, game-parameter dependence is unavoidable for OFTRL algorithms, which provides a clearer comparison between OFTRL and OGDA since the latter has an $O(\frac{\textnormal{poly}(d_1, d_2)}{\sqrt{T}})$ last-iterate convergence rate. In summary, while Theorem 2 is a direct corollary of Theorem 1, we state Theorem 2 separately to highlight our main contribution and the difference between OFTRL and OGDA.

C1: As a possible weakness, the stated negative results apply to a particular class of algorithms (OFTRL) and potentially might be sidestepped.

A: Although our results only hold for OFTRL, we believe they are still significant given that OFTRL is arguably one of the most studied classes of online learning algorithms and covers many standard algorithms, including the classical OMWU. We also want to emphasize that the existing positive results are even more restrictive: only OGDA and OMWU have proven concrete last-iterate convergence rates. Inspired by OMWU’s weaker convergence guarantees compared to OGDA, we demonstrate that this disadvantage is unavoidable and, in fact, applies to a broader class of OFTRL algorithms.

I thank the authors for the detailed responses, reading the other reviews and the rebuttal I understand that the main point of the work is analyzing the "OFTRL" class of algorithms. I agree with the other reviewers that the work merits a better score and have raised mine.

Thank you for your encouraging comments!

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

A: We conjecture that slow last-iterate convergence of OMWU persists for time-dependent step sizes (learning rates). In particular, we conjecture that our hard example works for decreasing step sizes. In the rebuttal PDF, we provide numerical experiment results for AadGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. However, a time-dependent learning rate that occasionally increases the step size or other periodic learning rate schedules might be able to address the issue of non-forgetfulness. We will discuss time-varying step sizes in the revised version of the paper. We leave the question of how time-varying step sizes affect the last-iterate convergence rates of OFTRL algorithms as an interesting and important open question.

Thank you for the positive review! Below, we address your questions.

Q1: 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 $\ell_2$ norm.

A: We clarify that we only verify Assumptions 1 and 2 for specific regularizers, but not all 1-strongly convex regularizers wrt to $\ell_2$ norm. In this current manuscript, we verify the two assumptions for the negative entropy, Euclidean and log regularizer. We can also show that the two assumptions hold for the family of (negative) Tsallis entropy regularizers: parameterized by $0 < \beta < 1$, $R(x) = \frac{1 - \sum x[i]^{\beta}}{1-\beta}$. Together with entropy, Euclidean, and the log regularizer, we believe our results cover every commonly-used regularizer in the online learning literature. We will add the proof for Tsallis entropy regularizers in the revised version of the paper.

Q2: Does the hard example still hold with vanishing step sizes?

A: This is a great question! Our current proof only works for fixed step sizes. In the rebuttal PDF, we provide numerical results for AdaGrad stepsize, an adaptively decreasing step size schedule. The results show that the last iterate of the decreasing step-size version exhibits qualitatively similar behavior to its constant step-size counterparts. We conjecture that our results could be extended to the case of decreasing step sizes. We will add a discussion and leave whether OFTRL with vanishing/variable step size could have a fast last-iterate convergence rate as an important future direction.

Q3: Is the high-dimensional example applicable only for the specific regularizers mentioned?

A: The reduction in the high-dimensional setting requires structures of the regularizers and might not hold for all 1-strongly convex regularizers. As shown in the current paper, the reduction works for negative entropy, Euclidean, and log regularizers. We can also prove that the reduction works for the family of Tsallis entropy regularizers (see Answer to point 1 above). We will add this result in the revised version of the paper.