Spend Free Arithmetic, Not Bandwidth: Block-Reuse Variance Reduction for Memory-Bound Optimization

When a model is fit to a large dataset such as a linear classifier on millions of examples, most of the running time goes to pulling training examples from main memory, not to doing arithmetic on them. In that regime, called memory-bound, the processor can perform tens of extra operations on every byte it loads at no cost in wall-clock time. Optimization theory ignores this. It counts "gradient evaluations" and treats each one as a unit of work. As a result, variance reduction (a family of stochastic methods that subtract a correction term so their noisy gradient estimates stay accurate near the solution) is judged to cost roughly twice as much per step as plain stochastic gradient descent (SGD), because it evaluates each sampled example at two points. We propose to count cost in bytes moved across the memory bus. Under that count, the second evaluation is almost free. The proposal then goes a step further: an optimizer should deliberately spend the idle arithmetic by running several corrected update steps on each block of data while the block sits in cache, before fetching the next one.

The claim, stated in two sentences, is this. If each data block is loaded once and reused for $r$ variance-corrected inner steps, those steps approximately solve a small proximal subproblem on that block, so each byte of data brings more progress. As long as $r$ stays below the ratio set by the hardware's arithmetic-to-bandwidth balance, the extra work is hidden behind memory transfers. The result should be an accelerated variance-reduced method whose number of bytes needed to reach a given accuracy falls as $r$ grows, while its wall-clock time per byte stays unchanged.

What the two directions contribute

On the optimization side, methods that combine variance reduction with momentum reach rates once reserved for full-gradient methods. Accelerated Variance Reduced Stochastic ADMM (ASVRG-ADMM) combines SVRG-style correction with momentum and proves $O(1/T^2)$ convergence for convex problems and linear convergence for strongly convex ones. Faster and Non-ergodic O(1/K) Stochastic ADMM reaches the lower-bound non-ergodic rate for linearly constrained problems. Both papers state their guarantees in terms of oracle calls and effective passes over the data. They supply the base method we modify, and they share the cost model we reject. StopWasting My Gradients shows that SVRG keeps its linear rate when the anchor gradient (the full-data reference gradient used in the correction term) is only approximate, provided the error shrinks over time. We reuse this inexactness argument, applied to inner subproblems rather than to anchors.

On the hardware side, the papers explain why bytes are the right currency. Can Tensor Cores Benefit Memory-Bound Kernels? (No!) shows on A100 and GH200 GPUs that faster arithmetic units cannot help memory-bound kernels: the theoretical FP64 speedup is capped at 1.33x, and in practice standard CUDA cores beat Tensor Cores on SpMV by 1.09x on A100 and 1.46x on GH200. Extreme Multicore Classification trains linear classifiers on AMD Rome CPUs and finds linear scaling up to 32 threads, then a memory wall that NUMA-aware replication does not remove. In A filtered bucket-clustering method for projection onto the simplex and the ℓ1 ball, more than half the runtime of a proximal projection is spent streaming the vector in and writing it out. These papers motivate the proposal: the extra arithmetic exists, and nothing else is using it.

Variance Reduction With Sparse Gradients is the closest attempt to make variance reduction cheaper. It reduces per-step cost by updating only a subset of coordinates. That saves arithmetic, but the authors acknowledge that scattered memory access can erase the wall-clock gain on dense-optimized hardware. In the memory-bound regime arithmetic is not the scarce resource, so we move in the opposite direction: we spend more arithmetic per byte instead of less.

Core Claim

Let $\beta$ be the bytes needed to load one block of $b$ examples, and let $W$ be the bandwidth. Let $\phi$ be the arithmetic cost of one corrected inner step on that block, and let $P$ be peak compute throughput. The time to process one block with $r$ inner steps is approximately

$$t(r) = \max\left(\frac{\beta}{W},\; \frac{r\,\phi}{P}\right).$$

This is the roofline model applied to one block. The time is flat in $r$ up to $r^\star = \beta P/(\phi W)$, which is the machine balance divided by the arithmetic intensity of a single step. For linear models on CPUs and GPUs, $r^\star$ is plausibly well above 1.

On the algorithm side, running $r$ SVRG-corrected steps on a block approximately solves the block proximal subproblem $\min_x f_B(x) + \langle \nabla F(\tilde x) - \nabla f_B(\tilde x), x\rangle + \tfrac{1}{2\gamma}\|x - x_t\|^2$. Here $f_B$ is the block loss, $\tilde x$ is the snapshot point where the anchor gradient was computed, $\gamma$ is the proximal step size, and $x_t$ is the current iterate. This subproblem is strongly convex, so inner gradient steps converge geometrically. Its error therefore shrinks like $(1-c)^r$ for some $c \in (0,1)$ fixed by the block's conditioning.

We will prove that the outer method is a variance-reduced, accelerated, inexact stochastic proximal-point iteration, analyzed with the decreasing-error technique of StopWasting My Gradients and with momentum in the style of ASVRG-ADMM. Its number of block loads to reach accuracy $\epsilon$ should decrease in $r$ toward the proximal-point limit, because a more exactly solved proximal subproblem tolerates a larger step size $\gamma$. The new object is the resulting byte complexity: the minimum total bytes to reach accuracy $\epsilon$ under a constraint that keeps the method memory-bound. This yields a principled choice $r \approx r^\star$ instead of a tuned guess. The final result we aim for is a matching statement: in the memory-bound regime, no method that touches each byte for $O(r^\star)$ operations can do asymptotically better in byte complexity.

Research Program

The theoretical part has three pieces. The first is the inexact accelerated proximal analysis that gives block loads to accuracy $\epsilon$ as a function of $r$, the block size $b$, and the condition number. The second is the byte-complexity corollary under the time model above. The third extends the analysis to the composite and constrained setting of stochastic ADMM, where the inner subproblem includes an $\ell_1$ or simplex term. That extension is where the projection result from A filtered bucket-clustering method becomes a component: its projection is itself memory-bound, and we would apply it to a cached block rather than to a full vector.

The systems part builds fused kernels in which a block is loaded once and all $r$ inner steps run on it. On the GPU, the block lives in shared memory and L2 cache. On the CPU, it lives in L2 or L3 cache per NUMA domain, following the replication approach of Extreme Multicore Classification. We will measure actual bus traffic with hardware counters rather than inferring it.

Baselines

The naive reference point is plain mini-batch SGD with a tuned step-size decay, run at the largest batch size below the roofline knee. That is the setting that already makes SGD as bandwidth-efficient as it can be. The proposal must beat it in wall-clock time to a fixed suboptimality, such as $10^{-6}$ relative objective gap.

The strongest existing method is ASVRG-ADMM from Accelerated Variance Reduced Stochastic ADMM, together with its unconstrained accelerated-SVRG specialization for logistic regression. It has the best proven rates in the file, and it was evaluated on HIGGS and SUSY, which are large enough to exceed cache. That paper reports no scalar value for objective gap or time on HIGGS ("no reported result found on Lacuna for ASVRG-ADMM wall-clock on HIGGS"), so we will rerun it ourselves.

We also include growing-batch SVRG from StopWasting My Gradients, because it is the existing method that reduces memory reads most directly. For the interpolating case, we include accelerated constant-step SGD from Fast and Faster Convergence of SGD for Over-Parameterized Models. It needs no snapshots and is the cheapest accelerated method per byte when its growth condition holds.

Fairness rules apply to every method. All share the same data layout, precision, thread or GPU count, and the same fused data-loading code path. Each gets an equal hyperparameter search budget (the same number of configurations per method, with a step-size grid over the same range). Results are reported as the median over five seeds.

Two ablations isolate the key ingredient. The first is ASVRG with a fused two-point kernel but $r=1$: it gets the "second evaluation is free" saving without block reuse. The second is block reuse without the variance-reduction correction, with $r$ local SGD steps per block. "Beating" the baselines means a lower median wall-clock time to target accuracy than both the strongest baseline and the $r=1$ fused ablation, with lower measured bytes per unit of objective decrease.

Why not just…?

Why not just increase the mini-batch size until the workload becomes compute-bound? A larger batch raises arithmetic per step only by reading more data, so bytes still scale with work done. Without variance correction, the method stays at the stochastic rates that ACC-SADMM's analysis identifies as suboptimal for constrained problems (Faster and Non-ergodic O(1/K) Stochastic ADMM). Extreme Multicore Classification also shows that feeding more data per core does not get past the bandwidth wall. Block reuse instead raises arithmetic per byte. The large-batch SGD baseline directly tests whether this difference matters.

Why not just fuse the SVRG kernel so both gradient evaluations share one load? This is the real threat, and it is part of the idea. If the $r=1$ fused ablation captures nearly all of the speedup, then the reuse-and-proximal mechanism adds nothing, and we would reduce the contribution to a byte-complexity analysis of fused variance reduction. The decisive measurement is the wall-clock curve as a function of $r$. We predict a decline up to roughly $r^\star$ and a rise beyond it. A flat curve would refute the proposal.

Why not just reuse each cached block for several plain SGD steps, as in data echoing? Repeated uncorrected steps on one block pull the iterate toward that block's own minimizer, which biases the result and leaves an error floor. The SVRG correction term is what makes the block subproblem consistent with the full objective. The uncorrected reuse ablation should show this floor. If it does not show one on interpolating data, that would be consistent with Fast and Faster Convergence of SGD, and we would report that the correction is needed only when interpolation fails.

Why not just use faster matrix hardware? Can Tensor Cores Benefit Memory-Bound Kernels? (No!) already answers this for memory-bound kernels: the theoretical FP64 gain is capped at 1.33x, and the measured result is a slowdown. Our approach does not depend on extra arithmetic speed, only on arithmetic that is already sitting idle.

Proposed Experiments

The workloads are L2-regularized logistic regression and graph-guided fused Lasso on HIGGS (7.7 million samples) and SUSY (3.5 million samples), with a9a, w8a, and CovType as small, cache-resident controls. On the controls the method should show no advantage, because they are not memory-bound. A one-vs-rest linear model on AmazonCat tests the multicore wall beyond 32 threads reported in Extreme Multicore Classification. The platforms are a many-core AMD CPU and an A100-class GPU.

The metrics are wall-clock time to a fixed objective gap, measured DRAM or HBM bytes to reach that gap, achieved bandwidth as a fraction of the STREAM-measured peak, and test accuracy.

There are three decisive checks. First, the wall-clock time to target versus $r$ should have its minimum near the $r^\star$ predicted from measured machine balance, on both platforms, even though the two platforms have different balance points. Second, on the small cache-resident datasets the advantage should vanish, which confirms that the mechanism is bandwidth and not just a better optimizer. Third, beyond 32 CPU threads, where plain methods stop scaling, block reuse should keep scaling longer, because each thread demands fewer bytes per unit of progress.