L7 - Gradient Descent, Convex Optimisation, Bracketing

Question 1

What is the purpose of Gradient Descent? What type of function is it?

Answer 1

An iterative optimisation function to determine the minimum point of a convex set. It is a Convex Function.

Question 2

How does Gradient Descent work to solve Convex Optimisation?

Answer 2

Algorithm iteratively tunes the parameters in order to iterate towards the minimum point. As algorithm nears the minimum point, the jumps towards minimum decrease so as not to overshoot.

Question 3

In the context of ML, what does the gradient represent?

Answer 3

The relationship between independent and dependent variables.

Question 4

What is tuned in order to establish the minimum of a convenient function?

Answer 4

Parameter of the GD algorithm.

Question 5

In ML, what is GD used to establish?

Answer 5

Minimum of the models cost function.

Question 6

Upon each iteration of GD, what happens to the size of the steps towards the min. value? Why is this needed?

Answer 6

Size of step decreases to safeguard against overshooting the minimum point.

Question 7

What is a Convex Optimisation problem?

Answer 7

A problem in which we want to find the minimum or maximum of a convex function.

Question 8

What determines if a function is convex?

Answer 8

A function is convex if for any 2 points in the domain, a line drawn between the points is always above the function graph.

Question 9

How many minimum points does a convex function have?

Answer 9

1

Question 10

How do we use Jensens Inequality or the Second Derivative Test to determine whether a function is convex?

Answer 10

1. Jensens Inequality - If for any 2 X and Y points in the domain, and for all 0 < t < 1, the line connecting the points is entirely above the function graph.
   2. Second Derivative Test - If the second derivative of the function is non-zero for all X’s in the domain, the function is known to be convex.

Question 11

What is the epigraph of a function? How can we used it to determine whether a function is convex?

Answer 11

The set of points in the domain the are located above the function graph.

Question 12

Give the definition of a Convex Set…

Answer 12

A set in which for any point in the set, the point if above the function graph.

Question 13

At the minimum of a convex function, what is the value of the derivative?

Answer 13

0

Question 14

What techniques do we use to find the minimum of a non-convex function?

Answer 14

Downhill Simplex or Bracketing

Question 15

Explain Bracketing…

Answer 15

Method used to find the minimum of a non-convex set in 1-d space. Start by establishing initial points either side of the minimal area (we must know the rough area of minimum). Iteratively decrease the bracket size, converging towards the minimum point. Repeat until convergence or timeout.

Question 16

Define Jensens Inequality and how it proves a function is convex…

Answer 16

States that a function is convex for is any 2 points on the secant line, the points lie above the graph of the function.

Question 17

What is the formula of Jensens Inequality?

Answer 17

For any X1 and X2 in the function domain …

tf(X1) + (1-t)f(X2) > f(tX1 + (1-t)X2), for all 0 < t < 1

Question 18

A function is convex iff…

Answer 18

It’s epigraph is a convex set

Question 19

What bracketing, there must be zero-crossing, what does this mean?

Answer 19

The bracketing points must be either side of 0.

Question 20

When bracketing, what is Bisection?

Answer 20

Iteratively narrow the bracket (a,b) to find new points an and b until convergence of minimum point is reached.

Question 21

What value should we shrink the bracket by?

Answer 21

0.382 (Golden ratio)

Question 22

What is Brent’s Method?

Answer 22

A method of parabolic interpolation in order to approximate the minimum value of a convex function.