Minimal-Norm Univariate Two-Layer ReLU Classification: Exact Solutions and Global Optimality with Skip Connections

• Norm minimization motivates the study, while a complete characterization of finite-sample minimum-norm classifiers—including bias and skip-connection effects—had remained open.Source: §1 · pp. 1–2
• The paper completely characterizes minimal-norm interpolators and regularized-loss minimizers in function space, including how their geometry depends on bias penalization.Source: §1 · p. 2
• With a skip connection, every KKT point of interpolator norm minimization and every positive-margin stationary point of regularized loss is globally minimizing; without it, this guarantee fails.Source: §1 · p. 3
• For unpenalized biases, regularized-loss minimizers have a sparsity-like geometry, so most minimal-norm interpolators are not limits of margin-normalized minimizers as λ tends to zero.Source: §1 · p. 3
• Experiments on synthetic datasets with varying overparameterization validate the predicted skip-connection landscape and sparsity results.Source: §1 · p. 3
• The 32r + 67 linear-region bound for penalized-bias KKT points reduces to r when a skip connection is added or minimizers are considered instead.Source: §1 · p. 3
• With penalized biases, minimal-norm interpolators are unique and optimally sparse in function space, with or without a skip connection.Source: §1 · p. 3
• The prior privacy attack's guarantee improves from at least one quarter of extracted points being training data to all extracted points, with every same-label segment represented, under the stated skip-connection or global-minimizer conditions.Source: §1 · p. 3

• The networks use univariate real inputs and two-layer ReLU units, with an optional affine skip connection whose parameters are never penalized.Source: §2 · pp. 3–4
• The represented functions are continuous piecewise affine with finitely many pieces; a kink is convex or concave according to the ordering of its incident slopes.Source: §2 · p. 3
• The setting considers four variants of interpolator norm minimization, and restricts attention to finite-width networks.Source: §2 · p. 3, Table 1 · p. 4

• Adding a free skip connection leaves the optimal functions unchanged but makes every KKT point globally optimal, across network widths.Source: §3 · pp. 4–5
• Without bias penalties, the minimizers are exactly the interpolating CPAs that hug every label switch and have convexity-correct kinks in intermediate same-label segments.Source: §3 · p. 4
• With bias penalties, the function-space minimizer is unique, has exactly one kink in each intermediate same-label segment, and is sparsest.Source: §3 · p. 4
• Without a skip connection, suboptimal KKT points can occur; the illustrated objective has plateaus at 11 and 7 despite a global minimum of 6.Source: §3 · p. 5, Figure 2 · p. 6
• For sufficiently small dataset-dependent λ, regularized-loss minimizers inherit the geometric characterizations, with switch hugging replaced by switch-optimal outputs at label switches.Source: §3 · p. 6
• With unpenalized biases, regularized-loss minimizers must also be interval turning: their kinks in each intermediate segment lie between the same consecutive training inputs.Source: §3 · p. 6
• With a skip connection, every positive-margin stationary point of the regularized logistic loss is globally minimizing, whether biases are penalized or not.Source: §3 · p. 6
• As λ tends to zero, margin-normalized stationary limits are KKT points; with a skip connection and unpenalized biases they are interval turning, so most minimal-norm interpolators are not such limits.Source: §3 · pp. 6–7

4 Experiments

• The experiments sample r0 class breaks, form datasets with n := (r0/2)2 inputs, and train width-m := ω · r0 networks using Adam toward Clarke stationary points.The global minimum is computed independently using the convex characterization in Theorem 6.Source: §4 · p. 7
• With a skip connection, training consistently reaches or closely approaches the global minimum; without one, best runs reach it, but mean and worst outcomes typically remain substantially above it.The comparison uses runs that reached positive margin.Source: Figure 3 · p. 8
• Figure 3 varies bias regularization by row and overparameterization factor by column, and compares networks with and without a skip connection.The plotted quantity is relative excess loss, L/L⋆−1.Source: Figure 3 · p. 8, §4 · p. 8

5 Discussion

• Prior representor-norm work characterizes function-space regularization, while this paper determines classifiers selected by finite constraints for both bias-penalization choices and with or without a skip connection.Savarese et al. [2019] related univariate cost to derivative total variation; Ongie et al. [2020] developed a multivariate analogue.Source: §5 · p. 8
• Unlike minimal-norm univariate regression results, this paper characterizes classification geometry, including how penalizing hidden biases affects sparsity and uniqueness.Hanin [2021] studied regression curvature extrapolation; Debarre et al. [2022] studied sparsest piecewise-linear regressors.Source: §5 · p. 8
• The fixed-dataset classification results allow margin-normalized small-regularization solutions to select only a strict subset of minimal-norm interpolators, unlike the cited asymptotic multivariate connection.The asymptotic connection is described by Park, Pelakh, and Wojtowytsch [2023].Source: §5 · p. 9
• For univariate hinge-loss classification, Ergen and Pilanci [2021] show an optimum can be chosen from data-aligned extreme-point features; this paper instead characterizes all optimal functions, including kinks away from training inputs.The paper also treats penalized biases, skip connections, nonconvex stationary points, and regularized logistic loss.Source: §5 · p. 9
• For arbitrary finite datasets satisfying a mild assumption, the paper jointly characterizes optimal functions, when sparsity and uniqueness occur, and when skip connections make first-order stationary points globally optimal.The results also characterize the regularized-to-constrained limit.Source: §5 · p. 9
• For finite networks, a free affine skip leaves globally optimal functions unchanged while making every constrained KKT point and every positive-margin regularized stationary point globally optimal.This is an exact landscape result, unlike cited deep-model analyses focused on conditioning, spectral behavior, or trainability.Source: §5 · p. 9

6 Conclusion

• The univariate setting permits complete characterization of optimal classifiers, bias-dependent sparsity and uniqueness, and skip-connection elimination of suboptimal KKT points without changing optimal functions.The conclusions require only a mild dataset assumption.Source: §6 · p. 9
• Extending the geometric and landscape results to multivariate inputs and deeper networks, and characterizing no-skip stationary points more fully, remain next steps.The paper identifies label-switch geometry, bias-induced spatial weighting, and skip-enabled descent directions as mechanisms whose higher-dimensional counterparts remain to be understood.Source: §6 · p. 10
• A proposed empirical direction is testing whether homogeneous, bias-penalized logistic-loss gradient flow selects the global solution or a suboptimal no-skip KKT point.The experiment is challenging because directional convergence is asymptotic and can be extremely slow.Source: §6 · p. 10

AI use statement

• The authors report using generative AI to polish writing, find related work, and help create and edit experiment and landscape code.They state they reviewed and tested the final content, including AI-assisted code.Source: AI use statement · p. 10

Reproducibility statement

• The paper provides experiment and landscape code with run instructions, requiring no specialized software or hardware and relatively little compute.The code is available at the URL specified in the paper.Source: Reproducibility statement · p. 10

A Overview diagram of proof dependencies

• Each box names a result in bold and describes its role in the proof.Source: Figure 4 · p. 15
• The three dotted panels distinguish tools used for both Theorem 1 and Theorem 6 from tools used for only one.Source: Figure 4 · p. 15
• Arrows show proof dependencies, dashed boxes mark prior-work results, and shaded boxes identify the main theorems.Source: Figure 4 · p. 15

Clarke subdifferential and directional derivative

• The Clarke subdifferential collects subgradients of a locally Lipschitz function, reduces to the gradient when the function is continuously differentiable, and handles ReLU’s nondifferentiability at zero.The Clarke directional derivative agrees with the ordinary directional derivative in the continuously differentiable case.Source: B Background on the Clarke… · p. 16

KKT points

• A KKT point satisfies stationarity through objective and active-constraint subgradients, with nonnegative multipliers and complementary slackness.The KKT definition is stated for locally Lipschitz objective and constraint functions.Source: B Background on the Clarke… · p. 16
• A feasible point is not KKT if some direction decreases the objective while making every tight constraint’s directional derivative nonpositive.This is the sufficient condition given in Proposition 1.Source: B Background on the Clarke… · p. 16

MFCQ

• MFCQ requires a direction that strictly decreases every tight constraint; a local minimizer satisfying MFCQ is KKT, and suitable approximate KKT limits are KKT.The limit result requires convergence of the points and vanishing approximation parameters, as well as MFCQ at the limit.Source: B Background on the Clarke… · p. 17

Known representor-norm results

• The section collates known results on representor-norm minimization across four problem variants as a basis for the paper’s analysis.The variants distinguish whether biases are penalized and whether a free skip connection is present.Source: C Background on minimal-norm… · p. 18

Expressive power

• A univariate function is representable by a two-layer ReLU network if and only if it is continuous piecewise affine, and adding a skip connection does not change the representable class.An affine term can be expressed as the difference of two ReLUs.Source: C Background on minimal-norm… · p. 18

Minimal representor norms

• Theorem 4 characterizes minimal representor norms for a CPA using its kink locations and slopes, and states attainment for specified variants.The text also states that allowing a free output bias leaves the minimum unchanged and attained.Source: C Background on minimal-norm… · pp. 18–19

Switch-count condition

• At least three label switches let the proof eliminate the free affine skip connection for positive-margin classifiers and transfer function-space characterizations to the no-skip problems.The weaker condition of at least two switches suffices for specified compactness arguments and finite-dimensional problems.Source: D Role of the dataset assumption · p. 20

Sign condition

• The sign condition is used only with penalized biases to handle outer-kink cases; with unpenalized biases, the stated conclusions require only at least three switches.For unpenalized biases, the relevant perturbations do not depend on kink location.Source: D Role of the dataset assumption · p. 20
• Without the sign condition, the penalized-bias proofs retain interior results, including exclusion of multiple kinks in intermediate same-label segments, but do not establish the full stated geometric characterizations.The limitation concerns results whose proofs use the sign condition to exclude outer geometric irregularities.Source: D Role of the dataset assumption · p. 20

Coordinate dependence

• For penalized biases, translating the inputs changes kink locations and representor costs, so translation cannot enforce the sign condition without changing the optimization problem.In the unpenalized-bias setting, the representor cost depends only on slope changes and the corresponding conclusions are translation invariant.Source: D Role of the dataset assumption · p. 20

E Proofs for minimal-norm interpolators

• Without penalized biases, the minimizers are exactly CPAs that pass through each label switch and have correctly oriented kinks within intermediate same-label segments.Each kink lies in an intermediate same-label segment, with convexity opposite to that segment’s label.Source: E Proofs for minimal-norm interpolators · p. 21
• With penalized biases, the function-space minimizer is unique, has exactly one kink in each intermediate same-label segment, and is a sparsest interpolant with r −1 kinks.Source: E Proofs for minimal-norm interpolators · p. 21
• With skip connections, every KKT point of the constrained problems is globally optimal across all network widths for which KKT points exist.Source: E Proofs for minimal-norm interpolators · p. 21
• The function-space classifier reveals training inputs incident to label switches: the extracted set consists exactly of the specified segment endpoints.The number of classifier switches across that set equals the dataset’s r label switches.Source: E Proofs for minimal-norm interpolators · p. 21
• For positive-margin CPAs with at least three label switches, adding a skip connection does not lower representational cost, and the no-skip minimum is attained.The proof establishes R(g) = R1(g) and Rb(g) = Rb1(g).Source: E Proofs for minimal-norm interpolators · pp. 21–23
• Both skip-connection interpolator problems attain their minima at every feasible fixed network width.For P1, the proof uses a compact minimizing sequence; the analogous argument establishes attainment for Pb1.Source: E Proofs for minimal-norm interpolators · pp. 24–25
• With a free affine skip connection, reversing a hidden neuron’s orientation changes its ReLU contribution by an absorbable affine function and preserves Clarke directional derivatives.The preserved derivatives cover network outputs, their negatives, and both regularizers considered.Source: E Proofs for minimal-norm interpolators · p. 25
• When perturbations move at most one neuron kink at an input, the Clarke directional derivative there reduces to the maximum of the two one-sided limits, provided zero neurons and coincident kinks satisfy the stated restrictions.This lets the subsequent proofs work with the affine expressions on either side of a kink.Source: E Proofs for minimal-norm interpolators · pp. 26–27
• A positive-margin CPA that is not convexity correct must have opposite-convexity neighboring kinks over a same-label interval or a boundary kink on a constant-label tail.These are the three local irregularities used to identify failures of convexity correctness.Source: E Proofs for minimal-norm interpolators · p. 28
• For datasets with at least two label switches, an interpolating convexity-correct CPA that fails switch hugging has a neighboring-kink or boundary-tail interval where no training output equals either label.The boundary cases place the first or last kink beyond the corresponding outer label-switch region.Source: E Proofs for minimal-norm interpolators · p. 30
• A convexity-correct CPA that is not single turning has either two convex neighboring kinks across an all-negative-label interval or two concave ones across an all-positive-label interval.Source: E Proofs for minimal-norm interpolators · p. 31
• An imbalanced neuron admits a direction that decreases the squared parameter norm while keeping every training point’s negative-margin Clarke derivative nonpositive.The proof then assumes balanced neurons when handling the geometric irregularities.Source: E Proofs for minimal-norm interpolators · p. 31
• Under Assumption 1, each listed convexity or single-turning irregularity admits a direction decreasing parameter cost while making every training point’s negative-margin Clarke derivative nonpositive.The proof first uses balanced neurons and an orientation reparameterization to construct the direction.Source: E Proofs for minimal-norm interpolators · pp. 28, 31, 32, 33

Lemma 12

• For interpolators failing switch hugging under penalized biases, Lemma 12 supplies a direction that decreases parameter norm without increasing loss on correctly classified samples.Source: E Proofs for minimal-norm interpolators · pp. 31, 33

Lemmas 13–15

• The cited lemmas construct parameter directions when a neuron has |a_j| ≠ |w_j|, or when two neurons have nonzero a and w, equal ratios −b_j/w_j = −b_j′/w_j′, and opposite signs of a.Source: E Proofs for minimal-norm interpolators · p. 33

Lemma 16

• Every feasible point of (P), (P1), (Pb), and (Pb1) satisfies MFCQ.The proof uses the increase in margin under parameter scaling, accounting for the skip connection’s failure of homogeneity.Source: E Proofs for minimal-norm interpolators · pp. 24, 34

Proof of Theorem 1

• The canonical switch-hugging, convexity-correct, single-turning interpolator is the unique function-space minimizer, with exactly r −1 kinks.Its kink in each intermediate same-label segment is the intersection of the adjacent affine pieces.Source: E Proofs for minimal-norm interpolators · p. 34

F Counterexamples without the skip connection

• Without a skip connection, width-4 and width-6 networks provide suboptimal KKT points for the unpenalized- and penalized-bias problems, respectively.The unpenalized-bias interpolant is not convexity correct; the penalized-bias interpolant is neither single turning nor sparsest.Source: F Counterexamples without the skip… · p. 36
• Adding a skip connection removes the suboptimal plateaus from the depicted unpenalized-bias landscape, leaving a plateau of minimizers with cost 6.For the small-regularization logistic-loss landscape, the appendix reports the same qualitative transformation when a skip connection is added.Source: F Counterexamples without the skip… · pp. 37, 41, Figure 11 · p. 41
• For the unpenalized-bias example, suboptimal KKT plateaus have costs 11 and 7, while the function-space minimizer costs 6.The cost-11 plateau includes freely varying outer kinks; the figure also depicts a cost-7 plateau and the cost-6 minimizer.Source: Figure 8 · p. 37, Figure 9 · p. 38, F Counterexamples without the skip… · p. 39
• In the penalized-bias example, two intermediate kinks cost more than one optimal kink, leaving six kinks instead of the minimum five.The two constructed kinks cost 2 · 2^5, exceeding the cost of 4 for one kink at 0 with slope change 4.Source: F Counterexamples without the skip… · p. 40
• The constructions persist under sufficiently small independent perturbations of input locations, and the identified suboptimal points include strict local minimizers.The symmetric datasets simplify the constructions; they are not required for the perturbation robustness.Source: F Counterexamples without the skip… · p. 40

Optimization landscape evidence

• Figure 11 provides numerical evidence of an analogous qualitative optimization-landscape phenomenon for small-λ regularized loss.Source: G Proofs for minimizing ℓ2-regularized… · p. 41

Auxiliary stationarity result

• A direction with nonpositive directional derivatives for the regularizer and every training-point negative margin, with at least one strict inequality, rules out Clarke stationarity with a skip connection.This sufficient condition applies for any λ > 0, with biases optionally penalized.Source: G Proofs for minimizing ℓ2-regularized… · p. 42

Minimizers of the regularized losses

• For sufficiently small dataset-dependent λ, the switch-incident margin problems have strictly convex objectives, convex feasible sets, and unique minimizers.These properties hold for both unpenalized- and penalized-bias variants.Source: G Proofs for minimizing ℓ2-regularized… · pp. 42–43

Theorem 6

• For sufficiently small λ, unpenalized biases yield minimizers that are switch optimal, convexity correct, and interval turning; penalized biases yield a unique minimizer with single turning and r − 1 kinks.For both bias choices, all variants with and without a free affine skip connection share the stated function-space minimizers.Source: G Proofs for minimizing ℓ2-regularized… · p. 45
• With a free affine skip connection, every positive-margin Clarke stationary point is a global minimizer across all network widths, for either bias-regularization choice.This conclusion applies to widths for which such points exist.Source: G Proofs for minimizing ℓ2-regularized… · p. 45

Attainment of minima

• For any λ > 0, the skip-connection regularized-loss problems attain their minima at every fixed network width when the dataset has at least two label switches.Source: G Proofs for minimizing ℓ2-regularized… · p. 45

G Proofs for minimizing ℓ2-regularized logistic loss

• For the stated small-λ bounds, a positive-margin, convexity-correct network that is interval turning (or single turning) but not switch optimal cannot be Clarke stationary.The proof constructs simultaneous perturbations across intermediate same-label segments, and of the skip connection, that move margins toward the unique switch-optimal solution and yield a negative Clarke derivative.Source: G Proofs for minimizing ℓ2-regularized… · pp. 47, 50
• Positive-margin Clarke-stationary networks are switch optimal and, under the theorem’s conditions, minimize the corresponding regularized loss.The unpenalized-bias case requires convexity correctness and interval turning; the penalized-bias case requires convexity correctness and single turning.Source: G Proofs for minimizing ℓ2-regularized… · pp. 51–52
• The single-turning minimizer is unique in function space because switch optimality and convexity correctness uniquely determine all crossing pieces.The proof adapts the positive-margin argument for the earlier uniqueness result.Source: G Proofs for minimizing ℓ2-regularized… · p. 51

Theorem 7

• For all four logistic-loss variants, limits of margin-normalized approximate Clarke stationary points are KKT points of the corresponding interpolator-norm problem under sufficiently fast-decaying approximation tightness.The regularization strength tends to zero.Source: H Proofs for limits of normalized… · p. 53
• With unpenalized biases and a skip connection, these limits must be interval turning, so most KKT points cannot be obtained this way.The paper relates this restriction to its characterization of KKT points in Theorem 1.Source: H Proofs for limits of normalized… · pp. 53, 55
• The result concerns limits as regularization vanishes and requires approximation tightness to decrease sufficiently fast.Source: H Proofs for limits of normalized… · p. 53

Outcomes

• With bias regularization, training typically reaches or approaches the minimal kink count, especially with a skip connection; without it, networks typically have more kinks.The plotted quantity is the relative excess kink count over the minimum for a positive-margin classifier.Source: Figure 14 · p. 58
• Positive-margin failures are significant only at overparameterization factor 1 and, when nonzero, are always higher without a skip connection.Failure fractions aggregate 300 runs per setting.Source: Figure 15 · p. 59

Training

• Training uses small regularization, set to a constant times 1/(mς^2), so the logistic-loss term dominates before positive margin is reached.The selected strength also satisfies the stated upper bounds in Lemma 18 and Theorem 6.Source: I Further details for and outcomes… · p. 59

Experimental setup

• The study varies five class-break counts and five overparameterization factors across bias-regularization and skip-connection settings, repeating each of 100 combinations for 60 seeds.Only positive-margin runs contribute to Figures 13 and 14; failure fractions are reported separately in Figure 15.Source: I Further details for and outcomes… · pp. 59–60