acceptodds
Under review as a conference paper at ICLR 2027

Leveraging Low-Rank Hessian Structures for Communication-Efficient Federated Learning

Abstract

Communication dominates the cost of federated learning (FL), and second-order curvature can reduce the number of rounds needed to reach a target accuracy. Existing federated second-order methods, however, largely face a dilemma: approaches that operate on curvature at full-Hessian scale incur memory and computation costs quadratic in the parameter count and are therefore restricted to shallow models, whereas lightweight diagonal approximations remain inexpensive but discard cross-coordinate curvature. To address this dilemma, we propose FHaN, a federated optimization method that builds second-order updates from a few locally sampled Hessian columns. Each client selects the columns in a gradient-guided manner and builds from them a compact low-rank correction capturing part of the cross-coordinate curvature. Because the solve is confined to the sampled subspace, neither the full Hessian nor its inverse is ever formed; the only inversion required is that of a small matrix, stabilized by smoothing its singular values. The result is a model-sized update vector per client, so the per-round payload matches that of first-order methods, and the efficiency gain comes from reaching target accuracy in fewer rounds. We show that FHaN converges linearly whenever the aggregated update satisfies a contraction condition, and identify a regime of data heterogeneity and sampling error in which this condition is feasible. On MNIST, Fashion-MNIST, CIFAR-10 and CIFAR-100, FHaN's advantage concentrates where curvature matters: federated fine-tuning of frozen pretrained backbones gains up to +13.2 final accuracy points with up to fewer rounds to target, and FC-dominated models trained from scratch gain up to +23.9 points, while saturated tasks, benign convex problems, and end-to-end convolutional training mark its boundaries.

Primary area:
optimization
Keywords:
Federated Learning, Communication Efficiency, Second-Order Optimization, Newton's Method, Low-Rank Approximation, Nystrom Approximation

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

The paper aims to propose a refined second-order method for federated learning. The main contribution seems to be tackling the local computation burden of Hessian, which is done through a sampling process. Further, a method is used for computing the Hessian inverse to avoid numerical instability.

Critical strengths
  1. Studying of second-order methods for federated learning can be of particular interest if they actually can outperform first-order methods under the same communication/computation budget.

  2. The paper aims to solve legitimate limitations of second-order methods: high computation complexity and numerical instability.

Critical weaknesses

The paper suffers from a variety of limitations which makes it unsuitable for publication in its current form:

  1. The text of the paper is extremely hard to follow as the text lacks a cohesive story. This can be caused by an excessive use of AI or lack of proofreading by the authors.

  2. The contributions of the paper are not crystal clear: (i) The computation of the inverse of Hessian matrix seems to be borrowed from existing techniques in the literature, and (ii) Hessian approximation using column sampling is also borrowed from a more generic techniques in Algebra. As a result, it is not clear what is the ground-breaking contribution in the paper.

  3. The simulation results of the paper are extremely limited. The paper compares with two methods: FedAvg (McMahan et al., 2017) and SCAFFOLD (Karimireddy et al., 2020). These are highly outdated methods that are not even second-order methods in nature. If the paper wants to show its advantage over the first-order methods that use the same communication/computation, it should move toward papers published in 2025/2026 and compare its method against state-of-the-art methods. Without such comparisons, it cannot be judged whether the proposed method in the paper can actually beat the best first-order methods.

Questions for authors

The paper suffers from major limitations that makes it unsuitable for publication in its current shape. Please refer to the comments above (I do not have a specific question and mostly there are a series of concerns that lead to my evaluation of the paper).

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

This paper proposes FHaN, a second-order federated optimization method that uses a small number of sampled Hessian columns to construct local updates. Clients select columns based on gradient magnitude and use a low-rank approximation to avoid forming the full Hessian. A smoothed inverse is used for numerical stability. Each client sends only a model-sized update, so communication savings come from reaching a target accuracy in fewer rounds. The paper provides a conditional convergence analysis and evaluates FHaN on image-classification tasks, with the largest gains occurring when training classification heads over frozen pretrained features.

Critical strengths

1. Using sampled Hessian columns to capture cross-coordinate curvature is well motivated. The method avoids constructing the full Hessian and communicates only model-sized updates, providing a practical way to explore second-order optimization under a limited communication budget.

2. The frozen-backbone experiments show substantial improvements over FedAvg, particularly on CIFAR-100. The paper also reports cases where FHaN loses its advantage, which helps readers understand when the additional curvature information is useful.

Critical weaknesses

1. I am not sure that the practical cost advantage is sufficiently established. Fewer communication rounds come at the expense of additional backward passes and O(Dd)O(Dd) sketch storage on each client, but training time and peak memory are not measured. The sampling rate and smoothing parameter λs\lambda_s remain fixed. Their impact on approximation quality and training stability is not sufficiently explored.

2. The comparisons with second-order baselines could be stronger. FONN is identified as the closest approach but is missing from the evaluation, while Fed-Sophia and FAGH are compared using single runs from a separate experimental campaign. It is unclear whether FHaN provides a consistent advantage over these alternatives.

Questions for authors

1. How were the sampling rate and smoothing parameter λs\lambda_s selected? While the paper studies the effect of λ\lambda, the other two parameters remain fixed across tasks. Does the same sampling rate provide sufficient curvature information for blocks of different sizes, particularly under stronger data heterogeneity?

2. The evaluation mainly uses MNIST, Fashion-MNIST, and CIFAR, and the pretrained backbones remain frozen during fine-tuning. How does FHaN perform when a larger model is trained end to end on a more demanding dataset? This would help clarify whether the reported gains extend beyond optimizing relatively small classification heads.

3. The communication analysis focuses on the number of rounds and the model-sized payload. Does it account for both downloads and uploads? Given that each sampled Hessian column requires an additional backward pass, a direct comparison of total training time and peak client memory would help establish when the communication savings outweigh the local overhead.

4. FONN is identified as the closest related method but is not included in the evaluation. Could you add this comparison and evaluate Fed-Sophia and FAGH under the same three-seed protocol as Table 2? The current single-run results make it difficult to determine whether the improvements over existing second-order methods are consistent.

5. Algorithm 1 does not show whether the local parameters are updated or the update directions are accumulated within the minibatch loop. As written, only the last minibatch’s direction appears to be sent to the server. Please clarify how the local epoch is implemented.

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

This paper proposes FHaN, a federated Newton-type optimizer that constructs local low-rank curvature approximations from gradient-guided Hessian-column sampling. A Nyström–Woodbury formulation avoids forming the full Hessian, and singular-value smoothing stabilizes the small core solve. Clients communicate only model-sized update vectors. The paper presents a conditional local linear convergence analysis and evaluates the method on MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100, covering frozen-backbone head training and several small models trained from scratch. The results show substantial improvements in selected settings, alongside limitations under extreme heterogeneity, end-to-end convolutional training, and some saturated tasks.

Critical strengths
  1. A practical curvature construction with model-sized communication. The method combines sampled Hessian columns with a small core solve, allowing clients to incorporate cross-coordinate curvature without transmitting Hessian information or storing a full Hessian. This addresses a meaningful computational and communication trade-off in federated optimization.
  2. Substantial gains in selected settings, with explicit reporting of limitations. The paired three-seed experiments show sizeable improvements on frozen-backbone CIFAR-100 head training. The paper also reports late-round collapse and settings where FHaN underperforms FedAvg. This makes the empirical contribution more informative than a presentation restricted to favorable cases.
Critical weaknesses
  1. The convergence guarantee is disconnected from the algorithm, and its contraction condition appears infeasible in the PSD setting used by the proof. Lemma 5.4 assumes sampling probabilities that dominate Hessian leverage scores, but the implemented probabilities are proportional to squared gradient coordinates. No domination bound is established; a coordinate can have zero gradient and still carry substantial curvature. Appendix B also analyzes an exact inverse of the regularized Nyström approximation, rather than the smoothed operator in Eq. (8), and does not account for blockwise approximation or multiple minibatch updates. (1-\eta)L/\nu+\cdots+\eta\epsilon_B L/\lambda, \qquad \epsilon_B=1+B/\sqrt{\delta}. ] In the PSD-loss-Hessian setting invoked in Appendix B, (L\geq\lambda) and (L\geq\nu). Therefore, for (0<\eta<1), [ P(\eta,\lambda)\geq 1-\eta+\eta\epsilon_B>1. ] This appears to prevent the claimed contraction. The feasibility argument treats (\lambda) as independently adjustable without addressing its effect on the objective’s smoothness and curvature constants. These issues undermine a central theoretical contribution.

  2. The empirical evidence does not sufficiently isolate the contribution or establish a reliable efficiency advantage. The closest sampled-curvature methods discussed in the paper, particularly FONN and Nys-FL, are not evaluated. There are no controlled ablations isolating gradient-guided sampling from uniform sampling or singular-value smoothing from the unsmoothed solve. Consequently, the benefits of the proposed modifications remain unclear. Furthermore, the second-order comparison in Table 3 uses single runs from an earlier campaign rather than the paired three-seed protocol of Table 2. Its results favor FHaN under CNN training and extreme heterogeneity, while the boundary study reports losses in these regimes; the setup differences need to be documented. The baseline learning-rate search is also narrow, and no measured runtime or peak-memory results quantify the additional Hessian-column computation. Fewer communication rounds are useful, but the current evidence does not establish when those savings compensate for the increased local cost.

Questions for authors

1.Theoretical clarification: How can (P(\eta,\lambda)<1) hold given the lower bound above in the PSD setting used by Appendix B? Please provide a consistent parameter regime that accounts for the dependence of (L) and (\nu) on (\lambda). 2.Theoretical clarification: What guarantees that squared-gradient sampling dominates Hessian leverage scores? How does the analysis account for the smoothing in Eq. (8) and the blockwise implementation? 3.Implementation clarification: What exactly is updated inside Algorithm 1’s local-step loop, and what quantity is transmitted after multiple batches? Is it an accumulated model displacement or the final batch’s direction? 4.Experimental clarification: What datasets, architectures, hyperparameters, and implementation differences distinguish Table 3 from the main and boundary experiments? Are its second-order comparisons reproducible under the same paired three-seed protocol?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.