Randomized Algorithms for Large scale SVMs

2009/09/19 by Vinay Jethava, Jethava, Vinay, Krishnan Suresh +5
Computer Science · #Advanced Image and Video Retrieval Techniques #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.0909.3609

openalex publication_date 2009/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a randomized algorithm for training Support vector machines(SVMs) on large datasets. By using ideas from Random projections we show that the combinatorial dimension of SVMs is O(log n) with high probability. This estimate of combinatorial dimension is used to derive an iterative algorithm, called RandSVM, which at each step calls an existing solver to train SVMs on a randomly chosen subset of size O(log n). The algorithm has probabilistic guarantees and is capable of training SVMs with Kernels for both classification and regression problems. Experiments done on synthetic and real life data sets demonstrate that the algorithm scales up existing SVM learners, without loss of accuracy.

Related

• Random matrices meet machine learning: a large dimensional analysis of LS-SVM
• A Class of Parallel Decomposition Algorithms for SVMs Training
• Approximate Stochastic Subgradient Estimation Training for Support\n Vector Machines
• But How Does It Work in Theory? Linear SVM with Random Features
• Optimal Learning Rates for Localized SVMs