Uniform Convergence with Square-Root Lipschitz Loss
Authors: Lijia Zhou
Zhen Dai
Frederic Koehler
Nathan Srebro
Venue: NeurIPS 2023 poster (2023)
Keywords: Uniform Convergence
Square-Root Lipschitz
Benign Overfitting
Minimal Norm Interpolation
Phase Retrieval
ReLU Regression
Matrix Sensing

Abstract: We establish generic uniform convergence guarantees for Gaussian data in terms of the Radamacher complexity of the hypothesis class and the Lipschitz constant of the square root of the scalar loss function.  We show how these guarantees substantially generalize previous results based on smoothness (Lipschitz constant of the derivative), and allow us to handle the broader class of square-root-Lipschtz losses, which includes also non-smooth loss functions appropriate for studying phase retrieval and ReLU regression, as well as rederive and better understand “optimistic rate” and interpolation learning guarantees.

Uniform Convergence with Square-Root Lipschitz Loss
Lijia Zhou University of Chicago z1j 21j@uchicago.co edu
Zhen Dai
Frederic Koehler Stanford University
University of Chicago zhen9@uchicago.c edu
fkochler@stanford
Nathan Srebro
Toyota Technological Institute at Chicago nati@ttic. edu
Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations ai)
Abstract
We establish generic uniform convergence guarantees for Gaussian data in terms the Rademacher complexity of the hypothesis class and the Lipschitz constant of the square root of the scalar loss function. We show how these guarantees substantially generalize previous results based on smoothness (Lipschitz constant of the derivative), and allow to handle the broader class of sguare-rott-Lipchhee losses, which includes also non-smooth loss functions appropriate for studying phase retrieval and ReLU regression, as well as rederive and better understand "optimistic rate" and interpolation learning guarantees.
Introduction
The phenomenon of "interpolation learning", where a learning algorithm perfectly interpolates noisy training labels while still generalizing well unseen data, has attracted significant interest recent years. As Shamir (2022) pointed out, one of the difficulties in understanding interpolation learning that we need to determine which loss function we should use to analyze the test error. In linear regression, interpolating the square loss is equivalent to interpolating many other losses (such as the absolute loss) on the training set. Similarly, in the context of linear classification, many works (Soudry et al. 2018; Ji and Telgarsky 2019; Muthukumar al. 2021) have shown that optimizing the logistic, exponential, or even square loss would all lead to the maximum margin solution, which interpolates the hinge loss. Even though there are many possible loss functions to choose from to analyze the population error, consistency is often possible with respect to only one loss function because different loss functions generally have different population error minimizers.
In linear regression, it has been shown that minimal norm interpolant can be consistent with respect to the square loss (Bartlett et al. 2020; Muthukumar et al. 2020; Negrea et al. 2020; Koehler et al. 2021). while the appropriate loss for benign overfitting linear classification the squared hinge loss (Shamir 2022; Zhou et al. 2022). In this line of work, uniform convergence has emerged as general and useful technique to understand interpolation learning (Koehler al. 2021; Zhou et al. 2022). Though the Lipschitz contraction technique has been very useful to establish uniform convergence in classical learning theory, the appropriate loss functions to study interpolation learning (such as the square loss and the squared hinge loss) are usually not Lipschitz. In fact, many papers (Nagarajan and Kolter 2019; Zhou et al. 2020: Negrea et al. 2020) have shown that the traditional notion of uniform convergence implied by Lipschitz contraction fails in the setting of interpolation learning. Instead, need to find other properties the loss function to establish a different type of uniform convergence.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Zhou et al. (2022) recently showed that the Moreau envelope of the square loss or the squared hinge loss is proportional to itself and this property is sufficient establish a type of uniform convergence guarantee known as "optimistic rate" (Panchenko 2002; Srebro et al. 2010). Roughly speaking, if this condition holds, then the difference between the square roots of the population error and the training error can be bounded by the Rademacher complexity of the hypothesis class. Specializing to predictors with zero training error, the test error can then be controlled by the square of the Rademacher complexity, which exactly matches the Bayes error for the minimal norm interpolant when it is consistent (Koehler et al. 2021). However, the Moreau envelope of a loss function is not always easy to solve in closed-form, and is unclear whether this argument can be applied to problems beyond linear regression and max- max-mnn classification. Moreover, considering the difference of square roots seem like mysterious choice and does not have a good intuitive explanation.
In this paper, by showing that optimistic rate holds for any square-rool Lipschitz loss, we argue that the class of square-root Lipschitz losses is the more natural class of loss functions to consider. In fact, any loss whose Moreau envelope is proportional to itself is square-root Lipschitz. Our result also provides an intuitive explanation for optimistic rate: when the loss is Lipschitz, the difference between the test and training error can be bounded by Rademacher complexity; therefore, when the loss is square-root Lipschitz, the difference between the square roots of the test and training error can be bounded by Rademacher complexity. In addition to avoiding any hidden constant and logarithmic factor, our uniform convergence guarantee substantially generalize previous results based on smoothness (Lipschitz constant of the derivative, such as Srebro et al. 2010). The generality of results allows us to handle non-differentiaabee losses. In the problems of phase retrieval and ReLU regression, we identify the consistent loss through a norm calculation, and we apply our theory to prove novel consistency results. In the context of noisy matrix sensing, we also establish benign overfitting for the minimal nuclear norm solution. Finally, we show that our results extend to fully optimized neural networks with weight sharing in the first layer.
2 Related Work
Optimistic rates. In the context of generalization theory, our results are related to a phenomena known as "optimistic rates" generalization bounds which give strengthened guarantees for predic- tors with smaller training error. Such bounds can be contrasted with "pessimistic" bounds which do not attempt to adapt to the training error of the predictor. See for example Vapnik 1982; Panchenko 2003; Panchenko 2002. The work of Srebro et al. 2010 showed that optimistic rates control the generalization eтror of function classes learned with smooth losses, and recently the works Zhou et al. 2021; Koehler et al. 2021; Zhou al. 2020 showed that a much sharper version of optimism can naturally explain the phenomena of benign overfitting in Gaussian linear models. (These works are turn connected with a celebrated line of work in proportional asymptotics for M-estimation such as Stojnic 2013, see references within.) In the present work, we show that the natural setting for optimistic rates is actually such as phase retrieval where the loss is not smooth.
Lopts--ssth losses and this allows us to capture new applications
Phase retrieval, ReLU Regression, Matrix sensing. Recent works (Maillard et al. 2020; Barbier et al. 2019; Mondelli and Montanari 2018; Luo et al. 2019) analyzed the statistical limits of phase retrieval in a nigh-dimensional limit for certain types of sensing designs (e.g. i.i.d. Real or Complex Gaussian), as well as the performance of Approximate Message Passing in this problem (which is used to predict a computational-statee statiistical gap). In the noiseless case, the works Andoni et al. 2017; Song et al. 2021 gave better computationally efficient estimators for phase retrieval based upon the LLL algorithm. Our generalization bound can naturally be applied to any estimator for phase retrieval, including these methods other ones, such as those based on non-convex optimization (Sun et al. 2018; Netrapalli et al. 2013). For the same reason, they can also naturally be applied in the context of sparse phase retrieval (see e.g. Li and Voroninski 2013; Candes et al. 2015).
Similarly, there have been many works studying the computational tractability of ReLU regression. See for example the work of Auer et al. 1995 where the "matching loss" technique was developed for learning well-specified GLMs including ReLUs. Under misspecification. learning ReLUs can be hard and approximate results have been established, see e.g. Goel et al. 2017; Diakonikolas et al. 2020. In particular, learning a ReL.U agnostically in squared loss, even over Gaussian marginals, is known to be hard under standard average-case complexity assumptions (Goel et al. 2019). Again, our

---

generalization bound has the merit that it can be applied to any estimator. For matrix sensing, we consider nuclear norm minimization (as e.g. Recht et al. 2010) which is a convex program, so can always be computed in polynomial time.
Weight-tied neural networks. The work of Bietti et al. 2022 studies similar two-layer neu- ral network model with weight tying. Their focus is primarily on understanding the non-convex optimization of this model via gradient-based methods. Again, our generalization bound can be straightforwardly combined with the output of their algorithm. The use of norm-based bounds as in our result is common in the generalization theory for neural networks, see e.g. Bartlett (1996) and Anthony, Bartlett, et al. (1999). Compared to existing generalization bounds, the key advantage of our bound is its quantitative sharpness (e.g. small constants and no extra logarithmic factors).
3 Problem Formulation
In most of this paper, we consider the setting of generalized linear models. Given any loss function f: IR x y + 2g and independent sample pairs (x,, 3/) from some data distribution D over R2 x V, we can learn linear model (10, b) by minimizing the empirical loss Ly with the goal of achieving small population loss Ly:
Ly(w, b)
Σ M(w,a))) + b,);), Ly(w, b) B(aw)) + v)]- n.
1
1 n
In the above, y' is an abstract label space. For example, y = R for linear regression and y Rzo for phase retrieval (section 5.1) and ReLU regression (section 5.2). If view 2; as vectorization of the sensing matrices, then our setting (1) also includes the problem of matrix sensing (section 5.3).
For technical reasons, we assume that the distribution D follows a Gaussian multi-index model (Zhou et al. 2022).
(A) d-dimensional Gaussian features with arbitrary mean and covariance: x N Σ)
(B) a generic multi-index model: there exist a low-dimensional projection W [wi .... wi] dd a random variable & De independent of (not necessarily Gaussian), and an unknown link function g : R*+1 + y such that
n7 x)), y = g(m. ..., E).
We require z to be Gaussian because the proof of our generalization bound depends the Gaussian Minimax Theorem (Gordon 1985; Thrampoulidis et al. 2014), as in many other works (Koehler et al. 2021: Zhou et al. 2022; Wang et al. 2021; Donhauser et al. 2022). In settings where the features not Gaussian, many works (Goldt et al. 2020; Mei and Montanari 2022; Misiakiewicz 2022; Hu and Lu 2023; Han and Shen 2022) have established universality results showing that the test and training error are asymptotically equivalent to the error of a Gaussian model with matching covariance matrix. However, we show in section 7 that Gaussian universality is not always valid and we discuss potential extensions of the Gaussian feature assumption there.
The multi-index assumption is generalization of a well-specified linear model y -ww,, ,x) + E. which corresponds to k 1 and g(7) <) = 17 + E in (2). Since g is not even required to be continuous, the assumption on y is quite general. It allows nonlinear trend and heteroskedasticity, which pose significant challenges for the analyses using random matrix theory (but not for uniform convergence). In Zhou al. (2022), the range of g is taken to be y {-1, 1} in order to study binary classification. In section 5.2, we allow the conditional distribution of to have point mass at zero, which is crucial for distinguishing ReL.U regression from standard linear regression.
Optimistic Rate
In order to establish uniform convergence, we need two additional technical assumptions because we have not made any assumption on f and g.
3

---

(C) hypercontractivity: there exists a universal constant (w, b) IR x R, it holds that
>
such that uniformly over all
E [[f( b. [[f b, 3)]
S
(3)
(D) the class of functions on R++11 x )' defined below has VC dimension at most h: ((x, [[[(w, x), v) 1) (w, E TR*+1 x R).
(4)
Crucially, the quantities and h only depend the number of indices & in assumption (B) instead of the feature dimension d. This is key distinction because & can be small constant even when the feature dimension is very large. For example, recall that h = 1 in well-specified model and it is completely free of d. The feature dimension plays no role in equation (3) because conditioned on W E I and & R, the response y non-random and the distribution of (w, x) for any Rd only depends on w² μ and w" Ew by properties of the Gaussian distribution.
The hypercontractivity (or "norm equivalence") assumption (3) is one of few different common assumptions made in the statistical learning theory literature to rule out the possibility of a very heavy-tailed loss function. The reason is that if the loss function has very tiny chance of being extremely large, it is not possible to state any meaningful learning guarantee from a finite number of samples. Hypercontractivity
used as assumption already in Vapnik 1982. Another common and incomparable assumption made in the literature is boundedness, but this is not suitable for us because, e.g., the squared loss under the Gaussian distribution will not be bounded almost surely. On the other hand, if is the squared loss then (3) holds with Gaussian distribution. We can also state other versions of our main theorem by using other results in statistical learning theory handle the low-dimensional concentration; in our proof we simply use result from Vapnik 1982 a contained and black-box fashion. (See e.g. Mendelson 2017; Vapnik 1982 for more discussion of the different possible assumptions.)
100 by standard properties of the
Similar assumptions are made in Zhou et al. (2022) and more background on these assumptions can be found there, but we note that our assumption (C) and (D) are weaker than theirs because we do not require (3) and (4) to hold uniformly over all Moreau envelopes of f.
We are now ready to state the uniform convergence results for square-root Lipschitz losses.
Theorem 1. Assume that (A), (B), (C), and (D) holds, and let Q (WW -'T'. For any 8 E (0, let Cs Rd [0, oo] be a continuous function such that with probability at least 1 6/4 over ~ (0, uniformly over all w R
(w,, Q" x) S Csslw).
(5)
If for each y E V. f non-negative and V is VH-Lipschit. with respect to the first argument, then with probability al least 1 - 5, it holds that uniformly over all (w, b) E IRd x IR, we have
2
(VErlu.))
H (w))2
(1- -
(6)
where e O (TV (og(n/h)++og(//
Since the label only depends on x through W x, the matrix Q is simply a (potentially oblique) projection such that QT x independent of y. In the proof, we separate x into a dimeennnsio component related to y and the independent component QTx.. z. We establish concentration result using VC theory, which is reflected in the term that does not depend on d, and we control the the remaining high-dimensional component using a scale-sensitive measure Cs-
low-dimensional
The complexity term Ca (w)) /n should be thought of as (localized form of) Rademacher complexity R,,. For example, for any norm || we have (w, Q" .r) < || || x=/l= and the Rademacher complexity for linear predictors with norm bounded by B is B E|| //vn (Shalev-Shwartz and Ben-David 2014). More generally, if we only care about linear predictors in a set K, then C/ so |supwex (w. Q2xx))))) is simply the Gaussian width (Bandeira 2016; Gordon 1988; Koehler et al. 2021) of IC with respect to E = x and is exactly equivalent to the expected Rademacher complexity of the class of functions (e.g., Proposition I of Zhou et al. 2021).

---

5 Applications
We now go on to analyze several different problems using optimistic rates and sqrt-lipschitz losses. One of the key insights want highlight is the idenrification of the consistent loss for many of these problems - in other word, the test loss which is implicitly being minimized. When we consider interpolators/overfitt models, this is not obvious because interpolator simultaneously minimizes many different training losses (and when we look at the test loss, each different loss functional may correspond to different minimizer). Nevertheless, we are able to analyze phenomena like benign overfitting by identifying the particular sqrt-Lipschitz, losses which the interpolator is consistent in, i.e. for which it approaches the minimum of the test loss in the appropriate limit.
5.1 Benign Overfitting in Phase Retrieval
In this section, we study the problem of phase retrieval where only the magnitude of the label y can be measured. If the number of observations n < d, the minimal norm interpolant
V
arg min WER (w..))
1100122-
We are particularly interested in the generalization error of (7) when y, are noisy labels and so i overfits to the training set. It is well-known that gradient descent initialized at zero converges to KKT point of the problem (7) when it reaches zero training error solution (see e.g. Gunasekar et al. 2018). While is not always computationally feasible to compute w, we can study it as a theoretical model for benign overfitting in phase retrieval.
Due to our uniform convergence guarantee in Theorem 1, suffices analyze the norm of á and we can use the norm calculation to find the appropriate loss for phase retrieval. The key observation that for any w E Rdd, we can let I = (i E [m] (wF, xz) 2 0} and the predictor w = wF + w- satisfies (w, am) Y: where
w
arg min
||w||22
(8)
wER1: VIE ( Vig (eng,,( [(w (x))) -
Then it holds that || S ||l||2 < ||00112 + ||w By treating yi - 1(w .z5)| and ((w", y:
as the residuals, the norm calculation for ||-112 is the same as the case of linear regression (Koehler
al. 2021; Zhou et al. 2022). Going through this analysis yields the following norm bound (here R(E) = Tr(=)² Tr(E²) is a measure of effective rank, as in (Bartlett et al. 2020)):
Theorem 2. Under assumptions (A) and (B), let f R x y + IR be given by f y) = (1ø) - y)²
with y = Rzo- Let Q be the same as in Theorem and Σ = QT Fix any w E Rdd such that
Qw = and for some p E (0, 1), it holds that
(w (1+ (w)(
(9)
Then with probability at least - 8. for some e S + log log
+ k
+
it
Va
VR(E-)
R(E
holds that
nL (L
min WER (el
| S | + (1 + V
(10)
Tr(E--)
Note that in this result we used the loss f y) (lø) y) which is l-square-root Lipschitz and naturally arises in the analysis. We will now show that this the correct loss in the sense that benign overfitting is consistent with this loss. To establish consistency result, we can pick w to be the minimizer of the population error. The population minimizer always satisfies Qw = 0 because L Q) < (w) for all w E Rd by Jensen's inequality. Condition (9) can also be easily checked because we just need concentration of the empirical loss at a single non-random parameter. Applying Theorem 1, we obtain the following.
5

---

Corollary 1. In the same setting as in Theorem 2, with probability at least 1 - 8, it holds that for some
klog(n//)) + log(1/0) + log (1/8)
1
k
P TV
n
/R(E-)
n
R(2+)
the minimal norm interpolant i given by (7) enjoys the learning guarantee:
L(ū. b) S p1+ ( (Vulut,bb 6F) || 1|2
Tr(E-)
(11)
Therefore, d is consistent if the same benign overfitting conditions from Bartlett et al. (2020) and Zhou et al. (2022) hold: & = o(n), = w(n) and ||wl| Tr o(n).
5.2 Benign Overfitting ReLU Regression
Since we only need vJ to be Lipschitz, for any 1-Lipschitz function : R - R, we can consider
① f(g v) (0) y)² when y R
i f(). v) = (1 o ( when y = (-1,1}.
We can interpret the above loss function f as learning a neural network with a single hidden unit. Indeed, Theorem 1 can be straightforwardly applied to these situations. However, we do not always expect benign overfitting under these loss functions for the following simple reason, as pointed out in Shamir (2022): when is invertible, interpolating the loss [(ū y) (α) y)² the interpolating the loss (ū
as (9.9) y) = (ú - (y))² and so the learned function would be the minimizer of [] which typically different from the minimizer of B[(a (w, + +6) y)
E[((w, 2)) +b
The situation of ReLU regression, where (ū) = max ( 0}. is more interesting because o is not invertible. In order to be able to interpolate, we must have y 2 0. If y > O with probability 1, then (ū) = y is the same as y = y and we are back to interpolating the square loss f(ū. y) = (0 y) From this observation, we that f(ū y) (a) cannot be the appropriate loss for consistency even though it's 1 square-root Lipschitz. In contrast, when there is some probability mass at y = 0, suffices output any non-positive value and the minimal norm interpolate is potentially smaller than requiring ý = 0. Similar to the previous section, we can let I = {i E [m] yi >> 0} and for any (w=, b²) E gd+1 the predictor w wt + w satisfies ((w, x4) + 65) = ys where
w-
arg min wERd: (w.a))) (wc (w) m
||l|22
(12)
Vigl (w,,,))) (...6)))++)))
Our analysis will show that the consistent loss for benign overfitting with ReI.U regression is
(0 y) if
y >
f(6.v) = (0))²
(13)
if y 0.0.
We first state the norm bound below.
Theorem 3. Under assumptions (A) and (B), let f R x y - R. be the loss defined in (13) with
= Rzo- Let Q be the same as in Theorem I and Σ Q² EQQ Fix any (w², 6²) E Rd+1 such that
Qwa and for some p (0, 1), it holds that
( bt) s (1+ ( Then with probability least 8, for some S p log (+) (+a VM(I") + + n(s.
(14)
holds that
nT. b4) Tr(E+)
min (u. viE(n) ((w..))+)))
||ll|
||wi (1 (1+
(15)
Since the loss defined in (13) is also I-square-root Lipschitz, it can be straightforwardyy combined with Theorem to establish benign overfitting in ReI.U regression under this loss. The details are exactly identical to the previous section and so we omit it here.

---

5.3 Benign Overfitting in Matrix Sensing
We now consider the problem of matrix sensing: given random matrices Aq...., An (with i.d.d standard Gaussian entries) and independent linear measurements yi..... Yn given by y4 = (A, &. where & independent of A,, and EE 0 and EE o², we hope to reconstruct the matrix X E dR xd2 with sample size n & d1 d2. To this end, we assume that X has rank r. In this setting, since the measurement matrices have i.i.d, standard Gaussian entries, the test error is closely related to the estimation error:
(X) = [((A,)) - y)² = |X- - 1 + +o²
The classical approach to this problem is to find the minimum nuclear norm solution:
X
arg min X NER Xx)
|
(16)
Gunasekar et al. (2017) also shows that gradient descent converges to the minimal nuclear norm solution in matrix factorization problems. It is well known that having low nuclear can ensure generalization (Foygel and Srebro 2011; Srebro and Shraibman 2005) and minimizing the nuclear norm ensures reconstruction (Candès and Recht 2009; Recht al. 2010). However, the noise level is high, then even the minimal nuclear norm solution X can have large nuclear norm. Since result can be adapted to different norms as regularizer, our uniform convergence guarantee can be directly applied. The dual norm of the nuclear norm is the spectral norm, and it is well-known that the spectrum norm of a Gaussian random matrix is approximately vd1 + Vdz (Vershynin 2018). It remains to analyze the minimal nuclear norm required to interpolate. For simplicity, we assume that & are Gaussian below, but we can extend it to be sub- uub-Gaussian.
Theorem 4. Suppose that di d2 > then there exists some E probability at least 8, it holds that
(2g(32/))
such that with
d,d2
na
min XA.
+ (1+ |X|1. S +
(17)
d2 V
d2
Without loss of generality, we will assume d1 < d2 from now on because otherwise we can take the transpose of A and X. Similar to assuming nz/ /[C ) + 0 in linear regression, we implicitly assume that n/d /d d2 - 0 in matrix sensing. Such scaling is necessary for benign overfitting because of the lower bound on the test error for any interpolant (e.g., Proposition 4.3 of 7hou et al. 2020). Finally, we apply the uniform convergence guarantee.
Theorem 5. Fix any E (0,1). 1). There exist constants C1, C2 C3 such that if d cnn.
d2 > c2d1, >> cgr(d1 + d2), then with probability at least 1 - 5 that
r(d1 + d2) { - -x
r(d1 + d2) |X
di
n
2
X S
+
(V
(18)
n
n
d2
d1
d1
X x 1
From Theorem 5, we see that when the signal to noise ratio |X is bounded away from zero,
then we obtain consistency - 1
if (i) r(d, + d2) = o(n), (ii) did2- w(n), and (iii) dd - {0, oo). This can happen for example when O(1), = ( d2 = @(n As discussed earlier, the second condition is necessary for benign overfitting, and the first consistency condition should be necessary even for regularized estimators. It is possible that the final condition is not necessary and we leave a tighter understanding of matrix sensing as future work.
6 Single-Index Neural Networks
We show that our results extend even more general setting than (1), Suppose that we have parameter space + C I"' and a continuous mapping w from 0 E θ to a linear predictor w(f) e Rd Given function f: R y x θ + R and i.idd. sample pairs (Iz ys) drawn from distribution D, we consider training and test error of the form:
1 L(0) = n
Σ
(O),
and L(O)- = (O))
(19)
7

---

We make the same assumptions (A) and (B) on D. Assumptions (C) and (D) can be naturally extended the following:
(E) there exists a universal constant such that uniformly over all & E e, it holds that
2)) [ff(( v. S.
(20)
(F) bounded VC dimensions: the class of functions on R x y defined by ((z, v) - 1[f((w, z) v. > f (w,t,) E R x xx
(21)
has VC dimension at most h.
Now we can state the extension of Theorem 1.
Theorem 6. Suppose that assumptions (A), (B), (E) and (F) hold. For any 5 (0,1), let Cs Rd - [0, oo] be continuous function such that with probability at least 1 8/ over N (0, E), uniformly over all E A
(w(0), Q x) S Cs(wo(0))
(22)
If for each 0 E θ and f is non non-negative and Vf is v Heg-ipschiitz with respect to the first argument, and Ha continuous in 0, then with probability least ö, it holds that uniformly over all E O we have
(1 (1-))(()) & (VE00)+ v
Ho Ca(w(0))2
(23)
Next, we show that the generality of result allows us establish uniform convergence bound for two-layer neural networks with weight sharing. In particular, we let (z) = max(æ, 0) be the ReLU activation function and f = (w, a, b) E Rd42N where N is the number of hidden units. Consider the loss function
N
2
f(0.200)
Σ (0 - b1) y
f(D.v.0)
(1
Σ
a.0
biyy
(24)
then L(0) is the test error of neural network of the form (x)x) En a b.). Since our uniform convergence guarantee holds uniformly over all 0, it applies to networks whose first and second layer weights optimized the same time. Without loss of generality,
assume that E a. Lipschitz. Applying
b1 S < by are sorted, then it is casy to see that vf is maxje(N] Theorem 6, we obtain the following corollary.
Corollary 2. Fix arbitrary norm and consider f defined in (24). Assume that the data distribution D satisfy (A), (B), and (E). Then with probability at least 6, holds that uniformly over all 0 (w, a. b) E IR IRd+2N
have
V max J[[]]
El= ai
||w|| (EllQT 21 + (0)
(10)) S
(25)
Vn
where is the same as in Theorem 6 with h = Ö(k- - N) and e' = (sup |/ v 105(1
The above theorem says given a network parameter 6, after sorting the b, 's a good complexity measure look is max El= a: ||w|| and equation (25) precisely quantify how the complexity of network controls generalization.
7 On Gaussian Universality
In this section, we discuss a counterexample Gaussian universality motivated by Shamir (2022). In particular, consider data distribution D over (æt y) given by:

---

(G) 2 (z) d where m/a ~ (O, E(R) and there exists function h: R - R such that
2|d-k = 1( 2 with 2~ N0, independent of 2/p
(26)
(H) there exists function g Rk+1 R such that
((
(27)
where De is independent of æ (but not necessarily Gaussian).
By the independence between and 2ik. we can easily see that 24 and r/a-s are uncorrelated. Moreover, the covariance matrix 2 dijdk is
E Blaja- E((x> -
which is just re-scaling of Ejd= and therefore has the same effective rank as R(E]d=k). Even though the feature x D is non- Gaussian, its tail Tjd-k is Gaussian conditioned on z k- Therefore, proof technique is still applicable after conditioning step. However, it turns out that the uniform convergence bound in Theorem is no longer valid. Instead, we have to re-weight the loss function. The precise theorem statements can be found in the appendix. We briefly describe theoretical results below, which follow the same ideas as in section and 5.
Uniform Convergence. Under a similar low-dimensional concentration assumption such as (C), we let C be such that (ur, z) S Cs(w) for all w E Rd-k with high probability, it holds that
M/, x), w) E
1 =
S(w, a.), h(0:)a)²
Co(w d-k)
< (1+
(28)
h(
vn.
Note that the distribution of is specified in (G) and different to the distribution of Tjd-k-
Norm Bound. Next, we focus on linear regression and compute the minimal norm required to interpolate. If pick -ia- satisfy the benign overfitting conditions, for any wit Rt we have
9 (wie ae 27 h((0ja)
nE
min WER (w.
1 < Ju
+
+ o())
(29)
Tr(E)d-s)
is easy that the w" that minimizes the population weighted square loss satisfy w/s and so we can let woj to be the minimizer.
Benign Overfitting. Let v arg min e ||w|| be the minimal norm interpolant. Plug- ging in the norm bound (29) into the uniform convergence guarantee (28), we show that
((w) x) - y)² h(21))²
| Tr(Eja-n)
((w" x) y) h(z)))2
E
(1 + o(1)
E
(30)
which recovers the consistency result Shamir (2022).
Contradiction. predict that
Suppose that Gaussian universality holds, then our optimistic rate theory would
B[((1,, x) -) (1+ ((1) |101 E[h(x, ( Tr
(31)
Combining (30) with (31), we obtain that
min E[((u x² - y)21 s (1 + o(1)) min E[((z)) -I ( (y-(un (w, (x)
27
(32)
h(x1e)

---

which cannot always hold. For example, let's consider the case where k = 11 (N 1). h(x1) =1+1 x1 and y = h(z1)² Then is straightforward to verify that the left hand side of (32) equals [()( and the right hand side equals {[ 2 but this is impossible because
B[h(x1)' - ()) ) (ar(h(()))) 0.
In the counterexample above, we see that is possible to introduce strong dependence between the signal and the tail component of x while ensuring that they are uncorrelated. The dependence will prevent the norm of the tail from concentrating around its mean, no matter how large the sample size is. In contrast, the norm of the tail will concentrate for Gaussian features with matching covariance such discrepancy results in an over-optimistic bound for non-Gaussian data.
8 Conclusion
In this paper, we extend a type of sharp uniform convergence guarantee proven for the square loss in Zhou et al. (2021) to any square-root Lipschitz loss. Uniform convergence with square-root Lipschitz loss is an important tool because the appropriate loss to study interpolation learning is usually square-root Lipschitz instead of Lipschitz. Compared to the prior work of Zhou al. 2022, our view significantly simplify the assumptions to establish optimistic rate. Since we don't ton't need to explicitly compute the Moreau envelope for each application, our framework easily leads to many novel benign overfitting results, including low-rank matrix sensing.
In the applications to phase retrieval and ReLU, we identify the appropriate loss function ʃ and our norm calculation overcomes the challenge that f is non-convex and so CGMT cannot be di- rectly applied. Furthermore, explore new extensions of the uniform convergence technique to study single-index neural networks and suggest a promising research direction to understand the generalization of neural networks. Finally, we argue that Gaussian universality cannot always be taken for granted by analyzing a model where only the weighted square loss enjoys an optimistic rate. Our results highlight the importance of tail concentration and shed new lights on the necessary conditions for universality. An important future direction is to extend optimistic rate beyond Gaussian data, possibly through worst-case Rademacher complexity. Understanding the performance of more practical algorithms in phase retrieval and deriving the necessary and sufficient conditions for benign overfitting in matrix sensing are also interesting problems.
Acknowledgements. F.K. was supported in part by NSF award CCF- NSF award IIS- 1908774, and N. Anari's Sloan Research Fellowship.
References
Andoni, Alexandr, Daniel Hsu, Kevin Shi, and Xiaorui Sun (2017). "Correspondence retrieval." Conference on Learning Theory. PMLR, pp. 105-126.
Anthony, Martin, Peter L. Bartlett, et al. (1999). Neural network learning: Theoretical foundations.
Vol. 9. cambridge university press Cambridge.
Auer, Peter, Mark Herbster, and Manfred KK Warmuth (1995). "Exponentially many local minima for single neurons." Advances in neural information processing systems 8.
Bandeira, Afonso S. (2016). "Ten Lectures and Forty-Two Open Problems in the Mathematics of
Data Science." Lecture notes, MIT. URL: https: : / people math ethz. c abandeira/ TenLecturesForty www.etyyyoooooeeemmm pdf.
Barbier, Jean, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zıleorováá (2019). "Optimal errors and phase transitions in high-dimensional generalized linear models." " Proceedings of the National Academy of Sciences 116. pp. 5451-5460.
Bartlett, Peter L. (1996). "For valid generalization the size of the weights is more important than the size of the network." Advances in neural information processing systems 9. Bartlett, Peter L., Nick Harvey, Christopher Liaw, and Abbas Mehrabian (2019). "Nearly- tiggh VC-dimension and pseudodimension bounds for piecewise linear neural networks." " The Journal of Machine Learning Research 20.1, pp. 2285-2301
Bartlett, 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. Bauschke, Heinz. H, Patrick I. Combettes, et al. (2011). Convex analysis and monotone operator theory in Hilbert spaces. Vol. 408. Springer.
10

---

Bietti, Alberto, Joan Bruna, Clayton Sanford, and Min Jae Song (2022). "Learning single-inde index models with shallow neural networks." arXiv preprint arXiv:2210.15633
Blumer, Anselm, Andrzej Ehrenfeucht, David Henry Haussler, and Manfred Klaus Warmuth (1989). "Learnability and the Sapnik-Chervonenke dimension." Journal of the ACM 36 (4), pp. 929-965.
Boyd, Stephen, Stephen P Boyd, and Lieven Vandenberghe (2004). Convex optimization. Cambridge University Press.
Candes, Emmanuel J, Xiaodong Li, and Mahdi Soltanolkotabi (2015). "Phase retrieval via Wirtinger
flow: Theory and algorithms." IEEE Transactions on Information Theory 61.4, pp. 1985-2007. Candès, Emmanuel J and Benjamin Recht (2009). "Exact matrix completion via convex optimization." Foundations of Computational mathematics 9.6, pp. 717-772.
Diakonikolas, Ilias, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi (2020). "Approximation schemes for relu regression." Conference on learning theory. PMLR, pp. 1452-1485.
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. guarantees for low-rank matrix reconstruction." Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, pp. 315-340.
Foygel, Rina and Nathan Srebro 1). "Concentration-baas
Goel, Surbhi, Varun Kanade, Adam Klivans, and Justin Thaler (2017). "Reliably learning the relu in polynomial time." Conference on Learning Theory. PMLR, pp. 1004-1042.
Goel, Surbhi, Sushrut Karmalkar, and Adam Klivans (2019). "Time/accuracy tradeoffss for learning a
relu with respect to gaussian marginals." Advances in neural information processing systems 32. Goldt, Sebastian, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka 7de- borova (2020). "The gaussian equivalence of generative models for learning with shallow neural networks." arXiv:2006. /4709.
Gordon, Yehoram (1985). "Some inequalities for Gaussian processes and applications." Israel Journal of Mathematics 50.4. pp. 265-289,
Gordon, Yehoram (1988). "On Milman's inequality and random subspaces which escape through a mesh in R"." Geometric Aspects of Functional Analysis. Vol. 1317. Lecture Notes in Mathematics. Springer, pp. 84-106.
Gunasekar, Suriya, Jason Lee, Daniel Soudry, and Nathan Srebro (2018). "Characterizing implicit bias in terms of optimization geometry." International Conference on Machine Learning. PMLR, pp. 1832-1841.
Gunasekar, Suriya, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro (2017). "Implicit Regularization in Matrix Factorization." Advances in Neural Information Processing Systems.
Han, Qiyang and Yandi Shen (2022). "Universality of regularized regression estimators in high
dimensions." arXiv: 2206 07936.
Hu, Hong and Yue M. Lu (2023). "Universality Laws for High-Dimension Learning With Random Features." " IEEE Transactions on Information Theory 69.3, pp. 1932-1964.
Ji, Ziwei and Matus Telgarsky (2019). "The implicit bias of gradient descent on nonseparable data." Conference on Learning Theory, pp. 1772-1798.
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 P Processing Systems. arXiv: 2106. 09276..
Li, Xiaodong and Vladislav Voroninski (2013). "Sparse signal recovery from quadratic measurements via convex programming." SIAM Journal on Mathematical Analysis 45.5, pp. 3019-3033. Luo, Wangyu, Wael Alghamdi, and Yue M Lu (2019). "Optimal spectral initialization for signal recovery with applications to phase retrieval." IEEE Transactions Signal Processing 67.9, pp. 2347-2356.
Maillard, Antoine, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová (2020). "Phase retrieval in high dimensions: Statistical and computational phase transitions." " Advances in Neural Information Processing Systems 33, pp. 1 11071-11082
Mei, Song and Andrea Montanari (2022). "The generalization error of random features regres- sion: Precise asymptoties and the double descent curve." Communications on Pure and Applied Mathematics 75.4, pp. 667-766
Mendelson, Shahar ().17). "Extending the scope of the small-ball method." arXiv: 1709. 00843. Misiakiewicz, Theodor (2022). "Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression." arXiv:2204.10422
11

---

Mondelli, Marco and Andrea Montanari (2018). "Fundamental limits of weak recovery with applica- tions to phase retrieval." Conference On Learning Theory. PMLR. pp. 1445-1450.
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.
Nagarajan, Vaishnavh and J. Zico Kolter (2019). "Uniform convergence may be unable to explain generalization in deep learning." Advances in Neural Information Processing Systems. arXiv: 1902. 1902.04742. 04742.
Negrea, Jeffrey, Gintare Karolina Dziugaite, and Daniel M. Roy (2020). "In Defense of Uniform Convergence: Generalization via derandomization with an application interpolating predictors." International Conference on Machine Learning. arXiv: 1912. 04265.
Netrapalli, Praneeth, Prateek Jain, and Sujay Sanghavi (2013). "Phase retrieval using alternating
minimization." " Advances in Neural Information Processing Systems 26.
Panchenko, Dmitry (2002). "Some Extensions of an Inequality of Vapnik and Chervonenkis." Elec-
Ironic Communications in Probability 7. pp. 55-65. arXiv: 0405342.
Panchenko, Dmitry (2003). "Symmettization approach concentration inequalities for empirical processes." The Annals of Probability 31.4, pp. 2068220888
Recht, Benjamin, Maryam Fazel, and Pablo A Parrilo (2010). "Guaranteed munimum-rannh solutions of linear matrix equations via nuclear norm minimization." SIAM review 52.3, pp. 471-501. Rockafellar, R Tyrrell (1970). Convex analysis. Vol. 18. Princeton university press. 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: 2201. 11489.
Song, Min Jae, Ilias Zadik, and Joan Bruna (2021). "On the cryptographic hardness of learning single periodic neurons." Advances in neural information processing systems 34, pp. 29602-29615.
Soudry, Daniel. Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro (2018). "The implicit bias of gradient descent separable data." Journal of Machine Learning Research 19, pp. 2822-2878.
Srebro, Nathan and Adi Shraibman (2005). "Rank, trace-norm and max-norm." International Confer-
ence on Computational Learning Theory, pp. 545-560. Srebro, Nathan, Karthik Sridharan, and Ambuj Tewari (2010). "Optimistic Rates for Learning with Smooth Loss." " Xiv: 1009.3886.
Stojnic, Mihailo (2013). "A framework characterize performance of LASSO algorithms." arXiv: 1303. 7291.
Sun, Ju, Qing Qu, and John Wright (2018). "A geometric analysis of phase retrieval." " Foundations of Computational Mathematics 18, pp. 1131-1 1911--198 198.
Thrampoulidis. Christos, Samet Oymak, and Babak Hassibi (2014). "The Gaussian min-max theorem in the presence of convexity." arXiv: 1408. 4837.
Thrampoulidis, Christos, Samet Oymak, and Babak Hassibi (2015). "Regularized linear regression: A precise analysis of the estimation error." Conference on Learning Theory. Vapnik, Vladimir (1982). Estimation of dependences based on empirical data. Springer Science & Business Media.
Vershynin, Roman (2010). "Introduction to the non-asymptotic analysis of random matrices." arXiv preprint arXiv:1011.301
Vershynin, Roman (2018). High-dimensional probubility: 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 of noisy data." arXiv: 2111, 05987.
Zhou, Lijia, Frederic Koehler, Pragya Sur, Danica J. Sutherland, and Nathan Srebro (2022). "A Non-Asymptotie Moreau Envelope Theory for High- figgh-Dimesiionl Generalized Linear Models." Advances in Neural Information Processing Systems. arXiv: 2210. 12082.
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.
12

---

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

---

A Organization of the Appendices
In the Appendix, we give proofs of all results from the main text. In Appendix B, we study properties of square-root-Lipschitz functions and introduce some technical tools that we use throughout the appendix. Appendix C, we prove our main uniform convergence guarantee (Theorem and the more general version Theorem 6). In Appendix D, we obtain bounds on the minimal norm required to interpolate in the settings studied in section 5. In Appendix E, we provide details on the counterexample to Gaussian universality described in section 7.
B Preliminaries
B.1 Properties of Square-root Lipschitz Loss
In this section, we prove that square-root Lipschitzness can be equivalently characterized by relationship between a function and its Moreau envelope, which can be used to establish uniform convergence results based the recent work of Zhou et al. 2022. We formally define Lipschitz functions and Moreau envelope below.
Definition 1. A function R + R M M-Lipschitz if for all x, y in IR,
(fx=) f(w)] S M x - yl-
(33)
Definition 2. The Moreau envelope a function f R + associated with smoothing parameter A E R4 is defined as
(x(x) = inf f(v) + X(u - =)² yEB
(34)
Though we define Lipschitz functions and Moreau envelope for univariate functions from to R above, we can easily extend definitions and 2 to loss functions f: R xxy - R or f Rxxxx θ - R.
We say a function f IR x y + M -ipisschiiz if for any y E and ő1. U2 R, we have
|f v) f(2 v)1 < M (ū 92)
Similarly, we say a function f x y x θ + R is M M-Lipschitz if for any E V.O E and 91. 02 E R, we have
( 0) f(0 y, 0)1 v M و j2l
We can also define the Moreau envelope function R
by
fx = inf fu, 3) X(u 9)
and the Moreau envelope of a function f RR y + R is defined
fx y. 0) == inf f y. 0) + X(u 0) HER
The proof of all results in this section can be straightforwardly extended to these settings. For simplicity, we ignore the additional arguments in y and @ in this section.
The Moreau envelope is usually viewed as a smooth approximation to the original function f; its minimizer is known as the proximal operator. It plays an important role in convex analysis (see e.g. Boyd et al. 2004; Bauschke, Combettes, et al. 20 Rockafellar 1970), but is also useful and well-defined when f is nonconvex. The canonical example of a /H- (F--square-root--ipsehhe function f(x = Hx? for which we can easily check
fx(x)
X H f(z)
In proposition I below, we show that the condition fx 2 X s is exactly equivalent to / II V--quurre- Lishhhisschsseeess
Proposition 1. A function f IR- + R is non-negative and / Hssqparr-rroo---ipschhh if and only if for any x E RR and X 2 0, it holds that
X
fx(x) 2 A f(x).
(35)
14

---

Proof. Suppose that equation (35) holds, then by taking À = 0 and the definition in equation (2), we see that ff must be non non-negative. For an non- -ongetvteeee function f. we observe for any z E R, it holds that
A
AAA O, fx(x)
A H f(x)
X
O, fx(x)
A H {(x
since fA 0
A 1 fx(x) 2 fx)
inf
ASD
A
X+ H
inf
inf yER
f(y) + A1y x) 2 f(x)
by equation (2)
XsO
À
H
inf inf
11 지
((y) + (A+ Hy - x)² 2 f(x)
A
Hf(w) (y xz)2
inf f()) + Hy ))²² + 2/ x²2 PER
x32 2 f(x)
by x
Ay R. (vf(y) V H y z1)² f(x)
VvER Hly x 2 ((z)) Vf(y
since f 2 0.
Therefore, f must be v H square-root-l.ppshheee then the above implies that (2) must hold and we are done.
as well. Conversely, if f is non- non-negative and
Interestingly, there is a similar equivalent characterization for Lipschitz functions as well.
Proposition 2. function f: IR + M -Lisschitzz if and only if for any x E R and X 0, it holds that
M
fx(x) 2 f(z)
(36)
4X
Proof. Observe that for any x E R, it holds that
M
<Y 0, fxxx) 2 [xx
4X
M
inf (xx 2 (xx)
ASO
4X
inf f()) + A(y xz)² + M
2 ((x)
by equation (2)
4X
M
inf (v) + Mly - x f(x)
by x- 21y
VER
x
Vy R. Mly x f()) f(y)
and we done.
Finally, we show that any smooth loss is gquare-root-Lipschii Therefore, the class of square-root- Lipschitz losses is more general than the class of smooth losses studied in Srebro et al. 2010. Definition 3. A twice differentiable' function f : IR + I is H-smooth if for all x in IR [f"()) < H.
The following result is similar Lemma 2.1 in Srebro et al. 2010:
Proposition 3. Let f IR + TR be a H-smooth and non-negative function. Then for any x. E IR, it
holds that
[f(()) f(H)
Therefore, VI is / Hpp--ipsehite.
'The definition of smoothness can be stated without twice differentiability. by instead requiring the gradient be Lipschitz. We make this assumption here simply for convenience.
15

---

Proof. Since f is H-smooth and non-negative, by Taylor's ' theorem, for any E R, we have
5 f(w)
f(x) + (v) 1) fa)
(y xx)²
< ((x) + (v) x) + H
2 x)²
where [min(r, y), max(2, v)]. Setting y = (x) is Lipschitz, we observe that for any x E
yields the desired bound. To show that vf
((())
f(z)
S HH/2
dx
2VT(x)
and so apply Taylor's theorem again to show that
Ivf(2) Vf(v)l S H/2 yl
which is the desired definition.
B.2 Properties of Gaussian Distribution
We will make use of the following results without proof.
Gaussian Minimax Theorem. Our proof of Theoree and will closely follow prior works that apply Gaussian Minimax Theorem (GMT) to uniform convergence (Koehler et al. 2021; Zhou et al. 2021; Zhou et 2022; Wang al. 2021; Donhauser et al. 2022). The following result is Theorem of Thrampoulidis et al. 2015 (see also Theorem in the same reference), As explained there, it is consequence of the main result Gordon (1985), known as Gordon's Theorem.
Theorem 7 (Thrampoulidis al. 2015; Gordon 1985). Let Z n be a matrix with i.i.d. (O, 1) entries and suppose G ~ (O, In) and H ~ (0, Ia) are independent of Z and each other. Let Su be compact sets and vé Sw Sn + R be an arbitrary continuous function. Define the Primary Optimization (PO) problem
O(Z)
min max(u, Zw> + (ww u) weSw aES,
(37)
and the Auxiliary Optimization (AO) problem
(G H)
min max w wES.
| u) + ||ull w) + (ww u).
(38)
Under these assumptions, Pr( < 2
I c) for any c R.
Furthermore, if we suppose that Sw Sn are conver sets and (bw,, u) is convex in and concave in then Pr( > c) S
2 c).
GMT is an extremely useful tool because it allows us to convert problem involving random matrix into problem involving only two random vectors. our analysis, we will make use of slightly more general version of Theorem 7, introduced by Koehler et al. (2021), to include additional variables which only affect the deterministic term in the minmax problem.
Theorem 8 (Variant of GMT). Let Z x d be matrix with i.id. (0001) entries and suppose G ~ (0, In) and H ~ (0, Ia) are independent of Z and each other. Let Sw, Sy be compact sets in Rdd x Rdd and R x Ran respectively, and let th Sw x Sy - R be arhitrary continuous function. Define the Primary Optimization (PO) problem
((Z)
max (u, Zw) + (((w, w'), (u, (w.,")) (u,0")ESv
min
(39)
and the Auxiliary Optimization (AO) problem
(G, min (w.w
|| |I]ll((,,)) u) + ||l||2 w) ((w,, w (u,
(40)
(u,
Under these assumptions, Pr c) < 2Pr(o S 2c) for o any R.
16

---

Theorem 8 requires Sw and Su to be compact. However, we can usually get around the compactness requirement by truncation argument.
Lemma 1 (Zhou et al. 2022, Lemma 6). Let f: IR 7 R be an arbitrary function and S = { E R
||ا|| S r), then for any set K. it holds that
lim sup T-+00
[(w) sup f(w). wek
(41)
If f is random vuntio,, then.for any t & R
Pr
sup f(w) >1)===)+= WEX
lim Pr mupo0
sup wEKnss
f(w) > >t) )
(42)
Lemma (Zhou et al. 2022, Lemma 7). Let K. be a compact set and f.g 9 be continuous real-valued functions on RR Then it holds that
lim sup inf Xf(w) + g(w) 1 wek OSASr
sup wEK:f(w)20
g(w).
(43)
If f and g are random functions, then for any t E R
lim Pr sup inf Xf(w) g(w) 21)
Pr
sup (()):
(ww) 21
(44)
1-000
wweK OSASr
Concentration inequalities. Let Cin (A) denote the minimum singular value of arbitrary matrix A, and max the maximum singular value. We use ||Al| = max (A) to denote the operator norm of matrix A. The following concentration results for Gaussian vector and matrix are standard.
Lemma (Special case of Theorem 3.1.1 of Vershynin 2018). Suppose that Z -N(00, In). Then
Pr[ vn 2 t) < 4e 14/4
(45)
Lemma 4 (Koehler et al. 2021, Lemma 10). For any covariance matrix E. and H ~ NNO Ia), with probability at least 8, it holds that
| | H
log(4/8)
(46)
Tr(3)
R(E)
and
| - log(4/6) Tr(
(47)
Therefore, provided that R(E) 2 log 1og(4/8),, it holds that
|C || ) S log(4/))
Tr(E²) Tr(E)
(48)
Theorem 9 (Vershynin 2010, Corollary 5.35). Let N E N. Let A Nx be random matrix
with entries i..dd (0, 1). Then for any t > 0, holds with probability at least 1 - 2 exp(-t²/1 that
VN Vn - / S amin (min(A) (A) < m S VN + Vn+L.
(49)
Conditional Distribution of Gaussian. To handle arbitrary multi-index conditional distributions of y given by assumption (B), we will apply a conditioning argument. After conditioning on W and &. the response is no longer random. Importantly, the conditional distribution of x remains Gaussian (though with different mean and covariance) and so we can still apply GMT. In the lemma is a random matrix with i..d. N/ 1) entries and X //
below, Z E aa
Lemma 5 (Zhou et al. 2022, Lemma 4). Fix any integer ls d and any ie vectors wi, ...... w in Bd such that 11/2 .... 22 are orthonormal. Denoting
k
P la Σ
/2,12113 (F
(50)
1=1
the distribution of X conditional on Xwi M,,,. Xw m is the same as that of
Σ (Ew;)² + ZP22122
(51)
17

---

B.3 "apnik-Chervonenkis (VC) theory
By the conditioning step mentioned above, we will separate x into diw-eeensional component W'x x and the independent component Q" r. Concentration results for the wwwdiimesioonl compo- nent can be easily established using VC theory. As mentioned in Zhou et al. 2022, dinddneniional concentration can be established using alternative results (e.g., Vapnik 1982; Panchenko 2002; Panchenko 2003; Mendelson 2017).
Recall the following definition of VC-dimension from Shalev-Shwartz and Ben-David (2014). Definition Let H. be a class of functions from X' {0, 1] and let C {ci, Cm C X. The restriction of H to C is
Hc ((h(c)) h((m))
E H)-
hypothesis class H shatters finite set C X' if Hcl = 2|0 The VC-dimension of H is the maximal size of set that can be shattered by H. If H. can shatter sets of arbitrary large size, we say H has infinite VC-dimension.
Also, we have the following well-known result for the class of nonhomogenous halfspaces in Rd (Theorem 9.3 of Shalev-Shwarzz and Ben-David (2014)), and the result on VC-dimension of the union of two hypothesis classes (Lemma 3.2.3 of Blumer et al. (1989)):
Theorem 10. The class {x + signl (w, (,w, z) + b) w E RR b E IR} has VC-dimension +
Theorem 11. Let H hypothesis classes of finite VC-dimension d 2 1. Let H2 (max(h1, h2): hr, h2 E H) and Hss == (min hi, h2 E H}- Then, both the VC-dimension of Hz and the VC-dimension of Hs O(d).
By combining Theorem and 11, we can easily verify the VC assumption in Corollary 1 for the phase retrieval loss (Ū, y) (lol 3) Similar results be proven for ReLU regression. To verify the VC assumption for single-index neural nets in Corollary 2, we can use the following result (equation 2 of Bartlett et al. (2019)):
Theorem 12. The VC-dimension of neural network with piecewise linear activation function, W parameters, and layers has VC-dimension O(W L log W).
We can easily establish low-dimensional concentration due to the following result: Theorem 13 (Vapnik 1982, Special case of Assertion in Chapter 7.8; see also Theorem 7.6). Suppose that the loss function Z x θ + Rzo satisfies
(i) for every 0 E O the function 1(:0) measurable with respect the first argument
(ii) the class of functions (2 ((((2,0) > (0,t) x has VC-dimension most h
and the distribution D over Z satisfies for every 0 e
E2-D (1z, 0)4/2/4
S.
(52)
E [12, 0)]
then for any n > h with probability at least 8 over the choice of (zı,..., ~ DD, it holds uniformly over all E that
1
h(log(2n/h)) + log(12/6)
1(2,. 2 1 8TV
EewD(((2,0)
(53)
1=1
C Proof of Theorem
It is clear that Theorem 1 is special case of Theorem 6. Therefore, we will prove the more general result here.
Notation. Following the tradition in statistics, we denote X = (æ1, ..., T E xxd as the design matrix. In the proof section, we slightly abuse the notation of 77, to mean Xw; and & to mean the n-dimensional random vector whose i-th component satisfies
g(h,i.... .... M,. Ex). We will write X 1// where Z is random matrix with i..dd standard normal entries if 0.
18

---

Throughout this section, we can first assume f 0 in Assumption (A) without loss of generality because if we define f' IR x
x θ - R by
fli. = f(ū + (),,;))))
(54)
then by definition, it holds that
f((w((), y, 0) =((w()),== v.
and so we can apply the theory on f first and then translate to the problem on f. Similarly, we can also assume w E are orthonormal without loss of generality. This is because we can denote W E Raxk by W = ..., w7l and let W = -W(W7 -WWWEWW)"1/ By definition, it holds that Wn are orthonormal.
WTEW = I and the columns of W [wi ... Wil satisfy 2'/2wf,... ..... /'/2ug If we define 1 + by
((...... Th. <) a(n nW EW) 1/2 + p W,E),
(55)
then y - (== W,& E) and so we can apply the theory on g.
We will write the generalization problem Primary Optimization problem in Theorem 8. For generality, we will let be any deterministic function and then choose it in the end.
Lemma 6. Fix an arbitrury set θ C RP and let O - R be any deterministic and continuous function. Consider dataset (X, Y) drawn i..dd from the duta distribution 'D according to (A) and (B) with μ = 0 and orthonormal y 11/2 w 21/2w Then conditioned on Xwi = -T2, Xw?. = 7k
and 5. if we define
sup (w,u,0) x uo /2
inf Z.) + (u, 0, A M. Tkk 5)
(56)
XE
where P is defined in (50) and 2A is a deterministic and continuous functtonn given by
(u, A /,A/ m..... The E) = F(0)
Σ
f(us, g(m..s Me.i: E:),
n
(57)
k +
(A,
Σ
n m2'ww)) w(0) - -w),
then it holds that for any E R, we have
Pr sup F(0) - i.(0) > 1 [, mc.)) (.........)))) = Pr( > 1).
(58)
PEO
Proof. By introducing a variable u = Xww(f), we have
n
sup F(0) - L(() sup F(B) 8Ee
((w)())
8c0 n
sup inf (A, Xu(() - u) + F(0) 1 Σ
flu, y4, O).
6EB, AER"
Conditioned on Xwi = 11: Xw nhs and &. the above is only random in X by our multi-index
model assumption on y. By Lemma 5, the above is equal in law to
sup inf (A,
w(O) - u) F(() n (EE;)) + /P
1 Σ
(1, Ni. 0)
R AER
1=1
sup inf (A, (2PI1/2) w(I)) + ((u, 0. A.A.m ...... Al....... -k.E)
dee,uER" AER
sup (u.,,0))R"* XR" x w= /2
inf (A, Zw) + (u, 0, /.Amm...... m.... Tk. à)
AeR=
The function & is continuous because we require F, and to be continuous in the definitions.
19

---

Next, we are ready to apply Gaussian Minimax Theorem. Although the domains in (56) are not compact, we can use the truncation lemmas 1 and 2 in Appendix B.
Lemma 7. In the same setting as Lemma 6, define the auxiliary problem as
sup (u.0)ER"x@ (H,PE /1 w0) l+ -. (w(0), (00)
F(O)
(us. Vi, 0)
(59)
72 1=1
then for any E R. it holds that
Pr sup F(0) -000-((0 [(0) > -[(0) OEX
22Pr( 2 21.
(60)
where the randomness in the second probability is taken over G, H. m,, and &.
( and ||w||2 + ||ul22+ ||112 < r). The set S, is bounded by definition and closed by the continuity of w. Hence, it is compact. Next, denote the truncated problems:
Proof. Denote S, [w,, u. 0) & x R
θ
4 = sup inf (A, Zw) bu, 0, 71 Thk E) (w.,,))E.. AER
(61)
r.a sup inf (A, Ew) + vb 0, M..... Mis E)-
(62)
(w.,,))S, ||l|lS
By definition, we have 4, Dr.s and Pr(#, > S Pr(2... t).
The corresponding auxiliary problems are V Vr. = sup inf [A) + |1ll A) + (u, A mn...,,7: E)
(W.,,)ES, J
sup inf (w,,, Alllasa
(A + (A,1ww|lGG +
n (w)()), Ewu)) u)
F(0) n
flu, I(M Thiss E)
k
sup inf (w,,,))ES, 0SA5.
(1H, |10l1:G G +
Σ (w)(. Ewe")
1m1
F(0) n
fluis ((n Ma.ss E,),
and the limit of -> oct
n F(0)
sup
f(us, ((.............................. mk. E))
(w.u.))ES. (H ||| + (o)
n
By definition, it holds that v < and so
Pr(V, 2 S SP((V 2).
Thus, it holds that
Pr(Φ > t) lim Pr(0, t)
by Lemma
r-000
< lim lim Pr( >
1-000 --330
< 2 lim lim Pr(U,,* 1)
by Theorem 8
r-+00 8-100
2 lim Pr(V, 2
by Lemma 2
< 2 Pr( t).
The proof concludes by applying Lemma 6 and the tower law.
20

---

The following two simple lemmas will be useful to analyze the auxiliary problem.
Lemma 8. For a, b, H > O, we have
À b= (Vb -Vb--HHH))
sup A20
Aa +
11 +
Proof.
Observe that
À
H H + X
sup
da +
b-
inf A20
Aa +
A20
H + X
Define f(A) λa + H+* then
Hb
Hb
(()) = a
0 - (H+ -
(H + 2)2
Hbb H X S
Hb H
Since require À 2 0, only need consider whether
Hh H
0
2 Ha. If
b < Ha, the infimum attained Otherwise, the infimum is attained X which point
V
Hb
H, at
π(x* 2v Ha.
Plugging in, we see that the expression equivalent (vb H in both cases.
Lemma 9, For a, b 2 0, we have
b A
sup A20
Aa
-4ab
Proof.
Define f(A) -aa 3.2 then
b a
((() a 20
X²
and so in the domain À 2 0, the optimum is attained at X = Vbaa at which point f(X*) ab.
We are now ready to analyze the auxiliary problem.
Lemma 10. In the same setting as Lemma 6, assume for every 8 > 0
(A) Cs Rd > [0, co] is continuous function such that with probability at least 8/4 over H ~ ((O. uniformly over all w E IRd, we have that
12 w) S CC(ww)
(63)
(B) es is a positive real number such that with probubility at least 5/4 over ((ā;, (i);;)))) drawn i..dd from D, it holds uniformly over all 0 E θ that
Σ 2.) 0)
1
E ((
(64)
1 I+
where the distribution D over (ā. 9) given by
t ~ NO IRt1), E~ Dg,
ÿ = Tx.
and the mapping Φ ad + R is defined as
Φ(w) ((w, Ewf), .... (w. Ewfi), /2
21

---

Then the following is true:
(i) suppose for some choice of Ma that is continuous in O, it holds for every E y and 0 E θ f is Mo-Lipschitz with respect to the first argument, then with probability least uniformly over all 0 E O we have
L(0) (1+ [10)+
Moy Co(w(())²
(65)
(i) suppose for some choice of Hg that is continuous in 0, it holds for every y and 0 O I is non-negative and vf is / /pg-lipschitz with respect to the first argument, then with probability at least 1 6, uniformly over all O O we have
(v (HCssw((0)) n
((0) & (1 (1+
(66)
Proof.
First, let's simplify the auxiliary problem (59), Changing variables to subtract the quantity |1 + Σ (w((), Ewi mi from each the former us we have that
G₁ PX
(tt ui + Gi 1 (0()
k
1 Σ1 1=1
V
sup (u.0)ER"*x0 x (HIP
F(O)
Σ 1=1
(wi(f), Ewi)), Vi. 0
and separating the optimization problem and 8, we obtain
V
sup F(0) AEe
1
inf MER"
Σs f ii lu+G,
PE 2
w() + Σ (w()), Ewe )wi)) mn Us. 0
72
TullaS(H,P2) (())
Next, we will lower bound the infimum term by weak duality to obtain upper bound on V::
Us + G; (0) + (w))), Ewi Mn, Us.
inf WER":
||x (H, (()) i=1
inf sup X(1 - PH, 2()))2))
"ER" X20
+
f E
u; + +G pL /201/22000 wo (0)
+ Σ (w))), m, Mo. 0
1=1
2 sup
- -/2 1/2 PH, 2())
A20
k +
+ inf
Σ f
ui + G. 2 |
Σ
(w))), v1,0 + A11
HER
1=1
1=1
ssup
-X PH, 20))
X
+
inf f 44 GG | + >
Lww m.. v6. Au?
1=1
1=1
sup -X PH, 20)) A
Σn ʃa (G.
Σ (w)(0), Ewet Euo Suttmn
Suppose that for every E y and 0 E O, f is Mo-Lipschitz with respect to the first argument, then by Proposition 2, the above can be further lower bounded by the following quantity:
sup- 122H 20)) nM A
(w)()) Ewi m. + p G., ys,
+
4A
22

---

On the other hand, suppose that for every E y and 0 E e. f is non-negative and vʃ is Ho- Lipschitz with respect the first argument, then by Proposition the above can be further lower bounded by:
A He +
(w (0), mm + pP2/2w(0)) Gi, Vi, v }
sup X
+
Notice that if we write ž; = (m.. M7,6 G.). then (0t, ys) are independent with distribution exactly equal to D. Moreover, we have
k (w)) Ewi + // | Gi, (h. 0) = [((((w(0)), v.). vc,0)
and it is easy to see that the joint distribution of (((ww())) ã) y) with (ã, v) D is exactly the same as ((w(0), x), y) with (z, v) ~ D. As a result, we have that
E B(w ((d((((((()w)))))))))))))))))))) 3), v. 0)] L(0).
By our assumption (63), (64) and a union bound, we have with probability at least 8/2
1 w(0)) - Cs(w(())
1
Σ (w) Mnj /2 wo (0) |
Gi, vo. 0 > 1+ E8
((0).
Therefore, if f is MggLipschitz, then by by Lemma we have
S sup F(0) sup -X Co(w(0))² M2
L())
6EB
X20
n
1 66
sup F(0) + M3 Co()
L(0)
6EB
1+66
Consequently, by taking F(0) 1 (() Mo
Cs Ca( and Lemma 7, have shown that
Ites
a
with probability at least 6, we have
L(O) S L(0) + Moy Co(w(O))
sup F(0) (() 0 ØEK
1
If VI is Hoo-Lipschiie then by Lemma 8
sup - Ca(u(O))2
V S sup F(0)-
Ho + +11 L(l)
BEK
A20
L(()
HoCs(w(O)))
sup F(Ø)
BER
1 1+65
Consequently, by taking F(O)=
L(0)
(w)))²
and Lemma 7, we have shown that
1tts
with probability at least - 8, we have
sup F(0) - L()) S O. eEk
Rearranging, either we have
L(Ø)
HaC HoCo(w(O0)2
Ha HoCo(w(O))
<0 ((0) (1 E8)
1+ Es
23

---

or we have
L(O)
HoCb(w(())
(1
11110) |+ts
L(0)
HcCs(w((1)
2
20-
S L(0)
1 68
n
n
(VL1O) +1
(w
L(0) - (6)
In either case, the desired bound holds.
Finally, we are ready to prove Theorem 6. the version below, we also provide uniform convergence guarantee (with sharp constant) for Lipschitz loss.
Theorem 14. Suppose that assumptions (A), (B), (E) and (F) hold. For any å E (0, let Cs R - [0, oo] be continuous function such that with probability at least 1 8/4 over x N E),
uniformly over all I E O
(w(00, Qr, S Cs(w(()).
(67)
Then holds that
(i) for each E @ and y E v, f is Mg-Lipschitz with respect to the first argument and Mg is continuous in 9, then with probability least 1 6, it holds that uniformly over all 0 θ,
we have
(1 (1- - (()) + May Co(w((0)²
(68)
(i) for each 0 E θ and y E y, f is non-negative and vJ is the first argument, and Hg is contimuous O, then with probability at least 1 it holds that uniformly over all 0 O we have
with respect to
(1 L(0) = (VELO)- + +V
Ho Ca(w(())2
(69)
n
where e =o O (TV log(n//))+oog
Proof. We apply the reduction argument at the beginning of the appendix. Given D that satisfies assumptions (A) and (B), define [w] ..., Tg W WWWTEW)-12 and f. Å as in (54) and (55). For {( y:) 1 sampled independently from D, we observe that the joint distribution of (xr+ - pr vi) can also be described by D' as follows:
(A') x ~ E),
(B') y (f mh. E) where Ti (x,, w.))
Indeed, we can check that
===(0TTm 5gg==WWe W.E)
=g((x 11)² (WW22 W.)
0((x 14) W.
Moreover, by construction, we have
2(0) Σ f((w(0), x; -00 1).
L( = E. f(( x;)), v/.
and D' satisfies assumptions (A) and (B) with l = 0 and orthonormal N,1/2 E1/2 and falls into the setting in Lemma 6. We see that being Lipschitz square-root Lipschitz is equivalent to
24

---

being Lipschitz or square-root Lipschitz. It remains to check assumptions (63) and (64) and then apply Lemma 10. Observe that
3-1/2p51/2=>> (T-- 51/2
la - -,-- T - = Q
(70)
and -
To check that (63) holds, observe that /21/2PH, w) has the same distribution as (Qw, x). To check
that (64) holds, will apply Theorem 13. Note that the joint distribution of ((o(w(0)) Z), , ÿ) with
(#, 17 D is exactly the same ((w(0), y) with (z. v) DD' and so
(w)) Ex (f(((O))) 0.00
E=) [olf((u(0)
()))(()(((()) x). 0)]
Therefore, the assumption (E) is equivalent to the hypercontractivity condition in Theorem 13. Note that {(z, v) + ([f((((w(0)) x), v. > $ : (0,t) θ RR subclass {(x,)) H [[f(ww I) + b, y, 8) > f} (w, b, 8) E R
R θ). Therefore, by assumption (F),
can apply Theorem 13 and (64) holds.
D Norm Bounds
The following lemma is version of Lemma 7 of Kochler et al. (2021) and follows straightforwardly from CGMT (Theorem 7), though it requires a slightly different truncation argument compared to the proof Theorem 6. For simplicity, won't repeat the proof here and simply use for applications.
Lemma 11 (Koehler et al. 2021, Lemma 7). Let Z : n x d be a matrix with i...d. N(0, 1) entries and suppose G N00 In) and H (O, Ia) independent Z and each other. Fix arbitrary norm || Il. any covariance matrix E, and any non-random vector & E R", consider the Primary Optimization (PO) problem:
(71)
WER /x!//
and the Auxiliary Optimization (AO) problem:
V =
min "
|w/.
(72)
El1 (2 H.w)
Then for any & E R, it holds that
Pr( > f) < Pr 2 t).
(73)
The next lemma analyzes the AO Lemma 11. Our proof closely follows Lemma 8 of Koehler et al. 2021, but don't 't make assumptions yet allow applications.
Lemma 12. Let 7 d be matrix with i.i.d. (O, 1) entries. Fix any 8 0, covariance matrix
Σ and non-random vector I2, then there exists S log(1/5) with probability at least 1 - 5, holds that
such that
(REE)
R(
| Tr(E)
min WERd
1| < (1 +
(74)
Proof. By a union bound, there exists a constant C > such that the following events oceur together with probability at least 1-8 8/2:
25

---

1. Since (G.E) ~ (0, (1E1)) by the standard Gaussian tail bound Pr([Z) 2 t) I 2e 12/2 we have
KG, v 2 log(32/0)
2. Using subexponential Bernstein's 's inequality (Theorem 288.1 of Vershynin (2018)), requiring n =l(oog(1/))) we have
|GG|2 s
2n
3. Using the first part of Lemma 4, we have
| Tr(2)) 11- log(32/5)
VR(Z)
4. Using the last part of Lemma 4, requiring R(Z) Z log(32/6)2
|
Colo((32/0) Tr(E²)
E H 12 <
Tr(E)
Therefore, by the AM-GM inequality, it holds that
|[G||>>//2/|> Ell2 = ||G||||> w0 112 + |K<|2 - 2(G, 2/112'/2221
- 2m /2 3 + 111112 + 2115 2og (32/6))22 w||2
s 3 + (1+ 2 2log(32/1)
||
To apply lemma 11, we will consider w of the form w
51/22 for some a > 0. Then we have
|S1/=H|1
Th Tr(E)
2 log (32/5)
|G| w|l2 E11 s 3nC log (32/0)
a² +
1 1+
|K
and
log 1og(32/0 (32/0) 0)) v R(E)
(5 H, w/)² /2 H 2 a² Tr(E.)
So suffices to choose a such that
1 (32(88
11E11
a²
Tr(E)
1 C log(32/5)
Tr( 3nC SnClog(32/6) TYEE)
/ /R()))
+ 10g((22
11
Tr(E)
C (lo((32/0)
+ +R(())) R()))
and we are done.
challenge for analyzing the minimal norm to interpolate is that the projection matrix Q is not necessarily an orthogonal projection. However, the following lemma suggests that if Σト = = XQ has high effective rank, then we can let R be the orthogonal projection matrix onto the image of Q and RER is approximately the same D in terms of the quantities that are relevant the norm analysis.
(w:) where /2 / are orthonormal and we let R be the orthogonal projection matrix onto the image of Q. Then holds that rank R) d and
Lemma 13. Consider Q I wf(w
REw; for any 1,..,kk. k.
Moreover, we have QR = R and RQ = Q, and so
1
(RRER) < R(QTEQ) Tr(QTEQ) R(RER)
-2 n
R(Q
R(Q
26

---

Proof. It is obvious that (R) rank(Q) and by the rank-nullity theorem, it suffices to show the nullity of Q k. To this end, we observe that
Qu = 1-
2 w [o))
1 =0
E
1/2 w ( 2/3 wz)²
51/2==
/ w span // wi 2
spant i ..... wk
It is also straightforward to verify that Q² Q and Q" Ew. 0 for L,..., For any E R Re lies in the image of Q and so there exists w such that Ru Qw. Then we can check that
TT REw = (Rwv Ywee)
(Qw, Ew?) (wc, Q" Emet) 0
and
(QR)c = Q(Rv)
= =Q(Qw) = Q²u Qw Rv.
Since the choice of is arbitrary, must the case that REw and QR For any u E Rdd we can check
(RQ)) = R(Qu)) Qu
by the definition of orthogonal projection. Therefore, it must be the case that RQ Q. Finally, use R = QR = =RQ" to show that
Tr(RER) =
=
= =T)("" Tr(Q"'Q(1-
2 TT(QTEQ) V (1)(011)))))(((11 RY²)
k
EQ)
V R(QUEQ)
[ 11- k n
R(QTEQ)
and
TT((ER)3) Tr(ERER)
-TH(IQRQT
-TE((RQT (Q)
S &TR(IQO" (M)(R EQR)) xQ)²
$ TT((Q"EQ)))
Rearranging concludes the proof.
D.1 Phase Retrieval
Theorem 2. Under assumptions (A) and (B), let f R x y - IR be given by f(j = (1ú) - y
with y Rzo- Let Q be the same as in Theorem and Σ =QT Fix any w E Rdd such that
Qwi = and for some E (0, 1), it holds that
(y( < (1+ (w))
(9)
27

---

Then with probability least 8. for some I p log (3) (
+ k n
+ R(2
VR(S+)
holds that
nLy(wt)
min WER": (w, ==
| S ||0fl22 + (1 / Th(E-)-
(10)
Proof. Without loss of generality, we assume that j lies in the span of [Ewi, ,..,, Lug] } because
otherwise we can simply increase k by one. Moreover, we can assume that ( ..... /./2/// orthonormal because otherwise let W -W(WTEW>- and conditioning W (x: j1) is the same as conditioning on W (x 11. By Lemma 5, conditioned
7í
[W (x) ()), W VV (Ji [1]
...
The
the distribution of X is the same
x= 11 + Σ mh ({w,))
where has i..dd standard normal entries. Furthermore, conditioned on W (x (a- ju) and the noise of variable in (which is independent of x), by the multi-index assumption (B), the label y is non-random. Since Qw we have w- =E (w]", Eweyyu and so
&
(w* x) = (wt, .)) + (ww Ywi x- pt).
Therefore, (wi, .r) also becomes non-random after conditioning. We can let / {i E [n]] (w xz) 2 0} and define g E IR. by
E y/ kwr, ifi KW -x)i if &
and & non-random after conditioning. Following the construction discussed in the main text, for any wf E Rd, the predictor w wf + w-t satisfies [w,==)) = Di where
w arg min ||0e||2 ERR4 Xw=
by the definition of g. Hence, we have
min WER (n) (wxx)
||lla S || 1|2 + 11
and it suffices to control || 1|2-
Let R be the orthogonal projection matrix onto the image of Q and we consider of the form Rw to upper bound ||w- 12. By Lemma 13, we know QR R and REw; By the assumption that jr lies in the span of (Ewr, ..., Ewe), we have
142" + (Ew + 2V1/2Q Rw 2/ Rw. Rw..
Since R an orthogonal projection, it holds that | S |1l1 Finally, we observe that the distribution of //2 R the same as 2(RER) and so
w 112 <
min
|
Z(RE
We are now ready to apply Lemma 12 to the covariance RER. We are allowed to replace the dependence on RER by the dependence on Σ by the last two inequalities of Lemma 13. The desired conclusion follows by the observation that ||E|| nLL((wFF and the assumption that Ly(w)) < (1 + (wF))
28

---

D.2 ReLU Regression
The proof of Theorem will closely follow the proof of Theorem
Theorem 3. Under assumptions (A) and (B), let
y IR be the loss defined in (13) with
y = Rzo. Let Q be the same as in Theorem I and Σ = Q² EQ. Fix any (w², b²) E Rd+1 such that
Qu = and some E (0, 1), it holds that
Lg(W0, 1FA) S (1+ (. (/).
(14)
Then with probability least for some e S p - log
J + VR(EL)
B + 7(
holds that
nLy b2) Tr(E=)
min (w.b)ER<+1;
||ll2 S | (1 1
(15)
(+)+)
Proof. We let 7 = {i [m]] 14 > 0} and for any (w#, b4) IRd+1 we define & E R by
& { yı (lof, az) - ba ifie - (ww@ v.) + bF) if
By the definition of g, the predictor (w, b) (w² wt, (P) satisfies ((w, mz) b) y: where
w = arg min ||w]|22-
wER Xw=
Hence, we have
min Vieln (w) *+)
| S ||00fl22 +
||w 112
(( (b)=))
and it suffices to control ||w-112. 1|2-
Similar the proof of Theorem 2, make the simplifying assumption that μ lies in the span of (Ewf,.., .... ]wg} and (E'/2wt,... [//] orthonormal. Conditioned WT(x; p)) and the noise variable in ys, both y and (wa, x.) non-random, and is also non-random. The distribution X is the same as
X 1
Σ
TZ /2
If consider of the form Rw; then have
[ ||2
min WER
|
Z( 19
We ready apply Lemma 12 to the covariance RER. We allowed replace the dependence on RER by the dependence on Σ- by the last two inequalities of Lemma 13. The desired conclusion follows by the observation that ||E1|2 = n 6²) due to the definition (13) and the assumption that L (wF) < (1 + p)L (w+, b²).
D.3 Low-rank Matrix Sensing
Theorem 4. Suppose that di d2 > n, then there exists some
log(32/8)
such that with
1
d,da
probability at least - 8, it holds that
no²
min (A.
XXI|- S
(1
+1++111))
(17)
dl V dz
29

---

Proof. Without loss of generality, we will assume that d1 S d2. We will vectorize the measurement
matrices and estimator Al.... An, E 14 xdl as di...., an Rd and define ||=||~ |X||.. Denote A
[01,... ... anl E guxdids, We define the primary problem &b by
min (A..)
|X||+
min ||=]|++ Anmg
By Lemma 11, it suffices to consider the auxiliary problem
V ==
| - ||]||.
min
We will pick of the form r -aH for some 2 0, which needs to satisfy ai e|| 2 ||a||| ||2 E 12- By a union bound, the following events occur simultaneously with probability at least 8//2:
1. by Lemma 3, it holds that
||]|2 S vn+ + 22 13g(32/6)
|El12 S vn+ 2/ 13g(32/6)
|||| vd1d2 + 2 2vlo0(32/5)
2. Condition on &, we have
[ (G,E) .V(0 1) and so by standard Gaussian tail bound
Pr([Z] > t) S 22/2 12/2
[(,
2 (og(6/60)
|
Then we can use AM-GM incquality to show for sufficiently large n
|| 21 2 - E
=a H 1 + ||E12
20|| (12((E))
log(32/6)
2 log( (16/8)
< <na? |
1+ 2
+ ||E122 + 2//aa |llllllla
n
n
log l32(32/6)
2 1og(16/6)
Sna²|
1 1 1
11E112
n
n
and it suffices let
10g(32/8)
2 log (16/8)
a²2 Rearranging the above inequality, can choose
| 2 na?
H11
+ 10
1
115112.
n
7
1/2
1 10
log(32/8)
n
+ 10
log(32/6)
(1 (1+2/ 2/
1og(32/6)
d,d2
d,
and since H as a matrix can have at most rank d1, by Cauchy-Schward inequality on the singular values of H. we have |||||- S vdn H|| and
di (1 (1 +
no²
||||| = aell H||. < ar
a du H| s (1 (1+0)
+o1
d1
for some S log(32/6) VF||X* because X has rank r.
The desired conclusion follows by the observation that || S
n
dide
30

---

Theorem 5. Fix any E 1). There exist constants C2, > d2 c2d,, n car car(d1 d2), then with probability at least 1 that
0 such that if d1d2 > cin,
x P S
r(11 + d2)
r(d1 + d2)
+
(v
n d1
(18)
X
n
|x
d2
X
Proof. Note that (A, ~ N (0, 12.) and so by the standard Gaussian tail bound Pr( 2 S 2e 1/2 Theorem 9 and union bound, it holds with probability at least 1 6/8 that
KA, XI /2 I|
|| op S vi + d (llog(32/0),
Then it holds that
(*) X 1
X
X"
A|lpp
X 1l
|
op
X op
$ v d1 + ddl + v22 (3200)
+
/2 log(32/0)
x 1|
/ di + doz v (3g((100)
Therefore, we can choose Cs in Theorem by
Cx(X)= = (Vir + V de V 8log(32/)) |||||-
and applying Theorem 1 and Theorem 4, we have (1-c) v Cx(X)
n
Vdi + Vdz + /8ll0(32/0))
2
no² di V d2
VF||X*I1+ (1++e)
n
)
2
d1 V di V d2
d2
8 (3g((2/
r(11 d2) + (1 + 6)
|
+
V
d
d2
+
di V d2
|x
where e the maximum of the two in Theorem and Theorem 4. Finally, recall that
((X)= = o² + 1
Assuming that d S d2, then the above implies that
|| 13
1
2
d
80g(222/))
r(dh + d2)
a²
<11-))
1+
d2
d2
n
|
r(d1 + d2) r(d1 + d2) n
(v
d1
+
n
|X*1|
F
d2
d
and we done.
E
Counterexample to Gaussian Universality
By assumption (G), we can write Djja-k = h(2,))) 2 where 2; ~ N/(0, Id-k). We will denote the matrix Z = [a1, 2n E (d-x), Following the notation in section we will also write X = [X X[a-k] where Xi E Raxk and Xja-x E Rax(d-k), The proofs in this section closely follows the proof of Theorem 6.
31

---

Theorem 15. Consider dataset (X, Y) drawn i.i.d. from the data distribution DD according to (G)
and (H), and fix any f : x y + Rz0 such that vf L-Lipschitz, for any y y. Fix any 8 and suppose there exists Eg and Cg Rd-k [0, oo] such that
(i) with probability at least 1 - 8/2 over (x, Y) and G (O, In). it holds uniformly over all W/p E R and a x R2o that
n f((wya Talk) + (1 - allEys Gz Vi) 2 (1 - (1-c6)Bp) ED
[(w, v)
R
h(za(1)2
h(21))2
(ii) with probability at least 6/2 over 21d-k ~ NO0 (10,, E). ) holds uniformly over all
w/d-k E RRd-k that
(wia-k: 7/a-k) S Ca(w)a-k)
(75)
then with probability at least 1 - 6, it holds uniformly over all w E Rd that
Co(w d-k) 2
[((u,,)),))
s((w)))))))
(1 cB)
(76)
n
h(Ia(a)²
vn
Proof. Note that
(10) ki Fqjda)) = M(Za)K)
(waa- 1/12
and for any f: y x R + R. write
Φ = sup F(w)
f(w, 24), Vi, Falk)
wERd
1=1
sup wER _ER" w=Zw wi-k
F(w)=
f(Wup, maph) + (( Mes zz1k.)
sup WER MER AER
inf
(X,
TΣ 1/2 dd w d-k u) F(w) Σ ((mmp Maaap)) Uis Taja)-
1/2
By the same truncation argument used in Lemma 7, suffices to consider the auxiliary problem:
sup uuR ue
inf [A]| 1/2 2'd w a-n) +
u, A)
AER"
1 + F(w)
Σ n
f((W)k: majke + (x Bcs Falk)
sup inf
( (H, 1/2
ld- up/--) - || =11,)
wERd MER" X20
+ F(w)
f((w)): Eqna) + h(za)))ss Vis zajp.
im
Therefore, it holds that
n
sup WERd R
F(w)
a0 + h(Dg))())s yi, 2qqu)
(H. (H 1/ -
-
1/2
= sup F(w) 1
inf WER
f f(Ww), 2gjk) + (( )u, Bis Tajk).
weRd
(H
1/2 2-
1
x
G -
12
1
32

---

Next, we analyze the infimum term:
n f(1wps Talk) ((zz))))s Mis Felke)
inf
EER
(11 mm +) G
wa 1 111-
((pp h(x0ak)) (ui + / wa allaG.) yc. 2.10)
inf wER (H, m(=))
inf sup A([|u||2 (H, 2:1/2 wajax)
MeiR" A20
+ {((1) + MZz;1k)
[4 + 112 a w uaa+112Gi) yis Talk)
sup inf A(llu|12 (H, x w x)))
A20 HER"
f( + Mzsuu) 14 + 1-- w w waa yis 1.112)
HH, Σ 1/2 1 w7 x)²
=sup- X20
n
A
Σ inf (( + un + ma- Dr U.ER
h( uf.
Now suppose that f takes the form f(0. y. m1)) = د f(). y) for some I square-root Lipschitz f and by union bound, it holds with probability at least 8 that
/// H, xx) s Co(w0jak))
i=1 (( f f(tu)) majk) + || a (11hh 91) (1 E5)B
h(al))2 b f(w.))).))
then the above becomes
-1 1d H1 w) + Σ sup A20
BA(WU)K zajke + || - - (2h( v1)
h( )a
sup -X 1/2 1d-
H, w| + x+1 1
A
1
| jd- wia allb
h(aa))² )2
A20
sup-
-ACo(W)d-s)
(1 e)nTE
h( f(w,))))))
A x+1
A20
2
Co(w)d-k) vn
2n
(1 (1
Ex)E
((w, v))
h(mpp)2
where we apply Lemma 8 in the last step. Then if we take
2
F(w)= = (Va-o)) cs)B
Cs(w)a-k) vn
Ma J(ww at).u)
then we have < O. To summarize, we have shown
(Va- (--==a) Ex)E h(m)))² [(1,,a)).))
Co(w)anu) vn
I(,, Ui) S
h(
which implies
M )2 [((u) 1;), v1)) + Co(wyaa 2
1 Mana) (w, 5 (1 - -s)-
1
11
vn
33

---

Theorem 16. Under assumptions (G) and (H), fix any wiz E R and suppose for some p E (0, (), it holds with probability at least - 6/8
y/s Tikk)
(
y (w m7kh
(1+
(77)
π2
h(Zzjk))
h(
Then with probability at least 8, for some e S p + log (2) holds that
+ (R(Eju->)
nE
min WE VEERAVV (1..(0)))))))
(1+
(78)
Tr(Sja=A)
Proof. Fix any wit E Rt we observe that
min w (ER
min
/ 112 |120)a-
WERV.Vi ae +e) (191a aia =)mu
12 +
min w w ER4 R
|,0aa 112.
-= = (1fE)
Therefore, is enough analyze
min Wia & - k
110/a-1122-
min
wia a ER 5-
Va, 2 =x)= to Fa mO
By introducing the Lagrangian, we have
Yi (w (alk)
+ = min
a & AERR
max
Σn Av
h(
+ 1122//-1:12
A Yt (Wf, Fe11)
2/ ACR
min
max
(A, ZΣ
1/2 ld-k w(d
h(xaae)
+ 1120aa-lle..
1=1
Similarly, the above is only random in Z after conditioning Xi and & and the distribution of Z remains unchanged after conditioning because of the independence. By the same truncation argument as before and CGMT, it suffices to consider the auxiliary problem:
[1aa/ w d=1l22G,
yi (10 salps h(zqua)
min max "ja-xERd-A AER" || H, 1/2 Id-k wid-k)
+
1=1
+ I|w d=2l12
(wo siake 2 h(Zqu))
min
max |Al|2
(H, E w waj-
|| w aa -0la-=112.-----
wIa - XER"
+ I|l d=
and can define
V
min -
11
94 14 *sje)) a(eaje)
( H.
To upper bound v. we consider w of the form a
then we just need
// H112"
2
| G,
(w Foike) h(2z)))
Σ
S a211221
1/11>>// d H
/ H|I
34

---

By union bound, the following occur together with probability at least 1 - 8/2 for some absolute constant C 0:
1. Using the first part of Lemma 4, we have
1 H 2 (=((au)) (1-c log (32/6)
(((I)u-A)
2. Using the last part of Lemma 4, requiring R(E(d-k) Z log (32/6))
2 < C3loo(32/0) | 1d- 11
Tr Tr(S(/8k)
Tr Tr(=)d=k)
3. Using subexponential Bernstein's inequality (Theorem 2.8.1 of Vershynin (2018)), requiring n [[(log((]) (1/5),
G 2
4. Using standard Gaussian tail bound Pr( / 2 1) S 2e 12/2,
we have
1
Gi(y (((A))
Ut (uip:
/
2 1og(32/0)
h(z((k)
h(
5. By assumption, it holds that
(wijes Falks h(zq))
y (w mppe h((1))))
S p1+
Then we use the above and the AM-GM inequality to show that
[E 112
G. V1 (20 maja))
ld= 11
1((2211)))
1=1
27 (u m7kk)
2aa² E 1 x
(1 + p) -E
1=//2 H|
27
+ a a HIl
y (w sTpk) h(T)1)
2 1og(33//
(1 + p) E
| | H ll
2 2log(32/0)
Tr Tr(EPa
< (Clog(32/8)
2 2 V
n
2 1/ (witee 20 (o) (2)p))
2 2log(32/0) (1+ p)
+
n
After some rearrangements, it is easy to see that we can choose
y- (wofe 27 (((p))))
1 +
lo2(82/8)
(1 p)
nE
2
Tr(E)d=k)
log (32/6)
log(32/))
+
(32/82
/R(S 2-k)
RO
and the proof is complete.
35


Reviews:
[{"review_id": "tXc75Mg7FG", "reviewer": "Reviewer_949a", "summary": "In this paper, generic uniform convergence guarantees are provided for Gaussian data in terms of the Rademacher complexity of the hypothesis class and the Lipschitz constant of the square root of the scalar loss function. Square-Root Lipschitz Loss is an important class of loss function to study because it is a suitable loss to study interpolation learning in cases like phase retrieval and matrix sensing. The authors obtain an optimistic rate in theorem 1 of the paper and the analysis is mostly inspired by the previous work of  Zhou et al. 2022. Then the authors discuss multiple use cases and provide generalization error bound for over-parametrized phase retrieval, matrix sensing, and single index weight tied neural network.", "questions": "Please see above. ", "limitations": "Not applicable. ", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is technically a good paper. Though I am not an expert in this area but it looks to me like, this paper modified the analysis in the previous recent work by Zhou et al. 2022 to obtain new overfitting results. ", "weaknesses": "I have a few questions and some might seem very trivial and please correct me if I am wrong.\n1. I can see that the paper utilizes the Gaussian minimax theorem that is explained in Appendix B.2. However, this still seems like a very restricted setting to me. What happens when one assumes that data is coming from a more general distribution?  Previous results (though not applicable for square roor Lipschitz loss) have no major distributional assumption. \n2. I am also curious to know how realistic is overparametrization setting in phase retrieval.\n3. I am also curious to understand the results of the single index neural network model as the paper cited in this work Biettie et al and other related papers in the domain seem to have the stronger guarantee of recovering the direction using spherical SGD or gf. In this paper, the guarantees are for generalization errors. Is there a way to compare these two results as the results in the other papers where there recover the optimal direction sounds stronger to me? \n\nAs a minor comment, it would also be great if the authors can discuss and compare the results in section 5 and 6 with previously known results. A discussion would be very helpful.\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThanks for the feedback.\n\nThe Gaussianity assumption is indeed a significant restriction, and deviates from much of the classical distribution-free statistical learning literature.  But assuming Gaussianity allows obtaining much tighter guarantees, with tight numerical constants (see [Koehler et al ‘21, Zhou et al ‘21]).  Gaussianity is also widely assumed and used in analysis of many statistical learning and inference problems, e.g. sparse recovery [e.g. Stojnic ‘13, Chandrasekaran et al ‘12 https://arxiv.org/abs/1012.0621, …], phase retrieval [e.g. Mondelli and Montanari ‘18, Barbier et al ‘19], logistic regression [e.g. Candes-Sur ‘20 https://arxiv.org/abs/1804.09753], many other works such as those using Approximate Message Passing, and even analysis of deep learning [e.g. Soltanolkotabi ‘17 https://arxiv.org/abs/1705.04591] (although most of these were also studied, usually with weaker guarantees, without assuming Gaussianity).  Furthermore, much of the statistical physics based analysis relies on “Gaussian universality”, which essentially also relies on the data behaving as if it was Gaussian [e.g. see Hu-Lu ‘23, Bayati et al ‘12 https://arxiv.org/pdf/1207.7321.pdf for some discussion and related rigorous results].  And so, although we agree this is a significant restriction, and it would be very interesting to relax this assumption, we still believe that results relying on Gaussianity are interesting and useful, both on their own right, and as a step toward more general analysis.\n\nSpecifically in the context of this work, by working with Gaussian data we were able to discover several interesting phenomena (e.g. benign overfitting in ReLU regression) which were not at all obvious beforehand (for example, that the consistent loss for interpolation in ReLU regression is (13), that this loss is sqrt-lipschitz, and that it satisfies an “optimistic rate” bound). With a view towards understanding all of these new phenomena beyond the Gausian setting, we have included Section 7, which reveals a situation where a naive generalization of our optimistic rates bound to non-gaussian data is false, but a correct & more sophisticated generalization (equation (28)) works. \n\n> I am also curious to know how realistic is overparameterization setting in phase retrieval.\n\nThe main significance of the phase retrieval model is that it is one of the simplest and most canonical nonlinear models, and so it is valuable to rigorously understand benign overfitting there before proceeding to more complex models like deep networks. Previous works have certainly studied the behavior of phase retrieval in high-dimensional limits with many parameters where overfitting occurs (e.g. cited work of Maillard et al) and understanding the behavior under overparameterization seems like a natural goal just as it was with linear regression. \n\n> I am also curious to understand the results of the single index neural network model as the paper cited in this work Biettie et al and other related papers in the domain seem to have the stronger guarantee of recovering the direction using spherical SGD or gf. In this paper, the guarantees are for generalization errors. Is there a way to compare these two results as the results in the other papers where there recover the optimal direction sounds stronger to me?\n\nBesides that we are both studying weight-tied neural networks, the results seem to be incomparable. Ours is a generalization bound, so it would apply to any algorithm/estimator and we expect it is pretty quantitatively sharp (see also the response to reviewer 8w1y). On the other hand, we didn’t analyze any polynomial time algorithm. The previous works you mentioned analyzed a particular algorithm and proved some guarantees for it (their main goal is algorithmic efficiency, so they did not carefully analyze features like constant factors in the number of samples which we care about in this work). There is probably a lot of interesting future work that could be done combining these types of algorithmic + statistical analyses. \n\n> As a minor comment, it would also be great if the authors can discuss and compare the results in section 5 and 6 with previously known results. A discussion would be very helpful.\n\nAs far as section 5 is concerned, there was a lot of previous work on matrix sensing, ReLU regression etc. but we are the first to establish these types of results, i.e. to prove (1) sufficient conditions for benign overfitting in these models and (2) as the key ingredient to achieve 1, prove very sharp generalization and norm bounds in these models. If we only wanted to prove _some_ generalization bound for say phase retrieval, we could apply standard tools from statistical learning theory like symmetrization+contraction, but they are very wasteful since our loss is not Lipschitz, but instead sqrt-Lipschitz. \n\nRegarding section 6, we have not seen a generalization bound of quite an analogous form (we are taking advantage of the weight-tied structure here). For non-weight-tied neural networks, it is possible to state generalization bounds in terms of the l1 norm of the weights (which could be bigger than the maximum partial sum which appears in our bound), and this type of analysis of neural networks dates at least back to the [Bartlett ‘96] reference. \n"}, {"review_id": "DNRU3mXF4o", "reviewer": "Reviewer_8w1y", "summary": "In the paper, the authors extended a type of sharp uniform convergence guarantee for the square loss to any square-root Lipschitz loss. The proof is considered to be simplified compared to ... \n\nIn the paper, the authors extend the theory of optimistic rates, a type of sharp uniform convergence guarantee, to square-root-Lipschitz losses, enabling new applications like phase retrieval. The authors have shown the uniform convergence for the multi-index model with Gaussian feature when the loss function is non-negative, square-root Lipshichtz and satisfies hypercontractivity. The convergence is controlled by the Radamacher complexity of the hypothesis class and the square-root Lipshichitz constant. The authors then show how this result can be applied to applications including phase retrieval, ReLU regression, matrix sensing, and single-index neural networks. \n\nCompared to other loss function classes being considered in the literature for uniform convergence, square-root Lipshichtz loss is more general that it includes certain nonsmooth non-convex functions, and provides a better intuition of where the square root comparison between loss functions shows up. \n\nThe author also provides a counter-example to argue that Gaussian universality cannot always be taken for granted, and why the result can be over-optimistic for non-Gaussian data.", "questions": "1. How should I think about the technical contribution of the paper? Specifically, how should I consider the difference between the proof here for the square-root Lipschitz functions and the proof for a general Moreau envelope? \n\n2. The generalization results over single-index model is interesting, where you have shown that $\\max_{j \\in [N]} |\\sum_{i = 1}^j a_i| || w ||$ is a good complexity measure. Potentially combined with known results in the single index model, how large should this quantity be? In some way, I think this can be considered as future work to achieve end-to-end results for the weight-tied neural networks so should be fine if there is no clear answer here. Just trying to understand if the generalization bound we achieve here is tight in some sense.", "limitations": "The authors have addressed the limitation of the paper appropriately.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper goes beyond Lipschitz and smooth loss functions and extends the analysis to square-root-Lipschitz losses. This extension is valuable as it includes square loss and can address nonsmoothness. Also, it is easier to verify compared to the Moreau envelope condition used in [Zhou et al. 2022]. As the authors have shown in section 5, their results can be applied to show the benign overfitting for a wide range of real-world scenarios, yielding consistent results compared to past literature. \n\n2. The concept of square-root Lipschitz losses is clean to state, and it indeed provides good intuition for the square-root relationship between losses shown up in previous optimistic rates analysis ([Zhou et al. 2020]). As a result, this new loss function class does seem to capture some intrinsic principle of the problem of optimistic rate and does contribute intuitions for the community. This expansion of applicable loss functions enhances the paper’s relevance and potential impact. \n\n3. Application in Neural Networks: The paper’s extension of norm-based bounds and optimistic rates to weight-tied neural networks contributes to the field of neural network research. By providing a generalization bound that can be combined with the algorithmic outputs of Bietti et al., the authors offer practical insights for optimizing and understanding the non-convex optimization of these network architectures.", "weaknesses": "1. The major concern of the paper is that the technical contribution of the paper is limited. It is mostly built upon previous optimistic rate results ([Zhou et al. 2021, Zhou et al. 2022]). Upon reading the appendix and related literature, the reviewer is on the side that the paper serves as a simplification and rewritten of some past results (except the fact that there is a generalization of previous results by including an extra (network) parameter $\\theta$). Still, the generalization results over general square-root Lipschitz loss is interesting, but need to note that there might not be enough technical contribution in the paper for the main theorem. The norm bounds in the applications are novel. \n\n2. The paper itself is not presented in a way to highlight its contribution either. The paper has done a good job for the literature review, and it has spent more space introducing the results instead of providing intuitions for why the results hold true. This can be understandable as the space for the main submission is rather limited and there are many theorems to be stated in a single paper. Still, the reviewer thinks it can be beneficial in spending a bit more space on proof outlines. \n\n3. There are some other limitations of the work, including the Gaussian feature assumption and the multi-index model for neural networks. Gaussian feature assumption can be served as a good starting assumption for the theory and the authors have addressed the limitation of this assumption appropriately. For neural networks, the multi-index model is a limited shallow neural network. In general, the Rademacher complexity for deep neural networks is normally only a loose estimation and thus results in unrealistic generalization bounds. Still, the multi-index model has been studied extensively recently, so the concern for the limitation here is just a minor one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback!\n> How should I think about the technical contribution of the paper? Specifically, how should I consider the difference between the proof here for the square-root Lipschitz functions and the proof for a general Moreau envelope?\n\nFirst, let us answer the specific question about the proof of the optimistic rates bound. Comparing the proof of the generalization bound with the Moreau envelope framework, we definitely needed a new analysis to avoid having unecessary assumptions involving the Moreau envelopes of f appear in Theorem 1. The new proof still uses key ingredients like the GMT, but after applying the GMT we have to be careful. Essentially, instead of trying to solve the auxiliary problem exactly, we show how to bound the auxiliary problem using analytic properties of square-root Lipschitz functions (in particular, allowing us to appeal to the useful calculus lemmas 8 and 9 in the appendix). \n\nNext, we would like to discuss the key technical contributions of our paper are, which do not end with establishing the optimistic rates bound. As a reminder, a very impressive theoretical understanding of benign overfitting in linear models (e.g. kernel machines) has emerged over the past few years. But studying (even mildly) nonlinear models has been a significant challenge since they do not seem as amenable to random matrix theory methods. One of the most important (and surprising!) realizations we had in this work was how to analyze benign overfitting in nonlinear models like phase retrieval & ReLU regression. At a technical level, this comes from the discovery of 1. the construction described in equation (8) which gives a low-norm interpolator for these nonlinear models, and 2. the closely related discovery of the correct ‘consistent losses’ for these problems. This was not at all obvious a priori! (E.g. we are not aware of anybody discovering the consistent loss (13) for interpolating ReLU regression before this work, or realizing that the Bartlett et al conditions for linear regression should also be sufficient for ReLU regression.) The extensions of the theory to matrix sensing, simple neural networks, and the non-gaussian setting of section 7 are also serious new contributions to the literature which cannot be obtained from previous work. In summary, the fact that sqrt-lipshitz losses satisfy a very sharp optimistic rates bound was one key finding, but the fact that combining this bound with the _right_ choice of sqrt-lipschitz losses lets us understand so many new phenomena is the deeper conceptual message of this work. \n\n> The generalization results over single-index model is interesting, where you have shown that max�∈[�]|∑�=1���|||�|| is a good complexity measure. Potentially combined with known results in the single index model, how large should this quantity be? In some way, I think this can be considered as future work to achieve end-to-end results for the weight-tied neural networks so should be fine if there is no clear answer here. Just trying to understand if the generalization bound we achieve here is tight in some sense.\n\nEnd-to-end results are definitely an interesting direction for future work, for example combining our generalization theory techniques with some of the algorithmic ideas in the literature. As far as tightness, if we choose the b_i appropriately then we can ensure that most of the data falls into a single linear region of the network, and \\sum_{i = 1}^j a_i \\|w\\| for the corresponding value of j will be the norm of the corresponding linear predictor on this region. So in this case the bound reproduces the existing sharp norm-based generalization bound for linear models from previous work (which in turn was shown to recover benign overfitting in linear models etc.), and in this sense the bound seems pretty sharp. \n"}, {"review_id": "njKCzwZdyG", "reviewer": "Reviewer_JChX", "summary": "This paper investigates optimistic rates under square-root Lipschitz losses and Gaussian data. Applications to phase retrieval, ReLu regression, matrix sensing, and single-index NNs are given.\n", "questions": "Please provide more discussion on the highlighted weaknesses.", "limitations": "Assuming the data are Gaussian is limiting.\n\nPlease provide examples when Assumption (C) is satisfied.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper extends the analysis of optimistic rates to square-root Lipschitz losses, which goes beyond the classical smoothness assumption, which is interesting. ", "weaknesses": "The authors claim that the obtained results provide a better understanding of benign overfitting, but the paper needs more explanations and comments on the main results.\n\nAs an example, the bound of eq. (10) features ten distinct terms. It would be nice to discuss which terms refer to what and how they compare with existing terms.\n\nAnother aspect I need clarification on is the notion of uniform convergence. In traditional statical learning, uniform convergence controls the rate of decay of |R(f) - \\hat{R}_n(f)| for all f \\in F and every distribution in a given class. On the other hand, the rate in Th.1 feature (1-\\varepsilon) R(f) on the LHS. I am unfamiliar with benign overfitting literature (which could be standard). However, I invite the authors to add a discussion on this to broaden the paper's audience.\n\nAs for the assumption, I think the Gaussian data is quite restrictive. In modern applications, it is not uncommon to have abundant data but poor quality. In these cases, the data distribution feature tails fatter than any sub-Gaussian (and even sub-Exponential). \n\nAssumption (C) is related to the L_4 norm of the loss. It looks formidable to verify in practice. Even for sub-Gaussian losses, the L_4 would be proportional to \\sqrt{4}*\\sqrt{VAR(loss)}, while the condition requires proportionality to the E[loss].\n\nPlease provide a discussion on these aspects. I may raise my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and questions! \n\n> As an example, the bound of eq. (10) features ten distinct terms... It would be nice to discuss which terms refer to what...\n\nThe term \\rho corresponds to the deviation between the train error and test error of the reference predictor w^# . The terms appearing on the rhs of the inequality for \\epsilon are small assuming Bartlett et al’s “benign overfitting conditions” on the covariance matrix \\Sigma. Basically, Bartlett et al’s conditions require that \\Sigma can be split into a low rank part and an orthogonal component with small trace and large effective rank (R(\\Sigma^{\\perp})). The parameter k lets us control the split between the low-rank part and the rest of \\Sigma. \n\nThough the resulting rhs of equation (10) may appear mysterious at first sight, once we combine it into the generalization inequality to get equation (11) there is a lot of cancellation and we can see that the rhs of (10) is exactly the right size to guarantee consistency under benign overfitting conditions. We also see that the dependencies involved with \\epsilon were necessary, because if benign overfitting conditions aren’t satisfied we shouldn’t be able to arrive at equation (11) (the conditions of Bartlett et al are close to necessary for benign overfitting, besides being sufficient). \n\n> Another aspect I need clarification on is the notion of uniform convergence... the rate in Th.1 feature (1-\\varepsilon) R(f) on the LHS ... \n\nThe (1 - \\varepsilon) factor in the bound is common in statistical learning theory — it is an elegant way to state uniform convergence bounds for classes of functions where the risk R(f) can vary over different scales. If we wanted to, we could rearrange the bound to be of the form R(f) - \\hat{R}_n(f) <= \\varepsilon R(f) + … and if we assume an a priori bound on R(f) (e.g. assume the class of functions is bounded) this bound will be exactly of the form you suggest. Stating the inequality with the \\varepsilon R(f) term is better, because as we obtain better upper bounds on R(f) the guarantee from the rhs improves. (This is related to “localization” in statistical learning.)\n\nAs far as the historical origin, if you look at Theorem 13 in the appendix (which is from Vapnik 1982) you can see that it has a (1 - \\varepsilon) factor in the same way on the rhs. Or for another example, the main result in “Extending the scope of the small-ball method” [Mendelson ‘20] also has such a factor and that paper has a lot of interesting discussion about these types of things. \n\n> As for the assumption, I think the Gaussian data is quite restrictive. In modern applications, it is not uncommon to have abundant data but poor quality. In these cases, the data distribution feature tails fatter than any sub-Gaussian (and even sub-Exponential).\n\nWe agree that assuming the data is Gaussian is restrictive and it is a great direction for future work. Assuming Gaussianity is often a very helpful first step for proving more general results in this area — first we figure out what is true in the Gaussian case, and then we can try to extend it to more general distributions. For this same reason, we included the discussion in Section 7 to illustrate a situation where this type of universality fails, which we hope will help guide future research. (See the response to reviewer 949a for more discussion.)\n\nIn [Zhou et al ‘22], there are related experimental results supporting the belief that sharp generalization theory from the Gaussian case should have more broadly applicable analogues — these experiments include very heavy-tailed distributions like the ones you mention.\n\n> Assumption (C) is related to the L_4 norm of the loss...  Please provide examples when Assumption (C) is satisfied.\n\nAssumption ( C ) is a common assumption in the statistical learning theory literature which goes by a few different names, such as hypercontractivity or ‘norm equivalence’. To understand this assumption, it helps to think of a simple example, so consider for a moment linear regression with the usual squared loss and Gaussian noise & covariates. Then the assumption is saying that $E[(Y - <w, X>)^8] <= \\tau E[(Y - <w, X>)^2]^4$ for any predictors w. Since the law of Y - <w, X> is a Gaussian distribution with a certain variance, this is true simply because for a Gaussian random variable Z, it satisfies E[Z^8] <= 105 E[Z^2]^4. \n\nMore generally, hypercontractivity will` be true for the squared loss if the class of functions is subgaussian in the sense of [Lecue-Mendelson ‘13] (https://arxiv.org/abs/1305.4825). Hypercontractivity is a weaker assumption since it doesn’t require the existence of arbitrarily large moments of the distribution. \n\nWe want to emphasize that we are not proposing hypercontractivity as a new assumption — it is an existing and well-known assumption which makes dealing with the ‘low-dimensional concentration’ part of our analysis clean and straightforward. Because the original work of [Vapnik ‘82] studied the same assumption, we can directly cite his results. However, as discussed in Appendix B.3 and [Zhou et al ‘22], it is also possible to apply other results from statistical learning theory to handle the low-dimensional concentration part of the argument and this would yield different versions of the main theorem. \n\n_Some_ type of concentration/anticoncentration assumption must always be made for any nonasymptotic guarantees on the test error to be possible. For example, consider two cases: (1) Y = 0 always, or (2)  the true Y equals 0 with probability 1 - \\xi and equals 1/\\xi otherwise. For \\xi -> 0 with a finite number of samples, we will not observe a sample where Y is nonzero, so we cannot distinguish situations (1) and (2). However, in situation (1) 0 is a perfect predictor of Y, whereas in situation (2) it suffers a very large squared loss. Standard assumptions like boundedness or hypercontractivity fix the problem because they rule out situation (2). \n"}, {"review_id": "upyI14qVhs", "reviewer": "Reviewer_K77B", "summary": "The paper introduces sharp uniform convergence guarantees for generalized linear models in Gaussian space  for square-root Lipschitz losses. These results extend the scope of previous findings and open up possibilities for applying the derived loss bounds in new contexts.", "questions": "See weaknesses.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.The paper is well-written, providing clear explanations of its contributions in relation to previous work.\n2.The paper achieves fast convergence rates for a broader class of losses, surpassing previous research in this area.\n3.By simplifying the assumptions compared to previous work, the paper is able to derive new bounds applicable to scenarios where solving the Moreau envelope of the loss function is challenging or not possible in closed-form.", "weaknesses": "While the authors discuss potential extensions of the Gaussian feature assumption,  the paper still focuses on the setting of Gaussian data, similar to previous work. Additionally, the proof technique employed in the paper is not entirely novel, as it follows prior works that utilize the Gaussian Minimax Theorem for establishing uniform convergence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! We would like to discuss two points from your comments: (1) the Gaussianity assumption and (2) the novelty of the proof techniques.\n\n*Regarding Gaussianity.* The Gaussianity assumption is indeed a significant restriction, and deviates from much of the classical distribution-free statistical learning literature.  But assuming Gaussianity allows obtaining much tighter guarantees, with tight numerical constants (see [Koehler et al ‘21, Zhou et al ‘21]).  Gaussianity is also widely assumed and used in analysis of many statistical learning and inference problems, e.g. sparse recovery [e.g. Stojnic ‘13, Chandrasekaran et al ‘12 https://arxiv.org/abs/1012.0621, …], phase retrieval [e.g. Mondelli and Montanari ‘18, Barbier et al ‘19], logistic regression [e.g. Candes-Sur ‘20 https://arxiv.org/abs/1804.09753], many other works such as those using Approximate Message Passing, and even analysis of deep learning [e.g. Soltanolkotabi ‘17 https://arxiv.org/abs/1705.04591] (although most of these were also studied, usually with weaker guarantees, without assuming Gaussianity).  Furthermore, much of the statistical physics based analysis relies on “Gaussian universality”, which essentially also relies on the data behaving as if it was Gaussian [e.g. see Hu-Lu ‘23, Bayati et al ‘12 https://arxiv.org/pdf/1207.7321.pdf for some discussion and related rigorous results].  And so, although we agree this is a significant restriction, and it would be very interesting to relax this assumption, we still believe that results relying on Gaussianity are interesting and useful, both on their own right, and as a step toward more general analysis.\n\nSpecifically in the context of this work, by working with Gaussian data we were able to discover several interesting phenomena (e.g. benign overfitting in ReLU regression) which were not at all obvious beforehand (for example, that the consistent loss for interpolation in ReLU regression is (13), that this loss is sqrt-lipschitz, and that it satisfies an “optimistic rate” bound). With a view towards understanding all of these new phenomena beyond the Gausian setting, we have included Section 7, which reveals a situation where a naive generalization of our optimistic rates bound to non-gaussian data is false, but a correct & more sophisticated generalization (equation (28)) works. \n\n*Regarding the novelty of the analysis.* Besides the proof of the main generalization bound (which has some new elements, see reply to reviewer 8w1y), there is a very substantial amount of technical content contained within sections 5-7 which goes well beyond the previous literature. As a reminder, a very impressive theoretical understanding of benign overfitting in linear models (e.g. kernel machines) has emerged over the past few years. But studying (even mildly) nonlinear models has been a significant challenge since they do not seem as amenable to random matrix theory methods. One of the most important (and surprising!) realizations we had in this work was how to analyze benign overfitting in nonlinear models like phase retrieval & ReLU regression. At a technical level, this comes from the discovery of 1. the construction described in equation (8) which gives a low-norm interpolator for these nonlinear models, and 2. the closely related discovery of the correct ‘consistent losses’ for these problems. This was not at all obvious a priori! (E.g. we are not aware of anybody discovering the consistent loss (13) for interpolating ReLU regression before this work, or realizing that the Bartlett et al conditions for linear regression should also be sufficient for ReLU regression.) The extensions of the theory to matrix sensing, simple neural networks, and the non-gaussian setting of section 7 are also serious new contributions to the literature which cannot be obtained from previous work. In summary, the fact that sqrt-lipshitz losses satisfy a very sharp optimistic rates bound was one key finding, but the fact that combining this bound with the _right_ choice of sqrt-lipschitz losses lets us understand so many new phenomena is the deeper conceptual message of this work. \n"}, {"review_id": "eiVOniZaZZ", "reviewer": "Reviewer_Y88d", "summary": "This paper develops uniform convergence result for empirical risk minimization with a loss function whose square root is Lipschitz. It is assumed that the covariate vector $x$ is drawn from a $d$-dimensional multivariate normal and the response $y$ is generated by a structural equation that only depends on $x$ through its $k$-dimensional projection. The result bounds the root of population risk in terms of the root of the empirical risk and another term concerning the Lipschitz constant, a complexity measure and the sample size. The bound holds uniformly (in high probability) over all possible affine coefficients in the empirical risk minimization. This key result is then applied to study \"benign overfitting\" in several problems, including phase retrieval, ReLU regression and matrix sensing. In addition, it is also shown that Gaussian universality does not hold for the setting considered. ", "questions": "1. Page 4, line 135: I do not see why the distribution of $\\langle w, x \\rangle$ only depends on $w^{T} \\Sigma W$. By $x \\sim \\mathcal{N}(\\mu, \\Sigma)$ as in Assumption (A), wouldn't it depend on $w^{T} \\mu$ and $w^T \\Sigma w$?\n2. Page 2, line 76: missing \"be\" before \"applied\".", "limitations": "I do not foresee any potential negative societal impact of this work.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper builds upon and generalizes related results in the literature. \n2. It establishes a key generic result and then illustrates its strength through application to several topical problems. \n3. The presentation is rigorous and clear.", "weaknesses": "As this paper falls out of my area of expertise, I am only listing below a few points that might help me (or someone from outside the field) to better understand the paper. \n\n1. The notion of \"consistency\" or a \"consistent loss\" is mentioned in the Introduction and throughout the applications. It is worth explaining what that means and how it relates the usual notion of \"consistency\" in statistics. \n2. Assumption (C) perhaps deserves more explanation: why is it necessary and when is it expected to hold?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback!\n\n> The notion of \"consistency\" or a \"consistent loss\" is mentioned in the Introduction and throughout the applications. It is worth explaining what that means and how it relates the usual notion of \"consistency\" in statistics.\n\nWe say that an estimator (\\hat{w},\\hat{b}) valued in a set K is consistent if the test error of the estimator converges to the optimal test error in the class, i.e. \nL(\\hat{w}, \\hat{b}) -> \\min_{w,b \\in K} L(w,b).\n\nHere when we take the limit, we are considering an asymptotic regime where the number of samples n goes to infinity but also the dimension and other parameters of the problem may be assumed to scale in a certain way as well. (In classical parametric statistics, consistency was largely studied where the dimension was fixed and number of samples goes to infinity. In high-dimensional statistics like this work, the cited work of Bartlett et al, Thrampoulidis et al, etc. the dimension also goes to infinity with the number of samples and this is crucial to observe modern phenomena like benign overfitting.) For e.g. phase retrieval we show consistency under the same asymptotic conditions on the covariance matrix \\Sigma that Bartlett et al. studied for linear regression.\n\nA key point with the above definition is that consistency is not just a property of the estimator, but also a property of the loss function f chosen. When we study benign overfitting in linear regression, phase retrieval, etc the estimator we are interested in will interpolate the data, and it is not clear a priori which losses this estimator will be consistent under (if any). The previous works on benign overfitting showed that in linear regression, minimum-norm interpolants will be consistent under the squared loss (but not e.g. the L1 loss if the model is misspecified). A major new contribution of this work is to prove consistency results for phase retrieval, ReLU regression etc and this requires in particular us to identify the consistent loss. \n\n> Assumption (C) perhaps deserves more explanation: why is it necessary and when is it expected to hold?\n\nAssumption ( C ) is a common assumption in the statistical learning theory literature which goes by a few different names, such as hypercontractivity or ‘norm equivalence’. To understand this assumption, it helps to think of a simple example, so consider for a moment linear regression with the usual squared loss and Gaussian noise & covariates. Then the assumption is saying that $E[(Y - <w, X>)^8] <= \\tau E[(Y - <w, X>)^2]^4$ for any predictors w. Since the law of Y - <w, X> is just a Gaussian distribution with a certain variance, this is true simply because for a Gaussian random variable Z, it satisfies E[Z^8] <= 105 E[Z^2]^4. \n\nMore generally, hypercontractivity will certainly be true for the squared loss if the class of functions is subgaussian in the sense of [Lecue-Mendelson ‘13] (https://arxiv.org/abs/1305.4825), and in fact hypercontractivity is a weaker assumption since it doesn’t require the existence of arbitrarily large moments of the distribution. \n\nWe want to emphasize that we are not proposing hypercontractivity as a new assumption, we are simply using it as an existing and well-known assumption which makes dealing with the ‘low-dimensional concentration’ part of our analysis clean and straightforward. Because the original work of [Vapnik ‘82] studied the same assumption, we can directly cite his results in our analysis. However, as discussed in Appendix B.3 and [Zhou et al ‘22], it is also possible to apply other results from statistical learning theory to handle the low-dimensional concentration part of the argument and this would yield different versions of the main theorem. \n\n_Some_ type of concentration/anticoncentration assumption must always be made for any nonasymptotic guarantees on the test error to be possible, simply to avoid degenerate situations. For example, consider two cases: (1) Y = 0 always, or (2)  the true Y equals 0 with probability 1 - \\xi and equals 1/\\xi otherwise. For \\xi -> 0 with a finite number of samples, we will not observe a sample where Y is nonzero, so we cannot distinguish situations (1) and (2). However, in situation (1) 0 is a perfect predictor of Y, whereas in situation (2) it suffers a very large squared loss. Standard assumptions like boundedness or hypercontractivity fix the problem because they rule out situation (2). \n\n\n\n> Page 4, line 135: I do not see why the distribution of ⟨�,�⟩ only depends on ��Σ�. By \n�∼�(�,Σ) as in Assumption (A), wouldn't it depend on ��� and ��Σ�?\n\nYou are right, this is a typo and it should also depend on $w^T \\mu$ and $w^T \\Sigma w$. The point is that it only depends on these O(k) many quantities instead of O(d) many. \n"}]

Author rebuttal:

Meta-review: This is a nice paper which, to my taste, can be best summarized somewhat technically as trying to find the limits of the Gaussian minimax technique to interpolation / benign overfitting from prior works, and resulting in a rather simple presentation which applies to many settings and moreover leads to some interesting further discussion and insight, for instance the counterexample in section 7. I am happy to recommend acceptance, and recommend the authors use the extra camera ready page to reflect all reviewer discussion.
Decision: Accept (poster)