acceptodds
Under review as a conference paper at ICLR 2027

Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always

Abstract

We study personalized federated linear stochastic approximation (LSA), a framework which notably encompass personalized temporal difference learning. In this setting, heterogeneous agents collaborate to solve distinct linear fixed-point equations, each corresponding to an agent-specific learning problem. A central open question in personalized learning is whether a single method can adapt to an unknown level of heterogeneity by converging to each agent's personalized solution in all regimes while achieving a linear speedup in the number of agents when their learning problems are sufficiently similar. We answer this question affirmatively by introducing PF-LSA, a minimalist algorithm that mixes each agent's local stochastic update with the average update across agents, at no additional computational cost relative to standard federated methods. We prove that PF-LSA, achieves *best-of-both-worlds* guarantees without any prior knowledge on the level of heterogeneity. Our analysis is based on a sharp decomposition of the error into consensus and disagreement components. The consensus error decays rapidly, whereas the disagreement error decays more slowly but becomes negligible in low-heterogeneity regimes.

Primary area:
optimization
Keywords:
Personalized Federated Learning, Linear Stochastic Approximation, Optimization

Reviews

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

This paper studies the personalized federated linear stochastic approximation problem, where the coefficient matrices AA's and the right-hand-side vectors bb's can be different across agents. It proposes an algorithm that allows the agents to collaborate while achieving local optimal solutions. In short, the agents use a mixture of local gradient and the global aggregated gradient to update their own parameter estimation. When heterogeneity is small enough, the algorithm is proven to achieve both linear speedup and personalization.

Critical strengths

Strengths: The paper is well-written and easy to follow. The technical part looks solid and clear to me. Personalization in federated reinforcement learning is under-researched; therefore, the exploration in this regard is commendable.

Critical weaknesses

Weaknesses: 1. The linear speedup relies on low heterogeneity, which is not convincing. If the heterogeneity is low, do we really need personalization? In [1], they already showed in their Theorem 2 that FedTD can converge to a neighbourhood of each agent's optimal solution, where the size of the neighbourhood is determined by heterogeneity. Therefore, I believe the message given by this paper is not adequate. Could the authors compare with [1]?

  1. The paper misses several papers on personalized federated reinforcement learning, such as [2]. In the Personalized Federated Learning section, [3] is missing as well.

  2. The algorithm structure that uses a mixture of local and global gradients is not novel. For example, [4] also uses weighted gradients.

[1] Han Wang, Aritra Mitra, Hamed Hassani, George J. Pappas, James Anderson, Federated TD Learning with Linear Function Approximation under Environmental Heterogeneity, TMLR 2024

[2] Guojun Xiong, Shufan Wang, Daniel Jiang, Jian Li, On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representations, ICLR 2025

[3] Liam Collins, Hamed Hassani, Aryan Mokhtari, Sanjay Shakkottai, Exploiting Shared Representations for Personalized Federated Learning, ICML 2021

[4] El Mahdi Chayti, Sai Praneeth Karimireddy, Sebastian U. Stich, Nicolas Flammarion, Martin Jaggi, Linear Speedup in Personalized Collaborative Learning, arXiv

Questions for authors

See Weaknesses.

3 comments

We thank the reviewer for their careful reading and constructive feedback. We appreciate the opportunity to clarify the motivation for our approach and its relationship to existing work. We address each concern below.

  • [W1] "The linear speedup relies on low heterogeneity, which is not convincing. If the heterogeneity is low, do we really need personalization? In [1], they already showed in their Theorem 2 that FedTD can converge to a neighbourhood of each agent's optimal solution, where the size of the neighbourhood is determined by heterogeneity. Therefore, I believe the message given by this paper is not adequate. Could the authors compare with [1]?"

We thank the reviewer for raising this important point. We agree that when heterogeneity is sufficiently small and the desired accuracy is not too stringent, learning a shared solution may be sufficient. However, even mild heterogeneity can make personalization necessary when aiming for high precision.

Indeed, as established in Theorem 2 of [1], FedTD converges to a neighborhood of each agent's individual solution, whose size depends on the level of heterogeneity. Consequently, even under mild heterogeneity, this residual bias prevents FedTD from guaranteeing arbitrarily high accuracy with respect to each agent's personalized target.

In contrast, PF-LSA preserves convergence toward each agent's individual solution, regardless of heterogeneity. Moreover, when the agents' learning problems are sufficiently similar and the target accuracy is not too stringent, our analysis establishes a linear speedup in per-agent sample complexity. Thus, our objective is precisely to combine the benefits of collaboration with the ability to attain arbitrarily high accuracy on personalized problems.

Importantly, the level of heterogeneity may not be known beforehand, particularly in online learning, where agents collect observations sequentially rather than having access to complete datasets. Our method therefore does not require determining in advance whether collaboration is beneficial: the same mixing coefficient β=1/N\beta=1/N is used across all heterogeneity regimes.

  • [W2] The paper misses several papers on personalized federated reinforcement learning, such as [2]. In the Personalized Federated Learning section, [3] is missing as well.

We thank the reviewer for bringing these references to our attention. We have included and discussed both [2] and [3] in the revised manuscript.

Both works exploit a shared representation across agents, together with agent-specific parameters, to obtain the benefits of collaboration. Our approach addresses a complementary setting. Rather than assuming that the agents' learning problems admit a common representation, we allow each agent to solve its own linear fixed-point equation with potentially heterogeneous stochastic operators. We establish conditions under which collaboration yields a linear sample-complexity speedup without assuming a shared representation or requiring prior knowledge of inter-agent similarities.

We have clarified these distinctions in the related-work section.

  • [W3] The algorithm structure that uses a mixture of local and global gradients is not novel. For example, [4] also uses weighted gradients.

We agree with the reviewer that mixing local and global gradients is not, by itself, a novel mechanism. We have revised the manuscript to acknowledge related approaches and to make clear that our main contribution lies in the theoretical guarantees rather than the mixing mechanism.

In particular, [4] studies personalized collaborative learning through a different formulation: the objective is to optimize a designated target task using information from auxiliary tasks. The authors analyze weighted gradient averaging and a bias-correction approach inspired by control variates.

By contrast, our objective is to solve all agents' personalized learning problems simultaneously, rather than using auxiliary agents primarily to improve the solution of one designated task. We establish non-asymptotic convergence guarantees toward every agent's individual solution and characterize when collaboration yields a linear speedup in per-agent sample complexity.

We believe this distinction is particularly relevant in federated learning, where every participating agent has its own learning objective. We have revised the manuscript to better acknowledge prior work and emphasize these theoretical contributions.


We thank the reviewer once again for their constructive feedback and remain available to address any further questions or concerns.

[1] Han Wang, Aritra Mitra, Hamed Hassani, George J. Pappas, James Anderson, Federated TD Learning with Linear Function Approximation under Environmental Heterogeneity, TMLR 2024

[2] Guojun Xiong, Shufan Wang, Daniel Jiang, Jian Li, On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representations, ICLR 2025

[3] Liam Collins, Hamed Hassani, Aryan Mokhtari, Sanjay Shakkottai, Exploiting Shared Representations for Personalized Federated Learning, ICML 2021

[4] El Mahdi Chayti, Sai Praneeth Karimireddy, Sebastian U. Stich, Nicolas Flammarion, Martin Jaggi, Linear Speedup in Personalized Collaborative Learning, arXiv

Dear Reviewer,

As the discussion period draws to a close, we would like to ask whether any of your concerns remain unresolved following our response. We would be grateful if you could let us know and consider updating your score if you feel that your concerns have been adequately addressed.

Regarding the linear speedup, we have included an additional experiment demonstrating that linear speedup is still achieved in mildly heterogeneous settings, and that our algorithm remains effective even in highly heterogeneous settings. The results are included in the revised manuscript, and we refer you to our response to Reviewer yDw6 for further details.

Thank you again for your time and valuable feedback.

Kind regards,
The Authors

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

This paper studies personalized federated linear stochastic approximation. Using a strict convex combination of the global and local updates is proved to converge to fully personalized solutions. An extension to personalized federated TD learning is discussed.

Critical strengths
  • The paper is well written. The structure and progression flows smoothly and the results are clearly presented.
  • The proposed method is simple and effective, and the theoretical results are sound and intuitive.
Critical weaknesses
  • I think the analysis framework is novel and promising, but an important chunk of the story is missing. Currently the work focuses on two extreme regimes of personalized learning: the low- and high-heterogeneity regimes, while it does not have much to say about the intermediate regime. Usually in practice, people are aware of low- and high-heterogeneity, and thus they can resort to more tailored methods. Therefore, personalized methods should be more powerful in the intermediate regime with unknown heterogeneity level, and thus I think it's more interesting and important to prove its benefits in this regime.
  • Specifically, I think the "High-Heterogeneity Regime" can be finer and expanded into a more thorough discussion of the intermediate regime:
    1. The O~(1/ϵ)\tilde{O}(1 /\epsilon) rate is too coarse. A finer asymptotic rate based on Corollary 4.8 is O(ζ2σˉϵ2a4ϵlog⁡(ζ2(D0+N−1∥eˉ0∥2)a2ϵ)).O\left( \frac{\zeta^{2} \bar{\sigma}^{2}_{\epsilon}}{a^{4}\epsilon} \log \left( \frac{\zeta^{2} (D^{0} + N^{-1}\|\bar{e}^{0}\|^{2}) }{a^{2}\epsilon} \right) \right). Assuming agents have comparable noise level and initialization error, compared to the single-agent baseline O~(σ2/(a4ϵ))\tilde{O}(\sigma^{2} /(a^{4}\epsilon) ), the rate can demonstrate provable speedup when ζ2\zeta^{2} is small, but can also be strictly worse when ζ2\zeta^{2} is large. A O~(1/ϵ)\tilde{O}(1 /\epsilon) rate mixes these two cases and also misses the opportunity to show the benefits of collaboration in the intermediate regime.
    2. Both the theoretical analysis and empirical performance of the method depend heavily on the hyperparameter β\beta. Currently the main text sets β=1/N\beta = 1 /N for all heterogeneity levels, which I believe would be very suboptimal for intermediate regimes and less practical when NN is large. An analysis of the optimal β\beta or its practical guidelines would significantly improve the work.
  • Experiments only contain single-agent and FedAvg as baselines, which are not enough to verify the theoretical results of the proposed method, especially in the intermediate regime. It's important to include other baselines, at least those converging to fully personalized solutions, in the LSA setup of the work across different heterogeneity levels.
  • Aˉ\bar{A} is not defined in Eq. (1)
Questions for authors

A previous version of the work sets λ=β−2\lambda = \beta^{-2} in the Lyapunov function and lists the second term in Theorem 4.2 as ηa(1+β−1N)\frac{\eta}{a}(1+\frac{\beta^{-1}}{N}). However, substituting λ=β−2\lambda = \beta^{-2} in the current version of Theorem 4.2 would make the second term ηa(β+β−2N)\frac{\eta}{a}(\beta+\frac{\beta^{-2}}{N}). Could you please explain the discrepancy?

5 comments

We thank the reviewer for their constructive feedback. We are pleased that the reviewer found that our paper 'is well written' and that "the theoretical results are sound and intuitive". In the following, we address each of the reviewers' concerns.

  • [W1]: Currently the work focuses on two extreme regimes of personalized learning: the low- and high-heterogeneity regimes, while it does not have much to say about the intermediate regime. [...] Therefore, personalized methods should be more powerful in the intermediate regime with unknown heterogeneity level, and thus I think it's more interesting and important to prove its benefits in this regime.

We thank the reviewer for this insightful comment. The reviewer's intuition is indeed correct, but only up to a certain target accuracy. Under mild heterogeneity, when the desired accuracy is not too stringent, the agents' learning problems remain sufficiently similar for collaboration to yield a linear speedup, as formalized in Corollary 4.6.

However, when aiming for very high precision, even small differences between the agents' individual objectives become significant relative to the target accuracy. Consequently, even under mild heterogeneity, the agents' objectives may no longer be sufficiently aligned to benefit from collaboration, and a linear speedup cannot generally be expected. This trade-off is captured by our analysis: collaboration accelerates the shared component of the learning process, whereas achieving high precision ultimately requires each agent to converge toward its own personalized solution.

We also emphasize that, to the best of our knowledge, our work is the first to establish a linear sample-complexity speedup in personalized federated learning under mild heterogeneity without requiring prior knowledge of the structure of heterogeneity or inter-agent similarities. Importantly, this guarantee is obtained with a fixed mixing coefficient β=1/N\beta=1/N, chosen independently of the heterogeneity level.

  • [W1b] Usually in practice, people are aware of low- and high-heterogeneity, and thus they can resort to more tailored methods.

We respectfully disagree with the reviewer's observation that the level of heterogeneity is generally known in practice. In many applications, heterogeneity depends on properties of the underlying environments that are unknown to the agents. This is precisely one of the main difficulties of online learning, where the agents interact with their environments and collect data sequentially, rather than having access to the complete datasets beforehand.

For instance, in personalized TD learning, autonomous vehicles may operate in different environments while initially observing very similar trajectories. However, an agent may encounter an obstacle only after 10,000 interactions, revealing a difference in the transition dynamics that could not have been anticipated from the initial observations. Thus, determining whether the agents operate in a low-, intermediate-, or high-heterogeneity regime may itself require substantial exploration and information that is not available in advance. This motivates the need for methods that can benefit from collaboration without requiring prior knowledge of the level of heterogeneity.

  • [W2]: "The O~(1/ε)\widetilde{O}(1/\varepsilon) rate is too coarse. A finer asymptotic rate based on Corollary 4.8 is O(ζ2σˉε2a4εlog⁡(ζ2(D0+N−1∣eˉ0∣2)a2ε)).O\left( \frac{\zeta^2 \bar{\sigma}_\varepsilon^2}{a^4 \varepsilon} \log\left( \frac{\zeta^2(D^0 + N^{-1}|\bar{e}^0|^2)} {a^2 \varepsilon} \right) \right). Assuming agents have comparable noise level and initialization error, compared to the single-agent baseline O~(σ2/(a4ε))\widetilde{O}(\sigma^2/(a^4\varepsilon)), the rate can demonstrate provable speedup when ζ2\zeta^2 is small, but can also be strictly worse when ζ2\zeta^2 is large."

We agree with the reviewer that, in the high-heterogeneity regime covered by Corollary 4.8, our sample-complexity guarantee may become less favorable as heterogeneity increases. However, recall that ζ≤2CA\zeta \leq 2C_A, and hence ζ2≤4CA2\zeta^2 \leq 4C_A^2. Consequently, the additional dependence on heterogeneity is uniformly bounded by a problem-dependent constant. Thus, even in highly heterogeneous settings, PF-LSA retains the same O~(1/ε)\widetilde{O}(1/\varepsilon) sample-complexity dependence as independent single-agent learning, although with potentially less favorable constants.

  • [W3]: "Both the theoretical analysis and empirical performance of the method depend heavily on the hyperparameter β\beta. Currently the main text sets β=1/N\beta = 1/N for all heterogeneity levels, which I believe would be very suboptimal for intermediate regimes and less practical when NN is large. An analysis of the optimal β\beta or its practical guidelines would significantly improve the work."

Our objective is to introduce a personalized federated algorithm that does not require tuning an additional mixing parameter based on the level of heterogeneity. In particular, choosing β=1/N\beta=1/N independently of heterogeneity is sufficient to establish our best-of-both-worlds guarantees.

We agree that this choice may not be optimal in every regime. Increasing β\beta accelerates the slower personalization dynamics but also increases the variance term in our convergence bounds. Our choice therefore provides a simple, heterogeneity-independent prescription rather than requiring problem-specific tuning. We will clarify this trade-off in the revised manuscript.

  • [W4]: "Aˉ\bar{A} is not defined in Eq.~(1)."

We thank the reviewer for pointing out this omission. The intended definition is

Aˉ=1N∑c=1NAˉc.\bar A=\frac1N\sum_{c=1}^N\bar A_c.

We have included this omission in the revised manuscript.

  • [Q1]: A previous version of the work sets λ=β−2\lambda = \beta^{-2} in the Lyapunov function and lists the second term in Theorem 4.2 as ηa(1+β−1N)\frac{\eta}{a}\left(1+\frac{\beta^{-1}}{N}\right). However, substituting λ=β−2\lambda = \beta^{-2} in the current version of Theorem~4.2 would make the second term ηa(β+β−2N)\frac{\eta}{a}\left(\beta+\frac{\beta^{-2}}{N}\right). Could you please explain the discrepancy?

We thank the reviewer for pointing out this discrepancy. It stems from a change in the Lyapunov function between the two versions, as well as a typographical error in the current manuscript, which has now been corrected. While the previous Lyapunov function weighted the disagreement component by β−1\beta^{-1}, the new formulation weights the consensus component by βλ\beta\lambda. Importantly, the introduction of λ\lambda allows us to adjust the relative weight of the two components according to the level of heterogeneity. This flexibility enables a more refined analysis, yielding sharper convergence bounds that distinguish between low- and high-heterogeneity regimes and are essential to establishing our sample-complexity guarantees.


We thank the reviewer once again for their constructive feedback and remain available to address any further questions or concerns.

Dear Reviewer,

As the discussion period draws to a close, we would like to ask whether any of your concerns remain unresolved following our response. We would be grateful if you could let us know so that we can improve the quality of our manuscript as much as possible.

Thank you again for your time and valuable feedback.

Kind regards, The Authors

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

The paper studies personalized federated linear stochastic approximation, in which each agent seeks the solution to its own linear system using noisy local observations. It proposes PF-LSA, which combines each agent’s local stochastic residual with the average residual across all agents through a fixed mixing parameter β\beta.

The analysis separates estimation error into a fast average-error component and a slower disagreement component. Under independent sampling and stability assumptions, it develops finite-time mean-square error bounds and identifies conditions under which β=1/N\beta=1/N yields linear speedup in per-agent sample complexity while retaining personalized solutions. In more heterogeneous regimes, the bounds recover the independent-learning dependence on target accuracy, with additional heterogeneity and transient factors. The results are specialized to personalized TD learning under an i.i.d. generative sampling model. Experiments on small Garnet problems compare PF-LSA with independent LSA and FedLSA across varying levels of heterogeneity and numbers of agents.

Critical strengths
  1. A simple collaboration mechanism that preserves the personalized targets. The problem is well-motivated: agents should benefit from shared information without being forced to solve a common or mixed problem. PF-LSA communicates only stochastic update vectors and does not require estimating pairwise similarities, density ratios, or explicit bias-correction variables. For β>0\beta>0, its deterministic stationary equations recover all local solutions. The value here is not simplicity by itself, but the possibility of obtaining useful personalized guarantees with such limited algorithmic machinery.

  2. A meaningful finite-time analysis of heterogeneous linear operators. The analysis separates the average estimation error from disagreement around that average, rather than requiring the personalized parameters themselves to reach consensus. It quantifies how operator heterogeneity couples the fast average-error dynamics to the slower personalization dynamics and distinguishes operator differences from dispersion of the local solutions. This provides an interpretable explanation of when collaboration can help and when the slow component dominates. The specialization to TD learning also makes the dependence on the discount factor and feature conditioning explicit. Subject to the corrections below, this analysis is a substantive contribution.

Critical weaknesses
  1. Theorem 4.2 does not hold for the Lyapunov function stated in the main text. Section 4.2 defines Φλt=E ⁣[∥eˉt∥2+βλDt],\Phi_\lambda^t=\mathbb E\!\left[\|\bar e^t\|^2+\beta\lambda D^t\right], whereas Theorem A.1 and Corollary A.3 analyze E ⁣[Dt+βλ∥eˉt∥2].\mathbb E\!\left[D^t+\beta\lambda\|\bar e^t\|^2\right]. These quantities cannot be interchanged without changing the bounds.

For a concrete counterexample, consider two deterministic scalar systems with A1=1A_1=1, A2=2A_2=2, and b1=b2=0b_1=b_2=0. Take a=1a=1, η∞=1/4\eta_\infty=1/4, CA=2C_A=2, η=0.01\eta=0.01, β=0.1\beta=0.1, and λ=1\lambda=1, with initial errors e10=1.1e_1^0=1.1 and e20=−0.9e_2^0=-0.9. These choices satisfy the stated assumptions and parameter restrictions, and the noise variance is zero. Algorithm 1 gives

\Phi_\lambda^1=0.11042246025,$$ while Theorem 4.2 requires $$\Phi_\lambda^1\leq(1-\eta\beta a)\Phi_\lambda^0=0.10989.$$ Thus, the stated quantity can increase even in this deterministic example. The appendix suggests that correcting the definition may repair the result, but the authors should reconcile the main theorem with its proof and verify the subsequent guarantees. This is consequential because the weighted-energy argument is a central ingredient of the analysis. 2. **The contribution and the scope of the “best-of-both-worlds” claim need sharper differentiation from prior work.** LG-Mix [1, Eq. (2)] already combines local updates with their global average. With one local step, uniform aggregation, and a fixed mixing coefficient, its general update rule has the same algebraic form as PF-LSA. This does not supply the present guarantees for general LSA operators, but it means that the contribution should be positioned primarily as new analysis and a specialization of an existing mixing mechanism, rather than as a fundamentally new aggregation rule. AffPCL [2] also establishes personalized linear-system convergence with heterogeneity-dependent collaborative speedup. PF-LSA has a potentially important advantage in avoiding its auxiliary correction and density-ratio machinery, but the corresponding trade-off in assumptions and guarantees needs a direct comparison. In particular, Corollary 4.6 requires more than $\zeta^2<a^2/4$: the initial disagreement and heterogeneity-induced slow component must be sufficiently small relative to the target accuracy. For fixed nonzero disagreement, the slow transient can dominate as the requested accuracy increases. Likewise, recovering the independent-learning dependence on $\varepsilon$ in high heterogeneity is not the same as a uniform guarantee of no slowdown in all problem parameters. The experiments provide qualitative support, but do not fully resolve these distinctions. Appendix E varies $N$, yet also scales $\eta$ with $N$. Quantitative comparisons at common target accuracies, with comparable step-size tuning for the baselines, would make the practical significance of the theoretical trade-off clearer. References: [1] Meirui Jiang, Anjie Le, Xiaoxiao Li, and Qi Dou. “Heterogeneous Personalized Federated Learning by Local-Global Updates Mixing via Convergence Rate.” ICLR, 2024. [2] Chenyu Zhang and Navid Azizan. “Personalized Collaborative Learning with Affinity-Based Variance Reduction.” ICLR, 2026.
Questions for authors
  1. Correction of the central Lyapunov statement. Is the intended definition in Theorem 4.2 Φλt=E ⁣[Dt+βλ∥eˉt∥2]?\Phi_\lambda^t=\mathbb E\!\left[D^t+\beta\lambda\|\bar e^t\|^2\right]? Please reconcile the main text with Theorem A.1 and confirm whether Theorem 4.4 and its corollaries remain unchanged. Please also make the step-size quantifiers in the sample-complexity statements precise: the displayed iteration budgets appear to require choosing η\eta at the scale of the maximum admissible value, not allowing an arbitrarily smaller η\eta while keeping the same budget.

  2. Precise distinction from LG-Mix and AffPCL. Which finite-time guarantees are new relative to these two works? A comparison separating the update rule, allowable local operators, required information or auxiliary estimation, heterogeneity measure, and sample/communication complexity would clarify the contribution. In particular, what is gained by dispensing with AffPCL’s correction machinery, and what is lost in the conditions or parameter dependence of the speedup guarantee?

  3. Accuracy range and heterogeneity-independent parameter selection. For a fixed problem with nonzero D0D^0 or ζ\zeta, over what target-accuracy range does Corollary 4.6 guarantee linear speedup before the slow personalization term dominates? Also, which concrete step-size prescription achieves the advertised adaptation without knowing the level of heterogeneity? The choice β=1/N\beta=1/N is heterogeneity independent, but the sufficient step-size bound in Corollary 4.8 explicitly contains ζ\zeta. Clarifying the distinction between an untuned mixing coefficient, universal stability, and an implementable accuracy guarantee would affect my assessment.

  4. Quantitative validation using the existing experiments. Appendix E already compares N∈{2,8,16}N\in\{2,8,16\}. Can these experiments report the number of iterations needed to reach several common MSE targets and compare the resulting speedup with independently tuned local LSA under the same tuning budget? Larger steps for PF-LSA may be justified by variance reduction, so identical step sizes are not essential; what matters is distinguishing a genuine improvement in the attainable error-versus-cost trade-off from a difference in the selected learning rates. Please distinguish per-agent samples, total samples across agents, and communication rounds, and relate the experimental heterogeneity settings to the quantities ζ\zeta and D0D^0 used in the theory.

3 comments

We thank the reviewer for their detailed and constructive review. We are pleased that the reviewer recognizes that our "analysis is a substantive contribution" , that we provide "a simple collaboration mechanism that preserves the personalized targets", and that we have provided a solution to a "problem [that] is well motivated." Below, we address each of the weaknesses and questions raised by the reviewer.

  • [W1] and [Q1]: " Is the intended definition in Theorem 4.2 $ \Phi_\lambda^t=\mathbb E!\left[D^t+\beta\lambda|\bar e^t|^2\right]? $" [...] Make the step-size quantifiers in the sample-complexity statements precise [...]

We thank the reviewer for catching these two typos. Both corrections have been incorporated into the revised manuscript.

  • [W2] and [Q2]: "Precise distinction from LG-Mix and AffPCL [...]"

We thank the reviewer for bringing LG-Mix to our attention, as we had overlooked this work in the original submission. We agree that LG-Mix introduces a closely related mechanism based on mixing local and global updates. We have revised the manuscript to acknowledge this prior contribution and clarify the novelty of our theoretical results.

Novelty with respect to LG-Mix. The main distinction lies in the theoretical guarantees. LG-Mix analyzes exact (full-batch) gradient updates and establishes a descent inequality for the training prediction error. However, its analysis does not provide finite-time convergence guarantees toward each agent's personalized solution or establish a linear speedup in the number of agents. In particular, the analysis does not justify increasing the global step size proportionally to NN while keeping the local step size fixed, which is a key ingredient in establishing a linear speedup through step-size scaling.

In contrast, we extend the local--global mixing mechanism to personalized federated LSA and analyze stochastic updates. We establish non-asymptotic convergence guarantees toward each agent's individual solution and prove that the method achieves a linear speedup in per-agent sample complexity under sufficiently mild heterogeneity.

We have incorporated this discussion into the revised manuscript, with the relevant changes highlighted in red.

Novelty with respect to AffPCL. AffPCL requires knowledge or estimation of density ratios, which are generally not available in practice (especially when using this type of methods), and assumes identical sample-wise operators Ac(⋅)A_c(\cdot) across agents. In contrast, our method accommodates heterogeneous stochastic operators without requiring prior knowledge of heterogeneity, while guaranteeing convergence to each agent's personalized solution.

  • [Q3a]: "For a fixed problem with nonzero D0D^0 or ζ\zeta, over what target-accuracy range does Corollary 4.6 guarantee linear speedup?"

From Corollary 4.6, we obtain that linear speedup is guaranteed whenever the desired precision is

\left(\frac{V^N}{U}\right)^{\frac{1}{N-1}},$$ where $U=|\bar e^0|^2$ and $V=D^0+\frac{\zeta^2}{a^2N}|\bar e^0|^2$. This condition shows that linear speedup can be achieved for moderate target accuracies, whereas achieving very high accuracy requires agents to converge toward their distinct individual solutions. This is expected as, in this regime, agents' objectives are not aligned, and one does not generally expect a linear speedup from collaboration with incompatible agents. Nevertheless, our experiments suggest that this theoretical condition may be conservative, as substantial speedups are observed beyond the regimes directly covered by our guarantees. Yet, extending our analysis beyond this condition is not straightforward at all, and deriving sharper conditions on $\varepsilon$ that better capture these empirical improvements is an interesting direction for future work.
  • [Q3b] "Which step-size achieves the advertised adaptation without knowing the level of heterogeneity? The choice β=1/N\beta = 1/N is heterogeneity independent, but the step-size bound in Corollary 4.8 contains ζ\zeta. "

Thank you for allowing us to clarify this central point. Our main objective is to introduce a personalized federated algorithm that does not require tuning an additional mixing parameter based on the level of heterogeneity. In particular, we choose β=1/N\beta = 1/N, independently of the similarity between agents. This choice is sufficient to establish our best-of-both-worlds guarantees.

However, we do not claim that every parameter can be chosen independently of the problem characteristics. As is common in finite-time analyses of federated learning, the admissible step size may depend on the problem parameters. Nevertheless, a conservative step-size choice independent of ζ\zeta can be obtained using the uniform bound $ \zeta = \leq 2C_A. $ Such a choice is valid in both heterogeneity regimes, although it may be more conservative than one based on the actual value of ζ\zeta.

We therefore emphasize that our heterogeneity-independent adaptation claim concerns the mixing coefficient β\beta, rather than a completely parameter-free choice of the learning rate. We thank the reviewer for pointing this out and we have clarified this distinction in the revised manuscript.

  • [W3] and [Q4]: " Quantitative comparisons at common target accuracies, with comparable step-size tuning for the baselines, would make the practical significance of the theoretical trade-off clearer."

We thank the reviewer for this suggestion. To address this concern, we have conducted additional experiments, presented in Figures 2 and 3 of the revised manuscript, to quantify the sample-complexity gains of PF-LSA relative to independent learning.

More precisely, we consider N∈2,8,16,32N\in{2,8,16,32} agents and eight levels of reward and transition-kernel heterogeneity:

\in{0,0.01,0.05,0.07,0.1,0.25,0.5,0.9}.$$ We compare PF-LSA, with $\beta=1/N$, against a single-agent Local LSA baseline ($N=1$). For a fair comparison, the step sizes of both methods are independently tuned over $14$ candidates for each configuration, using $5$ independent tuning runs. The selected configurations are then evaluated over $10$ additional independent runs. To quantify the benefits of collaboration, we measure the per-agent sample speedup required to reach a prescribed accuracy $\varepsilon=0.1$, defined as $$\text{Speedup}(N) = \frac{T_{\text{Local LSA}}(\varepsilon)}{T_{\text{PF-LSA},N}(\varepsilon)},$$ where $T_{\mathrm{Local\,LSA}}(\varepsilon)$ and $T_{\mathrm{PF\text{-}LSA},N}(\varepsilon)$ denote the numbers of iterations required by the respective algorithms to reach the target accuracy. Since each agent collects one sample per iteration, this ratio measures the reduction in per-agent sample complexity achieved through collaboration. The results in Figure 3 show that PF-LSA achieves a linear speedup in the number of agents under homogeneous environments. This linear scaling persists under mild heterogeneity, confirming that collaboration can substantially improve sample efficiency even when the agents' learning problems are not identical. As heterogeneity increases, the benefits of collaboration progressively diminish, consistent with our theoretical predictions. Importantly, even in highly heterogeneous settings, PF-LSA preserves personalization and recovers the same order of sample complexity as independent single-agent learning. The accompanying MSE trajectories in Figure 2, together with the additional configurations reported in the appendix, further illustrate this transition. These observations agree with the two-clock structure identified in our analysis: when heterogeneity is sufficiently small, the fast consensus dynamics dominates, allowing collaboration to substantially reduce per-agent sample complexity. As heterogeneity increases, the slower disagreement dynamics becomes more influential, limiting the benefits of information sharing. We have incorporated these additional experiments, the independently tuned comparisons, and the complete evaluation protocol into the revised manuscript. We believe these results directly address the reviewer's request and provide quantitative evidence of the practical significance of our theoretical guarantees. ---------- We thank the reviewer once again for their constructive feedback and remain available to address any further questions or concerns.
Reviewer_yDw6OpenReview ↗

Response

I appreciate the authors' effort to clearly address my earlier concerns. I will change my score accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.