1. Stochastic Heavy Ball
- Author
-
Sébastien Gadat, Sofiane Saadane, Fabien Panloup, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire Angevin de Recherche en Mathématiques (LAREMA), Université d'Angers (UA)-Centre National de la Recherche Scientifique (CNRS), PANORisk, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire Angevin de REcherche en MAthématiques ( LAREMA ), and Université d'Angers ( UA ) -Centre National de la Recherche Scientifique ( CNRS )
- Subjects
Statistics and Probability ,FOS: Computer and information sciences ,Mathematical optimization ,Optimization problem ,Differential equation ,Machine Learning (stat.ML) ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,35H10 ,01 natural sciences ,Random dynamical systems ,010104 statistics & probability ,Statistics - Machine Learning ,FOS: Mathematics ,second-order methods ,Ball (mathematics) ,0101 mathematics ,Stochastic optimization algorithms ,B- ECONOMIE ET FINANCE ,Mathematics ,010102 general mathematics ,Probability (math.PR) ,Regular polygon ,random dynamical systems ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,Convergence of random variables ,60G15 ,Stochastic optimization ,Statistics, Probability and Uncertainty ,Convex function ,[ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR] ,60J70 ,Mathematics - Probability ,35P15 - Abstract
This paper deals with a natural stochastic optimization procedure derived from the so-called Heavy-ball method differential equation, which was introduced by Polyak in the 1960s with his seminal contribution [Pol64]. The Heavy-ball method is a second-order dynamics that was investigated to minimize convex functions f . The family of second-order methods recently received a large amount of attention, until the famous contribution of Nesterov [Nes83], leading to the explosion of large-scale optimization problems. This work provides an in-depth description of the stochastic heavy-ball method, which is an adaptation of the deterministic one when only unbiased evalutions of the gradient are available and used throughout the iterations of the algorithm. We first describe some almost sure convergence results in the case of general non-convex coercive functions f . We then examine the situation of convex and strongly convex potentials and derive some non-asymptotic results about the stochastic heavy-ball method. We end our study with limit theorems on several rescaled algorithms., 39 pages, 3 pages
- Published
- 2016