Federated Dynamical Low-Rank Training with Global Loss Convergence Guarantees

## Abstract

Abstract In this work, we propose a federated dynamical low-rank training (FeDLRT) scheme to reduce client compute and communication costs - two significant performance bottlenecks in horizontal federated learning. Our method builds upon dynamical low-rank splitting schemes for manifold-constrained optimization to create a global low-rank basis of network weights, which enables client training on a small coefficient matrix. A consistent global low-rank basis allows us to incorporate a variance correction scheme and prove global loss descent and convergence to a stationary point. Dynamic augmentation and truncation of the low-rank bases automatically optimizes computing and communication resource utilization. We demonstrate the efficiency of FeDLRT in an array of computer vision benchmarks and show a reduction of client compute and communication costs by up to an order of magnitude with minimal impacts on global accuracy.

## 1 Introduction

Federated learning (FL) ; ; ; builds a global model on a central server from data distributed on multiple devices, i.e., clients, by iteratively aggregating local models trained with the computation resource on the clients.
In horizontal FL, where all clients share identical model architecture and data features, computation is often limited by (i) the communication bandwidth between clients and the server and (ii) the restricted compute and memory resources at each client.
The former could be addressed by deploying various compression techniques, such as sparse randomized sketching ; , subsampling , and low-rank approximation ; ; , or by allowing for partial ; ; or asynchronous ; communications.
The latter could be addressed by sparse training ; ; , low-rank training ; ; ; ; , and transfer learning ; .

This work addresses both challenges simultaneously by leveraging dynamical low-rank approximation of the gradient flow with a Galerkin-type operator splitting. It yields a consistent orthogonal low-rank basis across all clients and updates the low-rank factorization without reconstructing the full-weight matrices on either clients or servers. The proposed method yields
1) Efficient communication by only sending and receiving low-rank factors; 2) Low client compute and memory footprint, where the client optimizes only a small coefficient matrix; 3) Automatic server-side compression during training, by augmenting and truncating the weight matrix rank based on the training dynamics. This scheme robustly identifies suitable low-rank manifolds to represent the weight matrices at minimal memory requirements; 4)
Global loss convergence guarantees to a stationary point of the FL problem, since a globally consistent low-rank basis allows formulation of a variance correction  term to bound each client coefficient drift.

We demonstrate a significant performance increase in federated scenarios with many clients compared to non-variance corrected methods.

## 2 Background and problem statement

Federated optimization typically considers distributed setups and with limited communication and limited client compute and memory resources .
In this work, we consider a general federated optimization problem, i.e.,

$$ $\displaystyle\textstyle\min_{w}\mathcal{L}(w)\,:=\,\frac{1}{C}\sum_{c=1}^{C} \mathcal{L}_{c}(w),$ (1) $$

where $w$ is a trainable weight, $\mathcal{L}$ is the global loss function associated to a global dataset $X$, and $\mathcal{L}_{c}$ is the local loss function of client $c$ with local dataset $X_{c}$ in a federated setup with $C$ clients.
For notational simplicity, we consider that $X=\cup_{c=1}^{C}X_{c}$ and each $X_{c}$ is of the same size. Therefore, $\mathcal{L}$ is an average of $\mathcal{L}_{c}$ with uniform weights.
The extension to handle a (non-uniform) weighted average case is straightforward.

Figure: Figure 1: Federated, heterogeneous least squares regression problem, see Section 4.1, for $C=4$ clients, $s_{*}=100$ iterations, learning rate $\lambda=1\rm{e}-3$ and $C$ rank-$1$ local target functions. FL methods without variance correction plateau quickly, whereas FedLin and FeDLRT with variance correction converge to $1\rm{e}-5$. FeDLRT converges faster than FedLin and has lower communication costs.
Refer to caption: x1.png

As the first baseline for federated optimization, we consider FedAvg , see Algorithm 3. Here, each client optimizes its local loss function $\mathcal{L}_{c}$ for $s_{*}$ local iterations using gradient descent,

$$ $\displaystyle\textstyle w_{c}^{s+1}=w_{c}^{s}-\lambda\nabla_{w}\mathcal{L}(w_{ c}^{s}),$ (2) $$

with learning rate $\lambda$, for $s=0,\dots,s_{*}-1$. The initial value for the local iteration is the last global weight, i.e., $w_{c}^{0}=w^{t}$. After local iterations, the weights are communicated to and aggregated at the server to update the global weight following

$$ $\displaystyle\textstyle w^{t+1}=\frac{1}{C}\sum_{c=1}^{C}w_{c}^{s_{*}}.$ (3) $$

Client-drift effect is a common challenge in FL, where the iterative client updates (2) of FedAvg converge to local minima and jeopardize global training performance since the average of the local minimizers may be far away from the global minimizer.
These effects are particularly pronounced for a large number of local iterations $s_{*}$, or high discrepancies between local loss functions $\mathcal{L}_{c}$, as illustrated by Figure 1. Multiple methods ; ; ; ; have been proposed to mitigate this issue. However, these methods often exhibit a speed-accuracy conflict, where learning rates need to be heavily reduced; thus, convergence is slow.

Variance correction(^1^11Variance correction is commonly referred to as “variance reduction” ; .) introduced in the FedLin method  constructs a variance correction term $V_{c}=\nabla_{w}\mathcal{L}_{c}(w^{t})-\frac{1}{C}\sum_{c=1}^{C}\nabla_{w}
\mathcal{L}_{c}(w^{t})$ and modifies the client update iteration to

$$ $\displaystyle w_{c}^{s+1}=w_{c}^{s}-\lambda\left(\nabla_{w}\mathcal{L}(w_{c}^{ s})-V_{c}\right),\qquad s=0,\dots,s_{*}-1.$ (4) $$

This technique leads to global convergence to the minimizer of (1) with constant learning rates for convex $\mathcal{L}$ and else to convergence to a stationary point, at the cost of an additional communication round for computing the variance correction.

Federated neural network training considers problem (1) with the trainable weight $w$ being the set of weight matrices $\left\{W_{i}\right\}_{i}^{L}$ of an $L$ layer neural network. In each iteration, the weight updates in (2) and (4) are applied to all layers simultaneously. Therefore, w.l.o.g., we express the local loss function as $\mathcal{L}_{c}(W)$, where $W\in\mathbb{R}^{n\times n}$ denotes the weight matrix of an arbitrary layer.

Low-rank neural network training: An array of recent work has provided theoretical and experimental evidence that layer weights of over-parameterized networks tend to be low rank ; ; ; and that removing small singular values may even lead to increased model performance while dramatically reducing model size ; in non-federated scenarios.
This beneficial feature has spawned a rich landscape of methods to compress neural networks to a low-rank factorization after training with subsequent fine-tuning ; ; ; , train the factorized network with fixed rank ; ; , dynamically adjust the rank during training ; , or use low-rank adapters for fine-tuning foundation models ; ; .

Why is innovation upon existing low-rank methods needed?
Since FedAvg , several low-rank methods ; ; ; ; ; ; ; have been proposed to increase communication and compute efficiency for FL.
These low-rank methods can be categorized into: 1) methods that purely reduce communication cost by communicating only the low-rank factors obtained by performing a full-size SVD (or similar factorization methods) on the full weight matrix after client optimization ; ; and
2) methods that reduce both communication and client compute costs by learning only low-rank factors on clients ; ; ; ; .

To the best of the authors’ knowledge, there is no existing low-rank method that combines 1) efficient communication, 2)
low client compute and memory footprint, 3) automatic server side compression during training, and 4) global loss convergence guarantees using variance correction in the sense of FedLin , to achieve a globally consistent, robust, and efficient optimization scheme for FL.

## 3 FeDLRT: Federated dynamical low-rank training with variance correction

In this section, we present the core contribution of this paper, federated dynamical low-rank training (FeDLRT), which features a low-rank client optimization step with optional variance correction and an efficient server aggregation process that dynamically determines the optimal weight matrix rank for automatic compression.

FeDLRT builds on the dynamical low-rank approximation (DLRA) method, which was initially proposed for solving matrix equations and recently extended to neural network training ; ; .

Let $\dot{W}(t)=-\nabla_{W}\mathcal{L}(W(t))$ denote the gradient flow for minimizing $\mathcal{L}$.

The DLRA method restricts the trajectory of $W$ to $\mathcal{M}_{r}$, the manifold of $n\times n$, rank-$r$ matrices, by projecting $\dot{W}$ onto a local tangent plane of $\mathcal{M}_{r}$ via an orthogonal projection.
This guarantees a low-rank solution when following the projected dynamics from a low-rank initial guess.

Let the low-rank matrix take the form $W_{r}=USV^{\top}\in\mathcal{M}_{r}$
with $U,V\in\mathbb{R}^{n\times r}$ the orthonormal bases of $\mathcal{M}_{r}$ and $S\in\mathbb{R}^{r\times r}$ the coefficient matrix.
The dynamics for each low-rank factor in DRLA are then derived in (, Proposition 2.1) as

$$ $\displaystyle\textstyle{\begin{aligned} \dot{S}(t)&=-U^{\top}(t)\nabla_{W} \mathcal{L}(U(t)S(t)V(t)^{\top})V(t),\\ \dot{U}(t)&=-\left(I-P_{U(t)}\right)\nabla_{W}\mathcal{L}(U(t)S(t)V(t)^{\top}) V(t)S(t)^{-1},\\ \dot{V}(t)&=-\left(I-P_{V(t)}\right)\nabla_{W}\mathcal{L}(U(t)S(t)V(t)^{\top}) U(t)S(t)^{-\top},\end{aligned}}$ (5) $$

where $P_{U}=UU^{\top}$ and $P_{V}=VV^{\top}$ are the projections onto the column spaces of $U$ and $V$, respectively.
By using the basis update & Galerkin (BUG) scheme , (5) can be split into a basis update step for $U$ and $V$ and a coefficient update step for $S$.
This splitting scheme allows for dynamic adjustment of the rank via a basis augmentation before the coefficient update step and a basis truncation after the coefficient update, as shown in .

In the context of FL, the BUG splitting scheme is particularly interesting since it allows for learning the low-rank bases and coefficients in separate steps. This gives rise to a globally shared basis for the local client iterations, reducing communication and client compute cost of the proposed FeDLRT scheme, see Figure 2: First, the factorization is broadcast to the clients (panel 1), and the basis gradients(^2^22and later on the coefficient gradients for variance correction) $U,V$ are aggregated on the server (panel 2). Next, the basis is augmented on the server (panel 3) and broadcast. On the clients, only the augmented coefficient matrix $S$ is updated repeatedly (panel 4) before aggregation to the server. After aggregation of the local augmented coefficient matrices, redundant basis directions are eliminated to optimize the accuracy-to-compression ratio of the model on the server.

The strategy yields the following benefits compared to “full-rank” FL schemes as FedLin  and low-rank schemes with local compression:
Low client compute cost: Server-based basis augmentation and compression enables an automatic compression without a-priori knowledge of the layer rank $r$ and at no cost for the resource-constrained clients.
The clients only evaluate gradients of low-rank factors and optimize the small matrix $S\in\mathbb{R}^{r\times r}$.
When the clients are equipped with GPUs, this further implies that all “GPU unfriendly” parts of the low-rank scheme, i.e., SVD and QR decomposition for augmenting and compressing the representation, are performed on the server.
Efficient communication: Similar to FedLin, FeDLRT requires in practice two communication rounds – one for aggregating and distributing global gradients for basis augmentation and variance correction and one for aggregating locally updated coefficients. However, communication cost for each round is significantly reduced since only low-rank factors are communicated. We refer to Section 3.3 on communication and compute cost.

Figure: Figure 2: Communication of FeDLRT without variance correction. 1) Broadcast current global basis $U,V$ (blue). 2) Aggregate basis gradients $G_{c,U},G_{c,V}$ (orange). 3) Broadcast global augmented basis $\bar{U},\bar{V}$ (green). 4) Aggregate individual client coefficient update $\widetilde{S}_{c}^{s_{*}}$(purple).
Refer to caption: x2.png

Existing federated low-rank schemes effectively generate individual and incompatible representations of ${{W}_{r}}\in\mathcal{M}_{r}$ for each client. While the factors can still be efficiently communicated, averaging on the server requires a reconstruction of the full weigh matrix $W^{*}=\frac{1}{C}\sum_{c=1}^{C}U_{c}S_{c}V_{c}^{\top}$, since the local manifolds possibly diverge. Thus, the local rank information is lost and needs to be costly recovered by a full $n\times n$ SVD on the server; see Algorithm 6 for details. Since the average of low-rank matrices is not necessarily of low rank, these schemes may lose crucial information on the manifold if client solutions drift too far apart from each other. FeDLRT, in contrast, provides the advantage of client-wide manifold consistency: Splitting the low-rank update and sharing bases amongst clients provides a globally consistent manifold basis. This furthermore allows for bounding the coefficient drift, see Theorem 1, and enables a variance correction for the federated low-rank similar to the FedLin scheme.

### 3.1 Description of Algorithm 1 - FeDLRT

In this section, we elaborate on the details in Algorithm 1.
The orthonormal factors $U^{t},V^{t}$ and the coefficient matrix $S^{t}$ are initialized with rank $r$ and then broadcast to the clients. Note that FeDLRT ensures that, for all $t>1$, $U^{t}$ and $V^{t}$ are orthonormal, and $S^{t}$ is diagonal and full rank.

Basis augmentation of the bases $U^{t}$ and $V^{t}$ is performed using concatenation with the corresponding global basis gradients $G_{U}=\frac{1}{C}\sum_{c=1}^{C}\nabla_{U}\mathcal{L}_{c}(U^{t}S^{t}V^{t,\top})$ and $G_{V}=\frac{1}{C}\sum_{c=1}^{C}\nabla_{V}\mathcal{L}_{c}(U^{t}S^{t}V^{t,\top})$, obtained by aggregating the local basis gradients.
$G_{U}$ and $G_{V}$ encapsulate the gradient flow dynamics (5) projected onto the original bases, thus yielding an intuitive choice for basis augmentation. Further, this choice is consistent with the basis update step of the augmented BUG splitting scheme, see Appendix D, which ensures the robustness of the client optimizer.
Subsequent orthonormalization, e.g., by a QR decomposition, yields the augmented basis, i.e.,

$$ $\displaystyle\textstyle[U^{t}\mid\bar{U}]R=\texttt{qr}([U^{t}\mid G_{U}])\in \mathbb{R}^{n\times 2r},\quad\text{and}\quad[V^{t}\mid\bar{V}]R=\texttt{qr}([V ^{t}\mid G_{V}])\in\mathbb{R}^{n\times 2r}.$ (6) $$

We denote the augmented bases by ${\widetilde{U}}=[U^{t}\mid\bar{U}]$ and ${\widetilde{V}}=[V^{t}\mid\bar{V}]$.
The orthonormalization is performed on the server, providing compute cost reduction for the client.

Basis broadcasting of ${\widetilde{U}}$ and ${\widetilde{V}}$ only requires to broadcast the new bases $\bar{U}$ and $\bar{V}$, since $U^{t}$ and $V^{t}$ are readily available on the clients. Formally, the coefficients $S^{t}$ are projected onto the augmented basis, i.e., ${\widetilde{S}}={\widetilde{U}}^{\top}U^{t}S^{t}V^{t,\top}{\widetilde{V}}\in
\mathbb{R}^{2r\times 2r}$,
before broadcasting them to the clients. Exploiting the orthonormality of the basis results in further reduction of the communication and compute cost:

###### Lemma 1 .

${\widetilde{S}}={\widetilde{U}}^{\top}U^{t}S^{t}V^{t,\top}{\widetilde{V}}$ takes the form ${\widetilde{S}}=\begin{bmatrix}S^{t}&0\\
0&0\end{bmatrix}$.

See Appendix E for the proof.
With Lemma 1, only $\bar{U}$ and $\bar{V}$ have to be broadcast, and the augmented bases and coefficients ${\widetilde{U}}$, ${\widetilde{V}}$, and ${\widetilde{S}}$ can be assembled on each client as needed. Furthermore, only $S\in\mathbb{R}^{r\times r}$, instead of ${\widetilde{S}}\in\mathbb{R}^{2r\times 2r}$, needs to be communicated.

Below, we discuss three options for the client coefficient update step.

Client coefficient update without variance correction is implemented similarly to FedAvg (3). On each client $c$, the augmented coefficient matrix ${\widetilde{S}}_{c}$ is trained for $s_{*}$ iterations(^3^33Our analysis focuses on the case where all clients share the same number of local iterations $s_{*}$. The analysis can be extended to the case where $s_{*}$ is client dependent, following an approach similar to the one in .) with learning rate $\lambda$,

$$ $\displaystyle{\widetilde{S}}_{c}^{s+1}={\widetilde{S}}_{c}^{s}-\lambda\nabla_{ {\widetilde{S}}}\mathcal{L}_{c}({\widetilde{U}}{\widetilde{S}}_{c}^{s}{ \widetilde{V}}^{\top}),\quad s=0,\dots,s_{*}-1,\quad\text{with}\qquad{ \widetilde{S}}_{c}^{s=0}={\widetilde{S}}.$ (7) $$

Client coefficient update with variance correction is required in certain federated scenarios, e.g., the case considered in Figure 1. Based on FedLin , we introduce a correction step for the local coefficient update of FeDLRT.
It extends the above local iteration by another communication round, where the gradient of the augmented coefficients $G_{{\widetilde{S}},c}=\nabla_{\widetilde{S}}\mathcal{L}_{c}({\widetilde{U}}{
\widetilde{S}}{\widetilde{V}}^{\top})$ is computed, aggregated to $G_{\widetilde{S}}=\frac{1}{C}\sum_{c=1}^{C}G_{{\widetilde{S}},c}$ and subsequently broadcast. This yields a correction term $V_{c}=G_{\widetilde{S}}-G_{{\widetilde{S}},c}$ for each client $c$ and thus the client iterations read

$$ $\displaystyle\textstyle{\widetilde{S}}_{c}^{s+1}={\widetilde{S}}_{c}^{s}- \lambda\left(\nabla_{{\widetilde{S}}}\mathcal{L}_{c}({\widetilde{U}}{ \widetilde{S}}_{c}^{s}{\widetilde{V}}^{\top})+V_{c}\right),\quad s=0,\dots,s_{ *}-1,\quad\text{with}\qquad{\widetilde{S}}_{c}^{s=0}={\widetilde{S}}.$ (8) $$

The correction term results in a bound on the coefficient drift and leads to convergence guarantees for FeDLRT, as detailed in Section 3.2.

Client coefficient update with simplified variance correction:
Empirically, we observe that a simplified variance correction, which only considers the correction term of the non-augmented coefficients $S^{t}$, is sufficient, see Figure 5.
The simplified variance correction term takes the form

$$ $\displaystyle\textstyle V_{c}=G_{\widetilde{S}}-G_{{\widetilde{S}},c}\approx \check{V}_{c}:=\check{G}_{\widetilde{S}}-\check{G}_{{\widetilde{S}},c}=\begin{ bmatrix}\nabla_{S}\mathcal{L}(U^{t}S^{t}V^{t,\top})-\nabla_{S}\mathcal{L}_{c}( U^{t}S^{t}V^{t,\top})&0\\ 0&0\end{bmatrix},$ (9) $$

which makes lines 10 and 12 in Algorithm 1 redundant, since $\check{G}_{\widetilde{S}}$ can be aggregated in one step with the basis gradients $G_{U}$,$G_{V}$ in line 4 and broadcast with $\bar{U},\bar{V}$ in line 6, reducing the communication rounds to two - the same as FedLin. See Algorithm 5 for details.

Coefficient averaging is performed after (any of the above variants of) the client iterations. The server computes the updated global coefficients by averaging the local updates, i.e., ${\widetilde{S}}^{*}=\frac{1}{C}\sum_{c=1}^{C}{\widetilde{S}}_{c}^{s_{*}}$.
With the shared augmented bases ${\widetilde{U}}$ and ${\widetilde{V}}$, this is equivalent to the FedAvg aggregation

$$ $\displaystyle\textstyle{\widetilde{W}_{r}}^{*}=\frac{1}{C}\sum_{c=1}^{C}{ \widetilde{W}_{r}}^{s_{*}}=\frac{1}{C}\sum_{c=1}^{C}\left({\widetilde{U}}{ \widetilde{S}}_{c}^{s_{*}}{\widetilde{V}}^{\top}\right)={\widetilde{U}}(\frac{ 1}{C}\sum_{c=1}^{C}{\widetilde{S}}_{c}^{s_{*}}){\widetilde{V}}^{\top}={ \widetilde{U}}{\widetilde{S}}^{*}{\widetilde{V}}^{\top}.$ (10) $$

Since the basis is fixed, the rank $2r$ is preserved in the aggregation, which is
in contrast to other federated low-rank schemes where the aggregated weights could be full rank and, in turn, require a full matrix SVD to determine the new rank ; .

Automatic compression via rank truncation is necessary 1) to identify the optimal rank of the weight matrix and 2) to ensure that $S$ is full rank(^4^44Full rank $S$ is required to show consistency of the basis update step (6) with the robust operator splitting of ; , see Appendix D.).
To this end, a truncated SVD of ${\widetilde{S}}^{*}\in\mathbb{R}^{2r\times 2r}$ is performed, i.e.
$P_{r_{1}},\Sigma_{r_{1}},Q_{r_{1}}^{\top}=\texttt{svd}({\widetilde{S}}^{*})$, where $P_{r_{1}},Q_{r_{1}}\in\mathbb{R}^{2r\times r_{1}}$ and $\Sigma_{r_{1}}=\text{diag}(\sigma_{1},\dots,\sigma_{r_{1}})$ contains the $r_{1}$ largest singular values of ${\widetilde{S}}^{*}$. The new rank $r_{1}$ can be chosen by a variety of criteria, e.g., a singular value threshold $\left\lVert[\sigma_{r_{1}},\dots,\sigma_{2r}]\right\rVert_{2}<\vartheta$.
Once a suitable rank is determined, the factorization is updated by the projection of the bases
$U^{t+1}={\widetilde{U}}P_{r_{1}}\in\mathbb{R}^{n\times r_{1}}$, $V^{t+1}={\widetilde{V}}Q_{r_{1}}\in\mathbb{R}^{n\times r_{1}}$ and update of the coefficient $S^{t+1}=\Sigma_{r_{1}}$. Remarkably, Algorithm 1 is a federated low-rank learning scheme whose solution is close to a full-rank solution, see Theorem 5.

Figure: Algorithm 1 FeDLRT (See Algorithm 2 for auxiliary function definitions)

###### Lemma 1 .

### 3.2 Analysis of FeDLRT with variance correction

In this section, we analyze the FeDLRT algorithm under the general assumption that $\mathcal{L}_{c}$ and $\mathcal{L}$ are $L$-smooth with constant $L$.
Theorems 2 and 3 give the convergence results for FeDLRT with full variance correction (8) in Algorithm 1. Theorem 4 and Corollary 1 provide the convergence for FeDLRT with simplified variance correction in (9), as detailed in Algorithm 5, under additional assumptions given therein.
We note that the analysis does not require convexity of $\mathcal{L}_{c}$ or $\mathcal{L}$.

#### FeDLRT convergence with full variance correction.

The variance-corrected client iteration (8) leads to the following bound the client coefficient drift.

###### Theorem 1 .

Given augmented basis and coefficient matrices ${\widetilde{U}}$, ${\widetilde{V}}$, and ${\widetilde{S}}$.
If the local learning rate $0<\lambda\leq\frac{1}{Ls_{*}}$ with $s_{*}\geq 1$ the number of local steps, for all clients $c$,

$$ $\displaystyle\textstyle\|{\widetilde{S}_{c}^{s}-\widetilde{S}_{c}}\|\leq\exp(1 )s_{*}\lambda\|{\nabla_{\widetilde{S}}\mathcal{L}({\widetilde{U}}{\widetilde{S }}{\widetilde{V}}^{\top})}\|,\quad\textup{for}\quad s=1,\dots,s^{*}-1,$ (11) $$

where $\widetilde{S}_{c}^{s}$ is the variance corrected coefficient as given in (8).

The critical ingredient for the proof, provided in Section F.1, is the globally shared augmented bases. Theorem 1 bounds the drift of the low-rank representations of the local weight, which gives rise to the following global loss descent guarantee.

###### Theorem 2 .

Let $U^{t}S^{t}V^{t,\top}$ and $U^{t+1}S^{t+1}V^{t+1,\top}$ be the factorization before and after iteration $t$ of
Algorithm 1 with variance correction and singular value truncation threshold $\vartheta$. Let the local learning rate be $0<\lambda\leq\frac{1}{12Ls_{*}}$, then the global loss descent is bounded by

$$ $\displaystyle\begin{aligned} \mathcal{L}(U^{t+1}S^{t+1}V^{t+1,\top})-\mathcal{ L}(U^{t}S^{t}V^{t,\top})\leq-s_{*}\lambda(1-12s_{*}\lambda L)\|{\nabla_{ \widetilde{S}}\mathcal{L}({\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top} )}\|^{2}+L\vartheta.\end{aligned}$ (12) $$

The proof is provided in Section F.2.
Theorem 2 paves the way for the following result on convergence to a global stationary point.

**Table 1: Comparison of the computational footprint of FeDLRT with FedAvg, FedLin and several low-rank FL methods. The FeDLRT variants are the only low-rank schemes with linearly scaling (in $n$) memory, compute, and communication costs with automatic compression and variance correction.**
$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}(U^ {t}S^{t}V^{t,\top})\right\rVert^{2}\leq\frac{48L}{T}\left(\mathcal{L}(U^{1}S^{ 1}V^{1,\top})-\mathcal{L}(U^{{T+1}}S^{{T+1}}V^{{T+1},\top})\right)+{48L^{2}}{ \vartheta}.$ (13) $$

###### Theorem 1 .

###### Theorem 2 .

###### Theorem 3 .

#### FeDLRT convergence with simplified variance correction.

FeDLRT with simplified variance correction is detailed in Algorithm 5 with the variance correction term given in (9), which makes variance correction more communication and computation efficient but comes at a cost of the following additional assumption for convergence analysis.

###### Assumption 1 .

There exists $\delta\ll 1$ such that, at each client coefficient update,

$$ $\|{\nabla_{\widetilde{S}}\mathcal{G}({\widetilde{U}}\widetilde{S}_{c}^{s}{ \widetilde{V}}^{\top})}\|-\|{\nabla_{S}\mathcal{G}({\widetilde{U}}\widetilde{S }_{c}^{s}{\widetilde{V}}^{\top})}\|<\delta\|{\nabla_{{\widetilde{S}}}\mathcal{ L}({\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top})}\|,$ (14) $$

for functions $\mathcal{G}=\mathcal{L}$ and $\mathcal{G}=\mathcal{L}_{c}$, $c=1,\dots,C$.

This assumption can be interpreted as that most of dynamics in the gradient flow are captured in the coefficient update for the original rank-$r$ matrix $S$, and the basis augmentation provides little information. This scenario occurs when FeDLRT identifies the optimal rank, which could happen early for simpler problems as shown in Figure 4, or when FeDLRT approaches a stationary point.

###### Theorem 4 .

Under 1, if the local learning rate $0<\lambda\leq\frac{1}{12Ls_{*}}$, then Algorithm 5 leads to the global loss descent

$$ $\displaystyle\mathcal{L}(U^{t+1}S^{t+1}V^{t+1,\top})-\mathcal{L}(U^{t}S^{t}V^{ t,\top})\leq-\mathsf{C}\|{\nabla_{{\widetilde{S}}}\mathcal{L}({\widetilde{W}_{ r}})}\|^{2}+L\vartheta$ $$

with $\mathsf{C}=s_{*}\lambda(1-\delta^{2}-12s_{*}\lambda L+\delta^{2}\,s_{*}\lambda)$.

The proof is provided in Section G.1.
When $\delta$ is small, this bound is slightly weaker than the one in Theorem 2, which leads to the following corollary.

###### Corollary 1 .

Assume that 1 holds.
Algorithm 5 guarantees that, for the local learning rate $0<\lambda\leq\frac{1}{s_{*}(12L+\delta^{2})}$,

$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}(U^ {t}S^{t}V^{t,\top})\right\rVert^{2}\leq$ $\displaystyle\frac{96L}{T}(\mathcal{L}(U^{1}S^{1}V^{1,\top})-$ $\displaystyle\mathcal{L}(U^{{T+1}}S^{{T+1}}V^{{T+1},\top}))+{96L^{2}}{ \vartheta}.$ $$

The proof is analogous to the one for Theorem 3, see Section G.2.

###### Assumption 1 .

###### Theorem 4 .

###### Corollary 1 .

### 3.3 Compute and communication cost

The proposed FeDLRT methods significantly reduce server and client memory footprint, the required communication bandwidth, as well as the client compute cost compared to various baselines, see Section 3.2. On the clients, FeDLRT provides significant memory and compute efficiency since the optimizer only requires the coefficient gradients for the local iterations. To the best of our knowledge, FeDLRT is the only low-rank method with adaptive compression incorporating variance correction, whose server compute cost scales linearly with the layer dimension since the SVD for rank truncation only needs to be computed on the augmented coefficient matrix of size $2r\times 2r$. We remark that the complete federated learning process is performed on the low-rank factors, and the full matrix ${{W}_{r}}$ is never required, as, e.g., in ; . FeDLRT significantly reduces the communication cost between server and clients of a compressed layer and the compute cost on the client and server side, compared to FedLin, see Figure 3, see Algorithm 1. The client cost of the simplified variance corrected FeDLRT, see Algorithm 5 is slightly reduced compared to the full variance corrected since only non-augmented coefficient gradients have to be computed and communicated. However, the asymptotic behavior is the same. Its main advantage is the reduced number of communication rounds.

Figure: Figure 4: Comparison between FeDLRT with simplified variance correction and FedLin in the homogeneous linear least squares regression test. Each line represents the median result of $20$ random initialization with $C$ clients. The plots from left to right show the rank evolution, the distance to the global optimizer, the global loss values by FeDLRT, and the global loss values by FedLin. The results show that FeDLRT converges faster in this low-rank test case by identifying (and never underestimating) the target rank $r=4$ early in the training.
Refer to caption: x4.png

## 4 Numerical evaluation

### 4.1 Distributed linear least squares regression

#### Homogeneous test.

We first consider a (convex) FL problem (1) for linear least squares regression with local loss $\mathcal{L}_{c}(W)=\frac{1}{2\left|X_{c}\right|}\sum_{(x,y)\in X_{c}}\left
\lVert p(x)^{\top}Wp(y)-f(x,y)\right\rVert_{2}^{2}$,
where $W\in\mathbb{R}^{n\times n}$ and $p:[-1,1]\rightarrow\mathbb{R}^{n}$ is the Legendre polynomial basis of degree $n-1$.
The target function $f$ is manufactured as $f(x,y)=p(x)^{\top}W_{r}p(y)$, where $\text{rank}(W_{r})=r$.
We consider problems with $n=20$, $r=4$, and randomly generated $W_{r}$, with $10,000$ data points uniformly sampled on $[-1,1]^{2}$ and uniformly distributed among clients.
We compare FeDLRT with variance correction and FedLin with $s_{*}=20$ local iterations and $\lambda=1e-3$ learning rate on $C=1,2,4,8,16,32$ clients. This setting satisfies the step-size restriction given in Theorem 2.
In FeDLRT, the singular value truncation threshold $\vartheta=\tau||{\widetilde{S}}^{*}||$ with $\tau=0.1$ was used.

Figure 4 reports the dynamically updated ranks, errors, and loss values with respect to the aggregation rounds. The reported data are the medians over $20$ randomly generated initial weights(^5^55We chose to display the median trajectory to point out its convergence and monotonicity. The test case also converges in the mean.)
The results indicate that FeDLRT is able to identify the correct rank within a few aggregation rounds and, furthermore, never underestimates it – which would have increased the loss value significantly.
FeDLRT converges to the minimizer $W^{*}=W_{r}$ up to a $1e-5$ error and converges faster with more clients. On this problem, FeDLRT shows up to 10x faster convergence than FedLin.
We attribute this behavior to the fact that, by identifying a suitable low-rank manifold early in the training, FeDLRT significantly reduces the degrees of freedom in the FL problem.

#### Heterogeneous test.

Inspired by , we consider a variation of the linear least squares regression with $\mathcal{L}_{c}(W)=\frac{1}{2\left|X\right|}\sum_{(x,y)\in X}\left\lVert p(x)^
{\top}Wp(y)-f_{c}(x,y)\right\rVert^{2}$, where the target function $f_{c}$ is different for each client, and the $10,000$ training data points are available to all clients. We choose problem size $n=10$ with $C=4$ clients and use learning rate $\lambda=1\rm{e}-3$ with $s_{*}=100$ local epochs. As seen in Figure 1, FeDLRT with variance correction converges (to single precision accuracy) to the minimizer $W^{*}$ of (1) much faster than FedLin, whereas FeDLRT without correction quickly plateaus, similar to FedAvg.

Figure: Figure 5: Comparisons for training ResNet18 on CIFAR10 benchmark. Top row compares FeDLRT without variance correction to FedAvg, middle and bottom rows compare FeDLRT with full and simplified variance correction to FedLin, respectively. In each row, the left two panels show the model compression ratio and the communication cost reduction from FeDLRT, and the right two panels show the validation accuracy for FeDLRT and the full-rank counterparts. In each plot, the results are reported for $C=1,\dots,16$ or $32$ clients with $240/C$ local iterations. FeDLRT matches the accuracy of FedAvg and FedLin well, while substantially reducing the server and client memory and communication costs. Variance correction leads to an up to $12\%$ increase in validation accuracy for large $C$, mitigating the client drift problem. The simplified variance correction (bottom row) gives comparable results to full version (middle row) at a lower communication and computation cost.
Refer to caption: x8.png

### 4.2 ResNet18 on CIFAR10

We demonstrate the performance of FeDLRT for training the exemplary ResNet18 model on CIFAR10, where we apply FeDLRT to train its fully connected head. The truncation tolerance is set to $\vartheta=\tau||{\widetilde{S}}^{*}||$ with $\tau=0.01$.
The test case setup is summarized in Section B.3. The training data is equally partitioned across clients; see Section B.2 for the data-preprocessing details.
A local iteration of Algorithm 1 at client $c$ describes one mini-batch update on the client training data set $X_{c}$ for a given batch size, $s_{*}$ is the maximum number of local iterations, and $T$ denotes the number of aggregation rounds.
We display the statistics for $10$ random initializations;
each warm-started with $5$ iterations with one client.
We set $s_{*}=240/C$ so that in each training run, the global network iterates through the same amount of data. This setup favors low client counts, and, as expected, the validation accuracy drops as $C$ grows for FedAvg and FeDLRT without variance correction, see Figure 5 (upper row). We note that FeDLRT ties or outperforms FedAvg in terms of accuracy.
Using full variance correction (second row) increases the validation accuracy of FeDLRT by up to $12\%$ in this test case, matching the accuracy of FedLin and enabling FL with $93\%$ accuracy for $32$ clients. For $C=8$ clients, the communication cost saving of the compressed layers is up to $90\%$.
The computationally more efficient simplified variance correction, using Algorithm 5, (third row), yields similar validation accuracy, notably at higher compression ratio and communication cost reduction.
Similar results are obtained for AlexNet, VGG16 on CIFAR10, and ViT on CIFAR100 , see Appendix B, where we observe that FeDLRT closely matches the full-rank accuracy of FedLin.

In conclusion,
we have presented with FeDLRT an efficient low-rank FL scheme with convergence guarantees and automatic server side compression, and demonstrated its capabilities in several test cases. We remark that the underlying assumption for this work is that the target model can be expressed sufficiently well via a low-rank representation.
While this work is baseline algorithmic research, we believe that it leads to positive societal impacts by providing an energy efficient FL algorithm.

## Appendix A Additional algorithms

In the following, we list a set of algorithms that are used in the paper as a contribution or as a baseline method. In particular, Algorithm 2 contains auxiliary function definitions for Algorithm 1 and Algorithm 5.
Algorithm 3 is the standard FedAvg method as presented in []. Algorithm 4 is the FedLin Algorithm [], i.e. the extension of Algorithm 4 with variance correction.
Algorithm 5 represents the FeDLRT method with simplified variance correction, as analyzed in Theorem 4 and Corollary 1 with the additional 1.

Figure: Algorithm 2 Auxiliary functions

Figure: Algorithm 3 FedAvg []. (See Algorithm 2 for auxiliary function definitions)

Figure: Algorithm 4 FedLin []. (See Algorithm 2 for auxiliary function definitions)

Figure: Algorithm 5 FeDLRT with simplified variance correction. (See Algorithm 2 for auxiliary function definitions)

Figure: Algorithm 6 Naive implementation of FeDLRT. (See Algorithm 2 for auxiliary function definitions)

## Appendix B Additional numerical evaluation

### B.1 Compute resources

The convex test cases are computed on a single Nvidia GTX1080ti GPU. The computer vision benchmarks use a set of Nvidia Tesla V100-SXM2-16GB and Tesla P100-PCIE-16GB. For prototyping, a Nvidia RTX 4090 is used.

### B.2 Data augmentation

We use standard data augmentation techniques for the proposed test cases. That is, for CIFAR10, we augment the training data set by a random horizontal flip of the image, followed by a normalization using mean $[0.4914,0.4822,0.4465]$ and std. dev. $[0.2470,0.2435,0.2616]$. The test data set is only normalized.
The same augmentation is performed for CIFAR100, where with mean $[0.5071,0.4867,0.4408]$ and std. dev. $[0.2673,0.2564,0.2762]$.

### B.3 Additional computer vision results

AlexNet on CIFAR10: We train AlexNet on CIFAR10, where the fully connected head of the network is replaced by a low-rank counterpart. A federated neural network setup with $C$ clients trains on $CTs_{*}$ random batches of the dataset, that is the number of seen training data batches scales with the client count.
Figure 6 displays the validation accuracy of FeDLRT with variance correction compared to FedLin, where one can see that the performance of FeDLRT mirrors the performance of FedLin with more degrees of freedom. The measured validation accuracy peaks at $C=4$ clients in both cases, where the higher number of seen training data-points offsets the negative effects of more clients on the validation performance. All reported runs are within close distance of the non-federated, full-rank baseline accuracy of $85.6\%$. Communication cost savings of the fully connected layers amount between $96\%$ and $97\%$ (^6^66For clarity of exposition we consider only the fully connected layers. Taking into account the non low-rank convolution layers, the communication cost savings reduces to $87.5\%$ to $87.3\%$.) We observe, similarly to the results in Section 4.1, that the maximum achieved communication cost savings, which depend on the layer ranks scales with the number of clients $C=4$, indicating that the decay rate of the singular values of the averaged coefficient matrix ${\widetilde{S}}^{*}$ depends on $C$.

Figure: Figure 6: AlexNet CIFAR10 benchmark with fixed number of local iterations. (Left Panel) shows the savings in communication cost of simplified variance corrected FeDLRT vs FedLin. (Mid and right panel) compares the validation accuracy of FeDLRT and FedLin, where we see that FeDLRT behaves similarly to FedLin and achieves accuracy levels near the non-federated baseline value of $85.6\%$.
Refer to caption: x9.png

Figure: Figure 7: VGG16 CIFAR10 benchmark with $240/C$ local iterations for $C$ clients with simplified (lower row) and without (upper row) variance correction. (Left panel) show the savings in communication cost corresponding to FedLin at final time. (Mid and right panel top row) compares the validation accuracy of FeDLRT and FedAvg, where we see that FeDLRT behaves similarly to FedAvg, where higher $C$ correlates with a drop in accuracy. FeDLRT with variance correction mitigates this issue and achieves similar performance as FedLin, close to the non-federated baseline accuracy is $93.15\%$.
Refer to caption: x10.png

Vision Transformer on CIFAR100: We consider a small vision transformer for CIFAR100, with $6$ attention layers with $2$ heads each followed by a ResNet block and a drop-out layer, all with weight matrices of dimension $512\times 512$. The tokenizer takes patches of size $8$ with embedding dimension $512$. Training hyperparameters are given in Section B.3. Remark that we do not aim for SOTA performance, since transformer architectures are notoriously difficult to compress with low-rank approaches, but rather compare the performance of FedLin to FeDLRT for a given compute budget. We use $s_{*}=240/C$ local iterations for $C$ clients. Observe in Figure 8 that FeDLRT achieves similar performance as ViT with over $55\%$ communication cost savings on average.

Figure: Figure 8: ViT CIFAR100 benchmark. (Left Panel) shows the savings in communication cost of variance corrected FeDLRT vs FedLin. (Mid and right panel) compares the validation accuracy of FeDLRT and FedLin, where we see that FeDLRT behaves similarly to FedLin and achieves accuracy levels near the non-federated baseline value of $50\%$, which is similar to literature results [].
Refer to caption: x11.png

**Table 2: Experimental setup object detection benchmarks. All test cases use a cosine annealing learning rate scheduler.**
$$ $\displaystyle\begin{aligned} \dot{K}=-\nabla_{K}\mathcal{L}(K(t)V_{0}^{\top}) \in\mathbb{R}^{n\times r},\quad K(0)=U_{0}S_{0},&\\ \dot{L}=-\nabla_{L}\mathcal{L}(U_{0}L(t)^{\top})\in\mathbb{R}^{n\times r}, \quad L(0)=V_{0}S_{0}^{\top}.\end{aligned}$ (15) $$

## Appendix C Notation overview for the numerical analysis

We establish a set of notations to simplify the notation in the proofs

- •
$\mathcal{L}_{c}(W)$ denotes the local loss function based on dataset $X_{c}$ at client $c$.
- •
$\mathcal{L}(W)=\frac{1}{C}\sum_{c=1}^{C}\mathcal{L}_{c}(W)$ is the global loss function.
- •
$F_{c}(W)=-\nabla_{W}\mathcal{L}_{c}(W)$ is the negate of local loss gradient.
- •
$F(W)=\frac{1}{C}\sum_{c=1}^{C}F_{c}(W)$ is the negate of global loss gradient.
- •
$\mathcal{M}_{r}=\left\{W\in\mathbb{R}^{n\times n}:\text{rank}(W)=r\right\}$ is a manifold of rank $r$ matrices.
- •
$W_{r}=USV^{\top}\in\mathcal{M}_{r}$ is a rank-$r$ approximation of a matrix $W$.
- •
$\mathcal{T}_{W_{r}}\mathcal{M}_{r}$ is the tangent space of $\mathcal{M}_{r}$ at $W_{r}$.
- •
$P(W_{r})$ is the orthogonal projection onto $\mathcal{T}_{W_{r}}\mathcal{M}_{r}$.
- •
$P_{U}=UU^{\top}$ is the orthogonal projection onto the range of orthonormal $U\in\mathbb{R}^{n\times r}$.
- •
$P_{V}=VV^{\top}$ is the orthogonal projection onto the range of orthonormal $V\in\mathbb{R}^{n\times r}$.
- •
When applied to vectors, $\left\lVert\cdot\right\rVert$ denotes the Euclidean norm ($\ell_{2}$-norm). When applied to matrices, $\left\lVert\cdot\right\rVert$ denotes the Frobenius norm.

## Appendix D Efficient basis gradient dynamics for basis augmentation

We first consider the basis update & Galerkin splitting scheme of  (5). The splitting performs a reparametrization of the form $K(t)=U(t)S(t)$ and $L(t)=V(t)S(t)^{\top}$. The basis update then reads

$$ $\displaystyle\begin{aligned} \dot{K}=-\nabla_{K}\mathcal{L}(K(t)V_{0}^{\top}) \in\mathbb{R}^{n\times r},\quad K(0)=U_{0}S_{0},&\\ \dot{L}=-\nabla_{L}\mathcal{L}(U_{0}L(t)^{\top})\in\mathbb{R}^{n\times r}, \quad L(0)=V_{0}S_{0}^{\top}.\end{aligned}$ (15) $$

Given the solution $K(t_{1})$ and $L(t_{1})$ at time $t_{1}$, the bases $U_{0}$ and $V_{0}$ are augmented by the orthonormalization of the new directions $K(t_{1})$ and $L(t_{1})$, i.e.

$$ $\displaystyle\begin{aligned} {\widetilde{U}}R&=\texttt{qr}([U_{0}\mid K(t_{1}) ])\in\mathbb{R}^{n\times 2r},\\ \text{and}\quad{\widetilde{V}}R&=\texttt{qr}([V_{0}\mid L(t_{1})])\in\mathbb{R }^{n\times 2r},\end{aligned}$ (16) $$

where $R$ is the right factor of the respective QR decomposition and can be discarded.
The initial condition of the coefficient update is $S(t_{0})$ projected onto the new bases, i.e.,

$$ $\displaystyle\dot{\widetilde{S}}=-\nabla_{S}\mathcal{L}({\widetilde{U}}{ \widetilde{S}}(t){\widetilde{V}}^{\top}),\quad{\widetilde{S}}(0)={\widetilde{U }}^{\top}U_{0}{\widetilde{S}}(0)V_{0}^{\top}{\widetilde{V}}.$ (17) $$

After the integration of the coefficient dynamics above, the redundant basis functions are typically truncated via an SVD of $S$ ensuring that $S$ is always full rank.
In its continuous form above, the splitting yields a robust integrator for the projected gradient flow, without manifold dependent step-size restrictions:

###### Theorem 5 .

([])
Assume $\mathcal{L}$ is $L$-smooth with constant $L$, and locally bounded by $B$. Let ${{W}_{r}}(t)$ be the low-rank continuous time solution of (15) and (17) and let $W(t)$ be the full rank solution at $t=0$. Assume the $K,L,$ and $S$ equations are integrated exactly from time $t=0$ to $\Delta t$. Assume that for any $Y\in\mathcal{M}_{r}$ sufficiently close to ${{W}_{r}}(t)$ the gradient $F(Y)$ is $\epsilon$ close to $\mathcal{M}_{r}$. Then

$$ $\displaystyle\left\lVert W(\Delta t)-{{W}_{r}}(\Delta t)\right\rVert\leq d_{1} \epsilon+d_{2}\Delta t+d_{3}\frac{\vartheta}{\Delta t},$ $$

where $d_{1},d_{2},d_{3}$ depend only on $L$ and $B$.

The theorem guarantees, that the low-rank representation does not imply any step-size restrictions on the optimization scheme. This is in stark contrast to a naive alternating descent optimization of the low-rank factors $U,S,V$.

To build an discretized numerical optimizer in a resource constrained federated scenario from the above continuous splitting equations, we avoid the reparametrization, which implies a $200\%$ memory cost increase on the client side, since three versions of the low-rank layer need to be tracked.

###### Lemma 2 .

Let $USV\in\mathcal{M}_{r}$ be a low rank factorization that follows the projected gradient (5) flow using the splitting scheme (15) with $K=US$ and $V=VS^{\top}$.
Further, assume that equations for the $K$ and $L$ factors are solved by an explicit Euler time integration with learning rate $\lambda$, i.e.

$$ $\displaystyle\begin{aligned} K(t_{1})=K(0)-\lambda\nabla_{K}\mathcal{L}(K(0)V_ {0}^{\top}),\quad K(0)=U_{0}S_{0},&\\ L(t_{1})=L(0)-\lambda\nabla_{L}\mathcal{L}(U_{0}L(0)^{\top}),\quad L(0)=V_{0}S _{0}^{\top}.\end{aligned}$ (18) $$

Then, the basis augmentation (16) can be expressed as

$$ $\displaystyle\begin{aligned} {\widetilde{U}}R&=\texttt{{qr}}([U_{0}\mid-\nabla _{U}\mathcal{L}\big{(}U_{0}S_{0}V_{0}^{\top})])\in\mathbb{R}^{n\times 2r},\\ \text{and}\quad{\widetilde{V}}R&=\texttt{{qr}}([V_{0}\mid-\nabla_{V}\mathcal{L }\big{(}U_{0}S_{0}V_{0}^{\top})])\in\mathbb{R}^{n\times 2r}.\end{aligned}$ (19) $$

and maintains the structure of the basis update and Galerkin operator split.

###### Proof.

We consider the proof for the $K$ equation and the $U$ basis; the proof for $L$ and $V$ follows analogously.

Considering  (16), we obtain with the explicit Euler discretization  (18),

$$ $\displaystyle\begin{aligned} \mathrm{span}\left([U_{0}\mid K(t_{1})]\right)&= \mathrm{span}\left([U_{0}\mid U_{0}-\lambda\nabla_{K}\mathcal{L}(K(0)V_{0}^{ \top})]\right)\\ &=\mathrm{span}\left([U_{0}\mid-\lambda\nabla_{K}\mathcal{L}(K(0)V_{0}^{\top}) ]\right)\\ &=\mathrm{span}\left([U_{0}\mid-\nabla_{K}\mathcal{L}(K(0)V_{0}^{\top})]\right ).\end{aligned}$ (20) $$

Next, consider the continuous time dynamics of $\dot{K}$, where we omit explicit time dependence on $U,S,V$ and $K$ for the sake of brevity, i.e.,

$$ $\displaystyle\begin{aligned} \dot{K}&=\dot{\left(US\right)}\\ &=\dot{U}S+U\dot{S}\\ &\overset{\text{~{}\eqref{eq:gradient_flow_system}}}{=}-(I-UU^{\top})\nabla_{W }\mathcal{L}(USV^{\top})VS^{-1}S-UU^{\top}\nabla_{W}\mathcal{L}(USV^{\top})V\\ &=-(I-P_{U})\nabla_{W}\mathcal{L}(USV^{\top})V-P_{U}\nabla_{W}\mathcal{L}(USV^ {\top})V\\ &=(P_{U}-I)\nabla_{W}\mathcal{L}(USV^{\top})V-P_{U}\nabla_{W}\mathcal{L}(USV^{ \top})V\\ &=-\nabla_{W}\mathcal{L}(USV^{\top})V\end{aligned}$ (21) $$

Further, using the chain rule, we observe

$$ $\displaystyle\nabla_{U}\mathcal{L}(USV^{\top})=\nabla_{W}\mathcal{L}(USV^{\top })\nabla_{U}(USV^{\top})=\nabla_{W}\mathcal{L}(USV^{\top})VS^{\top}$ $$

Thus, $-\nabla_{U}\mathcal{L}(USV^{\top})S^{-\top}=-\nabla_{W}\mathcal{L}(USV^{\top})
V=\dot{K}$.
Full rankness of $S$ and  (21) yield that $\mathrm{span}(-\nabla_{U}\mathcal{L}(USV^{\top}))=\mathrm{span}(\dot{K})$.
Together with  (20) this yields the proof.
∎

Lemma 2 adopts a more general result for Tucker tensors in an unpublished manuscript and simplifies the analysis for the matrix case considered here.

###### Theorem 5 .

###### Lemma 2 .

###### Proof.

## Appendix E Efficient basis and coefficient communication

Note that we have by orthogonality of the bases ${\widetilde{U}}=[U,\bar{U}]$ with $\bar{U}\in\mathbb{R}^{n\times r}$ and $\bar{U}^{\top}U=0$ and ${\widetilde{V}}=[V,\bar{V}]$ with $\bar{V}\in\mathbb{R}^{n\times r}$ and $\bar{V}^{\top}V=0$.

###### Proof.

(Lemma 1)
The basis augmented basis $[U,G_{U}]$ before orthonormalization already contains the orthonormal vectors given by the columns of $U$. A QR decomposition therefor only rearranges the columns of $G_{U}$ such that ${\widetilde{U}}=[U,\bar{U}]$ with $\bar{U}\in\mathbb{R}^{n\times r}$ and $\bar{U}^{\top}U=0$. The analogous result holds for ${\widetilde{V}}=[V,\bar{V}]$. The projection onto the augmented basis therefore reads

$$ $\displaystyle{\widetilde{U}}^{\top}U=\begin{bmatrix}{U}^{\top}U\\ \overline{U}^{\top}U\end{bmatrix}=\begin{bmatrix}I\\ 0\end{bmatrix}\quad\text{and}\quad{\widetilde{V}}^{\top}V=\begin{bmatrix}{V}^{ \top}V\\ \overline{V}^{\top}V\end{bmatrix}=\begin{bmatrix}I\\ 0\end{bmatrix}.$ (22) $$

Consequently, the augmented coefficient matrix takes the form

$$ $\displaystyle{\widetilde{S}}={\widetilde{U}}^{\top}USV^{\top}{\widetilde{V}}= \begin{bmatrix}S&0\\ 0&0\end{bmatrix}.$ (23) $$

∎

###### Proof.

## Appendix F Analysis for FeDLRT with full variance correction

In this section we establish bounds on the coefficient drift of the FeDLRT method with full variance correction. We use the established coefficient drift bound to derive a loss-descend guarantee. The strategy of our analysis follows the one of FedLin [].
We first state an auxiliary lemma.

###### Lemma 3 .

Let $U\in\mathbb{R}^{n\times r}$ and $V\in\mathbb{R}^{n\times r}$ be orthonormal matrices.
Let $F$ be an $L$-continuous function.
Then, for $S_{1},S_{2}\in\mathbb{R}^{r\times r}$,

$$ $\displaystyle\left\lVert P_{U}\left(F(US_{1}V^{\top})-F(US_{2}V^{\top})\right) P_{V}\right\rVert\leq L\left\lVert S_{1}-S_{2}\right\rVert$ (24) $$

and

$$ $\displaystyle\left\lVert U\left(F(US_{1}V^{\top})-F(US_{2}V^{\top})\right)V^{ \top}\right\rVert\leq L\left\lVert S_{1}-S_{2}\right\rVert,$ (25) $$

where $P_{U}$ and $P_{V}$ are orthogonal projections defined in Appendix C.

###### Proof.

For the first statement, consider

$$ $\displaystyle\left\lVert P_{U}\left(F(US_{1}V^{\top})-F(US_{2}V^{\top})\right) P_{V}\right\rVert$ $\displaystyle=$ $\displaystyle\left\lVert UU^{\top}\left(F(US_{1}V^{\top})-F(US_{2}V^{\top}) \right)VV^{\top}\right\rVert$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle\left\lVert U\right\rVert\left\lVert U^{\top}\right\rVert\left \lVert F(US_{1}V^{\top})-F(US_{2}V^{\top})\right\rVert\left\lVert V\right \rVert\left\lVert V^{\top}\right\rVert$ $\displaystyle\overset{\text{(II)}}{=}$ $\displaystyle\left\lVert F(US_{1}V^{\top})-F(US_{2}V^{\top})\right\rVert$ $\displaystyle\overset{\text{(III)}}{\leq}$ $\displaystyle L\left\lVert US_{1}V^{\top}-US_{2}V^{\top}\right\rVert=L\left \lVert U(S_{1}-S_{2})V^{\top}\right\rVert$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle L\left\lVert U\right\rVert\left\lVert S_{1}-S_{2}\right\rVert \left\lVert V^{\top}\right\rVert$ $\displaystyle\overset{\text{(II)}}{=}$ $\displaystyle L\left\lVert S_{1}-S_{2}\right\rVert,$ $$

where we have used in (I) the operator norm inequality of the Frobenius norm, in (II) orthonormality of $U$, $V$, and in (III) $L$-continuity of $F$. The second statement is proven analogously.
∎

###### Lemma 3 .

###### Proof.

### F.1 Coefficient drift bound for FeDLRT with full variance correction

We consider the FeDLRT method with variance correction, see Algorithm 1. Key difference to the FeDLRT method without variance correction is the modified coefficient update, incorporating global gradient information of the augmented coefficient matrix ${\widetilde{S}}$ and local, stale gradient information of the augmented coefficient matrix ${\widetilde{S}}_{c}$.
The variance corrected local coefficient update (8) can be expressed in terms of the projected Riemannian gradient as

$$ $\displaystyle\widetilde{S}_{c}^{s+1}=\widetilde{S}_{c}^{s}+\lambda{\widetilde{ U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}})+F({ \widetilde{W}_{r}})\right){\widetilde{V}},$ (26) $$

where ${\widetilde{U}}^{\top}F_{c}(\widetilde{W}_{r,c}^{s}){\widetilde{V}}=\nabla_{
\widetilde{S}_{c}}\mathcal{L}_{c}({\widetilde{U}}\widetilde{S}_{c}^{s}{
\widetilde{V}})$, ${\widetilde{U}}^{\top}F_{c}(\widetilde{W}_{r,c}){\widetilde{V}}=\nabla_{
\widetilde{S}_{c}}\mathcal{L}_{c}({\widetilde{U}}\widetilde{S}_{c}^{s=0}{
\widetilde{V}})$ and ${\widetilde{U}}^{\top}F_{c}(\widetilde{W}_{r,c}^{s}){\widetilde{V}}=\nabla_{
\widetilde{S}_{c}}\mathcal{L}({\widetilde{U}}\widetilde{S}_{c}^{s}{\widetilde{
V}})$. Recall that ${\widetilde{S}}=\widetilde{S}_{c}$ for $s=0$.

We provide proof for Theorem 1 to bound the drift term $\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert$. We restate this theorem to the Riemannian notation and restate it below.

###### Theorem 6 .

(Restatement of Theorem 1)
Given augmented basis and coefficient matrices ${\widetilde{U}}$, ${\widetilde{V}}$, and ${\widetilde{S}}$, and ${\widetilde{W}_{r}}={\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top}$.
If the local learning rate $0<\lambda\leq\frac{1}{Ls_{*}}$ with $s_{*}\geq 1$ the number of local steps, for all clients $c$,

$$ $\displaystyle\textstyle\|{\widetilde{S}_{c}^{s}-\widetilde{S}_{c}}\|\leq\exp(1 )s_{*}\lambda\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert,\quad\textup{for}\quad s=1,\dots,s^{*}-1,$ (27) $$

where $\widetilde{S}_{c}^{s}$ is the variance corrected coefficient as given in (8).

###### Proof.

From the adjusted coefficient update in (26), we get

$$ $\displaystyle\left\lVert\widetilde{S}_{c}^{s+1}-\widetilde{S}_{c}\right\rVert$ $\displaystyle=\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}+\lambda{ \widetilde{U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W} _{r}})+F({\widetilde{W}_{r}})\right){\widetilde{V}}\right\rVert$ $\displaystyle\leq\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right \rVert+\lambda\left\lVert{\widetilde{U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c} ^{s})-F_{c}({\widetilde{W}_{r}})\right){\widetilde{V}}\right\rVert+\lambda \left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle\overset{\text{(I)}}{\leq}\left\lVert\widetilde{S}_{c}^{s}- \widetilde{S}_{c}\right\rVert+\lambda L\left\lVert\widetilde{S}_{c}^{s}-{ \widetilde{S}}\right\rVert+\lambda\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle\leq(1+\lambda L)\left\lVert\widetilde{S}_{c}^{s}-{\widetilde{S}} \right\rVert+\lambda\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert$ $\displaystyle\leq\left(1+\frac{1}{s_{*}}\right)\left\lVert\widetilde{S}_{c}^{s }-{\widetilde{S}}\right\rVert+\lambda\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert.$ $$

We use in (I) Lemma 3
Recursively plugging in the above inequality yields for $a=(1+\frac{1}{s_{*}})$

$$ $\displaystyle\left\lVert\widetilde{S}_{c}^{s+1}-\widetilde{S}_{c}\right\rVert$ $\displaystyle\leq a^{s+1}\left\lVert\widetilde{S}_{c}^{s=0}-{\widetilde{S}} \right\rVert+\left(\sum_{j=0}^{s}a^{j}\right)\lambda\left\lVert{\widetilde{U}} ^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle=\left(\sum_{j=0}^{s}a^{j}\right)\lambda\left\lVert{\widetilde{U} }^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle=\frac{a^{s+1}-1}{a-1}\lambda\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle\leq\left(1+\frac{1}{s_{*}}\right)^{s+1}s_{*}\lambda\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle\leq\left(1+\frac{1}{s_{*}}\right)^{s_{*}}s_{*}\lambda\left\lVert {\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle\leq\exp(1)s_{*}\lambda\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert.$ $$

∎

###### Theorem 6 .

###### Proof.

### F.2 Global loss descent for FeDLRT with full variance correction

We first state a few auxiliary lemmas, which provide common inequalities that will be used in the following analysis.

###### Lemma 4 .

([, Lemma 5.2])
For any two matrices $Y_{1},Y_{2}\in\mathbb{R}^{n\times n}$ and an $L$-smooth $\mathcal{L}$ with constant $L$ it holds

$$ $\displaystyle\mathcal{L}(Y_{1})-\mathcal{L}(Y_{2})\leq-\left<Y_{1}-Y_{2},F(Y_{ 2})\right>+\frac{L}{2}\left\lVert Y_{1}-Y_{2}\right\rVert^{2},$ (28) $$

where $F(Y)=-\nabla_{Y}\mathcal{L}(Y)$.

###### Lemma 5 .

([, Lemma 5])
For two vectors $x_{1},x_{2}\in\mathbb{R}^{d}$ it holds for $\gamma>0$

$$ $\displaystyle\left\lVert x_{1}+x_{2}\right\rVert^{2}\leq(1+\gamma)\left\lVert x _{1}\right\rVert^{2}+\left(1+\frac{1}{\gamma}\right)\left\lVert x_{2}\right \rVert^{2}.$ (29) $$

###### Lemma 6 .

([, Lemma 6])
For $C$ vectors $x_{1},\dots,x_{C}\in\mathbb{R}^{d}$ the application of Jensen’s inequality yields

$$ $\displaystyle\left\lVert\sum_{c=1}^{C}x_{c}\right\rVert^{2}\leq C\sum_{c=1}^{C }\left\lVert x_{c}\right\rVert^{2}.$ (30) $$

First, we consider the loss function value at the augmentation step.

###### Lemma 7 .

We have $\mathcal{L}({\widetilde{W}_{r}})=\mathcal{L}(W_{r}^{t})$ for the loss before and after basis augmentation.

###### Proof.

Due to Lemma 1, ${\widetilde{S}}=\begin{bmatrix}S^{t}&0\\
0&0\end{bmatrix}$, thus ${\widetilde{W}_{r}}={\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top}=USV^{
\top}=W^{t}$.
∎

We next bound the loss descent between the augmentation step and the truncation step - having performed the aggregation of the client updates.

###### Theorem 7 .

Let ${\widetilde{W}_{r}}={\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top}$ be the augmented factorization at global iteration $t$ and let
${\widetilde{W}_{r}}^{*}={\widetilde{U}}{\widetilde{S}}^{*}{\widetilde{V}}^{\top}$ be the aggregated solution after client iterations, i.e., ${\widetilde{S}}^{*}=\frac{1}{C}\sum_{c=1}^{C}{\widetilde{S}}_{c}^{s_{*}}$.
Then the variance corrected coefficient update (26) yields the guarantee

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})$ $\displaystyle\leq-(s_{*}\lambda)(1-(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^ {\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ (31) $\displaystyle+\left(\frac{L\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left \lVert\widetilde{S}_{c}^{s}-{\widetilde{S}}\right\rVert\right)\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle+\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1 }\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert^{2}.$ $$

###### Proof.

From (8), $P_{\widetilde{U}}={\widetilde{U}}{\widetilde{U}}^{\top}$, $P_{\widetilde{V}}={\widetilde{V}}{\widetilde{V}}^{\top}$, and the fact that $\widetilde{W}_{r,c}^{s=0}={\widetilde{W}_{r}}$ for all $c=1,\dots,C$,

$$ $\displaystyle\widetilde{W}_{r,c}^{s_{*}}$ $\displaystyle={\widetilde{U}}{\widetilde{S}}_{c}^{s_{*}}{\widetilde{V}}^{\top} ={\widetilde{U}}{\widetilde{S}}_{c}^{s=0}{\widetilde{V}}^{\top}+{\widetilde{U} }{\widetilde{U}}^{\top}\sum_{s=0}^{s_{*}-1}\lambda\left(F_{c}(\widetilde{W}_{r ,c}^{s})-F_{c}({\widetilde{W}_{r}})+F({\widetilde{W}_{r}})\right){\widetilde{V }}{\widetilde{V}}^{\top}$ $\displaystyle={\widetilde{W}_{r}}-\lambda\sum_{s=0}^{s_{*}-1}P_{\widetilde{U}} F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}}-\lambda P_{\widetilde{U}}\left (F({\widetilde{W}_{r}})-F_{c}({\widetilde{W}_{r}})\right)P_{\widetilde{V}}.$ $$

Averaging across clients leads to

$$ $\displaystyle{\widetilde{W}_{r}}^{*}=$ $\displaystyle\frac{1}{C}\sum_{c=1}^{C}\widetilde{W}_{r,c}^{s_{*}}={\widetilde{ W}_{r}}-\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{\widetilde{U}}F_ {c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}}-\frac{\lambda}{C}\sum_{c=1}^{C}P _{\widetilde{U}}\left(F({\widetilde{W}_{r}})-F_{c}({\widetilde{W}_{r}})\right) P_{\widetilde{V}}$ $\displaystyle=$ $\displaystyle{\widetilde{W}_{r}}-\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_ {*}-1}P_{\widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}},$ (32) $$

where we have used the definition of the global and local gradient at ${\widetilde{W}_{r}}$, i.e., $\frac{1}{C}\sum_{c=1}^{C}F_{c}({\widetilde{W}_{r}})=F({\widetilde{W}_{r}})$. Based on $L$-continuity of $F$ and $F_{c}$, (32), and Lemma 4, we obtain further

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})$ $\displaystyle\leq\left<{\widetilde{W}_{r}}^{*}-{\widetilde{W}_{r}},F({ \widetilde{W}_{r}})\right>+\frac{L}{2}\left\lVert{\widetilde{W}_{r}}^{*}-{ \widetilde{W}_{r}}\right\rVert^{2}$ (33) $\displaystyle=-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}},F({\widetilde{W} _{r}})\right>+\frac{L}{2}\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^ {s_{*}-1}P_{\widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}} \right\rVert^{2}.$ $$

Next, we bound each of the two right-hand-side terms separately. We first express the first term as

$$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}},F({\widetilde{W} _{r}})\right>$ $\displaystyle=$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}}) \right)P_{\widetilde{V}}+P_{\widetilde{U}}\left(\frac{\lambda}{C}\sum_{c=1}^{C }\sum_{s=0}^{s_{*}-1}F_{c}({\widetilde{W}_{r}})\right)P_{\widetilde{V}},F({ \widetilde{W}_{r}})\right>$ $\displaystyle=$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}}) \right)P_{\widetilde{V}}+P_{\widetilde{U}}\frac{s_{*}\lambda}{C}\sum_{c=1}^{C} F_{c}({\widetilde{W}_{r}})P_{\widetilde{V}},F({\widetilde{W}_{r}})\right>$ $\displaystyle=$ $\displaystyle-\left<P_{\widetilde{U}}\left(\frac{\lambda}{C}\sum_{c=1}^{C}\sum _{s=0}^{s_{*}-1}F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}}) \right)P_{\widetilde{V}}+P_{\widetilde{U}}s_{*}\lambda F({\widetilde{W}_{r}})P _{\widetilde{V}},F({\widetilde{W}_{r}})\right>$ $\displaystyle=$ $\displaystyle-\left<{\widetilde{U}}^{\top}\left(\frac{\lambda}{C}\sum_{c=1}^{C }\sum_{s=0}^{s_{*}-1}F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}}) \right){\widetilde{V}},{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde {V}}^{\top}\right>-s_{*}\lambda\left<{\widetilde{U}}^{\top}F({\widetilde{W}_{r }}){\widetilde{V}},{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right>$ $\displaystyle=$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}{ \widetilde{U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W} _{r}})\right){\widetilde{V}},{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right>-s_{*}\lambda\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

where the definitions of $P_{\widetilde{U}}$ and $P_{\widetilde{V}}$ are used.
Following this, the first term then can be bounded by

$$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}},F({\widetilde{W} _{r}})\right>$ $\displaystyle{\leq}$ $\displaystyle\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left\lVert{ \widetilde{U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W} _{r}})\right){\widetilde{V}}\right\rVert\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert-s_{*}\lambda\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle{\leq}$ $\displaystyle\frac{L\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left\lVert \widetilde{S}_{c}^{s}-{\widetilde{S}}\right\rVert\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert-s_{*}\lambda\left\lVert {\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

where Lemma 3 is invoked in the last inequality.
Following a similar approach, we express the second term as

$$ $\displaystyle\frac{L}{2}\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{ s_{*}-1}P_{\widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}}\right \rVert^{2}=\frac{L}{2}\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_ {*}-1}P_{\widetilde{U}}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{ W}_{r}})\right)P_{\widetilde{V}}+s_{*}\lambda P_{\widetilde{U}}F({\widetilde{W }_{r}})P_{\widetilde{V}}\right\rVert^{2},$ $$

which can be bounded by

$$ $\displaystyle\frac{L}{2}\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{ s_{*}-1}P_{\widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}}\right \rVert^{2}$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle L\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P _{\widetilde{U}}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({\widetilde{W}_{r}} )\right)P_{\widetilde{V}}\right\rVert^{2}+(s_{*}\lambda)^{2}L\left\lVert P_{ \widetilde{U}}F({\widetilde{W}_{r}})P_{\widetilde{V}}\right\rVert^{2}$ $\displaystyle\overset{\text{(II)}}{\leq}$ $\displaystyle\frac{L}{C}\sum_{c=1}^{C}\lambda^{2}s_{*}\sum_{s=0}^{s_{*}-1} \left\lVert P_{\widetilde{U}}\left(F_{c}(\widetilde{W}_{r,c}^{s})-F_{c}({ \widetilde{W}_{r}})\right)P_{\widetilde{V}}\right\rVert^{2}+(s_{*}\lambda)^{2} L\left\lVert P_{\widetilde{U}}F({\widetilde{W}_{r}})P_{\widetilde{V}}\right \rVert^{2}$ $\displaystyle\overset{\text{(III)}}{\leq}$ $\displaystyle\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1} \left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert^{2}+(s_{*} \lambda)^{2}L\left\lVert P_{\widetilde{U}}F({\widetilde{W}_{r}})P_{\widetilde{ V}}\right\rVert^{2}$ $\displaystyle\overset{\text{(IV)}}{\leq}$ $\displaystyle\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1} \left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert^{2}+(s_{*} \lambda)^{2}L\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert^{2},$ $$

where Lemma 5 with $\gamma=1$ is used in in (I), Jensen’s inequality is used in (II), Lemma 3 is used in in (III), and (IV) follows from the Operator norm inequality of the Frobenius norm in combination with orthonormality of $U$ and $V^{\top}$.

Plugging these two bounds into (33) gives

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})\leq$ $\displaystyle-\left<\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}P_{ \widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}},F({\widetilde{W} _{r}})\right>+\frac{L}{2}\left\lVert\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^ {s_{*}-1}P_{\widetilde{U}}F_{c}(\widetilde{W}_{r,c}^{s})P_{\widetilde{V}} \right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle\frac{L\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left\lVert \widetilde{S}_{c}^{s}-{\widetilde{S}}\right\rVert\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert-s_{*}\lambda\left\lVert {\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle+\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1 }\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert^{2}+(s_{*} \lambda)^{2}L\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert^{2}$ $\displaystyle=$ $\displaystyle-(s_{*}\lambda)(1-(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle+\left(\frac{L\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left \lVert\widetilde{S}_{c}^{s}-{\widetilde{S}}\right\rVert\right)\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle+\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1 }\left\lVert\widetilde{S}_{c}^{s}-\widetilde{S}_{c}\right\rVert^{2},$ $$

which concludes the proof.
∎

With this result, we next bound the loss descent between the augmentation and coefficient aggregation step in the following theorem.

###### Theorem 8 .

Under the same assumptions as in Theorem 7.
Let the local learning rate be $0<\lambda\leq\frac{1}{12Ls_{*}}$ with number of local iterations $s_{*}\geq 1$. Then,

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})$ $\displaystyle\leq-s_{*}\lambda(1-12s_{*}\lambda L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}.$ (34) $$

###### Proof.

Applying the drift bound given in Theorem 1 to the loss descent bound given by Theorem 7 in (31) leads to

$$ $\displaystyle-(s_{*}\lambda)(1-(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle+\left(\frac{L\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left( \exp(1)s_{*}\lambda\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert\right)\right)\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert$ $\displaystyle+\frac{L^{3}\lambda^{2}s_{*}}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1 }\left(\exp(1)s_{*}\lambda\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r }}){\widetilde{V}}\right\rVert\right)^{2}$ $\displaystyle=$ $\displaystyle-(s_{*}\lambda)(1-(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}+L\lambda^{2}s_{*}^{ 2}\exp(1)\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V} }\right\rVert^{2}$ $\displaystyle+{L^{3}\lambda^{4}s_{*}^{4}\exp(2)}\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle=$ $\displaystyle-(s_{*}\lambda)(1-(s_{*}\lambda)L-(s_{*}\lambda)L\exp(1)-(s_{*} \lambda)^{3}L^{2}\exp(2))\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r} }){\widetilde{V}}\right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle-(s_{*}\lambda)(1-(s_{*}\lambda)L(1+\exp(1)+\exp(2)))\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

where we have used that $(s_{*}\lambda)L\leq 1$ and that $1+\exp(1)+\exp(2)\approx 11.107\leq 12$.
∎

We are now prepared to prove Theorem 2, which we restate in terms of Riemannian gradients as below.

###### Theorem 9 .

(Restatement of Theorem 2)
Let $U^{t}S^{t}V^{t,\top}$ and $U^{t+1}S^{t+1}V^{t+1,\top}$ be the factorization before and after iteration $t$ of
Algorithm 1 with variance correction and singular value truncation threshold $\vartheta$. Let $\mathcal{L}_{c}$ and $\mathcal{L}$ be $L$-smooth with constant $L$, and let the local learning rate be $0\leq\lambda\leq\frac{1}{12Ls_{*}}$. Then the global loss descent is bounded by

$$ $\displaystyle\mathcal{L}(U^{t+1}S^{t+1}V^{t+1,\top})-\mathcal{L}(U^{t}S^{t}V^{ t,\top})\leq-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}+L\vartheta.$ (35) $$

###### Proof.

Consider $\mathcal{L}(W_{r}^{t+1})$ and $\mathcal{L}({\widetilde{W}_{r}}^{*})$, i.e., the loss values before and after the truncation step.
By the mean value theorem, we obtain for some $h\in[0,1]$

$$ $\displaystyle\begin{aligned} \mathcal{L}(W_{r}^{t+1})&=\mathcal{L}({\widetilde {W}_{r}}^{*})+\left<-F(hW_{r}^{t+1}+(1-h){\widetilde{W}_{r}}^{*}),W_{r}^{t+1}- {\widetilde{W}_{r}}^{*}\right>\\ &{\leq}\mathcal{L}({\widetilde{W}_{r}}^{*})+\left\lVert F(hW_{r}^{t+1}+(1-h){ \widetilde{W}_{r}}^{*})\right\rVert\left\lVert W_{r}^{t+1}-{\widetilde{W}_{r}} ^{*}\right\rVert\\ &{\leq}\mathcal{L}({\widetilde{W}_{r}}^{*})+L\vartheta\end{aligned}$ (36) $$

where $L$-smoothness and the fact that $\vartheta\geq\left\lVert W_{r}^{t+1}-{\widetilde{W}_{r}}^{*}\right\rVert$ are used in (II), where the latter follows from the singular value truncation threshold.
Combining the above arguments with Lemma 7 and Theorem 8 yields

$$ $\displaystyle\mathcal{L}(W_{r}^{t+1})-\mathcal{L}(W_{r}^{t})$ $\displaystyle=(\mathcal{L}(W_{r}^{t+1})-\mathcal{L}({\widetilde{W}_{r}}^{*}))+ (\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{r}}))+( \mathcal{L}({\widetilde{W}_{r}})-\mathcal{L}(W_{r}^{t}))$ $\displaystyle\leq L\vartheta-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

which concludes the proof.
∎

###### Lemma 4 .

###### Lemma 5 .

###### Lemma 6 .

###### Lemma 7 .

###### Proof.

###### Theorem 7 .

###### Proof.

###### Theorem 8 .

###### Proof.

###### Theorem 9 .

###### Proof.

### F.3 Global convergence of FeDLRT with full variance correction

###### Theorem 10 .

(Restatement of Theorem 3)
Assume that $\mathcal{L}$ is $L$-smooth with constant $L$ for all $c=1,\dots,C$. Let ${\widetilde{U}}^{t}{\widetilde{S}}^{t}{\widetilde{V}}^{t,\top}$ be the augmented representation at iteration $t$. Then Algorithm  1 guarantees for the learning rate $\lambda\leq\frac{1}{12Ls_{*}}$ and final iteration $T$

$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}(U^ {t}S^{t}V^{t,\top})\right\rVert^{2}\leq\frac{48L}{T}\left(\mathcal{L}({{W}_{r} }^{t=1})-\mathcal{L}({{W}_{r}}^{t={T+1}})\right)+{48L^{2}}{\vartheta}.$ (37) $$

###### Proof.

Consider Theorem 2,

$$ $\displaystyle\mathcal{L}(W_{r}^{t+1})-\mathcal{L}(W_{r}^{t})$ $\displaystyle\leq L\vartheta-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert \nabla_{\widetilde{S}}\mathcal{L}(U^{t}S^{t}V^{t,\top})\right\rVert^{2},$ (38) $$

and assume that $\lambda s_{*}=\frac{1}{24L}$, i.e. $\lambda=\frac{1}{24Ls_{*}}\leq\frac{1}{Ls_{*}}$, which obeys the learning rate requirement of Theorem 2. Plugging this learning rate into (38) gives

$$ $\displaystyle\left\lVert\nabla_{\widetilde{S}}\mathcal{L}(U^{t}S^{t}V^{t,\top} )\right\rVert^{2}\leq 48L\left(\mathcal{L}({{W}_{r}}^{t})-\mathcal{L}({{W}_{r} }^{t+1})+L\vartheta\right).$ $$

Averaging from $t=1$ to $t=T$ yields

$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}(U^ {t}S^{t}V^{t,\top})\right\rVert^{2}$ $\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\left\lVert\nabla_{\widetilde{S}} \mathcal{L}(U^{t}S^{t}V^{t,\top})\right\rVert^{2}$ $\displaystyle\leq\frac{48L}{T}\left(\mathcal{L}({{W}_{r}}^{t=1})-\mathcal{L}({ {W}_{r}}^{t={T+1}})\right)+{48L^{2}}{\vartheta},$ $$

which concludes the proof.
∎

###### Theorem 10 .

###### Proof.

## Appendix G Analysis for FeDLRT with simplified variance correction

We consider the FeDLRT method with simplified variance correction, see Algorithm 5.
Key difference to the standard FeDLRT with full variance correction, see Algorithm 1 is the modified coefficient update, incorporating global gradient information of the non-augmented coefficient matrix $S$ for the variance correction term, that is

$$ $\displaystyle\textstyle\check{V}_{c}=\check{G}_{\widetilde{S}}-\check{G}_{{ \widetilde{S}},c}=\begin{bmatrix}\nabla_{S}\mathcal{L}(U^{t}S^{t}V^{t,\top})- \nabla_{S}\mathcal{L}_{c}(U^{t}S^{t}V^{t,\top})&0\\ 0&0\end{bmatrix}.$ (39) $$

Using the Riemmanian gradient, we can equivalently write

$$ $\displaystyle\check{V}_{c}=\left[U^{\top}|\,0\,\right](F({\widetilde{W}_{r}})- F_{c}({\widetilde{W}_{r}}))\begin{bmatrix}V\\ 0\end{bmatrix}={\widetilde{U}}^{\top}\begin{bmatrix}I&0\\ 0&0\end{bmatrix}(F_{c}({\widetilde{W}_{r}})-F({\widetilde{W}_{r}}))\begin{ bmatrix}I&0\\ 0&0\end{bmatrix}{\widetilde{V}}.$ $$

Remember the simplified variance corrected local coefficient update, given by

$$ $\displaystyle\begin{aligned} \widetilde{S}_{c}^{s+1}&=\widetilde{S}_{c}^{s}+ \lambda{\widetilde{U}}^{\top}\left(F_{c}(\widetilde{W}_{r,c}^{s})+\begin{ bmatrix}I&0\\ 0&0\end{bmatrix}(F_{C}({\widetilde{W}_{r}})-F({\widetilde{W}_{r}}))\begin{ bmatrix}I&0\\ 0&0\end{bmatrix}\right){\widetilde{V}}\\ &=\widetilde{S}_{c}^{s}+\lambda{\widetilde{U}}^{\top}\left(F_{c}(\widetilde{W} _{r,c}^{s})\right){\widetilde{V}}+\check{V}_{c}.\end{aligned}$ (40) $$

### G.1 Global loss descent for FeDLRT with simplified variance correction

In the following we provide proof for a global loss descent for Algorithm 5, i.e. using the
local coefficient update with variance correction (40).

###### Theorem 11 .

(Restatement of Theorem 4)
Under 1, if the local learning rate $0<\lambda\leq\frac{1}{12Ls_{*}}$, then Algorithm 5 leads to the global loss descent

$$ $\displaystyle\begin{aligned} &\mathcal{L}({{W}_{r}}^{t+1})-\mathcal{L}({{W}_{r }}^{t})\leq-s_{*}\lambda(1-\delta^{2}-12s_{*}\lambda L+\delta^{2}{s_{*}\lambda })\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right \rVert^{2}+L\vartheta,\end{aligned}$ (41) $$

with ${{W}_{r}}^{t}=U^{t}S^{t}V^{t,\top}$ and ${{W}_{r}}^{t+1}=U^{t+1}S^{t+1}V^{t+1,\top}$.

###### Proof.

We split the adjusted coefficient update in (40) into the non-augmented $r\times r$ matrix $S$ and the tree off-diagonal blocks given by the augmentation ${\widehat{S}}$:

$$ $\displaystyle{\widehat{S}}={\widetilde{S}}-\begin{bmatrix}S&0\\ 0&0\end{bmatrix}.$ (42) $$

Analogously to the proof of Theorem 2, we consider

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})$ $\displaystyle\leq\left<{\widetilde{W}_{r}}^{*}-{\widetilde{W}_{r}},F({ \widetilde{W}_{r}})\right>+\frac{L}{2}\left\lVert{\widetilde{W}_{r}}^{*}-{ \widetilde{W}_{r}}\right\rVert^{2}$ $\displaystyle=\left<{\widetilde{U}}{\widetilde{S}}^{*}{\widetilde{V}}^{\top}-{ \widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top},F({\widetilde{W}_{r}}) \right>+\frac{L}{2}\left\lVert{\widetilde{U}}{\widetilde{S}}^{*}{\widetilde{V} }^{\top}-{\widetilde{U}}{\widetilde{S}}{\widetilde{V}}^{\top}\right\rVert^{2}$ $\displaystyle=\left<{\widetilde{S}}^{*}-{\widetilde{S}},{\widetilde{U}}^{\top} F({\widetilde{W}_{r}}){\widetilde{V}}\right>+\frac{L}{2}\left\lVert{\widetilde {S}}^{*}-{\widetilde{S}}\right\rVert^{2}$ $\displaystyle=\left<{\widetilde{S}}^{*}-{\widetilde{S}},-\nabla_{\widetilde{S} }\mathcal{L}({\widetilde{W}_{r}})\right>+\frac{L}{2}\left\lVert{\widetilde{S}} ^{*}-{\widetilde{S}}\right\rVert^{2},$ $$

where the transformation uses orthonormality of ${\widetilde{U}}$ and ${\widetilde{V}}$ and definition of the projected gradient.
We split the right hand side in terms corresponding to
augmented terms ${\widehat{S}}$ and non-augmented terms $S$ according to (42), i.e.,

$$ $\displaystyle\left<S^{*}-S,-\nabla_{S}\mathcal{L}({\widetilde{W}_{r}})\right>+ \frac{L}{2}\left\lVert S^{*}-S\right\rVert^{2},$ (43) $$

which is treated exactly as in the proof of Theorem 2, and the augmented terms

$$ $\displaystyle\left<{\widehat{S}}^{*}-{\widehat{S}},-\nabla_{\widehat{S}} \mathcal{L}({\widetilde{W}_{r}})\right>+\frac{L}{2}\left\lVert{\widehat{S}}^{* }-{\widehat{S}}\right\rVert^{2}.$ (44) $$

First we bound the term (43).
Remember that ${\widehat{S}}=0$ at the start of the local iterations due to orthonormality of ${\widetilde{U}},{\widetilde{V}}$.
The coefficient update (40) for $S$ reads

$$ $\displaystyle S_{c}^{s+1}=S_{c}^{s}+\lambda U^{\top}\left(F_{c}(\widetilde{W}_ {r,c}^{s})-F_{c}({\widetilde{W}_{r}})+F({\widetilde{W}_{r}})\right)V.$ (45) $$

Then we can readily apply Theorem 2 to obtain the bound

$$ $\displaystyle\left<S^{*}-S,-\nabla_{S}\mathcal{L}({\widetilde{W}_{r}})\right>+ \frac{L}{2}\left\lVert S^{*}-S\right\rVert^{2}\leq-(s_{*}\lambda)(1-12(s_{*} \lambda)L)\left\lVert U^{\top}F({\widetilde{W}_{r}})V\right\rVert^{2}.$ (46) $$

Next, we bound (44), starting with the first term:

$$ $\displaystyle\left<{\widehat{S}}^{*}-{\widehat{S}},-\nabla_{\widehat{S}} \mathcal{L}({\widetilde{W}_{r}})\right>$ $\displaystyle\overset{\text{(I)}}{=}\left<{\widehat{S}}^{*}-0,-\nabla_{ \widehat{S}}\mathcal{L}({\widetilde{W}_{r}})\right>$ $\displaystyle=\left<-\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\nabla _{\widehat{S}}\mathcal{L}_{c}(\widetilde{W}_{r,c}^{s}),-\nabla_{\widehat{S}} \mathcal{L}({\widetilde{W}_{r}})\right>$ $\displaystyle=\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left<\nabla_ {\widehat{S}}\mathcal{L}_{c}(\widetilde{W}_{r,c}^{s}),\nabla_{\widehat{S}} \mathcal{L}({\widetilde{W}_{r}})\right>$ $\displaystyle\leq\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^{s_{*}-1}\left \lVert\nabla_{\widehat{S}}\mathcal{L}_{c}(\widetilde{W}_{r,c}^{s})\right\rVert \left\lVert\nabla_{\widehat{S}}\mathcal{L}({\widetilde{W}_{r}})\right\rVert$ $\displaystyle\overset{\text{(II)}}{\leq}\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s =0}^{s_{*}-1}\delta^{2}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({ \widetilde{W}_{r}})\right\rVert\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({ \widetilde{W}_{r}})\right\rVert$ $\displaystyle=\delta^{2}s_{*}\lambda\left\lVert\nabla_{\widetilde{S}}\mathcal{ L}({\widetilde{W}_{r}})\right\rVert^{2}=\delta^{2}s_{*}\lambda\left\lVert{ \widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

where we use ${\widehat{S}}=0$ in (I), and 1 in (II).
Next, we bound the second term

$$ $\displaystyle\frac{L}{2}\left\lVert{\widehat{S}}^{*}-{\widehat{S}}\right\rVert ^{2}=$ $\displaystyle\frac{L}{2}\left\lVert-\frac{\lambda}{C}\sum_{c=1}^{C}\sum_{s=0}^ {s_{*}-1}\nabla_{\widehat{S}}\mathcal{L}(\widetilde{W}_{r,c}^{S})\right\rVert^ {2}$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle\frac{L}{2}\lambda^{2}\frac{1}{C}\sum_{c=1}^{C}\left\lVert\sum_{s =0}^{s_{*}-1}\nabla_{\widehat{S}}\mathcal{L}(\widetilde{W}_{r,c}^{S})\right \rVert^{2}$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle\frac{L}{2}{s_{*}}\lambda^{2}\frac{1}{C}\sum_{c=1}^{C}\sum_{s=0}^ {s_{*}-1}\left\lVert\nabla_{\widehat{S}}\mathcal{L}(\widetilde{W}_{r,c}^{S}) \right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle{s_{*}}\frac{L}{2}\delta^{2}\lambda^{2}\frac{1}{C}\sum_{c=1}^{C} \sum_{s=0}^{s_{*}-1}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({\widetilde{W }_{r}})\right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle\frac{L}{2}\delta^{2}{(s_{*}\lambda)^{2}}\left\lVert\nabla_{ \widetilde{S}}\mathcal{L}({\widetilde{W}_{r}})\right\rVert^{2}=\frac{L}{2} \delta^{2}{(s_{*}\lambda)^{2}}\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W }_{r}}){\widetilde{V}}\right\rVert^{2},$ $$

where we used Jensen’s inequality in (I) again 1.
We combine the bound on the non-augmented terms (46) and the two bounds above for the augmented terms to

$$ $\displaystyle\mathcal{L}({\widetilde{W}_{r}}^{*})-\mathcal{L}({\widetilde{W}_{ r}})\leq\left<{\widetilde{W}_{r}}^{*}-{\widetilde{W}_{r}},F({\widetilde{W}_{r} })\right>+\frac{L}{2}\left\lVert{\widetilde{W}_{r}}^{*}-{\widetilde{W}_{r}} \right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert U^{\top}F({ \widetilde{W}_{r}})V\right\rVert^{2}+\delta s_{*}\lambda\left\lVert{\widetilde {U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}+\delta{(s_{*} \lambda)^{2}}\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){ \widetilde{V}}\right\rVert^{2}$ $\displaystyle\overset{\text{(I)}}{\leq}$ $\displaystyle-(s_{*}\lambda)(1-12(s_{*}\lambda)L)\left\lVert{\widetilde{U}}^{ \top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}+\delta s_{*}\lambda \left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right \rVert^{2}+\delta{(s_{*}\lambda)^{2}}\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle=$ $\displaystyle-(s_{*}\lambda)(1-\delta^{2}-12(s_{*}\lambda)L+\delta^{2}{(s_{*} \lambda)})\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V }}\right\rVert^{2},$ $$

where we use in (I) $\left\lVert U^{\top}F({\widetilde{W}_{r}})V\right\rVert\leq\left\lVert{
\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert$.
Using Equation 36, we can conclude the proof:

$$ $\displaystyle\mathcal{L}(U^{t+1}S^{t+1}V^{t+1,\top})-\mathcal{L}(U^{t}S^{t}V^{ t,\top})$ $\displaystyle\leq$ $\displaystyle-(s_{*}\lambda)(1-\delta^{2}-12(s_{*}\lambda)L+\delta^{2}{(s_{*} \lambda)})\left\lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V }}\right\rVert^{2}+L\vartheta.$ $$

∎

###### Theorem 11 .

###### Proof.

### G.2 Global convergence of FeDLRT with simplified variance correction

###### Corollary 2 .

(Restatement of Corollary 1)
Under 1, Algorithm 5 guarantees for the learning rate $\lambda\leq\frac{1}{s_{*}(12L+\delta^{2})}$

$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({{ W}_{r}}^{t})\right\rVert^{2}\leq\frac{96L}{T}\left(\mathcal{L}({{W}_{r}}^{1})- \mathcal{L}({{W}_{r}}^{{T+1}})\right)+{96L^{2}}{\vartheta},$ (47) $$

with ${{W}_{r}}^{t}=U^{t}S^{t}V^{t,\top}$, ${{W}_{r}}^{1}=U^{1}S^{1}V^{1,\top}$. and ${{W}_{r}}^{T+1}=U^{T+1}S^{T+1}V^{T+1,\top}$.

###### Proof.

Consider Theorem 4,

$$ $\displaystyle\mathcal{L}({{W}_{r}}^{t+1})-\mathcal{L}({{W}_{r}}^{t})\leq-(s_{* }\lambda)(1-\delta^{2}-12(s_{*}\lambda)L+\delta^{2}{(s_{*}\lambda)})\left \lVert{\widetilde{U}}^{\top}F({\widetilde{W}_{r}}){\widetilde{V}}\right\rVert^ {2}+L\vartheta$ $$

and assume that $\lambda s_{*}=\frac{1}{(12L+\delta^{2})}$, i.e. $\lambda=\frac{1}{s_{*}(12L+\delta^{2})}\leq\frac{1}{Ls_{*}}$, which obeys the learning rate requirement of Theorem 2. Plugging this learning rate into (38) gives

$$ $\displaystyle\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({{W}_{r}}^{t})\right \rVert^{2}\leq 96L\left(\mathcal{L}({{W}_{r}}^{t})-\mathcal{L}({{W}_{r}}^{t+1} )+L\vartheta\right),$ $$

where we use $(\frac{1}{4}-\delta^{2})\leq\frac{1}{4}$ and $\frac{1}{(12L+\delta^{2})}\leq\frac{1}{12L}$
Averaging from $t=1$ to $t=T$ yields

$$ $\displaystyle\min_{t=1,\dots,T}\left\lVert\nabla_{\widetilde{S}}\mathcal{L}({{ W}_{r}}^{t})\right\rVert^{2}\leq$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left\lVert{\widetilde{U}}^{\top}F({ \widetilde{W}_{r}}){\widetilde{V}}\right\rVert^{2}$ $\displaystyle\leq$ $\displaystyle\frac{96L}{T}\left(\mathcal{L}({{W}_{r}}^{t=1})-\mathcal{L}({{W}_ {r}}^{t={T+1}})\right)+{96L^{2}}{\vartheta},$ $$

which concludes the proof.
∎

###### Corollary 2 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: - Could you better describe the relationship with respect to the above related works both regarding the methodology and the convergence guarantees?
- What are the assumptions regarding statistichal heterogeneity for the convergence of FeDLRT? I did not find an equivalent of the common "bounded gradient dissimilarity" assumption for the low-rank training of the proposed method, and I wonder what are the guarantees in heterogeneous FL
- With respect to the previous question, can you propose some experiments similar to the ones presented for real-world dataset (e.g. CIFAR-10 with ResNet18) in heterogeneous cases (e.g. Dirichlet split as standard)? I would like to see an assessment of the performance of the proposed methods in non-convex case on real-world dataset, as opposed to the (valuable) results already provided for the linear squares regression in figure 1.

**Other suggestions:**
- **Presentation of theoretical results:** Theorems 1,2 and 5 should be lemmas in my opinion, since they are intermediate results necessary for the convergence rates. Please evaluate providing also a more in-depht discussion of these results
- **Organization of figures:** figure 6 in hardly readable in a printed version of the manuscript. Please evaluate enlarging the font size as well as the size of the overall figure. Alternatively, results in tabular form could be an option. I also suggest not to put wrap figure 4 in the text, as it makes the text less readable.
- **Empirical validation of assumption 1:** I think that and empirical validation of assumption 1 could benefit the clarity and the robustness od the paper. While the assumption seems reasonable in homogeneous cases and the corresponding methods seems pretty equivalent in performance in the provided experiments, I expect statistical heterogeneity to play a role in this matter. Could you plot the quantity in the LHS of eq. 14 in one of the real-world experiments of your setup (e.g. CIFAR-10 with ResNet18), in iid and non-iid conditions?
soundness: 3
strengths: - The approach has strong theoretical guarantees, and the empirical results seems matching the theory;
- The method jointly reduces communication cost and client compute, since clients only optimize smaller matrices w.r.t. full weights
summary: The paper introduces the FeDLRT algorithm to jointly reduce client compute and communication cost in Federated Learning (FL). The method consist in estimating a global low-rank basis of network weights and constraing local client optimization to that manifold, with an optional variance-reduction term applied to local updates.
The work presents a convergence proof of the proposed algorithms and variants for non-convex objectives in full participation, demonstrating that FeDLRT achieves state-of-art linear convergence rate.
Experiments include theoretical settings (linear least squares regression) and computer vision setup (CIFAR-10 with ResNet-18/AlexNet/VGG and CIFAR-100 with ViT), and are convincing in showing the effectiveness of the proposed approach.
weaknesses: - **Poor introduction of the premises for the algorithm:** in my opinion the second part of section 2 is not clear enough in explaining the concepts the proposed algorithm is based on. In particular, it is not evident which technical innovations this work brings with respect to previous works. Authors are encouraged to dedicate more space to discuss how this work build on previous concepts and how it advances the state of the art.
- **Poor comparison with other approaches:** the proposed method is compared essentially only with FedLin and FedAvg, while many methods exist in the categories the authors outline in the introduction ((i) methods that only communicate compressed updates and (ii) methods that reduce by also learning low-rank factors). Other related methods in this area are correctly cited but not well-discussed and not considered in the evaluation, such as FedPara [1], FedDLR [2], FEDHM [3]. Additionally, related papers that I believe should be included and discussed are LBGM [4] and FetchSGD [5].
Another line of works that should be considered is subnetwork training in FL, for example FjORD [6], which achieves training and communication efficiency by locally training subnetwork via Ordered Dropout. 



[1] FedPara: Low-rank Hadamard Product for Communication-Efficient Federated Learning, ICLR 2022

[2] Communication-Efficient Federated Learning with Dual-Side Low-Rank Compression

[3] FedHM: Efficient Federated Learning for Heterogeneous Models via Low-rank Factorization

[4] RECYCLING MODEL UPDATES IN FEDERATED LEARNING: ARE GRADIENT SUBSPACES LOW-RANK?, ICLR 2022

[5] FetchSGD: Communication-Efficient Federated Learning with Sketching, ICML 2020

[6] FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropout, NeurIPS 2021

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: See Weaknesses
soundness: 2
strengths: -Very clear narrative and motivation. Bi-directional compression is very desirable for FL and still a relatively open problem. 

-The experiments perform very well against full-sized counterparts. The variance correction alleviates client drift and enables greater numbers of client participation.

-The convergence rate is good and clear proofs are provided for all guarantees. 

-The technique seems like a new approach to low-rank FL and comes equipped with an interesting variance reduction mechanism. As bi-directional compression is still relatively rare in the compressive FL landscape, this work could be valuable, but please see weakness.
summary: The authors introduce a strategy (FeDRLT) for federated training which enables cheaper communication and client computational costs by training over low-rank decompositions of weights. Their algorithm includes a variance correction term to reduce client drift. The convergence of DRLT is $\mathcal{O}(1/T)$ with respect to minimal gradient norm. The authors perform LLSR and CIFAR-10 experiments of FeDRLT against FedLin and pure FedAvg, which performs respectably.
weaknesses: -The work is at worst incremental and at best, not adequately compared against similar efforts. The authors must compare against one or more compression works which shrink the gradient and/or weights. These works include FetchSGD [1] (gradient compression), ComFetch [2] (bi-directional compression + correction), Fjord [3] (model splitting), LASER [4] (gradient compression, HeteroFL [5] (model splitting), PriSM [6] (model splitting), etc. The field of compressive FL is rich (and saturated) and the methods described in the paper are reminiscent of other approaches. 

-The variance correction mechanism is not a novel approach for compressed federated learning. In FL, sometimes this approach is referred to as "error feedback," and is necessary for most compression techniques [5] to compensate for reconstruction error, but doubles as a client-drifting mechanism as it is aggregated over all clients. See [6] for another mechanism and general discussion of variance reduction for distributed SGD. The authors should comment their approach in light of this existing literature. 

-The experiments are weak. LLSR is insufficient nowadays to demonstrate the efficacy of an FL algorithm. Although CIFAR-10 and CIFAR-100 experiments are conducted, it does not appear that there is any ablation over varying degrees of heterogeneity, which is absolutely necessary for a work which is attempting to combat client drift. The authors should ablate over varying Dirichlet allocations of classes and compare their algorithm to a few other compression works or at least mimic their setups and compare cited numbers. 

[1] Rothchild, D., Panda, A., Ullah, E., Ivkin, N., Stoica, I., Braverman, V., ... & Arora, R. (2020, November). Fetchsgd: Communication-efficient federated learning with sketching. In International Conference on Machine Learning (pp. 8253-8265). PMLR.

[2] Rabbani, T., Feng, B., Bornstein, M., Sang, K. R., Yang, Y., Rajkumar, A., ... & Huang, F. (2021). Comfetch: Federated learning of large networks on constrained clients via sketching. arXiv preprint arXiv:2109.08346.

[3] Horvath, S., Laskaridis, S., Almeida, M., Leontiadis, I., Venieris, S., & Lane, N. (2021). Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 34, 12876-12889.

[4] Makkuva, A. V., Bondaschi, M., Vogels, T., Jaggi, M., Kim, H., & Gastpar, M. C. (2023). Laser: Linear compression in wireless distributed optimization. arXiv preprint arXiv:2310.13033.

[5] Ivkin, N., Rothchild, D., Ullah, E., Stoica, I., & Arora, R. (2019). Communication-efficient distributed SGD with sketching. Advances in Neural Information Processing Systems, 32.
[6] Liang, X., Shen, S., Liu, J., Pan, Z., Chen, E., & Cheng, Y. (2019). Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv:1912.12844.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Please check Weaknesses section
soundness: 2
strengths: Overall, the paper is well-structured and clearly written, making it relatively easy to follow the development of ideas and contributions. The flow of the narrative allows readers to engage with the paper’s content without difficulty. 

The inclusion of thorough discussions between technical sections, such as detailed explanations following each lemma and theorem, is particularly valuable. These discussions help clarify the purpose and implications of the theoretical results, making the technical content more accessible and aiding readers in understanding the significance of each result within the broader context of the paper.

The algorithm is presented effectively, with a well-organized description and clear pseudo-code. This clarity in presentation facilitates understanding of the method and makes it easier for others to replicate or build upon the approach.

Additionally, the paper includes an extensive experimental section in the appendix, showcasing a wide range of deep neural network (DNN) experiments. This supplementary section broadens the paper’s experimental validation, demonstrating the versatility and effectiveness of the proposed method across various architectures and datasets. The breadth of experiments contributes to a more comprehensive evaluation, which is especially beneficial for readers interested in practical applications of the theoretical findings.
summary: This paper introduces a federated dynamical low-rank training (FeDLRT) approach aimed at reducing both compute and communication costs for clients in horizontal federated learning, addressing two key bottlenecks in this field. FeDLRT leverages dynamical low-rank splitting methods to construct a shared, global low-rank basis for network weights, enabling clients to train on a much smaller coefficient matrix rather than the full model. The global low-rank basis remains consistent across clients, allowing for an integrated variance correction scheme and ensuring convergence to a stationary point. Additionally, FeDLRT dynamically adjusts the rank through augmentation and truncation, optimizing resource usage in real-time.

The authors validate FeDLRT’s effectiveness on various computer vision benchmarks, demonstrating significant reductions—up to an order of magnitude—in both client compute and communication requirements, while maintaining high accuracy.
weaknesses: 1. **Abstract Length and Clarity**: The abstract is brief and could be expanded to provide a clearer, more comprehensive overview of the main ideas and contributions of the paper. Currently, it may be difficult for readers to fully grasp the paper’s objectives and significance from the abstract alone.

2. **Introduction and Literature Review**: Both the introduction and the literature review sections are quite short and lack depth. An expanded literature review would provide readers with a better understanding of the existing work in the field and how this paper’s contributions fit within that context.

3. **Client Drift Reduction Methods**: The paper does not discuss several important client drift reduction techniques, such as ProxSkip, S-Local-SVRG, and 5GCS. Notably, S-Local-SVRG predates FedLin and introduces essential concepts for handling client drift. The TAMUNA method also offers communication acceleration, variance reduction, and client drift correction through compression, which could provide useful context for this paper.
    - References:
        - Mishchenko, Konstantin, et al. "Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!." International Conference on Machine Learning. PMLR, 2022.
        - Hu, Zhengmian, and Heng Huang. "Tighter analysis for proxskip." International Conference on Machine Learning. PMLR, 2023.
        - Gorbunov, Eduard, Filip Hanzely, and Peter Richtárik. "Local sgd: Unified theory and new efficient methods." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
        - Grudzień, Michał, Grigory Malinovsky, and Peter Richtárik. "Can 5th generation local training methods support client sampling? yes!." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
        - Condat, Laurent, et al. "TAMUNA: Doubly Accelerated Federated Learning with Local Training, Compression, and Partial Participation." International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023.

Could you please add a comparison in the table that includes not only the mentioned papers but also other relevant works? This would provide a more comprehensive view of the existing literature and allow readers to better understand how your approach stands in relation to other methods.

4. **Compression in Federated Learning**: The literature review would also benefit from mentioning works on local methods for federated learning that incorporate compression. This line of research is relevant for addressing communication efficiency, an area where this paper aims to contribute.
    - Relevant papers:
        - Haddadpour, Farzin, et al. "Federated learning with compression: Unified analysis and sharp guarantees." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
        - Li, Zhize, et al. "SoteriaFL: A unified framework for private federated learning with communication compression." Advances in Neural Information Processing Systems 35 (2022): 4285-4300.
        - Meinhardt G. et al. Prune at the Clients, Not the Server: Accelerated Sparse Training in Federated Learning //arXiv preprint arXiv:2405.20623. – 2024.

5. **Notation and Formulation**: The notation used in the formulation is non-standard and may confuse readers. The symbol $ C $ is commonly used to denote the client cohort size (i.e., the mini-batch size of clients), while other symbols like $ M $ or $ n $ are often used for the total number of clients. Changing this notation would improve clarity.

6. **Client Drift Correction Communication Requirements**: The paper mentions that client drift correction requires additional communication. However, recent work, such as ProxSkip and SCAFFOLD, shows that client drift correction can be achieved without extra communication. Referencing these methods and discussing this point would clarify the communication requirements of different approaches.

    - Reference: Yu, Yaodong, et al. "TCT: Convexifying federated learning using bootstrapped neural tangent kernels." Advances in Neural Information Processing Systems 35 (2022): 30882-30897.

7. **Lipschitz Continuity of Gradients**: The paper's assumptions about Lipschitz continuity (or \( L \)-smoothness) of gradients are not rigorously defined. It would be helpful to clearly state these assumptions to ensure they align with the rest of the analysis.

8. **Clarity of Lemma 1**: The statement of Lemma 1 is somewhat unclear. To improve readability, it would be beneficial to make this lemma more rigorous and precise.

9. **Theorem 1**: Theorem 1 is also ambiguously stated, particularly regarding the meaning of the inequality provided. Adding a discussion to explain the significance of this inequality and how it relates to the paper's objectives would be beneficial.

10. **Theorem 2**: Similar to Theorem 1, Theorem 2 is stated in a way that may be confusing to readers. Providing a clear interpretation of the inequality and its implications would enhance understanding.

11. **Convergence Rate in Theorem 3**: In Theorem 3, the first term exhibits a convergence rate of \(1/T\), but the second term does not decrease (even with a diminishing step size). This contrasts with other methods that correct for client drift, which offer convergence guarantees to the exact minimizer without residual noise or error terms. It would be helpful to explain why this residual term persists in the analysis.

12. **Assumption 1**: Assumption 1 appears restrictive but lacks commentary. Including a discussion on the motivation and implications of this assumption would clarify its role in the analysis and inform readers about its necessity.

13. **Clarity of Theorem 4**: Theorem 4 is somewhat confusing, especially regarding the inequality it presents. A more thorough explanation of this inequality and its relevance to the paper’s objectives would be beneficial.

14. **Corollary 1 Convergence Rate**: Similar to Theorem 3, Corollary 1 includes a term with a convergence rate of \(1/T\) but also a second, non-diminishing term, even with a decreasing step size. Notably, other client drift-correction methods guarantee convergence to the exact minimizer without such persistent error terms. Discussing this difference would improve clarity.

15. **Connections to Strongly Convex or PL Cases**: The current theoretical results are limited to the general non-convex setting, which tends to yield conservative bounds. There are no results for strongly convex, convex, or PL-conditioned non-convex cases, though the first set of experiments is on a linear regression task, a convex problem. Clarifying how the theoretical findings connect to the experiments would enhance coherence between the theory and practical validation.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 2
questions: 1) As mentioned in table 1, FeDLRT enjoys a lower computation, memory and communication costs that scales linearly with $n$ unlike other current algorithms. This is a significant strength of this work so it might be helpful to mention this in Section 1. 

2) (line 210) If there is no page limit, it might be helpful to add the proof of lemma 1 or a sketch of the proof to the main body of the paper.

3) (line 210) If i understand correctly, using Lemma 1 the authors are able to reduce the communication costs. This could be explained in more detail.

4) (Figure 1) You can consider placing Figure 1 on page 6.

5) It would be interesting to see computational results with different singular value truncation threshold. This could be added or the effect could be explained briefly (if there is a page limit). Further, how is this selected?

6)  Many plots in this paper can be improved for neatness and clarity.
soundness: 3
strengths: 1) This work is well motivated. The challenges faced in horizontal federated learning are clearly stated and this work introduces a new algorithm to address these issues.

2) Computational results are promising.

3) Authors provide convergence results for their algorithm.
summary: In this work, the authors propose a new algorithm to perform the task of horizontal federated learning. In this particular setting, all clients share the same model architecture and data features. The compute available on the client side is fairly limited and the costs associated with the communication between the central server and the clients are expensive. Current state of the art federated learning algorithms suffer from memory, compute and communication costs that scale quadratically with the size of the problem. 

To address the aforementioned issues, the authors propose a federated dynamical low-rank training scheme (FeDLRT) with and without variance correction, incorporating both a full and a simple variance correction method. The proposed method transfers only low-rank factors between the server and clients, hereby reducing the communications costs as compared to traditional methods. Furthermore, each client optimize over a small coefficient matrix. The memory, compute and communication costs of FeDLRT scale linearly with $n$. 

The authors provide convergence result of their algorithm with full and simple variance correction schemes. To show the convergence guarantees to a stationary point, the work assume that the client and server-side loss functions are $L$-smooth but not necessarily convex. Finally, the authors demonstrate the efficiency of FeDLRT in an array of computer vision benchmarks and show a reduction of client compute and communications costs up to an order of magnitude with minimal impacts on global accuracy.
weaknesses: 1) The authors compare the computational costs of their scheme with 3 algorithms in table 1. However, in their experiments their only compare with FedLin. It would be helpful to compare their work with the other algorithms.

2) The description of the algorithm (section 3.1) can be improved. The authors should try to explain each step of their algorithm better. Also Algorithm 2 (which is not an algorithm) is placed in the appendix. As far as I noticed, there is no mention of Algorithm 2 in main body of the paper. Yet Algorithm 2 contains the important definitions/notations that are used throughout section 3.1. The authors can consider adding all these concepts in Section 3.1 while they explain the algorithm.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. In table 1, what is “b”? I think “b” was not introduced before. Is it a batchsize? 
2. Why in Figure 6, when clients increase from 1 to 4 , accuracy increases, but later decreases? This is not intuitive to me. 
3. It is also not very intuitive to me - why does the accuracy drop with a larger number of clients? Since with larger number clients, the number of local steps is smaller, it might point to the better performance of methods without variance reduction, such as FedAvg. I am also wondering if such behavior comes from suboptimal choice of hyperparameters. 
4. Could you also plot confidence intervals together with the median? 
5. Table 1 is slightly too small, if printed on the paper. 
6. I did not fully understand the algorithm. Why do you need to do basis augmentation and what does it mean? Also why is the $\tilde S^\star$ not diagonal?
soundness: 3
strengths: The paper is well written and easy to follow.
The paper provides proof of convergence of their proposed method when local gradients on clients are deterministic.
The paper provides a way of combining their algorithm with variance correction due to difference in data distribution on different clients.
The paper provides experimental verification of their proposed method.
summary: The paper considers federated learning training with dynamical low-rank training scheme that allows to reduce both computations, since the training is performed directly in the low-rank space, as well as communications as only low-rank representations of neural networks need to be communicated instead of the full layers. This allows for efficient training in the low-resource & low-communication FL setup.
weaknesses: 1. The paper provides convergence guarantees for their method only if the gradients are deterministic, which is limiting the potential applications of their algorithm. 

Experimental evaluation is limited: 

2. Experimental results are provided only for the artificial dataset, and for cifar 10 and cifar 100 datasets, which are not FL-related benchmarks. Evaluating on more realistic FL datasets, such as [R1, R2] would make the paper stronger.

3. Paper does not give all of the details of experiments, thus not reproducible. Several key details that are missing: 
3.1. How learning rate was chosen in Cifar-10 experiments
3.2. How the data was split across the clients in Cifar-10 experiments. 
3.3. On Cifar-10 experiments first warm-up is performed on 1 client, but how that 1 client was chosen is not mentioned in the paper. 

4. Paper does not tune the learning rate, but uses the same learning rate for different algorithms - that might give advantage to some algorithms. Tuning the learning rate is needed for fair comparison. 

5. Paper shows only 93% of accuracy of Cifar10 for 32 workers (I believe it is coming from suboptimal stepsize schedule that is just constant over training), which is quite low and quite far from stoa Cifar10 accuracy. Analysis of how close the proposed algorithm can reach to stoa accuracy is missing.


[R1] Terrail et al, FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings. 
[R2] Caldas et al, LEAF: A Benchmark for Federated Settings.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: See in weaknesses.
soundness: 2
strengths: 1. The proposed method is well-motivated, the paper reduces the number of training parameters using the dynamic low-rank approximation method with less performance sacrifice.
2. This paper gives the convergence analysis of the federated dynamical low-rank training (FeDLRT) method.
3. The empirical results show that the federated dynamical low-rank training (FeDLRT) method is better than FedLin.
summary: To reduce client computing and communication costs, this paper proposes a dynamic low-rank training method. The algorithm creates a global low-rank basis of network weights, enabling client training on a small coefficient matrix. This paper also gives the theoretical convergence guarantee of the algorithm with the variance correction scheme.The authors provide empirical validations on the theoretical results as well.
weaknesses: 1. The method only considers the full participation case without partial participation.
2. In addition to FedLin, other low-rank training methods should be considered such as [1].
3. In experiments, the number of clients is too small. In more realistic settings, more clients and partial participation should be considered.

[1] Nam Hyeon-Woo, Moon Ye-Bin, Tae-Hyun Oh. FedPara: Low-rank Hadamard Product for Communication-Efficient Federated Learning. ICLR 2022.

Meta-review: This work introduces FeDLRT, a federated dynamical low-rank training scheme that reduces client compute and communication costs in horizontal federated learning. By leveraging manifold-constrained optimization, FeDLRT trains a small coefficient matrix per client using a global low-rank basis, with dynamic augmentation and truncation to optimize resource utilization. The method ensures global loss descent and convergence, while maintaining accuracy comparable to traditional methods like FedAvg and FedLin on computer vision benchmarks.

Most reviewers indicate that paper introduces an interesting method for low-rank training in the federated setting. However, a concern shared by several reviewer is the lack of clarity in in comparing the proposed method with other state-of-art algorithms. 

The AC shares these concerns and believes the paper would benefit from a major revision to address the highlighted issues.

Decision: Reject