Timezone: »
We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distributions satisfying the minimal assumption that they have a positive density at a small neighborhood around the median. In particular, the distribution is allowed to output unbounded values and is not required to have finite moments. We compute the exact, up-to-constant terms, statistical rate of estimation for the median by providing nearly-tight upper and lower bounds. Furthermore, we design a polynomial-time differentially private algorithm which provably achieves the optimal performance. At a technical level, our results leverage a Lipschitz Extension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined ``typical" instances of the samples.
Author Information
Christos Tzamos (UW-Madison)
Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University)
Ilias Zadik (NYU)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Spotlight: Optimal Private Median Estimation under Minimal Distributional Assumptions »
Tue. Dec 8th 03:50 -- 04:00 PM Room Orals & Spotlights: Social/Privacy
More from the Same Authors
-
2021 Spotlight: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2022 Poster: First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces »
Michael Jordan · Tianyi Lin · Emmanouil-Vasileios Vlatakis-Gkaragkounis -
2022 Poster: Linear Label Ranking with Bounded Noise »
Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos -
2022 Poster: On the convergence of policy gradient methods to Nash equilibria in general stochastic games »
Angeliki Giannou · Kyriakos Lotidis · Panayotis Mertikopoulos · Emmanouil-Vasileios Vlatakis-Gkaragkounis -
2022 Poster: Perfect Sampling from Pairwise Comparisons »
Dimitris Fotakis · Alkis Kalavasis · Christos Tzamos -
2021 Poster: ReLU Regression with Massart Noise »
Ilias Diakonikolas · Jong Ho Park · Christos Tzamos -
2021 Poster: Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2021 Poster: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Poster: On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond »
Angeliki Giannou · Emmanouil-Vasileios Vlatakis-Gkaragkounis · Panayotis Mertikopoulos -
2020 Poster: No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras -
2020 Spotlight: No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras -
2020 Poster: The All-or-Nothing Phenomenon in Sparse Tensor PCA »
Jonathan Niles-Weed · Ilias Zadik -
2019 Poster: Efficiently avoiding saddle points with zero order methods: No gradients required »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2019 Poster: Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2019 Spotlight: Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras