Choosing How Many Cores to Use, Round by Round, in Sparse Coordinate Descent

Coordinate descent solves problems such as sparse regression by changing one weight at a time. It is the standard solver for problems with an $\ell_1$ penalty, a term that pushes most weights to exactly zero. There are two known ways to run it on many cores, and each fails for a different reason. If several cores update correlated weights at once, each one tries to correct the same residual error, and together they overshoot. The Shotgun analysis caps safe parallelism at roughly the number of features divided by the largest eigenvalue of the feature correlation matrix (Bradley et al. (2011)). Separately, when there is too little work per step, the cost of coordinating cores exceeds the arithmetic they save. Serial code then wins, sometimes by an order of magnitude (Agrawal et al. (2016)). Current parallel solvers pick one number of cores $P$ and keep it for the whole run.

That fixed choice is wrong in a predictable way. As the solver proceeds, most weights reach zero and stay there. Only a small "active set" of weights still needs work, and both limits on parallelism move as it shrinks. The per-round workload falls toward the point where overhead dominates. The surviving features can also be more correlated than the full feature set, so the safe number of cores can collapse. We propose a solver that re-estimates both limits every epoch and sets the number of cores to maximize predicted objective decrease per second of wall-clock time. That can mean dropping all the way to one core. We also treat the controller as a measuring instrument. By turning off one half of its model at a time, we can find out whether memory and synchronization costs or correlation-driven overshoot actually limits multicore coordinate descent on modern CPUs. The research file identifies this as unanswered (Gap 4).

Core Claim

On $\ell_1$-regularized logistic regression and Lasso over a full regularization path, a per-epoch choice of $P$ will match or beat the best fixed $P$ chosen after the fact. It will do this without per-dataset tuning, and the gain will be concentrated in the strongly regularized, small-active-set part of the path. The controller maximizes a simple ratio of predicted progress to predicted time:

$$P_t = \arg\max_{1 \le P \le P_{\max}} \frac{g(P;\, \hat\rho_t, |S_t|)}{\tau(P;\, W_t)}.$$

Here $S_t$ is the active set at epoch $t$, and $\hat\rho_t$ is an estimate of the largest eigenvalue of the normalized correlation matrix restricted to $S_t$. The numerator $g$ is the expected per-round decrease. It has the shape of the Shotgun bound: it grows linearly in $P$ and loses progress through a penalty proportional to $(P-1)\hat\rho_t / |S_t|$. The denominator $\tau$ is measured time per round for workload $W_t$ (the nonzeros touched in the active columns). $\tau$ has two parts. One is a synchronization cost that grows with $P$. The other is a compute term that scales as $W_t / \min(P, B)$, where $B$ is the core count at which memory bandwidth saturates, fitted once per machine by a short microbenchmark.

We estimate $\hat\rho_t$ by a few warm-started power-iteration steps on the active columns. Because the active set changes slowly between epochs, each estimate costs about one extra pass over the active data. The practical claim is that the controller removes the empirical tuning of bundle size that Bian et al. (2019) name as an open limitation. The scientific claim is that the controller's two halves tell us which constraint binds, and where along the path.

Relation to Prior Work

Three papers supply the stability side. Shotgun (Bradley et al. (2011)) gives the eigenvalue limit, computed once for all features. It also reports that eight cores cut iterations eightfold but wall-clock time only two to four times, because memory bandwidth ran out. That observation motivates our time model. Cheung et al. (2018) show such limits are tight, meaning divergence does happen beyond them. This constrains us: the controller must not overshoot the local limit even briefly. Block-Greedy coordinate descent (Scherrer et al. (2012)) groups correlated features into fixed blocks. It observes that under strong regularization the nonzero weights crowd into a few blocks and leave cores idle. That is the efficiency inversion we target, which Scherrer et al. leave unsolved. None of these three updates its parallelism as the active set shrinks.

PCDN (Bian et al. (2019)) avoids overshoot for any $P$ by running a joint line search over the $P$ coordinates updated together. It still keeps $P$ fixed and tunes it by hand. We reuse its line search as a safety net rather than as the mechanism that chooses $P$.

On the systems side, SySCD (Ioannou et al. (2019)) makes coordinate descent aware of caches and processor sockets. It does not change the thread count, and it tunes synchronization frequency manually. Petuum (Xing et al. (2015)) schedules correlated parameters apart and tolerates stale reads, but has no spectral step limit. FAST-BCDA (SIAM (2016)) shrinks the active set aggressively but runs serially, and names parallelization as future work. Our solver can be read as a parallel active-set method whose core count follows the active set.

Research Program

We will build the solver in C++ with OpenMP on a two-socket shared-memory machine. The inner update is Shotgun-style random selection of $P$ active coordinates with diagonal Newton steps, as in PCDN. The controller runs between epochs and can choose any $P$ from 1 to the core count.

The analysis has two parts. The first checks that $g/\tau$ predicts measured progress per second: we run every fixed $P$ at checkpoints along the path and compare the ranking of $P$ values with the model's ranking. The second is the attribution study. It compares three controllers: the full one, a "systems-only" one that sets $\hat\rho_t = 1$, and a "stability-only" one that sets $\tau$ constant in $P$. We record, for each point on the path, which term decided $P_t$.

We will also record how $\hat\rho_t$ drifts compared with the global eigenvalue. This directly tests the untested premise of Gap 3, that local correlation can rise as features are pruned. If it never rises on real data, we will say so and simplify the controller.

Baselines

The naive reference points are serial coordinate descent, meaning CDN or the serial Shooting algorithm, and Shotgun at full core count with no adaptation. The file reports that Shotgun on 8 cores converged in under 2,000 seconds against nearly 5,000 for serial Shooting on the Financial Report data, a 2x–4x wall-clock speedup (Bradley et al. (2011)). That dataset is not public, so we reproduce the comparison on Sparco and the text benchmarks.

The strongest existing method is PCDN with its best fixed bundle size. It is the only method in the file that keeps parallel updates stable for arbitrary $P$. Its reported numbers are 17.49x speedup over CDN with 23 threads on rcv1 for logistic regression, and 29x faster than TRON and 18x faster than CDN on news20 for $\ell_2$-loss SVM (Bian et al. (2019)). To make the comparison fair, we give PCDN a grid search over $P$ run separately on each dataset and each $\lambda$, and we select the winner after the fact on the test runs. This is a deliberately generous "oracle fixed $P$". Our controller gets no tuning beyond the one-time machine microbenchmark.

The second strong competitor is a hand-written switching rule. It uses $P = \min(P_{\max}, |S_t|/k)$ and drops to serial below an active-set size $m$, with $k$ and $m$ tuned on a held-out dataset under the same compute budget we spend on the microbenchmark.

For dense data we add SySCD's design, reimplemented with per-thread replicas and buckets matched to the cache line. The reported result there is 12x faster convergence than PASSCoDe on HIGGS (Ioannou et al. (2019)). We also include clustered Block-Greedy, which reports objective 0.136 at 1,000 seconds against 0.206 for random blocks on Reuters at $\lambda = 10^{-6}$ (Scherrer et al. (2012)).

The two ablated controllers, systems-only and stability-only, isolate the key ingredient. Beating the baselines means lower total wall-clock time across a 50-point regularization path to a fixed relative duality gap. Our controller must match the oracle fixed-$P$ PCDN within 10% overall and beat it clearly on the strongly regularized half of the path. It must also beat the tuned switching rule on datasets it was not tuned on. All methods use the same machine, the same stopping tolerance, warm starts along the path, and the same data layout.

Why not just…?

Why not just tune a fixed $P$ with PCDN's line search? The line search already prevents divergence, so the stability half of our controller might look redundant. The threat is real, and the stability-only and systems-only ablations exist to settle it. If the oracle fixed $P$ matches the controller, the adaptive idea fails. We expect it will not. The best $P$ at the start of the path, when thousands of features are active, should differ from the best $P$ near the end, when perhaps tens are, and a fixed choice must pay for the mismatch at one end. The line-search overhead that Bian et al. (2019) report also grows with $P$. The oracle also needs a full grid search per dataset, which a practitioner cannot afford.

Why not just drop to serial when the active set gets small? This is the most serious alternative, and it may capture most of the gain. We tune it fairly and report it head to head. Where it differs from our controller is on datasets whose surviving features are highly correlated, where the safe $P$ collapses before the workload does, and across machines, where the switching point moves with memory bandwidth. If the tuned rule transfers across datasets and machines as well as the controller, we will report that a two-parameter rule suffices. The attribution study remains useful in that case, because it would explain why the rule works.

Why not just run lock-free asynchronous updates? The evidence in the file is against it. PASSCoDe diverges on dense data as threads are added (Ioannou et al. (2019)). Overlap beyond a known limit provably diverges (Cheung et al. (2018)). Asynchronous stochastic updates stalled at 93% accuracy on covtype where greedy updates reached 95% (You et al. (2016)). Asynchrony also does nothing for idle cores when the active set is small.

Why not just parallelize over samples with mini-batch SGD or a quasi-Newton method? For problems with far more features than samples, parallelizing over features wins (Bradley et al. (2011)). PCDN beat TRON 29x on news20 (Bian et al. (2019)). Mini-batch speedups for SVMs obey the same spectral-norm limit as dual coordinate ascent (Takáč et al. (2013)), so switching to samples does not escape the correlation problem.

Proposed Experiments

The sparse benchmarks are news20, rcv1, real-sim, Reuters, and kdda, used by Scherrer et al. (2012) and Bian et al. (2019), plus the Sparco reconstruction problems from Shotgun. For dense data we use HIGGS and epsilon, as in SySCD. Every run covers a 50-point $\ell_1$ path, from the largest $\lambda$ that gives a nonzero solution down to $10^{-3}$ of that value. We report total path time, time per path segment, the $P_t$ trajectory, the $\hat\rho_t$ trajectory, and the controller's overhead as a share of runtime, which should stay below 5%.

Three checks decide the outcome. First, on the strongly regularized half of the path, the controller must beat the oracle fixed-$P$ PCDN; otherwise adaptation buys nothing. Second, the controller must beat the tuned switching rule on held-out datasets and on a second machine with a different bandwidth-saturation point; otherwise a heuristic is enough. Third, the attribution study must show whether the systems-only controller matches the full one. If it does, the answer to Gap 4 is that on current CPUs the memory wall and synchronization cost bind before correlation-driven overshoot does, and the local eigenvalue estimate can be dropped. If the stability term changes $P_t$ on correlated datasets, measured by synthetic Lasso with controlled collinearity among late-surviving features, then correlation among surviving features is a real and previously unmodeled limit.