INF 8245 E -

Fall 2021

Machine
Learning
-

Sarath Chandar

[Link]
 [Link] n

Gradient descent variants : -

-
-

:{
"
(n'
")J
'
Dataset , y
, , ,

1. Bath descent
-
gradient :

computes the
gradient of the cost fn

training
the entire
art .
the parameters or for

dataset .

tf Tfo ; )
( Iit ) (Iit )
0=0 -
rn n y
,

→ We need to calculate the

gradient for the whole

dataset to perform just one update .

Can be slow
→
very .

to the model
→ Doesn't allow us
update on1
→ Guaranteed to
converge to the
global minimum
for
convex error surfaces and to a
local minimum

for non -
convex surfaces >

-
 Stochastic descent :
2.
-
gradient
SGD performs parameter updates for each

example n' " and label

training
"
y .

o -
o -

n -4510; n' ii. y " )

descent performs redundant
→ Bath
gradient computations
it
for large datasets , as
recomputes gradients
for similar examples before each parameter update
.

→ SGD does
away
with this
redundancy by
update time
performing
one at a
.

Faster , can be used to learn online

→ .

→ Performs frequent updates with a

high variance

that cause the objective fn .

to
heavily
fluctuate .

SGD fluctuation .
 to skip local However
→ these fluctuations help minima .

to the exact minimum

it complicates convergence ,

as sad will keep overshooting .

→ If we
slowly decrease the
learning rate
,
SGD

shows the behavior

same
convergence
as

baKhGf
descent
3) Mini batch
gradient : -
-

→ takes the best of both worlds .

→ Performs an
update for batch of
every
mini

examples
training
a-
.

a- O -
D -4510 ; [Link]?yCi:i+n )
→ reduces the Variance of the parameter updates ,

which leads to stable

more
convergence .

→ can make use

of highly optimized matrix

operations .

-
Chew : -

①
Choosing
a
proper learning rate is difficult .

too small
learning rate → slow convergence .

too large learning rate → hinder

convergence/
even
divergence
②
learning rate schedules
try to
adjust the
learning rate

during training by e.g .

annealing i. e.
reducing
rate to
according predefined
learning
a
the

schedule or when the

change
in
objective fn .

below hreshold these

between epochs falls a
.

schedules and freeholds however

,
have to be
,

advance
defined in .

③ Same
learning rate
applies to an parameter

updates .

If our data is
sparse and our

features have different frequencies

very
we
,

to
might not want to update all of them some

extent , but perform a

larger update for rarely

ocaeñngfeatu
Gradiertdesarttt: -

Men : -

SGD has trouble i

navigating
ravines - e .

where the much

areas surface curves more

dimension than .€ which

steeply
in one in another

are common around local Optima) .

In these

scenarios
,
SGD oscillates across the slopes of

while hesitant
the ravine
only making progress
the bottom towards the local
along optimum .

SGD

Momentum :
helps accelerate SGD in the relevant

and
direction dampens oscillations .

Of =
8%+77%510 )
o =
o -
Ot
 8- momentum coefficient f friction coefficient)

usually 0.9 .

when momentum push ball

Essentially using we a
,
,

down a hill .
The ball accumulates momentum

as
it rolls downhill
, becoming faster and
faster
the
way
on .

Momentum term increases for dimensions whose

and
gradients point in the same directions

reduces updates for dimensions whose

gradients
directions
change
.

oscillation
faster convergence ,
reduced .

SGD with

momentum .

Nesterov's accelerated gradient :-(NAG )

-

However, a ball that rolls down

a hill
, blindly following
the
slope ,
is
highly
 We would like to have a smarter
unsatisfactory .

ball that has a notion of where it

ball a
,

so that it knows to slow down before

going
is

the hill slopes up again

.

→ we know that we will use our momentum

term rut , to move the

parameters .

→
Computing ( o -

8%, ) gives
us an
approximation

position of the
of the next
parameters .

lookahead
→ we can
efficiently by calculating
now

the
gradient not went .
our current
parameters
0 but wrt .

approximate future position

of our
parameters .

so
4- =
f- ,
-117
To to -64 ) ,

0 =
0 -

Of .
-

Now that able to

we are
adapt our
updates

to the slope of our error

function and
speed
, up

like to
SGD in turn
,
we would also adapt our

updates to individual to
each
parameter perform

larger smaller
updates their
depending
or
on

importance .

Ada_grad : -

Adapts the
learning rate to the
parameters ,

performing larger updates for infrequent and

smaller updates for frequent parameters .

-
Well suited for sparse
data .
 To lot ;))
9£ , ;
=
,

gradient of the
[Link] .

wer -

t .
the parameter Oi

[Link]#date:Ot i,- &t,i-N9t-+iAdagrad:Q-+i.- Q-i

at # me
step

÷¥gp;I It"
-

T
9 term
sum
of squares of past smoothing
Cex :/ e- 8)
gradients
to avoid division

by zero .

Sparse gradients -

learning rate is
high
frequent gradients learning rate is low
-

Adge ! Each
parameter gets its
-

own

learning rate .
 initial
Disadvantage the
gradients large
1.
If are
,
the

will be low for the

learning
rates

remainder of the
training .

to the continual accumulation

2. Due
of

squared gradients in the denominator

,

the
learning rate will continue to

decrease
during the
training ,
eventually
to
decreasing zero and
stopping
training .

Riaspnpi -

Instead
of
accumulating
the sum of squared
time
gradients over all
use
,
moving average .

E- [ golf PE[ g.)

=

←,
-14 -

e) 9+2
9

Decay constant (
usually 0.97

RMS [g)
+
=

\/E[gYt+E
[Link]?gy-9tAda-dtu:-
9- + , =
Ot -

Consider SGD :

•
It ,
=
% _n
±

Ota =
Of toot

should have the same

boy unit as
Ot .
If

the parameter had some

hypothetical units
,
the

to the parameter should be

changes changes in

those units as well .

Units
of oof ✗ units
of gt 2 dL ✗
1-
dot units
of of

the cost function J witless

assuming
is .

→ same for momentum

,
NAG .

and
80g witless
→
Adagrad RMS
Prop are

since they ratio of gradients

.

are
?⃝
Consider Newton 's method !
-

I
got ✗ High ✗ units ofot
÷-
.

dot
correct units for parameter updates .

Ada della corrects units in RMS

Prop ,

Newton's
Rearranging method
Cassuming a
diagonal Hessian )

¥ .
1- E.
Not
=
=

-0g
¥
÷, *
dot

the
since the RMS
of previous gradient
the denominator add
already
we
is presented in
,

numerator
RMS of bot in .

oof = -12ms [ so]

9£ .

Rms[gf
Adad : Adaptive Moment Estimation .

←
estimate of first
my
= B , Mt, + 4-B) Gt moment (mean )

Vt = P2 4- -
,
+ (1-132)%2
a
estimate second
of
moment Cuncerlered
variance )
where Bx , 132 are
usually get to 0-9 and 0£99

As initialized to vector
Mt and Vt are
of

0 's
,
they are biased towards zero ,

especially during
initial
steps .

Bias correction Ñt
Mtl
:
=

,t
-

-
B

if =
E-
1- Bat

9-a = 9- -
ñt

-
 Additional
strategies :
-

1. shuffle data before

your epoch
every
.

2. Use both norm .

Early stopping stop training when validation

3. :

did not for time

error improve some

(few epochs ) .

4 Sometimes to the
.

adding
noise
gradient helps
to escape
local minima .
You should

anneal the variance

of the noise .

Youshouldkno
① Batch gradient descent

② stochastic gradient descent

③ batch descent
gradient
Mini -

④ Momentum

⑤ Nesterov 's accelerated

gradient
⑥ Adagrad
⑦ RMSProp

Heady
⑧

⑨ Adam .