Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

Technical Summary: Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

Problem Formulation
This work addresses the challenge of decentralized optimization in dynamic environments where data arrives sequentially over a network of agents. Unlike classical static optimization or generic time-varying formulations that treat the objective evolution as an arbitrary process, this paper adopts a structured, weight-based formulation specific to streaming data.

The system consists of $N$ agents connected via an undirected, connected graph. At each time step $t$, every agent $n$ observes a new data sample and incurs an instantaneous loss $\ell_{n,t}(w)$. The global objective $F_t(w)$ is defined as a temporally weighted average of all network losses observed up to time $t$:
$$F_t(w) \triangleq \sum_{i=1}^t a_i(t) F_i(w),$$
where $F_i(w)$ is the average instantaneous loss at time $i$, and $a_i(t)$ are temporal weights satisfying $\sum a_i(t) = 1$. The goal is to track the time-varying minimizer $w^*_t = \arg\min_w F_t(w)$ using a decentralized algorithm with a limited communication and computation budget (i.e., a fixed number of inner iterations $E$ per time step).

Methodology
The authors analyze Decentralized Gradient Descent (DGD) applied to this streaming setting. The algorithm operates in two phases per time step:

1. Objective Update: The network incorporates the new time-weighted objective $F_{t+1}$.
2. Inner Iterations: Starting from the previous iterate, agents perform $E$ steps of DGD on the updated objective. The update rule is $w^{(k+1)}_t = M w^{(k)}_t - \eta \nabla f_{t+1}(w^{(k)}_t)$, where $M$ is the mixing matrix and $\eta$ is the step size.

The core analytical approach utilizes fixed-point operator theory. The authors define a time-varying DGD mapping $\phi_t(w) = Mw - \eta \nabla f_t(w)$. Under assumptions of strong convexity and smoothness (Assumption 1) and bounded minimizers (Assumption 2), they prove that $\phi_t$ is a contraction mapping. Consequently, for any frozen time $t$, there exists a unique fixed point $\tilde{w}_t$ such that $\tilde{w}_t = \phi_t(\tilde{w}_t)$.

The tracking error (TE), defined as $\|w_t - w^*_t\|$, is decomposed via the triangle inequality into two distinct components:

1. Fixed-Point Tracking Error (FPTE): The distance between the current iterate $w_t$ and the moving fixed point $\tilde{w}_t$. This term captures the algorithm's ability to converge to the current objective within the limited $E$ iterations.
2. Bias Term: The distance between the fixed point $\tilde{w}_t$ and the true time-varying optimizer $w^*_t$. This term arises from the decentralization of data and the step size $\eta$.

Key Contributions and Results
The paper derives explicit tracking error bounds for two canonical temporal weighting strategies:

1. Uniform Weights: All past samples are weighted equally ($a_i(t) = 1/t$).

   • Result: The fixed-point tracking error decays at a rate of $O(1/t)$.
   • Asymptotic Behavior: The total tracking error converges to a non-zero floor determined entirely by the bias term ($\eta \kappa \Lambda G$), which depends on the step size, condition number, network topology, and data heterogeneity. The contribution from the moving fixed point vanishes over time.

2. Exponentially Discounted Weights: Older samples are geometrically decayed ($a_i(t) \propto \gamma^{t-i}$).

   • Result: The fixed-point tracking error does not vanish; it induces a non-vanishing steady-state floor controlled by the discount factor $\gamma$.
   • Asymptotic Behavior: The total tracking error converges to a floor comprising both the bias term and a fixed-point tracking floor proportional to $(1-\gamma)$. The algorithm cannot fully catch up to the moving fixed point because the effective objective continues to evolve at a non-vanishing rate due to the constant influx of new, heavily weighted samples.

In both cases, the analysis reveals that decentralization introduces an additional bias floor under a constant step size, which is proportional to the gradient magnitude at the optimal solution (reflecting data heterogeneity). If data were homogeneous across agents, this bias would vanish.

Significance
The paper claims that by moving away from generic time-varying models to a structured streaming-data perspective, it provides sharper and more interpretable tracking error guarantees. Specifically:

• It clarifies the trade-off between the temporal weighting strategy and the asymptotic tracking performance.
• It demonstrates that while uniform weighting allows the algorithm to eventually "catch up" to the moving fixed point (vanishing FPTE), discounted weighting inherently limits this capability, resulting in a permanent tracking floor.
• It validates these theoretical findings through numerical simulations on a network of agents with quadratic losses, showing that increasing the number of inner iterations ($E$) improves transient performance but cannot eliminate the asymptotic bias floor caused by decentralization and step size constraints.

The work is presented as a theoretical foundation for understanding the fundamental limits of decentralized learning from streaming data, distinguishing between errors caused by algorithmic lag (FPTE) and errors caused by network/data structure (Bias).