Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization

1 Introduction

• The paper frames its contribution against the challenge of training high-dimensional, non-convex neural-network objectives, which are NP-hard in the worst case.It notes that even training a two-layer network of three nodes is NP-complete.Source: §1 · p. 2
• The paper targets whether SGD can efficiently train a ReLU network to global optimality despite infinitely many local minima, maxima, and saddle points.Linearly separable data provide a setting where zero training loss is attainable and can distinguish successful training.Source: §1 · p. 2
• It presents a simple SGD algorithm that uses noise to escape local minima and saddle points and attain global optimality for two-layer ReLU networks.The paper also offers theoretical and empirical evidence supporting noise injection during training.Source: §1 · p. 2
• The work investigates generalization behavior of ReLU networks trained with its novel SGD algorithm, including tight bounds and guarantees.The introduction identifies classic compression bounds as the basis for this analysis.Source: §1 · p. 2

2 Related Work

• Prior results learn two-layer networks under assumptions such as Gaussian data or sufficiently many hidden units, while general training remains NP-hard.These results concern different models and activation functions as well as particular assumptions.Source: §2 · p. 3
• Landscape results rule out bad minima for some sufficiently wide deep linear or quadratic-activation networks, and for leaky ReLU networks on linearly separable data.For leaky ReLU with hinge loss, all critical points are global minima; ReLU networks can instead have infinitely many bad local optima [50, Theorem 6], [5, Thm. 8],.Source: §2 · p. 3
• Existing complexity-based generalization bounds do not account for the training scheme, while compression bounds for leaky ReLU networks trained by SGD do not extend to ReLU networks.The cited PAC-Bayes bound is meaningful only when optimization succeeds [9].Source: §2 · p. 3

3 Problem Formulation

• The setting is binary classification on linearly separable data, with a two-layer network combining hidden ReLU activations into a scalar output.The second-layer weight vector is fixed with at least one positive and one negative entry, leaving the first-layer weights to be learned.Source: §3 · p. 4
• The empirical objective averages hinge loss over the training set, and separability makes zero training loss attainable.The ReLU-based empirical loss is non-smooth and non-convex, with infinitely many sub-optimal local minima [5, Thm. 8].Source: §3 · p. 4
• Figure 1 illustrates four critical points and shows that samples with classification error lie in the negative cone of all hyperplanes.The arrows indicate each hyperplane’s positive cone; the example has two positive-class samples and one negative-class sample.Source: Figure 1 · p. 5
• At a critical point, a sample with non-zero loss must have zero ReLU output at every hidden neuron.Such a sub-optimal critical point can be a local minimum, maximum, or saddle point, and small weight perturbations may not change its defining conditions.Source: §3 · p. 5
• Plain-vanilla SGD can encounter sub-optimal local minima where all hidden neurons are inactive for a sampled datum.The paper notes that under some conditions SGD converges to a sub-optimal local minimum with high probability.Source: §3 · p. 6

4.1 Algorithm

• Algorithm 1 perturbs ReLU activity indicators so at least one ReLU remains active at non-optimal critical points, enabling updates that can escape them.The Gaussian noise is added to the indicators’ inputs, not to hidden neurons; the hinge-loss indicator remains unperturbed.Source: §4.1 · pp. 6–8
• After no non-zero update occurs for np iterations, Algorithm 1 converges to a global optimum with probability that can be made arbitrarily close to 1 by increasing p or the noise variance.The stopping guarantee assumes bounded neuron weights and deterministic cycling through the samples.Source: §4.1 · p. 7

4.2 Convergence analysis

• With bounded initial rows, fixed nonzero second-layer weights of both signs, and a constant step size, Algorithm 1 reaches a global minimum in finitely many non-zero updates.The worst-case upper bound does not depend on input dimension, but scales with hidden-unit count and inversely with the step size.Source: §4.2 · pp. 8–9
• The convergence analysis bounds progress per non-zero update using lower and upper bounds on the Frobenius inner product and iterate norms.The bounds are compared through Cauchy–Schwarz to derive an upper bound on the number of updates.Source: §4.2 · p. 9

4.3 Lower bound

• For some linearly separable datasets, the required-update lower bound matches that for zero-initialized leaky-ReLU networks, while the ReLU upper bound is looser.The paper describes the gap between the bounds as the price of escaping bad local minima and saddle points.Source: §4.3 · p. 10

Compression construction

• The analysis uses the SGD-selected training examples as a compressed representation whose size is the number τk of non-zero updates.The remaining examples form the complement training set used in the risk bound.Source: §5 · p. 11

Compression bound

• The compression bound is non-asymptotic and requires n ≥ 2τk; as n grows, its final two terms vanish.The resulting ensemble-risk bound is then controlled by the empirical risk on the complement training set.Source: §5 · p. 11

Corollary 1

• In the worst case, reliably generalizing a k-unit ReLU network requires about n = O(k^2∥ω∗∥^2) training samples, despite zero training loss at any sample size.The stated comparison is with α-leaky ReLU networks, which need at most n = O(∥ω∗∥^2/α^2) samples for SGD-type training.Source: §5 · p. 11

6.1 Synthetic data

• Algorithm 1 reached global optimality in all considered Gaussian synthetic tests, while plain-vanilla SGD could get stuck, particularly for small k.The Gaussian experiments used 100 trials across varying sample counts and network sizes; success meant training loss at most 10^-10.Source: §6.1 · p. 12

6.2 Real data

• Algorithm 1 achieved 100% success in every tested uniform-data and iris setting, while the uniform-data plain-vanilla success rates were plotted separately.The iris tests used linearly separable, relabeled data; the uniform tests used d = 128.Source: §6.2 · p. 12, §6.1 · p. 12, Figure 3 · p. 13
• On MNIST digits 3 and 5, Algorithm 1 achieved 100% success under all tested conditions and markedly improved on plain-vanilla SGD.The tests varied training-set sizes and network widths on 2,000 linearly separable images.Source: §6.2 · p. 13

Conclusions

• The algorithm provably trains any single-hidden-layer ReLU network to global optimality on linearly separable data, regardless of data distribution, training or network size, or initialization.Random additive noise helps escape sub-optimal critical points; the analysis establishes upper and lower bounds on the required non-zero updates.Source: §7 · p. 13
• The paper’s compression-based generalization bounds reveal a worst-case sample-complexity difference between optimally learning ReLU and leaky ReLU networks.The stated ReLU-versus-leaky-ReLU comparison concerns the sample complexity required for generalization.Source: §7 · p. 13
• The analysis and comparisons are limited to single-hidden-layer networks with a hinge-loss criterion; multilayer networks and alternative losses are left for future work.The authors also identify (multi-)kernel approaches as a future direction.Source: §7 · p. 13

Stopping condition

• If every data point produces zero updates for a sufficiently long succession, the algorithm has reached a global minimum with high probability.The proof describes this stopping condition after t > 0 non-zero updates and with sufficiently large noise variance.Source: Appendix A.1 · p. 17

Update-count bounds

• The update-count argument bounds auxiliary quantities above and below, then telescopes their changes across non-zero updates.Its inequalities use the working condition ∥x_it∥_2 ≤ 1 and the fact that an update is non-zero.Source: Appendix A.1 · pp. 18–19
• For initialization W^0 = 0, the proof derives a maximum number of non-zero updates before convergence.The bound follows by taking ρ = 0 in the preceding expression.Source: Appendix A.1 · p. 20

• Summing the inequalities established for all k hidden neurons completes the proof.Source: Appendix B.2 · p. 21
• For an active ReLU with noise injected, the proof splits the inequality check according to whether noise changes the activity indicator.Source: Appendix B.2 · p. 21
• For an active ReLU without noise injection, the stated inequality holds with equality.Source: Appendix B.2 · p. 21
• For an inactive ReLU with noise injected, the inequality remains valid; without injection, both sides are zero and equality holds.Source: Appendix B.2 · p. 21

• The construction uses the d canonical basis vectors as positive-class training data, all correctly classified by the all-one weight vector of squared norm d.Source: Appendix C.3 · p. 21
• The argument telescopes the update while cycling deterministically through the d data points, then applies a necessary condition for a global minimum.Source: Appendix C.3 · p. 22
• With τ^-1=dp, the proof derives p≥1/(η||v||_2^2) as part of its lower-bound argument for Algorithm 1 initialized at W^0=0.Source: Appendix C.3 · p. 22

• Algorithm 1 performs at most Tk non-zero updates regardless of γ², so bounded initialization yields bounded iterates through iteration Tk.Source: Appendix D.4 · p. 22
• An update-free sampled point is either correctly classified or has all ReLUs inactive under the injected noise.Source: Appendix D.4 · p. 23
• With deterministic cycling, every datum is evaluated p times per np iterations, each with a different random noise realization.Source: Appendix D.4 · p. 23
• The referenced value can be made arbitrarily close to 1 by taking either a large enough p and/or γ > 0; the similar uniformly random case is omitted.Source: Appendix D.4 · p. 23