2
$\begingroup$

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.

Edit: Google Colab Notebook

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 :)

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – batwing
    Apr 9 at 18:07
  • $\begingroup$ @batwing thanks for your comment. I was under the impresison that squaring $\phi$ means I do not have to constrain it. $\endgroup$ Apr 9 at 21:22
  • $\begingroup$ 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. $\endgroup$
    – batwing
    Apr 9 at 21:32
  • $\begingroup$ Thanks. So if I dont square $\phi$, do I just clamp it to $\phi \geq 0$ after each gradient descent update? $\endgroup$ Apr 9 at 21:46
  • 1
    $\begingroup$ 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)}$ . $\endgroup$
    – batwing
    Apr 11 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.