# Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 2 Jun 2022.

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

- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problems](https://mlsanity.com/paper/2203.04869/) (2022)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [On Accelerated Methods for Saddle-Point Problems with Composite Structure](https://mlsanity.com/paper/2103.09344/) (2021)
- [New First-Order Algorithms for Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.08341/) (2021)
- [Iteration complexity of first-order augmented Lagrangian methods for convex conic programming](https://mlsanity.com/paper/1803.09941/) (2018)
- [An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems](https://mlsanity.com/paper/1402.5291/) (2014)
- [A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities](https://mlsanity.com/paper/2103.15270/) (2021)

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

- [Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2604.07662/) (2026)

## Abstract (arXiv)

In this paper we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone while the other is it locally Lipschitz continuous. We propose primal-dual extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of cal O(log ε-1) and cal O(ε-1log ε-1), measured by the number of fundamental operations consisting only of evaluations of one operator and resolvent of the other operator, for finding an varepsilon-residual solution of strongly and non-strongly MI problems, respectively. The latter complexity significantly improves the previously best operation complexity cal O(varepsilon-2). As a byproduct, complexity results of the primal-dual extrapolation methods are also obtained for finding an varepsilon-KKT or varepsilon-residual solution of convex conic optimization, conic constrained saddle point, and variational inequality problems under it local Lipschitz continuity. We provide preliminary numerical results to demonstrate the performance of the proposed methods.