Research map / Optimization / Nonconvex and smooth optimization
Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity
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.
Extends cohypomonotone and weak-MVI first-order methods to the range rho < 1/L using conic nonexpansiveness, with inexact Halpern/KM iterations with FBF subsolvers, and an MLMC-based stochastic KM variant.
Problem
First-order methods for constrained nonconvex-nonconcave min-max (nonmonotone inclusion) problems under cohypomonotonicity or weak MVI, where prior analyses only handled rho < 1/(2L).
Approach
Apply Halpern/KM iteration to the firmly nonexpansive (or conically quasi-nonexpansive) operator (1-alpha)Id + alpha J_{eta(F+G)} with alpha = 1 - rho/eta, which only needs rho < eta < 1/L; solve resolvent inexactly via FBF with a tighter inexactness schedule (k^{-3/2}) and, in the stochastic weak-MVI case, use multilevel Monte Carlo to control bias.
Key results
- Deterministic cohypomonotone case: Halpern-based method attains rho < 1/L with oracle complexity Õ(ε^{-1}), matching the optimal rate up to a log factor (previous best rho < 1/(2L)).
- Weak MVI case: inexact KM attains rho < 1/L with Õ(ε^{-2}) oracle complexity, best known up to log factors.
- Stochastic weak MVI with MLMC estimator achieves expected SFO complexity Õ(ε^{-4}); stochastic cohypomonotone last-iterate complexity Õ(ε^{-4}) versus prior Õ(ε^{-16}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use conic nonexpansiveness and apply Halpern iteration to the averaged resolvent | Inexact Halpern iteration for cohypomonotone problems · Cohypomonotone deterministic problems | upper bound of ρ: \frac{1}{2L} -> \frac{1}{L} | Helped |
| Use conic quasi-nonexpansiveness in the KM analysis | Inexact KM iteration for weak MVI problems · Weak MVI deterministic problems | upper bound of ρ: \frac{1}{2L} -> \frac{1}{L} | Helped |
| Relax the resolvent inexactness requirement from \widetilde{O}(k^{-3}) to \widetilde{O}(k^{-3/2}) | Inexact Halpern iteration · Monotone inclusions | resolvent inexactness: \widetilde{O}(k^{-3}) -> \widetilde{O}(k^{-3/2}) | Helped |
| Use the refined inexactness analysis rather than the existing analyses | Stochastic inexact Halpern iteration for cohypomonotone problems · Cohypomonotone stochastic problems | SFO complexity: \widetilde{O}(\varepsilon^{-7}) -> \widetilde{O} (\varepsilon^{-4}) | Helped |
| Use an MLMC estimator to control resolvent-estimator bias | Inexact KM for weak MVI problems · Weak MVI stochastic problems | expected SFO complexity: \widetilde{O}(\varepsilon^{-6}) -> \widetilde{O} (\varepsilon^{-4}) | Helped |
| Use stochastic inexact Halpern iteration with stochastic FBF resolvent approximation | Cohypomonotone stochastic problems · Cohypomonotone stochastic problems | SFO complexity: \widetilde{O}(\varepsilon^{-16}) -> \widetilde{O} (\varepsilon^{-4}) | Helped |
| Use stochastic KM with an MLMC estimator instead of standard stochastic KM | Weak MVI stochastic problems · Weak MVI stochastic problems | expected SFO complexity: \widetilde{O}(\varepsilon^{-6}) -> \widetilde{O} (\varepsilon^{-4}) | Helped |
Surprising findings
- Tighter inexactness schedule (k^{-3/2} rather than k^{-3}) for Halpern iteration suffices, improving even convex-concave stochastic complexity bounds.
Limitations
- Double-loop algorithms introduce an extra log factor in complexity.
- Constant in complexity deteriorates as rho approaches eta.
- Stochastic cohypomonotone result is last-iterate Õ(ε^{-4}) without matching the unconstrained ε^{-2} rate; open for constrained setting.
Experimental setup
Metrics: oracle complexity to reach dist(0,(F+G)(x)) <= epsilon fixed-point residual rate
Baselines: Diakonikolas et al. 2021 (Halpern cohypomonotone, rho < 1/(2L)) Pethick et al. 2022 Böhm 2022 (weak MVI KM) Gorbunov et al. 2022 Lee & Kim 2021 Pethick et al. 2023 (0.63/L)
Builds on: Halpern iteration Krasnosel'skii-Mann iteration forward-backward-forward (FBF) conic nonexpansiveness (Bauschke et al.) cohypomonotonicity
Closest papers by meaning
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.88)
- Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities (NeurIPS 2024 · similarity 0.87)
- Semi-infinite Nonconvex Constrained Min-Max Optimization (NeurIPS 2025 · similarity 0.87)
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.87)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.87)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.87)
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.