Linear and Logistic Regression From Scratch With L2

MediumML Coding

Reported in interviews at Uber

Problem statement

Implement linear regression and logistic regression from scratch with one training routine, then explain how the two models differ.

Both models score an example with a linear function $z_i = w \cdot x_i + b$. Linear regression predicts $\hat y_i = z_i$; logistic regression predicts $\hat p_i = \sigma(z_i) = 1/(1 + e^{-z_i})$. Training minimizes the mean loss plus an L2 penalty on the weights (never on the bias):

$$J(w, b) = \frac{1}{n}\sum_{i=1}^{n} \ell_i + \frac{\lambda}{2}\lVert w \rVert^2$$

  • linear: $\ell_i = \frac{1}{2}(z_i - y_i)^2$
  • logistic: $\ell_i = -y_i \log \sigma(z_i) - (1 - y_i)\log(1 - \sigma(z_i))$, with $y_i \in \{0, 1\}$

Start from $w = 0$, $b = 0$ and run exactly n_iters steps of full-batch gradient descent with learning rate $\eta$: compute $\nabla_w J$ and $\partial J / \partial b$ at the current parameters, then update both. Return $[w_1, \dots, w_d, b, J]$, where $J$ is the regularized loss at the final parameters.

def train_linear_model(X: list, y: list, kind: str, lr: float, n_iters: int, l2: float) -> list:
    ...

Constraints

  • $1 \le n \le 200$, $1 \le d \le 5$; kind is "linear" or "logistic"; $0 \le$ n_iters $\le 500$; $\lambda \ge 0$.
  • Use numpy or plain Python. Logits can reach the hundreds, so the sigmoid and the log-loss must be computed stably and exactly (no clipping of probabilities).
  • Outputs are compared with a relative tolerance of $10^{-6}$.

Example 1

X = [[1.0], [2.0], [3.0]], y = [2.0, 4.0, 6.0], kind = "linear", lr = 0.1, n_iters = 1, l2 = 0.0
output: [0.93333, 0.4, 1.88148]

At $w = b = 0$ every residual is $-y_i$, so $\partial J/\partial w = -(2 + 8 + 18)/3 = -28/3$ and $\partial J/\partial b = -4$; one step gives $w = 0.9333$, $b = 0.4$.

Example 2

X = [[0.5, -1.0]], y = [3.0], kind = "linear", lr = 0.1, n_iters = 0, l2 = 0.2
output: [0.0, 0.0, 0.0, 4.5]

No steps are taken, so the loss is $\frac{1}{2}(0 - 3)^2 = 4.5$ and the penalty is 0.

Example 3

X = [[0.0, 1.0], [1.0, 0.0], [1.0, 1.0], [2.0, 1.0]], y = [0, 0, 1, 1], kind = "logistic", lr = 0.5, n_iters = 100, l2 = 0.1
output: [1.14145, 0.81955, -1.70030, 0.49630]

After the code, explain: what each model predicts and why each loss fits it, how the gradients compare, what the L2 term does, and when you would use each model.

Show hint

What is the derivative of each loss with respect to the score $z_i$ before you chain through the weights?

Relevant roles: ML Engineer, Data Scientist and Applied Scientist.

Related free problems