acceptodds
Under review as a conference paper at ICLR 2027

Two-Level Normalization for Federated Optimization under Generalized Smoothness

Abstract

We study federated optimization with two-level normalization: clients perform normalized stochastic local updates, and the server applies a normalized update along the aggregated client displacement. This structure is natural under generalized -smoothness, where gradient magnitudes may be large and classical smoothness-based FedAvg analyses do not directly apply. The main difficulty is that exact normalization introduces a bias: the server direction is no longer an unbiased gradient estimate, and the bias depends on the dispersion of stochastic gradient norms within a communication round. We make this effect explicit through a norm-dispersion parameter . Under standard stochastic-noise and heterogeneity assumptions, we prove two-phase optimization rates up to an explicit error floor with client-and-step averaging of the stochastic term. In the non-convex setting, the rate contains both the standard sublinear component and an improved generalized-smoothness component. In the convex setting, we derive both sublinear and linear optimization behavior, up to the same bias/noise floor. We further extend the guarantees to mini-batching, partial participation, and heavy-tailed local stochastic noise, showing how batching and participation reduce stochastic and sampling-heterogeneity terms while the normalization-bias term remains explicit.

Primary area:
optimization
Keywords:
Two-Level Normalization, Federated Optimization, Generalized Smoothness

Reviews

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

In previous works, the theories on convergence of FL methods did not cover the case where the gradients are large and local smoothness grows with the gradient norm. This paper covers such a case for FedAvg with two-level normalization. The main technical challenge was how to treat the bias induced by normalization, and the paper handled this using Assumption 2.5. The paper showed convergence for various cases, and empirically showed that server-side normalization can improve the test performance of FL methods.

Critical strengths
  • The paper successfully handled convergence under the generalized assumption on smoothness. The paper proposes a new framework to analyze a new problem of normalization, which is nice.
  • Extensive experimental results add motivation for this paper, on why normalization technique should be used for FL methods.
Critical weaknesses
  • While the paper analyzes the convergence of two-level normalization FL, I do not see theoretical gains of normalization, especially the server-side normalization. I see that the paper empirically observes the benefits of server-side normalization, but I think the benefits should be reflected inside the theories. As the paper acknowledges, normalization can make the estimation biased and affect the convergence, which is shown as the term δ\delta in Theorem 3.1. But the term shows why the bias is harmful, not why server-side normalization is beneficial. Ideally, the paper should show two convergence rates respectively on the case with and without normalization. That was the most intriguing point of the paper, but unfortunately, I could not see such things.
  • While the assumption on smoothness is generalized, other assumptions such as Assumption 2.5 are strong. Considering that the paper focuses on the case where the gradient norm explodes, the norms of the gradients are not properly reflected in Assumption 2.5, etc. Especially on Assumption 2.5, the paper explains the motivation for it but I still think the assumptions should consider more on the gradient norms.
  • The main experiments in the main body of the paper lack the comparison with original FedAvg, which would be what most people are interested in. I see that Figure 7 shows the comparison of results with and without two-level normalization, but the performance gap between local-only normalization and two-level normalization is not large. Strangely, the test performance seems too low for ResNet-18 and CIFAR-10. CIFAR-10 integrates a relatively easy task, and I see from another paper that FedAvg can achieve 75% test accuracy even with a small CNN [1]. I understand that the performance can be varied in FL depending on the experimental settings, therefore I think the problem of the experiments is "minor". But I still think the experiments should be done under the best settings. Validation accuracies in Table 2 are also strangely low, which makes me wonder if the experimental settings were fair.

[1] Li, Yuhang, et al. "One arrow, two hawks: Sharpness-aware minimization for federated learning via global model trajectory." Forty-second International Conference on Machine Learning. 2025.

Questions for authors
  • Could you show the performance of original FedAvg for FLAIR and FEMNIST?
  • What part of the theorems shows the benefits of normalization, especially the server-side normalization?
  • What were the experimental settings of Figure 7 that could be the reason for low test peformance of FL methods?
3 comments

Dear Reviewer jkPF,

Thank you for recognizing the value of our framework under generalized smoothness. We retain the original problem setting, Algorithm 1, and core theoretical contribution; the additions directly address your questions.

While the paper analyzes the convergence of two-level normalization FL, I do not see theoretical gains of normalization, especially the server-side normalization. I see that the paper empirically observes the benefits of server-side normalization, but I think the benefits should be reflected inside the theories. As the paper acknowledges, normalization can make the estimation biased and affect the convergence, which is shown as the term δ\delta in Theorem 3.1. But the term shows why the bias is harmful, not why server-side normalization is beneficial. Ideally, the paper should show two convergence rates respectively on the case with and without normalization. That was the most intriguing point of the paper, but unfortunately, I could not see such things.

We added precisely this comparison in Theorems G.7 and G.2, keeping the normalized local updates the same. Without server normalization, the guarantee controls stationarity weighted by the aggregate length rt=∣∣Δt∣∣/(Kηloc)r_t=||\Delta_t||/(K\eta_{\mathrm{loc}}); with server normalization, it controls unweighted stationarity. Each bound uses its own trajectory. This identifies the aggregate-length attenuation removed by the server step. To also compare actual losses, Proposition G.8 proves a strict advantage over independently optimized local-only and FedAvg steps in a stochastic quadratic example with K=B=1K=B=1, with coefficients chosen before the current samples.

While the assumption on smoothness is generalized, other assumptions such as Assumption 2.5 are strong. Considering that the paper focuses on the case where the gradient norm explodes, the norms of the gradients are not properly reflected in Assumption 2.5, etc. Especially on Assumption 2.5, the paper explains the motivation for it but I still think the assumptions should consider more on the gradient norms.

The added analysis distinguishes large gradient magnitudes from distortion of their aggregate direction. Specifically, Theorem G.2 uses the sharper directional residual δ^tdir=min⁡a≥0∣∣gˉt−aut∣∣\widehat\delta_t^{\mathrm{dir}}=\min_{a\geq0}||\bar g_t-au_t|| without Assumption 2.5. Positively collinear gradients may have arbitrarily different norms while this residual is zero, so large norm variation is compatible with informative guarantees. Theorem I.1 develops this further under relative oracle moments and client dissimilarity: conditions (54)–(55) yield arbitrary expected stationarity accuracy for fixed KK with an accuracy-independent sufficient batch.

The main experiments in the main body of the paper lack the comparison with original FedAvg, which would be what most people are interested in. I see that Figure 7 shows the comparison of results with and without two-level normalization, but the performance gap between local-only normalization and two-level normalization is not large. Strangely, the test performance seems too low for ResNet-18 and CIFAR-10. CIFAR-10 integrates a relatively easy task, and I see from another paper that FedAvg can achieve 75% test accuracy even with a small CNN [1]. I understand that the performance can be varied in FL depending on the experimental settings, therefore I think the problem of the experiments is "minor". But I still think the experiments should be done under the best settings. Validation accuracies in Table 2 are also strangely low, which makes me wonder if the experimental settings were fair.

To supply the requested baselines, we added FedAvg comparisons in Appendix J.1, Figure 10 and Table 5, using 40 paired evaluation seeds. The values below are validation accuracy and AP, respectively:

TaskFedAvgLocal-onlyTwo-level
FEMNIST, 240 rounds, K=597.3198.1798.29
FLAIR, 60 rounds, K=549.1849.9950.29

The FLAIR FedAvg runs use different aggregation weights and tuning budgets. To isolate the second normalization level, the local-only/two-level comparison matches both weighting and tuning; it gives +0.305+0.305 AP points, with 95% CI [0.094,0.519][0.094,0.519].

To clarify the earlier measurements, Figure 7 uses a stress-test protocol multiplying gradients by 2020 with probability 0.10.1, while Table 2 reports validation values from 40-round parameter selection, before 240-round testing. We complemented this protocol with 1,000-round clean CIFAR-10 runs in Appendix J.2. FedAvg reaches 78.90% IID and 75.67% non-IID, outperforming two-level in this regime. These additional runs provide a strong clean-data reference alongside the scale-outlier experiment.

(Part 1/2)

Could you show the performance of original FedAvg for FLAIR and FEMNIST?

See the FLAIR/FEMNIST results above (Appendix J.1, Figure 10 and Table 5).

What part of the theorems shows the benefits of normalization, especially the server-side normalization?

See the first response above (Theorems G.7 and G.2, and Proposition G.8).

What were the experimental settings of Figure 7 that could be the reason for low test peformance of FL methods?

See the experimental protocols above (Appendices A.4 and J.2).

We believe the added comparisons and controls resolve your central concerns and strengthen the original contribution. We would be grateful if you would reconsider your rating in support of acceptance.

Best regards,
The Authors

(Part 2/2)

Thank you for the detailed revision which tries to address my concerns. However, by the quite late reply of the authors, I don't have much time to parse the long revision of the manuscript; I also think that the main results should be the results of Appendix G rather than the current version, which would need quite a substantial revision. I strongly recommend re-submission to other top-tier venues, since I still think that the paper has some values.

Below shows the reason why I think it needs a substantial revision:

(i) As far as I've read, rminr_{min} controls the difference between local-only normalization and server-side normalization, right? If rminr_{min} is small then local-only would be worse, but how does one lower-bound rminr_{min}? Most FL works assume a very small learning rate, which would result in large rtr_t. An experiment would be necessary to assess how rtr_t truly controls the benefits of server-side normalization.

(ii) I am not convinced by the role of δ\delta as pointed out by other reviewers. Isn't normalization technique devised for the case where the δ\delta is large (I am not fully convinced by it, so correct me if I am wrong)? This limitation is still not addressed in the current version of the manuscript.

(iii) Clean CIFAR-10 experiments in Appendix J shows that two-level normalization is not beneficial. This might be the correct results, since δ\delta might not interrupt the convergence error. Also, I think the main experiments should be done in such clean and practical settings; elsewise, the results would be non-generalizable and impractical.

Still, I think the paper has some values including the contribution on the generalized smoothness assumptions. But I think that (i) the limitation on δ\delta should be addressed and (ii) Appendix G should be the main results, both of which would need a substantial revision (which is already true in the current version). I highly recommend re-submission of this paper to other top-tier venues, which would value the theoretical contributions of this paper.

Reviewer_bBsaOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies two-level normalization for federated optimization under generalized (L0,L1)(L_0,L_1)-smoothness. The method normalizes both local stochastic gradients and aggregated server updates. The authors establish convergence guarantees for non-convex and convex objectives, explicitly accounting for normalization bias.

Critical strengths

The paper provides convergence analysis of two-level normalized federated optimization for both non-convex and convex objectives, explicitly accounting for the bias introduced by normalization.

Critical weaknesses

1.The theoretical condition on δ\delta conflicts with the motivation for normalization. The bound is only meaningful when δ\delta is small. However, the paper motivates normalization by arguing that gradient magnitudes can vary substantially, which would naturally lead to a larger δ\delta. This creates a tension between the motivation of the method and the conditions under which the theoretical bound is informative.

2.The experimental horizons and data settings are insufficient to establish the practical advantage of the proposed method. Several learning curves are still increasing at the final communication round, making it unclear whether the reported advantage persists after convergence. Longer training until the curves clearly plateau, with FedAvg as a baseline, is therefore needed. Moreover, the real-data experiments mainly use non-IID setting. An additional long-horizon IID comparison with FedAvg would help distinguish whether the benefit of normalization mainly comes from mitigating non-IID update-magnitude heterogeneity or reflects a genuine optimization advantage. For example, the authors could follow the long-horizon CIFAR-10 protocol in Figure 4 of [1], and evaluate both IID and non-IID partitions with FedAvg and the proposed normalization method until the learning curves clearly converge.

3.The theoretical benefit of two-level normalization is unclear. The paper establishes convergence guarantees for the proposed method but does not theoretically compare it with FedAvg or single-level normalization. Therefore, it remains unclear whether using two levels of normalization actually provides a better convergence rate or a tighter error bound.

4.Some descriptive subscripts are incorrectly typeset in italics. Terms such as 'loc', 'glob', and 'server' denote labels rather than mathematical variables, and should therefore be typeset in upright Roman font.

Reference

[1]. McMahan et al., Communication-Efficient Learning of Deep Networks from Decentralized Data, AISTATS 2017.

Questions for authors
  1. See weakness.
  2. Theorem 3.3 contains a geometric convergence term, but its rate depends on RTR_T. Can the authors clarify whether RTR_Tcan be bounded independently of the number of communication rounds, so that the claimed linear behavior is meaningful?
  3. Could the authors release their code to facilitate reproducibility of the experimental results?
2 comments

Dear Reviewer bBsa,

Thank you for recognizing our convex and non-convex convergence analysis. We retain the original setting, Algorithm 1, and core contribution; the additions below directly address your questions.

The theoretical condition on δ\delta conflicts with the motivation for normalization. The bound is only meaningful when δ\delta is small. However, the paper motivates normalization by arguing that gradient magnitudes can vary substantially, which would naturally lead to a larger δ\delta. This creates a tension between the motivation of the method and the conditions under which the theoretical bound is informative.

The original scalar proxy is a sufficient bound on the distortion of the normalized direction. To make this distinction explicit, Appendix G supplements the analysis with the directional residual δ^tdir=min⁡a≥0∣∣gˉt−aut∣∣\widehat\delta_t^{\mathrm{dir}}=\min_{a\geq0}||\bar g_t-a u_t||. It is zero for positively collinear gradients even when their norms vary arbitrarily. Theorem G.2 uses this sharper quantity without Assumption 2.5. Building on that analysis, Appendix I establishes arbitrary stationarity accuracy under relative noise and heterogeneity, with fixed KK and an accuracy-independent batch under its stated conditions. This explains how informative guarantees coexist with the magnitude variation motivating normalization.

The experimental horizons and data settings are insufficient to establish the practical advantage of the proposed method. Several learning curves are still increasing at the final communication round, making it unclear whether the reported advantage persists after convergence. Longer training until the curves clearly plateau, with FedAvg as a baseline, is therefore needed. Moreover, the real-data experiments mainly use non-IID setting. An additional long-horizon IID comparison with FedAvg would help distinguish whether the benefit of normalization mainly comes from mitigating non-IID update-magnitude heterogeneity or reflects a genuine optimization advantage. For example, the authors could follow the long-horizon CIFAR-10 protocol in Figure 4 of [1], and evaluate both IID and non-IID partitions with FedAvg and the proposed normalization method until the learning curves clearly converge.

[1]. McMahan et al., Communication-Efficient Learning of Deep Networks from Decentralized Data, AISTATS 2017.

We added the requested long-horizon comparisons on both IID and non-IID CIFAR-10. Appendix J.2 and Figure 11 report 1,000-round runs with six paired evaluation seeds and equal tuning budgets:

PartitionFedAvgLocal-onlyTwo-level
IID78.90%70.36%68.36%
Non-IID75.67%65.61%64.50%

These runs establish a strong FedAvg reference in the clean-data regime. The plateau check passes for IID but not non-IID, a distinction reported explicitly in Appendix J.2. This regime dependence is consistent with the role of magnitude information analyzed in Proposition G.10.

To assess where the additional server step helps, we also compared the methods on natural-client tasks. FLAIR with K=5K=5 gives +0.305+0.305 AP over local-only (95% CI [0.094,0.519][0.094,0.519]) under matched weighting and tuning across 40 pairs. On FEMNIST at 240 rounds with fixed K=5K=5, two-level reaches 98.29%, versus 98.17% for local-only and 97.31% for FedAvg (Table 5). The FEMNIST gain appears at the late endpoint, while earlier horizons favor local-only. The comparisons therefore establish positive effects and locate the budgets at which they occur.

(Part 1/2)

The theoretical benefit of two-level normalization is unclear. The paper establishes convergence guarantees for the proposed method but does not theoretically compare it with FedAvg or single-level normalization. Therefore, it remains unclear whether using two levels of normalization actually provides a better convergence rate or a tighter error bound.

To isolate the second normalization level, Theorem G.7 keeps the local updates unchanged and analyzes an unnormalized server aggregate. Its guarantee controls the time average of E[rt∣∣∇f(xt)∣∣]\mathbb E[r_t||\nabla f(x_t)||], where rt=∣∣Δt∣∣/(Kηloc)r_t=||\Delta_t||/(K\eta_{\mathrm{loc}}); the two-level guarantee controls the unweighted quantity. Each bound concerns its own trajectory. This identifies the aggregate-length factor removed by server normalization. Proposition G.8 then establishes a direct loss advantage over local-only and FedAvg in a one-step stochastic quadratic example, even after separate optimal tuning of coefficients chosen before sampling. Proposition G.10 explains when this removal of magnitude helps.

Some descriptive subscripts are incorrectly typeset in italics. Terms such as 'loc', 'glob', and 'server' denote labels rather than mathematical variables, and should therefore be typeset in upright Roman font.

Thank you for pointing this out. We now typeset loc\mathrm{loc}, glob\mathrm{glob}, and server\mathrm{server} in upright Roman type.

Theorem 3.3 contains a geometric convergence term, but its rate depends on RTR_T. Can the authors clarify whether RTR_T can be bounded independently of the number of communication rounds, so that the claimed linear behavior is meaningful?

The geometric term in Theorem 3.3 uses a deterministic finite-horizon radius. To identify when the initial radius suffices, we added two complementary results: Theorem F.4 proves first-hitting stability for the original algorithm under uniform directional control, while Theorem H.1 gives an expected last-iterate guarantee for an auxiliary projected variant. In the latter, the geometric term depends on R≥∣∣x0−x∗∣∣R\geq||x_0-x^*||, independently of TT. Remarks C.1–C.2 explain why the additional structure is needed.

Could the authors release their code to facilitate reproducibility of the experimental results?

Yes. We provided the experimental code, configurations, and reproduction instructions with the supplementary material.

We believe these comparisons, guarantees, and experiments strengthen the original contribution and address your concerns. We would be grateful if you would reconsider your rating in support of acceptance.

Best regards,
The Authors

(Part 2/2)

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

This paper studies federated optimization with two-level normalization under generalized smoothness. By applying normalization at both the client and server levels, the proposed method introduces bias, which poses challenges for theoretical analysis. The authors introduce a norm-dispersion parameter for this bias, and establish convergence rate for both non-convex and convex settings.

Critical strengths
  1. The algorithm design is clean and clean.It applies two-level normalization without requiring gradient clipping or control variates.
  2. The theoretical analysis covers both non-convex and convex setting. The authors further extend the analysis to mini-batching, partial participation, and heavy-tailed noise.
  3. The experimental evaluation covers multiple datasets and includes ablation studies and synthetic diagnostics.
Critical weaknesses
  1. Assumption 2.5 (Norm dispersion) introduces an additional assumption, which requires the length of stochastic gradients within a round not to be too dispersed around a common normalization scale. The corresponding paramter δ\delta then appears in the convergence bounds of Theorem 3.1, 3.3, 4.1, 4.3. However, it is not clear under what conditions δ\delta can be sufficiently small. In particular, under non-IID or heavy-tailed noise, δ\delta could be large. A more detailed discussion of this assumption and its practical implications would help clarify the applicability of the theoretical results.
  2. In the convex setting, Theorem 3.3 requires a bound RTR_T on the distance between the iterates and an optimal solution. It remains unclear whether RTR_T can be bounded independently of TT, or under what additional conditions such as bound can be established.
  3. The role of δ\delta in the experiments remains unclear. Although Table 4 reports the empirical normalization-bias proxy δ^\hat{\delta}, it only presents the average over the last 20% of logged communication rounds. Since this parameter plays an important role in the proposed methods and theoretical analysis, it would be helpful to investigate how it changes throughout training, especially during the early stages, and how it related to the convergence behavior of the proposed method.
  4. The experimental evaluation of the heavy-tailed noise setting is relatively limited. Additional experiments with explicitly varying values of pp would provide stronger empirical support for the theoretical analysis of two-level normalization under heavy-tailed noise.
  5. Table 1 in Appendix reports performance degradation on several datasets and settings. Although the authors provide some diagnostics on when the second normaliation level is beneficial, it remains unclear how to determine whether two-level normalization should be perfered for a given dataset or task. Does this suggest that the proposed method is sensitive to different data distributions or task? More practical guidance on when to use two-level normalization would strengthen the experiemntal evaluation?
Questions for authors

See the weaknesses above.

2 comments

Dear Reviewer 7ryp,

Thank you for your constructive review and recognition of the breadth of our analysis. Building on the original setting and Algorithm 1, the additions below clarify when the guarantees are informative and connect them to the experimental behavior.

1. Assumption 2.5 (Norm dispersion) introduces an additional assumption, which requires the length of stochastic gradients within a round not to be too dispersed around a common normalization scale. The corresponding paramter δ\delta then appears in the convergence bounds of Theorem 3.1, 3.3, 4.1, 4.3. However, it is not clear under what conditions δ\delta can be sufficiently small. In particular, under non-IID or heavy-tailed noise, δ\delta could be large. A more detailed discussion of this assumption and its practical implications would help clarify the applicability of the theoretical results.

The key distinction is between variation in gradient magnitudes and distortion of their aggregate direction. Appendix G makes this explicit: positively collinear gradients can have arbitrarily different norms and zero directional error. Theorem G.2 gives guarantees in terms of this sharper quantity without Assumption 2.5, while Corollary G.4 bounds it using the original smoothness, noise, and heterogeneity assumptions. Under the relative-noise and client-dissimilarity conditions of Theorem I.1, this control further yields arbitrary expected stationarity accuracy for fixed KK with an accuracy-independent batch satisfying Eq. (55). Thus, informative guarantees are compatible with large norm variation.

2. In the convex setting, Theorem 3.3 requires a bound RTR_T on the distance between the iterates and an optimal solution. It remains unclear whether RTR_T can be bounded independently of TT, or under what additional conditions such as bound can be established.

We added two results specifying when the initial radius suffices. For the original update, Theorem F.4 proves stability within that radius until the target is first reached, under explicit uniform-control conditions. For an auxiliary projected variant, Theorem H.1 instead gives an expected last-iterate guarantee through the initial radius. These complement Theorem 3.3, whose finite-horizon interpretation and need for additional structure are clarified in Remarks C.1–C.2.

3. The role of δ\delta in the experiments remains unclear. Although Table 4 reports the empirical normalization-bias proxy δ^\widehat\delta, it only presents the average over the last 20% of logged communication rounds. Since this parameter plays an important role in the proposed methods and theoretical analysis, it would be helpful to investigate how it changes throughout training, especially during the early stages, and how it related to the convergence behavior of the proposed method.

To show how these quantities evolve with optimization progress, we added full-training diagnostics in Appendix J.3 and Figure 12. They jointly track scalar dispersion, directional error, aggregate length, and reference loss throughout 240 CIFAR-10 rounds over six seeds. This includes early training and makes the distinction between changes in magnitude and direction visible along the same trajectories.

4. The experimental evaluation of the heavy-tailed noise setting is relatively limited. Additional experiments with explicitly varying values of pp would provide stronger empirical support for the theoretical analysis of two-level normalization under heavy-tailed noise.

Following your suggestion, Appendix J.4 and Table 6 cross p∈[1.25,1.5,1.8]p\in[1.25,1.5,1.8] with B∈[4,16,64]B\in[4,16,64], using ten paired seeds per cell and noise with finite pp-th moment but infinite variance. Larger batches reduce the measured stochastic error, consistent with the averaging term in Theorem 4.3. Table 6 reports all comparisons, including smaller final gaps for local-only and clipping. To complement this absolute-noise experiment, a relative-noise grid varies both pp and KK; all 160 runs reach ∣∣∇f∣∣≤0.025||\nabla f||\leq0.025.

(Part 1/2)

5. Table 1 in Appendix reports performance degradation on several datasets and settings. Although the authors provide some diagnostics on when the second normaliation level is beneficial, it remains unclear how to determine whether two-level normalization should be perfered for a given dataset or task. Does this suggest that the proposed method is sensitive to different data distributions or task? More practical guidance on when to use two-level normalization would strengthen the experiemntal evaluation?

The benefit depends on whether the aggregate length mainly introduces variability or carries useful information about the direction. Proposition G.10 makes this distinction precise through a quadratic comparison with separately optimized coefficients; G.7–G.9 provide complementary guarantees and strict-gain examples. The natural-user FLAIR experiment tests the additional server step at K=5K=5: matched tuning gives +0.305+0.305 AP points over local-only (95% CI [0.094,0.519][0.094,0.519]). Together with the local-work and horizon comparisons in Appendices A.2 and J.1–J.2, this motivates comparing separately tuned server rules at the intended training budget.

These additions address the applicability questions while strengthening the theory and evidence for the second normalization level. We would be grateful if you would reconsider your rating in favor of acceptance. We welcome any remaining questions.

Best regards,
The Authors

(Part 2/2)

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to the Reviewers

We sincerely thank all reviewers for their careful reading and constructive feedback. We appreciate their recognition of the original paper's theoretical contribution.

Reviewer 7ryp highlighted the breadth of the analysis:

The theoretical analysis covers both non-convex and convex setting. The authors further extend the analysis to mini-batching, partial participation, and heavy-tailed noise.

Reviewer bBsa emphasized its treatment of normalization bias:

The paper provides convergence analysis of two-level normalized federated optimization for both non-convex and convex objectives, explicitly accounting for the bias introduced by normalization.

Reviewer jkPF recognized the analytical framework:

The paper successfully handled convergence under the generalized assumption on smoothness. The paper proposes a new framework to analyze a new problem of normalization, which is nice.

The original problem setting, Algorithm 1, and core theoretical contribution are preserved. We have supplemented this analysis to explain more directly why server normalization helps and when its guarantees are informative. Theorem G.7 provides the requested comparison with local-only normalization, while Proposition G.8 establishes a strict benefit in a stochastic quadratic example even after separate coefficient optimization. The complementary directional analysis explains how useful normalized updates can coexist with large norm variation; under explicit relative-moment and alignment conditions, Appendix I further establishes arbitrary stationarity accuracy with fixed local work and an accuracy-independent batch.

We connect these theoretical additions to further experiments. On FLAIR with K=5K=5, matched tuning and 40 paired seeds give a 0.3050.305-point AP improvement over local-only (95% CI [0.094,0.519][0.094,0.519]). The additional FedAvg comparisons, longer training horizons, full-trajectory diagnostics, and varying heavy-tail exponents address the reviewers' requests and clarify the regimes in which the second normalization level is useful.

These additions strengthen the justification and empirical support for the original method. We address each comment below and would be grateful if the reviewers would reconsider their ratings in support of acceptance.

Best regards,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.