Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

Alon Brutzkus; Amir Globerson

Source-linked AI summary

Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

Alon Brutzkus, Amir Globerson

arXiv:1702.07966v1Feb 26, 2017cs.LGmath.OCstat.ML

TL;DR

The paper asks when gradient descent can globally optimize a non-convex ReLU convolutional network. It analyzes a one-hidden-layer no-overlap architecture and shows NP-completeness in general, but polynomial-time global optimization under independent standard Gaussian inputs.

Problem
The paper investigates under what conditions gradient descent can be globally optimal despite the hardness and non-convexity of neural-network training.
Method
The paper analyzes a one-hidden-layer convolution-like network with non-overlapping filters, ReLU activation, average pooling, and population-risk minimization.
Results
Learning is NP-complete for unconstrained input distributions, whereas independent Gaussian inputs permit polynomial-time learning with gradient descent.
Takeaways & Limitations
The results demonstrate distribution-dependent global optimality of gradient descent for a neural architecture combining convolution-like structure and ReLU activation.
Takeaways & Limitations
The derivation concerns population risk; finite-sample empirical-risk tractability is suggested experimentally but remains unproved.

Abstract

from arXiv · show

Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove that optimization will succeed. Here we provide a strong result of this kind. We consider a neural net with one hidden layer and a convolutional structure with no overlap and a ReLU activation function. For this architecture we show that learning is NP-complete in the general case, but that when the input distribution is Gaussian, gradient descent converges to the global optimum in polynomial time. To the best of our knowledge, this is the first global optimality guarantee of gradient descent on a convolutional neural network with ReLU activations.

1 Introduction

The paper studies when gradient descent can provably optimize a non-convex neural network, focusing on a no-overlap convolutional architecture with ReLU activation and average pooling. It establishes hardness without distributional restrictions, but polynomial-time global optimization for independent standard Gaussian inputs.

Gradient descent is widely used for non-convex deep-network training, but its theoretical convergence and global optimality remain poorly understood.
The studied no-overlap network applies one shared filter to disjoint input parts, uses ReLU activation, and averages the resulting neuron outputs.The architecture has one hidden layer and a single filter vector.
Without restrictions on the input distribution, learning No-Overlap Networks is NP-complete via a reduction from a set-splitting problem.
For independent Gaussian inputs with mean 0 and variance 1, No-Overlap Networks can be learned in polynomial time using gradient descent.
Experiments show gradient descent succeeds on the Gaussian case but fails for a different input distribution.
With overlapping filters, even Gaussian inputs can produce non-optimal local minima, although multiple restarts may overcome them empirically.

2 Related Work

Related work establishes hardness and studies distributional assumptions, loss geometry, and gradient-descent guarantees for neural networks and related optimization problems. The paper addresses the remaining question of global gradient-descent optimality for its ReLU convolutional architecture.

Prior results show hardness for several neural-network settings, including one-hidden-layer networks with sign or other activation functions.
Some learning guarantees rely on symmetric or log-concave distributions, but the cited works do not analyze gradient descent as the optimization method.
Gradient descent can succeed for over-specified networks or simpler single-neuron regression, while these settings differ from the architecture studied here.
Distribution-dependent tractability has limits for sufficiently large one-hidden-layer networks, although the cited hardness construction lacks parameter tying and does not apply to this architecture.
Other work characterizes loss surfaces or convergence for linear networks, matrix completion, tensor decompositions, and related models without directly establishing the paper's result.
Perfect fitting of random labels has been demonstrated, while its optimization-theoretic explanation remains open.

3 Preliminaries

The analysis uses realizable one-hidden-layer networks with average pooling and IID standard Gaussian inputs, reducing Gaussian ReLU expectations to a tractable function of filter geometry. No-overlap structure then simplifies the population loss.

The Gaussian analysis assumes IID input coordinates with mean 0 and variance 1, denoted by distribution G.
The general model has k hidden units, a fully connected weight matrix W, pointwise ReLU activation, and average pooling.
In the realizable setting, labels are generated by a true parameter W∗, and the population risk measures squared prediction error.
The Gaussian analysis defines g(u, v) as the expectation of the product of two ReLU responses, enabling the loss to be simplified.
For IID Gaussian inputs, g(u, v) has a closed form determined by the angle between u and v.
In No-Overlap Networks, the model uses one filter vector whose repeated block structure simplifies the loss and its pairwise terms.

4 Learning No-Overlap Networks is NP-Complete

Without assumptions on the data distribution, optimizing a realizable no-overlap network is NP-complete, established through a reduction from Set-Splitting-by-k-Sets.

The no-overlap architecture is a simplified convolutional layer with average pooling, yet its optimization remains hard.
The learning objective minimizes squared population risk, and the general-distribution analysis also encompasses empirical risk through distributions uniform on training points.
The reduction constructs a k-Non-Overlap-Opt instance whose low-risk solutions correspond to valid splitting sets.
Set-Splitting-by-k-Sets is NP-complete for every k ≥ 2, providing the source problem for the hardness reduction.
For every k ≥ 2, k-Non-Overlap-Opt is NP-complete, and finding a weight vector within the stated constant accuracy of minimum loss is hard.

5 No-Overlap Networks can be Learned for Gaussian Inputs

Under IID standard Gaussian inputs, the paper characterizes the loss landscape and proves that randomly initialized gradient descent reaches an approximately globally optimal solution in polynomial time with high probability.

The Gaussian analysis studies one-hidden-layer networks with IID zero-mean, unit-variance inputs, focusing on no-overlap networks.
For k > 1, the loss has a local maximum at w = 0, a unique global minimum at w = w∗, and a degenerate saddle point.
The gradient-descent update uses a positive step size λ and iteratively subtracts the loss gradient from the current weight vector.
With probability at least 1−δ, random unit-sphere initialization reaches loss O(ϵ) in O(1/ϵ^2) iterations under the theorem's conditions.The iteration complexity hides a linear factor in the input dimension.
When λ < 1, the angle to w∗ decreases each iteration, preventing convergence to the saddle point unless initialization is exactly opposite.
Consequently, gradient descent solves k-Non-Overlap-Opt under the Gaussian assumption with high probability and in polynomial time.

6 Empirical Illustration of Tractability Gap

The empirical comparison uses the same target weights with Gaussian and non-Gaussian inputs, showing optimal optimization in the Gaussian case but trapping in a sub-optimal point for the non-Gaussian case.

The experiment compares easy and hard cases by holding w∗ fixed while changing the input distribution.
The hard case is generated from a Set-Splitting instance with 40 elements, 760 subsets, and a resulting training set of 800 examples.
The Gaussian case uses the same training-set size and labels generated by the no-overlap network with w∗.
AdaGrad gets trapped at a sub-optimal point on the non-Gaussian dataset but solves the Gaussian case optimally and converges to w∗.
Figure 2 plots AdaGrad training loss across epochs for the Gaussian and non-Gaussian datasets.

7 Networks with Overlapping Filters

Allowing filter overlap changes the optimization landscape: even with Gaussian inputs, gradient descent can remain in sub-optimal regions, while empirical restarts often recover the global optimum.

7.1 Suboptimality of Gradient Descent for R2: With probability greater than 1/4, gradient descent gets stuck in a sub-optimal region for the analyzed overlapping setting.The result concerns the two-dimensional filter example under Gaussian inputs.
7.1 Suboptimality of Gradient Descent for R2: Overlapping filters create a more complex loss with large sub-optimal regions absent from the non-overlapping case.The overlapping objective contains additional interactions among filter vectors, altering gradient dynamics and geometry.
7.1 Suboptimality of Gradient Descent for R2: An initialization in the fourth quadrant remains there throughout gradient descent, although the unique global optimum lies in the second quadrant.This invariant region explains why those initializations cannot reach the global optimum.
7.1 Suboptimality of Gradient Descent for R2: The sub-optimality gap in the fourth quadrant scales with O(1/k^2), and the stated lower bound is tight.For the analyzed construction, the lower bound is attained by a specific parameter vector.
7.2 Empirical study of Gradient Descent for m > 2: For general dimensions, filter sizes, and overlaps, the theoretical behavior remains open, while experiments found a basin-of-attraction mass of at least 1/17.Across the tested settings, a few dozen random restarts found the global optimum with high probability.

8 Discussion

The paper characterizes when gradient descent is globally optimal for a non-linear convolution-like architecture, while noting limitations concerning empirical-risk theory and standard overlapping or max-pooling layers.

Discussion: The main characterization combines no-overlap architecture, one hidden layer, average pooling, and Gaussian inputs.The paper also notes that other distributions, including sub-Gaussian and log-concave ones, might be tractable.
Discussion: The results show that no-overlap learning is hard without distributional restrictions, whereas Gaussian inputs permit polynomial-time gradient descent.This demonstrates a gap between worst-case intractability and tractability under data assumptions.
Discussion: The derivation analyzes population risk in closed form, while experiments suggest—but do not formally prove—that Gaussian empirical-risk optimization is tractable.The authors identify measure concentration as a possible route to a formal result.
Discussion: Standard convolutional layers commonly use overlapping filters and max pooling, whereas the paper studies non-overlap and leaves max-pooling analysis for future work.The paper reports initial overlap results and suggests that random restarts may recover optimality.
Discussion: Distribution-dependent tractability had previously been shown for intersections of halfspaces, but not using gradient descent.That architecture is non-convolutional.

A Proof of Lemma 3.2

This appendix develops technical ingredients for the paper’s loss geometry and hardness arguments, including differentiability analysis, reductions from satisfiability, and classification of critical points.

A Proof of Lemma 3.2: The proof analyzes differentiability and partial derivatives when vectors are parallel, using rotation invariance and limiting arguments.The values obtained in the parallel case agree with the general derivative expression.
A Proof of Lemma 3.2: Equal-3SAT is shown NP-complete, and Set-Splitting-by-2-Sets is established NP-complete through a reduction from Equal-3SAT.The construction preserves satisfiability while balancing variables and clauses.
A Proof of Lemma 3.2: Set-Splitting-by-k-Sets is proved NP-complete by induction, reducing the k-set version to the (k+1)-set version.The reduction adds a new element and paired sets to preserve splittability.
A Proof of Lemma 3.2: For k > 1, w = 0 is a local maximum, while the antiparallel critical point is a one-dimensional local minimum and a degenerate saddle in the broader geometry.The Hessian at the antiparallel point has nonnegative eigenvalues with at least one zero eigenvalue.
A Proof of Lemma 3.2: For nonzero angular deviation, the critical-point condition forces a contradiction, ruling out additional critical points in that case.The argument uses the dependence of the loss on norms and the angle between vectors.

C.2 Proof of Theorem 5.2

The proof establishes convergence of gradient descent for the Gaussian population risk by controlling angle, norm, smoothness, and distance to the global minimum.

C.2 Proof of Theorem 5.2: For learning rate λ < 1, the angle between the iterate and w∗ decreases at every iteration unless it is already aligned or antiparallel.Consequently, initialization with angle different from π avoids the saddle point.
C.2 Proof of Theorem 5.2: The iterates’ norms remain bounded away from zero, preventing the trajectory from entering the nonsmooth singular region at the origin.The proof establishes a constant lower bound under the stated initialization and learning-rate conditions.
C.2 Proof of Theorem 5.2: Away from the origin, the gradient is Lipschitz continuous on the relevant half-plane, with L = 1 + 3∥w∗∥/M.This permits standard smooth-optimization descent analysis along each update segment.
C.2 Proof of Theorem 5.2: Under a random initialization avoiding the antiparallel direction, gradient descent reaches an iterate with ∥∇ℓ(w_t)∥ < ϵ after the stated iteration bound.The theorem’s proof then converts small gradient norm into proximity to w∗.
C.2 Proof of Theorem 5.2: A small gradient norm implies O(√ϵ) distance from the global minimum, using bounds on angle and norm error.The final loss bound follows from Lipschitz continuity of the ReLU and Gaussian norm calculations.

D.1 Proof of Proposition 7.1

The proof analyzes gradient-descent updates by tracking weight norms and angles, showing that iterates remain nonzero and enter the target fourth-quadrant region. It also establishes the relevant global-minimum characterization.

Geometric analysis: For weights in the fourth quadrant, adding the relevant gradient components can only increase the weight norm in the analyzed cases.This supports the geometric control used in the proof's update analysis.
Update properties: The proof shows that each update keeps w_t nonzero under the stated step-size and directional conditions.The argument bounds the update norm when the gradient component points opposite to w.
Update properties: Gradient components are analyzed through their effects on the iterate's angle relative to the coordinate axes and target vector.The proof separates cases according to the signs of w_1 and -w_2 and tracks how the components change the angle.
Update properties: The iterates are shown to enter the interior of the fourth quadrant, with 0 < θ_{t+1} < π/2 in the main case.The complementary sign case is handled by defining angles relative to the negative y axis.
Geometric analysis: The proof lower-bounds the loss using auxiliary lemmas, then minimizes the resulting expression over a scalar α.The minimizer is evaluated at a vector proportional to the target direction, yielding an explicit loss value.

E Experimental Setup for Section 7.2

The experiments vary network and ground-truth settings, repeat randomly initialized gradient descent, and estimate convergence to the unique global minimum. They report positive convergence rates across all tested ground truths.

Experimental design: Experiments vary hidden-neuron count, filter size, stride length, and ground-truth distributions, using 30 randomly selected ground truths per setting.Deterministic ground truths with constant and several increasing or decreasing sequences are also tested.
Experimental design: Each ground truth receives 20 gradient-descent runs, classified by reaching the unique global minimum or remaining away with very low gradients for 5000 iterations.The empirical convergence probability is computed from the number of successful runs out of 20.
Evaluation: The Wilson method provides a one-sided confidence-interval lower bound using α = 0.05 and n = 20.Initialization is restricted to a large hypercube where the gradient does not vanish outside the hypercube.
Results: ˆp ≥ 0.15 for every ground truth, so each ground truth reaches the global minimum at least 3 times.The corresponding confidence-interval lower bound exceeds 1/17 in every setting.
Results: The zero-loss analysis establishes w = w∗, making w∗ the unique global minimum in the examined no-overlap setting.The proof compares network outputs on inputs supported on individual coordinates to identify both filter components.