We study pathwise connectivity of sublevel sets for one-hidden-layer ReLU networks with constrained first-layer weights and an ℓ1 penalty on the output layer. The data term is assumed convex and globally Lipschitz in the scalar logit. We first give a finite-width construction that connects any two points of a common sublevel through a path controlled by a loss-consistent compression functional and a first-order perturbation term. The proof replaces the quadratic perturbation estimate in the Freeman--Bruna mechanism by a direct Lipschitz bound. Positive homogeneity is then used in a direction that is compatible with the penalty: every active atom is moved monotonically from the unit ball to the unit sphere while its output coefficient is reduced. Sphere covering and cluster merging consequently give O(m−1/(n−1)) fixed-level thickening for n≥2, while the one-dimensional two-ray dictionary gives exact connectivity for every m≥4. We also prove internally that the regularized approximation values satisfy e(l)−e∞=O(l−1/2). More generally, a rate O(l−s) transfers to a near-optimal barrier rate O(m−s/((n−1)s+1)); under the standing assumptions, this yields the explicit rate O(m−1/(n+1)). A theorem-aligned finite-distribution experiment complements the analysis. The primary Huber run yields a maximal best certified upper gap 1.66×10−5 over 720 recorded pairs at widths m≥16; a matched binary-cross-entropy rerun and a 720-endpoint dense-representation stress test probe loss robustness and the active cluster-merging mechanism.
Figures & tables
Figure 1: Returned-path upper gaps over width. Columns are input dimensions n=1,2,4 ; the top row uses one fixed level across widths and the bottom row uses the width-dependent moving level. Each curve is the median of ten replicate-wise maxima over three disjoint pairs, and its shaded band is the full range of those ten maxima. “Certified DSS” is the modified recursive search with a mesh certificate; “proof-inspired” is the explicit compression–reference construction; “direct interpolation” is the straight parameter segment. Zero is displayed separately on a symmetric-log scale. The abrupt change from m=8 to m=16 , followed by a DSS certificate floor near 10−5 , should not be interpreted as a fitted power law.
n
e(8)
e(128)
zero constructive
max best-path
median direct/DSS
max Δcmp/B
gap (%)
gap
ratio
1
0.117451
0.117451
90.8
2.338e-09
9.94e+02
0.089
2
0.023544
0.023544
90.0
1.600e-05
4.60e+03
0.066
4
0.010836
0.010721
35.8
1.658e-05
6.10e+03
0.045
Table 1: Frozen main-run summary. All path quantities are upper gaps for the recorded endpoint pairs, not estimates of the uniform sublevel barrier. The three path columns use only m≥16 ; the compression ratio uses all widths. “Best path” means the smaller of the certified DSS and exact constructive upper gaps; B is the analytic cluster-merge increment bound.
Figure 2: Implementation and certificate checks. Color identifies n throughout; in panel (c), solid and dashed curves identify fixed and moving levels. (a) The monotone pooled optimization proxy, normalized by its value at m=8 ; n=1 and n=2 saturate at the tested resolution, while n=4 decreases by 1.06% . (b) For each dimension and width, the largest positive cluster-merge increment over 80 trained endpoints divided by the explicit ambient-cube bound in Proposition 5.3 ; the dash-dotted horizontal line is the analytic limit one. (c) Fraction of the 30 certified-DSS records at each dimension, width, and level whose upper path value lies within numerical tolerance 10−5 of the selected level. Legends are placed above the panels to avoid obscuring curves.
Figure 3: Dense-endpoint cluster-merging stress test on 720 fixed-level Huber endpoint representations at widths m≥16 . Before merging, all coordinates are active; at least four are removed in every record. (a) Median selected cluster diameter with the full range across 60 endpoints at each dimension and width. (b) Largest positive objective increment. (c) Largest ratio to the individual certificate Bdiam=LDX∥θ∥1diam(Q) ; the dash-dotted line marks one. The zero one-dimensional curves reflect the exact two-ray dictionary. This constructed diagnostic checks nontrivial merging and its analytic inequality, not an asymptotic exponent.
Figure 4: Loss-robustness diagnostic. Columns are input dimensions and rows separate the fixed and moving empirical sublevels. Curves show the smaller of the certified DSS and exact constructive upper gaps, normalized by the selected level. Each marker is the median of ten replicate-wise worst values over three disjoint pairs; shading is the full replicate range. The symmetric-log scale displays exact zeros without replacing them by an artificial plotting floor. The comparison is descriptive: different losses induce different objective geometries, and the moving empirical level is not a certified value of e(m) .
Loss
level
max gap
max/level
proof zero (%)
DSS tol. (%)
med. direct/level
Huber
fixed
1.649e-05
1.377e-03
55.8
44.2
2.246e+00
Huber
moving
1.658e-05
1.439e-03
88.6
68.9
2.138e+00
BCE (logits)
fixed
7.134e-03
5.032e-02
51.7
31.4
2.317e-01
BCE (logits)
moving
1.016e-01
7.956e-01
57.5
23.3
5.991e-01
Table 2: Loss-robustness summary over all dimensions at widths m≥16 . Each loss–level row contains 360 recorded pairs. “Best” is the smaller certified DSS or constructive upper gap.
Shallow neural networks use one or a few layers to learn functions, offering a setting to study efficient approximation, training dynamics, and limits of depth.
This paper studies approximation by shallow ReLUs networks, σs(t)=max{0,t}s, together with their generalization behavior under ℓ1 path-norm control. For the Lp-type integral spaces Fp,τd,s, 1≤p≤2, spherical harmonic analysis yields approximation bounds for shallow networks. In particular, when τd is the uniform measure and 1≤p<2, the approximation rate is O(m−2dpp(2s+2d+1)−2d) for 1≤p≤p∗ and O(m−4dpp(4s+3d−1)−2d+2) for p∗<p<2, where p∗=d+32d+2. Approximation bounds for Sobolev spaces Wα,p, 1≤p<2, are obtained through embeddings into spectral Barron spaces. For nonparametric regression with sub-Gaussian noise, path-norm-regularized shallow ReLUs networks achieve minimax-optimal rates O(n−2d+2s+1d+2s+1logn) over Bs and O(n−2α+d2αlogn) over Wα,∞, with matching lower bounds up to logarithmic factors.
Weizhao Li, Fanghui Liu, Lei Shi
School of Mathematical Sciences Fudan University Shanghai, China · School of Mathematical Sciences Institute of Natural Sciences and MOE-LSC2026 Shanghai Jiao Tong University Shanghai, China · School of Mathematical Sciences Shanghai Key Laboratory for Contemporary Applied Mathematics25 Fudan University Shanghai, China
We study uniform approximation of the Hölder ball H1s([0,1]D) by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every s>0 and D≥1: networks with width O(N), depth O(L), and parameter magnitude O(1) attain uniform approximation error of order (N2L2logN)−s/D. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate n−2s/(2s+D) without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.
Thomas Nagler
Department of Statistics, LMU Munich Munich Center for Machine Learning (MCML)
We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all k≥2, we construct a globally [0,1]-valued, 1-Lipschitz function realized by a depth-(k+1) network of width O(d4), whereas any depth-k network with unrestricted weights and width at most 2d(k−1)2d has squared L2 error at least 1/24 under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least 3. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case k=2 gives a compactly supported separation between depths 3 and 2 with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally [0,1]-valued and O(d)-Lipschitz and maps the unit hypercube onto [0,1]. It is computed by a polynomial-width depth-4 network, whereas any depth-3 network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.
Itay Safran
Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev