Source-linked AI summary
Learning One-hidden-layer ReLU Networks via Gradient Descent
Xiao Zhang, Yaodong Yu, Lingxiao Wang, Quanquan Gu
TL;DR
The paper addresses guarantees for gradient-based learning of one-hidden-layer ReLU networks using empirical risk, a setting tied to practical training. It analyzes gradient descent for Gaussian-input noisy teacher data and proves linear convergence to teacher parameters up to statistical error, with sample complexity linear in dimension up to logarithmic factors.
Problem
The paper addresses the limited theory for gradient-based learning of shallow ReLU networks using empirical loss, the objective used in practical training.
Source: §1 · pp. 1, 3Method
Results
Gradient descent converges linearly to the ground-truth parameters up to statistical error, with sample complexity linear in d up to a logarithmic factor.
Source: §1 · p. 3, §7 · p. 11Takeaways & Limitations
The analysis provides a recovery guarantee for empirical-risk training of one-hidden-layer ReLU networks with multiple neurons.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We study the problem of learning one-hidden-layer neural networks with Rectified Linear Unit (ReLU) activation function, where the inputs are sampled from standard Gaussian distribution and the outputs are generated from a noisy teacher network. We analyze the performance of gradient descent for training such kind of neural networks based on empirical risk minimization, and provide algorithm-dependent guarantees. In particular, we prove that tensor initialization followed by gradient descent can converge to the ground-truth parameters at a linear rate up to some statistical error. To the best of our knowledge, this is the first work characterizing the recovery guarantee for practical learning of one-hidden-layer ReLU networks with multiple neurons. Numerical experiments verify our theoretical findings.
1 Introduction
The introduction frames a gap in gradient-descent theory for practical empirical-loss training of shallow ReLU networks. It studies recovery from Gaussian inputs and noisy teacher outputs, establishing linear convergence under suitable initialization and sample complexity linear in dimension up to logarithmic factors.
1 Introduction
- The introduction motivates the work by noting that nonconvex, nonsmooth loss landscapes leave existing optimization theory unable to explain effective gradient-based neural-network learning.Prior theoretical studies of shallow-network gradient descent had established recovery guarantees under a teacher-network assumption.Source: §1 · p. 1
- The recovery problem uses Gaussian inputs and noisy outputs from a one-hidden-layer ReLU teacher, with parameters estimated by minimizing empirical square loss.The goal is to recover the teacher's unknown parameter matrix.Source: §1 · p. 2
- The paper analyzes empirical risk minimization, unlike prior studies of one-hidden-layer ReLU learning that use ideal population risk (Tian, 2017; Li and Yuan, 2017; Du et al., 2017a,b).The authors describe the empirical-loss setting as more aligned with deep-learning practice.Source: §1 · p. 3
- With an appropriate initialization, gradient descent converges linearly to the teacher parameters up to statistical error, with sample complexity linear in d up to a logarithmic factor.The statistical error depends on sample size, input dimension, hidden-layer width, and noise magnitude.Source: §1 · pp. 2–3
- Uniform convergence control for empirical-loss gradients near the true parameters supports the convergence guarantee without the sample-splitting trick used by Zhong et al. (2017).The analysis characterizes the difference between empirical- and population-loss gradients near the ground truth.Source: §1 · p. 3
2 Related Work
Related work spans studies of neural-network expressivity and optimization, including gradient-based recovery analyses for shallow networks. The paper distinguishes its empirical-loss analysis from prior population-risk results and from approaches that require smooth activations or modified objectives.
2 Related Work
- Other work studies neural-network expressivity, while optimization-landscape analyses cover varied architectures and assumptions, including ReLU networks with multiple neurons using square loss.The cited expressivity literature includes approximation results for shallow networks and depth-related expressivity comparisons.Source: §2 · pp. 3–5
- Worst-case hardness results coexist with specialized learning algorithms, but the cited algorithms were not gradient-based methods, despite gradient methods being widely used in practice.The authors identify this mismatch as motivation for theoretical study of gradient-based learning.Source: §2 · p. 4
- Several shallow-network recovery results analyze population risk, including work on ReLU units, residual networks, convolutional filters, and no-overlap convolutional networks (Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Du et al., 2017a,b).These studies establish guarantees for gradient-based methods under their respective settings, but use expected rather than empirical loss.Source: §2 · p. 4
- Prior empirical-loss analyses established local linear convergence for smooth activations, while ReLU's nonsmoothness limits their applicability; one-neuron projected gradient descent also needs a constraint based on the unknown true weight.The smooth-activation studies include Zhong et al. (2017), Soltanolkotabi et al. (2017), and Fu et al. (2018).Source: §2 · p. 4
- Unlike Ge et al. (2017), this work analyzes ReLU networks with the unmodified square-loss objective, but requires a special initialization.Ge et al. modify the objective to show it has no spurious local minima.Source: §2 · p. 5
3 Problem Setup and Algorithm
The section formulates recovery of the teacher parameters by minimizing empirical loss and analyzes gradient descent for that objective. It contrasts the empirical objective available from training data with a population loss used in the analysis, and the algorithm does not require resampling.
3 Problem Setup and Algorithm
- The population loss is the analysis counterpart to the empirical objective for learning the one-hidden-layer ReLU network.The passage defines this loss to facilitate the later analysis.Source: §3 · p. 5
- The target is recovery of the unknown parameter matrix from empirical loss, since training data—not the population distribution—is available in practice.The corresponding population loss is introduced for the later analysis.Source: §3 · p. 5
- Gradient descent minimizes the empirical loss using an initial estimator, step size, and fixed iteration count, without resampling the training data.The analysis links avoiding resampling to a uniform convergence bound between empirical and population-loss gradients.Source: §3 · pp. 5–6
4 Main Theory
The theory gives a local linear-convergence guarantee for gradient descent under stated initialization, step-size, and sample-size conditions. Tensor initialization supplies a suitable starting point, and convergence is limited by a statistical error.
4 Main Theory
- For standard Gaussian inputs and teacher-network outputs, if ||W0−W*||F ≤ cσK/(λκ^3K^2) and η ≤ 1/(c2κK^2), Algorithm 1 is guaranteed to converge linearly to W*.Source: §4 · pp. 6–7
- The estimation error has optimization and statistical components, and the statistical error depends on sample size, input dimension, neuron count, and problem-specific parameters.The stated error also depends on the noise norm and parameters of the teacher network.Source: §4 · p. 7
- Tensor initialization can provide a starting estimator satisfying the local-neighborhood condition required by the convergence theorem.The cited initialization result gives a sample-size requirement involving the target approximation error, dimension, condition number, and neuron count.Source: §4 · p. 7
- The combined tensor-initialization and gradient-descent procedure is stated to learn the network with linear convergence up to statistical error.The theorem's statistical error bounds how closely the procedure can estimate the parameters.Source: §4 · p. 7
5 Proof of the Main Theory
The proof combines local curvature and smoothness of the population loss with uniform control of the empirical gradient near the teacher parameters. An induction then shows that gradient descent stays in the required neighborhood.
5 Proof of the Main Theory
- Local strong convexity and smoothness of the population loss, together with a uniform empirical-gradient convergence bound, supply the main ingredients for the theorem.The gradient bound is established for parameters near W*, while the curvature and smoothness lemmas apply locally around W*.Source: §5 · p. 8
- The proof uses a local Hessian lower bound and a Lipschitz bound on the population gradient to control the update.The stated local Lipschitz parameter scales with the condition number and the number of hidden neurons.Source: §5 · p. 8
- The induction proves that each gradient-descent update remains within the neighborhood required by the theorem, provided the current iterate is already there.The proof bounds the population-gradient and empirical-gradient contributions to the update error.Source: §5 · pp. 8–9
- Figure 2 covers convergence comparisons across initializations, recovery probability versus N/d, and estimation error versus rescaled sample size.Its caption says the recovery-probability plot illustrates sample complexity scaling linearly with d.Source: Figure 2 · p. 10
6 Experiments
Synthetic experiments test convergence, sample complexity, and noisy estimation for one-hidden-layer ReLU networks. Their results align with the theory, with tensor initialization converging faster early than random initialization.
6 Experiments
- Synthetic tests use standard-Gaussian inputs and a five-neuron teacher network with condition number 2.The teacher parameters are constructed with smallest and largest singular values 1 and 2.Source: §6 · p. 10
- Both tensor and random initialization achieve linear convergence after some iterations, while tensor initialization converges faster early.The comparison uses noiseless data with d=10 and N=5000.Source: §6 · p. 10
- Linear sample complexity in dimension d is supported by the successful-recovery results for tensor initialization followed by gradient descent.The reported recovery-probability results agree with the theory.Source: §6 · p. 11
- eO(d/N) is the observed order of the statistical rate for the final estimation error in the noisy setting.The experiments average results over 10 trials for each of three dimensions.Source: §6 · p. 11
7 Conclusions and Future Work
The paper studies empirical-risk minimization for one-hidden-layer ReLU networks and proves a linear-rate recovery guarantee up to statistical error with sample complexity eO(d). It identifies deeper networks, more general input distributions, and random initialization as directions for future work.
7 Conclusions and Future Work
- Gradient descent can recover ground-truth parameters at a linear rate up to statistical error with sample complexity eO(d).The conclusion specifies that the results concern shallow neural networks.Source: §7 · p. 11
- The authors suggest studying guarantees for deeper networks as a challenging future direction.They also say the shallow-network analysis may shed light on learning deep networks.Source: §7 · p. 11
- Future work includes relaxing the Gaussian-input assumption and studying guarantees for random-initialized gradient descent.Source: §7 · p. 11
A.1 Proof of Lemma 5.1
The appendix supplies local Hessian bounds and smoothness arguments used in the proofs. It also tracks extreme column norms when establishing the smoothness parameter.
A.1 Proof of Lemma 5.1
- Lemma A.1 lower-bounds the population-loss Hessian at W*, with µ=c/(λκ^2).Source: §A.1 · p. 11
- Lemma A.2 bounds Hessian variation as ρ-Lipschitz within ∥W−W*∥F≤σK/2, with ρ=cκK^2/σK.Source: §A.1 · p. 12
A.2 Proof of Lemma 5.2
- The proof tracks wmax and wmin, the columns of W with largest and smallest ℓ2 norms, respectively.Source: §A.2 · p. 12
- Under ∥W−W*∥2≤σK/2, the Lemma 5.2 proof uses Weyl bounds on W’s extreme singular values to derive a smoothness parameter L.Source: §A.2 · p. 12
A.3 Proof of Lemma 5.3
The proof controls the empirical gradient using covariance and error-matrix terms. Auxiliary lemmas provide high-probability local bounds, while the B.1 calculation derives a Hessian-Lipschitz parameter.
A.3 Proof of Lemma 5.3
- The empirical-gradient analysis uses empirical and population covariance terms together with the error matrix E(W).Source: §A.3 · p. 13
- Within the stated neighborhood of W*, Lemmas A.3–A.4 establish high-probability bounds for covariance deviations and the error term.Source: §A.3 · pp. 13–14
B.1 Proof of Lemma A.2
- The B.1 calculation uses Weyl bounds under ∥W−W*∥2≤σK/2 to obtain the Hessian-Lipschitz parameter ρ.Source: §B.1 · p. 14
B.2 Proof of Lemma A.3
The proofs bound empirical-to-population errors using covering arguments and concentration inequalities. They establish a high-probability uniform bound for Lemma A.3 and develop a related Frobenius-error bound for Lemma A.4.
B.2 Proof of Lemma A.3
- With probability at least 1 − d^-10, the proof establishes a uniform bound over W in the radius-r ball around W* for the empirical-to-population error.It decomposes the error through a ζ-net and bounds deviations on the net and between net points.Source: §B.2 · pp. 15, 18
B.3 Proof of Lemma A.4
- The Lemma A.4 proof bounds each error-matrix column using a sphere net and Bernstein-type concentration for products of independent centered sub-Gaussian noise and covariates.The noise has sub-Gaussian norm ν, and the projected covariates have sub-Gaussian norm at most C.Source: §B.3 · pp. 19–20
C Additional Definitions and Lemmas
- The appendix defines sub-Gaussian vectors through their one-dimensional marginals and sub-exponential variables through moment growth, then states concentration and covering lemmas used in the proofs.The cited background includes bounds for independent sub-Gaussian rows, sphere and ball covering numbers, and centered sub-exponential sums.Source: C Additional Definitions and Lemmas · p. 22