Optimization for Machine Learning:
Beyond Stochastic Gradient Descent
Elad Hazan
References and more info:
http://www.cs.princeton.edu/~ehazan/tutorial/MLSStutorial.htm
Based on:[Agarwal, Bullins, Hazan ICML ’16]
[Agarwal, Allen-Zhu, Bullins, Hazan, Ma STOC ’17]
[Hazan, Singh, Zhang ICML ‘17], [Agarwal, Hazan COLT ‘17]
[Agarwal, Bullins, Chen, Hazan, Singh, Zhang, Zhang ’18]

Princeton-Google Brain teamNaman Agarwal, Brian Bullins, Xinyi Chen,
Karan Singh, Cyril Zhang, Yi Zhang

Deep net, SVM,
boosted decision
stump,…

Chair/car

Function of vectors&'()*+,- (/)

Distribution overvectors{a} ∈ $%Modelparameters250200150
100500−50323120

10−1

Minimize incorrect chair/car
predictions on training setUC Berkeley)−1−2−3−2−3This talk: faster optimization
1. second order methods
2. adaptive regularization

Convex Optimization for Machine Learning

Fall 2009

(Non-Convex) Optimization in ML
Model

Distribution over{"} ∈ ℝ&Label

8minimize. / ,,∈ℝ

1. / = 4 ℓ5 /, "5 , :53567

Training set size (m) & dimension of data (d) are very large, days/weeks to train

Gradient Descent
Given first-order oracle: !" # ,!" #≤&Iteratively: #'() ← #' − ,!" #'Theorem: for smooth bounded functions, step size , ∼ . 1 (depends onsmoothness),

1
1 !" #'
0'2 ∼10

Stochastic Gradient Descent [Robbins & Monro ‘51]
" %Given stochastic first-order oracle: ! #$= #$ % ,!

" %#$(≤ *(" %+Iteratively: %+,- ← %+ − 0#$
Theorem [GL’15]: for smooth bounded functions, step size 0 =16 #$ %+5+( ∼*(512 3,SGD! "# $−!
"←'"!")+*⋅

SGD++
Variance Reduction[Le Roux, Schmidt, Bach ‘12]…

Momentum[Nesterov ‘83],…

!

"#$ ←!

" −'" ⋅*)+!

"

Adaptive Regularization[Duchi, Hazan, Singer ‘10],…

Are we at the limit ?

Woodworth,Srebro ‘16: yes!
(gradient methods)

Rosenbrock function

Higher Order Optimization• Gradient Descent – Direction of Steepest Descent• Second Order Methods – Use Local CurvatureNewton’s method (+ Trust region)!"!%&" = !% − ) [+ # ,(!)]0" +,(!)!#For non-convex function: can move to ∞Solution: solve a quadratic approximation in a
local area (trust region)!$Newton’s method (+ Trust region)!"!%&" = !% − ) [+ # ,(!)]0" +,(!)
1. d3 time per iteration, Infeasible for ML!!
2. Stochastic difference of gradients ≠ hessian!#!$Till recently J

Speed up the Newton direction computation??
• Spielman-Teng ‘04: diagonally dominant systems of equations inlinear time!
• 2015 Godel prize• Used by Daitch-Speilman for faster flow algorithms• Faster/simpler by Srivasatva, Koutis, Miller, Peng, others…

• Erdogu-Montanari ‘15: low rank approximation & inversion bySherman-Morisson• Allow stochastic information• Still prohibitive: rank * d2

Our results – Part 1 of talk
• Natural Stochastic Newton Method• Every iteration in O(d) time. Linear in Input Sparsity• Couple with Matrix Sampling/ Sketching techniques - Best known running
time for ! ≫ # for both convex and non-convex opt., provably faster thanfirst order methods

QP

Stochastic Newton?
(convex case for illustration).JK4 = .J − M [8 5 G(.)]H4 8G(.)

4• ERM, rank-1 loss: arg min ( )∼ + [ℓ . / 0) , 2) + |.|5 ]'5• unbiased estimator of the Hessian:
75 = a: a; ⋅ ℓ′ . / 0) , b: + ?
8:

H4
5
5
5
77
• clearly ( 8 = 8 G , but ( 8≠ 8 5 G H4

@ ~ B[1, … , E]

Circumvent Hessian creation and inversion!
• 3 steps:

For any distribution on
naturals i ∼ #• (1) represent Hessian inverse as infinite series$ %& =/ − $& )()*+ ,- .

• (2) sample from the infinite series (Hessian-gradient product) , ONCE
$ & 1 %2 $1 = ( / − $ & 1 ) $f = 4)∼5 / − $ & 1 ) $f ⋅)1Pr[;]• (3) estimate Hessian-power by sampling i.i.d. data examples= E)∼5,?∼[)]@?*2 ,- )/ − $ & 1? $f ⋅1Pr[;]

Single example
Vector-vector
products only

Improved Estimator• Previously, Estimate a single term in one estimate• Recursive Reformulation of the series"# ( %% +>!3"# = % + (% − !)(%++ %%)(−!
!
…
…
!)(%!
−!
. .. )))))**3"# ) + …
-.
/
CDE. 3=<FG5>
AB 3456789:;5 59-:<=-5 ?
@AB• Truncate after 0 steps. Typically 0 ~ 2 (condition # of f)
"#"#>
• H !
→!
as 0 → ∞3• Repeat and average to reduce the varianceLiSSA

Linear-time Second-order Stochastic Algorithm
arg min*'∈)+ ,∼ . [ℓ 1 2 3, , 5,1 :+ |1| ]
2
V is a bound on the variance• Compute a full (large batch) gradient ;f=• Use the estimator ; >:?;? defined previously & move thereof the estimator• In Practice - a small
constant (e.g. 1)• In Theory - N ≤ M :Theorem 1: For large t, LiSSA returns a point in the parameter space @A s.t.
? @A ≤ ? @ ∗ + D
In total time log

GH

I (K + L M N )Gà (w. more tricks) LP log :I K + MI , fastest known! (& provably faster 1st order WS ’16)
H

Hessian Vector Products for Neural Networks
in time ! " ($%&'()**%& +&,-.)

2 8 0 9: 20 = E1∼=,?∼[1]

BF − 2 8 0? 2f ⋅?C: DE 1

1Pr[,]• 01 - computed via a differentiable circuit of size !(")• 201 - computed via a differentiable circuit of size O(d)(Backpropagation)• Define 31 ℎ = 201 ℎ 6 7
2 3 ℎ = 2 8 01 ℎ 7• There exists a !(") circuit computing 2 8 01 ℎ 7

LiSSA for non-convex (FastCubic)
MethodGradient Descent(Folklore)
Stochastic Gradient
Descent (Folklore)

Time to| "#(%)| ≤ ((Oracle)*+) ,)*0+1,2Time to| "#(%)| ≤ ((Actual)

Second Order?

Assumption./) ,N/A

Smoothness/,2N/ASmoothness)

Noisy SGD (Ge et al)

/34)
,2

Cubic Regularization(Nesterov & Polyak)> /?@: + /?
)=, :.C./) :.EC,

Fast Cubic*+*D) :.C + :.EC,,

5-6 ℎ:≽ −, 3; <Smoothness-5 6 ℎ:≽ −, - <Smooth and Second
Order Lipschitz

5-6 ℎ:≽ −, - <Smooth and Second
Order Lipschitz

2nd order information: new phenomena?
• ”Computational lens for deep nets”:
experiment with 2nd order information…
• Trust region• Cubic regularization, eigenvalue methods….
• Multiple hurdles:• Global optimization is NP-hard, even deciding whether
But generally
speaking...
you areat a local minimum is NP-hardWe’re• screwed.
Goal: local minimum | "# ℎ | ≤ &! Local (non global) minima of f0
and" '#(evenℎ restricting≽ − to& continuous*! All kindsof constraintsfunctions):
What is Optimization

h(x) = sin(2πx) = 0

250
200
150

Bengio-group experiment100
500−5032312010−1−1−2−3Duchi (UC Berkeley)−2−3Convex Optimization for Machine Learning

Fall 20097 / 53

Experimental Results
Convex: clear
improvements

Neural networks: doesn’t
improve upon SGD

What goes wrong?

Adaptive Regularization Strikes BackT )-1/(GG

2Princeton Google Brain team: Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan,
Karan Singh, Cyril Zhang, Yi Zhang

Adaptive Preconditioning●Newton’s method special case of preconditioning: make loss surface
more isotropic"! " ↦ ! $"!

Modern ML is SGD++
Variance Reduction[Le Roux, Schmidt, Bach ‘12]…

Momentum[Nesterov ‘83],…

!

"#$ ←!

" −'" ⋅*)+!

"

Adaptive Regularization[Duchi, Hazan, Singer ‘10],…

Adaptive Optimizers-

Each coordinate ! " gets a learning rate #$ "' !*:$ ["] - ,*:$ ["]#$ ["] chosen “adaptively” using ()-AdaGrad: -$ " ≔-RMSprop: -$ " ≔-Adam: -$ " ≔*∑3012 40 5 6*∑3012 7 380 40 5 6
*

*97 3

∑3012 7 380 40 5 6

What about the other AdaGrad?

diagonal preconditioning" # time per iteration&%&'( ← %& − #34. + ., .,/,-(full-matrix preconditioning> " # $ time per iteration0(/$&⋅ .&%&'( ← %& − + ., .,/,-(0(/$⋅ .&What does adaptive regularization even do?!
● Convex, full-matrix case: [Duchi-Hazan-Singer ‘10]: “best regularization in hindsight”! #" $" − $ ∗ = ("● Diagonal version: up to20min,- . /0

! #" 1.
"

improvement upon SGD (in optimization AND generalization)● No analysis for non-convex optimization, till recently (still no speedup vs. SGD)○

Convergence: [Li, Orabona ‘18], [Ward, Wu, Bottou ‘18]

The Case for Full-Matrix Adaptive Regularization● GGT, a new adaptive optimizer● Efficient full-matrix (low-rank) AdaGrad● Theory: “Adaptive” convergence rate on convex & non-convex !
Up to "●●●●#$faster than SGD!

Experiments: viable in the deep learning era
GPU-friendly; not much slower than SGD on deep models
Accelerates training in deep learning benchmarks
Empirical insights on anisotropic loss surfaces, real and synthetic

The GGT Algorithm●●●●

SGD: !"#$ ← !" − '" ⋅ )"AdaGrad: !"#$ ← !" − diag ∑"/0$ )/1 2$/1 ⋅ )"Full-Matrix AdaGrad: !"#$ ← !" − ∑"/0$ )/ )/4 2$/1 ⋅ )"GGT: !"#$ ← !" − 5" 5"4 2$/1 ⋅ )": ≈ 200> ≈ 10@5"=)" 7)"2$ 71)"21 ⋯ 792$)"29#$Why a low-rank preconditioner?
● Answer 1: want to forget stale gradients (like Adam)● Synthetic experiments: logistic regression, polytope analytic center

The GGT speedup!×!

#$% =!×!×!

#'%×!

The GGT speedup

Matrix ops: ! "# $Huge SVD: ! # %Matrix ops: ! " $ #Tiny SVD: ! " %Large-Scale Experiments (CIFAR-10, PTB)

Visualizing Gradient Spectra
eigs %&' %&@ ) = 150

26-layer ResNet
CIFAR-10

3-layer LSTM
Penn Treebank(char-level)

Theory: faster convergence vs. non-convex SGD/0-Convex: ! "# ≤ argmin+ ! " + - in .

-Non-convex: ∃3: 5! "6-Reduction via modified descent lemma:≤ - within .

Minimize 1/- < times:! "6 + 5! " , " − "6+ ; " − "6 <"610
710

steps
convex epochs

Minimize 1/- < times:! " + 2; " − "6 < ≥ ! "≥! ""6"687"687

The Ratio of Adaptivity● Define the adaptivity ratio !:!" ≔● [DHS10]: ! ≤',>∑(%&' )%*+"∑(%&' )%,+-"

AdaGrad regret
worst−case OGD regret=@ for diag-AdaGrad, sometimes smaller for full AdaGrad
D DC E● Strongly convex losses: GGT* converges in BA● Non-convex reduction: GGT* converges in BA

FCDED
FGstepssteps● First step towards analyzing adaptive methods in non-convex optimization

A note on the important parameters● A lot of work on improving dependence on !

● Recent state-of-the-art in SGD++:"#"$ → &.(#● In practice: ) ∼ 0.1, improvement amounts to factor 10 ∼ 3.1● Our improvement".$→/0.$: can be as large as 1

(3 ∼ 104 for language models!)● Huge untapped potential: characterize the ratio of adaptivity!

Summary
1. Special characteristics of stochastic optimization in ML
2. Second order methods in linear time
• LiSSA : fastest running time for convex ML• Non-convex – different solution concept
FastCubic: faster than gradient descent!
3. Adaptive regularization strikes again:• full-matrix AR in linear time
• Dimension-scale improvements possible, visible in experiments

4. Opportunity to improve factors of dimension rather thanapproximation