AI summaryⓘ
The authors study how to optimize decisions across a network when data keeps coming in over time and the goal changes as new information arrives. They focus on decentralized methods where no single node controls all data, analyzing how well these methods track the evolving optimal solution. Their work breaks down the errors into parts caused by the time-varying nature and parts caused by decentralization and differences in local data. They provide mathematical guarantees for different ways of weighting past data, showing how these choices affect the error and how changing parameters like step size and communication affect performance. Finally, they support their findings with experiments that reflect their theoretical predictions.
Decentralized optimizationStreaming dataTime-varying objectiveGradient descentStrongly convexSmooth lossesTracking errorStep sizeNetwork connectivityTemporal weighting
Abstract
Optimization theory is a widely used tool for intelligent decision-making. While classical optimization deals with fixed, time-invariant objective functions, many modern applications operate in dynamic environments where data arrive sequentially, and the learning objective evolves over time, often under decentralized data and communication constraints. Motivated by these trends, we study decentralized optimization from streaming data through a structured time-varying formulation in which the global objective is a temporally weighted average of losses observed across the network. We analyze multi-iteration decentralized first-order methods, including decentralized gradient descent. For strongly convex and smooth losses, we develop guarantees for the Euclidean-norm \emph{tracking error} through a contraction-mapping viewpoint. The resulting bounds decompose the tracking error into a fixed-point tracking component and a bias term induced by decentralization and data heterogeneity. We specialize our analysis to uniform and exponentially discounted weights, as well as their finite-memory \emph{windowed} counterparts. The bounds explicitly characterize the roles of the temporal weighting rule, per-step iteration budget, step size, and network connectivity. Uniform weighting yields a vanishing fixed-point tracking contribution of order $\mathcal O(1/t)$, whereas discounted and windowed strategies generally induce non-vanishing tracking floors governed by the discount factor and effective memory, respectively. In all cases, decentralization induces an additional non-zero bias floor under a constant step size. Numerical experiments illustrate the predicted trends.