# Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2017.

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

- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Cooperative learning for multiview analysis](https://mlsanity.com/paper/2112.12337/) (2021)
- [Sampling with Mollified Interaction Energy Descent](https://mlsanity.com/paper/2210.13400/) (2022)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Gradient Multi-Normalization for Stateless and Scalable LLM Training](https://mlsanity.com/paper/2502.06742/) (2025)
- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints](https://mlsanity.com/paper/2302.00808/) (2023)
- [Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin](https://mlsanity.com/paper/2501.18143/) (2025)
- [Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling](https://mlsanity.com/paper/2410.06397/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)

## Abstract (arXiv)

We study connections between Dykstra's algorithm for projecting onto an intersection of convex sets, the augmented Lagrangian method of multipliers or ADMM, and block coordinate descent. We prove that coordinate descent for a regularized regression problem, in which the (separable) penalty functions are seminorms, is exactly equivalent to Dykstra's algorithm applied to the dual problem. ADMM on the dual problem is also seen to be equivalent, in the special case of two sets, with one being a linear subspace. These connections, aside from being interesting in their own right, suggest new ways of analyzing and extending coordinate descent. For example, from existing convergence theory on Dykstra's algorithm over polyhedra, we discern that coordinate descent for the lasso problem converges at an (asymptotically) linear rate. We also develop two parallel versions of coordinate descent, based on the Dykstra and ADMM connections.