PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Optimization Methods from a Machine Learning Perspective

Shiliang Sun, Zehui Cao, Han Zhu, Jing Zhao

arXiv:1906.06821v2cs.LGmath.OCstat.ML

TL;DR

The paper addresses optimization challenges arising from large-scale data, complex models, and non-convex objectives in machine learning. It surveys classical and modern optimization methods, their applications and developments, and open problems, concluding that higher-order methods for stochastic variational inference remain an interesting challenge.

  • Problem

    Optimization in machine learning must handle large-scale data, complex models, and challenges such as insufficient data and non-convex objectives.

  • Method

    The paper summarizes first-order, high-order, and derivative-free optimization methods, their theoretical bases, applications across machine learning scenarios, and performance-improvement approaches.

  • Results

    The survey synthesizes optimization methods and their applications across machine learning fields while identifying challenges and open problems.

  • Takeaways & Limitations

    Second-order or higher-order optimization for stochastic variational inference is identified as an interesting and challenging direction for handling large-scale data.

Abstract

from arXiv · show

Machine learning develops rapidly, which has made many theoretical breakthroughs and is widely applied in various fields. Optimization, as an important part of machine learning, has attracted much attention of researchers. With the exponential growth of data amount and the increase of model complexity, optimization methods in machine learning face more and more challenges. A lot of work on solving optimization problems or improving optimization methods in machine learning has been proposed successively. The systematic retrospect and summary of the optimization methods from the perspective of machine learning are of great significance, which can offer guidance for both developments of optimization and machine learning research. In this paper, we first describe the optimization problems in machine learning. Then, we introduce the principles and progresses of commonly used optimization methods. Next, we summarize the applications and developments of optimization methods in some popular machine learning fields. Finally, we explore and give some challenges and open problems for the optimization in machine learning.

I. INTRODUCTION

The paper surveys optimization in machine learning, covering foundational methods, applications across major learning fields, and unresolved challenges driven by data scale and model complexity.

  • Optimization in Machine Learning: Most machine learning algorithms formulate model learning as an optimization problem over parameters in an objective function.The paper frames optimization as a core component of machine learning and describes model construction, objective definition, and parameter solving as central steps.
  • Optimization Methods: The survey organizes fundamental methods into first-order, high-order, and derivative-free optimization categories.Stochastic gradient methods represent first-order approaches, Newton’s method represents high-order approaches, and coordinate descent represents derivative-free methods.
  • Optimization Methods: First-order methods are widely used, while high-order methods can converge faster but face the computational and storage difficulty of handling Hessian inverses.Many high-order variants therefore approximate the Hessian matrix.
  • Applications: Optimization methods support deep neural networks, reinforcement learning, meta learning, variational inference, and Markov chain Monte Carlo.The paper discusses stochastic optimization in reinforcement learning and large-scale stochastic variational inference using natural gradients.
  • Challenges and Open Problems: The paper identifies insufficient data, non-convexity, sequence truncation bias, higher-order stochastic variational inference, and stochastic conjugate-gradient methods as open problems.Insufficient samples can produce high variance and overfitting, while non-convex objectives may lead optimization toward local rather than global optima.

C. Optimization Problems in Unsupervised Learning

This section describes optimization formulations in unsupervised and related machine learning problems, then explains gradient-based methods and their trade-offs for solving them.

  • Clustering: K-means minimizes within-cluster variation so samples in the same cluster are similar and samples in different clusters are distinct.Its objective minimizes the sum of variances across all clusters.
  • Dimensionality Reduction: PCA minimizes reconstruction error while projecting samples from the original feature space into lower-dimensional coordinates.The passage describes dimensionality reduction as retaining as much original information as possible after projection.
  • Probabilistic Models: Probabilistic models can optimize parameters by maximizing the training samples’ logarithmic likelihood, while Bayesian priors can alleviate overfitting.The paper presents maximum likelihood estimation and prior distributions as optimization-related components of probabilistic modeling.
  • Gradient-Based Optimization: Gradient descent iteratively updates variables opposite the objective gradient, with learning rate η determining the step size and affecting convergence iterations.The method repeats gradient derivation and parameter updates until convergence.
  • Stochastic Gradient Descent: SGD uses one randomly selected sample per iteration, giving O(D) iteration complexity and reducing computation for large datasets.Its stochastic gradient is an unbiased estimate of the full gradient, and it can achieve optimal convergence speed for strongly convex problems.
  • Stochastic Gradient Descent: SGD’s stochastic fluctuations can help escape local minima in complex problems, but they can also slow convergence and make learning-rate selection difficult.Learning rates that are too small slow convergence, while rates that are too large can hinder convergence and cause loss fluctuation.
  • Stochastic Gradient Descent: Escaping saddle points remains a challenge for SGD because gradients can be zero in every direction despite opposing slopes along different directions.The paper identifies saddle points, rather than only local minimum values, as an important source of optimization difficulty.

3) Nesterov Accelerated Gradient Descent:

The section surveys momentum, Nesterov, adaptive-learning-rate, and variance-reduction approaches for improving stochastic gradient optimization. These methods address oscillation, learning-rate selection, diminishing rates, and gradient variance, but their benefits depend on parameter settings and problem structure.

  • Momentum Method: Momentum preserves part of the previous update direction, accelerating convergence for high curvature, small consistent gradients, or noisy gradients.Its speed variable uses an exponentially decaying average of the negative gradient and a momentum factor.
  • Momentum Method: A momentum factor that is too small weakens convergence improvement, whereas a factor that is too large can push the iterate beyond the optimum.Experiments empirically identify 0.9 as an appropriate setting in many cases.
  • Nesterov Accelerated Gradient Descent: Nesterov momentum evaluates the gradient at a future position rather than the current position, incorporating more gradient information than traditional momentum.The future position is formed by adding the momentum term to the parameters before computing the gradient.
  • Adaptive Learning Rate Method: Adaptive methods adjust learning rates automatically because manually selecting the SGD learning rate strongly affects optimization performance.They are described as requiring less parameter adjustment, converging quickly, and being widely used for deep neural networks.
  • Adaptive Learning Rate Method: AdaDelta and RMSProp use a moving window and exponential moving average rather than all historical gradients to address AdaGrad’s eventual collapse of the learning rate.AdaGrad’s principal benefit is eliminating manual learning-rate tuning, but its learning rate can eventually approach zero.
  • Variance Reduction Methods: Stochastic gradient methods have sublinear convergence and often high gradient variance, motivating variance-reduction methods and efforts toward linear convergence.SVRG reduces its variance bound over time through a specialized update term, thereby achieving linear convergence.

5) Variance Reduction Methods:

Variance-reduction methods improve stochastic optimization by controlling gradient noise, while related constrained methods decompose large convex problems into smaller subproblems. Their applicability and resource requirements remain problem-dependent.

  • SAG: SAG reduces variance by storing recent per-sample gradients and updating parameters with their aggregate, requiring only one sample gradient computation per iteration.This trades substantially higher memory overhead for computational overhead comparable to SGD.
  • SAG: SAG has linear convergence and can be faster than SGD, but applies only when the loss is smooth and the objective is convex.The paper gives convex linear prediction as an example and notes that SAG can sometimes outperform batch gradient descent.
  • SVRG: SVRG periodically computes an average gradient over all samples, then uses it with randomly selected samples during the intervening iterations.The interval average is refreshed every w iterations, and each update calculates the gradient up to two times.
  • SVRG: SVRG avoids storing every gradient, saving memory relative to SAG, and experiments report remarkable performance on a non-convex neural network.Both methods are presented as variance-reduction strategies, with SVRG designed for complex models where SAG is inconvenient.
  • ADMM: ADMM separates operators in convex optimization problems so large problems can be divided into multiple smaller problems solvable in a distributed manner.Its practical convergence behavior depends on the penalty parameter β, whose adjustment can be automated in some convex problems.

7) Frank-Wolfe Method:

The Frank-Wolfe method solves constrained convex optimization by linearizing the objective, finding a feasible descent direction, and performing a one-dimensional search within the feasible domain. The section also situates conjugate gradient as a memory-efficient alternative for certain large-scale systems and optimization problems.

  • Frank-Wolfe Method: Frank-Wolfe linearizes the objective, solves a linear program for a feasible descending direction, and searches along that direction within the feasible domain.The method is also called approximate linearization.
  • Frank-Wolfe Method: The Frank-Wolfe update chooses a step size between 0 and 1 along the direction from the current point to the linearized subproblem solution.The resulting point remains in a feasible direction, and the iteration continues until convergence.
  • Frank-Wolfe Method: Frank-Wolfe is a first-order method for constrained convex problems, with fast convergence early and slower convergence near the optimum.Near the optimum, its search and gradient directions tend to become orthogonal.
  • Conjugate Gradient Method: Conjugate gradient uses first-order information for some problems while providing convergence speed comparable to high-order methods, without storing or computing an inverse Hessian.It is effective for large-scale linear systems and can also solve nonlinear optimization problems.
  • Conjugate Gradient Method: For a symmetric positive-definite linear system, minimizing a quadratic positive-definite function and solving the system have the same unique solution.The gradient of the quadratic equals the system residual, connecting conjugate-gradient optimization to linear-system solving.

2) Quasi-Newton Methods:

Quasi-Newton methods approximate Hessian information to retain curvature-aware search while reducing Newton’s storage and computation costs. They use secant-based updates, approximate inverse Hessians, and line searches satisfying Wolfe conditions.

  • Newton’s Method: Newton’s method fits the local objective surface with a quadratic, whereas gradient descent fits it with a plane.The comparison explains why Newton-type methods incorporate curvature information.
  • Quasi-Newton Method: Quasi-Newton methods replace Newton’s expensive inverse-Hessian computation with a positive-definite approximation, sometimes making them more efficient.Different variants approximate the Hessian or its inverse using different update schemes.
  • Quasi-Newton Condition: The quasi-Newton condition, or secant equation, constrains the updated Hessian approximation using the parameter and gradient differences between successive iterates.The paper defines s_t = θ_t+1 − θ_t and u_t = ∇f(θ_t+1) − ∇f(θ_t).
  • Quasi-Newton Method: Quasi-Newton search directions use the gradient together with an approximate inverse Hessian, and their step sizes are selected to satisfy Wolfe conditions.The inverse approximation is denoted H_t = B_t^-1.
  • DFP: DFP is an early quasi-Newton method whose correction formula updates the inverse-Hessian approximation H_t+1.It was proposed by Davidon and later explained and improved by Fletcher and Powell.

HDF P

L-BFGS adapts quasi-Newton optimization for high-dimensional problems by retaining vector pairs rather than full Hessian approximations, with limited-memory and stochastic extensions.

  • Quasi-Newton methods: Quasi-Newton methods converge faster than first-order methods because curvature information makes their search directions more effective.Their main computational difficulty is operating on and storing inverse-Hessian information.
  • L-BFGS: L-BFGS stores a few n-dimensional vectors instead of fully dense n × n Hessian approximations, making it feasible for high-dimensional problems.It represents the inverse-Hessian approximation through stored vector sequences and recent displacement pairs.
  • L-BFGS: The L-BFGS update direction is computed through a two-loop recursion using the retained displacement pairs and the current gradient.The recursion avoids explicitly storing or computing the complete inverse-Hessian approximation.
  • Stochastic extensions: Stochastic quasi-Newton methods combine stochastic updates with quasi-Newton curvature approximation to address large-scale learning problems.This combination is motivated by the need for small-subset updates and the resource demands of matrix-based quasi-Newton methods.

3) Stochastic Quasi-Newton Method:

Stochastic quasi-Newton methods combine stochastic sampling with curvature approximation, while Hessian-free methods use sampled Hessian-vector products and conjugate gradients to reduce large-scale costs.

  • Stochastic quasi-Newton: Stochastic quasi-Newton methods replace deterministic gradients with stochastic gradients throughout BFGS-style iterations, as in online-BFGS and online-LBFGS.The displacement and gradient-difference quantities are modified using sampled objectives.
  • Stochastic quasi-Newton: SQN updates L-BFGS curvature estimates with sub-sampled Hessian-vector products and decouples gradient and curvature calculations for stability.Its framework maintains a limited collection of displacement pairs and computes matrix-vector products with two-loop recursion.
  • Stochastic quasi-Newton: A direct stochastic quasi-Newton adaptation can require two gradient estimates per iteration, while updating inverse-Hessian approximations at every step may be unreasonable.These drawbacks motivate SQN’s subsampled curvature updates and separation of stochastic gradient and curvature calculations.
  • Hessian-free optimization: Hessian-free optimization estimates Hv without directly calculating the Hessian matrix and uses conjugate gradients to obtain an approximate search direction.A damping term may be added to the Hessian approximation, and a line search determines the step size.
  • Hessian-free optimization: Sub-sampled Hessian-free optimization reduces each iteration’s cost by using a small sample set to calculate Hessian-vector products.The sample must be large enough to provide useful curvature information but small enough to keep conjugate-gradient costs manageable.

5) Natural Gradient:

Natural gradient methods adapt optimization to non-Euclidean parameter spaces using Fisher-information geometry, while trust-region methods control updates through local quadratic models and adaptive radii.

  • Natural gradient: When the parameter space has a Riemannian metric rather than Euclidean geometry, the steepest direction is given by the natural gradient.Natural gradient methods are especially suited to objectives based on KL divergence or related probabilistic surrogates.
  • Natural gradient: The natural gradient transforms the ordinary gradient using the Fisher information matrix.The Fisher matrix supplies the geometric structure used in the natural-gradient update.
  • Natural gradient: Natural-gradient application is limited by the cost of estimating and inverting the Fisher information matrix.Truncated Newton, factorized natural gradient, and K-FAC are described as approaches for avoiding or approximating this computation.
  • Trust-region methods: Trust-region methods approximate the objective with a second-order Taylor model and constrain each displacement by a trust-region radius.The model uses an approximate gradient and Hessian matrix, with the L2-constrained case yielding the Levenberg-Marquardt algorithm.
  • Trust-region methods: Trust-region radii are updated by comparing actual and predicted objective decreases through a ratio measuring model accuracy.Ratios near 1 support expanding the radius, whereas ratios near 0 support reducing it.

C. Derivative-Free Optimization

Derivative-free optimization addresses objectives whose derivatives are unavailable or difficult to compute, while preconditioning improves iterative optimization through better spectral properties.

  • Derivative-free optimization: Derivative-free optimization finds solutions without gradient information when objective derivatives do not exist or are difficult to calculate.It is therefore applicable to nondifferentiable or otherwise derivative-inaccessible objectives.
  • Derivative-free optimization: Heuristic derivative-free methods search according to empirical rules, including simulated annealing, genetic algorithms, ant colony algorithms, and particle swarm optimization.These methods generally produce approximate global solutions.
  • Derivative-free optimization: Coordinate descent performs sequential one-dimensional searches along coordinate axes and is suitable for some nondifferentiable loss functions.Its update directions remain fixed, and each iteration changes one axis direction without calculating gradients.
  • Derivative-free optimization: L(Θt+1) ≤L(Θt) ≤... ≤L(Θ0) is guaranteed for coordinate descent, with convergence similar to gradient descent.The coordinate order may be arbitrary, and coordinate directions can be generalized to coordinate blocks.
  • Preconditioning: Preconditioning transforms a difficult linear system into an equivalent one with the same solution but more favorable spectral characteristics.A structured or sparse preconditioned matrix can benefit computation, and preconditioned conjugate gradient accelerates convergence.
  • Applications and resources: The paper summarizes high-order optimization methods and available optimization toolkits in Tables II and III.The selected machine-learning applications include deep neural networks, reinforcement learning, variational inference, and Markov chain Monte Carlo.

A. Optimization in Deep Neural Networks

Optimization in deep neural networks spans first-order adaptive methods and modified high-order methods, addressing convergence, non-convexity, and computational challenges in DNN training.

  • First-order methods: RMSProp, Adam, AdaDelta, and Nadam can fail to converge under fixed-size windows of past gradients.A simple convex optimization example demonstrates this non-convergence problem.
  • First-order methods: Adaptive methods such as Adam use exponential moving averages, while AmsGrad replaces short-term memory with a monotonic second-moment estimate.AmsGrad is described as preserving Adam’s computational advantages while guaranteeing convergence in the later stage.
  • First-order methods: SWATS first trains with Adam for rapid progress and then switches to SGD for more precise optimization.The switching criterion lacks rigorous mathematical proof but performs well across varied applications.
  • RNN optimization: First-order methods can train RNNs effectively but still converge slowly in deep RNNs, motivating curvature-based optimization.High-order methods can accelerate convergence near the optimum, although their curvature computations are challenging.
  • High-order methods: Hessian-free optimization requires modifications for non-convex DNN objectives because the exact Hessian may not be positive definite.The generalized Gauss-Newton matrix provides a positive-semidefinite Hessian approximation, while structural damping improves robustness for RNNs.

B. Optimization in Reinforcement Learning

Reinforcement-learning optimization covers value-based, policy-based, and actor-critic approaches, with deep RL applying neural networks to challenging control problems.

  • RL foundations: Reinforcement learning models interactions through states, actions, transition probabilities, rewards, and discounting within a Markov decision process.Model-based methods know the transition and reward functions, whereas model-free methods require systematic exploration.
  • RL methods: Actor-critic optimization estimates policy and value-function parameters simultaneously to combine policy-gradient and temporal-difference learning.The actor seeks high return, while the critic evaluates the current policy.
  • RL methods: Value-based methods learn value functions, policy-based methods optimize policies directly, and actor-critic methods learn both policy and state value.Actor-critic methods separate prediction by the critic from control by the actor.
  • Deep RL optimization: Deep reinforcement learning often takes several days to train because first-order algorithms explore the neural-network weight space inefficiently.ACKTR addresses this challenge with a scalable, sample-efficient natural policy gradient using Kronecker-factored approximations.

C. Optimization in Meta Learning

Meta learning treats learning itself as an optimization problem, seeking rapid adaptation to new tasks with few samples; variational inference similarly converts posterior approximation into optimization.

  • Meta-learning motivation: Meta learning aims to train models that adapt to new tasks using few samples without overfitting.Its supervised-learning applications include few-shot learning.
  • Optimization-based meta learning: Optimization-based meta learning repeatedly samples tasks, updates task parameters with training data, and updates meta-parameters with test data.The trained optimizer is then used to learn a new task during meta-testing.
  • Learned optimizers: Learned neural optimizers predict gradients from original gradients and can outperform advanced adaptive stochastic-gradient methods in experiments.LSTM architectures are often used as meta-optimizers because their cell-state updates resemble backpropagation updates.
  • MAML: MAML learns an initialization that supports rapid adaptation across tasks without requiring additional meta-learning parameters or a specific learner architecture.It applies to classification, regression, and reinforcement learning.
  • Variational inference: Variational inference approximates Bayesian posteriors by optimizing a constrained distribution, commonly minimizing KL divergence or maximizing the ELBO.CAVI optimizes each mean-field factor while holding the others fixed, whereas stochastic optimization improves scalability to large datasets.

E. Optimization in Markov Chain Monte Carlo

Optimization in MCMC focuses on making posterior sampling feasible for large datasets, especially when full-data gradients and correction steps are expensive.

  • Scaling challenges: Traditional MCMC methods are computationally costly and difficult to extend to large-scale data because gradient calculations may require the entire dataset.This full-data gradient computation is identified as HMC’s bottleneck.
  • HMC: HMC simulates Hamiltonian dynamics with an auxiliary momentum variable and numerically approximates the dynamics using leapfrog integration.The Hamiltonian combines potential energy from the target distribution with kinetic energy from momentum.
  • Stochastic-gradient HMC: Mini-batch stochastic gradients reduce HMC’s large-dataset computation cost but introduce gradient noise into the dynamics.The noise can be approximated as normally distributed with covariance V(θ).
  • Stochastic-gradient HMC: SGHMC adds friction to momentum dynamics to reduce noisy-gradient effects and avoid the Metropolis-Hastings correction step.The method is designed for sampling problems involving large datasets.
  • HMC limitations: HMC efficiency is highly sensitive to path length L and step size ε, whose poor settings can sharply reduce sampling efficiency.Too-small path lengths produce nearby samples, while too-large path lengths can cause trajectories to loop back.

1) Path Length L:

The passages cover adaptive sampling, optimization challenges in deep and sequential models, stochastic variational inference, and the survey’s broader synthesis of machine-learning optimization methods.

  • HMC sampling: NUTS automatically selects the HMC trajectory length, avoiding manual setting of the iteration-step parameter L.Its recursive procedure stops simulation by detecting backtracking.
  • HMC sampling: HMC performance depends sensitively on step size ǫ: overly small values slow updates, while overly large values increase rejection.Dual averaging adapts ǫ toward a fixed average acceptance probability.
  • HMC sampling: Adaptive tuning can optimize HMC hyper-parameters including step size, iteration length L, and mass M, and can extend to other MCMC algorithms.The stated goal is improved sampling performance with less cumbersome manual adjustment.
  • Deep neural networks: Deep neural-network optimization is challenged by insufficient training data, which can produce high variance and overfitting, and by non-convex objectives.Improper learning rates or iteration counts can also prevent convergence and cause large accuracy fluctuations.
  • Deep neural networks: Transfer learning and meta learning address insufficient data by reusing related models or learning suitable parameter initialization, but require related tasks or data sources and may add complexity.The survey concludes that insufficient-data training of DNNs remains a challenge.
  • Sequential models: Large-scale sequential models commonly use stochastic optimization, mini-batches, or distributed computing, but sequence segmentation can introduce incorrect dependencies and approximation errors.The passages identify analysis of the difference between approximate and exact solutions as an open direction.
  • Stochastic variational inference: Stochastic variational inference enables variational inference to handle large-scale data, while incorporating second- or higher-order optimization remains an open challenge.The survey also describes stochastic conjugate-gradient variants using fast Hessian-gradient products, with numerical evidence of validity.
  • Survey scope: The paper surveys first-order, high-order, and derivative-free optimization methods, their machine-learning applications, performance improvements, and open problems.It aims to connect optimization-method development with challenges arising in different machine-learning fields.
Loading 1906.06821v2…