Online Learning with a Hint
Authors: Ofer Dekel, arthur flajolet, Nika Haghtalab, Patrick Jaillet
NeurIPS 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a variant of online linear optimization where the player receives a hint about the loss function at the beginning of each round. The hint is given in the form of a vector that is weakly correlated with the loss vector on that round. We show that the player can benefit from such a hint if the set of feasible actions is sufficiently round. Specifically, if the set is strongly convex, the hint can be used to guarantee a regret of O(log(T)), and if the set is q-uniformly convex for q (2, 3), the hint can be used to guarantee a regret of o(T). In contrast, we establish (T) lower bounds on regret when the set of feasible actions is a polyhedron. |
| Researcher Affiliation | Collaboration | Ofer Dekel Microsoft Research EMAIL Arthur Flajolet Operations Research Center Massachusetts Institute of Technology EMAIL Nika Haghtalab Computer Science Department Carnegie Mellon University EMAIL Patrick Jaillet EECS, LIDS, ORC Massachusetts Institute of Technology EMAIL |
| Pseudocode | Yes | Algorithm 1 Ahint FOR STRONGLY CONVEX K; Algorithm 2 Aset: SET-OF-HINTS |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as a repository link or an explicit statement about code release for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, it does not mention public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, it does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations with version numbers that would be needed for replication. |
| Experiment Setup | No | The paper is theoretical and does not present experimental results. Therefore, it does not provide details about experimental setup, hyperparameters, or training configurations. |