Moreau decomposition

One important technique related to proximal gradient methods is the Moreau decomposition, which decomposes the identity operator as the sum of two proximity operators.^[1] Namely, let ${\displaystyle \varphi$ :{\mathcal {X}}\to \mathbb {R} } be a lower semicontinuous, convex function on a vector space ${\displaystyle {\mathcal {X}}}$. We define its Fenchel conjugate ${\displaystyle \varphi ^{*}:{\mathcal {X}}\to \mathbb {R} }$ to be the function

${\displaystyle \varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).}$

The general form of Moreau's decomposition states that for any ${\displaystyle x\in {\mathcal {X}}}$ and any ${\displaystyle \gamma >0}$ that

${\displaystyle x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),}$

which for ${\displaystyle \gamma =1}$ implies that ${\displaystyle x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)}$.^[1][3] The Moreau decomposition can be seen to be a generalization of the usual orthogonal decomposition of a vector space, analogous with the fact that proximity operators are generalizations of projections.^[1]

In certain situations it may be easier to compute the proximity operator for the conjugate ${\displaystyle \varphi ^{*}}$ instead of the function ${\displaystyle \varphi }$, and therefore the Moreau decomposition can be applied. This is the case for group lasso.

Solving for L₁ proximity operator

For simplicity we restrict our attention to the problem where ${\displaystyle \lambda =1}$. To solve the problem

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\|w\|_{1},}$

we consider our objective function in two parts: a convex, differentiable term ${\displaystyle F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}}$ and a convex function ${\displaystyle R(w)=\|w\|_{1}}$. Note that ${\displaystyle R}$ is not strictly convex.

Let us compute the proximity operator for ${\displaystyle R(w)}$. First we find an alternative characterization of the proximity operator ${\displaystyle \operatorname {prox} _{R}(x)}$ as follows:

${\displaystyle {\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}}$

For ${\displaystyle R(w)=\|w\|_{1}}$ it is easy to compute ${\displaystyle \partial R(w)}$: the ${\displaystyle i}$th entry of ${\displaystyle \partial R(w)}$ is precisely

${\displaystyle \partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}}$

Using the recharacterization of the proximity operator given above, for the choice of ${\displaystyle R(w)=\|w\|_{1}}$ and ${\displaystyle \gamma >0}$ we have that ${\displaystyle \operatorname {prox} _{\gamma R}(x)}$ is defined entrywise by

${\displaystyle \left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}}$

which is known as the soft thresholding operator ${\displaystyle S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)}$.^[1][6]

Fixed point iterative schemes

To finally solve the lasso problem we consider the fixed point equation shown earlier:

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).}$

Given that we have computed the form of the proximity operator explicitly, then we can define a standard fixed point iteration procedure. Namely, fix some initial ${\displaystyle w^{0}\in \mathbb {R} ^{d}}$, and for ${\displaystyle k=1,2,\ldots }$ define

${\displaystyle w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).}$

Note here the effective trade-off between the empirical error term ${\displaystyle F(w)}$ and the regularization penalty ${\displaystyle R(w)}$. This fixed point method has decoupled the effect of the two different convex functions which comprise the objective function into a gradient descent step (${\displaystyle w^{k}-\gamma \nabla F\left(w^{k}\right)}$) and a soft thresholding step (via ${\displaystyle S_{\gamma }}$).

Convergence of this fixed point scheme is well-studied in the literature^[1][6] and is guaranteed under appropriate choice of step size ${\displaystyle \gamma }$ and loss function (such as the square loss taken here). Accelerated methods were introduced by Nesterov in 1983 which improve the rate of convergence under certain regularity assumptions on ${\displaystyle F}$.^[7] Such methods have been studied extensively in previous years.^[8] For more general learning problems where the proximity operator cannot be computed explicitly for some regularization term ${\displaystyle R}$, such fixed point schemes can still be carried out using approximations to both the gradient and the proximity operator.^[4][9]

Adaptive step size

In the fixed point iteration scheme

${\displaystyle w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),}$

one can allow variable step size ${\displaystyle \gamma _{k}}$ instead of a constant ${\displaystyle \gamma }$. Numerous adaptive step size schemes have been proposed throughout the literature.^{[1][4][11][12]} Applications of these schemes^[2][13] suggest that these can offer substantial improvement in number of iterations required for fixed point convergence.

Elastic net (mixed norm regularization)

Elastic net regularization offers an alternative to pure ${\displaystyle \ell _{1}}$ regularization. The problem of lasso (${\displaystyle \ell _{1}}$) regularization involves the penalty term ${\displaystyle R(w)=\|w\|_{1}}$, which is not strictly convex. Hence, solutions to ${\displaystyle \min _{w}F(w)+R(w),}$ where ${\displaystyle F}$ is some empirical loss function, need not be unique. This is often avoided by the inclusion of an additional strictly convex term, such as an ${\displaystyle \ell _{2}}$ norm regularization penalty. For example, one can consider the problem

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right),}$

where ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ For ${\displaystyle 0<\mu \leq 1}$ the penalty term ${\displaystyle \lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)}$ is now strictly convex, and hence the minimization problem now admits a unique solution. It has been observed that for sufficiently small ${\displaystyle \mu >0}$, the additional penalty term ${\displaystyle \mu \|w\|_{2}^{2}}$ acts as a preconditioner and can substantially improve convergence while not adversely affecting the sparsity of solutions.^[2][14]

Group lasso

Group lasso is a generalization of the lasso method when features are grouped into disjoint blocks.^[15] Suppose the features are grouped into blocks ${\displaystyle \{w_{1},\ldots ,w_{G}\}}$. Here we take as a regularization penalty

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$

which is the sum of the ${\displaystyle \ell _{2}}$ norm on corresponding feature vectors for the different groups. A similar proximity operator analysis as above can be used to compute the proximity operator for this penalty. Where the lasso penalty has a proximity operator which is soft thresholding on each individual component, the proximity operator for the group lasso is soft thresholding on each group. For the group ${\displaystyle w_{g}}$ we have that proximity operator of ${\displaystyle \lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)}$ is given by

${\displaystyle {\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}}$

where ${\displaystyle w_{g}}$ is the ${\displaystyle g}$th group.

In contrast to lasso, the derivation of the proximity operator for group lasso relies on the Moreau decomposition. Here the proximity operator of the conjugate of the group lasso penalty becomes a projection onto the ball of a dual norm.^[2]

Other group structures

In contrast to the group lasso problem, where features are grouped into disjoint blocks, it may be the case that grouped features are overlapping or have a nested structure. Such generalizations of group lasso have been considered in a variety of contexts.^{[16][17][18][19]} For overlapping groups one common approach is known as latent group lasso which introduces latent variables to account for overlap.^[20][21] Nested group structures are studied in hierarchical structure prediction and with directed acyclic graphs.^[18]