PaperlayerView exact revision on arXiv

Source-linked AI summary

Boosting with early stopping: Convergence and consistency

Tong Zhang, Bin Yu

arXiv:math/0508276v1math.STstat.TH

TL;DR

Boosting can overfit when run indefinitely, motivating theoretical early-stopping rules for greedy additive estimation. This paper analyzes numerical and statistical convergence over basis-function spans, combines optimization bounds with Rademacher complexity, and establishes consistency, convergence rates, and practical implications for step-size selection.

  • Problem

    The paper addresses unresolved questions about boosting’s numerical convergence, consistency under early stopping, and statistical convergence rates.

    Source: §1 · p. 2

  • Method

    It analyzes greedy boosting over a linear span of basis functions, combining numerical convergence analysis with Rademacher-complexity bounds.

    Source: §1 · p. 3, §3.1 · p. 7

  • Results

    The analysis establishes convergence, general early-stopping consistency, statistical rate bounds, and practical consequences supported by simulations.

    Source: §7 · p. 32

  • Takeaways & Limitations

    Restricted step-sizes and appropriately timed early stopping are central to the paper’s theoretical and practical boosting conclusions.

    Source: §1 · p. 3, §6.5 · p. 30, §7 · p. 32

    The learning-complexity analysis is crude, so the required consistency conditions may be more restrictive than necessary.

    Source: §5.3 · p. 23, §7 · p. 32

Abstract

from arXiv · show

Boosting is one of the most significant advances in machine learning for classification and regression. In its original and computationally flexible version, boosting seeks to minimize empirically a loss function in a greedy fashion. The resulting estimator takes an additive function form and is built iteratively by applying a base estimator (or learner) to updated samples depending on the previous iterations. An unusual regularization technique, early stopping, is employed based on CV or a test set. This paper studies numerical convergence, consistency and statistical rates of convergence of boosting with early stopping, when it is carried out over the linear span of a family of basis functions. For general loss functions, we prove the convergence of boosting's greedy optimization to the infinimum of the loss function over the linear span. Using the numerical convergence result, we find early-stopping strategies under which boosting is shown to be consistent based on i.i.d. samples, and we obtain bounds on the rates of convergence for boosting estimators. Simulation studies are also presented to illustrate the relevance of our theoretical results for providing insights to practical aspects of boosting. As a side product, these results also reveal the importance of restricting the greedy search step-sizes, as known in practice through the work of Friedman and others. Moreover, our results lead to a rigorous proof that for a linearly separable problem, AdaBoost with \epsilon\to0 step-size becomes an L^1-margin maximizer when left to run to convergence.

1. Introduction.

The paper addresses unresolved questions about boosting’s numerical convergence, consistency under early stopping, and convergence rates. It analyzes greedy stagewise optimization over basis-function spans and develops practical implications for step-size and stopping choices.

1. Introduction.

  • The paper studies greedy stagewise minimization over the linear span of basis functions for general loss functions.Boosting constructs additive estimators by repeatedly adding basis functions that reduce empirical risk.Source: §1 · p. 2
  • Boosting’s central unresolved issues are numerical convergence, consistency after early stopping, and statistical convergence rates.These questions are studied because boosting can overfit when run indefinitely.Source: §1 · p. 2
  • Earlier convergence studies treated special losses or restricted convex-hull optimization, leaving numerical convergence speed for standard boosting unresolved.The paper extends the underlying greedy-optimization idea without restricting optimization to the convex hull.Source: §1 · p. 3
  • Small step-sizes play an important role in convergence, providing theoretical support for Friedman’s empirical observation that they usually help boosting.The analysis specifically motivates restricted step-size procedures.Source: §1 · p. 3
  • The paper combines numerical convergence with Rademacher-complexity bounds to derive convergence rates and studies practical implications through simulations.The results also yield a rigorous small-step-size AdaBoost L1-margin result for separable problems.Source: §1 · pp. 3–4

2. Abstract boosting procedure.

The abstract procedure greedily selects a basis function and step-size to approximately reduce a convex objective, with restricted step-size sets controlling the search.

2. Abstract boosting procedure.

  • The procedure minimizes a convex objective over the linear span of a basis family using approximate greedy updates.At each iteration, it selects a basis function and coefficient to reduce the objective.Source: §2 · p. 4
  • The objective’s infimum need not be attained in span(S), and in formulations such as AdaBoost it may be infinite.The theoretical results are formulated to cover both situations.Source: §2 · p. 4
  • Each update chooses ᾱ_k and ḡ_k from Λ_k and S to approximately minimize A(f_k + α_k g_k).The approximation error ε_k is nonnegative and converges to zero.Source: §2 · pp. 4–5
  • The step-size set Λ_k is closed, symmetric, contains zero, and may be restricted to control convergence.The analysis considers both unrestricted Λ_k = R and bounded sets whose supremum tends to zero.Source: §2 · p. 5
  • The initial function, approximation errors, and restricted step-size choices can be sample-independent, with their conditions used in the numerical convergence analysis.The upper bound h_k = sup Λ_k is the key step-size quantity.Source: §2 · p. 5

3. Assumptions and main statistical results.

The paper separates numerical and statistical convergence, then combines them to establish consistency and rate results for early-stopped boosting under explicit loss, basis, and step-size conditions.

3. Assumptions and main statistical results.

  • The analysis combines numerical convergence with statistical convergence to control overfitting and establish consistency for early-stopped boosting.The statistical analysis uses empirical-process tools, especially Rademacher complexity.Source: §3 · p. 5, §3.2 · p. 8, §3.3 · p. 9

3.1. Assumptions for the numerical convergence analysis.

  • The objective is convex, differentiable, and controlled through second-order behavior along basis directions, with normalized basis functions simplifying the assumptions.The auxiliary function ψ is introduced for the convergence proof and does not change the implemented boosting procedure.Source: §3.1 · pp. 6–7

3.2. Assumptions for the statistical convergence analysis.

  • Statistical analysis assumes convex margin-based losses, basis closure under negation, and finite loss Lipschitz constants, with Rademacher complexity measuring basis-class complexity.The setup applies to classification and can also support regression analysis.Source: §3.2 · pp. 8–9

3.3. Main statistical results.

  • Consistency holds when sample-independent iteration and complexity sequences diverge while γ_φ(β_m)β_m R_m(S) tends to zero, provided stopping meets the theorem’s iteration and norm conditions.The result states Q(f̂_k̂) converges to inf_{f∈span(S)} Q(f).Source: §3.3 · p. 9
  • For constant-step-size logistic boosting, Theorem 3.2 gives a worst-case rate under h_0(m) ≤ m^-1/2 and k(m) = β_m/h_0(m) iterations.The bound is independent of h_0(m) under the stated restriction.Source: §3.3 · p. 10
  • The logistic rate is E_Zm Q(f̂_k̂) ≤ Q(f̄) + O(∥f̄∥_1^1/2 m^-1/4), and convergence slows as the target complexity ∥f̄∥_1 increases.The paper notes that these rate results are not necessarily tight.Source: §3.3 · p. 10

4. Preparatory results.

The preparatory results establish numerical convergence for greedy boosting, control statistical error through Rademacher complexity, and explain how restricted step-sizes support convergence and later consistency analysis.

4.2. Uniform convergence.

  • Uniform convergence is bounded using Rademacher complexity, whose dependence on the boosting iterate is controlled through the 1-norm of the function class.The approach is simple enough to support early-stopping consistency and rate results, although it may not measure the smaller space actually searched by boosting.Source: §4 · p. 11, §4.2 · pp. 16–17

4.1. Numerical convergence analysis.

  • The quantitative convergence bound balances the reference function’s loss against its 1-norm and accumulated step-size, with a closer-to-optimal initialization improving the bound.This reference-function comparison supplies numerical speed information while avoiding direct comparison with an unattained optimum.Source: §4.1 · p. 13
  • lim k→∞A(fk) = inf f∈span(S)A(f) under cumulative-step and approximation conditions, extending greedy optimization convergence beyond special losses.The analysis compares iterates with arbitrary reference functions in span(S), allowing convergence even when the infimum is not attained or is −∞.Source: §4.1 · pp. 13–14
  • Restricted step-sizes prevent large oscillations, while divergent cumulative step-size ensures that the iterates can cover span(S).For constant step-size boosting, convergence requires kh0 →∞ and kh0^2 →0 as the step-size decreases.Source: §4.1 · p. 15
  • In separable classification, AdaBoost with infinitesimal step-size is rigorously shown to become an L1-margin maximizer at convergence.The result connects the limiting behavior of AdaBoost with maximum-margin objectives associated with support vector machines.Source: §4.1 · p. 16

4.3. Estimating Rademacher complexity.

  • The Rademacher bound assumes a finite entropy integral; if it diverges, integration can start at ε0 > 0, but the dependence of Rm(F) on m may be slower than 1/√m.Source: §4.3 · p. 18
  • The complexity estimates apply to basis families such as two-level neural networks and restricted-size tree functions through finite VC-dimension and covering-number conditions.For the relevant classes, span(S) can also be dense in C(U) under the stated compact-domain conditions.Source: §4.3 · pp. 18–19

5. Consistency and rates of convergence with early stopping.

The paper combines numerical and statistical error decompositions to obtain consistency and convergence rates for restricted-step-size boosting with suitable early stopping. Under density conditions, the resulting classifiers achieve optimal classification loss, while the rate bounds are explicitly acknowledged as potentially loose.

5. Consistency and rates of convergence with early stopping.

  • Restricted-step-size boosting is analyzed because it is preferred in practice, whereas unrestricted-step-size consistency is not developed in the paper.The stopping point may be sample-independent or sample-dependent provided the estimator’s 1-norm remains within the prescribed βm bound.Source: §5 · p. 19, §5.1 · p. 20, §5.2 · p. 23

5.1. General decomposition.

  • The general decomposition separates estimation error, fixed-reference sampling error, and empirical optimization error, so consistency requires all three terms to vanish.The fixed-reference term has O(1/√m) behavior, while the optimization term is controlled by the numerical convergence analysis.Source: §5.2 · p. 20, §5.1 · p. 20

5.2. Consistency with restricted step-size boosting.

  • The required βm growth depends on the loss: o(m1/2) for logistic, o(log m) for exponential, and o(m1/4) for least-squares and modified least-squares losses.These conditions translate the Rademacher-based stopping requirement into loss-specific bounds on the estimator’s 1-norm.Source: §5.2 · p. 22
  • Q( ˆfkm) = inf f∈span(S)Q(f) and L( ˆfkm) = L∗ under sample-independent stopping, complexity assumptions, and suitable cumulative step-size growth.If span(S) is dense in C(U), the classification result holds for all Borel measures on U × {−1,1}.Source: §5.2 · pp. 21–22

5.3. Some bounds on the rate of convergence.

  • The rate analysis targets functions approximable in span(S) with small 1-norm and combines numerical convergence with statistical convergence estimates.The resulting bounds can be specialized to choices such as logistic loss and constant step-size boosting.Source: §5.2 · p. 21, §5.3 · pp. 23–24
  • The reported rate bounds are not necessarily optimal because the 1-norm, numerical convergence, and Rademacher-complexity analyses may each be loose.The paper uses these relatively simple, worst-case tools rather than more sophisticated complexity measures or tighter empirical-process bounds.Source: §5.3 · p. 23
  • The bounds are a priori and data-independent, despite data-dependent choices of β potentially yielding tighter bounds.The paper deliberately focuses on worst-case upper bounds without using the observed sample to refine them.Source: §5.3 · p. 23

6. Experiments.

Experiments use controlled one-dimensional synthetic classification problems to examine early stopping, total step-size, sample size, consistency, and target complexity. The results broadly support the theoretical analysis while showing that convex-loss and classification-error behavior can differ.

6.1. Experimental setup.

  • Synthetic experiments use uniformly distributed X, a complexity-controlled triangular target with Bayes error 0.25, one-dimensional stumps, and least-squares loss.The target complexity is controlled by integer d, and the experiments restrict step-sizes to satisfy the theoretical convergence and consistency conditions.Source: §6.1 · pp. 25–26

6.2. Early stopping and overfitting.

  • After 32 iterations the estimator roughly matches the target shape, whereas after 1024 iterations it appears random, indicating overfitting.Predictive performance worsens with excessive iterations even though training error continues to decrease.Source: §6.2 · p. 27

6.3. Early stopping and total step-size.

  • Predictive behavior is more comparable across boosting configurations when stopping is measured by total step-size rather than iteration count.Restricted and unrestricted step-size methods show similar behavior as a function of total step-size, supporting the theoretical parameterization.Source: §6.3 · p. 28

6.4. The effect of sample-size on early stopping.

  • As sample size increases, the optimal stopping point rises, the predictive curve flattens, and aggressive early stopping becomes less necessary.The effect is clearer for excessive convex loss than for classification error, revealing a discrepancy between the two criteria.Source: §6.4 · p. 29

6.5. Early stopping and consistency.

  • Cross-validation is more reliable than the theoretically motivated ρ-strategies, while all examined strategies show convergence toward consistency.Cross-validation stops later than the ρ-strategies, suggesting that the theoretical conditions are more restrictive than necessary.Source: §6.5 · pp. 30–31

6.6. The effect of target function complexity on early stopping.

  • Increasing target complexity raises the required stopping total step-size and worsens predictive performance, especially for excessive convex loss.The analysis measures approximation difficulty through the target function’s 1-norm, while classification error and convex loss do not behave identically.Source: §6.6 · p. 31

7. Conclusion.

The conclusion combines numerical convergence and learning-complexity analyses to establish consistency and rate results for greedy boosting with early stopping. Experiments show observable consequences of the theory, while the authors caution that their learning-complexity bounds are crude.

7. Conclusion.

  • Averaging-based analysis establishes numerical convergence conditions and convergence-speed estimates for the general boosting algorithm.The results generalize prior analyses of matching pursuit and AdaBoost.Source: §7 · p. 32
  • Combining numerical convergence with Rademacher-complexity bounds yields general early-stopping criteria guaranteeing consistency and, for selected settings, statistical convergence-rate bounds.The criteria apply to greedy boosting procedures for various loss functions.Source: §7 · p. 32
  • The learning-complexity analysis is crude, so the consistency conditions may be more restrictive than necessary.This is the principal scope qualification attached to the theoretical consistency strategy.Source: §7 · p. 32
  • The experiments indicate that theoretical quantities produce observable practical consequences for boosting with early stopping.The authors present this as evidence that the theory can provide useful insights into applications.Source: §7 · p. 32

A.1. Loss function examples.

This appendix subsection lists commonly used convex loss functions satisfying the paper’s assumption. It introduces a boundedness property for the associated auxiliary quantity.

A.1. Loss function examples.

  • Typical boosting loss functions in the appendix are convex and satisfy Assumption 3.1.The listed losses have a constant M such that sup_a M(a) ≤ M.Source: §A.1 · pp. 32–33
  • The appendix presents the traditional statistical loss function in natural-log form.The supplied passage introduces its formula without specifying further properties here.Source: §A.1.1 · p. 33

A.1.1. Logistic regression.

The logistic-regression subsection specifies a basis-function condition and notes that the corresponding loss is used by AdaBoost. It also states that the relevant objective is convex differentiable.

A.1.1. Logistic regression.

  • The subsection assumes that the basis functions satisfy a stated condition before deriving properties of the objective.The supplied passages do not reproduce the condition itself.Source: §A.1.1 · p. 33
  • The objective A(f) is convex differentiable under the subsection’s setup.The passage introduces this property as a verifiable consequence of the assumptions.Source: §A.1.1 · p. 33
  • The loss function described is used in AdaBoost, the original boosting procedure for classification.The supplied passage identifies its application but does not include the full displayed formula.Source: §A.1.2 · p. 33

A.1.2. Exponential loss.

This subsection specifies the exponential-loss boosting formulation and its convex-differentiability properties under the stated basis-function conditions.

A.1.2. Exponential loss.

  • The exponential-loss objective is treated as a convex differentiable function of the additive estimator.Source: §A.1.2 · p. 33
  • The subsection connects least-squares formulations, used in regression and classification, with a greedy boosting-like procedure first proposed in signal processing and called matching pursuit.Source: §A.1.3 · p. 33

A.1.3. Least squares.

This subsection introduces least-squares boosting and imposes a weaker basis-function condition while retaining bounded second derivatives of the objective.

A.1.3. Least squares.

  • Least-squares boosting uses a convex differentiable objective whose second derivative is bounded under the stated basis-function condition.Source: §A.1.3 · p. 33
  • The least-squares formulation is used for regression and classification and is connected to matching pursuit.Source: §A.1.4 · p. 34

A.1.4. Modified least squares.

The appendix extends the loss and convergence analysis across modified least-squares and p-norm settings, establishes numerical convergence under step-size conditions, and connects small-step AdaBoost to L1-margin maximization. It also identifies important limitations for unrestricted steps and nonsmooth losses.

A.1.4. Modified least squares.

  • The appendix’s modified least-squares analysis imposes classification-specific conditions and bounds the objective’s second derivative.Source: §A.1.4 · p. 34
  • Modified p-norm losses require p ≥2, while p∈(1,2) needs separate analysis because the loss is not second-order differentiable at zero.The current technique cannot directly handle hinge loss because its first derivative is discontinuous, although smooth approximations may be analyzed.Source: §A.1.4 · pp. 34–35

A.2. Numerical convergence proofs.

  • Under restricted step sizes, the numerical proofs bound objective decrease through convexity, Taylor expansion, weighted averaging, and recursive one-step inequalities.The analysis compares each iterate with an arbitrary reference function in the span and tracks coefficient 1-norm growth.Source: §A.2 · pp. 35–38

A.3. Discussion of step-size.

  • With exact minimization and unrestricted steps, convergence to inf_f∈span(S) A(f) follows when the required cumulative step-size condition holds.The result applies even when the optimum is unattained or the infimum is unbounded below, as covered by the general formulation.Source: §A.3 · pp. 38–39
  • The unrestricted-step result extends prior exponential-loss convergence analysis, but still constrains the probability measures generating (X,Y).For general problems the cumulative condition may fail, and convergence cannot be proved; logistic regression presents an additional difficulty from near-linear loss behavior at negative infinity.Source: §A.3 · pp. 40–41

A.4. The relationship of AdaBoost and L1-margin maximization.

  • AdaBoost with step size h approaching zero and continued iterations approaches an L1 maximum-margin separator on linearly separable problems.The normalized estimator achieves a margin within h of the maximum possible before taking the limit.Source: §A.4 · p. 42
Loading math/0508276v1…