Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces

Volkan Cevher, Junhong Lin
ICML, 2018
Article de conférence

We investigate regularized algorithms combining with projection for least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nystr"{o}m regularized algorithms. Our results are the first ones with optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nystr"{o}m regularized algorithms, considering both the attainable and non-attainable cases.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Volkan Cevher, Junhong Lin
ICML, 2018
Article de conférence

Résumé

Official source

https://infoscience.epfl.ch/record/253495?ln=fr

À propos de ce résultat

Concepts associés (11)

Concepts associés

Chargement

Publications associées (3)

Publications associées

Chargement

Convergences of Regularized Algorithms and Stochastic Gradient Methods with Random Projections

Volkan Cevher, Junhong Lin

We study the least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space as a special case. We rst investigate regularized algorithms adapted to a projection operator on a closed subspace of the Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nyström regularized algorithms. Our results provide optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nyström regularized algorithms, considering both the attainable and non-attainable cases, in the wellconditioned regimes. We then study stochastic gradient methods with projection over the subspace, allowing multi-pass over the data and minibatches, and we derive similar optimal statistical convergence results.

2020

Chargement

Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Volkan Cevher, Junhong Lin

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes over the data. We show that optimal generalization error bounds (up to a logarithmic factor) can be retained for distributed SGM provided that the partition level is not too large. We then extend our results to spectral algorithms (SA), including kernel ridge regression (KRR), kernel principal component analysis, and gradient methods. Our results are superior to the state-of-the-art theory. Particularly, our results show that distributed SGM has a smaller theoretical computational complexity, compared with distributed KRR and classic SGM. Moreover, even for non-distributed SA, they provide the first optimal, capacity-dependent convergence rates, for the case that the regression function may not be in the RKHS.

2018

Chargement

Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces

Volkan Cevher, Junhong Lin

In this paper, we study regression problems over a separable Hilbert space with the square loss, covering non-parametric regression over a reproducing kernel Hilbert space. We investigate a class of spectral/regularized algorithms, including ridge regression, principal component regression, and gradient methods. We prove optimal, high-probability convergence results in terms of variants of norms for the studied algorithms, considering a capacity assumption on the hypothesis space and a general source condition on the target function. Consequently, we obtain almost sure convergence results with optimal rates. Our results improve and generalize previous results, filling a theoretical gap for the non-attainable cases.

2018

Chargement

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de

Espace de Hilbert

vignette|Une photographie de David Hilbert (1862 - 1943) qui a donné son nom aux espaces dont il est question dans cet article. En mathématiques, un espace de Hilbert est un espace vectoriel réel (re

Espace de Hilbert à noyau reproduisant

En analyse fonctionnelle, un espace de Hilbert à noyau reproduisant est un espace de Hilbert de fonctions pour lequel toutes les applications f \mapsto f(x) sont des formes linéaires co