Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression
Authors: Ayoub El Hanchi
Murat A Erdogdu
Venue: NeurIPS 2023 poster (2023)
Keywords: Excess risk bounds
Linear regression
Lp-norm
Fast rates

Abstract: We study the performance of empirical risk minimization on the $p$-norm linear regression problem for $p \in (1, \infty)$. We show that, in the realizable case, under no moment assumptions, and up to a distribution-dependent constant, $O(d)$ samples are enough to exactly recover the target. Otherwise, for $p \in [2, \infty)$, and under weak moment assumptions on the target and the covariates, we prove a high probability excess risk bound on the empirical risk minimizer whose leading term matches, up to a constant that depends only on $p$, the asymptotically exact rate. We extend this result to the case $p \in (1, 2)$ under mild assumptions that guarantee the existence of the Hessian of the risk at its minimizer.

Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression
Ayoub El Hanchi
Murat A. Erdogdu
University of Toronto & Vector Institute aelhan@cs, toronto. edu
University of Toronto & Vector Institute erdogdu@cs toronto.. edu
Abstract
We study the performance empirical risk minimization on the p-norm linear regression problem for E (1, oo). We show that, in the realizable case, under no moment assumptions, and up to distribution-dependenn constant, (d) samples are enough to exactly recover the target. Otherwise, for E [2, oo), and under weak moment assumptions on the target and the covariates, we prove a high probability excess risk bound on the empirical risk minimizer whose leading term matches, up to a constant that depends only on p. the asymptotically exact rate. We extend this result to the p (1, 2) under mild assumptions that guarantee the existence of the Hessian of the risk at its minimizer.
Introduction
Real-valued linear prediction is fundamental problem in machine learning. Traditionally, the square loss has been the default choice for this problem. The performance of empirical risk minimization (ERM) on linear regression under the square loss, as measured by the excess risk, has been studied extensively both from an asymptotic [Whi82: LC83; Vaa98] and a non-asymptotic point of view [ACII; HKZ12; Olil6; LM16; Saul8; Mou22]. An achievement of the last decade has been the development non- non-asymptotic excess risk bounds for ERM on this problem under weak assumptions, and which match, up constant factors, the asymptotically exact rate.
In this paper, we consider the more general family of p-th power losses + |t| for user-chosen p E (1, :0). Under mild assumptions, the classical asymptotic theory can still be applied to ERM under these losses, yielding the asymptotic distribution of the excess risk. However, to the best of our knowledge, the problem of deriving non-asymptotic excess risk bounds for ERM for remains open, and, as we discuss below, resists the application of standard tools from the literature.
oo) (2)
Our motivation for extending the case p = 2 to E (c) is twofold. Firstly, the freedom in the choice of p allows us better capture our prediction goals. For example, might only care about how accurate our prediction is on average, in which case, the choice = 1 is appropriate. At the other extreme, we might insist that we do as well as possible on subset of inputs of probability case the choice p = oo is best. A choice of E (1, oc) therefore allows us to interpolate between these two extremes, with the case p offering balanced choice. Secondly, different choices of p have complementary qualities. On the one hand, small values of p allow us operate with weak moment assumptions, making them applicable more general cases. On the other, larger values of yield predictions whose optimality is less sensitive to changes in the underlying distribution: for p = oo, the best predictor depends only on the support of this distribution.
which
To sharpen our discussion, let us briefly formalize our problem. There is an input random vector X IR and output random variable E R. and we are provided with i.i.d. samples (X,, Y)) We select set of predictors to be the class of linear functions {ar (we, .r) w E IRd). and choose value p E (1, oo) with the corresponding loss (t) : pppppppp 1)]. Using this loss, we define
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the associated risk and empirical risk, respectively, by
1 n n Σ
Rp(w)= == Elep((w, = - Y)
Rp, (w)
Epl(w, Xi) Yi).
We perform empirical risk minimization Wp E arginn (p.((w), and our goal is to derive high probability bounds on the excess risk (2p))) Rp(wp) where wo is the risk minimizer. For efficient algorithms for computing an empirical risk minimizer Wp we refer the reader to the rich recent literature dealing with this problem [BCLL18; AKPSI9; APS19; JLS22J.
To see why the problem we are considering is difficult, let briefly review some of the recent literature. Most closely related to our problem are the results of [AC11; HKZ12: Oli16; LM16], who derive high probability non-asymptotic excess risk bounds for the case p 2. The best such bounds are found in Oliveira [Oli16] and Lecué and Mendelson [LM16], who both operate under weak assumptions
(X, Y). requiring most the existence of fourth moments of Y and the components X of X for j E [d]. Unfortunately, the analysis in Oliveira [Oli16] relies on the closed form expression of the empirical risk minimizer 1i2, and therefore cannot be extended to other values of p. Similarly, the analysis in Lecué and Mendelson [LM16] relies on an exact decomposition of the excess loss ( x) Y) b2 (u x) Y) in terms of "quadratic" and "multiplier" components, which also does not extend to other values of p.
To address these limitations, the work of Mendelson [Men18] extends the ideas of Mendelson [Men14] and Lecué and Mendelson [LM16] to work for loss functions more general than the square loss. Roughly speaking, the main result of Mendelson [Men18] states that as long the loss is strongly convex and smooth in a neighbourhood of 0, the techniques developed by Mendelson [4] can still be applied obtain high probability excess risk bounds. Unfortunately, the loss functions (t( are particularly ill-behaved in precisely this sense, as (t) - O when t -> 0 for p > 2, and (t) - 0o as + 0 for p E (1, This makes the analysis of the excess risk of ERM in the case p E (1, oo) \ {2} particularly challenging using well estabbishdl methods.
Contrary to the non-asymptotic regime, the asymptotic properties of the excess risk of ERM under the losses (t(t) are better understood [Ron84; BRW92; Nie92; Are96; HS96; LL055, and can be derived from the more general classical asymptotic theory of M-estimators [LC83; VW96; Vaa98] under mild regularity conditions. In particular, these asymptotic results imply that the excess risk of ERM with samples satisfies
E ViVlluu
x) 1> M=!
[[Rp(Upp)] - Rp((1,)
71
002
2n
where H, R² (w;) is the Hessian of the risk at its minimizer. We refer the reader to the discussions in Ostrovskii and Bach [OB21] and Mourtada and Gaïffas [MG22] for more details. As we demonstrate in Theorem I, the rate of convergence of ERM for the square loss derived in Oliveira [Oli16] and Lecué and Mendelson [LM16] matches the asymptotic rate (1) up to a constant factor. Ideally, we would like our excess risk bounds for the cases p E (1, oo) \ {2) to also match the asymptotic rate (1), although it is not yet clear how to derive any meaningful such bounds.
In this paper, we prove the first high probability non-asymptotic excess risk bounds for ERM under the p-th power losses (t) for any E (1, oo) \ (2). Our assumptions on (X, Y) are weak, arise naturally from the analysis, and reduce to the standard ones for the case p = 2. Furthermore, the rate we derive matches, up to a constant that depends only on the asymptotically exact rate (1).
We split the analysis in three cases. The first is when the problem is realizable, i.e. Y (w", XX) for some w" E Rd. This edge case is not problematic for the analysis of the case discussed above, the (() losses are ill-behaved around for p E (1, x)) (2), requiring us to treat this case separately. The second case is when the problem is not realizable and p E (2, x)). The final case is when the problem is not realizable and p E (1, 2), which turns out to be the most technically challenging. In Section 2, we present our main results and in Section 3, we provide their proofs.
2, but as
We denote the components of the random vector X E 12d by X for j [d]. We assume the support of X is not contained in any hyperplane, i.c. P( This is without loss of generality as discussed in Oliveira [Oli16] and Mourtada [Mou22]. For a positive semi- mefiniefi matrix A, we denote the bilinear form it induces on IR by (+ A, and define
Notation.
0) = only if w = 0.
Il+IlA == V). A. We define Hp. == 42 Rp.n(w

---

2
Main results
In this section, we state our main results. We start in Section 2.1 where we introduce constants that help us formulate our theorems. In Section 2.2, we state the best known results for both the case p = 2 and the realizable case where (w= X). Finally, in Section 2.3, we state our theorems.
2.1 Norm equivalence and small ball constants
To state our results, we will need to define two types of quantities first. The first kind are related to norms and their equivalence constants, which we will use in the analysis of the non-rcalizable case. The second are small ball probabilities, which we will use in the analysis of the realizable case.
We start by introducing the following functions on our space of coefficients Rd For p.g E (1, define, with the convention oc l/p- := do for all p E (1),
| == El[ xyp/
|| | == Bi]| [(w 11/9,
(2)
As suggested by the notation, under appropriate moment assumptions on X, these functions are indeed norms on Fd In that case, we will be interested in norm equivalence constants between them
|ullee |
Ca- := sup
of = C((s (LPPp))
where a and b stand for one of IP or (I9, p)) Let us note that since we work in a finite dimensional vector space, all norms are equivalent, so that soon the quantities defined in (2) are indeed
norms, the constants defined in (3) are finite. Furthermore, as suggested by the notation, of may be
viewed as the maximum second moment of the random variables || ((wg,) over the unit
sphere of I|-111...pp- Finally, we record the following identities for future use
|| 1t,pp ||]|| Hrp
|| 22.2 ||w||
of = C 14,12
(4)
The first identity holds by linearity, and the second by noticing that V ((w, - -Y) = XXX.
We now turn to small ball probabilities. We define the following functions on Rd, for E (0),
po (w) := P( X) = 0),
(u x)) : P([(w, > <||w]|[=)).
(5)
Assumptions the functions Po and p2 have been used extensively in the recent literature, e.g. [Men14; KM15; LM17a; LM17b; Men18; LM18; Mou22]. In particular, a standard assumption postulates the existence of strictly positive constants So. and (32, R2) such that po(w) S 1 8g and Py(w, x2) 2 32 for all w E Rdd Conditions of this type usually referred to as small ball conditions. Efforts have been made to understand when these conditions hold [Men14; RV15; LM17b] as well as reveal the dimension dependence of the constants with which they do [Sau18] Here we prove that such conditions always hold for finite dimensional spaces. We leave the proof of Lemma to Appendix B to not distract from main development.
Lemma 1. Po is upper semi continuonssusus. Furthermore, for some q E (o), E[| [9] < oc for all j E [d], then Py(t, K)) is lower semi-continuout for any K 2 O. Moreover, for all K E (0,1)
=
sup wERd\HO)
po(w) <
inf Pr(w, x) 0. wEB"((0)
2.2 Background
To better contextualize our results, we start by stating the best known high probability bound on ERM for the square loss, which we deduce from Oliveira [0li16] and Lecué and Mendelson [LM16]. Theorem (Theorem 4.2, Oliveira [Oli16]: Theorem 1.3, Lecué and Mendelson [LM16]). Assume that F do and F[(X))*1 < oo for all j E [d]. and let E (0, If
n 2 196 + 2 llg(4/5)),
then, with probability at least 1 -
16 V2, 82 (wwg, X) 1 H
(1 Rs (2(w5)
nō
3

---

Up to constant factor and the dependence on 6, Theorem 1 recovers the asymptotically exact rate (I). Let us briefly comment on the differences between Theorem and the comparable statements in the original papers. First, the finiteness of o3 is deduced from the finiteness of the fourth moments of the components of X, instead of being assumed as in Oliveira [Qli16] (see the discussion in Section 3.1 in Oliveira [Oli16]). Second we combine Theorem 3.1 from [Oli16] with the proof technique of Lecué and Mendelson [LM16] to achieve slightly better bound that the one achieved by the proof technique used in the proof of Theorem 4.2 in Oliveira [Oli while avoiding the dependence on the small ball-constant present in the bound of Theorem 1.3 Lecué and Mendelson [LM16], which is known to ineur additional dimension dependence in some cases [Sau18].
We now move to the realizable case, where Y (x) so that w; = w for all p oo). We immediately note that Theorem 1 is still applicable in this case, and ensures that we recover w exactly with no more than n = (a))d) samples. However, we can do much better, while getting rid of all the moment assumptions in Theorem 1. Indeed, it is not hard to see that uip * w² only if for some w E R {0), (w, x;) = 0 for all E [n]] (taking w t0p w works). The implicit argument Theorem then uses the pointwise bound (see Lemma B.2 in Oliveira [Oli16]
P(n=- Xt) 0}} S exp
20
and uniformizes over the 1,² unit sphere in R&, where the I,2 norm is as defined (2). However, we can use the much tighter bound p" where p is as defined in Lemma 1. To the best of our knowledge, the realizable case has not been studied explicitly before in the literature. However, with the above considerations in mind, we can deduce the following result from Lecué and Mendelson [LM17b], which uniformizes the pointwise bound we just discussed using a VC dimension argument.
Theorem 2 (Corollary 2.5, Lecué and Mendelson [LM17b]). Assume that there exists w² E TRd such that = (w", X). Let E (0, 1]. If
n 2 0 d log
(1 p)2
then for any p oo), up = w" with probability at least
2.3 Results
We are now in position to state our main results. discussed in Section 1, the (,(1) losses have degenerate second derivatives t O. When the problem is realizable, the risk is not twice diffcrentiable at its minimizer for the cases p E (1,2), and is degenerate for the cases p E (2, oc). want bounds of the form (1), we must exclude this case from our analysis. Our first main result is a strengthening of Theorem 2, and relies on a combinatorial argument to uniformize the pointwise estimate discussed in Section 2.2.
Theorem 3. Assume that there exists u² E IRdd such that (w*, X) = Y. Then for all 2 d, and for all E os), we have
P(ic 4 w²) S ( (d dd pa pa-d+l
where p is as defined in Lemma 1. Furthermore, if
O (d + log(1 (15)/ log(1/p))
if 0 0s
o + log(1/))
if ssspe
2
/
(log(1/(1 - p)) + log 1-
is e1/e <p<l
then with probubility at least 1 - 5, wp = w².
Comparing Theorem 2 and Theorem 3, we see that the bound on the number of samples required to
reach a confidence level 5 in Theorem 3 is uniformly smaller than the one in Theorem 2. The proof of Theorem 3 can be found in Appendix C.
We now move to the more common non-realizable case. Our first theorem here gives non-asymptotic bound for the excess risk of ERM under a p-th power loss for p E (2, oo). To the best of our knowledge, such result is known in the literature.

---

Theorem 4. Let p E (2) and E (0, 1]. Assume that no E R2 satisfies Y = (). Further, assume that EP] < cc, 1P < co, and El (wg X) 1| (X2)4 < oa for all j E [d] If
n z 1960 + log(4/6)),
then with probability least 1 8
2048p² E ( X) x)
Rp(mg)) - Ro(w()) -
nd
p/2
512p" E
V IV Vep((ur (m
1)1
115
nd
where we used cp to denote (12 as defined (3).
Up to a constant factor that depends only on p and the dependence on 6, the bound of Theorem is precisely of the form of the optimal bound (1). Indeed, a 2, the second term is ol1/n). At the
level of assumptions, the finiteness of the p-th moment of Y and the components of X is necessary to ensure that the risk Rg is finite for all w E R The last assumption E[[Y (w | ()) (X')) oo is natural extension of the fourth moment assumption in Theorem In fact, all three assumptions in Theorem 4 reduce to those of Theorem as - 2. It is worth noting that the constant Cp has the alternative expression suPwerd (o) || fi|| _r,, } by (4), i.e. it is the norm equivalence constant that Cp
p - 2. As - oc, Cp grows, and we suspect in a dimension dependent way. However, this does not affect the asymptotic optimality of our rate Cp only enters an o(1/n) term in our bound.
between the L" norm and the norm induced by Hp. Using again (4),
We now turn to the case of p E (1, where we need a slightly stronger version of non-realizability. Theorem 5. Let p E (1,2) and 6 E (0, 1]. Assume that P(Kw X) 212-P > 0) = and
El (un. X) 222((-2)) < co. Further, assume that E[ < oc, E[(x+)*] co, El X) 2 ( < oo for all j E [d. If
n 2 1966 (d d log( log(4/6))
then, with probability at least 1
32768 E VVp(( -))
1|
(1(()p) - Rp(w - p
nd
1/(x-1)
2097152 E
Vlp X) 101
H 07 00
2 Pop
nō
where we used ep to denote EJJy - ())(-X)2((-2)) and o, :- TT(,H where Σ = E E[XX]]
Just like the bounds of Theorems and 4, the bound of Theorem 5 is asymptotically optimal up to constant factor that depends only on p. Indeed, since < < 2, 1/(p-11(p))) 11p > 1, and the second term is o(1/n). At the level of assumptions, we have two additional conditions compared to Theorem 4. First, we require the existence of the second moment of the covariates instead of just the p-th moment. Second,
require stronger version of non-realizability by assuming the existence of the 2(2-p) - p) negative moment of Kw,, X)- - Yl. In the majority of applications, an intercept variable is included as a covariate, i.c. X = I, so that this negative moment assumption is already implied by the standard assumption E[JY - ( (() variable not included, any negative moment assumption on (w X) Y| can be used instead, at the cost of a larger factor in the o(1nz) term
2) (X*)*] < co. In the rare case where an intercept
Finally, it is worth noting that for the cases E [1. 2). there are situations where the asymptotic bound (1) does not hold, as the limiting distribution of the coefficients ui as n - oc does not necessarily converge to Gaussian, and depends heavily on the distribution of (wi. X) Y, see e.g. Lai and Lee (O) and Knight [Kni98]. Overall, we suspect that perhaps a slightly weaker version of our assumptions is necessary for fast rate like (1) to hold.
5

---

3 Proofs
3.1 Proof of Theorem
Here we give a detailed proof of Theorem 1. While the core technical result can be deduced by combining results from Oliveira [Oli16] and Lecué and Mendelson [LM16], here we frame the proof in way that makes it easy to extend to the cases p E (I, 20), and differently from either paper. We split the proof three steps. First notice that since the loss quadratic function of w. we can express it exactly using a second order Taylor expansion around the minimizer w
1
fe((w, X)- Y) ( x) Y) (Vl2((5,, -), w- w + I| wi ((og
Taking empirical averages and expectations of both sides respectively shows that the excess empirical risk and excess risk also admit such an expansion
(w)) R2,((w)) (V V22,,a (wz), w -w + 1
2 I1100 w willita.
(2(w) - (25) = 2 1| - wi willaa
(6)
where in the second equality we used that the gradient of the risk vanishes at the minimizer w Therefore, to bound the excess risk, it is sufficient bound the norm || - will This is the goal of the second step, where we use two ideas. First, by definition, the excess empirical risk of the empirical risk minimizer satisfies the upper bound
m2 (12)) - (w))) S 0.
Second, we use the Schwartz inequality lower bound the excess empirical risk by
R2,n(12) - R2, (w)) 2 - V (102 (10))
-=rll + 11
will Ha.n"
(8)
and we further lower bound it by deriving high probability bounds on the two random terms || R2,nn, (wg)),) and ||t0y w The first can easily be bounded using Chebyshev's in- equality and the elementary fact that the variance of the average of i.i.d. random variables the variance of their common distribution divided by n. Here we state the result for all p E (1, oo); the straightforward proof can be found the Appendix D.
Lemma 2. Let p (1, If E (1,2), let the assumptions of Theorem 5 hold. Then with probability at least 8/2
R (w,.(1))) S 2E Vl Vep((ug. - Y)1l, x)11,,-1/(m))
For the second random term || - w we use Theorem 3.1 of Oliveira [Oli16], which we restate here, emphasizing that the existence of fourth moments of the components of the random vector is enough to ensure the existence of the needed norm equivalence constant.
Proposition 1 (Theorem 3.1, Oliveira [Oli16]). Let Z E Rd be a random vector satisfying B[23] < oo for all [d] and assume that P((r, Z) 0) only if O. For p E (0) and u E Rd define
| := E[((v, Mr,
a² =
|| |101lz//1o||10>)
sup (ER
Let (Z.) be i..dd. samples of Z. Then, with probability at least 5, for all E Rd.
d + 2 log (2/8)
c, 2,) > 1 1 117Tay
Toy
||e|
1=1
Using this result we can immediately deduce the required high probability lower bound on the second random term |t0 wg]
1|
li... we leave the obvious proof to Appendix D.

---

Corollary 1. Under the assumptions of Theorem 1, if n 2 1960 + 2 2log(4/))) then with probability at least - 8/2, 2, for all w E Rdd
1 2 2211 willit..
I w wallit...
Combining Lemma 2, Corollary 1, and (8) yields that with probability at least 1 - 8
R2,n(102) R2,n (15) 2 -v / 2 (Vep(( X) 1)1 ((00)
1
- /1o2-wáll1 m2 + w 1t..
(9)
Finally, combining (7) and (9) gives that with probability at least -
|00g - w lm S / 2E V - -) -X)),,,)),)) ((nd).
Replacing in (6) finishes the proof.
3.2 Proof Sketch of Theorem 4
The main challenge in moving from the case p to the case p E (2, 00) is that the second order Taylor expansion of the loss is no longer exact. The standard way to deal with this problem is to assume that the loss is upper and lower bounded by quadratic functions, i.e. that it is smooth and strongly convex. Unfortunately,
discussed in Section 1, the lp loss is not strongly convex for any p > 2, so we need to find another way to deal with this issue. Once this has been resolved however, the strategy we used in the proof of Theorem 1 can be applied almost verbatim to yield the result. Remarkably, a result of [AKPS22] allows us to upper and lower bound the p-th power loss for p (2, oo) by its second order Taylor expansion around point, up some residual terms. An application of this result yields the following Lemma.
Lemma 3. Let p o0). Then:
Rgn(ww) (y)(( 2
8(p ||u w + (V Ryg (wz), w wi))
(10)
2p
Rp(w)= - Rp(w)) S
(p - 1) w w- wflli,,, + po1lw - 1.....
(11)
Up constant factors that depend only on p and an L norm residual term, Lemma 3 gives matching upper and lower bounds on the excess risk and excess empirical risk in terms of their second order Taylor expansions around the minimizer. We can thus use the approach taken in the proof of Theorem I to obtain the result. The only additional challenge is the control of the term 1 willt.. which we achieve by reducing to an || - w Hp term using norm equivalence. A detailed proof of Theorem 4, including the proof of Lemma 3, can be found in Appendix E.
3.3 Proof Sketch of Theorem 5
The most technically challenging case is when E (1, Indeed as seen in the proof of Theorem 1, the most involved step is lower bounding the excess empirical risk with high probability. For the case p E [2, 00), we achieved this by having access to a pointwise quadratic lower bound, which is not too surprising. Indeed, at small scales, expect the second order Taylor expansion be accurate, while at large scales, we expect the p-th power loss to grow at least quadratically for E [2, oo).
In the case of p E 21, we are faced with harder problem. Indeed, as p - 1, the lp losses behave almost linearly at large scales. This means that we cannot expect to obtain a global quadratic lower bound as for the case E [2, oo), concerns, Bubeck, Cohen, Lee, and [BCLL18] introduced the following approximation to the p-th power function
will need a different proof technique. Motivated by related
P pp P
if
x
2
7p (t,,,x) =
xP
(1-M)t
t
if
x>t.
7

---

for t, E j0, 2o) and with (0,00)) = 0. This function was further studied by Adil, Kyng, Peng, and Sachdeva [AKPS19]] who showed particular that for any E E. the function + (p (x|) is. up to constants that depend only on p. equal to the gap between the function z: +> fp + x)) and its linearization around O; see Lemma 4.5 in [AKPS19] for the precise statement. We use this result to derive the following Lemma.
Lemma 4, Let E (1,2). Under the assumptions Theorem 5, we have
1
Rgn((1)) (w)((u)))
3o (1w Xi) Vi u.. Xi)l) + Ryn (wx), w wf))
4p
(12)
Rp(w)= - Rg(w)) S (p 1) w w w/11
(13)
As expected, while we do have the desired quadratic upper bound, the lower bound is much more cumbersome, and is only comparable to the second order Taylor expansion when (w- - Kwg, X,) - Yil. What we need for the proof to go through is a high probability lower bound of order R[| - w" 1111)) on the first term in the lower bound (12). We obtain this in the following Proposition.
Proposition 2. Let 8 E (0, 1.. Under the assumptions of Theorem 5, if 2 196a + 2oo (4/))), then with probability at least 1 - 6/2, for all w E IRd.
To (1KC Xi) Yab - ups Xi)l) 2 P min | willitp 2 P w (up111,))
T1
where eP-2 2 = pop -=-p)--D)> Vep and cp and ey are defined in Theorem 5.
12-p)/2
Proof. Lete 0 and let T E (0) be a truncation parameter we will later. Define
x= X (1,T))
and the constant B == Te. By Lemma 3.3 in [AKPS19], we have that Pptt, 2 x>m >P) xt) for all X 2 0. Furthermore, decreasing in f and increasing in x. Therefore, we have, for all w E Rd,
straightforward to verify that (p, is
7o (1 X.) - Vil. - w x:)1)
2 minf E 2?|w up wpl1A,, 5- -p1lpe- - u J
1
1 Σ 70
(Kug, X,) - V/l. K e(wo- w -(le-up)
|| (1
xi 1)
w w071111
s=1
2 minff 2|| up 112,, S -l1lp - wpllit, }
inf |
To (K Xi) Yil, Kuc, X.).))
n2
(14)
The key idea to control the infimum in (14) is to truncate (w, X,) from above by using the truncated vector X, and (w X,) - Y/l from below by forcing it to be greater than B. By the monotonicity properties of 7p discussed above, we get that
inf [1,,,, = n.
7n (1 X.) - Y,b,lw,
2 inf
Σ 3p (max (( Xi) - 371.83.110 X:))
||wr|| =z n
c2p
inf
1
max
[( X,) - 211,183--1(0000 x.112
(x,,))))
(15)
2
|| N..
=1
8

---

where the equality follows by the fact that with the chosen truncations, the second argument of Yp is less than or equal to the first. remains lower bound the infimum in (15). Define
Z = max (w x) YI, 33 2//22/2/// X.
Removing the truncations and using our assumptions, we see that the components of Z have finite fourth moment. By Proposition and the condition on n, we get that with probability at least 1 5/2,
inf
max (w X,) 33 91 (w0, x,)1
Iwlll =1 n
i=1
inf
(w, Zi)² 2 2 || n,
E[ (2., [[ Z inf
|wlllp =1 1=1
1 inf
max (Kw X) 11. (p-2) 2) (w, 8}3]
2
||wl|la, =1
1
2
sup 1| =1
E [u - 2|p-2(0. (w. x3
- rl) + (1 15
(16)
We now bound the supremum in (16). We have
E Kew X) - Y 1 (w,, x)² (1(0,, X) - Yl) + 1 (1
sup 1,
E (u x) y 112 (w, x3 1/2)
(P(Ku X) - <1) -x)
+ P || m7 > 7 1/2
sup
|wllls
/ (P(1(uz:)) - <) + [ |X | > >T)) 1/2
)
sup [1
(P(K x| + ( (1 > >r)) 1/2
(17)
where the first inequality follows from Cauchy-Schwartz inequality, and the subsequent equalities by definitions of +p and oz. It remains to bound the tail probabilities. Recall that 3 = Te, so
P([ X) Yl < B)
P( X) - Yl < TT)
P((( x) - VI-1 > (1e)-1)
= ((((u)) X) x2 > (TT))(e-2)
S Bll(wp, X) - Y 260 2) (T)))((())))
= (T=)))2()))
where we applied Markov's 's inequality in the fourth line, and the last follows by definition of cs in
Theorem 5. Moreover by the finiteness of the second moment of the coordinates X of X, have
E
||x | = =[x"
E[IT(H;'xx*) = Tr(H)' c
where Σ = F[ and the last equality by definition of op in Theorem 5. By Markov's inequality
P(K X) - Yl < TT) + P
PPP (1 1|, > >T) s 21)
Cp T2
Choosing
1/(6-2p)
T= Cp
2-P
(7(2 - p)
807
8-p
Vop Cp
(2- (2-1)/2'
ensures that
dp (P(1 X) Y| < TTe) + PP TT Tr) Combining the inequalities (18), (17). (16), (15), and (14) yields the result.
1/2
$ 1/2.
(18)
A detailed proof of Theorem 5, including the proof of Lemma 4, can be found in Appendix F.

---

Acknowledgments and Disclosure of Funding
We thank Nikita Zhivotovskiy, Sushant Sachdeva, and Deeksha Adil for feedback on the manuscript. MAE was partially supported by NSERC Grant [2019-06167], CIFAR Al Chairs program, and CIFAR AI Catalyst grant.
References
[AC11]
J.-Y. Audibert and O. Catoni. "Robust Linear Least Squares Regression", In: The Annals of Stutistics (Oct. 2011). Dor: 10. 1011111411111 1111111119991
[AKPS19]
D. Adil, R. Kyng, R. Peng, and S. Sachdeva. "Iterative Refinement for f--norm Re- gression". In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Jan. 2019. DOr: 10. 9777711177161117744822 86.
[AKPS22]
D. Adil, R. Kyng, R. Peng. and S. Sachdeva. Fast Algorithms for e Reggresssin.. Nov. 7, 2022. DOE: 10. 48550/5550500 arxiv.
[APS19]
D. Adil, R. Peng, and S. Sachdeva. "Fast, Provably Convergent IRLS Algorithm for p-norm Linear Regression" In: Advances in Neural Information Processing Systems. 2019. URL: https: /
htppp//c/////ooccnngg.ccc neurips cc paper paape__fllss ppaper/2011
hash/46c 44666666066777772222454545133333 Abstractt.....tttt..t...a..aa... html..
[Arc96]
M. A. Arcones. "The Bahadur Representation of L, Regression Estimators". In: Econometric Theory (1996). URL: https:::p////ttt http:pps://ww...ssooo http://wwww.sotoorrrrrrrrrsseeee httg//taalee/353225
[AS19]
D. Adil and S. Sachdeva. "Faster p-Norm Minimizing Flows, via Smoothed q-Norm Problems". In: Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms (SODA). Dec. 23, 2019. DOL: 10. 1 1. 978161 1111111999994... 54.
[BCLL18] S. Bubeck, M. B. Cohen, Y. T. Lee, and Y. Li. "An Homotopy Method for l, Regression Provably beyond Seff-Concordance and in Input-Sparsity Time". In: Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing. June 20, 2018. 8. DOI: 10. 00145/3188744 3188776.
[BRW92]
Bai, C. R. Rao, and Y. Wu. "M-Estimation of Multivariate Linear Regression Parameters Under a Convex Discrepancy Function".. In: Statistica Sinica (1992). URL: https://wwe jstor. org/stabbee/4304122 O. Catoni and I. Giulini. Dimension-Free PAC-Bayesian Bounds for Matrices, Vectors, and Linear Least Squares Regression. Dec. 31, 2017. DOT: 10. 40550/550045 arxiv. 1712. 02747.
[CG17]
[HKZ12]
D. Hsu, S. M. Kakade, and T. Zhang. "Random Design Analysis of Ridge Regression". In: Proceedings of the 25th Annual Conference Learning Theory. June 16, 2012.
URL: https: http::://proceednng. mlr. www.mmrrrreree wwtppp/ees//eeeeeeeepeppp htt///hsul.... html.
[HS96]
X. He and Q.- Shao. "A General Bahadur Representation of M-cstimators and Its Application to Linear Regression with Nonstochastic Designs". In: The Annals of Statistics (Dec. 1996). DOI: 10. 1.0.11144 / aos 1032181177
[JLS22]
A. Jambulapati, Y. P. Liu, and A. Sidford. "Improved Iteration Complexities for Overcon- strained p-Norm Regression". In: Proceedings of the 54th Annual ACM SIGACT Sympo- sium on Theory of Computing. June 10, 2022. DOI: 10. 1 1145/3511111 19959999.... 3519971. V. Koltchinskii and S. Mendelson. "Bounding the Smallest Singular Value of a Random Matrix Without Concentration". In: International Mathematics Research Notices (2015).
[KM15)
DOE: 10.
[Kni98]
K. Knight. "Limiting Distributions for L1 Regression Estimators under General Condi- tions". In: The Annals of Statistics (Apr. 1998). DOI: 10. 2214/aos/ 1028144858.
[LC83]
L. Lehmann and G. Casella. Theory of Point Estimation. 1983.
[LL05]
P. Y. Lai and S. M. S. Lee. "An Overview of Asymptotic Properties of Lp Regression under General Classes of Error Distributions". In: Journal of the American Statistical Association (2005). URT.: https::///attt jstor org/ /tsbsstaaleee.. e/ 27590667.
[LM16]
G. Lecué and S. Mendelson. "Performance Empirical Risk Minimization in Linear Aggregation".. In: Bernoulli (Aug. 2016). DOI: 10.
[LM17a]
G. Lecué and S. Mendelson. "Regularization and the Small-Ball Method II: Complexity Dependent Error Rates". In: Journal of Machine Learning Research (2017). URL: http: org/papers/
/ // jmmr.. org/ papers/ wtaeerssv//// v18/16-427 html.
10

---

[LM17b]
G. Lecué and S. Mendelson. "Sparse Recovery under Weak Moment Assumptions". In: Journal of the European Mathematical Society (Feb. 15, 2017). DOE: 10.4171/jems/ 682.
[LM18]
G. Lecué and S. Mendelson. "Regularization and the Small-Ban Method I: Sparse Recovery". In: The Annals of Statistics (Apr. 2018). DOI: 10. 121141170--01156
[Men14]
S. Mendelson. "Learning without Concentration". In: Proceedings of The 27th Confer- ence on Learning Theory. May 29, 2014. URL: attps://proceediii v35 355/mendelson14 html.
mlr .rrees/es///
[Men18]
S. Mendelson. "Learning without Concentration for General Loss Functions". In: Proba- bility Theory and Related Fields (June I, 2018). DO1: 10. 1000010004000007077770
[Men21]
Mendelson. "Learning Bounded Subsets of Lp" In: IEEE Transactions on Informa- tion Theory (Aug. 2021). DOE: 10. 1109/TIT 2021 3083553.
[MG22]
J. Mourtada and S. Gaiffas. "An Improper Estimator with Optimal Excess Risk in Misspecified Density Estimation and Logistic Regression". In: Journal of Machine Learning Research (2022). URL: http:// http://mlrrrrr/ppppeeee wttpp/pprs/vv3//////oo 2ttp///v2//08/22222 .tmll.
[Mou22]
J. Mourtada. "Exact Minimax Risk for Linear Least Squares, and the Lower Tail of Sample Covariance Matrices". In: The Annals of Statistics (Aug. 2022). DOI: 10. 1214/ 22- AOS2181.
[MVZ22]
J. Mourtada, T. Vaškevičius, and N. Zhivotovskiy. "Distribution-free robust linear regression". In: Mathematical Statistics and Learning (2022). DOI: 10.4110.11111 10.4171/MSL/27, W. Niemiro. "Asymptotics for M M-Estimators Defined by Convex Minimization". In: The Annals of Statistics (Sept. 1992). DOI: 10. 1 aosss/////// 1176348782.
[Nic92]
[OB21]
D. M. Ostrovskii and F. Bach. PFinite-Samle Analysis of M-Estimators Using Self- Concordance".. In: Electronic Journal of Statisties (Jan. 2021). DOI: 10. 1214/20- EJS11880
[Oli16]
Oliveira. "The Lower Tail of Random Quadratic Forms with Applications to Ordinary Least Squares". In: Probability Theory and Related Fields (Dec. 1, 2016). DOI:
10. 1000000000000000000 073--9.
[Ron84]
A. F. Ronner. "Asymptotic Normality of p-norm Estimators in Multiple Regression". In: Zeitschrift für Wahhsccheinicchkeissheerrr und Verwandte Gebiete (Sept. 1984).
DOI: 10. 1007 10..100//FFF5530000 /FO053189.
[RV15]
M. Rudelson and R. Vershynin. "Small Ball Probabilities for Linear Images of High- Dimensional Distributions". In: International Mathematics Research Notices (2015).
DOT: 10. 1093/ htt//mmm/rruu///
[Sau18]
A. Saumard. "On Optimality of Empirical Risk Minimization in Linear Aggregation".
In: Bernoulli (Aug. 2018). DOI: 10. 3150/17-
[Vaa98]
A. W. Van Der Vaart. Asymptotic Statistics. 1998. DOI: 10. 1011 0017//80998051190225..
[VW96]
A. W. Van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes.
1996. DOI: 10. 1007 /111///788-777---1 2545-2.
[VZ23]
T. Vaškevičius and N. Zhivotovskiy. "Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors". In: Bernoulli (Feb. 2023). DOI: 3150/222 BEJ1465.
[Whi82]
H. White. "Maximum Likelihood Estimation of Misspecified Models". In: Econometrica (1982). DOI: 10. 2007 1912526.

---

A Differentiability of the risk
In this section, rigorously establish the twice differentiabilitty the risk under assumptions. We start by showing that under subset of our assumptions, the risk is differentiable everywhere on R
Lemma 5. Let p E (1, xc) and assume that E[[ < co and F11X < for all j [d] Then Rp is differentiable on Rd, and
= = X) Y)].
Proof. Let Rdd We want show that
Rplw + A) Rp(w) - ((v) 0,
lim
|
where, for convenience, we take the norm ||||| to be the Euclidean norm. Define the function 6(w, X, Y) == fol(w, X) - Y) and note that by the chain rule Φ is differentiable as function of w on all of Idd Now let (Ax ) be sequence in Rd such that limm- || A || = 0. Then
RB + AR) (w(w) - EKVØ(W, X, Y), Axll
lim
k+000
A
E[ó(w + Dc, X, )) s(w, X, 1) - V, Y),
lim k-+00
1| |
Jo(w + Ax, X, Y) - <6w,, X, Y) -
< lim E
(19)
10000
A
Our goal is to interchange the limit and expectation. For that, we will use the dominated convergence theorem. We construct dominating function follows. Let R == supxenll Ax|l, and note that R < oo since | + O as k + co. Then we have
lo(w + A X, ) - olw, X, Y) - (Vo(w, X, Y), AxY
A
16(w k. X, Y)- (ww, X,
KVo(w, (w X, Y), Ax)
1| |
Volw + thp X, Y), A
+ ||v X,YIII
|
Volw + +I X,
Vo X, X)I
V + LA, X. 1) + Volw. x, Y)
J0
22
sup
|V X,
R)
|
sup AEB(O.R)
[ww + A, X) - yPp-1
p-1 1
max 22 .13 (I(u,, X) x) -VP-1 + I(A, - x)p-11
X||
sup
p
((,
2F
(w,, X) - Y
| RC (XXP]] P =
p
where the second line follows by triangle inequality, the third from the fundamental theorem of calcu- lus applied component-wise, the fourth by Cauchy-Schwartz inequality, the fifth by Jensen's 's inequality and the convexity of the norm, and the eighth by the inequality la 6/9 max ( + [b]9)
12

---

valid for > O. It remains to show that (XX, Y) is integrable. We have
2
Elg(X,
- E Kw, X) Y ||||| + 1|
2
E Kew, X) -1 |x
+ R2 128-10 E
p-1
2
[w] X)
rp E
R dD Σ El E
p-1 < 00,
where in the second line we used that the Euclidean norm is bounded by the 1-norm, in the third we used Holder's inequality, and the last line follows from our assumptions. Applying the dominated convergence theorem, we interchange the limit and the expectation in (19). Recalling that e is differentiable finishes the proof.
We now turn to the twice differentiability of the risk. We start with the easy case p E [2, oc). The proof is very similar that of Lemma 5 and we omit here.
Lemma 6. Let p E o0) and assume that E[[Y|] < co and E| < for all j E [d. Then Ro is twice differentiable on Ted, and
R²) ((x, Y)].
The case p E (1, 2) is more complicated. The following lemma establishes the twice differentiability of the risk its minimizer under subset of the assumptions of Theorem 5.
Lemma 7. Let p (1, Assume that P(K X) - =| ( < oo for all j e [d]. Then Rp is twice differentiable at w and
and Elk X)
(RRr(W))) ElV2 X) Y)
Proof. The difficulty in the proof compared to Lemma 5 and Lemma stems from the fact that the loss is not twice differentiable zero. We still rely the dominated convergence theorem, but the construction of the dominating function is slightly more intricate. Using the setup the proof of Lemma 5, and following the same line of arguments, arrive at
Ry + A+) (R F. 22 2 X, X)
lim
k-400
||A
E VVol + X,) Volu X, X, V Voo X, X,
lim k-000
(20)
|
where we have used the fact that since P(K twice differentiable at w To finish the proof, remains to construct dominating function for the above sequence to justify the interchange of the limit and expectation. We consider two cases.
p. X) -| = 0, Φ(w, X, Y) is almost surely
13

---

Case 1: | 2 (uez X) - 12 =: R(X, Y). Then we have
Volug + Ak, Vo(u,, X, V V X,
1
[Volug + As, XI1 + IVV X, x) + | (1 X, A
|
(Kou +), 110 + Ku0 x) - 1p -1- ||XI|
+ 1 x, X)
(p- -1)
2 (ug X) rp ||
< | ||, X|
+ |K - 1-111-1 +
(p- - 1111 R
(p 1) A 12-0
4 (up X) 1 91
||
+ Kuz X) - 81 -18 1| + (M 1x11
(p - 1)
7 (unz- X) 13-Y0 1|113
11
where the second line follows by triangle inequality. the third by definition of the operator norm,
the fourth by la + b1S - |a| + 18/8 valid for q E (0. 1), and the fifth and sixth by Cauchy-Schward inequality and the assumed lower bound on ||
Case 2:
|| < Y).,Y). We start by noting that, for all A E B(X, =
{I E Rd1 ||||| < Y), we have
KwS + A, x Y| N (wzz x) - -IA. 2 (
X) - Y| > > X) - - > 0.
Therefore (ww, X, Y) is twice differentiable on B(0, R(X,)))))))))) Now
V + XY) Vehlig x, Y) V2 X)
||
VVo(ug + X.Y) Ve(w X,Y) + | V V X, X)))
A
Vip(uzz + +tAR x, ddtt
A
+ [V X, 1)
|
V2 Po(w+ + 1b X, dtt
+ (W x, llop
op
|V2 6l + AA, l) + 122 (2 x, llop
2 2 sup
| [V'oW + A, 1lop
< 2
sup AEB(O.R(X.Y)) (w: +), x1p-2
< <4[ - Y 1
where the second line follows from the triangle inequality, the third follows from the twice differen- tiability of Φ on R(X, Y)) and the fundamental theorem of calculus applied component-wiss the fifth by Jensen's 's inequality, and the last by definition of R(X, Y) and the above lower bound. We therefore define our dominating function by
g 9(X, Y) = 8| (w X)
Y p 1
It is then immediate from our assumptions that (X, Y) is integrable. Interchanging the limit and the expectation in (20) and recalling that & is almost surely twice differentiable at we finishes the proof.
14

---

B Proof of Lemma
We start with the claim that Po is upper-semicootinuous. We want to show that for any w E IR and any sequence (wa)fe converging w (in the norm topology)
lim sup Pa (wrk) I po(w))
Fix a w E Id and let (we ken)k=1 be a sequence in Rd satisfying limg-soo /wo - wxll = 0, where for convenience we take ||+]| to be the Euclidean norm on IR.. Then we have by (reverse) Fatou's Lemma
lim sup (wx))) lim sup E 1 fop ((wk, x))] <
lim k-
(() ((wx, ((wx,
(21)
k
k-+00
Now we bound the inner limsup pointwise. We split this task in two cases. If (wc, X) 0. then
lim sup (0) (ww,, x)) S 1 1 (o) ((w, X)).
(22)
k
Otherwise we have 8 == kw, X O. But then, by the convergence of (wx)R= to there exists K E such that for all 2 K we have ||w - w|l < (2 This implies that for all 2 K
(wa; = (w,, X) - (w wke X (w, X) - x) > 8 - w/2 6/2 > 0.
We conclude that
sup 1oy ((wx,X)) = lim ()), = 0 - [ ((w, X)). 4-000
(23)
k
Combining (21), (22), and (23) proves the upper-semicooniinity of Pu- Essentially the same proof shows the lower-semicontiniity of Pa(-, x) for any к 2 0; we omit it here.
For the remaining claims, first notice that the function po is scale invariant, i.e. for w Rd and all E IR we have po (cw) (ww).. Therefore
sup WE
Pu(w) sup Po(w), wEB4-1
where gd-1 is the Euclidean unit sphere. By assumption the random vector X. know that Po(w) < for all w E Sd-1, Furthermore since Pu is upper semicontinuous, and gd- is compact, Po attains its supremum on gd-1 at some point wig E sd-1, From this we conclude that
sup wER (10)
(o(w) po(wo) < 1.
Finally, we turn to the claim about Pg. Since E|X < oo, the function || norm on Rd. from which it follows that Py (wr, is also scale invariant for any Therefore
inf Pg(w. x)) inf Py(w, it), wES,
MER (()
where S. is the unit sphere of the norm |l Now fix x E [0, 1). We claim that P, k) > 0 for all w E Sy. Suppose not. Then there exists a w E S. such that (w, X) & x with probability 1, but then get the contradiction
1 = ||]] L. Ell (w, X)19//4 <
therefore Py(W, k) > for all w E Sg. Now since po(., x) is lower-semicontinuuus, and S, is compact, P.(:, x)) attains its infimum on S, at some point wy Sg. From this conclude
inf Pr(w,, x) py(wgg x)) wERd)(0)
15

---

C Proof of Theorem 3
Fix (1, oo), and let á := wp. Our goal will be to upper bound the probability P(w # w²). By
assumption, we have that Y = (w* X). so that Y; = (w", X2) for all E [n]. Since v minimizes the empirical risk, we must also have (ú0, X;) = Y; = (w" X,) for all i E [n]. Let A E R denote the matrix whose i-th row is X,, Then we have the following implications.
v + w² = (0 w², x,) 0 vi [n| + 3w E IR {O} Aw 0 + rowrank(A) < d. (24)
Let r == rowrank( A). We claim the following equivalence
rowrank(A) < d + As [n] [S] d - A Vi e [n] \S X, span((Xx, | E
(25)
Indeed the implication (=) follows by definition of the rowrank of A. For the implication (=), by definition, {X; E [n] is spanning set for the
space of A. therefore it can be reduced to
basis of {X, & S for some indices S C [n] with [S] = r. If = d - 1, then the choice
S S1 satisfies the right side of (25). Otherwise, let S2 C [n] \ Si with [S2 = d
Such
subset exists since by assumption n 2 d > 1. Then the set S == S1 U S2 satisfies the right side of (25). Combining (24) and (25) we arrive
P(ύ + SP
U SClol |S|=d-1
{ [R] \S X; E span((Xa k E 8}}}
P(vi E [n] \ S X; E span(fXx E S)))
(26)
ScIal
1s|=d-1
where the second inequality follows from the union bound. We now bound each of the terms of the sum. Fix S = fi....., "it....,.da1. 1 C [n]] with [S] d - 1. Let Zs = nn((,,,) be non non-zero vector orthogonal to span({X; [ & S)). Such vector must exist since dim (span) ( [Xx k E ())) < d: see Lemma 8 below for an explicit construction of the function n. Denote by Pzg the distribution of Zs and P(x.)eess = - - Px the distribution of (Xe)sE(n)sss where Px is the distribution of X. Note that since Zs is function of (Xi,)ā=1 only, it is independent of (Xi)sefn)ss In particular, the joint distribution of (Zs, (Xi))E(m))s)) given by the product Pzς x P(x.)semis Now X; E span (fXx & E 5}). then by definition Zs, (Zs, X2) = Therefore
P(Vi E [n] \ S X; E span (Xx k E S))) - P(vi E [n] 5 (Zs, X.) 0)
E II [E[N]]S
(1)s,
/
II (E(N)S
Hop (lys, xi))
/ (ds(s)) (d(x;)
= f Pzo (dy.)
II / 1 [E(m]]s8
P((as, X) = =0] Pzo (dya)
EE[M]LS
polys)
P2o
S -p--d+)
(27)
where in the third line we used the independence of Zg and (X))xe())ss in the fourth we used the independence of the (Xi)eess, in the sixth we used the definition of Pn in 5, and in the last line we used the fact that 2s * O and the definition of p Lemma 1. Combining the inequalities (26) and (27) yields the result.
D
16

---

Lemma 8. Let m E (1....d-11 1} and let (2z)}=1 be sequence of points in R Denote by A E Bandd the matrix whose j-th row is 2y and let A+ be its pseudo-inverse. Let (ba)==1 be ordered basis of Rd, and define
:: min i E [x]] (I A)6, + 0}
== Δ)bb
Then n ((xx)))==)) is non-zero and is orthogonal to span {az j E [m]H)
Proof. We start by showing that is well defined. First note that - A is the orthogonal projector d m 2 1. Now we claim that there exists an E [d] such that (I A+ A)b; + 0. Suppose not, then for
onto the kernel of A, which is non-trivial since dim(ker (ker(A))
dim(Im((A)
any E Hdd have (1 At A)w (1 At At --= c,b,)) Σ E-=1 c A A)6; 0. implying that / - A A O, but this contradicts the non-triviality of ker( This proves that k is well-defined, which in turn proves that (( * O. It remains to prove the orthogonality claim.
Let U E span((#) j E [ml]). Then there exists coefficients c E R such that v = c.c. Therefore
(v, (1((((())))))))) (())))))=)) = (A" c, n,n;s = c'A(TI AAT = 0,
where the last equality holds since (I - AA+) you E kcr(A))
D Missing proofs for Theorem 1
This section contains the proofs of Lemma 2 and Corollary 1 used in the proof of Theorem 1.
D.1 Proof of Lemma 2
compute the expectation:
E [u E VVl" - x
= =n
E
V Ep (w X;) -x:)
i=1
2n
2
E V ep (ww X,) - E/V, - -Ys)]) HF*
=n ( Y) H
where in the second line we expanded the inner product of the sums into its n² terms, used linearity of expectation, and used the independence of the samples to take the expectation inside the inner product. the last line, we used the fact that the samples are identically distributed to simplify the first term. For the second term, we used the fact that the expectation of the gradient of the loss at the risk minimizer vanishes. Applying Markov's inequality finishes the proof.
D.2
Proof of Corollary
We have
||
w willit...
(w w2)²
H2, wE)
V2 " X.) Y:)(w -wi)
n
1 (w w X
Now by assumption, the components of the vector have finite fourth moment so that applying Proposition 1 and using the condition on yields the result.
17

---

E Detailed proof of Theorem
This section contains the proof of Lemma as well as that of Theorem 4.
E.1 Proof of Lemma 3
By Lemma 2.5 in [AKPS22], we have for all 1, E R
1
(t() Ep(s) (g(s)(t -g())) 5) 2 8(p - ( (()s(( s)?.
Recall that by the chain rule
Vep((e, X) - Y) = (,w, -YX Vipp(1u, X) - Y) = (" YXXX"
Replacing and s by (w) Y; and (w Xi) Y, respectively, and using the formulas for the gradient and Hessian we arrive at
1 fp(ww, X1) - Yi) - Ep(tus, Xi) Yi) 2 8(p 1) (w wS) T 22 Ep(cp (x) X.) Y) wp) VV ( X,) - Yi), w - w
Averaging over E [n] yields the first inequality. The proof of the second inequality proceeds in the same way and uses instead the upper bound of Lemma 2.5 [AKPS22]. We omit it here.
E.2 Proof of Theorem 4
We proceed similarly to the proof of Theorem By definition of the empirical risk minimizer, we have the upper bound
Ppm (2 I 0.
(28)
Using (10) from Lemma 3 and the Cauchy-Schweee inequality, we obtain the pointwise lower bound
(wpp( Rp. (wf) 2 - -IV (w))) n5- 1| willH, 8(p 1) 1100 wi.........
(29)
Using Lemma we have that, with probability at least - -8/2.
Ry (1 S 2 X) Y) 10)
(30)
remains to control || - w Hp.n. from below. Define the random vector
Z = Kw X) 2)-2)
Then, for any E Rd, we have
||w - w 1 Hm...
(w 1: Hp. (w w²))
n
(w - wi)) V " ( X.) - Y:)(w - wx))
n
w Z
By assumption, the components of the random vector have finite fourth moment. Applying Proposition 1, and using the condition on assumed in the statement of Theorem 4, we get that, with probability least 1 5/2, for all w E IRdd
|| w 11
2
2 I/ w
(31)
18

---

Combining (30) and (31) with (29) gives that with probability at least - 8,
(p,((Up) Rp.n (w,)(up) - 2 [Vlp((u
1011 //(()))))))))))) 110p will
1
+ 16(p - 1) 11 - " lilli (32)
Further combining (32) with (28) and rearranging yields that with probability at least 5
512p² E
Ve ((u X3 1)
1 w 11
(33)
nz
The last step is bound the excess risk of the empirical risk minimizer using the bound (33) and (11)
from Lemma 3. For that, we control the L norm term in (11) as follows
p/2
11
w
101 w
p2
1|00p
2
Hp
p/2
| LP 10 Hpp
p² sup Wo
1100p
willit,,
D/2
p2 cll0,
" 11
(34)
Combining (33), (11), and (34) yields the result.
F Detailed proof of Theorem 5
This section contains the proof of Lemma 4 as well that of Theorem 5.
F. Proof of Lemma
Both inequalities follow from Lemma 4.5 in Adil, Kyng, Peng. and Sachdeva [AKPS19]. (12) follows from straightforward calculation using the lower bound of Lemma 4.5 in Adil, Kyng, Peng, and Sachdeva [AKPS19]; we omit it here. The upper bound requires a bit more work. We have by the quoted Lemma
4
fx())=((6) - (t(() 5) S
p(p 1) 20((s),1t s1).
Now assume that [s] > 0. 8| S |s/. we have
(1s,),, s|) ~ sisp-2 s)² s 1s/ 5)² =t)(s)(t- s)2
Otherwise, 8) |s|. then we have
(1s),, s|) = It s|" -
(1- p/2) < (t 3) - s/p < |// 2t =))= 5)2.
Therefore in both cases we have 7ip (1s). It +|) s (s) - 2)² as long as |s| 0. Replacing and by X) - Y and (wi. X) Y respectively we get, on the event that (w X) - Y + 0
4
()-) -))) x)
w w < p(p
I (ww
Recalling that by assumption P((wp, X) Y + 0) = 1, taking expectation of both sides, and bounding l/p < 1 finishes the proof of (13).
19

---

F.2 Proof of Theorem 5
We follow the same proof strategy as the one used in the proofs of Theorems 1 and 4. By definition of the empirical risk minimizer, we have
Rp.n(mg) Rp. (wp) S 0.
(35)
Using (12) from Lemma and the Cauchy- Schwarz inequality, we have the lower bound
(1p)(Up) Rp. (w,)) 2 -1 V (pp,((25)) 11 1k0
will
n
4p 7p (KW,. Xi) 1. w X.)l)
(36)
Using Lemma we have that, with probability at least 8/2.
A Rg. (wF)) 1r S
$ VVpp((ug x) -Y)l | 11,
2F
(nd).
(37)
On the other hand, by Proposition 2, we have with probability 1 8/2, for all e R
(l X1) - Ki w. x.)I min [1 thfu-wjiltae Ppppp w w 11,1 }} (38)
where is defined in Proposition 2. We now consider two cases. If 10p willir, =²² " Ill then combining (35), (36), (37), and (38) gives
8192 E
Vlp((u X) x)
1100
will I
(39)
nō 1 Il then again combining (35), (36), (37), and (38)
Otherwise,
|| will?r,
2--0 100
gives
1/(p-1)
8192 E
VV X) - 1) 1,, 22(0-2)
11:;; o li,
(40)
nz
In either case, we have, using (39) and (40), with probability at least 1 6,
8192 E
Ve ( X)
1
|100 willit, s
nd
1/(p-1)
8192 E
(V X) YY) 11
c((x-2)
nō
Combining this last incquality with (13) from Lemma 4 finishes the proof.
20


Reviews:
[{"review_id": "jNlB8uog9U", "reviewer": "Reviewer_1SnJ", "summary": "The paper studies excess risk bounds for empirical risk minimization for linear regression under $\\ell_p$-norm. It extends existing work $p=2$ to general $p\\in (1,\\infty)$.\n\nSampling complexity bounds are given for recovering the true parameter in the realizable case.\n\nAdditive error excess risk bounds are given (under mild assumptions on $O(p)^{th}$ moments) in the non-realizable case\n\nI generally like the paper but some issues need to be discussed/resolved, based on which my rating could move either way.", "questions": "1. Optimality is a strong claim. In what sense can your bounds be considered _optimal_ ? I see no lower bounds at all !?!\n\n2. Theorem 3 seems (at first glance) even below known lower bounds. For instance if the generating distribution realizes standard basis vectors with equal probability and the target is not contained in any subspace spanned by a proper subset, it is known that $\\Omega(d \\log d)$ is necessary to recover the exact target (follows simply from the coupon collector's theorem). So, my question is, what is the role and the dependence of the $\\rho$ parameter on the dimension?\n\n3. Again Theorem 3: the three cases seem a bit arbitrary, why is it necessary to distinguish between them? is it only to make the upper bounds work in any case or are there stronger indications for actually separated complexities in the three cases?\n\n4. Why are there no bounds on $p=1$, would there be a major complication (in your analysis or in general) in tackling this case?\n\n5. What is a \"negative moment\"?", "limitations": "The very important case $p=1$ is not handled or discussed at all beyond the intro/motivation", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* natural extension to $p$-norm regression\n* non-asymptotic bounds take similar forms as the asymptotic results in the p=2 case (up to dependencies on constants and $p$)\n* rigorous theory\n* good high-level discussion on the difficulties of generalizing previous proofs to general $p$ and how they are handled\n* good overview over existing work", "weaknesses": "* \"Optimality\", claimed already in the title is not supported by any (existing or new) lower bounds\n* some assumptions seem to 'eat' terms, that depend on the dimension d. There is some, but only very limited discussion on this\n* no result for the second most important case $p=1$\n* in a few places very 'mathematical' statements without explaining the semantic or intuition behind\n* bounds depend on Hessian forms of $\\ell_p$ loss functions, which fit _perfectly well_ to the quadratic function in the $p=2$ case but do not capture the loss as closely for other $p$, even though the bounds look similar\n* discussion on (third paragraph, ll 23-32) motivating the $\\ell_p$ loss regression problem could be improved and seems vague wrt the properties of the model. I suggest rewriting this, stating that it is the standard linear model with $p$-generalized Gaussian error distribution that has certain statistical properties parameterized by $p$. See https://arxiv.org/pdf/2203.13568.pdf and references therein.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and detailed feedback. We address the reviewer’s concerns below.\n\n---\n\n***”Optimality is a strong claim. In what sense can your bounds be considered optimal?”***\n\nOur bounds are optimal in the sense that the leading term in them matches the asymptotically **exact** expression of the excess risk of ERM given by equation (1) as $n \\to \\infty$, as we described after the statements of Theorems 4 and 5 (lines 164-165 and 181-182). In other words, **any** bound on the excess risk that holds for large enough $n$ must dominate the first term in the RHS of equation (1); our bounds are optimal in that they exactly recover this term (up to constants that depend only on $p$).\n\n---\n\n***”What is the role and the dependence of the parameter $\\rho$ on the dimension?”***\n\nThe role of the parameter $\\rho$ is to quantify the degree of \"degeneracy'' of the distribution of the covariates (see, e.g., Mourtada 2022), i.e., how well can the support of the distribution of the covariates be approximated by some fixed hyperplane.\n\nIn general, $\\rho$ does not depend directly on the dimension. Indeed, on the one hand, and when the distribution of the covariates $X$ is absolutely continuous with respect to Lebesgue measure, $\\rho = 0$, no matter how large the dimension is. On the other hand, $\\rho$ can be arbitrarily close to 1, even in very low dimensional settings. Indeed, let $\\varepsilon \\in (0, 1)$, and consider one dimensional $X$ satisfying $X = 0$ with probability $1 - \\varepsilon$, and $X = 1$ with probability $\\varepsilon$, then $\\rho = 1 - \\varepsilon$.\n\nFinally, let us mention that this parameter and closely related ones have been used many times in previous work (Rudelson et al., 2015; Lecue and Mendelson, 2017; Mourtada 2022), and that from a technical perspective, as we have discussed in the paper (lines 129-139), it is a natural parameter to consider.\n\n---\n\n***”Why is it necessary to distinguish between the three cases in Theorem 3? Is it only to make the upper bounds work in any case or are there stronger indications for actually separated complexities in the three cases?”***\n\nIt is only to make the upper bound on the failure probability work.\n\n---\n\n***”Some assumptions seem to \"eat\" terms that depend on the dimension d. There is some, but only very limited discussion on this.”***\n\nIf the reviewer is referring to the constants arising in our bounds, please note that we discussed their dimension dependence right after the statements of Theorems 4 and 5 (lines 167-171 and 196-197), and how that affects the optimality of our bounds. As for the constants $\\sigma^2_{p}$, they are powers of norm equivalence constants; one can show that they can be arbitrarily bad, even in a one dimensional setting, using an example similar to the one we used above to demonstrate the case $\\rho=1-\\varepsilon$. On the other hand, and to the best of our knowledge, no dimension dependent lower bound on them is known in the literature. As for Theorem 3, the above discussion on $\\rho$ shows that it does not depend on the dimension directly. We will add a discussion on both $\\rho$ and $\\sigma^2_{p}$ in the final version of the paper, but please note that our use of these constants is in alignment with previous work, and an inspection of our proofs would show that we did not purposefully hide dimension dependence in these constants, but that rather they naturally arise from the problem.\n\n---\n\n***”Why are there no bounds on p=1, would there be a major complication in tackling this case?”***\n\nYes, the case p=1 is technically more challenging, and we suspect that one needs new proof techniques to cover this case (as well as the case $p=\\infty$). Our proof technique breaks since Lemma 4 does not hold for the case $p=1$. This is in part due to the vanishing of the second derivative of the absolute value function (where it exists), which prevents us from extracting a quadratic lower bound on the excess empirical risk. Please note that even the asymptotic behavior of the excess risk of ERM is quite difficult to obtain in the case $p=1$, and can widely vary depending on the degree of \"non-realizability\" of the problem; we refer the reviewer to (Knight, 1998) for a detailed account.\n\n---\n\n***”Bounds depend on Hessian forms of $\\ell_{p}$ loss functions, which fit perfectly well to the quadratic function in the case $p=2$, but do not capture the loss as closely for other $p$, even though the bounds look similar.”***\n\nWhile the $\\ell_{p}$ losses are indeed not quadratic for $p \\neq 2$, in a small enough neighborhood of the optimum, the quadratic approximation of the risk is very accurate. Indeed, this is the basis of the asymptotic expansion in equation (1). As we have argued above, our bounds are optimal in that they asymptotically match the exact excess risk of ERM as $n \\to \\infty$, so that one cannot hope to obtain better bounds for large enough $n$. We agree however that for small $n$, better approximations of the $\\ell_{p}$ loss could potentially lead to better bounds.\n\n---\n\n***”Discussion motivating the $\\ell_{p}$ loss regression problem could be improved and seems vague wrt the properties of the model.”***\n\nWe will include the reviewer’s suggestion in the final version of our paper as an additional motivation for $\\ell_{p}$ norm regression. Please note however that the main perspective we take in this paper is learning theoretic, and our only concern is prediction: we are not postulating a statistical model, we make no assumptions on the distributional form of X and Y, and we are not motivating ERM as a maximum likelihood procedure.\n\n---\n\n***”What is a ‘negative moment’?”***\n\nFor a random variable $X$, we call $E[X^{-k}]$ its $k$-th negative moment. (with the convention $1/0 = \\infty$).\n\n---\nWe would be happy to clarify any concerns or answer any questions that may come up during the discussion period.\n"}, {"review_id": "rlVFQpRBVg", "reviewer": "Reviewer_KiJP", "summary": "The paper considers linear regression with inputs in dimension d and with n data points. It consider the Lp loss |.|^p with a focus on p different from the classical value 2. The paper provides non-asymptotic risk excess bound for this Lp loss, the excess being between the optimal linear combination w^* and the one obtained by minimizing the empirical risk. The bounds are of different natures in the two cases where the problem is realizable, meaning that the output is exactly a linear function of the input, and where the problem is not realizable.", "questions": "I do not have specific questions.", "limitations": "I do not see potential negative societal impact.\nThe limitations are discussed adequately", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. The problem is theoretically interesting. The theoretical results are well-connected to the existing literature and their novelty compared to this literature is well motivated. The proofs appear to be innovative and to combine arguments from different branches of  the literature. ", "weaknesses": "The content is technical and so the paper is not extremely easy to follow. \nAn option could be to take advantage of the appendix (with no space limit) to add more slow-paced pedagogical content. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation. We will be happy to answer any questions or comments that may arise during the discussion period.\n"}, {"review_id": "K9EFfzfaIc", "reviewer": "Reviewer_81uA", "summary": "This paper studies the empirical risk minimization of linear regression with the p-norm loss function, where p ∈ (1,∞).\n\nMain contributions:\n- The authors provide a high probability excess risk bound on the empirical risk minimizer, for p ∈ (1,∞), where for p ∈ [2,∞) only weak moment assumptions are needed, and for p ∈ (1, 2) there are assumptions that guarantee the existence of the hessian at the minimizer of the risk.\n- The authors strengthen a previous bound of perfect recovery in the realizable case.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Some strengths are:\n- This paper is the first work providing the high probability excess risk bounds for empirical risk minimization under the p-norm loss function with any p ∈ (1,∞).\n- The authors strengthen a previous bound of perfect recovery in the realizable case.", "weaknesses": "Some weaknesses of the paper:\n- The proof part is poorly written. For example, the statements of Corollary 1 and Proposition 1 don't make any sense (the inf of the left-hand side is less than the right-hand side?), where even for Proposition 1 the authors just want to cite an existing theorem in a previous paper (Theorem 3.1, Oliveira [2016]).  \n- There is a lack of the argument of the importance of this work. The authors discuss the benefits of using p-norm as the loss with p != 2, but why moving from asymptotic bound to finite sample bound is important for p != 2 is missing.\n\nTypos:\n- At line 232, second line of the equation misses index i on X and Y.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We kindly ask the reviewer to re-evaluate the paper in light of our response below.\n\n---\n\n***”The proof part is poorly written.”***\n\nWe thank the reviewer for pointing us to the typos in Corollary 1 and Proposition 1; we fixed these in the supplementary version, but we understand that this must have been a source of confusion when reading the original submission. To be more explicit, the required changes are as follows. \n\n- For Proposition 1, it suffices to move the term $\\||v\\||_{L^{2}}^{2}$ from the RHS of the statement to the denominator of the LHS. \n- Similarly, for Corollary 1, the term $\\||w - w_{2}^{*}\\||^2_{H_{2}}$ on the RHS should be moved to the denominator of the LHS. \n\nThe proofs of both statements remain unchanged. We invite the reviewer to consult the supplementary version for a correct and clearer version of both statements.\n\nPlease note that we have attempted to formulate our proofs in an accessible and readable way, and have dedicated a lot of effort in motivating all the steps in the proofs, emphasizing where our proofs differ from previous ones, and where our insights were needed. If the reviewer has other specific comments about the proofs, we would be happy to address them.\n\n\n***”There is a lack of the argument of the importance of this work. The authors discuss the benefits of using p-norm as the loss with p != 2, but why moving from asymptotic bound to finite sample bound is important for p != 2 is missing.”***\n\nWe clarify this with the following sentence in the revised version of our paper.\n\n*Among other reasons, non-asymptotic bounds are useful in characterizing **when** the asymptotic regime kicks in, and under what assumptions it can be attained for moderately large $n$, see, e.g., (Ostrovski and Bach, 2021) for more on this argument.*\n\n---\nWe would be happy to clarify any concerns or answer any questions that may come up during the discussion period.\n"}, {"review_id": "vJ4I2NoqYT", "reviewer": "Reviewer_YnMx", "summary": "This paper studies the performance of empirical risk minimization (ERM) for $\\ell_p$-norm linear regression, in both the realizable and non-realizable (say, noisy measurement) settings. While the $p=2$ case has been studied extensively in the literature, not as much is known for the general $p \\in (1,2) \\cup (2,\\infty)$ cases. For the realizable case, the author(s) improve over prior analyses and give a $O(d)$ sample complexity bound for finding the regression coefficients with high probability. For the non-realizable case, under moment assumptions, this paper shows high probability excess risk bounds.\n\nNote: this is an emergency review, and so I did not check the math carefully.", "questions": "Beyond the motivation question I have above:\n\n- The results are being compared to the asymptotic guarantees of ERM, but is there any evidence that ERM's asymptotic performance is statistically optimal (even when compared with other estimators)? In the special case of mean estimation, for example, we can actually write down non-asymptotic lower bounds on the estimation error in the Gaussian cases, which match the central limit theorem.\n- Can the author(s) further elaborate on the extra moment assumption $\\mathbb{E}[|Y - \\langle w_p^*,X\\rangle|^{2(p-2)} X_j^4] < \\infty$ in Theorem 4? Line 168 states that it's a \"natural extension\", but really doesn't give interpretation to this assumption, in particular, the interaction between the response and the covariate coordinates.\n\nAnother misc comment: The beginning of Section 2.2 makes it sound like Theorem 1 is an old result, but after the theorem, the author(s) state that there's novelty at least in the proof presentation. Probably worth writing that more explicitly before the theorem statement.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and clear. The author(s) motivate the $\\ell_p$ linear regression problem well, and this paper gives the first non-asymptotic excess risk bounds for ERM in this setting. The proof ideas are also explained pretty clearly.", "weaknesses": "My main concern/confusion is the message of the paper. The author(s) seem to sell the paper as having a high probability (excess) risk bound, yet the bound has a $1/\\delta$ dependence on the failure probability $\\delta$ (from using Markov, and might actually be tight) instead of logarithmic or root-logarithmic (sub-Gaussian) performance. ERM is very susceptible to heavy-tailed noise, even in the simple special case of mean estimation, so I'm a bit confused why we're studying the performance of ERM here, instead of designing better estimators that work under such mild moment assumptions. From my readthrough, it also appears that the paper is really bounding some expectation and using Markov to get the high probability bound. My question then, is, why is the paper phrased as a high probability result instead of an expectation/constant probability result, which I can imagine ERM to actually be decent at?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. Please find our detailed response below.\n\n---\n\n***”My main concern/confusion is the message of the paper.”***\n\nThe goal and achievement of the paper is the study of the performance of ERM non-asymptotically and under weak moment assumptions for the $p$-norm regression problem.\nWe motivate the ERM setting in the next paragraph.\n\n***”I'm a bit confused why we're studying the performance of ERM here, instead of designing better estimators that work under such mild moment assumptions.”***\n\nWe list a subset of the reasons why one would like to study ERM before trying to develop more sophisticated estimators with the optimal subgaussian performance under heavy tails.\n\n- Firstly, ERM is the most widely used method in practice, not the least because of its computational tractability, and so it is interesting to understand its performance and its failure modes.\n\n- Secondly, we decided to present our results under the weakest moment assumptions we could work with, which is why we incur the suboptimal $1/\\delta$ dependence on the confidence parameter. Note however that under stronger assumptions, e.g. subgaussianity of $X$ and $Y$, one may easily show root-logarithmic dependence on $\\delta$ using our proof techniques: it is enough to exploit the subgaussianity of $X$ and $Y$ to prove tighter concentration in Lemma 2. In such cases, which might occur in practical problems, ERM is likely to be competitive with the yet to be discovered, more sophisticated, \"subgaussian\" estimators.\n\n- Thirdly, just like the proof techniques used for the study of ERM for the case p=2 were very useful later in proving guarantees for more sophisticated subgaussian estimators, we believe that our proof techniques will serve as the basic machinery to study the performance of yet to be proposed estimators with subgaussian performance. In this sense, we view our work as a stepping stone towards the end goal the reviewer has outlined.\n\n---\n\n***”From my readthrough, it also appears that the paper is really bounding some expectation and using Markov to get the high probability bound. My question then, is, why is the paper phrased as a high probability result instead of an expectation/constant probability result, which I can imagine ERM to actually be decent at ?”***\n\nIn short, we do not have a bound on the expectation of the excess risk, and deriving such a bound requires non-standard assumptions. In more detail, we do not bound the expectation of the excess risk then use Markov's inequality, but rather combine two high-probability bounds: one of them is indeed coming from a bound on an expectation (Lemma 2), the other however is a uniform probability estimate (Proposition 1), and is in fact weaker than a bound on the expectation. Roughly speaking, this is because a bound on the expectation requires controlling the lower tail of the smallest eigenvalue of the empirical covariance matrix at all levels, whereas Proposition 1 provides a non-trivial bound only at a fixed level. Getting control over all levels requires non-standard assumptions (in particular, a quantitative version of the small-ball condition), please see (Mourtada, 2022) for such an approach and a thorough discussion of this issue.\n\n---\n\n***”The results are being compared to the asymptotic guarantees of ERM, but is there any evidence that ERM's asymptotic performance is statistically optimal (even when compared with other estimators)?”***\n\nOur goal and emphasis is to study the performance of ERM, so it is natural for us to compare our non-asymptotic guarantees with the asymptotic ones. The optimality of our bounds that we claim is in the sense that the leading term of our non-asymptotic bounds matches the asymptotically exact expression for the excess risk of ERM given by equation (1).\n\nConcerning the statistical optimality of ERM, if the reviewer is referring to minimax optimality over a given class of distributions, please see (Mourtada, 2022) for results for the case $p = 2$, where it is proven that, under mild regularity conditions, ERM is minimax optimal for well-specified models, and is asymptotically minimax optimal for misspecified ones. While we agree that it would be nice to extend such results to the cases $p \\neq 2$, this is outside the scope of our paper, and is an interesting future work. \n\n---\n\n***”Can the author(s) further elaborate on the extra moment assumption [...]?”***\n\nIt is an extension in the sense that when $p = 2$, this assumption reduces to the fourth moment condition of Theorem 1. We are afraid there is no straightforward \"intuitive\" interpretation of this assumption in terms of the interaction between the response and covariates. Nevertheless we qualified the assumption as natural in that it arises directly from the proof and in a completely analogous way to the proof of the case $p=2$.\n\n---\nWe would be happy to clarify any concerns or answer any questions that may come up during the discussion period.\n"}, {"review_id": "LH7gdf8SY6", "reviewer": "Reviewer_Ydss", "summary": "The paper studies the excess risk of empirical risk minimization on the $p$-norm linear regression. The asymptotic bound of the excess risk of ERM for $p$ in ($1,\\infty$) is known by prior work and more recent work had given high probability excess risk bounds for $p=2$ that match that asymptotic rate. This paper expands the result to $p$ in $(1,\\infty) \\setminus \\{2\\}$. It splits the results into three parts: It first provides bounds for the realizable case for $p \\in$ (1,$\\infty$). Then, a bound for the non-realizable case with $p$ $\\in$ (2,$\\infty$) where it requires mild assumptions on the moments that are natural extensions of the assumptions needed for the $p=2$ prior work’s result. For the non-realizable case with $p$ $\\in$ (1,2), the paper requires some additional assumptions: a slightly stronger version of non-realizability, assuming that the inner product of the covariates $x$ with the optimal minimizer $w^*$ is almost surely not equal to the label, and the existence of the $2(2-p)$ negative moment of $y-\\langle w^*,x \\rangle$.\n\nThe proof technique draws inspiration from Oliveira 2016, Lecue and Mendelson 2016b, which by itself is not sufficient. However, when combined with a recent result of Adil et al. 2022, the approach becomes valid by allowing the use of the second-order Taylor expansion, despite the fact that it is not exact. For the case of $p$ $\\in$ (1,2), a different approach is employed, utilizing an approximation for the $p$-th power function from Bubeck et al. 2018, along with the analysis of Adil et al. 2019a.\n", "questions": "What do the three regimes for $\\rho$ represent in Theorem 3?", "limitations": "Addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides the first high probability excess risk bounds of ERM for $p$-norm regression for $p \\in (1,\\infty)\\setminus \\{2\\}$ that are consistent with the existing asymptotic bounds. This is a considerable result. The paper does a very good job in describing the problem’s motivation, the problem’s background and the new results.", "weaknesses": "As the authors have already described, the case $p \\in (1,2)$ requires extra assumptions that it is unclear if they are necessary, leaving the goal of the paper for that regime only partially resolved.\n\nAlthough the paper writing is good in presenting the problem and the results, the proof strategy of the main results is not really discussed until later sections of the paper.\n\nAs a minor comment on writing, it would be better to provide a definition of $\\rho$ (or a reference to its definition) inside the theorem statements that use it. Similar comment for $\\sigma_p^2$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and constructive feedback. We will make sure to add a definition of $\\rho$ and $\\sigma_p^2$ inside the statements of the theorems to make them more readable.\n\n---\n\n***”What do the three regimes represent in Theorem 3?”***\n\nThey are an artifact of the particular probability bound we obtain in Theorem 3. Specifically, the three cases are needed to properly capture the dominating term in the sample complexity. This is due to the relative growth of the binomial coefficients compared to the exponential with base $\\rho$, which varies as $\\rho$ varies from 0 to 1.\n\n---\nWe would be happy to clarify any concerns or answer any questions that may come up during the discussion period.\n"}]

Author rebuttal:

Meta-review: All reviewers agree to accept this paper. The paper is theoretically sound and sufficiently novel to grant acceptance at this conference.

For a camera-ready version, please take into the account the comments from all reviewers regarding typos and clarifications. In particular, please include:
- a discussion of optimality as understood in this paper versus minimax optimality
- intuition about the moment assumptions for the well-specified case and general case as discussed during the rebuttal
Decision: Accept (poster)