Learning Sparse Group Models Through Boolean Relaxation
Authors: Yijie Wang
Yuan Zhou
Xiaoqing Huang
Kun Huang
Jie Zhang
Jianzhu Ma
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Structured sparisity
Convex relaxation
Cardinality-constrained program
Small sample size

Abstract: We introduce an efficient algorithmic framework for learning sparse group models formulated as the natural convex relaxation of a cardinality-constrained program with Boolean variables. We provide theoretical techniques to characterize the equivalent condition when the relaxation achieves the exact integral optimal solution, as well as a rounding algorithm to produce a feasible integral solution once the optimal relaxation solution is fractional. We demonstrate the power of our equivalent condition by applying it to two ensembles of random problem instances that are challenging and popularly used in literature and prove that our method achieves exactness with overwhelming probability and nearly optimal sample complexity. Empirically, we use synthetic datasets to demonstrate that our proposed method significantly outperforms the state-of-the-art group sparse learning models in terms of individual and group support recovery when the number of samples is small. Furthermore, we show the out-performance of our method in cancer drug response prediction.

Published as a conference paper at ICLR 2023
LEARNING SPARSE GROUP MODELS BOOLEAN RELAXATION
THROUGH
Yijie Wang'* Yuan Zhou?* Xiaoqing Huang² Kun Huang?
Jie Zhang*
Jianzhu Ma
Computer Science Department, Indiana University Bloomington
2 Yau Mathematical Sciences Center and Department of Mathematical Sciences, Tsinghua University $ Department of Biostatistics & Health Data Science, Indiana University
4 'Department Medical Molecular Genetics, Indiana University
" "Institute for Al Industry Research, Tsinghua University ma maajiann janzhu) Bttiinguuaa.a.n.... wdw.ghuuaeeddeccmm... Equal contribution)
yi jwang@ iu edu (yuan-zhon zhou,
ABSTRACT
We introduce an efficient algorithmic framework for learning sparse group models formulated the natural convex relaxation of cardinality-constral with Boolean variables. We provide theoretical techniques to characterize the equiv- alent condition when the relaxation achieves the exact integral optimal solution, as well as rounding algorithm to produce a feasible integral solution once the opti- mal relaxation solution fractional. We demonstrate the power of our equivalent condition by applying it to two ensembles of random problem instances that are challenging and popularly used literature and prove that our method achieves the exactness with overwhelming probability and the nearly optimal sample complexity. Empirically, we use synthetic datasets to demonstrate that our proposed method significantly outperforms the state-of-the-ar group sparse learning models in terms individual and group support recovery when the number of samples is small. Furthermore, show the put-performance of our method in cancer drug response prediction.
program
INTRODUCTION
Sparsity one of the most important concepts in statistical machine learning, which strongly connects to the data & computational efficiency, generalizability, and interpretability of the model. Traditional sparse estimation tasks aim at selecting sparse features at the individual level [ibshirami (1996); NNegabban et al. (0122) However, in many real-world scenarios, structural properties among the individual features are assumed thanks to prior knowledge, and leveraging these structures may improve both model accuracy and learning efficiency Gramfort & Kowalski (2099); Kim & Xing
(012)).
In this paper, we focus on learning the sparse group models for intersection-closee group sparsity, where groups of variables are either selected or discarded together. The general task of learning the sparse group models has been investigated quite a lot in literature, where most of the prior studies are based on the structured sparsity-inducin norm regularization Friedman et al. (2010); Huang al. (201T): Zhao et al. (2009); (Simon et al. (2013). which stems from Lasso Tibshirani (1996), the traditional and popular technique for a sparse estimate at the individual feature level. As reviewed in Bach et al. (2012); Jenatton et al. (201T). the structured
norm is quite general and
can encode structural assumptions such as trees Kim & Xing (2012) Liu & Ye (201)), contiguous groups Rapaport et al. (2008). directed-acyclic-eee graiieggrasss/sas Zheng et al. (2018). and general overlapping
groups Yuan et al. (2011).
Another type of approach for learning the sparse group models is to view the task as a cardinality- constrained program, where the constraint set encodes the group structures as well as restricts the
number of groups of variables being selected. Baldassarre et al. [Baldassarre et al. (2013) investigate the projection onto such curdinality-constrained set. However, due to the combinatorial nature of the projection, directly applying the projected gradient descent with the projection Baldassarre al.) (2013) to solve general learning problems with typical loss functions might not have good results Kyrillidis et al. (2013). Recent work Pilanci et al. (2015) studies the Boolean relaxation of the learning problem with cardinality constraints on the individual variables. This work Pilanci et al.) special case of sparse group models, where each group contains only
(2015) can be viewed one variable. Both the original work of Pilanci et al. (2015) and several follow-up papers Bertsimas & Parys| (2020); Bertsimas et al. (2020) show that the Boolean relaxation empirically outperforms the sparse estimation methods using caadse-nnducig norms (Lasso Tibshirani (1996) and elastic net /ou & Hastie (2005)), especially when the sample size is small and the feature dimension is

---

Published as a conference paper at ICLR 2023
large. However, the results in Pilanci et al. (2015) cannot be applied to the sparse group models with
arbitrary group structures.
To fill the gap. in this paper, we study the sparse group models through purdinality-constrain program. We first propose the Boolean relaxation for sparse group models. We further establish an analytical and algorithmic framework for our Boolean relaxation which includes theorem stating the equivalent condition for the relaxation to achieve the exactness (i.e., the optimal integral solution) and a rounding scheme that produces an integral solution when the optimal relaxation solution is fractional. We demonstrate the power of our equivalent condition theorem by applying it to two ensembles of random problem instances that are challenging and popularly used in literature and proving that our Boolean relaxation achieves the exactness with high probability and the nearly optimal sample complexity. Our contributions are threefold:
1) We propose a novel framework that uses constraints to induce intersection-closed group spar- sity. Baldassarre et al [Baldassarre et al. (2013) investigate the projection on the group sparsity constraints. But our framework extends to any convex loss function with the group sparsity constraints.
2) We prove our framework is tight and can achieve the exactness with high probability and the nearly optimal sample complexity for two ensembles of random problem instances. This result is inspired by Pilanci et al. (2015) but our derivations and proofs are not straightforward extensions (e.g., due to the group structure, we need to analyze more complex feature- group matrices, prove new matrix concentration properties, and carefully choose different regularization parameters).
3) Empirically, we perform extensive experiments to demonstrate that our framework significantly outperforms the state-of-the-art methods when the sample size is small on simulated datasets. Furthermore, we show the out-performance of our framework in cancer drug response prediction.
1.1 RELATED WORKS
Convex programming relaxations and their rounding techniques have been widely used for approx- imating many combinatorial optimization problems that are computationally intractable (see, e.g.. Williamson & Shmoys (201T)) The specific algorithmic technique in this work is inspired by the Boolean relaxation method introduced in PPilanci et al. (2015) for learning sparsity at the individual feature level. However, the additional group structure in our problem raises new algorithmic chal- lenges, and both our Boolean relaxation formulation and its theoretical analysis (e-g.. the equivalent condition for the exactness) are different from their counterparts Pilanci et al. (2015).
As mentioned before, sparse estimation using structured
norms were thoroughly studied for learning structured sparsity under different structure assumptions motivated by various
practical scenarios Friedman et al. (2010): Huang et al. (201T); Zhao et al, (2009); et al. (2013); ;
Tibshirani (1996); Bach et al. (2012); Kim & Xingl 2) Liu & Ye (2010))) Rapaport al. (0088)
Zheng et al. (2018); Yuan et al. (2011 10111 Jenatton et al. (201)) 1). I). However, none of these algorithms provides the rigorous theoretical techniques as in this work to verify whether the algorithm has produced the exact optimal solution. Also, as we will show in the experiments section, our proposed method outperforms these algorithms on both synthetic and real-world datasets. In our experiments, we also compare with the elastic net method Zou & Hastie (2005), which can only control the sparsity at the individual feature level. There exist another family of structured sparsity-inducet eet al. (2009) that aim to model the union-closed families of supports, where the support of the solution is union of groups. Different from our proposed models, which the support of the solution is the intersection of the complements of some of groups considered (intersection-closel group et al. (2009).
Yuan
norms Dacob)
Another approach is to learn sparse group models by introducing the penalty functions for the constraints and applying the convex relaxation to them. Bach Bach (2010) investigate to design norms from submodular set-functions. Halabi et al. EEl Halabi & Cevher (2015): Halabi et al. (2018) study to induce group sparsity using tight convex relaxation of linear matrix inequalities and combinatorial penalties. Note that these works use convex regularizers constraints. Halabi et al. El Halabi & Cevher 2015);: Halabi et al. (018)) study general equivalent conditions to characterize the tightness of their relaxations while our theoretical results works for specific distributions where their general conditions cannot be easily verified. We use different analytical frameworks and thus the theoretical results cannot be directly compared.
induce group sparsity while we use
2

---

Published as a conference paper at ICLR 2023
2 BOOLEAN RELAXATION FOR SPARSE GROUP MODEL
The organization of this section is as follows. In section we introduce the original problem and its exact boolean representation. In section 2.2 we propose the boolean relaxed program and provide the condition under which the relaxed program is guaranteed to have an integer solution and hence be tight. In section 2.3 we propose the rounding strategy if the relaxed program does not generate integral solutions.
2.1 SPARSE GROUP MODEL AND ITS FORMULATION VIA BOOLEAN CONSTRAINTS
We consider a learning problem for a collection of n. samples {( yi) E R x ) and define the design matrix as X E RTxd where a. E Rd is the i-th row of X. This setup is flexible to model various problems including binary classification (where the label space y {-1, 1, +1}) and regression problems (where the label space y = RR. For a linear model x + w xr our goal is to learn a sparse weight vector w E Ed whose support encodes certain structures reflecting the relationships among the features which are usually defined by the prior knowledge. More formally, we need to solve the following mathematical program.
P = min e
F(w): E A=1
((w)==Eft f(w 2;: v.) + 2 2
(1)
Here, the loss function f(:-) measures the prediction emror by our linear model, where the common choices include the squared loss for least-squares regression, the log loss for the logistic regression, and the hinge loss for the support vector machine. The regularization term 2/1lu/1 in makes sure that the objective function is strongly convex and therefore has unique optimal solution w" R Finally, the constraint set @ encodes the sparsity requirements for both individual features and groups of features. We use gi denote the of the indices of features in the i-th group and for any vector w E IRd, we use W'g to denote the vector containing all entries of w corresponding to the indices in gr- We further assume that we have b predefined groups and then the cardinality constraint set θ can be written
+ E IRd
| S k Σ [|
o lbo 0] s h
where || llo denotes the lo norm and [-]] denotes the indicator variable that takes the value 1 when the corresponding condition holds and 0 otherwise. The first constraint enforces the number of contributing features be less than k. and the second constraint makes sure the number of groups that contain those selected features is less than h.
We also remark that the structured sparsity constraints defined by in equation is very flexible. First, the || llo < k constraint imposes the feature-level sparsity requirement and encompasses the unstructured sparsity model (as investigated in Pilanci et al. (2015)) as a special case. Second, the h covers the needs for structured
group-level sparsity constraint is introduced by I[ Wgg In sparsity arising from many practical scenarios such as neuroimaging Gramfort & Kowalski (2009); Xi et al. (2009). genomic analysis Rapaport et al. (2008) Kim & Xing ( and wavelet-based denoising Zhao et al. (2009); Huang et al. (2011). The groups { 1 can be arbitrary sets of the features and may model not only non-overlapping structured sparsity when gi (gg, = 0, Vi. but also various overlapping patterns including the contiguous pattern, the block pattern, and the 2012)tJenattonn
hicrarchical pattern as reviewed in Bach et al. (2012); Jenatton et al.) (201T). Note that the first term in equation 2 can be absorbed into the second term, which however will not have the sparsity control at the individual level.
Note that the structured sparse group learning problem Pa defined in equation I involves only real variables. In the following theorem, we show that the problem can be reformulated as convex program with additional Boolean variables and constraints, which will naturally lead to the Boolean relaxation algorithm in the later sections.
Theorem 2.1 (Exact representation with Boolean constraints). Suppose that for each y E V, the function + f(;;2) () is closed and convex. The Legendre- Fenchel conjugate of f is f*( suPIeR {st - f(tt: y)}. Then for any p > 0, the structured sparse learning problem p in equation 1 can be represented by the following Boolean convex program
p
min max
Σ (vun))
(3)
(1, VER"
2p
H(a)
3

---

Published as a conference paper at ICLR 2023
where D(u) diag(u) is diagonal matrix with R its diagonal, and I' is the constraint set for u and u, defined as the follows,
(u, 2)
Σ
U S ki
Σ S ==1
Us 2g. Vieg E (0,1)" ZE (0, 13
The proof of Theorem 2.1 can be found in the supplementary materials Section A In the theorem statement, w is a vector of the Boolean indicators for the supports of the individual features and is also vector of the Boolean indicators for the supports of the group features. H (u) in equation is convex in u because it is the maximum of a family of functions that are linear with u. However, the whole program is still computationally difficult due to the Boolean constraints I
{0, 13d and E {0, 1 In the next subsection, we will relax these Boolean constraints which leads to a convex program that can efficiently solved for many popular loss functions f.
2.2
CONVEX PROGRAM THROUGH BOOLEAN RELAXATION AND THEORETICAL. CONDITIONS FOR EXACTNESS
We apply interval relaxation to both Boolean vector variables and and obtain the Boolean relaxation for P as follows.
1 - XD(U)X 8- - E(sso
PBR
min max (u,2)ER
(4)
2p
where
Ω
(u, z)
Σ Ui S k, Σ 1=1
E S 2j, E 9j. u u 10,
E E [0, 11
PBR is a convex program and can be solved by the sub-gradient-basse optimization algorithm Nes terov (2009) if the inner maximization problem can be solved efficiently. general. PBR can also be converted into minimax optimization problem and solved by methods in [in et (2020). We now investigate when PER achieves the exact solution of p*, under the assumption that the groups are non-overlapping. Note that PBR is a relaxation of P* as defined in equation 3 The relaxation is exact if and only if the optimal solution in PBR also happens to be integral and therefore feasible in P' The following theorem (proved in the supplementary materials Section B.1 characterizes the equivalent condition for the exactness.
Theorem 2.2. Suppose that each feature belongs to only one group and the optimal integral solution (û, 2) for P as defined in equation 3sleccts selects k features and h groups, then the optimal solution of
PAR, also recovers (ū, 2) if and only if there exists non-negatin non-negative ds and Aao such that
n
E arg max VER"
LU XD(()X 2p
Σ (way)) i=1
(5)
1. For each group such that
2, 1, it holds that
Vp E gi, úp = - (X 8)2 > N and
(6)
Vy gi, up = 0 (X, i)2 S dt.
2. For each group i such that & 1, it holds that
Σ
((x) Ax) > An-
(8)
PEgr,ap=1
3. For each group i such that 2, = 0,
Σ max
(X]
24. 03 s An
(9)
PEg:
Here, Xp denotes the p-th column of the design matrix X.
The special case of least-squares regression. Among all candidate choices of the loss function f. the squared loss f(t; y) = { y)² 2 for least-squares regression is the most important and popular one with many real- world applications Kim et al. (2007); Nguyen Rocke 2002): Boulesteix & [Strmmerr (200)) & Lambert- Lacrrix- (2004), and the corresponding Legendre- Fenchel conjugate
becomes ('({:) 3 sy. In this special case of the structured sparse learning for least-squares
4

---

Published as a conference paper at ICLR 2023
regression, the relaxed convex program PER becomes the following form.
c(u)==y' (HXD(U)X* +1)
LBR
min (u.z)en
y
(10)
The detailed derivation of equation I0 can be found in the supplementary materials Section
B.2 We
let denote the support of the unique optimal solution w² to the original Boolean program
L min {G(u)}
(11)
(u.2)ET
and define the n matrix M by M := (In + p 5)
(12)
Now are ready to apply Theorem 2.2 to the squared loss function and derive the sufficient and necessary condition for the exactness LBR (assuming non-overlapping groups), as follows.
Corollary 2.3. Suppose that each feature belongs only one group and the optimal integral solution
(û, 2) selects i features and h groups, then LBR = I. if and only if there exist non-negative As and Ano such that
1. For each group i such that 2; = 1, holds that
Vp E 9r. up 1 (X,) My)² > dv and
(13)
Vp E gr. up = (X, My)² S Av-
(14)
2. For each group i such that 2, 1, it holds that
Σ
((X)) My)² Nx)) > dn.
(15)
pE
3. For each group i such that 2, = 0,
m My) - A2, 03 S An-
(16)
PE.:
The proof of Corollary | can be found in the supplementary materials Section B.3
Corollary 2.3
creates an analysis framework for the exactness of the Boolean relaxation LBR where one only has to construct two scalars Å and \ and verify the conditions in equation [4] equation 15] and equation 16 In Section B] we will follow this framework to theoretically prove the exactness of LBR for several classes of problem instances that are popularly studied in the literature, demonstrating the power of
Corollary 2.3
2.3 RANDOMIZED ROUNDING
When the Boolean relaxation is not exact (i.e., the optimal solution of the Boolean relaxation turns out to be fractional), we describe in this section a rounding method to recover an integral solution. We will apply randomized rounding, a state-of-the--e technique for converting fractional solutions to integer solutions with provable approximation guarantees Pilanci et al. (2015), ) to the solution of the relaxed problem PER- Given the fractional solution ū E 00 1 and & E [0, 1]6, our goal is to recover feasible Boolean solution
{0, 1]d and E (0, 1)ah For simplicity of exposition, show the rounding scheme for the case when each feature belongs to exactly one group. However, the algorithm could be easily generalized the cases of overlapping groups In our rounding algorithm, we first generate a feasible Boolean solution at the group level E (0, 13a. For each group j. we independently set 2j according to the following probability distribution:
(17) Once the groups are decided, the is set to 0 for each feature i that belongs to non-selected group. For each selected group 9₁ and for each feature that belongs to the group, we independently set u; according to the following probability distribution:
Pr[z,
žj and Pr[z, = 0]
žj-
Pr(u: 1] it and Pr[u: = 0]
u. žj
(18)
2
is easy to verify that the Boolean solution generated by the method above matches the frac- tional solution in the sense of expectation B[z] E and Elu) ü. and furthermore their ex-
pected to norms are given by E [[]=]||]] = Pr =1 Σラ < h, and IE [[[u[[o]]
EL (Pr(ū, 1, 2, 1] + Pr[u, 1, 0)) Ei S. With these expectation bounds in hand, applying standard concentration inequalities, we can show that if we let 9 max, 1g,| be the size of the largest group, for any ó (0, 1/3), with probability
exp(-S((k255) ((((((((222(bG")) ((G) we have that ||=||o S (1 8)h and ||u||o I (1 + k) This means that when the group sizes are relatively small, our randomized rounding scheme produces nearly optimal solution with high probability. Finally, once have obtained
at least (1 exp(S((-h6")
5

---

Published as a conference paper at ICLR 2023
the integral solution u, the weight vector for the original problem equation | can be computed by
w: := arg win (()(
Value guarantees for least-squares regression. For least-squares loss, we are also able to establish theoretical guarantees for the value (i.e., H (u) as defined in equation 3) of our rounding scheme. Without loss of generality, let us assume the columns of the design matrix X are normalized, i.e., ||Xplla for p f1, d} and ||yl| = 1. We have the following theorem and its proof is in the supplementary materials Section C
Lei (ū, 2) be the optimal solution to the relaxed program. Let T. be the number of fractional entries in E and let Tu be the number of fractional entries in ú. Let (u, be the integral solution returned by our rounding scheme. For any 6 > O. with probability (1 - 6). it holds that
Theorem 2.4.
((u) - P* 5o (Vr. [Vr:log(r=/8%) + /rr Vrwlog(ra//))
3. THEORETICAL GUARANTEES OF LBR ON ENSEMBLES OF RANDOM INSTANCES
In this section, we apply Corollary 2.3 to prove our relaxed program is tight and can achieves the exactness with high probability and the nearly optimal sample complexity for two ensembles of random problem instances.
We focus on the case of least-squares regression and its corresponding relaxation LBR. We will introduce two ensembles of random problem instances and theoretically analyze the performance of our LBR on them. The first random ensemble has been popularly used in literature to evaluate the L Sparse Group Lasso algorithms Simon et al. (2013); |Friedman al. 2010). The second random ensemble is designed by us. It is more challenging compared to the first ensemble as there is more than one "optimal" weight vector w at the feature level. However, the algorithm has figure out the one with the most group sparsity. For both ensembles, we will show that our LBR will successfully recover both the group and feature sparsity with overwhelming probability and almost optimal sample complexity (i.e., n the number of observations).
3.1 R RANDOM ENSEMBLE
The first class of random instances can be generated as follows (illustrated in Fig. Ta).. We first generate the random design matrix X R. with i.i.d. AV 1) entries. The d features are divided into b groups where the size of each group is d/b. We will construct the regression weight vector w E id such that the first h groups will have non-zero coefficients and the coefficients in the rest of the groups are O. The number of non-zero coefficients in the j-th group (for j E (1.2....,h) is ky and we have that Σラ= kj k. where t the total number of non-zero coefficients in w. For each group j E {1, ........,,, we arbitrarily choose kū features in the group and randomly set the corresponding coefficient in w to be "E" Finally, y = Xw + 6, where the noise vector E I has i.idd N (0) entries. The goal is identify the support of w and the corresponding coefficients. The following theorem provides the theoretical guarantee that given a sufficient amount of observa- tions, LBR recovers the individual and group level sparsity for this random ensemble.
Theorem 3.1. Consider the random instance described above with parameters (n, d, k. 7, b, h) and
let y Xw c be the observed response vector. Suppose that 7 > 1. Let p 1/2+6 (8 E (0, 1 1/2)). With probability at least (1 - dexpp(-S 12(n2 /(>2k)) d exp( 52 12-5 ))) the relaxed program LBR admits the optimal solution u" and 2" where u. = 1 [w; + and 2; 1lj E f1,2,..., hh]]-
We remark that the regularization parameter p is set to 1/2+5 in our theorem, while in contrast, p was set to vn in Pilanci et al. (2015) for the sparse learning problem without group constraints. In fact, if we are only looking for (1 o(1) success probability, we can set ò to be as large (close to 1/2) as possible. For example, if set 8 1/2 log log
The success probability is (1 - o(1) as long as n2/ (1 log n) = (1), which means that we only need n = ((k/n22) (og(k//2)) to achieve the (1 o(1)) success probability, which almost matches the information theoretic lower bound Wainwright (007) up to the logarithmic factor.
log n
3.2 RANDOM ENSEMBLE II
We now describe the another class of random instances which is more challenging due to the multiple candidate regression vectors (illustrated Fig. aa). We first generate random design matrix X xxd with two candidate k-sparse cross-fit regression vectors (1), (2) E Rd, such that both

---

We next specifically describe how we generate w()), w(() and design the groups. For any vector w E IR* with no non-zero entries, we let the first l entries of w(1) filled by w and the rest filled by O; we also let the (k + 1)-th to the 2k-th entries of wi(2) filled by w and the rest filled O. We let each Published as a conference paper at ICLR 2023
vectors lead to the same expected response (i.e., Xw()) = ()) The response vector is generated by X Xuw(1) + 6 where E IR has i..d. (0, entries. The d feature dimensions are divided into b groups of the same size d/b (for simplicity we assume that d is a multiple of b). The groups are arranged in a way so that the non-zero coefficients of w:()) span h groups (where h 1 d/b 2 k), and the non-zero coefficients of 22(2) span Çh groups (5 > 1). Given (X, y) (after randomly permuting the indices of the coordinates and the groups), the goal is to identify the support of w:(1) since is sparser at the group level.
of the first groups contain k/ h non-zero identical coordinates of w(1), and let each of the next Çh groups contain k/ (çhh)) con-zero identical coordinates of w(2). We finally fill the groups with the coordinates numbered from (2k: 1) d that each group has the same size d/b.
We next describe how we generate the design matrix X. We first generate a random orthogonal matrix Q such that Qu W. This can be done by first fixing an arbitrary orthogonal matrix with Tw
w as
its first column (i.c., letting P = IIIi0 1 31, , 3x-1), generating a random (k - 1) x (k - 1)
orthogonal matrix Q', and finally letting Q- P. diag(1. PT. We then generate the matrices X1 1 and X3 E [ 22) with i.i.d. (0, 1) entries. Let X2 = -21 Since Q orthogonal, is easy to see that in the the marginal distribution of X2, each entry is also i.i.d. N/ 1). We finally let X = [X1. Xs]. One can verify that X (w) = X1W w as well as X ( = XiQw= = Xyw. w. For the theoretical guarantee of LBR on our second random ensemble, we have the following theorem.
be random instance described above with parameters (n, d, R, b, h. w. Suppose there exists & >> 0 such that S |was <//²g for all f1.2...., k). Also suppose that y 2 L. Let p n2/2+6 (6 (0, 1/2)). For large enough constant Ç. with probability at least (1 - the relaxed program LBR admits the optimal solution u² and 2n where u, 1[ (1) # 0] and
Theorem 3.2. Let X = [X1, X2, X3] and y (Io
/22))///))))))))))>)))))))))(/ - dexp( [22mnn (((2-26))),
- E g w features included in the group.
(1) + 0]. Here, we use to denote both the index of a group and the set of the
We first remark that the smallest possible value of { for the theorem to hold can be made arbitrarily
close to 1 (but greater than 1). This relaxation would only affect the constant coefficients in the (2())
notations in the success probability bound. Also, similarly to the remark in Section 3.1 we may
set 8- = 1/2 log log n The success probability is (1 - o(1)) as long as m²g/(??" log = w().
log
Since <² is usually ((1/k), again, we only need n w(kk/?? log(k/?²)) to achieve the (1 (1))
success probability, almost matching the information theoretic lower bound Wainwright 2007) up to the logarithmic factor.
4 EXPERIMENTS
In this section, we perform extensive experiments to investigate the effectiveness of the proposed sparse group models under the setting of éG-regularized least-squares regression specified in equa- tion IO We use both simulated datasets (non-overlapping groups) introduced in Sections 3.1 and 3.2 and real-world application (overlapping groups) in cancer to evaluate the performance. To access the performance on simulated data, we compute the recovery accuracy of both individual supports and group supports, which are defined as Ar)) and Ao(w), respectively:
Ar(w): = {i= w, o O, wrue + O}l
Ac(w)= == |15 Wa; * 0, w o 0H
(19)
Hi: woruu # 0}}
Ki : wutrue # 0}|
Here w is the ith element of the ground-truth vector true and w w
the weight vector for group 9j- We apply the projected Quasi-Newton method Schmidt et al. (2099) to efficiently solve equation TO The details related to the optimization could be found in supplementary materials Section P If the solution of equation [0] is not integral, we use the rounding scheme proposed
in section 2.3 For the non-overlapping setting, we compare the performance of our method with
Sparse Group Lasso (SGL) Simon et al. (2013), Sparse G-group cover (SGCover) El Halabi & Cevher (2015), , and SGL (group level sparsity using foe norm and individual level sparsity using & norm); for the overlapping group setting, we compare with (SGL-Overlap) Yuan et al. (00T)) and
SGCover El Halabi & Cevher (2015). We also compare our method with Elastic Net (ENet) Zou &
7

---

Published as a conference paper at ICLR 2023
(+)
(b)
(c)
noncem weights
Accurecy Indloddeal Sungort Recovers
Acourary of Group Support Recousy
0.95
0.9
1groups
0.85
0.6
0.8
0.5
0.75
0.4
0.7
0.3
0.2
SGL*
Proposed
SGCover
0.65
0.6
SGL
Proposed
0.3
ENet
0.55
S0Cover
06
200
400
600
ROO
1000 1200
0.5
0
200
400 600
800
1000 1200
Xa +
Sample stee
(d)
'00
Proposed, 600
(e)
0500
SGL,
n=600
SGL,, 600
(0)
160
SGCover, n=0
Out of Sample MSE
Out of Sample MSE
Jmdd
of Semple MSE
W 350
8000
hw5
140
3 130
7300
20
6 100
7000
90
80
40
80
0500
20
400
600
80
1000
40
60
80
100
20
40
60
60
100
Figure 1: (a) Illustration of the data generation process for Random Ensemble (b) A2 n. increases (c) Ac as increases, We average results over datascts and the ervor bar means 95% confidence interval. (d)(g) Estimate is and h by out-of-sample of MSE by different methods. The black vertical line indicates the true k. The results averaged over 10 datasets and the error bar means standard deviation.
Hastie (2005) which is the saate-of-the-ad method for detecting sparse features at the individual level. All experiments run on computer with cores 3.7GHz Intel CPU and 32 GB RAM.
4.1 SIMULATION EVALUATION OF RANDOM ENSEMBLE I
We first consider the simulation setting described in Section 3.1 in which we use d' = 1000, b 10. = 50 (k; = 10, Vi E {1, 2..,, 5)), h = 5, and 7 = 2.5 to generate the simulation data whose signal-noise-ratio (SNR) is around 4. We evaluate the performance of all the methods on recovering the ground truth weight vector w true with A: = 50 contributing features distributed in h = 5 groups. Feature selection with given support sizes 1: and h: We first consider the case when k and h are given and equal to the ground-truth for all methods, while all other hyper-pann peerrpprrmtters are selected by cross- validaaoi........... It is hard to let SGL. SGCover, and SGL to select exact &o individual features and h groups of features so we indirectly control l and by sweeping the regularization parameters. For cases where these methods do not yield exact l individual features and h groups of features, we rank their results and get the top A individual features and h groups of features instead. The same procedure was adopted to ENet to select & features. In this setting, we do not need to worry about false discovery rate (FDR), because it is complementary to the accuracy defined in equation [9] As shown in Fig. (bb) and (c), A, and Ag of all competing methods converge to 1 with the increasing sample size n. However, our proposed method converges the fastest among all the methods, indicating its effectiveness on recovering the structured sparsity when the sample size is small. We further conduct similar experiments with larger f and show the results in the supplementary materials Section G Based on these results, we could confirm that our proposed method outperforms conventional methods in selecting contributing features at both the individual level and group level.
Estimation of support sizes 1 and h: In the real-world scenario, we might not know the number of contributing features and groups. Typically, they could be selected by cross- gross-validation based on the oft-of-sample mean square error (MSE). Motivated by this practical need, in this study, we also investigate whether the competing methods could accurately recover the ground truth k and h based on the out-of-sample of MSE, As shown in Fig. dd) only our proposed method is able to provide the smallest MSE at h 5. In addition, for the number of contributing feature k., only our method achieves the smallest MSE around the number of features k = 50.
Interpreting the superior performance of our method. All the competing methods are norm-based and they rely on the regularization factor before the penalty norm to adjust to the support size (group number and feature number) requirements. However, this connection is not explicit as our Boolean relaxation where we directly require that > u; S le and Σ 2 S h. Together with our randomized rounding scheme, our Boolean relaxation method might be at an advantageous position to utilize the prior knowledge on support sizes and/or recover the support sizes from the -aampee MSE.
4.2 SIMULATION EVALUATION OF RANDOM ENSEMBLE II
Next, consider more challenging simulated data generated from the procedure introduced in Section 3.2 We set d = 500, & = 80, h = 10, Ç = 4, and y = 0.1 as described in Section As shown in Fig. aa)), both (1) and (2) are "optimal" for the linear regression problem. However, the
8

---

Published as a conference paper at ICLR 2023
lccurscy of indidial Support Recoveyy
0.9
SCL Propoigi
Retovvrry
0.9
(PI
08
0.7
0.7
0.6
Group
0.-
0.4
04
0.3
SGI
Proposed
ENst SGCover
1.1
0.
SGL
-ooond Pinss the some expected resporse
Ago
30.0x
100
300
5.00
700
900
1100
100
300
500
700
600
11.00
Figure 2: (a) Illustration of the data generation process for Random Ensomble II (b) Ay as n increases. (c) Ag as increases. We average results over 100 datasets the error means 95% confidence interval.
supports of w((1) are in h 10 groups but the supports of (2() are in Çh 40 groups. The goal is to test whether each method can recover the solution w((), which is more sparse on the group level. We control the parameters of each method to make select & = 80 features in / = 10 groups. As shown in Fig. (b) and (c), the recovery accuracy (Ag and Ay) of the proposed method rapidly converges to I and 0.93 when more training samples are provided. Surprisingly, the recovery accuracy of all the rest of the competing methods converge very slowly. Note that here do not need to consider false discovery rate (FDR) because each method selects exact & features in h groups, therefore, FDR is complementary the accuracy. Overall, under the setting of Random Ensemble II, the performance improvement of our method over the-state-of-an algorithms is significant in terms of both recovery accuracy.
4.3 CANCER DRUG RESPONSE PREDICTION
We further adapt our model and algorithm on real-world application to predict the drug response. The goal of the task is to find the essential genes and pathways that are responsible for the ineffectiveness of cancer therapy. For this task, we chose l2 réggeallrd least-square regression model to predict the continuous value of drug response.
Table 1: Result comparison for IMATNIB.
We collect drug response data from the Cancer Therapeutics Response Por- tal (CTRP) v2 and the Genomics of Drug Sensitivity in Cancer (GDSC)
Method
d.).d.)
M...d.)
Out-of-sample MSE +93%C1
Proposed
46
32.64 2.2
SGI-Overlap
(5.4)
19 (0:5)
46,913.77
ENet
60 (8.2)
18 (2.3)
39.6 4.2
database /Seashore-Ludlow et al. (2015); Yang et (2013) with 684 chemotherapy
SGCover
(10.5)
13 (1.7)
55.4
and targeted therapy drugs. For each drug, we create separate machine learning task to predict the drug response from the expression value of each gene for different tumor samples. In total, we include 1,225 tumor samples and use the gene expression value of 2.369 genes. We focus on the signal transduction pathways which are mined and collected by the Reactome database Jassal et al.. (2020). We only consider pathways that contain more than 10 genes and less than 80 genes. We collect 207 pathways (gene groups), in which the average number of genes each group is 28.9. The gene expression data are extracted from CCLE Barretina et al. (2012). For each drug (machine learning task), we hold 20% of the samples as the test set and used the remaining samples as training and validation set. For each competing method, hyper-paramenn based on the out-of-sample square error MSE on the validation set. Here we only show the performance of the drug IMATNIB
standard cross-validation
determine the
representative and put the performance of other drugs in the supplementary materials Section | Table [ iillstrates the estimation of k and h and the out-of-sample MSE on the test set for drug IMATNIB with 10 bootstrap samples. We do not compare with SGLx because the SpaSM package Sjöstrand et al. (2018) we used to solve SGL cannot handle overlapping groups. We find that our proposed method achieves the smallest oft-lee MSE well as selects the smallest number of genes and pathways. More importantly, as shown in supplementary materials Table [53] the selected pathways are all well associated with the drug response and functional mechanisms of IMATNIB in different types of tumor cells supported by rich literature. We also make predictions for other drugs and show the results in Table, SS4
CONCLUSION
In this paper, we propose novel convex framework for learning structured sparsity. We provide theoretical tools verify the exactness of the solution of the relaxation, and rounding algorithm to produce the feasible integral solution when the relaxation solution is fractional. For the case of ceast-squares loss, we perform extensive experiments to demonstrate the effectiveness of the proposed framework.

---

Published as a conference paper at ICLR 2023
REFERENCES
Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569 579, 2002.
Francis Bach. Structured sparsity-inducing norms through submodular functions. In NIPS 2010: Twenty-Fourth Annual Conference on Neural Information Processing Systems, pp. NIPS, Vancou- ver, Canada, 2010. URL https: htpp::///all aachaa..rcee. arch ves -owerteeeeeee.e.ee wtt.:/ttess..aaaa001011.1
Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Structured Sparsity through Convex Optimization. Statistical Science, 27(4) November 2012. ISSN 0883- 4237. doi: 10.1214/12-sts3 URL http:: 20t........///.1.221122------1--
Luca Baldassarre, Nirav Bhan, Volkan Cevher, Anastasios Kyrillidis, and Siddhartha Satpathi. Group- sparse model selection: Hardness and relaxations. arXiv preprint arXiv: 1303.3207, 2013.
Barretina, G. Caponigro, N. Stransky, Venkatesan, A. Margolin, Kim, C. J. Wilson, J. Lehár, G. V. Kryukov, D. Sonkin, A. Reddy, M. Liu, L. Murray, M. F. Berger, J. E. Monahan, P. Morais, Meltzer, A. Korejwa, Jané- Valbuena, F. A. Mapa, Thibault, E. Bric-Furlong,
Raman, A. Shipway, I. H. Engels, J. Cheng, G. K. Yu, J. Yu, P. Aspesi, M. de Silva, K. Jagtap, M. D. Jones,
L. Wang, C. Hatton, E. Palescandolo, S. Gupta, S. Mahan, C. Sougnez, R. C. Onofrio, Liefeld, L. MacConaill, W. Winckler, M. Reich, N. Li. J. P. Mesirov, S. B. Gabriel, G. Getz, K. Ardlie, V. Chan, V. E. Myer, B. L. Weber, J. Porter, M. Warmuth, P. Finan, J. L. Harris, M. Meyerson, T. R. Golub, M. P. Morrissey, W. R. Sellers, R. Schlegel, and I.. A. Garraway. The Cancer Cell Line Encyclopedia enables predictive modelling of anticancer drug sensitivity. Nature, 483(7391): 603-607, Mar 2012.
Dimitris Bertsimas and Bart Van Parys. Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. The Annals of Statistics, 48(1):300 323, 2020. doi: 2012244/1-AAOS804 htthttts::/
Dimitris Bertsimas, Jean Pauphilet, and Bart Van Parys. Sparse Regression: Scalable Algorithms and Empirical Performance. Statistical Science, 35(4):555 - 578, 2020. doi: 10.1214/1--STS70.
URL http:::/doo..gg///// wtt.:////.......1.11111 STS701
A. L. Boulesteix and K. Strimmer. Partial least squares: a versatile tool for the analysis of high- dimensional genomic data. Brief Bioinform, 8(1):32 44, Jan 2007.
B. S. Braun and K. Shannon. Targeting Ras in myeloid leukemias. Clin Cancer Res, 14(8):2249-222 Apr 2008.
S. C. Chen, T. T. Liao, and M. H. Yang. Emerging roles of epitheliial-messnnhymmall transition in hematological malignancies. Biomed Sci, 25(1):37, Apr 2018.
Y. J. Chung, T. M. Kim, D. W. Kim, H. Namkoong, H. K. Kim, S. A. Ha, S. Kim, M. Shin, J. H. Kim, Y. J. Lee, H. M. Kang, and J. W. Kim. Gene expression signatures associated with the resistance imatinib. Leukemia, 20(9):1542-14 --5515500,500 Sep 2006.
A. M. Coluccia, A. Vacca, M. Duñach, L. Mologni, S. Redaelli, V. H. Bustos, D. Benati, L. A. Pinna, and C. Gambacorti- Sitbaacorrti-aasrinnii Ber-Abl stabilizes beta-catenin in chronic myeloid leukemia through its tyrosine phosphorylation. EMBO J, (665):1456-1466 Mar 2007.
S. Corrêa, R. Binato, B. Du Rocher, M. T. Mastelo-Brance L. Pizzatti, and E. Abdelhay. Wnt/b- catenin pathway regulates ABCBI transcription in chronic myeloid leukemia. BMC Cancer, 12: 303, Jul 2012.
Kenneth Davidson and Stanislaw Szarek. Local operator theory, random matrices and banach spaces. Handbook of the geometry Banach spaces, 1(317-366):31,, 2001.
Damek Davis. Lecture notes for mathematical programming. 2020.
10

---

Published as a conference paper at ICLR 2023
Marwa EI Halabi and Volkan Cevher. A totally unimodular view of structured sparsity. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Eighteenth International Con- ference Artificial Intelligence and Statisties, volume 38 of Proceedings of Machine Learn- ing Research, pp. 223-231, San Diego, California, USA, 09-12 May 2015. PMLR. URL
ngs m httpaa/............e..... www.ppesss//////
abi html
Gersende Fort and Sophie Lambert-laccoix, Classificattinn using partial least squares with penalized logistic regression. Bioinformatics, 210)):1004-1111,, 2004. ISSN 1367-4803. doi: 10.1093 bioinformatics/biill 14. ut//hhttpps//oa...cro///00.00000
J. Friedman, T. Hastie, and R. Tibshirani. A note the group lasso and sparse group lasso, 2010.
Alexandre Gramfort and Matthieu Kowalski. Improving m/ceg source localization with an inter- condition sparse prior. In 2009 JEEE International Symposium Biomedical Imaging: From Nano to Macro, pp. 141-144, 2009. doi: 10. 109//SBB
J. Gu, J. R. Ryu, and A. M. Pendergast. Abl tyrosine kinases in T-cell signaling. Immunol Rev, 228 (1):170-183, Mar 2009.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL hEtps://wwa gur com
Marwa El Halabi, Francis Bach, and Volkan Cevher. Combinatorial Penalties: Which structures are preserved by convex relaxations? In AISTATS 2018 22nd International Conference on Artificial Intelligence and Statistics, Canary Islands, Spain, April 2018. URL https://hhl
trchives-ouvertee
frrhal-l1eeeee 662151
C. H. Heldin. Targeting the PDGF signaling pathway in tumor treatment. Cell Commun Signal, 11: 97, Dec 2013.
T. C. Hoang. T. K. Bui, Т. Taguchi, T. Watanabe, and Y. Sato. All-trans retinoic acid inhibits KIT activity and induces apoptosis in gastrointestinal stromal tumor GIST-TI cell line by affecting on the expression of survivin and Bax protein. / Exp Clin Cancer Res, 29:165, Dec 2010.
F. Huang, L. Zhang, D. Wu, X. Y. Yuan, Y. H. Yu, X. L. Zhao, F. P. Chen, and H. Zeng. PTEN regulates BCRP/ABCG2 and the side population through the PI3K/Akt pathway in chronic myeloid leukemia. PLoS One, 9())288898, 2014.
Junzhou Huang, Tong Zhang, and Dimitris Metaxas. Learning with structured sparsity. Journal of Machine Learning Research, 12(103):3371-3412,, 2011. URL httt:t//:// wwg.:operss....o.o..
v12/ 11bll1bbb. html
Y. Huang, E. O. Comiskey, R. S. Dupree, S. Li, A. J. Koleske, and K. Burkhardt. The c-Abl tyrosine kinase regulates actin remodeling at the immune synapse. Blood, 112(1):111-- 1111119119991111 Jul 2008.
Laurent Jacob, Guillaume Obozinski, and Jean-Philippe Vert. Group lasso with overlap and graph lasso. In Proceedings of the 26th Annual International Conference Machine Learning ICML '09. ACM Press, 2009, doi: 10.1145/15337741555333 1553374 1553431
httphtttp///.o.... 1145/
B. Jassal, L. Matthews, G. Viteri, C. Gong, P. Lorente, A. Fabregat, K. Sidiropoulos, Cook, M. Gillespie, R. Haw, F. Loney, B. May, M. Milacic, K. Rothfels, C. Sevilla, V. Shamovsky, S. Shorser, T. Varusai, J. Weiser, G. Wu, L. Stein, H. Hermjakob, and P. D E'stachio. The reactome pathway knowledgebase. Nucleic Acids Res, 484D1)):488-D5033 01 2020.
Rodolphe Jenatton, Jean-Yves Yves Audibert, and Francis Bach. Structured variable selection with sparsity- inducing norms. 2009. doi: 10.4850/ARXIV0000.5555 URL htllttts//a/xxv.orrt
0904. 3523
Rodolphe Jenatton, Jean- Yves Audibert, and Francis Bach. Struetured Variable Selection with Yearsity-Inducingg Norms. Journal of Machine Learning Research, 12:2777-2822 2011. URL https: inria... ff.ff/inns 00377732

---

Published as a conference paper at ICLR 2023
J. Kim, D. G. Bates, I. Postlethwaite, P. Heslop- Harrison, and K. H. Cho. Least-squares methods for identifying biochemical regulatory networks from noisy measurements. BMC Bioinformatics, 8:8, Jan 2007.
Seyoung Kim and Eric P. Xing. Tree-guided group lasso for multi-response regression with struc- tured sparsity, with an application to equi mapping. The Annals of Applied Statistics, 6(3), Sep 2012. ISSN 1932-6157. doi: 10.1214/12-a0a5444 URL /xx http:///t...ii...//.0..11.11.... 1214/ 12-A0A5549
Anastasios Kyrillidis, Luca Baldassarre, Marwa El Halabi, Quoc Tran-Dinh, and Volkan Cevher. Structured sparsity: Discrete and convex approaches. CoRR, abs/1507.05367, 2015. URL
pett://arxixy orgg hwrg/abs/// /100/ abs/1507.05367
E. Leo, M. Mancini, M. Aluigi, S. Luatti, F. Castagnetti, N. Testoni, S. Soverini, M. A. Santucci, and reduction of beta catenin antagonist Chibby1 in chronic
G. Martinelli. WCR-ABLI-assochee myeloid leukemia. PLoS One, 8(12) 1425, 2013.
L.. Li, D. K. Blumenthal, T. Masaki, C. M. Terry, and A. K. Cheung. Differential effects imatinib on PDGF-induced proliferation and PDGF receptor signaling in human arterial and venous smooth muscle cells. J Cell Biochem, 99(6):153--166 Dec 2006.
Tianyi Lin, Chi Jin, and Michael. I. Jordan. Near-optimal algorithms for minimax optimization, 2020.
Jun Liu and Jieping Ye. Moreau-Yosida regularization for grouped tree structure learn- ing. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Asso- ciates, Inc., 2010. URL https:: neurips wtt.:/pp.......ppeeeeeeee.e cctppapee///10//1eeee.e./ d4 d490d7b45/ (ttp//4/7729990003333333 w2w.0aa000ee111see11.eeaea Papez pdf
C. J. Malavaki, A. E. Roussidis, C. Gialeli, D. Kletsas, T. Tsegenidis, A. D. Theocharis, G. N. Tzanakakis, and N. K. Karamanos. Imatinib as a key inhibitor of the platelet-derived growth factor receptor mediated expression of cell surface heparan sulfate proteoglycans and functional properties of breast cancer cells. FEBS J. 280 (80010)2247722483 May 2013.
Sahand N. Negahban, Pradeep Ravikumar, Martin J. Wainwright, and Bin Yu. Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers. Statistical Science, 27(4):538 557, 2012. doi: 10.1214/1--SS5400 URL
1214/12 STS400
Yurii Nesterov. Primal-dus subgradient methods for convex problems. Mathematical Programmingg 120(1):221-259, 2009. doi: 10. 1011007/1100070000--144xxx URL
Danh V. Nguyen and David M. Rocke. Tumor classification by partial least squares using microarray
gene expression data. Bioinformatics. 18(1):39-50, 01 2002. ISSN 1367-4803, doi: 10.1093/
1aanformatics/1811.33 URL https://ddet htt::://doo..ooo htt.:t/ee/.aa..rrr//.o//////oonn
39
C. Nishioka, T. Ikezue, Yang, K. Udaka, and A. Yokoyama. Imatinib causes epigenetic alterations of PTEN gene via upregulation of DNA methyltransferases and polycomb group proteins. Blood Cancer J, 1(12)ee4, Dec 2011.
Roberto Oliveira et al. Sums of random hermitian matrices and an inequality by Rudelson. Electronic Communications Probability, 15:203-212, 2010.
C. Peng, Y. Chen, Z. Yang, H. Zhang, L. Osterby, A. G. Rosmarin, and S. Li. PTEN is tumor suppressor in CML stem cells and BCR-ABL-induced leukemias in mice. Blood, 115(3))626 635, Jan 2010.
Mert Pilanci, Martin J Wainwright, and Laurent El Ghaoui. Sparse learning via boolean relaxations. Mathematical Programming, 151(1);63-87, 2015.
F. Rapaport, E. Barillot, and P. Vert. Classification of arrayCGH data using fused SVM. Bioinfor- matics, 24(13):335--38,, Jul 2008.
12

---

Published as a conference paper at ICLR 2023
Mark Schmidt, Ewout van den Berg, Michael Friedlander, and Kevin Murphy. Optimizing costly functions with simple constraints: A limited-menan projected quasi-newton algorithm. David Dyk and Max Welling (eds.), Proceedings of the Twelth International Conference Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pp. 456-463, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16-18 Apr 2009. PMLR. URL
http://proceediie/ wtt.://s....pp.....p.....mme schmidt htmmmmlm.mmmmmmmmmm...mmmmmmm
m.r
B. Seashore-Ludlow, M. G. Rees, J. H. Cheah, M. Cokol, E. V. Price, M. E. Coletti, V. Jones, N. Bodycombe, C. K. Soule, J. Gould, B. Alexander, A. Li, P. Montgomery, M. J. Wawer, N. Kuru, D. Kotz, C. S. Hon, B. Munoz, Liefeld, V. Daněfk, A. Bittker, M. Palmer, J. E. Bradner, A. F. Shamji, P. A. Clemons, and S. L. Schreiber. Harnessing Connectivity in Large-Scale Small-Molecule Sensitivity Dataset. Cancer Discov, 5(11):121-- Nov 2015.
Noah Simon, Jerome Friedman, Trevor Hastie, and Rob Tibshirani. A sparse-group lasso. Journal of Computational and Graphical Staristics, 2013.
Karl Sjöstrand, Line Harder Clemmensen, Rasmus Larsen, Gudmundur Einarsson, and Bjamne Ersbøll. Spasm: A matlab toolbox for sparse statistical modeling. Journal of Statistical Software, 84(10), 2018. doi: 10. 1..18677jsss.0044... v004. URL nittss://do .or./oorgr/... 10.1111..1117.111 /s8 v084. i10
R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society (Series B), 58:267-288. 1996.
Martin Wainwright. information-theoree bounds on sparsity recovery in the high-dimensions and noisy setting. In 2007 IEFE International Symposium on Information Theory, pp. 961-965. IEEE, 2007.
David Williamson and David Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
Yongxin Xi, Uri Hasson, Peter J Ramadge, and Zhen Xiang. Boosting with spatial reg- ularization. In Y. Bengio, D. Schuurmans, Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Asso- ciates, Inc., 2009. URL htttps::/proceeeiiimit. www.ipesup.... wweurips.ccpppper///eeeee wttpppppee//0///1eee..e E2217062e 9a387799993978 2dtea33911dcaa222e222222
Paper. pdf
W. Yang, J. Soares, Greninger, Edelman, H. Lightfoot, S. Forbes, N. Bindal, D. Beare, J. A. Smith, I. R. Thompson, S. Ramaswamy, P. A. Futreal, D. A. Haber, M. R. Stratton, C. Benes, U. McDermott, and M. Garnett. Genomies of Drug Sensitivity in Cancer (GDSC): a resource for therapeutic biomarker discovery in cancer cells. Nucleic Acids Res, 41(Dttabese issue):D955-961, Jan 2013.
Lei Yuan, Jun Liu, and Jieping Ye. Efficient methods for overlapping group lasso. In Shawe-Taylor, R. Zemel, Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL htttps://proceednggs.t. neurips cc httppppp///21//11ee.
H. Zhang, Y. Wang, H. Yang, Z. Huang. X. Wang, and W. Feng. TCF7 knockdown in- hibits the imatinib resistance of chronic myeloid leukemia K562/G01 cells by neutralizing the Wwtbbcaaeein/TCCF//AN transporter signaling axis. Oncol Rep, 45(2):557-566, Feb 2021.
Peng Zhao, Guilherme Rocha, and Bin Yu. The composite absolute penalties family for grouped and hierarchical variable selection. The Annals of Statistiess 37(6A)33668 3497, 2009. doi:
10.1214407-A05584, URL (tttht::: /ttddoi.oogg////// 1214/07-A05584
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with tears: Continuous optimization for structure learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc,, 2018 URL / wwwp:nnnnn.suuuispp cc/
N.
13

---

Published as a conference paper at ICLR 2023
L. Zhou, N. An, R. C. Haydon, Q. Zhou, H. Cheng, Y. Peng, W. Jiang, H. H. Luu, P. Vanichakarn, Szatkowski, J. Y. Park, B. Breyer, and T. C. He. Tyrosine kinase inhibitor STI-571/Gleevec down-regulates the beta-catenin signaling activity. Cancer Lett, 193(2)161-170, Apr 2003.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society, Series B, 67:301-320, 2005.
14

---

Published as a conference paper at ICLR 2023
Supplementary Materials
A PROOF OF THEOREM 2.1
ProofThoorem Theorem 2.7 Let un E (0. indicate whether the i-th feature is selected and Vgg be a vector
containing th, Dý- We then define D(u) diag(u) and (4ug;) diag(1gg Considering the change of variable w = D(u)e, we find the original problem equation is equivalent to
P
min D(u)ullo D(Wa, )m
Σ f(w D(u)ag + 2 D
(20)
=0 h
We further introduce 2, E {0, 13 to indicate whether the group of features gj selected and obtain the following equivalent formulation
p
min D(w)wlll S D(ua, Way $
f(w" D(u)any)) pull
(21)
E 4j $
We further split w and u and then equation
21 becomes
P min (L WERS
min
f(w f( D(u)anu)) + 2
(22)
where
d
r
(u,
2)
U4
< K,
h, 24 Vi 93 We (0,1)) EE 13,
1=1
22 achieves the same objective function value of equation at the same unique optimal solution w It remains to prove the inner minimization is equivalent
is easy to verify that equation
min
Iww D(u)a
5 plll
2p T. XD(u)X
(vi ye)
vER"
(23)
Replacing f by its Legendre- Fenchel conjugate f*, we have
1
min max wERd ef
D(u)z; vs (v. : v.)
(24)
2
Under the stated assumptions, strong duality must hold and therefore minimum and maximum can be exchanged.
1
max min VER WER
w D(u)a - (vs : m. + b
(25)
The objective function is strongly convex with respect to w. Hence, we can obtain the unique minimizer w Em D(u)a,u, Substituting w* yields equation 23
B PROOFS AND DEVIATIONS FOR THE CONVEX FORMULATION
B. PROOF THEOREM 2.2
To prove Theorem 2.2 let us first provide the sufficient and necessary conditions for PBR to have integral solutions in the following Lemma.
Lemma B.I. Suppose that each feature belongs to exactly one group. Then suppose that the integral solution (û, 2) of equation selects exactly l. features and h groups. This solution is also the optimal
solution of the relaxed program PER and only if there exist non-negative {Su, du, 20 poppedd
(Ne, S1, de, 20 S Ixpea Nv. and Ap. such that
E arg max
Σ f im1
(26)
BER"
2p
15

---

Published as a conference paper at ICLR 2023
A1 Au,20 d (Xp 0)2
Aup
vp g6:
(27)
13151 >2120 + An= = Σ Auy
Vi E [b];
(28)
PEg:
A1 0,
vp Up 0;
(29)
Auz20 0,
Vp Up 1;
(30)
11 = 0,
Vi: & = 0;
(31)
A2220 = 0,
Ví: & = 1;
(32)
SapSa O,
Vp Up < 24
(33)
To prove Lemma B.1 we need to use the following two theorems.
Theorem B.2 Davis 2020).. Suppose I is a local minimizer of f Rd + R on a closed convex set X' S Rd If f is differentiable at E. it holds that
-V(()) E (T)
(34)
Theorem B.3 (Davis 20200). Let A E m and let B RR. Consider the polyhedron Q(A, B) {z|Ar I B}. Suppose x Q(A, 3), then the normal cone æ is (2(A,)(()) {A yly mn such that y 2 and y (B Ar) = 0}.
Proof of Lemma B.I
PBR
PBR
min max
XD(u)X v Σ (wn
(35)
VE
2p
F(u,z)
where Ω (uu,,, ((u,,)]E, Sk: S 2i of (0, 1]4; = (0,1]9 is the feasible
for 2u, By Theorem B.2 know (ū, 2) is optimal if and only if the following inclusion holds:
VF(a, 2) E NV((ū, 2),
(36)
where N2 (ū, 2) is the normal cone (ú, 2). Regarding the Left-Hand-Side of equation 36 by standard calculation, we have that d,, F(i)
-(X, 8)² (0 is defined in equation 26) and 0z F(2) = 0. Therefore,
(X 0)
(X. 6)2
(X 6)² 0
VF(0,
(37)
0
Regarding the Hand--ide of equation 36 we obtain the normal cone Na 2) using The- orem B.3 Specifically, the feasible set Ω is a polyhedron that can be presented by 9(A,b) b)
i
A
< B
where the A matrix and 3 vector are constructed as follows.
16

---

Published as a conference paper at ICLR 2023
Jesture block; d columns
group block: b columns
0
1
1
0
1
O
d2
x
1
I
0d
O
(38)
21
82
1
A'
:
9
Here, A' is the feature-gros group relation matrix where for each feature group relation 9s, there is row in A' where the p-th entry in the feature block is 1, the i-th entry the group block is 1, and all the rest entries are O. According to Theorem
B.3 we know the normal cone Nn 2)
Na(A (û, 2) = A A A (R20)=: T (1 (D-A)
á =
where e denotes the number of 0).
constraints (i.e., the row dimension of A). We identify the entries dual parameter corresponding to the constraint up S 1 for each feature p; Xu, denotes the dual parameter corresponding the constraint up 0 for each feature p; A denotes the dual parameter corresponding to the constraint E, Uj S k; λ2,5i denotes the dual parameter corresponding to the constraint 2; < for each group 2=,20 denotes the dual parameter corresponding to the constraint & 2 O for each group i; A denotes the dual parameter corresponding the constraint Σ, 2 S h; Sup denotes the dual parameter corresponding to the constraint Up S for each feature p and group 9: such that p E g:- Finally, conclude that the equivalent condition of equation
follows: Au, denotes the
36 is there exists À E (R2
such that -V F = A and A
b-
= 0. By equation 37 we obtain equa-
tion 27 and equation 28 as the equivalent condition of -V FV () A We also obtain equa- tion equation
30 equation 31 equation 32 and equation 33 as the equivalent condition of
à b
TT
A
0.
2
With Lemma
B.I in hand,
prove Theorem 2.2 in the following.
Proof of Theorem We first prove the sufficient condition. Given As and An. we only need to construct neg-nigetive (A 20, 20]pe[4]- (Azis A Se P satisfy equa-
tion 27 equation PER-
By Lemma B.1 this will establish the optimality of (ū, 2) in the relaxed program
We first construct (1 An, pe(d] and {,,,s= as follows.
1. For each group such that 2; = 1, and for each E 9: and û, 1, set Au Ao, 0
and Aup (X. 0) dg. For each 9: and âp 0, set Au d (X, 0) and Au, Au 0. By equation 14 one may verify that all constructed values this step are non-negative.
17

---

Published as a conference paper at ICLR 2023
2. For each group i such that 2; 1, set 2, = 0 and A2:51 Epenn (Xp 0)2 0)2
Aς)) - An. which non-negative due to equation 15
3. For each group such that & = O, and for each E d and (XT > Akr set Auy =
(Xp (x 2u, d - (Xp 6)² and Xu, Aupso. 0. Observe that we always have Aupsa
Au,20 = 0 and Sa,
AR. For each p 9i and (X, I ARs set
max((X, 8)2 Λx,0) 0} for each p E 9i-
4. For each group such that & - 0, set A45S 0 and A2, - An - -pEEp m 6)2-
de, 0}, which is non-negative due to equation 16
Finally, it is straightforward to verify that equation 27 equation 33 are satisfied by our constructed X, and therefore, by Lemma B.1 conclude that (á, is the optimal solution of the relaxed program PBR.
We next prove the necessary condition. Given PER and P have the same integral solution, we only need to show there exist 2 and b that satisfy equation 14 equation 16 By Lemma B.1 and á is the integral solution, we have
1. For each group i such that 2; = 1 and Vp E Jr, úp = 1, we have
(X,) 0)² = b Au S1 + AuySa.
(X2 0))
AR-
(39)
For each group i such that & 1 and vp E 9o. up =0, have
(X,) p 0)2 = A u0 = (X 0)² S AR=
(40)
2. For each group such that 2; = 1 and all p E 9:, up = 1, we apply equation 39 and equa- tion 28 and have
((X 0)2 Ax) An A
Σ
((X 0)2 Ap)
An-
(41)
pE
pÊg..
3. For each group i such that 2 = 0. we apply equation 440
and equation 28 and have
((X,) p 0)2 Xs) An >2:20
Xu,20
20
pEg:
pEgi
max ( (Xx T 0)² >k. 00 S an 2=
Xu,20
pEgi
pēg:
max ((X A2:03 S An-
(42)
B.2 DERIVATION OF EQUATION 10
In the case of sqaae regression, the Legendre-Fenchel conjugate of the least-square loss [(::)) = (L - y) is given by (s; 2 + sy. Substituting this conjugate function into H (u) in equation 3 in Theorem 2.1 we have
1 XD(u)x 1 11u112 TT 1
(u) max eEE
(43)
2p"
We can verify that the unique optimal solution of Hu))
XD(x)XT
y.
(44)
P
Substituting i back into equation and applying Theorem 2.1
yield the representation
y (+XD())X++)
LBR
min (u,*)ER
-1 y
(45)
B.3 PROOF OF COROLLARY 2.3
Proof of Corollary 2.3 Under the least-square regression setting, we apply Theorem 2.2 and based
on equation 5 we know à = X + +1) y. We further define M (In + 1-p1111 Xx xxx
P where is the support set indicated by à and then i = -My. Substituting e by 0 = -y in Theorem 2.2 proves the Corollary.
18

---

Published as a conference paper at ICLR 2023
C
PROOF OF THEOREM 2.4
Proof of Theorem 2.4 For least- loss f(,,)) 2t y)² we have that
(uu) max "ER"
X |1012 y
2p
Since the optimal value if non-negative, the optimal dual parameter RR must satisfy that ||l||2 S 2| 2. Note that
H(u) P H()) = (i) + H())) H()), where we set 0; = ūz/Ej 2j if the feature i belongs group and 2j 1, otherwise we set ū, 0. For (u) H(). we have that
(46)
H(u) (()
T XD(u)X
uT -11011 y
n XX(()XXT v -211111 vTy
max vER"
max VER"
2p
2p
_ (D(u) - -((()))D()XXT
max
vEll"
2p
1 max
(X(D(u) T(
(47)
P
where maxx (-) denotes the maximum singular value of the matrix. Similarly, for H(ū) H(ū), we
have that
( H( S max (X(D(a) D(a))x
(48)
For (D( - X( we rewrite it as
- -(()))) =
ΣΣ
2j
1 X.X.
2j
1E::
Note that by our assumption, the operator norm of Eieg, (2 - - u X,X; is at most و S g and the mean of the random matrix 0. By the Ahlswede-We Winter matrix concentration bound Ahlswede & Winter 2002): Oliveira et al. 2010), we have that
Pr max (D() (
Vr= STz exp(-S(t²)),
(49)
where T2 is the number of fractional entries in z. The standard matrix concentration bound (e.g.. matrix Hoeffding) states that for n-dimensional random matrices X2, XM, we have that Pr( (X1 +.... XM) 2 a] < 2n exp(-o' -a02(a"0)=²) where upper bounds the operator norms of X1, X2........ XM almost surely. In the context Eq. (49), we have that o G and we set a = Vr. Using the matrix concentration inequality, we upper bound the Left- Hand-Sid of Eq. (49) by 2n (xp(-rrt//8.M) S 2n exp( -tt /8) (since r= > M). Note that this bound is already good enough since the only difference from the Right- Haant-Han--idde of Eq. (49) is the factor 2n instead of r.. These factors would go into the logarithmic factor in the final error bound of Theorem 2.4 so they do not make much difference.
To improve the factor 2n to rz in Eq. (49), we need to show that there exists dimensional subspace whose basis vector denoted by the columns of Q E R=xr= so that X X(D(ū) (())xx' can be almost surely (where Xi...., Xh,, are r. diddennnioa matrices and
X MM written Q({ ...,X,, ) their operator norms are also bounded by 9). The construction of Q and X1.... .......,' X,,, is possible because each matrix associated with a fractional variable Σ, is low rank and there are only fractional Zy's. We then apply the above matrix concentration bound to X +...X', to derive Eq. (49).
For (D())) - XT, we have that
X(D(u) - D( Σ(u: -.)XXXX
Again, by our assumption, the operator norm of (u4- X. is at most 1, and the mean of the random matrix is (even when conditioned on 2). Therefore, by the Ahlswede- Winter matrix concentration bound Ahlswede & Winter (200);; Oliveira et al. (2010), we have that Pr Tmax (X(((u) D(ū))x 2 Vral2z] < exp( exp(-)(())),
(50)
where ru is the number of fractional entries in i7.
19

---

Published as a conference paper at ICLR 2023
Combining equation 46
equation 47 equation 48
equation 49
and equation 50
have that with
probability at least (1
5), it holds that
Vrx
Vrz:oo((:/009 (000 + Vra log(ra/0)
H(w) - P so
P
proving the theorem.
D ANALYSIS OF THE PERFORMANCE OF LBR ON SYNTHETIC RANDOM ENSEMBLES
D.1 PROOF OF THEOREM 3.1
Proof of Theorem 3.7 Let
M ('xD(WIXT+1) +1
For each feature index i E {1, 2, n) by Mw + we have that
e, x MXy e, MX e X Me.
(51)
We first bound e X XM w as follows. Applying Lemma D.1 to each feature index such that w/ F 0, and via a union bound, we have that there exists universal constant E (0, 1/3200), such that with probability least (1 3k exp(-cnn' (
2))). ), holds that
Vi : w. + O, - e; X MXw E
(52)
Also, applying Lemma D.2 to each feature index such that w; = O, and via a union bound, we have that with probability at least (1 4(d k) exp exp(-cim/k)). it holds that
Vi w, 0, 1 x MXw 0.1/v
(53)
We then bound e X Me as follows. Note that M & 1. Therefore, applying Lemma D.3 to each
feature index i (with T 0.1p/ /k), and via a union bound, we have that with probability least (1 - aidexp(-n/S3 exp( - (4)00>>)))) (.))).ir it holds that
Vi (1, .....,,........... d), |e X Mel S 0.1p/Vk.
(54)
Now we condition on the event that all of equation 52 equation 51 we have that
equation
53 and equation 54 happen. By
Vi wi + 0: le] x MXy E [0.8p/ Vk, 1.2p/ Vk.,
(55)
Vi w. 0: le x MXy E [0,0.2p/vA.
(56)
We now set Ag = (0.2p/vk)2. A = ((0.79p/ Vx)2 Ax) kmin (where we let kmin mi...( [kz} be the size of the smallest non-empty group (in terms of non-zero coefficients)).
and verify the conditions in Corollary 2.3 as follows:
1. Fix any group y such that z = 1. For each E g such that of = 1, we have that wy + 0
and therefore (e. X 2 (0.8p/vK) > 0 by equation 55 For each i g such
that of O, we have that w; = 0 and therefore (e. XT X (0.2p/ S A by equation 56
2. Fix any group such that = = 1. By equation 55 we have Σieg =1 ((e XTMy)²
Ax) 2 ((0.8p/ VTa2 Ax) Kmin > dp-
3. Fix any group such that 2 = 0. By equation 55 and equation 56 we have
Eveg max x My) Ae. 0} < 0 < A
Finally, the theorem is proved by collecting the failure probabilities of the desired events (equation 52 equation (33] and equation (44)
20

---

Published as a conference paper at ICLR 2023
D.2 PROOF OF THEOREM 3.2
Proof of Theorem 3.2
Let
= xD((")) Jx +1) +1)- = -(xxxxx++) +1 = - +
-1
For each feature index E {1, .............................. n..,,..,,,,,,.... yy Mw +,, we have that
ef x MXy= = X MXw(1) + + X Me.
(57)
We first bound e, X ()w as follows. Applying Lemma D.1 each feature index i such that
w o O, and via union bound, we have that there exists universal constant ci E (0, 1/3200), such that with probability least 3k cpp it holds that
Vi: ( * 0, e x MX (o (1) 1.1 1.1||/ 1 S [0.9C, 1.1)
(58)
Similarly, applying Lemma
D.1 to each feature index such that w (2( * 0, and via a union bound,
we have that with probability at least (1 3k exp(-c(p )2))), it holds that
Vi: w (2) +
c x (Xw(() =
x MXx E [0.9|w; 1.1 2 S [0.9g, 1.15 1/4 g]
(59)
Finally, applying Lemma D.2 to each feature index i such that both (1) = and w = 0, and via a union bound, we have that with probability at least (1 4(d - 2k) exp(-c, n )), it holds that
Vi w (1) A w (2) 00, ee M < 0.1g..
(60)
We then bound e, X Mc as follows. Note that M < I. Therefore, applying Lemma D.3 to each feature index (with す = 0. 0.1Ep), and via a union bound, we have that with probability at least - 2deexpppppp) - n/8 () 2d exp( 2 (40002))), it holds that
Vi E {1, ...,....dd d), lc, x Mc s 0.1Ep.
(61)
Now condition on the event that all of equation 58 equation
59 equation
60
and equation 6]
happen. By equation 57 we have that
Vi w 40V w (2)
#0: le, X MXy [0.8Ep, 1.2ç /4pp,,
(62)
Vi u (1) 0 w!" (2) 0: 00|eTx" x MXy 0.2pp.)
(63)
We now set A = (0.2Ep)², An. = ((0.79kp)² -x)) (k/h), and verify the conditions Corollary 2.3 as follows:
1. Fix any group g such that 2g For each E such that u, 1, we have that w ( *
and therefore (e, X MX (0.8Ep)² > A by equation 62 For each E g such that
uf 0, we have that w!! (") w (2) 0 and therefore (c. X MX (0.2Ep)² < d by equation 63
2. Fix any group g such that 2 By equation 62 we have Eiegu; ((e XTM2)²
Ax) ((0.8Ep)² A&) (k/h) An-
3. Fix any group such that 2 = 0. By equation 62 and equation 63 we have
Exeg max((e) X x My) - >R. 0} S ((1.4EE))
> -
(k<(Ch)) S ((1.445))
Ax) (k/((Vh)) 2.0336(Ep) (kth)//k// An, where the last inequality holds for large
enough constant Ç > 1.
Finally, the theorem proved by collecting the failure probabilities of the desired events (equation 58 equation 59 equation 60) and equation 61
D.3 TECHNICAL LEMMAS
Lemma D.1. Suppose & & n/4. Let E Bank be a matrix with i.i.d. N((0,) entries. Let
= 1/248 (8 2 0), and M = (1 (1+ p 1 For any 2 32n 1122, any fixed vector
E R&. such that ||=||oo & and any fixed index i (1,2,..., k), with probability least
21

---

Published as a conference paper at ICLR 2023
(1 (1-3em) (exp (-nl-222/20088) it holds that
(+XTMX-))) XX -1 (x) Se, (
e. P
where Eq the i-th (column) basis vector.
Proof. The proof follows the similar lines of Part (1) of the proof of Lemma 2 in Pilanci et al. (2015). However, we adopt a different regularization parameter p. We write X = U DVT for the singular decomposition of X. By standard results on the singular value of Gaussian random matrices (e.g.. Davidson & Szarek (00T)), for each / 2 0, it holds that
Pr[Vj E {1, (1.......4 k} Vn vk - S Dis S Vn k + -
In particular, if we set t = vn/4 4. we have that
Pr[vj E (1, 2,,,.... k} vn/4 S D3s S / 2 2exp(-n/333
(64)
The rest of the proof will be carried out by conditioning on the successful event equation 64 that
Note
MX V(pl D2
and therefore,
- x MX - 1 + - = -
1
P
D2 where we let D = diag(1 ,,bb all j E (1, ..... kj due to the successful event in equation 64 Note that
11,,,1......, and have that Dzs 2 0 and Djs S 16n 1/2 for
e ( (omx--1)- 11)
e @TTVDVTz)
Σ Vij
39 Σ
Vas Yaiza Zg
Σ 1333
+
Σ Vis Vvs
Djs
Vai2g
(65)
9:93/1
It is easy to bound the first term in equation 65 by
Σ
S 16n 6 112
(66)
Let V be the (k - 1) x k matrix obtained by removing the i-th row from V, and let z be the (k: 1)- dimensional vector by removing the i-th entry of z. We can rewrite the second term in equation 65 as
EVODSS Σ Vap2o
C TVVVVT
(77)
Observe that even when conditioned on D (and therefore D). e, VDVT is (k- dimeeensio vector pointing towards uniform random direction, and its 2-norm is most 16n On the other hand, ă is fixed (A 1) -idimensiinnal vector with || I vk I. Therefore, by standard spherical concentration inequality, we have that
Pr VVVV
S < 16n 6 1/2
2 1 exp [ni(c - 16n 1
> 1 exp (-n' 126,2 22222/2488
(68)
Combining equation 65 equation 66 equation
67 equation
68 and collecting the probabilities, we
prove the desired result.
Lemma D.2. Suppose k S n/4. Let X E R be matrix with i.i.d. N' 1) entries. Let u E Rk
be a column vector with i.i.d. N(O, 1) entries. Let p p= n (8 2 0), and M = (I + 1 For any E (0,1) and any fixed vector z E TR. such that ||=||2 S 1, with probability at least
(1 - 4exp (-ne² /322),, it holds that
1 T MX Sc.
22

---

Published as a conference paper at ICLR 2023
Proof. The following proof is based on the standard calculation, which also appeared in Part (2) of the proof of Lemma 2 in Pilanci et al. (2013).
Write X UDV for the singular decomposition of X. Again, we have equation 64 and will condition on the successful event in equation 64 for the rest of the proof. Note that
MXx (()D==++)--VV
and therefore
1 MX²
$4/Vi
Thus, fu MX is a centered Gaussian with standard deviation 4/ /n, and the probability that Lu MMMxX > e is at most 2 exp((c"'n332 by the standard Gaussian tail bound. The lemma is proved by collecting the failure probabilities.
by the successful event in equation 64
Lemma D.3. Let u E R a column vector with i.i.d. N(O, 1) entries. Let M E RRax be any PSD matrix (which might depend on u) such that its eigenvalues at most 1. Let e E R" be independent column noise vector with i..d. (O, 7²) entries. For any T > O, with probubility at least
(1 - 2 expp( -n/8) 2 2exp(->" 1aapp-22/(A//pp))) (n)) it holds that
Mc ST.
Proof. By standard x² concentration results, we have that with probability least (1- (1-2exp(-n/8)) it holds that | < 2n. The rest of the proof will be carried out conditioning on this event.
Note that Mull22 S || |2/ Therefore,
Me N/(0, 7 2 ||| (l))) By the standard Gaussian tail bound,
we have that
Pr[lu' Me < +] 2 2 exxp - (2- 2 - 2 2exp(-72/442"1)
The lemma is proved by collecting the failure probabilities.
E OPTIMIZATION
We the projected Quasi-Newtar Newton (PQN) method solve the optimization L.n defined in equa- tion TO The details of PQN is elaborated in Schhidt et al.) (2009) Algorithm 1, therefore, we refer the interested audiences to Schmidt al. (2009) for more details. To apply PQN, we need know the
gradient of the objective function in equation
10 The partial gradient of G(u) w.r.t us can be written
as
aG(u) au, = - (xx]
x (HXD(())) +1)
+1)"'v y/
(69)
Computing such gradient requires the solution of a cank-|/u/lo linear system of size n, which can be calculated in time (1 + (nd) via the QR decomposition. When the sparsity level is relatively small, such computation is not expensive. also need to do the following projection PQN.
min ||x vll2.
(70)
ZEQ
where 12 is defined in Section 2.2 The projection on the relaxed constraint set Q can be efficiently obtained by a commercial solver (we use Gurobi Gurobi Optimization, LLC((022))
F NUMERICAL VERIFICATION OF COROLLARY 2.3
Corollary 2.3 states that under the least-squares regression setting, under certain conditions, the solution of the relaxed program integral and consistent with the optimal solution of the problem with Boolean constraints. In this section, we numerically verify the equivalence established in Corollary 2.3
We consider to generate synthetic data follow Random Ensemble we set d 200, 10, J: 50 (h; 10, vi E (1,2,..., .,)) h = 5. We vary sample size n and SNR (controlled by 7) to see whether the solution of the relaxed program is the optimal integral solution of the program with Boolean constraints.
For each n and SNR, we randomly generate 10 datasets. We run our relaxed program on these 10 datasets and count the number of solutions that the same the integral solutions of the program with Boolean constraints. As shown in the Table ST the proposed equivalence can be achieved when the sample size and SNR are large.
23

---

Published as a conference paper at ICLR 2023
(a)
(b)
1
1
Accuracy of Individual
support recovery
0.8
Accuracy of group support recoery
0.9
0.6
SGL
0.8
Proposed
ENet
0.4
5GL.
0.7
SGL
5GCover
Proposed
ENet
0.2
0.6
SGL,
SGCover
0
0.5
500
1000
1500
500
1000
1500
Sample size
Sample size
Figure S1:
Performance comparison different ys (a) A, as n increases when 7 3.5. (b) Ag as increases when y = 3.5. We average results over 10 datasets and the error bar means 95% confidence interval.
Table S1: Number of solutions that is the integral solutions of the program with Boolean constraints
SNR
n
100
n
200
n 300
n = 000
40
0/10
10/TO
10/TO
10/10
30
0/10
10/10
10/10
10/10
20
0/10
0/10
0/10
10/10
G
ADDITIONAL EXPERIMENTS FOR RANDOM ENSEMBLE
We compare our proposed method with other state-of-the-art methods on simulation data generated from Random Ensemble I with different ys. We first set 7 3.5 and compare the performance of the competing methods the signal to noise ratio is around 3. We compare the competing methods on 10 different data sets generated from Random Ensemble I with 3.5. As illustrated in Fig. [ST (a) and (b), our proposed method still outperforms all the competing methods in terms of both A and Ag with the increasing number of samples.
recovering the individual and group supports. Note that when
3.5.
H EXPERIMENTS FOR SYNTHETIC DATA SATISFYING MUTUAL INCOHERENCE CONDITION
In Random Ensemble I, we generate v; (Q0, 7) as i.i.d features. In this experiments, aims to evaluate the performance of the competing methods in the presence correlation between features. We follow the way we generate the data Random Ensemble I, where we set d 1000, 10, 5)). h = 5, and 7 0.1. Then only different is that we generate
k 50 (k:- 10, vi E [1, ,1,,,,..,,))) I; (0, M). where E is the Toeplitz covariance matrix Σn أ Such matrices satisfy the mutual incoherence condition, required by f-rreuulrrized estimators be statistically consistent. We consider = 0.2 and p = 0.7 for Σ to evaluate the competing methods' performance under different correlations. The performance is shown in Fig. S2
We find that when p 0.2, support recovery (both individual level Fig. (2[a) a)) and group level Fig. S2 b)) can be easily achieved by most of the models. And our model outperforms other competing methods. However, when p = 0.7, all models have difficulties to accurately recover the support at the individual level (Fig- (2(c)) c)). which makes sense because the correlation between features are high so that finding the correct features becomes more challenge. Our model still outperforms other competing methods at both individual level (Fig. ()) and group level (Fig. (2())) d)).
ADDITIONAL EXPERIMENTS FOR CANCER DRUG RESPONSE PREDICTION
We first show Table. SB which illustrates the pathways and genes identified by the proposed method for drug IMATNIB and the corresponding researches that support the findings. We further find the targeted pathways and genes for three other drugs: GEFITINIB, BEXAROTENE, and BOSUTINIB. In Table. SS4 show the number of targeted pathways and genes identified by
24

---

Published as a conference paper at ICLR 2023
[a]
p=0.2
(D)
p=0.2
[C]
p=0.7
(d)
p=0.7
ACOL ncy of
support micoovv
Accuraayy of group
s-ppport recoMrT
0.9
Accurety of Indivvtuul
support rosverry
Accunsty of grosp
support redteey
0.6
0.6
0.6
Proposed
0.7
SG.
9.4
Pripossed
SCL
SCL. 5DC
500
S0L_
S00ovo
0.
SCL
0.5
500
1000
1500
500
10000
1500
1000
1500
500
1000
1500
Sample
Sample
Figure S2: Performance comparison for different ps. (a) A, as n increases when p = 0.2. (b) Ag as
increases when = 0.2. (c) Ar increases when 0.7. (d) Ac as increases when p 0.y. We average results 10 datasets and the error bar means 95% confidence interval for (a)-(d).
each competing method and the out-of-sample MSE. As shown our method achieves the smallest out-of-sample MSE and the fewest number of pathways and genes.
J TIME COMPARISON FOR RANDOM ENSEMBLE I
We compared the running time for experiments of Random Ensemble when the sample size is 1,000 the Table. S2
Table S2: Time comparison (mean s.d.) for Random Ensemble when the sample size is 1000.
Method SGL
SGL_po
SGCover
ENET
Proposed
Time (s) 1.4.0.1 4.2 0.2 20.8 0.2+0.03
24.412.1
K IMPLEMENTATION DETAILS
For section 4.1 subsection "Feature selection with given support sizes k and h² and section 4.2, select the parameters as follows. For our method, because k: and h are given, we only have one parameter p in (1) left, select p by the 5-fold CV in terms of MSE. For the result of the methods, which cannot control & and h, we just sweep the parameters to let them yield the desired k and h. For the real-world application, we select the parameters in terms of out-of-sample MSE
L CODE AVAILABILITY
The codes for the proposed method be found here: science/ee Bttp:///LOOOOO100/R.eee
4opee 4open
Table S3: Pathways and genes identified by the proposed methods for IMATNIB.
Pathway
Genes
Reference
RHO GTPases Activate WASP: and WAVEs
ARPCIB WASFI ARPCS WASL CYFIPI ACTGI ACTR3
Gu et al.
2009
Huang al.
2008
Chen et
LAMTOR3 LAMTOR4 SNATI RPTOR RRAGA RRAGR MBD3
Regulation of PTEN gene transcription
RRAGD PHC3 GATAD2A RCORI MECOM CBX8 LAMTOR2
Nishioka
2011
Peng et
2010 Huae
Signaling by PDGF
PDGFC COL4A3 COL6A2 COL6A3 COL9A3
Malavaki et
2013
Li ct al.
2006
Heldin
Retinoid metabolism and transport
CLPS LRPS APOCS SDC4 LPL LRP10 LRP12 APOA2
Hoxng al.
2010
TCF transactivating complex
RBBP5 KATS PYGO1 PYGO2 BCL9
Zhung et
2021
Coluccia et al.
2007 Cox
Deactivation the betn-catenin transactivating complex
RBBPS SOX3 SRY PYGOI PYGO2 CBYI BCL9
Zhou
2003
2213
RAS processing
ZDHHCO GOLGAZ BCL2LI ABHDI7R
Ching et ml.
2006
Braun & Shannon
2008
25

---

Published as a conference paper at ICLR 2023
Table S4: Result comparison for three other drugs.
Durg BOSUTINIB
Method
1o (s.d.)
(s.d.)
Out-of-sample
MSE 95% CI
Proposed method
36
5
29.412.1
SGL-Overlap
64 (4.3)
(0.9)
4
ENet
48 (5.3)
18(3.2)
35.4
SGCover
240 (10.4)
15 (1.8)
52.4 - 4.2
GEFITINIB
Proposed method
42
6
35.4 1.4
SGL-Overlap
78 (4.6)
13 (1.3)
4.78 2.1
ENet
49 (5.6)
(2.1)
+
SGCover
278 (13.4)
12 (2.4)
59.6 3.6
BEXAROTENE
Proposed method
52
8
36.9
SGL-Overlap
86 (3.8)
15 (1.5)
61.8 2.7
ENet
64 (5.2)
17 (3.5)
38.4 + 2.3
SGCover
312 (16.3)
18 (2.3)
58.2 - 3.1
26


Reviews:
[{"review_id": "kioeU4yxl9", "reviewer": "Reviewer_fvhG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new convex relaxation for the high-dimensional group-sparse recovery problem.  It builds on the boolean relaxation from element-wise sparsity from previous work.  In experiments the method is shown to improve individual feature and group-recovery upon existing sparse-group-lasso family of methods in the low-data regime.  It also allows direct control of the desired (group)-sparsity instead of more cumbersome sweep over regularization parameters. \n", "summary_of_the_review": "Interesting work on group-sparse recovery, a formulation that stands out from the existing (large) body of work.  It naturally builds on the boolean relaxation for individual sparsity done in prior work, but the extension is not trivial (especially the analysis -- which I unfortunately couldn't check carefully due to the extremely short timeline of the review process).  Empirically the proposed method appears to give noticeably improved recovery performance in low-sample regime.  I am unclear of the practical significance -- as computational complexity / timing results are not provided, and likely high. ", "strength_and_weaknesses": "Strength:  The so-called boolean relaxation is qualitatively different from the large existing body of work on convex relaxations of individual and group sparsity.  The paper extends this approach from regular sparsity, done in prior work, to group sparsity.  Very thorough theoretical analysis, and good experimental performance on simulated and real data.  Also a so-called 'equivalent' condition for non-overlapping groups is proposed which certifies that the convex relaxation is equivalent to the binary optimization problem -- although I'm not sure if it's realistic to evaluate it in practice, or it has purely theoretical value. Overall, group-sparse priors are important in practice, and if the method is indeed significantly better in terms of support and group-support recovery in the low-data regime, that could be impactful. \n\nWeaknesses:\n1.  Limited or no discussion of computational complexity + timing results.  How does the method compare to enet / Sparse-group-lasso and related methods.  From the construction it appears significantly more expensive.  Even if it's more expensive -- it could still be valuable in settings with limited data -- please add some discussion / timing results. \n\n2. The explanation of the main method itself in the main body of the paper is rather concise, with limited motivation.  Essentially the formulation is just given onto the reader.  Due to the very tight reviewing deadline -- I haven't had a chance to read the supplementary material -- if there's additional explanatory detail there, it would be helpful to move it upfront. \n\n3. Is the result in theorem 2.2. -- equivalent condition -- possible to evaluate numerically for a given problem? How would you find the lambda's?  Also you claim there are no equivalent recovery results (\"rigorous theoretical techniques\" ) for group-sparse settings (GL and the like) -- what do you mean exactly -- there's a large literature on this topic, with various group-generalizations of conditions from plain sparsity for exact recovery. \n\n4.  You mentioned that the formulation captures other structural sparsity assumptions -- like tree-sparsity, DAGs, e.t.c.  Does this possibly require a very large number of groups in your formulation (so only of theoretical interest)? \n\n5. Random ensemble II is curious -- but highly artificial.\n\n6. How well can you control k and h by sweeping regularization parameters for competing methods?  What do you mean by ranking results (based on coefficient magnitude) for other methods?  The ability to pick exact k and h is a nice advantage -- but I wonder if the improvement in recovery results is somehow an artifact of not being able to find parameters to get the right solution for GL-family, and instead of forcing an incorrect solution to have the same k and h? \n\n7. Have you looked at greedy (of the group-OMP type) or  iterative-hard-thresholding methods for group-sparsity?  These can control exact group sparsity, and some do come with theoretical analysis.  How do they compare with the proposal? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_LouOnYbjF9", "reviewer": "Reviewer_7cXz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of learning sparse group models via Boolean convex relaxation. The paper establishes the equivalence between the original problem with the cardinality constraint and the relaxed convex problem with the Boolean relaxation. Then, the authors apply the established equivalence to two ensembles of random problem instances and prove that the proposed relaxation method can achieve the true support of the regression vector.", "summary_of_the_review": "Overall the paper is interesting, which studied the Boolean relaxation for sparse group models and established the theoretical equivalence between the original problem and the relaxed problem. However, the authors should solve the concerns about Theorems 3.1 and 3.2, and provide experimental verification (Please refer to the Weakness part for more details).", "strength_and_weaknesses": "Strengths: \n1. The paper provides theoretical guarantees on the equivalence between the original problem and the relaxed problem, which makes the relaxation more convincing.\n\n2. The paper provides two examples to demonstrate equivalence.\n\nWeakness:\n1. Theorems 3.1 and 3.2 claim that the relaxed program achieves the optimal solution. However, such a solution is only consistent with the underlying regression vector $w$. It is unclear whether this solution is consistent with the optimal solution of the problem with Boolean constraints, i.e., Problem (3). If not, the equivalence is not established actually.\n\n2. Experimental verification for the established equivalence is necessary. More specifically, the author should design experiments to show that the solution of the relaxed program is integral and consistent with the optimal solution of the problem with Boolean constraints.\n\n3. In Theorem 3.1, $\\rho$ should be $n^{1/2 + \\delta}$ instead of $n^{1/2} + \\delta$.\n\n4. The paper presents a rounding scheme. It is unclear whether the rounding scheme has been applied in experiments. \n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FYYZyxfGLi", "reviewer": "Reviewer_4rdY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose learning group structured sparsity using explicit constraints on the feature and group sparsity. They derive a reformulation of the proposed problem in terms of boolean variables for the selected features and groups, which is then converted into a convex problem by relaxing the boolean constraints to lie within [0, 1]. Theoretical results are presented to (a) give conditions when the relaxed problem recovers the true model structure, (b) special cases when the model and design matrix are generated according to a random ensemble protocol. \nThe experimental results illustrate the superiority of the proposed scheme against similar methods such as SGL, SGL_\\infty. ", "summary_of_the_review": "Overall, this paper presents an approch for learning group structured sparse models. The theoretical results and evaluation are convincing. ", "strength_and_weaknesses": "Strengths\n1. The paper is written well and easy to follow. \n2. Presents theoretical results on support recovery and convergence\n\nQuestions / Comments\n1. The idea has some similarity to (I) \"Convex relaxation for combinatorial penalties - Obozinski. et. al, 2012\" and (ii)\"Identifying Groups of Strongly Correlated Variables through Smoothed Ordered Weighted 𝐿1-norms - Sankaran et.al 2017\". The above works consider L_p relaxations of combinatorial (submodular) penalties, the special case of which is L_2 relaxation of the penalties. The formulation proposed in this submitted paper may be compared to (i) and (ii) after converting the constraints into a penalty. \n\n2. Most/All the results are presented for non-overlapping groups only, even though the problem setup initially studied is in general. It may be better to stress this in the paper to avoid misrepresentation.  \n\n3. The random ensembles are studied for iid design matrices. May be interesting to understand how the algorithms compare in the presence of correlation within columns of X. \n\n4. What are the regimes where the other compared algorithms such as SGL, SGL_\\infty may do better in the structure recovery ? Or, is the proposed formulation expected to perform better than them in many other settings than the ones considered in this paper. If so, how do we reason out on the performance ?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DrLHyqo9OtV", "reviewer": "Reviewer_4Ewe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents an algorithm for learning sparse group models. The key technique used is a convex Boolean relaxation. Solution to the resulting Boolean relaxation is fractional, and the authors then propose rounding algorithms to recover the feasible Boolean solutions with provable guarantees.", "summary_of_the_review": "I enjoyed reading the paper, and recommend acceptance.", "strength_and_weaknesses": "The idea of the paper is clear and well-presented. The proposed Boolean relaxation supports a variety of models with proper Legendre-Fenchel conjugates. The authors also illustrate the utility of the method in least-squares regression. Empirically, the authors demonstrated that the algorithm could help recover the support sizes k and h under certain circumstances. It could be useful to provide the computational complexity of the algorithm. At a first glance, the complexity appears to be O(n^2 d^2) which could be relatively expensive.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%