Combining DC algorithms (DCAs) and decomposition techniques for the training of nonpositive-semidefinite kernels

Area of Science:

• Machine Learning
• Optimization Theory

Background:

• Support Vector Machines (SVMs) are widely used for classification.
• Standard SVM training methods struggle with kernels not satisfying Mercer's condition (nonpositive-semidefinite kernels).

Purpose of the Study:

• To develop a new decomposition method for SVM training that handles nonpositive-semidefinite kernels.
• To integrate Difference of Convex (DC) optimization techniques into SVM decomposition algorithms.

Main Methods:

• Incorporation of truncated Difference of Convex Algorithms (DCAs) into SVM decomposition.
• Development of a working set selection rule using second-order information for SMO-type decomposition.

Main Results:

• The proposed method achieves a sufficient decrease in the objective function at each iteration.
• An asymptotic convergence proof is established without blockwise convexity assumptions.
• Numerical results demonstrate robustness and efficiency compared to existing software.

Conclusions:

• The new DC optimization-based decomposition method effectively addresses SVM training with challenging kernels.
• The algorithm offers a theoretically sound and practically efficient solution for a broader range of SVM applications.