An Efficient ADMM-Based Algorithm to Nonconvex Penalized Support Vector Machines

Lei Guan, Linbo Qiao, Dongsheng Li, Tao Sun, Keshi Ge, Xicheng Lu

Introduction

Support Vector Machines (SVMs) are a cornerstone of supervised learning, particularly for classification tasks. However, modern data science often requires models that are not only accurate but also "sparse"—capable of identifying a small subset of relevant features from high-dimensional datasets. While the popular $\ell_1$ (Lasso) penalty is frequently used for feature selection, it can introduce statistical bias by over-shrinking large coefficients.

Nonconvex penalties, such as the Smoothly Clipped Absolute Deviation (SCAD) and Minimax Concave Penalty (MCP), are theoretically superior because they can identify true features more accurately. The challenge lies in optimization: these penalties transform the SVM problem into one that is nonconvex, nondifferentiable, and nonsmooth. This paper introduces FEADMM, an efficient framework based on the Alternating Direction Method of Multipliers (ADMM) designed to solve these difficult problems at state-of-the-art speeds.

The FEADMM Framework

The authors leverage the ADMM strategy to decompose the complex global optimization problem into smaller, manageable subproblems. By introducing auxiliary variables, they decouple the nondifferentiable hinge loss of the SVM from the nonconvex penalty.

Computational Innovations

A primary contribution of FEADMM is its handling of the weight vector ($w$) update, typically the most expensive step in SVM optimization.

  1. Matrix Inversion Trick: For high-dimensional data where the number of features ($d$) exceeds the number of samples ($n$), the algorithm utilizes the Sherman-Morrison formula. This reduces computational complexity from $O(d^3)$ to $O(dn^2)$.
  2. Pre-computation: The algorithm performs Cholesky factorization of the required matrices before the iterative process begins. This shifts the "heavy lifting" out of the main loop, reducing the cost of each subsequent iteration to a simple $O(dn)$ operation.
  3. Generality: Unlike previous solvers hardcoded for specific penalties, FEADMM is a general framework. It can handle various nonconvex regularizers (SCAD, MCP, LSP, and Capped-$\ell_1$) simply by adjusting a single step in the algorithm.

Results and Discussion

The algorithm was evaluated against state-of-the-art competitors like GIST and specialized solvers (SCAD-SVM, RankSVM-MCP) across several benchmark datasets, ranging from small-scale (heart_scale) to massive high-dimensional sets (news20 with 1.35 million features).

Performance comparison of FEADMM against GIST and other solvers on heart_scale and mushrooms datasets using SCAD and MCP penalties.

As illustrated in the experimental results, FEADMM (represented by the red lines) consistently reaches peak accuracy significantly faster than its competitors. On the mushrooms dataset, FEADMM reached 100% accuracy in just 11 iterations, compared to 194 iterations for GIST. In large-scale tests like real_sim, FEADMM converged in approximately 42 seconds, nearly three times faster than GIST. Furthermore, while traditional solvers like SCAD-SVM failed to process the largest datasets, FEADMM scaled effortlessly, maintaining high prediction accuracy across all tested penalties.

Conclusion

FEADMM offers a powerful solution for nonconvex penalized SVMs, combining mathematical rigor with extreme computational efficiency. By utilizing clever matrix-inversion tricks and a pre-computation strategy, it overcomes the traditional bottlenecks of high-dimensional optimization. While currently focused on linear SVMs, the framework's generality suggests it could be extended to other complex sparsity-inducing penalties or nonlinear kernels in future research.

Summary updated

Abstract

Support vector machines (SVMs) with sparsityinducing nonconvex penalties have received considerable attentions for the characteristics of automatic classification and variable selection. However, it is quite challenging to solve the nonconvex penalized SVMs due to their nondifferentiability, nonsmoothness and nonconvexity. In this paper, we propose an efficient ADMM-based algorithm to the nonconvex penalized SVMs. The proposed algorithm covers a large class of commonly used nonconvex regularization terms including the smooth clipped absolute deviation (SCAD) penalty, minimax concave penalty (MCP), log-sum penalty (LSP) and capped-'1 penalty. The convergence of the proposed algorithm is guaranteed. Extensive experimental evaluations on five benchmark datasets demonstrate the superior performance of the proposed algorithm to other three state-of-the-art approaches.
BibTeX
@inproceedings{guan2018efficient,
  author = {Lei Guan and Linbo Qiao and Dongsheng Li and Tao Sun and Keshi Ge and Xicheng Lu},
  title = {{An Efficient ADMM-Based Algorithm to Nonconvex Penalized Support Vector Machines}},
  booktitle = {Workshops @ ICDM},
  year = {2018},
  url = {https://openreview.net/forum?id=Rlx1zH32tHC},
}
Figure