Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems
Authors: Sucheol Lee, Donghwan Kim
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper proposes a two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast O(1/k2) rate on the squared gradient norm for smooth structured nonconvex-nonconcave problems; the corresponding saddle-gradient operator satisfies the negative comonotonicity condition. This paper further develops its backtracking line-search version, named FEG-A, for the case where the problem parameters are not available. The stochastic analysis of FEG is also provided. and Theorem 4.1. For the L-Lipschitz continuous and ρ-comonotone operator F with ρ > 1/2L and for any z Z (F ), the sequence {zk}k 0 generated by FEG satisfies, for all k 1, F zk 2 <= 4 z0 z 2 / (1/L + 2ρ)^2 k^2. |
| Researcher Affiliation | Academia | Sucheol Lee Department of Mathematical Sciences KAIST Daejeon, Republic of Korea Donghwan Kim Department of Mathematical Sciences KAIST Daejeon, Republic of Korea |
| Pseudocode | Yes | Algorithm 1 Fast extragradient (FEG) method, Algorithm 2 Fast extragradient method with adaptive step size (FEG-A), Algorithm 3 Stochastic fast extragradient (S-FEG) method |
| Open Source Code | No | The paper does not provide any explicit statements about the release of source code or links to a code repository for the described methodology. |
| Open Datasets | No | The paper uses a 'Toy example' with a simple quadratic function f(x, y) = ρL^2/2 y^2 for illustration, which is a mathematical construct and not a publicly available dataset with concrete access information. |
| Dataset Splits | No | The paper primarily presents theoretical analysis and a mathematical toy example, thus it does not provide specific training/validation/test dataset split information. |
| Hardware Specification | No | The paper does not provide any specific hardware details for running experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers. |
| Experiment Setup | Yes | For the case ρ = 1/3L and L = 1, Figure 2 illustrates that the FEG converges with an accelerated rate... |