Timezone: »
Poster
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.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(d^2 \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.
Author Information
Sreenivas Gollapudi (Google Research)
Guru Guruganesh (Google Research)
Kostas Kollias (Google Research)
Pasin Manurangsi (Google)
Renato Leme (Google Research)
Jon Schneider (Google Research)
More from the Same Authors
-
2022 : "I pick you choose": Joint human-algorithm decision making in multi-armed bandits »
Kate Donahue · Sreenivas Gollapudi · Kostas Kollias -
2023 Poster: Sparsity-Preserving Differentially Private Training »
Badih Ghazi · Yangsibo Huang · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Amer Sinha · Chiyuan Zhang -
2023 Poster: Affinity-Aware Graph Networks »
Ameya Velingker · Ali Sinop · Ira Ktena · Petar Veličković · Sreenivas Gollapudi -
2023 Poster: Optimal Unbiased Randomizers for Regression with Label Differential Privacy »
Ashwinkumar Badanidiyuru Varadaraja · Badih Ghazi · Pritish Kamath · Ravi Kumar · Ethan Leeman · Pasin Manurangsi · Avinash V Varadarajan · Chiyuan Zhang -
2023 Poster: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2023 Poster: On Differentially Private Sampling from Gaussian and Product Distributions »
Badih Ghazi · Xiao Hu · Ravi Kumar · Pasin Manurangsi -
2023 Poster: On Computing Pairwise Statistics with Local Differential Privacy »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Adam Sealfon -
2023 Oral: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2022 Poster: Private Isotonic Regression »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: A Fourier Approach to Mixture Learning »
Mingda Qiao · Guru Guruganesh · Ankit Rawat · Kumar Avinava Dubey · Manzil Zaheer -
2022 Poster: Anonymized Histograms in Intermediate Privacy Models »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Cryptographic Hardness of Learning Halfspaces with Massart Noise »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi · Lisheng Ren -
2021 Poster: User-Level Differentially Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 Poster: Margin-Independent Online Multiclass Learning via Convex Geometry »
Guru Guruganesh · Allen Liu · Jon Schneider · Joshua Wang -
2021 Poster: A Convergence Analysis of Gradient Descent on Graph Neural Networks »
Pranjal Awasthi · Abhimanyu Das · Sreenivas Gollapudi -
2020 Poster: Adaptive Probing Policies for Shortest Path Routing »
Aditya Bhaskara · Sreenivas Gollapudi · Kostas Kollias · Kamesh Munagala -
2020 Poster: Myersonian Regression »
Allen Liu · Renato Leme · Jon Schneider -
2020 Poster: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2020 Poster: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise »
Ilias Diakonikolas · Daniel M. Kane · Pasin Manurangsi -
2020 Oral: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2020 Poster: Big Bird: Transformers for Longer Sequences »
Manzil Zaheer · Guru Guruganesh · Kumar Avinava Dubey · Joshua Ainslie · Chris Alberti · Santiago Ontanon · Philip Pham · Anirudh Ravula · Qifan Wang · Li Yang · Amr Ahmed -
2019 Poster: Prior-Free Dynamic Auctions with Low Regret Buyers »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Poster: Contextual Bandits with Cross-Learning »
Santiago Balseiro · Negin Golrezaei · Mohammad Mahdian · Vahab Mirrokni · Jon Schneider -
2019 Poster: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: Secretary Ranking with Minimal Inversions »
Sepehr Assadi · Eric Balkanski · Renato Leme -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Oral: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2018 Poster: Contextual Pricing for Lipschitz Buyers »
Jieming Mao · Renato Leme · Jon Schneider -
2017 Poster: Dynamic Revenue Sharing »
Santiago Balseiro · Max Lin · Vahab Mirrokni · Renato Leme · IIIS Song Zuo