Topic 8: Intro to Gradient Descent

Question 1

What can we say about ε in GD

Answer 1

“target accuracy”
Gradient Descent runtime scales logarithmically with target accuracy (ε)
O (log (1/ε)) number of steps

Question 2

Why is x0 ≠ 0 in GD

Answer 2

As gradient descent works logarithmically:
xt+1 =xt − ηtF ′(xt)

It would mean all xt onwards are multiplied by x0 so would all be 0 and the algorithm would never move
Furthermore if the algorithm starts at F’(x0) = 0
(ie x0 = critical point) then it would never move

Question 3

Where do we want xt to tend

Answer 3

xt -> 0 as t -> inf

Question 4

What is an objective function

Answer 4

The loss function
The function you want to maximise or minimise

Question 5

Describe the GD algorithm steps on a differentiable function F

Answer 5

Initial w1 and T>0 (number of steps)
set ηt > 0
for t=1 to T
wt+1 = wt − ηt ⋅ ∇F(wt)
output wt

Question 6

what is a differentiable function

Answer 6

If it has a well-defined derivative at every point in its domain

Question 7

What properties does a function need to have for gd

Answer 7

Differentiable
convexity and lipschitzness are ideal
existence of at least one minima

Question 8

why does gradient descent converge faster on strongly convex functions compared to non-convex ones

Answer 8

strong convexity:
provides unique global minimum
provides a convergence rate guarantee for gradient descent

Question 9

what is k in gd

Answer 9

k is a constant parameter chosen from the interval (0,1)
It’s a tuning parameter that allows you to control the size of the step length
is not always present in all gd

Question 10

will gd find local minima for non convex non lipshcitz functions

Answer 10

yes
as is often the case irl, functions are not convex and lipschitz
minima is still found through careful consideration of step size and algorithm parameters