Summary
This work investigates the problem of last-iterate convergence in time-varying zero-sum games. Specifically, the authors study the last-iterate convergence of three kinds of algorithms (OGDA, EG, and negative momentum method) considering two kinds of time-varying games with specific structures, i.e., periodic games and convergent perturbed games. The authors obtained a convergence rate of EG in periodic games while providing a counterexample showing that OGDA and negative momentum method will diverge in this kind of game. In convergent perturbed games, the authors showed that all three kinds of algorithm will converge with a rate dependent on the perturbation $B_t$. Finally, experiments validate the statements proposed by the authors.
Strengths
In general, I think there is no last-iterate convergence rate in time-varying games due to the changing nature of the games. However, with specific problem structures, I believe that last-iterate convergence results can be established, and this work provides a piece of clear evidence. Overall, although the solutions are relatively simple by modeling the learning algorithms as dynamical systems and leveraging some existing results in the control theory, I am satisfied with the motivation and the final results of this work.
Weaknesses
There are no significant weaknesses that affect my rating of the whole paper. In the following, I only list some minor issues.
1. The notion of $T$ in periodic games. The notion of $T$ is commonly used to refer to the total number of rounds in online learning. In this work, the authors use $T$ to represent the number of rounds inside each period, which may lead to unnecessary understandings. I suggest the authors could choose a different notion to denote the period length.
2. The notion of $\text{ker}(\cdot)$. This notion, which appears in Line 98 for the first time, seems not to be defined or given a clear description before.
3. In Line 120, the authors mention that 'Recently, there are also works analyzing the regret behaviors of OGDA under a time-varying setting [1]'. The reference to [1] is not accurate enough. The work of [33], which is published at ICML2022, firstly gives a comprehensive study of the optimistic methods in time-varying zero-sum games by optimizing multiple performance measures simultaneously. I suggest the authors could refer to [33] in the aforementioned statement to make the credits more accurate.
4. The negative momentum method requires the $x$-player to evolve to the next round first to give its gradient $A_{t+1} x_{t+1}$ to the $y$-player. In some cases where the learning procedure is strictly in an online style, this algorithm is NOT applicable since both players must act first to make the game evolve. I suggest the authors could give a discussion on this point in the revised version.
Typos:
1. Line 89: 'Section 4' not 'section 4'.
2. Line 188: 'Section 3.3' not 'Section3.3'.
3. The reference to theorems are not unified, e.g., in Line 237, 'theorem 3.2', and in Line 255, 'Theorem (3.1)'.
Questions
I only have a major question on Theorem 3.1. What is the range of $t$? If $t$ is only chosen in $[1,T]$, choosing $t=T$ yields a convergence rate of $O(\lambda_* \text{poly}(T))$, which can be seen as a constant in terms of $T$. As mentioned in the 'Weaknesses' part, a bound linear in $T$ is pretty bad in the standard online learning convention. Theorem 3.1 exhibits an exponential rate only when $t$ can be significantly larger than the period length. Can the authors give some further explanations on this point?
In the end, I am very curious about whether the method in this paper, which models the learning algorithms as dynamical systems, can be applied to the constrained case, where the projection operations may bring some unique challenges to the modeling issue. Can the authors give some further explanations on this point?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Please mainly refer to the 'Weaknesses' part.