Rules

.  English: Answer the questions in English. Otherwise, you’ll lose half of the points.

.  Electronic submission: Turn in solutions electronically via Blackboard.  Be sure to submit your homework as a single readable file.

.  Collaboration  policy:  Collaboration is allowed for all problems,  but please list all the people with whom you discussed.  Crediting help from other classmates will not take away any credit from you.

Notably, only insightful discussions are allowed. Directly sharing the solutions is prohibited. The details of the collaboration policy for this course are available in the Resources tab on Piazza.

.  Time issue: Note that late submissions will result in discounted scores: 0-24 hours → 80%, 24-72 hours → 50%, 72 or more hours→ 0%.

.  Score and weight:

DDA4210: 100 points, the weight of this assignment in the final grade is 10%. AIR6002: 150 points, the weight of this assignment in the final grade is 15%.

. Important Note:  Problems/Sub-problems with a label  [AIR6002] are only required for master students in AIR6002.

.  Questions on assignment:  Start early and come to TA office hours with your questions on the assignments.

1. Basics (you are assumed to know the answers before taking this course) Answer each of the following problems with 1-2 short sentences.            [8 points]

The dataset bv_data.csv is provided and has a header denoting which columns correspond to which values.   Using  this  dataset,  plot  learning  curves  for  1st-,  2nd-,  6th-,  and  12th- degree polynomial regression (4 separate plots) by following these steps for each degree d ∈ {1, 2, 6, 12}:

(1)  For each N ∈ {20, 25, 30, 35, ··· , 100} :

i.  Perform 5-fold cross-validation on the first N points in the dataset (setting aside the other points), computing the both the training and validation error for each fold.

*  Use the mean squared error loss as the error function.

* Use NumPy’s polyfit method to perform the degree-d polynomial regression and NumPy’s polyval method to help compute the errors.  (See the example code and NumPy documentation for details.)

* When partitioning your data into folds, although in practice you should ran- domize your partitions, for the purposes of this set, simply divide the data into K contiguous blocks.

ii.  Compute the average of the training and validation errors from the 5 folds.

(2)  Create a learning curve by plotting both the average training and validation error as functions of N.      [10 points]

3.  Find the closed-form solutions of the following optimization problems (W ∈ RK×D, N ≫ D > K):

(a) minimizeW ,2                                        [5 points]

(b) minimizeW ,b 2 F(2)                [7 points]

4. Consider the following problem

minimize  - ∥WΦ − Y∥F  + - ∥W∥F

where  ∥ · ∥F  denotes the Frobenius norm; Y ∈ RK×N, Φ = [ϕ(x1 ),ϕ(x2 ),...,ϕ(xN )], xi  ∈ RD , i = 1, 2,...,N, and ϕ is the feature map induced by a kernel function k( · , · ).  Prove that for any x ∈ RD, we can make prediction as

y = Wϕ(x) = Y (K + λI)−1 k(x),

where K = Φ⊤ Φ and k(x) = [k(x1 , x), k(x2 , x),..., k(xN , x)]⊤ .                                     [14 points]

5.   Compute the space and time complexities (in the form of big O, consider only the training stage) of the following algorithms:        [6 points]

(a)  Ridge regression (Question 2(b)) with the closed-form solution

(b)  PCA (N data points of D-dimension, choose d principal components)

(c) Neural network with architecture D − H1 − H2 − K on a mini-batch of size B  (consider only the forward process and neglect the computational costs of activation functions)

*  [Hint:  the time complexity of A  ∈  Rm×n  × B  ∈  Rn×l  is O(mnl);  the time complexities of eigenvalue decomposition and inverse of an n × n matrix are both O(n3 ).]

6.   Prove the convergence of the generic gradient boosting  algorithm  (AnyBoost).   Specifically, suppose in the algorithm of AnyBoost (page 14 of Lecture 02), the gradient of the objective function L is L-Lipschitz continuous, i.e., there exists L > 0 such that

∥∇L(H) − ∇L(H′)∥ ≤ L∥H − H′∥

holds for any H and H′. Suppose in the algorithm, α is computed as

αt+1 = −  .

Then the ensemble model is updated as Ht+1  = Ht  + αt+1ht+1 .  Prove that the algorithm either

terminates at round T with ⟨∇L(Ht), ht+1⟩ or L(Ht) converges to a finite value, in which case

limt→∞⟨∇L(Ht), ht+1⟩ = 0.

* [Hint: Using the following result: Suppose L : H → R and ∥∇L(F)−∇L(G)∥ ≤ L∥F −G∥ holds for any F and G in H, then L(F + wG) − L(F) ≤ w⟨∇L(F), G⟩ +  ∥G∥2  holds for any w > 0.] [14 points]

7. Stochastic gradient descent (SGD) is an important optimization tool in machine learning, used every- where from logistic regression to training neural networks.  In this problem, you will be asked to first implement SGD for linear regression using the squared loss function.  Then, you will analyze how several parameters affect the learning process.

Linear regression learns a model of the form:

f (x1 , x2 , ··· , xd ) =  wi xi ) + b

(a) We can make our algebra and coding simpler by writing f (x1 , x2 , ···  , xd) = wTx for vectors w and x. But at first glance, this formulation seems to be missing the bias term b from the equation above. How should we define x and w such that the model includes the bias term?   [3 points]

Linear regression learns a model by minimizing the squared loss function L, which is the sum across all training data {(x1 , y1 ) , ··· , (xN , yN )} of the squared difference between actual and predicted output values:

L(f) =  (yi− wT xi）2

(b)  SGD uses the gradient of the loss function to make incremental adjustments to the weight vector w.   Derive  the  gradient  of the squared loss function with respect to  w  for linear regression. [3 points]

[AIR6002] The following few problems ask you to work with the first of two provided Jupyter notebooks for this problem, notebook  7  part1.ipynb, which includes tools for gradient descent visualization.  This notebook utilizes the files sgd_helper.py and multiopt.mp4, but you should not need to modify either of these files.  In addition, to run the animation code provided in this notebook, you may need to install FFmpeg, which includes a library for handling multimedia data. For step-by-step instructions on installing FFmpeg, please refer to the file installing_ffmpeg.pdf.

For your implementation of problems (c)-(e), do not consider the bias term.

(c)  [AIR6002] Implement the loss, gradient, and SGD functions, defined in the notebook, to perform SGD, using the guidelines below:

- Use a squared loss function.

- Terminate the SGD process after a specified number of epochs, where each epoch performs one SGD iteration for each point in the dataset.

- It is recommended, but not required, that you shuffle the order of the points before each epoch such that you go through the points in a random order. You can use numpy.random . permutation.

- Measure the loss after each epoch. Your SGD function should output a vector with the loss after each epoch, and a matrix of the weights after each epoch (one row per epoch).  Note that the weights from all epochs are stored in order to run subsequent visualization code to illustrate SGD.    [10 points]

(d)  [AIR6002] Run the visualization code in the notebook corresponding to problem (d).  How does the convergence behavior of SGD change as the starting point varies?  How does this differ between datasets 1 and 2? Please answer in 2-3 sentences.                                [3 points]

(e)  [AIR6002] Run the visualization code in the notebook corresponding to problem (e).  One of the cells-titled ”Plotting SGD Convergence”-must be filled in as follows. Perform SGD on dataset 1 for each of the learning rates η ∈ {1e − 6, 5e − 6, 1e − 5, 3e − 5, 1e − 4}. On a single plot, show the training error vs.  number of epochs trained for each of these values of η . What happens as η changes?                                    [6 points]

The following problems consider SGD with the larger, higher-dimensional dataset, sgd_data.csv. The file has a header denoting which columns correspond to which values.  For these problems, use the Jupyter notebook notebook  7  part2.ipynb.

For your implementation of problems  (f)-(h),  do  consider  the  bias term using your  answer to problem (a).

(f)  [AIR6002] Use your SGD code with the given dataset, and report your final weights.  Follow the guidelines below for your implementation:                          [6 points]

- Use η = e−15  as the step size.

- Use w = [0.001, 0.001, 0.001, 0.001] as the initial weight vector and b = 0.001 as the initial bias.

- Use at least 1000 epochs.

- You should incorporate the bias term in your implementation of SGD and do so in the vector style of problem (a).

- Note that for these problems, it is no longer necessary for the SGD function to store the weights after all epochs; you may change your code to only return the final weights.

(g)  [AIR6002] Perform SGD as in the previous problem for each learning rate η in

{e−10, e−11, e−12, e−13, e−14, e−15} ,

and calculate the training error at the beginning of each epoch during training.  On a single plot, show training error vs. number of epochs trained for each of these values of η.  Explain what is happening.          [3 points]

(h)  [AIR6002] The closed form solution for linear regression with least squares is

w = xixi(T))−1  xi yi ) .

Compute this analytical solution. Does the result match up with what you got from SGD? [3 points]

Answer the remaining questions in 1-2 short sentences.

(i)  [AIR6002] Is there any reason to use SGD when a closed form solution exists?      [3 points]

(j)  [AIR6002] Based on the SGD convergence plots that you generated earlier, describe a stop- ping condition that is more sophisticated than a pre-defined number of epochs.       [3 points]

(k)  [AIR6002] How does the convergence behavior of the weight vector differ between the per- ceptron and SGD algorithms?   [3 points]