Learning One-hidden-layer Neural Networks with Landscape Design

Rong Ge; Jason D. Lee; Tengyu Ma

Source-linked AI summary

Learning One-hidden-layer Neural Networks with Landscape Design

Rong Ge, Jason D. Lee, Tengyu Ma

arXiv:1711.00501v2Nov 1, 2017cs.LGcs.DSmath.OCstat.ML

TL;DR

The paper studies how to design objectives that enable efficient, guaranteed optimization for learning one-hidden-layer neural networks. It analyzes standard population risk, designs a new objective with a benign landscape, and shows stochastic gradient descent can converge to an approximate global minimum under the stated setting.

Problem
Standard population risk can be empirically difficult to optimize because its landscape may contain spurious local minima.
Method
The paper analytically characterizes standard population risk and designs a non-convex objective G whose local minima correspond to structured ground-truth solutions.
Results
Stochastic gradient descent with fresh samples converges to an approximate global minimum B that is ε-close to a global minimum in time poly(d, 1/ε).
Takeaways & Limitations
The designed objective has no spurious local minima, and its global minima correspond to the ground-truth parameters up to permutation and fixed transformation.
Takeaways & Limitations
The results assume Gaussian input distributions, and extending them to other input distributions remains an open problem.

Abstract

from arXiv · show

We consider the problem of learning a one-hidden-layer neural network: we assume the input $x\in \mathbb{R}^d$ is from Gaussian distribution and the label $y = a^\top σ(Bx) + ξ$, where $a$ is a nonnegative vector in $\mathbb{R}^m$ with $m\le d$, $B\in \mathbb{R}^{m\times d}$ is a full-rank weight matrix, and $ξ$ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. Inspired by the formula, we design a non-convex objective function $G(\cdot)$ whose landscape is guaranteed to have the following properties: 1. All local minima of $G$ are also global minima. 2. All global minima of $G$ correspond to the ground truth parameters. 3. The value and gradient of $G$ can be estimated using samples. With these properties, stochastic gradient descent on $G$ provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity result and validate the results by simulations.

1 Introduction

The paper studies how to design neural-network models and objectives with favorable optimization landscapes, focusing on one-hidden-layer networks under Gaussian inputs. It analyzes standard squared-loss risk, then constructs an objective whose minima recover the ground truth and support sample-based stochastic optimization.

The paper asks how model and objective design can enable efficient optimization with guarantees for one-hidden-layer neural networks.
The proposed objective G has only global local minima, with global solutions corresponding to ground-truth parameters up to permutation and fixed transformations.
The setup assumes Gaussian inputs, ground-truth network parameters, additive noise, m ≤ d, and nonnegative output weights.
The standard squared-loss population risk can have spurious local minima, preventing stochastic gradient descent from reaching the ground truth even with infinite data.
The population-risk formula reveals an implicit simultaneous decomposition of finitely many low-rank tensors with shared components.
G’s value and gradient are sample-estimable, enabling unconstrained stochastic gradient descent and a polynomial finite-sample surrogate guarantee.

2 Main Results

The paper analyzes one-hidden-layer neural-network learning through tensor-decomposition structure, then designs an objective with a provably benign landscape and sample-based optimization guarantees.

Tensor-decomposition connection: The natural ℓ2 population risk implicitly decomposes multiple low-rank tensors of different orders with shared components.For each order k, the objective targets a rank-m tensor built from the ground-truth weights.
Challenges with the natural objective: Stochastic gradient descent on the natural population risk can fail to reach zero test error because the landscape appears to contain spurious local minima.This failure is reported even with zero noise, fresh samples, and an orthogonal ground-truth matrix.
Landscape guarantees: The designed objective G has local minima exactly at signed and permuted versions of the ground-truth matrix, so every local minimum is global.The result assumes an orthogonal B⋆, suitable activation conditions, and regularization parameters satisfying the theorem’s bounds.
Optimization and sample complexity: Stochastic gradient descent on G reaches an approximate global minimum in polynomial time, and polynomially many samples preserve the relevant landscape properties with high probability.The approximate solution is close to a global minimum, after which the output weights can be estimated by linear regression.

3 Overview: Landscape Design and Analysis

The paper designs G(·) from sample-estimable polynomial forms so its landscape avoids spurious local minima and recovers the ground-truth parameters up to symmetries.

Objective design: The design starts from an analytic population-risk formula and selects an objective family with unbiased sample estimators.Hermite-based constructions provide access to weighted powers and symmetric polynomials of parameter inner products.
Objective design: The natural squared-loss objective is difficult because it has bad local minima and must respect permutation invariance.Permuting rows of B and the corresponding coefficients in a leaves the network unchanged.
Landscape construction: The unweighted tensor-decomposition objective P has only permutation and sign-flip copies of B⋆ as local minima under unit-row constraints.Its row-wise optimization reduces to an eigenvector problem with no spurious local minima.
Landscape construction: The regularizer R(B) pushes rows toward target vectors, while sufficiently small µ makes P′(B)+R(B) free of spurious local minima.R(B) is introduced to remove spurious minima associated with rows that combine several ground-truth rows.
Unconstrained objective: The unconstrained objective adds S(B) to approximately enforce row norms and extends to non-orthogonal settings without pre-estimating B⋆B⋆⊤.S(B) slightly changes global minima, so λ is chosen large enough to keep row norms close to one.
Unconstrained objective: The final objective G(·) uses only B as variables, with a⋆ estimated after recovering B.Its analysis is more delicate because R(B) and S(B) are degree-4 polynomials.

4 Analytic Formula for Population Risks

This section derives Gaussian population-risk formulas using Hermite expansions, then constructs sample-estimable functions for the polynomial terms needed to analyze G(·).

4.1 Basics on Hermite Polynomials: Normalized probabilists’ Hermite polynomials form a complete orthonormal basis under the Gaussian-weighted inner product.Hermite coefficients are obtained by inner products with the normalized polynomials.
4.1 Basics on Hermite Polynomials: For correlated Gaussian variables, expectations of Hermite-polynomial products are computable through their correlation.This property underlies the subsequent Fourier/Hermite calculations.
4.1 Basics on Hermite Polynomials: For Gaussian projections onto unit vectors, expanding σ and γ in the Hermite basis expresses their interaction through corresponding Hermite coefficients.Claim 4.3 is proved by expanding the two functions in the Fourier basis.
4.2 Analytic Formula for population risk f and f′: The population risk fγ has an analytic formula for predictors ˆy = a⊤γ(Bx), with contributions weighted by the Hermite coefficients of σ and γ.Choosing γ=σ gives Theorem 2.1, while a second-order/fourth-order Hermite choice gives Theorem 2.2.
4.3 Analytic Formula for population risk G: The paper also derives an analytic formula for the population risk G(·), which supplies the expression used in the landscape analysis.The formula is stated in Theorems 4.5 and 4.6 and follows from the preceding Gaussian identities.
4.3 Analytic Formula for population risk G: The derived formulas support sample-based estimation of the polynomial objective terms used by G(·).The section extends the Gaussian identities to vectors with non-unit scaling where needed.
4.3 Analytic Formula for population risk G: Lemma 4.9 and its proof establish the product extraction identity used term-by-term in Theorem 4.5.The identity follows from expanding squared inner products of v+w and v−w.

5 Landscape of Population Risk G(·)

The landscape analysis shows that, under parameter conditions, G(·) has structured local minima, strict saddle curvature, and approximate-minimum guarantees that identify the true parameters up to permutation and scaling.

Landscape theorem: By rotational invariance, the analysis assumes B⋆=I and studies a generalized objective Gα,β,µ with nonnegative parameters.The generalized theorem uses αmax/αmin and conditions on µ and λ.
Landscape theorem: Every local minimum of Gα,β,µ is exactly DP, where P is a permutation matrix and D has prescribed diagonal entries.The theorem states the converse as well: every such matrix is a local minimum.
Landscape theorem: Every saddle point has strictly negative curvature, with a Hessian eigenvalue bounded above by −τ0.The curvature scale depends on µ, β, κα, and d.
Approximate minima: Approximate local minima satisfy an entrywise error bound and are close to a scaled permutation of the ground-truth matrix.The decomposition is B=DP+E, with E controlled by the approximate gradient and curvature conditions.
Row-wise analysis: The row-wise proof first shows that a locally optimal row is close to a scaled basis vector, then that different rows select different basis vectors.Together these steps imply that B is a permutation matrix up to row scaling.
Row-wise analysis: The row analysis uses gradient and Hessian conditions, significant-coordinate sets, and negative-curvature arguments to exclude rows with multiple large coordinates.Norm bounds and coefficient comparisons further constrain possible local minima.
Row-wise analysis: Strong regularization keeps local-minimum row norms bounded and helps establish the final scaling characterization.The analysis gives coarse bounds between 1/2 and 2 before proving norms are close to one.
Conclusion: Setting ε=τ=0 shows that all local minima have the DP form and share the same objective value, so they are global minimizers.This completes the no-spurious-local-minima result for the generalized objective.

6 Simulation

Simulations show that the proposed activations and objective enable SGD to approach the ground-truth parameters, while standard ReLU training can fail without over-parameterization.

Activation-based learning: The ˆσ2h2 + ˆσ4h4 activation empirically recovers B⋆ even when labels are generated by a ReLU network.This supports the conjecture based on the population-risk formula in Equation (2.3).
Experimental setup: The experiments use d = 50, B⋆ = I_d, a⋆ = 1, noiseless ReLU-generated data, and fresh samples at every SGD iteration.The plotted error is the expected population error on a fresh batch.
Standard ReLU baseline: Without over-parameterization, ReLU-based SGD does not converge to zero test error or the ground-truth parameters in the reported experiments.The final step size is below 10^-9, supporting that the nonzero objective value is not attributed to SGD variance.
Activation-based learning: SGD with the ˆσ2h2 + ˆσ4h4 activation converges to the ground-truth parameters when projected onto matrices with row norm 1.The plotted loss also reaches the global-minimum value after subtracting the constant term in equation (2.7).
Objective G: Using G(B), the iterates converge to B⋆, although parameter error can rise and fall near a saddle point before reaching a global minimum.Figure 3 reports test loss and parameter-space error measured by equation (6.1).
Experimental setup: The G(·) loss requires a substantially larger batch size of 262144 than 8192 for ˆσ2h2 + ˆσ4h4 and 256 for ReLU.The larger batch is used to reduce variance in gradient estimation.

7 Conclusion

The paper concludes that its population-risk analysis motivates an objective with no spurious local minima, while identifying Gaussian inputs and a conjectural extension as limitations.

Conclusion: The standard ℓ2 population risk is analyzed explicitly and may converge empirically to spurious local minima.The paper then designs a novel population loss guaranteed to have no spurious local minimum.
Conclusion: The authors hope their techniques will help characterize and design optimization landscapes in other settings.
Limitations: The claim that αf2 + βf4 has no spurious local minimum for reasonable constants and ground-truth parameters in general position remains a conjecture supported empirically.
Limitations: The results assume Gaussian input distributions, and extending them to other input distributions is identified as an open problem.

A Handling Non-Orthogonal Weights

For non-orthogonal weight vectors, the paper uses a linearly transformed variant of the objective while preserving the relevant local-minimum structure.

Non-orthogonal weights: When the ground-truth weight vectors are not orthonormal, a slight variant of G(B) can still recover B⋆.
Non-orthogonal weights: The objective F(B) is designed to be equivalent to G(B) up to a linear transformation, allowing Theorem 2.3 to characterize its local minima.

A.1 Local Minimum after a Linear Transformation

The appendix establishes how full-rank linear transformations transfer first- and second-order optimality conditions and relate the landscapes of transformed objectives.

Landscape correspondence: A full-rank linear transformation maps local minima and saddle points between the original and transformed objectives.Corresponding gradient norms and Hessian eigenvalues differ multiplicatively according to the transformation’s spectrum.
Landscape correspondence: For g(x) = f(Wx) with full-rank W, first- and second-order optimality conditions hold at x exactly when they hold at y = Wx.
Spectral comparison: The proof compares Hessian Rayleigh quotients through the minimum and maximum singular values of W.
Gradient and Hessian relations: The gradient relation ∇g(x) = W^⊤∇f(Wx) implies that stationary points correspond under a full-rank transformation.
Gradient and Hessian relations: The Hessian transforms as ∇2g(x) = W^⊤[∇2f(Wx)]W, preserving positive-semidefinite second-order conditions under full rank.

A.2 Objective for Non-Orthogonal Weights

The paper transforms the non-orthogonal problem into an orthonormal one using a whitening matrix, then transfers the resulting landscape guarantees back to the original objective.

Objective transformation: The transformed objective is designed in the ground-truth basis and related to the original objective through a linear transformation.The rows of the transformed matrix are linear combinations determined by W, and the two objectives share corresponding local-minimum structure.
Whitening transformation: A whitening transformation built from the weighted Gram matrix makes transformed ground-truth vectors orthogonal.The transformation uses the SVD of M and W = UD^-1/2, yielding orthogonal transformed vectors.
Landscape guarantees: Every local minimum of G has the form B = PDO, with permutation P and sign-scaled diagonal D near ±1.The theorem also characterizes saddle points by strictly negative curvature and approximate local minima by bounded entrywise error.
Landscape guarantees: Every local minimum of F corresponds to an appropriately transformed permutation and sign scaling of B⋆, and all local minima are global.The characterization uses Γ, the weighted ground-truth matrix, and M^-1 to map the result from G back to F.
Approximate recovery: Approximate local minima of F remain close to the corresponding transformed ground-truth solution.The proof transfers gradient and Hessian conditions through W and controls the resulting inverse perturbation.

A.3 Handle Undercomplete Case

When m < d, the objective depends only on the ground-truth row space, so an ℓ2 regularizer is added to eliminate arbitrary orthogonal components while preserving recovery guarantees.

Undercomplete setting: For m < d, the ground-truth vectors span a subspace S, and the unmodified objective depends only on B's projection onto S.Consequently, local optima can contain arbitrary components in S⊥.
Regularization: An additional ℓ2 regularizer is introduced to prevent components in S⊥.The regularization strength δ is chosen to suppress the orthogonal projection without substantially changing the local optima in S.
Recovery analysis: Because B is rectangular in the undercomplete case, the proof uses pseudo-inverses, whose products represent identity and projection onto the row span.This replaces ordinary inverses when restricting the analysis to S.
Regularization: A small gradient bounds the orthogonal component by ∥PS⊥B∥F ≤ ε/δ.This follows because the unregularized objective has zero gradient in S⊥, while the regularizer contributes δB there.
Recovery analysis: The analysis separates B into its S and S⊥ components and applies the non-orthogonal landscape theorem to the S component.Matrix perturbation arguments then combine the in-subspace recovery with the small orthogonal residual.

B Recovering the Linear Layer

Once the hidden-layer weights are close to B⋆ up to permutation and sign, the paper recovers the nonnegative linear coefficients through empirical correlations and matrix inversion.

Recovery algorithm: For non-orthogonal rows, the algorithm uses the inverse of BB⊤ to account for cross-row correlations.The paper notes that linear regression on σ(Bx) would also recover the coefficients, but chooses this procedure for ease of analysis.
Recovery algorithm: The coefficient-recovery procedure computes empirical correlations u_i = 2 Ê[y⟨x, b_i⟩] and solves a linear system using BB⊤.The resulting estimates are sign-corrected to recover the nonnegative coefficients.
Recovery guarantees: If B is spectrally δ-close to B⋆ up to permutation and sign, coefficient and weight estimates achieve a bounded recovery error.Lemma B.2 provides the spectral-norm setting, while the row-wise version gives an ℓ∞ coefficient bound proportional to δa⋆max.
Recovery guarantees: Pseudo-inverse perturbation shows that coefficient estimates inherit permutation and sign transformations from the hidden-layer estimate, plus an error term.After correcting signs, the remaining coefficient error is controlled by the perturbation of the inverse.

C Sample Complexity

The paper establishes polynomial sample complexity by proving uniform convergence of empirical gradients and Hessians, while excluding large-norm points from approximate local minima.

Sample complexity: Polynomially many samples suffice to find the desired solution with high probability.The authors explicitly state that the polynomial dependence was not optimized.
Uniform convergence: Uniform convergence transfers approximate-local-minimum conditions from the empirical objective to the population objective.The proof controls both gradient and Hessian deviations over the relevant parameter region.
Concentration analysis: Truncation handles Gaussian tails before applying concentration bounds to sample gradients and Hessians.The truncated objective approximates the original objective on matrices whose row norms are at most 2.
Concentration analysis: Bounded-gradient and Hessian convergence results yield high-probability closeness between empirical and population derivatives.The argument applies a prior universal-convergence theorem after establishing boundedness through truncation.
Uniform convergence: Large-norm points cannot be approximate local minima because their empirical gradients have a large outward component.If a row norm is at least 2, the gradient has correlation at least cλ∥b_i∥^4 with that row.
Final guarantee: Combining empirical derivative control with the population landscape theorem characterizes approximate empirical minima near permuted and sign-scaled ground truth.The final guarantee expresses the estimate as a structured solution plus bounded error.

D Spurious Local minimum for function P ′

The section constructs an example in which P′ has a spurious local minimum, using d = 4 and a perturbation analysis showing the objective cannot decrease locally.

d = 4, with true vectors given by standard basis vectors and a⋆_1 = 1, while a⋆_2, a⋆_3, and a⋆_4 equal 2 + δ.
The candidate spurious local minimum sets b_1 = b_2 = e_1 = b⋆_1, yielding P′(B) = 1 with only the corresponding nonzero term contributing.
A local perturbation changes b_1 and b_2 away from e_1 while constraining ε_1, ε_2 and selected coordinates of b_3 and b_4.
Because the analyzed terms are disjoint, the perturbed objective expands into separate contributions involving ε_1 and ε_2.
P′(B′) ≥ 1 for sufficiently small ε after removing higher-order terms, so B is a local minimum of P′ despite being spurious.