Timezone: »
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 Qrationality assumption. We propose a new polynomialtime algorithm for this task which is based on the seminal LenstraLenstraLovasz (LLL) lattice basis reduction algorithm. We establish that under the Qrationality assumption, our algorithm recovers exactly the vector \beta^* for a large class of distributions for the iid entries of X and nonzero 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 informationtheoretic level of the noise.
Author Information
Ilias Zadik (MIT)
I am a CDS MooreSloan (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

2021 Poster: On the Cryptographic Hardness of Learning Single Periodic Neurons »
Min Jae Song · Ilias Zadik · Joan Bruna 
2019 Poster: Sparse HighDimensional Isotonic Regression »
David Gamarnik · Julia Gaudio 
2017 : Poster session »
Abbas Zaidi · Christoph Kurz · David Heckerman · YiJyun Lin · Stefan Riezler · Ilya Shpitser · Songbai Yan · Olivier Goudet · Yash Deshpande · Judea Pearl · Jovana Mitrovic · Brian Vegetabile · Tae Hwy Lee · Karen Sachs · Karthika Mohan · Reagan Rose · Julius Ramakers · Negar Hassanpour · Pierre Baldi · Razieh Nabi · Noah Hammarlund · Eli Sherman · Carolin Lawrence · Fattaneh Jabbari · Vira Semenova · Maria Dimakopoulou · Pratik Gajane · Russell Greiner · Ilias Zadik · Alexander Blocker · Hao Xu · Tal EL HAY · Tony Jebara · Benoit Rostykus 
2014 Poster: Hardness of parameter estimation in graphical models »
Guy Bresler · David Gamarnik · Devavrat Shah 
2014 Poster: Structure learning of antiferromagnetic Ising models »
Guy Bresler · David Gamarnik · Devavrat Shah