Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Authors: Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Leme, Jon Schneider
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design algorithms for this problem which achieve regret O(d log T) and exp(O(d log d)). To accomplish this, we design novel cutting-plane algorithms with low regret the total distance between the true point w and the hyperplanes the separation oracle returns. We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with O(d2 log d) regret and list size poly(d). Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner s formula for the centroid of a convex set) which may be of independent interest.3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] |
| Researcher Affiliation | Industry | Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, and Jon Schneider Google Research |
| Pseudocode | No | No explicit pseudocode or algorithm blocks were found. Algorithm steps are described in narrative text. |
| Open Source Code | No | The paper states "If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?" with the answer "[N/A]". No other statements about open-source code release were found. |
| Open Datasets | No | The paper states "If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?" with the answer "[N/A]". No datasets are mentioned as being used for training or evaluation. |
| Dataset Splits | No | The paper states "If you ran experiments... (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?" with the answer "[N/A]". No mention of validation splits was found. |
| Hardware Specification | No | The paper states "If you ran experiments... (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?" with the answer "[N/A]". No specific hardware details were provided. |
| Software Dependencies | No | No specific software dependencies with version numbers were mentioned. |
| Experiment Setup | No | The paper states "If you ran experiments... (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?" with the answer "[N/A]". No specific experimental setup details were provided. |