Riemannian Federated Learning via Averaging Gradient Streams

## Abstract

Abstract Federated learning (FL) as a distributed learning paradigm has a significant advantage in addressing large-scale machine learning tasks.
In the Euclidean setting, FL algorithms have been extensively studied with both theoretical and empirical success.
However, there exist few works that investigate federated learning algorithms in the Riemannian setting.
In particular, critical challenges such as partial participation and data heterogeneity among agents are not explored in the Riemannian federated setting.
This paper presents and analyzes a Riemannian FL algorithm, called RFedAGS, based on a new efficient server aggregation—averaging gradient streams, which can simultaneously handle partial participation and data heterogeneity.
We theoretically show that the proposed RFedAGS has global convergence and sublinear convergence rate under decaying step sizes cases; and converges sublinearly/linearly to a neighborhood of a stationary point/solution under fixed step sizes cases.
These analyses are based on a vital and non-trivial assumption induced by partial participation, which is shown to hold with high probability. Extensive experiments conducted on synthetic and real-world data demonstrate the good performance of RFedAGS. Keywords: Riemannian federated learning, Averaging gradient streams, Partial participation, Heterogeneity data, Riemannian distributed optimization

## 1 Introduction

Modern learning tasks handle massive amounts of data, which are geographically distributed across heterogeneous devices. Conventional centralized algorithms, e.g., stochastic gradient descent (SGD), need to collect the data into single device for training, which consumes significant storage and computing resource. Additionally, from the perspective of privacy security, transmitting raw training data may leak data privacy.
A promising distributed learning paradigm—federated learning (FL)—allows a center server to coordinate with multiple agents (e.g., mobile phones and tablets) to train a desired model parameter without raw data sharing, which is an ideal solution to the issues aforementioned.

In recent years, with the development of Riemannian optimization, many machine learning problems have data structures that can be inscribed by low-dimensional smooth manifolds, and thus they can be modeled on manifolds. There are such examples including but not limited to principal component analysis [YZ21], Fréchet mean computation [HMJG21], hyperbolic structured prediction [XCNS22], low-rank matrix completion [JM18, MKJS19], multitask feature learning [JM18, MKJS19], and neural network training [Mag23]. This motives us to develop an efficient Riemannian FL algorithm.

This paper focuses on the following Riemannian federated optimization problem

$$ $\displaystyle\operatorname*{arg\,min}_{x\in\mathcal{M}}F(x):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x),\hbox{ with }f_{i}(x)=\mathbb{E}_{\xi\sim\mathcal{D}_{i}}[f_{i}(x;\xi)],$ (1.1) $$

where $\mathcal{M}$ is a $d$-dimensional Riemannian manifold, $N$ is the number of agents, $F:\mathcal{M}\rightarrow\mathbb{R}$ is the global objective, and $f_{i}:\mathcal{M}\rightarrow\mathbb{R}$ and $\mathcal{D}_{i}$ are local objectives and the data distribution held by agent $i$, $\forall i\in[N]=\{1,2,\dots,N\}$. Throughout this paper, we focus on the expected minimization ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)), but the resulting conclusions are also true for the finite sum minimization in which the local objective is defined by $f_{i}(x)=\frac{1}{N_{i}}\sum_{j=1}^{N_{i}}f_{i}(x;z_{i,j})$ with $\mathcal{D}_{i}=\{z_{i,1},z_{i,2},\dots,z_{i,N_{i}}\}$ the local dataset held by agent $i$.
We may not necessarily assume that $\mathcal{D}_{i}$, $\forall i\in[N]$, are the independently identical distribution (I.I.D.), i.e., the data distributions across different agents are non-I.I.D.

A well-known Euclidean FL algorithm is Federated Averaging (FedAvg) [MMR^+17], which is adapted from the local stochastic gradient descent (local SGD) method. Specifically, at the beginning, FedAvg takes an initial guess $x_{1}$ as input and then sends it to all agents. Subsequently, the following steps are performed alternately:

- (i)
agent $j$ updates its the local parameter via performing $K$-step SGD with $x_{t}$ being the initial guess and generates the trained local parameter $x_{t,K}^{j}$ (this is called “local update” or “inner iteration”), and then the local parameter $x_{t,K}^{j}$ is uploaded to the server;
- (ii)
the server at random samples a subset of size $S$ from all agents, denoted by $\mathcal{S}_{t}$, and then averages the received local parameters to generate the next global parameter $x_{t+1}$, i.e.,
$\displaystyle x_{t+1}\leftarrow\frac{1}{S}\sum_{j\in\mathcal{S}_{t}}x_{t,K}^{j},$
(1.2)
which is called “server aggregation”, and then sends $x_{t+1}$ to all agents.

The two steps above constitute a round of communication (or outer iteration).

##### Related works.

Early works primarily analyzed the convergence of FedAvg and its variants in limited settings, typically relying on one or both of the following assumptions: (i) full participation (i.e., $S=N$) and (ii) I.I.D. data distributions; see, e.g., [ZC18, Sti19, YYZ19, HKMC19, WJ21, GLHA23] and references therein.
Subsequently, numerous works have studied the convergence of FL algorithms under (iii) partial participation and (iv) non-I.I.D. data assumption; see e.g., [LHY^+20, LSZ^+20, RVS22] and references therein. In these works, partial participation is implemented by random sampling—the server randomly selects a subset of agents to perform local updates in each outer iteration.

Due to heterogeneity in the computational capabilities and the environment conditions across agents,
their availability and response speeds are hardly predictable. This unpredictability makes random sampling-based approaches unsuitable for such scenarios.
Recent works have instead adopted an arbitrary participation model, where agents may respond to the server in a stochastic and uncontrolled manner [GHZH21, WJ22, RVdV23, XIY^+23, YND^+23, WJ24, XIY^+25]. These works can be roughly divided into three categories:
(i) time-varying statistic, i.e. agent $i$ participates in the $t$-th outer iteration with probability $p_{t}^{i}$ varying over time [WJ22, RVdV23, XIY^+23, WJ24, XIY^+25];
(ii) time-invariant statistic, i.e., the participation probability for agent $i$ is not varying over time (meaning $p_{t}^{i}=p_{i}$ for all $t\geq 1$) [WJ24];
and (iii) periodic participation, i.e.,
each agent $i$ must participate in at least one communication round within a fixed iteration interval [GHZH21, YND^+23].

The FL algorithms mentioned earlier operate solely in Euclidean space and thus cannot directly handle such problems whose parameters are located in manifolds due to the inherent curvature effects of manifolds.
Only a limited number of studies have explored the design and analysis of FL algorithms on Riemannian manifolds. Li and Ma [LM23] proposed a Riemannian counterpart of ([1.2](https://arxiv.org/html/2409.07223v2#S1.E2)) and thus developed a Riemannian FL algorithm. Their algorithm involves in exponential mapping, its inverse, and parallel transport. Nevertheless, for some manifolds, e.g., the Stiefel manifold, the inverse of the exponential mapping and parallel transport have no closed forms, and only iterative methods can be used to compute them, which brings an extra computation burden.
Huang et al. [HHJM24] adopted a framework similar to that of [LM23] but integrate differential privacy to strengthen privacy guarantees.
Under the non-I.I.D. setting, most convergence results in [LM23, HHJM24] are established for the case $K=1$ and full participation, i.e., all agents just perform one step local update (notably, for $K>1$, the convergence analyses of both algorithms further assume that only one agent participates in communication).
The algorithm proposed in [ZHSJ24] supports general settings where $K>1$ and $S>1$, but its convergence analysis relies on the full participation assumption. Additionally, the algorithm therein involves an orthogonal projector onto the manifold and requires that this projector is a singleton. Thus, its applicability is restricted to problems on compact Riemannian submanifolds embedded in Euclidean spaces. The algorithms in [XYW24, XYZ25] incorporated the Barzilai-Borwein method into the framework of [LM23]. Despite the efforts of some, all of the Riemannian FL algorithms above have no theoretical guarantee under both partial participation and data heterogeneity setting.
See Table [1](https://arxiv.org/html/2409.07223v2#S1.T1)
for comprehensive comparisons of existing Riemannian FL algorithms and the proposed RFedAGS.

**Table 1: Summary of existing algorithms and the proposed RFedAGS.**
| Algorithms | Manifold | Partial Participation | Non-I.I.D. | Retraction | Vector transport |
| --- | --- | --- | --- | --- | --- |
| RFedSVRG [LM23] | General ^1 | ✗ ^2 | Conditioned ^3 | Exponential mapping | Parallel transport |
| RPriFed [HHJM24] | General ^1 | ✗ | Conditioned ^3 | Exponential mapping | Parallel transport |
| RFedProj [ZHSJ24] | Compact submanifold | ✗ | ✔ | N/A | N/A |
| RFedSVRG-2BBS [XYW24] | General ^1 | ✗ ^2 | Conditioned ^3 | Exponential mapping | Parallel transport |
| RFedSVRG-BB [XYZ25] | General ^1 | ✗ ^2 | Conditioned ^3 | Exponential mapping | Parallel transport |
| RFedAGS (this paper) | General | ✔ | ✔ | General retraction | Bounded |

##### Challenges.

In this paper, we focus on investigating a FL algorithms on general Riemannian manifolds, which works under arbitrary participation and data heterogeneity setting. In that case, the challenges of designing and analyzing such an algorithm mainly arise from (i) the curvature effects of manifolds, (ii) multiple-step local updates at each agent, (iii) stochastic error of arbitrary participation, and (iv) data heterogeneity across agents.
The biggest challenge brought by (i) and (iii) is how the server generates new global parameters based on the local update information from multiple agents, which directly affects the design of the algorithm. While (ii) and (iv) will bring local errors into the global parameter even make algorithms diverge, which is called agent drift effects.
These issues often couple together and make convergence analysis more complicated.

##### Contributions.

The main contributions of this paper are summarized as follows.

- 1.
The server aggregation (SA) proposed in [LM23] is inspired by the Euclidean weighted average ([2.1](https://arxiv.org/html/2409.07223v2#S2.E1)). Although this SA is feasible in practice, it has significant challenges in terms of theory analysis and computation efficiency. This paper presents a new SA which can avoid the issues mentioned above. The idea behind the presented SA is that it does not handle local parameters but rather averages local gradient information, which retains linearity to some extent.
- 2.
We investigate the availability of the proposed RFedAGS under arbitrary participation and non-I.I.D. data, where the arbitrary participation setting is based on the time-invariant statistic model without requiring prior knowledge of the participation probabilities. This model encompasses many practical scenarios, including random sampling.
- 3.
We establish the convergence guarantees of the proposed RFedAGS under the arbitrary participation and non-I.I.D data setting with the standard assumptions in FL and Riemannian optimization except Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) which is important and nontrivial. We also discuss the reasonability of this assumption when using the frequencies to estimate the true probabilities.
- 4.
Extensive numerical experiments with synthetic/real-world data are conducted to demonstrate the efficacy of the proposed RFedAGS.

##### Notations.

Throughout this paper, we use $\mathbb{R},\mathbb{R}^{n}$, and $\mathbb{R}^{m\times n}$ to denote the real numbers, the space real vectors of dimension $n$, and the space real matrices of size $m\times n$, respectively.
We use $\mathcal{M}$ to denote the Riemannian manifold and the equipped Riemannian metric is denoted by $\left<\cdot,\cdot\right>$, whose the induced norm on the tangent space $\mathrm{T}_{x}\mathcal{M}$ is denoted by $\|\cdot\|_{x}$ (omitting the subscript sometimes). $\mathrm{Exp}$, $\mathrm{R}$, $\mathcal{T}$, and $\mathrm{grad}f$ denote exponential mapping, retraction, vector transport, and the gradient of $f:\mathcal{M}\rightarrow\mathbb{R}$, respectively. Also, $\left<\cdot,\cdot\right>_{\mathrm{F}}$, $\|\cdot\|_{\mathrm{F}}$, and $\nabla f$ denote the Euclidean inner product, the norm induced by the Euclidean inner product, and the Euclidean gradient of $f$.

## 2 RFedAGS: R iemannian Fed erated A veraging G radient S treams

A basic background in Riemannian geometry and optimization is assumed, and the details can be found in Appendix [B](https://arxiv.org/html/2409.07223v2#A2).
The proposed RFedAGS (stated in Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1)) is explained as follows.

Figure: Algorithm 1 Riemannian Federated Learning via Averaging Gradient Streams: RFedAGS

##### A new Riemannian SA.

Due to the curvature effects of manifolds, the addition of two points in a manifold is not valid, and thus the SA via the weighted average of local parameters ([1.2](https://arxiv.org/html/2409.07223v2#S1.E2)) does not work in the Riemannian setting.
[LM23] proposed a SA, called tangent mean, defined by

$$ $\displaystyle x_{t+1}\leftarrow\mathrm{Exp}_{x_{t}}\left(\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\mathrm{Exp}_{x_{t}}^{-1}(x_{t,K}^{i})\right),$ (TM) $$

which is an approximate to the weighted average of points on a manifold.
On the one hand, ([TM](https://arxiv.org/html/2409.07223v2#S2.Ex1)) involves the inverse of exponential mapping, which has no closed-form expression in some manifolds, e.g., the Stiefel manifold. This limits its scope of availability.
Additionally, due to the curvature effects of manifolds, exponential mapping and its inverse almost are nonlinear. Hence, when agents perform multiple-step local updates, ([TM](https://arxiv.org/html/2409.07223v2#S2.Ex1)) involves multiple consecutive exponential mappings, resulting in that the increment of parameters, $\mathrm{Exp}_{x_{t}}^{-1}(x_{t+1})$, is difficult to be bounded in analysis, which makes convergence analysis fairly challenging.
In view of the discussions above, this paper resorts to another aggregation which can not only implement SA efficiently but also analyze algorithm convergence conveniently.

Back to the Euclidean setting, the increment of parameters of FedAvg can be expanded as

$$ $\Delta_{t}=x_{t+1}-x_{t}=-\alpha_{t}\frac{1}{|\mathcal{S}_{t}|}\sum_{i\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{i}}\nabla f_{i}(x_{t,k}^{i};\xi_{t,k,b}^{i}).$ $$

Observing the expression shows that the increment of parameters is given by the average of mini-batch gradients of active agents.
We can adopt the similar idea in the Riemannian setting but require making some adaptations, since directly combining the mini-batch gradients located in different tangent spaces is not well defined.
With the aid of vector transport, the combination can be defined. Specifically, we define the the Riemannian “increment of parameters” as

$$ $\zeta_{t}=\mathrm{R}_{x_{t}}^{-1}(x_{t+1})=-\alpha_{t}\frac{1}{|\mathcal{S}_{t}|}\sum_{j\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}{\color[rgb]{1,0,0}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}}(\mathrm{grad}f_{j}(x_{t,k}^{k};\xi_{t,k,b}^{j})).$ $$

Specific to agent $j$, it just need to upload

$$ $\zeta_{t,K}^{j}=\sum_{k=0}^{K-1}\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{k};\xi_{t,k,b}^{j})),$ $$

called gradient stream, to the server.
The resulting new SA is given via averaging gradient streams:

$$ $\displaystyle x_{t+1}=\mathrm{R}_{x_{t}}(\zeta_{t})=\mathrm{R}_{x_{t}}\left(-\alpha_{t}\frac{1}{|\mathcal{S}_{t}|}\sum_{j\in\mathcal{S}_{t}}\zeta_{t,K}^{j}\right).$ (AGS-RS) $$

It is worth noting that when the manifold reduces to a Euclidean space, ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) is equivalent to the Euclidean SA ([1.2](https://arxiv.org/html/2409.07223v2#S1.E2)).
In our opinion, this aggregation is a more essential generalization from the Euclidean setting to the Riemannian setting.

##### Arbitrary partial participation.

Now we are ready to extend ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) to the arbitrary partial participation setting under consideration, which is formally modeled in Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1).

###### Assumption 2.1 .

Assume that each agent $i$ independently participates in any round of communication with probability $p_{i}>0$.

Under Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1), when the participation probabilities are not exactly equal to each other, using ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) simply may introduce stochastic participation errors. In that case,
the next theorem points out that the algorithm equipped with ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) may work incorrectly since it
may solve another problem different from the original problem.

###### Theorem 2.1 (Proved in Appendix E.1 ) .

Under Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1), let $\mathcal{S}_{t}$ denotes the set of agents who respond to the server at the $t$-th round of communication. Then, $\mathbb{E}\left[\sum_{j\in\mathcal{S}_{t}}\frac{1}{|\mathcal{S}_{t}|}\mathrm{grad}f_{j}(x)\right]=\sum_{i=1}^{N}\tilde{p}_{i}\mathrm{grad}f_{i}(x),$
with $\tilde{p_{i}}=p_{i}\int_{0}^{1}\prod_{j\not=i}^{N}(1-p_{j}+p_{j}t)\mathrm{d}t$.

Therefore, if $p_{i}\not=p_{j}$ for some $i,j\in[N]$, then $\tilde{p_{i}}\not=\tilde{p}_{j}$, and thus there exists no $\chi>0$ such that $\sum_{i=1}^{N}\tilde{p_{i}}\mathrm{grad}f_{i}(x)=\chi\mathrm{grad}F(x)$. That is, the algorithm may not solve the original problem $\min_{x\in\mathcal{M}}F(x)$ since each of its search directions leads the iterate $x_{t}$ to the minimizer of another problem $\min_{x\in\mathcal{M}}\tilde{F}(x):=\sum_{i=1}^{N}{\tilde{p}_{i}}f_{i}(x)$.

Back again to Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1), at the $t$-th round of communication, note that

$$ $\displaystyle\mathbb{E}\left[\sum_{i\in\mathcal{S}_{t}}\frac{1}{p_{i}N}\mathrm{grad}f_{i}(x)\right]$ $\displaystyle=\mathbb{E}\left[\sum_{i=1}^{N}\frac{1}{p_{i}N}\mathbb{I}_{\mathcal{S}_{t}}(i)\mathrm{grad}f_{i}(x)\right]=\sum_{i=1}^{N}\frac{1}{p_{i}N}\mathbb{E}\left[\mathbb{I}_{\mathcal{S}_{t}}(i)\mathrm{grad}f_{i}(x)\right]$ $\displaystyle=\sum_{i=1}^{N}\frac{1}{p_{i}N}\left(p_{i}\mathrm{grad}f_{i}(x)\right)=\mathrm{grad}F(x),$ (2.1) $$

where $\mathbb{I}_{\mathcal{S}_{t}}(i)=1$ if $i\in\mathcal{S}_{t}$ otherwise $\mathbb{I}_{\mathcal{S}_{t}}(i)=0$. Hence, if the participation probabilities, $p_{i}$’s, are known, one of the feasible aggregation patterns can be chosen as

$$ $\displaystyle x_{t+1}\leftarrow\mathrm{R}_{x_{t}}\bigg(-\varpi\sum_{i\in\mathcal{S}_{t}}\frac{1}{p_{i}N}\alpha_{t}\zeta_{t,K}^{i}\bigg)\hbox{ with $\varpi>0$ the global step size},$ (AGS-AP) $$

which ensures that the algorithm correctly solves the original problem $\min_{x\in\mathcal{M}}F(x)$.

On the other hand,
in practical applications, the server is actually unaware of the true probabilities. In this case, what the server can do is to estimate the true probabilities as possible in some ways, that is, the server computes $q_{t}^{i}$ in the $t$-th round of communication and uses it to serve as the true probability $p_{i}$.
Summarizing above, this paper proposes a Riemannian FL algorithm, called RFedAGS, which can address the partial participation setting, as stated in Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1).

###### Assumption 2.1 .

###### Theorem 2.1 (Proved in Appendix E.1 ) .

## 3 Convergence Analysis

In this section, we establish the convergence properties of RFedAGS (Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1)) on the partial participation and the non-I.I.D. data settings. All of the proofs can be found in Appendix [D](https://arxiv.org/html/2409.07223v2#A4).

### 3.1 Assumptions

We first present a set of assumptions as follows that are necessary for the convergence analysis. All assumptions except Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) have been used
in e.g., [Bon13, TFBJ18, SKM19, HG21], and their reasonability is discussed in Appendix [C](https://arxiv.org/html/2409.07223v2#A3).

###### Assumption 3.1 .

The retraction $\mathrm{R}$ is such that its restriction to $\mathrm{T}_{x}\mathcal{M}$ for all $x\in\mathcal{M}$, $\mathrm{R}_{x}$, is of class $C^{2}$, and the associated vector transport $\mathcal{T}$ is continuous and bounded in the sense that there exists a constant $\Upsilon>0$ such that for any $x\in\mathcal{M}$, $\zeta_{x},\eta_{x}\in\mathrm{T}_{x}\mathcal{M}$, it holds that $\|\mathcal{T}_{\eta_{x}}(\zeta_{x})\|\leq\Upsilon\|\zeta_{x}\|$.

###### Assumption 3.2 .

For a sequence of the outer iterates $\{x_{t}\}_{t\geq 1}$ and a sequence of the inner iterates $\{\{\{x_{t,k}^{j}\}_{j=1}^{N}\}_{k=0}^{K-1}\}_{t\geq 1}$ generated by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1), there exists a $W$-totally retractive set $\mathcal{W}\subset\mathcal{M}$
such that $\{x_{t}\}_{t\geq 1}\subset\mathcal{W}$ and $\{\{\{x_{t,k}^{j}\}_{j=1}^{N}\}_{k=0}^{K-1}\}_{t\geq 1}\subset\mathcal{W}$. The minimizers of Problem ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)) are inside $\mathcal{W}$.
Additionally, there exists a
compact and connected set $\mathcal{X}\subset\mathcal{M}$ such that $\mathcal{W}\subset\mathcal{X}$.

###### Assumption 3.3 .

The cost function $F$ is continuously differentiable in $\mathcal{W}$, the local cost functions $f_{1},\dots,f_{N}$ are continuously differentiable in $\mathcal{W}$, and their components $f_{j}(\cdot,\xi)$ for $\xi\sim\mathcal{D}_{j}$ with $j\in[N]$ are continuously differentiable in $\mathcal{W}$.

###### Assumption 3.4 .

The local objective functions $f_{j}$, $j\in[N]$, are $L_{f}$-Lipschitz continuously differentiable in $\mathcal{W}$ with the retraction $\mathrm{R}$ and the vector transport $\mathcal{T}$ (see Definition [B.1](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition1)), implying that $F$ is also $L_{f}$-Lipschitz continuously differentiable.

###### Assumption 3.5 .

$F$ is $L_{g}$-retraction smooth over $\mathcal{W}$ with respect to $\mathrm{R}$ (see Definition [B.2](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition2)).(^1^11In general, in the Riemannian setting, a $L$-Lipschitz continuously differentiable function $f:\mathcal{M}\rightarrow\mathbb{R}$ is not necessarily $L$-retraction smooth, which is different from the Euclidean setting.)

###### Assumption 3.6 .

For any parameter $x\in\mathcal{M}$, the Riemannian stochastic gradient $\mathrm{grad}f_{j}(x;\xi^{j})$ is an unbiased estimator of the gradient $\mathrm{grad}f_{j}(x)$, i.e., $\mathbb{E}_{\xi^{j}}[\mathrm{grad}f_{j}(x;\xi^{j})]=\mathrm{grad}f_{j}(x)$, $\forall j\in[N]$.

###### Assumption 3.7 .

For any fixed parameter $x\in\mathcal{M}$, there exists a positive constant $\sigma_{L}$ such that for all $j\in[N]$, it holds that
$\mathbb{E}[\|\frac{1}{B}\sum_{b\in\mathcal{B}^{j}}\mathrm{grad}f_{j}(x;\xi^{j}_{b})-\mathrm{grad}f_{j}(x)\|^{2}]\leq\frac{\sigma_{L}^{2}}{B}$ with $|\mathcal{B}^{j}|=B$.

The method estimating the probabilities is discussed in Section [3.3](https://arxiv.org/html/2409.07223v2#S3.SS3). Now we just make an assumption requiring that the approximate probability $q_{t}^{i}$ in each round of communication is not far away from the true probability $p_{i}$, formally stated in Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8).

###### Assumption 3.8 .

There exist constants $q_{\min},q_{\max}\in(0,1]$ and $G\geq 0$ independent of $t\geq 1$ and $i\in[N]$, such that the approximate probabilities $q_{t}^{i}$’s satisfy
$\left|\frac{1}{q_{t}^{i}}-\frac{1}{p_{i}}\right|\leq\sqrt{G\alpha_{t}}$, and $q_{\min}\leq q_{t}^{i}\leq q_{\max},\forall t\geq 1,i\in[N]$,
where $\alpha_{t}$ is the local step size in the $t$-th round of communication.

Note that the constant $G$ controls the accuracy of the approximate probabilities and when the true probabilities are available to the server, $G$ can take exactly zero. In Section [3.3](https://arxiv.org/html/2409.07223v2#S3.SS3), we discuss the reasonability of Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8).

###### Remark 3.1 .

In [WJ24], the authors imposed the following bound on the approximate probabilities:
$\sum_{i=1}^{N}p_{i}^{2}\left(\frac{1}{q_{t}^{i}}-\frac{1}{p_{i}}\right)^{2}\leq\frac{N}{81}$. This bound essentially requires that $|\frac{1}{q_{t}^{i}}-\frac{1}{p_{i}}|$ is less than some constant, which is consistent with Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) in fixed step size cases. Note that this assumption is considered in [WJ24] only for fixed step size cases, but Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) considers another situation where the bound varies over time $t$ when decaying step sizes are used.

###### Assumption 3.1 .

###### Assumption 3.2 .

###### Assumption 3.3 .

###### Assumption 3.4 .

###### Assumption 3.5 .

###### Assumption 3.6 .

###### Assumption 3.7 .

###### Assumption 3.8 .

###### Remark 3.1 .

### 3.2 Convergence properties

In this section, we establish the convergence properties of the proposed RFedAGS.

###### Theorem 3.1 .

Let Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) hold. Suppose Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) is run with a fixed global step size $\varpi>0$ and a decaying local step size sequence $\{\alpha_{t}\}$ satisfying Conditions

$$ $\sum_{t=1}^{\infty}\alpha_{t}=\infty,\sum_{t=1}^{\infty}\alpha_{t}^{2}<\infty.$ (3.1) $$

Then, $\liminf_{t\rightarrow\infty}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]=0.$

In what follows, we further characterize the nonasymptotic convergence.

###### Theorem 3.2 .

Under the same conditions as Theorem [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem1) except that the local step size sequence $\{\alpha_{t}\}$ is determined by $\alpha_{t}=\frac{\alpha_{0}}{(\beta+t)^{p}}$ with constants $\alpha_{0},\beta>0$ and $p\in(1/2,1]$ satisfying $\varpi\alpha_{1}KL_{g}\leq 1$, the weighted average norm of the squared gradients satisfy, with $A_{T}=\sum_{t=1}^{T}\alpha_{t}$,

$$ $\displaystyle\frac{1}{A_{T}}\sum_{t=1}^{T}\alpha_{t}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\begin{cases}\mathcal{O}(\frac{1}{\ln(\beta+T)})&p=1,\\ \mathcal{O}(\frac{1}{(\beta+T)^{1-p}})&p\in(1/2,1).\end{cases}$ $$

###### Remark 3.2 .

In particular, if the full agent participate in any round of communication and agents use the full local gradient in local update, i.e., $G=0$ and $\sigma_{L}=0$, one can relax the step sizes to $\alpha_{t}=\frac{\alpha_{0}}{(\beta+t)^{p}}$ where $p=1/3+a$ with $a\in(0,2/3)$. In this case, for large $T$, the upper bound can be improved to $\frac{1}{A_{T}}\sum_{t=1}^{T}\alpha_{t}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\mathcal{O}(\frac{1}{(\beta+T)^{{2}/{3}-a}})$ (see Appendix [D.3](https://arxiv.org/html/2409.07223v2#A4.SS3)).

###### Theorem 3.3 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8), suppose that $F$ satisfies RPL condition, i.e., there exists a constant $\mu>0$, such that for all $x\in\mathcal{W}$, it holds that
$F(x)-F(x^{*})\leq\frac{1}{2\mu}\|\mathrm{grad}F(x)\|^{2}$.
If we run Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with the batch size $B_{t}\in[B_{\mathrm{low}},B_{\mathrm{up}}]$ and the step sizes satisfying

$$ $\displaystyle\alpha_{t}=\frac{\beta}{\gamma+t}\hbox{ for some $\gamma>0$ and $\beta>\frac{1}{\mu\varpi K}$ such that $\alpha_{1}\varpi KL_{g}\leq 1$},$ $$

then the iterates $\{x_{t}\}_{t\geq 1}$ satisfy

$$ $\displaystyle\mathbb{E}[F(x_{t})]-F(x^{*})\leq\frac{\nu}{\gamma+t},\;\hbox{ and }\;\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\frac{2L_{g}\nu}{\gamma+t},$ (3.2) $$

where $\nu=\max\left\{\frac{\varpi K\beta^{2}Q(K,B_{\mathrm{low}},\alpha_{1},\varpi)}{\beta\mu\varpi K-1},(\gamma+1)\Theta(x_{1})\right\}$, $\Theta(x_{1})=F(x_{1})-F(x^{*})$, and $Q(K,B_{t},\alpha_{t},\varpi)=(2K-1)(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\alpha_{t}/{6}+GP^{2}\delta_{2}^{2}+\Upsilon^{2}P^{2}\delta_{4}^{2}KL_{g}\varpi+\frac{L_{g}\delta^{2}_{3}\sigma_{L}^{2}\Upsilon^{2}\varpi}{2B_{t}}$ with $P,J$, and $H$ being three constants depended on the problem, manifold and the retraction and $\delta_{1},\delta_{2},\delta_{3},\delta_{4}$ being constants depended on $q_{t}^{i},p_{i}$,$\forall i\in[N]$. That is, Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) converges sublinearly to the minimizer in expectation.

Theorems [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem1)-[3.3](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem3) provide the global convergence of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1). Under mild assumptions, the first theorem states that Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) has global convergence in expectation for general objectives while the other theorems further provide the convergence rate of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1). However, all of these theorems require the usage of the decaying step sizes. When decaying step sizes are used, a large number of iteration are required for Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) to converge. A compromise is to use a fixed step size of moderate size, the advantage of which is that the convergence rate is sublinear (even linear) while the disadvantage of which is that it may not converge to the minimizers but to an $\epsilon$-stationary point/solution (see Definition [B.4](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition4)); see Theorems [3.4](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem4) and [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem5).

###### Theorem 3.4 .

Suppose that Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) hold. We run Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with a fixed global step size $\varpi$, a fixed batch size $B$, and a fixed number of local updates $K$.

- 1.
If the fixed step sizes $\alpha$ and $\varpi$ satisfy $\alpha\varpi KL_{g}\leq 1$, then
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]$
$\displaystyle\leq\frac{2\Theta(x_{1})}{\varpi\alpha KT}+{2\alpha Q(K,B,\alpha,\varpi)}.$
(3.3)
- 2.
If the true probabilities are known, meaning $G=0$, and
one takes local and global step sizes $\alpha$ and $\varpi$ such that $\alpha\varpi=\sqrt{\frac{\Theta(x_{1})B}{(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)\Upsilon^{2}L_{g}KT}}$ with $T$ satisfying
$T\geq\max\bigg\{\frac{KL_{g}\Theta(x_{1})B}{(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)\Upsilon^{2}},$
$\frac{\Theta(x_{1})(2K-1)^{2}(K-1)^{2}L_{f}^{4}\delta_{1}^{4}P^{4}(L_{g}^{2}\varpi^{2}J^{2}K^{2}+P^{2}H^{2})^{2}B^{3}}{9(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)^{3}\Upsilon^{6}L_{g}^{7}\varpi^{6}K^{5}}\bigg\},$
then
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq 4\Upsilon\sqrt{L_{g}\Theta(x_{1})\left(\frac{\delta_{3}^{2}\sigma_{L}^{2}}{KTB}+\frac{2P^{2}\delta_{4}^{2}}{T}\right)}.$

###### Remark 3.3 .

If the probabilities $p_{i}$ are known, i.e., $q_{t}^{i}=p_{i}$, and $p_{\min}=\min_{i}\{p_{i}\}$ is not too small and not fairly far away from $p_{\max}=\max_{i}\{p_{i}\}$, such that the constants $\delta_{1}^{2},\delta_{2}^{2},\delta_{3}^{2},\delta_{4}^{2}$ are

$$ $\displaystyle\delta_{1}^{2}=\frac{1}{N}\sum_{j=1}^{N}\left(\frac{p_{j}}{q_{t}^{j}}\right)=1,\delta_{2}^{2}=\sum_{j=1}^{N}\frac{p_{j}^{2}}{N}\leq 1,\delta_{3}^{2}=\frac{1}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}}{(q_{t}^{j})^{2}}\leq\frac{1}{Np_{\min}},\;\delta_{4}^{2}=\sum_{j=1}^{N}\frac{(1-p_{j})}{N^{2}p_{j}}\leq\frac{1}{Np_{\min}},$ $$

then, Item [2](https://arxiv.org/html/2409.07223v2#S3.I1.i2) gives the upper bound as $\mathcal{O}(\frac{1}{\sqrt{p_{\min}NKTB}})+\mathcal{O}(\frac{1}{\sqrt{p_{\min}NT}})$.
In particular, if the probabilities are the same across agents, e.g., $p_{i}=\frac{S}{N}$ with $S\leq N$, then $\delta^{2}_{3}=\frac{1}{S}$, and $\delta^{2}_{4}=\frac{N-S}{NS}\leq\frac{1}{S}$. It follows that Item [2](https://arxiv.org/html/2409.07223v2#S3.I1.i2) gives the upper bounds as $\mathcal{O}(\frac{1}{\sqrt{SKTB}})+\mathcal{O}(\frac{1}{\sqrt{ST}})$. The bound of $\mathcal{O}(\frac{1}{\sqrt{ST}})$ matches with the existing result for FedAvg given in [KKM^+20, Theorem 1] and improves by $\frac{1}{\sqrt{K}}$ over that given in [YFL21, Corollary 2].

###### Theorem 3.5 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8), suppose that $F$ satisfies RPL condition with a constant $\mu>0$. If we run Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with batch size $B_{t}\in[B_{\mathrm{low}},B_{\mathrm{up}}]$ and step sizes $\alpha_{t}=\alpha$ and $\varpi$ satisfying $\alpha\varpi K\leq\min\{1/L_{g},1/\mu\}$,
then the resulting iterates $\{x_{t}\}_{t=1}^{T}$ satisfy

$$ $\displaystyle\mathbb{E}[F(x_{T})]-F(x^{*})$ $\displaystyle\leq(1-\mu\varpi K\alpha)^{T-1}\Theta(x_{1})+\frac{\alpha}{\mu}Q(K,B_{\mathrm{low}},\alpha,\varpi)\xrightarrow[]{T\rightarrow\infty}\frac{\alpha}{\mu}Q(K,B_{\mathrm{low}},\alpha,\varpi).$ (3.4) $$

From Theorem [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem5), if one lets $T\rightarrow\infty$, then the expected optimality gaps $\{\mathbb{E}[F(x_{T})]-F(x^{*})\}$ are bounded from above by $\frac{\alpha}{\mu}Q(K,B_{\mathrm{low}},\alpha,\varpi)$, which implies that any accumulation point of the sequence of iterates $\{x_{t}\}$ generated by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) is a $\epsilon$-solution if taking $\alpha\leq\frac{\epsilon\mu}{Q(K,B_{\mathrm{low}},\alpha,\varpi)}$. Smaller $\alpha$ means smaller upper bound as well as slower convergence speed.

###### Remark 3.4 .

Similar to the Euclidean setting, the RPL property is weaker than the strong retraction-convexity. In fact, if the objective $f:\mathcal{M}\rightarrow\mathbb{R}$ is $\mu$-strongly retraction-convex, then it also satisfies the RPL property with parameter $\mu$ (proved in Appendix [E.2](https://arxiv.org/html/2409.07223v2#A5.SS2)). Therefore, Theorems [3.3](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem3) and [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem5) also hold under strong retraction-convexity.

###### Theorem 3.1 .

###### Theorem 3.2 .

###### Remark 3.2 .

###### Theorem 3.3 .

###### Theorem 3.4 .

###### Remark 3.3 .

###### Theorem 3.5 .

###### Remark 3.4 .

### 3.3 Estimating the participation probabilities

At the $t$-th round of communication, let $\mathcal{S}_{t}$ denote the set of participating agents. Then, under Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1), $\mathbb{I}_{\mathcal{S}_{t}}(i)$ follows the Bernoulli distribution, i.e., $\mathbb{I}_{\mathcal{S}_{t}}(i)\sim\mathrm{Bernoulli}(p_{i})$. At each round of communication, for each agent $i$, whether it participates in communication can be regarded as a Bernoulli trial. Therefore, by Bernoulli’s Large Number Theorem, the frequency of agent $i$ participating in communication goes closely to the true probability $p_{i}$ as the growth of $t$, the number of communications. Formally, let $\mathfrak{q}_{t}^{i}=\sum_{\tau=1}^{t}\mathbb{I}_{\mathcal{S}_{\tau}}(i)$, and compute the approximate probability by $q_{t}^{j}=\mathfrak{q}_{t}^{j}/t$. Then we have $\lim_{t\rightarrow\infty}\mathbb{P}\{|q_{t}^{i}-p_{i}|\leq\epsilon\}=1$ for any small $\epsilon>0$. This justifies the use of frequencies to estimate probabilities.
The next theorem shows that Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) holds with high probability when the step size takes the form of $\alpha_{t}=\mathcal{O}(t^{-a})$ with $a\in(1/2,1]\cup\{0\}$.

###### Theorem 3.6 (Proved in Appendix D.7 ) .

Under Assumption [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmassumption1), for each agent $i$, we have

$$ $\displaystyle\mathbb{P}\left\{\left|\frac{1}{q_{t}^{i}}-\frac{1}{p_{i}}\right|\leq\mathcal{G}t^{-\frac{a}{2}}\right\}\geq 1-\min\left\{2e^{-\frac{tp_{i}^{2}}{2}},\frac{4(1-p_{i})}{tp_{i}}\right\}-\min\left\{2e^{-\frac{\mathcal{G}^{2}p_{i}^{4}}{2}t^{1-a}},\frac{4(1-p_{i})}{\mathcal{G}^{2}p_{i}^{3}t^{1-a}}\right\},$ (3.5) $$

where $q_{t}^{i}=\sum_{\tau=1}^{t}\mathbb{I}_{\mathcal{S}_{\tau}}(i)/t$, and $\mathcal{G}\geq 0$ and $a\geq 0$ are constants.

In practice, taking $a=0$ leads to fixed step size cases or $a\in(1/2,1]$ to decaying step size cases. Therefore, it follows from Theorem [3.6](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem6) that Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) holds with probability not less than $1-\min\{2e^{-\frac{tp_{i}^{2}}{2}},\frac{4(1-p_{i})}{tp_{i}}\}-\min\{2e^{-\frac{\mathcal{G}^{2}p_{i}^{4}}{2}t^{1-a}},\frac{4(1-p_{i})}{\mathcal{G}^{2}p_{i}^{3}t^{1-a}}\}$ with a proper constant $\mathcal{G}\geq 0$. Large enough $t$ and properly chosen $\mathcal{G}$ make the probability high.

###### Theorem 3.6 (Proved in Appendix D.7 ) .

## 4 Experiments

Here we conduct numerical experiments on principal component analysis (PCA) over the Stiefel manifold, hyperbolic structured prediction (HSP) over the hyperbolic manifold, and the Fréchet mean computation (FMC) over the SPD manifold such that we can compare RFedAGS with existing RFL algorithms, including RFedAvg [LM23], RFedSVRG [LM23], and RFedProj [ZHSJ24] (used in PCA). Additionally, we still conduct two experiments on principal eigenvector computation and low-rank matrix completion shown in Appendices [A.1](https://arxiv.org/html/2409.07223v2#A1.SS1)-[A.2](https://arxiv.org/html/2409.07223v2#A1.SS2). The first one tests the comprehensive performance of RFedAGS, while the second compares RFedAGS with some existing centralized algorithms
showing the comparable availability of RFedAGS with those. The experiment settings in this section can be found in Appendix [A.3](https://arxiv.org/html/2409.07223v2#A1.SS3).

##### PCA.

The PCA problem has the form of

$$ $\displaystyle\min_{X\in\mathrm{St}(r,d)}F(X):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(X),\quad\hbox{ with }f_{i}(X)=-\frac{1}{S}\sum_{j=1}^{S}\mathrm{tr}(X^{T}(Z_{ij}Z_{ij}^{T})X),$ $$

where $\mathrm{St}(r,d)$ is the Stiefel manifold, $Z_{ij}Z_{ij}^{T}$ is the covariance matrix of local datum $Z_{ij}\in\mathbb{R}^{d\times p}$.
We generate $\mathcal{D}_{i}=\{Z_{ij}\}_{j=1}^{S}$ in two ways: (i) synthetic data by sampling from the Gaussian distribution $\mathcal{N}(0,\frac{i}{N})$ such that $\mathcal{D}_{i}$ are non-I.I.D; (ii) real-world data from CIFAR10 (^2^22See [https://www.cs.toronto.edu/ kriz/cifar.html](https://www.cs.toronto.edu/%C2%A0kriz/cifar.html).) dataset.
We can observe from Figure [1](https://arxiv.org/html/2409.07223v2#S4.F1) that our proposed RFedAGS outperforms the existing three RFL algorithms under the arbitrary participation setting in terms of accuracy of solutions and consumed time. This justifies the efficacy of the proposed RFedAGS.

Figure: (a) Synthetic data
Refer to caption: x1.png

It should be noted that the tools used in our RFedAGS are fairly general (as stated in Assumption [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)), however RFedAvg and RFedSVRG require more strict tools (the inverse of exponential and parallel transport) and RFedProj requires the orthogonal projector onto the manifold.
These requirements limit the application scope of RFedAvg, RFedSVRG, and RFedProj. For instance, RFedProj can not be used in the HSP and FMC problems below.

##### HSP.

Given a set of training pairs $\mathcal{D}=\{\mathcal{D}_{i}\}_{i=1}^{N}=\{\{(w_{i,j},y_{i,j})\}_{j=1}^{S}\}_{i=1}^{N}$, where $w_{i,j}\in\mathrm{R}^{r}$ is the feature and $y_{i,j}\in\mathcal{H}^{d}$ is the hyperbolic embedding of the class of $w_{i,j}$. Then for a test sample $w$, the task of HPS is to predict its hyperbolic embeddings by solving the following problem

$$ $\operatorname*{arg\,min}_{x\in\mathcal{H}^{d}}F(x):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x),\hbox{ with }f_{i}(x)=\frac{1}{S}\sum_{i=1}^{S}a_{i,j}(\omega)\mathrm{dist}^{2}(x,y_{i,j})$ $$

where the hyperbolic manifold $\mathcal{H}^{d}$ is characterized via the Lorentz hyperbolic model, and $[a_{1}(w),\dots,\\
a_{N}(w)]^{T}\in\mathbb{R}^{N\times S}$ is a parameter matrix. We use the WordNet (^3^33See [https://wordnet.princeton.edu/](https://wordnet.princeton.edu/).) dataset to test the algorithms.
From the reported Figure [2](https://arxiv.org/html/2409.07223v2#S4.F2), we can observe that the proposed RFedAGS outperforms both RFedAGS and RFedSVRG in terms of distance to the true point. Figure [2](https://arxiv.org/html/2409.07223v2#S4.F2) directly demonstrates this advantage of RFedAGS.

Figure: Figure 2: HSP with WordNet dataset. Here “primate” is the test sample (true point).
Refer to caption: x5.png

##### FMC.

Given a set of SPD matrices, $\mathcal{D}=\{\{X_{i,j}\}_{j=1}^{S}\}_{i=1}^{N}$, the FMC of these SPD matrices is the solution to the problem

$$ $\operatorname*{arg\,min}_{X\in\mathcal{S}_{++}^{n}}F(X):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(X)\hbox{ with }f_{i}(X)=\frac{1}{S}\sum_{i=1}^{S}\mathrm{dist}^{2}(X,X_{i,j}),$ $$

where $\mathrm{dist}(\cdot,\cdot)$ is the Riemannian distance.
We use the PATHMNIST (^4^44See [https://medmnist.com/](https://medmnist.com/).) dataset to test the algorithms.
From Figure [3](https://arxiv.org/html/2409.07223v2#S4.F3), we still observe that RFedAGS outperforms RFedAvg and RFedSVRG.

Figure: Figure 3: FMC with PATHMNIST dataset: RFedAGS consistently performs better than RFedAvg and RFedSVRG.
Refer to caption: x8.png

## 5 Conclusions

In this work, we propose a Riemannian FL algorithm, called RFedAGS, that addresses critical challenges caused by curvature effects of manifolds, the partial participation, and the heterogeneity data.
Unlike the commonly studied random sampling setting, RFedAGS accommodates a more practical and challenging scenario where agents’ participation statistics may be unknown.
Theoretically, we prove that the proposed RFedAGS, under decaying step sizes, achieves global convergence and provide sublinear convergence rate. When using a fixed step size, it attains sublinear—or even linear—convergence near a neighborhood of a stationary point/solution.
Numerical experiments we conducted have confirmed the efficacy of RFedAGS and in particular, it outperforms existing RFL algorithms methods on PCA, HSP, and FMC with synthetic and real-world data.
Current analyses on partial participation rely on time-invariant statistical assumptions. An important direction for future research is to analyze more realistic and complex scenarios, such as settings with time-varying participation probabilities.

## References

- [AMS08]
P.-A. Absil, R. Mahony, and Rodolphe Sepulchre.
Optimization Algorithms on Matrix Manifolds.
Princeton University Press, Princeton, 2008.
- [BAC19]
Nicolas Boumal, Pierre-Antoine Absil, and Coralia Cartis.
Global rates of convergence for nonconvex optimization on manifolds.
IMA Journal of Numerical Analysis, 39(1):1–33, 2019.
- [BCN18]
Léon Bottou, Frank E. Curtis, and Jorge Nocedal.
Optimization methods for large-scale machine learning.
SIAM Review, 60(2):223–311, 2018.
- [BMAS14]
N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre.
Manopt, a Matlab toolbox for optimization on manifolds.
Journal of Machine Learning Research, 15(42):1455–1459, 2014.
- [BN03]
Mikhail Belkin and Partha Niyogi.
Laplacian eigenmaps for dimensionality reduction and data representation.
Neural Computation, 15(6):1373–1396, 06 2003.
- [Bon13]
Silvere Bonnabel.
Stochastic gradient descent on Riemannian manifolds.
IEEE Transactions on Automatic Control, 58(9):2217–2229, 2013.
- [Boo75]
W. M. Boothby.
An introduction to differentiable manifolds and Riemannian geometry.
1975.
- [Bou23]
Nicolas Boumal.
An introduction to optimization on smooth manifolds.
Cambridge University Press, 2023.
- [Den12]
Li Deng.
The MNIST database of handwritten digit images for machine learning research.
IEEE Signal Processing Magazine, 29(6):141–142, 2012.
- [FO02]
OP Ferreira and PR Oliveira.
Proximal point algorithm on Riemannian manifolds.
Optimization, 51(2):257–270, 2002.
- [GHZH21]
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang.
Fast federated learning in the presence of arbitrary device unavailability.
In Advances in Neural Information Processing Systems, 2021.
- [GLHA23]
Xinran Gu, Kaifeng Lyu, Longbo Huang, and Sanjeev Arora.
Why (and when) does local SGD generalize better than SGD?
In International Conference on Learning Representations (ICLR), 2023.
- [HAG18]
Wen Huang, P.-A. Absil, and K. A. Gallivan.
A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems.
SIAM Journal on Optimization, 28(1):470–495, 2018.
- [HG21]
Andi Han and Junbin Gao.
Improved variance reduction methods for Riemannian non-convex optimization.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7610–7623, 2021.
- [HGA15]
Wen Huang, K. A. Gallivan, and P.-A. Absil.
A Broyden class of quasi-Newton methods for Riemannian optimization.
SIAM Journal on Optimization, 25(3):1660–1685, 2015.
- [HHJM24]
Zhenwei Huang, Wen Huang, Pratik Jawanpuria, and Bamdev Mishra.
Federated learning on Riemannian manifolds with differential privacy.
arXiv, arxiv.org/abs/2404.10029(v1), 2024.
- [HKMC19]
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe.
Local SGD with periodic averaging: Tighter analysis and adaptive synchronization.
In Advances in Neural Information Processing Systems (NeurIPS), 2019.
- [HMJG21]
Andi Han, Bamdev Mishra, Pratik Jawanpuria, and Junbin Gao.
On Riemannian optimization over positive definite matrices with the Bures-Wasserstein geometry.
In Advances in Neural Information Processing Systems, 2021.
- [HMJG24]
Andi Han, Bamdev Mishra, Pratik Jawanpuria, and Junbin Gao.
Differentially private Riemannian optimization.
Machine Learning, 113(3):1133–1161, 2024.
- [HW22]
Wen Huang and Ke Wei.
Riemannian proximal gradient methods.
Mathematical Programming, 194(1):371–413, 2022.
- [JM18]
Pratik Jawanpuria and Bamdev Mishra.
A unified framework for structured low-rank matrix learning.
In International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2254–2263. PMLR, 10–15 Jul 2018.
- [KKM^+20]
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.
Scaffold: Stochastic controlled averaging for federated learning.
In International conference on machine learning, pages 5132–5143. PMLR, 2020.
- [LHY^+20]
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.
On the convergence of FedAvg on non-iid data.
In International Conference on Learning Representations, 2020.
- [LM23]
Jiaxiang Li and Shiqian Ma.
Federated learning on Riemannian manifolds.
Applied Set-Valued Analysis and Optimization, 5(2):213–232, 08 2023.
- [LSZ^+20]
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks.
In Proceedings of Machine Learning and Systems, volume 2, pages 429–450, 2020.
- [Mag23]
German Magai.
Deep neural networks architectures from the perspective of manifold learning.
In 2023 IEEE 6th International Conference on Pattern Recognition and Artificial Intelligence (PRAI), pages 1021–1031. IEEE, 2023.
- [Mil95]
George A. Miller.
WordNet: A lexical database for English.
Commun. ACM, 38:39–41, 1995.
- [MKJS19]
Bamdev Mishra, Hiroyuki Kasai, Pratik Jawanpuria, and Atul Saroop.
A Riemannian gossip approach to subspace learning on Grassmann manifold.
Machine Learning, 108:1783 – 1803, 2019.
- [MMR^+17]
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data.
In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
- [NK17]
Maximilian Nickel and Douwe Kiela.
Poincaré embeddings for learning hierarchical representations.
Advances in Neural Information Processing Systems, 2017.
- [RVdV23]
Mónica Ribero, Haris Vikalo, and Gustavo de Veciana.
Federated learning under intermittent client availability and time-varying communication constraints.
IEEE Journal of Selected Topics in Signal Processing, 17(1):98–111, 2023.
- [RVS22]
Elsa Rizk, Stefan Vlaski, and Ali H. Sayed.
Federated Learning Under Importance Sampling.
IEEE Transactions on Signal Processing, 70:5381–5396, 2022.
- [SKM19]
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra.
Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport.
SIAM Journal on Optimization, 29(2):1444–1472, 2019.
- [Sti19]
Sebastian U. Stich.
Local SGD converges fast and communicates little.
In International Conference on Learning Representations (ICLR), 2019.
- [TFBJ18]
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael I Jordan.
Averaging stochastic gradient descent on Riemannian manifolds.
In Conference On Learning Theory, pages 650–687. PMLR, 2018.
- [TPM06]
Oncel Tuzel, Fatih Porikli, and Peter Meer.
Region covariance: A fast descriptor for detection and classification.
In European conference on computer vision, pages 589–600. Springer, 2006.
- [WJ21]
Jianyu Wang and Gauri Joshi.
Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms.
Journal of Machine Learning Research, 22(213):1–50, 2021.
- [WJ22]
Shiqiang Wang and Mingyue Ji.
A unified analysis of federated learning with arbitrary client participation.
In Advances in Neural Information Processing Systems, volume 35, pages 19124–19137. Curran Associates, Inc., 2022.
- [WJ24]
Shiqiang Wang and Mingyue Ji.
A lightweight method for tackling unknown participation statistics in federated averaging.
In International Conference on Learning Representations, 2024.
- [XCNS22]
Bo Xiong, Michael Cochez, Mojtaba Nayyeri, and Steffen Staab.
Hyperbolic embedding inference for structured multi-label prediction.
Advances in Neural Information Processing Systems, 35:33016–33028, 2022.
- [XIY^+23]
Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, and Lili Su.
Towards bias correction of FedAvg over nonuniform and time-varying communications.
In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 6719–6724, 2023.
- [XIY^+25]
Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, and Lili Su.
Empowering federated learning with implicit gossiping: Mitigating connection unreliability amidst unknown and arbitrary dynamics.
IEEE Transactions on Signal Processing, 73:766–780, 2025.
- [XYW24]
He Xiao, Tao Yan, and Kai Wang.
Riemannian SVRG using Barzilai–Borwein method as second-order approximation for federated learning.
Symmetry, 16(9):1101, 2024.
- [XYZ25]
He Xiao, Tao Yan, and Shimin Zhao.
Riemannian SVRG with Barzilai-Borwein scheme for federated learning.
Journal of Industrial and Management Optimization, 21(2):1546–1567, 2025.
- [YFL21]
Haibo Yang, Minghong Fang, and Jia Liu.
Achieving linear speedup with partial worker participation in non-iid federated learning.
In International Conference on Learning Representations, 2021.
- [YND^+23]
Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Shaojie Tang, Qinya Li, Fan Wu, Chengfei Lyu, Yanghe Feng, and Guihai Chen.
Federated optimization under intermittent client availability.
INFORMS Journal on Computing, 36(1):1185–202, 2023.
- [YSW^+23]
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni.
Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification.
Scientific Data, 10(1):41, 2023.
- [YYZ19]
Hao Yu, Sen Yang, and Shenghuo Zhu.
Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning.
In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5693–5700, 2019.
- [YZ21]
Haishan Ye and Tong Zhang.
DeEPCA: Decentralized exact PCA with linear convergence rate.
Journal of Machine Learning Research, 22(238):1–27, 2021.
- [ZC18]
Fan Zhou and Guojing Cong.
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization.
In International Joint Conference on Artificial Intelligence, 2018.
- [ZHSJ24]
Jiaojiao Zhang, Jiang Hu, Anthony Man-Cho So, and Mikael Johansson.
Nonconvex federated learning on compact smooth submanifolds with heterogeneous data.
In Advances in Neural Information Processing Systems, volume 37, pages 109817–109844. Curran Associates, Inc., 2024.
- [ZS16]
Hongyi Zhang and Suvrit Sra.
First-order methods for geodesically convex optimization.
In Conference on learning theory, pages 1617–1638. PMLR, 2016.
- [ZS21]
Xiaojing Zhu and Hiroyuki Sato.
Cayley-transform-based gradient and conjugate gradient algorithms on Grassmann manifolds.
Advances in Computational Mathematics, 47:1–28, 2021.

## Appendix A Experiment settings and additional experiment results

In this section, we supplement the numerical experiments conducted to demonstrate the performance of RFedAGS (Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1)) on non-I.I.D. data setting.
We focus on empirical minimization of ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)).

The decaying local step size is determined by the following formula

$$ $\displaystyle\alpha_{t}=\begin{cases}\alpha_{0}&\hbox{ if }t=0,\\ \frac{\alpha_{0}}{\beta+c_{t}}&\hbox{ if }t\geq 1,\end{cases}\hbox{ with }c_{t}=\begin{cases}0&\hbox{ if }t=0,\\ c_{t-1}+1&\hbox{ if }\mathrm{mod}(t,\mathrm{d})=0,\\ c_{t-1}&\hbox{ otherwise},\end{cases}$ $$

where $\alpha_{0}$ and $\beta$ are two positive constants, and $\mathrm{d}$ is a positive constant integer, which results in the step size decaying once after each $\mathrm{d}$ iterations. Optimality gap defined as $F(x_{t})-F(x^{*})$ with $x^{*}\in\operatorname*{arg\,min}_{x\in\mathcal{W}}F(x)$ is a commonly-used measure to evaluate the performance of algorithms.
In all experiments, the global step size is set as $1$.
The CPU time consists of the server computation time and the local computation time of active agents, without the communication time between the server and agents.
Unless otherwise specified, frequencies are used in Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) to estimate the true probabilities.
All of algorithms involved in our experiments are implemented built on Manopt [BMAS14].
All of the experiments are conducted under Windows 11 and MATLAB R2024b running on a laptop (Intel(R) Core(TM) i7-1165G7 CPU @2.80GHz, 16.0G RAM).

### A.1 Comprehensive tests

Consider the principal eigenvector computation (PEC) problem over the sphere manifold, formulated as follows

$$ $\displaystyle\min_{x\in\mathbb{S}^{n-1}}F(x):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x),\hbox{ with }f_{i}(x)=-\frac{1}{S}\sum_{j=1}^{S}x^{T}z_{i,j}z_{i,j}^{T}x,$ (A.1) $$

where $\mathbb{S}^{n-1}=\{x\in\mathbb{R}^{n}:x^{T}x=1\}$ is the sphere manifold, $\mathcal{D}_{i}=\{z_{i,1},\dots,z_{i,S}\}$ is the local samples held by agent $i$. Problem ([A.1](https://arxiv.org/html/2409.07223v2#A1.E1)) is in the form of finite sum minimization of ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)).

The sphere manifold $\mathbb{S}^{n-1}$ is viewed as a Riemannian embedded submanifold of $\mathbb{R}^{n}$, that is, the Riemannian metric is induced by the Euclidean metric: $\left<\xi,\eta\right>_{x}=\xi^{T}\eta$ for all $\xi,\eta\in\mathrm{T}_{x}\mathbb{S}^{n-1}$. The exponential mapping is chosen as the Retraction and the parallel transport along the geodesic correspondingly is selected as the isometric vector transport. The MNIST dataset [Den12] (^5^55See [https://yann.lecun.com/exdb/mnist/](https://yann.lecun.com/exdb/mnist/).) consists of 60000 hand-written gray images of size $28\times 28$ each of which is associated with a label taking values from 0 to $9$. In our experiments, each image is concatenated into a 784-dimensional column vector by column. In addition, to test the effectiveness of the proposed RFedAGS under the heterogeneity data setting, according to the FL setting, the MNIST dataset is shuffled into different levels of heterogeneity following the way in [MMR^+17]. Figure [4](https://arxiv.org/html/2409.07223v2#A1.F4) demonstrates histograms of the MNIST dataset with three different levels of heterogeneity.

Figure: (a) Non-I.I.D. (heavy)
Refer to caption: x10.png

#### A.1.1 Comparison of two aggregation patterns

First we demonstrate the importance of the aggregation pattern ([AGS-AP](https://arxiv.org/html/2409.07223v2#S2.Ex7)). As shown in ([2.1](https://arxiv.org/html/2409.07223v2#S2.E1)), the aggregation of RFedAGS in Line [16](https://arxiv.org/html/2409.07223v2#alg1.l16) of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) actually is unbiased in the sense of $\mathbb{E}\left[\sum_{i\in\mathcal{S}_{t}}\frac{1}{p_{i}N}\mathrm{grad}f_{i}(x)\right]=\mathrm{grad}F(x)$. Nevertheless, if the participation probabilities are not considered and the usual aggregation, $x_{t+1}\leftarrow\mathrm{R}_{x_{t}}\left(-\varpi\sum_{j\in\mathcal{S}_{t}}\frac{1}{|\mathcal{S}_{t}|}\zeta_{t,K}^{j}\right)$, is used, then the output of the algorithm equipped with this aggregation will tend towards a minimizer of another objective function different from the original objective when there exist $i,j\in[N]$ such that $p_{i}\not=p_{j}$, which exactly is what Theorem [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmtheorem1) points out.

Figure: (a) Fixed step size
Refer to caption: x13.png

Figure [5](https://arxiv.org/html/2409.07223v2#A1.F5) reports the experiment results, where the two curves “True” and “Approximating” adopt the aggregation pattern ([AGS-AP](https://arxiv.org/html/2409.07223v2#S2.Ex7)), the curve “Approximating” uses the frequency to estimate the true probability, and the curve “Biased” uses the usual aggregation ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)). Besides, the participation probabilities $p_{i}$’s are uniformly and randomly generated (i.e., $p_{i}$, $i\in[N]$, follows the uniform distribution $\mathrm{U}(0,1)$), the fixed step size is set as $\alpha=8.0\times 10^{-5}$, the parameters for decaying steps sizes are set as $(\alpha_{0},\beta,\mathrm{d})=(3.5\times 10^{-4},0.1,20)$, batch size is $B=0.5S$, and the number of local updates is set as $K=5$.
It is observed from Figure [5](https://arxiv.org/html/2409.07223v2#A1.F5) that RFedAGS equipped with the aggregation pattern ([AGS-AP](https://arxiv.org/html/2409.07223v2#S2.Ex7)) gives a better solution to Problem ([A.1](https://arxiv.org/html/2409.07223v2#A1.E1)) than
that generated by RFedAGS equipped with the usual aggregation pattern ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)). The reason lies on that the usual aggregation pattern ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) leads the iterates to the minimizer of $\tilde{F}:=\sum_{i=1}^{N}\tilde{p}_{i}f_{i}$ with $\tilde{p}_{i}=p_{i}\int_{0}^{1}\prod_{j\not=i}^{N}(1-p_{j}+p_{j}t)\mathrm{d}t$, as stated by Theorem [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmtheorem1). Meanwhile, due to $p_{i}\not=p_{j}$ for some $i,j\in[N]$, it follows that there exists no $\chi>0$ such that $\tilde{F}=\chi\cdot F$. Hence, the minimizers of $\tilde{F}$ may be not consistent with those of $F$.

Figure: (a) Fixed step size
Refer to caption: x15.png

Furthermore, Figure [6](https://arxiv.org/html/2409.07223v2#A1.F6) shows the curves of optimality gap v.s. iterations for the re-weighted objective $\tilde{F}$ valued at the iterates given in Figure [5](https://arxiv.org/html/2409.07223v2#A1.F5). Combining Figures [5](https://arxiv.org/html/2409.07223v2#A1.F5) and [6](https://arxiv.org/html/2409.07223v2#A1.F6), we conclude that RFedAGS equipped with the aggregation pattern ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)) does solve the re-weighted problem $\operatorname*{arg\,min}_{x\in\mathcal{M}}\tilde{F}(x)$ rather than the original problem.

#### A.1.2 Comparisons of different participation schemes

Here we consider the special case where each agents participates in any round of communication with the same participation probability, i.e., $p_{i}=p_{j}$ with $i,j\in[N]$. In this case, the random sampling scheme is denoted by Scheme I, while our arbitrary participation scheme is denoted by Scheme II, where we use frequencies to estimate the true probabilities.
For Scheme I, the sampling rate (the ratio of the number of sampled agents to the number of total agents) is as $\rho=0.3$ ($0.5$, or $0.7$). For Scheme II, the participation probability agent $i$ is respectively set as $p_{i}=0.3$ ($0.5$, or $0.7$) for all $i\in[N]$ such that the number of participating agents in Scheme II is equivalent to that of Scheme I in expectation, which means $\sum_{i=1}^{N}p_{i}=\rho N$.
The fixed step size is set $\alpha=8\times 10^{-5}$, the parameters for decaying step sizes are set as $(\alpha_{0},\beta,\mathrm{d})=(3.5\times 10^{-4},0.1,20)$, batch size is $B=0.5S$, and the number of local updates is set as $K=5$.
As demonstrated in Figure [7](https://arxiv.org/html/2409.07223v2#A1.F7), the performance of two participation schemes are extremely the same. This indicates that Scheme I can be viewed as a special case of our participation scheme and that using frequencies to estimate the true probabilities is sufficient to ensure convergence.

Figure: (a) Fixed step size
Refer to caption: x17.png

Next, we simulate the scenario of straggling agent participation. Suppose that the first three agents are stragglers and make their local computation time become 10 times as much as that under normal conditions. Specifically, for Scheme I, if one of the three stragglers are chosen, then its local computational time becomes 10 times as much as that under normal conditions; for Scheme II, setting the stragglers’ participation probabilities as $0.05$ ensures that they rarely participate in local updates, and when one of the stragglers responds to the server, its local computational also becomes 10 times as much as that under normal conditions. The participation probabilities of the other agents are properly set such that $\sum_{i=1}^{N}p_{i}\approx\rho N$.
The fixed step size is set $\alpha=8\times 10^{-5}$, the parameters for decaying step sizes are set as $(\alpha_{0},\beta,\mathrm{d})=(2.8\times 10^{-4},0.1,20)$, batch size is $B=0.5S$, and the number of local updates is set as $K=5$.
The experiment results are shown in Figure [8](https://arxiv.org/html/2409.07223v2#A1.F8).

Figure: (a) Fixed step size
Refer to caption: x21.png

By the definition of Scheme I, each agent is sampled with probability $\rho$ (e.g., 0.3 and 0.5 in our experiments), which is much greater than $0.05$ in Scheme II for the three stragglers. Hence, the number of stragglers participating local updates of Scheme I is greater than the one of Scheme II, leading to the CPU time of Scheme I are greater than the one of Scheme II. The results in Figure [8](https://arxiv.org/html/2409.07223v2#A1.F8) is consistent with our analysis. Meanwhile we note that the performance of using the true probabilities and frequencies is extremely the same, which indicates again the validity of using frequencies serving as the true probabilities.

It should be noted that in a practical situation, if some agents do not respond to the server in a certain round of communication, then scheme I may not work in this case, because one of these agents may be sampled by the server, but it will not respond to the server. This will cause the algorithm to stagnate. Nevertheless, Scheme II does not encounter this issue since the server does not choose the agents which do not respond.

#### A.1.3 Influence of the level of heterogeneity data on performance

Next we test the impact of the heterogeneity level of the MNIST dataset on the performance of RFedAGS. Here the participation probabilities $p_{i}$’s are uniformly and randomly generated, that is, $p_{i}\sim\mathrm{U}(0,1)$ for $i\in[N]$.
The fixed step size is set $\alpha=8\times 10^{-5}$, the parameters for decaying step sizes are set as $(\alpha_{0},\beta,\mathrm{d})=(2.8\times 10^{-4},0.1,20)$, batch size is $B=0.5S$, and the number of local updates is set as $K=5$. The experiment results are reported in Figure [9](https://arxiv.org/html/2409.07223v2#A1.F9), where we observe that the quality of the solution generated by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) gets worse as the growth of the levels of heterogeneity of the training data across agents. Additionally, Theorems [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem1) and [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem2) point out that if decaying step sizes satisfying ([3.1](https://arxiv.org/html/2409.07223v2#S3.E1)) are used, Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) has global convergence. Hence, it is expected that the higher-quality solutions may be found when using decaying step sizes and running more rounds of communication compared with the case using a fixed step size. This is consistent with the experiment results as shown in Figure [7](https://arxiv.org/html/2409.07223v2#A1.F7)-Figure [9](https://arxiv.org/html/2409.07223v2#A1.F9).

Figure: (a) Fixed step size
Refer to caption: x25.png

#### A.1.4 Effect of local multiple-step update

In addition, we test the impact of different number of local updates $K$ on the performance of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1).
The participation probabilities $p_{i}$’s are uniformly and randomly generated, that is, $p_{i}\sim\mathrm{U}(0,1)$ for $i\in[N]$.
The fixed step size is set $\alpha=8\times 10^{-5}$ and batch size is $B=0.5S$. The experiment results are shown in Figure [10](https://arxiv.org/html/2409.07223v2#A1.F10).

When using a fixed step size, Item [1](https://arxiv.org/html/2409.07223v2#S3.I1.i1) of Theorem [3.4](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem4) states that the convergence upper bound consists of two terms: a decaying term $\frac{2\Theta(x_{1})}{\varpi\alpha KT}$ as $K$ (or $T$) increases, and a increasing (or constant) term $2\alpha Q(K,B,\alpha,\varpi)$ with respect to $K$ (or $T$). The initial guess $x_{1}$ is usually generated at random such that $\Theta(x_{1})$ is relatively large, and thus the first term dominates at the initial stage. As a result, at the initial stage, the convergence speed is accelerated when using larger $K$. Subsequently, due to the growth of $T$, the second term begins to dominate and thus when using larger $K$ the error of solution generated by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) to the minimizer get larger. This analysis is verified by Figure [10](https://arxiv.org/html/2409.07223v2#A1.F10). Additionally, we note that in fixed step size cases, Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) numerically demonstrates linear convergence as seen in Figures [5](https://arxiv.org/html/2409.07223v2#A1.F5)-[10](https://arxiv.org/html/2409.07223v2#A1.F10).

Figure: (a) I.I.D.
Refer to caption: x27.png

### A.2 Comparisons with some centralized algorithms

Low-rank matrix completion (LRMC) aims to recover the missing entries of an unknown matrix from a small account of accesible entries with low-rank constraint for the matrix.
Mishra et al. [MKJS19] formulate LRMC in the form of finite sum, which can be extended to the FL setting with finite sum minimization as follows:

$$ $\displaystyle\min_{\mathcal{U}\in\mathrm{Gr}(r,m)}F(\mathcal{U})=\frac{1}{N}\sum_{i=1}^{N}f_{i}(\mathcal{U}),\hbox{with }f_{i}(\mathcal{U})=$ $\displaystyle\frac{1}{S}\sum_{j=1}^{S}5\|\mathcal{P}_{\Omega_{ij}}(\mathbf{U}\mathbf{W}_{ij\mathbf{U}}^{T})-\mathcal{P}_{\Omega_{ij}}(\mathbf{Y}^{*}_{ij})\|_{F}^{2}$ (A.2) $\displaystyle+\lambda\|\mathbf{U}\mathbf{W}_{ij\mathbf{U}}^{T}-\mathcal{P}_{\Omega_{ij}}(\mathbf{U}\mathbf{W}_{ij\mathbf{U}}^{T})\|_{F}^{2}$ $$

where $\mathrm{Gr}(r,m)$ is the Grassmann manifold, i.e, the set of all the $r$-dimension subspaces of $\mathbb{R}^{m}$, $\mathbf{U}\in\mathrm{St}(r,m)$ is the matrix characterization of $\mathcal{U}\in\mathrm{Gr}(r,m)$, $\mathbf{W}_{ij\mathbf{U}}\in\mathbb{R}^{n_{ij}\times r}$ with $\sum_{i=1}^{N}\sum_{j=1}^{S}n_{ij}=n$ is the least-squares solution to $\operatorname*{arg\,min}_{\mathbf{W}_{ij}\in\mathbb{R}^{n_{ij}\times r}}0.5\|\mathcal{P}_{\Omega_{ij}}(\mathbf{U}\mathbf{W}_{ij}^{T})-\mathcal{P}_{\Omega_{ij}}(\mathbf{Y}^{*}_{ij})\|_{F}^{2}+\lambda\|\mathbf{U}\mathbf{W}_{ij}^{T}-\mathcal{P}_{\Omega_{ij}}(\mathbf{U}\mathbf{W}_{ij}^{T})\|_{F}^{2}$, $\mathbf{Y}^{*}\in\mathbb{R}^{m\times n}$ is the known matrix and is partitioned into $\mathbf{Y}^{*}=[\mathbf{Y}^{*}_{1,1},\dots,\mathbf{Y}^{*}_{1,S},\dots,\\
\mathbf{Y}^{*}_{N,1},\dots,\mathbf{Y}^{*}_{N,S}]$ with $\mathbf{Y}_{ij}^{*}\in\mathbb{R}^{m\times n_{ij}}$, $\Omega$ is the indices set of elements of $\mathbf{Y}^{*}$: the $(l,k)$-element of $\mathbf{Y}^{*}$ is nonzero if and only if its index belongs to $\Omega$ and is also partitioned similar to the way of $\mathbf{Y}$: $\Omega=\{\Omega_{1,1},\dots,\Omega_{1,S},\dots,\Omega_{N,1},\dots,\Omega_{N,S}\}$, and
operator $\mathcal{P}_{\Omega_{ij}}$ is the orthogonal sampling operator defined by $[\mathcal{P}_{\Omega_{ij}}(\mathbf{Y})]_{lk}=\hbox{ the }(l,k)$-element of $\mathbf{Y}$ if $(l,k)\in\Omega_{i,j}$ and $[\mathcal{P}_{\Omega_{ij}}(\mathbf{Y})]_{lk}=0$ otherwise. It is worthy mentioned that Problem ([A.2](https://arxiv.org/html/2409.07223v2#A1.E2)) is defined on $\mathrm{Gr}(r,m)$ but the computation can be implemented with matrices $\mathbf{U}$ in $\mathrm{St}(r,m)$. The over-sampling ratio (OS) is the ratio of number of entries of $\Omega$ and the freedom degree of $\mathbf{Y}^{*}$, i.e., $OS=|\Omega|/((m+n-r)r)$.

In this paper, the Grasssmann manifold $\mathrm{Gr}(r,m)$ is equipped with the quotient structure $\mathrm{Gr}(r,m)=\mathrm{St}(r,m)/\mathrm{O}(r)=\{[\mathbf{U}]:\mathbf{U}\in\mathrm{St}(r,m)\}$ with $\mathrm{O}(r)$ the orthogonal group of the order $r$. The Riemannian metric on $\mathrm{Gr}(r,m)$ is induced by the inner product, i.e., $\left<\eta_{\mathcal{U}},\xi_{\mathcal{U}}\right>_{\mathcal{U}}=\mathrm{trace}(\eta_{\mathcal{U}_{\uparrow}}^{T}\xi_{\mathcal{U}_{\uparrow}})$, where $\xi_{\mathcal{U}_{\uparrow}}$ is the horizontal lift of $\xi_{\mathcal{U}}$. The retraction via Cayley transform (CT) [ZS21] is given by

$$ $\mathrm{R}^{\mathrm{Cay}}_{\mathcal{U}}(\xi_{\mathcal{U}})=\left[\mathbf{U}+\xi_{\mathcal{U}_{\uparrow}}-\left(\frac{1}{2}\mathbf{U}+\frac{1}{4}\xi_{\mathcal{U}_{\uparrow}}\right)\left(I_{r}+\frac{1}{4}\xi_{\mathcal{U}_{\uparrow}}^{T}\xi_{\mathcal{U}_{\uparrow}}\right)^{-1}\xi_{\mathcal{U}_{\uparrow}}^{T}\xi_{\mathcal{U}_{\uparrow}}\right],$ $$

and the inverse of $\mathrm{R}^{\mathrm{Cay}}$ [ZS21] is computed by

$$ $\left(\left(\mathrm{R}_{\mathcal{U}}^{\mathrm{Cay}}\right)^{-1}(\mathcal{V})\right)_{\mathcal{U}_{\uparrow}}=2(\mathbf{V}-\mathbf{U}\mathbf{U}^{T}\mathbf{V})(I_{r}+\mathbf{U}^{T}\mathbf{V})^{-1}.$ $$

Correspondingly, the isometric vector transport associated with $\mathrm{R}^{\mathrm{Cay}}$ [ZS21] is given by

$$ $\left(\mathcal{T}^{\mathrm{Cay}}_{\eta_{\mathcal{U}}}(\xi_{\mathcal{U}})\right)_{\mathcal{V}_{\uparrow}}=\xi_{\mathcal{U}_{\uparrow}}-\left(\mathbf{U}+\frac{1}{2}\eta_{\mathcal{U}_{\uparrow}}\right)\left(I_{r}+\frac{1}{4}\eta_{\mathcal{U}_{\uparrow}}^{T}\eta_{\mathcal{U}_{\uparrow}}\right)^{-1}\eta_{\mathcal{U}_{\uparrow}}^{T}\xi_{\mathcal{U}_{\uparrow}}$ $$

with $\mathcal{V}=\mathrm{R}^{\mathrm{Cay}}_{\mathcal{U}}(\eta_{\mathcal{U}})$. We point out that Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) does not require the usage of the inverse of retraction. Here, that we use the inverse of retraction is just to assist in the implementation of the vector transport.
Moreover, if one uses the vector transport by projection, then the inverse of retraction does not need.

#### A.2.1 Synthetic case

Sample at random two matrices $\mathbf{A}\in\mathbb{R}^{m\times r}$ and $\mathbf{B}\in\mathbb{R}^{n\times r}$.
Let $\mathbf{Y}^{*}=\mathbf{A}\mathbf{B}^{T}$. $mn-|\Omega|$ entries are randomly removed with uniform probability.
Each of the rest entries is perturbed by noise obeying the
Gaussian distribution with mean zero and standard deviation $10^{-6}$. In the experiment, the rank is set as $r=5$, the OS is set as $OS=6$, and $(m,n)=(100,2000)$. The other parameters are set as $\lambda=0$, $(N,S)=(20,100),p_{i}\sim\mathrm{U}(0,1),\forall i\in[N]$, $B=0.5S$, and $\alpha=2\times 10^{-3}$,

Let $\tilde{\mathbf{U}}$ be the solution given by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1). Then $\mathbf{W}_{\tilde{\mathbf{U}}}=[\mathbf{W}_{11\tilde{\mathbf{U}}},\dots,\mathbf{W}_{1S\tilde{\mathbf{U}}},\dots,\mathbf{W}_{N1\tilde{\mathbf{U}}},\dots,\\
\mathbf{W}_{NS\tilde{\mathbf{U}}}]$, and thus the approximation to $\mathbf{Y}^{*}$ is given by $\tilde{\mathbf{Y}}=\tilde{\mathbf{U}}\mathbf{W}^{T}_{\tilde{\mathbf{U}}}$. Relative error (lower is better) between $\tilde{\mathbf{Y}}$ and $\mathbf{Y}^{*}$, computed by

$$ $\mathrm{rel_err}(\tilde{\mathbf{Y}})=\frac{\|\tilde{\mathbf{Y}}-\mathbf{Y}^{*}\|_{F}}{\|\mathbf{Y}^{*}\|_{F}},$ $$

is used to measure the performance of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1). From Figure [11](https://arxiv.org/html/2409.07223v2#A1.F11), we also observe a similar result: the number of inner iterations significantly affects the convergence. It is worth mentioning that the results demonstrate Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) has a linear convergence rate.

Figure: Figure 11: LRMC with synthetic data: performance of RFedAGS with different $K$.
Refer to caption: x30.png

#### A.2.2 A real-world application

We use MovieLens 1M (^6^66See [https://grouplens.org/datasets/movielens/1m/](https://grouplens.org/datasets/movielens/1m/).) dataset which consists of $1000209$ ratings with $6040$ users rating $3952$ movies. In LRMC setting, $\mathbf{Y}^{*}\in\mathbb{R}^{m\times n}$, with $m=3952$, $n=6040$, and $|\Omega|=1000209$, whose nonzero elements are the ratings. We randomly sample $80\%$ ratings for each column of $\mathbf{Y}^{*}$ as the training samples, denoted by $\mathbf{Y}^{\mathrm{tr}}$, and the testing dataset, denoted by $\mathbf{Y}^{\mathrm{te}}$, is consisted of the remainder. In terms of the FL setting, $\mathbf{Y}^{\mathrm{tr}}$ is equally divided into $N=40$ agents by column at order, i.e., $\mathbf{Y}^{\mathrm{tr}}=[\mathbf{Y}^{\mathrm{tr}}_{1},\dots,\mathbf{Y}^{\mathrm{tr}}_{N}]$, and each agent has $S=151$ columns, i.e., $\mathbf{Y}^{\mathrm{tr}}_{i}=[\mathbf{Y}^{\mathrm{tr}}_{i,1},\dots,\mathbf{Y}^{\mathrm{tr}}_{i,S}]$ where $\mathbf{Y}^{\mathrm{tr}}_{i,j}\in\mathbb{R}^{m}$. The other parameters are set as $\lambda=10^{-2}$, $p_{i}\sim\mathrm{U}(0,1),\forall i\in[N]$, $B=0.5S$, and $\alpha=6\times 10^{-4}$.

In order to evaluate the performance of those methods, the root mean square error (RMSE) is used and is computed by

$$ $\mathrm{RMSE}(\tilde{\mathbf{Y}})=\sqrt{\frac{1}{|\Omega^{\mathrm{te}}|}\sum_{(i,j)\in\Omega^{\mathrm{te}}}|\tilde{\mathbf{Y}}_{ij}-\mathbf{Y}_{ij}^{\mathrm{te}}|^{2}}$ $$

with $\tilde{\mathbf{Y}}$, $\mathbf{Y}^{\mathrm{te}}$, and $\Omega^{\mathrm{te}}$ being the approximation to $\mathbf{Y}^{\mathrm{te}}$, the testing matrix, and the indices set of known entries of $\mathbf{Y}^{\mathrm{te}}$, respectively. We observe in Figure [12](https://arxiv.org/html/2409.07223v2#A1.F12) and Table [2](https://arxiv.org/html/2409.07223v2#A1.T2) that the proposed RFedPP is comparable to these centralized methods in solving LRMC in terms of RMSE when choosing an appropriate $K$.

Figure: (a) $r=3$
Refer to caption: x32.png

**Table 2: The best RMSE scores (lower is better) on testing set for different subspace dimension $r$ and different number of local update $K$. Here the scalar $a.bcd_{k}$ denotes $a.bcd\times 10^{k}$.**
|  | RFedPP | RSD | RCG | LRBFGS |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | $K=2$ | $K=4$ | $K=8$ | $K=12$ | $K=16$ |  |  |  |
| $r=3$ | $8.260_{-1}$ | $8.101_{-1}$ | $8.023_{-1}$ | $7.968_{-1}$ | $7.948_{-1}$ | $7.925_{-1}$ | $7.925_{-1}$ | $7.925_{-1}$ |
| $r=5$ | $8.095_{-1}$ | $7.902_{-1}$ | $7.757_{-1}$ | $7.679_{-1}$ | $7.654_{-1}$ | $7.616_{-1}$ | $7.614_{-1}$ | $7.614_{-1}$ |
| $r=7$ | $7.966_{-1}$ | $7.743_{-1}$ | $7.577_{-1}$ | $7.507_{-1}$ | $7.468_{-1}$ | $7.392_{-1}$ | $7.384_{-1}$ | $7.382_{-1}$ |

### A.3 The details of experiment settings in Section 4

In this section, we detail the experiment settings in Section [4](https://arxiv.org/html/2409.07223v2#S4).

##### PCA.

We restate the PCA problem as follows for convenience:

$$ $\displaystyle\min_{X\in\mathrm{St}(r,d)}F(X):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(X),\quad\hbox{ with }f_{i}(X)=-\frac{1}{S}\sum_{j=1}^{N}\mathrm{tr}(X^{T}(Z_{ij}Z_{ij}^{T})X),$ (A.3) $$

where $\mathrm{St}(r,d)=\{X\in\mathbb{R}^{d\times r}:X^{T}X=I_{r}\}$ is the Stiefel manifold, $\mathcal{D}_{i}=\{Z_{i1},\dots,Z_{iS}\}\subseteq\mathbb{R}^{d\times p}$ is the local dataset held by agent $i$, $\forall i\in[N]$.

For the Stiefel manifold $\mathrm{St}(r,d)$, we view it as a Riemannian manifold embedded in $\mathbb{R}^{d\times r}$. Thus the Riemannian metric is chosen as $\left<U,V\right>_{X}=\left<U,V\right>_{\mathrm{F}}$ for all $X\in\mathrm{St}(r,d)$ and $U,V\in\mathrm{T}_{X}\mathrm{St}(r,d)$. The retraction is the qr-retraction [AMS08] and the vector transport is given via the projection, i.e., $\mathcal{T}_{V}U=\mathcal{P}_{\mathrm{R}^{\mathrm{qr}}_{X}(V)}(U)$.
In theory, RFedAvg and RFedSVRG [LM23] require the exponential mapping, its inverse, and parallel transport. But on the Stiefel manifold, the last two operators have no closed-form expressions. Thus we use retraction, its inverse, and vector transport to replace them.

For the synthetic data, we set $p=1$ and generate the local datesets by setting $[Z_{i1},\dots,Z_{iS}]=Z_{i}$ drawn from the Gaussian distribution $Z_{i}\sim\mathcal{N}(0,\frac{i}{N})$. In experiment, all parameters are set as $(r,d)=(5,100)$, $(N,S)=(40,100)$, $\alpha=6\times 10^{-3}$, $B=0.5S$, $K=5$, and $p_{i}\sim\mathrm{U}(0,1)$.

For CIFAR10 dataset, whose training dataset contains 50000 RGB images with size $32\times 32$ of each channel, it is also shuffled following the way of [MMR^+17] such that the local datasets are non-I.I.D. (see Figure [13](https://arxiv.org/html/2409.07223v2#A1.F13) below).
In experiment, we flatten each image into a vector in $\mathbb{R}^{3072}$, and thus each local data point $Z_{ij}$ is inside $\mathbb{R}^{3072}$. The other parameters are set as $(r,d)=(4,3072)$, $(N,S)=(50,1000)$, $\alpha=3\times 10^{-5}$, $B=0.5S$, $K=5$, and $p_{i}\sim\mathrm{U}(0,1)$.

Figure: (a) Local dataset distributions
Refer to caption: x35.png

##### HSP.

Given a set of training pairs $\mathcal{D}=\{\mathcal{D}_{i}\}_{i=1}^{N}=\{\{(w_{i,j},y_{i,j})\}_{j=1}^{S}\}_{i=1}^{N}$, where $w_{i,j}\in\mathrm{R}^{r}$ is the feature and $y_{i,j}\in\mathcal{H}^{d}$ is the hyperbolic embedding of the class of $w_{i,j}$. Then for a test sample $w$, the task of HPS is to predict its hyperbolic embeddings by solving the following problem

$$ $\operatorname*{arg\,min}_{x\in\mathcal{H}^{d}}F(x):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x),\hbox{ with }f_{i}(x)=\frac{1}{S}\sum_{i=1}^{S}a_{i,j}(\omega)\mathrm{dist}^{2}(x,y_{i,j})$ $$

where the hyperbolic manifold $\mathcal{H}^{d}$ is characterized via the Lorentz hyperbolic model $\mathcal{H}^{d}:=\{x\in\mathbb{R}^{d+1}:\left<x,y\right>_{\mathcal{L}}=-1\}$ with $\left<x,x\right>_{\mathcal{L}}=x^{T}y-2x_{1}y_{1}$, $a_{1}(w)^{T}=(a_{i,1}(w),\dots,a_{i,S}(w))^{T}\in\mathbb{R}^{S}$ is a pre-given constant vector related to $w$, and $\mathrm{dist}(\cdot,\cdot):\mathcal{M}\times\mathcal{M}\rightarrow\mathbb{R}$ is the Riemannian distance. A commonly used option of $a_{i}(w)$ is computed by $a_{i}(w)=(K_{i}+\gamma I)^{-1}K_{i,w}$, where $\gamma$ is the regularization parameter, and $K_{i}\in\mathbb{R}^{S\times S}$ and $K_{i,w}\in\mathbb{R}^{S}$ are given by $(K_{i})_{l,h}=k(w_{i,l},w_{i,h})$ and $(K_{i,w})_{j}=k(w_{i,j},w)$ for a raial basis function (RBF) kernel $k(w,w^{\prime})=\exp(-\|w-w^{\prime}\|_{2}^{2}/(2\nu)^{2})$ with a constant $\nu>0$.

The WordNet dataset [Mil95] is used to conduct the experiment of inferring hyperbolic embeddings. Following [NK17], the pretrained hyperbolic embeddings on $\mathcal{H}^{2}$ of the mammals subtree with the transitive closure containing $n=1180$ nodes (words) and $6540$ edges (hierarchies) are used. (^7^77It is referred to website [https://github.com/facebookresearch/poincare-embeddings](https://github.com/facebookresearch/poincare-embeddings).) The features are stemmed from Laplacian eigenmap [BN03] to dimension $r=3$ of the adjacency matrix formed by the edges. In other words, we obtained $\{(w_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{3}\times\mathcal{H}^{2}$. This setting is in line with the work in [HMJG24]. In the experiments, the word “primate” is selected as the test sample, and the remainder is used to train. Therefore, the hyperbolic embedding of the word “primate” is known and is viewed as the true embedding, i.e., $x_{\mathrm{true}}$. For other parameters, they are set as $(N,S)=(9,131)$, $\alpha=6\times 10^{-2}$, $B=0.5S$, $K=5$, $p_{i}\sim\mathrm{U}(0,1)$, and $(\gamma,\nu)=(10^{-5},0.3)$.

##### FMC.

Given a set of training SPD matrices $\mathcal{D}:=\{\mathcal{D}_{i}\}_{i=1}^{N}=\{\{X_{i,j}\}_{j=1}^{S}\}_{i=1}^{N}$, where $\{X_{i,j}\}^{S}_{j=1}\subseteq\mathcal{S}_{++}^{N}:=\{X\in\mathbb{R}^{N\times N}:X^{T}=X,X\succ 0\}$, the FMC of these SPD matrices is the solution to the following problem

$$ $\operatorname*{arg\,min}_{X\in\mathcal{S}_{++}^{N}}F(X):=\frac{1}{N}\sum_{i=1}^{N}f_{i}(X),\hbox{ with }f_{i}(X)=\frac{1}{S}\sum_{j=1}^{S}\mathrm{dist}^{2}(X,X_{i,j}),$ $$

where $\mathrm{dist}(X,Y)=\|\mathrm{logm}(X^{-1/2}X_{i,j}X^{-1/2})\|_{\mathrm{F}}$ with $\mathrm{logm}(\cdot)$ the principal matrix logarithm is the Riemannian distance.

The PATHMNIST dataset [YSW^+23] consists of 89996 RGB images and we transform each image into a $9\times 9$ SPD matrix by the covariance descriptor [TPM06]. In the experiment, we randomly selects $20000$ images to construct the training dataset.
The parameters are set as $(N,S)=(50,400)$, $\alpha=0.01$, $B=0.5S$, $K=5$, and $p_{i}\sim\mathrm{U}(0,1)$.

## Appendix B Preliminaries on Riemannian optimization

In this section, we briefly review the basic ingredients for Riemannian optimization, which are drawn from the standard literature, e.g., [Boo75, AMS08]. Let $\mathcal{M}$ be a $d$-dimensional Riemannian manifold equipped with a Riemannian metric $\left<\cdot,\cdot\right>:(\eta_{x},\zeta_{x})\mapsto\left<\eta_{x},\zeta_{x}\right>_{x}\in\mathbb{R}$ for any $x\in\mathcal{M},\eta_{x},\zeta_{x}\in\mathrm{T}_{x}\mathcal{M}$ (when it is clear in the context, we omit the subscript and write $\left<\eta,\zeta\right>$ for short). For all $x\in\mathcal{M}$, the tangent space $\mathrm{T}_{x}\mathcal{M}$ is a $d$-dimensional linear space. The norm induced by the Riemannian metric in the tangent space $\mathrm{T}_{x}\mathcal{M}$ is $\|\eta\|=\sqrt{\left<\eta,\eta\right>}$ for all $\eta\in\mathrm{T}_{x}\mathcal{M}$. An open ball centered at $\eta\in\mathrm{T}_{x}\mathcal{M}$ with radius $r$ in $\mathrm{T}_{x}\mathcal{M}$ is denoted by $\mathbb{B}(\eta,r)=\{\zeta\in\mathrm{T}_{x}\mathcal{M}:\|\zeta-\eta\|<r\}$. The union of all tangent spaces is tangent bundle, denoted by $\mathrm{T}\mathcal{M}$. A vector field is a mapping which maps from $\mathcal{M}$ to $\mathrm{T}\mathcal{M}$, formally defined by $\eta:\mathcal{M}\rightarrow\mathrm{T}\mathcal{M}:x\mapsto\eta_{x}\in\mathrm{T}_{x}\mathcal{M}$. Given a differentiable function $f:\mathcal{M}\rightarrow\mathbb{R}$, the Riemannian gradient of $f$, denoted by $\mathrm{grad}f$, is a vector field such that for any $x\in\mathcal{M}$, $\mathrm{grad}f(x)$ is the unique vector satisfying $\mathrm{D}f(x)[\eta]=\left<\mathrm{grad}f(x),\eta\right>$ for any $\eta\in\mathrm{T}_{x}\mathcal{M}$, where $\mathrm{D}f(x)[\eta]$ is the directional derivative of $f$ at $x$ along $\eta$.

A critical concept in Riemannian optimization is retraction, which defines a smooth mapping, denoted by $\mathrm{R}$, from the tangent bundle to the manifold, i.e., $\mathrm{R}:\mathrm{T}\mathcal{M}\rightarrow\mathcal{M}$, satisfying

- 1.
$\mathrm{R}(0_{x})=x$ for all $x\in\mathcal{M}$, where $0_{x}$ is the origin of $\mathrm{T}_{x}\mathcal{M}$;
- 2.
$\mathrm{D}\mathrm{R}(0_{x})[\eta]=\eta$ for all $\eta\in\mathrm{T}_{x}\mathcal{M}$, which implies that $\mathrm{D}\mathrm{R}(0_{x})=\mathrm{id}_{\mathrm{T}_{x}\mathcal{M}}$ with $\mathrm{id}_{\mathrm{T}_{x}\mathcal{M}}$ being the identity in $\mathrm{T}_{x}\mathcal{M}$.

When restricted to $\mathrm{T}_{x}\mathcal{M}$, we denote $\mathrm{R}$ by $\mathrm{R}_{x}$, i.e., $\mathrm{R}_{x}=\mathrm{R}\mid_{\mathrm{T}_{x}\mathcal{M}}$.
Note that the domain of $\mathrm{R}$ does not need to be the whole tangent bundle. In practice, it is usually the case. In this paper, we always assume that $\mathrm{R}$ is well-defined whenever needed. A special retraction is the exponential mapping, dented by $\mathrm{Exp}$, satisfying $\mathrm{Exp}_{x}(\eta_{x})=\gamma(1)$ where $\gamma$ is the geodesic such that $\gamma(0)=x$ and $\gamma^{\prime}(0)=\eta_{x}$. Geodesic is the generalization of straight line in the Euclidean setting to the Riemannian setting, and naturally the exponential mapping is the generalization of addition to the Riemannian setting. Additionally, retraction is a first-order approximation to the exponential mapping. A $r$-totally retractive set $\mathcal{W}$ is a subset of $\mathcal{M}$ such that for any $y\in\mathcal{W}$, it holds that $\mathcal{W}\subseteq\mathrm{R}_{y}(\mathbb{B}(0_{y},r))$ and $\mathrm{R}_{y}$ is a diffeomorphism on $\mathbb{B}(0_{y},r)$. Hence, $\mathrm{R}_{x}^{-1}(y)$ is well-defined, whenever $x,y\in\mathcal{W}$.

For our RFedPP, another essential concept is vector transport, denoted by $\mathcal{T}$, which is usually associated with a retraction $\mathrm{R}$.
Given a retraction $\mathrm{R}$, a vector transport associated with $\mathrm{R}$ maps from $\mathrm{T}\mathcal{M}\oplus\mathrm{T}\mathcal{M}$, the Whitney sum, to $\mathrm{T}\mathcal{M}$, i.e., $\mathcal{T}:\mathrm{T}\mathcal{M}\oplus\mathrm{T}\mathcal{M}\rightarrow\mathrm{T}\mathcal{M}$, and satisfies that for any $(x,\eta_{x})\in\mathrm{domain}(\mathrm{R})$ and all $\zeta_{x}\in\mathrm{T}_{x}\mathcal{M}$, the followings hold that

- 1.
$\mathcal{T}_{\eta_{x}}(\zeta_{x})\in\mathrm{T}_{\mathrm{R}(\eta_{x})}\mathcal{M}$;
- 2.
$\mathcal{T}_{0_{x}}\zeta_{x}=\zeta_{x}$;
- 3.
$\mathcal{T}_{\eta_{x}}$ is linear, i.e., for all $a_{1},a_{2}\in\mathbb{R}$ and $\xi_{x},\zeta_{x}\in\mathrm{T}_{x}\mathcal{M}$, it holds that $\mathcal{T}_{\eta_{x}}(a_{1}\xi_{x}+a_{2}\zeta_{x})=a_{1}\mathcal{T}_{\eta_{x}}(\xi_{x})+a_{2}\mathcal{T}_{\eta_{x}}(\zeta_{x})$.

We say $\mathcal{T}$ is isometric if for any $(x,\eta_{x})\in\mathrm{domain}(\mathrm{R})$, $\xi_{x},\zeta_{x}\in\mathrm{T}_{x}\mathcal{M}$, it satisfies $\left<\mathcal{T}_{\eta_{x}}(\xi_{x}),\mathcal{T}_{\eta_{x}}(\zeta_{x})\right>_{\mathrm{R}(\eta_{x})}=\left<\xi_{x},\zeta_{x}\right>_{x}$, which implies that $\|\mathcal{T}_{\eta_{x}}(\zeta_{x})\|=\|\zeta_{x}\|$.
An important vector transport is the parallel transport, which is isometric; refer to [AMS08, Bou23] for the rigorous definition.

In the Euclidean setting, the convergence analyses of FedAvg are established under the assumption that $F$ is $L$-smooth, where a continuously differentiable function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is said $L$-smooth if

$$ $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|\;\forall x,y\in\mathbb{R}^{n},$ $$

in which case we have

$$ $f(y)\leq f(x)+\left<\nabla f(x),y-x\right>+\frac{L}{2}\|y-x\|^{2}.$ $$

Both properties above are critical in the analyses of FedAvg.
Similar assumptions are made in the Riemannian setting for the analysis of the proposed RFedAGS; see Definitions [B.1](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition1) [HAG18] and [B.1](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition1) [HW22]. The first one is called $L$-Lipschitz continuously differentiable (Definitions [B.1](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition1)) and the second one is called $L$-retraction-smooth (Definitions [B.2](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition2)).

###### Definition B.1 ( $L$ -Lipschitz continuous differentiability) .

Let $\mathcal{T}$ be a vector transport associated with a retraction $\mathrm{R}$. A function $f:\mathcal{M}\rightarrow\mathbb{R}$ is said $L$-Lipschitz continuous differentiable with respect to $\mathcal{T}$ on $\mathcal{U}\subseteq\mathcal{M}$ if there exists a constant $L>0$ such that

$$ $\|\mathcal{T}_{\eta}(\mathrm{grad}f(y))-\mathrm{grad}f(x)\|\leq L\|\eta\|$ $$

for all $x\in\mathcal{U}$ and $\eta\in\mathrm{T}_{x}\mathcal{M}$ satisfying $y=\mathrm{R}_{x}(\eta)$.

###### Definition B.2 ( $L$ -retracton-smoothness) .

A function $f:\mathcal{M}\rightarrow\mathbb{R}$ is called $L$-retraction-smooth with respect to a retraction $\mathbb{R}$ in $\mathcal{N}\subseteq\mathcal{M}$ if for any $x\in\mathcal{N}$ and any $\mathcal{N}_{x}\subseteq\mathrm{T}_{x}\mathcal{M}$ satisfying $\mathrm{R}_{x}(\mathcal{N}_{x})\subseteq\mathcal{N}$, it holds that

$$ $f(\mathrm{R}_{x}(\eta))\leq f(x)+\left<\mathrm{grad}f(x),\eta\right>+\frac{L}{2}\|\eta\|^{2},$ $$

for all $\eta\in\mathcal{N}_{x}$.

A function which is $L$-Lipschitz continuously differentiable is not necessarily $L$-retraction-smoooth, however it is the case in the Euclidean setting. It should be highlighted that there exist some cases where $L$-Lipschitz continuous differentiability implies also $L$-retraction smoothness [HAG18, BAC19, Bou23].

We next review convexity and strongly convexity in the Riemannian setting [HW22].

###### Definition B.3 (Strongly retraction-convex, retraction-convex) .

A function $f:\mathcal{M}\rightarrow\mathbb{R}$ is called $\mu$-strongly retraction-convex with respect to a retraction $\mathrm{R}$ in $\mathcal{N}\subseteq\mathcal{M}$ if for any $x\in\mathcal{N}$ and any $\mathcal{N}_{x}\subseteq\mathrm{T}_{x}\mathcal{M}$ satisfying $\mathrm{R}_{x}(\mathcal{N}_{x})\subseteq\mathcal{N}$, there exist a constant $\mu>0$ and a tangent vector $\zeta\in\mathrm{T}_{x}\mathcal{M}$ such that $f_{x}=f\circ\mathrm{R}_{x}$ satisfies

$$ $f_{x}(\eta)\geq f_{x}(\xi)+\left<\zeta,\eta-\xi\right>+\frac{\mu}{2}\|\eta-\xi\|^{2}\;\forall\eta,\xi\in\mathcal{N}_{x}.$ $$

In particular, if $\mu=0$, we call $f$ retraction-convex with respect to $\mathrm{R}$ in $\mathcal{N}$.

Note that $\zeta=\mathrm{grad}f_{x}(\xi)$ if $f$ is differentiable; otherwise, $\zeta$ is any Riemannian subgradient of $f_{x}$ at $\xi$. In literature, convexity has been studied based on geodesic; see, e.g., [FO02, ZS16], in which case a function $f:\mathcal{M}\rightarrow\mathbb{R}$ is called geodesic convex, if for any $x,y\in\mathcal{M}$, there exists a tangent vector $\zeta_{x}\in\mathrm{T}_{x}\mathcal{M}$ such that $f(y)\geq f(x)+\left<\zeta_{x},\mathrm{Exp}_{x}^{-1}(y)\right>$. It can be verified if taking $\xi=0$ and exponential mapping as the retraction in Definition [B.3](https://arxiv.org/html/2409.07223v2#A2.Thmdefinition3), then retraction-convexity reduces to geodesic convexity.

We end this section with an introduction to the concept of $\epsilon$-stationary points/solutions.

###### Definition B.4 .

We say that $x_{T}\in\mathcal{M}$, the output from Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1), is an $\epsilon$-stationary point of Problem ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)) if it holds that $\mathbb{E}[\|\mathrm{grad}F(x_{T})\|^{2}]\leq\epsilon$, or is an $\epsilon$-solution if it holds that $\mathbb{E}[F({x}_{T})]-F(x^{*})\leq\epsilon$, where $x^{*}\in\operatorname*{arg\,min}_{x\in\mathcal{M}}F(x)$.

###### Definition B.1 ( L L -Lipschitz continuous differentiability) .

###### Definition B.2 ( L L -retracton-smoothness) .

###### Definition B.3 (Strongly retraction-convex, retraction-convex) .

###### Definition B.4 .

## Appendix C Additional Discussions

### C.1 Discussions for Assumptions

Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.7](https://arxiv.org/html/2409.07223v2#S3.Thmassumption7) are standard for Riemannian stochastic gradient-based methods.
Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1) imposes requirements for the retraction under consideration to be $C^{2}$ and the vector transport under consideration to be continuous and bounded from above. These requirements are fairly standard in Riemannian optimization. Note that the boundedness for vector transport can be achieved by requiring isometricness, in which case we have $\|\mathcal{T}_{\eta_{x}}(\zeta_{x})\|=\|\zeta_{x}\|$, implying $\Upsilon=1$. In fact, a lots of papers do have such requirements, e.g., [SKM19, LM23]. Additionally, if the Riemannian manifold $\mathcal{M}$ is a submanifold embedded in a Euclidean space and equipped with the inner product as its Riemannian metric, then an option for vector transport is based on the orthogonal operation onto the tangent space, i.e., $\mathcal{T}_{\eta_{x}}(\zeta_{x})=\mathcal{P}_{\mathrm{R}(\eta_{x})}(\zeta_{x})$ with $\mathcal{P}_{x}(u)=\operatorname*{arg\,min}_{v\in\mathrm{T}_{x}\mathcal{M}}\|v-u\|_{\mathrm{F}}^{2}$, in which case by the nonexpansivity of the orthogonal projection we have $\|\mathcal{T}_{\eta_{x}}(\zeta_{x})\|\leq\|\zeta_{x}\|$, also implying $\Upsilon=1$.

In the deterministic optimization, the compactness of the sublevel set of the objective function is required to ensure that the iterates generated by the algorithms which are monotonically decreasing are still located in that compact set. However, in the stochastic setting, it is difficult to ensure that the iterates generated by the algorithms all fall within the sublevel set since the algorithms are not necessarily monotonically decreasing, and thus, it is not sufficient to require the sublevel set to be compact under stochastic optimization.
In this case, Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2) becomes a commonly used choice in Riemannian stochastic optimization; see, e.g., [Bon13, ZS16, TFBJ18, SKM19, HG21, LM23].
For some manifolds that are compact themself, e.g., the Stiefel manifold and the Grassmann manifold, the compactness assumption naturally holds.
Moreover, in all experiments we conducted, it is observed that the generated iterates $x_{t}$, with $t\geq 1$, fall into the sublevel set $\{x\in\mathcal{M}:f(x)\leq f(x_{1})\}$.

Assumptions [3.6](https://arxiv.org/html/2409.07223v2#S3.Thmassumption6) and [3.7](https://arxiv.org/html/2409.07223v2#S3.Thmassumption7) impose requirements on the first- and second-order moments for the local stochastic gradient estimator, which are necessary for Riemannian/Euclidean stochastic gradient-based methods.
In the analyses for Euclidean federated learning algorithms, majority of works make extra assumptions for addressing the heterogeneity data. These assumptions essentially require that the divergence between local and global gradients is bounded, i.e., there exists a constant $\sigma>0$ such that for all $x$,

$$ $\|\nabla f_{i}(x)-\nabla F(x)\|^{2}\leq\sigma^{2}.$ $$

In our analyses for the proposed RFedAGS, we do not explicitly make the similar assumption, since Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2) implies the counterpart requirement. Indeed, under Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2), there exists a constant $P>0$, such that $\|\mathrm{grad}f_{i}(x)\|\leq P$ and $\|\mathrm{grad}F(x)\|\leq P$ for all $i\in[N]$ and $x\in\mathcal{W}$. Hence, it holds that

$$ $\|\mathrm{grad}f_{i}(x)-\mathrm{grad}F(x)\|^{2}\leq 2\|\mathrm{grad}f_{i}(x)\|^{2}+2\|\mathrm{grad}F(x)\|^{2}\leq 4P^{2}.$ $$

Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) imposes the requirement that the approximate probabilities are how close to the true probabilities. As discussed in Section [3.3](https://arxiv.org/html/2409.07223v2#S3.SS3), when using frequencies as the approximation, this assumption holds with high probability. Numerically, the reported results show that the performance using frequencies is comparable to the case using true probabilities.
We note that in the fixed step size case, existing work [WJ24] also makes an equivalent assumption. The difference lies in that the assumption in [WJ24] only considers fixed step size cases, but Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) more finely encompasses the cases of decaying step sizes.

In summary, except Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) that aims to address the arbitrary partial participation, there exists no assumption beyond those made for Riemannian (stochastic) optimization and federated learning.
In theory, the proposed RFedAGS is the first algorithm that can simultaneously address the challenges caused by the partial participation and the heterogeneity data settings. The partial participation under consideration allows arbitrary participation which is more practical than the commonly-countered participation scheme based on random sampling. Even without the Riemannian manifold constraint, i.e., $\mathcal{M}=\mathbb{R}^{n}$, the proposed RFedAGS can reduce to one proposed in [WJ24]. This paper establishes the convergence propoerties of RFedAGS under both the decaying (see Theorems [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem1), [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem2), and [3.3](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem3)) and fixed (see Theorems [3.4](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem4) and [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem5)) step size cases. Under the decaying step size case, global convergence is guaranteed.
These analyses depend on a vital and non-trivial observation (see Assumption [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8)).
However, [WJ24] only considered the assumption of the fixed step case, and thus only established convergence under the fixed step size case, which does not ensure global convergence rather only converges to a $\epsilon$-stationary point.

### C.2 Discussions for Implementations

In Algortihm [1](https://arxiv.org/html/2409.07223v2#alg1), there exists a scenario (called NA) where in certain round of communication no agent participates in communication. We emphasize that this scenario happens with fairly low probability. For example, considering a FL system where $20$ agents participate in communication with probability $p_{i}=0.1$, $i=1,2,\dots,20$, and $5$ agents participate with probability $p_{i}=0.5$, $i=21,22,\dots,25$. Then the scenario NA happens only with probability not greater than $0.38\%$.
For the purpose of robustness, when the scenario NA happens, one option is set $x_{t+1}\leftarrow x_{t}$ to restart the next round of local updates.

## Appendix D Proofs of Theorems in Section 3

### D.1 Supporting lemmas

If the objective $F$ in Problem ([1.1](https://arxiv.org/html/2409.07223v2#S1.E1)) is $L_{g}$-retraction smooth (Assumption [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmassumption5)), under Assumption [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1), it follows that

$$ $\displaystyle\mathbb{E}_{t}[F(x_{t+1})]-F(x_{t})\leq\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\right>]+\frac{L_{g}}{2}\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\|^{2}].$ (D.1) $$

Without considering the arbitrary participation, recalling ([TM](https://arxiv.org/html/2409.07223v2#S2.Ex1)) and ([AGS-RS](https://arxiv.org/html/2409.07223v2#S2.Ex5)), we have

$$ $\displaystyle\mathrm{Exp}_{x_{t}}^{-1}(x_{t+1})$ $\displaystyle=\frac{1}{S}\sum_{j\in\mathcal{S}_{t}}\mathrm{Exp}_{x_{t}}^{-1}(x_{t,K}^{j}),\hbox{ and }$ (D.2) $\displaystyle\mathrm{R}_{x_{t}}^{-1}(x_{t+1})$ $\displaystyle=-\alpha_{t}\frac{1}{S}\sum_{j\in\mathcal{S}_{t}}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\left(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\right).$ (D.3) $$

When $K>1$ and $S>1$, from the increment of parameters of ([TM](https://arxiv.org/html/2409.07223v2#S2.Ex1)) it follows that analyzing the upper bounds of the two terms in the right-hand side of ([D.1](https://arxiv.org/html/2409.07223v2#A4.E1)) is fairly challenging, since the nonlinearity of exponential and its inverse leads to difficulty expand ([D.2](https://arxiv.org/html/2409.07223v2#A4.E2)) into the desired one involved gradient information.
However, the form of ([D.3](https://arxiv.org/html/2409.07223v2#A4.E3)) is very similar to the Euclidean version and thus significantly address the issue.

Lemmas [D.1](https://arxiv.org/html/2409.07223v2#A4.Thmlemma1) together with [D.3](https://arxiv.org/html/2409.07223v2#A4.Thmlemma3) have provided an upper bound for the first term in the right-hand side of ([D.1](https://arxiv.org/html/2409.07223v2#A4.E1)).

###### Lemma D.1 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.5](https://arxiv.org/html/2409.07223v2#S3.Thmassumption5), at the $t$-th outer iteration of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with a stepsize ${\alpha}_{t}$ and a batchsize ${B}_{t}$, we have that

$$ $\displaystyle\mathbb{E}_{t}[\left<\mathrm{grad}F({x}_{t}),\mathrm{R}_{{x}_{t}}^{-1}({x}_{t+1})\right>]\leq-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+{\varpi\alpha_{t}L_{f}^{2}\delta^{2}_{1}}\sum_{k=0}^{K-1}\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})\|^{2}]$ $\displaystyle\quad+{\varpi\alpha_{t}^{2}KGP^{2}\delta_{2}^{2}}-\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}\left[\left\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\right\|^{2}\right],$ (D.4) $$

where $\delta_{1}^{2}=\max_{t\geq 1}\left\{\frac{1}{N}\sum_{j=1}^{N}\left(\frac{p_{j}}{q_{t}^{j}}\right)^{2}\right\}$ and $\delta_{2}^{2}=\sum_{j=1}^{N}\frac{p_{j}^{2}}{N}$.

###### Proof of Lemma D.1 .

On the one hand, we have

$$ $\displaystyle\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\right>]=\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})+\varpi\alpha_{t}K\mathrm{grad}F(x_{t})-\varpi\alpha_{t}K\mathrm{grad}F(x_{t})\right>]$ $\displaystyle=-\varpi\alpha_{t}K\|\mathrm{grad}F(x_{t})\|^{2}+\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})+\varpi\alpha_{t}K\mathrm{grad}F(x_{t})\right>],$ (D.5) $$

where for the second term of the equality on the right-hand side, we have

$$ $\displaystyle\quad\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})+\varpi\alpha_{t}K\mathrm{grad}F(x_{t})\right>]$ $\displaystyle=\mathbb{E}_{t}\bigg[\bigg<\mathrm{grad}F(x_{t}),-\sum_{j\in\mathcal{S}_{t}}\frac{\varpi\alpha_{t}}{q_{t}^{j}N}\sum_{k=0}^{K-1}\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j}))+\varpi\alpha_{t}K\mathrm{grad}F(x_{t})\bigg>\bigg]$ $\displaystyle=\mathbb{E}_{t}\bigg[\bigg<\mathrm{grad}F(x_{t}),-\sum_{k=0}^{K-1}\bigg(\sum_{j\in\mathcal{S}_{t}}\frac{\varpi\alpha_{t}}{q_{t}^{j}NB_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j}))+\mathrm{grad}F(x_{t})\bigg)\bigg>\bigg]$ $\displaystyle=\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg<\mathrm{grad}F(x_{t}),-\varpi\alpha_{t}\sum_{j\in\mathcal{S}_{t}}\bigg(\frac{1}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}N}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg>\biggl]$ $\displaystyle=\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg<\sqrt{\varpi\alpha_{t}}\mathrm{grad}F(x_{t}),-\sum_{j\in\mathcal{S}_{t}}\frac{{\sqrt{\varpi\alpha_{t}}}}{N}\bigg(\frac{1}{q_{t}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg>\bigg]$ $\displaystyle=\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg<\sqrt{\varpi\alpha_{t}}\mathrm{grad}F(x_{t}),-\sum_{j=1}^{N}\mathbb{I}_{\mathcal{S}_{t}}(j)\frac{{\sqrt{\varpi\alpha_{t}}}}{N}\bigg(\frac{1}{q_{t}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg>\bigg]$ $\displaystyle=\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg<\sqrt{\varpi\alpha_{t}}\mathrm{grad}F(x_{t}),-\sum_{j=1}^{N}\frac{p_{j}{\sqrt{\varpi\alpha_{t}}}}{N}\bigg(\frac{1}{q_{t}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg>\bigg]$ $\displaystyle=\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{N}\bigg(\frac{1}{q_{t}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle\quad-\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg],$ (D.6) $$

where the third equality follows ([2.1](https://arxiv.org/html/2409.07223v2#S2.E1)), the sixth equality follows $\mathbb{E}[\mathbb{I}_{\mathcal{S}_{t}}(j)]=p_{j}$, and the last equality is due to $\left<u,v\right>=\frac{1}{2}(\|u\|^{2}+\|v\|^{2}-\|u-v\|^{2})$.
Moreover, we note that

$$ $\displaystyle\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{N}\bigg(\frac{1}{q_{t}^{j}}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\frac{1}{p_{j}}\mathrm{grad}f_{j}(x_{t})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle=\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{N}\bigg(\frac{1}{q_{t}^{j}}\left(\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))-\mathrm{grad}f_{j}(x_{t})\right)$ $\displaystyle\quad+\bigg(\frac{1}{q_{t}^{j}}-\frac{1}{p_{j}}\bigg)\mathrm{grad}f_{j}(x_{t})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle\leq\varpi\alpha_{t}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\left(\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f(x_{t,k}^{j}))-\mathrm{grad}f_{j}(x_{t})\right)\bigg\|^{2}\bigg]$ $\displaystyle\quad+\varpi\alpha_{t}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{N}\bigg(\frac{1}{q_{t}^{j}}-\frac{1}{p_{j}}\bigg)\mathrm{grad}f_{j}(x_{t})\bigg\|^{2}\bigg]$ $\displaystyle\leq\frac{\varpi\alpha_{t}L_{f}^{2}}{N}\sum_{j=1}^{N}\left(\frac{p_{j}}{q_{t}^{j}}\right)^{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})\|^{2}]+\sum_{j=1}^{N}\frac{p_{j}^{2}}{N}KGP^{2}\varpi\alpha_{t}^{2}$ $\displaystyle\leq\varpi\alpha_{t}\delta_{1}^{2}L_{f}^{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})\|^{2}]+\varpi\alpha_{t}^{2}KGP^{2}\delta_{2}^{2},$ (D.7) $$

where the first inequality follows $\|u+v\|^{2}\leq 2\|u\|^{2}+2\|v\|^{2}$, the second inequality is due to the $L_{f}$-retraction smoothness of $\mathrm{grad}f_{j}$ for $j=1,2,\dots,N$, Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2) (which implies that there exists $P>0$ such that $\|\mathrm{grad}f_{i}(x_{t})\|\leq P$), [3.4](https://arxiv.org/html/2409.07223v2#S3.Thmassumption4), and [3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8), and the third inequality follows that $\delta_{1}^{2}=\max_{t\geq 1}\left\{\frac{1}{N}\sum_{i=1}^{N}\left(\frac{p_{i}}{q_{t}^{i}}\right)^{2}\right\}$ and $\delta_{2}^{2}=\sum_{i=1}^{N}\frac{p_{i}^{2}}{N}$.
Combining ([D.5](https://arxiv.org/html/2409.07223v2#A4.E5)), ([D.6](https://arxiv.org/html/2409.07223v2#A4.E6)), and ([D.7](https://arxiv.org/html/2409.07223v2#A4.E7)) yields the desired result.
∎

In order to further bound $\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\right>]$ for $K>1$, from Lemma [D.1](https://arxiv.org/html/2409.07223v2#A4.Thmlemma1), it is necessary to estimate the bounds for $\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})\|^{2}]$, as theoretically discussed in Lemma [D.3](https://arxiv.org/html/2409.07223v2#A4.Thmlemma3) which states that for agent $j$, the “distance” between the $k$-th local update $x_{t,k}^{j}$ and the the $t$-th outer iterate $x_{t}$ are controlled by the sum of squared step sizes. Intuitively, the “distance” increases as the number of local iterations grows, which is shown in Lemma [D.4](https://arxiv.org/html/2409.07223v2#A4.Thmlemma4). Meanwhile, it also reflects the drift between an agent’s local update parameter $x_{t,k}^{j}$ and the global parameter $x_{t}$. A general result is provided in Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2).

###### Lemma D.2 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.3](https://arxiv.org/html/2409.07223v2#S3.Thmassumption3), let $F:\mathcal{M}\rightarrow\mathbb{R}$ be a smooth function. If consider the following update formulation

$$ $x_{t,k+1}=\mathrm{R}_{x_{t,k}}(-\alpha_{t,k}\mathcal{G}_{F}(x_{t,k})),$ $$

where $\mathcal{G}_{F}(x_{t,k})$ is an estimator of $\mathrm{grad}F(x_{t,k})$, $x_{t}=x_{t,0}$, and $\alpha_{t,\tau}$ is the step size, then it follows that

$$ $\|\mathrm{R}^{-1}_{x_{t}}(x_{t,k})\|^{2}\leq 2k\sum_{\tau=0}^{k-1}\alpha_{t,\tau}^{2}(J^{2}+\alpha_{t,\tau}^{2}H^{2}\|\mathcal{G}_{F}(x_{t,\tau})\|^{2})\|\mathcal{G}_{F}(x_{t,\tau})\|^{2},$ $$

where $J$ and $H$ are two positive constants related with the manifold and retraction.

The proof of Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2) needs the following inverse function theorem on manifolds.

###### Theorem D.1 (Inverse function theorem) .

Given a smooth mapping $P:\mathcal{M}\rightarrow\mathcal{M^{\prime}}$ defined between two manifolds, if $\mathrm{D}P(x)$ is invertible at some point $x\in\mathcal{M}$, then there exist neighborhoods $\mathcal{U}_{x}\subseteq\mathcal{M}$ of $x$ and $\mathcal{V}_{P(x)}\subseteq\mathcal{M^{\prime}}$ of $P(x)$ such that $P|_{\mathcal{U}_{x}}:\mathcal{U}_{x}\rightarrow\mathcal{V}_{P(x)}$ is a diffeomorphism. Meanwhile, if $P^{-1}$ is the inverse of $P$ in $\mathcal{U}_{x}$, then we have $(\mathrm{D}P(x))^{-1}=\mathrm{D}P^{-1}(P(x))$.

Now we are ready to prove Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2).

###### Proof of Lemma D.2 .

For two points $x,y\in\mathcal{W}$, consider the map $P_{x,y}=\mathrm{R}_{y}^{-1}\circ\mathrm{R}_{x}:\mathrm{T}_{x}\mathcal{M}\rightarrow\mathrm{T}_{y}\mathcal{M}:\eta_{x}\mapsto\mathrm{R}_{y}^{-1}(\mathrm{R}_{x}(\eta_{x}))$, which is defined between two vector spaces.
According to the chain rule for the differential of a map and the first-order property of the retraction, i.e., $\mathrm{D}\mathrm{R}_{x}(0_{x})=\mathrm{I}_{\mathrm{T}_{x}\mathcal{M}}$, we have

$$ $\displaystyle\mathrm{D}P_{x,y}(0_{x})$ $\displaystyle=\mathrm{D}(\mathrm{R}_{y}^{-1}\circ\mathrm{R}_{x})(0_{x})=\mathrm{D}\mathrm{R}_{y}^{-1}(\mathrm{R}_{x}(0_{x}))\circ\mathrm{D}\mathrm{R}_{x}(0_{x})$ $\displaystyle=(\mathrm{D}\mathrm{R}_{y}(\mathrm{R}_{y}^{-1}(R_{x}(0_{x}))))^{-1}\circ\mathrm{I}_{\mathrm{T}_{x}\mathcal{M}}=(\mathrm{D}\mathrm{R}_{y}(\mathrm{R}_{y}^{-1}(x)))^{-1}=(\Lambda_{y}^{x})^{-1},$ $$

where the third equality is due to the inverse function Theorem [D.1](https://arxiv.org/html/2409.07223v2#A4.Thmtheorem1).
Noting that the map $P_{\cdot,\cdot}(\cdot)$ is defined in $\mathrm{T}_{\mathcal{W}}=\{(x,y,\eta):x,y\in\mathcal{W},\eta\in\mathrm{R}_{x}^{-1}(\mathcal{W})\}$, which is inside a compact set, according to Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2), thus,
smoothness of the retraction implies that the Jacobin and Hessian of $P_{\cdot,\cdot}(\cdot)$ with respect to the third variable is uniformly bounded in norm on the compact set.
We, thus, use $C_{2},C_{3}>0$ to denote bounds on the operator norms of the Jacobin and Hessian of $P_{\cdot,\cdot}(\cdot)$ with respect to the third variable in the compact set.
Noting that

$$ $\displaystyle P_{x_{t,k-1}^{j},x_{t}}(\eta_{x_{t,k-1}^{j}})=\mathrm{R}_{x_{t}}^{-1}(\mathrm{R}_{{x}_{t,k-1}^{j}}(\eta_{x_{t,k-1}^{j}}))=\mathrm{R}^{-1}_{x_{t}}(x_{t,k}^{j}),\hbox{ and }$ $\displaystyle P_{{x}_{t,k-1}^{j},x_{t}}(0)=\mathrm{R}_{x_{t}}^{-1}(\mathrm{R}_{x_{t,k-1}^{j}}(0))=\mathrm{R}_{x_{t}}^{-1}(x_{t,k-1}^{j})$ $$

with $\eta_{x_{t,k-1}^{j}}=-{\alpha_{t,k-1}}\mathcal{G}_{F}(x_{t,k-1}^{j})$, using a Taylor expansion for $P_{x,y}$ yields

$$ $\displaystyle\mathrm{R}^{-1}_{x_{t}}(x_{t,k}^{j})$ $\displaystyle=P_{x_{t,k-1}^{j},x_{t}}(-{\alpha_{t,k-1}}\mathcal{G}_{F}(x_{t,k-1}^{j}))$ $\displaystyle=P_{{x}_{t,k-1}^{j},x_{t}}(0)+\mathrm{D}P_{x_{t,k-1}^{j},x_{t}}(0)(-{\alpha_{t,k-1}}\mathcal{G}_{F}(x_{t,k-1}^{j}))+{\alpha_{t,k-1}}e_{t,k-1}^{j}$ $\displaystyle=\mathrm{R}_{x_{t}}^{-1}(x_{t,k-1}^{j})-{\alpha_{t,k-1}}(\Lambda_{x_{t}}^{x_{t,k-1}^{j}})^{-1}(\mathcal{G}_{F}(x_{t,k-1}^{j}))+{\alpha_{t,k-1}}e_{t,k-1}^{j},$ $$

where $\|e_{t,k-1}^{j}\|\leq{\alpha_{t,k-1}}C_{3}\|\mathcal{G}_{F}(x_{t,k-1}^{j})\|^{2}$.
Hence, we have

$$ $\displaystyle\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})$ $\displaystyle=-\sum\limits_{\tau=0}^{k-1}\alpha_{t,\tau}(\Lambda_{x_{t}}^{x_{t,\tau}^{j}})^{-1}(\mathcal{G}_{F}(x_{t,\tau}^{j}))+\sum\limits_{\tau=0}^{k-1}\alpha_{t,\tau}e_{t,\tau}^{j},$ (D.8) $$

where we used $\mathrm{R}_{x_{t}}^{-1}(x_{t})=0_{x_{t}}$.
Combining ([D.8](https://arxiv.org/html/2409.07223v2#A4.E8)), $\|(\Lambda_{x_{t}}^{x_{t,k-1}^{j}})^{-1}(\mathcal{G}_{F}(x_{t,k-1}^{j})\|\leq C_{2}\|\mathcal{G}_{F}(x_{t,k-1}^{j})\|$ (for all $t=1,2,\dots,T-1$ and $k=1,2,\dots,K-1$), and
$\|\sum_{i=1}^{n}u_{i}\|^{2}\leq n\sum_{i=1}^{n}\|u_{i}\|^{2}$ yields the desired result.
∎

When $\mathcal{M}$ reduces into a Euclidean space, e.g., $\mathcal{M}=\mathbb{R}^{d}$, the constants in Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2) will become $C_{2}=1$ and $C_{3}=0$. In this case, the results correspondingly becomes
$\|x_{t}-x_{t,k}^{j}\|^{2}\leq k\sum_{\tau=0}^{k-1}\alpha_{t,\tau}^{2}\|\mathcal{G}_{F}(x_{t,\tau}^{j})\|^{2}.$
In Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2), if one uses $\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})$ to replace $\mathcal{G}_{F}(x_{t,k}^{j})$, then the desired result is obtained in Lemma [D.3](https://arxiv.org/html/2409.07223v2#A4.Thmlemma3).

###### Lemma D.3 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.3](https://arxiv.org/html/2409.07223v2#S3.Thmassumption3), at the $k$-th inner iteration of the $t$-th outer iteration of Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1), for each agent $j\in\mathcal{S}_{t}$ and $k=1,2,\dots,K-1$, we have

$$ $\displaystyle\|\mathrm{R}^{-1}_{{x}_{t}}(x_{t,k}^{j})\|^{2}\leq 2k^{2}{\alpha}_{t}^{2}P^{2}(J^{2}+{\alpha}^{2}_{t}P^{2}H^{2}),$ (D.9) $$

where $P$ is a positive constant such that for all $x\in\mathcal{W}$, $j=1,2,\dots,N$ and $\xi\sim\mathcal{D}_{j}$, it holds that $\|\mathrm{grad}F(x)\|\leq P$, $\|\mathrm{grad}f_{j}(x)\|\leq P$ and $\|\mathrm{grad}f_{j}(x;\xi)\|\leq P$ by Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2).

###### Proof of Lemma D.3 .

From Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1), letting $\mathcal{G}_{F}(x^{j}_{t,k})=-\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})$, then, we have

$$ $\displaystyle\|\mathcal{G}_{F}(x_{t,k}^{j})\|$ $\displaystyle=\left\|-\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\right\|\leq\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\|\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\|\leq P.$ $$

Hence, combining the inequality above and Lemma [D.2](https://arxiv.org/html/2409.07223v2#A4.Thmlemma2) gives rise to the desired result ([D.9](https://arxiv.org/html/2409.07223v2#A4.E9)).
∎

Under the same conditions as Lemma [D.1](https://arxiv.org/html/2409.07223v2#A4.Thmlemma1), plugging ([D.9](https://arxiv.org/html/2409.07223v2#A4.E9)) into ([D.4](https://arxiv.org/html/2409.07223v2#A4.E4)) yields

$$ $\displaystyle\mathbb{E}_{t}[\left<\mathrm{grad}F({x}_{t}),\mathrm{R}_{{x}_{t}}^{-1}({x}_{t+1})\right>]\leq-\frac{\varpi\alpha_{t}}{2}\sum_{k=0}^{K-1}\mathbb{E}_{t}\left[\left\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\right\|^{2}\right]$ $\displaystyle-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+{\varpi\alpha_{t}^{2}KGP^{2}\delta_{2}^{2}}+\frac{1}{6}{(2K-1)K(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\varpi\alpha_{t}^{3}}.$ (D.10) $$

The next is to bound the second term $\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\|^{2}]$.

###### Lemma D.4 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8), the iterates $\{x_{t}\}_{t=1}^{T}$ generated by Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with fixed stepsize $\alpha_{t}$ and fixed batchsize $B_{t}$ within parallel inner iterations satisfies

$$ $\displaystyle\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\|^{2}]$ $\displaystyle\leq\frac{\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}\sigma^{2}_{L}\delta_{3}^{2}K}{B_{t}}+{\varpi^{2}\alpha_{t}^{2}K}\sum_{k=0}^{K-1}\mathbb{E}_{t}\left[\left\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\right\|^{2}\right]$ $\displaystyle\quad+{\varpi^{2}\alpha_{t}^{2}P^{2}K^{2}}\delta_{4}^{2}$ (D.11) $$

where $\delta_{3}^{2}=\frac{1}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}}{(q_{t}^{j})^{2}}$ and $\delta_{4}^{2}=\frac{1}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}(1-p_{j})}{(q_{t}^{j})^{2}}$.

###### Proof of Lemma D.4 .

Let ${x}_{t}$ denote the $t$-th aggregation by the server.
Then,

$$ $\displaystyle\mathbb{E}_{t}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t,k}^{j})\|^{2}]=\varpi^{2}\alpha_{t}^{2}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j\in\mathcal{S}_{t}}\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle=\varpi^{2}\alpha_{t}^{2}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\mathbb{I}_{\mathcal{S}_{t}}(j)\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle={\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\mathbb{I}_{\mathcal{S}_{t}}(j)\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})-\mathrm{grad}f_{j}(x_{t,k}^{j})$ $\displaystyle\quad+\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle={\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{\mathbb{I}_{\mathcal{S}_{t}}(j)}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})-\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle\quad+{\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\mathbb{I}_{\mathcal{S}_{t}}(j)\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle={\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{\mathbb{I}_{\mathcal{S}_{t}}(j)}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})-\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle\quad+{\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}(\mathbb{I}_{\mathcal{S}_{t}}(j)-p_{j}+p_{j})\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg\|^{2}\bigg]$ $\displaystyle\leq\frac{\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}\sigma_{L}^{2}K}{N^{2}B_{t}}\sum_{j=1}^{N}\frac{p_{j}}{(q_{t}^{j})^{2}}+{\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}(\mathbb{I}_{\mathcal{S}_{t}}(j)-p_{j})\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg]$ $\displaystyle\quad+{\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg]$ $\displaystyle=\frac{\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}\sigma^{2}_{L}K}{N^{2}B_{t}}\sum_{j=1}^{N}\frac{p_{j}}{(q_{t}^{j})^{2}}+\frac{\varpi^{2}\alpha_{t}^{2}}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}(1-p_{j})}{(q_{t}^{j})^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg]$ $\displaystyle\quad+{\varpi^{2}\alpha_{t}^{2}}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg]$ $\displaystyle\leq\frac{\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}\sigma^{2}_{L}\delta_{3}^{2}K}{B_{t}}+{\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}P^{2}K^{2}}\delta_{4}^{2}+{\varpi^{2}\alpha_{t}^{2}K}\sum_{k=0}^{K-1}\mathbb{E}_{t}\bigg[\bigg\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\bigg\|^{2}\bigg]$ $$

where the fourth equality follows that

$$ $\displaystyle\mathbb{E}\left[\sum_{j=1}^{N}\sum_{k=0}^{K-1}\frac{\mathbb{I}_{\mathcal{S}_{t}}(j)}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})\bigg)\right]=\sum_{j=1}^{N}\sum_{k=0}^{K-1}\frac{\mathbb{I}_{\mathcal{S}_{t}}(j)}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))$ $$

and that $\mathbb{E}[\|u\|^{2}]=\mathbb{E}[\|u-\mathbb{E}[u]\|^{2}]+\|\mathbb{E}[u]\|^{2}$, the first inequality follows that

$$ $\mathbb{E}\bigg[\sum_{j=1}^{N}\sum_{k=0}^{K-1}\frac{\mathbb{I}_{\mathcal{S}_{t}}(j)}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}\bigg(\frac{1}{B_{t}}\sum_{b\in\mathcal{B}_{t,k}^{j}}\mathrm{grad}f_{j}(x_{t,k}^{j};\xi_{t,k,b}^{j})-\mathrm{grad}f_{j}(x_{t,k}^{j})\bigg)\bigg]=0$ $$

and that $\mathbb{E}[\|\sum_{i=1}^{n}u_{i}\|^{2}]=\sum_{i=1}^{n}\mathbb{E}[\|u_{i}\|^{2}]$ with $u_{i}$ being independent and having zero mean, that $\|\mathcal{T}_{\eta}(\zeta)\|\leq\Upsilon$ (Assumption [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)), and Assumption [3.6](https://arxiv.org/html/2409.07223v2#S3.Thmassumption6),
the sixth equality follows that

$$ $\displaystyle\mathbb{E}\left[\sum_{j=1}^{N}(\mathbb{I}_{\mathcal{S}_{t}}(j)-p_{j})\frac{1}{q_{t}^{j}N}\sum_{k=0}^{K-1}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\right]=0,$ $$

and that $\mathbb{E}[(\mathbb{I}_{\mathcal{S}_{t}}(j)-p_{j})^{2}]=p_{j}(1-p_{j})$,
and the last inequality follows that $\delta_{3}^{2}=\max_{t\geq 1}\left\{\frac{1}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}}{(q_{t}^{j})^{2}}\right\}$, $\delta_{4}^{2}=\max_{t\geq 1}\left\{\frac{1}{N^{2}}\sum_{j=1}^{N}\frac{p_{j}(1-p_{j})}{(q_{t}^{j})^{2}}\right\}$,
and $\|\sum_{i=1}^{n}u_{i}\|^{2}\leq n\sum_{i=1}^{n}\|u_{i}\|^{2}$.
∎

Now we can formally state the descent lemma in the Riemannian FL setting.

###### Lemma D.5 .

Under Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8), we run Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with batch size $B_{t}$ and step sizes $\varpi>0$ and $\{\alpha_{t}\}$ satisfying

$$ $1\geq KL_{g}\varpi\alpha_{t}.$ (D.12) $$

Then, we have

$$ $\displaystyle\mathbb{E}_{t}[F(x_{t+1})]-F(x_{t})$ $\displaystyle\leq-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+{\varpi\alpha_{t}^{2}K}Q(K,B_{t},\alpha_{t},\varpi),$ (D.13) $$

where $Q(K,B_{t},\alpha_{t},\varpi)=(2K-1)(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\alpha_{t}/{6}+GP^{2}\delta_{2}^{2}+\Upsilon^{2}P^{2}\delta_{4}^{2}KL_{g}\varpi+\frac{L_{g}\delta^{2}_{3}\sigma_{L}^{2}\Upsilon^{2}\varpi}{2B_{t}}$.

###### Proof of Lemma D.5 .

By the $L_{g}$-retraction smoothness of $F$, it follows for $t\geq 1$ that

$$ $F(x_{t+1})\leq F(x_{t})+\left<\mathrm{grad}F(x),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\right>+\frac{L_{g}}{2}\|\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\|^{2},$ $$

where the existence of $\mathrm{R}_{x_{t}}^{-1}(x_{t+1})$ is guaranteed by Assumption [3.2](https://arxiv.org/html/2409.07223v2#S3.Thmassumption2). Taking expectation on both sides over the randomness over the $t$-th outer iteration yields

$$ $\displaystyle\mathbb{E}_{t}[F(x_{t+1})]\leq F(x_{t})+\mathbb{E}_{t}[\left<\mathrm{grad}F(x_{t}),\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\right>]+\frac{L_{g}}{2}\mathbb{E}[\|\mathrm{R}_{x_{t}}^{-1}(x_{t+1})\|^{2}].$ (D.14) $$

Inequality ([D.14](https://arxiv.org/html/2409.07223v2#A4.E14)) together with Lemmas [D.1](https://arxiv.org/html/2409.07223v2#A4.Thmlemma1), [D.3](https://arxiv.org/html/2409.07223v2#A4.Thmlemma3), and [D.4](https://arxiv.org/html/2409.07223v2#A4.Thmlemma4) give rise to

$$ $\displaystyle\mathbb{E}_{t}[F(x_{t+1})]-F(x_{t})\leq-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+\frac{1}{6}{(2K-1)K(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\varpi\alpha_{t}^{3}}$ $\displaystyle\quad-\frac{\varpi\alpha_{t}}{2}(1-KL_{g}\varpi\alpha_{t})\sum_{k=0}^{K-1}\mathbb{E}_{t}\left[\left\|\sum_{j=1}^{N}\frac{p_{j}}{q_{t}^{j}N}\mathcal{T}_{\tilde{\eta}_{t,k}^{j}}(\mathrm{grad}f_{j}(x_{t,k}^{j}))\right\|^{2}\right]$ $\displaystyle\quad+{\varpi\alpha_{t}^{2}KGP^{2}\delta_{2}^{2}}+{L_{g}\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}P^{2}K^{2}}\delta_{4}^{2}+\frac{KL_{g}\sigma_{L}^{2}\Upsilon^{2}\delta_{3}^{2}\varpi^{2}\alpha_{t}^{2}}{2B_{t}}.$ (D.15) $$

Under Condition ([D.12](https://arxiv.org/html/2409.07223v2#A4.E12)), the third term on the right-hand side of ([D.15](https://arxiv.org/html/2409.07223v2#A4.E15)) can be discarded and then we obtain

$$ $\displaystyle\mathbb{E}_{t}[F(x_{t+1})]-F(x_{t})$ $\displaystyle\leq-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+{\varpi\alpha_{t}^{2}KGP^{2}\delta_{2}^{2}}+\frac{KL_{g}\sigma_{L}^{2}\Upsilon^{2}\delta_{3}^{2}\varpi^{2}\alpha_{t}^{2}}{2B_{t}}$ $\displaystyle\quad+{L_{g}\varpi^{2}\alpha_{t}^{2}\Upsilon^{2}P^{2}K^{2}}\delta_{4}^{2}+\frac{1}{6}{(2K-1)K(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\varpi\alpha_{t}^{3}}$ $\displaystyle=-\frac{\varpi\alpha_{t}K}{2}\|\mathrm{grad}F(x_{t})\|^{2}+{\varpi\alpha_{t}^{2}K}Q(K,B_{t},\alpha_{t},\varpi)$ $$

where $Q(K,B_{t},\alpha_{t},\varpi)=(2K-1)(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+\alpha_{t}^{2}P^{2}H^{2})\alpha_{t}/{6}+GP^{2}\delta_{2}^{2}+\Upsilon^{2}P^{2}\delta_{4}^{2}KL_{g}\varpi+\frac{L_{g}\delta^{2}_{3}\sigma_{L}^{2}\Upsilon^{2}\varpi}{2B_{t}}$.
∎

Note that $Q(K,B_{t},\alpha_{t},\varpi)$ in ([D.13](https://arxiv.org/html/2409.07223v2#A4.E13)) consists of four error terms: the first one resulted from the agent drift effect and non-I.I.D. setting, the second one brought by the probability approximating, the third one caused by partial participation, and the fourth one caused by the local stochastic gradient.

###### Lemma D.1 .

###### Proof of Lemma D.1 .

###### Lemma D.2 .

###### Theorem D.1 (Inverse function theorem) .

###### Proof of Lemma D.2 .

###### Lemma D.3 .

###### Proof of Lemma D.3 .

###### Lemma D.4 .

###### Proof of Lemma D.4 .

###### Lemma D.5 .

###### Proof of Lemma D.5 .

### D.2 Proof of Theorem 3.1

Now we are ready to prove Theorem [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem1).

###### Theorem 3.2 .

The second condition in ([3.1](https://arxiv.org/html/2409.07223v2#S3.E1)) ensure $\{\alpha_{t}\}\rightarrow 0$, and thus, without loss of generality, we may assume that $L_{g}K\varpi\alpha_{t}\leq 1$ for all $t\in\mathbb{N}_{+}$. Then, it follows from [D.5](https://arxiv.org/html/2409.07223v2#A4.Thmlemma5) that

$$ $\alpha_{t}\|\mathrm{grad}F(x_{t})\|^{2}\leq\frac{2(F(x_{t+1})-\mathbb{E}_{t}[F(x_{t})])}{K\varpi}+{\alpha_{t}^{2}}Q(K,B_{t},\alpha_{t},\varpi).$ $$

Summing the inequality above over $t=1,2,\dots,T$ and taking total expectation yields

$$ $\displaystyle\sum_{t=1}^{T}\alpha_{t}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]$ $\displaystyle\leq\frac{2\mathbb{E}[F(x_{0})-F(x_{T+1})]}{K\varpi}+\sum_{t=1}^{T}{\alpha_{t}^{2}}Q(K,B_{t},\alpha_{t},\varpi)$ $\displaystyle\leq\frac{2(F(x_{0})-F(x^{*}))}{K\varpi}+\sum_{t=1}^{T}{\alpha_{t}^{2}}Q(K,B_{t},\alpha_{t},\varpi).$ $$

Dividing the both side by $A_{T}=\sum_{t=1}^{T}\alpha_{t}$ results in the bound for the weighted average norm of the squared gradients as follows

$$ $\displaystyle\frac{1}{A_{T}}\sum_{t=1}^{T}{\alpha_{t}}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]$ $\displaystyle\leq\frac{2(F(x_{0})-F(x^{*}))}{K\varpi A_{T}}+\frac{1}{A_{T}}\sum_{t=1}^{T}{\alpha_{t}^{2}}Q(K,B_{t},\alpha_{t},\varpi),$ (D.16) $$

which, under Conditions ([3.1](https://arxiv.org/html/2409.07223v2#S3.E1)), implies that

$$ $\lim_{T\rightarrow\infty}\frac{1}{A_{T}}\sum_{t=1}^{T}{\alpha_{t}}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]=0.$ $$

The desired result follows the fact above.
∎

###### Theorem 3.2 .

### D.3 Proof of Theorem 3.2

###### Theorem 3.2 .

By the definition of $\alpha_{t}$, there exists a positive constant $M>0$ such that $\sum_{t=1}^{T}\alpha_{t}^{2}$, $\sum_{t=1}^{T}\alpha_{t}^{3}$, $\sum_{t=1}^{T}\alpha_{t}^{4}$, $\sum_{t=1}^{T}\alpha_{t}^{5}\leq M$ for all $T\geq 1$. Then,

$$ $\displaystyle\sum_{t=1}^{T}\alpha_{t}^{2}Q(K,B_{\mathrm{low}},\alpha_{t},\varpi)$ $\displaystyle\leq\frac{1}{6}(2K-1)(K-1)L_{f}^{2}\delta^{2}_{1}P^{2}(J^{2}+P^{2}H^{2})M$ $\displaystyle\quad+GP^{2}\delta_{2}^{2}M+P^{2}\delta_{4}^{2}KL_{g}\varpi M+\frac{L_{g}\delta^{2}_{3}\sigma_{L}^{2}\Upsilon^{2}\varpi}{2B_{\mathrm{low}}}M.$ (D.17) $$

On the other hand,

$$ $A_{T}=\sum_{t=1}^{T}\frac{\alpha_{0}}{(\beta+t)^{p}}\geq\int_{t=1}^{T+1}\frac{\alpha_{0}}{(\beta+t)^{p}}\mathrm{d}t=\begin{cases}\alpha_{0}(\ln(T+1+\beta)-\ln(\beta+1))&p=1,\\ \frac{\alpha_{0}}{1-p}((T+1+\beta)^{1-p}-(b+1)^{1-p})&p\in(1/2,1),\end{cases}$ $$

which gives

$$ $\displaystyle\frac{1}{A_{T}}\leq\begin{cases}\frac{1}{\alpha_{0}(\ln(T+1+\beta)-\ln(\beta+1))}&p=1,\\ \frac{1-p}{\alpha_{0}((T+1+\beta)^{1-p}-(b+1)^{1-p})}&p\in(1/2,1).\end{cases}$ (D.18) $$

Plugging ([D.3](https://arxiv.org/html/2409.07223v2#A4.Ex55)) and ([D.18](https://arxiv.org/html/2409.07223v2#A4.E18)) into ([D.16](https://arxiv.org/html/2409.07223v2#A4.E16)) ensures the desired result.
∎

In particular, if full agents participate in any round of communication and agents use local full gradient in local updates, implying $G=0$, $\delta_{4}^{2}=0$, and $\sigma_{L}^{2}=0$, then we have

$$ $\sum_{t=1}^{T}\alpha_{t}^{2}Q(K,B_{\mathrm{low}},\alpha_{t},\varpi)=\frac{1}{6}(2K-1)(K-1)L_{f}^{2}\delta_{1}^{2}P^{2}(J^{2}\sum_{t=1}^{T}\alpha_{t}^{3}+P^{2}H^{2}\sum_{t=1}^{T}\alpha_{t}^{4}).$ $$

Hence, we can relax the condition for $\alpha_{t}$ as $\sum_{t=1}^{\infty}\alpha_{t}=\infty$ and $\sum_{t=1}^{\infty}\alpha_{t}^{3}<\infty$. If one takes $\alpha_{t}=\frac{\alpha_{0}}{(\beta+t)^{p}}$ with constants $\alpha_{0},\beta,p=1/3+a$ and $a\in(0,2/3)$ properly small, it follows that

$$ $\frac{1}{A_{T}}\sum_{t=1}^{T}\alpha_{t}\mathbb{E}_{t}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\frac{M(a)}{(\beta+T)^{2/3-a}},$ $$

where $M(a)$ is a constant depended on $a$. The smaller $a$ the larger $M(a)$.

###### Theorem 3.2 .

### D.4 Proof of Theorem 3.3

###### Theorem 3.3 .

By Lemma [D.5](https://arxiv.org/html/2409.07223v2#A4.Thmlemma5) and the RPL condition, we have

$$ $\mathbb{E}_{t}[F(x_{t+1})]-F(x^{*})+(F(x^{*})-F(x_{t}))\leq-\mu\varpi K\alpha_{t}(F(x_{t})-F(x^{*}))+{\varpi\alpha_{t}^{2}K}Q(K,B_{\mathrm{low}},\alpha_{t},\varpi).$ $$

Rearranging this inequality yields

$$ $\displaystyle\mathbb{E}[F(x_{t+1})]-F(x^{*})\leq(1-\mu\varpi K\alpha_{t})(\mathbb{E}[F(x_{t})]-F(x^{*}))+{\varpi\alpha_{t}^{2}K}Q(K,B_{\mathrm{low}},\alpha_{1},\varpi),$ (D.19) $$

where we take the total expectation on both sides.
Subsequently, we prove the desired result by induction. For $t=1$, it follows from the definition of $\nu$. Now assume that ([3.2](https://arxiv.org/html/2409.07223v2#S3.E2)) holds for $t\geq 1$. Then, from ([D.19](https://arxiv.org/html/2409.07223v2#A4.E19)), it follows that

$$ $\displaystyle\mathbb{E}[F(x_{t+1})]-F(x^{*})$ $\displaystyle\leq\left(1-\frac{\beta\mu\varpi K}{\mathfrak{t}}\right)\frac{\nu}{\mathfrak{t}}+\frac{\varpi K\beta^{2}}{\mathfrak{t}^{2}}Q(K,B_{\mathrm{low}},\alpha_{1},\varpi)$ $\displaystyle=\left(\frac{\mathfrak{t}-\beta\mu\varpi K}{\mathfrak{t}^{2}}\right){\nu}+\frac{\varpi K\beta^{2}}{\mathfrak{t}^{2}}Q(K,B_{\mathrm{low}},\alpha_{1},\varpi)$ $\displaystyle=\left(\frac{\mathfrak{t}-1}{\mathfrak{t}^{2}}\right)\nu-\left(\frac{\beta\mu\varpi K-1}{\mathfrak{t}^{2}}\right)\nu+\frac{\varpi K\beta^{2}}{\mathfrak{t}^{2}}Q(K,B_{\mathrm{low}},\alpha_{1},\varpi)$ $\displaystyle\leq\frac{\nu}{\mathfrak{t}+1},$ (D.20) $$

where $\mathfrak{t}=\gamma+t$, the last inequality is due to $-\left(\frac{\beta\mu\kappa K-1}{\mathfrak{t}^{2}}\right)\nu+\frac{\varpi K\beta^{2}}{\mathfrak{t}^{2}}Q(K,B_{\mathrm{low}})\leq 0$ by the definition of $\nu$ and $\mathfrak{t}^{2}\geq(\mathfrak{t}-1)(\mathfrak{t}+1)$.

On the other hand, for any two points $x,y\in\mathcal{W}$, it follows from the $L_{g}$-smoothness of $F$ that

$$ $F(y)\leq F(x)+\left<\mathrm{grad}F(x),\mathrm{R}_{x}^{-1}(y)\right>+\frac{L_{g}}{2}\|\mathrm{R}_{x}^{-1}(y)\|^{2}.$ $$

Plugging $y=\mathrm{R}_{x}(-\frac{1}{L_{g}}\mathrm{grad}F(x))$ into the inequality above yields

$$ $F(x^{*})\leq F(y)\leq F(x)-\frac{1}{2L_{g}}\|\mathrm{grad}F(x)\|^{2},$ $$

which gives $\frac{1}{2L_{g}}\|\mathrm{grad}F(x)\|\leq F(x)-F(x^{*})$. Replacing $x$ with $x_{t}$ and plugging the replaced inequality into Inequality ([D.4](https://arxiv.org/html/2409.07223v2#A4.Ex60)) yields

$$ $\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\frac{2L_{g}\nu}{\gamma+t},$ $$

which completes the proof.
∎

###### Theorem 3.3 .

### D.5 Proof of Theorem 3.4

Here we rewrite Theorem [3.5](https://arxiv.org/html/2409.07223v2#S3.Thmtheorem5) as the following more complete statement.

###### Theorem D.2 .

Suppose that Assumptions [3.1](https://arxiv.org/html/2409.07223v2#S3.Thmassumption1)-[3.8](https://arxiv.org/html/2409.07223v2#S3.Thmassumption8) hold. We run Algorithm [1](https://arxiv.org/html/2409.07223v2#alg1) with a fixed global step size $\varpi$, a fixed batch size $B$, and a fixed number of local updates $K$.

- 1.
If the fixed step sizes $\alpha$ and $\varpi$ satisfy $\alpha\varpi KL_{g}\leq 1$, then
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]$
$\displaystyle\leq\frac{2\Theta(x_{1})}{\varpi\alpha KT}+{2\alpha Q(K,B,\alpha,\varpi)}.$
(D.21)
- 2.
If local full gradient descent step is performed in local updates, i.e., $\sigma_{L}=0$, and one takes a local fixed step size $\alpha>0$ such that $\alpha=\sqrt{\frac{\Theta(x_{1})}{2\varpi P^{2}(G\delta_{2}^{2}+\Upsilon^{2}\delta_{4}^{2}KL_{g}\varpi)KT}}$ with $T$ satisfying
$T\geq\max\left\{\frac{\varpi KL_{g}^{2}\Theta(x_{1})}{2P^{2}(G\delta_{2}^{2}+KL_{g}\varpi\Upsilon^{2}\delta_{4}^{2})},\frac{\Theta(x_{1})(2K-1)^{2}(K-1)^{2}L_{f}^{4}\delta_{1}^{4}(\varpi^{2}L_{g}^{2}J^{2}K^{2}+P^{2}H^{2})^{2}}{72P^{2}L_{g}^{4}K^{4}\varpi^{5}(G\delta_{2}^{2}+KL_{g}\varpi\Upsilon^{2}\delta_{4}^{2})^{3}}\right\},$
then
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq 4P\sqrt{2\Theta(x_{1})\left(\frac{G\delta_{2}^{2}}{\varpi KT}+\frac{L_{g}\Upsilon^{2}\delta_{4}^{2}}{T}\right)}.$
- 3.
If the true probabilities are known, meaning $G=0$, and
one takes local and global step sizes $\alpha$ and $\varpi$ such that $\alpha\varpi=\sqrt{\frac{\Theta(x_{1})B}{(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)\Upsilon^{2}L_{g}KT}}$ with $T$ satisfying
$T\geq\max\bigg\{\frac{KL_{g}\Theta(x_{1})B}{(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)\Upsilon^{2}},$ $\frac{\Theta(x_{1})(2K-1)^{2}(K-1)^{2}L_{f}^{4}\delta_{1}^{4}P^{4}(L_{g}^{2}\varpi^{2}J^{2}K^{2}+P^{2}H^{2})^{2}B^{3}}{9(\delta_{3}^{2}\sigma_{L}^{2}+2P^{2}\delta_{4}^{2}KB)^{3}\Upsilon^{6}L_{g}^{7}\varpi^{6}K^{5}}\bigg\},$
then
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq 4\Upsilon\sqrt{L_{g}\Theta(x_{1})\left(\frac{\delta_{3}^{2}\sigma_{L}^{2}}{KTB}+\frac{2P^{2}\delta_{4}^{2}}{T}\right)}.$

###### Proof.

Item [1](https://arxiv.org/html/2409.07223v2#A4.I1.i1). Using $\alpha_{t}=\alpha$ and $B_{t}=B$ in Lemma [D.5](https://arxiv.org/html/2409.07223v2#A4.Thmlemma5), we have

$$ $\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]\leq\frac{2\mathbb{E}[F(x_{t})-F(x_{t+1})]}{\varpi\alpha K}+{2\alpha Q(K,B,\alpha_{t},\varpi)}.$ $$

Summing the inequality above over $t=1,2,\dots,T$ gives rise to

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\|\mathrm{grad}F(x_{t})\|^{2}]$ $\displaystyle\leq\frac{2\mathbb{E}[F(x_{0})-F(x_{T+1})]}{\varpi\alpha KT}+{2\alpha Q(K,B,\alpha,\varpi)}$ $\displaystyle\leq\frac{2(F(x_{0})-F(x^{*}))}{\varpi\alpha KT}+{2\alpha Q(K,B,\alpha,\varpi)},$ $$

where the last inequality follows $F(x^{*})\leq F(x_{T+1})$.
Item [2](https://arxiv.org/html/2409.07223v2#A4.I1.i2). In particular, suppose that let $\alpha$ and $\varpi$ satisfy

$$ $\displaystyle\frac{1}{6}(2K-1)(K-1)L_{f}^{2}\delta_{1}^{2}P^{2}(J^{2}+\alpha^{2}P^{2}H^{2})\alpha\leq GP^{2}\delta_{2}^{2}+\Upsilon^{2}P^{2}\delta_{4}^{2}KL_{g}\varpi.$ (D.22) $$

Define $h(\alpha)=\frac{2\Theta(x_{1})}{\varpi\alpha KT}+4\alpha GP^{2}\delta_{2}^{2}+4\Upsilon^{2}P^{2}\delta_{4}^{2}KL_{g}\varpi\alpha$. Solving $\alpha^{*}=\operatorname*{arg\,min}_{\alpha>0}h(\alpha)$ results in

$$ $\displaystyle\alpha^{*}=\sqrt{\frac{\Theta(x_{1})}{2\varpi P^{2}(G\delta_{2}^{2}+\Upsilon^{2}\delta_{4}^{2}KL_{g}\varpi)KT}},\hbox{ and }h(\alpha^{*})=4P\sqrt{2\Theta(x_{1})\left(\frac{G\delta_{2}^{2}}{\varpi KT}+\frac{L_{g}\Upsilon^{2}\delta_{4}^{2}}{T}\right)}.$ $$

Taking

$$ $T\geq\max\left\{\frac{\varpi KL_{g}^{2}\Theta(x_{1})}{2P^{2}(G\delta_{2}^{2}+KL_{g}\varpi\Upsilon^{2}\delta_{4}^{2})},\frac{\Theta(x_{1})(2K-1)^{2}(K-1)^{2}L_{f}^{4}\delta_{1}^{4}(\varpi^{2}L_{g}^{2}J^{2}K^{2}+P^{2}H^{2})^{2}}{72P^{2}L_{g}^{4}K^{4}\varpi^{5}(G\delta_{2}^{2}+KL_{g}\varpi\Upsilon^{2}\delta_{4}^{2})^{3}}\right\}$ $$

can ensure that $\alpha^{*}\varpi KL_{g}\leq 1$ and that ([D.22](https://arxiv.org/html/2409.07223v2#A4.E22)) holds. Hence, the left-hand side of ([D.21](https://arxiv.org/html/2409.07223v2#A4.E21)) is not greater than $h(\alpha^{*})$. The proof for Item [3](https://arxiv.org/html/2409.07223v2#A4.I1.i3) is similar to that for Item [2](https://arxiv.org/html/2409.07223v2#A4.I1.i2).
∎

###### Remark D.1 .

Continuing with Remark [3.3](https://arxiv.org/html/2409.07223v2#S3.Thmremark3), If the probabilities $p_{i}$ are known, i.e., $q_{t}^{i}=p_{i}$, and $p_{\min}=\min_{i}\{p_{i}\}$ is not too small and not fairly far away from $p_{\max}=\max_{i}\{p_{i}\}$, Item [2](https://arxiv.org/html/2409.07223v2#A4.I1.i2) gives the upper bound as $\mathcal{O}(\frac{1}{\sqrt{\varpi KT}})+\mathcal{O}(\frac{1}{\sqrt{p_{\min}NT}})$.
In particular, if $p_{i}=\frac{S}{N}$ with $S\leq N$, the upper bound becomes $\mathcal{O}(\frac{1}{\sqrt{\varpi KT}})+\mathcal{O}(\frac{1}{\sqrt{ST}})$.

###### Theorem D.2 .

###### Proof.

###### Remark D.1 .

### D.6 Proof of Theorem 3.5

###### Theorem 3.5 .

Using a fixed stepsize $\alpha_{t}=\alpha\leq 1/(\mu\varpi K)$ satisfying Condition ([D.12](https://arxiv.org/html/2409.07223v2#A4.E12)) and batchsize $B_{t,k}\in[B_{\mathrm{low}},B_{\mathrm{up}}]$, it follows from ([D.19](https://arxiv.org/html/2409.07223v2#A4.E19)) that

$$ $\mathbb{E}[F(x_{t+1})]-F(x^{*})\leq(1-\mu\varpi K\alpha)\mathbb{E}[F(x_{t})]-F(x^{*})+{\varpi\alpha^{2}K}Q(K,S,B_{\mathrm{low}},\alpha,\varpi),$ $$

which implies that

$$ $\displaystyle\mathbb{E}[F(x_{T})]-F(x^{*})\leq(1-\mu\varpi K\alpha)\mathbb{E}[F(x_{T-1})]-F(x^{*})+{\varpi\alpha^{2}K}Q(K,B_{\mathrm{low}},\alpha,\varpi)$ $\displaystyle\quad\leq(1-\mu\varpi K\alpha)^{2}(\mathbb{E}[F(x_{T-2})]-F(x^{*}))+((1-\mu\varpi K\alpha)+1){\varpi\alpha^{2}K}Q(K,B_{\mathrm{low}},\varrho,\varpi)$ $\displaystyle\quad\dots$ $\displaystyle\quad\leq(1-\mu\varpi K\alpha)^{T-1}(\mathbb{E}[F(x_{1})]-F(x^{*}))+\sum_{\tau=0}^{T-1}(1-\mu\varpi K\alpha)^{\tau}{\varpi\alpha^{2}K}Q(K,B_{\mathrm{low}},\alpha,\varpi)$ $\displaystyle\quad=(1-\mu\varpi K\alpha)^{T-1}\Theta(x_{1})+\frac{1-(1-\mu\varpi K\alpha)^{T}}{\mu\varpi K\alpha}{\varpi\alpha^{2}K}Q(K,B_{\mathrm{low}},\alpha,\varpi)$ $\displaystyle\quad\leq(1-\mu\varpi K\alpha)^{T-1}\Theta(x_{1})+\frac{\alpha}{\mu}Q(K,B_{\mathrm{low}},\alpha,\varpi),$ $$

which completes the proof.
∎

###### Theorem 3.5 .

### D.7 Proof of Theorem 3.6

###### Theorem 3.6 .

Restricting $q_{t}^{i}\in[p_{i}/2,3p_{i}/2]$ yields $\mathbb{P}\{|q_{t}^{i}-p_{i}|\leq p_{i}/2\}\geq 1-\min\{2e^{-tp_{i}^{2}/2},4(1-p_{i})/(tp_{i})\}$ by the Hoeffding’s and Chebyshev’s inequalities. Then

$$ $\left|\frac{1}{q_{t}^{i}}-\frac{1}{p_{i}}\right|=\left|\frac{q_{t}^{i}-p_{i}}{q_{t}^{i}p_{i}}\right|\leq\frac{2}{p_{i}^{2}}|q_{t}^{i}-p_{i}|$ $$

holds with probability not less than $1-\min\{2e^{-tp_{i}^{2}/2},4(1-p_{i})/(tp_{i})\}$. Noting that under $q_{t}^{j}\in[p_{i}/2,3p_{i}/2]$, $\frac{2}{p_{i}^{2}}|q_{t}^{i}-p_{i}|\leq\mathcal{G}t^{-a/2}$ (i.e., $|q_{t}^{i}-p_{i}|\leq\frac{\mathcal{G}}{2}p_{i}^{2}t^{-a/2}$) implies $|(q_{t}^{i})^{-1}-p_{i}^{-1}|\leq\mathcal{G}t^{-a/2}$, and that

$$ $\mathbb{P}\left\{|q_{t}^{i}-p_{i}|\leq\frac{\mathcal{G}}{2}p_{i}^{2}t^{-a/2}\right\}\geq 1-\min\left\{2e^{-\frac{\mathcal{G}^{2}p_{i}^{4}}{2}t^{1-a}},\frac{4(1-p_{i})}{G^{2}p_{i}^{3}t^{1-a}}\right\},$ $$

where we use the Hoeffding’s and Chebyshev’s inequalities again. Let $\mathcal{A}:=\{|(q_{t}^{i})^{-1}-p_{i}^{-1}|\leq\mathcal{G}t^{-a/2}\}$, $\mathcal{B}:=\{q_{t}^{i}\in[p_{i}/2,3p_{i}/2]\}$, and $\mathcal{C}:=\{|q_{t}^{i}-p_{i}|\leq\frac{\mathcal{G}}{2}p_{i}^{2}t^{-a/2}\}$.
The desired result follows $\mathcal{B}\cap\mathcal{C}\subseteq\mathcal{A}$ and $\mathbb{P}\{\mathcal{B}\cap\mathcal{C}\}\geq 1-\mathbb{P}\{\mathcal{B}^{c}\}-\mathbb{P}\{\mathcal{C}^{c}\}$.
∎

###### Theorem 3.6 .

## Appendix E Supplementary Proofs

### E.1 Proof of Theorem 2.1

###### Lemma E.1 .

Let $x_{1},x_{2},\dots,x_{N}$ be independent Bernoulli random variables with $p_{i}>0$, i.e., $x_{i}\sim\mathrm{Bernoulli}(p_{i})$. Then,

$$ $\mathbb{E}\left[\frac{1}{1+\sum_{i=1}^{N}x_{i}}\right]=\int_{0}^{1}\prod_{i=1}^{N}(1-p_{i}+p_{i}t)\mathrm{d}t.$ $$

###### Proof.

Let $S=\sum_{i=1}^{N}x_{i}$. Considering that for any $a>0$, it follows
$\frac{1}{a}=\int_{0}^{\infty}e^{-at}\mathrm{d}t.$
Picking $\alpha=1+S>0$ yields

$$ $\frac{1}{1+\sum_{i=1}^{N}x_{i}}=\frac{1}{1+S}=\int_{0}^{\infty}e^{-t}e^{-St}\mathrm{d}t.$ $$

Taking expectation for both sides of the equality above, we have

$$ $\mathbb{E}\left[\frac{1}{1+\sum_{i=1}x_{i}}\right]=\mathbb{E}\left[\int_{0}^{\infty}e^{-t}e^{-St}\mathrm{d}t\right]=\int_{0}^{\infty}e^{-t}\mathbb{E}[e^{-St}]\mathrm{d}t,$ $$

where the second equality is due to that $e^{-St}$ is a discrete random variable.
Since $x_{i}$ is independent and $S=\sum_{i=1}^{N}x_{i}$, it follows $\mathbb{E}[e^{-St}]=\prod_{i=1}^{N}\mathbb{E}[e^{-x_{i}t}]$. Noting that $\mathbb{E}[e^{-x_{i}t}]=p_{i}e^{-t}+(1-p_{i})$, we obtain $\mathbb{E}[e^{-St}]=\prod_{i=1}^{N}(p_{i}e^{-t}+(1-p_{i}))$. Finally, let $u=e^{-t}$. Then $\mathrm{d}u=-e^{-t}\mathrm{d}t$, $u\rightarrow 1$ as $t\rightarrow 0$, and $u\rightarrow 0$ as $t\rightarrow\infty$. Hence,

$$ $\int_{0}^{\infty}e^{-t}\mathbb{E}[e^{-St}]\mathrm{d}t=\int_{0}^{1}\prod_{i=1}^{N}(1-p_{i}+p_{i}u)\mathrm{d}u,$ $$

which completes the proof.
∎

Now we are ready to prove Theorem [2.1](https://arxiv.org/html/2409.07223v2#S2.Thmtheorem1).

###### Proof of Theorem 2.1 .

At the $t$-th outer iteration, $\mathcal{S}_{t}$ denotes the indices set of agents who send their gradient streams to the server. Let $x_{i}=\begin{cases}1&i\in\mathcal{S}_{t},\\
0&i\notin\mathcal{S}_{t}.\end{cases}$ Then

$$ $\displaystyle\mathbb{E}\left[\sum_{i\in\mathcal{S}_{t}}\frac{1}{|\mathcal{S}_{t}|}\mathrm{grad}f_{i}(x)\right]=\sum_{i=1}^{N}\mathrm{grad}f_{i}(x)\mathbb{E}\left[\frac{x_{i}}{\sum_{i=1}^{N}x_{i}}\right].$ (E.1) $$

Noting that $\mathbb{E}\left[\frac{x_{i}}{\sum_{i=1}^{N}x_{i}}\right]=\mathbb{E}\left[\mathbb{E}\left[\frac{x_{i}}{\sum_{i=1}x_{i}}\right]\bigg|x_{i}\right]=p_{i}\mathbb{E}\left[\frac{1}{1+\sum_{j\not=i}^{N}x_{j}}\right]$. Since $x_{j}\sim\mathrm{Bernoulli}(p_{j})$ is independent, by Lemma [E.1](https://arxiv.org/html/2409.07223v2#A5.Thmlemma1), we have $\mathbb{E}\left[\frac{1}{1+\sum_{j\not=i}^{N}x_{i}}\right]=\int_{0}^{1}\prod_{j\not=i}^{N}(1-p_{j}+p_{j}t)\mathrm{d}t$. Plugging these intermediate results into ([E.1](https://arxiv.org/html/2409.07223v2#A5.E1)) leads to the desired result.
∎

###### Lemma E.1 .

###### Proof.

###### Proof of Theorem 2.1 .

### E.2 Proof of the claim in Remark 3.4

In general, it is difficult to verify directly whether the objective function satisfies the PL (in the Euclidean setting) or RPL (in the Riemannian setting) property. There are some stronger but useful sufficient conditions that imply PL or RPL condition. Specifically, in the Euclidean setting, a strongly convex function satisfies the PL condition [BCN18]. Similarly, in the Riemannian setting, the geodesic strong convexity of real-valued functions implies the RPL property [Bou23]. However, geodesic strong convexity usually requires the use of exponential mapping and its inverse, whose the closed-form expression is not available in some manifolds, e.g., the Stiefel manifold.
In the next theorem, we use a more general notion of the strong convexity of real-valued functions—strong retraction-convexity, in the Riemannian setting than geodesic strong convexity and claim that a strongly retraction-convex function also satisfies RPL condition.

###### Theorem E.1 .

Suppose that function $q:\mathcal{M}\rightarrow\mathbb{R}$ is twice continuously differentiable and $\mu$-strongly retraction-convex with respect to the retraction $\mathrm{R}$ on $\mathcal{W}\subseteq\mathcal{M}$, which is a totally retractive neighborhood of $x^{*}$, a minimizer of $q$ on $\mathcal{W}$. Then,

$$ $q(x)-q(x^{*})\leq\frac{1}{2\mu}\|\mathrm{grad}q(x)\|^{2},$ $$

that is, $q$ satisfies the RPL condition on $\mathcal{W}$.

###### Proof.

From the poof of [HGA15, Lemma 3.2], the $\mu$-strongly retraction-convexity of $q$ implies that

$$ $\displaystyle q(y)-q(x)\geq\left<\mathrm{grad}q(x),\eta\right>+\frac{\mu}{2}\|\eta\|^{2},$ (E.2) $$

for any $x\in\mathcal{W}$, $\eta\in\mathrm{T}_{x}\mathcal{M}$, and $y=\mathrm{R}_{x}(\eta)\in\mathcal{W}$. Define $q_{x}(\eta)=q(x)+\left<\mathrm{grad}q(x),\eta\right>+\frac{\mu}{2}\|\eta\|^{2}$ with $\eta\in\mathrm{T}_{x}\mathcal{M}$, which is $\mu$-strongly convex with respect to $\eta$ (in classical), implying that the unique minimizer of $q_{x}$ is given by
$\eta^{*}=-\frac{1}{\mu}\mathrm{grad}q(x)$.
Thus, $\min_{\eta\in\mathrm{T}_{x}\mathcal{M}}q_{x}(\eta)=q_{x}(\eta^{*})=q(x)-\frac{1}{2\mu}\|\mathrm{grad}q(x)\|^{2}$. It follows from ([E.2](https://arxiv.org/html/2409.07223v2#A5.E2)) that

$$ $q(x^{*})\geq q(x)+\left<\mathrm{grad}q(x),\eta\right>+\frac{\mu}{2}\|\eta\|^{2}\geq q_{x}(\eta^{*})=q(x)-\frac{1}{2\mu}\|\mathrm{grad}q(x)\|^{2},$ $$

which completes the proof.
∎

###### Theorem E.1 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See questions in the weaknesses part.
soundness: 3
strengths: * The proposed aggregation mechanism is novel and easy to follow.
* The paper provides comprehensive convergence analysis.
* The main experiments effectively demonstrate the proposed method’s effectiveness.
summary: This paper proposes a new federated optimization algorithm for learning over Riemannian manifolds. The proposed RFedAGS allows efficient and theoretically sound updates even under partial participation and non-IID data. The authors provide convergence guarantees and validate RFedAGS on synthetic and real datasets, showing consistent improvements over baselines.
weaknesses: * While I understand the reasonableness of $G$, I am wondering what the value of $G$ would be when the true probabilities are not available to the server in the experiments.
* How are the data partitioned across clients? How many total clients are included in the experiments, and what is the client participation ratio?
* The ablation study is somewhat limited, and the sensitivity of several important parameters is missing—for example, different participation ratios, varying numbers of local steps, and comparisons between using approximate probabilities and true probabilities.
* The assumption of Lipschitz continuity for each $f_i$ seems a bit strong, although it may be necessary for the Riemannian SGD convergence analysis. I am also curious whether this Lipschitz continuity can be empirically verified in the experiments.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 2
questions: 1. Can the authors provide empirical or theoretical discussion regarding the scalability of the method as the number of agents, local dataset size, or manifold dimension increases? 
2. Could the method be efficiently applied to other manifolds? Are there limitations?
3. Could the method be compared with recent or advanced Riemannian federated learning algorithms (e.g., Wang et al., 2025 [1]) ?
4. The paper claims computational efficiency due to the removal of exponential/logarithmic maps, yet provides no quantitative analysis.
Could the authors offer detailed communication and computation cost metrics per round, beyond total CPU time, to support this claim?
soundness: 3
strengths: This paper proposes and analyzes RFedAGS, a Riemannian federated learning algorithm that introduces a new and efficient server aggregation scheme based on averaging gradient streams.

The method is designed to effectively handle both partial client participation and data heterogeneity. Theoretical analysis establishes that RFedAGS achieves global convergence and a sublinear convergence rate under decaying step sizes, and further converges sublinearly or linearly to a neighborhood of a stationary point or solution when using fixed step sizes. Extensive experiments on both synthetic and real-world datasets demonstrate the strong empirical performance and stability of the proposed approach.
summary: This paper proposes RFedAGS, a new Riemannian federated learning algorithm that replaces parameter averaging with gradient-stream aggregation to preserve linearity in tangent spaces and improve computational efficiency. RFedAGS proposes an efficient retraction-based aggregation which eliminates the need for the computationally burdensome inverse exponential map or parallel transports required by prior Riemannian FL methods, and theoretically establishes global (and sublinear/linear neighborhood) convergence under various step size regimes. Extensive experimental results are provided across synthetic and real-world tasks, demonstrating RFedAGS’ advantages over competing Riemannian FL baselines under general participation and data heterogeneity.
weaknesses: 1. Limited novelty. The key idea—aggregating gradient flows in tangent space—is conceptually straightforward once the FedAvg update is projected to a manifold setting. 
2. The paper lacks a argument for why RFedAGS offers a distinct or superior geometric interpretation.
3. Limited Scope of Baselines: Although several strong Riemannian FL baselines are included (RFedAvg, RFedSVRG, RFedProj) for targeted tasks, more recent algorithms are not considered, e.g., Wang et al., 2025 [1].
4. Some results tied too closely to specific manifolds. Experiments and implementation notes (Appendix A.3) are mostly focused specific manifolds. Broader applicability to more exotic or high-dimensional manifolds remains an open question
5. Although the authors claim computational efficiency (no need for exponential/logarithmic maps), no quantitative results support this.

[1] Wang H, Pan Z, He C, et al. Federated Learning on Riemannian Manifolds: A Gradient-Free Projection-Based Approach[J]. arXiv preprint arXiv:2507.22855, 2025.

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. Mislabels algorithm in line 438.

2. In A.1.4 it seems like the effect of heterogeneity is almost unseen as the convergence improves consistently when K increases. Is it possible to show results for K > 10? Since the algorithm is not designed to mitigate heterogeneity, there should be a certain level of performance degradation observed with extremely large K.
soundness: 3
strengths: 1. The algorithm avoids the computational burden of exponential map inverses and parallel transport used in earlier Riemannian FL methods.

2. It is the first Riemannian FL method proven to work under arbitrary partial participation.
summary: They propose RFedAGS, a Riemannian Federated Learning algorithm that aggregates gradient streams instead of model parameters to handle manifold curvature and arbitrary partial participation. The method introduces a new aggregation correction AGS-AP, supported by convergence proofs under generalized retraction and bounded vector transport assumptions. Experimental results on several manifold-based tasks  show consistent improvement over prior Riemannian FL baselines.
weaknesses: 1. Theoretical clarity and novelty: While the proposed framework claims to generalize existing Riemannian FL methods by relaxing the requirements on retraction and vector transport, the theoretical advancement remains unclear. Specifically, the main difficulty in proving convergence under assumptions like 3.1, 3.2, and 3.5 is not explicitly articulated. The authors should clarify why convergence analysis becomes more challenging under generalized retraction and bounded vector transport, and in what way their proof techniques go beyond those established in prior works. In other words, the paper should highlight which parts of the analysis cannot be handled by the existing Riemannian FL theoretical tools and why this generalization is nontrivial.

2. Significance of AGS-AP extension: The transition from AGS-RS to AGS-AP appears to be a relatively straightforward correction that compensates for non-uniform participation probabilities by reweighting expectations. While this adjustment enables handling arbitrary participation, it is not evident that it introduces fundamentally new theoretical challenges. The proposed fix seems more like an incremental adaptation rather than a substantial methodological contribution. The authors should therefore elaborate on why the treatment of partial participation in the Riemannian context poses unique analytical obstacles that cannot be addressed by simply adapting existing Euclidean analyses with weighted expectations.

In summary, the current formulation does not convincingly demonstrate that the proposed theoretical extensions constitute a significant leap beyond existing works. The authors are encouraged to explicitly contrast their convergence analysis with prior proofs, detailing where prior methods would fail or become inapplicable under their new setting.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. The convergence proofs rely heavily on Assumption 3.8, which bounds the deviation between estimated and true participation probabilities. However, it remains unclear how $q_{i,t}$ is actually computed during training.
- Are these probabilities updated as empirical participation frequencies over rounds, or are they fixed a priori?
- How sensitive is RFedAGS to inaccurate or time-varying participation estimates (e.g., if some clients drop out permanently)?

2. While the theory emphasizes arbitrary participation and heterogeneous data, the experiments do not explicitly test these conditions.
- Could the authors provide additional experiments that vary (a) the proportion of participating clients per round and (b) the degree of data heterogeneity across clients?
- How does RFedAGS perform compared to baselines as participation becomes sparse or data distributions diverge?

3. The proposed AGS framework involves transporting and averaging gradients in the manifold’s tangent space, which may introduce additional computational overhead compared to standard Riemannian FedAvg.
- How does this affect runtime and communication efficiency when the number of clients or model dimensionality scales up?
- Are there specific manifolds (e.g., Stiefel or SPD) where vector transport becomes a bottleneck?
soundness: 3
strengths: - The paper introduces an aggregation mechanism, Averaging Gradient Streams (AGS), which avoids direct parameter averaging on curved manifolds by accumulating and transporting gradient updates in a common tangent space. This design elegantly resolves the geometric inconsistency inherent in prior Riemannian FL methods and extends federated optimization to non-Euclidean domains under partial client participation—a setting unexplored before.

- The work demonstrates theoretical depth and rigor, providing global and sublinear convergence guarantees under decaying step sizes and linear convergence under Riemannian PL/strong convexity conditions. The proofs are comprehensive, grounded in standard FL and manifold optimization assumptions, and even include a non-trivial probabilistic justification (Assumption 3.8) for estimating client participation probabilities.

- Despite the technical complexity, the paper is logically structured, moving smoothly from motivation to algorithm design, theory, and experiments. The authors provide sufficient mathematical background, clear notation, and consistent use of terminology. While additional intuition could help non-specialists, the exposition is coherent and reproducible, with algorithmic and experimental details clearly documented.

- The proposed RFedAGS algorithm broadens the applicability of federated learning to manifold-constrained models (e.g., SPD matrices, hyperbolic embeddings, Stiefel subspaces), an area of high emerging interest.
summary: The authors propose RFedAGS, a federated learning algorithm optimized for optimization on Riemannian manifolds under realistic scenarios of partial client participation and non-IID data. The method introduces a server aggregation strategy called Averaging Gradient Streams (AGS), which averages transported gradient information instead of local model parameters. This approach addresses the non-linearity of manifolds and avoids costly exponential map computations. The authors theoretically demonstrate global and sublinear convergence under decaying step sizes, as well as sublinear/linear convergence to a neighborhood under fixed step sizes. These results are supported by an assumption that holds with high probability as training progresses. Extensive experiments on both synthetic and real-world manifold-structured datasets showcase RFedAGS’s ability to achieve superior accuracy and faster convergence compared to existing Riemannian FL baselines.
weaknesses: - While the paper is theoretically rigorous, its dense and mathematically demanding nature may hinder its accessibility to a broader audience at ICLR. Consequently, many critical ideas, such as the geometric intuition behind averaging gradient streams and how vector transport preserves consistency, are primarily presented in formal notation.

- Although the paper claims to handle arbitrary participation and non-IID data, the experiments do not explicitly vary these factors to show robustness. It remains unclear how the algorithm performs under different participation rates or degrees of client heterogeneity.

- The convergence proof relies on Assumption 3.8, which establishes a bound on the estimation error between the true and empirical participation probabilities. While this assumption is theoretically justified, the paper lacks a clear description of how these probabilities are computed in practice and how sensitive the algorithm is to their inaccuracies.


Decision: Accept (Poster)