# An ADMM Algorithm for a Generic $\ell_{0}$ Sparse Overlapping Group Lasso
Problem

Youming Zhao
Email<EMAIL_ADDRESS>
(First draft: March 31, 2022 Last update: August 28, 2024)

###### Abstract

We present an alternating direction method of multipliers (ADMM) for a generic
overlapping group lasso problem, where the groups can be overlapping in an
arbitrary way. Meanwhile, we prove the lower bounds and upper bounds for both
the $\ell_{1}$ sparse group lasso problem and the $\ell_{0}$ sparse group
lasso problem. Also, we propose the algorithms for computing these bounds.

##  1 Generic $\ell_{0}$ sparse overlapping group lasso

The generic $\ell_{0}$ sparse overlapping group lasso problem is defined as

$\min_{x\in\mathbf{R}^{n}}\left\\{F(x):=\frac{1}{2s}\left\|x-v\right\|^{2}+\lambda_{0}\|x\|_{0}+\lambda_{1}\sum_{i=1}^{m}\|x_{G_{i}}\|_{2}\right\\}$
(1)

where $m$ denotes the number of groups, and $G_{i}\subseteq\\{1,2,\ldots,n\\}$
contains the feature indices of the $i$-th group. Here $s$ is the step size
employed to get $v$ based on $x$. Note that
$\bigcap_{i=\\{1,\ldots,m\\}}G_{i}\neq\emptyset$. Now consider the problem,

$\begin{array}[]{ll}\operatorname{minimize}_{x_{G_{i}}\in\mathbf{R}^{n_{i}},z\in\mathbf{R}^{n}}&\frac{1}{2s}\left\|z-v\right\|^{2}+\lambda_{0}\|z\|_{0}+\lambda_{1}\sum_{i=1}^{m}\|x_{G_{i}}\|_{2}\\\
\mathop{\mathrm{subject\,\,to}}&x_{G_{i}}-z_{i}=0,\quad
i=1,2,\ldots,m\end{array}$ (2)

where $z_{i}\in\mathbf{R}^{n_{i}}$ is defined by
$(z_{i})_{j}=z_{G(i,j)}=z_{g}$. Here, $G(i,j)=g$ denotes the global index
(location) of the $j$-th element in the set (group) $G_{i}$. Hence, $z$ is a
linear function of $z_{i},i\in\\{1,\ldots,m\\}$.

The augmented Lagrangian for (2) is

$L_{\rho}(x_{G_{i}},z,y_{G_{i}})=\sum_{i=1}^{m}\left[\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}(x_{G_{i}}-z_{i})+\frac{\rho}{2}\|x_{G_{i}}-z_{i}\|_{2}^{2}\right]+\frac{1}{2s}\left\|z-v\right\|^{2}+\lambda_{0}\|z\|_{0}.$
(3)

$\displaystyle
x_{G_{i}}^{k+1}:=\mathop{\mathrm{argmin}}_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+x_{G_{i}}^{T}y^{k}_{G_{i}}+\frac{\rho}{2}\|x_{G_{i}}-z_{i}^{k+1}\|_{2}^{2}\right),\quad
i=1,2,\ldots,m$ (4) $\displaystyle
z^{k+1}:=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2s}\left\|z-v\right\|_{2}^{2}+\lambda_{0}\|z\|_{0}+\sum_{i=1}^{m}\left(\frac{\rho}{2}\|x_{G_{i}}^{k+1}-z_{i}\|_{2}^{2}-z_{i}^{T}y^{k}_{G_{i}}\right)\right)$
(5) $\displaystyle
y^{k+1}_{G_{i}}:=y^{k}_{G_{i}}+\rho(x_{G_{i}}^{k+1}-z_{i}^{k+1})$ (6)

where $x_{G_{i}}$ and $z$ are primal variables, and $y_{G_{i}}$ are dual
variables. The $x$-update is actually a group lasso problem and can be solved
with the proximal operator of group lasso as follows.

$\displaystyle x_{G_{i}}^{k+1}$
$\displaystyle=\mathop{\mathrm{argmin}}_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+x_{G_{i}}^{T}y^{k}_{G_{i}}+\frac{\rho}{2}\|x_{G_{i}}-z_{i}^{k+1}\|_{2}^{2}\right)$
$\displaystyle=\mathop{\mathrm{argmin}}_{x_{G_{i}}}\left(\frac{1}{2}\|x_{G_{i}}-z_{i}^{k+1}\|_{2}^{2}+x_{G_{i}}^{T}\frac{y^{k}_{G_{i}}}{\rho}+\frac{\lambda_{1}}{\rho}\|x_{G_{i}}\|_{2}\right)$
$\displaystyle=\mathop{\mathrm{argmin}}_{x_{G_{i}}}\left(\frac{1}{2}\|x_{G_{i}}-(z_{i}^{k+1}-\frac{y^{k}_{G_{i}}}{\rho})\|_{2}^{2}+\frac{\lambda_{1}}{\rho}\|x_{G_{i}}\|_{2}\right)$
$\displaystyle=S_{\lambda_{1}/\rho}(z_{i}^{k+1}-\frac{y^{k}_{G_{i}}}{\rho}),\quad
i=1,2,\ldots,m$

where $S_{\lambda}(\cdot)$ is a soft-thresholding operator defined as

$S_{\lambda}(a)=(\|a\|_{2}-\lambda)_{+}\frac{a}{\|a\|_{2}}.$

Now we derive the solution to the $z$-update.

$z^{k+1}=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2s}\left\|z-v\right\|_{2}^{2}+\lambda_{0}\|z\|_{0}+\sum_{i=1}^{m}\left(\frac{\rho}{2}\|x_{G_{i}}^{k+1}-z_{i}\|_{2}^{2}-z_{i}^{T}y^{k}_{G_{i}}\right)\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left(\frac{1}{2s}(z_{g}-v_{g})^{2}+\lambda_{0}\|z_{g}\|_{0}+\sum_{G(i,j)=g}\left(\frac{\rho}{2}(z_{i})_{j}^{2}-(y_{i}^{k})_{j}(z_{i})_{j}-\rho(x_{i}^{k+1})_{j}(z_{i})_{j}\right)\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left(\frac{1}{2s}(z_{g}-v_{g})^{2}+\lambda_{0}\|z_{g}\|_{0}+\frac{k_{g}\rho}{2}z_{g}^{2}-z_{g}\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left(\frac{1}{2s}z_{g}^{2}-\frac{1}{s}v_{g}z_{g}+\frac{k_{g}\rho}{2}z_{g}^{2}-z_{g}\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)+\lambda_{0}\|z_{g}\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left((\frac{1}{2s}+\frac{k_{g}\rho}{2})z_{g}^{2}-\frac{v_{g}}{s}z_{g}-z_{g}\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)+\lambda_{0}\|z_{g}\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left((\frac{1}{2s}+\frac{k_{g}\rho}{2})z_{g}^{2}-z_{g}\left(\frac{v_{g}}{s}+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)\right)+\lambda_{0}\|z_{g}\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\sum_{g=1}^{n}\left(\frac{1}{2}z_{g}^{2}-z_{g}\frac{v_{g}/s+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)}{1/s+k_{g}\rho}+\frac{\lambda_{0}}{1/s+k_{g}\rho}\|z_{g}\|_{0}\right)$

equivalently,

$z_{g}^{k+1}=\mathop{\mathrm{argmin}}_{z_{g}}\left(\frac{1}{2}z_{g}^{2}-z_{g}\frac{v_{g}/s+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)}{1/s+k_{g}\rho}+\frac{\lambda_{0}}{1/s+k_{g}\rho}\|z_{g}\|_{0}\right)=\mathop{\mathrm{argmin}}_{z_{g}}\left(\frac{1}{2}\left(z_{g}-\frac{v_{g}/s+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)}{1/s+k_{g}\rho}\right)^{2}+\frac{\lambda_{0}}{1/s+k_{g}\rho}\|z_{g}\|_{0}\right)=H_{\sqrt{2\lambda_{0}/(1/s+k_{g}\rho)}}\left(\frac{v_{g}/s+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)}{1/s+k_{g}\rho}\right),\quad\forall
g\in\\{1,2,\ldots,n\\}$

where $H_{\lambda}(\cdot)$ is a hard-thresholding operator defined as follows.

$H_{\lambda}(u)=\begin{cases}u,&\mbox{if }|u|>\lambda\\\
0,&\mbox{otherwise}.\end{cases}$

Note that when $u$ is a vector, $H_{\lambda}(\cdot)$ is an element-wise hard-
thresholding operator.

Thus, we obtain the final update formulas for $x,z$ and $y$ as follows.

$\displaystyle
x_{G_{i}}^{k+1}=S_{\lambda_{1}/\rho}(z_{i}^{k+1}-\frac{y^{k}_{G_{i}}}{\rho}),\quad\forall
i\in\\{1,2,\ldots,m\\}$ $\displaystyle
z_{g}^{k+1}=H_{\sqrt{2\lambda_{0}/(1/s+k_{g}\rho)}}\left(\frac{v_{g}/s+\sum_{G(i,j)=g}\left((y_{i}^{k})_{j}+\rho(x_{i}^{k+1})_{j}\right)}{1/s+k_{g}\rho}\right),\quad\forall
g\in\\{1,2,\ldots,n\\}$ $\displaystyle
y^{k+1}_{G_{i}}=y^{k}_{G_{i}}+\rho(x_{G_{i}}^{k+1}-z_{i}^{k+1}),\quad\forall
i\in\\{1,2,\ldots,m\\}$

###  1.1 The matrix form of the $\ell_{0}$ sparse overlapping group lasso

Define
$\tilde{x}=[x^{T}_{G_{1}},x^{T}_{G_{2}},\ldots,x^{T}_{G_{m}}]^{T}\in\mathbf{R}^{\tilde{n}}$
and
$\tilde{z}=[z^{T}_{G_{1}},z^{T}_{G_{2}},\ldots,z^{T}_{G_{m}}]^{T}\in\mathbf{R}^{\tilde{n}}$
where $\tilde{n}=\sum_{i=1}^{m}n_{i}$. Then $\tilde{z}$ can be represented as

$\tilde{z}=Gz$

where each row of $G$ has only one entry being $1$ and other entries being
$0$. The corresponding definition of $z$-update becomes

$z^{k+1}=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2s}\left\|z-v\right\|_{2}^{2}+\lambda_{0}\|z\|_{0}+\frac{\rho}{2}\|\tilde{x}^{k}-Gz\|_{2}^{2}-(\tilde{y}^{k})^{T}Gz\right)=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2}\left(\frac{z^{T}z}{s}+\rho
z^{T}G^{T}Gz\right)-\left(\frac{v^{T}z}{s}+(\rho\tilde{x}^{k})^{T}Gz+(\tilde{y}^{k})^{T}Gz\right)+\lambda_{0}\|z\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2}z^{T}\left(\frac{I}{s}+\rho
G^{T}G\right)z-\left(\frac{v^{T}z}{s}+(\rho\tilde{x}^{k})^{T}Gz+(\tilde{y}^{k})^{T}Gz\right)+\lambda_{0}\|z\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2}z^{T}\left(\frac{I}{s}+\rho
G^{T}G\right)z-\left(\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right)^{T}z+\lambda_{0}\|z\|_{0}\right)$

where
$\tilde{y}=[y^{T}_{G_{1}},y^{T}_{G_{2}},\ldots,y^{T}_{G_{m}}]^{T}\in\mathbf{R}^{\tilde{n}}$.
We observe that $G^{T}G$ is a diagonal matrix of which the $g$-th diagonal
entry corresponds to the number of groups that the global variable $z_{g}$
involves. Since $G^{T}G$ is positive semidefinite and $s,\rho>0$, $I/s+\rho
G^{T}G$ is definitely a positive definite matrix. Let $I/s+\rho
G^{T}G=\operatorname{diag}(c_{1},\ldots,c_{n})$ and
$C=\operatorname{diag}(\sqrt{c_{1}},\ldots,\sqrt{c_{n}})$ where
$c_{g}=1/s+k_{g}\rho$. Thus, $C^{T}C=I/s+\rho G^{T}G$. With this setting, we
have

$z^{k+1}=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2}z^{T}C^{T}Cz-\left(\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right)^{T}C^{-1}Cz+\lambda_{0}\|z\|_{0}\right)=\mathop{\mathrm{argmin}}_{z}\left(\frac{1}{2}\|Cz-C^{-1}\left(\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right)\|_{2}^{2}+\lambda_{0}\|z\|_{0}\right).$

Since $C$ is diagonal, the $z$-update reduces to $n$ subproblems as follows.

$z_{g}^{k+1}=\mathop{\mathrm{argmin}}_{z_{g}}\left(\frac{1}{2}\left(\sqrt{c_{g}}z_{g}-\frac{1}{\sqrt{c_{g}}}\cdot\left[\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right]_{g}\right)^{2}+\lambda_{0}\|z_{g}\|_{0}\right)=\mathop{\mathrm{argmin}}_{z_{g}}\left(\frac{1}{2}\left(z_{g}-\frac{1}{c_{g}}\cdot\left[\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right]_{g}\right)^{2}+\frac{\lambda_{0}}{c_{g}}\|z_{g}\|_{0}\right)=H_{\sqrt{2\lambda_{0}/c_{g}}}\left(\frac{1}{c_{g}}\cdot\left[\frac{v}{s}+G^{T}(\rho\tilde{x}^{k}+\tilde{y}^{k})\right]_{g}\right)$

which is exactly the same as the previous counterpart result.

###  1.2 Solving the dual problem via ADMM

The dual of (2) is,

$\displaystyle\min_{x_{G_{i}},z}\frac{1}{2s}\left\|z-v\right\|^{2}+\lambda_{0}\|z\|_{0}+\lambda_{1}\sum_{i=1}^{m}\|x_{G_{i}}\|_{2}+\sum_{i=1}^{m}y_{G_{i}}^{T}(x_{G_{i}}-z_{i})$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}\left\|z-v\right\|^{2}+\lambda_{0}\|z\|_{0}-\sum_{i=1}^{m}y_{G_{i}}^{T}z_{i}\right)+\min_{x_{G_{i}}}\left(\sum_{i=1}^{m}(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}})\right)$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}(z^{T}z-2v^{T}z+v^{T}v)-\tilde{y}^{T}\tilde{z}+\lambda_{0}\|z\|_{0}\right)+\sum_{i=1}^{m}\min_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}}\right)$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}(z^{T}z-2v^{T}z-2s\tilde{y}^{T}Gz+v^{T}v)+\lambda_{0}\|z\|_{0}\right)+\sum_{i=1}^{m}\min_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}}\right)$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}(z^{T}z-2(v+sG^{T}\tilde{y})^{T}z+v^{T}v)+\lambda_{0}\|z\|_{0}\right)+\sum_{i=1}^{m}\min_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}}\right)$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}\left(\|z-(v+sG^{T}\tilde{y})\|^{2}+v^{T}v-(v+sG^{T}\tilde{y})^{T}(v+sG^{T}\tilde{y})\right)+\lambda_{0}\|z\|_{0}\right)+\sum_{i=1}^{m}\min_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}}\right)$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}\|z-(v+sG^{T}\tilde{y})\|^{2}+\lambda_{0}\|z\|_{0}\right)+\sum_{i=1}^{m}\min_{x_{G_{i}}}\left(\lambda_{1}\|x_{G_{i}}\|_{2}+y_{G_{i}}^{T}x_{G_{i}}\right)+\frac{1}{2s}(\|v\|^{2}-\|v+sG^{T}\tilde{y}\|^{2})$
$\displaystyle=$
$\displaystyle\min_{z}\left(\frac{1}{2s}\|z-(v+sG^{T}\tilde{y})\|^{2}+\lambda_{0}\|z\|_{0}\right)-\frac{1}{2s}\|v+sG^{T}\tilde{y}\|^{2}+\frac{1}{2s}\|v\|^{2},\quad\|y_{G_{i}}\|_{2}\leq\lambda_{1},i=1,\ldots,m$

After dropping the constant term, the dual problem of (2) becomes

$\displaystyle\max_{\tilde{y}\in\Omega}\min_{z\in\mathbf{R}^{n}}\left\\{\psi(z,\tilde{y})=\frac{1}{2s}\|z-(v+sG^{T}\tilde{y})\|^{2}+\lambda_{0}\|z\|_{0}-\frac{1}{2s}\|v+sG^{T}\tilde{y}\|^{2}\right\\}.$
(7)

where $\Omega$ is defined as follows:

$\Omega=\\{\tilde{y}\in\mathbf{R}^{\tilde{n}}\ |\
\|y_{G_{i}}\|_{2}\leq\lambda_{1},i=1,2,\ldots,m\\}.$

For a given $\tilde{y}^{k-1}$, the optimal $z$ minimizing
$\psi(z,\tilde{y}^{k-1})$ in (7) is given by

$z^{k}=H_{\sqrt{2s\lambda_{0}}}(v+sG^{T}\tilde{y}^{k-1}).$ (8)

Plugging (8) into (7), we get the following maximization problem with respect
to $\tilde{y}$:

$\max_{\tilde{y}\in\Omega}\ \\{\omega(\tilde{y})=-\psi(z^{k},\tilde{y})\\}$
(9)

which is equivalent to the following problem

$\max_{\tilde{y}\in\Omega}\ \tilde{y}^{T}G(z^{k}-2v)$ (10)

which can be solved analytically as follows.

$\tilde{y}_{G_{i}}=\frac{[G(z^{k}-2v)]_{i}}{\|[G(z^{k}-2v)]_{i}\|_{2}}$ (11)

where $[G(z^{k}-2v)]_{i}\in\mathbf{R}^{n_{i}}$ denotes the counterpart
corresponding to the group $G_{i}$. Finally, our methodology for minimizing
the problem defined in (2) is to alternate update $z$ and $\tilde{y}$.

###  1.3 The bounds on the optimal value of the overlapping group lasso

Before presenting the results regarding the bounds of the optimal value of the
$\ell_{0}$ sparse group lasso, we introduce three lemmas which lead to the
upcoming theorem. For completeness, we describe a well known result as the
following lemma, namely the quadratic mean (QM) is no less than the arithmetic
mean (AM).

######  Lemma 1.1 (QM$\geq$AM).

Given $\mathbf{x}\in\mathbf{R}^{n}$, the following

$\sqrt{\frac{\sum_{i=1}^{n}x_{i}^{2}}{n}}\geq\frac{\sum_{i=1}^{n}|x_{i}|}{n}$

holds. The equality holds if and only if $x_{1}=x_{2}=\ldots=x_{n}$.

###### Proof.

According to Cauchy-Schwartz inequality which says that given two vectors
$\mathbf{x},\mathbf{y}\in\mathbf{R}^{n}$,
$\|\mathbf{x}\|_{2}\|\mathbf{y}\|_{2}\geq|\mathbf{x}^{T}\mathbf{y}|$, we have

$\displaystyle\sqrt{\frac{\sum_{i=1}^{n}x_{i}^{2}}{n}}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}(\frac{|x_{i}|}{\sqrt{n}})^{2}}\cdot\overbrace{\sqrt{\sum_{i=1}^{n}(\frac{1}{\sqrt{n}})^{2}}}^{=1}$
$\displaystyle\geq\frac{\sum_{i=1}^{n}|x_{i}|}{n}\geq\frac{\sum_{i=1}^{n}x_{i}}{n},$

where the equalities in the first and second inequalities hold if and only if
$|x_{1}|=|x_{2}|=\cdots=|x_{n}|$ and $x_{1}=x_{2}=\cdots=x_{n}$, respectively.
This completes the proof. ∎

####  1.3.1 Lower bound on the overlapping group lasso

######  Lemma 1.2 (lower bound on the overlapping group lasso).

Given $\mathbf{x}\in\mathbf{R}^{n}$, $\mathbf{w}\in\mathbf{R}_{++}^{m}$ and
some groups $G_{i}\subseteq\\{1,2,\ldots,n\\},i=1,2,\ldots,m$, let
$I_{G_{i}}(j)$ denote an indicator function whose value is $1$ if $j\in G_{i}$
and $0$ otherwise. Then, the following

$\|\mathbf{L}\mathbf{x}\|_{1}\leq\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}$

holds, where $\mathbf{L}=\operatorname{\mathbf{diag}}(\mathbf{l})$ with
elements $l_{j}=\sum_{i=1}^{m}\frac{w_{i}}{\sqrt{|G_{i}|}}\odot\mathbb{I}(j\in
G_{i}),j=1,\ldots,n$ and $\mathbb{I}(e)=1$ if $e$ is true, $0$ otherwise. The
equality holds if and only if for every $G_{i}$, the entries of
$\mathbf{x}_{G_{i}}$ are identical.

###### Proof.

$\displaystyle\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}$
$\displaystyle=w_{1}\|\mathbf{x}_{G_{1}}\|_{2}+\cdots+w_{m}\|\mathbf{x}_{G_{m}}\|_{2}$
$\displaystyle=\sum_{i=1}^{m}w_{i}\sqrt{\sum_{j=1}^{|G_{i}|}|x_{j}|^{2}}=\sum_{i=1}^{m}w_{i}\sqrt{|G_{i}|}\cdot\sqrt{\frac{\sum_{j=1}^{|G_{i}|}|x_{j}|^{2}}{|G_{i}|}}$
$\displaystyle\geq\sum_{i=1}^{m}w_{i}\sqrt{|G_{i}|}\cdot\frac{\sum_{j=1}^{|G_{i}|}|x_{j}|}{|G_{i}|}=\sum_{i=1}^{m}\frac{w_{i}}{\sqrt{|G_{i}|}}\cdot\sum_{j=1}^{|G_{i}|}|x_{j}|$
$\displaystyle=\sum_{j=1}^{n}\sum_{i=1}^{m}\left(\frac{w_{i}}{\sqrt{|G_{i}|}}\odot\mathbb{I}(j\in
G_{i})\right)|x_{j}|$

where $\mathbb{I}(e)$ is an indicator function defined as follows:

$\begin{cases}1,&\mbox{if $e$ is true}\\\ 0,&\mbox{otherwise}.\end{cases}$

The second line follows from the definition of $p$-norm ($p\geq 1$) and the
third line from Lemma 1.1. The equality holds if and only if the entries
belonging to the same group are identical for all the groups. Let
$\mathbf{L}=\operatorname{\mathbf{diag}}(\mathbf{l})$, the diagonal matrix
with elements
$l_{j}=\sum_{i=1}^{m}\frac{w_{i}}{\sqrt{|G_{i}|}}\odot\mathbb{I}(j\in
G_{i}),j=1,\ldots,n$, so we have

$\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}\geq\|\mathbf{L}\mathbf{x}\|_{1}$
(12)

∎

####  1.3.2 Computing the lower bound on the overlapping group lasso

Since we have found the lower bound on the overlapping group lasso operator,
the overlapping group lasso problem reduces to solving a weighted lasso
problem as follows.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\text{GL\\_lb}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Lx}\|_{1}\right\\}$
(13)

Since $f_{\text{GL\\_lb}}(\mathbf{x})$ is separable w.r.t $\mathbf{x}$, this
is equivalent to solving the following subproblem for each $i$.

$\min_{x_{i}\in\mathbf{R}}\left\\{f_{\text{GL\\_lb}}(x_{i}):=\frac{1}{2}(x_{i}-v_{i})^{2}+\lambda
l_{i}|x_{i}|\right\\}$

If $x_{i}>0$, then
$f_{\text{GL\\_lb}}(x_{i})=\frac{1}{2}(x_{i}-v_{i})^{2}+\lambda l_{i}x_{i}$.
By the first-order optimality condition,

$\nabla f_{\text{GL\\_lb}}(x_{i})=x_{i}-v_{i}+\lambda
l_{i}=0\Longleftrightarrow x_{i}=v_{i}-\lambda l_{i}>0\Longleftrightarrow
v_{i}>\lambda l_{i}.$

For $x_{i}<0$, we have the following similar argument.

$\nabla f_{\text{GL\\_lb}}(x_{i})=x_{i}-v_{i}-\lambda
l_{i}=0\Longleftrightarrow x_{i}=v_{i}+\lambda l_{i}<0\Longleftrightarrow
v_{i}<-\lambda l_{i}.$

In the case of $x_{i}=0$, let $\nu$ be the subdifferential of $|x_{i}|$ at
$x_{i}=0$, then $\nu\in[-1,1]$. Thus,

$0\in\partial f_{\text{GL\\_lb}}(0)=0-v_{i}+\lambda
l_{i}\nu\Longleftrightarrow\frac{v_{i}}{\lambda
l_{i}}\in\nu\Longleftrightarrow|v_{i}|\leq\lambda l_{i}$

where the RHS follows from the fact that $|\nu|\leq 1$. To sum up, the
solution to the subproblem is

$x_{i}=\begin{cases}v_{i}-\lambda l_{i},&\mbox{if }v_{i}>\lambda l_{i}\\\
0,&\mbox{if }|v_{i}|\leq\lambda l_{i}\\\ v_{i}+\lambda l_{i},&\mbox{if
}v_{i}<-\lambda l_{i}.\end{cases}\quad i=1,2,\ldots,n.$ (14)

####  1.3.3 Upper bound on the overlapping group lasso

######  Lemma 1.3 (upper bound on the overlapping group lasso).

Given $\mathbf{x}\in\mathbf{R}^{n}$, $\mathbf{w}\in\mathbf{R}_{++}^{m}$ and
some groups $G_{i}\subseteq\\{1,2,\ldots,n\\},i=1,\ldots,m$, denote the total
number of appearances in all groups by $k_{j},j=1,\ldots,n$, and let
$\mathbf{U}=\operatorname{\mathbf{diag}}(\sqrt{k_{1}}\|\mathbf{w}\|_{2},\ldots,\sqrt{k_{n}}\|\mathbf{w}\|_{2})$.
Then, the following

$\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}\leq\|\mathbf{U}\mathbf{x}\|_{2}$

holds. The equality holds if and only if
$\frac{\|\mathbf{x}_{G_{1}}\|_{2}}{w_{1}}=\ldots=\frac{\|\mathbf{x}_{G_{m}}\|_{2}}{w_{m}}$.

###### Proof.

$\displaystyle\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}$
$\displaystyle=w_{1}\|\mathbf{x}_{G_{1}}\|_{2}+\cdots+w_{m}\|\mathbf{x}_{G_{m}}\|_{2}$
$\displaystyle\leq\sqrt{w_{1}^{2}+\cdots+w_{m}^{2}}\cdot\sqrt{\|\mathbf{x}_{G_{1}}\|_{2}^{2}+\cdots+\|\mathbf{x}_{G_{m}}\|_{2}^{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{m}w_{i}^{2}}\cdot\sqrt{\sum_{g=1}^{n}k_{g}x_{g}^{2}}=\sqrt{\sum_{g=1}^{n}(\sum_{i=1}^{m}w_{i}^{2})k_{g}x_{g}^{2}}$

where the second line follows from Cauchy-Schwarz inequality and the equality
holds if and only if
$\frac{\|\mathbf{x}_{G_{1}}\|_{2}}{w_{1}}=\ldots=\frac{\|\mathbf{x}_{G_{m}}\|_{2}}{w_{m}}$.
Let
$\mathbf{U}_{0}=\operatorname{\mathbf{diag}}(\sqrt{k_{1}},\ldots,\sqrt{k_{n}})$
and $\mathbf{w}=(w_{1},\ldots,w_{m})$, then we have

$\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}\leq\|\mathbf{w}\|_{2}\cdot\sqrt{\mathbf{x}^{T}\operatorname{\mathbf{diag}}(k_{1},\ldots,k_{n})\mathbf{x}}=\|\mathbf{w}\|_{2}\cdot\|\mathbf{U}_{0}\mathbf{x}\|_{2}$
(15)

By the positive homogeneity of $\|\cdot\|_{2}$, $\|\mathbf{w}\|_{2}$ can be
absorbed into $\mathbf{U}_{0}$ as follows.

$\sum_{i=1}^{m}w_{i}\|\mathbf{x}_{G_{i}}\|_{2}\leq\|\mathbf{U}\mathbf{x}\|_{2}$
(16)

where $\mathbf{U}=\operatorname{\mathbf{diag}}(\mathbf{u})$ and
$\mathbf{u}=(\sqrt{k_{1}}\|\mathbf{w}\|_{2},\ldots,\sqrt{k_{n}}\|\mathbf{w}\|_{2})$.
∎

####  1.3.4 Computing the upper bound on the overlapping group lasso

After replacing the overlapping group lasso operator with
$\|\mathbf{U}\mathbf{x}\|_{2}$, the upper bound on the overlapping group lasso
is equal to the optimal value of the following problem.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\text{GL\\_ub}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Ux}\|_{2}\right\\}$
(17)

Let $\mathbf{s}$ be an element of the subdifferential of $\|\cdot\|_{2}$ at
$\mathbf{0}$. Then if $\mathbf{x}=\mathbf{0}$, solving the following zero
subgradient equation gives

$\mathbf{0}-\mathbf{v}+\lambda\mathbf{U}^{T}\mathbf{s}=\mathbf{0}\Longleftrightarrow\mathbf{v}=\lambda\mathbf{U}^{T}\mathbf{s}\Longleftrightarrow\mathbf{U}^{-1}\mathbf{v}=\lambda\mathbf{s}\Longleftrightarrow\|\mathbf{U}^{-1}\mathbf{v}\|_{2}\leq\lambda$

Thus, we obtain that if $\|\mathbf{U}^{-1}\mathbf{v}\|_{2}\leq\lambda$, the
optimal minimizer is $\mathbf{0}$.

When $\mathbf{x}\neq\mathbf{0}$, we have

$\nabla
f_{\text{GL\\_ub}}(\mathbf{x})=\mathbf{x}-\mathbf{v}+\frac{\lambda\mathbf{U}^{T}\mathbf{Ux}}{\|\mathbf{Ux}\|_{2}}=0\Longleftrightarrow\left(\mathbf{I}+\frac{\lambda\mathbf{U}^{T}\mathbf{U}}{\|\mathbf{Ux}\|_{2}}\right)\mathbf{x}=\mathbf{v}\Longleftrightarrow\mathbf{x}=\left(\mathbf{I}+\frac{\lambda\mathbf{U}^{T}\mathbf{U}}{\|\mathbf{Ux}\|_{2}}\right)^{-1}\mathbf{v}.$

Thus, we reformulate the optimality condition as $\mathbf{x}=T(\mathbf{x})$
for the case of $\mathbf{x}\neq\mathbf{0}$, where $T$ is the operator

$T(\mathbf{x}):=\left(\mathbf{I}+\frac{\lambda\mathbf{U}^{T}\mathbf{U}}{\|\mathbf{Ux}\|_{2}}\right)^{-1}\mathbf{v}.$
(18)

Then we have the following result concerning $T(\mathbf{x})$.

######  Theorem 1.4.

$T(\mathbf{x})$ has a unique fixed point $\mathbf{x}^{*}$. In other words, the
corresponding fixed point iteration

$\mathbf{x}^{(k+1)}:=T(\mathbf{x}^{(k)})$

converges to a unique $\mathbf{x}^{*}$.

###### Proof.

Since $\mathbf{U}$ is a diagonal matrix,
$\mathbf{U}^{T}\mathbf{U}=\mathbf{U}^{2}$. Let
$\mathbf{G}=\mathbf{I}+\frac{\lambda\mathbf{U}^{T}\mathbf{U}}{\|\mathbf{Ux}\|_{2}}$,
then $\mathbf{G}$ is a diagonal matrix with elements $G_{ii}=1+\frac{\lambda
u_{i}^{2}}{\|\mathbf{Ux}\|_{2}},i=1,2,\ldots,n$. Thus, $\mathbf{G}^{-1}$ is
also a diagonal matrix with elements

$0<\rho_{i}=\frac{\|\mathbf{Ux}\|_{2}}{\|\mathbf{Ux}\|_{2}+\lambda
u_{i}^{2}}=1-\frac{\lambda u_{i}^{2}}{\|\mathbf{Ux}\|_{2}+\lambda
u_{i}^{2}}<1.$ (19)

Then we have $x_{i}=\rho_{i}v_{i}$ for each $i$. Let $\boldsymbol{\rho}$ be a
vector whose $i$-th entry is $\rho_{i}$ with $\rho_{i}\in(0,1)$. So,
$\mathbf{x}=\boldsymbol{\rho}\odot\mathbf{v}$ where $\odot$ is the element-
wise Hadamard product, which indicates $\mathbf{x}$ is a contracted version of
$\mathbf{v}$. Let $\rho_{i}(y)=1-\frac{\lambda u_{i}^{2}}{y+\lambda
u_{i}^{2}}$ with $y=\|\mathbf{Ux}\|_{2}>0$. Then

$\rho_{i}^{\prime}(y)=\frac{\lambda u_{i}^{2}}{(y+\lambda u_{i}^{2})^{2}}>0.$

which shows $\rho_{i}$ is a strictly increasing function of $y$, i.e.,
$\|\mathbf{Ux}\|_{2}$. By (19), a smaller (bigger) $\|\mathbf{Ux}\|_{2}$ gives
a smaller (bigger) $\rho_{i}$ for each $i$ which in turn generates smaller
(bigger) $x_{i}$ via $x_{i}=\rho_{i}v_{i}$ for each $i$, and then small
(greater) $\|\mathbf{Ux}\|_{2}$. Thanks to this interplay between
$\|\mathbf{Ux}\|_{2}$ and $\boldsymbol{\rho}$, the sequences regarding
$\|\mathbf{Ux}\|_{2}$ and $\boldsymbol{\rho}$ generated by performing
$T(\mathbf{x})$ are monotone. For example, let us start the iteration with
$\mathbf{x}^{(0)}\neq\mathbf{0}$. Then
$\mathbf{x}^{(1)}=\boldsymbol{\rho}^{(0)}\odot\mathbf{v}$. Suppose
$\|\mathbf{U}\mathbf{x}^{(0)}\|_{2}>\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}$, then

$\rho_{i}^{(0)}=1-\frac{\lambda
u_{i}^{2}}{\|\mathbf{U}\mathbf{x}^{(0)}\|_{2}+\lambda
u_{i}^{2}}>1-\frac{\lambda
u_{i}^{2}}{\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}+\lambda
u_{i}^{2}}=\rho_{i}^{(1)},\quad i=1,2,\ldots,n.$ (20)

Thus,

$x_{i}^{(2)}=\rho_{i}^{(1)}v_{i}<\rho_{i}^{(0)}v_{i}=x_{i}^{(1)},\quad
i=1,2,\ldots,n.$

Since $\mathbf{U}$ is a diagonal matrix with nonnegative diagonal entries
$u_{i}$, we have

$\|\mathbf{U}\mathbf{x}^{(2)}\|_{2}=\sqrt{\sum_{i=1}^{n}(u_{i}x_{i}^{(2)})^{2}}<\sqrt{\sum_{i=1}^{n}(u_{i}x_{i}^{(1)})^{2}}=\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}$

So,
$\|\mathbf{U}\mathbf{x}^{(0)}\|_{2}>\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}>\|\mathbf{U}\mathbf{x}^{(2)}\|_{2}$.
Substituting $\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}$ and
$\|\mathbf{U}\mathbf{x}^{(2)}\|_{2}$ into (20), we get
$\rho_{i}^{(1)}>\rho_{i}^{(2)}>\rho_{i}^{(3)}$. By repeating this, the
contraction interplay between $\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}$ and
$\rho_{i}{(k)}$ lead to that both $\\{\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}\\}$
and $\\{\rho_{i}^{(k)}\\}_{i=1,2,\ldots,n}$ are decreasing sequences. Also,
$\\{\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}\\}$ and $\\{\rho_{i}^{(k)}\\}$ are both
bounded below by $0$. Since monotone bounded sequences converge,
$\\{\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}\\}$ and $\\{\rho_{i}^{(k)}\\}$ are
convergent. Assuming $\lim_{k\to\infty}\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}=c$
and $\lim_{k\to\infty}\rho_{i}^{(k)}=\rho_{i}$ yield

$x_{i}=\frac{cv_{i}}{c+\lambda u_{i}^{2}},\quad i=1,2,\ldots,n.$

Multiplying both sides by $u_{i}$, squaring both sides and summing over $i$
gives

$c^{2}=\sum_{i=1}^{n}(u_{i}x_{i})^{2}=\sum_{i=1}^{n}\frac{(cu_{i}v_{i})^{2}}{(c+\lambda
u_{i}^{2})^{2}}\Longrightarrow
1=\sum_{i=1}^{n}\frac{(u_{i}v_{i})^{2}}{(c+\lambda u_{i}^{2})^{2}}$ (21)

The solution to the equation on the RHS of (21) is $c$ which is unique since
$c=\|\mathbf{U}\mathbf{x}^{*}\|_{2}>0$. We can show this by contradiction.
Specifically, suppose $c^{\prime}>c$ is the solution to (21). Since
$\lambda,u_{i}>0,i=1,2,\ldots,n$, then we get

$\frac{(u_{i}v_{i})^{2}}{(c^{\prime}+\lambda
u_{i}^{2})^{2}}<\frac{(u_{i}v_{i})^{2}}{(c+\lambda
u_{i}^{2})^{2}}\Longrightarrow\sum_{i=1}^{n}\frac{(u_{i}v_{i})^{2}}{(c^{\prime}+\lambda
u_{i}^{2})^{2}}<\sum_{i=1}^{n}\frac{(u_{i}v_{i})^{2}}{(c+\lambda
u_{i}^{2})^{2}}=1$

which contradicts the supposition $c^{\prime}>c$ is the solution to (21),
i.e., $\sum_{i=1}^{n}\frac{(u_{i}v_{i})^{2}}{(c^{\prime}+\lambda
u_{i})^{2}}=1$. Similar arguments hold for the case when $c^{\prime}<c$. Thus,
$c$, i.e., $\|\mathbf{U}\mathbf{x}^{*}\|_{2}$ is unique. Furthermore,
$\boldsymbol{\rho}$ is unique because of $\rho_{i}=1-\frac{\lambda
u_{i}^{2}}{\|\mathbf{Ux}\|_{2}+\lambda u_{i}^{2}},i=1,2,\ldots,n$.

For the case of
$\|\mathbf{U}\mathbf{x}^{(0)}\|_{2}<\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}$,
similar arguments give increasing and bounded sequences
$\\{\|\mathbf{U}\mathbf{x}^{(k)}\|_{2}\\}$ and $\\{\rho_{i}^{(k)}\\}$. Thus,
they are convergent as well. If
$\|\mathbf{U}\mathbf{x}^{(0)}\|_{2}=\|\mathbf{U}\mathbf{x}^{(1)}\|_{2}$, we
luckily hit the fixed point in one step. Finally, $\mathbf{x}^{*}$ is unique
due to $\mathbf{x}^{*}=\boldsymbol{\rho}\odot\mathbf{v}$. Therefore,
$T(\mathbf{x})$ is a fixed point operator. This completes our proof. ∎

###  1.4 The bounds on the optimal value of the $\ell_{1}$ sparse overlapping
group lasso

We have found the bounds for the overlapping group lasso operator in the
previous section. Now it is natural to transform the bounds on the optimal
value of the $\ell_{1}$ sparse overlapping group lasso into solving two
problems.

####  1.4.1 Lower bound on the optimal value of the $\ell_{1}$ sparse
overlapping group lasso

The lower bound can be obtained by solving the following problem.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{1}\\_\text{GL\\_lb}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Lx}\|_{1}+\lambda_{1}\|\mathbf{x}\|_{1}\right\\}.$
(22)

Since $\mathbf{L}$ is a diagonal matrix, it can be rewritten as

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{1}\\_\text{GL\\_lb}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\|(\lambda\mathbf{L}+\lambda_{1}\mathbf{I})\mathbf{x}\|_{1}\right\\}.$
(23)

which shares the same form as (13) and can be solved in a similar way. For
brevity, we present its solution directly as follows.

$x_{i}=\begin{cases}v_{i}-\lambda l_{i},&\mbox{if }v_{i}>\lambda
l_{i}+\lambda_{1}\\\ 0,&\mbox{if }|v_{i}|\leq\lambda l_{i}+\lambda_{1}\\\
v_{i}+\lambda l_{i},&\mbox{if }v_{i}<-\lambda
l_{i}-\lambda_{1}.\end{cases}\quad i=1,2,\ldots,n.$

####  1.4.2 Upper bound on the optimal value of the $\ell_{1}$ sparse
overlapping group lasso

The upper bound can be obtained by solving the following problem.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{1}\\_\text{GL\\_ub}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Ux}\|_{2}+\lambda_{1}\|\mathbf{x}\|_{1}\right\\}.$
(24)

Let $\boldsymbol{\mu}$ and $\boldsymbol{\nu}$ be the subdifferentials of
$\|\mathbf{x}\|_{2}$ and $\|\mathbf{x}\|_{1}$ at $\mathbf{x}=\mathbf{0}$,
where $\|\boldsymbol{\mu}\|_{2}\leq 1$ and $\|\boldsymbol{\nu}\|_{\infty}\leq
1$. $\Delta$ and $\Lambda$ are defined as

$\Delta=\\{\boldsymbol{\mu}\in\mathbf{R}^{n}\mid\|\boldsymbol{\mu}\|_{2}\leq
1\\},\quad\Lambda=\\{\boldsymbol{\nu}\in\mathbf{R}^{n}\mid\|\boldsymbol{\nu}\|_{\infty}\leq
1\\}.$

If $\mathbf{x}=\mathbf{0}$, using the first-order optimality condition gives

$\mathbf{0}\in\mathbf{0}-\mathbf{v}+\lambda\mathbf{U}^{T}\boldsymbol{\mu}+\lambda_{1}\boldsymbol{\nu}\Longleftrightarrow\mathbf{U}^{-1}\mathbf{v}\in\lambda\boldsymbol{\mu}+\lambda_{1}\mathbf{U}^{-1}\boldsymbol{\nu}\Longleftrightarrow\mathbf{U}^{-1}(\mathbf{v}-\lambda_{1}\boldsymbol{\nu})=\lambda\boldsymbol{\mu}\Longleftrightarrow\max_{\boldsymbol{\nu}\in\Lambda}\,\|\mathbf{U}^{-1}(\mathbf{v}-\lambda_{1}\boldsymbol{\nu})\|_{2}\leq\lambda$

Since $\mathbf{U}^{-1}$ is also a diagonal matrix with positive diagonal
entries, the maximum value of
$\|\mathbf{U}^{-1}(\mathbf{v}-\lambda_{1}\boldsymbol{\nu})\|_{2}$ is attained
at $\boldsymbol{\nu}=-\operatorname{sgn}(\mathbf{v})\odot\mathbf{1}$. Here,
$\operatorname{sgn}$ is an elementwise sign function whose value is $1$ for
positive inputs, $-1$ for negative inputs and 0 otherwise, and $\mathbf{1}$ is
a vector with all entries being $1$. With these settings, we have

$\max_{\boldsymbol{\nu}\in\Lambda}\,\|\mathbf{U}^{-1}(\mathbf{v}-\lambda_{1}\boldsymbol{\nu})\|_{2}=\|\mathbf{U}^{-1}\left(\mathbf{v}+\lambda_{1}\operatorname{sgn}(\mathbf{v})\odot\mathbf{1}\right)\|_{2}=\sqrt{\sum_{i=1}^{n}\left(\frac{v_{i}+\lambda_{1}\operatorname{sgn}(v_{i})}{u_{i}}\right)^{2}}\leq\lambda$

Hence, we get that $\mathbf{x}=\mathbf{0}$ if and only if
$\|\mathbf{U}^{-1}\left(\mathbf{v}+\lambda_{1}\operatorname{sgn}(\mathbf{v})\odot\mathbf{1}\right)\|_{2}\leq\lambda$.

Now we talk about the case of $\mathbf{x}\neq\mathbf{0}$. By the first-order
optimality condition, we have

$\mathbf{0}\in\mathbf{x}-\mathbf{v}+\lambda\frac{\mathbf{U}^{T}\mathbf{Ux}}{\|\mathbf{Ux}\|_{2}}+\lambda_{1}\mathbf{x}^{\prime}$

where $\mathbf{x}^{\prime}$ denotes the subdifferential of $\|\mathbf{x}\|$ at
$\mathbf{x}\neq\mathbf{0}$ defined as follows.

$x^{\prime}_{i}=\begin{cases}1,&\mbox{if }x_{i}>0\\\ -1,&\mbox{if }x_{i}<0\\\
\nu\in[-1,1],&\mbox{if }x_{i}=0.\end{cases}$

If $x_{i}=0$, we have

$x_{i}=0\Longleftrightarrow 0\in 0-v_{i}+0+\lambda_{1}\nu\Longleftrightarrow
v_{i}\in\lambda_{1}\nu\Longleftrightarrow|v_{i}|\leq\lambda_{1}.$

By contradiction, if $x_{i}\neq 0$, it is clear to see that the optimal
$x_{i}$ shares the common sign with $v_{i}$, otherwise it will lead to greater
objective values. Thus, we get

$\mathbf{\tilde{x}}+\lambda\frac{\mathbf{\tilde{U}}^{T}\mathbf{\tilde{U}\tilde{x}}}{\|\mathbf{\tilde{U}\tilde{x}}\|_{2}}=\mathbf{\tilde{v}}-\lambda_{1}\operatorname{sgn}(\mathbf{\tilde{v}})\odot\mathbf{1}\Longleftrightarrow\mathbf{\tilde{x}}=T_{\ell_{1}\text{\\_ub}}\left(\mathbf{I}+\lambda\frac{\mathbf{\tilde{U}}^{T}\mathbf{\tilde{U}\tilde{x}}}{\|\mathbf{\tilde{U}\tilde{x}}\|_{2}}\right)^{-1}(\mathbf{\tilde{v}}-\lambda_{1}\operatorname{sgn}(\mathbf{\tilde{v}})\odot\mathbf{1})$

where $\mathbf{\tilde{x}}$ represents the reduced $\mathbf{x}$ after removing
zero entries, and $\mathbf{\tilde{v}},\mathbf{\tilde{U}}$ are the
corresponding notations. By Theorem 1.4,
$T_{\ell_{1}\text{\\_ub}}(\mathbf{\tilde{x}})$ is a fixed point operator.

###  1.5 The bounds on the optimal value of the $\ell_{0}$ sparse overlapping
group lasso

####  1.5.1 Lower bound on the optimal value of the $\ell_{0}$ sparse
overlapping group lasso

The lower bound can be obtained by solving the following problem.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{0}\\_\text{GL\\_lb}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Lx}\|_{1}+\lambda_{0}\|\mathbf{x}\|_{0}\right\\}.$
(25)

which is separable and can be divided into subproblems as follows.

$\min_{x_{i}\in\mathbf{R}}\left\\{f_{\ell_{0}\\_\text{GL\\_lb}}(x_{i}):=\frac{1}{2}(x_{i}-v_{i})^{2}+\lambda
l_{i}\|x_{i}\|_{1}+\lambda_{0}\|x_{i}\|_{0}\right\\}.$ (26)

If $x_{i}\neq 0$, then (26) can be reduced to solving the following simpler
problem.

$\min_{x_{i}\in\mathbf{R}}f_{\ell_{0}\\_\text{GL\\_lb}}(x_{i})=\frac{1}{2}(x_{i}-v_{i})^{2}+\lambda
l_{i}|x_{i}|+\lambda_{0}$

whose solution is given by (14), namely, $x_{i}=v_{i}-\lambda
l_{i}\operatorname{sgn}(v_{i})$. In this case, if $|v_{i}|>\lambda l_{i}$, the
corresponding objective value is

$f_{\ell_{0}\\_\text{GL\\_lb}}(v_{i}-\lambda
l_{i}\operatorname{sgn}(v_{i}))=\frac{1}{2}(\lambda l_{i})^{2}+\lambda
l_{i}|v_{i}-\lambda l_{i}\operatorname{sgn}(v_{i})|+\lambda_{0},$

and if $|v_{i}|\leq\lambda l_{i}$, we are done and definitely $x_{i}=0$.
However, in the case of $|v_{i}|>\lambda l_{i}$, we still need to compare
$\frac{1}{2}(\lambda l_{i})^{2}+\lambda l_{i}|v_{i}-\lambda
l_{i}\operatorname{sgn}(v_{i})|+\lambda_{0}$ with
$f_{\ell_{0}\\_\text{GL\\_lb}}(0)=\frac{1}{2}v_{i}^{2}$ due to the existence
of the additional term $\lambda_{0}$. If $f_{\ell_{0}\\_\text{GL\\_lb}}(0)\leq
f_{\ell_{0}\\_\text{GL\\_lb}}(v_{i}-\lambda l_{i}\operatorname{sgn}(v_{i}))$,
the solution is $0$ rather than $v_{i}-\lambda
l_{i}\operatorname{sgn}(v_{i})$.

####  1.5.2 Upper bound on the optimal value of the $\ell_{0}$ sparse
overlapping group lasso

The upper bound can be obtained by solving the following problem.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{0}\\_\text{GL\\_ub}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\|\mathbf{Ux}\|_{2}+\lambda_{0}\|\mathbf{x}\|_{0}\right\\}.$
(27)

By the definition of the induced norm of $\|\cdot\|_{a,b}$, we have
$\|\mathbf{Ux}\|_{2}\leq\|\mathbf{U}\|_{2}\|\mathbf{x}\|_{2}$. When $a=b=2$,
$\|\mathbf{U}\|_{2}$ is called the spectral norm and it is equal to the
maximum singular value of $\mathbf{U}$, denoted as
$\sigma_{\mathrm{max}}(\mathbf{U})$. Thus, the upper bound can be relaxed as
follows.

$\min_{\mathbf{x}\in\mathbf{R}^{n}}\left\\{f_{\ell_{0}\\_\text{GL\\_ub}}(\mathbf{x}):=\frac{1}{2}\|\mathbf{x}-\mathbf{v}\|_{2}^{2}+\lambda\sigma_{\mathrm{max}}(\mathbf{U})\|\mathbf{x}\|_{2}+\lambda_{0}\|\mathbf{x}\|_{0}\right\\}.$
(28)

which has a closed-form solution proposed by Shao et al., (2022).

##  2 Acknowledgement

The inspiration of this work is from reading Boyd et al., (2011).

## References

  * Boyd et al., (2011) Boyd, S. P., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011).  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Found. Trends Mach. Learn., 3:1–122.
  * Shao et al., (2022) Shao, Y., Zhao, K., Cao, Z., Peng, Z., Peng, X., Li, P., Wang, Y., and Ma, J. (2022).  Mobileprune: Neural network compression via $\ell_{0}$ sparse group lasso on the mobile system.  Sensors, 22(11):4081.