Alternating Mirror Descent for Constrained Min-Max Games
Authors: Andre Wibisono, Molei Tao, Georgios Piliouras
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as an alternating discretization of a skew-gradient flow in the dual space, and use tools from convex optimization and modified energy function to establish an O(K 2/3) bound on its average regret after K iterations. This quantitatively verifies the algorithm s better behavior than the simultaneous version of mirror descent algorithm, which is known to diverge and yields an O(K 1/2) average regret bound. |
| Researcher Affiliation | Academia | Andre Wibisono Department of Computer Science Yale University andre.wibisono@yale.edu Molei Tao Department of Mathematics Georgia Institute of Technology mtao@gatech.edu Georgios Piliouras Engineering Systems and Design Singapore University of Technology and Design georgios@sutd.edu.sg |
| Pseudocode | No | The paper presents mathematical equations for the algorithm steps (e.g., equations (1), (2), (3), (11)) but does not include a clearly labeled 'Pseudocode' or 'Algorithm' block. |
| Open Source Code | No | The paper does not provide any explicit statement or link regarding the release of source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on algorithm analysis and does not involve training on datasets. Therefore, it provides no information about publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper focused on algorithm analysis and does not involve dataset splits for validation or training. Therefore, it provides no information about dataset splits. |
| Hardware Specification | No | This is a theoretical paper focused on algorithm analysis and does not report on empirical experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper focused on algorithm analysis and does not report on empirical experiments. Therefore, no software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper focuses on theoretical analysis of an algorithm and its properties (like step size and smoothness assumptions) rather than practical implementation details. It does not provide specific experimental setup details, hyperparameters, or training configurations for empirical runs. |