Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 ℓ1\ell_1 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 λ>0\lambda>0 always beats least squares.
  • Derive the lasso's optimality conditions, explain geometrically why ℓ1\ell_1 gives sparsity, and prove the slog⁡p/n\sqrt{s\log p/n} 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 y=Xw⋆+ε\mathbf y=X\mathbf w^\star+\boldsymbol\varepsilon with Eε=0\E\boldsymbol\varepsilon=\mathbf 0, Cov⁡ε=σ2I\Cov\boldsymbol\varepsilon=\sigma^2I, and X∈Rn×pX\in\R^{n\times p} of full column rank with X⊤X=VD2V⊤X^\top X=VD^2V^\top, eigenvalues d12≥⋯≥dp2>0d_1^2\ge\dots\ge d_p^2>0. Write α=V⊤w⋆\boldsymbol\alpha=V^\top\mathbf w^\star for the true coefficients in the eigenbasis, and w^λ=(X⊤X+λI)−1X⊤y\hat{\mathbf w}_\lambda=(X^\top X+\lambda I)^{-1}X^\top\mathbf y for ridge.

DerivationThe risk of ridge, coordinate by coordinate
  1. E[V⊤w^λ]j=dj2dj2+λ αj,biasj=−λ αjdj2+λ\E\big[V^\top\hat{\mathbf w}_\lambda\big]_j=\frac{d_j^2}{d_j^2+\lambda}\,\alpha_j,\qquad\text{bias}_j=-\frac{\lambda\,\alpha_j}{d_j^2+\lambda}

    The mean shrinks the truth, so ridge is biased. In the eigenbasis, coordinate jj is multiplied by dj2/(dj2+λ)d_j^2/(d_j^2+\lambda):

  2. Var⁡[V⊤w^λ]j=σ2dj2(dj2+λ)2\Var\big[V^\top\hat{\mathbf w}_\lambda\big]_j=\frac{\sigma^2d_j^2}{(d_j^2+\lambda)^2}

    The covariance is σ2(X⊤X+λI)−1X⊤X(X⊤X+λI)−1\sigma^2(X^\top X+\lambda I)^{-1}X^\top X(X^\top X+\lambda I)^{-1}, diagonal in the same basis:

  3. MSE(λ)=E∥w^λ−w⋆∥2=∑j=1pσ2dj2+λ2αj2(dj2+λ)2\mathrm{MSE}(\lambda)=\E\norm{\hat{\mathbf w}_\lambda-\mathbf w^\star}^2=\sum_{j=1}^p\frac{\sigma^2d_j^2+\lambda^2\alpha_j^2}{(d_j^2+\lambda)^2}

    Adding squared bias and variance over coordinates gives the exact mean squared error:

  4. MSE(0)=σ2tr⁡[(X⊤X)−1]=σ2∑j=1p1dj2\mathrm{MSE}(0)=\sigma^2\operatorname{tr}\big[(X^\top X)^{-1}\big]=\sigma^2\sum_{j=1}^p\frac1{d_j^2}

    At λ=0\lambda=0 this is σ2∑j1/dj2\sigma^2\sum_j1/d_j^2, which explodes when the inputs are nearly collinear (some dj≈0d_j\approx0). Ridge caps every term, however small djd_j is: since (dj2+λ)2≥4λdj2(d_j^2+\lambda)^2\ge4\lambda d_j^2, each is at most σ2/(4λ)+αj2\sigma^2/(4\lambda)+\alpha_j^2.

DerivationProof
  1. ddλ σ2d2+λ2α2(d2+λ)2=2λα2(d2+λ)−2(σ2d2+λ2α2)(d2+λ)3=2d2(λα2−σ2)(d2+λ)3\frac{d}{d\lambda}\,\frac{\sigma^2d^2+\lambda^2\alpha^2}{(d^2+\lambda)^2}=\frac{2\lambda\alpha^2(d^2+\lambda)-2(\sigma^2d^2+\lambda^2\alpha^2)}{(d^2+\lambda)^3}=\frac{2d^2\big(\lambda\alpha^2-\sigma^2\big)}{(d^2+\lambda)^3}

    Differentiate one term of MSE(λ)\mathrm{MSE}(\lambda) (drop the index jj); the λ2α2\lambda^2\alpha^2 pieces cancel in the numerator:

  2. 0<λ<σ2max⁡jαj2⟹d MSEdλ<0 on (0,λ]0<\lambda<\frac{\sigma^2}{\max_j\alpha_j^2}\quad\Longrightarrow\quad\frac{d\,\mathrm{MSE}}{d\lambda}<0\ \text{on }(0,\lambda]

    This is negative whenever λ<σ2/α2\lambda<\sigma^2/\alpha^2. Below σ2/max⁡jαj2\sigma^2/\max_j\alpha_j^2 every term is strictly decreasing, so the sum is too, and MSE(λ)<MSE(0)\mathrm{MSE}(\lambda)<\mathrm{MSE}(0).

  3. min⁡λσ2dj2+λ2αj2(dj2+λ)2=σ2dj2+σ2/αj2\min_\lambda\frac{\sigma^2d_j^2+\lambda^2\alpha_j^2}{(d_j^2+\lambda)^2}=\frac{\sigma^2}{d_j^2+\sigma^2/\alpha_j^2}

    Term jj is minimized at λj=σ2/αj2\lambda_j=\sigma^2/\alpha_j^2, where it equals σ2/(dj2+λj)\sigma^2/(d_j^2+\lambda_j). If the αj\alpha_j are drawn from a prior N(0,τ2)\mathcal N(0,\tau^2), the average-optimal choice is λ=σ2/τ2\lambda=\sigma^2/\tau^2: the Bayesian posterior mean of Gaussian Processes & Bayesian ML.

Predict before you look

Orthonormal design (dj=1d_j=1), p=10p=10 coefficients, noise σ2=1\sigma^2=1 and αj2=1\alpha_j^2=1 for every jj (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: MSE(0)=∑jσ2/dj2=10\mathrm{MSE}(0)=\sum_j\sigma^2/d_j^2=10. The optimum is λ=σ2/α2=1\lambda=\sigma^2/\alpha^2=1, where each term is σ2/(d2+λ)=12\sigma^2/(d^2+\lambda)=\tfrac12, so MSE=5\mathrm{MSE}=5: half the error, bought with bias. In general the ratio per coordinate is 1/(1+σ2/(αj2dj2))1/(1+\sigma^2/(\alpha_j^2d_j^2)), so shrinkage helps most where the signal-to-noise ratio is low.

The lasso: optimality, sparsity and guarantees

The lasso solves min⁡w 12n∥y−Xw∥2+λ∥w∥1\min_{\mathbf w}\ \frac1{2n}\norm{\mathbf y-X\mathbf w}^2+\lambda\norm{\mathbf w}_1, a convex problem with a non-smooth objective. Its solutions are characterized by subgradients: ∂∣w∣={sign⁡w}\partial\abs{w}=\{\sign w\} for w≠0w\ne0 and [−1,1][-1,1] at w=0w=0.

Why the ℓ1\ell_1 ball gives sparsity. In constrained form, the solution is where the smallest level set of ∥y−Xw∥2\norm{\mathbf y-X\mathbf w}^2 touches the polytope {∥w∥1≤t}\{\norm{\mathbf w}_1\le t\}, and optimality means −∇(loss)-\nabla(\text{loss}) lies in the polytope's normal cone at the contact point. At a vertex, a sparse point ±t ej\pm t\,\mathbf e_j, the normal cone is a full-dimensional solid cone, so an open set of responses y\mathbf y, an event of positive probability under continuous noise, puts the solution exactly there; lower-dimensional faces, also sparse, behave the same way. On the ℓ2\ell_2 ball the normal cone at each boundary point is a single ray, so the solution lands on a coordinate axis with probability zero.

The ℓ1\ell_1 norm is also the best convex stand-in for counting nonzeros: on the cube {∥w∥∞≤1}\{\norm{\mathbf w}_\infty\le1\} it is the convex envelope of #{j:wj≠0}\#\{j:w_j\ne0\}. Penalties ∥w∥qq\norm{\mathbf w}_q^q with q<1q<1 are sparser still, but non-convex.

DerivationProof
  1. 12n∥Xv∥2≤1nε⊤Xv+λ(∥w⋆∥1−∥w⋆+v∥1)\frac1{2n}\norm{X\mathbf v}^2\le\frac1n\boldsymbol\varepsilon^\top X\mathbf v+\lambda\big(\norm{\mathbf w^\star}_1-\norm{\mathbf w^\star+\mathbf v}_1\big)

    Compare the objective at w^\hat{\mathbf w} and at w⋆\mathbf w^\star (the "basic inequality"), with v=w^−w⋆\mathbf v=\hat{\mathbf w}-\mathbf w^\star, and expand y−Xw^=ε−Xv\mathbf y-X\hat{\mathbf w}=\boldsymbol\varepsilon-X\mathbf v:

  2. 12n∥Xv∥2≤λ2(∥vS∥1+∥vSc∥1)+λ(∥vS∥1−∥vSc∥1)=λ2(3∥vS∥1−∥vSc∥1)\frac1{2n}\norm{X\mathbf v}^2\le\frac\lambda2\big(\norm{\mathbf v_S}_1+\norm{\mathbf v_{S^c}}_1\big)+\lambda\big(\norm{\mathbf v_S}_1-\norm{\mathbf v_{S^c}}_1\big)=\frac\lambda2\big(3\norm{\mathbf v_S}_1-\norm{\mathbf v_{S^c}}_1\big)

    Bound the noise term by Hölder's inequality and the choice of λ\lambda, and the penalty difference by the triangle inequality on SS (where w⋆\mathbf w^\star lives) and exact additivity on ScS^c:

  3. κ2∥v∥22≤12n∥Xv∥2≤3λ2∥vS∥1≤3λ2s ∥v∥2⟹∥v∥2≤3s λκ\frac\kappa2\norm{\mathbf v}_2^2\le\frac1{2n}\norm{X\mathbf v}^2\le\frac{3\lambda}2\norm{\mathbf v_S}_1\le\frac{3\lambda}2\sqrt s\,\norm{\mathbf v}_2\quad\Longrightarrow\quad\norm{\mathbf v}_2\le\frac{3\sqrt s\,\lambda}\kappa

    The left side is nonnegative, so v∈C\mathbf v\in\mathcal C and the restricted eigenvalue condition applies. With ∥vS∥1≤s∥v∥2\norm{\mathbf v_S}_1\le\sqrt s\norm{\mathbf v}_2:

  4. ∥w^−w⋆∥22≤72κ2 s σ2ln⁡(2p/δ)n\norm{\hat{\mathbf w}-\mathbf w^\star}_2^2\le\frac{72}{\kappa^2}\,\frac{s\,\sigma^2\ln(2p/\delta)}n

    For Gaussian noise and columns scaled to ∥xj∥2=n\norm{\mathbf x_j}^2=n, a union bound over the pp columns shows λ=2σ2ln⁡(2p/δ)/n\lambda=2\sigma\sqrt{2\ln(2p/\delta)/n} is large enough with probability at least 1−δ1-\delta. Hence the rate below, within a logarithm of the minimax rate sσ2log⁡(p/s)/ns\sigma^2\log(p/s)/n for ss-sparse vectors: the price of not knowing SS is only a log⁡p\log p.

Estimation is not selection. Recovering the support SS exactly also needs an irrepresentable condition, ∥XSc⊤XS(XS⊤XS)−1∥∞<1\norm{X_{S^c}^\top X_S(X_S^\top X_S)^{-1}}_\infty<1, 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

DerivationEarly stopping is a spectral filter
  1. wt+1=wt+ηX⊤(y−Xwt)⟹cj(t+1)=(1−ηdj2) cj(t)+ηdj uj⊤y\mathbf w_{t+1}=\mathbf w_t+\eta X^\top(\mathbf y-X\mathbf w_t)\quad\Longrightarrow\quad c_j(t+1)=(1-\eta d_j^2)\,c_j(t)+\eta d_j\,\mathbf u_j^\top\mathbf y

    Run gradient descent on 12∥y−Xw∥2\tfrac12\norm{\mathbf y-X\mathbf w}^2 from w0=0\mathbf w_0=\mathbf 0 with step η≤1/d12\eta\le1/d_1^2. With X=UDV⊤X=UDV^\top and cj=vj⊤wc_j=\mathbf v_j^\top\mathbf w, the coordinates decouple:

  2. cj(t)=[1−(1−ηdj2)t]uj⊤ydjversuscj(λ)=dj2dj2+λ uj⊤ydjc_j(t)=\Big[1-(1-\eta d_j^2)^t\Big]\frac{\mathbf u_j^\top\mathbf y}{d_j}\qquad\text{versus}\qquad c_j(\lambda)=\frac{d_j^2}{d_j^2+\lambda}\,\frac{\mathbf u_j^\top\mathbf y}{d_j}

    Solve the scalar recursion from cj(0)=0c_j(0)=0 and compare with ridge:

  3. stopping after t steps ≈ ridge with λ≈1ηt\text{stopping after }t\text{ steps}\ \approx\ \text{ridge with }\lambda\approx\frac1{\eta t}

    Both filters pass strong directions and suppress weak ones, with the crossover near dj2≈1/(ηt)d_j^2\approx1/(\eta t) for early stopping and dj2≈λd_j^2\approx\lambda for ridge; for small ηdj2\eta d_j^2, 1−(1−ηdj2)t≈1−e−ηtdj21-(1-\eta d_j^2)^t\approx1-e^{-\eta td_j^2}. So:

  4. 1−e−td2⏟gradient flowvsd2d2+1/t⏟ridge, λ=1/t\underbrace{1-e^{-td^2}}_{\text{gradient flow}}\quad\text{vs}\quad\underbrace{\frac{d^2}{d^2+1/t}}_{\text{ridge},\ \lambda=1/t}

    Ali, Kolter & Tibshirani (2019) made this precise for gradient flow: with λ=1/t\lambda=1/t, 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 EE of i.i.d. N(0,s2)\mathcal N(0,s^2) entries, E∥y−(X+E)w∥2=∥y−Xw∥2+ns2∥w∥2\E\norm{\mathbf y-(X+E)\mathbf w}^2=\norm{\mathbf y-X\mathbf w}^2+ns^2\norm{\mathbf w}^2: exactly ridge with λ=ns2\lambda=ns^2. For nonlinear models with squared loss, the equivalence holds to leading order, with a Tikhonov penalty on the input gradients, s2 E∥∇xf(x)∥2s^2\,\E\norm{\nabla_{\mathbf x}f(\mathbf x)}^2 (Bishop, 1995).

DerivationDropout on a linear model
  1. y^i=∑jxijwj δijq,E[δijq]=1,Var⁡[δijq]=1−qq\hat y_i=\sum_{j}x_{ij}w_j\,\frac{\delta_{ij}}q,\qquad\E\Big[\frac{\delta_{ij}}q\Big]=1,\qquad\Var\Big[\frac{\delta_{ij}}q\Big]=\frac{1-q}q

    Keep each input with probability qq and rescale by 1/q1/q ("inverted" dropout), with independent masks δij∼Bernoulli(q)\delta_{ij}\sim\mathrm{Bernoulli}(q):

  2. Eδ∥y−y^∥2=∥y−Xw∥2+1−qq∑j=1p∥xj∥2wj2\E_{\boldsymbol\delta}\norm{\mathbf y-\hat{\mathbf y}}^2=\norm{\mathbf y-X\mathbf w}^2+\frac{1-q}q\sum_{j=1}^p\norm{\mathbf x_j}^2w_j^2

    Average the squared error over the masks: the mean prediction is the undropped one, and the variances of the independent terms add up:

  3. Ωdropout(w)=1−qq∑j=1p∥xj∥2wj2\Omega_{\text{dropout}}(\mathbf w)=\frac{1-q}q\sum_{j=1}^p\norm{\mathbf x_j}^2w_j^2

    This is ridge with a per-feature weight, equivalently ridge on standardized features. For generalized linear models, dropout is to second order an L2L_2 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 L2L_2 term in the loss and decoupled weight decay are no longer the same thing (Loshchilov & Hutter, 2019).

The implicit bias of gradient descent

DerivationProof
  1. wt∈R(X⊤)  for all t\mathbf w_t\in\mathcal R(X^\top)\ \text{ for all }t

    Every gradient, 2X⊤(Xw−y)2X^\top(X\mathbf w-\mathbf y), lies in the row space R(X⊤)\mathcal R(X^\top). Starting from 0\mathbf 0, so does every iterate, and so does the limit, because the subspace is closed:

  2. ∥w†+z∥2=∥w†∥2+∥z∥2(w†∈R(X⊤), z⊥R(X⊤))\norm{\mathbf w^\dagger+\mathbf z}^2=\norm{\mathbf w^\dagger}^2+\norm{\mathbf z}^2\qquad(\mathbf w^\dagger\in\mathcal R(X^\top),\ \mathbf z\perp\mathcal R(X^\top))

    The loss is a convex quadratic, so with step below 1/d121/d_1^2 the iterates converge to a minimizer; since XX has rank nn, the minimum is 00 and the limit interpolates. Every interpolant has the form w†+z\mathbf w^\dagger+\mathbf z with z∈ker⁡X=R(X⊤)⊥\mathbf z\in\ker X=\mathcal R(X^\top)^\perp, and Pythagoras gives

  3. w^λ=X⊤(XX⊤+λI)−1y → λ→0+  X⊤(XX⊤)−1y=w†\hat{\mathbf w}_\lambda=X^\top(XX^\top+\lambda I)^{-1}\mathbf y\ \xrightarrow{\ \lambda\to0^+\ }\ X^\top(XX^\top)^{-1}\mathbf y=\mathbf w^\dagger

    The only interpolant inside R(X⊤)\mathcal R(X^\top) has z=0\mathbf z=\mathbf 0: the limit is w†\mathbf w^\dagger, the minimum-norm one. For ridge, the push-through identity (X⊤X+λI)−1X⊤=X⊤(XX⊤+λI)−1(X^\top X+\lambda I)^{-1}X^\top=X^\top(XX^\top+\lambda I)^{-1} gives the same limit:

The geometry of the algorithm picks the solution. Started at w0\mathbf w_0, gradient descent on least squares converges to the interpolant nearest w0\mathbf w_0; 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).

Check your understanding

You run gradient descent on an underdetermined least-squares problem (p>np>n, rank nn) from a nonzero start w0\mathbf w_0, with a small step. Where does it converge?

  1. To the minimum-norm interpolant X+yX^+\mathbf y, whatever the start
  2. To the interpolant closest to w0\mathbf w_0, namely w0+X+(y−Xw0)\mathbf w_0+X^+(\mathbf y-X\mathbf w_0)
  3. It does not converge, because there are infinitely many minimizers
  4. To w0\mathbf w_0 itself, since the gradient vanishes there
Show the answer

B. To the interpolant closest to w0\mathbf w_0, namely w0+X+(y−Xw0)\mathbf w_0+X^+(\mathbf y-X\mathbf w_0)

The iterates stay in w0+R(X⊤)\mathbf w_0+\mathcal R(X^\top), and the only interpolant in that affine subspace is w0+X+(y−Xw0)\mathbf w_0+X^+(\mathbf y-X\mathbf w_0), the projection of w0\mathbf w_0 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 ∑j(σ2dj2+λ2αj2)/(dj2+λ)2\sum_j(\sigma^2d_j^2+\lambda^2\alpha_j^2)/(d_j^2+\lambda)^2; its derivative at 00 is negative, so some λ>0\lambda>0 always beats least squares (Hoerl–Kennard), and λ=σ2/τ2\lambda=\sigma^2/\tau^2 is Bayes-optimal under a N(0,τ2)\mathcal N(0,\tau^2) prior.
  • The lasso's KKT conditions pin every active variable's residual correlation at ±λ\pm\lambda. Vertices of the ℓ1\ell_1 ball have full-dimensional normal cones, so sparse solutions occur with positive probability.
  • Under a restricted eigenvalue condition with λ≍σlog⁡p/n\lambda\asymp\sigma\sqrt{\log p/n}, the lasso's error is ∥w^−w⋆∥22≲sσ2log⁡p/(κ2n)\norm{\hat{\mathbf w}-\mathbf w^\star}_2^2\lesssim s\sigma^2\log p/(\kappa^2n); exact support recovery needs irrepresentability and a minimum signal size.
  • Early stopping filters like ridge with λ≈1/(ηt)\lambda\approx1/(\eta t); input noise is ridge with λ=ns2\lambda=ns^2; dropout is ridge weighted by ∥xj∥2\norm{\mathbf x_j}^2.
  • 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.

Question 1

In the fixed-design linear model, how does the mean squared error of ridge behave as λ\lambda increases from 00?

  1. It increases immediately, because ridge is biased
  2. It stays constant until λ\lambda exceeds the smallest eigenvalue of X⊤XX^\top X
  3. It decreases at first, so some λ>0\lambda>0 beats least squares
  4. It decreases monotonically for all λ\lambda
Show the answer

C. It decreases at first, so some λ>0\lambda>0 beats least squares

Each term's derivative is 2dj2(λαj2−σ2)/(dj2+λ)32d_j^2(\lambda\alpha_j^2-\sigma^2)/(d_j^2+\lambda)^3, negative for λ<σ2/αj2\lambda<\sigma^2/\alpha_j^2. The variance falls at first order while the squared bias grows only at second order in λ\lambda, so a little shrinkage always helps; too much makes the bias dominate.

Question 2

For the lasso min⁡w12n∥y−Xw∥2+λ∥w∥1\min_{\mathbf w}\frac1{2n}\norm{\mathbf y-X\mathbf w}^2+\lambda\norm{\mathbf w}_1, when is the solution exactly 0\mathbf 0?

  1. Exactly when λ≥∥X⊤y∥∞/n\lambda\ge\norm{X^\top\mathbf y}_\infty/n
  2. Only in the limit λ→∞\lambda\to\infty
  3. When λ\lambda exceeds the largest eigenvalue of X⊤X/nX^\top X/n
  4. Never, if y≠0\mathbf y\ne\mathbf 0
Show the answer

A. Exactly when λ≥∥X⊤y∥∞/n\lambda\ge\norm{X^\top\mathbf y}_\infty/n

At w^=0\hat{\mathbf w}=\mathbf 0 the residual is y\mathbf y, and the KKT conditions require ∣xj⊤y∣/n≤λ\abs{\mathbf x_j^\top\mathbf y}/n\le\lambda for every jj. So the whole path starts at λmax⁡=∥X⊤y∥∞/n\lambda_{\max}=\norm{X^\top\mathbf y}_\infty/n, where the first variable enters.

Question 3

Inverted dropout with keep probability qq on the inputs of a linear regression is, in expectation over the masks, equivalent to which penalty?

  1. An ℓ1\ell_1 penalty 1−qq∥w∥1\frac{1-q}q\norm{\mathbf w}_1
  2. No penalty: inverted scaling makes dropout unbiased
  3. An early-stopping rule with t=1/qt=1/q steps
  4. A ridge penalty 1−qq∑j∥xj∥2wj2\frac{1-q}q\sum_j\norm{\mathbf x_j}^2w_j^2
Show the answer

D. A ridge penalty 1−qq∑j∥xj∥2wj2\frac{1-q}q\sum_j\norm{\mathbf x_j}^2w_j^2

The mask is unbiased, so the mean prediction is unchanged, but it adds variance 1−qq∑jxij2wj2\frac{1-q}q\sum_jx_{ij}^2w_j^2 to each prediction, and squared error charges for that variance. The result is ridge weighted by each feature's squared norm.

Question 4

Gradient descent on the logistic loss for linearly separable data has reached zero training error. What happens if you keep training?

  1. Nothing: the gradient is exactly zero once the data are separated
  2. The weights grow without bound while their direction slowly converges to the hard-margin SVM direction
  3. The weights converge to a finite minimizer of the logistic loss
  4. 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 wt≈w^log⁡t\mathbf w_t\approx\hat{\mathbf w}\log t, so the direction converges to the max-margin separator at rate O(1/log⁡t)\order{1/\log t}, 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).