Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Łojasiewicz Condition
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910525293592576 |
|---|---|
| author | Kim, Seunghyun Madden, Liam Dall'Anese, Emiliano |
| author_facet | Kim, Seunghyun Madden, Liam Dall'Anese, Emiliano |
| contents | This paper focuses on the online gradient and proximal-gradient methods with stochastic gradient errors. In particular, we examine the performance of the online gradient descent method when the cost satisfies the Polyak-Łojasiewicz (PL) inequality. We provide bounds in expectation and in high probability (that hold iteration-wise), with the latter derived by leveraging a sub-Weibull model for the errors affecting the gradient. The convergence results show that the instantaneous regret converges linearly up to an error that depends on the variability of the problem and the statistics of the sub-Weibull gradient error. Similar convergence results are then provided for the online proximal-gradient method, under the assumption that the composite cost satisfies the proximal-PL condition. In the case of static costs, we provide new bounds for the regret incurred by these methods when the gradient errors are modeled as sub-Weibull random variables. Illustrative simulations are provided to corroborate the technical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_03285 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Łojasiewicz Condition Kim, Seunghyun Madden, Liam Dall'Anese, Emiliano Optimization and Control Systems and Control This paper focuses on the online gradient and proximal-gradient methods with stochastic gradient errors. In particular, we examine the performance of the online gradient descent method when the cost satisfies the Polyak-Łojasiewicz (PL) inequality. We provide bounds in expectation and in high probability (that hold iteration-wise), with the latter derived by leveraging a sub-Weibull model for the errors affecting the gradient. The convergence results show that the instantaneous regret converges linearly up to an error that depends on the variability of the problem and the statistics of the sub-Weibull gradient error. Similar convergence results are then provided for the online proximal-gradient method, under the assumption that the composite cost satisfies the proximal-PL condition. In the case of static costs, we provide new bounds for the regret incurred by these methods when the gradient errors are modeled as sub-Weibull random variables. Illustrative simulations are provided to corroborate the technical findings. |
| title | Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Łojasiewicz Condition |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2108.03285 |