Optimization for deep learning: theory and algorithms

Ruoyu Sun

Source-linked AI summary

Optimization for deep learning: theory and algorithms

Ruoyu Sun

arXiv:1912.08957v1Dec 19, 2019cs.LGmath.OCstat.ML

TL;DR

Training neural networks raises questions about stability, optimization speed, and global solution quality. This article surveys neural-network-specific training mechanisms, generic optimization algorithms, and global-landscape results, concluding that theory already informs several practical designs while retaining important limitations.

Problem
The article addresses how neural networks can be trained successfully despite challenges involving optimization convergence, training stability, and global solution quality.
Method
The article synthesizes theory and algorithms for initialization, normalization, SGD, adaptive methods, distributed training, and global neural-network optimization.
Results
Theory provides understanding of initialization and over-parameterization and has informed practical algorithms including initialization schemes, batch normalization, Adam, and CNTK.
Takeaways & Limitations
The survey shows that optimization theory can guide neural-network algorithm design while also identifying empirical phenomena such as mode connectivity and lottery tickets.
Takeaways & Limitations
Over-parameterization cannot eliminate bad local minima, and SGD theory often relies on diminishing step sizes although constant learning rates work well in many cases.

Abstract

from arXiv · show

When and why can a neural network be successfully trained? This article provides an overview of optimization algorithms and theory for training neural networks. First, we discuss the issue of gradient explosion/vanishing and the more general issue of undesirable spectrum, and then discuss practical solutions including careful initialization and normalization methods. Second, we review generic optimization methods used in training neural networks, such as SGD, adaptive gradient methods and distributed methods, and theoretical results for these algorithms. Third, we review existing research on the global issues of neural network training, including results on bad local minima, mode connectivity, lottery ticket hypothesis and infinite-width analysis.

1 Introduction

The article surveys how neural-network architecture, optimization algorithms, and training techniques affect whether training converges, how quickly it converges, and the quality of the resulting solution. It emphasizes that current theory covers selected choices while leaving important architectural and generalization questions outside its scope.

Training ingredients: Successful neural-network training requires a suitable network, training algorithm, and training tricks.The article highlights architecture and activations, SGD-based optimization, initialization, normalization, and skip connections.
Open questions: The theoretical understanding of design choices is selective, with neural architecture identified as a major unresolved component.The article focuses on choices such as initialization, normalization, skip connections, over-parameterization, and SGD, while omitting architecture that is not yet theoretically understood.
Scope boundary: The survey focuses on supervised learning with feedforward neural networks and does not treat representation or generalization in detail.GANs, deep reinforcement learning, recurrent networks, attention, and Capsule architectures are also outside the stated scope.
Optimization decomposition: Optimization theory separates training concerns into convergence, convergence speed, and global solution quality.These categories are related and only roughly distinct; test accuracy and generalization lie beyond the optimization decomposition.
Survey scope: The survey reviews neural-network-specific mechanisms, generic optimization algorithms, and global optimization phenomena.Its coverage includes spectrum control, initialization, normalization, SGD, adaptive methods, distributed training, landscape analysis, mode connectivity, and lottery tickets.

2 Problem Formulation

The paper formulates supervised neural-network learning as choosing parameters for a feedforward network that maps inputs to predictions while minimizing a loss. It relates this problem to classical least-squares and matrix-factorization formulations.

2 Problem Formulation: Supervised learning provides input-output pairs, and neural-network optimization seeks parameters that predict each output from its corresponding input.Inputs and outputs may represent feature vectors, images, words, regression values, or classification labels.
2 Problem Formulation: A fully connected feedforward network composes weighted layers and activation functions, with θ collecting all weight matrices.The simplified model uses z_l = φ(W_l z_{l−1}) and sets input and output layer dimensions to d_x and d_y.
2 Problem Formulation: The recursive network expression omits bias terms for presentation, although practical networks include them.The practical recurrence is z_l = φ(W_l z_{l−1} + b_l).
2 Problem Formulation: Training minimizes a distance between the network prediction and the true output using a selected loss function.Quadratic loss is common for regression, while logistic loss is a popular binary-classification choice.
2 Problem Formulation: Although practical networks may use CNNs, attention, or other structures, the article mainly analyzes fully connected feedforward networks.The simplified model is used to study the optimization problem rather than to represent every practical architecture.
2.1 Relation with Least Squares: With one linear neuron and quadratic loss, the neural-network problem reduces to linear least squares.This classical problem supplies simple optimization intuition for neural-network analysis.
2.2 Relation with Matrix Factorization: With one hidden linear layer, quadratic loss, and identity inputs, the problem becomes matrix factorization.When the hidden width is smaller than the relevant dimensions, it yields a best rank-d_1 approximation of the target matrix.

3 Gradient Descent: Implementation and Basic Analysis

The section explains gradient descent and backpropagation for neural networks, then examines what classical convergence theory can and cannot guarantee. Neural-network nonlinearity creates a gap between standard global smoothness assumptions and the actual optimization problem.

Gradient methods: Gradient descent updates parameters by subtracting a learning-rate-scaled loss gradient, while SGD uses a randomly selected sample gradient.The per-sample objective is F_i(θ) = ℓ(y_i, f_θ(x_i)).
Backpropagation: Backpropagation efficiently computes all layerwise gradients through a forward pass and a backward pass.It reuses intermediate matrix products instead of separately recomputing the products required for every partial gradient.
Backpropagation: For a layer l, the partial gradient has the outer-product form ∂F_0/∂W_l = e_l(z_{l−1})^T.Backpropagated errors are defined recursively and paired with the preceding layer’s post-activation.
SGD implementation: Backpropagation can implement SGD by updating weights during the backward pass, with mini-batch SGD processing multiple samples together.The term backpropagation strictly refers to gradient computation but is also commonly used for the broader learning algorithm.
Meaning of convergence: Classical gradient-descent theory typically targets stationary points or vanishing gradients rather than global minima.Function-value convergence alone may end at an arbitrary finite value, whereas lower-bounded objectives and classical results can imply gradients converge to zero.
Basic convergence analysis: Standard smoothness theory assumes a global Lipschitz constant for the gradient, but such a constant does not exist for the neural-network problem considered.This creates a gap between classical assumptions and neural-network optimization.
Basic convergence analysis: If all iterates are bounded, gradient descent with a proper constant step size converges, but bounded Lipschitz constants do not ensure fast convergence.The relevant constants may still be exponentially large or small, motivating analysis of gradient explosion and vanishing.

4 Neural-net Specific Tricks

Successful training depends on controlling gradient and signal-propagation instabilities through principled initialization, normalization, architectural choices, and spectrum-aware analysis. The surveyed results connect these design choices to convergence, trainability at extreme depth, and practical performance.

Gradient explosion/vanishing: 2L−1|e| and 0.5L−1e illustrate exponentially exploding and vanishing gradients when layer derivatives are consistently large or small.The survey links these effects to slow convergence, poor conditioning, and difficulty selecting a step-size.
Gradient explosion/vanishing: Exponential-time convergence can arise when initialization places gradient descent outside the good basin and forces traversal through a flat region.In the scalar example, the good basin is near the global minimum, while initialization at w = −1 encounters vanishing gradients.
Careful initialization: Principled initialization replaces unreliable trial points by scaling weights with network structure, such as variance 1/fan-in for LeCun initialization.The fan-in dependence is presented as a way to obtain a tuning-free initial scaling across networks.
Careful initialization: Kaiming initialization can still yield signal variance of order exp(L/d), so increasing depth at fixed width may destabilize propagation.The result motivates analyzing both forward and backward signal behavior rather than relying only on a single initialization heuristic.
Spectrum and dynamical isometry: Dynamical isometry keeps Jacobian singular values near one, preserving back-propagated error strength; orthogonal initialization achieves this directly in equal-width deep linear networks.For nonlinear networks, infinite-width analyses identify activation- and initialization-dependent conditions for achieving dynamical isometry.
Spectrum and dynamical isometry: DeltaOrthogonal initialization trained a 10000-layer CNN without batch normalization or skip connections, although CIFAR10 accuracy was below state of the art.The result indicates that carefully chosen initialization can support ultra-deep optimization, while representation power at the initial point remains a constraint.
Normalization methods: BatchNorm adds differentiable normalization layers so layer pre-activations can target zero mean and unit variance without disrupting backpropagation.The surveyed normalization methods also include spectral normalization, which rescales weights by their largest singular value.
Changing neural architecture: Identity skip connections enabled 152-layer ResNet to reach a 3.57% top-5 error on ImageNet, while later architectures reached around 85% top-1 accuracy versus ResNet’s 78%.These results illustrate the practical impact of architectural changes, though the comparisons involve different architectures and associated training tricks.

5 General Algorithms for Training Neural Networks

The section surveys generic optimization algorithms for neural-network training, emphasizing SGD, adaptive methods, and distributed computation alongside their theoretical guarantees and practical trade-offs.

Optimization methods must balance faster convergence with improvement on the metric of interest, since optimization loss and unseen-data performance can differ.
SGD: SGD is widely used because mini-batches reduce memory demands and often converge faster than full-gradient descent in memory-constrained systems.
SGD: Constant-step-size SGD can remain in a confusion zone, while diminishing-step-size theory may poorly reflect practice; in realizable problems, constant-step-size SGD can converge.
SGD: Theoretical analysis shows SGD can be n/d to n times faster than GD under the stated eigenvalue conditions.
Adaptive gradient methods: Adaptive methods address unequal coordinate frequencies, while Adam is popular for hyperparameter insensitivity and rapid initial progress, despite well-tuned SGD sometimes outperforming it.
Adaptive gradient methods: Adam and RMSProp can diverge because their effective step sizes need not diminish; AMSGrad restores a convex-problem convergence guarantee, with similar or slightly worse empirical performance.
Adaptive gradient methods: Theoretical convergence and iteration-complexity analyses have been extended to several adaptive methods for non-convex optimization under verifiable conditions.
Distributed computation: Distributed optimization trained ResNet50 on ImageNet in 1 hour using 256 GPUs, achieving scaling efficiency 29/32 ≈0.906 with large-batch learning-rate scaling and warmup.

6 Global Optimization of Neural Networks (GON)

Global optimization of neural networks studies why deep-learning optimization can avoid the worst difficulties of general non-convex problems and reach global minima. The survey treats this as a distinct theoretical subarea motivated by the empirical success of neural networks.

Non-convexity is a central challenge because general non-convex problems may contain sub-optimal local minima.
Neural-network optimization appears unlike worst-case non-convex optimization, since finding global minima is no longer surprising in deep learning.
GON collects theoretical work on the global optimization landscape of neural networks.
The global view asks when algorithms converge to global minima, beyond local movement and convergence to stationary points.

6.1 Related areas

GON is connected to tractability, global optimization, and non-convex matrix or tensor factorization. These neighboring areas provide contrasting algorithmic and geometric perspectives on why some non-convex problems admit global solutions.

Tractability research studies the boundary between problems that can and cannot be solved efficiently, although the convex–non-convex boundary is not absolute.
Global optimization designs and analyzes methods for finding globally optimal solutions in general or structured non-convex problems.
Non-convex matrix and tensor factorization studies why problems such as matrix completion, phase retrieval, and tensor decomposition can reach global minima.
A key geometric property in matrix factorization is that every local minimum is global, motivating analogous structural questions for deep neural networks.
GON similarly seeks geometric structure in deep nonlinear neural networks viewed as generalizations of matrix-factorization problems.

6.2 Empirical exploration of landscape

Empirical studies portray neural-network landscapes as more favorable than generic non-convex landscapes, highlighting plateaus, low-barrier connections between solutions, and compressible subnetworks. However, the evidence remains largely empirical and the relationship between landscape shape and generalization is debated.

6.2 Empirical exploration of landscape: Early experiments reported no empirically observed bad local minima and identified plateaus as a larger challenge.
6.2 Empirical exploration of landscape: Loss along the line between initialization and convergence appeared similar to a one-dimensional convex function without bumps.
6.2 Empirical exploration of landscape: Mode connectivity studies found that two global minima can be joined by an almost equal-value path, though practical minima are often merely low-error solutions.
6.2.2 Model compression and lottery ticket hypothesis: Pruning can produce much smaller networks with only a small test-accuracy drop, but these networks often rely on weights inherited from a trained large model.
6.2.2 Model compression and lottery ticket hypothesis: Lottery-ticket experiments found subnetworks with selected initial weights that can match the performance of the original large network on some datasets.
6.2.2 Model compression and lottery ticket hypothesis: The pruning and lottery-ticket literature remains mostly empirical, without a clean general theoretical message.
6.2.3 Generalization and landscape: The claim that wide minima generalize better than sharp minima is debated, despite numerical evidence and continued use in optimization discussions.

6.3 Optimization Theory for Deep Neural Networks

Recent theory studies deep-network optimization through landscape properties and algorithmic dynamics, with positive results for linear, over-parameterized, and infinite-width settings alongside important negative results and assumptions.

Landscape analysis covers linear, over-parameterized, and modified networks, while also documenting negative results under particular activation, data, and structural assumptions.
Deep linear networks: For deep linear networks with quadratic loss and suitable rank conditions, every local minimum is a global minimum.
Deep over-parameterized networks: With sufficient last-layer width, fully connected networks can lack spurious valleys or set-wise strict local minima under mild data and activation assumptions.
Deep over-parameterized networks: Over-parameterization cannot eliminate bad local minima: arbitrarily wide networks can still contain sub-optimal local minima, although bad basins may be absent.
Algorithmic analysis: Gradient dynamics remain difficult to analyze, but balanced initialization and suitable stepsizes yield polynomial-time convergence for some deep linear problems, while infinite-width limits produce constant positive-definite NTK matrices.
Algorithmic analysis: NTK formulas enable empirical kernel-gradient-descent studies, including 77% test accuracy on CIFAR10 with global average pooling.

6.4 Research in Shallow Networks after 2012

After 2012, shallow-network research was organized by landscape versus algorithmic analysis and by network class, producing results on connected sublevel sets, bad basins, local minima, and training dynamics.

The survey groups shallow-network work by landscape or algorithmic analysis and by neuron, 2-layer, or 1-hidden-layer structure.
Global landscape: Connected sublevel sets in deep linear and 1-hidden-layer ultra-wide ReLU networks imply no spurious valley, but do not imply that every local minimum is global.
Global landscape: For 1-hidden-layer networks, results include no spurious valleys under low intrinsic dimension, partial global-minimum guarantees for positive homogeneous activations, and redesigned losses with only global minima.
Algorithmic analysis: Algorithmic studies analyze SGD and gradient descent for single-neuron, 2-layer, and 1-hidden-layer networks under varied activation, initialization, width, and data assumptions.

7 Concluding Remarks

The survey finds meaningful theoretical progress on initialization, over-parameterization, and algorithm design, but emphasizes that major gaps remain in explaining architecture, Adam, and out-of-distribution performance.

Theory now gives a good understanding of initialization’s effect on stable training and some understanding of over-parameterization’s effect on the landscape.
Theory has helped design optimization algorithms, but many performance-relevant components remain poorly understood, including detailed architecture and Adam.
Current theory remains far from reliably predicting algorithm performance, especially outside classification settings.

A Discussion of General Convergence Result

General convergence theory for neural-network optimization relies on boundedness, smoothness, and related assumptions, but these conditions are difficult to guarantee or use cleanly in generic non-convex networks.

Convergence analysis must distinguish reaching stationary points, obtaining fast convergence, and reaching low objective values; iterate convergence adds further concerns.
Kurdyka-Lojasiewicz conditions can help rule out multiple limit points, but rigorous generic arguments for neural-network optimization remain difficult.
Excluding divergent iterates may require compact level sets, regularizers, or ball constraints, but suitable regularizers can be impractical and constrained SGD analysis is complicated.
Lipschitz constants: Neural-network objectives lack global gradient-Lipschitz constants, making local-constant stepsizes attractive but difficult to analyze because stepsizes may shrink too quickly.
Lipschitz constants: Within a bounded region, proving that iterates remain inside the region is difficult for general non-convex functions, and bounded Lipschitz constants do not ensure fast convergence.
A posterior bounded-iterate assumption yields gradient convergence for gradient descent with a proper constant stepsize, but it can be verified only after running the algorithm.

B Details of Batch Normalization

Batch normalization transforms layer inputs using mini-batch statistics, learnable parameters, and inference-time training statistics. The construction changes the objective’s sample decomposition and has theoretical limitations in higher dimensions.

BatchNorm operation: Batch normalization maps pre-activation inputs to normalized outputs using learnable γ and β parameters and a fixed small ε.The operation is differentiable and is inserted before each nonlinear transformation layer.
Theoretical limitation: Current proofs do not generalize cleanly to high-dimensional problems because they rely heavily on one-dimensional structure.The authors characterize these proofs as limited and not broadly interesting.
BatchNorm operation: In high-dimensional networks, normalization applies separately to each pre-activation feature while aggregating statistics across samples.This aggregation couples the samples used to compute the normalization statistics.
Mini-batch implementation: Mini-batches make BatchNorm practical by jointly processing N inputs, computing their statistics, and restoring objective decomposition across mini-batches.The resulting network produces N predictions jointly, enabling mini-batch stochastic gradient methods.
Inference stage: At inference, the network uses training-data means and variances so it can predict each new test sample individually.This avoids requiring a mini-batch of test samples at prediction time.

C Theoretical Complexity of Large-scale Optimization Methods

Large-scale optimization methods improve gradient descent through parallelism, acceleration, decomposition, or second-order information. Their benefits can be compared through epoch complexity and computation time, with gains depending on conditioning, data structure, and hardware.

Common framework: Epoch complexity provides a common basis for comparing optimization methods while avoiding confusion from different per-iteration costs.The survey uses O(κ log 1/ϵ) for strongly convex GD and O(β/ϵ) for convex problems as prototype rates.
Parallel computation: Parallel computation reduces per-epoch cost rather than necessarily improving overall convergence speed.For an n-dimensional least-squares matrix-vector product, serial cost O(n^2) can fall to as little as O(log n) in a parallel model.
Fast gradient methods: Fast gradient methods achieve O(√κ log 1/ϵ), saving a factor of √κ over GD’s O(κ log 1/ϵ) rate for strongly convex problems.Conjugate gradient, heavy ball, and accelerated gradient methods attain this rate for convex quadratic problems.
Decomposition methods: Randomized coordinate descent has epoch complexity O(κ_D log 1/ϵ), improving over GD by a factor of λ_max/λ_avg between 1 and d.The condition parameter κ_D uses the average and minimum eigenvalues of the coefficient matrix.
Decomposition methods: SVRG and SAGA achieve O(nκ_D log 1/ϵ) epoch complexity, described as 1 to n times faster than GD.When n = d, this complexity matches randomized coordinate descent for least-squares problems.
Method comparison: A benchmark summary gives computation times O(nκ log 1/ϵ) for GD, O(n√κ log 1/ϵ) for accelerated methods, and O(nκ_D log 1/ϵ) for SVRG or randomized coordinate descent.BFGS and BB may improve κ to other parameters, but those parameters are described as unclear; mixed methods are theoretically harder to analyze.