1
$\begingroup$

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form:

$\min \text{ } f(X) + g(Z)$

$\text{s.t. } AX + BZ = C$

where $X$, $Z$ and $C$ are real matrices and both functions - $f$ and $g$ - are convex. The methodology is rather straightforward: write the augmented Lagrangian, update $X$ by minimizing it w.r.t. to $X$ while keeping $Z$ and $M$ (Lagrangian multiplier) constants; in a similar fashion update $Z$ and then update $M$. http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf here you can find all the necessary details.

Consider the following problem:

$\argmin \limits_P \text{ }\lambda \|X-PX\|_1 + \frac{1}{\beta}\|Y-P\|^2_F$

Where $Y$ and $X$ are given constant matrices and $\lambda$, $\beta$ are given constants. Let $J = X-PX$. Then we can write:

$\min_{P,J}\lambda \|J\|_1 + \frac{1}{\beta}\|Y-P\|^2_F$

$\text{s.t. } J+PX=X$

which is of the form ADMM is designed to solve.

Now, notice the role of $\lambda$ and $\beta_k$; they facilitate a trade-off between minimizing the first norm of $X-PX$ and getting closer to the matrix $Y$. Intuitively, they can be well-interpreted as respective weights.

Now, here is the thing I do not understand: let $\lambda=1$ and let's take two values of $\beta$: say, $\beta_1 = 0.1$ and $\beta_2 = 0.001$. Let the metric for convergence be the primal residual, namely, $R_k = J_k+P_kX-X$. Let's take a fixed number of iterations, say, 30. Then it turns out that the value of the convergence metric for these two different values of $\beta$ and a fixed number of iterations is different by a factor of more than 2.

To put in a different way: for the a smaller value of $\beta_k$ algorithm converges perceptibly slower. Why this is the case?

Update for $J$ is given by the soft thresholding operator with a threshold value given by $\lambda/\rho$, applied to $X-PX-\frac{M}{\rho}$, where $\rho$ is a constant in front of the extra term in the augmented Lagrangian (step-size for the $M$ update).

Update for $P$ is given by $P = (Y-\beta M X^T + (X-J)\beta \rho X^T)(I + \beta \rho X X^T)$, where $I$ is the identity matrix.

$\endgroup$
  • $\begingroup$ Intuitively, what happens when $\beta\rightarrow 0$ ? Intuitively I would have guessed that it would converge faster, but apparently I'm wrong. I think this has something to do with the proximals operators in the update equations. $\endgroup$ – Bertrand R Aug 12 '14 at 11:53
  • $\begingroup$ Are you using the same ADMM step size with both values of $\beta$? How did you pick the ADMM step size? $\endgroup$ – littleO Aug 12 '14 at 12:17
  • $\begingroup$ Out of curiosity, what application does this problem arise in? $\endgroup$ – littleO Aug 12 '14 at 12:19
  • $\begingroup$ Bertrand, proximal operator is used for the update of J only; but as you can see now (sorry, I forgot to mention), beta_k is not involved there. $\endgroup$ – trembik Aug 12 '14 at 14:33
  • $\begingroup$ littleO, I vary penalty parameter to speed up the convergence; you can look it up if you follow the link I gave above, page 20. $\endgroup$ – trembik Aug 12 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.