PaperlayerView exact revision on arXiv

Source-linked AI summary

Global optimality conditions for deep neural networks

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

arXiv:1707.02444v3cs.LGmath.OCstat.ML

TL;DR

Deep neural-network training is nonconvex, and global optimization can be intractable, while existing conditions for global minima may require restrictive widths. The paper derives necessary and sufficient, efficiently checkable criteria for deep linear networks and extends sufficient conditions to nonlinear networks in function space; the criteria classify linear-network critical points as global minima or saddles.

  • Problem

    Deep-network training is nonconvex and global optimization is NP-Hard in the worst case, while some prior global-minimum criteria require restrictive layer-width conditions.

    Source: §1 · p. 1

  • Method

    The paper derives necessary and sufficient global-optimality conditions for deep linear networks and extends the results to sufficient conditions for nonlinear networks in function space.

    Source: §1.1 · p. 2

  • Results

    The deep-linear theorems partition critical points into sets containing only global minima or only saddles, with efficiently checkable conditions for distinguishing them.

    Source: §2.2 · p. 3

  • Takeaways & Limitations

    The conditions provide an efficient test for global optimality in these nonconvex deep-linear settings, unlike general nonconvex optimization.

    Source: §2.2 · p. 3

    The nonlinear results are stated in function space and do not imply that every critical point of a fixed sigmoid or arctan network is globally optimal.

    Source: §4.2 · p. 8

Abstract

from arXiv · show

We study the error landscape of deep linear and nonlinear neural networks with the squared error loss. Minimizing the loss of a deep linear neural network is a nonconvex problem, and despite recent progress, our understanding of this loss surface is still incomplete. For deep linear networks, we present necessary and sufficient conditions for a critical point of the risk function to be a global minimum. Surprisingly, our conditions provide an efficiently checkable test for global optimality, while such tests are typically intractable in nonconvex optimization. We further extend these results to deep nonlinear neural networks and prove similar sufficient conditions for global optimality, albeit in a more limited function space setting.

1 INTRODUCTION

Deep neural networks have achieved broad empirical success, but their nonconvex loss surfaces and global optimization remain difficult to understand. This paper gives checkable global-optimality conditions for deep linear networks and extends sufficient conditions to nonlinear networks in a limited function-space setting.

1 INTRODUCTION

  • Global optimization is a major challenge: training neural networks is nonconvex, and even training a 3-node network to global optimality is NP-Hard in the worst case.Source: §1 · p. 1
  • Prior critical-point criteria can require hidden layers as wide as the training set or rapidly growing parameter counts; another sufficient result assumes parallel subnetworks with identical architectures.The cited width conditions are attributed to Nguyen & Hein (2017), Soudry & Carmon (2016), and Xie et al. (2016); the parallel-subnetwork result is attributed to Haeffele & Vidal (2017).Source: §1 · p. 1
  • Deep linear networks remain nonconvex despite removing nonlinear activations, and prior work established that their local minima are global while other critical points are saddles (Kawaguchi, 2016; Lu & Kawaguchi, 2017).Source: §1 · pp. 1–2

1.1 OUR CONTRIBUTIONS

  • The paper gives necessary and sufficient, efficiently checkable conditions for deep-linear critical points to be global minima, and sufficient conditions for nonlinear networks in function space.The authors contrast their tests with results that only distinguish minima from saddles in principle, and with general nonconvex tests that are intractable.Source: §1.1 · p. 2

2 GLOBAL OPTIMALITY CONDITIONS FOR DEEP LINEAR NEURAL NETWORKS

The section formulates squared-error empirical risk for deep linear networks and characterizes which critical points are global minima. The resulting conditions divide the critical points into global minima and saddles and can be checked efficiently.

2.1 PROBLEM FORMULATION AND NOTATION

  • The network maps the input data through a product of layer-weight matrices, and training minimizes summed squared error over the input-output pairs.Source: §2.1 · p. 2
  • The assumptions include full ranks for XX^T and YX^T, and distinct singular values for YX^T(XX^T)^-1; the latter is for notational simplicity and can be relaxed.Source: §2.1 · p. 2
  • Let k be the minimum width among input, hidden, and output layers; the minimum-width layer determines the maximum possible rank of the full weight product.Source: §2.1 · p. 3

2.2 NECESSARY AND SUFFICIENT CONDITIONS FOR GLOBAL OPTIMALITY

  • When k = min{dx, dy}, every critical point whose full weight product has rank k is global, while every other critical point is a saddle.Source: §2.2 · p. 3
  • When k < min{dx, dy}, global minima additionally require the relevant partial product's column space to equal col(Uhat); the resulting conditions distinguish minima from saddles efficiently.The theorems also extend the population-risk result of Hardt & Ma (2017), removing its positive-determinant assumption on the true linear model.Source: §2.2 · p. 3

3 ANALYSIS OF DEEP LINEAR NETWORKS

The analysis reduces deep-linear optimization to a rank-constrained matrix problem, then uses its optimum and the layerwise derivatives to prove the full-width case of the global-optimality theorem.

3.1 SOLUTIONS OF THE RELAXED PROBLEM

  • A rank-at-most-k relaxation has the same loss as a network whose weight product is its matrix variable, so a network attaining the relaxed optimum is globally optimal.Source: §3.1 · p. 4
  • For k < min{dx, dy}, the relaxed problem is nonconvex because of its rank constraint, but its optimum is the projection of YX^T(XX^T)^-1 onto col(Uhat).Source: §3.1 · p. 4

3.2 PARTIAL DERIVATIVES OF L(W)

  • The proof uses the partial derivatives of the risk with respect to each layer matrix, whose formula is established in Lemma 3.2.Source: §3.2 · p. 4

3.3 PROOF OF THEOREM 2.1

  • In the full-width case, critical points in the specified set have a weight product equal to the unique relaxed optimum and are global minima; critical points outside the full-rank set are saddles.The proof extends the saddle-point conclusion to the dx > dy case using Lemma B.1.Source: §3.3 · p. 5

1. Consider

For the narrower-bottleneck case, the proof characterizes critical points through residual orthogonality and identifies the subspace alignment needed for global optimality.

3.4 PROOF OF THEOREM 2.2

  • Critical points outside the rank-k set cannot be global minima because the relaxed problem's global optimum has rank k; these points are saddles.Source: §3.4 · p. 6
  • In the rank-k set, a tuple is critical if and only if ApE = 0 and EBp+1 = 0.Source: §3.4 · p. 6
  • A critical point in the rank-k set is globally optimal exactly when the relevant partial-product subspace matches col(Uhat).The proposition states this as col(WH+1 · · · Wp+1) = row(Ap) = col(Uhat).Source: §3.4 · p. 6
  • Consequently, every critical point in V2 is a global minimum, while other critical points in the rank-k set are saddles.Source: §3.4 · p. 7

4 EXTENSION TO DEEP NONLINEAR NEURAL NETWORKS

The section gives sufficient global-optimality conditions for deep nonlinear networks in function space. It formulates squared-error population risk and distinguishes these guarantees from guarantees for fixed network architectures.

4.1 PROBLEM FORMULATION AND NOTATION

  • For squared-error population risk, the target is h*(x) = E[Y | X = x], and matching it almost surely reduces risk to the irreducible variance term C.Source: §4.1 · p. 7
  • The function spaces require differentiable functions that vanish at zero and have sublinear growth, with layer dimensions at least min{dx, dy}.Source: §4.1 · pp. 7–8

4.2 SUFFICIENT CONDITIONS FOR GLOBAL OPTIMALITY

  • Under the respective hypotheses of Theorems 4.1 and 4.2, every function-space critical point is a global minimum.Proposition 4.3 establishes that each theorem's conditions are satisfied by at least one global minimum.Source: §4.2 · p. 8
  • The theorems provide sufficient, not necessary, conditions, and their conclusions do not guarantee global optimality for fixed sigmoid or arctan networks.A function-space descent direction may be orthogonal to the functions represented by a fixed architecture.Source: §4.2 · p. 8
  • Connecting function-space results to parameter spaces of common architectures remains open; Jacobian full rank is one cited condition linking the views.Source: §4.2 · p. 8

A ANALYSIS OF DEEP NONLINEAR NETWORKS

The appendix establishes notation for function derivatives and norms, then expresses Fréchet derivatives as directional changes in the risk functional.

A.1 NOTATION

  • Writing the derivative in inner-product form emphasizes that its output is a real number and avoids confusion from nested parentheses and brackets.Source: §A.1 · p. 10
  • The appendix defines vector and matrix norms, a generalized induced norm for nonlinear functions, and an operator norm for linear functionals.Source: §A.1 · p. 10

A.2 FR´ECHET DERIVATIVES

  • Equation (6) expresses the risk change under a perturbation of one layer and is used in the proofs of Theorems 4.1 and 4.2.Source: §A.2 · p. 10
  • The Fréchet derivative with respect to a layer is a linear functional on perturbation directions, returning a real-valued directional derivative.Source: §A.2 · p. 10

A.3 PROOF OF THEOREM 4.1

The proof of Theorem 4.1 constructs a layer perturbation using a full-row-rank Jacobian and uses it to connect stationarity with global optimality.

A.3 PROOF OF THEOREM 4.1

  • The proof sets A(X) to the Jacobian of the downstream composition evaluated at h1(X); its assumed full row rank makes A(X)A(X)^T invertible for constructing a direction.Source: §A.3 · p. 10
  • The constructed direction is checked to vanish at zero and be differentiable, supporting its membership in the first-layer function space.Source: §A.3 · p. 10
  • At a critical point, a zero operator norm of the first-layer risk derivative implies that the population risk equals its optimum.Source: §A.3 · p. 11

A.4 PROOF OF THEOREM 4.2

Theorem 4.2's proof selects a layer with specified input and output dimensions, then constructs a perturbation from the downstream Jacobian.

A.4 PROOF OF THEOREM 4.2

  • The proof considers the derivative with respect to layer j, where the theorem assumes dx = d_(j−1) and dy ≤ d_j.Source: §A.4 · p. 11
  • It defines A(w) as the Jacobian of the downstream composition evaluated at h_j(w); the assumed full row rank makes A(w)A(w)^T invertible.Source: §A.4 · p. 11
  • The proof checks that the constructed perturbation vanishes at zero and is differentiable, including through the inverse map used in its construction.Source: §A.4 · p. 11

A.5 PROOF OF PROPOSITION 4.3

The construction embeds the target function in selected coordinates and pads the remaining coordinates with zeros, yielding layer functions that satisfy the theorem’s conditions.

A.5 PROOF OF PROPOSITION 4.3

  • The first layer places h*(x) in its first dy components and sets all remaining components to zero.The construction assumes d1 ≥ dy.Source: §A.5 · p. 12
  • Each later layer truncates its input when its width is smaller and zero-pads it when its width is larger.Source: §A.5 · p. 12
  • The composed layers reproduce h*, and the final composition has a Jacobian with minimum singular value at least 1.The passage also states that this composition is twice-differentiable.Source: §A.5 · p. 12

B DEFERRED LEMMA

The lemma shows that a critical point of the deep linear network is either a local minimum or a saddle point by ruling out local maxima in both product cases.

B DEFERRED LEMMA

  • Any critical point that is not a local minimum is a saddle point.Source: B DEFERRED LEMMA · p. 12
  • When the product of the first H weight matrices is nonzero, the Hessian has a strictly positive eigenvalue, giving an increasing direction and ruling out a local maximum.The argument assumes XXT is full rank.Source: B DEFERRED LEMMA · pp. 12–13
  • When the product is zero, the proof treats the degenerate critical-point case separately because such points can be harder to handle.Source: B DEFERRED LEMMA · p. 13
  • For the zero-product case, arbitrarily small perturbations produce a nearby point with strictly greater loss, excluding a local maximum.The perturbation procedure selects a layer index and uses opposite perturbations of that layer’s weight matrix.Source: B DEFERRED LEMMA · p. 13

C.1 PROOF OF PROPOSITION 3.1

The proof reduces the rank-constrained risk to a matrix approximation problem and derives a first-order loss expansion for weight perturbations.

C.1 PROOF OF PROPOSITION 3.1

  • The residual from projecting Y onto row(X) is orthogonal to matrices whose columns lie in row(X).Source: §C.1 · p. 14
  • The rank-constrained minimizer is obtained by taking the k-rank approximation of the projected output matrix, yielding a unique global minimum under the distinct-singular-values assumption.The approximation uses the leading k left-singular directions.Source: §C.1 · p. 14

C.2 PROOF OF LEMMA 3.2

  • Perturbing one weight matrix changes the loss by a first-order trace term plus an O(∥∆i∥2) remainder.Source: §C.2 · p. 14
Loading 1707.02444v3…