Paper deep dive
Distributed Optimization with Streaming Data: A Temporal Weighting Perspective
Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.09565v1
- Canonical: https://arxiv.org/abs/2608.09565v1
Trouble viewing inline? Open PDF directly →
Full Text
98,426 characters extracted from source content.
Expand or collapse full text
Distributed Optimization with Streaming Data: A Temporal Weighting Perspective Muhammad Faraz Ul Abrar, , Nicolò Michelusi, , and Erik G. Larsson M. Faraz Ul Abrar and N. Michelusi are with the School of Electrical, Computer and Energy Engineering, Arizona State University. email: mulabrar, nicolo.michelusi@asu.edu. Erik G. Larsson is with the Department of Electrical Engineering (ISY), Linköping University, 58183 Linköping, Sweden. e-mail: erik.g.larsson@liu.se. This research was funded in part by NSF under grant CNS-21290152129015. The work of E. G. Larsson was supported in part by ELLIIT, VR, and the KAW foundation.A preliminary version of this work is available in [1]. 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 and diffusion, where only a fixed number of communication/gradient steps can be performed before new samples arrive. 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 (1/t)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. I Introduction Modern artificial intelligence (AI) systems increasingly rely on learning and optimization tools for intelligent decision-making across domains such as autonomous vehicles, robotics, telecommunications, power grids, and cyber-physical systems [2, 3]. Despite their success, many existing AI systems follow an optimize-and-deploy paradigm, where a model is trained for a fixed objective under an implicitly static data distribution. In practice, however, many applications are both dynamic and decentralized: data arrive sequentially over time [4, 5, 6], while storage, computation, and communication are distributed across multiple agents due to scale, privacy, or architectural constraints [7, 8, 9, 10]. Representative examples include mobile target localization, measurement-based network optimization, streaming data processing, and adaptive control under time-varying dynamics [3, 11, 4, 12]. These settings call for learning systems that continuously adapt to incoming information while operating cooperatively over a network. Time-varying optimization provides a natural framework for such problems. A network of agents collaboratively tracks the minimizer of an objective that evolves over time, typically while performing only a limited number of optimization and communication steps before the objective changes again [3, 4]. Exact tracking is therefore generally infeasible, and performance is naturally measured through the tracking error (TE), defined at each time step as the Euclidean distance between the current iterate and the corresponding optimizer. Existing decentralized time-varying optimization methods have primarily focused on algorithmic developments for improving TE performance [13, 14, 15, 16, 17, 12, 18, 19, 20]. However, these works treat the objective evolution as generic and largely unstructured. In these formulations, the sequence of objectives is usually specified directly as an arbitrary time-varying process and worst-case TE guarantees are derived under generic “minimizer drift” assumptions. While broadly applicable, this viewpoint treats the temporal evolution as exogenous and unstructured, and may therefore be conservative when the objective changes according to a specific mechanism. In many modern learning problems, the objective does not evolve arbitrarily. Rather, it changes because new data samples are continuously acquired across the network, see [21] and references therein. The objective evolution therefore inherits structure from the underlying data-acquisition process. This observation motivates the central question addressed in this paper: Can the streaming-data structure be explicitly incorporated into the optimization model to obtain sharper and more interpretable tracking guarantees? To address this question, in this work, we study decentralized time-varying optimization from a streaming-data perspective. Each agent acquires data online, and the network objective at time t is modeled as a temporally weighted average of losses over the samples observed so far. By explicitly encoding the temporal relevance of past data through the weights, the resulting formulation yields weight-specific tracking guarantees that sharpen generic worst-case drift-based bounds. Building on this structured formulation, we analyze decentralized first-order methods under limited computation and communication per time step. In particular, we develop a unified TE analysis for a general class of temporal weighting strategies and specialize the results to two natural choices: (i) uniform weights, which assign equal importance to all past samples and are natural for stationary environments, and (i) exponentially discounted weights, which geometrically discount old samples and emphasize recent observations. We further specialize the guarantees to their finite-memory windowed variants. The resulting bounds explicitly characterize the roles of the temporal weighting rule, per-step iteration budget, network connectivity, step size, and data heterogeneity. For smooth and strongly convex losses, our analysis reveals a vanishing fixed-point tracking contribution of order (1/t)O(1/t) under uniform weighting and generally non-vanishing TE floors under discounted and finite-memory windowed strategies. I-A Related Work The field of time-varying optimization traces back to early works on non-stationary optimization [22, 23, 24], primarily in the single-agent setting. For smooth and strongly convex objectives, classical results establish tracking to a neighborhood whose size depends on a bounded-minimizer-drift or bounded-gradient-variation condition [22, 24, 25, 3]. Methods that solely utilize the objective available at time t to track the drifting minimizer are often termed correction-only schemes [3]. In contrast, prediction-correction schemes first predict the next optimizer using the objective at time t (e.g., via a first-order optimality condition), and then perform a correction update once the objective at time t+1t+1 becomes available, leading to improved asymptotic tracking performance [25, 26, 27, 15]. Related prediction mechanisms based on parameter estimation, including Kalman-filter and neural-network predictors, have also been studied [28, 29]. Time-varying optimization has also been investigated in decentralized multi-agent settings using primal methods, such as decentralized gradient descent (DGD) [30], and primal-dual methods, such as alternating direction method of multipliers (ADMM) [31]; see, e.g., [13, 14, 15, 16, 17, 18, 19, 20, 32]. Nonetheless, these works characterize temporal variation through generic worst-case drift measures and treat the objective evolution as exogenous. In contrast, the present formulation ties the evolution of the objective explicitly to streaming data through the temporal weights. Another closely related research direction is online learning [33, 34, 35, 5]. In online learning, a learner chooses the decision before observing the current loss, and performance is commonly measured through regret against a fixed or time-varying comparator [36, 37, 38]. The paradigm of continual learning similarly considers sequential data or “task” arrivals, with a primary focus on catastrophic forgetting and methods for retaining previously learned knowledge [39, 40, 6, 41, 42, 43]. While these directions are related through their sequential-data viewpoint, they primarily address information availability, regret, or task adaptation. Our focus is instead on tracking-error guarantees for decentralized optimization algorithms operating under communication and computation constraints. Learning from data streams has also been studied in server-coordinated federated settings [44, 45, 46]. Among these, [45] is closest in spirit to our work, as it considers memory-constrained learning from streaming data and assigns relative importance weights to samples. Yet a key distinction is that [45] adopts a statistical learning viewpoint: it designs the weights to improve generalization error under distributional assumptions. In contrast, we provide an optimization-theoretic, weight-specific characterization of the TE of decentralized first-order methods, without imposing a data-generating distribution. Moreover, the setting considered in this work is fully decentralized and does not rely on a coordinating server. I-B Contributions and Organization Our main contributions are summarized as follows: • We extend our single-agent formulation in [47] to decentralized multi-agent networks and formulate decentralized learning from streaming data samples through temporally weighted objectives. We introduce a structured family of kernel-parameterized temporal weighting strategies, including uniform and exponentially discounted weights, together with their finite-memory windowed variants. • Leveraging the contraction-mapping framework of [48], we develop a unified TE analysis for multi-iteration DGD and diffusion under limited communication and computation per time step. • We develop TE guarantees that decompose the overall error into a fixed-point tracking component and a bias term capturing the effect of data heterogeneity across the network. The resulting bounds explicitly characterize the dependence on the per-step iteration budget, network connectivity, step size, and temporal weighting rule. • We specialize the TE guarantees to four canonical weighting strategies and use numerical experiments to illustrate the predicted effects of key system parameters and temporal-weighting choices. The remainder of the paper is organized as follows. Section I presents the system model and streaming-data objective. Section I introduces the temporal weighting strategies. Section IV describes the decentralized algorithms and performance metrics. Section V develops the TE analysis. Section VI presents numerical results. Section VII concludes the paper. I-C Notation Scalars are denoted by italic letters (e.g., a), vectors by boldface lowercase letters (e.g., w), and matrices by boldface uppercase letters (e.g., A). Bold sans-serif lowercase letters are reserved for network-stacked vectors. The all-ones vector in ℝNR^N is denoted by N 1_N. For a vector or matrix, (⋅)⊤(·) denotes its transpose, and the Euclidean norm is denoted by ∥⋅∥\|·\|. For a stacked vector =[1⊤⋯N⊤]⊤∈ℝNd w= bmatrixw_1 ·sw_N bmatrix ^Nd, the notation []n∈ℝd[ w]_n ^d denotes its n-th block. The identity matrix of dimension q is denoted by q∈ℝq×qI_q ^q× q, and ⊗ denotes the Kronecker product. For a matrix A, ‖2\|A\|_2 denotes its spectral norm and †A its Moore–Penrose pseudoinverse. The symbols ℛ()R(A) and ()N(A) denote the range and nullspace of A, respectively. If A is symmetric, ⪰0A 0 means that A is positive semidefinite, and λmin() _ (A) and λmax() _ (A) denote its minimum and maximum eigenvalues. The indicator function of an event ω is denoted by ω 1\ω\. For a scalar x∈ℝx , we define its positive and negative parts as x+≜maxx,0x_+ \x,0\ and x−≜max−x,0x_- \-x,0\. For functions f(ϵ)f(ε) and g(ϵ)g(ε), we write f(ϵ)=(g(ϵ))f(ε)=O(g(ε)) if f(ϵ)f(ε) is upper bounded by a constant multiple of g(ϵ)g(ε) as ϵ→0ε→ 0, and f(ϵ)=Θ(g(ϵ))f(ε)= (g(ε)) if f(ϵ)f(ε) is both upper and lower bounded by constant multiples of g(ϵ)g(ε) as ϵ→0ε→ 0. I System Model and Problem Formulation We consider a network of N agents collaboratively solving a time-varying optimization problem induced by streaming data, as shown in Fig. 1. At each time step t≥1t≥ 1, agent n∈1,…,Nn∈\1,…,N\ observes a new data sample and incurs the instantaneous loss ℓn,t() _n,t(w) evaluated at the model parameter ∈ℝdw ^d. The network seeks to track the minimizer of a suitably constructed weighted average of the accumulated losses (discussed next), under a limited communication/computation budget per time index. The agents communicate over an undirected, connected, time-invariant graph. In particular, the communication among agents is described by a symmetric mixing matrix ∈ℝN×NM ^N× N. Specifically, []m,n[M]_m,n is the weight used by agent m to combine information from agent n, and []m,n=0[M]_m,n=0 whenever agents m and n do not directly communicate. We assume that M satisfies =⊤,N=N. =M , 1_N= 1_N. (1) We further assume that the eigenvalues of M lie in (−1,1](-1,1] and are ordered as 1=λ1>λ2≥⋯≥λN>−11= _1> _2≥·s≥ _N>-1.111Sufficient conditions for this spectral property, e.g., in terms of nonnegativity of M and non-bipartiteness of the underlying graph, are discussed in [48]. We next define the streaming-data objective. The network-wide instantaneous loss at time t is Ft()≜1N∑n=1Nℓn,t(), F_t(w) 1N _n=1^N _n,t( w), (2) capturing the average loss computed across all the agents at time t. Building on the single-agent formulation in [47], we define the time-t objective as a temporally weighted average of the past network-wide losses. Let ai(t)i=1t\a_i(t)\_i=1^t represent a nonnegative temporal weighting strategy that satisfies ai(t)∈[0,1],∀i≤t,∑i=1tai(t)=1 a_i(t)∈[0,1],\;∀ i≤ t,\; _i=1^ta_i(t)=1 (3) for all t≥1t≥ 1. Several strategies that satisfy (3) are discussed in the next section. This leads to the following time-varying optimization problem: ¯t∗∈argmin∈ℝdF¯t(),F¯t()≜∑i=1tai(t)Fi(), w_t^*∈ _w ^d F_t(w)\;, F_t(w) _i=1^ta_i(t)\,F_i(w), (4) defined for all t≥1t≥ 1. We emphasize that the objective F¯t(⋅) F_t(·), and hence its minimizer ¯t∗ w_t^*, evolves as new samples arrive across the network. Our goal is to characterize how well decentralized methods, such as DGD [30] and diffusion [11], track this moving minimizer when only a limited number of communication/computation iterations can be performed per time step. Before presenting the decentralized algorithms and the associated tracking guarantees, we first discuss the temporal weighting strategies used in (4). Figure 1: Illustration of decentralized learning from streaming data. Each agent receives a local stream of samples and exchanges information with neighboring agents over a communication graph. The network tracks the minimizer of a temporally weighted objective formed from past losses. I Temporal Weights for Streaming Losses The temporal weights ai(t)i=1t\a_i(t)\_i=1^t in (4) determine how past samples contribute to the current objective and hence control the stability–plasticity tradeoff in streaming environments [6]. We present two structured ways to generate such weights, and begin with a structured family of temporal weightings induced by kernel sequences, which includes several canonical choices. I-A Stationary kernel-induced temporal weights Let gkk≥0\g_k\_k≥ 0 be a nonnegative kernel sequence with g0>0g_0>0, and define the associated kernel-induced temporal weights for all t≥1t≥ 1 as ai(t)≜gt−iSt,St≜∑k=0t−1gk,i=1,…,t. a_i(t) g_t-iS_t, S_t _k=0^t-1g_k, i=1,…,t. (5) Here, StS_t normalizes the weights so the probability simplex constraint (3) holds. Note that the index k=t−ik=t-i can be interpreted as the age of sample i at time t. Since ai(t)∝gt−ia_i(t) g_t-i, the kernel gk\g_k\ specifies how sample importance varies with age, and (5) implements a simple shift-and-normalize weighting rule. Several choices follow as special cases: ∙ Uniform Weights: Setting gk=1g_k=1 for all k≥0k≥ 0 yields ai(t)=1t,i=1,…,t. a_i(t)= 1t, i=1,…,t. (6) This rule is natural in stationary environments. ∙ Exponentially discounted weights: Setting gk=γkg_k=γ^k with a discount factor γ∈(0,1)γ∈(0,1) results in ai(t)=(1−γ)γt−i1−γt,i=1,…,t. a_i(t)= (1-γ)γ^t-i1-γ^t, i=1,…,t. (7) This rule emphasizes recent samples and can be naturally employed for adaptation in non-stationary environments; see, e.g., [4] for several applications. ∙ Windowed-uniform weights: A finite-memory variant of the uniform weighting strategy assigns equal weight only to the most recent m samples, corresponding to gk=0≤k≤m−1g_k= 1\0≤ k≤ m-1\: ai(t)=1m,t−m+1≤i≤t,0,otherwise,for t≥m. a_i(t)= cases 1m,& t-m+1≤ i≤ t,\\ 0,& , cases t≥ m. (8) ∙ Windowed-discounted weights: Similarly, choosing gk=γk0≤k≤m−1g_k=γ^k 1\0≤ k≤ m-1\ yields ai(t)=(1−γ)γt−i1−γm,t−m+1≤i≤t,0,otherwise.for t≥m. a_i(t)= cases (1-γ)γ^t-i1-γ^m,&t-m+1≤ i≤ t,\\ 0,&otherwise. cases t≥ m. (9) This provides a finite-memory approximation of exponentially discounted weighting using only the last m samples. I-B Uniform-shrinkage weighting The stationary kernel family (5) assigns weights based on age using a fixed time-invariant kernel sequence. Another possible construction is to generate the weights recursively by shrinking all previous weights by the same factor whenever a new sample arrives. Let βtt≥1\ _t\_t≥ 1 satisfy β1=1 _1=1 and βt∈(0,1) _t∈(0,1) for t≥2t≥ 2, and define the time-varying objective function as F¯t+1()=(1−βt+1)F¯t()+βt+1Ft+1(), F_t+1(w)=(1- _t+1)\, F_t(w)+ _t+1\,F_t+1(w), (10) for all t≥1t≥ 1. Equivalently, the induced weights satisfy ai(t)=βi∏k=i+1t(1−βk),i=1,…,t. a_i(t)= _i _k=i+1^t(1- _k), i=1,…,t. (11) This family recovers uniform weighting with βt+1=1/(t+1) _t+1=1/(t+1) and exponential discounting with βt+1=(1−γ)/(1−γt+1) _t+1=(1-γ)/(1-γ^t+1). Notably, (11) also allows time-adaptive weighting strategies. For example, one may choose βt _t to decay from an initially constant level toward 1/t1/t, so that the objective first emphasizes recent samples for fast adaptation and then gradually approaches uniform weighting for stability. Such schedules depend on absolute time, not only on sample age, and are therefore not generally representable by a stationary kernel. On the other hand, since βt∈(0,1) _t∈(0,1) preserves strictly positive weights for all past samples, this construction does not capture the finite-window rules in (8)–(9). IV Algorithm and Performance Metrics We now present the decentralized methods used to solve (4) and define the associated performance metrics that are adopted throughout the paper. We study two decentralized first-order algorithms: decentralized gradient descent (DGD) [30] and adapt-then-combine (ATC) diffusion [11].222Throughout the paper, “diffusion” refers to ATC diffusion, which is closely related to combine-then-adapt diffusion; see [48] for a discussion. Each agent n maintains a local parameter n,t∈ℝdw_n,t ^d at time t. Upon receiving new data samples, the objective is updated, after which the agents perform E≥1E≥ 1 decentralized iterations before the time advances. Each decentralized iteration consists of one mixing and one local gradient step. This models a fixed communication/computation budget per time step. Let t∈ℝNd w_t ^Nd denote the stacked vector of local parameters, t≜[1,t⊤⋯N,t⊤]⊤ w_t bmatrixw_1,t &·s&w_N,t bmatrix with n,t=[t]nw_n,t=[ w_t]_n. Next, define the block-separable instantaneous objective ft()≜∑n=1Nℓn,t(n), f_t( w) _n=1^N _n,t(w_n), and its temporally weighted version f¯t()≜∑i=1tai(t)fi()=∑i=1tai(t)∑n=1Nℓn,i(n), f_t( w) _i=1^ta_i(t)\,f_i( w)= _i=1^ta_i(t) _n=1^N _n,i(w_n), (12) whose gradient has the block-stacked form, and is given by ∇f¯t()=∑i=1tai(t)∇fi()=∑i=1tai(t)[∇ℓ1,i(1)⋮∇ℓN,i(N)]. ∇ f_t( w)= _i=1^ta_i(t)\,∇ f_i( w)= _i=1^ta_i(t) bmatrix∇ _1,i(w_1)\\ \\ ∇ _N,i(w_N) bmatrix. (13) The objectives F¯t(⋅) F_t(·) in (4) and f¯t(⋅) f_t(·) in (12) encode the same collection of sample losses ℓn,i\ _n,i\. However, F¯t(⋅) F_t(·) is defined over a common decision parameter ∈ℝdw ^d, whereas f¯t(⋅) f_t(·) is defined over the stacked collection of local parameters ∈ℝNd w ^Nd which need not be consensual. In particular, on the consensus subspace N⊗:∈ℝd⊆ℝNd\ 1_N :w ^d\ ^Nd, we have f¯t(N⊗)=∑i=1tai(t)∑n=1Nℓn,i()=NF¯t() f_t( 1_N )= _i=1^ta_i(t) _n=1^N _n,i(w)=N\, F_t(w). Thus, on the consensus subspace, the two objectives differ only by the constant factor N and and their minimizers correspond through the mapping ↦N⊗w 1_N . Finally, we let ¯t∗≜N⊗¯t∗∈ℝNd w_t^* 1_N w_t^* ^Nd denote the stacked version of the global minimizer in (4). After the new samples arrive at time t+1t+1, the agents perform E decentralized iterations on the updated objective. For DGD, the k-th iteration at agent n is n,t(k+1)=∑m=1N[]n,mm,t(k)−η∑i=1t+1ai(t+1)∇ℓn,i(n,t(k)), _n,t^(k+1)= _m=1^N[M]_n,mw_m,t^(k)-η _i=1^t+1a_i(t+1)∇ _n,i (w_n,t^(k) ), (14) whereas diffusion performs the adaptation and combination: ~n,t(k+1) w_n,t^(k+1) =n,t(k)−η∑i=1t+1ai(t+1)∇ℓn,i(n,t(k)), =w_n,t^(k)-η _i=1^t+1a_i(t+1)∇ _n,i (w_n,t^(k) ), (15) n,t(k+1) _n,t^(k+1) =∑m=1N[]n,m~m,t(k+1), = _m=1^N[M]_n,m w_m,t^(k+1), (16) for k=0,…,E−1k=0,…,E-1. Stacking the local parameters across the network, the DGD and diffusion updates can be expressed in the unified form t(k+1)=¯t(k)−η¯∇f¯t+1(t(k)), w_t^(k+1)= M w_t^(k)-η Z∇ f_t+1( w_t^(k)), (17) where η>0η>0 is a constant step size, and we define ¯≜⊗d M _d, ¯≜⊗d∈ℝNd×Nd Z _d ^Nd× Nd and ≜,DGD,,diffusion. casesI,&DGD,\\ M,&diffusion. cases (18) For both methods, t(0)=t w_t^(0)= w_t, and the macro-update (the stacked local parameter update) after E iterations is t+1≜t(E). w_t+1 w_t^(E). (19) When E=1E=1, (17)–(19) reduce to the standard single-step DGD/diffusion updates applied to the time-varying objective. In the considered streaming setting, the objective changes whenever new data arrive; therefore, the stacked iterates t\ w_t\ generally do not converge. We therefore measure performance through the tracking error TE(t)≜‖t−¯t∗‖=‖t−N⊗¯t∗‖, (t) \| w_t- w_t^* \|= \| w_t- 1_N w_t^* \|, (20) and the asymptotic tracking error ATE≜lim supt→∞‖t−¯t∗‖. _t→∞ \| w_t- w_t^* \|. (21) V Tracking Error Analysis In this section, we analyze the decentralized updates (17)–(19) to solve the streaming time-varying problem (4). Following [48], we adopt a contraction-mapping viewpoint, which enables a unified TE analysis for both DGD and diffusion. We first derive generic TE bounds and then specialize them to the temporal weighting strategies in Section I. Define the time-varying decentralized update operator ϕt:ℝNd→ℝNd _t:R^Nd→R^Nd as ϕt()≜¯−η¯∇f¯t(), _t( w) M w-η Z∇ f_t( w), (22) where ¯=⊗d M=M _d and ¯=⊗d Z=Z _d. The decentralized updates in (17)–(19) with E iterations at time t can then be written as t+1=(ϕt+1∘⋯∘ϕt+1⏟Etimes)(t)≜Φt+1(t), w_t+1=( _t+1 ·s _t+1_E\ times)( w_t) _t+1( w_t), (23) where we use Φt(⋅) _t(·) to denote the composition of the mapping ϕt(⋅) _t(·) applied E times. For the analysis, we make the following standard assumptions; see, e.g., [49, 50, 48]. Assumption 1. For every agent n and time t, the loss ℓn,t(⋅) _n,t(·) is L-smooth and μ-strongly convex. Then, for all ,∈ℝdx,y ^d, μ‖−‖≤‖∇ℓn,t()−∇ℓn,t()‖≤L‖−‖ μ\|x-y\|≤ \|∇ _n,t(x)-∇ _n,t(y) \|≤ L\|x-y\| (24) We use κ≜L/μκ L/μ with κ≥1κ≥ 1 to denote the condition number of the optimization problem. Since Ft(⋅)F_t(·) and F¯t(⋅) F_t(·) are convex combinations of the losses at time t and up to time t, respectively, both are also L-smooth and μ-strongly convex for all t≥1t≥ 1. The same properties also hold for the block-separable objectives ft(⋅)f_t(·) and f¯t(⋅) f_t(·). That is, for all ,∈ℝNd u, v ^Nd and for either choice f~t∈ft,f¯t f_t∈\f_t, f_t\, ‖∇f~t()−∇f~t()‖≤L‖−‖, \|∇ f_t( u)-∇ f_t( v) \|≤ L\| u- v\|, (25) f~t()≥f~t()+∇f~t()⊤(−)+μ2‖−‖2. f_t( v)≥ f_t( u)+∇ f_t( u) ( v- u)+ μ2\| v- u\|^2. (26) Under Assumption 1, the analysis in Section IV.C of [48] gives the following lemma. Lemma 1. Suppose Assumption 1 holds. Then, ϕt(⋅) _t(·) is a contraction for every t, and ‖ϕt()−ϕt()‖≤(1−ημ)‖−‖,∀,∈ℝNd. \| _t( u)- _t( v)\|≤(1-ημ)\| u- v\|, ∀\, u, v ^Nd. (27) under the step size conditions 0<η≤(1+λN)/(L+μ)0<η≤(1+ _N)/(L+μ) for DGD and 0<η≤2/(L+μ)0<η≤ 2/(L+μ) for diffusion. Consequently, Φt _t is a contraction with factor α≜(1−ημ)E∈(0,1)α (1-ημ)^E∈(0,1). Throughout the rest of the analysis, we assume the step size conditions of Lemma 1. Hence, by Banach’s fixed-point theorem [51], each ϕt(⋅) _t(·) admits a unique fixed point, given by ~t∈ℝNds.t.~t=ϕt(~t). w_t ^Nd .t. w_t= _t( w_t). (28) Since Φt(⋅) _t(·) is the E-fold composition of ϕt(⋅) _t(·), ~t=Φt(~t) w_t= _t( w_t). The sequence ~t\ w_t\ provides a natural reference trajectory for the analysis: it represents the network state to which the decentralized method would converge if the objective f¯t(⋅) f_t(·) were frozen at time t. Leveraging this perspective, the tracking error in (20) can be upper-bounded as TE(t) (t) =‖t−¯t∗‖≤‖t−~t‖⏟FPTE(t)+‖~t−¯t∗‖⏟FP bias. = \| w_t- w_t^* \|≤ \| w_t- w_t \|_FPTE(t)+ \| w_t- w_t^* \|_FP bias. (29) The fixed-point tracking error (FPTE) above captures the ability of the algorithms to track a moving fixed point under a limited per-time-step iteration budget. The second term is the fixed-point bias, capturing the distance between the fixed point and the minimizer at time t. To bound these two terms, we next impose the following boundedness condition on the sample-wise minimizers. Assumption 2. For each agent n and time t, let n,t∗∈argmin∈ℝdℓn,t()w_n,t^*∈ _w ^d _n,t(w). There exists C>0C>0 such that ‖n,t∗‖≤C\|w_n,t^*\|≤ C for all n and t. Assumption 2 is a structural condition on the sample losses, rather than a direct bounded-drift assumption on the minimizer sequence, as commonly used in time-varying optimization; see, e.g., [3]. Similar bounded-minimizer conditions have appeared in streaming and federated learning analyses [47, 46]. Here, it ensures that the time-varying minimizer ¯t∗\ w_t^*\ and the fixed-point sequences ~t\ w_t\ are uniformly bounded. Lemma 2. Under Assumptions 1 and 2, it holds that ‖¯t∗‖≤Cκ.. \| w_t^*\|≤ C κ.. (30) Moreover, the fixed points ~t\ w_t\ satisfy, for all t≥1t≥ 1, ‖~t‖≤NCZ, where \| w_t\|≤ N\,C_Z, where CZ≜Cκ,=(DGD),Cκ,=(diffusion),Cκ,=,⪰0. C_Z casesC κ,&Z=I (DGD),\\ Cκ,&Z=M (diffusion),\\ C κ,&Z=M,\ M 0. cases (31) Furthermore, for all i,t≥1i,t≥ 1, ‖∇f¯t(~i)‖,‖∇ft(~i)‖,‖∇f¯t(¯t∗)‖≤GZ. \|∇ f_t( w_i) \|,\; \|∇ f_t( w_i) \|,\; \|∇ f_t( w_t^*) \|≤ G_Z. (32) where GZ≜2LNCZG_Z 2L N\,C_Z. The proof of Lemma 2 can be found in Appendix. We note that the condition ⪰0M 0 is not required by the algorithms or by the TE analysis; it only yields a tighter bound in (31) for diffusion. V-A Fixed-point bias To bound the TE, we first bound the bias term in (29). The following result is obtained by applying the fixed-point-to-minimizer bound of [48, App. A] to f¯t(⋅) f_t(·) and then using Lemma 2. Proposition 1. Under the conditions above, ‖~t−¯t∗‖ \| w_t- w_t^* \| ≤ηκΛZ‖∇f¯t(¯t∗)‖≤ηκΛZGZ, ≤ηκ _Z \|∇ f_t( w_t^*) \|≤ηκ _ZG_Z, (33) where ΛZ≜‖(−)†‖2=11−λ2,=(DGD),2‖(−)†‖2,=(diffusion). _Z cases\|(I-M) \|_2= 11- _2\;,\;Z=I (DGD),\\[8.53581pt] 2\|(I-M) M\|_2, =M\;(diffusion). cases (34) For diffusion, the first inequality additionally requires η≤1/(LΛZ)η≤ 1/(L _Z). The bounds in (33) show that the fixed point bias scales linearly with the step size η and depends on the condition number κ, the topology factor ΛZ _Z, and the gradient magnitude ‖∇f¯t(¯t∗)‖\|∇ f_t( w_t^*)\|, which reflects data heterogeneity across agents. In particular, in homogeneous settings where all agents observe identical losses, they share the same minimizer, and hence ‖∇f¯t(¯t∗)‖=0\|∇ f_t( w_t^*)\|=0, implying zero bias. Better network connectivity reduces ΛZ _Z; for the complete graph =1N⊤M= 1N11 , one obtains ΛZ=1 _Z=1 for DGD and ΛZ=0 _Z=0 for diffusion. V-B Fixed-point tracking error and drift We next bound the fixed-point tracking term in (29). Since t+1=Φt+1(t) w_t+1= _t+1( w_t) and ~t+1=Φt+1(~t+1) w_t+1= _t+1 ( w_t+1 ), the contraction of Φt+1(⋅) _t+1(·) from Lemma 1 yields FPTE(t+1)FPTE(t+1) =‖t+1−~t+1‖ =\| w_t+1- w_t+1\| =‖Φt+1(t)−Φt+1(~t+1)‖ =\| _t+1( w_t)- _t+1( w_t+1)\| ≤α‖t−~t+1‖≤αFPTE(t)+α‖~t+1−~t‖, ≤α\| w_t- w_t+1\|≤ (t)+α\| w_t+1- w_t\|, (35) where recall that α=(1−ημ)Eα=(1-ημ)^E. Unrolling (35) and using the same contraction argument yields FPTE(t)≤αt‖0−~1‖+∑i=1t−1αt−i‖~i+1−~i‖. (t)≤α^t\| w_0- w_1\|+ _i=1^t-1α^t-i\| w_i+1- w_i\|. (36) In (36), the first term decreases geometrically to zero as t→∞t→∞, while the second term accumulates the drift of the moving fixed-point ~t\ w_t\. Thus, controlling the FPTE reduces to controlling this drift. We next bound this drift. Lemma 3. Under Assumption 1, the fixed points ~t\ w_t\ satisfy ‖~t+1−~t‖≤1μ‖∇f¯t+1(~t+1)−∇f¯t(~t+1)‖. \| w_t+1- w_t\|≤ 1μ \|∇ f_t+1( w_t+1)-∇ f_t( w_t+1) \|. (37) The proof is given in Appendix. Lemma 3 relates the fixed-point drift to the temporal variation of the gradient of the time-weighted objective. In particular, if ∇f¯t(⋅)∇ f_t(·) changes slowly with t, then the corresponding fixed-point sequence ~t\ w_t\ cannot drift rapidly. Next, using ∇f¯t+1()−∇f¯t()=at+1(t+1)∇ft+1()+∑i=1t(ai(t+1)−ai(t))∇fi()∇ f_t+1( w)-∇ f_t( w)=a_t+1(t+1)∇ f_t+1( w)+ _i=1^t (a_i(t+1)-a_i(t) )∇ f_i( w), the gradient bound in Lemma 2 and applying the triangle inequality, (37) implies ‖~t+1−~t‖≤GZμ(at+1(t+1)+∑i=1t|ai(t+1)−ai(t)|). \| w_t+1- w_t\|≤ G_Zμ (a_t+1(t+1)+ _i=1^t|a_i(t+1)-a_i(t)| ). (38) The following identity further simplifies (38); its proof is given in the Appendix. Lemma 4. Let It≜∑i=1t(ai(t+1)−ai(t))+I_t _i=1^t (a_i(t+1)-a_i(t) )_+. Then, ∑i=1t|ai(t+1)−ai(t)|=at+1(t+1)+2It. _i=1^t|a_i(t+1)-a_i(t)|=a_t+1(t+1)+2I_t. (39) Leveraging Lemma 4, the fixed-point drift in (38) can be rewritten as ‖~t+1−~t‖≤2GZμ(at+1(t+1)+It). \| w_t+1- w_t\|≤ 2G_Zμ (a_t+1(t+1)+I_t ). (40) Moreover, if the weights are non-increasing over time, i.e., ai(t+1)≤ai(t),∀i≤ta_i(t+1)≤ a_i(t),∀ i≤ t, then It=0I_t=0, and (40) simplifies to ‖~t+1−~t‖≤2GZμat+1(t+1). \| w_t+1- w_t\|≤ 2G_Zμ\,a_t+1(t+1). (41) This property is satisfied by the uniform-shrinkage family in Section I-B; it is also satisfied by the stationary-kernel family in Section I-A whenever the kernel sequence gk\g_k\ is non-increasing. Therefore, it holds for the four canonical weighting strategies considered in Section I, whose drift bounds are summarized next. Proposition 2. Under (41), the following bounds hold. ∙ Uniform weights in (6): ‖~t+1−~t‖≤2GZμ(t+1). \| w_t+1- w_t\|≤ 2G_Zμ(t+1). (42) ∙ Exponentially discounted weights in (7): ‖~t+1−~t‖≤2GZμ1−γ1−γt+1. \| w_t+1- w_t\|≤ 2G_Zμ 1-γ1-γ^t+1. (43) ∙ Windowed-uniform weights in (8): For all t≥mt≥ m, ‖~t+1−~t‖≤2GZμm. \| w_t+1- w_t\|≤ 2G_Zμ m. (44) ∙ Windowed-discounted weights in (9): For all t≥mt≥ m, ‖~t+1−~t‖≤2GZμ1−γ1−γm. \| w_t+1- w_t\|≤ 2G_Zμ 1-γ1-γ^m. (45) Substituting these drift bounds into (36), and combining with the bias bound in (33), yields the TE guarantees discussed next. V-C Tracking error guarantees We next present the TE bounds specialized to the four canonical weighting strategies. All bounds are stated under the step size conditions of Lemma 1 and, for diffusion, the additional condition in Proposition 1. Uniform temporal weights For the uniform temporal weighting strategy (6), utilizing (42), the following holds TE(t) (t) ≤αt‖0−~1‖+2GZμ∑i=1t−1αt−i+1+ηκΛZGZ. ≤α^t\,\| w_0- w_1\|+ 2G_Zμ _i=1^t-1 α^t-ii+1+ηκ _ZG_Z. (46) The summation term in (46) admits an (1/t)O(1/t) upper bound, yielding the following theorem. Theorem 1. Define S(t)≜∑i=1t−1αt−i+1S(t) _i=1^t-1 α^t-ii+1 with α=(1−ημ)E∈(0,1)α=(1-ημ)^E∈(0,1). Under uniform weights (6), the tracking error satisfies for all t≥t0≜⌈2α1−α⌉t≥ t_0 2α1-α TE(t)≤αt‖0−~1‖+2GZμAt+ηκΛZGZ, (t)≤α^t\| w_0- w_1\|+ 2G_Zμ At+ηκ _ZG_Z, (47) where A≜maxt0S(t0),2α1−αA \t_0S(t_0), 2α1-α \. Furthermore, lim supt→∞TE(t)=ATE≤ηκΛZGZ. _t→∞TE(t)=ATE≤ηκ _ZG_Z. (48) The proof is given in Appendix. Since α∈(0,1)α∈(0,1), the first term in (47) decays geometrically, while the second term decays as (1/t)O(1/t). Thus, under uniform weighting, the FPTE contribution vanishes asymptotically, and the TE is ultimately governed solely by the fixed-point bias term, which is (η)O(η). In particular, to guarantee ATE=lim supt→∞TE(t)≤ϵATE= _t→∞TE(t)≤ε, it suffices to choose η≤ϵκΛZGZ. η≤ εκ _ZG_Z. (49) Exponentially discounted weights For the exponentially discounted temporal weighting strategy (7), utilizing (43) gives TE(t) (t) ≤αt‖0−~1‖+2GZμ∑i=1t−1αt−i1−γ1−γi+1+ηκΛZGZ. ≤α^t\| w_0- w_1\|+ 2G_Zμ _i=1^t-1α^t-i 1-γ1-γ^i+1+ηκ _ZG_Z. (50) The summation term in (50) admits a non-vanishing asymptotic bound, yielding the following theorem. Theorem 2. Define Sγ(t)≜∑i=1t−1(1−γ)αt−i1−γi+1S_γ(t) _i=1^t-1 (1-γ)α^t-i1-γ^i+1 with α=(1−ημ)E∈(0,1)α=(1-ημ)^E∈(0,1). Under discounted weights (7), the tracking error satisfies for all t≥t0≜⌈ln(1−α1+α−2γα)/ln(γ)⌉t≥ t_0 ( 1-α1+α-2γα)/ (γ) TE(t)≤αt‖0−~1‖+2GZμAγ1−γ1−γt+ηκΛZGZ, (t)≤α^t\| w_0- w_1\|+ 2G_ZμA_γ 1-γ1-γ^t+ηκ _ZG_Z, (51) where Aγ≜max(1−γt0)Sγ(t0)1−γ,2α1−αA_γ \ (1-γ^t_0)S_γ(t_0)1-γ, 2α1-α \. Furthermore, ATE≤2GZμ(1−γ)α1−α+ηκΛZGZ. ≤ 2G_Zμ (1-γ)α1-α+ηκ _ZG_Z. (52) The proof is given in Appendix. Unlike uniform weighting, exponentially discounted weighting induces a non-vanishing FPTE contribution in addition to the bias floor. This is because old samples are exponentially forgotten, and, hence, the fixed point continues to drift by an amount proportional to 1−γ1-γ (cf. (43)). As γ→1γ→ 1, this additional floor vanishes and the discounted rule approaches uniform weighting. For a target ϵ>0ε>0, suppose we choose 0<η≤ϵ/(2κΛZGZ)0<η≤ε/(2κ _ZG_Z) so that the bias term ηκΛZGZηκ _ZG_Z is at most ϵ/2ε/2. Then, from (52), it is sufficient to choose E≥ @3⌈ln(ϵ+4GZμ(1−γ))ln(1−ημ) @3⌉, E≥ @3 \! ( ε+ 4G_Zμ(1-γ) ) (1-ημ) @3 , (53) to guarantee ATE≤ϵATE≤ε. Windowed temporal weights We next consider the finite-memory windowed variants. Unlike the full-memory weightings, windowed strategies retain only a fixed number of past samples, thereby reducing memory and computational requirements. This finite-memory constraint, however, generally induces a non-vanishing FPTE. We first state the result for windowed-discounted weights; the windowed-uniform case is then recovered as the limiting case γ→1γ→ 1. Using the drift bound in (45), together with the geometric sum ∑i=1t−1αt−i=α(1−αt−1)/(1−α) _i=1^t-1α^t-i=α(1-α^t-1)/(1-α), we obtain the following bound. Theorem 3. Under windowed-discounted weights (9), for all t≥mt≥ m, the tracking error satisfies TE(t) (t) ≤αt‖0−~1‖+2GZμ1−γ1−γmα(1−αt−1)1−α ≤α^t\| w_0- w_1\|+ 2G_Zμ 1-γ1-γ^m α(1-α^t-1)1-α +ηκΛZGZ. +ηκ _ZG_Z. (54) Consequently, ATE≤2GZμ1−γ1−γmα1−α+ηκΛZGZ. ≤ 2G_Zμ 1-γ1-γ^m α1-α+ηκ _ZG_Z. (55) For windowed-discounted weights, the FPTE contribution in (55) is controlled by the effective-memory factor (1−γ)/(1−γm)(1-γ)/(1-γ^m). As m→∞m→∞, this factor approaches 1−γ1-γ, matching the bound in (52) for full-memory exponentially discounted weighting. For a target ϵ>0ε>0, suppose η≤ϵ/(2κΛZGZ)η≤ε/(2κ _ZG_Z). Then, from (55), it is sufficient to choose E≥ @3⌈ln(ϵ+4GZμ⋅1−γ1−γm)ln(1−ημ) @3⌉, E≥ @3 \! ( ε+ 4G_Zμ· 1-γ1-γ^m ) (1-ημ) @3 , (56) to guarantee ATE≤ϵATE≤ε. Since limγ→1(1−γ)/(1−γm)=1/m _γ→ 1(1-γ)/(1-γ^m)=1/m, the windowed-uniform guarantees follow directly as a special case. Corollary 1. Under windowed-uniform weights (8), for all t≥mt≥ m, TE(t)≤αt‖0−~1‖+2GZμmα(1−αt−1)1−α+ηκΛZGZ. (t)≤α^t\| w_0- w_1\|+ 2G_Zμ m α(1-α^t-1)1-α+ηκ _ZG_Z. (57) Consequently, ATE≤2GZμmα1−α+ηκΛZGZ. ≤ 2G_Zμ m α1-α+ηκ _ZG_Z. (58) Moreover, for a target ϵ>0ε>0, if 0<η≤ϵ/(2κΛZGZ)0<η≤ε/(2κ _ZG_Z), it is sufficient to choose E≥ @3⌈ln(ϵ+4GZμm)ln(1−ημ) @3⌉ E≥ @3 \! ( ε+ 4G_Zμ m ) (1-ημ) @3 (59) to guarantee ATE≤ϵATE≤ε. For fixed η and E, the finite-memory FPTE contribution in (58) has a 1/m1/m prefactor, whereas the overall ATE also includes the fixed-point bias term. Hence, increasing the window length reduces the additional finite-memory contribution. In the limit m→∞m→∞, this contribution vanishes, and the bound reduces to the ATE bound obtained under full-memory uniform weighting in (48). The iteration complexity needed to achieve ATE≤ϵATE≤ε is summarized next. Remark 1. Under uniform weighting, the FPTE contribution vanishes for any E≥1E≥ 1, and the ATE in (48) is controlled solely by the bias term. Hence, the condition in (49) shows that the ATE can be made arbitrarily small by reducing the step size η. In contrast, for the discounted and windowed strategies, the ATE contains a non-vanishing FPTE floor in addition to the bias term. The sufficient conditions in (53), (56), and (59) reveal a tradeoff between the step size η and the number of decentralized iterations per time-step E. For fixed η, the sufficient threshold on E for achieving an FPTE floor of order ϵε scales as Θ(ln(1/ϵ)) ( (1/ε)). However, achieving an arbitrarily small total ATE also requires reducing the bias term, which motivates choosing η=Θ(ϵ)η= (ε). In this case, −ln(1−ημ)=Θ(ϵ)- (1-ημ)= (ε), and the sufficient per-step iteration budgets in (53)–(56) scale as Θ(ln(1/ϵ)/ϵ) ( (1/ε)/ε). VI Numerical Results Figure 2: Diffusion with uniform temporal weights: RMS TE vs. time index for number of iterations per time-step E. Figure 3: Diffusion with exponentially discounted temporal weights, γ=0.7γ=0.7: RMS TE vs. time index for number of iterations per time-step E. We now present numerical experiments illustrating the tracking behavior predicted by the analysis. While the derived bounds are not expected to be tight in general, the experiments are intended to show that they are meaningful and capture the qualitative behavior of the considered decentralized system. At time t, agent n∈1,…,Nn∈\1,…,N\ incurs the quadratic loss ℓn,t()=12(−n,t)⊤n,t(−n,t), _n,t(w)= 12(w-c_n,t) A_n,t(w-c_n,t), (60) where n,t∈ℝdc_n,t ^d models the streaming data process and n,t∈ℝd×dA_n,t ^d× d is positive definite. We adopt quadratic losses because they provide a controlled and interpretable setting and admit a closed-form expression for the time-varying minimizer. This choice is appropriate because our objective is not to benchmark a particular learning architecture or dataset, but to study the qualitative implications of the theoretical analysis. We generate n,t=diag(λn,t1,…,λn,td)A_n,t=diag( _n,t^1,…, _n,t^d), where λn,tj∼Unif[μ,L] _n,t^j [μ,L] independently across n, t, and j. Hence, ℓn,t _n,t in (60) is μ-strongly convex and L-smooth. For this quadratic model, the temporally weighted global objective F¯t()=∑i=1tai(t)Fi() F_t(w)= _i=1^ta_i(t)F_i(w) admits the closed-form minimizer ¯t∗=(∑i=1tai(t)∑n=1Nn,i)−1(∑i=1tai(t)∑n=1Nn,in,i) w_t^*= ( _i=1^ta_i(t) _n=1^NA_n,i )^-1 ( _i=1^ta_i(t) _n=1^NA_n,ic_n,i ), which allows exact evaluation of the TE. The temporal evolution is generated through a bounded Gaussian random walk. For each coordinate j=1,…,dj=1,…,d, [n,t+1]j=max−Cmax,min([n,t]j+[n,t+1]j,Cmax)[c_n,t+1]_j= \! \-C_ , \! ([c_n,t]_j+[z_n,t+1]_j,C_ ) \, where n,t∼(,σ2)z_n,t (0,σ^2I) are independent and identically distributed across agents and time. We initialize n,0c_n,0 uniformly over [−Cmax,Cmax]d[-C_ ,C_ ]^d and set n,0=w_n,0=0 for all n. In all experiments, we use N=50N=50 agents, dimension d=100d=100, step size η=0.1η=0.1, Cmax=10C_ =10, σ2=1σ^2=1, μ=0.01μ=0.01, and L=0.1L=0.1. All the experiments are run for T=1000T=1000 time-steps. Agents are placed uniformly at random in a disk of radius one, and an undirected random geometric graph is formed by connecting agents within distance rth=0.9r_th=0.9, increased if needed to ensure connectivity. Given the connected graph, we construct the Metropolis-Hastings mixing matrix []ij=11+maxdeg(i),deg(j),(i,j)∈ℰ,i≠j,1−∑j≠i[]ij,i=j,0,otherwise, [M]_ij= cases 11+ \ (i), (j)\,&(i,j) ,\ i≠ j,\\[4.30554pt] 1- _j≠ i[M]_ij,&i=j,\\ 0,&otherwise, cases (61) where deg(i) (i) is the degree of agent i. This construction yields a symmetric doubly stochastic mixing matrix satisfying the assumptions in Section I. All curves report the root-mean-squared (RMS) TE 1R∑r=1RTEr(t)2, 1R _r=1^RTE_r(t)^2, averaged over R=100R=100 Monte Carlo runs, where TEr(t)TE_r(t) is computed according to (20). The communication graph is generated once and kept fixed across all Monte Carlo runs; randomness across runs comes from the streaming data process and loss parameters. Figures 2 and 3 compare different numbers of decentralized diffusion iterations per time-step E for uniform and exponentially discounted temporal weights, respectively. Under uniform weighting, the influence of each new sample decreases with time, leading to a decaying fixed-point drift and a vanishing FPTE. Increasing E accelerates the transient decay through the smaller contraction factor α=(1−ημ)Eα=(1-ημ)^E. The TE therefore decreases steadily before approaching the bias-dominated regime predicted by Theorem 1. By contrast, under discounted weighting with γ=0.7γ=0.7, the TE settles to a substantially larger steady-state level, consistent with Theorem 2. This behavior arises because old samples are exponentially forgotten, so the fixed-point drift does not vanish, and the TE contains a non-zero FPTE contribution in addition to the data-heterogeneity-induced bias. Larger E lowers this floor by improving tracking of the moving fixed point. Figure 4: Diffusion with discounted weights: RMS TE vs. time index for different discount factors γ, with E=5E=5. The uniform-weight curve is included as a benchmark. Figure 4 studies the effect of the discount factor γ for diffusion with fixed E=5E=5. Smaller γ places more emphasis on recent samples, making the effective objective more adaptive but also more variable; this leads to a larger asymptotic TE, consistent with Theorem 2. As γ increases, however, the effective memory grows, and the TE floor decreases. In the limit γ→1γ→ 1, discounted weighting approaches uniform weighting, explaining why the curve for γ=0.99γ=0.99 closely follows the uniform-weight curve. Moreover, the continued decay of the uniform-weight curve is consistent with Theorem 1: after the geometrically decaying initialization transient, the FPTE contribution decreases as (1/t)O(1/t), until the overall TE becomes limited by the constant-step-size bias floor. Figure 5: DGD with windowed-uniform temporal weights: RMS TE vs. time index for different window lengths m, with E=5E=5. The case m=∞m=∞ corresponds to standard uniform weighting. Figure 6: DGD with windowed-discounted temporal weights, γ=0.7γ=0.7: RMS TE vs. time index for different window lengths m, with E=5E=5. The case m=∞m=∞ corresponds to standard discounted weighting. Figures 5 and 6 illustrate finite-memory windowing with DGD. For windowed-uniform weights, increasing the window length m lowers the TE floor, in agreement with the 1/m1/m dependence in Corollary 1. In contrast to the fixed-window curves, the full-memory uniform curve, corresponding to m=∞m=∞, continues to decrease. This behavior is consistent with Theorem 1, which gives an (1/t)O(1/t) FPTE contribution under full-memory uniform weighting. For windowed-discounted weights, increasing m improves performance only up to the effective memory induced by the discount factor. Notably, due to exponential forgetting, even moderate window lengths, e.g., m>5m>5, nearly match the full-memory discounted curve, consistent with the factor (1−γ)/(1−γm)(1-γ)/(1-γ^m) in (55). VII Conclusion We investigated decentralized optimization with streaming data through a temporal-weighting formulation. For both DGD and diffusion, we developed a unified analysis that yields explicit tracking guarantees by decomposing the tracking error into a fixed-point tracking component and a network-induced bias term. We also introduced a structured class of kernel-based temporal weights, encompassing uniform and exponentially discounted rules together with memory-efficient windowed variants. Specializing the bounds, we showed that uniform weighting yields a vanishing fixed-point tracking contribution of order (1/t)O(1/t), leaving only the decentralization-induced bias floor, whereas discounted and windowed schemes generally exhibit non-vanishing error floors governed by the discount factor and the window length, respectively. The resulting bounds explicitly show how temporal weighting, network topology, and the per-time-step iteration budget jointly determine the attainable asymptotic tracking performance. Numerical experiments corroborate the qualitative trends predicted by the theory. Lemma 5 (Mean Hessian Theorem [48]). Let g:ℝNd→ℝg:R^Nd be differentiable (but not necessarily twice differentiable), μ-strongly convex, and L-smooth. Then, for any ,∈ℝNdx,y ^Nd, there exists a symmetric matrix ,∈ℝNd×NdA_x,y ^Nd× Nd (dependent on x and y) such that μ⪯,⪯L, _x,y LI, (62) ∇g()−∇g()=,(−). ∇ g(y)-∇ g(x)=A_x,y(y-x). (63) The proof of Lemma 5 can be found in [48]. Lemma 6. Let 0<α<10<α<1 and let btt≥0⊂ℝ\b_t\_t≥ 0 be a sequence that satisfies bt→b∗b_t→ b^* as t→∞t→∞. Define the sequence xtt≥0\x_t\_t≥ 0 by xt+1=αxt+bt,x0∈ℝ. x_t+1=α x_t+b_t, x_0 . (64) Then, xt\x_t\ is also a convergent sequence which satisfies limt→∞xt=b∗1−α. _t→∞x_t= b^*1-α\,. Proof. Since bt→b∗b_t→ b^*, we express btb_t as bt=b∗+etb_t=b^*+e_t with et≜bt−b∗→0e_t b_t-b^*→ 0. Subtracting the candidate limit b∗1−α b^*1-α from both sides of (64), letting δt=xt−b∗1−α _t=x_t- b^*1-α gives δt+1=αδt+et _t+1=α _t+e_t. Using induction on t, we further obtain δt _t =αtδ0+∑k=0t−1αt−1−kek. =α^t _0+ _k=0^t-1α^t-1-ke_k. (65) Next, we will show that for every ε>0 >0 there exists a τ such that |δt|<ε,∀t≥τ| _t|< ,\ ∀ t≥τ, which implies δt→0 _t→ 0, hence xt→b∗1−αx_t→ b^*1-α. Let ε>0 >0 be given. Since et→0e_t→ 0, there exists N such that |et|≤(1−α)ε/2|e_t|≤(1-α) /2 ∀t≥N∀ t≥ N, and, since every convergent sequence is bounded, there exists ℰ>0E>0 such that |et|≤ℰ,∀t|e_t| ,\;∀ t. Under such N, for t≥Nt≥ N, we rewrite δt _t as δt=αtδ0+∑k=0N−1αt−1−kek⏟Ht+∑k=Nt−1αt−1−kek⏟Tt. _t=α^t _0+ _k=0^N-1α^t-1-ke_k_H_t\;+\; _k=N^t-1α^t-1-ke_k_T_t. Since |ek|≤(1−α)ε/2,∀k≥N|e_k|≤(1-α) /2\,,∀ k≥ N, we bound |Tt||T_t| as |Tt|≤(1−α)ε2∑k=Nt−1αt−1−k≤(1−α)ε2∑j=0∞αj=ε2. |T_t|≤(1-α) 2 _k=N^t-1α^t-1-k≤(1-α) 2 _j=0^∞α^j= 2. Since |et|≤ℰ,∀t|e_t| ,∀ t, it follows that |Ht|≤∑k=0N−1αt−1−k|ek|≤ℰ∑k=0N−1αt−1−k≤ℰ1−ααt−N. |H_t|≤ _k=0^N-1α^t-1-k|e_k| _k=0^N-1α^t-1-k≤ E1-α\,α^t-N. Therefore, for all t≥Nt≥ N, it holds that |δt| | _t| ≤αt|δ0|+ℰ1−ααt−N+ε2. ≤α^t| _0|+ \ E1-α\,α^t-N+ 2. (66) Since αt→0α^t→ 0, there exists some τ≥Nτ≥ N such that αt|δ0|<ε/4α^t| _0|< /4 and ℰ1−ααt−N<ε/4 \ E1-α\,α^t-N< /4, for all t≥τt≥τ, hence |δt|<ε,∀t≥τ| _t|< ,\ ∀ t≥τ. Hence δt→0 _t→ 0, which proves the lemma. ∎ Proof of Lemma 3. Fix any t≥1t≥ 1. From the definition of ϕt(⋅) _t(·) in (22) and the fixed-point relation (28), we have (−¯)~t+η¯∇f¯t(~t)=, (I- M) w_t+η Z∇ f_t( w_t)=0, (67) where ¯=Nd Z=I_Nd for DGD and ¯=¯=⊗d Z= M=M _d for diffusion. For notational convenience, define t≜~t+1−~t d_t w_t+1- w_t. ∙ DGD (¯= Z=I): Writing (67) at times t and t+1t+1 and subtracting, we obtain: (−¯)t+η(∇f¯t+1(~t+1)−∇f¯t(~t))=. (I- M) d_t+η (∇ f_t+1( w_t+1)-∇ f_t( w_t) )=0. (68) Applying Lemma 5 to f¯t(⋅) f_t(·) at the points ~t w_t and ~t+1 w_t+1, there exists a symmetric matrix A with μ⪯L LI such that ∇f¯t(~t)−∇f¯t(~t+1)=(~t−~t+1). ∇ f_t( w_t)-∇ f_t( w_t+1)=A( w_t- w_t+1). (69) Substituting (69) into (68) gives [(−¯)+η]t=−η(∇f¯t+1(~t+1)−∇f¯t(~t+1)). [(I- M)+ ] d_t=-η (∇ f_t+1( w_t+1)-∇ f_t( w_t+1) ). Since the eigenvalues of ¯=⊗d M=M _d are those of M, each repeated d times, and λmax()=1 _ (M)=1, it follows that −¯⪰0I- M 0. Moreover, since ⪰μA , we have λmin((−¯)+η)≥ημ _ ((I- M)+ )≥ημ, and therefore it holds that ‖t‖≤ημ‖∇f¯t+1(~t+1)−∇f¯t(~t+1)‖ \| d_t\|≤ ημ\, \|∇ f_t+1( w_t+1)-∇ f_t( w_t+1) \| which yields (37) for any η>0η>0. ∙ Diffusion (¯=¯ Z= M): Specializing (67) yields (−¯)~t+η¯∇f¯t(~t)=. (I- M) w_t+η Z∇ f_t( w_t)=0. Subtracting the relations at t and t+1t+1 and rearranging yields t=¯t−η¯(∇f¯t+1(~t+1)−∇f¯t(~t)). _t= M d_t-η M (∇ f_t+1( w_t+1)-∇ f_t( w_t) ). (70) Next, applying Lemma 5 and utilizing (69), (70) becomes t=¯((−η)t−η(∇f¯t+1(~t+1)−∇f¯t(~t+1))). d_t= M ((I- ) d_t-η (∇ f_t+1( w_t+1)-∇ f_t( w_t+1) ) ). Taking norms and using ‖¯‖2=‖⊗d‖2=‖2‖d‖2=1\| M\|_2=\|M _d\|_2=\|M\|_2\|I_d\|_2=1 (since M is symmetric and doubly stochastic) gives ‖t‖≤‖−η‖2‖t‖+η‖∇f¯t+1(~t+1)−∇f¯t(~t+1)‖. \| d_t\|≤\|I- \|_2\,\| d_t\|+η \|∇ f_t+1( w_t+1)-∇ f_t( w_t+1) \|. Next, it can be shown that under 0<η≤2/(L+μ)0<η≤ 2/(L+μ), we have ‖−η‖2=max|1−ημ|,|1−ηL|≤1−ημ\|I- \|_2= \|1-ημ|,|1-η L|\≤ 1-ημ, so ημ‖t‖≤η‖∇f¯t+1(~t+1)−∇f¯t(~t+1)‖, ημ\,\| d_t\|≤η \|∇ f_t+1( w_t+1)-∇ f_t( w_t+1) \|, which again yields (37). ∎ Proof of Lemma 4. For notational convenience, define Δi(t)≜ai(t+1)−ai(t) _i(t) a_i(t+1)-a_i(t), for i=1,…,t.i=1,…,t. Then, we have ∑i=1tΔi(t) _i=1^t _i(t) =∑i=1tai(t+1)−∑i=1tai(t) = _i=1^ta_i(t+1)- _i=1^ta_i(t) =(1−at+1(t+1))−1=−at+1(t+1). = (1-a_t+1(t+1) )-1=-a_t+1(t+1). (71) Next, we can express Δi(t)=(Δi(t))+−(Δi(t))− _i(t)=( _i(t))_+-( _i(t))_-. Summing over i=1,…,ti=1,…,t yields ∑i=1t(Δi(t))+−∑i=1t(Δi(t))−=−at+1(t+1), _i=1^t( _i(t))_+- _i=1^t( _i(t))_-=-a_t+1(t+1), where the equality follows from (71). Hence, ∑i=1t(Δi(t))−=∑i=1t(Δi(t))++at+1(t+1)=It+at+1(t+1), _i=1^t( _i(t))_-= _i=1^t( _i(t))_++a_t+1(t+1)=I_t+a_t+1(t+1), since It=∑i=1t(Δi(t))+I_t= _i=1^t( _i(t))_+. Leveraging |Δi(t)|=(Δi(t))++(Δi(t))−| _i(t)|=( _i(t))_++( _i(t))_-, we have ∑i=1t|Δi(t)| _i=1^t| _i(t)| =∑i=1t((Δi(t))++(Δi(t))−) = _i=1^t (( _i(t))_++( _i(t))_- ) =It+(It+at+1(t+1))=at+1(t+1)+2It, =I_t+ (I_t+a_t+1(t+1) )=a_t+1(t+1)+2I_t, which proves (39). ∎ Proof of Lemma 2. We prove the three claims in (30)–(32) as follows: ∙ Bound on the global minimizer ¯t∗ w_t^*: Since F¯t(⋅) F_t(·) is μ-strongly convex (Assumption 1) with minimizer ¯t∗ w_t^*, we have, for any ∈ℝdw ^d, F¯t()≥F¯t(¯t∗)+μ2‖−¯t∗‖2. F_t(w)≥ F_t( w_t^*)+ μ2 \|w- w_t^* \|^2. Specializing the above inequality at =w=0, we obtain: ‖¯t∗‖2≤2μ(F¯t()−F¯t(¯t∗)). \| w_t^* \|^2≤ 2μ ( F_t(0)- F_t( w_t^*) ). (72) Using the definition of F¯t()=∑i=1tai(t)Fi() F_t(w)= _i=1^ta_i(t)F_i(w) and Fi()=1N∑n=1Nℓn,i()F_i(w)= 1N _n=1^N _n,i(w), we have F¯t()−F¯t(¯t∗) F_t(0)- F_t( w_t^*) =∑i=1tai(t)1N∑n=1N(ℓn,i()−ℓn,i(¯t∗)) = _i=1^ta_i(t) 1N _n=1^N ( _n,i(0)- _n,i( w_t^*) ) ≤∑i=1tai(t)1N∑n=1N(ℓn,i()−ℓn,i(n,i∗)), ≤ _i=1^ta_i(t) 1N _n=1^N ( _n,i(0)- _n,i(w_n,i^*) ), where the inequality follows since n,i∗=argmin∈ℝdℓn,i()w_n,i^*= _w ^d _n,i(w). Furthermore, utilizing L-smoothness (Assumption 1) and optimality of n,i∗w_n,i^*, it follows that ℓn,i()−ℓn,i(n,i∗)≤L2‖−n,i∗‖2≤L2C2, _n,i(0)- _n,i(w_n,i^*)≤ L2\|0-w_n,i^*\|^2≤ L2C^2, where the second inequality invokes Assumption 2. Next, using ∑i=1tai(t)=1 _i=1^ta_i(t)=1 gives F¯t()−F¯t(¯t∗)≤L2C2. F_t(0)- F_t( w_t^*)≤ L2C^2. (73) Finally, substituting (73) into (72) yields ‖¯t∗‖≤CL/μ=Cκ\| w_t^*\|≤ C L/μ=C κ, proving (30). ∙ Bound on the fixed point ~t w_t: – (DGD: =Z=I). From the definition of ϕt(⋅) _t(·) in (22) and the fixed-point relation (28), for DGD it holds that (−¯)~t+η∇f¯t(~t)=. (I- M) w_t+η∇ f_t( w_t)=0. (74) Utilizing the μ-strong convexity of f¯t(⋅) f_t(·) (Assumption 1), (26) can be specialized as f¯t()≥f¯t(~t)−∇f¯t(~t)⊤~t+μ2‖~t‖2 f_t(0)≥ f_t( w_t)-∇ f_t( w_t) w_t+ μ2 \| w_t \|^2 Next, using (74) to substitute ∇f¯t(~t)=−(1/η)(−¯)~t∇ f_t( w_t)=-(1/η)(I- M) w_t further gives f¯t()≥f¯t(~t)+1η~t⊤(−¯)~t+μ2‖~t‖2. f_t(0)≥ f_t( w_t)+ 1η w_t (I- M) w_t+ μ2\| w_t\|^2. (75) Since −¯⪰0I- M 0, the middle term is nonnegative. Hence, ‖~t‖2≤2μ(f¯t()−f¯t(~t)). \| w_t\|^2≤ 2μ ( f_t(0)- f_t( w_t) ). (76) Next, using the definition of f¯t(⋅) f_t(·) and ~t=[[~t]1⊤⋯[~t]N⊤]⊤ w_t= bmatrix[ w_t]_1 &·s&[ w_t]_N bmatrix , we have f¯t()−f¯t(~t) f_t(0)- f_t( w_t) =∑i=1tai(t)∑n=1N(ℓn,i()−ℓn,i([~t]n)) = _i=1^ta_i(t) _n=1^N( _n,i(0)- _n,i([ w_t]_n)) ≤(a)∑i=1tai(t)∑n=1N(ℓn,i()−ℓn,i(n,i∗)) (a)≤ _i=1^ta_i(t) _n=1^N( _n,i(0)- _n,i(w_n,i^*)) ≤(b)∑i=1tai(t)∑n=1NL2‖n,i∗‖2≤(c)NL2C2, (b)≤\ _i=1^ta_i(t) _n=1^N L2\|w_n,i^*\|^2 (c)≤ NL2C^2, (77) where (a)(a) follows since n,i∗w_n,i^* minimizes ℓn,i(⋅) _n,i(·), (b)(b) follows from L-smoothness (Assumption 1), and (c)(c) invokes Assumption 2 along with the fact that ∑i=1tai(t)=1 _i=1^ta_i(t)=1. Substituting (77) into (76) gives ‖~t‖≤CNLμ=NCZ\| w_t\|≤ C NLμ= N\,C_Z, which is (31) with CZ=CκC_Z=C κ and holds for all t≥1t≥ 1. – (Diffusion: =Z=M). From (22) and (28), the fixed point satisfies ~t=ϕt(~t) w_t= _t( w_t) with ϕt()=¯−η¯∇f¯t() _t( w)= M w-η M∇ f_t( w) for diffusion. Hence, ‖~t‖ \| w_t\| =‖ϕt(~t)‖ =\| _t( w_t)\| ≤(a)‖ϕt(~t)−ϕt()‖+‖ϕt()‖≤(b)ρ‖~t‖+‖ϕt()‖, (a)≤\| _t( w_t)- _t(0)\|+\| _t(0)\| (b)≤ρ\| w_t\|+\| _t(0)\|, where (a)(a) follows from adding and subtracting ϕt() _t(0) and using the triangle inequality, and (b)(b) invokes Lemma 1, whereby ϕt(⋅) _t(·) is a contraction with factor ρ∈(0,1)ρ∈(0,1). Therefore, ‖~t‖≤11−ρ‖ϕt()‖. \| w_t\|≤ 11-ρ\,\| _t(0)\|. (78) Next, ϕt()=−η¯∇f¯t() _t(0)=-η M∇ f_t(0), and since ‖¯‖2=1\| M\|_2=1 (for symmetric doubly stochastic ¯ M), we have ‖ϕt()‖≤η‖∇f¯t()‖. \| _t(0)\|≤η\|∇ f_t(0)\|. Moreover, from (13), the n-th block of ∇f¯t()∇ f_t(0) equals ∑i=1tai(t)∇ℓn,i() _i=1^ta_i(t)∇ _n,i(0). By L-smoothness (Assumption 1) and the optimality condition ∇ℓn,i(n,i∗)=∇ _n,i(w_n,i^*)=0, ‖∇ℓn,i()‖=‖∇ℓn,i()−∇ℓn,i(n,i∗)‖≤L‖−n,i∗‖≤LC, \|∇ _n,i(0)\|=\|∇ _n,i(0)-∇ _n,i(w_n,i^*)\|≤ L\|0-w_n,i^*\|≤ LC, where the last inequality utilizes Assumption 2. Therefore, ‖∇f¯t()‖2=∑n=1N‖∑i=1tai(t)∇ℓn,i()‖2≤∑n=1N(LC)2=NL2C2, \|∇ f_t(0)\|^2= _n=1^N \| _i=1^ta_i(t)∇ _n,i(0) \|^2≤ _n=1^N(LC)^2=NL^2C^2, where the inequality follows from Jensen’s inequality and ∑i=1tai(t)=1 _i=1^ta_i(t)=1, yielding ‖∇f¯t()‖≤NLC\|∇ f_t(0)\|≤ N\,LC. Substituting into (78) gives ‖~t‖≤η1−ρNLC\| w_t\|≤ η1-ρ N\,LC. Finally, under the step size range 0<η≤2/(L+μ)0<η≤ 2/(L+μ), we have ρ=1−ημρ=1-ημ (cf. Lemma 1), and therefore, for all t≥1t≥ 1, ‖~t‖≤CNκ\| w_t\|≤ C N\,κ, which is (31) for =Z=M. – (Sharper diffusion bound when ⪰0M 0). If, in addition, ⪰0M 0, the diffusion fixed-point satisfies (−¯)~t+η¯∇f¯t(~t)=. (I- M) w_t+η M∇ f_t( w_t)=0. (79) Define the orthogonal projectors Pℛ(¯)≜¯¯†P_R( M) M\, M and P(¯)≜−¯¯†P_N( M) - M\, M , where ¯† M is the Moore–Penrose pseudoinverse of ¯ M. Pre-multiplying (79) by P(¯)P_N( M) yields P(¯)~t=, P_N( M) w_t=0, where we leverage the facts that P(¯)¯=(−¯¯†)¯=¯−¯¯†¯=P_N( M) M=(I- M\, M ) M= M- M\, M M=0 and P(¯)(−¯)=P(¯)−P(¯)¯=P(¯)P_N( M)(I- M)=P_N( M)-P_N( M) M=P_N( M). Therefore, ~t∈ℛ(¯) w_t ( M). Hence, there exists t∈ℝNd y_t ^Nd such that ~t=¯t. w_t= M y_t. (80) Next, pre-multiply (79) by t⊤ y_t to obtain t⊤(−¯)~t+ηt⊤¯∇f¯t(~t)=0. y_t (I- M) w_t+η\, y_t M∇ f_t( w_t)=0. Since ¯ M is symmetric, t⊤¯=(¯t)⊤=~t⊤ y_t M=( M y_t) = w_t , we further obtain ∇f¯t(~t)⊤~t=−1ηt⊤(−¯)~t=−1ηt⊤(−¯)¯t, ∇ f_t( w_t) w_t=- 1η\, y_t (I- M) w_t=- 1η\, y_t (I- M) M y_t, (81) where the last equality uses (80). Since ⪰0M 0, ¯ M is also positive semidefinite and its eigenvalues are those of M. Hence, since λ(¯)⊂[0,1]λ( M)⊂[0,1], the matrix (−¯)¯(I- M) M is positive semidefinite (its eigenvalues are λ(1−λ)≥0λ(1-λ)≥ 0), and therefore, −∇f¯t(~t)⊤~t=1ηt⊤(−¯)¯t≥0. -∇ f_t( w_t) w_t= 1η\, y_t (I- M) M y_t≥ 0. (82) Next, utilizing the μ-strong convexity of f¯t(⋅) f_t(·) (Assumption 1), (26) can be specialized as f¯t()≥f¯t(~t)−∇f¯t(~t)⊤~t+μ2‖~t‖2≥f¯t(~t)+μ2‖~t‖2, f_t(0)≥ f_t( w_t)-∇ f_t( w_t) w_t+ μ2\| w_t\|^2≥ f_t( w_t)+ μ2\| w_t\|^2, where the last inequality uses (82). Rearranging yields ‖~t‖2≤2μ(f¯t()−f¯t(~t)), \| w_t\|^2≤ 2μ ( f_t(0)- f_t( w_t) ), which is identical to (76). Thus, following the same steps as in (76)–(77) yields the same bound as that obtained for DGD: ‖~t‖≤CNLμ=NCZ\| w_t\|≤ C NLμ= N\,C_Z, which is (31) with CZ=CκC_Z=C κ. ∙ Gradient Bounds ‖∇f¯t(~i)‖\|∇ f_t( w_i)\| and ‖∇ft(~i)‖\|∇ f_t( w_i)\|: We begin by recalling the μ-strong convexity of f¯t(⋅) f_t(·) under Assumption 1. Let ¯t∗=argmin∈ℝNdf¯t() m_t^*= _ w ^Nd f_t( w) denote the minimizer of f¯t(⋅) f_t(·). Next, since f¯t()=∑n=1N∑i=1tai(t)ℓn,i([]n) f_t( w)= _n=1^N _i=1^ta_i(t) _n,i([ w]_n) is block-separable, each d-dimensional block [¯t∗]n[ m_t^*]_n minimizes the function ∑i=1tai(t)ℓn,i() _i=1^ta_i(t) _n,i(w) with ∈ℝdw ^d. As a result, by using the same argument used to bound ¯t∗ w_t^* in (72)–(73), it is easy to verify that ‖[¯t∗]n‖≤Cκ \|[ m_t^*]_n \|≤ C κ, and hence ‖¯t∗‖≤NCZ. \| m_t^*\|≤ N\,C_Z. (83) Next, L-smoothness (Assumption 1) of f¯t(⋅) f_t(·) and the optimality condition ∇f¯t(¯t∗)=∇ f_t( m_t^*)=0 yields, for any i,t≥1i,t≥ 1, ‖∇f¯t(~i)‖ \|∇ f_t( w_i)\| =‖∇f¯t(~i)−∇f¯t(¯t∗)‖ =\|∇ f_t( w_i)-∇ f_t( m_t^*)\| ≤L‖~i−¯t∗‖≤(a)L(‖~i‖+‖¯t∗‖)≤(b)2LNCZ, ≤L\| w_i- m_t^*\| (a)≤L (\| w_i\|+\| m_t^*\| ) (b)≤2L N\,C_Z, where (a)(a) invokes the triangle inequality and (b)(b) uses (83) and ‖~t‖≤NCZ\| w_t\|≤ N\,C_Z. This proves the first inequality in (32) with GZ=2LNCZG_Z=2L NC_Z. Let t∗=argminft() m_t^*= _ wf_t( w). Since ft()=∑n=1Nℓn,t([]n)f_t( w)= _n=1^N _n,t([ w]_n) is block-wise separable, it follows that t∗=[(1,t∗)⊤⋯(N,t∗)⊤]⊤ m_t^*= bmatrix(w_1,t^*) ·s(w_N,t^*) bmatrix , hence ‖t∗‖≤NC≤NCZ\| m_t^*\|≤ NC≤ NC_Z. Using L-smoothness (Assumption 1) of ft(⋅)f_t(·) and ∇ft(t∗)=∇ f_t( m_t^*)=0 yields ‖∇ft(~i)‖≤L‖~i−t∗‖≤L(‖~i‖+‖t∗‖)≤2LNCZ, \|∇ f_t( w_i)\|≤ L\| w_i- m_t^*\|≤ L(\| w_i\|+\| m_t^*\|)≤ 2L NC_Z, for any i,t≥1i,t≥ 1, which proves the second inequality in (32). Finally, since ¯t∗=N⊗¯t∗ w_t^*= 1_N w_t^*, (30) implies ‖¯t∗‖=‖N⊗¯t∗‖=N‖¯t∗‖≤CNκ≤NCZ\| w_t^*\|=\| 1_N w_t^*\|= N\,\| w_t^*\|≤ C Nκ\,≤ N\,C_Z. Using again the L-smoothness of f¯t(⋅) f_t(·) and the optimality condition ∇f¯t(¯t∗)=∇ f_t( m_t^*)=0, for all t≥1t≥ 1, we have ‖∇f¯t(¯t∗)‖ \|∇ f_t( w_t^*)\| =‖∇f¯t(¯t∗)−∇f¯t(¯t∗)‖ =\|∇ f_t( w_t^*)-∇ f_t( m_t^*)\| ≤L‖¯t∗−¯t∗‖≤L(‖¯t∗‖+‖¯t∗‖)≤2LNCZ. ≤L\| w_t^*- m_t^*\|≤L (\| w_t^*\|+\| m_t^*\| )≤2L N\,C_Z. Utilizing the definition of GZG_Z yields the desired bound. ∎ Proof of Theorem 1. We first show that for all t≥t0t≥ t_0 it holds that S(t)≤At. S(t)≤ At. (84) Note that we can express S(t+1)S(t+1) as S(t+1) S(t+1) =∑i=1tαt+1−i+1=αt+1+αS(t). = _i=1^t α^t+1-ii+1= αt+1+α S(t). (85) By the definition of A, we have A≥t0S(t0)A≥ t_0S(t_0), hence it directly holds that S(t0)≤At0S(t_0)≤ At_0. Next, as induction hypothesis assume that S(t)≤AtS(t)≤ At for some t≥t0=⌈2α1−α⌉t≥ t_0= 2α1-α . Then, from (85), S(t+1)S(t+1) can be upper bounded as S(t+1)≤αt+1+αAtS(t+1)≤ αt+1+α At. To complete the argument, it is sufficient to show that the right-hand side above is at most At+1 At+1, which is equivalent to showing that A(1−α−αt)≥α. A (1-α- αt )≥α. Since t≥t0≥2α/(1−α)t≥ t_0≥ 2α/(1-α), it follows that 1−α−α/t≥(1−α)/21-α-α/t≥(1-α)/2. Thus, the desired inequality holds whenever A≥2α/(1−α)A≥ 2α/(1-α), which is true by definition of A. Therefore, it follows by induction that (84) holds for all t≥t0t≥ t_0. Leveraging this bound in (46) yields the desired TE bound (47). Finally, taking lim supt→∞ _t→∞ in (47) gives the stated ATE bound, completing the proof. ∎ Proof of Theorem 2. We first show that, for all t≥t0t≥ t_0, Sγ(t)≤Aγ1−γ1−γt. S_γ(t)≤ A_γ 1-γ1-γ^t. (86) Note that Sγ(t+1)=∑i=1t(1−γ)αt+1−i1−γi+1S_γ(t+1)= _i=1^t (1-γ)α^t+1-i1-γ^i+1 can be written recursively as Sγ(t+1) S_γ(t+1) =(1−γ)α1−γt+1+αSγ(t). = (1-γ)α1-γ^t+1+α S_γ(t). (87) By definition of AγA_γ, we have Aγ≥(1−γt0)Sγ(t0)1−γA_γ≥ (1-γ^t_0)S_γ(t_0)1-γ, thus it holds that Sγ(t0)≤Aγ(1−γ)1−γt0S_γ(t_0)≤ A_γ(1-γ)1-γ^t_0. Next, we assume as induction hypothesis that Sγ(t)≤Aγ(1−γ)1−γtS_γ(t)≤ A_γ(1-γ)1-γ^t for some t≥t0=⌈ln(1−α1+α−2γα)/ln(γ)⌉t≥ t_0= ( 1-α1+α-2γα)/ (γ) . Then, from (87), Sγ(t+1)S_γ(t+1) can be upper bounded as Sγ(t+1)≤(1−γ)α1−γt+1+αAγ(1−γ)1−γtS_γ(t+1)≤ (1-γ)α1-γ^t+1+α A_γ(1-γ)1-γ^t. To complete the induction, it suffices to show that the right-hand side above is at most Aγ(1−γ)1−γt+1 A_γ(1-γ)1-γ^t+1. After rearranging and simplifying, this condition is equivalent to Aγ[1−α−αγt1−γ1−γt]≥α. A_γ [1-α-αγ^t 1-γ1-γ^t ]≥α. (88) Since t≥t0t≥ t_0 and γ∈(0,1)γ∈(0,1), the definition of t0t_0 implies γt≤γt0≤γln(1−α1+α−2γα)/ln(γ)=1−α1+α−2γα. γ^t≤γ^t_0≤γ ( 1-α1+α-2γα)/ (γ)= 1-α1+α-2γα. Therefore, we can lower bound the left-hand side of (88) as Aγ[1−α−αγt1−γ1−γt]A_γ [1-α-αγ^t 1-γ1-γ^t ] ≥Aγ[1−α−α1−α1+α−2γα1−γ1−1−α1+α−2γα]=Aγ1−α2,≥ A_γ [1-α-α 1-α1+α-2γα 1-γ1- 1-α1+α-2γα ]=A_γ 1-α2, where the inequality is due to the bound on γtγ^t. Finally, by the definition of AγA_γ, we have Aγ(1−α2)≥αA_γ( 1-α2)≥α, and thus (88) holds. We have thus proved that Sγ(t+1)≤Aγ(1−γ)1−γt+1S_γ(t+1)≤ A_γ(1-γ)1-γ^t+1. Hence, by induction, (86) holds for all t≥t0t≥ t_0. Substituting (86) into (50) yields (51). Next, from (87), the sequence Sγ(t)\S_γ(t)\ satisfies Sγ(t+1)=αSγ(t)+bt, S_γ(t+1)=α S_γ(t)+b_t, with bt≜(1−γ)α1−γt+1b_t (1-γ)α1-γ^t+1. Since bt→(1−γ)αb_t→(1-γ)α and α∈(0,1)α∈(0,1), Lemma 6 immediately yields limt→∞Sγ(t)=(1−γ)α1−α. _t→∞S_γ(t)= (1-γ)α1-α. Applying lim supt→∞ _t→∞ to both sides of (50), and using the limit of Sγ(t)S_γ(t) gives (52), which completes the proof. ∎ References [1] M. F. U. Abrar, N. Michelusi, and E. G. Larsson, “Decentralized time-varying optimization for streaming data via temporal weighting,” 2026, to appear at the 2026 IEEE Asilomar Conference on Signals, Systems, and Computers. [Online]. Available: https://arxiv.org/abs/2605.06971 [2] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, p. 278–305, 2019. [3] A. Simonetto, E. Dall’Anese, S. Paternain, G. Leus, and G. B. Giannakis, “Time-varying convex optimization: Time-structured algorithms and applications,” Proceedings of the IEEE, vol. 108, no. 11, p. 2032–2048, 2020. [4] E. Dall’Anese, A. Simonetto, S. Becker, and L. Madden, “Optimization and learning with information streams: Time-varying algorithms and applications,” IEEE Signal Processing Magazine, vol. 37, p. 71–83, 2019. [5] S. C. Hoi, D. Sahoo, J. Lu, and P. Zhao, “Online learning: A comprehensive survey,” Neurocomput., vol. 459, no. C, p. 249–289, Oct. 2021. [6] L. Wang, X. Zhang, H. Su, and J. Zhu, “A comprehensive survey of continual learning: Theory, method and application,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 46, no. 8, p. 5362–5383, 2024. [7] L. Yuan, Z. Wang, L. Sun, P. S. Yu, and C. G. Brinton, “Decentralized federated learning: A survey and perspective,” IEEE Internet of Things Journal, vol. 11, no. 21, p. 34 617–34 638, 2024. [8] M. Chen, D. Gündüz, K. Huang, W. Saad, M. Bennis, A. V. Feljan, and H. V. Poor, “Distributed learning in wireless networks: Recent progress and future challenges,” IEEE Journal on Selected Areas in Comms., vol. 39, no. 12, p. 3579–3605, 2021. [9] N. Michelusi, “Non-coherent over-the-air decentralized gradient descent,” IEEE Trans. on Signal Processing, vol. 72, p. 4618–4634, 2024. [10] M. F. Ul Abrar and N. Michelusi, “Biased federated learning under wireless heterogeneity,” IEEE Trans. on Wireless Comms., vol. 25, p. 16 449–16 462, 2026. [11] A. H. Sayed, “Adaptation, learning, and optimization over networks,” Found. Trends Mach. Learn., vol. 7, no. 4–5, p. 311–801, Jul. 2014. [12] L. Bai, C. Sun, Z. Feng, and G. Hu, “Distributed continuous-time resource allocation with time-varying resources under quadratic cost functions,” in 2018 IEEE Conference on Decision and Control (CDC), 2018, p. 823–828. [13] Q. Ling and A. Ribeiro, “Decentralized dynamic optimization through the alternating direction method of multipliers,” IEEE Trans. on Signal Processing, vol. 62, no. 5, p. 1185–1197, 2014. [14] C. Xi and U. A. Khan, “Distributed dynamic optimization over directed graphs,” in 2016 IEEE 55th Conference on Decision and Control (CDC), 2016, p. 245–250. [15] A. Simonetto, A. Koppel, A. Mokhtari, G. Leus, and A. Ribeiro, “Decentralized prediction-correction methods for networked time-varying convex optimization,” IEEE Trans. on Automatic Control, vol. 62, no. 11, p. 5724–5738, 2017. [16] C. Sun, M. Ye, and G. Hu, “Distributed time-varying quadratic optimization for multiple agents under undirected graphs,” IEEE Trans. on Automatic Control, vol. 62, no. 7, p. 3687–3694, 2017. [17] S. Rahili and W. Ren, “Distributed continuous-time convex optimization with time-varying cost functions,” IEEE Trans. on Automatic Control, vol. 62, no. 4, p. 1590–1605, 2017. [18] B. Wang, S. Sun, and W. Ren, “Distributed continuous-time algorithms for optimal resource allocation with time-varying quadratic cost functions,” IEEE Trans. on Control of Network Systems, vol. 7, no. 4, p. 1974–1984, 2020. [19] B. Huang, Y. Zou, Z. Meng, and W. Ren, “Distributed time-varying convex optimization for a class of nonlinear multiagent systems,” IEEE Trans. on Automatic Control, vol. 65, no. 2, p. 801–808, 2020. [20] S. Sun, J. Xu, and W. Ren, “Distributed continuous-time algorithms for time-varying constrained convex optimization,” IEEE Trans. on Automatic Control, vol. 68, no. 7, p. 3931–3946, 2023. [21] Y. Li, H. Wang, W. Xu, T. Xiao, H. Liu, M. Tu, Y. Wang, X. Yang, R. Zhang, S. Yu, S. Guo, and R. Li, “Unleashing the power of continual learning on non-centralized devices: A survey,” IEEE Comms. Surveys & Tutorials, vol. 28, p. 1059–1098, 2026. [22] B. Polyak, Introduction to optimization. Optimization Software, 1987. [23] Y. Zhao and M. Swamy, “A novel technique for tracking time-varying minimum and its applications,” in Conference Proceedings. IEEE Canadian Conference on Electrical and Computer Engineering, vol. 2, 1998, p. 910–913 vol.2. [24] A. Y. Popkov, “Gradient methods for nonstationary unconstrained optimization problems,” Autom. Remote Control, vol. 66, no. 6, p. 883–891, Jun. 2005. [25] A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, and A. Ribeiro, “A class of prediction-correction methods for time-varying convex optimization,” Trans. Sig. Proc., vol. 64, no. 17, p. 4576–4591, Sep. 2016. [26] M. Fazlyab, S. Paternain, V. M. Preciado, and A. Ribeiro, “Prediction-correction interior-point method for time-varying convex optimization,” IEEE Trans. on Automatic Control, vol. 63, no. 7, p. 1973–1986, 2018. [27] A. Simonetto and E. Dall’Anese, “Prediction-correction algorithms for time-varying constrained optimization,” IEEE Trans. on Signal Processing, vol. 65, no. 20, p. 5481–5494, 2017. [28] A. S. Charles, A. Balavoine, and C. J. Rozell, “Dynamic filtering of time-varying sparse signals via ℓ1 _1 minimization,” IEEE Trans. on Signal Processing, vol. 64, no. 21, p. 5644–5656, 2016. [29] A. Simonetto and P. Massioni, “Nonlinear optimization filters for stochastic time-varying convex optimization,” International Journal of Robust and Nonlinear Control, vol. 34, no. 12, p. 8065–8089, 2024. [30] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Trans. on Automatic Control, vol. 54, no. 1, p. 48–61, 2009. [31] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, “On the linear convergence of the admm in decentralized consensus optimization,” Trans. Sig. Proc., vol. 62, no. 7, p. 1750–1761, Apr. 2014. [32] K. Yuan, W. Xu, and Q. Ling, “Can primal methods outperform primal-dual methods in decentralized dynamic optimization?” IEEE Trans. on Signal Processing, vol. 68, p. 4466–4480, 2020. [33] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ser. ICML’03. AAAI Press, 2003, p. 928–935. [34] S. Shalev-Shwartz, “Online learning and online convex optimization,” Found. Trends Mach. Learn., vol. 4, p. 107–194, 2012. [35] E. Hazan, “Introduction to online convex optimization,” Found. Trends Optim., vol. 2, p. 157–325, 2016. [36] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan, “Online Optimization: Competing with Dynamic Comparators,” in Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), ser. Proceedings of Machine Learning Research, vol. 38, 2015, p. 398–406. [37] O. Besbes, Y. Gur, and A. Zeevi, “Non-stationary stochastic optimization,” Oper. Res., vol. 63, no. 5, p. 1227–1244, Oct. 2015. [38] S. Shahrampour and A. Jadbabaie, “Distributed online optimization in dynamic environments using mirror descent,” IEEE Trans. on Automatic Control, vol. 63, no. 3, p. 714–725, 2018. [39] Z. Li and D. Hoiem, “Learning without forgetting,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 40, p. 2935–2947, 2016. [40] G. I. Parisi, R. Kemker, J. L. Part, C. Kanan, and S. Wermter, “Continual lifelong learning with neural networks: A review,” Neural Netw., vol. 113, no. C, p. 54–71, May 2019. [41] M. De Lange, R. Aljundi, M. Masana, S. Parisot, X. Jia, A. Leonardis, G. Slabaugh, and T. Tuytelaars, “A continual learning survey: Defying forgetting in classification tasks,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 44, no. 7, p. 3366–3385, 2022. [42] M. McCloskey and N. J. Cohen, “Catastrophic interference in connectionist networks: The sequential learning problem,” Psychology of Learning and Motivation, vol. 24, p. 109–165, 1989. [43] B. Wu, Z. Ding, and J. Huang, “A review of continual learning in edge ai,” IEEE Trans. on Network Science and Engineering, vol. 13, p. 6571–6588, 2026. [44] A. Mitra, H. Hassani, and G. J. Pappas, “Online federated learning,” in 2021 60th IEEE Conference on Decision and Control (CDC), 2021, p. 4083–4090. [45] O. Marfoq, G. Neglia, L. Kameni, and R. Vidal, “Federated learning for data streams,” in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, F. Ruiz, J. Dy, and J.-W. van de Meent, Eds., vol. 206. PMLR, 25–27 Apr 2023, p. 8889–8924. [46] C.-H. Hu, Z. Chen, and E. G. Larsson, “Energy-efficient federated edge learning with streaming data: A Lyapunov optimization approach,” IEEE Trans. on Comms., vol. 73, no. 2, p. 1142–1156, 2025. [47] M. F. Ul Abrar, N. Michelusi, and E. G. Larsson, “Time-varying optimization for streaming data via temporal weighting,” in 2025 59th Asilomar Conference on Signals, Systems, and Computers, 2025, p. 1343–1349. [48] E. G. Larsson and N. Michelusi, “Unified analysis of decentralized gradient descent: a contraction mapping framework,” IEEE Open Journal of Signal Processing, p. 1–25, 2025. [49] Y. Nesterov, Lectures on Convex Optimization, 2nd ed. Springer Publishing Company, Incorporated, 2018. [50] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge university press, 2004. [51] W. Rudin, Principles of Mathematical Analysis, 3rd ed. New York, NY: McGraw-Hill, 1976, vol. 3.