PaperlayerView exact revision on arXiv

Source-linked AI summary

Margins, Shrinkage, and Boosting

Matus Telgarsky

arXiv:1303.4172v1cs.LGstat.ML

TL;DR

AdaBoost can favor good margins but does not attain maximum margins on general instances, motivating methods with margin guarantees. This manuscript shows that scaling back step sizes can approximate maximum-margin choices and provides guarantees for shrinkage and other step sizes, while noting that the logistic-loss bounds may not represent algorithm behavior accurately.

  • Problem

    AdaBoost does not attain maximum margins on general instances, and the connection between margins and boosting efficacy remains unclear.

    Source: §1 · p. 1, §5 · p. 8

  • Method

    The manuscript analyzes four step-size choices for boosting and shows how scaling back steps approximates the path of constrained optima.

    Source: §1 · p. 1

  • Results

    More regularized step choices have improved margin bounds, and straightforward choices achieve margins at rates matching explicitly margin-maximizing boosting methods.

    Source: §1 · p. 1, §3.3 · p. 7

  • Takeaways & Limitations

    The results provide theoretical guarantees for Friedman's shrinkage procedure, an effective practice adopted in gradient boosting.

    Source: §1 · p. 1

    The authors say their logistic-loss treatment yields bounds that do not accurately represent algorithm behavior, and it is unclear how to improve that treatment.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

This manuscript shows that AdaBoost and its immediate variants can produce approximate maximum margin classifiers simply by scaling step size choices with a fixed small constant. In this way, when the unscaled step size is an optimal choice, these results provide guarantees for Friedman's empirically successful "shrinkage" procedure for gradient boosting (Friedman, 2000). Guarantees are also provided for a variety of other step sizes, affirming the intuition that increasingly regularized line searches provide improved margin guarantees. The results hold for the exponential loss and similar losses, most notably the logistic loss.

1. Introduction

AdaBoost can favor good margins, but it does not attain maximum margins on general instances; this work shows that scaling back step sizes can more finely approximate constrained optima. It studies four step-size choices and provides theoretical guarantees for shrinkage, a procedure already used in practice.

1. Introduction

  • Margin-based explanations of boosting connect good margins with improved generalization, while AdaBoost does not attain maximum margins on general instances.This led to methods designed to guarantee maximum margins.Source: §1 · p. 1
  • Scaling back step sizes makes boosting iterates approximate the path of constrained optima and can achieve margin maximization.The manuscript studies four step-size choices and reports improved bounds for more regularized choices, with rates matching straightforward step choices to explicitly margin-maximizing boosting methods.Source: §1 · p. 1
  • Friedman (2000) proposed shrinkage, a step-size scaling practice adopted in practice; this manuscript supplies theoretical guarantees for it.The manuscript also studies step sizes beyond the optimal line search.Source: §1 · p. 1

1.1. Outline

  • The analysis covers separable instances and general, potentially nonseparable instances, including a separable sub-component under a certain decomposition.For both settings, the outline reports convergence-rate guarantees; for the general setting, it also describes margins on the separable sub-component.Source: §1.1 · p. 2

1.2. Related Work

  • Earlier regularized-line-search work addressed consistency or margin maximization without rates, whereas this manuscript gives rates for more stringent step sizes and studies an existing method with minor algorithmic changes.The manuscript is concerned with convergence of empirical quantities.Source: §1.2 · p. 2

2. Algorithms and Notation

The manuscript formulates boosting over a finite set of weak-learner responses, defines a family of losses comparable to the exponential loss, and presents an iterative algorithm. It studies four step-size choices, including scaled line searches and AdaBoost's step.

2. Algorithms and Notation

  • The sample responses of the finite effective weak-learner set form a matrix A, and the best achievable margin γ is also the weak learning rate.Positive γ means the instance is separable under the classical weak learning assumption.Source: §2 · pp. 2–3

2.1. The Family of Loss Functions

  • The convergence analysis uses relative curvature: the Hessian need only be sufficiently large relative to the gap between the current objective and its optimum.The text notes that exponential loss is a fixed point of differentiation, making it well suited to this analysis.Source: §2.1 · p. 3
  • The loss family L requires twice-continuously differentiable, strictly convex losses whose derivatives remain comparable to the exponential loss by a finite constant.Both exponential and logistic losses belong to L∞, the subclass whose comparison constant tends to 1 as its argument tends to negative infinity.Source: §2.1 · p. 3

2.2. Algorithm

  • Each iteration chooses a weak learner by column and updates its weight by a line-search step; the objective is the average loss over the sample responses.The primal objective minimizes L(Aλ) over λ in R^n.Source: §2.1 · p. 3
  • The parameter C_t bounds the loss-dependent comparison constant over candidates considered at iteration t, since each line search guarantees descent.For the exponential loss, the quadratic-upper-bound step is algorithmically convenient because C_t equals 1.Source: §2.2 · pp. 3–4
  • The shrinkage parameter ν lies in (0, 1], and more regularized choices scale back the line-search step.The quadratic-upper-bound and Wolfe step sizes are related under the stated assumptions.Source: §2.2 · p. 4
  • The four choices range from a quadratic upper-bound step and Wolfe line search to AdaBoost's step and the fully minimizing line search.The Wolfe step avoids needing C_t and uses function and gradient evaluations; the AdaBoost step yields rates only for exponential loss, while the fully minimizing step with shrinkage was suggested for logistic loss.Source: §2.2 · p. 4

3. The Separable Case

In the separable setting, the paper studies empirical-risk convergence and margin guarantees for several boosting step sizes. Shrinkage preserves the basic convergence rate while more regularized choices can improve the rate of convergence to a good margin.

3.1. Convergence of Empirical Risk

  • For any loss in L and arbitrary shrinkage, the line-search methods have the same basic empirical-risk convergence rate as AdaBoost.The convergence analysis describes a trade-off: about 1/ν steps that are ν times as long as the original can match its progress.Source: §3.1 · p. 4

3.2. Margin Maximization

  • More regularized step sizes converge faster to a good margin, but unconstrained step sizes have only asymptotic margin guarantees.The margin results require ℓ∈L∞; the paper notes that strict convexity matters, since hinge-loss minimization can stop at zero error with poor margins.Source: §3.2 · p. 5

3.3. Discussion

  • With Wolfe steps and ν = 1/2, 12 ln(m)/γ^2 iterations suffice to reach margin γ/2; more generally, margin γ(1 − ν) takes 8 ln(m)/(νγ)^2 iterations.The discussion compares the latter guarantee with 32 ln(m)/ϵ^2 iterations for Shalev-Shwartz & Singer (2008), but says the comparison is unfair because the shrinkage choice requires knowledge of γ.Source: §3.3 · p. 6
  • Figure 2 presents a sanity check reporting that shrinkage leads to margin maximization.Figure 3 demonstrates that the Wolfe search (with ℓ= exp) is effective, but demanding higher accuracy comes at a price.Source: Figure 2 · p. 7, §3.3 · p. 7
  • The logistic-loss test performs well despite the bounds being loose and suggesting a startup cost.The discussion cautions that one matrix example is not very indicative.Source: §3.3 · p. 7

4. The General Case

For potentially nonseparable boosting problems, the paper decomposes examples into a hard core and an easy, separable complement. It gives empirical-risk and margin guarantees, but the margin result is limited to positive margins off the hard core and supplies neither rates nor maximality.

4. The General Case

  • The hard core H(A) is unique, and its complement is separable and can be solved without affecting the hard core.The decomposition separates examples where positive margins on some force negative margins on others from those that can be solved independently.Source: §4 · p. 7
  • For nonseparable instances, the method has an empirical-risk convergence guarantee, with an improved rate when the instance is separable or the minimizer is attainable.The supplied theorem fragments state that the improved rate applies when γ > 0 or |H(A)| = m.Source: §4 · p. 8
  • When the hard core is nonempty but not all examples, the method eventually attains some positive margin on every example outside it.The result does not establish maximal margins or give rates for attaining these positive margins.Source: §4 · p. 8
  • Unlike soft-margin boosting, this approach uses a fixed, data-dependent hard core, and its margins over that core depend on the loss function.The paper describes its nonseparable margin analysis as incomplete: it gives no rates and does not identify exactly which positive margins are attained.Source: §4 · p. 8

5. Discussion

The discussion leaves open how directly margins explain boosting efficacy and how tightly the logistic-loss bounds characterize performance. It also reports a shrinkage threshold in an example: full step size misses the maximum margin, while 1/2 and smaller reach it.

5. Discussion

  • The paper leaves open how directly margins correlate with good boosting algorithms, despite their intuitive theoretical role.It cites Reyzin & Schapire (2006).Source: §5 · p. 8
  • The logistic-loss bounds are not tight, leaving open whether new techniques can characterize that loss more sharply.Source: §5 · p. 8
  • In the tested example, shrinkage 1 misses the maximum margin, while 1/2 and smaller reach it; experimentation places the threshold near 0.92.The paper suggests smaller steps may dodge bad attractors, citing Rudin et al. (2004; 2007).Source: §5 · p. 8

A. Deferred Material from Section 2

The deferred material develops technical bounds used in the paper’s analysis of exponential and logistic losses.

A. Deferred Material from Section 2

B.1. Deferred Material from Section 3.1

The deferred proofs derive convergence bounds by establishing per-step guarantees and iterating them across updates.

B.1. Deferred Material from Section 3.1

  • The stated bounds are extended from t0 to t by applying them t − t0 times and using that C does not increase.The proof applies this iteration scheme to the relevant bounds.Source: §B.1 · p. 11
  • The proof of Lemma 3.3 applies a nearly identical Wolfe line-search guarantee with specified constants and a sublevel-set ratio.Source: §B.1 · p. 11
  • The proof of Lemma 3.4 follows by selecting τ = 0 in the second bound of Lemma B.1.Source: §B.1 · p. 11

B.2. Deferred Material from Section 3.2

The deferred results establish margin guarantees under several step-size choices, including Wolfe and optimal step sizes. They give asymptotic bounds and, for the exponential-loss specialization, a lower bound on the margin.

B.2. Deferred Material from Section 3.2

  • Wolfe-condition step sizes have a lower bound that can be applied recursively from t_0 to obtain the stated bound.The proof applies the first Wolfe condition t − t_0 times.Source: §B.2 · p. 12
  • When θ < Υ_ν(γ), the bound in Lemma 3.8 is eventually less than 1/m, yielding its stated result.The proof chooses ν sufficiently small and then takes t sufficiently large.Source: §B.2 · p. 13
  • Lemma 3.9 shows its bound is eventually less than 1, yielding the stated result for the optimal step size.Its proof invokes Lemma B.7 and replaces γ_i by γ using Lemma B.6.Source: §B.2 · pp. 13–14
  • For the exponential-loss specialization, M(Aλ_t) ≥ θ for the choices specified in Proposition 3.10.The proof uses θ < γ/(2 + γ).Source: §B.2 · p. 14
  • Lemmas 3.8 and 3.9 already state their results in the desired asymptotic form.Source: §B.2 · p. 14
  • For losses in L∞, the bounds in Lemmas 3.6 and 3.7 can be made sufficiently tight by choosing t_0 large, ν small, and t_ν large.The passage states that C t_0 can thereby be made arbitrarily close to 1.Source: §B.2 · p. 14

B.2.1. The Quantity Υν

The section establishes bounds and monotonicity properties for Υ_ν. It also identifies the limit as ν tends to zero and relates Υ_ν to the ν = 1 case.

B.2.1. The Quantity Υν

  • For ν = 1, the quantity Υ_1(γ) and the bounds γ/2 ≤ Υ_1(γ) ≤ γ have been studied in prior work.The passage names Rätsch & Warmuth (2005) and Schapire & Freund (2012).Source: §B.2.1 · pp. 14–15
  • Υ_ν(γ) ≥ Υ_1(γ), and γ/2 ≤ Υ_1(γ) ≤ γ, so Υ_ν(γ) ≥ γ/2.Source: §B.2.1 · p. 15
  • As ν tends to zero, Υ_ν(γ) converges to (1 + γ) ln(1 + γ) + (1 − γ) ln(1 − γ).Source: §B.2.1 · p. 15
  • The map introduced in Lemma B.6 is nonincreasing over [θ, 1], and its stated threshold condition is characterized by θ < Υ_ν(γ).Source: §B.2.1 · p. 16

B.2.2. Miscellaneous Technical Material

The deferred technical proof uses first-order conditions for the optimal step size to derive inequalities, then applies the resulting bounds under step-size scaling.

B.2.2. Miscellaneous Technical Material

  • First-order conditions for the optimal step size are rearranged to derive inequalities, including a corresponding lower-bound argument.The proof considers the cases s = +1 and s = −1 separately; it also states that scaling the first guarantee by ν yields a further bound.Source: §B.2.2 · pp. 16–17

C. Deferred Material from Section 4

The deferred results extend convergence arguments to the considered line searches and establish eventual positive margins for specified step-size choices. They also give an eventual lower bound on iterate norms.

C. Deferred Material from Section 4

  • The convergence rates from Telgarsky (2012, Section 6) carry over to the other considered line searches with only a change of constants.The passage also states that the considered loss class L is contained in G.Source: C. Deferred Material from Section 4 · p. 17
  • For every B > 0, the iterate norms ∥λ_t∥_1 eventually satisfy ∥λ_t∥_1 ≥ B.Lemma C.2 gives a threshold T_B after which the inequality holds.Source: C. Deferred Material from Section 4 · p. 18
  • With step sizes 0.5α_i^Q(ν), all margins over H(A)^c eventually exceed a positive threshold.Lemma C.3 states that there exist γ̂ > 0 and T such that the bound holds for all t ≥ T.Source: C. Deferred Material from Section 4 · p. 18
  • With step sizes α_i ∈ α_i^W(ν), all margins eventually exceed a positive threshold.Lemma C.4 states that there exist γ̂ > 0 and T such that the bound holds for all t ≥ T.Source: C. Deferred Material from Section 4 · p. 19

C.1. Miscellaneous Technical Material

The appendix uses convexity of g and g′(0) = 1 to establish a lower bound on g over [0, 1). It also sketches how a step-size guarantee yields the result under nonseparability and convergence.

C.1. Miscellaneous Technical Material

  • On [0, 1), g is convex and g′(0) = 1.Source: §C.1 · p. 19
  • Consequently, g(r) ≥ r for r in [0, 1).Source: §C.1 · p. 19
  • The proof sketch uses a step-size guarantee with a constant c > 0 independent of t, then invokes nonseparability and convergence to obtain the result.The cited argument identifies nonseparability through a positive lower bound on L(Aλ_t) and convergence through L(Aλ_t) − L(Aλ_{t+1}) → 0.Source: §C.1 · p. 19
Loading 1303.4172v1…