Sublinear Optimization for Machine Learning
作者： Kenneth L. Clarkson , Elad Hazan , David P. Woodruff
DOI: 10.1109/FOCS.2010.50
关键词:
摘要: We give sub linear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our can be extended to kernelized versions of these problems, SVDD, hard margin SVM, $L_2$-SVM, which were not known before. These new use a combination novel sampling techniques multiplicative update algorithm. lower bounds show the running times many our nearly best possible unit-cost RAM model. also implementations semi-streaming setting, obtaining first low pass polylogarithmic space time achieving arbitrary factor.
princeton.edu
sci-hub.se 参考文章(17)
Ankan Saha, S. V. N. Vishwanathan, Efficient Approximation Algorithms for Minimum Enclosing Convex Shapes ,(2009)
Bernhard Schölkopf, Alexander J. Smola, A short introduction to learning with kernels Lecture Notes in Computer Science. pp. 41- 64 ,(2003) , 10.1007/3-540-36434-X_2
S. Muthukrishnan, Data Streams: Algorithms and Applications ,(2005)
Rocco A. Servedio, On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm Proceedings of the twelfth annual conference on Computational learning theory - COLT '99. pp. 296- 307 ,(1999) , 10.1145/307400.307474
Tom Bylander, Learning linear threshold functions in the presence of classification noise Proceedings of the seventh annual conference on Computational learning theory - COLT '94. pp. 340- 347 ,(1994) , 10.1145/180139.181176
Michael D. Grigoriadis, Leonid G. Khachiyan, A sublinear-time randomized approximation algorithm for matrix games Operations Research Letters. ,vol. 18, pp. 53- 58 ,(1995) , 10.1016/0167-6377(95)00032-0
John Dunagan, Santosh Vempala, A simple polynomial-time rescaling algorithm for solving linear programs symposium on the theory of computing. pp. 315- 320 ,(2004) , 10.1145/1007352.1007404
S.A. Plotkin, D.B. Shmoys, E. Tardos, Fast approximation algorithms for fractional packing and covering problems [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. pp. 495- 504 ,(1991) , 10.1109/SFCS.1991.185411
N. Cesa-Bianchi, A. Conconi, C. Gentile, On the generalization ability of on-line learning algorithms IEEE Transactions on Information Theory. ,vol. 50, pp. 2050- 2057 ,(2004) , 10.1109/TIT.2004.833339
Hamid Zarrabi-Zadeh, Timothy Moon-Yew Chan, A Simple Streaming Algorithm for Minimum Enclosing Balls canadian conference on computational geometry. ,(2006)