PaperlayerView exact revision on arXiv

Source-linked AI summary

The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent

Karthik A. Sankararaman, Soham De, Zheng Xu, W. Ronny Huang, Tom Goldstein

arXiv:1904.06963v5cs.LGstat.ML

TL;DR

The paper asks how neural-network architecture affects training and analyzes the question using gradient confusion, a condition on interactions among objective gradients. It finds that width and depth have opposing effects under standard Gaussian initialization, while orthogonal initialization and combined batch normalization and skip connections are promising for deep networks.

  • Problem

    How neural-network architecture affects trainability and SGD dynamics remains incompletely understood, despite overparameterization being typical.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes gradient confusion theoretically and tests its predictions in experiments across several network architectures and image-classification datasets.

    Source: §1 · p. 2, §7 · p. 6

  • Results

    At standard Gaussian initialization, increasing width lowers gradient confusion while increasing depth raises it; orthogonal initialization makes confusion independent of depth in linear networks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Batch normalization combined with skip connections lowers gradient confusion, and orthogonal initialization offers a promising direction for improving very deep network trainability.

    Source: §10 · p. 9

    The depth analysis is restricted to weights with operator norm close to 1; it does not provide non-vacuous bounds for general signal-magnitude blow-ups.

    Source: §5 · p. 5

Abstract

from arXiv · show

This paper studies how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion to help formally analyze this. When gradient confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through theoretical and experimental results, we demonstrate how the neural network architecture affects gradient confusion, and thus the efficiency of training. Our results show that, for popular initialization techniques, increasing the width of neural networks leads to lower gradient confusion, and thus faster model training. On the other hand, increasing the depth of neural networks has the opposite effect. Our results indicate that alternate initialization techniques or networks using both batch normalization and skip connections help reduce the training burden of very deep networks.

1. Introduction

The paper examines how architecture affects SGD trainability and introduces gradient confusion as a way to analyze the connection. It reports that width lowers confusion while depth raises it under standard Gaussian initialization, with orthogonal initialization and batch normalization plus skip connections offering approaches for deep networks.

1. Introduction

  • The paper addresses limited theoretical understanding of neural-network SGD dynamics and how architecture affects training, including the observed contrast between deeper, slower and wider, faster networks.The paper aims to relate width, depth, problem dimensionality, and initialization to trainability and SGD dynamics.Source: §1 · pp. 1–2
  • Gradient confusion links pairwise gradient interactions to SGD convergence: high confusion may slow convergence, whereas low confusion can accelerate it and support constant learning rates.The paper uses the condition to study architecture’s effects on trainability and convergence.Source: §1 · p. 2
  • At standard Gaussian initialization, wider networks have lower gradient confusion while deeper networks have higher confusion, making width and depth opposing influences on trainability.The analysis applies to a large class of networks with different activations and loss functions, without requiring large layer widths.Source: §1 · p. 2
  • For linear neural networks, orthogonal initialization makes gradient confusion independent of depth, suggesting a route toward training deeper models.This result is specific to linear networks and orthogonal initialization.Source: §1 · p. 2
  • Experiments across WRNs, CNNs, and MLPs on CIFAR-10, CIFAR-100, and MNIST consistently support the theoretical predictions; batch normalization combined with skip connections lowers confusion.The authors connect the lower confusion to efficient SGD training of deep residual networks.Source: §1 · p. 2

2. Gradient confusion

Gradient confusion describes disagreement among objective terms when their gradients point in negatively correlated directions. The section defines a bound on pairwise gradient inner products and illustrates how low confusion can arise in orthogonal or overparameterized settings.

Gradient confusion

  • Gradient confusion occurs when gradients of different objective terms are negatively correlated, so their objectives disagree about the direction of parameter updates.SGD selects an objective function at random and updates parameters using its negative gradient.Source: §2 · p. 2
  • A gradient confusion bound η requires pairwise inner products between distinct objective gradients at fixed w to be at least −η.This bounds how negatively aligned the gradients can be.Source: §2 · p. 2

Observations in simplified settings

  • With orthogonal training vectors, logistic-regression gradients have zero confusion, so each objective term decouples and SGD behaves like gradient descent on each term.An update on one term has no effect on another term’s loss in this example.Source: §2 · p. 3
  • For randomly sampled vectors, overparameterization is expected to make a random linear model’s gradients nearly orthogonal and its confusion low.The section also describes a toy linear-regression example with faster convergence and lower confusion for a slightly overparameterized model.Source: §2 · p. 3, Figure 1 · p. 3

3. SGD is fast when gradient confusion is low

The section derives constant-learning-rate SGD convergence bounds in terms of gradient confusion. Under the stated conditions, low confusion supports fast convergence, while a separate smooth non-convex result relates the confusion bound to an O(1/T) rate.

Background

  • Earlier constant-rate SGD results for strongly convex, smooth functions converge only to a neighborhood whose noise floor depends on the learning rate and gradient variance.Those results require a small learning rate, α = O(ε), for ε-accuracy in O(1/ε) iterations.Source: §3 · p. 3

Relation to variance

  • Low gradient variance at the minimizer implies low gradient confusion there, but bounded confusion generally does not bound gradient variance.The section notes that small variance can also support fast constant-rate convergence without small step sizes.Source: §3 · p. 3

Convergence bounds

  • When the PL and smoothness assumptions hold, constant-rate SGD converges linearly to a neighborhood of the minima; η = O(ε) gives O(ε)-accuracy in O(log(1/ε)) iterations.The learning rate need not be vanishingly small for this accuracy guarantee.Source: §3 · pp. 3–4
  • For smooth non-convex functions, η = O(1/T) yields fast O(1/T) convergence, with an initial phase approaching a minimizer’s neighborhood or a stationary point.The paper says its aim is to show the direct effect of the confusion bound, not to establish state-of-the-art rate bounds.Source: §3 · p. 4

4. Effect of neural network architecture at Gaussian initializations

At standard Gaussian initialization, the analysis links network width and depth to gradient confusion and trainability. Its results predict that wider networks are easier to train, while deeper networks are harder.

4. Effect of neural network architecture at Gaussian initializations

  • The analysis studies fully connected networks at initialization with square or logistic loss, bounded inputs, and commonly used nonlinear activations.The stated scope includes sigmoid, tanh, and ReLU activations, with inputs either bounded or sampled from the unit sphere.Source: §4 · p. 4
  • Increasing depth raises gradient confusion, while increasing width lowers it, making deeper models harder and wider models easier to train at standard Gaussian initializations.The results cover bounded arbitrary inputs and inputs sampled from the unit sphere, under the paper’s stated network and loss settings.Source: §4 · p. 5
  • Experiments reported later provide evidence that increasing width often lowers gradient confusion and speeds convergence in sufficiently deep networks.The paper relates this trend to prior work on infinitely wide networks and width increasing linearly with depth.Source: §4 · p. 5

5. A more general result on the effect of depth

The analysis extends the depth result beyond initialization to weights bounded in operator norm and data sampled uniformly from a unit sphere. Under these conditions, increasing depth reduces the probability that the gradient-confusion bound holds, including uniformly within a ball around a local minimizer.

5. A more general result on the effect of depth

  • The results apply to fully connected and convolutional networks with square or logistic loss and commonly used activations, for data sampled from a unit sphere.The setup assumes small operator norms for all weight matrices and places the weights in a ball around a local minimizer for the uniform result.Source: §5 · p. 5
  • For fixed input dimension and sample count, increasing depth lowers the probability that the gradient-confusion bound holds, indicating typically slower training in the general small-weight setting.The weights are assumed to have operator norm at most 1; the analysis considers data sampled uniformly from a unit sphere.Source: §5 · p. 5
  • Under the unit-norm weight assumption, the width dependence can disappear when each weight matrix has only one nonzero entry equal to 1.In that example, forward and backward propagated signals do not depend on width despite each matrix having operator norm 1.Source: §5 · p. 5
  • The bound is made uniform over a ball around a weight point, and for unit-sphere data it holds throughout that ball with the stated high-probability guarantee.This addresses the distinction between a concentration bound at a fixed weight and SGD’s path through parameter space.Source: §5 · pp. 5–6
  • The authors connect the depth result to deep networks trained in practice, reporting that skip connections and batch normalization together substantially lower confusion.This is presented as an empirical finding about these techniques, rather than as a consequence of the general bound.Source: §5 · p. 6

6. Gradient confusion is independent of depth for orthogonal initializations

For deep linear networks with orthogonal weight matrices, the gradient-confusion bound’s probability does not depend on depth or maximum width. The paper notes that orthogonal initialization is incompatible with nonlinear activations such as sigmoid and ReLU.

6. Gradient confusion is independent of depth for orthogonal initializations

  • With orthogonal weight matrices and inputs sampled from the unit sphere, the gradient-confusion bound for the linear network has a probability independent of depth and maximum width.The theorem assumes the weight matrices satisfy the small-weight condition and uses the empirical square loss.Source: §6 · p. 6
  • The result indicates that trainability need not worsen with depth under orthogonal initialization, but the paper notes this initialization is incompatible with sigmoid and ReLU activations.The authors describe this as a potential direction for training deeper models, with a practical limitation for nonlinear networks.Source: §6 · p. 6

7. Experimental results

Experiments on image-classification networks examine how depth, width, batch normalization, and skip connections relate to SGD convergence and gradient confusion. Increasing depth worsens convergence in the tested CNNs, while greater width and the combination of normalization and skip connections improve trainability.

7. Experimental results

  • The experiments use WRNs, CNNs, and MLPs on CIFAR-10, CIFAR-100, and MNIST, with the section presenting CNN results on CIFAR-10.The reported setup uses SGD without momentum and runs each experiment five times.Source: §7 · p. 6
  • With width factor fixed at 2, increasing CNN depth slows convergence and increases gradient confusion; cosine similarities also concentrate less sharply around zero.Figure 2 reports SGD convergence curves, minimum pairwise cosine similarities, and their end-of-training density estimates for depths 16, 22, 28, 34, and 40.Source: Figure 2 · p. 7, §7 · p. 7
  • Increasing width at fixed depth speeds convergence and lowers gradient confusion; pairwise gradient cosine similarities concentrate around zero as width grows.The tested CNN-16-2 was still overparameterized and achieved high performance.Source: §7 · p. 7
  • Using batch normalization and skip connections together leaves gradient confusion relatively low even in very deep networks, significantly improving deep-model trainability.Either technique individually helps train deeper models, but results still worsen and confusion increases with depth.Source: §7 · p. 7

8. Alternate definitions of gradient confusion

The section extends gradient confusion beyond its worst-case definition and describes how minibatch averaging affects the condition.

8. Alternate definitions of gradient confusion

  • The gradient confusion bound η uses the worst-case gradient inner product, but the results also extend to an average-inner-product bound with unchanged conclusions up to constants.A normalized variant is also introduced, with an additional bounded stochastic-gradient norm assumption that permits tighter results.Source: §8 · p. 7
  • The normalized condition assumes bounded stochastic-gradient norms, and therefore bounded gradient variance; the theoretical results remain qualitatively similar but can be tighter.This assumption is discussed in section 9.Source: §8 · p. 7
  • For minibatches of size B, gradient confusion still applies, while the gradient-inner-product variance scales as 1/B^2 and η is expected to decrease as B grows.Source: §8 · p. 7

9. Related work

The related work distinguishes gradient confusion from gradient variance and diversity, and situates the paper alongside studies of architecture effects and SGD convergence.

9. Related work

  • Gradient variance can bound gradient confusion under a stated assumption, but gradient confusion does not generally bound variance; the paper’s counterexample has zero confusion and unbounded variance.With unbounded variance, lowering the learning rate does not reduce the SGD noise term in the convergence bounds.Source: §9 · p. 8
  • Unlike gradient diversity, which rises as gradients become orthogonal and then oppose one another, gradient confusion is zero unless their inner product is negative.The paper frames the measures as complementary: diversity concerns large-batch distributed training, while confusion concerns small-batch convergence.Source: §9 · p. 8
  • Prior architecture studies report increasingly negative gradient correlations with depth for ReLU networks at Gaussian initialization, and slow early dynamics when hidden-layer reciprocal widths sum too high.Hanin (2018) links that sum to gradient-variance growth; Hanin & Rolnick (2018) link it to activation-size variance.Source: §9 · pp. 8–9
  • Results showing SGD convergence to global minimizers in over-parameterized linear and nonlinear networks complement this paper’s study of low gradient confusion in practical networks.Source: §9 · p. 9

10. Discussion

The discussion connects width, depth, and initialization to trainability, while the appendix outlines supporting experiments, lemmas, intuition, and assumptions.

10. Discussion

  • At standard Gaussian initialization, greater width lowers gradient confusion while greater depth raises it, motivating width growth with depth to maintain trainability.The discussion notes related work suggesting width should increase linearly with depth to help early training dynamics (Hanin, 2018; Hanin & Rolnick, 2018).Source: §10 · p. 9
  • The paper studies batch normalization and skip connections as ways to train deep models without relying on width growth; their combination lowers confusion and helps train very deep models.Orthogonal initialization is presented as a promising direction for improving very-deep-network trainability.Source: §10 · p. 9
  • The discussion proposes gradient confusion as a possible trainability measure and future work on its connection to generalization, while highlighting orthogonal initialization for nonlinear very deep networks.Source: §10 · p. 9

Appendix

  • Appendix A adds experimental setup and results across network types and datasets; Appendix B proves the near-orthogonality lemma used in the main text.Source: Appendix · p. 12
  • Appendices C and E provide intuition and supporting lemmas, while Appendix F discusses the small-weights assumption required by several main-text results.Source: Appendix · p. 12

A. Additional experimental results

Across MNIST, CIFAR CNNs, and WRNs, the additional experiments broadly reproduce the depth and width trends, while combined batch normalization and skip connections help very deep models.

A.1. MLPs on MNIST

  • The experiments vary MLP depth, width, activation, and initialization, and assess confusion using sampled mini-batch gradient cosine similarities.The MNIST setup uses standard train-validation-test splits, constant-rate SGD, and reports means and standard deviations across runs.Source: §A.1 · pp. 12–13
  • For MNIST MLPs, gradient confusion and final training loss increase with depth; at depth 1000, tanh networks are effectively untrainable.The trend appears with identity and tanh activations under both Glorot-normal and LeCun-normal initialization.Source: §A.1 · p. 13
  • For MNIST MLPs, increasing width lowers gradient confusion and final training loss, while width 30 leaves the network completely untrainable.The trend appears for linear and tanh networks with both Glorot-normal and LeCun-normal initialization.Source: §A.1 · p. 13

A.2. Additional experimental details for CNNs and WRNs; WIDE RESIDUAL NETWORKS; CONVOLUTIONAL NEURAL NETWORKS; HYPERPARAMETER TUNING AND OTHER DETAILS

A.3. Additional plots for CIFAR-10 on CNNs; A.4. CIFAR-100 on CNNs

  • On CIFAR-10 and CIFAR-100, deeper CNNs are harder to train and have higher gradient confusion, while wider CNNs are easier to train and have lower confusion.For CIFAR-100 CNNs, the minimum pairwise cosine similarity showed no perceptible width-related change, although the distribution concentrated more sharply around zero.Source: §A.3 · p. 15, §A.4 · p. 15

A.5. Image classification with WRNs on CIFAR-10 and CIFAR-100

  • On CIFAR-10 and CIFAR-100, deeper WRNs have higher gradient confusion, while greater width typically lowers confusion and loss, with possible diminishing returns.Pairwise cosine similarities concentrate less around zero with depth and typically more around zero with width.Source: §A.5 · p. 16

A.6. Effect of batch normalization and skip connections

  • On CIFAR-100, batch normalization and skip connections each help train deeper models, but using both keeps gradient confusion relatively low even in very deep networks.The combination significantly improves the trainability of deep models.Source: §A.6 · p. 16

B. Near orthogonality of random vectors

  • The near-orthogonality proof bounds the chance that two random unit vectors have a large inner product, then uses a union bound over pairs.The lemma considers vectors sampled uniformly from a unit sphere in d dimensions.Source: B. Near orthogonality of random vectors · p. 17

C. Low-rank Hessians lead to low gradient confusion

Under a Lipschitz-Hessian assumption, the section relates low-rank random Hessians to low gradient confusion near a minimizer.

C. Low-rank Hessians lead to low gradient confusion

  • With a Lipschitz Hessian, each gradient is approximated near the minimizer by its Hessian at the minimizer times the weight vector, plus a quadratically bounded error.The section uses this local approximation to motivate the low-rank-Hessian argument.Source: C. Low-rank Hessians lead to low… · p. 18
  • If Hessians are sufficiently random and low-rank, gradient confusion may be small for many standard over-parameterized neural networks near the minimizer.The argument assumes each function has a minimizer at the origin and a Lipschitz Hessian; the authors characterize the suggestion as somewhat non-rigorous.Source: C. Low-rank Hessians lead to low… · p. 18

D.1. Proofs of theorems 3.1 and 3.2

This section supports the proofs of SGD convergence under low gradient confusion and probabilistic gradient-confusion bounds across network, initialization, and data conditions. It also supplies relevant Gaussian facts and discusses the small-weights assumption and its limitations during training.

D.1. Proofs of theorems 3.1 and 3.2

  • Under (A1) and (A2), SGD converges linearly to a neighborhood of the minima; under (A1), it converges to a neighborhood of a stationary point.Theorem 3.2 also gives an expected-gradient bound and an averaged bound over T iterations, with the latter including a term proportional to η/T.Source: §D.1 · pp. 19–21, §D.2 · p. 21

D.2. Proof of lemma D.1

  • For square or logistic loss, Lemma D.1 bounds each layer's output gradient by 1 and gives ζ0 = 2√β for the loss-derivative gradient bounds.The lemma assumes inputs have norm at most 1 and the network weights satisfy assumption 1.Source: §D.2 · p. 21

D.3. Proofs of theorem 5.1 and corollary 5.1

  • Theorem 5.1 establishes a probabilistic gradient-confusion bound for weights satisfying assumption 1, using bounded gradients and nonnegative expected gradient inner products.The proof bounds the norm of the gradient of the confusion function by 4ζ0^2(β + 2)^2; the supplied theorem statement omits its probability expression.Source: §D.3 · pp. 22–23

D.3.1. PROOF OF COROLLARY 5.1

  • Corollary 5.1 extends the gradient-confusion bound uniformly across a ball around a selected weight point when data are sampled uniformly from the unit sphere.Its proof uses a Lipschitz bound and an ε-net argument; the supplied corollary statement omits the probability expression.Source: §D.3.1 · pp. 23–24

D.4. Proof of theorem 4.1

  • Theorem 4.1 gives probabilistic gradient-confusion bounds for strategy 4.1, both for fixed bounded inputs when η > 4 and for inputs sampled from the unit sphere for every η > 0.The proof bounds the gradient of the gradient-inner-product function and lower-bounds its expectation; the supplied theorem statements do not show the probability expressions.Source: §D.4 · pp. 24, 26

D.5. Proof of Theorem 6.1

  • The proof of Theorem 6.1 combines nonnegative expected gradient inner products with a bound of 2 on the gradient norm of that inner product.The expectation condition follows from the dataset's i.i.d. sampling on a d-dimensional unit sphere.Source: §D.5 · p. 26

E. Technical lemmas

  • The technical lemmas state concentration bounds for differentiable Lipschitz functions of a sphere-sampled vector and of two independent sphere-sampled vectors.The supplied passages identify these bounds but omit their formulas.Source: E. Technical lemmas · p. 27
  • Normalized Gaussian coordinates have mean 0 and second moment 1/d, and the proofs also invoke concentration for differentiable Lipschitz functions of i.i.d. Gaussian variables.The mean-zero property follows from spherical symmetry; the concentration lemma is stated for coordinates distributed as N(0, ν²).Source: E. Technical lemmas · pp. 27–28

F. Additional discussion of the small weights assumption (assumption 1)

Related papers

Loading 1904.06963v5…