Talk by Mahdi Haghifam (Toyota Technological Institute at Chicago)
summary
Shows that differentially private gradient descent incurs a linear R penalty for geometric median but a new private algorithm localizes to the data so error depends on a quantile radius (radius containing ~60% of points) not the worst-case R. Method uses private estimation of that radius, repeated coarse-to-fine DP-SGD phases (about log(R/radius) rounds) or an inverse-sensitivity sampler; runtime and sample complexity scale with log R (later improved to linear time) and experiments (d≈200, n≈3k, ε≈3) improve over DP-SGD.
AI-written summary · about
chapters (7)
- 0:00Private geometric median intro
- 1:06DP gradient descent problem
- 8:29Geometric median for private optimization
- 17:10Algorithm design intuition
- 24:35Key algorithm property
- 28:55Takeaways and future work
- 34:00Q&A
related talks
01h 14mTutorial: Privacy, Part II
58mLarge-Scale Private Learning, Part III
47mPrivate targeting strategies
17mData privacy and reliable learning
01h 02mLarge-Scale Private Learning, Part I
01h 07mLarge-Scale Private Learning, Part II
37mUser-level and federated local differential privacy
33mPrivacy of Decentralized Machine Learning