High Dimensional Linear Regression using Lattice Basis Reduction
We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector β * from n noisy linear observations Y = Xβ * + W ∈ R n , for known X ∈ R n×p and unknown W ∈ R n . Unlike most of the literature on this model we make no sparsity assumption on β * . Instead we adopt a regularization based on assuming that the underlying vectors β * have rational entries with the same denominator Q ∈ Z >0 . 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 β * 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.
The paper presents a novel method of exactly recovering a vector of coefficients in high-dimensional linear regression, with high probability as the dimension goes to infinity. The method assumes that the correct coefficients come from a finite discrete set of bounded rational values, but it does not - as is commonplace - assume that the coefficient vector is sparse. To achieve this, the authors extend a classical algorithm for lattice basis reduction. Crucially, this approach does not require the sample size to grow with the dimension, thus in certain cases the algorithm is able to recover the exact coefficient vector from just a single sample (with the dimension sufficiently large).  A novel connection between high-dimensional linear regression and lattice basis reduction is the main strength of the paper. The ideas and algorithms in the paper are presented clearly. The main limitation of the algorithm is the fact that all of the guarantees hold „with high probability as dimension p goes to infinity”. No finite dimension guarantees are offered, which raises the question of whether the proposed algorithm only achieves the desired behavior for combinatorially large dimensions. That would make the „polynomial runtime” guarantee somewhat misleading (since the runtime depends on p). It is worth noting that despite the authors’ claim that taking dimension p to infinity is „very popular in the literature”, after looking at some of the cited works I noticed that typically at least some finite dimension guarantees are offered in these works. Thus, to address this, in addtion to „w.h.p. when p tends to infinity”, the authors could - if at all possible - state the guarantees as „w.p. at least 1-delta for p larger than…”, for example.   Minor comments: - line 76: „so that to” -> „so as to” - line 212: „can be applied,.” -> „can be applied.”