The main objective of this paper is to provide a state-of-the-art survey of advanced optimization methods used in machine learning. It starts with a short introduction to machine learning followed by the formulation of optimization problems in three main approaches to machine learning. Then optimization is presented along with a review of the most recent state-of-the-art methods and algorithms that are being extensively used in machine learning in general and deep neural networks in particular. The paper concludes with some general recommendations for future work in the area.
In recent years, machine learning has made
significant progress and received enormous
attention in the research community and
industry. Machine learning is applied
successfully to a wide range of problems
ranging from image recognition, speech
recognition, text classification, online
advertising, web search, recommendation
systems, etc. However, there also exist many
challenging problems in machine learning
including minimization of loss (error) function,
hyperparameters tuning, feature selection,
dimensionality reduction, finding the optimum
combination from a pool of base classifiers, etc.
Optimization is an efficient and robust tool to
tackle some of these challenges, and since its
beginning has played a vital role in statistical
and machine learning. In today’s data-intensive
technology era, machine learning models in
general, and deep neural networks in particular,
rely more and more on optimization methods
[
The relationship between optimization methods and machine learning is one of the most relevant topics in modern computational science.
More recently a lot of work has been done
by both the optimization and machine learning
community by achieving state-of-the-art results
on this matter. Generally, it is considered a
relationship of great intimacy, optimization has
proved to be a core tool in machine learning and
at the same time, machine learning can be
considered as an important source of inspiration
for new optimization ideas [
From point of view of gradient information
in optimization, popular optimization can be
grouped into three major classes: the first-order
optimization methods, which are mainly based
on stochastic gradient methods, the second
class comprises of high-order optimization
methods, here Newton’s method represents a
typical example of this class and the third class
comprises of heuristic derivative-free
optimization methods, in which the coordinate
descent method is a representative [
The interplay of optimization and machine learning has also attracted the attention of various researchers and practitioners.
This paper serves as a complementary one to those previously published, at the same time provides a state-of-the-art review on advanced learning. First, it gives a short introduction to machine learning followed by the formulation of optimization problems in three main types of
The following is given a short introduction to machine learning models, followed past experience”. These authors and others in their work treat learning problem as an optimization one.
As described in [
∑ =1 ( , ( , )) (1)
Support Vector Machine - here loss function
is
a
typical
form
of
structured
risk
minimization. In this case, usually, the
regularization
items
are
added
into the
objective function to alleviate overfitting [
∑ =1 ( , ( , )) + | ∥ 2 2 (2) here
is a fixed parameter that usually is determined through cross-validation.
The main task here is to find a function that best minimizes the loss function on training, when only input is given without output (target), for a set of defined parameters.
For the k-means clustering algorithm, the
optimization problem can be formulated as
minimizing the following loss function [
being the number of clusters, feature vector of samples, represents the center of cluster , and that represents the sample set of cluster . The main goal of the objective function considers minimizing the variance through all clusters.
In the case of principal component analysis (PCA) the goal of the objective function is to
minimize the reconstruction errors and has the form as given below: ℎ Here
min ∑ =1 ∥ − ∥2
2 = ∑ ′ =1
(4) >> ′, (4.1) denotes the number of samples, denotes the -dimensional vector, denotes under ′. the reconstruction of . In the second part of the equation above, = 1, . . . , ′ denotes the projection of in ′-dimensional coordinates, and denotes the standard orthogonal basis
In probabilistic models, the optimization
goal is to find an optimal probability density
function
of ( ),
which
maximizes
the
logarithmic likelihood function (MLE) [
max ∑ =1 ln ( , )
Here the main task is to maximize the
expected reward after executing a series of
actions which are defined by a policy mapping
function [
max ( ) ( ) = [∑∞=0
+ | = ] 2.2.
(5)
(6)
(6.1)
Optimization is a mathematical discipline that
is used to solve any problem involving decision
making, whether in engineering or economics.
The basic idea used in optimization is choosing
the best solution among
various available
alternatives, in the sense of the given objective
function
[
According
to
[
subj. to 0( ) ( ) ≤ = 1, … , , where vector = ( 1, . . . , ) represents the optimization variable of the problem and is the objective function, 0: → : → , = 1, . . . , (inequality) constraint functions and with 1, . . . , are denoted limits for the constraints.
Depending on the particular forms of the
objective and constraint functions there is a
taxonomy of optimization problems including
linear, quadratic, semi-definite, semi-infinite,
integer, nonlinear, goal, geometric, fractional,
etc. [
In this paper, we have tried to reflect mainly on the advanced optimization methods that are used in machine learning in general and deep neural networks in particular. are denoted the
The following is given an overview of the state-of-the-art optimization methods applied in machine learning models.
3.1.
First-order optimization methods are also known as gradient-based optimization and as the name implies, these methods are mainly based on first-order derivatives or gradient descent. This section dealt with state-of-the-art first-order optimization methods in machine learning that are currently in use apart.
a. Gradient Descent - is one of the oldest and most popular algorithms used to perform optimization. Because of its relevant role in solving optimization problems in learning and deep learning, it is part of every deep
The main drawback of batch gradient descent is the run-time, it can be very slow because the entire dataset used to perform just one update, at the same time, is inconvenient for datasets that are too large to fit in memory. Stochastic gradient descent - in contrast to batch gradient descent, it does not use the entire dataset but rather performs parameter update only for one training example at a time. = − ⋅ ∇ ( ; ( ); ( )) (8) Because the stochastic gradient descent uses only one training example before updating the gradients, especially in the case of a large training set, it can be much faster compared to batch gradient descent. Due to being much faster, it can also be used to learn online. However, there is a drawback in the context of the parameters, they will “oscillate” toward the minimum rather than converge smoothly. Further details on the stochastic gradient descent can be found in the following section. Mini-batch gradient descent - this approach benefits from combining the best of both worlds and performs an update for every mini-batch of n training examples:
= − ⋅ ∇ ( ; ( : + ); ( : + )) (9)
There are two main advantages to this: first,
it further reduces the variance of the parameter
updates, which can lead to more stable
convergence. Second, it can make use of highly
optimized matrix optimizations typical to
stateof-the-art deep learning libraries. In general,
mini-batch has sizes ranging from 50 up to 256
but this can be larger depending on the
applications. Because of its advantages,
minibatch gradient descent is a method of choice for
training a neural network and the term SGD
usually is employed also when mini-batches are
used [
b. Stochastic Gradient Descent (SGD) [
c. Momentum [
= −1 − ∇ ( ) (10) = − with is denoted momentum term, −1 is update vector in the previous step, ∇ ( ) is update vector in the current step and with = − is denoted update of the parameter.
In other words, the idea of using momentum
is similar to the ball effect down a hill. It starts
with an initial momentum value and
accumulates momentum as it goes down a hill,
it speeds up on the way (until finally terminal
velocity is reached, i.e. < 1). In the same
way, the momentum term increases when
moving in the direction of the gradient and
decreases updates for dimensions whose
gradient is in different directions. As a result,
the convergence speeds up and oscillation has
been reduced [
d. Nesterov Accelerated Gradient (NAG)
[
e. AdaGrad [
words, adopting smaller learning rates for features occurring often, and higher learning rate for features not occurring often. By doing this, it is well-suited for dealing with sparse data.
Here are the updating
formulae as presented by [
, = ∇ ( , ) Then, the SGD update performed for every parameter at each step takes the form: +1, = , − ⋅ , As given in the equation above, Adagrad adopts the general learning rate dynamically for every parameter at each step based on the previous gradients computed for .
+1, = , −
√ , +
⋅ ,
here is a diagonal matrix
where ∈ ℝ
step [
Adagrad is
characterized by the ability to adapt the learning
rate dynamically
based
on historical data,
which makes it convenient to handle sparse data
[
f. AdaDelta [
The running average [ 2
] at time then
depends only on the previous average and the
current gradient [
] is the running average at time step that depends only on the previous average and the current gradient. The parameter is updated as: Δ = − ⋅ , +1 = − Δ (14)
In Adadelta there is no need to set the
learning rate because it is defined by default and
has been eliminated from the update rule [
g. RMSProp [
Here and are denoted the estimates of the first and the second moment of the gradients respectively. (15) (16) the same time as AdaDelta. Both RMSProp and AdaDelta aimed to tackle the radically diminishing learning rates issue of AdaGrad.
h. Adaptive moment estimation (Adam) [
√ , + ⋅ , and 10−8 for .
As proposed by authors in [
benefits of both Adam and NAG. Adam is characterized by two main components - a momentum
and an adaptive learning rate.
Although, regular momentum can be shown conceptually and empirically to be inferior to
(j)
Other recent adaptive optimizers
several new variants of adaptive optimizers
have been proposed
more recently. These
include AdamW [
k. Variance Reduction Methods - over the
years several variance reduction techniques
have been proposed. Some of the most
wellknown including stochastic average gradient
(SAG) [
SAG - is a variance reduction method that has been proposed with the aim to improve the convergence speed. SAG iterations have a linear convergence rate that makes them faster than
SGD, and has favorable advantages
compared
to
other
stochastic
algorithms, especially when the loss function is
smooth and convex [
SVRG - SGD is characterized by slow
convergence due to the inherent variance. The
SVRG method was proposed with the idea to
overcome this drawback. It has the same fast
convergence rate with SAG and SDCA for
smooth and strongly convex functions, but
unlike SAG and SDCA it does not require the
storage of gradients. As result, SVRG has very
good performance and easily applicable to
complex models such as non-convex neural
networks [
l. Alternating Direction Method of
Multipliers (ADMM) [
As presented by authors in [
Many different variants of ADMM have
been proposed including stochastic alternating
direction method of multipliers (S-ADMM)
algorithm [
m. Frank-Wolfe Method - also known as
conditional gradient algorithm for smooth
optimization, was originally proposed by Wolfe
in 1956. It is one of the simplest and earliest
known iterative algorithms used for solving
quadratic programming problems with linear
constraints [
The use of curvature information in addition
to the gradient offers a convenient approach
where an objective function exhibits a highly
nonlinear and is ill-conditioned. For example,
second-order optimization methods have been
proposed with this aim in mind. When these
methods are used in the context of machine
learning, they work effectively by providing
faster convergence rates, stability to parameter
tuning, and robustness to problem conditioning.
However, the benefits derived from the use of
curvature information in the form of a dense
Hessian matrix come at the cost of increased
per-iteration complexity [
In the last decades, with the continuous
improvement of high-order optimization
methods, there has been increased interest in the
exploration of large-scale data by using
stochastic techniques [
a. Conjugate gradient (CG) - can be seen as
being between the method of steepest descent
and Newton’s method. It is one of the most
effective iterative methods used for solving
sparse systems of linear equations [
b. Quasi-Newton Methods - methods of
Newton or quasi-Newton’s type are typically
well-known to be the most convenient choice
for solving nonlinear minimization problems
when the objective function is twice
continuously differentiable [
During the last decades, several methods
based on Newton’s has been developed and
some of the most well-known include BFGS
[
c. Stochastic Quasi-Newton Method - both
stochastic Newton (SN) and stochastic
quasiNewton (SQN) methods have been proposed as
a solution to overcome some issues present in
first-order optimization methods. The central
idea of these methods is to combine the speed
of Newton’s method and the scalability of
firstorder methods by integrating curvature
information. The resulting class of these
combined methods is enjoying increasing
popularity as a robust method for several
largescale machine learning tasks [
d. Hessian-Free Method - the working
principle of the Hessian-free (HF) method is
quite similar to Newton’s method, which
incorporates second-order gradient
information. In contrast to Newton’s method
discussed above, for HF method as the name
implies does not make any approximation to the
Hessian H, but rather the product Hd is
accurately computed using the finite
differences method [
Sub-sampled Hessian-Free Method - HF
optimization is also known as
truncatedNewton, is a popular method, and has also been
subject to a number of studies in the
optimization research community for decades,
but never seriously applied in machine learning
because of its limitations. In order to overpass
these limitations, a sub-sampled technique has
been introduced in HF, resulting in an improved
HF method [
e. Natural Gradient - the natural gradient
descent approach [
In some applications, a smaller number of
iteration is required in the natural gradient
compared to gradient descent, which makes it
an attractive alternative method. However,
computing the natural gradient has been shown
to be impractical for models with very many
parameters such as large neural networks, due
to the extreme size of the Fisher matrix [
For some optimization problems arising
from practical applications, the derivative of
objective and constraint functions may not exist
or is difficult to calculate. This is where the use
of derivative-free, or zeroth-order, optimization
comes into play. Derivative-free optimization
(DFO) is a discipline in mathematical
optimization that aimed to find the optimal
solution without requiring the availability of
derivatives [
In general, there are two major types of ideas with regard to derivative-free optimization. To the first type belong heuristic algorithms and the second type is made up of the coordinate descent method.
a. Heuristic algorithms - heuristic and
metaheuristic techniques have been
successfully used to solve several optimization
problems in the different research areas of
science and engineering. Some of the most
well-known examples of these techniques
include optimization methods include genetic
algorithms, simulated annealing, differential
evolution, harmony search, ant colony
algorithms, and particle swarm optimization.
Although, the implementation strategy of
heuristic or metaheuristic algorithm in
largescale machine learning problems is still rarely
investigated [
b. Coordinate descent method (CD) - is a
well-known typical derivative-free [
Over the last decades, there has been a huge interest in optimization across multiple fields in science and engineering including machine learning. However, there also exist many challenging problems in machine learning because of the increasing scale and complexity of machine learning and computational platforms.
Optimization is an efficient and robust tool to tackle some of these challenges, and since its beginning has played a vital role in statistical and machine learning. In today’s data-intensive technology era, machine learning models in general, and deep neural networks in particular rely more and more on optimization methods.
More recently a lot of work has been done by both the optimization and machine learning community by achieving state-of-the-art results on this matter. Generally, optimization has proved to be a core tool in machine learning and at the same time, machine learning can be considered as an important source of inspiration for new optimization ideas.
We hope that the issues discussed in this paper will push forward the discussion in the area of optimization and machine learning, on the same time it may serve as complementary material for other researchers interested in both these topics.