Homework 1: Regularized Regression & Statistical Estimators

Introduction In this homework we will explore gradient based optimization and explain in detail how gradient descent can be implemented. Gradient based algorithms have been crucial to the development of machine learning in the last few decades. The most famous example is the backpropagation algorithm used in deep learning, which is in fact just an application of a simple algorithm known as (stochastic) gradient descent. We will first implement gradient descent from scratch on a deterministic problem (no data), and then extend our implementation to solve a real world regression problem. We then also look at the notions of bias, variance and MSE of statistical estimators. Points Allocation There are a total of 28 marks.

• Question 1 a): 3 marks
• Question 1 b): 1 mark
• Question 1 c): 2 marks
• Question 1 d): 2 marks
• Question 1 e): 5 marks
• Question 1 f): 4 marks
• Question 1 g): 1 mark
• Question 1 h): 2 marks
• Question 1 i): 4 marks
• Question 2 a): 1 mark
• Question 2 b): 1 mark
• Question 2 c): 1 mark
• Question 2 d): 1 mark

What to Submit

• A single PDF file which contains solutions to each question. For each question, provide your solution in the form of text and requested plots. For some questions you will be requested to provide screen shots of code used to generate your answer— only include these when they are explicitly asked for.
• .py file(s) containing all code you used for the project, which should be provided in a separate .zip file. This code must match the code provided in the report.
• You may be deducted points for not following these instructions.
• You may be deducted points for poorly presented/formatted work. Please be neat and make your solutions clear. Start each question on a new page if necessary.
• You cannot submit a Jupyter notebook; this will receive a mark of zero. This does not stop you from developing your code in a notebook and then copying it into a .py file though, or using a tool such as nbconvert or similar.
• We will set up a Moodle forum for questions about this homework. Please read the existing questions before posting new questions. Please do some basic research online before posting questions. Please only post clarification questions. Any questions deemed to be fishing for answers will be ignored and/or deleted.
• Please check Moodle announcements for updates to this spec. It is your responsibility to check for announcements about the spec.
• Please complete your homework on your own, do not discuss your solution with other people in the course. General discussion of the problems is fine, but you must write out your own solution and acknowledge if you discussed any of the problems in your submission (including their name(s) and zID).
• As usual, we monitor all online forums such as Chegg, StackExchange, etc. Posting homework questions on these site is equivalent to plagiarism and will result in a case of academic misconduct.
• You may not use SymPy or any other symbolic programming toolkits to answer the derivation questions. This will result in an automatic grade of zero for the relevant question. You must do the derivations manually.

When and Where to Submit

• Due date: Week 4, Monday March 6th, 2023 by 5pm. Please note that the forum will not be actively monitored on weekends.
• Late submissions will incur a penalty of 5% per day from the maximum achievable grade. For example, if you achieve a grade of 80/100 but you submitted 3 days late, then your final grade will be 80 􀀀 3 5 = 65. Submissions that are more than 5 days late will receive a mark of zero.
• Submission must be made on Moodle, no exceptions.

Question 1. Gradient Based Optimization

The general framework for a gradient method for finding a minimizer of a function f : defined by where $\alpha_k > 0$ is known as the step size, or learning rate. Consider the following simple example of minimizing the function , we first note that . We then need to choose a starting value of x, say $x_0 = 1$. Let’s also take the step size to be constant, $\alpha_k = \alpha = 0.1$. Then we have the following iterations: ...

and this continues until we terminate the algorithm (as a quick exercise for your own benefit, code this up and compare it to the true minimum of the function which is x= 􀀀1). This idea works for functions that have vector valued inputs, which is often the case in machine learning. For example, when we minimize a loss function we do so with respect to a weight vector, When we take the stepsize to be constant at each iteration, this algorithm is known as gradient descent. For the entirety of this question, do not use any existing implementations of gradient methods, doing so will result in an automatic mark of zero for the entire question.

Question 2. Gradient Descent for Learning Combinations of Models

In this question, we discuss and implement a gradient descent based algorithm for learning combinations of models, which are generally termed ’ensemble models’. The gradient descent idea is a very powerful one that has been used in a large number of creative ways in machine learning beyond direct minimization of loss functions as in the previous question. The Gradient-Combination (GC) algorithm can be described as follows: Let F be a set of base learning algorithms2. The idea is to combine the base learners in F in an optimal way to end up with a good learning algorithm. Let `(y; ^y) be a loss function, where y is the target, and ^y is the predicted value.3 Suppose we have data (xi; yi) for i = 1; : : : ; n, which we collect into a single data set D0. We then set the number of desired base learners to T and proceed as follows

...