Home > Research > Publications & Outputs > Compact Convex Projections

Electronic data

  • 16-147

    Accepted author manuscript, 602 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

  • 16-147

    Final published version, 602 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

View graph of relations

Compact Convex Projections

Research output: Contribution to journalJournal articlepeer-review

Published
<mark>Journal publication date</mark>1/04/2018
<mark>Journal</mark>Journal of Machine Learning Research
Issue number219
Volume18
Number of pages43
Pages (from-to)1-43
Publication StatusPublished
Early online date6/02/18
<mark>Original language</mark>English

Abstract

We study the usefulness of conditional gradient like methods for determining projections onto convex sets, in particular, projections onto naturally arising convex sets in reproducing kernel Hilbert spaces. Our work is motivated by the recently introduced kernel herding algorithm which is closely related to the Conditional Gradient Method (CGM). It is known that the herding algorithm converges with a rate of 1=t, where t counts the number of iterations, when a point in the interior of a convex set is approximated. We generalize this result and we provide a necessary and sufficient condition for the algorithm to approximate projections with a rate of 1=t. The CGM, which is in general vastly superior to the herding algorithm, achieves only an inferior rate of 1=pt in this setting. We study the usefulness of such projection algorithms further by exploring ways to use these for solving concrete machine learning problems. In particular, we derive non-parametric regression algorithms which use at their core a slightly modified kernel herding algorithm to determine projections. We derive bounds to control approximation errors of these methods and we demonstrate via experiments that the developed regressors are en-par with state-of-the-art regression algorithms for large scale problems.