Research map / Learning theory and algorithms / Kernels and regression theory
Random features models: a way to study the success of naive imputation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies zero (naive) imputation for linear prediction under MCAR missingness using a random features model, showing its bias is negligible in both very low and high dimensions, and gives finite-sample SGD bounds.
Problem
Constant (naive) imputation is widely used despite expected large prediction bias; prior theory showed low bias only in high-dimensional linear settings under MCAR. The paper asks whether naive imputation is also competitive in low dimension, and how SGD on zero-imputed data performs.
Approach
Model inputs as random features of a latent variable (finite p, then infinite-dimensional latent space), with MCAR masks; derive exact Bayes risks for zero-imputed linear predictors as a function of input dimension d, and bound the excess risk of averaged SGD on zero-imputed data.
Key results
- Bayes risk of zero-imputed linear predictor exceeds the missing-data Bayes risk by at most a factor rho(d-1)/(p-rho(d-1)-2) when d<p, so naive imputation is near-optimal in low dimension.
- For d>=p, both the imputation bias and missing-data bias vanish at rate p/(rho d) and the Delta_miss decays exponentially in d.
- Averaged SGD on zero-imputed data achieves excess risk of order 1/sqrt(n) in low dimension (d<<p) and in high dimension (d > rho(1-rho)sqrt(n)), with the bias term becoming negligible; extension to MNAR shows the bias vanishes as d grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use zero imputation before linear prediction when ρd ≪ p | Linear random features under MCAR · Low-dimensional regime (ρd ≪ p) | imputation excess risk over the best predictor using missing data: Δ_imp/miss(d)≤[ρ(d-1)/(p-ρ(d-1)-2)]Δ_miss(d) | No clear effect |
| Use zero imputation with many random features | Linear random features under MCAR · High-dimensional regime (d ≫ p) | excess risk over the complete-data Bayes risk: p/[ρd+(1-ρ)p]‖β⋆‖₂² | No clear effect |
| Use zero imputation with an increasing number of random features | General random features under MCAR · Infinite-dimensional latent space | Bayes excess risk over R⋆(∞): λ_imp/d‖f⋆‖_ν² | Helped |
| Use zero imputation as the number of features increases | Random features with MNAR missingness · MNAR, d → +∞ | Bayes excess risk over R⋆(∞): lim_{d→ +∞} R⋆_imp(d)= R⋆(∞) | Helped |
| Train with Polyak-Ruppert averaged SGD on zero-imputed data | Linear random features under MCAR · d<p-1 | excess risk over the missing-data Bayes risk: ρ(1-ρ)d(d-1)/[p(p-ρ(d-1)-2)]‖β⋆‖₂²; [d/(ρn)] [d/(p-ρ(d-1)-2)]‖β⋆‖₂² + ρd/n(σ²+‖β⋆‖₂²) | Mixed |
| Train with Polyak-Ruppert averaged SGD on zero-imputed data | Linear random features under MCAR · d ≥ p | excess risk over R⋆(d): (1/ρ)(p/d)‖β⋆‖₂² + [p/(ρ²(1-ρ)√n)]‖β⋆‖₂² + (σ²+‖β⋆‖₂²)/√n | Helped |
Surprising findings
- Naive zero-imputation is nearly as good as the best missing-data predictor in very low dimension, a regime not previously identified in the literature.
- The imputation-induced bias decays only as 1/d in high dimension, not exponentially, unlike the missing-data bias.
Limitations
- Analysis relies on strong assumptions: Gaussian latent, uniform sphere weights, linear well-specified model, MCAR for main results.
- In high dimension the SGD learning error decays only at slow rate 1/sqrt(n); fast rates are left open.
- Bounds for MNAR settings are asymptotic only, with no SGD rates.
Experimental setup
Metrics: Bayes risk excess risk bias from imputation
Baselines: pattern-by-pattern Bayes predictor Bayes risk on complete random features
Builds on: random features (Rahimi and Recht) impute-then-regress consistency results Ayme et al. zero-imputation linear model analysis averaged SGD (Bach and Moulines)
Closest papers by meaning
- Distribution Shift in Missing Data Imputation: A Risk-Based Perspective and Importance-Weighted Correction under MAR (NeurIPS 2026 · similarity 0.89)
- Imputation for prediction: beware of diminishing returns. (ICLR 2025 · similarity 0.88)
- Prediction models that learn to avoid missing values (ICML 2025 · similarity 0.86)
- Rethinking the Diffusion Models for Missing Data Imputation: A Gradient Flow Perspective (NeurIPS 2024 · similarity 0.86)
- Learning What Not to Impute: An Uncertainty-Aware Diffusion Framework for Meaningful Missingness (NeurIPS 2026 · similarity 0.85)
- Interpretable Generalized Additive Models for Datasets with Missing Values (NeurIPS 2024 · similarity 0.85)
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.