acceptodds
Under review as a conference paper at ICLR 2027

Understanding Generalization in Client-Level DP-FL: A Hierarchical Stability Analysis

Abstract

Differentially private federated learning (DP-FL) has been extensively studied for privacy and optimization, while its generalization remains less understood. Since data in FL are organized at the client and local-sample levels, they give rise to within-client and unseen-client generalization. We develop a hierarchical distributional-stability framework for client-level DP-FL based on sample- and client-replacement stability, revealing that the heterogeneity term explicitly enters the unseen-client generalization bound, whereas local dataset size explicitly governs the within-client generalization bound. Using total variation (TV) distance and KL divergence, we derive complementary generalization guarantees: the TV-based bound exhibits a tighter dependence on the client participation ratio, whereas the KL-based bound exhibits a tighter dependence on the training horizon. Furthermore, under suitable learning-rate decay, the KL-based bound can remain independent of the training horizon without requiring a finite cumulative step size. Combining these generalization guarantees with optimization analysis, we derive population excess-risk bounds that characterize the optimization-generalization trade-off induced by privacy, training dynamics, and heterogeneity. Experiments across multiple datasets empirically support the hierarchical decomposition and the main theoretical predictions.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Differentially private federated learning, Stability-based generalization, Hierarchical generalization

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_U5CAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper develops a hierarchical distributional-stability analysis to understand the generalization on the general DP-FL framework. It constructs two terms to learn both sample- and client-replacement stability, leading to the final global generalization bound. The assumptions and theorems are aligned with the previous studies. Several experiments are conducted to validate the trends of the analysis in this paper.

Critical strengths
  1. The paper addresses the relatively underexplored problem of generalization in client-level DP-FL. Its formulation provides a useful finding between within-client and unseen-client generalization.

  2. The KL-based analysis is a useful contribution. Although the derivation is relatively straightforward, replacing the accumulation of learning rates with that of their squares yields an improved dependence on the training horizon.

Critical weaknesses
  1. The analysis relies on globally bounded losses and potentially loose relaxations, without characterizing the tightness of the resulting bounds. These limitations weaken its practical relevance, particularly because the experiments use cross-entropy loss, which does not satisfy the global boundedness assumption.

  2. The compatibility between horizon-independent generalization and optimization is insufficiently discussed. Corollary 1 considers decaying learning rates, whereas Corollary 3 assumes a constant learning rate. Moreover, the horizon-independent result relies on a fixed per-round noise scale. The paper should clarify which learning-rate and noise schedules provide meaningful simultaneous optimization and generalization guarantees.

  3. The practical informativeness of the bounds remains unclear. The outer truncation in Eq. (5) may reduce the guarantee to the trivial bounded-loss bound. Without representative numerical evaluations, it is difficult to assess whether the theoretical dependencies provide informative guarantees under the experimental settings.

Questions for authors
  1. What is the precise role of assuming that client distributions are independently sampled from a common meta-distribution Π? Please distinguish the results that rely on this assumption from those that remain valid for fixed, heterogeneous client distributions. Usually we only assume Pi≠PjP_i\neq P_j. An overall distribution Π\Pi may be more strong assumption here.

  2. In Eqs. (10) and (11), the noise contribution suppresses an inverse dependence on the learning rate η that appears explicitly in the appendix. Could the authors retain this dependence and explain how the optimization–generalization trade-off changes with the choice of learning rate?

  3. Can the bounded-loss assumption be relaxed, for example under suitable moment or tail conditions? Alternatively, please clarify how the current guarantees relate to the cross-entropy experiments.

  4. Under what parameter regimes do the bounds improve upon the trivial bounded-loss guarantee? Please provide representative values or justified estimates of the theoretical constants and evaluate whether these regimes cover the experimental settings.

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

This paper studies generalization of client-level DP-FL through distributional stability. It decomposes the total generalization error into unseen-client and within-client errors. These errors are upper-bounded by client-replacement and sample-replacement stability, respectively. Using total variation (TV) and KL divergence with Gaussian noise, the authors derive two bounds: the TV-based bound and the KL-based bound. In particular, TV-based bound is tighter in the client participation ratio (m/M) and the KL-based bound is tighter in the horizon T. In addition, KL-based bound becomes T-independent under learning-rate decay with large decay rate aa (a>0.5a>0.5). Experiments with LeNet on FEMNIST, Fashion-MNIST and CIFAR-10 are used to illustrate these theoretical results.

Critical strengths
  1. The paper splits FL generalization error into unseen-client generalization error and within-client generalization error, providing a more detailed view to the FL data-generating process than a single generalization error.

  2. Providing the insight that the convergence of \sum \eta_t^2, rather than \sum\eta_t results in O(1) KL-based generalization error. This convergence condition is more practically relevant in FL.

  3. The horizon-independence claims are tested through two separate mechanisms (learning rate decay and a fixed privacy budget).

Critical weaknesses
  1. The claim of horizon independence is weakened by the optimization cost in Eq. (1) because when the decay rate gets lager (i.e., for larger a), the optimization cost becomes the dominant term even though the generalization error is O(1).

  2. The comparison in Remark 1 is not rigorous. Remark 1 compares one factor in these two bounds at a time, which does not indicate which bound is tighter overall. For instance, the upper bounds of TV-based and KL-based generalization errors can be written as Bound_{TV}<=(m/M)*\sum \eta e^{\eta\beta\tau}Const_1 and Bound_{KL} <=\sqrt{m/M}\sqrt{\sum \eta^2 e^{2\eta\beta\tau}}*Const_2, respectively. The relations (m/M)<=\sqrt{m/M} and \sum \eta e^{\eta\beta\tau} >= \sqrt{\sum \eta^2 e^{2\eta\beta\tau}} do not provide information about which bound is tighter.

  3. Moreover, Bound_{TV}/Bound_{KL} \approx \sqrt{2/ \pi} \sqrt{T*m/M}, indicating that Bound_{TV} is tighter only if T<=M/m (Corollary 2 also shows this). This suggests that Bound}_{KL} is always tighter in typical practical scenarios (e.g., in the experiments, M/m=10 and T=2000).

  4. The reasons for choosing the experimental settings are not clearly stated. Moreover, the randomness caused by unseen data and unseen clients has impacts on the experimental results, which should therefore be discussed in detail.

Questions for authors

1.Can a finer analysis of the KL-based bound improve the \sqrt{m/M} dependence? If so, please drive an uniform upper bound for Gamma_c and Gamma_s. 2.For a decaying \eta_t, please give the complete excess-risk bound including the optimization error. This could be more useful in deciding corresponding hyper-parameters. 3.The results of Corollary 3 are only qualitatively analyzed. Further quantitative analysis of these results can yield deeper insights into DP-FL training and effectively improve the overall quality of this work. 4.Experiments on diverse model architectures and more complex datasets can further enhance the credibility of the experimental results. 5. Randomness of the unseen client and unseen data should be discussed in detail in the experiments. 6. Proposition 1 is placed in the appendix. Since Corollary 3 references this proposition, the main text is not self-contained as a result. 7. The statements that “the KL-based bound exhibits a tighter dependence on the training horizon” and “the KL-based bound can remain independent of the training horizon” are ambiguous and confusing, and should be rephrased.

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

This paper studies hierarchical generalization in client-level DP-FL, using client- and sample-replacement stability to bound unseen-client and within-client generalization, respectively. It derives complementary TV- and KL-based bounds with explicit dependencies on heterogeneity and local dataset size. The KL analysis yields a horizon-independent relaxed bound under square-summable learning rates, including non-summable schedules. The paper further considers privacy-calibrated noise and establishes an excess-risk bound under an additional PL condition. Experiments on three image datasets qualitatively support several predicted trends, but lack uncertainty estimates and numerical evaluation of the bounds.

Critical strengths
  1. The paper presents a coherent hierarchical stability framework linking client- and sample-replacement stability to unseen-client and within-client generalization, respectively. The bounds reveal distinct explicit dependencies on gradient heterogeneity and local dataset size, providing more diagnostic insight than a single aggregate bound.

  2. The TV and KL bounds offer complementary participation-rate and horizon dependencies. The KL analysis yields a horizon-independent relaxed bound for learning rates �0�with�1��0� with �1�, including non-summable schedules when a≤1a\leq1. The analysis incorporates sampling, local updates, clipping, and noise, with experiments probing these factors.

Critical weaknesses
  1. The privacy guarantee requires clarification of the mechanism under add/remove adjacency, the sufficient calibration conditions for Equation (8), and the experimental accountant configuration. These omissions weaken Corollary 2’s privacy premise, though not necessarily the stability bounds.

  2. Ordinary cross-entropy violates the globally bounded-loss assumption, and update clipping does not resolve this mismatch. The additional expected PL condition required for the excess-risk result is also not justified for the experiments.

  3. The experiments lack repeated-run uncertainty and numerical bound evaluations. Short-horizon learning-rate comparisons also confound smaller generalization gaps with higher training loss, limiting support for the horizon-independence claims.

Questions for authors
  1. How is Algorithm 1 defined under add/remove client adjacency with fixed-size sampling, and what precise privacy-calibration conditions justify Equation (8)? Please specify the accountant configuration, calibrated noise multipliers for Figure 5, and achieved privacy budgets for the remaining experiments.

  2. Can you report both generalization components with uncertainty across independent runs, alongside numerical TV/KL bounds in a setting satisfying the assumptions? Comparisons across participation rates, horizons, and decay exponents would help assess the claimed distinctions, with training-loss-matched comparisons for the learning-rate decay experiments where feasible.

  3. How do the cross-entropy experiments relate to the bounded-loss and smoothness assumptions, and what supports the additional trajectory-wise expected PL condition used for the excess-risk result? Which parameters are hidden in Equations (10)–(11), particularly the dimension and learning-rate dependencies retained in Proposition 1?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.