Large Scale Kernel Learning using Block Coordinate Descent

2016-02-17 · Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman, Benjamin Recht

We demonstrate that distributed block coordinate descent can quickly solve kernel regression and classification problems with millions of data points. Armed with this capability, we conduct a thorough comparison between the full kernel, the Nystr\"om method, and random features on three large classification tasks from various domains. Our results suggest that the Nystr\"om method generally achieves better statistical accuracy than random features, but can require significantly more iterations of optimization. Lastly, we derive new rates for block coordinate descent which support our experimental findings when specialized to kernel methods.

📄 PDF Abstract BibTeX arXiv:1602.05310

Code (0)

등록된 구현이 없습니다.

Tasks

Classification General Classification regression

Alternating Randomized Block Coordinate Descent

2018-07-01 · ICML 2018 7 · Jelena Diakonikolas, Lorenzo Orecchia

Block-coordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in large-scale optimization and machine learning. While various block-coord…

A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis

2024-04-04 · Benjamin Doerr, Joshua Knowles, Aneta Neumann, Frank Neumann

We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimizat…

Scheduling

Asynchronous Parallel Greedy Coordinate Descent

2016-12-01 · NeurIPS 2016 12 · Yang You, Xiangru Lian, Ji Liu, Hsiang-Fu Yu 외

n this paper, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greed…

Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems

2015-11-23 · Zhanxing Zhu, Amos J. Storkey

We consider convex-concave saddle point problems with a separable structure and non-strongly convex functions. We propose an efficient stochastic block coordinate descent method using adaptive primal-dual updates, which …

feature selection

Feature Clustering for Accelerating Parallel Coordinate Descent

2012-12-01 · NeurIPS 2012 12 · Chad Scherrer, Ambuj Tewari, Mahantesh Halappanavar, David Haglin

Large scale $\ell_1$-regularized loss minimization problems arise in numerous applications such as compressed sensing and high dimensional supervised learning, including classification and regression problems. High perf…

Clustering compressed sensing