Resilient Two-Time-Scale Local Stochastic Gradient Descent for Byzantine Federated Learning
Amit Dutta Thinh T. Doan





Resilient Two-Time-Scale Local Stochastic Gradient Descent for Byzantine Federated Learning
    Amit Dutta and Thinh T. DoanAmit Dutta is with the Electrical and Computer Engineering Department at Virgnia Tech, email: amitdutta@vt.edu. Thinh T. Doan is with the Aerospace Engineering and Engineering Mechanics Department at University of Texas, Austin, email: thinhdoan@utexas.edu. This work was partially supported by NSF-CAREER Grant No. 2339509 and AFOSR YIP Grant No. 420525

    September 9, 2024
===================================================================================================================================================================================================================================================================================================================================================================================================





§ ABSTRACT 

We study local stochastic gradient descent methods for solving federated optimization over a network of agents communicating indirectly through a centralized coordinator. We are interested in the Byzantine setting where there is a subset of f malicious agents that could observe the entire network and send arbitrary values to the coordinator to disrupt the performance of other non-faulty agents. The objective of the non-faulty agents is to collaboratively compute the optimizer of their respective local functions under the presence of Byzantine agents. In this setting, prior works show that the local stochastic gradient descent method can only return an approximate of the desired solutions due to the impacts of Byzantine agents. Whether this method can find an exact solution remains an open question. In this paper, we will address this open question by proposing a new variant of the local stochastic gradient descent method. Under similar conditions that are considered in the existing works, we will show that the proposed method converges exactly to the desired solutions. We will provide theoretical results to characterize the convergence properties of our method, in particular, the proposed method convergences at an optimal rate 𝒪(1/k) in both strongly convex and non-convex settings, where k is the number of iterations. Finally, we will present a number of simulations to illustrate our theoretical results. 






Federated optimization, Byzantine fault-tolerance, two-time-scale methods.





§ INTRODUCTION

We consider a distributed optimization framework where there are N agents communicating with a single coordinator. This framework is also popularly known as federated optimization <cit.>. Associated with each agent i is a function q^i:ℝ^d→ℝ. The goal of the agents is to find a point x^⋆ that optimizes their aggregate local functions. 





Besides traditional machine learning applications<cit.>, federated optimization now also finds application in networked systems e.g., internet of vehicles <cit.>, industrial control systems <cit.>, and wireless <cit.>.

One of the key advantages of the federated optimization framework is its ability to implement optimization algorithm updates locally at the agents without necessitating the transmission of raw data to a centralized coordinator.

This localized data processing not only reduces the communication overhead between agents and the central server but also introduces an element of privacy preservation.


One of the main challenges in federated learning is the vulnerability of the system to malicious attacks where some agents in the network may fail or whose updates can be manipulated by an external entity. Such malicious agents will have detrimental impacts to the performance of other agents, and if not addressed, it can lead to catastrophic failures of entire network. For example, malicious attacks have been identified as the most critical problem in wireless spectrum sensing <cit.>.    

In this paper, we are interested in studying the so-called distributed local stochastic gradient descent (SGD) for solving federated optimization. Our focus is to characterize the performance of this method when there are a (small) number of Byzantine malicious agents in the network . In this setting,  Byzantine agents can observe the entire network and send any information to the centralized coordinator to corrupt the output of local SGD. Due to the impact of Byzantine agents, our goal now is to solve the optimization problem that only involves the honest agents. In particular, we consider the setting where there are up to f faulty Byzantine agents with unknown identities. We then seek to solve an exact fault-tolerance problem defined as follows.

Exact fault-tolerance problem: 
Let ℋ be the set of honest agents with |ℋ| ≥ N-f, then an algorithm is said to have exact fault-tolerance if it allows all the non-faulty agents to compute

    x_ℋ^⋆∈min_x∈ℝ^d∑_i ∈ℋq^i(x).

Note that if the number of Byzantine agent is large, i.e., f> ℋ, it is impossible to solve problem (<ref>). We, therefore, consider the following 2f-redundancy condition, which is necessary and sufficient for solving problem (<ref>) exactly <cit.>. 

The set ℋ, with |ℋ| ≥ N-f, is said to have 2f-redundancy if for any subset 𝒮⊂ℋ with |𝒮| ≥ N -2f

    min_x∈ℝ^d∑_i ∈𝒮q^i(x) = min_x∈ℝ^d∑_i ∈ℋq^i(x).



We note that the 2f-redundancy condition arises naturally in many problems, including hypothesis testing <cit.>, and distributed learning <cit.>. For example, in distributed learning this condition is satisfied when all agents have identical objective functions, the so-called homogeneous setting. 




In this paper, we will investigate the convergence of local SGD in solving problem (<ref>) under this 2f-redundancy condition. In <cit.>, the authors show that the local deterministic gradient descent can find x_ℋ^⋆ when using a comparative elimination (CE) filter in its update to address the impacts of Byzantine agents. However, their approach cannot be extended to the case of local SGD, i.e., each agent only has access to stochastic samples of ∇ q^i(·). In this stochastic setting, the work in <cit.> can only return a point within a ball around x_ℋ^⋆ whose the size depends on the ratio f/ℋ. The level idea behind this issue is that the CE filter cannot simultaneously address the impacts of Byzantine agents and local stochastic errors due to gradient sampling. Our focus is therefore to address this open question. Specifically, we will propose a new variant of local SGD that will allow each agent to find exactly x_ℋ^⋆ in both strongly convex and non-convex settings. Our main contribution is summarized as follows. 



Main contribution. We propose a new two-time-scale variant of local SGD for solving problem (<ref>) in the Byzantine setting under the 2f-redundancy condition. We will show that the proposed algorithm can return an exact solution x_ℋ^⋆ of problem (<ref>). In addition, we will study theoretical results to characterize the convergence rate of our algorithms when the underlying objective function satisfies either strong convexity or non-convex Polyak-Łojasiewicz (PŁ) condition. In both cases, our algorithm converges to the optimal solutions at an optimal rate 𝒪(1/k), where k is the number of iteration. Finally, we will provide a few numerical simulations to illustrate the correctness of our theoretical results.  











 §.§ Related work

According to existing literature, there are various Byzantine fault-tolerant aggregation schemes for distributed optimization and learning. These include multi-KRUM <cit.>, coordinate-wise trimmed mean (CWTM) <cit.>, geometric median-of-means(GMoM) <cit.>, minimum-diameter averaging (MDA) <cit.>, and Byzantine-robust stochastic aggregation (RSA) <cit.> filters. However, it is important to note that these schemes do not guarantee exact fault-tolerance even in a deterministic setting with 2f-redundancy, unless additional assumptions are made regarding the objectives of the honest agents. The work by <cit.> shows that it is possible to achieve exact fault tolerance in deterministic setting and approximate fault tolerance in stochastic setting in 2f-redundancy scenario. <cit.> proposed RESilient Averaging of Momentum (RESAM) which presents an unified byzantine fault-tolerant framework with accelerated gradient descent based on the previously mentioned methods. They also established finite time convergence with some additional assumptions. Although their results hold for non-convex objectives, they clearly proved that such generalization and acceleration cannot be applied for the CE aggregation scheme. Recently, <cit.> explored the impact of Byzantine agents and stragglers, where stragglers are agents that experience significant delays in their updates, on solving distributed optimization problems under the redundancy of cost functions. Furthermore, the authors examined Byzantine fault-tolerant min-max distributed optimization problems under similar redundancy conditions in <cit.>. Both works demonstrate that the authors' approach can only achieve approximate solutions. We also want to note some relevant work in <cit.>, where the authors study approximate fault tolerance problem with more relaxed conditions on the Byzantine agents. Our work in this paper builds on the works of <cit.> where based on the 2f-redundancy condition we propose a two-time-scale variant of the local SGD in both strongly convex non-convex setting. To address the affect of approximate convergence to optimal solution in byzantine free case minibatch SGD has been studied in <cit.>, <cit.> in order to reduce the dependency on the variance of the stochastic gradients. Here the authors have further proposed an accelerated version of the mini-batch SGD to further reduce the impact of gradient noise in both IID and non-IID sampling cases. However no such improvements have been addressed in literature when a given network is under attack from byzantine agents. 


Another relevant literature to this paper is the recent works in studying the complexity of two-time-scale stochastic approximation, see for example <cit.>. It has been observed that two-time-scale approach can be used to either study or design better distributed algorithms in different settings, e.g., delays <cit.>, quantization <cit.>, and cluster networks <cit.>. In this paper, we will leverage this idea to design a new resilient local SGD for the Byzantine setting. 


















§ RESILIENT TWO-TIME-SCALE LOCAL SGD


In this section, we present the proposed algorithm, namely, resilient two-time scale local SGD, for solving problem (<ref>) when there are up to f Byzantine agents. Our algorithm is formally stated in Algorithm <ref>, where  each honest agent i∈ℋ maintains two local variables x^i,y^i to estimate the optimal value x_ℋ^⋆ and its local gradient ∇ q^i(·), respectively. On the other hand, the server maintains a global variable x̅ to estimate the average of the iterates sent by the agents. At any global iteration k, each agent i∈ℋ implements 𝒯 two-time-scale SGD steps to update its variables (a.k.a Eqs. (<ref>) and (<ref>)), where ∇ q^i(·;Δ^i) is the sample of ∇ q^i(·). These two updates are implemented by using two different step sizes α_k≥β_k, i.e., the update of y^i is implemented at a “faster" time scale than x^i, explaining for the name of two-time-scale SGD. In particular, each agent first estimates its local gradient from the samples, which is then used to update its local variable toward the optimal solution x_ℋ^⋆. After 𝒯 steps, each honest agent will send its last iterate x_k,𝒯^i to the server. We note that Byzantine agents can send any arbitrarily to the server. To address this issue, the server will implement a comparative elimination (CE) filter, studied in <cit.>. In particular, the server first sorts the distance between the agent estimates and its average in an ascending order (Step 8). The server then eliminates the f largest distances (Step 9), i.e., since it does not know the identity of Byzantine agents the server can only eliminate any “suspiciously large values". The server then computes a new average based on the estimates of remaining N-f agents in Eq. (<ref>).  


In Eq. (<ref>), when α_k = 1 the proposed algorithm is reduced to the local SGD with CE filter studied in <cit.>. However, as we will show in this paper, by properly choosing α_k and β_k our algorithm will guarantee an exact convergence to x_ℋ^⋆ even under the Byzantine setting, which cannot be achieved by the one in <cit.>. In particular, we choose the step sizes to satisfy β_k≤α_k≤ 1 as follows

    α_k = C_α/1+h+k,   β_k = C_β/1+h+k,
       where   C_β≤ C_α  s.t. α_k≤ 1  and  L𝒯β_k≤ 1,  ∀ k≥0.

We will demonstrate in Theorems <ref> and <ref> that, with an appropriate selection of the parameter h > 1, this choice of step sizes is essential for the algorithm to achieve an optimal convergence rate of 𝒪(1/k). 











§ TECHNICAL ASSUMPTIONS AND PRELIMINARIES

We present here the main technical assumptions and some preliminaries, which will help to facilitate the development of our main results later. First, we consider the following two main assumptions, where 𝒫_k,t is the filtration that includes all the random variables generated by Algorithm <ref> up to time k+t. 


    The random variables Δ^i_k, ∀ i and k≥ 0, are i.i.d. and there exists a positive constant σ such that we have ∀ x ∈ℝ^d
    
    𝔼[∇ q^i(x,Δ^i_k,t)|𝒫_k,t] = ∇ q^i(x),
       𝔼[∇ q^i(x,Δ^i_k,t)-∇ q^i(x)^2|𝒫_k,t] ≤σ^2.



 For each i∈ℋ, q^i has Lispchitz continuous gradients, i.e., there exists a constant L>0 such that 

    ∇ q^i(y) - ∇ q^i(x)≤ L y-x,  ∀ x,y ∈ℝ^d.


In the sequel, we will assume that these two assumptions always hold. For notational convenience, we define

    q_ℋ(x) = 1/|ℋ|∑_i ∈ℋq^i(x).

Let e_k,t^i be the local gradient estimate error at client i defined as

    e_k,t^i = y_k,t^i - ∇ q^i (x̅_k),

and W_k be the average of local gradient estimate error defined as 

    W_k = 1/|ℋ|∑_i ∈ℋe^i_k,0^2.

We denote by ℬ_k the set of potential Byzantine clients and ℋ_k the set of non-faulty clients in ℱ_k in step 9 in Algorithm <ref>. Finally, we denote by 𝒳^⋆_ℋ and 𝒳^⋆_i the sets of minimizers of q_ℋ and q^i, respectively. Then, under Assumption <ref> and the 2f-redundancy property, one can show that <cit.>

    ⋂_i∈ℋ𝒳^⋆_i = 𝒳^⋆_ℋ.

Using the notation above, we rewrite (<ref>) as follows: ∀ i∈ℋ

    x^i_k,𝒯    = x_k -β_k∑_t=0^𝒯-1e^i_k,t -𝒯β_k∇ q^i(x̅_k),

which since |ℱ_k| = |ℋ| and |ℬ_k| = |ℋ\ℋ_k| yields

    x_k+1   =1/|ℱ_k|∑_i ∈ℱ_kx^i_k,𝒯
       =1/|ℋ|[∑_i∈ℋx^i_k,𝒯 + ∑_i∈ℬ_kx^i_k,𝒯 - ∑_i∈ℋ\ℋ_kx^i_k,𝒯],
       = x̅_k - 𝒯β_k∇ q_ℋ(x̅_k) - β_k/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t
          + 1/|ℋ|[∑_i∈ℬ_k(x^i_k,𝒯 -x_k) - ∑_i∈ℋ\ℋ_k(x^i_k,𝒯-x_k)].

    
    
    
    





























































































































    









































































































































































We next consider the following result on W_k, where for an ease of exposition its proof will be presented in the Appendix.  

For all k≥ 0 we have 
    
    𝔼[W_k+1]
         
         
         
         
         
           ≤(1-α_k/2 + 126(L+1)^2𝒯^2β_k)𝔼[W_k]
          +(14L^3𝒯^2α_kβ_k + 300L^4𝒯^2β^2_k/α_k)𝔼[x̅_k-x^⋆_ℋ^2]
         + 2σ^2𝒯α^2_k + 96L^2𝒯^2σ^2β^2_k
         + 6L^2𝒯^2σ^2α^2_kβ^2_k + 96L^2𝒯^2σ^2fα_kβ^2_k/|ℋ|·

























































































































































































§ MAIN RESULTS


In this section, we present the main results of this paper, where we will study the convergence properties of Algorithm <ref> in two settings, namely, strong convexity and PL conditions. 




 §.§ Strongly convex condition

We consider the following assumption on q_ℋ(x).

The objective function q_ℋ(.) is strongly convex, i.e., there exists a constant μ∈ (0,L] s.t.

    (y-x)^T(∇ q_ℋ(y) - ∇ q_ℋ(x)) ≥μy-x^2,  ∀ x,y ∈ℝ^d.



Assumption <ref> guarantees a unique solution x_ℋ^⋆ for problem (<ref>). However, it does not require each local function q^i to be strongly convex, meaning each q^i may have multiple minimizers. Note that under the 2f-redundancy condition, we have x_ℋ^⋆ lies in the intersection of the minimizer sets 𝒳_i^⋆ of  q^i.

Our main result in this section is based on the following lemma, whose proof is presented in the Appendix.

For all k ≥ 0 we have
    
    𝔼[x̅_k+1-x^⋆_ℋ^2]
       ≤(1-35μ𝒯β_k/18 + 17L𝒯β_k|ℬ_k|/3|ℋ|+ 103L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + 72L^2𝒯α_kβ_k/μ𝔼[x̅_k-x^⋆_ℋ^2] +  78𝒯β_k/μ𝔼[W_k]
          + 4𝒯^2σ^2α_kβ^2_k + 
        48𝒯σ^2α^2_kβ_k/μ + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|·









































    































































































































































To study the convergence of Algorithm <ref> under Assumption <ref>, we consider the following Lyapunov function V_k 

    V_k = x̅_k - x^⋆_ℋ^2 + W_k.



    Let {x^i_k} and {y^i_k} be generated by Algorithm <ref> for 𝒯>1. 
    Suppose the step sizes α_k and β_k in (<ref>) satisfying 

    α_k≤μ/(8)^4(L+1)^4𝒯,   β_k≤μ/(12)^4L^2𝒯, 
    β_k/α_k≤μ/(14)^4(L+1)^4𝒯·

    Then we have

    𝔼[V_k+1]
       ≤(1-23μ𝒯β_k/12 + 17L𝒯β_k|ℬ_k|/3|ℋ|)𝔼[V_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|·

In addition, if the following condition holds 
    
    |ℬ_k|/|ℋ| = f/N-f≤μ/3L,

  and C_α, C_β and h are chosen as

    C_α≥(84)^4(L+1)^4/6μ^2,    C_β = 72/μ𝒯
        h ≥max{(8)^4(L+1)^4𝒯C_α/μ; (72)^4L^2/18μ^2},

then we obtain the following.

    𝔼[V_k+1]    ≤h^2𝔼[V_0]/(1+h+k)^2 + 150(L+1)^3𝒯^2σ^2C^2_α/μ(1+h+k)
         + 128(L+1)^2𝒯^2σ^2fC^2_α/(1+h+k)|ℋ|·
    


Our result in (<ref>) implies that the sequence {x̅_k} generated by Algorithm <ref> converges to x^⋆_ℋ in the mean-square sense at a rate 𝒪(1/k), which is the same rate as in the Byzantine-free setting. In addition, our convergence complexity bound depends on the ratio f/ℋ, which is similar to the result in <cit.>.  
     




































    By adding (<ref>) into (<ref>) we have
    
    𝔼[V_k+1]
       ≤(1-35μ𝒯β_k/18 + 17L𝒯β_k|ℬ_k|/3|ℋ| + 103L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + (300L^4𝒯^2β^2_k/α_k + 72L^2𝒯α_kβ_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
         + 14L^3𝒯^2α_kβ_k𝔼[x̅_k-x^⋆_ℋ^2]
         +(1-α_k/2 + 126(L+1)^2𝒯^2β_k + 78𝒯β_k/μ)𝔼[W_k]
         + 2𝒯σ^2α^2_k + 4𝒯^2σ^2α_kβ^2_k + 42𝒯^2σ^2α_kβ_k/μ
          + 6L^2𝒯^2σ^2α^2_kβ^2_k + 96L^2𝒯^2σ^2β^2_k
          + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ| + 96L^2𝒯^2σ^2fα_kβ^2_k/|ℋ|
       ≤(1-35μ𝒯β_k/18 + 17L𝒯β_k|ℬ_k|/3|ℋ| + 103L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + (300L^4𝒯^2β^2_k/α_k + 72L^2𝒯α_kβ_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
         + 14L^3𝒯^2α_kβ_k𝔼[x̅_k-x^⋆_ℋ^2]
         +(1-α_k/2 + 126(L+1)^2𝒯^2β_k + 78𝒯β_k/μ)𝔼[W_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|
       ≤(1-69μ𝒯β_k/36 + 17L𝒯β_k|ℬ_k|/3|ℋ|)𝔼[V_k] 
          + (-μ𝒯β_k/36 + 103L^2𝒯^2β^2_k + 14L^3𝒯^2α_kβ_k)𝔼[x̅_k - x^⋆_ℋ^2]
          +(72L^2𝒯α_kβ_k/μ + 300L^4𝒯^2β^2_k/α_k)𝔼[x̅_k - x^⋆_ℋ^2]
          +(-α_k/2 + 69μ𝒯β_k/36 + 126(L+1)^2𝒯β_k + 78𝒯β_k/μ)𝔼[W_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|,

    where the second inequality is obtained using β_k≤α_k≤ 1 and μ≤ L. 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    Using μ≤ L we express the above inequality as
    
    𝔼[V_k+1]
       ≤(1-69μ𝒯β_k/36 + 17L𝒯β_k|ℬ_k|/3|ℋ|)𝔼[V_k] 
         +(-μ𝒯β_k/36 +103L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_k^2]
         + (86(L+1)^4𝒯^2α_kβ_k/μ + 300(L+1)^4𝒯β_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
         +(-α_k/2 +206(L+1)^4𝒯β_k/μ)𝔼[W_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|
       ≤(1-69μ𝒯β_k/36 + 17L𝒯β_k|ℬ_k|/3|ℋ|)𝔼[V_k] 
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|,

    
    
    
    
    
    

























where the last inequality we use (<ref>) to have 

    0 ≤μ𝒯β_k/36 -103L^2𝒯^2β^2_k - 86(L+1)^4𝒯^2α_kβ_k/μ
            -300(L+1)^4𝒯^2β^2_k/α_k,
       0≤α_k/2 - 206(L+1)^4𝒯β_k/μ·















Next, to show (<ref>) we observe that the conditions (<ref>) satisfy those in (<ref>). Thus, we have

    𝔼[V_k+1]
       ≤(1-𝒯β_k(23μ/12 - 17L|ℬ_k|/3|ℋ|))𝔼[V_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|.
        
       ≤(1-μ𝒯β_k/36)𝔼[V_k]
          + 150(L+1)^3𝒯^2σ^2α^2_k/μ + 128(L+1)^2𝒯^2σ^2fα^2_k/|ℋ|,

where the last inequality is due to (<ref>) 

    23μ/12 - 17L|ℬ_k|/3|ℋ|≥μ/36·







Using β_k = 72/μ𝒯(1+h+k) we obtain from above

    𝔼[V_k+1]   ≤(1-2/1+h+k)𝔼[V_k]
          + 150(L+1)^3𝒯^2σ^2C^2_α/μ(1+h+k)^2 + 128(L+1)^2𝒯^2σ^2fC^2_α/(1+h+k)^2|ℋ|,

which by multiplying both sides  by (1+h+k)^2 gives

    (1+h+k)^2𝔼[V_k+1]
       ≤ (h+k)^2𝔼[V_k] 
         + 150(L+1)^3𝒯^2σ^2C^2_α/μ + 128(L+1)^2𝒯^2σ^2fC^2_α/|ℋ|
       ≤ h^2𝔼[V_0]+ 150(L+1)^3𝒯^2σ^2C^2_α(k+1)/μ
         + 128(L+1)^2𝒯^2σ^2fC^2_α(k+1)/|ℋ|·

By dividing both sides of the above inequality by (1+h+k)^2 we immediately obtain (<ref>), which concludes our proof. 






























































































































































































 §.§ Non-convex satisfying PL condition


In this section, we will present the results for the case where  q_ℋ(x) satisfy the so-called PŁ  condition presented below.
  There exists a constant μ>0 s.t. 

    1/2∇ q_ℋ(x_k)^2≥μ (q_ℋ(x_k) - q_ℋ(x^⋆_ℋ)) ≥μ^2/2x_k - x^⋆_ℋ^2.





Next we consider following lemma, where we present its proof in the Appendix.












































We have for all k≥ 0
    
    𝔼[ q_ℋ(x_k+1) - q_ℋ(x_k)]
       ≤(-5𝒯β_k/6 + 2L𝒯β_k|ℬ_k|/|ℋ| + 110L^3𝒯^2β^2_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2]
          +50𝒯β_k𝔼[W_k] + 30𝒯σ^2α^2_k + 16L𝒯^2σ^2α_kβ^2_k + 16𝒯^2σ^2fα^2_k/|ℋ|·




































































































































































































For our result, we consider the following Lyapunov function 

    V_k = (q_ℋ(x̅_k)-q_ℋ(x^⋆_ℋ)) + W_k.
















Let Assumption <ref> hold. Let α_k and β_k be given in  (<ref>) and satisfy
    
    α_k   ≤μ^2/(6)^4(L+1)^3𝒯,   β_k≤μ^2/(12)^4L^3𝒯,
         β_k/α_k≤μ^2/(12)^4(L+1)^4𝒯^2·

    Then for all k ≥ 0 we have
    
    𝔼[V_k+1]
               ≤(1 -9μ𝒯β_k/6 + 4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[V_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|·

    Further, let C_α, C_β and h satisfy
    
    C_α≥(12)^5(L+1)^4𝒯/μ^3,    C_β = 12/μ𝒯
        h ≥max{(6)^4(L+1)^3𝒯C_α/μ^2; (12)^5L^3/μ^3},

    and the condition (<ref>) hold. Then we obtain

    𝔼[V_k+1] 
       ≤h^2𝔼[V_0]/(1+h+k)^2 + 150𝒯σ^2C_α^2/(1+h+k) + 112𝒯^2σ^2fC_α^2/(1+h+k)|ℋ|·
    


Our result in (<ref>) implies that q_ℋ(x̅_k) converges to the optimal function value q_ℋ(x^⋆_ℋ)  at a rate 𝒪(1/k), which is the same rate as in the Byzantine-free setting. In addition, our convergence complexity bound depends on the ratio f/ℋ, which is similar to the result in <cit.>. 
    


    Using Lemmas <ref> and <ref> we obtain
    
    𝔼[ q_ℋ(x_k+1)- q_ℋ(x_k)] + 𝔼[W_k+1]
       ≤(-5𝒯β_k/6 + 2L𝒯β_k|ℬ_k|/μ|ℋ| + 110L^3𝒯^2β^2_k/μ^2) 𝔼[∇ q_ℋ(x̅_k)^2]
         + (14L^3𝒯^2α_kβ_k/μ^2+ 300L^4𝒯^2β^2_k/μ^2α_k)𝔼[∇ q_ℋ(x̅_k)^2]
         +(1-α_k/2 + 78β_k𝒯/μ + 126(L+1)^2𝒯^2β_k)𝔼[W_k]
         +30𝒯σ^2α^2_k + 16L𝒯^2σ^2α_kβ^2_k + 2𝒯σ^2α_k^2
         + 96L^2𝒯^2σ^2β^2_k + 6L^2𝒯^2σ^2α^2_kβ^2_k
         + 16𝒯^2σ^2fα^2_k/|ℋ| + 96L^2𝒯^2σ^2fα^2_k/|ℋ|,

    which since β_k≤α_k≤ 1 
    
    
    
    
    
   gives
    
    𝔼[ q_ℋ(x_k+1)- q_ℋ(x^⋆_k)] + 𝔼[W_k+1]
         -𝔼[ q_ℋ(x_k)- q_ℋ(x^⋆_k)]
       ≤(-5𝒯β_k/6 + 2L𝒯β_k|ℬ_k|/μ|ℋ| + 110L^3𝒯^2β^2_k/μ^2) 𝔼[∇ q_ℋ(x̅_k)^2]
         + (14L^3𝒯^2α_kβ_k/μ^2+ 300L^4𝒯^2β^2_k/μ^2α_k)𝔼[∇ q_ℋ(x̅_k)^2]
         +(1-α_k/2 + 78β_k𝒯/μ + 126(L+1)^2𝒯^2β_k)𝔼[W_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|·

    By the definition of V_k in (<ref>) we have from the relation above
    
    𝔼[V_k+1]
       ≤(1-9μ𝒯β_k/6+4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[V_k]
         +(9μ𝒯β_k/6-4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[q_ℋ(x̅_k)-q_ℋ(x^⋆_ℋ)]
         +(-5𝒯β_k/6 + 2L𝒯β_k|ℬ_k|/μ|ℋ| + 110L^3𝒯^2β^2_k/μ^2) 𝔼[∇ q_ℋ(x̅_k)^2]
         + (14L^3𝒯^2α_kβ_k/μ^2+ 300L^4𝒯^2β^2_k/μ^2α_k)𝔼[∇ q_ℋ(x̅_k)^2]
         +(-α_k/2 + 78β_k𝒯/μ + 126(L+1)^2𝒯^2β_k)𝔼[W_k]
         +(9μ𝒯β_k/6-4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[W_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|,

    which by Assumption <ref> gives
    
    
    
    
    
    
    
    
    
    
    
    
    𝔼[V_k+1]
       ≤(1-9μ𝒯β_k/6 + 4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[V_k]
          +(-𝒯β_k/12+ 110L^3𝒯^2β^2_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2]
         + (14L^3𝒯^2α_kβ_k/μ^2+ 300L^4𝒯^2β^2_k/μ^2α_k)𝔼[∇ q_ℋ(x̅_k)^2]
         +(-α_k/2 + 9μ𝒯β_k/6 + 204(L+1)^4𝒯^2β_k/μ^2)𝔼[W_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|
       ≤(1-9μ𝒯β_k/6 + 4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[V_k]
          +(-𝒯β_k/12+ 110L^3𝒯^2β^2_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2]
         + (14L^3𝒯^2α_kβ_k/μ^2+ 300L^4𝒯^2β^2_k/μ^2α_k)𝔼[∇ q_ℋ(x̅_k)^2]
         +(-α_k/2 +206(L+1)^4𝒯^2β_k/μ^2)𝔼[W_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|
       ≤(1-9μ𝒯β_k/6 + 4L𝒯β_k|ℬ_k|/|ℋ|)𝔼[V_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|,

    where the last inequality we use (<ref>) to have 

    0≤𝒯β_k/12- 110L^3𝒯^2β^2_k/μ^2 - 14L^3𝒯^2α_kβ_k/μ^2 - 300L^4𝒯^2β^2_k/μ^2α_k,
       0 ≤α_k/2 - 206(L+1)^4𝒯^2β_k/μ^2·

 
 
 
 
 
   
   
   
   
   
To show  (<ref>),  we use (<ref>) into the relation above to obtain
    
    
    
    
     
    𝔼[V_k+1]   ≤(1-μβ_k𝒯/6)𝔼[V_k]
         +150(L+1)^2𝒯^2σ^2α^2_k + 112(L+1)^2𝒯^2σ^2fα_k^2/|ℋ|,

    which by using β_k = 12/μ𝒯(1+h+k)  gives

    𝔼[V_k+1]   ≤(1-2/1+h+k)𝔼[V_k] 
         + 150𝒯σ^2C_α^2/(1+h+k)^2 + 112𝒯^2σ^2fC_α^2/(1+h+k)^2|ℋ|.

Multiplying both sides of the above inequality by (1+h+k)^2 gives

    (1+h+k)^2𝔼[V_k+1]
       ≤ (h+k)^2𝔼[V_k] + 40𝒯σ^2C_α^2 + 112𝒯^2σ^2fC_α^2/|ℋ|
       ≤ h^2𝔼[V_0]+ 150𝒯σ^2C_α^2(k+1) + 112𝒯^2σ^2fC_α^2(k+1)/|ℋ|,

which when diving both sides by (k + 1 + h)^2  gives (<ref>). 













































§ SIMULATIONS









    


























In this section we present a few simulations to illustrate the convergence of Algorithm <ref> and the correctness of our theoretical results. For our simulations, we consider a network of N = 50 agents. Each non-faulty agent i has access to 100 noisy observations of a 10-dimensional vector x^⋆. Specifically, the sample set X^i comprises 100 samples distributed as X^i_j = x^⋆ + Z_j, where Z_j ∼𝒩(0, I_d). On the other hand, a Byzantine faulty agent j mimics the behavior of an honest agent but with different samples. Each sample for a Byzantine agent is given by X^j_j = 2 ×x^⋆ + Z_j, where Z_j ∼𝒩(0, I_d), similar to the honest agents. This implies that while honest agents send information corresponding to Gaussian noisy observations of x^⋆, the Byzantine agents send information corresponding to Gaussian noisy observations with the same variance but centered at 2 ×x^⋆.


We will simulate Algorithm <ref> in both strongly convex and PŁ  conditions, where we set the local steps 𝒯 = 3. In each case, we vary the number of Byzantine agents f = 4,8,10 to study the convergence of our algorithm when this number is changing.  For the strongly convex setting, we consider the local cost function of i^th agent as


    q^i(x; X^i) = 1/2x - X^i^2.



For the PŁ  condition, we consider the following local cost function


    q^i(x; X^i) = 1/2x - X^i^2 + 1/2sin^2(x - X^i).

In this case, the global function ∑_i = 1^50 q^i(x; X^i) represents a non-convex function that satisfies the Polyak-Łojasiewicz (PL) condition. 








Our simulation results are shown in Figs. <ref> and <ref> for strongly convex and PŁ  conditions, respectively. 

First, our simulations show that the optimization and gradient estimate errors converge to zero as expected.  Second, the rates of convergence seem to be 𝒪(1/k), which are consistent in both cases. Finally, the algorithm converges slower as the number of faulty agents increases, agreeing with our theoretical bounds in Theorems <ref> and <ref>.







§ CONCLUSION

In this paper, we propose a new two-time-scale variant of the local SGD method to solve an exact Byzantine fault-tolerance problem under the 2f-redundancy condition. 

Our theoretical analysis demonstrates that our approach effectively mitigates the impact of noise from stochastic gradients and the interference of Byzantine agents. Notably, our algorithm achieves an optimal rate 𝒪(1/k) when the underlying objective function satisfies either strong convexity or the PŁ  condition, similar to that of the Byzantine-free setting.




IEEEtran



[Proofs of Lemmas <ref>–<ref>]
We now proceed to present the analysis of Lemmas <ref>–<ref>. First, we rewrite (<ref>) as follows

    x̅_k+1   = x̅_k - 𝒯β_k∇ q_ℋ(x̅_k) - β_k/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t + ℰ_x.

where 
    
    ℰ_x = 1/|ℋ|[∑_i∈ℬ_k(x^i_k,𝒯 -x_k) - ∑_i∈ℋ\ℋ_k(x^i_k,𝒯-x_k)].

Next, we will consider the following results that will be used in our analysis later. 

For each honest client i ∈ℋ we have
    
    x^i_k,t+1-x_k^2≤ 2L^2t^2β_k^2x_k-x^⋆_ℋ^2 + 2tβ_k^2∑_l=0^te^i_k,l^2.



    By (<ref>) and (<ref>), we have 

    x^i_k,t+1-x_k^2 = ∑_l=0^t(x^i_k,l+1-x^i_k,l)^2
       ≤ t∑_l=0^tx^i_k,l+1-x^i_k,l^2 = β_k^2t∑_l=0^ty^i_k,l^2
       = β_k^2t∑_l=0^te_k,t^i + ∇ q^i(x̅_k)^2
       ≤ 2β_k^2t∑_l=0^t(e_k,t^i^2  + ∇ q^i(x̅_k)^2)
       = 2β_k^2t∑_l=0^t(e_k,t^i^2  + ∇ q^i(x̅_k -∇ q^i(x_ℋ^⋆)^2)
       ≤ 2L^2t^2β_k^2x_k-x^⋆_ℋ^2 + 2tβ_k^2∑_l=0^te^i_k,l^2,

where in the last equality we use (<ref>) to have ∇ q^i(x_ℋ^⋆) = 0 and the last inequality is due to Assumption <ref>. This concludes our proof. 


For each honest client i ∈ℋ we have 


    𝔼[e_k,t+1^i^2]
       ≤ (1-α_k)𝔼[e^i_k,t^2] + α_kL^2𝔼[x^i_k,t-x̅_k^2] + α^2_kσ^2.
    



    Using (<ref>) and (<ref>) we consider

    e^i_k,t+1 = (1-α_k)y^i_k,t + α_k∇ q^i(x^i_k,t;Δ^i_k,t) - ∇ q^i(x_k)
        = (1-α_k)e^i_k,t + α_k(∇ q^i(x^i_k,t;Δ^i_k,t) - ∇ q^i(x^i_k,t))
          +α_k(∇ q^i(x^i_k,t)-∇ q^i(x_k)),

which by using Assumptions <ref> and <ref> gives

    𝔼[e^i_k,t+1^2|𝒫_k,t]
       = (1-α_k)^2e^i_k,t^2 + α^2_k∇ q^i(x^i_k,t)-∇ q^i(x_k)^2
          + α^2_k𝔼[∇ q^i(x^i_k,t;Δ^i_k,t) - ∇ q^i(x^i_k,t)^2|𝒫_k,t]
          + 2α_k(1-α_k)(∇ q^i(x^i_k,t)-∇ q^i(x_k))^Te^i_k,t
          + 2 α_k(1-α_k)𝔼[(∇ q^i(x^i_k,t,Δ^i_k,t) - ∇ q^i(x^i_k,t))|𝒫_k,t]^Te^i_k,t
          +2α^2_k𝔼[(∇ q^i(x^i_k,t,Δ^i_k,t) - ∇ q^i(x^i_k,t))|𝒫_k,t]^T
       × (∇ q^i(x^i_k,t)-∇ q^i(x_k)
       = (1-α_k)^2e^i_k,t^2 + α^2_k∇ q^i(x^i_k,t)-∇ q^i(x_k)^2
          + α^2_k𝔼[∇ q^i(x^i_k,t;Δ^i_k,t) - ∇ q^i(x^i_k,t)^2|𝒫_k,t]
          + 2α_k(1-α_k)(∇ q^i(x^i_k,t)-∇ q^i(x_k))^Te^i_k,t
       ≤ (1-α_k)^2e^i_k,t^2 + L^2α^2_kx^i_k,t - x̅_k^2 + α^2_kσ^2
           + 2α_k(1-α_k)(∇ q^i(x^i_k,t) - ∇ q^i(x_k))^Te^i_k,t.

Taking the expectation on both sides of the preceding equation and using the Cauchy-Schwarz inequality we obtain (<ref>), i.e.,

    𝔼[e^i_k,t+1^2] 
       ≤ (1-α_k)^2𝔼[e^i_k,t^2] + L^2α^2_k𝔼[x^i_k,t - x̅_k^2^2] + α^2_kσ^2
           + α_k(1-α_k)𝔼[e^i_k,t^2]+ L^2α_k(1-α_k)𝔼[x^i_k,t-x_k^2]
        = (1-α_k)𝔼[e^i_k,t^2] + L^2α_k𝔼[x^i_k,t - x̅_k^2] + α^2_kσ^2.





Let α_k satisfy for all k≥ 0

    α_k≤1/2L𝒯·

Then the following holds
    
    1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1𝔼[e^i_k,t^2] 
       ≤ 2𝒯𝔼[W_k] + 2𝒯σ^2α_k + 4L^4𝒯^3β_k^2𝔼[x̅_k-x_ℋ^⋆^2].



    By taking (<ref>) recursively and since α_k < 1 we have
    
    𝔼[e^i_k,t^2]
               ≤ (1-α_k)^t𝔼[e^i_k,0^2] + α_k^2σ^2∑_l=0^t-1(1-α_k)^t-1-ℓ
           + α_kL^2∑_ℓ = 0^t-1(1-α_k)^t-l-1𝔼[x^i_k,l-x̅_k^2]
       ≤ (1-α_k)^t𝔼[e^i_k,0^2] + α_kσ^2
         + α_kL^2∑_ℓ = 0^t-1(1-α_k)^t-l-1𝔼[x^i_k,l-x̅_k^2],

    which by using (<ref>) gives
    
    𝔼[e^i_k,t^2]
       ≤ (1-α_k)^t𝔼[e^i_k,0^2] + α_kσ^2
          +2L^4𝒯^2α_kβ_k^2∑_ℓ=0^t-1(1-α_k)^t-ℓ-1𝔼[x̅_k-x_ℋ^⋆^2]
          +2L^2𝒯α_kβ_k^2∑_ℓ=0^t-1(1-α_k)^t-ℓ-1∑_m = 0^ℓ-1𝔼[e_k,m^i^2]
       ≤ (1-α_k)^t𝔼[e^i_k,0^2] + α_kσ^2+2L^4𝒯^2β_k^2𝔼[x̅_k-x_ℋ^⋆^2]
          +2L^2𝒯α_kβ_k^2∑_ℓ=0^t-1(1-α_k)^t-ℓ-1∑_m = 0^𝒯-1𝔼[e_k,m^i^2]
       ≤ (1-α_k)^t𝔼[e^i_k,0^2] + α_kσ^2 + 2L^4𝒯^2β_k^2𝔼[x̅_k-x_ℋ^⋆^2]
          +2L^2𝒯β_k^2∑_m = 0^𝒯-1𝔼[e_k,m^i^2].

Using the relation above and the definition of W_k in (<ref>) we have
    
    1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1𝔼[e^i_k,t^2] 
       ≤1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1(1-α_k)^t𝔼[e^i_k,0^2] + 𝒯σ^2α_k
          + 2L^4𝒯^3β_k^2𝔼[x̅_k-x_ℋ^⋆^2] 
          + 2L^2𝒯^2β_k^21/|ℋ|∑_i ∈ℋ∑_m = 0^𝒯-1𝔼[e_k,m^i^2]
       ≤𝔼[W_k] + 𝒯σ^2α_k + 2L^4𝒯^3β_k^2𝔼[x̅_k-x_ℋ^⋆^2] 
          + 2L^2𝒯^2β_k^21/|ℋ|∑_i ∈ℋ∑_m = 0^𝒯-1𝔼[e_k,m^i^2],

    where the last inequality we use the fact that 1-α_k≤ 1.  Since β_k≤α_k≤ 1/2L𝒯 implying 1-2L^2T^2β_k^2 > 1/2, rearranging the preceding relation we obtain (<ref>).
    
    
    
    
    
    
    



Let α_k satisfy (<ref>). Then we have

    𝔼[x_k+1 - x_k^2]   ≤ 100L^2𝒯^2β^2_k𝔼[x̅_k-x^⋆_ℋ^2]  + 40β^2_k𝒯^2𝔼[W_k] 
         + 32𝒯^2σ^2α_kβ^2_k + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|·




    By (<ref>) and since ∇ q_ℋ(x^⋆_ℋ)) = 0 we have

    x_k+1-x_k^2
       = ℰ_k-𝒯β_k∇ q_ℋ(x_k)-β_k/|ℋ|∑_i∈ℋ∑_l=0^𝒯-1e^i_k,l^2
       ≤ 2ℰ_x^2 + 2𝒯β_k(∇ q_ℋ(x_k)+β_k/|ℋ|∑_i∈ℋ∑_l=0^𝒯-1e^i_k,l^2
       ≤ 2ℰ_x^2 + 4𝒯^2β_k^2∇ q_ℋ(x_k)^2  + 4β^2_k𝒯/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2
        = 2ℰ_x^2 + 4𝒯^2β_k^2∇ q_ℋ(x_k)-∇ q_ℋ(x^⋆_ℋ))^2
            + 4β^2_k𝒯/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2
       ≤ 2ℰ_x^2 + 4L^2𝒯^2β^2_kx_k - x^⋆_ℋ^2 + 4β^2_k𝒯/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2.

Taking the expectation of the preceding relation and using (<ref>) give

    𝔼[x̅_k+1-x̅_k^2]
       ≤ 2𝔼[ℰ_k^2] + (4L^2𝒯^2β^2_k + 16L^4𝒯^4β^4_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + 8𝒯^2β^2_k𝔼[W_k].

Next, we analyze the term ℰ_x^2. For this using (<ref>), we have 
     
    ℰ_x^2 = 1/|ℋ|[∑_i∈ℬ_k(x^i_k,𝒯 -x_k) - ∑_i∈ℋ\ℋ_k(x^i_k,𝒯-x_k)]^2.

     By (<ref>), we have x^i_k,𝒯-x_k≤x^j_k,𝒯-x_k for all i ∈ℬ_k and j ∈ℋ\ℋ_k. Thus, we obtain
     

    ℰ_x^2   ≤2|ℬ_k|/|ℋ|^2∑_i ∈ℬ_kx^i_k,𝒯 - x_k^2 + 2|ℬ_k|/|ℋ|^2∑_i ∈ℋ\ℋ_kx^i_k,𝒯 - x_k^2
       ≤4|ℬ_k|/|ℋ|^2∑_i ∈ℋ\ℋ_kx^i_k,𝒯 - x_k^2,

which by (<ref>) yields

    ℰ_x^2
       ≤4|ℬ_k|/|ℋ|^2∑_i ∈ℋ\ℋ_k(2L^2𝒯^2β_k^2x_k-x^⋆_ℋ^2+ 2𝒯β_k^2∑_l=0^𝒯-1e^i_k,l^2)
       ≤8L^2𝒯^2β_k^2|ℬ_k|^2/|ℋ|^2x_k-x^⋆_ℋ^2 + 8𝒯β_k^2|ℬ_k|/|ℋ|^2∑_i ∈ℋ\ℋ_k∑_l=0^𝒯-1e^i_k,l^2.

Using (<ref>) we obtain from the preceding relation

    𝔼[ℰ_x^2]
       ≤(8L^2𝒯^2β^2_k|ℬ_k|^2/|ℋ|^2 + 32α_kβ^4_kL^4𝒯^4|ℬ_k|/|ℋ|)𝔼[x̅_k-x^⋆_ℋ^2]
          +16β^2_k𝒯^2|ℬ_k|/|ℋ|𝔼[W_k] + 16α^2_kβ^2_k𝒯^2|ℬ_k|σ^2/|ℋ|,

which when using (<ref>) and  β_kL𝒯≤ 1 gives (<ref>), i.e., 

    𝔼[x̅_k+1-x̅_k^2]
       ≤(16L^2𝒯^2β^2_k|ℬ_k|^2/|ℋ|^2 + 64L^2𝒯^2β^2_k|ℬ_k|/|ℋ|)𝔼[x̅_k-x^⋆_ℋ^2]
          + (4L^2𝒯^2β^2_k + 16L^4𝒯^4β^4_k)𝔼[x̅_k-x^⋆_ℋ^2]
         +(8𝒯^2β^2_k + 32𝒯^2β^2_k|ℬ_k|/|ℋ|)𝔼[W_k]
          + 32𝒯^2σ^2α_kβ^2_k + 32𝒯^2σ^2|ℬ_k|α^2_kβ^2_k/|ℋ|
       ≤ 100L^2𝒯^2β^2_k𝔼[x̅_k-x^⋆_ℋ^2]  + 40β^2_k𝒯^2𝔼[W_k] 
         + 32𝒯^2σ^2α_kβ^2_k + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|,

where the last inequality we use |ℬ_k| ≤ f, |ℬ_k|/|ℋ|≤f/N-f≤ 1.





 §.§ Proof of Lemma <ref>

From (<ref>) using y^i_k+1,0 = y^i_k,𝒯 we have

    e^i_k+1,0    = y^i_k,𝒯- ∇ q^i(x_k+1)
        
        = e^i_k,𝒯 + ∇ q^i(x_k)-∇ q^i(x_k+1).

Using the Cauchy-Schwarz inequality and Assumption <ref> we obtain

    e^i_k+1,0^2   ≤(1+α_2/2)e^i_k,𝒯^2 + (1+2/α_k)L^2x_k+1-x_k^2
       ≤(1+α_2/2)e^i_k,𝒯^2 + 3L^2/α_kx_k+1-x_k^2.

Thus, we have

    𝔼[W_k+1] = 1/|ℋ|∑_i ∈ℋ𝔼[e^i_k+1,0^2]
       ≤(1+α_k/2)1/|ℋ|∑_i ∈ℋ𝔼[e^i_k,𝒯^2] + 3L^2/α_k𝔼[x_k+1 - x_k^2].


By (<ref>), we consider

    𝔼[e^i_k,𝒯^2]   ≤ (1-α_k)^𝒯𝔼[e^i_k,0^2] + α_k^2σ^2∑_t=0^𝒯-1(1-α_k)^𝒯-1-t
           + α_kL^2∑_t = 0^𝒯-1(1-α_k)^𝒯-t-1𝔼[x^i_k,t-x̅_k^2]
       ≤ (1-α_k)𝔼[e^i_k,0^2] + σ^2𝒯α^2_k
           + α_kL^2∑_t = 0^𝒯-1𝔼[x^i_k,t-x̅_k^2]
       ≤ (1-α_k)𝔼[e^i_k,0^2]  + L^4T^3α_kβ_k^2𝔼[x_k-x^⋆_ℋ^2
            + 2L^2𝒯α_kβ_k^2∑_t=0^𝒯e^i_k,t^2]+ σ^2𝒯α^2_k,

where the last inequality is due to (<ref>). Using this equation and (1+α_k/2) ≤ 3/2 we obtain

    (1+α_k/2)1/|ℋ|∑_i ∈ℋ𝔼[e^i_k,𝒯^2]
       ≤(1+α_k/2)1/|ℋ|∑_i ∈ℋ(1-α_k)𝔼[e^i_k,0^2] + 2σ^2𝒯α^2_k
          + 2  L^4T^3α_kβ_k^2𝔼[x_k-x^⋆_ℋ^2]
            + 3L^2𝒯α_kβ_k^21/|ℋ|∑_i ∈ℋ∑_t=0^𝒯𝔼[e^i_k,t^2]
       ≤(1-α_k/2)𝔼[W_k] + 2σ^2𝒯α^2_k
          + 2  L^4T^3α_kβ_k^2𝔼[x_k-x^⋆_ℋ^2]
            + 3L^2𝒯α_kβ_k^21/|ℋ|∑_i ∈ℋ∑_t=0^𝒯𝔼[e^i_k,t^2],


where the last inequality we use 

    (1-α_k)(1+α_k/2) ≤ 1-α_k/2·

Thus, substitute the relation above into (<ref>) we have

    𝔼[W_k+1]    ≤(1-α_k/2)𝔼[W_k] + 2σ^2𝒯α^2_k
          + 2  L^4𝒯^3α_kβ_k^2𝔼[x_k-x^*_ℋ^2]
            + 3L^2𝒯α_kβ_k^21/|ℋ|∑_i ∈ℋ∑_t=0^𝒯𝔼[e^i_k,t^2]
          + 3L^2/α_k𝔼[x_k+1 - x_k^2]
       ≤(1-α_k/2)𝔼[W_k] + 2σ^2𝒯α^2_k
          + 2  L^4𝒯^3α_kβ_k^2𝔼[x_k-x^*_ℋ^2]
            + 6L^2𝒯^2α_kβ_k^2𝔼[W_k] + 6L^2𝒯^2σ^2α_k^2β_k^2
            + 12L^6𝒯^4α_kβ_k^4𝔼[x̅_k-x_ℋ^⋆^2]
          + 3L^2/α_k𝔼[x_k+1 - x_k^2]
       = (1-α_k/2+ 6L^2𝒯^2α_kβ_k^2)𝔼[W_k]
             + 2σ^2𝒯α^2_k + 6L^2𝒯^2σ^2α_k^2β_k^2
           + (2  L^4𝒯^3α_kβ_k^2 + 12L^6𝒯^4α_kβ_k^4)𝔼[x̅_k-x_ℋ^⋆^2]
          + 3L^2/α_k𝔼[x_k+1 - x_k^2],

where we use (<ref>) to obtain the second inequality.  
Next, applying Lemma <ref>, the above inequality becomes

    𝔼[W_k+1]    ≤(1-α_k/2)𝔼[W_k]
          +(6L^2𝒯^2α_kβ^2_k + 120L^2𝒯^2β^2_k/α_k)𝔼[W_k]
          +(2L^4𝒯^3α_kβ^2_k + 12L^6𝒯^4α_kβ^4_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + 300L^4𝒯^2β^2_k/α_k𝔼[x̅_k-x^⋆_ℋ^2]+ 2σ^2𝒯α^2_k
          + 96L^2𝒯^2σ^2β^2_k+ 6L^2𝒯^2σ^2α^2_kβ^2_k
          + 96L^2𝒯^2σ^2fα_kβ^2_k/|ℋ|.

Using β_k ≤α_k and β_kL𝒯≤ 1  we obtain


    𝔼[W_k+1]    ≤(1-α_k/2)𝔼[W_k]
          + (6L𝒯β_k + 120L^2𝒯^2β_k)𝔼[W_k]
          +(14L^3𝒯^2α_kβ_k + 300L^4𝒯^2β^2_k/α_k)𝔼[x̅_k-x^⋆_ℋ^2]
         + 2σ^2𝒯α^2_k + 96L^2𝒯^2σ^2β^2_k
         + 6L^2𝒯^2σ^2α^2_kβ^2_k + 96L^2𝒯^2σ^2fα_kβ^2_k/|ℋ|
       ≤(1-α_k/2 + 126(L+1)^2𝒯^2β_k)𝔼[W_k]
          +(14L^3𝒯^2α_kβ_k + 300L^4𝒯^2β^2_k/α_k)𝔼[x̅_k-x^⋆_ℋ^2]
         + 2σ^2𝒯α^2_k + 96L^2𝒯^2σ^2β^2_k
         + 6L^2𝒯^2σ^2α^2_kβ^2_k + 96L^2𝒯^2σ^2fα_kβ^2_k/|ℋ|·




 §.§ Proof of Lemma <ref>

    
    
    
    
    
    Using (<ref>) we have
    
    x_k+1 -x^*_ℋ^2
       = x̅_k-x^*_ℋ - 𝒯β_k∇ q_ℋ(x̅_k)^2 + ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2
          -2(x̅_k-x^*_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)
       = P_1 + P_2 + P_3 ,

where P_i, for i = 1, 2, 3, are defined in that order. Firstly, using ∇ q_ℋ(x^⋆_ℋ) = 0 along with Assumption <ref> and <ref> we analyze the term P_1 as

    
    x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k)^2
       = x̅_k-x^⋆_ℋ^2-2𝒯β_k∇ q_ℋ(x̅_k)^T(x̅_k-x^⋆_ℋ) 
         + 𝒯^2β^2_K∇ q_ℋ(x̅_k)^2
       = x̅_k-x^⋆_ℋ^2-2𝒯β_k(∇ q_ℋ(x̅_k)-∇ q_ℋ(x^⋆_ℋ))^T(x̅_k-x^⋆_ℋ) 
         + 𝒯^2β^2_K∇ q_ℋ(x̅_k)-∇ q_ℋ(x^⋆_ℋ)^2
       ≤ (1-2μ𝒯β_k + L^2𝒯^2β^2_k)x̅_k-x^⋆_ℋ^2


    Secondly, using Cauchy-Schwarz inequality term P_2 can be expressed as
    
    ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2
       ≤ 2ℰ_x^2+ 2β^2_k𝒯(1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2).


Taking the expectation on both sides of the above inequality, and applying Lemma <ref> along with (<ref>) from Lemma <ref> with α_k≤ 1 , we obtain the following


    𝔼[ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2]
       ≤(16L^2𝒯^2β^2_k|ℬ_k|/|ℋ| + 64L^3𝒯^3β^3_k|ℬ_k|/|ℋ|)𝔼[x̅_k -x^⋆_ℋ^2]
          + 8L^4𝒯^4β^4_k𝔼[x̅_k -x^⋆_ℋ^2] 
          +(32𝒯^2β^2_k|ℬ_k|/|ℋ| + 4𝒯^2β^2_k)𝔼[W_k]
          + 4𝒯^2σ^2α_kβ^2_k + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|
       ≤ 88L^2𝒯^2β^2_k𝔼[x̅_k -x^⋆_ℋ^2] + 36𝒯β_k/μ𝔼[W_k]
          + 4𝒯^2σ^2α_kβ^2_k + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|,

where the last inequality is obtained using β_kL𝒯≤ 1 and μ≤ L.
Thirdly we express term P_3 from (<ref>) as  

    -2(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)
       = -2(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^Tℰ_x
          +2(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)
       = P_3a + P_3b,

where P_3a and P_3b are defined in that order. 
Next, we apply the Cauchy-Schwarz inequality 2a^Tb ≤ηa^2 + b^2/η for any η >0, and use Assumptions <ref> and <ref> to analyze term P_3a. Thus, we have

    -2(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^Tℰ_x
       ≤3L𝒯β_k|ℬ_k|/|ℋ|x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k)^2 + |ℋ|/3L𝒯β_k|ℬ_k|ℰ_x^2
    
       ≤3L𝒯β_k|ℬ_k|/|ℋ| (x̅_k-x^⋆_ℋ^2+L^2𝒯^2β_k^2x̅_k-x^⋆_ℋ^2) 
         + |ℋ|/3L𝒯β_k|ℬ_k|ℰ_x^2.

 Next taking expectation on both sides of the above inequality and using (<ref>) from Lemma <ref> along with α_k≤ 1, we have

    -2𝔼[(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^Tℰ_x]
       ≤(17L𝒯β_k|ℬ_k|/3|ℋ|+32L^2𝒯^2β_k^2/3+3L^3𝒯^3β_k^3|ℬ_k|/|ℋ|)𝔼[x̅_k-x^⋆_ℋ^2] 
          + 16β_k𝒯/3L𝔼[W_k] + 16𝒯σ^2α^2_kβ_k/3L
       ≤(17L𝒯β_k|ℬ_k|/3|ℋ|+ 14L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_ℋ^2] 
          + 16𝒯β_k/3μ𝔼[W_k] + 16𝒯σ^2α^2_kβ_k/3μ,

where the last inequality is obtained using β_kL𝒯≤ 1, |ℬ_k|/|ℋ|≤ 1 and μ≤ L. To analyze the term P_3b from (<ref>), we use the Cauchy-Schwarz along with Assumption <ref> and <ref> to obtain

    2(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)
       ≤μ𝒯β_k/18x̅_k-x^⋆_ℋ -𝒯β_k∇ q_ℋ(x̅_k)^2
          + 18β_k/μ(1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2)
       ≤μ𝒯β_k/18(x̅_k-x^⋆_ℋ^2 + L^2𝒯^2β^2_kx̅_k-x^⋆_ℋ^2)
         + 18β_k/μ(1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2).

Next, taking expectation on both the sides of the above inequality along with the result from Lemma <ref> we have 

    2𝔼[(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)]
       ≤(μ𝒯β_k/18 + μ L^2𝒯^3β^3_k/18+72L^4𝒯^3α_kβ^3_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
          +36β_k𝒯/μ𝔼[W_k] + 36𝒯σ^2α^2_kβ_k/μ
       ≤(μ𝒯β_k/18 +  L^2𝒯^2β^2_k/18+72L^2𝒯α_kβ_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
          +36β_k𝒯/μ𝔼[W_k] + 36𝒯σ^2α^2_kβ_k/μ,

where the last inequality is obtained using μ≤ L and β_kL𝒯≤ 1. Putting back the results from (<ref>) and (<ref>) back into (<ref>), we have

    -2𝔼[(x̅_k-x^⋆_ℋ - 𝒯β_k∇ q_ℋ(x̅_k))^T(ℰ_x -β_k/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)]
       ≤(μ𝒯β_k/18+17L𝒯β_k|ℬ_k|/3|ℋ|)𝔼[x̅_k-x^⋆_ℋ^2]
          + (15L^2𝒯^2β^2_k + 72L^2𝒯α_kβ_k/μ)𝔼[x̅_k-x^⋆_ℋ^2]
          +42𝒯β_k/μ𝔼[W_k] + 42𝒯σ^2α^2_kβ_k/μ.

Finally, by taking the expectation on both sides of (<ref>), substituting the expressions for P_1, P_2, and P_3 from (<ref>), (<ref>), and (<ref>), respectively we obtain


    𝔼[x̅_k+1-x^⋆_ℋ^2] 
       ≤(1-35μ𝒯β_k/18 + 17L𝒯β_k|ℬ_k|/3|ℋ|+ 103L^2𝒯^2β^2_k)𝔼[x̅_k-x^⋆_ℋ^2]
          + 72L^2𝒯α_kβ_k/μ𝔼[x̅_k-x^⋆_ℋ^2] +  78𝒯β_k/μ𝔼[W_k]
          +4𝒯^2σ^2α_kβ^2_k + 48𝒯σ^2α^2_kβ_k/μ + 32𝒯^2σ^2fα^2_kβ^2_k/|ℋ|.

This concludes our proof.
















































































































































    































































































































































 §.§ Proof of Lemma <ref>

To prove lemma <ref> we require the following lemma.

    
    ℰ_k≤2L𝒯β_k|ℬ_k|/μ|ℋ|∇ q_ℋ(x̅_k) + 2β_k(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t).



    Using the definition of ℰ_k from (<ref>) we have
    
    ℰ_x≤1/|ℋ|∑_i ∈ℬ_kx^i_k,𝒯-x̅_k + 1/|ℋ|∑_i ∈ℋ\ℋ_kx^i_k,𝒯-x̅_k.

    By (<ref>), there exists j ∈ℋ\ℋ_k such that x^i_k,t-x_k≤x^j_k,t-x_k for all agent i ∈ℬ_k using which the above inequality becomes
    
    ℰ_x≤|ℬ_k|/|ℋ|x^j_k,𝒯-x̅_k +1/|ℋ|∑_i ∈ℋ\ℋ_kx^j_k,𝒯-x̅_k.

Here, we consider that there exists an agent j ∈ℋ\ℋ_k such that the quantity x^j_k,t-x_k is maximum over all the agents in the set ℋ\ℋ_k. Further since |ℋ\ℋ_k| = |ℬ_k|, we have 

    x^j_k,t-x_k^2   ≤1/|ℋ\ℋ_k|∑_i ∈ℋ\ℋ_kx^i_k,t-x_k^2
       =1/|ℬ_k|∑_i ∈ℋ\ℋ_kx^i_k,t-x_k^2.
 
Next using (<ref>) which implies ∇ q^i(x^*_ℋ) =0 which  with the result from (<ref>), we express (<ref>) as

    ℰ_k   ≤2/|ℋ|∑_ℋ\ℋ_kx^i_k,𝒯-x̅_k
       ≤2/|ℋ|∑_ℋ\ℋ_k(-𝒯β_k∇ q^i(x̅_k)-β_k∑_t=0^𝒯-1e^i_k,t)
       ≤2𝒯β_k/|ℋ|∑_i ∈ℋ\ℋ_k∇ q^i(x̅_k)-∇ q^i(x^⋆_ℋ)
          +2β_k/|ℋ|∑_i ∈ℋ\ℋ_k∑_t=0^𝒯-1e^i_k,t
       ≤2L𝒯β_k|ℬ_k|/|ℋ|x̅_k-x^⋆_ℋ + 2β_k(1/|ℋ|∑_i ∈ℋ\ℋ_k∑_t=0^𝒯-1e^i_k,t)
       ≤2L𝒯β_k|ℬ_k|/μ|ℋ|∇ q_ℋ(x̅_k)+ 2β_k(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t),

where the second last inequality is due to Assumptiom <ref> and last inequality is obtained using Assumption <ref>.






























 §.§ Proof of Lemma <ref>


Assumption <ref> implies q_ℋ has Lipschitz continuous gradient using which we have

    q_ℋ(x_k+1)-  q_ℋ(x_k)
       ≤∇ q_ℋ(x_k)^T(x_k+1-x_k) + L/2x_k+1-x_k^2.

Using (<ref>), we analyze the first term in the right hand side of the above equation as the following

    ∇ q_ℋ(x_k)^T(x_k+1-x_k)
       = -𝒯β_k∇ q_ℋ(x_k)^2 -β_k∇ q_ℋ(x_k)^T(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t) 
         + ℰ_x^T∇ q_ℋ(x_k)
        = A_1 + A_2 +A_3,

where A_i with i=1,2,3 are defined in that order. To analyze A_2, we apply Assumption <ref> and utilize the Cauchy-Schwarz inequality. Thus, we have







    -β_k∇ q_ℋ(x_k)^T(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t) 
       ≤β_k𝒯/12∇ q_ℋ(x̅_k)^2 + 3β_k/𝒯1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2
       ≤β_k𝒯/12∇ q_ℋ(x̅_k)^2 + 3β_k(1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l^2).

Taking expectation on both the sides of the above inequality and using Lemma <ref> along with Assumption <ref> we have

    -𝔼[β_k∇ q_ℋ(x_k)^T(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t)] 
       ≤(β_k𝒯/12 + 12L^4𝒯^3β^3_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2] + 6β_k𝒯𝔼[W_k] 
         + 6σ^2𝒯α_kβ_k.














































Next, to analyze term A_3 from (<ref>) we use Lemma <ref> and Cauchy-Schwarz ineuqlity to obtain

    ℰ_x^T∇ q_ℋ(x_k)   ≤ℰ_x∇ q_ℋ(x_k)
       ≤2L𝒯β_k|ℬ_k|/μ|ℋ|∇ q_ℋ(x_k)^2
         + 2β_k∇ q^ℋ(x̅_k)(1/|ℋ|∑_i ∈ℋ∑_l=0^𝒯-1e^i_k,l)
       ≤(2L𝒯β_k|ℬ_k|/μ|ℋ| + 𝒯β_k/12)∇ q_ℋ(x̅_k)^2
          + 12β_k(1/|ℋ|∑_i ∈ℋ∑_t=0^𝒯-1e^i_k,t^2).

Taking expectation on both sides of the above inequality and using Lemma <ref> we have

    𝔼[ℰ_x^T∇ q_ℋ(x̅_k)]
       ≤(2L𝒯β_k|ℬ_k|/μ|ℋ| + 𝒯β_k/12 + 48L^4𝒯^3β^3_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2] 
          + 24𝒯β_k𝔼[W_k] + 24𝒯σ^2α_kβ_k.

Finally putting back the relations from (<ref>) and (<ref>) back into (<ref>) and using L𝒯β_k≤ 1 we get

    𝔼[∇ q_ℋ(x̅_k)^T(x̅_k+1-x̅_k)]
       ≤(-5β_k𝒯/6 +  2Lβ_k𝒯|ℬ_k|/μ|ℋ| + 60L^3𝒯^2β^2_k/μ^2)𝔼[∇ q_ℋ(x̅_k)^2] 
          + 30β_k𝒯𝔼[V^k_2]+30σ^2𝒯α^2_k.



























Next, using Lemma <ref>, we analyze the second term in the right hand side of (<ref>). Thus we have

    L/2𝔼[x̅_k+1-x̅_k^2]
       ≤ 50L^3𝒯^2β^2_k𝔼[x̅_k-x^*_ℋ^2]  + 20L𝒯^2β^2_k𝔼[W_k] 
         + 16L𝒯^2σ^2α_kβ^2_k + 16L𝒯^2σ^2fα^2_kβ^2_k/|ℋ|
       ≤50L^3𝒯^2β^2_k/μ^2𝔼[∇ q_ℋ(x̅_k)^2]  + 20𝒯β_k𝔼[W_k] 
         + 16L𝒯^2σ^2α_kβ^2_k + 16L𝒯^2σ^2fα^2_kβ^2_k/|ℋ|,

where the last inequality is obtained using Assumption <ref> and the condition L𝒯β_k≤ 1. 

Putting back the results from (<ref>) and (<ref>) back into (<ref>) we immediately obtain (<ref>).































