Summary of Private Geometric Median, by Mahdi Haghifam et al.
Private Geometric Median
by Mahdi Haghifam, Thomas Steinke, Jonathan Ullman
First submitted to arxiv on: 11 Jun 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: None
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper explores differentially private (DP) algorithms for computing the geometric median (GM) of a dataset. Given n points in Rd, the goal is to find a point θ that minimizes the sum of Euclidean distances to these points. Existing methods like DP-GD require strong prior knowledge about the data’s location within a ball of radius R, and their excess risk depends linearly on R. The paper asks whether we can design an efficient and private algorithm with an excess error guarantee that scales with the (unknown) radius containing the majority of datapoints. The main contribution is two polynomial-time DP algorithms for private GM with an excess error guarantee scaling with the effective diameter of datapoints. Additionally, the paper proposes an inefficient algorithm based on inverse smooth sensitivity mechanism satisfying pure DP. The results are complemented by a lower bound and demonstrate the optimality of polynomial-time algorithms in terms of sample complexity. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper is about making sure that computer programs can keep secrets. It’s trying to find a way to do this when you’re looking at a lot of data points. Right now, there are ways to do this, but they require knowing something about where the data is located. The goal is to make an algorithm that works without needing this information. The researchers came up with two new algorithms that can do this and showed that these algorithms are better than previous ones. |
