acceptodds
Under review as a conference paper at ICLR 2027

Clipped Optimization over Hierarchical Networks under Generalized Smoothness

Abstract

Hierarchical learning systems combine federated aggregation within groups of clients with decentralized communication across hubs. We study optimization in this setting under -smoothness, where the local smoothness level may grow with function suboptimality. This model is particularly convenient for hierarchical objectives because averaging preserves the curvature-growth parameter , with heterogeneity entering through an additive interpolation defect. The main difficulty is locality, since the corresponding descent inequality is valid only for sufficiently small displacements. We therefore use clipping at both levels of the hierarchy: clients clip gradients before aggregation, while hubs clip the optimization step and leave the gradient tracker unchanged. We prove nonconvex convergence guarantees for the resulting federated, decentralized, and hierarchical methods, with accelerated dependence on the network spectral gap. For convex objectives, the same mechanism leads to two phases: linear convergence while clipping is active, followed by an regime. Under strong convexity, both phases are linear.

Primary area:
optimization
Keywords:
hierarchical optimization, federated learning, decentralized optimization, gradient clipping, gradient tracking, generalized smoothness, $(H_0, H_1)$-smoothness, two-phase convergence

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_GDhiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper provides a theoretical analysis of decentralized SGD type algorithms in hierarchical networks specifically of 2 layers. They propose a different H0,H1 generalized smoothness analysis which is novel in this setting in the existing literature and propose a gradient clipping based algorithm (clipping client gradients before aggregation and clipping hub steps) and show convergence guarantees across convex and non convex objectives.

Critical strengths
  1. The authors provide substantial mathematical rigor to a paper in a complex setup with both convex and non-convex formulations.
  2. Their H0,H1 smoothness is perhaps a novelty and an interesting analysis component. Clipping is also shown to be necessary, which is an interesting observation.
Critical weaknesses
  1. I understand that the paper is a theory/optimization paper , but the practical takeaways are very limited relative to the baselines the paper positions it against. The paper poses itself and compares itself with local sgd, decentralized sgd type methods where, clipping and hierarchical aggregation has been done in many ways in literature (even in the paper's own related works cite them). This broader prior work also also consider more fundamental complexities such as non full participation, additive noise, adversarial models (label flip is not really adversarial), non-exact gradient, and also gradient clipping and variance reduction methods, and then go on to show that those algorithms have worked on training anywhere between 100,s 1000s of extremely non-iid scenarios to training (small) language models even in practice. By comparison, the setting in this paper is considerably constrained by its own assumptions and the experiments are not detailed or sufficient enough for us readers to extract any practicial lesson. 1.a. The paper starts with motivations about non-iid and transformers etc, the experiments are convex (logistic,exponential,quadratic) with only two toy examples. Without larger scale experiments with convex and non convex, larger in size of distributed network, non iid-ness, model trained, skewed distribution, etc. in 2026 it is difficult to justify. 1.b. clipping at many levels has been prevalent in federated learning literature, this is not the novel contribution. i think the novelty is around the H0,H1 smoothness class and the specific setting of two layered hierarchy with clipping before aggregation. This can be made much more clear perhaps.

  2. The paper does compare itself with local sgd, but the 3 algorithms in the paper (HUBCLIP, GT-CLIP, H2GT-CLIP) fundamentally do not do any local sgd or local steps which may lead to additive errors (e.g. could be because of client drift and or gradient compression etc.) and this regime does not appear to be modeled here which is leaving a gap. How would the analysis and experimental behavior change if the clients are taking local steps?

  3. As a decentralized algorithm paper, communication experiments analysis is limited. No ablation over the topology or connectivity or benchmarks against communication against local sgd baselines. fastmix does require gossip communication for every single gradient step, compared tofederated learning/ SGD algorithms, the communication impacts of running such an algorithm in practice is not understandable. The authors mention about 38x message saving against some flat baseline but that is not clear in the context of existing methods of decentralized algorithms.

  4. The paper does not go into details about how we are supposed to get the optimal values of all the variables, for example the step size, clipping radius, even constants like H0, H1, the spectral gap etc. These gets even worse if we consider training anything more complex than a logistic regression such as a MLP, a CNN/LSTM or even a transformer. Their own experiments show that assumptions in their theory may or may not even hold in their own toy experiments (e.g. dissimilarity) and the method is not parameter free itself.

  5. The paper reads very difficult. It assumes familiarity with subjects such as generalized smoothness etc. and several notations are being deferred to appendix or not defined before use.

Questions for authors

See weaknesses.

2 comments

Thank you for the detailed review. Your request for neural networks led to the CNN and transformer experiments now in §7, and while re-checking the communication cost for your third point we found and corrected an undercount of the messages of tracking methods.

Weakness #1 (practical lessons). §7 now ends with four. Clip before aggregation when the start is far from the solution or some clients send large gradients; without clipping the step must be 4 to 32 times smaller, or the method diverges (Figs. 4a, 5, 9a). The product γτ\gamma\tau bounds the clipped step and locates the stability boundary for small radii, but γ\gamma and τ\tau still need separate tuning (Fig. 9c). One gossip step per round (Kin=1K_{\mathrm{in}}=1) converged on every topology we tried (Fig. 8). Tracking pays when hubs differ, gossip is cheap and high accuracy is needed (Figs. 3c, 4b, 4c, 9a); it costs a second gossip exchange per round and gave no measurable gain on the CNN and the transformer.

Weakness #1 (settings of prior work). The paper covers partial participation and stochastic gradients at the federated level under strong growth (Theorem 6), heavy-tailed noise at that level (Theorem 2), per-round differential privacy (Proposition 4), and stochastic clients in the hierarchy with full participation and a growing batch (Corollary 1). Additive noise at the decentralized and hierarchical levels and Byzantine clients are not covered, and the Limitations paragraph says so.

Weakness #1.a (convex experiments). The convex runs let us compute f⋆f^\star and RR and test the theorems. We added three nonconvex experiments in hierarchies of 8 hubs and 8 clients per hub with heterogeneous splits: a two-layer network (App. H) and, in §7 (Figure 5), a CNN on Fashion-MNIST and a GPT-style transformer with 3.3M parameters on WikiText-2, both with mini-batches and three seeds:

methodCNN, training losstransformer, validation loss (nats/byte)
H²GT-Clip (ours)0.40 ± 0.022.3757 ± 0.0105
HD-SGD with our client clipping0.38 ± 0.032.3843 ± 0.0004
H²GT, no clipping0.44 ± 0.022.4532 ± 0.0021
HD-SGD0.45 ± 0.032.4581 ± 0.0038

Clipping before aggregation wins on every seed. HD-SGD with our client clipping is our method without tracking, so on these tasks the gain comes from clipping.

Weakness #1.b (novelty). Agreed: §1 now says that clipping, tracking and Chebyshev gossip are known tools and that the contribution is the analysis (see the reply to e3rH). One correction to the strengths: Proposition 3 shows that unclipped tracking with a constant step can diverge in this class; it does not show that clipping is the only remedy.

Weakness #2 (local steps). LL local clipped steps keep the analysis within the locality radius when Lγℓτ≤1/H1L\gamma_\ell\tau\le1/\sqrt{H_1}, but the accumulated direction also needs alignment and tracking arguments that we have not proved; §6 says so. Fig. 9(b) tests one variant, in which clients return the normalized displacement: rounds to 10−210^{-2} are 35 or 36 for every L∈{1,2,5,10}L\in\{1,2,5,10\}, and grow from 149 to 181 at 10−410^{-4}. Other designs are not ruled out.

Weakness #3 (communication). Fig. 8 varies n∈{4,9,16,25}n\in\{4,9,16,25\} and the topology, and counts hub messages to 10−210^{-2} against hierarchical local GD, the structure of SD-FEEL and multi-level local SGD. A round of our method costs 4∣E∣Kin4|E|K_{\mathrm{in}} messages, since the tracker exchange uses gradients at the newly mixed models. With this count our method needs 1.3 to 2.3 times fewer messages for n≥16n\ge16 on the torus and the matching graph and on the ring with n=9n=9, 1.7 times more on the torus with n=9n=9, and about twice as many at n=4n=4; the baseline misses the target on the ring with n≥16n\ge16. The 38× of §7 is 50× with the corrected count.

Weakness #4 (parameters). The method is not parameter-free. Theorem 5 prescribes γ=1/(180H^0)\gamma=1/(180\hat H_0), τ=H^0/(H1R~)\tau=\hat H_0/(H_1\tilde R) and Kin=⌈log⁡(2048nΓ)/2(1−λ)⌉K_{\mathrm{in}}=\lceil\log(2048n\Gamma)/\sqrt{2(1-\lambda)}\rceil, and the run of Fig. 3(b) uses these values. On real data we tune γ\gamma and τ\tau on a grid, and Kin=4K_{\mathrm{in}}=4 already matches the prescribed 18 (Fig. 8c). The dispersion thresholds are violated on real data, and the method still converges (App. F).

Weakness #5 (readability). δ\delta is defined at first use, and Proposition 1 no longer refers forward to Lemma 6.

Dear Reviewer GDhi,

Thank you again for reviewing our paper. Before the discussion closes, could you let us know whether our rebuttal addresses your main concerns? Even a brief reply would be appreciated.

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

The paper studies hierarchical learning with cheap client–hub communication and costly communication between hubs over a gossip network. It combines this setting with gap-dependent smoothness and client-side clipping before aggregation.

The method uses clipped hub updates, gradient tracking, and accelerated gossip. The authors establish convergence for federated, decentralized, and hierarchical variants: an initial linear phase followed by O(1/K)O(1/K) for convex objectives, and linear convergence throughout under strong convexity. A refined bound reduces dependence on initial curvature.

Experiments illustrate the methods, although they fall outside the theoretical heterogeneity assumptions.

Critical strengths
  1. Strong convergence results: linear rate in the large-gap phase, and throughout under strong convexity.
  2. Decentralized convergence without a hub-gradient-dissimilarity assumption.
  3. The refined bound shows a concrete benefit of clipping: initial curvature enters logarithmically rather than multiplying the 1/ε1/\varepsilon term.
Critical weaknesses

The motivation for the setting is unclear. The paper assumes cheap client–hub communication and costly inter-hub communication, but does not sufficiently explain which applications fit this structure.

Two aspects need further justification:

  1. No local steps. Given the communication asymmetry, multiple client–hub updates before communicating between hubs seem natural. The authors should explain their choice and evaluate its communication cost.
  2. Assumptions 2 and 3 imply a common minimizer in the convex setting. This restricts the heterogeneity covered by the theory and raises questions about which applications satisfy these assumptions.

The experiments should better establish when the method is beneficial. Varying hub count, connectivity, and relative communication costs, alongside comparisons with centralized methods, would help. The experiments fall outside the theoretical conditions, both in heterogeneity and parameter choices. Experiments satisfying these conditions would better connect the guarantees to the observed behavior.

Questions for authors
  1. Which applications fit this communication structure and the shared-minimizer assumptions?
  2. Why communicate between hubs after every update? What does this gain over less frequent communication or independent hubs in the convex setting?
  3. Can you provide experiments satisfying the theoretical assumptions and parameter bounds?
3 comments

Thank you for the precise questions. Your observation that Assumptions 2 and 3 imply a common minimizer is correct, and Question #2 led to the new Figure 3(b, c) in the main text.

Question #1 and Weakness #2 (applications and the shared minimizer). The topology fits three settings, now named in §1: hospitals or clinical sites that aggregate their own departments and are connected pairwise with no central party; devices served by edge servers of several operators, as in SD-FEEL and HierFAVG; and data centers in several regions, where bandwidth inside a region is far cheaper than between regions. These settings motivate the network; the thresholds of Assumptions 2 and 3 are a separate matter.

The thresholds ask for more than a shared minimizer: f1=x2/2f_1=x^2/2 and f2=50x2f_2=50x^2 share the minimizer 00, yet ∥∇f1−∇f∥/∥∇f∥=99/101\|\nabla f_1-\nabla f\|/\|\nabla f\|=99/101 at every x≠0x\neq0. They fit interpolating models whose clients have close curvature. The assumptions differ by level. HubClip uses Assumption 2 and strong growth, GT-Clip (Theorem 7) uses no hub-dissimilarity condition, and H²GT-Clip uses Assumptions 2 and 3 in the convex and the nonconvex theorems. Without convexity they make every stationary point of ff stationary for every client, while the minimum values may differ, which the interpolation defect δ\delta measures. A version with a bias floor for clients that do not interpolate is open.

Question #2 (why communicate between hubs; independent hubs). Inside the convex hierarchical theory, communication between hubs is not what makes the hubs converge, and Fig. 3(b) now shows this. With the parameters of Theorem 5, one server over all clients, independent hubs and the hierarchy reach 10−210^{-2} and 10−610^{-6} at the same rounds (19 200 and 26 300): a common minimizer and νh≤1/48\nu_h\le1/48 keep every hub gradient within two percent of the full one. What the theory certifies in this regime is that the hierarchy loses nothing against a central server.

The backbone is needed once the hubs differ. In Fig. 3(c) the hub minimizers are shifted by vectors of norm 2, so Assumption 3 fails. Independent hubs stop at their own minimizers (gap 0.37 to 0.74). H²GT-Clip converges to the minimizer of ff for τ=2\tau=2 and τ=1\tau=1, above the client gradient norms at the solution (0.46 to 0.72). With τ=0.5\tau=0.5 some messages stay clipped at the solution and the method stalls at 6⋅10−36\cdot10^{-3}, behind even a one-shot average of the independent hubs (3⋅10−33\cdot10^{-3}): a radius below the client gradients at the solution creates a bias. Our hierarchical theorems cover only the common-minimizer case; the decentralized level (Theorem 7) has no such condition. On real data, tracking separates from plain gossip under heterogeneity (Fig. 9a: 8.6⋅10−48.6\cdot10^{-4} against 3.6⋅10−33.6\cdot10^{-3} for HD-SGD with client clipping).

A round costs two gossip exchanges, one for the models and one for the tracker; Fig. 8 shows on which backbones this pays off.

Question #3 (experiments inside the assumptions). Yes: Fig. 3(b), with details in Fig. 7. All clients share the minimizer of an exponential base loss and add quadratic perturbations of computable size. The constants are certified from the construction, not measured: H1=2.95H_1=2.95, H0=2.64H_0=2.64, R≤7.95R\le7.95 by strong convexity, ν≤0.067<1/6\nu\le0.067<1/6 and νh≤0.017<1/48\nu_h\le0.017<1/48. The run uses the prescribed τ=0.113\tau=0.113, γ=0.00211\gamma=0.00211 and Kin=8K_{\mathrm{in}}=8. The gap decreases linearly while messages are clipped and geometrically afterwards. It crosses the phase threshold τR~\tau\tilde R of the bound at round 10 800, and the last clipped message is at round 18 600. The bound holds and is loose by about two orders of magnitude in the clipped phase.

Weakness #1 (no local steps). Clients send one clipped gradient per round because the descent inequality holds only within the locality radius 1/H11/\sqrt{H_1}; LL local steps would also need alignment and tracking arguments for the accumulated direction, which we do not prove (§6). Fig. 9(b) evaluates one variant with normalized local displacements: rounds to 10−210^{-2} stay at 35 or 36 for L∈{1,2,5,10}L\in\{1,2,5,10\}, and at 10−410^{-4} they grow from 149 to 181.

Experiments (hub count, connectivity, communication, centralized methods). Fig. 8 varies the number of hubs, the topology and KinK_{\mathrm{in}}; against hierarchical local GD the outcome depends on the backbone (reply to GDhi, Weakness #3). With the prescribed KinK_{\mathrm{in}} the hierarchy takes 51 or 52 rounds for every nn and topology, so the difference to a central server is the message cost and the absence of a trusted party.

Thank you for the detailed responses and additional experiments. The discussion with you and the other reviewers was helpful, and I appreciate the paper’s primarily theoretical contribution.

Nevertheless, further evidence of practical relevance could change my assessment. Could you provide references or systems evidence supporting the communication assumptions in the hospital, edge-server, or regional data-center examples, and clarify how closely these scenarios match the setting studied?

Thank you for the follow-up. Edge networks match our setting most closely; hospitals and data centers support parts of it.

  1. Edge networks. MEC servers can be deployed at or near base stations [1]. CFEL, SD-FEEL and MLL-SGD [2–4] study devices that talk only to their edge server or hub, while hubs exchange models with neighbouring hubs and no central aggregator is used. With one local update per iteration, this is our communication pattern.
  2. Hospitals. Swarm Learning [5] trains clinical models across sites without a central coordinator. With one node per hospital, this is our decentralized level, where Theorems 3 and 7 need no hub-dissimilarity condition.
  3. Data centers. Measured bandwidth between EC2 regions is on average 15 times lower than inside a data center [6], which motivates hierarchical training with cheap links inside a hub and expensive links between hubs. Extending our method to local steps, which would further reduce communication between regions, remains open.

We will add these references to the introduction, with edge networks as the primary example.

[1] F. Giust, G. Verin et al. MEC deployments in 4G and evolution towards 5G. ETSI White Paper No. 24, 2018.

[2] Z. Zhang, Z. Gao, Y. Guo, Y. Gong. Scalable and low-latency federated learning with cooperative mobile edge networking. IEEE Transactions on Mobile Computing, 2024.

[3] Y. Sun, J. Shao, Y. Mao, J. H. Wang, J. Zhang. Semi-decentralized federated edge learning with data and device heterogeneity. IEEE Transactions on Network and Service Management, 20(2):1487–1501, 2023.

[4] T. Castiglia, A. Das, S. Patterson. Multi-level local SGD: Distributed SGD for heterogeneous hierarchical networks. ICLR, 2021.

[5] S. Warnat-Herresthal et al. Swarm Learning for decentralized and confidential clinical machine learning. Nature, 594:265–270, 2021.

[6] K. Hsieh, A. Harlap, N. Vijaykumar, D. Konomis, G. R. Ganger, P. B. Gibbons, O. Mutlu. Gaia: Geo-distributed machine learning approaching LAN speeds. USENIX NSDI, 2017.

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

This paper studies hierarchical distributed optimization under (H0,H1)(H_0,H_1)-smoothness. It shows that averaging preserves the curvature-growth parameter H1H_1, with an additive interpolation defect accounting for heterogeneity. The authors develop federated, decentralized, and hierarchical methods that combine client gradient clipping before aggregation with clipped hub updates, unclipped gradient tracking, and accelerated gossip. Under the stated assumptions, they establish nonconvex stationarity guarantees and two-phase convergence for convex objectives with both phases linear under strong convexity and accelerated dependence on the network spectral gap. Experiments with logistic, exponential, and quadratic losses examine convergence behavior, stability, and communication costs.

Critical strengths

The motivation for studying hierarchical learning is clearly presented. In particular, the explanation and illustration of how this setting differs from conventional federated and decentralized learning make the network structure and communication setting easy to understand.

Critical weaknesses
  • It is difficult to isolate the main technical contribution from the existing ingredients. The closure under averaging result is useful, but its derivation follows directly from averaging the smoothness bounds, while clipping, gradient tracking, and accelerated gossip are established techniques. Although the paper discusses the locality constraint and the control of consensus and tracking errors, it would benefit from a more explicit account of which arguments are new. In particular, it should distinguish the novelty of the algorithmic design from that of the convergence analysis and clarify why existing analyses cannot be applied directly.

  • The computational implications of the batch-size requirement in Theorem 2 are insufficiently discussed. Since ε=F0/(2γK)\varepsilon=F_0/(2\gamma K), fixing the clipping radius and other problem parameters requires b=Ω(K1/(α−1))b=\Omega(K^{1/(\alpha-1)}). Thus, the O(1/K)O(1/K) stationarity guarantee relies on an increasing number of stochastic gradient evaluations per round. The resulting total oracle complexity, accounting for KsbKsb evaluations with cohort size ss, should be stated explicitly to clarify the computational meaning of the result.

  • Several quantities and results are referenced before sufficient explanation is provided, which makes the presentation harder to follow. Examples include the interpolation defect δ\delta in the first contribution and the “round count of Lemma 6” in Proposition 1. Briefly introducing these quantities and summarizing the relevant consensus bound at their first use would improve readability.

Questions for authors
  • In Figure 4(a), the proposed method and HD-SGD with client clipping nearly coincide, whereas Figures 4(b,c) show benefits from gradient tracking but little difference between the clipped and unclipped tracking methods. Could the authors clarify which empirical benefits arise from clipping, which arise from tracking, and in what regimes the full proposed method offers an advantage over the simpler baselines?

  • Could the authors explicitly identify the main new algorithmic and analytical contributions relative to existing clipping and gradient-tracking methods? In particular, which technical obstacles require new arguments when combining client-side clipping before aggregation with decentralized hub communication under (H0,H1)(H_0,H_1)-smoothness?

4 comments

Thank you for the careful review, and for working out the batch-size consequence of Theorem 2: the oracle complexity is now stated in the paper.

Question #2 and Weakness #1 (what is new; why existing analyses do not apply). The algorithms compose known tools, and the analysis is new; §1 now says which parts. The first obstacle is locality. Under (H0,H1)(H_0,H_1)-smoothness the descent inequality holds only for displacements up to 1/H11/\sqrt{H_1}, and the modulus H0+H1ϕ(x)H_0+H_1\phi(x) changes along the run and differs across hubs. Existing tracking proofs (Nedić et al., 2017; Qu & Li, 2018; Koloskova et al., 2020; Ye et al., 2023) use one global Lipschitz constant and a step that is a fixed fraction of its inverse. Proposition 3 shows that unclipped tracking with a constant step can diverge in this class, so these proofs do not transfer. We bound the consensus and tracking errors relative to the current clipped gradient mk=min⁡{∥∇f(xˉk)∥,τ}m^k=\min\{\|\nabla f(\bar x^k)\|,\tau\} (eq. 6) and carry this bound through the induction over rounds (Lemmas 13 and 14, Theorem 7). Because the errors are measured against mkm^k and not against a heterogeneity constant, the decentralized level needs no hub-dissimilarity assumption.

The second obstacle is that in the hierarchy each hub applies an average of individually clipped client gradients, which is not the gradient of any function; Lemma 16 gives the three properties of these surrogates that the tracking recursion needs. The third is the bias of averaged clipped vectors: under multiplicative dissimilarity the average stays aligned with the hub gradient (Lemmas 10 and 11), so there is no bias floor without error feedback. The two convex phases come from a lower bound on the clipped measure in terms of the gap (Lemma 8) and a scalar recursion (Lemma 7). Jiang et al. (2025) also prove two-phase convex rates for decentralized gradient descent, with a step that depends on the largest gradient norm in the network; ours differ in the class, the constant step, the absence of a hub-dissimilarity condition, strong convexity and the hierarchy. The closure result is elementary, and the paper presents it as such.

Weakness #2 (oracle complexity). Fix the failure probability β\beta and a target η\eta for min⁡k∥∇fi(xk)∥2\min_k\|\nabla f_i(x^k)\|^2. Then K=O(η−1)K=O(\eta^{-1}) rounds suffice, the batch condition gives b=O(η−1/(α−1))b=O(\eta^{-1/(\alpha-1)}), and with cohort size ss the run uses Ksb=O(s η−α/(α−1))Ksb=O(s\,\eta^{-\alpha/(\alpha-1)}) stochastic gradients, i.e. O(s ϵ−2α/(α−1))O(s\,\epsilon^{-2\alpha/(\alpha-1)}) for ∥∇fi∥≤ϵ\|\nabla f_i\|\le\epsilon. At α=2\alpha=2 the exponent is the ϵ−4\epsilon^{-4} of SGD and matches that of the lower bound of Zhang et al. (2020); the criterion and the class differ, so only the exponents match. For α<2\alpha<2 the bound is worse than the LL-smooth benchmark ϵ−(3α−2)/(α−1)\epsilon^{-(3\alpha-2)/(\alpha-1)} by a factor ϵ−(2−α)/(α−1)\epsilon^{-(2-\alpha)/(\alpha-1)}, because the noise is controlled by batching alone.

Weakness #3 (forward references). Fixed. δ\delta is defined in the first contribution, and Proposition 1 states directly that accelerated gossip needs Θ(1/1−λ2)\Theta(1/\sqrt{1-\lambda_2}) rounds for a fixed contraction, with Lemma 6 as a reference.

Question #1 (benefits of clipping and of tracking). Clipping helps when the start is far from the solution or some clients send large gradients; tracking helps when the hubs differ and high accuracy is required; the full method is needed when both hold. Fig. 4 shows the two separately: panel (a) has a distant start, where clipping matters, and panels (b, c) are heterogeneous problems with cheap gossip, where tracking matters. Fig. 9(a) puts both in one regime (exponential loss, label-sorted clients, distant start, Kin=1K_{\mathrm{in}}=1). Without clipping the step must be 32 times smaller and the final gap is 48 to 100 times worse; without tracking, HD-SGD with client clipping stalls at 3.6⋅10−33.6\cdot10^{-3}, while H²GT-Clip reaches 8.6⋅10−48.6\cdot10^{-4}. On the CNN and the transformer (Figure 5) the two clipped methods are within one standard deviation, so the gain there comes from clipping. We did not measure the consensus and tracking errors in those runs, so we do not claim why tracking adds nothing there.

Dear Reviewer e3rH,

Thank you again for reviewing our paper. Before the discussion closes, could you let us know whether our rebuttal addresses your main concerns? Even a brief reply would be appreciated.

Thank you to the authors for the detailed responses, and apologies for my delayed reply. The clarifications and additional experiments have addressed my main concerns and clarified the analytical contribution. I now lean toward acceptance and raise my score to 3.

Thank you for your helpful comments and for raising your score!

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

The paper studies distributed optimization under generalized (H0, H1)-smoothness. The generalized smoothness notation is a relatively new branch of research in numerical optimization starting from paper of Zhang et al. 2020. The generalized smoothness condition allows to analyze the performance of numerical methods over functions with non-Lipschitz gradient. The paper proposes a distributed algorithm based on a gradient tracking technique. Moreover, the paper specifically adapts the distributed algorithm for hierarchical networks, where the top-level is a general connected undirected graph and the lower level is a star graph. The proposed method uses gradient clipping to tackle the heavy-tailed noise and multi-step fast consensus between gradient steps. It also uses the gradient tracking trick, as mentioned above.

The paper gives assumptions, the analysis of the algorithms and numerical experiments.

Critical strengths

The paper is generally well-structured. The assumptions are clearly formulated as well as the main result. The theoretical findings are covered by numerical simulations, as well. The paper looks into an interesting two-level hierarchical network structure.

Critical weaknesses

The paper combines several assumptions: two-level hierarchy, heavy-tailed noise and a generalization on noise with infinite variance. But what is the main paper contribution? Is it one concrete new assumption or the combination of several challenges? If the paper focus is one concrete challenging assumption, it should be explicitly underlined. If the paper main contribution is an interesting combination of several assumptions, then a comparison with other works where partial combinations were performed should be done (i.e. some paper on distributed optimization under (H0, H1) assumption).

Questions for authors

See the question of paper contribution in "Critical Weaknesses" above.

2 comments

Thank you for the positive assessment and for the clear question.

Question (main contribution). The main contribution is one analysis, not a combination of assumptions: clipped optimization over a two-level network under function-gap (H0,H1)(H_0,H_1)-smoothness, in which consensus, tracking and client-averaging errors are bounded relative to the current clipped gradient. §1 now states this in a "What is new" paragraph. Heavy-tailed noise with infinite variance is handled at the federated level only (Theorem 2), by clipping at the clients before aggregation. The decentralized and hierarchical theorems use exact gradients, and Corollary 1 extends the hierarchy to stochastic clients under strong growth, with full participation and a batch that grows with the horizon. Each is a separate guarantee with its own assumptions.

The comparison with partial combinations is new Table 2 (App. G), which lists the ten closest distributed results with their smoothness class, network, clipping, heterogeneity assumption and convex rates. No prior distributed result exists for function-gap (H0,H1)(H_0,H_1)-smoothness; the closest use (L0,L1)(L_0,L_1)-smoothness. Luo et al. (2026) assume bounded dissimilarity. Jiang et al. (2025) use a step that depends on the largest gradient norm in the network and no tracking. The hierarchical analyses of Sun et al. (2022) and Castiglia et al. (2021) are LL-smooth and unclipped. Our decentralized method uses a constant step and no hub-dissimilarity condition, and the paper adds strong convexity and the refined bound of Theorem 5.

Dear Reviewer QPJK,

Thank you again for reviewing our paper. Before the discussion closes, could you let us know whether our rebuttal addresses your main concerns? Even a brief reply would be appreciated.

Comments on the paper

1 comment

We thank the reviewers for their careful reviews. All changes are in blue, and the main text uses the ten pages allowed for the revision. The numbers behind each change are given in the individual responses.

The reviews share one question: what does the analysis add to known tools, and which settings does it cover? Our answer has two parts. First, the algorithms compose known tools (client clipping, gradient tracking, Chebyshev gossip), and the contribution is the analysis. Under (H0,H1)(H_0,H_1)-smoothness the smoothness modulus changes along the run, so we bound the consensus and tracking errors relative to the current clipped gradient and carry this bound through the induction over rounds; the same bound removes the hub-dissimilarity assumption for decentralized GT-Clip. Second, the hierarchical theorems assume a bounded relative dissimilarity of clients and hubs (Assumptions 2 and 3), which under convexity implies a common minimizer. In this regime the hierarchy matches a central server. Once the hubs differ, communication between hubs is what lets the method converge; we show this on a construction, not as a theorem.

The main changes:

  1. A "What is new" paragraph in §1 separates the algorithm from the analysis, and new Table 2 (App. G) compares assumptions and guarantees with the ten closest distributed results (e3rH, QPJK, GDhi).
  2. New Figure 3 in §7 shows the two phases on real data, a run that satisfies every assumption with certified constants and the parameters of Theorem 5, together with a central server and independent hubs, and a run where the hub minimizers differ (ETXw, GDhi).
  3. §3 and §6 state that Assumptions 2 and 3 imply a common minimizer, and §1 names the applications of the hierarchical topology (ETXw).
  4. The oracle complexity of Theorem 2 is stated after the theorem and in App. C.4 (e3rH).
  5. We corrected the message count of tracking methods: a round has two gossip exchanges, one for the models and one for the tracker, and the submitted version charged one. Fig. 8 and the 38× of §7, now 50×, use the corrected count (GDhi, ETXw).
  6. §7 now reports a CNN on Fashion-MNIST and a transformer language model on WikiText-2 with three seeds each (Figure 5 and a table) and ends with practical lessons. New App. H gives their full protocol and studies hub count, topology and inner rounds against hierarchical local GD (Fig. 8), clipping against tracking, local steps and sensitivity (Fig. 9), and a two-layer network (Fig. 10) (GDhi, ETXw, e3rH).
  7. δ\delta is defined at first use, Proposition 1 no longer points forward to Lemma 6, and the round cost of the decentralized and hierarchical methods is stated as 2Kin2K_{\mathrm{in}} gossip steps (e3rH, GDhi).

On the neural networks, clipping before aggregation helps on every seed, and tracking adds no measurable gain. This is evidence on the cases we tested, not a guarantee.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.