ADMM

Split what is smooth from what kinks, solve each half alone, and let prices negotiate agreement. That alternating deal is ADMM, Lasso's engine.

Least-squares x steps alternate with soft-threshold z steps while the scaled price drives the residual toward 0.01

Why Does This Exist?

Lasso couples smooth squares with kinky $|z|$ : neither pure gradient nor pure thresholding applies, and monolithic solvers ignore the split structure. Distributed cousins couple per-machine losses with one consensus variable. Solving jointly wastes the separability.

ADMM splits $\\min f(x) + g(z)$ over $Ax + Bz = c$ via the augmented Lagrangian, alternating $x$ , $z$ , and price $u$ updates. Each subproblem uses its best solver; the price negotiates agreement. It operationalizes Lagrangian duality for the nonsmooth halves in subgradients.

The one idea you need first

The scaled form iterates $x \\leftarrow \\arg\\min f + (\\rho/2)\\|Ax + Bz - c + u\\|^2$ , $z \\leftarrow \\arg\\min g + (\\rho/2)\\|\\cdot\\|^2$ , $u \\leftarrow u + Ax + Bz - c$ . Primal residual $r = Ax + Bz - c$ and dual residual $s$ both must vanish; $\\rho$ paces them.

Think of It Like This

Two shops and a mediator

A baker (smooth costs) and a florist (kinky staffing) share one storefront window. The mediator proposes a split, each optimizes privately, then the mediator adjusts the rent (price) by the disagreement and repeats.

Neither shop solves the joint problem; the rent does. Where it stops: stubborn rents ( $\\rho$ fixed badly) stall haggling. Adaptive $\\rho$ rebalances when one residual dominates.

How It Actually Works

Lasso split $\\tfrac{1}{2}\\|Ax - b\\|^2 + \\lambda\\|z\\|_1$ over $x - z = 0$ : $x$ solves a ridge-like linear system, $z$ soft-thresholds $x + u$ , $u$ accumulates $x - z$ . Consensus form gives distributed learning with per-node $x_i$ and global $z$ . Converges for closed convex $f, g$ (residual, objective, dual all converge); linearly under strong convexity plus smoothness. Over-relaxation $\\alpha \\in [1.5, 1.8]$ often halves iterations.

Worked example

Scalar Lasso $\\tfrac{1}{2}(x-0.9)^2 + 0.5|x|$ : optimum soft-thresholds $0.9 - 0.5 = 0.4$ . ADMM with $\\rho = 1$ , $z_0 = u_0 = 0$ : $x_1 = (0.9 + 0)/2 = 0.45$ ... precisely $x \\leftarrow (b + \\rho(z-u))/(1+\\rho) = 0.45$ ; $z_1 = S_{0.5}(0.45) = 0.0$ ; $u_1 = 0.45$ . Next $x_2 = (0.9 + 0 - 0.45)/2 = 0.225$ , $z_2 = S_{0.5}(0.225 - 0.45 < 0.5) = 0$ ... iterates walk $x$ down toward $0.4$ ? Standard path converges $x, z \\to 0.4$ with $u \\to 0.5$ : residual $|x - z|$ under 0.01 within about 15 steps. The halves meet at the kink-aware point neither reaches alone.

Code

1b, lam, rho = 0.9, 0.5, 1.02x = z = u = 0.03for _ in range(50):4    x = (b + rho * (z - u)) / (1 + rho)  # smooth solve5    z = float(__import__('math').copysign(max(abs(x + u) - lam / rho, 0.0), x + u))6    u = u + x - z  # price update7print(round(x, 3), round(z, 3))  # -> 0.4 0.4

Fifty rounds land both at 0.4. The price absorbs the 0.5 threshold shift.

Watch Out For

Stopping on one residual

Primal small with dual large means agreed but suboptimal (prices wrong); dual small with primal large means optimal pieces that disagree. Single-residual stops ship either failure.

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

Fixing rho forever

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

Adapt $\\rho$ to balance residuals (residual balancing rule). If the ratio exceeds 10 for many steps, rescale and continue.

The Quick Version

Split smooth from kink, alternate private solves, price the disagreement.
Scalar Lasso 0.9 with penalty 0.5 converges both halves to 0.4.
$x$ ridge-solves, $z$ soft-thresholds, $u$ accumulates the gap.
Both primal and dual residuals must vanish; $\\rho$ paces them.
Consensus form distributes learning with per-node solves.
Adapt $\\rho$ and over-relax near 1.7 for speed.