Streaming Federated Learning with Markovian Data
Authors: Tan-Khiem HUYNH
Malcolm Egan
Giovanni Neglia
Jean-Marie Gorce
Venue: NeurIPS 2025 poster ()
Keywords: Optimization - Non-convex
Federated Learning
Markovian Processes
Stochastic Approximation
Primary area: optimization
TL;DR: We show that collaboration is beneficial in Federated Learning with Markovian streaming data.

Abstract: Federated learning (FL) is now recognized as a key framework for communication-efficient collaborative learning. Most theoretical and empirical studies, however, rely on the assumption that clients have access to pre-collected data sets, with limited investigation into scenarios where clients continuously collect data. In many real-world applications, particularly when data is generated by physical or biological processes, client data streams are often modeled by non-stationary Markov processes. Unlike standard i.i.d. sampling, the performance of FL with Markovian data streams remains poorly understood due to the statistical dependencies between client samples over time. In this paper, we investigate whether FL can still support collaborative learning with Markovian data streams. Specifically, we analyze the performance of Minibatch SGD, Local SGD, and a variant of Local SGD with momentum. We answer affirmatively under standard assumptions and smooth non-convex client objectives: the sample complexity is proportional to the inverse of the number of clients with a communication complexity comparable to the i.i.d. scenario. However, the sample complexity for Markovian data streams remains higher than for i.i.d. sampling. Our analysis is validated via experiments with real pollution monitoring time series data.

Streaming Federated Learning with Markovian Data
Tan-Khiem Huynh"
Malcolm Egan Inria, INSA Lyon
Giovanni Neglia
Inria,
Inria, Université Côte d' Azur
INSA Lyon
Jean-Marie Gorce
Inria,
INSA Lyon
Abstract
Federated learning (FL) is now recognized as a key framework for communication- efficient collaborative learning. Most theoretical and empirical studies, however, rely on the assumption that clients have access to pre-collected data sets, with limited investigation into scenarios where clients continuously collect data. In many real-world applications, particularly when data is generated by physical or ological processes, client data streams are often modeled by non-stationary Markov processes. Unlike standard i.i.d. sampling, the performance of FL with Markovian data streams remains poorly understood due the statistical dependencies between client samples over time. In this paper, we investigate whether FL can still support collaborative learning with Markovian data streams. Specifically, analyze the performance of Minibatch SGD, Local SGD, and variant of Local SGD with momentum. We answer affirmatively under standard assumptions and smooth non-convex client objectives: the sample complexity is proportional to the inverse of the number of clients, with a communication complexity comparable to the i.i.d. scenario. However, the sample complexity for Markovian data streams remains higher than for i.i.d. sampling. Our analysis is validated via experiments with real pollution monitoring time series data.
Introduction
Many of these clients are capable of continuously collecting and lcarning from data, instead of simply storing large quantities of historical data (28). This streaming data arises in applications ranging from health 21 22 and
As edge networks grow in scale, clients are increasingly diverse 34
environmental monitoring (24], to control of robots [29].
Each data stream provides detailed information about individual clients. However, applications such as environmental resource management [54] or public health monitoring [6] often aim to derive population- level insights, leveraging data streams from multiple individuals learn global model. As this data may be sensitive or costly to communicate, centralized training solutions are undesirable. Federated Learning (FL.) has emerged as key strategy for communication-effccii
collaborative
learning 26 In conventional FL. scenarios, clients have access to local datasets used to train models locally. These models are then transmitted to central server, where aggregation facilitates collaborative learning. FL minimizes communication overhead while learning models with high accuracy and ensuring client data are not shared.
Clients with streaming data must also cope with memory constraints have limited control over data sampling: local updates can only be computed using the current data
38 35
This means that clients
Inria, INSA Lyon, CITI, UR3720, 69621 Villeurbanne, France
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

samples stored in memory. Moreover, data in health and environmental monitoring applications is often generated by non-linear physical and biological systems. The data generated by these systems is frequently modeled as non-stationary Markovian data streams [1 58). When client memory caches are continually refreshed by Markovian streaming data, the samples available to compute updates are statistically dependent and non-stationary in time.
In this paper, we address the following question: Can FL with Markovian data streams support collaborative learming? ? While Markovian sampling has been explored in the centralized setting 17 existing work in the federated setting has focused on Federated Reinforcement Learning [45
28
with convex objectives. However, classification and regression tasks in systems with non non-linear dynamics often rely on deep neural networks or non-convex regularization [63] (3). resulting in non-convex minimization problems during training. We therefore consider a family of training
tasks beyond the work in 45
28 37 characterized by smooth non-convex loss functions. Our main
contributions can be summarized as follows:
(i) Impact of Markovian sampling: We rigorously characterize the impact of Markovian sam- pling on the convergence rate of Minibatch and Local Stochastic Gradient Descent (SGD), the two most common baselines in FL. key conclusion is that linear speed-up is achieved under standard assumptions on the objectives and heterogeneity: the sample complexity is proportional to the inverse of the number of clients.
(ii) Mitigating client heterogeneity: We show that a momentum-basee variant of Local SGD introduced in the i.i.d. setting [1] can effectively mitigate the client drift with Markovian data streams. In particular, unlike Local SGD, Local SGD with Momentum matches performance of Minibatch SGD up constant without requiring any bound on client data heterogeneity.
(iii) Validation on Environmental Monitoring Data: The key difference between i.i.d. and Markovian sampling is statistical dependence between consecutive samples. We validate our analysis using multi-site pollution time series data (7), which shows the benefit of collaboration on real data with dependent samples.
2
Related Works
Edge devices often encounter the challenge of processing continuous data streams while operating under memory constraints [38, [35]. Learning from streaming data presents numerous challenges, with solutions dependent on the data-generating process. One line of research addresses scenarios where the data distribution evolves over time, with continual learning methods designed to adapt the model the changing data distribution
[5T]. Another line focuses on adversarial settings, where the data stream is generated by an adversary [33] often addressed using online learning algorithms with
regret guarantees.
In this paper, we focus on learning from data generated by Markovian processes. Markovian processes have been successfully applied to model various physical and biological systems I 58
and encompass the special case where data samples are drawn i...d. from an unknown distribution.
In the centralized setting, this learning problem can be framed as stochastic approximation problem, typically addressed by variants of stochastic gradient descent (SGD). While SGD with i.i.d. data is well-understood [4 31, the Markovian nature of the data stream introduces challenges due the temporal correlation between samples.
For uniformly ergodic Markov chains, [66] first demonstrated that mirror descent achieves optimal convergence rates for Lipschitz, general convex, and non-convex problems. Recently, [5] random batch size algorithm that adapts the mixing time of the Markov chain, while 3 adopted the same technique to develop accelerated methods and established lower bounds for strongly convex objectives.
proposed
have shown sub- optimal dependence the mixing time and on the variance of stochastic gradient estimates relative to the lower bounds in 3 16.. We refer to Table 1] for an exhaustive review of the literature on SGD with Markovian noise.
For general Markov chains, existing analysis of SGD-type algorithms [4 13

---

In the case of SGD with Markovian noise on finite state space - common scenario in distributed optimization 4
T7 23 developed convergence theories and variance reduction techniques for first-order methods, demonstrating improvements over the gossip algorithm [5]
In the context of FI., few papers have considered learning from data streams. and
62 framed
the problem in an adversarial and in a continual learning setting, respectively. homogeneity assumptions, such as requiring all clients to share a common optimal model. (38 assumed that each client's 's data stream consists of i.i.d. samples, while allowing for heterogeneous data distributions across clients. The study focused on temporal dependencies arising from the use
g imposed strong
of local memory and analyzed the impact of heterogeneous memory constraints. [35] studied how
to jointl tune batch sizes and number of local updates, but did not have convergence results in the streaming setting.
In the case of Markovian data streams, recent work has primarily focused on Federated Reinforcement Learning (FRL) with linear function approximation. A key challenge is demonstrating that collabora- tion beneficial in this setting; namely, that the per-client sample complexity of FRL algorithms decreases inversely with the number of clients. While this linear speed-up is well-understood for i..dd data, the impact of collaboration remains an open question in the presence of statistical depen- dence, as is the case with Markovian data streams. [28] [8] demonstrated the benefits of cooperation under a strong homogeneity assumption on the client environment. Heterogeneous settings have been considered in [12 25
with a linear speed-up established in [59] subject to heterogeneity assumptions, which were then relaxed in (37] by incorporating control variates 27 Unfortunately, these results
do not readily extend beyond the FRI. setting.
Beyond Markovian data streams, temporal correlations arise from other factors in the FL setting. For instance, memory update strategies, as explored in [38]. can introduce dependencies between subsequent updates. Similarly, the availability of clients can exhibit Markovian behavior, as discussed in [46, 49 (56). While these sources of correlation are distinct from the Markovian data stream focus of this paper, they highlight the broader significance of understanding and mitigating temporal dependencies in the FL context.
3 Problem Setup
In this section, we introduce our problem setting. We denote by [M] [1, MM] the set of positive integers up to M, and by [K]o = [0, K - 1] the set of non-negative integers less than K.
3.1 Streaming Federated Learning
Consider M clients, each with an objective given by
(ww)) = Ez= Um (w;
where fm : IRd x 14m + R and 7m the target data distribution. for client m. In the context of supervised learning, the objective Fn corresponds to the true risk of the loss function fm- parameterized by the parameter w. on data sample x drawn from km.
In FL, the M clients collaborate to solve
M Σ Fm(w)) (w),
min weRd
M
by iterating a two-phase procedure over multiple communication rounds. Two popular examples of this procedure are Minibatch SGD (Algorithm 2 in Appendix A and Local SGD FedAvg (Algorithm 3 in Appendix AA) (26.. In the first phase of the 1-th communication round, client m has access to K data samples. These samples are used to compute a local update: either gradient
estimate g; (m) in the case of Minibatch SGD, or a model iterate w (m,,k) obtained after performing K
local gradient steps in the case of Local SGD. In the second phase, the server aggregates the local
updates from all clients-typically typically via averaging- to update the global model. In the second phase, the updates are aggregated via averaging.
In the standard FL scenario, the samples available at client m any communication round are fixed, corresponding to pre-collected data (26). In contrast, in streaming FL, the data available to client
3

---

m can change in every communication round. Streaming FL models scenarios where clients have a limited memory cache of K samples and new data is collected over time [3 35].
Streaming FL. raises a key challenge: the data sampling process is not completely controlled by the clients. As a consequence, i.i.d. data samples from the target distribution 7. may not be available. For example, patient data in health monitoring is continuously collected from wearable devices. Statistical dependence between data collected over time naturally arises due latent factors such as daily routines, sleep patterns, and weather conditions [32]. Moreover, the initial data collection or warm-up period [2] might capture atypical behavior, such as adjustments new wearable devices. As consequence, the data stream of a patient m will, in general, be non- con-stationary and not reflect the long-term target distribution my-
3.2 Markovian Data Streams
Data streams arising in health and environmental monitoring often exhibit specific statistical structures. Indeed, many biological, chemical, and physical systems are governed by non-stationary Markov processes 28
processes [ 58 Data streams arising in federated reinforcement learning also form Markov however, the use of stationary exploration policies leads to stationary data streams.
We model the data stream Xm = (x:"*) )ee of client m by a time-homogeneous Markov chain evolving on the state space 2um C Rd with the corresponding Borel o-field Bm. [48] [3]. As an abuse of notation, for all E N, and for all & E [K]. we denote by xi [m.k) == Kk++ the k-th sample
(m.,k)
available client m at the I-th communication round. We may also use xx." 3
ke(K]o to
denote all K data samples available to client m in communication round t. The evolution of the time-homogeneous Markov chain for client m is characterized by the initial distribution 200 and by the transition kernel P...
(m,00 jm
We focus on the case of independent clients, where X,, is independent of Xm for m # m'. This scenario occurs when client data streams are generated by non-interacting processes. Key examples include patient health monitoring and environmental monitoring across spatially separated regions, where observations from different clients are often assumed be independent [50]
The Markov chain Xm admits a stationary distribution Tm on 2m if
f
(Tm(()) mm (I, da(mm.)) = dd (1m (m..k)
JEER
We say that Xm is stationary if zo
(m,0) Tni otherwise, Xm is non-stationary.
The stationary distributions Tmy E [M] correspond to the target distributions in (1. which capture the long-term statistics of the data samples. Since long-term statistics, rather than transient behavior of the samples, of interest for learning in health and environmental monitoring scenarios, the stationary distribution is natural choice for the target distribution. Hence, we make the following assumption, which guarantees that the Markov process associated with each client admits a unique stationary distribution.
Assumption 3.1. The data samples of client m [M] are drawn from an independent time- homogeneous Markov chain Xm. defined on (Im,, B,x) with transition kernel Pm and initial distribu- tion fmm, converging to the unique stationary distribution mm-
Assumption 3.1 ensures that samples x!"" from the data stream of client m will be approximately drawn from K. as diverges.
We also define by X (Xm) [M the system-level Markov process defined on (2,, where m=1 Pm and B = 0 Bn This Markov chain, at each time step, evolves independently on each of M coordinates according to the corresponding transition kernel Pm- We denote by
P its transition matrix. Similarly, for the ease of notation, we write o. == (z.
and ME[M]
(z kE|K]o
In the case of nearby or overlapping regions, statistical dependence between the data samples may arise
40

---

In Proposition B.6 we provide formal characterization of P and we also prove that X is indeed well-defined Markov chain. Furthermore, under Assumption [.I] X admits stationary distribution
M We denote by Pps the pseudo spectral gap of 4 Section 3.1].
π m=1 mm
We also make the following assumption on the absolute continuity of the transition kernel P with respect the stationary distribution π.
Assumption 3.2. For every I E Ω2 the probability measure P(z,)) .) is absolutely continuous with respect the stationary measure म, and its Radon-Nikodym derivative dP(x..) is uniformly bounded on sets with non-zero measure with respect to т. In particular,
dP
C sup CsS sup acQ
< 30
dm
We note that Assumption 3.2 is generally mild, in the sense that it only requires, for every E S2 P(x,-) absolutely continuous with respect to π, and every r-integrable function also P(x,, .)- integrable. This assumption is commonly used in the analysis of other stochastic approximation algorithms with Markovian noise, for example, Markov chain Monte Carlo [19] Theorem 12]. In the
We provide further discussion of the dependence of case where Ω is finite, C = mäX P(z.9)
Co on the transition kernel in Appendix D.5
In contrast to most existing studies on stochastic optimization (approximation) with Markovian data, we do not impose any assumption on the speed of convergence to the stationary measure of the underlying Markov processes, such the commonly used uniform geometric ergodicity assumption (see, e. [3 Assumption A3;37 Assumption A3; Assumption 3; 66] Assumption 3J), which requires exponentially fast convergence to the stationary measure. Prior works rely on this fast mixing property to handle the non -oattioiinn of Markovian data when taking conditional expectations, which is ubiquitous in the analysis of SGD-type algorithms. However, our analysis shows that, under the mild Assumption 3.2. simple change of measures suffices. As uniform geometric ergodicity is typically difficult verify in real-world scenarios, our results are therefore more broadly applicable. For completeness, in Appendix [D.4] we provide an extension of our analysis under the stronger uniform geometric ergodicity assumption.
4 Convergence Analysis
4.1
Assumptions
To conduct the convergence analysis, we first impose the following assumptions on the objective functions and the stochastic gradients. Assumption 4.1. The global objective function F is L-smooth; that is, for all w1, w2 RR:
L || w2ll"
F(w2) F(w1) FVF()) w2 w1) +
In some cases, we will need the following assumption that requires the sample- wise local objective functions to be L-smooth:
Assumption 4.2. For every that is, for all wi, Wa E IRd Ωm.
[M], the sample-wise objective functions fm (w: are L-smooth;
L fm (w < fm (w)))) + fm We wi) + 2 || w2ll?
We note that Assumption 4.2 implies Assumption 4.1
Next, we state an assumption the noise of the stochastic gradients. Assumption 4.3. For all clients m E [M], for x E 9m and w E [Rd, there exists o such that (w; (w) 0²
Assumption 4.3 uniformly bounds the gradient estimation error for each client. While stronger than the bounded variance assumption, this assumption standard for stochastic optimization with Markovian noise in both the centralized (3] and federated [37] settings.
5

---

Heterogeneity in client objective functions and data distributions is a well-known challenge for FL algorithms based on Local SGD, it leads client drift [27]. In order to provide convergence guarantees in the i.i.d. setting, it is necessary to impose constraints on the local gradient norms (60 [4] Client heterogeneity poses the same difficulty in the Markovian setting. As such, we impose the following bounded gradient dissimilarity (BGD) assumption.
Assumption 4.4. There exist 0 2 0 and 8 > such that, for all w E RRd
V (w)l Σ M
S 0² 6 (VF((
This assumption first introduced in 27 and has since become ubiquitous in the analysis of Local SGD [64]. We highlight that the BGD assumption includes the assumptions in [60 33]. While weaker heterogeneity assumptions exist in the literature, these are not straightforward to apply for non-convex objectives where the BGD assumption is standard 30) In Section we establish iteration and communication complexity bounds of Local SGD under these assumptions.
Finally, we define the following three classes of problems for the analysis of Minibatch SGD, Local SGD, and Local SGD with Momentum (SGD-M). Recall from Section 3.2 that the system-level Markov chain is denoted by X. We assume throughout that all objective functions are general non-convex and F is bounded from below by F* -X0.
Fi(L, uss Coo) [[F, X) Assumptions 3.1
3.2
4.1
and
4.3
hold]
F, Ups Ups Cxo) = {(F,X) Assumptions
3.1
3.2
4.2
and hold] }
Mps Coc) == {(F,X X): Assumptions
3.1
3.2
and
4.2 to hold
We note that
o,, Cx) F2(, Coo) C Fi(LL,, Coo).
In the following sections, analyze the convergence of Minibatch SGD, Local SGD, and Local SGD-M for the problem classes F3. and F2, respectively. For any <> 0, we derive conditions on the step sizes, the number of local steps K, and the number of communication rounds T that ensure convergence to an e-accurate solution, i.e.,
where viy is the output of each algorithm, drawn uniformly at random from the iterates wo, WT--- We use the Landau big-O notation O(-), Vbb for max {a,b), aAD for min {a, b). Ao for F(wo) F and Go for 1 M
Σ MM E V/ (wo))
4.2 Minibatch SGD
We first establish the following upper bound for Minibatch SGD.
Theorem 4.5. For the problem class Fi Fi o, Upe, Coo), with global step size 7 S 1/L, the iterates of Minibatch SGD satisfy:
Ao TT
Co
E [IVF S S
Ups MK
The proof of Theorem 4.3 is given in Appendix D.I The first deterministic term depends on the initial iterate and decays with the same rate as in the i.i.d. setting. The last term arises from the dependence structure and statiiotttoiitt of the Markov data process. In contrast to i.i.d. sampling [60], these terms cannot be controlled by the step size. In particular, Theorem reveals that the stochastic gradient noise is amplified by factor inversely proportional to the spectral gap of the system-level Markov chain.
The following corollary characterizes the communication and sample complexity of Minibatch SGD.

---

Corollary 4.6. Under the conditions of Theorem 4.5 the required number of local steps and communication rounds for Minibatch SGD achieve
[TF( e² are:
C (( Mps
T.o
K = O
T T= 0
2
The proof of Corollary 4.6 is deferred to Appendix
D.I
4.3 Local SGD
In the analysis of Local SGD, bounded heterogeneity assumptions required, in the i..d. setting [27]. We consider the problem class (L or 0, ó, ppss Cs.), which requires sample-wise smoothness (Assumption 4.2 and bounded heterogeneity (Assumption 4.4.
Theorem 4.7, For any F E Fa(L,, a,,,,,,,,0000 0, Ups Coo), with local step size rj S (, the iterates of Local SGD) satisfy:
IE [FF(T)] S so ( Do nKT Mp
Coo
LK1 (02 + 0²)
+
82
The proof of Theorem 4.7 is given in Appendix D.2 The convergence behavior of Local SGD closely resembles that of Minibatch SGD, except for the additional third term introduced by the client drift. We note that this term can be controlled by having sufficiently small step size. Similar to Corollary 4.6 the following corollary specifies the communication and sample complexity of Local SGD for both stationary and non-stationary Markov chains.
Corollary 4.8. Under the conditions of Theorem 4.7 and
8²2
moo KL + o2) A KL82
the required number of local steps and communication rounds for Local SGD achieve B[][F((TT]] e,, are:
(Coo0²)
T LAo
0² P
K K-O
822
822
Mpa
The proof of Corollary 4.8 also given in Appendix D.2
4.4 Local SGD with Momentum
In the case of i.i.d. sampling, several algorithms have been proposed to mitigate the client drift effect without the need of Assumption 4.4 One line of work focuses on the control variate technique, first introduced by [27). Recently, 99 61 have demonstrated that momentum can also be used to mitigate
client drift in the i.i.d. setting.
In this section, we study the convergence of momentum- based variant of Local SGD, named Local SGD-M, detailed in Algorithm [ The key difference from Local SGD is that the local updates are computed via the convex combination of the gradient estimate for the local objective and the aggregated updates from the previous communication round. This allows to build recursive bound for the gradient estimate error, without relying on any heterogeneity assumption bound the drift caused by local updates as in the case of Local SGD.
We show that, with Markovian data, this technique also mitigates the impact of client drift. In particular, the lower bound on communication complexity in the i.i.d. setting [42) is achieved up constant without any heterogeneity assumptions. The convergence result for Local SGD with momentum holds for the broader function class Fz o, M/p.. Coo ), which retains the sample-wise smoothness condition but relaxes the requirement for bounded heterogeneity.
Theorem 4.9. For the problem class Fz Vps, Coo), with the following conditions on the step sizes:
KL 0 (
Co.
LAo B3TG. (1 3)
BTLT 750 $
4
A
MK32
7

---

Algorithm Local SGD-M
Input: initial model wp and gradient estimate vo, local learning rate v,, global learning rate 7 and momentum / for /. 0 to - do
for every client m [MM] parallel do
Initialize local model wi (m..0) Wr
for k to K do
u/ (m,k) = fm W
(m, km.)k)))
+ (1 -1-18 (1-1))
w (m, wi km. 17,4 (m) end for Communicate uit m.K end for
Aggregate: U++11 1MK 2m=1 We w/ k))
Server update: W4+11 = W/ - 7/1+11
end for Output: Wi sampled uniformly from wo.... w1--1
the iterates of Local SGD-M satisfy:
E |VF(On))
so
LLo
Cooo?
3T
The proof of Theorem 4.9 is given in Appendix D.3 The communication and sample complexities of Local SGD-M are characterized in the following corollary.
Corollary 4.10. Under the conditions of Theorem communication rounds for Local SGD-M achieve
4.9 the required number of local steps and
VIVF((c ((TT))11 e² are:
K K=0
C20 Mp2
LAo
T O
3e2
The proof of Corollary 4.10 is delegated to Appendix D.3
4.5 Discussion
Impact of Markovian Data:
Our convergence analysis in Corollaries 4.6 4.8 and 4.10 reveals
the impact of Markovian sampling for smooth non-convex objectives. Due to temporal dependence between samples, the gradient noise is scaled by Coc/Ups. which depends on the spectral properties of the Markov kernel. Moreover, the stochastic gradient estimates computed by the clients are inherently biased. This bias arises from the Markovian structure of the data and, unlike the i.i.d. case, cannot be controlled by having a small or decaying step size. This is due to the fact that the bias contributes to the terms involving the gradient noise 2² in bounds. Consequently, in order control these terms and guarantee convergence, the number of local steps must be sufficiently large.
However, we emphasize that our results remain consistent with the core principles of FL: leveraging more local computation to reduce communication costs. Indeed, a comparison with 42] Table 2] shows that the lower bound established in the i.i.d. setting for communication complexity can be achieved by Minibatch SGD and Local SGD-M. Similar results for the special case of Federated Stochastic Approximation (FSA) be observed in (37 Corollary 4.5), where additional local
computation required to reduce the third term in 37 Theorem 4.1].
or the loken-passing [7 setting introduce auxiliary papee-parameters that can tuned to make the bias vanish, instead of tuning directly the step size. This is achieved:
Some prior works in the centralized 3 15 14
in 17 by decomposing the bias into other terms involving delayed gradients, and scaling such delays as 1/VT. However, this technique requires a constraint on the minimum number of iterations T (analogous to the number of communication rounds in our analysis),

---

at the order of the mixing time of the Markov chain. Such a constraint is undesirable in the FL setting, where the main goal is to minimize communication. A recent paper on FSA [65] follows the same strategy and indeed needs to impose a lower bound on 7 proportional to the maximum mixing time across all clients.
in 15 by using minibatch gradient estimates (instead of using just one sample). More precisely, at each iteration, random batch size is drawn from a truncated geometric distribution with maximum value m, requiring a new haper-parameter. [3] [5 show that the bias scales inversely with mn, which is then chosen to scaled with vT.
We highlight that the sample complexities obtained in our paper of the order of 1/(MM*), matching those achieved in [3 14 17 scaled inversely with the number of clients M. However, as already mentioned in Section 3.2 assumptions on the underlying Markov processes are more general.
Furthermore, as the terms involving o² scale with 1/ K, following the approach in 15] and letting K scale with I would indeed drive these terms zero as T - oc. Nevertheless, doing so would not lead to any improvement in the overall sample complexity. Further details on this, as well as a more exhaustive discussion on the differences of our work with existing works, are provided in Appendix C
Impact of Heterogeneity: assumption. The lower bound for communication complexity in the i.i.d. setting can only be achieved
Convergence analysis of Local SGD requires the BGD heterogeneity
within the low-heterogeneity, low-noise regime; i.e., when +
e² < 84. In contrast, Local SGD-M successfully mitigates the client drift caused by heterogeneity. In particular, the lower bound on the communication complexity in [4 is achieved without any heterogeneity assumptions, up to constant of 1/3, while maintaining the same number of samples per communication round K. This contrasts with SCAFFLSA (37), which utilizes control variates to mitigate heterogeneity, resulting in lower communication complexity. However, SCAFFLSA needs a higher number of samples per communication round than its vanilla version, FedLSA, and still relies around the optimum. Another work on FSA shows the presence of a persistent bias term (59) Theorem 2). which cannot be controlled with increased local computation even more communication rounds.
heterogeneity assumption
Impact of Number of Clients M: The sample complexity of all three algorithms scales with 1 1/M, demonstrating the benefits of collaboration in FL with heterogeneous Markovian data streams and smooth non-convex objective functions.
5 Numerical Results
In this section, we evaluate the performance of Local SGD, Minibatch SGD, and Local SGD with Momentum on the Beijing Multi-Site Air-Quality dataset [7]. which contains hourly measurements from 12 weather stations across China, collected between March 2013 and February 2017. The prediction target is seasonality logical indicators as features. In Appendix E we provide further details for the time series data preprocessing, non-convex objective, and additional experiments to investigate the impact of the Markov chain's 's spectral gap with synthetic data.
PM2.5 concentration, using other air quality and meteoro-
We partition the data temporally, reserving the last 12 months for testing and using the preceding 36 months for training. To simulate a federated setting with a larger number of clients, we create virtual clients by randomly sampling contiguous windows of {6, 12} months from the training period. We use a linear regression model with a non-convex regularizer to encourage sparsity, based on preliminary correlation analysis indicating that some features are not informative. The regularization suppresses less relevant features while preserving smoothness for optimization, and is widely used in
robust non-convex optimization [57 20
Impact of heterogeneity: In Figure we plot the trajectories of the gradient norm over the communication rounds for Minibatch SGD, Local SGD, Local SGD-M, and SCAFFOLD 27,, which the first algorithm proposed in the i.i.d. setting to mitigate heterogeneity in FL. We compare these methods under varying numbers of samples, K, per communication round. We observe that the performance of Minibatch SGD and Local SGD-M consistently improves as K increases, whereas Local SGD and SCAFFOLD exhibit little to no improvement. This is consistent with our theoretical findings, which identify heterogeneity as a limiting factor as K increases for Local SGD, but not for Minibatch SGD or Local SGD-M. For SCAFFOLD, we argue that its advantage is clearer in the

---

10
10
10
Scalffo
10-1
10
200 400 Communication rounds
50 Communication rounds
150
Commanication rounds
(a) K 10
(b) K 50
(c) K 100
Figure Gradient norm as a function of the number of communication rounds for Local SGD, Minibatch SGD, Local SGD-M, and SCAFFOLD, with 7 = 0.1, = 0.01, 3 = 0.5, X = 0.01 for 120 clients (each client has access 12 consecutive months of training data) and different numbers of local steps.
clients 240 clients
10-2
10-1
10-1
10
20
30
20
30
40
10 Communication rounds
30
40
Communication rounds
Communication rounds
(a) Local SGD
(b) Minibatch SGD
(c) Local SGD-M
Figure 2: Gradient norm as a function of the number of communication rounds for Local SGD, Minibatch SGD & Local SGD-M, with y = 0.1, = 0.001, 3 = 0.5, À = 0.01 and K = 100 for different numbers of clients. Each client has access to window consecutive months of training data.
partial participation setting. (9] also shows that incorporating momentum into SCAFFOLD under the partial client participation setting further improves the convergence. Extending current analysis to evaluate the combined effect momentum and control variates in the partial participation setting with Markovian data is promising direction for future research.
Impact Number of Clients M: In Figure 2 we plot the trajectories of the gradient norm for each of the three algorithms with different numbers of clients. For all three methods, the gradient norm decreases as the number clients increases, indicating that collaboration beneficial even in the presence of heterogeneous Markovian data trend consistent with our theoretical analysis.
6 Conclusion
Statistical dependence a reality in data streams arising from physical and biological systems. A key question is whether collaboration remains beneficial for FL with Markovian data streams. To address this question, we showed via analysis and experiments with pollution data that there is a speed-up in FL with smooth non-convex objectives for Minibatch SGD, Local SGD, and Local SGD with Momentum. However, there is cost associated with Markovian data streams, quantified by an increase in the sample complexity compared with i.i.d sampling.
10

---

Acknowledgments and Disclosure of Funding
This research was supported part by the French government, through the 31A Côte d' Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference numbers ANR- 11--119------000 and ANR-24-CE25-222, in part by the European Network of Excellence dAIEDGE under Grant Agreement Nr. 101 101126,,6, in part by the Groupe La Poste, sponsor of the Inria Foundation, the framework of the FedMalin Inria Challenge, and in part by the EU HORIZON MSCA 2023 DN project FINALITY (G.A. 101 168816). This work was also partially supported by the Inria-Nokia Challenge Learn-Nee Experiments were carried out using the Grid' 5000 testbed supported by scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations.
References
[1] D. Anderson and T. Kurtz. Stochastic Analysis of Biochemical Systems. Springer, Berlin, 2015.
[2] A. Baghdadi, L. Cavuoto, A. Jones-Farmet S. Rigdon, E. Esfahani, and E. Megahed. Monitoring worker fatigue using wearable devices: case study to detect changes gait parameters. Journal of Quality Technology, 54(1):47-71, 2021.
[3] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. In Advances in Neural Information Processing Systems, volume 36, pages 44820-44835. Curran Associates, Inc., 2023.
[4] Mikael Johansson Bjorn Johansson, Maben Rabi. A simple peer-to-peer algorithm for distributed optimization in sensor networks. In Proceeding of the 46th IEEE Conference on Decision and Control, pages 4705-477 4015-4410.10 2007.
[5] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6))2508-25) -5300, 2006. doi: 10.1 10.1109/1TT.2206884455111
[6] S. Chae, S. Kwon, and D. Lee. Predicting infectious disease using deep learning and big data. International Journal of Environmental Research and Public Health, 15(8), 2018.
[7] Song Chen. Beijing Multi-Site Air Quality. UCI Machine Learning Repository, 2017. DOI: http://bbb.rr///2244333/CCCC
[8] Y. Chen, Y. Ning, M. Slawski, and H. Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In IEEE International Conference on Big Data, 2020.
[9] Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably, In The Twelfth International Conference on Learning Representations, 2024.
[10] Donald L. Cohn. Measure Theory: Second Edition. Springer New York, 2013.
[11] Ashok Cutkosky and Francesco Orabona. Momentum- -Based Variance Reduction in Non-Convex SGD. In Advances in Neural Information Processing Systems, volume 32, 2019.
[12] Thinh Doan, Siva Maguluri, and Justin Romberg, Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1626-1635. PMLR, 09-15 Jun 2019.
[13] Thinh Doan, Lam M. Nguyen, Nhan H. Pham, and Justin Romberg. Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning. wwXiv:2002.02873. October 2020. doi: 10448550arrx::222222287.
[14] Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, and Justin Romberg. Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness. arXiv:2003. 10973, April 2020. doi: 10.448550/rxXi.22003.0999

---

[15] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimization with Markovian data. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages Jul 2022.
PMLR, 17-23
[16] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan, Ergodic mirror descent. 2011 1 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 701-706, 2011.
[17] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9412-9430 9439. PMLR, 23-29 Jul 2023.
[18] Nicolò Dal Fabbro, Aritra Mitra, and George Pappas. Federated td learning over finite-rate erasure channels: Linear speedup under markovian sampling. IEEE Control Systems Letters, 7: 2461-2466, 2023.
[19] Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding's Inequality for General Markov Chains and Its Applications Statistical Learning. Journal of Machine Learning Research, 22, 2021.
[20] Hyas Fatkhullin, Alexander Tyurin, and Peter Richtarik. Momentum provably improves error feedback! In Advances in Neural Information Processing Systems, volume 36, pages 76444- 76495. Curran Associates, Inc., 2023.
[21] Luca Greco, Pierluigi Ritrovato, and Fatos Xhafa. An edge-stream computing infrastructure for real-time analysis of wearable sensors data. Future Generation Computer Systems, 93:515-528, 2019. ISSN 0167-739X. doi: https://oii.rrg/ wttp//..0006........o www..e..208.....00..
[22] Kehua Guo, Tianyu Chen, Sheng Ren, Nan Li, Min Hu, and Jian Kang. Federated learn- ing empowered real-time medical data processing method for smart healthcare. IEEE/ACM Transactions on Computational Biology and Bioinformaties, 21(():869 879, 2024. doi: 10.1 10111//CCBBB222.3331131
[23] Hadrien Hendrikx. A principled framework for the design and analysis of token algorithms. In Proceedings The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 470-489. PMLR, 25-27 Apr 2023.
[24] D. Hill and B. Minsker. Anomaly detection in streaming environmental sensor data: a data- driven modeling approach. Environmental Modelling & Software,
2010.
[25] Hao Jin, Yang Peng. Wenhao Yang, Shusen Wang. and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 18-37. PMLR, 28-30 30 Mar 2022.
[26] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' Oliveira, Salim EI Rouayheh, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Pranceth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. CoRR, abs/19 1tss/992.04477, 2019.
[27] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. Proceedings of the 37th International Conference on Machine Learning, volume 1 119, pages 5132-5143, PMLR, 2020.
12

---

[28] Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated re- inforcement learning: Linear speedup under Markovian sampling. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 10997-11057. PMLR, 17-23 Jul 2022.
[29] J. Kober, J. Bagnell, and J. Peters. Reinforcement learning in robotics: survey. The Interna- tional Journal of Robotics Research, (2(11): 2013.
[30] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5381-5393. PMLR, 13-18 Jul 2020.
[31] Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer Series in Data Science. Springer, 2020.
[32] X. Li. J. Dunn, D. Salins, G. Zhou, W. Zhou, S. Schüssler-Fiorenza Rose, D. Perelman, E. Colbert, R. Runge, S. Rego, and R. Sonecha. Digital health: tracking physiomes and activity using wearable biosensors reveals useful health-related information. PLoS Biology, 15(1). 2017.
[33] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020.
[34] W. Lim, N. Luong, D. Hoang, Y. Jiao, Y.-.. Liang, Q. Yang, D. Niyato, and C. Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEÉ Communications Surveys & Tutorials, 22(3):2031 10633, 2020.
[35] W. Liu, X. Zhang, J. Duan, C. Joe-Wooog Wong, Z. Zhou, and X. Chen. DYNAMITE: Dynamic interplay of mini-batch size and aggregation frequency for federated learning with static and streaming dataset. IEEE Transactions on Mobile Computing, 7(23):76447767, July 2023.
[36] S. Lucia, D. Navarro, B. Karg, H. Sarnago, and O. Lucia. Deep learning- model predictive control for resonant power converters. IEEE Transactions on Industrial Informatics, 17(1): 409-420, 2020.
[37] Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, Reda ALAMI, Alexey Naumov, and Eric Moulines. SCAFFLSA: Taming heterogeneity in federated linear stochastic approximation and TD learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[38] O. Marfoq, G. Neglia, L. Kameni, and R. Vidal. Federated learning for data streams. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
[39] Sean Meyn, Richard L. Tweedie, and Peter W. Glynn. Markov Chains and Stochastic Stability. Cambridge Mathematical Library. Cambridge University Press, 2 edition, 2009.
[40] Montero, G. Femáádeez-Avilés, and Mateu. Spatial and spatio-temporal geostatistical modeling and kriging. John Wiley & Sons, Chichester, UK, 2015.
[41] Olusola Odeyomi and Gergely Zaruba. Differentially-priiee federated learning with long-term constraints using online mirror descent. In 2021 IEEE International Symposiun on Information Theory (ISIT), pages 1308-1313, 2021.
doi: 10. D0.1109/SIT45517..222 20..9598777...
[42] Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nathan Srebro. To- wards optimal communication complexity in distributed non-convex optimization. In Advances in Neural Information P Processing Systems, 2022.
[43] Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods, 2018.
2015
[44] Jiaju Qi, Qihao Zhou, Lei Lei, and Kan Zheng. Federated reinforcement learning: Techniques, applications, and open challenges. ArXiv, abx/2108. 1887, 2021.
13

---

[45] Jiaju Qi, Qihao Zhou, Lei Lei, and Kan Zheng. Federated reinforcement learning: techniques, applications, and open challenges. Intelligence & Robotics, ((1), 2021. ISSN 2770-3541. doi: 10.205177/r.2021.000
[46] Mónica Ribero, Haris Vikalo, and Gustavo de Veciana. Federated Learning Under Intermittent Client Availability and Time- Varying Communication Constraints. IEEE Journal of Selected Topics in Signal Processing, 17(1):98-111) January 2023. ISSN 1941-0484. doi: 10. 109/
JSTSP.200..3224590.
[47] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400- 407, 1951.
[48] Gareth O. Roberts and Jeffrey S. Rosenthal. General state space Markov chains and MCMC algorithms. Probability Surveys, (mnone):20- - 71, 2004. doi: 10.121411449578410000000
[49] Angelo Rodio, Francescomaria Faticanti, Othmane Marfoq, Giovanni Neglia, and Emilio Leonardi. Federated learning under heterogeneous and correlated client availability, IEEE/ACM Transactions Networking, 32(2):155-11460 2024. doi: 10.1 10.1109/NNET2203.3322222
[50] K. Sainani. The importance of accounting for correlated observations. PM&R, 2(9):858-861, 2010.
[51] J. Schwarz, W. Czarnecki, J. Luketina, A. Grabska-Barwinska, Y. W. Teh, R. Pascanu, and R. Hadsell. Progress & compress: A scalable framework for continual learning. In International Conference on Machine Learning (ICML), 2018.
[52] Skipper Seabold and Joseph Perktold, statsmodels: Econometric and statistical modeling with python. 9th Python in Science Conference, 2010.
[53] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
[54] D. Sirimewan, M. Bazli, S. Raman, S. Mhoandes, A. Kineber, and M. Arashpour. Deep learning-based models for environmental management: Recognizing construction, renovation, and demolition waste in-the-wild. Journal of Environmental Management, 351, 2024.
[55] Tao Sun, Yuejiao Sun, and Wotao Yin. On Markov Chain Gradient Descent. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
(56) Zhenyu Sun, ziyang zhang, Zheng Xu, Gauri Joshi, Pranay Sharma, and Ermin Wei. Debi- asing federated learning with correlated client participation. In The Thirteenth International Conference Learning Representationss, 2025.
[57] Trang H Tran, Lam M Nguyen, and Quoe Tran-Dinh. Smg: A shuffling gradient-based method with momentum. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10379-10389. PMLR, 18-24 Jul 2021.
[58] N. Van Kampen. Stochastic Processes in Physics and Chemistry. Elsevier, Oxford, 1992.
[59] Han Wang, Aritra Mitra, Hamed Hassani, George J. Pappas, and James Anderson. Federated TD learning with linear function approximation under environmental heterogeneity. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
[60] Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heteroge- neous distributed learning. In Advances in Neural Information Processing Systems, volume 33, pages 6281 6281-6292, 2020.
[61] Wenjing Yan, Kai Zhang, Xiaolu Wang, and Xuanyu Cao. Problem- parammeee free federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
[62] Jaehong Yoon, Wonyong Jeong, Giwoong Lee, Eunho Yang, and Sung Ju Hwang. Federated continual learning with weighted inter-client transfer. In International Conference on Machine Learning, pages 12073-12086 PMLR, 2021.
14

---

[63] Q. Yuan, H. Shen, Li, Z. Li, S. Li, Y. Jiang, H. Xu, W. Tan, Q. Yang. J. gg. and J. Gao. Deep learning in environmental remote sensing: Achievements and challenges. Remote sensing of Environment, 2020.
[64] Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations. 2022.
[65] Feng Zhu, Aritra Mitra, and Robert W. Heath. Achieving tighter finite-time rates for heteroge- neous federated stochastic approximation under markovian sampling, 2025.
15

---

Appendix
Contents
Introduction
2
Related Works
3
Problem Setup
3.1
Streaming Federated Learning
Markovian Data Streams
Convergence Analysis
Assumptions
Minibatch SGD
Local SGD
4.4
Local SGD with Momentum
4.5
Discussion
5
Numerical Results
Conclusion
10
Appendix
16
Preliminaries
18
A. I Pseudo-code for Minibatch SGD and I Local SGD
18
A.2 Notation
18
Markov Chain Preliminaries
20
Comparison with Existing Work
25
D Convergence Analyyis
27
D.I Minibatch SGD
28
Local SGD
................................
29
D.3
Local SGD with Momentum
32
D.4
Uniformly Ergodic Markov Processes
37
D.5
Characterization of C.o
38
D.6
Alternative Bounds for Stochastic Gradient Errors in the Non- -ta--Statonaay Case
39
Additional Experiments
41
Experimental Setting
Step Size Scaling with the Number of Local Steps
42
E.3
Additional Experiments on Synthetic Data
43
16

---

Limitations
45
17

---

A Preliminaries
A.1 Pseudo-code for Minibatch SGD and Local SGD
Algorithm 2 Minibatch SGD
Algorithm Local SGD
Input: initial model wo. global learning rate
Input: initial model wg. local learning rate 7).
7.
for t 0 to T 1 do
for t - do
for every client m E [M] in parallel do Receive the global model wt
for every client m E [M] in parallel do Initialize the local model:
(m.U)
for k: = 0 to
do
Wi
Wt
Compute:
for k = 0 to (m,k+1)
do
(m,,) Vm (wes (m..k) ((m.))
w/
(m,,))
9t
(m k)
It (m.
end for Communicate:
7 V fm
W
end for Communicate w/ (m,
9
En=o 9:
m.k
end for
end for Server update:
1 Σ m= Dr Aggregate: gt = M
Server update: W1+11 W4 79t
Wt+1 = Mr Em Wy
(m,
end for
end for
Output: ur sampled uniformly from 10: WT-1.
Output: ur sampled uniformly from wo. WT-1-
A.2 Notation
For clarity, we first recall some notations introduced in Section 3
We use [M]] {1..... M to denote the set of positive integers up to M, and [K]o = [0 1o denote the set of non-negative integers less than K. For any vector E Rdd we write (a:); for the i-th coordinate of
For every client m E [M], the data stream X,, = (x"")t tee is time-homogeneous Markov process defined on state space 22m endowed with the corresponding Borel a-field B,, and transition kernel. As an abuse notation, for all E N, and for all is E [K]o we denote by x! (m.,)) = x Kr-k and by
x²
2t (m,)k
the k-th sample and the set of all K samples used by client m during round kE(K]o
respectively.
(Xm)me[M) is a product Markov chain defined on (==X (--Xmee)) Pm, 8 Bm which, at each time step, moves independently on each of M coordinates according to the corresponding transition kemel. Its transition matrix is defined the Kronecker tensor product P
The level Markov chain
2 meeMM Pm. Similarly, to simplify the notation, we write
and x, (=t)
mE(M]
For Markov chain, we denote by PP, and E.g the corresponding probability distribution and expec- tation with initial distribution g. When g 5(x)), we simply write IPz and Ez, We also denote by
F, == 1 (mm,k) E [M] A: E [K], E (M)) the o-algebra generated by all data points received up to round f, and write [.[.] as an alias for the conditional expectation E[.
The following notation will be used throughout the Appendix:
Jt
1
Σ
Vnn
(wi x (m..k)
MK
mikk
vm
(m),)) (m,))) We a
9t
MK
18

---

A, [F (w,)] F",
E || wil [1]]
where we use m,, for EmE[M] Eke(K), unless explicitly stated differently. With this notation, the global update rule of Minibatch SGD is
W++1 Wt 79t.
the global update rule of Local SGD is
W+++ W2 Wr-9t.
where în Kn,, and the global update rule of Local SGD-M is
W[+1 +-
19

---

B Markov Chain Preliminaries
In this section, we introduce some basic properties of Markov chains on general state spaces. In the following, we let S be Polish space, and B denote the associated Borel o-field.
We begin with the following formal definition of transition kernels.
Definition B.1. If P {P(x, A), E Ω2 A E B} such that:
(i for each B, (., a non-negative measurable function on Q
(ii) for each x E Ω2 P (x.-) a probability measure on B,
then P is called transition kernel.
If is countable, then P(x, y) corresponds to the transition probability of moving from state x to state y in single step. However, in the case of continuous state spaces, may have P (ar, y) for all E Q hence the need defining P (æ, A) as the probability of jumping from the current state æ into subset A Q.
Now we are ready to define a Markov chain.
Definition B.2. A hongeoomgessous Markov chain defined on (Ω, B) with transition kernel P is sequence of random variables (Xi)ieN taking values in f2 such that for all i E N:
P (X+ X zi-1i 24-2: X1 21) (X, A X,-1 x4-1) P()
(2)
The Markov property can be expressed in the following equivalent form:
Proposition B.3 39 Proposition 3.4.3). Given a time-homogeneous Markov chain (Xi)ien (2, B), and f ~ R bounded and measurable function, then:
E (Xn+1, Xn42s...) Xn Fni Xn-1 In- X1 x1] Ex., [f X2........)
We recall the definition of stationary measure follows:
Definition B.4. The stationary measure of time-homo homogenooss Markov chain defined on (St, B) with transition kernel P is probability measure и such that, for all B:
(AA)= / ((E,),
or, equivalently:
dr = dr ((x)
Before formally defining the system-level Markov chain introduced in Section 3.2 need the following result on the measurability of the product of measurable functions.
Lemma B.5. Let (2,, Bi) and (I22, B2) be two measurable spaces. Let and g be two real-valued measurable functions on 22, and G2g respectively. Let h be velled function defined as:
4 x 92 - IR
(x1, h(21, -()))))))((())))
Then is B, @ Be-masuurabl..
Proof. Consider and defined as:
8: x 22 + RR
(I1, + f(x1, = f(x1)
20

---

and
9:Ω: S22 + R (21, + (( = g(22).
As f and are Bi-measurable and Bz-measurable, and are Bi 69 By-measurable. Indeed,
f-1 (la, +o0)) = / (la, +20)) x f22 E B1 @ B2, and 9 (la, +00)) = Un g (oo)) B & B2.
As [g. and the product of two measurable functions on the same measurable space measur- able 10 Proposition 2.1.7], we proved that h is Bi & B2-measurable.
The above result can be generalized to the product of more than two functions in a trivial way. We omit the proof for readability.
Now, we provide formal definition of the system-level Markov chain introduced in Section 3.2 We show that it is indeed well-defined Markov chain and characterize its transition kernel and stationary distribution.
Proposition B.6. Consider M time-homogeneous Markov chains X m E [M]. each defined on (Sm Bm) with transition kernel Pm and stationary distribution Ty, respectively. The product
Markov chain X, evolving on (2 mm Sm,: B defined as:
=x mmEEM Bix) with transition kernel P
P (x)
II ME[M]
Pm Am):
for all (Im)mE(M)) E Ω and A
X
Am
E B,
AmE[M]]
is a well-defied Markov chain with stationary distribution क mm(MM) [Mr] Tm-
x
Proof. By construction, it is easy to see that for each æ Q. P(x,.) .) is a product measure on B. hence the second condition in Definition B.4 satisfied. Also by construction, for every A B, P(., A) is non-negative, and Lemma B.5 shows that P(., A) B-measurable. Thus, also satisfies the first condition and is therefore well-defined transition kerne..
We still need to show that the Markov property is achieved. For simplicity, will do for the case M 2, but extension to any M < oo is straightforward.
Denote by Xi (X7) SEN and X₂ (X?)
the two chains. Indeed, the chains are independent, iEN
we have that:
[X],, Ai Ag (X-11x2111 (f-)) (x), (x],) X =+)) P pX? A₂ x2_ .f-1,...,X?? -
=P(X E A X = 1!_.....
Pi ( A1)
P2 A2)
=
P 1
(A1 x Az))
21

---

Since for every A E B, P(.. A) is non-negative and B B-measurable, direct application of Tonelli's Theorem gives the statement on the stationary measure of the product chain:
(AA)
mm
(A) =
II ME(M]
Tm (Am)
mE(M]
S dTM((M)) Pas AM)
dm (11,
[(.... I
P1 A1), ... P.s (rMs, AM) d (x1) dTM((M))
aam
1 di (x,
We recall the definition of total variation distance: Definition B.7. For two probabilities μa, v defined on (S2, B), the total variation distance between and is defined as:
|| uIlTy= = sup Ip(A) - v(A) = 2 / ldp - del.
AEB
Below, we give an equivalent definition of the total variation distance: Proposition B.8. Let (Y, 2) be coupling of μ and v, i.e. the marginal distribution of is μ and the marginal distribution of Z is v. Then:
|| v ll inf {PP (Y Z), (Y,Z) is coupling of p.v).
(4)
The coupling (Y, Z) that satisfies ||I v lrv (Y + Z) is then called the maximal coupling of μ and v.
The proof can be found in 48 Proposition 3].
Now we present some nice properties on the total variation distance with respect the stationary measure of Markov chains:
Proposition B.9. Lei X1, X2,... be a Markov chain on (St B) with transition kernel P and station- ary distribution then:
(i) For all probability distributions v/ defined over (22,
|| - v Pllly S =1|x-ul -ollv-
(ii) More specifically, advancing the chain will not increase the total variation distance to the stationary distribution, i.e.:
||pT (x. - (.)l & pp- (z, x()lrvv
(5)
(ii) Let d(n) 2 sup & |M (x,.) T (-)lrv- Then for μ varying over probability distribu- tion defined over (S2 B):
d(n) ssup |pP xl|rv.
(6)
and d(.) is sub-multiplicative, i.e.:
d(m n) d(m)d(n) for m. N.
(iv) For E [n], let μ4 and v4 be probability distributions (Ω,, B.). Define = == p4 and
v 8 i= Vi as two probability distributions on (S) XT Pr B ,__,B,, Then
we have:
|1 - vIlrV 5
|| - villTy.
1=1
22

---

Proof. The proof of (1), (tt) and (iéi) can also be found in 48 Proposition 3]. Here we present the proof for the last statements.
By using (4) it follows that
Mmmm 4m Fmllry Pm (Xm Ym):
where, for all m E [M], (Xms Ym) is the maximal coupling of Jmm m Define X = (Xm [m[M] and Y mmjas Then again by 4 we have
|| vllrv S P ( +Y}
M
U
Xm + Ym
m==
M
M
<
Pm (Xm # Ym) =
Σ m=1
M Vm VmllTV
m=1
which follows from the union bound.
We now give the definition of uniform geometric ergodicity, which is commonly used in the literature of stochastic optimization with Markovian data 37].
Definition B.10. Markov chain defined on (2, B) with transition kernel P is uniformly geometri- cally ergodic if:
sup |M (x.,.) - T/|rV S sep", rE
for some S Do and < 1.
Uniform geometric ergodicity implies that, regardless the starting distribution, the chain converges exponentially fast to its stationary measure in terms of total variation norm.
To end this section, we have the following results the mixing time of Markov chains.
Proposition B.11. Given a Markov chain defined on (S,,), let d(t) the total variation distance defined in (6) the mixing time T (e) and T are defined as:
T(E) = min(t: d(t) s {e).
(8)
T =1/44,
For any positive integer nI, we have
d(nr (c)) cn.
More specifically,
d (nT) n
and
(c) < [logs (T.
Proof. The first statement is direct application of 7 Simply by taking 1/4, obtain the second statement. Then with n 2 [log, (c-1)], d (wr) which implies that no 2 (6), hence the last statement.
Proposition B.12. Consider the product Markov chain in Proposition B.6 product Markov chain (see definitions in Proposition B.1l satisfies
The mixing time of this
T & ([log, M] + 1) max Tm
mE[M]
23

---

Proof. Let
d(t) = 2sup
pt (x, - π
refl
(t) = 2 sup
||PM (2. Tm
sefmm
By Proposition B.9 we have
M
d(t) S Σ (t(())
(9)
m=1
As in (5) advancing the Markov chain in time can only move closer to the stationary distribution. Thus, for all E [M],
(5)
dm
max mEIM
S
M
M
where 7 (c) min (t: d(t) s ef and Tm (c) min (t. (t)(t) S c). Hence, from
T (E) S max
mc(M)
M
Then from Proposition B.11 we have that, for all m E [M],
Ti (e/M)= < [loga (M/e Tm
Tm-
The lemma follows by taking 1/4 in the definition of mixing time 8
24

---

C Comparison with Existing Work
In Table [ we compare our results with existing ones in stochastic non-convex optimization with Markovian data in the centralized (or loken-passingl setting [ 17 setting. In the FL setting with i..d. data, we include the lower bounds in 42). along with some results [ For completeness, also report results in the literature of Federated Stochastic Approximation (FSA), which is analogous to stochastic optimization with strongly convex [65] or linear least-square [37] objectives.
Table 1: Comparison of algorithms in terms of communication and sample complexity to reach an e-stationary point for smooth, non-convex objectives.
Additional Constraints: GE: uniform geometric ergodicity (Definition B.10). ST: stationary Markov processes, BG: bounded gradient, BD: bounded domain, FS: finite state space, LT: lower bound on T. SS: sample-wise smoothness (Assumption 4.2p. BR: bounded Radon-Nikodyn derivative (Assumption B.2p. BH: bounded heterogeneity (Assumption [44)), BHO: bounded heterogeneity around optimum (i.e., the average distance between the optimum of the local objectives and the global objective is bounded, see 37 Page 4), LS: linear ceast-square objectives, SC: strongly convex global objective..
Additional Constraints
Algorithm
Communication
Sample complexity KT
Centralized
Thm.
δ
T
e
LAyo?
GE
(NS+++0)
MAG 15
Thm. 4.3]
BG, BD
MC-SGD 17
Thm. 5.3]
Lonto
+ (LAnto"oo
FS, GE, LT FS, GE, LT
c¹
11 [| +1 10 3
14 Thm. 3]
FL i.i.d.
Lower bound 42
Q LAe
Ω
LAng
Me
FedAvg-M
9 Thm. 1]
LAo)
0
LAno²
Me
FedAvg-M-VR 9 Thm. 2]
LAn
LAng
SS GE, ST, BHO, LS BHO, LS FS, GE, SC, LT
Me
FSA (6)
FedLSA 37 Cor. 4.5]
( log !)
Tmaz Mea
log
SCAFFLSA Cor. 5.2]
0 Olog )
Mea log
1
FedHSA Cor. 1]
(
O Tmma Mr²
Minibatch SGD
0 (ما0)
o LAnC
BR BR, BH, SS BR, SS
Upaddet
Ours
Local SGD
0 LAg
82 V
2+2
o( LanC (2 V (
Myu Afc
0²c²
Local SGD-M
LAn
LAnCawo Bupe Met
ignores logarithmic constants.
(1) In the centralized (or token-pen token-passing) setting, is the mixing time of the underlying Markov process.
(2) M and G are upper bounds the domain diameter and the gradient norm, respectively.
(3) w² is global optimum of the objective. Their proof also requires projection onto the unknown set that contains all the optima, and hides exponential factors in
(4) The setting for the lower bound requires other assumptions. We refer to the original paper 42 for a complete list. (5) The variance-reduction technique akin to the STORM algorithm [II) which relies on the sample-wise smoothness assumption (Assumption (4.2) and achieves the sample complexity lower bound in [42] Extending Local SGD-M with variance reduction attain this bound is promising direction.
(6) This setting focuses on stochastic approximation problems, with strongly monotone or linear operators. The rates presented here denote the complexity to reach an e-optimal solution. We omit problem-specific constants, except Tmax (the maximum mixing time across all clients) and M. (7) The authors present only the rate for the i.i.d. case.
We first give theoretical justification that clarifies why adjusting the step size alone offers limited leverage for controlling the gradient noise term. By standard decomposition from the T--smoothness condition:
25

---

E, (F - F(wr) 7/2(1 - 2, E/2 V VF(w)))l
+ + LE; 1199 -VF(w))]
and = E. |1s: VF be the bias and the variance of the gradient estimate. This bias arises from the Markovian structure of the data, since in the i.i.d. setting, E. Be[g,] = Fwwx) for all L. Observe that the bias is scaled by the step size y, Since the term [VV(( is also scaled by 7, the bias cannot be directly controlled by the choice of step size without sacrificing the reduction of the objective. Note that by Jensen's 's inequality, by I Us, hence the bias also contributes the "variance" term arising in our main results. This leads to a non-vanishing term involving the gradient noise o² in our results as the step size decreases.
Let b, = [91] - V (F(w))
We now give additional details of the techniques used in prior works to control this bias, and obtain vanishing "variance" term. In short, they introduce other pyper-parameters that can be tuned to make the bias vanish, instead of tuning directly the step size directly.
decompose the bias term into other terms containing delayed gradient. detail, in order to bound the bias, instead of taking the conditional expectation up to the current iteration t, they condition on a distant past iteration, which t minus some delay. This delay is later chosen to be scaled with 1/vT [7], or with the mixing time Te)) (see Proposition B...), where is then (the step size itself is tuned to be at the order of 1/TT).
First, 17 14 655
chosen to be scale with the step size [14 65
This technique requires constraint on the minimum number of iterations (or communication rounds)
T at the order of (Tmix) (this constraint referred to as LT in Table lb. As revealed in Table also contains hidden factors that can be exponential in Tmix. The bound for non-convex functions in [4] (Theorem in the arxiv version) also requires a projection onto the unknown set that contains all the optima.
14
Next, 3 15 use minibatch gradient estimates. Precisely, at each iteration, a random batch size is drawn from a truncated geometric distribution. Hence, a new hyper-parameter is introduced, which is the truncation threshold m. The authors of 3 [5] chosen be scaled with /T.
show that b, scales inversely with m. which is then
In the FSA setting, the analysis in (37 employs a blocking technique that sub-samples data sequences mitigate temporal correlations, using sub-sampling gap the order of the maximum mixing time Timax- Beyond assuming uniform geometric ergodicity, this approach also requires the underlying Markov processes to be stationary. Moreover, their analysis is restricted to linear least-squares problems.
We emphasize that the gradient noise term in our results can be easily made to vanish as T diverges.
Consider Minibatch SGD, under the setting of Theorem 4.5
By choosing K = O C. T
then we
Pp 57
have:
LAo o²) +
E |[F
s
T
which leads to the sample complexity:
(Lo Vo2j3
=T=
However, the above result shows no improvement in sample complexity compared to those reported in the main paper. We highlight that our complexity results match the best-known rates achieved in the centralized setting 3 15 [4], scaled by the number of clients M (see Table []]. while avoiding the commonly imposed uniform geometric ergodicity assumption. Instead, we rely on general mild assumption about the boundedness of the Radon-Nikodym derivative (Assumption 3.2) which allows for simple change of measures to handle the non-stationarity of Markovian samples when taking conditional expectation. Prior works rely heavily on the exponential mixing property to deal with -to-stationnritt. The analysis in B even yields a dependence on the square of the mixing time 3 Section I. The proof in [1] does not require uniform geometric mixing, but in the other hand relies strongly on the boundedness of the domain. We decide to choose K as independent of both the step size and the number of rounds T, because in real-world scenarios, the value of K can be dictated by other factors such as the data-arrival rate and the client's 's buffer capacity.
26

---

D Convergence Analysis
We begin this section with the following lemma that bounds the square emoor of the stochastic gradient estimate computed by M clients, each using K Markovian samples.
Lemma D.1. Let be the initial meusure of the system-level Markov chain defined in Section 3.2 !j
Assumptions 3.7 3.2
and 4.3 hold, then we have:
4C
E
MK Σ
vm (uns (mms)))))))) VF(WE)
Upp M K
Proof. By Markov's ' property
1
Σ fm (wrt (urizc km/kk))))) VF Vu(c))))
Ex
MK
|I mm (o
E
((((o)))
MK
Hence, by change of measures:
Ex
vm
(wi; (wg;zfmm.))
v (ww)
MK
mik
dP K-1
Even vmm (m) V (w:))
Ex
di
MK
dP (r K
r t-
.
E
Σ vm (wria(( V.
(Holder's inequality)
dm
MK
7,00
m.k
<
Coo
Σ
V.m
(wy: (ws: (m.)))
V ((we)
(Assumption 3.2
(10)
MK
m,k
We now utilize
43
Theorem 3.7], applied on the stationary system-level Markov process:
(wr:zt (m)))) - VF(w.)
E
mm
MK
mik
Ex
Σ vim
(wri 20 (().)) - F(wr)
MK
1=1
mirk
(4)
27
(11)
Er
Vm (w FF(W))
Kvpe
M
jml
4
1
Er
v. (wxiz) ( VF
K Kups
M
(10)
402
MKV
27

---

In (i), we apply 43 Theorem 3.7] to each of d functions:
h4 92 I,,
(x =
1
Σ
fm (wy xi (m..k)
M
m
In (ii), we use the fact that E,,,. V f (w;; :r] = Fm (w) together with the independence between clients' Markov processes. As such, the term Ex |1 V (w; z)
(F) can be seen
as the variance of the sum of independent random variables. Using Assumption 4.3 it follows that:
E
Σ
VF(w)
Σ
E ET
(m;(())) - V. (w))l
M
M
S Mo²
Hence, by plugging 11 back into (10 we prove the lemma.
D.1
Minibatch SGD
In this section, we consider the problem class F1 TT). We begin with the following descent lemma.
Lemma D.2. For the problem class Fi(T,,o,T) T), with constant global step size S L the iterates of Minibatch SGD satisfy:
27Coo
I (V 2
A+11 I SA,
Up MK
Proof. Since F is L-smooth,
(w1+11) & F (w;) + (VF (wr) u1++1 -wi) + L L
2 || wzll
(12)
= F - - (F F (w)). ...) + 2
|| well?
Note that the term F (w:). .t)) can be expanded as
(VF(w.), 2 VF (w:)1 + ? lg. VF (F(w)ll
?
2 |1
(13)
2/
? VF (w:)l + 3 g VF VF (wx)ll
|| 10:+1-0:11
w
2
Plugging
13) back into 12
subtracting F from both sides, and taking the conditional expectation,
then have
(F(:)) - F*) - IT, [IVF(w))] + IR, [1a. VF(w))]]] (14)
[F
F*] < E.
E, [1[11e11- -iil wil??
27
2
Then, with the condition 7 < J. the last term in 14 be ignored. The lemma follows by replacing the second term in (14) using L.ema D.I then taking the full expectation.
Now proceed to the proof of Theorem 4.5
28

---

Theorem D.3 (Theorem 4.5 in the main paper). For the problem class Fi T,T), with global step size y S 1/L, the iterates of Minibatch SGD satisfy:
Ao
Coo
E
0
7T
MK
Proof. The proof of Theorem D.3 follows directly from Lemma D.2 by rearranging the terms, then taking the average from 0 to T
+
Σ 1=0
E
VF (w))
(wx)
20o
4C
(15)
7T
u MK
Noticing that with dy sampled uniformly from wo. C0.....T-1..
T-1
v F (w))))
= E [IVE (1r (12)))
T
which concludes the proof.
Now we are ready to prove Corollary 4.6
Corollary D.4 (Corollary i. the main paper). Under the conditions of Theorem D.3 to achieve EllV [WT)F(1)) e², the required number local steps and communication rounds of Minibatch
SGD are:
K K ( UpoMe)) (
(
T.Ap 2
T=
Proof. By choosing
K > 8C
V/s Vpa M
4Ao
41.D0 22
T >
2
762
15 guarantees that E | ( se
D.2 Local SGD
For the analysis of Local SGD, we define
E,
W
kmm,)
we
MK
where & is the client drift observed in the local computation phase of the 1-th communication round.
We recall that the analysis of Local SGD is for the problem class F3 (L, a, 0, T). We begin with the following descent lemma.
Lemma D.5. If the local step size satisfies
<
10L82
L'
then the iterates of Local SGD satisfy
45
4ñAC σ2
40 Lij (62 + +0²)
A A,
VF (w))
98
Ups MK
98
29

---

Proof. We can adapt the proof of Lemma D.2 to Local SGD but with the update rule w/+1 = w nig:
Ee [F(F(WL+)) - FT] S Ex (ww)
=- - -, (V.:
F*]
2 Ex [lle- VF (u=:)]1²
L
||01+1 well"]
E.
2nj
2
(16)
E, (Fw))
F=]
0 E
|F (ux:)]]
+ t [13c
VF VF [12
2
|1g. 3ell3
+ n
Here in the last step, we use the triangle inequality, and the condition on the step size ń s 10L82 L.
Using the sample-wise smoothness (Assumption 4.2 yields:
E2 [1sx 3011"] = E
Σ
fm
(ur (m..)) (.mm))))
V.m (uz; (m),))
MK
mikk
(17)
L
(m,.))
we/ 11
MK
m.kk
E.
where Jensen's 's inequality is used in the last step.
The local drift &r can then be bounded as follows:
E
Σ
E2
W
(m.))
MK
mik
11 7m (w) (m)m));; 30 (mm.)))
E,
MK
Σ m.k
12k k
E,
V fm (m (mm))) I (m)
MK
==0
1/
k-1
Vm fm ( (mmmm ( (mmm) |
Es
MK
)=D
K-1
Σ
ΣΣR
(w) (m)))))) zot mm) 11²)
Ee
M
m,k j=0
(ufmmi);; x(( |2]
Σ
E,
vm mu
MK m.j
27j²
Σ
E4,
vm
(m (mm)))
Im (wr::((mm))) ) 11²
MK m.j
(w)e (we: (mm))) ||]
Σ E,
+
MK
m.j
(4)
4772
2T. 1T
+
Σ
Es
(ee::((m))) V Fm Pmr(we))
MK
mj.
2
+
Ex+
/ (wm))11]
M
(8i)
2 Σ
< 20 2
1)
E,
+
Es (Vm
M
m
30

---

In (2) we use the sample-wise smoothness (Assumption 4.2 and the triangle inequality, and in (di) we use the uniform bound on the noise of the gradient estimator (Assumption 4.3)
Therefore, we have:
4
Ex
(18)
2L r/2
M
Plugging 17 and 18 back into [66.. together with Lemma D.I and the condition on the step size
then yields
407C
[,[F(w+11) - = & (.(F(w))
F*
E
V (F((w))
2
UpaMK
40
0²
+
E,
v Fm (ux)))
9882
M
By taking the full expectation and using the heterogeneity assumption 4.4 we have that:
A++1 S A.
? 80
1
n688
[[IF((())))
E
(19)
2
98
Up
40ij
(2
o²
98
82
Using the condition on the local step size on the second term in the RHS of (19 proves the lemma.
We now prove Theorem 4.7
Theorem D.6 (Theorem 4.7
in the main paper). For the problem class Fa 0, 0, T), if the constant
step size safisfies
<
LK82
L
then the iterates of Local SGD satisfy
Ao
Coo
Lan (02 + 0²)
50
Mp
82
Proof. By rearranging the terms in Lemma
D.5 and taking the average from / = 0 T - 1:
Σ t=
[IVE
E |IF
98 Ao
392 Coo
40 Lij (0² + +
(20)
45 Tj
45
MK
45
52
We conclude the proof by replacing r n and noticing that with de sampled uniformly from Wo.
WT we have
E
v
(wm)) EE [IVF (wT)))
T
t=0
We now establish Corollary
4.8
which characterizes the communication and sample complexities of
Local SGD.
Corollary D.7 (Corollary 4.8 in the main paper). For the problem class Fz O, 5, with step size
822
S O
KL +
KL82
the required number of local steps and communication rounds for Local SGD achieve E[[[F((or] are given by:
T
LAo
8 + 02
))
K
T = O
82 V
M
2
82.2
31

---

Proof. By choosing
392 o
2
15
2
3
8²22
A
8 KL (02 + 0²)
10K
98 Do
98 LAO
(108*) V 8 + 0²
T ス
2
15 nk²²
15 2
3 8
20 guarantees that E
| || S
D.3 Local SGD with Momentum
All the proofs in this section are for the problem class F2 (L, T.T. Recall that the update rule of Local SGD-M can be written W++1 Wy Yu++1- For the theoretical analysis of Local SGD) with momentum, we introduce the following notation:
E. E
VF (w)) - 11+111
1 Go M
Σ VF (woo)1?
We begin with the following descent lemma. Lemma D.8. With global step size
1
7 s L
we have
A
<
S.
B |IF (wx) )1
+ -= 2
Proof. Similarly as the proof of Lemma Wt 7//+1 we have:
D.2 with the update rule Local SGD-M: we+1
( L
A4 A B (w)))
+
+ 22 +
2
2
Applying the condition y proves the lemma.
We have the following recursive bound on E,:
Lemma D.9.
With condition:
B
7 x /60
We have:
14
B |VF (w]-1)]1] + 63E
[13. VF (w:))l 6
E S
1 +
15
Proof. We have the following decompasition:
F (wy) - U+41 = (1 (3)
(VF (wx) vz) -
Σ
V.n Evim
(wi; ar smm.mi)) VF (wi)
.KK
m,k
B
Σ Vim (w (mm.A);...(0)) (mm.)))
Vim (w): (ot::.mmmkk))
.K
= (1 - 8) (VF (w.) - -2t) -2)) -3 vF(w:)) - (g. - gt)
32

---

Hence, by using Young's s inequality:
1 B
2 13
(a b)² 2
a² +
1+
b².
We have:
1+ 8
(1 3)² |VF F (wy) - vell?]
E S
2
+ 1 +
B'B [ - gt) - (ā) - VF (w)) (w)) )>1
8
3
(1 9) E |VF (wi) - vell'] +2 2 1+ 2 3 |l - VF VF (wx))??
1+
2
2
+ 2
1
8² 1.
8
Here, in the last step, we use the triangle inequality and the sample-wise smoothness (Assumption 4.2).
Now, since we have:
VF(w,) - 0 VF((,,1)) u, (VF(w,, -FF()))))(( E (VF(w;)) - VF(We-1)).
Using again Young's inequality, we have:
8 5(1 + 2) (1 (1-3)² 3)
[11
8 2 1
1+ 2
E (VF(w.)) VF (w)=1))²
3
+ 6,3 |13. VF (1
+ 639L25
(21)
2L
(1- B)
E
[w wi w(-11?? 63E
| VF (w))1l 6
3
1 + 3 < 3: in the second inequality we use Here since 8 < 1, in the first inequality
(1
8 2 2 3) s (1 - 3) and 1 + 2) (1 + 3 (1 B)
2 g together with the smoothness of
F.
Furthermore, by the update rule, we have:
||w, wt 11/ = B2B ||1-- [1]]
(22)
< 2 + 2T
|IF (wl-1)1
Plugging back into 21 we have:
2,2
E, < 1 - 3 +
E, E +
[IVF(u;-))lf) + 68E [loe - VF (wx))1]]
+ 633.2
8
B
We conclude the proof by using the condition on the global step size
Next, we continue to bound the drift &
Lemma D.10. With the following conditions:
n L <
2
33

---

We have:
S (n,3KK) o² + 32 (2 33 E B) K)
( | (w (wx=
+ +1n
Σ E M m
|VV (w)))
Proof. We start by using Young inequality (a + b)² (1 (++-1/ )2²))a a² KT? Then, for any
0 S k S K - we have:
E
Wi h)
we 19/ 1
1 K 1
E
W (m. 1)
+ KE
w
(m 1)
w
(m.
W [m.k 11
22
1 + K
E
+ KipE
1), x
(m.
+ (1 - 33 e0)
Now we have the following decomposition:
fm (w, (m.k- 1), 10
+ ())
U) = 3) Ur FV (w,)
/ w ( :m 1) ( Vnn (ussa((md-1))
fm (us:z(m Vmm (wx)
Hence, by using the triangle inequality, we have:
(m,k)
us 1
W (m. -wel we/"
E
W
1
E
K
+ 4n KE
V !i (1) : fm.m
vmn (( (m.
|. (w.: (m Fm (we)
+ 3 [|VF(W))]
+ +n7² (1 - 3) (EI-++ VF (w) =)0=))
1 K - + 3² E | (ommmt-))) w/ 1|3
+ 4KA.
with
A = 32
(o² +
| (wx))l + 2n² (1 (3- (5 + E [IVF (w>-1)
Here, we use the sample-wing wise smoothness and the uniform bound on the gradient noise in the last step (Assumptions 4.2 4.3).
Unrolling the above recursion, with w (m,0) Wt, we have:
E
w
km,)))
we 1']
4KA
1
1
K-1
1=0
34

---

With the condition on 77, we have that 4n formula, we have:
1 K-I-
Hence, by using the geometric sum
K
1
1
4m
B
5
+
R-1
2
K-1
K-1
K-1
(1+
-1
2
K
K -
2
k-1
1+
2
K
6²
S 2 (K - 1) s 4K.
We conclude the lemma by taking the average over K and M.
In the proof of Local SGD, we have to use the heterogeneity assumption to bound the term 1 M Σm E FV (w=))l The use momentum allows us to build a recursive bound for this term by the following lemma.
Lemma D.11. We have that:
1 M
Σ E VF (w()) 3G
2
E +
IVF (VF(()))
j=d
Proof. By using Young's inequality and the smoothness of Fm. we have that:
V (w=))l
<1 B E
V Fm (w: (w:-1)l? )|
+ (1 a 1) L | - W 113
< E E
VFm (wa-1)ll =|1
+2 1) (E E [IVFF(t))))) (wx-))))))
By unrolling, we have:
E VFF (wo))p) S(1 a) E VF (wo)]l] +2(1+a a- >
[ + E (1)F(1))) (1 ())-)-
j=
t-1
< VV (wo))l
+ at (1 + 2
Σ
E + E [VF
j=0
By taking a = 1-1 and taking the average over m E [M]. we conclude the lemma.
Lemma D.12. With the following conditions:
Co
L.D.
1 A
nKL <
A
23
120 ps MK3
360,33TGp
225 (1 B)
525 BYLT
7 5
V60 L
We have that:
T-1
L
Cooz
T-1
Σ
E,
+
+
| (w.))l
2 3T
Ups
MK
1=0
35

---

Proof. By Lemma D.II
we have that:
T-1
1
T-1
1-1
1
E IV Fm (wx))l
S3TG, + 6,2
(1 + 1)
Σ
[ E
M
1=
1=
j=0
(23)
T-2 Σ
E + E [1vF(w))]1
S3GG + 12 (2
Plugging 23 back into Lemma D.10 we have:
1.7, 2
Σ & <9637 (nK) (o² 3Go)
T-2 + 3 (1 3))² 1152 (xKL3) (xLT)²
2
Σ
E E |VF (w,, (Pt))
By condition on the step size, we have that B s 15
2
Therefore, plugging 24
back into Lemma
D.9
by noticing that E
|VF (w-1)l?]
0, gives:
T-1 Σ
T
T-2 2 E
14
E
3
Σ
E
VF (1)))
15
15
1=0
1=0
+ 63
E [1lee - VF(w;)]
963T (nK (o²+3G))
t=
T-22
T-2
28
Σ S
Σ E
|VF
T-2
$
(1-3))
4
8
Σ E +
Σ E 1=
1=-1
T-1
639
Σ
E |1
vF(W)]1
96,3 (nKL)) (o² (o²+3Go))
By rearranging the terms, we have:
T-1
T-1
15 T-1
Σ
E
5 331+ +
Σ E |VF (w:) [1))(
+
E 11..
VF (w:))l²
43
2
(25)
A=
1=
120T (3K)3) (o² + 33o).
With the condition on the step size, we have:
L2) < C2
Mp
(26)
360 (nKL3)2 Gu < LAo
BT
And by the law of total expectation, we have:
llg.
[F(W))]]
E E, 1g. - [F(w)))
4Coo02
(Lemma D.1
(27)
Ups MK
36

---

Hence, by plugging 26 and
27
back into 25 we have:
r-1
5E
LAo
310
1
T-1
- 1= 4
V (wx)ll²
+
T
3T
BT
MK K
4
1=0
Finally noticing that if we initialize vo = 0, 3-1 = E F. Hence, we prove the lemma.
IVF (wo) 112
S 2L by the smoothness of
Now we are ready to prove Theorem 4.9
Theorem D.13 (Theorem 4.9 in the main paper). For the problem class F2 0, T), with the following conditions the step sizes:
1
Co
LAo
1
NKLSO
A
3
MK
B8TGG
(1 3)
ByI.T
8
7
the iterates of Local SGD-M satisfy:
[Ao
Coo
[VF(tT))
3T
Vppa M K
Proof. By rearranging the terms in Lemma D.8
20.
1
Σ
E
S
Σ
E,
T
yT
T
t=
Using the condition on and replacing
# Σ. E. by Lemma D.12 proves the theorem.
From Theorem D.13
derive directly the communication and sample complexity of Local
SGD-M.
Corollary D.14 (Corollary 4.10 in the main paper). Under the conditions of Theorem D.13 the required number of local steps and communication rounds for Local SGD-M to achieve E[][VF(@x)] are:
(Coo0
Cxoo2 MpeMe)
(T=O(TA)
T.Do Be
K K=
T=
Proof. The proof is direct consequence of Theorem D.13 and follows the same steps in the proof of Corollary D.4
D.4
Uniformly Ergodic Markov Processes
A common assumption in the literature on Markov SGD is uniform geometric ergodicity (see Definition B.10).
Assumption D.15. The system-level Markov chain is uniformly ergodic. In particular, for any N, we have:
sup
pm (x.-) Tllry sep", #E
for some < xo and < 1.
This assumption, which characterizes exponentially fast convergence to unique stationary measure of Markov processes, is widely used in the literature of Stochastic Approximation with Markovian noise 3 37 [5]. We highlight that in the main paper, we only assume that the clients' Markov chains converge to unique stationary measure, without any further assumption convergence
37

---

speed. In this section, we show that our analysis can be easily extended with this additional stronger assumption. In particular, from Proposition 3.4], we have that:
Mps S 2T,
where T is the mixing time of the system-level Markov chain (see Proposition B.11 for definition). According to Proposition B.12. we also have that:
[og + 1 Tmax:
where Tiaxx
max Tm the maximum mixing time of clients' Markov processes. mE[M]]
Hence, key implication of the uniform ergodicity assumption is a characterization of the pseudo- spectral gap in terms of the mixing time, That is, 1/Mps is replaced by r in the proof of Lemma D.1 As consequence, for Minibatch SGD, Local SGD, and Local SGD-M, the new required number of local steps is:
CooTmaxx 2
K K=
The communication complexity remains unchanged under the additional assumption of uniform ergodicity.
We note that uniform ergodicity can also be used to characterize Coc. is discussed further in Section D5
D.5
Characterization of Coo
A key quantity in our analysis is Coo. which impacts the required number of local steps. In particular, recall
dP(x,
Co sup sup
xeft
dm
When [2] < co, Coo is given by
P(x,y)
max Coo
ayeEi
(t))
which can be explicitly computed for the case of two-state revensible Markov chains with Ω {0, 1} satisfying
P(x, v)
P. 1 1-p, p,
x y x
y.
In this case, x(x) (0, 1). It then follows that
- C.. = 2 maxmmal11ppp
which is minimized for p = 3. corresponding to independence between consecutive samples from the Markov chain.
For Markov chains with finite state space, where [S2] < co, Coc can be bounded using the uniform ergodicity assumption in Assumption D.15 For an arbitrary æ E Ω, under the assumption P(z,)) -) <
π,, observe that
P(r, TTy)
Σ P(z, v) =())
Σ (1)
2
BEN
ZEO
1
P(x, y)
2
Tiin
max yED
T(y)
P y)
1)
2
Tmin
max yE
n (
38

---

where Tmin min (V)) It then follows that for arbitrary 2 E S2,
P(x, v)
P1). T|
max yell
(V)
Amin
Choosing x arg maxugs maXyen
Plu.w) and applying the uniform ergodicity assumption in x(x)
Assumption D.15 we then have
2cp
Co S
+
min
For finite Markov chains under the uniform ergodicity assumption, 43 Proposition 3.4] provides a relationship between the total variation distance and the pseudo spectral gap. Applying 43 Proposition 3.4] then yields
(1 Yps) (2- )2 (2-1/1pa//2
Coo
Tiin
1/Tmin -
Tmin
D.6 Alternative Bounds for Stochastic Gradient Errors in the Non-Stationary Case
In Lemma D.1 we obtained bound on the stochastic gradient error in terms of Coo by choosing the stationary distribution as reference. In the following lemma, we obtain an alternative bound on the stochastic gradient error by choosing a different reference distribution. This bound can distinguish between stationary and non-stationary Markovian data processes.
Lemma D.16.
Let be the initial distribution of the system-level Markov chain defined in Section 3.2 We assume that for every t E N, and every I E Qt P(x,) is absolutely continuous with respect to uPKt, and we define:
dP((x,))
C..t sup sup aeft
(28)
If Assumptions 3.7 and 4.3 hold, then we have:
4C 4Co.0²
E2
Σ Sm (1ee: VF(w:)
MK + +2 l|ghtt
- -
MK
m.k
39

---

Proof. Let p be a distribution such that pPkt
< and < We then have:
Ex
Im (w):
(o) (((e))
MK
mikk
dP x (
Pyps
1
Σ
Vin (uss:at
V F(w))
d(qpir)
MK
m,k
2
dP ( K-1
).)
Eggas
Σ vm
(w))
(Holder's inequality)
d dgg
MK m.k
1,00
Cype
Σ
vmm Du
V VF(we))
(By using (8
MK
m.
Σ
vm
(1 (mm.)))
F(w+)
MK
m.kk
Cai (
1
Σ vm (ursa((m))) VF(w)
d (qpkt) dp
dm
dp
MK
dp
1C MK
+ ,0 llapkt T||rv
In the last step, we follow (11) to bound the squared error of the gradient estimator at the sta- tionary measure and Assumption 4.3 together with the definition of the total variation norm (Ap- pendix B Definition B.7
Observe that in the stationary case, for every E N the additional term || x =||rv is zero, and Cg. C.o. and we recover the bound in Lemma D.I On the other hand, in the non-stationary case, while the total variation norm can be bound using [43] Proposition 3.4], obtaining a tighter bound than the one in Lemma D.I challenging due to the term Cg.t-
40

---

E Additional Experiments
E.1 Experimental Setting
All the experiments performed in this paper are run entirely many different CPU clusters provided by the Grid' 5000 testbed, with different types CPU (e.g.. Intel Xeon E5-2698, Intel Xeon E5-2620, Intel Xeon E5-2630). All the software packages and datasets used for experiments in this paper are open-sourced, with the exact version provided. For the main experiments, we use 10 different random seeds, and report the average together with the 95% confidence interval. Further detailed instructions to run experiments are provided in supplementary material.
Computing environment:
we evaluated the performance of Local SGD, Minibatch SGD, and Local SGD with Momentum on the Beijing Multi-Site Air- Quality dataset. In this section, we provide details on the data preprocessing and the learning problem.
In Section
The Beijing Multi-Site Air-Quality dataset consists of hourly measurements from 12 weather stations across China, collected between March 2013 and February 2017. In particular, the dataset consists of measurements of 6 pollutants (PM2.5, PMI0, S02, CO2, CO, and O3) and 6 meteorological indicators (temperature, pressure, dew point, rainfall, wind speed, and wind direction). In total, there are more than 400,000 measurements of each variable.
PM2.5
TEMP
S02
400-
5000
19000
24000
32000
8000
16000
24000
32000
3000
16000
24000
32000
Figure 3: Original time series for PM2.5 pollution, temperature, and SO2 pollution. Observe the periodicity the data indicating seasonality.
X122
5.0
1.6
2.5
0.6
-0.8
8000
36000
24500
8000
16000
24000
32000
8000
16000
32000
Figure 4: Time series PM2.5, temperature, and SO2 with seasonality removed, which utilized (along with the other pollution and meteorological variables) for the experiments.
As illustrated in Figure 3 the dataset has a strong seasonality effect. As we seek to experimentally validate our theoretical analysis, which requires convergence to a stationary distribution. As such, estimate and remove the scasonality via the STATSMODEL python package (52). We then drop the PM10 and WD (wind direction) features, fill in the missing values with their average values during the last month, and normalize the data. In Figure 4 plot some measures after these steps of preprocessing.
The focus of our theoretical analysis is on Markovian data. Pollution and meteorological data are commonly modelled via Markov chains. To verify that a Markovian model relevant to the dataset, it is necessary to verify that there is dependence between samples. To this end, in Fig. we plot the autocorrelation of the PM2.5 concentration time series. Observe that while the autocorrelation decreases the lag increases, which indicates mixing. On the other hand, the autocorrelation with
41

---

<10-1
x30
x10
1.-
5.0
1.-
0.0
8.9
-2.5
Figure 5: Auto-correlation PM2.5, SO2, and temperature time series with seasonality removed. Observe that, particularly for the temperature, there are high levels of correlation at small lags, indicating dependence between adjacent samples.
Actichongxin
Dingling
Chanaping
60-
dewp
6,8
0vAp
9.8
5emp
0.8
n22
0.6
3.
0.
pn2.5
84
pm2.
94
pm2.5
04
pws
52
20e
0.0
3.
400
tepp
-02
temp
temp
xspm
-0.4
tono
Figure 6: Correlation matrix of the data at three stations.
small lag remains high, indicating the presence of dependence and the need for non-independent and, in particular, Markovian models for the evolution of the PM2.5 concentration.
The learning problem we consider is linear regression with the PM2.5 measurements as the response, and the meteorological variables and the other pollution variables utilized as covariates. From the correlation matrices in Figure 6 we can see that there a strong correlation between PM2.5 and CO, DEWP (dew point), and NO2, while other features are less relevant. Hence, we consider the following loss function:
[w; (x, u)) (w- x y) Ar(w),
d=
w
r(w) = 2 1=1
w
where y E IR is the PM2.5 measure, R99 is the vector of other variables measured the same hour, and w E Rd is the model parameter. The non-convex regularizer encourages small weights for irrelevant features.
To allocate the data over different clients, for each client we randomly sample n E {6, 12) consecutive months from the first 36 months from all the sites with seasonality removal. The remaining 12 months are reserved for testing.
E.2 Step Size Scaling with the Number of Local Steps
We remind here the upper bounds for Local SGD in Theorem 4.7
Do nK
LKn (62 + 022
E
[VF((T)]
< 5o
MK
82
In Section we perform experiments with fixed local step size to better illustrate the heterogeneity effect on Local SGD when K increases. In this section, we perform the same experiments in Figure but with the local step size 77 scaled as b/ K, where b {0.1, 0.01). This replaces the fixed
42

---

Table 2: Mean gradient norm of Local SGD
7
K 10
K 50
K 100
0.1/K
0.00506 0.00076
0.00307 0.00041
0.00233 + 0.00030
0.01/K
0.01248 + 0.00279
0.00921 + 0.00210
0.01190 + 0.00245
Local SGD
Minibatch
10
Local SGD-M
10-3
10--
10-5
10-3-
10
1000000000 20000 30000 40000 50000 Communication rounds
1000 2000 3000 4000 5000
100
200
300
400
500
Communication
Communication rounds
(a) 10
(b) K 100
(c) K = 1000
Figure 7: Gradient norm as a function of the number of communication rounds for Local SGD, Minibatch SGD, and Local SGD-M, with 10 clients, 7 0.01, // 0.001, 3 0.1, and the mixing time for every client Tm = 100.
local step size = 0.01 in the original experiments. We report the results after 10 different seeds together with the 95% confidence interval in Table
From the above upper bound, we note that, for moderate values of the initial suboptimality gap and heterogeneity:
If K is large, then the bound is dominated by the heterogeneity term.
. If K is small, then the bound is dominated by the variance term.
Choosing the step size as n x 1/K leaves the first and third error terms unchanged with K, while the second term decays with increasing K. Hence, when this second term dominates for small K, the gradient norm V FV [w)]l should decrease before flattening out at positive plateau. The patterns shown in each row align with this qualitative prediction.
The comparison of the two rows also supports the fact that the "variance" term cannot be controlled by the step size, which was discussed in Appendix [ Indeed, for fixed K, reducing the step size by factor of 10 does not improve the performance. On the contrary. the gradient norm appears to increase for smaller 7). This can be explained by the first term the bound, associated with the suboptimality gap, which scales inversely with the step size.
E.3 Additional Experiments on Synthetic Data
In this section, experimentally evaluate the performance of Minibatch SGD, local SGD, and local SGD-M on the linear regression problem with non-conver regularization with synthetic Markovian data. In the following experiments, we study the average performance over 10 random seeds in setting similar to 15
Let ll (a, b) denote the uniform probability distribution over [o,, b). The data stream for each client m generated by a two-state Markov chain (f(m.)) E [K] 1 N), where the probability of jumping from one state to another is (0, 1), with mixing time Ô(1 ((1/p). We note that for reversible Markov chains, as considered in these experiments, the mixing time is related the spectral gap via
< 2T
Vps
Associated with each state {0, 1) are the vectors Vm,, 10 which are drawn randomly for each seed according to 24 (0, 1). For each seed and i {0, 1), half of the optimal parameters Wm,s R take the value w 20 1), while the other half take the value wi ~ (11
43

---

10a
10
10
10
M- 100
10
10
10:
M-
10-1
10-3
10-2
10-1
10
10-1
10
10
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000 3000 4000 5000 Communication rounds
Communication rounds
Communication rounds
(a) Local SGD
(b) Minibatch SGD
(c) Local SGD-M
Figure Gradient norm as a function of the number of communication rounds for Local SGD, Minibatch SGD & Local SGD-M, with 0.01, = 0.001, 3 = 0.1, À = 0.01, Tm 100 for all m and K 100.
10-1
10
10-1
Local SGD
10:2
10
Minibatch SGD
Local SGD-M
10-2
10-3
10-3
10-4
10
10
10-4
10-6
10-6
10'
10P
10'
10!
10a
10a
101
10a
10a
Mixing time
Mixing time
Mixing time
(a) K 10
(b) 100
(c) K 1000
Figure 9: The gradient norm of the last iterate algorithms as a function the mixing time with 7 0.01, 0.001, 3 = 0.1, X = 0.01, 100 clients and different numbers of local steps.
The samples associated with client m correspond to the observations
mf.fm. V ((m.)) c, km,
where E, (m,k) ~ ((0,0.01), E N,m E [M] l E [K].
Since the Markov chain (i) (m.,)) k E |K] E N) is symmetric, the stationary distribution for every client m is uniform; i.e., Tm Tm(() Tm 1/2. The local objective function for each client m is then given by
- (w wm.1) ) Vm.1 2
(w))
+ (w wm.2) " Vm, 12
+ Ar(w),
where rww Σ
10 wid
is a non-convex regularizer often used in robust non-convex and
T+
smooth stochastic optimization 577
20
Impact of Heterogeneity and Number of Clients: Figure 7 and confirm that synthetic data experiments replicate the trends observed on real-world data: Local SGD's ss performance degrades under heterogeneity, while all three algorithms improve with more consiitentt supporting our theoretical analysis.
plot the gradient norm of the last iterate of Minibatch SGD, Local SGD, and Local SGD-M as a function of the mixing time, As predicted by our analysis, the performance of Minibatch SGD, Local SGD, and Local SGD-M degrades when the mixing time increases.
Effect of mixing time: In Figure 9
44

---

Limitations
Heterogeneity and Smoothness Assumptions: In our work, we have imposed the bounded gradient dissimilarity (BGD) assumption. As noted in Section 4.1] this assumption was first introduced in [27] and has since become ubiquitous in the analysis of local SGD [64]. We highlight that the BGD assumption includes the assumptions in [60] [3]. While weaker heterogeneity assumptions exist in the literature, these are not straightforward to apply for non-convex objectives where the BGD assumption is standard (30]
Statistical Assumptions:
The focus of this work is time series data with temporal dependence modeled via Markov chains. These models are widely used in many areas of statistical modeling, ranging from physical and biological systems queuing systems. On the other hand, Markovian mod- els are not the only common time series models, and, for example, do not include all autoregressive models.
We also assumed that the stochastic gradient estimates have bounded errors. Nevertheless, this is a common assumption in stochastic optimization with bounded noise.
Optimality: At present, tight lower bounds for Markovian data are not known. As such, we were not able to establish the optimality of our algorithm. Instead, we have compared with the lower bound in the i..dd setting. We are only able to assert that in this setting, Minibatch SGD and Local SGD with momentum can least match the lower bound on the communication complexity, but at the cost of performing more local computation (larger K). Nevertheless, we note that the 1/e" lower bound in the i.i.d. setting is achieved by more complex algorithms than those considered in this paper. For example, Algorithm 2 in [9] utilizes updates round that require evaluation of the gradient at the global model in round 1.
A challenge numerically understanding the performance of FL al- gorithms with Markovian sampling is the strong impact of the mixing time of the data-generating process. real data sets, such as the pollution data in Section the mixing time cannot easily controlled, which means that comparison of the algorithms in different regimes is more challenging. To study the impact of the pseudo spectral gap or the mixing time, we instead relied on synthetic experiments in Section E.3
Experimental Validation:
45

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers
integral part of your paper submission. They visible the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation.
While "[Yes]" is generally preferable to "[No]" ", it perfectly acceptable to answer "[No] provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" " or "we were unable to find the license for the dataset we used"). ) In general, answering "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide theoretical proof' for the claims made in the abstract in Section 4
In Section we experimentally validate our analysis real-world time-series data.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In Section and Section 4.1 we provide discussions about our assumptions, with regard to other assumptions that have been used in the literature. In Section 4.5) from our theoretical analysis, we point out some limitations of FL algorithms when applied to Markovian data. A separate section about limitations of work is given in Appendix
Guidelines:
46

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We clearly state set of assumptions in Section 3.2 and Section 4.1 Our main theoretical results are presented in Section with explicit references to the relevant assumptions and detailed proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Details about computing environment and experimental settings are given in Appendix [E.T Code is provided the supplemental material with detailed instructions.
Guidelines:
The answer NA means that the paper does not include experiments.
47

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-soures dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is provided in the supplemental material together with sufficient instructions reproduce the main results of the paper. The computing environment is described in Appendix E.I We use an open-source dataset distributed under the CC BY 4.0 license, cited in line 302.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ piaips.cc/public/guuddee httppp//il..guiieeee//d/deeaabaa
/CodeSumeeeeeeeeeceeeee ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
48

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all the experimental settings in Appendix E.1
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We run each experiment with 10 different random seeds and report the average values together with the confidence intervals.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the computing environment and all the details about the experi- mental setup in Appendix E.
Guidelines:
49

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Our paper theoretical and analyzes convergence properties of Federated Learning algorithms. It does not involve human subjects, personal data, application domains with known ethical concerns. Therefore, the work complies with the NeurlPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Our paper focuses on the convergence analysis of Federated Learning algo- rithms. It does not propose or implement any specific application, dataset, or deployment scenario. As such, the work does not have direct societal implications or foreseeable negative societal impacts at this stage. Any potential societal effects would depend on downstream applications, which are outside the scope of this study.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
50

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper provides a theoretical analysis of convergence in Federated Learning algorithms and does not introduce new models, datasets, implementation methods that could be directly applied in practice. The results are abstract and foundational, with no foreseeable misuse potential. Therefore, specific safeguards necessary.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The experiments carried out using open-source dataset distributed under the CC BY 4.0 license. We cite the original paper that produced the dataset in line 302.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, snperswithcode com /atasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper theoretical and does not release any new assets. The code is provided in the supplemental material under the MIT license with fully detailed instruction.
Guidelines:
The answer NA means that the paper does not release new assets.
51

---

Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper is theoretical, hence it does not involve any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper is theoretical, hence it does not involve any crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as institution conducting the review.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
52

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non non-standard components.
Please refer to our LLM policy (https://neurip:: /ttp://pp.ccc//offfeeeee//////// for what should or should not be described.
53


Reviews:
[{"review_id": "HiTUz4jfob", "reviewer": "Reviewer_iDzF", "summary": "The paper presents a rigorous theoretical and empirical study of federated learning (FL) under Markovian streaming data, a realistic and understudied scenario in FL. The key contribution lies in providing convergence guarantees and communication/sample complexity bounds for Minibatch SGD, Local SGD, and Local SGD with Momentum (Local SGD-M), all under non-i.i.d., temporally correlated data generated by Markov chains. The work is well-motivated, theoretically sound, and empirically validated.", "questions": "1. The paper evaluates performance on a single real-world dataset (air-quality time series). How generalizable are the findings across domains?\n2. You suggest that momentum-based methods (SGD-M) mitigate heterogeneity without requiring control variates (e.g., SCAFFOLD). Could you provide direct empirical comparison with control variate-based methods, such as SCAFFOLD or SCAFFLSA, under the Markovian setting?\n3. The theoretical results require careful tuning of parameters like step sizes $\\gamma$, $\\eta$, and momentum $\\beta$ based on unknown quantities. Is there an adaptive strategy or heuristic the authors can recommend for real-world deployment?\n4. All your evaluation metrics focus on gradient norm as the convergence criterion. Can you report test accuracy or loss (e.g., RMSE on PM2.5) to give a sense of practical performance?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper is well-organized, beginning with a strong motivation and providing precise mathematical modeling.\n- The paper presents a rigorous theoretical analysis of FL under Markovian data streams, an underexplored yet realistic setting.\n- It provides tight convergence bounds for Minibatch SGD, Local SGD, and Local SGD-M, under well-stated assumptions.\n- Detailed proofs and assumptions are provided in the appendix; results are reproducible with shared code and setup.\n- Empirical validation on real-world, temporally dependent data strongly supports the theoretical findings.\n\n## Weaknesses\n- While the theoretical results are strong, some assumptions (e.g., bounded Radon-Nikodym derivative, fixed spectral gap) may not be easily verifiable in practice.\n- The experimental section is somewhat limited, only one real dataset is used, and synthetic settings are only briefly mentioned.\n- The practical implications for deployment in real FL systems are not deeply explored. For example, how to estimate spectral gap or choose $K$ in practice is left unaddressed.", "was_revised": true, "final_justification": "4", "rebuttal": "We are happy that the Reviewer appreciated our solid theoretical results! We address the Reviewer's specific comments point-by-point below.\n\n### Weaknesses\n\n> While the theoretical results are strong, some assumptions (e.g., bounded Radon-Nikodym derivative, fixed spectral gap) may not be easily verifiable in practice.\n\n- We highlight that our assumptions on the underlying Markov chain are weaker than those often used in the literature of SGD, which allows for more general data streams' models. For example, we do not impose the condition of uniform ergodicity, and rather assume the existence of a pseudo spectral gap [41, Section 3.1]. The bounded Radon-Nikodym derivative is a classical assumption and has been used extensively in the literature on Markov chain Monte Carlo methods [17] (lines 177-178 in our paper). As even the standard assumptions (e.g., uniform ergodicity) are difficult to verify, we believe that moving to weaker assumptions  represents a step toward conditions that practitioners can realistically justify.\n\n> The practical implications for deployment in real FL systems are not deeply explored. For example, how to estimate spectral gap or choose $K$ in practice is left unaddressed.\n\n- In the case of finite state space Markov chain, the pseudo spectral gap and $C_{\\infty}$ can be computed by estimating the transition matrix and the stationary distribution. This can be done as in [47], by keeping track of the transition between different states.\n\n> The experimental section is somewhat limited, only one real dataset is used, and synthetic settings are only briefly mentioned.\n\n- We note that the main focus of our paper is on the theoretical guarantees of FL algorithms with Markovian Data. We believe that providing the first convergence results for these FL algorithms under Markovian data streams, showing that collaboration is still beneficial in this setting is a major contribution of our paper. Additional experiments with synthetic data are provided in Appendix B.7, where we also show the effect of mixing time on the convergence. These experiments also support our theoretical findings.\n\n### Questions\n\n> The paper evaluates performance on a single real-world dataset (air-quality time series). How generalizable are the findings across domains?\n\n- Our analysis focuses on problems that can be modelled by Markov chains. The choice of the air-quality dataset used in our experiments is motivated by the fact that many physical processes exhibit Markov structure. Our results are not restricted to this specific domain, but rather apply broadly to settings where data can be modeled as Markov chains—such as reinforcement learning, financial forecasting, and sensor networks (see lines 141-144 in our paper).\n\n> You suggest that momentum-based methods (SGD-M) mitigate heterogeneity without requiring control variates (e.g., SCAFFOLD). Could you provide direct empirical comparison with control variate-based methods, such as SCAFFOLD or SCAFFLSA, under the Markovian setting?\n\n> The theoretical results require careful tuning of parameters like step sizes $\\gamma$, $\\eta$, and momentum $\\beta$ based on unknown quantities. Is there an adaptive strategy or heuristic the authors can recommend for real-world deployment?\n\n> All your evaluation metrics focus on gradient norm as the convergence criterion. Can you report test accuracy or loss (e.g., RMSE on PM2.5) to give a sense of practical performance?\n\n- We carried out additional experiments for the air-quality time series dataset used in Section 5, we added a comparison to SCAFFOLD. To tune $\\gamma$, $\\eta$ and $\\beta$, we use grid search over a logarithmic grid from $0.1$ to $10^{-4}$ for the learning rates and from $0.1$ to $0.9$ for the momentum coefficient. We report the *RMSE on PM2.5* averaged over 5 runs, along with the 95% confidence interval at the $80$-th communication rounds in the table below:\n\n    | Algorithm     | $K=10$            | $K=50$            | $K=100$           |\n    | ------------- | ----------------- | ----------------- | ----------------- |\n    | Minibatch SGD | $0.3997 ± 0.0054$ | $0.3774 ± 0.0012$ | $0.3776 ± 0.0005$ |\n    | Local SGD     | $0.3880 ± 0.0088$ | $0.3786 ± 0.0004$ | $0.3776 ± 0.0001$ |\n    | SCAFFOLD      | $0.3879 ± 0.0088$ | $0.3788 ± 0.0004$ | $0.3778 ± 0.0001$ |\n    | Local SGD-M   | $0.3835 ± 0.0027$ | $0.3774 ± 0.0004$ | $0.3767 ± 0.0008$ | \n\n\n- We can observe that Local SGD-M consistently achieves the lowest RMSE, while SCAFFOLD behaves quite similarly to Local SGD. We argue that the benefit of SCAFFOLD is more clear in the partial participation setting. [9] also shows that incorporating momentum into SCAFFOLD under the partial client participation setting further improves the convergence. Extending our current analysis to evaluate the combined effect of momentum and control variates in the partial participation setting with Markovian data is a promising direction for future research.\n\n- In real world deployment, where grid search is impractical, another alternative is to use adaptive step-size method. In the centralized setting, it has been shown that AdaGrad step size can adapt to the unknown mixing time of the underlying Markov chain [13]. We believe that exploring similar adaptive learning rate strategies in the federated setting is a valuable direction for future work.\n\n#### References\n\n[41] Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. 2018\n\n[17] Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding’s Inequality for General Markov Chains and Its Applications to Statistical Learning. JMLR 22, 2021.\n\n[47] Angelo Rodio, Francescomaria Faticanti, Othmane Marfoq, Giovanni Neglia, Emilio Leonardi. Federated learning under heterogeneous and correlated client availability. IEEE INFOCOM 2023.\n\n[9] Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. ICLR 2024"}, {"review_id": "UrXeqgqSx8", "reviewer": "Reviewer_CkzJ", "summary": "The work provides methods for federated learning in the setting where clients hold a sliding window of K most-recent samples that evolve as a time-homogeneous Markov chain converging to a stationary distribution.", "questions": "1.) Would it be preferred to have a small $\\theta$ and $\\delta$, in the context of the  bounded gradient dissimilarity (BGD) assumption? If so, how would you ensure that in your work?\n\n2.) How would extending to mini-batch updates (multiple correlated samples) change the convergence results?\n\n3.) What is local local SGD on line 212 and how is it different from local SGD? Is local local SGD a typo or refers to Local SGD with Momentum?\n\n4.) What is the difference in the setup in proposition C.10 Vs. the equation between line 740 and 741 that give mixing time results?", "limitations": "These have been described in great detail.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThe convergence bounds provided are sharp. The method has a good communication efficiency.\nThe problem is well motivated as such temporal streams of data are quite common in the federated setting. \n\nIt provides some mixing-time results to understand the convergence to a statioary target distribution. \n\nMain weakness:\n1.) In order to guarantee convergence, they suggest that many local steps are needed. Can you share some more info about this?", "was_revised": true, "final_justification": "The authors have done a thorough job and clarified all the main concerns. Based on that and rest of the discussions, I uphold my score at 5.", "rebuttal": "We really appreciate the Reviewer's positive comments about our paper! We address the Reviewer's concerns below.\n\n### Main weaknesses\n\n> In order to guarantee convergence, they suggest that many local steps are needed. Can you share some more info about this?\n\n- It is true that in order to guarantee convergence, there is a constraint on the number of local steps. The reason for this is that the term $\\frac{C_{\\infty}\\sigma^2}{\\nu_{ps}MK}$ in our bounds corresponds to the bias of the gradient estimates and cannot be controlled by the step size. A similar issue is already present even for centralized Markov SGD, where the bias is often controlled by increasing the batch size (see, e.g [3]). Other works [12, 15], also in the centralized setting, instead require a large number of iterations to control the Markovian bias—an approach that would translate to higher communication cost in federated learning. In contrast, our analysis is more aligned with the core aim of FL---trading extra local computation for fewer communication rounds.\n\n### Questions\n\n> Would it be preferred to have a small $\\theta$ and $\\delta$, in the context of the bounded gradient dissimilarity (BGD) assumption? If so, how would you ensure that in your work?\n\n- Ideally, in the homogeneous setting (all clients learning task are the same), $\\theta = 0$ and $\\delta = 1$ would minimize the heterogeneity term for local SGD in Theorem 4.7. On the other hand, the heterogeneity parameters $\\theta$ and $\\delta$ are determined by the gradient functions $\\nabla F_m, m \\in [M]$, which depends on the data distribution $\\pi_m$ and the local objective $f_m$. As a consequence, $\\theta$ and $\\delta$ can only be changed by modifying the data distribution or the learning task. For example local data distributions may be made closer if clients are allowed to share at least a part of their dataset, something that is not usually envisaged in federated learning, but it is an option in the so-called fog learning (e.g. [Hosseinalipour et al. 2020])\n\n> How would extending to mini-batch updates (multiple correlated samples) change the convergence results?\n    \n- Thank you for your great question! Indeed our analysis can be generalized to consider minibatch updates. Precisely, the number of samples utilized per communication round appears in the term $E_t [ || g_t - \\nabla F(w_t) ||2 ]$, where $E_t$ is the expectation conditioned on information available up to time $t$ and $g_t = \\frac{1}{MK}\\sum_{m,k} \\nabla f_m(w_t^{(m,k)};x_t^{(m,k)})$. As a consequence, if mini-batch updates are utilized with the same number of samples $K$ utilized per communication round, then the variance term $\\frac{C_{\\infty}\\sigma^2}{\\nu_{ps}MK}$ will not change. However, in local SGD, if fewer local steps are taken, this can reduce the impact of heterogeneity (corresponding to the last term in Theorem 4.7). In the extreme case where only one local step is used (with a mini-batch of $K$ samples), this corresponds to mini-batch SGD, for which the convergence bound is given in Theorem 4.5. In the revised version of our paper, we will add discussions about this extension.\n\n> What is local local SGD on line 212 and how is it different from local SGD? Is local local SGD a typo or refers to Local SGD with Momentum?\n\n- Many thanks for your careful reading. The “local local SGD” reference was a typo and will be replaced with local SGD with Momentum in a revised version.\n\n> What is the difference in the setup in proposition C.10 Vs. the equation between line 740 and 741 that give mixing time results?\n\n- Proposition C.10 provides a general characterization of the mixing time of the system Markov chain in terms of the mixing times of the individual mixing times of the client chains. In the case the system Markov chain is also uniformly ergodic (as discussed in Appendix B.5), then the pseudo spectral gap $\\nu_{ps}$ of the system Markov chain can be bounded in terms of its mixing time (see lines 733-734). The result of Proposition C.10 can then be applied (see lines 735-736), which leads to the equation you indicate between lines 740 and 741.\n\n\n#### References\n\n[3] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Neurips 2023.\n\n[12] Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, and Justin Romberg. Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness. arXiv:2003.10973.\n\n[15] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. ICML 2023.\n\n[Hosseinalipour et al. 2020] S. Hosseinalipour, C. G. Brinton, V. Aggarwal, H. Dai and M. Chiang, From Federated to Fog Learning: Distributed Machine Learning over Heterogeneous Wireless Networks, IEEE Communications Magazine 2020."}, {"review_id": "IpOGERmswM", "reviewer": "Reviewer_T7vf", "summary": "This paper addresses the challenges of Federated Learning (FL) in the context of streaming, non-i.i.d. data, specifically focusing on Markovian data streams, which frequently arise in real-world applications such as health and environmental monitoring. Unlike standard FL setups where clients train on static datasets, the authors consider data generated by time-homogeneous Markov processes, which introduces temporal dependencies and non-stationarity. The authors conduct a rigorous theoretical analysis of three FL algorithms in this setting: (i) Minibatch SGD; (ii) Local SGD, and (iii) Local SGD with Momentum (Local SGD-M). In addition to the theoretical contributions, the paper includes experiments on a regression task using a real-world dataset to illustrate the behavior of the algorithms under Markovian sampling.", "questions": "1) Can you clarify why the variance term in your convergence bounds is not controlled by the step-size, unlike in [1]? Can you either refine the analysis or show empirically that this term does not vanish with a smaller step-size?\n\n2) Would it be possible to rerun or supplement the experiments with step-size schedules that follow the theoretical scaling with respect to $K$ or a grid search?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1) The paper tackles a realistic and underexplored setting in FL by modeling client data streams as non-stationary Markov processes, a framework that reflects the dynamics of many physical and biological systems.\n\n2) The theoretical analysis is rigorous and well-written, and characterizes the convergence behavior of Minibatch SGD and Local SGD under Markovian sampling. In particular, the results confirm that linear speedup (i.e., sample complexity scaling with $1/M$) is achievable under standard smoothness and bounded heterogeneity assumptions.\n\n3) An important contribution is the analysis of Local SGD with Momentum, which is shown to mitigate client drift due to data heterogeneity under Markovian streaming, achieving convergence guarantees without the need for gradient dissimilarity assumptions.\n\n**Weaknesses**\n\n1) *Main concern* : The variance term in the convergence bounds is independent of the step-size, which seems suboptimal. Intuitively, one would expect the variance term to decay as the step size decreases since smaller steps imply smaller parameter movement from initialization. This contradicts both empirical intuition and existing results in the literature (e.g., [1]), where the variance is weighted by the step-size. The authors should either provide theoretical justification for why such an \"incompressible\" variance term appears, or offer empirical evidence of its presence and persistence across different step-size regimes.\n\n2) In Section 4.3 (\"Impact of Markovian Data\"), the paper references [2] and asserts that the bias term in Theorem 2 of [2] is persistent and uncontrollable even with increased local computation. However, the bias in [2] originates from client heterogeneity, not from Markovian sampling. This remark is misleading and should be relocated to the section discussing heterogeneity.\n\n3)  In the experimental section, the choice of hyperparameters lacks consistency with the theoretical findings. For example, the theory suggests that the step size should scale as $\\mathcal{O}(K)$, yet the experiments use a fixed step size across different values of $K$. This makes it difficult to isolate whether stagnation in performance is due to the variance term, the heterogeneity term, or simply hyperparameter mismatch. I strongly suggest including either experiments where step-size is scaled according to theory, or to select the hyperparameters according to a grid search, to better support the empirical conclusions drawn in the paper.\n\n[1] Zhu,F. ,Mitra,A., and Heath, R.W. (2025) . Achieving tighter finite-time rates for heterogeneous federated stochastic approximation under markovian sampling.\n\n[2] Han Wang, Aritra Mitra, Hamed Hassani, George J. Pappas, and James Anderson. Federated TD learning with linear function approximation under environmental heterogeneity. Transactions on Machine Learning Research, 2024", "was_revised": true, "final_justification": "The authors have adequately addressed my concerns, especially regarding the non-compressible 'variance' term. Their response clarified the key points I raised, and I find the rebuttal satisfactory. I am therefore increasing my score.", "rebuttal": "We are happy that the Reviewer appreciates the contribution of our work! We address the Reviewer's comments below.\n\n> Main concern: The variance term in the convergence bounds is independent of the step-size, which seems suboptimal...\n\n> Can you clarify why the variance term in your convergence bounds is not controlled by the step-size, unlike in [1]? Can you either refine the analysis or show empirically that this term does not vanish with a smaller step-size?\n\n- The main concern of the reviewer is the presence of a variance term (dependent on the variance of the gradient estimator) in Theorems 4.5,4.7,4.9, which is not scaled by the step size. We first highlight that our results apply for non-convex objectives with Markovian sampling in the federated setting, while existing results motivated by reinforcement learning (e.g., TD learning) with linear function approximation are in the (strongly) convex setting (see lines 40-42), **including [Zhu,F. ,Mitra,A., and Heath, R.W. (2025)] pointed by the reviewer**. We were not aware of this work which appeared online one month before NeurIPS and we thank the reviewer for pointing it out. In the revised version of the paper we will also include this reference.\n- We first give a theoretical justification that clarifies why adjusting the step size alone offers limited leverage for controlling the variance term. By a standard decomposition from the $L$-smoothness condition:\n$$\nE_t [ F(w_{t+1}) ] \\leq F(w_t) - \\gamma/2 (1-2\\gamma L) || \\nabla F(w_t) ||^2 + \\gamma/2 || E_t [g_t] - \\nabla F(w_t) ||^2 +\\gamma^2 L E_t [ || g_t - \\nabla F(w_t) ||^2 ]\n$$\nwhere $b_t = || E_t [g_t] - \\nabla F(w_t) ||^2$ and $v_t = E_t [ || g_t - \\nabla F(w_t) ||^2$ denotes the bias and the variance of the gradient estimate, and $\\mathbb{E}_t$ denotes the expectation conditioned on the history up to time t.  Observe that the bias is scaled by the step size $\\gamma$. Since the term $||\\nabla F(w_t) ||^2$ is also scaled by $\\gamma$, the bias cannot be directly controlled by the choice of step size without sacrificing the reduction of the objective. Note that by Jensen's inequality, $b_t \\leq v_t$, hence the bias also contributes to the \"variance\" term arising in our main results. This lead to a non-vanishing \"variance\" term in our results as the step size decreases.\n\n- For smooth non-convex objectives, we are aware of only three papers [3,13,15] that have a variance term vanishing as the number of iterations diverges. Note that the three papers consider centralized or token-passing settings as opposed to the federated setting in our paper. These papers make the variance term vanish by introducing auxiliary parameters that can be tuned to scale the bias with the step size or with $1/\\sqrt{T}$. This is achieved:\n    - in [15] by decomposing the bias into other terms that contain delayed gradients, and scaling such delay as $1/\\sqrt{T}$. This technique requires a constraint on the minimum number of iterations $T$ (analogous to communication rounds $T$).\n    - in [3,13] by using a minibatch gradient estimate at each iteration (instead of using just one sample). The minibatch size utilized is then chosen to be scaled inversely with the step size [13], or with $\\sqrt{T}$ [3].\n    \n- We highlight that the sample complexities obtained in our paper is at the order of $1/(M \\epsilon^4)$, which is the same as those achieved in [3, 13, 15] and scale inversely with the number of clients $M$. However, our assumptions on the underlying Markov processes are weaker (see Section 3.2 in our paper). \n- In our paper, we considered $K$ as independent of both the step size and the number of rounds $T$, because we think that in real deployments the value of $K$ is dictated by the data-arrival rate and client's buffer capacity. Nonetheless, following the approach of [3, 13], $K$ grow with $T$ or inversely with the step size, which would indeed drive the variance term to zero as $T \\rightarrow \\infty$. Note, however, that this would not lead to any improvement in sample complexity.\n\n> In Section 4.3 (\"Impact of Markovian Data\"), the paper references [2] and asserts that the bias term in Theorem 2 of [2] is persistent and uncontrollable even with increased local computation...\n\n- We thank the Reviewer for their comment and after re-reading [2], we agree that this reference would be better suited in the section discussing heterogeneity. In the revised version of the paper, we will make this modification.\n\n> In the experimental section, the choice of hyperparameters lacks consistency with the theoretical findings...\n\n> Would it be possible to rerun or supplement the experiments with step-size schedules that follow the theoretical scaling with respect to $K$ or a grid search?\n\n- As suggested, we have performed additional experiments to investigate the scaling of the step size. As the reviewer notes, for Local SGD, the choice of the local step size can impact performance. For moderate values of the initial suboptimality gap and heterogeneity:\n    - If $K$ is large, then the bound is dominated by the heterogeneity term.\n    - If $K$ is small, then the bound is dominated by the variance term.\n- To empirically validate this, we modified the setup in Section 5 to scale the local learning rate as $\\eta = b / K$, with two base values: $b=0.1$ and $b=0.01$. This replaces the fixed learning rate $\\eta = 0.01$ used in the original experiments. We report below the mean gradient norm after 80 communication rounds, along with the 95% confidence interval over 5 random seeds:\n\n    | $\\eta$   | $K=10$              | $K=50$              | $K=100$             | \n    | -------- | ------------------- | ------------------- | ------------------- |\n    | $0.1/K$  | $0.00506 ± 0.00076$ | $0.00307 ± 0.00041$ | $0.00233 ± 0.00030$ |\n    | $0.01/K$ | $0.01248 ± 0.00279$ | $0.00921 ± 0.00210$ | $0.01190 ± 0.00245$ |\n\n- We report here the bound for Local SGD from Theorem 4.7:\n$$\n\\frac{1}{T} \\sum_{t=0}^{T-1} E [ || \\nabla F(w_t) ||^2 ] \\leq \\mathcal{O} \\left( \\frac{\\Delta_0}{\\eta K T} + \\frac{C_{\\infty} \\sigma^2}{\\nu_{ps}MK} + \\frac{L K \\eta (\\theta^2+\\sigma^2)}{\\delta^2}  \\right)\n$$\n- Choosing the step size as $\\eta \\propto 1/K$ leaves the first and third error terms unchanged with  $K$, while the second term decays with increasing $K$. Hence, when this second term dominates for small $K$, the gradient norm $||\\nabla F(w)||^2$ should decrease before flattening out at a positive plateau. The patterns shown in each row align with this qualitative prediction.\n    \n- The comparison of the two rows support the fact that the variance term cannot be controlled by the step size. Indeed, for a fixed $K$, reducing the step size by a factor of $10$ does not improve the performance. On the contrary, the gradient norm appears to increase for smaller $\\eta$. This can be explained by the first term in the bound, associated with the suboptimality gap, which scales inversely with the step size.\n\n#### References:\n\n[3] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Neurips 2023.\n    \n[13] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimization with Markovian data. ICML 2022.\n    \n[15] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. ICML 2023.\n\n[Zhu,F. ,Mitra,A., and Heath, R.W. (2025)] Zhu,F. ,Mitra,A., and Heath, R.W. (2025) . Achieving tighter finite-time rates for heterogeneous federated stochastic approximation under markovian sampling."}, {"review_id": "FqzAleeB5U", "reviewer": "Reviewer_hK1v", "summary": "1. This paper establishes the upper bounds (of convergence rates) for Minibatch SGD and Local SGD (FL) on Markovian data.\n2. This paper establishes the upper bounds of the momentum-based variants of Local SGD.", "questions": "**Questions**:\n\nI am not familiar with Markov chain. So my questions are focused on the part related to Markov chain.\n\n1. Section 4.1, Assumptions, Lines 214--215: What does $\\tau$ mean?\n\n2. Proof of Lemma B.1, Lines 581--582. What does $x_{t-1}^{K-1} = x$ mean? Can you elaborate on the change of measures?\n\n3. Proof of Lemma B.1, Line 582. What does $|| \\cdot ||_{\\pi, \\infty}$ mean? Can you elaborate on how to use Holder's inequality? You can write the form of Holder's inequality used here and specify how to use it.\n\n4. Proof of Theorem B.3, Line 607. Can you elaborate on this equality?\n\n5. Proof of Lemma B.5, Line 626, the first inequality. Is it possible to do as follows?\n   \n    $$\n   \\begin{align*}\n   \\xi_t &= \\frac{1}{MK} \\sum_{m,k} \\eta^2  E_t \\\\| \\sum_{j=0}^{k-1}\\nabla f_m(w_t^{(m,j)};x_t^{(m,j)}) \\\\|^2 \\\\\\\\\n   &\\leq \\frac{1}{MK} \\sum_{m,k} \\eta^2  \\left( E_t \\\\| \\sum_{j=0}^{k-1}\\nabla f_m(w_t^{(m,j)};x_t^{(m,j)}) - \\sum_{j=0}^{k-1}\\nabla f_m(w_t;x_t^{(m,j)}) \\\\|^2 + E_t \\\\| \\sum_{j=0}^{k-1}\\nabla f_m(w_t;x_t^{(m,j)})- \\sum_{j=0}^{k-1}\\nabla F_m(w_t) \\\\|^2 + E_t \\\\|  \\sum_{j=0}^{k-1}\\nabla F_m(w_t) \\\\|^2 \\right)\n   \\end{align*}\n   $$\n\n   The above inequality has three terms. Can the second term be bounded by [41, Theorem 3.7] (as done in Lemma B.1)? If so, does this cause a different bound for $\\xi_t$? Does this cause different convergence rates for FL?\n\n**Suggestions**:\n\n1. Could you add the comparisons of upper bounds with Minibatch SGD and Local SGD with IID data for both without momentum and with momentum settings in a more straightforward way? One simple way is collect them in one table and highlight the main difference in different colors, just like the tables in [+6,+7]. This can help the readers see their differences more clearly.\n\n   [+6] Minibatch vs Local SGD for Heterogeneous Distributed Learning, NeurIPS, 2020.\n\n   [+7] Momentum Benefits Non-Iid Federated Learning Simply and Provably, ICLR, 2024.\n\n2. Could you add the comparisons with SGD on Markovian data in a more straightforward way? One simple way is collect them in one table and highlight the main difference in different colors, just like the tables in [+6,+7].\n\n3. Is it possible to remove the \"streaming\" in the title. Compared to the existing works focusing on FL with IID data [+5], this work study FL with Markovian data. Nevertheless, this work still considers the typical stochastic optimization, instead of online stochastic optimization. Thus, in my opinion, \"streaming\" may be unnecessary, and may misguide the readers into the works of online federated learning [+8,+9], which also claimed to address the problem of streaming data.\n\n   I know that this may cause some revisions of the introduction. I think that [+10] (see their introduction) will be helpful.\n\n   [+8] Asynchronous Online Federated Learning for Edge Devices with Non-IID Data, BigData, 2020.\n\n   [+9] Online Federated Learning, CDC, 2021.\n\n   [+10] On the Decentralized Stochastic Gradient Descent With Markov Chain Sampling, IEEE Transactions on Signal Processing, 2023.\n\n**Scores**:\n\nIf character count is limited, please focus on Weaknesses.\n\n1. I will raise my score to 4, as long as Weaknesses 1 and 2 are well explained. However, I cannot guarantee a higher score for now, as I am not an expert in Markov chains.\n2. I have checked the proofs of Theorems 4.5--4.8 (without momentum) and have the questions above. Explaining them clearly will make this work more convincing and accessible.\n3. The suggestions are not enforced. Nevertheless, I hope that the authors can consider them.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1. The upper bounds of FL on Markovian data are novel (to the best of my knowledge) in the FL literature.\n2. The momentum-based variants are also new for FL on Markovian data.\n3. The amount of work in this paper is sufficient.\n4. The paper is well-organized and well-written.\n\n**Weaknesses**:\n\n1. My **main concern** is that there exists one non-vanishing term (as $T$ approaches infinity) in the upper bounds (e.g., Theorems 4.5 and 4.7). This is quite different from the classical results of Markov chain SGD [+1,+2,+3,+4] and FL [+5], whose upper bounds approach zero as $T$ approaches infinity if an appropriate step size is chosen.\n\n   [+1] Finite-Time Analysis of Markov Gradient Descent, TAC, 2022.\n\n   [+2] Adapting to Mixing Time in Stochastic Optimization with Markovian Data, ICML, 2022.\n\n   [+3] Stochastic Gradient Descent under Markovian Sampling Schemes, ICML, 2023.\n\n   [+4] First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities, NeurIPS, 2023.\n\n   [+5] Tighter Theory for Local SGD on Identical and Heterogeneous Data, AISTATS, 2020.\n\n2. Could you discuss the different measures used for Makrov chain in this paper and previous works? After checking some works of Markov chain SGD, I note that the mixing time is common (e.g., [+3]). So could you elaborate on why we use $C_{\\infty}$ and $\\nu_{ps}$, rather than the mixing time (or other measures). I am curious about this.", "was_revised": true, "final_justification": "This paper establish the convergence guarantees of FedAvg (w/ or w/o momentum) on Markovian data.\n\nThe concern in my initial review is the non-vanishing term of the bounds (it is essentially the same concern of Reviewer T7vf). The responses of the authors seem reasonable for me, and they are also acknowledged by Reviewer T7vf.\n\nConsidering that I am not an expert of Markovian SGD, it is hard for me to verify their responses in detail, I decide to increase my rating to 4, and decrease my confidence to 3.   \n\nLastly, I hope the authors will revise this paper as promised.", "rebuttal": "We sincerely thank the Reviewer for their detailed and thoughtful feedback. We are pleased to see that the Reviewer values our contribution. Below, we address each of the Reviewer’s comments in turn.\n\n### Main weaknesses\n    \n> My main concern is that there exists one non-vanishing term (as $T$ approaches infinity) in the upper bounds (e.g., Theorems 4.5 and 4.7)...\n    \n- We highlight that the non-vanishing term in Theorems 4.5, 4.7, 4.9 is scaled by $1/K$, where $K$ is the batch size (or the number of local steps in local SGD). As a consequence, $K$ can be chosen to be a function of $T$ such that the term vanishes. For example, choosing $K = T$ in Theorem 4.5 for Minibatch SGD or $K = \\sqrt{T}$ and $\\eta = 1/T$ in Theorem 4.7 for Local SGD, all terms in the bounds converge to zero as $T \\rightarrow \\infty$. For example, with minibatch SGD we have the following modification of Theorem 4.5.\n\n- *Theorem: Suppose the conditions of Theorem 4.5 hold, and $K = T$. Then,*\n$$\n\\frac{1}{T} \\sum_{t=0}^{T-1} E [ || \\nabla F(w_t) ||^2 ] \\leq \\mathcal{O} \\left(\\frac{\\Delta_0}{\\gamma T} + \\frac{C_{\\infty}\\sigma^2}{\\nu_{ps}MT} \\right).\n$$\n    \n- Note that letting $K$ scale with $T$ does not lead to any improvement in the sample complexity over our corollaries 4.6,4.8,4.10. Hence, we presented our results with $K$ independent of $T$ as, in practice, $K$ may be determined by the arrival rate of the data samples and the buffer size of each client.\n    \n- We highlight that scaling the number of samples utilized in each iteration is also the method of [3,13] (for the centralized Markov SGD) to ensure that all terms vanish as the number of iterations diverges.\n\n- There is a theoretical justification for why the variance term in our bounds cannot be directly controlled by the step size. By a standard decomposition from the $L$-smoothness condition:\n$$\nE_t [ F(w_{t+1}) ] \\leq F(w_t) - \\gamma/2 (1-2\\gamma L) || \\nabla F(w_t) ||^2 + \\gamma/2 || E_t [g_t] - \\nabla F(w_t) ||^2 +\\gamma^2 L E_t [ || g_t - \\nabla F(w_t) ||^2 ]\n$$\nwhere $b_t = || E_t [g_t] - \\nabla F(w_t) ||^2$ and $v_t = E_t [ || g_t - \\nabla F(w_t) ||^2$ denotes the bias and the variance of the gradient estimate, and $\\mathbb{E}_t$ denotes the expectation conditioned on the history up to time t. This bias arises from the Markovian structure of the data, and does not appear in the i.i.d. setting. Observe that the bias is scaled by the step size $\\gamma$. Since the term $||\\nabla F(w_t) ||^2$ is also scaled by $\\gamma$, the bias cannot be directly controlled by the choice of step size. By Jensen's inequality, we have $b_t \\leq v_t$, hence the bias also contributes to the \"variance\" term arising in our main results. This leads to a non-vanishing \"variance\" term in our results as the step size decreases.\n    \n- We now give additional details of the techniques used in [3, 12, 13, 15] to control this bias, and obtain a vanishing variance term. In short, they introduce other hyper-parameters that can be tuned to make the bias vanish, instead of tuning directly the step size.\n    - [12, 15] decompose the bias term into other terms containing delayed gradient. This delay is later chosen to be scaled with $1/\\sqrt{T}$. This technique requires a constraint on the minimum number of iterations (analogous to communication rounds $T$) at the order of $\\tilde{\\mathcal{O}} (\\tau_{\\mathrm{mix}})$. As revealed in [Table 1, 3], [12] also contains hidden factors that can be exponential in $\\tau_{\\mathrm{mix}}$. The bound for non-convex function in [12] (Theorem 3 in the arxiv version) also requires a projection onto the unknown set that contains all the optima.\n    - [3, 13], as discussed above, use minibatch gradient estimates. Precisely, at each iteration, a random batch size is drawn from a truncated geometric distribution. Hence, a new hyper-parameter is introduced which is the truncation threshold $m$. [3, 12] shows that $b_t$ scales inversely with $m$, which is then chosen to be scaled with $1/\\sqrt{T}$.\n    \n- We highlight that the sample complexities obtained in our paper are of the order of $1/(M\\epsilon^4)$, which is the same as those achieved in [3, 12, 13, 15] scaled inversely with the number of clients $M$. However, our assumptions on the underlying Markov processes are weaker (see Section 3.2 in our paper). As not every convergence result in [3, 12, 13, 15] are stated as sample complexity, we refer to [Table 1, 3] for a detailed comparison in term of sample complexity.\n\n> Could you discuss the different measures used for Makrov chain in this paper and previous works?...\n    \n- The use of $C_{\\infty}$ and $\\nu_{ps}$ comes from the fact that we do not impose uniform ergodicity assumption on the underlying Markov chains as in [3, 12, 15]. This suggests that our results can be applied to a broader class of Markov chains. [13] does not require uniform ergodicity, but their bounds rely strongly on the bounded gradient norm assumption. \n    \n- More precisely, the pseudo spectral gap $\\nu_{ps}$ arising in our bounds is due to a variance bound for Markov chains [Theorem 3.7, 41], which applies for very general Markov chains (non-reversible and non-uniformly ergodic). However, this variance bound only holds for stationary chains (chains start from the stationary distribution). The term $C_{\\infty}$ appears in a change of measure to account for this non-stationarity. \n    \n- In contrast, [3] relies on uniform ergodicity to deal with non-stationarity, but this can yield a dependence on the square of the mixing time [Section B.1, 3], and applying blindly their technique in the FL setting does not show the linear speedup. Recent works on FL with Markovian data [35] with linear speedup only consider stationary and uniformly ergodic Markov processes. \n    \n- We provide a characterization of $C_{\\infty}$ and $\\nu_{ps}$ under more restricted settings in Appendix B.6 of our paper, showing that we can recover the dependence on the mixing time as in [3, 12, 13, 15].\n    \n### Questions\n\n> Section 4.1, Assumptions, Lines 214--215: What does $\\tau$ mean?\n    \n- This is a typo. The problem classes defined at the end of Section 4.1 only depend on $C_{\\infty}$ and $\\nu_{ps}$. We will fix this in the revised version of the paper.\n    \n> Proof of Lemma B.1, Lines 581-582...\n    \n- Here $x_{t-1}^{K-1}$ denotes all the Markov samples used by the clients in the last local step of round $t-1$. In the proof of Lemma B.1, we first need to take the conditional expectation with respect to the history up to round $t$, so that the randomness now depends only on the Markov samples arriving in round $t$. Due to the memoryless property of Markov chain [37, Proposition 3.4.3], conditioning on the past is equivalent to conditioning only on the most recent sample. We write $x_{t-1}^{K-1}=x$ to highlight that we are conditioning on $x_{t-1}^{K-1}$. Denote by $q$ the probability measure $P ( {x_{t-1}^{K-1}}=x, .)$. The conditional expectation $E_t[.]$ is equivalent to $E_q[.]$. The Markov samples used in round $t$, conditioned on $x_{t-1}^{K-1}$, is a Markov chain with starting distribution $q$. The change of measure comes in to make this Markov chain stationary (i.e. start from the stationary measure $\\pi$), so that [Theorem 3.7, 41] can be applied.\n\n> Proof of Lemma B.1, Line 582...\n    \n- $\\left\\lVert \\cdot \\right\\rVert_{\\pi, \\infty}$ denotes the norm in the $L^{\\infty} (X, \\pi)$ space of measurable function $f: X \\rightarrow \\mathbb{R}$. More precisely,\n$$\n\\left\\lVert f \\right\\rVert_{\\pi, \\infty} = \\inf \\left\\\\{ C \\geq 0, | f(x) | \\leq C~ \\text{for}~ \\pi \\text{-almost everywhere}~ x \\right\\\\}    \n$$\n\n- This is an equivalent way to write the essential supremum in Assumption 3.2 of our paper. We write this way to make it clearer that we use Holder's inequality in this step. The exact form of Holder's inequality used here is:\n$$\n\\mathbb{E} [|XY|] \\leq \\mathbb{E} [|X|^p] ^ {1/p} \\mathbb{E} [|Y|^q]^{1/q}, \n$$\nfor two random variables $X, Y$, and $1/q+1/p=1$. We then apply this inequality with $p=\\infty, q=1$, $X$ is the Radon-Nikodym derivative, and $Y$ is the term with the square Euclidean norm.\n    \n> Proof of Theorem B.3...\n\n- This equality follows from the fact that $\\hat{w_T}$ is sampled uniformly at random from the iterates $w_0, \\dots, w_{T-1}$, independently from the randomness during training.\n    \n> Proof of Lemma B.5...\n\n- Thank you for your suggestion. Indeed, what you suggest is totally possible, but doing this will make the term $1/\\nu_{ps}$ appear in the drift bound, and later on, appear in the communication complexity. We note that $1/\\nu_{ps}$ can be upper-bounded by the mixing time. Thus, this technique will result in a worse communication complexity than the one achieved in Theorem 4.7 of our paper.\n\n### Suggestion\n\n- We greatly appreciate the Reviewer’s thoughtful suggestions and will incorporate all of them into the revised version of our paper.\n    \n#### References\n[3] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. Neurips 2023.\n\n[12] Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, and Justin Romberg. Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness. arXiv:2003.10973.\n\n[13] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimization with Markovian data. ICML 2022.\n\n[15] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. ICML 2023.\n\n[35] Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, Reda ALAMI, Alexey Naumov, and Eric Moulines. SCAFFLSA: Taming heterogeneity in federated linear stochastic approximation and TD learning. Neurips 2024.\n\n[37] Meyn S, Tweedie RL, Glynn PW. Markov Chains and Stochastic Stability. 2nd ed. Cambridge University Press; 2009."}]

Author rebuttal:

Meta-review: This paper investigates federated learning (FL) with Markov data streams. In particular, minibatch SGD, local SGD, and local SGD with momentum on Markovian data are considered. The main strength lies in its rigorous theoretical contributions and clear exposition. The main weakness about the non-vanishing variance term and the lack of experiment were fully addressed in the rebuttal. Therefore, I recommend acceptance.
Decision: Accept (poster)