# Convergence rate analysis of several splitting schemes

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2014.

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

- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [ALPS: Improved Optimization for Highly Sparse One-Shot Pruning for Large Language Models](https://mlsanity.com/paper/2406.07831/) (2024)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Distributed Learning With Sparsified Gradient Differences](https://mlsanity.com/paper/2202.02491/) (2022)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [LMI-Net: Linear Matrix Inequality--Constrained Neural Networks via Differentiable Projection Layers](https://mlsanity.com/paper/2604.05374/) (2026)
- [Solving Constrained Variational Inequalities via a First-order Interior Point-based Method](https://mlsanity.com/paper/2206.10575/) (2022)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [3BASiL: An Algorithmic Framework for Sparse plus Low-Rank Compression of LLMs](https://mlsanity.com/paper/2603.01376/) (2026)
- [ADMM-Q: An Improved Hessian-based Weight Quantizer for Post-Training Quantization of Large Language Models](https://mlsanity.com/paper/2605.11222/) (2026)
- [Last-Iterate Guarantees for Learning in Co-coercive Games](https://mlsanity.com/paper/2604.19065/) (2026)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)

## Abstract (arXiv)

Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. In the first part of this paper, we analyze the convergence rates of several general splitting algorithms and provide examples to prove the tightness of our results. The most general rates are proved for the fixed-point residual (FPR) of the Krasnosel'skiui-Mann (KM) iteration of nonexpansive operators, where we improve the known big-O rate to little-o. We show the tightness of this result and improve it in several special cases. In the second part of this paper, we use the convergence rates derived for the KM iteration to analyze the objective error convergence rates for the Douglas-Rachford (DRS), Peaceman-Rachford (PRS), and ADMM splitting algorithms under general convexity assumptions. We show, by way of example, that the rates obtained for these algorithms are tight in all cases and obtain the surprising statement: The DRS algorithm is nearly as fast as the proximal point algorithm (PPA) in the ergodic sense and nearly as slow as the subgradient method in the nonergodic sense. Finally, we provide several applications of our result to feasibility problems, model fitting, and distributed optimization. Our analysis is self-contained, and most results are deduced from a basic lemma that derives convergence rates for summable sequences, a simple diagram that decomposes each relaxed PRS iteration, and fundamental inequalities that relate the FPR to objective error.