PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization Methods for Large-Scale Machine Learning

Léon Bottou, Frank E. Curtis, Jorge Nocedal

arXiv:1606.04838v3stat.MLcs.LGmath.OC

TL;DR

Large-scale machine learning challenges traditional nonlinear optimization, motivating a review of stochastic-gradient methods and their successors. The paper develops SG theory and finds stochastic optimization achieves better expected error than batch optimization in the studied work-complexity setting.

  • Problem

    Large-scale machine learning presents a setting where traditional nonlinear optimization techniques typically falter, motivating alternatives that respect the problem’s statistical nature.

  • Method

    The paper reviews optimization through machine-learning case studies, develops theory for stochastic gradient, and organizes emerging noise-reduction and second-order approaches.

  • Results

    Stochastic optimization achieves better expected error than batch optimization as a learning algorithm in the paper’s large-scale work-complexity analysis.

  • Takeaways & Limitations

    The analysis supports stochastic methods as the central optimization framework for large-scale machine learning while retaining a role for batch approaches.

  • Takeaways & Limitations

    The paper leaves the mini-batching trade-off when the minibatch size approaches the dataset size for more formal treatment.

Abstract

from arXiv · show

This paper provides a review and commentary on the past, present, and future of numerical optimization algorithms in the context of machine learning applications. Through case studies on text classification and the training of deep neural networks, we discuss how optimization problems arise in machine learning and what makes them challenging. A major theme of our study is that large-scale machine learning represents a distinctive setting in which the stochastic gradient (SG) method has traditionally played a central role while conventional gradient-based nonlinear optimization techniques typically falter. Based on this viewpoint, we present a comprehensive theory of a straightforward, yet versatile SG algorithm, discuss its practical behavior, and highlight opportunities for designing algorithms with improved performance. This leads to a discussion about the next generation of optimization methods for large-scale machine learning, including an investigation of two main streams of research on techniques that diminish noise in the stochastic directions and methods that make use of second-order derivative approximations.

1 Introduction

The paper reviews numerical optimization for machine learning, arguing that large-scale settings require methods that respect the statistical nature of the problem because traditional nonlinear optimization techniques typically falter. It examines this issue through text-classification and perceptual-task case studies and focuses on stochastic optimization methods.

  • Optimization in machine learning: Mathematical optimization computes parameters for machine-learning systems that make decisions on unseen data, using available data to optimize a given learning problem.The paper presents optimization as one of machine learning’s pillars.
  • Paper scope: The paper reviews and comments on the past, present, and future of numerical optimization algorithms for machine-learning applications.Its central theme is the distinctive nature of large-scale machine learning.
  • Large-scale optimization: Traditional nonlinear optimization techniques typically falter at large scale, making alternative approaches that respect the underlying problem’s statistical nature central to the paper.The paper contrasts this setting with small-scale learning, where traditional gradient-based methods may work with batch approaches.
  • Case studies: The case studies cover text classification and perceptual tasks such as speech or image recognition, illustrating convex and highly nonlinear, nonconvex optimization problems.Text classification commonly uses logistic regression or support vector machines, whereas perceptual tasks commonly use deep neural networks.
  • Large-scale optimization: The stochastic gradient method proposed by Robbins and Monro has been the core optimization algorithm for large-scale machine learning.The paper contrasts this with traditional gradient-based methods used for small-scale learning problems.

2 Machine Learning Case Studies

The case studies span text classification and deep neural networks, showing how high-dimensional representations, simple predictors, and large parameterized architectures support effective machine learning systems. They also motivate stochastic-gradient methods through cheap iterations, contrasting convergence behavior and highlighting mini-batch and gradient-information strategies.

  • Text classification: Text documents are represented by feature vectors x_i and binary labels y_i ∈ {−1, 1}, enabling classification through prediction functions evaluated on examples.The classifier’s performance is measured by how often its predictions match the document labels.
  • Text classification: High-dimensional sparse documents are effectively modeled with linear prediction functions h(x; w, τ) = w^T x − τ, using weights w and bias τ.The bias provides an adjustable offset for the linear discriminant.
  • Text classification: Carefully chosen prediction functions and document representations achieve good performance while avoiding training-set overfitting, and simple surrogates have succeeded beyond text classification.The passage attributes this conclusion to both theoretical arguments and experimental evidence.
  • Deep neural networks: Deep neural networks have driven major machine-learning successes in perceptual problems, including speech recognition, computer vision, and signal processing.Fully connected speech-recognition networks typically use five to seven layers and tens of millions of parameters, while CNNs have proved effective for vision and signal processing.
  • Deep neural networks: CNNs became the tool of choice for visual object recognition after the large 2012 ILSVRC performance gain and are deployed for image search and face recognition.The competition counted a classification as successful when the correct category appeared among the system’s top five outputs.
  • Optimization implications: Stochastic-gradient iterations use one randomly selected sample and are cheap, but basic SG converges sublinearly, motivating mini-batches and dynamic gradient-information methods.SG’s total work for ϵ-optimality is proportional to 1/ϵ, whereas batch gradient work is proportional to n log(1/ϵ); mini-batches reduce variance and can ease stepsize tuning.

4 Analyses of Stochastic Gradient Methods

The section develops a generalized stochastic-gradient method and establishes how descent, noise, and stepsize choices determine its convergence behavior. Results cover strongly convex and nonconvex objectives, mini-batching, and the computational advantages of stochastic updates.

  • Generalized SG method: Algorithm 4.1 requires mechanisms to generate independent random variables, compute stochastic vectors, and select positive stepsizes.These are the three computational tools assumed by the generalized SG method.
  • Descent and assumptions: Convergence follows when stochastic directions and stepsizes control the descent and second-moment terms, with variance restrictions limiting noise.Unbiased gradient estimates satisfy the sufficient-descent conditions with µG = µ = 1.
  • Strongly convex objectives: For strongly convex objectives, fixed stepsizes yield expected function values converging near the optimum rather than to the solution, while diminishing stepsizes can make expected suboptimality converge to zero.With noisy gradients, fixed stepsizes retain linear convergence only to a neighborhood; decreasing stepsizes produce sublinear convergence.
  • Mini-batching and computation: Mini-batching can match simple SG’s total computation despite different iteration costs, while offering software optimization and parallelization benefits, especially on GPUs.For batch size nmb, simple SG may require nmb times more iterations, offsetting its nmb-times-cheaper iterations.
  • Nonconvex objectives: For nonconvex objectives, fixed stepsizes make average gradient norms arbitrarily small at lower speed, whereas diminishing stepsizes drive weighted average squared gradients to zero despite noise.The fixed-stepsize result exhibits a trade-off between stepsize size and convergence speed; the diminishing-stepsize result applies even when M > 0.

5 Noise Reduction Methods · 5.1 Reducing Noise at a Geometric Rate

The section argues that stochastic-gradient noise limits fixed-stepsize convergence and motivates methods that reduce gradient or iterate errors. It then shows that geometrically decreasing stochastic-direction variance yields linear convergence and motivates dynamic sampling as an efficient realization.

  • 5 Noise Reduction Methods: Noisy gradient estimates prevent fixed-stepsize SG from converging to the solution and otherwise produce slow, sublinear convergence.
  • 5 Noise Reduction Methods: Noise-reduction methods improve gradient estimates or iterate sequences, combining practical effectiveness with attractive theoretical properties.
  • 5 Noise Reduction Methods: Dynamic sampling progressively increases mini-batch sizes, producing increasingly accurate gradient estimates during optimization.
  • 5 Noise Reduction Methods: Iterate averaging reduces noise by averaging iterates rather than gradient estimates, while using a more aggressive stepsize sequence of order O(1/√k).
  • 5 Noise Reduction Methods: The section develops dynamic sampling and gradient aggregation methods, including SVRG, SAGA, and SAG, as approaches to controlling stochastic-gradient noise.
  • 5.1 Reducing Noise at a Geometric Rate: 5.1 Reducing Noise at a Geometric Rate: SG with a fixed stepsize has a linearly vanishing expected optimality gap when stochastic-vector variance decreases geometrically.
  • 5.1 Reducing Noise at a Geometric Rate: 5.1 Reducing Noise at a Geometric Rate: The admissible fixed-stepsize range is large for typical parameter magnitudes, making the restriction practically realistic.
  • 5.1 Reducing Noise at a Geometric Rate: 5.1 Reducing Noise at a Geometric Rate: Dynamic sampling is presented as an efficient method for attaining the critical variance bound needed for geometric noise reduction.

5.2 Dynamic Sample Size Methods

Dynamic sample size methods reduce stochastic-gradient noise by increasing mini-batch sizes, yielding linear convergence for strongly convex objectives while retaining O(ϵ^-1) total gradient-evaluation complexity. Practical variants can choose sample sizes adaptively, but preset growth requires experimentation and current dynamic sampling techniques remain underdeveloped in machine learning.

  • Work complexity: O(ϵ^-1) stochastic-gradient evaluations suffice for dynamic sampling to achieve the target optimality gap, matching the complexity of diminishing-stepsize SG.The comparison concerns total evaluations of individual stochastic gradients.
  • Practical algorithms: Preset sample-size growth ties nk to optimization convergence but requires experimentation, including selecting τ > 1 and possibly delaying dynamic sampling.These heuristic adaptations may be difficult in practice because the full sample set could be used too soon or unnecessarily.
  • Practical algorithms: Adaptive sampling estimates gradient variance or related information to choose nk so descent-direction conditions hold sufficiently often.Because the relevant condition involves the true gradient, implementations use estimators such as sample variance rather than evaluating it directly.
  • Practical algorithms: Dynamic sampling is not yet widely used in machine learning, motivating methods that begin like SG and transition efficiently to reduced-variance updates.The adaptive backup can enforce at least a preset geometric growth rate when condition-based sampling grows more slowly.

5.3 Gradient Aggregation

Gradient aggregation methods reduce stochastic-gradient variance by reusing or correcting previously computed information, enabling linear convergence for finite-sum problems. Their higher storage or per-iteration costs mean they are not uniformly superior to SG, with benefits depending on accuracy and problem regime.

  • Overview: Gradient aggregation methods improve on basic SG’s sublinear convergence by achieving a linear rate for suitable finite-sum problems.This faster rate motivates reusing or revising previously computed stochastic-gradient information rather than computing increasingly larger batches.
  • SVRG: SVRG corrects a current stochastic gradient using a periodically computed full gradient, producing an unbiased, lower-variance estimator.The correction subtracts the component gradient at a reference iterate and adds the batch gradient evaluated there.
  • SVRG: SVRG achieves linear convergence for strongly convex objectives, but each outer iteration requires 2m + n component-gradient evaluations and is comparable to a full-gradient iteration.In practice, SG is more efficient during early epochs, whereas SVRG becomes beneficial near the solution when high training accuracy is required.
  • SAGA: SAGA averages stored component gradients from previous iterates to form unbiased, lower-variance directions while retaining basic SG’s per-iteration cost after initialization.For strongly convex objectives, SAGA can achieve a linear convergence rate, but it requires storing n stochastic gradient vectors, which may be prohibitive at scale.
  • Comparison with SG: Despite linear convergence, SVRG, SAGA, and SAG are not uniformly better than SG because their computing times grow with n and can approach batch-method costs.Aggregation methods may be superior when κ ≫ n, whereas SG is clearly more efficient when κ is close to 1.

5.4 Iterate Averaging Methods

Iterate averaging was introduced to reduce the noise and oscillation of stochastic-gradient iterates, but classical O(1/k) stepsizes did not reliably improve convergence. Polyak–Juditsky averaging instead combines longer steps with averaging to obtain O(1/k) mean-square convergence for averaged iterates in strongly convex problems, sometimes with an optimal asymptotic constant.

  • Motivation and limitation: Iterate averaging computes an auxiliary sequence intended to reduce the noisy oscillations of stochastic-gradient iterates around minimizers.The averaged sequence does not affect computation of the original stochastic-gradient iterates.
  • Motivation and limitation: Classical stepsizes diminishing at O(1/k) produced elusive convergence improvements for the averaged sequence.Early expectations that averaging would improve convergence over stochastic-gradient iterates were not generally realized with this stepsize rate.
  • Polyak–Juditsky averaging: For strongly convex objectives, Polyak–Juditsky averaging uses stepsizes diminishing at O(1/k^a), with a ∈ (1/2, 1), yielding E[∥w_k − w*∥2] = O(1/k^a) and E[∥˜w_k − w*∥2] = O(1/k).The faster O(1/k) rate applies to the averaged iterates, while the stochastic-gradient iterates retain the O(1/k^a) rate.
  • Polyak–Juditsky averaging: In certain cases, averaging with long steps achieves an optimal asymptotic constant for the averaged-iterate rate, and positive-definite rescaling cannot improve it.This averaging effect removes the adverse asymptotic effects of ill-conditioning.
  • Extensions: Iterate averaging has been incorporated into robust SA, mirror descent SA, and Nesterov’s primal-dual averaging, whose gradient aggregation gives the averaged sequence an O(1/k) convergence rate.The cited methods use averaging to permit longer steps while maintaining desired convergence rates.

6 Second-Order Methods

Second-order methods address the effects of nonlinearity and ill-conditioning that hinder first-order methods, improving batch convergence rates or stochastic convergence constants. The section examines Hessian-free Newton, quasi-Newton, Gauss-Newton, diagonal-rescaling, and natural-gradient approaches across stochastic and batch regimes.

  • Motivation: Second-order information mitigates high nonlinearity and ill-conditioning, improving batch convergence rates or stochastic methods’ sublinear convergence constants.This motivates moving beyond classical stochastic gradient methods.
  • Scale invariance: First-order methods are not scale invariant, so changing variables can produce different algorithmic behavior.The section illustrates this by comparing full-gradient iterations before and after a linear transformation.
  • Newton’s method: For a strongly convex quadratic, choosing B = (∇2F(w1))−1/2 and α1 = 1 yields w2 = w∗ from any initial point, corresponding to one Newton iteration.By contrast, the standard full-gradient method generally requires many iterations to approach the minimizer.
  • Taylor models: Full-gradient and Newton iterations minimize second-order Taylor models with B−2 = I and B−2 = ∇2F(wk), respectively.The full-gradient model is only first-order accurate, whereas Newton uses successive local rescalings based on an exact second-order Taylor model when the Hessian is positive definite.
  • Convergence: Newton’s method achieves a quadratic convergence rate near a strong minimizer, whereas stochastic gradient methods cannot converge faster than sublinearly regardless of B.The section therefore investigates whether second-order information can benefit stochastic optimization.
  • Methods and regimes: The section covers Hessian-free Newton, quasi-Newton, Gauss-Newton, diagonal-rescaling, and natural-gradient methods, with effectiveness varying across stochastic and batch regimes.The first three methods can use mini-batches of any size, while the last two are efficient only with moderate-to-large mini-batches.

6.1 Hessian-Free Inexact Newton Methods

Hessian-free inexact Newton methods use iterative CG solves and Hessian-vector products instead of explicit Hessians, enabling scalable second-order optimization. Subsampling the Hessian can reduce CG costs substantially, but the approach is most suitable when gradient samples are large enough to support useful curvature estimates.

  • Hessian-Free Inexact Newton Methods: Inexact Newton-CG avoids exact matrix factorization and can achieve superlinear convergence when its linear solves are sufficiently accurate.The method solves Newton systems iteratively with conjugate gradient rather than forming or factorizing the Hessian.
  • Hessian-Free Inexact Newton Methods: Hessian-free CG requires only Hessian-vector products, which can be computed without storing the O(d^2)-size Hessian.For smooth objectives, these products cost a small multiple of gradient evaluation, with additional storage for intermediate quantities.
  • Hessian Subsampling: Subsampling the Hessian reduces each CG iteration’s cost while retaining productive curvature information when the subsample is chosen appropriately.The method uses a smaller Hessian sample than gradient sample and applies backtracking line search in the stated algorithm.
  • Computational Cost: maxcg × factor ≈1 makes the stochastic subsampled method’s per-iteration cost proportional to that of SG.By contrast, deterministic inexact Newton-CG typically uses maxcg values of 5, 20, or more, making iterations many times costlier than SG.
  • Applicability and Convergence: The method is recommended only when the gradient sample S_k is large; with highly noisy small samples, Hessian subsampling may corrupt the step and be less attractive than SG.For strongly convex empirical risk with full gradients, CG improves on steepest descent, while subsampled convergence faster than linear has not been established.

6.2 Stochastic Quasi-Newton Methods

Stochastic quasi-Newton methods extend L-BFGS to machine learning by using stochastic gradients and curvature approximations, but noisy gradient differences create theoretical, computational, and stability challenges. Proposed remedies include shared-sample updates, subsampled Hessian information, and decoupling step computation from quasi-Newton updates.

  • Stochastic quasi-Newton formulation: Stochastic quasi-Newton iterations use L-BFGS curvature approximations without explicitly constructing H_k, making them suitable for large-scale problems.The method stores displacement pairs and computes matrix-vector products through the L-BFGS two-loop recursion.
  • Theoretical limitations: Their convergence rate cannot exceed sublinear, although H_k may improve the constant in that rate by addressing conditioning.The stochastic iteration shares SG’s sublinear rate limitation, while curvature information can affect the conditioning-dependent constant.
  • Additional per-iteration costs: Each stochastic quasi-Newton step adds the product H_k g(w_k, ξ_k) to SG’s gradient evaluation, creating substantial per-iteration overhead.The product requires 4md operations; with one-sample gradient cost d and memory m = 5, this overhead is significant.
  • Stochastic L-BFGS variants: Online L-BFGS reuses the same sample seed in paired gradient estimates, preserving positive-definite updates when each f_i is strongly convex.The shared seed addresses gradient-noise issues and ensures s^T v > 0 under strong convexity.
  • Conditioning and stability: Noisy consecutive gradient estimates can produce poor curvature approximations that overwrite useful information and degrade computed steps.This issue is especially important when gradient estimates have high variance or displacement pairs are based on small samples.
  • Subsampled curvature and SQN: SQN reduces update costs by fixing H_k across several iterations and computing displacement pairs less frequently, potentially using larger subsampled-Hessian batches.In the described setup, update pairs may be formed every 10 or 20 iterations, while the Hessian sample is larger than the gradient sample.

6.3 Gauss-Newton Methods

Gauss-Newton methods approximate curvature using first-order information by linearizing the prediction function, while omitting its second-derivative terms. Their practical use involves regularization for singular matrices, computational considerations tied to prediction dimensionality, and extensions to general convex losses.

  • Classical Gauss-Newton: Gauss-Newton approximates the Hessian by making an affine approximation of the prediction function inside the quadratic loss.The approximation uses the Jacobian of the prediction function with respect to the parameters.
  • Classical Gauss-Newton: The Gauss-Newton matrix retains curvature from the positive curvature of the quadratic loss while dropping terms involving second derivatives of the prediction function.It therefore replaces the subsampled Hessian with a Gauss-Newton matrix.
  • Classical Gauss-Newton: Gauss-Newton matrices are often singular or nearly singular, so practice typically adds a positive multiple of the identity matrix for regularization.Regularized Gauss-Newton approximations can also be used with inexact Hessian-free Newton and stochastic quasi-Newton methods for least-squares losses.
  • Classical Gauss-Newton: The computational cost depends on prediction dimensionality: for scalar predictions, the Jacobian is already computed during stochastic-gradient evaluation, unlike generally higher-dimensional predictions.For scalar-valued prediction functions, the Jacobian has a single row whose elements are intermediate stochastic-gradient quantities.
  • Generalized Gauss-Newton: Generalized Gauss-Newton combines an affine prediction approximation with a second-order loss expansion, and in some logarithmic-loss settings its matrix does not require explicit Jacobian computation.The strategy can preserve convexity in the loss component when network computation is assigned to that component.

6.4 Natural Gradient Method

The natural gradient method formulates optimization in prediction-function space, using the Fisher information matrix to achieve invariance under differentiable invertible parameter transformations. Its practical appeal is tempered by the difficulty of computing this matrix in large learning systems, although it approaches the Hessian near the optimum.

  • Natural Gradient: Natural gradient descent seeks invariance to all differentiable invertible transformations by optimizing in prediction-function space rather than directly in parameter coordinates.The method accounts for the anisotropic relation between parameter changes and prediction-function changes.
  • Information Geometry: The KL divergence locally defines a norm through the symmetric positive semidefinite Fisher information matrix, yielding a Riemannian geometry that can curve over larger regions.The geometry is locally Euclidean, but G(w) changes as the prediction-function space is traversed.
  • Natural Gradient: The natural gradient constrains each step by local Riemannian length, linearizes the objective, and scales the gradient using the inverse Fisher information matrix.Replacing the exact gradient with a noisy first-order approximation produces a stochastic natural gradient iteration.
  • Practical Natural Gradient: Near the optimum, the Fisher information matrix approaches the Hessian, so natural gradient and Newton’s method perform very similarly as optimality is approached.This occurs when the estimated density approaches the true distribution P.
  • Practical Natural Gradient: Computing the Fisher information matrix in large learning systems is generally very challenging, and Monte-Carlo estimation is usually prohibitive because sampling the current density estimate is costly.Some applications instead use a subset of training examples to compute an approximate quantity.

6.5 Methods that Employ Diagonal Scalings

Diagonal and block-diagonal scalings reduce the cost of incorporating second-order information by scaling individual search-direction components. The section covers direct and estimated curvature methods, gradient-based rescaling, and structural techniques such as batch normalization.

  • Methods that Employ Diagonal Scalings: Diagonal or block-diagonal matrices reduce the multiplicative cost of second-order-type scaling by avoiding general scaling-and-rotation transformations.The added cost of an iteration involving a full scaling matrix can be as little as 4md operations.
  • Computing Diagonal Curvature: Direct diagonal-curvature methods divide each stochastic-gradient coefficient by an estimated Hessian or Gauss-Newton diagonal term, with regularization for near-singular matrices.For deep networks, diagonal squared-Jacobian computation costs roughly as much as the stochastic gradient, making each iteration roughly twice as expensive.
  • Estimating Diagonal Curvature: Curvature estimates can be stabilized by estimating Hessian rather than inverse-Hessian diagonals and enforcing monotonically decreasing effective stepsizes.Keeping estimates in a fixed positive interval yields O(1/k) stepsize decay while incorporating local curvature, performing well when input coefficients have different variances.
  • Diagonal Rescaling without Curvature: RMSprop rescales stochastic-gradient components using running average magnitudes, producing near-unit expected second moments and effective performance on deep neural networks.Its theoretical explanation on nonconvex problems remains an active research topic.
  • Diagonal Rescaling without Curvature: Adagrad replaces RMSprop’s running average with a sum to create diminishing coordinate-wise stepsizes, but its stepsizes may decrease too aggressively early in deep-learning optimization.The method was initially proposed and analyzed for convex optimization with diminishing stepsizes scaling as O(1/k).
  • Structural Methods: Batch normalization improves deep-network training by changing network structure to facilitate optimization and is discussed in relation to diagonal second-order methods.The section introduces batch normalization for a fully connected layer using the layer’s input values.

7 Other Popular Methods

This section reviews momentum, accelerated-gradient, and coordinate-descent methods as distinctive optimization approaches with theoretical or practical advantages. It highlights momentum’s practical success, acceleration’s optimal deterministic rate but limited stochastic benefit, and coordinate descent’s conditional effectiveness and convergence risks.

  • Gradient methods with momentum: Momentum combines the steepest-descent direction with the most recent displacement, recursively maintaining movement along previous search directions.When β_k = 0, it reduces to steepest descent; fixed positive α and β define the heavy-ball method.
  • Gradient methods with momentum: Stochastic gradient methods with momentum tend to preserve persistent descent directions while suppressing oscillatory ones, contributing to their popularity in deep-neural-network training.The heavy-ball interpretation describes the steps as an exponentially decaying average of past gradients.
  • Accelerated gradient methods: Nesterov’s accelerated method reverses the computation order relative to momentum, evaluating the gradient after first applying the momentum-related update.For convex functions with Lipschitz continuous gradients, appropriate parameters yield O(1/k^2) convergence versus steepest descent’s O(1/k).
  • Accelerated gradient methods: In stochastic settings, acceleration can improve convergence-rate constants but cannot improve the rate itself.This limitation applies when stochastic gradients replace full gradients.
  • Coordinate descent methods: Coordinate descent is not guaranteed to converge for every continuously differentiable function, including a nonconvex example where cyclic exact minimization cycles with a nonzero gradient at limit points.The method can nevertheless be effective for partially block-separable, component-efficient, or diagonally dominant objectives, with coordinate updates costing O(nnz(x_i)).

8 Methods for Regularized Models

This section extends optimization for regularized machine-learning models from smooth regularizers to convex, nonsmooth ones, especially the ℓ1 norm. It develops proximal-gradient methods, their convergence and sparsity properties, and related first- and second-order approaches.

  • Problem setting: The section studies objectives combining a differentiable loss with a convex, nonsmooth regularizer, with methods designed for a fixed regularization parameter λ.The framework includes ℓ1-regularized problems and can represent LASSO as a special case.
  • Alternative regularizers: The ℓ1 framework also illustrates how methods can be adapted to other sparsity-inducing regularizers, including group-sparsity regularizers and the nuclear norm.The section does not discuss these alternatives in detail but presents ℓ1 methods as a model for designing and analyzing them.
  • Proximal gradient: Proximal gradient extends gradient descent by minimizing a regularized local model that encourages each new iterate to remain close to the current one.It reduces to the ordinary gradient update when the regularization term is absent and can also be given a stochastic-gradient variant.
  • Proximal gradient: Under strong convexity, Lipschitz-continuous gradients, and sufficiently small constant stepsizes α ∈ (0, 1/L], proximal gradient converges globally at a linear rate.The stepsize is critical: guarantees require it to be sufficiently small, while an excessively small value can slow optimization.
  • ℓ1-regularized methods: For ℓ1 regularization, ISTA induces sparsity by setting sufficiently small components to zero and shrinking the magnitudes of other components.A component is zeroed when the steepest-descent result has absolute value less than αkλ; stochastic gradient estimates can replace full gradients.
  • Related methods: Proximal-gradient ideas encompass projection methods for bound constraints, while interior-point and proximal-Newton approaches provide second-order alternatives with tradeoffs in sparsity, scalability, and guarantees.Interior-point methods may not rapidly generate sparse solutions, and some orthant-based implementations lack convergence guarantees; stochastic variants require positive-bounded Hessian eigenvalues.

9 Summary and Perspectives

The paper highlights numerical optimization’s integral role in machine learning and the dominant role of stochastic gradient methods. It points toward noise-reduction, second-order, and parallel or distributed approaches as opportunities for future optimization methods.

  • Numerical optimization algorithms have played an integral role in machine learning’s transformational progress over the past two decades.
  • The stochastic gradient method has had a dominant role in the paper’s account of optimization for machine learning.
  • Parallel and distributed computing represent important opportunities that could alter perspectives on optimization methods in the years ahead.The paper notes that these opportunities were not discussed or analyzed at length.
  • Noise-reduction and second-order methods could improve convergence rates, mitigate high nonlinearity and ill-conditioning, and exploit parallel and distributed architectures.
  • Numerical optimization is expected to continue having a profound impact on the rapidly growing field of machine learning.

A Convexity and Analyses of SG

The paper’s SG analyses primarily rely on smoothness, enabling convergence results for both convex and nonconvex minimization and for unbiased or symmetrically positive-definite-scaled stochastic gradients. Convexity-based analyses extend guarantees to smooth and nonsmooth settings but depend on distance-to-solution arguments that do not transfer easily to nonconvex or quasi-Newton settings.

  • Smoothness-based analysis: Smoothness-based SG analyses apply to both convex and nonconvex minimization.They also cover stochastic vectors that are unbiased gradient estimators or are scaled by a symmetric positive definite matrix.
  • Smoothness-based analysis: A drawback of smoothness-based analysis is that nonsmooth models require separate treatment.The paper addresses nonsmooth models separately in §8.
  • Convexity-based analysis: Convexity-based analyses begin with squared-distance identities to the optimum and use subgradient expectations in ∂F(w_k).The framework assumes Eξ_k[g(w_k, ξ_k)] = ĝ(w_k) ∈ ∂F(w_k).
  • Convexity-based analysis: Convexity bounds the first distance-identity term, while strong convexity provides a stronger condition; second-moment bounds and stepsize choices control the remaining terms.With Lipschitz-continuous gradients, these results resemble the smoothness-based analysis in §4.
  • Limitations: Distance-to-solution analyses do not transfer easily to nonconvex problems or quasi-Newton steps because w* may be unknown.Without explicit knowledge of w*, appropriately bounding the first term is difficult.

B Proofs

The proofs derive the stated inequalities under the paper’s assumptions, then use expectations and convergent-sum arguments to establish convergence of the relevant sequences. In particular, G(w_K) converges, and Theorem 4.9 implies that its limit is zero.

  • B Proofs: Under Assumption 4.1, Inequality (4.3) is obtained, and the desired result follows.The proof also invokes Inequality (4.11) with w = w* and arbitrary w ∈ R^d.
  • B Proofs: Taking expectations using Assumptions 4.1 and 4.3 and Inequality (4.9) yields the required bound.The proof proceeds from conditional expectation to total expectation.
  • B Proofs: The bound (B.1) is a term of a convergent sum, so the nondecreasing sequence S_K^+ is upper bounded and converges.The proof applies Theorem 4.10 to both components of the bound, using P∞_k ≤ α_k for sufficiently large k.
  • B Proofs: The sequence S_K^- also converges; consequently, G(w_K) converges, and Theorem 4.9 implies that its limit is zero.The argument uses G(w_K) = G(w_0) + S_K^+ − S_K^- and S_K^- ≥ 0.
Loading 1606.04838v3…