ADMM

Split a hard problem into an easy smooth piece and an easy kinked piece, solve each alone, and let a price nudge them into agreement. Repeating that deal solves Lasso and distributed fits neither half can solve alone.

Why Does This Exist?

Lasso couples a smooth square with a kinky absolute value, so neither pure gradient descent nor pure thresholding applies. A Lasso with 10,000 features has the same structure repeated 10,000 times, and a distributed fit across 10 machines couples 10 local losses through one consensus variable. Solving jointly wastes the separability that makes each piece easy.

ADMM splits $\min f(x) + g(z)$ subject to $Ax + Bz = c$ , where $f$ is the smooth part, $g$ is the possibly nonsmooth part, and $Ax + Bz = c$ is the linear coupling, via the augmented Lagrangian and alternates an $x$ solve, a $z$ solve, and a price update. Each subproblem uses its best solver while the price negotiates agreement.

This page covers the splitting mechanism and its residuals. Convex structure lives in convex optimization, prices in Lagrangian duality, kinks in subgradients, and optimality certificates in optimality conditions.

The one idea you need first

The scaled form iterates $x \leftarrow \arg\min f + (\rho/2)\lVert Ax + Bz - c + u \rVert^2$ , then $z \leftarrow \arg\min g + (\rho/2)\lVert \cdot \rVert^2$ , then $u \leftarrow u + Ax + Bz - c$ , where $\rho$ is the penalty pace and $u$ is the scaled price. The primal residual $r = Ax + Bz - c$ measures disagreement and the dual residual $s$ measures suboptimality, and both must vanish. Background prices are in Lagrangian duality.

Think of It Like This

Two shops and a mediator

A baker with smooth oven costs and a florist with kinked staffing rules share one storefront window. The mediator proposes a split, each optimizes privately with the current rent added, then the mediator adjusts the rent by the disagreement and repeats.

The baker maps to the smooth $x$ solve, the florist maps to the thresholding $z$ solve, and the rent maps to the price $u$ . Neither shop solves the joint problem. The rent does.

Where it stops: a stubborn fixed rent stalls haggling when one residual dominates. Adaptive rents that rebalance residuals keep the deal moving.

How It Actually Works

For closed convex $f$ and $g$ , ADMM converges in residual, objective, and dual value. The $x$ update is often a ridge-like linear solve, the $z$ update is often a proximal soft threshold, and over-relaxation with $\alpha$ in $[1.5, 1.8]$ often halves iterations. The consensus form gives each machine its own $x_i$ with one global $z$ , which is how distributed Lasso and distributed SVM train without moving raw data.

Concretely for Lasso split as $(1/2)\lVert Ax - b \rVert^2 + \lambda \lVert z \rVert_1$ subject to $x - z = 0$ , where $A$ is the feature matrix, $b$ is the target, and $\lambda$ is the penalty: $x$ solves a linear system, $z$ soft-thresholds $x + u$ at $\lambda/\rho$ , and $u$ accumulates $x - z$ .

Worked example

Scalar Lasso $(1/2)(x - 0.9)^2 + 0.5\lvert x \rvert$ with split $x - z = 0$ , where $0.9$ is the least-squares target and $0.5$ is the penalty. The optimum soft-thresholds $0.9 - 0.5 = 0.4$ , since the target exceeds the penalty. Run ADMM with $\rho = 1.0$ , $z_0 = 0.0$ , $u_0 = 0.0$ , where $\rho$ paces agreement. Updates are $x \leftarrow (b + \rho(z - u))/(1 + \rho)$ and $z \leftarrow S_{0.5}(x + u)$ , where $S$ is soft thresholding $S_{\kappa}(v) = \mathrm{sign}(v)\max(\lvert v \rvert - \kappa, 0)$ .

Step 1: $x_1 = (0.9 + 0.0)/2 = 0.45$ . Then $x_1 + u_0 = 0.45$ , which is below $0.5$ , so $z_1 = 0.0$ . Price becomes $u_1 = 0.0 + 0.45 - 0.0 = 0.45$ . Primal residual is $0.45$ .

Step 2: $x_2 = (0.9 + 0.0 - 0.45)/2 = 0.225$ . Then $x_2 + u_1 = 0.675$ , minus $0.5$ gives $z_2 = 0.175$ . Price becomes $u_2 = 0.45 + 0.225 - 0.175 = 0.5$ . Residual falls to $0.05$ .

Step 3: $x_3 = (0.9 + 0.175 - 0.5)/2 = 0.2875$ . Then $x_3 + u_2 = 0.7875$ , minus $0.5$ gives $z_3 = 0.2875$ . Price stays $u_3 = 0.5$ . Residual is $0.0$ and both halves sit at $0.2875$ , walking up toward the shared $0.4$ with $u$ settled at $0.5$ . About 15 such steps land within $0.01$ of $0.4$ .

Code

The point is the check: the same three steps and the same $0.4$ landing, in plain Python.

1import math2
3
4def soft_threshold(v: float, kappa: float) -> float:5    return math.copysign(max(abs(v) - kappa, 0.0), v)6
7
8def admm_lasso(b: float, lam: float, rho: float, steps: int) -> tuple[float, float, float]:9    x: float = 0.010    z: float = 0.011    u: float = 0.012    for _ in range(steps):13        x = (b + rho * (z - u)) / (1.0 + rho)14        z = soft_threshold(x + u, lam / rho)15        u = u + x - z16    return (x, z, u)17
18
19x1, z1, u1 = admm_lasso(0.9, 0.5, 1.0, 1)20print((round(x1, 4), round(z1, 4), round(u1, 4)))  # -> (0.45, 0.0, 0.45)21
22x2, z2, u2 = admm_lasso(0.9, 0.5, 1.0, 2)23print((round(x2, 4), round(z2, 4), round(u2, 4)))  # -> (0.225, 0.175, 0.5)24
25x3, z3, u3 = admm_lasso(0.9, 0.5, 1.0, 3)26print((round(x3, 4), round(z3, 4), round(u3, 4)))  # -> (0.2875, 0.2875, 0.5)27
28x50, z50, _ = admm_lasso(0.9, 0.5, 1.0, 50)29print((round(x50, 3), round(z50, 3)))  # -> (0.4, 0.4)

Fifty rounds land both halves at $0.4$ . The price absorbs the $0.5$ threshold shift and parks at $0.5$ .

Watch Out For

Stopping on one residual

Primal small with dual large means the halves agree but prices are wrong, so the point is feasible yet suboptimal. Dual small with primal large means each piece is optimal alone but they disagree, as after step 1 above where $x_1 = 0.45$ and $z_1 = 0.0$ look agreed only if you ignore the $0.45$ gap.

Stop when both sit under tolerance with scaling. If one stalls while the other shrinks, retune $\rho$ instead of iterating.

Fixing rho forever

The default $\rho = 1.0$ on badly scaled problems imbalances residuals 100-to-1 and crawls toward $0.4$ sideways. Practitioners blame ADMM while the pace parameter idles.

Adapt $\rho$ to balance residuals, the residual-balancing rule. If the ratio exceeds 10 for many steps, rescale $\rho$ and rescale $u$ with it, then continue.

The Quick Version

ADMM splits smooth $f$ from kinked $g$ and alternates private solves with a price update.
Scalar Lasso with target $0.9$ and penalty $0.5$ converges both halves to $0.4$ .
Three steps give $(0.45, 0.0)$ , then $(0.225, 0.175)$ , then $(0.2875, 0.2875)$ with price $0.5$ .
The $x$ update ridge-solves, the $z$ update soft-thresholds, and $u$ accumulates the gap.
Both primal and dual residuals must vanish, and $\rho$ paces them.
Consensus form distributes learning with per-node solves and one global $z$ .
Adapt $\rho$ and over-relax near $1.7$ for speed.