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

arXiv: https://arxiv.org/abs/2610.15829 · HTML: https://mlsanity.com/paper/2610.15829/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 11 Oct 2026.

## Builds on (most cited first, 11 of 11)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Mind the duality gap: safer rules for the Lasso](https://mlsanity.com/paper/1505.03410/) (2015)
- [Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling](https://mlsanity.com/paper/1602.02485/) (2016)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Boosting Frank-Wolfe by Chasing Gradients](https://mlsanity.com/paper/2003.06369/) (2020)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [Scaling SVM and Least Absolute Deviations via Exact Data Reduction](https://mlsanity.com/paper/1310.7048/) (2013)
- [Active set complexity of the Away-step Frank-Wolfe Algorithm](https://mlsanity.com/paper/1912.11492/) (2019)
- [Avoiding bad steps in Frank Wolfe variants](https://mlsanity.com/paper/2012.12737/) (2020)
- [A Novel Frank-Wolfe Algorithm. Analysis and Applications to Large-Scale SVM Training](https://mlsanity.com/paper/1304.1014/) (2013)

## Abstract (arXiv)

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(tfrackρlogtfrac1τ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 L2 margins, LIBLINEAR's dual solver is up to 4.5× faster on the separable L2 margin, and our solver is one to three orders of magnitude slower than LIBLINEAR's Newton solver on dense-support L2 margins and than LIBSVM on a nearly touching kernel hull. Its edge is the certificate, not speed.