Online Agnostic Boosting via Regret Minimization

• URL: http://arxiv.org/abs/2003.01150v1
• Date: Mon, 2 Mar 2020 19:21:25 GMT
• Title: Online Agnostic Boosting via Regret Minimization
• Authors: Nataly Brukhim, Xinyi Chen, Elad Hazan, Shay Moran
• Abstract summary: Boosting is a widely used machine learning approach based on the idea of aggregating weak learning rules. We provide the first online boosting algorithm; that is, given a weak learner with only marginally-better-than-trivial regret guarantees, our algorithm boosts it to a strong learner with sublinear regret.
• Score: 47.19178618537368
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boosting is a widely used machine learning approach based on the idea of aggregating weak learning rules. While in statistical learning numerous boosting methods exist both in the realizable and agnostic settings, in online learning they exist only in the realizable case. In this work we provide the first agnostic online boosting algorithm; that is, given a weak learner with only marginally-better-than-trivial regret guarantees, our algorithm boosts it to a strong learner with sublinear regret. Our algorithm is based on an abstract (and simple) reduction to online convex optimization, which efficiently converts an arbitrary online convex optimizer to an online booster. Moreover, this reduction extends to the statistical as well as the online realizable settings, thus unifying the 4 cases of statistical/online and agnostic/realizable boosting.

Related papers

• Sample-Efficient Agnostic Boosting [19.15484761265653]
  Empirical Risk Minimization (ERM) outstrips the agnostic boosting methodology in being quadratically more sample efficient than all known boosting algorithms. A key feature of our algorithm is that it leverages the ability to reuse samples across multiple rounds of boosting, while guaranteeing a generalization error strictly better than those obtained by blackbox applications of uniform convergence arguments.
  arXiv  Detail & Related papers  (2024-10-31T04:50:29Z)
• How to Boost Any Loss Function [63.573324901948716]
  We show that loss functions can be efficiently optimized with boosting. We show that boosting can achieve a feat not yet known to be possible in the classical $0th$ order setting.
  arXiv  Detail & Related papers  (2024-07-02T14:08:23Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Online Agnostic Multiclass Boosting [20.22409095000365]
  We give the first boosting algorithm for online agnostic mutliclass classification. Our reduction also enables the construction of algorithms for statistical agnostic, online realizable, and statistical realizable multiclass boosting.
  arXiv  Detail & Related papers  (2022-05-30T13:59:55Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  parameter-free algorithms are online learning algorithms that do not require setting learning rates. We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
  arXiv  Detail & Related papers  (2022-03-19T13:39:49Z)
• OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression [5.457279006229211]
  This paper presents a new regularization approach -- OpReg-Boost -- to boost the convergence of online optimization and learning algorithms. We show how to formalize the operator regression problem and propose a computationally-efficient Peaceman-Rachford solver.
  arXiv  Detail & Related papers  (2021-05-27T16:17:38Z)
• Boosting for Online Convex Optimization [64.15578413206715]
  We consider the decision-making framework of online convex optimization with a large number of experts. We define a weak learning algorithm as a mechanism that guarantees approximate regret against a base class of experts. We give an efficient boosting algorithm that guarantees near-optimal regret against the convex hull of the base class.
  arXiv  Detail & Related papers  (2021-02-18T12:30:49Z)
• Online Boosting with Bandit Feedback [36.33990847170534]
  We consider the problem of online boosting for regression tasks, when only limited information is available to the learner. We give an efficient regret minimization method that has two implications: an online boosting algorithm with noisy multi-point bandit feedback, and a new projection online convex optimization algorithm with gradient.
  arXiv  Detail & Related papers  (2020-07-23T12:40:57Z)
• On the Dual Formulation of Boosting Algorithms [92.74617630106559]
  We show that the Lagrange problems of AdaBoost, LogitBoost and soft-marginBoost are all dual problems with generalized hinge loss entropy. By looking at the dual problems of these boosting algorithms, we show that the success of boosting can be understood in terms of maintaining a better margin distribution.
  arXiv  Detail & Related papers  (2009-01-23T02:14:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.