arXiv preprint ·
Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
A 4-Qubit Variational Quantum Classifier for Sequence-Specific Classification of DNMT3A and DNMT3B Flanking Methylation Preferences
EvolvAttack: Backdooring self Evolving VLM Agents
Improving the Evaluation of Biomedical Question Answering with Few Human Preference Signals
ObsSpec: Accelerating Agentic Reinforcement Learning with Observation Speculation
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.