We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, we promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical-computational tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.

Carratino, L., Vigogna, S., Calandriello, D., Rosasco, L. (2021). ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (pp.6430-6441). Neural Information Processing Systems Foundation.

ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions

Vigogna S.;
2021-01-01

Abstract

We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, we promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical-computational tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.
Advances in Neural Information Processing Systems 34
2021
Rilevanza internazionale
2021
Settore MAT/06 - PROBABILITA' E STATISTICA MATEMATICA
English
Intervento a convegno
Carratino, L., Vigogna, S., Calandriello, D., Rosasco, L. (2021). ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (pp.6430-6441). Neural Information Processing Systems Foundation.
Carratino, L; Vigogna, S; Calandriello, D; Rosasco, L
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/361043
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact