Private Center Points and Learning of Halfspaces
summary
Provides an (ε,δ)-private algorithm that finds an approximate center point (Tukey depth ≥ n/(2d+1)) of points on a finite grid and uses that to privately learn halfspaces over X^d. It combines Tukey depth as the quality score, the exponential mechanism plus a 1‑D private optimizer for concave functions (from 2015), and discretization; sample complexity is polynomial in d (about d^{2.5}·2^{O(log|X|)}) and matches a lower bound of Ω(d+log|X|) up to factors. The algorithm is (ε,δ)-DP and yields a private halfspace learner; runtime is efficient mainly for constant d.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:37Talk Outline
- 4:02Remarks
- 11:58Warmup: Interior Point
- 21:56Point in the Convex Hull: Exponential Mechanism
- 33:08Quasi-concave Functions
- 35:28Quasi-concave: Example
- 37:32Point in the Convex Hull: Conclusion
- 40:49Combing the Halfspaces II
related talks
36mPrivately Learning High-Dimensional Distributions
01h 02mLarge-Scale Private Learning, Part I
36mTalk by Mahdi Haghifam (Toyota Technological Institute at Chicago)
26mGeneralized Private Selection and Testing with High Confidence
17mData privacy and reliable learning
58mLarge-Scale Private Learning, Part III
30mEfficiently Computing Similarities to Private Datasets
37mUser-level and federated local differential privacy