Approximate First-order Interpolators. When \(\mathcal {F}\)  is an expressive family of nonlinear models, it has been observed empirically that standard stochastic gradient methods can be run until the model begins to perfectly interpolate the training data, without hurting test-time performance. This phenomenon has been referred to in the literature as benign overfitting [1]}, and has been seen to hold frequently in the training of DNNs in practice, when stochastic gradient descent is run for sufficiently many epochs. In fact, in all our experiments (see Figs. REF  and REF  in app:theorem:5), we observe that upon running stochastic gradient descent for sufficiently long on the aggregate loss \(\mathcal {L}_n ( + R (\) , the parameter \(\hat{ eventually converges to a solution \textit {which interpolates the labelled examples well}, i.e., the mean square error \mathcal {L}_n (\hat{) is upper bounded by a sufficiently small \Delta > 0. Note that we \textit {do not} assume that \Delta  is so small that the condition essentially imposes that \hat{ is an approximate global minimizer of the training loss. In theory, our results also hold under the stronger condition that \mathcal {L}_n (\hat{) + R(\hat{) is upper bounded by \Delta , which is the loss function being optimized by (stochastic) gradient descent. This phenomenon motivates the following definition of approximate first order stationary interpolators.}\begin{definition}[\Delta -approximate first order stationary interpolator] A point \hat{ is defined to be a \Delta -approximate first-order stationary interpolator if,\begin{enumerate}\item \hat{ is a first order stationary point of the aggregate loss \mathcal {L}_n ( + R (. Namely,{\begin{@align}{1}{-1} 0 \in (\nabla \mathcal {L}_n) ( \hat{) + (\nabla R) ( \hat{).}}\item f_{\hat{} approximately interpolates the observed training data. Namely, the empirical mean squared error of \hat{ evaluated on the training dataset satisfies,{\begin{@align}{1}{-1}\mathcal {L}_n (\hat{) \le \Delta .}\end{@align}Note that our results hold under the stronger condition \mathcal {L}_n (\hat{) + R(\hat{) \le \Delta , the training loss function being minimized by the (stochastic) gradient methods in our experiments.}}}We are ready to establish a guarantee on the statistical performance of approximate first-order stationary interpolators.}}\end{@align}\begin{theorem} Suppose \lambda  is chosen = 4 C_0 \sigma \sqrt{\frac{d + \log (1/\delta )}{n}} for a sufficiently large constant C_0 > 0. Assume that the size of the dataset is sufficiently large, namely, n > n_0 (as defined in {eq:n0}). Consider a learner returns \hat{ which is a \Delta -approximate first order stationary interpolator, where \Delta \le C_1 ( C_{n,\delta }^*/\mu )^2 for a sufficiently large constant C_1. Then, with probability \ge 1 - 2 \delta ,\begin{equation}\Vert  \hat{- * \Vert _2 \lesssim \frac{L}{2C_{n,\delta }^*} \sqrt{\frac{kd}{n}}.}\end{equation}}\begin{remark}For pseudo-Boolean functions, the log-covering number in any norm up to log factors is \approx \log \binom{2^d}{k} \approx kd. Therefore, an algorithm which returns a function which is an exact minimizer of the mean squared error among all functions with a k-sparse polynomial representation, {\mathrm {LS}}_k admits the guarantee \Vert  {\mathrm {LS}}_k - * \Vert _2 \lesssim \sqrt{kd/n} up to scaling constants, with high probability, up to log factors. However, when \Delta  is large, the learner considered in {theorem:111} is not constrained to return the exact minimizer of the squared error (subject to the sparsity constraint). Thus, under the additional condition of first-order stationarity, {theorem:111} imposes a much weaker condition, \mathcal {L}_n (\hat{) \lesssim \Delta  rather than \hat{\in \operatornamewithlimits{arg\,min}\mathcal {L}_n (.}}Finally, in the context of the previous two results, we prove a lower bound showing statistical optimality under the imposed assumptions.\end{remark}\end{theorem}}\begin{theorem} Suppose d \ge 3 and k \le 2^d/4. Then, there exists a parameter class \Theta , and an associated function class \mathcal {F} = \lbrace  f_{ : \Theta \rbrace  such thatfor any learner \hat{, there exists a ground truth function f_{*} : \lbrace  \pm 1 \rbrace ^d \rightarrow \mathbb {R} having a k-sparse polynomial representation, such that given a sufficiently large dataset of n samples,\begin{enumerate}\item Assumptions~\ref {A0}, \ref {A1}, \ref {A2} and \ref {A3} are satisfied with constants L = 1, \mu = 0 and C_{n,\delta ^*} \in \left[ \frac{1}{2}, \frac{3}{2} \right] with probability \ge 1 - \delta .\item \mathbb {E} \left[ \Vert  \hat{- * \Vert _2  \gtrsim \sigma \sqrt{\frac{kd}{n}}, where \sigma ^2 denotes the noise variance in the observed labels.}\right.\end{enumerate}{\bf Extensions to cases with multiple local minima}.While we focus on general parametric function classes in {theorem:000,theorem:111}, for the specific case of DNNs, the issue of ``permutation invariance^{\prime \prime } can appear. In particular, a permutations (i.e., relabeling) of the neurons in the same layer of a network can result in a different network with the same functional relationship between the input and the output. In this case, Assumptions~\ref {A0} and \ref {A1} cannot hold globally for all \mathbb {R}^m, as the loss \mathrm {Err}_{n} (*) and its gradient become 0 at any parameter *_{\sigma }, where *_\sigma  denotes the weight matrices corresponding to a functionally invariant permutation \sigma  of the neurons of the base network with parameter *. However, even in this case, we can extract a guarantee from {theorem:000} and {theorem:111} by modifying the underlying assumptions slightly.}In particular, consider an arbitrary norm \Vert  \cdot \Vert  and a nearest neighbor partitioning of the parameter space depending on the nearest permutation of *. Namely, for a permutation \sigma , \mathcal {K}_\sigma \subset \mathbb {R}^m iff \sigma = \operatornamewithlimits{arg\,min}_{\sigma ^{\prime }} \Vert   *_{\sigma ^{\prime }} \Vert  . Suppose for each \mathbb {R}^m, belonging to the partition \mathcal {K}_\sigma , the condition, \langle  *_\sigma , \nabla _{ \mathrm {Err}_{n} (*_\sigma )\rangle \ge C^*_{n,\delta } \Vert   *_\sigma \Vert _2^2 (modified Assumption \ref {A0}) and \mathrm {Err}_{n} (*_\sigma )\ge C^*_{n,\delta } \Vert   *_\sigma \Vert _2^2 (modified Assumption \ref {A1}) hold. In words, instead of globally, we impose the RSI and QG conditions in a local neighborhood (corresponding to the partition \mathcal {K}_\sigma ) around each permutation \sigma ^* of the ground truth parameter *. This avoids the issue alluded to before, since the modified versions of Assumptions~\ref {A0} and \ref {A1} are now true trivially at  *_\sigma , corresponding to any within-layer permutation of the neurons of *.}Corresponding to the new modified assumptions, a learner which returns any \hat{ which is a stationary point under {A0} (resp. approximate first order stationary interpolator under {A1}), guarantees to approximate \sigma ^*, the nearest permutation of * to it in the norm \Vert  \cdot \Vert . The proofs of these results follow identically to {theorem:000} and {theorem:111}. In particular, replacing * by the parameter *_\sigma  where \hat{\in \mathcal {K}_\sigma  and following the same argument completes the proof of the result showing that *_\sigma  can be recovered approximately.}In summary, rather than assuming that the loss \mathrm {Err}_{n} (*) is globally bowl shaped as in {A1}, which cannot hold globally because of the permutation invariance of neural networks, it suffices to assume that the loss function is locally bowl shaped around each functionally invariant permutation \sigma ^* of the ground truth parameter *. This line of reasoning can be extended to incorporate other symmetries in the function class which prevent exact parameter recovery, as in the case of permutation invariance of neural networks. The corresponding parameter recovery guarantee is also be modified to be up to this symmetry.}}\begin{figure}[t]\centering \includegraphics [width=]{figures/fig1.pdf}\caption {The plots demonstrate the generalization power of a depth-4 feed-forward neural network in learning 3 classes of sparse pseudo-Boolean functions f(x):\lbrace \pm 1\rbrace ^{13}\rightarrow \mathbb {R} using the mean squared error (MSE) loss before (first row) and after (second row) adding the spectral (SP) regularizer, as a function of the number of training samples. \textsc {Monomial} are 1-sparse functions in Walsh-Hadamard transform (WHT) with an increasing order of interactions (1 to 5). \textsc {Power law} are 10-sparse functions in WHT with second order interactions and coefficients set using a power law function. \textsc {Staircase} are 18-sparse functions in WHT with 3 first order, 6 second order, and 9 third order interactions, each with an equal coefficients and set using a power law function. The heat maps show the fraction of times (among 5 random independent trials) the models generalize on unseen data with the coefficient of determination larger than R^2\ge 0.45 on the test data points.}\end{figure}\end{theorem}}\section {Empirical Studies} \end{enumerate}}\begin{figure}[t]\centering \includegraphics [width=1]{figures/assumption4.png}\caption {We estimate the empirical lower bound \hat{C}_{n,\delta }^\ast  in the quadratic growth (QG) condition by finding the minimum change in the network^{\prime }s output as a result of perturbations to the weights with noise drawn from the normal distribution W \sim \mathcal {N} (0,\sigma ^2). Experiments on 2 fully connected networks (FCNs) and a convolutional neural network (CNN) reveals empirical lower bounds. }\end{figure}\end{definition}We design our experiments in a way to address these questions:\begin{itemize}\item Does SP improve generalization accuracy in learning sparse polynomials?\item When does QG hold for common DNN architectures? what is the empirical lower bound \hat{C}_{n,\delta }^\ast ?\item Does SP improve generalization accuracy in real-world problems?\item How does L_1-regularization compare to SP-regularization in practice in terms of generalization?\end{itemize}}}}{\bf Sparse polynomials}. We compare the generalization performance of a depth-4 fully connected network with and without the SP regularization on 3 classes of sparse polynomials in Fig.~\ref {fig:dl_phase_tr}: 1) \textsc {Monomial} are randomly-drawn 1-sparse functions in WHT with increasing order of interactions from 1 to 5. 2) \textsc {Power Law} are randomly-drawn 10-sparse functions in WHT all with order-2 interactions and coefficients set based on a power law function with decreasing exponent. 3) \textsc {Staircase} are randomly-drawn 18-sparse functions in the WHT with 3 first order, 6 second order, and 9 third order interactions, each with equal coefficients and set based on a power law function. These synthetic sparse polynomials are inspired by physical models for real-world pseudo-Boolean functions (e.g., protein functions~\cite {brookes2022sparsity,qian2001protein,qin2018power}). We observe clear transitions in generalization power: it is harder in terms of sample cost to learn nonlinear models with higher order interactions and lower sparsity exponent (i.e., denser functions in WHT). This analysis adds a new axis to the accuracy-vs-sample-cost phase transition curves in compressed sensing~\cite {donoho2011noise}. SP regularization consistently improves the transition curves for generalization power as a function of order and sample cost.}\)
