Optimal last-iterate rates for the projected decentralized stochastic subgradient method

We study the projected decentralized stochastic subgradient (PDSG) method for minimizing the average of convex, possibly nonsmooth local objectives over a common closed convex constraint set and a fixed connected undirected network. We focus on the finite-time expected suboptimality of the last local iterate generated at each node, which is the actual output locally available without time averaging or network averaging. Under the standard stepsizes αₜ=α/√t and αₜ=2/(μt), we establish O(log T/√T) and O(log T/T) last-local-iterate rates for PDSG when each local objective is convex and the aggregate objective is strongly convex, respectively. To eliminate the logarithmic loss, we introduce a general horizon-dependent stepsize framework, termed cooldown stepsize, that combines a base stepsize with segmentwise scaling over a multistage partition and includes the dyadic construction (Jain et al, SIAM J. Optim., 2021) as a special case. For adapting to decentralized settings, we propose a long-range variation condition to make the stepsize schedule compatible with network contraction. Under this cooldown stepsize, we obtain O(1/√T) and O(1/T) last-local-iterate rates for PDSG in both problem classes, matching the optimal centralized dependence on T. Experiments on a lower-bound instance and constrained hinge-loss problems illustrate the predicted terminal behavior of local iterates and the control of consensus error under the cooldown stepsize.