Timezone: »
Poster
Nearly Optimal Private LASSO
Kunal Talwar · Abhradeep Guha Thakurta · Li Zhang
We present a nearly optimal differentially private version of the well known LASSO estimator. Our algorithm provides privacy protection with respect to each training data item. The excess risk of our algorithm, compared to the non-private version, is $\widetilde{O}(1/n^{2/3})$, assuming all the input data has bounded $\ell_\infty$ norm. This is the first differentially private algorithm that achieves such a bound without the polynomial dependence on $p$ under no addition assumption on the design matrix. In addition, we show that this error bound is nearly optimal amongst all differentially private algorithms.
Author Information
Kunal Talwar (Google)
Abhradeep Guha Thakurta (APPLE Inc)
Li Zhang (Google)
More from the Same Authors
-
2021 : Mean Estimation with User-level Privacy under Data Heterogeneity »
Rachel Cummings · Vitaly Feldman · Audra McMillan · Kunal Talwar -
2020 Poster: Rankmax: An Adaptive Projection Alternative to the Softmax Function »
Weiwei Kong · Walid Krichene · Nicolas E Mayoraz · Steffen Rendle · Li Zhang -
2019 Poster: Private Stochastic Convex Optimization with Optimal Rates »
Raef Bassily · Vitaly Feldman · Kunal Talwar · Abhradeep Guha Thakurta -
2019 Spotlight: Private Stochastic Convex Optimization with Optimal Rates »
Raef Bassily · Vitaly Feldman · Kunal Talwar · Abhradeep Guha Thakurta -
2018 Poster: Adversarially Robust Generalization Requires More Data »
Ludwig Schmidt · Shibani Santurkar · Dimitris Tsipras · Kunal Talwar · Aleksander Madry -
2018 Poster: Model-Agnostic Private Learning »
Raef Bassily · Abhradeep Guha Thakurta · Om Thakkar -
2018 Spotlight: Adversarially Robust Generalization Requires More Data »
Ludwig Schmidt · Shibani Santurkar · Dimitris Tsipras · Kunal Talwar · Aleksander Madry -
2018 Oral: Model-Agnostic Private Learning »
Raef Bassily · Abhradeep Guha Thakurta · Om Thakkar -
2017 Poster: Practical Locally Private Heavy Hitters »
Raef Bassily · Kobbi Nissim · Uri Stemmer · Abhradeep Guha Thakurta