2024-06-30-brown24b.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract	Original Papers	We present a sample- and time-efficient differentially private algorithm for ordinary least squares, with error that depends linearly on the dimension and is independent of the condition number of $X^\top X$, where $X$ is the design matrix. All prior private algorithms for this task require either $d^{3/2}$ examples, error growing polynomially with the condition number, or exponential time. Our near-optimal accuracy guarantee holds for any dataset with bounded statistical leverage and bounded residuals. Technically, we build on the approach of Brown et al. (2023) for private mean estimation, adding scaled noise to a carefully designed stable nonprivate estimator of the empirical regression vector.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	brown24b	0	Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract	750	751	750-751	750	false	Brown, Gavin and Hayase, Jonathan and Hopkins, Samuel and Kong, Weihao and Liu, Xiyang and Oh, Sewoong and Perdomo, Juan C and Smith, Adam	given family Gavin Brown given family Jonathan Hayase given family Samuel Hopkins given family Weihao Kong given family Xiyang Liu given family Sewoong Oh given family Juan C Perdomo given family Adam Smith	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/brown24b/brown24b.pdf