Coordinate and block descent methods — Examples

Put $s={\theta }_1+{\theta }_2$. [F5] gives $\mathrm{\mid }{\theta }_1\mathrm{\mid }+\mathrm{\mid }{\theta }_2\mathrm{\mid }\ge \mathrm{\mid }s\mathrm{\mid }$, hence by [F1], $Q_y(\theta )\ge (1-s{)}^2+\frac{1}{2}\mathrm{\mid }s\mathrm{\mid }=2(\frac{1}{2}{s}^2-s+\frac{1}{4}\mathrm{\mid }s\mathrm{\mid })+1$. By [F3]--[F4], the scalar bracket is uniquely minimized at $s=S_{1\mathrm{/}4}(1)=3\mathrm{/}4$.

Equality in $\mathrm{\mid }{\theta }_1\mathrm{\mid }+\mathrm{\mid }{\theta }_2\mathrm{\mid }\ge \mathrm{\mid }{\theta }_1+{\theta }_2\mathrm{\mid }$ holds when the two coefficients have the same sign or one is zero. Since the minimizing sum is positive, every nonnegative pair summing to $3\mathrm{/}4$ attains the lower bound from step 1.1; every minimizer must have that sum and equality, so the displayed set is exact. It contains distinct points $(3\mathrm{/}4,0)$ and $(0,3\mathrm{/}4)$, and both fit to $3\mathrm{/}4$.

Writing $s=x_1+2x_2$, we have ${\mathrm{\nabla }}_{1}f=s$, ${\mathrm{\nabla }}_{2}f=2s$, and their coordinate Lipschitz constants are $1$ and $4$. At $x^0$, $s=1$ and $f(x^0)=1\mathrm{/}2$. If coordinate $1$ is sampled with common majorizer $4$, $x_1$ becomes $3\mathrm{/}4$, so $f=\frac{1}{2}(3\mathrm{/}4{)}^2=9\mathrm{/}32$; if coordinate $2$ is sampled, $x_2$ becomes $-1\mathrm{/}2$, so $f=0$.

Uniform averaging of the two outcomes gives expected objective $(9\mathrm{/}32+0)\mathrm{/}2=9\mathrm{/}64$. In cyclic minimization, the first coordinate minimizer at $x_2=0$ is $x_1=0$, and the second coordinate minimizer at $x_1=0$ is $x_2=0$; hence the sweep reaches the global minimum.

With $\beta =0$, bilinearity [F2] expands the terms depending on $\alpha$ as $\frac{1}{2}(\mathrm{\parallel }a{\mathrm{\parallel }}_2^2+1){\alpha }^2-(a^{T}y)\alpha$ plus a constant. Here $\mathrm{\parallel }a{\mathrm{\parallel }}_2^2+1=2$ and $a^{T}y=2$, so completing the square gives ${\alpha }^2-2\alpha =(\alpha -1{)}^2-1$ plus a constant. Thus the unique global slice minimizer is $\alpha =1$.

With $\alpha =1$, bilinearity [F2] expands the terms depending on $\beta$ as $\frac{1}{2}(\mathrm{\parallel }b{\mathrm{\parallel }}_2^2+2){\beta }^2-b^T(y-a)\beta$ plus a constant. Here $\mathrm{\parallel }b{\mathrm{\parallel }}_2^2+2=4$ and $b^T(y-a)=2$, so completing the square gives $2{\beta }^2-2\beta =2(\beta -1\mathrm{/}2{)}^2-1\mathrm{/}2$ plus a constant. Thus $\beta =1\mathrm{/}2$ is the unique global slice minimizer. The residual is $(1\mathrm{/}2,1\mathrm{/}2)$ and $J=\frac{1}{2}(1\mathrm{/}2)+\frac{1}{2}+1\mathrm{/}4=1$. At the initial point $J(0,0)=5\mathrm{/}2$, so the exact sweep decreases the objective.

Initially $r_1=y$, so $X_1^T{r}_1=2$, $\mathrm{\parallel }{X}_1{\mathrm{\parallel }}_2^2=1$, and $n\tau =1\mathrm{/}2$. The update lemma gives ${\theta }_1^1=S_{1\mathrm{/}2}(2)=3\mathrm{/}2$; holding ${\theta }_2=0$ gives residual $(1\mathrm{/}2,1)$ and objective $Q_y(3\mathrm{/}2,0)=\frac{1}{2}(1\mathrm{/}4+1)+\frac{1}{2}(3\mathrm{/}2)=11\mathrm{/}8$.

For the second block, $r_2=y-X_1(3\mathrm{/}2)=(1\mathrm{/}2,1)$, so $X_2^T{r}_2=3\mathrm{/}2$ and $\mathrm{\parallel }{X}_2{\mathrm{\parallel }}_2^2=2$. Thus ${\theta }_2^2=S_{1\mathrm{/}2}(3\mathrm{/}2)\mathrm{/}2=1\mathrm{/}2$. The final residual is $(0,1\mathrm{/}2)$ and $Q_y(3\mathrm{/}2,1\mathrm{/}2)=\frac{1}{2}(1\mathrm{/}4)+\frac{1}{2}(2)=9\mathrm{/}8$. The values decrease from $Q_y(0,0)=5\mathrm{/}2$ to $11\mathrm{/}8$ to $9\mathrm{/}8$, as the exact updates require.

With $X_j=0$, changing ${\theta }_j$ leaves $y-X\theta$ unchanged and leaves all other penalty terms unchanged. The only varying part of the objective is $2\tau \mathrm{\mid }{\theta }_j\mathrm{\mid }$, which is nonnegative and vanishes only at zero because $\tau >0$.

Therefore every exact coordinate minimization has the unique update ${\theta }_j=0$, independent of the residual from the other columns. This agrees with the zero-column branch of [F3]; [F4] ensures the overall Lasso problem is not being treated as an empty minimization problem.

Expanding [F1] and using $X^{T}X=n{I}_d$ and $X^{T}Y\mathrm{/}n=Z$ gives $Q_Y(\theta )=\mathrm{\parallel }Y{\mathrm{\parallel }}_2^2\mathrm{/}n-2Z^T\theta +\mathrm{\parallel }\theta {\mathrm{\parallel }}_2^2+2\tau \mathrm{\parallel }\theta {\mathrm{\parallel }}_1$. Hence $Q_Y(\theta )=c(Y)+{\sum }_{j=1}^d((Z_j-{\theta }_j{)}^2+2\tau \mathrm{\mid }{\theta }_j\mathrm{\mid })$, where $c(Y)=\mathrm{\parallel }Y{\mathrm{\parallel }}_2^2\mathrm{/}n-\mathrm{\parallel }Z{\mathrm{\parallel }}_2^2$ is independent of $\theta$. The objective therefore separates into one-coordinate objectives plus a constant.

For a scalar $z$, on $\theta \ge 0$ completing the square gives $(z-\theta {)}^2+2\tau \theta =(\theta -(z-\tau ){)}^2+2\tau z-{\tau }^2$, whose constrained minimum is at $\max \{z-\tau ,0\}$. On $\theta \le 0$, $(z-\theta {)}^2-2\tau \theta =(\theta -(z+\tau ){)}^2-2\tau z-{\tau }^2$, whose constrained minimum is at $\min \{z+\tau ,0\}$. If $z>\tau$, the positive candidate has value $2\tau z-{\tau }^2$ and is below the negative-branch boundary value $z^2$ by $(z-\tau {)}^2$; if $z<-\tau$, the negative candidate is below the positive-branch boundary value by $(z+\tau {)}^2$; if $\mathrm{\mid }z\mathrm{\mid }\le \tau$, both constrained minima occur uniquely at $0$. Thus the unique scalar minimizer is $S_{\tau }(z)$.

By [F4] the minimizer set is nonempty. Since each coordinate term in step 1.1 has the unique minimizer from step 1.2, their vector of minimizers is the unique global minimizer, and its coordinates satisfy ${\widehat{\theta }}_j=S_{\tau }(Z_j)$ for every $j$. In the Gaussian specialization, $Y=X{Z}_0$ gives $Z=X^{T}X{Z}_0\mathrm{/}n=Z_0$, so the formula applies pointwise to every realization of [F2]. When $n=d$ and $X=\sqrt{n}{I}_d$, this response is $Y=\sqrt{n}{Z}_0$, recovering the square case.