Shrinkage As A Step-Size Regularizer

Why Scale a Boosting Update?

In gradient boosting, each round adds a fitted function to the current predictor. The fitted function and its coefficient determine a direction and a proposed distance to move. Shrinkage multiplies that update by a learning rate, so the model takes a smaller step in the chosen direction. This can make progress slower per round, but it also changes the sequence of predictors that the algorithm visits.

This distinction matters. If the learner is refitted after every update, a smaller step can lead to different later directions, not just a slower version of the same sequence. Shrinkage is therefore a step-size regularizer: it restricts how far one round can move, but it is not a penalty term and does not guarantee that test risk will be lower.

Definition: Let $F_{m-1}$ be the predictor after $m-1$ boosting rounds, and let $h_m$ be the fitted update direction at round $m$. Suppose a line search chooses a coefficient $\rho_m$, giving the proposed update $\rho_m h_m$. With learning rate $\eta$, the shrunken update is $$ F_m=F_{m-1}+\eta\rho_m h_m,\qquad 0<\eta\leq 1. $$ The value $\eta=1$ takes the proposed line-search step; $0<\eta<1$ takes only a fraction of it.

For a training sample of size $n$, write the empirical risk as $R(F)=n^{-1}\sum_{i=1}^n \ell(y_i,F(x_i))$. At a fixed round, the line search considers $R(F_{m-1}+\rho h_m)$ as a function of $\rho$. Shrinkage instead uses $\eta\rho_m$. If the line search finds a minimizer along the current direction, taking a fraction of that step cannot improve on that minimizer for that same one-dimensional search. Its value comes from controlling the path across rounds, especially when subsequent directions are fitted anew.

A Smoothness Condition for Descent

A small step is useful only if it moves in a descent direction. The following result gives a sufficient step-size condition. It is stated in finite-dimensional coordinates, such as the vector of fitted values on the training observations.

Theorem (Descent lemma): Suppose $R:\mathbb{R}^p\to\mathbb{R}$ is differentiable and its gradient is $L$-Lipschitz on the line segment from $\theta$ to $\theta+\eta d$, for some chosen bound $L>0$. Then, for $\eta\geq 0$, $$ R(\theta+\eta d)\leq R(\theta)+\eta\nabla R(\theta)^\mathsf{T}d+\frac{L\eta^2}{2}\|d\|^2. $$ If $\nabla R(\theta)^\mathsf{T}d<0$, then $R(\theta+\eta d)<R(\theta)$ whenever $$ 0<\eta<\frac{-2\nabla R(\theta)^\mathsf{T}d}{L\|d\|^2}. $$

Here $L$ is a positive Lipschitz bound, not necessarily the smallest possible one. If the gradient is constant, it is $0$-Lipschitz, but any positive $L$ is also a valid bound. Stating $L>0$ keeps the sufficient step-size expression well-defined. The strict directional condition implies $d\ne 0$, so its denominator is positive.

To prove the inequality, define $g(t)=R(\theta+t\eta d)$ for $0\leq t\leq 1$. The fundamental theorem of calculus gives $$ R(\theta+\eta d)-R(\theta)=\int_0^1 \eta\nabla R(\theta+t\eta d)^\mathsf{T}d\,dt. $$ Add and subtract $\nabla R(\theta)$ inside the integral. By the Lipschitz condition and the Cauchy–Schwarz inequality, $$ \left|(\nabla R(\theta+t\eta d)-\nabla R(\theta))^\mathsf{T}d\right| \leq Lt\eta\|d\|^2. $$ Consequently, $$ R(\theta+\eta d)-R(\theta) \leq \eta\nabla R(\theta)^\mathsf{T}d +\int_0^1 L t\eta^2\|d\|^2\,dt =\eta\nabla R(\theta)^\mathsf{T}d+\frac{L\eta^2}{2}\|d\|^2. $$ When the directional derivative is negative, the right-hand side is strictly negative if $\eta>0$ and $\eta\nabla R(\theta)^\mathsf{T}d+(L\eta^2/2)\|d\|^2<0$. Dividing by the positive quantity $\eta L\|d\|^2/2$ gives the stated bound. $\square$

In boosting, this result applies when the empirical risk in the chosen coordinates has a Lipschitz gradient along the proposed update. A fitted negative-gradient direction is intended to have a negative directional derivative, but an imperfect base learner need not achieve one. Shrinkage limits the step; it does not turn a non-descent direction into a descent direction.

Worked Example: A Quadratic Risk and the Number of Rounds

Consider $R(a)=\tfrac12(a-3)^2$, starting at $a_0=0$. At each round use the direction $d_m=3-a_{m-1}$. The full line-search coefficient is $1$, since $a_{m-1}+\rho d_m=3$ at $\rho=1$, which minimizes $R$ along this direction. Set the learning rate to $\eta=0.2$.

The shrunken update is $$ a_m=a_{m-1}+0.2(3-a_{m-1}). $$ Let $e_m=3-a_m$ denote the distance to the minimizer. Then $$ e_m=3-a_{m-1}-0.2(3-a_{m-1})=0.8e_{m-1}. $$ Since $e_0=3$, repeated substitution gives $e_m=3(0.8)^m$, and therefore $$ R(a_m)=\frac12 e_m^2=4.5(0.64)^m. $$

After five rounds, $R(a_5)=4.5(0.64)^5=4.5(0.1073741824)\approx0.4832$. To get risk below $0.1$, require $4.5(0.64)^m<0.1$, or $(0.64)^m<0.02222\ldots$. At $m=8$, the risk is about $0.1267$; at $m=9$, it is about $0.0811$. Thus nine rounds are needed for this threshold. A full step would reach $a=3$ in one round. Here shrinkage clearly slows progress in rounds, while producing a sequence of smaller changes.

What Shrinkage Does to the Path

The quadratic example has a particularly simple path: every round uses the same direction rule, and the distance to the optimum contracts by a constant factor. Real boosting is more complicated. The fitted update at round $m+1$ is based on the current predictor, so changing $\eta$ changes the residuals or pseudo-residuals used to fit the next base learner. Even when two runs use the same base-learner class, their later directions can differ.

A useful interpretation is that shrinkage moderates the influence of each fitted component. At a fixed number of rounds, a smaller $\eta$ usually means less cumulative movement when the directions and coefficients are comparable. Reaching a similar training-risk level can then require more rounds. The quadratic calculation illustrates this exactly, but the rough idea that the number of rounds scales like $1/\eta$ is not a general theorem: the directions, line-search coefficients, and curvature can all change along the path.

More rounds do not necessarily mean a more complicated predictor in a simple one-to-one sense. With small steps, many components may accumulate gradually; with larger steps, fewer components can produce a rapid fit. The realized complexity depends on the base learners, the data, the loss, and the path of fitted updates.

Worked Example: Shrinking an AdaBoost Line-Search Step

Suppose the current normalized weights assign total weight $e=0.2$ to observations misclassified by a candidate binary rule and weight $1-e=0.8$ to those it classifies correctly. For the exponential loss, the AdaBoost line-search coefficient is $$ \alpha=\frac12\log\left(\frac{1-e}{e}\right) =\frac12\log(4)=\log(2)\approx0.6931. $$

If the coefficient is multiplied by $\eta$, the exponential-loss normalization factor for this fixed rule is $$ Z(\eta)=(1-e)e^{-\eta\alpha}+e e^{\eta\alpha}. $$ For a half step, $\eta=0.5$, so $e^{-\eta\alpha}=2^{-1/2}\approx0.7071$ and $e^{\eta\alpha}=2^{1/2}\approx1.4142$. Thus $$ Z(0.5)=0.8(0.7071)+0.2(1.4142) \approx0.5657+0.2828=0.8485. $$ For the full line-search step, $$ Z(1)=0.8(0.5)+0.2(2)=0.4+0.4=0.8. $$ The full step gives the smaller one-round factor for this fixed rule. The half step still reduces the exponential loss because $0.8485<1$, but reduces it less in this round. This calculation shows why shrinkage should not be described as improving every immediate loss decrease; it controls the cumulative path instead.

Why It Can Help, and What It Cannot Guarantee

A flexible boosting procedure can keep reducing training loss as rounds accumulate, including by fitting patterns that are specific to the training sample. Smaller updates can make this fitting more gradual: any one newly fitted component has less influence on the current predictor. In practice, this can make the sequence less sensitive to a single update and can improve predictive performance for some data sets and settings.

That practical benefit is not a universal guarantee. Shrinkage alone does not imply that test risk decreases, that the predictor is less variable, or that a particular learning rate is optimal. At a fixed round count, a small learning rate may underfit; at a sufficiently large number of rounds, its path may reach a similarly low training risk. Whether its test performance is better is an empirical question. In particular, lowering training risk is not the same as lowering risk on new observations.

Worked Example: Training Risk Falls While Held-Out Risk Rises

Consider a constant predictor $F(x)=a$ with squared loss $\tfrac12(y-a)^2$. The one-observation training set has response $y=1$, and a held-out observation has response $y=-1$. Start at $a_0=0$, use the constant update direction $h=1$, and take the training-risk line-search coefficient $\rho=1$. With $\eta=0.5$, the update is $a_m=a_{m-1}+0.5(1-a_{m-1})$.

This gives $a_1=0.5$, $a_2=0.75$, and, by the recurrence $1-a_m=0.5(1-a_{m-1})$, $a_m=1-2^{-m}$. The training risk at round $m$ is $$ R_{\mathrm{train}}(a_m)=\frac12(1-a_m)^2=2^{-2m}. $$ It falls from $0.5$ at round zero to $0.125$ at round one and $0.03125$ at round two. The held-out loss, however, is $$ R_{\mathrm{held\text{-}out}}(a_m)=\frac12(-1-a_m)^2. $$ It rises from $0.5$ at round zero to $1.125$ at round one and $1.53125$ at round two. In this deliberately small example, the training observation and held-out observation disagree, so fitting the former makes prediction on the latter worse. It demonstrates a possibility, not a prediction that shrinkage generally harms performance: shrinkage delays the movement toward the training response, but does not guarantee that the held-out loss will improve.

Common Mistakes

Calling shrinkage a guarantee of better generalization. It limits each update, but test risk depends on the data and the full sequence of fitted directions.
Assuming a smaller learning rate improves the current line-search objective. Along a fixed direction, a full line-search minimizer is already optimal for that one-dimensional search. A fractional step can have a smaller immediate decrease.
Assuming the path is just the same models at a slower speed. Refitting the base learner after each update can change later directions when the learning rate changes.
Using a descent bound without its hypotheses. A smoothness-based step-size guarantee needs a descent direction and a positive Lipschitz bound on the relevant segment. If the direction is not descending, shrinking it does not by itself establish a decrease.
Equating number of rounds with complexity. Many small updates and a few large updates can behave differently; the round count alone does not determine predictive complexity.

Key takeaway: Shrinkage multiplies each boosting update by a learning rate, typically making progress per round more gradual and changing the optimization path. It is a practical step-size regularizer, not a universal risk guarantee; its effect must be judged along the resulting sequence of predictors.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

In the update $F_m=F_{m-1}+\eta\rho_mh_m$, which quantities determine the update direction and the proposed line-search distance, and what does $\eta$ change?
Why must the descent-lemma statement specify a positive Lipschitz bound even when the gradient happens to be constant?
For the quadratic example, derive the recurrence for $e_m=3-a_m$ and explain why the risk contracts by a factor of $0.64$ each round.
Why can a shrunken step have a smaller one-round loss reduction than the full line-search step while still being useful across many rounds?
Give one reason that a smaller learning rate may improve practical generalization and one reason it cannot guarantee lower test risk.