Research map / Learning theory and algorithms / Sample complexity
Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that optimal acceleration for minimax and fixed-point problems is not unique by deriving dual anchor-type algorithms (Dual-OHM, Dual-FEG) that match the worst-case rates of the anchor-based OHM and FEG via H-duality.
Problem
Anchor-based accelerated methods were believed to be the unique optimal acceleration mechanism for nonexpansive fixed-point problems and smooth convex-concave minimax optimization, with matching lower bounds.
Approach
Using H-duality, the authors construct dual algorithms (Dual-OHM, Dual-FEG, Dual-Anchor ODE) that use a different acceleration mechanism (momentum on operator differences with a finite-horizon step-size schedule depending on N or T) yet attain exactly the same worst-case rates as the primal anchor-based methods; they also show a continuous family of exact optimal fixed-point algorithms interpolati
Key results
- Dual-OHM attains ||y_{N-1} - T y_{N-1}||^2 <= 4||y_0 - y_*||^2 / N^2, exactly matching the OHM rate and the matching lower bound for fixed-point problems.
- Dual-FEG attains ||grad L(x_N)||^2 <= 4||x_0 - x_*||^2 / (alpha^2 N^2) for alpha <= 1/L, matching the FEG rate for k=N and optimal up to a constant factor.
- Numerically, Dual-FEG reaches terminal accuracy much earlier than FEG on strongly-convex-strongly-concave bilinear problems, though worst-case guarantees are identical.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace anchoring with the Dual-OHM update | Optimal Halpern Method · Nonexpansive fixed-point problems | fixed-point residual norm squared: \frac{4\|y_0 - y_\star\|^2}{N^2} -> \frac{4\|y_0 - y_\star\|^2}{N^2} | No clear effect |
| Replace anchoring with the Dual-FEG update | Fast Extragradient · Smooth convex-concave minimax problems | gradient norm squared: \frac{4\|x_0 - x_\star\|^2}{\alpha^2 N^2} -> \frac{4\|x_0 - x_\star\|^2}{\alpha^2 N^2} | No clear effect |
| Vary the H-matrix within the continuous family of optimal algorithms (ablation) | Fixed-point algorithms · Nonexpansive fixed-point problems | fixed-point residual norm squared: \frac{4 \norm{y_0-y_\star}^2}{N^2} | No clear effect |
| Use dual algorithms rather than primal algorithms in early iterations | Dual-OHM and Dual-FEG · Problems involving strongly monotone operators | convergence speed | Helped |
| Use Dual-FEG instead of FEG | Smooth minimax optimization · Strongly-convex-strongly-concave bilinear problems | gradient norm convergence speed | Helped |
| Use Dual-OHM instead of OHM | Fixed-point algorithms · Linear operators | terminal iterate | No clear effect |
Surprising findings
- The optimal fixed-point algorithm is not unique: there is an (N-2)-dimensional continuous family of exact optimal algorithms.
- Dual algorithms converge faster than primal ones in early iterations on strongly monotone problems despite identical worst-case guarantees.
Limitations
- Dual algorithms require the total iteration count N (or terminal time T) to be fixed in advance, unlike primal methods.
- The minimax result is optimal only up to a constant factor, and the full characterization of exact optimal algorithms is left open.
Experimental setup
Metrics: squared norm of fixed-point residual squared norm of saddle operator
Baselines: Optimal Halpern Method (OHM) Fast Extragradient (FEG) Extragradient (EG) Anchor ODE Accelerated Proximal Point Method (APPM)
Builds on: Halpern iteration Extra Anchored Gradient Fast Extragradient H-duality for convex minimization performance estimation problem
Closest papers by meaning
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · similarity 0.89)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.87)
- Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization (NeurIPS 2026 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.87)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.