A Comparison of Hamming Errors of Representative Variable Selection Methods
Authors: Tracy Ke
Longlin Wang
Venue: ICLR 2022 Poster (2022)
Keywords: Lasso
Hamming error
phase diagram
rare and weak signals
elastic net
SCAD
thresholded Lasso
forward selection
forward backward selection

Abstract: Lasso is a celebrated method for variable selection in linear models, but it faces challenges when the covariates are moderately or strongly correlated. This motivates alternative approaches such as using a non-convex penalty, adding a ridge regularization, or conducting a post-Lasso thresholding. In this paper, we compare Lasso with 5 other methods: Elastic net, SCAD, forward selection, thresholded Lasso, and forward backward selection. We measure their performances theoretically by the expected Hamming error, assuming that the regression coefficients are ${\it iid}$ drawn from a two-point mixture and that the Gram matrix is block-wise diagonal. By deriving the rates of convergence of Hamming errors and the phase diagrams, we obtain useful conclusions about the pros and cons of different methods.

Published as a conference paper at ICLR 2022
A COMPARISON OF HAMMING ERRORS OF REPRESEN- TATIVE VARIABLE SELECTION METHODS
Zheng Tracy Ke Department of Statistics Harvard University Cambridge, MA 02138, USA zke@ fas www.ahaaaadde.oom edu
Longlin Wang
Department Statistics
Harvard University
Cambridge, MA 02138, USA 1wang20fas www.waraaaa... edu
ABSTRACT
Lasso is celebrated method for variable selection in linear models, but it faces challenges when the variables are moderately or strongly correlated. This motivates alternative approaches such using non-convex penalty, adding ridge regular- ization, or conducting a post-Lasso thresholding. In this paper, we compare Lasso with 5 other methods: Elastic net, SCAD, forward selection, thresholded Lasso, and forward backward selection. We measure their performances theoretically by the expected Hamming error, assuming that the regression coefficients are iid drawn from two-point mixture and that the Gram matrix is block-wiss diagonal. By deriving the rates of convergence of Hamming errors and the phase diagrams, we obtain useful conclusions about the pros and cons of different methods.
INTRODUCTION
Variable selection is one of the core problems in high-dimensional data analysis. Consider linear regression, where response y E IR" and the design matrix X ==I1...., E RRxp satisfy that
y X + 2,
| 1,
(1)
The goal estimating the support of /3 (Supp(B)). Lasso Tibshirani 1996) is a popular method:
Slasso argming {1ly X 31 >|1BBh
Lasso has good rates of convergence on the T.y-estimation error or prediction error (Bickel et al. 2009). However, it can be unsatisfactory for variable selection, especially when the columns in the design matrix are moderately or strongly correlated, /Zhao & Yu (2006) showed that an irrepresentable condition on X is necessary for Lasso to recover Supp(3) 3) with high probability, and such a condition restrictive when p is large (Fan & Lv 2010). Ji & Jin (012) studied the Hamming error of Lasso and revealed Lasso's 's non-optimality by lower-bounding its Hamming
rate. Many alternative
strategies were proposed for variable selection, such as using non-convex penalties (Fan & Li 2001]
Zhang 2010 Shen al. 2012), adding ridge regularization (Zou & Hastie 2005). post-processing
on the Lasso estimator (Zou 2006 Zhou 2009), and iterative algorithms ZZhag 2011 Donoho
al. 2012). In this paper, our main interest to theoretically compare these different strategies.
Existing theoretical studies focused on 'model selection consistency' (c.g., Fan & Li (2001): Zhao &
Yu (2006); Zou (2006); Meinshausen Bühlmann (2010): Loh & Wainwright/ (211)), which uses
((Supp( 5 Su)p(5)) measure the performance variable selection. However, for many real applications, the study of the Hamming error (i.e., total number of false positives and false negatives)
urgent need. For example, genome-wid widde association studies (GWAS) or Genetic Regulatory Network, the goal is to identify the genes or SNPs that are truly associated with given phenotype, and we hope to find multiple testing procedure that simultaneously controls the FDR and maximizes be re-cast minimizing the Hamming error in
the power (for multiple testing). This problem special regression setting (Efron 20044) Jin] 2012 [Sun & Cail 2007). This motivates us to study the Hamming errors of variable selection methods, which were rarely considered in the literature.
We adopt the rare and weak signal model (Donoho & Jin 2004; Arias-Castro et al. 2011 Jin & Ke 2016), which is often used in theoretical analysis of sparse linear models. Let p be the asymptotic

---

Published as a conference paper at ICLR 2022
parameter. Given constants & E (0,1) and r assume that B, are iid generated such that
Tp:
with probability Epp with probability 1 - Eps
Bg - 0.
where
Tp = /2r log(p). Cp c
(3)
As + 00, || R p1-1 and a nonzero B3 is at the critical order v (p) The two parameters (U.r) capture the sparsity level and signal strength, respectively. We may generalize 3 to let nonzero Sy's s take different values in [Tp, oo), but the current form is more convenient for presentation.
The blockwise covariance structure is frequently observed in real applications. In genetic data, there may exist strong correlations between nearby genetic markers, but the long-range dependence is usually negligible: as a result, the sample covariance matrix is approximately blockwise diagonal (Dehman et al. 2015). In financial data, the sample covariance matrix of stock returns (after common factors are removed) is also approximately blockwise diagonal, where each block corresponds to an industry group (Fan et al. 2015). Motivated by these examples, we consider an idealized setting, where the Gram matrix X block-wise diagonal consisting of x 2 blocks:
B = P and Bo = {
[
p
B,
if is even, if p is odd.
G = dBiag(B, B,... B, Bo),
where
(4)
1,
This is an idealization of the blockwise covariance structures in real applications. We may generalize (4) to allow unequal block sizes and unequal off-diagonal entries, but we keep the current form for convenience of presentation. Model (4) is also closely connected to the random designs in compressed sensing DDnohoo| 2006). Write X = X2,
X,Y'' Suppose X2......... X,, are iid generated from (O, n E), where Σ has the same form as G in 4 In high-dimensional sparse setting, we have || < < p. Then, G == X'X ss 2, and due to the blessing of sparsity of B3 GB EB As a result, X'y (sufficient statistic of (3) satisfies that X'y G3 + (00 G) ~ ΣB + +N, E), and the right hand side reduces to Model 4 (Genovese et al. 2012). In Section 3.5 we formally show that
this random design setting is asymptotically equivalent to Model )
Now, under model (3) and model 4 we have three parameters (0,r,p) They capture the sparsity level, signal strength and design correlations, respectively. Our main results are the explicit con- vergence rates of Hamming error, as a function of (0, r, p). for different methods. We will study six methods: (i) Lasso in (2): (ii) Elastic net (Zou & Hastie 2005). which adds an additional - penalty to 2 (iii) smoothly clipped absolute deviation (SCAD) Fan Li 200T), which replaces the I' --eeallyyy by non-convex penalty, (iv) thresholded Lasso (Zhou 2009), which further thresholds the Lasso solution, and two iterative algorithms, (v) forward selection and (vi) forward backward selection (Huang et al. 20166;; see Section 3 for precise description of each method. To our best knowledge, our results are the first that directly compare Hamming errors of these methods.
2 A PREVIEW OF MAIN RESULTS AND SOME DISCUSSIONS
For any 8, its Hamming error is H(3 = Σラ= 183 # 0,3, 0 0} + E 0 0). As we shall show, for any of the six methods studied here, there exists a function h(0, r) E [0. such that (3,
=
L,p2-h((,r.p) h(d,r.p), where Lp is multi-log(p) term. (A multi-log(p) term is such that Lp p" - oc and Lp p-= e + for any e > 0.) Since the expected number of true relevant variables is p - we are interested in three cases:
Exact recovery: h(Dr,,)) p) > 1. In this case, the expected Hamming error is o(1) as p + co. It follows that model selection consistency holds.
Almost full recovery: 1 < h(0,r, p) 1. In this case, the expected Hamming error does not vanish as p + oo, but is much smaller than the total number of true relevant variables. Variable selection is still satisfactory (although model selection consistency no longer holds).
No recovery: h(0, r, P) < 0. In this case, the expected Hamming error is comparable with or much larger than the total number of true relevant variables. Variable selection fails.
In TT. we assume that cach column of X is standardized to have unit e- --norm and that the order of nonzero 3, is / /log(n). Alternatielly, many works assume that each column of X is standardized have an L (--oorm of 2//////log())) (p) These are two equivalent parameterizations.
v and that the order for nonzero 8, is n 1/2
2

---

Published as a conference paper at ICLR 2022
p = 0.5
0 = -0.4
18
Elastic net Ip- 0.25]
Elastic net (u- 0.25)
16
Lacso
SCAD
14
SCAD
Thresholded Lasse
Forward selection
Farwaidd selaction
12
Thresholded Lasso
6
Forwaid backward selection
Forward backward selection
Region of recovery
10
Region of recovery
4-
2
8.0 0.2
0.4 0.6 0.8 1.0 0.2
0.4 0.6 0.8 1.0
0
Figure 1: Phase diagrams of six variable selection methods for a block-wise diagonal design. The parameters (1, r. p) characterize the sparsity, signal strength, and design correlations, respectively. For each method, we plot the curve r = (()) which separates Region of Almost Full Recovery and Region of Exact Recovery (the lower this curve, the better). Explicit forms of (0) are in Section 3 On the left panel, the curves for Lasso and SCAD overlap and are displayed as dashed line. How to
interpret these phase curves are discussed in Section 2
We call the two-dimensional space (1, r) the phase space. For each fixed p. the phase space is divided into three regions: Region of Exact Recovery (ER), which is the subset {(0, r) h(0 r, p) >> 1], and Region of Almost Full Recovery (AFR) and Region of No Recovery (NR) defined similarly. This gives rise to phase diagram for each method. We denote the curve separating ER region and AFR region by r UV) and the curve separating AFR region and NR region by L(0); they are called the upper and lower phase curves, respectively. The phase diagram and phase curves convenient ways to visualize the convergence rates of the Hamming error.
Figure shows the phase curves for the six methods (with explicit expressions in the theorems in Section 3). These phase curves depend on the correlation parameter Under our model, for each diagonal block (j.j+ + 1). it holds that E[z = Bg + p8 where By, B5+1 E {0. Tp). Therefore, a positive p boosts the signal at each individual site (i.e., [| 2 B,), while a negative p leads to potential 'signal cancellation' (i.e., E| [ < Bj). This is why the phase curves have different shapes for positive and negative p. In Figure we plot the phase curves for p = 0.5 and -0.4. For other positive/negative value of p, the patterns are similar.
Discussion of SCAD. SCAD is representative of non-convex penalization methods. There have been inspiring works that demonstrate the advantages of using a non-convex penalty (e.g.. Fan & Peng y004): Loh & Wainwright (2017)). Our results support their insights from different angle: The phase curve of SCAD is strictly better than that of Lasso, when & < 0.5 and p < O. Furthermore, our results illustrate where the advantage of SCAD comes from compared with Lasso, it handles 'signal cancellation' better. To see this, we recall that 'signal cancellation' only happens for p < O. Moreover, under our model (3), the expected number of signal pairs (a signal pair is a diagonal block {j.j + 11 where both 33 and 33++1 are nonzero) is x pe p1-20 Therefore, "signal cancellation" becomes problematic only when 0 < 0.5 and p < 0 both hold. This explains why the phase curves of SCAD and Lasso are the same for the other values of 0 and p. We note that in the previous studies (c.g.. Loh & Wainwright (017)), the advantages of a non-convex penalty in handling 'signal cancellation are reflected in the weaker conditions of (X, 3) for achieving model selection consistency. Our results support the advantage of using non-convex penalty by directly studying the Hamming errors and phase diagrams.
The performance of SCAD can be further improved by adding an entry-wise thresholding on 3. We believe that the phase diagrams of thresholded SCAD are better than those of SCAD itself, although the extremely tedious analysis impedes us from specific results for now. Also, we are cautious about what to conclude from comparing SCAD and thresholded Lasso. In our settings, Lasso has no model selection consistency mainly because the signals are too weak (i.e., is not sufficiently large). In such settings, thresholded Lasso outperforms SCAD in terms of the Hamming error. However, there cases where Lasso has model selection consistency no matter how large the signal strength is
3

---

Published as a conference paper at ICLR 2022
(Zhao & Yu 2006).
For those cases, it is possible that SCAD is better than thresholded Lasso (see for a related study).
Wainwright 2009)
Discussion of Elastic net. The phase curve of Elastic net is worse than that of Lasso. As will explain in Section Elastic net is a 'bridge' between Lasso and marginal regression in our case. Since the phase curve of marginal regression is always worse than that of Lasso for the blockwise diagonal design, we do not benefit from using Elastic net in the current setting. We must note that Elastic net is motivated by genetic applications where several correlated variables are competing as predictors, and where it is implicitly assumed that groups of correlated variables tend to be all relevant or all irrelevant (Zou& & Hastie| 2005). This is not captured by our model (3). Therefore, our results do not go against the benefits of Elastic net known in the literature, but rather our results support that the advantages of Flastic net come from 'group' appearance of signal variables.
Discussion of thresholded Lasso. Thresholded Lasso is representative of improving Lasso by post-processae There have been inspiring works that demonstrate the advantages of such a post- processing (van de Geer et al. 2 [Wang et al. 2200;; Weinstein et al. 2020). Our results support these insights from a different angle. is surprising (and very encouraging) that the improvement by post-Lasso thresholding is so significant. We note that Lasso is a I-stage method, which solves single optimization obtain B. By comparison, thresholded Lasso is 2-stage method. Lasso has only one algorithm parameter X, while thresholded Lasso has two algorithm parameters À and t (the threshold). In Lasso, we control false positives and false negatives with the same algorithm parameter X, and it is sometimes hard to find a value of À that simultaneously controls the two types of errors well. In thresholded Lasso, the two types of errors can be controlled separately by two algorithm parameters. This explains why thresholded Lasso enjoys such a big improvement upon Lasso. It inspires us to modify other I-stage methods, such as SCAD, by adding prosessoosssing step of thresholding. For example, we conjecture that thresholded SCAD also has strictly better phase diagram than that of Lasso, even for a positive p. On the other hand, thresholding is no free lunch. It leaves one more tuning parameter to be decided in practice. Our theoretical results are based on ideal tuning parameters. How to properly choose these tuning parameters in a data-driven way is an interesting question. Weinstein et al. (2020) proposes promising approach, where they use cross-validation to select À and FDR control by knockoff to select t. We leave for future work to study the phase diagrams with data-driven tuning parameters.
Discussion of the two iterative algorithms. We consider two iterative algorithms, forward selection ('Forward") ) and forward backward selection ('FB'). The FB algorithm we analyze is simplified version in Huang et al. (2016). which has only one backward step (after all the forward steps have finished) by thresholding the refitted least-squares solution. Our results show that both methods outperform Lasso, and between these two methods, FB is strictly better than Forward. In the literature, there are very interesting theoretical works showing the advantages of iterative algorithms for variable selection (Donhho et al.) [012] Zhang (011)) Our results support their insights from different angle. We discover that, for a wide range of p. FB has the best phase diagram among all the six methods. This is a very encouraging result. Of course, it is as important to note that the performance of an iterative algorithm tends to be more sensitive to the form of the design, due to its sequential nature.
3 MAIN RESULTS
Consider model the expected Hamming error, where the expectation is with respect to the randomness of B and z. Let Lp denote a generic multi-log(7 term such that Lpp" + 0o and Lpp + 0 for any >> 0.
and 4p where we set 0² = 1 without loss of generality. Let (8, [3, be
Theorem 1. Under Models (.. (3), and (4). for each of the methods considered in this paper (Lasso, Elastic net, SCAD, thresholded Lasso, forward selection, forward backward selection, as well as marginal regression in Section 3.1 there exists a function h( T.PP) such that E.H (3, 3)] = Lpp' -h(0,..).)) The explicit expressions of h(0, r. p), which may depend on the tuning parameters of a method, are given in Theorems B. C.I, D.I.D.3, F.I, G.I, H.1-H.4 of the supplement.
In the main article, to save space, we only present the expressions of the upper phase curve Ui))
U 0;; p) and the lower phase curve L(O) L(0;) p) for each method, which are defined as follows:
U U(0 p) in > 0: h(0 r.)) 1),
T(O:p) inf(r > 0: h(0,r.)) 0)- (5)
4

---

Published as a conference paper at ICLR 2022
p 0.5
p -0.2
p
00.4
p- (Marg, Reg.)
p- (Marg. Reg-1
J.me (Marg. Reg.)
24
pm2
p 2
54
0.5
48
M.5
pl (Casso)
p 0 (Lasso)
ju (Lasso)
10
43
24
022
122
13
0
Figure 2: The phase diagrams of Elastic net and its comparison with Lasso (notation: rj = p/(1+p))
These two curves describe the phase diagram: The upper phase curve (0) separates the ER region and AFR region, and the lower phase curve L(0) separates the AFR region and NR region.
3.1 ELASTIC NET AND LASSO
The Elastic net Zouu & Hastie, 2005) is method that estimates /3 by
jEN argmin, 3 { [llv x A||Bll, + (1/2)1181
(6)
Compared with Lasso, adds an additional L'-penalty to the objective function. Below, we fix μ > 0 and re- re-parametrize = log(),, for some constant q > 0. The choice of affects the exponent,
1 1 1(0, r),). in the expression of (3, [3)]. We choose the ideal q that minimizes 1 h(0,r,p) P). The next theorem is proved in the supplement.
Theorem 2 (Elastic Net). Under Models ① 3. and (4. let JEN be the Elastic net estimator in ( Fix μ and write = p1 + p). Let = v 2q log(p) with an ideal choice of q that minimizes the
exponent of TE H [8, 3). The phase curves are given by L(0) = 0, and
U(O)- fmax (12)
when 2 0,
max (h)( (0), h2))), has (1), ha))
when p < 0,
where 111 (0) = (1 + v1 0)2, h2) = (1 +
v 12 11 2pm
(1 1), li((0) = (T- (1
1- pl
/ -1+78=2pm 1+|a
14m (VI- 2 + VI 20) and ha( (1
1-10 vI 20
1+|1
Lasso is a special case with μ = 0. By setting μ = 0 (cquivalently, 7 = p) in Theorem we obtain the phase curves for Lasso. They agree with the results in Ji & Jin 2012) (but Ji & Jin (2022) does not cover Elastic net).
To see the effect of the L Le-plllyyy, consider extreme case where μ - co. Some elementary algehra shows that (1 3 converges to the soft-thresholding of X'y at the threshold X. In other words, as μ + oo, Elastic net converges to marginal screening (i.c., select variables by thresholding the marginal regression coefficients). At the same time, when μ = 0, (1 + 2)) equals the Lasso estimate. Hence, Elastic net serves as bridge between Lasso and marginal regression. In the setting here, the phase diagram of marginal regression is inferior to that of Lasso, and so the phase diagram of Elastic net also inferior to that of Lasso. See the proposition below and Figure [
In Theorem 2 for each fixed 0 E (0, 1). μ O, (()) is monotone decreasing and converges to ULasso )), which is the upper phase curve of Lasso; as μ + Do, U(1) is mono- tone increasing and converges UMR(0) which is the upper phase curve of marginal regression. F Furthermore, when f 2. Uan((f) = Do for all 0 < 0 & 2 (Le. exact recovery is impossible to achieve matter how large is).
Proposition 1.
3.2
SMOOTHLY CLIPPED ABSOLUTE DEVIATION PENALTY (SCAD)
SCAD (ann & Li 2001 is a non-convex penalization method. For any a > 2, it defines (at-0)
a penalty
function q (0) on (0, oc) by (0) _e 9 (t)dt, where 9x X A) (a-1)A I(0 > A)).
5

---

Published as a conference paper at ICLR 2022
0 0.4
p 0.5
p= 0.7
(vieO (62 Vina V1- [Gite]a
SCAD Lass0
SOAD Lasso
Zemm ca Lave
50
30
28
9
8
0
Figure 3: Left: Phase curves of SCAD. Middle and Right: Comparison of SCAD and Lasso.
The resulting penalty function gx(+) coincides with the -penntly in (0, >] and becomes a constant in [ad, oo). Let (x = ンj (x(B))). Then, SCAD estimates 3 by
3SCAD argmin fly - x / (3)}
The following theorem is proved in the supplemental material (see Figure left panel):
Theorem 3 (SCAD). Under Models ( 33), and (4) let BSCAD be the SCAD estimator in 7 Fix a E (2, - Let X - v 2q log(p) with an ideal choice of q that minimizes the rates of convergence of the expected Hamming error. The phase curves are given by I(O) 0, and
max (h1 (1), hes 0), ho))
when p 0,
U(0)-
max {hr (1), h2 (0), h1)) h (0)}
when p O,
where (1)) = (1 + vI 2) and h1) = (1
1+
20 (1 9). h2(0) = (v
p
| x
h0(
3+p ((11-p))
1+e
1
2(1-
(1-0)
annd
1-p
1+p
(1-p)²
5+31ee) T-MA|
(1 - ))
if
1-20
3 4-4 [1
3p
1+
1-0
3+3|p p
ho(D)=
(I-1p)>²
(v
1-1Ø
1+1p
v1
0 +
I+
V1
20
2
1-#
(1+
1- pl
(0)(0)
other wise,
with
2
20
1-2|pl
1-
1-28
+
V
[(1-2111
2
+
1- 2l
1)
1-20 (++1))²
(0)
p2
(1 (e)
T-Ip
2/el
2
+
Ite
1- lol
Note that the phase curves of Lasso are given in Theorem by setting 7j = p. We compare SCAD with Lasso. When م < 0, the upper phase curve in Theorem is strictly lower than that of Lasso (see Figure[] middle and right panels). When p 2 0, the upper phase curve in Theorem BJ sometimes higher than that of Lasso. Note that we restrict a Tー|p in Theorem 3 In fact, larger a may be preferred for p 2 0. The next proposition about using an optimal a.
Proposition 2. In the SCAD estimator, we choose a² and X 24 log(p) such that (a" (a","") (0, r, p), q² (0, r, p)) minimize the rates of convergence of the expected Hamming error among all choices of (a, Let (*) be the resulting upper phase curve for SCAD. Then, (1) ULasso (1) when p 2 0, and (0) < Urassoo (0) when <
The phase curves of SCAD are insensitive to the choice of a. When a < O, the optimal a" can be any value in (2, ) When p 2 there exists a constant c c(U,p) p) such that the optimal a* is any value in (c, oc). As + oo, the SCAD penalty reduces to the L -penalty. This explains why the phase curve of SCAD the same as that of Lasso when p 2 0.

---

Published as a conference paper at ICLR 2022
p 0.5
p= 0.3
p= 0.5
Threshored Lasso
11 1.
00:11-0
Lasso
MiL A
61-400
40 -800 of
(1 y -d--
0
0
Figure 4: Comparison of the phase diagrams of thresholded Lasso and Lasso.
3.3 THRESHOLDED LASSO
Let GLasso be the Lasso estimator in (2). The thresholded Lasso estimator 3TL is obtained by applying coordinate-wii hard-thresholding to the Lasso estimator:
TTL BLasso 1[18 > th. 1sisp.
Theorem (Thresholded Lasso). Under Models [ (3) and 4.. let ÍTL be the thresholded Lasso estimator in (8) Let À = / 29 lpg(p) and v log(p) with the ideal (q. w) that minimize the
exponent of the expected Hamming erron. The phase curves are given by L(0) = 0, and
U(0) = [max (1)(0),22(0))
when p 2 0,
[max (h1(0), (2( ha())) when p < 0,
where hz (1+ -I- 0)3, h2(0) 41-2) and h2 =1+ l+|el
-
+
1-20
See Figure 4 for a comparison with Lasso (a special case of t = 0). With the flexibility of using an optimal I, the phase diagram of thresholded Lasso is always better than that of Lasso.
Theorem also gives other interesting facts about thresholded Lasso. First, the shape of phase curves much less affected by the sign of p. This differs from Lasso, Elastic net, and SCAD, for which the shape of phase curves is significantly different for positive and negative Second, the optimal À in thresholded Lasso is considerably smaller than the optimal in Lasso (it can be seen from the proofs of Theorem negatives, but the in Lasso is used to simultaneously control false positives and false negatives, hence, cannot be too small. We observe the same phenomenon in simulations; see Section 4
g and Theorem 2). This is because the X in thresholded Lasso only serves to control false
3.4 FORWARD SELECTION AND FORWARD BACKWARD SELECTION
Forward selection is a classical textbook method for variable selection. Write X = [21, 2.,.... Tpl. where H2 E R for < i i p. For any subset C {1, .........P ,P), let Pl be the projection onto the A). Given threshold > 0, the
orthogonal complement of the linear space spanned by {r; forward selection algorithm initializes with So 0 and ñn At the kth iteration, compute
argmax
If > f, compute S₁ Sg-1 U { and Fr = Ps. y. otherwise. output 3forward as the least-squares estimator restricted to S. The stopping rule of < is equivalent to measuring the decrease of the residual sum of squares. The following theorem is proved in the supplemental material:
Theorem 5 (Forward Selection). Under Models I 3 and 4 let Ilorward be the estimator from forward selection. Let /2q log(p) with the ideal that minimizes the exponent of the expected Hamming error. The phase curves are given by L(Ø) 0, and
mmax {h1(0), (1),, (0) ha( max {1r (0). ha (0). h1)))}
when 2 0,
U(0)-
when < 0,
with (0)= 0)3, h2( = 2(1-))
1-1p hz(
(1+11-20)
1-29 ha( (v 2(1 Ppl) +
1-p"
7

---

Published as a conference paper at ICLR 2022
p 0.7
p 0.4
0
Forward selection
Fsrward selection Foreard rd backward se seleciion
Forward backward selection
61--8+33-000 11--88/3-280----
Figure 5: The phase diagrams of forward selection and forward backward selection.
Forward backward selection (FB) modifies forward selection by allowing to drop variables. We use the FB algorithm in Huang et al. (2016), where the backward step is conducted after all the forward steps are finished. For threshold O, it applies entry-wise thresholding on 3forward:
FFB
forwward (fraardad > v},
isjsn
Theorem 6 (Forward Backward Selection). Under Models
(3 and ( let BFB be the estimator
from forward selection. Let = 22 log(p) and 22 log(p) with the ideal (g. u) that minimize the exponent of the expected Hamming error. When p Z O, the phase curves are given by L(0) = and
U = max (h1 (0) (2( (0)),
where hi (1) and h0) are the same as in Theorem and h2) (V1-0+V1220
When p < O.
I-p²
(1) < max (0), (0) ya (0).g4(0)) (1)),
where gi (0) = (Umin (1) + v1 9)2, 92(0) p- (d) = (v1-2 + Umin (0)) (0(
2(1-0)
(V
1-20 fain (d)
) (mmi((1) max(1, / /1-0 1-9 1-p² }. and Eiin (1) = max /2 Munin (8)
1(1)
1-1p pl
Theorem gives (+)) for p and an upper bound of it for p 0. Combining it with Theorems 55d we conclude that the upper phase curve of FB is always better than those of Lasso and forward selection (for p 0, the upper bound here is already better than (1) for the other two methods).
We remark that we did obtain the exact phase curve for < in the proof of Theorem 6 is just too complicated and space-consuming present it in the main text. However, given specific values of (V, p). we can always plot the exact phase curve using the (complicated) formulas in the supplement. In Figures [ and 5 the phase curves of FB are indeed the exact ones.
3.5 CONNECTION TO THE RANDOM DESIGN MODEL
Consider the random design mentioned in Section 1 The minimax Hamming error is H' (0, r.P) = inf, [E (8, 3)), where the infimum is taken over all methods 3 and the expectation is with respect to the randomness of (X, 2)) We can define H (1) r. in the same way for our current model 4 The minimax Hamming error is related to the statistical limit of the model setting, but not any specific method. The next theorem shows that, when n >> 8p = pi-0 (we allow both p S n and p > n), the convergence rate of the minimax Hamming error is the same under two models.
Theorem 7. Under Models ① and (3), suppose X is independent of (3, 2) and its rows are iid generated from (N, -1 Σ), with E having the same form as G in (4). Suppose n pp" with w > 1 0 (note: this allows w < 1, which corresponds to n & p). There exists a number h (0,r. such that the minimax Hamming error satisfies that H (0, r.P) = T (Orr.))) Furthermore, if we instead have X'X = Σ (i.e., model then it also holds that H* (0, r)P) = L,p² 1 (U.r.p).
SIMULATIONS
In Experiments 1-3, (n. p) (1000, 300). In Experiment 4, (n,p) (500, 1000).
8

---

Published as a conference paper at ICLR 2022
Experiment 1 (block-wist diagonal designs). We generate (X, () in (3-44) For each method, we select the ideal tuning parameters that minimize the average Hamming error over 50 repetitions. The averaged Hamming errors and its standard deviations under the ideal tuning parameters over 500 repetitions are reported below. The results are consistent with the theoretical phase diagrams (see Figure D. E.g., thresholded Lasso and forward backward selection are the two methods that perform the best; Lasso is more unsatisfactory when < 0; SCAD improves Lasso when < O.
p
1
Lasso
ThresLasso
ElasticNet
SCAD
Forward
FoBackward
0.5
0.1
1,5
11.57 (3.59)
10.48 (3.34)
11.57 (3.31)
11.72
14.88 (4.12)
13.35 (3,90)
0.5
0.1
4
1.00 (1.00)
0.42 (0.65)
1.03 (1.00)
1.00 (0.96)
0.66 (0.84)
0.51 (0.73)
-0.5
0.1
1.5
35.62 (5.09)
15.62 (4.06)
35.48 (5.64)
25.87 (5.04)
19.48 (4.61)
14.82 (3.82)
Table 1: Experiment 1 (block-diagonal designs). (n,p) (1000,300),
Experiment 2 (general designs). In the Toeplitz design, we let (X'X), = 0.7 and set (U,r) 2051, In the factor model design, we let X'X BB' diag (BB) + Lp. where entries of B E RPx2 are rid from (O, 0.6), and set (1,r) (0.1, 1.5). Same in Experiment 1, the ideal tuning parameters. The averaged Hamming errors and its standard deviations are reported below. The Toeplitz design is setting where each variable is only highly correlated with a few other variables. The factor model design is setting where a variable is (weakly) correlated with all the other variables. The results are quite similar to those in Experiment This confirms that the insight gained in the study of the block-wise diagonal design continues to apply to more general designs.
design Toeplitz
Lasso 47.15 (6.32)
Tares
ElasticNet
SCAD 24.61 (5.70)
Forward
FoBackward 22.93 (5.44) 16.13 (3.76)
22.02 (5.31)
47.40 (6.41)
30.77 (6.18)
Factor model
21.14 (4.52)
15.90 (3.87) 21.20 (4.45)
19.68 (4.23)
20.04 (4.34)
Table 2: Experiment (general designs). (n, p) (1000, 300).
Experiment 3 (tuning parameters). Fix (0,r) 1.5) and p (=:0.5) in the block-wise diagonal design. We study the effect of tuning parameters in Lasso, thresholded Lasso (ThreshLasso), forward selection (ForwardSelect). and forward backward selection (FB). (a)-(b), we show the heatmap of averaged Hamming error (over 50 repetitions) of ThreshLasso for grid of (t, A); when t 0, it reduces to Lasso. In (c)-(d), we show the Hamming error of FB for grid of (u. 1); when 0, it reduces to ForwardSelect. Cyan points are theoretically optimal tuning parameters (formulas are proofs of theorems). Red points are empirically optimal tuning parameters that minimize the averaged Hamming error. The theoretical tuning parameter values are quite close to the empirically optimal ones. Moreover, the optimal À in ThreshLasso smaller than the optimal Lasso.
3.0
1.2
0.0
1.0
45
2.0
5.0
4,0
2.0
30
4.0
160
120
320
6.0
3.6
140
26-
2.3
120
100
100
1.0
10
6.
20
(a) Lasso and LareshLasso (p- 0.5)
(b) Lasso and Threshl.sse
(c) ForwardSelect and FB (d) ForwardSelect and FB (p -0.5)
-0.55
0.5)
Figure Experiment 3 (effects of tuning parameters). In all plots, cyan points are computed from the formulas in our theory. and red points are the empirically best tuning parameters (they minimize the average Hamming еπтог over 500 repetitions). In (a)-(b), the cyan/red points with correspond to Lasso, and the other two are for thresholded Lasso. In (c)-(d), the cyan/red points with 0 correspond to forward selection, and the other two are for forward backward selection.
Experiment (p > n and random designs). Fix (n, P, 0, r) (500, 1000, 0.5, 1.5). We simulate
data from the random design setting in Theorem 7 We study the average Hamming error over 500 repetitions (tuning parameters are set in the same way as in Experiment 1). See Table 3 We have some similar observations as before: e.g., TareshLasso and FoBackward still the best two,

---

Published as a conference paper at ICLR 2022
REFERENCES
Ery Arias-Castro, Emmanuel Candès, and Yaniy Plan. Global testing under sparse alternatives:
ANOVA, multiple comparisons and the higher criticism. The Annals of Statistics, pp. 2533-2556, 2011.
Peter Bickel, acov Ritov, and Alexandre B Tsybakov. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, 37(4):1705-1 (000))770513222 2009.
Alia Dehman, Christophe Ambroise, and Pierre Neuvial. Performance of blockwise approach in variable selection using linkage disequilibrium information. BMC Bioinformatics, 16(1):1-14, 2015.
David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. The Annals of Statistics, 32(3);662-994, 2004.
David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 1299-1368991366 2006.
David L Donoho, Yaakov Tsaig, Iddo Drori, and Jean-Luc Starck. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit. IEEE Transactions on Information Theory, 58(2):1094-112) 2012.
Bradley Efron. Large-scale simultaneous hypothesis testing: the choice of null hypothesis. Journal of the American Statistical Association, 99(465):96 104, 2004.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association,
2001.
Jianqing Fan and Jinchi Lv. A selective overview of variable selection in high dimensional feature space. Statistica Sinica, 20(1):101, 2010.
Jianqing Fan and Heng Peng. Nonconcave penalized likelihood with a diverging number of parameters. The Annals of Statistics, 32(3):92--611, 2004.
Jianqing Fan, Yuan Liao, and Xiaofeng Shi. Risks of large portfolios. Journal of Econometrics, 186 (2):367-387, 2015.
Christopher R Genovese, Jiashun Jin, Larry Wasserman, and Zhigang Yao. A comparison of the lasso and marginal regression. The Journal of Machine Learning Research, 13:2107-2143, 2012.
Shiqiong Huang, Jiashun Jin, and Zhigang Yao. Partial correlation screening for estimating large precision matrices, with applications to classification. The Annals Statistics, 44(5):2018-2577, 2016.
Pengsheng Ji and Jiashun Jin. UPS delivers optimal phase diagram in high-dimensional variable selection. The Annals of Statistics, 40(1):73-103, 2012.
Jiashun Jin. Comment on "Estimating false discovery proportion under arbitrary covariance de-
pendence" by Fan al. Journal of the American Statistical Association, 107(499):1042-1045 2012.
Jiashun Jin and Zheng Tracy Ke. Rare and weak effects in large-scale inference: methods and phase diagrams. Statistica Sinica, pp. 1-34, 2016.
Po-Ling Loh and Martin J Wainwright. Support recovery without incoherence: A case for nonconvex regularization. The Annals of Statistics, (5(6):245522433 2017.
Nicolai Meinshausen and Peter Bühlmann. Stability selection. Journal of the Royal Statistical Society: Series (Statistical Methodology). 72(4):417-473, 2010.
0
r
Lasso
Threst lasso
ElasticNet
SCAD
Forward
FoBackward
0.5
0.5
1.5
16.02 (5.52)
9.83 (4.08)
13.92 (5.12)
15.98 (6.28)
11.74 (5.55)
9.84 (4.93)
-0.5
0.5
1.5
18.49 (6.03)
10.50 (4.23)
15.18 (5.64)
18.12 (6.00)
12.00 (5.67)
10.41 (5.03)
Table 3: Experiment 4 (p > and random designs).
10

---

Published as a conference paper at ICLR 2022
Xiaotong Shen, Wei Pan, and Yunzhang Zhu. Likelihood lakeee selection and sharp parameter estimation. Journal of the American Statistical Association, 107(497):223-22 -222, 2012.
Wenguang Sun and T Tony Cai. Oracle and adaptive compound decision rules for false discovery rate control. Journal of the American Statistical Association, 102(479):001-12, 2007.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 58(1):267-288, 1996.
Sara de Geer, Peter Bühlmann, and Shuheng Zhou. The adaptive and the thresholded lasso for potentially misspecified models (and a lower bound for the lasso). Electronic Journal of Statistics, 5:688 74988-74,.1 2011.
Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using L constssrae quadratic programming (lasso). IEEE Transactions on Information Theory, 55(5): 2183-2202, 2009.
Shuaiwen Wang, Haolei Weng, and Arian Maleki. Which bridge estimator optimal for variable selection? The Annals of Statistics, 48(5), 2020.
Asaf Weinstein, Weijie Su, Malgorzata Bogdan, Rina F Barber, and Emmanuel J Candès. A power analysis for knockoffs with the lasso coefficient-ddfffreecee statistic. arXiv preprint arXiv:2007.15346. 2020.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894-942, 2010.
Tong Zhang. Adaptive warkwddb greedy algorithm for learning sparse representations. IEEE Transactions on Information Theory, 57(7):4689-4708, 2011.
Peng Zhao and Bin Yu. On model selection consistency lasso. The Journal of Machine Learning Research, 7:2541-2566 2006.
Shuheng Zhou. Thresholding procedures for high dimensional variable selection and statistical estimation. Advances in Neural Information Processing Systems, 22:2304-2313 2009.
Hui Zou. The adaptive lasso and its oracle properties. Journal of the American Statistical Association, (014476):14181444 2006.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301-322 2005.


Reviews:
[{"review_id": "Xj828xW9tI5", "reviewer": "Reviewer_fogT", "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": "## Strengths\nThe paper is well written and easy to follow. Since variable selection is of importance to many, the problem is well motivated and worthy of study. The phase diagrams and insights provided in the discussion are useful for developing intuition about each method and laying a foundation for how future work might be carried out. Although I have not reviewed proofs closely, they appear to be of sufficient technical merit and illustrate the authors mettle!\n\n## Weaknesses \nThe primary weakness of the paper seems to be in the applicability to realistic problems. There is brief mention in section 2 of how the block structure can be found in the correlation matrix of genetic markers and how empirical results for Toeplitz matrices agree with the simplified theory, but little else is said. A few words motivating the use of such a simplified model with additional examples would be useful and make the paper more compelling.\n \n\n## Questions and comments:\n- Does $X^T X = I_p \\ne \\text{diag}(X^T X) = [1,1, \\dots, 1]^T$ in equation (1)? The notation is a bit unclear.\n- Consider writing \"smoothly clipped absolute deviation\" before using the acronym.\n- A few words defining the multi-log function would be helpful for a general audience.\n\n", "summary_of_the_paper": "This paper investigates the theoretical performance of a number of variables selection methods when the columns of the design matrix are correlated. They focus specifically on the case where the Gram matrix for the design is block-wise diagonal (2 x 2 blocks) with the off-diagonals within each block given by a correlation parameter and diagonals set to 1. The quality of each estimator is evaluated by using its expected Hamming distance. Extending ideas presented in _UPS delivers optimal phase diagram in high-dimensional variable selection [Ji and Jin]_ and others, phase diagrams are constructed with phase curves (derived in the appendices) establishing the boundary between each region: exact recovery, almost full recovery, and no recovery. A discussion of each variable selection method provides insight and a comparison between them is included. ", "summary_of_the_review": "Given the complexity of calculations as mentioned in the _technical novelty_ section, it isn't clear that more realistic settings can be addressed, i.e., larger blocks, more complicated correlation models, etc., with analytic phase curves. 71 pages of proofs suggest that small increases in model complexity will quickly result in prohibitively complex calculations. Although I believe the analysis of this idealized model is of sufficient interest to researchers in variable selection methods, it would be nice to know that the results can reasonably be used by a wider audience.\n\nI would like to know that the simplified block correlated model is in fact a reasonable approximation for a number of real examples or that phase diagrams for more realistic models are within striking distance. For now, I'd say the paper is marginally below the acceptance threshold and ask for the authors to further motivate the simplified model.\n\n\n====== REVIEW UPDATE ========\nBased on the authors comments, I am improving my recommendation from a 5 to a 6 provided the authors incorporate their response into the paper (I still haven't seen a revision). ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S_HoNEA02BC", "reviewer": "Reviewer_YAB8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Strong points\n\nThe article is a pleasure to read, with clearly exposed contributions. The adopted setting (“rare and weak signal” + “blockwise correlation”) is simple but very well motivated. This systematic study is comprehensive and several insights and intuitions are provided. The introduction of the Almost Full Recovery regime is interesting. Indeed, common model consistency properties can only separate the Full recovery regime from the other two.  Even though, strict model consistency does not hold, the Almost Full Recovery regime remains a useful regime to study for practitioners. The references to related works and similar settings are adequate and the work is well-placed in the literature. The experiments compliment the theoretical results.\n\nWeak points\n\nIt is not stated explicitly in the theorems of Section 3 that the expected Hamming error is of shape $L_p p^{1-h(\\vartheta, r, \\rho)}$ contrary to the theorems of the supplements. This makes statements like “[…] with an ideal choice of $q$ that minimizes the exponent $E[H(\\beta, \\hat{\\beta})]$” akward. \n\nTypos:\n\n(Main article)\n- Figure and table without number or caption (page 9).\n- Several typos in the references (inconsistent capitalisation of journal names, “et al.”).\n- Legends in figures are too small to read on a printed article.\n\n(Supplementary)\n- Equation 7 : $\\rho’$ (should be $\\rho$).\n- Lemma B.1, first bullet point : $\\lambda’$ (should be $q$).\n- Bottom of page 3 : “Figure 1 only dipicts”.\n- Page 54 $(x_j, x_{j+2})$ (should be $(x_j, x_{j+1})$.", "summary_of_the_paper": "The goal of the paper is to theoretically compare several variable selection schemes related to Lasso. To that end, the authors propose a comprehensive and visual methodology: phase diagrams. Under an idealised setting, they show that, depending on the strength and sparsity of the signal, variants of Lasso fall in one of the three following regimes, Full recovery, Almost Full Recovery, No Recovery. Their main results consist in the exact and non-asymptotic characterisation of those regimes. Once the phase diagrams are computed, the efficiency of algorithms can easily be compared. Most demonstrations rely on the fact that, under the “blockwise correlation” setting, methods can be  reduced to bivariate (Lasso-type) sub-problems.", "summary_of_the_review": "This is a solid work that will be certainly be helpful to the community, and I recommend it for publication.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "LYpIgIaMhuI", "reviewer": "Reviewer_3QXZ", "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": "Basically, I like the paper's motivation; it is quite a fundamental research problem to select unnecessary variables from a given data matrix. Besides, this paper is well structured, and the theoretical background of the proposed approach is well described in the paper. Specifically, I really appreciate that this paper theoretically revealed Hamming errors of each variable selection approach. \n\nUnfortunately, the theoretical analyses in this paper assume that n>p holds in the data matrix. However, I think variable selection approaches are especially useful in the case of n<p. So, I want to know the theoretical results in such a case.", "summary_of_the_paper": "This paper performs theoretical analyses of several variable selection approaches such as Lasso, Elastic net, SCAD, thresholded Lasso, forward selection, and forward backward selection. While the previous studies focused on the model selection consistency, this paper focused on the impassibleness of the model selection consistency based on Hamming errors. Its theoretical analyses show that SCAD has better performance than Lasso, Elastic net is worse than Lasso, and other approaches are superior to Lasso.", "summary_of_the_review": "This paper is well-written.\nTheoretical analyses for the case of n<p are needed in the paper. ", "strength_and_weaknesses": "", "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": "-1oow9o4jPC", "reviewer": "Reviewer_darD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strengths:\n1. In general, the presentation of the paper is clear. \n2. The theoretical results are carefully studied under the problem setup discussed in the paper.\n\nWeakness:\n1. The paper studied a very specific setting: \"coefficients are iid drawn from a two-point mixture and that the Gram matrix is block-wise diagonal.\" The model is generated by three parameters. In my opinion, this setting is way simpler than the model settings studied in sparse linear regression literature. This may hurt the significance of the contribution.\n\n2. The paper provides a long supplement file with proofs. However, to be honest, I did not spot many new technical contributions that are worth being commended as theoretical novelties. Besides, I am not sure if the results can be naturally generalized to more sparse linear regression settings.\n\n3. The numerical studies are limited. Only a low-dimensional setting is considered. The figure at the bottom of page 9 lacks explanations. It is not clear to me what type of applications the results in the paper can be applied to.\n", "summary_of_the_paper": "The paper compares several variable selection methods over block-wise diagonal designs. The performance is theoretically evaluated by the expected Hamming error. Some simulations are implemented to justify the empirical performance of the methods in the comparison.", "summary_of_the_review": "Correctness:\nMost of the theoretical results are well supported by the proofs in the supplement material. It is unclear if the pros and cons of the methods summarized in this paper can be generalized to more sparse linear regression setups. \n\nTechnical Novelty And Significance:\nSparse linear regression is a well-studied area. Although the authors have done a good job to deliver their theoretical results, I feel the technical novelty is limited. This paper focused on some specific settings. I also hold a conservative opinion towards its significance.\n\nEmpirical Novelty And Significance:\nAll the methods compared in the simulation study have mature algorithms to implement. The simulation is done under a low-dimensional setting (n=1000, p=300). The data generating processes are quite simple. I feel the novelty and significance of empirical studies are limited.\n\nFlag For Ethics Review:\nI do not foresee this research having any ethical issues.\n", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In the end, all reviewers agreed that this is a solid piece of work. However, there were also some doubts regarding the relevance of the block diagonal design and the underlying assumptions about the p/n ratio. The majority of the reviewers, on the other hand, had the impression that the positive aspects dominate the potential problems, and I also share this viewpoint. However, I'd like to encourage the authors to carefully address the points of criticism raised by the reviewers in their final version.
Decision: Accept (Poster)