Description

Optimization for Machine Learning
Gradient Descent
Solve Exercises 15, 17 and 19 from the lecture notes.
Computing Fixed Points
EPFL
Martin Jaggi & Nicolas Flammarion github.com/epfml/OptML course

Gradient descent turns up in a surprising number of situations which apriori have nothing to do with optimization. In this exercise we will see how computing the fixed point of functions can be seen as a form of gradient descent. Suppose that we have a 1-Lipschitz continuous function g : R→R such that we want to solve for
g(x) = x.
A simple strategy for finding such a fixed point is to run the following algorithm: starting from an arbitary x0, we iteratively set
xt+1 = g(xt). (1)
Practical exercise. We will try solve for x starting from x0 = 1 in the following two equations:
x = log(1 + x), and (2) x = log(2 + x). (3)
Follow the Python notebook provided here:
colab.research.google.com/github/epfml/OptML course/blob/master/labs/ex03/template/notebook.ipynb
What difference do you observe in the rate of convergence between the two problems? Let’s understand why this occurs.
Theoretical questions.
1. We want to re-write the update (1) as a step of gradient descent. To do this, we need to find a function f such that the gradient descent update is identical to (1):
xt+1 = xt − γf0(xt) = g(xt).
Derive such a function f.
2. Give sufficient conditions on g to ensure convergence of procedure (1). What γ would you need to pick? Hint: We know that gradient descent on f with fixed step-size converges if f is convex and smooth. What does this mean in terms of g?
3. What condition does g need to satisfy to ensure linear convergence? Are these satisfied for problems (2) and (3) in the exercise?