Towards Best-of-All-Worlds Online Learning with Feedback Graphs
Authors: Liad Erez, Tomer Koren
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop an algorithm that simultaneously achieves regret bounds of the form: O(θ(G)T) with adversarial losses; O(θ(G) polylogT) with stochastic losses; and O(θ(G) polylogT+ θ(G)C) with stochastic losses subject to C adversarial corruptions. Here, θ(G) is the clique covering number of the graph G. Our algorithm is an instantiation of Follow-the Regularized-Leader with a novel regularization that can be seen as a product of a Tsallis entropy component... One of our key technical contributions is in establishing the convexity of this regularizer and controlling its inverse Hessian, despite its complex product structure. |
| Researcher Affiliation | Collaboration | Liad Erez Blavatnik School of Computer Science Tel Aviv University liaderez1@gmail.com Tomer Koren Blavatnik School of Computer Science Tel Aviv University and Google Research tkoren@tauex.tau.ac.il |
| Pseudocode | Yes | Algorithm 1: FTRL with feedback graphs |
| Open Source Code | No | The information is insufficient. The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The information is insufficient. The paper is theoretical and does not describe experiments using publicly available datasets for training. It defines a feedback model and assumptions on losses but does not refer to specific datasets or their public availability. |
| Dataset Splits | No | The information is insufficient. The paper is theoretical and does not describe empirical experiments that would involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The information is insufficient. The paper does not provide any details about the specific hardware (e.g., GPU/CPU models, memory) used for running experiments. |
| Software Dependencies | No | The information is insufficient. The paper does not provide specific software names with version numbers (e.g., libraries, frameworks, or programming languages with their versions) that would be needed to replicate the work. |
| Experiment Setup | No | The information is insufficient. As a theoretical paper, it does not describe an empirical experimental setup, and thus does not include details such as hyperparameter values or training configurations. |