Research map / Learning theory and algorithms / Prediction and decision losses
Finite Smoothing Algorithm for High-Dimensional Support Vector Machines and Quantile Regression
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 the finite smoothing algorithm (FSA), which smooths the SVM hinge and quantile check losses, then uses finite identification of non-differentiable points plus generalized coordinate descent to recover exact solutions for high-dimensional SVM and quantile regression, implemented in R packages hdsvm and hdqr.
Problem
Computing exact solutions of sparse penalized high-dimensional SVM and quantile regression is slow because the hinge and check losses are non-differentiable, which blocks efficient coordinate descent.
Approach
Smooth the hinge/check loss with a δ-smoothed surrogate, iteratively identify the set of points lying on the non-differentiable kink (adding linear equality constraints via augmented Lagrangian), shrink δ by a factor of 4 until KKT conditions of the exact problem hold, and solve each smoothed subproblem with a majorization-based generalized coordinate descent.
Key results
- On simulated SVM with p=3000 and 10000, hdsvm runs in about 0.03-0.12 s versus roughly 49-1600 s for ReHline and CVXR, with the lowest objective values.
- On quantile regression with n=200, p=10000, hdqr achieves the lowest objective values (e.g., 0.65 at tau=0.1) and is orders of magnitude faster than FHDQR, ReHline, and CVXR.
- On the Scheetz et al. microarray data, hdqr is at least 3,000 times faster than ReHline and CVXR at p=10000 (per the paper's text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use hdsvm instead of ReHline | High-dimensional SVM · SVM simulation, ρ = 0.2, p = 10000 | run time (seconds): 1389.28 -> 0.12 | Helped |
| Use hdsvm instead of ReHline | High-dimensional SVM · SVM simulation, ρ = 0.2, p = 10000 | objective value: 0.79 -> 0.78 | Helped |
| Use hdqr instead of FHDQR | High-dimensional quantile regression · Simulation, n = 200, p = 3000, τ = 0.1 | run time (seconds): 1.43 -> 0.03 | Helped |
| Use hdqr instead of FHDQR | High-dimensional quantile regression · Simulation, n = 200, p = 3000, τ = 0.1 | objective value: 0.66 -> 0.64 | Helped |
| Use hdqr instead of FHDQR | High-dimensional quantile regression · Simulation, n = 200, p = 3000, τ = 0.5 | objective value: 0.87 -> 0.87 | No clear effect |
| Replace the elastic-net penalty with MCP (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.2 | test error: 0.11(0.02) -> 0.10(0.01) | Helped |
| Replace the elastic-net penalty with MCP (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.7 | test error: 0.21(0.03) -> 0.20(0.01) | Helped |
| Replace the elastic-net penalty with MCP (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.9 | test error: 0.25(0.03) -> 0.24(0.02) | Helped |
| Replace the elastic-net penalty with SCAD (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.2 | test error: 0.11(0.02) -> 0.11(0.02) | No clear effect |
| Replace the elastic-net penalty with SCAD (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.7 | test error: 0.21(0.03) -> 0.21(0.03) | No clear effect |
| Replace the elastic-net penalty with SCAD (ablation) | High-dimensional SVM · SVM simulation, p = 10000, ρ = 0.9 | test error: 0.25(0.03) -> 0.25(0.03) | No clear effect |
Limitations
- Focuses on unconstrained problems; linear constraints and fairness-type constraints are left for future work.
- Theory guarantees linear convergence of GCD only for the smoothed subproblem; overall procedure convergence is argued from finite identification.
Experimental setup
Datasets: simulated Gaussian data following Wang et al. 2006 simulated data following Friedman et al. 2010 UCI/microarray benchmarks (Breast, Colon, Leukemia, Malaria, Ovarian) Scheetz et al. 2006 rat eye gene expression
Benchmarks: simulated high-dimensional SVM simulated high-dimensional quantile regression five high-dimensional SVM benchmarks Scheetz et al. 2006 microarray quantile regression
Metrics: objective value run time (seconds) test error number of true/false positive features
Baselines: ReHLine CVXR DrSVM FHDQR quantreg
Builds on: Wang & Zou 2022 delta-smoothed hinge loss generalized coordinate descent (Yang & Zou) glmnet local linear approximation (Zou & Li 2008)
Closest papers by meaning
- Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery (ICML 2024 · similarity 0.83)
- Faster Algorithms for Structured Linear and Kernel Support Vector Machines (ICLR 2025 · similarity 0.82)
- Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise (ICML 2024 · similarity 0.82)
- Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning (NeurIPS 2024 · similarity 0.81)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.81)
- Optimal Kernel Quantile Learning with Random Features (ICML 2024 · similarity 0.81)
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.