MATH3191/5191 T3 2022 Homework assignment
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework assignment (MATH3191/5191 T3 2022)
1. Determine whether the set C is convex. Provide a rigorous argument in each case. (a) Suppose that A,B ⊆ Rn are convex sets, and let
C = {z ∈ Rn | z = x − y for some x ∈ A,y ∈ B}.
(b) The set C ⊆ R3 is defined as
C = {(x,y,z)|(x2 + y2 + z2 − 1)2 + (z + 1)4 ≤ 1}.
(c)* The set C ⊆ Rn is such that any xi-slice of this set is convex, that is, for any c ∈ R and i ∈ {1, . . . ,n} the set
{x = (x1 , . . . ,xn )| x ∈ C, xi = c}
is convex.
2. Determine whether the function f : R → R, f(x) = |x|x2 is: convex, m-strongly convex for some m > 0, L-smooth for some L > 0. Provide an explanation.
3. Suppose that f : Rn → R is convex and bounded from above (that is, there exists an M ∈ R such that f(x) ≤ M for all x ∈ Rn ). Show that f must be a constant function.
4. Let f : Rn → R be an L-smooth and m-strongly convex function. We consider an algorithm that uses exact line searches along random directions. That is, given the previous iterate x we pick a direction v ∼ N(0,σ2 I), find the minimiser tmin of f along the line x + tv , t ∈ R, and let x + tminv be the next iterate.
(a) Use properties of L-smooth functions to deduce that for any x,v ∈ Rn and t ∈ R
f(x + tv) ≤ f(x) + tv · ∇f(x) + 
t2 ∥v∥2 . (1)
(b) Use minimisation on both sides of (1) to obtain an upper bound on the value f(x+tminv).
(c) Using the known bound
∥∇f(x)∥2 ≥ 2m(f(x) − f(x* ))
and the fact that for the coordinates vi , i ∈ {1, . . . ,n} of v ∼ N(0,σ2 I) we have Ev (vi(2)/∥v∥2 ) = 1/n, Ev (vivj /∥v∥2 ) = 0,
obtain a bound on E(f(xk+1) − f(x* )) in the form of a constant factor multiplied by E(f(xk ) − f(x* )).
(d)* Prove that to guarantee E(f(xk ) − f(x* )) ≤ ε, it is sufficient to require that k ≥ 
ln ( 
) ,
where C is some constant.
The last question asks you to do some coding. Please submit your code in a separate file. Your code can be in python, MATLAB or any other suitable language.
The data for the question is given within the question, and can also be copied from a text file that accompanies this description.
5. Given a set {(xi ,yi )}
of labelled data, with xi ∈ Rn and yi ∈ {−1, 1} for i ∈ {1, . . . ,N}, the goal is to find w = (u,v), with u ∈ Rn and v ∈ R that minimises the objective function
L(w) = − 
「(l)j:
1 ln(1 − p(xj ,w)) + j 
ln(p(xj ,w))
,
where
p(x,w) = 
with w = (u,v).
(a) Let
{
so that L(w) = 
z
fi (w). Find an explicit expression for the gradients of fi (w). (b) Show that for each i the function φi (w) = ∥∇fi (w)∥2 is bounded by some quantity that
doesn’t depend on w .
(c) Use the bound obtained on the previous item to show that there exists some B > 0 such that the expected value of ∥∇fi (w)∥2 taken over the index i distributed uniformly at random on {1, . . . ,N} is bounded by B2 , that is,
Ei (∥∇fi (w)∥2 ) ≤ B2 .
(d) Implement the stochastic gradient descent method for the following (two-dimensional) data {(xi ,yi )}
= {(x
,x
,yi )}
= {(−0.7, −0.3, 1), (−0.4, −0.8, 1), (−1.1, −0.3, 1), (−0.2, −0.3, 1), (−0.5, −0.2, 1), (−0.1, 0.1, 1), (−0.5, −0.4, 1), (0.7, 0.8, −1), (0.1, −0.3, −1), (−0.3, 0.2, −1), (0.2, 0.2, −1), (0.3, 0.3, −1), (0.6, 0.2, −1), (0.5, 0.8, −1), (0.4, −0.3, −1)}.
Use different values for the steplength and the number iterations. Record the best solution you managed to obtain (both the approximate minimiser wk and the function value L(wk )) along with the value of steplength and the number of iterations that you used.
(e)* By running the stochastic gradient descent for 10000 iterations starting with w0 = (0, 0, 0) and different values of steplength and recording the function value at the average L(
T ) (with T = 10000), find empirically what steplength value works best, that is, results in the lowest value of L(
T ).
(f)* Using an estimate of the optimal solution obtained in (d) and the bound on B2 computed earlier, estimate the value αopt using results from the lectures (see Proposition 5.1 on page 90 in the textbook or slide 12 in week 5 part 2 of the lecture notes). Explain how this value compares to to the practically optimal value obtained in (e), and how the calculated value L(
T ) − L(w* ) compares with the relevant theoretical bound.
2022-11-08