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

Mayank Gupta

cs.LGOct 11, 2026

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

Authors: Mayank Gupta

Organizations: Independent Researcher

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(\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.

Figures & tables

cell	dataset	$n_{k}$ / $d$	ETA (s)	baseline (s)	conv	dist. ETA / base	acc. ETA / base	oracle
LIN	gisette	6000 / 5000	$38.2\pm 3.2$	$38.5\pm 3.1$ [ $34.0\pm 3.2$ ]	5/5	3.6638 / 3.6640	.981 / .981	1.5 [1.4]
KHM	gisette	6000 / 5000	$64.6\pm 6.2$	$75.6\pm 3.1$	5/5	.05215 / .05215	.979 / .979	2.6
KHM	ijcnn1	9853 / 22	$242\pm 69$	$1.1\pm 0.2$	5/5	.00430 / .00430	.946 / .946	2.6
KHM	a9a	10000 / 123	$>600$	$18.5\pm 2.0$	0/5	$\leq$ .00002 / .0033	.685 / .752	6.0
KHM	covtype	10000 / 54	$>600$	$122\pm 33$ (maxiter)	0/5	$\leq$ .00044 / .00025	.711 / .712	7.6
KHM	w8a	6479 / 300	$7.2\pm 20.1$	—	5/5	hulls intersect	—	0.5

Table 1: Regime battery on real data, five seeds, 600 s per solver, mean

\pm

95% CI. Kernel cells (RBF with width parameter

1/d

) use a class-balanced subsample of

n_{k}

points. Same objective per row: LIN, linear hard margin (ETA with screening vs LIBSVM’s [ 14 ]

C{=}10^{6}

surrogate; our SMO in brackets); KHM, feature-space hard margin (K-ETA vs the same surrogate); KL2, kernel

L_{2}

margin,

C{=}1

(K-ETA vs kernel SMO, exact objective; in brackets LIBSVM on the precomputed

K+I/C

kernel, fit time

+

kernel construction, September machine). conv = seeds in which ETA certified; oracle =

O(nd)

column (ETA) or row (SMO) evaluations, thousands; both cache every column or row they compute; the ETA column is K-ETA on kernel rows. Released code, AMD EPYC 9754 (Appendix C ).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Certified relative gap of ETA on a9a, w8a and ijcnn1 (

L_{2}

C=0.1

, uncapped, seed 0, AMD EPYC 7B13), versus iteration and wall-clock: linear-rate convergence in the dense-support regime, reaching the certified

10^{-3}

259

–

792

s against the

600

s cap of Table 2 . Heuristically (

\delta

has no known bound in terms of the class hulls),

n_{s}\approx 0.6n

active atoms forming a near-regular simplex have pyramidal width

\sqrt{2/n_{s}}

times the side [ 3 ] , so

\rho\sim 1/n_{s}

and the cost is

O(n^{2})

-type.

dataset ( $n+m$ / $d$ )	$C$	ETA (s)	SMO (s)	LIBLINEAR (s)	ETA gap at stop	acc. ETA / SMO / LIBLINEAR
gisette (6,000 / 5,000)	0.1	$19.3\pm 2.4$	$16.7\pm 2.6$	$261\pm 4$	$9\times 10^{-4}$	.981 / .981 / .981
	1	$20.6\pm 3.5$	$15.9\pm 3.3$	$1{,}893\pm 41$	$10\times 10^{-4}$	.981 / .981 / .981
	10	$20.9\pm 1.4$	$19.6\pm 1.1$	$4{,}380\pm 277$	$10\times 10^{-4}$	.981 / .981 / .978
a9a (32,561 / 123)	0.1	$583\pm 17^{\ast}$	$163\pm 4$	$1.9\pm 0.1$	$(9.9$ – $11)\times 10^{-4}$	.849 / .849 / .849
	1	cap	cap	$3.2\pm 0.8$	0.66 [0.55, 0.85]	.840 / .850 / .849
	10	cap	cap	$1.1\pm 0.1$	1.2 [1.2, 1.2]	.594 / .786 / .849

Appendix

Table 2:

L_{2}

soft-margin battery: five seeds, 600 s per solver for ETA and our SMO (our own implementation; LIBSVM would need an

n\times n

precomputed kernel), LIBLINEAR (primal Newton solver, Appendix C ) at tolerance

10^{-6}

with no time cap; released code with a full SMO row cache, up to four single-threaded cells at a time on the AMD EPYC 9754 machine, except covtype (below). Mean

\pm

95% CI, which on the fixed-split datasets (all but covtype) measures timing noise only (w8a,

C{=}0.1

: one LIBLINEAR seed took

71

s, the other four

12

–

14

s). “cap” = stopped at the time or iteration cap in every seed; ∗ four of five seeds converged within the cap, the mean counting the capped seed at

600

s. ETA’s certified relative gap is reported at its stopping point (mean [min, max]); accuracies are those of the returned iterate. covtype: ETA and SMO from the September run on the earlier machine with SMO’s 512-row cache, because a full cache needs about

80

GB (Appendix C ); LIBLINEAR on an AMD EPYC 7B13, whose objective values match the September run’s to seven or more significant digits.

instance	schedule	time (s)	iterations	drops	skips	distance
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	unconditional	0.8	16	0	0	55.339365
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	Lemma A.9	0.7	16	0	0	55.339365
$L_{2}$ overlap, $d{=}100$ , $C{=}1$	unconditional	23.1	12,311	785	0	0.078400
$L_{2}$ overlap, $d{=}100$ , $C{=}1$	Lemma A.9	21.5	10,701	599	316	0.078400
$L_{2}$ overlap, $d{=}1000$ , $C{=}1$	unconditional	14.2	2,901	182	0	0.578143
$L_{2}$ overlap, $d{=}1000$ , $C{=}1$	Lemma A.9	14.9	3,001	180	121	0.578143

Appendix

Table 3: Two-sided schedules on the synthetic instances of this appendix (September run) (

n{=}5{,}000

per class,

k{=}16

): the unconditional

V

-then-

W

order of the submitted version versus the schedule of Lemma A.9 (larger-gap side first, second side skipped after a drop). Drop steps and skipped second-side steps are counted over the run.

dataset	$C$	tol	Newton (s)	Newton primal	dual (s)	dual primal	acc. Newton / dual
gisette	0.1	$10^{-4}$	$40.1\pm 0.5$	0.15345 ( $+3.4\%$ )	$3.0\pm 0.1$	0.14835 ( $+0.0\%$ )	.978 / .981
		$3\times 10^{-5}$	$85.7\pm 0.8$	0.14922 ( $+0.6\%$ )	$3.3\pm 0.2$	0.14835 ( $+0.0\%$ )	.980 / .981
		$10^{-5}$	$151\pm 2$	0.14842 ( $+0.05\%$ )	$3.7\pm 0.6$	0.14835 ( $+0.0\%$ )	.981 / .981
		$10^{-6}$	$269\pm 2$	0.14835 ( $+0.0\%$ )	$4.5\pm 0.7$	0.14835 ( $+0.0\%$ )	.981 / .981
gisette	1	$10^{-4}$	$3.0\pm 0.2$	0.18440 ( $+24\%$ )	$2.9\pm 0.2$	0.14893 ( $+0.0\%$ )	.974 / .981
		$3\times 10^{-5}$	$4.0\pm 0.3$	0.18343 ( $+23\%$ )	$3.2\pm 0.1$	0.14893 ( $+0.0\%$ )	.974 / .981

Appendix

Table 4: LIBLINEAR’s two solvers across tolerances on gisette and a9a ( src/liblin_sweep.py ; five seeds, three processes at a time and nothing else running, AMD EPYC 7B13). Newton: LinearSVC with dual='auto' , which selects the primal trust-region Newton solver, the one the batteries ran; dual: dual=True , dual coordinate descent. Primal objective relative to the best known value

P^{*}

(

0.14835

and

0.14893

on gisette at

C{=}0.1

and

1

, ETA’s certified values;

687.07

and

6{,}869.7

on a9a); on these fixed splits every seed returns the same primal and accuracy. On a9a at

C{=}1

the dual solver hit its

2\times 10^{5}

iteration cap in four of five seeds at

10^{-6}

and in all five at

10^{-8}

, so those times are lower bounds.

dataset	$C$	$P^{*}$	ETA $1\%$	ETA $0.1\%$	cert. $1\%$	cert. $10^{-3}$	LIBLINEAR $1\%$ , Newton / dual
gisette	0.1	0.14835	17 s	18 s	19 s	19 s	86 s / 3.0 s
gisette	1	0.14893	20 s	21 s	21 s	22 s	1,813 s / 2.9 s
gisette	10	0.14899	20 s	21 s	22 s	22 s	none at $10^{-6}$ / not run
a9a	0.1	687.07	218 s	295 s	402 s	510 s	0.5 s / 131 s
w8a	0.1	108.80	435 s	559 s	670 s	792 s	$\leq 24$ s / not run
ijcnn1	0.1	550.61	80 s	125 s	189 s	259 s	$\leq 0.14$ s / not run

Appendix

Table 5: Time to

1\%

of the optimum, seed-0 traces. The ETA columns measure dual progress and LIBLINEAR’s column primal progress, so this is not a matched primal comparison (the primal of ETA’s returned

(w,b)

is not recorded in the traces). For ETA the certified dual value

2/\mathrm{UB}_{t}^{2}

increases to the optimum, so

s_{t}=1-(2/\mathrm{UB}_{t}^{2})/P^{*}

with

P^{*}

the best known primal (the lower of LIBLINEAR’s best value and ETA’s certified value); “certified

1\%

” is the first time the certificate itself proves

1-\mathrm{LB}_{t}^{2}/\mathrm{UB}_{t}^{2}\leq 1\%

, and “cert.

10^{-3}

” the time the stopping rule

(\mathrm{UB}-\mathrm{LB})/\mathrm{UB}\leq 10^{-3}

is met. ETA’s a9a, w8a and ijcnn1 times are from the uncapped runs of Figure 1 ( src/time_to_tol.py ); its gisette times are from the battery traces of Table 2 . Machines: ETA’s gisette entries and LIBLINEAR’s upper bounds come from the EPYC 9754, ETA’s a9a, w8a and ijcnn1 entries and LIBLINEAR’s swept times from the EPYC 7B13. LIBLINEAR: the mean time of the coarsest tolerance of Table 4 whose primal is within

1\%

P^{*}

in every seed, for the Newton and the dual solver; where the sweep did not run, the matched

10^{-6}

Newton run of Table 2 , an upper bound (on gisette at

C{=}10

that run stops

4.3\%

above

P^{*}

). On the remaining cells ETA is not within

1\%

at the 600 s cap (

s=3

–

89\%

instance	variant	$k$	time (s)	scan	col	step	rest	iterations	columns	drops
gisette $L_{2}$	MDM	1	$12.1\pm 0.2$	0.2	10.2	0.8	0.9	4,946	1,300	0
gisette $L_{2}$	MDM, exact	1	$12.0\pm 0.2$	0.1	10.6	0.7	0.7	3,546	1,341	0
gisette $L_{2}$	guarded	1	$12.8\pm 0.1$	0.2	10.5	1.5	0.6	3,471	1,334	82
gisette $L_{2}$	guarded, exact	1	$12.9\pm 0.4$	0.1	10.7	1.5	0.7	3,416	1,341	87
gisette $L_{2}$	AFW, exact	1	$206.7\pm 5.3$	7.6	10.8	90.9	97.3	527,108	1,340	0
gisette $L_{2}$	block	16	$13.0\pm 0.1$	0.1	11.6	1.2	0.2	831	1,480	301

Appendix

Table 6: Step ablation on real data with a time split, isolated runs ( src/step_profile.py : three seeds, each configuration alone in its own process on an otherwise idle AMD EPYC 7B13, with the final code): the gisette

L_{2}

margin (

C{=}1

d{=}5{,}000

) and the four kernel

L_{2}

cells of Table 1 . MDM is plain pairwise FW (single transfers, no guard, no fallback) with the prioritised receiver search and schedule of the other rows; “exact” rows replace that search by an exact linear minimisation over all points; AFW is away-step FW with exact search; guarded

k{=}1

is Algorithm 3 with a single pair (guard and case-(b) fallback active); BPCG is the blended pairwise step of [ 12 ] on the side supports (Table 7 ). Split of the ETA time: scan = the score scan and pair selection; col = Gram or kernel column computation; step = the step itself (block assembly, guard, line search, cache and score update); rest = certificate and bounds. Drops = away fallbacks that removed a support index. Every run converged to the certified gap, distances agreeing to that tolerance and test accuracies to

2\times 10^{-4}

per dataset and seed, except AFW on the ijcnn1, a9a and covtype kernel cells, which timed out at

600

s with certified gaps of

0.0012

–

0.004

(iterations and columns at the cap shown).

cell	solver	time (s)	iterations	columns	drops
gisette $L_{2}$	ETA, $k{=}16$	$13.0\pm 0.1$	831	1,480	301
gisette $L_{2}$	BPCG, product	$13.9\pm 0.8$	10,470	1,322	87
gisette $L_{2}$	BPCG, side	$12.1\pm 0.7$	7,930	1,300	75
gisette KL2	ETA, $k{=}16$	$35.1\pm 6.0$	251	3,653	4
gisette KL2	BPCG, product	$39.7\pm 3.4$	8,702	3,641	3
gisette KL2	BPCG, side	$36.2\pm 4.0$	4,375	3,643	3

Appendix

Table 7: BPCG [ 12 ] versus block ETA (

k{=}16

) on the same objective with the same certificate (

\varepsilon{=}10^{-3}

), the same column cache and the same 600 s cap (

L_{2}

margins at

C{=}1

), three seeds, each configuration alone in a fresh process on the AMD EPYC 7B13 ( src/step_profile.py ). “product”: BPCG on the

nm

product atoms

v_{i}-w_{j}

( src/bpcg.py ); “side”: the same blended pairwise rule on the side supports ETA uses ( src/corrective_fw.py ). Both BPCG rows were run after a fix to their kernel-column routine, which had recomputed a class’s squared norms for every RBF column (

3.5\times

ETA’s column cost; columns are bit-identical). Every run converged; distances agree per cell and seed to

10^{-6}

and test accuracies to

2\times 10^{-4}

. Columns are kernel or Gram columns computed; drops count ETA’s away drops and BPCG’s capped local steps.

instance	$k$	time (s)	iterations	columns	drops
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	1	0.7	301	104	0
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	4	0.7	36	103	0
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	16	0.7	16	103	0
hard margin, $d{=}1000$ , $\varepsilon{=}10^{-5}$	32	0.7	16	109	0
$L_{2}$ overlap, $d{=}100$ , $C{=}1$	1	17.4	72,546	1,345	0
$L_{2}$ overlap, $d{=}100$ , $C{=}1$	4	23.1	24,606	1,632	416

Appendix

Table 8: Block-size ablation on the synthetic instances (released code, September run): single MDM (

k{=}1

) versus blocks of

k

transfers. Iterations fall with

k

; wall-clock need not: blocks touch more columns, and on the

d{=}100

L_{2}

instance they add receivers (

1{,}345

3{,}076

columns) and single MDM is fastest.

Figure 2: Safe screening: wall-clock speed-up vs dimension at two tolerances on the separated synthetic protocol; labels are surviving points of

10{,}000

. Made with the toward-step solver of the development phase ( src/shrink_benchmark.py ); the rule and its activation do not depend on the step.

Figure 3: Time to certified solution on seven problem classes: optimised ETA (

k{=}16

with screening on the hard-margin classes,

k{=}32

on the

L_{2}

class,

k{=}8

on MNIST) vs the comparison configuration (the toward-step algorithm of [ 2 ] on the hard-margin classes, single MDM on the

L_{2}

and MNIST classes, pairwise K-ETA on RBF) vs the best standard solver per class; five trials per class (October rerun, AMD EPYC 9754), mean with 95% CI. The

\nu

-SVM row has no comparison bar because the toward-step algorithm of [ 2 ] has no reduced-hull variant (reduced hulls need capped transfers).

Support Vector Machines

Support vector machines learn margin-based classifiers and regressors using linear or kernel-defined decision boundaries.

See all 42 papers

Sep 15, 2026

Sharp margin-based generalization bounds for realizable SVM

Let the exact homogeneous hard-margin support vector machine be trained on

m

independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant

C

such that

\Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ.

Here

γ_m

is the empirical homogeneous margin,

u_m

is the exact minimum-norm unit-margin separator,

r_m

is the largest training radius, and

K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2

\{γ_m>0\}

. The proof is driven by a deterministic deletion problem. Given vectors

x_1,\ldots,x_n

in the unit ball, delete a set

B

of constraints and let

u_B

be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that

\norm{u_B}^2\le k

and that every deleted vector has nonpositive score under

u_B

. We prove that a family of such deletion sets of cardinality

q

has size at most

\exp(8k+2q)

. The conceptual step is an exact identity obtained from the KKT representation of

u_B

. For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.

Steve Hanneke, Aryeh Kontorovich

Support Vector Machines Statistical Learning Theory Generalization Bounds

Ask PDF

Mar 26, 2026

Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise

Robust Support Vector Machines (R-SVMs) address feature noise by adopting a worst-case robust formulation that explicitly incorporates uncertainty sets into training. While this robustness improves reliability, it also leads to increased computational cost. In this work, we develop safe sample screening rules for R-SVMs that reduce the training complexity without affecting the optimal solution. To the best of our knowledge, this is the first study to apply safe screening techniques to worst-case robust models in supervised machine learning. Our approach safely identifies training samples whose uncertainty sets are guaranteed to lie entirely on either side of the margin hyperplane, thereby reducing the problem size and accelerating optimization. Owing to the nonstandard structure of R-SVMs, the proposed screening rules are derived from the Lagrangian duality rather than the Fenchel-Rockafellar duality commonly used in recent methods. Based on this analysis, we first establish an ideal screening rule, and then derive a practical rule by adapting GAP-based safe regions to the robust setting. Experiments demonstrate that the proposed method significantly reduces training time while preserving classification accuracy.

Tan-Hau Nguyen, Thu-Le Tran, Kien Trung Nguyen

Can Tho University, Vietnam

Support Vector Machines Robust Optimization

Ask PDF

Aug 24, 2026

Mirror descent algorithms with logarithmic barriers

This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard approaches cannot be applied when the solution lies on the boundary, where the Bregman divergence blows up. We show that, in a specific setting, both methods enjoy an

O(\log k / k)

rate, which is also tight. In addition, our contributions include: (i) a new technique for handling the blow-up; (ii) a resolution of a gap in the theory of relative smoothness; and (iii) a comparison of the proposed approach with interior-point methods.

Alberto De Marchi, Yura Malitsky, Adrien B. Taylor

University of the Bundeswehr Munich, Germany. · Faculty of Mathematics, University of Vienna, Austria. · Inria, DI ENS, CNRS, PSL Research University, France.

Mirror Descent

Ask PDF

Abstract

Support Vector Machines

Explore similar work

Sharp margin-based generalization bounds for realizable SVM

Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise

Mirror descent algorithms with logarithmic barriers