Reference no: EM132995790

Question 1. Rewrite the objective in the form

f(x) = 1/2n ||y - Ax||²

where A is the data matrix and n is the number of data points.

Question 2. Implement the gradient descent (GD) method which consists of the iter- ations:

x^k+1 = x^k - α_k∇f(x_k)

where

∇f(x) = -1/n A^T(y - Ax).

where we choose α_k = a > 0 for some constant a. Tune your algorithm to different values of a. You can stop your algorithm when ||∇(x)|| ≤ ε with ε = 10^-2. For which values of a, do you see divergence or convergence in your algorithm?

How close is the solution you compute with GD is to the actual solution
x^∗ = [x^∗₁, x^∗₂, x₃^∗ ] where x^∗ = (A^T A)^-1A^T y?

Question 3. Plot the level sets of the objective f(x₁, x₂, x₃) when x₁ = x∗₁. In other words, plot the level sets of f(x₁∗ , x₂, x₃) versus x2 and x₃. Mark the iterates of gradient descent on the level set plots and verify that gradient descent moves perpendicular to the level sets. Visualize the function f(x₁∗ , x₂, x₃) in 3D as a function of x₂ and x₃. Does it look like a "cereal bowl"?

Question 4. Repeat the previous question with different choise of the stepsize αk in your implementation

(a) αk = a > 0 is a constant. How does the performance change when we vary a? For which values of a, do you see divergence or convergence? How large a should be for you to observe divergence of the GD?
(b) Repeat part (a) with α_k = a/k varying the values of a.
(c) Repeat part (a) with α_k = a/√k. Based on these experiments, what is the best stepsize rule in your opinion to get the best performance?

Question 5. Note that

f(x) = X f where f = 1 (y - aT x)2

is the loss of the data point i where aT is the i-th row of the data matrix

A. Note that each row comes from a single data point and the gradient of fi is

∇fi(x) = -ai (yi - ai x).

At step k, choose a data point index ik uniformly randomly from the set of all indices {1, 2, . . . , n} and consider the iterations

xk+1 = xk - αk∇fik (xk)

where the replace the gradient in the GD method with a random estimate of it; i.e. ∇fik . This is called the stochastic gradient method (SGD).

Repeat questions 3) and 4) for stochastic gradient descent. Can SGD be faster than GD for different values of target accuracy ε = 10-1, 10-2, 10-3, . . . etc? Please explain.

Attachment:- Question.rar