Introduction

Modern machine learning models often contain more parameters than the number of training samples. Despite the capacity to overfit, training these models without explicit regularization has been empirically shown to achieve good generalization performance (Neyshabur et al. 2015;C. Zhang et al. 2017;Belkin et al. 2019). On the theoretical side, the study of minimal-norm interpolation has revealed fascinating phenomena that challenge traditional understandings of machine learning.

We now have a better understanding of 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 once 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, even when the signal is sparse, the risk of the minimal-`1 norm interpolator can be shown to converge much slower to the Bayes risk than the minimal-`2 ⇤ These authors contributed equally. norm interpolator in the junk feature setting (Chatterji and Long 2021;Koehler et al. 2021). In contrast, the minimal-`2 norm interpolator fails to achieve consistency in the isotropic setting, while the minimal-`1 norm interpolator is consistent with sparsity but suffers from an exponentially slow rate in the number of parameters d (G. Wang et al. 2021;Muthukumar et al. 2020). However, we can still achieve the minimax rate with minimal-`p norm interpolators with p 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 a 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 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. In 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 et 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 highdimensional 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 parameter 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 a constant; this property alone suffices to obtain a generalization guarantee in terms of the original square loss. The squared hinge loss enjoys the same property, and hence a completely analogous argument shows an 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 of 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 a variety of feature distributions and label generating processes confirm the wide applicability of our theory.

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 et 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 asymptotics, rather than generalization, and does not provide any non-asymptotic results. Loureiro et al. 2021 studied proportional asymptotics in a student-teacher model similar to the one we consider, and gave finite-sample 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-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 to be convex.

For linear regression, Bartlett et al. (2020) identify nearly-matching necessary and sufficient conditions for the consistency of minimal-`2 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 et 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-`1 norm interpolator. Based on this uniform convergence framework, G. Wang et al. (2021) establish tight bounds for the minimal-`1 norm interpolator under a 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 an exponentially slow rate, Donhauser et al. (2022) show the minimal-`p 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 as 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-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-Gaussian features, and shows that benign overfitting does not necessarily occur in the most general setting, even with a spiked-covariance structure (see his Example 1).

For linear classification, Muthukumar et al. (2021) analyze `2 max-margin classifier by connecting to minimal-norm 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 `p maxmargin classifiers in the isotropic setting and do not consider the 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 `2 and `p (with p 2 [1, 2)) max-margin classifiers. Though their proof techniques also rely on the GMT, our approaches are drastically different. We use GMT in order to show uniform convergence for a class of predictors and establish a non-asymptotic bound, whereas their results are asymptotic and assume a proportional scaling limit. This is a key distinction, because overfitting usually cannot be benign with proportional scaling (e.g. Donhauser et 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 to 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 a 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 f : R ⇥ R ! R and i.i.d. sample pairs (x i , y i ) from some data distribution D, we can learn a linear model ( ŵ, b) by minimizing the empirical loss Lf with the goal of achieving small population loss L f :

Multi-index model. We assume that the data distribution D over (x, y) is such that 1. x ⇠ N (0, ⌃) is a centered Gaussian with unknown covariance matrix ⌃.

2. There are unknown weight vectors w ⇤ 1 , ..., w ⇤ k 2 R d such that the ⌃ 1/2 w ⇤ i are orthonormal, a function g : R k+1

! R, and a random variable ⇠ ⇠ D ⇠ independent of x (not necessarily Gaussian) such that

We can assume that the distribution of x is centered without loss of generality since presence of a mean term simply corresponds to changing the bias term b:

We can also assume that ⌃ 1/2 w ⇤ 1 , ..., ⌃ 1/2 w ⇤ k are orthonormal without loss of generality since we have not imposed any assumption on the link function g. The multi-index model includes wellspecified linear regression, by setting k = 1 and g(⌘, ⇠) = ⌘ + ⇠. It also allows nonlinear trends and heteroskedasticity (such as the model in Figure 1) by changing the definition of g. Since g need not be continuous, the label y can be binary, as in linear classification.

Moreau Envelope Generalization Theory

Our theory vitally depends on the Moreau envelope, defined as follows. Definition 1. The Moreau envelope of f : R ⇥ R ! R with parameter 2 R + is defined as the function f : R ⇥ R ! R given by

(3)

The Moreau envelope can be viewed as a smooth approximation to the original function f : in our parameterization, smaller corresponds to more smoothing. The map that outputs the minimizer u, known as the proximal operator, plays an important role in convex analysis (Parikh and Boyd 2014;Bauschke, Combettes, et al. 2011).

Our general theory, as stated in Theorem 1 below, essentially upper bounds the generalization gap between the population Moreau envelope L f and the original training loss Lf by the sum of two parts: a parametric component that can be controlled by the dimension k of the "meaningful" part of x, and a non-parametric component that can be controlled by a dimension-free complexity measure such as the Euclidean norm of the predictor. Typically, the first term is negligible since k 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 a (possibly oblique) projection matrix Q onto the space orthogonal to w ⇤ 1 , ..., w ⇤ k and a mapping from

We let ⌃ ? = Q T ⌃Q denote the covariance matrix of Q T x. We also define a low-dimensional surrogate distribution D over R k+1 ⇥ R by x ⇠ N (0, I k+1 ), ⇠ ⇠ D ⇠ , and ỹ = g(x 1 , ..., xk , ⇠).

(5)

This surrogate distribution compresses the "meaningful part" of x while maintaining the test loss, as shown by our main result Theorem 1 (proved in Appendix D). Note that as a non-asymptotic statement, the functions ✏ , and C only need hold for a specific choice of n and D.

Theorem 1. Suppose 2 R + satisfies that for any 2 (0, 1), there exists a continuous function ✏ , : R k+1 ! R such that with probability at least 1 /4 over independent draws (x i , ỹi ) from the surrogate distribution D defined in (5), we have uniformly over all ( w, b) 2 R k+2 that

Further, assume that for any 2 (0, 1), there exists a continuous function C : R d ! [0, 1] such that with probability at least 1 /4 over x ⇠ N (0, ⌃), uniformly over all w 2 R d ,

Then it holds with probability at least 1 that uniformly over all (w, b) 2 R d+1 , we have

If we additionally assume that (6) holds uniformly for all 2 R + , then (8) does as well.

As we will see, we can generally bound the difference between L f and L f when the loss is assumed to be Lipschitz. If f is not Lipschitz but smooth (i.e. rf 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 f is proportional to f , meaning that (8) becomes a generalization guarantee in terms of L f . 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 C (w) should be thought of as a localized, high-probability version of Rademacher complexity. This is because the Gaussian width of a convex set K, E sup w2K hw, xi, is the same as the Rademacher complexity of the class of linear functions {x 7 ! hw, xi : w 2 K} (Zhou et al. 2021, Proposition 1). A somewhat similar complexity functional appears in Panchenko (2003). Also, note (6) requires only one-sided concentration -see Remark 3.

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 ✏ , ) will inevitably depend on the exact setting we consider (see e.

The assumption (9) is standard (indeed, this is the setting primarily focused on in Vapnik 1982) and is sometimes referred to as hypercontractivity or norm equivalence in the literature; a variant of the result holds with 4 replaced by 1 + ✏. In many settings of interest, this can be directly checked using the fact that x is Gaussian (for instance, see Theorem 9 and Appendix E. The last conclusion (uniformity over ) 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, it is 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 k have VC dimension k + 1.

Applications

Linear Regression with Square Loss

In this section, we show how to recover optimistic rates (Zhou et al. 2021) for linear regression without assuming the model is well-specified. We will consider the square loss, f (ŷ, y) = (ŷ y) 2 . A key property of the square loss is that the Moreau envelope is proportional to itself:

Thus we can multiply by (1 + )/ in our generalization bound and solve for the optimal choice of .

Corollary 2. Suppose f is the square loss and the surrogate distribution D satisfies assumption (9) uniformly over (w, b) 2 R k+1 , then with probability at least 1 , uniformly over all w, b we have

As mentioned earlier, assumption (9) usually holds under mild conditions on y. For example, ⌧ can be chosen to be a constant when y is a bounded-degree polynomial of a Gaussian due to Gaussian hypercontractivity (O'Donnell 2014, Section 11.1). Specializing Corollary 2 to interpolators ( Lf = 0) recovers the uniform convergence of interpolators guarantee from Koehler et al. (2021).

Combined with a more general norm analysis in Section 6, we establish `2 benign overfitting with misspecification. In the well-specified case, see Zhou et al. (2021) for detailed examples on ordinary least squares, ridge regression, and LASSO.

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 (ŷ, y) = max(0, 1 y ŷ) 2 . Its Moreau envelope is given by

We consider the case of a general binary response y valued in {±1} satisfying the model assumptions in equation ( 2). In this case as well, f is 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 E.3.1, we discuss certain settings (including noisy settings) where minimizing the squared hinge loss also minimizes the zero-one loss, i.e. the misclassification rate.

For regression, the number of leading eigenvalues is k = 3, and the label is generated according to y = 1.5 x 1 + |x 1 | cos x 2 + x 3 • N (0, 0.5). For classification, the number of leading eigenvalues is k = 1 and Pr(y = 1 | x) = sigmoid(5x 1 + 3).

The risk bound is calculated using the expression p L + p kwk 2 2 Tr(⌃ ? )/n 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 w is projected to the orthogonal complement of the Bayes predictor w ⇤ (Zhou et al. 2021). In the other cases, we use covariance splitting without projection of w. Each point on the curve is the average from repeated experiments, and shaded areas correspond to 95% bootstrap confidence intervals.

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.

L 1 loss (LAD) and Hinge. For the L 1 loss f (ŷ, y) = |ŷ y| its Moreau envelope is given by

which is 2 times the Huber loss with parameter = 1 2 . Therefore, the population Huber loss is controlled by the empirical L 1 loss. Clearly, interpolators have zero training error under both L 1 and L 2 training losses. We already see that Corollary 2 implies (1 o(1)) E(hw, xi+b y) 2  C (w) 2 /n. Now, considering Corollary 1 with f the L 1 loss and using the above Moreau envelope calculation, we can check that when ! 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, 1 ŷy): its Moreau envelope f will be a rescaling of the Huber hinge loss (c.f. T. Zhang 2004a).

Lipschitz loss: improved contraction. If f is M -Lipschitz in ŷ, Proposition 3.4 of Planiden and X. Wang (2019) gives that 0  f f  M 2 4 . Thus, assuming k/n = o(1), Corollary 1 implies

; optimizing over yields

For w 2 K, a high-probability upper bound on the Rademacher complexity of the function class x 7 ! hw, xi upper bounds the second term (Remark 1). In comparison, the standard symmetrization and contraction argument (Bartlett and Mendelson 2002) loses a factor of two. Note that if f is the L 1 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 | @ 2 f @ ŷ2 |  H) and convex function of ŷ. In addition, assume that the minimum of f (ŷ, y) is zero for any fixed y. Since f is H-smooth, there exists a function f such that f = fH/2 (Bauschke, Combettes, et al. 2011, Corollary 18.18). If w satisfies Lf (w) = 0, then L f (w) = 0 as well.foot_0 Finally, by Corollary 2, if k/n = o(1) we have uniformly over all w such that Lf (w) = 0 that

which generalizes the main result of Koehler et al. (2021) to arbitrary smooth losses.

`2 Benign Overfitting

We can obtain conditions for consistency, like those of Bartlett et al. (2020), by simply combining a norm-based uniform generalization bound with an upper bound on the norm of interpolators. Koehler et al. (2021) used the same strategy, but our more powerful and general tools give better results:

1. For squared loss regression, we 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 modelfoot_1 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 f = 1+ f and that f is the square of a Lipschitz function.

First, the following lemma (essentially just the standard Rademacher complexity bound for the `2 ball) combines with Corollary 2 and its squared hinge loss version to give generalization bounds. These bounds are demonstrated in Figure 1 andAppendix B.

Lemma 1. In the setting of Theorem 1, letting ⌃ ? = Q T ⌃Q, the following C (w) will satisfy (7):

Next, we provide a sufficient condition for a zero-training error predictor w to exist in an `2 ball. In the case of classification, this allows us to lower-bound the margin of the max-margin halfspace. Lemma 2. Suppose that f (ŷ, y) is either squared loss or squared hinge loss. Let (w ] , b ] ) 2 R d+1 be an arbitrary vector satisfying Qw ] = 0 and with probability at least 1 /4,

for some ⇢ 1 (w ] , b ] ) > 0. Then for any ⇢ 2 2 (0, 1), provided

we have that with probability at least 1 that min kwkB L f (w, b ] ) = 0 for B > 0 defined by

We note that for any vector w ] , we have

) by Jensen's inequality over Q T x, so the assumption Qw ] = 0 in the lemma is always satisfied for the minimizer of L f (w, b).

Combining the norm bound Lemma 2 and the generalization bound Lemma 1 yields the following.

where ⇢ 3 > 0 is defined by

i 2 and we recall ⇢ 1 (w ] , b ] ) from (13).

We now show that this formally implies convergence to the optimal test loss (i.e. consistency) under the `2 benign overfitting conditions (15) from Bartlett et al. (2020) and Tsigler and Bartlett (2020): Corollary 3. Suppose that D n is a sequence of data distributions following our model assumptions (2), with k n such that y = g(⌘ 1 , . . . , ⌘ kn , ⇠), and projection operator Q n defined as in (4). Suppose f is either the squared loss or the squared hinge loss, and define

) is the population loss over distribution D n with loss f . Suppose that the hypercontractivity assumption (9) holds with some fixed ⌧ > 0 for all D n . Define ⌃ n := E Dn [xx T ] and ⌃

Then we have the following convergence in probability, as n ! 1:

where ( ŵn , bn ) = arg min w2R d ,b2R: Lf (w,b)=0 kwk 2 is the minimum-norm interpolator, and Lf,n is the training error based on n i.i.d. samples from the distribution D n .

Note when applying Corollary 3, we have the flexibility to increase k n and shrink ⌃ ?

n by choosing additional weights w ⇤ i 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 a slightly stronger statement: let ( ŵn , bn ) 2 arg min kwkBn,b2R Lf,n (w ] n , b ] n ) such that, if there are multiple minima, we pick the one with smallest kwk. As long as B n kw ] n k, we still have ( 16), and this is established uniformly over all sequences B n satisfying the constraint. Therefore, under the benign overfitting conditions we get consistency as long as we do not over-regularize the predictor. See Figure 1 for an experimental demonstration of the flatness.

Training Error and Local Gaussian Width

Theorem 1 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. In particular, this general result is used to 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 ⌧ is such that with probability at least 1 , for (x, ỹ) n i=1 sampled i.i.d. from D we have Then with probability at least 1 2 , min w2K,b2B Lf (w, b)  ⌧ .

Note that the assumption (17) implicitly suggests a low-dimensional concentration assumption: we expect 1 n P n i=1 f (h w, xi + b 0 , y i ) to be approximately the test loss of ( w, b 0 ) under the surrogate distribution D. As we discuss more in Appendix F, combining this training error bound with the correct choice of C (w) in Theorem 1, which is essentially C (w) = E max w02 1 ( w)\K hx, Qw 0 i 2 ), yields a matching lower bound to (8) on the Moreau envelope test loss and so our generalization 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).

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-dimensional 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. It does appear experimentally that it may hold much more broadly (Appendix B); proving that this is the case could allow us 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 Gaussian-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 to 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.