acceptodds
Under review as a conference paper at ICLR 2027

Distributed Learning with Selective State Space Models: Architecture-Aware Convergence Analysis

Abstract

Modern state space models (SSMs), such as Mamba2, provide a compelling alternative to transformers by combining linear-time sequence modeling with recurrent state-space dynamics. However, the behavior of SSMs in distributed learning settings remains poorly understood. In particular, the existing standard federated learning methods are largely architecture-agnostic, and do not account for the stability, selectivity, and state-space parameterization that characterize modern selective SSMs. To address this, we derive architecture-aware gradient and smoothness bounds for single- and multi-layer selective SSMs, and convergence bounds for FedAvg and FedProx, characterizing how recurrent stability, input-dependent discretization, and state projection norms affect federated optimization. We then numerically validate the single-layer bounds on sequences generated by a teacher SSM, using a learner that follows the analyzed recurrence. We use this analysis to formulate expectations about the effects of local training and client heterogeneity, and examine these expectations by comparing nine federated learning algorithms on Mamba2 language modeling across six text domains. These experiments illustrate how SSM-specific bounds can provide a basis for interpreting the behavior of practical federated learning algorithms.

Primary area:
optimization
Keywords:
State Space Model, SSM, Selective State Space Models, Federated Learning, Distributed Learning, Distributed Optimization, Convergence Analysis, Upper Bounds, Gradient Bounds, Smoothness Bounds, Optimization, Deep Learning, AI, Mamba2, Recurrent Stabilitym

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_8ApXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies federated training of selective SSMs. It derives architecture-aware gradient and smoothness bounds, and then uses them to obtain convergence guarantees for FedAvg and FedProx. The theory is further validated with synthetic experiments and practical Mamba2 experiments.

Critical strengths
  1. Architecture-aware analysis. Instead of assuming bounded gradients, the paper derives the gradient and smoothness bounds directly from the selective SSM structure, which makes the dependence on recurrent stability and model parameters explicit.
  2. Meaningful connection to federated optimization. The paper further incorporates these SSM-specific quantities into the convergence analysis of FedAvg and FedProx, providing insight into how recurrent stability, local updates, and client heterogeneity affect federated training.
Critical weaknesses
  1. Limited to Full Client Participation. The analysis assumes that all clients participate in every communication round and does not study partial participation. As partial client participation is common in federated learning, this limits the practical applicability of the theoretical results.
  2. Strong stability assumption. From an FL perspective, assuming that all local iterates remain in a stable parameter region seems fairly strong, especially with heterogeneous data and multiple local steps. This concern is even stronger in the multi-layer setting, where the stability and boundedness conditions must hold simultaneously across all layers throughout training. This condition is enforced by projection in the synthetic experiments, but it is unclear whether it holds in the practical Mamba2 setting. I am not an expert in selective state space models, so further clarification on this assumption would be helpful.
  3. Limited characterization of client heterogeneity. Sequence-level TV may saturate under strong heterogeneity and therefore provide limited resolution between different non-IID regimes. Also, the heterogeneity term disappears when E=1E=1. Although this follows from the full-participation setting, it is less representative of practical FL with partial participation, where heterogeneity can still matter through client sampling. The authors should clarify this limitation.
Questions for authors
  1. See weakness.
  2. Could the authors extend the analysis to SCAFFOLD and provide a direct comparison among the convergence bounds of FedAvg, FedProx, and SCAFFOLD for selective SSM training? It would be particularly interesting to understand how the architecture-specific factors identified in this paper, such as recurrent stability, parameter envelopes, and client drift, affect the relative tightness of the three bounds.
  3. The synthetic experiments study the effect of ρ\rho extensively, but the practical Mamba2 experiments do not appear to report the realized layerwise stability factors. Could the authors measure these quantities during Mamba2 training and examine whether the theoretical dependence on recurrent stability is also observed in practice?
  4. I am not an expert in selective state space models, so I would defer to the opinions of other reviewers.
  5. I am open to raising my score if the authors adequately address my concerns in the rebuttal.
9 comments

Response (1/4)

We thank the reviewer for the insightful feedback. Below, we address the raised concerns and questions.

Full client participation and limited client heterogeneity analysis. The main objective of this work is to establish a theoretical foundation for architecture-aware distributed optimization of selective SSMs. Full client participation is a well-defined federated learning setting that allows us to isolate the effects of recurrent stability, parameter envelopes, and local client drift. Given this setting and the stated assumptions, we derive sequence-length-independent gradient bounds and local smoothness estimates for single-layer and multi-layer selective SSMs, and establish how recurrent stability and parameter envelopes enter FedAvg and FedProx convergence guarantees, including the trade-off between proximal radius contraction and the additional smoothness cost.

We agree that partial participation and a more detailed characterization of heterogeneity are important research directions. A comprehensive analysis would involve accounting for client-sampling variability and characterizing how these quantities interact with the architecture-specific sensitivities and local-update dynamics of selective SSMs. This question already substantially expands the theoretical scope and could form the basis of a dedicated follow-up study, however it is beyond the scope of a work meant to establish foundations for such analysis. Nevertheless, we agree that these limitations and their implications should be made explicit. We therefore provide an illustrative discussion below.

Consider partial participation with arbitrary client weights pk≥0p_k \geq 0 (∑kpk=1\sum_k p_k =1) and a single local SGD step (E=1E=1). At each round rr, let Cr\mathcal C_r be a multiset of m=∣Cr∣m=|\mathcal C_r| independent client draws with replacement, where each draw selects client kk with probability pkp_k (and each client draw uses an independent mini-batch). Define D_r:=\sum_{k=1}^{K}p_k \left\\|\nabla \mathcal L_k(W^r)-\nabla f(W^r)\right\\|_F^2 and g^r:=1m∑k∈Crgk,Ξ(Wr)\widehat g_r:=\frac{1}{m}\sum_{k\in\mathcal C_r}g_{k,\Xi}(W^r). Let Er\mathbb E_r denote expectation conditional on the training history before round-rr sampling. Under the stated assumptions, the fact that Er[g^r]=∇f(Wr)\mathbb E_r[\widehat g_r]=\nabla f(W^r), and by Lemmas B.3 and B.4, it follows that: \mathbb E_r \left\\|\widehat g_r - \nabla f(W^r)\right\\|_F^2 \le \underbrace{\frac{G_{\mathrm{SSM},R}^{2}}{m\Xi}}_{\text{within-client noise}} + \underbrace{\frac{D_r}{m}}_{\text{client-selection noise}} \le \frac{G_{\mathrm{SSM},R}^{2}}{m}\left(\frac1\Xi+4 \mathcal H_{\mathrm{TV}}\right).

For E=1E=1 and η≤1/LSSM,R\eta\le 1/L_{\mathrm{SSM},R}, this gives 1T∑r=0T−1E∣∇f(Wr)∣F2≤2(f(W0)−f∗)ηT+ηLSSM,RGSSM,R2m(1Ξ+4HTV)\frac1T\sum_{r=0}^{T-1}\mathbb E\\|\nabla f(W^r)\\|_F^2\le\frac{2(f(W^0)-f^*)}{\eta T}+\frac{\eta L_{\mathrm{SSM},R}G_{\mathrm{SSM},R}^2}{m}\left(\frac1\Xi+4\mathcal H_{\mathrm{TV}}\right). Thus, as the reviewer pointed out, under client sampling heterogeneity enters even at E=1E=1 through the client-selection term, whereas it vanishes at E=1E=1 under full participation. Extending this to multiple local updates, and refining the worst-case heterogeneity bound with client-dependent gradient sensitivities and stability margins, is left for future work.

Regarding HTV\mathcal H_{\mathrm{TV}}, we agree that sequence-level total variation can saturate. We note this limitation in Section 5 and quantify it in our synthetic experiments (Appendix H.1, Figure 8b): the sequence-level squared-TV aggregate is 0.560.56 at K=4K=4 and is unchanged by the partition, whereas a token-level analogue varies by two orders of magnitude. A token-level or moment-based dissimilarity would give finer resolution but requires a separate bound. We will include the partial client participation discussion along with the limitation of the existing analysis as a new section in the Appendix of the revised manuscript.

Response (2/4)

Stability assumption. In standard Mamba2, the transition parameters and discretization steps are parameterized as A=−exp⁡(a)<0A=-\exp(a)<0 and Δt=Softplus(ut)>0\Delta_t=\mathrm{Softplus}(u_t)>0, respectively. As such, as long as aa and utu_t remain uniformly bounded over the considered training neighborhoods (i.e. do not diverge to −∞-\infty), we can take their infima and choose: γ=exp⁡(inf⁡a)>0\gamma = \exp(\inf a) > 0 and δ=Softplus(inf⁡ut)>0\delta = \mathrm{Softplus}(\inf u_t) > 0 resulting in Aˉt≤exp⁡(−γδ)=ρ<1\bar A_t\le \exp(-\gamma\delta)=\rho<1. For an appropriate choice of RR, the bounded neighborhood together with bounded layer inputs ensure such finite lower bounds. The same reasoning applies separately to every layer, allowing layer-specific margins.

Containment of the local iterates does not depend on data heterogeneity. By Theorem 4.4 and Lemma B.2, every per-sequence gradient in the neighborhood has norm at most GSSM,RG_{\mathrm{SSM},R}, so EE local SGD steps displace a client by at most ηE,GSSM,R\eta E\\,G_{\mathrm{SSM},R}, and containment in NR(Wr)\mathcal N_R(W^r) holds whenever ηE,GSSM,R≤R\eta E\\,G_{\mathrm{SSM},R}\le R. Under Mamba2's parameterization every finite parameter value gives Aˉt∈(0,1)\bar A_t\in(0,1), so local updates cannot leave the stable region. The assumption therefore reduces to the boundedness discussed above.

In the synthetic experiments, projection imposes a specific stability upper bound, such as Aˉt≤0.7\bar A_t \le 0.7, enabling controlled comparisons across different stability regimes. This is stronger than requiring that some ρ<1\rho<1 exists: projection lets us select the stability ceiling in advance instead of obtaining it from the parameter and input bounds. The additional Mamba2 results reported below show that a single bound ρ<1\rho < 1 holds in practice during federated training, supporting the practicality of this assumption.

Response (3/4)

SCAFFOLD analysis. Our architecture-specific gradient and smoothness bounds provide the results needed to analyze SGD-based SCAFFOLD. The additional step is to track the evolution of its control variates along with the optimization error. Below we outline this extension, and will include the full rigorous analysis in the revised manuscript.

The SCAFFOLD local update is Wkr,e+1=Wkr,e−η(gk(Wkr,e;ξkr,e)+cr−ckr)W_{k}^{r,e+1} = W_{k}^{r,e} - \eta\left(g_k(W_{k}^{r,e};\xi_{k}^{r,e}) + c^r - c_k^r\right) where cr=∑kpkckrc^r=\sum_kp_kc_k^r, and ckrc_k^r estimates the gradient of the local objective (gkg_k denotes the mini-batch gradient of Assumption 4.6). All assumptions, common parameter envelopes, and stable-neighborhood containment conditions of Theorem B.5 hold. In particular, the corrected local iterates, including their endpoints, lie in NR(Wr)⊆Sγ,δ\mathcal N_R(W^r)\subseteq\mathcal S_{\gamma,\delta}. This holds whenever 3ηE,GSSM,R≤R3\eta E\\,G_{\mathrm{SSM},R}\le R, since the control variates are averages of gradients bounded by GSSM,RG_{\mathrm{SSM},R}. In this analysis, we use L:=LSSM,RL := L_{\mathrm{SSM},R}, G:=GSSM,RG := G_{\mathrm{SSM},R}, σ2:=G2Ξ\sigma^2:=\frac{G^2}{\Xi}, and q:=∑kpk2q:=\sum_kp_k^2.

We use the standard control-variate update, ckr+1=ckr−cr+Wr−Wkr,EηE=1E∑e=0E−1gk(Wkr,e;ξkr,e)c_k^{r+1} = c_k^r-c^r+\frac{W^r-W_k^{r,E}}{\eta E} = \frac{1}{E}\sum_{e=0}^{E-1}g_k(W_k^{r,e};\xi_k^{r,e}), the aggregation rule Wr+1=∑kpkWkr,EW^{r+1}=\sum_kp_kW_k^{r,E} and cr+1=∑kpkckr+1c^{r+1}=\sum_kp_kc_k^{r+1}. We further define C_r := \sum_kp_k\\,\mathbb{E} \left\\| (c_k^r-c^r) - \bigl(\nabla\mathcal{L}_k(W^r)-\nabla f(W^r)\bigr)\right\\|_F^2.

The main new step of the proof is using the LL-smoothness to bound local drift in terms of CrC_r, the global gradient norm, and σ2\sigma^2. By expanding the local displacement and applying smoothness and the variance bounds from the paper, for ηEL≤1/8\eta EL \leq 1/8, it follows that 1E∑e=0E−1∑kpkE∣Wkr,e−Wr∣F2≤2η2E(E−1)(E∣∇f(Wr)∣F2+Cr)+2η2(E−1)σ2\frac{1}{E}\sum_{e=0}^{E-1}\sum_kp_k\mathbb{E}\\|W_k^{r,e}-W^r\\|_F^2 \leq 2\eta^2E(E-1) \left(\mathbb{E}\\|\nabla f(W^r)\\|_F^2+C_r\right)+2\eta^2(E-1)\sigma^2. Then, the control-variate update, together with this result and the cancellation of the corrections in the server aggregate, yields Cr+1≤10η2E2L2Cr+22η2E2L2E∣∇f(Wr)∣F2+4σ2EC_{r+1} \leq 10\eta^2E^2L^2C_r + 22\eta^2E^2L^2\mathbb{E}\\|\nabla f(W^r)\\|_F^2 + \frac{4\sigma^2}{E}. By the smoothness of ff and conditional unbiasedness, it follows that E[f(Wr+1)]≤E[f(Wr)]−ηE2E∣∇f(Wr)∣F2+ηL22∑e=0E−1∑kpkE∣Wkr,e−Wr∣F2+η2ELqσ2\mathbb{E}[f(W^{r+1})] \leq \mathbb{E}[f(W^r)] -\frac{\eta E}{2}\mathbb{E}\\|\nabla f(W^r)\\|_F^2 +\frac{\eta L^2}{2} \sum_{e=0}^{E-1}\sum_kp_k \mathbb{E}\\|W_k^{r,e}-W^r\\|_F^2 +\eta^2ELq\sigma^2.

Substituting the local drift bound into the descent inequality and adding the control-error recursion scaled by an appropriate constant, under ηEL≤1/8\eta EL\leq 1/8, it follows that: E[f(Wr+1)]+2η3L2E2(E−1)Cr+1≤E[f(Wr)]+2η3L2E2(E−1)Cr−ηE4E∣∇f(Wr)∣F2+η2ELqσ2+9η3L2E(E−1)σ2\mathbb{E}[f(W^{r+1})]+2\eta^3L^2E^2(E-1)C_{r+1}\leq \mathbb{E}[f(W^r)]+2\eta^3L^2E^2(E-1)C_r-\frac{\eta E}{4}\mathbb{E}\\|\nabla f(W^r)\\|_F^2+\eta^2ELq\sigma^2+9\eta^3L^2E(E-1)\sigma^2. Summing over r=0,…,T−1r=0,\ldots,T-1, telescoping the terms, using E[f(WT)]≥f∗\mathbb{E}[f(W^T)]\geq f^*, CT≥0C_T \geq 0, and dividing by ηET/4\eta ET/4, we get: 1T∑r=0T−1E∣∇f(Wr)∣F2≤4(f(W0)−f∗)ηET+4ηLqσ2+36η2L2(E−1)σ2+8η2L2E(E−1)C0T\frac{1}{T}\sum_{r=0}^{T-1} \mathbb{E}\\|\nabla f(W^r)\\|_F^2 \leq \frac{4\bigl(f(W^0)-f^*\bigr)}{\eta ET} +4\eta Lq\sigma^2+36\eta^2L^2(E-1)\sigma^2 +\frac{8\eta^2L^2E(E-1)C_0}{T}. For zero initial controls, Lemma B.4 gives C0≤4G2HTVC_0\leq 4G^2 \mathcal H_{\mathrm{TV}}, so the heterogeneity contribution enters through an initialization term that decays as 1/T1/T, while the architecture-specific dependence remains through LL and σ2=G2/Ξ\sigma^2=G^2/\Xi.

Below we compare FedAvg, FedProx, and SCAFFOLD, where Lμ:=LSSM,Rμ+μL_\mu:=L_{\mathrm{SSM},R_\mu}+\mu and Gμ:=GSSM,RμG_\mu:=G_{\mathrm{SSM},R_\mu} are evaluated on the no-larger neighborhood NRμ(Wr)\mathcal N_{R_\mu}(W^r):

MethodLocal-noise drift termHeterogeneity term
FedAvg6η2L2(E−1)G2/Ξ6\eta^2L^2(E-1)G^2/\Xi48η2L2E(E−1)G2HTV48\eta^2L^2E(E-1)G^2\mathcal H_{\mathrm{TV}}
FedProx3η2Lμ2(E−1)Gμ2/Ξ3\eta^2L_\mu^2(E-1)G_\mu^2/\Xi24η2Lμ2E(E−1)Gμ2HTV24\eta^2L_\mu^2E(E-1)G_\mu^2\mathcal H_{\mathrm{TV}}
SCAFFOLD36η2L2(E−1)G2/Ξ36\eta^2L^2(E-1)G^2/\Xi32η2L2E(E−1)G2HTV/T32\eta^2L^2E(E-1)G^2\mathcal H_{\mathrm{TV}}/T

At equal η\eta, LL, and GG, and for E≥2E\ge2, the SCAFFOLD bound is smaller than the FedAvg bound exactly when E,Ξ,HTV>30/(48−32/T)E\\,\Xi\\,\mathcal H_{\mathrm{TV}}>30/(48-32/T), which is approximately 5/85/8 for large TT, i.e. when heterogeneity dominates local sampling noise. The remaining two terms of the FedAvg and SCAFFOLD bounds coincide. For nearly IID data it is larger, and SCAFFOLD also requires the stricter step-size condition ηEL≤1/8\eta EL\le1/8. This is consistent with the SCAFFOLD results in Table 2. The architecture-specific factors enter both terms through L2G2=O(MR6/(1−ρ)12)L^2G^2=\mathcal O(M_R^6/(1-\rho)^{12}), so they do not change which bound is smaller but amplify the gap as ρ→1\rho\to1. FedProx is the only one of the three that reduces the architecture-specific constants themselves, through the tighter envelopes on NRμ(Wr)\mathcal N_{R_\mu}(W^r), at the cost of μ\mu in LμL_\mu.

Reviewer_e26SOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the convergence behavior of selective state space models (SSMs) in federated learning. The authors derive architecture-aware gradient and smoothness bounds and incorporate them into existing convergence frameworks for FedAvg and FedProx. The theoretical results characterize the influence of SSM-specific parameters on federated optimization. Experiments on synthetic datasets and Mamba2 language models are conducted to evaluate the theoretical findings.

Critical strengths
  1. The paper studies an interesting problem at the intersection of selective SSMs and federated learning. Understanding how model architecture affects distributed optimization could be valuable.
  2. The authors derive explicit gradient and smoothness bounds based on SSM-specific properties, providing an alternative perspective to conventional architecture-agnostic convergence analyses.
Critical weaknesses
  1. Limited theoretical novelty and loose bounds. The convergence analysis largely builds upon existing federated optimization frameworks by incorporating SSM-specific constants. While this is a reasonable approach, the additional theoretical insights appear somewhat limited. Moreover, the derived bounds are considerably loose, as also observed in the experiments. This raises concerns about their practical usefulness in understanding or guiding federated optimization.
  2. Gap between theory and experiments. Although the authors provide a multi-layer extension in the appendix, the theoretical analysis relies on simplified SSM formulations and SGD-based optimization, whereas the practical experiments employ deeper Mamba2 models trained with AdamW. It remains unclear to what extent the theoretical results can explain the behavior observed in these practical settings.
Questions for authors
  1. Could the authors further clarify the main theoretical contributions beyond applying existing federated convergence frameworks with architecture-specific constants? In particular, what new insights or guarantees are obtained from the proposed analysis?
  2. Given that the derived bounds are relatively conservative, could the authors elaborate on how these bounds can provide meaningful guidance for practical federated optimization?
  3. Could the authors provide additional evidence supporting the connection between the theoretical analysis and the experiments with deep Mamba2 models? It would also be helpful to clarify whether the stability assumptions are satisfied during practical training.
8 comments

Response (1/4): Question 1.

We thank the reviewer for the feedback and for recognizing the value of understanding how selective SSM architectures affect distributed optimization. We answer in three parts: where an existing framework is used, which guarantees are new, and which insights the analysis provides that a generic bound cannot.

Only the final step of the FedAvg proofs uses existing result (Theorem B.5; Corollary C.8 for multiple layers). There, three quantities are substituted into the bound of [6]: the smoothness constant LL, the gradient variance σ2\sigma^2, and the client disagreement Γ2\Gamma^2. Generic frameworks assume that these constants exist. For a selective SSM this is not evident: gradients pass through SS input-dependent transitions, WΔW_\Delta enters both Aˉt\bar A_t and Bˉt\bar B_t, and the constants depend on the parameter norms, so they can hold only locally. Proving that they exist, with explicit values that do not grow with the sequence length, is the main body of our analysis (Appendices A, B.1, and C). Deriving the model-specific estimates required by a general theorem is common in architecture-specific theory [1,2], and to our knowledge this is the first federated convergence analysis of selective SSMs in which these quantities are derived from the architecture. The FedProx results (Theorem B.6, Corollary C.9) use no template and are proved directly.

New guarantees (under the stated stability, neighborhood, and regularity assumptions) are summarized as follows:

  • Sequence-length-independent gradient bound (Theorems 4.4, C.3): a closed-form bound GSSM(W)\mathcal G_{\mathrm{SSM}}(W) on the per-sequence gradient norm of single- and QQ-layer selective SSMs, valid for every sequence length SS.
  • Regularity that is proven rather than assumed (Lemmas 4.7, B.2-B.4, C.4-C.7): local smoothness, gradient variance, and client disagreement hold on an RR-neighborhood with explicit constants, and the gradient bound itself is Lipschitz across that neighborhood (Lemma B.1).
  • Fully explicit convergence rates for FedAvg and FedProx (Theorems B.5, B.6; Corollaries 4.8, C.8, C.9, D.1): every model-dependent constant can be evaluated before training from the initialization, the radius RR, and the stability margin (Appendix G.3).

New insights. In a generic bound, LL, σ2\sigma^2, and Γ2\Gamma^2 are unrelated constants. We show that for selective SSMs they are governed by the same two quantities, the parameter envelope MR=(1+MB)(1+MC)(1+MΔ)(1+MΔ+MA)M_R=(1+M_B)(1+M_C)(1+M_\Delta)(1+M_\Delta+M_A), in which the four parameter blocks enter separately, and the stability margin 1−ρ1-\rho: GSSM,R=O(MR/(1−ρ)2)G_{\mathrm{SSM},R}=\mathcal O(M_R/(1-\rho)^2), LSSM,R=O(MR2/(1−ρ)4)L_{\mathrm{SSM},R}=\mathcal O(M_R^2/(1-\rho)^4), σ2=GSSM,R2/Ξ\sigma^2=G_{\mathrm{SSM},R}^2/\Xi, and Γ2≤4GSSM,R2HTV\Gamma^2\le 4G_{\mathrm{SSM},R}^2\mathcal H_{\mathrm{TV}}. This coupling has consequences that a generic bound cannot express:

  • Memory, not sequence length, sets the difficulty. The bounds are independent of SS but grow as ρ→1\rho\to1, i.e. as the model retains past states for longer.
  • Local steps cost more for long-memory models. The baseline stochastic term scales as ηMR4/(1−ρ)8\eta M_R^4/(1-\rho)^8, whereas the multi-step drift terms (E>1E>1) scale as η2MR6/(1−ρ)12\eta^2M_R^6/(1-\rho)^{12} (Corollary 4.8).
  • The architecture amplifies heterogeneity. The same data mismatch HTV\mathcal H_{\mathrm{TV}} costs more when parameter norms are larger or ρ\rho is closer to one. Its contribution vanishes at E=1E=1 and is not reduced by a larger batch size when E>1E>1.
  • FedProx changes the constants themselves. The proximal term confines clients to a radius Rμ=min⁡R,GSSM,Rμ[1−(1−ημ)E]≤RR_\mu=\min\\{R,\frac{G_{\mathrm{SSM},R}}{\mu}[1-(1-\eta\mu)^E]\\}\le R, which tightens the envelopes to MXμ=MX−R+RμM_X^\mu=M_X-R+R_\mu and reduces the SSM-dependent factors, at the cost of adding μ\mu to the smoothness (Theorem B.6, Corollary D.1). An analysis with a fixed LL cannot show this trade-off.
  • Depth has three regimes. With layerwise input-output sensitivity κ\kappa, the gradient / smoothness bounds are O(1)\mathcal O(1) for κ<1\kappa<1, O(Q)\mathcal O(\sqrt Q) / O(Q2)\mathcal O(Q^2) for κ=1\kappa=1, and O(κQ)\mathcal O(\kappa^Q) / O(κ2Q)\mathcal O(\kappa^{2Q}) for κ>1\kappa>1 (Corollaries D.2-D.6). Temporal stability ρ<1\rho<1 alone does not imply κ<1\kappa<1.

Furthermore, obtaining these results required several novel technical steps: separating direct readout sensitivity from recurrent-state sensitivity, solving coupled state and parameter-Jacobian recurrences under input-dependent transitions, bounding the second-order transition, state, and mixed-derivative terms of the loss Hessian, and composing causal input-output sensitivities across time and layers.

The looseness part of Weakness 1 is addressed in Response 2/3, which also shows how these insights are used to form expectations about nine federated algorithms. We will revise Section 4 to state the division between derived and reused components explicitly.

Response (2/4): Question 2.

We acknowledge that the absolute numerical values of the bounds are conservative, as noted in Section 5. Their practical role is therefore not to predict magnitudes, but to identify which quantities enter the convergence guarantee, how they scale, and which of them a given federated algorithm acts on. This is how worst-case convergence bounds commonly guide federated optimization: for example, the client-drift and objective-inconsistency terms of such bounds motivated the design of SCAFFOLD [7] and FedNova [6]. Furthermore, norm-based capacity measures are often studied for the trends they explain rather than for their numerical values [4]. In our case, the bounds show how recurrent stability and parameter norms interact with local training and client heterogeneity. These relationships remain informative even when the guarantee overestimates empirical magnitudes.

We utilized these relationships to analyze how practical federated algorithms modify specific terms of the bound: the local radius RR on which the SSM-dependent constants are evaluated, the heterogeneity term proportional to E(E−1)HTVE(E-1)\mathcal H_{\mathrm{TV}}, or the server step. We then formulated algorithm performance expectations in Table 2 based on this analysis. Methods that contract the radius (FedProx, FedDyn) are expected to improve on FedAvg. Disagreement correction (SCAFFOLD) is expected to help when clients are heterogeneous, but not when they are IID. Methods that rescale the server update (FedExP, FedAdam, DiLoCo) may enlarge the neighborhood and are expected to perform similarly or worse, while methods that act on none of these terms (FedAlign, FedSAM) are expected to behave like FedAvg. These expectations agree with 13 of 16 aggregate comparisons in the Mamba2 experiments (Table 2). For example, SCAFFOLD improves on FedAvg in 23 of 24 configurations at β=1\beta=1 and is worse in 22 of 24 at β=0\beta=0.

Furthermore, the synthetic experiments support the identified dependencies. Figure 2b shows that the measured gradient and estimated Hessian norms grow as ρ\rho approaches one, approximately as (1−ρ)−0.5(1-\rho)^{-0.5} and (1−ρ)−1.0(1-\rho)^{-1.0}. This growth is milder than that of our upper bounds, but it preserves their two-to-one ratio between the curvature and gradient exponents. Figure 2c shows gradient energy shifting toward the transition parameter AA, consistent with the importance of recurrent sensitivity. Client displacement grows approximately as E0.87E^{0.87}, consistent with the linear accumulation envelope (Figure 6a), and client-gradient disagreement increases near the stability boundary (Figure 6c).

We also note that the conservatism of the bound has a concrete origin in the proof. In Appendix A, controlling the hidden-state history introduces a geometric factor 1/(1−ρ)1/(1-\rho), and propagating the resulting parameter sensitivity through time introduces another, producing the recurrent contribution ρ/(1−ρ)2\rho/(1-\rho)^2 in the gradient bound. These factors are the cost of controlling recurrent accumulation uniformly over arbitrarily long sequences through ∑j=0S−1ρj=1−ρS1−ρ≤11−ρ\sum_{j=0}^{S-1}\rho^j =\frac{1-\rho^S}{1-\rho} \leq \frac{1}{1-\rho}. Without a uniform stability margin, these sums grow with the sequence length. Consistent with this, Table 22 and Figure 9 identify ρ/(1−ρ)2\rho/(1-\rho)^2 as the dominant contributor to the variation in both the bound magnitude and its utilization.

As such, the bounds provide empirically supported qualitative guidance about architectural sensitivity and algorithm selection in distributed optimization, even though their absolute magnitudes are conservative.

Response (3/4): Question 3.

We would like to clarify the scope and purpose of our experimental evaluation, why the theory is stated for SGD, and whether the stability assumption holds during practical training. Our experimental section consists of two parts: the synthetic dataset experiments that directly relate to our theoretical analysis, and the practical Mamba2 experiments. Below we describe each in detail.

The synthetic experiments (Section 5, Appendix H.1) implement the theoretical setting directly: teacher (which generates the data) and learner (the trained model) are both single-layer selective SSMs following the formulation of Section 3. The learner is trained with plain SGD (no momentum, weight decay, or clipping), and FedAvg and FedProx take local SGD steps as in Theorems B.5 and B.6. Stability is enforced rather than assumed: after every update the parameters are projected onto Sγ,δ\mathcal S_{\gamma,\delta} for eight specific stability limits from ρ=0.3\rho=0.3 to ρ=0.999\rho=0.999. Across 72 datasets, we find no violations in 1,411,776 checks of the gradient, smoothness, and bound-variation inequalities (Theorem 4.4, Lemmas 4.7 and B.1; Table 1), and none in 103,200 further checks over 1,200 FedAvg/FedProx runs. The same runs measure the quantities entering the convergence analysis: client displacement grows as E0.87E^{0.87}, consistent with the linear accumulation bound ηE,GSSM,R\eta E\\,G_{\mathrm{SSM},R}, and client-gradient disagreement grows as (1−ρ)−1.15(1-\rho)^{-1.15} (Figure 6). The paper therefore includes experiments in which the model, the SGD updates, and the stability condition match those of the analysis.

The purpose of the Mamba2 experiments is to ask a different question: do the mechanisms identified by the analysis remain informative for a complete practical architecture, trained the way such models are trained in practice? They are not a verification of the SGD convergence theorems (Appendix E describes the connection as "qualitative rather than a direct application of the convergence results"). The link is through the terms of the bound on which each algorithm acts: the local radius RR (FedProx, FedDyn), the client-disagreement term proportional to E(E−1)HTVE(E-1)\mathcal H_{\mathrm{TV}} (SCAFFOLD, FedDyn), and the server step (FedExP, FedAdam, DiLoCo). From these we state, per algorithm and heterogeneity level, whether validation perplexity should be lower than, similar to, or higher than that of FedAvg (Table 2), and compare with the results over 72 configurations and three seeds:

  • Direction. The expectations agree with 13 of 16 aggregate outcomes (Table 2). The correlation between expected direction and observed log-perplexity change is 0.710.71 over all configurations and seeds, and 0.810.81 at β=1\beta=1.
  • Heterogeneity. SCAFFOLD improves on FedAvg in 23 of 24 configurations at β=1\beta=1 and is worse in 22 of 24 at β=0\beta=0, as expected if its benefit comes from the disagreement term. FedProx's improvement grows from 17.017.0\\% at β=0\beta=0 to 34.434.4\\% at β=1\beta=1.
  • Local steps. The improvements of SCAFFOLD and FedDyn over FedAvg grow from about 4.54.5\\% and 1212\\% at E=64E=64 to about 1010\\% and 2222\\% at E=256E=256, consistent with the E(E−1)E(E-1) drift term (Appendix H.2.1).

Our theory analyzes SGD for several reasons. SGD-type local updates are the setting in which the reference guarantees for the considered federated algorithms are stated [3, 6-9], so our derived constants directly replace the assumed smoothness, variance, and dissimilarity constants. Convergence guarantees for client-side adaptive optimizers remain an active research topic, requiring additional assumptions or algorithmic corrections [10], and including them could introduce optimizer-specific effects that obscure the architectural dependencies we aim to isolate. Moreover, most of our results are optimizer-independent: the gradient, smoothness, variance, and heterogeneity bounds (Theorem 4.4, Lemmas 4.7 and B.1-B.4) are properties of the selective SSM objective, and only the final descent arguments of Theorems B.5 and B.6 use the SGD update. The practical experiments use AdamW because it is the standard optimizer for Mamba language models [11] and distributed language-model training [12]. Analyzing a tractable setting and then testing whether the conclusions transfer to full models is common in architecture-specific theory [5,13-16].

Reviewer_MekxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper looks at the challenges of convergence analysis for training state-space models (SSMs) in a federated setting. It presents an analysis that builds on the standard FedAvg convergence bounds by replacing the usual constants with SSM-specific terms, mainly the decay factor ρ and the norms of the SSM weights. The authors first derive gradient and smoothness bounds for a single-layer selective SSM, then use them to get convergence rates for FedAvg and FedProx, and extend this to multi-layer models. They test the bounds on synthetic data from a small teacher SSM and find no violations. They then compare nine federated learning algorithms on Mamba2 language modeling and report that the theory-based predictions mostly match the results.

Critical strengths

The proofs are careful and consistent, and the constants carry through correctly to the final convergence rate. The paper provides a strong research direction for analyzing how SSMs can be trained in a federated setting, making it more predictable and principled. Instead of just assuming the usual constants, the authors tie them to SSM properties like the decay factor and the weight norms, which gives some intuition for why long-memory SSMs are harder to train. The synthetic experiments are thorough and match the trends the theory predicts. The authors are also upfront about the limitations of their bounds.

Critical weaknesses

None

Questions for authors
  1. I’m not sure how this is architecture-aware. The FedAvg bound looks like the standard Wang et al. (2020) bound with the constants replaced by weight norms. Other than the 1/(1−ρ) term, what here is specific to SSMs? Also, the backbone ablation (Table 28) shows the same algorithm ranking for an attention-only model, so how are the results SSM-specific?

  2. What about the other layers in Mamba that are not SSMs (projections, convolution, gating, normalization, residuals)? How do you handle these in the bounds?

  3. In regular Mamba2 the default decay factor is around 0.999. Wouldn’t that make the bounds very loose (the (1−ρ)⁻¹² term is ~10³⁶)? Also, Mamba2 doesn’t stop Δ from going to zero during training, so how is the stability assumption guaranteed?

  4. The bounds depend on the weights, and you need to keep training within a ball R at each round. Doesn’t this mean you can’t compute the convergence bounds before training? And isn’t the FedProx result just a simple damping effect that would apply to any model?

  5. Hyperparameters are picked on the same validation perplexity that’s reported, and FedAvg isn’t tuned at all. Can you show results with a tuned FedAvg? Also, FedDyn and FedAdam look much worse over all 50 rounds (Table 26). Does the 13/16 agreement still hold with a different metric?

4 comments

Response (1/3)

We thank the reviewer for the insightful questions and the positive assessment of our manuscript. Below, we address each question to clarify the architecture-aware contributions, the assumptions and scope of our theoretical analysis, and the interpretation of our experimental results.

Architecture-aware components. The template of Wang et al. (2020) is used only in the final step of the FedAvg proof (Theorem B.5). The quantities substituted into that bound - the smoothness, variance, and client-disagreement constants - are the architecture-aware components: the preceding analysis derives them from the selective SSM recurrence rather than assuming them (Theorem 4.4, Lemmas 4.7, B.3, and B.4). Beyond the 1/(1−ρ)1/(1-\rho) factor, the resulting bounds are independent of sequence length, the parameter blocks enter separately through MR=(1+MB)(1+MC)(1+MΔ)(1+MΔ+MA)M_R=(1+M_B)(1+M_C)(1+M_\Delta)(1+M_\Delta+M_A) rather than through a single weight norm, and the local-drift terms scale as MR6/(1−ρ)12M_R^6/(1-\rho)^{12} versus MR4/(1−ρ)8M_R^4/(1-\rho)^{8} for the baseline stochastic term, so multiple local steps are penalized more when ρ\rho is close to one. Regarding Table 28, our analysis does not claim that the benefits of federated algorithms are exclusive to SSMs, and the provided results show that the transfer is not uniform: for instance, the FedAdam penalty (vs FedAvg) grows from +8+8\\% on Mamba2 to +40+40\\% on the attention-only backbone (Appendix H.2.3). However, extending our analysis to attention architectures, particularly the linear-attention formulations, which directly relate to SSMs through state-space duality [1], is an interesting direction for future work.

Non-SSM layers. To keep the architectural dependencies explicit and the analysis tractable, we focus on the core weight tuple of the selective SSM and its multi-layer composition. The input projections defining Bt,Ct,ΔtB_t,C_t,\Delta_t are explicitly incorporated in the bounds. Including the additional projections, convolution, gating, normalization, and residual connections would require substantial further first- and second-order sensitivity analysis. Furthermore, the additional constants and introduced relationships could obscure the dependence on recurrent stability and the core SSM parameters that we seek to isolate. Our deep Mamba2 experiments complement this focused theoretical analysis by examining whether the identified optimization mechanisms remain informative in complete practical model architectures containing these additional components.

Response (2/3)

Stability and sequence-length independence. The uniform stability margin ρ<1\rho<1 is the basis of our sequence-length-independent analysis: it controls recurrent accumulation through ∑j=0S−1ρj=1−ρS1−ρ≤11−ρ\sum_{j=0}^{S-1}\rho^j = \frac{1-\rho^S}{1-\rho} \leq \frac{1}{1-\rho}. Without a uniform margin, these accumulated contributions grow with the sequence length, and the argument no longer yields a length-independent guarantee. The strong dependence on (1−ρ)−1(1-\rho)^{-1} is the cost of controlling both the recurrent states and their parameter sensitivities uniformly over all sequence lengths.

We agree with the reviewer's estimate: for ρ≈0.999\rho\approx 0.999 the worst-case constants are extremely large, and in this regime the bound is numerically conservative rather than predictive. However, some degradation as ρ→1\rho\rightarrow 1 is inherent to any sequence-length-independent bound, since at ρ=1\rho=1 the accumulated terms grow linearly in SS.

When it comes to Δ\Delta, Mamba2 indeed does not prevent Δt\Delta_t from becoming arbitrarily small. However, Δt=Softplus(ut)>0\Delta_t=\mathrm{Softplus}(u_t)>0 for every finite utu_t, and a uniform lower bound δ>0\delta>0 exists whenever utu_t is bounded below, which holds when the parameters and layer inputs remain bounded, as in the neighborhoods used in our analysis (note that in the synthetic dataset experiments, we project the model parameters to ensure ρ\rho remains bounded by specified values such as 0.70.7). To examine this in practice, we conducted a new experiment tracking the largest recurrent transition factor in every layer of a 44-layer Mamba2 model during 5050 rounds of FedAvg training (44 clients, 6464 local AdamW steps per round, learning rate 0.0010.001, batch size 88, sequence length 512512). The table reports the largest measured factor per layer at selected rounds, across 33 seeds.

LayerInitializationRound 10Round 20Round 30Round 40Round 50
10.999451030.999674770.999577510.999273540.999166440.99922571
20.999456200.999430390.999524200.999678380.999571900.99972624
30.999543610.999727480.999680800.999642480.999619780.99960960
40.999525430.999764020.999612720.999625770.999796320.99976987

Across all recorded rounds and both local and server endpoints, no measured factor exceeded 0.9998830.999883, so a single constant ρ<1\rho < 1 bounds every measured factor. We acknowledge that the resulting numerical conservativeness is a limitation of our analysis, as we noted in Section 5 of our paper. Nevertheless, the established relationships remain informative: they identify which components of the selective SSM, namely the recurrent stability margin and the parameter envelopes, govern gradient growth, client drift, and the amplification of heterogeneity in distributed optimization.

Response (3/3)

Weight dependence and FedProx contribution. Calculating the bounds does not require knowing the actual future trained weights. Under the stated per-round containment assumption, each client remains within a distance RR of the broadcast model, moving the global model by at most RR per round through convex aggregation. As such, the deterministic parameter-norm envelopes can be constructed directly from initialization (Appendix G.3 directly uses MX=∣WX0∣2+(T+1)RM_X = \\|W_X^0\\|_2 + (T+1)R to compute the convergence bounds before the training), allowing the architecture-dependent constants to be pre-computed, conditional on the radius RR, uniform stability margins, and remaining theorem assumptions. Regarding FedProx, the proximal damping is the effective mechanism, but our analysis quantifies how this mechanism affects selective SSM distributed training. The effective radius Rμ≤RR_\mu \leq R results in tighter envelopes, which can reduce the gradient and smoothness bounds, while the proximal penalty adds the smoothness cost. As such, Theorem B.6 establishes an explicit trade-off rather than just observing that proximal regularization reduces client displacement.

FedAvg hyperparameters. The local learning rate and batch size were chosen beforehand based on non-federated training and held fixed across all methods, so that the federated algorithms are compared under a common local-training setup. FedAvg introduces no additional hyperparameters in this setup (Table 15), so we did not run a separately tuned FedAvg: tuning the shared local settings would retune every method rather than FedAvg alone.

Training performance differences. The reported 13/16 agreement concerns last-ten-round validation perplexity, which summarizes late-training performance. Using instead the validation perplexity averaged over all 5050 rounds (Table 23), the expected and observed directions agree in 1414 of the 1616 cases. Both disagreements are FedDyn, whose all-round average is dominated by early-round behavior: after round 1 its validation perplexity is approximately 88 times that of FedAvg, but it falls below FedAvg from round 4 onward and finishes 1818\\% lower (Appendix H.2.1). FedAdam's higher all-round perplexity is consistent with its expected direction, since it remains above FedAvg throughout training.

We appreciate the reviewer’s thoughtful questions and positive assessment of our work. We would be glad to address any further questions or feedback.

[1] Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In Forty-first International Conference on Machine Learning, 2024.

Thank you to the authors for their detailed response and for clarifying my comments and concerns. My original score already reflected a positive view of the paper, so I will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.