From Approximation Rates to Loss-Landscape Barrier Decay in Shallow ReLU Networks

Saveliy Baturin

cs.LGFeb 19, 2026

From Approximation Rates to Loss-Landscape Barrier Decay in Shallow ReLU Networks

Authors: Saveliy Baturin

Organizations: Independent Researcher, Russia.

Abstract

We study pathwise connectivity of sublevel sets for one-hidden-layer ReLU networks with constrained first-layer weights and an $\ell_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\ge2$ , while the one-dimensional two-ray dictionary gives exact connectivity for every $m\ge4$ . We also prove internally that the regularized approximation values satisfy $e(l)-e_\infty=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\times10^{-5}$ over 720 recorded pairs at widths $m\ge16$ ; 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

m=16

, followed by a DSS certificate floor near

10^{-5}

, should not be interpreted as a fitted power law.

$n$	$\widehat{e}(8)$	$\widehat{e}(128)$	zero constructive	max best-path	median direct/DSS	max $\Delta_{\rm 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\geq 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\geq 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

B_{\rm diam}=LD_{X}\left\lVert\theta\right\rVert_{1}\operatorname{diam}(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\geq 16

. Each loss–level row contains 360 recorded pairs. “Best” is the smaller certified DSS or constructive upper gap.

Shallow Neural Networks

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.

See all 51 papers

Shallow ReLU $^s$ Networks in $L^p$ -Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization
May 18, 2026Weizhao Li, Fanghui Liu, Lei ShiShallow Neural Networks Nonparametric Regression
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
Optimal approximation of smooth functions by ReLU neural networks
Oct 15, 2026Thomas NaglerNeural Network Approximation Theory ReLU Neural Networks
Department of Statistics, LMU Munich Munich Center for Machine Learning (MCML)
Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks
Aug 24, 2026Itay SafranShallow Neural Networks ReLU Neural Networks
Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev

May 18, 2026J/K move · Enter open · S save

Shallow ReLU $^s$ Networks in $L^p$ -Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization

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

Shallow Neural Networks Nonparametric Regression Neural Network Approximation Theory Generalization Bounds

Open paper AskPDF arXiv

This paper studies approximation by shallow ReLU

^s

networks,

σ_s(t)=\max\{0,t\}^s

, together with their generalization behavior under

\ell_1

path-norm control. For the

L^p

-type integral spaces

\widetilde{\mathcal{F}}_{p,τ_d,s}

1\le p\le2

, spherical harmonic analysis yields approximation bounds for shallow networks. In particular, when

τ_d

is the uniform measure and

1\le p<2

, the approximation rate is

O\!\left(m^{-\frac{p(2s+2d+1)-2d}{2dp}}\right)

for

1\le p\le p^*

and

O\!\left(m^{-\frac{p(4s+3d-1)-2d+2}{4dp}}\right)

for

p^*<p<2

, where

p^*=\frac{2d+2}{d+3}

. Approximation bounds for Sobolev spaces

W^{α,p}

1\le p<2

, are obtained through embeddings into spectral Barron spaces. For nonparametric regression with sub-Gaussian noise, path-norm-regularized shallow ReLU

^s

networks achieve minimax-optimal rates

O\!\left(n^{-\frac{d+2s+1}{2d+2s+1}}\log n\right)

over

\mathscr{B}_s

and

O\!\left(n^{-\frac{2α}{2α+d}}\log n\right)

over

W^{α,\infty}

, with matching lower bounds up to logarithmic factors.

Abstract

Shallow Neural Networks

Explore similar work

Shallow ReLUs^ss Networks in LpL^pLp-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization

Optimal approximation of smooth functions by ReLU neural networks

Every Layer Counts: An Exponential L2L_2L2​ Depth Hierarchy for ReLU Networks

Shallow ReLU $^s$ Networks in $L^p$ -Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks