QR Decomposition Framework for Efficient Implementation of Linear Support Vector Machines Using Dual Ascent

Abstract

Support Vector Machines (SVMs) is a popular method to solve standard machine learning tasks like classification, regression or clustering. There are many algorithms to solve the linear SVM classification problem. However, only a few algorithms are optimized on both per iteration cost and convergence. While fast convergence is essential for solving any optimization problem, per iteration cost is critical in resource-limited environments like dedicated embedded solutions for machine learning problems. In this thesis, we propose a novel approach to solve large-scale linear SVM classification problems. The proposed algorithm has low per iteration cost and also converges faster than existing state-of-art solvers.

There are two significant contributions from this thesis. First, we analyzed and improved the performance of the dual ascent (DA) algorithm, which would serve as the optimizing engine for solving SVM classification problem. An analytical model to evaluate the optimum step size and synchronization period for solving a generic quadratic programming optimization problem using DA is presented. Second, we implement SVM using the improved Dual Ascent algorithm. We also introduce a novel approach to tackle low dimensional classification problems of large data sizes via QR decomposition technique.