Source-linked AI summary
Semismooth Newton Coordinate Descent Algorithm for Elastic-Net Penalized Huber Loss Regression and Quantile Regression
Congrui Yi, Jian Huang
TL;DR
High-dimensional penalized Huber and quantile regression needs efficient algorithms because existing approaches face scalability and nonsmoothness challenges. The paper proposes SNCD, combining coordinate descent with semismooth Newton updates and adaptive strong-rule screening. It establishes convergence properties and reports efficiency and scalability in high-dimensional settings.
Problem
High-dimensional penalized Huber and quantile regression lack efficient algorithms and publicly available software, while existing approaches have unclear scalability.
Method
SNCD combines coordinate descent with semismooth Newton updates and an adaptive strong rule for screening predictors.
Results
The authors report that SNCD is efficient and scalable in high-dimensional settings and establish its convergence properties.
Takeaways & Limitations
SNCD provides an implemented approach for computing elastic-net penalized Huber and quantile regression solution paths in high-dimensional settings.
Takeaways & Limitations
The algorithm can become ill-conditioned when γ gets too close to 0.
Abstract
from arXiv · showhide
We propose an algorithm, semismooth Newton coordinate descent (SNCD), for the elastic-net penalized Huber loss regression and quantile regression in high dimensional settings. Unlike existing coordinate descent type algorithms, the SNCD updates each regression coefficient and its corresponding subgradient simultaneously in each iteration. It combines the strengths of the coordinate descent and the semismooth Newton algorithm, and effectively solves the computational challenges posed by dimensionality and nonsmoothness. We establish the convergence properties of the algorithm. In addition, we present an adaptive version of the "strong rule" for screening predictors to gain extra efficiency. Through numerical experiments, we demonstrate that the proposed algorithm is very efficient and scalable to ultra-high dimensions. We illustrate the application via a real data example.
1 INTRODUCTION
The paper addresses limited algorithmic support for penalized Huber and quantile regression in high-dimensional settings, where nonsmooth losses challenge standard coordinate descent. It proposes SNCD, which combines coordinate descent with semismooth Newton updates and adaptive predictor screening.
- Motivation: High-dimensional penalized Huber and quantile regression lack efficient algorithms and publicly available software.The paper focuses on settings with p ≫ n and sparse coefficients.
- Motivation: Standard coordinate descent works poorly here because Huber loss is only first-order differentiable and quantile loss is nondifferentiable.Existing coordinate-descent approaches rely on quadratic or twice-differentiable losses with closed-form updates.
- Proposed method: SNCD computes solution paths for elastic-net penalized Huber loss regression and quantile regression.The method combines coordinate descent with the semismooth Newton algorithm for nonsmooth equations.
- Results and scope: The authors report that SNCD is efficient and scalable in high-dimensional settings and provide the hqreg R implementation.The implementation supports Huber, quantile, and squared losses, with simulations and real datasets used for evaluation.
- Proposed method: SNCD updates both regression coefficients and subgradient information, unlike typical coordinate descent methods that update only the primal variable.An adaptive strong rule screens predictors to gain additional efficiency.
- Results and scope: The framework can be generalized to other nonsmooth-loss problems, including linear support vector machines with hinge loss.The paper establishes convergence properties and extends SNCD beyond the initial regression settings.
2.1 Background on Newton Derivatives and SNA
This section introduces Newton differentiability and the semismooth Newton iteration for nonsmooth equations. Under local regularity and nonsingularity conditions, the iteration converges superlinearly near a solution.
- Newton differentiability: Newton differentiability provides a framework for applying Newton-type methods to nonsmooth equations.Newton derivatives can be calculated using basic algebra and chain rules.
- Newton differentiability: A Newton derivative is a mapping H associated with the local behavior of F around a point.The definition uses boundedness of nearby derivative mappings and local Lipschitz continuity.
- Convergence: Under Newton differentiability, the SNA has a superlinear convergence result.The theorem assumes a solution, nonsingular H in a neighborhood, a bounded inverse, and a sufficiently close initial point.
2.2 Algorithm
SNCD transforms the penalized Huber regression KKT conditions into a coordinate-wise root-finding procedure, combining semismooth Newton updates with cyclic coordinate descent. Its convergence is established under local regularity conditions and improved in practice through pathwise warm starts.
- Algorithm: The penalized Huber optimization problem is transformed into a root-finding problem using KKT conditions and soft-thresholding.The coefficient equations include βj − S(βj + sj) = 0, with S the soft-thresholding operator.
- Algorithm: SNCD combines semismooth Newton with cyclic coordinate descent to solve the KKT equations without cumbersome matrix operations.It updates each coefficient-subgradient pair while holding the other variables fixed.
- Algorithm: Each coordinate pair (βj, sj) is updated by semismooth Newton steps under two cases determined by |βj + sj| relative to 1.The method uses distinct update formulas when the threshold expression is above or below 1.
- Convergence: SNCD convergence follows coordinate-descent theory under nonsingularity, bounded inverse, separability, and sufficiently small level-set diameter conditions.The objective decreases along iterations, and the theorem guarantees convergence to a minimizer under the stated assumptions.
- Pathwise optimization: Pathwise optimization warm-starts each λ problem from the previous optimizer, helping SNCD converge quickly.The approach addresses the need for a sufficiently good starting point in local semismooth Newton updates.
2.3 Comparison with SNA and Existing Coordinate Descent Type Algorithms
Compared with semismooth Newton applied to the full system, SNCD avoids expensive matrix operations through coordinate-wise updates. This lowers per-iteration cost while retaining practical convergence advantages over SNA and extending coordinate descent to broader nonsmooth models.
- SNCD versus SNA: SNCD reduces computational cost per iteration from O(np^2) for SNA to O(np).The reduction comes from avoiding full-system matrix operations and using coordinate-wise updates.
- SNCD versus SNA: SNCD has at most linear convergence, whereas SNA has a locally superlinear theoretical rate.The paper presents this as a worthwhile compromise because SNCD substantially lowers iteration cost and benefits from warm starts.
- SNCD versus SNA: SNCD is reported to be much faster in practice, while SNCD converges and SNA diverges in some high-dimensional cases.These findings are reported even when pathwise optimization is used.
- Existing coordinate descent: SNCD generalizes coordinate descent to first-order differentiable losses such as Huber loss and reaches nondifferentiable quantile loss through smoothing.Its root-finding formulation treats subgradients as independent variables connected through the KKT conditions.
- Existing coordinate descent: Unlike existing coordinate descent methods that update only coefficients, SNCD simultaneously updates each coefficient and its corresponding subgradient.The pair update uses different formulas across the two threshold regions.
3 SNCD FOR PENALIZED QUANTILE REGRESSION
For penalized quantile regression, SNCD uses a differentiable Huber smoothing approximation because the quantile loss is nondifferentiable. The approximation has convergence guarantees and connects penalized LAD and LS regression as its smoothing parameter varies.
- Quantile-loss smoothing: SNCD handles penalized quantile regression by replacing the nondifferentiable quantile loss with a differentiable Huber approximation.The resulting problem permits KKT derivation and application of SNCD.
- Practical implementation: The smoothing parameter must be sufficiently small for accuracy but becomes ill-conditioned when too close to zero.The algorithm therefore uses a data-dependent heuristic to select γ values and safeguards numerical stability.
- Convergence results: As γ approaches 0, minimizers of the Huber approximation have cluster points that minimize the penalized absolute-loss objective.This establishes convergence of the approximation toward penalized LAD regression.
- Connections to LAD and LS: Penalized Huber regression bridges penalized LAD and LS regression as γ varies from 0 to infinity.Its solutions form a spectrum between the absolute-loss and squared-loss solutions.
PREDICTORS
The standard strong rule can produce many screening violations for penalized Huber and quantile regression, requiring repeated refits. An adaptive multiplier varies along the solution path and reduces violations without sacrificing speed.
- Strong rule: Strong-rule screening must be followed by KKT checks because its underlying assumption does not necessarily hold.Violating predictors are added back and the restricted problem is solved again.
- Motivation: The strong rule often produces many violations for penalized Huber and quantile regression, reducing overall efficiency through repeated reruns.The issue indicates that the standard rule can be too restrictive for these models.
- Adaptive rule: A fixed multiplier M > 1 is difficult to choose across all λ values in a solution path.The paper therefore replaces it with a multiplier that adapts to the local path trend.
- Adaptive rule: The adaptive rule automatically estimates a localized M(λ) that follows solution-path trends.It is designed specifically for penalized Huber and quantile regression screening.
- Results: The adaptive rule reduces screening violations by a large margin without sacrificing speed.The procedure still checks KKT conditions and expands the active predictor set when violations occur.
5 NUMERICAL RESULTS
The numerical experiments compare hqreg with quantreg and assess SNCD, adaptive screening, and related methods across simulated and real datasets. Results indicate close optimization agreement, faster computation, improved scalability, and distinct predictive and selection behavior among models.
- Optimization Performance for Penalized Quantile Regression: Across GDP and Riboflavin data, hqreg and quantreg produce very similar penalized quantile-regression solutions.The objective-function curves show no visually detectable discrepancy, while relative differences remain extremely narrow and close to zero.
- Optimization Performance for Penalized Quantile Regression: hqreg is significantly faster than quantreg for computing solution paths, although the comparison may favor hqreg because quantreg does not use warm-starting.For Riboflavin, quantreg evaluated at a single λ can take longer than hqreg computes the entire path.
- Optimization Performance for Penalized Quantile Regression: On 10000 simulated datasets, relative differences D range from 1e-7 to 1e-1, with most values below 1e-3 and slightly smaller values at τ = 0.5.The distributions appear roughly symmetric on the logarithmic scale.
- Huber Loss Regression and Least Squares: The adaptive strong rule makes hqreg much faster and more scalable than the version without variable screening, especially as dimension p increases.The two versions are similar when p = 100 but hqreg-ASR becomes considerably faster at larger p.
- Huber Loss Regression and Least Squares: SNCD converges in every tested case, whereas SNA fails for large p and γ = 0.1; SNCD becomes increasingly faster as p grows.These results support greater stability and scalability for SNCD relative to SNA.
- Real Data Example: In the microarray example, Q-Enet(τ = 0.75) performs best overall, while LS-Enet performs poorly under both MAPE and QPE criteria.Q-Enet(τ = 0.75) also tends to select sparser models, and H-Enet and Q-Enet select frequently occurring genes more consistently than LS-Enet.
6 DISCUSSIONS
Huber loss and quantile regression are important in many fields, yet efficient algorithms and publicly available software for high-dimensional settings are lacking. The paper develops scalable elastic-net solution-path algorithms and provides an R implementation.
- Efficient algorithms and publicly available software are lacking for fitting Huber loss and quantile regression models in high-dimensional settings.
- The paper develops an efficient and scalable algorithm for computing elastic-net solution paths for both models.
- The implementation is publicly available through the R package hqreg.
APPENDICES
The appendices provide convex-analysis foundations, Newton-differentiability results, KKT formulations, and active-set updates supporting the algorithm. They also describe how the high-dimensional Newton step is reduced using active coefficients and subgradient updates.
- Convex-analysis preliminaries establish subgradients, subdifferentials, proximity operators, soft-thresholding, and Fermat-based KKT optimality conditions.
- The penalized Huber-loss KKT conditions are rewritten as a system of equations involving coefficient and subgradient variables.
- At a solution, the active set defined from coefficients and subgradients equals the support of the coefficient vector.
- The algorithm updates the Newton state and uses an active set to reduce the apparent (2p + 1) × (2p + 1) inversion required by the full step.
C Proofs
The proofs establish Newton differentiability and matrix regularity for the algorithmic system under stated conditions. They use piecewise-smooth structure, block-matrix arguments, spectral bounds, and convergence-sequence reasoning.
- The convergence proofs analyze cluster points of the iterates and the behavior of residuals and smoothing parameters.
- Piecewise-smoothness and Newton-differentiability lemmas are used to establish Newton differentiability of the system components.
- The proof establishes invertibility of key matrices and, under a mild condition, invertibility of H3.
- Spectral arguments show positive-semidefinite structure and bounded eigenvalues for matrices involving the active-design matrix and regularization term.
- The analysis uses bounds on design-matrix norms and inverse matrices to establish uniform boundedness in spectral norm.