微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-COMP9417
时间：2022-07-03
COMP9417 - Machine Learning
Homework 2: Newton’s Method and Mean Squared Error of
Estimators
Introduction In homework 1, we considered Gradient Descent (and coordinate descent) for minimizing a
regularized loss function. In this homework, we consider an alternative method known as Newton’s algo-
rithm. We will first run Newton’s algorithm on a simple toy problem, and then implement it from scratch
on a real life classification problem. We will also dig deeper into the idea of estimation and comparing
estimators based on bias, variance and MSE.
Points Allocation There are a total of 28 marks.
• Question 1 a): 1 mark
• Question 1 b): 1 mark
• Question 1 c): 1 mark
• Question 2 a): 2 marks
• Question 2 b): 2 marks
• Question 2 c): 5 marks
• Question 2 d): 1 mark
• Question 2 e): 3 marks
• Question 2 f): 5 marks
• Question 2 g): 1 mark
• Question 3 a): 3 marks
• Question 3 b): 2 marks
• Question 3 c): 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.
1
• 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 ques-
tions on these site is equivalent to plagiarism and will result in a case of academic misconduct.
When and Where to Submit
• Due date: Week 7, Monday July 11th, 2022 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 ex-
ample, 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 done through Moodle, no exceptions.
Page 2
Question 1. Introduction to Newton’s Method
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to in the question. Using existing implementations can result in
a grade of zero for the entire question. In homework 1 we studied gradient descent (GD), which is
usually referred to as a first order method. Here, we study an alternative algorithm known as Newton’s
algorithm, which is generally referred to as a second order method. Roughly speaking, a second order
method makes use of both first and second derivatives. Generally, second order methods are much
more accurate than first order ones. Given a twice differentiable function g : R→ R, Newton’s method
generates a sequence {x(k)} iteratively according to the following update rule:
x(k+1) = x(k) − g
′(x(k))
g′′(x(k))
, k = 0, 1, 2, . . . , (1)
For example, consider the function g(x) = 12x
2 − sin(x) with initial guess x(0) = 0. Then
g′(x) = x− cos(x), and g′′(x) = 1 + sin(x),
and so we have the following iterations:
x(1) = x(0) − x
(0) − cos(x0)
1 + sin(x(0))
= 0− 0− cos(0)
1 + sin(0)
= 1
x(2) = x(1) − x
(1) − cos(x1)
1 + sin(x(1))
= 1− 1− cos(1)
1 + sin(1)
= 0.750363867840244
x(3) = 0.739112890911362
...
and this continues until we terminate the algorithm (as a quick exercise for your own benefit, code this
up, plot the function and each of the iterates). We note here that in practice, we often use a different
update called the dampened Newton method, defined by:
x(k+1) = x(k) − α g
′(xk)
g′′(xk)
, k = 0, 1, 2, . . . . (2)
Here, as in the case of GD, the step size α has the effect of ‘dampening’ the update.
(a) Consider the twice differentiable function f : Rn → R. The Newton steps in this case are now:
x(k+1) = x(k) − (H(x(k)))−1∇f(x(k)), k = 0, 1, 2, . . . , (3)
where H(x) = ∇2f(x) is the Hessian of f . Explain heuristically (in a couple of sentences) how the
above formula is a generalization of equation (1) to functions with vector inputs. what to submit:
Some commentary
(b) Consider the function f : R2 → R defined by
f(x, y) = 100(y − x2)2 + (1− x)2.
Create a 3D plot of the function using mplot3d (see lab0 for example). Further, compute the
gradient and Hessian of f . what to submit: A single plot, the code used to generate the plot, the gradient
and Hessian calculated along with all working. Add a copy of the code to solutions.py
Page 3
(c) Using NumPy only, implement the (undampened) Newton algorithm to find the minimizer of the
function in the previous part, using an initial guess of x(0) = (−1.2, 1)T . Terminate the algorithm
when
∥∥∇f(x(k))∥∥
2
≤ 10−6. Report the values of x(k) for k = 0, 1, . . . ,K where K is your final
iteration. what to submit: your iterations, and a screen shot of your code. Add a copy of the code to
solutions.py
Question 2. Solving Logistic Regression Numerically
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to do so in the question. Using existing implementations can
result in a grade of zero for the entire question. In this question we will compare gradient descent
and Newton’s algorithm for solving the logistic regression problem. Recall that in logistic regresion,
our goal is to minimize the log-loss, also referred to as the cross entropy loss. For an intercept β0 ∈ R,
parameter vector β = (β1, . . . , βp) ∈ Rp, target yi ∈ {0, 1}, and feature vector xi = (xi1, xi2, . . . , xip)T ∈
Rp for i = 1, . . . , n, the (`2-regularized) log-loss that we will work with is:
L(β0, β) =
1
2
‖β‖22 +
λ
n
n∑
i=1
[
yi ln
(
1
σ(β0 + βTxi)
)
+ (1− yi) ln
(
1
1− σ(β0 + βTxi)
)]
,
where σ(z) = (1 + e−z)−1 is the logistic sigmoid, and λ is a hyper-parameter that controls the amount
of regularization. Note that you are provided with an implementation of this loss in helper.py.
(a) Suppose that you were going to solve this problem using gradient descent and chose to update
each coordinate individually. Derive gradient descent updates for each of the components β0, β1, . . . , βp
for step size α and regularization parameter λ. That is, derive explicit expressions for the terms †
in the following:
β
(k)
0 = β
(k−1)
0 − α× †
β
(k)
1 = β
(k−1)
1 − α× †
β
(k)
2 = β
(k−1)
2 − α× †
...
β(k)p = β
(k−1)
p − α× †
Make your expression as simple as possible, and be sure to include all your working. Hint: If you
haven’t done so already, take a look at Question 4 of Tutorial 3. what to submit: your coordinate
level GD updates along with any working.
(b) For the non-intercept components β1, . . . , βp, re-write the gradient descent updates of the previous
question in vector form, i.e. derive an explicit expression for the term † in the following:
β(k) = β(k−1) − α× †
Your expression should only be in terms of β0, β, xi and yi. Next, let γ = [β0, βT ]T be the (p + 1)-
dimensional vector that combines the intercept with the coefficient vector β, write down the update
γ(k) = γ(k−1) − α× †.
Note: This final expression will be our vectorized implementation of gradient descent. The point
of the above exercises is just to be careful about the differences between intercept and non-intercept
parameters. Doing GD on the coordinates is extremely innefficient in practice. what to submit: your
vectorized GD updates along with any working.
Page 4
(c) Derive the (dampened) Newton updates for the logistic regression problem with step size α. You
should do this in vector form as in the previous question. Make sure to include all your working.
For notational ease, you might find it helpful to write z(k)i = β
(k)
0 + x
T
i β
(k). Hint: When doing
this question, first solve it without the regularization term (i.e. ignore the ridge penalty term
and take λ = 1). Once you have a form for the Hessian in that case, it should be more straight-
forward to extend it to the the more general setting needed here. what to submit: your vectorized
dampened Newton updates along with any working.
(d) We will now compare the performance of GD and the Newton algorithm on a real dataset using
the derived updates in the previous parts. To do this, we will work with the songs.csv dataset.
The data contains information about various songs, and also contains a class variable outlining the
genre of the song. If you are interested, you can read more about the data here, though a deep
understanding of each of the features will not be crucial for the purposes of this assessment. Load
in the data and preform the follwing preprocessing:
(I) Remove the following features: ”Artist Name”, ”Track Name”, ”key”, ”mode”, ”time signature”,
”instrumentalness”
(II) The current dataset has 10 classes, but logistic regression in the form we have described it here
only works for binary classification. We will restrict the data to classes 5 (hiphop) and 9 (pop).
After removing the other classes, re-code the variables so that the target variable is y = 1 for
hiphop and y = 0 for pop.
(III) Remove any remaining rows that have missing values for any of the features. Your remaining
dataset should have a total of 3886 rows.
(IV) Use the sklearn.model selection.train test split function to split your data into
X train, X test, Y train and Y test. Use a test size of 0.3 and a random state of 23 for
reproducibility.
(V) Fit the sklearn.preprocessing.StandardScaler to the resulting training data, and
then use this object to scale both your train and test datasets.
(VI) Print out the first and last row of X train, X test, y train, y test (but only the first three columns
of X train, X test).
What to submit: the print out of the rows requested in (VI). A copy of your code in solutions.py
Page 5
A quick aside: Backtracking Line Search: In homework 1, we chose the step-size parameter in our
implementations naively by looking at a grid of step-sizes and choosing the best one. In practice,
this is obviously not feasible (computational cost of training the model multiple times for a large
number of candidate step-sizes). One very popular and empirically successful approach is known
as Backtracking Line Search (BLS). In BLS, the step-size is chosen adaptively at each iteration of the
algorithm by checking a given criteria. In particular, choose parameters 0 < a ≤ 0.5 and 0 < b < 1.
At iteration k of the algorithm (where we are minimizing the function f(x)), the current iterate is
x(k), set the step-size to α = 1. Then, while
f(x(k) − α∇f(x(k))) > f(x)− aα‖∇f(x(k))‖22,
shrink the step-size according to α = bα, otherwise use the current step-size α in your update. We
will not explain why this is a sensible thing to do here, but you will be able to find information
about it online if you are interested. (Of course, we can also discuss it during one of the consultation
sessions). Importantly however, the BLS idea can be applied in both gradient descent and the
dampened Newton algorithm, and you will be required to use the BLS in your implementations of
both algorithms in the following questions.
(e) Run gradient descent with backtracking line search on the training dataset for 60 epochs and λ =
0.5, and initalize β(0)0 = 0, β
(0) = 0p, where 0p is the p-dimensional vector of zeroes. For your BLS
implementation take a = 0.5, b = 0.8. Report your train and test losses, as well as plots of your
step-sizes at each iteration, and train loss at each iteration. Hint: if you need a sanity check here,
the best thing to do is use sklearn to fit logistic regression models. This should give you an idea
of what kind of loss your implementation should be achieving (if your implementation does as
well or better, then you are on the right track) what to submit: two plots, one for the step-sizes and the
other for the train losses. Report your train and test losses, and a screen shot of any code used in this section,
as well as a copy of your code in solutions.py.
(f) Run the dampened Newton algorithm with backtracking line search on the training dataset for 60
epochs and λ = 0.5. Use the same parameters for your BLS algorithm as in the previous question.
Use the same initialization for β0, β as in the previous question Report your train and test losses,
as well as plots of your step-sizes at each iteration. Further, provide a single plot showing the train
loss for both GD and Newton algorithms (use labels/legends to make your plot easy to read). what
to submit: two plots, one for the step-sizes and the other for the train losses (of both GD and Newton). Report
your train and test losses, and a screen shot of any code used in this section, as well as a copy of your code in
solutions.py.
(g) In general, it turns out that Newton’s method is much better than GD, in fact convergence of the
Newton algorithm is quadratic, whereas convergence of GD is linear (much slower than quadratic).
Given this, why do you think gradient descent and its variants (e.g. SGD) are much more popular
for solving machine learning problems? what to submit: some commentary
Question 3. More on MLE
Let X1, . . . , Xn
i.i.d.∼ N(µ, σ2). Recall that in Tutorial 2 we showed that the MLE estimators of µ, σ2 were
µˆMLE and σˆ2MLE where
µˆMLE = X, and σˆ2MLE =
1
n
n∑
i=1
(Xi −X)2.
In this question, we will explore these estimators in more depth.
Page 6
(a) Find the bias and variance of both µˆMLE and σˆ2MLE. Hint: You may use without proof the fact that
var
(
1
σ2
n∑
i=1
(Xi −X)2
)
= 2(n− 1)
what to submit: the bias and variance of the estimators, along with your working.
(b) Your friend tells you that they have a much better estimator for σ2, namely:
σ˜2 =
1
n− 1
n∑
i=1
(Xi −X)2.
Discuss whether this estimator is better or worse than the MLE estimator:
σˆ2MLE =
1
n
n∑
i=1
(Xi −X)2.
Be sure to include a detailed analysis of the bias and variance of both estimators, and describe what
occurs to each of these quantities (for each of the estimators) as the sample size n increases (use
plots). For your plots, you can assume that σ = 1.
what to submit: the bias and variance of the new estimator. A plot comparing the bias of both estimators as
a function of the sample size n, a plot comparing the variance of both estimators as a function of the sample
size n, use labels/legends in your plots. A copy of the code used here in solutions.py
(c) Compute and then plot the MSE of the two estimators considered in the previous part. For your
plots, you can assume that σ = 1. Provide some discussion as to which estimator is better (accord-
ing to their MSE), and what happens as the sample size n gets bigger. what to submit: the MSEs of
the two variance estimators. A plot comparing the MSEs of the estimators as a function of the sample size
n, and some commentary. Use labels/legends in your plots. A copy of the code used here in solutions.py
Page 7
Homework 2: Newton’s Method and Mean Squared Error of
Estimators
Introduction In homework 1, we considered Gradient Descent (and coordinate descent) for minimizing a
regularized loss function. In this homework, we consider an alternative method known as Newton’s algo-
rithm. We will first run Newton’s algorithm on a simple toy problem, and then implement it from scratch
on a real life classification problem. We will also dig deeper into the idea of estimation and comparing
estimators based on bias, variance and MSE.
Points Allocation There are a total of 28 marks.
• Question 1 a): 1 mark
• Question 1 b): 1 mark
• Question 1 c): 1 mark
• Question 2 a): 2 marks
• Question 2 b): 2 marks
• Question 2 c): 5 marks
• Question 2 d): 1 mark
• Question 2 e): 3 marks
• Question 2 f): 5 marks
• Question 2 g): 1 mark
• Question 3 a): 3 marks
• Question 3 b): 2 marks
• Question 3 c): 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.
1
• 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 ques-
tions on these site is equivalent to plagiarism and will result in a case of academic misconduct.
When and Where to Submit
• Due date: Week 7, Monday July 11th, 2022 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 ex-
ample, 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 done through Moodle, no exceptions.
Page 2
Question 1. Introduction to Newton’s Method
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to in the question. Using existing implementations can result in
a grade of zero for the entire question. In homework 1 we studied gradient descent (GD), which is
usually referred to as a first order method. Here, we study an alternative algorithm known as Newton’s
algorithm, which is generally referred to as a second order method. Roughly speaking, a second order
method makes use of both first and second derivatives. Generally, second order methods are much
more accurate than first order ones. Given a twice differentiable function g : R→ R, Newton’s method
generates a sequence {x(k)} iteratively according to the following update rule:
x(k+1) = x(k) − g
′(x(k))
g′′(x(k))
, k = 0, 1, 2, . . . , (1)
For example, consider the function g(x) = 12x
2 − sin(x) with initial guess x(0) = 0. Then
g′(x) = x− cos(x), and g′′(x) = 1 + sin(x),
and so we have the following iterations:
x(1) = x(0) − x
(0) − cos(x0)
1 + sin(x(0))
= 0− 0− cos(0)
1 + sin(0)
= 1
x(2) = x(1) − x
(1) − cos(x1)
1 + sin(x(1))
= 1− 1− cos(1)
1 + sin(1)
= 0.750363867840244
x(3) = 0.739112890911362
...
and this continues until we terminate the algorithm (as a quick exercise for your own benefit, code this
up, plot the function and each of the iterates). We note here that in practice, we often use a different
update called the dampened Newton method, defined by:
x(k+1) = x(k) − α g
′(xk)
g′′(xk)
, k = 0, 1, 2, . . . . (2)
Here, as in the case of GD, the step size α has the effect of ‘dampening’ the update.
(a) Consider the twice differentiable function f : Rn → R. The Newton steps in this case are now:
x(k+1) = x(k) − (H(x(k)))−1∇f(x(k)), k = 0, 1, 2, . . . , (3)
where H(x) = ∇2f(x) is the Hessian of f . Explain heuristically (in a couple of sentences) how the
above formula is a generalization of equation (1) to functions with vector inputs. what to submit:
Some commentary
(b) Consider the function f : R2 → R defined by
f(x, y) = 100(y − x2)2 + (1− x)2.
Create a 3D plot of the function using mplot3d (see lab0 for example). Further, compute the
gradient and Hessian of f . what to submit: A single plot, the code used to generate the plot, the gradient
and Hessian calculated along with all working. Add a copy of the code to solutions.py
Page 3
(c) Using NumPy only, implement the (undampened) Newton algorithm to find the minimizer of the
function in the previous part, using an initial guess of x(0) = (−1.2, 1)T . Terminate the algorithm
when
∥∥∇f(x(k))∥∥
2
≤ 10−6. Report the values of x(k) for k = 0, 1, . . . ,K where K is your final
iteration. what to submit: your iterations, and a screen shot of your code. Add a copy of the code to
solutions.py
Question 2. Solving Logistic Regression Numerically
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to do so in the question. Using existing implementations can
result in a grade of zero for the entire question. In this question we will compare gradient descent
and Newton’s algorithm for solving the logistic regression problem. Recall that in logistic regresion,
our goal is to minimize the log-loss, also referred to as the cross entropy loss. For an intercept β0 ∈ R,
parameter vector β = (β1, . . . , βp) ∈ Rp, target yi ∈ {0, 1}, and feature vector xi = (xi1, xi2, . . . , xip)T ∈
Rp for i = 1, . . . , n, the (`2-regularized) log-loss that we will work with is:
L(β0, β) =
1
2
‖β‖22 +
λ
n
n∑
i=1
[
yi ln
(
1
σ(β0 + βTxi)
)
+ (1− yi) ln
(
1
1− σ(β0 + βTxi)
)]
,
where σ(z) = (1 + e−z)−1 is the logistic sigmoid, and λ is a hyper-parameter that controls the amount
of regularization. Note that you are provided with an implementation of this loss in helper.py.
(a) Suppose that you were going to solve this problem using gradient descent and chose to update
each coordinate individually. Derive gradient descent updates for each of the components β0, β1, . . . , βp
for step size α and regularization parameter λ. That is, derive explicit expressions for the terms †
in the following:
β
(k)
0 = β
(k−1)
0 − α× †
β
(k)
1 = β
(k−1)
1 − α× †
β
(k)
2 = β
(k−1)
2 − α× †
...
β(k)p = β
(k−1)
p − α× †
Make your expression as simple as possible, and be sure to include all your working. Hint: If you
haven’t done so already, take a look at Question 4 of Tutorial 3. what to submit: your coordinate
level GD updates along with any working.
(b) For the non-intercept components β1, . . . , βp, re-write the gradient descent updates of the previous
question in vector form, i.e. derive an explicit expression for the term † in the following:
β(k) = β(k−1) − α× †
Your expression should only be in terms of β0, β, xi and yi. Next, let γ = [β0, βT ]T be the (p + 1)-
dimensional vector that combines the intercept with the coefficient vector β, write down the update
γ(k) = γ(k−1) − α× †.
Note: This final expression will be our vectorized implementation of gradient descent. The point
of the above exercises is just to be careful about the differences between intercept and non-intercept
parameters. Doing GD on the coordinates is extremely innefficient in practice. what to submit: your
vectorized GD updates along with any working.
Page 4
(c) Derive the (dampened) Newton updates for the logistic regression problem with step size α. You
should do this in vector form as in the previous question. Make sure to include all your working.
For notational ease, you might find it helpful to write z(k)i = β
(k)
0 + x
T
i β
(k). Hint: When doing
this question, first solve it without the regularization term (i.e. ignore the ridge penalty term
and take λ = 1). Once you have a form for the Hessian in that case, it should be more straight-
forward to extend it to the the more general setting needed here. what to submit: your vectorized
dampened Newton updates along with any working.
(d) We will now compare the performance of GD and the Newton algorithm on a real dataset using
the derived updates in the previous parts. To do this, we will work with the songs.csv dataset.
The data contains information about various songs, and also contains a class variable outlining the
genre of the song. If you are interested, you can read more about the data here, though a deep
understanding of each of the features will not be crucial for the purposes of this assessment. Load
in the data and preform the follwing preprocessing:
(I) Remove the following features: ”Artist Name”, ”Track Name”, ”key”, ”mode”, ”time signature”,
”instrumentalness”
(II) The current dataset has 10 classes, but logistic regression in the form we have described it here
only works for binary classification. We will restrict the data to classes 5 (hiphop) and 9 (pop).
After removing the other classes, re-code the variables so that the target variable is y = 1 for
hiphop and y = 0 for pop.
(III) Remove any remaining rows that have missing values for any of the features. Your remaining
dataset should have a total of 3886 rows.
(IV) Use the sklearn.model selection.train test split function to split your data into
X train, X test, Y train and Y test. Use a test size of 0.3 and a random state of 23 for
reproducibility.
(V) Fit the sklearn.preprocessing.StandardScaler to the resulting training data, and
then use this object to scale both your train and test datasets.
(VI) Print out the first and last row of X train, X test, y train, y test (but only the first three columns
of X train, X test).
What to submit: the print out of the rows requested in (VI). A copy of your code in solutions.py
Page 5
A quick aside: Backtracking Line Search: In homework 1, we chose the step-size parameter in our
implementations naively by looking at a grid of step-sizes and choosing the best one. In practice,
this is obviously not feasible (computational cost of training the model multiple times for a large
number of candidate step-sizes). One very popular and empirically successful approach is known
as Backtracking Line Search (BLS). In BLS, the step-size is chosen adaptively at each iteration of the
algorithm by checking a given criteria. In particular, choose parameters 0 < a ≤ 0.5 and 0 < b < 1.
At iteration k of the algorithm (where we are minimizing the function f(x)), the current iterate is
x(k), set the step-size to α = 1. Then, while
f(x(k) − α∇f(x(k))) > f(x)− aα‖∇f(x(k))‖22,
shrink the step-size according to α = bα, otherwise use the current step-size α in your update. We
will not explain why this is a sensible thing to do here, but you will be able to find information
about it online if you are interested. (Of course, we can also discuss it during one of the consultation
sessions). Importantly however, the BLS idea can be applied in both gradient descent and the
dampened Newton algorithm, and you will be required to use the BLS in your implementations of
both algorithms in the following questions.
(e) Run gradient descent with backtracking line search on the training dataset for 60 epochs and λ =
0.5, and initalize β(0)0 = 0, β
(0) = 0p, where 0p is the p-dimensional vector of zeroes. For your BLS
implementation take a = 0.5, b = 0.8. Report your train and test losses, as well as plots of your
step-sizes at each iteration, and train loss at each iteration. Hint: if you need a sanity check here,
the best thing to do is use sklearn to fit logistic regression models. This should give you an idea
of what kind of loss your implementation should be achieving (if your implementation does as
well or better, then you are on the right track) what to submit: two plots, one for the step-sizes and the
other for the train losses. Report your train and test losses, and a screen shot of any code used in this section,
as well as a copy of your code in solutions.py.
(f) Run the dampened Newton algorithm with backtracking line search on the training dataset for 60
epochs and λ = 0.5. Use the same parameters for your BLS algorithm as in the previous question.
Use the same initialization for β0, β as in the previous question Report your train and test losses,
as well as plots of your step-sizes at each iteration. Further, provide a single plot showing the train
loss for both GD and Newton algorithms (use labels/legends to make your plot easy to read). what
to submit: two plots, one for the step-sizes and the other for the train losses (of both GD and Newton). Report
your train and test losses, and a screen shot of any code used in this section, as well as a copy of your code in
solutions.py.
(g) In general, it turns out that Newton’s method is much better than GD, in fact convergence of the
Newton algorithm is quadratic, whereas convergence of GD is linear (much slower than quadratic).
Given this, why do you think gradient descent and its variants (e.g. SGD) are much more popular
for solving machine learning problems? what to submit: some commentary
Question 3. More on MLE
Let X1, . . . , Xn
i.i.d.∼ N(µ, σ2). Recall that in Tutorial 2 we showed that the MLE estimators of µ, σ2 were
µˆMLE and σˆ2MLE where
µˆMLE = X, and σˆ2MLE =
1
n
n∑
i=1
(Xi −X)2.
In this question, we will explore these estimators in more depth.
Page 6
(a) Find the bias and variance of both µˆMLE and σˆ2MLE. Hint: You may use without proof the fact that
var
(
1
σ2
n∑
i=1
(Xi −X)2
)
= 2(n− 1)
what to submit: the bias and variance of the estimators, along with your working.
(b) Your friend tells you that they have a much better estimator for σ2, namely:
σ˜2 =
1
n− 1
n∑
i=1
(Xi −X)2.
Discuss whether this estimator is better or worse than the MLE estimator:
σˆ2MLE =
1
n
n∑
i=1
(Xi −X)2.
Be sure to include a detailed analysis of the bias and variance of both estimators, and describe what
occurs to each of these quantities (for each of the estimators) as the sample size n increases (use
plots). For your plots, you can assume that σ = 1.
what to submit: the bias and variance of the new estimator. A plot comparing the bias of both estimators as
a function of the sample size n, a plot comparing the variance of both estimators as a function of the sample
size n, use labels/legends in your plots. A copy of the code used here in solutions.py
(c) Compute and then plot the MSE of the two estimators considered in the previous part. For your
plots, you can assume that σ = 1. Provide some discussion as to which estimator is better (accord-
ing to their MSE), and what happens as the sample size n gets bigger. what to submit: the MSEs of
the two variance estimators. A plot comparing the MSEs of the estimators as a function of the sample size
n, and some commentary. Use labels/legends in your plots. A copy of the code used here in solutions.py
Page 7
