Description

Pour votre examen, imprimez de préférence les documents compilés à l’aide de auto-multiple-choice.
+1/2/59+
First part, multiple choice
Convexity and Smoothness
1
0.5
−0.5 −1
convex
smooth convex + smooth
none of these properties
convex
smooth convex + smooth
convex + strictly convex
+1/3/58+
Question 3 Given the function C. above, which are all of its properties?
convex + strictly convex convex + strictly convex + strongly convex + smooth
convex
convex + smooth
smooth
Question 4 convex + strictly convex smooth
convex
convex + smooth
none of these properties
Question 5 convex + smooth
convex + strictly convex smooth
convex
none of these properties
Question 6
smooth
convex
convex + smooth
none of these properties

+1/4/57+
Question 7 Given the function G. above, which are all of its properties?
convex + strictly convex + strongly convex + smooth
convex
(x ) < 1.
+1/5/56+
Question 11 Suppose we run 1000 steps of gradient descent on f(x) as above, with correct stepsizes.
Which of the following is true about the error f(xt)−f?, relative to f(x0)−f?? Assume that the following
The error is
The error is
The error is
The error is
Adaptive methods
Question 12
Non-smooth optimization
Question 13
x? = x? − L1 x x? = proxh, 1 (x − x x? = x? − L1 +1/6/55+
Empirical comparison of different methods
Suppose that your roommate wanted to minimize a linear regression problem with `2 regularization.
Last night, she overheard you mumbling in your sleep something about “SGD”, “gradient descent” and
None of them
Only Algorithm B
All of them
SGD with constant stepsize
Gradient descent with stepsize 1/L
Gradient descent with incorrect stepsize
SGD with stepsize decreasing as
SGD with stepsize decreasing as O(1/t)
SGD with stepsize decreasing as O(1/t)
Gradient descent with stepsize 1/L SGD with stepsize decreasing as
Gradient descent with incorrect stepsize
SGD with constant stepsize
Gradient descent with incorrect stepsize
SGD with stepsize decreasing as SGD with constant stepsize

+1/7/54+
Second part, true/false questions
Question 18 (Frank-Wolfe convergence in duality gap) On a convex and smooth function, and a bounded and convex constraint set, let x0,x1,… be the iterates of the Frank-Wolfe algorithm.
The duality gap (or Hearn gap) g(x ) := hx − s,∇f(x )i of the iterates satisfies g(x ) ≤ O(1/t).
Question 19
√
functions.
Question 20
Question 21
Question 22
+1/8/53+
Third part, open questions
Answer in the space provided! Your answer must be justified with all steps. Do not cross any checkboxes, they are reserved for correction.

+1/9/52+
Let x1 ∈ Rd be an arbitrary initial point and consider the following iterates defined for t ≥ 1 as:

+1/10/51+ Question 26: 4 points. Prove an upper bound of the form

where C1 and C2 are constants.

+1/11/50+
Question 28: 4 points. Unroll the recursion proven in previous question for t = 1,··· ,T to get a upper bound on depending on and the function values

+1/12/49+
Averaged SGD for Quadratic Functions
Throughout this exercise we consider minimizing a convex quadratic function:

+1/13/48+
Question 32: 4 points. Compute a closed-form expression for αt in function of t, γ, H, the initial iterate α0 and the noise vectors (εk)tk=1.

+1/14/47+
Question 34: 4 points.
Using the properties given on the noise εt and the expressions obtained above compute the value of

+1/15/46+
Question 37: 4 points (BONUS, optional question). Prove the inequality , for all u ∈ [0,1].

0 1 2 3 4

(We have used this in Question 35. Previous questions are not necessary to prove the inequality.)
Pour votre examen, imprimez de préférence les documents compilés à l’aide de auto-multiple-choice.

Pour votre examen, imprimez de préférence les documents compilés à l’aide de auto-multiple-choice.