[Solved] ML Homework4- SGD for Hinge loss

1. SGD for Hinge loss. We will continue working with the MNIST data set. The file template (skeleton sgd.py), contains the code to load the training, validation and test sets for the digits 0 and 8 from the MNIST data. In this exercise we will optimize the Hinge loss (as you seen in the lecture) using the stochastic gradient descent implementation discussed in class. Namely, at each iteration t = 1, we sample i uniformly; and if y_iw_t x_i < 1, we update:

wt+1 = (1 t)wt + tCyixi

and w_t+1 = (1 _t)w_t otherwise, where _t = ₀/t, and ₀ is a constant. Implement an SGD function that accepts the samples and their labels, C, ₀ and T, and runs T gradient updates as specified above. In the questions that follow, make sure your graphs are meaningful.

Consider using set xlim or set ylim to concentrate only on a relevant range of values.

• Train the classifier on the training set. Use cross-validation on the validation set to find the best ₀, assuming T = 1000 and C = 1. For each possible ₀ (for example, you can search on the log scale ₀ = 10⁵,10⁴,,10⁴,10⁵ and increase resolution if needed), assess the performance of ₀ by averaging the accuracy on the validation set across 10 runs. Plot the average accuracy on the validation set, as a function of ₀.
• Now, cross-validate on the validation set to find the best C given the best ₀ you found above. For each possible C (again, you can search on the log scale as in section (a)), average the accuracy on the validation set across 10 runs. Plot the average accuracy on the validation set, as a function of C.
• Using the best C, ₀ you found, train the classifier, but for T = 20000. Show the resulting w as an image.
• What is the accuracy of the best classifier on the test set?

2. SGD for multi-class cross-entropy. The skeleton file contains a second helper function to load the training, validation and test sets for all the digits. In this exercise

we will optimize the multi-class cross entropy loss using SGD. Recall the multi-class crossentropy loss discussed in the recitation (our classes are 0,1,,9):

Derive the gradient update for this case, and implement the appropriate SGD function.

• Train the classifier on the training set. Use cross-validation on the validation set to find the best ₀, assuming T = 1000. For each possible ₀ (for example, you can search on the log scale ₀ = 10⁵,10⁴,,10⁴,10⁵ and increase resolution if needed), assess the performance of ₀ by averaging the accuracy on the validation set across 10 runs. Plot the average accuracy on the validation set, as a function of ₀.
• Using the best ₀ you found, train the classifier, but for T = 20000. Show the resulting w₀,,w₉ as images.
• What is the accuracy of the best classifier on the test set?