Source-linked AI summary
On the Quality of the Initial Basin in Overspecified Neural Networks
Itay Safran, Ohad Shamir
TL;DR
Training neural networks is practically successful, but understanding the computational tractability of their highly non-convex objectives remains an open problem. This paper studies objective geometry in ReLU networks under random initialization, finding conditions for monotone paths and low-value basins, with favorable properties more likely in larger networks. These are geometric results, not guarantees that a practical optimizer will converge to a good solution.
Problem
Despite neural networks' practical success, understanding the computational tractability of training remains a major open problem because the objective is highly non-convex and worst-case training is hard.
Source: §1 · pp. 1–2Method
The paper analyzes the geometry of ReLU-network objectives under random initialization, studying monotone paths for arbitrary-depth networks and basin values for two-layer networks.
Source: §1 · p. 2Results
Under stated conditions, larger networks are more likely to initialize at points with a decreasing path to a global minimum or in basins with small minimal values.
Source: §1 · pp. 2–3Takeaways & Limitations
The results characterize favorable geometric properties of the objective, including conditions under which overspecification improves the chance of a good basin or monotone path.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
Deep learning, in the form of artificial neural networks, has achieved remarkable practical success in recent years, for a variety of difficult machine learning applications. However, a theoretical explanation for this remains a major open problem, since training neural networks involves optimizing a highly non-convex objective function, and is known to be computationally hard in the worst case. In this work, we study the \emph{geometric} structure of the associated non-convex objective function, in the context of ReLU networks and starting from a random initialization of the network parameters. We identify some conditions under which it becomes more favorable to optimization, in the sense of (i) High probability of initializing at a point from which there is a monotonically decreasing path to a global minimum; and (ii) High probability of initializing at a basin (suitably defined) with a small minimal objective value. A common theme in our results is that such properties are more likely to hold for larger ("overspecified") networks, which accords with some recent empirical and theoretical observations.
1 Introduction
The paper studies whether the non-convex training objective of ReLU networks has geometric properties favorable to optimization. It analyzes monotone paths and low-value basins under random initialization, with favorable properties more likely in larger networks.
1 Introduction
- Training neural networks is practically successful but computationally hard in the worst case, motivating a study of objective geometry.Finding weights that best fit a training set is NP-hard even for very small networks.Source: §1 · p. 1
- For arbitrary-depth networks, increasing width can make random initialization more likely to admit a strictly decreasing path to a global minimum under mild conditions.The result concerns geometric paths, not whether a specific optimizer will find or follow one.Source: §1 · p. 2
- For two-layer scalar-output networks, larger width raises the probability of initializing in a basin with a small minimal objective value under conditions such as low intrinsic dimension or clustered data.Replacing the single-neuron construction of with Ω(log(d)) neurons yields, with overwhelming probability, a basin whose minimal value is globally optimal.Source: §1 · pp. 2–3
- The paper studies finite-sized networks on fixed datasets, unlike related work on asymptotically large networks with Gaussian data or learning methods that avoid direct objective optimization.Earlier results for very large networks may involve networks that almost invariably overfit [Livni et al., 2014; Haeffele and Vidal, 2015].Source: §1 · p. 3
2 Preliminaries and Notation
This section establishes the network, objective, basin, and initialization setup used in the paper. It focuses on feedforward ReLU networks, convex prediction losses, and a general class of random initializations.
2 Preliminaries and Notation
- The notation uses bold letters for vectors, capital letters generally for matrices, and [k] for the set {1, ..., k}.The parameter space is the Euclidean space containing the vector of all network weights.Source: §2 · p. 3, §2.1 · p. 4
2.1 ReLU Neural Networks
- The networks are fully connected feedforward networks with ReLU hidden units, a linear output layer, and width defined as the largest layer size.The analysis imposes no weight constraints such as regularization or convolutional layers.Source: §2.1 · pp. 3–4
2.2 Objective Function
- The objective is average loss over training examples; the loss is convex in predictions, although the objective is generally non-convex in network weights.The loss examples include squared loss and cross-entropy loss.Source: §2.2 · pp. 4–5
2.3 Basins
- A basin is a closed convex parameter-space region with connected sublevel sets in which every local minimum is global; its basin value is its minimal objective value.The analysis considers basins with disjoint interiors so that a point's basin is well-defined.Source: §2.3 · p. 5
2.4 Initialization Scheme
- Initialization assumes independent neuron weights, with each neuron's weight-and-bias vector drawn from a spherically symmetric distribution supported on non-zero vectors.Examples include independently drawn multivariate Gaussians up to scaling and uniform draws from an origin-centered sphere.Source: §2.4 · pp. 5–6
3 Networks of Any Depth: Path to Global Minima
For networks of any depth, the paper proves conditions under which a path from initialization to a lower objective value can be replaced by a strictly decreasing path. The result is geometric and does not guarantee that a practical local-search algorithm will find such a path.
3 Networks of Any Depth: Path to Global Minima
- The path result applies to arbitrary-depth fully connected networks and can reach an objective as low as the original path's endpoint, including a global minimum.The theorem requires an initial continuous path to a point with lower objective, but that original path need not be monotone.Source: §3 · pp. 6–7
- The existence of a decreasing path does not guarantee that local search, including stochastic gradient descent, will find or follow it.The authors characterize the results as geometric and note that the path may be difficult to find using local search.Source: §3 · p. 6
- Under convexity of the prediction loss and two path conditions, a lower-objective endpoint can be reached from initialization along a continuous path with strictly decreasing objective.The conditions require a rescaled prediction along the original path to remain above the initial objective by a positive margin, and the initial objective to exceed L(0).Source: §3 · p. 7
- Rescaling the linear output layer along the path provides the mechanism for converting a non-monotone path into a monotone one.The theorem itself also applies to networks with activation functions other than ReLU.Source: §3 · p. 7
- For squared loss or softmax cross-entropy, the needed condition that initialization has worse objective than the zero predictor holds with probability close to one half under the stated initialization scheme.The loss-growth condition is generally satisfied for these losses under the stated general-position conditions.Source: §3 · p. 7
4 Two-layer ReLU Networks
The paper analyzes how overspecification changes basin quality in two-layer ReLU networks, including on singleton, low-intrinsic-dimension, full-rank, and clustered data. These results concern objective geometry, not a guarantee that gradient descent reaches a good solution.
4 Two-layer ReLU Networks
- For two-layer scalar-output ReLU networks, fixing activation and output-weight signs partitions parameters into regions where local minima are global within each basin; this is a geometric claim, not an SGD guarantee.The sign-fixed regions are the basis of the paper’s basin analysis.Source: §4 · pp. 8–9
4.1 Bad Local Minima Results: Brittleness to Overspecification
- For singleton-instance datasets, the probability of a suboptimal basin decays exponentially with width and becomes arbitrarily small at n = Ω(log(d)).The result demonstrates brittleness of the cited hardness construction under overspecification; it is not intended as a claim about typical datasets.Source: §4.1 · p. 10
4.2 Data With Low Intrinsic Dimension
- For realizable data, increasing first-layer width raises the probability of initializing in a basin containing a good minimum, but the required width grows exponentially with intrinsic dimension.The result is most meaningful when intrinsic dimension and the original width are modest.Source: §4.2 · p. 10
4.3 Clustered or Full-rank Data
- Under rank(X) = m, a two-layer network of width O(log(m)) suffices to initialize in a basin with a global minimum with overwhelming probability.The theorem allows arbitrary target outputs; this regime has m ≤ d.Source: §4.3 · p. 11
- For sufficiently tight clusters, width Ω(log(d)) yields initialization in a basin containing a low-valued minimum with overwhelming probability.The clustered-data result concerns k ≤ d clusters.Source: §4.3 · pp. 11–12
A.1 Proof of Lemma 1
The proof establishes that each basin has a favorable geometry: the objective is convex in the products of output weights and neuron weights, and its sublevel sets are connected. It also shows that local minima within a basin are global, using paths that preserve the basin structure.
A.1 Proof of Lemma 1
- Within a basin, the objective is convex in Z = (z1, . . . , zn), where zi = viwi.With activation and output signs fixed, the network objective is a convex loss composed with a linear function of Z.Source: §A.1 · p. 14
- Positive rescaling of neuron weights provides a continuous path to a representation with normalized output-weight magnitudes.The proof uses positive homogeneity of ReLU to preserve the relevant network function along the rescaling path.Source: §A.1 · p. 14
- Every local minimum within a basin is global, and any two points in a sublevel set can be connected by a path that stays in that sublevel set.The proof interpolates weights while staying in the basin, then uses convexity of the objective in W there.Source: §A.1 · p. 16
A.2 Proof of Lemma 2
- The Lemma 2 proof compares representations within the same basin and uses that the compared weights compute the same network output.The supplied proof passage states that same-basin membership supports the inequality and identical outputs support the equality.Source: §A.2 · p. 17
B.1 Proof of Thm. 1
The proof constructs a continuous path from initialization by rescaling the output layer along a path in parameter space. It matches that path to a strictly decreasing loss target, yielding a monotonically decreasing route to the endpoint loss.
B.1 Proof of Thm. 1
- For squared loss, varying the output-layer scale makes the objective quadratic, allowing loss values along the scaling ray to be used in constructing the path.The proof notes that the objective ranges from its value at zero scale toward infinity as the scale grows.Source: §B.1 · p. 18
- For general convex losses, the proof chooses a unique continuous output-scaling factor so the loss matches a strictly decreasing target value.The scaling factor begins at 1, and its continuity is established using convexity and a local one-to-one property.Source: §B.1 · pp. 18–19
- Rescaling the last-layer weights continuously along the parameter path yields a strictly decreasing-loss path from initialization to a point with the endpoint path's loss.The proof then rescales the last-layer parameters to the endpoint while continuing to decrease the loss.Source: §B.1 · p. 19
B.2 Proof of Proposition 1
The proof establishes strict convexity of the loss as the output is scaled for both squared loss and cross-entropy. For cross-entropy, it uses that a nonzero, nonconstant prediction vector occurs with probability one under the stated conditioning.
B.2 Proof of Proposition 1
- For squared loss, scaling a nonzero prediction vector gives a strictly convex objective in the scale, so strict convexity holds with probability 1.At least one training example has a nonzero prediction, making its squared-loss term strictly convex; the remaining terms are convex.Source: §B.2 · p. 19
- For cross-entropy, the loss is strictly convex in the scale unless the prediction vector is constant, and the proof shows nonconstant predictions occur with probability 1 given nonzero network output.The Hessian argument identifies constant vectors as the only direction where the relevant second derivative can vanish.Source: §B.2 · p. 20
B.3 Proof of Proposition 2
Under the stated initialization assumptions, a neuron receives nonzero input with high probability, and output symmetry supplies a lower bound on the probability of the favorable loss comparison. The bound depends on the number of neurons in the preceding layer.
B.3 Proof of Proposition 2
- With independently initialized neurons from a spherically symmetric distribution, the output neuron receives nonzero input with probability at least 1 − 2^-n_{h−1}.When this occurs, the output is nonzero with probability 1; the proof applies this to a training example.Source: §B.3 · pp. 20–21
- The proof gives a probability lower bound of r/2 (1 − 2^-n_{h−1}) for the favorable side of the loss comparison.The bound combines nonzero output probability with symmetry between W and −W.Source: §B.3 · p. 21
B.4 Proof of Thm. 2
The proof compares the best achievable objective values with the values attainable in the initialized basin, then bounds the chance that initialization misses the required neuron conditions.
B.4 Proof of Thm. 2
- The proof reduces the desired basin-value guarantee to initializing in a basin that achieves a value β no greater than α.The single-neuron minimum is lower-bounded by the two-layer minimum α, which is itself lower-bounded by the average of the minima over the S±_j sets.Source: §B.4 · p. 21
- The proof treats the S±_j objectives separately because the basin partition fixes the sign at each coordinate.It uses a union bound to control whether any S±_j lacks a neuron attaining its minimal value.Source: §B.4 · pp. 21–22
- For a single neuron, the probability of failing the required condition is at most 3/4.The proof then uses neuron independence to bound the probability that the condition fails for every neuron.Source: §B.4 · pp. 21–22
B.5 Proof of Thm. 3
The proof bounds the chance that random initialization is close to an optimal weight, then uses such neurons to construct a basin with a small objective value.
B.5 Proof of Thm. 3
- The proof uses spherical-cap probabilities to bound how often a random neuron initializes near an optimal weight.It reduces the relevant sphere dimension from d to rank(X), since projection onto the span of the data preserves the basin region.Source: §B.5 · pp. 22, 24
- The proof bounds the probability of a good initialization using the measure of a hyperspherical cap.Its auxiliary geometric steps establish a lower bound on cap area relative to sphere area.Source: §B.5 · p. 23
- Rescaling neuron weights to the unit sphere preserves the initialized basin and its basin value.The proof invokes positive homogeneity of ReLU to rescale the output weights accordingly.Source: §B.5 · p. 24
- If enough neurons initialize close to an optimal weight, the constructed basin has objective value at most ε with probability at least 1 − e^-1.The proof counts good initializations using a binomial bound and applies a Chernoff bound.Source: §B.5 · pp. 25–26
B.6 Proof of Thm. 4
The proof constructs a network that predicts selected training examples correctly while leaving the rest at zero, and uses initialization conditions to place that construction in the same basin.
B.6 Proof of Thm. 4
- The construction assigns neurons to predict selected examples correctly and zero on the rest, combining them to attain objective value α.The Gram matrix of the training inputs has rank m, ensuring the coefficients used in the construction exist.Source: §B.6 · p. 26
- For each training instance, the proof requires a neuron whose weight has positive inner product with the instance and whose output sign agrees with its target.The proof analyzes the occurrence of these conditions under independent, spherically symmetric neuron initialization.Source: §B.6 · pp. 26, 28
- Replacing the initialized parameters with the construction preserves the basin by retaining the relevant signs of weights and output parameters.The proof checks that the constructed prediction on an instance is unaffected by earlier neurons that already predict it.Source: §B.6 · p. 27
- The proof concludes that initialization has at least the stated probability of landing in a basin achieving the global minimum α.The supplied passage does not specify the probability value.Source: §B.6 · p. 28
B.7 Proof of Thm. 5
The proof of Thm. 5 transfers a good solution on cluster centers to clustered data while accounting for noisy regions; the appendix also gives a poor-basin result for single neurons.
B.7 Proof of Thm. 5
- For δ > 0, the cluster partition adds noisy regions, so a good center solution is not guaranteed to lie in the initialized basin.The proof instead constructs a surrogate within the initialized basin and bounds how well it approximates the center solution.Source: §B.7 · pp. 28, 31
- The proof bounds initialization from noisy regions and uses general position of the cluster centers to meet the conditions of Lemma 9.General position is expressed as σ_min(C) > 0, implying rank k; Lemma 9 then supplies the basin-constrained approximation step.Source: §B.7 · pp. 28, 31, 33
- With high probability, Thm. 4 provides a zero-value solution on the cluster centers, which the proof uses to seek a good solution on the clustered sample.The proof's stated strategy is to approximate the center solution and transfer its objective value to the data.Source: §B.7 · pp. 28, 31
C Poor Basin Structure for Single Neurons
- The appendix presents a hardness result for initializing single-neuron ReLU networks with convex losses in a basin with good basin value.It also gives an explicit construction for squared loss; single-neuron basins arise by partitioning weights according to training-instance activation signs.Source: C Poor Basin Structure for Single… · p. 34
C.1 Exponentially Many Poor Local Minima
The section constructs ReLU objectives with exponentially many poor local minima, then gives an explicit squared-loss example. Under the stated initialization condition, the higher-dimensional construction is overwhelmingly likely to start in a sub-optimal basin despite an ε-valued solution.
C.1 Exponentially Many Poor Local Minima
- The construction extends to a single ReLU neuron, where their technical conditions do not apply.Source: §C.1 · p. 34
- With initialization according to Assumption 1, the construction has 2^d strict local minima, and the probability of starting in a sub-optimal basin converges exponentially fast to 1 despite an ε-valued solution.Theorem 6 states that the sample is ε-realizable; the accompanying explanation gives the initialization-probability conclusion.Source: §C.1 · p. 35
- Independent coordinate-wise minima combine into 2^d local minima, with each combined minimum's value averaging the one-dimensional minima.The all-good combination is the global minimum with value ε.Source: §C.1 · pp. 35–36
C.2 An Explicit Construction With the Squared Loss
- In the two-dimensional illustration, the objective surface has one optimal minimum, one bad minimum, and two average-valued minima.Source: Figure 3 · p. 37
- For ReLU with squared loss, the explicit construction is ε-realizable and gives a 50% chance of initializing in the bad basin under Assumption 1.Extending the sample to d dimensions yields 2^d local minima.Source: §C.2 · pp. 36–37