Source-linked AI summary
Convex Geometry and Duality of Over-parameterized Neural Networks
Tolga Ergen, Mert Pilanci
TL;DR
Finite-width two-layer ReLU networks can favor simple solutions, but the structure behind that bias is not fully characterized, especially beyond one dimension. The paper uses convex geometry and duality to characterize optimal networks and develop convex training approaches. It derives spline structure for one-dimensional and rank-one data, alongside closed-form solutions and conditions for globally optimizing relaxations.
Problem
The structure and mechanism behind simple solutions in finite-width ReLU networks remain incompletely characterized, particularly for data beyond one dimension.
Source: §1 · p. 1Method
The paper uses convex duality to characterize optimal networks as extreme points of a convex set and develops convex relaxations for training.
Source: §1 · p. 2, §3.6 · p. 16Results
Optimal networks yield linear spline interpolation for one-dimensional and rank-one data, and the analysis gives closed-form parameters in some practical cases.
Source: §1 · p. 2, §7 · p. 31Takeaways & Limitations
The convex characterization explains simple output structures and provides globally optimizing relaxations when stated geometric conditions hold.
Source: §2.2.1 · p. 8, §7 · p. 31The convex formulations are not tractable in polynomial time in the worst case; with A = I_n, the problem becomes copositive and is NP-hard for arbitrary Y.
Source: §4.5.4 · p. 25
Abstract
from arXiv · showhide
We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We first prove that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set, where simple solutions are encouraged via its convex geometrical properties. We then leverage this characterization to show that an optimal set of parameters yield linear spline interpolation for regression problems involving one dimensional or rank-one data. We also characterize the classification decision regions in terms of a kernel matrix and minimum $\ell_1$-norm solutions. This is in contrast to Neural Tangent Kernel which is unable to explain predictions of finite width networks. Our convex geometric characterization also provides intuitive explanations of hidden neurons as auto-encoders. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints. Then, we apply certain convex relaxations and introduce a cutting-plane algorithm to globally optimize the network. We further analyze the exactness of the relaxations to provide conditions for the convergence to a global optimum. Our analysis also shows that optimal network parameters can be also characterized as interpretable closed-form formulas in some practically relevant special cases.
1. Introduction
The introduction frames the unresolved problem of explaining why finite-width ReLU networks favor simple solutions, then presents a convex-geometric account and its consequences for spline fits, optimal parameters, and training methods.
1. Introduction
- Earlier work linked implicit regularization to simple ReLU-network solutions, but the structure and mechanism of optimal solutions beyond one dimension remained unclear.The paper positions its analysis against lazy-regime kernel characterizations, which do not explain finite-width network behavior.Source: §1 · p. 1, §1.1 · p. 2
1.2 Our contributions
- The framework characterizes optimal networks through extreme points of a data-dependent convex set, whose geometry encourages simple solutions and whose extreme points act as autoencoders.The authors relate this geometry to sparsity-promoting ℓ1 regularization and provide exact expressions for extreme points.Source: §1.2 · p. 3
1.3 Overview of our results
- For one-dimensional and rank-one data, optimal networks fitting the training outputs yield linear spline interpolations, while a representer theorem characterizes hidden weights more generally.In the one-dimensional overview, small initialization produces spline fits with neuron kinks at input samples; the same analysis applies to hinge-loss binary classification.Source: §1.2 · p. 3, §1.3 · pp. 3–5
1.2 Our contributions
- For specific cases, the authors reformulate training as convex optimization and show that multiple globally optimal minimum-regularization networks can make different predictions.The introduction also notes that the minimum-norm criterion alone need not uniquely determine the network model.Source: §1.2 · p. 3
- For whitened data matrices, convex duality yields exact closed-form expressions for both network layers, with a thresholding effect resembling soft-thresholding.The paper also connects ReLU training to ℓ0-ℓ1 equivalence in compressed sensing to derive closed-form parameters in certain practical cases.Source: §1.2 · p. 3
- The authors propose convex-relaxation-based training algorithms and prove tightness in certain regimes, including whitened and i.i.d. random training data, enabling global optimization there.They also report that their convex optimization methods perform well on standard datasets and offer transparent, interpretable training.Source: §1.2 · p. 3
1.4 Organization of the Paper
- The paper’s organization moves from problem definitions and convex-duality results to extensions, an NTK comparison, numerical experiments, and concluding remarks.The extensions cover regularization, vector outputs, and arbitrary convex losses.Source: §1.4 · p. 5
2. Preliminaries
The section recasts regularized two-layer ReLU training through the geometry of rectified ellipsoids and their extreme points. This geometry characterizes optimal neurons and, for one-dimensional data, explains linear-spline interpolation.
2. Preliminaries
- The training objectives optimize network parameters under regularization, but their nonconvex ReLU objectives can have complex landscapes depending on the data matrix.After rescaling, minimum squared Euclidean norm is equivalent to minimum ℓ1-norm.Source: §2 · p. 6
2.1 Geometry of a single ReLU neuron in the function space
- For a single neuron, the feasible outputs form a rectified ellipsoid, whose geometry determines the distance-minimizing fit to the positive or negative labels.The ellipsoid's shape and orientation depend on the data matrix's singular values and output singular vectors.Source: §2.1 · p. 6
2.2 Rectified ellipsoid and its geometric properties
- The rectified ellipsoid is generally nonconvex, but it is convex for spike-free data matrices, where it equals the intersection of the ellipsoid image and the nonnegative orthant.Its convex hull can provide a convex relaxation when the set itself is nonconvex.Source: §2.2 · p. 7, §2.2.1 · pp. 7–8
2.2.1 Spike-free matrices
- Whitened matrices with n ≤ d and rank-one matrices with positive left singular vectors are spike-free; whitening is one practically relevant example.The paper also gives a matrix condition characterizing spike-free data.Source: §2.2.1 · pp. 7–9
2.3 Polar convex duality
- The dual of the optimization problem is expressed through the polar set of the rectified ellipsoid.The polar set is defined as Q_A's polar.Source: §2.3 · p. 9
2.4 Extreme points
- Optimal neurons lie among extreme points: in one dimension their ReLU kinks align with training samples, yielding linear-spline interpolation, while in higher dimensions they admit a data-based representer characterization.The higher-dimensional characterization describes neurons as convex-mixture approximations of training samples and supports an auto-encoder interpretation.Source: §2.4 · pp. 10–11
3. Main Results
The results characterize finite-width two-layer ReLU networks through convex duality and extreme points, yielding global optimization guarantees and structural results for several data regimes. They also identify settings where optimal solutions are non-unique or admit simpler convex formulations.
3.1 Convex duality
- Optimal neuron weights lie among extreme points determined by a dual optimum, and strong duality holds with an optimal width bounded by n + 1.The optimality condition is ∥(AU*)^T + v*∥∞ = 1 for dual-optimal v*.Source: §3.1 · pp. 11–12
3.1.1 Duality for finite width neural networks
- For feasible finite-width networks, strong duality holds once width reaches the number of active dual constraints, which is at most n + 1.The primal optimum can then be attained through the dual form and a subset of the characterized extreme points.Source: §3.1.1 · p. 12
3.2 Structure of one dimensional networks
- For one-dimensional data, optimal solutions include linear spline interpolants with kinks at data points, but other optimal fits can have different forms and predictions.The optimal neuron parameters have u_i = ±1 and b_i = −sign(u_i)a_i; the dual characterization also describes non-spline optima.Source: §3.2 · pp. 13–14
3.3 Solutions to rank-one problems
- For rank-one data matrices A = ca^T, optimal solutions can be chosen from characterized extreme points, and strong duality holds.These results provide a finite subset of extreme points for global optimization.Source: §3.3 · pp. 14–15
3.4 Solutions to spike-free problems
- For spike-free data, the regularized training problem is equivalent to a convex problem with two neurons and can be globally optimized in polynomial time.The formulation can be solved with standard convex optimization solvers.Source: §3.4 · p. 15
3.5 Closed-form solutions and ℓ0-ℓ1 equivalence
- Under stated conditions, the minimum-cardinality and regularized solutions coincide; whitened data matrices with n ≤ d satisfy this ℓ1-ℓ0 equivalence.For whitened data, the network can be globally optimized using the two extreme points identified in Lemma 9.Source: §3.5 · pp. 15–16
3.6 A cutting plane method
- The cutting-plane method uses convex optimization subproblems and globally optimizes the dual for spike-free data, inserting neurons until no violating neuron remains.The method adds neurons incrementally rather than requiring a prespecified hidden-layer width.Source: §3.6 · p. 16
- If every sample is a vertex of the sample convex hull, n basis-direction neurons suffice for zero training error; high-dimensional i.i.d. Gaussian data meet this vertex condition with high probability when d > 2n log(n − 1).Separately, i.i.d. Gaussian data matrices are asymptotically spike-free as d → ∞.Source: §3.6 · pp. 16–17
4. Regularized ReLU Networks and Convex Optimization for Spike-Free Matrices
This section develops convex optimization formulations for regularized ReLU networks, extending the analysis to convex losses and vector outputs and focusing on spike-free data. It gives globally optimizable scalar-output problems, closed-form solutions, conditions for efficient or hard vector-output optimization, and an ℓ1–ℓ0 equivalence condition for a spike-free relaxation of the ℓ1-regularized vector-output case.
4.1 Regularized two-layer ReLU networks
- For regularized networks, optimal neurons can be obtained from a dual problem; for whitened data, closed-form solutions show how weight decay β controls neuron counts and parameter forms.These formulas eliminate the need for backpropagation or other numerical training methods in the whitened case.Source: §4.1 · pp. 18–19
4.2 Two-layer ReLU networks with hinge loss
- For hinge-loss classification, dual solutions use extreme-point neurons; in one dimension they yield piecewise-linear fits and minimum ℓ1-norm SVM solutions, with rank-one datasets also admitting an ℓ1-norm SVM solution.In one dimension, decision boundaries are determined by zero crossings, and margin samples lie on the piecewise-linear fit.Source: §4.2 · pp. 19–20
4.3 Two-layer ReLU networks with general loss functions
- For arbitrary convex losses, optimal parameters lie in the same extreme-point set determined by the input data matrix, independent of the loss function.The dual formulation uses the Fenchel conjugate of the loss.Source: §4.3 · p. 21
4.4 Polynomial-time convex optimization of problems with spike-free matrices
- For two-layer ReLU training on spike-free data matrices, the equivalent convex problem has 2d variables and 2n constraints and is globally solvable by standard interior-point solvers in O(d^3).Source: §4.4 · p. 22
4.5.1–4.5.2 Solutions to one dimensional and rank-one problems
- For one-dimensional and rank-one vector-output data, extreme points can be characterized and fixed as hidden neurons, reducing regularized training to a globally solvable convex problem.The rank-one result gives efficient global optimization with standard convex solvers.Source: §4.5.1 · p. 23, §4.5.2 · pp. 23–24
4.5.3 Solutions to Whitened Problems
- For whitened vector-output data with one-hot labels, at most o hidden neurons classify individual classes, activate only when β is below the square root of that class’s sample count, and have Fisher discriminant form.The hidden-neuron form is Fisher’s Linear Discriminant applied one-vs-all.Source: §4.5.3 · pp. 24–25
4.5.4 Convex optimization for spike-free problems
- For spike-free vector-output data, the bidual convex formulation is not generally polynomial-time tractable: with A = I_n it becomes a copositive program, NP-hard for arbitrary Y.The result states the convex problem’s scope limitation, unlike the scalar-output spike-free formulation.Source: §4.5.4 · p. 25
4.5 Extension to vector output neural networks
- For vector outputs, the section derives a dual formulation and cutting-plane approach; an ℓ1-regularized variant is introduced to find extreme points efficiently using convex optimization tools.The derivations extend to regularized problems with arbitrary convex losses.Source: §4.5.5 · p. 25
4.5.5 ℓ1 regularized version of vector output case
- A dual formulation chosen for simpler cutting-plane solutions leads to spike-free relaxations; selecting the maximum- and minimum-objective neurons yields hidden-layer weights via convex optimization.The optimization is performed for each output coordinate.Source: §4.5.5 · p. 26
- For n ≤ d and full-row-rank A, with one-hot encoded outputs and at least one sample per class, Lemma 12 characterizes an optimal solution for each output coordinate.The provided passage states the characterization but omits its formula.Source: §4.5.5 · p. 26
- Lemma 13 establishes ℓ1-ℓ0 equivalence when its stated condition holds; the condition itself is not included in the supplied passage.Source: §4.5.5 · p. 26
5. Comparison with Neural Tangent Kernel
The section contrasts the paper’s exact kernel characterization with NTK, whose construction linearizes the network under a particular scaling assumption. In one-dimensional regression, NTK produces smoother functions than GD and the paper’s approach, while the latter yield piecewise-linear fits.
5. Comparison with Neural Tangent Kernel
- NTK characterizes an infinitely wide network through a kernel of parameter-gradient inner products, interpreted as a linearization under a particular scaling assumption.Earlier kernel approaches considered untrained networks or trained only the last layer while keeping hidden layers fixed and random.Source: §5 · p. 26
- The paper’s approach differs from NTK in both kernel construction and objective function.The paper characterizes NTK as a kernel method based on gradients with respect to all network parameters under an infinite-width limit.Source: §5 · pp. 26–27
- In one-dimensional regression, NTK outputs smoother functions than GD and the paper’s approach, whose piecewise-linear fits have kinks aligned with data points.The authors also note that optimal solutions may be non-unique, which explains why GD can have a kink between data points.Source: §5 · p. 27, Figure 9 · p. 27
6. Numerical Experiments
Experiments report that the closed-form network achieves the lowest training objective and highest test accuracy on sampled MNIST and CIFAR-10, while the convex cutting-plane approach outperforms backpropagation on the full-data experiments. Convex-RF uses extreme-point filters learned from image patches, and its reported accuracy is almost 40% higher than the cutting-plane convex approach.
6. Numerical Experiments
- On the synthetic binary classification experiment, Theory achieves slightly better test generalization than GD.Figure 10 plots mean test accuracy with one-standard-deviation confidence bands; an example shows agreement between the approaches’ fitted functions.Source: §6 · p. 28, Figure 10 · p. 28
- On sampled MNIST and CIFAR-10, the closed-form network achieves the lowest training objective and highest test accuracy; on full datasets, Convex outperforms backpropagation.The experiments use five independent SGD trials for the sampled classification tasks; Table 1 reports classification accuracies and test errors.Source: Figure 11 · p. 28, §6 · p. 29, Figure 12 · p. 29
6.1 Unsupervised and interpretable training using extreme points: Convex-RF
- Convex-RF uses extreme points extracted from image patches as filters, and its reported accuracy is almost 40% higher than Convex’s.The approach obtains filters from randomly selected, normalized patches through a convex optimization problem with unit-simplex constraints, then solves a convex ℓ1-norm problem for output weights.Source: §6 · p. 29, Figure 13 · p. 30, §6.1 · pp. 30–31
- The authors state that whitening is optional for Convex-RF because its hidden neurons are informative and normalized, and its distance-to-convex-hull construction is more robust to patch correlations.They contrast this with approaches using direct distances or sample inner products, for which whitening can make features more informative.Source: §6.1 · p. 31
7. Concluding Remarks
The paper uses convex duality to characterize optimal two-layer ReLU networks and explain their simple output structures, including linear splines. Closed-form parameter solutions apply in special data settings, while broader extensions remain open research directions.
7. Concluding Remarks
- Optimal solutions are extreme points of a convex set, yielding simple network outputs such as linear spline interpolation for one-dimensional data.For rank-one or spike-free data matrices, closed-form hidden-layer weights can permit training only the output layer.Source: §7 · p. 31
- The framework relates finite-width ReLU networks to minimum-cardinality problems and provides closed-form optimal hidden-layer weights in practically relevant cases.For those cases, the output layer can then be trained as a linear layer, similarly to kernel regression or classification.Source: §7 · p. 31
- Unlike NTK and other kernel methods, the approach uses ℓ1-norm regularization and matches classical finite-width ReLU networks trained with SGD in the stated comparison.The paper also introduces a cutting-plane algorithm for arbitrary data and proves global-optimum convergence under certain assumptions.Source: §7 · p. 31
- The authors identify convex-duality analysis of optimization and generalization in deep networks, and extensions to deeper networks, as open research directions.They conjecture that a similar framework may extend beyond the analyzed data classes to arbitrary distributions and alternative architectures.Source: §7 · pp. 31–32
- Some analyses are restricted to spike-free, whitened, rank-one, or one-dimensional data; extension to arbitrary data distributions and deeper networks is conjectured.The authors also suggest that convex formulations for spike-free problems could support efficient layerwise optimization of deeper networks.Source: §7 · p. 32
Appendix
The appendix provides proofs of the main results and additional algorithmic and numerical details.
Appendix
- The appendix presents proofs of the main results and further details on the algorithms and numerical results.Source: Appendix · p. 33
8. Additional details on the numerical experiments
The experiments compare the proposed approach with backpropagation-trained two-layer networks and linear least squares on real datasets. The setup also tests how initialization standard deviation relates to deviation from linear interpolation.
8. Additional details on the numerical experiments
- The experiments evaluate the proposed approach on several real datasets, comparing it with a backpropagation-trained two-layer network and linear least squares.The two neural-network approaches use the same number of hidden neurons; regularization is used to support generalization to unseen data.Source: §8 · p. 33
- For large datasets such as CIFAR-10, the experiments use SPGL1 and SuperSCS because plain CVX solvers may require significant memory.Source: §8 · p. 33
- Figure 1 measures the maximum absolute difference between a fully training-fitted network and ground-truth linear interpolation across different initial weight standard deviations, averaged over random trials.The same settings are used for the hinge-loss experiment.Source: §8 · p. 33
9. Cutting plane algorithm with a bias term
The bias-term cutting-plane algorithm searches for dual constraint violations, using a convex relaxation to find candidate hidden-layer weights and biases. It adds violating neurons iteratively and terminates when optimality conditions hold.
9. Cutting plane algorithm with a bias term
- Adding a bias term makes the cutting-plane algorithm more involved because it introduces extra constraints.The corresponding dual problem is given by Theorem 1.Source: §9 · p. 34
- The algorithm searches among unit-norm weights for those violating a dual inequality constraint.The passage also presents the dual variable and optimal parameters in relation to this dual problem.Source: §9 · p. 34
- Because the ReLU-based search problem is nonconvex, the method applies a spike-free relaxation that replaces the ReLU-transformed set with a convex set.Source: §9 · p. 34
- The algorithm adds each violating neuron's weights and bias, resolves the original problem, and repeats until no new violation remains and optimality conditions hold.Without an output bias, a nonzero sum of dual variables makes a problem unbounded and supplies a violating constraint; with an output bias, the dual enforces a zero sum. The algorithm is guaranteed to terminate in finitely many iterations under the stated boundedness conditions.Source: §9 · p. 34
10. Infinite size neural networks
The section formulates infinite-width two-layer networks using measures over ReLU basis functions, whose total variation norm reduces to an ℓ1 norm for finitely many neurons. It also presents a cutting-plane training procedure and notes extensions to other objectives and outputs.
10. Infinite size neural networks
- The cutting-plane algorithm adds violating neurons, uses a dual problem to check for further violations, and solves the resulting problem to return network parameters.The algorithm is identified as training for two-layer networks with bias.Source: §10 · p. 35
- For finitely many neurons, representing the measure as a mixture of Dirac deltas makes its total variation norm equal to the neuron-weight ℓ1 norm.The section relates this finite-width formulation to the infinite-dimensional measure-based problem.Source: §10 · p. 35
- The formulation extends to regularized objectives, different loss functions, and vector outputs.The section states that similar results hold in these settings.Source: §10 · p. 35
11. Proofs of the main results
The proofs establish geometric properties of optimal network parameters and construct extreme points by optimizing over neuron directions and activation patterns. They also show that multiple optimal training solutions can arise when the bias does not affect the objective.
11.1 Proofs for the results in Section 2
- Rescaling neuron parameters preserves the network representation, and the proof uses this freedom to impose unit-norm directions and express the objective through the weight ℓ1 norm.The argument rescales each direction and bias by a positive factor while inversely rescaling its output weight.Source: §11.1 · p. 36
- For an optimal solution, any neuron with nonzero weight must have its unit-norm inequality constraint active.Otherwise the proof removes the inactive constraint and reduces the objective by setting that neuron's weight to zero.Source: §11.1 · p. 36
- The extreme-point proofs divide samples into ReLU-active and inactive sets, then optimize over directions and biases consistent with that partition.In one dimension, the direction is restricted to ±1, and the feasible bias range follows from the activation inequalities.Source: §11.1 · pp. 37–38
- When the active-set coefficients sum to zero, every feasible bias in the specified interval is optimal, so the training problem can have multiple optimal solutions.For a one-dimensional direction, the interval is bounded by the active and inactive samples' locations.Source: §11.1 · p. 37
Proof of Theorem 1 and Corollary 2
The proofs connect finite-width networks to convex optimization and establish equality of primal and dual values. They show that at most n + 1 active constraints suffice to represent the relevant extreme points.
Proof of Theorem 1 and Corollary 2
- For finite-width optimal neurons with nonzero weights, the corresponding inequality constraints must attain their extreme points.The proof argues that a non-extreme neuron can be removed without changing the optimum, then its weight set to zero.Source: Proof of Theorem 1 and Corollary 2 · p. 40
- The proof establishes weak duality for finite-width networks by comparing their objective values with the infinite-width problem.It uses the fact that an infinite-width network can attain an objective no larger than a finite-width network.Source: Proof of Theorem 1 and Corollary 2 · p. 40
- At most n + 1 active dual constraints are needed, yielding a finite set of extreme-point neurons for the finite-width formulation.The proof uses Carathéodory’s theorem to bound the number of active constraints.Source: Proof of Theorem 1 and Corollary 2 · pp. 40–41
- The convex ℓ1-norm problem with linear equality constraints has strong duality, and the proof uses it to establish strong duality for finite-width networks.The argument first relates the finite-width formulation to the infinite-width optimum.Source: Proof of Theorem 1 and Corollary 2 · p. 41
Proof of Proposition 1
The proofs analyze optimal network parameters through non-uniqueness, extreme-point geometry, strong duality, and primal optimality. They also derive special-case closed-form or convergence results, characterize simple neuron constructions and positive sample-to-hull distances, and connect the network dual to minimum ℓ1-norm and gauge optimization.
Proof of Proposition 1
- The unregularized one-dimensional example has distinct optimal parameterizations with the same objective value, disproving uniqueness.The example uses a = [-2, -1, 0, 1, 2] and y = [1, -1, 1, 1, -1].Source: Proof of Proposition 1 · p. 42
- For β = 10^-4, the regularized example has infinitely many optimal solutions, with biases parameterized by any c in [0, 1].These solutions attain the same objective value; the extreme-point characterization explains the interval when the relevant output weights sum to zero.Source: Proof of Proposition 1 · pp. 43–44
- For rank-one data A = ca^T, the extreme-point conditions require u to align positively or negatively with a, with b lying in a corresponding interval.The stated alignment is u = s a/||a||₂ for s = ±1.Source: Proof of Proposition 1 · p. 44
- The cutting-plane method converges because the constraint is bounded below and hidden-layer weights lie in the unit Euclidean ball.The proof invokes Theorem 11.2 of Goberna and López-Cerdá (1998).Source: Proof of Proposition 1 · p. 46
- When each sample is a vertex of the convex hull of the data, separating neurons yield a feasible network with zero training error.The proof constructs one separating hyperplane per sample, making the activated data matrix diagonal and full rank.Source: Proof of Proposition 1 · p. 47
- For d > 2n log(n−1), the proof gives positive expected sample-to-hull distance and, with probability exceeding 1 − 2e^(−t²/2), positive distances for all samples.A union bound with t² = 4 log(n−1) gives failure probability O(1/n).Source: Proof of Proposition 1 · p. 48
11.3 Proofs for the results in Section 4
- The supplied proof passage states that Theorem 8 establishes equivalence between weight-decay and ℓ1-regularized problems, using a scaling argument as in the proofs of Lemmas 1 and 2.Source: §11.3 · p. 48
- The proof establishes strong duality (P = D) and shows that the weights in (67) are optimal for the primal problem (66).Source: §11.3 · p. 52
12. Polar convex duality
- The polar-duality section restates the constraint and dual in polar terms, relating the network problem to minimum ℓ1-norm solutions and a parallel gauge-optimization form.Source: §12 · p. 53