  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: Prox-DASA and 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 https://github.com/xuxingc/ProxDASA.
