Implicit Regularization

Definition

Among the many minimizers of an over-parameterized objective, the optimizer (GD, SGD) converges to one with extra properties, without an explicit penalty term.

Formula

Least squares, $n<d$, full row rank, GD from $w_0=0$ with $0<\eta <2/{\lambda }_{\max }(X{X}^{\top })$:

$$w_t\to w^{\star }=X^{\top }(X{X}^{\top }{)}^{-1}y=\arg \min \{\Vert w\Vert :Xw=y\}.$$

Logistic loss, separable data: $\Vert w_t\Vert \to \infty$ and $w_t/\Vert w_t\Vert \to w_{mm}/\Vert w_{mm}\Vert$ (max margin).

The iterates stay in the span of the data, so the component in $\ker X$ is never touched: from $w_0\ne 0$ GD converges to the solution closest to $w_0$. For deep non-linear networks the implicit bias is not well understood.

Appears in

• Lecture 2, SGD picks a special minimizer
• Lecture 8, Theorem 1 (GD finds the minimum norm solution), Theorem 2 (max-margin bias of GD), neural networks

Related concepts

• Regularization
• Least Squares Regression
• Margin
• Benign Overfitting