Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning

By Francesco Orabona. 2014

106 citations recorded by the source corpus.

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 as well as preliminary empirical results.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Lacoste-Julien
2. Francis R. Bach
3. Alessandro Rudi
4. Lorenzo Rosasco
5. Peter Richtárik
6. Luigi Carratino
7. Francesco Orabona
8. Ashok Cutkosky

In Computational Mechanics

1. Simon Lacoste-Julien
2. Alessandro Rudi
3. Francis R. Bach
4. Peter Richtárik
5. Lorenzo Rosasco
6. Francesco Orabona
7. Warrren B Powell
8. Ashok Cutkosky

In Management Science and Operations Research

1. Warrren B Powell
2. Simon Lacoste-Julien
3. Ashok Cutkosky
4. Róbert Istvan Busa-Fekete
5. Alessandro Rudi
6. Lorenzo Rosasco
7. Luigi Carratino
8. Anton Osokin

In Optimization & Training

1. Simon Lacoste-Julien
2. Francesco Orabona
3. Francis R. Bach
4. Alessandro Rudi
5. Peter Richtárik
6. Lorenzo Rosasco
7. Warrren B Powell
8. Anton Osokin

Citations in the corpus

• On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, background): “Assumption 4 can be relaxed if the kernel K is universal, but then the convergence analysis becomes much more complicated [36].”
• Training Deep Networks without Learning Rates Through Coin Betting (2017, background): “ng have enough curvature to guarantee any gain. There exists a line of work on unconstrained stochastic gradient descent without learning rates [Streeter and McMahan, 2012, Orabona, 2013, McMahan and Orabona, 2014, Orabona, 2014, Cutkosky and Boahen, 2016, 2017]. The latest advancement in this direc”
• Distributed Stochastic Optimization via Adaptive SGD (2018, methodology): “This is an acceptable restriction because there are many examples of such algorithms, including AdaGrad [8], SOLO [15], PiSTOL [14] and FreeRex [6].”
• Learning with SGD and Random Features (2018, background): “Note that numerous works have combined stochastic gradient and kernel methods with no random projections approximation [32, 33, 34, 35, 36, 5].”
• A unified framework for stochastic optimization (2019, methodology): “Optimizing over policies means optimizing over the choice of stepsize rule (such as Kesten’s rule ( Kesten, 1958 ), BAKF ( Powell & George, 2006 ), AdaGrad ( Duchi et al., 2011 ), Adam ( Kingma & Ba, 2015 ), PiSTOL ( Orabona, 2014 ) and the parameters that characterize the rule (such as θ in Kesten’”