Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise
Tan-Hau Nguyen, Thu-Le Tran, Kien Trung Nguyen · 2026
Read Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise by Tan-Hau Nguyen, Thu-Le Tran, Kien Trung Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-25221.txt.
Introduction
Nguyen and co-authors speed up robust support vector machines by safely dropping easy training points. Robust training guards against noisy features, but the worst-case setup costs far more time. Their screening rules prove some points sit fully on one side of the margin, noise set and all. Those points cannot change the final model, so they can leave the problem early. The rules come from Lagrangian duality, since the robust form breaks standard tools. A gap-based version proves practical. Training runs much faster with accuracy intact.
Catalog record
| CREATOR | Tan-Hau Nguyen, Thu-Le Tran, Kien Trung Nguyen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45922 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.25221
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise Tan-Hau Nguyen, Thu-Le Tran, Kien Trung Nguyen Abstract 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. 1 Introduction Support Vector Machines (SVMs) [ 3 ; 2 ; 21 ] have long been regarded as one of the most influential methods in supervised learning, owing to their solid theoretical foundation and strong empirical performance. A key property of SVMs is that the resulting decision boundary depends only on a small subset of training samples, known as support vectors, while the remaining samples do not influence the optimal solution. Despite these appealing properties, training SVMs can be computationally expensive for large-scale datasets, as standard solvers must process the entire training set throughout the optimization procedure. This is inherently inefficient, since the optimal solution ultimately depends on only a small number of support vectors. However, because the identities of these support vectors are unknown before solving the optimization problem, identifying and removing redundant samples in advance is nontrivial. This naturally motivates the development of screening techniques with theoretical guarantees, which aim to safely eliminate irrelevant training samples before or during training. To address this challenge, safe screening techniques have been developed to identify elements of an optimization problem that are guaranteed to be inactive at optimality and can therefore be safely removed [ 5 ; 13 ; 14 ; 10 ; 11 ; 12 ; 26 ; 15 ; 24 ; 7 ; 17 ; 20 ] . Depending on the target, safe screening can be classified into feature screening [ 5 ] , sample screening [ 14 ] , and hybrid approaches that combine both [ 16 ] . In the context of SVMs, sample screening is particularly important, as it reduces the training set size without affecting the optimal classifier. Beyond the choice of screening target, safe screening methods can also be distinguished by how the screening rules are constructed and applied during optimization. From a methodological perspective, safe screening strategies can be classified into static [ 5 ] , sequential [ 22 ] , and dynamic [ 1 ] approaches, depending on whether screening rules are applied once, along a regularization path, or iteratively refined during optimization. Another important classification is based on the geometry of the safe region used to localize the optimal solution. In sample screening, the safe region contains a primal solution, whereas in feature screening it contains a dual solution. Common constructions include ball-shaped [ 5 ] , dome-shaped [ 18 ] , ellipsoid-shaped [ 4 ; 9 ] , linear programming based approach [ 16 ] and region-free approach [ 8 ] . Among these, GAP ball [ 6 ; 10 ; 12 ] and its refinement RYU ball [ 19 ] regions have emerged as a state-of-the-art choice due to their strong theoretical guarantees and practical effectiveness. Despite their strong guarantees and practical success in classical SVMs, existing safe screening methods have been primarily developed under standard SVM formulations. However, classical SVMs are known to be sensitive to noise, which can significantly degrade generalization performance and motivates the development of robust variants. In robust support vector machines, one typically considers robustness with respect to label noise or feature noise. In this paper, we focus on robustness against feature noise, where uncertainty is explicitly modeled through uncertainty sets around the training samples. One line of research addresses robustness to label noise and outliers by adopting non-convex loss functions, such as the ramp loss. For this class of ramp-loss-based SVMs, safe screening techniques have already been investigated and shown to provide computational benefits [ 25 ] . A different line of work considers robustness against feature noise by optimizing against worst-case perturbations within uncertainty sets. In particular, the Robust SVM (R-SVM) proposed by 23 formulates training as a worst-case robust optimization problem and yields classifiers that are more stable under feature perturbations. However, this robustness comes at the cost of a more challenging optimization problem compared to standard SVMs. Despite the success of safe screening methods for standard SVMs and ramp-loss-based robust SVMs, to the best of our knowledge, no safe screening framework has been developed for the feature-noise R-SVM model of Xu et al. This gap stems from the min–max structure induced by uncertainty sets, which cannot be directly handled by existing screening approaches. Specifically, most existing safe screening frameworks for SVM-type models rely on a composite convex structure of the form f(Aw)+g(w), and are developed under Fenchel-Rockafellar duality. Within this setting, one derives the dual problem, establishes KKT conditions, and constructs screening rules based on a safe region that contains optimal dual solutions. Classical constructions such as the GAP safe ball [ 12 ] and the more recent, tighter RYU safe ball [ 19 ] leverage strong convexity and primal-dual gap bounds inherent to this composite framework. In contrast, the main loss function in R-SVM involves a min-max formulation induced by uncertainty sets and cannot be expressed in the composite form f(Aw) . Consequently, the Fenchel-Rockafellar framework underlying existing GAP and RYU constructions does not directly apply. To overcome this difficulty, we reformulate the R-SVM as a second-order cone program and derive its dual via Lagrangian duality, from which the KKT conditions and screening rules are established. While the RYU ball provides a tighter safe region, its derivation crucially depends on the composite Fenchel-Rockafellar structure and is therefore not compatible with our dual formulation. We thus adapt the GAP safe ball within the Lagrangian framework to construct a valid safe region for the robust R-SVM. To further clarify the positioning of our method within the existing safe screening literature, we summarize the main related approaches in Table 1 . Table 1: Position of our result among closely related safe screening approaches Problem & Reference Noise Screened Methodology Safe region Sparse SVM [ 5 ] — Features Static — SVM [ 14 ] — Samples Sequential Dome Sparse SVM [ 26 ] — Features Sequential Dome Sparse SVM [ 16 ] — Samples, Features Dynamic Ball (GAP) Ramp-loss SVM [ 25 ] Label Samples Dynamic Ball (GAP) R-SVM (This paper) Feature Samples Dynamic Ball (GAP) This paper makes the following contributions. First, we establish