🤖 machine learning

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

This paper establishes pathwise connectivity of sublevel sets in shallow ReLU networks with constrained weights and $\ell_1$ regularization by deriving explicit loss-landscape barrier decay rates that transition from approximation bounds to near-optimal connectivity guarantees, validated through theoretical proofs and numerical experiments.

Original authors: Saveliy Baturin

Published 2026-08-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Saveliy Baturin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Landscape of Learning: Why Some Paths Are Easier Than Others

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This isn't just any mountain range; it's the "loss landscape" of a neural network, a computer brain made of mathematical layers. In this world, every possible setting of the computer's internal knobs (called parameters) corresponds to a specific spot on the map. The height of the land at that spot tells you how well the computer is doing its job: lower is better, higher is worse.

For a long time, scientists worried that this landscape was a nightmare of "spurious valleys"—deep pits that looked like the bottom but were actually just traps. If you started in one low valley and tried to walk to another low valley, you might think you'd have to climb a massive mountain in between, forcing the computer to forget everything it learned before it could learn something new. This paper dives into a specific type of computer brain called a "shallow ReLU network." It asks a simple but profound question: If two different settings of the brain both work well (sitting in the same low valley), is there a smooth, safe path connecting them, or do we have to climb a huge barrier to get from one to the other? The answer turns out to depend on how wide the network is and how we measure the "height" of the mountains.

The Paper's Big Discovery: Flattening the Mountains

This paper by Saveliy Baturin is like a cartographer drawing a new map for these computer brains. The author proves that for a specific kind of network, the scary mountains between two good solutions are actually much smaller than we feared. In fact, as you make the network wider (give it more neurons, or "neurons" in the analogy), the barrier between any two good solutions shrinks until it almost disappears.

Think of the network's settings as a giant, flexible rubber sheet. If you have two points on this sheet that are both low and happy, the paper shows you can stretch a rubber band between them without it snapping or climbing too high. The "height" of this rubber band—the extra effort needed to move from one solution to the other—is the "barrier." The paper proves that for networks with a certain structure (where the first layer of knobs is constrained to stay within a specific size limit), this barrier gets tiny very quickly as you add more neurons.

The "Magic" of Width
The most exciting part is the math behind the shrinkage. The paper calculates exactly how fast this barrier disappears.

If the data has 2 dimensions (like a flat map), the barrier shrinks at a rate related to the width of the network raised to a specific power.
If the data has 3 dimensions, it shrinks even faster.
In the simplest case, where the data is just a single line (1 dimension), the paper proves something even cooler: if you have at least 4 neurons, the barrier is exactly zero. You can walk from any good solution to any other without ever going up a single step. It's like having a perfectly flat floor between two rooms.

How They Did It: The "Cluster Merge" Trick
So, how do you prove there's a flat path? The author uses a clever construction, like a game of "musical chairs" for the neurons.

The Squeeze: Imagine you have a messy room with 100 people (neurons) trying to fit into a small space. The paper shows you can "compress" this group. You find people who are standing very close together (similar neurons) and gently merge them into one person, adjusting their voices (weights) so the total sound (the prediction) stays the same.
The Sphere: The paper also uses a trick called "monotone sphericalization." Imagine the neurons are on a balloon. The author shows you can slide them all to the surface of the balloon (making them all the same size) without changing what the computer predicts, while simultaneously making the "cost" of the solution go down.
The Bridge: Once you've squeezed both starting points into a compact, standard form, you can easily draw a straight line between them. The paper proves that the "cost" of this line never spikes too high.

The Numbers Behind the Magic
The paper doesn't just guess; it calculates.

For networks with 2 or more dimensions, the barrier height decays at a rate of $O(m^{-1/(n-1)})$ , where $m$ is the number of neurons and $n$ is the dimension of the data.
When the paper connects this to how well the network learns (approximation theory), it finds a "near-optimal" rate of $O(m^{-1/(n+1)})$ .
In the real-world tests described in the paper, the author ran 720 pairs of solutions on networks with widths of 16, 32, 64, and 128. They found that for networks with at least 16 neurons, the highest point on the path between two good solutions was never more than $1.66 \times 10^{-5}$ above the starting level. That is an incredibly tiny bump, essentially a flat floor.

What This Paper Does NOT Say
It is important to know what this paper doesn't promise.

It's not a training guide: The paper proves a path exists, but it doesn't tell a computer how to find that path using standard training methods like gradient descent. It's like proving a tunnel exists through a mountain, but not giving you a map to find the entrance.
It's not for all networks: This result is specific to "shallow" networks (one hidden layer) with a specific type of constraint on the first layer. It doesn't automatically apply to the very deep, complex networks used in today's biggest AI models.
It's not about "perfect" connectivity for all cases: While the 1D case is perfectly connected, the higher-dimensional cases have a tiny, non-zero barrier that gets smaller as the network grows. The paper is careful to say this is a "barrier bound," not a claim that the landscape is perfectly flat everywhere.

The Takeaway
This paper is a reassuring mathematical proof that for a specific class of neural networks, the "loss landscape" is not a jagged, impossible maze. Instead, it's a terrain where wide networks create smooth, low-energy highways between different good solutions. The "mountains" between solutions are real, but they are so small and so easy to cross that, in practice, a wide network can likely move between different ways of solving a problem without getting stuck. The author verified this with computer simulations using both standard regression (Huber loss) and classification (binary cross-entropy), finding that the "barrier" remained tiny even when the rules of the game changed slightly.

In short: If you build a wide enough network with the right constraints, the path between two good ideas is almost as flat as the ideas themselves.

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

Problem Statement
This paper addresses a quantitative question regarding the topology of the loss landscape for one-hidden-layer ReLU neural networks with constrained first-layer weights and an $\ell_1$ penalty on the output layer. Specifically, it investigates how much the regularized risk must increase when connecting two arbitrary parameter points within the same sublevel set via a continuous path. The study focuses on models where the loss function is convex and globally Lipschitz with respect to the scalar logit, a condition satisfied by losses like binary cross-entropy but not by quadratic loss on unbounded domains.

Methodology
The author develops a finite-width construction to connect any two points in a common sublevel set. The methodology relies on three primary mechanisms:

First-Order Perturbation Bridge: Unlike previous work (e.g., Freeman and Bruna) that relied on quadratic perturbation estimates for quadratic losses, this paper establishes a direct Lipschitz bound. By leveraging the global Lipschitz continuity of the loss in the logit, the author replaces the quadratic expansion with a first-order estimate to control the risk increase during parameter interpolation.
Monotone Sphericalization: The author utilizes the positive homogeneity of ReLU networks ( $ReLU(w^\top x) = c ReLU((w/c)^\top x)$ ) in a specific direction compatible with the $\ell_1$ penalty. They construct a path that monotonically moves active first-layer weights from the interior of the unit ball to the unit sphere while simultaneously reducing the corresponding output coefficients. This process preserves the predictor and non-increases the objective, effectively reducing the relevant metric dimension of the problem.
Cluster Merging and Compression: Using covering arguments on the unit sphere, the author demonstrates that active neurons with similar directions can be merged. This "cluster merging" allows the reduction of the number of active neurons (compression) while controlling the loss increase. This is combined with a Maurey-type sampling argument to relate approximation rates to landscape connectivity.

The theoretical framework is complemented by a "theorem-aligned" computational diagnostic. This experiment verifies the invariants of the construction (parameter constraints, compression) and compares three path types: direct linear interpolation, a modified certified Dynamic String Sampling (DSS) algorithm, and the explicit proof-inspired path (involving cluster merging and canonical embedding).

Key Contributions

Finite-Width Barrier Bounds: The paper proves an attained, finite-width barrier bound for losses that are convex and Lipschitz in the logit. It provides an explicit perturbation estimate and a relocation argument for inactive neurons, avoiding asymptotic-only arguments.
Uniform Connectivity Rates:
- For input dimension $n \ge 2$ , the paper establishes a uniform thickening rate of $O(m^{-1/(n-1)})$ for fixed sublevels above the limiting approximation value, where $m$ is the network width.
- For $n=1$ , the paper proves exact connectivity (zero thickening) for every width $m \ge 4$ , utilizing a two-ray dictionary structure.
Approximation-to-Topology Transfer: The author connects approximation theory to landscape topology. They prove an internal approximation rate of $e(l) - e_\infty = O(l^{-1/2})$ for the regularized objective. By combining this with the geometric compression rates, they derive a near-optimal barrier rate of $O(m^{-1/(n+1)})$ for moving levels near the optimum.
Explicit Construction: The paper provides a constructive path that connects endpoints via a sequence of sphericalization, compression (merging clusters), and interpolation to a canonical reference network, ensuring the path remains within the constrained parameter space.

Results

Theoretical: The study confirms that for constrained shallow ReLU networks, the loss landscape becomes increasingly connected as width increases. The "energy barrier" (the maximum excess risk along the connecting path) decays polynomially with width.
Empirical: Numerical experiments on finite seeded distributions (using Huber loss and binary cross-entropy) validate the theoretical mechanisms.
- For widths $m \ge 16$ , the "proof-inspired" path and the "certified DSS" path yielded maximal upper gaps of approximately $1.66 \times 10^{-5}$ over 720 recorded pairs, significantly outperforming direct linear interpolation.
- The constructive path remained exactly inside the selected sublevel for a high percentage of cases (e.g., 90.8% for $n=1$ ).
- Stress tests on dense representations confirmed the validity of the cluster-merging mechanism and the analytic bounds on objective increments.
- The results held for both Huber regression and binary cross-entropy, demonstrating loss robustness.

Significance and Scope
The paper claims to provide a concrete bridge from approximation theory to loss-landscape topology. Its primary significance lies in replacing asymptotic arguments with explicit, finite-width constructions that quantify the "energy barrier" between sublevel sets.

The author explicitly states the limitations of their work:

The results apply to constrained shallow (one-hidden-layer) networks; they do not claim results for arbitrary deep networks.
The findings are not convergence theorems for gradient descent or claims about training-time dynamics; they describe the geometry of the parameter space, not the trajectory of an optimizer.
The connectivity is uniform over sublevel endpoints but does not assert exact connectivity for all finite widths (except in the $n=1, m \ge 4$ case).
The barrier decay does not imply rapid optimization; the constructed path is admissible but not necessarily found by standard training algorithms.

In summary, the work demonstrates that under specific architectural constraints and loss conditions, the non-convexity of shallow ReLU networks is "benign" in a topological sense, with barriers decaying as the network width increases, governed by the interplay between approximation rates and the geometry of the active neuron directions.

The Landscape of Learning: Why Some Paths Are Easier Than Others

The Paper's Big Discovery: Flattening the Mountains

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

More like this