PaperlayerView exact revision on arXiv

Source-linked AI summary

Boosting for Online Convex Optimization

Elad Hazan, Karan Singh

arXiv:2102.09305v1cs.LGstat.ML

TL;DR

Large contextual expert classes make enumeration and search infeasible in online convex optimization. The paper uses weak learners and boosting to obtain efficient algorithms competing with the convex hull of the base class under full and bandit feedback, with related statistical guarantees. The experiments show the largest gains for impoverished base classes such as decision stumps, while boosting linear models offers little or negative improvement.

  • Problem

    Large policy classes make enumeration and search infeasible, motivating efficient online convex optimization methods that avoid dependence on the number of experts.

  • Method

    The paper defines weak learners with multiplicatively approximate regret and combines them through boosting for full-information, bandit, and i.i.d. contextual settings.

  • Results

    The algorithms achieve near-optimal regret against the convex hull of the base class, while experimental gains are strongest for decision stumps and least prominent or negative for ridge regression.

  • Takeaways & Limitations

    Boosting extends online and gradient-boosting ideas to contextual online convex optimization, including full OCO and bandit linear optimization settings.

  • Takeaways & Limitations

    The statistical results rely on i.i.d. samples, while the corresponding online weak-learner assumptions are stronger.

Abstract

from arXiv · show

We consider the decision-making framework of online convex optimization with a very large number of experts. This setting is ubiquitous in contextual and reinforcement learning problems, where the size of the policy class renders enumeration and search within the policy class infeasible. Instead, we consider generalizing the methodology of online boosting. We define a weak learning algorithm as a mechanism that guarantees multiplicatively approximate regret against a base class of experts. In this access model, we give an efficient boosting algorithm that guarantees near-optimal regret against the convex hull of the base class. We consider both full and partial (a.k.a. bandit) information feedback models. We also give an analogous efficient boosting algorithm for the i.i.d. statistical setting. Our results simultaneously generalize online boosting and gradient boosting guarantees to contextual learning model, online convex optimization and bandit linear optimization settings.

1 Introduction

The paper addresses computationally infeasible online convex optimization with large expert classes by using weak learners to efficiently compete with convex combinations of base hypotheses. It extends online boosting to full OCO, including arbitrary convex decision sets and approximation factors, while also relating the approach to statistical, bandit, and gradient-boosting settings.

  • 1 Introduction: The classical O(T log |H|) regret guarantee becomes computationally impractical when the expert class is too large to enumerate, especially for contextual policies.Algorithms achieving this bound can require running time linear in |H|.
  • 1 Introduction: Weak learners enable efficient regret minimization against the convex hull of a large base hypothesis class, rather than only its best individual hypothesis.The resulting guarantee is standard regret without the weak learner’s multiplicative γ factor.
  • 1.1 Setting and contributions: A γ-weak OCO learner provides multiplicatively approximate regret against a base class, generalizing the better-than-random edge used by classical weak learners.The definition is invariant to constant offsets in the loss functions.
  • 1.1 Setting and contributions: The main algorithm uses running time independent of |H| and depends instead on natural problem parameters such as the number N of weak-learner copies.It competes with the best convex combination of base hypotheses without a multiplicative γ factor.
  • 1.2 Related Work: The work generalizes online boosting to full online convex optimization with arbitrary convex decision sets and arbitrary approximation factor γ.The authors identify a new extension operator as necessary for this generalization.
  • 1.2 Related Work: Unlike α-regret approaches based on approximate oracles, the paper targets standard regret against the stronger benchmark of convex combinations of experts.This distinguishes the guarantee from methods that generate only approximately optimal decisions.

2 Improper learning and the Extension operator

The extension operator addresses infeasible scaled actions by modifying losses outside the decision set, smoothing them, and enabling projection back into the feasible set without increasing cost.

  • 2.1 Preliminaries: The preliminaries introduce scaling and smoothing operators used to construct the loss extension.Smoothing is defined through inf-convolution or Moreau-Yoshida regularization, with standard smoothness and Lipschitz properties.
  • 2.2 The extension operator: The weak learner’s approximate guarantee motivates scaling its predictions, but the resulting actions lie in the infeasible set γ^-1K.A rescaled Frank-Wolfe method can compete with the convex hull of the base class if actions in γ^-1K were feasible.
  • 2.2 The extension operator: Directly mapping scaled actions into K is generally impossible for linear losses because their extrema occur on the boundary.This prevents a generic loss-preserving reduction from scaled actions to feasible actions.
  • 2.2 The extension operator: The extension modifies losses outside K using distance penalties and smoothing, then projects predictions back onto K.The construction uses Euclidean distance, projection, and the parameters δ and κ.
  • 2.2 The extension operator: With κ=G, extended losses are smooth, agree approximately with the original losses on K, and projection increases their value by at most G^2δ.The projection guarantee permits infeasible weak-learner outputs to be converted into feasible actions without a significant cost increase.

3 Algorithm and Main Theorems

Algorithm 1, BoOCO, combines multiple weak online learners to obtain an efficient online convex optimization procedure with a main performance guarantee.

  • 3 Algorithm and Main Theorems: Algorithm 1 applies weak learners to linear loss functions formed from gradients and recursively processes residual losses.This is the paper’s black-box boosting mechanism for converting weak online learning into OCO.
  • 3 Algorithm and Main Theorems: The paper states Theorem 6 as the main performance guarantee for the actions generated by Algorithm 1.The theorem specifies the guarantee under a chosen value of δ.
  • 3 Algorithm and Main Theorems: BoOCO uses N copies of a γ-WOCL with learning-rate parameters, smoothing parameter δ, and κ=G.The algorithm receives contexts, constructs predictions, incurs loss, and passes linear losses to the weak learners.

4 Analysis

The analysis establishes the main guarantee through extended losses, smoothness and Lipschitz bounds, recursive residual control, and comparison with the best convex-hull hypothesis.

  • 4 Analysis: The proof combines the extension lemmas with smoothness and Lipschitz estimates to establish Theorem 6.The analysis also uses that the distance to K is 1-Lipschitz and bounds the extended gradients by 2G.
  • 4 Analysis: The analysis compares the algorithm’s actions with a hindsight-best hypothesis in the convex hull of the base class.The comparator’s decisions are defined as h*(c_t).
  • 4 Analysis: A smoothness lemma controls the recursive boosting error when the extended losses are β-smooth and have bounded gradient norm.This lemma is used to analyze the sequence of residual losses.
  • 4 Analysis: Linearity lets the analysis restate weak-learner guarantees over convex combinations of hypotheses.The argument uses linear loss on a convex combination to relate aggregate predictions to individual hypotheses.
  • 4 Analysis: The recursive relation for the residual term is simplified using Lemma 8, yielding an explicit bound on the final residual quantity.The stated simplification gives ˆΔ_N ≤ 2βD^2T.

5 Boosting for Bandit Linear Optimization

The paper extends boosting to bandit linear optimization by using randomized unbiased loss estimates, and states that the resulting regret is sublinear whenever the full-information bound is sublinear, though slower.

  • 5 Boosting for Bandit Linear Optimization: Bandit linear optimization differs from OCO through linear costs and feedback limited to the incurred cost.The section introduces this setting before presenting the boosting construction.
  • 5 Boosting for Bandit Linear Optimization: The bandit method uses randomness to construct a random linear loss whose expectation equals the actual loss, enabling reuse of the full-information boosting algorithm.This is implemented through randomized exploration and unbiased gradient estimation.
  • 5 Boosting for Bandit Linear Optimization: The construction assumes the convex decision set contains the unit simplex, an assumption obtained by scaling and rotating any non-degenerate set.Scaling changes regret only by a constant factor, while axis-aligning rotation does not affect the regret bound.
  • 5 Boosting for Bandit Linear Optimization: The procedure inputs η and an instance A of Algorithm 1, observes context ct each round, draws Bernoulli bt with parameter η, and on bt = 1 randomly selects and plays a coordinate basis vector.When bt = 1, it passes estimated feedback ˜ft as specified by Equation (2) to A.
  • 5 Boosting for Bandit Linear Optimization: The bandit regret bound is sublinear whenever the full-information regret bound is sublinear, but boosting proceeds at a slower rate.Theorem 10 states the resulting performance guarantee for Algorithm 2.
  • 5.1 Application to contextual bandits: For multi-armed contextual bandits, the decision set is K=ΔK with [0,1]-bounded losses and feedback only from the selected arm.The paper states a corollary for predictions generated by Algorithm 2 in this setting.

6 Boosting for Stochastic Contextual Optimization

The paper extends boosting to stochastic contextual optimization by using weak contextual optimizers instead of explicit optimization over the hypothesis class. Algorithm 3 produces a hypothesis with guarantees stronger than those of the weak optimizers.

  • 6 Boosting for Stochastic Contextual Optimization: The stochastic contextual setting assumes losses are generated from a joint distribution over contexts and convex cost functions.
  • 6 Boosting for Stochastic Contextual Optimization: Weak contextual optimizers provide an approximate alternative to explicit optimization over a large hypothesis class in stochastic contextual optimization.They operate on samples from a distribution over contexts and unit linear loss functions.
  • 6 Boosting for Stochastic Contextual Optimization: The stochastic results do not follow blackbox from the online results because their i.i.d. assumptions differ from the stronger online weak-learner assumptions.
  • 6.1 Algorithm and main theorem: Algorithm 3 uses N weak optimizers and constructs a hypothesis whose guarantee improves on the weak optimizers in two ways.
  • 6.1 Algorithm and main theorem: The resulting solution competes with the convex hull of H and removes the weak optimizers’ γ approximation factor.

7 Experimental Results

Experiments test whether boosting improves concrete online weak learners across regression datasets. The method improves accuracy with few weak learners, especially for decision stumps, while gains for ridge regression are limited or negative.

  • The experiments evaluate decision stumps, ridge regression, and a one-hidden-unit multilayer perceptron on three regression datasets averaged over 20 runs.
  • Boosting improves accuracy with few weak learners, requiring only a reasonably small increase in computation.
  • Improvements are most pronounced for decision stumps, whereas ridge regression gains are least prominent and sometimes negative because convex combinations of linear models remain linear.

8 Conclusions

The paper generalizes gradient boosting and online boosting to contextual online convex optimization. Its derivation introduces a new extension operator for convex functions over convex domains.

  • The paper applies a boosting approach to contextual online convex optimization, generalizing gradient boosting and online boosting.
  • The derivation introduces a new extension operator for convex functions over convex domains.
Loading 2102.09305v1…