- 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
- The paper is technically solid, and its presentation and organization are clear.
- 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.
- 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 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 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 (while the experiments sweep over ), 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
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 against the gradient norm of the full objective divided by the run's regularization strength, , and Figure 17 plots it against the relative improvement of the best loss over the second half of training, where . 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 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 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 , and every such width admits a global constrained minimizer, which is a KKT point by MFCQ. Under the bound on in Theorem 6, these widths also admit a positive-margin global minimizer of the regularized loss. Without the skip, 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 , 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 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 , 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 for both choices of bias penalization; its two theorems are given with proof sketches. For every , 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 , 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 (, 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.
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, 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) with ∥u∥=1, balancing by positive homogeneity gives the cost ∣α∣ when biases are unpenalized and ∣α∣1+h2 when they are penalized. In one dimension, ∣h∣ 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.