Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning

Abstract

Stochastic gradient descent algorithms for training linear and kernel predictors are gaining more and more importance, thanks to their scalability. While various methods have been proposed to speed up their convergence, the model selection phase is often ignored. In fact, in theoretical works most of the time assumptions are made, for example, on the prior knowledge of the norm of the optimal solution, while in the practical world validation methods remain the only viable approach. In this paper, we propose a new kernel-based stochastic gradient descent algorithm that performs model selection while training, with no parameters to tune, nor any form of cross-validation. The algorithm builds on recent advancement in online learning theory for unconstrained settings, to estimate over time the right regularization in a data-dependent way. Optimal rates of convergence are proved under standard smoothness assumptions on the target function, using the range space of the fractional integral operator associated with the kernel.

References in corpus (7)

• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Statistical performance of support vector machines
• Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
• No-Regret Algorithms for Unconstrained Online Convex Optimization
• Less Regret via Online Conditioning
• A Drifting-Games Analysis for Online Learning and Applications to Boosting
• Online Learning as Stochastic Approximation of Regularization Paths

Cited by in corpus (18)

• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• Model selection for contextual bandits
• A Drifting-Games Analysis for Online Learning and Applications to Boosting
• MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
• Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
• Differentially Private SGD with Non-Smooth Losses
• Stochastic Proximal AUC Maximization
• Combining Online Learning Guarantees
• Matrix-Free Preconditioning in Online Learning
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
• Pareto Optimal Model Selection in Linear Bandits
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits
• Artificial Constraints and Lipschitz Hints for Unconstrained Online Learning
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• Online Linear Optimization with Many Hints
• Variance Reduced Stochastic Proximal Algorithm for AUC Maximization
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning
• Adaptive Online Learning with Varying Norms