acceptodds
Under review as a conference paper at ICLR 2027

Distributed Learning under Autonomous Client Participation

Abstract

The common assumption in distributed learning (DL) is that the central parameter server dictates client participation to optimize its training efficiency, while clients do not actively affect participation decisions beyond sending their updates when requested. However, this does not reflect the clients' real-world behavior, where they act autonomously based on self-interest, privacy concerns, and local model performance. In this paper, we introduce a theoretical framework that models autonomous state-dependent client participation in DL as a Markov chain, and analyze learning convergence in case client availability is dynamic and correlated across rounds. We analyze both homogeneous and heterogeneous data environments, as well as various participation rules that model client behavior. We demonstrate, both theoretically and empirically, that once autonomy exceeds a critical threshold, the Markov chain fails to mix and the learning process stagnates. We further show that, in heterogeneous settings, autonomous dropout of clients from the learning process induces a bias. This bias creates a feedback loop that steers the global model to an equilibrium that favors the more dominant data distributions. Finally, we consider the setting in which the parameter server can incentivize the participation of a uniform set of clients using a limited budget. We develop a policy-optimization method for the allocation of this budget that is based on our error bounds, and show it ensures convergence even in highly autonomous distributed networks.

Primary area:
learning theory
Keywords:
Distributed Learning, Autonomous Client Participation, Markov Chain Dynamics, Convergence Bounds

Reviews

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

This paper investigates distributed learning under autonomous client participation, challenging the conventional assumption that client participation is primarily controlled by a central server. Motivated by practical scenarios where clients independently decide whether to participate based on their self-interest, resource constraints, and historical information, the authors propose a Markovian framework to characterize dynamic and temporally correlated participation behaviors. Under homogeneous data distributions, the paper derives convergence bounds that characterize the effects of participation probability, effective sample size, and Markov chain mixing time on learning performance. The authors further analyze different participation mechanisms and identify a critical autonomy threshold associated with training instability. Based on these theoretical findings, a budget-constrained server policy optimization method is proposed to incentivize client participation and improve learning stability. The framework is subsequently extended to heterogeneous data settings, where autonomous participation may introduce distributional bias and feedback effects that influence global model convergence. Finally, numerical simulations are conducted to examine the theoretical predictions, participation dynamics, and effectiveness of the proposed budget allocation strategy.

Critical strengths

1. Meaningful Problem Motivation and Research Perspective. The paper investigates a practically relevant problem by relaxing the conventional assumption that client participation in distributed learning is primarily controlled by a central server. In real-world distributed environments, clients may independently decide whether to participate based on their individual interests, resource constraints, and historical experiences. Considering such autonomous behavior introduces additional challenges beyond conventional client selection, particularly regarding temporally correlated participation and its interaction with global model training. This perspective is valuable because it highlights an important aspect of distributed learning dynamics that deserves further theoretical investigation.

2. Systematic Theoretical Analysis of Autonomous Participation. The paper demonstrates substantial theoretical effort in analyzing the influence of dynamic client participation on learning convergence. In particular, Theorem 2 (Sec. 3.4) connects participation probability, effective sample size, and Markov chain mixing time with convergence performance, offering a structured perspective on how different aspects of participation dynamics affect distributed optimization. The subsequent analysis of different participation mechanisms and critical autonomy thresholds further extends this theoretical investigation. These results provide useful insights into the relationship between client participation behavior and learning stability, while also motivating the server-side budget allocation framework.

Critical weaknesses

1. Limited Generality and Insufficient Justification of the Theoretical Framework.

Although the paper investigates a meaningful and practically relevant problem, the proposed theoretical framework relies on several restrictive assumptions, and the scope of its main theoretical guarantees remains insufficiently aligned with the motivating scenarios. My primary concerns are as follows:

  • Insufficient justification of autonomous participation behaviors. The proposed participation mechanisms rely on specifically designed behavioral assumptions whose connections to realistic client decisions remain unclear. For instance, Eq. (10) assumes that a client's participation probability increases with the number of previously participating clients, following a predefined logistic function. Although the authors provide intuitive explanations based on privacy and resource considerations, it remains unclear whether this model captures representative participation behaviors in practical distributed systems or whether the theoretical conclusions remain valid under alternative participation mechanisms.

  • Overemphasis on homogeneous data and limited heterogeneous analysis. The central theoretical contributions in Sec. 3, including the convergence bounds, Markovian mixing analysis, and critical autonomy threshold, are predominantly established under homogeneous data distributions. However, the motivating problem involves clients with different interests, local conditions, and potentially heterogeneous data, making the interaction between autonomy and heterogeneity particularly important. The extension in Sec. 5 and Appendix D considers only a simplified two-group setting, without sufficiently examining more general client-specific distributions or different forms of data heterogeneity commonly encountered in federated learning.

  • Insufficient justification of the critical autonomy threshold. The theoretical interpretation of the critical autonomy threshold requires further clarification. In particular, Proposition 3 establishes the threshold through a mean-field stability condition, but this does not directly demonstrate that the underlying finite-state Markov chain fails to mix. A more rigorous connection between mean-field instability, Markov chain mixing behavior, and learning convergence is needed to substantiate this central claim.

2. Insufficient Empirical Validation and Limited Practical Significance.

The experimental evaluation remains a major limitation, particularly given the paper's emphasis on practical autonomous participation in distributed learning. Although the numerical results illustrate several theoretical predictions, the current evidence is insufficient to establish their broader applicability or practical effectiveness. Several issues are particularly important:

  • Limited experimental scope and external validity. The evaluations in Figures 1–2 and Appendix E primarily rely on numerical simulations constructed around the proposed participation mechanisms and theoretical assumptions. While these results help illustrate the predicted convergence behaviors, they largely examine the internal consistency of the mathematical framework rather than independently validating its applicability to realistic distributed learning environments. The experiments lack representative real-world datasets, practical federated training tasks, and evaluations across diverse forms and degrees of non-IID data. Consequently, it remains unclear whether the reported critical threshold, participation-induced bias, and convergence characteristics generalize beyond the specifically constructed settings.

  • Insufficient comparisons and experimental reproducibility. The paper does not provide systematic comparisons with representative existing client selection or incentive-based approaches, making it difficult to assess the relative benefits of the proposed framework. Furthermore, important experimental details, including the precise learning configurations, participation mechanisms, and statistical variability of the reported results, are not sufficiently consolidated or discussed. These omissions limit the reproducibility of the experiments and make it difficult to evaluate the robustness of the observed phenomena.

  • Limited methodological depth and practical validation of server optimization. The server-side budget optimization in Sec. 4 is developed under a predefined incentive-response function and ultimately reduces to a one-dimensional search over the number of incentivized clients. Although this provides a reasonable application of the theoretical framework, its algorithmic contribution appears relatively limited. More importantly, the paper does not sufficiently demonstrate whether this strategy offers meaningful advantages over alternative budget allocation or client selection approaches in practical distributed training.

Questions for authors
  1. How does the approximation λ2≈μ′(n⋆)\lambda_2 \approx \mu'(n^\star) in Appendix B.9.1 justify the claimed failure of Markov chain mixing at the critical autonomy threshold? Under what conditions is this approximation valid for the finite-state Markov chain?

  2. In Appendix B.5, the proof of Theorem 2 assumes that the expected suboptimality at intermediate rounds is bounded by its initial value. How is this inequality guaranteed under Assumptions 1–3, particularly with stochastic gradient noise?

  3. Although Appendix B.7–B.8 analyzes additional participation mechanisms, how well do the main theoretical findings generalize beyond these predefined rules? Can the authors provide supporting analysis or experiments using alternative, practically motivated participation policies?

  4. In Sec. 5 and Appendix D, the heterogeneous analysis focuses on the target objective F1F_1 rather than the original global objective FF. Does the claimed participation-induced debiasing also improve convergence toward the original global optimum? Evidence under more general non-IID settings would help clarify this issue.

  5. Can the authors provide additional FL experiments on standard datasets (e.g., CIFAR-10/100) with practical models and varying degrees of non-IID data? Please examine whether the critical threshold and participation-induced bias affect actual test accuracy and convergence, and compare the proposed budget optimization with representative baselines under identical budgets. Reporting participation rates and variability across multiple runs would further strengthen the evidence.

3 comments

We thank the reviewer for their constructive feedback and for recognizing the meaningful motivation and systematic theoretical analysis of our work. To address your concerns regarding empirical validation, we have expanded our experiments and clarified the theoretical connections.

Below are the detailed answers to your specific questions:

  1. How does the approximation λ2≈μ′(n∗)\lambda_2\approx\mu'(n^*) in Appendix B.9.1 justify the claimed failure of Markov chain mixing at the critical autonomy threshold? Under what conditions is this approximation valid for the finite-state Markov chain?

This relationship follows from Kurtz's density-dependent Markov process limit theorems and the Linear Noise Approximation (Ethier & Kurtz, 1986, Chapter 11): Under the following conditions this approximation is valid: (i) NcN_c is sufficiently large, (ii) the chain is initialized within the basin of attraction of a hyperbolic fixed point n∗n^* (∣μ′(n∗)∣<1|\mu'(n^*)| < 1), and (iii) n∗n^* is bounded away from the boundary n=0n=0, a first-order Taylor expansion yields the linear autoregressive (discrete Ornstein-Uhlenbeck) process δYr+1≈μ′(n∗)δYr+ξr\delta Y_{r+1} \approx \mu'(n^*) \delta Y_r + \xi_r.

For a linear AR(1) Markov chain, the second largest eigenvalue of the Markov transition operator is exactly its drift contraction rate, λ2=μ′(n∗)\lambda_2 = \mu'(n^*).

As shown in our finite-size scaling analysis (Figure 5), the finite-state Markov chain converges rapidly to this continuous limit as NdN_d increases (Nd≥50N_d \ge 50).

  1. In Appendix B.5, the proof of Theorem 2 assumes that the expected suboptimality at intermediate rounds is bounded by its initial value. How is this inequality guaranteed under Assumptions 1–3, particularly with stochastic gradient noise?

We thank the reviewer for catching this technical detail in Appendix B.5 (Line 825). Because of stochastic gradient variance σ2>0\sigma^2 > 0, $ \mathbb{E}[F(\theta^{(r)}) - F(\theta^*)]$ is not strictly monotonic at every intermediate round. However, the exact same $ \mathcal{O}\left(\frac{1}{\eta \rho_\pi T} + \frac{\eta \sigma^2}{\rho_\pi m_{\text{eff},\pi}} + \frac{\tau_{\text{mix}}}{T}\right)$ convergence bound holds under the following assumption, which we included in the revised Appendix B.5.

Under the standard bounded-iterate assumption already stated in Theorem 5 (E∥θ(r)−θ∗∥2≤D2\mathbb{E}\|\theta^{(r)} - \theta^*\|^2 \le D^2, enforceable via projection onto a ball of radius DD), LL-smoothness immediately guarantees E[F(θ(r))−F(θ∗)]≤L2E∥θ(r)−θ∗∥2≤L2D2\mathbb{E}[F(\theta^{(r)}) - F(\theta^*)] \le \frac{L}{2}\mathbb{E}\|\theta^{(r)} - \theta^*\|^2 \le \frac{L}{2}D^2 for all r≥0r \ge 0, which directly substitutes into Line 825.

  1. Although Appendix B.7–B.8 analyzes additional participation mechanisms, how well do the main theoretical findings generalize beyond these predefined rules? Can the authors provide supporting analysis or experiments using alternative, practically motivated participation policies?

Our core theoretical results (Lemma 1, Theorem 1, and Theorem 2) are completely agnostic to the specific functional form of the participation rule ϕc\phi_c. Theorem 2 applies to any state-dependent participation mechanism as long as the induced Markov chain over Ω=2[Nc]\Omega = 2^{[N_c]} is irreducible and aperiodic (which holds whenever pi(S)∈(0,1)p_i(S) \in (0,1)), characterizing convergence purely through the macroscopic quantities (ρπ,meff,π,τmix)(\rho_\pi, m_{\text{eff},\pi}, \tau_{\text{mix}}).

Across the paper, we already analyze and evaluate four distinct, practically motivated participation mechanisms:

Case 1, Sec.3.5 & Case 2, App.B.7: Clients participate when the active ∣S∣|S| is large to ensure gradient dilution/privacy.

Case 3, App.B.8: Clients follow individual two-state Markov chains with entry/exit rates (ϵ(b),δ(b))(\epsilon(b), \delta(b)) modeling local resource fatigue and recovery.

Sec.4, Eq.~17: Clients respond to server rewards ww via diminishing marginal returns pu(w)=w1+wp_u(w) = \frac{w}{1+w}.

Sec.5 & App.E.3, Eq.69: Clients evaluate model alignment and drop out when their local gradient norm exceeds the active population average.

  1. In Sec. 5 and Appendix D, the heterogeneous analysis focuses on the target objective F1F_1 rather than the original global objective FF. Does the claimed participation-induced debiasing also improve convergence toward the original global optimum? Evidence under more general non-IID settings would help clarify this issue.

Improving convergence toward the original unweighted global objective F(θ)F(\theta) was not the goal of Section 5. On the contrary, our goal in Section 5 is to prove that under heterogeneous data, autonomous participation moves the model away from the global average FF and causes specialization toward a single group's distribution.

To formalize this specialization mathematically, we designate one of the two groups (G1G_1, determined by population majority and model initialization θ(0)\theta^{(0)}) as the reference ``target objective'' F1(θ)F_1(\theta) and measure the model's distance to θ1∗\theta_1^*. Under static participation (b=0b=0), the model converges to the compromised global objective FF, leaving a high steady-state error with respect to F1F_1 proportional to (1−α)2ζ1,2(1-\alpha)^2 \zeta_{1,2}. Under autonomous participation (b>0b>0), clients in G2G_2 experience larger local gradient norms as the model moves toward F1F_1 and consequently drop out. This feedback loop drives α(r)→1\alpha^{(r)} \to 1, eliminating the cross-group interference (1−α)2ζ1,2(1-\alpha)^2 \zeta_{1,2} relative to F1F_1 so the server specializes exclusively in G1G_1 (Figure 2 and Figure 8). We will clarify the phrasing in Section 5 so it is clear that F1F_1 is used as the analytical reference to measure specialization rather than a debiasing of the global objective FF.

  1. Can the authors provide additional FL experiments on standard datasets (e.g., CIFAR-10/100) with practical models and varying degrees of non-IID data? Please examine whether the critical threshold and participation-induced bias affect actual test accuracy and convergence, and compare the proposed budget optimization with representative baselines under identical budgets. Reporting participation rates and variability across multiple runs would further strengthen the evidence.

We have added a new set of experiments on CIFAR-10 using a CNN across Nc=50N_c = 50 clients (reporting mean ±\pm std across 5 random seeds) in Appendix E.4.

Impact of bcriticalb_{\text{critical}} on Test Accuracy (Case 1): Consistent with Proposition 3, when client autonomy is below the critical threshold (b=13<bcritical≈14b=13 < b_{\text{critical}} \approx 14), active participation stays high (ρπ=0.995\rho_\pi = 0.995, Mean ∣S∣=13.54|S| = 13.54), yielding stable convergence and a test accuracy of 49.60±1.17%49.60 \pm 1.17\%. Once bb crosses the threshold (b=16b=16), the autonomous clients drop out. The active cohort collapses to the uniform baseline (Mean ∣S∣=2.12|S| = 2.12), starving the effective sample size meff,πm_{\text{eff},\pi}. As predicted by Theorem 2, this inflates gradient variance, dropping accuracy to 42.28%42.28\% and exploding run-to-run variability to ±4.45%\pm 4.45\%.

Participation-Induced Specialization (Non-IID): Under heterogeneous splits (60/40 majority/minority label skew), static participation (b=0b=0) traps the model at a compromised global average (α(r)≈0.606\alpha^{(r)} \approx 0.606), yielding a high target-error floor (Target G1G_1 Acc: 47.81±3.60%47.81 \pm 3.60\%). However, autonomous gradient-norm dropout (b=5b=5) triggers the predicted feedback loop, driving the target participation ratio α(r)→0.997\alpha^{(r)} \to 0.997. By purging conflicting gradients, this specialization eliminates the cross-group bias relative to F1F_1, boosting Target G1G_1 accuracy to 54.99±1.71%54.99 \pm 1.71\%.

Server Budget Optimization Baselines (Sec. 4): Note that Algorithm 1 optimizes the Markov chain metrics (ρπ,meff,π,τmix)(\rho_\pi, m_{\text{eff},\pi}, \tau_{\text{mix}}) which depend only on the client population dynamics, independent of the dataset. Comparing Algorithm 1 (Nu∗=29,w∗=0.14N_u^* = 29, w^* = 0.14) against equal-budget baselines in Figure 6, Uniform Full-Spread (Nu=50,w=0.08N_u = 50, w = 0.08) and Concentrated Top-kk (Nu=4,w=1.0N_u = 4, w = 1.0), demonstrates that Algorithm 1 strictly minimizes steady-state error by balancing sample starvation against mixing delays.

Thank you for the detailed rebuttal and additional experiments. I have read the revised manuscript and appreciate the authors' efforts. Some of my concerns have been partially addressed, particularly through the theoretical clarifications and new CIFAR-10 results. However, I still share the concerns about experimental validation raised by other reviewers. More evaluations using established FL benchmarks and stronger baselines are needed to show how well the findings work in practice, especially the proposed budget optimization. I also value the extensive theoretical analysis, but it mainly focuses on homogeneous data, while real-world FL often involves much more complex non-IID settings. The heterogeneous analysis remains limited to a simplified two-group model, making it hard to judge how well the conclusions generalize. After considering the rebuttal and revisions, I feel these two main concerns remain unresolved, so I will maintain my original rating.

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

This paper considers the standard Distributed Optimization (DO) with several clients to minimise a global objective. Clients perform one step of gradient descent on their local objective and a server aggregates the updates and keep a global model. The main novelty of the work is the freedom of clients to choose whether or not participate in a specific round depending on their own preference. This is in contrast to common DO setting in which server selects a set of active clients for each round instead of clients having agency of their own. Authors consider both homogeneous and heterogeneous regimes and provide convergence guarantee for GD in this distributed setting (Theorem 2 and Theorem 5). Authors use Markov chain to model the client participation and show if the autonomy of clients reaches a certain threshold, the system will collapse and we cannot minimize the global objective. In the extreme case, it is possible that no client participates.

Critical strengths

The setting is interesting on its own. The fact that clients should be able to decide on their own in order to participate or not in a round sounds reasonable and practical. The use of Markov chain and probabilistic point of view for client participation is good.

Critical weaknesses

The paper is poorly written and lacks clear discussion and formulation. There are too many confusing notations with subscript and superscript that made it very difficult to read the paper. Results are not well discussed and a clear comparison with some relative works and other rates is missing. Moreover, it seems paper considers the setting in which each client only takes one local steps and decides whether to communicate or not. This is far less interesting than the common federated setting in which clients are allowed to take several steps and then communicate. If we assume we just take one local steps, this setting resembles mini-batch SGD with batch size = number of active clients. Since paper assumes it can be the case that no client participates, it is similar to running mini-batch GD with delayed gradient which is a well-known topic (or asynchronous GD). So a clear comparison is needed with these similar works.

Questions for authors
  1. Why in Theorem 2 and Theorem 5 where convergence rate is stated, the step size is not tuned and just left as it is? Authors should have optimised and chose the best possible step size and replace it in the final theorem.
  2. If no client participates, why should server even do an update? if it does not do an update, then what is the difference with GD with delayed gradient or asynchronous GD?
  3. The critical threshold (eq 15) is very hard to understand and unintuitive. Can authors provide more intuitive explanation for it?
2 comments

We thank the reviewer for finding our autonomous setting interesting and practical, and for appreciating the probabilistic Markov chain approach. Below are the detailed answers to your specific questions:

  1. Why in Theorem 2 and Theorem 5 where convergence rate is stated, the step size is not tuned and just left as it is? Authors should have optimised and chose the best possible step size and replace it in the final theorem.

    We kept η≤12L\eta \le \frac{1}{2L} (Theorem 2) and η≤14L\eta \le \frac{1}{4L} (Theorem 5) explicit in the main theorem statements so that the three distinct physical mechanisms: (1) initialization decay ∝1ηρπT\propto \frac{1}{\eta \rho_\pi T}, (2) steady-state stochastic variance ∝ησ2ρπmeff,π\propto \frac{\eta \sigma^2}{\rho_\pi m_{\text{eff},\pi}}, and (3) Markov mixing transient error ∝τmixTρπ\propto \frac{\tau_{\text{mix}}}{T \rho_\pi}, remain transparent for the constant-step-size regime used in Section 4's server policy optimization. We added to the revised paper the corresponding Corollaries 1 and 2 about the tuned step size for Theorem 2 and 5.

  2. If no client participates, why should server even do an update? if it does not do an update, then what is the difference with GD with delayed gradient or asynchronous GD?

When no client participates (∣S(r+1)∣=0|\mathcal{S}^{(r+1)}|=0), the server does not modify the model: as written in Section 3.2 (Line 181), the indicator I(r+1)=1∣S(r+1)∣>0=0\mathbb{I}^{(r+1)} = \mathbf{1}_{\\{\vert{}\mathcal{S}^{(r+1)}|>0\\}} = 0 yields θ(r+1)=θ(r)\theta^{(r+1)} = \theta^{(r)}. However, communication round r+1r+1 still elapses in system time because the server broadcast θ(r)\theta^{(r)} and waited for the round timeout.

In delayed-gradient or asynchronous GD, workers compute gradients on an older model θ(r−τ)\theta^{(r-\tau)} and those stale gradients eventually arrive at round rr, introducing a staleness bias ∇F(θ(r−τ))−∇F(θ(r))\nabla F(\theta^{(r-\tau)}) - \nabla F(\theta^{(r)}). In our autonomous setting, non-participating clients never compute or transmit an update for round rr. There is no gradient staleness, but rather a dynamic loss of active rounds (ρπ<1\rho_\pi < 1) and sample size starvation (meff,πm_{\text{eff},\pi}).

  1. The critical threshold (eq 15) is very hard to understand and unintuitive. Can authors provide more intuitive explanation for it?

Intuitively, bcriticalb_{\text{critical}} represents a tipping point in a positive feedback loop. In Case 1, autonomous clients prefer to participate when the active set size nn is large (e.g., for stronger gradient dilution/privacy or better global model utility). If participation drops slightly in round rr, autonomous clients become more reluctant in round r+1r+1, which further shrinks the active set in subsequent rounds.

Mathematically, μ(n)=Ndpd(n)+Nupu\mu(n) = N_d p_d(n) + N_u p_u is the expected number of participants in the next round given nn participants of the current round. Its derivative μ′(n∗)\mu'(n^*) measures the sensitivity of the crowd: if one client drops out at this round, μ′(n∗)\mu'(n^*) is the expected number of autonomous clients that drop out in response in the next round. As long as μ′(n∗)<1\mu'(n^*) < 1, perturbations dampen out and the system is self-correcting. At b=bcriticalb = b_{\text{critical}} (Eq.15), the feedback sensitivity reaches μ′(n∗)=1\mu'(n^*) = 1: a single client's dropout triggers a self-reinforcing cascade where all NdN_d autonomous clients abandon the system, leaving only the uniform baseline NuN_u.

Each factor in Eq.(15), bcritical=x(1−x/Nd)[ln⁡(Nd/x−1)]2b_{\text{critical}} = x(1 - x/N_d)[\ln(N_d/x - 1)]^2, has a physical interpretation at the equilibrium autonomous turnout x=Ndpd(n∗)x = N_d p_d(n^*):

x(1−x/Nd)=Ndpd(n∗)(1−pd(n∗))x(1 - x/N_d) = N_d p_d(n^*)(1 - p_d(n^*)) is the responsiveness of the autonomous population. The crowd is most sensitive to state changes when pd(n∗)p_d(n^*) is neither near 00 nor near 11.

ln⁡(Nd/x−1)=b/n∗\ln(N_d/x - 1) = b / n^* is the the effective barrier to entry at equilibrium.

Thank you for the reply. I still think the paper needs substantial work and in the current form the contribution is not clear. Th experiments section and comparison with relevant results and rates on asynchronous methods or distributed methods with local steps are missing. Therefore I will maintain my score.

Reviewer_oAP9OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper revisits client-driven autonomous participation in distributed machine learning, including federated learning, by modeling such state-dependent client participation as a Markov chain. To make this chain mix and the distributed learning converge, the authors define and argue that the autonomy should obey a so-called critical threshold. Further, several practical constraints are also considered, e.g., clients dropout and incentivization as a budget allocation.

Critical strengths

The authors proposed the critical autonomy threshold, which acts as the touchstone of the validity of autonomous client participation in FL.

Critical weaknesses
  • The overall presentation is not well-organized and confusing.
    • Even though the proposed method assumes a single central server setting, literature on multiple-server setting is cited and mentioned in the first section, which imprints that the proposed method is about multiple server, or hierarchical FL settings.
    • It is hard to parse sections 3 and 4, which are the main bodies of the manuscript. It reads each section is not streamlined with previous and subsequent (sub)sections. For example, I expected the justification of using Markovian dynamics model before jumping into section 3.3, but there is none.
    • If the autonomy in participation truly holds, why should we assume shared probabilities (L209) for participation decisions?
    • Even though the critical autnomy threshold is the main contribution, it doesn't appear until page 6 (L320)
  • Missing important branches of prior arts.
    • While there are several direct precursors that allow autonomous participation both in homogeneous and heterogeneous settings, these are neither cited nor compared or analyzed in experiments or theoretical analyses. (cf. [1, 2])
    • Furthermore, it is closely connected to asynchronous federated learning, in that client participation is not orchestrated by the server. However, the manuscript does not mention this relationship.
    • For example, those classifications into cases 1 to 3 are already predominant in asynchronous FL or client participation literature, too. (cf. [3, 4])
  • No empirical validation
    • While the authors appealed the need of autonomous participation, no empirical results on real-world FL benchmark datasets are provided. (e.g., LEAF, FLamby, or the ones prepared in TensorFlowFederated)
  • Deviations from practical feasibility
    • It assumes local gradients, instead of local parameters, which is not aligned with the communication efficiency of typical federated learning algorithms.
    • The stability of the budget algorithm holds only inside the assumed logistic participation response model with known or accurately estimated transition dynamics, which seems barely true in highly autonomous networks.

References

    1. On-Demand Federated Learning for Arbitrary Target Class Distributions (AISTATS 2024)
    1. Incentive-Aware Autonomous Client Participation in Federated Learning (IEEE TPDS 2022)
    1. TimelyFL: Heterogeneity-aware Asynchronous Federated Learning with Adaptive Partial Training (CVPRW 2023)
    1. Decentralized Federated Averaging via Random Walk (arXiv 2024)
    1. Asynchronous Wireless Federated Learning with Probabilistic Client Selection (IEEE TWC 2023)
Questions for authors
  • Please consider citing asynchronous federated learning, incentivized federated learning, and on-demand federated learning as precursors, and compare the proposed method with them, both empirically and operationally.
  • Should all of each client maintain all previous history krk^r, to determine the participation? If so, it would require sheer amount of computational complexity, which degrades the practicality of the proposed method.
  • What is the relationship with the reference (Sinitsin et al., 2020) and the client history?
  • Under unequal sample counts across clients, isn't the standard uniform averaging in the aggregation introducing biases, compared to weighted average?
  • It seems that Theorem 2 becomes non-informative whenever ρπ\rho_{\pi}} is too small or when τmix\tau_{mix} cannot be made small. Can we justify that one can avoid these degenerate cases in practice? Please provide with convincing settings and examples.
2 comments

We thank the reviewer for their valuable feedback. To address the concerns regarding empirical validation, we have added new experiments on the CIFAR-10 dataset (Appendix E.4) to practically demonstrate the critical autonomy threshold and the participation-induced specialization.

Below are the answers to your specific questions:

  1. Please consider citing asynchronous federated learning, incentivized federated learning, and on-demand federated learning as precursors, and compare the proposed method with them, both empirically and operationally.

    Asynchronous FL address unorchestrated updates caused by hardware stragglers, channel fading, or graph topology, where stale updates eventually arrive. In our setting, non-participation is an autonomous strategic dropout (the update is never computed or sent), and empty rounds (∣S(r+1)∣=0\vert{}\mathcal{S}^{(r+1)}\vert{}=0) arise endogenously from self-interested feedback loops rather than physical link delays. Incentivized and On-Demand FL typically model client participation via static one-shot game-theoretic equilibria or server-side subset querying to match a target distribution. In contrast, our framework models state-dependent, temporally correlated Markovian dynamics, where clients autonomously react to evolving system states across rounds, revealing a dynamic phase transition (bcriticalb_{\text{critical}}) where the Markov chain fails to mix.

  2. Should all of each client maintain all previous history krk^r, to determine the participation? If so, it would require sheer amount of computational complexity, which degrades the practicality of the proposed method.

    No, in Section 2 we defined the general system history F(r)\mathcal{F}^{(r)} and the personal histories hiri=1Nc\\{h_i^r\\}_{i=1}^{N_c} to keep the framework general. But in our concrete Markovian participation models in Sections 3,4 and 5 the complexity is O(1)\mathcal{O}(1) in memory and compute. For example, cases 1 and 2 requires a single scalar from previous round (∣S(r)∣\vert{}\mathcal{S}^{(r)}\vert{}).

  3. What is the relationship with the reference (Sinitsin et al., 2020) and the client history?

    Sinitsin et al. (2020) (Editable Neural Networks) was cited in Section 2 (line 118) as an example of how in modern LLM a client's local update could represent local model edits rather than standard SGD gradients.

  4. Under unequal sample counts across clients, isn't the standard uniform averaging in the aggregation introducing biases, compared to weighted average?

    Under homogeneous data ($ \mathcal{D}_i = \mathcal{D}$), the standard uniform averaging is unbiased as we shown in Lemma 1. Under heterogeneous data, it introduces a steady-state convergence bias proportional to (1−α)2ζ1,2(1-\alpha)^2 \zeta_{1,2}, as explained in Section 5.

  5. It seems that Theorem 2 becomes non-informative whenever ρπ\rho_{\pi} is too small or when τmix\tau_{\text{mix}} cannot be made small. Can we justify that one can avoid these degenerate cases in practice? Please provide with convincing settings and examples.

    This observation is exactly the point of the critical autonomy threshold we defined. When b>bcriticalb > b_{\text{critical}}, ρπ\rho_\pi and meff,πm_{\text{eff},\pi} are too small, which causes the bound to degrade. In practice, we show how the server can avoid this case by optimizing its incentives policy in Section 4. When autonomous clients have high bb, the server deploys a limited budget BB to incentivize a stabilizing uniform subset Nu∗N_u^{*} (Algorithm 1). As shown in Proposition 3 and Figure 6, allocating incentives to maintain Nupu>xln⁡(Nd/x)−xN_u p_u > x \ln(N_d/x) - x shifts the Markov chain away from the collapse threshold, guaranteeing ρπ≈1\rho_\pi \approx 1 and a large meff,πm_{\text{eff},\pi} (e.g., Nu∗=29N_u^{*} = 29 in Figure 6 achieves ρπ>0.99\rho_\pi > 0.99 and keeps the steady-state error low).

Thank you for your responses. While some addressed my concerns, the manuscript still needs further refinement. Furthermore, in the absence of empirical validation and compelling practical motivation, I would maintain my original score.

  1. I found that the on-demand FL aligns with the assumed setting of this manuscript, in which clients autonomously decide whether or not to participate for the sake of their own utility. Additionally, the practical motivation behind using Markovian dynamics in modeling is not fully understood. Even in the case that clients act in an adversarial manner to maximize their gain, it becomes still important to consider the impact of their actions on the previous FL history. Please note that this issue (i.e., adversarial and greedy clients) is related to the previously mentioned incentivized FL, too. In the abstract, the authors also mentioned that "the parameter server can incentivize the participation of a uniform set of clients using a limited budget." For this reason, I requested that they be cited. In the absence of a clear distinction, the contribution may be perceived as vague.
  2. While it is interesting, I believe that it should also be empirically demonstrated, at least using a widely-used FL benchmark (e.g., [1-3]).
  3. I couldn't find LLM-relevant claims or experiments in the manuscript. That's why I found it seemed out of context. Please consider polishing the manuscript accordingly.

Reference

  1. LEAF: A Benchmark for Federated Settings.
  2. FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings.
  3. https://www.tensorflow.org/federated/api_docs/python/tff/simulation/datasets

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.