AI Paper Atlas

Research map / Learning theory and algorithms / Matrix and tensor methods

High Dimensional Linear Regression using Lattice Basis Reduction

Ilias Zadik, David Gamarnik

NeurIPS 2018 · Learning theory and algorithms › Matrix and tensor methods · approach: High-dimensional estimation theory · 5 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use lattice basis reduction with finite-precision truncation under Q-rationalityHigh-dimensional linear regression with bounded adversarial noise · High-dimensional linear regressionexact recovery probability: 1-O\left(\frac{1}{np}\right)Improved
Use LBR with iid mean-zero noise of variance at most σ²High-dimensional linear regression · High-dimensional linear regression, iid noiseexact recovery probability: 1-O\left(\frac{1}{np}\right)Improved
Use ELO lattice reduction for integer-valued regressionELO · Integer linear regression with iid entries of Xexact recovery probability: 1-O \left(\frac{1}{np} \right)Improved
Choose the LBR truncation level within the stated intervalLBR · High-dimensional linear regression, random noiseexact recovery: N \geq (1+\epsilon)\left[\frac{(p+2n)^2}{2n}+(2+\frac{p}{n}) \log (RQ)\right]Improved
Increase truncation beyond the noise-safe bit rangeLBR · Noisy high-dimensional linear regressionexact recoveryHurt
Use the LBR method in the low-sample, large-RQ Gaussian-noise regimeLBR · Gaussian white noise; n=o(p/log p), RQ=2^{ω(p)}noise tolerance for exact recovery: \sigma_0:=2^{-\frac{p \log (RQ)}{n}}; \sigma<\sigma_0^{1+\epsilon}Improved
Raise Gaussian noise above the stated information-theoretic thresholdAny recovery mechanism · Gaussian white noise; n=o(p/log p), RQ=2^{ω(p)}exact recovery possibility: \sigma_0:=2^{-\frac{p \log (RQ)}{n}}; \sigma>\sigma_0^{1-\epsilon}Hurt
Set ELO α below 1ELO · Synthetic instances, p=30, n=1,10,30exact recovery fractionImproved
Use larger α values in ELO synthetic instancesELO · Synthetic instances, p=30exact recovery fractionMixed
Tune LBR truncation between the stated lower and noise-dependent upper boundsLBR · Synthetic instances, p=30, n=10exact recovery fraction: (2n+p)^2/2n<N<\log (1/\sigma)Improved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy