Online Agnostic Boosting via Regret Minimization
Online Agnostic Boosting via Regret Minimization
复制标题
通过后悔最小化进行在线不可知提升
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
Nataly Brukhim;Xinyi Chen;Elad Hazan;S. Moran
Boosting 是一种广泛使用的机器学习方法，基于聚合弱学习规则的思想。虽然在统计学习中，许多增强方法都存在于可实现和不可知的环境中，但在在线学习中，它们仅存在于可实现的情况下。在这项工作中，我们提供了第一个不可知的在线提升算法；也就是说，给定一个弱学习器，只有比微不足道的遗憾保证稍微好一点的效果，我们的算法将其提升为具有次线性遗憾的强学习器。
我们的算法基于对在线凸优化的抽象（且简单）简化，可有效地将任意在线凸优化器转换为在线助推器。
此外，这种减少扩展到统计以及在线可实现设置，从而统一了统计/在线和不可知/可实现提升的 4 种情况。
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.
DOI：
10.1109/focs.2019.00015
发表时间：
2019-04
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Matthew Joseph;Jieming Mao;Seth Neel;Aaron Roth
通讯作者：
Matthew Joseph;Jieming Mao;Seth Neel;Aaron Roth