Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
Authors: Pierre C Bellec
Yiwei Shen
Venue: NeurIPS 2021 Submitted (2021)
Keywords: M-estimators
regularization
robustness
adaptive parameter tuning
p/n->const
Huber loss
Elastic-Net

Abstract: This paper studies M-estimators with gradient-Lipschitz loss function regularized with convex penalty in linear models with Gaussian design matrix and arbitrary noise distribution. A practical example is the robust M-estimator constructed with the Huber loss and the Elastic-Net penalty and the noise distribution has heavy-tails. Our main contributions are three-fold. (i) We provide general formulae for the derivatives of regularized M-estimators $\hat{\boldsymbol{\beta}}(\boldsymbol{y},\boldsymbol{X})$ where differentiation is taken with respect to both $\boldsymbol{y}$ and $\boldsymbol{X}$; this reveals a simple differentiability structure shared by all convex regularized M-estimators. (ii) Using these derivatives, we characterize the distribution of the residual $r_i  = y_i-\boldsymbol{x}_i^\top\hat{\boldsymbol{\beta}}$ in the intermediate high-dimensional regime where dimension and sample size are of the same order. (iii) Motivated by the distribution of the residuals, we propose a novel adaptive criterion to select tuning parameters of regularized M-estimators. The criterion approximates the out-of-sample error up to an additive constant independent of the estimator, so that minimizing the criterion provides a proxy for minimizing the out-of-sample error. The proposed adaptive criterion does not require the knowledge of the noise distribution or of the covariance of the design. Simulated data confirms the theoretical findings, regarding both the distribution of the residuals and the success of the criterion as a proxy of the out-of-sample error. Finally our results reveal new relationships between the derivatives of $\hat{\boldsymbol{\beta}}(\boldsymbol{y},\boldsymbol{X})$ and the effective degrees of freedom of the M-estimators, which are of independent interest.

Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
Anonymous Author(s)
Affiliation Address
email
Abstract
This paper studies M-estimators with gradient-Lppschitz loss function regularized with convex penalty in linear models with Gaussian design matrix and arbitrary noise distribution. A practical example the robust M-estimator constructed with the Huber loss and the Elastic-Net penalty and the noise distribution has heavy-tails. Our main contributions are three-fold.
3
5
(i) We provide general formulae for the derivatives of regularized M-estimators fyy X) where differentiation is taken with respect to both y and X; this reveals simple differentiabilityy structure shared by all convex regularized M-estimators. (ii) Using these derivatives, we characterize the distribution of the residual = x; [ in the intermediate high nigh-dimensional regime where dimension and sample size are of the same order. (iii) Motivated by the distribution of the residuals, we propose novel adaptive criterion to select tuning parameters of regularized M-estimators. The criterion approximates the out-of-sample error up that minimizing the criterion provides a proxy for minimizing the -samlle error. The proposed adaptive criterion does not require the knowledge of the noise distribution or of the covariance of the design. Simulated data confirms the theoretical findings, regarding both the distribution of the residuals and the success of the criterion as a proxy of the out-of-sample error. Finally our results reveal new relationships between the derivatives of B3y. X) and the effective degrees of freedom of the M-estimator, which are of independent interest.
6
8
10
11
12
additive constant independent of the estimator,
14
16
18
19
20
Introduction
21
22 This paper studies properties of robust estimators in linear models X,8 + E with response
23 y R", unknown regression vector 3 where X is design matrix with n rows #1; Fn each row
24 I; being a high-dimensional feature vector Rp with covariance Σ. Throughout, 3 B X) be regularized M Mesttmmator given as solution of the convex minimization problem
Bly X)= = argmingeRT 1 Σr p(m x. b) (bb
(I)
28 where p RR R is a convex data-fitting loss function and g R.P IR a convex penalty. We
27 may write 3 p.g (y. X) for ( to emphasize the dependence on the loss-penaly, pair (p,g); the
28 argument (y, X) is dropped then f is implicitly understood at the observed that (y, X). Typical
29 examples of losses include the square loss p(u) = =²2/,, the Huber loss H(u) f min(1, (1, f) (//) A) for some tuning parameter A > O, while typical examples of 31 penalty functions include the Flastic-Net (b) = A \||b|| 1 + / ||b][// /2 for tuning parameters X, /4 2
30 or its scaled version H
32 The paper introduces the following criterion to select a loss-penalty pair (p.g) with small out-of- sample error // 12 for given set of candidate loss-penalty pairs {(p,g)} and the
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

34
corresponding M -estimator 3 Ag
in ①. select the pair (p.g) g) that minimizes the criterion
y X P.g
E R
df
Crit(p, = = tr [v] 1 (r) with
df = (r/((0 V diag (r) ( (()38))3 p.g)
E R,
(2)
E R
35 where tr[-] is the trace, 1 R + R is the derivative of e the derivative of to and we extend xb 36 and v/ to functions I2 IR" by componentwise application the univariate function of the same
37 symbol. Above, (0/0y)33 3 P.N E RRx= denotes the Jacobian of (T) with respect to for X fixed, 38 at the observed data y.. X). As we will see while studying particular examples, for pairs (p. g) commonly used in robust nigh-dimensional statistics such as the square loss, Huber loss with the penallyy or Elastic-Net penalty, the ratio df/ / tr [r] in 2 admits simple, closed-form expressions 41 and can be computed at negligible computational cost once Bp.g(1) (y,X) X) itself has been computed. The criterion (2) has appealing adaptivity property: it does not require any knowledge of the noise 43 E or its distribution, nor any knowledge the covariance Σ of the design.
Ite dww.eeteeeeeeeee Mefie
Figure 1: Heatmaps for 1/3 311 its approximation ||r (df (d/ -lell/
and the approximation error ||| [/ - |- ||r +
- ||e||/// for the Huber loss and Elastic-Net penalty grid of tuning parameters (A, r) where À [0.0032, 0.41]
and T E [10-10, 0.1]. Each cell the average over 100 repetitions. See Section 6 for more details.
1.1 Contributions
45 1. The end goal of paper is to provide thcoretical justification and theoretical guarantees for the criterion (2) in the nigh-dimensional regime where the ratio p/n has finite limit and X has anisotropic Gaussian distribution. The theoretical results will justify the approximation
47
r + dff tr (v(V)) /n ||=|i/n= |Σ 1/2 (2 -3)
(3)
Figure I illustraaes the accuracy of 33 on simulated data. To study the criterion (2) and derive the approximation we develop novel results of independent interest regarding M-estimators in (T):
49
2. The paper derives general formula for the derivatives (0/0y,) and (0/Or.y) ) This sheds light on the differentiability structure of Meestimators for general loss- coss-penalty pairs: for any P. g with strongly convex, there exists A E Pxx depending on (y, X) such that for almost every (y. X).
50
51
52
(0/0y.) X) Ax e, (r:), (0/3r.,) Bly
Ae,ū(r:) Ax e (ra (r.)),
53
for r; y1 - x, Vi E [n].j E [p] where e, E R and e; E 1 are canonical basis vectors.
54
3. The paper obtains stochastic representation for the residual yi - x.! 3 for some fixed i = 1,...
55
extending some results of [10] on unregularized --esimmators to penalized ones as I In
56
short, for each i 1, I,... n the i-th residual satisfies r; y: x
r; + (df/ tr (r:))) x E; + Z, 1 (3-
(4)
57
where 2; ~ (O, 1) is independent of E, This stochastic representation is the motivation for 58 the criterion 2 the amplitude of the normal part in the right-hand side is proportional the out-of-sample error 1/2 - 3I' that we wish to minimize, while the variance of the noise E; does not depend on the choice of (p, g).
59

---

61
Simulated data in Figure 2 confirms that the stochastic representation for the i-th residual r; 3/- x. [ is accurate. Our working assumption throughout the paper is the following.
Assumption 1.1. For constants H. independent of n. p we have p/n S 7, the loss p:: R IR 64 is convex with a unique minimizer at O, continuously differentiable and its derivative vb pf is 65 1 Lipschitz. The design matrix X has iid N (0, Σ) rows for some invertible covariance and the noise& E is independent of X with continuous distribution. The penalty g RP + R is u-strongly convex w.r.t. Σ in the sense that b + g(b) (u/2)bb Eb is convex in b E IP..
63
68
87
68
Throughout the paper, we consider a sequence (say, indexed by n) of regression problems with 3r, Σ and the loss-penalty pair (p: 9) depending implicitly on n. For some deterministic sequence (an). the stochastically bounded notation (a,) in this context may hide constants depending on
69
70
71
y μ only. that is, (a,),) denotes sequence of random variables Wn, such that for any > there exists K depending on (c, 71,1)) satisfying P([..) 2 Ku,)= S.
73 Since Assumption 1.1 requires p/n S 7, the Sirzano-Weierssrrass theorem lets us extract a subse-
74 quence of regression problems such that p/v n/n + 7 along this subsequence, for some constant 7. This the asymptotic regime we have in mind throughout the paper, although our results do not require a specific limit for the ratio p/n. For some results, we will require the following additional assumption which is satisfied by robust loss functions and penalty that shrink towards 0.
75
78
77
78
Assumption 1.2.
The penalty is minimized at O that is, g(O) = mimbER g(b); the loss is Lipschitz as S M for some constant M independent of n. P. the signal is bounded as in 1/ 1|2 < M.
79
in |
80
1.2
Related works
81
The context of the present work is the study of M -estimattors the regime 2 has a finite limit. This
n literature pioneered in 22, 10 15 typically describes the subtle behavior of [3 in this regime by solving a system of nonlinear equations. This system typically depends on a prior distribution for the components of [3,, and either depends the covariance Σ 7 or assume Σ Ip [2] 16 among many others]. Solutions to the nonlinear system are a powerful tool to understand |3 in theory, e.g.. to characterize the deterministic limit of || - |l, see e.g., the general results in (6) for the square loss and [6] for general loss-penalty pairs. However, since the system and its solution depend on unobservable quantity (E and prior on 3*) ), the system solution is not directly usable for practical purposes such as parameter tuning.
83
84
85
86
87
88
89
90
The present work distinguishes itself from most of this literature as the goal is to describe the behavior of 33 using observable quantities that only depend on the data (y, X) (and not unobservable ones such
81
92 as E or prior distribution on 3 that appear in the aforementioned nonlinear system of equations).
93
As we will see this view lets us perform adaptive tuning of parameters in a fully adaptive manner using the criterion (2). The criterion (2) appeared in previous works for the square loss only: [2]
94
95 studied (2) for the Lasso with Σ = I and [3] Section 3] for the square loss and general penalty
(ntee that for the square loss p(u) u² /2, (2) reduces to n² || (n dr)² due to (b))) and [ n df. The property (u) u of the square loss hides the subtle interplay between r, (r), df and tr[ in (2) for different than the square loss). A criterion different from ( is studied in [12 3 estimate the out-of- sammpe error. That criterion has the drawback require the
97
98
99
knowledge of Σ, unlike (2) which is fully adaptive.
100
This work leverages probabilistic results on functions of standard normal random variables 4 $6. $7] which are consequences of Stein's 's formula [4). Consequently, the main limitation of our work is that it currently requires Gaussian design for the probabilistic results (on the other hand, the differentiability result (5) is deterministic and does not rely on any probabilistic assumption).
102
103
104
Differentiability of regularized M-estimators
105
106
The first step towards the study of the criterion 2 is to justify the almost sure existence of the derivatives of 33 that appear in 2 through the scalar scalar df and the matrix V in (2). Although the criterion (2) only involves the derivatives of B(y, X) with respect to y for a fixed X, the proof of
107
3

---

109 our results rely on the interplay between the derivatives with respect to y and with respect to X: this
110 differentiability structure of M -eestimators the content of the following result.
111 Theorem 2.1. Let Assumption 1.1 I.I be fulfilled. For almost every (y. X) the map (y, x) + B(y X)
112 is differentiable at (y, X) and there exists a matrix A E IRPXP with |/ A 1lop - (nzn) s.t.
(0/0y, 3 X)= = Ax_ Ax,e,t(rr))
where Ti V/i 2; 3 (5)
(0/02,)) (g X) (r))(r))) Ax (.v"(r:))
113 e, E R" Gj E R canonical basis vectors, , 1/ df = tr tr| (0/00)) = tr x AX (ong(v'(r))))
of and uj denote the derivatives. Furthermore,
(6)
V diagg (r)) X (3/00)33 = diagl ( (r)) diag(& (()) di
(7)
satisfy 0 S df and 0 - tr [ S
Since the same matrix À appears in both the derivatives with respect y; and to 2íj. (5) provides relationship between (0/0y, ) and (0/0z;) )3, for instance (0/0x.) ) = (r.) - 3, )0,
115
116
Although the matrix A is not explicit for arbitrary loss- poss-penalty pair, closed-form expressions are available for particular examples such as the Flastic-Net penalty as discussed in Section
117
118
Remark 2.1. For the square loss p(u) =22/2, the differentiability fortenu ( reduce to
119
(0/0y)) B = AxTe, e,, (0/0z,) B(y X)= = Ae,(u. x x3 3) AxTe,
120 for most every (y, X) and some matrix A RPxP depending on X), since in this case wp 1.
121 In the simple case where g is twice continuously differentiable, (5) follows 4 with
À == (xT diagl diag(v((r)) + VV (33)
(8)
by differentiating the KKT conditions provided that (y, X) is differentiable, if (y)(), (()) are smooth perturbations of (y, X) with
X (byyy X13) n vV(). To illustrate why this is true,
(()) = (y, X) and & dt
= (ú. X), differentiation of X(t) (z)())
x (1)) X (I))) V (B(((()))))))))))))))))))()))( X (()) at ( = and the chain rule yields
x T (rr - x T diagtv ve (r) - x3(y. A-
de (ty(t), X (()) L=D
with Á in g This gives 5 if the penalty g is wwice-differentiable. Theorem 2.1 reveals that for arbitrary convex penalty functions including non non-differentiable ones, the differentiability structure
122
123
124
5 always holds, as in the case of twice differentiable penalty g. even for penalty functions such as
g /||b|/// /2 + X|] Al]maa(b)]]uu where mat : R -> Rddixds xd2 is linear isomorphism to the space of
125
d d2 matrices and || II is the nuclear norm: in this case by Theorem 2.1 there exists matrix
A RexP such that (5) holds although closed-form expression for À is known.
127
128
The representation (5) is a powerful tool as it provides explicit derivatives of quantities of interest such as probabilistic identities and inequalities that involve derivatives, for instance Stein's formulae [4]
X [1²² or (3 - 312 These explicit derivatives can then be used in
129
130
the Gaussian Poincaré inequalty [5] Theorem 3.20], or normal approximations B 4.
131
132
Remark 2.2. Similar derivative formulae hold if an intercept included in the minimization, as in
(Bu(y, B(y,x)) = argmin BEER V2
Σ ply: - bo - -x, b) + g(b)
(9)
Let Assumption 1.1 be fulfilled, and assume assume,uurthr (r))l > 0 with r :=:yy- 10 x. B where 1, (1,...,)) 1) E TR.. For almost every (y. X) the map (y, X) 1 Bly X) is differentiable at 1/2
133
134
(y, X), and there exists À E Roxr depending on (y. X) with |/ A 11op S (mp) such that
135
(0 X)= = Ax T w'e, (0/0x,) B(y X) Ae,u(r:) - Ax v e'e., (10) 137 where e: E R", ej E IR are canonical busis vectors, & o and v diagl (v(()) ((())'(r)) // ((())..

---

139
3
Distribution of individual residuals
We now turn to the distribution of single residual r; y/4 -x 3 for some fixed observation
141
i E {l....,?) n (for instance, fix = 1). By leveraging the differentiability structure (5) and the normal
approximation from 44, the following result provides clear picture of the distribution of r.-
142
Theorem 3.1. Let Assumption 1.1 be fulfilled and let A E TRPX be given by Theorem 2.1 Then for
143
every: I,..., n there exists Z; [0, 1) such that
144
3 111,) S
E 12 (00-)) (11)
Furthermore, if e, has a fixed distribution F, there exists bivariate variable (C) ?, converging in distribution to the product measure F @ N 1) such that
145
146
+ tr (r.) = ET + /2 33
(12)
147 If eg has a fixed distribution F and Assumption 1.2 holds then (<)())) + || = -
Thuntil Duetii
Transtal Ourdl
Figure 2: Histogram and QQ-plot for S1 in 13 under Huber Elastic-Net regression for different
choices of tuning parameters (A, r). Left Top: (0.036, 10-19), Right Top: (0.054, 0.01), Left Bottom: (0.036, 0.01), Right Bottom: (0.024, 0.1). Each figure contains 600 data points generated with anisotropic design matrix and iid e, from the /-distribution with 2 degrees of freedom. detailed setup is provided in Section 6
148
Theorem 3.1 is a formal statement regarding the informal normal approximation
C2 r; + fr Σン (b:))) E ~ 10)
(13)
(2 31]1
Simulations in Figure 2 confirm the normality of C for the Huber loss with Elastic-Net penalty and four combinations of tuning parameters. For the square loss p(u) = u²/2, because (bu)) = asymptotic normality of the residuals hold in the following form.
149
150
151
Theorem 3.2. Let Assumption hold with p(u)= = u²2 /2/2 and e ~ ((0,021,) Then for i = 1,
152
(o2 + E (2 - -3)113)-112( + tr ( - x (3) aa N(0,1)
as n + t00. (14)
153
is informative to provide a sketch of the proof Theorem 3.1 explain the appearance of vi(rt) and
154
tr ÆA] in the normal approximation results (TT) and (13). A variant of the normal approximation
of 4 proved in the supplement states that for a differentiable function f : R R (0) and
155
156
N(,, Ig). there exists Z ~ N 1) such hat
f(z) x- EL (0/00)))) (8/0zx)f(z))
21 CE El (()0)2))(())1)
E
(15)
[[(=)]] Some technical hurdles aside, the proof sketch is the following: Apply the previous display q p. Σ 1/1 conditionally on (E, (x1))=(())(()) and to f(z) >
[[(2]]1
157
158
3²) in the simple case where 3 = 0 (this amounts to performing a change of variable by translation of B to 3 -²). Then the right-hand side of the previous display negligible in probability compared to Z. and in the
( /
159
160
lend-hand side f(z)T= 2 = a. (ā ,²) and Σi_, (0/0zx) fx(2) R tr (EEA (r:)) as the second term
161
in 5 is negligible. This completes the sketch of the proof of 133
5

---

Proximal operator representation. From the above asymptotic normality results, stochastic representation for the i-th residual r; = y,, x. [3 can be obtained as follows: With prox{tp](u) the proximal operator of x: + 1p(z)) defined as the unique solution E IR of equation = + (1)(2) = n,
Ti = 1/4 z; 3 prox (E + 1B 12,)
with f = tr(
where (E), 2 converges in distribution to product measure F @ (N, 1) where F' is the law of eg.
163
4 A proxy of the out-of-sample error if Σ is known
184
The approximations of the previous sections for ri + tr [EA] (r:) and the fact that e is independent
165
of Z; (0, 1) in (TI) suggest that (r; + tr tr(=A]b(rr:) ss of + | , I1 z7; and
averaging over [l.... n one can hope for the approximation ||r + tr(EA| /n ||=|| /
167
Σ 12 3*) The following result makes this heuristic precise.
188
Theorem 4.1. Let Assumption 1.1 be fulfilled and À be given by Theorem 2.1 Then
169
13 -3*)11 +||+||/////////////// -
( |1 1100=:/00----aa00-00000000000000 0pm 1/2) Rem,
where Rem = -1 /|21//(/ - +
eh Thus
(3 33)1-1 3² + || /n = (1+ ||]
170
Theorem 4.1 provides a first candidate,
||r ir (ΣA (x) nn to estimate
E 12 - 3*) + ||=||//n.
(16)
Estimation of (16) is useful as ||=|| f is independent of the choice of the estimator 3 and in particular independent of the chosen loss-penalty pair in (I. Given two more estimators (I), choosing the
171
172
one with smallest |r tr(EArrAa (r)]] is thus a good proxy for minimizing the out-of-sample error.
173
Corollary 4.2. Let 3. be two M-estimators ① Assumption 1.1 with loss-penalty pair (p, g) and (p. 9) respectively. Assume that both satisfy Assumption I.1 and let vo = =p' and d/ = .'. Let y X3, y XB be the residuals, A, A be the corresponding matrices of size p p given by Theorem 2.7 Further assume that both estimators satisfy Assumption I.2and and that e has iid coordinates independent with E[le,|++9]= & M for constants q (0, 1), M O independent of n. P. n/((1+))). Then for any r > 0 independent of Let = X||X= 112 llpp < 2/n - VD) n nllell <
174
175
176
177
178
179
p. there exists C(T, 7, U,,,,,7,
M) > O depending only (7, 14, m, q, M) such that
P P(1E 12 3-)
Σ /2 B²)11 > n, ||r ET (r) S I tr tr ())
I C(( 7, q, M)n / + P(2) + 0.
181
Provided that the noise random variables &, have at least 1 + 9 moments, Corollary implics that with probability approaching one given two M-estimators / and B, choosing the estimator
182
corresponding to the smallest criteria among ||r + tr(EA)r and || + tr tr(EA]r leads to the smallest out-of-sample error, up to any small constant 7) > Ó. This allows noise random variables s; with infinite variance. A similar result can be obtained to select among K different M-estimators (I.
183
184
Corollary 4.3. As in Corollary 4.2 assume E|ie,| [t] M and let BI..... 3x be --ssimattors of
186
the form (1) with loss-penally pair (Pk.gk) satisfying Assumptions 1.1 and 1.2 For each k = l,... K.
187
188
let T = y-yx3x3 3 be the residuals and Au be the corresponding matrix of size pxpfrrom Theorem 2.1 Let k E argmin -..... [|r + A1EAA)arrrra where thu = Pk. Then if (7,149994 M) are
189
constants independent of n.p
190
/ -1>)|12 > ming-
/ 11 +n) 0
if o(19/(1+9)).

---

191
Given K different loss loss-penalty pairs and the corresponding Meestmmttors in T.. minimizing the criterion ||r + tr tr[EA|rrl thus provably selects a loss-penalty pair that leads to an optimal out- sf-sa error, up to an arbitrary small constant 1j > 0 independent of n, p. The requirement
193
K (nn9/(1+9) means that the cardinality of the collection of M-estimators to select from should grow more slowly than power of n. This is typically satisfied for default tuning parameter grids in popular libraries (e.g., sklearn wwwrrrl..ineee www.lninar.... _aoaarr_meee_.__ Lasso (T3 with tuning parameters evenly spaced in log-scale that consequently have cardinality logarithmic in the parameter range. The major draw of the criterion ||r + tr |r| is the dependence through tr [EA] the covariance E of the design, which typically unknown. The next section introduces an estimator of tr tr[EA] that
194
196
198
199
200
does not require the knowledge of Σ.
5 Degrees of freedom and estimating tr [ΣA] without the knowledge of Σ
This section focuses on estimating tr [[AA]] The matrix À from Theorem 2.1 can estimated from the data (y. X) in the sense that A is a measurable function of (y, X) (thanks to the observation that derivatives are limits, and limits of measurable functions again measurable). The difficulty thus to estimate tr tr[EÅ] without the knowledge of E. To illustrate this difficulty, consider Ridge regression with square loss p(u) = u² and penalty g(b) = => |bbl/// Then Bly. X) = (x X + - x T y and A in Theorem 2.1 is given explicitly by A (X X + rnI and
tr |EA tr[(G' G n 1)
where G = -X- 1/2
Above, G is random matrix with iid (N, 1) entries the value of tr [[AA] is highly dependent on the spectrum of E- In this particular case, the limit of tr (G nイΣー can be obtained using random matrix theory [+] as the limiting behavior of the Stieltjes transform of G G + - and its spectral distribution is known; however the limit of the spetral distribution depends on the spectrum of 7 This is not desirable here as we wish to construct estimators that require no knowledge on Σ. For more involved loss-penalty pairs such as the Elastic-Net in Example 66. such random matrix theory results do not apply as tr [E depends on the random support of (.
202
203
204
206
207
208
Instead, we do not rely on known random matrix theory results. With the matrix À E RPXP given by Thcorem 2.1 our proposal to estimate tr [EA] is the ratio df/ tr[V] with df and V in 6 Both R are observable; in particular they do not depend on E.
209
210
the scalar df and the matrix V
212
Theorem 5.1. Let Assumption
be fulfilled and À be given by Theorem 2.1 Then
tr Σ tr(V]/n df /nl] s C2(y.1)n 1/2
(17)
Simulations in Figure and Table confirm that the approximation tr [EA] df/ tr is accurate for the Huber loss with Elastic-Net penalty. For the square loss, v/' = and Ir [r[V] = n df so that becomes (1 - d1 + tr (EĀ)) - 1/ Ca(7, p)n and the following result holds.
214
215
Corollary 5.2. Let Assumption 1.1 be fulfilled with p(u) u²/2 and e (O, r.). Then 14p holds with L+tx(EA) replaced by (1 (1-df) d
216
(1 df (fffn(/(+ttr Æ +7 and the normality
217
For general loss p. the criterion 2 replaces tr (EAA| by df/ tr [V] in the proxy of the oft-o--sample error ||r tr (r) studied in the previous section. Thanks to (7]. this replacement preserves the good properties of ||r tr| (r)))) proved in Corollaries 4.2 and 4.3
218
220
Theorem 5.3. For k = 1,..., K, let (pt, .kk) be loss-penalty pair satisfying Assumptions T.1 and 1.2 with th = P/g. let 3g. rk. A be the corresponding M M-estimator residual vector and matrix size p x p given by Theorem
2.1 as in Corollary 4.3 and let df,- = tx diag ( and
V = diagft/ (rx))
X A diag ( (rx))) For a small constant > O independent of
n. p. say r = 0.05, define
dfx Voa (Tx)
k argmin k=I....K
Fk + (r v
subject to
(l(m) 2 n.
n1
7

---

1.0
06
0.2
8
0/
Figure 3: Above: Boxplots for df, p. n. [V. tr [EA] and tr tr[EA]] d [r in Huber Elastic-
Net regression with r 10-10 and E [0.0032, 0.41]. Each box contains 200 data points. Below:
heatmaps for df nn, tr|V tr[V//n and n/n Σ v (r(r)/n under the simulation setup in Figure detailed simulation setup given Section
The
X4
Bin
43
30
00
245
1600
3002
08
200
0.00
1000 Do
100
000
221 If E4 has 1 + moments in the sense that Bi|s S M for constants g E (0, > 0. If 222
(M, q, 17 H. 7) and ij > 0 are independent of n. p then
P (II" 1/2 (3 13)-3)111
min (((r))2
(3 - 3²) +0
i o(ne/(1+())
223
2 over grid of tuning parameters for Mestimaators with the Huber loss and Elastic-Net penalty. The criterion ( thus successful at selecting a .M-ess -eestimator with smallest out-of-sample error up to an additive constant 7, among those -eestimators indexed in (1, K} that are such that -ー= vik (rxc) 2 17. On the one hand is unclear to us whether the restriction n. Σ (rka) 2 r7. on the other hand there is a practical meaning in excluding Meestimators with small 1 >E= (Txe): For the Huber loss H = 22/2
Figure illusstaate on simulations the success of the criterion
224
226
227
228
229
im1 2i (rw:) is the number of of data points in {l....,.7 n such that the residual 81 - x fall within the quadratic regime of the loss function. Observations i {l,..., n that fall in the linear regime of the loss excluded from the fit, in the sense that for some with rk: = 8: xx, B 1, replacing Y4 by ÿr y + 1000 (or any positive value) does not change the M-estimator solution B (this can be seen from the KKT conditions directly, or by integration the derivative with respect yi (5). Thus the constraint 1 >> v (rw)) n requires that at most a constant fraction of the observations are excluded from the fit (or equivalently, least constant fraction of the observations participate in the fit). For scaled versions of the Huber loss, P=(2) = Ha (a-'u) 'u) for some a > 0, the value î = >>= (Tka)) again counts the number residuals falling the quadratic regime of the loss, i.c., the number of observations participating in the fit. The heatmaps of Figure 3 illustrate á in simulation for wide range of
for |u| < 1 and |u| - 1/2 for |u| 2 1 the quantity >
230
232
239
234
235
236
237
238
239
parameters. Similarly, for smooth robust loss functions such as (u) = v1 + u², the constraint
240
DL (*()) 2 17 requires that at most a constant fraction of the n observations are such that (FR)) < <// i.e., such that the second derivative vi is too small (and the loss en flat).
241
242
243
Theorems 2.1 3.2 and 5.1 provide our general results applicable to a single regularized M- estimator while corollaries such as Theorem 5.3 are obtained using the union bound. The next

---

245
section specializes our results and notation to the Huber loss with Elastic-Net penalty and details the simulation setup used in the figures.
248
6
Example and simulation setting: Huber loss with Elastic-Net penalty
247
248
In simulations and in the example below, we focus on the loss-penalty pair
plu; A) - A A u), g(b; A, - |||6|| + (7/2)]]6l2
(18)
249
for tuning parameters A, 7, r 2 where H(u) := u2/2 for |u| S 1 and |u| 1/2 for |u| 2 1.
Example 6.1. With (p. g) in 18 matrix A in matrix V in 7 and df in 66 we have
250
A (X ş
T diag R (r)) X
+ ntI p) Ar. 0 if i o S or j S.
V = di (r)) diag (1) (r)) X 3 diag( (2l/ x + RT (TTT X diag (r)), (19)
df xr|x s( { diag (r)((((())))))))))))))) X nt pp) -X diagf ( (r)H),
251 where S is the active set (j E [p] B3 # 0} and p is the size of S; X s is the submatrix of X
selecting columns with index in S and Ag s, is the submatrix of A with entries indexed in x S.
252
(1,
10036,11-11
(0.054, 0.01)
(0.036,
(0.024, 0.1)
df / p/n
0.31 + 0.012
0.21 + 0.0095
0.3
0.37 + 0.0093
0.31 + 0.012
0.22 + 0.0098
0.31 + 0.012
0.47 + 0.014
0/n
0.83 0.011
0.76 :: 0.014
0.83 + 0.012
0 0.012
tr[EA]
0.58 + 0.039
0.39 + 0.027
0.58 + 0.038
0.8 = 0.038
tr [EA] df/ tr [[]]
0.0019 + 0.0015
0.0015 + 0.0012
0.0021 0.0016
0.0023 0.0017
Σ /2 - -]
1.3 0.18
1.7 0.25
1.3
1.9 = 0.21
21
0.056 +
0.021 =
0.0044
0.042 = 0.97
Table 1: Simulation for Huber Elastic-Net regression under different choices of (A, (n, p) (1001, 1000). For each choice of (>, r). 600 data points are simulated with anisotropic design matrix and i.i.d. t-distributed noises with 2 degrees of freedom. A detailed setup is provided in Section
253 The identities 19 are proved in 3 $2.6]. Simulations in Figures tto 3 and Table Illustratee typical values for df, VI tr [ΣA], the out-of-sample error and the criterion 22) ñ
7 (r(r:) and
254
[ under anisotropic Gaussian design and heavy-tailed EG. The simulation setup is as follows.
256
Data Generation Process. Simulation data are generated from a linear model y = X,3 + e with anisotropic Gaussian design Σ and heavy-tail noise vector e. The design matrix X has n = 1001 rows and p 1000 columns. Each row of X is i.i.d. (0, E), with the same Σ across all repetitions, generated once by Σ = R (2p)p) with R E 22xxp being a Rademacher matrix with Li.. entries PR,, =1) 2. The true signal vector ( E R2 has its first 100 coordinates set to RR" has i.i.d. entries from the t-distribution with 2 degrees of freedom (so that Var[s.] co, i.e., 8; is heavy-tailed).
257
258
259
p² /2 //100 / VT0/10 and the rest 900 coordinates set to The noise vector
261
263
Estimation Process. Each dataset (y, X) is fitted by a Huber Elastic-Net estimator with loss lenaaty pair in (18). We focus on 2d heatmaps with respect to the two penalty parame- ters (X, r) of the penalty; to this end the Huber loss parameter A is set to A = 0.054m 1/2
284
265
and grid for (), in then set so that df/n varies on the grid from 0 to 1 (cf. the mid-
286
267
Figure 3). The Elastic-Net penalty g(b; 7) A||bll + b|| is used with (X,r) E (0.0336 10-10), (0.054, 0.01), (0.036, 0.01). (0.024, 0.1)) in Figure 2 and Table 1
dle heatmap
269 (),T) E [0.0032, 0.41] x (10-10) 100 Figure 3 and (X, r) E [0.0032, 0.041) x [10-10, 0.1 in Figure
270
More simulation results are provided in the supplementary materials.
References
272
[1] Mohsen Bayati, Murat A Frdogdu, and Andrea Montanari. Estimating lasso risk and noise level. In Advances in Neural Information Processing Systems, pages 944-952, 2013.

---

274
[2]
Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices, IEEE Transactions on Information Theory, 58(4):1997-2017, 2012.
275
276
[3] Pierre C Bellec. Out-of-sample error estimate for robust m-estimators with convex penalty. arXiv:2008. / /840, 2020.
[4] Pierre C Bellec and Cun-Hui Zhang. Second order poincare inequalities and de-biasing arbitrary convex regularizers when p/n + ",. arXiv:/912./1943. 2019.
279
280
[5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequaliries: A
281
nonasympootic theory of independence. Oxford University Press, 2013.
282
[6]
Michael Celentano and Andrea Montanari. Fundamental barriers to high-dimensional regression with convex penalties. arXiv preprint arXiv: 1903. 10603, 2019.
Michael Celentano, Andrea Montanari, and Yuting Wei. The lasso with general gaussian designs with applications to hypothesis testing. arXiv preprint arXiv:2007.137/6, 2020.
285
286
[8] Sourav Chatterjee. Fluctuations of eigenvalues and second order poincaré inequalities. Proba- bility Theory and Related Fields, 143(1):1-40, 2009.
287
288
9
David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166(3- 4):935-969 2016.
289
290
291
[10] Noureddine El Karoui, Derek Bean, Peter Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences, 115731))4557-14562 2013.
293
294
[1]]
Vladimir A Marčenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 1(4):457, 1967.
295
296
[12] Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. arXiv preprini 1811:1811.0111111 2018.
[13] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-288 2011.
299
301
302
[14] Charles M Stein. Estimation of the mean of a multivariate normal distribution. The annals of Statistics, pages 1135-1151, 1981.
303
304
[15] Mihailo Stojnic. framework to characterize performance of lasso algorithms. arXiv preprint 1333::130..729,, 2013.
305
[16] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-56 2018.
307
Checklist
309
310
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
312
313
(b) Did you describe the limitations of your work? [Yes] See Assumptions I.] and 1.2 and
314
the limitations mentioned in Section [.2]
315
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
316
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
10

---

319
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions L.n and [.2]
320
321
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary
material.
323
3. If you ran experiments...
324
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] See code in suppiementary material.
325
328
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The code is also provided.
328
329
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
331
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] It takes an Amazon EC2 server approximately 40 hours to generate all our simulation results. This is also mentioned in supplementary.
332
333
334
335
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
336
(a) If your work uses existing assets, did you cite the creators? [N/A] Simulations are implemented using Python.
338
(b) Did you mention the license of the assets? [N/A]
339
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
340
(d) Did you discuss whether and how consent was obtained from people whose data you're 'e using/curating? [N/A]
342
343
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Simulated data only.
344
5. If you used crowdsoureing conducted research with human subjects...
346
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
347
348
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
350
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
351


Reviews:
[{"review_id": "iU9JbYZaoiu", "reviewer": "Reviewer_ikDg", "summary": "Finding the right parameter when doing robust estimation is a recurring problem in the robust community. This article propose to choose the parameters in a robust regularized linear regression model by minimizing a completely data-driven criterion. This criterion is shown to be a good approximation to the out of sample error, this is also illustrated on practical experiments.", "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": "The article is clear and well written, the results are very important in the robust machine learning community as it is often a problem to tune the estimators to a specific dataset. Most tuning procedures require knowledge on the variance of the inliers or a large computational effort (for instance through Lepski's method). In this article, the tuning is computationally tractable and the theory prove that this tuning is efficient with respect to the out of sample error.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main use for M-estimator is in robust statistics, however there are some limitations for the use of these results in robust statistics.  The article suppose Gaussian design matrix which is rather restrictive in practice and which shows that this article is about robustness in the target space but not in the feature space. A very important extension of this work would be when the design is heavy-tailed. Similarly, even though the error $\\varepsilon$ can be anything as long as its distribution is continuous, there cannot be outliers because the outliers would change the $\\beta^*$ and the criterion would then be non robust (for instance . This is a limitation for use in robust machine learning), this article is only valid for Gaussian design and uncorrupted, heavy-tailed target variable $y$.  This can be seen by the fact that the criterion depends on $r$ and if $y$ is corrupted or $X$ is corrupted, there can be some very large values of $r$.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hTXrNxgVcJR", "reviewer": "Reviewer_A6hk", "summary": "This paper studies the derivatives of regularized M-estimators and distribution of the residual. \nThese results give rises to a new novel adaptive criterion for tuning loss and penalty function.\nNumerical experiments are conducted on various models to validate the theoretical result.", "questions": "", "limitations": "", "rating": 6, "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": "This paper is well-written and mostly clear.\nThe theory and method in this paper has many benefits, including general loss and penalty, $\\Sigma$ and $\\varepsilon_i$ agnostic criterion.\nI am not an expert in this area and cannot judge the novelty and significance.\n\nQuestion:\n1. In the Theorem 3.1, it says $Z_i\\sim N(0,1)$, but the dependency between $Z_i$ and $X$ is not clarified. Is it better to say  $(X_1,...,X_n,Z_i)\\sim \\otimes_{i=1}^n N(0,\\Sigma)\\otimes N(0,1)$ to explicitly show the dependency?\n2. In line 417, how Proposition 7.1 is applied in the proof?\n\nUPDATE: I thank the authors for addressing my questions and I decided to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This article clearly describes the assumptions needed for each theoretical result.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 day"}, "extra_text": {}}, {"review_id": "h3A17cUfQyd", "reviewer": "Reviewer_kzqs", "summary": "The paper is dedicated to the analysis of robust linear regression, where the proposed estimation is based on sparse M-estimation. The statistical criterion corresponds to a penalised M-estimation problem, where both the non-penalised loss function and penalty function are assumed convex. The contributions of the paper can be summarised as follows:\n- the authors provide a criterion for the optimal selection of the non-penalised loss and penalty function so that some out-of-sample distance, say D, is minimal. \n- the authors quantify the behaviour of the penalised estimator \\hat\\beta using quantities depending on the observations only (idest no unknown quantities such as true sparse support) in a regime where p/n has finite limit.\n- some explicit derivative formulas of the penalised estimator are provided. \n- the distribution of the estimated residuals is provided, which allows for a selection of the tuning parameter for regularization.\n- the authors derive an approximation formula of the distance D. \n", "questions": "", "limitations": "", "rating": 7, "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": "As a general comment, the idea of proposing a criterion for an optimal choice of both penalty and loss functions is interesting. There was an effort to derive theoretical results. That being said, I would have several concerns. I hope my comments will be useful.\n- On the clarity: \n1) I feel there is a significant lack of details supporting the underlying motivation and intuition of the proposed methodology. What is clearly the purpose? Do the authors aim at selecting a penalty function so that variable selection can be satisfied in a high-dimensional regime? Or rather than interpreting the model, do the authors aim at gaining prediction accuracy? \n2) On the related works: the authors mention in the abstract \"adaptive criterion to selection tuning parameters of penalised M-estimators\". In the rest of the paper, I would have expected to find some theoretical results giving some explicit rates of \\lambda to ensure the consistency of the penalised parameter. With this in mind, Loh's work (2017, \"Statistical consistency and asymptotic normality for high-dimensional robust M-estimators\") treated the problem of robust estimation with sparsity assumption and proposed a penalised M-estimation setting with non-convex penalisation. It would be relevant to discuss this further.\n3) The simulation experiment seems like an afterthought and lacks further explanations: what properties of the proposed methodology are illustrated by the simulations?  \n- On the model assumptions: the key assumption is the convexity of both the loss function and the penalty function. The problem of convex penalty functions is that they do not provide good performances in terms of bias and variable selection. There are two ways to solve this issue: considering a two step procedure for incorporating stochastic adaptive weights in the penalty and alter the rate of \\lambda; considering non-convex penalty functions as in Loh (2017). Should a non-convex penalty be chosen, the theoretical analysis might probably be altered. Would it be possible to consider non-convex penalty functions? How would it change the theoretical framework? \nI am also wondering if this would be possible to relax the convexity of the loss function (which is not guaranteed especially in a high-dimensional regime) and assume alternative regularity conditions (such as restricted eigenvalue conditions).\n- On the theoretical results:\nThe authors stated in Section 1.2 that their work is within the regime \"p/n ---> finite limit\". In assumption 1, the authors assume p/n <= \\gamma, for \\gamma >0. In theorem 3.2., a large sample distribution is provided when n --> \\infty. How is the dimension p treated? Does the theorem hold when n,p --> \\infty with the scaling behaviour p/n --> \\gamma? It would be relevant to discuss this issue further.\nIn Theorem 3.1, the matrix \\hat{A} is given by Theorem 2.1: there, a specific assumption is stated on \\|\\Sigma^1/2 \\hat{A} \\Sigma^1/2\\|_op: such quantity depends on the dimension p; how does the inequality \\|\\Sigma^1/2 \\hat{A} \\Sigma^1/2\\|_op <= 1/(n\\mu) behave with respect to p? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors proposed a interesting way to specify a criterion for loss/penalty functions and their method is supported by some theoretical results. Please see my comments above concerning the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Approximately 6.5 hours"}, "extra_text": {}}, {"review_id": "7rCwRvIGjSv", "reviewer": "Reviewer_eMyT", "summary": "This paper studies M-estimators in linear models, with convex and gradient-Lipschitz loss function and a convex penalty. \n\nMain contributions: \n1. The authors provide a criterion to select tuning parameters (the loss function and the penalty function) of M-estimators, such that minimizing the criterion provides a proxy for minimizing the out-of-sample error, since the criterion is an approximation of the out-of-sample error up to a constant shift. One advantage of this criterion is that it does not require the prior knowledge of the covariance matrix of the design and the noise distribution. \n2. The authors provide simulation results that confirm theoretical findings.", "questions": "", "limitations": "", "rating": 5, "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": "The paper is well organized. Some comments:\n\n1. The criterion in Eq (2) exists for general $(\\rho, g)$, while in the experiments it is only used for tuning the parameter with Huber loss and with Elastic-Net penalty. Some related questions on this: (1) If there exists an optimal estimator $\\hat{\\beta}$ that minimize the out-of-sample error? Does it has the form as Eq (1) for some $(\\rho_0, g_0)$? (2) If the answers to (1) are both 'yes', is it possible to show that $(\\rho_0, g_0)$ minimizes the criterion (over some space of $(\\rho, g)$)?\n2. The simulation part demonstrates how the criterion is calculated and its approximation accuracy of the out-of-sample error. One important missing part is the comparison with other parameter tuning methods: could this method outperform other parameter tuning methods?\n3. The simulations in the appendix suggests that the results generalize to non-Gaussian design. What is the main technical difficulty of extending the results to non-Gaussian design?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "31Q2JMbIm1", "reviewer": "Reviewer_nTec", "summary": "The authors study M-estimators with convex penalties. They give algebraic forms for derivatives of the estimator with respect to response $y$ and the design matrix $X$. They describe the distribution of residuals or certain functions of residuals. Given a loss function and penalty (with tuning parameters) they propose a criterion that can effectively approximate the out-of-sample error. This criterion can be computed without the knowledge of the covariance matrix $\\Sigma$ (rows of $X \\sim N(0,\\Sigma)$). They give finite sample bounds that show how fast the criterion converges to the out-of-sample error. \n\n", "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": "The main results are all interesting. The manuscript sets up and explains the results in good detail. \n\nFollowing are some limitations of the work. The design matrix $X$ is assumed to have Gaussian rows. This may not be true in practice, and it is not clear how good the criterion is without this assumption. The penalty $-\\beta^T \\Sigma \\beta$ is assumed to be strongly convex. Therefore the results are not applicable when the estimator uses $\\ell_1$ type of penalties.\n\nEven with these limitations, the contributions are significant.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I cannot see any negative societal impact due to this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agree that the paper makes interesting contributions to the field of high-dimensional statitics. The authors provided informative answers to the questions raised by the area chair and the reviewers as well. The area chair has a positive view of the paper as well and believes that the paper should be eventually published at Neurips or similar venues. However, the paper suffers from a weakness; It missed some of the related work that seemed quite related to the contributions of the paper. The authors provided interesting conceptual comparisons in their response to the reviewers' comments. However, for the following two reasons the paper is rated below the other papers presented at Neurips:

1. A proper and more detailed comparison with related work should be part of the original paper so that all the reviewers can judge the paper better. 

2. A more quantitative and numeric comparison is required to help reviewers see how the paper's contributions are compared with the existing methods. 

Based on these issues, the reviewers and the area chair have rated this paper slightly below the other papers that have been accepted at Neurips. However, we would like to encourage the authors to submit this paper to future venues. It seems that the paper can become a major contribution to the field of high-dimensional statistics. 
Decision: Reject