Timezone: »
Poster
User-Level Differentially Private Learning via Correlated Sampling
Badih Ghazi · Ravi Kumar · Pasin Manurangsi
Most works in learning with differential privacy (DP) have focused on the setting where each user has a single sample. In this work, we consider the setting where each user holds $m$ samples and the privacy protection is enforced at the level of each user's data. We show that, in this setting, we may learn with a much fewer number of users. Specifically, we show that, as long as each user receives sufficiently many samples, we can learn any privately learnable class via an $(\epsilon, \delta)$-DP algorithm using only $O(\log(1/\delta)/\epsilon)$ users. For $\epsilon$-DP algorithms, we show that we can learn using only $O_{\epsilon}(d)$ users even in the local model, where $d$ is the probabilistic representation dimension. In both cases, we show a nearly-matching lower bound on the number of users required.A crucial component of our results is a generalization of global stability [Bun, Livni, Moran, FOCS 2020] that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy to show that the global stability can be boosted to be arbitrarily close to one, at a polynomial expense in the number of samples.
Author Information
Badih Ghazi (Google)
Ravi Kumar (Google)
Pasin Manurangsi (Google)
More from the Same Authors
-
2022 Poster: Private Isotonic Regression »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
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: Logarithmic Regret from Sublinear Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 Poster: Online Knapsack with Frequency Predictions »
Sungjin Im · Ravi Kumar · Mahshid Montazer Qaem · Manish Purohit -
2021 Poster: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider -
2020 Poster: Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Benjamin Moseley · Philip Pham · Sergei Vassilvitskii · Yuyan Wang -
2020 Poster: Online Linear Optimization with Many Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
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 -
2019 : Coffee Break & Poster Session 2 »
Juho Lee · Yoonho Lee · Yee Whye Teh · Raymond A. Yeh · Yuan-Ting Hu · Alex Schwing · Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Christian Bueno · Aditya Sanghi · Pradeep Kumar Jayaraman · Ignacio Arroyo-Fernández · Andrew Hryniowski · Vinayak Mathur · Sanjay Singh · Shahrzad Haddadan · Vasco Portilheiro · Luna Zhang · Mert Yuksekgonul · Jhosimar Arias Figueroa · Deepak Maurya · Balaraman Ravindran · Frank NIELSEN · Philip Pham · Justin Payan · Andrew McCallum · Jinesh Mehta · Ke SUN -
2019 : Contributed Talk - Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Philip Pham -
2019 Poster: Efficient Rematerialization for Deep Networks »
Ravi Kumar · Manish Purohit · Zoya Svitkina · Erik Vee · Joshua Wang -
2019 Poster: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2018 Poster: Mallows Models for Top-k Lists »
Flavio Chierichetti · Anirban Dasgupta · Shahrzad Haddadan · Ravi Kumar · Silvio Lattanzi -
2018 Poster: Improving Online Algorithms via ML Predictions »
Manish Purohit · Zoya Svitkina · Ravi Kumar -
2017 Poster: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Spotlight: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii