Sublinear optimization for machine learning

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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 L2-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.

Original languageEnglish (US)
Article number23
JournalJournal of the ACM
Volume59
Issue number5
DOIs
StatePublished - Oct 1 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Sublinear optimization for machine learning'. Together they form a unique fingerprint.

Cite this