Abstract
This paper presents the first variance-reduced adaptations of the Halpern iteration for solving finite-sum monotone inclusion problems. By integrating the classical Halpern method with modern variance reduction techniques such as PAGE, the authors achieve a near-optimal oracle complexity of $O(n + \sqrt{n}L\epsilon^{-1})$. This result provides a $\sqrt{n}$ speedup over deterministic methods while maintaining "last-iterate" convergence guarantees for a computable optimality measure, addressing a significant gap in stochastic optimization for equilibrium problems.
Introduction
In modern machine learning, the focus is shifting from simple empirical risk minimization toward solving complex equilibrium problems. These problems, which include training Generative Adversarial Networks (GANs), multi-agent reinforcement learning, and robust optimization, are mathematically formulated as Monotone Inclusion (MI) problems. The goal is to find a point $x^*$ such that $0 \in A(x) + B(x)$, where $A$ and $B$ are monotone operators.
A critical challenge in these applications is the "finite-sum" structure, where the operator is an average of $n$ components corresponding to individual data points. While stochastic methods exist for minimizing the duality gap, this measure is often impractical to compute or ill-defined on unbounded domains. Practitioners instead prefer the operator norm residual—a metric that measures how close the current iterate is to a true equilibrium. However, existing stochastic methods for the residual have historically been suboptimal or lacked the "last-iterate" convergence properties that ensure the final output of the algorithm is the most accurate.
Methodology
The authors address these limitations by leveraging the Halpern iteration, a fixed-point algorithm known for its strong performance on residuals in deterministic settings. They propose two primary algorithmic frameworks to handle the finite-sum structure efficiently.
1. The Cocoercive Case (Algorithm 1)
For operators that are "on average" cocoercive—a property stronger than monotonicity but common in smooth minimization—the authors integrate the Probabilistic Gradient Estimator (PAGE) variance reduction technique directly into a constrained Halpern iteration. This results in a "direct," single-loop algorithm that maintains the simplicity of the original Halpern method while significantly reducing the per-iteration cost.
2. The Monotone Lipschitz Case (Algorithm 2)
In the more general case where operators are monotone and Lipschitz continuous, the "resolvent" (a proximal-like step) is typically too expensive to compute exactly. The authors employ an Inexact Halpern Iteration, where the inner subproblem is solved approximately using a variance-reduced subsolver called VR-FoRB.
The core technical contribution lies in a new stochastic error analysis and the development of a specific potential function. This allows the authors to prove that the approximation errors from the subsolver do not accumulate in a way that degrades the overall convergence rate.
Theoretical and Empirical Results
Oracle Complexity and Speedup
The proposed algorithms achieve an expected oracle complexity of $\tilde{O}(n + \sqrt{n}L\epsilon^{-1})$. Compared to the best deterministic Halpern methods, which require $O(nL\epsilon^{-1})$ operations, this represents a speedup by a factor of $\sqrt{n}$. For large-scale datasets where $n$ is substantial (e.g., $n=10,000$), this translates to a theoretical 100x improvement in efficiency.
Key Insights
- Last-Iterate Convergence: Unlike many stochastic algorithms that only guarantee the quality of the average of all iterates, these Halpern-based methods guarantee that the very last iterate is accurate. This is highly desirable for real-world deployment.
- Verifiable Exit Criteria: Because the operator residual is computable, these algorithms provide a verifiable stopping criterion. Engineers can monitor the residual and stop the algorithm once the desired accuracy $\epsilon$ is reached, rather than relying on heuristics.
- Near-Optimality: The authors demonstrate that their complexity is unimprovable (up to logarithmic factors) in the monotone Lipschitz setting, suggesting they have reached the theoretical lower bounds for this class of problems.
Numerical Performance
The algorithms were evaluated on structured synthetic problems, including Matrix Games (specifically the "policeman and burglar" benchmark) and difficult Quadratic Programs designed to establish lower bounds in min-max optimization. In these tests, the proposed methods converged significantly faster than deterministic baselines like the Extra-Gradient (EG) and Extra-Anchor Gradient (EAG) methods. Notably, while other variance-reduced methods like VR-EG often stagnated on difficult worst-case instances, the Halpern-based methods maintained steady progress.
Conclusion and Future Work
This work successfully bridges the gap between variance reduction and Halpern iterations, providing a robust framework for solving finite-sum monotone inclusions with last-iterate guarantees.
While Algorithm 1 offers a simple single-loop structure for cocoercive operators, Algorithm 2 for the Lipschitz monotone case remains "indirect" due to its nested subsolver. The authors identify the development of a direct, single-loop algorithm for the general Lipschitz monotone case as a primary open question. Additionally, refining the analysis to remove the remaining polylogarithmic factors in the complexity bounds would further solidify the theoretical foundation of these methods.
Summary updated