§15.01: Introduction

• Regularisation are methods used to add inductive bias to model usually, some “low complexity” priors (shrinkage & sparsity for eg) to reduce overfitting and get better bias-variance tradeoff. Explicit (L1/L2), Implicit (Early stopping, dropout), Structural Knowledge (group Lasso) are some broad categories (examples) of regularisation.
• Increasing the dataset size can be useful but often is not feasible in practice. Another way is reduce model complexity. For example just start with constant model and add one feature at a time in Linear Regression for example. Or we could “optimise less” i.e. early stopping.
• Regularised Empirical Risk Minimisation has contradictory goals (maximising the fit and at the same time minimising model complexity). We can add a penalty term which is a function of model complexity to the Empirical Risk Minimisation objective.

§15.02: Ridge Regression

• In linear regression if $p$ is large enough and $n$ is small enough, LR can also overfit. Moreover OLS Estimator requires a full rank design matrix, and for highly correlated features, OLS becomes sensitive to random errors resulting in a large variance.

  $${\hat{\theta }}_{Ridge}=\underset{\theta }{\mathrm{argmin}}{\mathrm{\Sigma }}_{i=1}^n(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2+\lambda {\mathrm{\Sigma }}_{j=1}^p{\theta }_j^2=||y-{\theta }^{T}x|{|}_2^2+\lambda ||\theta |{|}_2^2$$ $${\hat{\theta }}_{Ridge}=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$$

§15.03: LASSO Regression

• Another shrinkage method is the so-called LASSO (least absolute shrinkage and selection operator) which uses the L1 penalty on $\theta$:

  $$\begin{array}{rl}{\hat{\theta }}_{\text{lasso}}& =\underset{\theta }{\mathrm{argmin}}\sum _{i=1}^n(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2+\lambda \sum _{j=1}^p|{\theta }_j|\\ & =\underset{\theta }{\mathrm{argmin}}\Vert y-X\theta {\Vert }_2^2+\lambda \Vert \theta {\Vert }_1\end{array}$$
• Optimisation becomes much harder because the function is no longer differentiable.
• For $p>n$, LASSO selects atmost $n$ features.

§15.04: LASSO vs Ridge Regression

• Usually the intercept is not regularised so that the “infinitely” regularised model is the constant model.
• Unregularised Linear Regression has rescaling equivariance. If you rescale certain variables then the coefficients change and the risk does not change. For example if a variable was encoded in cm, but we convert it to mm, then the coefficient would be a simple multiple by a 100 for the mm variable. However for the regularised version, the risk for rescaled variables are often different and hence don’t have rescaling equivariance $\Rightarrow$ standardize features in regularised linear regression!

• Suppose two variables are highly correlated. Then Ridge regression has tends to have “grouping effect” i.e. similar effect on both variables where LASSO arbitrarily decides to select one of them. If $x_i=x_j$, then ${\theta }_{i,Ridge}={\theta }_{j,Ridge}$ because the $L2$ penalty is strictly convex. Since $L1$ is not strictly convex, sum of coefficents can be arbitrarily allocated across both features i.e.

  $${\hat{\theta }}_i=s.({\hat{\theta }}_i+{\theta }_j)\text{ and }{\hat{\theta }}_j=(1-s)({\hat{\theta }}_i+{\theta }_j)\text{ for }s\in [0,1]$$

§15.05: Elastic Net and Regularization for GLMs

• It is a “compromise” between L1 and L2 penalties:

  $$\begin{array}{rl}{\hat{\theta }}_{\text{elnet}}& =\underset{\theta }{\mathrm{argmin}}\sum _{i=1}^n(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2+{\lambda }_1\Vert \theta {\Vert }_2^2+{\lambda }_2\Vert \theta {\Vert }_1\\ & =\underset{\theta }{\mathrm{argmin}}\Vert y-X\theta {\Vert }_2^2+\lambda \alpha \Vert \theta {\Vert }_2^2+\lambda (1-\alpha )\Vert \theta {\Vert }_1\end{array}$$
• Correlated features tend to be selected or zeroed out together and selection more than $n$ features possible if $p>n$.
• Unlike pure Ridge, Elasticnet does perform some feature selection and unlike Lasso which sometimes ignores relevant features, Elasticnet keeps them in.

§15.06: Other Types of Regularisation

• Although Ridge and Lasso have many desirable properties, they are biased estimators.
• Besides $L1/L2$, we can also consider $L_q$ Norm: $\mid \mid \theta \mid {\mid }_q^q$. For $q<1$, penalty becomes non-convex, and for $q>1$ sparsity is not achieved. Non-convex $L_q$ has the so-called Oracle Property - consitent and asymptotically unbiased estimator and feature selection. However the non-convexity makes the problem quite a bit harder.
• The $L0$ norm simply counts the number of non-zero parameters. Induces sparsity more aggressively than $L1$ but does not shrink parameters. AIC and BIC are special cases of $L0$ Norm and the problem is NP-hard.

§15.07: Non-Linear Models and Structural Risk Minimisation

• We can summarise regularised risk minimisation using this equation:

  $$\underset{\theta }{min}{R}_{reg}(\theta )=\underset{\theta }{min}({\mathrm{\Sigma }}_{i=1}^{n}L(y^{(i)},f(x^{(i)}|\theta ))+\lambda J(\theta )$$
  • hypothesis space of f controls how features influence predictions
  • loss function L measures how errors are treated
  • regulariser $J(\theta )$ encodes inductive bias
• Structural Risk Minimisation (SRM) assumes that our hypothesis space can be decomposed into a sequence of increasingly complex hypothesis for eg degree of polynomials or size of hidden layer : $H=\bigcup H_k$.
• SRM chooses the smallest $k$ such that the optimal model from $H_k$ is not significantly outperformed by a model from $H_m$ with $m>k$. In simple terms, if a model from the higher complexity hypothesis space does not significantly outperform the current complexity level, then choose the optimal model from the current level.
• We can also interpret Regularised Risk Minimisation from the lens of SRM by considering each level of $\lambda$ as a complexity level.

§15.08: Bayesian Priors

• We have previously created an equivalence between MLE and ERM. We can do the same for MAP and RRM. Assume we have a parametrised distribution $p(y\mid \theta ,x)$ for our data and a prior distribution $q(\theta )$ over our parameter space, then, as per Bayes rule:

  $$p(\theta |x,y)=\frac{p(y|\theta ,x)q(\theta )}{p(y|x)}\propto p(y|\theta ,x)q(\theta )$$

• The Maximum Priori Estimator is then given by:

  $$\begin{array}{rl}{\hat{\theta }}_{\text{MAP}}& =\underset{\theta }{\mathrm{argmax}}p(y\mid \theta ,x)q(\theta )\\ & =\underset{\theta }{\mathrm{argmax}}\log p(y\mid \theta ,x)+\log q(\theta )\\ & =\underset{\theta }{\mathrm{argmin}}-\log p(y\mid \theta ,x)-\log q(\theta )\end{array}$$
• In this formulation we can identify the $\log p(y\mid \theta ,x)$ as our Loss function and and the $\log q(\theta )\propto J(\theta )$ : our regulariser.
• $L2$ regularisation is equivalent to an MAP estimator with ${\theta }_j\sim N(0,{\sigma }^2)$ prior and $L1$ regularisation is equivalent to ${\theta }_j\sim Laplace(0,b)$ prior. For the $L2$ regularisation we can show that larger the variance of our prior, lower the regularisation i.e. the shrinkange is inversely proportional to the variance of our prior.

§15.09: Weight Decay and L2

• Consider $L2$ regularisation:

  $$\underset{\theta }{min}{R}_{reg}(\theta )=\underset{\theta }{min}L(y,f(x|\theta ))+\frac{\lambda }{2}||\theta |{|}_2^2=\underset{\theta }{min}{R}_{emp}(\theta )+\frac{\lambda }{2}||\theta |{|}_2^2$$

  If we now update $\theta$ using gradient descent, then the gradient is:

  $${\mathrm{\nabla }}_{\theta }{R}_{reg}(\theta )={\mathrm{\nabla }}_{\theta }{R}_{emp}(\theta )+\lambda \theta$$

  Thus we get the following update:

  $$\begin{gathered} {\theta }^{new}={\theta }^{old}-\alpha ({\mathrm{\nabla }}_{\theta }{R}_{emp}({\theta }^{old})+\lambda {\theta }^{old}) \\ {\theta }^{old}(1-\alpha \lambda )-\alpha {\mathrm{\nabla }}_{\theta }{R}_{emp}({\theta }^{old}) \end{gathered}$$

• Usually both $\alpha \lambda «1$. Therefore essentially what is happening is the old parameter is decayed in magnitude before performing an update. Thus this well known technique of weight decay is simply $L2$ regularisation in disguise. Note that this equivalence only holds for (stochastic) gradient descent and not for Adam, etc.

§15.10: Geometry of L2 Regularisation

§15.11: Geometry of L1 Regularisation

§15.12: Early Stopping

• Early stopping is effective and simple to implement. It involves simply stopping optimisation when the validation error stops decreasing.
• For a simple linear regression with squared loss and gradient descent optimisation with initial parameters set to 0 has exact correspondence with $L2$ regularisation. The optimal early stopping iteration $T_{stop}\approx \frac{1}{\alpha \lambda }\Rightarrow$ small $\lambda$ (low regularisation) implies a larger $T_{stop}$ (more complexity of the model).