On the Variance, Admissibility, and Stability of Empirical Risk Minimization
Authors: Gil Kur
Eli Putterman
Alexander Rakhlin
Venue: NeurIPS 2023 spotlight (2023)
Keywords: empirical risk minimization
bias-variance decomposition
admissibility
TL;DR: We show that the variance of Empirical Risk Minimization enjoys the minimax rate in various settings.

Abstract: It is well known that Empirical Risk Minimization (ERM) may attain minimax suboptimal rates in terms of the mean squared error (Birgé and Massart, 1993). In this paper, we prove that, under relatively mild assumptions, the suboptimality of ERM must be due to its bias. Namely, the variance error term of ERM (in terms of the bias and variance decomposition) enjoys the minimax rate. In the fixed design setting, we provide an elementary proof of this result using the probabilistic method. Then, we extend our proof to the random design setting for various models. In addition, we provide a simple proof of Chatterjee’s admissibility theorem (Chatterjee, 2014, Theorem 1.4), which states that in the fixed design setting, ERM cannot be ruled out as an optimal method, and then we extend this result to the random design setting. We also show that our estimates imply stability of ERM, complementing the main result of Caponnetto and Rakhlin (2006) for non-Donsker classes. Finally, we highlight the somewhat irregular nature of the loss landscape of ERM in the non-Donsker regime, by showing that functions can be close to ERM, in terms of $L_2$ distance, while still being far from almost-minimizers of the empirical loss.

On the Variance, Admissibility, and Stability of Empirical Risk Minimization
Gil Kur
Eli Putterman Mathematics Department Tel Aviv University
Alexnader Rakhlin BCS & IDSS MIT rakhlin@mi t. edu
EECS MIT
gi dilkur@mit.en t.rtt.iiieeuu
putterman@mail. tau. ac. i1
Abstract
It is well known that Empirical Risk Minimization (ERM) may attain minimax suboptimal rates in terms of the mean squared error (Birgé and Massart, 1993). this paper, we prove that, under relatively mild assumptions, the suboptimality of ERM must be due to its bias. Namely, the variance eтrоr term of ERM (in terms of the bias and variance decomposition) enjoys the minimax rate. In the fixed design setting, we provide an elementary proof of this result using the probabilistic method. Then, we extend our proof to the random design setting for various models. In addition, we provide simple proof of Chatterjee's 's admissibility theorem (Chatterjee, 2014, Theorem 1.4), which states that in the fixed design setting, ERM cannot be ruled out an optimal method, and then we extend this result to the random design setting. We also show that our estimates imply stability of FRM, complementing the main result of Caponnetto and Rakhlin (2006) for non- Donsker classes. Finally, we highlight the somewhat irregular nature of the loss landscape of ERM in the non non-Donsker regime, by showing that functions can be close to ERM, in terms of L2 distance, while still being far from of the empirical loss.
Introduction
Maximum Likelihood and the method of Least Squares fundamental procedures in statistics. The study of the asymptotic consistency of Maximum Likelihood has been central to the field for almost century (Wald, 1949). Along with consistency, failures of Maximum Likelihood have been thoroughly investigated for nearly as long (Neyman and Scott, 1948; Bahadur, 1958; Ferguson, 1982). In the setting of non- parammertiic estimation, the seminal work of (Birgé and Massart, 1993) provided sufficient conditions for minimax optimality (in non asymptoiiiic sense) of Least Squares while also presenting an example of a model class where this basic procedure is sub-optimal. Three decades later, we still do not have necessary and sufficient conditions for minimax optimality of Least Squares when the model class is large. While the present paper does not resolve this question, it makes several steps towards understanding the behavior of Least Squares equivalently, Empirical Risk Minimization (ERM) with square loss - large models.
Beyond intellectual curiosity, the question of minimax optimality of Least Squares is driven by the desire understand the current practice of fitting large overparametrized models, such as neural networks, to data (cf. (Belkin et al., 2019; Bartlett et al., 2020)). At the present moment, there is little theoretical understanding of whether such unregularized data-fitting procedures are optimal, and the study of their statistical properties may lead to new methods with improved performance.
In addition to minimax optimality, many other important properties of Least Squares on large models are yet to be understood. For instance, little is known about its stability with respect to perturbations of the data. It is also unclear whether approximate minimizers of empirical loss enjoy similar statistical
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

properties as the exact solution. Conversely, one may ask whether in the landscape of possible solutions. small perturbation of the minimizer output by Least Squares itself is a near-optimizer of empirical loss.
The contribution of this paper is to provide novel insights into the aforementioned questions for convex classes of functions in a quite generic setting. In detail, we show the following:
1. We prove that in the fixed design setting, the variance term of ERM is upper bounded by the minimax rate of estimation; thus, if the ERM is minimax suboptimal, this must be due to the bias term in the bias- decomposition. Then, we extend this result to random design, and provide an upper bound for the variance error term under a uniform boundedness assumption on the class. This bound also implies that under classical assumptions in empirical process theory, the variance error term is minimax optimal.
2.
We show that under an isoperimetry assumption on the noise, the expected conditional variance error term of ERM is upper bounded by the "lower isometry" remainder, a parameter that was introduced in Bartlett et al. (2005); Mendelson (2014). Next, under an additional isoperimetry assumption on the covariates, we prove that the variance of ERM is upper bounded by the lower isometry remainder on any robust learning architecture (namely, a class consisting of functions which are all (1)--ippshitz) which almost interpolates the observations (cf. Bubeck and Sellke (2023)).
3. It is known that ERM is always admissible in the fixed design setting (Chatterjee, 2014; Chen et al., 2017); that is, for any convex function class, there is no estimator having a lower error than ERM (up multiplicative absolute constant) on every regression function. We provide a short proof of this result for fixed design via a fixed-point theorem. Using the same method, also prove a somewhat weaker result in the random design case, generalizing the main result of Chatterjee (2014).
4. We show that ERM is stable, in the sense that all almost-minimizers (up to the minimax rate) of the squared loss are close in the space of functions. This result a non-asymptotic analogue of the asymptotic analysis in Caponnetto and Rakhlin (2006), and extends its scope to mon-Donsker classes.
5. While any almost-minimizer of the squared loss is close to the minimizer with respect to the underlying population distribution, the converse is incorrect. We prove that for any non-Donsker class of functions, there exists a target regression function such that, with high probability, there exists function with high empirical error near the ERM solution; this means that the landscape of near-solutions is, in some sense, irregular.
Conclusions Our results show that the ERM enjoys an optimal variance error term in two distinct regimes: the classical regime (van de Geer, 2000), where the function class is fixed and the number of samples is increasing, and the "benign overfitting" setting (Belkin et al., 2019; Bartlett et al., 2020), in which the "capacity" of the class is large compared to the number of samples. In both these settings, our work implies that the minimax optimality of ERM is only determined by its bias error term (or its implicit bias). For models with "few" parameters, computationally efficient bias correction methods do exist and are commonly used in practice (cf. (Efron and Tibshirani, 1994)). however, these methods fail over large function classes, in which the bias causes the statistical sub-optimality. Our work reveals the importance of inventing computationally efficient debiasing methods for rich function classes, including non- ponaamreetric models and tigh-dimessional models. The main message of our work is that such methods, if discovered, may significantly improve the statistical performance of ERM over large models in practice.
1.1 Prior Work
Stability of ERM The stability of learning procedures, which was an active area of research in the early 2000's, s, has recently seen resurgence of interest because of its connections to differential privacy and to robustness of learning methods with respect to adversarial perturbations. In the interest of space, we only compare present results to those of Caponnetto and Rakhlin (2006). In the latter paper, the authors showed that the Liddiameter of the set of dimost-minimizer of empirical error (with respect to any loss function) asymptotically shrinks to zero long the perturbation is o(n -1/2) and the function class is Donsker. The analysis there relies passing from the empirical

---

process to the associated Gaussian process in the limit, and studying uniqueness of its maximum using anticconcentration properties. While the result there holds without assuming that the class is convex, it is limited by (a) its asymptotic nature and (b) the assumption that the class is not too complex. In contrast, the present paper uses more refined non-asymptotic concentration results, at the expense of additional assumptions such as convexity and minimax optimal lower and upper lower isometry remainders, Crucially, the present result, unlike that of Caponnetto and Rakhlin (2006), holds for non-Donsker classes those for which the empirical process does not converge to the Gaussian process.
Shape-constrained regression The term "shape-constrained regression" refers to function classes consisting of functions with a certain "shape" property, such as convexity or monotonicity (Samworth and Sen, 2018). In these problems. common theme is that the statistical behavior of the class exhibits a phase transition when the dimension d of the domain reaches a certain value. For instance, in convex (Lipschitz) regression, the transition happens at d when 5, the ERM procedure is minimax optimal (Seijo and Sen, 2011; Han and Wellner, 2016; Kim and Samworth, 2016; Seijo and Sen, 2011; Guntuboyina, 2012), but in higher dimensions, it known be suboptimal (Kur et al., 2020a.b). In other stupe-constraile in high dimensions, such as isotonic regression and log- log-coneave density estimation (Han al., 2019; Kur et al., 2019; Carpenter et al., 2018). Our results show that the sub-optimality of ERM in shape-constrained regression can only be due the high bias of ERM. These results also align with the empirical observation that for the problem of estimation of convex sets, the ERM has a bias towards "smooth" " convex sets (Soh and Chandrasckaran, 2019; Ghosh et al., 2021).
models, however, the ERM is minimax optimal even
High-dimensional statisties In classical statistics, the Maximum Likelihood (MLE) typically has low bias compared to its variance, and the standard approach is to introduce bias into the procedure in order reduce the variance, overall achieving better trade-off (see (Sur and Candès, 2019, $1) and references therein). In contrast, in high-dimensional models, the MLE may suffer from high bias even in tasks such logistic regression and sparse linear regression (ef. Candès and Sur (2020); Javanmard and Montanari (2018)). Our results align with this line of work, showing that the problem of high bias may also arise in the task of regression over rich function classes.
Main Results
In $2.1, we present the setting of our model and the all required preliminaries, and the remaining sub-sections, we present our results. In details, in $2.2-2.3, we present our results on the variance of ERM in fixed and random designs respectively, and in $3 we provide sketches of some of our proofs. For lack of space, we presents our admissibility and our landscape results on ERM in the supplementary material ($4.1.4.2).
2.1 Preliminaries
Let X' be some fixed domain, F be class of functions from X' to IR, and f F unknown target regression function. We are given n 2 2 data points X1 X1..., Xn E X' and n noisy observations
Y; f + Ei, i i= I,...,
(I)
which we denote by D
= {(,,, ;;);;;; = : ..)) is the random noise vector.
In the fixed design setting, the observations X1 Z1...., X,, T, are arbitrary and fixed, and we denote the uniform measure on this set of points by pp(n), In the random design setting, the data points == (XI,..., X,,) are drawn i.i.d. from a probability distribution over X, denoted by IP, and the noise vector E is drawn independently of X. Note that this model is general enough to cover the high-ding high-dimensional setting, as both the function class F and the distributions of & and X are allowed to depend the number of samples
An estimator for the regression task is defined as measurable function Ju. D - {X R), that for any realization of the input D, outputs some real-valued measurable function on X.. The risk of fn is defined as
/ (Tn ( d
R(Fn, F, = sup ED
(2)
where Q = P in the random design case, and Q p(n) the fixed design case. Note that in fixed design, the expectation Ep is taken over the noise &. while in random design the expectation Ep is
3

---

taken both over the random data points X and noise &. The minimax rate is defined via
M(n, = inf R( F,Q) Q).
fm
In the fixed design setting, we also denote the minimax rate by M(F, (P()), the dependence in is already present in [p(n).
The most natural estimation procedure is the Least Squares (LS) Empirical Risk Minimization (ERM) with squared loss, defined as
Fn argmin fEF ( - -1)
When studying fixed design, we will abuse notation and treat fr as vector in R We emphasize that many of our results hold for many other estimators, including various regularized ERM procedures (see the relevant remarks below).
In both the fixed and random design settings, we shall assume the following:
Assumption 1. F is a closed convex subset of L2(Q), where Q {Ip("),P}
The convexity of F means that any J,g E F and X E [o, 1]: A/ (1 A)y F; closedness means that for any sequence {fn C F converging to f with respect to the norm L2( the limit f lies in F. The closedness ensures that fn is well-defined.
Assumption 1 is standard in studying the statistical performance of the ERM (cf. Lee et al. (1996); Bartlett et al. (2005); Mendelson (2014)). In particular, under this assumption, the values of Jn the observation points X1 Xı.-.., X, is uniquely determined for any &. Note that in general, the values of a function f F the points _,...., Xn, does not uniquely identify f among all functions in the class.
In addition to fr. we analyze properties of the set of 8-approximate minimizers of empirical loss, defined for 5 > 0 via
Os = -==SET
0x=f1ee
1 - Ix(x)))) +
<
(5)
==1
Note that Og is a random set, in both fixed and random designs.
is well-known that the squared error of any estimator, in particular that of LS, decomposes into variance and bias components:
Ep | ( = ED 1 =d0
/ (Bo (
(6)
v(fa)
B²(
where pp(n) in the fixed design setting and Q = P in random design setting. Also, for simplicity of the presentation of our results, denote the maximal variance error term of fa by Vf F,
sup V(T)) ED Tn
In the random design setting, also have the law of total variance:
v(r.) Ex / (fr Es 1 dP
+ Ex
Eg F X
Ex
dIP
(7)
EV(F.X) X))
v(B(f.II))
We refer to the two terms as the expected conditional variance and the variance of the conditional expectation, respectively. We conclude this introductory section with bit of notation and definition.

---

Notation We use the notation of x, 2. S to denote equality/inequality up to an absolute constant. We use =| lllggr to denote the (1P) norm, and Ilx to denote the L (1P(a) norm (that is equal to the Euclidean norm scaled by 1/vn). Finally, given function f S + T between metric spaces, define its Lipschitz constant |l SUPo,bET, dr(f(m).f(()) and we say "f is ds(a,))
L-Lipschitz" when its Lipschitz constant is at most L. Finally, we denote by diamo(H) the Lz(Q) diameter of set of functions H.
Definition Let c 2 O, O. F.F C (X -R) and d(-.-) a pseudo-metrics on F. We call set S F an e-net of F with respect to d for any f E F there exists g E S with d(f.9) S c. We denote by Ne,FF.l .d) the e-covering number of F with respect that is, the minimal positive integer N such that F admits e-net of cardinality N.
2.2 Variance of ERM in fixed design setting
In this part, we consider some fixed (F,P()) and assume that the noise is standard normal.
Assumption 2. The noise vector is distributed an isotropic Gaussian, i.e. & N(O, Iaxa).
Our first result provides an exact characterization of the variance (up to a multiplicative absolute constant) under Assumptions 1-2. In order to state it, for fixed ʃ* F, we define the following set:
H. ( -
V(f.))
8
In words, when the underlying function f is fixed, we consider the ERM as a random vector (depending the noise), whose expectation we denote by ED H. is then just neighborhood around the expected ERM with radius of order the square root of the variance error term of Jn. when the underlying function is f* F.
We can now state our first result, which uses the notion of the set O₂ of 8-approximate minimizers from (5).
Theorem 1. Under Assumptions 1-2, the following holds:
Vo(fn) x =MH.,, p(n)),
F, and in particular V(nn F(1((n) $ M(F,Ip(n), Furthermore, 8(f*, ((H,,,
the event
/ (S-ED. P = MMH., p(()).
sup FEO,
(9)
holds with probability at least max(1 exxp(-en M(H,, 0.9}, where E (0, is an absolute constant.
Theorem establishes our first claim: the variance of ERM is bounded above (up to a multiplicative absolute constant) by the minimax rate of estimation on H.. Since H. is contained in F, its minimax rate is at most that of F; in particular, the variance of ERM is bounded by M(F, P(n)), and hence, any sub-optimality of ERM must arise from its bias. The theorem also incorporates stability result: not only is the ERM close to its expected value Epfn, with high probability, but any approximate minimizer (up to an excess error of 62) is close to Epf., as well.
Our next result complements Theorem I above, providing lower bound on F(F,,F
Theorem 2. Under Assumptions 1-2, the following holds:
F, F, 2 MMF, p())22
Note that there is a multiplicative gap of order M(F p(n)) between the bounds of Theorems 1 and We leave it as an open problem whether the bound of Theorem 2 can improved under these general assumptions.
5

---

2.3 Variance of ERM in random design sefting
We now turn our attention to the random design setting. Here, we establish similar results to the previous sub-section, albeit under additional assumptions, and with significantly more effort. Unlike the fixed design case, we cannot provide an exact characterization of the variance of ERM. We shall two different approaches estimate the variance tools of empirical process theory together with assumptions that are commonly used in M-estimation (van de Geer, 2000). The second approach, which is inspired by our fixed-design approach, relies heavily on isoperimetry and concentration of measure (cf. Ledoux (2001)).
term. In the first approach, use classical
Throughout this part, we assume for simplicity of presentation that the (22(P) diameter of the function class is independent n.
Assumption 3. There exist absolute constants C, > such that c S diamp S
(F)
The classical work of Yang and Barron (1999) provides characterization of the minimax rate F, under appropriate assumptions (such as normal noise, and uniform boundedness F, and richness of F). They proved that the minimax rate is the square of the solution of the following (asymptotic) equation
log log,N(e, x ne?
(10)
where (e,, F, denote this point by = (n), and even under less restrictive assumptions, e² also lower bounds the minimax rate, up a multiplicative factor of O(log n). Also, we remark that well known that ERM may not achieve this optimal rate (Birgé and Massart, 1993) for large (so-called non- con-Donsker) function classes.
the e-covering number of F in terms of L2(P) metric (see Def. above). We
We also introduce the following additional notations and definitions: First, I,, denotes the (random) uniform measure over X = (X1,..., x.,) Next, following Bartlett al. (2005), define the lower and upper isometry remainders of (F.P) for a given n. These remainders measure the discrepancy between L2 (P) and "typical" (2(P,), here "typical" means for most of realizations of X. These remainders first emerged in the field of metric embeddings, specifically in the definition of quasi-isometries (cf. Ostrovskii (2013)).
In order to introduce these isometry remainders, we first define for each realization of the input X. the constants Zr, (X) and Tez (X) as the minimal numbers Ax, Bx 2 O, respectively, such that the following holds:
VfgEF: 4-1 V 4U- -x S
A 9 S <4f11- 18- 9)
+ Bx.
Note that Ax and Bx increase, the geometry of (P,,,, and (TP) over FF becomes less similar. For example, in the extreme case of Ax = Bx = O, it implies the L2(P) and L2 (I),, induce the same topology over F. In words, the lower isometry is the minimal threshold that satisfies the following: all f.g E F that are (X)( far from each other in (2P),, must be at least O[ - gll) far in (2( The upper isometry remainder implies the converse. To provide further intuition on these remainders, for instance, observe that Iz (X) upper bounds on diameter in (2()) of possible solutions of ERM; namely, one has
sup EEE
Diamp (1S F
<x.I.
Finally, the isometry remainders Iz (n), (n) are defined as the "typical" values of Ir, (X), Io (X):
Definition 2. The lower and upper isometry remainders (n),,, (n) are defined as the minimal constants An, Bn, 2 0 (respectively) such that
Pr( < A,) 2 21 1 -n and (r < Ba) > - -1
X
In the classical regime (van de Geer, 2000). it is considered to be a standard assumption that max (m), (n)) S 2.. However, in the high dimensional setting, may happen that the lower isometry remainder is significantly smaller than the upper isometry remainder, e.g., (n) S e and

---

(n) > E. (cf. Liang et al. (2020); Mendelson (2014)). We discuss these remainders further in Remark 10 below.
Finally, we remind the reader that fn is uniquely defined on the data points X when F is a convex closed function class, but it may not be unique over the entire X' (as multiple functions in F may take the same values at ..,..., xx)). In $2.3.1, the results hold for any possible solution of f. over X, whereas in $2.3.2, we (implicitly) assume that Jn is equipped with selection rule such that also unique over the entire X' (e.g., choosing the minimal norm solution (Hastie et al., 2022; Bartlett et al., 2020)); ie, fn D
2.3.1 The empirical processes approach
Here, we assume that the function class and the noise are uniformly bounded.
Assumption There exist universal constants 1, > such that is uniformly upper-bounded by T1, i.e. sup || Tıi; and the components of & (E1...., are i.i.d. zero mean with variance one and are almost surely bounded by 1'2.
Remark 1. The uniform boundedness assumption on the noise is taken to simplify the proof (which uses of Talagrand's s incquality). This can be relaxed the assumption that the noise is i.i.d. sub- Gaussian, at the price of multiplicative factor of O(log n) in the error term in Theorem 3 below.
Definition 3. Set ey max(e., é}. where ė is the solution of
[n(n)) Log.
ne.
(11)
Note that when (n) S E,, et x e., while if Iu (n. P) > 2 then ev >> c.. The following is our main result in this approach the random design setting:
Theorem 3. Set Et == max ( (n)), then under Assumptions 1,3,4 the following holds with probability of at least 1 n
J (D-)) Vi
sup
fEC
where 6,, Oct)); and in particular F,P
Theorem is generalization of Theorem 1 to the random design case, and its proof uses the strong convexity of the loss and Talagrand's inequality. In $5.1 below, we discuss this bound in the context of "distribution unaware" estimators. We remark that this Theorem extends the scope of Caponnetto and Rakhlin (2006) to non-Donsked classes.
An immediate and useful corollary of this result is that if we have sufficient control of the upper and lower isometry remainders, the variance will be minimax optimal:
Corollary 1. Under Assumptions 1,3,4 and (n), (o))) S e the following holds:
F(F
In the classical regime, the assumption that max max (n), Io [n)} S e is considered to be standard in the empirical process and shape constraints literature (cf. van de Geer (2000) and references therein); it holds for many classical models (see Remark 11 below).
Remark 2. Note that Corollary may also be derived directly from Theorem if the noise is assumed to be standard Gaussian. Yet, this corollary holds for any isotropic aab-aussiin noise which is significantly more general.
2.3.2
The isoperimetry approach
In order to motivate this part, we point out that just requiring that (n. S is considered to a mild assumption (see Remark 10 below). However, the upper bound of Theorem 3 depends on the upper isometry remainder as well; we would like to find some conditions under which this dependency can be removed. Moreover, note that the isometry remainders connected to the geometry of
7

---

(F.P) and not directly to the stability properties of the estimator. Using different approach, based on isoperimetry. we will upper- upper-bound the variance of ERM based on some "interpretable" stability parameters of the estimator itself. These stability parameters will be data-dependent relatives of the lower isometry remainder. Differently from the previous part, we do not assume that the function class F is uniformly bounded by constant independent of the sample size n.
First, we introduce the definition of Lipschitz Concentration Property (LCPP):
Definition 4. Let Z = (Zi...., Zm) be random vector taking values in 2%m Z satisfies the LCP with constant O, with respect to a metric d (z gom) - Rt, for all F 2 + lR is 1 --ipssciitz the following holds:
Pr([F(Z) - EF(Z) 2 < 2 2eepppxppp cxt
(12)
The LCP property also known as the isoperimetry condition (cf. (Bubeck and Sellke, 2023, $1.3)), and it is stronger than being uub-Gaussian (Boucheron et al., 2013), and yet it is significantly less restrictive than requiring normal noise (in which case cr. 1/2 (Ledoux, 2001)); for further details see Remark 9 below. Now, we state our first assumption:
Assumption 5. & an isotoopic random vector satisfying (12) with constant cr (1), with respect to the Euclidean norm in IR".
Recall that c, is defined as the stationary point of nc² x log (,c,FF and that the conditional variance of Jn, which is function of the realization X of the input, is defined as
V(x Bell Ee[fx
that is, we fix the data points X and take expectation over the noise.
The formulation of the following definition involves a ret-to-be-detined (large) absolute constant M > O, which will be specified in the proof of Theorem 4 (see $3.2 below).
Definition 5. For each realization X and f F. let (X, f*) be defined the minimal constant 8(n) such that
Pr f E IR" :V'' E B,,E, (x,' - fn( < 6(m) 2 exp(-ceme,). (13)
where Bn, (E' E R" 1e -''ll S r), and C2 > is an absolute constant.
We also set PX( == sup supreF "robbstness"") of Jn to perturbations of the noise when the underlying function and data points X are fixed. This is weaker notion than the lower isometry remainder; in fact, one can verify that px( S max (X).2) for every realization X (see Lemma 12 for completeness). Now, we are ready to present our first theorem:
(X( measures the optimal radius of stability (or
Theorem 4. Under Assumptions 1,3,5, the following holds for every realization X of the data:
VD VD ( & max (x) f)
and in particular s'pp'er er ExVp (F. X) S max(Iz (n),
Note that if (n) S 2 a very mild assumption - then we obtain that the expected conditional variance is minimax optimal. However, we believe that it is impossible to bound the total variance via the lower isometry remainder alone. Intuitively, fn only observes a given realization X, and in general, the geometry of F may "look different" under different realizations if I, is large (see the discussion in $5.1 for further details).
In next result, we identify model under which lower isometry remainder. To state the next assumption, we fix a metric d. X' x X' R on X, and denote by d, the metric x given by d,, (x,X') x')² = E d(Xi, X!)2.
bound the total variance of fa by the
Assumption X ~ ppn satisfies (12) with respect to the metric da(,s) and with constant cx that only depends on P
8

---

Note that it is insufficient to assume that X ~ P satisfies an LCP, since this does not imply that X satisfies an LCP with constant independent of n (w.rt. d,, (..)). However, if X IP satisfies concentration inequality which tensorizes "nicely," such as log-Sobolev or Wy-transportation cost inequality (cf. (Ledoux, 2001, $5.2, $6.2)), then X ~ pon does satisfy this LCP property.
Next, we assume that with high probability, fn close to interpolating the observations:
Assumption 7. There exist absolute constants cj, Cf > O, such that the following holds:
Pro (fx,)
- Y,) = C.e. n) 2 1 exp( exp(-eene?)
This assumption is quite common in the study of "rich" high dimensional models (i.e. when the function class F depends on n; see, e.g., Belkin et al. (2019); Liang and Rakhlin (2020)) which are prominent in the recent benign overfitting literature.
Finally, we introduce another stability notion. Recall the random set O2 C F of almost-mmnimizers of the empirical loss, defined in (5) above: note that, in the random design setting, O₂ depends both X and g. The random variable diam: (Os) can be thought of as measuring the stability of the ERM with respect to imprecision in the minimization algorithm (cf. (Caponnetto and Rakhlin, 2006)). The formulation of the following definition involves another yet-to-be-defined (large) absolute constant M' > O, which will be specified in the proof of Theorem 5 (see $6.6 below), as well as the constant ei from Assumption 7.
Definition 6. po P, P*) is defined as the smallest 8(n) 2 0 such that
(O(de) S vō(n)) > 2 2eex(p=ccnee D
(14)
where 2 0 is the same absolute constant defined in Assumption 7.
In order to understand the relation between this and the previous stability notions, note that under Assumption and the event of Definition 6, we have that on an event of nonnegligible probability,
ps(X. f*) po (n, IP, f*) in addition, po (n, P, f*) S max (n), e (see Lemma 13 below). Under these additional two assumptions and the last definition, we state our bound for the total variance of In:
Theorem 5. Under Assumptions 1,3,5-7, the following holds:
Vo(fa) Sex
sup || FCFF
poln,,
and in particular one has V( F,F, -uppy ||pp (
Note that when F is a robust learning architecture (i.e. J C (X
[[p 011)), our bound is optimal. Interestingly, the assumptions of Theorem: 5 coincide with those of the model considered the recent paper of Bubeck and Sellke (2023). Also note that the last theorem connects the total variance of fm to a "probabilistic" threshold for the (z2))) of the data-dependent set of ( approximating solutions of T. two parameters which at first sight are unrelated.
Remark 3. One may suspect that the assumptions of almost interpolation and robustness are in- compatible, which would render our theorem vacuous. However, perhaps counter-intuitively, in the high-dimensional setting these assumptions can coexist. For example, interpolation with O(1)- Lipschitz functions may be possible when the "intrinsic" dimension of X' is ([(og(n)) (depending on the richness of F), though it is generally impossible when the dimension is (n)) (this follows from the behaviour of the entropy numbers of the class of Lipschitz functions; cf. Dudley (1999)).
Remark 4. Using Assumptions 1.3,5-6, may prove the same bound in Theorem 3, i.c. that F, S et without requiring the noise or the function class be uniformly bounded. The idea is to obtain the crucial concentration bounds in the proof of Theorem 3 by using the LCP properties of & and X IP along with the robustness of F. rather than via Talagrand's inequality.

---

3
Proof sketches
In this section, we sketch the proofs of less-technical results to give the reader a flavor of our methods. The full proofs are given in the next section. For the proofs we introduce some additional notations. For m E N, we set [m] = m... The inner products in (2)P), L (P(()) are denoted by (, (ts nn respectively.
3.1 Sketch of proof of Theorem 1
Here, we sketch a simple proof of a weaker version our result, namely Vo(fa) S M(F, p(")). under the stronger assumption that
M(F,P!n)
(15)
where solves log Ne,, F, p(n) x ne? (This holds under reasonable assumptions on F, but can be dispensed with; see Lemma for the exact characterivation.) In $6.1.1, we fill the details of this sketch, and in $6.1.2, give the full proof of Theorem 1.
The proof uses the probabilistic method (Alon and Spencer, 2016). Let fI,..., I'N be centers of minimal <.veer of J with respect (2(()))), per Definition 1. First, since for any E [N] the map & + fm
fill Ilo is I-Lipschitz, (12) and a union bound ensure that with probability at least 1 2N for all i [N].
log N n
Egll fill. 1lfm felln 2
On the other hand, by the pigeonhole principle, there exists at least one i E [N] such that with probability at least 1/N, Il.m - ft- lln S c.. Hence, there exists at least one realization of & E R" for which both bounds hold, and thus, deterministically.
Eg f.. - ft- II Sea + V log
Se.
where used the balancing equation (10). Another application of (12) and integration of tails yields
V(h)) = Ep fI fn s EDDIf fi 112 S e
implying that the variance of ERM is minimax optimal.
3.2 Sketch of proof of Theorem 4
As is well-known, the Lipschitz concentration condition (12) is equivalent to an isoperimetric
phenomenon: for any set A C Th" with (rę(A) 2 1/2, its I-neighborhood A, (E IR" infae || El < t} satisfies
Pr(A.) 2 exxp(-n(212)
(16)
One sees quickly that this implies that if has measure at least 2 exp( (nnp(/n then Ag has measure 1 - 2 exp(-nt² /2).
Let & be the event of Definition As in $3.1 above, one obtains via the pigeonhole principle and the definition of e. that there exists some fo E E such that
Pre(E)
Pr(lfm B(f
2 exp(=Csnee) N,E,F
By isoperimetry, (rę(Ax) 2 11 - 2 2exp(-nt? nnt/2), where Mcx/2 and M is chosen such that (M/2)² 2 2C3; this fixes the value of the absolute constant M used in (13).
Applying (13) yields that i E C and - S Mc, 21, (l. - fa(E')ll S ps(X, and so [[a)(e") - fall S e, + *s(,, S*). This implies
Pr( B(fare, + pX( {())) 2 Pr(An1X) 2 1 2tx
which implies via conditional expectation that V(fx S max (ps(X)()))))))
(X).)) {) as desired (where we used that e 2 log(n)/n (see Lemma 3 below), and therefore exp(-nt") O(e2))
10

---

Acknowledgements: This work was supported by the Simons Foundation through Award 814639 for the Collaboration on the Theoretical Foundations Deep Learning, the ERC under the European Union's & Horizon 2020 research and innovation programme (grant agreement No 770127), and the NSF (awards DMS-2031 1883, DMS-195318) Part of this work was carried out while the first two authors authors were in residence at the Institute for Computational and Experimental Research in Mathematics Providence, RI, during the Harmonic Analysis and Convexity program; this residency was supported by the NSF (grant DMS-1929282 Finally, the first two authors also wish to acknowledge Prof. Shiri Artstein-Avidan for introducing them to each other.
References
Charalambos D. Aliprantis and Kim C. Border. Infinite Dimensional Analysis: Hitchhiker's Guide. Springer, Berlin; London, 2006. ISBN 9783540326960 3540326960. doi: 10.1007/3-540-29558
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman. Asymptotic geometric analysis, Part I, volume 202 of Mathematical Surveys and Monographs. American Mathematical Society, 2015.
RR Bahadur. Examples of inconsistency of maximum likelihood estimates. Sankhyā: The Indian Journal of Statistics, pages 207-210, 1958.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. The
Annals of Statistics, 33(4): 1497-15777 2005.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear
regression. Proceedings of the National Academy of Sciences, 117(488):0063-30077) 2020.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
Lucien Birgé and Pascal Massart. Rates of convergence for minimum contrast estimators. Probability Theory and Related Fields, 97(1-2):1 13-13-11-5 150, 1993.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Journal of the ACM, 10(2):1-18, 2023.
Emmanuel Candès and Pragya Sur. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, +8(1):27-43 2020.
Andrea Caponnetto and Alexander Rakhlin. Stability properties of empirical risk minimization over Donsker classes. Journal of Machine Learning Research, 7(22). 2006.
Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, and Alistair Stewart. Near-optimal sample complexity bounds for maximum likelihood estimation of multivariate log-coneave densi- ties. In Conference On Learning Theory, pages 1234-1262, 2018.
Souray Chatterjee. A new perspective on least squares under convex constraint. The Annals of Statistics, 42(6)22340--381, 2014.
Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. A note on the approximate admissibility of regularized estimators in the gaussian sequence model. arXiv preprint wwXiv:1703.00544 2017.
Richard M Dudley. Uniform central limit theorems. Number 63. Cambridge University Press, 1999.
Bradley Elron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994.
Thomas Ferguson. An inconsistent maximum likelihood estimate. Journal of the American Statistical Association, 77(380):831-834 1982. ISSN 01621459.

---

Avishek Ghosh, Ashwin Pananjady, Adityanand Guntuboyina, and Kannan Ramchandran. Max-affine regression: Parameter estimation for gaussian designs. IEEE Transactions on Information Theory, 2021.
Adityanand Guntuboyina. Optimal rates of convergence for convex set estimation from support functions. The Annals of Statistics, 40(1):385-411, 2012.
Qiyang Han and Jon A Wellner. Multivariate convex regression: global risk bounds and adaptation. arXiv preprint 1rxivv 2016.
Qiyang Han, Tengyao Wang. Sabyasachi Chatterjee, and Richard J Samworth. Isotonic regression in general dimensions. The Annals of Statistics, 47(5):2440-24777 2019.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, 2022.
Adel Javanmard and Andrea Montanari. Debiasing the lasso: Optimal sample size for gaussian designs. The Annals of Statistics, (0(6A))259332622)) 2018.
Arlene KH Kim and Richard J Samworth. Global rates of convergence log-concave density estimation. The Annals of Statistics, 44(6):2766-275) 2016.
Vladimir Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d' Eté de Probabilités de Saint-Flour XXXVIII 2000,, volume 2033. Springer Science & Business Media, 2011.
Gil Kur and Alexander Rakhlin. On the minimal error of empirical risk minimization. In Conference on Learning Theory, pages 2849-28522 PMLR, 2021.
Gil Kur, Yuval Dagan, and Alexander Rakhlin.
Optimality of maximum likelihood for log-concave density estimation and bounded convex regression. arXiv preprint arXiv:/903.0531 1903.05315, 2019.
Gil Kur, Fuchang Gao, Adityanand Guntuboyina, and Bodhisattva Sen. Convex regression in multidimensions: Suboptimality of least squares estimators. arXiv preprint arXiv:2006002044, 2020a.
Gil Kur, Alexander Rakhlin, and Adityanand Guntuboyina. On suboptimality of least squares with application to estimation of convex bodies. In Conference on Learning Theory, pages 2406-2424. PMLR, 2020b.
Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper and minimax bounds. arXiv preprint arXiv:1305.4888 2013.
Michel Ledoux. The concentration of measure phenomenon. Number 89 in Mathematical Surveys and Monographs. American Mathematical Soc., 2001.
Wee Sun Lee, Peter L Bartlett, and Robert C Williamson. The importance of convexity in learning with squared loss. In Proceedings of the Ninth Annual Conference Computational Learning Theory, pages 140-146, 1996.
Tengyuan I. Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-134) 2020.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-none norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, pages 2683 27 PMLR. 2020.
Shahar Mendelson. Learning without concentration. In Conference on Learning Theory, pages 25 25-39, 2014.
Shahar Mendelson. Extending the scope of the small-ball method. arXiv preprint 1eXiv:170.00082 2017.
Emanuel Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Inven- tiones mathematicae, 177(1):1-43 2009.
12

---

Matey Neykov. On the minimax rate of the gaussian sequence model under bounded convex constraints. IEEE Transactions on Information Theory, 69(2):1244-1260 2022.
Neyman and Elizabeth L. Scott. Consistent estimates based on partially consistent observations. Econometrica, 16(1):1-32, 1948. ISSN 00129682, 14680262.
Mikhail I Ostrovskii. Metric embeddings: Bilipschitz and coarse embeddings into Banach spaces, volume 49, Walter de Gruyter, 2013.
Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy, minimax regret and minimax risk. Bernoulli, 23 2017.
Richard Samworth and Bodhisattva Sen. Special issue on "nonparametric inference under shape constraints". 2018.
Rolf Schneider. Convex bodies: the Bramn-Minkowski theory. Number 151 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2014.
Emilio Seijo and Bodhisattva Sen. Nonparametric least squares estimation of a multivariate convex regression function. The Annals of Statisties, 1933):1633-1657, 2011.
Yong Sheng Soh and Venkat Chandrasekaran. Fitting tractable convex sets support function evaluations. arXiv preprint
2019.
Pragya Sur and Emmanuel Candès. A modern maximum-lkceliood theory for high- nigh-dimensional logistic regression. Proceedings of the National Academy of Sciences, 149-)-):4516--444 2019.
Sara A van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge University Press, 2000.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018
Martin J Wainwright. High-diienssoonl statistics: non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
Abraham Wald. Note on the consistency of the maximum likelihood estimate. The Annals of Mathematical Statistics, 20(4):595 601, 1949.
Yuhong Yang. Aggregating regression procedures to improve performance. Bernoulli, 10(1):25-47, 2004.
Yuhong Yang and Andrew Barron. Information-theoree theoretic determination of minimax rates of conver- gence. Annals of Statistics, pages 1564-1599 1999.
13


Reviews:
[{"review_id": "dWc7xHaPFy", "reviewer": "Reviewer_XB3R", "summary": "This paper studies the classic problem of regression under noisy observations, with a convex and closed function class $\\mathcal{F}$. In particular, the paper considers the performance of the Empirical Risk Minimizer (ERM) under the mean squared error, in both the fixed design and random design settings.\n\nAt a high level, the author(s) show that:\n1. The variance of the ERM is comparable to the minimax rate of regression, implying that when ERM is not minimax-optimal, it must be due to large bias\n2. ERM is admissible up to constant factors, via a simpler proof using fixed point theorems\n3. ERM enjoys stability, in the sense that all almost-empirical-loss-minimizers also have similar expected loss as the actual empirical loss minimizer.\n4. For \"non-Donsker\" function classes, the converse of 3 is false, that there is always some ground truth function $f^* \\in \\mathcal{F}$ such that, with high probability over the samples and noise, there is a function $f_{\\mathrm{bad}}$ whose expected loss close to the ERM, but that its empirical loss is much larger than the ERM's.\n\nI did the following review as an emergency review, so I did not check the details/appendices carefully.", "questions": "Minor questions and comments:\n1. Please consider using the same number-counter across all of definitions/theorems/assumptions. It was hard to scroll through the paper looking at backward references when reading.\n2. (Line 164) The author(s) mention that $\\mathcal{G}_\\ast$ in Theorem 2 can replace 2 with any other absolute constant. How does the replacement propagate to Theorem 2? Does it change the constants in the $\\asymp$?\n3. Theorem 6, the assumptions 1,2,4,6 have nothing to do with the instantiation of $\\mathbf{X}$?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The ERM is perhaps the most commonly used regression estimator. This paper furthers our understanding of its behavior, particularly for function classes where ERM isn't minimax-optimal. I found the introduction well-written, describing each result at a high level. I also find the observation that \"non-minimax-optimality must be due to bias\" to be an interesting result.", "weaknesses": "While I liked the paper, and recommend a weak accept, I think there are the following writing/presentational issues that can be improved. Overall, my comment is that the paper currently perhaps reads better for experts who have worked on ERM (or at least, in empirical process theory), but not that easy to read for a more general learning theory audience.\n\n- The paper reads a bit like a collection of related results, but without a \"main point\", and could maybe be strung together better as a story. For example, the \"variance <= minimax-rate\" result and the stability result seem somewhat disjoint in the introduction, even though later on in Theorem 1, they are shown together as one big result. I was also a bit confused about the writing in Section 2, in terms of the narrative. For example, I don't quite understand how Theorem 2 \"complements\" Theorem 1 (cf. Line 150), though Theorem 2 is a cool result itself with the local minimax optimality and is used to prove Corollary 1 (the admissibility result). Moreover, Theorem 3 also \"complements\" Theorem 1 (cf. Line 185), but there's a quadratic gap. Is the gap necessary?\n\n- I also found that the technical Section 2 is a bit too heavy on definitions and assumptions and not enough interpretation. When I was reading, I felt that the author(s) tried hard to succinctly give the most general results that are shown, but in my opinion, for readability, it might be better to start with simpler cases (and perhaps even informal versions) of statements (particularly the assumptions), and provide more interpretation.\n\n- Related to the above point, some of the assumptions/quantities in the results are stated without much interpretation or intuition (in the main body). There are also a few comments along the lines of \"this assumption is considered mild in the literature/by some other authors\" without much additional interpretation. This makes the paper not quite as self-contained as it could be. This issue is particularly prevalent in Section 2.2 (especially the isoperimetry assumptions), and it became quite hard to interpret the results. I can see that there are some remarks in the appendices, but I think a lot of them really should be in the main body for readability.\n\n- The term non-Donsker was never defined in the main body, even though it is a key element in a main result. While Donsker classes are a basic object in empirical process theory, I don't think it should be assumed knowledge for the general theory reader. There is also a lack of discussion on whether Theorem 4 only hold for non-Donsker classes, or more generally what's the significance of the assumption: whether it's a necessary condition for the result, or just that this is the result that can be proved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed report. Following your comments as well as those of other reviewers regarding the density of results in the paper, in the revised version, we moved the relatively technical Theorem 2 to the appendix and inserted more explanations/intuition into the main body, which the more generous page limit for the revision enabled us to do.\n\nRegarding some of the specific points raised by this review:\n\n- The minimax optimality of the ERM's variance and its stability are conceptually distinct phenomena and thus explained separately in the introduction, but mathematically they are so closely linked that it is easier to present them together in Theorem 1.\n- Theorem 2 complements Theorem 1 mainly in the sense that they are both needed to prove the ERM's admissibility. In any case, Theorem 2 will be relegated to the appendix in the revision. \n- Regarding the quadratic gap between Theorem 3 and Theorem 1, we do not know if it is necessary, but we do not currently know how to improve it. \n- \"The paper reads a bit like a collection of related results, but without a \"main point\", and could maybe be strung together better as a story.\" - see Item 1 in the rebuttal for all reviewers. Also, we improved the organization to the paper that the main points and the applications appear before the main results -- that are more techincal in their nature.\n- \"The term non-Donsker was never defined in the main body\" - we will add a definition and some examples for non-Donsker classes and move this result to the random design section, and provide some more motivation as well.\n- \"I also found that the technical Section 2.... Related to the above point, some of the assumptions/quantities in the results are stated without much interpretation'' - Again, we have moved some results to the appendix, which along with the extra page frees up room to add more explanations and concrete examples, especially in the random design setting."}, {"review_id": "uD024yWxDi", "reviewer": "Reviewer_vswn", "summary": "The paper considers  the Empirical Risk Minimization (ERM) problem with squared loss and shows that the suboptimality of ERM is due to the bias rather than variance.", "questions": "I found that this paper is more suitable for conference like COLT instead of NIPS. Audience from learning theory filed might be more interested in this topic.", "limitations": "More examples and applications should be included. Otherwise, it is a merely technical paper with no practical usage.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper is quite theoretical and technical. The paper provides useful insights in different aspects. The paper finds that (1) the variance term of ERM agrees with the minimax rate of estimation in both fixed and random design, (2) ERM is stable, (3) the landscape of near-solution for non-Donsker class is irregular, (4) the relation between isoperimetry and variance of ERM.\n", "weaknesses": "The main weakness is organization. Too many results wrapped in nine pages makes reader feel the paper is very crowded. \n\nSome definitions and results could be explained more detailedly. For example, what does it mean by the minimax rate of ERM and variance, respectively? What is local optimality? Donsker and non-donsker classes. Any specific application of current results? Technical differences between fixed and random design could be explained on a very high level.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " Thank you for your report. We agree that the intuitive explanations of our assumptions and results are a bit briefer than we would like, which was forced upon us by the page limit for the submission.  In the revised version, we will move Theorem 2 to the appendix, along with the additional page in the revised version, to provide fuller explanations to improve the accessibility of this manuscript.\n\n- Applications: our results are applicable to the ERM under extremely mild assumptions on the function class, as well as to other estimators satisfying Lipschitz conditions, such as regularized least-squares. A wide variety of problems intensively studied in non-parametric statistics, from estimation of a bounded $L$-Lipschitz or convex function, to kernel regression, satisfy these assumptions.\n- \"I found that this paper is more suitable for conference like COLT....'' - At first glance, this paper may look very theoretical. However, our results reveal that with regard to the large learning models commonly used in practice, if the ERM performs poorly then it does so because it is biased. In contrast (according to our knowledge) to the setting of models with few parameters, efficient debiasing methods for ERM on these large models do not exists (see Item 1 in the general rebuttal). We believe that the main message of our work -- efficient debiasing methods are all you need to improve the statistical performance of ERM over large models -- is insightful for the entire learning community. We moved this takeaway from the end of the paper to the introduction."}, {"review_id": "5rWQDQhMAW", "reviewer": "Reviewer_DCZr", "summary": "This paper studies the suboptimality of Empirical Risk minimization (ERM) of the squared loss, or equivalently, Least Squares (LS), for convex function classes, in both fixed and random design settings. In the context of non-parametric statistics, necessary and sufficient conditions for the optimality of LS are not known (though sufficient conditions were given by Birge and Massart, '93).\nRoughly speaking, the main message of this paper is showing in both settings that the suboptimality is due to the bias term, where the variance term enjoys minimax rates, under some reasonable assumptions.\n\n", "questions": "Typos:\nline 69: should be $f*\\in F$.\n\nline 16: should be \"in detail\".", "limitations": "I don't see any.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies a classic and fundamental question in statistics, understanding the suboptimality of Least Squares.\nThis paper makes nice progress in this direction. Besides the main result (mentioned in the summary), there are several other contributions, such as the (weak) admissibility property of the ERM in the random design setting; sometimes ERM can be optimal.\nMoreover, one of the results shows that ERM is stable; all approximate minimizers of the squared loss are close to each other in the functions space, and on the other end, the converse doesn't hold, sometimes the ERM is an optimal estimate and there exist close functions to it with high empirical error.\n\nAlso, the proof techniques (the isoperimetry approach for example) look interesting and elegant.  ", "weaknesses": "I don't see any.\nThere is a chance that I didn't understand some details, this is not my main research field and some proof techniques were new to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind report and your typo fixes."}, {"review_id": "YytNZUcWiy", "reviewer": "Reviewer_ZyPC", "summary": "This paper explores the minimax optimality of ERM in terms of the bias and variance of the ERM method.\nThey find in some settings that the variance is always at the minimax rate, implying that suboptimality can only occur due to bias. This paper also explores stability of ERM, finding that almost-minimizers are close to the ERM w.r.t the population distribution, but not necessarily the empirical distribution.", "questions": "* Given that assumption 8 is necessary to get from a $\\epsilon_V^2$ to an $\\epsilon_\\star^2$ bound, how restrictive is this assumption?", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Cool results and proofs in the fixed design setting\n* The random design setting results are very interesting as well, albeit harder to digest all the quantities.", "weaknesses": "* The independence relations should be clarified in the preliminaries. I assume that $\\mathbf{\\xi}$ is independent from $\\mathbf{X}$ in the random design case, but I don't think that's mentioned.\n\n\n\nMinor Typos:\n* In the proof of Theorem 2, $\\mathcal{G}$ and $\\mathcal{G}_\\star$ seem to be used interchangeably.\n* The statement of Lemma 2 in the proof of Theorem 2 seems to have a typo? I think it should be $f$ instead of $f^\\star$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind report and your typo fixes. We have clarified that the noise vector is drawn independently of the data points.\n\nRegarding Assumption 8, is motivated by  high-dimensional models, especially in the ``benign overfitting'' literature where we they assume that ERM interpolates the noisy observations. However, there are function classes which do not satisfy it. As mentioned below its statement, the assumption cannot hold if $\\mathcal F$ is taken to be a compact class of functions on some compact domain $\\mathcal X \\subset \\mathbb R^d$. For instance, if $\\mathcal F$ is the class of $1$-Lipschitz functions, $d$ must increase at least logarithmically in $n$. "}, {"review_id": "1EA5nVBTwR", "reviewer": "Reviewer_hXZP", "summary": "\nThis paper proves that variance for ERM enjoys a a minimax rate. The findings indicate that in scenarios where ERM is not optimal, the source of suboptimality lies within the bias component. Furthermore, these insights are extended to encompass an admissibility-type theorem for both fixed and random design, as well as a stability result for ERM.\nThe paper's contributions can be summarized as follows:\n1)Demonstrating the optimality of the variance term in both fixed and random design situations.\n2)The obtained results automatically yield a stability result for ERM.\n3)Presenting a simpler proof for the admissibility theorem in the fixed and random design setting.\n4)Highlighting a counterintuitive outcome concerning the ERM estimator $\\widehat{f}_n$: when $f'$ is close to $\\widehat{f}_n$, it can lead to a large squared error.\n\n", "questions": "Given dense results here, it would help reader to better understand the paper if the theorems could be summarized in a table.\n", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper studies an important problem, provides convincing conclusion. The problem is not only intellectually interesting, it also advances our understanding of ERM, which is arguably the most important estimator for modern machine learning.\n", "weaknesses": "Typo: above Equation 1 $f^* \\in f^*$.\nRemark should be referred to in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind report and for pointing out that typo. In the revised version, we will follow your suggestion and embed a tabular summary of the results. We will move many of the remarks to the appendix."}]

Author rebuttal:
We thank all reviewers for their thoughtful comments. We provide the following general remarks and comments for all reviewers and to the area chair:
    
1. The main contribution/message of the paper:  Empirical Risk Minimization (ERM) with squared loss, or any "Lipschitz" loss in the observations, enjoys a minimax optimal variance error term. Therefore, if the ERM is minimax suboptimal, this is due to its bias. Beyond mere intellectual curiosity, our results demonstrate the salience of finding computationally efficient methods to debias ERM (see the remark below). This finding aligns with a few recent works that demonstrate that ERM (or MLE) suffers from high bias in certain classical models in their high dimensional settings, such as logistic regression or $l_1$ regression. We have proven that the potential high bias of ERM is a general phenomenon over rich function classes or in "high dimensions."

    This takeaway appeared at the end of the manuscript (page 9); in the revised version, we improved the phrasing and placed it more prominently in the introduction section.

    Remark: In the classical regime (i.e., classes with a low number of parameters), one may reduce the bias by using bootstrap methods (see, e.g., B. Efron, "Bootstrap methods: another look at the jackknife," Ann. Statist. 7(1): 1-26). Unfortunately, according to our knowledge, in the non-parametric case or with models with a large number of parameters (such as neural networks), such methods do not work.

2. Clarity and organization of the manuscript: We have enhanced the organization of the manuscript by adding more intuitive explanations for the quantities that appear in the random design, and moved some of the more technical results to the appendix. This change is aimed at improving the accessibility of the paper. Additionally, in line with the reviewers' suggestions, we have incorporated a concise summary of all our results, potentially presented in a table format, to provide readers with a quick overview.

3. Generality of our results: Although we presented our results specifically for Empirical Risk Minimization (ERM) with squared loss, otherwise known as the LS estimator, our findings are more broadly applicable. As indicated in our remarks, many of our results hold for estimators that exhibit certain stability properties, such as Lipschitzness in noise or data. This includes many variants of convex regularizers, such as ridge regression.

Meta-review: This paper considers ERM with squared loss, which can be decomposed into a bias term and a variance term, and shows that the variance term necessarily enjoys the minimax rate, therefore any suboptimality must be due to the bias term. The authors then discuss its implications on the admissibility and stability of the ERM estimator with squared loss.

The contributions are solid, and all the reviewers agree that it should be accepted. Maybe a minor concern is that the paper mainly talks about ERM with squared loss, but "squared loss" is not mentioned in the title, which could be a little misleading.
Decision: Accept (spotlight)