Recovery Guarantees for One-hidden-layer Neural Networks

Kai Zhong; Zhao Song; Prateek Jain; Peter L. Bartlett; Inderjit S. Dhillon

Source-linked AI summary

Recovery Guarantees for One-hidden-layer Neural Networks

Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon

arXiv:1706.03175v1Jun 10, 2017cs.LGcs.DSstat.ML

TL;DR

The paper addresses recovery of ground-truth parameters in one-hidden-layer neural-network regression, where non-convexity makes learning guarantees difficult. It derives activation conditions for local curvature, uses tensor initialization to enter that region, and applies gradient descent to obtain dimension-efficient recovery guarantees.

Problem
The paper asks how to recover underlying one-hidden-layer neural-network parameters under assumptions including Gaussian inputs and linearly independent hidden-neuron parameters.
Method
The method combines activation-function conditions yielding local positive definiteness, tensor initialization into that region, and gradient descent for smooth homogeneous activations.
Results
Sample complexity is linear in input dimension and logarithmic in precision, while computational complexity is linear in dimension for the stated smooth homogeneous setting.
Takeaways & Limitations
The paper provides recovery guarantees for 1NNs with dimension-efficient sample and computational complexity under its stated assumptions.
Takeaways & Limitations
The analysis assumes Gaussian inputs, noiseless data, k ≤ d, and activation functions satisfying the paper’s specified properties.

Abstract

from arXiv · show

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to $\mathit{local~strong~convexity}$ in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show $\mathit{local~linear~convergence}$ guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity $ d \cdot \log(1/ε) \cdot \mathrm{poly}(k,λ)$ and computational complexity $n\cdot d \cdot \mathrm{poly}(k,λ) $ for smooth homogeneous activations with high probability, where $d$ is the dimension of the input, $k$ ($k\leq d$) is the number of hidden nodes, $λ$ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, $ε$ is the targeted precision and $n$ is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity $\mathit{linear}$ in the input dimension and $\mathit{logarithmic}$ in the precision.

1 Introduction

The paper studies parameter recovery for one-hidden-layer neural networks under non-convex optimization, developing local curvature, initialization, and convergence guarantees with dimension-efficient complexity.

Parameter recovery targets the underlying ground-truth parameters, up to equivalent permutations, rather than developing a new generalization analysis.Exact parameter recovery also guarantees generalization performance within the stated setting.
The proposed 1NN algorithm has sample complexity eO(d) and computational time eO(dn) under mild assumptions.
Activation-function properties yield positive-definite Hessians near ground truth and local linear convergence for smooth activations using gradient descent.
A tensor method initializes parameters inside the local positive-definiteness region, reducing dimension dependence from cubic to linear.
Combining tensor initialization with gradient descent gives complexity linear in dimension and logarithmic in precision for smooth homogeneous activations.

2 Related Work

Prior work addresses neural-network expressivity, optimization, generalization, recovery, and improper learning, but the paper positions its method as an efficient recovery approach under explicit assumptions.

Expressivity results explain approximation and depth advantages, but expressive power alone does not guarantee that target functions can be learned.
Many optimization results study over-parameterized networks, while the paper instead seeks efficient recovery of underlying ground-truth parameters.
The paper distinguishes its approach from generalization-analysis and improper-learning methods that rely on difficult-to-justify assumptions or exponential complexity.
Recovery guarantees for neural networks require assumptions; this paper assumes Gaussian inputs, noiseless data, and linearly independent hidden-layer parameters.
Compared with related 1NN analyses, the paper allows learning second-layer parameters and requires linear independence rather than orthogonality of first-layer weights.

3 Problem Formulation

The paper formulates noiseless 1NN regression under Gaussian inputs and asks how many samples suffice to recover the underlying parameters, imposing structural and activation-function assumptions.

Samples are drawn independently from an underlying distribution over input-output pairs in R^d × R.
The problem asks how many samples suffice to recover the underlying parameters of a one-hidden-layer neural network.
The setting assumes standard normal inputs, noiseless data, input dimension at least the number of hidden nodes, and activation functions satisfying specified properties.
The analysis extends to zero-mean Gaussian inputs with positive-definite covariance after covariance estimation and input transformation, with some loss of accuracy.
ReLU, leaky ReLU, squared ReLU, sigmoid, tanh, and erf satisfy the three properties, whereas linear and quadratic functions fail required properties.

4 Positive Definiteness of Hessian

The paper analyzes the empirical-risk Hessian near ground truth, establishes local positive definiteness under activation and sampling conditions, and connects tensor initialization with gradient-descent convergence.

For homogeneous activations, tensor methods can exactly recover the discrete second-layer parameters using finite samples.
The Hessian is shown to be positive definite near the global optimum when the activation satisfies Properties 3.1–3.3 and enough independent samples are available.
The local guarantee applies within a neighborhood of W∗ whose size depends polynomially on conditioning and activation-related parameters.
The quantity ρ(σk) controls positive definiteness: popular nonlinear activations have positive ρ(σk), while linear and square activations yield rank-deficient Hessians.
The overall algorithm combines tensor initialization with gradient descent to obtain global convergence guarantees.
For smooth activations, gradient descent achieves local linear convergence when iterates start sufficiently close to ground truth and use resampled independent data.

5 Tensor Methods for Initialization

The paper uses moment tensors and a dimension-reduced decomposition to initialize hidden-layer parameters near the region where recovery guarantees apply.

Tensor initialization: Tensor methods recover W* approximately and v* exactly for homogeneous activations.The method relies on noiseless data, Gaussian inputs, and activation-function conditions ensuring usable moments.
Tensor construction: P2 and P3 are constructed from the first non-zero moments and are rank-k under the activation assumptions.Their empirical versions are estimated from samples for subsequent decomposition.
Complexity: Dimension reduction lowers tensor estimation and decomposition costs relative to the cubic-in-dimension baseline.The original tensor approach can require Ω(d^3) samples and Ω(d^3) decomposition time.
Dimension reduction: The algorithm first estimates the hidden-weight subspace from P2, then projects P3 into a k-dimensional tensor space.This replaces decomposition of a d × d × d tensor with decomposition in R^k×k×k.
Guarantee: Theorem 5.6 provides initialization using |S| ≥ ϵ^-2 · d · poly(t, k, κ, log d) samples and |S|k · eO(d) time.The resulting initialization succeeds with probability at least 1 − d^-Ω(t).

6 Global Convergence

Combining tensor initialization with local positive definiteness of the Hessian yields a globally converging algorithm for smooth homogeneous activations.

Algorithm: The global algorithm combines Hessian positive definiteness near the optimum with tensor initialization.Tensor initialization places the parameters in the region where the local convergence result applies.
Guarantees: Theorem 6.1 uses |S| ≥ d log(1/ϵ)·poly(log d, t, k, λ) samples and runs in |S| · d · poly(log d, k, λ) time.The guarantee holds with probability at least 1 − d^-Ω(t).

7 Numerical Experiments

Synthetic experiments examine recovery, tensor initialization, and initialization strategies for gradient descent under squared-ReLU networks.

Experimental setup: The experiments use squared ReLU, a smooth homogeneous activation, with synthetic Gaussian-distribution data.They set W* through an SVD-based construction and use κ = 2 and k = 5.
Recovery: The least sample count achieving 100% recovery is approximately proportional to the input dimension.Recovery is evaluated across dimensions d = 10, 20, · · · , 100 and sample sizes n = 1000, 2000, · · · , 10000.
Tensor initialization: For fixed dimension, increasing the sample count improves tensor initialization, while matching initialization error requires samples approximately proportional to dimension.Initialization error is plotted against sample count under different dimensions.
Gradient descent: Tensor initialization followed by gradient descent is fastest, whereas random initialization of both W and v does not converge in the reported comparison.The comparison fixes d = 10, k = 5, and n = 10000.

8 Conclusion

For smooth homogeneous activations, tensor initialization followed by gradient descent yields a globally converging recovery procedure with linear dimension dependence and logarithmic precision dependence.

Tensor initialization followed by gradient descent provides a globally converging algorithm for smooth homogeneous activation functions.
The analysis uses Gaussian-distribution notation, indicator functions, identity matrices, asymptotic notation, and standard matrix operations.
The paper’s notation defines tensor products, tensor flattenings, matrix norms, and related linear-algebraic operations used throughout the analysis.
The paper introduces auxiliary facts and lemmas for bounding matrix products, Gaussian expectations, singular values, and distances between subspaces.

B.2 Matrix Bernstein

The paper develops a modified matrix Bernstein argument for random matrices that may be unbounded but are bounded with high probability, then derives error bounds for empirical matrix estimates.

The modified matrix Bernstein lemma handles random matrices that are not almost surely bounded or subexponential but are bounded with high probability.
n ≥ (18t log d) · (ν + ∥B∥^2 + m∥B∥ϵ)/(ϵ^2∥B∥^2) and γ ≤ (ϵ∥B∥/(2L))^2 ensure the stated concentration guarantee.
The proof truncates matrices using an event-controlled threshold, separates truncation and concentration errors, and applies matrix Bernstein to the truncated terms.
For symmetric rank-one random matrices formed from Gaussian samples, the corollary gives analogous sample-size and truncation-probability conditions.

C Properties of Activation Functions

The paper identifies activation-function properties that yield positive-definite Hessians near the ground truth, establishes local convergence for smooth activations, and bounds empirical Hessian errors.

Properties of Activation Functions: ReLU, leaky ReLU, squared ReLU, sigmoid, tanh, and erf satisfy the distilled activation properties, whereas linear and quadratic activations fail specified properties.
Properties of Activation Functions: For smooth non-decreasing nonlinear activations with bounded symmetric first derivatives, ρ(σ) > 0 for every σ.
Local Strong Convexity: Theorem D.1 bounds the Hessian spectrum near the ground truth with sufficiently many samples and parameters sufficiently close to W*.
Local Linear Convergence: Gradient descent requires resampling at each iteration because iterates computed from a sample set depend on those same samples.
Local Strong Convexity: The population Hessian is positive definite at the ground-truth parameters under the distilled activation properties.
Error Bound of Hessians near the Ground Truth for Smooth Activations: For smooth activations, Lemma D.8 bounds empirical-population Hessian differences when ∥W − W*∥ ≤ σk/2, with a sample condition involving κ(W*).

D.4 Error Bound of Hessians near the Ground Truth for Non-smooth Activations

The section bounds Hessian errors near the ground truth for non-smooth activations, including parameters that may depend on the samples. These bounds support local analysis without requiring activation smoothness.

Non-smooth analysis cannot use bounded second derivatives, so it instead controls Hessian blocks through properties of the activation and sample moments.The proof treats diagonal and off-diagonal blocks separately and uses concentration bounds for matrix-valued quantities.
The proof handles exceptional points of piece-wise linear activations by bounding the probability that random projections cross them.This controls the contribution of discontinuous or non-smooth second-derivative behavior.
The analysis bounds Hessian differences near the ground truth even when the current parameters depend on the samples.The comparison is made to an anchor point independent of the samples, provided the parameters are sufficiently close.

E.2 Main Result for Tensor Methods

This section presents tensor initialization for homogeneous activations. The method estimates moments, recovers the hidden-weight subspace and factors, then solves auxiliary systems to recover magnitudes and signs.

The final recovery stage estimates weight magnitudes and signs through auxiliary first- and second-order moments and perturbed linear systems.The resulting linear-system solutions are robust to small perturbations in the estimated subspace, moments and tensor factors.
The initialization procedure uses eO(d) + eO(k^3) samples, while the cited component estimates are linear in dimension for constant error.The third-order tensor estimation contributes the polynomial dependence on k.
The method is restricted to homogeneous activations because the final recovery step is not implemented for general non-homogeneous activations.The underlying lemmas apply more broadly, but the complete theorem is stated only for homogeneous functions.

E.3.1 Error Bound for the Second-order Moment in Different Cases

The section develops concentration bounds for empirical second-order moments and their power-method subspace estimates. These estimates use linear sample complexity in the input dimension under activation and moment assumptions.

The moment analysis treats each hidden-node component separately and controls matrix norms using concentration inequalities for Gaussian inputs.The component matrices are symmetric, allowing several norm bounds to be reduced to one representative case.
Linear sample complexity in d suffices to approximate the empirical second-order moment to a prescribed precision.Lemma E.5 states the bound under Property 3.1 and Assumption 5.3.
Power iteration recovers the subspace spanned by the ground-truth hidden weights after O(log(1/ϵ)) iterations when the empirical moment is sufficiently accurate.The guarantee uses the spectral gap σ_k(P2) and compares the estimated and true projectors.
The resulting subspace estimate supports the later reduced third-order moment construction and tensor initialization guarantees.The subspace approximation is the input to the subsequent reduced tensor estimation stage.
The subspace procedure separates positive and negative eigenvalue components before combining their eigenvectors into the estimated hidden-weight subspace.The shifted matrices C I + bP2 and C I − bP2 are used to identify the relevant eigenvectors by magnitude.

E.4.2 Final Error Bound for the Reduced Third-order Moment

This section bounds estimation error for the reduced third-order moment and the subsequent linear systems used in tensor initialization. Together, these results establish robustness of the final parameter-recovery stage.

The reduced third-order moment can be estimated to small precision with polynomial dependence on k and high probability.Lemma E.10 obtains the bound by matricizing the tensor and applying matrix Bernstein concentration.
The tensor estimate is combined with first- and second-order moment estimates to recover unknown parameter quantities through perturbed linear systems.The later lemmas bound errors in the solutions of both systems under perturbations of moments and estimated factors.
Robustness follows from controlling perturbations relative to the smallest singular value and condition number of the underlying systems.The perturbation lemma bounds solution error when matrix and right-hand-side errors remain sufficiently small.
The first linear system estimates quantities associated with the first-order moment, while the second uses vectorized rank-one factors for the second-order moment.The constructions use matrices whose columns encode estimated weight directions and their outer products.