PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Gradient Boosting

Alina Beygelzimer, Elad Hazan, Satyen Kale, Haipeng Luo

arXiv:1506.04820v2cs.LG

TL;DR

The paper addresses the lack of theoretical foundations for regression boosting in online learning. It models weak learners as online linear-loss learners and constructs boosting reductions to richer classes. The main algorithms target the span and convex hull of the base class, with theoretical guarantees and empirical accuracy improvements, especially for weak base learners.

  • Problem

    Regression boosting had not been extended to online learning with theoretical guarantees, despite the need for online methods on datasets too large for batch training.

    Source: §1 · p. 1

  • Method

    The paper converts an online learner for a base class under linear losses into learners for the span and convex hull of that class under convex losses.

    Source: §1 · p. 2, §2 · p. 3, §3 · p. 6

  • Results

    The algorithms provide theoretical convergence guarantees, prove optimality for the convex-hull method, and improve prediction accuracy in experiments, especially with weaker base learners.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    Online boosting can strengthen weak regression learners in practice and theory, with larger empirical improvements for weaker base learners.

    Source: §7 · p. 12, §6 · p. 12

    The one-dimensional regression analysis assumes true labels and base-function predictions lie in [−1, 1].

    Source: §3.1 · p. 7

Abstract

from arXiv · show

We extend the theory of boosting for regression problems to the online learning setting. Generalizing from the batch setting for boosting, the notion of a weak learning algorithm is modeled as an online learning algorithm with linear loss functions that competes with a base class of regression functions, while a strong learning algorithm is an online learning algorithm with convex loss functions that competes with a larger class of regression functions. Our main result is an online gradient boosting algorithm which converts a weak online learning algorithm into a strong one where the larger class of functions is the linear span of the base class. We also give a simpler boosting algorithm that converts a weak online learning algorithm into a strong one where the larger class of functions is the convex hull of the base class, and prove its optimality.

1 Introduction

The paper extends regression boosting from batch to online learning, addressing the lack of theoretical guarantees for online regression boosting. It develops span- and convex-hull-based algorithms with theoretical and empirical support.

  • Online boosting is especially motivated by datasets too large for batch training, where one-pass online learning is useful.Prior online boosting theory primarily addressed classification rather than regression [4] [2].Source: §1 · p. 1
  • Online regression boosting had lacked theoretical guarantees, motivating a rigorous online formulation and extension of gradient boosting.Source: §1 · p. 1
  • The main algorithm converts an online linear learner for a base class into an online learner competing with any linear combination of base functions.This is the online analogue of Zhang and Yu’s batch boosting algorithm [24].Source: §1 · p. 2
  • A simpler algorithm competes with the best convex combination of base functions and achieves an optimal regret bound up to constant factors.The method is analyzed along the lines of the Frank-Wolfe algorithm [8].Source: §1 · p. 2
  • Experiments show prediction improvements over different base learners, with greater gains for weaker learners.Source: §1 · p. 2

2 Setup

The setup models online boosting as a reduction from a weak learner handling linear losses to a strong learner handling convex losses over a richer function class. It formalizes online regret, comparator classes, and the assumptions needed for this reduction.

  • In each round, an adversary presents an example and loss function before the learner predicts and incurs the resulting loss.The learner’s regret compares cumulative loss with that of comparator functions in its class.Source: §2 · pp. 2–3
  • Online boosting gives an algorithm with access to a base learner A for F and linear losses, producing a learner for a richer class F′ and convex losses.The reduction uses at most N calls to copies of A per iteration, analogous to the number of batch boosting stages.Source: §2 · p. 3
  • The function class is assumed symmetric, containing negations of its functions and the constant zero function.This assumption is stated for the reference class F.Source: §2 · p. 4
  • The richer comparator classes are the convex hull CH(F) and the span span(F), with span comparators measured using an l1-type coefficient norm.Uniform regret over the unbounded span is unavailable, so regret is specified for individual comparators.Source: §2 · p. 4
  • The base class is online learnable for 1-Lipschitz linear losses, while the richer loss class contains regular convex losses with bounded subgradients and smoothness parameters.Source: §2 · p. 4

3 Online Boosting Algorithms

The online gradient boosting algorithms maintain multiple copies of a weak learner and update them using loss information to compete with richer function classes. The span algorithm has vanishing average regret under increasing stages and data, while the convex-hull algorithm is optimal in its dependence on the number of stages.

Online Gradient Boosting for span(F)

  • Algorithm 1 maintains N copies of the base learner and competes with span(F) under convex losses.Its construction combines base predictions through staged updates, projections, shrinkage, and scaled linearized losses.Source: §3 · pp. 4–5
  • With suitable η, Algorithm 1’s average regret converges to zero as N and T grow, and the required increase in boosting stages is necessary by a lower bound.Source: §3 · p. 5

Online Gradient Boosting for CH(F)

  • Algorithm 2 uses a simpler convex combination of base predictions to compete with CH(F), avoiding the projections and shrinkage used by Algorithm 1.Its analysis follows the Frank-Wolfe method.Source: §3 · pp. 5–6
  • The convex-hull algorithm’s dependence on N is optimal up to constant factors, while improving its dependence on the base learner’s regret requires additional assumptions.Source: §3 · p. 6

The parameters for several basic loss functions

  • For one-dimensional regression, the analysis assumes labels and base predictions lie in [−1, 1] and computes loss-specific regularity parameters.For linear loss, the resulting parameters include L_b = 1, β_b = 0, ϵ_b = 1, and B = ηN.Source: §3.1 · p. 7

4 Analysis

The analysis establishes regret guarantees for boosting against both the convex hull and span of the base functions, and proves optimality for the convex-hull setting.

4.1 Competing with convex combinations of the base functions

  • The convex-hull analysis bounds the boosted learner’s regret by recursively controlling the excess loss across its N boosting stages.The induction yields a bound scaling with N, the smoothness and boundedness parameters, and the base learner’s regret.Source: §4.1 · pp. 7–8
  • The convex-hull boosting algorithm has a regret bound whose dependence on the number N of base-learner calls is optimal up to constant factors.The lower-bound construction uses one-dimensional regression with squared loss and extends to D-bounded classes and β-smooth losses.Source: §4.1 · pp. 8–9
  • The lower-bound proof constructs two nearby label distributions that a booster with at most N base-learner calls cannot reliably distinguish, forcing regret of order βD^2T/N.The contradiction follows by comparing the booster’s behavior under the two distributions and bounding their total variation distance.Source: §4.1 · p. 9

4.2 Competing with the span of the base functions

  • For the span of the base functions, Algorithm 1 is analyzed by representing a comparator as a weighted combination and applying online gradient descent to its coefficient updates.The proof combines coefficient-update control with the base learners’ regret bounds and projection analysis.Source: §4.2 · p. 10
  • The span analysis controls projection-induced excess loss and iterates the resulting inequality across boosting stages to complete the regret guarantee.When the projection is inactive, it contributes no excess loss; otherwise, the parameter choice bounds that contribution.Source: §4.2 · pp. 10–11

5 Variants of the boosting algorithms

The paper presents practical variants that accommodate greedy-fitting base learners and improve the span algorithm’s regret through scaling of the base function class.

5.1 Greedy fitting

  • The algorithms can be modified to use base learners that perform greedy fitting rather than the analysis-friendly online linear-learning interface.In the online version, the learner receives an offset before predicting and then incurs loss under the round’s loss function.Source: §5 · p. 11, §5.1 · p. 11

5.2 Improving the regret bound via scaling

  • Scaling the base class by λ preserves online linear learnability while scaling the base learner’s regret by λ.The scaled learner λA is obtained by multiplying the original predictions by λ.Source: §5.2 · p. 11
  • A suitable λ ≥ 1 can improve Algorithm 1’s regret because the comparator’s induced 1-norm decreases, although the parameter B′ increases and worsens another term.The paper notes that the norm improvement can outweigh the degradation in many situations, producing an improved overall regret bound.Source: §5.2 · p. 11

5.3 Batch specialization

  • The boosting technique also transfers to batch learning, where coefficient-scaling variables yield convergence bounds analogous to those of Zhang and Yu [24].The same specialization provides better convergence rates than previous work in the batch setting.Source: §5 · p. 11, §5.3 · p. 12

6 Experimental Results

Experiments on 14 public datasets test both online boosting algorithms with three base learners, showing practical accuracy gains that are largest for the weakest learner.

Experimental setup

  • The evaluation averages and takes medians of relative squared-loss improvements over the respective base learner across 14 regression and classification datasets.Learning rates, numbers of weak learners, and Algorithm 1’s step size were tuned using progressive validation on half of each dataset, with results reported on the other half.Source: §6 · p. 12

Overall results

  • The reported results compare the average and median relative improvements of Algorithms 1 and 2 for each base-learner type.The table summarizes both aggregate measures rather than reporting only a single dataset outcome.Source: §6 · p. 12

7 Conclusions and Future Work

The paper establishes online boosting theory for regression, provides guaranteed algorithms for the span and convex hull of a base class, and validates practical accuracy improvements.

Contributions

  • The paper generalizes boosting theory to online regression and provides online boosting algorithms with theoretical convergence guarantees.Its technique also improves convergence guarantees for batch boosting algorithms.Source: §7 · p. 12

Empirical conclusion

  • Experiments show improved prediction accuracy over commonly used base learners, with larger gains for weaker base learners.The conclusion identifies whether span-boosting optimality can be characterized as the main remaining open question.Source: §7 · p. 12

Future work

  • The optimality of the algorithm competing with the span of the base functions remains unresolved, unlike the convex-hull algorithm’s established optimality.The paper explicitly contrasts this open question with its proof of optimality for the convex-hull setting.Source: §7 · p. 12

Supplementary material for “Online Gradient Boosting”

The supplementary material develops variants of the boosting algorithms, including greedy fitting, scaled base functions, and an application to faster batch-boosting convergence.

A.1 Fitting to actual loss functions

The analysis extends boosting to base learners that fit the actual loss functions using offsets, under boundedness, Lipschitz, and smoothness assumptions.

  • Greedy fitting gives the base learner an offset y′_t and a fixed step size α before it produces a prediction and receives the loss function.Source: §A.1 · p. 15
  • The analysis assumes bounded offsets and predictions, with loss functions that are Lipschitz and smooth on the resulting bounded domain.Source: §A.1 · p. 15
  • The resulting regret is sublinear in T whenever the base learner’s regret R(T) is sublinear.Source: §A.1 · p. 15
  • When R(T) scales linearly with α, choosing α using R′(T) yields a better regret bound.Source: §A.1 · p. 15
  • The boosting algorithms retain multiple copies of the base learner and pass the offset y′_t through modified update lines.Source: §A.1 · p. 16

A.2 Improving the regret bound via scaling

Scaling the base function class can improve the regret bound by trading better higher-order terms against worse lower-order and parameter-dependent terms.

  • Scaling F by λ produces λA over λF, with the base learner’s regret scaled by λ.Source: §A.2 · p. 16
  • Using λA in Algorithm 1 gives an online learner for span(F) with the stated regret bound for every f in span(F).Source: §A.2 · p. 16
  • Scaling can increase B′, which correspondingly increases the smoothness and Lipschitz parameters βB′ and LB′.Source: §A.2 · p. 16
  • Larger λ can improve higher-order regret terms when B′ equals B or grows slowly, such as logarithmically in λ.Source: §A.2 · p. 16
  • The overall bound improves when λ is chosen large enough to balance higher-order gains against the worse lower-order term involving λR(T).Source: §A.2 · p. 16

A.3 Improvements for batch boosting

The paper’s boosting technique also accelerates batch boosting: under the compared setup, its convergence depends logarithmically on the target accuracy rather than inversely on it.

  • The batch analysis minimizes a β-smooth convex functional over span(F), using a base learner that selects g in F to minimize ℓ(f + ηg).Source: §A.3 · pp. 16–17
  • The algorithm initializes f_0 = 0 and updates successive functions using step sizes η_i and greedy fitting.Source: §A.3 · p. 17
  • For the corresponding summed terms, the proposed algorithm has log(1/ǫ) dependence, while Zhang and Yu [24] have 1/ǫ dependence.Source: §A.3 · p. 17
  • The proposed batch algorithm converges exponentially faster than Zhang and Yu’s algorithm [24] under the stated comparison setup.Source: §A.3 · pp. 16–17

B Description of Data Sets and Detailed Experimental Results

The experiments use datasets from the UCI repository and KDD Cup challenges, reporting online squared losses for a baseline and two algorithms. The table covers multiple datasets with varying feature counts and per-example sparsity, but the supplied rows do not identify column semantics beyond the headers.

Description of Data Sets

Detailed Experimental Results

Loading 1506.04820v2…