Optimization

Rowel Atienza

rowel@eee.upd.edu.ph

University of the Philippines

​

Optimization

Finding the parameters, 𝞱, of a neural network that significantly reduce the loss function L(𝞱)

Measured in terms of a performance measure, P, on the entire training set and some regularization terms

P is the one that makes Optimization in Machine Learning different from just pure optimization as the end goal itself.

Optimization

Loss function from an empirical distribution p’_data (over the training set)

L(𝜽) = E_{(x,y)~p’data}L(f(x;𝜽),y)

f(x;𝜽) per sample prediction

y is the label

Usually, we want to minimize L* over the true data generating distribution p_data

L*(𝜽) = E_(x,y)~pdataL(f(x;𝜽),y)

Empirical Risk Minimization

Empirical Risk Minimization:

L(𝜽) = E_{(x,y)~p’data}L(f(x;𝜽),y) = 1/m∑_i=1^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾)

m is the number of sample

in some cases, prone to overfitting as training goes indefinitely

use validation set to detect start of overfitting

Minibatch Stochastic

Using entire training set, known as deterministic, is expensive and has no linear return; good estimate of gradient but low linear return; Note that gradient itself is a random variable

Use of minibatch stochastic (small subset of entire training set) offers many advantages:

Suitable for parallelization; GPU memory limits batch size

GPUs perform better on power of 2 sizes, 32 to 256

Small batches offer regularizing effects; improves generalization error

Small batch size increases gradient variance; learning rate must be reduced

Shuffle minibatch, make minibatches independent improves training

Challenges

Ill conditioning of Hessian Matrix, H: Issue for both convex and non-convex

Gradient step, -𝜖g, using second order Taylor expansion of Loss will add , ½𝜖²g^THg - 𝜖g^Tg, to the cost:

f(x₀ - eg) = f(x₀) + ½𝜖²g^THg - 𝜖g^Tg

If ½𝜖²g^THg > 𝜖g^Tg, then we must choose small 𝜖 to ensure stable training. Else the loss increases instead of decreasing.

This results to slow learning process

​

Challenges

Convex loss function: any local minimum is a global minimum

Non-convex: any local minimum is not necessarily a global minimum. We settle for a local minimum that satisfies our performance metrics.

​

Challenges

Saddle points: found in high-dimensional models

Hessian matrix both have positive and negative eigenvalues

Saddle pts common in high dim space; Local min in low dim space

Can be easily overcome by SGD; SGD are designed to move downhill and not necessarily seek critical points unlike Newton method

Newton method encounters difficulty dealing with saddle and global maxima

Saddle-free Newton method can overcome saddle points - research in progress

​

​

​

Saddle pt

Challenges

Cliff

Gradient descent proposes a large change

thus missing the minimum - Exploding Gradient

Solution is to use gradient clipping - capping the gradient

Common problem is Recurrent Neural Networks

Challenges

Long Term Dependencies (eg RNN, LSTM)

Performing the same computation many times

Applying the same W t-times

W^t = (Vdiag(𝝺)V^-1)^t = Vdiag(𝝺)^tV^-1

if |𝝺|<1, the term vanishes as t increases

if |𝝺|>1, the term explodes as t increases

Gradients are influenced by diag(𝝺)

Collectively known as the vanishing or exploding gradients problem

Challenges

Inexact gradients due to noisy or biased estimates

Deep learning uses sampling-based estimates

Local and Global Structure

Optimization does not necessarily lead to a critical pt (global, local or saddle).

Most of the time, only near zero gradient points with resulting acceptable performance

​

Challenges

Wrong side of the mountain: gradient descent will not find the minimum

Solution: algorithm for choosing the initial points (initial parameters)

Bad initial points send the objective function to the wrong side of the mountain

Parameter Initialization

Initial weights determine if the objective function will converge or not

Also affects network generalization and optimization

Modern initialization strategies are simple and heuristics

Optimization for neural network is not well understood yet

Initialize weights and biases with different random values (symmetry breaking effect) - no 2 units connected to same input have the same initial weights

Initialize weights with high-entropy distribution like Gaussian and Uniform PD

​

Parameter Initialization

Large weights are good for optimization and breaks symmetry

But… can saturate activation functions, can cause gradient explosion esp in RNN

Small weights are good for regularization

Optimal weights are good for optimization

Big enough weights for gradients to propagate

​

Parameter Initialization - Weights

Easiest and Default

Random values with std = 0.01

Difficult to converge on deep models

​

Parameter Initialization - Weights

Glorot Initialization

Assume a network layer with m inputs, n outputs

W_i,j ~ U(-sqrt(6/(m+n)), +sqrt(6/(m+n))) - Glorot uniform

W_i,j ~ N(w; 0, sqrt(2/(m+n))) - Glorot normal

Balance of activation and gradient variance

Assumes linear activation; Shallow models

[Glorot & Bengio, AISTATS 2010 - http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf

​

Parameter Initialization - Weights

He Initialization

Assume a network layer with m inputs

W_i,j ~ U(-6/sqrt(m), +6/sqrt(m)) - He uniform

W_i,j ~ N(w; 0,sqrt(2/m)) - He normal

Applicable to non-linear activations (ReLU, PReLU); Deep models

[He et al., http://arxiv.org/abs/1502.01852]

​

Parameter Initialization - Biases

Set biases to zero (only for linear activation)

Use small values (eg 0.1) for ReLU activation

1 for LSTM forget state

For output layer with highly skewed output c_i in categorical distribution, we solve softmax(b) = c

Where c is the vector representing one-hot training labels for some marginal distribution c_i ; under small weights, bias alone determines the right output label

Optimization Algorithms

Stochastic Gradient Descent

with Momentum

Adaptive Gradient (AdaGrad)

RMSProp

with Momentum

Adaptive Moment (Adam)

Stochastic Gradient Descent

Instead of using the whole training set, we use a minibatch of m iid samples

Learning Rate:

Gradually decrease learning rate during training since after some time, the gradient due to noise is more significant

Apply learning rate decay until t=𝝉 when it set to constant 𝝐_𝝉

𝝐_k = (1-k/𝝉)𝝐_o + (k/𝝉)𝝐_𝝉

𝝐 is usually chosen by trial and error while observing all errors

typical values [0.01 to 0.001]

​

Stochastic Gradient Descent Algorithm

Require: Learning Rate Scheduler: 𝝐₁, 𝝐₂, … 𝝐_k

Require: Initial Parameter 𝛉

k ← 1

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾)

Apply update: 𝜽 = 𝜽 - 𝜖_kg

k = k + 1

end while

Stochastic Gradient Descent

Guarantee of convergence of SGD

∑^∞_k=1𝝐_k = ∞

∑^∞_k=1𝝐_k² < ∞

Stochastic Gradient Descent - Convergence Rate

Theoretically, the excess error = L(𝞱) - L_min(𝞱), has lower bound of O(1/k) for convex functions. Anything faster than O(1/k) will not improve the generalization error. Thus resulting to overfitting.

Generally, batch gradient is better than SGD in convergence. A technique that can be used is to increase the batch size gradually.

Momentum on SGD for Speed Improvement

v ← 𝛼v - 𝝐g

𝞱 ← 𝞱 + v

where v is the accumulator of gradient g; v includes influence of past gradients, g

𝛼 is momentum [0,1); typical 0.5, 0.9 and 0.99; 𝛼 is larger compared to 𝝐, the bigger is the influence of past g’s; similar to snowballing effect

If the momentum always agree, then the terminal velocity is 𝝐||g||/(1-𝛼)

𝛼=0.9, multiplies g by 10 (momentum effect)

​

SGD Algorithm with Momentum

Require: Learning Rate Scheduler: 𝝐₁, 𝝐₂, … 𝝐_k

Require: Initial Parameter 𝛉

k ← 1

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾)

Compute velocity: v ← 𝛼v - 𝝐g

Apply update: 𝞱 ← 𝞱 + v

k = k + 1

end while

Momentum on SGD for Speed Improvement

Nesterov Momentum: Loss is evaluated after the momentum is applied

𝞱 → (𝞱 + 𝛼v)

​

SGD Algorithm with Nesterov Momentum

Require: Learning Rate Scheduler: 𝝐₁, 𝝐₂, … 𝝐_k

Require: Initial Parameter 𝛉

k ← 1

while stopping criterion is not met

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽+𝛼v),y⁽ⁱ⁾)

Compute velocity: v ← 𝛼v - 𝝐g

Apply update: 𝞱 ← 𝞱 + v

k = k + 1

end while

Adaptive Learning Rates

AdaGrad (Adaptive Gradient) [Duchi et al 2011]: learning rate decrease is inversely proportional to the square root of the sum of all the historical squared values of the gradient

r ← r + g⌾g

𝝙𝞱 ← -g⌾𝝐/(ẟ+√r)

𝞱 ← 𝞱 + 𝝙𝞱

where ẟ = small constant (eg 10^-7)

Effective for some deep learning but not all; Accumulation of early learning rate can cause excessive decrease in learning rate

​

​

AdaGrad Algorithm

Require: Learning Rate: 𝝐, Initial Parameter 𝛉, Small constant ẟ=10^-7 for numerical stability

r ← 0

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾)

Accumulate squared gradient: r ← r + g⌾g

Compute update: 𝝙𝞱 ← -g⌾𝝐/(ẟ+√r) (Division and sqrt applied element-wise)

Apply update: 𝞱 ← 𝞱 + 𝝙𝞱

end while

Adaptive Learning Rates

RMSProp [Hinton 2012] is like AdaGrad but replaces gradient accumulation with exponentially weighted moving average; Suitable for nonconvex optimization

r ← 𝜌r + (1-𝜌)g⌾g

𝝙𝞱 ← -g⌾𝝐/√(ẟ+r)

𝞱 ← 𝞱 + 𝝙𝞱

where ẟ = small constant (eg 10^-6); 𝜌 is the decay rate (e.g. 0.9)

Discard history from extreme past. Effective and practical for deep neural nets

On nonconvex, AdaGrad might fail to converge to local convex bowl. RMSprop is like AdaGrad but converges rapidly after finding the local convex bowl.

​

​

RMSProp Algorithm

Require: Learning Rate: 𝝐, Initial Parameter 𝛉, Small constant ẟ=10^-6 for numerical stability, Decay rate ⍴ (eg 0.9)

r ← 0

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾)

Accumulate squared gradient: r ← 𝜌r + (1-𝜌)g⌾g

Compute param update: 𝝙𝞱 ← -g⌾𝝐/√(ẟ+r) (𝝐/√(ẟ+r) applied element-wise)

Apply update: 𝞱 ← 𝞱 + 𝝙𝞱

end while

Adaptive Learning Rates

RMSProp with Nesterov Momentum

r ← 𝜌r + (1-𝜌)g⌾g

v ← 𝛼v - g⌾𝝐/√r

𝞱 ← 𝞱 + v

where ẟ = small constant (eg 10^-6)

𝜌 is the decay rate

𝛼 is momentum coefficient

​

​

RMSProp Algorithm with Nesterov Momentum

Require: Learning Rate: 𝝐, Initial Parameter 𝛉, Small constant ẟ=10^-6 for numerical stability, Decay rate ⍴

r ← 0

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽+𝛼v),y⁽ⁱ⁾)

Accumulate gradient: r ← 𝜌r + (1-𝜌)g⌾g

Compute velocity update: v ← 𝛼v - g⌾𝝐/√r (𝝐/√r applied element-wise)

Apply update: 𝞱 ← 𝞱 + v

end while

Adaptive Learning Rates

Adam (Adaptive Moments) [Kingma and Ba 2014]

first moment: s ← 𝜌₁s + (1-𝜌₁)g, s’ ← s/(1-𝜌₁^t)

Built-in 1st-order momentum & correction

second moment: r ← 𝜌₂r + (1-𝜌₂)g⌾g, r’ ← r/(1-𝜌₂^t)

Built-in 2nd-order momentum & correction

𝝙𝞱 ← -𝝐s’/(ẟ+√r’), 𝞱 ← 𝞱 + 𝝙𝞱

where ẟ = small constant for numerical stabilization (eg 10^-8), 𝜌₁ and 𝜌₂ ∈ [0, 1) (suggest: 𝜌₁ = 0.9, 𝜌₂ = 0.999), t is time step, 𝝐 is suggested to be 0.001

​

​

Adam Algorithm

Require: Learning Rate: 𝝐 (eg 0.001), Initial Parameter 𝛉, ẟ = small constant for numerical stabilization (eg 10^-8), 𝜌₁ and 𝜌₂ ∈ [0, 1) (suggest: 𝜌₁ = 0.9, 𝜌₂ = 0.999), t is time step, 𝝐 is suggested to be 0.001

r ← 0, s ← 0, t ← 0

while stopping criterion is not met do

Sample a minibatch { x⁽¹⁾, ..., x^(m) } with corresponding targets { y⁽¹⁾, ..., y^(m) }

Compute gradient estimate ∇_𝜽L(𝜽) = g = 1/m∇_𝜽∑_i^mL(f(x⁽ⁱ⁾;𝜽),y⁽ⁱ⁾), t = t + 1

Compute 1st-moment and correction: s ← 𝜌₁s + (1-𝜌₁)g, s’ ← s/(1-𝜌₁^t)

Compute 2nd-moment and correction: r ← 𝜌₂r + (1-𝜌₂)g⌾g, r’ ← r/(1-𝜌₂^t)

Compute and apply update: 𝝙𝞱 ← -𝝐s’/(ẟ+√r’), 𝞱 ← 𝞱 + 𝝙𝞱

end while

Batch Normalization

Applied layer-wise

To maintain zero mean and variance of 1 for activation outputs

Batch normalization reduces the amount by what the hidden unit values shift around (covariance shift).

Allows use of larger learning rate in deep models w/o causing instability

Applied to any input or hidden layer

H’ = (H - μ)/σ (row-wise operation, one sample is one row)

where H matrix is a minibatch of activations of the layer to normalize

μ vector of mean of each unit, σ vector of std of each unit (broadcast op)

Batch Normalization

At training time,

μ = 1/m∑_iH_i,: (1)

σ = sqrt(ẟ + 1/m∑_i(H-μ)_i²) (2)

ẟ = 10^-8 for numerical stability

In retrospect, this operations discourages μ and σ from attempting to propose large changes

In practice, μ and σ are stored as running averages so we do not have to compute (1) and (2) all the time.

Reference

Deep Learning, Ian Goodfellow and Yoshua Bengio and Aaron Courville, MIT Press, 2016, http://www.deeplearningbook.org

​

End