2022-06-28-chen22d.md

title	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
On the well-spread property and its relation to linear regression	We consider the robust linear regression model $\bm{y} = X\beta^* + \bm{\eta}$, where an adversary oblivious to the design $X \in \R^{n \times d}$ may choose $\bm{\eta}$ to corrupt all but a (possibly vanishing) fraction of the observations $\bm{y}$ in an arbitrary way. Recent work \cite{d2021consistent, d2021consistentICML} has introduced efficient algorithms for consistent recovery of the parameter vector. These algorithms crucially rely on the design matrix being well-spread (a matrix is well-spread if its column span is far from any sparse vector). In this paper, we show that there exists a family of design matrices lacking well-spreadness such that consistent recovery of the parameter vector in the above robust linear regression model is information-theoretically impossible. We further investigate the average-case time complexity of certifying well-spreadness of random matrices. We show that it is possible to efficiently certify whether a given $n$-by-$d$ Gaussian matrix is well-spread if the number of observations is quadratic in the ambient dimension. We complement this result by showing rigorous evidence —in the form of a lower bound against low-degree polynomials— of the computational hardness of this same certification problem when the number of observations is $o(d^2)$.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chen22d	0	On the well-spread property and its relation to linear regression	3905	3935	3905-3935	3905	false	Chen, Hongjie and d'Orsi, Tommaso	given family Hongjie Chen given family Tommaso d’Orsi	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/chen22d/chen22d.pdf