Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

arXiv:2608.18402 · math.ST, cs.DS, cs.LG, stat.TH · Submitted 2026-08-19 · Read on arXiv

math.ST, cs.DS, cs.LG, stat.TH

Submitted: 2026-08-19

Updated: 2026-09-15

Comments: shortened arxiv abstract

Code: https://github.com/SpencerCompton/adaptive-regression

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Fisher Information — 13× in this paper · explained in 3 episodes
• Statistical Query — 12× in this paper
• Benchmark — 6× in this paper · explained in 2 episodes
• VC Dimension — 5× in this paper · explained in 2 episodes
• Accuracy — 4× in this paper · explained in 1 episode
• Theoretical Guarantees — 3× in this paper · explained in 2 episodes
• Adaptation — 2× in this paper · explained in 1 episode
• Adaptivity — 2× in this paper · explained in 1 episode
• Core — 2× in this paper · explained in 2 episodes
• Ablation — 1× in this paper · explained in 1 episode
• Adam — 1× in this paper · explained in 2 episodes
• Annual Symposium on Foundations of Computer Science — 1× in this paper
• Convergence Guarantees — 1× in this paper · explained in 3 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Influence Functions — 1× in this paper · explained in 2 episodes
• Optimal Transport — 1× in this paper · explained in 5 episodes
• Robustness — 1× in this paper · explained in 5 episodes
• Sample Complexity — 1× in this paper · explained in 15 episodes

Sources

• Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
• Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
• The Statistical Complexity of Interactive Decision Making
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Performance of the empirical median for location estimation in heteroscedastic settings
• High-Dimensional Statistics: Reflections on Progress and Open Problems
• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Related papers

• Conformal Prediction for Dyadic Regression Under Complex Missingness
• Bentkus-type asymptotic e-values
• High-Dimensional Asymptotics of Differentially Private PCA
• KL Convergence Guarantees for Score diffusion models under minimal data assumptions
• Geometric bias in eigenspace perturbation under random heterogeneous noise
• On the Asymptotic Inadmissibility of Double Machine Learning Estimators Under Structure-Agnostic Models