Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Authors: Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Figure 1: Comparison of the dynamics produced by three variants of OFTRL with different regularizers (negative entropy, logarithmic regularizer, and squared Euclidean norm) and OGDA in the same game Aδ defined in (2) for δ := 10 2. The bottom row shows the duality gap achieved by the last iterates. The OFTRL variants exhibit poor performance due to their lack of forgetfulness, while OGDA converges quickly to the Nash equilibrium. Figure 2: Performance of OMWU on the game Aδ defined in eq. (2) for three choices of δ. In all plots, the learning rate was set to η = 0.1. As predicted by our analysis, the length of the flat region between iteration T1 (red star) and T2 (blue dot) scales inversely proportionally with δ. Our simulations were done within a few hours on an average consumer laptop. |
| Researcher Affiliation | Academia | Yang Cai Yale yang.cai@yale.edu Gabriele Farina MIT gfarina@mit.edu Julien Grand-Clément HEC Paris grand-clement@hec.fr Christian Kroer Columbia ck2945@columbia.edu Chung-Wei Lee USC leechung@usc.edu Haipeng Luo USC haipengl@usc.edu Weiqiang Zheng Yale weiqiang.zheng@yale.edu |
| Pseudocode | No | The paper provides mathematical definitions and update rules for algorithms (OOMD, OFTRL) but does not present them in a structured pseudocode or algorithm block format. |
| Open Source Code | Yes | Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: See Python code in the supplementary materials. |
| Open Datasets | No | The paper defines a specific 2x2 matrix game Aδ for its analysis and simulations ('The game s loss matrix Aδ is parameterized by δ (0, 1 2) and is defined as follows: Aδ = 2 + δ 1 2 0 1'). This is a synthetic instance created by the authors, not a publicly available dataset with external access information or citation. |
| Dataset Splits | No | The paper conducts simulations on a specific game instance and analyzes dynamics. It does not mention traditional training, validation, or test dataset splits. |
| Hardware Specification | No | Our simulations were done within a few hours on an average consumer laptop. The term 'average consumer laptop' is not a specific hardware detail (e.g., CPU/GPU model, memory, or clock speed). |
| Software Dependencies | No | The paper does not provide specific version numbers for any ancillary software dependencies or libraries used in the experiments. It mentions 'Python code in the supplementary materials' but without version details. |
| Experiment Setup | Yes | In all plots, the learning rate was set to η = 0.1. In this section we present our numerical results when OFTRL and OOMD are instantiated with adaptive stepsize [Duchi et al., 2011]: ηt = 1/ q ϵ + Pt 1 k=1 ℓk 2 k with some constant ϵ > 0. We present our numerical experiments in Figure 4, where we choose ϵ = 0.1. |