Source-linked AI summary
Parallel Coordinate Descent for L1-Regularized Loss Minimization
Joseph K. Bradley, Aapo Kyrola, Danny Bickson, Carlos Guestrin
TL;DR
L1-regularized optimization needs scalable methods because high-dimensional problems can outgrow sequential computation and few parallel alternatives exist. The paper introduces Shotgun, which parallelizes coordinate updates over features and proves convergence bounds for its behavior. Across theory and experiments, the predicted parallelism matches observed behavior, and Shotgun outperforms published L1 solvers on many large datasets.
Problem
High-dimensional L1-regularized problems need scalable optimization, while few parallel algorithms exist and sample-parallel methods may have limited utility when features outnumber samples.
Method
Shotgun performs P coordinate updates in parallel over features and uses convergence analysis to characterize speedups up to a problem-dependent limit.
Results
Shotgun’s theoretical predictions matched empirical behavior, and extensive comparisons found it outperformed state-of-the-art L1 solvers on many datasets.
Takeaways & Limitations
Shotgun is reported as one of the most efficient and scalable current solvers for L1-regularized problems.
Takeaways & Limitations
Runtime speedups were limited by low-level hardware issues, especially memory bandwidth and latency at the memory wall.
Abstract
from arXiv · showhide
We propose Shotgun, a parallel coordinate descent algorithm for minimizing L1-regularized losses. Though coordinate descent seems inherently sequential, we prove convergence bounds for Shotgun which predict linear speedups, up to a problem-dependent limit. We present a comprehensive empirical study of Shotgun for Lasso and sparse logistic regression. Our theoretical predictions on the potential for parallelism closely match behavior on real data. Shotgun outperforms other published solvers on a range of large problems, proving to be one of the most scalable algorithms for L1.
1. Introduction
L1-regularized models support sparse learning in high-dimensional settings, but growing problem sizes and limited core-speed gains create a need for scalable parallel optimization. Shotgun parallelizes coordinate descent over features, with theory predicting speedups up to a data-dependent limit and experiments showing strong performance.
- L1 regularization promotes sparse solutions and can make logistic-regression sample complexity scale logarithmically with irrelevant features.
- Sequential coordinate descent updates one coordinate per iteration and is effective for high-dimensional data, but few parallel algorithms target L1-regularized losses.
- Parallelizing over samples may be of limited utility when applications have many more features than samples, motivating Shotgun’s feature-parallel approach.
- Shotgun makes P feature-coordinate updates in parallel, despite coordinate descent appearing inherently sequential.
- Shotgun’s convergence bounds predict speedups linear in P up to a problem-dependent maximum P∗ that can be estimated from the data.
- Experiments compare Shotgun with five state-of-the-art algorithms on 35 real and synthetic datasets, finding stronger performance on large problems and about 1/P as many iterations as Shooting.
2. L1-Regularized Loss Minimization
The paper formulates L1-regularized convex loss minimization over normalized feature data and connects the formulation to Lasso and sparse logistic regression. Its sequential coordinate-descent baseline randomly updates one weight, while the analysis supplies bounds for expected optimization progress.
- The objective minimizes a non-negative convex loss over samples plus an L1 penalty weighted by λ.
- The formulation includes Lasso with real-valued observations and sparse logistic regression with labels in {−1, +1}.
- For analysis, the L1 problem is transformed using duplicated features and a twice-differentiable regularizer, although duplicate features are unnecessary in implementation.
- 2.1. Sequential Coordinate Descent: Shooting randomly selects one weight per iteration and applies a coordinate update based on the gradient and loss-dependent constant β.
- 2.1. Sequential Coordinate Descent: The analysis assumes a uniform upper bound on the loss change from a single-weight update and derives convergence rates for the stochastic coordinate-descent baseline.
- 2.1. Sequential Coordinate Descent: Theorem 2.1 indicates that stochastic coordinate descent scales well with dimensionality and can have better runtime bounds in d than specified stochastic-gradient methods.
3. Parallel Coordinate Descent
Shotgun parallelizes coordinate descent by updating P randomly selected features simultaneously, with convergence governed by feature interactions and a problem-dependent parallelism limit. Theory and controlled experiments show near-linear iteration speedups below the predicted threshold, while excessive parallelism can cause divergence.
- Shotgun algorithm: Shotgun updates P weights independently and uniformly at random in parallel, applying the same coordinate update used by Shooting.The collective update combines the selected coordinate changes into one iteration.
- Parallel-update intuition: Parallel updates help with uncorrelated features but can conflict for correlated features and increase the objective.The interference term captures interactions between simultaneous updates; positively correlated features with updates in the same direction can be harmful.
- Practical considerations: A step size of 1/P guarantees convergence for convex F but produces very small steps and long runtimes.The authors therefore found this generic safeguard impractical in experiments.
- Theory versus empirical performance: Using the predicted P* gives almost optimal speedups, while increasing P beyond P* soon makes Shotgun diverge.Figure 2 compares predicted and empirical iteration counts to reach within 0.5% of the optimum on two single-pixel camera datasets.
- Scope and assumptions: The convergence proof applies to convex losses satisfying Assumption 3.1 and extends beyond L1 to smooth problems constrained by x ≥ 0.The analysis assumes parallel updates of the same weight do not make that weight negative; write-conflict resolution can enforce this in multicore settings.
4. Experimental Results
The experiments study Shotgun for Lasso and sparse logistic regression across diverse datasets, comparing it with published state-of-the-art solvers and analyzing self-speedup and hardware effects.
- Experimental design: The study evaluates Shotgun on Lasso and sparse logistic regression across a wide variety of datasets against published state-of-the-art solvers.It also analyzes self-speedup in relation to Theorem 3.2 and multicore hardware issues.
4.1. Lasso
Shotgun performs strongly across Lasso datasets, especially large sparse problems, but its advantage depends on dataset structure and parallelism limits.
- Experimental setup: Shotgun was tested against five published Lasso solvers on 35 datasets spanning four dataset categories.Runs used λ = 0.5 and 10, omitting executions that failed to converge within a reasonable time.
- Results: Shotgun with P = 8 converged faster than other algorithms on most dataset categories and performed particularly well on Large, Sparse Datasets.Most competing algorithms failed to converge near the plotted ranges for that category.
- Results: On the largest dataset, Shooting required ∼4900 seconds while Shotgun required < 2000 seconds.The dataset contained 5 million features and 30K samples, with bigram occurrences from financial reports as features.
- Results: On Single-Pixel Camera datasets, Shotgun with P = 8 was slower than Shooting because the plotted datasets had P∗ = 3.A Ball64 singlepixcam experiment showed divergence for P > 4 before practical adjustments enabled convergence with P = 8.
- Other algorithms: L1 LS was the most robust competing solver and solved some Large, Sparse Datasets.
- Caveats: The comparison is difficult because termination criteria and implementations differ across algorithms, so the authors emphasize major trends rather than exact rankings.Shotgun and Shooting used C++, whereas other solvers used Matlab; runs failing to converge were omitted.
4.2. Sparse Logistic Regression
The sparse logistic-regression experiments compare Shotgun CDN with stochastic-gradient methods across low- and high-dimensional regimes. Shotgun CDN is competitive when samples dominate and much faster when features dominate, while SMIDAS is substantially slower per iteration.
- Experimental setup: The experiments compare Shotgun CDN with SGD variants on training objectives and held-out classification error for two large datasets.The held-out set contains 10% of the data.
- rcv1: On rcv1, where d > n, Shotgun CDN with P = 8 was much faster than SGD, especially in terms of the objective.Parallel SGD performed almost identically to SGD.
- Other algorithms: SMIDAS took over 8500 seconds versus 728 seconds for SGD to execute 10M updates on zeta.The authors attribute the longer iterations to SMIDAS’s mirror-descent updates.
- Implications: The results suggest SGD handles large n while Shotgun handles large d, motivating a possible hybrid that parallelizes over samples and features.
4.3. Self-Speedup of Shotgun
Shotgun achieves near-linear iteration speedups, but runtime gains are smaller because multicore hardware becomes the bottleneck. Memory bandwidth and latency limit practical scaling.
- Method: Self-speedup experiments varied λ and P, defining runtime as the first point within 0.5% of Shooting’s optimal objective.P denotes the number of parallel updates and cores.
- Results: Iteration speedups matched Theorem 3.2 closely, reaching about 8×, while runtime speedups reached only about 2× to 4×.
- Hardware limits: Runtime speedups were limited by memory-bus bandwidth and latency, with each weight update requiring an atomic update to the shared Ax vector.The ratio of memory accesses to floating-point operations is O(1), and updates lack temporal locality.
- Logistic-regression comparison: Figure 4 compares training objectives and held-out classification error for zeta and rcv1, with SGD initially faster on zeta and Shotgun CDN faster on rcv1.The rcv1 comparison uses a log scale, and Parallel SGD is hidden by SGD.
5. Discussion
Shotgun provides parallel coordinate descent for L1-regularized optimization, with convergence bounds predicting linear speedups up to a problem-dependent limit. Experiments matched these predictions and showed strong performance against state-of-the-art solvers.
- Shotgun is a simple parallel algorithm for L1-regularized optimization.
- Its convergence bounds predict linear speedups up to an interpretable, problem-dependent limit.
- Experiments matched Shotgun’s theoretical predictions with empirical behavior.
- Extensive comparisons found that Shotgun outperforms state-of-the-art L1 solvers on many datasets.The authors identify it as one of the most efficient and scalable solvers for L1-regularized problems.
- The work points to a hybrid of stochastic gradient descent and Shotgun as a promising extension.