Two Pulls on Every Weight

Regularization adds a charge for large weights to the loss. Gradient descent then feels two pulls on every weight: the data pulls it toward whatever fits the training set, and the penalty pulls it toward zero. This problem runs both pulls for several steps and tracks where the weights end up.

To make the data's pull concrete, each weight $w_i$ has a target $t_i$ , the value the training data on its own would choose for it. The data loss is a bowl centred on the targets:

$L_{\text{data}} = \tfrac{1}{2} \sum_i (w_i - t_i)^2$

The penalty is one of these, with strength $\lambda$ (strength):

`penalty`	penalty term
`"l2"`	$\lambda \sum_i w_i^{2}$
`"l1"`	$\lambda \sum_i \lvert w_i \rvert$

Each step updates every weight in two stages, both using learning rate $\eta$ (lr):

Data stage. An ordinary gradient-descent step on $L_{\text{data}}$ alone, starting from $w_i$ . Call the result $u_i$ .
Penalty stage. A gradient-descent step on the penalty term alone, starting from $u_i$ . The penalty's slope is measured at $u_i$ , not at the old $w_i$ . The result is the new $w_i$ .

The L1 penalty needs one extra rule. Its slope is $+\lambda$ wherever the weight is positive and $-\lambda$ wherever it is negative, so its stage moves $u_i$ a fixed distance toward zero. If that distance would reach or cross zero, the weight stops at exactly $0$ instead of going past it. If $u_i$ is exactly $0$ , it stays $0$ through the penalty stage.

Task: write penalised_descent(weights, targets, lr, strength, penalty, steps). Starting from weights, run steps full steps and return the final weights as a list of floats, rounded to 4 decimal places. weights and targets have the same length (at least 1), lr and strength are positive, penalty is "l1" or "l2", and steps is a whole number of at least 1.

Worked through, penalised_descent([1.0, 0.2], [0.8, 0.1], 0.5, 0.2, "l1", 2). The L1 stage moves each weight $\eta\lambda = 0.1$ toward zero:

step	weight	data stage	penalty stage
1	$w_1$	$1.0 - 0.5(1.0 - 0.8) = 0.9$	$0.9 - 0.1 = 0.8$
1	$w_2$	$0.2 - 0.5(0.2 - 0.1) = 0.15$	$0.15 - 0.1 = 0.05$
2	$w_1$	$0.8 - 0.5(0.8 - 0.8) = 0.8$	$0.8 - 0.1 = 0.7$
2	$w_2$	$0.05 - 0.5(0.05 - 0.1) = 0.075$	$0.075 \le 0.1$ , so it stops at $0$

The answer is [0.7, 0.0].

Why stop at zero? Without that rule, the L1 stage subtracts the same fixed amount every step. A weight smaller than that amount jumps across zero, gets pushed back, and jumps again. It flickers around zero forever without ever being zero. The stop rule is what makes L1 switch weights off exactly, and exact zeros are the whole reason to choose L1 over L2.

Two Pulls on Every Weight

Examples

Hints