[SOLVED] algorithm python workshop project

workshop project
August 10, 2019
The goal is to implement algorithms for (sparse) linear regression and to conduct experiments
The implementations and experiments should be conducted using python in a jupyter notebook. Every function you implement should have a doc strings that describes the role of the function arguments, the effect of the function, and the output of the function. Your code should not access the filesystem in any way.
Do at least two of the optional steps. (You can also propose to me other experiments that you want to carry out instead.)
1. Implement a function draw_observation that given a matrix A and a vector x0, outputs a realization of the random variable Ax0 +w, where w is a standard Gaussian.
2. Implement a function prediction_error that given A, x0 , x outputs the square prediction error 1/n Ax Ax02.
3. Implement a function loglikelihood that given A,x,y outputs the (scaled) log likelihood 1/n Ax y2.
4. Implement a function gradient that given A, x, y outputs the gradient of the above log likelihood function with respect to x
5. Implement a function gradient_descent that given A,y,T,,xinit runs gradient descent starting at xinit for T steps with step size . This function should use the previous one to compute a gradient in each step. The output of the function should be an array of all T + 1 iterates that gradient descent computed.
6. Implement a function plot_prediction that given A, x0 and a list of iterates plots the prediction errors of the iterates.
1

7. Implement a function plot_optimization that given A, y and a list of iterates plots the loglikelihoods of the iterates.
8. Implement a function random_unit_vector that given d outputs a random unit vector. You can obtain such a vector by first choosing a $d$-dimensional standard Gaussian vector v and then scaling this vector by 1/v.
9. Implement a function random_model that given d and n, outputs a matrix A and a vector x0 such that every entry of A is a standard Gaussian and x0 is a random unit vector.
10. Conduct some experiments. Choose values of d and n. Choose a step size and a number of steps T. Choose A and x0 using the function random_model. Choose xinit as a random unit vector. Show the plots for the prediction error and the loglikelihoods.
11. Optional: Conduct experiments to confirm that the prediction error scales like d/n
12. Implement a function random_sparse_model similar to random_model but adapted to sparse linear regression. This function should have the sparsity parameter k as an additional argument.
13. Optional: Implement LASSO in penalty form using subgradient de- scent and carry out experiments confirming the prediction error rate of O(logd) k/n. As a function of d,k,n how do you choose the parameter for this version of LASSO?
14. Optional: Implement LASSO in constraint form using projected gradi- ent descent and carry out experiments confirming the prediction error rate of O(logd)k/n. As a function of d,k,n how do you choose the parameter for this version of LASSO?
15. Optional: Compare the two implementations of LASSO
2