Homework 3: Gradient Descent

Due: Tuesday, September 22 at 11:59 PM EDT

Overview

In this homework you will implement two approaches to fitting linear-regression models: the analytic solution and stochastic gradient descent (SGD). You will practice vectorized NumPy operations, investigate convergence, and interpret the resulting models.

By the end of the homework, you should be able to:

• represent a linear model with vectors and matrices;
• fit linear regression using the analytic solution;
• implement stochastic gradient descent;
• calculate predictions and regression cost;
• diagnose convergence using a cost-versus-iteration plot; and
• interpret the weights of a fitted linear model.

Credit: Adapted from materials by Sara Mathieson, Allison Gong, Jessica Wu, and Jenna Wiens.

Getting started

Download the Homework 3 starter files from Piazza. Your working folder should contain:

LinearRegression.py
run_regression.py
tests.py
README.md
HW03_written_problems.pdf
HW03_written_problems.tex
data/
  regression_test.csv
  regression_train.csv
  sea_ice_data.csv
  USA_Housing_cleaned.csv
  USA_Housing.csv

LinearRegression.py will contain the reusable regression functions. Use run_regression.py to load a requested dataset, run the models, print results, and create the required figure.

Written component

HW03 includes a written component covering design matrices and dimensions, predictions and residuals, regression cost, stochastic gradient descent by hand, and the analytic least-squares solution. The starter archive includes two versions:

• HW03_written_problems.pdf, which you may print and complete by hand; and
• HW03_written_problems.tex, which you may edit to typeset your answers using LaTeX.

Choose one of these approaches. Show your work and clearly label every final answer. You may use a calculator for arithmetic, but do not use Python or another programming language to solve the written problems.

If you complete the problems by hand, scan the finished pages into one clear, legible PDF. If you use LaTeX, compile the completed .tex file to PDF. In either case, name the file HW03_written_problems.pdf and include it with your Gradescope submission.

Install the required packages if they are not already available:

python3 -m pip install numpy matplotlib

Your program must accept a required dataset filename through argparse. For example:

python3 run_regression.py -d data/sea_ice_data.csv

Do not hard-code the input filename. Importing either Python file must not run the analysis; call main() only beneath an if __name__ == "__main__": guard.

Public tests

The starter files include tests.py, which contains a small, informative subset of the tests used by the Gradescope autograder. Run these tests from the top-level HW03 directory:

python3 tests.py

When all four public tests pass, your output should look like this. The reported runtime may differ on your computer.

test_add_ones (__main__.TestLinearRegression.test_add_ones)
The intercept column should be added without changing the input. ... ok
test_analytic_fit_predict_and_cost (__main__.TestLinearRegression.test_analytic_fit_predict_and_cost)
The analytic solution should recover a simple exact line. ... ok
test_normalize (__main__.TestLinearRegression.test_normalize)
Every normalized feature should have mean 0 and standard deviation 1. ... ok
test_sgd_converges_on_a_small_dataset (__main__.TestLinearRegression.test_sgd_converges_on_a_small_dataset)
SGD should approach known weights on a centered dataset. ... ok

----------------------------------------------------------------------
Ran 4 tests in 0.008s

OK

Passing the public tests does not guarantee full credit. Gradescope includes additional cases, so test your functions with examples of your own as well.

NumPy reminders

• Print array.shape while debugging incompatible dimensions.
• A * B performs element-wise multiplication. Use np.matmul(A, B) or A @ B for matrix multiplication.
• In this homework, vectors should be rank-one arrays with shape (n,), not matrices with shape (1, n) or (n, 1).
• np.ones(), np.zeros(), np.concatenate(), np.reshape(), np.transpose(), and np.linalg.pinv() may be useful.
• Prefer np.linalg.pinv() to an ordinary inverse so your analytic solution also works when a matrix is singular.

Except for the two loops explicitly allowed in the SGD section, use NumPy operations rather than loops.

Required interfaces

Place these functions at module scope in LinearRegression.py. Do not rename them or change their parameters or return types:

import numpy as np
from numpy.typing import NDArray

FloatArray = NDArray[np.float64]

def add_ones(X: FloatArray) -> FloatArray:
    ...

def fit(X: FloatArray, y: FloatArray) -> FloatArray:
    ...

def predict(X: FloatArray, w: FloatArray) -> FloatArray:
    ...

def cost(X: FloatArray, y: FloatArray, w: FloatArray) -> float:
    ...

def fit_SGD(
    X: FloatArray,
    y: FloatArray,
    alpha: float,
    eps: float = 1e-10,
    tmax: int = 10_000,
) -> FloatArray:
    ...

Type annotations are required. You may add helper functions, but the functions above must remain independently importable so Gradescope can test them without running the full experiment.

Use this convention consistently: X passed to fit(), predict(), cost(), and fit_SGD() contains only the original feature columns. Each function that needs an intercept column should call add_ones() internally. Do not add the intercept column more than once.

Part 1: Read the data

Use argparse in run_regression.py to define a required -d/--data_filename argument:

import argparse

def parse_arguments() -> argparse.Namespace:
    parser = argparse.ArgumentParser(
        prog="Linear Regression",
        description="Run linear-regression methods",
    )
    parser.add_argument(
        "-d",
        "--data_filename",
        type=str,
        required=True,
        help="path to a CSV data file",
    )
    return parser.parse_args()

Load the selected CSV file into a NumPy array. The first columns are features and the final column is the response. Separate them without a loop:

X = data[:, :-1]
y = data[:, -1]

The sea-ice and regression datasets appeared in HW02. The USA Housing dataset contains several features that may help predict housing prices. Use USA_Housing_cleaned.csv for computation; USA_Housing.csv is included so you can inspect the original feature names.

Part 2: Analytic linear regression

For a design matrix X with an intercept column, the prediction for example i is:

y_hat[i] = w[0] + w[1]X[i, 0] + ... + w[p]X[i, p - 1]

The analytic solution is:

w = (XᵀX)⁺Xᵀy

Here (XᵀX)⁺ is the pseudoinverse. Implement add_ones() without a loop, then implement fit() so it returns the optimal weight vector, including the intercept.

Test the analytic method with both datasets:

python3 run_regression.py -d data/sea_ice_data.csv
python3 run_regression.py -d data/regression_train.csv

Clearly print the fitted weights. In README.md, compare them with the linear models supplied in HW02 and discuss how closely they agree.

Part 3: Stochastic gradient descent

For this part, use:

python3 run_regression.py -d data/USA_Housing_cleaned.csv

Normalize the data

The housing features have large magnitudes and different scales. Normalize each feature by subtracting its column mean and dividing by its column standard deviation:

X_mean = X.mean(axis=0)
X_std = X.std(axis=0)
X_normalized = (X - X_mean) / X_std

Normalize y in the same way. Use the normalized arrays for both the analytic and SGD solutions so their weights and costs are comparable. Do not normalize the intercept column.

Predictions and cost

Implement predict() so it returns one prediction per row of X. Then implement cost() using:

J(w) = 1/2 Σ(predicted y - observed y)²

Use cost() to evaluate the analytic weights. This establishes the baseline SGD should approach. For the normalized housing data, the analytic cost should be below 205.

Fit with SGD

Implement fit_SGD(). Begin with an all-zero weight vector. During each epoch, visit every example in its existing order and update the weights using that single example:

w = w - alpha × (w · x_i - y_i) × x_i

The x_i in this expression includes the intercept value. One loop over epochs and one nested loop over examples are permitted here. Do not shuffle the examples for this homework.

After each complete epoch, calculate the cost. Stop when either:

• the absolute difference between consecutive costs is less than eps; or
• the algorithm reaches tmax epochs.

Begin your experiments with alpha=0.001, then tune alpha, eps, and tmax as needed. tmax is a safety limit, not the preferred convergence condition. Your SGD result should come within 0.1 of the analytic cost.

Your output must clearly label:

• the analytic cost and weights;
• the alpha, eps, and tmax used for SGD;
• the SGD cost and weights; and
• the number of completed SGD epochs.

Plot convergence

Record the cost after every epoch and plot cost against epoch number. Save the labeled plot as:

figures/cost_J.pdf

Create figures/ in code if it does not exist. A rising or unstable curve usually means the learning rate is too large or the update is incorrect.

Part 4: Interpret the housing model

Answer the following in README.md:

1. Report the analytic and SGD weights. How different are the two models?
2. Which feature has the largest effect in each model? Which features have little effect?
3. Do these results make sense in the context of housing prices?
4. Why does normalization matter when comparing the weights and when running SGD?

Use USA_Housing.csv to identify the original feature names.

Optional extension: polynomial regression

For a dataset with one original feature, create a design matrix in which column k contains the original x-value raised to power k. Fit the resulting matrix with the analytic linear-regression machinery and compare the recovered polynomial coefficients with the models from HW02.

Submission

Submit one .zip file to the HW03 assignment on Gradescope. The archive must preserve this structure:

LinearRegression.py
run_regression.py
README.md
HW03_written_problems.pdf
figures/
  cost_J.pdf

You do not need to upload the data/ directory. Gradescope will supply the datasets at data/ while grading.

Before submitting:

• run the program with all three required datasets;
• verify that figures/cost_J.pdf is recreated;
• complete every written problem, show your work, and include the finished HW03_written_problems.pdf;
• fully answer every required question in README.md; and
• confirm that both Python modules can be imported without running the experiment.