Online Agnostic Boosting via Regret Minimization
Authors: Nataly Brukhim, Xinyi Chen, Elad Hazan, Shay Moran
NeurIPS 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 a boosting algorithm. 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. |
| Researcher Affiliation | Collaboration | Nataly Brukhim Google AI Princeton Princeton University Department of Computer Science EMAIL Xinyi Chen Google AI Princeton Princeton University Department of Computer Science EMAIL Elad Hazan Google AI Princeton Princeton University Department of Computer Science EMAIL Shay Moran Department of Mathematics Technion Israel Institute of Technology EMAIL |
| Pseudocode | Yes | Algorithm 1 Online Agnostic Boosting with OCO; Algorithm 2 Boosting with OCO; Algorithm 3 Online boosting with OCO. |
| Open Source Code | No | The paper does not provide any specific links to source code repositories or explicit statements about code availability. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs; it does not report empirical experiments using specific datasets. |
| Dataset Splits | No | The paper is theoretical and does not report empirical experiments. Therefore, there are no mentions of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs; it does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs; it does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs; it does not describe any experimental setup details such as hyperparameters or training configurations. |