Research map / Optimization / Optimizers
Enhanced Cyclic Coordinate Descent Methods for Elastic Net Penalized Linear Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Enhanced Cyclic Coordinate Descent (ECCD), which unrolls s coordinate updates into batched computations using a first-order Taylor correction, to speed up elastic-net penalized GLM path fitting while keeping convergence stable for large block sizes.
Problem
Cyclic coordinate descent for elastic-net penalized GLMs is sequential and costly due to repeated nonlinear link-function evaluations, while naive block coordinate descent becomes numerically unstable as block size grows.
Approach
Unroll the vector recurrences of single-coordinate CD over a block of s coordinates, using a first-order Taylor expansion of the gradient around the block-start iterate so that the link function is evaluated once per block, with a frozen Hessian in the denominator and an intra-block correction term in the numerator.
Key results
- On regularization-path logistic runs, ECCD (s=8 or 16) achieves up to 3.49x speedup over glmnet on duke (alpha=0.8), with objective relative differences around 1e-5.
- Block-size relative objective differences for ECCD stay at or below 9.9e-7 for s up to 32 across lambda values, while naive BCD errors reach about 1e10 at lambda=0.001.
- In scalability tests, ECCD speedups over glmnet are about 3-4x on square problems and up to 8.09x on a 10000x5000 wide-regime case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ECCD with block size s=8 instead of glmnet | Logistic elastic-net regularization-path fitting · duke, α=0.5 | speedup: 1.00× -> 3.05× | Helped |
| Use Taylor-corrected ECCD instead of BCD at s=32 (ablation) | Elastic-net logistic regression on duke · duke, λ=0.001, s=32 | relative objective difference: 5.79 \times \text{10}^{\text{10}} -> 4.20\times10^{-7} | Helped |
| Increase ECCD block size from s=8 to s=16 (ablation) | Elastic-net logistic regression regularization paths · duke, α=0.8 | speedup: 3.16× -> 3.49× | Mixed |
| Use ECCD instead of glmnet | Elastic-net logistic regression scalability benchmarks · 10000×5000, n>p | speedup: 8.09 | Helped |
| Increase ECCD block size up to s=32 (ablation) | ECCD on duke · duke, α∈{0.1,0.2} | relative objective difference from s=1: Δ_s < 5×10⁻⁷ | No clear effect |
Surprising findings
- Naive block coordinate descent diverges with errors on the order of 1e10 for small lambda and s>=8, while ECCD stays stable.
- ECCD is slower than glmnet on some single-lambda settings (e.g., phishing at larger lambda, prostate at alpha=0.1) and on the colon dataset at some alpha values.
Limitations
- Choosing the optimal block size s is nontrivial; performance is robust across s but the optimum is hard to pinpoint.
- Speedups are smaller or negative for some low-dimensional or large-lambda settings.
- Theoretical error bounds rely on assumptions such as bounded coefficients and derivatives of the link function.
Experimental setup
Datasets: duke colon leu australian diabetes prostate phishing LIBSVM benchmarks synthetic data
Benchmarks: duke colon leu australian diabetes prostate synthetic scalability regimes
Metrics: wall-clock time speedup over glmnet relative difference of objective peak RSS
Baselines: glmnet ncvreg biglasso BCD
Builds on: glmnet s-step Krylov methods sequential strong rules block coordinate descent
Closest papers by meaning
- When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent (NeurIPS 2017 · similarity 0.87)
- Accelerating Greedy Coordinate Descent Methods (ICML 2018 · similarity 0.86)
- Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization (ICML 2023 · similarity 0.86)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.85)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.85)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.