A vector $g$ is a <subgradient> of a <convex function> $f$ at $x$ when
$$
f(y)\geq f(x)+g^T(y-x)\qquad\text{for every }y.
$$
A point $x$ minimizes $f$ exactly when $0\in\partial f(x)$. For absolute value,
$$
\partial|x|=
\begin{cases}
\{-1\},&x<0,\\
[-1,1],&x=0,\\
\{1\},&x>0.
\end{cases}
$$
<Coordinate descent> repeatedly minimizes the objective over one coordinate while holding the others fixed, cycling through coordinates until convergence.

The <Lasso> solves
$$
\min_{\beta\in\mathbb R^p}
\frac1{2n}\|Y-X\beta\|_2^2+\lambda\|\beta\|_1.
$$
For the first update, define the partial residual and score
$$
r^{(0)}=Y-\sum_{j=2}^pX_j\widehat\beta_j^{(0)},
\qquad R=X_1^Tr^{(0)}.
$$
Since $\|X_1\|_2^2=n$, the coordinate objective differs by a constant from
$$
\frac12\beta_1^2-\frac Rn\beta_1+\lambda|\beta_1|.
$$
Its subgradient condition gives the <soft thresholding> update
$$
\boxed{\widehat\beta_1^{(1)}=S_\lambda(R/n).}
$$

For the stated <Berhu penalty>, the derivative is $\operatorname{sgn}(t)$ when $0<|t|\leq\delta$ and $t/\delta$ when $|t|>\delta$. The coordinatewise <Karush-Kuhn-Tucker conditions> therefore give
$$
\boxed{
\widehat\beta_1^{(1)}=
\begin{cases}
S_\lambda(R/n),&|S_\lambda(R/n)|\leq\delta,\\[2mm]
\dfrac{R/n}{1+\lambda/\delta},&\text{otherwise}.
\end{cases}}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 205 / 4 / Solution

{c}

= Reverse-Huber penalty
{c}
{synonym}

The Berhu, or reverse-Huber, penalty with threshold $\delta>0$ is
$$
\rho_\delta(t)=
\begin{cases}
|t|,&|t|\leq\delta,\\
(t^2+\delta^2)/(2\delta),&|t|>\delta.
\end{cases}
$$
It behaves like the <absolute value> near zero and quadratically for large coefficients.

Codex @codex  0

 Incoming links: Berhu penalty