Research map / Learning theory and algorithms / Matrix and tensor methods
High Dimensional Linear Regression using Lattice Basis Reduction
Ilias Zadik, David Gamarnik
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 changed | Where | Measured | Effect |
|---|---|---|---|
| Use lattice basis reduction with finite-precision truncation under Q-rationality | High-dimensional linear regression with bounded adversarial noise · High-dimensional linear regression | exact 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 noise | exact recovery probability: 1-O\left(\frac{1}{np}\right) | Improved |
| Use ELO lattice reduction for integer-valued regression | ELO · Integer linear regression with iid entries of X | exact recovery probability: 1-O \left(\frac{1}{np} \right) | Improved |
| Choose the LBR truncation level within the stated interval | LBR · High-dimensional linear regression, random noise | exact 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 range | LBR · Noisy high-dimensional linear regression | exact recovery | Hurt |
| Use the LBR method in the low-sample, large-RQ Gaussian-noise regime | LBR · 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 threshold | Any 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 1 | ELO · Synthetic instances, p=30, n=1,10,30 | exact recovery fraction | Improved |
| Use larger α values in ELO synthetic instances | ELO · Synthetic instances, p=30 | exact recovery fraction | Mixed |
| Tune LBR truncation between the stated lower and noise-dependent upper bounds | LBR · Synthetic instances, p=30, n=10 | exact recovery fraction: (2n+p)^2/2n<N<\log (1/\sigma) | Improved |
Closest papers by meaning
- Linear regression without correspondence (NeurIPS 2017 · similarity 0.91)
- Adaptive Reduced Rank Regression (NeurIPS 2020 · similarity 0.86)
- Distributed High-dimensional Regression Under a Quantile Loss Function (JMLR 2020 · similarity 0.86)
- Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery (ICML 2024 · similarity 0.85)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
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.
