Optimization for deep learning: theory and algorithms

1 Introduction

• Successful neural-network training requires a suitable architecture, training algorithm, and training tricks, including initialization, normalization, and skip connections.The article highlights convolutional architectures, ReLU or other activations, SGD with tuned step sizes, momentum or adaptive stepsizes, and normalization for deeper networks.Source: §1 · pp. 1–2
• The survey focuses on supervised feedforward networks and examines how neural-network parameterization affects optimization, while leaving representation and generalization largely outside its scope.It emphasizes theoretical results for optimization and notes that architecture remains difficult to understand, whereas initialization, normalization, skip connections, over-parameterization, and SGD have established insights.Source: §1 · p. 2

1.1 Big picture: decomposition of theory

• Optimization theory is decomposed into making training converge, accelerating convergence, and obtaining solutions with low objective value, distinct from achieving test accuracy.The broader supervised-learning error is divided into representation, optimization, and generalization error, while the article’s optimization partition is approximate because its boundaries overlap.Source: §1.1 · p. 3

1.2 Outline

• The article proceeds from problem formulation and back propagation to neural-network-specific methods, generic nonconvex optimization algorithms, and global optimization research.Later sections cover gradient explosion/vanishing and spectrum control, initialization and normalization, SGD and adaptive methods, distributed and second-order methods, mode connectivity, lottery tickets, and infinite-width analysis.Source: §1.2 · p. 4

2 Problem Formulation

• Supervised learning uses samples (x_i, y_i) to learn a mapping from inputs to outputs, where outputs may support regression or classification.Source: §2 · p. 4
• A neural network f_θ maps each input x to a predicted output ˆy, with θ collecting the network’s layer-weight matrices.Source: §2 · p. 4
• The fully connected network is expressed recursively as z_0 = x and z_l = φ(W_lz_{l−1}), with biases omitted for simplicity although practical networks include them.Source: §2 · p. 4
• Training selects parameters to minimize a distance between predictions and targets, commonly using quadratic loss for regression and logistic loss for binary classification.Source: §2 · pp. 4–5
• Although practical models include CNNs and attention layers, the article primarily analyzes fully connected networks, with occasional CNN results.Source: §2 · p. 5

2.1 Relation with Least Squares

• With one linear neuron and quadratic loss, the neural-network problem reduces to least squares, which supplies optimization insight because it is a simple neural-network case.Source: §2.1 · p. 5

2.2 Relation with Matrix Factorization

• With one hidden linear layer, quadratic loss, and identity input data, the problem becomes matrix factorization; when d_1 < min{n, d_y}, it yields the best rank-d_1 approximation of Y.Source: §2.2 · p. 5

3 Gradient Descent: Implementation and Basic Analysis

• Gradient descent updates parameters using a learning rate and loss gradient, while SGD randomly selects a sample and applies its per-sample gradient update.The section focuses on simple GD and SGD before treating SGD in more detail later.Source: §3 · p. 6

3.1 Computation of Gradient: Backpropagation

• Backpropagation computes all layer gradients by reusing forward activations and backward errors in one forward and one backward pass, and supports SGD and mini-batch SGD updates.The resulting layer gradient has the form ∂F0/∂W_l = e_l(z_{l−1})^T, avoiding the O(L^2) matrix multiplications of naive computation.Source: §3.1 · p. 7

3.2 Basic Convergence Analysis of GD

• With a proper constant stepsize and bounded iterates, GD drives gradients toward zero, but global Lipschitz-gradient assumptions generally fail for neural-network objectives.Classical results also show that a constant stepsize below 2/β yields stationary limit points and gradient convergence when a global β exists; bounded Lipschitz constants do not ensure fast convergence.Source: §3.2 · pp. 8–9

4.1 Possible Slow Convergence Due to Explosion/Vanishing

• Gradient explosion or vanishing amplifies or attenuates back-propagated signals, causing slow convergence through poor conditioning and difficult step-size selection.In a scalar example, gradients scale as 2^(L−1)|e| when all weights equal 2 and as 0.5^(L−1)e when they equal 1/2.Source: §4.1 · pp. 9–10

4.2 Careful Initialization

• Initialization must place parameters in a good basin because naive zero, sparse, or random choices can fail across neural-network problems.LeCun initialization uses zero-mean weights with variance 1/fan-in, while Xavier initialization uses variance 2/(fan-in + fan-out) to balance forward and backward propagation.Source: §4.1 · p. 10, §4.2 · pp. 11–12
• Initialization analyses show that signal stability depends on width, depth, activation, and propagation direction, limiting simple prescriptions for finite or general nonlinear networks.For Kaiming initialization in equal-width ReLU networks, E[ˆV] is roughly exp(L/d); infinite-width analyses require case-specific variance choices, while narrow networks can behave differently.Source: §4.2 · p. 13
• Dynamical isometry seeks input-output Jacobian singular values near 1, preserving back-propagated error and enabling depth-independent or ultra-deep training under suitable initialization.Orthogonal initialization achieves exact isometry in equal-width deep linear networks; DeltaOrthogonal methods trained a 10000-layer CNN without batch normalization or skip connections, though CIFAR10 accuracy was not state-of-the-art.Source: §4.2 · pp. 13–14
• Spectrum computations reveal large Hessian outlier eigenvalues in shallow networks and ImageNet ResNets, while practical training has a relatively small local gradient Lipschitz constant.Ghorbani et al. [73] used stochastic Lanczos quadrature to estimate large-scale spectral densities and confirmed the outlier-eigenvalue finding of [181].Source: §4.2 · p. 15

4.3 Normalization Methods

• Normalization modifies the network throughout optimization rather than only changing its initial point, with batch normalization [92] presented as a standard representative method.Source: §4.3 · p. 15
• BatchNorm adds a differentiable nonlinear transformation that normalizes layer pre-activations while remaining compatible with backpropagation.It avoids directly imposing normalization constraints, although naive post-update normalization may disrupt gradient-descent convergence.Source: §4.3 · p. 15
• Normalization methods differ in what they normalize: BatchNorm uses row segments, layer normalization columns, group normalization submatrices, and weight or spectral normalization weight matrices.Alternatives can outperform BatchNorm when mini-batches are small or in settings such as recurrent networks and generative adversarial networks.Source: §4.3 · p. 16

4.4 Changing Neural Architecture

• ResNet-152 with identity skip connections and BatchNorm improved ImageNet top-5 error to 3.57%, establishing ultra-deep architectures as practically effective [88].ResNet addressed the difficulty of training networks beyond roughly 20–30 layers, where a 56-layer VGG performed worse than a 20-layer network.Source: §4.4 · pp. 16–17
• ResNet skip connections support signal propagation: dynamic isometry can hold for any activation and bi-unitary random initialization, unlike non-residual networks [208].Theoretical explanations also include improved optimization landscapes, signal propagation, and generalization; Fixup initialization achieves good ImageNet performance without BatchNorm [245].Source: §4.4 · pp. 17–18

4.5 Training Ultra-Deep Neural-nets

• Networks exceeding 1000 layers can reach reasonable image-classification accuracy using proper initialization, residual architectures, and BatchNorm, or alternatives such as Fixup [245].Carefully chosen initialization alone can train ultra-deep CNNs, though the cited work does not achieve the best test accuracy.Source: §4.5 · p. 18

5 General Algorithms for Training Neural Networks

• Optimization methods should be accepted only when faster convergence also passes a performance check on the metric of interest, which may differ from training loss.A faster method does not necessarily generalize better or improve the target metric.Source: §5 · p. 19

5.1 SGD and learning-rate schedules

• SGD uses mini-batches because of memory constraints and often converges faster than full-gradient descent in memory-limited systems.Learning-rate practice includes constant or decayed schedules, warmup, and cyclical rates; SGDR was reported to converge several times faster than SGD in image classification [196].Source: §5.1 · pp. 19–20

5.2 Theoretical analysis of SGD

• SGD theory explains constant learning rates through realizability, where zero optimal loss can provide automatic variance reduction, while classical diminishing-rate analyses may poorly reflect practice.For a realizable least-squares example, single-sample SGD is n/d to n times faster than GD, though practical acceleration depends on multiple factors.Source: §5.2 · pp. 21–22

5.3 Momentum and accelerated SGD

• Momentum methods are widely used for practical speed, but naive stochastic momentum lacks a general theoretical acceleration guarantee, especially for non-convex neural-network problems.Acceleration can arise from variance reduction or additional problem structure, whereas many general non-convex accelerated methods remain mainly theoretical and unused in practice.Source: §5.3 · pp. 22–23

5.4 Adaptive gradient methods: AdaGrad, RMSProp, Adam and more

• Adaptive methods adjust coordinate-wise steps and are popular because Adam offers rapid initial progress and relative hyperparameter insensitivity, although well-tuned SGD can achieve better training and test error.AdaGrad was motivated by sparse, unbalanced data; RMSProp and Adam use exponentially weighted gradient information, while Adam and RMSProp can diverge even on convex problems and AMSGrad restores a convergence guarantee under stated conditions.Source: §5.4 · pp. 24–25

5.5 Large-scale distributed computation

• Distributed training can approach linear speedup only when communication, synchronization, and data-structure effects permit it, while preserving test accuracy remains essential.ResNet50 training reached 1 hour on 256 GPUs with scaling efficiency 29/32 ≈0.906 using large batches, learning-rate scaling, and gradual warmup [80].Source: §5.5 · p. 25
• Large-scale follow-up systems trained ResNet50 on ImageNet in 14 minutes or 1.2 minutes using larger machines, warmup, LARS, learning-rate choices, and label smoothing, with 75%–77% validation accuracy.The reported 1.2-minute result used 2048 V100 GPUs and a mini-batch size of 81920 [230].Source: §5.5 · p. 26

5.6 Other Algorithms

• Other approaches include tuning-free schedules, Hessian-free and stochastic quasi-Newton methods, natural gradients, and K-FAC, with a continuum between first- and second-order methods.Second-order methods may use efficient Hessian-vector products, Fisher-information scaling, or block-diagonal Kronecker-factorized approximations.Source: §5.6 · p. 26
• K-FAC achieved 75% top-1 accuracy on ImageNet in 35 epochs, suggesting second-order methods may regain competitiveness despite SGD’s dominance and implicit regularization.Bottou and Bousquet provided theoretical justification for first-order methods in large-scale machine learning, while Osawa et al. [163] showed recent promise for K-FAC.Source: §5.6 · p. 27

Motivation

• GON studies why neural-network optimization can find global minima despite the general difficulty of non-convex problems with sub-optimal local minima.The recent success of neural networks suggests their optimization is far from a worst-case non-convex problem.Source: §6 · p. 27

Scope

• The section takes a global view beyond local convergence, asking when algorithms reach global minima, whether bad local minima exist, how initialization affects convergence, and which landscape properties matter.Earlier sections addressed gradient explosion/vanishing and convergence to local minima or stationary points.Source: §6 · p. 27

Tractable problems

• Optimization research studies the boundary between tractable and intractable problems, traditionally associated with convex versus non-convex formulations, although some non-convex problems admit convex reformulations.The article suggests some neural-network problems may be tractable, while noting that tractability remains unclear and lacks a framework as complete as semi-definite programming.Source: §6.1 · pp. 27–28

Global optimization

• Global optimization designs and analyzes algorithms for globally optimal solutions, covering general non-convex search, problem-specific methods, and structural analyses of particular non-convex problems.Examples include simulated annealing, evolutionary methods, and analyses of specific problems such as those cited in and.Source: §6.1 · p. 28

Non-convex matrix/tensor factorization

• Non-convex matrix/tensor factorization is the closest related area, studying why many problems—including matrix completion, phase retrieval, sensing, dictionary learning, and tensor decomposition—reach global minima easily.Its central geometric question is whether every local minimum is global, extending the optimization view of eigenvalue problems to broader factorizations and deep nonlinear neural networks.Source: §6.1 · p. 28

6.2 Empirical exploration of landscape

• Early experiments found no empirically bad local minima, identified plateaus as a greater challenge, and observed nearly convex loss along initialization-to-solution line segments.These results suggested neural-network landscapes are substantially nicer than previously expected.Source: §6.2 · p. 28

6.2.1 Mode connectivity

• Two independently trained low-error solutions can be connected by an almost equal-value path, providing empirical evidence for mode connectivity in deep networks.Stronger path-finding experiments validated this phenomenon on CIFAR10 and CIFAR100, while related connectivity results were proved for simpler and deep networks.Source: §6.2.1 · p. 29

6.2.2 Model compression and lottery ticket hypothesis

• Pruning can produce much smaller networks with little test-accuracy loss, while lottery tickets identify subnetworks and half-random initializations that can match large-network performance on some datasets.Training pruned networks from scratch often performs substantially worse; the lottery-ticket procedure requires modification for larger datasets such as ImageNet, and its underlying theory remains unresolved.Source: §6.2.2 · pp. 29–30

6.2.3 Generalization and landscape

• The conjecture that flat, wide minima generalize better remains contested because sharp minima may become wide under re-parameterization, and rigorous flatness definitions are still challenging.Researchers have proposed alternative flatness metrics and optimization methods such as entropy-SGD that explicitly seek wider minima.Source: §6.2.3 · pp. 30–31

6.3.1 Global landscape analysis of deep networks

• Global landscape results cover linear, over-parameterized, modified, and negative cases, showing that favorable geometry does not universally eliminate optimization failures.The main positive results concern linear networks, over-parameterized networks, and modified problems, while counterexamples establish bad local minima under various assumptions.Source: §6.3.1 · pp. 31, 33
• For deep linear networks, under full-rank and dimensionality conditions, every local minimum is global, with stronger necessary-and-sufficient characterizations for global stationary points.These results include analyses by Choromanska et al. [42], Kawaguchi [102], Lu and Kawaguchi [134], Laurent and James, Zhang [247], and others.Source: §6.3.1 · pp. 31–32
• Over-parameterization can remove spurious valleys and set-wise strict local minima when the last layer is sufficiently wide, but arbitrarily wide networks can still have sub-optimal local minima.Nguyen et al. [157] and Li et al. [118] prove the positive result under different activation assumptions, whereas Ding et al. shows that over-parameterization eliminates bad basins rather than all bad minima.Source: §6.3.1 · p. 32
• Modified neural-network problems can eliminate bad local minima, yet gradient descent may diverge, so absence of bad minima excludes only one type of failure.Liang et al. [124] and Kawaguchi et al. [103] study binary and multi-class modifications, while [103] gives divergence examples.Source: §6.3.1 · p. 33

6.3.2 Algorithmic analysis of deep networks

• Gradient descent converges in polynomial time for certain deep linear problems when initialization is balanced and near the target, while other results require separability, a low initial objective, or small adaptive stepsizes.Ji and Telgarsky [98] additionally show normalized weights converge to rank-1 matrices, and Shin finds faster convergence for deeper networks under conditions.Source: §6.3.2 · pp. 33–34
• In the infinite-width limit, NTK dynamics become kernel gradient descent with a constant positive-definite kernel under suitable initialization, activation, and data assumptions.Jacot et al. [94] derive a recursively computable limiting kernel; related finite-width analyses prove global convergence with Gaussian initialization and sufficiently small stepsizes, while CNTK achieves 89% test accuracy on CIFAR10.Source: §6.3.2 · pp. 34–35

Global landscape of 1-hidden-layer neural-nets

• For 1-hidden-layer networks, analyses establish connected sublevel sets or no spurious valleys in several settings, while specialized constructions yield global-minimum guarantees.Freeman and Bruna [67] showed connected sublevel sets for deep linear and ultra-wide ReLU networks, which excludes spurious valleys but does not imply every local minimum is global.Source: §6.4 · pp. 36–37

Algorithmic analysis of 2-layer neural-nets

• For 2-layer networks, GD and SGD analyses span single neurons, fixed-second-layer models, and over- or under-parameterized settings, with guarantees under Gaussian, separable, and parameter-count conditions.Oymak and Soltanolkotabi [165] proved global GD convergence when parameters exceed O(n^2), while other results establish polynomial-time convergence for Gaussian inputs or analyze failures and specialized architectures.Source: §6.4 · p. 37

Algorithmic analysis of 1-hidden-layer neural-nets

• For trainable-second-layer 1-hidden-layer networks, analyses cover tensor methods, alternating minimization, spectral methods, and GD/SGD under varied normalization, initialization, and sample-dimension conditions.Du et al. [57] found that SGD can converge to a global or bad local minimum depending on initialization; Vempala and Wilmes [214] obtained convergence to the best degree-k polynomial approximation with n^O(k) neurons, with a matching lower bound.Source: §6.4 · pp. 37–38

Progress in understanding and design

• Theory has clarified initialization’s effect on stable training, partly explained overparameterized landscapes, and guided algorithms including initialization schemes, batch normalization, and Adam.CNTK illustrates how theoretical analysis can motivate a practical tool.Source: §7 · p. 38

Open empirical phenomena

• Empirical phenomena such as mode connectivity and the lottery ticket hypothesis remain open for deeper theoretical study.Source: §7 · p. 38

Remaining challenges

• Many performance-relevant components, including detailed architecture and Adam, remain poorly understood, limiting reliable predictions across algorithms and settings beyond classification.Source: §7 · p. 38

Future opportunities

• Strong theory-driven algorithms for image classification appear unlikely, motivating opportunities in adversarial robustness and deep reinforcement learning.Source: §7 · p. 38

• Convergence to stationary limit points does not rule out multiple limit points or the absence of any limit point.These are identified as two distinct undesirable cases, (U1) and (U2).Source: A Discussion of General Convergence… · p. 39
• The Kurdyka-Lojasiewicz condition can help exclude multiple limit points for descent algorithms, but rigorous generic neural-network arguments remain difficult [243],.Source: A Discussion of General Convergence… · p. 39
• Eliminating divergent iterates often requires compact level sets, regularizers, or ball constraints, but these may be impractical or make constrained convergence analysis difficult.For neural networks, the needed regularizer can be a degree 2L polynomial for quadratic loss; tailored analysis may therefore be necessary.Source: A Discussion of General Convergence… · p. 39
• Neural-network objectives lack global Lipschitz constants, while local-Lipschitz stepsizes can shrink too quickly, provide only local upper bounds, or fail to keep iterates inside a compact region, [175], [40].For general non-convex functions, proving that iterates remain in a ball is difficult.Source: A Discussion of General Convergence… · pp. 39–40
• Assuming bounded iterates yields GD convergence with a proper constant stepsize and gradient tending to 0, but this posterior assumption is verifiable only after running the algorithm.Constraints and regularizers intended to enforce boundedness introduce additional difficulties and require new problem-specific analysis.Source: A Discussion of General Convergence… · p. 40

First trick of BatchNorm

• BatchNorm adds learned γ and β parameters before each nonlinear layer, preserving representation power while defining a differentiable transformation.The resulting network includes the new parameters {γ_l, β_l} across layers.Source: B Details of Batch Normalization · p. 40

Limitations

• Current proofs for the discussed BatchNorm behavior rely heavily on one-dimensional structure and lack a clean generalization to high-dimensional problems.The limitation is explicitly identified as a proof-generalizability issue.Source: B Details of Batch Normalization · p. 40

First trick of BatchNorm

• For high-dimensional networks, BatchNorm normalizes each pre-activation feature separately using means and variances aggregated across samples.This changes the objective because sample-wise decomposition no longer applies directly.Source: B Details of Batch Normalization · p. 41

Inference stage

• At inference, BatchNorm uses means and variances computed from training data so predictions can be made for individual unseen samples.This avoids requiring a test mini-batch during deployment.Source: B Details of Batch Normalization · p. 41

Baseline convergence

• For strongly convex problems, gradient descent requires O(κ log 1/ϵ) epochs to reach error ϵ, with epoch costs comparable between batch GD and SGD.The corresponding convex-problem rate is O(β/ϵ), but the discussion focuses on strongly convex problems.Source: C Theoretical Complexity of… · p. 41

Parallel computation

• Parallel computation reduces per-epoch time rather than convergence speed, with matrix-vector products potentially decreasing from O(n^2) serial time to O(log n) in an idealized model.Hardware, synchronization, and communication costs affect realized performance; using K machines for nearly K-times speedup is a major deep-learning research direction.Source: C Theoretical Complexity of… · p. 42

Fast gradient methods

• Fast gradient methods improve the strongly convex rate from O(κ log 1/ϵ) to O(√κ log 1/ϵ), saving a factor of √κ.Conjugate gradient, heavy ball, and accelerated gradient attain this rate for convex quadratic problems, while only accelerated gradient is known to do so generally.Source: C Theoretical Complexity of… · p. 42

Decomposition methods

• Decomposition methods exploit smaller sample or coordinate updates: randomized CD is 1 to d times faster than GD, while SVRG and SAGA are 1 to n times faster.Mini-batch or block methods have a maximal acceleration ratio roughly equal to the number of mini-batches or blocks.Source: C Theoretical Complexity of… · pp. 42–43

Second-order methods

• Second-order methods, including BFGS, BB, AdaGrad, RMSProp, and Adam, may depend less on κ, although their theoretical advantage over GD remains difficult to justify.Under the benchmark setup, parallel computation can reach O(κ log n log 1/ϵ), accelerated gradients O(n√κ log 1/ϵ), and SVRG or randomized CD O(nκD log 1/ϵ).Source: C Theoretical Complexity of… · p. 43