Nyström-SGD: Fast Learning of Kernel-Classifiers with Conditioned Stochastic Gradient Descent

Pfahler, Lukas; Morik, Katharina

doi:10.1007/978-3-030-10928-8_13

Nyström-SGD: Fast Learning of Kernel-Classifiers with Conditioned Stochastic Gradient Descent

Lukas Pfahler, Katharina Morik

ECML-PKDD 2018 pp. 209-224

doi:10.1007/978-3-030-10928-8_13 /ecmlpkdd/2018/pfahler2018ecmlpkdd-nystromsgd/

Abstract

Kernel methods are a popular choice for classification problems, but when solving large-scale learning tasks computing the quadratic kernel matrix quickly becomes infeasible. To circumvent this problem, the Nyström method that approximates the kernel matrix using only a smaller sample of the kernel matrix has been proposed. Other techniques to speed up kernel learning include stochastic first order optimization and conditioning. We introduce Nyström-SGD, a learning algorithm that trains kernel classifiers by minimizing a convex loss function with conditioned stochastic gradient descent while exploiting the low-rank structure of a Nyström kernel approximation. Our experiments suggest that the Nyström-SGD enables us to rapidly train high-accuracy classifiers for large-scale classification tasks. Code related to this paper is available at: https://bitbucket.org/Whadup/kernelmachine/ .

PDF ECML-PKDD Semantic Scholar

Cite

Text

Pfahler and Morik. "Nyström-SGD: Fast Learning of Kernel-Classifiers with Conditioned Stochastic Gradient Descent." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2018. doi:10.1007/978-3-030-10928-8_13

Markdown

[Pfahler and Morik. "Nyström-SGD: Fast Learning of Kernel-Classifiers with Conditioned Stochastic Gradient Descent." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2018.](https://mlanthology.org/ecmlpkdd/2018/pfahler2018ecmlpkdd-nystromsgd/) doi:10.1007/978-3-030-10928-8_13

BibTeX

@inproceedings{pfahler2018ecmlpkdd-nystromsgd,
  title     = {{Nyström-SGD: Fast Learning of Kernel-Classifiers with Conditioned Stochastic Gradient Descent}},
  author    = {Pfahler, Lukas and Morik, Katharina},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2018},
  pages     = {209-224},
  doi       = {10.1007/978-3-030-10928-8_13},
  url       = {https://mlanthology.org/ecmlpkdd/2018/pfahler2018ecmlpkdd-nystromsgd/}
}