# Exclusive Sparsity Norm Minimization with Random Groups via Cone Projection

Yijun Huang and Ji Liu
{huangyj0<EMAIL_ADDRESS>
Department of Computer Sciences, University of Rochester

###### Abstract

Many practical applications such as gene expression analysis, multi-task
learning, image recognition, signal processing, and medical data analysis
pursue a sparse solution for the feature selection purpose and particularly
favor the nonzeros _evenly_ distributed in different groups. The exclusive
sparsity norm has been widely used to serve to this purpose. However, it still
lacks systematical studies for exclusive sparsity norm optimization. This
paper offers two main contributions from the optimization perspective: 1) We
provide several efficient algorithms to solve exclusive sparsity norm
minimization with either smooth loss or hinge loss (non-smooth loss). All
algorithms achieve the optimal convergence rate $O(1/k^{2})$ ($k$ is the
iteration number). To the best of our knowledge, this is the first time to
guarantee such convergence rate for the general exclusive sparsity norm
minimization; 2) When the group information is unavailable to define the
exclusive sparsity norm, we propose to use the random grouping scheme to
construct groups and prove that if the number of groups is appropriately
chosen, the nonzeros (true features) would be grouped in the ideal way with
high probability. Empirical studies validate the efficiency of proposed
algorithms, and the effectiveness of random grouping scheme on the proposed
exclusive SVM formulation.

##  1 Introduction

The exclusive sparsity norm ($\ell_{e}$ norm, also namely $\ell_{1,2}$ norm in
some literatures) is defined as

$\|{\bf w}\|_{e}:=\sqrt{\sum_{g\in\mathcal{G}}\|{\bf w}_{g}\|_{1}^{2}}$ (1)

where ${\bf w}\in\mathbb{R}^{n}$, $g_{i}~{}(i=\\{1,2,\cdots,m\\})$ is a subset
of $\\{1,2,\cdots,n\\}$, and $\mathcal{G}=\\{g_{1},g_{2},\cdots,g_{m}\\}$ is
the super set of groups. The groups $g_{i}$’s may have overlaps. The exclusive
sparsity norm regularization serves to enforce a structural sparsity on the
solution such that its nonzeros are (roughly) evenly distributed in different
groups.

Figure 1 shows an example to illustrate the difference of the sparsity pattern
induced by the $\ell_{e}$ norm regularization from several other commonly used
(sparse) regularizations including $\ell_{2}$ norm $\|{\bf w}\|$, $\ell_{1}$
norm $\|{\bf w}\|_{1}$, and $\ell_{2,1}$ (group sparsity) norm $\|{\bf
w}\|_{2,1}$. We can observe that

  * •

the $\ell_{2}$ norm does not enforce sparsity (actually usually leads to a
dense solution);

  * •

the $\ell_{1}$ norm enforces a sparse solution but has no any structural
pattern;

  * •

the $\ell_{2,1}$ norm enforces a group sparsity, i.e., nonzeros concentrate in
the same group;

  * •

the $\ell_{e}$ norm provides a dense solution in the group level but a sparse
solution inside of groups.

Figure 1: Sparsity structure induced by different norms: $\ell_{2}$ norm,
$\ell_{1}$ norm, $\ell_{2,1}$ norm, and $\ell_{e}$ norm. Blue blocks indicate
nonzeros and white blocks indicate zeros.

To further explain the difference among these norms above, we assume that
there are two important features $f_{i}$ and $f_{j}$ in two disjoint groups.
They are similar and highly correlated. $\|{\bf w}\|$ prefers to select both
of them; $\|{\bf w}\|_{1}$ prefers to select the one which gives a lower
objective function value; $\|{\bf w}\|_{2,1}$ prefers to select the one with
more group members selected; and $\|{\bf w}\|_{e}$ prefers to select the one
with fewer group members selected.

Since the exclusive sparsity norm enforces a special and unique sparse
structure, it has been widely used and received many successes in applications
including gene expression analysis (Breheny and Huang, 2009; Kim and Xing,
2012), siginal processing (Bayram and Akyıldız, 2014; Balazs et al., 2013;
Kowalski et al., 2013), multi-task learning (Wang et al., 2014; Lozano and
Swirszcz, 2012), image recognition / classification (Chen et al., 2011; Liu et
al., 2011) and medical data analysis (Lin et al., 2014; Vidyasagar, 2014).

While the $\ell_{1}$ norm, $\ell_{2}$ norm, and $\ell_{2,1}$ norm have
received extensive studies, it still lacks systematical studies for the
exclusive sparsity $\ell_{e}$ norm on twofold: optimization (how to
efficiently solve $\ell_{e}$ norm minimization problem) and consistency
analysis (under what condition the solution to the $\ell_{e}$ norm regularized
formulation converges to the true model asymptotically?). This paper mainly
considers the optimization aspect and leave the consistency analysis as the
future work.

We mainly offer two contributions. First, this paper considers two types of
$\ell_{e}$ norm minimization problems 1) smooth convex loss +
$\|\cdot\|^{2}_{e}$ and 2) hinge loss (non-smooth convex function) +
$\|\cdot\|^{2}_{e}$. To efficiently solve the $\ell_{e}$ norm minimization
problems, the key step is to solve the proximal problem. Due to the difficulty
of precisely solving the proximal step, it still lacks efficient algorithms to
solve the general $\ell_{e}$ norm minimization problems, especially for the
case where groups have overlaps. We propose several simple tricks to
reformulate the original formulations, derive efficiently solvable proximal
steps, and provide three optimization algorithms (Fista-pcp, Fista-locp,
Fista-licp) achieving the optimal convergence rate by adopting the Fista
framework. To the best of our knowledge, this is the first time to obtain such
optimal convergence rate $O(1/k^{2})$ for the general $\ell_{e}$ norm
minimization problems. In addition, a new SVM (E-SVM) formulation is proposed.

Second, existing applications of the exclusive sparsity norm usually assume
that groups have been well defined. However, if the group information is
unavailable, how to define reasonable groups? This paper proposes to use the
random grouping scheme to obtain groups and proves that each group will have
roughly equal number of true features with high probability by using this
scheme. Empirical studies validate the efficiency of the proposed algorithms
and effectiveness of the proposed random grouping scheme.

Notation Throughout the whole paper, we use the following notations:

  * •

Both $g$ and $g_{i}$ denote the subset of $\\{1,2,\cdots,n\\}$; other plain
small letters denote scalars, for example, $a,x,\alpha$.

  * •

$n$ denotes the dimension of the feature vector. $m$ denotes the number of
groups.

  * •

Bold small letters denote vectors, for example, ${\bf a},{\bf u},{\bf x},{\bf
w}$.

  * •

$\mathcal{G}$ is the superset of all groups $g_{1},\cdots,g_{m}$; other
capital letters denote matrices, for example, $A,X$.

  * •

$|\cdot|$ returns a vector consisting of absolute values of components in
“$\cdot$”, if “$\cdot$” is a vector. $|\cdot|$ returns the cardinality of
“$\cdot$”, if “$\cdot$” is a set.

  * •

${\bf w}_{g}\in\mathbb{R}^{|g|}$ is the subvector of ${\bf w}$ consisting of
elements of ${\bf w}$ in the index set $g$. ${\bf w}_{i}$ is the $i$th
component of ${\bf w}$. ${\bf{1}}$ denotes a vector with all $1$’s. We will
also use the notation ${\bf w}^{g}\in\mathbb{R}^{|g|}$, which is a free vector
named by ${\bf w}^{g}$ and whose value has nothing to do with ${\bf w}$.

  * •

$\|{\bf w}\|_{2}$ or $\|{\bf w}\|$ denotes the $\ell_{2}$ norm of ${\bf w}$:
$\sqrt{\sum_{i}{\bf w}_{i}^{2}}$.

  * •

$\|{\bf w}\|_{1}$ denotes the $\ell_{1}$ norm: $\sum_{i}|{\bf w}_{i}|$.

  * •

$\|{\bf w}\|_{\infty}$ is the infinity norm: $\max_{i}|{\bf w}_{i}|$.

  * •

${\bf I}_{\text{condition}}({\bf x})$ is the indicator function which returns
$0$ if ${\bf x}$ satisfies the “condition”; otherwise $+\infty$.

Organization The related work is reviewed in Section 2. In Section 3, we
provide preliminary results first, then propose efficient algorithms for
solving a general problem in the form “smooth loss + exclusive sparsity
regularization”, and in the last propose the exclusive SVM formulation “hinge
loss + exclusive sparsity regularization” and the efficient algorithm to solve
it. We discuss the random grouping scheme in Section 4. We report the
empirical study for the proposed algorithms and formulations in Section 5 and
conclude this paper in Section 6. All proofs are provided in Supplemental
Materials.

##  2 Related Work

Structural sparsity induced by regularization terms have been widely used
recently for the feature selection purpose (Bach, 2012; Jenatton et al.,
2011). Both theoretical and empirical studies have suggested the powerfulness
of structure sparsity for feature learning, e.g., LASSO (Tibshirani, 1996),
group LASSO (Yuan and Lin, 2006), exclusive LASSO (Zhou et al., 2010), fused
LASSO (Tibshirani et al., 2005; Liu et al., 2013), and generalized LASSO
(Roth, 2004). We refer readers to Bach (2012) for comprehensive review.

The $\ell_{1}$ norm minimization problem, particularly the LASSO formulation
(Tibshirani, 1996), has received extensive attentions. Many efficient
algorithms have been proposed to solve it, including proximal gradient descent
(Wright et al., 2009), accelerated gradient descent (Nesterov, 2004), Fista
(Beck and Teboulle, 2009), coordinate descent (Wu and Lange, 2008),
accelerated coordinate descent (Fercoq et al., 2014), and interior point
method (Koh et al., 2007). We refer readers to Tropp and Wright (2010) for
comprehensive review of the $\ell_{1}$ norm optimization.

The $\ell_{2,1}$ (group sparsity) norm minimization, particularly the group
LASSO (without overlaps) (Yuan and Lin, 2006), can be solved using similar
optimization algorithms to $\ell_{1}$ norm problems by simply treating each
group as an element (Liu et al., 2009). For the the group LASSO with overlaps,
one can use the Admm framework to solve it (Boyd et al., 2011), where the key
step can still apply those approaches for non-overlapping formulations.

The exclusive sparsity regularization was originally defined on matrices for
the feature selection purpose in multi-task learning (Zhou et al., 2010). A
subgradient algorithm is proposed to solve this problem, but leads to a slow
convergence rate $O(1/\sqrt{k})$, where $k$ is the number of iterations. Kong
et al. (2014) considers to minimize an objective “$\text{least squares
loss}+\lambda\|{\bf w}\|^{2}_{e}$” and proposes a reweighed approach to solve
it. However, the proposed reweighted approach only guarantees convergence,
which means that the convergent point is not necessarily the optimal solution.
Chen et al. (2011) considers to minimize an variant objective “$\text{least
squares loss}+\lambda\|D{\bf w}\|^{2}_{e}$”. They apply the Nesterov’s
smoothing scheme to smooth the regularization term and the Nesterov’s
accelerated approach to solve an approximate smooth objective function
(Nesterov, 2005). This algorithm leads to a convergence rate $O(1/k)$. To the
best of our knowledge, none of existing algorithms can strictly achieve the
optimal convergence rate $O(1/k^{2})$ for the general exclusive sparsity norm
minimization even the loss function is smooth.

Algorithm 1 The General Framework of Fista

0: ${\bf x}^{\text{old}}$, $\gamma$ (steplength)

0: ${\bf x}^{\text{new}}$

1: Initialize $t^{\text{old}}=1$, $\bar{{\bf x}}={\bf x}^{\text{old}}$;

2: while not converge do

3: ${\bf x}^{\text{new}}=\text{Prox}_{\gamma H({\bf x})}(\bar{{\bf
x}}-\gamma\nabla F(\bar{{\bf x}}))$;

4: $t^{\text{new}}={1\over 2}+{1\over 2}\sqrt{1+4t^{\text{old}}}$;

5: $\bar{{\bf x}}={\bf x}^{\text{new}}+({\bf x}^{\text{new}}-{\bf
x}^{\text{old}})(t^{\text{old}}-1)/t^{\text{new}}$;

6: ${\bf x}^{\text{old}}={\bf x}^{\text{new}}$,
$t^{\text{old}}=t^{\text{new}}$;

7: end while

##  3 Optimization

We consider two types of exclusive sparsity norm minimization problems: smooth
loss function and non-smooth loss (specifically hinge loss) function. Several
efficient algorithms would be provided, with the guarantee of the optimal
convergence rate $O(1/k^{2})$.

###  3.1 Preliminary Results

For optimization problems with the structure: “smooth loss $F({\bf x})$ \+
non-smooth function $H({\bf x})$”

$\displaystyle\min_{{\bf x}}\quad F({\bf x})+H({\bf x}),$ (2)

the Nesterov type of accelerated algorithms (Nesterov, 2007), for example,
Fista (Beck and Teboulle, 2009) in Algorithm 1, is often considered as one of
the most efficient gradient based algorithms, since it achieves the optimal
convergence rate $O(1/k^{2})$ where $k$ is the number of iterations. $H({\bf
x})$ could be the regularizer such as $\|{\bf x}\|_{1}$ and $\|{\bf x}\|$ or
the indicator function representing the constraint, for example, ${\bf
I}_{{\bf x}\geq 0}({\bf x})$. One can see the key step in Fista is Step 3 (the
proximal step) in Algorithm 1, which essentially solves the following problem:

${\text{Prox}}_{\gamma H({\bf x})}({\bf
c}):=\operatornamewithlimits{argmin}_{{\bf x}}\quad{1\over 2}\|{\bf x}-{\bf
c}\|^{2}+\gamma H({\bf x})$ (3)

where ${\bf c}=\bar{{\bf x}}-\gamma\nabla F(\bar{{\bf x}})$. The steplength
$\gamma$ can be set as any positive constant smaller than
$(\max_{x}\|\nabla^{2}F(x)\|)^{-1}$ or decided by using the linear search
scheme (Beck and Teboulle, 2009). The difficulty of solving (2) is decided by
the complexity of $H({\bf x})$. When $H({\bf x})$ is simple enough such as
$\|{\bf x}\|_{1}$, $\|{\bf x}\|$, or ${\bf I}_{{\bf x}\geq 0}({\bf x})$, the
proximal step (3) is easy. However, if $H({\bf x})$ is $\|{\bf x}\|_{e}$, it
is difficult to solve efficiently even all groups have no overlaps. Therefore
we need reformulation work to simplify the proximal steps. The following
preliminary results play the key roles in reformulation and solving proximal
steps.

Algorithm 2 $[{\bf x},y]=\text{P}_{1}^{\zeta}({\bf a},b)$

0: ${\bf a}\in\mathbb{R}^{d}$, $b\in\mathbb{R}$, $\zeta\in\mathbb{R}$

0: ${\bf x}\in\mathbb{R}^{d}$, $y\in\mathbb{R}$

1: Sort the sequence $\\{|{\bf a}_{j}|~{}|~{}j=1,\cdots,d\\}$ in the
decreasing order and denote $|{\bf a}|^{(j)}$ the $j$th largest element of
${\bf a}$ in the absolute value sense and define $|{\bf a}|^{(d+1)}$ as $0$;

2: $t=0$;

3: for $j=1:d$ do

4: $t=t+|{\bf a}|^{(j)}$;

5: $\delta=(t-b)/(\zeta^{-1}+j)$;

6: if $|{\bf a}|^{(j+1)}\leq\delta\leq|{\bf a}|^{(j)}$ then

7: ${\bf x}=\text{sgn}({\bf a})\odot\max({\bf{0}},|{\bf a}|-\delta)$;

8: $y=\|{\bf x}\|_{1}$;

9: Return;

10: end if

11: end for

12: ${\bf x}={\bf a}$;

13: $y=b$;

Algorithm 3 $[{\bf x},y]=\text{P}_{\infty}^{\zeta}({\bf a},b)$

0: ${\bf a}\in\mathbb{R}^{d}$, $b\in\mathbb{R}$, $\zeta\in\mathbb{R}$

0: ${\bf x}\in\mathbb{R}^{d}$, $y\in\mathbb{R}$

1: $y=0$;

2: ${\bf x}={\bf 0}$;

3: Sort the sequence $\\{|{\bf a}_{j}|~{}|~{}j=1,\cdots,d\\}$ in the
increasing order and denote $|{\bf a}|^{(j)}$ the $j$th smallest element of
${\bf a}$ in the absolute value sense and define $|{\bf a}|^{(0)}$ as $0$;

4: if $b\geq|{\bf a}|^{(d)}$ then

5: $y=b$;

6: ${\bf x}={\bf a}$;

7: Return;

8: end if

9: $t=0$;

10: for $j=d-1:-1:0$ do

11: $t=t+|{\bf a}|^{(j+1)}$;

12: $y={\zeta b+t\over\zeta+d-j}$;

13: if $y\in(|{\bf a}|^{(j)},~{}|{\bf a}|^{(j+1)}]$ then

14: ${\bf x}=\text{sgn}({\bf a})\odot\min(|{\bf a}|-y,0)$;

15: Return;

16: end if

17: end for

We first propose an alternative way to represent $\|{\bf w}\|_{e}^{2}$ in
Lemma 1:

######  Lemma 1.

Let ${\bf v}^{g}\in\mathbb{R}^{|g|}$ denote the $|g|-$ dimensional vector. For
any $\beta>0$, we have

$\displaystyle\|{\bf w}\|_{e}^{2}=\sum_{g\in\mathcal{G}}\left(\max_{{\bf
v}^{g}\in\mathbb{R}^{|g|}}\frac{2}{\beta}\langle{\bf w}_{g},{\bf
v}^{g}\rangle-{1\over\beta^{2}}\|{\bf v}^{g}\|_{\infty}^{2}\right).$ (4)

This lemma is used to decompose the overlaps among groups in the dual space.
It will be used to reformulate E-SVM.

######  Lemma 2.

Algorithm 2 exactly solves ${\bf P}^{\zeta}_{1}({\bf a},b)$ – the projection
of $[{\bf a};b]$ onto the $\ell_{1}$ norm cone $\\{[{\bf x};y]~{}|~{}\|{\bf
x}\|_{1}\leq y\\}$:

$\displaystyle{\bf P}^{\zeta}_{1}({\bf
a},b):=\operatornamewithlimits{argmin}_{{\bf x}\in\mathbb{R}^{d},y}$
$\displaystyle{1\over 2}\|{\bf x}-{\bf a}\|^{2}+{\zeta\over 2}(y-b)^{2}\quad$
(5) s.t. $\displaystyle\|{\bf x}\|_{1}\leq y.$

Problem (5) can be considered as a general version of the projection onto the
$\ell_{1}$ cone. Although (5) does not have the closed form, but its solution
can be obtained from a search routine in Algorithm 2. Algorithm 2 essentially
gives a method to search a feasible point satisfying the KKT condition. The
complexity of this algorithm is $O(d\log d)$. The key motivation behind this
algorithm is the monotonicity of the optimal solution ${\bf x}^{*}$, that is,
if $|{\bf a}_{i}|\geq|{\bf a}_{j}|$, then $|{\bf x}^{*}_{i}|\geq|{\bf
x}^{*}_{j}|$. This lemma will be used in solving the special case (groups have
no overlaps) of the first type problem.

Lemma 3 provides a solution to a similar problem to Lemma 2. The only
difference lies on that the $\ell_{1}$ norm in the constraint is replaced by
the $\ell_{\infty}$ norm.

######  Lemma 3.

Algorithm 3 exactly solves ${\bf P}^{\zeta}_{\infty}({\bf a},b)$ – the
projection of $[{\bf a};b]$ onto the $\ell_{\infty}$ norm cone $\\{[{\bf
x};y]~{}|~{}\|{\bf x}\|_{\infty}\leq y\\}$:

$\displaystyle{\bf P}_{\infty}^{\zeta}({\bf
a},b):=\operatornamewithlimits{argmin}_{{\bf x}\in\mathbb{R}^{d},y}$
$\displaystyle{1\over 2}\|{\bf x}-{\bf a}\|^{2}+{\zeta\over 2}(y-b)^{2}$ (6)
s.t. $\displaystyle\|{\bf x}\|_{\infty}\leq y$

Problem (6) can be considered as a general version of the projection onto the
$\ell_{\infty}$ cone. The complexity of Algorithm 3 is also $O(d\log d)$. This
algorithm also follows the sprit of the monotonicity of the optimal solution.
This lemma would be used in solving the problem with non-smooth loss function.

###  3.2 Smooth Loss Function $+$ $\ell_{e}$ Regularization: Fista-pcp and
Fista-locp Algorithms

We consider the following general formulation

$\displaystyle\min_{{\bf w}}\quad f({\bf w})+{\lambda\over 2}\|{\bf
w}\|^{2}_{e}.$ (7)

Note that here we do not assume groups $g$’s to be disjoint. One might ask why
do not use $\phi\|{\bf w}\|_{e}$ as the regularizer. The reason lies on that
${\lambda\over 2}\|{\bf w}\|^{2}_{e}$ is easier to solve efficiently and leads
to the same solution as using $\phi\|{\bf w}\|_{e}$ if $\lambda(\phi)$ is
appropriately chosen. Note that $\|{\bf w}\|^{2}_{e}$ is still non-smooth.

To directly apply the Fista framework, one has to solve the proximal step (3)
with $H(\cdot)={\lambda\over 2}\|{\bf w}\|^{2}_{e}$. However, it is very
difficult to solve it efficiently in general. Existing approaches apply
iterative algorithms to _approximately_ solve this proximal step, for example,
in Kong et al. (2014); Yuan and Yan (2011), thus requiring heavy computation
load (computing the inverse of a $n\times n$ matrix) and unable to
theoretically ensure the convergence (rate).

We propose to use a simple substitution to reformulate the problem (7), which
largely simplifies the original formulation. The key idea is to decompose the
variable ${\bf w}$ into two parts: positive part ${\bf w}_{+}\geq{\bf{0}}$ and
negative part ${\bf w}_{-}\geq{\bf{0}}$ such that ${\bf w}={\bf w}_{+}-{\bf
w}_{-}$ and $\|{\bf w}_{g}\|_{1}={\bf{1}}^{\top}(({\bf w}_{+})_{g}+({\bf
w}_{-})_{g})$. It leads to an equivalent formulation to (7):

$\displaystyle\min_{{\bf w}_{+}\geq 0,{\bf w}_{-}\geq 0}~{}f({\bf w}_{+}-{\bf
w}_{-})+{\lambda\over 2}\sum_{g\in\mathcal{G}}({\bf{1}}^{\top}({\bf
w}_{+})_{g}+{\bf{1}}^{\top}({\bf w}_{-})_{g})^{2}$ $\displaystyle=$
$\displaystyle\min_{{\bf w}_{+},{\bf w}_{-}}\underbrace{f({\bf w}_{+}-{\bf
w}_{-})+{\lambda\over 2}({\bf w}_{+}+{\bf w}_{-})^{\top}Q({\bf w}_{+}+{\bf
w}_{-})}_{=:F([{\bf w}_{+};{\bf w}_{-}])}+$
$\displaystyle\quad\quad\quad\underbrace{{\bf I}_{{\bf w}_{+}\geq 0}({\bf
w}_{+})+{\bf I}_{{\bf w}_{-}\geq 0}({\bf w}_{-})}_{=:H([{\bf w}_{+};{\bf
w}_{-}])},$ (8)

where $Q$ is a positive semidefinite matrix and its elements are defined by

$\displaystyle Q_{ij}=\begin{cases}|\\{g\in\mathcal{G}~{}|~{}\\{i,j\\}\subset
g\\}|,&\text{if }i\neq j\\\ |\\{g\in\mathcal{G}~{}|~{}i\in
g\\}|,&\text{otherwise.}\end{cases}$

This simple trick turns the original non-smooth minimization (7) into a smooth
minimization with simple constraints. In other words, (8) is an equivalent
form of (7). (8) can be easily solved by accelerated Nesterov approach or
Fista, since the key proximal step has closed form

$\displaystyle\text{Prox}_{\gamma H(\cdot)}([{\bf c}_{+};{\bf c}_{-}])={}$
$\displaystyle\operatornamewithlimits{argmin}_{{\bf w}_{+},{\bf
w}_{-}}~{}{1\over 2}\|[{\bf w}_{+};{\bf w}_{-}]-[{\bf c}_{+};{\bf
c}_{-}]\|^{2}+$ $\displaystyle\quad\quad\quad\quad H([{\bf w}_{+};{\bf
w}_{-}])$ $\displaystyle={}$ $\displaystyle[\max({\bf{0}},{\bf
c}_{+});\max({\bf{0}},{\bf c}_{-})].$

Now we can apply the proximal operator to the Fista framework in Algorithm 1.
Since the key step is the projection onto the positive cone, we call it
positive cone projection (Fista-pcp) algorithm to distinguish the later
algorithms. The main workload per iteration is just to compute the gradient,
which is the minimal computation load for the gradient based approaches. To
the best of our knowledge, this is the first approach to solve overlapped
exclusive sparsity regularization with the optimal convergence rate
$O(1/k^{2})$. It is worth to point out that for the more general exclusive
sparsity norm minimization “$\text{smooth loss}+\sum_{g\in\mathcal{G}}\|{\bf
w}_{g}\|^{q}_{q}$” ($q\geq 1$), one can also apply this positive-negative
decomposition trick to obtain the optimal convergence rate.

Actually, if groups $g$’s are disjoint (or have no overlaps), we can derive a
slightly more efficient algorithm, because the following proximal step can be
solved efficiently (letting $H({\bf w})={\lambda\over 2}\|{\bf w}\|^{2}_{e}$)

$\displaystyle{\text{Prox}_{\gamma H(\cdot)}}({\bf
c}):=\operatornamewithlimits{argmin}_{{\bf w}}\quad{1\over 2}\|{\bf w}-{\bf
c}\|^{2}+{\gamma\lambda\over 2}\|{\bf w}\|_{e}^{2}.$ (9)

The following will show that this problem can be solved efficiently due to
Lemma 2. (If we use $\|{\bf w}\|_{e}$ as the regularizer, then (9) is
difficult to solve efficiently.) This why we are interested in (7).

Because groups are disjoint, the proximal step can be split into a few
subproblems

$\min_{{\bf w}_{g}}\quad{1\over 2}\|{\bf w}_{g}-{\bf
c}_{g}\|^{2}+{\gamma\lambda\over 2}\|{\bf w}_{g}\|_{1}^{2}\quad\forall
g\in\mathcal{G}.$

To solve this problem, we can reformulated it into the form of (5)

$\displaystyle\min_{{\bf w}_{g},t}\quad$ $\displaystyle{1\over 2}\|{\bf
w}_{g}-{\bf c}_{g}\|^{2}+{\gamma\lambda\over 2}t^{2}\quad$ s.t.
$\displaystyle\|{\bf w}_{g}\|_{1}\leq t$

whose solution is exactly provided by ${\bf P}_{1}^{\gamma\lambda}({\bf
c}_{g},0)$.

Now we can simply apply the proximal operator defined in (9) to the Fista
framework to obtain an algorithm with the optimal convergence rate. Since the
proximal step in this algorithm is the projection onto the $\ell_{1}$ cone, we
call this algorithm as L-one cone projection (Fista-locp) algorithm. One can
verify that the computation load per iteration is still on the gradient, that
is, $O(n^{2})$, if the number of samples is proportional to $n$.

###  3.3 Exclusive SVM (Non-smooth Loss + $\ell_{e}$ Regularization): Fista-
licp Algorithm

This section considers the case where the loss function is non-smooth. In
general, it is difficult to find an efficient algorithm to minimize non-smooth
objective function. To solve such general problems, one can apply the
subgradient algorithm, which leads to a convergence rate $O(1/\sqrt{k})$. We
only consider a specific non-smooth loss function “hinge loss” which is the
most popular non-smooth loss function in machine learning and data mining due
to SVM. In particular, we are interested in solving the following exclusive
SVM (E-SVM) formulation:

$\displaystyle\min_{\bf w}\quad\sum_{i}$ $\displaystyle\max(1-Z_{i}^{\top}{\bf
w},0)+{\alpha\over 2}\|{\bf w}\|^{2}+{\beta\over 2}\|{\bf w}\|_{e}^{2},$ (10)

where groups $g_{i}$’s defined in the $\ell_{e}$ norm may have overlaps. This
formulation is motivated by finding a linear classifier only defined on a few
features which evenly distributed in different groups. “Hinge loss + exclusive
sparsity regularization” in (10) is a very natural idea, but people usually
try to avoid solving it mainly due to the lack of efficient algorithms. For
example, to avoid solving (10), Kong et al. (2014, see Section 5.2) pretend
the classification problem to be the regression problem by using the exclusive
LASSO formulation for the feature selection purpose. The section derives an
efficient algorithm to solve (10) with the optimal convergence rate
$O(1/k^{2})$.

Apparently, it is ineligible to apply the Fista framework directly, due to the
non-smooth “hinge loss” and the overlapped exclusive sparsity regularizer
$\|{\bf w}\|^{2}_{e}$. The following reformulation uses Lemma 1 and strong
duality to reformulate (10):

######  Theorem 4.

Let $[{\bf u}_{*};\\{{\bf v}^{g}_{*}\\}_{g\in\mathcal{G}}]$ be the solution of
the following problem:

$\displaystyle[{\bf u}_{*};\\{{\bf
v}^{g}_{*}\\}_{g\in\mathcal{G}}]=\operatornamewithlimits{argmin}_{{\bf
u},\\{{\bf v}^{g}\\}_{g\in\mathcal{G}}}$ $\displaystyle\underbrace{{1\over
2\alpha}\left\|Z{\bf u}-\sum_{g\in\mathcal{G}}\overline{{\bf
v}^{g}}\right\|^{2}-{\bf{1}}^{\top}{\bf u}}_{=:F([{\bf u};\\{{\bf
v}^{g}\\}_{g\in\mathcal{G}}])}+$ $\displaystyle\underbrace{{1\over
2\beta}\sum_{g\in\mathcal{G}}\|{\bf
v}^{g}\|_{\infty}^{2}+{\bf{I}}_{{\bf{0}}\leq{\bf u}\leq{\bf{1}}}({\bf
u})}_{=:H([{\bf u};\\{{\bf v}^{g}\\}_{g\in\mathcal{G}}])},$ (11)

where $Z_{i}$ (the $i$th column of matrix $Z$) denotes $y_{i}X_{i}$ and
$\overline{{\bf v}^{g}}\in\mathbb{R}^{n}$ to denote the extended version of
${\bf v}^{g}\in\mathbb{R}^{|g|}$, that is, the elements in $g$ of
$\overline{{\bf v}^{g}}$ take the corresponding values of ${\bf v}^{g}$ and
zeros in the rest. Then we have that the solution ${\bf w}_{*}$ to E-SVM in
(10) can be obtained by

${\bf w}_{*}={\alpha^{-1}}\left(Z{\bf
u}_{*}-\sum_{g\in\mathcal{G}}\overline{{\bf v}^{g}}_{*}\right).$

(11) essentially defines a dual formulation of (10). We can reconstruct the
solution to (10) by solving (11), which actually fits the structure “smooth
function $F(\cdot)$ \+ non-smooth function $H(\cdot)$” in (2). To apply the
Fista framework in Algorithm 1, we only need to show an efficient algorithm to
compute the proximal step defined in (3):

$\displaystyle\text{Prox}_{\gamma H(\cdot)}([{\bf c};\\{{\bf
d}^{g}\\}_{g\in\mathcal{G}}])$ $\displaystyle:=$
$\displaystyle\operatornamewithlimits{argmin}_{{\bf u},{\bf
v}^{g}:~{}g\in\mathcal{G}}{1\over 2}\|{\bf u}-{\bf c}\|^{2}+\gamma{\bf
I}_{{\bf u}\in[{\bf{0}},{\bf{1}}]}({\bf u})+$
$\displaystyle\quad\quad\quad\quad\sum_{g\in\mathcal{G}}\left({1\over 2}\|{\bf
v}^{g}-{\bf d}^{g}\|^{2}+{\gamma\over 2\beta}\|{\bf
v}^{g}\|^{2}_{\infty}\right).$ (12)

Since $H({\bf u},\\{{\bf v}^{g}:~{}g\in\mathcal{G}\\})$ is separable in terms
of all variables ${\bf u}$ and ${\bf v}^{g}(g\in\mathcal{G})$. ${\bf u}$ can
be simply solved by projecting ${\bf c}$ to the feasible region
$[{\bf{0}},{\bf{1}}]$. All ${\bf v}^{g}$’s are computed solving the following
problem:

$\min_{{\bf v}^{g}}\quad{1\over 2}\|{\bf v}^{g}-{\bf d}^{g}\|^{2}+{\gamma\over
2\beta}\|{\bf v}^{g}\|^{2}_{\infty}\quad\forall g\in\mathcal{G}.$

To solve each subproblem, we can reformulate it into the form of (6)

$\displaystyle\min_{{\bf v}^{g}}\quad$ $\displaystyle{1\over 2}\|{\bf
v}^{g}-{\bf d}^{g}\|^{2}+{\gamma\over 2\beta}t^{2}\quad\quad$ s.t.
$\displaystyle\|{\bf v}^{g}\|_{\infty}\leq t.$

From Lemma 3, each subproblem can be solved by ${\bf
P}_{\infty}^{\gamma/\beta}({\bf d}^{g},0)$ in Algorithm 3. Since the key
proximal step mainly uses the projection onto the infinity cone, we call this
algorithm as L-infinity cone projection (Fista-licp) algorithm.

##  4 Random Grouping Scheme

The group information needs to be known to define the exclusive sparsity norm.
In some cases such as multi-task feature selection (Zhou et al., 2010) and
image classification (Chen et al., 2011), groups have been defined in a
natural manner, for example, features are grouped in terms of kinds. However,
sometimes the natural group information is unavailable or does not make sense
for some specific purpose. Therefore, the key question is how to construct
groups for defining the exclusive sparsity regularization.

The exclusive sparsity regularization tends to provide a solution with
nonzeros (selected features) evenly distributed in different groups. The ideal
grouping result is that all $s$ true (really important) features are evenly
distributed in different groups (of course we have no idea what features are
true or important beforehand). This motivates us to use the random grouping
scheme, that is, uniformly randomly split all features indexed by
$\\{1,2,\cdots,n\\}$ into $m$ disjoint groups with roughly equal size.
Apparently, the ideal case is that each group is assigned $s/m$ true features.
Although the random grouping scheme does not necessarily achieve the ideal
case, it still can provide a reasonable grouping result. Theorem 5 basically
shows that the number of true features assigned to any group would be roughly
equal.

######  Theorem 5.

Assume that we have $s$ true features among $n$ features, that is, the true
model only has $s$ nonzero elements ($s\leq n$). The feature index set
$\\{1,2,\cdots,n\\}$ is uniformly randomly split into $m$ groups with roughly
equal size.111The size difference between two groups is $1$ maximally. If the
chosen number of groups $m$ satisfies $s\geq O(t^{-2}m\log m)$, where $t$
could be any number in the range $(0,1)$, then with high probability,222“With
high probability” means that the probability converges to $1$ when the number
of true features $s$ converges to infinity. the following holds

$\frac{\max_{j}|\Omega_{j}|}{\min_{j}|\Omega_{j}|}\leq\frac{1+t}{1-t}.$

where $\Omega_{j}\subset g_{j}$ denote the index set of true features assigned
to group $j\in\\{1,2,\cdots,m\\}$.

Note that Theorem 5 is independent to the total number of features $n$. The
only requirement in this theorem is that the number of groups $m$ should be
set properly to satisfy $s\geq O(t^{-2}m\log m)$. One can trivially set $m=1$
to meet this condition, it reduces the $\ell_{e}$ norm to the plain $\ell_{1}$
norm, which does not take any benefits from the $\ell_{e}$ norm. Therefore,
intuitively one always expect to set $m$ to a value as large as possible. A
simple way to choose $m$ to satisfy the condition is $m=\text{constant}\times
s/\log s$.

##  5 Experiments

This section mainly validates the efficiency and the effectiveness of proposed
algorithms, formulations, and the random grouping scheme.

(a)

(b)

(c)

(d)

Figure 2: Plots for Experiments

###  5.1 Efficiency

This section conducts numerical simulation to validate the efficiency of
proposed algorithms: Fista-pcp, Fista-locp, and Fista-licp.

For Fista-pcp and Fista-locp, we consider the most popular exclusive LASSO
(E-LASSO) formulation (Zhou et al., 2010): ${1\over 2}\|X{\bf w}-{\bf
y}\|^{2}+\lambda\|{\bf w}\|^{2}_{e}$.

We compare Fista-pcp and Fista-locp to several recent algorithms of solving
E-LASSO, including PLS-DN (Yuan and Yan, 2011), Kong’s approach (Kong et al.,
2014), and LELR (Chen et al., 2011). All algorithms are implemented in Matlab.
We try our best to tune optimization parameters in all algorithms and report
their best performance.

We first consider the nonoverlapped case. The elements in data matrix
$X\in\mathbb{R}^{400\times 4000}$ are generated from i.i.d. Gaussian
distribution $\mathcal{N}(0,1)$. The true model ${\bf
w}^{*}\in\mathbb{R}^{4000}$ has been split into $100$ disjoint groups with $4$
nonzeros in each group. All nonzeros are generated from i.i.d.
$\mathcal{N}(0,1)$. The observation vector ${\bf y}$ is generated from ${\bf
y}=X{\bf w}^{*}+0.01\times\mathcal{N}(0,1)$. $\lambda$ is set as $0.4/\|{\bf
w}^{*}\|_{1})$. We report the objective function value against the CPU time in
Figure 2a. We observe that Fista-locp is the most efficient and Fista-pcp is
the second best. This observation is not surprising, because Fista-locp and
Fista-pcp strictly guarantees the optimal convergence rate with light
computation complexity per iteration.

We then consider the overlapped case. The synthetic data is generated in the
same manner as above except that $100$ groups in ${\bf w}^{*}$ are randomly
generated and the group size has changed from $40$ to $140$ (groups are highly
overlapped). Note that the Fista-locp algorithm is not available in this case
anymore. We report the efficiency comparison of the rest algorithms in Figure
2b. We can observe that Fista-pcp algorithm outperforms other algorithms.

To see the efficiency of Fista-licp, we compare it to the general optimization
algorithm Admm (Boyd et al., 2011) (to the best of our knowledge, there is no
specific optimization algorithm for solving E-SVM). We compare two algorithms
on synthetic data with 5040 features and 720 samples. The details on how to
generate the synthetic data is introduced in Section 5.2. We plot curves of
the relative error ($\|{\bf w}^{k+1}-{\bf w}^{k}\|/\|{\bf w}^{k}\|$) against
the running time for both algorithms in Figure 2c and observe that Fista-licp
is more efficient than Admm. This observation is not surprising since the
convergence rate for Fista-licp $O(1/k^{2})$ is superior to the rate for Admm
$O(1/k)$ (He and Yuan, 2012).

###  5.2 Effectiveness

The effectiveness of the exclusive sparsity regularization for smooth loss
such as exclusive LASSO can be found in many existing literatures. We refer
readers to (Zhou et al., 2010; Kowalski and Torrésani, 2009; Chen et al.,
2011; Kong et al., 2014). This section only validates the effectiveness of the
exclusive sparsity regularization in non-smooth loss as well as the random
grouping scheme through solving the E-SVM formulation (10). We consider two
setups of E-SVM: 1) E-SVM – group information is available and 2) E-SVM(R) –
group information is unavailable using the proposed random grouping scheme.
Fista-licp is used to solve both of them. We compare E-SVM and E-SVM(R) to the
standard SVM, sparse SVM (S-SVM) (Bi et al., 2003), and Kong’s approach (Kong
et al., 2014) on both synthetic data and real data.

The synthetic data is generated as follows. The true classifier ${\bf
w}^{*}\in\mathbb{R}^{n}$ vector is randomly split into $m$ disjoint groups
$g_{1},g_{2},\cdots,g_{m}\subset\\{1,2,\cdots,n\\}$ with equal size. Each
group ${\bf w}_{g_{i}}$ only has a single nonzero element, whose value is
generated from Gaussian distribution $\mathcal{N}(0,1)$. Then we generate the
data matrix $X=[X_{+},X_{-}]\in\mathbb{R}^{n\times m}$, where $X_{+}$ and
$X_{-}$ denote $m/2$ positive class samples and $m/2$ negative class samples.
(Note that the number of samples is equal to the number of groups $m$.) We
first generate a matrix $X_{0}\in\mathbb{R}^{n\times{m\over 2}}$ with elements
generated from i.i.d. Gaussian $\mathcal{N}(0,1)$. $X_{+}$ is obtained by
$X_{+}(:,i)=X_{0}(:,i)+d{\bf w}^{*}$ for any positive sample $i$ and $X_{-}$
is obtained by $X_{-}(:,j)=X_{0}(:,j)-d{\bf w}^{*}$ for any negative sample
$j$. Here, $d$ is used to control the accuracy. We tune the value of $d$ such
that the misclassification rate using the true model ${\bf w}^{*}$ is around
$10\%$. The testing data set is generated in the same manner and has the equal
size.

For the synthetic data, we fix the feature dimension as $5040$ and choose
different values for the number of samples (groups)
$m=112,315,504,720,1008,1260,1680,2520$. The group number in E-SVM(R) is set
as $m/\log m$. All experiments using four variants of SVM formulation are
repeated for $10$ times. We report the average accuracy of testing data for
four algorithms in Figure 2d. We observe that 1) the E-SVM outperforms other
three algorithms, which is not surprising because it employs the structural
sparsity information; 2) The E-SVM(R) is slightly worse than E-SVM, but still
superior to SVM and S-SVM, which validates the effectiveness of the random
grouping scheme; and 3) The performance of SVM, E-SVM and E-SVM (R) are
comparable when the sparsity ratio is high.

Next we compare the proposed E-SVM (R) to SVM, S-SVM, and Kong’s approach
(Kong et al., 2014) (they use exclusive LASSO to select features and then
apply SVM to only selected features) on real datasets. Since the group
information is unavailable, we only use E-SVM(R) for comparison. Table 1
reports the accuracy of four algorithms using cross validation. We observe
that the proposed E-SVM(R) is overall superior to SVM, S-SVM, and Kong’s
approach. Note that the main purpose of this comparison is to validate the
random grouping scheme and shows that E-SVM can be superior on some common
real data sets under certain scenarios, rather than arguing that E-SVM can
substitute SVM and S-SVM.

Table 1: Accuracy on real datasets using SVM, S-SVM, Kong’s approach, and E-SVM(R). Real datasets we use include Computer (ISOLET (Bache and Lichman, 2013), Handwritten Digits (PCMAT (Zhao et al., 2010)), Linguistic (PCMAT (Zhao et al., 2010) and TDT2 (Cai, )), Cancer (LEU (Golub et al., 1999), ALLAML (Fodor, 1997), Colorectal (Alexandrov et al., 2009), ProstateCancer (‘JNCI 7-3-02’) (Petricoin et al., 2002) and Prostate-GE (Singh et al., 2002)) and Social Media (TwitterHealthData (Sadilek et al., 2013)). Data | #Feature | #Samples | #Flods | SVM | S-SVM | Kong | E-SVM(R)
---|---|---|---|---|---|---|---
ISOLET | 617 | 1560 | 41 | 69.59% | 67.37% | 69.64% |  69.85%
MNIST | 784 | 3119 | 6 | 95.92% | 97.90% | 97.69% |  98.11%
PCMAT | 3289 | 1943 | 31 | 64.43% | 55.05% | 64.26% |  66.21%
TDT2 | 36771 | 885 | 5 | 53.84% | 92.97% | 79.77% |  94.07%
LEU | 3571 | 72 | 5 | 83.66% | 76.02% | 83.67% |  84.71%
ALLAML | 7129 | 72 | 9 | 74.48% | 61.81% | 74.31% |  74.65%
Colorectal | 16331 | 112 | 20 | 80.17% | 63.59% |  81.40% | 81.39%
ProstateCancer | 15154 | 89 | 21 |  70.90% | 55.79% | 70.89% | 70.33%
Prostate-GE | 5966 | 102 | 21 | 64.46% | 54.62% | 67.45% |  67.65%
TwitterHealthData | 5087 | 6873 | 2 | 71.96% | 80.77% | 81.17% |  82.67%

##  6 Conclusion

This paper investigates the exclusive sparsity norm minimization problem.
Several efficient algorithms are proposed to solve two types of objectives
“smooth loss + $\|\cdot\|^{2}_{e}$” and “hinge loss (non-smooth) +
$\|\cdot\|^{2}_{e}$”. The optimal convergence rate $O(1/k^{2})$ is guaranteed
for all proposed algorithms. When the group information is not available, a
random grouping scheme is proposed to define groups. This grouping scheme is
proven to be capable of (roughly) evenly assigning true nonzeros to every
groups with high probability. Empirical studies validate the efficiency of the
proposed algorithms (Fista-pcp, Fista-locp, and Fista-licp) and the
effectiveness of the proposed E-SVM formulation and the random grouping
scheme.

## Acknowledgments

The authors would like to thank Dr. Deguang Kong at Samsung Research for
sharing data sets and help with experiments. The authors would also thank
Professor Henry Kautz and Roya Feizi at University of Rochester for sharing
the TwitterHealthData used in Table 1.

## References

  * Alexandrov et al. (2009) T. Alexandrov, J. Decker, B. Mertens, A. M. Deelder, R. A. T. P. Maass, and H. Thiele.  Biomarker discovery in maldi-tof serum protein profiles using discrete wavelet transformation.  _Bioinformatics_ , 25(5):643–649, 2009.
  * Bach (2012) F. Bach.  Structured sparsity and convex optimization.  _ICPRAM_ , 2012.
  * Bache and Lichman (2013) K. Bache and M. Lichman.  UCI machine learning repository.  2013\.  URL http://archive.ics.uci.edu/ml.
  * Balazs et al. (2013) P. Balazs, M. Doerfler, M. Kowalski, and B. Torresani.  Adapted and adaptive linear time-frequency representations: a synthesis point of view.  _Signal Processing Magazine, IEEE_ , 30(6):20–31, 2013.
  * Bayram and Akyıldız (2014) I. Bayram and Ö. D. Akyıldız.  Primal-dual algorithms for audio decomposition using mixed norms.  _Signal, Image and Video Processing_ , 8(1):95–110, 2014.
  * Beck and Teboulle (2009) A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  _SIAM Journal on Imaging Sciences_ , 2(1):183–202, 2009.
  * Bi et al. (2003) J. Bi, K. Bennett, M. Embrechts, C. Breneman, and M. Song.  Dimensionality reduction via sparse support vector machines.  _The Journal of Machine Learning Research_ , 3:1229 – 1243, 2003.
  * Boyd et al. (2011) S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends® in Machine Learning_ , 3(1):1–122, 2011.
  * Breheny and Huang (2009) P. Breheny and J. Huang.  Penalized methods for bi-level variable selection.  _Statistics and its interface_ , 2(3):369, 2009\.
  * (10) D. Cai.  Tdt2.  URL www.cad.zju.edu.cn/home/dengcai/Data/TextData.html.
  * Chen et al. (2011) X. Chen, X. Yuan, Q. Chen, S. Yan, and T.-S. Chua.  Multi-label visual classification with label exclusive context.  _ICCV_ , pages 834–841, 2011.
  * Fercoq et al. (2014) O. Fercoq, Z. Qu, P. Richtárik, and M. Takávc.  Fast distributed coordinate descent for non-strongly convex losses.  _ArXiv e-prints_ , 2014.
  * Fodor (1997) S. P. Fodor.  DNA SEQUENCING: Massively Parallel Genomics.  _Science_ , 277:393–395, 1997.
  * Golub et al. (1999) T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P. Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, et al.  Molecular classification of cancer: class discovery and class prediction by gene expression monitoring.  _science_ , 286(5439):531–537, 1999.
  * He and Yuan (2012) B. He and X. Yuan.  On the o(1/n) convergence rate of the douglas-rachford alternating direction method.  _SIAM Journal on Numerical Analysis_ , 50(2):700–709, 2012.
  * Jenatton et al. (2011) R. Jenatton, J. Y. Audibert, and F. Bach.  Structured variable selection with sparsity-inducing norms.  _Journal of Machine Learning Research_ , 12:2777–2824, 2011\.
  * Kim and Xing (2012) S. Kim and E. P. Xing.  Tree-guided group lasso for multi-response regression with structured sparsity, with an application to eqtl mapping.  _Annals of Applied Statistics_ , 6(3):1095–1117, 2012.
  * Koh et al. (2007) K. Koh, S. Kim, and S. Boyd.  An interior-point method for large-scale l1-regularized logistic regression.  _Journal of Machine learning research_ , 8(8):1519–1555, 2007.
  * Kong et al. (2014) D. Kong, R. Fujimaki, J. Liu, F. Nie, and C. Ding.  Exclusive feature learning on arbitrary structures via $\ell_{1,2}$-norm.  _NIPS_ , 2014.
  * Kowalski and Torrésani (2009) M. Kowalski and B. Torrésani.  Sparsity and persistence: mixed norms provide simple signal models with dependent coefficients.  _Signal, image and video processing_ , 3(3):251–264, 2009.
  * Kowalski et al. (2013) M. Kowalski, K. Siedenburg, and M. Dorfler.  Social sparsity! neighborhood systems enrich structured shrinkage operators.  _Signal Processing, IEEE Transactions on_ , 61(10):2498–2511, 2013.
  * Lin et al. (2014) D. Lin, J. Zhang, J. Li, H. He, H. Deng, and Y. Wang.  Integrative analysis of multiple diverse omics datasets by sparse group multitask regression.  _Frontiers in cell and developmental biology_ , 2, 2014.
  * Liu et al. (2009) J. Liu, S. Ji, and J. Ye.  Multi-task feature learning via efficient l 2, 1-norm minimization.  _UAI_ , pages 339–348, 2009.
  * Liu et al. (2013) J. Liu, L. Yuan, and J. Ye.  Guaranteed sparse recovery under linear transformation.  _ICML_ , 2013.
  * Liu et al. (2011) X. Liu, X. Yuan, S. Yan, and H. Jin.  Multi-class semi-supervised svms with positiveness exclusive regularization.  _ICCV_ , 2011.
  * Lozano and Swirszcz (2012) A. C. Lozano and G. Swirszcz.  Multi-level lasso for sparse multi-task regression.  _ICML_ , 2012.
  * Nesterov (2004) Y. Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer, 2004.
  * Nesterov (2005) Y. Nesterov.  Smooth minimization of non-smooth functions.  _Mathematical programming_ , 103(1):127–152, 2005\.
  * Nesterov (2007) Y. Nesterov.  Gradient methods for minimizing composite objective function.  _Technical Report_ , 2007.
  * Petricoin et al. (2002) E. F. Petricoin, D. K. Ornstein, C. P. Paweletz, A. Ardekani, P. S. Hackett, B. A. Hitt, A. Velassco, C. Trucco, L. Wiegand, K. Wood, et al.  Serum proteomic patterns for detection of prostate cancer.  _Journal of the National Cancer Institute_ , 94(20):1576–1578, 2002.
  * Roth (2004) V. Roth.  The generalized lasso.  _IEEE Transactions on Neural Networks_ , 15(1):16–28, 2004.
  * Sadilek et al. (2013) A. Sadilek, S. Brennan, H. Kautz, and V. Silenzio.  nemesis: Which restaurants should you avoid today?  _First AAAI Conference on Human Computation and Crowdsourcing_ , 2013\.
  * Singh et al. (2002) D. Singh, P. G. Febbo, K. Ross, D. G. Jackson, J. Manola, C. Ladd, P. Tamayo, A. A. Renshaw, A. V. D’Amico, J. P. Richie, E. S. Lander, M. Loda, P. W. Kantoff, T. R. Golub, and W. R. Sellers.  Gene expression correlates of clinical prostate cancer behavior.  _Cancer Cell_ , 1(2):203 – 209, 2002.
  * Tibshirani (1996) R. Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society. Series B_ , pages 267–288, 1996.
  * Tibshirani et al. (2005) R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight.  Sparsity and smoothness via the fused lasso.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 67(1):91–108, 2005.
  * Tropp and Wright (2010) J. A. Tropp and S. J. Wright.  Computational methods for sparse solution of linear inverse problems.  _Proceedings of the IEEE_ , 98(6), 2010.
  * Vidyasagar (2014) M. Vidyasagar.  Machine learning methods in the computational biology of cancer.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science_ , 470(2167):20140081, 2014.
  * Wang et al. (2014) X. Wang, J. Bi, S. Yu, and J. Sun.  On multiplicative multitask feature learning, 2014.
  * Wright et al. (2009) S. J. Wright, R. D. Nowak, and M. Figueiredo.  Sparse reconstruction by separable approximation.  _Signal Processing, IEEE Transactions on_ , 57(7):2479–2493, 2009.
  * Wu and Lange (2008) T. T. Wu and K. Lange.  Coordinate descent algorithms for lasso penalized regression.  _The Annals of Applied Statistics_ , pages 224–244, 2008.
  * Yuan and Lin (2006) M. Yuan and Y. Lin.  Model selection and estimation in regression with grouped variables.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 68(1):49–67, 2006.
  * Yuan and Yan (2011) X. Yuan and S. Yan.  A finite newton algorithm for non-degenerate piecewise linear systems.  _AISTAT_ , pages 841–854, 2011.
  * Zhao et al. (2010) Z. Zhao, F. Morstatter, S. Sharma, S. Alelyani, A. Anand, and H. Liu.  Advancing feature selection research.  _ASU Feature Selection Rep._ , 2010.
  * Zhou et al. (2010) Y. Zhou, R. Jin, and S. Hoi.  Exclusive lasso for multi-task feature selection.  pages 988–995, 2010.

## Supplemental Materials: Proofs

Proof to Lemma 1

###### Proof.

We have

$\displaystyle\max_{{\bf v}^{g}\in\mathbb{R}^{|g|}}~{}\langle{\bf w}_{g},{\bf
v}^{g}\rangle-{1\over 2\beta}\|{\bf v}^{g}\|^{2}_{\infty}$ $\displaystyle=$
$\displaystyle\max_{t}\max_{\|{\bf v}^{g}\|_{\infty}\leq t}~{}\langle{\bf
w}_{g},{\bf v}^{g}\rangle-{1\over 2\beta}t^{2}$ $\displaystyle=$
$\displaystyle\max_{t}~{}t\|{\bf w}_{g}\|_{1}-{1\over 2\beta}t^{2}\quad$
$\displaystyle(\text{from the fact that $\ell_{1}$ norm and $\ell_{\infty}$
norm are dual to each other.})$ $\displaystyle=$ $\displaystyle{\beta\over
2}\|{\bf w}_{g}\|_{1}^{2}.$

It completes the proof by summarizing over all $g\in\mathcal{G}$. ∎

Lemma 2 and 3 follows the sprit of projection on to the $\ell_{1}$ norm cone
and $\ell_{\infty}$ cone, which can be considered as a special case with
$\zeta=1$. The proof mainly applies fundamental results such as KKT condition
in optimization. We include their proofs for completeness.

Proof to Lemma 2

###### Proof.

Let us consider a trivial case first: $\|{\bf a}\|_{1}\leq b$. In this case,
the optimal values for ${\bf x}$ and $y$ are ${\bf a}$ and $b$ respectively.

Then let us consider the nontrivial case: $\|{\bf a}\|_{1}>b$. In this case,
it is easy to see that the optimal values ${\bf x}^{*}$ and $y^{*}$ satisfy
$\|{\bf x}^{*}\|_{1}=y^{*}$ and the element signs of ${\bf x}^{*}$ are the
same as ${\bf a}$. Therefore, to simplify the following notation and
discussion, we make an assumption without the loss of generality

${\bf a}_{1}\geq{\bf a}_{2}\geq\cdots\geq{\bf a}_{d}\geq 0.$

Based on this assumption, the problem (5) is equivalent to solving the
following problem

$\displaystyle\min_{{\bf x},y}$ $\displaystyle{1\over 2}\|{\bf x}-{\bf
a}\|^{2}+{\zeta\over 2}(y-b)^{2}$ (13) s.t. $\displaystyle{\bf{1}}^{\top}{\bf
x}=y$ $\displaystyle{\bf x}\geq{\bf 0}.$

It can be further simplified by

$\displaystyle\min_{{\bf x}}$ $\displaystyle{1\over 2}\|{\bf x}-{\bf
a}\|^{2}+{\zeta\over 2}({\bf{1}}^{\top}{\bf x}-b)^{2}$ (14) s.t.
$\displaystyle{\bf x}\geq{\bf{0}}.$

The optimal solution is defined by the KKT condition

$0\leq{\bf x}_{i}~{}\bot~{}{\bf x}_{i}-{\bf a}_{i}+\zeta({\bf{1}}^{\top}{\bf
x}-b)\geq 0\quad\forall i\in\\{1,2,\cdots,d\\}.$

We also note that if ${\bf a}_{i}\geq{\bf a}_{j}$, then ${\bf
x}^{*}_{i}\geq{\bf x}^{*}_{j}$ (otherwise we can simply swap the values of
${\bf x}^{*}_{i}$ and ${\bf x}^{*}_{j}$ to obtain a lower objective value).
Therefore, from the monotonicity assumption on ${\bf a}$, we have

${\bf x}^{*}_{1}\geq{\bf x}^{*}_{2}\geq\cdots\geq{\bf x}^{*}_{d}.$

Let $j\in\\{1,2,\cdots,d\\}$ be the watershed: ${\bf x}^{*}_{i}=0$ for $i>j$
and ${\bf x}^{*}_{i}\geq 0$ for $i\leq j$. The KKT is simplified by

$\displaystyle\forall i\leq j\quad$ $\displaystyle{\bf x}_{i}={\bf
a}_{i}-\zeta({\bf{1}}^{\top}{\bf x}-b)\geq 0$ $\displaystyle\forall i>j\quad$
$\displaystyle{\bf x}_{i}=0\quad{\bf a}_{i}-\zeta({\bf{1}}^{\top}{\bf
x}-b)\leq 0.$

Summarize all ${\bf x}^{*}_{i}$’s to obtain

$\displaystyle{\bf{1}}^{\top}{\bf x}=\left(\sum_{i=1}^{j}{\bf
a}_{i}\right)-j\zeta({\bf{1}}^{\top}{\bf x}-b)$ $\displaystyle\Rightarrow$
$\displaystyle{\bf{1}}^{\top}{\bf x}=\frac{\left(\sum_{i=1}^{j}{\bf
a}_{i}\right)+j\zeta b}{1+j\zeta}$ $\displaystyle\Rightarrow$
$\displaystyle\zeta({\bf{1}}^{\top}{\bf x}-b)=\frac{\left(\sum_{i=1}^{j}{\bf
a}_{i}\right)-b}{\zeta^{-1}+j}=:\delta_{j}.$

Then finding a point satisfying the KKT condition is equivalent to finding a
$j$ such that

$\displaystyle\forall i\leq j$ $\displaystyle{\bf x}_{i}={\bf
a}_{i}-\delta_{j}\geq 0$ (15) $\displaystyle\forall i>j$ $\displaystyle{\bf
x}_{i}=0\quad{\bf a}_{i}-\delta_{j}\leq 0.$

Due to the monotonicity, to find such “$j$”, we only need to enumerate all
possible values for $j$ such that

$\displaystyle{\bf a}_{j}-\delta_{j}$ $\displaystyle\geq 0$ (16)
$\displaystyle{\bf a}_{j+1}-\delta_{j}$ $\displaystyle\leq 0.$

As long as we find such “$j^{*}$”, we can compute the optimal values for ${\bf
x}^{*}$ from (15)

${\bf x}^{*}=\max({\bf{0}},{\bf a}-\delta_{j^{*}})$

and $y^{*}$ from $y^{*}={\bf{1}}^{\top}{\bf x}^{*}$. If we remove the
assumption, the definition of $\delta_{j}$ should be modified into

$\delta_{j}:=\frac{\left(\sum_{i=1}^{j}|{\bf
a}|^{(i)}\right)-b}{\zeta^{-1}+j},$

where $|{\bf a}|^{(i)}$ denotes the $i$th largest absolute value in ${\bf a}$.
The condition to define the optimal $j$ in (16) should be replaced by

$\displaystyle|{\bf a}|^{(j)}-\delta_{j}$ $\displaystyle\geq 0$
$\displaystyle|{\bf a}|^{(j+1)}-\delta_{j}$ $\displaystyle\leq 0.$

The optimal values for ${\bf x}^{*}$ and $y^{*}$ are given by respectively

${\bf x}^{*}=\text{sgn}({\bf a})\odot\max({\bf{0}},|{\bf
a}|-\delta_{j^{*}})\quad y^{*}=\|{\bf x}^{*}\|_{1}.$

Algorithm 2 exactly follows the procedure to find the optimal solution. It
completes the proof.333We derive this solution from the perspective of the L
one norm cone projection. The solution to (4) can also be derived from the
perspective of shrinkage operator (Kowalski et al., 2013). ∎

Proof to Lemma 3

###### Proof.

First we have that (6) is equivalent to

$\min_{y\geq 0}~{}\min_{\|{\bf x}\|_{\infty}\leq y}{1\over 2}\left(\|{\bf
x}-{\bf a}\|^{2}+\zeta(y-b)^{2}\right).$ (17)

Given $y$, the optimal value for ${\bf x}$ is

${\bf x}_{i}=\text{sgn}({\bf a}_{i})\odot\min(|{\bf a}_{i}|,y)\quad\forall i$
(18)

Replacing ${\bf x}$ in (17) by its optimal value with respect to ${\bf a}$, we
obtain

$\min_{y\geq 0}{\zeta\over 2}(y-b)^{2}+{1\over 2}\sum_{i=1}^{d}\min(y-|{\bf
a}_{i}|,0)^{2}.$ (19)

The optimality condition is

$0\leq\zeta(y-b)+\sum_{i=1}^{d}\min(y-|{\bf a}_{i}|,0)\perp y\geq 0.$

To decide the optimal value for $y$, we can first test if $y=0$ is the optimal
solution. $y=0$ is the optimal solution is equivalent to
$\zeta(0-b)+\sum_{i=1}^{d}\min(0-|{\bf a}_{i}|,0)\geq 0$. If $y=0$ is not the
optimal solution, we know that the optimal solution must be greater than $0$.
Thus, we only need to find a $y>0$ satisfying

$0=\zeta(y-b)+\sum_{i=1}^{d}\min(y-|{\bf a}_{i}|,0).$

We do not have a closed form solution to this equality due to the
$\min(\cdot,\cdot)$ function. To remove this part, we sort $\\{|{\bf
a}_{i}|~{}i=1,\cdots d\\}$ and consider different ranges for $y$:

$(0,|{\bf a}|^{(1)}],~{}(|{\bf a}|^{(1)},|{\bf a}|^{(2)}],~{}\cdots,~{}(|{\bf
a}|^{(d-1)},~{}|{\bf a}|^{(d)}],~{}(|{\bf a}|^{(d)},~{}\infty)$

where $|{\bf a}|^{(i)}$ denotes the $i$th smallest element of ${\bf a}$ in the
absolute value sense. For the range $(|{\bf a}|^{(d)},~{}\infty)$, we only
need to check if

$y=b\in(|{\bf a}|^{(d)},~{}\infty)$

If yes, we find the optimal solution for $y^{*}$. Otherwise, we check the
remaining ranges. For the range $(0,|{\bf a}|^{(1)}]$, we only need to check
if

$y={1\over\zeta+d}\left(\zeta b+\sum_{i=1}^{d}|{\bf
a}|^{(i)}\right)\in(0,|{\bf a}|^{(1)}].$

If yes, we find the optimal solution for $y^{*}$. For the general range
$(|{\bf a}|^{(k)},~{}|{\bf a}|^{(k+1)}]$, we only need to check if

$y={1\over\zeta+d-k}\left(\zeta b+\sum_{i=k+1}^{d}|{\bf
a}|^{(i)}\right)\in(|{\bf a}|^{(k)},~{}|{\bf a}|^{(k+1)}].$

When the optimal value for $y^{*}$ is determined, one easily recover the
optimal value for ${\bf x}^{*}$ by (18). Algorithm 3 exactly follows the
procedure above. It completes the proof. ∎

Proofs to Theorem 4

###### Proof.

Denote $y_{i}X_{i}$ by $Z_{i}$($i\in\\{1,2,\cdots,t\\}$). To deal with the
first non-smooth term “$\max(1-y_{i}X_{i}^{\top}{\bf w},0)$”, we rewrite (10)
by introducing a vector ${\boldsymbol{\xi}}$ in the following:

$\displaystyle\min_{{\bf w},{\boldsymbol{\xi}}\geq 0}$
$\displaystyle{\bf{1}}^{\top}{\boldsymbol{\xi}}+{\alpha\over 2}\|{\bf
w}\|^{2}+{\beta\over 2}\|{\bf w}\|_{e}^{2}\quad\quad$ (20) s.t. $\displaystyle
1-Z_{i}^{\top}{\bf w}\leq{\boldsymbol{\xi}}_{i}\quad$ $\displaystyle\forall i$

We introduce a dual variable ${\bf u}\in\mathbb{R}^{t}$ to move the constraint
“$1-Z_{i}^{\top}{\bf w}\leq{\boldsymbol{\xi}}_{i}$” to the objective and apply
Lemma 1 to rewrite the exclusive sparsity regularizer:

$\displaystyle\min_{{\bf w},~{}{\boldsymbol{\xi}}\geq 0}\max_{{\bf u}\geq
0,{\bf v}^{g}\in\mathbb{R}^{|g|},g\in\mathcal{G}}$
$\displaystyle{\bf{1}}^{\top}{\boldsymbol{\xi}}+{\alpha\over 2}\|{\bf
w}\|^{2}+\langle{\bf u},{\bf{1}}-Z^{\top}{\bf w}-{\boldsymbol{\xi}}\rangle+$
$\displaystyle\sum_{g\in\mathcal{G}}\langle{\bf v}^{g},{\bf
w}_{g}\rangle-{1\over 2\beta}\|{\bf v}^{g}\|_{\infty}^{2}$

which is equivalent to (20). From the definition of $\overline{{\bf v}_{g}}$,
we have $\sum_{g\in\mathcal{G}}\langle{\bf v}^{g},{\bf
w}_{g}\rangle=\left\langle\sum_{g\in\mathcal{G}}\overline{{\bf v}^{g}},{\bf
w}\right\rangle$.

From strong duality, we safely swap $\min$ and $\max$:

$\displaystyle\max_{{\bf u}\geq 0,{\bf
v}^{g}\in\mathbb{R}^{|g|},g\in\mathcal{G}}\min_{{\bf
w},~{}{\boldsymbol{\xi}}\geq 0}{\bf{1}}^{\top}{\boldsymbol{\xi}}+{\alpha\over
2}\|{\bf w}\|^{2}+\langle{\bf u},{\bf{1}}-Z^{\top}{\bf
w}-{\boldsymbol{\xi}}\rangle+$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left\langle\sum_{g\in\mathcal{G}}\overline{{\bf
v}^{g}},{\bf w}\right\rangle-{1\over 2\beta}\sum_{g\in\mathcal{G}}\|{\bf
v}^{g}\|_{\infty}^{2}$ $\displaystyle=$ $\displaystyle\max_{{\bf u}\geq 0,{\bf
v}^{g}\in\mathbb{R}^{|g|},g\in\mathcal{G}}\min_{{\boldsymbol{\xi}}\geq
0}\quad-{1\over 2\alpha}\left\|Z{\bf u}-\sum_{g\in\mathcal{G}}\overline{{\bf
v}^{g}}\right\|^{2}+\langle{\boldsymbol{\xi}},1-{\bf u}\rangle+$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad{\bf{1}}^{\top}{\bf
u}-{1\over 2\beta}\sum_{g\in\mathcal{G}}\|{\bf v}^{g}\|_{\infty}^{2}$
$\displaystyle=$ $\displaystyle\max_{{\bf u}\geq 0,{\bf
v}^{g}\in\mathbb{R}^{|g|},g\in\mathcal{G}}~{}\begin{cases}-{1\over
2\alpha}\left\|Z{\bf u}-\sum_{g\in\mathcal{G}}\overline{{\bf
v}^{g}}\right\|^{2}+\\\ {\bf{1}}^{\top}{\bf u}-{1\over
2\beta}\sum_{g\in\mathcal{G}}\|{\bf v}^{g}\|_{\infty}^{2},&\text{if }{\bf
u}\leq 1\\\ -\infty,&\text{otherwise}\end{cases}$ (21)

where the second equality is obtained by letting

$\quad{\bf w}={1\over\alpha}\left(Z{\bf
u}-\sum_{g\in\mathcal{G}}\overline{{\bf v}^{g}}\right).$ (22)

Eq. (21) essentially defines the dual problem of (10)

$\displaystyle\min_{{\bf u},{\bf v}^{g}~{}g\in\mathcal{G}}\quad$
$\displaystyle\underbrace{{1\over 2\alpha}\left\|Z{\bf
u}-\sum_{g\in\mathcal{G}}\overline{{\bf
v}^{g}}\right\|^{2}-{\bf{1}}^{\top}{\bf u}}_{=:F([{\bf u};\\{{\bf
v}^{g}\\}_{g\in\mathcal{G}}])}+$ $\displaystyle\underbrace{{1\over
2\beta}\sum_{g\in\mathcal{G}}\|{\bf
v}^{g}\|_{\infty}^{2}+{\bf{I}}_{{\bf{0}}\leq{\bf u}\leq{\bf{1}}}({\bf
u})}_{=:H([{\bf u};\\{{\bf v}^{g}\\}_{g\in\mathcal{G}}])}.$ (23)

It completes the proof. ∎

Proof to Theorem 5

###### Proof.

We use $\Omega$ to denote the index set of useful features and
$\Omega_{j}\subseteq g_{j}$ to denote the index set of useful features
assigned to group $j$, where $j\in\\{1,2,\cdots,m\\}$. In most cases, the
Uniform type model is difficult to analyze due to the dependence among
variables. A common trick is to use the Bernoulli model to approximate it and
then bridge the difference between the Uniform model and Bernoulli model. The
Bernoulli model performs the following experiment: for any group $g_{j}$, each
index in $g_{j}$ corresponds to a useful feature with probability $p$ and a
useless feature with probability $(1-p)$. The Bernoulli model admits the
independence among all indices, thus is much easier to derive the probability
bound. Denote by $\mathbb{P}_{\text{Unif}(k)}$ and
$\mathbb{P}_{\text{Ber}(p)}$ probabilities calculated under the uniform and
Bernoulli models. For example,
$\mathbb{P}_{\text{Unif}(s)}\left(\max_{j\in\\{1,2,\cdots,m\\}}|\Omega_{j}|\leq
2{s\over m}\right)$ is the probability of the number of useful features
assigned into any group is less than $2s/m$ by using the uniformly randomly
assignment.

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{n}\\{\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)~{}\Bigg{|}~{}|\Omega|=k\right)$
$\displaystyle\quad\quad\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)\\}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{s-1}\\{\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)~{}\Bigg{|}~{}|\Omega|=k\right)$
$\displaystyle\quad\quad\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)\\}~{}+$
$\displaystyle\sum_{k=s}^{n}\\{\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)~{}\Bigg{|}~{}|\Omega|=k\right)$
$\displaystyle\quad\quad\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)\\}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\text{Ber}(p)}(|\Omega|<s)~{}+$
$\displaystyle\sum_{k=s}^{n}\\{\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)~{}\Bigg{|}~{}|\Omega|=k\right)$
$\displaystyle\quad\quad\quad\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)\\}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{\text{Ber}(p)}(|\Omega|<s)~{}+$
$\displaystyle\sum_{k=s}^{n}\\{\mathbb{P}_{\text{Unif}(k)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right)\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)\\}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\text{Ber}(p)}(|\Omega|<s)~{}+~{}\mathbb{P}_{\text{Unif}(s)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right)$

where the last equality uses the fact

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)~{}\Bigg{|}~{}|\Omega|=k\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}_{\text{Unif}(k)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right)$

and the last inequality uses the monotonicity

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right)$ $\displaystyle\geq$
$\displaystyle\mathbb{P}_{\text{Unif}(s+1)}\left(\max_{j}|\Omega_{j}|<{s\over
m}(1+t)\right).$

It follows that

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)+\mathbb{P}_{\text{Ber}(p)}(|\Omega|<s).$ (24)

Bernstein’s inequality states that for a sum of uniformly bounded independent
random variables with $Y_{i}-\mathbb{E}Y_{i}\leq c$, we have

$\mathbb{P}\left(\sum_{i=1}^{k}(Y_{i}-\mathbb{E}Y_{i})\geq\delta\right)\leq\exp\left\\{-{\delta^{2}\over
2k\sigma^{2}+2c\delta/3}\right\\}\quad$

and

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{k}(Y_{i}-\mathbb{E}Y_{i})\leq-\delta\right)\leq\exp\left\\{-{\delta^{2}\over
2k\sigma^{2}+2c\delta/3}\right\\}$ (25)

hold for any $\delta>0$, where $\text{Var}(Y_{i})=\sigma^{2}$. Let $Y_{i}$’s
follow i.i.d. Bernoulli distribution with parameter $p$. Take $p={s\over
n}(1+\epsilon)$ where $t>\epsilon>0$. From $\mathbb{E}(Y_{i})=p$, $c=1-p$ and
$\text{Var}(Y_{i})=(1-p)p$ for $i\in\\{1,\cdots,n/m\\}$, we have

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle\leq$
$\displaystyle\sum_{j}\mathbb{P}_{\text{Ber}(p)}\left(|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle=$
$\displaystyle\sum_{j}\mathbb{P}_{\text{Ber}(p)}\left(|\Omega_{j}|\geq{s\over
m}(1+\epsilon)+{s\over m}(t-\epsilon)\right)$ $\displaystyle=$
$\displaystyle\sum_{j}\mathbb{P}\left(\sum_{i=1}^{n/m}(Y_{i}-\mathbb{E}Y_{i})\geq{s\over
m}(t-\epsilon)\right)$ $\displaystyle\leq$
$\displaystyle\sum_{j}\exp\left\\{-{(t-\epsilon)^{2}s^{2}/m^{2}\over
2(1-p)pn/m+2(1-p)(t-\epsilon)s/(3m)}\right\\}$ $\displaystyle\leq$
$\displaystyle\exp\left\\{-{(t-\epsilon)^{2}s/m\over
2(1+\epsilon)+2(t-\epsilon)/3}+\log m\right\\}.$

Taking $\epsilon=0.1t\leq 1$, we have

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle\leq$
$\displaystyle\exp\left\\{-0.08t^{2}s/m+\log m\right\\}.$ (26)

From Bernstein’s inequality (25), we can similarly have

$\displaystyle\mathbb{P}_{\text{Ber}(p)}(|\Omega|<s)$
$\displaystyle\leq\exp\\{-\epsilon^{2}s/2(1+{3\over 4}\epsilon)\\}$
$\displaystyle\leq\exp\\{-0.001t^{2}s\\}.$ (27)

Plugging (26) and (27) into (24), we obtain

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle\leq$
$\displaystyle\exp\left\\{-0.001t^{2}s\right\\}+\exp\left\\{-0.08{t^{2}s\over
m}+\log m\right\\}$ (28)

Next we turn to prove
$\mathbb{P}_{\text{Unif}(s)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)$ holds with high probability. Choose $p={s\over m}(1-\epsilon)$
where $0<\epsilon=0.1t$.

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)$ $\displaystyle\geq$
$\displaystyle\sum_{k=0}^{s}\mathbb{P}_{\text{Ber}(p)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)~{}\Bigg{|}~{}|\Omega|=k\right)\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{s}\mathbb{P}_{\text{Unif}(k)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)\mathbb{P}_{\text{Ber}(p)}(|\Omega|=k)$ $\displaystyle\geq$
$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)\mathbb{P}_{\text{Ber}(p)}(|\Omega|\leq s).$

If follows that

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)$ $\displaystyle\leq$
$\displaystyle\frac{\mathbb{P}_{\text{Ber}(p)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)}{\mathbb{P}_{\text{Ber}(p)}(|\Omega|\leq s)}$ (29)

Since $s\geq np$, we have

$\displaystyle\mathbb{P}_{\text{Ber}(p)}(|\Omega|\leq s)\geq 0.5.$ (30)

From Bernstein’s inequality, we can similarly have

$\displaystyle\mathbb{P}_{\text{Ber}(p)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)\leq\exp\left\\{-0.2t^{2}s/m+\log m\right\\}.$ (31)

Combine (29), (30), and (31) to obtain

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)\leq 2\exp\left\\{-0.08t^{2}s/m+\log m\right\\}.$ (32)

We can prove the final result by combining (28) and (32):

$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\frac{\max_{j}|\Omega_{j}|}{\min_{j}|\Omega_{j}|}\geq\frac{1+t}{1-t}\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\min_{j}|\Omega_{j}|\leq{s\over
m}(1-t)\right)+$
$\displaystyle\mathbb{P}_{\text{Unif}(s)}\left(\max_{j}|\Omega_{j}|\geq{s\over
m}(1+t)\right)$ $\displaystyle\leq$ $\displaystyle
3\exp\left\\{-0.08t^{2}s/m+\log m\right\\}+\exp\left\\{-0.001t^{2}s\right\\}$

If we have $s=O(t^{-2}m\log m)$, the probability in the right hand side of
(29) converges to zero, which indicates that the probability on the left hand
side converges to $1$. It completes the proof. ∎