Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the Effectiveness of Richardson Extrapolation in Machine Learning

Francis Bach 1, 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : Richardson extrapolation is a classical technique from numerical analysis that can improve the approximation error of an estimation method by combining linearly several estimates obtained from different values of one of its hyperparameters, without the need to know in details the inner structure of the original estimation method. The main goal of this paper is to study when Richardson extrapolation can be used within machine learning, beyond the existing applications to step-size adaptations in stochastic gradient descent. We identify two situations where Richardson interpolation can be useful: (1) when the hyperparameter is the number of iterations of an existing iterative optimization algorithm, with applications to averaged gradient descent and Frank-Wolfe algorithms (where we obtain asymptotically rates of $O(1/k^2)$ on polytopes, where $k$ is the number of iterations), and (2) when it is a regularization parameter, with applications to Nesterov smoothing techniques for minimizing non-smooth functions (where we obtain asymptotically rates close to $O(1/k^2)$ for non-smooth functions), and ridge regression. In all these cases, we show that extrapolation techniques come with no significant loss in performance, but with sometimes strong gains, and we provide theoretical justifications based on asymptotic developments for such gains, as well as empirical illustrations on classical problems from machine learning.
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02470950
Contributor : Francis Bach <>
Submitted on : Thursday, July 9, 2020 - 4:08:12 PM
Last modification on : Tuesday, January 5, 2021 - 9:53:02 AM

Files

richardson_hal_v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02470950, version 2
  • ARXIV : 2002.02835

Collections

Citation

Francis Bach. On the Effectiveness of Richardson Extrapolation in Machine Learning. 2020. ⟨hal-02470950v2⟩

Share

Metrics

Record views

5977

Files downloads

132