Sparse models such as the Lasso, which is least squares with an $\ell_1$ penalty that drives most weights to exactly zero, are usually solved by coordinate descent: the solver updates one weight at a time. Two separate tricks make these solvers fast. Safe screening uses a cheap mathematical test to prove that a weight must be zero at the optimum, so the solver can stop touching it. Lock-free parallelism lets many CPU threads update weights at the same time without waiting for one another. The two tricks fit badly together. Screening tests are proved for a single, consistent snapshot of the solver's state, and in a lock-free solver no such snapshot exists unless all threads stop at a barrier. In practice that means screening runs only at epoch boundaries, while the threads spend most of each epoch, on very wide datasets, updating weights that could already have been ruled out.
This note proposes to make safe screening valid inside a running lock-free solver. The key observation is that the danger does not come from reading old values. A screening test based on the duality gap, the distance between the current objective and a lower bound on the optimum, stays valid at any weight vector, however out of date. The test fails only when the weight vector and the shared residual (the prediction errors $y - Xw$) disagree because updates from other threads are half-written. That disagreement is bounded by the size of the updates currently in flight, and in-flight updates can be tracked cheaply. Widening the screening margin by this bound gives tests that each thread can run on its own, mid-epoch, while keeping the guarantee that no weight that is nonzero at the optimum is ever discarded.
Core Claim
For $\ell_1$-regularized least squares and logistic regression solved by lock-free coordinate descent, a duality-gap screening test computed from a thread's possibly inconsistent view stays provably safe if its margin is inflated by a term that grows with the norm of uncommitted in-flight updates. That norm is bounded by the number of threads times the largest recent step, not by the staleness window. Two further claims follow. First, barrier-free screening reaches a target duality gap faster than screening at epoch boundaries when epochs are long relative to the time needed to identify which weights will be zero, which is the regime of very wide click-prediction data. Second, the speedups from screening and from parallelism multiply only if the surviving weights are re-packed into contiguous memory blocks. Without re-packing, shrinking the active set concentrates writes on a few cache lines and the parallel speedup collapses.
Background and Positioning
The screening side supplies the method. Ida et al. (2019) and Ida et al. (2020) bound group gradients from residual statistics to skip block updates in the Sparse Group Lasso. Fujiwara et al. (2017) screen Graphical Lasso entries using a decomposition of the data matrix into singular values. Ida et al. (2023) stress that such tests return exactly the unscreened solution. Fast IHT with pruned gradients skips 98.87% of gradient computations on gisette, for up to a 73x speedup. It relies on a precomputed feature-correlation (Gram) matrix that takes $O(n^2)$ memory and on exact sequential states, so it constrains rather than supplies our design. We deliberately use gap-based tests, which need only the residual and column norms, so they scale to kdd2012's 54 million features.
The parallel side supplies the execution substrate. Asy-GCD keeps a shared gradient with atomic additions and converges under a bounded-delay condition, but it maintains gradients for every coordinate. SySCD shows that uncoordinated lock-free coordinate descent (PASSCoDe) thrashes caches and diverges at high thread counts. It fixes this with cache-line buckets, per-epoch re-partitioning across threads, and synchronization across processor sockets (NUMA, non-uniform memory access, where each socket reads its own memory faster). It never skips provably-zero coordinates.
The closest combined work sits at the boundary. Blitz pairs safe elimination with working sets and runs distributed with 64 workers. Its screening, however, is an outer, globally synchronized step. pSCOPE skips updates only for features that are absent from a mini-batch, which is a passive kind of skipping, and it synchronizes at epoch boundaries. FLEXA updates selectively in parallel and observes early identification of zeros, but it must evaluate violations for every block and runs synchronously. None of these screens safely while threads run unsynchronized, which is the gap we target. We leave non-convex penalties (FireWorks) out of scope because gap-based safety needs convexity.
Research Program
The first component is theory. Consider the objective $\tfrac12\|y-Xw\|^2+\lambda\|w\|_1$. A thread reads a weight vector $\tilde w$ and a shared residual $\tilde\rho$. The true residual of what it read is $y - X\tilde w = \tilde\rho + e$, where the mismatch $e$ is the sum of partially committed updates from other threads. If each update to coordinate $i$ by a step $\delta_i$ is published to a per-thread slot before its residual writes begin, then
$$\|e\|_2 \le \varepsilon := \sum_{i\in \mathcal{F}} |\delta_i|\,\|x_i\|_2,$$
where $\mathcal{F}$ is the set of in-flight updates (at most one per thread) and $x_i$ is column $i$ of $X$. We will derive a gap-safe rule that eliminates feature $j$ when
$$|x_j^\top\tilde\theta| + \big(r(\tilde w,\tilde\rho) + c\,\varepsilon/\lambda\big)\|x_j\|_2 < 1,$$
where $\tilde\theta$ is the rescaled dual point built from $\tilde\rho$, $r$ is the usual radius $\sqrt{2\,\mathrm{gap}}/\lambda$ evaluated at the mismatched pair, and $c$ is a constant to be pinned down. The constant should come from the gap being Lipschitz in the residual on the bounded set the iterates occupy, so $c$ depends on $\|y\|$ and the dual rescaling. A matching derivation for the logistic dual is the second theoretical target. Eliminations are monotone and are committed as a single flag write, so a feature can never become active again.
The second component is the system. We will build on a SySCD-style solver. Each thread owns buckets of coordinates and screens its own bucket against a residual snapshot it computes at that moment. When the survivors in a bucket fall below a threshold, the thread re-packs them, together with their data columns, into dense cache-line-aligned blocks. At the next per-epoch re-partitioning, it redistributes those blocks so the remaining work stays balanced across threads and sockets. The in-flight slots cost one cache line per thread.
The third component is analysis. We will measure how often $\varepsilon$ is non-negligible, how much safety margin the inflation costs, and how parallel speedup varies with active-set size, with and without re-packing.
Baselines
The naive reference point is a lock-free coordinate descent solver with SySCD's memory optimizations and no screening. It isolates the value of screening at all. SySCD reports being 10x to 42x faster than scikit-learn, H2O and Vowpal Wabbit, and 12x faster than an optimized PASSCoDe on HIGGS. These are the strongest reported numbers for the unscreened parallel regime.
The strongest competitor is the same solver with exact gap-safe screening run at its existing per-epoch synchronization point. It costs one extra residual pass and adds no new barrier. This is the obvious way to combine the two lines of work, and our method has to beat it. No reported result found on Lacuna for epoch-boundary screening combined with system-aware lock-free coordinate descent, so we will establish this number ourselves.
We also run two references that are not exact competitors. Blitz serves as an outer working-set coordinator around the same parallel inner solver. It reports being an order of magnitude faster than naive proximal gradient on Criteo with 64 workers, and determining the Finance sparsity pattern in seconds. pSCOPE, which reports 3.78 seconds on rcv1 against over 1,000 seconds for distributed block coordinate descent, is a reference for passive skipping rather than a same-hardware competitor.
Three ablations isolate the ingredients. The first applies the uninflated rule mid-epoch, which shows whether inflation is actually needed. The second inflates by a staleness-window bound instead of the in-flight bound, which shows whether our tighter bound matters. The third removes re-packing, which tests the cache-locality claim.
All methods share one C++ code base, one two-socket machine, and identical thread counts from 1 to the full core count. All use the same $\lambda$ path and the same stopping rule: a relative duality gap of $10^{-6}$, with the gap computed on a synchronized snapshot. Tunable parameters such as bucket size, screening frequency and Blitz's working-set growth each get the same grid budget. Our method beats the epoch-boundary baseline if its median time-to-gap over five seeds is lower by more than the seed-to-seed spread on at least the wide datasets. It must also record zero false eliminations, checked against a high-precision sequential solve.
Why not just…?
Why not just screen at epoch boundaries and run the lock-free solver in between? This is the real threat. On narrow or quickly-solved problems it may well match us, because zeros are identified within the first epoch or two and the remaining waste is small. Our advantage should scale with epoch length relative to identification time, so it should appear on kdd2012, Criteo and avazu and vanish on rcv1 or epsilon. The experiments are stratified this way, and if the gap does not appear on the wide datasets the core claim fails.
Why not just run an unsafe heuristic screen mid-epoch and fix mistakes afterward with an optimality check? Heuristics that discard aggressively and re-check optimality conditions can be fast. With asynchrony, however, the post-check itself needs a consistent state, which brings back the barrier. Repeated corrections can also cycle, as FireWorks documents for heuristic working sets. We include an unsafe mid-epoch variant with a final correction pass and report both its time and how many features it re-adds.
Why not just use a working-set method like Blitz around a parallel inner solver? Working sets often beat screening outright. Newsgroup-5 drops from 117,749 seconds to 554 seconds with FireWorks. Barrier-free screening is complementary rather than competing, since it can prune inside the inner solve too. We therefore also run Blitz with our screened inner solver. If that hybrid shows no gain over Blitz with an unscreened inner solver, our contribution is limited to settings without working sets, and we will say so.
Proposed Experiments
The datasets are rcv1, real-sim and epsilon, where epochs are short; webspam, avazu, Criteo and kdd2012, where epochs are long and the data are wide; and gisette as a small-scale check against the screening literature. For logistic regression we use the same datasets with their labels.
There are three decisive checks. The first is safety under real contention. We log every elimination together with the measured $\varepsilon$ and compare against a sequential high-precision solution. We expect zero violations for the inflated rule and a nonzero count for the uninflated ablation at high thread counts. If the uninflated rule never errs, the inflation is unnecessary in practice, and the contribution shrinks to a proof.
The second is the epoch-length prediction. We plot speedup over epoch-boundary screening against the ratio of epoch time to the time until 90% of the final zeros are identified. We expect a monotone increase. If the speedup does not grow with that ratio, epoch-length is not what drives the advantage and the regime-based argument against epoch-boundary screening fails.
The third is the multiplicativity test. We compare parallel speedup at 1, 8 and the full thread count as the active set shrinks, with and without re-packing. We expect that, without re-packing, scaling degrades once survivors occupy few cache lines, consistent with the contention failures documented for PASSCoDe in SySCD, and that re-packing restores it. Secondary metrics are the fraction of coordinate updates skipped, the extra elimination delay caused by the inflated margin, and memory overhead.
References
- Fast Sparse Group Lasso
- Fast Block Coordinate Descent for Sparse Group Lasso
- SVD-Based Screening for the Graphical Lasso
- Fast Regularized Discrete Optimal Transport with Group-Sparse Regularizers
- Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations
- Asynchronous Parallel Greedy Coordinate Descent
- SySCD: A System-Aware Parallel Coordinate Descent Algorithm
- Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization
- Proximal SCOPE for Distributed Sparse Learning
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Convergent Working Set Algorithm for Lasso with Non-Convex Sparse Regularizers