Analysis of Decentralized Stochastic Successive Convex Approximation for composite non-convex problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929360720625664 |
|---|---|
| author | Idrees, Basil M. Sharma, Shivangi Dubey Rajawat, Ketan |
| author_facet | Idrees, Basil M. Sharma, Shivangi Dubey Rajawat, Ketan |
| contents | This work considers the decentralized successive convex approximation (SCA) method for minimizing stochastic non-convex objectives subject to convex constraints, along with possibly non-smooth convex regularizers. Although SCA has been widely applied in decentralized settings, its stochastic first order (SFO) complexity is unknown, and it is thought to be slower than the centralized momentum-enhanced SCA variants. In this work, we advance the state-of-the-art for SCA methods by proposing an accelerated variant, namely the \textbf{D}ecentralized \textbf{M}omentum-based \textbf{S}tochastic \textbf{SCA} (\textbf{D-MSSCA}) and analyze its SFO complexity. The proposed algorithm entails creating a stochastic surrogate of the objective at every iteration, which is minimized at each node separately. Remarkably, the D-MSSCA achieves an SFO complexity of $\mathcal{O}(ε^{-3/2})$ to reach an $ε$-stationary point, which is at par with the SFO complexity lower bound for unconstrained stochastic non-convex optimization in centralized setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07100 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analysis of Decentralized Stochastic Successive Convex Approximation for composite non-convex problems Idrees, Basil M. Sharma, Shivangi Dubey Rajawat, Ketan Optimization and Control Signal Processing This work considers the decentralized successive convex approximation (SCA) method for minimizing stochastic non-convex objectives subject to convex constraints, along with possibly non-smooth convex regularizers. Although SCA has been widely applied in decentralized settings, its stochastic first order (SFO) complexity is unknown, and it is thought to be slower than the centralized momentum-enhanced SCA variants. In this work, we advance the state-of-the-art for SCA methods by proposing an accelerated variant, namely the \textbf{D}ecentralized \textbf{M}omentum-based \textbf{S}tochastic \textbf{SCA} (\textbf{D-MSSCA}) and analyze its SFO complexity. The proposed algorithm entails creating a stochastic surrogate of the objective at every iteration, which is minimized at each node separately. Remarkably, the D-MSSCA achieves an SFO complexity of $\mathcal{O}(ε^{-3/2})$ to reach an $ε$-stationary point, which is at par with the SFO complexity lower bound for unconstrained stochastic non-convex optimization in centralized setting. |
| title | Analysis of Decentralized Stochastic Successive Convex Approximation for composite non-convex problems |
| topic | Optimization and Control Signal Processing |
| url | https://arxiv.org/abs/2405.07100 |