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

Hard-margin SVM training is the distance problem between two convex hulls, which the Trian- gle 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 rate does not de- pend on k, so the theory shows that aggregation is safe, while the saving in scans is measured rather than proved. Since the TA certificate is the Frank–Wolfe gap divided by the current dis- tance, gap-safe screening applies, and we bound the iteration after which it has removed every non-support point by O((k/ρ) log (1/τ) ) up to logarithmic factors in the geometry, ρ the rate constant and τ the optimal-face margin. Every inequality has a numerical check. On five LIBSVM benchmarks the solver matches the baselines to five digits wherever both converge, wins or ties against LIB- SVM and kernel SMO on sparse-support cells, and is one to two orders of magnitude slower on dense-support L2 margins and nearly touching kernel hulls, where LIBLINEAR finishes in seconds. We report both sides.