Accumulations of Projections—A Unified Framework for Random Sketches in Kernel Ridge Regression

Apr 14, 2021

Sprecher:innen

Über

Building a sketch of the $n$-by-$n$ empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. In this paper we propose a unified framework to understand sketching methods in kernel ridge regression (KRR), which considers the sketching matrix $S$ as the accumulation of $m$ rescaled sub-sampling matrices with independent columns. Two types of random sketches, sub-sampling sketches (known as the Nystr\"{o}m method) and sub-Gaussian sketches, could thus be (approximately) taken as two special cases in the framework, with $m=1$ and $m=\infty$ respectively. Under the new framework we provide an error analysis of KRR and show how the accumulation would conduce to the reduction of the approximation error, especially when there is high incoherence in the KRR problem. The theoretical analysis suggests that tuning the parameter $m$ could be taken as a new method to improve the trade-off between computational efficiency and statistical accuracy. In practice, the sketching method induced by our framework can be efficiently implemented, as only some extra matrix addition is needed. The empirical evaluations also demonstrate that the proposed method could attain the accuracy close to sub-Gaussian sketches, while still be as efficient as sub-sampling sketches.

Organisator

Kategorien

Über AISTATS 2021

The 24th International Conference on Artificial Intelligence and Statistics was held virtually from Tuesday, 13 April 2021 to Thursday, 15 April 2021.

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? AISTATS 2021 folgen