Timezone: »
We present a new mechanism for label differential privacy, a relaxation of differentially private machine learning that only protects the privacy of the labels in the training set. Our mechanism clusters the examples in the training set using their (non-private) feature vectors, randomly re-samples each label from examples in the same cluster, and outputs a training set with noisy labels as well as a modified version of the true loss function. We prove that when the clusters are both large and high-quality, the model that minimizes the modified loss on the noisy training set converges to small excess risk at a rate that is comparable to the rate for non-private learning. Our experiments show that randomizing the labels within each cluster significantly improves the privacy vs. accuracy trade-off compared to applying uniform randomized response to the labels, and also compared to learning a model via DP-SGD.
Author Information
Hossein Esfandiari (Google Research)
Vahab Mirrokni (Google Research)
Umar Syed (Google)
Sergei Vassilvitskii (Google)
More from the Same Authors
-
2023 Poster: Robust and private stochastic linear bandits »
Vasilis Charisopoulos · Hossein Esfandiari · Vahab Mirrokni -
2023 Poster: Multi-channel Autobidding with Budget and ROI Constraints »
Yuan Deng · Negin Golrezaei · Patrick Jaillet · Jason Cheuk Nam Liang · Vahab Mirrokni -
2023 Poster: Label differential privacy and private training data release »
Robert Busa-Fekete · andres munoz · Umar Syed · Sergei Vassilvitskii -
2023 Poster: Predictive Flows for Faster Ford-Fulkerson »
Sami Davies · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang -
2023 Poster: Learning Rate Schedules in the Presence of Distribution Shift »
Matthew Fahrbach · Adel Javanmard · Vahab Mirrokni · Pratik Worah -
2023 Poster: Learning-augmented private algorithms for multiple quantile release »
Mikhail Khodak · Kareem Amin · Travis Dick · Sergei Vassilvitskii -
2023 Poster: Speeding Up Bellman Ford via Minimum Violation Permutations »
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii -
2023 Poster: Robust Budget Pacing with a Single Sample »
Santiago Balseiro · Rachitesh Kumar · Vahab Mirrokni · Balasubramanian Sivan · Di Wang -
2023 Poster: Differentially Private Hierarchical Clustering with Provable Approximation Guarantees »
Jacob Imola · Alessandro Epasto · Mohammad Mahdian · Vincent Cohen-Addad · Vahab Mirrokni -
2023 Poster: Approximately Optimal Core Shapes for Tensor Decompositions »
Mehrdad Ghadiri · Matthew Fahrbach · Thomas Fu · Vahab Mirrokni -
2023 Oral: Robust Budget Pacing with a Single Sample »
Santiago Balseiro · Rachitesh Kumar · Vahab Mirrokni · Balasubramanian Sivan · Di Wang -
2023 Oral: Differentially Private Hierarchical Clustering with Provable Approximation Guarantees »
Jacob Imola · Alessandro Epasto · Mohammad Mahdian · Vincent Cohen-Addad · Vahab Mirrokni -
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Oral: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2019 Poster: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh