Gradient Boosting on Stochastic Data Streams

Hanzhang Hu; Wen Sun; Arun Venkatraman; Martial Hebert; J. Andrew Bagnell

Source-linked AI summary

Gradient Boosting on Stochastic Data Streams

Hanzhang Hu, Wen Sun, Arun Venkatraman, Martial Hebert, J. Andrew Bagnell

arXiv:1703.00377v1Mar 1, 2017cs.LG

TL;DR

The paper addresses how to adapt batch gradient boosting for convex-loss minimization to stochastic online regression. It introduces an online weak-learning edge and Streaming Gradient Boosting algorithms, obtaining exponential regret shrinkage for strongly convex smooth losses and O(ln N/N) convergence for non-smooth losses, with experiments supporting competitive performance against batch boosting using less computation.

Problem
The paper asks how batch gradient boosting for convex losses can be adapted to online regression when losses are i.i.d. sampled from an unknown distribution.
Method
The paper defines an online weak-learning edge and combines weak learners through gradient-descent-style streaming boosting, with separate treatments for smooth and non-smooth losses.
Results
SGB achieves exponential regret shrinkage for strongly convex smooth losses and an O(ln N/N) no-regret rate for non-smooth losses, while experiments support competitive results against classic gradient boosting using less computation.
Takeaways & Limitations
The analysis supports streaming gradient boosting as an online extension of classic gradient boosting, with guarantees that also extend to adversarial learning when the edge assumption holds there.
Takeaways & Limitations
The current SGB procedure uses gradient descent to combine weak-learner predictions, leaving accelerated, mirror, and adaptive gradient updates as open possibilities.

Abstract

from arXiv · show

Boosting is a popular ensemble algorithm that generates more powerful learners by linearly combining base models from a simpler hypothesis class. In this work, we investigate the problem of adapting batch gradient boosting for minimizing convex loss functions to online setting where the loss at each iteration is i.i.d sampled from an unknown distribution. To generalize from batch to online, we first introduce the definition of online weak learning edge with which for strongly convex and smooth loss functions, we present an algorithm, Streaming Gradient Boosting (SGB) with exponential shrinkage guarantees in the number of weak learners. We further present an adaptation of SGB to optimize non-smooth loss functions, for which we derive a O(ln N/N) convergence rate. We also show that our analysis can extend to adversarial online learning setting under a stronger assumption that the online weak learning edge will hold in adversarial setting. We finally demonstrate experimental results showing that in practice our algorithms can achieve competitive results as classic gradient boosting while using less computation.

1 INTRODUCTION

The paper adapts gradient boosting to stochastic regression streams by defining an online weak-learning edge and developing algorithms for smooth and non-smooth convex losses.

1 INTRODUCTION: Boosting is motivated by combining simple models into stronger learners and has been effective across vision, ranking, transportation, medical inference, and real-time applications.Its anytime test-time property supports varying computation budgets.
1 INTRODUCTION: Streaming boosting adapts batch gradient boosting to regression streams where each loss is independently sampled from an unknown fixed distribution.Weak predictors are trained stage-wise to approximate the functional gradient of the loss, with approximation error measured through an online regression edge.
1 INTRODUCTION: Assuming each weak learner achieves a non-trivial edge, the smooth-loss algorithm obtains exponential average-regret decay as the number of weak learners increases.The decay ratio depends on the weak-learning edge and the loss condition number.
1 INTRODUCTION: For strongly convex but non-smooth losses, the second algorithm achieves an O(ln N/N) convergence rate in the number of weak learners.This extends residual gradient boosting to non-smooth losses and matches the no-regret rate of online gradient descent for strongly convex loss.
1 INTRODUCTION: As both the sample count T and learner count N grow, both algorithms have average regret converging to zero.The analysis also extends to adversarial online learning when the weak-learning edge holds in that harsher setting.

2 RELATED WORK

Prior online boosting work addressed classification and regression, while this paper changes the weak-learner training and combination strategy to support non-smooth convex losses with gradient-boosting-like bounds.

2 RELATED WORK: Earlier online boosting research developed classification algorithms, convergence guarantees, and applications including feature selection and semi-supervised learning.The cited progression includes Oza and Russell, Leistner et al., Chen et al., and Beygelzimer et al. [Oza and Russell (2001); Chen et al. (2012); Beygelzimer et al. (2015b)].
2 RELATED WORK: Beygelzimer et al. (2015a) extended gradient boosting to online regression under smooth loss using linear-loss weak-learner training and Frank-Wolfe updates.Their analysis does not require weak-learner edge assumptions.
2 RELATED WORK: This work trains each weak learner with squared loss against the gradient, treating its prediction as a gradient approximation under an edge assumption.The ensemble can therefore use gradient-descent-style combination updates that mimic classic gradient boosting.
2 RELATED WORK: Compared with the prior Frank-Wolfe approach, the proposed design handles non-smooth convex losses such as hinge and L1 losses and yields bounds more analogous to batch boosting.The paper also explicitly assumes an online weak-learning edge.

3 PRELIMINARIES

The online boosting setup receives losses and inputs sequentially, combines predictions from weak learners, and analyzes performance through regret and risk under stochastic sampling.

3 PRELIMINARIES: At each round, the learner predicts before observing the loss, then updates after suffering that loss; the main analysis assumes i.i.d. loss-input pairs from a fixed distribution.The framework also permits adversarially generated sequences in the general online-learning formulation.
3 PRELIMINARIES: Regret compares the learner’s cumulative loss with that of the best hypothesis in hindsight, and no-regret means cumulative regret grows sublinearly in T.Risk is the expected loss of a hypothesis under the sampling distribution.
3 PRELIMINARIES: The analysis uses online-to-batch reduction to relate regret guarantees, obtained without stochastic assumptions, to risk through concentration of measure.This connects online performance to expected-risk conclusions in the stochastic setting.
3 PRELIMINARIES: The boosting learner maintains N weak online learners, combines their predictions into y_t, incurs the revealed loss, and passes a square loss to each weak learner for updating.In the stochastic setting, the generated hypotheses are combined into a final boosted hypothesis for future testing.
3.1 Online Boosting Setup: The setup seeks to improve a single weak learner through linear combination while ideally achieving prediction-error reduction exponential in N, as in batch gradient boosting.This objective motivates the learner-combination design.

4 WEAK ONLINE LEARNING

The paper defines an online weak learning edge that measures how well weak learners predict regression targets under streaming data. A positive edge is both sufficient for the later boosting analysis and necessary for linear ensembles to approximate targets in the stated setting.

Weak Online Learning Edge: The Weak Online Learning Edge requires square-loss weak learners to achieve sublinear excess loss while explaining a nonzero fraction γ of target variance.The definition includes high-probability control through an excess-loss term R(T) ∈ o(T).
Weak Online Learning Edge: A larger edge means the hypothesis better explains target variance, while the bound holds with high probability over learner and example randomness.The probability is 1−δ, with dependence on δ absorbed into R(T).
Weak Online Learning Edge: The edge definition extends batch weak learning to online data by adding an agnostic learnability assumption.The paper explicitly presents this as the online generalization of the batch definition.
Why Weak Learner Edge is Reasonable?: When H is scaling-closed and the target function is not orthogonal to span(H), no-regret online learning yields a nonzero weak-learning edge.The proposition assumes i.i.d. samples and relates the resulting edge to the online algorithm’s regret.
Why Weak Learner Edge is Reasonable?: Without a positive edge, span(H) is orthogonal to the target function, so no linear boosted ensemble can approximate it.The paper therefore treats a positive online weak learner edge as necessary for online boosted algorithms.

5 ALGORITHM

The paper develops Streaming Gradient Boosting for smooth losses and a residual-projection variant for strongly convex non-smooth losses. Under weak-learning edge assumptions, the methods obtain exponential or O(ln N/N) regret decay as the number of weak learners grows.

5.1 Smooth Loss Functions: SGB predicts by combining weak learners, trains each learner toward the loss gradient, and uses its prediction as an approximate gradient-descent step.The squared deviation from the gradient forces weak learners to approximate gradients, while averaged predictors support stochastic testing.
5.1 Smooth Loss Functions: Exponential decay in average regret with N weak learners is obtained for strongly convex, smooth losses under the weak online learning edge assumption.The decay depends on the edge and the loss condition number, and parallels classic batch boosting guarantees.
5.1 Smooth Loss Functions: The smooth-loss proof recursively shows each added learner shrinks ensemble regret by a constant fraction plus O(R(T)) ∈ o(T), producing the exponential bound.Strong smoothness, strong convexity, and the weak-learning edge connect loss expansions to gradient norms.
5.1 Smooth Loss Functions: The algorithms’ risk bounds can approach zero for square loss as N increases when the weak learners have a nonzero edge, including when the target lies in span(H).This comparison is made against a potentially stronger target than any single hypothesis in H.
5.2 Non-smooth Loss Functions: The smooth-loss guarantee does not extend to arbitrary non-smooth losses: a constructed sequence can make Algorithm 1’s regret grow linearly with sample size.This failure motivates the residual-projection algorithm.
5.2 Non-smooth Loss Functions: For strongly convex non-smooth losses, residual projection fits each learner to the current subgradient plus accumulated residuals, achieving O(ln N/N) average regret.The rate matches Online Gradient Descent for strongly convex loss functions.

6 EXPERIMENTS

Experiments evaluate SGB’s regret behavior, computational complexity, and test-time performance against batch gradient boosting across several datasets and weak learners.

6.1 Experimental Analysis of Regret Bounds: SGB’s average regret shrinks as regression-tree depth and the number of weak learners increase.Deeper trees are treated as stronger weak learners with larger edge parameters.
6.1 Experimental Analysis of Regret Bounds: More powerful weak learners produce faster convergence as the number of samples increases.Similar behavior was observed with hinge loss on A9A and L1 loss on SLICE.
6.2 Batch Boosting vs. Streaming Boosting: SGB training complexity is O(TN), while batch boosting has complexity O(T_BN^2) under the stated prediction-cost model.The two methods have similar complexity when T_B is approximately 6T/N.
6.2 Batch Boosting vs. Streaming Boosting: SGB can converge with less computation than batch boosting when batch boosting requires many weak learners, although batch boosting is more efficient on A9A.On A9A, the first batch weak learner already performs well, while SGB simultaneously optimizes N=8 learners.
6.2 Batch Boosting vs. Streaming Boosting: Choosing N too large can slow SGB’s convergence, whereas choosing N too small can worsen final performance.The selected N values were approximately the number of weak learners required by batch boosting to converge.
6.2 Batch Boosting vs. Streaming Boosting: SGB’s test errors are competitive with batch gradient boosting across the evaluated datasets.The comparison uses square error for regression and error rate for classification.

7 CONCLUSION

The conclusion presents SGB as an online convex-programming method with theoretical guarantees for smooth and non-smooth losses, while identifying broader gradient-based combinations as an open direction.

SGB achieves exponential regret shrinkage in the number of weak learners for strongly convex and smooth losses.
For non-smooth loss functions, the extended SGB algorithm achieves an O(ln N/N) no-regret rate.
The online weak learning edge definition and square-loss design support boosting weak-learner predictions through gradient descent.
The current method uses gradient descent to combine weak learners, leaving accelerated, mirror, and adaptive gradient updates unexplored.

Supplementary Material for Gradient Boosting on Stochastic Data Streams

The supplementary material develops proof components for the online weak-learning edge and strong-convexity arguments used in the theoretical analysis.

A positive alignment between a target predictor and some normalized weak hypothesis yields a nonzero weak-learning edge.
Hoeffding’s inequality transfers the relevant norm relationships to finite samples with high probability.
Strong convexity supplies inequalities relating a loss value to its minimizer for the subsequent proof steps.
The supplementary proofs establish intermediate propositions by algebraic manipulation, including completing the square and canceling common terms.

B.2 Proof of Theorem 5.1

The proof of Theorem 5.1 links successive weak learners’ regret terms and iterates this relation to obtain the theorem’s convergence guarantee under stochastic sampling.

The analysis assumes each weak learner satisfies the online weak-learning condition.
The proof defines successive regret differences and relates each Δ_i to Δ_{i−1} through the weak-learning edge and the selected step size.
Iterating the recurrence over N weak learners yields geometric decay because the contraction factor lies between zero and one.
The chosen step size produces the theorem’s regret bound through minimization of an auxiliary expression.
For i.i.d. losses and examples, taking expectations converts the online inequality into the stochastic convergence statement.

C Proof of Theorem 5.2

Theorem 5.2 derives a performance guarantee for Alg. 2 by combining weak-learner edge assumptions with intermediate-predictor inequalities, summation, and Jensen’s inequality. The result also extends to the stochastic setting by taking expectations and applying Jensen’s inequality.

Assumptions: The argument assumes bounded loss gradients and weak learners with edge γ and regret R(T) = o(T).These assumptions support the weak-learner comparison used in the proof and the resulting quadratic relation for c.
Proof of Theorem 5.2: The constant c is selected as the positive root of a quadratic equation equivalent to c^2G^2T = (1 − γ)(c + 1)^2G^2T + R(T).This equality supplies the algebraic relation needed in the inductive argument.
Proof of Theorem 5.2: The proof defines intermediate predictors and uses induction on the weak-learner index to establish the required inequalities.The induction starts from Δ_t^0 = 0 and proceeds from learner i to learner i + 1.
Stochastic setting: For stochastic data, the guarantee follows from analogous proof techniques that take expectations and apply Jensen’s inequality to the deterministic relation.The stochastic extension is described as following the approach used for Theorem 5.1.

D Counter Example for Alg. 1

The counterexample shows that Alg. 1 can fail on a non-smooth loss because its weak learners repeatedly select hypotheses that move predictions in only one coordinate. The resulting prediction remains a fixed distance from the optimum, causing regret to grow linearly with time regardless of the number of weak learners.

Counterexample construction: The construction uses the non-smooth loss ℓ_t(y) = 2|y[1]| + |y[2]| and restricts the hypothesis class to coordinate-axis predictors.The loss has four possible subgradients, while the hypothesis class contains only [α, 0]^T and [0, α]^T forms.
Weak-learner behavior: The weak learners always choose hypotheses of the form h(x) = [α, 0]^T, so their combined predictions can move only horizontally.Follow the Leader selects this hypothesis type because it minimizes the accumulated squared loss for the constructed gradients.
Prediction trajectory: Starting from y_0^t = [a, b]^T with a, b > 0, Alg. 1 produces y_N^t = [η, b]^T for some η ∈ R.The second coordinate remains unchanged through all weak-learner updates.
Counterexample outcome: Alg. 1’s regret accumulates linearly as bT, regardless of how many weak learners are used.The output retains second coordinate b while the optimum is [0, 0]^T.

E Details of Implementation

The implementation details specify the losses and prediction structure used for binary and multi-class classification. Regularization preserves strong convexity for the binary loss, while the loss is also shown to be 1/4-smooth under the stated conditions.

Binary classification: The binary loss is twice differentiable with respect to y, and its second derivative is bounded above by 1/4.This curvature bound provides the stated smoothness guarantee.
Binary classification: With bounded outputs |y| ≤ Y, the binary classification loss is 1/(2 + 2 exp(Y))-strongly convex and 1/4-smooth.The smoothness bound follows from the second-derivative inequality, while strong convexity uses the output-boundedness assumption.
Classification losses: The implementation also evaluates hinge loss as another classification loss.
Binary classification: Regularization keeps the binary loss strongly convex even though it is no longer smooth in the unregularized formulation.The implementation uses regularization to avoid overfitting while retaining the required curvature property.
Multi-class classification: For multi-class classification, labels use one-hot vectors in R^k, and the online learner linearly combines weak learners’ vector predictions.Each weak learner maps x_t to a vector prediction, which contributes to the final prediction y.