Many sparse learning problems have far more candidate features than we can hold in memory. Genomic panels, text vocabularies and engineered feature banks often arrive one column at a time, from disk or from a generator. Greedy coordinate descent is the natural optimizer for these problems. It is a method that updates one model weight at a time and always picks the weight whose gradient is largest, the Gauss-Southwell rule. It can be up to $d$ times faster than picking weights at random, but it assumes every feature is available to be compared at every step. We propose the missing streaming version. Features arrive once, in uniformly random order. The algorithm keeps at most $k$ feature columns in memory. It must decide on the spot whether an arriving feature earns a slot, and it does so by scoring the feature against the current residual of the model it is building.
The random-order assumption is what makes this tractable. If features arrive in random order, the first few percent of them are a fair sample of all of them. That short prefix can be observed without committing to anything. From it the algorithm learns how large a "good" gradient score is, and it uses that calibration to set an admission threshold for the rest of the stream. The same trick gives constant-factor guarantees for irrevocable clustering and submodular selection in random-order streams. Our aim is a single-pass, $O(nk)$-memory sparse regression and classification method whose objective comes within a constant factor of offline greedy coordinate descent run on all $d$ features.
Core Claim
For squared loss $f(w)=\tfrac12\|Xw-y\|^2$ with unit-norm columns $X_j$ and residual $r=y-Xw$, an exact line search along coordinate $j$ lowers the loss by
$$\Delta_j(w) \;=\; \tfrac12 (X_j^\top r)^2 \;=\; \tfrac12 |\nabla_j f(w)|^2 .$$
So the Gauss-Southwell score is exactly the marginal gain of adding feature $j$ to the current model. This identity lets us treat streaming greedy coordinate descent as streaming selection under a cardinality budget. For smooth losses such as logistic loss, the same holds up to the ratio of restricted strong convexity to restricted smoothness. The problem then becomes one where random-order analyses are known to buy constant approximation factors.
The algorithm has three parts. The first is a non-committing prefix phase over the first $\epsilon d$ features. The second is residual-adaptive admission: an arriving column is admitted if its current score exceeds a threshold. That threshold is estimated from the prefix's score order statistics and shrinks as the residual shrinks. The third is swap eviction: when memory is full, a new feature replaces the stored feature with the smallest contribution if it beats it by a constant factor. Each admission triggers a few greedy steps (the GS-q variant for $\ell_1$ penalties) on the stored working set.
The claim we want to establish, in theory and in experiments, has three parts. The method achieves a constant fraction of the loss reduction of the best $k$-feature greedy solution. It degrades gracefully to nothing special under adversarial feature orders. And on correlated designs it beats static one-pass screening, which cannot notice that a feature has become redundant.
Relation to Prior Work
Two results supply the optimization side. Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection proves that Gauss-Southwell converges at rate $1-\mu_1/L$, measured with strong convexity in the $\ell_1$ norm. That can be up to $d$ times faster than random selection, and the paper introduces the GS-q rule for $\ell_1$-regularized objectives. We reuse GS-q as the working-set solver. Accelerating Greedy Coordinate Descent Methods measures how much better the greedy coordinate is than an average one on real data: $\gamma\approx0.016$ on rcv1, "nearly 60 times more effective than an average step." This is our motivating evidence that scoring against the residual matters. If a random feature is nearly useless compared with the best one, a streaming method must find the best ones and not merely sample.
Both papers assume all features are resident. So does Nearest Neighbor based Greedy Coordinate Descent. That paper speeds up the argmax by indexing all columns in a nearest-neighbor structure built offline, which is impossible when columns are seen once. Asynchronous Parallel Greedy Coordinate Descent parallelizes greedy selection but keeps a full shared gradient vector.
The streaming side supplies the analysis technique. A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering uses an uncommitted prefix to set cost baselines for irrevocable choices. Cardinality constrained submodular maximization for random streams and Streaming Submodular Maximization Under Matroid Constraints show that random order sharply improves single-pass selection guarantees. These papers treat the objective as a black-box oracle. Our setting differs in two ways. The marginal gain is a gradient coordinate that changes as the model is refit. And the objective is only approximately submodular, with the approximation ratio governed by feature correlation. We borrow their prefix-and-threshold logic and replace the oracle with coordinate descent. Approximating the Top Eigenvector in Random Order Streams contributes a warning about outliers: rare heavy rows break block concentration and must be buffered explicitly. The analogue here is a rare, very strong feature. Our admission rule must take such a feature immediately, because a prefix-based threshold cannot anticipate it.
The closest applied work is Online Streaming Feature Selection. OSFS admits streaming features by conditional independence tests and prunes redundant ones. It neither assumes nor exploits random order, and it does not optimize a loss. The same paper reports that Grafting, a gradient-threshold streaming method, ran out of memory on Dorothea. We read that as a constraint on our design: a fixed gradient threshold with no memory cap is not acceptable. That is why our threshold is calibrated and our memory is hard-capped.
Research Program
The first deliverable is the algorithm and its analysis for squared and logistic loss. The approximation constant should depend on the prefix fraction $\epsilon$, the budget $k$, and the ratio $\mu_{2k}/L_{2k}$ of restricted strong convexity to restricted smoothness over $2k$-sparse directions. We expect $\epsilon$ to trade a small loss of opportunity against threshold accuracy, as in secretary-type arguments. We will also give a simple adversarial-order construction on which any threshold rule of this kind fails. That construction shows the random-order assumption is doing real work.
The second deliverable is an empirical study. It separates three ingredients: residual-adaptive versus static scoring, prefix-calibrated versus fixed thresholds, and swap eviction versus fill-and-freeze. We will also measure how much each assumption is violated by realistic, non-random feature orders.
Computationally, scoring an arriving column costs one sparse dot product with the residual, $O(\mathrm{nnz}(X_j))$. The working-set solver touches only $k$ columns. Total memory is $O(nk)$ plus the residual, independent of $d$.
Baselines
The naive reference point is reservoir selection. Because the order is random, this amounts to keeping the first $k$ features and running offline GS-q coordinate descent on them. It uses the same memory and one pass, and it shows what random order gives "for free." Our method must beat it by a wide margin on any problem with a sparse true support. Otherwise the prefix machinery is pointless.
The strongest streaming competitor is one-pass marginal screening. Each arriving column is scored against the original labels, $|X_j^\top y|$, and the top $k$ are kept in a heap. GS-q is then run on the survivors. It needs no random-order assumption and is exactly optimal among static scores, so it is the baseline most likely to embarrass us. It gets identical memory and data, and the same solver and regularization path tuned on the same validation split. Beating it means lower final objective and higher test accuracy at equal $k$ on correlated designs.
We also run OSFS and Fast-OSFS from Online Streaming Feature Selection. Each is followed by GS-q on its selected set, with its significance level tuned on the same budget, and its memory recorded rather than capped. Where it keeps more than $k$ features, we report accuracy at matched feature count as well. On Dorothea and Dexter we found no reported result on Lacuna for OSFS accuracy. The paper states only that OSFS and Fast-OSFS "successfully handled the Dorothea dataset (100k features), whereas Grafting failed due to out-of-memory errors." We will therefore run OSFS ourselves.
A Grafting-style fixed-threshold rule, with the threshold set to the regularization $\lambda$ and memory uncapped, isolates the value of prefix calibration.
The non-streaming upper reference is offline Gauss-Southwell-q coordinate descent on all $d$ features, following Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection, restricted to $k$ nonzeros. Our target is a stable fraction of its loss reduction, reported as a ratio.
Two ablations isolate the key ingredient. The first freezes the residual at initialization; this is our method with static scores. The second removes swap eviction. If the first ablation matches the full method, residual adaptivity is not the source of any gain.
Why not just…?
Why not just keep the top-$k$ features by correlation with the labels? This is a genuine threat. On designs with nearly orthogonal columns, like the i.i.d. Gaussian generators used in Nearest Neighbor based Greedy Coordinate Descent, marginal and residual scores rank features almost identically, and we expect a tie. The case for our method is the correlated regime. There screening fills memory with near-duplicates of one strong signal, while residual scoring stops rewarding a feature once its signal has been explained. We therefore sweep column correlation on synthetic data and report where the curves cross. If there is no crossover at realistic correlation levels, including on GISETTE and rcv1, we will report that screening suffices.
Why not just sample features uniformly? In expectation a uniform $k$-subset contains a $k/d$ fraction of the true support. Lu et al.'s $\gamma\approx0.016$ on rcv1 indicates that a typical coordinate is worth about a sixtieth of the greedy one. The reservoir baseline measures this cost directly.
Why not just buffer everything on disk and run offline greedy coordinate descent or the nearest-neighbor index? When one extra pass is affordable, that is the right answer, and we include it as the upper reference. The question here is the regime where columns are generated or discarded after arrival, or where the $O(nd)$ index does not fit. The Grafting out-of-memory failure on Dorothea reported in Online Streaming Feature Selection shows this regime occurs at 100k features.
Why not just use OSFS? OSFS optimizes no loss and ignores order. It can therefore keep features that are statistically dependent on the label but add little predictive value once others are present. The matched-feature-count comparison settles whether this matters in practice.
Proposed Experiments
The synthetic study uses the sparse regression and logistic generators from the greedy coordinate descent papers, with $p=10^4,10^5,10^6$ and a $k$-sparse ground truth. We add block-correlated columns with correlation from 0 to 0.9 and a few "heavy" features whose signal dwarfs the rest. Metrics are objective ratio to offline GS-q, support recovery F1, and peak stored columns.
Real data are GISETTE (6,000 samples, 5,000 features), LEUKEMIA (38 samples, 7,129 features) and rcv1 from the LIBSVM collection, plus Dexter (20,000 features) and Dorothea (100,000 features) from the challenge data used by OSFS. Each is streamed by column under 20 random permutations with $k$ from 10 to 500. We report test accuracy, objective and wall-clock time. The only published numbers for the greedy solvers on these datasets are qualitative, for example ASGCD beating Katyusha on GISETTE per Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex. So all comparisons are run in-house under one budget.
Three checks are decisive. First, on correlated designs the method must beat top-$k$ screening at equal memory, and the frozen-residual ablation must lose that advantage. Second, under adversarial orders the method's advantage should shrink or vanish, with features sorted by increasing or decreasing marginal score or with strong features placed last. This confirms that the gains come from random order and not from the threshold alone. Third, the objective ratio to offline greedy should stay roughly constant as $d$ grows from $10^4$ to $10^6$ at fixed $k$, as a constant-factor guarantee predicts. A ratio that decays with $d$ would falsify the central claim.
References
- Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
- Accelerating Greedy Coordinate Descent Methods
- Nearest Neighbor based Greedy Coordinate Descent
- Asynchronous Parallel Greedy Coordinate Descent
- A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering
- Cardinality constrained submodular maximization for random streams
- Streaming Submodular Maximization Under Matroid Constraints
- Approximating the Top Eigenvector in Random Order Streams
- Online Streaming Feature Selection
- Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex