Linear convergence of proximal gradient method for linear sparse SVM.

Area of Science:

• Machine Learning
• Optimization Algorithms
• Statistical Learning Theory

Background:

• Support Vector Machines (SVM) are powerful classification tools.
• Hinge loss is commonly used in SVM but lacks strong convexity/smoothness properties.
• Achieving linear convergence rates for non-strongly convex problems is challenging.

Purpose of the Study:

• To establish the linear convergence rate for sparse linear SVM with hinge loss.
• To analyze the performance of proximal gradient methods for this problem.
• To investigate the interplay between numerical and statistical convergence.

Main Methods:

• Utilized the proximal gradient method for composite functions.
• Applied the method to a sequence of regularization parameters to compute the approximate solution path.
• Analyzed convergence rates considering both numerical and statistical aspects.

Main Results:

• Established linear convergence rate for sparse linear SVM up to statistical accuracy.
• Demonstrated convergence to the population truth, not necessarily the exact solution.
• Showed that O(log*s*) iterations are sufficient for an approximate solution, with O(log n) stages for near-oracle rates.

Conclusions:

• Proximal gradient methods can achieve linear convergence for sparse linear SVM with hinge loss.
• The method effectively balances numerical and statistical convergence.
• The findings offer theoretical guarantees for sparse SVM optimization.