Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon
Authors: Tongtong Liang
Dan Qiao
Yu-Xiang Wang
Rahul Parhi
Venue: NeurIPS 2025 spotlight ()
Keywords: Generalization bound
minima stability
gradient descent
large learning rate
ReLU neural network
minimax rate
Primary area: deep_learning

Abstract: We study the implicit bias of flatness / low (loss) curvature and its effects on generalization in two-layer overparameterized ReLU networks with multivariate inputs---a problem well motivated by the minima stability and edge-of-stability phenomena in gradient-descent training. Existing work either requires interpolation or focuses only on univariate inputs. This paper presents new and somewhat surprising theoretical results for multivariate inputs. On two natural settings (1) generalization gap for flat solutions, and (2) mean-squared error (MSE) in nonparametric function estimation by stable minima, we prove upper and lower bounds, which establish that while flatness does imply generalization, the resulting rates of convergence necessarily deteriorate exponentially as the input dimension grows. This gives an exponential separation between the flat solutions compared to low-norm solutions (i.e., weight decay), which are known not to suffer from the curse of dimensionality. In particular, our minimax lower bound construction, based on a novel packing argument with boundary-localized ReLU neurons, reveals how flat solutions can exploit a kind of "neural shattering" where neurons rarely activate, but with high weight magnitudes. This leads to poor performance in high dimensions. We corroborate these theoretical findings with extensive numerical simulations. To the best of our knowledge, our analysis provides the first systematic explanation for why flat minima may fail to generalize in high dimensions.

Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon
Tongtong Liang UC San Diego tt ttl stliang@uesd. edu
Dan Qiao UC San Diego
Yu-Xiang Wang UC San Diego yuxiangv@ucsd. edu
Rahul Parhi UC San Diego rahul@ucse edu
d2qiaoQucsd. edu
Abstract
We study the implicit bias of flatness low (loss) curvature and its effects on general- ization in two-layer overparameterizee ReLU networks with multivariate inputs-a problem well motivated by the minima stability and edge-of-stability phenomena in gradient-descent training. Existing work either requires interpolation or focuses only on univariate inputs. This paper presents new and somewhat surprising theo- retical results for multivariate inputs. On two natural settings (1) generalization gap for flat solutions, and (2) mean-squared error (MSE) in nonparametric function estimation by stable minima, prove upper and lower bounds, which establish that while flatness does imply generalization, the resulting rates of convergence necessarily deteriorate exponentially the input dimension grows. This gives exponential separation between the flat solutions compared to low-norm solutions (i.e., weight decay), which are known not suffer from the curse of dimensionality. In particular, our minimax lower bound construction, based on a novel packing argument with coandarr-localizer ReLU neurons, reveals how flat solutions exploit kind of "neural shattering" where neurons rarely activate, but with high weight magnitudes. This leads to poor performance high dimensions. We cor- roborate these theoretical findings with extensive numerical simulations. To the best of our knowledge, our analysis provides the first systematic explanation for why flat minima may fail to generalize in high dimensions.
Introduction
Modern deep learning is inherently overparameterized. In this regime, there are typically infinitely many global (i.e., zero-loss or interpolating) minima to the training objective, yet gradient-descent (GD) training seems to successfully avoid "bad" minima, finding those that generalize well. Un- derstanding this phenomenon boils down understanding the implicit biases of training algo- rithms [Zhang et al., 2021]. A large body of work has focused on understanding this phenomenon in the interpolation regime [Du et al., 2018, Liu et al., 2022], and the related concept of "benign overfitting" [Belkin et al., 2019, Bartlett et al., 2020, Frei et al., 2022].
While these directions have been fruitful, there is increasing evidence that rectified linear unit (ReLU) neural networks do not benignly overfit [Mallinar et al., 2022, Haas et al., 2023], particularly in the case of learning problems with noisy data [Joshi al., 2023, Qiao et al., 2024]. Furthermore, for noisy labels, it takes many iterations of GD to actually interpolate the labels [Zhang et al., 2021]. This discounts theories based on interpolation to explain the generalization performance of practical neural networks, which would have entered the so-called edge-of-stabiillyy regime [Cohen et al., 2020), or stopped long before interpolating the training data.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Weight Norm vs. Activation Rate
107
Tral lieuno E.I
nn Neuron Used 11
201
1.0
0.5
10-1
0.0
10
Figure 1: The "neural shattering" phenomenon: From empirical observations to its geometric origin and theoretical consequences. Left panel: Training with a large learning rate and gradient descent empirically results in "neural shattering": Neurons develop large weights despite activating on very few inputs, leading to a high MSE of ~ 1.105 (red points). In contrast, explicit L eerregulriization prevents this, achieving a much lower MSE of 0.055 (orange points). Middle panel: The number of distinet directions, or "caps", on gigh-dimensional sphere grows exponentially. Consequently, the data sites are spread thinly across these caps. This makes trivial for ReLU neuron to find direction that isolates only a few data points. This sparse activation pattern allows neurons to use large weight magnitudes for this local fitting without impacting the global loss curvature, thus "tricking" the flatness criterion. Right panel: Visualization of "hard-to-learn function from our minimax lower bound construction, built from localized ReLU neurons described in the middle panel.
To that end, it has been observed that an important factor that afficts/charractrriess the implicit bias of GD training is the notion of dynamical stability [Wu et al., 2018]. Intuitively, the (dynamical) stability of particular minimum refers to the ability of the training algorithm to "stably converge" to that minimum. The stability of a minimum is intimately related the flatness of the loss landscape about the minima [Mulayoff et al., 2021]. A number of recent works have focused on understanding linear stability, i.e., the stability of an algorithm's linearized dynamics about a minimum, in order to characterize the implicit biases of training algorithms [Wu et al., 2018, Nar and Sastry, 2018, Mulayoff et al., 2021, Ma and Ying, 2021, Nacson al., 2023]. Minima that exhibit linear stability are often referred to as stable minima. In particular, Mulayoff et al. [2021] and Nacson et al. [2023] focus on the interpolation regime of two-layer overparameterized ReI.U neural networks in the univariate input and multivariate input settings, respectively. Roughly speaking, the main takeaway from their work is that stability flatness in parameter space implics a founded-variation smoothness in function space.
of
Moving beyond the interpolation regime, Qiao al. [2024] extend the framework of Mulayoff et al. [2021] and provide generalization and risk bounds for stable minima in the non-interpolation regime for univariate inputs. They show that for univariate nonparametric regression, the functions realized by stable minima cannot overfit in the sense that the generalization gap vanishes as the number of training examples grows. Furthermore, they show that the learned functions achieve near-optimal estimation error rates for functions of second-order bounded variation on an interval strictly inside the data support. While this work good start, it begs the questions of (i) what happens in the multivariate high- nigh-dimennsionl case and (ii) what happens off of this interval (i.e., how does the network extrapolate). Indeed, these are key to understanding the implicit bias of GD trained neural networks, especially since learning high dimensions seems to always amount to extrapolation [Balestriero et al., 2021]. These two questions motivate the present paper in which we provide precise answer to the following fundamental question.
How well do stable minima of two-layer overparameterized ReL.U neural networks perform in the high-dimensional and non-interpolation regime?
We provide several new theoretical results for stable minima in this scenario, which are corroborated by numerical simulations. Some of our findings are surprising given the current state of understanding of stable minima. Notably, we show that, while flatness does imply generalization, the resulting sam- ple complexity grows exponentially with the input dimension. This gives an exponential separation between flat solutions and low-norm solutions (weight decay) which are known not to suffer from the curse of dimensionality [Bach, 2017, Parhi and Nowak, 2023b].
2

---

1.1 Contributions
In this paper, we provide new theoretical results for stable minima of two-layer ReLU neural networks, particularly in the high-dimg diteemimenii and non- -oniieerpolation regime. Our primary contributions lie in the rigorous analysis of the generalization and statistical properties of stable minima and the resulting insights into their high-dimensional behavior. In particular, our contributions include the following.
1. We establish that the functions realized by stable minima are regular in the sense of a weighted variation norm (Theorem 3.2 and Corollary 3.3). This norm defines a data-dependent function class that captures the inductive bias of stable minima. Furthermore, this regularity admits an analytic description as a form of weighted total variation in the domain of the Radon transform. These results synthesize and extend previous work [ef., Nacson et al., 2023, Qiao et al., 2024] by removing interpolation assumptions and generalizing them to multivariate inputs.
2.
We analyze the generalization properties of stable minima in both a statistical learning setting and a nonparametric regression setting defined using the smoothness class above.
We establish that stable minima provably cannot overfit in the sense that their generalization gap (i.e., a uniform convergence bound) tends 0 as the number of training examples n > 00 at a rate n उ up to logarithmic factors (Theorem 3.5).
For nigh-dimensional (d > 1) nonparametrie regression, we show that stable minima (up to logarithmic factors) achieve an estimation error rate, in mean-squared error (MSE), upper bounded by n शरो (Theorem 3.6).
We prove a minimax lower bound of rate n अी up to a constant (Theorem 3.7) on both the MSE and the generalization gap, which certifies that stable minima are not immune to the curse of dimensionality. This gives an exponential separation between flat solutions and low-norm solutions (weight decay) [Bach, 2017, Parhi and Nowak, 2023b].
By specializing the MSE upper bound to the univariate case (d 1), we show that stable minima (up to logarithmic factors) achieve an upper bound of n b. Furthermore, by a construction specific to the univariate case, we have a sharper lower bound of n- when d = 1. These results should be contrasted those of Qiao et al. [2024], who derive matching upper and lower bounds of n on an interval strictly inside the data support. Note that our results hold over the full domain, therefore capturing how the networks extrapolate. Thus, results provide a more realistic characterization of the statistical properties of stable minima in the univariate case than in prior work.
3. In Section 4, we corroborate our theoretical results with extensive numerical simulations. As uncover and characterize a phenomenon refer to "neural shattering" that is inherent to stable minima in high dimensions. This refers to the observation that each neuron in flat solution has very few activated data points, which means that the activation boundaries of the ReLU neurons in the solutions shatter the data set into small pieces. This leads poor performance in high dimensions. We also highlight that this observation exactly matches the construction of "hard-to-learn" functions for our minimax lower bound. Thus, our empirical validation combined with our theoretical analysis offers fresh insights into how gigh-dimensionality impacts neural network optimization and generalization. Indeed, our results reveal a subtle mechanism that leads to poor performance specifically in high dimensions.
by-product.
These results are based on two novel technical innovations in the analysis of minima stability in comparison to prior works, which we summarize below.
Statistical bounds on the full input domain. The data-dependent nature of the stable minima function class implies that there are regions of the input domain where neuron activations are sparse for stable minima. This because the functions in this class have local smoothness that can become arbitrarily irregular near the boundary of the data support. This makes it challenging to study the statistical performance of stable minima the irregular regions. This was bypassed in the univariate case by Qiao et al. [2024] by restricting their attention to an interval strictly inside the data support, completely ignoring these hard-to-handii toadddlee regions. Our analysis overcomes this via a novel technique
'More specifically, this quantity detines a seminorm which correspondingly defines a kind of Banach space of functions called weighted variation space Vore et al., 2025].
3

---

that balances the error strictly inside the data support with the error close to the boundary. This allows us establish meaningful statistical bounds on the full input domain.
ReL U-specicci minimax lower bound construction. We develop a novel minimax lower bound construction (see proof of Theorem 3.7) using functions built from sums of ReLU neurons. These neu- rons are strategically chosen to have activation regions near the boundary of the input domain. This ex- ploits the "'n/oof"" nature of ReLUs and digh-dimensional geometry to create "hard-to-learn" functions. The data-dependent weighting allows these sparsely active, high-magnitude neurons to exist within the stable minima function class. This construction is fundamentally different from classical nonpara- metric techniques and is tightly linked to our experimental findings on neural shattering (see Figure 1).
1.2 Related Work
Stable minima and function spaces. Many works have investigated characterizations of the implicit bias of GD training from the perspective of dynamical stability [Wu et al., 2018, Nar and Sastry, 2018, Mulayoff et al., 2021, Ma and Ying, 2021, Nacson et al., 2023, Wang et al., 2022, Qiao et al., 2024]. In particular, Mulayoff et al. [2021] characterized the function-space implicit bias of minima stability for two-layer overparameterizee univariate ReLU networks in the interpolation regime. This was extended to the multivariate case by Nacson et al. [2023] and, the univariate case, this was extended to the non-interpolation regime by Qiao et al. [2024] with the addition of generalization guarantecs. In this paper, we extend these works to the sigh-dimensional and non-interpolation regime and characterize the generalization and statistical properties of stable minima.
Nonparametric function estimation with neural networks. is well known that neural networks are minimax optimal estimators for a wide variety of functions [Suzuki, 2018, Schmidt-Hieber, 2020, Kohler and Langer, 2021, Parhi and Nowak, 2023b, Zhang and Wang. 2023, Yang and Zhou, 2024, Qiao et al., 2024]. Outside of the univariate work of Qiao et al. [2024], all prior works construct their estimators via empirical risk minimization problems. Thus, they do not incorporate the training dynamics that arise when training neural networks in practice. Thus, the results of this paper provide more practically relevant results on nonparametric function estimation, providing estimation error rates achieved by local minima that GD training can stably converge to.
Loss curvature and generalization. A long-standing theory to explain why overparameteriize neural networks generalize well is that the flat minima found by GD training generalize well [Hochre- iter and Schmidhuber, 1997, Keskar et al., 2017]. Although there is increasing theoretical evidence for this phenomenon in various settings [Ding et al., 2024, Qiao et al., 2024), there is also evidence that sharp minima can also generalize [Dinh al., 2017]. Thus, this paper adds complementary results to this list where we establish that, while flatness does imply generalization for two-layer ReLU networks, the resulting sample complexity grows exponentially with the input dimension.
2 Preliminaries, Notation, and Problem Setup
We investigate learning with two-layer ReLU neural networks. Our focus is on understanding the generalization and statistical performance of solutions obtained through GD training, particularly those that are stable.
Neural networks. We consider two-layer ReLU neural networks with K neurons. Such a network implements a function fo Rdd R of the form
K
fo(x) = Σ
N - be) + 3,
k=1
where 0 = { U (ox, Wa, b U {B} denotes the collection of all neural network parameters, including the width K E N. Here, 2s E IR denotes the output-layer weights, w, E Rd denotes the input-layer weights, by E IR denotes the input-layer biases, and B E IR denotes the output-layer bias.
Data fitting and loss function. We consider the problem of fitting the data = -(x,,,++)² 3/m where n; E & and y; E TR. We consider the empirical risk minimization problem with squared-error loss L( 2n E (y fo(

---

Gradient descent and minima stability. We aim to minimize 2()) via GD training, i.., we consider the iteration 0.+1 0, -VVo(()) for 0, 1, 2....... where rj > is the step size / learning rate, Vo denotes the gradient operator with respect to 0 V2 denotes the Hessian operator with respect to 0, and the iteration is initialized with some initial condition og. The analysis of these dynamics in generality is intractable in most cases. Thus, following the work of Wu et al. [2018], many works [e.g.. Nar and Sastry, 2018, Mulayoff' et al., 2021, Ma and Ying, 2021, Wang et al., 2022, Nacson et al., 2023, Qiao et al., 2024] have considered the behavior of this iteration using linearized dynamics about a minimum. Following Mulayoff et al. [2021], we consider the Taylor series expansion of the loss function about minimum 0 That is,
0) = (())) + (0 - (0--))Tv=((0)) + 2 (0 - (V)
(2)
As the GD iteration approaches minimum 0*, is well approximated by the linearized dynamics
0z+1 = 0: - (
07) 0,0,,,2
A minimum is said to be linearly stable if the GD iterates are "trapped" once they enter neighborhood of the minimum. See Wu et al. [2018]. Ma and Ying [2021], or Chemnitz and Engel [2025] for various rigorous definitions of linear stability that have appeared in the literature. It turns out that stability is tightly connected to the flatness of the minimum. Indeed, many equivalences have been proven, e.g., Mulayoff al. [2021, Lemma IJ. Qiao et al. [2024, Lemma 2.2], or Chemnitz and Engel (2025, Section 2.3]. We have the following proposition from Chemnitz and Engel [2025, 7]. Proposition 2.1. Suppose that r) < 2. A minimum 0* is linearly stable if and only if
Amax ( (2)(())) 2
Tj
Thus, we see that the stability of a minimum is equivalent to the flatness of the minimum under the assumption that the step size satisfies 1) < 2. Thus, we make this assumption in the remainder of this paper. Given a data set D, we refer to the class of neural network parameters
m (1T: D) {0: Amax (V2C()) 2
(5)
as the collection of flat / stable minima flat stable solutions. This parameter class is further motivated by empirical observations that GD often operates in the adge-of-stabilitg regime, where Amax V2 (())) hovers around 2/1 [Cohen et al., 2020, Damian et al., 2024].
3 Main Results
In this section, we characterize the implicit bias of stable solutions. It turns out that every function fe. with 0 Onac (7; D). regular in the sense of a weighted variation norm. In particular, the weight function is a data-dependent quantity. This weight function reveals that neural networks can learn features that are intrinsic within the structure of the training data. To that end, given data set D {(x;; ) C Rd R. we consider a weight function g $d-1 x I + R, where gd-1 = {u E Rd |ull = 1} denotes the unit sphere. This weight is defined by g(u, !) = min(ğ(u, 1),g( u. {)). where
ō(u,t) = P u E - x
f) V EX X E]1
(6)
Techhically, require that the loss is twice differentiable 0". Due to the ReLU activation, there is measure 0 set in the parameter space where this is not true. However, we randomly initialize the weights with a density and use gradient descent with non-vanishing learning rate, then with probability the GD iterations do not visit such non-differentiable points. For the interest of generalization bounds, the behaviors of non dindiffferentable points are identical to their infinitesimally perturbed neighbor. which is differentiaale. For these reasons, this assumption will be implicitly assumed each candidate 0 in the remainder of the paper.
"n particular, this holds for the detinition of linear stability where μ(0") ) I O in the notation of Chemnitz and Engel [2025, p. 7J. which is strictly weaker notion of linear stability than that of Wu et al. [2018] and Ma and Ying [2021] [see the discussion in Chemnitz and Engel, 2025, Appendix A].
5

---

Here. X is a random vector drawn uniformly at random from the training examples {at)e= Note that the distribution Px from which {æi)==1 are drawn i..d. controls the regularity of g. With this weight function in hand, we define a (semi)norm on functions of the form
/ Jgd 1x(-R.1
Su.a.oo (x)
((u Tu x - du 1) cTT + co. a E R"
where > O, c RR, and ep E R. Functions of this form are "inftnitewwidth" neural networks. We define the weighted variation (semi)norm as
Ilv,
inf DEMiS*-iX X(- CER ,eR
11g . Vll. s.t. S -u,,0o
(8)
where, if there does not exist a representation of / in the form of (7), then the seminorm' is understood to take the value +00. Here, M(S5-1 x II-R, R)) denotes the Banach space of (Radon) measures and, for μ M(S [- R, R)), || == Sga-1x1-R,10 [lpl(u, is the mhesurc-theoretic votal-variation norm.
With this seminorm, we define the Banach space of functions Vy (B on the ball B = {a E Rd : || I R} as the set of all functions f such that Iflv, finite. When = 1, lv, and Vg (B coincide with the variation (semi)norm and variation norm space of Bach [2017].
Example 3.1. Since are interested in functions defined on B for finite-width neural network fo(x) = EK UrO(w bR) + 3, we observe that it has the equivalent implementation as fo(x) - - an 12) -t)) + Co, where 0j E R. U, E Ega-1, E IR, E Rd,, and E R. Indeed. this is due to the fact that the ReLU is homogeneous, which allows us to absorb the magnitude of the input weights into the output weights (i.e., each aj = |uk, I| [w, 22 for some k, E (1,.... ......,K)), Furthermore, any ReLUs in the original parameterization whose activation threshold is outside 1 can be implemented by affine function on Biy, which gives rise to the c. x + co term in the implementation. If this new implementation is in "reduced form", iee, the collection {(u,, 43)) are distinct, then we have that [ v.,
E laz19(u,,,)) 12).
This example reveals that this seminorm is a weighted path norm of a neural network and, in fact, coincides with the path norm when g [Neyshabur al., 2015]. It also turns out that the data- dependent regularity induced by this seminorm is tightly linked to the flatness of a neural network minimum. We summarize this fact in the next theorem.
Theorem 3.2. Suppose that So is !wo-layer neural network such that the loss L(-) is twice differentiable at O. Then, [Saly, S Amar(V3
(R + /
2
The proof of this theorem appears in Appendix C. This theorem reveals that flatness implics regularity in the sense of the variation space V, (B)). In particular, also have an immediate corollary for stable minima thanks to Proposition 2.1.
Corollary 3.3. For any 0 Oaae (7;; D), Isolv,
1 + 1R++1)2C00
The main takeaway messages from Theorem 3.2 and Corollary 3.3 are that flat stable solutions smooth in the sense of V (BB). In particular, we see that the Banach space V (BB) function space study stable minima. This framework provides the mathematical foundation and sets the stage to investigate the generalization and statistical performance of stable minima.
) is the natural
We also note that, from Corollary 3.3 and Example 3.1, for stable solutions So. the step size n grows, the function fo becomes smoother, eventually approaching an affine function as 1j -> oc. This be viewed as example of the simplicity bias phenomenon of GD training [Arpit et al., 2017, Kalimeris et al., 2019, Valle-Perez et al., 2019].
'We use the notation instead of ||- to highlight that this quantity is seminorm. This quantity is seminorm since affine functions are in its null space. See Kürková and Sanguineti [2001, 2002], Mhaskar [2004], Bach [2017], Siegel and Xu [2023], Shenouda et al. [2024] for more details about variation spaces.
'The activation threshold of neuron s(w" b) is the hyperplane {x E Rd w b}.

---

Finally, we note that the function-space regularity induced by V, (Bx)) has an equivalent analytic description via a weighted norm the domain of the Radon transform of the function. This analytic description is based on the E of unfititewwitth two-layer neural networks [Ongie et al., 2020, Parhi and Nowak, 2021, Bartolucei et al., 2023]. Before stating our theorem, we first recall the definition of the Radon transform. The Radon transform of a function f L' (I24) is given by
Radon-domain total variation inductive bias
(f) = f f(x) dx, (u, E gd-1 x R. Ju==
(9)
where the integration against the (d-1) dimen-aimesso Lebesgue measure on the hyperplane Tuz x = t. Thus, see that the Radon transform integrates functions along hyperplanes.
Theorem 3.4. For every f E V (B)),, consider the canonical extension" fext : IRd - IR via its integral representation (7). It holds that Iflv, l1g ((-A) d+1 fext where fractional powers of the Laplacian are understood via the Fourier transform.
The proof of this theorem appears in Appendix D. We remark that the operators that appear in the theorem must be understood in the distributional sense (i.c., by duality). We refer the reader to Parhi and Unser [2024] for rigorous details about the distributional extension of the Radon transform. We also remark that a version of this theorem also appeared in Nacson et al. [2023, Theorem 1], but we note that their problem setting was the implicit bias of minima stability in the interpolation regime.
3.1 Stable Solutions Generalize But Suffer the Curse of Dimensionality
In the remainder this paper, we focus on the scenario where inputs {>; are drawn i.i.d. uniformly from the unit ball By (i.c., R = 1). Under this assumption, the population version of the weight function, which we denote as gp. has well-defined asymptotic behavior. As detailed in Appendix E, for |t| 2 1, (r( t) = 0, and as ||| 1 9r (r, t) x (1 |t)) While the actual weight function g in our analysis remains the empirical one derived from the data, this population behavior serves as a crucial analytical guide. Our proofs will show that the empirical g concentrates around this population version (Appendix E.2). For clarity in expressing our main results and their dependence on dimensionality, we will characterize the function space of stable minima with respect to canonical weight function g(u, L) = (1 11))++2, which captures this essential asymptotic property.
With this in hand, to be the absolute difference between the training loss and the population risk. We are able to characterize the generalization gap under mild conditions on the joint distribution of the training examples and the labels.
now characterize the generalization gap of stable minima, which is defined
Theorem 3.5. Let P denote the joint distribution of (xx y). Assume that P is supported on B$ D, D) for some D > O and that the marginal distribution of is Uniform(BB) (B4). Fix data set D D y:) Pi where each (I,, M1) is drawn i...d. from P. Then, with probability 2 8 we
have that for the plug-in in risk estimator R(f) == E (fx, - yt)²
sup (e:n))(n:
Generalization =
E (Jo(z)) -y)²] -1) -N((o) (æ.y)~p
E _ 11
4M
2244403
M n ,र...
(10)
where M max (I ( 1} and Sa hides constants (which could depend on d) and logarithmic in n and (1/8). Furthermore, for any L 2 D, it holds that
inf sup R P Dippon
sup o 0 (v: [lfe (.
GeneralizationGap((oo.. Rt) Za L2n -4i
(11)
'Since functions in V, (B are only defined on B we must consider their extension to ge when working with the Radon transform. See Parhi and Nowak [2023b, Section IV] for more details.
7

---

where the inf is over all risk estimators, Za hides constants (which could depend on d), and the sup over all distributions that satisfy the above hypotheses.
The proof of this theorem appears in Appendix F. While this theorem does show that as - co, the generalization gap vanishes, it reveals that the sample complexity grows exponentially with the input dimension (as seen by the n मंनर term in the upper bound and the n क term in the lower bound). This suggests that the not an artifact of our mathematical analysis nor the naive plug-in in empirical risk estimator being suboptimal. On the other hand, for low-norm solutions (in the sense that they minimize the weight-
saree-of-dmmmsionaliyy is intrinsic to the stable minima set Gae (17: D) D)-
decay objective), it can be shown that the generalization gap decays at a rate of Ö(n 4). where O(-) hides logarithmic factors [cf., Bach, 2017, Parhi and Nowak, 2023b]. This uncovers an exponential gap between flat and low-norm solutions, and, in particular, that stable solutions suffer the curse of dimensionality. When d 1, this result also provides strict generalization of Qiao et al. [2024, Theorem 4.3], as they measure the error strictly inside the input domain, rather than on the full input domain. Thus, our result also characterizes how stable solutions extrapolate.
3.2 Nonparametric Function Estimation With Stable Minima
We now turn to the problem of nonparametric function estimation. As we have seen that V, (BB) is natural model class for stable minima, this raises two fundamental questions: (i) How well do stable minima estimate functions in Vg (Bę) from noisy data? and (ii) What the best performance any estimation method could hope to achieve for functions in V, (B1) In this section we provide answers to both these questions by deriving mean mean-squared error upper bound for stable minima and a minimax lower bound for this function class.
Theorem 3.6. Fix a step size 1) > O and noise level σ > 0. Given a ground truth function fo V (Bf) such that Ilfollz= S B and l c - + 20) suppose that we are given data sel y: fo(ar)) Ei. where on are i.i.d. Uniform(B{) and e are i.i.d. N(0, o²). Then, with probability 2 6, we have that
1 15 (fo(z)) fo(x:)) Sd
1
(2d2 (1242)242)
[02
I044
20
B²
(12)
17
1=1
for any O Ona (1); D) that is optimized, i.e. (fe (xx)) v1)² S (fo(x:)) - u.)),, for 1,...,n.
The proof of this theorem appears in Appendix G. This theorem shows that optimized stable minima incur estimation error rate that decays as Ö( xdFT), ), which suffers the curse of dimensionality. The optimized assumption is mild as it only asks that the error for each data point is smaller than the label noise o², which is easy to achieve in practice with GD training, especially in the overpurameterized regime. The next theorem shows that the curse of dimensionality is actually necessary for this function class.
Theorem 3.7. Consider the same data- natta-ennrattig process as in Theorem 3.6. We have the following minimax lower bounds.
min(B,C)
22
d>
1,
inf f
sup (R.) of SBAfNN,
Elií - f1122 Zd
(13)
min(B.C)2 0"
d=1.
where Za hides constants (that could depend on d).
The proof of this theorem appears in Appendix H. Our proof relies on two high-dimensional construc- tions. The first construction is to pack the unit sphere gd-1 with M = cxp(S((d)) pairwise-disjoint spherical caps, each specified by unit vector u, as its center. Then, for every center u; the ReLU neuron (z)) = cœ(2t æ t) is active only on its outward-facine cap, and attains its peak value min C} by choosing a suitable 1. The second construction to observe that since the weight function g(u, 1) decreases quickly as |[| + 1 (see Appendix E), the regularity constraint lv,, S C allows us to combine an exponential number of such atoms to construct a family of "hard-to-learn" functions. Traditional lower-bound constructions satisfy regularity by shrinking bump amplitudes
8

---

(vertical changes), whereas our approach fundamentally differs by shifting and resizing bump sup- ports (horizontal changes). Our experiments reveal that stable minima actually favor these kinds of hard-to-learn functions and we refer to this as the neural shattering phenomenon.
4 Experiments
In this section, we empirically validate our claims that (i) stable minima are not immune to the curse of dimensionality and (ïi) the "neural shattering" phenomenon occurs. All synthetic data points generated by uniformly sampling æ from Bi and y = fo (x:) + N (0, o²), where the ground-trum function fo(2:) wt for some fixed vector u with ||w/|| 1. All the models are two-layer ReLU neural networks with width four times the training data size. The networks are randomly initialized by the standard Kaiming initialization [He et al., 2015]. We also use gradient clipping with threshold 50 to avoid divergence for large learning rates.?
Curse of dimensionality. In this experiment, we train neural networks with GD and vary the data set sizes in {32, 64, 128, 256, 512} and dimensions in {1, 3, 4, 4,5, with noise level o = 1. For each data size, dimension, and training parameters (17 = 0.2 without weight decay and rj = 0.01 with weight-decay 0.1), we conduct 5 experiments and take the median. The log-log curves are displayed Figure 2.
MSE vs n (Stable Minima)
MSE vs n (Weight Decay)
D=10t=0 0.1 www.pppp-0... 0.64)
De 20 1.5kpe--0.00
10
10
De 3Am0 Skpee-00.90
0..000..1,55000 0.w.ppp---ep-- 0.75)
D- StA-0 1, 5kppe-1.000
10 1
10
De 10n 1ii.:in2.Slppe--e. ww2.Slpee-0...mm
0=2 0.5ppe
De wtw.3nn-022300 20in=:0....ppe-..222.
10 2
4- 2.tpp-ee 0.14)
10
2
D-5
32
64
128
256
512
32
64
128
256
512
Figure 2: Empirical validation of the curse of dimensionality. Left panel: The slope of log MSE versus log n for training with vanilla gradient descent rapidly decreases with dimension, falling to about 0.1 at d = 5. Right panel: Training with e² (weight decay) results in slopes above 0.5 in the log-log scale.
Neural shattering. As briefly illustrated in the right panel of Figure 1, Figure 3 presents more detailed experiments. We train two-layer ReLU network of width 2048 on 512 noisy samples (a 1) of a 10-dimensional linear target. Under a large step size 7) 0.9 (no weight decay), gradient descent enters a flat / stable minimum (Amax (V)C(()) oscillates around 2/1 RS 2.2, signaling edge- of-stability dynamics). This drastically reduces each neuron's data-activation rate to < 10%, rather than reducing their weight norms. The network overfits (train MSE R 10105, matching the noise level). In contrast, with 7 0.01 plus weighhtt-dycay À 0. all neurons remain active and weight norms stay tightly bounded, so the model avoids overfitting (train MSE Rs 0.055).
Discussion and Conclusion
This paper presents nuanced conclusion on the link between minima stability and generalization:
Stable solutions do generalize, but when data is distributed uniformly on a ball, this generalization ability is severely weakened by the Curse of Dimensionality (CoD), Our analysis pinpoints the mechanism behind this failure. The implicit regularization from GD is not uniform across the input
We monitor clipping during the training. and the clipping only occurs in the first 10 epochs. Gradient clipping does prevent the training dynamics from entering efge-of stabbiiiyyy regime.

---

12"
Weightt Norm vs Activation Rate (1=0099, Amd)
Adtil PAPE ASEGHE 123PA
365
Than Uni 193 30
(1m0.99 X-0]
2.30
AmadiHessiatt (g- A
Than dhart
In Russon
204
Frud Nouron
222
207
2.0
10-1
10
25%
75%
102%
13000
20200
31000
43000
20002
10003
23000
20200
40020
50000
Weight Norm vs Activation Rate (n 01, X,0.1)
(1-0.01
2mak(Hesstbr) Curve In A-0.1)
100
120
301
sit Yauron
Find hearen
C0-
10%
20-
Tian: Less 9C
Tram MS2 dkent
0%
75%
150%
13000 20000 30003
43000 20072
10200 25000
30000
40003
50000
Figure 3: The top-left plot illustrates the neural shattering phenomenon: after large-step training each ReLU neuron (orange) is active on only a tiny fraction of the data (small horizontal support) yet its weight norm remains large, exactly as in our sphere-packing lower-bound construction where each outward-facin ReLU atom fires on very few inputs but retains full peak amplitude.
domain. While it imposes strong regularity in the strict interior of the data support, this guarantee collapses at the boundary. This localized failure of regularization is precisely what enables "neural shattering", phenomenon where neurons satisfy the stability condition not by shrinking their weights, but by minimizing their activation frequency. This causes the CoD: The intrinsic geometry of a high-dimensional ball provides an exponential increase in available directions for shattering to occur, while the boundary regularization simultaneously weakens exponentially as the input dimension d grows. This mechanism, confirmed by both our lower bounds and experiments, explains why stable solutions exhibit poor generalization high dimensions.
Several simplifications limit the scope of these results. The theory treats only two-layer ReLU networks and relies the idealized assumption that samples are drawn uniformly from the unit ball. For more general distributions, the induced weight function inherits the full geometry of the data and becomes harder to describe and interpret. Understanding this effect, together with extending the analysis to deeper architectures and adaptive algorithms, will take substantial effort, which we leave as future work.
6 Acknowledgments
The research was partially supported by NSF Award # 2134214. The authors acknowledge early discussion with Peter Bartlett at the Simons Foundation that motivated us consider the Tongtong Liang thanks Zihan Shao for providing helpful suggestions on the implementation of the experiments.
problem.
References
Devansh Arpit. Stanislaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International Conference on Machine Learning, pages 233-242. PMLR, 2017.
Richard Arratia, Larry Goldstein, and Louis Gordon. Two moments suffice for poisson approxima- tions: the chen-stein method. Annals of Probability, 17(1):-225, 1989.
10

---

Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(1):629-681, 2017.
Randall Balestriero, Jerome Pesenti, and Yann LeCun. Learning in high dimension always amounts to extrapolation. arXiv preprint arXhv:2110.09483 2021.
A. D. Barbour, L. Holst, and S. Janson. Poisson Approximation, volume of Oxford Studies in Probability. Oxford University Press, 1992.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear
regression. Proceedings of the National Academy of Sciences, 117748):3003333007 2020.
Francesca Bartolucci, Ernesto De Vito, Lorenzo Rosasco, and Stefano Vigogna. Understanding neural networks with reproducing kernel Banach spaces. Applied and Computational Harmonic Analysis, 62:1 02:1944220 94-236, 2023.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
Lucien Le Cam. An approximation theorem for the poisson binomial distribution. Pacific Journal of Mathematics, ((44):1111-111) 181-1197, 1960.
Dennis Chemnitz and Maximilian Engel. Characterizing dynamical stability of stochastic gradient
descent in overparameterizee learning. Journal of Machine Learning Research, 16(134):1-46, 2025.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, International Conference on Learning Representations, 2020.
Alex Damian, Eshaan Nichani, and Jason D Lee. Self-stabillizatin:: The implicit bias of gradient descent at the edge of stability. In International Conference on Learning Representations, 2024.
Ronald De Robert D. Nowak, Rahul Parhi, and Jonathan W. Siegel. Weighted variation spaces and approximation by shallow ReLU networks. Applied and Computational Harmonic Analysis, 74:101713, 2025.
Lijun Ding, Dmitriy Drusvyatskiy, Maryam Fazel, and Zaid Harchaoui. Flat minima generalize for low-rank matrix recovery. Information and Inference: Journal of the IMA, 13(2) 2024.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterrizd neural networks. In International Conference on Learning Representations, 2018.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages 2668-2703. PMLR, 2022.
Moritz Haas, David Holzmüller, Ulrike Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. Advances in Neural Information Processing Systems, 36, 2023.
David Haussler. Decision-theore generalizations of the pac model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision (ICCV), pages 1026-1034, 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):144, 1997.

---

Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate ReLU networks. In International Conference on Learning Representations, 2023.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems, 32, 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Michael Kohler and Sophie Langer. On the rate of convergence of fully connected deep neural network regression estimates. Annals of Statistics, 49(4):2231-2244, 2021.
Vêra Kürková and Marcello Sanguineti. Bounds on rates of variable-basis and neural-network approximation. IEEE Transactions on Information Theory, 47(6):2659-26666 2001.
Véra Kúrková and Marcello Sanguineti. Comparison of worst case errors in linear and neural network approximation. IEEE Transactions on Information Theory, 48(1 (481):2200 (:::::2222255 2002.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in weerpparametrrized non-lineat systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Chao Ma and Lexing Ying. On linear stability of sgd and input-smoothness of neural networks. Advances in Neural Information Processing Systems, 34: 34:16805- 11116660-681,,, 16817, 2021.
Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran, Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting. Advances in Neural Information Processing Systems, 35:1 182-11981 2022.
Hrushikesh N. Mhaskar. On the tractability of multivariate integration and approximation by neural networks. Journal of Complexity, 20(4):561-590 2004.
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances in Neural Information Processing Systems, 177611, 2021.
Mor Shpigel Nacson, Rotem Mulayoff, Greg Ongie, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability in multivariate shallow ReLU networks. In International Conference Learning Representations, 2023.
Kamil Nar and Shankar Sastry. Step size matters in deep learning. Advances in Neural Information Processing Systems, 31, 2018.
Behnam Neyshabur, Russ R. Salakhutdinov, and Nati Srebro. Path-SGD: Path-normalized opti- mization in deep neural networks. Advances in Neural Information Processing Systems, 28, 2015.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations, 2020.
Rahul Parhi and Robert D. Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1 2021.
Rahul Parhi and Robert D. Nowak. What kinds of functions do deep neural networks learn? Insights from variational spline theory. SIAM Journal Mathematics of Data Science, 4(2):464 489, 2022.
Rahul Parhi and Robert D. Nowak. Deep learning meets sparse regularization: A signal processing perspective. IEEE Signal Processing Magazine, 40(6):63-74, 2023a.
Rahul Parhi and Robert D. Nowak. Near-minimax optimal estimation with shallow ReI.U neural networks. IEEE Transactions Information Theory, 69(2): 125-1139, 2023b.
12

---

Rahul Parhi and Michael Unser. Distributional extension and invertibility of the k-plane transform and its dual. SIAM Journal on Mathematical Analysis, 56(4):4662 -6866, 2024.
Dan Qiao, Kaiqi Zhang, Esha Singh, Daniel Soudry, and Yu-Xiang Wang. Stable minima cannot overfit in univariate ReLU networks: Generalization by large step sizes. In Advances in Neural Information Processing Systems, volume 37, pages 21163-94208, 2024.
Johannes Schmidt-Hieher Nonparametric regression using deep neural networks with ReLU activa- tion function. Annals of Statistics, 48(4):1875 1897, 2020.
Joseph Shenouda, Rahul Parhi, Kangwook Lee, and Robert D. Nowak. Variation spaces for multi- output neural networks: Insights on multi-task learning and network compression. Journal of Machine Learning Research, 25(231):1-40, 2024.
Jonathan W. Siegel and Jinchao Xu. Characterization the variation spaces corresponding to shallow neural networks. Constructive Approximation, pages 1-24, 2023.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:1810.08033, 2018.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 1st edition, 2009, ISBN 9780387790511.
Guillermo Valle-Perez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions, In International Conference on Learning Representations, 2019.
Vladimir Vapnik. Statistical Learning Theory. Wiley, 1998.
Roman Vershynin. Vighh-Diensional Probubility: An Introduction with Applications Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
ISBN 978- 1101411441194 doi: 10.1017/978 108231596.
Martin J Wainwright. High-dimensionne statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect. In International Conference Learning Representations (ICLR), 2022.
Larry Wasserman. Minimax theory lecture notes. https://ww..stt cmu, edu/1arry/==m// minimax. pdf, 2020. Accessed: 2025-05-21.
Lei Wu, Chao Ma, and Weinan E. How SGD selects the global minima in over-parameterized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31, 2018.
Yunfei Yang and Ding-Xuan Zhou. Optimal rates of approximation by shallow ReLU* neural networks and applications to nonparametric regression. Constructive Approximation, pages 1-32, 2024.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Kaiqi Zhang and Yu-Xiang Wang. Deep learning meets nonparametric regression: Are weight- decayed DNNs locally adaptive? In International Conference on Learning Representations, 2023.
13

---

Supplementary Materials
Additional Experiments
15
A.1
Empirical Evidence: High Dimensionality Yields Neural Shattering
15
A.2 Neural Shattering and Learning Rate (dim=5)
16
A.3 Neural Shattering in the Underparametrized Regime
17
A.4 Neural Shattering for GELU Networks
18
A.5 Empirical Analysis of the Curse of Dimensionality
19
A.6 Empirical Analysis of the Curse of Dimensionality _...............................
20
A.7 Empirical Analysis of the Curse of Dimensionality (IIII.
22
Overview of the Proofs
24
B.1 Proof Overview of Theorem 3.2.
................................ ................................
24
B.2 Proof Overview of Theorem 3.5
25
................................
B.3 Proof Overview of Theorem 3.6
25
B.4 Proof Overview Theorem 3.7
26
B.5 Discussion of the Proofs
27
C Proof of Theorem 3.2: Stable Minima Regularity
28
D Proof of Theorem 3.4: Radon-Domain Characterization of Stable Minima
30
Characterization of the Weight Function for the Uniform Distribution
30
E.1 The Computation of the Population Weight Function
30
E.2 Empirical Process for the Weight Function
34
Proof of Theorem 3.5: Generalization Gap of Stable Minima
36
F.
Definition of the Variation Space of ReLU Neural Networks
36
F2
Metric Entropy and Variation Spaces
36
F3
Generalization Gap of Unweighted Variation Function Class
37
E4
Concentration Property on the Ball: Uniform Distribution
F55
Upper Bound of Generalization Gap of Stable Minima
38
G Proof of Theorem 3.6: Estimation Error Rate for Stable Minima
42
G.I Computation Local Gaussian Complexity
42
G.2 Proof of the Estimation Error Upper Bound
H Proof of Theorem 3.7: Minimax Lower Bound
44
The Multivariate Case ................................
H.2 Why Classical Bump- Type Constructions Are Ineffective
................................
H.3 The Univariate Case
I Lower Bound on Generalization Gap
51
L1 The Lower Bound Construction Can be Realized by Stable Minima
51
J Technical Lemmas
56
J.1 Information-Thooue tools
56
J.2 Poissonization and Le Cam's Inequality
57
14

---

A Additional Experiments
A.1
Empirical Evidence: High Dimensionality Yields Neural Shattering
Weight Nerm Activation Rate in=0.5 0.S, dim=l)
Weight Norm vs Activation Rate (n=0..s, dim-
10"
Juttinn peuroes 624 (308))
10-
Amtun rearsec 1441 oxe 218 Soi
0007
8.224
10a
I1 Neuron Final Neuron
10
In Neuron Firil Nevron
104
10a
10: 1,
10 -
10-3
0%
25%
100%
25%
50%
75%
100%
Woight Norm vs Activation Rate In-0.55 dim-3)
Weight Narm vs Activation Rate On=0.5, 4)
Trai Mac 20111
Trais Laer
0.223
10
Neurnn Nouron
10a
Int Neumn
Rral
30a
10a
10-3.
10-2
2
10-2
20-2
10
30
0%
25%
50%
75%
100%
0%
25%
50%
75%
100%
Weight Norm vs Activation Rate (n=0 5, dim=5)
Weight Norm vs Activation Rate (n=-D,,, dim-6)
detiin nerrne 145.6)) Trair Mac
10.
Antua teurore d4s) ooe (K Train 6.2623
10a
In hauron
10a
In Neuron
Final Nouron
Fiall Neuron
10
10a
10
10
10-1
10-3
0% 25%
75%
100%
50%
75%
10066
Figure 4: Comparison across input dimension d for a two-layer ReLU network of width 1024 trained on 512 samples for 20000 epochs with learning rate 1) = 0.5. At d = 1, all neurons extrapolate (0% active), while as d increases the fraction of neurons surviving training rises dramatically (up to 65% at d = 6). Simultaneously, the training loss monotonically decreases whereas the training MSE increases with d, demonstrating that neural shattering under large learning rates may be the key driver of the curse of dimensionality in stable minima.
15

---

A.2 Neural Shattering and Learning Rate (dim=5)
Training Curves (n=0. A=
10"
Weight Norm Activation Rate (n-D.4 4, O=
Actuo resrone: 5/012244 (53 290 Than 02300
Thain Loss Ivs
10
Nolse Baseline (c5=0.25)
10
Initial Newuron Rro Neuron
104
161
10
10a
10-2
10"
10-2
25%
75%
100%
5000
18000
15000
20000
25000
Training Curves (g=0.2. X=
10
Welghtt Norm vs Activation Rate 1n= Am0)
Serie nearver 1224 (100
10
Train Loss IVS no
Train MSE (os clean!
0232
(c*=0.25)
101
Inttaal Neuron
10a
Finel Nouron
101
10
100
10-2
10-3
075
75%
100%
10000
20000
30000
40000
50000
Training Curves (n=0.11 A-a)
Weight Norm vs Activation Rate (n- X=
16a
Train Loss Ivs rotay!
Tren Loee e C307
122402024 (006.50
Noisa (.2-0.55)
Train MSE (ve deani
101
10a
Rro Nizooon
100
101
10-1
100
10
10
10-3
10-2
0%
25%
50%
75%
100%
20000
40000
50000
80000
1000000
ning Curves (n-0.05, A-0)
Weight Norm vs Activation Rate 0.05, A=0) heatgra: 33242004 290l
eoay!
10
10a
Thiir MSF (us clean)
Dian 2,024
Noise Baseins io
10
Rraal Mearon
Inkial heuron
101
109
100
10:
10
10-2
10-2
25%
75%
100%
50000
100000
150000
200000
Figure 5: Effect of increasing learning rate 7) on shattering (n x epochs 10000): as 7) grows, the stability/flatness constraint forces an ever larger fraction of neurons to activate only on small subset of the data (neural shattering). To further decrease the training loss, gradient descent correspondingly increases the weight norms of the remaining active neurons.
16

---

A.3 Neural Shattering in the Underparametrized Regime
Weight Norm us Acthvation Rate (p=0 dim-16)
Weight Norm Acthvation Rate (p-0 5, d6m-16)
Weight Norm vs Acthvation Rate (n-0 dim- 16)
The 2202
2220
The
Inttal Heuron Pis Meute
Inft Heuren FiN
Iritall
Fins Meuten
300
1.0
3.2
30
10
30
10
10-1
10-1
0%
25%
50%
75%
130%
5%
25%
50%
75%
130%
0%
25%
500
75%
130%
(a) W/ 32, weight decay-
(b) W 48, weight decay
0
(c) W 64, weight decay
Weight Norm vs Activation Rate (n=055 S. dim-16)
Welght Norm vs Activation Rate (n=0 dlm=16)
Weight Norm vs Activation Rate (n=05 S. dim- 16)
1202 12305N1
EAV 1200500
The
The
The
100
30
301
3.0
102
3.2
10.4
10a2
10"2
10
10a1
57
25%
35%
73%
150%
5%
25%
30%
73%
130%
25% 53%
73%
150%
(d) W = 32, weight decay = 0.05
(e)W-
W = 48, weight decay = 0.05 (f) W = 64, weight decay- = 0.05
Figure 6: Persistence of neural shattering across width in the underparametrized regime. Each panel plots per-neuron activation rate versus weight norm after training a two-layer ReLU network on n 1024 samples with learning rate 17 = 0.5. Columns correspond to widths W E {32, 48, 64); the top row uses no weight decay, and the bottom row uses mild decay (A = 0.05). The parameter count is Wd + W + 1, so W = 64 is mildly overparameterized while W = 32, 48 are strictly underparamettrizzed Across all widths, we observe clear neural shattering: neurons with smaller activation fractions carry larger weight norms. This monotone trend is especially visible in the stable-minima panels (A = 0), exactly as predicted by our theory. The weight-decay panels serve only as a high-activation baseline to calibrate what "few activations" means, underscoring how exceptionally low the activation rates are at stable minima.
Whightt Nerm vs Activation Rate (n=0.5 S. dim=32)
Whight Nerm vs Activation Rate (n=0.5, dim=48) Whightt Nerm vs Activation Rate (n=055 dim=64)
The
Tha Vaa 8030
The
10
10.
al
10
12a
30
10
10
10
10
30
30
5%
25%
50%
75%
150%
5%
25%
50%
75%
150%
0%
25%
53%
75%
150%
(a) d - 32
(b) d = 48
(c) d - 64
Figure 7: Each panel shows the relation between neuron activation rate and weight norm after training a two-layer ReLU network of width W = 16 on n = 1024 samples drawn from a linear target with learning rate 17 0.5 for d E (64, 48, 32). This observation indicates that neural shattering is a generie feature of stable minima, robust even when in small network.
17

---

A.4 Neural Shattering for GELU Networks
This set of stable minima serves as a prism through which we can understand the emergent behaviors of the learning process. The data-dependent weight function g(u, t), which is central to our analysis, arises directly from the structure of the loss Hessian and provides a static characterization of the implicit bias of gradient dynamics. A smaller value of g(u, 1) for a neuron (u, 1) implies that the stability condition imposes a weaker regularization, allowing for larger weight magnitudes for that neuron.
This static view is intimately connected to the underlying learning dynamics. In high-dimensional spaces, a neuron's s activation boundary can easily drift to a region where it activates on only a small fraction of the data points. For such a neuron, the gradients it receives are sparse and localized. If the few data points it activates on are already well-fitted, the local gradient signal can vanish, causing the neuron's 's parameters to become effectively "stuck" or stable. The small value of g (u, t) in these boundary regions creates "space" within the class of stable functions for these trapped, yet aparsely-activating neurons to exist, a possibility our lower bound construction then formalizes and exploits.
The ReLU activation function is analytically convenient for this analysis because its hard-sparsity property: a strictly zero gradient for non-activating inputs. This leads to a sparse loss Hessian, allowing for a clean derivation of the weight function g(u, t). However, the underlying "stuck neuron" dynamic is not necessarily unique to ReLU. Activations like GELU provide a non-zero gradient for negative inputs, but this signal is weak and decays quickly away from the activation boundary. It is therefore plausible that this weak gradient is insufficient to pull a "stuck" neuron back from the data boundary once it has drifted there and its activation rate has diminished. This suggests that the fundamental mechanism enabling 'neural shattering" may persist. This hypothesis motivates an empirical investigation into whether the same phenomena of neural shattering also manifests in networks trained with GELU activations.
Weight Norm vs Activation Rate (ng-0.5, 0.5, dim-3)
Weight Norm vs Activation Rate (n-0,5,, dim-4)
Accies Lssz 2572
Actis 3201804 5L.%) Lasi 6.4
10
10
Neuron
10
100
10
20
10
20 7
10-1
20-3
0%
25%
50%
75%
100%
0%
25%
50%
75%
100%
Weight Norm vs Activation Rate (n=0.5 0,5, dim=5)
Weight Nerm vs Activation Rate (n=0.5 5. dim=6)
Active 112/001411000000 (21.99) Thar Noc 2243
Active neurone 335/1004 (1225)
Traie No: 6.257
102
Intial Ncuron Final Neuron
10-
an Neuron
Rrol Nouron
10a
10
20
10-1
20-2
10
30
0%
25%
50%
75%
100%
07%
25%
50%
75%
300%
Figure& 8: Comparison across input dimension d for a two-layer GELU network of width 1024 trained on 512 samples for 20000 epochs with learning rate 1/= 0.5. The neural shattering behavior observed for ReLU networks in Figure 4 also appears here with GeLU activations. In particular, we can see the trend more clearly: neurons with lower activation rates tend to develop larger weight norms, highlighting that the neural shattering mechanism extends beyond piecewise-lined activations.
18

---

A.5 Empirical Analysis of the Curse of Dimensionality (I)
We conduct the following experiments in the setting where the ground-truth function is linear with Gaussian noise o² The width of neural network 4 times of the number of samples.
MSE vs (Dim=1, A=
MSE vs (Dim=1, X>0)
10
10
10
10
0-0.11 0.38
n=02 (Slope: 0.38, 83: 0.72)
n-0.4 (Slope: 0.49. 8": 0.78)
10
10-2
ne0.8
MSE (Dim=2, A=
MSE (Dim=2, A>0)
100
100
10-1
10-1
0=0.1 ISlope: 0.47, 8": 0.94
A²:
10
0=0.4 (Slope: 0.51 R": 0.97)
10-2
0.6.6 (Slape: 0.01,
A-0.1 [Slope: -0.91 0.95)
128
256
512
128
256
MSE vs n (Dim=3, x=0)
MSE vs (Dim=3, X>0)
10a
10a
10-1
10-1
n=0.1 (Slope: 0.27, R²: 0.87)
n=02 (Slope: -0.55 0.81)
10
(Slope: 0.18.8":
10-2
0.6 (Slope: 4.25, R 0.99)
A-0.1 [Slope: -0.08. 0.97)
32
64
128
256
512
32
64
128
256
512
Figure 9: Log-log plots of the mean squared error (MSE) versus sample size n (Part I). Each curve is regressed by the median result over five random initializations (lighter markers), while the shallow markers denote the other runs. As the input dimension increases, the slope the fitted regression line becomes progressively shallower, indicating slower error decay.
19

---

MSE VS n (Dim=4, λ=
MSE Vs (Dim=4, \>0)
10
10
10
10
n=0.1 (Slope: 0.15, 0.995
ne02 (Slope: 0.14, R 0.83)
10
(Slope: 4..1..6;
10
0-0.6 ISlope: 0.10, 0.50)
A-0.1 (Slope: 0.75, 8.7 0.77)
32
64
128
256
512
32
64
128
256
512
MSE vs n (Dim=5 5, A=
MSE Vs n (Dim=5, Λ>0)
10
10
10
10
ne0.1 ISlope: 0.90)
02 (Slope: -..00 8+, 0.95)
0-0.4 (Slope: 0.83)
10
10
ISlope: 0.13)
A-0.1
1.00. 0.91)
32
64
128
256
512
32
64
128
256
512
Figure 10: Log-log plots of the mean squared error (MSE) versus sample size illustrating the curse of dimensionality in stable minima (Part II). We can see dimension 5, the slope almost flat and even the large-step size cannot save the results (even worse than small step-size).
A.6 Empirical Analysis of the Curse of Dimensionality (II)
We conduct the following experiments in the setting where the ground-trute truth function is linear with Gaussian noise 2² 0.25. The width of neural network 2 times of the number of samples.
MSE vs n (Dim=2, λ=0)
MSE vs n (Dim=2, ^=0)
10-1
10
10-2
10-2
0=0.05
0.90)
ne0.1 ISlope: -0 0.89)
02 33.5p:--0.58, R3: 0.95)
10-1
0=0.3 (Slpee
0.96)
10-1
0=0.4 ISlope: 39, RR:
Aud 01
-1.44, 0.92)
32
64
128
256
512
32
64
128
256
512
Figure 11: Log-log plots of the mean squared error (MSE) versus sample size n (Part III). Compared the previous experiments, this setup reduces the noise level 0.5, applies weight decay X 0.01, and constrains the model width to 2n.
20

---

MSE vs (Dim=3, x=0)
MSE vs (Dim=3, X>0)
10
10
10
ne0.05 0.19,8%:11 1.00)
m= (Stpp: -022, 8 0.87)
0=02 0.19, 0.87)
10
(Slope R!: 0.95)
10-3
4-0.4 ISlope -0.22 8 0.8d)
A= ISiope: -1.17, R2: 0.91)
32
64
128
256
512
32
64
128
256
512
MSE vs n (Dim=4, 2=0)
MSE vs n (Dim=4, Λ>0)
10
10
10
10
n=0.05
0.94)
m=0.1 (Sope: -0.10, R2; 0.97)
n=02 (Slope: 0.09, 8 0.88)
10-3
0=0.3
0.73)
10-3
n-0.4 (Slope: -0 RP; 0.64)
^-0.01 (Slope: -122, R 0.99)
32
64
128
256
512
32
64
128
256
512
MSE vs (Dim=5, x=0)
MSE vs (Dim=5, X>0)
1
1
10-2
10-2
n=0.05 (Slope: 0.08. R²: 0.97)
ISlope
n=02 (Slope: 0.07, R*: 0.98)
10-1
ne0.3 1Slope 09, 0.96)
10-1
0.82)
-123. R
32
128
256
512
128
256
512
Figure 12: Log-log plots of the mean squared error (MSE) versus sample size (Part IV). The log-log MSE vs. n curves still exhibit progressively flattening slopes as the input dimension grows, demonstrating the enduring curse of dimensionality in stable minima.
21

---

A.7 Empirical Analysis of the Curse of Dimensionality (III)
We conduct the following experiments in the setting where the ground-truth function Hölder(122 f()) = - |u]
x/ + 1 with Gaussian noise o² 0.25, where uy is uniformly sampled from gd-1. The width of neural network is 2 times of the number of samples.
MSE vs (Stable Minima)
MSE (Weight Decay)
D-11A= 11-11==0.01.500 wwwp000pppp........00 0.09)
D=212=0.01.500 01ppp..1-.-........
D-31X-0.01 S.7ee-0.766 0.6
10-1
10
10
10-2
De 0.0/==005.pp00..777
D 5.5ppee-.....00..0 0..60
De 4 0.120
128
256
512
128
256
512
Figure 13: Log log plots of the mean squared error (MSE) versus sample size n (Part V). We can see the generalization slopes of stable minima degrades as dimension increase from to 4.
MSE vs n (Dim=1, x=0)
MSE vs n (Dim=1, λ>0)
10
10
10
ne0.05 (Slope: 0.79, R 0.8)
10:
n=0.1 (Slope: 0.24, R 0.46)
(Slope: R²
0-0.4 (Slope: 0.77, 8 0.88)
A- (Slope: 0.68, R 0.871
32
64
128
256
512
32
64
128
256
512
MSE vs (Dim=2) 2, x=
MSE vs (Dim=2, X>0)
10 -
10-1
0e0.05 -0400 A2; 0.89)
10
n=0.1 (Slope: 0.45, 8²: 0.94)
ne02 (Slope: 0.50, R² 0.90)
A²:
A-O. -0.72 R²: 0.98)
32
64
128
256
512
32
64
128
256
512
Figure 14: Log- plots of the mean squared error (MSE) versus sample size n (Part VI). The panels on the left are the log-log plots for stable minima trained in 7) E (0.05, 0.1, 0.2, 0.4]. while the panels on the left are the log-log plots for low-norm solutions trained in weight decay X = 0.01.
22

---

MSE vs (Dim=3, X=
MSE vs (Dim=3, A>-))
10
10
10
n-0.05 ISlope: 0.21, 0.87)
10-2
ne0.1 ISlope: 4.23, R 0.86)
-0.28
0-0.4 ISlope: 0.19. 8?: 0.70)
A- (Slope: 0.76, R 0.98)
32
64
128
256
512
32
64
128
256
512
MSE vs n (Dim=4, A=
MSE vs n (Dim=4, A>0)
10
10-1
10
ne0.05 ISlope: R²: 0.94)
10-2
n-0.1 1Slope: 40 09, AP: 0.95)
0=02 (Slope:
0.90)
ISlope: 92122. 0.80)
A-0. R 0.90)
32
64
128
256
512
32
64
128
256
512
Figure 15: Log-log plots of the mean squared error (MSE) versus sample size (Part VII). The panels on the left are the log-log plots for stable minima trained in different learning rate r) (0.05, 0.1, 0.2, 0.4), while The panels on the left are the log-log plots for low-norm solutions trained weight decay 0.01.
23

---

B Overview of the Proofs
In this section, we provide an overview the proofs of the claims the paper. The full proofs are deferred to later appendices. We introduce the following notations we use in our proofs and their overviews.
Let (e) and (e() be two functions in variable of e. For constants o, E IR (independent of e), the notation
(0()) (e))
(e)
means that (fE) I (x)) and b b(E) S ((=). We may directly use the notation x if the constants are hidden (we may use the simplified version when the constants are justified).
[(x) = (g(()) means there exist constants e > and zig > such that
0 S f(x) S <cg(a), V 2 z0-
Intuitively, for sufficiently large x, fx) grows most fast as g(x),, up to constant factor. We may also use f(x) & g(x).
f(x) ()((z)) means there exist constants d' and 21 > 0 such that
0 f d' g(z) S fx))
A a 2 I1.
Intuitively, for sufficiently large z, f fz) grows least fast as g up constant factor.
f(x) (g(()) means there exist constants C2 and 22 > 0 such that
S cig(()) < f(x) c2g()), VオΣ
Equivalently,
f(x) = 0(g(x)) - (f(x) Ogg(z))) and [f(x) {)((())))
Intuitively, for sufficiently large x, f (a) grows at the same rate as g(x), up to constant factors.
B.1 Proof Overview of Theorem 3.2.
We consider the neural network of the form:
K
fo(x) Σ Up dw bx) + +.
(14)
The Hessian matrix of the loss function, obtained through direct computation, is expressed as:
V2C(O) = 1 Σ (affo(a))
1 n Σ (fo(z.) - u) (zfo(z.).
(15)
Consider v to be the unit eigenvector (i.e., |lal| 1) corresponding to the largest eigenvalue of the matrix En (Vefe(æ.)) (V fe (xx T. Consequently, the maximum eigenvalue of the Hessian of the loss can be lower-bounded follows:
Amax V)C(0) v C())(
( n
1
Vofo(2))
Amax
(16)
(Temm A)
(fo(x.) - 4 V Vofe(z,)o.
72
(Temm

---

Regarding (Term A), its maximum eigenvalue at a given & can be related to the Vg seminorm of the associated function f = fo. Letting St = (0, R), Nacson et al. [2023, Appendix F.2] demonstrate that:
1 n
K
(Term A) = Amax
Vololaz))
21+2
bx), (17)
where We -wx wux/|/wa/
E gd-1 by bx/ 1|11|12 and
((w, b) = xP b)2 E X bl
x > b)
V
[[X
X > B]1..
(18)
For (Term B), an upper bound can be established using the training loss L(0) via the Cauchy-Schward inequality. This also employs a notable uniform upper bound for o Lemma C.I:
as detailed in
1 n
n
(Term B) S
(fe(æ;)) y1)²
-1))
vv Vafaoa()))) s 2(R 1) 2C(0). (19)
B.2
Proof Overview of Theorem 3.5
This proof establishes an upper bound on the generalization gap for stable minima in O D). The strategy leverages the structural properties of these solutions, which are captured by data-dependent weighted variation norm.
First, we recall from Corollary 3.3 that any stable solution fe has a bounded norm, Ifelv, I A. The weight function g determined by the training data. This data-dependent nature is central to our analysis. To bound the generalization gap, we must translate the constraint on the weighted norm I/lv, into a bound on the standard, unweighted norm [/|v. This possible only in regions where the weight function is bounded away from zero. This naturally suggests a decomposition of the input domain into two parts: a "well-behaved" region where g has a positive lower bound, and the remaining region where g may be arbitrarily close to zero.
To facilitate tractable analysis, we introduce the deterministic population weight function gP as reference. We then bridge the two using empirical process theory. As established in Appendix E.2 (Theorem E.5), the uniform deviation between g and its population counterpart is bounded by statistical error term 6 = Ó(vd/n) with high probability. This allows us to leverage the well- behaved properties of gp to characterize the behavior of the empirical function g.
For inputs from Uniform( (TBG), this population function behaves like (1 |t])d+2 (see Appendix E), where |t] is the distance of neuron's 's activation boundary from the origin. This behavior motivates a specific geometric decomposition: an inner core B (where it| < E) and an outer annulus Ad
For the inner core B the key step is to translate the bound on Ifl to a bound on the standard (unweighted) norm |flv. To do this, we need lower bound on the empirical weight g within the core. Using gP our analytical proxy, establish that Imin 2 !P,min En Rs dd42 En. This step requires validity condition: must be large enough such that the geometric term dd2 dominates the statistical error e.. With the unweighted norm now bounded, we utilize metric entropy arguments (e.g., Proposition F.4 and results from Parhi and Nowak [2023b]) to bound the generalization error in d(d+2)
the core that scales with O 2d43
). In the annulus Ag the contribution is small, scaling ad4o
2+3
with OEE).
B.3
Proof Overview of Theorem 3.6
The proof for Theorem 3.6 establishes upper bound the mean squared error (MSE) for estimating a true function fo using a stable minimum fe. The overall strategy shares similarities with the proof of the generalization gap, particularly in its treatment of the data-dependent function class.
The argument begins by leveraging the property that a stable minimum @pa((y: D) corresponds to neural network fe with bounded weighted variation norm I V,, where g is the empirical
25

---

weight function. The theorem also assumes the ground truth fo lies in similar space. A key condition that fo is "optimized" such that its empirical loss is worse than that of fo- This crucial allows us to bound the empirical MSE primarily by an empirical process term involving the noise terms Es-
To bound this empirical process, the proof again decomposes the input domain Bf into strict interior ball By and an annulus Aç- In the outer shell, the contribution to the MSE is controlled by the function's 0 bound. For the strict interior By- we analyze the difference function ʃa = so fo- Consistent with our generalization analysis, empirical weight function can be reliably analyzed via its population counterpart. This allows us to bound the unweighted variation norm of fa over the core, which is then used to bound the empirical process via local Gaussian complexities (as detailed in Appendix G).
the results from Appendix F.2 ensure the
The bounds from the annulus and the MSE is minimized by choosing an optimal E. This balancing yields the final estimation error rate presented in Theorem 3.6, connecting the stability-induced regularity and the "optimized" nature of the solution to its statistical performance.
then summed. The resulting expression for the total
B.4 Proof Overview of Theorem 3.7
The proof establishes the minimax lower bound by constructing a packing of functions within the specified function class V (BB) and then applying Fano's Lemma. The construction differs for multivariate (d 1) and univariate (d cases.
Multivariate Case (d > 1) The core idea is to use highly localized ReLU atoms that have a small Vg norm due to the weighting g(u, t) vanishing near the boundary ((t) - 1), yet can be combined to form sufficiently rich and separated set of functions.
1.0
0.5
0.0
1
Figure 16: The ReLU atoms only activate on the localized spherical cap and with L (BB) (B4)) -norm equal to As dimension increases, data points will concentrate the boundary region and the choice of directions increase exponentially.
1. Atom Construction: We utilize ReLU atoms t (x)= = =-2u -1 - (2)) as defined in Construction H.4 (see Eq. (105) for the unnormalized version). These atoms _ -oromaallie have an (IB @ aa.= x d+1 (Lemma H.1), and a weighted
variation norm (2,..> lv, = 2d+2 (Lemma H.2, Eq. (116)). The small Vo norm is crucial.
2. Packing Set: Using packing of K x (d-1) disjoint spherical caps on Sd-1 (Lemma ( H.3), we construct family of functions L& (x) = Σ &u (x) for & E ()1,
lemma (Lemma J.2), we can find a subset E C {-1,1] such that log | x K x (d-1) and for any distinct Se, E [fe)ces their di-distance [/5 Je Z The total variation norm [ S Ke2d+2 x gd+3 which is significantly smaller than when 1.
By Varshamov-
26

---

3. Leveraging Fano's Lemma: (Proposition H.S) The KL divergence between distributions induced by f& and for (L(P)))Pe)) X n p To apply Fano's Lemma (see Lemma J.1). we need to satisfy the condition (141) that ne²/o² X log || x 5 == -dd-1), which implies x (o² /n) क and the minimax risk is then given by E IIf Alli2 2 =² (a² /n) /n)=T.
Univariate Case (d = 1) The high- digh-dimensional spherical cap packing is not applicable. Instead, we use scaled bump functions and exploit the simplified ID Vg norm.
1. Function Class: For d = 1, if we assume f is smooth, then Iflv, = IIf" Mlle = dx (from Theorem 3.4 and leading to the class in Eq. (121)).
Sh (=)))(( - |=])²
2. Atom Construction:
We construct functions (x(x) as smooth bump functions, each supported on distinct interval of width =² near the boundary (e.g., x E [1-E-(K (---(k11))) =² 1-
E + k=))). These are scaled such that [|øx|ll2 E. Due to the (1 (1-1x)) X E factor in the
Vg norm and [_, (x)) dæ x 1/62, the weighted variation is | x e (1/6²) s.
3. Packing Set: A family fe(z) E &x (xx) is formed with K = 1/E terms. Using Varshamov-Gilberr (Lemma J.2), we find a subset E with log | x K x 1/8 such that for distinct fe, fer, the di=dditance is Il.fe fe Il & V - VE.
4. Leveraging Fano's Lemma: The KL divergence is KL(Pel)Pg) x n( (E)> nE/o². Fano's 's condition (141) ne/o²
02222 < log E x implies E = (o² (2//n)//2 The minimax risk
is then fflff - flli.a Z (VE)² = E x (o2/n)!!?
B.5 Discussion of the Proofs
notable feature in the proofs for the generalization gap upper bound (Theorem 3.5) and the MSE upper bound (Theorem 3.6) is the strategy of decomposing the domain By into an inner core Bf_, and an annulus A.. This decomposition, involving trade-off by treating the boundary region differently, is not merely a technical convenience but is fundamentally motivated by the characteristics of the function class Vg (BB)) and the nature of "hard-to- lo-arn""" functions within it.
The necessity for this approach is starkly illustrated by our minimax lower bound construction in Theorem 3.7 (see Appendix H for construction details) and Proposition I.1. The hard-to-learn functions used establish this lower bound are specifically constructed using ReLU neurons that activate only near the boundary of the unit ball (i.e., for æ such that u x z 1). The crucial insight here is the behavior of the weight function g(u, 1) x (1 11)222 (see Appendix E). For these moundary-acttvatinn
neurons, [4] is close to 1, making g(u, 1) exceptionally small. This allows for functions that are potentially complex or have large unweighted magnitudes near the boundary (the annulus) still possess small weighted variation norm If flv thus qualifying them as members of the function class under consideration. Our lower bound construction focuses almost exclusively on these boundary phenomena, as they represent the primary source of difficulty for estimation within this specific weighted variation space.
The upper bound proofs implicitly acknowledge this. By isolating the annulus Ad, the analysis effectively concedes that this region might harbor complex behavior. The error contribution from this annulus is typically bounded by simpler means, often proportional to its small volume (controlled by 2) and the 1 norm of the functions. The more sophisticated analysis, involving metrie entropy or Gaussian complexity arguments (which depend on an unweighted variation norm that becomes large as Ifll,, /Ed+2 when restricted to the strict interior = is applied to the "better-behaved interior region. The parameter is then chosen optimally to balance the error from the boundary (which increases with E) against the error from the interior (where the complexity term effectively increases as shrinks).
This methodological alignment between our upper and lower bounds underscores self-consistency in our analysis. Both components of the argument effectively exploit the geometric properties stemming from the uniform data distribution on a sphere and the specific decay characteristics of the data-dependent weight function y near the boundary. The strategy of "sacrificing the boundary" in the upper bounds is thus a direct and necessary consequence of where the challenging functions identified by the lower bound constructions.
27

---

C Proof of Theorem 3.2: Stable Minima Regularity
In this section, prove the regularity constraint of stable minima. We begin by upper bounding the operator norm of the Hessian matrix. In other words, we upper bound le' Volo())) under the constraint that ||l12
Lemma C.I. Assume [o(x) E v.o(w x + by) + 3 is a two-layer ReLU network with input a Rd such that ||>l| I R. Let represent all parameters {wk. by, Uk B) Assume fo(x) is twice differentiable with respect to 0 at Then for any vector v corresponding perturbation in such that || = 1, holds that:
Vofo(z) 2
(20)
Proof. Let the parameters be 0 [w) w b1 bg. ...... UK B) The total number of parameters is N = K x d K + K + = K K(d+ (dd+2) 2) + 1. Let the corresponding perturbation vector be v E RV structured as: v = (a ..... a T :1,... 8x n..... T..
.),,, 7k.4) where a E R corresponds to Wk. R corresponds to by, 7 R corresponds to uhs and IR corresponds 3. The normalization constraint is
K
7 + 22
(21)
We need compute the Hessian matrix (a)((.). Let 2 we assume twice differentiabilityy 2 * 0 for all k, the Hessian (o) is block diagonal, with K blocks corresponding to each neuron. The k-th block, ViL (o(r). involves derivatives with respect The relevant non-zero second partial derivatives defining this block are:
w + by and 1₁- 1(2 0). Since
0% = [w] bR, ux)
0² fo Owyder
8. (Vw, So)
(vn (z))==zx))e))) (zx)az) = (1 (=x)ax 1
Jeg
Buc
8 fo
8
0f0 Ubu
0 Dos
(vael (zu)) ('(zz) l
3b,00s
All other second derivatives within the block are zero, as are derivatives between different blocks or involving 3. The k-th block of the Hessian is thus:
82 fo (Swr) fa 0² obe fe Boguwx
8 Swn, ab o² fo (Ob,) o Dug
8 fo Twz+er a fo ab des 8 (8ux)
Odxd
0a
L
V (oL))
0
0
1
(22)
1,00
1
0
where Odxa the d zero matrix and 0, the d-dimensional zero vector. The quadratic form v (z)o( becomes:
K
0 Oaxd 0g
1
Ol òu
TaT
7k)
0
1;
k=
1
1
Tkk
(a (1 (1x)) + m11x
Jaa + 7 (1.)6))
(23)
K
2. 14 7A (af 5k)
k=1
28

---

Now, we bound the absolute value:
K
K
10 Vofe((z)o)
2 1a na(aff + -66)
2 1x 111l1ala + oxl
k=1
2/7x ((0 (ōkl)
[|aaaa/aa + 16xl)
(Cauchy-Schwane
K
2R
7h |l1 1/2 + Σ
7x T
k=1
1=1
K
K
S 2R
7
cc 113 +22
Σ 7
Σ 0%
(Cauchy-Schward on sums)
22
vi+ 2v Σ th vI
2
Σ
k
$ 2 + 1).
Now we are ready to prove Theorem 3.2.
Proof of Theorem 3.2. Without loss of generality, we consider neural networks of the following form:
fe(x)) Σ uy dww bx) B.
(24)
The Hessian matrix of the loss function, obtained through direct computation, is expressed as:
n Σ (Volo(m))) (Voloo() 1 Σ (Jo(m.) yt) (a.o(
V2L(0)
(25)
Let be the unit eigenvector (i.e., ||o|| = 1) corresponding to the largest eigenvalue of the matrix (2 lower-bounded as follows:
the maximum eigenvalue of the Hessian matrix of the loss can be
Amaxx V2C(O)) 20 TVCC(())
1 (
Amax
(ooolaa))
(26)
(Tem
(fo(z.) u Vafo(z;)v.
(Temm
Regarding (Term A), its maximum eigenvalue at given 0 can be related the V, norm of the associated function f fe- Considering the domain Bd Nacson et al. [2023, Appendix F.2] demonstrate that:
n
(Term A) Amax n
(ofola))
21+2 D
welllwkl12 g(w bw), (27)
where wi w ///k Sd-1 by bz/ 11 and
b( = PP i 6)2 E x v0 - b
x
>
8)
v
|| XT > 811.. |
(28)
29

---

For (Term B), an upper bound can be established using the training loss [()) via the Cauchy-Schwarz inequality. This also employs a notable uniform upper bound for to T Vole ( )ol, as detailed in Lemma C.I:
(Term B)] S
Σ (fo(æ;) vi)²
v Vafo(z)))) s 2 1) 2)/ (29)
Finally, the proof of Theorem 3.2 is complete by plugging (27) and (29) into (26).
D Proof of Theorem 3.4: Radon-Domain Characterization of Stable Minima
In this part, we prove Theorem 3.4 by extending the unweighted case to the weighted one.
Proof of Theorem 3.4. In the unweighted scenario, i.e., 9 = 1, it was established by Parhi and Nowak [2023b, Lemma 2] that if E V(Bg) = V1(B)) with integral representation
(ax) = f
alu T 1) du(u, + c. x + co. E BB
(30)
-
where v, c, and co solve (8) (with = 1) that
== 28 (-A) d+1
fext:
(31)
where we recall that fex: is the canonical extension of f from By Rd via the formula (30) and E M(St11 x R) with supp g [-R, R| (i.e., we can identify v with a measure in M( [-R, RJ). Since the weighted variation seminorm lv, is simply (ef., (8)
Iflv,
inf vEMM - CER* ,RER
l1g llg.vllM s.t. f = ff.cco
(32)
we readily see that 1flv, lgg 2 (-)) + SexillM
Remark D.1. The unweighted variation seminorm exactly corresponds to the second-order Radon- domain total variation of the function [Ongie et al., 2020, Parhi and Nowak, 2021, 2022, 2023b,a] Thus, the weighted variation seminorm is weighted variant of the second-order Radon-domain total variation.
E
Characterization of the Weight Function for the Uniform Distribution
Recall that, given a data gd-1 x R - R. where gd-1 {u E Rd | =} denotes the unit sphere. This weight is defined by guu, 1) == min o0 1), uu, -1)}. where
((.,,;:)} y:)) Rd R, we consider weight function g
u 2)² E[X g(u,t) ( -
x t V1+ [ X u E]]?
(33)
Here, X is random vector drawn uniformly at random from the training examples { Note that the distribution Px which the {a are drawn i.i.d. from controls the regularity of g.
In this section, We first analyze the properties of the population version gP by assuming that the random vector X is uniformly sampled from the d-dimensional unit ball By {a Rd ||ズ||| 2 S 1}. Then we analyze the gap between the empirical and the population gr using the empricial process.
E.1 The Computation of the Population Weight Function
We focus on the marginal distribution of single coordinate and related conditional expectations. Let X, be the first coordinate of X. Due to symmetry, all coordinates have the same marginal distribution.
The following proposition calculates the marginal probability density function of the first coordinate (and also other coordinates) of the random vector X.
30

---

Proposition E.1 (Marginal PDF of Coordinate). Let X follow the uniform distribution in B The probability density function (PDF) of its first coordinate X, given by:
ft. ci (d) -1- 2-) t tel 1-1-1,11
(34)
where a = 1 and the normalization constant is
T +1)
ci(d) V d+1
(35)
Proof. The volume of the unit ball is Va
The uniform density is fx(x)= 1/Va for Bq. The marginal PDF is found by integrating out the other coordinates:
T4/2
T(d/2+1)
Vola- 1ola-1(V1- 82)
(1) [ 11a0 Va dæ'
Va
g(d-13/2
where VRl is the volume of (d 1)lb of radius R. Using Va-1 a/d 11/2 we get [(d+1)/2)
F((d-1)/++1
(t) Va- (3)(1-1)/2
(d-1)//2
T(d/2+1)
(1 (11-2((d-- (d)dd11/2
Va
I'(d+ 1)/2)
Td/2
which simplifies to the stated result. For d = 22 = 1/2, (2
I(2)
2 For
(31
Vx(Va/2)
= 3, =, c3)
T(5/2)
3/4/4
(2)
V
Given the marginal probability density function, the tail probability follows from direct calculation.
Proposition E.2 (Tail Probability). Let X be a random vector uniformly distributed in the d- dimensional unit ball By {æ Rd ||æ]||2 probability is defined as Q(x) = P(X, > x) for E [-1, 1]. Then there exists fixed To E [0, 1) (specifically, we choose To 3/4, 4, which implies (1 2) (0, 1/4) such that for all x [zo, 1):
1}. Let X1 be ils first coordinate whose tail
(d( ((x)
x) $ (2(d)
Or equivalently,
(2(d)( x)
< ((x) s ca(d)(1 x) +2
where the constants (2(d) and cx(d) are given by:
4+1
(d) 7
(d) d+1 4
C1 (d) 442
cd
d+1 2
[1(+11 / 20
and (d)
is the normalization constant from the marginal PDF of X1.
Proof. The tail probability Q(x) is given by the integral of the marginal PDF fx. (t) cdd())1-)t) fort E [],,1], where d-1
Q(x) - f( (1)d)(1 -2) dt
Let f2, so dt ds)(22/). The limits of integration for become x2 to 1.
Q(x) = ci( /' (1 - 5)a 2
ds
31

---

Now, let u = 1 - s. Then 1 - a and ds = du. Let 6, =1 1 - x². The limits for u become 6, O.
Q(x) = (d) 6..
2 / /
(1 u1)1//2 vt du
For u [0, we have
< (1 u)- (1- - -1/2, because (1 - u) is decreasing and
non-negative. The integral Jo f u du g.
a+l Substituting these bounds for the term (1 u)-
ci (d)d) 8at1 - (()) & (i(d)
(1 - 5,2-11280
2(a 1)
2(a + 1)
We use d-1 2, 50 2( + 1) = 2( +1 = 211211) d + 1. The exponent + 1 d+1 2 Thus, (d))
(d) - < (a))== - d+1 (1 55,) 1/22, d ++1
d+1
We choose 20 = 3//4. so we consider e 3/34,1 1), which means (1 (1-21 x) (0. 1/4]. For r E [3/4, 1).
we have + x E [7/4, 2). The term 6, 1-115
(1- + æ). Given the range for + æ, for
(1 - 2) E 1/4]:
1 (1 (1-x) s 8, 2(1 x)
7
Lower Bound for (xx): Using 8, 2 [1 x) from the above range:
= (d)
d+1
Q(z) 2 c (d)
d+1 4 (1=)))
7
7
(1 (1- 2) 41
1
4
This establishes the lower bound with (2(d)
(d)
2+1 d+1
(7)
2
Upper Bound for Q(x): For the term 0₂ 2 we use 0, < 2(1 - s0 5,- < (2(
For the term (1 (1-0) 6.)-1/2 Since (1 (1-20 x) E (0, 1/4, 6, < 2(1 - x) < 20144 So.
6, > 1 - 11/2- = 1/2. This implies (1 - 6.) 6.) < (1/2)-117 = 22. Combining these
for the upper bound of Q(z):
((x)
(1 21/2 d+1
2 22/1/22"" (1-x) 2
d+1
d+1 2 (1 x.)
4 (dd) 2+2
This establishes the upper bound with c3(d) = 9(d)
2 d+2
d+1
Thus, for x E 13/4,1) (i.e., 1 - x 1/4):
c2(d) -1 = < Q(+) < -))
This corresponds to Q(xx) - cold (1 x) بنب The constants (2 and Ca ca depend only on the
dimension d (via ei (d) and the exponents derived from d) and are valid for the specified range of xr.
Based on the tail probability, we calculate the expectation conditional on the tail events. Proposition E.3 (Conditional Expectation). For x E [3/4, 1), the conditional expectation E[X,
X1 > z] is bounded by
cs (d) - x) S E| X1 > x| < ca(d)(1 x),
(36)
where the constants (d) and (d) are given by:
(d) = 2(d + 1) (7/4(/d11//
d+3
2(d+2)/2
+ 2(d+1) 1) 2(d-1)/2
2(d
c cd())
d+3 3 (7/4)/--1)/2*
32

---

Proof. We consider 1 - -[x X1 > x| = B[1 - X1
X1 > z].
1
| >
(1- fx)xx (f)
Q(x)
ci(d)
Q(z) (1 - (1 - -
ci(d)
Q(z) (1 - t)att(((a000) (1 + 1) dt
Let Let [1)) = f (1 (1+t) We consider I E [3/4, 1). For t E [a,, 1}, we have 1 + t e
[1 + 2. Since x 2 3/4, 1 + x 2 7/4. Thus, (7/4) Σ (1 + t)a - 2 for E [x. 1] (assuming
2 0, which holds for d 2 1). The integral [1 t)at1 dt [ [-0-7 (1-0)111)
(1-2)=12 So,
a+2
a+2
I (x) is bounded by:
(7/4) (1- (1=x)at2 x)
a+2 < [1(x) 20 (1 (1-2)) 1z)00t2
a+2
Let (1) = (x). Then, using a - 2 = (d + 3)/2:
201 (d)
x) S N1 (z) 20 (d)2(d-11/2
(1 (1-z) 4+3
d From Proposition E x E (3/4, 1), Q(x) is bounded by:
d-3
c2(d)( - x) + 1 ((x) I cs(d) - x) 7
where (d)
(
d+1 (I) and cd(d)= 2 ~ي Therefore, E[ X1 X1 x]
Ni (m) is Q(2)
bounded by:
Lower bound:
20, (c)(1)(/4)( 11/2
(1-x)
2c (0(()(/44)d-)//)(( +3)
d+3
(1 (1-x) x))
ca - x) 4t
gidd)
d+1 2 2x2
11d+1) (7/4)
(1 x) ca(d)( x)
d+3
2(d+2)/2
Upper bound:
20y (d)2
(1 (1=x)² 443
2c (d)2( 1)/2 /(d + 3)
d+3
(1 1--r) I)
(2(d)(1 _
(
(1) +
d+T
2(d [ 1) 2(d-1)/2
d+3 (7/4)l443//2 (1 - x) = =cs(d)( - x)
So, for x E 1):
(d) -) = X1 X1 > 2] S ccd)((1
This implies:
1- cs( x) s B[X1 X1 > a| S 1 ca(d)(1 - x)
This completes the proof.
Finally, we combine the results and characterize the asymptotic behavior of the weight function g. Proposition E.4 (Asymptotic Behavior of g" (z)). Let the function g (x) be defined as: for x e 1),
g g+(x) = IP > x)² E[X1 - x X1 > x] (1+(B[X)
X1> x1)²
X1 >
(37)
Then for x E [3/4, 1), we have:
40 { (d)(1=))4+)
(d) g
(38)
where (d) (d) and
( cg (d) are positive constants depending dimension d, defined in the proof (39).
33

---

Proof. Let Q(x) = P(X1 > 2) and E(x) = | x/. The function is g (a) = Q(z)².
(E(x) -x) x) v1+ Ex)². Now, establish precise bounds for [3/4, 1). Let (1 r) be the variable.
Bounds for Q(x)²; From Propostion E.2, (2())) - - - < Qax) z cs(d)(1 - x) x)
1.
So. AL (d) z) d++ - Q(x)² < (d) - (1) where
(i(d) 7
Ar.(d) (c2(d))²
d+1
4
Ad(d) = (ca(d))² = (1(()) 4-2
2
d +
2. Bounds for E(x) == E| - x X1 > =|: From Propostion E.3, have (1 - x)
(s) - x) < E(x) - x S (1 -x) - -c((d) - x). So. Br, (d) x) I E(x) - x S
(d) x), where
Br(() = 1 -c))d = 1 2(d + 2(d-11/2
d+3 (7/4)l++1)/2
Bu(d) = 1 - c4(d) = 2(d+ 1) (7/4)
d+3 2(d+2)/2
Since E(x) - x = E[X1 - x X1 x| must be positive (as X1 > x), we take (2(d) = max(0, (0,110((1d)) (d)).
3. Bounds for / 1 E(x) We know 1 - cs(d) 2) < E(x) 1 - cdd)(1 - -r). For
x E [3/4, 1), (1 I)) (0, 1/4] and the upper bound of E(x) given by
E(x) S 1 - c4 (d) x) < 1.
The lower bound is also given in this way
E(x) E
X1 > x 2 3/4.
Therefore, we deduce that
CL(d) V Cd(
where
5
C2(d) 4' Cd V2.
Combining these bounds, for x E [3/4,1):
g g*(x) Z Add z) (1 x) c/. (d)(1 x)
g+(x) S (4d) - 11 x) = di (d) - 2)dt2
The constants are:
(g) (d) = (c2(d))² (1-cs(d) 5/4,
(39)
(e) (d) = (c (1 - (d)) V2.
E.2 Empirical Process for the Weight Function
In this section, we discuss the empirical process of gp. Now we may relax the assumption by just assuming that X is random variable with xu)p(X) S BB. Fix dimension d E N, sample size n E N, and let XI..... X, be i.i.d. copies of X. We use the notation 9n to denote empirical weight function g as we defined previously.
For u E 1d-1 and [-1, 1], define
puu, t) = IP x u >1) f),
s(u,t) = E((x ((t)4=)))))
34

---

and recall the population weight gr(u,t). t). By the bounds 0 S (X +)+ - and [ X f]ll S 1 (valid on (,, we have the pointwise comparison
gp(u, t) p(u, (,,
with absolute constants,
(40)
ie., there exist universal C E (0, such that cps S gp S Cps for all (u.t) E g x 1-1, Consider the empirical plug-ins
(u, 1)
Σ 1(xTu> ut, (u, Σ (XTu-t)+
(n(u, := Pn t) 8n (u, t).
Note that In involves no division by Pn. hence avoids any small-mass instability. We now give self-contained proof of sharp, distribution free uniform deviation bound.
Theorem E,5 (Distribution-free uniform deviation for 9n). There exists a universal constant C > such that, for every å (0, 1),
In (u, - gp(u,t) > OV + log(2/0)
P
sup ME3A AEES--1,EE 1,11-111
S Ó.
Proof. Using (40), it is enough (up to absolute constants) to control Pn(us, (u,t)
p(u,t)si t) uniformly over (u, E gd-1 [-1, Observe that 0 I 8,8n S 2 and 0 S Pm I so
8n psl S pmn pl 18, pn s 2 ppl + 18, - s/.
(41)
We thus seek uniform bounds for the two empirical processes appearing on the right-hand side. The argument proceeds in two steps:
Halfspaces. The class + 1xxT > f} S t EE R} has VC-dimension d 1. Hence, by the VC uniform convergence inequality for (0, J--allded classes (e.g., [Vapnik, 1998]), there exists a universal constant Ci 0 such that, for all E (0,
(r(u,)) t) p(u, t) Cip d (1g()/
P
sup WEB 1,1E(-1.1]
I 6.
(42)
ReLU class. Let (.) (uJ x 1)+ E S0-1 LE [-1, 1]}. Since | and t [-1, 1]. we have (0,2]. Consider the subgraph family
subG(FF) (x. ERd R:: y (u x - 1)+
For S 0 membership is automatic; for y 0 it is equivalent to the affine halfspace condition u T -t t- 2 0 in Rd+1 Thus (Cdim(subG(FF) < d whenee Pdim (F) s d + 2. Standard pscudo-dimension bounds (see [Haussler, 1992, Thm. 3, 6. 7]) give universal C2 > with
d 1og(1/5)
P
sup
(u, s(u,t)] > C2p
<
(43)
4E34-1 16|-1111
Combining Step (I) and Step (II) with union bound and the previous inequality yields
d
(2/5) n
P
sup
8n - pps > C'V u.t
<
(44)
for an absolute constant Finally, the equivalence (40) transfers this bound to supu, 19n. grl up to universal multiplicative factor and the same failure probability.
35

---

Proof of Theorem 3.5: Generalization Gap of Stable Minima
Let P denote the joint distribution of (a, y). Assume that P is supported on Bf x [-D, D, DJ for some
D 0. Let f be function. The population risk or expected risk of f is defined be
R() = E
[U(x)) w)²
(45)
Let D {(,,, Pi be a data set where each (z:; ys) is drawn i.i.d from P. Then the empirical risk is defined to be
R(F) = (f(a)))
- - -4))
(46)
The generalization gap is defined be
GeneralizationGap((f R) R(f) R(f)--
(47)
The generalization gap measures the difference between the train loss and the expected testing error. The smaller the generalization gap, the less likely the model overfits.
F.1 Definition of the Variation Space of ReLU Neural Networks
Recall the notion in Section 3, the weighted variation (semi)norm is defined to be
Iflv,
inf RR))
l|g wllM s.t. f fn.eco:
(48)
MEM(S cER4.
and now we define the unweighted variation norm simply variation norm to be
Iflv
inf MEMIS - x(-RRR) cER
Mllll s.t. f= fue.er
(49)
This definition is identical to the one in [Parhi and Nowak, 2023b, Section V.B]. The following example for unweighted variation norm similar to Example 3.1.
Example F1. Since we are interested in functions defined on k for a finite-width neural network I vnd(w] by) 3, observe thut it has the equivalent implementation as +c + Co. where aj E R. u E ESa-1, tú E RR E Rdd, and co E R. Indeed, this is due to the fact that the ReLU homogeneous, which allows to absorb the magnitude of the imput weights into the output weights (i.e., each a; = |Uk, ||w,, 1 for some k, E "1l...,,K, ). Furthermore, any ReLUU in the original parameterization whose activation threshold is outside By can be implemented by an affine function on B which gives rise to the c l'x + co term in the implementation. If this new implementation is in "reduced form"" i.e. the collection {(u, t distinct, then have that life v -E/= lagl-
fo(x) = - -
The bounded variation function class is defined w.r.t. the unweighted variation norm. Definition F.2. For the compact region 52 Bd we define the bounded variation function class as
o(u x dv(u,, cJx + +b, 1flv s =c) (50)
Vc( = f: f: 1 f
Jgd 1x|-R.8
F.2 Metric Entropy and Variation Spaces
Metric entropy quantifies the compactness of A in metric space px). Below we introduce the definition of covering numbers and metric entropy.
'The activation threshold of neuron o(w x b) is the hyperplane {æ Rd wTo b}.
36

---

Definition F.3 (Covering Number and Entropy). Let A be compact subset of metric space (X, px For O, the covering number N(A,t, t, px) is the minimum number of closed balls of radius needed to cover A:
((t, A, min N
X s.t. AC U B(z,, t)
(51)
1=1
where (ax,,)) E (x) S 1). The metric entropy of A at scale I. is defined as: (x)A) == log (1, A,p).
(52)
The metric entropy of the bounded variation function class has been studied in previous works, More specifically, will directly use the one below in future analysis. Proposition F.4 (Parhi and Nowak 2023b, Appendix D). The metric entropy of (c (see Definition F.2) with respect to the L -disttnnee || Iloo satisfies
(9)
log (t, Vo( (1 Ea
(53)
where Ed hides constants (which could depend d) and logarithmic factrit
F3
Generalization Gap of Unweighted Variation Function Class
As middle step towards bounding the generalization gap of the weighted variation function class, we first bound the generalization gap of the unweighted variation function class according to metric entropy analysis.
|I S SM with M 2 D where D refers to Theorem 3.5. Then with probability at least 5:
Lemma F.S. Let FM.C {s E (c(B))
RRJ)
366+2) 4+3 Rn(()) Ea Cadla M 2443 n 4d+0.
sup fEFM,c
(54)
Proof. According Proposition F.4, one just needs N (t) balls to cover F in lloo with radius t such that where
log ((t)(t)= Ed (
Then for any f.g FM and any (z,
[(f(z) y)² (9(x) y) = lf(z) g(x)) (x g(x) 2yl I 4M |lf ol
Hence replacing f by centre f, within t changes both the empirical and true risks by at most 4Mt.
For any fixed centre f in the covering. Hoeffding's 's inequality implies that with probability least 8, we have
IR() --(F(()) < 4M², (2/()
(55)
because each squared error lies in J. Then we take all the centers with union bound to deduce that with probability least
8/2, for any center f in the covering index, we have
Tog (o)(4))))/8))
IR() R(F) < 4M²
(56)
J
Sa M²
n -
According the definition of covering sets, for any f E FM,Cs we have that - floo S t for some center Then we have
IR(f) R(()
< [R( PR(5) + O(M()
(57)
< M2 C n +
After tuning to be the optimal choice, deduce that (54).
37

---

F.4 Concentration Property on the Ball: Uniform Distribution
In the following analysis. will handle the interior and boundary of the unit ball separately. this part, we define the annulus of a ball rigorously and provide a high-probability bound on the number of samples falling the annulus.
Definition F.6. Let Bf be the unit ball. The E-annulus is subset of BB defined as
Ag (æc By ||0||| 2 1 c}
and the closure of its complement is called E-strict interior and denoted by Ie. Lemma E.7 (High-Probability Upper Bound on Annulus). Let d N and e E (0,1). Let
Uniform (B.).
1 In
Define na = =(i n; A and p P(X Ag)
(1 61-6 e)d
O(s). Then for any
ô E (0, 1), with probability at least 1 8,
p log
S p+
(58)
Proof. For each I,.... n, consider a Bernoulli random variable
1(X E A
so that [E] p and regards U, sample. Then may take nA Σ U. By the multiplicative Chernoff bound for the upper tail of a sum of independent Bernoulli variables,
P(ns > (1+)) S exp (-3 np).
Aイ> 0.
Set the right-hand side equal 5 and solve for ?:
In(1/5)
22 exp 3/ np)
2² 3 np In
n p
If > 1, note that trivially na/n $ p
3 (1/6
so the claimed bound holds in all cases.
Otherwise, plugging this choice of into the Chernoff bound gives
pmpa5np(1+)) 2 1 8,
i.e. with probability at least 6,
nA S np+ V In(1/5),
and dividing by yields the stated inequality.
E5 Upper Bound of Generalization Gap of Stable Minima
Let f = fe be stable solution of the loss function L(0), trained by gradient descent with learning rate 77. Then we have
2 2 Amaxx (V2C(0)) 2 a. V2C(000
-Amax
1
Σ
(ofo(z)))
11
(59)
(Tem A)
Σ (fo(z,) - y VV.o
72
2m
(Term B)
38

---

For (Term A), we have
max
Σ (Volola))
21+210llv.
(60)
For (Term B), we have
n (fo(æ;) - uz)²
(Term B) S
(o Vgfo(,))) (4n $4)2c(0).
(61)
71
Let M max D, 1}. Then we have
2C( (fo(x))) - v.)² & 2M.
Combining these inequalities together, we may deduce that
1
Jolv, < + 4M.
(62)
17 2
With all the preparations, we are ready to prove the generalization gap upper bound for stable minima.
Theorem F.8. (First part of Theorem 3.5) Let P denote the joint distribution of (ar, v)- Assume that P is supported on [ x [- D] for some D > O and that the marginal distribution of x is Uni Fix a data set D = {(x,, yi) } where each (æt, Yi) is drawn i.i.d. from P. and D yields the empirical weight function defined (6). Then, with probability at least 1 8. we have
that for the plug-in risk estimator R( E (f(x)) y.)²
GeneralizationGappFf R) = [R(f) R(f) Ea AT 4013 B² n záो4.
sup (EV,(B() VI,,SA, SB
where B is assumed > 1 and Sa hides constants (which could depend d) and logarithmic factors in n and (1/8). particular, Theorem 3.2 and (62) imply that that
So E {TEV,(B))
|slv S
1 + 4M,, 111
(1f)) & M
(63)
2
for every
0 (0 Onai (1; |1 (nf)) MM}.
(64)
Therefore, we may conclude that GeneralizationGap((ee ft) = [ - R((S))
sup 00:nalo;
1 1
4M 2444443 M n ztz,
Rd
(65)
17
where M max (D [I (
Proof. For any fixed < 1/4, we may decompose By into e-annulus and e-strict interior
= U
According to the law total expectation, the population risk decomposed into
(f(x)) ->> P(a E AG) Es [f(m)) y)²| + P(a T!) E2 (f(xr) -1)² (66)
(
39

---

where EA means that {æ, y is new sample from the data distribution conditioned on a E A and Eg means that (æ, y) is a new sample from the data distribution conditioned on a: E In.
Similarly, also have this decomposition for empirical risk
Σ (J(z))
y:)²
1 "
Σ (s(co)) yz)²² 30 E(((0))- - uz)²
JEA
(67)
Ry
((((a))) - y1)) +
[(((0)) - vz)
nA
VEI
jEA
where 7 is the set of data points with æ; E To and the set of data points with æ; E Ag. Then the generalization gap can be decomposed into
[R()) =( E AC)- EA (fo(z)) - w)²
nA
E(f(z)) - 4₁)
(68)
nA DEA
+ P(æ E 1
[(((z)) )1
(69)
nhs
REL
+ P( 12)
Br
[((x)) - -2)²
1 [(((a)) y1)² 91)2
(70)
SE7
Using the property that the marginal distribution of x is Uniform([By) (144) and its concentration property (see Lemma F.7), with probability at least 1 8/2:
(68) Ea O(B²s),
(71)
where Sa hides the constants that could depend on and logarithmic factors of 1/5.
For the term (69), with probability 1--8% 8/3
P( E I1) R1
log(3/8)
(Lemma E.7)
(72)
Eier(((x:))
y1)2
4B2
so we may also conclude that
(69) S M² (3/0)
(73)
For the part of the interior (70), the scalar IP(x E ug) is less than with high-probability. Therefore, we just need to deal with the term
Ey [((()) w)8
E(((:)) yz)²
(74)
ni SEl
Since both the distribution and sample points only support in lg. we may consider / by its restrictions in Id. which are denoted by f. Furthermore, according to the definition, we have
f(x)
o(u x t) du(utt) + clx
- Jg4-1x(-14e.-
olu t) dv(,
olu t) dv(,,t)
Annulus ReLU
+ cTT bb
(75)
where the Annulus ReLU term is totally linear in the strictly interior i.c. there exists e', such that
c TT + -
olu Tu t) du(u,,), Vo E Id.
(76)
40

---

Therefore, we may write
f = { -1-11x1114 x =) + x (77)
The core of the argument is to rigorously bound the interior generalization gap. Recall that stable minima 0 E n (T; satisfies I/lv, I with respect to the empirical weight function To analyze the complexity of its restriction f on the core TTd we need a lower bound on Fiin = infjiigi-e g(u, t). This quantity is random variable.
From empirical process we discussed in Section E.2, especially Theorem E.5, we know that with probability least 0/3,
sup [g 8) - (u( t)] Sa + log(6/0)
En.
(78)
u.t
"
This implies lower bound on the empirical minimum weight in the core with probability at least 1 8/3.
Dmin inf g(, 1) 2 inf gp(u,, cn = Dp 6n 14s1--
(79)
10/-1-
Here, min x cd is the minimum the population weight function in the core.
For the bound lf S A/gmin A//gg 6n) be meaningful with high probability, we must operate in regime where Jmin 2 Cn- We enforce a stricter validity condition for our proof
Jmin 2 2en
d+2 Rdd n1 1
(80)
Therefore, we may choose
2
d + (6/(6/8)
A 3444243
(81)
n1
Under this condition, we have Imin 2 PP.iin P /2 x d+2 Thus, for any stable solution f, its restriction f has controlled unweighted variation norm with high probability:
A
A
A
If lv
cd42 =: Cg.
Fmin
Prmin/
We now apply the generalization bound from Lemma F.5 to the class Vc, (Bi_e) by plugging in (81), with probability 8/3, Interior Gap (70) Sa (C.) 2dt3 224)2 B 24-3
3(d++)
4+3
n 4246
(82)
31++2 B 22+3
A 2 244443
(83)
d log (6/8)
B(i
E A 2444+4
7 3248
(84)
where Ea hides the constants that could depend on and logarithmic factors of 1/5.
Now we combine the upper bounds (71), (73) and (84) to deduce an upper bound of the generalization have
gap. With probability
R(f) R(()) La A A Ban 2444 + A B
Bid-2) 24-3
46+6
(855
3(112) 2243
Since
2444
4440 and B² >
with the assumption M 1, we conclude that
R(F) R(()) Ea __
2 + 4B
M n 2,
(86)
which finishes the proof.
Remark F.9. For the generalization gap lower bound (second part Theorem 3.5), we defer the proof to Appendix I as it relies construction that is used to prove Theorem 3.7 from Appendix H.
41

---

G Proof of Theorem 3.6: Estimation Error Rate for Stable Minima
G.1
Computation of Local Gaussian Complexity
is known from Wainwright 2019 that tight analysis of MSE results from local gaussian complexity. We begin with the following proposition that connects the local gaussian complexity to the critical radius.
Proposition G.1 (Wainwright 2019, Chapter 13), Let F be a convex model class that contains the the region of interest and denote the empirical
constant function 1. Fix design points æ ... norm
In ,.,,,,,,,,
Il == 1 Σ f(x;)2
For any radius r > write
1 fEF(r) n iml
F(r):= = [ IIfll sr). F) = sup Σ ff())
where En....,En itd N(1 o²) and 9n (r, : E3 (r, If 8 satisfies the integral inequality
Vn !'" V log (1, OF, 11 (la) de S 4'
16
(87)
where OF = {51 f2: f1, f2 E F}. then the local empirical Gaussian complexity obeys
(r, S 20
(88)
Moreover, with probability least 8 one has
x2
/lo((1/0)
Gr, F) s
> 0).
(89)
20
vn
As result, we can derive an upper bound for the local empirical Gaussian complexity of the variation function class through careful analysis of the critical radius.
Lemma G.2. Let FB.C (TB4) (TB)) (s (C |I [|
B). Then with probability at least
1 8, we have
ΣE (((((z)) - f2(x,)) Sa Cauta # Cai
4010
1og(1/6).
(90)
for any two f. FB.C.
Proof. As OF BFB.c C F2B,20 bounding the entropy of F2 suffices. Using ||/ S (24) and referring to Proposition E.4, we have, up to logarithmic factors,
log N F2B,20, 11l))) Ea
Plugging this entropy bound into the left side of (87) and integrating,
l ( पकक dt
Cafz
vn [ t o = Cats rars Vn
Sa
Ta Jo
Hence inequality (87) is met provided
Cafa pats
Se
rd4s Zd C 44s n 1/2
Vn
4
Solving for 2 (and keeping only dominant terms) yields
C C2dta n
Xd
With this choice r.. Proposition G.I guarantees
g, (F.))(rr)) Sa Tu.
and the high-probability version (89) holds verbatim.
42

---

G.2 Proof of the Estimation Error Upper Bound
Given the local gaussian complexity upper bound, together with the assumption of solutions being "optimized", we can prove the following MSE upper bound.
Theorem G.3 (Restate Theorem 3.6). Fix step size n > and noise level > 0. Given ground truth function fo (BB) such that I S B and |folv, S 2 + 20)) suppose that
we are given a data set y; = folæx) ti, where æ4 are i..dd Uniform((B)) and e; are i..dd NN o²). Then, with probability at least 1 - 6, we have that
15 (fo((z)) n1
Ed (2 -2-1- 20 (
120 188 31242)
B
o²
2d44
(91)
for any 0 (na D) that is optimized, i.e., (fo(x;) y112 S (fo(z.) yi) for 1,
Here, Sa hides constants (that could depend on d) and logarithmic factors in n and (1/6).
Proof of Theorem 3.6. The empirical Mean Squared Error (MSE) MSE(fe. fu) = : (fo(x.) - fo(x)))??
we want to bound is
First, we establish bounds on the regularity of fo(x) - fo(x). The condition that fo is "opti- mized" means (Jo(ar.) - )² (Joar:) yy)²² for all Summing over i and dividing by n, we have (f)(a) y=)² R
E (Jo(z) 9,)² - et. Since ~ (0, a²), BI Ez= c 0². Standard concentration inequalities (e.g., for sums of (11 scaled variables) show that E of < a² with high probability (hiding logarithmic factors in 1/5, which absorbed into Ed). Thus, 20(0) S o². For O E OBat (17; D), by Corollary 3.3 (with R = 1 for By. so R 12=1=1 = 2), we have
1 + 2/(0(()) S - + 2a. 2
1 1) 2
Soolv <
(92)
Let C 1 - - 20. The theorem assumes Ifolv, SC Thus, we have lfoll, SC.. The difference fo(x) - fo(z) then satisfies
I/e - Solv, s 1oll, + -oolv, 2C
(93)
Also, llfe foll I [[fellem +1ffolle<334) S BB B 2B.
The optimized condition (fo( (x:) y1)² < (Jo(æ;) - y:)² implies ((so(az)) - fo(x:))-=;;) S o7 Expanding this gives (Ja (z:)) fo(=.))² ) - 2(fo(z;) fo(=:)) + S s7 which simplifies to
(fo( - fu(x:)) < ((f( - fo(
(94)
This incquality is crucial and holds for each data point.
We decompose the MSE based on the location of data points. Let Ag = fx Bf ||ح||| 1 - $} be the annulus and B4 be the inner core. Let SA == (i: x. E Ag) and S = (i: : a, E B The total empirical MSE is
MSF(So,
Σ [Jolaa)) So(mm))) + n VESA
Σ (So(a:)) ) - fo(xx))
n
ieS;
RAA
(fo(x:)) - fo(
+
n1
1
Σ
(fo(z:) - fo((;))))
nA
n2
(95)
SESA
iES;
TIA
(Jo(ax)) (o(2))
1
(Jo(æ:) fo(a;))2
ULA
ny
SESA
1ESt
MSES
MSEx
The contribution from the shell, MSEs, is bounded using the L norm of So - So and the concentra- tion of points in the shell. Let n := |. By Lemma F.7. NA/n S with high probability.
MSE$ V n4 Ilfo folli. S TLA (2B)² Sa B
(96)
n
n
43

---

For the inner core's contribution, MSEI, we use Equation (94):
2 Σ (fo(æ,) - fo(xx)) Es.
MSEI = [(f((z) - fo( v
(97)
kES:
iES1
Let ny == |Sy|- The empirical process term is 2 ( Eies, (fe(a:) - So(mz))).. The function
So fo restricted to BB has unweighted variation norm. As shown in Appendix E, for Uniform(B4)) the population weight function gr(u,
t) x (1- [4))+2, For activation hyperplanes
relevant to By (i.e., |t] < 1 - -),, (p( t) 2 gdt? Thus, the unweighted variation of fe fo on
B4-220 is
fe - fol folv S lsee - folv / d=2 S
(98)
We apply Lemma G.2 to bound 1 Eies, (fo(æ:) (o(z))) Ej. The function h(x) - fo fo( has unweighted variation Z C/sat2 and L norm - 2B. Therefore, we have that
ny
2443
o
2013
MSE S
(99)
cd+2
Combining the bounds for MSEs and MSEz:
d13
MSE(fe. fo) $ B² BB& + Cadts ()=2) 2d
2213
(100)
Similarly to the proof Theorem 3.5 in Appendix F.5, we require that
1
(101)
inf ||| Sp (p(
to filling the gap between the empirical weighted function g and the population gP with high probability, becase with high probability,
sup (9(u, gr (u, Sa n
(102)
where Sa hides constants (which could depend on d) and logarithmic factors, as stated by by Theorem E.5 in Section E.2. Therefore, we may choose
2074
e x
(103)
and plug it into (100) to have
1
2204 Gdl 3)
2d
2
MSE(fe, fo) Sa
+ 20
Ba
(104)
2
n
3 Since 2d44 2d43
conclude that
(1_
32 od 131d 2J
2
20
MSE(fo. fo) Ed
2a
B
77
2
n
which completes the proof.
H Proof of Theorem 3.7: Minimax Lower Bound
H.1 The Multivariate Case
In this section, we assume that d > and the norms and semi-norms are restricted to the unit ball
Bd. Let E 8d-1 be unit vector. Let 8 E R., be constant with e < 1/2. Consider the ReLU atom:
(x)) o(u² (1 =²))
(105)
44

---

Lemma H.1. The L -oonorm of Pu,c² over B is given by
11Pu. (B2
(106)
(r
where (7(d) and cg(d) constants depends d (the conconcrete definition is (113)). Recall that (a(d)
means (d(
07 ( + 11 (le
cg(d) _
Proof. The squared L norm of ca over the unit ball iB is defined as:
/ (x)) dæ
|| (Pu.:=1Bi<(B))
Substituting the definition of (w, x) and using the property of the ReLU function that ((z) = for z > 0 and 6(2) = 0 for = S O, we get:
= /
ul 1Pu..>>12A(BB) [[
jō(u x - (1-))] dx
saf
(107)
(u (1 (1 dx ( =">>1-E")
To simplify the integral, we perform rotation the coordinate system such that w aligns with the d-th standard basis vector (0, .... 0, 1). In these new coordinates, u x = Xx. The unit ball remains the unit ball under rotation. The integral becomes:
== Pl (2))
SIXEBy-XAN (XEBBXXxS1--5) x
(Xa (1 (1- dx
We can write the volume element dXX dX' dXd, where X' R represents the first d 1 coordinates. The condition X E By translates 1 + X3 1. The integral can be written iterated integral:
I-fr (N (Xa - -1- ax')
dXa
The inner integral over a (d - -)-dimensional ball in RR-1 with radius R V--X- The integrand (Xa (1 E²) is constant with respect to X'. Therefore, the inner integral evaluates to:
(Xa (1 - 2² Vola-1(R)
where Vola-1(R)) is the volume of the (d -iimensioonal ball of radius R. This volume is given by Va- 1od-1 with Va-1 p'd 11/2 So, the inner integral is (Xa - (1 8²)) - (d-12/) r(alt)-
and the outer integral becomes:
I V [' (X
=2))
x2) + dX
(108)
1-82
Let X, = 1 performing a change of variable. Then dXaa = - dô. The integration limits change
I = Va-
((1 8) -1 (1- - - -1) do)
Va-1
-62-5)(1 - -5 (8) - d5
(109)
Va-1
- 6)8 82) z d8
45

---

Since we assumed E² < 1' for the integration range =0, we may write 28 -22 = (2 (2-6)6 x9/0 28.
(1)
7
8 S26 83)²² $2=0=
The integral is approximated by:
Va-1 7 1=1
1 (E 63'-0 d8 S I Vo-12 1 ( (E² (52-5)00* d8
(110)
Consider another change of variable: 8 == s²s. Then dð = ds. The limits change
! (2--8)80= db 6===2s)²(E"" - (E2 ds)
/ (63) - -)) 11/2 a-1 e² ds
(62)24 +1 / (1 - s)= ds
(111)
dt5 (1 (1- 3)²3 d-1 ds
(1 81- + ds d45
constant
The L norm is the square root of is given by
(d) E عال
VI <c(d)
(112)
where (7(d) and es (d) are constants defined by
7 d-1
(f(a- 5)2=s بي ds
c7(d) V Va-1 1
(113)
cs(d) = V V (f. (1=ss ds
This completes the proof.
Lemma H.2. Let fu,e² be a ReL.U atom defined in (105). Then
le,,,,ly, 26+4
(114)
Proof. We decode the definiton (see Example 3.1) and compute directly the weighted function g(u, 1 - =?) = ( 2d44
Let gd-1 be the unit sphere in Rd For 0 < < and w 1d-1 define the spherical cap C(u, =?)
as
C(u, = (xc E gd-1 T x 2 22].
(115)
Lemma H.3. Let Nmaz(e, d) denote the maximum number of points u....., uN gd-1 such that the caps C(u,, e²) are mutually disjoint. Then, + 0,
Nman (E, d) x x-- (d-1)
where the implicit constants depend only the dimension d.
46

---

Proof. The spherical cap = has an angular radius 1) = arccos(1-E"), satisfying 1 = (E) for small E. The condition that caps Cuu =²) and C(u,, e²) are disjoint requires the angular separation Φi between their centers w; and wj to be at least 20. Thus, Nm,r(E,d) is the maximum size M($--1,20) 2dd) of a 2ep-saprr set (packing number) on 8d-1
The upper bound Naar (E, d) = 0 (2-1)) follows from a surface area argument: N disjoint caps C(u,, each with surface area ((8d-1) = O(=" '), must within the total surface area Sd
For the lower bound, relate the packing number (( a) to the covering number N(S the minimum number of caps of angular radius needed to cover gd-1, It is a standard result that these quantities are closely related, for instance, M (Sd-1_ aa) 2 _N a) can be shown via a greedy packing argument [Vershynin, 2018, discussions in Chapter 4]. Furthermore, the asymptotic behavior of the covering number is known to be N( a) x a (d-1) for small [Vershynin, 2018, Corollary 4.2.14]. Setting the minimum separation a 20 (e), we obtain the lower bound:
(E, d) = ( 21)) 2 NN x (20) = 02(==
where the implicit constants depend only on the dimension d. Combining the upper and lower bounds, we conclude that Nea (E, d) x E (d-1).
Construction H.4. We construct a suitable packing set in F= 1} based on a weighted ReLU atoms. Let eeu,e be the ReLU atom defined in (105), and according to Lemma H.1 and Lemma H.2:
= (f E Vo |If S 11,1flv
Lu (( = 1, 0 L2(3)) x x [ (u, = E
uu = c- Pu,e²
(116)
According to Lemma H.I, there exists cx (d)) d++1 spherical caps u un such that the caps c(),,²²) are mutually disjoint, for some constant ex (d) s 1 that may depend the dimension d. For convenience, we simply denote Φ; uu Therefore, we have IN Φ;lv,, cx gd+3 < referring to (116). For each & (EI...., .x) E (-1,1] define
N
fe(x) Σ & (x))
According to the conventions, each fe belongs to F. Since the supports of the ridge functions are disjoint, for any E, E (11,, 13 we have
Ilfe - fcr (1:11
112 1 =e 2t dE(E))))
iES
where (5 {¹) denotes the Hamming distance between & and E', and S is the set of indices where &, + C. By the Varshamov Gilbert lemma, there exists a subset C (-1,1} with
log E K x -d-1
for some constant, and such that for any distinct E E E, the Hamming distance di
d=( 2 K.
Thus, for any distinct E E E, we obtain
[l - fer Ie (B 2 K =
Proposition H.5 (Minimax Lower Bound via Fano's Lemma). Consider the problem of estimating function f F {f E VB(B) || -- < Ifvv, , < 1} with
y/ = f(.)) + E,, -= 1..... where (5 are i..dd Ni(000) random variables and {z,Vi_n C. B are i.i.d. uniform random variables on Bd. The lower bound of the minimax non-parametric risk is given by
0²
inf sup E
flli (1
f fEF
47

---

Proof. We use the standard Fano's lemma argument. By our Construction (105), we have packing {fg : }} F with the following properties:
1. The L'-diistnce between any two distinct functions is least 6, where d x
2. The size of the packing satisfies log E ž K (d-11)
For Gaussian noise with variance o², the Kullback-Leite divergence between the distributions induced by two functions fe and fer is
20² life fo- fe-11i:(33)
1
n 20
In order to use Fano's lemma J.1 effectively, we need to satisfy the requirement (141), where in this context is
n 6 < log |+]
2x
for some small constant > 0, then the minimax risk is bounded from below by a constant multiple of 8².
Substituting ò and log (d-1),, the condition becomes
2
(d--1)
or equivalently,
n S o² ed+1 .
Solving for e, we have
gd+1 0²
022
af1
Ex
(117)
7
Then, the separation becomes
2+1
8
n
Therefore, Fano's lemma J.1 (particularly (140)) yields
0
inf sup JE 1lf fll
23)))
2 82
x
f JEF
n1
which is the desired result.
| & BBlffl, I C). Then Corollary H.6. Ler {f E V (B
inf sup Elf flli: > min(B,C) 0²
f feF
71
Proof. We just need replace fe Construction 105 by min B, C) and adapt it to the the proof of Proposition H.5.
H.2 Why Classical Bump- Type Constructions Are Ineffective
The minimax lower bound construction in this paper crucially hinges on exploiting the properties of the depe-depnn weighted variation norm, denoted as | .v,, where the weight function is g(u, t). A key characteristic of g(u, t) (when data is, for instance, uniform on the unit ball BB() is that g t) x (1 d+) This implies that g(u,t) becomes very small as |t] + 1, i.e., for activations near boundary of the domain. This property allows for the construction of functions with significant magnitudes near the boundary using a relatively small variation norm. Therefore, any effective construction for the lower bound must create functions that are highly localized near this boundary.
48

---

0.0
-0.5
0.0
Figure 17: Isotropic Locality is Costly: An isotropic bump function, by definition, must be localized (decay rapidly) in all directions around its center. Suppose we place such a bump centered point di near the boundary in direction uo (i.e., uy 20 & e², here to = (1, 0)). To achieve localization in directions orthogonal to to, one would need to combine ReLU activations whose ridges oriented appropriately. More critically, to achieve localization in the direction parallel to uo (i.c., to ensure the bump decays as we move radially inward from σp), we would need ReLU activations whose ridges {æ ug t have t < 1 E² and are potentially much closer to the origin (i.e., & significantly smaller than 1).
For these ReLU activations whose ridges are not very close to the boundary (i.c., is not close to 1), the weight function g( (uo. t) will not be small. Consequently, constructing sharply localized bump isotropically would require a substantial sum of weighted coefficients in the Vg norm to cancel out the function in regions away from its intended support while maintaining significant peak. This large variation norm would make such functions "too regular" or "too expensive" to serve as effective elements in packing set for Fano's Lemma, especially when aiming to show rate degradation due to dimensionality.
In essence, isotropic bump functions do not efficiently leverage the anisotropic nature of the ReLU activation and the specific properties of the g(u,t) t) weighting. The construction used in this paper, which employs ReLU atoms active only on thin spherical caps near the boundary (an anisotropic construction), is far more effective. It allows for localization and significant function magnitude primarily by choosing the activation threshold to be very close to I (making g(u, t) small), rather than by intricate cancellations of many neurons with large weighted coefficients. This is why such anisotropic, boundary localzzed constructions are essential for revealing the curse of dimensionality in this setting.
H.3 The Univariate Case
The minimax lower bound construction detailed above, which leverages a packing argument with boundary-localized ReLU neurons exploiting the multiplicity of available directions on Sd-1, is particularly effective in establishing the curse dimensionality for d > 1. However, the geometric foundation of this approach, specifically the ability to pack an exponential number of disjoint spherical caps, does not directly translate to the univariate case (d = 1) where the notion of distinct directional activation regions fundamentally changes. Consequently. the lower bound for d = necessitates separate construction or modification of the argument. Fortunately, in the one-dimensional setting, the distinction between isotropic and anisotropic function characteristics, which posed challenges for classical approaches in higher dimensions under the specific data-dependent weighted norm, becomes moot. This simplification allows to directly employ classical bump function constructions, suitably adapted to the function class, to establish the minimax rates in one dimension.
According to Theorem 3.4, we have
Iflv, = (-))) 2t1 fllm
(118)
49

---

When d = and f is smooth, (118) is simplified to be
Iflv |1 gll. S (f" f (x)] |=1)² dr
(119)
and so is the unweighted variation seminorm
1flv 11 [ [
(120)
which is also known as the second-order total variation seminorm. Therefore, the function class of stable minima univariate case characterized into
FB.C =f: [-111 R
|
S B. 11f" (1-1) 11-1-1) C}.
(121)
Using this characterization, more convenient to smooth bump functions to construct minimax risk lower bound for stable minima class.
Construction H.7. Consider smooth compact support function:
(xx) cexp(- 1-20)
|>| < otherwise
(122)
By adjusting the constant c, may assume
(V) [ 10" (1) =1
(123)
and let D be constant such that [[ V2D. We can construct a translated and scaled
version:
2x - -a ba+ for a <
(a)(())
(124)
b b-a
and in particular, P..b b has the following properties by directly computations:
supp Pa.s)
(a, b),
TV
1
(125)
b-a a
vb
Proposition H.8. Consider the problem of estimating function F1,1 with
Yi = f(x) + Ei, i 1==1,-. 1,...,
where {e are i...d. N(0,0²) random variables and {ra) c [--1, 1] are i.i.d. uniform random variables on 1, The lower bound of the minimax non non-parametric risk is given by
inf sup Ell fl 2
f JEF.,1
7
Proof. For any > O, we may construct family. Let = 11- + kE² k = 0, [
We denote
K = =. For each k 1,... K, we define d2 4 1 Since du ah-1 22 we have the following properties
+ = D D
+V²(
(11(()))(() de S because g(() < e3, AL E [ak-1,as] ag).
Let { Øx). }. x 1 be such family of function classes, and any K K-terms combination { 10,,... 2x) is in Fi,1- Then we let
* [+1]k + FL.. { (
a t fs.
(126)
50

---

For any two indexes E1, E2 in {+1}*, we have that
llfe feallra = (5)
(127)
where dn is the Hamming distance. Then, using Varshamov- Gilbert's lemma (Lemma J.2). the pruned cube of (fi..., fM] has size M 2 2k/8, and each has the property that if + j.
IIfe 1 2 D
x VE.
and thus for any #
ne (L(P)||PP)) 2n
On the other hand, satisfy the Fano inequality (141):
ne 20 = KL(Pr S log M x
we let
and thus Fano's lemma (Lemma J.1, particularly (140)) implies that
[
inf sup Ell - f112((-111) 2 f fEFi,
Note that by rescale the functions in the lower bound construction, we can deduce a more general result.
Corollary H.9. For general case FB,C. we can scale the ffnntttoooonnuuuccion by min(B B, C') to deduce the result:
inf sup feJn,
Blff - -fll 2 min(B, C)2
(128)
I Lower Bound on Generalization Gap
In this section, we derive a lower bound for the generalization gap.
L1 The Lower Bound Construction Can be Realized by Stable Minima
Recall the notations in Construction H.4, for e E (0, 1) and a unit vector u E Sd-1 define the (ball) cap
C(u,e) é) == {ar E B Ju: 2 =].
Fix dimension 2 2 and a fixed cap C = C(u, the mass under Uniform(B.) satisfies the two-sided bound
2 1d-1 d+1 PP d
2 2 Wd-1
X
d+1
(129)
Ud
d d+1 Vd
pop
U
where writing Uy : Vol(
Indeed, writing 2² and parameterizing we have
+ VI & with E [1 h, 1] and gd-2
Vol(C) = va-1 ('
(1 1-2) -2)²= á-1 di vd-1 / (s(2 - -s) 1 ds,
1-1
51

---

where 8 = 1 - t. Using 1 2 - - on [0, h] yields
vd-1 7,- 8 ds S Vol(C) I v / s ds
2
2 d vd-1 7
d+1 vd-1 h
S
Dividing by va- Vol( and recalling h = ²² gives the stated probability bounds.
Proposition 1.1 (Many caps does not have sample point w.h.p. via Poissonization). Fix d 2 2 and ε Kn kn -1/(4+1) with a constant K E (0, I]. Let {C(uj, {C(us,=")]T be any family of pairwise-
disjoint caps as in (129), and draw X 1,...., Xn Lid. (Bi)) For each j. write Zj == # ii S X; E C(u,,e²) } and pj = P X E C(ug. Then there exist absolute constants C.. C. 0 (depending only on d and 6) such that, for any 6 E (0,1).
P ((# m 2 0) (g. 8) m) 2 1- expc_xpc m) C. 2(d+1),
where 9, e A and X T x is constant independent of In particulaa with probability at least cxp( cm)) (for some c > 0), there exists a subset I C fl....,,m) m) with [T] 2 co m such
that Zj < 1 for every
where co (0, q.) depends only on d,
Proof. Introduce a Poisson variable N ~ Poi(n) independent of the data. Conditionally on N, draw L.d. Uniform(B4)) Let Z, := # - N: : X; E C(u,,=")}. By standard Poisson
XI...., XN thinning, Z,... 7m are independent with Z ~ Poi(Aj) and
n a d+1 s X3 S u edt1
At the critical scaling 1/(+1) we thus have constants
cap d+1 S X s Uau d+1
b
For each j. set Ay: = 1 = -). Then A . Am are independent Bernoulli random variables with
A Therefore, by Hoeffding's 's inequality for independent bounded variables,
E[Ay] (Ay) = 0) -
g-
P Aj 9- -6) S mxp(-282m) for all 8 E (0, 1).
Equivalently,
P p(#U: 2, 0} 2 (g. 8) 6)m) 2 1 exp(-252
To proceed de- Se-Poissonization, we compare (Z,,.., ..... under the fixed-n model (a multinomial random variable) to the corresponding joint Poisson variable (Zi...., 2m.. By Le Cam's inequality for Poisson approximation, the total variation distance between the joint law of the Bernoulli multi- variables (Zi,..., Zm) and that of independent Poi(A;) variables is bounded by
m Σ PS
sup multi (Z.,..., 7mm E FF)) Proi ( (7,,..., 7m) E EF)
S
S m (U.eP ddt122
(130)
Applying this to the event E = [ 2g = 0} 2 (g. - 8)m} and combining with (130) yields
P(#(): Z, = 0} 2 (g. - 8) m 2
- (Ugap)² m 2(d+1)
Setting c. == 2 and C. = (U gives the stated bound. In particular, choosing any fixed
8 E (0, q.) and defining co g. d E (0, g.) proves that with probability at least - exp(-cm)
C. C.me ((++1) there exists I C {1...., m [ com, such that Z, < 1 for all j I'
52

---

Proposition 1.1 ensures that, at the critical scaling E x n 111(1)+ there exists (with overwhelmingly high probability) large subcollection of caps, each containing no sample.
We now show that a neural network does not have any activated datapoint, the operator norm of its Hessian constantly 1.
Proposition 1.2. Let fo(x)= = -Ex= un v by) + 3 be network defined in (I). Let D {(z,, y:) Fim be data set such that each neuron of fo contains activated datapoint, i.e for each k, >i=1 1 02
b 0, and Jo interpolates D in the sense that so(w:) y/i 0 ff each i.
Then Amax (V)C)= =
Proof. By direct computation, the Hessian V is given by
V&C =
Velo(a:)Vofatz.) T + E(f(a))) -
(131)
Since the model interpolates fo(x;) = ys for all i, we have
c&c Volo(t;
(132)
Consider the tangent features matrix that is defined
(Vooo(z)), Vofo(22), Voso(ar))-
(133)
Then we have vac = T //n, and the operator norm computed by
1 4b
Amax VzL)=
max *ES1++2j
b T 7112
max wE3n-1
(134)
Furthermore, we have
(w(
Volfo)
vaJo(w)-
(135)
V.(fo)
Vo(fo)
For the parameters [wk, bk. vs] associated to the neuron of index k.
f 1 x > buk (wix bk),
ff((z)
1(w > Ux
Oox
Ow.
(f)(v)
Sf(())
1ww ba) uk
Oby
03
Since there is no data point activating, we have that
0
(we be.. f)
(136)
After subsistion by (136), (134) is of the form
0
0
0
:
(137)
0
0
1
1
1
Let (u,,..., un) E g and plug (137) in (134) to have
(E U;) 2
Amax
(22C= = max
max wEBn-1
= -1
53

---

We now establish that such specially constructed interpolation solution is indeed stable. As shown the proof, for an interpolation solution where none of the hidden neurons are active on the training data, the Hessian of the loss has operator norm of exactly 1, i.e., Amax (V) contribution to this norm comes from the gradient of the output layer bias. According the stability condition defined in Proposition 2.1 (Amax 2/n),, this solution is guaranteed to be in nar (77; D) so long as the step size satisfies 7) I 2. Since we assume that < in this paper (cf. Proposition 2.1 and the discussion below it), we have that this interpolating solution is indeed stable.
1. The primary
For brevity, we write Faa (7;: D) {fe 0 E aa (77: D)} in the sequel.
Corollary I.3 (Stronger Version of Minimax Lower Bound). Consider the problem of estimating function f E F {f Fna (1: D), lI IIf (B+) I L} with
= f(.)
where {xr) C Ty are ii.dd uniform random variables on B4. The lower bound of the minimax nonparametric risk is given by
IÍ(D)) - I1ll2(34) Za L (1)
d+1
inf sup E JEF D=PRA
where f refers to estimator and fD) means the estimation based on the data DD
Proof. The core of the proof to construct two functions, fi and f2, which belong the function class FF but are far apart in L norm. We will show that for typical random data set {æ;) any estimator f(D) cannot distinguish between them, as they produce identical observations on D. This implies lower bound on the minimax risk.
We set the critical scaling for our construction to be:
é == nn -1/441)
(138)
Following the geometric packing argument from Lemma H.3, we can find set of N x (dd-1) pairwise-disjoint spherical caps {C,] where each cap C₁ = c( defined by a unique direction u, E gd-1
Let {xx 12 be the randomly drawn data set's inputs. Let & be the event that there exists subset of indices C .I.....N) such that:
(i) r 2 N for some constant co
(ii) For every j E I, the cap Cj is empty, i.e. C, n fx: = 0.
According to Proposition I.1, this event & occurs with high probability, i.e., IPE) 2 1 exp(-cx for some constant ci > 0. From now on, we condition our entire analysis on this high-probability event & occurring.
Conditioned on the event E, we now define two functions. Let j T be an index corresponding to of the empty caps, Cj.
1. Let the first function be the zero function:
fi fx: = 0.
Clearly, fi E Faae (1;; D) and || = 0 < 1.
2. Let the second function be combination appropriately scaled ReLU atoms supported on the empty cap Cy:
= - L (1==3)).
jer
54

---

On the event E, both functions produce the exact same observations. For any æ;;
Vi,1 (1:)) = 0 and Vi.2 f2(x;) = 0.
Therefore, the data set generated by both functions is identical: D = {( O),...,................... (x 0)}.
Since the data set D is fixed by the condition & and the cap Cj empty for E r, the neuron implementing fr is never active on any data point æ, E { This implies f2(2;) ) = 0 for all æ,, The corresponding labels are Yi O. Therefore, f2 perfectly interpolates the data (x 0). According to Proposition 1.2, any such network that interpolates the data and has active neurons on the data set has maxx ((2)) solution is stable. Thus, f2 E Faat (7); D). Moreover, l 1M = L, since the spherical caps {C₃} are disjoint, at any point a at most one of the scaled ReLU atoms is non-zero. summary, both fi and f2 are valid functions in the class F.
1, where 02 is the parameter vector that implements fz. Since 2. this
An estimator f takes as input the data set D, which is identical for both potential ground-truth functions fi and fz. and produces an estimate function, which we denote by f(D). The performance of this estimator is measured by its population risk. The estimator's objective minimize this risk under worst-case choice of the ground truth from the set (S1, f2].
For given estimate f(D), the worst-case risk over this set is
Risk(f(D)) max -
s (lece ||(D)
(10)-11 12 (11))
The minimax risk for this problem is the minimal possible worst-case risk achievable by any estimator. It is lower-bounded by considering the optimal decision rule conditioned on the event E:
inf sup ED ||( - (2()))
> inf (isk((())) P(E).
f SEULLN
The function f(D)* that minimizes max [ - - -fa [,(34)] ʃ is the average
of fi and /2 in the Hilbert space (. This optimal estimate is I(D)* = (Si + f2)/2. The
minimal possible worst-case risk thus achieved at this midpoint:
f f2 f1
f2 S1
inf Risk(f(D)) f(D) f(D)EF
L2(B))
(P(EF)
2 L2(B4)
According to the computation in Construction H.4, may conclude that
aFT
l1fe fill2a(0))
L Σ jer
e Mpuu (1-
I x 1
L.(B()
This completes the proof.
Theorem I.4. Let P denote any joint distribution of (æ. where the marginal distribution of is Uniform(B44) and satisfies the Pp.-D S. D] =.
Let D (()},,))}5 be data set of i...d. samples from P. and that R is any risk estimator that takes any f and DD as input, then outputs a scalar that aims at estimating the risk Rp(f) B(a.))~> [(f(x)) - )) Moreover, let F be the function class we defined in Corollary I.3.
Then
inf sup E R P
sup (EFaa((1:D)) [I5 (1
Rp(f) - R(F:(( Za L2n di.
(139)
where assume that L > D.
55

---

Proof. Let the E[-] be the short-hand for the expectation over the random training data set D.
inf sup E R
sup
Rp(f) - R(f:
P
(EFD
inf
sup
E
sup
Rp(f) - R D)
R
(EiD)
Fo
inf
sup
(R((E Ro(fo)
R P=Unif(B()xfo
far (T:2)
2 inf
sup
E Rp(((DD) - R
f P=Unir(F))x.fo
foEJna(T::))
1
inf sup
E -
2
)x
foEFam
(Corollary 1.3) - Za
The first inequality restricts P further to deterministic labels with labeling functions in F. Check that any function in FF is bounded between 1-M,M] The second inequality uses the fact that fo E Faat (n; D), and the following decomposition
Rp R fERMA RR) - Rp(fo)
RR((ERRM(PR) (R)) R(FERMI D) R R[JERM: D) R(fo:D) + R(fo:D) Rp
S R(RplfERN R)) R(FERM; D)
R(fu: - -lfu:)))RR(foo)
22 sup (EFa
RJ( R(:: (D)
where we used R(FERM: D) R(fu: D) I 0 from the definition of FERM
fERM
argmin R(f:D). feFna((;:)
The third inequality enlarges the set of ERM estimators to any function of the data that output. The subsequent identity uses the fact that (Jo = O.
This completes the proof for the lower bound on generalization gap stated Theorem 3.5.
Technical Lemmas
J.1 Information- Theioornii-eeeiiee tools
Fano's Lemma provides a powerful method for establishing such minimax lower bounds by relating the estimation problem to a hypothesis testing problem. It leverages wwfommation-thhoree concepts, particularly the Kullback-Leilerr (KL) divergence.
Lemma J.1 (Fano's Lemma (Statistical Estimation Context)). Consider finite set of functions (or parameters) (fi, f2,...;; C F, with N 2 2. Let Pj; denote the probability distribution of the observed data D when the true underlying function is fz- Suppose that for any estimator f. the loss function L(fs, f) satisfies L(fr.f) 2 s²/2 0 if is not close to fq (e.g., if we make a wrong decision in a multi- huntii-hypotheiis test where closeness is defined by a metric d(f;, fx) 2 s). More specifically, for function estimation with squared I -oorm loss, if we have a packing set fx fx1122 2 82 for all + k, then the minimax risk is bounded as:
(J,.... JA C F such that [|5;
52
maxj KL(P,, PPr) + log
inf sup Ell flli:
1
(140)
1 feF
log M
56

---

provided the term in the parenthesis is positive. (L(P))IPP(e) denotes the Kullback-Leite diver- gence between the distributions Pt; and Piv- For this bound to be non-trivial (e.g., 2 s²), we rypically require that the number of weel-separated functions funciono M is large enough such that
M log
> max (P,11P)))) j
(141)
2
One can refer to Wasserman [2020, Theorem 12, Corollary 13] or Tsybakov [2009, Chapter 2] for more details.
Our application of Fano's Lemma (for proving Proposition H.5) involves:
1. Constructing suitable finite subset of functions !f. within the class FF such that they are well-separated in the metric defined by the loss function (e.g., pairwise dié-distacce 8). This is often achieved using techniques like the Varshamov-Gilbber lemma (Lemma J.2) for constructing packings.
2. Bounding the KL divergence (or another information measure like x²-divergence) between the probability distributions generated by pairs of these functions. For n i.i.d. observations with additive Gaussian noise N (0, o²), and if using the empirical L norm (11.((P).)) based fixed data points 2;, this divergence is often related 20 Σ (f=((f - fx())))² More generally,
for population norms, it's often -il/s-falli,
2xd
3. Choosing M and (or the parameters defining the packing) to maximize the lower bound, typically by ensuring that the KL divergence term does not dominate log M.
Lemma J.2 (Varshamov Gillertt Lemma). Let
= {5 = (EI,...,EN) ;N):: Ey E 1).
Suppose N 2 8. Then there exist
59, 52 ..., gM E
such that
1. Eo = (O,
2. M 2 2/8,
3. for all 0 o < k. S M, the Hamming distance satisfies
N
dn(s', 5*) 2
8
We call (50,5/, "',.,,,,,, , 3 pruned hypercube.
One can refer to Tsybakov [2009, Lemma 2.9] and Wasserman [2020, Lemma 15] for more details.
J.2 Poissonization and Le Cam's Inequality
For random variable S on probability space (S, P) with values in measurable space (F, E). the law L(S)= = Po s-1, For two laws μt, on the same space, define the total variation distance
sup (m(A) v(A)).
AEE
When E is countable, drv(p, E.EE (m((x)) ((0l))-v((3)))) v({=))) Lemma J.3 (Poissonization [Barbour et al., 1992 Ch. 1)). Let N Poi(X) and, conditional on N, let W,..., WN be i.i.d. taking values in (0, 1, m) with P(W =}] Pý for 1, m. where Po := ΣØ 2 Define Z, = #(1 s i N W, = j] I...., m. Then
7, ..... , 7... are independent and Z,j Poi(Ap;).
Remark J.4. This standard Poissonization trick replaces the fixed sample size by Poisson random size N ~ (oi(n), making the cell counts independent. See Barbour, Holst and Janson [Barbour et al., 1992, Ch. 1] for general treatment and applications in occupancy problems.
57

---

Lemma J.5 (Le Cam's inequality for Poisson approximation [Cam, 1960, Arratia et al., 1989, Barbour al., 1992]). Let (Zi...., 2m Mult( P...... .......Pr....................... Pms Po) with Po = -ーー Pj. Let ......, Y... be independent with Y, ~ Poi(np,). Then there exists a universal constant C such that
m Pj
drv(E(Z),.... Zm,) ((%) & ((Ym)) S C
j=1
Remark J.6. Lemma J.5 classical result of Le Cam [Cam, 1960], with modern proofs and refinements given by [Arratia et al., 1989] and by [Barbour et al., 1992, Sec. 1.3]. provides quantitative control of the total variation distance between the multinomial occupancy vector and the independent Poisson approximation. We this bound to justify the de-Poissonization step in the proof of Proposition I.1.
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer the last paragraph Section 5,
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
59

---

Justification:
The assumptions are clearly stated in the theorems while the proof is stated in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The details can be found in Section 5 and Appendix.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
60

---

Answer: [Yes]
Justification:
We will release the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //n /nips. wwtppcccpccccceeccccccccccccclct hataaigggddeeeedeeuniiieeeeeee
/Coo///oomissssseeeee coriiisssoooiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The details can be found in both Section 4 and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We sweep the random seeds for the initializations of neural networks and take the median for performance metrics such as MSE. Details are discussed the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
61

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All the experiments can run on Mac Air M1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https httppp:://nurrre http///eerrippppeeee httpp////ccpppitcieiiceceeeaeee
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the Neuips Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a paper about theory of neural network, where we believe there is no possible negative societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
62

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does have have such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
63

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: This paper does not involve this.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Guidelines:
The paper does not involve crowdsourcing nor research with human subjects.
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
64

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development of this paper comes from human brains.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https /ttps////neui.pp.eeee /c/////neeeeeecc/////////1 for what should or should not be described.
65


Reviews:
[{"review_id": "1vgdieqGAQ", "reviewer": "Reviewer_fmSs", "summary": "The paper conducts a theoretical study of two-layer ReLU networks, focusing on the interplay between generalization ability of a minimum, and the flatness of the objective landscape around it, as measured by the maximum eigenvalue of the Hessian; with flatness also being equivalent to stability of gradient descent in the neighborhood of the minimum. The main theoretical result shows that while the network trained to reach an empirical minimum has vanishing generalization gap, the required number of training samples $n$ required for the gap to be small grows exponentially with the input dimension $d$. Authors provide both an upper and a lower bound on the generalization gap for stable/flat minima, and show a construction of a stable minimum that generalizes poorly, and consists of pseudo-sparse activations, with few ReLUs firing for any specific input. The theoretical results are validated experimentally.", "questions": "- Does network width affect the theoretical findings?\n\n- How much are the empirical results influenced by width, e.g. what would happen for K=d, or K=4d as in Transformer MLP? At the extreme, a single ReLU hidden layer (K=1) should have no problem learning a noisy d-dimensional linear function, by shifting the ReLU bias to be outside of the data domain and effectively becoming a two-layer linear network in the data domain. More generally, lower width should, hypothetically, make pseudo-sparse solution less attractive.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper extends our knowledge about the connections between flatness of the objective function around a minimum and the generalization capability of the minimum. Prior work shows varying levels of relationship, depending on the specific scenarios. Most closely, prior work with univariate ReLU network showed that stable minima, those with flat objective around a minimum, generalize well. Authors show that this is not the case in the multivariate case. Previous studies of 1-hidden-layer ReLU showed that it can be trained (with large step size) to arrive at stable/flat minima, resulting in smooth predictor function. The current paper shows that this does not translate to efficient (low sample complexity as a function of input dimensionality) generalization capabilities. On the other hand, they also show that networks trained with weight decay do generalize in the same scenarios. \n\nThe experimental part provides support for the theoretical findings, yet the spectrum of scenarios / synthetic datasets is very limited. The dimensionality of the datasets is very small (d<=5), while the networks are relatively very wide (e.g. 2048 ReLU neurons in Fig. 2). While this setup serves the purpose of demonstrating in practice the existence of pseudo-sparse solutions, it does so at the expense of demonstrating the applicability of the bounds across a broad rande of widths.  Also, only linear ground truth is considered (it would be interesting to see at least one simple non-linear function, e.g. absolute value).\n\nOverall, while the above advances are novel, there are somewhat narrow in scope and in its relationship to practice. The connection between flatness and generalization has been questioned before, with recent work showing that training towards a flat minimum is beneficial in some tasks and/or architectures, but not in others (e.g. [1]). One wonders to what extent is the result influenced by not limiting the width of the network (if width plays some role in theorems and proofs, authors should make it more explicit) while at the same time not limiting weight magnitudes via e.g. weight decay. The study of very wide ReLU networks with no weight decay has limited connection to practice, where weight decay is typically used, width is limited, and, in recent years, GELU is increasingly used instead of ReLU. \n\n[1] Kaddour et al., When do flat minima optimizers work? NeurIPS’22", "was_revised": true, "final_justification": "The additional experiments provided in the authors' rebuttal have resolved my concerns about the impact of width.", "rebuttal": "We thank the reviewer for their time and for providing the opportunity to clarify our contributions.\n\n**Clarification of the set-up of the experiment**\n\nThe setup of our experiments was designed to test the precise claims of our generalization bounds. Our theory investigates the inductive bias of vanilla GD in the overparameterized regime, where generalization occurs even as network width scales with the sample size (e.g the scaling law). This is the reason why we use wide neural networks.\n\nFurthermore, the decision to limit our experiments to $d\\leq5$ is a direct and practical consequence of our theory. Our bounds predict that the required sample complexity for effective generalization scales exponentially with dimension $d$. The primary goal of our log-log plots is therefore not to achieve a low error in high dimensions, but to empirically demonstrate the trend that the generalization slope flattens as d increases. Our results show this unequivocally: the slope for $d=5$ is already exceptionally flat for a simple linear function, indicating severe sample inefficiency. Extending the experiments to higher dimensions would require a computationally infeasible number of samples merely to confirm an already established trend, providing no additional scientific insight for the immense cost involved.\n\n>Also, only linear ground truth is considered (it would be interesting to see at least one simple non-linear function, e.g. absolute value).\n\nWe have conducted experiments on non-linear functions (e.g., quadratic) and confirmed the same generalization trends, and we will add these experiments to the appendix in the final version. \n\n\n\n> Does network width affect the theoretical findings?\n\nWe focus on the overparameterized regime because the underparameterized regime does not require implicit bias for generalization. Our upper bound does apply to small $K$, but the bound could be bigger than the standard parametric rate $\\sqrt{Kd/n}$. Our lower bound requires $K$ to be large to be relevant for neural networks. We will make the assumption that $K>n$ explicit in the final version.\n\n\n>a single ReLU hidden layer ($K=1$) should have no problem learning a noisy d-dimensional linear function, by shifting the ReLU bias to be outside of the data domain and effectively becoming a two-layer linear network in the data domain.\n\nWe agree that a 1-unit ReLU network is capable of learning a linear function. We ran new experiments and found that GD with sufficiently small learning rate does indeed finds good solutions.\n\nOur experiments focused on the overparameterized setting (when $K$ is large) for the reason we described earlier (generalization bound via standard uniform convergence is readily available even without flatness or EoS).  Our aim is not to find the best model / algorithm for fitting a linear function, but to illustrate how the modern regime of overparameterize + GD can be fragile even in such a simple setting.\n\nInterestingly, we find that when $K = 16, d = 64$ and $n=1024$, the \"pseudo-sparsity\" phenomenon is still very prominent. We suspect that even a mild overparameterization (over the number of parameters to describe the target function) is rather harmful, if we solely rely on \"flatness / implicit bias of GD stability\".\n\n\nThis finding allows us to reiterate our core research paradigm. Our work uses the set of stable minima as a prism to understand the dynamics of GD's representation leanring, since directly analyzing large-step-size gradient dynamics is notoriously difficult. Within this paradigm, our lower bound construction (see Append B.4 Figure 9 for the visualization of our lower bound construction) provides a intuition: it proves the existence of a \"hard-to-learn\" solution built from pseudo-sparse neurons, hinting at a dynamic where neurons pathologically shatter the dataset and get 'stuck' fitting local points. For example, neurons whose activation boundary is near the edge of the data support only receives gradients from a few nearby points and if those points are already well-fit, the local gradient on this neuron's parameters can vanish, causing it to get \"stuck\" nearby the boundary. The higher the dimension is, the easier for these neuron to shatter the dataset. \n\nWe agree that the width of an NN plays a role on the probability of the occurance of this dynamic. As the reviewer astutely points out, such a \"stuck\" state is unlikely with just a single neuron. However, once representational redundancy is introduced (e.g K=16, d=64), the learning task may become distributed on various neurons and thus create the possibility for a pseudo-sparse neuron to become stable, as other neurons can compensate for the global loss, effectively shielding the \"stuck\" neurons from further updates. Moreover, our empirical results support this perspective (even with a narrow NN). We thank the reviewer for their insight and will clarify this perspective in the final version.\n\n\n>in recent years, GELU is increasingly used instead of ReLU.\n\n\nWe acknowledge the reviewer's point on GELU. Following the gradient analysis perspective, we believe this problem is not unique to ReLU. While GELU provides a non-zero gradient for negative inputs, this signal is weak and decays quickly. It is therefore plausible that this weak gradient is insufficient to pull a \"stuck\" neuron back from the data boundary. To test this, we conducted new experiments, and our empirical results show that the pseudo-sparsity and poor generalization phenomena indeed persist for GELU networks. We will add these supporting experiments to the appendix in the final version."}, {"review_id": "FnEOF0YksD", "reviewer": "Reviewer_f8m7", "summary": "The paper investigates stable minima of two-layer ReLU networks using the MSE loss. It shows that although flatness, measured as the largest EV of the loss Hessian, implies generalization, this guarantee degrades in high-dimensional settings. Specifically, the dependence on dataset size deteriorates exponentially with the input dimension. Notably, these results hold in the non-interpolating regime, where networks do not fit the training data exactly but still seek stable minima.", "questions": "Questions:\n- How do the theoretical results relate to deep learning practice? There, input dimensions have grown enormously (LLMS and LVLMs), but while datasests have grown enormously as well, it seems their growth was not exponential in the input dimension. \n- The theoretical insight is interesting when compared to the results from relative flatness [1]. There, the bound also deteriorates exponentially, but in the dimension of the feature extractor, i.e., with roughly $n^\\frac{-2}{4+m}$, where $m$ is the dimension of the feature space. In this paper, $m$ would be the number of hidden neurons. Now if $m$ was kept fixed when increasing $d$ the results from relative flatness would imply that generalization does not deteriorate, which would contradict this paper. I suspect, however, that this is ruled out in the construction of the proof: since the pseudo-sparse functions need to have a number of localized \"bumps\" that grows with $d$, $m$ would grow with $d$. If that is the case, it seems that indeed it is not the input dimension that ultimately governs the generalization ability, but the dimension of the feature extractor. If my argument is correct, this should be discussed openly.\n- The discussion on low-norm solutions vs flat solutions is very interesting. I wonder whether this is particular to the MSE, since for the cross-entropy loss larger weights (at least in the penultimate layer) imply higher confidence, which in turn implies a flatter minimum [2]. So one could use this result to support flatness measures that take weight norms into account [1,3]. \n\n[1] Petzka, Henning, et al. \"Relative flatness and generalization.\" Advances in neural information processing systems 34 (2021): 18420-18432.\n\n[2] Walter, Nils Philipp, et al. \"The uncanny valley: Exploring adversarial robustness from a flatness perspective.\" arXiv preprint arXiv:2405.16918 (2024).\n\n[3] Liang, Tengyuan, et al. \"Fisher-rao metric, geometry, and complexity of neural networks.\" The 22nd international conference on artificial intelligence and statistics. PMLR, 2019.", "limitations": "Limitations are adequately addressed and assumptions are explicitly mentioned.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- Interesting minimax lower bound using pseudo-sparse functions, where neurons have large weights but rarely activate. \n- The analysis of flatness and generalization remains an important subject. The investigation using hard-to-learn functions is conceptually interesting.\n- Although experiments are synthetic, they are well-designed and support the theory.\n\n**Weaknesses:**\n- It would have been great to test some assumptions in more realistic scenarios.", "was_revised": true, "final_justification": "I remain convinced that this is a very solid paper and therefore maintain my score.", "rebuttal": "Thank you for your support and insightful comments! Responses to your questions below:\n\n> The theoretical insight is interesting when compared to the results from relative flatness [1].\n\nThanks for bringing up the Relative Flatness paper [1]. We will cite and appropriately discuss that work. However, while both [1] and our paper study how flatness is connected to generalization, the settings of the two papers seem very different, and consequently, the nature of the results is different.\n\nFirst and foremost, the definition of flatness in [1] seems to *condition on* the feature map $\\phi$, i.e., the loss function is not a function of the parameter of $\\phi$ and the first layer weights and biases are not learned. On the otherhand, in our paper, the loss takes *both* the first and second layer weights and biases as input. Our motivation is to study feature learning. Thus, in our setting, we do not consider a fixed feature map $\\phi$.\n\nSecond, we focus on the overparameterized ($m>n$) regime with the hope of understanding whether \"flatness/EoS/MinimaStability\" can be used to explain the generalization of neural networks in this regime. In the generalization bound (Theorem 6) in [1], it seems that $m$ (this is $K$ in our paper) cannot be too large before the $n^{-2/(m+4)}$ bound becomes vacuous. Our upper bound is **independent** of $m$. Thus, when $m$ is sufficiently large, our bound is tighter than that of Theorem 6 of [1]. Furthermore, there was not a lower bound established in [1] that requires an exponential dependence on $m$.\n\n> Now if $m$ was kept fixed when $d$ increasing, the results from relative flatness would imply that generalization does not deteriorate, which would contradict this paper.\n\nThe reviewer is absolutely right here! Our lower bound does have an implicit assumption that $m$ is sufficiently large.  If $m$ is fixed and $n\\rightarrow \\infty$, then we are in the classical regime and one can obtain an $O(\\sqrt{dm/n})$-type uniform generalization gap bound (for all solutions and thus applicable to flat solutions as well). This bound does not have $\\exp(d)$ dependence. In this under-parameterized regime, our upper bound (that depends exponentially on $d$) is still valid, but vacuous. Our exponential lower bound requires, naturally, that $m$ be sufficiently large to avoid the contradiction. A sufficient condition for our bound to kick in is that $m = \\Omega(n)$. \n\nIn particular, we highlight that our Theorem 3.7 does not have this condition on $m$. This is because it deals with the weighted variation class directly, which can be viewed as a space of neural networks with arbitrary (even infinite) width and so the neural networks parameterization is abstracted away.\n\nWe will add the above discussion to the paper to increase readability. \n\n>  How do the theoretical results relate to deep learning practice? There, input dimensions have grown enormously (LLMS and LVLMs), but while datasets have grown enormously as well, it seems their growth was not exponential in the input dimension.\n\nThis is a good point. We thought about this too. If the input data are truly somewhat uniformly distributed on a ball in $\\mathbb{R}^d$ then our lower bound would apply directly there. However, images and texts are very structured, and we believe they are embedded in a much lower-dimensional manifold.  The key to bridge the theory-practice gap could be to study how neural networks adapt to such low-dimensional structures.\n\n\n> Discussion on low-norm vs flat solutions is interesting. Does it only apply to MSE?\n\nThe function-space characterization of low-norm (i.e., weight decay) solutions is independent of the loss function of interest, thus the resulting generalization bounds apply to other losses. On the other hand, the function-space characterization of \"flatness\" in terms of the largest-eigenvalue of Hessian is sensitive to the choice of loss functions. \n\nMore specifically, we believe that the key features of low-norm vs flat solutions that we discovered in this paper do apply beyond MSE although there might be other factors to consider for other loss functions.\n\nIn particular, we studied MSE as a first step. Some parts of the techniques work beyond MSE but this would require a thorough study, e.g., if the Hessian decomposition of other twice-differentiable loss functions has a similar structure to that of the square loss. The papers that you brought up are interesting (thanks!), and we will look into them more closely to understand the difficulty of going beyond MSE as well as the merits of other weight-norm sensitive flatness definitions for future work."}, {"review_id": "LqY8PMImCM", "reviewer": "Reviewer_UZNs", "summary": "This work considers studies generalization bounds for a subset of functions which can be implemented by a two layer ReLU network. More specifically, the authors consider functions corresponding to local minima of a sample least squares loss which are $\\epsilon$-stable,  such functions are shown to be regular with respect to a certain variation norm. In addition, uniform lower and upper generalization bounds are provided which decay to zero zero as the number of samples grows, the input dimension $d$ is assumed constant. For these bounds to be useful the sample complexity needs to grow exponentially in the data dimension.", "questions": "- Proposition 2.2: I don't see how this can be true for any $\\epsilon$, if this where true then wouldn't this mean that you get convergence to the minimizer from any initial condition? Perhaps another way of putting it is that the linearized dynamics can't be a good approximation for any $\\theta$ right unless unless the loss is a quadratic form in the parameters? \n\n- A small comment, you also say on line 29 that ReLU networks are thought not to benignly overfit, but there are quite a number of papers now showing this exact phenomenon for $d$ growing like $n^2$ (or even $n$ for leaky ReLU networks) instead of being fixed. In addition, the specialization of neurons (i.e., sparse activations) is often how one shows benign overfitting.\n\n- Can you provide some intuition as to the origin of the weighting function given in (4), how should one think about this?\n\n- Does your class of $\\epsilon$-stable functions only include those minimizers for which the loss is twice differentiable? What happens to minimizers which are not differentiable / are on the boundary between cells?\n\n- What is special about ReLU here? Would similar results also hold for Leaky-ReLU, what is stopping you extend your techniques to other activation functions? Also what is the main technical barrier moving to 3 layers as opposed to 2?\n\n- To confirm / clarify the main takeaway, is it the implicit bias of GD (i.e., minima that are stable for gradient descent) do not in general guarantee good generalization, unless you have an exponentially large amount of data in the input dimension $d$ (which then perhaps is not too surprising for data arising on a compact domain), and this is in contrast to weight decay?", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Understanding the role of flat / stable minima is, at least in my opinion, a topic of significant interest, the paper is well written and clear and the technical contributions seem good. Overall I think this paper should be accepted.", "was_revised": true, "final_justification": "This paper has limitations in terms of its practical relevance with regard to setup and assumptions. However, I think the theoretical analysis and observations are interesting: in particular, this work shows that flatness alone as measured by the largest eigenvalue of the Hessian does not guarantee good generalization / an escape from the curse of dimensionality and empirically illustrates a setting in which this pseudo sparsity phenomenon occurs.", "rebuttal": "Thank you for your support and insightful comments! Responses to your questions below:\n\n>  Proposition 2.2: I don't see how this can be true for any $\\epsilon$, if this where true then wouldn't this mean that you get convergence to the minimizer from any initial condition? Perhaps another way of putting it is that the linearized dynamics can't be a good approximation for any $\\theta$ right unless unless the loss is a quadratic form in the parameters?\n\nOur proposition is not a claim about global convergence from an arbitrary starting point. Instead, it is about a local-stability condition. The purpose is to use this local analysis to derive a static condition that characterizes the stable minima. The \"initial condition\" in our stability definition refers to the moment an iterate enters the local quadratic region of a local minimum, $\\theta^\\star$. The proposition then shows that the curvature condition, $\\lambda_{max}(\\nabla^2\\mathcal{L}(\\theta^\\star))\\leq 2/\\eta$, is necessary and sufficient for the linearized dynamics to remain trapped near $\\theta^\\star$. A rigorous proof can be found in [Qiao et al 24, Appendix C].\n\nIt is crucial to note that while this mathematical proposition about the *linearized system* holds for any $\\epsilon$, we agree with the reviewer that this linearization is only a faithful approximation of the true GD dynamics for small $\\epsilon$. This local regime is precisely where the concept of stability is meaningful, and it allows us to define the entire set of stable minima, which is the true object of our paper's generalization analysis. The key idea is that we are not analyzing the convergence from an arbitrary initialization, but rather characterizing the intrinsic properties of the entire set of stable minima that GD could possibly find. \n\nRef: [Qiao et al 24] Qiao et al Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes, Neurips 2024\n\n>  A small comment, you also say on line 29 that ReLU networks are thought not to benignly overfit, but there are quite a number of papers now showing this exact phenomenon for $d$ growing like $n^2$ (or even $n$ for leaky ReLU networks) instead of being fixed. In addition, the specialization of neurons (i.e., sparse activations) is often how one shows benign overfitting.\n\nOur work is motivated by the observation that standard ReLU networks typically do not benignly overfit in fixed-dimensional, noisy regression. The recent work by [Haas et al. 2023] supports this, showing that benign overfitting in this setting requires modifying the ReLU activation with special high-frequency functions. In their paper, Theorem 4 explicitly confirms that standard ReLU NTKs are inconsistent when overfitting and Figure 1c empirically shows that the standard ReLU network exhibits harmful overfitting. This suggests the phenomenon is not intrinsic to standard ReLU. We would be grateful if the reviewer could share specific citations that show otherwise.\n\nRef: [Haas et al. 2023]: Haas et al, Mind the spikes: benign overfitting of kernels and dneural networks in fixed dimension. Neurips 2023\n\n>  Can you provide some intuition as to the origin of the weighting function given in (4)...\" & \"What is special about ReLU here? Would similar results also hold for Leaky-ReLU, what is stopping you extend your techniques to other activation functions?\n\nThese are great questions! We would answer these two questions by explaining their common mechanism organically.\n\nThe weight function $g$ arises from two complementary perspectives: a static analysis of the loss landscape's curvature and a dynamic view of representation learning.\n\nFrom a static viewpoint, as derived in [Nacson et al. 2023, Appendix F], the form of $g(  {u},t)$ emerges directly from a careful analysis of the loss function's Hessian matrix for a two-layer ReLU network. Intuitively, a neuron defined by the hyperplane $  {w}^{\\top}  {x} - b = 0$ contributes to the Hessian based on how many data points it activates. Hyperplanes that are \"on the boundary\" of the data support (i.e., activate very few data points) contribute less to the Hessian. Consequently, the weight $g(  {u},t)$ is small in these regions, meaning the stability condition imposes a weaker regularization on neurons that are rarely active.  ReLU is analytically special because its hard-sparsity property leads to a sparse loss Hessian, which allows for a clean derivation of the weighting function $g(  {u},t)$ that is central to our analysis.\n\n\nFrom a dynamic learning perspective, one can form an intuitive picture of how these pseudo-sparse neurons might emerge. High-dimensional geometry may make it easier for neurons' activation boundary to drift to shatter the dataset and isolate a very small subset of data points for each of them. Such a neuron only receives gradients from a few nearby points and if those points are already well-fit, the local gradient on this neuron's parameters can vanish, causing it to get \"stuck\" nearby the boundary. The small value of $g(  {u},t)$ near the data boundary can be seen as the mathematical manifestation of this hypothesized dynamic: it creates \"space\" within the class of stable functions for these trapped, high-magnitude neurons to exist, a possibility our lower bound construction then formalizes.\n\n\nInformally speaking, **our work uses the set of stable minima as a prism to understand the dynamics of GD's representation leanring**. The insight gained from ReLU is a general one that should be reasonably extrapolated to other activations like Leaky-ReLU, where weak negative gradients also fail to solve the underlying problem. Our intuition is that a small leaky coefficient would yield similar results (some light experiments confirmed that), as the weak gradient in the negative domain is likely insufficient to overcome this scattered signal problem. A large coefficient (e.g., an absolute value activation) might behave differently, but a rigorous analysis is challenging. We will conduct more experiments to investigate this behavior.\n\nRef: [Nacson et al. 2023]: Nacson et al. The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks, ICLR 2023.\n\n>  Does your class of $\\epsilon$-stable functions only include those minimizers for which the loss is twice differentiable...\n\nWe thank the reviewer for this very insightful question that touches upon a key technical aspect of our work. We'd like to highlight three points. First, even though we are motivated by stable minima, the set of interest (below Prop 2.2) covers all NNs with Hessian's largest-eigenvalue being small. This set includes not just twice-differentiable stable local / global minima, but also many other low-curvature regions that are not local / global minima. Second, non-differentiable points in two-layer ReLU networks correspond to points where the hyperplane of a ReLU unit coincides with a data point. This is a measure 0 set. If we initialize the network randomly from a density and optimize using gradient descent (with constant stepsize), with probability 1, the whole trajectory will not run into such points. (see Footnote 2 in the paper). \nThird, analyzing twice-differentiable solutions is, in some sense, without loss of generality. This is because we can perturb the a non-differentiable solution infinitesimally to get a differentiable solution.  Thus, by the Lipschitzness of the loss, it suffices that there is a differentiable solution with low-curvature near the non-differentiable solution of interest.\n\n\n\n\n>  Also what is the main technical barrier moving to 3 layers as opposed to 2?\n\nMoving from a two-layer to a three-layer network introduces two primary technical barriers that would require highly non-trivial extensions of our current analytical framework.\n\nFirst, our analysis of the generalization gap and estimation error relies on calculating the metric entropy of some function class. For a two-layer ReLU network, the function space can be related to dictionary learning and ridge spline approximations, allowing us to leverage existing tools to bound its complexity [Parhi & Nowak 2023]. For a three-layer network, is is not even known what is the ``correct'' function class to consider. Even if the class were known, estimating the complexity of the corresponding function class would be significantly more involved and would require substantial new theoretical work.\n\nSecond, the derivation of the data-dependent weighting function is tied to a precise analysis of the loss function's Hessian matrix. For a three-layer network, the Hessian becomes much more complex.\n\nRef: [Parhi & Nowak 2023]: Rahul Parhi & Robert Nowak Near-minimax optimal estimation with shallow ReLU neural networks. IEEE Transcations on Information Theory, 2023\n\n>   To confirm / clarify the main takeaway...\n\nYes, the reviewer's summary is an accurate takeaway within the setting of our paper. The implicit bias of gradient descent towards stable minima does not, on its own, prevent the curse of dimensionality, leading to a sample complexity that grows exponentially with the input dimension $d$. This is in sharp contrast to explicit regularization like weight decay.\n\nHowever, we wish to add a crucial clarification: the driving force behind this phenomenon is the data distribution's interaction with the high-dimensional geometry, not just the ambient dimension in isolation. Our work highlights this \"data-dependent regularity\" and particularly examines the case of the uniform distribution on a ball. As mentioned in the discussion part of the paper, the induced weighted function $g$ inherits the full geometry of the data and becomes harder to describe and interpret for arbitary distributions, so we leave such an investivgation as future work."}, {"review_id": "ZQpPH58Ala", "reviewer": "Reviewer_WMiE", "summary": "The flatness of a parameter at a minima of the loss is typically correlated with the generalization, even though obstacles like reparametrization affect this claim.\nThis paper shows that dimensionality weakens the correlation by providing mostly theoretical results for two layers ReLU networks.\n\nMore precisely, after laying out a definition of flat or *stable minima* based on linear stability the paper first shows that flatness in parameter space translates to smoothness of the implemented function in the sense of a weighted variation norm.\nThis variation norm is defined for a function $f$ by finding a corresponding minimal representative $f_\\nu$ of $f$ inside the class of infinite width shallow ReLU networks and computing the total variation of the measure $\\nu$ defining $f_\\nu$ multiplied by a weight function that depends on data.\nThen, 4 bounds specific to stable minima are given, first on the generalization then on robustness to noise.\nUpper bounds show that stable minima can generalize and converge towards the noiseless function (i.e. infinite data leads to perfect results).\nLower bounds reveal an exponential dependency on the dimension.", "questions": "1. **Intuition on the weight function** I interpret the weight function as a multiplication between (a) the expected activations of a neuron and (b) the probability of a neuron being activated times a data norm in the case the neuron is activated. In particular, what is the role of the (b) term ? And why can't the weight function $g(u,t)$ be simply $\\tilde g(u,t)$ ?\n1. **Sharpness-Aware Minimization** (SAM) (e.g. \"Sharpness-Aware Minimization for Efficiently Improving Generalization\" by Foret et al, \"ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networks\" by Kwon et al) seem to work on vision datasets like CIFAR, which are very high dimensional. They use other models but do you have comments on the relation with your work and in particular on the fact that dimensionality didn't seem to be blocking in SAM ?\n1. **Pseudo sparsity** I am a bit sceptical on the pseudo-sparsity phenomenon being specific to flatness. When trying to fit perfectly a function without regularization, the parameter might diverge to endlessly try to minimize the loss. This has been theoretically studied in \"Best k-Layer Neural Network  Approximations\" by Lim et al. If you think the pseudo-sparsity phenomenon is fundamentally different and specific to flat minima, could you contrast the 2 phenomena ?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Quality\nThe paper seems technically sound. The theoretical claims are supported with a detailed technical appendix.\nExperimental results are complementary to the theoretical claims, but are more of a sanity check than an experimental validation.\n\nHowever I have some doubts on the upper bound of Corollary 3.3:\n- with a low loss and a high learning rate it seems the norm could become negative.\n- in the paragraph below Corollary 3.3: in case of high loss, scaling $\\eta \\to \\infty$ would not be enough to get an affine function which has 0 seminorm. The upperbound does not necessarily converge to 0 if the loss is high so I don't understand this claim.\n\n## Clarity\n\nThe exposition is good overall except for the beginning of section 3.\nThe different steps leading to the comprehensive view of the weighted variation seminorm are difficult to follow.\nI think adding motivation or intuition along the way (on the choice of the weight function and its role w.r.t. to the measure, $\\infty$ width NN, Radon measure, total variation of a measure) could help the reader, like it is done in the previous section.\\\nLess critically in theorem 3.7 it is not clear exactly over which set $\\hat{f}$ can vary.\n\n\n**Minors**\n- line 187: in the definition of $\\mathcal F_{\\text{stable}}(\\eta)$, there is no condition on the $\\theta$ being a minimum but the text after refers to stable minima.\n- line 148: \"sharp minima can also be generalized\" -> \"can generalize\".\n- line 218: \"any ReLUs ... <del> is </del> can be\".\n- Figure 1: missing x/y axis labels.\n- Figure 2: in the caption, orange instead of red.\n- Notation in theorem F.8 in appendix: $\\hat{R}$ vs $\\hat{R_n}$, $f_\\theta$ vs $f$.\n- $\\phi$ is never defined as ReLU\n\n\n## Significance\n\nThis paper reveals that dimensionality is another important component to take into account when studying the relation between flatness and generalization.\nA theoretical understanding of this phenomenon could be of great use to the community as it might help distinguishing when flatness is relevant and when it is not (however, see my question on SAM below).\nMoreover the paper shows a methodology on how to link the parameter and function spaces, which is an important step when thinking about identifiability for example.\n\nOne weak point is that the lower bounds, which are the most significant results since the upper bounds are basically feasibility statement, are formulated for parameters that are not the outcome of a training process.\nFor example, this means that the lower bound of theorem 3.5 could be achieved for exotic configurations inside $\\mathcal F_{\\text{stable}}(\\eta)$ that are not the solutions found by a typical optimization algorithm (as for theorem 3.7 see \"Clarity\" above).\nThis fact limits the insights provided by the paper.\n\nThe experiments reported in Figure 1, though limited in scope, address the gap empirically: it is reported that solutions found with high learning rate (stable minima) suffer when increasing the dimensionality.\n\n## Originality\n\nThere were already results on the smoothness of function implemented by stable minima, corollary 3.3 is a similar result for another definition of function smoothness.\n\nWhile smoothness results have also been obtained for the multivariate case, the part of this paper focusing explicitly on the quantifying the role of dimension on generalization and overfitting noise is to the best of my knowledge new (and critically, the bounds).", "was_revised": true, "final_justification": "In their rebuttal the authors clarified a misconception I had which was that the lower bound in theorem 3.7 could be achieved only by very specific functions and was therefore not very informative for typical parameters obtained via gradient descent.\nMoreover they also offered helpful intuitive explanations that allowed me to better grasp part of their work, in particular regarding how pseudo-sparsity enables even stable minima to overfit.\nAdditionally, the authors clarified the scope of their contributions with respect to SAM and addressed my concerns about Corollary 3.3.\nOverall, I find the paper presents an interesting and motivated negative result: that flatness alone is insufficient to bypass the curse of dimensionality.\nThe theoretical analysis is well detailed, and some empirical validation is provided.\nTherefore, I see no reason to recommend against acceptance.\nNotably, the authors also convincingly addressed other reviewers’ comments on the role of network width.\nI still chose a low confidence score because I am not an expert on the mathematical tools used in the paper and found parts of the paper challenging to follow.", "rebuttal": "Thanks for your support and detailed feedback! We will check and revise the minors. Responses to your questions below:\n\n>   For example, this means that the lower bound of theorem 3.5 could be achieved for exotic configurations inside $\\mathcal{F}_{\\text{stable}}(\\eta) $ that are not the solutions found by a typical optimization algorithm (as for theorem 3.7 see \"Clarity\" above). This fact limits the insights provided by the paper.\n\nThank you for mentioning this critical point. We argue that the configurations used in our lower bound are not exotic because they are precisely the structures that emerge from a typical training process, which our experiments empirically confirm.\n\nOur work uses the set of stable minima as a prism to understand the dynamics of GD's representation leanring. Within this paradigm, our lower bound construction (see Append B.4 Figure 9 for the visualization of our lower bound construction) provides a intuition: it proves the existence of a \"hard-to-learn\" solution built from pseudo-sparse neurons, hinting at a dynamic where neurons pathologically shatter the dataset and get 'stuck' fitting local points. Moreover, the higher the dimension is, the easier for these neuron to shatter the dataset. \n\nFurthermore, our experiments then provide direct empirical evidence for this theoretical construction. As shown in (Figure 1 right panel, Appendix A.1, A.2), vanilla Gradient Descent converges to a solution containing many neurons that exhibit these exact characteristics: a very low activation rate but a high weight norm. This demonstrates that the fundamental components of our lower bound represents a tangible failure mode produced by standard optimization algorithms in high dimensions.\n\n\n>Intuition on the weight function I interpret the weight function as a multiplication between (a) the expected activations of a neuron and (b) the probability of a neuron being activated times a data norm in the case the neuron is activated. In particular, what is the role of the (b) term ?\n\nThis is a great question! As derived in [Nacson et al. 2023, Appendix F], the form of $\\tilde{g}(  {u},t)$ is derived by brute-force computation of the loss function's Hessian matrix for a two-layer ReLU network:$$\n\\nabla_{\\theta}^2\\mathcal{L}=\\frac{1}{n}\\sum_{i=1}^n\\nabla_{  {\\theta}}f_{\\theta}( x_i)\\nabla_{\\theta}f_{\\theta}(x_i)^{\\top} + \\sum_{i=1}^n(f_{\\theta}(x_i)-y_i)\\nabla^2_{\\theta}f_{  \\theta}(x_i)\n$$ \n\nIntuitively, a neuron defined by the hyperplane $  {w}^{\\top}  {x} - b = 0$ contributes to the Hessian based on how many data points are in its activation region. Hyperplanes that are near the boundary of the data support (i.e., activate on very few data points) contribute less to the Hessian. Consequently, the weight $g(  {u},t)$ is small in these regions. This means that the stability condition imposes a weaker regularization on neurons that are rarely active.  \n\n\nRef: [Nacson et al. 2023]: Nacson et al. The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks, ICLR 2023.\n\n\n\n>  why can't the weight function $g(  {u},t)$ be simply $\\tilde{g}(  {u},t)$?\n\nNote that any function $f$ implemented by a ReLU neural network, can be displayed by different sets of parameters. Our goal is to find a lower bound on the top eigen vector of the Hessian for any implementation of $f$. However, choosing between $\\tilde{g}(  {u},t)$ and $\\tilde{g}(-  {u},-t)$ directly according to the sign of the hidden weight vector $  {w}$ is implementation dependent. For example, a linear function can be implemented by $  {w}^{\\top}x=\\phi(  {w}^{\\top}x-t)-\\phi(-  {w}^{\\top}x+t)$ and by shifting $t$, we can get infinitely many implementations. Therefore, the choice of $\\min(g(  {u},t),g(-  {u},-t))$ guarantees that the bound applies to all possible implementations of the function $f$. \n\n\n>  However I have some doubts on the upper bound of Corollary 3.3...\n\nCorollary 3.3 is deduced from Theorem 3.2 in our paper. The right handside of the inequality in Theorem is deduced from\n\n\n$$1 + 2\\sum_{k=1}^Ka_k \\tilde{g}(u_k,t_k)\\leq \\lambda_{max}(\\frac{1}{n}\\sum_{i=1}^n \\nabla_{\\theta} f(x_i) \\nabla_{\\theta} f(x_i)^{T})$$\n\n\nwhere $a_k$ is the path norm of the $k$-th neuron, see [Nacson et al. 2023, Appendix F. eq 47, 48, 50, 52-54]. Therefore, the term $\\lambda_{max}(\\frac{1}{n}\\sum_{i=1}^n\\nabla_{\\theta}f(x_i) {\\nabla}_{\\theta} f(x_i)^{\\top}) $ is at least 1. In other words, if $\\eta >2$, then the set of stable solutions is an empty set. In practice, when $\\eta\\geq 1$, gradient descent cannot converge even for a linear ground true functions with mild noise. Therefore, it is almost impossible to use a very large learning rate to achieve a low empirical risk.\n\n>Sharpness-Aware Minimization (SAM) (e.g. \"Sharpness-Aware Minimization for Efficiently Improving Generalization\" by Foret et al, \"ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networks\" by Kwon et al) seem to work on vision datasets like CIFAR, which are very high dimensional. They use other models but do you have comments on the relation with your work and in particular on the fact that dimensionality didn't seem to be blocking in SAM?\n\nSAM modifies the loss function, and therefore has a different loss landscape that comes with no sharp minima.  We do not modify the loss function and focus on what gradient descent can stably find. Our results thus do not apply to the solution of SAM. For CIFAR-type datasets, we believe there are other effects that might prevent the curse-of-dimensionality, such as the intrinsic low-dimensional data manifold that the neural networks might be able to adapt to. The takeaway from the investigation of four paper is that stability / flatness is not the reasons that neural networks avoid the curse of dimensionality.\n\n\n\n\n\n> Pseudo sparsity I am a bit sceptical on the pseudo-sparsity phenomenon being specific to flatness. When trying to fit perfectly a function without regularization, the parameter might diverge to endlessly try to minimize the loss. This has been theoretically studied in \"Best k-Layer Neural Network Approximations\" by Lim et al. If you think the pseudo-sparsity phenomenon is fundamentally different and specific to flat minima, could you contrast the 2 phenomena ?\n\nIt is not about pseudo-sparsity being specific to flatness, but rather such pseudo-sparse (and overfit) solutions can be found *even if* we impose the flatness constraint. \n\nCompared to the work of [Lim et al.], which studies a large-weight solution that interpolates (and overfits) the noisy labels, our study aims at understanding whether flatness is sufficient in ruling out such bad solutions. Our paper shows that while the flatness constraint is strong enough to rule out the large weights on neurons that activate frequently, the neurons that activate rarely can still be permitted to have large weights. This was a very surprising observation to us. Our result also highlights that we should not solely depend on the implicit bias of GD to prevent overfitting.\n\nTherefore, we believe the two phenomena are fundamentally different, and our work is novel."}]

Author rebuttal:

Meta-review: This paper presents an in-depth study of the generalization performance and landscape properties of ReLU networks beyond the interpolation regime. The style is formal, pleasant, precise; the results are interesting, well supported numerically, and of great interest in the community of theoretical deep learning.

All reviewers agree the paper deserved publication, and I 100% agree with this. I congratulate the authors for focusing on such fundamental properties of simple models, and I find reading this extremely refreshing.
Decision: Accept (spotlight)