Search papers, labs, and topics across Lattice.
This paper investigates decentralized optimization in dynamic environments where data arrives sequentially, focusing on a structured time-varying formulation that utilizes temporally weighted averages of losses. The authors analyze multi-iteration decentralized first-order methods, specifically decentralized gradient descent, and establish guarantees for tracking error through a contraction-mapping approach. Key findings reveal that uniform weighting leads to a diminishing tracking error over time, while discounted and windowed strategies introduce persistent bias floors influenced by the discount factor and memory effects, with empirical results supporting these theoretical insights.
Uniform weighting in decentralized optimization can yield a vanishing tracking error, but discounted strategies may trap you in a persistent bias floor.
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.
