A smoothing algorithm is presented for solving the soft-margin Support Vector
Machine (SVM) optimization problem with an $\ell^{1}$ penalty. This algorithm
is designed to require a modest number of passes over the data, which is an
important measure of its cost for very large datasets. The algorithm uses
smoothing for the hinge-loss function, and an active set approach for the
$\ell^{1}$ penalty. The smoothing parameter $\alpha$ is initially large, but
typically halved when the smoothed problem is solved to sufficient accuracy.
Convergence theory is presented that shows
$\mathcal{O}(1+\log(1+\log_+(1/\alpha)))$ guarded Newton steps for each value
of $\alpha$ except for asymptotic bands $\alpha=\Theta(1)$ and
$\alpha=\Theta(1/N)$, with only one Newton step provided $\eta\alpha\gg1/N$,
where $N$ is the number of data points and the stopping criterion that the
predicted reduction is less than $\eta\alpha$. The experimental results show
that our algorithm is capable of strong test accuracy without sacrificing
training speed.

设计用于大数据集的软间隔支持向量机优化问题的平滑算法通过对于铰链损失函数的平滑和对于 $\ell^{1}$ 惩罚项的活动集方法，在保持计算成本较低的同时，实现了强测试准确性。

l1 支持向量机的平滑算法

A Smoothing Algorithm for l1 Support Vector Machines

In this paper we consider the numerical solution to the soft-margin support
vector machine optimization problem. This problem is typically solved using the
SMO algorithm, given the high computational complexity of traditional
optimization algorithms when dealing with large-scale kernel matrices. In this
work, we propose employing an NFFT-accelerated matrix-vector product using an
ANOVA decomposition for the feature space that is used within an interior point
method for the overall optimization problem. As this method requires the
solution of a linear system of saddle point form we suggest a preconditioning
approach that is based on low-rank approximations of the kernel matrix together
with a Krylov subspace solver. We compare the accuracy of the ANOVA-based
kernel with the default LIBSVM implementation. We investigate the performance
of the different preconditioners as well as the accuracy of the ANOVA kernel on
several large-scale datasets.

本文研究软间隔支持向量机优化问题的数值解，通过使用 NFFT 加速的矩阵向量乘积和 ANOVA 分解特征空间的方法，结合预处理方法和 Krylov 子空间求解器，对线性鞍点形式的线性系统进行求解，比较了 ANOVA 核方法与默认 LIBSVM 实现方法在大规模数据集上的准确性和性能表现。