Closing the Loop in Adaptive Subsampling with Recency-Weighted Averages

Fitting a regression or classification model to millions of rows is often too slow, so practitioners fit it on a subsample. The best subsamples are not uniform. They favor points whose gradients are large, such as misclassified examples, high-residual points, or unusual feature vectors. The catch is that the ideal sampling probabilities depend on the parameter you are trying to estimate. The standard fix is two-stage subsampling. A small uniform "pilot" sample gives a rough parameter estimate, that estimate sets the importance probabilities, and a second, larger sample is drawn and fit with inverse-probability weights. The design is open-loop: one pilot, one adaptive draw, one solve. When the pilot is small, noisy, or misses a rare class, every second-stage probability inherits its error, and nothing later corrects it.

We propose to replace the one-shot pilot with a feedback loop. A stochastic optimizer runs on importance-weighted draws. It keeps a recency-weighted average of its iterates, meaning a running mean that puts more weight on recent parameter values. On a geometric schedule, it recomputes the sampling probabilities from that average. The same average is also the final estimator. The recency weighting is what makes the loop work: iterates produced while the probabilities were still poor are forgotten at a polynomial rate, so the final estimate behaves as if it had been sampled with probabilities computed at the true parameter. Pilot size stops being a tuning knob. The approach should help most where two-stage designs are known to struggle, namely small budgets, rare events, and heavy-tailed responses.

Core Claim

Let $\pi$ denote a vector of sampling probabilities over the $n$ data points. Write $g_i(\theta)$ for the per-point gradient of the loss at parameter $\theta$, and $H$ for the full-data Hessian at the full-data optimum $\hat\theta$. An inverse-probability-weighted subsample estimator drawn under $\pi$ has asymptotic covariance

$$V(\pi) = H^{-1}\Big(\tfrac{1}{n^2}\textstyle\sum_{i} \tfrac{g_i(\hat\theta)\,g_i(\hat\theta)^\top}{\pi_i}\Big) H^{-1},$$

and the optimal subsampling literature chooses $\pi$ to minimize the trace of this matrix or of a linear transform of it. The A-optimal criterion minimizes the trace of the covariance itself, and the cheaper L-optimal criterion minimizes the variance of a linear predictor. Both are developed in Optimal Subsampling for Large Sample Logistic Regression and Optimal Subsampling Algorithms for Big Data Generalized Linear Models. The resulting probabilities are $\pi_i \propto \|g_i(\hat\theta)\|$ in the L-optimal and least-squares cases Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares.

Our estimator runs stochastic gradient steps $\theta_t$ on single draws, each weighted by $1/\pi^{(k)}_i$, where $\pi^{(k)}$ are the probabilities in force during epoch $k$. It reports

$$\bar\theta_T = \frac{\sum_{t\le T} t^{\alpha}\,\theta_t}{\sum_{t\le T} t^{\alpha}},$$

the polynomially increasing weighted average with power $\alpha\ge 0$ studied in Revisiting SGD with Increasingly Weighted Averaging. It refreshes $\pi^{(k+1)}_i \propto \max(\|g_i(\bar\theta_{t_k})\|, \delta)$ at times $t_k$ that double each epoch. Here $\delta$ is the probability floor already used by the subsampling methods to stop inverse weights from exploding.

The claim has two parts. First, for generalized linear models with $\alpha>0$, the covariance of $\bar\theta_T$ converges to $V(\pi^\star)$, where $\pi^\star$ is the oracle design computed at $\hat\theta$, whatever the initial pilot. The doubling schedule needs only about $\log_2(T)$ full scoring passes. Second, the finite-sample gap to the oracle is governed by how much averaging mass sits on early epochs. Uniform averaging ($\alpha=0$) keeps that mass and is therefore stuck with the error of the early, poorly informed probabilities.

The intuition for why the stale-probability error vanishes comes from the averaging theory. Polyak–Ruppert-type averaging gives the sandwich covariance of the sampling distribution that generated the gradients. A recency weight of order $t^\alpha$ gives epoch $k$ a share that shrinks like $(t_k/T)^{\alpha+1}$. Every epoch before the probabilities have settled therefore contributes a vanishing fraction of the final covariance.

Relation to Prior Work

Prior work plays three different roles here.

The subsampling papers motivate the gap and supply the probability formulas. Optimal Subsampling for Large Sample Logistic Regression introduces the pilot-then-weighted-fit design and the truncation floor $\delta$. It also notes that asymptotic variance formulas underestimate the true variance under severe imbalance. Optimal Subsampling Algorithms for Big Data Generalized Linear Models extends the design to generalized linear models and supplies the $O(np)$ L-optimal criterion we refresh with. Gradient-based Sampling shows that residual-gradient probabilities beat design-only leverage scores and that Poisson sampling is more efficient than sampling with replacement. Scale-invariant Optimal Sampling for Rare-events Data and Sparse Models shows how badly information is lost when events are rare. All of these fix the probabilities once, from a single pilot. We keep their probability formulas but make them a moving target that converges.

The averaging papers supply the method and also constrain it. Stochastic Gradient Descent for Non-smooth Optimization shows that uniform averaging carries an extra logarithmic factor from early iterates. It also gives an online polynomial-decay recursion that needs no horizon $T$, which is what makes refreshes at unknown stopping times possible. Revisiting SGD with Increasingly Weighted Averaging proves the constraint we must respect: larger $\alpha$ forgets faster but makes the estimate more sensitive to noise in the final steps. Under importance sampling, those final steps carry inverse weights $1/\pi_i$, so this tension is sharper here than in their uniform-sampling setting, and we must measure it rather than assume it away.

Two papers sit closest to our proposal. On Adaptive Stochastic Optimization for Streaming Data pairs a streaming Newton method with recency-weighted iterate averaging, but its data arrive passively. It never chooses which points to sample. Hessian averaging in stochastic Newton methods uses rapidly growing weights to forget early estimates, but it averages curvature matrices rather than iterates, and its subsamples are uniform. Not All Samples Are Created Equal closes a sampling loop in deep learning. It scores a large candidate batch with the current iterate and trains the last iterate without any averaging. Our proposal differs from each of these on a specific point. The sampling reference parameter is the averaged trajectory rather than the noisy current iterate. The final estimator is that same average. The averaging weights are chosen so that the design converges to the oracle.

Research Program

The theoretical work targets logistic regression and least squares. We will prove that the closed-loop estimator is asymptotically normal with covariance $V(\pi^\star)$. The proof treats the inverse-weighted gradients as a martingale difference sequence, conditionally unbiased given the past, because each $\pi^{(k)}$ is fixed before epoch $k$'s draws.

We will then derive a finite-sample bound that splits the excess error over the oracle into three terms. The first is a stale-design term that depends on $\alpha$ and the refresh schedule. The second is the averaging bias term from initialization. The third is a late-noise term that grows with $\alpha$ and with $\max_i 1/\pi_i$. The bound should yield a concrete rule for choosing $\alpha$ together with the floor $\delta$. This connects two tuning problems the file lists as open: choosing the floor and choosing the averaging power.

The empirical work isolates three questions. Does closing the loop help at matched cost? Is the averaged reference what helps, as opposed to any adaptive reference? Does recency weighting, specifically, remove pilot sensitivity?

Baselines

The naive reference is uniform subsampling at the same total number of drawn points, fit exactly by inverse-weighted maximum likelihood. It shows how much adaptive sampling buys at all.

The strongest existing method is the two-step estimator with A-optimal and L-optimal probabilities from Optimal Subsampling for Large Sample Logistic Regression and Optimal Subsampling Algorithms for Big Data GLMs. For least squares, the matching method is Gradient-based Sampling with Poisson draws. These are the methods practitioners actually use, and they already have asymptotic optimality when the pilot is large. We will run them with the same total sample budget (pilot size plus second-stage size equal to the closed-loop method's number of draws). They will get the same number of full-data scoring passes, letting them spend extra passes on a larger pilot, and the same grid over pilot fraction and floor $\delta$. The file reports no MSE numbers for these methods on SUSY, Census, Million Song, CASP, or NEWS; the only quantitative claims are runtime. On a dataset with $n=10^6, d=50$, subsampling takes seconds where the full-data fit takes minutes Optimal Subsampling for Large Sample Logistic Regression. On 5 million rows, gradient-based sampling is roughly $10\times$ faster than approximate leverage sampling Gradient-based Sampling. We will therefore rerun all baselines ourselves.

Beating the strongest baseline means one of two things. The first is lower empirical MSE against the full-data estimate at equal budget and passes, by more than the replicate standard error, in the small-pilot and rare-event regimes. The second is matching the baseline's best-tuned MSE without tuning the pilot fraction at all. If neither happens, the claim fails.

The loop-without-averaging competitor is importance-sampled SGD that scores points with the current iterate and reports the last iterate, in the style of Not All Samples Are Created Equal, run with the same refresh schedule.

Three ablations isolate the key ingredient. The first keeps everything fixed but uses uniform Polyak–Ruppert averaging ($\alpha=0$). The second uses the current iterate rather than the average as the scoring reference. The third uses suffix averaging over the last half of the run, given oracle knowledge of $T$.

As a ceiling, we include an oracle that samples with $\pi^\star$ computed at the full-data estimate. The closed-loop method should approach this ceiling as the budget grows.

Why not just…?

Why not just use a bigger pilot? For large budgets, this may genuinely be enough, because the two-step estimator is already asymptotically equivalent to the oracle when the pilot grows. We concede this regime in advance. The proposal's claim lives where the pilot cannot grow cheaply or fails silently. One such case is when the total budget is a few thousand points. Another is a rare-events problem, where a uniform pilot may contain almost no positives Scale-invariant Optimal Sampling for Rare-events Data. A third is an outlier-contaminated pilot. Sweeping pilot fraction against MSE for the two-step baseline, alongside the untuned closed-loop curve, settles whether a well-chosen pilot erases the advantage.

Why not just iterate the two-step estimator, re-solving exactly on each new sample and resampling? This is the most serious threat. It is a closed loop too, with exact solves instead of stochastic steps. Without iterate averaging, though, it must either discard earlier samples or combine estimators from different designs with ad hoc weights. Each round also costs a full weighted solve. We will run it with the same doubling schedule and budget. If it matches our MSE at equal passes and equal time, then the contribution reduces to "refreshing helps" and the averaging is not needed. That would be a negative result for the averaging ingredient, and we will report it as such.

Why not just score with the current iterate, as deep-learning importance sampling does? The current iterate fluctuates with the very draws it selects, so high-gradient points can keep themselves in the sample. Not All Samples Are Created Equal reports wins over uniform sampling, such as 28.06% versus 33.74% test error on MIT67 fine-tuning, but it never compares against an averaged reference. The current-iterate ablation answers this directly. We expect its advantage to be smallest on well-conditioned least squares and largest on ill-conditioned or rare-event logistic regression.

Why not just apply a standard exponential moving average? A fixed-decay moving average forgets at a constant rate, so its lag never shrinks, and it lacks the rate guarantees of polynomial weighting EMA Without the Lag. We include it as an extra averaging variant at a tuned decay. If it matches polynomial weighting, the practical recommendation simplifies, and the theory still explains why.

Proposed Experiments

The main study uses logistic regression on SUSY ($n=5\times 10^6$, $d=18$) and Census Income, the generalized linear model on the Million Song Dataset, and least squares on CASP, NEWS, and the synthetic Gaussian-mixture designs GA and MG1–MG3 from Gradient-based Sampling. We add a synthetic rare-event logistic generator with positive rates from 1% down to 0.05%, and a contaminated-pilot variant in which a fraction of rows have flipped labels or heavy-tailed noise.

The primary metric is empirical MSE of the estimate relative to the full-data estimate, averaged over 500 replicates, plotted against total draws and against wall-clock time. Secondary metrics are held-out log-loss, and coverage of confidence intervals built from $V(\pi^{(K)})$, the plug-in covariance at the final probabilities. Coverage tests whether the variance underestimation noted in Optimal Subsampling for Large Sample Logistic Regression persists or shrinks under the closed loop.

Three checks decide the claim. The first is a pilot-sensitivity curve: the closed-loop MSE should be flat across initial pilot sizes, while the two-step MSE degrades sharply as the pilot shrinks, especially at low positive rates. The second is the averaging-power sweep: MSE should improve from $\alpha=0$ to moderate $\alpha$ and then worsen as the floor $\delta$ shrinks, with the turning point matching the derived rule. The third is the oracle gap: the ratio of closed-loop MSE to oracle-design MSE should approach one as the budget grows. A gap that persists would falsify the asymptotic claim.

A secondary check reuses the candidate-batch scoring of Not All Samples Are Created Equal on CIFAR-10 with ResNet20. Scores come from the polynomially weighted average rather than the current network. This is an exploratory test of whether the averaged-reference effect survives outside convex models; no theory is claimed there.