IMPORTANT: yes
The Exact Geometry of Minimal-Norm ReLU Classifiers
When a neural network is trained on a binary classification task, what function does it actually learn? And how does the answer depend on architectural choices like whether biases are regularized or whether a skip connection is present? These questions are not merely academic: they determine what implicit bias drives gradient-based optimization, what regularization actually penalizes, and what landscape the optimizer navigates.
Karolina Drabik, Ben Lewis, Antoni Puch, Etienne Boursier, Piotr Hofman, Matthias Englert, and Ranko Lazić resolve these questions in full generality for the canonical setting of univariate binary classification with two-layer ReLU networks. Their paper, submitted September 23, 2博士, provides complete geometric characterizations of the optimal classifiers in function space, shows that adding a free affine skip connection leaves the optimal functions unchanged while transforming the optimization landscape from one riddled with suboptimal stationary points to one where every KKT point is globally optimal, and establishes a fundamental sparsity distinction between minimal-norm interpolators and regularized-loss minimizers.
The Setting: Four Architectural Variants
The study considers two-layer ReLU networks with univariate inputs. The output of such a network takes the form f(x) = a₀x + b₀ + Σ aⱼσ(wⱼx + bⱼ), where σ is the ReLU activation, a₀ and b₀ define a skip connection, and the remaining parameters define m hidden neurons with output weights aⱼ, hidden weights wⱼ, and biases bⱼ.
The paper systematically explores four architectural variants, defined by two binary choices. First, whether hidden-layer biases are included in the parameter norm that is being minimized: the "unpenalized-bias" variant minimizes Σ(aⱼ² + wⱼ²), while the "penalized-bias" variant minimizes Σ(aⱼ² + wⱼ² + bⱼ²). Second, whether a free affine skip connection is present: the skip-absent variant uses f(x) = Σ aⱼσ(wⱼx + bⱼ), while the skip-present variant adds the a₀x + b₀ term. Both the skip parameters a₀ and b₀ are never penalized, regardless of the other choices.
The classification task is binary: given a dataset of sorted points (xᵢ, yᵢ) with labels yᵢ ∈ {±1}, the goal is to find a function f such that yᵢf(xᵢ) ≥ 1 for all training points, while minimizing the parameter norm. This is the minimal-norm interpolation problem, a natural regularization objective whose connection to generalization has been studied extensively since the foundational work on implicit bias in neural network training.
The Main Theorem: Three Geometric Characters
The central result, Theorem 1, provides complete geometric characterizations of the optimal classifiers under all four architectural variants, unified into a single statement with three parts.
Part 1 applies when biases are unpenalized (whether or not the skip connection is present). In this case, the minimizers in function space are exactly the continuous piecewise-affine (CPA) functions that satisfy two geometric conditions: switch hugging and convexity correctness. Switch hugging means the function passes through both data points at every label switch; convexity correctness means that at every kink within an intermediate same-label segment, the change in slope has the opposite sign to the label of that segment. Intuitively, the function "hugs" the data at transitions and bends away from the label in the interior of each flat region.
Part 2 applies when biases are penalized. Here the minimizer is unique in function space and satisfies an additional constraint: single turning. Every intermediate same-label segment contains exactly one kink, and that kink is uniquely determined by the adjacent switch points. With r label switches, the minimizer has exactly r−1 kinks, making it the sparsest possible interpolant of the dataset. The uniqueness and sparsity emerge from the strict triangle inequality applied to the cost of individual kinks.
Part 3 is the most striking result concerning the optimization landscape rather than the functions themselves. When the skip connection is present, every KKT point of the constrained minimization problem is a global minimizer, regardless of whether biases are penalized. Without the skip connection, this fails: there exist suboptimal KKT points. The paper constructs explicit counterexamples showing that the parameter-norm landscape, when projected onto kink positions, contains plateaus of suboptimal KKT points that disappear entirely upon adding the skip connection.
Why the Skip Connection Transforms the Landscape
The mechanism behind Part 3 is subtle but reveals something fundamental about the geometry of ReLU networks. The ReLU activation satisfies σ(z) − σ(−z) = z, meaning that reversing a neuron (negating its hidden weight and output weight) changes its contribution by an affine function. The skip connection can absorb this affine perturbation without changing the function's value on the data, and critically, without changing the relevant directional derivatives. This means that when a skip connection is present, any violation of the optimality conditions can be corrected by an infinitesimal perturbation that decreases the parameter norm without violating any training constraint.
Without the skip connection, such perturbations are unavailable because there is no affine term to absorb the reversal. The optimizer can get stuck at configurations that satisfy the KKT conditions but are not globally optimal: these are configurations where kinks of inappropriate convexity or outer kinks exist, and no local descent direction exists within the parameter space.
The practical implication is significant: training a two-layer ReLU network on classification data with a skip connection guarantees that gradient-based optimization, if it converges to any KKT point, will find a globally optimal solution. Without a skip connection, practitioners have no such guarantee, and suboptimal stationary points can and do trap the optimizer.
Regularized Logistic Loss: A Sparsity Distinction
The paper extends its analysis from the constrained interpolation problem to ℓ₂-regularized logistic-loss minimization. The central question is: what functions arise as minimizers of the regularized objective, and how do those functions relate to the minimal-norm interpolators?
For sufficiently weak regularization (λ below a mild dataset-dependent bound), the regularized-loss minimizers share the same function-space characterizations as the interpolator minimizers, with two important differences. First, the switch-hugging property is replaced by switch-optimality: the outputs at the label-switch inputs are uniquely determined by the dataset and the regularization strength, rather than being fixed at ±1. Second, when biases are unpenalized, the regularized-loss minimizers satisfy an interval-turning property: all kinks in each same-label segment must lie between the same pair of consecutive training inputs.
This interval-turning property creates a fundamental distinction. Minimal-norm interpolators when biases are unpenalized can have kinks anywhere within intermediate same-label segments. Regularized-loss minimizers cannot. This means that most minimal-norm interpolators cannot arise as limits of margin-normalized regularized-loss minimizers as λ → 0. In other words, the regularization path does not sweep through all the minimal-norm solutions; it selects a strict subset.
This finding has consequences for understanding implicit bias in practice. Many optimization algorithms, including gradient descent on overparameterized networks, are believed to converge to solutions that minimize some norm implicitly. If the implicit bias corresponds to the regularized-loss minimizer rather than the minimal-norm interpolator, then the function actually learned is more constrained than the full set of minimal-norm solutions would suggest. The paper's sparsity result shows that the regularized path enforces a kind of structural parsimony beyond what bias penalization alone achieves.
Global Optimality Under Regularization
The paper also establishes that the global-optimality guarantee from Part 3 extends to the regularized-loss setting. Every Clarke stationary point of the ℓ₂-regularized logistic loss with positive margin is a global minimizer when the skip connection is present, regardless of bias penalization. This result holds for all regularization strengths, not just sufficiently weak ones.
The proof technique parallels the constrained case: the skip connection provides descent directions that convert any stationary point violating global optimality into one with strictly lower objective value. The convexity of the regularized objective in function space, combined with the geometric characterization of the minimizers, ensures that no non-global stationary points can exist when the skip connection is present.
Technical Depth and Broader Context
The paper builds on a substantial body of prior work. The study of minimal-norm representers for two-layer ReLU networks traces back to the early work on the ℱ₁ norm and its relationship to generalization. Prior results established the existence and properties of minimal-norm interpolators for regression, but the classification case presented additional challenges: the margin constraints yᵢf(xᵢ) ≥ 1 create a non-smooth feasible set, and the interaction between the ReLU kinks and the label structure required entirely new geometric tools.
The skip-connection result addresses a gap in the theoretical understanding of modern architectures. While skip connections are ubiquitous in practice, from ResNets to transformers, their theoretical role in optimization landscapes has been underexplored. The paper provides one of the clearest demonstrations that a skip connection can fundamentally alter the optimization geometry, converting a problem with suboptimal stationary points into one where every stationary point is optimal.
The technical apparatus draws on convex analysis, Clarke subdifferentials, and the Mangasarian-Fromovitz constraint qualification. The proofs carefully navigate the non-smoothness introduced by the ReLU activation and the margin constraints, using the structure of univariate data to construct explicit descent directions and establish the KKT characterizations.
Limitations and Open Directions
The paper is explicit about its scope. The analysis is restricted to univariate data and two-layer ReLU networks. Extending the results to multivariate inputs, deeper architectures, or other activation functions would require fundamentally different geometric tools, since the correspondence between CPA functions and two-layer ReLU networks is specific to the univariate case.
Assumption 1, which requires that the first two segments have negative labels and the last two have positive labels, is a coordinate-dependent condition that avoids degenerate cases in the proofs. While all results apply regardless of how the dataset is sampled, the assumption constrains the statement rather than the generality of the underlying phenomena.
The regularization bound in the ℓ₂-regularized analysis depends on the dataset, and the paper does not provide a tight characterization of how this bound scales with dataset properties. Numerical experiments across varying dataset complexity and network width support the theoretical predictions, but the precise thresholds remain an area for further investigation.
An open direction suggested by the results is whether the sparsity distinction between interpolators and regularized-loss minimizers persists for richer function classes or in multivariate settings. If it does, it would imply that implicit regularization in deep networks fundamentally selects a narrower class of functions than the minimal-norm interpolators alone would suggest, with implications for understanding what neural networks actually learn.
Why This Matters
The paper provides what the authors describe as a complete geometric picture of minimal-norm classification by two-layer ReLU networks, resolving how the solutions depend on two architectural choices that are central to both theory and practice: bias penalization and skip connections.
The skip-connection result is perhaps the most practically relevant. It tells us that adding a free affine skip to a two-layer ReLU network does not change the set of optimal functions but removes all suboptimal stationary points from the optimization landscape. This is a rare and valuable combination: architectural modification that preserves the solution set while guaranteeing that every stationary point is a global optimum. For practitioners designing architectures, this provides a theoretical rationale for the empirical effectiveness of skip connections that goes beyond their known benefits for gradient flow and residual learning.
The sparsity result addresses a long-standing question about the relationship between minimal-norm interpolation and regularized-loss minimization. By showing that most minimal-norm interpolators cannot be reached through the regularization path, the paper clarifies that implicit bias in gradient-based training selects a more structured class of functions than the unconstrained minimal-norm solutions. This has implications for understanding generalization: the functions that gradient descent actually finds may be more constrained and more interpretable than the full minimal-norm class would suggest.
All proofs, further results, counterexamples, and detailed experimental validation appear in the extensive appendix, which spans over 100 pages and includes complete derivations, additional theoretical results, and experiments across a range of synthetic datasets and network widths.