Trasferimenti a blocchi con salvaguardia per la distanza tra politopi: convergenza lineare con costanti esplicite e selezione certificata dal gap per l’addestramento delle SVM

Abstract degli autori

L’addestramento di una SVM a margine rigido equivale a calcolare la distanza tra due inviluppi convessi, un problema che il Triangle Algorithm (TA) risolve con un gap di dualità certificato. Proponiamo i \emph{trasferimenti a blocchi con salvaguardia}: $k$ trasferimenti Mitchell--Demyanov--Malozemov (MDM) per scansione vengono aggregati in un’unica ricerca esatta lungo la direzione, confrontati con il miglior trasferimento singolo a un costo indipendente dal numero di punti $n$ e sostituiti da un passo di allontanamento quando il trasferimento principale è limitato dalla capacità. Sul politopo delle differenze di Minkowski, dove la funzione obiettivo è $1$-fortemente convessa, dimostriamo la convergenza lineare globale con costanti esplicite e senza limiti combinatori sui passi di scambio; la contrazione per passo è indipendente da $k$ e solo il limite sul numero di passi che eliminano un punto cresce con $k$. L’aggregazione è quindi sicura in modo dimostrabile, mentre il risparmio di scansioni è misurato, non dimostrato. Poiché il certificato del TA è il gap di Frank--Wolfe diviso per la distanza corrente, si può applicare una selezione sicura basata sul gap. Stabiliamo inoltre un limite $O\!\left(\tfrac{k}ρ\log\tfrac{1}τ\right)$, a meno di fattori logaritmici legati alla geometria, per l’iterazione dopo la quale sono stati eliminati tutti i punti di peso nullo esterni alle facce ottimali; $ρ$ è la costante del tasso di convergenza e $τ$ il margine delle facce ottimali. Su cinque benchmark LIBSVM, con baseline più eque rispetto a quelle della nostra versione presentata, il solver coincide con le baseline fino alla quarta o quinta cifra ovunque entrambi convergano, eguaglia LIBSVM sui margini rigidi con supporto sparso e supera il nostro metodo blended pairwise conditional gradients (BPCG). Tuttavia, il nostro codice di ottimizzazione minima sequenziale (SMO) con cache completa lo eguaglia o lo supera sui margini $L_2$ con kernel, il solver duale di LIBLINEAR è fino a $4.5\times$ più veloce sul margine $L_2$ separabile e il nostro solver è da uno a tre ordini di grandezza più lento del solver di Newton di LIBLINEAR sui margini $L_2$ con supporto denso e di LIBSVM su un inviluppo convesso nel kernel quasi a contatto. Il suo punto di forza è il certificato, non la velocità.