# Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions

arXiv: https://arxiv.org/abs/2110.08150 · HTML: https://mlsanity.com/paper/2110.08150/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 73 references that are in the map.
- First posted on arXiv 15 Oct 2021.

## Builds on (most cited first, 22 of 22)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Generalized monotone operators and their averaged resolvents](https://mlsanity.com/paper/1902.09827/) (2019)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Convergence rate analysis of several splitting schemes](https://mlsanity.com/paper/1406.4834/) (2014)
- [A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization](https://mlsanity.com/paper/1507.06243/) (2015)
- [Fast convergence of generalized forward-backward algorithms for structured monotone inclusions](https://mlsanity.com/paper/2107.10107/) (2021)
- [An inertial forward-backward algorithm for monotone inclusions](https://mlsanity.com/paper/1403.3522/) (2014)
- [Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions](https://mlsanity.com/paper/1407.5210/) (2014)
- [Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants](https://mlsanity.com/paper/1407.6723/) (2014)
- [Inertial Douglas-Rachford splitting for monotone inclusion problems](https://mlsanity.com/paper/1403.3330/) (2014)
- [Convergence rate analysis of the forward-Douglas-Rachford splitting scheme](https://mlsanity.com/paper/1410.2654/) (2014)
- [Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive stepsizes and convergence](https://mlsanity.com/paper/1801.03765/) (2018)
- [Convergence rate analysis of primal-dual splitting schemes](https://mlsanity.com/paper/1408.4419/) (2014)
- [On the Douglas-Rachford algorithm](https://mlsanity.com/paper/1604.04603/) (2016)

## Built on by (most cited first, 21 of 21)

- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [Extragradient-Type Methods with O (1/k) Last-Iterate Convergence Rates for Co-Hypomonotone Inclusions](https://mlsanity.com/paper/2302.04099/) (2023)
- [Negative Momentum for Convex-Concave Optimization](https://mlsanity.com/paper/2604.17145/) (2026)
- [A Unifying View of Anchoring via Operator-Side Tikhonov Regularization](https://mlsanity.com/paper/2605.30905/) (2026)
- [Accelerated and Stable Convergence with Anchored Generalized Optimistic Method](https://mlsanity.com/paper/2606.21528/) (2026)
- [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)
- [Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems](https://mlsanity.com/paper/2609.30212/) (2026)
- [Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding](https://mlsanity.com/paper/2609.36033/) (2026)

## Abstract (arXiv)

In this paper, we develop a new type of accelerated algorithms to solve some classes of maximally monotone equations as well as monotone inclusions. Instead of using Nesterov's accelerating approach, our methods rely on a so-called Halpern-type fixed-point iteration in [32], and recently exploited by a number of researchers, including [24, 70]. Firstly, we derive a new variant of the anchored extra-gradient scheme in [70] based on Popov's past extra-gradient method to solve a maximally monotone equation G(x) = 0. We show that our method achieves the same O(1/k) convergence rate (up to a constant factor) as in the anchored extra-gradient algorithm on the operator norm Vert G(xk)Vert, , but requires only one evaluation of G at each iteration, where k is the iteration counter. Next, we develop two splitting algorithms to approximate a zero point of the sum of two maximally monotone operators. The first algorithm originates from the anchored extra-gradient method combining with a splitting technique, while the second one is its Popov's variant which can reduce the per-iteration complexity. Both algorithms appear to be new and can be viewed as accelerated variants of the Douglas-Rachford (DR) splitting method. They both achieve O(1/k) rates on the norm Vert Gγ(xk)Vert of the forward-backward residual operator Gγ(·) associated with the problem. We also propose a new accelerated Douglas-Rachford splitting scheme for solving this problem which achieves O(1/k) convergence rate on Vert Gγ(xk)Vert under only maximally monotone assumptions. Finally, we specify our first algorithm to solve convex-concave minimax problems and apply our accelerated DR scheme to derive a new variant of the alternating direction method of multipliers (ADMM).