acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

We study minimal-norm interpolation and -regularized logistic-loss minimization for binary classification by univariate two-layer ReLU networks. We give complete geometric characterizations of the optimal classifiers in function space, resolving how the solutions depend on whether hidden-layer biases are included in the parameter norm. When biases are unpenalized, the minimal-norm interpolators are exactly the continuous piecewise-affine functions that hug every label switch and have kinks of the appropriate convexity. When biases are penalized, the minimizer is unique in function space, has exactly one kink in each intermediate same-label segment, and is therefore a sparsest positive-margin classifier. We further show that adding a free affine skip connection leaves these function-space solutions unchanged but fundamentally improves the parameter-space landscape: every KKT point of the constrained problem becomes globally optimal, whereas suboptimal KKT points can occur without the skip connection. We establish analogous global-optimality and geometric results for sufficiently weak -regularization of the logistic loss. In the unpenalized-bias case, we identify an additional sparsity-like restriction, implying that most minimal-norm interpolators cannot arise as small-regularization limits of margin-normalized logistic-loss minimizers. Numerical experiments across varying dataset complexity and network width support the predicted landscape and sparsity phenomena.

Primary area:
learning theory
Keywords:
minimal-norm interpolation learning, univariate classification, two-layer ReLU networks, optimization landscapes

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_4UTDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies optimality in two-layer ReLU networks for univariate data, focusing on minimum-norm binary classification and l2-regularized logistic-loss minimization. In function space, the authors give necessary and sufficient geometric conditions that characterize all minimum-norm classifier functions. In parameter space, they prove that every KKT point is globally optimal when a free affine skip connection is present, under the stated assumptions.

The paper also examines the effects of penalizing hidden-layer biases and including a free affine skip connection. The skip connection leaves the globally optimal functions unchanged while eliminating suboptimal KKT points.

Overall, the paper presents many interesting results that help us understand the optimality of shallow neural networks, but its practical applicability is limited by the univariate setting. The empirical evaluation is restricted to synthetic univariate datasets with at most 36 training samples and networks with at most 60 hidden neurons. Although these experiments illustrate the theoretical results within their stated assumptions, they provide little evidence that the identified mechanisms remain informative in higher-dimensional or larger-scale settings.

Critical strengths
  1. The paper is technically solid, and its presentation and organization are clear.
  2. The experiments are systematic within the theoretical setting. They vary skip connections, bias regularization, network width, and dataset complexity across multiple random seeds. Comparisons against a computed global optimum, together with reported failure rates, provide useful evidence about optimization behavior.
  3. The paper makes a coherent and important theoretical contribution. It connects optimal-function geometry, sparsity, and stationary-point properties. Explicit counterexamples help establish why the architectural distinctions matter.
Critical weaknesses

Scope of claims

The formal statements qualify the results appropriately: Theorem 1 assumes Assumption 1, while Theorem 6 additionally requires λ\lambda to be sufficiently small and restricts its stationarity claim to positive-margin Clarke stationary points. However, the abstract and conclusion present the skip-connection result more broadly, stating that every KKT point or stationary point is globally optimal without consistently repeating these conditions. This wording may be read as an unconditional guarantee about the optimization landscape or training behavior. Please state the assumptions and scope alongside these summary claims, and clarify that the results do not guarantee that a training algorithm will reach such a point.

Assumptions

The theoretical results are established only for univariate inputs, and the experiments do not investigate whether the identified mechanisms remain informative beyond this setting. The paper could better explain the scientific value of its one-dimensional setting. In particular, it remains unclear which findings reveal mechanisms relevant to more general neural networks and which are consequences of the ordering structure specific to one dimension.

Experimental gaps

  • Long training does not establish near-stationarity.

Appendix I reports 2×1072\times10^7 full-batch Adam updates per experiment, but provides no end-of-training convergence or stationarity diagnostics. For runs with nonzero excess loss, particularly those without a skip connection, it is therefore difficult to distinguish proximity to a suboptimal stationary point from incomplete optimization. Appropriate diagnostics would strengthen the empirical connection to the landscape results. Experiments that compare the results with optimal solutions computed using an exact algorithm for univariate data would make the findings clearer.

  • Clarify the role of width in the global-optimality results.

Theorem 1(iii) states that any KKT point, at any width for which one exists, is globally optimal over all widths. The regularized-loss analogue, Corollary 1(ii), says that any positive-margin Clarke stationary point with a skip connection is globally optimal, under the stated assumptions. These are conditional guarantees: they do not ensure that such a point exists at every width or that Adam reaches one. Since each run fixes m=ωr0m=\omega r_0 (while the experiments sweep over ω\omega), what role is width intended to play?

Related works

The related-work discussion could more clearly distinguish the paper’s structural and landscape guarantees from existing exact-training results for shallow ReLU networks, such as [1], [2], and [3]. These works address finding global optima or the computational complexity of training, whereas the present paper characterizes optimal functions under explicit regularization and architectural constraints. A brief comparison of objectives, dimensionality, width assumptions, and regularization would help readers understand the relationship between these contributions.

[1] Arora, et al. “Understanding Deep Neural Networks with Rectified Linear Units.” International Conference on Learning Representations (ICLR), 2018.

[2] Froese, et al. “The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality.” Journal of Artificial Intelligence Research, 74: 1775–1790, 2022.

[3] He, et al. “Deep-ICE: The First Globally Optimal Algorithm for Empirical Risk Minimization of Two-Layer Maxout and ReLU Networks.” International Conference on Learning Representations (ICLR), 2026

Questions for authors

Appendix D explains where Assumption 1 enters the proofs. Which conclusions are known to fail when its conditions are removed, and which are conjectured to remain valid?

Could the authors provide a targeted higher-dimensional experiment to assess whether the optimization benefit of the free affine skip connection persists beyond the univariate setting? I am particularly interested in whether it reduces optimization gaps relative to a reliable global-optimum benchmark.

Can the authors explain how their results relate to [1-3]? In particular, could the results potentially be generalized to the 0-1 loss considered in [3]?

3 comments

Scope of the claims. Thank you for pointing out this ambiguity. We have revised the abstract, the summary of contributions, the discussion and the conclusion, so that the dataset assumption is stated alongside the skip-connection claims, and so that the regularized-loss result is stated with its requirements of sufficiently small regularization and a positive-margin Clarke stationary point. We also state explicitly that these results establish the global optimality of such points, without guaranteeing that a training algorithm reaches them.

Why the univariate setting. Beyond being the basic case of low dimensionality, the univariate setting serves both as a testbed and as a stepping stone to higher dimensions. For example, Joshi et al. (2024) use univariate minimum-norm networks to show that overfitting can be tempered or catastrophic depending on how the risk is measured; Ongie et al. (2020) extend the univariate representation-cost theory of Savarese et al. (2019) to multivariate functions; and Zeno et al. (2023) proceed from a univariate characterization of minimum-norm denoisers to multivariate characterizations under specified geometric assumptions. These precedents support the usefulness of univariate analysis without implying that its conclusions transfer unchanged. In our case, one dimension is what currently permits an exact and simultaneous treatment of function-space selection, the parameter-space landscape, and the regularized-to-constrained limit.

What depends on one dimension, and what does not. Our complete descriptions of the optimal functions (switch hugging, convexity correctness, single turning, and interval turning) are phrased in terms of the order of the inputs, and our proofs of global optimality use that order. Three ingredients, however, do not depend on the dimension. First, a free affine term absorbs the reversal of a neuron's orientation: in every dimension, σ(⟨w,x⟩+b)−σ(−⟨w,x⟩−b)=⟨w,x⟩+b\sigma(\langle w,x\rangle+b)-\sigma(-\langle w,x\rangle-b)=\langle w,x\rangle+b, so reversing a neuron changes the network function only by an affine term and leaves either norm penalty unchanged. In our proofs, this lets perturbations act on a chosen side of a kink; in Appendix J, it is exactly what separates the minimal widths with and without the skip. Second, penalizing biases weights the distance of each activation hyperplane from the origin: for a normalized neuron α σ(⟨u,x⟩−h)\alpha\,\sigma(\langle u,x\rangle-h) with ∥u∥=1\lVert u\rVert=1, balancing by positive homogeneity gives the cost ∣α∣\lvert\alpha\rvert when biases are unpenalized and ∣α∣1+h2\lvert\alpha\rvert\sqrt{1+h^2} when they are penalized. In one dimension, ∣h∣\lvert h\rvert is the distance of the kink from the origin, and this weight is what makes the penalized-bias optimum single turning. Third, the proof of Lemma 22 shows how perturbations of many neurons and of the skip can be coordinated to improve training margins while controlling the regularizer; its construction uses the order of the inputs, but its principle does not.

Near-stationarity diagnostics and the exact benchmark. Thank you for this suggestion. The last two figures in Appendix I are new diagnostics, both evaluated for each run at the network attaining the smallest regularized loss. Figure 16 plots the relative excess L/L⋆−1L/L^\star-1 against the gradient norm of the full objective divided by the run's regularization strength, ∥∇L∥2/λ\lVert\nabla L\rVert_2/\lambda, and Figure 17 plots it against the relative improvement BT/2/BT−1B_{T/2}/B_T-1 of the best loss over the second half of training, where T=2⋅107T=2\cdot 10^7. For most of the significantly suboptimal runs, almost all of which are without the skip, both diagnostics lie in the same range as for the runs that reach the optimum; in particular, their best loss barely improved during the last 10710^7 iterations. This suggests that these runs are near suboptimal stationary points rather than incompletely optimized, although such diagnostics are not certificates of stationarity. Figures 18 and 19 show the same diagnostics for the parity experiments. We have also doubled the number of seeds per configuration, from 60 to 120. Regarding comparison with exact optima, the benchmark L⋆L^\star in all our excess-loss plots is such an optimum: it is computed independently of training, by solving the strictly convex finite-dimensional problem to which Theorem 6 reduces regularized-loss minimization for univariate data.

Role of width. The relevant existence results were dispersed across the proofs, and we have now collected them in a paragraph on network width at the end of Section 3. Under Assumption 1 and with a free affine skip, interpolation is feasible exactly when m≥r−1m\geq r-1, and every such width admits a global constrained minimizer, which is a KKT point by MFCQ. Under the bound on λ\lambda in Theorem 6, these widths also admit a positive-margin global minimizer of the regularized loss. Without the skip, m≥r+1m\geq r+1 suffices for both conclusions, by the construction in the proof of Lemma 1. All tested widths permit interpolation, and we varied the width to examine how it changes the effects of the skip connection and of bias penalization on both optimization and sparsity. At the smallest width, training sometimes failed to reach a positive margin, more often without the skip (Figure 15); the existence results do not guarantee that Adam reaches the relevant stationary points. Finally, the benchmark, a minimum over all widths, is attainable at every tested width except possibly without the skip at ω=1\omega=1, where some datasets may need more neurons; there, an observed excess may reflect the width restriction as well as incomplete optimization, and we do not separate the two.

Relation to exact-training results. Thank you for pointing us to these works; we have added to the discussion a comparison of objectives, dimensionality, width and regularization. Arora et al. [1] give an exact training algorithm for convex losses, Froese et al. [2] establish dimension-dependent hardness and extend such algorithms to a broader class of losses, and He et al. [3] treat the 0–1 loss for ReLU and maxout networks under a general-position assumption. These works allow multivariate inputs and concern unregularized risk at a prescribed width. Our univariate results instead characterize all optimal functions for unit-margin norm minimization and for norm-regularized logistic loss and, under the stated assumptions, establish the global optimality over all widths of KKT points and of positive-margin Clarke stationary points, respectively, with a free affine skip.

Assumption 1. We believe that Assumption 1 can be removed entirely, but at the cost of cluttering most definitions and results with careful treatments of special cases in which the number of label switches is very small or most of the data lie on one side of the origin; we opted not to do this because it would obscure the main contributions while adding relatively little. The two conditions in the assumption play different roles (Appendix D). The condition r≥3r\geq 3 is used for the equality of the minima with and without the skip, and this equality can indeed fail without it: with a single label switch, the skip alone interpolates, so the minimum with it is zero, whereas without it the minimum is positive. The sign condition is used only when biases are penalized, so, given r≥3r\geq 3, all our unpenalized-bias conclusions hold without it. With penalized biases and without the sign condition, the interior arguments remain valid, including the exclusion of multiple kinks in an intermediate segment, but we believe that counterexamples can be constructed showing that convexity correctness and switch hugging would need revisions around the first and last same-label segments.

A preliminary multivariate study: parity classification (new Appendix J). We have added Appendix J, a preliminary study of parity classification on the hypercube {−1,1}d\lbrace -1,1\rbrace^d for both choices of bias penalization; its two theorems are given with proof sketches. For every d≥2d\geq 2, Theorem 8 gives the exact global minimum of the regularized logistic loss over all widths: it is the same with and without a free affine skip connection, and so are the optimal predictions on the cube. For d=3,4,5d=3,4,5, Theorem 9 determines the least widths attaining this minimum (2, 4 and 16 with the skip, against 4, 8 and 18 without), so both architectures can attain it at every width in our experiments. Figures 18 and 19 compare the two architectures against this exact benchmark, using 50 pairs of runs with identical initial ReLU parameters in each of the six settings (d=3,4,5d=3,4,5, with and without bias penalization). All 300 runs with the skip reached positive margins, against 279 of the 300 without it. Among the runs with positive margins, the skip lowers the mean relative excess in all six settings and, apart from occasional outliers, eliminates significantly suboptimal outcomes. We conjecture that in this setting the skip removes certain classes of suboptimal positive-margin Clarke stationary points, possibly not all; determining which, and with what consequences for gradient-based training, is a promising direction for future work.

Generalization to the 0–1 loss. Extending our characterizations to the 0–1 loss would first require specifying how functions with equal classification error are selected and how their scale is fixed; unit-margin constraints together with norm minimization recover our constrained problem. The stationarity arguments do not extend directly either: the 0–1 empirical risk is locally constant whenever all training outputs are nonzero, even if some inputs are misclassified, so stationarity alone does not identify a global optimum. Moreover, every positive-margin classifier already minimizes the pure 0–1 risk, which therefore does not select our minimum-norm functions. We have added this distinction to the discussion.

Reviewer_qtE4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper is about studying minimum norm solutions for classification problems over univariate and shallow ReLU networks. The role of regularizing the biases and the role of skip connections is studied as well and the extent to which this affects the optimizers is identified.

Critical strengths

A clear strength is that various setups, bias penalization, and skip connections are studied, and the effects of these are clearly identified. This adds to our understanding of the role of these architecture/algorithm choices.

I also find the paper to be relatively well written and accessible. All statements and mathematical derivations appear to be correct.

Critical weaknesses
  1. I feel like the scope is too restricted to be meaningful. The problem studied are univariate shallow networks. This facilitates a lot of arguments, for example, it allows us to order the samples in a natural way, and have simple formulas for interpolators. The problem is that it is well known, that for input dimension at least two ReLU shallow approximation is entirely different than for the univariate case. A simple example is the representation of a nonzero compactly supported function, which is not possible with shallow networks in 2D, but trivial in 1D. This means that approximation in more dimensions becomes much more non-local. The arguments in this work are typically using local approximations, so I expect them to not be transferable. The authors present multivariate and deeper networks as a topic of future work, but I think this is not enough.

  2. Most results seem to not be that deep. In 1d with shallow networks it is clear that, for example, an unneccessary label change, requires alternating slopes, which can be removed without increasing the overall total variation. It is already well known how ReLU coefficient sizes relate to total variation. Naturally, the no kink condition is explained similarly. If multiple biases lie in a certain same class region, they can be merged to the smallest bias. Simple computations show how to do this without increasing the regularizers. I agree that this is interesting, but it is not a deep insight. As a result, there is absolutely no justification for a 60 page document.

Questions for authors
  1. Which of the presented mechanisms are expected to survive in higher dimensions? How could this be addressed?
  2. Is there a way to streamline the document to bring its length and the technical depth to an appropriate balance.
4 comments

Non-locality beyond one dimension. We agree that the order of the inputs substantially facilitates our analysis, and that, since shallow ReLU networks cannot represent nonzero compactly supported functions in two or more dimensions, multivariate results will probably require more global arguments. Locality in input space is, however, only a convenient means in our arguments: what they require is control of how a perturbation changes the outputs at the finitely many training inputs. Moreover, one of the most involved constructions in the present work is already non-local. In the proof of Lemma 22, neurons with kinks in all the intermediate same-label segments are perturbed together with the affine skip, so that the induced change of the margins at all label switches points towards the minimizer of a coupled convex problem. Its implementation uses the one-dimensional order, but we see it as an example of a technique that may extend to multivariate settings. The analysis of parity in the new Appendix J is likewise global: it rests on a bound on the correlation of any single ReLU neuron with parity over the whole cube.

A preliminary multivariate study: parity classification (new Appendix J). We have added Appendix J, a preliminary study of parity classification on the hypercube {−1,1}d\lbrace -1,1\rbrace^d for both choices of bias penalization; its two theorems are given with proof sketches. For every d≥2d\geq 2, Theorem 8 gives the exact global minimum of the regularized logistic loss over all widths: it is the same with and without a free affine skip connection, and so are the optimal predictions on the cube. For d=3,4,5d=3,4,5, Theorem 9 determines the least widths attaining this minimum (2, 4 and 16 with the skip, against 4, 8 and 18 without), so both architectures can attain it at every width in our experiments. Figures 18 and 19 compare the two architectures against this exact benchmark, using 50 pairs of runs with identical initial ReLU parameters in each of the six settings (d=3,4,5d=3,4,5, with and without bias penalization). All 300 runs with the skip reached positive margins, against 279 of the 300 without it. Among the runs with positive margins, the skip lowers the mean relative excess in all six settings and, apart from occasional outliers, eliminates significantly suboptimal outcomes. We conjecture that in this setting the skip removes certain classes of suboptimal positive-margin Clarke stationary points, possibly not all; determining which, and with what consequences for gradient-based training, is a promising direction for future work.

Depth of the results. We have aimed to make the proofs as simple and clear as possible, and Figures 6 (left), 7 (left) and 6 (right) illustrate precisely the three perturbation ideas you describe; they build on the known relation between the parameter norm and the total variation of the derivative (Theorem 4). These local ideas yield necessary conditions, but the complete picture rests on further ingredients. The equality of the minimal representation costs with and without the skip requires the construction in Lemma 1. Showing that every KKT point with the skip is globally optimal over all widths requires nonsmooth KKT and MFCQ arguments whose subtleties need particular care. The regularized-loss results (Theorems 6 and 7, from which Corollary 1 follows) require the global perturbation of Lemma 22 described above. Finally, constructing the counterexamples in Appendix F, which show that suboptimal KKT points do occur without the skip, required a deep understanding of the limits of the perturbations that the skip affords. We hope that these distinctions help explain both the contribution and the amount of proof material needed to establish it.

What depends on one dimension, and what does not. Our complete descriptions of the optimal functions (switch hugging, convexity correctness, single turning, and interval turning) are phrased in terms of the order of the inputs, and our proofs of global optimality use that order. Three ingredients, however, do not depend on the dimension. First, a free affine term absorbs the reversal of a neuron's orientation: in every dimension, σ(⟨w,x⟩+b)−σ(−⟨w,x⟩−b)=⟨w,x⟩+b\sigma(\langle w,x\rangle+b)-\sigma(-\langle w,x\rangle-b)=\langle w,x\rangle+b, so reversing a neuron changes the network function only by an affine term and leaves either norm penalty unchanged. In our proofs, this lets perturbations act on a chosen side of a kink; in Appendix J, it is exactly what separates the minimal widths with and without the skip. Second, penalizing biases weights the distance of each activation hyperplane from the origin: for a normalized neuron α σ(⟨u,x⟩−h)\alpha\,\sigma(\langle u,x\rangle-h) with ∥u∥=1\lVert u\rVert=1, balancing by positive homogeneity gives the cost ∣α∣\lvert\alpha\rvert when biases are unpenalized and ∣α∣1+h2\lvert\alpha\rvert\sqrt{1+h^2} when they are penalized. In one dimension, ∣h∣\lvert h\rvert is the distance of the kink from the origin, and this weight is what makes the penalized-bias optimum single turning. Third, the proof of Lemma 22 shows how perturbations of many neurons and of the skip can be coordinated to improve training margins while controlling the regularizer; its construction uses the order of the inputs, but its principle does not.

Length of the paper. We also value succinctness, and we reuse arguments across the four settings and their symmetries wherever possible; some proofs may already be more compressed than is ideal for the reader. The appendix reached its length through our effort to make the work complete for future reference and as readable as possible. It could be shortened substantially: by omitting the figures repeated from the main text, the full-page diagram of proof dependencies, the figures illustrating the proofs, the one-page discussion of Assumption 1 or the example landscape plots; by citing the literature on the Clarke subdifferential, KKT points and MFCQ instead of recalling what we need in unified notation; or by stating the counterexamples without proving their properties. Our concern is that these cuts would make the arguments harder to follow and would remove details, particularly of the counterexamples, that may be useful in subsequent work. We would welcome your suggestions on where the exposition could be condensed while preserving its readability and usefulness.

I thank the reviewers for their responses. I invoked the non-locality of approximation in higher dimensions mostly to highlight that there is a fundamental difference, in general, between the univariate and the multivariate cases. Nonetheless, I found the reviewers' explanations helpful here.

The new results in Appendix J, however, I do not consider such a great addition. These dilute the scope and represent a somewhat awkward stopping point of inquiry. A paper should have a clear scope, and its results should not be partial, unless there is a really good reason for this. Here, the only reason is limited time in the rebuttal phase, and to me, that is not a good reason.

I would prefer a clearly scoped manuscript with complete results. The original version was something like that, focused on the univariate case. Such a result can and should be published. However, due to the limited depth, it should not necessarily be published at a top venue like ICLR.

I think my current score still adequately reflects this sentiment.

Thank you very much for your reply.

Regarding the depth, we are concerned your assessment may not be based on the entirety of our developments and proofs. We are convinced this work is as involved technically as most theoretical papers in recent years at ICLR and comparable other venues; for example, we think our proofs are as complex as those of Joshi et al. (ICLR 2024 spotlight) and Kim et al. (ICLR 2025 oral). In case you can suggest any specific ways of simplifying significantly our proofs while achieving the same results, we would be eager to see them.

We added the new appendix J on parity classification since Reviewer 4UTD asked us to "provide a targeted higher-dimensional experiment to assess whether the optimization benefit of the free affine skip connection persists beyond the univariate setting". We think it is a start of a promising direction for future work, which may lead to a separate paper by ourselves or others. Whether it should remain in the current work is a matter of taste (and we sympathize with your point of view on this). To make a decision on this, we would like to see also the thoughts of the remaining two reviewers, and any guidance from the Area Chair.

Reviewer_WpHAOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies minimal-norm interpolation and ℓ2\ell_2-regularized logistic-loss minimization for binary classification with univariate two-layer ReLU networks. The authors provide exact geometric characterizations of optimal classifiers, showing how bias regularization affects uniqueness and sparsity. In particular, they show that adding a free affine skip connection preserves the optimal functions while making every KKT point of the constrained problem globally optimal. They also show that, when biases are unregularized, not all minimal-norm interpolators can arise as small-regularization limits of margin-normalized logistic-loss minimizers.

Although this is not my primary area of expertise, I found the results particularly interesting and enjoyed reading the paper.

Critical strengths

Geometric characterization: While previous works have studied minimal-norm representations and related regression problems, this paper provides exact geometric characterizations of minimal-norm classifiers, showing how bias regularization affects uniqueness and sparsity.

Global optimality with skip connections: While skip connections are known to improve neural network training empirically, this paper provides a theoretical insight into their role in optimization landscapes. In particular, adding a free affine skip connection eliminates suboptimal KKT points without changing the optimal functions.

Connection to regularized logistic loss: Interestingly, the paper shows that even in the small-regularization limit, the possible limits of regularized logistic-loss minimizers are restricted to a subset of minimal-norm interpolators, revealing a nontrivial distinction between the two optimization formulations.

Critical weaknesses

Restricted setting: Although the results are valuable in the univariate setting, extending the geometric characterizations and global-optimality guarantees to multivariate inputs does not appear straightforward.

Presentation and intuition: Some of the main results could be explained more intuitively. For example, the meaning of "hug every label switch" is not immediately clear in the abstract. The proof sketch of Theorem 1 could benefit from a clearer structure, perhaps using subheadings to distinguish the main arguments, together with more explanation of their underlying intuition. It would also be helpful to explain why regularized logistic-loss minimizers satisfy the additional interval-turning property. Moreover, the term "discontinuity" between regularized and constrained optimization seems somewhat strong, as the result concerns additional restrictions on which minimal-norm interpolators can arise as small-regularization limits. Clarifying this distinction would be helpful.

In "implications of our results", it would be clearer to explain that the 32r+6732r+67 bound concerns the number of linear regions of functions represented by KKT points before introducing the bound itself. The privacy attack could also benefit from a brief explanation of how training inputs can be recovered from the learned classifier.

Questions for authors
  • Why is the affine skip connection assumed to be free (unpenalized)? Would the global-optimality result still hold if the skip-connection parameters were penalized?

  • Do the authors have any intuition or conjectures about the implicit bias of gradient descent on unregularized logistic loss? In particular, which minimal-norm interpolators, if any, would gradient descent be expected to select?

  • Could the authors explicitly indicate which optimization settings correspond to the functions illustrated in Figure 1?

3 comments

A preliminary multivariate study: parity classification (new Appendix J). We have added Appendix J, a preliminary study of parity classification on the hypercube {−1,1}d\lbrace -1,1\rbrace^d for both choices of bias penalization; its two theorems are given with proof sketches. For every d≥2d\geq 2, Theorem 8 gives the exact global minimum of the regularized logistic loss over all widths: it is the same with and without a free affine skip connection, and so are the optimal predictions on the cube. For d=3,4,5d=3,4,5, Theorem 9 determines the least widths attaining this minimum (2, 4 and 16 with the skip, against 4, 8 and 18 without), so both architectures can attain it at every width in our experiments. Figures 18 and 19 compare the two architectures against this exact benchmark, using 50 pairs of runs with identical initial ReLU parameters in each of the six settings (d=3,4,5d=3,4,5, with and without bias penalization). All 300 runs with the skip reached positive margins, against 279 of the 300 without it. Among the runs with positive margins, the skip lowers the mean relative excess in all six settings and, apart from occasional outliers, eliminates significantly suboptimal outcomes. We conjecture that in this setting the skip removes certain classes of suboptimal positive-margin Clarke stationary points, possibly not all; determining which, and with what consequences for gradient-based training, is a promising direction for future work.

The abstract and the proof sketch of Theorem 1. Thank you for these suggestions; we have revised the abstract and both proof sketches to explain the geometric conditions and the arguments behind them more directly. Instead of saying that the minimal-norm interpolators hug every label switch, the abstract now states that they equal the labels at both inputs incident to each label switch. The sketch of Theorem 1 is now organized under four headings: necessary conditions via local perturbations, identifying the minimizers, removing the skip connection, and KKT points are global minimizers. It explains how the free affine term supports the perturbations, and why, with unpenalized biases, all switch-hugging and convexity-correct functions have the same cost: the slope across each label switch is forced, and the slope changes within each intermediate segment share a sign. It also explains how penalizing biases forces a single kink in each intermediate segment.

Interval turning and the regularized-to-constrained limit. The sketch of Corollary 1 now explains this additional condition. Suppose that biases are unpenalized, and that the first and last kinks in an intermediate segment with label yy enclose a training input. Replacing the function between these two kinks by the extensions of the adjacent pieces moves it towards yy there, at the same cost, because the slope changes in the segment share a sign. This strictly decreases the logistic loss at the enclosed input, since the logistic loss keeps rewarding larger margins. The constrained problem, in contrast, is indifferent to this change, because the enclosed input already has margin at least 1; indeed, the cyan curve in Figure 1 is a minimal-norm interpolator that is not interval turning. An infinitesimal version of the same perturbation shows that positive-margin Clarke stationary points with a skip are interval turning. We have also replaced the word “discontinuity” and the wording about “most interpolators” throughout: margin-normalized limits of regularized-loss minimizers as λ→0\lambda\to 0 are still minimal-norm interpolators, but those violating interval turning cannot arise as such limits.

The bound of Safran et al. and the reconstruction of training inputs. We have rewritten the comparison with Safran et al. (2022) so that the quantity they bound by 32r+6732r+67, namely the number of linear regions of functions represented by KKT points of the penalized-bias interpolation problem, is identified before the bound is given. Our penalized-bias minimizer has exactly r−1r-1 kinks, hence rr linear regions, and this count applies both to global minimizers without the skip and to every KKT point with it. We also explain the reconstruction rule behind the privacy attack: solve g(x)=±1g(x)=\pm 1 and discard the interiors of intervals on which gg is constant. Switch hugging and convexity correctness ensure that the remaining points are exactly the training inputs incident to label switches, so every same-label segment is represented. Corollary 2 makes this precise, and the rule uses only the represented function, not the parameters.

Why the affine skip connection is free. We follow a standard convention in the literature on minimal-norm representors and regression interpolators (e.g., Ongie et al., 2020, Section 2.1; Hanin, 2021; Boursier and Flammarion, 2023; Kim et al., 2025, Section 3.3). Leaving the affine term free separates it from the cost of changes in slope, which gives simpler function-space formulations. We have made this motivation explicit in the introduction. A related practical example is Mamba (Gu and Dao, COLM 2024), whose reference implementation marks its trainable diagonal skip parameter for exclusion from weight decay; this is a more restricted bypass than the affine term studied here.

A penalized skip connection. The answer then depends on the form and strength of the penalty. Our proofs use affine corrections that incur no cost; with a penalty, their cost must be weighed against the reduction in the norm, so some of the directions that rule out suboptimal KKT points may remain effective while others may not. A penalized skip could thus still remove some suboptimal stationary configurations and help optimization, even if a general global-optimality guarantee fails. Which exclusions survive, and with what numerical benefit, would have to be established for the specific penalty.

Implicit bias of gradient descent on the unregularized logistic loss. This is an intriguing question, and our characterization gives a concrete candidate to investigate. Without a skip connection, the network is positively homogeneous in its parameters. At fixed width, and under their small-loss and regularity assumptions, Lyu and Li (2020, Theorem 4.4 and its logistic-loss extension) and Ji and Telgarsky (2020, Theorem 3.1) then imply that gradient flow converges in direction to a rescaled KKT point of the margin-maximization problem whose norm includes the hidden biases. If this point is globally optimal, Theorem 1(ii) identifies its function as the unique single-turning minimizer. Whether training selects this function, rather than a suboptimal KKT point, remains open, as does the corresponding question for finite-step gradient descent.

The same question with a trainable skip connection. There is also a reason to investigate the same candidate when a trainable affine skip is present. Under joint scaling of all parameters, the ReLU branch has degree two and the affine term degree one, so the latter disappears from the degree-two homogenization. Cai et al. (2025, Theorem 3.5) relate asymptotic directions to a margin problem for the homogenized network, which suggests that the leading margin problem may be unchanged by the skip. Their theorem assumes the exponential loss and continuous differentiability, however, so for our nonsmooth logistic-loss model this remains a conjectural connection. We have added this question to the conclusion; as noted there, testing such selection numerically is computationally expensive, because directional convergence can be very slow.

Figure 1. The figure illustrates the definitions of switch hugging, convexity correctness, single turning, and interval turning, and its revised caption now relates them to the optimization problems. With the unspecified origin placed so that Assumption 1 holds, all three curves are switch hugging and convexity correct, and hence minimize in function space the constrained problems with unpenalized biases, with or without the skip connection. Only the pink curve is single turning, so it is the unique function minimizing the penalized-bias problems. The lime and pink curves are interval turning, whereas the cyan curve is not, which illustrates the additional condition in Corollary 1(iii).

Thank you for the detailed responses and revisions. I appreciate the added discussion on the implicit bias of gradient flow. I will keep my original positive assessment.

Comments on the paper

1 comment

We thank the reviewers for their careful reading and constructive comments, which have helped us to improve the paper. We have uploaded a revised PDF, in which changed segments of the text are indicated in blue. In addition, two figures and one appendix are entirely new: the last two figures in appendix I (Figures 16 and 17), which give convergence diagnostics for our experiments, and the last appendix (J), a preliminary multivariate study of parity classification. We reply to each reviewer individually below, and we would be glad to answer any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.