Decentralized Nonconvex Nonsmooth Optimization with Client-Data Sampling

This paper studies decentralized online non-convex optimization (D-ONO), where a network of agents collaboratively minimizes a sequence of non-convex global loss functions through local computation and communication. Existing approaches either rely on an offline optimization oracle, which may require computational cost, or analyze window-averaged local regret based on local objectives, which does not accurately characterize the performance of individual agents. How to solve D-ONO under the standard notion of local regret, without requiring computations beyond gradient evaluations, remains largely unexplored. We propose Accelerated Decentralized Gradient Tracking (ADGT), which integrates gradient tracking into a block-wise online accelerated gossip scheme. Under both exact and stochastic gradient oracle feedback, we establish nearly optimal upper bounds on individual local regret and provide matching lower bounds. Extensive experiments on both synthetic and real-world datasets corroborate our theoretical findings and demonstrate the effectiveness of the proposed algorithm.