Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training

arXiv:2610.15829v1 Announce Type: new 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 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(frac{k}{rho}logfrac{1}{au}right) up to logarithmic factors in the geometry, rho the rate constant and au 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.5imes 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.

Source: arXiv cs.LG | 2026-10-14

Related