CS Paper Radar

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

Spencer Compton, Tselil Schramm

cs.DS math.STcs.LG ·submitted 2026-08-19 00:17 UTC · v2
theory

Abstract

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive $n$ pairs $(X_i,Y_i)$ with labels $Y_i=X_i^\topβ+\varepsilon_i$, where $\varepsilon_i\sim N(0,σ_i^2)$ and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples $m$ for which $σ_i^2\le1$ (larger $m$ is easier). We obtain a polynomial-time estimator with rate $\tilde{O}((nd^3/m^4)^{1/6})$ when $m\gg d^{3/4}n^{1/4}$, as well as nearly-matching lower bounds. For $d=O(1)$, our estimator achieves error $o(1)$ when $m\gg n^{1/4}$, whereas $L_1$ regression and other traditional approaches require $m\gg n^{1/2}$. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution $p$, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows $p$. We introduce a (computationally inefficient) adaptive estimator that, so long as $p$ is a mixture of $k$ symmetric log-concave densities, achieves error comparable with the optimal estimator that knows $p$ and has $\tildeΘ(n/k)$ samples. For $k=1$, we show that $L_q$ regression (with data-dependent $q$) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where $X_i\sim N(0,I_d)$, $m$ unknown samples are noiseless, and the rest have error $\varepsilon_i\sim N(0,1)$. We conjecture that recovering $β$ up to error $\ll\sqrt{d/n}$ (or exactly) may have an information-computation gap between $m=d+1$ and $m\sim d^{3/4}n^{1/4}$, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Comment
shortened arxiv abstract

Closest papers

Nearest neighbours by meaning across the whole index.

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

cs.LG stat.MLmath.OC ·2026-11-01 ·Anish Senapati, Jose Blanchet
similarity 0.58
Abstract · 37 pages, 4 figures

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the $K$ nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension $d\ge2$. In particular, for $d>4$, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of $\widetilde O(n^{-2/d})$ using neighborhoods sizes (i.e. $K=K_n$) of order $\widetilde O(n^{2(d-1)/(2d-1)})$ for general convex functions and $\widetilde O(n^{(d+1)/(d+2)})$ for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.

0.35

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

cs.CC math.OCcs.LG ·2026-08-10 ·Jikai Jin
theory similarity 0.56
Abstract

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

0.38

Sample-Optimal Estimation of the Fréchet Inception Distance

cs.LG cs.CVcs.DSmath.ST+1 ·2026-10-05 ·Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
code/datahot direction similarity 0.56
Abstract · Our code is available at https://github.com/zys996/sample-optimal-fid-estimation

The Fréchet Inception Distance (FID) is widely used to evaluate generative models, but its empirical plug-in estimator suffers from finite-sample bias [BSAG18, CF20]. We study the sample complexity $n$ of estimating FID to error $ε$ between $d$-dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. Our contributions are threefold. (1) We establish tight finite-sample $Θ(\frac{d^2}{n})$ bias and $Θ(\frac{d}{n} + \frac {d^2} {n^2})$ variance bounds for the empirical plug-in estimator, establishing a $\gtrsim d^2$ sample complexity. (2) To debias the empirical plug-in estimator, we generalize the ${\rm FID}_\infty$ estimator of [CF20] to extrapolation methods of arbitrary order $k$. We further prove tight bias and variance bounds of $Θ(\frac{d^{k + 2}}{n^{k + 1}})$ and $Θ(\frac d n + \frac{d^2}{n^2})$ for any order-$k$ extrapolation under our framework. (3) We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm using debiasing techniques inspired by U-statistics. We show that RTD achieves an $O(\frac d {ε^2})$ sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians validate the predicted residual bias and support the tightness of our bounds. On ImageNet with Inception embeddings, RTD achieves the lowest mean estimation error at the standard 50K sample budget, while our second-order variance-aware extrapolation estimator (VALE$_2$) uses only 10K samples to achieve accuracy comparable to FID$_\infty$ at 50K samples.

0.46

On Sample Complexity Bounds for Frequency-Domain System Identification

eess.SY ·2026-10-22 ·Arya Honarpisheh, Mario Sznaier
theory similarity 0.55
Abstract

We study the sample complexity of frequency-domain system identification with bounded measurement noise. We focus on interpolatory identification algorithms, which return models consistent with both the data and a priori constraints. For equally spaced samples, we sharpen previous worst-case bounds on the consistency-set radius. Its excess above the noise level decays as $N^{-2}$, where $N$ is the number of samples, and a matching lower bound shows that this rate is tight. We then examine whether bounded stochastic noise allows identification below the noise level. We show that high-probability error bounds can converge to zero. Their convergence rate depends on how strongly the noise distribution is concentrated near the boundary of the noise set. For example, noise uniformly distributed on a disk gives an upper bound of order $(\log N/N)^{2/3}$. Numerical experiments examine these convergence rates and the effect of the noise distribution on the identification error.

0.20

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

cs.LG stat.MLmath.OCmath.ST ·2026-10-31 ·Denis Belomestny, Alexey Naumov, Sergey Samsonov
theory similarity 0.54
Abstract

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.

0.28

Linear Regression with Self-Selection Bias in Polynomial Time

cs.DS math.STcs.LGstat.ML ·2026-11-12 ·Felix Zhou
similarity 0.54
Abstract

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.

0.26

Stochastic gradient descent with initial regularization

cs.LG math.OCstat.ML ·2026-08-24 ·Nabil Kahalé
theory similarity 0.54
Abstract · 33 pages

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$, where the number of training samples is of order $m$. For another value of the source parameter, we obtain, for any $ε>0$, bounds of order $m^{-3+ε}$, provided that the capacity parameter exceeds $ε^{-1}$. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.

0.35

A Short Note on Algorithms For The Noisy $k$-XOR Problem

cs.DS cs.CCmath.ST ·2026-10-19 ·Kiril Bangachev
similarity 0.54
Abstract

This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time $n^{O(k)}$ where $m = n^β, β\in [0,k]$ is the number of samples and $\mathsf{Bern}(n^{-δ}),δ\in (0,+\infty)$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $β> 1, δ>1$ based on Gaussian elimination; II. A folklore algorithm when $β\ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $β> δ+ k(1-δ), δ\in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $β> δ+ (k-1)(1-δ), δ\in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.

0.24