Best-case lower bounds in online learning
Authors: Cristóbal Guzmán, Nishant Mehta, Ali Mortazavi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Much of the work in online learning focuses on the study of sublinear upper bounds on the regret. In this work, we initiate the study of best-case lower bounds in online convex optimization, wherein we bound the largest improvement an algorithm can obtain relative to the single best action in hindsight. Our contributions are a general method to provide best-case lower bounds in Follow the Regularized Leader (FTRL) algorithms with time-varying regularizers... We show that this general bound can easily be applied to yield concrete best-case lower bounds for FTRL with time-varying negative regularizers... In the setting of DTOL with 2 experts and binary losses, we explicitly identify the best-case sequence, proving that our best-case lower bounds are tight in this setting (Section 6). |
| Researcher Affiliation | Academia | Cristóbal Guzmán 1,2 Nishant A. Mehta 3 Ali Mortazavi 3 1Department of Applied Mathematics, University of Twente 2 Institute for Mathematical and Computational Eng., Pontificia Universidad Católica de Chile 3 Department of Computer Science, University of Victoria |
| Pseudocode | No | The paper describes algorithms and mathematical formulations (e.g., equation (1) for FTRL), but it does not include any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not include any statements about the release of source code for the methodology described, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper focuses on theoretical analysis of online learning algorithms within settings like Online Convex Optimization (OCO) and Decision-Theoretic Online Learning (DTOL). It discusses 'loss sequences' as theoretical constructs (e.g., 'characterize the binary loss sequence'), but it does not use or provide concrete access information for any publicly available or open datasets that were used for empirical training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, thus there is no mention of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not discuss specific software implementations of its methods. No software names with version numbers are mentioned as dependencies for replicating work. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments. Consequently, there are no details about experimental setup, hyperparameters, or training configurations. |