Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-Łojasiewicz condition
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910339923181568 |
|---|---|
| author | Choi, Hyung Jun Choi, Woocheol Seok, Jinmyoung |
| author_facet | Choi, Hyung Jun Choi, Woocheol Seok, Jinmyoung |
| contents | In this work, we establish the linear convergence estimate for the gradient descent involving the delay $τ\in\mathbb{N}$ when the cost function is $μ$-strongly convex and $L$-smooth. This result improves upon the well-known estimates in Arjevani et al. \cite{ASS} and Stich-Karmireddy \cite{SK} in the sense that it is non-ergodic and is still established in spite of weaker constraint of cost function. Also, the range of learning rate $η$ can be extended from $η\leq 1/(10Lτ)$ to $η\leq 1/(4Lτ)$ for $τ=1$ and $η\leq 3/(10Lτ)$ for $τ\geq 2$, where $L >0$ is the Lipschitz continuity constant of the gradient of cost function. In a further research, we show the linear convergence of cost function under the Polyak-Łojasiewicz\,(PL) condition, for which the available choice of learning rate is further improved as $η\leq 9/(10Lτ)$ for the large delay $τ$. The framework of the proof for this result is also extended to the stochastic gradient descent with time-varying delay under the PL condition. Finally, some numerical experiments are provided in order to confirm the reliability of the analyzed results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_11984 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-Łojasiewicz condition Choi, Hyung Jun Choi, Woocheol Seok, Jinmyoung Optimization and Control Distributed, Parallel, and Cluster Computing In this work, we establish the linear convergence estimate for the gradient descent involving the delay $τ\in\mathbb{N}$ when the cost function is $μ$-strongly convex and $L$-smooth. This result improves upon the well-known estimates in Arjevani et al. \cite{ASS} and Stich-Karmireddy \cite{SK} in the sense that it is non-ergodic and is still established in spite of weaker constraint of cost function. Also, the range of learning rate $η$ can be extended from $η\leq 1/(10Lτ)$ to $η\leq 1/(4Lτ)$ for $τ=1$ and $η\leq 3/(10Lτ)$ for $τ\geq 2$, where $L >0$ is the Lipschitz continuity constant of the gradient of cost function. In a further research, we show the linear convergence of cost function under the Polyak-Łojasiewicz\,(PL) condition, for which the available choice of learning rate is further improved as $η\leq 9/(10Lτ)$ for the large delay $τ$. The framework of the proof for this result is also extended to the stochastic gradient descent with time-varying delay under the PL condition. Finally, some numerical experiments are provided in order to confirm the reliability of the analyzed results. |
| title | Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-Łojasiewicz condition |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2308.11984 |