pipette
ENEnglish

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

Hao Wu, Chao Yin, Yuhong Dai, Liping Wang

Preprint

En palabras de los autores

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 and , we establish and 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 and last-local-iterate rates for PDSG in both problem classes, matching the optimal centralized dependence on . 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 25 pages, 2 figures