Logarithmic Regret from Sublinear Hints
Authors: Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | As our main result, we show that for OLO in which hints are guaranteed to be good whenever the algorithm asks for a hint, there is an efficient randomized algorithm that obtains O(log T) regret using only O(T) hints. We also show two lower bounds that show the optimality of our algorithm. The first is regarding the minimum number of hints needed to get O(log T) regret: we show that any (potentially randomized) algorithm that uses o(T) hints will suffer a regret of (T). The second and more surprising result is the role of randomness: we show that any deterministic algorithm that obtains O(log T) regret must use (T/ log(T)) hints, even if each of them is perfect. |
| Researcher Affiliation | Collaboration | Aditya Bhaskara Department of Computer Science University of Utah Salt Lake City, UT bhaskaraaditya@gmail.com, Ashok Cutkosky Dept. of Electrical and Computer Engineering Boston University Boston, MA ashok@cutkosky.com, Ravi Kumar Google Research Mountain View, CA ravi.k53@gmail.com, Manish Purohit Google Research Mountain View, CA mpurohit@google.com |
| Pseudocode | Yes | Algorithm 1 Adaptive FTRL Aftrl., Algorithm 2 OGD with shrinking domain Aogd., Algorithm 3 Algorithm with hints Ahints., Algorithm 4 Algorithm with hints (unconstrained case). |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for its methodology is publicly available. |
| Open Datasets | No | The paper presents theoretical results and algorithms, and does not involve training on publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation or provide details on training/validation/test dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions and does not report on empirical experiments that would specify hardware. |
| Software Dependencies | No | The paper is theoretical and does not discuss specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |