A Novel and Safe Two-Stage Screening Method for Support Vector Machine.

Area of Science:

• Machine Learning
• Computational Science

Background:

• Support Vector Machines (SVMs) face scalability challenges with large datasets.
• Existing safe screening rules like Dual Screening with Variational Inequalities (DVI) and Dynamic Screening Rule (DSR) have limitations in efficiency or safety.
• DVI is efficient but potentially unsafe with inaccurate solvers; DSR is safe but requires accurate solutions for efficiency.

Purpose of the Study:

• To propose a novel Two-Stage Screening (TSS) rule for enhancing SVM scalability.
• To leverage the strengths and mitigate the weaknesses of existing DVI and DSR methods.
• To ensure both the safety and efficiency of the sample screening process for large-scale SVM training.

Main Methods:

• A two-stage approach is introduced: initial screening using DVI followed by DSR embedded within the solver.
• DVI is used first to reduce dataset size and provide an initial solution for DSR.
• A post-checking step is included for safety verification, and theoretical analysis estimates DVI's deviation upper bound, leading to Safe-DVI.

Main Results:

• The proposed TSS rule effectively reduces SVM scale while maintaining safety.
• The integration of DVI and DSR improves solver accuracy and strengthens DVI's safety.
• Numerical experiments on various datasets confirm the efficiency and safety of the TSS method.
• A kernel version of TSS is developed for nonlinear SVM problems.

Conclusions:

• The TSS rule offers a robust solution for applying SVMs to large-scale and nonlinear datasets.
• The method successfully combines the efficiency of DVI with the safety guarantees of DSR.
• TSS represents a significant advancement in safe and efficient sample screening for machine learning algorithms.