Sublinear Optimization for Machine Learning

被引：55

作者：

Clarkson, Kenneth L. ^{[2
]}

Hazan, Elad ^{[1
]}

Woodruff, David P. ^{[2
]}

机构：

[1] Technion Israel Inst Technol, IL-32000 Haifa, Israel

[2] IBM Almaden Res Ctr, San Jose, CA USA

来源：

JOURNAL OF THE ACM | 2012年 / 59卷 / 05期

基金：

以色列科学基金会;

关键词：

Algorithms; ALGORITHM;

D O I：

10.1145/2371656.2371658

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this article we describe and analyze sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and L-2-SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model.

引用

页数：49

共 23 条

[1] [Anonymous], 2003, P 20 INT C MACH ICML
[2] A polynomial-time algorithm for learning noisy linear threshold functions
Blum, A
Frieze, A
Kannan, R
Vempala, S
[J]. ALGORITHMICA, 1998, 22 (1-2) : 35 - 52
[3] Bylander T., 1994, Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 94, P340, DOI 10.1145/180139.181176
[4] On the generalization ability of on-line learning algorithms
Cesa-Bianchi, N
Conconi, A
Gentile, C
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (09) : 2050 - 2057
[5] Cesa-Bianchi N., 2010, P C LEARNING THEORY, P218
[6] Clarkson KL, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P922
[7] Cover T.M., 2006, ELEMENTS INFORM THEO, V2nd ed
[8] DIACONIS P, 1980, ANN PROBAB, V8, P745, DOI 10.1214/aop/1176994663
[9] Dunagan John., 2004, PROC 36 ANN ACM S TH, P315
[10] Frank M., 1956, Naval Res. Logist. Q., V3, P95, DOI [https://doi.org/10.1002/nav.3800030109, 10.1002/nav.3800030109, DOI 10.1002/NAV.3800030109]

← 1 2 3 →