Communication-Efficient Parallel Block Minimization for Kernel Machines

2016-08-05 · Cho-Jui Hsieh, Si Si, Inderjit S. Dhillon

Kernel machines often yield superior predictive performance on various tasks; however, they suffer from severe computational challenges. In this paper, we show how to overcome the important challenge of speeding up kernel machines. In particular, we develop a parallel block minimization framework for solving kernel machines, including kernel SVM and kernel logistic regression. Our framework proceeds by dividing the problem into smaller subproblems by forming a block-diagonal approximation of the Hessian matrix. The subproblems are then solved approximately in parallel. After that, a communication efficient line search procedure is developed to ensure sufficient reduction of the objective function value at each iteration. We prove global linear convergence rate of the proposed method with a wide class of subproblem solvers, and our analysis covers strongly convex and some non-strongly convex functions. We apply our algorithm to solve large-scale kernel SVM problems on distributed systems, and show a significant improvement over existing parallel solvers. As an example, on the covtype dataset with half-a-million samples, our algorithm can obtain an approximate solution with 96% accuracy in 20 seconds using 32 machines, while all the other parallel kernel SVM solvers require more than 2000 seconds to achieve a solution with 95% accuracy. Moreover, our algorithm can scale to very large data sets, such as the kdd algebra dataset with 8 million samples and 20 million features.

📄 PDF Abstract BibTeX arXiv:1608.02010

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

Scalable Dual Coordinate Descent for Kernel Methods

2024-06-26 · Zishan Shao, Aditya Devarakonda

Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) are important iterative methods for solving convex optimization problems. In this work, we develop scalable DCD and BDCD methods for the kernel suppo…

Federated Empirical Risk Minimization via Second-Order Method

2023-05-27 · Song Bian, Zhao Song, Junze Yin

Many convex optimization problems with important applications in machine learning are formulated as empirical risk minimization (ERM). There are several examples: linear and logistic regression, LASSO, kernel regression,…

Federated Learning quantile regression regression Variational Inference

High-performance Kernel Machines with Implicit Distributed Optimization and Randomization

2014-09-03 · Vikas Sindhwani, Haim Avron

In order to fully utilize "big data", it is often required to use "big models". Such models tend to grow with the complexity and size of the training data, and do not make strong parametric assumptions upfront on the nat…

Distributed Optimization Vocal Bursts Intensity Prediction

Nonlocal Transition Kernel for Efficient Learning of Restricted Boltzmann Machines

2026-08-18 · Kaiji Sekimoto, Muneki Yasuda arxiv

Learning restricted Boltzmann machines (RBMs) is computationally challenging because it requires expectations whose exact evaluation is generally intractable. The expectations are typically evaluated using a sampling app…

Avoiding Synchronization in First-Order Methods for Sparse Convex Optimization

2017-12-17 · Aditya Devarakonda, Kimon Fountoulakis, James Demmel, Michael W. Mahoney

Parallel computing has played an important role in speeding up convex optimization methods for big data analytics and large-scale machine learning (ML). However, the scalability of these optimization methods is inhibited…

subspace methods