Decentralized Stochastic Successive Convex Approximation for composite non-convex problems with non-linear functional constraints

Abstract

This paper explores consensus-based decentralized stochastic optimization for minimizing stochastic non-convex objectives, potentially accompanied by non-smooth convex regularizers and subject to non-linear functional constraints. The original problem is reformulated using the exact penalty method. Our proposed approach relies on successive convex approximation (SCA), specifically the Decentralized Momentum-based Linear Stochastic SCA (D-MLSSCA), to solve this equivalent problem. The algorithm iteratively solves a strongly convex subproblem at each node with linearized constraints. Recursive momentum-based local gradient updates are leveraged to accelerate the convergence. Despite solving a simpler subproblem, we achieve a stochastic first-order (SFO) complexity of ${\mathcal{O}}\left({{ \in ^{ - 3/2}}}\right)$ to reach an ϵ-stationary point. Notably, this SFO complexity matches the lower bound for unconstrained stochastic non-convex optimization in the centralized setting.