A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models
Authors: Lijia Zhou
Frederic Koehler
Pragya Sur
Danica J. Sutherland
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)

Abstract: We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss $\ell$ can control the test error under all Moreau envelopes of the loss $\ell$ . We use our finite-sample bound to directly recover the “optimistic rate” of Zhou et al. (2021) for linear regression with the square loss, which is known to be tight for minimal $\ell_2$-norm interpolation, but we also handle more general settings where the label is generated by a potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covariance settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand’s well-known contraction lemma by a factor of two, and we prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing a non-asymptotic Moreau envelope theory for generalization that applies outside of proportional scaling regimes, handles model misspecification, and complements existing asymptotic Moreau envelope theories for M-estimation.

A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models
Lijia Zhou" University of Chicago 21j jijuicicaaoo... edu
Frederic Koehler" Stanford University
Pragya Sur Harvard University pragyaOfas harvard.
fkoehler@stanf edu
Danica J. Sutherland University of British Columbia & Amii dsuthScs. wutessubc.cc.
Nathan Srebro
Toyota Technological Institute Chicago nati@ttic. edu
Collaboration the Theoretical Foundations of Deep Learning (deepfoundations. ai)
Abstract
We prove new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss l can control the test error under all Moreau envelopes of the loss É. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) for linear regression with the square loss, which known to be tight for minimal Ez norm interpolation, but we also handle more general settings where the label generated by potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max- max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covarianee settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand's well-known contraction lemma by a factor two, and prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing non-an con-asympootic Moreau envelope theory for generalization that applies outside of proportional scaling regimes, handles model misspecification, and complements existing asymptotic Moreau envelope theories for M-estimation.
Introduction
Modern machine learning models often contain parameters than the number of training ples. Despite the capacity to overfit, training these models without explicit regularization has been empirically shown to achieve good generalization performance (Neyshabur' al. 2015; C. Zhang et al. 2017; Belkin et al. 2019). On the theoretical side, the study minimal-norm interpolation has revealed faseinating phenomena that challenge traditional understandings of machine learning.
now have a better understanding how properties of the data distribution and algorithmic bias can affect generalization in high-dimensional linear regression. For example, data with a spiked covariance structure can ensure that the test error of ridge regression will be approximately constant the regularization strength is small enough for the model to fit the signal (Zhou et al. 2021; Tsigler and Bartlett 2020), contradicting the classical U-shaped curve expected from arguments about the bias-variance tradeoff. Surprisingly, norm interpolator can be shown to converge much slower to the Bayes risk than the minimal-l2
when the signal is sparse, the risk of the minimal-e,
These authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

norm interpolator in the junk feature setting (Chatterji and Long 2021; Koehler et al. 2021). In contrast, the minimal-f, norm interpolator fails to achieve consistency in the isotropic setting, while the minimal-l, norm interpolator is consistent with sparsity but suffers from an exponentially slow rate the number of parameters d (G. Wang et al. 2021; Muthukumar et al. 2020). However, we can still achieve the minimax rate with minimal-e, norm interpolators with extremely close to 1 (Donhauser et al. 2022).
In fact, many of the intriguing phenomena from the work above may be understood using the norm of predictor; localized notions of uniform convergence have emerged as essential tools for doing so. Compared to other techniques, uniform convergence analyses can have the benefit of requiring neither particular proportional scaling regimes nor closed-form expressions for the learned model, since only an approximate estimate of its complexity is needed. Despite uniform convergence's s potential for wider applicability, though, work in this area has mostly focused on linear regression settings with strong assumptions: that the conditional expectation of the label is linear with respect to the features, and that the residual has constant variance. contrast, classical agnostic learning guarantees established by uniform convergence usually need only much weaker assumptions on the data distribution, and apply to a broader range of losses and function classes. For example, Srebro et al. (2010) show that bounds with an "optimistic rate" hold generally for any smooth, nonnegative loss, though the hidden logarithmic factor in their result is too loose for explaining noisy interpolation; this was recently addressed by Zhou al. (2021) in the special case of well-specified linear regression.
In this work, we take a step further towards agnostic interpolation learning and consider a high- dimensional generalized linear model (GLM) setting where the label is generated by a potentially misspecified model. We show a new generalization bound that allows us to use the Moreau envelopes of any continuous loss function as an intermediate tool. By optimizing over the smoothing param- eter to balance the approximation and generalization errors, our general Moreau envelope theory yields sharp non-asymptotic generalization bounds in a wide variety of settings. Applying to linear regression with the square loss, we recover the optimistic rate of Zhou et al. (2021) and show that it can more generally be extended to handle model misspecification, such as nonlinear trends and heteroskedasticity. The generality of our result comes from the fact that taking the Moreau envelope of the square loss only scales by constant; this property alone suffices to obtain generalization guarantee in terms of the original square loss. The squared hinge loss enjoys the same property, and hence completely analogous argument shows optimistic rate in that setting. Combined with an analysis of the margin, we show a novel consistency result for max- -margin classifiers.
More generally, we apply the Moreau envelope theory to obtain a generic bound for any Lipschitz loss and smooth, nonnegative loss with sharp constants. Looking specifically at the test error of an Empirical Risk Minimizer (ERM), we show our generalization bound with localized Gaussian width will be asymptotically sharp even when overfitting is not necessarily benign, yielding a version the asymptotic Moreau envelope framework for analyzing M-estimators (El Karoui et al. 2013; Bean et al. 2013; Donoho and Montanari 2016; Thrampoulidis et al. 2018; Sur and Candès 2019) but for the problem of generalization. Numerical simulations on variety of feature distributions and label generating processes confirm the wide applicability of our theory.
2 Related Work
The Moreau envelope has been useful in characterizing asymptotic properties of M-estimators in linear models (Bean et al. 2013; El Karoui et al. 2013; Donoho and Montanari 2016; El Karoui 2018: Thrampoulidis al. 2018) and logistic regression (Sur and Candès 2019; Sur et al. 2019; Candès and Sur 2020; Salehi et al. 2019; Zhao et al. 2022). This theory focuses on estimation and inference under proportional asymptoties. rather than generalization, and does not provide any non-asymptotic results. Loureiro et al. 2021 studied proportional asymptotics in a student-teache model similar to the one we consider, and gave saitle bounds on the speed of convergence to the limit. Like other works using the CGMT framework, they give formulas directly in terms of the regularization parameter used in M-estimation, and they also give results to characterize the distribution of the output of the estimator. Our work does not study the properties of the M-estimator in this level of detail. Instead, our approach is fundamentally based on establishing a nonasymptotic generalization bound. This enables our results to apply beyond proportional scaling (which is crucial to analyze benign overfitting), and yield guarantees for predictors besides the exact optima of convex M- M-estimation objectives. Another difference is that the class of generalized linear models we consider

---

is somewhat broader: we allow multi-index models for the teacher (which may also be possible with their approach) and our loss function does not need be convex.
For linear regression, Bartlett et al. (2020) identify nearly-matching necessary and sufficient conditions for the consistency of minimal-f2 norm interpolation; their subsequent work (Tsigler and Bartlett 2020) shows generalization bounds for overparametrized ridge regression. Following their work, Negrea et al. (2020) and Zhou al. (2020) explore the role of uniform convergence, including showing that uniformly bounding the difference between training error and test error fails to explain interpolation learning. Zhou et al. (2020) argue, however, that uniform convergence of interpolators is sufficient to establish consistency in a toy example. Koehler et al. (2021) extend their result to arbitrary data covariance and norm, recovering the benign overfitting conditions of Bartlett et al. (2020) as well as proving novel consistency results for the minimal-f, norm interpolator. Based on this uniform convergence framework, G. Wang et al. (2021) establish tight bounds for the minimal-(, norm interpolator under sparse signal with isotropic data. Earlier work (Ju et al. 2020; Chinot et al. 2020; Li and Wei 2021) also studied the minimal-(1 norm interpolator, without showing consistency. Though the minimal-é1 norm interpolator suffers from exponentially slow rate, Donhauser et al. (2022) show the minimal-e, norm interpolator can achieve faster rates with p close to 1. Zhou et al. (2021) show a risk-dependent ("localized") bound that extends the uniform convergence of interpolators guarantee to predictors with arbitrary training loss, and used it to establish generalization for regularized estimators such Ridge and LASSO. Our Moreau envelope theory builds on the techniques developed in this line of work to apply uniform convergence in the interpolation regime.
In terms of requirements on the data distribution, Bartlett et al. (2020) and Tsigler and Bartlett (2020) only require the feature vector to be sub-Gaussian, but assume a well-specified linear model for the conditional distribution of the label. The uniform convergence-base based works also assume a well-specified linear model, but the assumptions are more restrictive in the sense that the marginal distribution of the feature needs to be exactly Gaussian because their proof techniques rely on the Gaussian Minimax Theorem (GMT). Our Moreau envelope theory's application to linear regression significantly relaxes the assumption on the label generating process, though it is still constrained by the Gaussian data assumption. Shamir (2022) also studies model misspecification in linear regression, but allows non- Non-Gaussian features, and shows that benign overfitting does not necessarily occur in the most general setting, even with a spikkedcovariiae
structure (see his Example 1).
For linear classification, Muthukumar et al. (2021) analyze f2 max- margin classifier by connecting to minimal- interpolation in regression. Similarly, our analysis in the classification case depends on the fact the squared hinge loss goes through the same transformation as the square loss under smoothing by Moreau envelope. Donhauser et al. (2022) prove generalization bounds for 6p max- margin classifiers in the isotropic setting and do not consider the spiked spiked-covariance case. Deng et al. (2021), Montanari et al. (2019), and Liang and Sur (2020) derive exact expressions for the asymptotic prediction risk of the Eg and lp (with p E [1,2)) max-margin classifiers. Though their proof techniques also rely on the GMT, our approaches are drastically different. We use GMT in order asymptotic bound, whereas
to show uniform convergence for class of predictors and establish their results are asymptotic and assume proportional scaling limit. This is a key distinction, because overfitting usually cannot be benign with proportional scaling (e.g. Donhauser al. 2022, Proposition 1). Similar lower bounds have also been shown in the context of linear regression (Muthukumar et al. 2020; G. Wang et al. 2021: Zhou et al. 2020).
Some concurrent works have obtained consistency results for max-margin classification in the spiked covariance setting. In particular, the May 2022 version of the work by Shamir (2022) also studies convergence to the minimum of the squared hinge loss, and obtains consistency under conditions similar to the benign covariance condition of Bartlett et al. (2020). During preparation of this manuscript we learned of concurrent work by Montanari et al., not yet publicly available, which also studies consistency results for classification. Comparing our Corollary 3 Shamir (2022), their result applies to some non-Gaussian settings, but in the Gaussian setting their result is not as general as ours. (Combining Assumptions 1 and 2 of Theorem 7 there, they require the norm of the data to be bounded, whereas our Corollary 3 applies even if o(n) eigenvalues of Σ grow arbitrarily quickly with n.) More conceptually, our result follows from norm-based generalization bound that applies to all predictors and outside of the "benign overfitting" " conditions, generalizing the result of Koehler et al. (2021) and unlike the analysis of prior work.
3

---

Problem Formulation
GLM setting. Given a continuous loss function / R
R x IR - I and i.i.d. sample pairs (I,, Vi)
from some data distribution D, we can learn a linear model (tb, b) by minimizing the empirical loss Ly with the goal of achieving small population loss Ly:
Ly b) = f((w, vz) + vi), Ly(w,b)=
E (2,0)
f((w, b.
(1)
Multi-index model. We assume that the data distribution D over (a, y) is such that
1. z ~ (0, Σ) is centered Gaussian with unknown covariance matrix E.
2. There are unknown weight vectors wi, .... "x E Bed such that the E are orthonormal, function IR*+1 -> R, and random variable g ~ De independent of x (not necessarily Gaussian) such that
7 ,)) y = g(n. ....,.... E). (wf,
We assume that the distribution of is centered without loss of generality since presence of mean term simply corresponds to changing the bias term b: (w, x) + b (w, x 14) + (b (w, 14) We can also assume that w" .... E1/2us " are orthonormal without loss of generality since we have not imposed any assumption on the link function g. The multi-index model includes well- specified linear regression, by setting A = and g(n, <) = 7 &. It also allows nonlinear trends and heteroskedasticity (such the model in Figure by changing the definition of g. Since g need be continuous, the label can be binary, as in linear classification.
Moreau Envelope Generalization Theory
Our theory vitally depends the Moreau envelope, defined as follows.
Definition The Moreau envelope of f x R + R with parameter E R+ is defined as the function fx R R - IR given by
fA v) inf fu, v) + A(u - 2)
The Moreau envelope can be viewed as smooth approximation to the original function f: in our parameterization, smaller À corresponds to more smoothing. The map that outputs the minimizer known as the proximal operator, plays an important role in convex analysis (Parikh and Boyd 2014; Bauschke, Combettes, et al. 2011).
Our general theory, stated in Theorem below, essentially upper bounds the generalization gap between the population Moreau envelope L,x and the original training loss Ly by the sum of two parts: a parametric component that can be controlled by the dimension & of the "meaningful" part of Jr and non- non-parametric component that can be controlled by dimension-free complexity measure such as the Euclidean norm of the predictor. Typically, the first term is negligible since & is small, and the complexity of fitting all the noise is absorbed into the second term. More precisely, we introduce the following definitions to formalize separating out a low dimensional component:
Definition 2. Under the model assumptions (2), define (possibly oblique) projection matrix Q onto the space orthogonal to wi, wt and mapping o from Rd to IR k-1 by
Q Q= ls Σ ot (w
((w)= ((w, Ewi) ..., (w, Ewit), ||
(4)
We let Σ = QTEQ denote the covariance matrix of QT.. We also define low-dimensional surrogate distribution D over R++1 x IR by
N, TR)), DE. and ÿ= 5 ... Tr.
This surrogate distribution compresses the "meaningful part" of x while maintaining the test loss, as shown by our main result Theorem (proved in Appendix D). Note that as non-asymptotic statement, the functions 6x,5 and C3 only need hold for a specific choice of and D.

---

Theorem 1. Suppose X E R satisfies that for any ô E (0, 1), there exists continuous function 6x,5 : RR++1 + R such that with probability at least 6/44 over independent draws (3,, ū.) from the surrogate distribution D defined in (5), we have uniformly over all (w, b) E RR+2 that
fu T.) + +.. 0.) 2
E (B
[al(i 8) + b, 1)) cx,5(10, b).
(6)
T2
Further, assume that for any E (0, 1), there exists a continuous function C3 : IR - [0, oa] such that with probability at least 8/4 over x N (0, E), uniformly over all w E Rdd (Qw, x)) S Cs(w).
Then it holds with probability at least 1 - 8 that uniformly over all (w,, b) E IRd+1 we have 1 (w. b) S Ly(w,b) b) + (x,((o(w). XCs(w)2
(8)
n If we additionally assume that (6) holds uniformly for all E IR,, then (8) does as well.
As we will see, we can generally bound the difference hetween I, and T. when the loss is assumed to be Lipschitz. If f is not Lipschitz but smooth (i.e. f is Lipschitz, as for the squared loss), we can always write it as the Moreau envelope of another function f. In the special case of square loss or squared hinge loss, the Moreau envelope ʃx is proportional to f. meaning that (8) becomes a generalization guarantee in terms of Ly. Optimizing over will establish optimal bounds that recover the result of Koehler et al. (2021) and Zhou et al. (2021), and lead to other novel results.
Remark 1. The complexity functional Cs(w) should be thought of as localized, gighpprbabiility version of Rademacher complexity. This is because the Gaussian width of a convex set K, Esupwex(w, (w, is the same as the Rademacher complexity of the class of linear functions {or + (mc, x) w E KC} (Zhou et al. 2021, Proposition 1). A somewhat similar complexity functional appears in Panchenko (2003). Also, note (6) requires only one-sided concenfration see Remark 3.
4.1 VC Theory for Low-dimensional Concentration
To apply our generalization result (Theorem 1), we should check the low-dimensional concentration assumption (6). The quantitative bounds in the low-dimensional concentration (i.e. the precise form of error term c2,5) will inevitably depend on the exact setting we consider (see e.g. Vapnik 1982; Koltchinskii and Mendelson 2015; Lugosi and Mendelson 2019 for discussion).
First, we recall the following result from VC theory.
Theorem (Special case of Assertion of Vapnik (1982), Chapter 7.8; see also Theorem 7.6). Let K. C Rd and B C R. Suppose that distribution D over (I, E Rd x IR satisfies that for some T >> 0, it holds uniformly over all (w, b) E K. x B that
(E f(w, x) + 6, 1) 1/4
ST.
(9)
E f( (ww 2) + b.y)
Also suppose the class of functions {(x, v) + ([f x) + y) > f} ::::weee w =e,:eKK R} has VC- "C-dimension at most h. Then for any n > h, with probability at least 1 - 5 over the choice of
((11, (1),,)),.... ... (Fn, yn ))- ~ DD, it holds uniformly over all w E K, E B that
1 n
f(1w, 24) + b. 2 1 11-8ry hhlog(2n/h)) 1) + l2g(1)/))
E f(((w
+ b. v)-
n
The assumption (9) is standard (indeed, this is the setting primarily focused on in Vapnik 1982) and is sometimes referred to as hypercontractivitty result holds with 4 replaced by + e. In many settings of interest, this can be directly checked using the fact that is Gaussian (for instance, see Theorem 9 and Appendix E.3). Of course, our general result can be applied without this assumption, by using low-dimensional concentration under an alternative assumption: Vapnik (1982), Panchenko (2002), Panchenko (2003), and Mendelson (2017) have further discussion and alternative results; in particular, Assertion of Vapnik (1982, Chapter 7.8) gives bound based a fourth-moment assumption, and Panchenko (2003, Theorem 3) gives one based on a version of Rademacher complexity.
norm equivalence in the literature; variant of the
Combining Theorems and 2 yields the following.
5

---

Corollary 1. Under the model assumptions (2), suppose that C3 satisfies condition (7). Also suppose
that for some fixed X 2 O, K. C Rd and B S R. the surrogate distribution DD satisfies assumption (9) under fa uniformly over 6(K) x B, and that the class {(z, u) + 1 <(x)) + + v) > t) w E (KK),, b E B.L. E R) has VC-dimension at most h. Then with probubility at least 8, uniformly over all (ue, b) E x
h(log(2n/h) + 11 (486)) Lix (w, b) S L5(w, b) ACa(w))
1 1- 1 8TV
16
Furthermore, if assumption (9) holds uniformly for all (ʃx : A E R2o) and the class {(I, y) + (f Φ(x)) + b.y) > t (w.b) E ((K) x B, E X Rzo) has VC-dimension at most h, then the same conclusion holds uniformly over
The last conclusion (uniformity over X) follows by going through the proof of Theorem 2, since it is based on reduction to uniform control of indicators. In every situation we will consider, easy to check that the VC dimension h in the theorem statement is O(k), generally by reducing to the fact that halfspaces in R$ have VC dimension k + 1.
5
Applications
5.1 Linear Regression with Square Loss
In this section, we show how to recover optimistic rates (Zhou al. 2021) for linear regression without assuming the model is well-specified. We will consider the square loss, f(ğ y) = (Ú - -). key property of the square loss is that the Moreau envelope is proportional to itself:
A
fx inf (u y)² + A(u 1+ f(j.y).
(10)
Thus we can multiply by (1 + A)/A in our generalization bound and solve for the optimal choice of X. Corollary 2. Suppose I is the square loss and the surrogate distribution D satisfies assumption (9) uniformly over (w, b) E R then with probability at least 1 1-6, 6, uniformly over all w, b we have
(1 1 18- /kllg(220/ + 1)- + log(48/6) Ly( b) (Vgg(vob) CCa()))))
As mentioned earlier, assumption (9) usually holds under mild conditions on y. For example, 7 can be chosen to be a constant when is bounded-degree polynomial of a Gaussian due to Gaussian hypercontractivity (O'Donnell 2014, Section 11.1). Specializing Corollary 2 interpolators (L,, 0) recovers the uniform convergence of interpolators guarantee from Koehler et al. (2021). Combined with more general norm analysis in Section 6, we establish Eg benign overfitting with misspecification. In the well-specified case, see Zhou al. (2021) for detailed examples on ordinary least squares, ridge regression, and LASSO.
5.2 Classification with Squared Hinge Loss
In this section, we show a novel optimistic rate bound for max-margin linear classification with the squared hinge loss, f(ū. v) = max(0, v0)². Its Moreau envelope is given by
if vů 5 - - yo)² if - yū > = 1+
f0 { (
fx(9. v) = inf max(0, 1 yu)² + A(u - 2)
f(D.2).
We consider the case of general binary response valued in {=1} satisfying the model assumptions in equation (2). In this case as well, I proportional to its Moreau envelope; thus, the same proof as for the squared loss shows that Corollary 2 continues to hold when square loss is replaced by squared hinge loss! In Appendix 1. we discuss certain settings (including noisy settings) where minimizing the squared hinge loss also minimizes the zero-one loss, i.c. the misclassification rate.

---

Pottingee n. 100 150
Jast Searise P 101 4 3000
Herrii (eah in 300 4= 300
NE mer
san ne
48 nec
[9] 1002 perttee
bu 1815 poraee
kn 103p DeVATeee
Istrmpte: 12 100,00 1000:1129
J.nE feature = 180, d 2000
Harmhi feature: is 100, d 2000
Smprica
Deprital fic seans
14- Ergiital mo
secosure
10
14
04
80
05
14
5.5
25
-3.3
-12
1gg regulanuzion
kg ruguia 48/08
Figure 1: Top: ridge regression with model misspecification; bottom: 22 margin classification with logistic model. Here the features Gaussian; see Appendix B for additional experiments & regularization and non-Gausseee Gansssasi features. The covariance in the first column (isotropic) is Σ = -d, in the second column (junk features) is Σ = diag(1,... ..., 1, 0.05² .... 0.05*), and in the third (harmful features) is Σ- = diag(1, 1, (I+1) : .... tt) ). For regression, the number of leading eigenvalues is h: = 3. and the label is generated according to y 1.5 21 + |21 cos T2 + T3 (O 0.5). For classification, the number of leading eigenvalues is k = 1 and Pr(y = x) = sigmoid(522 + 3).
The risk bound is calculated using the expression (VL+ + /Iw 13 )//) 2
which corresponds to the choice of C(w) from Lemma 1, and is expected to be tight in the junk features setting. In the isotropic case, we use an easy improvement of the bound where is projected to the orthogonal complement of the Bayes predictor w" (Zhou et al. 2021). splicting without projection of w. Each point on the curve is the average from repeated experiments, and shaded areas correspond to 95% bootstrap confidence intervals.
the other cases, we use covariance
5.3 Further applications
In this section, we discuss further interesting examples where our general theory applies. As before, we can obtain a generalization bound by appealing to the general Corollary 1: we omit stating the formal corollary for each case, and simply show the Moreau envelope and its consequences.
L1 loss (LAD) and Hinge. For the L1 loss f(i.v) j/j - y/ its Moreau envelope is given by
fx v) = inf a - yl + A(u - 0) = [> - y)
if 10 リーーンー S
v
1
21
100 yl 4X
1 if 1
1
2X
which is 2λ times the Huber loss with parameter 5= 2x. Therefore, the population Huber loss is controlled by the empirical 7, loss. Clearly, interpolators have zero training error under both Ia and Lg training losses. We already see that Corollary 2 implies (1 (1-)(1) [[( +b))² y)² Now, considering Corollary 1 with ff the L1 loss and using the above Moreau envelope calculation, we can check that when X + 0 we reproduce the exact same bound, since the Huber loss becomes the squared loss in the limit. Further insight into this phenomenon appears later in Theorem 4: the Huber loss naturally shows up when computing the training error of the LAD estimator. An entirely analogous situation occurs when f is the hinge loss f(. y) == max(0. ÿy): its Moreau envelope fx will be a rescaling of the Huber hinge loss (c.f. T. Zhang 2004a).
< Cs(w)) /n.
Lipschitz loss: improved contraction.
If f is M-Lipschitz in ÿ. Proposition 3.4 of Planiden and M²
X. Wang (2019) gives that 0 < fx < 4x Thus, assuming k/n o(1), Corollary 1 implics
7

---

- (T)(())())(11)) 4x² > [.5(10) + ACs(w)
optimizing over À yields
n
(1 (1) S (y(w)) + My Cs(w)²
(11)
For w E K. a high-probability upper bound on the Rademacher complexity of the function class + (w, 22) upper bounds the second term (Remark 1). In comparison, the standard symmetrization and contraction argument (Bartlett and Mendelson 2002) loses factor of two. Note that if f is the L1 loss, this applies with M = 1, and it can further be shown that the constant factor cannot be improved further (see Appendix E.4), but this bound is also not as tight as the version with Huber test loss.
Uniform Convergence of Interpolators for Smooth Losses Suppose that f is an H-smooth (in the sense that @ / S H) and convex function of ÿ. In addition, assume that the minimum of f y) 0g
is zero for any fixed y. Since is H Hssoooth, there exists function of such that f fu/2 (Bauschke, Combettes, et al. 2011, Corollary 18.18). If w satisfies (y( = O, then L j(w) = 0 as well. Finally, by Corollary 2, if k/n o(1) we have uniformly over all such that ( that
H Cs(w)²
-1-o (1-((1))
(12)
2
which generalizes the main result of Koehler et al. (2021) to arbitrary smooth losses.
6
1g Benign Overfitting
We can obtain conditions for consistency, like those of Bartlett et al. (2020), by simply combining norm-based uniform generalization bound with an upper bound on the norm of interpolators. Kochler al. (2021) used the same strategy, but our more powerful and general tools give better results:
1. For squared loss regression, show that the assumption that the ground truth is generated by a linear model (i.e. well-specified), made in previous work, is not required. The same result holds under the much more general model assumption of Section 3.
2. We show an analogous result in the classification setting, replacing the squared loss with the squared hinge loss. In fact, the argument is exactly the same in the two cases: all we need to use is that fx . f and that f is the square of Lipschitz function.
First, the following lemma (essentially just the standard Rademacher complexity bound for the & ball) combines with Corollary 2 and its squared hinge loss version to give generalization bounds. These bounds are demonstrated in Figure 1 and Appendix B.
Lemma In the setting of Theorem letting Σ EQ the following Cs(w) will satisfy (7):
(sww) ||||| (Tr(E') + 2//12 ol log(8/8)
Next, provide sufficient condition for zero-training error predictor exist in & ball. In the case of classification, this allows us to lower-boune the margin of the max-marga halfspace.
Definition 3 (Bartlett et al. 2020). The effective ranks of a covariance matrix E are
Tr(2) |
Tr(2)²
(E)
and R(E) Tr(E2)
Since f < is nonnegative, f nonnegative as well. When f(i. v) there must ue such that f(ue, v) x 5) < E; this is only possible if we have Uh + f. implying since is smooth that f(j. y) 0. If (w) 0, we must have for every that ((x, y:) = O: thus f(g. v)) = 0 and Ly(w) = 0.
'Theorem 3 of concurrent work by Shamir (2022) also proves benign overfitting for some misspecified models, but requires the very strong assumption n² [ llop + 0 that fails to hold in several examples from Bartlett et al. (2020).
8

---

Lemma 2. Suppose that f(. v) is either squared loss or squared hinge loss. Let (w² ba) Rd+1 be an arbitrary vector satisfying Qu = 0 and with probability at least 8/4,
L b²) S Lg(w², .t) + p1 (,,,
(13)
for some pr p1 > O. Then for any P2 E (0, 1), provided Σ+ = Q² EQ satisfies
R( = n loog" (4/8)
(14)
P2
we have that with probability at least 1 1-6 that min iSB Lz(w,b) = for B > 0 defined by B² = | - P2) THEI (I.y ( + P1).
We note that for any vector w², we have L5((T Qil-- b4) Ly(w², b²) by Jensen's inequality over Q" x. so the assumption Quf in the lemma always satisfied for the minimizer of Ly(w,, b)- Combining the norm bound Lemma and the generalization bound Lemma yields the following.
Theorem 3. Let (vo, b) = arg min wERd bER: (w b)= || be the minimum-lz norm predictor with zero training error. In the setting of Lemma 2, we have
(I,(wt, + pI(w", b²) + | Tr(E+)
[y b) co()(()),)) S (1 + ps)
inf wt ERd EB
n2
where P3 > 0 defined by 1 1+ P3 (1 p2) [ 1
l2g(2/8) r(=
and we recall pi (w b²) from (13).
We now show that this formally implies convergence to the optimal test loss (i.e. consistency) under the &z benign overfitting conditions (15) from Bartlett al. (2020) and Tsigler and Bartlett (2020):
Corollary 3. Suppose that Dr is a sequence of data distributions following our model assumptions (2), with kn such that y = g(m,, Me,, E), and projection operator Qn defined as in (4). Suppose is either the squared loss or the squared hinge loss, and define (wh bb] arg min b L [ww, b) where L.n(w. b) is the population loss over distribution Dn with loss f. Suppose that the hypercontracciivtyy assumption (9) holds with some fixed т > 0 for all Dn.. Define En, = ED, ED,[,x"") and Σ = En Suppose that as n 0o, have
71
Tr(E
kn
O.
0,
(15)
R R
n
n
Then we have the following convergence probability, as n - oc:
L (tn ba)
I F. (wh, bh) + 1,
(16)
where (w,, by.) arg min weRd beR:Ly ()= /lll the minimum- interpolator, and L. is the training error based on n i..dd. samples from the distribution Dn.-
Note when applying Corollary 3, we have the flexibility to increase kn and shrink Ei by choosing additional weights wi and letting the link function g ignore the extra components.
Remark 2 (Flatness of the test loss along regularization path). Our method can easily show slightly stronger statement: let (ui,, b..) E arg min (we BER y (wi, 66) such that, if there are multiple minima, we pick the one with smallest ||w]]. As long B, > |/=ff] |l. we still have (16), and this is established uniformly over all sequences B,, satisfying the constraint. Therefore, under the benign overfitting conditions get consistency as long we do not over-regularize the predictor. See Figure for an experimental demonstration of the flatness.
Training Error and Local Gaussian Width
Theorem shows how to upper-bound the test error of a predictor (under the Moreau envelope loss) by its training error and an upper bound on the class complexity. The following theorem is the dual result, which upper-bounds the training error of the constrained ERM (Empirical Risk Minimizer) by the Moreau envelope and a complexity term. particular, this general result used derive the norm bound for interpolators in Lemma 2 above.

---

Theorem 4. Let K, B be bounded convex sets, and let f y) be convex in ÿ. Suppose that T is such that with probability at least
ö, for (3. D) sampled i.idd. from 'D we have
min #E
max A20
A(v0, .) + bo: Vi) ) woE (oEE--(a)nn
max
(z, Qwo)? ST.
(17)
Then with probability at least 1 26, minwex,bes [. b) S.
Note that the assumption (17) implicitly suggests low-dimensional concentration assumption: we expect +.4 Zi=1 (110, i) + bo. yi) to be approximately the test loss of (v², bo) under the surrogate distribution D. As discuss more in Appendix F, combining this training error bound with the correct choice of (u(w) in Theorem 1, which is essentially Co (w) = E m (w))) (w Qwo)? yields a matching lower bound (8) on the Moreau envelope test loss and bound is asymptotically sharp. This establishes a non-asymptotic analogue of the existing asymptotic Moreau envelope theory (see Section 2), and recovers the special case of well-specified linear models (Zhou et al. 2021).
generalization
Discussion
In this work, we significantly extend the localized uniform convergence technique developed in the study of noisy interpolation to any loss function and label generating process under mild conditions. Though the application of Moreau envelope to study GLMs is not new in the statistical literature, our general theory establishes novel non-asymptotic generalization bounds in a wide variety of overparameterized settings. We believe the generality of our framework may allow further applications in other areas of statistics, such as robust statistics and high- nigh-dimensiona inference.
As mentioned in Section 2, the applicability of our theory is still considerably limited by the Gaussian data assumption, required by our use of the Gaussian minimax theorem. does appear experimentally that it may hold much more broadly (Appendix B); proving that this is the case could allow to study kernel methods and bring us closer to a theoretical understanding of deep neural networks. Some work has been done in related settings to extend Caussian-based results to broader distributions via universality arguments (e.g. Hu and Lu 2022; Liang and Sur 2020; Montanari and Saeed 2022), but it is not yet clear how apply those techniques to our general framework. The GMT formulation also does not allow for multi-class classification or two-layer networks, because of their vector-valued outputs. Overcoming these two challenges seems to be crucial avenues for future work.
Acknowledgments and Disclosure of Funding
F.K. was supported in part by NSF award CCF-1704417,, NSF award 1S0-1997744, and N. Anari's Sloan Research Fellowship. P.S. was supported in part by NSF award DMS- 22OS-2113442 13426. D.J.S. was supported in part by the Canada CIFAR AI Chairs program. Part of this work was initiated when F.K., P.S., and N.S. were visiting the Simons Institute for the Theory of Computing for their program on Computational Complexity Statistical Inference. This work was done as part of the Collaboration on the Theoretical Foundations of Deep Learning
ai).
References
Bartlett, Peter I.., Michael I Jordan, and Jon D McAuliffe (2006). "Convexity, classification, and risk
bounds." " Journal of the American Statistical Association 101 443,473, pp. 138-156.
Bartltt, Peter L., Philip M. Long, Gábor Lugosi, and Alexander Tsigler (2020). "Benign overfitting in linear regression." Proceedings of the National Academy of Sciences 117.48, pp. 30063-30070.
arXiv: 1906. 11300.
Bartlett, Peter L. and Shahar Mendelson (2002). "Rademacher and Gaussian complexities: Risk bounds and structural results." Journal of Machine Learning Research 3.Nov, pp. 463 463-482. Bauschke, Heinz H, Patrick L Combettes, et al. (2011). Convex analysis and monotone operator theory in Hilbert spaces. Vol. 408. Springer.
Bean, Derek, Peter Bickel, Noureddine El Karoui, and Bin Yu (2013). "Optimal M-estimation in high-dimensional regression." " Proceedings of the National Academy of Sciences 1 110.36, pp. 14563- 14568.
10

---

Belkin, Mikhail. Daniel Hsu, Siyuan Ma, and Soumik Mandal (2019). "Reconciling modern machine learning practice and the bias-variance trade-off." Proceedings of the National Academy of Sciences 116.32, pp. 18849-15854, arXiv: 1812. 11118. Blum, Avrim, Adam Kalai, and Hal Wasserman (2003). "Noise-tolerant learning, the parity problem, and the statistical query model." Journal of the ACM (JACM) 50.4, pp. 506-519.
Blumer, Anselm, Andrzej Ehrenfeucht, David Henry Haussler, and Manfred Klaus Warmuth (1989). "Learnability and the
dimension." Journal of the ACM 36 (4), pp. 929-965. Boyd, Stephen, Stephen P Boyd, and Lieven Vandenberghe (2004). Convex optimization. Cambridge University Press.
Bubeck. Sébastien (2015). "Convex Optimization: Algorithms and Complexity." Foundations and Trends in optimizatiion 8.3-4, pp. 231-358.
Candès, Emmanuel and Pragya Sur (2020). "The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression." The Annals of Statistics 48.1, pp. 27-
42.
Chatterji, Niladri S. and Philip M. Long (2021). "Foolish Crowds Support Benign Overfitting" arXiv:
2110. 02914.
Chen, Lin, Yifei Min, Mikhail Belkin, and Amin Karbasi (2021). "Multiple Descent: Design Your Own Generalization Curve." " Advances in Neural Information Processing Systems. arXiv: 2008.
01036.
Chinot, Geoffrey, Matthias Löffler, and Sara van de Geer (2020). "On the robustness of minimum- norm interpolators." arXiv: 2012.00807.
Deng. Zeyu, Abla Kammoun, and Christos Thrampoulidis (2021). "A model of double descent for high-dimensional binary linear classification." Information and Inference: Journal of the IMA. arXiv: 1911 .08222.
Donhauser, Konstantin, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang (2022). "Fast rates for
noisy interpolation require rethinking the effects of inductive bias." arXiv: 2203. 03597. Donoho, David and Andrea Montanari (2016). "High dimensional robust m-estimation: Asymptotic variance via approximate message passing." Probubility Theory and Related Fields 166.3, pp. 935- 969.
El Karoui, Noureddine (2018). "On the impact of predictor geometry the performance high- dimensional riggaaregllarized generalized robust regression estimators." Probability Theory and Related Fields 170.1, pp. 95-175.
El Karoui, Noureddine, Derek Bean, Peter Bickel, Chinghway Lim, and Bin Yu (2013). "On robust regression with nigh-dimensional predictors." Proceedings of the National Academy of Sciences 110.36, pp. 14557-14562.
Gordon, Yehoram (1985). "Some inequalities for Gaussian processes and applications." Israel Journal of Mathematics 50.4, pp. 265-289.
Hu, Hong and Yue M. Lu (2022). "Universality Laws for High-Dimensional Learning with Random Features." IEEE Transactions on Information Theory. arXiv: 2009.07669. In press.
Ju. Peizhong, Xiaojun Lin, and Jia Liu (2020). "Overfitting Can Be Harmless for Basis Pursuit: Only to a Degree." " Advances in Neural Information Processing Systems. arXiv: 2002. 00492. Koehler, Frederic, Lijia Zhou, Danica J. Sutherland, and Nathan Srebro (2021). "Uniform Con- vergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting." Advances in Neural Information Processing Systems. arXiv: 2106. 09276.
Koltchinskii, Vladimir and Shahar Mendelson (2015). "Bounding the smallest singular value of a random matrix without concentration." International Mathmmatics Research Notices 2015.23,
pp. 12991-13008.
Lecué, Guillaume and Shahar Mendelson (2013). "Learning subgaussian classes: Upper and minimax
bounds." " arXiv: 1305. 4825.
Li, Yue and Yuting Wei (2021). "Minimum & norm interpolators: Precise asymptotics and multiple
descent." arxiv: 2110. 09502.
Liang, Tengyuan, Alexander Rakhlin, and Xiyu Zhai (2020). "On the Multiple Descent of Minimum- Norm Interpolants and Restricted Lower Isometry of Kernels." Conference Learning Theory. Liang, Tengyuan and Pragya Sur (2020). "A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-Ll-Nome Interpolated Classifiers." arXiv: 2002.01586
Loureiro, Bruno, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová (2021). "Learning curves of generic features maps for realistic datasets with teacher-student model." Advances in Neural Information Processing Systems 34, pp. 18137-18151.
11

---

Lugosi, Gábor and Shahar Mendelson (2019). "Mean estimation and regression under heavy-tailed distributions: survey." " Foundations of Computational Mathematics 19.5, pp. 1145-1190.
Mendelson, Shahar (2014). "Learning without concentration." Conference on Learning Theory.
PMLR, pp. 25-39.
Mendelson, Shahar (2017). "Extending the scope of the small-ball method." arXiv: 1709. 00843.
Montanari, Andrea, Feng Ruan, Youngtak Sohn, and Jun Yan (2019). "The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime." arXiv: 1911 01544.
Montanari, Andrea and Basil N. Saeed (2022). "Universality of empirical risk minimization." Confer- ence on Learning Theory. arXiv: 2202.08832.
Muthukumar, Vidya, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai (2021). "Classification vs regression in overparameterized regimes: Does the loss function matter?" Journal of Machine Learning Research 22, pp. 1-69. arXiv: 2005. 08054. Muthukumar, Vidya, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai (2020). "Harmless interpolation of noisy data in regression." IEEE Journal on Selected Areas in Information Theory.
arXiv: 1903.09139.
Negrea, Jeffrey, Gintare Karolina Dziugaite, and Daniel M. Roy (2020). "In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors." International Conference on Machine Learning. arXiv: 1912. 04265.
Neyshabur, Behnam. Ryota Tomioka, and Nathan Srebro (2015). "In Search of the Real Inductive Bias: On the Role of Implicit Regularization Deep Learning." International Conference on
Learning Representatiooss Workshop. arXiv: 1412.6614.
O'Donnell, Ryan (2014). Analysis of boolean functions. Cambridge University Press. Panchenko, Dmitry (2002). "Some Extensions of an Inequality of Vapnik and Chervonenkis." Elec- tronic Communications in Probability 7. pp. 55-65 arXiv: 0405342.
Panchenko. Dmitry (2003). "Symmetrizztiin approach to concentration inequalities for empirical processes." " The Annals of Probability 31.4, pp. 2068-2081.
Parikh, Neal and Stephen Boyd (2014). "Proximal algorithms." Foundations and Trends in optimiza-
tion 1.3, pp. 127-239.
Planiden, Chayne and Xianfu Wang (2019). "Proximal mappings and Moreau envelopes of single- variable convex piecewise cubic functions and multivariable gauge functions." " Nonsmooth opti- mization and its applications. Springer, pp. 89-130.
Salehi, Fariborz, Ehsan Abbasi, and Babak Hassibi (2019). "The impact of regularization on high- dimensional logistic regression." Advances in Neural Information Processing Systems 32.
Shalev-Shwartz, Shai and Shai Ben-David (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press.
Shamir, Ohad (2022). "The Implicit Bias of Benign Overfitting," arXiv: 11489.
Sion, Maurice (1958). "On general minimax theorems." Pucific Journal of mathematics 8.1, pp. 171- 176.
Srebro, Nathan, Karthik Sridharan, and Ambuj Tewari (2010). "Optimistic Rates for Learning with a Smooth Loss." arXiv: 1009.3896.
Sur, Pragya and Emmanuel J Candès (2019). "A modern
theory for high- dimensional logistic regression." Proceedings of the National Academy of Sciences 116.29,
pp. 14516-14525.
Sur, Pragya, Yuxin Chen, and Emmanuel J Candès (2019). "The likelihood ratio test in high- dimensional logistic regression is asymptotically a rescaled chi-square." Probubility theory and related fields 175.1, pp. 487-558.
Thrampoulidis, Christos, Ehsan Abbasi, and Babak Hassibi (2018). "Precise error analysis of regular- ized M -essimaators in high dimensions." IEEE Transactions on Information Theory 64.8, pp. 5592- 5628.
Thrampoulidis, Christos, Samet Oymak, and Babak Hassibi (2015). "Regularized linear regression:
A precise analysis of the estimation error." Conference on Learning Theory.
Thrampoulidis, Christos, Samet Oymak, and Mahdi Soltanolkotabi (2020). "Theoretical insights into
multiclass classification: A high-dimensional asymptotic view." Advances in Neural Information
Processing Systems 33, pp. 8907-8920.
Tsigler, Alexander and Peter L. Bartlett (2020). "Benign overfitting in ridge regression." arXiv:
2009. 14286.
Van Handel, Ramon (2014). "Probability in High Dimension." Lecture notes, Princeton University.
URL: https: / /wtbb/ebbbbbbb math. weatc..rinneton.co "rtra/aaaaaaaaaa pdf.
12

---

Vapnik, Vladimir (1982). Estimation of dependences based on empirical data. Springer Science & Business Media.
Vershynin, Roman (2018). High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge University Press.
Wang. Guillaume, Konstantin Donhauser, and Fanny Yang (2021). "Tight bounds for minimum 11-norm interpolation noisy data." " arXiv: 2111.05987.
Zhang, Chiyuan, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals (2017). "Under- standing deep learning requires rethinking generalization. International Conference on Learning Representations. arXiv: 1611. 03530.
Zhang, Tong (2004a). "Solving large scale linear prediction problems using stochastic gradient descent algorithms." Proceedings of the twenty-first international conference on Machine learning. p. 116.
Zhang, Tong (2004b). "Statistical behavior and consistency of classification methods based convex risk minimization." The Annals of Statistics 32.1, pp. 56-85.
Zhao, Qian, Pragya Sur, and Emmanuel J Candes (2022). "The asymptotic distribution of the MLE in high-dimensional logistic models: Arbitrary covariance." " Bernoulli 28.3, pp. 1835-1861. Zhou, Lijia, Frederic Koehler, Danica Sutherland, and Nathan Srebro (2021). "Optimistic Rates:
A Unifying Theory for Interpolation Learning and Regularization in Linear Regression." arXiv:
2112. 04470.
Zhou, Lijia, Danica J. Sutherland, and Nathan Srebro (2020). "On Uniform Convergence and Low-
Norm Interpolation Learning." Advances in Neural Information Processing Systems. arXiv: 2006. 05942.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is purely theoretical study of existing, commonly used algorithms.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "vGPVHpp100h", "reviewer": "Reviewer_dxeC", "summary": "This paper studies the generalization properties of high-dimensional generalized linear models (GLM). Assuming that the inputs are Gaussian and the underlying data distribution follows a multi-index model, the authors obtained upper bounds for the population Moreau envelope risk in terms of the training loss and the Rademacher complexity of the function class in a variety of overparameterized settings. Specializing their results to several applications, they show connections to existing results in the literature such as the optimistic rates for linear regression and the benign overfitting.", "questions": "Major questions/comments:\n1. The Gaussian input assumption is quite restrictive. If a well-specified model is assumed, can you relax this assumption?\n2. How easy is it to verify Eq (6)? Can you give some examples?\n3. One line 198, there is a claim \"in many settings of interest, this can be directly checked using the fact that $x$ is Gaussian\". I would like to see concrete results to support this claim. What can you say when $x$ is not Gaussian?\n4. In Cor. 3, it is required that the inputs are Gaussian and Eq. (9) holds for all $\\mathcal{D}_n$. However, Bartlett et al. (2020) do not have these assumptions when the model is well-specified. In the well-specified setting, can you verify or relax these assumptions?\n\nMinor questions/comments:\n1. The sentence \"the first term is negligible since the dimension is small\" on line 158 is confusing. Isn't the main focus here the high-dimensional setting?\n2. What are $x_i$s in Eq. (5)? Are they the coordinates of $\\tilde x$? If so, what happens to the $(k+1)$-th coordinate?\n3. Should the term $\\epsilon_{\\lambda, \\delta}$ in Eq. (6) also depend on $n$?\n4. Should the term $C_\\delta(w)$ in Eq. (7) depend on $k$, $d$, and $\\Sigma$?\n5. Why is the claim on line 245 true? Isn't $f_\\lambda \\rightarrow 0$ as $\\lambda \\rightarrow 0$?\n6. On line 260, is $\\tilde f$ convex? If not, how did you get $\\hat L_{\\tilde f}(w) = 0$?", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe main results in the paper are novel due to their generality -- they holds for GLMs with possible model misspecification. The results in the main text are clearly stated and intuitions are given to parse them. The proofs of these results I checked seem to be technically solid. Finally, the connections to existing literature are very interesting and show the generality of their results.\n\nWeaknesses:\nThe main issue I have with this paper is that some of the assumptions are not transparent and seem to be difficult to verify. This is the case in the main theorem in Sec. 4 as well as in the results derived in Secs. 5 and 6. One important question the authors did not answer is that whether these assumptions hold in a specific setting, e.g., well-specified linear regression. This, together with the Gaussian input assumption, question the applicability of their results. See the Questions section for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "slaIJFLrsHS", "reviewer": "Reviewer_S5Ha", "summary": "analysis of (one-sided) generalization error using Moreau envelopes. \n\ntheorem 1: if the empirical Moreau loss is unformly not much smaller than the expected Moreau loss whp then the expected Moreau loss is less than the empirical loss plus a complexity term, so ERM leads to small expected Moreau loss.\n\nthis is applied to develop \n1. vc bounds for the expected Moreau loss\n2. bounds linear regression with square loss and classification with sq-hinge loss (for the expected loss instead of expected Moreau loss, by exploiting properties of Moreau envelope of square/sq-hinge resp.)\n3.  discussion of l1 and hinge loss implications, and relationship to huber loss\n4. general Lipschitz losses (improves existing results by a constant factor)\n5. general smooth losses given interpolation (generalizes existing work)\n6. recover results on benign overfitting\n\n", "questions": "- The matrix Q in Eq (4): I verified that Q is idempotent, but it is not clear that it is symmetric. are you sure this is the correct definition?", "limitations": "- limited to linear multi-index models and gaussian covariates", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- clear writing\n- easily interpreted results\n- results appear to be sound\n- the approach to studying generalization via Moreau envelope analysis is an interesting, and the present work initiates a nice connection between recent work in high dimensional statistics with generalization bounds.\n- the literature review is quite thorough\n\nWeaknesses:\n- the consequences of the main result are not really novel. better or essentially the same (up to constants) results have been obtained using other techniques before.\n- the present work would be stronger and more compelling if there was an example where these methods provided a strictly better rate than existing work.\n- some of the results only bound the expected Moreau loss, not the expected Loss\n- limited to linear multi-index models and gaussian covariates\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kl9Fyue4yqg", "reviewer": "Reviewer_vsNX", "summary": "This paper establishes generalization bounds for a broad class of losses over linear predictors by utilizing Moreau envelope theory. The authors show that particular quantities that depend on a localized Gaussian width can control the prediction error under Moreau envelopes of the loss, which can then translate to generalization bounds on the original loss as well. The setting is fairly broad, as it allows for models misspecification and more general loss functions. A number of previous results in the literature were extended.", "questions": "What is the intuition behind the use of the surrogate distribution in the main theorem (Theorem 1)? Does this aid in analyzing the interaction between the noise and the low-dimensionality of the data? Also, is the main hurdle in extending the Gaussian data assumption the use of the GMT framework for the analysis? I would also suggest a short discussion after the introduction of the Moreau envelope about why analyzing the Moreau envelope of the loss is useful. The results showcase the utility of the framework, but it could be good to provide some intuition beforehand.", "limitations": "Yes. No societal impacts need to be discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: There has been significant interest in better understanding generalization properties, especially of interpolating solutions. To the reviewer's knowledge, the application of the Moreau envelope framework to tackling generalization appears novel.\n\nQuality: The general theory provided here seems to give a number of improvements to previous results, including classical and recent ones. While the Gaussian data assumption is fairly restrictive, obtaining a complete understanding of this regime is still important.\n\nClarity: The paper is very well-written and easy to follow, even though it is quite technical. Here are some small comments:\n- need a space between sentences in line 163\n- the footnote at the top of page 8 takes you to page 1 instead of the bottom of the page\n\nSignificance: The work appears quite significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept