Functional Gradient Boosting For Differentiable Losses

From Finite-Dimensional Descent to Function Updates

A statistical predictor can be viewed as a function $F$ that assigns a score to each input $x$. In boosting, the predictor is built additively: each new component changes the current scores rather than replacing the existing model. The key question is how to choose that change when the objective is an empirical loss.

On a fixed training sample $(x_i,y_i)_{i=1}^n$, the loss depends on $F$ only through its $n$ fitted values. Thus, even though $F$ is a function, empirical optimization can be described by a vector of scores. Gradient boosting uses this observation: calculate the direction that most rapidly decreases the loss in score space, then approximate that direction using a permitted base learner.

Definition: Let $\ell(y,F(x))$ be differentiable in its second argument. The empirical risk of a predictor $F$ is $$ R(F)=\frac{1}{n}\sum_{i=1}^n \ell(y_i,F(x_i)). $$ The negative functional gradient at the training observations is the vector $r=(r_1,\ldots,r_n)$, where $$ r_i=-\left.\frac{\partial \ell(y_i,z)}{\partial z}\right|_{z=F(x_i)}. $$ Its entries are the negative loss derivatives with respect to the current fitted scores.

The word “functional” emphasizes that the object being updated is a predictor function. For empirical risk, however, the derivative is evaluated at the observed inputs. A base learner $h$ supplies a possible change $h(x_i)$ to each training score. If those changes approximate $r_i$, the additive update $F+\eta h$, for a positive step size $\eta$, moves in a direction intended to reduce risk.

The Gradient and the Additive Update

Use the empirical inner product $\langle u,v\rangle_n=n^{-1}\sum_i u_i v_i$ and norm $\|u\|_n^2=\langle u,u\rangle_n$. Write $g_i=\partial\ell(y_i,z)/\partial z$ evaluated at $z=F(x_i)$, so $r_i=-g_i$. For any vector of score changes $v$, differentiation gives

\left.\frac{d}{dt}R(F+t v)\right|_{t=0} =\frac{1}{n}\sum_{i=1}^n g_i v_i =\langle g,v\rangle_n.

Consequently, the direction $r=-g$ has directional derivative $\langle g,r\rangle_n=-\|g\|_n^2$, which is nonpositive and is strictly negative unless every observed score has zero derivative. This identifies the unrestricted steepest-descent direction in score space. A boosting method cannot generally add an arbitrary vector of $n$ changes: it seeks a base learner whose fitted values approximate this direction.

Definition: Given a base-learner class $\mathcal H$, a gradient-fitting step chooses $h\in\mathcal H$ to approximate the negative gradient on the training sample, often by minimizing $$ \frac{1}{n}\sum_{i=1}^n (r_i-h(x_i))^2. $$ The additive update is $F_{\mathrm{new}}(x)=F(x)+\eta h(x)$, with $\eta>0$. The fit is an approximation to a descent direction; it is not itself a guarantee that every possible update decreases the empirical risk.

A useful alignment fact follows directly from the fitting criterion. If the class contains the zero function and $h$ minimizes the displayed squared error, its error is no greater than the error of the zero function. Expanding that comparison gives

\|r-h\|_n^2\leq \|r\|_n^2 \quad\Longrightarrow\quad 2\langle r,h\rangle_n\geq \|h\|_n^2.

Thus a nonzero exact least-squares fit has positive alignment with the negative gradient. This fact explains why gradient fitting is a principled construction. It does not, by itself, account for curvature in the loss or justify an arbitrarily large step.

Worked Example: A Gradient-Fitting Step for Regression

Suppose four training responses are $y=(1,1,-1,-1)$, and the current predictor has score $F(x_i)=0$ at all four observations. Use the squared-error loss $\ell(y,z)=\tfrac12(y-z)^2$. A base learner can split the observations into the first two and last two, assigning a constant score within each group.

The loss derivative is $\partial\ell(y,z)/\partial z=z-y$. At the current scores it is $-y_i$, so the negative-gradient values are $r_i=y_i$, namely $(1,1,-1,-1)$. The indicated split can fit these values exactly with $h(x_i)=y_i$.

For an update $F_{\mathrm{new}}=F+\eta h$, each residual is $y_i-\eta h(x_i)=(1-\eta)y_i$. Since $y_i^2=1$, the empirical risk is $$ R(F+\eta h)=\frac{1}{4}\sum_{i=1}^4\frac12(1-\eta)^2 y_i^2 =\frac12(1-\eta)^2. $$

The initial risk is $1/2$. At $\eta=1/2$, the new risk is $\tfrac12(\tfrac12)^2=1/8=0.125$. The update decreases risk because this learner follows the negative gradient and the chosen step is not too large. This calculation illustrates the general gradient-fitting construction; it does not require that every loss produce residuals of the form $y_i-F(x_i)$.

A Descent Guarantee for a Smooth Empirical Risk

To state a precise guarantee, regard $R$ as a differentiable function of the vector of training scores. Say its gradient is $L$-Lipschitz along the segment from $F$ to $F+\eta h$ if, for all points $F+t\eta h$ on that segment, the gradient changes in empirical norm by at most $L$ times the change in scores. The constant $L$ can be a local bound for that segment; a global bound is not required.

Theorem: Suppose $R$ is continuously differentiable on the segment from $F$ to $F+\eta h$, and its gradient is $L$-Lipschitz there in the empirical norm. Let $r=-\nabla R(F)$ be the negative gradient vector. Then $$ R(F+\eta h)\leq R(F)-\eta\langle r,h\rangle_n +\frac{L\eta^2}{2}\|h\|_n^2. $$ In particular, if $\langle r,h\rangle_n>0$ and $h\neq 0$, every step satisfying $0<\eta<2\langle r,h\rangle_n/(L\|h\|_n^2)$ gives a strict decrease.

Here the gradient is with respect to the score vector, using the empirical inner product, so its entries are the loss derivatives $g_i$ defined above. The condition is about the direction and the step together: positive alignment supplies the first-order decrease, while the second-order term limits how much curvature can offset it.

Proof of the Descent Bound

Define the scalar function $\phi(t)=R(F+t\eta h)$ for $0\leq t\leq 1$. By the chain rule and the fundamental theorem of calculus,

R(F+\eta h)-R(F) =\phi(1)-\phi(0) =\int_0^1 \langle \nabla R(F+t\eta h),\eta h\rangle_n\,dt.

Add and subtract $\nabla R(F)$ inside the integrand. The constant-gradient part is $\eta\langle\nabla R(F),h\rangle_n=-\eta\langle r,h\rangle_n$. For the remaining part, the Cauchy–Schwarz inequality and the Lipschitz condition give

\begin{aligned} &\int_0^1 \langle \nabla R(F+t\eta h)-\nabla R(F),\eta h\rangle_n\,dt\\ &\qquad\leq \int_0^1 \|\nabla R(F+t\eta h)-\nabla R(F)\|_n\,\eta\|h\|_n\,dt\\ &\qquad\leq \int_0^1 Lt\eta^2\|h\|_n^2\,dt =\frac{L\eta^2}{2}\|h\|_n^2. \end{aligned}

Combining the two parts proves the inequality. If $\langle r,h\rangle_n>0$, its right-hand change in risk is strictly negative whenever $-\eta\langle r,h\rangle_n+(L\eta^2/2)\|h\|_n^2<0$. Dividing by the positive quantity $\eta\|h\|_n^2/2$ gives the stated step-size condition. $\square$

Worked Example: Checking the Descent Bound Numerically

Suppose a current empirical risk is $1$, the fitted direction has negative-gradient alignment $\langle r,h\rangle_n=1/12$, the step is $\eta=1$, and $\|h\|_n^2=1/16$. Suppose also that the gradient is Lipschitz along the update segment with $L=e^{1/4}$. The theorem gives $$ R(F+h)\leq 1-\frac{1}{12}+\frac{e^{1/4}}{32}. $$

Numerically, $e^{1/4}\approx1.2840254$, so the upper bound is $1-0.0833333+1.2840254/32\approx 1-0.0833333+0.0401258=0.9567925$, or $0.9568$ to four decimal places. This is a bound, not an exact risk calculation: the actual updated risk may be smaller.

Classification Losses Also Have Functional Gradients

For binary classification, encode labels as $y_i\in\{-1,+1\}$ and let $F(x)$ be a real-valued score. A predicted class can be obtained from the sign of that score, but the training objective may be a smooth loss of the score and label. Differentiating that loss gives a negative-gradient target just as in regression. Its values need not be class labels, and the fitted learner need not be a perfect classifier to have useful alignment.

Worked Example: A Differentiable Classification Surrogate

Take labels $y=(+1,+1,-1)$, current scores $F(x_i)=0$, and the differentiable squared-margin loss $\ell(y,z)=\tfrac12(1-yz)^2$. The derivative with respect to $z$ is $-y(1-yz)$. At zero scores the negative gradients are therefore $(+1,+1,-1)$.

Suppose the base learner returns $h=(1,0,-1)$. Its alignment with the negative gradient is $$ \langle r,h\rangle_3=\frac{1}{3}(1\cdot1+1\cdot0+(-1)\cdot(-1))=\frac23>0. $$ For $\eta=1/2$, the updated scores are $(1/2,0,-1/2)$. The three signed margins $y_iF_{\mathrm{new}}(x_i)$ are $1/2,0,1/2$, so their losses are $\tfrac12(1/2)^2=1/8$, $\tfrac12(1)^2=1/2$, and $\tfrac12(1/2)^2=1/8$. The updated empirical risk is $(1/8+1/2+1/8)/3=1/4$. The initial risk is $1/2$, so it has decreased to $1/4$. The middle observation receives no score change; gradient boosting does not require each individual observation to improve at every step.

Worked Example: A Classification Direction That Increases Risk

Keep the same labels and squared-margin loss at zero scores, but consider $h=(-1,-1,+1)$, the negative of the negative-gradient vector. Then $\langle r,h\rangle_3=-1$, so the direction is misaligned. At step size $\eta=1/2$, the updated scores are $(-1/2,-1/2,+1/2)$; each signed margin is $-1/2$. Each loss is $\tfrac12(1+1/2)^2=9/8$, giving empirical risk $9/8$, greater than the initial risk $1/2$.

This explicit calculation shows why merely adding a base learner is not enough. The sign and alignment of the fitted direction matter, as does the size of the step.

What the Gradient View Clarifies

Functional gradient boosting is a general optimization pattern, not a claim that every loss leads to the same numerical targets. The loss determines the derivatives; the current predictor determines where those derivatives are evaluated; and the base-learner class determines which approximations to the negative-gradient vector are available. The additive model then changes the predictor by the fitted learner, scaled by a positive step.

A common mistake is to treat the negative gradients as ordinary observed responses and assume that any fit to them guarantees a decrease in risk. The correction is twofold. First, the fitted learner must be aligned with the negative gradient, not its opposite. Second, even a well-aligned direction may increase risk if the step is too large: the smoothness bound includes a positive curvature term proportional to $\eta^2$. Gradient fitting supplies a direction; the descent result states the additional conditions needed for a guarantee.

This perspective also separates the role of the loss from the role of the learner. The derivative calculation is determined by the chosen objective, while approximation quality depends on the functions available in $\mathcal H$. In practice, a weak learner may only capture part of the negative gradient. The descent inequality makes the relevant issue precise: useful updates need positive alignment, and their step must be controlled relative to alignment, curvature, and the learner’s norm.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

For empirical risk $R(F)=n^{-1}\sum_i\ell(y_i,F(x_i))$, write the negative-gradient value at observation $i$ and explain why it depends on the current predictor.
If a least-squares fit $h$ to the negative-gradient vector minimizes squared error and the learner class contains zero, derive the inequality relating $\langle r,h\rangle_n$ to $\|h\|_n^2$.
In the descent bound, what roles are played by positive alignment and the Lipschitz-gradient constant?
For the squared-margin loss, why does a positive score change for a positive label have the opposite effect on the loss from the same score change for a negative label?
Can positive alignment alone guarantee a decrease for every positive step size? Explain using the curvature term in the theorem.