Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimization

## Abstract

Abstract Federated Learning is a popular distributed learning paradigm in machine learning.
Meanwhile, composition optimization is an effective hierarchical learning model, which
appears in many machine learning applications such as meta learning
and robust learning. More recently, although a few federated composition optimization algorithms have been proposed, they still suffer from high sample and communication complexities.
In the paper, thus, we propose a class of faster federated compositional optimization algorithms (i.e., MFCGD and AdaMFCGD) to solve the nonconvex distributed composition problems, which builds on the momentum-based variance reduced and local-SGD techniques. In particular, our adaptive algorithm (i.e., AdaMFCGD) uses a unified adaptive matrix to flexibly incorporate various adaptive learning rates. Moreover, we provide a solid theoretical analysis for our algorithms under non-i.i.d. setting, and prove our algorithms obtain a lower sample and communication complexities simultaneously than the existing federated compositional algorithms. Specifically, our algorithms obtain lower sample complexity of O ~ ​ ( ϵ − 3 ) ~ 𝑂 superscript italic-ϵ 3 \tilde{O}(\epsilon^{-3}) with lower communication complexity of O ~ ​ ( ϵ − 2 ) ~ 𝑂 superscript italic-ϵ 2 \tilde{O}(\epsilon^{-2}) in finding an ϵ italic-ϵ \epsilon -stationary solution.
We conduct the numerical experiments on robust federated learning and distributed meta learning tasks to demonstrate the efficiency of our algorithms.

## 1 Introduction

Composition optimization is an effective hierarchical model, which is widely used to many applications such as reinforcement learning [Wang et al., , Huo et al., ],
meta learning [Wang et al., ], risk management [Huo et al., ] and deep AUC maximization  [Yuan et al., ].
In the paper, we study the following distributed composition optimization problem:

$$ $\displaystyle\min_{x\in\mathbb{R}^{d}}$ $\displaystyle\ F(x):=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}\bigg{[}f^{m}\Big{(}\mathbb{E}_{\zeta^{m}\sim\mathcal{S}^{m}}\big{[}g^{m}(x;\zeta^{m})\big{]};\xi^{m}\Big{)}\bigg{]},$ (1) $$

where $y^{m}=g^{m}(x)=\mathbb{E}_{\zeta^{m}\sim\mathcal{S}^{m}}\big{[}g^{m}(x;\zeta^{m})\big{]}$ and $f^{m}(y^{m})=\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}\big{[}f^{m}(y^{m};\xi^{m})\big{]}$
for any $m\in[M]$ denote the inner
and outer objective functions respectively in
$m$-th client. Here $\xi^{m}$ and $\zeta^{m}$ for any $m\in[M]$ are independent random variables follow unknown distributions $\mathcal{D}^{m}$
and $\mathcal{S}^{m}$ respectively. For any $m,j\in[M]$ possibly $\mathcal{D}^{m}\neq\mathcal{D}^{j}$,
$\mathcal{S}^{m}\neq\mathcal{S}^{j}$ and $\mathcal{D}^{m}\neq\mathcal{S}^{j}$.
Applications of the problem ([1](#S1.E1)) involves many machine learning problems with a compositional structure, which include model-agnostic meta learning [Tutunov et al., , Chen et al., , Wang et al., ],
reinforcement learning [Wang et al., , Huo et al., ] and sparse additive models [Wang et al., ].
In the following, we give two specific applications
that can be formulated as the distributed composition optimization problem ([1](#S1.E1)).

**Table 1: Sample and Communication complexities comparison of the representative federated compositional optimization algorithms in finding an $\epsilon$-stationary solution of the distributed composition optimization problem ([1](#S1.E1)), i.e., $\mathbb{E}\|\nabla F(x)\|\leq\epsilon$ or its equivalent variants. ALR denotes adaptive learning rate.**
| Algorithm | Reference | Sample Complexity | Communication Complexity | ALR |
| --- | --- | --- | --- | --- |
| ComFedL | Huang et al. [] | $O(\epsilon^{-8})$ | $O(\epsilon^{-4})$ |  |
| LocalMOML | Wang et al. [] | $O(\epsilon^{-5})$ | $O(\epsilon^{-3})$ |  |
| FEDNEST | Tarzanagh et al. [] | $\tilde{O}(\epsilon^{-4})$ | $\tilde{O}(\epsilon^{-4})$ |  |
| Local-SCGDM | Gao et al. [] | $O(\epsilon^{-4})$ | $O(\epsilon^{-3})$ |  |
| MFCGD | Ours | $\tilde{O}(\epsilon^{-3})$ | $\tilde{O}(\epsilon^{-2})$ |  |
| AdaMFCGD | Ours | $\tilde{O}(\epsilon^{-3})$ | $\tilde{O}(\epsilon^{-2})$ | $\checkmark$ |

1). Task-Distributed Meta Learning.
Meta Learning is to learn some properties in the optimal model to improve model performances
with more experiences, i.e., learning to learn [Andrychowicz et al., ].
Model-Agnostic Meta Learning (MAML) [Finn et al., ] is a class of popular meta learning methods,
which is to find a common initialization that can adapt to a desired model for a set of new tasks after taking several gradient descent steps.
In the paper, we consider a class of task-distributed MAMLs, where a set of tasks $\{\mathcal{T}_{m}\}_{m=1}^{M}$ are drawn from a certain task distribution
and each task is assigned in each client.
Specifically, we solve the following task-distributed MAML problem:

$$ $\displaystyle\min_{x\in\mathbb{R}^{d}}\frac{1}{M}\sum_{m=1}^{M}f^{m}\big{(}x-\eta\nabla f^{m}(x)\big{)},$ (2) $$

where $f^{m}(x)=\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}[f(x;\xi^{m})]$, and random variable $\xi^{m}$ follows the unknown distribution $\mathcal{D}^{m}$, and $\eta>0$ is a learning rate.
Let $f^{m}(y^{m})=f^{m}(g^{m}(x))$ and $y^{m}=g^{m}(x)=x-\eta\nabla f^{m}(x)$, the above problem ([2](#S1.E2)) is a special case of the above composition problem [1](#S1.E1).

2). Distributionally Robust Federated Learning.
Federated learning (FL) [McMahan et al., , Kairouz et al., ] is a distributed and privacy preserving machine learning method to learn a global model
collaboratively from decentralized data distributed over a network of devices.
To tackle the data heterogeneity from different devices,
some robust FL algorithms [Mohri et al., , Reisizadeh et al., , Deng et al., ] have been studied.
In the paper, as in [Huang et al., ], we consider solving the following distributed composition problem
to reach distributionally robust FL, defined as

$$ $\displaystyle\min_{x\in\mathbb{R}^{d}}\frac{1}{M}\sum_{m=1}^{M}f\Big{(}\mathbb{E}\big{[}g^{m}(x;\xi^{m})\big{]}\Big{)},$ (3) $$

where $g^{m}(x)=\mathbb{E}\big{[}g^{m}(x;\xi^{m})\big{]}$ denotes the loss function in the $m$-th client,
and $f(\cdot)$ is a monotonically increasing function.
Clearly, the problem ([3](#S1.E3)) is a special case of the above problem ([1](#S1.E1)).

Although recently many compositional gradient algorithms have been proposed to solve the composition problems, few distributed algorithms focus on
solving the distributed composition optimization problems. More recently, Huang et al. [], Wang et al. [], Gao et al. [], Tarzanagh et al. [] proposed some federated compositional gradient algorithms for the distributed stochastic composition problems.
However, few adaptive algorithm focuses on
the composition optimization problems under the distributed setting.
Meanwhile, these existing federated composition optimization
methods suffer from large sample complexity and communication complexity (Please see Table [1](#S1.T1)).
Then there exists a natural question:

In the paper, we provide an affirmative answer to the above question and propose
a class of faster momentum-based federated compositional gradient descent algorithms (i.e., MFCGD and AdaMFCGD)
to solve the problem ([1](#S1.E1)),
which builds on the local Stochastic Gradient Descent (SGD) and momentum-based variance reduced techniques
to obtain a lower sample and communication complexities simultaneously.
Our main contributions are as follows:

- (1)
We propose a class of faster momentum-based federated compositional gradient descent algorithms (i.e., MFCGD and AdaMFCGD) to solve the nonconvex distributed composition problems, which builds on the momentum-based variance reduced and local-SGD techniques. In particular, our adaptive algorithm (i.e., AdaMFCGD) uses a unified adaptive matrix to flexibly incorporate various adaptive learning rates.
- (2)
We provide a solid convergence analysis framework for our algorithms under non-i.i.d. setting, and prove that our algorithms obtain simultaneously lower sample complexity of $\tilde{O}(\epsilon^{-3})$
and lower communication complexity of $\tilde{O}(\epsilon^{-2})$ than the existing federated composition methods for finding an $\epsilon$-stationary solution (Please see Table [1](#S1.T1)).
- (3)
Experimental results demonstrate efficiency of our algorithms on the robust federated learning and task-distributed meta learning.

## 2 Related Works

In this section, we overview some representative composition optimization, federated optimization and
adaptive optimization methods, respectively.

### 2.1 Composition Optimization

Composition optimization has been widely applied to
many applications such as reinforcement learning [Wang et al., ],
model-agnostic meta Learning [Tutunov et al., ] and risk management [Huo et al., ].
Recently, many compositional gradient-based methods have recently been proposed
to solve these composition optimization problems.
For example, stochastic compositional gradient methods [Wang et al., , , Ghadimi et al., ] have been proposed
to solve these problems.
Subsequently, some variance-reduced compositional algorithms [Huo et al., , Lin et al., , Zhang and Xiao, ]
have been proposed for composition optimization.
Tutunov et al. [], Chen et al. [] presented a class of momentum-based compositional
gradient methods for stochastic composition optimization. More recently, Jiang et al. [] proposed a class of efficient momentum-based variance reduced methods for non-convex
stochastic composition optimization. Huang and Gao [] studied the stochastic composition optimization on Riemannian manifolds.

For the distributed setting, Huang et al. [] firstly studied federated learning algorithm for the general distributed composition optimization. Meanwhile, Wang et al. [] studied personalized federated learning algorithm based on the composition optimization. Subsequently, Gao et al. [], Tarzanagh et al. [] proposed some accelerated federated learning algorithms for the distributed composition optimization.

### 2.2 Federated Optimization

Federated Learning (FL) is a popular distributed machine learning framework for collaboratively training the global model without sharing the local data, and is widely used in many applications such as healthcare informatics [Xu et al., ] and automatic diagnosis of COVID-19 [Yang et al., ]. McMahan et al. [] first studied FL and
proposed the FedAvg algorithm for FL based on local-SGD algorithms [Stich, ],
where each client conducts multiple steps of SGD with its local data
and then sends the learned model to the server for averaging.
Subsequently, [Li et al., , Karimireddy et al., , Deng and Mahdavi, ] have studied the convergence properties of the local-SGD and FedAvg algorithms or their variations.
To accelerate the vanilla local-SGD and FedAvg algorithms, various accelerated FL algorithms [Yuan and Ma, , Karimireddy et al., , Khanduri et al., , Chen et al., ] have been developed and studied.
For example, Karimireddy et al. [] proposed a stochastic controlled
averaging algorithm for FL by adopting the variance-reduced technique of SARAH [Nguyen et al., ]/SPIDER [Fang et al., ]. Subsequently, Khanduri et al. [] proposed a faster federated algorithm based on momentum-based variance reduced technique of STORM [Cutkosky and Orabona, ] and ProxHSGD [Tran-Dinh et al., ], which obtains lower sample and communication complexities simultaneously.

To solve the data heterogeneity in FL, Mohri et al. [], Deng et al. []
proposed some effective robust FL algorithms by learning the
worst-case loss based on the minimax optimization problems. To further incorporate personalization in FL,
some personalized federated learning models [Fallah et al., , Deng et al., , Li et al., ] have been developed and studied. For example, [Li et al., ] proposed an effective and efficient personalized FL
algorithm (i.e., Ditto) by learning a regularized local model for each client.

### 2.3 Adaptive Optimization Methods

Adaptive optimization methods [Duchi et al., , Kingma and Ba, ]
are a class of efficient optimization methods due to using adaptive learning rates in machine learning, and they have been widely studied in machine learning community.
For example, AdaGrad [Duchi et al., ] is the first adaptive gradient method.
Adam [Kingma and Ba, ] is a popular variation of AdaGrad algorithm based on the momentum technique, which is the default optimization algorithm
for training large-scale machine learning models.
Meanwhile, some variants of Adam algorithm [Reddi et al., , Chen et al., ]
have been proposed to obtain a convergence guarantee under the nonconvex setting.
To further improve the performance of Adam algorithm, recently some new its variants such as AdamW [Loshchilov and Hutter, ] have been developed.
More recently, some accelerated adaptive gradient methods [Cutkosky and Orabona, , Huang et al., ] have been proposed based on the momentum-based variance reduced techniques.
In parallel, some adaptive gradient methods [Reddi et al., , Chen et al., ] are proposed for distributed optimization. For example, Reddi et al. [] proposed a class of adaptive federated algorithms for FL
by using adaptive learning rates at the server side.

## 3 Preliminaries

### 3.1 Notations

Let $[M]$ denote the set $\{1,2,\cdots,M\}$.
$\|\cdot\|$ denotes the $\ell_{2}$ norm for vectors and Frobenius norm for matrices.
$\langle x,y\rangle$ denotes the inner product of two vectors $x$ and $y$. For vectors $x$ and $y$, $x^{r}\ (r>0)$ denotes the element-wise
power operation, $x/y$ denotes the element-wise division and $\max(x,y)$ denotes the element-wise maximum. $I_{d}$ denotes a $d$-dimensional identity matrix. $A\succ 0$ denotes that $A$ is a positive definite matrix.
$a_{t}=O(b_{t})$ denotes that $a_{t}\leq cb_{t}$ for some constant $c>0$. The notation $\tilde{O}(\cdot)$ hides logarithmic terms. $\Pi_{C}\big{[}x\big{]}=\arg\min_{||w||\leq C}||x-w||^{2}$ denote a projection onto the
ball with radius $C>0$.

### 3.2 Classic Federated Learning

The classic Federated Learning (FL) solves the following distributed optimization problem:

$$ $\displaystyle\min_{x\in\mathbb{R}^{d}}\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}[\ell_{m}(x;\xi^{m})],$ (4) $$

where $\ell_{m}(x;\xi^{m})$ is the loss function on $m$-th device,
and $\mathcal{D}^{m}$ denotes the data distribution on $m$-th device.
In FL, the data distributions $\{\mathcal{D}^{m}\}_{m=1}^{M}$ generally are different, i.e., for any $m,j\in[M]$ possibly $\mathcal{D}^{m}\neq\mathcal{D}^{j}$. The goal of FL is to
learn a global variable $x$ based on these heterogeneous data from different data distributions.

### 3.3 Federated Composition Optimization

In the paper, we studied Federated Composition Optimization (FCO) defined as:

$$ $\displaystyle\min_{x\in\mathbb{R}^{d}}$ $\displaystyle\ F(x):=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}\bigg{[}f^{m}\Big{(}\mathbb{E}_{\zeta^{m}\sim\mathcal{S}^{m}}\big{[}g^{m}(x;\zeta^{m})\big{]};\xi^{m}\Big{)}\bigg{]},$ (5) $$

where $y^{m}=g^{m}(x)=\mathbb{E}_{\zeta^{m}\sim\mathcal{S}^{m}}\big{[}g^{m}(x;\zeta^{m})\big{]}$ and $f^{m}(y^{m})=\mathbb{E}_{\xi^{m}\sim\mathcal{D}^{m}}\big{[}f^{m}(y^{m};\xi^{m})\big{]}$
for any $m\in[M]$ denote the inner
and outer objective functions respectively in
$m$-th client. Here $\xi^{m}$ and $\zeta^{m}$ for any $m\in[M]$ are independent random variables follow unknown distributions $\mathcal{D}^{m}$
and $\mathcal{S}^{m}$ respectively. For any $m,j\in[M]$ possibly $\mathcal{D}^{m}\neq\mathcal{D}^{j}$,
$\mathcal{S}^{m}\neq\mathcal{S}^{j}$ and $\mathcal{D}^{m}\neq\mathcal{S}^{j}$. Due to the existence of composition objective function and double unknown distributions, FCO has more challenges than classic FL.

## 4 Federated Compositional Gradient Descent Algorithms

In this section, we propose a class of faster momentum-based federated compositional gradient descent algorithms (i.e., MFCGD and AdaMFCGD) to
solve the problem ([1](#S1.E1)), which builds on the local-SGD and
momentum-based variance reduced techniques. Specifically, the local-SGD technique reduce the communication complexity and
the momentum-based variance reduced technique reduce the sample complexity without relying on large batches.
Meanwhile, our AdaMFCGD algorithm uses the unified adaptive matrix to flexibly
incorporate various adaptive learning rates in updating variables.
Specifically, Algorithm [1](#alg1) provides a procedure framework of our MFCGD and AdaMFCGD algorithms.

Figure: Algorithm 1 MFCGD and AdaMFCGD Algorithms

In Algorithm [1](#alg1), when $\mbox{mod}(t,q)=0$ (i.e., synchronization step), the server receives the local variables $\{x^{m}_{t}\}_{m=1}^{M}$ and
local gradients $\{w_{t}^{m}\}_{m=1}^{M}$ from the clients, and then averages them to obtain
the averaged variables $\{\bar{x}_{t}\}$ and averaged gradients $\{\bar{w}_{t}\}$.
Based on
these averaged gradients $\{\bar{w}_{t}\}$, we can generate some adaptive matrices $\{A_{t}\}_{t\geq 1}$ (i.e., adaptive learning rates).
Note that for our non-adaptive MFCGD algorithm, we only set $A_{t}=I_{d}$ for all $t\geq 1$ in Algorithm [1](#alg1).
Besides one example given
at the line 6 of Algorithm [1](#alg1), we can also generate many other adaptive matrices. For example, we can generate
adaptive matrix $A_{t}$ as the norm-type of Adam, defined as

$$ $\displaystyle a_{t}=\vartheta_{t}a_{t-1}+(1-\vartheta_{t})\|\bar{w}_{t}\|,\quad A_{t}=\mbox{diag}(a_{t}+\rho),$ (6) $$

where $0<\vartheta_{t}\leq 1$. Note that we can directly choose $\alpha_{t}$, $\beta_{t}$ or $\varrho_{t}$ instead of $\vartheta_{t}$ to reduce the number of tuning parameters in
our algorithm. Next, based on these adaptive matrices, we can update the variable $x$ in the server,
then sent it to each client.

When $\mbox{mod}(t,q)\neq 0$ (i.e., asynchronization step), the clients receive the updated variables $\{\bar{x}_{t+1}\}$
and the generated adaptive matrices $\{A_{t}\}$ from the server. Then the clients use the momentum-based variance reduced technique of STORM [Cutkosky and Orabona, ] and ProxHSGD [Tran-Dinh et al., ]
to update the stochastic gradients based on local data: for $m\in[M]$

$$ $\displaystyle h^{m}_{t+1}=g^{m}(x^{m}_{t+1};\zeta^{m}_{t+1})+(1-\alpha_{t+1})\big{(}h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\big{)}$ (7) $\displaystyle u^{m}_{t+1}=\Pi_{C_{g}}\Big{[}\nabla g^{m}(x^{m}_{t+1};\zeta^{m}_{t+1})+(1-\beta_{t+1})\big{(}u^{m}_{t}-\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\big{)}\Big{]}$ (8) $\displaystyle v^{m}_{t+1}=\Pi_{C_{f}}\Big{[}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})+(1-\varrho_{t+1})\big{(}v^{m}_{t}-\nabla f(h^{m}_{t};\xi^{m}_{t+1})\big{)}\Big{]},$ (9) $$

where $\alpha_{t+1}\in(0,1)$, $\beta_{t+1}\in(0,1)$ and $\varrho_{t+1}\in(0,1)$. Here the projection functions $\Pi_{C_{g}}\big{[}\cdot\big{]}$ and
$\Pi_{C_{f}}\big{[}\cdot\big{]}$ ensure that the estimated stochastic gradients $u^{m}_{t+1}$ and $v^{m}_{t+1}$ are bounded, i.e., $\|u^{m}_{t+1}\|\leq C_{g}$
and $\|v^{m}_{t+1}\|\leq C_{f}$ for any $t\geq 1$. Based on the estimated stochastic gradients and adaptive matrices, the clients
update the variables $\{x^{m}_{t}\}_{m=1}^{M}$, defined as

$$ $\displaystyle x^{m}_{t+1}=x^{m}_{t}-\gamma\eta_{t}A_{t}^{-1}w^{m}_{t}=\arg\min_{x\in\mathbb{R}^{d}}\Big{\{}\langle x,w^{m}_{t}\rangle+\frac{1}{2\eta_{t}\gamma}\big{(}x-x^{m}_{t}\big{)}^{T}A_{t}\big{(}x-x^{m}_{t}\big{)}\Big{\}},$ (10) $$

where $\gamma>0$ and $\eta_{t}>0$.
In our algorithms, all clients use the same adaptive matrix generated from the server as in [Chen et al., ]. Note that the existing adaptive FL algorithms such as
local-AMSGrad [Chen et al., ] only builds on some specific adaptive learning rates such as AMSGrad [Reddi et al., ]. However, our algorithms can use the unified adaptive matrix to flexibly incorporate various adaptive learning rates.

## 5 Convergence Analysis

In this section, we study the convergence properties of our MFCGD and AdaMFCGD algorithms under some mild assumptions. All related proofs are provided in the Appendix.
We first review some useful lemmas and assumptions.

###### Assumption 1 .

(Lipschitz Gradients)
For any $m\in[M]$, there exist constants $L_{f}$ and $L_{g}$ for $\nabla f^{m}(y;\xi^{m})$, $\nabla g^{m}(x;\zeta^{m})$ respectively satisfying

$$ $\displaystyle\|\nabla g^{m}(x_{1},\zeta^{m})-\nabla g^{m}(x_{2},\zeta^{m})\|\leq L_{g}\|x_{1}-x_{2}\|,\ \forall x_{1},x_{2}\in\mathbb{R}^{d},$ $\displaystyle\|\nabla f^{m}(y_{1};\xi^{m})-\nabla f^{m}(y_{2};\xi^{m})\|\leq L_{f}\|y_{1}-y_{2}\|,\ \forall y_{1},y_{2}\in\mathbb{R}^{p}.$ $$

###### Assumption 2 .

(Bounded Gradients)
For any $m\in[M]$, gradient $\nabla g^{m}(x;\zeta^{m})$ and Jacobian matrix $\nabla f^{m}(y;\xi^{m})$ have the upper bounds $C_{g}$ and $C_{f}$ respectively, i.e.,

$$ $\displaystyle\|\nabla g^{m}(x;\zeta^{m})\|\leq C_{g},\ \|\nabla f^{m}(y;\xi^{m})\|\leq C_{f},\ \forall x\in\mathbb{R}^{d},\ y\in\mathbb{R}^{p}.$ $$

###### Assumption 3 .

(Bounded Variances)
For any $m\in[M]$, functions $f^{m}(y;\xi^{m})$ and
$g^{m}(x;\zeta^{m})$ and its gradients are unbiased and the bounded variances, i.e., we have
$\mathbb{E}[g^{m}(x;\zeta^{m})]=g^{m}(x)$, $\mathbb{E}[\nabla g^{m}(x;\zeta^{m})]=\nabla g^{m}(x)$,
$\mathbb{E}[\nabla f^{m}(y;\xi^{m})]=\nabla f^{m}(y)$ and

$$ $\displaystyle\mathbb{E}\|g^{m}(x;\zeta^{m})-g^{m}(x)\|^{2}\leq\sigma^{2},\quad\mathbb{E}\|\nabla g^{m}(x;\zeta^{m})-\nabla g^{m}(x)\|^{2}\leq\sigma^{2},$ $\displaystyle\mathbb{E}\|\nabla f^{m}(y;\xi^{m})-\nabla f^{m}(y)\|^{2}\leq\sigma^{2},\quad\forall x\in\mathbb{R}^{d},\ y\in\mathbb{R}^{p}$ $$

where $\sigma>0$.

###### Assumption 4 .

$F(x)$ has a lower bound, i.e., $F^{*}=\inf_{x\in\mathbb{R}^{d}}F(x)$.

###### Assumption 5 .

In our algorithms, the adaptive matrix $A_{t}$ for all $t\geq 1$ satisfies
$A_{t}\succeq\rho I_{d}$, where $\rho>0$ is an appropriate positive number.

###### Assumption 6 .

For any $m,j\in[M]$, $x\in\mathbb{R}^{d}$ and $y\in\mathbb{R}^{p}$, we have $\|\nabla f^{m}(y)-\nabla f^{j}(y)\|\leq\delta_{f}$,
$\|\nabla g^{m}(x)-\nabla g^{j}(x)\|\leq\delta_{g}$ and $\|g^{m}(x)-g^{j}(x)\|\leq\delta_{g}$, where $\delta_{f}>0$ and $\delta_{g}>0$ are constants.

Assumptions [1](#Thmassumption1) ensures the smoothness of functions $f^{m}(y;\xi^{m})$, $g^{m}(x;\zeta^{m})$ for any $m\in[M]$,
Assumption [2](#Thmassumption2) ensures the bounded gradients (or Jacobian matrix) of functions $f^{m}(y;\xi^{m})$ and $g^{m}(x;\zeta^{m})$ for any $m\in[M]$.
Assumption [3](#Thmassumption3) ensures the bounded variances of stochastic gradient or value of functions $f^{m}(y;\xi^{m})$ and
$g^{m}(x;\zeta^{m})$ for any $m\in[M]$.
Assumption [4](#Thmassumption4) guarantees the feasibility of the problem ([1](#S1.E1)).
Assumptions [1](#Thmassumption1)-[4](#Thmassumption4) have been commonly used in the convergence
analysis of the stochastic composition algorithms [Wang et al., , ].
Assumption [5](#Thmassumption5) has been commonly used in the existing adaptive methods [Huang et al., ].
Assumption [6](#Thmassumption6) is the standard condition constrained the data heterogeneity
in non-i.i.d FL setting [Li et al., ]. In fact, we can obtain the part results of Assumption [6](#Thmassumption6) based on
Assumptions [1](#Thmassumption1)-[2](#Thmassumption2). For example, we have

$$ $\displaystyle\|\nabla f^{m}(y)-\nabla f^{j}(y)\|=\|\nabla f^{m}(y)-\nabla f^{m}(y;\xi^{m})+\nabla f^{m}(y;\xi^{m})-\nabla f^{j}(y;\xi^{j})+\nabla f^{j}(y;\xi^{j})-\nabla f^{j}(y)\|$ $\displaystyle\leq\|\nabla f^{m}(y)-\nabla f^{m}(y;\xi^{m})\|+\|\nabla f^{m}(y;\xi^{m})\|+\|\nabla f^{j}(y;\xi^{j})\|+\|\nabla f^{j}(y;\xi^{j})-\nabla f^{j}(y)\|$ $\displaystyle\leq 2\sigma+2C_{f},$ (11) $$

where the last inequality holds by Assumptions [1](#Thmassumption1)-[2](#Thmassumption2). Similarly, we have $\|\nabla g^{m}(y)-\nabla g^{j}(y)\|\leq 2\sigma+2C_{g}$ based on Assumptions [1](#Thmassumption1)-[2](#Thmassumption2).

###### Lemma 1 .

Given the above Assumptions [1](#Thmassumption1)-[2](#Thmassumption2),
the function $F(x)=\frac{1}{M}\sum_{m=1}^{M}f^{m}(g^{m}(x))$ is $L$-smooth, i.e., for any $x_{1},x_{2}\in\mathbb{R}^{d}$, we have

$$ $\displaystyle\|\nabla F(x_{1})-\nabla F(x_{2})\|^{2}\leq L^{2}\|x_{1}-x_{2}\|^{2},$ (12) $$

where $L=\sqrt{2C^{2}_{f}L^{2}_{g}+2C^{4}_{g}L^{2}_{f}}$.

###### Lemma 2 .

Assume the gradient estimator $\{\bar{w}_{t}\}_{t=1}^{T}$ generated from Algorithm [1](#alg1), where $w_{t}=\frac{1}{M}\sum_{m=1}^{M}w^{m}_{t}$,
we have

$$ $\displaystyle\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Big{(}2C_{f}^{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+4C_{g}^{2}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad+4C_{g}^{2}L^{2}_{f}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}.$ (13) $$

###### Assumption 1 .

###### Assumption 2 .

###### Assumption 3 .

###### Assumption 4 .

###### Assumption 5 .

###### Assumption 6 .

###### Lemma 1 .

###### Lemma 2 .

### 5.1 Convergence Properties of AdaMFCGD Algorithm

In this subsection, we provide the convergence properties of our AdaMFCGD algorithm.

###### Theorem 1 .

Assume the sequence $\{\bar{x}_{t}\}_{t=1}^{T}$ be generated from AdaMFCGD algorithm.
Under the above Assumptions, and let $\eta_{t}=\frac{k}{(n+t)^{1/3}}$ for all $t\geq 0$, $\alpha_{t+1}=c_{1}\eta_{t}^{2}$, $\beta_{t+1}=c_{2}\eta_{t}^{2}$, $\varrho_{t+1}=c_{3}\eta_{t}^{2}$, $n\geq\max\big{(}2,k^{3},(c_{1}k)^{3},(c_{2}k)^{3},(c_{3}k)^{3},\frac{(24k\gamma qL_{fg}C_{fg})^{3}}{\rho^{3}}\big{)}$, $k>0$,
$c_{1}\geq\frac{2}{3k^{3}}+B$, $c_{2}\geq\frac{2}{3k^{3}}+5C^{2}_{f}$, $c^{2}_{1}+c^{2}_{2}\leq\frac{(24)^{4}q^{2}\gamma^{4}L^{4}_{fg}C^{4}_{fg}}{9\rho^{4}}$, $c_{3}\geq\frac{2}{3k^{3}}+5C^{2}_{g}$, $\frac{\rho(c^{2}_{1}+c^{2}_{3})^{1/4}}{12\sqrt{5q}L_{fg}C_{fg}}\leq\gamma\leq\min\Big{(}\frac{3\rho qL_{fg}C_{fg}}{4(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})},\frac{n^{1/3}\rho}{2Lk}\Big{)}$, $B\geq 20C_{g}^{2}L^{2}_{f}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{216q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}+\frac{\Theta\rho^{2}(c_{1}^{2}+c_{3}^{2})}{30q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}$, $\Theta=\Big{(}5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}+\frac{\gamma\rho}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}$ and $\Theta+\frac{BC^{2}_{g}\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\leq\frac{5\rho^{2}}{48}$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\Big{(}\frac{\sqrt{2G}n^{1/6}}{T^{1/2}}+\frac{\sqrt{2G}}{T^{1/3}}\Big{)}\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}},$ (14) $$

where $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, $L^{2}_{fg}=L^{2}_{f}C^{2}_{g}+L^{2}_{g}$, $G=\frac{4(F(\bar{x}_{1})-F^{*})}{k\rho\gamma}+\frac{12n^{1/3}\sigma^{2}}{qk^{2}\rho^{2}}+4k^{2}\Big{(}\frac{\hat{\delta}^{2}}{4\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\rho\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)$ and $\hat{\delta}^{2}=2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}$.

###### Remark 1 .

Under the above Assumption [2](#Thmassumption2), we have $\big{\|}\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(\bar{x}_{t})\big{)}^{T}\nabla f^{m}(g^{m}(\bar{x}_{t}))\big{\|}\leq C_{f}C_{g}$. When the adaptive matrix $A_{t}$ be generated from the line 6 of Algorithm [1](#alg1), we have $\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}}\leq 2(C^{2}_{f}C^{2}_{g}+\rho)$.
Without loss of generality, let $k=O(1)$, $\rho=O(1)$, $c_{1}=O(1)$, $c_{2}=O(1)$, $c_{3}=O(1)$ and $n=O(q^{3})$,
we have and $G=\tilde{O}(1)$. Let $q=T^{1/3}$ and

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\tilde{O}\Big{(}\frac{\sqrt{q}}{\sqrt{T}}+\frac{1}{T^{1/3}}\Big{)}=\tilde{O}\Big{(}\frac{1}{T^{1/3}}\Big{)}\leq\epsilon,$ (15) $$

then we have $T=\tilde{O}(\epsilon^{-3})$. Since our AdaMFCGD algorithm requires $2$ samples at each iteration expect for the first iteration requires $2q$ samples, it has a sample complexity of $2q+2T=\tilde{O}(\epsilon^{-3})$. Thus, our AdaMFCGD algorithm requires $\tilde{O}(\epsilon^{-3})$ sample (or gradient) complexity
and $\frac{T}{q}=T^{2/3}=\tilde{O}(\epsilon^{-2})$ communication complexity to find an $\epsilon$-stationary point of the distributed composition problem ([1](#S1.E1)).

###### Remark 2 .

From Theorem [1](#Thmtheorem1), our AdaMFCGD algorithm simultaneously have lower sample and communication complexities than the existing federated compositional optimization algorithms (Please see Table [1](#S1.T1)).
Moreover, our AdaMFCGD algorithm simultaneously have lower sample and communication complexities than the existing adaptive single-level FL algorithms such as the local-AMSGrad [Chen et al., ] algorithm that needs sample complexity of $O(\epsilon^{-4})$ and communication complexity of $O(\epsilon^{-3})$ for finding an $\epsilon$-stationary point of the distributed single-level optimization problem, i.e., the above problem ([1](#S1.E1)) with $g^{m}(x)=x$ for all $m\in[M]$.

###### Theorem 1 .

###### Remark 1 .

###### Remark 2 .

### 5.2 Convergence Properties of MFCGD Algorithm

In this subsection, we provide the convergence properties of our non-adaptive MFCGD algorithm, i.e.,
set $A_{t}=I_{d}$ for all $t\geq 1$.

###### Theorem 2 .

Assume the sequence $\{\bar{x}_{t}\}_{t=1}^{T}$ be generated from MFCGD algorithm, i.e., $A_{t}=I_{d}$ for all $t\geq 1$ in Algorithm [1](#alg1).
Under the above Assumptions, and let $\eta_{t}=\frac{k}{(n+t)^{1/3}}$ for all $t\geq 0$, $\alpha_{t+1}=c_{1}\eta_{t}^{2}$, $\beta_{t+1}=c_{2}\eta_{t}^{2}$, $\varrho_{t+1}=c_{3}\eta_{t}^{2}$, $n\geq\max\big{(}2,k^{3},(c_{1}k)^{3},(c_{2}k)^{3},(c_{3}k)^{3},(24k\gamma qL_{fg}C_{fg})^{3}\big{)}$, $k>0$,
$c_{1}\geq\frac{2}{3k^{3}}+B$, $c_{2}\geq\frac{2}{3k^{3}}+5C^{2}_{f}$, $c^{2}_{1}+c^{2}_{2}\leq\frac{(24)^{4}q^{2}\gamma^{4}L^{4}_{fg}C^{4}_{fg}}{9}$, $c_{3}\geq\frac{2}{3k^{3}}+5C^{2}_{g}$, $\frac{(c^{2}_{1}+c^{2}_{3})^{1/4}}{12\sqrt{5q}L_{fg}C_{fg}}\leq\gamma\leq\min\Big{(}\frac{3qL_{fg}C_{fg}}{4(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})},\frac{n^{1/3}}{2Lk}\Big{)}$, $B\geq 20C_{g}^{2}L^{2}_{f}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{216q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}+\frac{\Theta(c_{1}^{2}+c_{3}^{2})}{30q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}$, $\Theta=\Big{(}5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{1}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}+\frac{\gamma}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}$ and $\Theta+\frac{BC^{2}_{g}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\leq\frac{5}{48}$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\frac{\sqrt{2G}n^{1/6}}{T^{1/2}}+\frac{\sqrt{2G}}{T^{1/3}},$ (16) $$

where $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, $L^{2}_{fg}=L^{2}_{f}C^{2}_{g}+L^{2}_{g}$, $G=\frac{4(F(\bar{x}_{1})-F^{*})}{k\gamma}+\frac{12n^{1/3}\sigma^{2}}{qk^{2}}+4k^{2}\Big{(}\frac{\hat{\delta}^{2}}{4\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)$ and $\hat{\delta}^{2}=2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}$.

###### Remark 3 .

The proof of Theorem [2](#Thmtheorem2) can totally follow the proofs of the above Theorem [1](#Thmtheorem1)
with the parameter $\rho=1$.
Without loss of generality, let $k=O(1)$, $c_{1}=O(1)$, $c_{2}=O(1)$, $c_{3}=O(1)$ and $n=O(q^{3})$,
we have and $G=\tilde{O}(1)$. Let $q=T^{1/3}$ and

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\tilde{O}\Big{(}\frac{\sqrt{q}}{\sqrt{T}}+\frac{1}{T^{1/3}}\Big{)}=\tilde{O}\Big{(}\frac{1}{T^{1/3}}\Big{)}\leq\epsilon,$ (17) $$

then we have $T=\tilde{O}(\epsilon^{-3})$. Since our MFCGD algorithm requires $2$ samples at each iteration expect for the first iteration requires $2q$ samples, it has a sample complexity of $2q+2T=\tilde{O}(\epsilon^{-3})$.
As the above AdaMFCGD algorithm, our MFCGD algorithm also obtain lower sample complexity of $\tilde{O}(\epsilon^{-3})$
and communication complexity of $\tilde{O}(\epsilon^{-2})$ in finding an $\epsilon$-stationary point of the problem ([1](#S1.E1)).

###### Theorem 2 .

###### Remark 3 .

## 6 Numerical Experiments

In this section, we apply some numerical experiments to demonstrate the efficiency of our MFCGD and AdaMFCGD algorithms on robust federated learning and distributed meta learning tasks.
In the experiments, we compare our algorithms with the existing algorithms in Table [1](#S1.T1) for solving distributed composition optimization problems.

### 6.1 Robust Federated Learning

### 6.2 Task-Distributed Meta Learning

## 7 Conclusions

In the paper, we proposed a class of faster momentum-based federated compositional gradient descent algorithms (i.e., MFCGD and AdaMFCGD) to solve the nonconvex distributed composition problems. Our adaptive algorithm (i.e., AdaMFCGD) uses a unified adaptive matrix to flexibly incorporate various adaptive learning rates. Moreover, we established a solid convergence analysis framework for our algorithms, and proved that our methods obtain lower sample and communication complexities simultaneously than the existing federated composition optimization methods.

## Appendix A Appendix

In this section, we provide the detailed convergence analysis of our algorithms.

We first introduce some useful notations: $\bar{w}_{t}=\frac{1}{M}\sum_{m=1}^{M}w^{m}_{t}$,
$\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$,

$$ $\displaystyle F(x)=\frac{1}{M}\sum_{m=1}^{M}f^{m}(g^{m}(x)),\quad\nabla F(x)=\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x)\big{)}^{T}\nabla f^{m}(g^{m}(x)).$ $$

Next, we review and provide some useful lemmas.

###### Lemma 3 .

Given $M$ vectors $\{u^{m}\}_{m=1}^{M}$, the following inequalities satisfy: $||u^{m}+u^{j}||^{2}\leq(1+c)||u^{m}||^{2}+(1+\frac{1}{c})||u^{j}||^{2}$ for any $c>0$, and
$||\sum_{m=1}^{M}u^{m}||^{2}\leq M\sum_{m=1}^{M}||u^{m}||^{2}$.

###### Lemma 4 .

Given a finite sequence $\{u^{m}\}_{m=1}^{M}$, and $\bar{u}=\frac{1}{M}\sum_{m=1}^{M}u^{m}$,
the following inequality satisfies $\sum_{m=1}^{M}\|u^{m}-\bar{u}\|^{2}\leq\sum_{m=1}^{M}\|u^{m}\|^{2}$.

Given a $\rho$-strongly convex function $\varphi(x)$, we define a prox-function (Bregman distance) Censor and Lent [], Censor and Zenios []
associated with $\varphi(x)$ as follows:

$$ $\displaystyle D(z,x)=\varphi(z)-\big{[}\varphi(x)+\langle\nabla\varphi(x),z-x\rangle\big{]}.$ (18) $$

Then we define a generalized projection problem as in Ghadimi et al. []:

$$ $\displaystyle x^{+}=\arg\min_{z\in\mathcal{X}}\big{\{}\langle z,w\rangle+\frac{1}{\gamma}D(z,x)+h(z)\big{\}},$ (19) $$

where $\mathcal{X}\subseteq\mathbb{R}^{d}$, $w\in\mathbb{R}^{d}$ and $\gamma>0$.
In the paper, we consider $h(x)=0$. Meanwhile, we also define a generalized projected gradient (a.k.a., gradient mapping):

$$ $\displaystyle\mathcal{G}_{\mathcal{X}}(x,w,\gamma)=\frac{x-x^{+}}{\gamma}.$ (20) $$

###### Lemma 5 .

(Lemma 1 in Ghadimi et al. [])
Let $x^{+}$ be given in ([19](#A1.E19)). Then, for any $x\in\mathcal{X}$, $w\in\mathbb{R}^{d}$ and $\gamma>0$,
we have

$$ $\displaystyle\langle w,\mathcal{G}_{\mathcal{X}}(x,w,\gamma)\rangle\geq\rho\|\mathcal{G}_{\mathcal{X}}(x,w,\gamma)\|^{2}+\frac{1}{\gamma}\big{[}h(x^{+})-h(x)\big{]},$ (21) $$

where $\rho>0$ depends on $\rho$-strongly convex function $\varphi(x)$.

When $h(x)=0$, in the above lemma [5](#Thmlemma5), we have

$$ $\displaystyle\langle w,\mathcal{G}_{\mathcal{X}}(x,w,\gamma)\rangle\geq\rho\|\mathcal{G}_{\mathcal{X}}(x,w,\gamma)\|^{2}.$ (22) $$

###### Lemma 6 .

(Restatement of Lemma 1)
Given the above Assumptions [1](#Thmassumption1)-[2](#Thmassumption2),
the function $F(x)$ is $L$-smooth, i.e., for any $x_{1},x_{2}\in\mathbb{R}^{d}$, we have

$$ $\displaystyle\|\nabla F(x_{1})-\nabla F(x_{2})\|^{2}\leq L^{2}\|x_{1}-x_{2}\|^{2},$ (23) $$

where $L=\sqrt{2C^{2}_{f}L^{2}_{g}+2C^{4}_{g}L^{2}_{f}}$.

###### Proof.

Based on Assumptions [1](#Thmassumption1)-[2](#Thmassumption2), the deterministic functions $f^{m}(y)=\mathbb{E}\big{[}f^{m}(y;\xi^{m})\big{]}$ $g^{m}(x)=\mathbb{E}\big{[}f^{m}(x;\zeta^{m})\big{]}$ and its gradients also satisfy the Lipschitz gradients and bounded gradients.
For example, for any $y_{1},y_{2}\in\mathbb{R}^{n}$

$$ $\displaystyle\big{\|}\nabla f^{m}(y_{1})-\nabla f^{m}(y_{1})\big{\|}$ $\displaystyle=\big{\|}\mathbb{E}\big{[}\nabla f^{m}(y_{1};\xi^{m})-\nabla f^{m}(y_{1};\xi^{m})\big{]}\big{\|}$ $\displaystyle\leq\mathbb{E}\big{\|}\nabla f^{m}(y_{1};\xi^{m})-\nabla f^{m}(y_{1};\xi^{m})\big{\|}\leq L_{f}\|y_{1}-y_{2}\|,$ (24) $$

where the first inequality holds by Jensen’s inequality, and the last inequality holds by Assumption [1](#Thmassumption1).

Since $F(x)=\frac{1}{M}\sum_{m=1}^{M}f^{m}(g^{m}(x))$, we have

$$ $\displaystyle\|\nabla F(x_{1})-\nabla F(x_{2})\|^{2}$ $\displaystyle=\big{\|}\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x_{1})\big{)}^{T}\nabla f^{m}(g^{m}(x_{1}))-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x_{2})\big{)}^{T}\nabla f^{m}(g^{m}(x_{2}))\big{\|}^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\big{\|}\big{(}\nabla g^{m}(x_{1})\big{)}^{T}\nabla f^{m}(g^{m}(x_{1}))-\big{(}\nabla g^{m}(x_{2})\big{)}^{T}\nabla f^{m}(g^{m}(x_{2}))\big{\|}^{2}$ $\displaystyle=\frac{1}{M}\sum_{m=1}^{M}\big{\|}\big{(}\nabla g^{m}(x_{1})\big{)}^{T}\nabla f^{m}(g^{m}(x_{1}))-\big{(}\nabla g^{m}(x_{2})\big{)}^{T}\nabla f^{m}(g^{m}(x_{1}))+\big{(}\nabla g^{m}(x_{2})\big{)}^{T}\nabla f^{m}(g^{m}(x_{1}))$ $\displaystyle\quad-\big{(}\nabla g^{m}(x_{2})\big{)}^{T}\nabla f^{m}(g^{m}(x_{2}))\big{\|}^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}2C^{2}_{f}\big{\|}\nabla g^{m}(x_{1})-\nabla g^{m}(x_{2})\big{\|}^{2}+\frac{1}{M}\sum_{m=1}^{M}2C^{2}_{g}\big{\|}\nabla f^{m}(g^{m}(x_{1}))-\nabla f^{m}(g^{m}(x_{2}))\big{\|}^{2}$ $\displaystyle\leq 2C^{2}_{f}L^{2}_{g}\|x_{1}-x_{2}\|^{2}+2C^{4}_{g}L^{2}_{f}\|x_{1}-x_{2}\|^{2}=\big{(}2C^{2}_{f}L^{2}_{g}+2C^{4}_{g}L^{2}_{f}\big{)}\|x_{1}-x_{2}\|^{2},$ (25) $$

where the second last and the last inequalities hold by Assumptions [1](#Thmassumption1)-[2](#Thmassumption2).

∎

###### Lemma 7 .

(Restatement of Lemma 2)
Assume the gradient estimator $\{\bar{w}_{t}\}_{t=1}^{T}$ generated from Algorithm [1](#alg1), where $w_{t}=\frac{1}{M}\sum_{m=1}^{M}w^{m}_{t}$,
we have

$$ $\displaystyle\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Big{(}2C_{f}^{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+4C_{g}^{2}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4C_{g}^{2}L^{2}_{f}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}.$ (26) $$

###### Proof.

Since $\bar{w}_{t}=\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}$,
we have

$$ $\displaystyle\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|^{2}$ $\displaystyle=\|\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(\bar{x}_{t})\big{)}^{T}\nabla f^{m}(g^{m}(\bar{x}_{t}))\|^{2}$ $\displaystyle=\|\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(\bar{x}_{t})\big{)}^{T}v^{m}_{t}+\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(\bar{x}_{t})\big{)}^{T}v^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(\bar{x}_{t})\big{)}^{T}\nabla f^{m}(g^{m}(\bar{x}_{t}))\|^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}2C^{2}_{f}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{1}{M}\sum_{m=1}^{M}2C^{2}_{g}\|v^{m}_{t}-\nabla f^{m}(g^{m}(\bar{x}_{t}))\|^{2}$ $\displaystyle=\frac{2C^{2}_{f}}{M}\sum_{m=1}^{M}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{2C^{2}_{g}}{M}\sum_{m=1}^{M}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})+\nabla f^{m}(h^{m}_{t})-\nabla f^{m}(g^{m}(\bar{x}_{t}))\|^{2}$ $\displaystyle\leq\frac{2C^{2}_{f}}{M}\sum_{m=1}^{M}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C^{2}_{g}}{M}\sum_{m=1}^{M}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+\frac{4C^{2}_{g}L^{2}_{f}}{M}\sum_{m=1}^{M}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2},$ (27) $$

where the first inequality is due to Assumptions [1](#Thmassumption1)-[2](#Thmassumption2) and the above Lemma [3](#Thmlemma3).

∎

###### Lemma 8 .

Suppose that the sequence $\big{\{}\bar{x}_{t}\big{\}}_{t=1}^{T}$ be generated from Algorithm [1](#alg1), where $\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$.
Let $0<\gamma\leq\frac{\rho}{2L\eta_{t}}$,
then we have

$$ $\displaystyle F(\bar{x}_{t+1})$ $\displaystyle\leq F(\bar{x}_{t})+\frac{1}{M}\sum_{m=1}^{M}\Big{(}\frac{2C_{f}^{2}\eta_{t}\gamma}{\rho}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C_{g}^{2}\eta_{t}\gamma}{\rho}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\qquad+\frac{4C_{g}^{2}L^{2}_{f}\eta_{t}\gamma}{\rho}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}-\frac{\rho}{2\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}.$ (28) $$

###### Proof.

According to the above Lemma [6](#Thmlemma6), the function $F(x)$ is $L$-smooth. Thus we have

$$ $\displaystyle F(\bar{x}_{t+1})$ $\displaystyle\leq F(\bar{x}_{t})+\langle\nabla F(\bar{x}_{t}),\bar{x}_{t+1}-\bar{x}_{t}\rangle+\frac{L}{2}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ (29) $\displaystyle=F(\bar{x}_{t})+\underbrace{\langle\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle}_{=T_{1}}+\underbrace{\langle\nabla F(\bar{x}_{t})-\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle}_{=T_{2}}+\frac{L}{2}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}.$ $$

According to Assumption [5](#Thmassumption5), i.e., $A_{t}\succ\rho I_{d}$ for any $t\geq 1$,
the mirror function $\varphi_{t}(x)=\frac{1}{2}x^{T}A_{t}x$ is $\rho$-strongly convex, then we can define a Bregman distance as in Ghadimi et al. [],

$$ $\displaystyle D_{t}(x,\bar{x}_{t})=\varphi_{t}(x)-\big{[}\varphi_{t}(\bar{x}_{t})+\langle\nabla\varphi_{t}(\bar{x}_{t}),x-\bar{x}_{t}\rangle\big{]}=\frac{1}{2}(x-\bar{x}_{t})^{T}A_{t}(x-\bar{x}_{t}).$ (30) $$

When $t=s_{t}=q\lfloor t/q\rfloor+1$, according to the line 7 of Algorithm [1](#alg1), we have
$\bar{x}_{t+1}=\arg\min_{x\in\mathbb{R}^{d}}\big{\{}\langle\bar{w}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-\bar{x}_{t})^{T}A_{t}(x-\bar{x}_{t})\big{\}}$.
By using Lemma 1 in Ghadimi et al. [] to the problem $\bar{x}_{t+1}=\arg\min_{x\in\mathbb{R}^{d}}\big{\{}\langle\bar{w}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-\bar{x}_{t})^{T}A_{t}(x-\bar{x}_{t})\big{\}}$, we can obtain

$$ $\displaystyle\langle\bar{w}_{t},\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\rangle\geq\rho\|\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\|^{2}.$ (31) $$

When $t\in(s_{t},s_{t}+q)$, according to the line 11 of Algorithm [1](#alg1), we have $x^{m}_{t+1}=\arg\min_{x\in\mathbb{R}^{d}}\big{\{}\langle w^{m}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-x^{m}_{t})^{T}A_{t}(x-x^{m}_{t})\big{\}}$.
Similarly, we have

$$ $\displaystyle\langle w^{m}_{t},\frac{1}{\eta_{t}\gamma}(x^{m}_{t}-x^{m}_{t+1})\rangle\geq\rho\|\frac{1}{\eta_{t}\gamma}(x^{m}_{t}-x^{m}_{t+1})\|^{2}.$ (32) $$

Then we have

$$ $\displaystyle\frac{1}{M}\sum_{m=1}^{M}\langle w^{m}_{t},\frac{1}{\eta_{t}\gamma}(x^{m}_{t}-x^{m}_{t+1})\rangle$ $\displaystyle\geq\rho\frac{1}{M}\sum_{m=1}^{M}\|\frac{1}{\eta_{t}\gamma}(x^{m}_{t}-x^{m}_{t+1})\|^{2}$ $\displaystyle\geq\rho\|\frac{1}{\eta_{t}\gamma}\frac{1}{M}\sum_{m=1}^{M}(x^{m}_{t}-x^{m}_{t+1})\|^{2}=\rho\|\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\|^{2}.$ (33) $$

Thus we have

$$ $\displaystyle\langle w^{m}_{t},\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\rangle\geq\rho\|\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\|^{2}.$ (34) $$

Since $\bar{w}_{t}=\frac{1}{M}\sum_{m=1}^{M}w^{m}_{t}$,
averaging the above inequality ([34](#A1.E34)) from $m=1$ to $M$, we can obtain

$$ $\displaystyle\langle\bar{w}_{t},\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\rangle=\frac{1}{M}\sum_{m=1}^{M}\langle w^{m}_{t},\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\rangle\geq\rho\frac{1}{M}\sum_{m=1}^{M}\|\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\|^{2}=\rho\|\frac{1}{\eta_{t}\gamma}(\bar{x}_{t}-\bar{x}_{t+1})\|^{2}.$ (35) $$

Then we have for any $t\in[s_{t},s_{t}+q)$,

$$ $\displaystyle T_{1}=\langle\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle\leq-\frac{\rho}{\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}.$ (36) $$

Since $s_{t}=q\lfloor t/q\rfloor+1$ and all $t\in[s_{t},s_{t}+q)$, clearly, we have, for all $t\geq 1$

$$ $\displaystyle T_{1}=\langle\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle\leq-\frac{\rho}{\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}.$ (37) $$

Next, consider the bound of the term $T_{2}$, we have

$$ $\displaystyle T_{2}$ $\displaystyle=\langle\nabla F(\bar{x}_{t})-\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle$ $\displaystyle\leq\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|\cdot\|\bar{x}_{t+1}-\bar{x}_{t}\|$ $\displaystyle\leq\frac{\eta_{t}\gamma}{\rho}\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|^{2}+\frac{\rho}{4\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2},$ (38) $$

where the first inequality is due to the Cauchy-Schwarz inequality and the last is due to Young’s inequality.
By combining the above inequalities ([29](#A1.E29)), ([37](#A1.E37)) with ([A](#A1.Ex25)),
we obtain

$$ $\displaystyle F(\bar{x}_{t+1})$ $\displaystyle\leq F(\bar{x}_{t})+\langle\nabla F(\bar{x}_{t})-\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle+\langle\bar{w}_{t},\bar{x}_{t+1}-\bar{x}_{t}\rangle+\frac{L}{2}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ $\displaystyle\leq F(\bar{x}_{t})+\frac{\eta_{t}\gamma}{\rho}\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|^{2}+\frac{\rho}{4\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}-\frac{\rho}{\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}+\frac{L}{2}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ $\displaystyle=F(\bar{x}_{t})+\frac{\eta_{t}\gamma}{\rho}\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|^{2}-\frac{\rho}{2\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}-\big{(}\frac{\rho}{4\eta_{t}\gamma}-\frac{L}{2}\big{)}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ $\displaystyle\leq F(\bar{x}_{t})+\frac{\eta_{t}\gamma}{\rho}\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|^{2}-\frac{\rho}{2\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ $\displaystyle\leq F(\bar{x}_{t})+\frac{1}{M}\sum_{m=1}^{M}\Big{(}\frac{2C_{f}^{2}\eta_{t}\gamma}{\rho}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C_{g}^{2}\eta_{t}\gamma}{\rho}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\qquad+\frac{4C_{g}^{2}L^{2}_{f}\eta_{t}\gamma}{\rho}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}-\frac{\rho}{2\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2},$ (39) $$

where the second last inequality is due to $0<\gamma\leq\frac{\rho}{2L\eta_{t}}$, and the last inequality holds by Lemma [7](#Thmlemma7).

∎

###### Lemma 9 .

Under the above assumptions, and assume the stochastic gradient estimators $\big{\{}h^{m}_{t},u^{m}_{t},v^{m}_{t}\big{\}}_{t=1}^{T}$ be generated from Algorithm [1](#alg1),
we have, for any $m\in[M]$

$$ $\displaystyle\mathbb{E}\|h^{m}_{t+1}-g^{m}(x^{m}_{t+1})\|^{2}$ $\displaystyle\leq(1-\alpha_{t+1})\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle\quad+2C_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2},$ (40) $$

$$ $\displaystyle\mathbb{E}\|u^{m}_{t+1}-\nabla g^{m}(x^{m}_{t+1})\|^{2}$ $\displaystyle\leq(1-\beta_{t+1})\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle\quad+2L_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}.$ (41) $$

$$ $\displaystyle\mathbb{E}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}$ $\displaystyle\leq(1-\varrho_{t+1})\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4L^{2}_{f}C^{2}_{g}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}$ $\displaystyle\quad+2\varrho^{2}_{t+1}\sigma^{2}+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2},$ (42) $$

###### Proof.

Without loss of generality, we only prove the above inequality ([9](#A1.Ex34)), and it is similar to the other inequalities.
Since $v^{m}_{t+1}=\Pi_{C_{f}}\Big{[}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})+(1-\varrho_{t+1})\big{(}v^{m}_{t}-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})\big{)}\Big{]}$,
we have

$$ $\displaystyle\mathbb{E}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}$ $\displaystyle=\mathbb{E}\big{\|}\Pi_{C_{f}}\big{[}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})+(1-\varrho_{t+1})\big{(}v^{m}_{t}-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})\big{)}\big{]}-\Pi_{C_{f}}\big{[}\nabla f^{m}(h^{m}_{t+1})\big{]}\big{\|}^{2}$ $\displaystyle\leq\mathbb{E}\|\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})+(1-\varrho_{t+1})\big{(}v^{m}_{t}-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})\big{)}-\nabla f^{m}(h^{m}_{t+1})\|^{2}$ $\displaystyle=\mathbb{E}\big{\|}(1-\varrho_{t+1})(v^{m}_{t}-\nabla f^{m}(h^{m}_{t}))-\varrho_{t+1}(\nabla f^{m}(h^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1}))$ $\displaystyle\quad+(1-\varrho_{t+1})\big{(}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1})+\nabla f^{m}(h^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle=(1-\varrho_{t+1})^{2}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+\mathbb{E}\big{\|}\varrho_{t+1}(\nabla f^{m}(h^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1}))$ $\displaystyle\quad-(1-\varrho_{t+1})\big{(}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1})+\nabla f^{m}(h^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq(1-\varrho_{t+1})^{2}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+2\varrho^{2}_{t+1}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})\big{\|}^{2}$ $\displaystyle\quad+2(1-\varrho_{t+1})^{2}\big{\|}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1})+\nabla f^{m}(h^{m}_{t})\big{\|}^{2}$ $\displaystyle\leq(1-\varrho_{t+1})^{2}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+2(1-\varrho_{t+1})^{2}\big{\|}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})\big{\|}^{2}$ $\displaystyle\leq(1-\varrho_{t+1})^{2}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+2(1-\varrho_{t+1})^{2}L^{2}_{f}\mathbb{E}\|h^{m}_{t+1}-h^{m}_{t}\|^{2},$ (43) $$

where the third equality holds by the following fact:

$$ $\displaystyle\mathbb{E}_{\xi^{m}_{t+1}}\big{[}\varrho_{t+1}(\nabla f^{m}(h^{m}_{t+1})-\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1}))-(1-\varrho_{t+1})\big{(}\nabla f^{m}(h^{m}_{t+1};\xi^{m}_{t+1})-\nabla f^{m}(h^{m}_{t};\xi^{m}_{t+1})$ $\displaystyle\qquad\quad-\nabla f^{m}(h^{m}_{t+1})+\nabla f^{m}(h^{m}_{t})\big{)}\big{]}=0,$ $$

and
the second last inequality holds by the inequality $\mathbb{E}\|\zeta-\mathbb{E}[\zeta]\|^{2}\leq\mathbb{E}\|\zeta\|^{2}$ and Assumption [3](#Thmassumption3);
the last inequality is due to Assumption [1](#Thmassumption1).

Since $h^{m}_{t+1}=g^{m}(x^{m}_{t+1};\zeta^{m}_{t+1})+(1-\alpha_{t+1})\big{(}h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\big{)}$,
we have

$$ $\displaystyle\mathbb{E}\|h^{m}_{t+1}-h^{m}_{t}\|^{2}$ $\displaystyle=\mathbb{E}\|g^{m}(x^{m}_{t+1};\zeta^{m}_{t+1})-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})-\alpha_{t+1}\big{(}h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\big{)}\|^{2}$ $\displaystyle\leq 2\mathbb{E}\|g^{m}(x^{m}_{t+1};\zeta^{m}_{t+1})-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\|^{2}+2\alpha^{2}_{t+1}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\alpha^{2}_{t+1}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})\|^{2}$ $\displaystyle=2C^{2}_{g}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\alpha^{2}_{t+1}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t};\zeta^{m}_{t+1})+g^{m}(x^{m}_{t})-g^{m}(x^{m}_{t})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+4\alpha^{2}_{t+1}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+4\alpha^{2}_{t+1}\mathbb{E}\|g^{m}(x^{m}_{t};\zeta^{m}_{t+1})+g^{m}(x^{m}_{t})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+4\alpha^{2}_{t+1}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+4\alpha^{2}_{t+1}\sigma^{2},$ (44) $$

where the second inequality holds by Assumption , .

Combining the above inequalities [A](#A1.Ex35) with [A](#A1.Ex47), we have

$$ $\displaystyle\mathbb{E}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}$ $\displaystyle\leq(1-\varrho_{t+1})^{2}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+2(1-\varrho_{t+1})^{2}L^{2}_{f}\mathbb{E}\|h^{m}_{t+1}-h^{m}_{t}\|^{2}$ $\displaystyle\leq(1-\varrho_{t+1})\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+4L^{2}_{f}C^{2}_{g}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}$ $\displaystyle\quad+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2},$ $$

where the last inequality holds by $0<\varrho_{t+1}\leq 1$.

∎

###### Lemma 10 .

Based on the above Assumptions [1](#Thmassumption1)-[2](#Thmassumption2) and [6](#Thmassumption6), we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(h^{j}_{t})\big{\|}^{2}\leq 8L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+4M\delta^{2}_{f}+4ML^{2}_{f}\delta^{2}_{g},$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(x^{j}_{t})\big{\|}^{2}\leq 6L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+3M\delta_{g}^{2}$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}g^{m}(x^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}g^{j}(x^{j}_{t})\big{\|}^{2}\leq 6C^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+3M\delta_{g}^{2}.$ $$

###### Proof.

Consider the term $\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(h^{j}_{t})\big{\|}^{2}$, we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(h^{j}_{t})\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t})-\nabla f^{m}(g^{m}(\bar{x}_{t}))+\nabla f^{m}(g^{m}(\bar{x}_{t}))-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{m}(\bar{x}_{t}))+\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{m}(\bar{x}_{t}))$ $\displaystyle\quad-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{j}(\bar{x}_{t}))+\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{j}(\bar{x}_{t}))-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(h^{j}_{t})\big{\|}^{2}$ $\displaystyle\leq\sum_{m=1}^{M}4\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t})-\nabla f^{m}(g^{m}(\bar{x}_{t}))\big{\|}^{2}+\sum_{m=1}^{M}4\mathbb{E}\big{\|}\nabla f^{m}(g^{m}(\bar{x}_{t}))-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{m}(\bar{x}_{t}))\big{\|}^{2}$ $\displaystyle\quad+\sum_{m=1}^{M}4\mathbb{E}\big{\|}\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{m}(\bar{x}_{t}))-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{j}(\bar{x}_{t}))\big{\|}^{2}+\sum_{m=1}^{M}4\mathbb{E}\big{\|}\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(g^{j}(\bar{x}_{t}))-\frac{1}{M}\sum_{j=1}^{M}\nabla f^{j}(h^{j}_{t})\big{\|}^{2}$ $\displaystyle\leq 4L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+4\sum_{m=1}^{M}\frac{1}{M}\sum_{j=1}^{M}\mathbb{E}\|\nabla f^{m}(g^{m}(\bar{x}_{t}))-\nabla f^{j}(g^{m}(\bar{x}_{t}))\|^{2}$ $\displaystyle\quad+4L^{2}_{f}\sum_{m=1}^{M}\frac{1}{M}\sum_{j=1}^{M}\big{\|}g^{m}(\bar{x}_{t})-g^{j}(\bar{x}_{t})\big{\|}^{2}+4L^{2}_{f}\sum_{j=1}^{M}\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}\big{\|}g^{m}(\bar{x}_{t})-h^{m}_{t}\big{\|}^{2}$ $\displaystyle\leq 8L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+4M\delta^{2}_{f}+4ML^{2}_{f}\delta^{2}_{g},$ (45) $$

where the last inequality holds by Assumption [6](#Thmassumption6).

Next, we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(x^{j}_{t})\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t})-\nabla g^{m}(\bar{x}_{t})+\nabla g^{m}(\bar{x}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(\bar{x}_{t})+\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(\bar{x}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(x^{j}_{t})\big{\|}^{2}$ $\displaystyle\leq\sum_{m=1}^{M}3\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t})-\nabla g^{m}(\bar{x}_{t})\big{\|}^{2}+\sum_{m=1}^{M}3\mathbb{E}\big{\|}\nabla g^{m}(\bar{x}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(\bar{x}_{t})\big{\|}^{2}$ $\displaystyle\quad+\sum_{m=1}^{M}3\mathbb{E}\big{\|}\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(\bar{x}_{t})-\frac{1}{M}\sum_{j=1}^{M}\nabla g^{j}(x^{j}_{t})\big{\|}^{2}$ $\displaystyle\leq 3L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+3\sum_{m=1}^{M}\frac{1}{M}\sum_{j=1}^{M}\mathbb{E}\|\nabla g^{m}(\bar{x}_{t})-\nabla g^{j}(\bar{x}_{t})\|^{2}+3\sum_{m=1}^{M}\frac{1}{M}\sum_{j=1}^{M}\big{\|}\nabla g^{j}(\bar{x}_{t})-\nabla g^{j}(x^{j}_{t})\big{\|}^{2}$ $\displaystyle\leq 6L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+3M\delta_{g}^{2},$ (46) $$

where the last inequality is due to the above Assumption [6](#Thmassumption6).

Similarly, we can obtain

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}g^{m}(x^{m}_{t})-\frac{1}{M}\sum_{j=1}^{M}g^{j}(x^{j}_{t})\big{\|}^{2}\leq 6C^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+3M\delta_{g}^{2}.$ (47) $$

∎

###### Lemma 11 .

Suppose the iterates $\{x^{m}_{t}\}_{t=1}^{T}$, for all $m\in[M]$ generated from Algorithm [1](#alg1) satisfy:

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}\leq(q-1)\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2},$ (48) $$

where $\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$, $d_{t}^{m}=\frac{x_{t}^{m}-x_{t+1}^{m}}{\gamma\eta_{t}}$ and $\bar{d}_{t}=\frac{\bar{x}_{t}-\bar{x}_{t+1}}{\eta_{t}\gamma}$.

###### Proof.

According to the lines 7 and 11 of Algorithm [1](#alg1), we have

$$ $\displaystyle x_{t+1}^{m}=x^{m}_{t}-\gamma\eta_{t}A^{-1}_{t}w^{m}_{t}=\arg\min_{x\in\mathbb{R}^{d}}\big{\{}\langle w^{m}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-x^{m}_{t})^{T}A_{t}(x-x^{m}_{t})\big{\}},$ $\displaystyle\bar{x}_{t+1}=\bar{x}_{t}-\gamma\eta_{t}A^{-1}_{t}\bar{w}_{t}=\arg\min_{x\in\mathbb{R}^{d}}\big{\{}\langle\bar{w}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-\bar{x}_{t})^{T}A_{t}(x-\bar{x}_{t})\big{\}},$ $$

and then we define the gradient mappings as in the above ([20](#A1.E20)): $d_{t}^{m}=\frac{x_{t}^{m}-x_{t+1}^{m}}{\gamma\eta_{t}}=A_{t}^{-1}w^{m}_{t}$ and $\bar{d}_{t}=\frac{\bar{x}_{t}-\bar{x}_{t+1}}{\eta_{t}\gamma}=A_{t}^{-1}\bar{w}_{t}=\frac{1}{M}\sum_{m=1}^{M}d_{t}^{m}$ for any
$m\in[M]$ and $t\geq 1$.

From the line 7 of Algorithm [1](#alg1), when $t=s_{t}=q\lfloor t/q\rfloor+1$, we have $x^{m}_{t}=\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$ for any $m\in[M]$, so the about inequality in the lemma holds trivially.

When $t\in(s_{t},s_{t}+q)$, we have

$$ $\displaystyle x^{m}_{t}=x^{m}_{s_{t}}-\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}d^{m}_{l},\quad\text{and}\quad\bar{x}_{t}=\bar{x}_{s_{t}}-\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}\bar{d}_{l}.$ $$

Thus we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\Big{\|}x^{m}_{s_{t}}-\bar{x}_{s_{t}}-\Big{(}\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}d^{m}_{l}-\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}\bar{d}_{l}\Big{)}\Big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\Big{\|}\Big{(}\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}d^{m}_{l}-\sum_{l=s_{t}}^{t-1}\gamma\eta_{l}\bar{d}_{l}\Big{)}\Big{\|}^{2}\leq(q-1)\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2},$ $$

where the above inequality is due to $t-s_{t}\leq q-1$.
∎

###### Lemma 12 .

Let $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, $L^{2}_{fg}=L^{2}_{f}C^{2}_{g}+L^{2}_{g}$ and $\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$ for all $t\geq 0$. Further let $\alpha_{t+1}=c_{1}\eta^{2}_{t}$, $\beta_{t+1}=c_{2}\eta^{2}_{t}$ and
$\varrho_{t+1}=c_{3}\eta^{2}_{t}$, $c_{1},c_{2},c_{3}>0$ and $c^{2}_{1}+c^{2}_{2}\leq\frac{(24)^{4}q^{2}\gamma^{4}L^{4}_{fg}C^{4}_{fg}}{9\rho^{4}}$.
Set $s_{t}=q\lfloor t/q\rfloor+1$ and $t\in[s_{t},s_{t}+q-1]$, we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle\leq\frac{6M}{5}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{3M\hat{\delta}^{2}}{5\gamma^{2}L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t},$ (49) $$

where $\hat{\delta}^{2}=2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}$.

###### Proof.

According to the lines 7 and 11 of Algorithm [1](#alg1), we have

$$ $\displaystyle x_{t+1}^{m}=\arg\min_{x\in\mathbb{R}^{d}}\Big{\{}\langle w^{m}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-x^{m}_{t})^{T}A_{t}(x-x^{m}_{t})\Big{\}},$ $\displaystyle\bar{x}_{t+1}=\arg\min_{x\in\mathbb{R}^{d}}\Big{\{}\langle\bar{w}_{t},x\rangle+\frac{1}{2\eta_{t}\gamma}(x-\bar{x}_{t})^{T}A_{t}(x-\bar{x}_{t})\Big{\}},$ $$

and then we define the gradient mappings as in the above ([20](#A1.E20)): $d_{t}^{m}=\frac{x_{t}^{m}-x_{t+1}^{m}}{\gamma\eta_{t}}=A_{t}^{-1}w^{m}_{t}$ and $\bar{d}_{t}=\frac{\bar{x}_{t}-\bar{x}_{t+1}}{\eta_{t}\gamma}=A_{t}^{-1}\bar{w}_{t}=\frac{1}{M}\sum_{m=1}^{M}d_{t}^{m}$ for any
$m\in[M]$ and $t\geq 1$.
Then we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\|A_{t}^{-1}(w^{m}_{t}-\bar{w}_{t})\|^{2}\leq\frac{1}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|w^{m}_{t}-\bar{w}_{t}\|^{2}$ (50) $\displaystyle=\frac{1}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|(u^{m}_{t})^{T}-(u^{m}_{t})^{T}\bar{v}_{t}+(u^{m}_{t})^{T}\bar{v}_{t}-(\bar{u}_{t})^{T}\bar{v}_{t}+(\bar{u}_{t})^{T}\bar{v}_{t}-\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$ $\displaystyle\leq\frac{1}{\rho^{2}}\sum_{m=1}^{M}\Big{(}3C^{2}_{g}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}+3C^{2}_{f}\mathbb{E}\|u^{m}_{t}-\bar{u}_{t}\|^{2}+3\|(\bar{u}_{t})^{T}\bar{v}_{t}-\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}\|^{2}\Big{)},$ $$

where the first inequality holds by Assumption [5](#Thmassumption5), i.e., $A_{t}\succeq\rho I_{d}$ for all $t\geq 1$,
and the last inequality holds by $\|u^{m}_{t}\|^{2}\leq C^{2}_{g}$ and $\|\bar{v}_{t}\|^{2}\leq C^{2}_{f}$.
Consider the term $\|(\bar{u}_{t})^{T}\bar{v}_{t}-\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$, we have

$$ $\displaystyle\|(\bar{u}_{t})^{T}\bar{v}_{t}-\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$ $\displaystyle=\|(\bar{u}_{t})^{T}\bar{v}_{t}-\frac{1}{M}\sum_{m=1}^{M}(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\|(\bar{u}_{t})^{T}\bar{v}_{t}-(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$ $\displaystyle=\frac{1}{M}\sum_{m=1}^{M}\|(\bar{u}_{t})^{T}\bar{v}_{t}-(\bar{u}_{t})^{T}v^{m}_{t}+(\bar{u}_{t})^{T}v^{m}_{t}-(u^{m}_{t})^{T}v^{m}_{t}\|^{2}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Big{(}2C^{2}_{g}\|v^{m}_{t}-\bar{v}_{t}\|^{2}+2C^{2}_{f}\|u^{m}_{t}-\bar{u}_{t}\|^{2}\Big{)}.$ (51) $$

By combining the above inequalities ([50](#A1.E50)) and ([A](#A1.Ex81)), we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}\leq\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t}-\bar{u}_{t}\|^{2}.$ (52) $$

Let $t=s_{t}=q\lfloor t/q\rfloor+1$. When $t=s_{t}$, we have $v^{m}_{t}=\bar{v}_{t}$ and $u^{m}_{t}=\bar{u}_{t}$ for any $m\in[M]$, so we have $\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}=0$ and $\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t}-\bar{u}_{t}\|^{2}=0$.
According to the above inequality ([52](#A1.E52)), when $t=s_{t}$, we have $\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}=0$. Clearly, the about inequality ([12](#A1.Ex76)) in the lemma holds trivially.

When $t\in(s_{t},s_{t}+q)$, we first consider the term $\sum_{m=1}^{M}\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}$ as follows:

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}$ (53) $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}v^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}v^{m}_{t}\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\Pi_{C_{f}}\big{[}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})+(1-\varrho_{t})\big{(}v^{m}_{t-1}-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{]}-\frac{1}{M}\sum_{m=1}^{M}\Pi_{C_{f}}\big{[}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})$ $\displaystyle\qquad+(1-\varrho_{t})\big{(}v^{m}_{t-1}-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{]}\big{\|}^{2}$ $\displaystyle\leq\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})+(1-\varrho_{t})\big{(}v^{m}_{t-1}-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}-\frac{1}{M}\sum_{m=1}^{M}\Big{(}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})$ $\displaystyle\qquad+(1-\varrho_{t})\big{(}v^{m}_{t-1}-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\Big{)}\big{\|}^{2}$ $\displaystyle\leq(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})$ $\displaystyle\quad-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-(1-\varrho_{t})\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{\|}^{2}.$ $$

Then, we consider the last term of ([53](#A1.E53)):

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-(1-\varrho_{t})\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}$ $\displaystyle\quad+\varrho_{t}\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\|^{2}+2\varrho^{2}_{t}\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{\|}^{2}$ $\displaystyle\leq 2L^{2}_{f}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-h^{m}_{t-1}\|^{2}+2\varrho^{2}_{t}\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{\|}^{2},$ (54) $$

where the second last inequality is due to Young inequality and the above Lemma [4](#Thmlemma4).

Consider the term $\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{\|}^{2}$, we have

$$ $\displaystyle\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1})\big{)}$ $\displaystyle\quad\quad+\nabla f^{m}(h^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1})\big{)}\big{\|}$ $\displaystyle\quad\quad+2\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\nabla f^{m}(h^{m}_{t-1})\big{\|}^{2}+2\sum_{m=1}^{M}\big{\|}\nabla f^{m}(h^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2M\sigma^{2}+16L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+8M\delta^{2}_{f}+8ML^{2}_{f}\delta^{2}_{g},$ (55) $$

where the last inequality holds by the above Lemma [10](#Thmlemma10).

Since $h^{m}_{t}=g^{m}(x^{m}_{t};\zeta^{m}_{t})+(1-\alpha_{t})\big{(}h^{m}_{t-1}-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}$,
we have

$$ $\displaystyle\mathbb{E}\|h^{m}_{t}-h^{m}_{t-1}\|^{2}$ $\displaystyle=\mathbb{E}\|g^{m}(x^{m}_{t};\zeta^{m}_{t})-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\alpha_{t}\big{(}h^{m}_{t-1}-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\|^{2}$ $\displaystyle\leq 2\mathbb{E}\|g^{m}(x^{m}_{t};\zeta^{m}_{t})-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\|^{2}+2\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+2\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\|^{2}$ $\displaystyle=2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+2\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(x^{m}_{t-1};\zeta^{m}_{t})+g^{m}(x^{m}_{t-1})-g^{m}(x^{m}_{t-1})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+4\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(x^{m}_{t-1})\|^{2}+4\alpha^{2}_{t}\mathbb{E}\|g^{m}(x^{m}_{t-1};\zeta^{m}_{t})+g^{m}(x^{m}_{t-1})\|^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+4\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(x^{m}_{t-1})\|^{2}+4\alpha^{2}_{t}\sigma^{2}$ $\displaystyle=2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+4\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})+g^{m}(\bar{x}_{t-1})-g^{m}(x^{m}_{t-1})\|^{2}+4\alpha^{2}_{t}\sigma^{2}$ $\displaystyle\leq 2C^{2}_{g}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+8\alpha^{2}_{t}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+8\alpha^{2}_{t}C^{2}_{g}\|\bar{x}_{t-1}-x^{m}_{t-1}\|^{2}+4\alpha^{2}_{t}\sigma^{2},$ (56) $$

where the second inequality holds by Assumption [3](#Thmassumption3).

By combining the above inequalities ([53](#A1.E53)), ([A](#A1.Ex91)), ([A](#A1.Ex95)) and ([A](#A1.Ex101)), we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}$ (57) $\displaystyle\leq(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})$ $\displaystyle\quad-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t};\xi^{m}_{t})-(1-\varrho_{t})\big{(}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla f^{m}(h^{m}_{t-1};\xi^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\bigg{(}4L^{2}_{f}C^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+16\alpha^{2}_{t}L^{2}_{f}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}$ $\displaystyle\quad+16\alpha^{2}_{t}L^{2}_{f}C^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|\bar{x}_{t-1}-x^{m}_{t-1}\|^{2}+8ML^{2}_{f}\alpha^{2}_{t}\sigma^{2}$ $\displaystyle\quad+4M\varrho^{2}_{t}\sigma^{2}+32\varrho^{2}_{t}L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+16M\varrho^{2}_{t}\delta^{2}_{f}+16ML^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}\bigg{)}$ $\displaystyle\leq(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\bigg{(}8L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t-1}-\bar{d}_{t-1}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+16(q-1)L^{2}_{f}C^{2}_{g}\alpha^{2}_{t}\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2}+8ML^{2}_{f}\alpha^{2}_{t}\sigma^{2}$ $\displaystyle\quad+4M\varrho^{2}_{t}\sigma^{2}+32(\varrho^{2}_{t}+\alpha^{2}_{t})L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+16M\varrho^{2}_{t}\delta^{2}_{f}+16ML^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}\bigg{)}$ $\displaystyle\leq(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Bigg{(}\frac{72L^{2}_{f}C^{4}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1}\|^{2}$ $\displaystyle\quad+\frac{72C^{2}_{f}L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+16(q-1)L^{2}_{f}C^{2}_{g}\alpha^{2}_{t}\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\Big{(}\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+32(\varrho^{2}_{t}+\alpha^{2}_{t})L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+8ML^{2}_{f}\alpha^{2}_{t}\sigma^{2}+4M\varrho^{2}_{t}\sigma^{2}+16M\varrho^{2}_{t}\delta^{2}_{f}+16ML^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}\Bigg{)},$ (58) $$

where the second last inequality holds by the above Lemma [11](#Thmlemma11) and the above inequality ([52](#A1.E52)), and the last inequality holds by
$d^{m}_{t-1}=\frac{x^{m}_{t}-x^{m}_{t-1}}{\eta_{t}\gamma}$, and the above inequality ([52](#A1.E52)).

Next, we consider the term $\sum_{m=1}^{M}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}$ as follows:

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}$ (59) $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}u^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}u^{m}_{t}\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\Pi_{C_{g}}\big{[}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})+(1-\beta_{t})\big{(}u^{m}_{t-1}-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{]}-\frac{1}{M}\sum_{m=1}^{M}\Pi_{C_{g}}\big{[}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})$ $\displaystyle\qquad+(1-\beta_{t})\big{(}u^{m}_{t-1}-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{]}\big{\|}^{2}$ $\displaystyle\leq\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})+(1-\beta_{t})\big{(}u^{m}_{t-1}-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}-\frac{1}{M}\sum_{m=1}^{M}\Big{(}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})$ $\displaystyle\qquad+(1-\beta_{t})\big{(}u^{m}_{t-1}-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\Big{)}\big{\|}^{2}$ $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})$ $\displaystyle\quad-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-(1-\beta_{t})\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{\|}^{2}.$ (60) $$

Then, we consider the last term of ([59](#A1.E59)):

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-(1-\beta_{t})\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}$ $\displaystyle\quad+\beta_{t}\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\|^{2}+2\beta^{2}_{t}\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{\|}^{2}$ $\displaystyle\leq 2L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}+2\beta^{2}_{t}\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{\|}^{2},$ (61) $$

where the second last inequality is due to Young inequality and the above Lemma [4](#Thmlemma4).

Consider the term $\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{\|}^{2}$, we have

$$ $\displaystyle\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{\|}^{2}$ $\displaystyle=\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1})\big{)}$ $\displaystyle\quad\quad+\nabla g^{m}(x^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1})\big{)}\big{\|}$ $\displaystyle\quad\quad+2\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\nabla g^{m}(x^{m}_{t-1})\big{\|}+2\sum_{m=1}^{M}\big{\|}\nabla g^{m}(x^{m}_{t-1})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1})\big{\|}^{2}$ $\displaystyle\leq 2M\sigma^{2}+12L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t-1}-\bar{x}_{t-1}\|^{2}+6M\delta_{g}^{2},$ (62) $$

where the last inequality holds by the above Lemma [10](#Thmlemma10).

By combining the above inequalities ([59](#A1.E59)), ([A](#A1.Ex126)) and ([A](#A1.Ex130)), we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}$ (63) $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\sum_{m=1}^{M}\mathbb{E}\big{\|}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})$ $\displaystyle\quad-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t};\zeta^{m}_{t})-(1-\beta_{t})\big{(}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla g^{m}(x^{m}_{t-1};\zeta^{m}_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Big{(}2L^{2}_{g}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t}-x^{m}_{t-1}\|^{2}$ $\displaystyle\quad+4M\sigma^{2}\beta^{2}_{t}+24L^{2}_{g}\beta^{2}_{t}\sum_{m=1}^{M}\mathbb{E}\|x^{m}_{t-1}-\bar{x}_{t-1}\|^{2}+12M\delta_{g}^{2}\beta^{2}_{t}\Big{)}$ $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Bigg{(}4L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t-1}-\bar{d}_{t-1}\|^{2}+4L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+4M\sigma^{2}\beta^{2}_{t}+24(q-1)L^{2}_{g}\beta^{2}_{t}\sum_{l=s_{t}}^{t-2}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2}+12M\delta_{g}^{2}\beta^{2}_{t}\Bigg{)}$ $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Bigg{(}\frac{36C^{2}_{g}L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1}\|^{2}$ $\displaystyle\quad+\frac{36C^{2}_{f}L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1}\|^{2}+4L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}+4M\sigma^{2}\beta^{2}_{t}+12M\delta_{g}^{2}\beta^{2}_{t}$ $\displaystyle\quad+24(q-1)L^{2}_{g}\beta^{2}_{t}\sum_{l=s_{t}}^{t-2}\gamma^{2}\eta_{l}^{2}\Big{(}\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}\Bigg{)},$ (64) $$

where the last inequality holds by the above inequality ([52](#A1.E52)).

By summing the above inequalities ([57](#A1.E57)) and ([63](#A1.E63)), we have

$$ $\displaystyle\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ (65) $\displaystyle\leq(1+\nu)(1-\beta_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Bigg{(}\frac{36C^{2}_{g}L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1}\|^{2}$ $\displaystyle\quad+\frac{36C^{2}_{f}L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1}\|^{2}+4L^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}+4M\sigma^{2}\beta^{2}_{t}+12M\delta_{g}^{2}\beta^{2}_{t}$ $\displaystyle\quad+24(q-1)L^{2}_{g}\beta^{2}_{t}\sum_{l=s_{t}}^{t-2}\gamma^{2}\eta_{l}^{2}\Big{(}\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}\Bigg{)}$ $\displaystyle\quad+(1+\nu)(1-\varrho_{t})^{2}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Bigg{(}\frac{72L^{2}_{f}C^{4}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t-1}-\bar{v}_{t-1}\|^{2}$ $\displaystyle\quad+\frac{72C^{2}_{f}L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t-1}-\bar{u}_{t-1}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+16(q-1)L^{2}_{f}C^{2}_{g}\alpha^{2}_{t}\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\Big{(}\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+32(\varrho^{2}_{t}+\alpha^{2}_{t})L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+8ML^{2}_{f}\alpha^{2}_{t}\sigma^{2}+4M\varrho^{2}_{t}\sigma^{2}+16M\varrho^{2}_{t}\delta^{2}_{f}+16ML^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}\Bigg{)}$ $\displaystyle\leq\max\Big{(}(1+\nu)(1-\beta_{t})^{2}+(1+\frac{1}{\nu})\frac{72C^{2}_{f}(L^{2}_{f}C^{2}_{g}+L^{2}_{g})\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}},(1+\nu)(1-\varrho_{t})^{2}+(1+\frac{1}{\nu})\frac{72C^{2}_{g}(C^{2}_{g}L^{2}_{f}+L^{2}_{g})\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\Big{)}$ $\displaystyle\quad\cdot\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t-1}-\bar{u}_{t-1}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t-1}-\bar{v}_{t-1}\big{\|}^{2}\big{)}+8(1+\frac{1}{\nu})(L^{2}_{f}C^{2}_{g}+L^{2}_{g})\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+24(1+\frac{1}{\nu})(q-1)\big{(}L^{2}_{f}C^{2}_{g}\alpha^{2}_{t}+L^{2}_{g}\beta^{2}_{t}\big{)}\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\Big{(}\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+32(1+\frac{1}{\nu})(\varrho^{2}_{t}+\alpha^{2}_{t})L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}+(1+\frac{1}{\nu})\Big{(}8ML^{2}_{f}\alpha^{2}_{t}\sigma^{2}+4M\varrho^{2}_{t}\sigma^{2}+16M\varrho^{2}_{t}\delta^{2}_{f}$ $\displaystyle\quad+16ML^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}+4M\sigma^{2}\beta^{2}_{t}+12M\delta_{g}^{2}\beta^{2}_{t}\Big{)}.$ (66) $$

Let $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, $L^{2}_{fg}=L^{2}_{f}C^{2}_{g}+L^{2}_{g}$, $\nu=\frac{1}{q}$ and $\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$ for all $t\geq 0$.
Since $\beta_{t}\in(0,1)$ for all $t\geq 0$, we have

$$ $\displaystyle(1+\nu)(1-\beta_{t})^{2}+(1+\frac{1}{\nu})\frac{72C^{2}_{f}(L^{2}_{f}C^{2}_{g}+L^{2}_{g})\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}$ $\displaystyle\leq 1+\frac{1}{q}+(1+q)\frac{72C^{2}_{f}(L^{2}_{f}C^{2}_{g}+L^{2}_{g})\gamma^{2}}{\rho^{2}}\frac{\rho^{2}}{576\gamma^{2}q^{2}L^{2}_{fg}C^{2}_{fg}}$ $\displaystyle\leq 1+\frac{1}{q}+\frac{1+q}{8q^{2}}\leq 1+\frac{5}{4q}.$ (67) $$

Similarly, since $\varrho_{t}\in(0,1)$ for all $t\geq 0$, we have $(1+\nu)(1-\varrho_{t})^{2}+(1+\frac{1}{\nu})\frac{72C^{2}_{g}(C^{2}_{g}L^{2}_{f}+L^{2}_{g})\eta^{2}_{t-1}\gamma^{2}}{\rho^{2}}\leq 1+\frac{5}{4q}$.
Based on the above inequality ([65](#A1.E65)) and the parameters, then we have

$$ $\displaystyle\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ (68) $\displaystyle\leq\big{(}1+\frac{5}{4q}\big{)}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t-1}-\bar{u}_{t-1}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t-1}-\bar{v}_{t-1}\big{\|}^{2}\big{)}+8(q+1)L^{2}_{fg}\eta^{2}_{t-1}\gamma^{2}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+216(q^{2}-1)\frac{C^{2}_{fg}L^{2}_{fg}\gamma^{2}}{\rho^{2}}\big{(}\alpha^{2}_{t}+\beta^{2}_{t}\big{)}\sum_{l=s_{t}}^{t-1}\eta_{l}^{2}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+32(1+q)(\varrho^{2}_{t}+\alpha^{2}_{t})L_{f}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}$ $\displaystyle\quad+4M(q+1)\Big{(}2L^{2}_{f}\alpha^{2}_{t}\sigma^{2}+\varrho^{2}_{t}\sigma^{2}+4\varrho^{2}_{t}\delta^{2}_{f}+4L^{2}_{f}\varrho^{2}_{t}\delta^{2}_{g}+\sigma^{2}\beta^{2}_{t}+3\delta_{g}^{2}\beta^{2}_{t}\Big{)}$ $\displaystyle\leq\big{(}1+\frac{5}{4q}\big{)}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t-1}-\bar{u}_{t-1}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t-1}-\bar{v}_{t-1}\big{\|}^{2}\big{)}+\frac{\rho^{2}}{36qC^{2}_{fg}}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{t-1}\|^{2}$ $\displaystyle\quad+\frac{3(c^{2}_{1}+c^{2}_{2})}{8}\eta^{2}_{t-1}\sum_{l=s_{t}}^{t-2}\eta_{l}^{2}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{9q\gamma^{2}C^{2}_{fg}C^{2}_{g}}\eta^{2}_{t-1}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t-1}-g^{m}(\bar{x}_{t-1})\|^{2}$ $\displaystyle\quad+\frac{M\rho}{3\gamma L_{fg}C_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\eta^{3}_{t-1},$ (69) $$

where the first inequality holds by the above inequality ([59](#A1.E59)) and $\nu=\frac{1}{q}$, and
the last inequality holds by $\alpha_{t}=c_{1}\eta^{2}_{t-1}$, $\beta_{t}=c_{2}\eta^{2}_{t-1}$, $\varrho_{t}=c_{3}\eta^{2}_{t-1}$ and
$\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$ for all $t\geq 0$, and $\frac{L^{2}_{f}}{L^{2}_{fg}}\leq\frac{1}{C^{2}_{g}}$.

According to the above inequality ([68](#A1.E68)), we have

$$ $\displaystyle\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ $\displaystyle\leq\frac{\rho^{2}}{36qC^{2}_{fg}}\sum_{s=s_{t}}^{t-1}\big{(}1+\frac{5}{4q}\big{)}^{t-1-s}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{s}\|^{2}$ $\displaystyle\quad+\frac{3(c^{2}_{1}+c^{2}_{2})}{8}\sum_{s=s_{t}}^{t-1}\big{(}1+\frac{5}{4q}\big{)}^{t-1-s}\eta^{2}_{s}\sum_{l=s_{t}}^{s-2}\eta_{l}^{2}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{9q\gamma^{2}C^{2}_{fg}C^{2}_{g}}\sum_{s=s_{t}}^{t-1}\big{(}1+\frac{5}{4q}\big{)}^{t-1-s}\eta_{s}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{s-1}-g^{m}(\bar{x}_{s-1})\|^{2}$ $\displaystyle\quad+\frac{M\rho}{3\gamma L_{fg}C_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{s=s_{t}}^{t-1}\big{(}1+\frac{5}{4q}\big{)}^{t-1-s}\eta^{3}_{s}$ $\displaystyle\leq\frac{\rho^{2}}{9qC^{2}_{fg}}\sum_{s=s_{t}}^{t-1}\sum_{m=1}^{M}\mathbb{E}\|\bar{d}_{s}\|^{2}+\frac{3(c^{2}_{1}+c^{2}_{2})}{2}\sum_{s=s_{t}}^{t-1}\eta^{2}_{s}\sum_{l=s_{t}}^{s-2}\eta_{l}^{2}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{l}-\bar{v}_{l}\|^{2}+\mathbb{E}\|u^{m}_{l}-\bar{u}_{l}\|^{2}\Big{)}$ $\displaystyle\quad+\frac{4\rho^{2}(c_{1}^{2}+c_{3}^{2})}{9q\gamma^{2}C^{2}_{fg}C^{2}_{g}}\sum_{s=s_{t}}^{t-1}\eta_{s}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{s-1}-g^{m}(\bar{x}_{s-1})\|^{2}$ $\displaystyle\quad+\frac{4M\rho}{3\gamma L_{fg}C_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{s=s_{t}}^{t-1}\eta^{3}_{s}$ $\displaystyle\leq\frac{M\rho^{2}}{9qC^{2}_{fg}}\sum_{s=s_{t}}^{t-1}\mathbb{E}\|\bar{d}_{s}\|^{2}+\frac{\rho^{2}(c^{2}_{1}+c^{2}_{2})}{24*16\gamma^{2}qL^{2}_{fg}C^{2}_{fg}}\sum_{s=s_{t}}^{t-1}\eta^{2}_{s}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{s}-\bar{v}_{s}\|^{2}+\mathbb{E}\|u^{m}_{s}-\bar{u}_{s}\|^{2}\Big{)}$ $\displaystyle\quad+\frac{4\rho^{2}(c_{1}^{2}+c_{3}^{2})}{9q\gamma^{2}C^{2}_{fg}C^{2}_{g}}\sum_{s=s_{t}}^{t-1}\eta_{s}^{2}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{s-1}-g^{m}(\bar{x}_{s-1})\|^{2}$ $\displaystyle\quad+\frac{4M\rho}{3\gamma L_{fg}C_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{s=s_{t}}^{t-1}\eta^{3}_{s},$ (70) $$

where the second inequality holds by $\big{(}1+\frac{5}{4q}\big{)}^{t-1-s}\leq\big{(}1+\frac{5}{4q}\big{)}^{q}\leq e^{5/4}\leq 4$
and the last inequality holds by $\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$ for all $t\geq 0$.

By multiplying both sides of ([A](#A1.Ex163)) by $\eta_{t}$ and summing over $t=s_{t}$ to $s_{t}+q-1$, we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ $\displaystyle\leq\frac{M\rho^{2}}{9C^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{4}(c^{2}_{1}+c^{2}_{2})}{24^{3}*16\gamma^{4}q^{2}L^{4}_{fg}C^{4}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\Big{(}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}+\mathbb{E}\|u^{m}_{t}-\bar{u}_{t}\|^{2}\Big{)}$ $\displaystyle\quad+\frac{\rho^{4}(c_{1}^{2}+c_{3}^{2})}{24*54q^{2}\gamma^{4}C^{4}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}$ $\displaystyle\quad+\frac{M\rho^{2}}{18\gamma^{2}L^{2}_{fg}C^{2}_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t},$ (71) $$

Given $c^{2}_{1}+c^{2}_{2}\leq\frac{(24)^{4}q^{2}\gamma^{4}L^{4}_{fg}C^{4}_{fg}}{9\rho^{4}}$, we have
$\frac{60}{72}\leq 1-\frac{\rho^{4}(c^{2}_{1}+c^{2}_{2})}{24^{3}*16\gamma^{4}q^{2}L^{4}_{fg}C^{4}_{fg}}$,
we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ $\displaystyle\leq\frac{2M\rho^{2}}{15C^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{4}(c_{1}^{2}+c_{3}^{2})}{1080q^{2}\gamma^{4}C^{4}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}$ $\displaystyle\quad+\frac{M\rho^{2}}{15\gamma^{2}L^{2}_{fg}C^{2}_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}.$ (72) $$

According to the above inequality ([52](#A1.E52)) and $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, we have

$$ $\displaystyle\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}\leq\frac{9C^{2}_{g}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|v^{m}_{t}-\bar{v}_{t}\|^{2}+\frac{9C^{2}_{f}}{\rho^{2}}\sum_{m=1}^{M}\mathbb{E}\|u^{m}_{t}-\bar{u}_{t}\|^{2}\leq\frac{9C^{2}_{fg}}{\rho^{2}}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}.$ (73) $$

Thus we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle\leq\frac{9C^{2}_{fg}}{\rho^{2}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\big{(}\mathbb{E}\big{\|}u^{m}_{t}-\bar{u}_{t}\big{\|}^{2}+\mathbb{E}\big{\|}v^{m}_{t}-\bar{v}_{t}\big{\|}^{2}\big{)}$ $\displaystyle\leq\frac{6M}{5}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}$ $\displaystyle\quad+\frac{3M}{5\gamma^{2}L^{2}_{fg}}\Big{(}2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}\Big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}.$ (74) $$

∎

###### Theorem 3 .

(Restatement of Theorem 1)
Assume the sequence $\{\bar{x}_{t}\}_{t=1}^{T}$ be generated from AdaMFCGD algorithm.
Under the above Assumptions, and let $\eta_{t}=\frac{k}{(n+t)^{1/3}}$ for all $t\geq 0$, $\alpha_{t+1}=c_{1}\eta_{t}^{2}$, $\beta_{t+1}=c_{2}\eta_{t}^{2}$, $\varrho_{t+1}=c_{3}\eta_{t}^{2}$, $n\geq\max\big{(}2,k^{3},(c_{1}k)^{3},(c_{2}k)^{3},(c_{3}k)^{3},\frac{(24k\gamma qL_{fg}C_{fg})^{3}}{\rho^{3}}\big{)}$, $k>0$,
$c_{1}\geq\frac{2}{3k^{3}}+B$, $c_{2}\geq\frac{2}{3k^{3}}+5C^{2}_{f}$, $c^{2}_{1}+c^{2}_{2}\leq\frac{(24)^{4}q^{2}\gamma^{4}L^{4}_{fg}C^{4}_{fg}}{9\rho^{4}}$, $c_{3}\geq\frac{2}{3k^{3}}+5C^{2}_{g}$, $\frac{\rho(c^{2}_{1}+c^{2}_{3})^{1/4}}{12\sqrt{5q}L_{fg}C_{fg}}\leq\gamma\leq\min\Big{(}\frac{3\rho qL_{fg}C_{fg}}{4(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})},\frac{n^{1/3}\rho}{2Lk}\Big{)}$, $B\geq 20C_{g}^{2}L^{2}_{f}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{216q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}+\frac{\Theta\rho^{2}(c_{1}^{2}+c_{3}^{2})}{30q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}$, $\Theta=\Big{(}5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}+\frac{\gamma\rho}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}$ and $\Theta+\frac{BC^{2}_{g}\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\leq\frac{5\rho^{2}}{48}$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\Big{(}\frac{\sqrt{2G}n^{1/6}}{T^{1/2}}+\frac{\sqrt{2G}}{T^{1/3}}\Big{)}\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}},$ (75) $$

where $C^{2}_{fg}=\max(C^{2}_{f},C^{2}_{g})$, $L^{2}_{fg}=L^{2}_{f}C^{2}_{g}+L^{2}_{g}$, $G=\frac{4(F(\bar{x}_{1})-F^{*})}{k\rho\gamma}+\frac{12n^{1/3}\sigma^{2}}{qk^{2}\rho^{2}}+4k^{2}\Big{(}\frac{\hat{\delta}^{2}}{4\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\rho\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)$ and $\hat{\delta}^{2}=2c_{1}^{2}L^{2}_{f}\sigma^{2}+c_{3}^{2}\sigma^{2}+4c_{3}^{2}\delta^{2}_{f}+4c_{3}^{2}L^{2}_{f}\delta^{2}_{g}+c^{2}_{2}\sigma^{2}+3c^{2}_{2}\delta_{g}^{2}$.

###### Proof.

Since $\eta_{t}=\frac{k}{(n+t)^{1/3}}$ on $t$ is decreasing and $n\geq k^{3}$, we have $\eta_{t}\leq\eta_{0}=\frac{k}{n^{1/3}}\leq 1$ and $\gamma\leq\frac{n^{1/3}\rho}{2Lk}\leq\frac{\rho}{2L\eta_{0}}\leq\frac{\rho}{2L\eta_{t}}$ for any $t\geq 0$. Since $\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$ for all $t\geq 0$, we have
$\frac{k}{n^{1/3}}=\eta_{0}\leq\eta_{t}\leq\frac{\rho}{24\gamma qL_{fg}C_{fg}}$, then we have $n\geq\frac{(24k\gamma qL_{fg}C_{fg})^{3}}{\rho^{3}}$.
Due to $0<\eta_{t}\leq 1$ and $n\geq(c_{1}k)^{3}$, we have $\alpha_{t+1}=c_{1}\eta_{t}^{2}\leq c_{1}\eta_{t}\leq\frac{c_{1}k}{n^{1/3}}\leq 1$.
Similarly, due to $n\geq(c_{2}k)^{3}$ and $n\geq(c_{3}k)^{3}$, we have $\beta_{t+1}\leq 1$ and $\varrho_{t+1}\leq 1$.

According to Lemma [9](#Thmlemma9), for any $m\in[M]$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|h^{m}_{t+1}-g^{m}(x^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}$ (76) $\displaystyle\leq\big{(}\frac{1-\alpha_{t+1}}{\eta_{t}}-\frac{1}{\eta_{t-1}}\big{)}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+2C_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle=\big{(}\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-c_{1}\eta_{t}\big{)}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+2C_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2},$ $$

where the second equality is due to $\alpha_{t+1}=c_{1}\eta^{2}_{t}$.
Similarly, since $\beta_{t+1}=c_{2}\eta^{2}_{t}$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|u^{m}_{t+1}-\nabla g^{m}(x^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}$ (77) $\displaystyle\leq\big{(}\frac{1-\beta_{t+1}}{\eta_{t}}-\frac{1}{\eta_{t-1}}\big{)}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+2L_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle=\big{(}\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-c_{2}\eta_{t}\big{)}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+2L_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}.$ $$

And we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ (78) $\displaystyle\leq\big{(}\frac{1-\varrho_{t+1}}{\eta_{t}}-\frac{1}{\eta_{t-1}}\big{)}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4L^{2}_{f}C^{2}_{g}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}$ $\displaystyle\quad+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2}$ $\displaystyle=\big{(}\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-c_{3}\eta_{t}\big{)}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4L^{2}_{f}C^{2}_{g}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}$ $\displaystyle\quad+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2},$ $$

where the second equality is due to $\varrho_{t+1}=c_{2}\eta^{2}_{t}$.

By $\eta_{t}=\frac{k}{(n+t)^{1/3}}$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}$ $\displaystyle=\frac{1}{k}\big{(}(n+t)^{\frac{1}{3}}-(n+t-1)^{\frac{1}{3}}\big{)}\leq\frac{1}{3k(n+t-1)^{2/3}}\leq\frac{1}{3k\big{(}n/2+t\big{)}^{2/3}}$ $\displaystyle\leq\frac{2^{2/3}}{3k(n+t)^{2/3}}=\frac{2^{2/3}}{3k^{3}}\frac{k^{2}}{(n+t)^{2/3}}=\frac{2^{2/3}}{3k^{3}}\eta_{t}^{2}\leq\frac{2}{3k^{3}}\eta_{t},$ (79) $$

where the first inequality holds by the concavity of function $f(x)=x^{1/3}$, *i.e.*, $(x+y)^{1/3}\leq x^{1/3}+\frac{y}{3x^{2/3}}$; the second inequality is due to $n\geq 2$, and
the last inequality is due to $0<\eta_{t}\leq 1$.

Let $c_{1}\geq\frac{2}{3k^{3}}+B$, for any $m\in[M]$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|h^{m}_{t+1}-g^{m}(x^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}$ (80) $\displaystyle\leq-B\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+2C_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle=-B\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+2C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}+\bar{d}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle\leq-B\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle\leq-\frac{B}{2}\eta_{t}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+BC^{2}_{g}\eta_{t}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2},$ $$

where the last inequality holds by $-\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}\leq-\frac{1}{2}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\|g^{m}(x^{m}_{t})-g^{m}(\bar{x}_{t})\|^{2}\leq-\frac{1}{2}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+C^{2}_{g}\|x^{m}_{t}-\bar{x}_{t}\|^{2}$.

Let $c_{2}\geq\frac{2}{3k^{3}}+5C^{2}_{f}$, for any $m\in[M]$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|u^{m}_{t+1}-\nabla g^{m}(x^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}$ (81) $\displaystyle\leq-5C^{2}_{f}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+2L_{g}^{2}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle=-5C^{2}_{f}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+2L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}+\bar{d}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle\leq-5C^{2}_{f}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle\leq-\frac{5C^{2}_{f}\eta_{t}}{2}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+5C^{2}_{f}L^{2}_{g}\eta_{t}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2},$ $$

where the last inequality holds by $-\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}\leq-\frac{1}{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\|\nabla g(x^{m}_{t})-\nabla g^{m}(\bar{x}_{t})\|^{2}\leq-\frac{1}{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+L^{2}_{g}\|x^{m}_{t}-\bar{x}_{t}\|^{2}$.

Let $c_{3}\geq\frac{2}{3k^{3}}+5C^{2}_{g}$, for any $m\in[M]$, we have

$$ $\displaystyle\frac{1}{\eta_{t}}\mathbb{E}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ (82) $\displaystyle\leq-5C^{2}_{g}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4L^{2}_{f}C^{2}_{g}\mathbb{E}\|x^{m}_{t+1}-x^{m}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2}$ $\displaystyle=-5C^{2}_{g}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}+\bar{d}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2}$ $\displaystyle\leq-5C^{2}_{g}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}$ $\displaystyle\quad+8\alpha^{2}_{t+1}L^{2}_{f}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2}$ $\displaystyle\leq-5C^{2}_{g}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}$ $\displaystyle\quad+\frac{c^{2}_{2}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\eta_{t}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2},$ $$

where the last inequality holds by Assumption , $\alpha_{t+1}=c_{2}\eta^{2}_{t}$ and $\eta_{t}\leq\frac{\rho}{24q\gamma L_{fg}C_{fg}}$ for all $t\geq 0$.

According to Lemma [6](#Thmlemma6), we have

$$ $\displaystyle F(\bar{x}_{t+1})-F(\bar{x}_{t})$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Big{(}\frac{2C_{f}^{2}\eta_{t}\gamma}{\rho}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C_{g}^{2}\eta_{t}\gamma}{\rho}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\qquad+\frac{4C_{g}^{2}L^{2}_{f}\eta_{t}\gamma}{\rho}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}-\frac{\rho}{2\eta_{t}\gamma}\|\bar{x}_{t+1}-\bar{x}_{t}\|^{2}$ $\displaystyle=\frac{1}{M}\sum_{m=1}^{M}\Big{(}\frac{2C_{f}^{2}\eta_{t}\gamma}{\rho}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C_{g}^{2}\eta_{t}\gamma}{\rho}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\qquad+\frac{4C_{g}^{2}L^{2}_{f}\eta_{t}\gamma}{\rho}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}-\frac{\rho\eta_{t}\gamma}{2}\|\bar{d}_{t}\|^{2}.$ (83) $$

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle\leq\frac{6M}{5}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{3M\hat{\delta}^{2}}{5\gamma^{2}L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t},$ (84) $$

Next, we define a *potential* function, for any $t\geq 1$

$$ $\displaystyle\Omega_{t}$ $\displaystyle=\mathbb{E}\Big{[}F(\bar{x}_{t})+\frac{\gamma}{\rho\eta_{t-1}}\frac{1}{M}\sum_{m=1}^{M}\Big{(}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}\Big{)}\Big{]}.$ $$

Then we have

$$ $\displaystyle\Omega_{t+1}-\Omega_{t}$ $\displaystyle=F(\bar{x}_{t+1})-F(\bar{x}_{t})+\frac{\gamma}{M\rho}\sum_{m=1}^{M}\Bigg{(}\frac{1}{\eta_{t}}\mathbb{E}\|h^{m}_{t+1}-g^{m}(x^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\mathbb{E}\|h^{m}_{t}-g^{m}(x^{m}_{t})\|^{2}+\frac{1}{\eta_{t}}\|u^{m}_{t+1}-\nabla g^{m}(x^{m}_{t+1})\|^{2}$ $\displaystyle\quad-\frac{1}{\eta_{t-1}}\|u^{m}_{t}-\nabla g^{m}(x^{m}_{t})\|^{2}+\frac{1}{\eta_{t}}\|v^{m}_{t+1}-\nabla f^{m}(h^{m}_{t+1})\|^{2}-\frac{1}{\eta_{t-1}}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}\Bigg{)}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Big{(}\frac{2C_{f}^{2}\eta_{t}\gamma}{\rho}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+\frac{4C_{g}^{2}\eta_{t}\gamma}{\rho}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+\frac{4C_{g}^{2}L^{2}_{f}\eta_{t}\gamma}{\rho}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}-\frac{\rho\eta_{t}\gamma}{2}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\sum_{m=1}^{M}\bigg{(}-\frac{B}{2}\eta_{t}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+BC^{2}_{g}\eta_{t}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4C_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\alpha_{t+1}^{2}\sigma^{2}$ $\displaystyle\quad-\frac{5C^{2}_{f}\eta_{t}}{2}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+5C^{2}_{f}L^{2}_{g}\eta_{t}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\beta_{t+1}^{2}\sigma^{2}$ $\displaystyle\quad-5C^{2}_{g}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\mathbb{E}\|\bar{d}_{t}\|^{2}+2\varrho^{2}_{t+1}\sigma^{2}$ $\displaystyle\quad+\frac{c^{2}_{2}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\eta_{t}\mathbb{E}\|x^{m}_{t}-\bar{x}_{t}\|^{2}+8L^{2}_{f}\alpha^{2}_{t+1}\sigma^{2}\bigg{)}$ $\displaystyle\leq\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad-\frac{\gamma}{\rho}\big{(}\frac{B}{2}-4C_{g}^{2}L^{2}_{f}-\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\big{)}\eta_{t}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}-\Big{(}\frac{\rho\gamma\eta_{t}}{2}-\frac{4C_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{4L_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{3}}{\rho}\Big{)}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\Big{(}BC^{2}_{g}+5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\eta_{t}(q-1)\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\Big{(}4C_{g}^{2}\eta^{2}_{t}\gamma^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\Big{)}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+\frac{2\sigma^{2}\gamma}{\rho}\big{(}\alpha^{2}_{t+1}+\beta^{2}_{t+1}+\varrho^{2}_{t+1}\big{)},$ (85) $$

where the first inequality holds by the above inequalities ([80](#A1.E80)), ([81](#A1.E81)), ([82](#A1.E82)) and ([A](#A1.Ex204)),
and the last inequality is due to Lemma [11](#Thmlemma11).

Let $s_{t}=q\lfloor t/q\rfloor+1$, summing the above inequality ([A](#A1.Ex209)) over $t=s_{t}$ to $s_{t}+q-1$,
we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\big{(}\Omega_{t+1}-\Omega_{t}\big{)}$ $\displaystyle\leq\sum_{t=s_{t}}^{s_{t}+q-1}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad-\frac{\gamma}{\rho}\big{(}\frac{B}{2}-4C_{g}^{2}L^{2}_{f}-\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\big{)}\eta_{t}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=s_{t}}^{s_{t}+q-1}\Big{(}\frac{\rho\gamma\eta_{t}}{2}-\frac{4C_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{4L_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{3}}{\rho}\Big{)}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\Big{(}BC^{2}_{g}+5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}(q-1)\sum_{l=s_{t}}^{t-1}\gamma^{2}\eta_{l}^{2}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{l}-\bar{d}_{l}\|^{2}$ $\displaystyle\quad+\sum_{t=s_{t}}^{s_{t}+q-1}\frac{\gamma}{M\rho}\Big{(}4C_{g}^{2}\eta^{2}_{t}\gamma^{2}+4L_{g}^{2}\eta^{2}_{t}\gamma^{2}+8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{2}\Big{)}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}+\sum_{t=s_{t}}^{s_{t}+q-1}\frac{2\sigma^{2}\gamma}{\rho}\big{(}\alpha^{2}_{t+1}+\beta^{2}_{t+1}+\varrho^{2}_{t+1}\big{)}$ $\displaystyle\leq\sum_{t=s_{t}}^{s_{t}+q-1}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad-\frac{\gamma}{\rho}\big{(}\frac{B}{2}-4C_{g}^{2}L^{2}_{f}-\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\big{)}\eta_{t}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=s_{t}}^{s_{t}+q-1}\Big{(}\frac{\rho\gamma\eta_{t}}{2}-\frac{4C_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{4L_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{3}}{\rho}\Big{)}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\Big{(}BC^{2}_{g}+5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\frac{\gamma\rho}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|d^{m}_{t}-\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\sigma^{2}}{12qL_{fg}C_{fg}}\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t},$ (86) $$

where the second inequality is due to $\eta_{t}\leq\frac{\rho}{24q\gamma L_{fg}C_{fg}}$ for all $t\geq 0$.

Let $\gamma^{2}\geq\frac{\rho^{2}\sqrt{c^{2}_{1}+c^{2}_{3}}}{24\sqrt{30}qL^{2}_{fg}C^{2}_{fg}}$, we have

$$ $\displaystyle\frac{\rho^{2}C^{2}_{g}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\leq\frac{1}{4}.$ (87) $$

Set $\Theta=\Big{(}5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}+\frac{\gamma\rho}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}$.
Based on the above Lemma [12](#Thmlemma12), then we have

$$ $\displaystyle\sum_{t=s_{t}}^{s_{t}+q-1}\big{(}\Omega_{t+1}-\Omega_{t}\big{)}$ $\displaystyle\leq\sum_{t=s_{t}}^{s_{t}+q-1}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad-\frac{\gamma}{\rho}\big{(}\frac{B}{2}-4C_{g}^{2}L^{2}_{f}-\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\big{)}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=s_{t}}^{s_{t}+q-1}\Big{(}\frac{\rho\gamma\eta_{t}}{2}-\frac{4C_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{4L_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{3}}{\rho}\Big{)}\mathbb{E}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\Big{(}BC^{2}_{g}+5C^{2}_{f}L^{2}_{g}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}\Big{)}\frac{\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}$ $\displaystyle\qquad\cdot\Bigg{(}\frac{6M}{5}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{3M\hat{\delta}^{2}}{5\gamma^{2}L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}\Bigg{)}$ $\displaystyle\quad+\frac{\gamma}{M\rho}\frac{\gamma\rho}{6qL_{fg}C_{fg}}\Big{(}C_{g}^{2}+L_{g}^{2}+2L^{2}_{f}C^{2}_{g}\Big{)}$ $\displaystyle\qquad\cdot\Bigg{(}\frac{6M}{5}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta_{t}\sum_{m=1}^{M}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}+\frac{3M\hat{\delta}^{2}}{5\gamma^{2}L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}\Bigg{)}$ $\displaystyle\quad+\frac{\sigma^{2}}{12qL_{fg}C_{fg}}\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}$ $\displaystyle\leq\sum_{t=s_{t}}^{s_{t}+q-1}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}$ $\displaystyle\quad-\frac{\gamma}{\rho}\Big{(}\frac{B}{4}-4C_{g}^{2}L^{2}_{f}-\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{864q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}-\frac{\Theta\rho^{2}(c_{1}^{2}+c_{3}^{2})}{120q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}\Big{)}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=s_{t}}^{s_{t}+q-1}\Big{(}\frac{\rho\gamma\eta_{t}}{2}-\frac{4C_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{4L_{g}^{2}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{8L^{2}_{f}C^{2}_{g}\eta^{2}_{t}\gamma^{3}}{\rho}-\frac{6\gamma}{5\rho}\big{(}\Theta+\frac{BC^{2}_{g}\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\big{)}\eta_{t}\Big{)}\mathbb{E}\|\bar{d}_{t}\|^{2}$ $\displaystyle\quad+\Big{(}\Theta+\frac{BC^{2}_{g}\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\Big{)}\frac{3\hat{\delta}^{2}}{5\rho\gamma L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}+\frac{\sigma^{2}}{12qL_{fg}C_{fg}}\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}$ $\displaystyle\leq\sum_{t=s_{t}}^{s_{t}+q-1}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}-\frac{\gamma C^{2}_{g}L^{2}_{f}}{\rho}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=s_{t}}^{s_{t}+q-1}\frac{\rho\gamma\eta_{t}}{4}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho\hat{\delta}^{2}}{16\gamma L^{2}_{fg}}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t}+\frac{\sigma^{2}}{12qL_{fg}C_{fg}}\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sum_{t=s_{t}}^{s_{t}+q-1}\eta^{3}_{t},$ (88) $$

where the second inequality holds by the above inequality ([87](#A1.E87)), and the last inequality holds by
$B\geq 20C_{g}^{2}L^{2}_{f}+\frac{c^{2}_{2}C^{2}_{g}L^{2}_{f}}{216q^{3}\gamma^{3}L^{3}_{fg}C^{3}_{fg}}+\frac{\Theta\rho^{2}(c_{1}^{2}+c_{3}^{2})}{30q^{2}\gamma^{4}C^{2}_{fg}L^{2}_{fg}C^{2}_{g}}$,
$\gamma\leq\frac{3\rho qL_{fg}C_{fg}}{4(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})}$ (i.e., the following inequality ([89](#A1.E89))) and $\Theta+\frac{BC^{2}_{g}\rho^{2}}{(24)^{2}L^{2}_{fg}C^{2}_{fg}}\leq\frac{5\rho^{2}}{48}$.

Since $\eta_{t}\leq\frac{\rho}{24q\gamma L_{fg}C_{fg}}$ and $\gamma\leq\frac{3\rho qL_{fg}C_{fg}}{4(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})}$, we have

$$ $\displaystyle\gamma^{2}\leq\frac{\rho^{2}}{32(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})}\frac{24q\gamma L_{fg}C_{fg}}{\rho}\leq\frac{\rho^{2}}{32\eta_{t}(C^{2}_{g}+L^{2}_{g}+2L^{2}_{f}C^{2}_{g})}.$ (89) $$

Summing the above inequality [A](#A1.Ex231) from $t=1$ to $T$, then we have

$$ $\displaystyle\sum_{t=1}^{T}\big{(}\Omega_{t+1}-\Omega_{t}\big{)}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{1}{M}\sum_{m=1}^{M}\Bigg{(}-\frac{C_{f}^{2}\gamma}{2\rho}\eta_{t}\mathbb{E}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}-\frac{C_{g}^{2}\gamma}{\rho}\eta_{t}\mathbb{E}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}-\frac{\gamma C^{2}_{g}L^{2}_{f}}{\rho}\eta_{t}\mathbb{E}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Bigg{)}$ $\displaystyle\quad-\sum_{t=1}^{T}\frac{\rho\gamma\eta_{t}}{4}\mathbb{E}\|\bar{d}_{t}\|^{2}+\frac{\rho\hat{\delta}^{2}}{16\gamma L^{2}_{fg}}\sum_{t=1}^{T}\eta^{3}_{t}+\frac{\sigma^{2}}{12qL_{fg}C_{fg}}\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sum_{t=1}^{T}\eta^{3}_{t}.$ (90) $$

Since $h^{m}_{1}=\frac{1}{q}\sum_{j=1}^{q}g^{m}(x^{m}_{1};\zeta^{m}_{1,j})$, $u^{m}_{1}=\frac{1}{q}\sum_{j=1}^{q}\nabla g^{m}(x^{m}_{1};\zeta^{m}_{1,j})$ and $v^{m}_{1}=\frac{1}{q}\sum_{j=1}^{q}\nabla f(h^{m}_{1};\xi^{m}_{1,j})$ for all $m\in[M]$, we have

$$ $\displaystyle\Omega_{1}$ $\displaystyle=\mathbb{E}\Big{[}F(\bar{x}_{1})+\frac{\gamma}{\rho\eta_{0}}\frac{1}{M}\sum_{m=1}^{M}\Big{(}\|h^{m}_{1}-g^{m}(x^{m}_{1})\|^{2}+\|u^{m}_{1}-\nabla g^{m}(x^{m}_{1})\|^{2}+\|v^{m}_{1}-\nabla f^{m}(h^{m}_{1})\|^{2}\Big{)}\Big{]}$ $\displaystyle\leq F(\bar{x}_{1})+\frac{3\gamma\sigma^{2}}{q\rho\eta_{0}},$ (91) $$

where the last inequality holds by Assumption [2](#Thmassumption2).

Since $\eta_{t}=\frac{k}{(n+t)^{1/3}}$ is decreasing, i.e., $\eta_{T}^{-1}\geq\eta_{t}^{-1}$ for any $0\leq t\leq T$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\Big{[}\frac{1}{M}\sum_{m=1}^{M}\frac{1}{\rho^{2}}\Big{(}2C_{f}^{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+4C_{g}^{2}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4C^{2}_{g}L^{2}_{f}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}+\|\bar{d}_{t}\|^{2}\Big{]}$ $\displaystyle\leq\frac{4}{T\rho\gamma\eta_{T}}\sum_{t=1}^{T}\big{(}\Omega_{t}-\Omega_{t+1}\big{)}+\frac{\hat{\delta}^{2}}{4T\gamma^{2}\eta_{T}L^{2}_{fg}}\sum_{t=1}^{T}\eta^{3}_{t}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3T\rho\gamma\eta_{T}qL_{fg}C_{fg}}\sum_{t=1}^{T}\eta^{3}_{t}$ $\displaystyle\leq\frac{4}{T\rho\gamma\eta_{T}}\big{(}F(\bar{x}_{1})+\frac{3\gamma\sigma^{2}}{\rho\eta_{0}}-F^{*}\big{)}+\Big{(}\frac{\hat{\delta}^{2}}{4T\gamma^{2}\eta_{T}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3T\rho\gamma\eta_{T}qL_{fg}C_{fg}}\Big{)}\sum_{t=1}^{T}\eta^{3}_{t}$ $\displaystyle\leq\frac{4}{T\rho\gamma\eta_{T}}\big{(}F(\bar{x}_{1})+\frac{3\gamma\sigma^{2}}{q\rho\eta_{0}}-F^{*}\big{)}+\Big{(}\frac{\hat{\delta}^{2}}{4T\gamma^{2}\eta_{T}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3T\rho\gamma\eta_{T}qL_{fg}C_{fg}}\Big{)}\int^{T}_{1}\frac{k^{3}}{n+t}dt$ $\displaystyle\leq\frac{4}{T\rho\gamma\eta_{T}}\big{(}F(\bar{x}_{1})+\frac{3\gamma\sigma^{2}}{q\rho\eta_{0}}-F^{*}\big{)}+\frac{1}{T\eta_{T}}\Big{(}\frac{\hat{\delta}^{2}}{4\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\rho\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)$ $\displaystyle=\bigg{(}\frac{4(F(\bar{x}_{1})-F^{*})}{k\rho\gamma}+\frac{12n^{1/3}\sigma^{2}}{qk^{2}\rho^{2}}+4k^{2}\Big{(}\frac{\hat{\delta}^{2}}{4\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\rho\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)\bigg{)}\frac{(n+T)^{1/3}}{T},$ (92) $$

where the second inequality holds by the above inequality ([A](#A1.Ex247)).
Let $G=\frac{4(F(\bar{x}_{1})-F^{*})}{k\rho\gamma}+\frac{12n^{1/3}\sigma^{2}}{qk^{2}\rho^{2}}+4k^{2}\Big{(}\frac{\hat{\delta}^{2}}{4\rho\gamma^{2}L^{2}_{fg}}+\frac{\big{(}c^{2}_{1}+c^{2}_{2}+c^{2}_{3}\big{)}\sigma^{2}}{3\rho\gamma qL_{fg}C_{fg}}\Big{)}\ln(n+T)$.
According to the above Lemma [7](#Thmlemma7), then
we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\Big{[}\frac{1}{\rho^{2}}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|^{2}+\|\bar{d}_{t}\|^{2}\Big{]}$ $\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\Big{[}\frac{1}{M}\sum_{m=1}^{M}\frac{1}{\rho^{2}}\Big{(}2C_{f}^{2}\|u^{m}_{t}-\nabla g^{m}(\bar{x}_{t})\|^{2}+4C_{g}^{2}\|v^{m}_{t}-\nabla f^{m}(h^{m}_{t})\|^{2}+4C^{2}_{g}L^{2}_{f}\|h^{m}_{t}-g^{m}(\bar{x}_{t})\|^{2}\Big{)}+\|\bar{d}_{t}\|^{2}\Big{]}$ $\displaystyle\leq\frac{G}{T}(n+T)^{1/3},$ (93) $$

where the first inequality holds by Lemma [7](#Thmlemma7), and the last inequality holds by ([A](#A1.Ex248)).

Since $\bar{d}_{t}=\frac{\bar{x}_{t}-\bar{x}_{t+1}}{\eta_{t}\gamma}=\frac{\eta_{t}\gamma A_{t}^{-1}\bar{w}_{t}}{\eta_{t}\gamma}=A_{t}^{-1}\bar{w}_{t}$,
and let $\mathcal{G}_{t}=\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|+\|\bar{d}_{t}\|$, we have

$$ $\displaystyle\mathcal{G}_{t}$ $\displaystyle=\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|+\|\bar{d}_{t}\|=\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|+\|A_{t}^{-1}\bar{w}_{t}\|$ $\displaystyle\geq\|A^{-1}_{t}\bar{w}_{t}\|+\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|$ $\displaystyle=\frac{1}{\|A_{t}\|}\|A_{t}\|\|A_{t}^{-1}\bar{w}_{t}\|+\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|$ $\displaystyle\geq\frac{1}{\|A_{t}\|}\|\bar{w}_{t}\|+\frac{1}{\rho}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|$ $\displaystyle\mathop{\geq}^{(i)}\frac{1}{\|A_{t}\|}\|\bar{w}_{t}\|+\frac{1}{\|A_{t}\|}\|\nabla F(\bar{x}_{t})-\bar{w}_{t}\|$ $\displaystyle\geq\frac{1}{\|A_{t}\|}\|\nabla F(\bar{x}_{t})\|,$ (94) $$

where the inequality $(i)$ holds by $\|A_{t}\|\geq\rho$ for all $t\geq 1$ due to Assumption [6](#Thmassumption6). Then we have

$$ $\displaystyle\|\nabla F(\bar{x}_{t})\|\leq\|A_{t}\|\mathcal{G}_{t}.$ (95) $$

According to Cauchy-Schwarz inequality, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|\leq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\big{[}\mathcal{G}_{t}\|A_{t}\|\big{]}\leq\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\mathcal{G}_{t}^{2}]}\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}}.$ (96) $$

According to the above inequality ([A](#A1.Ex253)), we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\mathcal{G}_{t}^{2}]$ $\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\Big{[}\frac{2}{\rho^{2}}\|\bar{w}_{t}-\nabla F(\bar{x}_{t})\|^{2}+2\|\bar{d}_{t}\|^{2}\Big{]}$ $\displaystyle\leq\frac{2G}{T}(n+T)^{1/3}.$ (97) $$

Combining the above inequalities ([96](#A1.E96)) with ([A](#A1.Ex260)), we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|\nabla F(\bar{x}_{t})\|$ $\displaystyle\leq\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\mathcal{G}_{t}^{2}]}\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}}$ $\displaystyle\leq\Big{(}\frac{\sqrt{2G}n^{1/6}}{T^{1/2}}+\frac{\sqrt{2G}}{T^{1/3}}\Big{)}\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\|A_{t}\|^{2}}.$ (98) $$

∎

###### Lemma 3 .

###### Lemma 4 .

###### Lemma 5 .

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof.

###### Lemma 8 .

###### Proof.

###### Lemma 9 .

###### Proof.

###### Lemma 10 .

###### Proof.

###### Lemma 11 .

###### Proof.

###### Lemma 12 .

###### Proof.

###### Theorem 3 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: Regarding sample complexity, shouldn't the total number of samples be $ 2qM + TM$? This would include the $2q$ samples drawn during the initialization phase for each worker, as well as the two samples drawn at each iteration $t \in [T] $ and for each worker $m \in [M]$. By this reasoning, the sample complexity would be $2qM + TM = \tilde{O}(M \epsilon^{-3})$. Could the authors provide clarification on this calculation?
soundness: 2
strengths: The paper tackles a challenging compositional optimization problem in nonconvex settings with heterogeneous data, achieving sample complexity of $O(\epsilon^{-3})$ and communication complexity of $O(\epsilon^{-2})$, comparable to the best current methods.
summary: The paper introduces MFCGD and AdaMFCGD, two algorithms designed for federated compositional optimization in nonconvex settings with heterogeneous data. By leveraging variance reduction techniques, these algorithms achieve efficient sample and communication complexities of $O(\epsilon^{-3})$ and $O(\epsilon^{-2})$, respectively. The authors support their findings with theoretical analysis and empirical validation using the MNIST and CIFAR-10 datasets.
weaknesses: * *Novelty of this Approach*: Upon review, there appears to be an overlap with recent advances, specifically with the Fed-DR-SCGD algorithm published at the ICML proceedings in early May ([Fed-DR-SCGD Paper](https://openreview.net/pdf?id=GentO2E4ID)). This algorithm demonstrates comparable sample complexity of $O\left(\frac{1}{\epsilon^3}\right)$ and communication complexity of $O\left(\frac{1}{\epsilon^2}\right)$. Given this context, comparing Fed-DR-SCGD would strengthen the paper’s contribution and clarify its unique value. Could the authors highlight any distinctive advantages of MFCGD / AdaMFCGD over Fed-DR-SCGD?

* *Lack of Explicit Dependence on the Number of Machines $M$*: The convergence rates in *Theorem 1.* and *Theorem 2.* do not explicitly depend on the number of machines $M$, which is atypical in distributed stochastic optimization. In many distributed settings, the convergence rate often scales with the number of machines, reflecting the collective contribution to reducing variance and accelerating convergence. 

* *Unavailable Code*: The absence of available code for the experiments reduces the transparency of the results, making it challenging to validate the findings and restricting the community's ability to build upon this work.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: - What are the technical contributions of this paper? I skimmed through the proof and it looks like a combination of several existing results [2, 4, 5, 6]. Can you highlight the technical difficulties and novelties?
- Can you explain how you handled the unknown constant  $C_g$ and $C_f$ (lines 18 and 19 of Algorithm 1) in your experiments?

[4] Gao, Hongchang, Junyi Li, and Heng Huang. "On the convergence of local stochastic compositional gradient descent with momentum." In International Conference on Machine Learning, pp. 7017-7035. PMLR, 2022.

[5] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. "Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization." IEEE Transactions on Signal Processing 69 (2021): 4937-4948.

[6] Jiang, Wei, Bokun Wang, Yibo Wang, Lijun Zhang, and Tianbao Yang. "Optimal algorithms for stochastic multi-level compositional optimization." In International Conference on Machine Learning, pp. 10195-10216. PMLR, 2022.
soundness: 1
strengths: Whether the sample and communication complexities for the distributed composition optimization problem can be further improved is indeed an open problem.  Additionally, adaptivity in stochastic algorithms is an interesting area of research, even for single-level optimization problems.
summary: This paper proposes a variance-reduced local stochastic algorithm based on STORM [1] estimators for improving sample and communication complexities in distributed compositional optimization. The algorithm incorporates adaptivity within the SUPER-ADAM [2] framework. They also performed numerical experiments on the robust federated learning problem to testify the proposed algorithm.

[1] Cutkosky, Ashok, and Francesco Orabona. "Momentum-based variance reduction in non-convex sgd." Advances in neural information processing systems 32 (2019).

[2] Huang, Feihu, Junyi Li, and Heng Huang. "Super-adam: faster and universal framework of adaptive gradients." Advances in Neural Information Processing Systems 34 (2021): 9074-9085.
weaknesses: - The proof of Lemma 6 seems to be problematic. How can you get (27) from (26)? To be specific, how can you get $<w\_t^m,\frac{1}{\eta\_t \gamma}(\bar{x}\_t - \bar{x}\_{t+1})>$ from $\frac{1}{M}\sum_{m=1}^M<w\_t^m,\frac{1}{\eta\_t \gamma}(x\_t^m - x\_{t+1}^m)>$? Note that $w\_t^m$ also depends on $m$.
- The title "Federated Methods for Distributed Compositional Optimization" is potentially misleading. Federated learning and distributed learning are fundamentally distinct paradigms, each with different settings, assumptions (on data and clients), and requirements. See, e.g., Table 1.1 in [3]. Using these terms interchangeably is quite confusing.
- In lines 18 and 19 of Algorithm 1, the proposed algorithms require projection onto balls with unknown problem-specific constants $C_g$ and $C_f$. This limits the applicability of the proposed algorithm.
- Client sampling is highly desirable in the cross-device federated learning regime since the total number of clients M is quite large. Unfortunately, the proposed algorithms in this paper do not support this feature.  
- The function g in (10) is an exponential function. It makes no sense to assume its stochastic gradient is Lipschitz and bounded (as in Assumption 2 and Assumption 3), considering the model w in this paper is unconstrained. 
- The numerical experiments cannot fully verify the robustness of the proposed AdaMFCGD algorithm without comparing it to standard local algorithms such as FedAvg and SCAFFOLD. This can justify why the composition optimization problem in (10) is meaningful and whether it can improve the robustness compared to Federated ERM. 


[3] Kairouz, Peter, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz et al. "Advances and open problems in federated learning." Foundations and trends® in machine learning 14, no. 1–2 (2021): 1-210.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. See the Weaknesses above.
soundness: 2
strengths: 1. The proposed adaptive algorithms effectively reduce sample and communication complexities for non-convex distributed compositional optimization problems.
summary: This paper proposes a class of faster adaptive federated compositional optimization algorithms to address non-convex distributed compositional problems. By employing a unified adaptive matrix, the adaptive algorithm achieves a lower sample and lower communication complexities.
weaknesses: 1. Some highly relevant works are not cited. For instance, [1] and [2] discuss storm-like algorithms for compositional optimization problems, while [3] addresses momentum-based federated methods for distributed compositional optimization.
2. The improvement presented in the paper appears to be incremental. The use of an adaptive matrix is not novel within adaptive algorithms, as similar approaches have been explored, such as in [4]. In the distributed setting, the adaptive matrix operates independently on each client without communication. While communicating this matrix would be computationally expensive and unnecessary, this choice makes the theoretical analysis closely resemble that of the non-federated setting. As a result, the contribution of this paper is trivial, limiting its overall novelty.
3. There is a typo in Eq.(4), a_t should have a squared root.

[1] Huizhuo Yuan, Wenqing Hu. Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization, arXiv preprint arXiv: 2006.01688, 2020.
[2] Liu, Jin, et al. Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization. Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 12. 2024.
[3] Zhang, Xinwen, et al. Federated compositional deep auc maximization. Advances in Neural Information Processing Systems 36 (2024).
[4] Feihu Huang, et al. Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 34:9074–9085, 2021b.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: - What are some of the recent works in this area (see also Weaknesses)?
- Typos:
  - Line 897: "Assumption ,."
soundness: 4
strengths: - The proposed algorithms are novel and well-motivated.
- The theoretical results are thorough. The authors provided convergence results for a general adaptive step size framework.
- The experimental results are promising. The proposed algorithms achieve better performance than existing methods.
summary: In this paper, the authors considered the distributed composition optimization problem. They proposed MFCGD and AdaMFCGD, which leverage adaptive step size on both the server and clients, and momentum-based variance reduction on clients. The authors derived convergence results for the proposed algorithms. Finally, they conducted experiments to show that the proposed algorithms achieve better performance than existing methods.
weaknesses: - The literature review is not up-to-date. It seems the authors only considered works up to 2022. As far as I know, there are more recent works on Distributed/ Federated Composition Optimization (e.g., [1], [2], [3]). The authors should conduct a more thorough literature review.  
  [1] Hongchang Gao. A Doubly Recursive Stochastic Compositional Gradient Descent Method for Federated Multi-Level Compositional Optimization. ICML 2024.  
  [2] Xidong Wu et al. Federated Conditional Stochastic Optimization. NeurIPS 2023.  
  [3] Xinwen Zhang et al. Federated Compositional Deep AUC Maximization. NeurIPS 2023.