Regularization

Definition

A regularizer $\Omega :\mathcal{F}\to {\mathbb{R}}_{\ge 0}$ measures how complex a function is. Regularized ERM minimizes $R_{reg,n}(f)=R_n(f)+\lambda \Omega (f)$ with the regularization constant $\lambda >0$.

Formula

$${\mathcal{F}}_t=\{f\in \mathcal{F}:\Omega (f)\le t\},\lambda \text{ large}\iff t\text{ small}$$

• Small $\lambda$: rich class, overfitting (small approximation, large estimation error). Large $\lambda$: underfitting.
• Side effects: unique solutions, easier optimization, stability ($\lambda \Vert w{\Vert }^2$ is $2\lambda$-strongly convex, ${\Delta }_{\sup }\le 2L^2/(\lambda n)$).
• Consistency: huge class, ${\lambda }_n\to 0$ slowly (for example ${\lambda }_n\to 0$ and ${\lambda }_n\sqrt{n}\to \infty$ with the stability bound).
• Examples: ridge ($L_2$), lasso ($L_1$), $L_0$ (NP hard). Implicit regularization by the optimizer: Implicit Regularization (Lecture 8).

Appears in

• Lecture 5, principle
• Lecture 5, nested classes and the trade-off
• Lecture 5, consistency with λ_n → 0
• Lecture 5, regularization implies stability
• Lecture 5, exam-style task on λ_n
• Lecture 8, implicit regularization by GD

Related concepts

• Ridge Regression
• Lasso
• Algorithmic Stability
• Estimation and Approximation Error