Stagewise Additive Fitting And The Greedy Objective

Why the Stagewise Objective Is Local

Boosting builds a prediction from a sequence of additions. At a given stage, the central question is not simply which learner predicts the response best on its own. It is: which permitted addition most reduces the loss of the model already built? The current model matters because a learner that is weak by itself may improve it substantially, while a learner that looks strong in isolation may add little once earlier terms are present.

This is a greedy choice: optimize the next move while holding the earlier moves fixed. That procedure is different from choosing all learners and then jointly optimizing every coefficient. The distinction matters whenever the learner outputs overlap or are correlated.

Definition: For observations $(x_i,y_i)$, $i=1,\ldots,n$, let $F_m(x)$ be the prediction after $m$ additive terms, and let $L(y,F)$ be a specified loss. The empirical risk is $$ R(F_m)=\frac{1}{n}\sum_{i=1}^{n}L\bigl(y_i,F_m(x_i)\bigr). $$ Given a class $\mathcal{H}$ of candidate learners, a stagewise update chooses a learner $h_m\in\mathcal{H}$ and coefficient $\beta_m$ to minimize $$ R\bigl(F_{m-1}+\beta_m h_m\bigr), $$ with the previous model $F_{m-1}$ held fixed. If coefficients or learner choices are restricted, the minimization is over those permitted choices.

The stagewise objective is evaluated on the whole updated prediction, not on $h_m$ alone. In a finite sample, the learner contributes the values $h_m(x_i)$, and the update changes each current fitted value from $F_{m-1}(x_i)$ to $F_{m-1}(x_i)+\beta_m h_m(x_i)$. The loss is then calculated using those updated values.

The procedure is called forward stagewise because it adds terms one at a time. In the usual unrestricted version, each new coefficient is chosen for that update, but coefficients from earlier stages are not subsequently changed. The exact optimization at a stage can vary with the loss and the permitted learner class; the definition above states the objective without requiring a particular algorithm for solving it.

Stagewise Fitting Versus Joint Optimization

After $M$ additions, the model has the form $$ F_M(x)=F_0(x)+\sum_{m=1}^{M}\beta_m h_m(x). $$ A stagewise procedure selects one new pair $(h_m,\beta_m)$ at a time. By contrast, a joint optimization over $M$ terms would choose all learners and coefficients together:

\min_{h_1,\ldots,h_M\in\mathcal{H},\,\beta_1,\ldots,\beta_M} R\left(F_0+\sum_{m=1}^{M}\beta_m h_m\right).

In stagewise fitting, once an earlier coefficient has been chosen, it remains fixed unless the procedure explicitly includes a refitting step. In joint optimization, every coefficient may adjust in response to all the other selected terms. These objectives need not produce the same model. The greedy procedure makes a locally best next addition, but it does not generally guarantee the globally best model with $M$ terms.

Question	Stagewise fitting	Joint optimization
What is optimized?	The risk after adding one candidate term to the current model	The risk of the complete model with all selected terms
Are earlier coefficients changed?	No, in the usual forward stagewise procedure	Yes, all coefficients are optimized together
What does “greedy” mean?	Choose the best available next move under the current objective	It is a simultaneous optimization, not a sequence of frozen choices

Squared-Error Line Search

A useful exact calculation is available when the loss is squared error. Use the convention $L(y,F)=\tfrac12(y-F)^2$, so the empirical risk is $1/(2n)$ times the sum of squared residuals. At a given stage, define the current residual for observation $i$ as $r_i=y_i-F_{m-1}(x_i)$. For a fixed candidate learner $h$, the stagewise objective as a function of its coefficient is

R(F_{m-1}+\beta h) =\frac{1}{2n}\sum_{i=1}^{n}\bigl(r_i-\beta h(x_i)\bigr)^2.

The coefficient can be found by expanding this quadratic and minimizing it. This is a line search along the candidate learner’s prediction vector, with the current model held fixed.

Expand the objective.
Writing $h_i=h(x_i)$, the sum inside the risk is $\sum_i r_i^2-2\beta\sum_i r_i h_i+\beta^2\sum_i h_i^2$.

Minimize over the coefficient.
Differentiate with respect to $\beta$, set the derivative equal to zero, and solve. If $\sum_i h_i^2>0$, the minimizing unrestricted coefficient is $\beta^*=\frac{\sum_i r_i h_i}{\sum_i h_i^2}$.

Compare learners by their minimized risks.
For each candidate $h$, use its own minimizing coefficient and compare the resulting values of $R(F_{m-1}+\beta^*h)$. The candidate with the smallest resulting risk is the greedy choice.

The formula follows because the expanded expression is a quadratic in $\beta$. Its second derivative is $\frac{1}{n}\sum_i h_i^2$, which is positive when the candidate is not identically zero on the training observations. Thus the stationary point is the unique minimum. Substitution also gives the reduction in empirical risk:

R(F_{m-1})-R(F_{m-1}+\beta^*h) =\frac{\left(\sum_{i=1}^{n}r_i h_i\right)^2}{2n\sum_{i=1}^{n}h_i^2}.

This reduction is nonnegative. If $\sum_i h_i^2=0$, the learner is zero on every training observation, so no coefficient changes the training predictions; the coefficient is not identified by this objective and the candidate gives no improvement. If coefficients are constrained, the unrestricted formula may not be feasible, and the minimum must instead be taken over the allowed coefficient values.

Worked Example: Selecting the First Greedy Learner

Hypothetical scenario. A model is being fitted to two observations with responses $y=(3,1)$, starting from $F_0=(0,0)$. Two candidate learners have training predictions $h_1=(1,1)$ and $h_2=(1,0)$. Use squared-error risk $R=\frac{1}{2n}\sum_i(y_i-F_i)^2$, and select the learner with the smaller risk after its coefficient is optimized.

Method. For each learner, compute its coefficient by the squared-error line-search formula, then calculate the updated predictions and risk. Here $n=2$, and the initial risk is $(3^2+1^2)/4=10/4=2.5$.

For $h_1=(1,1)$, the residual is $r=(3,1)$. The coefficient is $\beta_1=(3\cdot1+1\cdot1)/(1^2+1^2)=4/2=2$. The updated predictions are $2(1,1)=(2,2)$, so the residuals are $(1,-1)$. The risk is $(1^2+(-1)^2)/4=2/4=0.5$.

For $h_2=(1,0)$, the coefficient is $\beta_2=(3\cdot1+1\cdot0)/(1^2+0^2)=3$. The updated predictions are $3(1,0)=(3,0)$, and the residuals are $(0,1)$. The risk is $(0^2+1^2)/4=1/4=0.25$.

Therefore, the first greedy learner is $h_2$, with coefficient $3$ and risk $0.25$. The reduction from the initial risk is $2.5-0.25=2.25$. As a check, the reduction formula for $h_2$ gives $3^2/(2\cdot2\cdot1)=9/4=2.25$, as required. The common mistake to avoid is choosing $h_1$ without comparing its minimized risk to $h_2$’s.

Why Frozen Coefficients Can Matter

When candidate learners have overlapping prediction patterns, a later addition can change how the model would ideally allocate weight among the terms. Stagewise fitting does not automatically revisit that allocation. The following example makes the distinction explicit.

Worked Example: A Two-Stage Fit Compared With a Joint Fit

Hypothetical scenario. Three observations have responses $y=(2,0.2,1)$, and $F_0=(0,0,0)$. The two candidate learners are $a=(1,0,0)$ and $b=(1,1,0)$. Use $R=\frac{1}{6}\sum_i(y_i-F_i)^2$, the squared-error risk for $n=3$. At each stage choose the candidate and unrestricted coefficient giving the least risk for that update.

First stage. The risk before any update is $(2^2+0.2^2+1^2)/6=(4+0.04+1)/6=5.04/6=0.84$. For $a$, the minimizing coefficient is $2/1=2$; its updated predictions are $(2,0,0)$, leaving residuals $(0,0.2,1)$. Its risk is $(0+0.04+1)/6=1.04/6$, approximately $0.1733$.

For $b$, the coefficient is $(2+0.2)/(1+1)=1.1$. The predictions are $(1.1,1.1,0)$, giving residuals $(0.9,-0.9,1)$. The risk is $(0.81+0.81+1)/6=2.62/6$, approximately $0.4367$. Thus the first stage selects $a$ with coefficient $2$.

Second stage. With $a$ fixed at coefficient $2$, the residual is $(0,0.2,1)$. Adding a multiple of $a$ has optimal incremental coefficient $0$, since its residual dot product with $a$ is $0$. For $b$, the incremental coefficient is $(0+0.2+0)/2=0.1$. The resulting predictions are $2a+0.1b=(2.1,0.1,0)$, so the residuals are $(-0.1,0.1,1)$. The stagewise risk is $(0.01+0.01+1)/6=1.02/6=0.17$.

Joint comparison. A joint model $\alpha a+\gamma b$ predicts $(\alpha+\gamma,\gamma,0)$. Choosing $\gamma=0.2$ and $\alpha=1.8$ fits the first two responses exactly; the third prediction must be zero, leaving residual $1$. The joint risk is therefore $1/6$, approximately $0.1667$, less than the stagewise risk $1.02/6$. The calculation checks the distinction: the sequential fit retains the first coefficient $2$, whereas the joint fit changes it to $1.8$. The common mistake is to describe a frozen stagewise fit as though it had jointly reoptimized its earlier coefficient.

Choosing the Next Addition From the Current Model

The stagewise objective is conditional on what has already been fitted. The next example starts from a nonzero model to show why comparing candidates against the response alone can give the wrong answer.

Worked Example: Ranking Candidates Against a Nonzero Fit

Hypothetical scenario. Three responses are $y=(2,2,0)$, and the current model predicts $F=(1,0,1)$. Candidate learners have predictions $h_A=(1,0,1)$, $h_B=(0,1,1)$, and $h_C=(1,1,0)$. Use $R=\frac{1}{6}\sum_i(y_i-F_i)^2$, and choose the candidate whose optimized addition gives the smallest risk.

The current residual is $r=y-F=(1,2,-1)$, and the current risk is $(1^2+2^2+(-1)^2)/6=6/6=1$.

For $h_A$, the residual dot product is $1+0-1=0$, and $\sum_i h_{A,i}^2=2$. Thus its optimal coefficient is $0/2=0$, so its risk remains $1$.

For $h_B$, the dot product is $0+2-1=1$ and the squared norm is $2$. Its coefficient is $1/2=0.5$. The new residual is $(1,1.5,-1.5)$, giving risk $(1+2.25+2.25)/6=5.5/6$, approximately $0.9167$.

For $h_C$, the dot product is $1+2+0=3$ and the squared norm is $2$, so the coefficient is $3/2=1.5$. The new residual is $(1,2,-1)-1.5(1,1,0)=(-0.5,0.5,-1)$. Its risk is $(0.25+0.25+1)/6=1.5/6=0.25$. Therefore $h_C$ is the greedy choice. The risk reduction is $1-0.25=0.75$, which also equals $3^2/(2\cdot3\cdot2)=0.75$. The common mistake is to fit each learner to $y$ as if $F$ were zero; the objective here depends on the residual from the current model.

Common Exam Traps

Ranking learners before optimizing their coefficients. Compare each candidate after its permitted coefficient has been optimized, not by an arbitrary coefficient or by its standalone fit.
Using the wrong baseline. The update is judged against $F_{m-1}$, so the relevant residual under squared error is $y_i-F_{m-1}(x_i)$, not $y_i$ unless the current model is zero.
Confusing sequential and joint fitting. A stagewise method freezes earlier coefficients unless refitting is explicitly part of the method. Joint optimization does not have this restriction.
Claiming a greedy choice is globally optimal. It is best among the next permitted updates from the current model; that does not establish that the final collection of terms is the best collection of the same size.
Ignoring a zero or constrained update. A zero learner cannot change training predictions. With coefficient restrictions, the unrestricted line-search formula may not be allowed.

Key takeaway: Stagewise additive fitting minimizes the loss after adding one term to the current model while keeping earlier terms fixed. Joint optimization instead permits all coefficients to change together. The two objectives can select different coefficients and produce different risks.

Check Your Understanding

For squared-error risks below, use $R=\frac{1}{2n}\sum_i(y_i-F_i)^2$ unless stated otherwise. Each update uses an unrestricted coefficient.

For $y=(2,0)$, $F_0=(0,0)$, and $h=(1,1)$, find the minimizing coefficient and the updated risk. (Answer: $\beta=1$; updated risk $=0.5$.)
For $y=(1,3)$, $F_0=(0,0)$, and candidates $h_A=(1,0)$, $h_B=(0,1)$, which candidate is selected at the first stage, and what are its coefficient and risk? (Answer: $h_B$, coefficient $3$, risk $0.25$.)
Let $y=(2,0.2,1)$, $F_0=(0,0,0)$, $a=(1,0,0)$, and $b=(1,1,0)$, with risk $R=\frac{1}{6}\sum_i(y_i-F_i)^2$. After the first stage selects $a$, find the next stagewise coefficient for $b$, the two-term stagewise risk, and the joint-fit risk for $\alpha a+\gamma b$. (Answer: the increment for $b$ is $0.1$; stagewise risk $=1.02/6=0.17$; joint-fit risk $=1/6$.)
For $y=(3,1)$, current predictions $F=(1,1)$, and candidates $h_A=(1,0)$, $h_B=(1,1)$, identify the greedy candidate, coefficient, and updated risk under the stated squared-error convention. (Answer: $h_A$, coefficient $2$, updated risk $=0$.)

What You'll Learn