Theoretical Problems (11 points)
1. (5 points) Consider the quadratic objective function
Q(x) = 3×2
1 + x2
2 + 2x1x2 − x1 − x2
defined on x = [x1, x2] ∈ R2. Assume that we want to solve
x∗ = arg min
x
Q(x)
from x0 = 0.
• (1 point) Find A and b so that Q(x) = 1 2 x(cid:62)Ax − b(cid:62)x. • (2 point) For gradient descent method with constant learning rate η, what range should η belong
to? What is the optimal value of η, and what is the corresponding convergence rate?
• (1 points) For CG, how many iterations T are needed to find XT = x∗? Find values of α1, β1,
and α2.
• (1 point) For the Heavy-Ball method with constant η and β. What’s the optimal values of (η, β) to achieve the fastest asymptotic convergence rate, and what is the corresponding convergence rate?
2. (2 points) Consider the regularized logistic regression:
f (w) =
1 n
n (cid:88)
i=1
ln(1 + exp(−w(cid:62)xiyi)) +
λ 2
(cid:107)w(cid:107)2 2
where xi ∈ Rd and yi ∈ {±1}. Assume (cid:107)xi(cid:107)2 ≤ 1 for all i.
• (1 point) find the smoothness parameter L of f (w). • (1 point) find an estimate of Lipschitz constant G in the region {w : f (w) ≤ f (0)} which holds
for all dataset {xi} such that (cid:107)xi(cid:107)2 ≤ 1.
3. (2 points) Consider training data (xi, yi) so that (cid:107)xi(cid:107)2 ≤ 1 and yi ∈ {±1}, and we would like to solve
the linear SVM problem
f (w)(cid:44)
min w
(cid:34)
1 n
n (cid:88)
(1 − w(cid:62)xiyi)+ +
i=1
(cid:35)
λ 2
(cid:107)w(cid:107)2 2
using subgradient descent with w0 = 0, and learning rate ηt ≤ η < 1/λ.
• (1 point) Let C = {w : (cid:107)w(cid:107)2 ≤ R}. Find the smallest R so that for all training data that satisfy
the assumptions of the problem, subgradient descent without projection belongs to C.
1
• (1 point) Find an upper bound of Lipschitz constant G of f (w) in C.
4. (2 points) Given a nonsmooth function, we would like to find its smooth approximation.
• (1 point) Find a closed form solution of
• (1 point) Let x ∈ Rd, find
φγ(x) = min
z
(cid:20) (1 − z)+ +
(z − x)2
(cid:21)
.
1 2γ
f (x) = min z∈Rd
(cid:20) (cid:107)z(cid:107)2 +
1 2γ
(cid:107)x − z(cid:107)2 2
(cid:21)
.
Proof. Let z achieves the minimum on the right hand side. If (cid:107)x(cid:107)2 ≤ γ, then z = 0 is a solution, and
If (cid:107)x(cid:107)2 > γ, then z = (1 − γ/(cid:107)x(cid:107)2)x, and
f (x) =
1 2γ
(cid:107)x(cid:107)2 2.
We thus obtain
f (x) = (cid:107)x(cid:107)2 − γ/2.
f (x) =
(cid:40) 1
2γ (cid:107)x(cid:107)2 2 (cid:107)x(cid:107)2 − 0.5γ
(cid:107)x(cid:107)2 ≤ γ otherwise
Programming Problem (4 points)
We consider optimization with the smoothed hinge loss, and randomly generated data.
• Use the python template “prog-template.py”, and implement functions marked with ’# implement’.
• Submit your code and outputs. Please note that in real machine learning problems, strong-convexity settings are often associated with L2 regularization: it is necessary to choose a proper regularization to better estimate true w. Thus, you should
1. choose the most proper setting mentioned in “prog-template.py” for real problems (including λ,
γ, and the optimizer);
2. Try some different λ and discuss how λ influences optimization and prediction respectively.
2
