Summary
Training a hard-margin support vector machine (SVM) involves finding the shortest distance between two shapes made from data points. The authors improve an existing approach, called the Triangle Algorithm, by introducing 'guarded block transfers,' which speed up the process without losing accuracy. They prove mathematically that their method converges faster in a predictable way. They also show how to identify and ignore irrelevant points during training, making the process more efficient. Tested on several public datasets, their method matches or beats some existing solvers in accuracy but is slower than others, with its main advantage being a reliable certificate of correctness.
What this means in practice
- •For machine learning engineers: Improve certified accuracy checking and pruning of training data in support vector machine models for hard-margin settings.
- •For optimization software developers: Incorporate guarded block transfer techniques to accelerate convergence guarantees in convex optimization problems related to SVM training.
Abstract
Hard-margin SVM training is the distance problem between two convex hulls, which the Triangle Algorithm (TA) solves with a certified duality gap. We propose \emph{guarded block transfers}: $k$ Mitchell--Demyanov--Malozemov (MDM) transfers per scan are aggregated into one exact line search, guarded by a comparison with the single best transfer at a cost independent of the number of points $n$, and replaced by an away step when the leading transfer is capacity-clipped. On the Minkowski-difference polytope, where the objective is $1$-strongly convex, we prove global linear convergence with explicit constants and no combinatorial swap-step bounds; the per-step contraction is $k$-independent and only the drop-count bound grows with $k$, so aggregation is provably safe while the saving in scans is measured, not proved. Since the TA certificate is the Frank--Wolfe gap divided by the current distance, gap-safe screening applies, and we bound the iteration after which it has removed every zero-weight point off the optimal faces by $O\!\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$ up to logarithmic factors in the geometry, $ρ$ the rate constant and $τ$ the optimal-face margin. On five LIBSVM benchmarks, with fairer baselines than our submission, the solver matches the baselines to four or five digits wherever both converge, ties LIBSVM on sparse-support hard margins and beats our blended pairwise conditional gradients (BPCG). But our full-cache sequential minimal optimisation (SMO) code ties or beats it on kernel $L_2$ margins, LIBLINEAR's dual solver is up to $4.5\times$ faster on the separable $L_2$ margin, and our solver is one to three orders of magnitude slower than LIBLINEAR's Newton solver on dense-support $L_2$ margins and than LIBSVM on a nearly touching kernel hull. Its edge is the certificate, not speed.