[SOLVED] COMP6211E Assignment 2

Theoretical Problems
1. (5 points) Consider the quadratic objective function
Q(x) = 3×21
+ x22
+ 2x1x2 􀀀 x1 􀀀 x2
dened on x = [x1; x2] 2 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
2x>Ax 􀀀 b>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 nd 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
Xn
i=1
ln(1 + exp(􀀀w>xiyi)) +

2
kwk22
where xi 2 Rd and yi 2 f1g. Assume kxik2  1 for all i.
• (1 point) nd the smoothness parameter L of f(w).
• (1 point) nd an estimate of Lipschitz constant G in the region fw : f(w)  f(0)g which holds
for all dataset fxig such that kxik2  1.
3. (2 points) Consider training data (xi; yi) so that kxik2  1 and yi 2 f1g, and we would like to solve
the linear SVM problem
min
w
f(w),
”
1
n
Xn
i=1
(1 􀀀 w>xiyi)+ +

2
kwk22
#
using subgradient descent with w0 = 0, and learning rate t   < 1=.
• (1 point) Let C = fw : kwk2  Rg. 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