Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

This paper studies decentralized optimization from streaming data, where data arrive sequentially over time and the learning objective evolves dynamically. The authors motivate this by noting that many modern AI applications—such as autonomous vehicles, robotics, telecommunications, power grids, and cyber-physical systems—operate in environments that are both dynamic and decentralized: data arrive sequentially over time, while storage, computation, and communication are distributed across multiple agents due to scale, privacy, or architectural constraints.

The central question addressed is: Can the streaming-data structure be explicitly incorporated into the optimization model to obtain sharper and more interpretable tracking guarantees? Unlike prior work in time-varying optimization that treats objective evolution as generic and unstructured, this paper explicitly models the objective evolution as arising from streaming data acquisition.

The paper considers a network of N agents collaborating on a time-varying optimization problem. At each time step t, agent n observes a new data sample and incurs an instantaneous loss ln,t(w) evaluated at model parameter w ∈ R d. The network-wide instantaneous loss is defined as:

F t(w) = (1/N) Σ n=1 N ln,t(w)

The time-t objective is a temporally weighted average of past network-wide losses:

F̄ t(w) = Σ i=1 t a i(t) F i(w)

where a i(t) i=1 t is a nonnegative temporal weighting strategy satisfying a i(t) ∈ [0,1] and Σ i=1 t a i(t) = 1 for all t ≥ 1.

The agents communicate over an undirected, connected, time-invariant graph described by a symmetric mixing matrix M ∈ R N×N satisfying M = M T and M1 N = 1 N, with eigenvalues ordered as 1 = λ 1 > λ 2 ≥... ≥ λ N > -1.

The paper introduces two structured families of temporal weights:

1. Stationary kernel-induced temporal weights: Given a nonnegative kernel sequence g k k≥0 with g 0 > 0, weights are defined as a i(t) = g t-i/S t where S t = Σ k=0 t-1 g k. Special cases include:

• Uniform weights: g k = 1 for all k, giving a i(t) = 1/t

• Exponentially discounted weights: g k = γ k with γ ∈ (0,1), giving a i(t) = (1-γ)γ t-i/(1-γ t)

• Windowed-uniform weights: g k = 1 0 ≤ k ≤ m-1, giving equal weight 1/m only to the most recent m samples

• Windowed-discounted weights: g k = γ k 1 0 ≤ k ≤ m-1, giving a finite-memory approximation of exponential discounting

2. Uniform-shrinkage weighting: Weights are generated recursively via F̄ t+1(w) = (1-β t+1)F̄ t(w) + β t+1F t+1(w), yielding a i(t) = β i Π k=i+1 t (1-β k). This recovers uniform weighting with β t+1 = 1/(t+1) and exponential discounting with β t+1 = (1-γ)/(1-γ t+1).

The paper analyzes two decentralized first-order methods:

• Decentralized gradient descent (DGD): w n,t(k+1) = Σ m=1 N [M] n,m w m,t(k) - η Σ i=1 t+1 a i(t+1)∇l n,i (w n,t(k))

• Adapt-then-combine (ATC) diffusion: performs adaptation first, then combination

Both can be expressed in unified form: w t(k+1) = M w t(k) - ηZ∇f̄ t+1(w t(k)), where Z = I for DGD and Z = M for diffusion. Each time step allows E ≥ 1 decentralized iterations before new samples arrive.

The tracking error is defined as TE(t) = w t - w* t = w t - 1 N ⊗ w* t, with asymptotic tracking error ATE = lim sup t→∞ w t - w* t.

Assumption 1: Each loss ln,t(·) is L-smooth and µ-strongly convex, with κ = L/µ denoting the condition number.

Assumption 2: For each agent n and time t, the sample-wise minimizer w* n,t satisfies w* n,t ≤ C for some C > 0.

The update operator ϕ t(w) = Mw - ηZ∇f̄ t(w) is shown to be a contraction with factor (1-ηµ) under step size conditions: 0 < η ≤ (1+λ N)/(L+µ) for DGD and 0 < η ≤ 2/(L+µ) for diffusion. The E-fold composition Φ t has contraction factor α = (1-ηµ) E ∈ (0,1).

The tracking error decomposes as:

TE(t) ≤ w t - w̃ t + w̃ t - w* t = FPTE(t) + FP bias

where w̃ t is the unique fixed point of ϕ t(·), FPTE(t) is the fixed-point tracking error, and the second term is the fixed-point bias.

The bias is bounded as: w̃ t - w* t ≤ ηκΛ Z ∇f̄ t(w* t) ≤ ηκΛ Z G Z, where Λ Z = (I-M)† 2 = 1/(1-λ 2) for DGD and Λ Z = 2(I-M)†M 2 for diffusion, and G Z = 2L√(N)C Z with C Z depending on the algorithm (C√κ for DGD, Cκ for diffusion, C√κ for diffusion with M ⪰ 0).

The drift of the fixed-point sequence satisfies: w̃ t+1 - w̃ t ≤ (2G Z/µ)(a t+1(t+1) + I t), where I t = Σ i=1 t (a i(t+1) - a i(t))+. For non-increasing weights, this simplifies to w̃ t+1 - w̃ t ≤ (2G Z/µ)a t+1(t+1).

Uniform weights (Theorem 1): TE(t) ≤ α tw 0 - w̃ 1 + (2G Z A)/(µt) + ηκΛ Z G Z for all t ≥ t 0 = ⌈2α/(1-α)⌉, where A = max t 0 S(t 0), 2α/(1-α). The ATE satisfies: ATE ≤ ηκΛ Z G Z. The FPTE contribution vanishes as O(1/t), leaving only the bias floor. To guarantee ATE ≤ ε, it suffices to choose η ≤ ε/(κΛ Z G Z).

Exponentially discounted weights (Theorem 2): TE(t) ≤ α tw 0 - w̃ 1 + (2G Z/µ)A γ(1-γ)/(1-γ t) + ηκΛ Z G Z, with ATE ≤ (2G Z(1-γ)α)/(µ(1-α)) + ηκΛ Z G Z. Unlike uniform weighting, discounted weighting induces a non-vanishing FPTE contribution proportional to (1-γ). As γ → 1, this floor vanishes and approaches uniform weighting.

Windowed-discounted weights (Theorem 3): ATE ≤ (2G Z(1-γ)α)/(µ(1-γ m)(1-α)) + ηκΛ Z G Z. The FPTE contribution is controlled by the effective-memory factor (1-γ)/(1-γ m), which approaches 1-γ as m → ∞.

Windowed-uniform weights (Corollary 1): ATE ≤ (2G Z α)/(µm(1-α)) + ηκΛ Z G Z, with a 1/m prefactor on the FPTE contribution.

For uniform weighting, ATE can be made arbitrarily small by reducing η. For discounted and windowed strategies, the ATE has a non-vanishing FPTE floor. The sufficient per-step iteration budgets scale as Θ(ln(1/ε)/ε) when η = Θ(ε).

The paper validates the theory using quadratic losses l n,t(w) = (1/2)(w - c n,t) T A n,t(w - c n,t) with A n,t = diag(λ 1 n,t,..., λ d n,t) where λ j n,t Unif[µ, L]. The temporal evolution uses a bounded Gaussian random walk. Experiments use N = 50 agents, d = 100 dimensions, η = 0.1, C max = 10, σ2 = 1, µ = 0.01, L = 0.1, T = 1000 time steps, with Metropolis-Hastings mixing matrices on random geometric graphs.

Key findings:

• Under uniform weighting, increasing E accelerates transient decay, and TE decreases steadily toward the bias-dominated regime

• Under discounted weighting with γ = 0.7, TE settles at a substantially larger steady-state level due to non-vanishing fixed-point drift

• Smaller γ leads to larger asymptotic TE; as γ → 1, curves approach uniform weighting

• For windowed-uniform weights, increasing window length m lowers the TE floor with 1/m dependence

• For windowed-discounted weights, moderate window lengths (m > 5) nearly match full-memory discounted performance due to exponential forgetting

The paper develops a unified tracking error analysis for decentralized gradient descent and diffusion methods in streaming-data settings with temporally weighted objectives. The bounds decompose the tracking error into a fixed-point tracking component and a network-induced bias term, explicitly characterizing the roles of temporal weighting rule, per-step iteration budget, step size, and network connectivity. Uniform weighting yields vanishing FPTE of order O(1/t), while discounted and windowed strategies exhibit non-vanishing floors governed by the discount factor and window length, respectively.

Improvements to AI Systems:

1. Adaptive Temporal Weighting for Non-Stationary Environments: AI systems can dynamically switch between uniform, discounted, or windowed weighting strategies based on detected drift rates. For slowly-varying environments, uniform weighting minimizes asymptotic error; for rapidly-changing ones, discounted weighting with tuned γ provides faster adaptation. The system can automatically select the optimal weighting scheme using the derived ATE bounds as a cost function.

2. Optimal Step-Size and Iteration Budget Scheduling: Using the theoretical bounds (e.g., TE(t) ≤ α tw0 - w̃1 + (2G Z A)/(µt) + ηκΛ Z G Z for uniform weights), AI systems can pre-compute the minimal step size η and per-step iteration count E needed to guarantee a specified tracking error ε. This enables resource-aware deployment: systems can allocate computation (E) and learning rate (η) to meet accuracy targets while minimizing energy or latency.

3. Network-Topology-Aware Hyperparameter Tuning: The bias term ηκΛ Z G Z explicitly depends on network connectivity via Λ Z = 1/(1-λ2). AI systems can measure their graph's spectral gap (1-λ2) and automatically adjust η or E to compensate for poorly-connected networks, ensuring consistent tracking performance across different deployment topologies (e.g., sparse sensor networks vs. dense data centers).

4. Early-Stopping and Transient-Phase Control: The transient term α tw0 - w̃1 shows that convergence rate is governed by (1-ηµ) E. AI systems can monitor this term and decide when to switch from aggressive tracking (high E) to energy-saving mode (low E) once the transient has decayed below a threshold, extending battery life in edge devices.

5. Window-Length Optimization for Memory-Constrained Systems: For windowed strategies, the bounds show ATE scales as O(1/m) for uniform windows and O((1-γ)/(1-γ m)) for discounted windows. AI systems with limited memory can compute the minimum window length m* that achieves a target error floor, then discard older data—reducing storage requirements while provably maintaining accuracy.

6. Unified Controller for Distributed Learning Pipelines: The framework enables a supervisory controller that jointly optimizes (η, E, weighting strategy, window length) across the entire system. For example, in federated learning with streaming data, the controller can: (a) use uniform weighting during stable periods, (b) switch to discounted weighting when concept drift is detected, (c) increase E when network connectivity degrades, and (d) reduce η when approaching the bias floor—all guided by closed-form expressions rather than heuristic tuning.

7. Predictive Error Bounds for Online Decision-Making: The explicit ATE formulas (e.g., ATE ≤ (2G Z(1-γ)α)/(µ(1-α)) + ηκΛ Z G Z for discounted weights) allow AI systems to predict their worst-case tracking error before deployment. This is critical for safety-critical applications (autonomous vehicles, power grids) where the system must certify performance guarantees under dynamic conditions, enabling pre-deployment validation and risk assessment.

8. Heterogeneous Agent Adaptation: The bounds distinguish between DGD (bias ∝ C√κ) and diffusion (bias ∝ Cκ) algorithms. AI systems can choose per-agent algorithms based on local computational resources: agents with limited compute use DGD (lower per-iteration cost), while powerful agents use diffusion (better bias), with the global system still achieving provable tracking guarantees through the unified analysis.

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 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 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 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.