Failures of Gradient-Based Deep Learning

Shai Shalev-Shwartz; Ohad Shamir; Shaked Shammah

Source-linked AI summary

Failures of Gradient-Based Deep Learning

Shai Shalev-Shwartz, Ohad Shamir, Shaked Shammah

arXiv:1703.07950v2Mar 23, 2017cs.LGcs.NEstat.ML

TL;DR

Deep learning’s success leaves important difficulties of common gradient-based methods insufficiently understood. The paper studies simple failure cases through experiments and theoretical analysis, identifying uninformative or noisy gradients, poor conditioning, and flat activations. It also examines alternative objectives, architectures, conditioning techniques, and update rules as remedies.

Problem
Theoretical understanding remains insufficient for rigorously analyzing the difficulties practitioners face with common deep-learning algorithms.
Method
The paper combines practical experiments with theoretical analyses of gradient information, gradient variance, signal-to-noise ratios, conditioning, and activation flatness.
Results
The studied failures arise from negligible target information in gradients, noisy end-to-end gradients, poor conditioning, and vanishing gradients from flat activations; alternative methods can remedy some cases.
Takeaways & Limitations
Gradient-based deep learning can be limited by local gradient properties and optimization geometry, so decomposition, architecture choice, conditioning, or non-gradient updates may help.
Takeaways & Limitations
Convergence guarantees are established for a one-layer architecture, while deeper networks are left for future study.

Abstract

from arXiv · show

In recent years, Deep Learning has become the go-to solution for a broad range of applications, often outperforming state-of-the-art. However, it is important, for both theoreticians and practitioners, to gain a deeper understanding of the difficulties and limitations associated with common approaches and algorithms. We describe four types of simple problems, for which the gradient-based algorithms commonly used in deep learning either fail or suffer from significant difficulties. We illustrate the failures through practical experiments, and provide theoretical insights explaining their source, and how they might be remedied.

1 Introduction

The paper examines simple problems where commonly used gradient-based deep-learning methods struggle, combining experiments with theory to identify failure sources and possible remedies.

1 Introduction: The paper studies simple problem families where commonly used methods perform worse than expected, using empirical results to motivate theoretical analysis.The analysis characterizes sources of failure and informs alternative architectures, loss functions, or optimization schemes.
1 Introduction: Some problems have gradients carrying negligible information about the target function, limiting any gradient-based method regardless of network architecture.The analysis uses Statistical Queries insights and contrasts local loss information with globally defined objectives.
1 Introduction: End-to-end training can be much slower than decomposition, which optimizes structured sub-problems with additional objectives and supervision.The paper analyzes this disparity through gradient informativeness and signal-to-noise differences.
1 Introduction: Architecture and optimization choices can substantially affect training time even when architectures have equal expressive power, while deeper or wider networks may not help.The paper studies this through conditioning and gradient-descent runtime on a piece-wise linear curve-encoding problem.
1 Introduction: Flat activation regions can cause vanishing gradients and slow training, but alternative update rules can solve the learning problem efficiently with convergence guarantees for a function family.The paper studies non-flat approximations of step functions using sums of sigmoids.

2 Parities and Linear-Periodic Functions

This section shows that gradient-based learning can fail on random parities and related linear-periodic problems because gradients may contain negligible information about the target, independent of network architecture. Empirical and theoretical analyses explain the failure and identify exponentially long runtimes as a consequence under a stated oracle model.

Gradient information: For the studied problem family, gradients are essentially identical across target functions at any fixed point, regardless of architecture or parametrization.The family includes compositions of linear and periodic functions, and deeper or wider networks do not resolve the lack of gradient information.
Random parities: Random parity learning maps uniformly sampled binary inputs to labels determined by the parity of coordinates selected by a random vector v∗.The target is y = (−1)^⟨x,v∗⟩, with v∗ chosen uniformly from {0,1}^d.
Empirical failure: As dimension d increases, parity learning becomes harder, reaching no better than random accuracy around d = 30 after reasonable training time.The experiments use a ReLU network with one hidden layer and hinge loss; Figure 1 plots accuracy against training iterations for different input dimensions.
Gradient information: For mutually orthogonal candidate targets, gradient variance is bounded by G(w)^2/2^d and therefore becomes exponentially small in dimension.Chebyshev’s inequality then implies that gradients concentrate around a target-independent fixed point.
Linear-periodic functions: The same lack of gradient signal extends to linear-periodic functions under smooth input distributions, when the Fourier-transform condition on the density is satisfied.The bound is extremely small for moderately large norm r and dimension d, indicating little target information in the gradients.
Implications: Under a reasonable oracle-based model, gradient-based methods require exponentially many iterations in r and d to return a reasonable predictor.The result applies regardless of predictor complexity, while the difficulty arises from choosing v∗ randomly; known fixed targets can be easier.

3 Decomposition vs. End-to-end

The paper compares end-to-end optimization with decomposition on structured problems composed of image-level subproblems. In a parity-based vision experiment, decomposition trains reliably while end-to-end gradients become non-informative and noisy as tuple length grows.

3.1 Experiment: The decomposition architecture first scores each image with a CNN, then feeds transformed scores into a second network that outputs the tuple prediction.Under the stated expressivity assumptions, this architecture has the potential to perform well.
3.1 Experiment: The end-to-end approach optimizes one primary objective, whereas decomposition separately optimizes subproblems using additional objectives.The decomposition loss can direct the image-level network toward outputs that the second network can separate, but requires known intermediate labels.
3.1 Experiment: End-to-end training works only for k = 1, 2 and completely fails for k = 3 or larger, while decomposition reaches a good solution across the tested tuple lengths.The comparison uses zero-one accuracy on a held-out test set; end-to-end training ran for 20000 SGD iterations versus 2500 for decomposition.
3.2 Analysis: The theoretical and empirical analyses attribute the end-to-end failure to gradients whose signal decreases rapidly with k and is masked by noise for k ≥3.The analysis distinguishes this mechanism from local-minimum or saddle-point explanations.

4 Architecture and Conditioning

Architecture choice affects optimization even when expressive power is sufficient: convolutional structure improves conditioning, and explicit conditioning can reduce dependence on input dimension. Extra expressive power alone does not resolve optimization difficulties.

Architecture choice: Architecture choice changes training complexity despite equal expressive power, with convolutional and fully connected solutions showing orders-of-magnitude differences in condition numbers.The study uses encoding one-dimensional piecewise linear curves to expose this optimization gap.
Problem setup: The task encodes sampled values of a piecewise linear curve into its intercept, slope changes, and breakpoint locations.The experiments use n = 100 samples and k = 3 pieces, with uniformly sampled breakpoints and slopes.
Fully connected architecture: A fully connected linear architecture converges slowly despite convex realizability, retaining inaccuracies at the curve’s non-smoothness points.The inverse transformation is realizable by the learned weights, but satisfactory convergence is still slow.
Convolutional architecture: A convolutional layer represents the inverse mapping with filter [1, −2, 1], improving convergence and reducing the required gradient-descent order from Ω(n3.5) to Θ(n3).The convolutional representation lowers the problem dimension and improves its condition number.
Explicit conditioning: Whitening the reduced convolutional regression makes the condition number approximately 1, yielding SGD convergence in order of log(1/ϵ) iterations independently of n.The method estimates a 3×3 correlation matrix, applies its inverse square root, and quickly produces highly accurate results.
Expressive power: Greater expressive power does not fix the optimization problem: a stronger auto-encoder still misses fine details at non-smooth points.The combined use of a better architecture and conditioning is what produces the dramatic improvement.

5 Flat Activations

Flat or saturated activations make gradient-based optimization ineffective because their derivatives vanish. The paper compares approximations, improper learning, classification, and a forward-only update to propagate useful error through step-like functions.

Problem: Saturation creates flat loss regions, vanishing gradients, and slower training, with the problem amplified in deeper networks.The issue is especially relevant to sigmoid gates in recurrent architectures such as LSTMs and GRUs.
Approaches: Piecewise-flat activations produce zero gradients, so the paper tests alternatives that approximate, implement, or learn the activation while allowing error propagation.The experiments focus on monotone step functions and related non-smooth targets.
Non-flat approximation: A sigmoid-based non-flat approximation remains slow and can fail because initialization may place the bias in a wide, nearly flat region.Although continuous and not completely flat, the approximation retains flatness-related optimization difficulties.
End-to-end learning: End-to-end learning with a larger ReLU network captures discontinuities imperfectly and incurs higher sample, training, and test-time costs.Its advantage is requiring minimal prior knowledge about the step function.
Multi-class classification: Multi-class classification suffers from inaccuracies at class boundaries because the predictor lacks structure over the ordered step values.The final layer uses one output for each of the 55 step classes.
Forward-only update: The forward-only update empirically achieves the best final accuracy, training time, and test-time cost.Its convergence guarantee requires u to be L-Lipschitz and the weight vector to have bounded norm, giving ϵ-optimality in O(L2/ϵ2).

6 Summary

The paper identifies four recurring sources of difficulty for standard gradient-based deep learning: uninformative gradients, low signal-to-noise ratios, poor conditioning, and flat activations.

Summary: Standard gradient-based approaches can struggle because gradients contain insufficient information about the target function.The paper presents this as one of several difficulties beyond stationary-point issues.
Summary: Low signal-to-noise ratios, bad conditioning, and flat activations are additional sources of significant optimization difficulty.The paper frames these findings as an initial step toward understanding failures and possible remedies.

A.1 Experiment

In the synthetic asset-allocation experiment, decomposition outperforms end-to-end optimization in training time and final accuracy. The comparison uses alternative objectives or gradient estimators under a toy correlation assumption.

Strategies: The end-to-end strategy trains a network to output a distribution over k stocks and maximizes gain from that allocation.The experiment uses k = 500 stocks in the S&P500 index.
Strategies: The decomposition strategy predicts the single stock whose future gains are most positively correlated with the media reference, requiring additional labels.It separates prediction of the relevant stock from the downstream allocation objective.
Assumption: The synthetic setup assumes each media reference is strongly positively correlated with one stock and uncorrelated with the others, making the problem explicitly toyish.The authors note that real stock-exchange and media relationships have highly complicated correlations.
Gradient estimators: The two approaches can use different gradient estimators even when their expectations are equal, because exact gradient computation is expensive at large scale.The end-to-end estimator uses (x, z), while decomposition pays for labels y(x) and ignores z.
Results: For d = 1000, Figure 8 shows decomposition has better training-time and final-accuracy performance, while end-to-end optimization cannot close the gap for large k in reasonable time.The figure plots loss against training iterations for multiple k values, with red for end-to-end and blue for decomposition.

A.2 Analysis

Both gradient estimators are unbiased, so they have the same signal, but their variances differ because the end-to-end estimator sums k terms while the decomposition estimator uses one.

Both the end-to-end and decomposition estimators are unbiased estimators of the true gradient.The decomposition estimator is shown to be a different unbiased estimator, so the two estimators have the same signal.
SGD iteration complexity depends on the estimator variance, requiring on the order of ν̄2/ϵ2 iterations to reach ∥∇wL(w)∥2 ≤ ϵ.
At random initialization, the end-to-end estimator’s variance is roughly k times larger than the decomposition estimator’s variance.The comparison assumes the values of ∥G_i∥2 are similar at the beginning of training.
The variance gap arises because the end-to-end estimator sums k per-input terms, whereas the decomposition estimator contains a single corresponding element.

B.1 Proof of Theorem 1

The proof bounds gradient-estimator variance using orthogonality in an L2 function space. The squared-loss argument extends to classification loss through the binary-valued property of the functions.

The proof represents functions in a weighted L2 space and defines inner products and norms through expectations over the relevant distribution.
For squared loss, the variance bound is obtained by comparing ∇F_h(w) with a vector a independent of h, chosen as E_x[p_w(x)g(x)].
Mutual orthogonality of the functions in H and the norm bound ∥h∥L2 ≤ 1 provide the key inequality in the proof.
The classification-loss proof uses the loss definition together with h(x) ∈ {−1,+1}, then proceeds as in the squared-loss case.

B.2 Proof of Theorem 3

The proof controls variance when functions are normalized and nearly orthogonal, first through a spectral-norm argument and then through Gaussian-vector constructions and recursive update analysis.

Lemma 3 bounds the deviation for normalized functions whose pairwise L2 inner products are at most c in absolute value.
In a finite uniform domain, the functions form a matrix H whose Gram matrix is I + M, with off-diagonal entries bounded by c.
The spectral-norm bound yields ∥g∥2(1 + cn), which supplies the required estimate in the finite-dimensional proof.
The same operator-norm proof extends from finite domains to functions in weighted L2 spaces.
Gaussian projections of unit vectors are analyzed through their joint covariance, which equals the vectors’ inner product.
Measure concentration constructs many nearly orthogonal unit vectors, enabling the variance argument to be applied to a large family of induced functions.

B.5 Proof of Theorem 4

The proof analyzes stochastic updates through eigenvalues and condition numbers. It shows that ill-conditioned matrices can make convergence slow, while piecewise-linear covariance matrices can have condition number at least Ω(n3).

The expected matrix recursion converges only when ηλS1,1^2 < 1.
The condition number of W⊤W equals that of U⊤U, allowing the proof to transfer the eigenvalue analysis between the two matrices.
A constructed vector makes the minimal eigenvalue of U⊤U at most O(n^-3.5), while its maximal eigenvalue is at least 1.
For the linear update, the error remains at least 0.5 when t + 1 < 0.5 Dn,n/D1,1.
Under the stated assumptions on slopes and piecewise-linear curves, the covariance matrix satisfies λ1(C) ≥ Ω(n2) and λ3(C) ≤ O(k/n).These bounds imply a condition number of C at least Ω(n3).
For the specified distribution with k slope changes, the covariance condition-number analysis establishes the corresponding upper-bound argument.

B.8 Proof of Update Rule 4 Convergence in the Lipschitz Case

The proof bounds the update dynamics under Lipschitzness and monotonicity assumptions, then separates iterations into cases to obtain an error guarantee. The supplied passages also state a ReLU construction that exactly realizes parity functions.

Convergence proof: The proof assumes bounded parameter norms, bounded target weights, and |u| ≤ c while analyzing the update rule.These bounds support the subsequent lower-bound argument for the update.
Convergence proof: L-Lipschitzness, monotonicity of u, and bounds on w, x, and u are used to derive the relevant inequality for expected regressor error.The expected error is denoted e_t before the proof separates into cases.
Convergence proof: At most 1/(η^2c^2) iterations can satisfy the case where the squared distance to v∗ decreases by at least η^2B^2c^2.This follows from nonnegativity of the squared distance and the initial bound ∥w_0 − v∗∥^2 ≤ B^2.
Convergence proof: After T iterations, the first case no longer holds, while the second case implies e_T ≤ ϵ.The supplied passage introduces the iteration bound immediately before this conclusion.
Parity construction: Scaling the output weights by 4 and adding an output bias of −1 yields a perfect parity predictor.The preceding construction produces outputs 0 and 1 before this final rescaling and bias adjustment.

D Command Lines for Experiments

The appendix lists command lines for viewing options and running experiments across the paper’s sections. Separate scripts cover piecewise-linear, parity, tuple-rectangle, stock, and SNR experiments.

General usage: The implementation uses Python and TensorFlow, with help commands available for viewing optional arguments.The supplied instructions identify TensorFlow as the optimization package.
Section 5 experiments: Section 5 experiments use step_learn.py and parity.py, each with a help option for available arguments.The commands are listed as separate executable scripts.
Section 3 experiments: Tuple-rectangle experiments use tuple_rect.py, while SNR estimations use tuple_rect_SNR.py.Both commands are shown with the --help option.
Experiment A: Stock experiment A uses dec_vs_e2e_stocks.py with the --help option.The command is provided as the entry point for that experiment.
Section 4 experiments: The FtoKConvCond experiment is run with batch_size 10, number_of_iterations 500, and learning_rate 0.99.These are the explicit command-line settings supplied for experiment 4.1.3.