Generalization Properties of Doubly Stochastic Learning Algorithms
arXiv:1707.00577 · doi:10.1016/j.jco.2018.02.004
Abstract
Doubly stochastic learning algorithms are scalable kernel methods that perform very well in practice. However, their generalization properties are not well understood and their analysis is challenging since the corresponding learning sequence may not be in the hypothesis space induced by the kernel. In this paper, we provide an in-depth theoretical analysis for different variants of doubly stochastic learning algorithms within the setting of nonparametric regression in a reproducing kernel Hilbert space and considering the square loss. Particularly, we derive convergence results on the generalization error for the studied algorithms either with or without an explicit penalty term. To the best of our knowledge, the derived results for the unregularized variants are the first of this kind, while the results for the regularized variants improve those in the literature. The novelties in our proof are a sample error bound that requires controlling the trace norm of a cumulative operator, and a refined analysis of bounding initial error.
24 pages. To appear in Journal of Complexity
References in corpus (4)
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Better Mini-Batch Algorithms via Accelerated Gradient Methods
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression