PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal learning with Bernstein Online Aggregation

Olivier Wintenberger

arXiv:1404.1356v5stat.MLcs.LGmath.STstat.TH

TL;DR

Online aggregation procedures had not been shown to yield the fast batch rate in deviation. The paper introduces BOA, adding second-order terms to exponential weights and extending the method with adaptive learning rates. It reports stochastic cumulative predictive-risk bounds and an optimal high-probability batch rate under the stated iid loss conditions.

  • Problem

    The paper addresses the lack of an online aggregation procedure whose batch version achieves the fast rate in deviation.

    Source: §1 · p. 3

  • Method

    BOA incorporates a second-order term into exponential weights and uses empirical Bernstein-based stochastic conversion, with a multiple-learning-rate adaptive version.

    Source: §1 · pp. 3, 4, 6, §4.1 · p. 15

  • Results

    BOA gives cumulative predictive-risk bounds in any stochastic environment, and its batch version achieves the optimal high-probability rate under the paper's stated setting.

    Source: §1 · p. 7

  • Takeaways & Limitations

    The paper presents BOA as the first online aggregation procedure whose batch version is optimal, and as an explicit adaptive algorithm with an optimal high-probability oracle inequality.

    Source: §1 · pp. 3, 7

    With multiple adaptive learning rates, the relative-entropy bound is not attained as it is with a single adaptive rate; whether this drawback can be avoided remains open.

    Source: §3.2 · p. 15

Abstract

from arXiv · show

We introduce a new recursive aggregation procedure called Bernstein Online Aggregation (BOA). The exponential weights include an accuracy term and a second order term that is a proxy of the quadratic variation as in Hazan and Kale (2010). This second term stabilizes the procedure that is optimal in different senses. We first obtain optimal regret bounds in the deterministic context. Then, an adaptive version is the first exponential weights algorithm that exhibits a second order bound with excess losses that appears first in Gaillard et al. (2014). The second order bounds in the deterministic context are extended to a general stochastic context using the cumulative predictive risk. Such conversion provides the main result of the paper, an inequality of a novel type comparing the procedure with any deterministic aggregation procedure for an integrated criteria. Then we obtain an observable estimate of the excess of risk of the BOA procedure. To assert the optimality, we consider finally the iid case for strongly convex and Lipschitz continuous losses and we prove that the optimal rate of aggregation of Tsybakov (2003) is achieved. The batch version of the BOA procedure is then the first adaptive explicit algorithm that satisfies an optimal oracle inequality with high probability.

1 Introduction and main results

The paper asks how online aggregation can achieve fast, high-probability batch guarantees, then introduces BOA, whose second-order weighting supports regret bounds and stochastic cumulative predictive-risk comparisons. It extends the procedure with adaptive learning rates and establishes a fast batch rate under iid strongly convex, Lipschitz losses.

1 Introduction and main results

  • Very few procedures achieve the fast log(M)/n rate in deviation, and none came from an online procedure before BOA.Earlier batch procedures could require computational optimization, while progressive mixture rules achieved the rate in expectation but were suboptimal in deviation.Source: §1 · p. 3
  • BOA adds a second-order term to exponential weights, chosen to stabilize the procedure and account for the cost of learner-to-aggregate loss distances.The paper describes this refinement as necessary for its optimality goal.Source: §1 · pp. 3–4
  • An empirical Bernstein inequality yields second-order regret bounds and a stochastic conversion to cumulative predictive-risk bounds valid in any stochastic environment.The conversion uses quadratic variation rather than predictive quadratic variation.Source: §1 · pp. 4–5
  • The paper extends BOA with a gradient trick for convex aggregation and multiple learning rates that adapt to observation ranges.The gradient trick uses a linearized loss to compare BOA with the best deterministic aggregation.Source: §1 · pp. 5–6
  • The adaptive procedure provides second-order bounds with excess-loss terms, with constants growing at the rate log log(n).The paper contrasts its learning-rate and range-estimator dependence with the doubling trick.Source: §1 · pp. 6–7
  • Under iid strongly convex and Lipschitz losses, the batch BOA procedure achieves the fast model-selection rate; the adaptive batch bound has larger constants growing at log log(n).The paper also gives a convex-aggregation rate smaller than sqrt(log(M)/n) under a boundedness assumption.Source: §1 · p. 7

2 Preliminaries

The preliminaries set up recursive supermartingale arguments and the variational form of entropy as tools for deriving second-order regret bounds.

2 Preliminaries

  • The proof strategy combines recursive supermartingale arguments with the variational form of entropy to derive second-order regret bounds.Source: §2 · p. 8, §2.2 · p. 8

2.1 The proof of the martingale inequality in Theorem 1.1

  • For the martingale inequality, the proof applies log(1 + x) ≥ x − x^2 for increments bounded below by −1/2, then recurses using centered martingale differences.Source: §2.1 · p. 8

2.2 The variational form of the entropy

  • The entropy variational formula bounds differences of expectations by an expectation under Q plus a relative-entropy penalty.Source: §2.2 · pp. 8–9

3 Second order regret bounds for the BOA procedure

The section develops second-order regret bounds for BOA in a deterministic setting, first for fixed learning rates and then for an adaptive version. Multiple learning rates address differing learner variability, while the adaptive version handles unknown ranges at an additional logarithmic cost.

3.1 First regret bounds and link with the individual sequences framework

  • BOA’s multiple-learning-rate procedure has cumulative-loss regret bounds for convex losses, including a gradient-trick form using linearized losses.The second-order term can be small when sub-gradients are small or when BOA’s weights are close to the objective distribution.Source: §3.1 · pp. 9–11
  • Different learners’ second-order properties can make a single learning rate inefficient, motivating separate rates for each learner.The section also relates its bounds to the individual-sequences framework.Source: §3.1 · pp. 9, 11
  • The multiple-rate bound favors small learning rates, which the authors associate with bad experts; changing the initial weights can address this drawback.A differently tuned rate can yield an upper bound, but that procedure is not recursive when the rates depend on the full data sequence, so it does not convert to the batch setting.Source: §3.1 · p. 12

3.2 A new adaptive method for exponential weights

  • Adaptive BOA uses learner-specific learning rates and range estimates, with range exceedances penalized in the exponential weights.This extends the doubling-trick approach to multiple learning rates and learner-specific ranges.Source: §3.2 · p. 13
  • The adaptive procedure handles unknown ranges but pays an additional logarithmic term depending on the variability of learning rates over time.That term is avoidable with one shared adaptive learning rate.Source: §3.2 · p. 14
  • The relative-entropy bound is achieved only with a single adaptive learning rate; whether multiple-rate procedures can avoid this drawback remains open.With multiple rates, the relative-entropy terms for the comparison distribution and initial distribution need not coincide.Source: §3.2 · p. 15

4 Optimality of the BOA procedure in a stochastic environment

The section converts second-order regret bounds into stochastic predictive-risk guarantees, then establishes BOA’s optimality under more specific settings. For model selection, the fast-rate result relies on iid observations and strongly convex, Lipschitz losses.

4.1 An empirical stochastic conversion

  • The stochastic conversion bounds cumulative predictive risk with high probability in a general stochastic environment, without a dependence condition, using cumulative predictive risk.It applies to any aggregation procedure under the stated boundedness condition and also has a convex-case linearized form.Source: §4.1 · p. 15

4.2 Second order bounds on the excess of the cumulative predictive risk

  • BOA’s second-order regret bounds yield second-order bounds on cumulative predictive risk, with the adaptive conversion preserving a second-order form similar to the regret bound.The adaptive result requires adapting the conversion because its boundedness condition does not hold at every time step.Source: §4.2 · pp. 16–17
  • Reducing dictionary size can tighten the second-order bound, but reduces the generality of convex aggregation by limiting the learners in the dictionary.Source: §4.2 · p. 18
  • The upper bound is observable and resembles empirical bounds from the PAC-Bayesian approach; the second-order complexity terms are identified as a candidate measure of convex aggregation complexity.The passage leaves open whether those complexity terms are optimal.Source: §4.2 · p. 18

4.3 Optimal learning for Problem (MS)

  • For Problem (C), BOA’s optimal rate also holds in general stochastic environments for excess mean predictive risk.The section then turns to Problem (MS) under Lipschitz, strongly convex losses.Source: §4.3 · p. 18
  • Under iid observations and condition (LIST), BOA achieves the optimal fast aggregation rate for Problem (MS), and its adaptive version retains the rate with larger constants growing as log log(n).The stated scope is strongly convex, Lipschitz-continuous losses; condition (LIST) may hold only locally.Source: §4.3 · pp. 19, 22, 23
  • The adaptive batch guarantee carries larger constants growing as log log(n), while the non-adaptive rate depends on a gradient-range parameter that may be unknown.The multiple-learning-rate adaptive procedure tunes learning rates automatically.Source: §4.3 · p. 22
  • BOA is explicitly computed with complexity O(Mn), unlike cited batch procedures requiring computational optimization.The cited comparison is with.Source: §4.3 · p. 23

Related papers

Loading 1404.1356v5…