A one-sample decentralized proximal algorithm for non-convex stochastic composite optimization

Tesi Xiao, Xuxing Chen, Krishnakumar Balasubramanian, Saeed Ghadimi
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:2324-2334, 2023.

Abstract

We focus on decentralized stochastic non-convex optimization, where $n$ agents work together to optimize a composite objective function which is a sum of a smooth term and a non-smooth convex term. To solve this problem, we propose two single-time scale algorithms: \texttt{Prox-DASA} and \texttt{Prox-DASA-GT}. These algorithms can find $\epsilon$-stationary points in $\mathcal{O}(n^{-1}\epsilon^{-2})$ iterations using constant batch sizes (i.e., $\mathcal{O}(1)$). Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-iteration operations (such as double loops), or stronger assumptions. Our theoretical findings are supported by extensive numerical experiments, which demonstrate the superiority of our algorithms over previous approaches. Our code is available at \url{https://github.com/xuxingc/ProxDASA}.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-xiao23a, title = {A one-sample decentralized proximal algorithm for non-convex stochastic composite optimization}, author = {Xiao, Tesi and Chen, Xuxing and Balasubramanian, Krishnakumar and Ghadimi, Saeed}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {2324--2334}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/xiao23a/xiao23a.pdf}, url = {https://proceedings.mlr.press/v216/xiao23a.html}, abstract = {We focus on decentralized stochastic non-convex optimization, where $n$ agents work together to optimize a composite objective function which is a sum of a smooth term and a non-smooth convex term. To solve this problem, we propose two single-time scale algorithms: \texttt{Prox-DASA} and \texttt{Prox-DASA-GT}. These algorithms can find $\epsilon$-stationary points in $\mathcal{O}(n^{-1}\epsilon^{-2})$ iterations using constant batch sizes (i.e., $\mathcal{O}(1)$). Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-iteration operations (such as double loops), or stronger assumptions. Our theoretical findings are supported by extensive numerical experiments, which demonstrate the superiority of our algorithms over previous approaches. Our code is available at \url{https://github.com/xuxingc/ProxDASA}.} }
Endnote
%0 Conference Paper %T A one-sample decentralized proximal algorithm for non-convex stochastic composite optimization %A Tesi Xiao %A Xuxing Chen %A Krishnakumar Balasubramanian %A Saeed Ghadimi %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-xiao23a %I PMLR %P 2324--2334 %U https://proceedings.mlr.press/v216/xiao23a.html %V 216 %X We focus on decentralized stochastic non-convex optimization, where $n$ agents work together to optimize a composite objective function which is a sum of a smooth term and a non-smooth convex term. To solve this problem, we propose two single-time scale algorithms: \texttt{Prox-DASA} and \texttt{Prox-DASA-GT}. These algorithms can find $\epsilon$-stationary points in $\mathcal{O}(n^{-1}\epsilon^{-2})$ iterations using constant batch sizes (i.e., $\mathcal{O}(1)$). Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-iteration operations (such as double loops), or stronger assumptions. Our theoretical findings are supported by extensive numerical experiments, which demonstrate the superiority of our algorithms over previous approaches. Our code is available at \url{https://github.com/xuxingc/ProxDASA}.
APA
Xiao, T., Chen, X., Balasubramanian, K. & Ghadimi, S.. (2023). A one-sample decentralized proximal algorithm for non-convex stochastic composite optimization. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:2324-2334 Available from https://proceedings.mlr.press/v216/xiao23a.html.

Related Material