Does decreasing regularisation parameter always decrease loss

Question

For a training problem with some loss function $L(w) = \frac{1}{N}\sum_{i=1}^N l(w, x_i, y_i) + \lambda ||w||^2_2$, where $l(w, x_i, y_i)$ is something like least squares and the global minimum of $L(w)$ can always be found, how can I show that decreasing $\lambda$ always decreases $L(w)$?

Answer 1

Suppose $w'$ is the optimal $w$ with a smaller $\lambda$ (say $\lambda'$) and $w$ is the optimal with the larger $\lambda$

We know $L(w',\lambda')\leq L(w,\lambda')$ because $w'$ is optimal (by definition), and $L(w,\lambda')\leq L(w,\lambda)$ because $L$ is increasing in $\lambda$.

The first inequality is actually stronger than you asked for; it says that decreasing $\lambda$ decreases not just the penalised loss $L(w)$ but the unpenalised loss $\frac{1}{N}\sum_i l(w; x_i,y_i)$.

Another way to see this is that minimising $\frac{1}{N}\sum_i l(w; x_i,y_i)+\lambda\|w\|_2^2$ is equivalent to minimising $\frac{1}{N}\sum_i l(w; x_i,y_i)$ subject to some constraint on $\|w\|^2_2$, and that smaller $\lambda$ means a looser constraint. Minimising subject to a looser constraint means a lower minimum.

Unfortunately, this is only for the in-sample loss (or 'apparent loss'). The out-of-sample loss (which is what you usually care most about) can go up or down as $\lambda$ decreases