Timezone: »

 
Poster
High Dimensional Linear Regression using Lattice Basis Reduction
Ilias Zadik · David Gamarnik

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #94
in Wed Poster Session A »

We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector \beta^* from n noisy linear observations Y=X \beta^+W in R^n, for known X in R^{n \times p} and unknown W in R^n. Unlike most of the literature on this model we make no sparsity assumption on \beta^. Instead we adopt a regularization based on assuming that the underlying vectors \beta^* have rational entries with the same denominator Q. We call this Q-rationality assumption. We propose a new polynomial-time algorithm for this task which is based on the seminal Lenstra-Lenstra-Lovasz (LLL) lattice basis reduction algorithm. We establish that under the Q-rationality assumption, our algorithm recovers exactly the vector \beta^* for a large class of distributions for the iid entries of X and non-zero noise W. We prove that it is successful under small noise, even when the learner has access to only one observation (n=1). Furthermore, we prove that in the case of the Gaussian white noise for W, n=o(p/\log p) and Q sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level of the noise.

Keywords: Information Theory · Learning Theory · Regression

Author Information

Ilias Zadik (MIT)

I am a CDS Moore-Sloan (postdoctoral) fellow at the Center for Data Science of NYU and a member of it's Math and Data (MaD) group. I received my PhD on September 2019 from MIT , where I was advised by David Gamarnik. My research lies broadly in the interface of high dimensional statistics, the theory of machine learning and applied probability.

David Gamarnik (Massachusetts Institute of Technology)

More from the Same Authors