Is Interaction Necessary for Distributed Private Learning?
summary
Proves that local differential privacy forces a tradeoff between accuracy and rounds: one-dimensional convex ERM gets optimal O(1/√(n)ε) error with zero adaptivity by reducing to median estimation and using binary tree aggregation per device, while general p‑dimensional ERM needs either gradient‑based noise‑stable methods (≈√(p)/(nε^2) error) or cutting‑plane style algorithms that require ≈p·log(1/α) adaptive rounds to reach error α. Provides convex function constructions (max of shifted pieces) that yield matching lower bounds showing adaptivity of Ω(log(1/α)) or 1/α^2 regimes is necessary.
AI-written summary · about
chapters (10)
- 0:00Start
- 7:15Ideal scenario: Complete parallelism
- 10:28Example: Linear regression
- 11:59This work - Upper bounds
- 14:33This work - Lower bound
- 18:12Previous work
- 19:52Private learning with single parameter Idea: Reduce empirical risk minimization (ERM) to finding median
- 20:39ERM in one-dimension equivalent to median
- 25:17Private median estimation
- 38:14This work Distributed private learning with local differential privacy
related talks
17mData privacy and reliable learning
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
01h 02mLarge-Scale Private Learning, Part I
33mDistributed Learning, Communication Complexity, and Privacy
37mUser-level and federated local differential privacy
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
21mDimension-free Private Mean Estimation for Anisotropic Distributions