Description

Exam Optimization for Machine Learning – CS-439
Prof. Martin Jaggi

For your examination, preferably print documents compiled from automultiple-choice.
+0/2/59+
First part, multiple choice
There is exactly one correct answer per question.
by
We write A for the vector x
Question 1
i-th coordinate, is large value of λ.
n
gradient descent (with optimal stepsize), i.e. how many iterations T does it take to reach suboptimality f(xT) − f? ≤ ε?

+0/3/58+
Question 3 Given access to a stochastic gradient oracle gSG: Rn → Rn we can implement stochastic gradient descent on f. Assume the stochastic oracle outputs
gSG(x) := gG + ξ
for every call, where ξ ∈ Rn is a random variable with Eξ = 0, and Ekξk2 ≤ σ2 (and σ2 > 0). What
no answer is correct


gA(x) :=

Oracle A and B are both biased.
Question 5 no answer is correct
Question 6
constant stepsize γ) converges as:
Oracle D over C if ε > 10b.
Oracle D over C if ε ≤ 10b.

+0/4/57+
Convexity and Smoothness
For each of the functions below, verify whether they are (1) convex, (2) strictly convex, (3) strongly convex, and (4) smooth:
A. f(x) = x, x ∈ R B. f(x) = sin(x), x ∈ R
C. f(x) = ReLu(ax + b), x ∈ R D. f(x) = ReLu(a x (a x + b ) + b ), x ∈ R2
E. f(x) = e−x
G. f(x) = x>Ax, x ∈ R ,
where
, a,b ∈ R2 .
Question 7 convex + smooth convex
convex + strictly convex
smooth
none of these properties
Question 8
convex convex + strictly convex
convex + smooth smooth
none of these properties
Question 9
convex convex + smooth convex + strictly convex + strongly convex convex + strictly convex + strongly convex + smooth smooth convex + strictly convex none of these properties
+0/5/56+
Question 10 Given the function D. above, which are all of its properties?
convex + strictly convex convex + strictly convex + strongly convex smooth convex + strictly convex + smooth convex convex + smooth
none of these properties
Question 11
smooth convex + smooth convex
convex + strictly convex
none of these properties
Question 12
smooth
convex + smooth
convex convex + strictly convex none of these properties
Question 13
convex + strictly convex
convex convex + strictly convex + smooth convex + smooth smooth none of these properties
+0/6/55+
Smoothness and Strong Convexity
Consider an iterative optimization procedure.
Question 14 Which one of the following three inequalities is valid for a smooth convex function f for some L ∈ R:

+0/7/54+
Second part, true/false questions
Question 16 (Linear Minimization Oracle) The LMO used in the Frank-Wolfe algorithm is given as LMOX(g) := argmin being the convex hull of any bounded set A ⊂ Rd,
s∈X
Question 17 minx∈X
X
Question 18
(µ > 0)-strongly convex function f converges as O(1/ ε).
Question 19 convex function f converges as O(1/ ε).
Question 20 set.
Question 21
+0/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.

+0/9/52+
Question 23: 3 points. In the same setting as the previous page, recall that the standard simplex is defined as . For some fixed positive constants ci ∈ R for i ∈ [n], let y? be the optimum of
.
minimize the variance E[kgt − ∇f(xt)k2] gt

+0/10/51+
Convergence of Signed Gradient Descent
Suppose that f : Rd → R is an L-smooth function. Let us look at an algorithm which only uses the coordinate-wise signs of the gradient, with step-size γ > 0:
xt+1 := xt − γsign(∇f(xt)). (sgnGD)

+0/11/50+
Coordinate descent vs. Gradient descent
Recall that for a function f, Lc coordinate-wise smoothness is defined as

+0/12/49+
Question 28: 3 points. Define the symmetric matrix A ∈ Rd×d to be A := εId + 1d1>d where Id is the identity matrix and 1d is a vector of all 1s. For some b ∈ Rd, consider the quadratic function
. (FQ)
Compute the Lc and Lg smoothness constants for f.

+0/13/48+
Smooth non-convex functions
Question 30: 3 points. Suppose that f is a possibly non-convex, twice differentiable function such that the Hessian is bounded in spectral norm
+0/14/47+
Over-parameterized problems
Suppose that f satisfies the sum structure:
+0/15/46+
Question 32: 2 points. Using the result in the previous question prove that
E[f(xt+1)|xt] ≤ f(xt) − γ k∇f(xt)k2 + γ2L2(f(xt) − f(x?)). (OPS)
Hint: Plug in the SGD update into the smoothness bound on f.

For your examination, preferably print documents compiled from automultiple-choice.