RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks

# RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks
Source: [https://arxiv.org/html/2609.00078](https://arxiv.org/html/2609.00078)
Rohit BhagatGhadir AyacheRawad BitarYanmin GongSalim El Rouayheb††thanks:Xingran Chen is with the Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore 487372 \(E\-mail: xingranc@ieee\.org\)\. Ghadir Ayache is with the LinkedIn, New York, NY 10118, USA \(E\-mail: ayache\.ghad@gmail\.com\)\. Rawad Bitar is with the Chair of Communications Engineering, Technical University of Munich, 80333 Munich, Germany \(E\-mail: rawad\.bitar@tum\.de\)\. Yanmin Gong is with School of Engineering Medicine and the Department of Computer Science, Texas A&M University, College Station, TX 77843, USA \(E\-mail: yanmin\.gong@tamu\.edu\)\. Rohit Bhagat and Salim El Rouayheb are with Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA \(E\-mail: \{rb1395, sye8\}@scarletmail\.rutgers\.edu\)\. This paper has been accepted by IEEE ITW 2026\.

###### Abstract

Parameter\-efficient fine\-tuning methods such as LoRA have become a standard approach for adapting large foundation models\. Adopting fine\-tuning to distributed settings faces several challenges\. Most existing distributed LoRA methods rely on centralized aggregation, and gossip\-based decentralized LoRA requires repeated synchronization among multiple model copies\. Both methods incur significant communication overhead and introduce errors due to simultaneous aggregation of multiple model updates\. In this paper, we take a different perspective and propose a random\-walk\-based LoRA fine\-tuning scheme\. Instead of maintaining multiple model replicas, a single model token traverses the network and is updated sequentially using local fine\-tuning objectives\. This design eliminates the need for global synchronization, substantially reduces communication and computation costs, and avoids aggregation errors\. We provide rigorous convergence guarantees for non\-convex objectives under standard assumptions\. Through empirical results on multiple NLP tasks and graph topologies, we show that the proposed method achieves competitive task performance with substantially less communication and computation than gossip\-based LoRA\.

## IIntroduction

Foundation models such as GPT\-4\[[1](https://arxiv.org/html/2609.00078#bib.bib23)\], LLaMA\[[2](https://arxiv.org/html/2609.00078#bib.bib22)\], and BERT\[[3](https://arxiv.org/html/2609.00078#bib.bib21)\]have transformed artificial intelligence, achieving strong performance on tasks ranging from translation to summarization\[[4](https://arxiv.org/html/2609.00078#bib.bib12),[5](https://arxiv.org/html/2609.00078#bib.bib20)\]\. To achieve strong performance on domain\-specific tasks, these models often need to be adapted using local or task\-specific data\. However, their scale, often ranging from10810^\{8\}to101110^\{11\}parameters, makes full fine\-tuning computationally expensive, communication\-heavy, and prone to overfitting\. Parameter\-efficient fine\-tuning \(PEFT\) methods, especially low\-rank adaptation \(LoRA\), address this challenge by updating only a small number of additional parameters while keeping the backbone model frozen\[[6](https://arxiv.org/html/2609.00078#bib.bib11)\]\. As a result, LoRA substantially reduces the computational and communication costs of fine\-tuning\.

The benefits of LoRA are especially important in distributed and resource\-constrained applications, such as healthcare, edge personalization, and enterprise AI, where privacy, bandwidth, and data\-sovereignty constraints often prevent raw data from being centralized\. In such settings, fine\-tuning must be performed through distributed collaboration across multiple data owners or edge nodes\. Among them, federated LoRA methods\[[7](https://arxiv.org/html/2609.00078#bib.bib18),[8](https://arxiv.org/html/2609.00078#bib.bib19),[9](https://arxiv.org/html/2609.00078#bib.bib17),[10](https://arxiv.org/html/2609.00078#bib.bib16),[11](https://arxiv.org/html/2609.00078#bib.bib15),[12](https://arxiv.org/html/2609.00078#bib.bib14),[13](https://arxiv.org/html/2609.00078#bib.bib13)\]have become a predominant approach\. However, these methods rely on centralized aggregation through a parameter server, which introduces communication and memory overhead and creates a single point of failure\. To remove the need for central coordination, Ghiasvand et al\.\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]recently proposed a gossip\-based decentralized LoRA method\. Nevertheless, gossip\-based methods require nodes to exchange model updates with their neighbors repeatedly, which can still incur substantial communication overhead, especially on dense or bandwidth\-limited networks\.

More importantly, LoRA updates are of the formW=B​AW=BAwhere the modelW∈ℝd1×d2W\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}is factored into two low\-rank matricesA∈ℝr×d2A\\in\\mathbb\{R\}^\{r\\times d\_\{2\}\}andB∈ℝd1×rB\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\}withr≪min⁡\{d1,d2\}r\\ll\\min\\\{d\_\{1\},d\_\{2\}\\\}\. In federated and gossip\-based learning, the local modelsWiW\_\{i\}of the nodes need to be averaged at every round\. To avoid communicating their localWi=Bi​AiW\_\{i\}=B\_\{i\}A\_\{i\}’s, the nodes send their factor matricesAiA\_\{i\}andBiB\_\{i\}\. Aggregation can happen in two ways, each with its own drawback: \(i\) averaging the factors introduces a*bilinear mismatch*\[[14](https://arxiv.org/html/2609.00078#bib.bib33),[15](https://arxiv.org/html/2609.00078#bib.bib34),[16](https://arxiv.org/html/2609.00078#bib.bib35),[17](https://arxiv.org/html/2609.00078#bib.bib36)\], since∑iBi​Ai≠\(∑iBi\)​\(∑iAi\)\\sum\_\{i\}B\_\{i\}A\_\{i\}\\neq\(\\sum\_\{i\}B\_\{i\}\)\(\\sum\_\{i\}A\_\{i\}\); and \(ii\) computingWi=Bi​AiW\_\{i\}=B\_\{i\}A\_\{i\}, averaging them and doing SVD to get a low\-rank factorization ofWW; introducing additional computation and potential truncation errors\.

To address these limitations, we advocate token\-based random\-walk learning as a scalable alternative\. A token, consisting of the current pair of low\-rank factors\(At,Bt\)\(A\_\{t\},B\_\{t\}\), traverses the graph by moving at each iteration from its current node to a randomly selected neighbor, where it is updated using that node’s local data\[[18](https://arxiv.org/html/2609.00078#bib.bib27),[19](https://arxiv.org/html/2609.00078#bib.bib26),[20](https://arxiv.org/html/2609.00078#bib.bib28)\]\. Random\-walk learning differs from consensus\- and gossip\-based methods\[[7](https://arxiv.org/html/2609.00078#bib.bib18),[4](https://arxiv.org/html/2609.00078#bib.bib12)\]: rather than maintaining and synchronizing local models kept at each node, it propagates a single model through the network\. This offers two main advantages\. First, at each iteration, communication and computation are devoted to advancing a single model trajectory rather than updating and reconciling local models\. Second, the sequential update of the model at each visited node avoids the drawbacks of simultaneously aggregating multiple updates\. While their inherently sequential nature may be less advantageous in applications requiring rapid convergence, random\-walk methods offer an attractive alternative suitable for applications running in the background or requiring convergence with low communication and computation overhead\.

Our contributions are summarized as follows:

1. \(i\)We propose random\-walk\-based LoRA fine\-tuning as a low communication overhead alternative to gossip\-based LoRA\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\. This design enables decentralized fine\-tuning without a parameter server or synchronous neighbor\-wise aggregation\. We also provide rigorous convergence guarantees for non\-convex objectives \(Theorem[1](https://arxiv.org/html/2609.00078#Thmtheorem1)\)\.
2. \(ii\)We conduct experiments on several GLUE benchmark tasks using complete and ring communication graphs\. The training data are partitioned across nodes in an*i\.i\.d\.*manner\. Compared with the gossip\-based decentralized LoRA baseline\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\], RW\-LoRA maintains comparable accuracies while significantly reducing both communication and computational overhead \(Fig\.[1](https://arxiv.org/html/2609.00078#S6.F1)\)\.

## IISystem Model

We consider a set of nodes collaborating to fine\-tune a large model\. Nodes hold local iid datasets111Extending RW\-LoRA to non\-*i\.i\.d\.*data is left for future work\.that can be used for fine\-tuning, and they are able to communicate only with their neighbors\. We represent the communication network as a graph, where each vertex corresponds to a node and each edge indicates that the two corresponding nodes can communicate directly\. A token carrying the model parameters is passed from node to node and moves on this graph\.

###### Definition 1\(Communication topologies and random walks\)\.

A communication topology is defined as a finite undirected graph𝒢≜\(𝒱,E\)\\mathcal\{G\}\\triangleq\(\\mathcal\{V\},E\)with the set of nodes𝒱=\[N\]\\mathcal\{V\}=\[N\]and the set of edgesE⊆\(𝒱2\)E\\subseteq\\binom\{\\mathcal\{V\}\}\{2\}\. A random walk\{vt\}t⩾0:Ω→𝒱ℤ\+\\left\\\{v\_\{t\}\\right\\\}\_\{t\\geqslant 0\}:\\Omega\\to\\mathcal\{V\}^\{\\mathbb\{Z\}\_\{\+\}\}on this graph can be defined by the common transition probability matrixP:𝒱→ℳ⁡\(𝒱\)P:\\mathcal\{V\}\\to\\mathcal\{M\}\(\\mathcal\{V\}\), where the probability of transition from nodeuuto nodevvin one time step at timet∈ℤ\+t\\in\\mathbb\{Z\}\_\{\+\}, isPu​v≜Pr⁡\(vt\+1=v\|vt=u\)P\_\{uv\}\\triangleq\\mathrm\{Pr\}\\left\(v\_\{t\+1\}=v\\,\\middle\|\\,v\_\{t\}=u\\right\)\.

Without loss of generality, we assume thatPu​v\>0P\_\{uv\}\>0for all nodesvvconnected to nodeuuin graph𝒢\\mathcal\{G\}\.

The stationary distribution describes the long\-run fraction of time that the random walk spends at each node\. LetPPbe the transition matrix defined in Definition[1](https://arxiv.org/html/2609.00078#Thmdefinition1)\. A probabilityπ\\piis called a stationary distribution ifπ=π​P\\pi=\\pi P\.

Letπ0\\pi\_\{0\}denote the initial distribution, and letπt=Pt​π0\\pi\_\{t\}=P^\{t\}\\pi\_\{0\}denote the distribution at time steptt\. Forϵ\>0\\epsilon\>0, the mixing timeτmix​\(ϵ\)\\tau\_\{\\mathrm\{mix\}\}\(\\epsilon\)of\{vt\}t⩾0\\left\\\{v\_\{t\}\\right\\\}\_\{t\\geqslant 0\}is defined as\[[18](https://arxiv.org/html/2609.00078#bib.bib27), Definition 2\]:

τmix\(ϵ\)=inf\{t⩾1\|∀π0,dTV\(Ptπ0,π\)⩽ϵ\},\\displaystyle\\tau\_\{\\mathrm\{mix\}\}\(\\epsilon\)=\\inf\\left\\\{t\\geqslant 1\|\\forall\\pi\_\{0\},d\_\{\\text\{TV\}\}\(P^\{t\}\\pi\_\{0\},\\pi\)\\leqslant\\epsilon\\right\\\},wheredTV​\(⋅,⋅\)d\_\{\\text\{TV\}\}\(\\cdot,\\cdot\)is the total\-variance distance andπ0\\pi\_\{0\}is the initial distribution\.

We consider the decentralized stochastic optimization

min𝐰⁡f⁡\(𝐰\)=min𝐰⁡𝔼v∼π​\[fv​\(𝐰\)\],\\displaystyle\\min\_\{\\bf w\}\\,f\(\{\\bf w\}\)=\\min\_\{\\bf w\}\\,\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\[f\_\{v\}\(\{\\bf w\}\)\\right\],\(1\)where𝐰\{\\bf w\}denotes the set of parameters to be fine\-tuned \(details are provided in Section[III\-A](https://arxiv.org/html/2609.00078#S3.SS1)and Section[IV](https://arxiv.org/html/2609.00078#S4)\) andπ\\piis a probability distribution over the node set𝒱\\mathcal\{V\}\. In our setting,ffis the global fine\-tuning objective, whilefvf\_\{v\}is the local fine\-tuning objective associated with the data stored at nodevv\. Let𝒟v\\mathcal\{D\}\_\{v\}denote the local data distribution specific to uservv, then the local fine\-tuning objectivefvf\_\{v\}is given in stochastic form:

fv​\(𝐰\)=𝔼ξv∼𝒟v​\[Fv​\(𝐰,ξv\)\]\.\\displaystyle f\_\{v\}\(\{\\bf w\}\)=\\mathbb\{E\}\_\{\\xi\_\{v\}\\sim\\mathcal\{D\}\_\{v\}\}\\left\[F\_\{v\}\(\{\\bf w\};\\xi\_\{v\}\)\\right\]\.\(2\)
Let\{vt\}t⩾0\\\{v\_\{t\}\\\}\_\{t\\geqslant 0\}be a random walk on𝒱\\mathcal\{V\}with stationary distributionπ\\pi\. At timett, the model token is located at nodevtv\_\{t\}and is updated using only the local objective at that node\[[18](https://arxiv.org/html/2609.00078#bib.bib27),[19](https://arxiv.org/html/2609.00078#bib.bib26),[20](https://arxiv.org/html/2609.00078#bib.bib28)\]:

𝐰t\+1=𝐰t−η∇fvt\(𝐰t\),\\displaystyle\{\\bf w\}\_\{t\+1\}=\{\\bf w\}\_\{t\}\-\\eta\\nabla f\_\{v\_\{t\}\}\(\{\\bf w\}\_\{t\}\),\(3\)whereη\>0\\eta\>0is the stepsize\. \([3](https://arxiv.org/html/2609.00078#S2.E3)\) provides only a general random\-walk update rule for random\-walk\-based learning\. Its adaptation to the LoRA setting is presented in Section[IV](https://arxiv.org/html/2609.00078#S4)\.

## IIIPreliminaries on LoRA

### III\-ALow\-Rank Adaptation

Consider a pre\-trained modelΦ0\\Phi\_\{0\}consisting of multiple layers parameterized by weight matrices\. LetW0∈ℝd1×d2W\_\{0\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}denote the weight matrix of one layer\. In full fine\-tuning, one would learn an update matrixΔ​W∈ℝd1×d2\\Delta W\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}and useW=W0\+Δ​WW=W\_\{0\}\+\\Delta W\. To increase the efficiency of fine\-tuning, LoRA keepsW0W\_\{0\}fixed and restricts the update to a low\-rank form\[[6](https://arxiv.org/html/2609.00078#bib.bib11)\]Δ​W=B​A\\Delta W=BA, whereA∈ℝr×d2A\\in\\mathbb\{R\}^\{r\\times d\_\{2\}\},B∈ℝd1×rB\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\}, andr≪min⁡\{d1,d2\}r\\ll\\min\\\{d\_\{1\},d\_\{2\}\\\}\. Thus, the adapted weight matrix becomes

W=W0\+B​A\.\\displaystyle W=W\_\{0\}\+BA\.\(4\)
During the fine\-tuning phase, LoRA optimizes the factors \(also called adapters\)AAandBBinstead of directly updatingΔ​W\\Delta W\. This reduces the number of trainable parameters fromd1​d2d\_\{1\}d\_\{2\}tor⁡\(d1\+d2\)r\(d\_\{1\}\+d\_\{2\}\)and hence reduces the required computation and memory resources\[[7](https://arxiv.org/html/2609.00078#bib.bib18)\]\. Throughout the paper, we refer torras the LoRA rank, which is typically chosen from\{2,4,8,16\}\\\{2,4,8,16\\\}\.

### III\-BFederated LoRA\-based Fine\-Tuning

LoRA has become a popular approach for adapting foundation models\[[6](https://arxiv.org/html/2609.00078#bib.bib11)\]\. To enable efficient fine\-tuning across distributed data sources, LoRA has recently been incorporated into federated learning\. Representative methods include FLoRA\[[7](https://arxiv.org/html/2609.00078#bib.bib18)\], FedALT\[[8](https://arxiv.org/html/2609.00078#bib.bib19)\], FedLoRA\[[9](https://arxiv.org/html/2609.00078#bib.bib17)\], FRLoRA\[[10](https://arxiv.org/html/2609.00078#bib.bib16)\], FedSA\-LoRA\[[11](https://arxiv.org/html/2609.00078#bib.bib15)\], FedEx\-LoRA\[[12](https://arxiv.org/html/2609.00078#bib.bib14)\], and FedMomentum\[[13](https://arxiv.org/html/2609.00078#bib.bib13)\]\. These methods mainly differ in how they aggregate or personalize LoRA adapters across clients\. For example, FLoRA, FedALT, and FedLoRA address heterogeneous or personalized LoRA adapters through stacking, personalized components, or global\-local knowledge exchange\. Other methods, including FRLoRA, FedSA\-LoRA, FedEx\-LoRA, and FedMomentum, improve aggregation efficiency or stability through residual updates, selective factor sharing, exactness\-preserving corrections, or momentum\-based aggregation\. Most existing federated LoRA methods still rely on centralized aggregation through a server\. As a result, they inherit the communication and coordination bottlenecks of classical federated learning, which become increasingly limiting for large foundation models\.

### III\-CToken\-based Random\-Walk Learning

Decentralized learning bypasses the need of a central node coordinating the process\. The closest to our work is the recent work of\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\. The authors studied fully decentralized, gossip\-based LoRA fine\-tuning algorithm\. They established convergence guarantees for non\-convex objectives under standard assumptions\. In contrast, our work studies a random\-walk\-based LoRA method that avoids repeated server aggregation and neighbor\-wise synchronization\. This design reduces both communication and computational overhead\.

The literature on random\-walk\-based learning is broad, and we provide only a brief overview here\. Seminal work in this area includes\[[21](https://arxiv.org/html/2609.00078#bib.bib9),[22](https://arxiv.org/html/2609.00078#bib.bib10),[19](https://arxiv.org/html/2609.00078#bib.bib26)\], which laid the foundation for optimization methods driven by Markov chain sampling\. There are two directions to design and analyze token algorithms\. First,\[[21](https://arxiv.org/html/2609.00078#bib.bib9)\]studied incremental optimization and subdifferentials methods under Markov chain sampling\. Second,\[[19](https://arxiv.org/html/2609.00078#bib.bib26),[22](https://arxiv.org/html/2609.00078#bib.bib10)\]developed improved convergence guarantees for stochastic gradient and mirror\-descent methods under Markovian sampling\. A common feature of these results is that the convergence rate depends on the mixing timeτmix\\tau\_\{\\mathrm\{mix\}\}of the underlying Markov chain, often through terms such as𝒪⁡\(τmixT\)\+𝒪⁡\(τmixT\)\\mathcal\{O\}\\left\(\\frac\{\\tau\_\{\\mathrm\{mix\}\}\}\{T\}\\right\)\+\\mathcal\{O\}\\left\(\\sqrt\{\\frac\{\\tau\_\{\\mathrm\{mix\}\}\}\{T\}\}\\right\)\. For a more complete account of random\-walk\-based learning and token algorithms, we refer the reader to\[[18](https://arxiv.org/html/2609.00078#bib.bib27)\]\. Recently, random\-walk\-based learning has also been studied for data privacy\[[23](https://arxiv.org/html/2609.00078#bib.bib30),[24](https://arxiv.org/html/2609.00078#bib.bib31)\]and robustness to probabilistic and malicious node failures\[[25](https://arxiv.org/html/2609.00078#bib.bib29),[26](https://arxiv.org/html/2609.00078#bib.bib1),[27](https://arxiv.org/html/2609.00078#bib.bib32)\]\.

## IVThe RW\-LoRA Algorithm

In this section, we present the RW\-LoRA algorithm, summarized in Algorithm[1](https://arxiv.org/html/2609.00078#alg1)\.

Algorithm 1RW\-LoRA Algorithm1:Graph

𝒢=\(𝒱,E\)\\mathcal\{G\}=\(\\mathcal\{V\},E\), transition matrix

PP, stepsize

η\\eta, LoRA rank

rr, number of iterations

TT, pre\-trained weight matrix

W0∈ℝd1×d2W\_\{0\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}
2:Initialize

\[A\(0\)\]i​j∼𝒩⁡\(0,σ2\)\[A^\{\(0\)\}\]\_\{ij\}\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\)and

B\(0\)=𝟎B^\{\(0\)\}=\{\\bf 0\}
3:Initialize the random walk at node

v0∈𝒱v\_\{0\}\\in\\mathcal\{V\}
4:for

t=0,1,…,T−1t=0,1,\\ldots,T\-1, at node

vtv\_\{t\}do

5:Compute

W\(t\)=W0\+B\(t\)​A\(t\)W^\{\(t\)\}=W\_\{0\}\+B^\{\(t\)\}A^\{\(t\)\}\.

6:Update the LoRA factors via \([7](https://arxiv.org/html/2609.00078#S4.E7)\) – \([10](https://arxiv.org/html/2609.00078#S4.E10)\)\.

7:Sample the next node according to

vt\+1∼Pvt,⋅v\_\{t\+1\}\\sim P\_\{v\_\{t\},\\cdot\}\.

8:Transfer the token

\(A\(t\+1\),B\(t\+1\)\)\(A^\{\(t\+1\)\},B^\{\(t\+1\)\}\)to node

vt\+1v\_\{t\+1\}\.

9:endfor

10:return

A\(T\),B\(T\)A^\{\(T\)\},B^\{\(T\)\}and

W\(T\)=W0\+B\(T\)​A\(T\)W^\{\(T\)\}=W\_\{0\}\+B^\{\(T\)\}A^\{\(T\)\}

As discussed in Section[III\-A](https://arxiv.org/html/2609.00078#S3.SS1), we fine\-tune the model by optimizing the low\-rank factorsAAandBB\. Specifically, the optimization problem in \([1](https://arxiv.org/html/2609.00078#S2.E1)\) can be written as:

minA,B⁡f⁡\(W\)=minA,B⁡𝔼v∼π​\[fv​\(W\)\],\\displaystyle\\min\_\{A,B\}f\(W\)=\\min\_\{A,B\}\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\[f\_\{v\}\(W\)\\right\],\(5\)whereA∈ℝr×d2A\\in\\mathbb\{R\}^\{r\\times d\_\{2\}\},B∈ℝd1×rB\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\},fv:ℝd1×d2→ℝf\_\{v\}:\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}\\to\\mathbb\{R\}is the local fine\-tuning objective of nodevv, andπ\\piis a pre\-determined target distribution\.

For simplicity, we use∇\\nablato denote the gradient with respect toWW, i\.e\.,∇W\\nabla\_\{W\}, and use∇A\\nabla\_\{A\}and∇B\\nabla\_\{B\}to denote the gradients with respect toAAandBB, respectively\. We define

∇f~v​\(W\)≜∇Fv​\(W,ξv\)\.\\displaystyle\\nabla\\tilde\{f\}\_\{v\}\(W\)\\triangleq\\nabla F\_\{v\}\(W;\\xi\_\{v\}\)\.\(6\)
Given a target sampling distributionπ\\pi\(assumingπv\>0\\pi\_\{v\}\>0for allv∈𝒱v\\in\\mathcal\{V\}\), the Metropolis\-Hastings algorithm\[[19](https://arxiv.org/html/2609.00078#bib.bib26)\]provides a principled way to construct a RW on𝒢\\mathcal\{G\}with a transition matrixPPsuch thatπ\\piis the stationary distribution of the Markov chain defined byPP\.222The transition matrixPPdepends on both the target sampling distributionπ\\piand the graph𝒢\\mathcal\{G\}\. We re\-parameterize it asPπ,𝒢∈ℝ\+N×NP\_\{\\pi,\\mathcal\{G\}\}\\in\\mathbb\{R\}\_\{\+\}^\{N\\times N\}, and simply writePPwhen there is no risk of confusion\.Let\{vt\}t⩾0\\\{v\_\{t\}\\\}\_\{t\\geqslant 0\}be a random walk on𝒱\\mathcal\{V\}that evolves according to the transition matrixPP\. As mentioned in Section[II](https://arxiv.org/html/2609.00078#S2), \([3](https://arxiv.org/html/2609.00078#S2.E3)\) provides a general random\-walk update rule for vector\-valued parameters\. Since LoRA fine\-tuning optimizes matrix\-valued parameters, we extend this update rule to the two LoRA matricesAAandBB: At timett, the model token is located at nodevtv\_\{t\}, where the local fine\-tuning objective is used to update the LoRA factors forKKlocal steps\[[4](https://arxiv.org/html/2609.00078#bib.bib12),[6](https://arxiv.org/html/2609.00078#bib.bib11)\]\. Specifically, fork∈\{0,1,⋯,K−1\}k\\in\\left\\\{0,1,\\cdots,K\-1\\right\\\},

A\(t,k\+1\)=A\(t,k\)−η​∇Af~vt​\(W\(t,k\)\),\\displaystyle A^\{\(t,k\+1\)\}=A^\{\(t,k\)\}\-\\eta\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\),\(7\)B\(t,k\+1\)=B\(t,k\)−η​∇Bf~vt​\(W\(t,k\)\),\\displaystyle B^\{\(t,k\+1\)\}=B^\{\(t,k\)\}\-\\eta\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\),\(8\)After theKKlocal steps, the updated LoRA matrices are given by

A\(t\+1\)=A\(t,K\),\\displaystyle A^\{\(t\+1\)\}=A^\{\(t,K\)\},\(9\)B\(t\+1\)=B\(t,K\)\.\\displaystyle B^\{\(t\+1\)\}=B^\{\(t,K\)\}\.\(10\)The local updates are initialized withA\(t,0\)=A\(t\)A^\{\(t,0\)\}=A^\{\(t\)\}andB\(t,0\)=B\(t\)B^\{\(t,0\)\}=B^\{\(t\)\}\. The initial LoRA matrices are initialized asA\(0\)∈ℝr×d2A^\{\(0\)\}\\in\\mathbb\{R\}^\{r\\times d\_\{2\}\},\[A\(0\)\]i​j​∼​i\.i\.d\.​𝒩​\(0,σ2\)\[A^\{\(0\)\}\]\_\{ij\}\\overset\{\\emph\{i\.i\.d\.\}\\ \}\{\\sim\}\\mathcal\{N\}\(0,\\sigma^\{2\}\),B\(0\)=𝟎∈ℝd1×rB^\{\(0\)\}=\{\\bf 0\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\}, andW\(0\)=W0\+B\(0\)​A\(0\)W^\{\(0\)\}=W\_\{0\}\+B^\{\(0\)\}A^\{\(0\)\}, as adopted in\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\.

## VTheoretical Results

This section establishes the convergence of RW\-LoRA in the non\-convex setting under Assumptions[1](https://arxiv.org/html/2609.00078#Thmassumption1)–[5](https://arxiv.org/html/2609.00078#Thmassumption5)\. These assumptions are stated and discussed immediately after the theorem\.

###### Theorem 1\.

Let Assumptions[1](https://arxiv.org/html/2609.00078#Thmassumption1)∼\\sim[5](https://arxiv.org/html/2609.00078#Thmassumption5)hold\. Letϵ<12\\epsilon<\\frac\{1\}\{2\},πmin=minv∈𝒱⁡\{πv\}\\pi\_\{\\min\}=\\min\_\{v\\in\\mathcal\{V\}\}\\left\\\{\\pi\_\{v\}\\right\\\},τ⩾τmix​\(πmin​ϵ\)\\tau\\geqslant\\tau\_\{\\mathrm\{mix\}\}\(\\pi\_\{\\min\}\\epsilon\),T⩾τ2T\\geqslant\\tau^\{2\},η⩽14​L​T\\eta\\leqslant\\frac\{1\}\{4L\\sqrt\{T\}\}, we obtain333Here,𝒪~​\(⋅\)\\widetilde\{\\mathcal\{O\}\}\(\\cdot\)hides logarithmic factors in the relevant problem parameters\. For example,𝒪~​\(1/T\)\\widetilde\{\\mathcal\{O\}\}\(1/\\sqrt\{T\}\)may represent terms such as𝒪⁡\(log⁡T/T\)\\mathcal\{O\}\(\\log T/\\sqrt\{T\}\)or𝒪⁡\(log⁡\(c​T\)/T\)\\mathcal\{O\}\(\\log\(cT\)/\\sqrt\{T\}\), depending on the context\.:

1T\\displaystyle\\frac\{1\}\{T\}∑t=1T\(𝔼⁡\[‖∇Af​\(W\(t\)\)‖2\]\+𝔼⁡\[‖∇Bf​\(W\(t\)\)‖2\]\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\left\(\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\+\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\\right\)⩽\\displaystyle\\leqslant𝒪~​\(ϵ2\+L​τT\+L​τT\)\.\\displaystyle\\widetilde\{\\mathcal\{O\}\}\\left\(\\epsilon^\{2\}\+\\frac\{L\\tau\}\{\\sqrt\{T\}\}\+\\frac\{L\\tau\}\{T\}\\right\)\.\(11\)

First, Theorem[1](https://arxiv.org/html/2609.00078#Thmtheorem1)shows that the proposed RW\-LoRA algorithm converges to a stationary point in terms of the following first\-order stationarity measure\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]:

𝔼⁡\[‖∇Af​\(W\(t\)\)‖\]\+𝔼⁡\[‖∇Bf​\(W\(t\)\)‖\]\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\)\}\)\\\|\\right\]\+\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\)\}\)\\\|\\right\]\.This criterion is natural for LoRA fine\-tuning because the trainable variables are the low\-rank factorsAAandBB, rather than the full update matrixΔ​W\\Delta W\. Hence, stationarity should be evaluated with respect to these actual optimization variables\. The complete proofs are provided in Appendix[A](https://arxiv.org/html/2609.00078#A1)\.

Second, Theorem[1](https://arxiv.org/html/2609.00078#Thmtheorem1)indicates that the convergence rate depends on the mixing timeτ\\tauof the underlying Markov chain\. In particular, our bound has the form

𝒪~​\(ϵ2\+L​τT\+L​τT\)\.\\widetilde\{\\mathcal\{O\}\}\\left\(\\epsilon^\{2\}\+\\frac\{L\\tau\}\{\\sqrt\{T\}\}\+\\frac\{L\\tau\}\{T\}\\right\)\.This is broadly consistent with the rates obtained in standard random\-walk learning for vector\-valued objectives, where the dependence on the number of iterations typically appears as𝒪⁡\(τmixT\)\+𝒪⁡\(τmixT\)\\mathcal\{O\}\\left\(\\frac\{\\tau\_\{\\mathrm\{mix\}\}\}\{T\}\\right\)\+\\mathcal\{O\}\\left\(\\sqrt\{\\frac\{\\tau\_\{\\mathrm\{mix\}\}\}\{T\}\}\\right\)\[[21](https://arxiv.org/html/2609.00078#bib.bib9),[22](https://arxiv.org/html/2609.00078#bib.bib10),[19](https://arxiv.org/html/2609.00078#bib.bib26)\]\. There are, however, two differences\. First, our result is stated in𝒪~\\widetilde\{\\mathcal\{O\}\}notation, whereas the standard vector\-valued setting is often expressed in𝒪\\mathcal\{O\}notation\. Second, the coefficient of the1/T1/\\sqrt\{T\}term scales linearly with the mixing timeτ\\tauin our LoRA setting, while it scales asτmix\\sqrt\{\\tau\_\{\\mathrm\{mix\}\}\}in the standard vector\-valued case\. This difference arises from the low\-rank matrix factorization in LoRA: the trainable variables are the matricesAAandBB, and the updateΔ​W=B​A\\Delta W=BAintroduces additional coupling between the two factors\.

###### Assumption 1\(Submultiplicative property\)\.

The matrix norm∥⋅∥\\\|\\cdot\\\|used in this paper is submultiplicative, i\.e\.,‖B​A‖⩽‖B‖​‖A‖\\\|BA\\\|\\leqslant\\\|B\\\|\\\|A\\\|for any compatible matricesAAandBB\.

This assumption is mild and is satisfied by most commonly used matrix norms, such as the spectral norm, Frobenius norm,11\-norm, and∞\\infty\-norm\.

###### Assumption 2\(LL\-smooth, Assumption 4\.1 in\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\)\.

We assume that each local fine\-tuning objectivefvf\_\{v\}isLL\-smooth, i\.e\., for allW,W′∈ℝd1×d2W,W^\{\\prime\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}, we have

‖∇fv​\(W\)−∇fv​\(W′\)‖⩽L​‖W−W′‖\.\\\|\\nabla f\_\{v\}\(W\)\-\\nabla f\_\{v\}\(W^\{\\prime\}\)\\\|\\leqslant L\\\|W\-W^\{\\prime\}\\\|\.

###### Assumption 3\(Bounded gradient, Assumption 4\.2 in\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\)\.

We assume that the stochastic gradients are unbiased and that their expected squared norm remains uniformly bounded:

𝔼ξv∼𝒟v​\[∇f~v​\(W\)\]=∇fv​\(W\),\\displaystyle\\mathbb\{E\}\_\{\\xi\_\{v\}\\sim\\mathcal\{D\}\_\{v\}\}\\left\[\\nabla\\tilde\{f\}\_\{v\}\(W\)\\right\]=\\nabla f\_\{v\}\(W\),𝔼ξv∼𝒟v​\[‖∇f~v​\(W\)‖2\]⩽c2,v∈𝒱,\\displaystyle\\mathbb\{E\}\_\{\\xi\_\{v\}\\sim\\mathcal\{D\}\_\{v\}\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]\\leqslant c^\{2\},\\,\\,v\\in\\mathcal\{V\},whereξv\\xi\_\{v\}represents a randomly sampled subset of training data fromvv\-th node\.

Assumption[3](https://arxiv.org/html/2609.00078#Thmassumption3)is standard in decentralized optimization\[[4](https://arxiv.org/html/2609.00078#bib.bib12),[7](https://arxiv.org/html/2609.00078#bib.bib18),[9](https://arxiv.org/html/2609.00078#bib.bib17),[11](https://arxiv.org/html/2609.00078#bib.bib15)\]\. It helps bound the magnitude of the update steps, as in the analysis in Lemmas77and1111of\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\. For notational simplicity, we omit the subscriptξv∼𝒟v\\xi\_\{v\}\\sim\\mathcal\{D\}\_\{v\}when it is clear from the context\.

###### Assumption 4\(Bounded variance, Assumption 5\.1 in\[[28](https://arxiv.org/html/2609.00078#bib.bib24)\]\)\.

There existsσ2\\sigma^\{2\}such that for allv∈𝒱v\\in\\mathcal\{V\}and allW∈ℝd1×d2W\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}, we have:

𝔼⁡\[‖∇f~v​\(W\)−∇f​\(W\)‖2\]⩽σ2\.\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\-\\nabla f\(W\)\\\|^\{2\}\\right\]\\leqslant\\sigma^\{2\}\.

In Assumption[4](https://arxiv.org/html/2609.00078#Thmassumption4), the expectation𝔼\\mathbb\{E\}is taken over two sources of randomness: \(i\) the randomness in data sampling at nodevv, i\.e\.,ξv∼𝒟v\\xi\_\{v\}\\sim\\mathcal\{D\}\_\{v\}, and \(ii\) the randomness in the global objective, as defined in \([5](https://arxiv.org/html/2609.00078#S4.E5)\)\. It is used to control the stochastic noise arising from the random\-walk sampling process\[[28](https://arxiv.org/html/2609.00078#bib.bib24), Lemmas C\.1 & C\.2\]\.

Assumptions[3](https://arxiv.org/html/2609.00078#Thmassumption3)and[4](https://arxiv.org/html/2609.00078#Thmassumption4)are both necessary and play distinct roles in our analysis\. For vector\-valued optimization variables, one of these assumptions is often sufficient, since the other is not needed for the convergence proof\. In our setting, however, the optimization variables are the matrix\-valued LoRA factorsAAandBB, withΔ​W=B​A\\Delta W=BA\. BecauseAAandBBare updated separately, dropping either assumption would prevent us from completing the convergence proof\.

###### Assumption 5\(Assumption 4\.3 in\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\)\.

There exists constantsa\>0a\>0andb\>0b\>0such that:‖A\(t\)‖⩽a\\\|A^\{\(t\)\}\\\|\\leqslant a,‖B\(t\)‖⩽b\\\|B^\{\(t\)\}\\\|\\leqslant bfor all0⩽t⩽T0\\leqslant t\\leqslant T\.

In Assumption[5](https://arxiv.org/html/2609.00078#Thmassumption5), the constantsaaandbbare chosen uniformly overtt\. These constants may depend on the matrix dimensions, namelyrr,d1d\_\{1\}, andd2d\_\{2\}\.

## VIExperiments

In this section, we compare the proposed RW\-LoRA algorithm with a gossip\-based decentralized LoRA baseline\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\. The results show that RW\-LoRA significantly reduces both communication and computational overhead while avoiding the bilinear mismatch issue\.

### VI\-AExperiment Settings

#### VI\-A1Setup

We use RoBERTa\-base with 125M parameters\[[29](https://arxiv.org/html/2609.00078#bib.bib2)\]as the backbone model for all tasks\. Following\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\], we use a default LoRA rank ofr=16r=16, and additionally conduct an ablation study withr∈\{4,8,16,32\}r\\in\\left\\\{4,8,16,32\\right\\\}\. We use the defaultAdamWoptimizer with learning rate10−310^\{\-3\}\. The random\-walk fine\-tuning process is run over3030nodes\. At each communication round, the active node performsK=10K=10local training steps with batch sizeb=32b=32before passing the model token to the next node\. For reproducibility, all five runs use a fixed random seed of4242, except for the random\-walk process, which uses seeds11,22,33,44, and55across the five runs to generate different trajectories\.

#### VI\-A2Datasets

We evaluate the proposed RW\-LoRA algorithm on five GLUE datasets, covering two types of tasks:

1. \(i\)Sentence\-pair classification: We fine\-tune the base model on MRPC\[[30](https://arxiv.org/html/2609.00078#bib.bib8)\], QQP\[[31](https://arxiv.org/html/2609.00078#bib.bib5)\], QNLI\[[31](https://arxiv.org/html/2609.00078#bib.bib5),[32](https://arxiv.org/html/2609.00078#bib.bib6)\], and MNLI\[[31](https://arxiv.org/html/2609.00078#bib.bib5),[33](https://arxiv.org/html/2609.00078#bib.bib4)\]\. These tasks require the model to determine semantic equivalence, textual entailment, or whether a sentence contains the answer to a given question\.
2. \(ii\)Sentiment classification: We fine\-tune the base model on SST\-2\[[34](https://arxiv.org/html/2609.00078#bib.bib7)\], where the task is to classify each sentence as positive or negative\.

#### VI\-A3Baseline

We compare RW\-LoRA to the gossip\-based decentralized LoRA method introduced in\[[4](https://arxiv.org/html/2609.00078#bib.bib12)\]\.

#### VI\-A4Topologies

In our decentralized framework, nodes communicate exclusively along the edges of a fixed communication graph that connects3030nodes\. We focus on two topologies: ring graphs and complete graphs\. These two topologies represent two extremes in network connectivity\[[35](https://arxiv.org/html/2609.00078#bib.bib3),[26](https://arxiv.org/html/2609.00078#bib.bib1)\]\. The target distributionπ\\piis chosen as the uniform distribution, and the corresponding transition probability matrix is constructed using the Metropolis–Hastings rule\[[19](https://arxiv.org/html/2609.00078#bib.bib26)\]\.

MRPCSST2QNLIMNLIQQPRW \(Final Scores\)91\.32±\\pm0\.8793\.28±\\pm0\.5491\.35±\\pm0\.2284\.50±\\pm0\.0987\.61±\\pm0\.40Gossip \(Final Scores\)89\.2693\.5890\.7583\.5986\.59RW \(Best Scores\)91\.56±\\pm0\.7894\.03±\\pm0\.6491\.98±\\pm0\.3385\.90±\\pm0\.6388\.77±\\pm0\.41Gossip \(Best Scores\)90\.3094\.3890\.8085\.2088\.05
TABLE I:Accuracy under Complete GraphMRPCSST2QNLIMNLIQQPRW \(Final Scores\)90\.30±\\pm0\.8792\.96±\\pm0\.8790\.87±\\pm0\.4884\.83±\\pm0\.4082\.52±\\pm9\.68Gossip \(Final Scores\)83\.2693\.1290\.3383\.7286\.63RW \(Best Scores\)91\.61±\\pm0\.5193\.83±\\pm0\.3491\.51±\\pm0\.1785\.65±\\pm1\.0587\.87±\\pm0\.45Gossip \(Best Scores\)88\.4294\.0091\.0884\.8287\.58
TABLE II:Accuracy under Ring Graph

### VI\-BExperimental Results

##### Task Performance

The task performance of random\-walk\-based LoRA is reported in Tables[II](https://arxiv.org/html/2609.00078#S6.T2)&[II](https://arxiv.org/html/2609.00078#S6.T2)\. Table[II](https://arxiv.org/html/2609.00078#S6.T2)reports results on the complete graph, while Table[II](https://arxiv.org/html/2609.00078#S6.T2)reports results on the ring topology444In both tables, the performance metric forMRPC\\mathrm\{MRPC\}is F1, whereas the metric for all other datasets is accuracy\. For simplicity of presentation, we use the term “Accuracy” in the tables to refer to the corresponding task performance metric\.\. In both tables,Final Scoredenotes the model performance at the last training round, whereasBest Scoredenotes the highest performance achieved over all training rounds\. Both methods are run until convergence, resulting in different convergence horizons: approximately25002500time steps for RW\-LoRA and180180time steps for gossip\-based LoRA\. Although gossip\-based LoRA converges in fewer rounds, each round involves neighbor\-to\-neighbor synchronization across multiple nodes, leading to approximately5400054000local updates in total\. By contrast, RW\-LoRA activates only one node at each time step and requires approximately2500025000local updates before convergence\.

As shown in both tables, RW\-LoRA performs comparably to gossip\-based LoRA in both final and best accuracies on theMRPC\\mathrm\{MRPC\},QNLI\\mathrm\{QNLI\},MNLI\\mathrm\{MNLI\}, andQQP\\mathrm\{QQP\}tasks\. OnSST2\\mathrm\{SST2\}, RW\-LoRA achieves final and best accuracies comparable to those of gossip\-based LoRA\. Overall, these results demonstrate that RW\-LoRA consistently matches or exceeds the performance of gossip\-based LoRA across all evaluated tasks\. More importantly, RW\-LoRA achieves comparable performance with substantially lower communication and computation overhead\.

##### Communication and Computation Efficiency

Under gossip\-based LoRA, each node exchanges updates with its neighbors in every communication round\. Thus, the per\-node communication cost isO⁡\(degree×model​\_​size\)O\(\\mathrm\{degree\}\\times\\mathrm\{model\\\_size\}\), here0\.59​M0\.59Mfor the ring graph and8\.555​M8\.555Mfor the complete graph, and the total network\-wide cost per round isO⁡\(network​\_​size×degree×model​\_​size\)O\(\\mathrm\{network\\\_size\}\\times\\mathrm\{degree\}\\times\\mathrm\{model\\\_size\}\), here17\.7​M17\.7Mand256\.65​M256\.65Mfor the ring and complete graph, respectively\. In contrast, random\-walk\-based LoRA involves only one active transmission per round, from the current node to the next node on the walk\. Its total communication cost per round is thereforeO⁡\(model​\_​size\)O\(\\mathrm\{model\\\_size\}\), here0\.295​M0\.295Mfor both graphs\. For a fixed network sizeNNand a fixed number of local updatesKK, the computational cost scales linearly with the communication horizon\. Specifically, it isO⁡\(K×network​\_​size×time​\_​horizon\)O\(K\\times\\mathrm\{network\\\_size\}\\times\\mathrm\{time\\\_horizon\}\)for gossip\-based learning andK×time​\_​horizonK\\times\\mathrm\{time\\\_horizon\}for random\-walk learning\.

Fig\.[1](https://arxiv.org/html/2609.00078#S6.F1)shows the results on theQNLI\\mathrm\{QNLI\}dataset\. The dataset is partitioned across nodes in an*i\.i\.d\.*manner\. Although we evaluate all methods on five datasets, the accuracy curves exhibit similar trends across datasets; therefore, we report the results forQNLI\\mathrm\{QNLI\}only\. In Fig\.[1](https://arxiv.org/html/2609.00078#S6.F1), thexx\-axis denotes the communication overhead, measured by the total number of edge activations555Here, one edge activation corresponds to one communication event between two neighboring nodes\., while theyy\-axis represents the accuracy or loss\. As shown in Figs\.[1\(a\)](https://arxiv.org/html/2609.00078#S6.F1.sf1)and[1\(b\)](https://arxiv.org/html/2609.00078#S6.F1.sf2), RW\-LoRA achieves comparable or higher accuracy and converges with significantly lower communication costs than gossip\-based LoRA while requiring substantially lower communication costs\.

![Refer to caption](https://arxiv.org/html/2609.00078v1/Gossip_vs_RW_Figures/communication_ring.png)\(a\)
![Refer to caption](https://arxiv.org/html/2609.00078v1/Gossip_vs_RW_Figures/communication_complete.png)\(b\)

Fig\. 1:Accuracy vs\. communication overhead in a ring and complete graph\.
##### Ablation Study

![Refer to caption](https://arxiv.org/html/2609.00078v1/Gossip_vs_RW_Figures/rank.png)Fig\. 2:Task accuracies under different LoRA ranks\.We conduct the ablation study for the LoRA rank by consideringr∈\{4,8,16,32\}r\\in\\left\\\{4,8,16,32\\right\\\}\. Fig\.[2](https://arxiv.org/html/2609.00078#S6.F2)presents the task accuracies achieved under different LoRA ranks in a complete graph\. The results show that the performance remains largely unchanged across the these rank settings\. This indicates that RW\-LoRA is relatively insensitive to the choice of LoRA rank and can maintain competitive performance even with a small rank\.

## VIIConclusion

In this paper, we studied a decentralized random\-walk\-based LoRA framework\. Unlike existing federated and gossip\-based approaches that rely on multiple synchronized model copies, our method maintains a single mobile model that is updated sequentially across the network\. We established convergence guarantees for non\-convex objectives\. Experimental results demonstrate that the proposed method achieves competitive performance while being substantially more resource\-efficient than the gossip\-based LoRA algorithm\. Future work will explore additional information\-theoretic aspects of random\-walk LoRA algorithms\. In particular, it would be interesting to study heterogeneous networks in which nodes use different LoRA ranks\.

## References

- \[1\]OpenAI, J\. Achiam, S\. Adler, and et\.al\(2024\)GPT\-4 technical report\.External Links:2303\.08774,[Link](https://arxiv.org/abs/2303.08774)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p1.1)\.
- \[2\]H\. Touvron, T\. Lavril, G\. Izacard, and et\.al\(2023\)LLaMA: open and efficient foundation language models\.\.CoRRabs/2302\.13971\.External Links:[Link](http://dblp.uni-trier.de/db/journals/corr/corr2302.html#abs-2302-13971)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p1.1)\.
- \[3\]J\. Devlin, M\. Chang, K\. Lee, and et\.al\(2019\)BERT: pre\-training of deep bidirectional transformers for language understanding\.InNorth American Chapter of the Association for Computational Linguistics,External Links:[Link](https://api.semanticscholar.org/CorpusID:52967399)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p1.1)\.
- \[4\]S\. Ghiasvand, M\. Alizadeh, and R\. Pedarsani\(2025\)Decentralized low\-rank fine\-tuning of large language models\.InProceedings of the 1st Workshop for Research on Agent Language Models \(REALM 2025\),pp\. 334–345\.Cited by:[item i](https://arxiv.org/html/2609.00078#S1.I1.i1.p1.1),[item ii](https://arxiv.org/html/2609.00078#S1.I1.i2.p1.1),[§I](https://arxiv.org/html/2609.00078#S1.p1.1),[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§I](https://arxiv.org/html/2609.00078#S1.p4.1),[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p1.1),[§IV](https://arxiv.org/html/2609.00078#S4.p4.1),[§IV](https://arxiv.org/html/2609.00078#S4.p4.3),[§V](https://arxiv.org/html/2609.00078#S5.p2.1),[§V](https://arxiv.org/html/2609.00078#S5.p5.1),[§VI\-A1](https://arxiv.org/html/2609.00078#S6.SS1.SSS1.p1.1),[§VI\-A3](https://arxiv.org/html/2609.00078#S6.SS1.SSS3.p1.1),[§VI](https://arxiv.org/html/2609.00078#S6.p1.1),[Assumption 2](https://arxiv.org/html/2609.00078#Thmassumption2),[Assumption 3](https://arxiv.org/html/2609.00078#Thmassumption3),[Assumption 5](https://arxiv.org/html/2609.00078#Thmassumption5)\.
- \[5\]R\. Bommasani, D\. A\. Hudson, E\. Adeli, and et\.al\(2021\)On the opportunities and risks of foundation models\.ArXivabs/2108\.07258\.External Links:[Link](https://api.semanticscholar.org/CorpusID:237091588)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p1.1)\.
- \[6\]E\. J\. Hu, Y\. Shen, P\. Wallis, and et\. al\(2022\)LoRA: low\-rank adaptation of large language models\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p1.1),[§III\-A](https://arxiv.org/html/2609.00078#S3.SS1.p1.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1),[§IV](https://arxiv.org/html/2609.00078#S4.p4.1)\.
- \[7\]Z\. Wang, Z\. Shen, Y\. He, and et\.al\(2024\)FLoRA: federated fine\-tuning large language models with heterogeneous low\-rank adaptations\.InProceedings of the 38th International Conference on Neural Information Processing Systems,Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§I](https://arxiv.org/html/2609.00078#S1.p4.1),[§III\-A](https://arxiv.org/html/2609.00078#S3.SS1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1),[§V](https://arxiv.org/html/2609.00078#S5.p5.1)\.
- \[8\]J\. Bian, L\. Wang, L\. Zhang, and et\.al\(2025\)FedALT: federated fine\-tuning through adaptive local training with rest\-of\-world lora\.arXiv preprint arXiv:2503\.11880\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1)\.
- \[9\]L\. Yi, H\. Yu, G\. Wang, and et\.al\(2023\)FedLoRA: model\-heterogeneous personalized federated learning with lora tuning\.ArXivabs/2310\.13283\.External Links:[Link](https://api.semanticscholar.org/CorpusID:264405713)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1),[§V](https://arxiv.org/html/2609.00078#S5.p5.1)\.
- \[10\]Y\. Yan, C\. Feng, W\. Zuo, and et\. al\(2025\)Federated residual low\-rank adaption of large language models\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=e0rQRMUhs7)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1)\.
- \[11\]P\. Guo, S\. Zeng, Y\. Wang, and et\. al\(2025\)Selective aggregation for low\-rank adaptation in federated learning\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=iX3uESGdsO)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1),[§V](https://arxiv.org/html/2609.00078#S5.p5.1)\.
- \[12\]R\. Singhal, K\. Ponkshe, and P\. Vepakomma\(2025\)FedEx\-LoRA: exact aggregation for federated and efficient fine\-tuning of foundation models\.InFirst Workshop on Scalable Optimization for Efficient and Adaptive Foundation Models,Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1)\.
- \[13\]P\. Yan, Y\. Hua, H\. Wang, and et\.al\(2026\)FedMomentum: preserving lora training momentum in federated fine\-tuning\.ArXivabs/2603\.08014\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.00078#S3.SS2.p1.1)\.
- \[14\]Z\. Wang, Z\. Shen, Y\. He, G\. Sun, H\. Wang, L\. Lyu, and A\. Li\(2024\)FLoRA: federated fine\-tuning large language models with heterogeneous low\-rank adaptations\.Advances in Neural Information Processing Systems37,pp\. 22513–22533\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p3.1)\.
- \[15\]R\. Singhal, K\. Ponkshe, and P\. Vepakomma\(2025\)FedEx\-LoRA: exact aggregation for federated and efficient fine\-tuning of large language models\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),pp\. 1316–1336\.External Links:ISBN 979\-8\-89176\-251\-0Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p3.1)\.
- \[16\]H\. Zhang, D\. Kim, S\. Cha, and H\. Vikalo\(2026\)FedRot\-loRA: mitigating rotational misalignment in federated loRA\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=2X8Qi3VdjA)Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p3.1)\.
- \[17\]Y\. Xia, T\. Jahani\-Nezhad, M\. Bakshi, and R\. Bitar\(2026\)SeFoRA: sketch\-aggregated federated low\-rank adaptation with heterogeneous client ranks\.arXiv preprint arXiv:2608\.10144\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p3.1)\.
- \[18\]M\. Even\(2023\)Stochastic gradient descent under markovian sampling schemes\.InProceedings of the 40th International Conference on Machine Learning,Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p4.1),[§II](https://arxiv.org/html/2609.00078#S2.p4.1),[§II](https://arxiv.org/html/2609.00078#S2.p6.1),[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1)\.
- \[19\]B\. Johansson, M\. Rabi, and M\. Johansson\(2010\)A randomized incremental subgradient method for distributed optimization in networked systems\.SIAM Journal on Optimization20\(3\),pp\. 1157–1170\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p4.1),[§II](https://arxiv.org/html/2609.00078#S2.p6.1),[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1),[§IV](https://arxiv.org/html/2609.00078#S4.p4.1),[§V](https://arxiv.org/html/2609.00078#S5.p3.2),[§VI\-A4](https://arxiv.org/html/2609.00078#S6.SS1.SSS4.p1.1)\.
- \[20\]T\. Sun, Y\. Sun, and W\. Yin\(2018\)On markov chain gradient descent\.InProceedings of the 32nd International Conference on Neural Information Processing Systems,pp\. 9918–9927\.Cited by:[§I](https://arxiv.org/html/2609.00078#S1.p4.1),[§II](https://arxiv.org/html/2609.00078#S2.p6.1)\.
- \[21\]B\. Johansson, M\. Rabi, and M\. Johansson\(2007\)A simple peer\-to\-peer algorithm for distributed optimization in sensor networks\.2007 46th IEEE Conference on Decision and Control,pp\. 4705–4710\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1),[§V](https://arxiv.org/html/2609.00078#S5.p3.2)\.
- \[22\]C\. G\. Lopes and A\. H\. Sayed\(2007\)Incremental adaptive strategies over distributed networks\.IEEE Transactions on Signal Processing55,pp\. 4064–4077\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1),[§V](https://arxiv.org/html/2609.00078#S5.p3.2)\.
- \[23\]G\. Ayache and S\. E\. Rouayheb\(2021\)Private weighted random walk stochastic gradient descent\.IEEE Journal on Selected Areas in Information Theory2\(1\),pp\. 452–463\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1)\.
- \[24\]M\. Egger, S\. Lage, R\. Bitar, and et\. al\(2025\)Source anonymity for private random walk decentralized learning\.InIEEE Information Theory Workshop \(ITW\),pp\. 1–6\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1)\.
- \[25\]M\. Egger, G\. Ayache, R\. Bitar, and et\. al\(2024\)Self\-duplicating random walks for resilient decentralized learning on graphs\.InIEEE Global Communications Conference \(GLOBECOM\),pp\. 2960–2965\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1)\.
- \[26\]X\. Chen, P\. Parag, R\. Bhagat, and et\.al\(2026\)Self\-creating random walks for decentralized learning under pac\-man attacks\.arXiv preprint arXiv:2601\.07674\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1),[§VI\-A4](https://arxiv.org/html/2609.00078#S6.SS1.SSS4.p1.1)\.
- \[27\]A\. Khalesi and R\. Bitar\(2026\)Fundamental limits of decentralized self\-regulating random walks\.to be presented at the IEEE International Symposium on Information Theory\.Cited by:[§III\-C](https://arxiv.org/html/2609.00078#S3.SS3.p2.1)\.
- \[28\]M\. Even\(2023\)Stochastic gradient descent under markovian sampling schemes\.InProceedings of the 40th International Conference on Machine Learning,ICML’23\.Cited by:[§A\-B](https://arxiv.org/html/2609.00078#A1.SS2.p1.10),[§A\-B](https://arxiv.org/html/2609.00078#A1.SS2.p1.7),[§A\-B](https://arxiv.org/html/2609.00078#A1.SS2.p1.8),[§A\-B](https://arxiv.org/html/2609.00078#A1.SS2.p1.9),[§V](https://arxiv.org/html/2609.00078#S5.p6.1),[Assumption 4](https://arxiv.org/html/2609.00078#Thmassumption4)\.
- \[29\]Y\. Liu, M\. Ott, N\. Goyal, and et\. al\(2019\)RoBERTa: a robustly optimized bert pretraining approach\.External Links:[Link](http://arxiv.org/abs/1907.11692)Cited by:[§VI\-A1](https://arxiv.org/html/2609.00078#S6.SS1.SSS1.p1.1)\.
- \[30\]B\. Dolan and C\. Brockett\(2005\)Automatically constructing a corpus of sentential paraphrases\.InThird International Workshop on Paraphrasing \(IWP2005\),Cited by:[item i](https://arxiv.org/html/2609.00078#S6.I1.i1.p1.1)\.
- \[31\]A\. Wang, A\. Singh, J\. Michael, and et\. al\(2018\)GLUE: a multi\-task benchmark and analysis platform for natural language understanding\.InBlackboxNLP@EMNLP,Cited by:[item i](https://arxiv.org/html/2609.00078#S6.I1.i1.p1.1)\.
- \[32\]P\. Rajpurkar, J\. J\. Zhang, K\. Lopyrev, and et\.al\(2016\)SQuAD: 100,000\+ questions for machine comprehension of text\.InProceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,Cited by:[item i](https://arxiv.org/html/2609.00078#S6.I1.i1.p1.1)\.
- \[33\]A\. Williams, N\. Nangia, and S\. R\. Bowman\(2017\)A broad\-coverage challenge corpus for sentence understanding through inference\.InNorth American Chapter of the Association for Computational Linguistics,External Links:[Link](https://api.semanticscholar.org/CorpusID:3432876)Cited by:[item i](https://arxiv.org/html/2609.00078#S6.I1.i1.p1.1)\.
- \[34\]R\. Socher, A\. Perelygin, J\. Wu, and et\.al\(2013\)Recursive deep models for semantic compositionality over a sentiment treebank\.InProceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,Cited by:[item ii](https://arxiv.org/html/2609.00078#S6.I1.i2.p1.1)\.
- \[35\]X\. Chen, P\. Parag, R\. Bhagat, and et\. al\(2026\)Random walk learning and the pac\-man attack\.InIEEE International Symposium on Information Theory \(ISIT\),Cited by:[§VI\-A4](https://arxiv.org/html/2609.00078#S6.SS1.SSS4.p1.1)\.
- \[36\]S\. Ghiasvand, M\. Alizadeh, and R\. Pedarsani\(2025\)Decentralized low\-rank fine\-tuning of large language models\.Note:arXiv:2501\.15361Cited by:[Lemma 3](https://arxiv.org/html/2609.00078#Thmlemma3)\.

## Appendix AProof of Theorem[1](https://arxiv.org/html/2609.00078#Thmtheorem1)

The proof consists of three parts\. In the first part, we establish several useful lemmas\. In the second part, we decompose the critical termf⁡\(W\(t\+1\)\)=f⁡\(B\(t\+1\)​A\(t\+1\)\)f\(W^\{\(t\+1\)\}\)=f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\. In the third part, we apply a telescoping argument to obtain the desired result\.

### A\-AUseful lemmas

First of all, we provide the following useful lemmas\.

###### Lemma 1\.

The expected squared norms of∇Af~v​\(W\)\\nabla\_\{A\}\\tilde\{f\}\_\{v\}\(W\)and∇Bf~v​\(W\)\\nabla\_\{B\}\\tilde\{f\}\_\{v\}\(W\)are bounded:

𝔼⁡\[‖∇Af~v​\(W\)‖2\]⩽b2​c2,\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]\\leqslant b^\{2\}c^\{2\},\(12\)𝔼⁡\[‖∇Bf~v​\(W\)‖2\]⩽a2​c2\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]\\leqslant a^\{2\}c^\{2\}\.\(13\)

###### Proof\.

SinceW=B​AW=BA, the gradients off~v​\(W\)\\tilde\{f\}\_\{v\}\(W\)with respect toAAandBBcan be obtained by applying the chain rule\. Specially, we have:

∇Af~v\(W\)=BT∇f~v\(W\),\\displaystyle\\nabla\_\{A\}\\tilde\{f\}\_\{v\}\(W\)=B^\{T\}\\nabla\\tilde\{f\}\_\{v\}\(W\),∇Bf~v​\(W\)=∇f~v​\(W\)​AT\.\\displaystyle\\nabla\_\{B\}\\tilde\{f\}\_\{v\}\(W\)=\\nabla\\tilde\{f\}\_\{v\}\(W\)A^\{T\}\.\(14\)Taking norms on both sides of \([14](https://arxiv.org/html/2609.00078#A1.Ex9)\), and using the submultiplicative property in Assumption[1](https://arxiv.org/html/2609.00078#Thmassumption1)together with Assumption[5](https://arxiv.org/html/2609.00078#Thmassumption5), we obtain

‖∇Af~v​\(W\)‖⩽\\displaystyle\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\}\(W\)\\\|\\leqslant‖B‖​‖∇f~v​\(W\)‖⩽b​‖∇f~v​\(W\)‖,\\displaystyle\\\|B\\\|\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|\\leqslant b\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|,\(15\)‖∇Bf~v​\(W\)‖⩽\\displaystyle\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\}\(W\)\\\|\\leqslant‖A‖​‖∇f~v​\(W\)‖⩽a​‖∇f~v​\(W\)‖\.\\displaystyle\\\|A\\\|\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|\\leqslant a\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|\.\(16\)According to Assumption[3](https://arxiv.org/html/2609.00078#Thmassumption3), taking square and expectations on both sides of \([15](https://arxiv.org/html/2609.00078#A1.E15)\) and \([16](https://arxiv.org/html/2609.00078#A1.E16)\), we obtain:

𝔼⁡\[‖∇Af~v​\(W\)‖2\]⩽b2​c2,\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]\\leqslant b^\{2\}c^\{2\},𝔼⁡\[‖∇Bf~v​\(W\)‖2\]⩽a2​c2\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]\\leqslant a^\{2\}c^\{2\}\.∎

###### Lemma 2\.

The expected squared differences𝔼⁡\[‖A\(t\+1\)−A\(t\)‖2\]\\mathbb\{E\}\[\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}\],𝔼⁡\[‖B\(t\+1\)−B\(t\)‖2\]\\mathbb\{E\}\[\\\|B^\{\(t\+1\)\}\-B^\{\(t\)\}\\\|^\{2\}\], and𝔼⁡\[‖W\(t\+1\)−W\(t\)‖2\]\\mathbb\{E\}\[\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|^\{2\}\]are upper bounded as follows:

𝔼⁡\[‖A\(t\+1\)−A\(t\)‖2\]⩽η2​K​b2​c2,\\displaystyle\\mathbb\{E\}\\left\[\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}\\right\]\\leqslant\\eta^\{2\}Kb^\{2\}c^\{2\},\(17\)𝔼⁡\[‖B\(t\+1\)−B\(t\)‖2\]⩽η2​K​a2​c2,\\displaystyle\\mathbb\{E\}\\left\[\\\|B^\{\(t\+1\)\}\-B^\{\(t\)\}\\\|^\{2\}\\right\]\\leqslant\\eta^\{2\}Ka^\{2\}c^\{2\},\(18\)𝔼⁡\[‖W\(t\+1\)−W\(t\)‖2\]⩽3​K2​\(η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4\)\.\\displaystyle\\mathbb\{E\}\\left\[\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|^\{2\}\\right\]\\leqslant 3K^\{2\}\(\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\)\.\(19\)

###### Proof\.

According to \([7](https://arxiv.org/html/2609.00078#S4.E7)\) – \([10](https://arxiv.org/html/2609.00078#S4.E10)\), we have:

‖A\(t\+1\)−A\(t\)‖2=η2​‖∑k=0K−1∇Af~vt​\(W\(t,k\)\)‖2,\\displaystyle\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}=\\eta^\{2\}\\\|\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\},‖B\(t\+1\)−B\(t\)‖2=η2​‖∑k=0K−1∇Bf~vt​\(W\(t,k\)\)‖2\.\\displaystyle\\\|B^\{\(t\+1\)\}\-B^\{\(t\)\}\\\|^\{2\}=\\eta^\{2\}\\\|\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\.Taking expectations on both sides of above equalities and Cauchy–Schwarz inequality, and based on \([12](https://arxiv.org/html/2609.00078#A1.E12)\) and \([13](https://arxiv.org/html/2609.00078#A1.E13)\), we have \([17](https://arxiv.org/html/2609.00078#A1.E17)\) and \([18](https://arxiv.org/html/2609.00078#A1.E18)\)\.

Next, we calculateW\(t\+1\)−W\(t\)W^\{\(t\+1\)\}\-W^\{\(t\)\}:

W\(t\+1\)−W\(t\)=B\(t\+1\)​A\(t\+1\)−B\(t\)​A\(t\)\\displaystyle W^\{\(t\+1\)\}\-W^\{\(t\)\}=B^\{\(t\+1\)\}A^\{\(t\+1\)\}\-B^\{\(t\)\}A^\{\(t\)\}=\(B\(t\)−η​∑k=0K−1∇Bf~vt​\(W\(t,k\)\)\)​\(A\(t\)−η​∑k=0K−1∇Af~vt​\(W\(t,k\)\)\)−B\(t\)​A\(t\)\\displaystyle=\\left\(B^\{\(t\)\}\-\\eta\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\right\)\\left\(A^\{\(t\)\}\-\\eta\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\right\)\-B^\{\(t\)\}A^\{\(t\)\}=−η∑k=0K−1∇Af~vt\(W\(t\)\)B\(t\)−ηA\(t\)∑k=0K−1∇Bf~vt\(W\(t\)\)\\displaystyle=\-\\eta\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t\)\}\)B^\{\(t\)\}\-\\eta A^\{\(t\)\}\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t\)\}\)\+η2∑k1=0K−1∑k2=0K−1∇Af~vt\(W\(t,k1\)\)∇Bf~vt\(W\(t,k2\)\)\.\\displaystyle\+\\eta^\{2\}\\sum\_\{k\_\{1\}=0\}^\{K\-1\}\\sum\_\{k\_\{2\}=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{1\}\)\}\)\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{2\}\)\}\)\.Taking norms on both sides, by the triangle inequality, we obtain:

‖W\(t\+1\)−W\(t\)‖⩽\\displaystyle\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|\\leqslantη​‖∑k=0K−1∇Af~vt​\(W\(t,k\)\)​B\(t\)‖\+η​‖A\(t\)​∇B​∑k=0K−1f~vt​\(W\(t,k\)\)‖\\displaystyle\\eta\\\|\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)B^\{\(t\)\}\\\|\+\\eta\\\|A^\{\(t\)\}\\nabla\_\{B\}\\sum\_\{k=0\}^\{K\-1\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|\+\\displaystyle\+η2​‖∑k1=0K−1∑k2=0K−1∇Af~vt​\(W\(t,k1\)\)​∇Bf~vt​\(W\(t,k2\)\)‖\.\\displaystyle\\eta^\{2\}\\\|\\sum\_\{k\_\{1\}=0\}^\{K\-1\}\\sum\_\{k\_\{2\}=0\}^\{K\-1\}\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{1\}\)\}\)\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{2\}\)\}\)\\\|\.Applying the submultiplicative property and the triangle inequality, we obtain

‖W\(t\+1\)−W\(t\)‖⩽\\displaystyle\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|\\leqslantη​b​∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖\+η​a​∑k=0K−1‖∇Bf~vt​\(W\(t,k\)\)‖\\displaystyle\\eta b\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|\+\\eta a\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|\+\\displaystyle\+η2​\(∑k1=0K−1‖∇Af~vt​\(W\(t,k1\)\)‖\)​\(∑k2=0K−1‖∇Bf~vt​\(W\(t,k2\)\)‖\)\.\\displaystyle\\eta^\{2\}\\left\(\\sum\_\{k\_\{1\}=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{1\}\)\}\)\\\|\\right\)\\left\(\\sum\_\{k\_\{2\}=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{2\}\)\}\)\\\|\\right\)\.For simplicity of notation, we denote

XA=\\displaystyle X\_\{A\}=η​b​∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖,XB=η​a​∑k=0K−1‖∇Bf~vt​\(W\(t,k\)\)‖\\displaystyle\\eta b\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|,\\quad X\_\{B\}=\\eta a\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|XC=\\displaystyle X\_\{C\}=η2​\(∑k1=0K−1‖∇Af~vt​\(W\(t,k1\)\)‖\)​\(∑k2=0K−1‖∇Bf~vt​\(W\(t,k2\)\)‖\)\.\\displaystyle\\eta^\{2\}\\left\(\\sum\_\{k\_\{1\}=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{1\}\)\}\)\\\|\\right\)\\left\(\\sum\_\{k\_\{2\}=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\_\{2\}\)\}\)\\\|\\right\)\.By Cauchy–Schwarz inequality, it follows that

‖W\(t\+1\)−W\(t\)‖2⩽3​XA2\+3​XB2\+3​XC2\.\\displaystyle\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|^\{2\}\\leqslant 3X\_\{A\}^\{2\}\+3X\_\{B\}^\{2\}\+3X\_\{C\}^\{2\}\.ForXA2X\_\{A\}^\{2\}, again, by Cauchy–Schwarz inequality, we have:

XA2⩽η2​b2​\(∑k=0K−112\)​\(∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖2\)=η2​b2​K​\(∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖2\)\.\\displaystyle X\_\{A\}^\{2\}\\leqslant\\eta^\{2\}b^\{2\}\\left\(\\sum\_\{k=0\}^\{K\-1\}1^\{2\}\\right\)\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)=\\eta^\{2\}b^\{2\}K\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)\.Similar processes forXB2X\_\{B\}^\{2\}andXC2X\_\{C\}^\{2\}, we have the following inequality:

‖W\(t\+1\)−W\(t\)‖2⩽\\displaystyle\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|^\{2\}\\leqslant3​η2​b2​K​\(∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖2\)\+3​η2​a2​K​\(∑k=0K−1‖∇Bf~vt​\(W\(t,k\)\)‖2\)\\displaystyle 3\\eta^\{2\}b^\{2\}K\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)\+3\\eta^\{2\}a^\{2\}K\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)\+\\displaystyle\+3​η4​K2​\(∑k=0K−1‖∇Af~vt​\(W\(t,k\)\)‖2\)​\(∑k=0K−1‖∇Bf~vt​\(W\(t,k\)\)‖2\)\.\\displaystyle 3\\eta^\{4\}K^\{2\}\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{A\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)\\left\(\\sum\_\{k=0\}^\{K\-1\}\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\)\.Taking expectations on both sides of above equalities, based on \([12](https://arxiv.org/html/2609.00078#A1.E12)\) and \([13](https://arxiv.org/html/2609.00078#A1.E13)\), we obtain:

𝔼⁡\[‖W\(t\+1\)−W\(t\)‖2\]⩽3​K2​\(η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4\)\.\\displaystyle\\mathbb\{E\}\\left\[\\\|W^\{\(t\+1\)\}\-W^\{\(t\)\}\\\|^\{2\}\\right\]\\leqslant 3K^\{2\}\(\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\)\.∎

###### Lemma 3\(Lemma 4\.10 in\[[36](https://arxiv.org/html/2609.00078#bib.bib25)\]\)\.

Under Assumption[2](https://arxiv.org/html/2609.00078#Thmassumption2), each local fine\-tuning objectivefvf\_\{v\}isL​b2Lb^\{2\}\-smooth with respect toAAwhenBBis fixed, andL​a2La^\{2\}\-smooth with respect toBBwhenAAis fixed\.

###### Lemma 4\.

Letf⁡\(⋅\)f\(\\cdot\)be defined in \([5](https://arxiv.org/html/2609.00078#S4.E5)\)\. Then,ffisLL\-smooth\.

###### Proof\.

According to \([5](https://arxiv.org/html/2609.00078#S4.E5)\),

∇f​\(W\)−∇f​\(W′\)=𝔼v∼π​\[∇fv​\(W\)−∇fv​\(W′\)\]\.\\displaystyle\\nabla f\(W\)\-\\nabla f\(W^\{\\prime\}\)=\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\[\\nabla f\_\{v\}\(W\)\-\\nabla f\_\{v\}\(W^\{\\prime\}\)\\right\]\.By Jensen’s inequality applied to the convex norm function, we have:

‖∇f​\(W\)−∇f​\(W′\)‖=‖𝔼v∼π​\[∇fv​\(W\)−∇fv​\(W′\)\]‖⩽𝔼v∼π​‖∇fv​\(W\)−∇fv​\(W′\)‖\.\\displaystyle\\\|\\nabla f\(W\)\-\\nabla f\(W^\{\\prime\}\)\\\|=\\left\\\|\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\[\\nabla f\_\{v\}\(W\)\-\\nabla f\_\{v\}\(W^\{\\prime\}\)\\right\]\\right\\\|\\leqslant\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\\\|\\nabla f\_\{v\}\(W\)\-\\nabla f\_\{v\}\(W^\{\\prime\}\)\\right\\\|\.Based on Assumption[2](https://arxiv.org/html/2609.00078#Thmassumption2), it follows that

‖∇f​\(W\)−∇f​\(W′\)‖⩽𝔼v∼π​\[L​‖W−W′‖\]=L​‖W−W′‖\.\\displaystyle\\\|\\nabla f\(W\)\-\\nabla f\(W^\{\\prime\}\)\\\|\\leqslant\\mathbb\{E\}\_\{v\\sim\\pi\}\\left\[L\\\|W\-W^\{\\prime\}\\\|\\right\]=L\\\|W\-W^\{\\prime\}\\\|\.∎

###### Lemma 5\.

Letf⁡\(⋅\)f\(\\cdot\)be defined in \([5](https://arxiv.org/html/2609.00078#S4.E5)\)\. Then,ffisL​b2Lb^\{2\}\-smooth with respect toAAwhenBBis fixed, andL​a2La^\{2\}\-smooth with respect toBBwhenAAis fixed\.

###### Proof\.

The proof directly follows from Lemma[3](https://arxiv.org/html/2609.00078#Thmlemma3)and Lemma[4](https://arxiv.org/html/2609.00078#Thmlemma4)\. ∎

Letπ0\\pi\_\{0\}denote the initial distribution, and letπt=Pt​π0\\pi\_\{t\}=P^\{t\}\\pi\_\{0\}denote the distribution at time steptt\. Letπmin=minu∈𝒱⁡πu\\pi\_\{\\min\}=\\min\_\{u\\in\\mathcal\{V\}\}\\pi\_\{u\}\.

###### Lemma 6\.

Fort⩾0t\\geqslant 0and ifvt∼πtv\_\{t\}\\sim\\pi\_\{t\}fordTV​\(πt,π\)⩽πmin2d\_\{\\text\{TV\}\}\(\\pi\_\{t\},\\pi\)\\leqslant\\frac\{\\pi\_\{\\min\}\}\{2\}, we have

𝔼⁡\[‖∇f~vt​\(W\)‖2\]⩽3​σ2\+2​𝔼​\[‖∇f​\(W\)‖2\]\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\_\{t\}\}\(W\)\\\|^\{2\}\\right\]\\leqslant 3\\sigma^\{2\}\+2\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]

###### Proof\.

SincedTV​\(πt,π\)⩽πmin2d\_\{\\text\{TV\}\}\(\\pi\_\{t\},\\pi\)\\leqslant\\frac\{\\pi\_\{\\min\}\}\{2\}, then for anyv∈𝒱v\\in\\mathcal\{V\}, we have

Pr⁡\(vt=v\)⩽πv\+πv/2=3​πv2\.\\displaystyle\\Pr\(v\_\{t\}=v\)\\leqslant\\pi\_\{v\}\+\\pi\_\{v\}/2=\\frac\{3\\pi\_\{v\}\}\{2\}\.By the triangle inequality, Cauchy–Schwarz inequality, and Assumption[4](https://arxiv.org/html/2609.00078#Thmassumption4), it follows that

𝔼⁡\[‖∇f~vt​\(W\)‖2\]⩽\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\_\{t\}\}\(W\)\\\|^\{2\}\\right\]\\leqslant2​𝔼​\[‖∇f~vt​\(W\)−∇f​\(W\)‖2\]\+2​𝔼​\[‖∇f​\(W\)‖2\]\\displaystyle 2\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\_\{t\}\}\(W\)\-\\nabla f\(W\)\\\|^\{2\}\\right\]\+2\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]⩽\\displaystyle\\leqslant2​∑v∈𝒱Pr⁡\(vt=v\)​σ2\+2​𝔼​\[‖∇f​\(W\)‖2\]\\displaystyle 2\\sum\_\{v\\in\\mathcal\{V\}\}\\Pr\(v\_\{t\}=v\)\\sigma^\{2\}\+2\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]=\\displaystyle=3​σ2\+2​𝔼​\[‖∇f​\(W\)‖2\]\.\\displaystyle 3\\sigma^\{2\}\+2\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]\.∎

###### Lemma 7\.

The expected squared norms of∇f​\(W\)\\nabla f\(W\),∇Af​\(W\)\\nabla\_\{A\}f\(W\)and∇Bf​\(W\)\\nabla\_\{B\}f\(W\)are bounded by:

𝔼⁡\[‖∇f​\(W\)‖2\]⩽2​σ2\+2​c2,\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]\\leqslant 2\\sigma^\{2\}\+2c^\{2\},\(20\)𝔼⁡\[‖∇Af​\(W\)‖2\]⩽2​b2​\(σ2\+c2\),\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W\)\\\|^\{2\}\\right\]\\leqslant 2b^\{2\}\(\\sigma^\{2\}\+c^\{2\}\),\(21\)𝔼⁡\[‖∇Bf​\(W\)‖2\]⩽2​a2​\(σ2\+c2\)\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W\)\\\|^\{2\}\\right\]\\leqslant 2a^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\.\(22\)

###### Proof\.

By the triangle inequality and Cauchy–Schwarz inequality, we have

𝔼⁡\[‖∇f​\(W\)‖2\]⩽\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]\\leqslant2​𝔼​\[‖∇f~v​\(W\)−∇f​\(W\)‖2\]\+2​𝔼​\[‖∇f~v​\(W\)‖2\]\\displaystyle 2\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\-\\nabla f\(W\)\\\|^\{2\}\\right\]\+2\\mathbb\{E\}\\left\[\\\|\\nabla\\tilde\{f\}\_\{v\}\(W\)\\\|^\{2\}\\right\]According to Assumption[3](https://arxiv.org/html/2609.00078#Thmassumption3)and Assumption[4](https://arxiv.org/html/2609.00078#Thmassumption4), we have

𝔼⁡\[‖∇f​\(W\)‖2\]⩽2​σ2\+2​c2\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla f\(W\)\\\|^\{2\}\\right\]\\leqslant 2\\sigma^\{2\}\+2c^\{2\}\.
Note thatW=B​AW=BA, we have:

∇Af\(W\)=BT∇f\(W\),∇Bf\(W\)=∇f\(W\)AT\.\\displaystyle\\nabla\_\{A\}f\(W\)=B^\{T\}\\nabla f\(W\),\\,\\,\\nabla\_\{B\}f\(W\)=\\nabla f\(W\)A^\{T\}\.\(23\)Applying the submultiplicative property and taking expectations on \([23](https://arxiv.org/html/2609.00078#A1.E23)\), we obtain:

𝔼⁡\[‖∇Af​\(W\)‖2\]⩽2​b2​\(σ2\+c2\)\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W\)\\\|^\{2\}\\right\]\\leqslant 2b^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)𝔼⁡\[‖∇Bf​\(W\)‖2\]⩽2​a2​\(σ2\+c2\)\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W\)\\\|^\{2\}\\right\]\\leqslant 2a^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\.

### A\-BDecomposition of𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]

Sinceffis smooth, by the Descent Lemma666The descent lemma is a standard result forLL\-smooth differentiable functions\. IfffisLL\-smooth, then for anyx,yx,y,f⁡\(y\)⩽f⁡\(x\)\+⟨∇f​\(x\),y−x⟩\+L2​‖y−x‖2\.\\displaystyle f\(y\)\\leqslant f\(x\)\+\\langle\\nabla f\(x\),y\-x\\rangle\+\\frac\{L\}\{2\}\\\|y\-x\\\|^\{2\}\., we have:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\)\)\]\+𝔼⁡⟨∇Af​\(B\(t\+1\)​A\(t\)\),A\(t\+1\)−A\(t\)⟩\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\)\}\)\\right\]\+\\mathbb\{E\}\\left\\langle\\nabla\_\{A\}f\(B^\{\(t\+1\)\}A^\{\(t\)\}\),A^\{\(t\+1\)\}\-A^\{\(t\)\}\\right\\rangle\+\\displaystyle\+L​b22​𝔼​\[‖A\(t\+1\)−A\(t\)‖2\]\.\\displaystyle\\frac\{Lb^\{2\}\}\{2\}\\mathbb\{E\}\\left\[\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}\\right\]\.\(24\)In \([24](https://arxiv.org/html/2609.00078#A1.Ex42)\), the expectation𝔼\\mathbb\{E\}is taken over the target samplingπ\\piand the randomness from the position of the RW at timett, i\.e\.,vtv\_\{t\}\. Again, by the Descent Lemma, we further have:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\)​A\(t\)\)\]\+𝔼⁡⟨∇Bf​\(B\(t\)​A\(t\)\),B\(t\+1\)−B\(t\)⟩\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\)\}A^\{\(t\)\}\)\\right\]\+\\mathbb\{E\}\\left\\langle\\nabla\_\{B\}f\(B^\{\(t\)\}A^\{\(t\)\}\),B^\{\(t\+1\)\}\-B^\{\(t\)\}\\right\\rangle\+\\displaystyle\+L​a22​𝔼​\[‖B\(t\+1\)−B\(t\)‖2\]\.\\displaystyle\\frac\{La^\{2\}\}\{2\}\\mathbb\{E\}\\left\[\\\|B^\{\(t\+1\)\}\-B^\{\(t\)\}\\\|^\{2\}\\right\]\.\(25\)Combine \([24](https://arxiv.org/html/2609.00078#A1.Ex42)\) and \([25](https://arxiv.org/html/2609.00078#A1.Ex43)\), we obtain:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\)​A\(t\)\)\]\+𝔼⁡⟨∇Af​\(B\(t\+1\)​A\(t\)\),A\(t\+1\)−A\(t\)⟩\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\)\}A^\{\(t\)\}\)\\right\]\+\\mathbb\{E\}\\left\\langle\\nabla\_\{A\}f\(B^\{\(t\+1\)\}A^\{\(t\)\}\),A^\{\(t\+1\)\}\-A^\{\(t\)\}\\right\\rangle\+\\displaystyle\+𝔼⁡⟨∇Bf​\(B\(t\)​A\(t\)\),B\(t\+1\)−B\(t\)⟩\+L​b22​𝔼​\[‖A\(t\+1\)−A\(t\)‖2\]\\displaystyle\\mathbb\{E\}\\left\\langle\\nabla\_\{B\}f\(B^\{\(t\)\}A^\{\(t\)\}\),B^\{\(t\+1\)\}\-B^\{\(t\)\}\\right\\rangle\+\\frac\{Lb^\{2\}\}\{2\}\\mathbb\{E\}\\left\[\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}\\right\]\+\\displaystyle\+L​a22​𝔼​\[‖B\(t\+1\)−B\(t\)‖2\]\.\\displaystyle\\frac\{La^\{2\}\}\{2\}\\mathbb\{E\}\\left\[\\\|B^\{\(t\+1\)\}\-B^\{\(t\)\}\\\|^\{2\}\\right\]\.\(26\)By the Cauchy–Schwarz inequality followed by Young’s inequality, we have

𝔼⁡⟨∇Af​\(B\(t\+1\)​A\(t\)\),A\(t\+1\)−A\(t\)⟩⩽\\displaystyle\\mathbb\{E\}\\left\\langle\\nabla\_\{A\}f\(B^\{\(t\+1\)\}A^\{\(t\)\}\),A^\{\(t\+1\)\}\-A^\{\(t\)\}\\right\\rangle\\leqslant12​𝔼​\[‖∇Af​\(B\(t\+1\)​A\(t\)\)‖2\]\\displaystyle\\frac\{1\}\{2\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(B^\{\(t\+1\)\}A^\{\(t\)\}\)\\\|^\{2\}\\right\]\+\\displaystyle\+12​𝔼​\[‖A\(t\+1\)−A\(t\)‖2\]\.\\displaystyle\\frac\{1\}\{2\}\\mathbb\{E\}\\left\[\\\|A^\{\(t\+1\)\}\-A^\{\(t\)\}\\\|^\{2\}\\right\]\.From \([17](https://arxiv.org/html/2609.00078#A1.E17)\) in Lemma[2](https://arxiv.org/html/2609.00078#Thmlemma2)and \([21](https://arxiv.org/html/2609.00078#A1.E21)\) in Lemma[7](https://arxiv.org/html/2609.00078#Thmlemma7),

𝔼⁡⟨∇Af​\(B\(t\+1\)​A\(t\)\),A\(t\+1\)−A\(t\)⟩⩽b2​\(σ2\+c2\)\+η2​K2​b2​c22\.\\displaystyle\\mathbb\{E\}\\left\\langle\\nabla\_\{A\}f\(B^\{\(t\+1\)\}A^\{\(t\)\}\),A^\{\(t\+1\)\}\-A^\{\(t\)\}\\right\\rangle\\leqslant b^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\+\\eta^\{2\}K^\{2\}\\frac\{b^\{2\}c^\{2\}\}\{2\}\.\(27\)According to the update rule \([10](https://arxiv.org/html/2609.00078#S4.E10)\), we have

𝔼⁡⟨∇Bf​\(B\(t\)​A\(t\)\),B\(t\+1\)−B\(t\)⟩\\displaystyle\\mathbb\{E\}\\left\\langle\\nabla\_\{B\}f\(B^\{\(t\)\}A^\{\(t\)\}\),B^\{\(t\+1\)\}\-B^\{\(t\)\}\\right\\rangle=𝔼⟨∇Bf\(B\(t\)A\(t\)\),−η∑k=0K−1∇Bf~vt\(W\(t,k\)\)⟩\\displaystyle=\\mathbb\{E\}\\left\\langle\\nabla\_\{B\}f\(B^\{\(t\)\}A^\{\(t\)\}\),\-\\eta\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\right\\rangle=−η​𝔼​⟨∇Bf​\(B\(t\)​A\(t\)\),∑k=0K−1∇Bf~vt​\(W\(t,k\)\)⟩\\displaystyle=\-\\eta\\mathbb\{E\}\\left\\langle\\nabla\_\{B\}f\(B^\{\(t\)\}A^\{\(t\)\}\),\\sum\_\{k=0\}^\{K\-1\}\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\right\\rangle=∑k=0K−1𝔼⁡\[−η⁡⟨∇Bf​\(W\(t\)\),∇Bf~vt​\(W\(t,k\)\)⟩\]\.\\displaystyle=\\sum\_\{k=0\}^\{K\-1\}\\mathbb\{E\}\\left\[\-\\eta\\left\\langle\\nabla\_\{B\}f\(W^\{\(t\)\}\),\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\right\\rangle\\right\]\.\(28\)Letϵ<12\\epsilon<\\frac\{1\}\{2\},τ⩾τmix​\(πmin​ϵ\)\\tau\\geqslant\\tau\_\{\\mathrm\{mix\}\}\(\\pi\_\{\\min\}\\epsilon\), andt⩾τt\\geqslant\\tau, for anyk∈\{0,1,⋯,K−1\}k\\in\\left\\\{0,1,\\cdots,K\-1\\right\\\}, from the first equality in\[[28](https://arxiv.org/html/2609.00078#bib.bib24), Appendix C\.1\], we have:

𝔼⁡\[−η⁡⟨∇Bf~vt​\(W\(t,k\)\),∇Bf​\(W\(t\)\)⟩\]\\displaystyle\\mathbb\{E\}\\left\[\-\\eta\\left\\langle\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\),\\nabla\_\{B\}f\(W^\{\(t\)\}\)\\right\\rangle\\right\]=𝔼⁡\[−η⁡⟨∇Bf~vt​\(W\(t−τ\)\),∇Bf​\(W\(t−τ\)\)⟩\]\\displaystyle=\\mathbb\{E\}\\left\[\-\\eta\\left\\langle\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t\-\\tau\)\}\),\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\right\\rangle\\right\]\+𝔼⁡\[−η⁡⟨∇Bf~vt​\(W\(t,k\)\),∇Bf​\(W\(t\)\)−∇Bf​\(W\(t−τ\)\)⟩\]\\displaystyle\+\\mathbb\{E\}\\left\[\-\\eta\\left\\langle\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\),\\nabla\_\{B\}f\(W^\{\(t\)\}\)\-\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\right\\rangle\\right\]\+𝔼⁡\[−η⁡⟨∇Bf~​\(W\(t,k\)\)−∇Bf~​\(W\(t−τ\)\),∇Bf​\(W\(t−τ\)\)⟩\]\\displaystyle\+\\mathbb\{E\}\\left\[\-\\eta\\left\\langle\\nabla\_\{B\}\\tilde\{f\}\(W^\{\(t,k\)\}\)\-\\nabla\_\{B\}\\tilde\{f\}\(W^\{\(t\-\\tau\)\}\),\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\right\\rangle\\right\]≜E1\+E2\+E3\.\\displaystyle\\triangleq E\_\{1\}\+E\_\{2\}\+E\_\{3\}\.By the the third inequality in\[[28](https://arxiv.org/html/2609.00078#bib.bib24), Appendix C\.1\], we have:

E1⩽−η4​𝔼​\[‖∇Bf​\(W\(t−τ\)\)‖2\]\+η​ϵ2​σ2\.\\displaystyle E\_\{1\}\\leqslant\-\\frac\{\\eta\}\{4\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\+\\eta\\epsilon^\{2\}\\sigma^\{2\}\.\(29\)By utilizing Assumption[2](https://arxiv.org/html/2609.00078#Thmassumption2)and the forth inequality in\[[28](https://arxiv.org/html/2609.00078#bib.bib24), page 18\], we have:

E2⩽η2​L2​τ​𝔼​\[‖∇Bf~vt​\(W\(t,k\)\)‖2\]\+η2​L2​∑s=t−τt−1∑k′=0K−1𝔼⁡\[‖∇Bf~vs​\(W\(s,k′\)\)‖2\]\.\\displaystyle E\_\{2\}\\leqslant\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\}\}\(W^\{\(t,k\)\}\)\\\|^\{2\}\\right\]\+\\frac\{\\eta^\{2\}L\}\{2\}\\sum\_\{s=t\-\\tau\}^\{t\-1\}\\sum\_\{k^\{\\prime\}=0\}^\{K\-1\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{s\}\}\(W^\{\(s,k^\{\\prime\}\)\}\)\\\|^\{2\}\\right\]\.\(30\)Similarly, by utilizing Assumption[2](https://arxiv.org/html/2609.00078#Thmassumption2)and the sixth inequality in\[[28](https://arxiv.org/html/2609.00078#bib.bib24), page 18\], we have:

E3⩽\\displaystyle E\_\{3\}\\leqslantη2​L2​τ​𝔼​\[‖∇Bf​\(W\(t−τ\)\)‖2\]\+η2​L2​∑s=t−τt−2∑k′=0K−1𝔼⁡\[‖∇Bf~vs​\(W\(s,k\)\)‖2\]\\displaystyle\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\+\\frac\{\\eta^\{2\}L\}\{2\}\\sum\_\{s=t\-\\tau\}^\{t\-2\}\\sum\_\{k^\{\\prime\}=0\}^\{K\-1\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{s\}\}\(W^\{\(s,k\)\}\)\\\|^\{2\}\\right\]\+\\displaystyle\+η2​L2​∑k′=0k−1𝔼⁡\[‖∇Bf~vt−1​\(W\(t−1,k′\)\)‖2\]\\displaystyle\\frac\{\\eta^\{2\}L\}\{2\}\\sum\_\{k^\{\\prime\}=0\}^\{k\-1\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{t\-1\}\}\(W^\{\(t\-1,k^\{\\prime\}\)\}\)\\\|^\{2\}\\right\]⩽\\displaystyle\\leqslantη2​L2​τ​𝔼​\[‖∇Bf​\(W\(t−τ\)\)‖2\]\+η2​L2​∑s=t−τt−1∑k′=0K−1𝔼⁡\[‖∇Bf~vs​\(W\(s,k\)\)‖2\]\.\\displaystyle\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\+\\frac\{\\eta^\{2\}L\}\{2\}\\sum\_\{s=t\-\\tau\}^\{t\-1\}\\sum\_\{k^\{\\prime\}=0\}^\{K\-1\}\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}\\tilde\{f\}\_\{v\_\{s\}\}\(W^\{\(s,k\)\}\)\\\|^\{2\}\\right\]\.\(31\)Based on Lemma[2](https://arxiv.org/html/2609.00078#Thmlemma2), Lemma[7](https://arxiv.org/html/2609.00078#Thmlemma7), and \([27](https://arxiv.org/html/2609.00078#A1.E27)\) – \([31](https://arxiv.org/html/2609.00078#A1.Ex54)\), we have:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\)​A\(t\)\)\]\+K​η​ϵ2​σ2\+b2​\(σ2\+c2\)\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\)\}A^\{\(t\)\}\)\\right\]\+K\\eta\\epsilon^\{2\}\\sigma^\{2\}\+b^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\+\\displaystyle\+η2​K​\(\(2​K\+1\)​L2​τ​a2​c2\+c2​K​L2​\(a4\+b4\)\+K2​b2​c22\)\\displaystyle\\eta^\{2\}K\\left\(\\frac\{\(2K\+1\)L\}\{2\}\\tau a^\{2\}c^\{2\}\+\\frac\{c^\{2\}KL\}\{2\}\(a^\{4\}\+b^\{4\}\)\+K^\{2\}\\frac\{b^\{2\}c^\{2\}\}\{2\}\\right\)−\\displaystyle\-\(η4−η2​L2​τ\)​K​𝔼​\[‖∇Bf​\(W\(t−τ\)\)‖2\]\.\\displaystyle\\left\(\\frac\{\\eta\}\{4\}\-\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\right\)K\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\.\(32\)
In \([24](https://arxiv.org/html/2609.00078#A1.Ex42)\) and \([25](https://arxiv.org/html/2609.00078#A1.Ex43)\), we decomposef⁡\(B\(t\+1\)​A\(t\+1\)\)f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)using the intermediate termsf⁡\(B\(t\)​A\(t\+1\)\)f\(B^\{\(t\)\}A^\{\(t\+1\)\}\)andf⁡\(B\(t\)​A\(t\)\)f\(B^\{\(t\)\}A^\{\(t\)\}\)\. By a similar analysis, we obtain:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\)​A\(t\)\)\]\+K​η​ϵ2​σ2\+a2​\(σ2\+c2\)\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\)\}A^\{\(t\)\}\)\\right\]\+K\\eta\\epsilon^\{2\}\\sigma^\{2\}\+a^\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\+\\displaystyle\+η2​K​\(\(2​K\+1\)​L2​τ​b2​c2\+c2​K​L2​\(a4\+b4\)\+K2​a2​c22\)\\displaystyle\\eta^\{2\}K\\left\(\\frac\{\(2K\+1\)L\}\{2\}\\tau b^\{2\}c^\{2\}\+\\frac\{c^\{2\}KL\}\{2\}\(a^\{4\}\+b^\{4\}\)\+K^\{2\}\\frac\{a^\{2\}c^\{2\}\}\{2\}\\right\)−\\displaystyle\-\(η4−η2​L2​τ\)​K​𝔼​\[‖∇Af​\(W\(t−τ\)\)‖2\]\.\\displaystyle\\left\(\\frac\{\\eta\}\{4\}\-\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\right\)K\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\.\(33\)Summing over \([32](https://arxiv.org/html/2609.00078#A1.Ex56)\) and \([33](https://arxiv.org/html/2609.00078#A1.Ex58)\), we derive:

𝔼⁡\[f⁡\(B\(t\+1\)​A\(t\+1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\+1\)\}A^\{\(t\+1\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(B\(t\)​A\(t\)\)\]\+K​η​ϵ2​σ2\+a2\+b22​\(σ2\+c2\)\\displaystyle\\mathbb\{E\}\\left\[f\(B^\{\(t\)\}A^\{\(t\)\}\)\\right\]\+K\\eta\\epsilon^\{2\}\\sigma^\{2\}\+\\frac\{a^\{2\}\+b^\{2\}\}\{2\}\(\\sigma^\{2\}\+c^\{2\}\)\+\\displaystyle\+η2​K​\(\(2​K\+1\)​\(a2\+b2\)​L4​τ​c2\+c2​K​L2​\(a4\+b4\)\+K2​c2​\(a2\+b2\)4\)\\displaystyle\\eta^\{2\}K\\left\(\\frac\{\(2K\+1\)\(a^\{2\}\+b^\{2\}\)L\}\{4\}\\tau c^\{2\}\+\\frac\{c^\{2\}KL\}\{2\}\(a^\{4\}\+b^\{4\}\)\+K^\{2\}\\frac\{c^\{2\}\(a^\{2\}\+b^\{2\}\)\}\{4\}\\right\)−\\displaystyle\-\(η4−η2​L2​τ\)​K​\(𝔼⁡\[‖∇Af​\(W\(t−τ\)\)‖2\]\+𝔼⁡\[‖∇Bf​\(W\(t−τ\)\)‖2\]\)\.\\displaystyle\\left\(\\frac\{\\eta\}\{4\}\-\\frac\{\\eta^\{2\}L\}\{2\}\\tau\\right\)K\\left\(\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\+\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\-\\tau\)\}\)\\\|^\{2\}\\right\]\\right\)\.\(34\)

### A\-CTelescoping

LetT⩾τ2T\\geqslant\\tau^\{2\},η⩽14​L​T\\eta\\leqslant\\frac\{1\}\{4L\\sqrt\{T\}\}, we have

η8⩽η4−η2​L2​τ\.\\displaystyle\\frac\{\\eta\}\{8\}\\leqslant\\frac\{\\eta\}\{4\}\-\\frac\{\\eta^\{2\}L\}\{2\}\\tau\.Then, summing forτ⩽t<T\+τ\\tau\\leqslant t<T\+\\tau, by telescoping \([34](https://arxiv.org/html/2609.00078#A1.Ex60)\), we obtain:

1T​∑t=0T−1\(𝔼⁡\[‖∇Af​\(W\(t\)\)‖2\]\+𝔼⁡\[‖∇Bf​\(W\(t\)\)‖2\]\)\\displaystyle\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\left\(\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\+\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\\right\)⩽ϵ2​σ2\+η​Γ\+8​𝔼​\[f⁡\(W\(τ\)\)\]\+4​\(a2\+b2\)​\(σ2\+c2\)/Kη​T,\\displaystyle\\leqslant\\epsilon^\{2\}\\sigma^\{2\}\+\\eta\\Gamma\+\\frac\{8\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]\+4\(a^\{2\}\+b^\{2\}\)\(\\sigma^\{2\}\+c^\{2\}\)/K\}\{\\eta T\},\(35\)where

Γ=\\displaystyle\\Gamma=2​\(2​K\+1\)​\(a2\+b2\)​L​τ​c2\+4​c2​K​L​\(a4\+b4\)\+2​K2​c2​\(a2\+b2\)\.\\displaystyle 2\(2K\+1\)\(a^\{2\}\+b^\{2\}\)L\\tau c^\{2\}\+4c^\{2\}KL\(a^\{4\}\+b^\{4\}\)\+2K^\{2\}c^\{2\}\(a^\{2\}\+b^\{2\}\)\.Now, we upper bound𝔼⁡\[f⁡\(W\(τ\)\)\]\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]\. According to Lemma[4](https://arxiv.org/html/2609.00078#Thmlemma4),ffisLL\-smooth\. By the Descent Lemma, we have:

f⁡\(W\(τ\)\)−f⁡\(W\(τ−1\)\)⩽⟨∇f​\(W\(τ−1\)\),W\(τ\)−W\(τ−1\)⟩\+L2​‖W\(τ\)−W\(τ−1\)‖2\.\\displaystyle f\(W^\{\(\\tau\)\}\)\-f\(W^\{\(\\tau\-1\)\}\)\\leqslant\\langle\\nabla f\(W^\{\(\\tau\-1\)\}\),W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\rangle\+\\frac\{L\}\{2\}\\\|W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\\|^\{2\}\.By Cauchy–Schwarz inequality,

f⁡\(W\(τ\)\)−f⁡\(W\(τ−1\)\)⩽\(‖∇f​\(W\(τ−1\)\)‖\+L2​‖W\(τ\)−W\(τ−1\)‖\)​‖W\(τ\)−W\(τ−1\)‖,\\displaystyle f\(W^\{\(\\tau\)\}\)\-f\(W^\{\(\\tau\-1\)\}\)\\leqslant\\left\(\\\|\\nabla f\(W^\{\(\\tau\-1\)\}\)\\\|\+\\frac\{L\}\{2\}\\\|W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\\|\\right\)\\\|W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\\|,which implies

𝔼⁡\[f⁡\(W\(τ\)\)\]−𝔼⁡\[f⁡\(W\(τ−1\)\)\]⩽\(𝔼⁡\[‖∇f​\(W\(τ−1\)\)‖2\]\+L2​‖W\(τ\)−W\(τ−1\)‖\)​‖W\(τ\)−W\(τ−1\)‖\.\\displaystyle\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]\-\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\-1\)\}\)\\right\]\\leqslant\\left\(\\sqrt\{\\mathbb\{E\}\\left\[\\\|\\nabla f\(W^\{\(\\tau\-1\)\}\)\\\|^\{2\}\\right\]\}\+\\frac\{L\}\{2\}\\\|W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\\|\\right\)\\\|W^\{\(\\tau\)\}\-W^\{\(\\tau\-1\)\}\\\|\.Based on \([20](https://arxiv.org/html/2609.00078#A1.E20)\) in Lemma[7](https://arxiv.org/html/2609.00078#Thmlemma7)and \([19](https://arxiv.org/html/2609.00078#A1.E19)\) in Lemma[2](https://arxiv.org/html/2609.00078#Thmlemma2), we have:

𝔼⁡\[f⁡\(W\(τ\)\)\]−𝔼⁡\[f⁡\(W\(τ−1\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]\-\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\-1\)\}\)\\right\]\\leqslant3​L2​K2​\(η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4\)\\displaystyle 3\\frac\{L\}\{2\}K^\{2\}\(\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\)\+\\displaystyle\+3​2​σ2\+2​c2​K​η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4\.\\displaystyle 3\\sqrt\{2\\sigma^\{2\}\+2c^\{2\}\}K\\sqrt\{\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\}\.By applying the inequality above repeatedly, we obtain:

𝔼⁡\[f⁡\(W\(τ\)\)\]⩽\\displaystyle\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]\\leqslant𝔼⁡\[f⁡\(W\(0\)\)\]\+3​τ​L2​K2​\(η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4\)\\displaystyle\\mathbb\{E\}\\left\[f\(W^\{\(0\)\}\)\\right\]\+3\\tau\\frac\{L\}\{2\}K^\{2\}\(\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\)\+\\displaystyle\+3​τ​2​σ2\+2​c2​K​η2​b4​c2\+η2​a4​c2\+K2​η4​a2​b2​c4,\\displaystyle 3\\tau\\sqrt\{2\\sigma^\{2\}\+2c^\{2\}\}K\\sqrt\{\\eta^\{2\}b^\{4\}c^\{2\}\+\\eta^\{2\}a^\{4\}c^\{2\}\+K^\{2\}\\eta^\{4\}a^\{2\}b^\{2\}c^\{4\}\},which implies𝔼⁡\[f⁡\(W\(τ\)\)\]\\mathbb\{E\}\\left\[f\(W^\{\(\\tau\)\}\)\\right\]is bounded\.

Finally, letϵ<12\\epsilon<\\frac\{1\}\{2\},τ⩾τmix​\(πmin​ϵ\)\\tau\\geqslant\\tau\_\{\\mathrm\{mix\}\}\(\\pi\_\{\\min\}\\epsilon\),T⩾τ2T\\geqslant\\tau^\{2\},η⩽14​L​T\\eta\\leqslant\\frac\{1\}\{4L\\sqrt\{T\}\}, we obtain:

1T​∑t=1T\(𝔼⁡\[‖∇Af​\(W\(t\)\)‖2\]\+𝔼⁡\[‖∇Bf​\(W\(t\)\)‖2\]\)⩽𝒪~​\(ϵ2\+L​τT\+L​τT\)\.\\displaystyle\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\left\(\\mathbb\{E\}\\left\[\\\|\\nabla\_\{A\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\+\\mathbb\{E\}\\left\[\\\|\\nabla\_\{B\}f\(W^\{\(t\)\}\)\\\|^\{2\}\\right\]\\right\)\\leqslant\\tilde\{\\mathcal\{O\}\}\\left\(\\epsilon^\{2\}\+\\frac\{L\\tau\}\{\\sqrt\{T\}\}\+\\frac\{L\\tau\}\{T\}\\right\)\.∎