Abstract: Differentially private (DP) algorithms typically exhibit a significant dependence on the dimensionality of their input, as their error or sample complexity tends to grow polynomially with the dimension. This cost of dimensionality is inherent in many problems, as Bun, Ullman, and Vadhan (STOC 2014) showed that any method that achieves lower error rates is vulnerable to tracing attacks (also known as, membership inference attacks). Unfortunately, such a cost is usually too high in many real-world scenarios like training large neural networks where the number of parameters (the ambient dimension) is very high.

On the positive side, the lower bounds do not rule out the possibility of reducing the error rates for “easy” inputs. But what are “easy” inputs? And, how likely is it to see such inputs in real-world scenarios?

In this talk, I’ll present a few ways to quantify “easiness” for the fundamental task of private averaging and support them with upper and lower bounds. In particular, I’ll show types of properties that are sufficient and necessary for eliminating the polynomial dependency in the dimension. I’ll end the talk by presenting several future research directions. 

The talk is mainly based on the following three papers:

(1) FriendlyCore https://arxiv.org/abs/2110.10132 (joint with Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer, ICML 2022),

(2) https://arxiv.org/abs/2307.07604 (joint with Naty Peter and Jonathan Ullman, COLT 2024), and

(3) https://arxiv.org/abs/2402.06465 (2024)

Bio: 

Eliad Tsfadia is a second-year postdoctoral researcher in the Department of Computer Science at Georgetown University, hosted by Prof. Kobbi Nissim. His first year was supported in part by the Fulbright program. He completed his Ph.D. at Tel Aviv University under the supervision of Prof. Iftach Haitner.  In addition, Eliad was a research intern at Google Research – Israel (2019-2022), a part-time security researcher at IBM Research – Haifa (2017-2019), and a full-time software engineer, team leader, and officer (Major) in the technological unit of the Intelligence Corps at IDF (2008-2017). Eliad’s main research interests are data privacy and cryptography.