On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917582113603584 |
|---|---|
| author | Bai, Yunyan Liu, Yuxing Luo, Luo |
| author_facet | Bai, Yunyan Liu, Yuxing Luo, Luo |
| contents | This paper considers the optimization problem of the form $\min_{{\bf x}\in{\mathbb R}^d} f({\bf x})\triangleq \frac{1}{n}\sum_{i=1}^n f_i({\bf x})$, where $f(\cdot)$ satisfies the Polyak--Łojasiewicz (PL) condition with parameter $μ$ and $\{f_i(\cdot)\}_{i=1}^n$ is $L$-mean-squared smooth. We show that any gradient method requires at least $Ω(n+κ\sqrt{n}\log(1/ε))$ incremental first-order oracle (IFO) calls to find an $ε$-suboptimal solution, where $κ\triangleq L/μ$ is the condition number of the problem. This result nearly matches upper bounds of IFO complexity for best-known first-order methods. We also study the problem of minimizing the PL function in the distributed setting such that the individuals $f_1(\cdot),\dots,f_n(\cdot)$ are located on a connected network of $n$ agents. We provide lower bounds of $Ω(κ/\sqrtγ\,\log(1/ε))$, $Ω((κ+τκ/\sqrtγ\,)\log(1/ε))$ and $Ω\big(n+κ\sqrt{n}\log(1/ε)\big)$ for communication rounds, time cost and local first-order oracle calls respectively, where $γ\in(0,1]$ is the spectral gap of the mixing matrix associated with the network and~$τ>0$ is the time cost of per communication round. Furthermore, we propose a decentralized first-order method that nearly matches above lower bounds in expectation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02569 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition Bai, Yunyan Liu, Yuxing Luo, Luo Optimization and Control Machine Learning This paper considers the optimization problem of the form $\min_{{\bf x}\in{\mathbb R}^d} f({\bf x})\triangleq \frac{1}{n}\sum_{i=1}^n f_i({\bf x})$, where $f(\cdot)$ satisfies the Polyak--Łojasiewicz (PL) condition with parameter $μ$ and $\{f_i(\cdot)\}_{i=1}^n$ is $L$-mean-squared smooth. We show that any gradient method requires at least $Ω(n+κ\sqrt{n}\log(1/ε))$ incremental first-order oracle (IFO) calls to find an $ε$-suboptimal solution, where $κ\triangleq L/μ$ is the condition number of the problem. This result nearly matches upper bounds of IFO complexity for best-known first-order methods. We also study the problem of minimizing the PL function in the distributed setting such that the individuals $f_1(\cdot),\dots,f_n(\cdot)$ are located on a connected network of $n$ agents. We provide lower bounds of $Ω(κ/\sqrtγ\,\log(1/ε))$, $Ω((κ+τκ/\sqrtγ\,)\log(1/ε))$ and $Ω\big(n+κ\sqrt{n}\log(1/ε)\big)$ for communication rounds, time cost and local first-order oracle calls respectively, where $γ\in(0,1]$ is the spectral gap of the mixing matrix associated with the network and~$τ>0$ is the time cost of per communication round. Furthermore, we propose a decentralized first-order method that nearly matches above lower bounds in expectation. |
| title | On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2402.02569 |