Online Learning with a Hint
Authors: Ofer Dekel, arthur flajolet, Nika Haghtalab, Patrick Jaillet
NeurIPS 2017 | Conference 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 oferd@microsoft.com Arthur Flajolet Operations Research Center Massachusetts Institute of Technology flajolet@mit.edu Nika Haghtalab Computer Science Department Carnegie Mellon University nika@cmu.edu Patrick Jaillet EECS, LIDS, ORC Massachusetts Institute of Technology jaillet@mit.edu |
| 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. |