Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915257397542912 |
|---|---|
| author | Tadipatri, Uday Kiran Reddy Vidyasagar, Mathukumalli |
| author_facet | Tadipatri, Uday Kiran Reddy Vidyasagar, Mathukumalli |
| contents | In this paper, we establish the convergence of the stochastic Heavy Ball (SHB) algorithm under more general conditions than in the current literature. Specifically, (i) The stochastic gradient is permitted to be biased, and also, to have conditional variance that grows over time (or iteration number). This feature is essential when applying SHB with zeroth-order methods, which use only two function evaluations to approximate the gradient. In contrast, all existing papers assume that the stochastic gradient is unbiased and/or has bounded conditional variance. (ii) The step sizes are permitted to be random, which is essential when applying SHB with block updating. The sufficient conditions for convergence are stochastic analogs of the well-known Robbins-Monro conditions. This is in contrast to existing papers where more restrictive conditions are imposed on the step size sequence. (iii) Our analysis embraces not only convex functions, but also more general functions that satisfy the PL (Polyak-Łojasiewicz) and KL (Kurdyka-Łojasiewicz) conditions. (iv) If the stochastic gradient is unbiased and has bounded variance, and the objective function satisfies (PL), then the iterations of SHB match the known best rates for convex functions. (v) We establish the almost-sure convergence of the iterations, as opposed to convergence in the mean or convergence in probability, which is the case in much of the literature. (vi) Each of the above convergence results continue to hold if full-coordinate updating is replaced by any one of three widely-used updating methods. In addition, numerical computations are carried out to illustrate the above points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_16241 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating Tadipatri, Uday Kiran Reddy Vidyasagar, Mathukumalli Optimization and Control Machine Learning 68Q25, 68R10, 68U05 In this paper, we establish the convergence of the stochastic Heavy Ball (SHB) algorithm under more general conditions than in the current literature. Specifically, (i) The stochastic gradient is permitted to be biased, and also, to have conditional variance that grows over time (or iteration number). This feature is essential when applying SHB with zeroth-order methods, which use only two function evaluations to approximate the gradient. In contrast, all existing papers assume that the stochastic gradient is unbiased and/or has bounded conditional variance. (ii) The step sizes are permitted to be random, which is essential when applying SHB with block updating. The sufficient conditions for convergence are stochastic analogs of the well-known Robbins-Monro conditions. This is in contrast to existing papers where more restrictive conditions are imposed on the step size sequence. (iii) Our analysis embraces not only convex functions, but also more general functions that satisfy the PL (Polyak-Łojasiewicz) and KL (Kurdyka-Łojasiewicz) conditions. (iv) If the stochastic gradient is unbiased and has bounded variance, and the objective function satisfies (PL), then the iterations of SHB match the known best rates for convex functions. (v) We establish the almost-sure convergence of the iterations, as opposed to convergence in the mean or convergence in probability, which is the case in much of the literature. (vi) Each of the above convergence results continue to hold if full-coordinate updating is replaced by any one of three widely-used updating methods. In addition, numerical computations are carried out to illustrate the above points. |
| title | Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating |
| topic | Optimization and Control Machine Learning 68Q25, 68R10, 68U05 |
| url | https://arxiv.org/abs/2303.16241 |