# ALS: Augmented Lagrangian Sketching Methods for Linear Systems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 12 Aug 2022.

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

- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [SEGA: Variance Reduction via Gradient Sketching](https://mlsanity.com/paper/1809.03054/) (2018)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory](https://mlsanity.com/paper/1706.01108/) (2017)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [An Accelerated Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1310.2887/) (2013)
- [Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization](https://mlsanity.com/paper/1802.04079/) (2018)
- [A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility](https://mlsanity.com/paper/1605.01418/) (2016)
- [Stochastic Dual Ascent for Solving Linear Systems](https://mlsanity.com/paper/1512.06890/) (2015)
- [Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration](https://mlsanity.com/paper/2002.07321/) (2020)
- [A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing](https://mlsanity.com/paper/1403.7543/) (2014)
- [Stochastic Spectral and Conjugate Descent Methods](https://mlsanity.com/paper/1802.03703/) (2018)
- [Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem](https://mlsanity.com/paper/1902.03502/) (2019)
- [Penalty & Augmented Kaczmarz Methods For Linear Systems & Linear Feasibility Problems](https://mlsanity.com/paper/2205.08085/) (2022)
- [Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems](https://mlsanity.com/paper/2009.08251/) (2020)
- [Sketch & Project Methods for Linear Feasibility Problems: Greedy Sampling & Momentum](https://mlsanity.com/paper/2012.02913/) (2020)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)

## Abstract (arXiv)

We develop two fundamental stochastic sketching techniques; Penalty Sketching (PS) and Augmented Lagrangian Sketching (ALS) for solving consistent linear systems. The proposed PS and ALS techniques extend and generalize the scope of Sketch & Project (SP) method by introducing Lagrangian penalty sketches. In doing so, we recover SP methods as special cases and furthermore develop a family of new stochastic iterative methods. By varying sketch parameters in the proposed PS method, we recover novel stochastic methods such as Penalty Newton Descent, Penalty Kaczmarz, Penalty Stochastic Descent, Penalty Coordinate Descent, Penalty Gaussian Pursuit, and Penalty Block Kaczmarz. Furthermore, the proposed ALS method synthesizes a wide variety of new stochastic methods such as Augmented Newton Descent, Augmented Kaczmarz, Augmented Stochastic Descent, Augmented Coordinate Descent, Augmented Gaussian Pursuit, and Augmented Block Kaczmarz into one framework. Moreover, we show that the developed PS and ALS frameworks can be used to reformulate the original linear system into equivalent stochastic optimization problems namely the Penalty Stochastic Reformulation and Augmented Stochastic Reformulation. We prove global convergence rates for the PS and ALS methods as well as sub-linear O(frac1k) rates for the Cesaro average of iterates. The proposed convergence results hold for a wide family of distributions of random matrices, which provides the opportunity of fine-tuning the randomness of the method suitable for specific applications. Finally, we perform computational experiments that demonstrate the efficiency of our methods compared to the existing SP methods.