⚡ electrical engineering

Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

This paper analyzes decentralized first-order optimization methods for streaming data by modeling the global objective as a temporally weighted average, deriving contraction-mapping-based error bounds that explicitly characterize how different weighting strategies (uniform, discounted, or windowed) and network constraints influence tracking performance and bias floors.

Original authors: Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where a swarm of tiny robots, a fleet of self-driving cars, or a network of smart sensors needs to make decisions together. They can't all shout their data to a single super-computer in the middle; maybe they are too far apart, or maybe they need to keep their secrets private. Instead, they have to talk only to their neighbors, passing notes back and forth to figure out the best solution. This is the world of decentralized optimization. Think of it like a group of friends trying to pick a movie to watch. They don't have a boss telling them what to do; they just keep suggesting movies to the person next to them until everyone agrees on one.

Now, imagine that the "best movie" keeps changing every minute because new reviews are coming in, or the group's mood is shifting. This is streaming data: information that arrives one piece at a time, constantly updating the goal. The challenge is that the group has to keep moving toward the new target while only having a tiny amount of time to chat and calculate before the target moves again. If they move too slowly, they get left behind; if they move too fast based on old news, they might run in the wrong direction. The big question for scientists is: How do we teach these networks to chase a moving target without tripping over their own feet?

This paper, titled "Distributed Optimization with Streaming Data: A Temporal Weighting Perspective," dives into exactly that problem. The authors, Muhammad Faraz Ul Abrar, Nicolò Michelusi, and Erik G. Larsson, propose a new way to look at how these networks should weigh the information they receive. Instead of treating every new piece of data as a brand-new mystery, they suggest the network should act like a smart historian. They ask: How much should we remember from yesterday? How much from last week? And how much should we trust what just happened?

The researchers set up a mathematical model where the network's goal is a "temporally weighted average" of all the losses (or mistakes) it has seen so far. They tested two main strategies for this memory. The first is uniform weighting, which is like a student who studies for a test by reading every single page of the textbook equally, from the first chapter to the last. The second is exponentially discounted weighting, which is like a student who only cares about the last few chapters because they assume the old stuff is less relevant to the current test. They also looked at windowed versions, where the network only remembers the last few days of data and forgets everything else entirely.

Using a clever mathematical tool called a "contraction-mapping" (which is essentially a way of proving that if everyone keeps talking to their neighbors, they will eventually stop arguing and agree on something), the authors derived strict rules for how well these networks can track the moving target. They found that the choice of memory strategy makes a huge difference. If the network uses uniform weighting, the error component caused by the network's inability to keep up with the moving target gets smaller and smaller over time, eventually vanishing. However, the total error does not disappear completely. Because the network is decentralized (no central boss) and agents have different data, a small, permanent "bias floor" remains. It's like the group slowly getting better and better at picking the right movie until they are as close to perfect as their decentralized nature allows, but they can never be perfect due to the inherent limitations of their setup.

However, if they use discounted or windowed strategies, the story changes. The paper shows that these methods create an additional "tracking floor" on top of the decentralization bias. This means no matter how long they keep talking, there will always be a small, permanent gap between where they are and the perfect answer. It's like the group will always be slightly off because they are ignoring the history that would have helped them. The size of this gap depends on how quickly they forget (the discount factor) or how many days they remember (the window size). The authors also proved that because the network is decentralized, there is always a tiny bit of extra error caused by the fact that the agents are spread out and have different data, but this is a separate issue from the memory strategy.

The paper doesn't just guess these things; they proved them with rigorous math and then checked their predictions with computer simulations. In these simulations, they created a network of 50 agents with quadratic losses (a specific type of math problem that's easy to solve exactly) and watched how they performed. The results matched their theory perfectly: uniform weighting led to a steady decline in the "tracking" part of the error, leaving only the constant bias floor, while discounted and windowed methods settled into a higher, steady, non-zero error level. The simulations showed that if you want to reduce that error floor, you have to either remember more (increase the window) or forget more slowly (increase the discount factor), but you can never make it disappear completely with those specific strategies.

In short, this paper tells us that when a decentralized network is chasing a moving target, the way it chooses to remember the past dictates its future success. If you want to get as close to perfect as possible, you need to treat all past data with equal respect (uniform weighting), which allows the tracking error to vanish, leaving only the unavoidable bias from decentralization. If you decide to forget the past quickly to stay agile, you pay a price: you will always be a little bit off, no matter how hard you try. The authors provide the exact formulas to calculate exactly how big that "off" gap will be, helping engineers design smarter, more efficient networks for everything from power grids to autonomous vehicles.

Technical Summary: Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

Problem Formulation
The paper addresses decentralized optimization in dynamic environments where data arrive sequentially across a network of agents. Unlike classical optimization, which assumes fixed, time-invariant objective functions, this work considers settings where the learning objective evolves over time due to the continuous acquisition of new data samples. The network operates under constraints of limited communication and computation per time step, meaning agents can only perform a fixed number of local gradient and mixing iterations before new data arrives and shifts the objective.

The core problem is defined as tracking the time-varying minimizer of a global objective function, $F_t(w)$ , which is constructed as a temporally weighted average of losses observed across the network up to time $t$ . The authors aim to characterize the tracking error (TE)—the Euclidean distance between the agents' current iterates and the true, time-varying minimizer—under various temporal weighting strategies and decentralized algorithms (specifically Decentralized Gradient Descent and Diffusion).

Methodology
The authors propose a structured approach that explicitly incorporates the streaming-data nature of the problem into the optimization model via temporal weighting.

Temporal Weighting Strategies: The global objective is formulated as a weighted sum of past network-wide losses. The paper introduces a structured family of kernel-parameterized weights, including:
- Uniform weights: Assigning equal importance to all past samples (suitable for stationary environments).
- Exponentially discounted weights: Geometrically discounting older samples to emphasize recent observations (suitable for non-stationary environments).
- Finite-memory windowed variants: Both uniform and discounted strategies are adapted to use only the most recent $m$ samples to reduce memory and computational requirements.
- Uniform-shrinkage weighting: A recursive construction that allows for time-adaptive strategies.
Algorithmic Framework: The analysis covers multi-iteration decentralized first-order methods (DGD and Adapt-Then-Combine diffusion) where $E$ iterations are performed per time step.
Analytical Approach: The authors employ a contraction-mapping viewpoint to derive unified tracking error bounds. The total tracking error is decomposed into two distinct components:
- Fixed-Point Tracking Error (FPTE): The error arising from the algorithm's inability to fully converge to the moving fixed point within the limited iteration budget $E$ before the objective changes.
- Fixed-Point Bias: The distance between the algorithm's fixed point (under a frozen objective) and the true minimizer of the current objective. This term captures the effects of data heterogeneity across the network and the step size.

Key Contributions

Structured Formulation: The paper extends single-agent streaming optimization formulations to decentralized multi-agent networks, explicitly modeling the objective evolution through temporal weights rather than treating it as a generic, unstructured drift.
Unified Error Decomposition: A novel analysis decomposes the tracking error into a fixed-point tracking component and a bias term. This decomposition explicitly characterizes the roles of the temporal weighting rule, per-step iteration budget ( $E$ ), step size ( $\eta$ ), network connectivity, and data heterogeneity.
Specific Tracking Guarantees: The authors derive explicit bounds for four canonical weighting strategies:
- Uniform Weighting: Yields a vanishing FPTE contribution of order $O(1/t)$ . The asymptotic tracking error is governed solely by the bias term (proportional to the step size).
- Discounted and Windowed Weighting: Generally induce non-vanishing tracking floors. The FPTE contribution does not vanish asymptotically but is governed by the discount factor ( $\gamma$ ) or the effective memory (window length $m$ ).
Iteration Complexity: The paper provides sufficient conditions on the number of iterations per time step ( $E$ ) required to achieve a target tracking error, revealing a trade-off between the step size and the iteration budget for non-uniform weighting schemes.

Results
Theoretical analysis and numerical experiments (using quadratic losses and Gaussian random walks) demonstrate the following trends:

Uniform Weighting: The tracking error decreases over time, with the FPTE component decaying as $O(1/t)$ . The final error floor is determined by the decentralization-induced bias. Increasing the number of iterations ( $E$ ) accelerates the transient decay but does not alter the asymptotic bias floor.
Exponentially Discounted Weighting: The tracking error converges to a steady-state level significantly higher than the uniform case. This floor is non-vanishing and depends on the discount factor; a smaller $\gamma$ (faster forgetting) leads to a larger error floor due to persistent fixed-point drift.
Windowed Strategies: Finite-memory strategies introduce a non-vanishing error floor controlled by the window length $m$ . For windowed-discounted weights, performance improves with $m$ only up to the effective memory induced by the discount factor.
Bias vs. Tracking: In all cases, a constant step size induces a non-zero bias floor due to decentralization. However, for uniform weighting, the tracking component vanishes, whereas for discounted/windowed strategies, the tracking component remains a significant contributor to the total error.

Significance
The paper claims that by explicitly encoding the temporal relevance of past data through weighting rules, the optimization model yields sharper and more interpretable tracking guarantees compared to generic worst-case drift assumptions. The structured analysis reveals that the choice of temporal weighting fundamentally alters the nature of the tracking error:

Uniform weighting allows for asymptotic elimination of tracking error (leaving only bias), making it suitable for stationary environments.
Discounted and windowed strategies, while adaptive to non-stationarity, inherently incur non-vanishing tracking floors.
The derived bounds provide system designers with explicit formulas to balance the trade-offs between memory/computation (via $E$ and window size), adaptability (via $\gamma$ ), and asymptotic accuracy.

The work does not propose new learning architectures or specific real-world applications but rather provides a theoretical framework to understand the performance limits of existing decentralized algorithms in streaming data scenarios.

Technical Summary: Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

More like this