Optimization Methods for Large-Scale Machine Learning

• Machine learning relies on mathematical optimization to compute parameters that perform well on unseen data, with increasingly challenging applications motivating more broadly applicable methods.Source: §1 · p. 3
• The paper argues that traditional nonlinear optimization techniques typically falter at large scale and should be secondary to methods respecting the problem’s statistical structure.Source: §1 · p. 3
• Two case studies span convex problems from text classification and highly nonlinear, nonconvex problems from deep neural networks.Source: §1 · pp. 3–4
• For large-scale machine learning, stochastic gradient, proposed by Robbins and Monro, is the core strategy, while batch-oriented gradient methods suit smaller problems.Source: §1 · p. 4
• The review organizes newer methods around stochastic gradient through noise reduction, approximate second-order information, and regularization, emphasizing computational trade-offs and theoretical properties.Source: §1 · p. 4

2 Machine Learning Case Studies

• The case studies focus on very large datasets and many model parameters, illustrating why machine-learning optimization problems are difficult to solve.They connect optimization to selecting prediction functions in state-of-the-art systems across text classification and perceptual tasks.Source: §2 · p. 4

2.1 Text Classification via Convex Optimization

• Text classification uses high-dimensional sparse document features with linear prediction, replacing discontinuous accuracy optimization by convex surrogate losses and regularization.The RCV1 representation uses d = 47,152 vocabulary features for news stories typically containing fewer than 1,000 words; cross-validation selects among candidate models.Source: §2.1 · pp. 5–6

2.2 Perceptual Tasks via Deep Neural Networks

• DNNs achieve major perceptual-task advances despite highly nonlinear, nonconvex training problems that are solved approximately with gradient methods and back propagation.Speech-recognition DNNs significantly outperform traditional GMMs, while CNNs became state-of-the-art for visual object recognition.Source: §2.2 · pp. 7, 9, Figure 2.2 · p. 8, Figure 2.4 · p. 9
• Contemporary fully connected DNNs can require tens of millions of parameters, hundreds of millions of examples, and weeks of computation, making initialization and conditioning practically important.A typical speech-recognition network has five to seven layers; CNN training can also involve about 60 million parameters and a few million labeled images.Source: §2.2 · pp. 7–9

2.3 Formal Machine Learning Procedure

• Formal learning seeks prediction functions with low expected rather than merely empirical risk, requiring a suitable function family and an optimizable selected member.Uniform laws of large numbers and VC dimension explain how sample size and family capacity control the empirical–expected risk gap.Source: §2.3 · pp. 10–11
• Structural risk minimization balances empirical fit against generalization by selecting nested function families, while increasing family size lowers training risk but can widen the risk gap.Regularized empirical risk, expanded feature dictionaries, higher-degree polynomials, and wider DNN layers provide alternative ways to impose such structures.Source: §2.3 · pp. 11–12
• Structural risk minimization lowers empirical risk as C increases, but the bound on the empirical–expected risk deviation also increases, with the best C increasing with sample size n.The procedure minimizes R_n(h) subject to Ω(h) ≤ C, and the optimal tradeoff depends on the number of examples.Source: Figure 2.5 · p. 12
• Early stopping can yield better expected risk than fully optimizing empirical risk, with stopping time playing a role analogous to the hyperparameter C.Prematurely stopping optimization provides a form of regularization comparable to structural risk minimization.Source: Figure 2.6 · p. 13

3.1 Formal Optimization Problem Statements

• Large-scale machine-learning optimization is framed through expected and empirical risks, with prediction functions parameterized by w and losses composed as f(w; ξ).Empirical risk is the practical objective when the data distribution is unknown; the notation supports single samples or sample sets.Source: §3.1 · pp. 13–14

3.2 Stochastic vs. Batch Optimization Methods

• SG uses one randomly selected sample per cheap iteration, while batch methods use full gradients that cost more but provide deterministic steps and access to advanced nonlinear optimization techniques.Batch computations can also benefit from parallel and distributed evaluation, whereas SG behavior is governed by the random sample sequence.Source: §3.2 · p. 15, §3.3 · p. 16

3.3 Motivation for Stochastic Methods

• SG is favored for large-scale learning because it exploits redundant or sufficient subsets of data, improves rapidly initially, and has total work proportional to 1/ϵ versus n log(1/ϵ) for batch gradient methods.Its stochastic directions can cause slowdown near a minimizer, but diminishing stepsizes can overcome oscillations; SG also retains a sublinear expected-risk rate when full expected gradients are unavailable.Source: §3.3 · pp. 17–19
• SG’s practical advantage is not universal: batch methods can eventually achieve lower training error, while SG is difficult to parallelize and communication-intensive in distributed settings.These limitations motivate methods combining stochastic efficiency with batch-like accuracy or parallelism.Source: §3.3 · pp. 17, 19

3.4 Beyond SG: Noise Reduction and Second-Order Methods

• Methods beyond SG are organized by noise reduction and second-order strategies, including mini-batches, dynamic sample sizes, gradient aggregation, quasi-Newton, Newton, and natural-gradient methods.Mini-batches reduce stochastic variance, ease stepsize tuning, and permit some parallelization; the two-dimensional roadmap is explicitly a useful guide rather than a literal classification.Source: §3.4 · pp. 20–21

4 Analyses of Stochastic Gradient Methods

• The generalized SG method generates independent random seeds, stochastic directions, and positive stepsizes, covering single-sample, mini-batch, gradient, Newton, quasi-Newton, and active-learning variants.Its theoretical results require a sufficiently positive expected angle between the stochastic direction and the true gradient, while allowing fixed or diminishing stepsizes.Source: §4 · pp. 21–22

4.1 Two Fundamental Lemmas

• Under Lipschitz-continuous gradients, the fundamental lemmas bound expected objective change through directional descent and the stochastic direction’s second moment.Sufficient descent and restricted variance make the descent term dominate, although balancing stepsize-induced decrease against the second-moment term remains critical.Source: §4.1 · pp. 23–24

4.2 SG for Strongly Convex Objectives

• For strongly convex objectives, fixed stepsizes yield expected linear convergence only to a neighborhood when stochastic-gradient noise persists, whereas noiseless or vanishing noise permits convergence to the optimum.A smaller fixed stepsize reaches a closer neighborhood but worsens the contraction constant; the analysis focuses on convergence in expectation.Source: §4.2 · pp. 26–27
• Halving the stepsize only after the suboptimality gap reaches its current threshold drives the expected gap to zero, with each halving requiring twice as many iterations and yielding an effective O(1/k) rate.The schedule decreases stepsizes sublinearly rather than at every iteration.Source: §4.2 · pp. 27–28, Figure 4.1 · p. 28
• Strong convexity enables contraction, but diminishing-stepsize SG requires β > 1/(cµ); underestimating β can leave the iterate more than 10^-2 from solution after 10^9 iterations.For constant stepsizes, the upper bound on the stepsize does not depend on c; initialization can reduce the asymptotic influence of the initial optimality gap.Source: §4.2 · pp. 29–30
• Mini-batching reduces stochastic-direction variance by 1/nmb but increases per-iteration cost nmb-fold, yielding comparable total computation to simple SG in one regime.This comparison does not always extend to larger batches because per-iteration costs and convergence rates trade off, and stepsizes cannot necessarily be increased proportionally.Source: §4.2 · p. 31

4.3 SG for General Objectives

• The nonconvex guarantees apply beyond stochastic gradients because the stochastic direction may also be a mini-batch gradient or Newton-like direction.The fixed- and diminishing-stepsize results retain the same assumptions on stochastic directions while dropping convexity of F.Source: §4.3 · pp. 31–32
• Under nonconvex objectives with fixed stepsizes, SG bounds average squared gradients, but gradient noise creates a limiting neighborhood whose size depends on the stepsize and variance.Smaller stepsizes can make the average gradient norm arbitrarily small, but slow its approach to the limiting distribution.Source: §4.3 · pp. 32–33
• With diminishing stepsizes satisfying (4.19), SG’s weighted average of squared gradient norms converges to zero even when gradient noise is present.Consequently, expected gradient norms cannot asymptotically remain far from zero, and the result also implies the corresponding lim-inf guarantee.Source: §4.3 · pp. 33–34

4.4 Work Complexity for Large-Scale Learning

• Under a time budget, batch computation grows at least linearly with sample size n, whereas stochastic computation is independent of n, so SG should use as many examples as possible.The optimization problem balances approximation, estimation, and optimization errors through the sample size n and optimization tolerance ϵ.Source: §4.4 · p. 35
• Simple SG reaches ϵ-optimality in time Tstoch(n, ϵ) ∼ 1/ϵ, achieving accuracy proportional to 1/Tmax and optimal error proportional to 1/Tmax.These rates are independent of n under the stated asymptotic error model, so the optimal strategy is to choose the largest feasible sample size.Source: §4.4 · p. 36
• SG optimization achieves lower expected error than batch optimization under the considered time budget, despite batch methods’ better dependence on ϵ.For batch optimization, choosing ϵ ∼ 1/Tmax yields error proportional to log(Tmax)/Tmax + 1/Tmax, but dependence on n dominates.Source: §4.4 · p. 36, Table 4.1 · p. 37

A Lower Bound

• SG matches the Ω(1/k) accuracy lower bound for algorithms using k noisy-oracle calls, up to constant factors, for both expected and empirical risk.The bound applies to strongly convex objectives and follows analyses of noisy gradient estimates.Source: A Lower Bound · pp. 36–37

4.5 Commentary

• SG’s asymptotic convergence guarantee is fragile because its stepsize constant must exceed a quantity inversely proportional to strong convexity, motivating locally adaptive algorithms.Squared ℓ2 regularization can provide a lower bound for strong convexity, but the regularization parameter should decrease as sample size grows.Source: §4.5 · p. 37
• SG’s implementation advantages from sparsity and GPUs erode under ill-conditioning, whose unfavorable constants grow with L/c and M/c.Adaptive rescaling using matrices that capture local curvature can improve both ratios.Source: §4.5 · pp. 37–38
• Distributed SG can reduce computation by a machine-count factor in principle, but frequent shared-parameter access creates communication overhead that may favor mini-batch methods.SG tolerates additional noise and relaxed synchronization, yet communication can exceed the extra per-iteration work of alternatives.Source: §4.5 · p. 38
• Gradient aggregation can achieve linear convergence for empirical risk, while dynamic sampling can match SG’s optimal asymptotic efficiency in big-data settings.These improvements exploit revisited training examples and apply to empirical risk rather than expected risk; dynamic sampling is discussed in §5.2 and aggregation in §5.3.Source: §4.5 · p. 38
• Regret bounds show that SG’s average loss is close to the best fixed parameter’s average loss, even for arbitrary noise sequences.With independent noise, martingale arguments recover traditional convergence results, whereas the regret bound remains meaningful under dependent or adversarial noise and connects probability, machine learning, and game theory.Source: §4.5 · p. 39

5 Noise Reduction Methods

• Noise reduction methods address stochastic-gradient error and can provide attractive practical and theoretical properties, including linear convergence with fixed stepsizes for several method classes.The reviewed classes include dynamic sampling, gradient aggregation, and iterate averaging, which reduce gradient-estimate or iterate-sequence noise in different ways.Source: §5 · p. 40

5.1 Reducing Noise at a Geometric Rate

• Geometrically decreasing stochastic-direction variance makes fixed-stepsize SG converge linearly in expected optimality gap under the stated assumptions.The admissible fixed-stepsize range is described as large enough not to be unrealistic in practical situations.Source: §5.1 · pp. 41–42

5.2 Dynamic Sample Size Methods

• Geometrically increasing mini-batch sizes reduce variance sufficiently for unbiased dynamic-sampling SG to achieve linear convergence on strongly convex objectives.Independent samples with bounded, equal stochastic-gradient variance establish the variance condition required by the geometric-rate result.Source: §5.2 · p. 43
• O(ϵ^-1) stochastic-gradient evaluations suffice for dynamic-sampling SG to obtain an ϵ-optimal solution, matching the stated complexity of diminishing-stepsize SG.The result applies under the specified stepsize, geometric growth parameter, and assumptions of Theorem 5.1.Source: §5.2 · p. 43
• For batch methods, sublinear convergence admits no efficient sampling rate, linear convergence requires geometric growth, and superlinear convergence requires slightly faster-than-geometric growth.These sampling-rate conditions are presented as criteria for minimizing overall computational complexity.Source: §5.2 · p. 44
• Preset sampling schedules require application-specific tuning of τ and may apply the full sample too early, making heuristic dynamic-sampling adaptations difficult.The practical implementation therefore motivates adaptive sample-size selection based on optimization information rather than a prescribed sequence.Source: §5.2.1 · pp. 44–45
• Adaptive sampling estimates variance or descent-direction quality to choose sample sizes, but a geometric-growth backup is needed because the adaptive rule alone lacks a geometric-rate guarantee.Dynamic sampling remains uncommon in machine learning, while a method that initially behaves like SG and later reduces variance is identified as a promising direction.Source: §5.2.1 · p. 45

5.3 Gradient Aggregation

• Gradient aggregation achieves linear rather than sublinear convergence on strongly convex finite-sum problems by trading increased computation or storage for lower-variance directions.The methods reuse or revise previously computed stochastic-gradient information, rather than continually computing more new information.Source: §5.3 · p. 46

5.3.1 SVRG

• SVRG uses a batch-gradient correction to form an unbiased, lower-variance estimator and achieves a linear rate under suitable stepsize and cycle-length choices.Each outer iteration costs 2m + n component-gradient evaluations, making SVRG much more expensive than SG and comparable to a full-gradient iteration; it is most effective at high training accuracy after SG’s early advantage.Source: §5.3.1 · pp. 46–47

5.3.2 SAGA

• SAGA stores component gradients to produce unbiased, lower-variance estimates with basic-SG per-iteration cost after initialization, while attaining a linear rate on strongly convex objectives.Its main drawback is storing n gradient vectors, although logistic and least-squares structure can reduce storage to one scalar per example; SAG has a related linear-rate approach but uses biased estimates.Source: §5.3.2 · pp. 47–48

5.3.3 Commentary

• For very large n, SVRG, SAGA, and SAG become comparable to batch algorithms and cannot beat SG, whereas aggregation may be superior when κ ≫ n.When κ is close to 1, SG can be clearly more efficient; aggregation methods may also be easier to tune in the favorable regime.Source: §5.3.3 · p. 49

Motivation

• Iterate averaging forms a less noisy auxiliary sequence because stochastic-gradient iterates oscillate around minimizers during optimization.The averaged sequence does not affect computation of the underlying stochastic-gradient iterates.Source: §5.4 · p. 49

Limitations

• Classical stepsizes diminishing at O(1/k) failed to provide the hoped-for improved convergence behavior of averaged iterates.This limitation motivated slower-decaying stepsizes in subsequent iterate-averaging analyses.Source: §5.4 · p. 49

Polyak–Juditsky averaging

• For strongly convex objectives, slower stepsizes of O(1/(k^a)) with a ∈ (1/2, 1) yield O(1/k) mean-squared error for averaged iterates, with an optimal asymptotic constant that eliminates ill-conditioning effects.The raw iterates achieve O(1/(k^a)); the optimal averaged-iterate behavior can resemble a second-order method, though it is difficult to realize in practice.Source: §5.4 · pp. 49–50

Extensions

• Iterate averaging has been incorporated into robust stochastic approximation, mirror-descent stochastic approximation, and Nesterov’s primal-dual averaging, whose gradient aggregation gives averaged iterates an O(1/k) convergence rate.These methods use averaging to permit longer steps while maintaining desired convergence rates.Source: §5.4 · p. 50

Motivation

• Second-order information can improve batch convergence rates or the constants in stochastic methods’ sublinear convergence rates by addressing nonlinearity and ill-conditioning.Stochastic methods still cannot achieve faster-than-sublinear convergence regardless of the re-scaling matrix, but careful approximate second-order re-scalings can benefit both stochastic and batch regimes.Source: §6 · pp. 50–51

Scale invariance

• For a strongly convex quadratic, Newton’s re-scaling reaches the unique minimizer in one iteration from any initial point, whereas full gradient generally requires many iterations.The cited choice is B = (∇2F(w1))^-1/2 with α1 = 1, yielding w2 = w∗.Source: §6 · p. 50

Taylor models

• Full gradient uses a first-order-accurate model, while Newton’s method repeatedly minimizes an exact second-order Taylor model when the Hessian is positive definite.The full gradient iteration corresponds to B^-2 = I, whereas Newton’s method uses B^-2 = ∇2F(wk).Source: §6 · p. 50

Methods and regimes

• The section covers Hessian-free Newton, quasi-Newton, Gauss-Newton, diagonal re-scalings, and natural gradient methods, with effectiveness varying across stochastic and batch regimes.Natural gradient is invariant to general invertible transformations, whereas Newton’s method is invariant to linear transformations.Source: §6 · p. 51, Figure 6.1 · p. 51

6.1 Hessian-Free Inexact Newton Methods

• Inexact Newton-CG avoids explicit Hessian formation by using Hessian-vector products, and sufficiently accurate solves can achieve superlinear convergence.Each product costs at least a gradient evaluation, but fewer CG iterations can offset this additional per-iteration work.Source: §6.1 · p. 52
• Hessian-vector products can be computed at a small multiple of gradient cost without O(d^2) Hessian storage, though CG overhead may exceed SG or limited-memory BFGS.This tradeoff is especially relevant in multinomial logistic regression and deep neural networks, where the products can be coded directly.Source: §6.1 · p. 52

6.1.1 Subsampled Hessian-Free Newton Methods

• Subsampled Hessian-free Newton methods use smaller Hessian samples than gradient samples, reducing CG costs while retaining productive curvature when the gradient sample is sufficiently large.With appropriate subsampling, maxcg × factor ≈ 1 makes per-iteration cost proportional to SG; the method is unattractive when gradients are highly noisy and samples are small.Source: §6.1.1 · pp. 53–54
• For strongly convex empirical risk with full gradients, CG directions improve steepest descent, while residual control yields linear, superlinear, or quadratic convergence; subsampled Hessians have no proven faster-than-linear rate.Despite this limitation, subsampled Hessian information often substantially reduces the iterations needed for a good approximate solution.Source: §6.1.1 · p. 54

6.1.2 Dealing with Nonconvexity

• For nonconvex problems, Hessian-free Newton methods commonly use trust regions and terminate CG on negative curvature, or use subsampled Gauss-Newton approximations that are positive semidefinite and have succeeded in deep-network training.Negative curvature occurs near deep-network minimizers, while the effectiveness of classical saddle-point avoidance remains unknown for batch and stochastic methods.Source: §6.1.2 · p. 55

6.2 Stochastic Quasi-Newton Methods

• L-BFGS uses recent displacement pairs to compute inverse-Hessian products in O(d) time without explicitly forming matrices, offering practical performance better than full-gradient iterations despite only linear convergence guarantees.BFGS uses first-order information and has local superlinear convergence, but dense updates motivate limited-memory schemes for large problems.Source: §6.2 · p. 56

6.2.1 Deterministic to Stochastic

• Stochastic quasi-Newton methods may improve SG’s sublinear-rate constant by reducing dependence on Hessian conditioning when Hk approaches the inverse Hessian at the optimum.This suggests greater robustness to ill-conditioning, although constructing approximations with the required limiting property may be impractical.Source: §6.2.1 · p. 56
• Mini-batches are essential in practice because a single-sample stochastic quasi-Newton iteration can be 20 times more expensive than SG, whereas larger batches make its additional cost marginal.The passage notes that batches of 256 are common and recommends sizes of at least roughly 20 or 50 because of matrix-vector product costs.Source: §6.2.1 · p. 57

6.2.2 Algorithms

• Online L-BFGS maintains positive definiteness, while SQN decouples step computation from quasi-Newton updates to amortize costs, replacing stored displacement pairs only every 10 or 20 iterations.Performance gains can be achieved, but the full potential of these quasi-Newton schemes is not yet known.Source: §6.2.2 · pp. 57–58

Classical Gauss-Newton

• Gauss-Newton approximates the Hessian through an affine prediction model and retains positive-curvature terms from the loss while dropping prediction-function second derivatives.This approximation is therefore positive semidefinite, though it can lose useful curvature information from parameter interactions.Source: §6.3 · pp. 59–60
• The Gauss-Newton and true Hessian matrices coincide when the least-squares loss is zero, because their difference contains factors h(xξ; wk)−yξ.Source: §6.3 · p. 60

Practical considerations

• Gauss-Newton matrices are often singular or nearly singular, so adding a positive multiple of the identity regularizes them and yields positive-definite scaling matrices.Regularized Gauss-Newton approximations can support inexact Hessian-free Newton and stochastic quasi-Newton methods for least-squares losses.Source: §6.3 · p. 60
• When predictions are multidimensional, computing Gauss-Newton matrices requires Jacobian rows not usually produced by stochastic-gradient backpropagation, increasing computational cost relative to scalar predictions.For scalar-valued predictions, the Jacobian is a single row whose elements are already intermediate stochastic-gradient computations.Source: §6.3 · p. 60

Generalized Gauss-Newton

• Generalized Gauss-Newton combines an affine prediction approximation with a second-order expansion of any convex loss, enabling curvature modeling beyond least squares.In probability estimation with logarithmic losses, the resulting matrix can avoid explicit computation of the prediction Jacobian.Source: §6.3 · pp. 60–61

Natural Gradient

• The natural gradient seeks invariance to differentiable invertible parameter transformations by moving cautiously along directions strongly affecting predictions and faster along weakly affecting directions.It formulates gradient descent in prediction-function space while computing updates in parameter space.Source: §6.4 · pp. 61, 63

Information Geometry

• The Fisher information matrix defines the local Riemannian geometry because KL divergence behaves locally as its quadratic norm, with the matrix symmetric and positive semidefinite.This geometry makes optimization paths and geodesics meaningful in prediction-function space.Source: §6.4 · pp. 61–62

Natural Gradient

• The natural-gradient update solves a locally constrained optimization problem, replacing the objective with a first-order approximation and optionally replacing its gradient with a stochastic estimate.The constraint uses the local quadratic form defined by G(w_k), producing both batch and stochastic variants.Source: §6.4 · p. 63

Practical Natural Gradient

• As the optimum is approached in density estimation, the Fisher information matrix approaches the Hessian, so natural-gradient and Newton updates perform very similarly.The matrices differ in general because their expectations use different distributions.Source: §6.4 · p. 64
• Computing the Fisher information matrix is generally challenging in large learning systems, and Monte Carlo estimation is usually prohibitive because sampling the current density estimate is costly.Convenient analytic expressions are only occasionally available.Source: §6.4 · p. 64

Diagonal scaling

• Diagonal or block-diagonal matrices reduce per-iteration overhead by scaling individual gradient components instead of applying a full scaling-and-rotation transformation.This strategy targets the added cost of general R^d × R^d scaling matrices while retaining second-order-type information.Source: §6.5 · p. 64

Computing Diagonal Curvature

• A diagonal Gauss–Newton scheme costs roughly twice a first-order SG iteration and can modestly outperform a well-tuned SG algorithm, while typically improving convergence speed by only a factor of three [12, 89, §9.1].A regularization constant handles singular or nearly singular curvature, and slowly changing curvature permits updates only once every few epochs.Source: §6.5 · p. 65

Estimating Diagonal Curvature

• Directly estimating diagonal inverse-Hessian terms can suffer correlated noise and chaotic rescaling factors, whereas curvature estimates with fixed positive bounds yield O(1/k) coordinate-wise stepsizes and perform well on unequal-variance inputs [18, 19, §3, 19, §5].The revised approach estimates diagonal Hessian ratios and replaces running averages with sums to ensure monotonically decreasing effective stepsizes.Source: §6.5 · pp. 65–66

Diagonal Rescaling without Curvature

• RMSprop rescales each stochastic-gradient component using its running second-moment estimate and is highly effective for deep neural networks, although its nonconvex behavior remains theoretically under study.Adagrad uses cumulative sums and can perform well in deep learning, but its stepsizes may decrease too aggressively early in optimization [54, 162].Source: §6.5 · pp. 66–67

Structural Methods

• Batch normalization adaptively whitens layer inputs using current mini-batch statistics, improving second-order properties and proving extremely effective despite introducing poorly controlled stochastic-gradient noise.Fresh statistics address the failure of slowly changing running estimates, but make each example’s output depend on other examples in its mini-batch.Source: §6.5 · pp. 67–68

7.1 Gradient Methods with Momentum

• Momentum combines steepest descent with a recursively maintained displacement, often improving convergence over fixed-stepsize steepest descent and supporting practical stochastic optimization.The heavy ball method is a fixed-parameter instance with superior rates for certain strictly convex quadratics, while stochastic momentum can preserve persistent descent directions but lacks broadly established guarantees.Source: §7.1 · pp. 68–69

7.2 Accelerated Gradient Methods

• Accelerated gradient reverses the computation order of descent and momentum, achieving O(1/k^2) convergence for convex smooth objectives versus O(1/k) for steepest descent.With stochastic gradients, acceleration can improve convergence constants but not the convergence-rate order.Source: §7.2 · p. 70

7.3 Coordinate Descent Methods

• Coordinate descent updates one variable at a time and can fail on general nonconvex objectives, although randomized coordinate descent converges linearly under strong convexity and coordinate-wise Lipschitz continuity.The method’s simple one-coordinate strategy can cycle, whereas under the stated assumptions a uniform random choice and stepsize 1/bL yield linear convergence.Source: §7.3 · pp. 71–72
• Coordinate descent is especially effective when updates exploit sparsity, separability, efficient component gradients, or parallelism, with per-update costs tied to the selected coordinate’s nonzeros.These structures arise in least squares, logistic regression, dictionary learning, non-negative matrix factorization, online updates, and stochastic dual coordinate ascent.Source: §7.3 · pp. 71, 73, 74

8 Methods for Regularized Models

• ℓ1 regularization induces sparse parameter vectors, supporting simpler models and feature selection, while the section treats convex nonsmooth regularizers with fixed λ.The methods are presented assuming F is continuously differentiable and full-batch gradients are available; stochastic variants are discussed after the motivating ideas.Source: §8 · pp. 74–75

8.1 First-Order Methods for Generic Convex Regularizers

• Proximal gradient methods retain the nonsmooth regularizer explicitly while applying a first-order Taylor model and scaled quadratic, achieving global linear convergence under strong convexity, Lipschitz gradients, and sufficiently small fixed stepsizes.They are practical when the proximal mapping is inexpensive, including for ℓ1-norm or separable regularizers, and stochastic gradients yield analogous stochastic-gradient behavior.Source: §8.1 · pp. 75–76

8.1.1 Iterative Soft-Thresholding Algorithm (ISTA)

• ISTA applies the proximal-gradient update to ℓ1 regularization through soft thresholding, setting sufficiently small components to zero and shrinking the remaining components toward zero.The same update can use a stochastic gradient estimate, while accelerated FISTA and adaptive stepsize techniques are noted as practical variants.Source: §8.1.1 · p. 77

8.1.2 Bound-Constrained Methods for ℓ1-norm Regularized Problems

• Bound-constrained reformulation splits w into positive and negative parts, enabling gradient projection methods whose linear convergence and sparsity depend on maintaining complementarity between each variable pair.Without complementarity, the method may fail to generate sparse solutions; exploiting the reformulation can also be more effective than applying general bound-constrained techniques.Source: §8.1.2 · pp. 77–78

8.2 Second-Order Methods

• Second-order methods build successive quadratic models while leaving the regularizer unchanged, focusing on proximal Newton and orthant-based active-set methods that promote sparsity more directly than interior-point approaches.Interior-point methods can use Hessians or quasi-Newton approximations but do not promote fast sparse-solution generation because they remain away from the feasible-region boundary.Source: §8.2 · pp. 78–79

8.2.1 Proximal Newton Methods

• Proximal Newton methods minimize quadratic-plus-regularizer models using Hessian or quasi-Newton curvature, with practical scalability relying on efficient subproblem solves, controlled inexactness, and active-variable elimination.Coordinate descent can exploit the quadratic-plus-ℓ1 structure to generate sparse iterates; an ISTA-step norm provides a continuous termination measure, and increasing solve accuracy can yield superlinear convergence.Source: §8.2.1 · pp. 79–80

8.2.2 Orthant-Based Methods

• Orthant-based methods exploit smoothness within each orthant by selecting active and free variables, minimizing a smooth quadratic model, and using a line search confined to the current orthant.The active orthant is selected using sensitivity information derived from the minimum-norm subgradient, while the search direction uses Hessian or approximate curvature.Source: §8.2.2 · pp. 80–81
• Proximal Newton and orthant-based methods form two efficient classes of second-order active-set methods for ℓ1-norm regularized problems.Proximal Newton resembles sequential quadratic programming by solving a complex subproblem that estimates the optimal active set.Source: Commentary · p. 81
• Coordinate descent makes the otherwise expensive proximal Newton piecewise-quadratic subproblem applicable to very large problems.Source: Commentary · pp. 81–82
• Orthant-based methods are useful in practice but can be heuristic because popular implementations lack convergence guarantees.Their iterations project onto a chosen orthant so the initial and final points remain in the same orthant.Source: §8.2.2 · p. 81, Commentary · p. 82
• Stochastic variants of proximal Newton and orthant-based schemes can be constructed naturally and generally inherit stochastic proximal-gradient properties when Hessian approximations have eigenvalues within a positive interval.Source: Commentary · p. 82

• Stochastic gradient (SG) methods, originating with Robbins and Monro, dominate machine learning optimization because of their favorable work-complexity guarantees and practical gains.The paper presents a concise, broadly applicable convergence and complexity theory explaining these benefits.Source: §9 · p. 82
• Parallel and distributed computing remains an underanalyzed opportunity, and SG may be poorly suited to emerging computer architectures despite its other advantages.The paper explicitly identifies this as an important limitation of its coverage.Source: §9 · p. 82
• Noise-reduction and second-order methods could surpass SG through faster convergence, improved robustness to nonlinearity and ill-conditioning, and better use of parallel and distributed architectures.The study emphasizes methods and theoretical guarantees with the greatest practical impact.Source: §9 · p. 82
• The review omits important frameworks including alternating direction method of multipliers (ADMM) and expectation-maximization (EM) variants, while covering many core optimization frameworks.Its scope prioritizes methods and theoretical guarantees most strongly affecting practical performance.Source: §9 · p. 82
• Numerical optimization is expected to continue having a profound impact on the rapidly growing field of machine learning.The paper connects this outlook to recent progress and continuing opportunities for contribution.Source: §9 · p. 82

• Smoothness-based analysis yields convergence results for both convex and nonconvex functions and accommodates unbiased or symmetrically positive-definite-scaled stochastic gradient estimators.Its main limitation is that nonsmooth models require separate treatment in §8.Source: A Convexity and Analyses of SG · pp. 82–83
• Convexity-based SG analyses begin with squared-distance recursions to the optimum and use expected stochastic subgradients belonging to the objective’s subdifferential.Convexity supplies a subgradient inequality, while strong convexity provides a stronger bound.Source: A Convexity and Analyses of SG · p. 83
• Bounding stochastic-subgradient second moments and choosing suitable stepsizes controls the distance recursion, with gradient Lipschitz continuity translating solution-distance decreases into objective decreases.These guarantees closely resemble the smoothness-based analysis.Source: A Convexity and Analyses of SG · p. 83
• Distance-to-solution analyses do not transfer easily to nonconvex settings or quasi-Newton steps because bounding the key term requires knowledge of the unknown optimum w∗.This limitation arises directly in the squared-distance recursion.Source: A Convexity and Analyses of SG · p. 83

• The proof derives inequalities under Assumption 4.1, including a bound involving ∥∇F(w)∥² and inequality (4.11).Source: B Proofs · pp. 83–84
• Expectation bounds from Assumptions 4.1 and 4.3 reduce the relevant right-hand side to terms of a convergent sum.Source: B Proofs · p. 84
• The positive convergent bound makes S+_K and S−_K bounded and convergent, so G(wK) converges and Theorem 4.9 forces its limit to zero.Source: B Proofs · p. 84