Regularization Theory
Ridge, lasso, priors and implicit regularization.
Every learner that works is regularized, whether or not anyone wrote down a penalty. This lesson computes exactly what ridge buys, shows why the ball produces sparse solutions and when the lasso finds the right variables, then uncovers the hidden penalties in early stopping, noise, dropout and gradient descent itself.
What you’ll learn
- Derive the exact bias and variance of ridge in the eigenbasis, and prove the Hoerl–Kennard theorem that some always beats least squares.
- Derive the lasso's optimality conditions, explain geometrically why gives sparsity, and prove the estimation bound under a restricted eigenvalue condition.
- Show that early stopping is a spectral filter close to ridge, and that input noise and dropout are data-dependent Tikhonov penalties.
- Prove that gradient descent on underdetermined least squares converges to the minimum-norm interpolant, and state the max-margin bias of gradient descent on separable logistic regression.
Ridge, exactly
Work in the fixed-design linear model with , , and of full column rank with , eigenvalues . Write for the true coefficients in the eigenbasis, and for ridge.
The mean shrinks the truth, so ridge is biased. In the eigenbasis, coordinate is multiplied by :
The covariance is , diagonal in the same basis:
Adding squared bias and variance over coordinates gives the exact mean squared error:
At this is , which explodes when the inputs are nearly collinear (some ). Ridge caps every term, however small is: since , each is at most .
Differentiate one term of (drop the index ); the pieces cancel in the numerator:
This is negative whenever . Below every term is strictly decreasing, so the sum is too, and .
Term is minimized at , where it equals . If the are drawn from a prior , the average-optimal choice is : the Bayesian posterior mean of Gaussian Processes & Bayesian ML.
Orthonormal design (), coefficients, noise and for every (signal-to-noise ratio 1 per coordinate). The best ridge estimator achieves what percentage of least squares' mean squared error?
Show the answer
50 %
Least squares: . The optimum is , where each term is , so : half the error, bought with bias. In general the ratio per coordinate is , so shrinkage helps most where the signal-to-noise ratio is low.
The lasso: optimality, sparsity and guarantees
The lasso solves , a convex problem with a non-smooth objective. Its solutions are characterized by subgradients: for and at .
Why the ball gives sparsity. In constrained form, the solution is where the smallest level set of touches the polytope , and optimality means lies in the polytope's normal cone at the contact point. At a vertex, a sparse point , the normal cone is a full-dimensional solid cone, so an open set of responses , an event of positive probability under continuous noise, puts the solution exactly there; lower-dimensional faces, also sparse, behave the same way. On the ball the normal cone at each boundary point is a single ray, so the solution lands on a coordinate axis with probability zero.
The norm is also the best convex stand-in for counting nonzeros: on the cube it is the convex envelope of . Penalties with are sparser still, but non-convex.
Compare the objective at and at (the "basic inequality"), with , and expand :
Bound the noise term by Hölder's inequality and the choice of , and the penalty difference by the triangle inequality on (where lives) and exact additivity on :
The left side is nonnegative, so and the restricted eigenvalue condition applies. With :
For Gaussian noise and columns scaled to , a union bound over the columns shows is large enough with probability at least . Hence the rate below, within a logarithm of the minimax rate for -sparse vectors: the price of not knowing is only a .
Estimation is not selection. Recovering the support exactly also needs an irrepresentable condition, , which says irrelevant columns are not too well explained by relevant ones, plus a minimum signal size; both are essentially necessary (Zhao & Yu, 2006; Wainwright, 2009). Correlated designs violate it, which motivates the elastic net (Zou & Hastie, 2005) and stability selection. The same mathematics underlies compressed sensing (Candès, Romberg & Tao, 2006; Donoho, 2006).
Hidden penalties: early stopping, noise and dropout
Run gradient descent on from with step . With and , the coordinates decouple:
Solve the scalar recursion from and compare with ridge:
Both filters pass strong directions and suppress weak ones, with the crossover near for early stopping and for ridge; for small , . So:
Ali, Kolter & Tibshirani (2019) made this precise for gradient flow: with , its estimation risk is at most 1.69 times that of ridge, along the entire path. The number of steps is a regularization parameter, chosen on a validation curve like any other.
Input noise. Corrupting inputs with noise during training is ridge in disguise. For least squares with a noise matrix of i.i.d. entries, : exactly ridge with . For nonlinear models with squared loss, the equivalence holds to leading order, with a Tikhonov penalty on the input gradients, (Bishop, 1995).
Keep each input with probability and rescale by ("inverted" dropout), with independent masks :
Average the squared error over the masks: the mean prediction is the undropped one, and the variances of the independent terms add up:
This is ridge with a per-feature weight, equivalently ridge on standardized features. For generalized linear models, dropout is to second order an penalty scaled by the diagonal of the Fisher information (Wager, Wang & Liang, 2013); in deep networks it also acts like averaging exponentially many thinned subnetworks (Srivastava et al., 2014).
Other regularizers work the same way, by changing what the optimizer can cheaply reach: data augmentation enforces invariances, label smoothing penalizes overconfident logits, and the noise of SGD is believed to steer training toward flat regions of the loss (Keskar et al., 2017), although flatness can be changed by reparameterizing a network without changing its function (Dinh et al., 2017). Under adaptive optimizers, an term in the loss and decoupled weight decay are no longer the same thing (Loshchilov & Hutter, 2019).
The implicit bias of gradient descent
Every gradient, , lies in the row space . Starting from , so does every iterate, and so does the limit, because the subspace is closed:
The loss is a convex quadratic, so with step below the iterates converge to a minimizer; since has rank , the minimum is and the limit interpolates. Every interpolant has the form with , and Pythagoras gives
The only interpolant inside has : the limit is , the minimum-norm one. For ridge, the push-through identity gives the same limit:
The geometry of the algorithm picks the solution. Started at , gradient descent on least squares converges to the interpolant nearest ; mirror descent converges to the interpolant nearest the start in its Bregman divergence (Gunasekar, Lee, Soudry & Srebro, 2018); steepest descent in another norm finds the maximum margin in that norm. For homogeneous neural networks on separable data, gradient flow converges in direction to a KKT point of a margin-maximization problem (Lyu & Li, 2020; Ji & Telgarsky, 2020).
You run gradient descent on an underdetermined least-squares problem (, rank ) from a nonzero start , with a small step. Where does it converge?
- To the minimum-norm interpolant , whatever the start
- To the interpolant closest to , namely
- It does not converge, because there are infinitely many minimizers
- To itself, since the gradient vanishes there
Show the answer
B. To the interpolant closest to , namely
The iterates stay in , and the only interpolant in that affine subspace is , the projection of onto the solution set. Initialization is part of the implicit regularizer, which is one reason small initializations matter in deep learning.
Key takeaways
- Ridge's risk is exactly ; its derivative at is negative, so some always beats least squares (Hoerl–Kennard), and is Bayes-optimal under a prior.
- The lasso's KKT conditions pin every active variable's residual correlation at . Vertices of the ball have full-dimensional normal cones, so sparse solutions occur with positive probability.
- Under a restricted eigenvalue condition with , the lasso's error is ; exact support recovery needs irrepresentability and a minimum signal size.
- Early stopping filters like ridge with ; input noise is ridge with ; dropout is ridge weighted by .
- Gradient descent from zero converges to the minimum-norm interpolant on underdetermined least squares, and to the max-margin direction on separable logistic regression: the algorithm and its initialization are part of the model.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the fixed-design linear model, how does the mean squared error of ridge behave as increases from ?
- It increases immediately, because ridge is biased
- It stays constant until exceeds the smallest eigenvalue of
- It decreases at first, so some beats least squares
- It decreases monotonically for all
Show the answer
C. It decreases at first, so some beats least squares
Each term's derivative is , negative for . The variance falls at first order while the squared bias grows only at second order in , so a little shrinkage always helps; too much makes the bias dominate.
For the lasso , when is the solution exactly ?
- Exactly when
- Only in the limit
- When exceeds the largest eigenvalue of
- Never, if
Show the answer
A. Exactly when
At the residual is , and the KKT conditions require for every . So the whole path starts at , where the first variable enters.
Inverted dropout with keep probability on the inputs of a linear regression is, in expectation over the masks, equivalent to which penalty?
- An penalty
- No penalty: inverted scaling makes dropout unbiased
- An early-stopping rule with steps
- A ridge penalty
Show the answer
D. A ridge penalty
The mask is unbiased, so the mean prediction is unchanged, but it adds variance to each prediction, and squared error charges for that variance. The result is ridge weighted by each feature's squared norm.
Gradient descent on the logistic loss for linearly separable data has reached zero training error. What happens if you keep training?
- Nothing: the gradient is exactly zero once the data are separated
- The weights grow without bound while their direction slowly converges to the hard-margin SVM direction
- The weights converge to a finite minimizer of the logistic loss
- The direction drifts randomly, since every separator has zero training error
Show the answer
B. The weights grow without bound while their direction slowly converges to the hard-margin SVM direction
The logistic loss has no finite minimizer on separable data; its gradient only decays. Soudry et al. (2018) showed , so the direction converges to the max-margin separator at rate , and test behavior can keep changing after the training error is zero.
Further reading
- A. E. Hoerl & R. W. Kennard, "Ridge regression: biased estimation for nonorthogonal problems," Technometrics 12(1), 55–67 (1970).
- P. J. Bickel, Y. Ritov & A. B. Tsybakov, "Simultaneous analysis of Lasso and Dantzig selector," Annals of Statistics 37(4), 1705–1732 (2009).
- N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever & R. Salakhutdinov, "Dropout: a simple way to prevent neural networks from overfitting," Journal of Machine Learning Research 15, 1929–1958 (2014).
- D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar & N. Srebro, "The implicit bias of gradient descent on separable data," Journal of Machine Learning Research 19, 1–57 (2018).
- T. Hastie, R. Tibshirani & M. Wainwright, Statistical Learning with Sparsity: The Lasso and Generalizations (CRC Press, 2015).