How does regularization reduce overfitting? [duplicate]

A common way to reduce overfitting in a machine learning algorithm is to use a regularization term that penalizes large weights (L2) or non-sparse weights (L1) etc. How can such regularization reduce overfitting, especially in a classification algorithm? Can one show this mathematically?

This is related to the Bias-Variance tradeoff. The expected error can be decomposed as $$\mathrm{E}[(y - f(x))^2] = \mathrm{Bias}(f(x))^2 + \mathrm{Var}(f(x)) + \sigma^2,$$ where the bias is the systematic deviation of our estimator, $f$, from the true value, i.e. $E[f^* - f]$, where $f^*$ is the true estimator, and the variance is essentially how sensitive our estimator is to deviations in the training set. The $\sigma^2$ term is the residual noise term; this term is irreducible and can not be made to impact less with mathematics (if your samples are noise, there might be something you can do in regards to collecting the data, though).
Whether or not you obtain a successful reduction in expected variance depends on your estimator and the regularisation used. For instance, for multiple linear regression and $\ell_2$ regularisation, it is possible to prove that there is a solution that reduces the expected error by properly selecting the regularisation parameter.