# ADMM diverges on L1 regression

TLDR: Why does ADMM diverge when solving $$\ell_1$$ regression?

## Introduction

I am learning about convex optimisation and wanted to solve a simple exercise that I am having issues with. I want to solve a $$\ell_1$$ regression using ADMM (Alternating Direction Method of Multiplies, https://stanford.edu/~boyd/admm.html). Not because I have to, but because I want to try it and have a little fun.

## Problem set up

The problem is:

$$\min_\beta \|X\beta -y \|_1$$

where $$X$$ has dimensions $$N \times D$$, $$\beta$$ is a $$D$$-dimensional vector and $$y$$ has length $$N$$.

What I wanted to try is using an augmented variable $$\alpha$$ to make the problem linear. That is, I want to solve

$$\min_{\alpha, \beta} \alpha^\top 1_N \quad \text{s.t.} \quad X\beta-y \leq \alpha \quad \text{and} \quad -X\beta + y \leq \alpha$$

these constraints are quivalent to $$|X\beta-y| \leq \alpha$$.

I now write down the Augmented Lagrangian:

$$\mathcal{L}=\alpha^\top 1_N + \lambda_1 (\alpha-X\beta+y) + \lambda_2 (\alpha+X\beta-y) + \rho_1/2 \|\alpha-X\beta+y\|_2^2 + \rho_2/2 \|\alpha+X\beta-y\|_2^2$$

with $$\lambda_1 \leq 0$$ and $$\lambda_2 \leq 0$$ (Constraint should be positive, so during minimisation the $$\lambda$$s should be negative. See Bishop, Pattern Recognition Appendix).

I initialise: $$\rho_1 \leftarrow 1$$ $$\rho_2 \leftarrow 1$$ $$\lambda_1 \leftarrow 1_N$$ $$\lambda_2 \leftarrow 1_N$$ $$\alpha \leftarrow |X\beta-y|$$

Now I update in the following order:

We solve $$\nabla_\beta \mathcal{L}=0$$ and use the pseudo inverse (same as OLS estimator) to get

$$\beta \leftarrow \frac{1}{\lambda_1-\lambda_2 + \rho_1 - \rho_2} (X^\top X)^{-1}X^\top \left[\lambda_1 (\alpha + y) + \lambda_2 (\alpha - y) + \rho_1 (\alpha + y) + \rho_2 (\alpha - y) \right]$$

We solve $$\nabla_\alpha \mathcal{L}=0$$

$$\alpha \leftarrow - \frac{1}{\rho_1 + \rho_2} \left[1_N + \lambda_1 + \lambda_2 +(\rho_2-\rho_1) (X \beta - y) \right]$$

Next the dual ascent on $$\lambda_1$$:

$$\lambda_1 \leftarrow \max \{\lambda_1 + \rho_1 (\alpha-X\beta+y), 0\}$$

and $$\lambda_2$$:

$$\lambda_2 \leftarrow \max \{ \lambda_2 + \rho_2 (\alpha+X\beta-y), 0 \}$$

## The Issue

$$\alpha$$ grows to $$-\infty$$ quite quickly and the loss goes to $$\infty$$. I can't seem to make it stop. What am I doing wrong? I tried playing with hyperparameters.

ADMM assumes that the constraints being added as penalties are equality constraints. In your reformulation of the l1 objective into inequality constraints i.e., $$X\beta - y \leq \alpha$$ and $$-X \beta + y \leq \alpha$$, you first have to convert those inequality constraints into equality constraints using slack variables and then dualize those equalities.

I implemented @batwing's suggestion and it works. Let $$\phi_1 \geq 0$$, $$\phi_2 \geq 0$$ be slack variables (which we initialise to $$0_N$$), the Lagrangian becomes:

$$\mathcal{L}=\alpha^\top 1_N + \lambda_1^\top (\alpha-X\beta+y-\phi_1) + \lambda_2^\top(\alpha+X\beta-y-\phi_2) + \rho_1/2 \|\alpha-X\beta+y-\phi_1\|_2^2 + \rho_2/2 \|\alpha+X\beta-y-\phi_2\|_2^2$$ with $$\phi_1 \geq 0$$ and $$\phi_2 \geq 0$$.

The update for $$\beta$$ becomes:

$$\beta \leftarrow - \frac{1}{\rho_1 + \rho_2} (X^\top X)^{-1}X^\top \left[ (\lambda_2 - \lambda_2) - \rho_1(\alpha + y - \phi_1) + \rho_2 (\alpha-y-\phi_2) \right]$$

The update for $$\alpha$$ becomes:

$$\alpha \leftarrow - \frac{1}{\rho_1 + \rho_2} \left[1_N + \lambda_1 + \lambda_2 +(\rho_2-\rho_1) (X \beta - y) - \rho_1 \phi_1 - \rho_2 \phi_2 \right]$$

Solve for $$\phi_1$$ and $$\phi_2$$:

$$\phi_1 \leftarrow \max\left(0, \frac{1}{\rho_1}\lambda_1 + \alpha - X\beta + y \right)$$ $$\phi_2 \leftarrow \max\left(0, \frac{1}{\rho_1}\lambda_1 + \alpha + X\beta - y \right)$$

And then we perform dual ascent on dual and slack variables:

$$\lambda_1 \leftarrow \lambda_1 + \rho_1 (\alpha-X\beta+y-\phi_1)$$ $$\lambda_2 \leftarrow \lambda_2 + \rho_2 (\alpha+X\beta-y-\phi_2)$$

And now it works :)

• One comment, since slack variables are primal variables, I believe the standard way of ADMM update should be to perform slack variable minimization before dual ascent. Also, note that by introducing slack variables $\phi$, you should also introduce the constraint $\phi \geq 0$. I did not see that manifest in your formulation. Apr 9 at 18:07
• @batwing thanks for your comment. I was under the impresison that squaring $\phi$ means I do not have to constrain it. Apr 9 at 21:22
• Squaring $\phi$ makes the equality constraint non-convex. TBH, I am not aware whether ADMM coverges to the optimal solution for equality constrained quadratic constraints. Apr 9 at 21:32
• Thanks. So if I dont square $\phi$, do I just clamp it to $\phi \geq 0$ after each gradient descent update? Apr 9 at 21:46
• I was suggesting that $\alpha^{(t)}, \beta^{(t)}$ depend on $\phi_1^{(t-1)}, \phi_2^{(t-1)}$, while $\phi_1^{(t)}, \phi_2^{(t)}$ depends on $\alpha^{(t)}, \beta^{(t)}$ . Apr 11 at 13:33