Parameter-free, Dynamic, and Strongly-Adaptive Online Learning
Authors: Ashok Cutkosky
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a new online learning algorithm that for the first time combines several disparate notions of adaptivity. First, our algorithm obtains a parameter-free regret bound that adapts to the norm of the comparator and the squared norm of the size of the gradients it observes. Second, it obtains a strongly-adaptive regret bound, so that for any given interval of length N, the regret over the interval is O( N). Finally, our algorithm obtains an optimal dynamic regret bound: for any sequence of comparators with path-length P, our algorithm obtains regret O( PN) over intervals of length N. Our primary technique for achieving these goals is a new method of combining constrained online learning regret bounds that does not rely on an expert meta-algorithm to aggregate learners. |
| Researcher Affiliation | Collaboration | 1Google Research 2Boston University, Boston Massachusetts, USA. |
| Pseudocode | Yes | Algorithm 1 Varying Constraints; Algorithm 2 Residual Algorithm |
| Open Source Code | No | The paper does not provide any statement or link regarding open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not mention specific datasets or their public availability for training. |
| Dataset Splits | No | The paper is theoretical and does not provide details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setup details such as hyperparameters or training configurations. |