Research map / Learning theory and algorithms / Submodular and game algorithms
Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions
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.
Proposes variance-reduced Halpern iterations for finite-sum monotone inclusions that achieve O~(n + sqrt(n) L/eps) oracle complexity for last-iterate operator norm residual, improving on deterministic methods by up to sqrt(n).
Problem
Finding approximate solutions of finite-sum monotone inclusions (and VIs / min-max problems) with guarantees on the last iterate and a computable operator norm residual, where existing methods either lack variance reduction for residuals or have suboptimal complexity.
Approach
Combine the Halpern iteration with PAGE-style recursive variance reduction (single-loop, cocoercive case) and, for the monotone Lipschitz case, use an inexact Halpern iteration whose resolvent is approximated by a variance-reduced forward-reflected-backward subsolver with a randomized inexactness criterion.
Key results
- Cocoercive case: oracle complexity O~(n + sqrt(n) L/eps) for expected residual, improving on deterministic Halpern's O~(n L_F/eps) by up to sqrt(n).
- Monotone Lipschitz case: same O~(n + sqrt(n) L/eps) complexity via inexact Halpern with VR-FoRB subsolver, argued near-optimal up to log factors.
- Numerically, variance-reduced Halpern variants converge faster than deterministic EG and EAG in epochs; VR-EG is slightly faster on some instances but stagnates on the hard instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PAGE variance reduction in constrained Halpern iteration | Halpern iteration · Finite-sum monotone inclusion, average cocoercivity | oracle complexity: \widetilde{\mathcal{O}}(nL_F\varepsilon^{-1}) -> \widetilde{\mathcal{O}}\big( n + \frac{\sqrt{n}L\|\vu_0 - \vu_*\|}{\var | Helped |
| Use inexact resolvent evaluations computed by variance-reduced VR-FoRB | Halpern iteration · Finite-sum monotone inclusion, monotone Lipschitz | oracle complexity: \Tilde{\mathcal{O}}( nL_F\varepsilon^{-1} ) -> \Tilde{\gO}\big(n + \frac{\sqrt{n}L\|\vu_0 - \vu_*\|}{\varepsilon}\big) | Helped |
| Use variance-reduced Halpern algorithms instead of deterministic methods | Matrix game and quadratic program · Matrix game and quadratic program | operator norm | Helped |
| Use VR-EG instead of the proposed Halpern-type algorithms | Matrix game and quadratic program · Matrix game and quadratic program | operator norm | Mixed |
| Use non-uniform importance sampling | Inexact Halpern iteration with VR-FoRB · Matrix games | oracle complexity | Helped |
Surprising findings
- VR-EG converges slightly faster than the proposed Halpern-type methods on the matrix game, while the proposed methods keep progressing on the hard instance where VR-EG stagnates.
Limitations
- Monotone Lipschitz result relies on an indirect algorithm (randomized resolvent approximation) rather than a direct method.
- Cohypomonotone extension requires restrictive bound on rho (roughly rho < L/(sqrt(n) L_F^2)) and G=0.
- Complexity is in expectation; high-probability guarantees need repeated runs with residual monitoring.
Experimental setup
Datasets: matrix games (policeman and burglar matrix, 500x500) quadratic program lower-bound instance (200x200)
Benchmarks: matrix game with simplex constraints (m=500) quadratic program min-max instance (m=200)
Metrics: operator norm / gradient mapping norm vs. epochs
Baselines: extragradient (EG) extra anchored gradient (EAG) variance-reduced extragradient (VR-EG)
Builds on: Halpern iteration PAGE estimator VR-FoRB extragradient extra anchored gradient
Closest papers by meaning
- Monotone Inclusion Approach to Weakly Monotone Discrete-Time Finite-Horizon Mean-Field Games (NeurIPS 2026 · similarity 0.87)
- Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities (NeurIPS 2024 · similarity 0.87)
- Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity (ICML 2024 · similarity 0.86)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.85)
- Solving hidden monotone variational inequalities with surrogate losses (ICLR 2025 · similarity 0.85)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.85)
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.