Pith. sign in

REVIEW 2 major objections 5 minor 31 references

Achieving Linear Speedup for Composite Federated Learning

T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Pith's one-line read FedNMap achieves linear speedup for nonconvex composite federated learning by pairing a normal-map update with a local correction term.

desk verdict Promising first linear-speedup claim for nonconvex composite FL, but both headline rate theorems currently choose parameters that violate their own conditions—worth refereeing after a fix. read the letter →

arxiv 2602.03357 v2 pith:PIZAFPZF submitted 2026-02-03 cs.LG math.OC

classification cs.LGmath.OC
keywords federatedlearningcompositeoptimizationnonsmoothregularizernormalmaplinearspeedupnonconvexstochasticgradientscommunicationcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes FedNMap, a federated algorithm for minimizing an objective made of a smooth loss plus a possibly nonsmooth regularizer such as an ℓ1 norm or constraint indicator. Its central claim is that FedNMap attains linear speedup—the dominant communication cost to reach a stationary point falls as 1/(nQ), where n is the number of clients and Q the number of local steps—for nonconvex composite objectives, both with and without a Polyak-Łojasiewicz condition. Prior proximal federated methods required convexity, bounded subgradients, or homogeneous data; FedNMap needs only smooth local losses, weak convexity of the regularizer, and bounded stochastic-gradient variance. The key mechanism is a normal-map update, which keeps stochastic estimates unbiased despite the proximal operator, combined with a correction term that cancels client drift. Numerical experiments on image classification show convergence improving as n or Q increases, matching the predicted speedup.

What carries the argument

The central object is the normal map F^γ_nor(z)=∇f(prox_γφ(z))+γ^{-1}(z−prox_γφ(z)). It belongs to the subdifferential of ψ at the prox point and serves both as stationarity measure and as the local update direction. FedNMap's client update z^{ℓ+1}=z^ℓ−η_a[g_i(x^ℓ;ξ)+γ^{-1}(z_t−x_t)+c_{i,t}] with x^ℓ=prox_γφ(z^ℓ) is an unbiased stochastic normal-map step because the prox is applied before the gradient is sampled. The correction term c_{i,t+1}=c_{i,t}−y_{i,t}+(1/n)Σ_j y_{j,t} forces the average of client directions to track the global stochastic normal map, so the server update z_{t+1}=z_t−(Qη_sη_a/n)Σ_i y_{i,t} is an approximate normal-map step. This combination is what carries the 1/(nQ) ra

What would settle it

Fix all hyperparameters as in Theorem 3.1 and measure the stationarity ∥F^γ_nor(z_t)∥² after T rounds for n=20 versus n=100, and Q=10 versus Q=20, on a heterogeneous nonconvex task; the theory predicts the dominant error scales as 1/(nQ). A second check: implement a partial-participation variant and verify whether the average correction \bar c_t remains zero—if it drifts, the server update is no longer an approximate normal-map step and the bound should degrade.

Watch

Extended reading notes

Core claim

FedNMap is the first federated method with proven linear speedup for nonconvex composite optimization: to reach an ε-stationary point (measured by the normal map), the communication complexity is O((L+ρ)Δψσ²/(nQε⁴)+...) under standard assumptions. Under the proximal-PL condition, the ε-suboptimality communication complexity is Õ(Lσ²/(nQμ²ε)) in the dominant regime. The algorithm preserves unbiasedness by replacing the proximal gradient step with a normal-map step, and the correction term makes each client's transmitted direction track the global stochastic normal map. This closes the gap left by prior proximal FL methods, which either worked only in convex/strongly convex settings, assumed b

Load-bearing premise

The analysis requires every client to participate in every communication round so that the average correction term cancels exactly; if clients are subsampled, the proof's key identity fails and the claimed speedup is not established.

Editorial extensions

If this is right

  • To reach an ε-stationary point, communication rounds scale as O(Δψσ²/(nQε⁴)) in the dominant term, so doubling clients or local steps halves the required communication in that regime.
  • Under the PL condition, reaching ε-suboptimality costs Õ(Lσ²/(nQμ²ε)) communication rounds, again showing linear speedup.
  • Convergence holds without assumptions on data heterogeneity or bounded subgradients; only smoothness, weak convexity of φ, and bounded stochastic-gradient variance are needed.
  • Each client uploads one variable per round, halving uplink communication relative to two-variable correction methods.
  • Experiments on MNIST and SVHN show stationarity decreases faster as n or Q grows, matching the theoretical dependence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The zero-average correction identity \bar c_t = \bar c_0 = 0 is built on summing over all clients; under random subsampling the server no longer executes an approximate normal-map step. A natural extension would add a global control variate to preserve the correction average, and the testable prediction is that without it, partial participation loses the 1/(nQ) rate.
  • Because the unbiasedness of the normal map is local to each client's update, the same construction should transfer to decentralized or personalized composite federated settings, where only neighborhood averages replace the full-server average.
  • The 1/(nQ) scaling is equivalent to saying FedNMap behaves like a centralized composite method with an effective batch of nQ samples; a concrete test is whether its communication curve matches centralized prox-SGD with batch size nQ on the same tasks.
  • The proximal parameter γ is decoupled from the effective stepsize in the server update, which may allow adaptive or schedule-based choice of γ to improve practical convergence; the paper does not explore this.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes FedNMap, a federated algorithm for minimizing composite objectives f(x)+φ(x) with a possibly nonsmooth, weakly convex regularizer φ. Each client performs Q local normal-map-based corrected steps and transmits a single variable to the server; the server aggregates these into an approximate normal-map update. Under smooth local losses, weak convexity of φ, bounded stochastic gradient variance, and full client participation, the authors claim a nonconvex stationarity-bound communication complexity of O((L+ρ)Δψσ²/(nQε⁴)+...) and, under a proximal PL condition, a communication complexity of O~( (L+ρ)σ²/(nQεμ²)+... ). The paper also reports numerical comparisons on MNIST and SVHN against existing composite FL baselines.

Significance. The algorithmic idea—using the normal map to preserve unbiasedness and adding a SCAFFOLD-type correction—is natural and the multistep Lyapunov analysis represents a substantial technical effort. If the parameter-choice issues identified below are repaired, the nonconvex result would be a genuine contribution to composite federated learning, for which linear speedup has not previously been established. The paper is also careful to avoid bounded-subgradient or homogeneity assumptions and to use single-variable uplink communication. However, the two main parameter specializations in Theorems 3.1 and 3.2 are not valid as printed, so the stated rates are not currently derived.

major comments (2)
  1. [Theorem 3.1, Eq. (15) and Eq. (101)] The 'in particular' parameter choices in Eq. (15) are incompatible with the theorem's own conditions and with the proof. As printed, η̂ in Eq. (15) is O(√T), while the condition above (14) requires η̂ = O(1/m) = O(T^{-1/2}) for m = Θ(√T); similarly, the displayed ηa contains a term 240√((L+ρ)TQσ²/Δψ) = O(√T), whereas the condition requires ηa = O(1/(Q√m)) = O(T^{-1/4}). The proof in Eq. (101) uses the reciprocal orientations: η̂² ≤ nQΔψ/(320²(L+ρ)Tσ²) and ηa² ≤ Δψ/(240²(L+ρ)TQσ²). Thus Eq. (16) is not a consequence of Theorem 3.1 as stated. This appears to be a typographical reversal, but the theorem statement must be corrected to match the proof.
  2. [Theorem 3.2, Eqs. (19)-(21) and Remark 3.2] The PL specialization is not valid. Setting m = floor(μT/(L+ρ)) makes m = O(T), so the number of contraction blocks in the multistep proof is R = T/m = O((L+ρ)/μ), a constant independent of T. Under the theorem's step-size condition η̂ ≤ 1/[120m(L+ρ+μ)], we have η̂m = O(1), and therefore the unrolled contraction in (107)-(109) has a constant number R of factors, each bounded away from 1. The exponent -2η̂μT/(9(1+γμC0)) in (19) is consequently O(1), not O(T). The first term in (19) does not vanish as T→∞, so the rate (21) and the communication complexity in Remark 3.2 do not follow. The proof also leaves ηs unspecified in a way that would simultaneously satisfy (20) and the theorem's conditions: a constant ηs violates the η̂ bound for large T, while ηs=O(1/log T) yields no exponential decay when m=O(T). A repair such as m=o(T) is needed, with the complexity re-optimized.
minor comments (5)
  1. [Section 5] Please define the exact stationarity measure plotted in Figure 2. The text refers to ||F^γ_nat(x_t)||², but the y-axis label is only 'Stationarity' and the expression is first introduced informally in Remark 3.1.
  2. [Algorithm 1 / Section 1.3] The analysis assumes full client participation and averaging over all clients (Algorithm 1, lines 3 and 19). This is a legitimate setting, but it should be stated explicitly as a limitation; the extension to partial participation or client subsampling is not addressed.
  3. [Table 1] The FedNMap nonconvex row reports O(√(σ²/(nQT)) + 1/T), which looks like an optimization-error rate, while the text reports a communication complexity. Please align the notation and clarify which quantity is being tabulated.
  4. [Remark 3.1] The normal-map stationarity measure F^γ_nat is used before being defined. Moving its definition to Section 2 would improve readability.
  5. [Related work] The description of prior work is very brief. Please clarify the relationship between [26] and [27] and why both are classified as nonconvergent for general nonconvex composite FL, since the distinction is central to the claimed novelty.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity found; self-citations are not load-bearing and the flagged PL parameter issue is a correctness concern, not a circularity.

full rationale

The derivation is self-contained in the relevant sense. FedNMap's update rules (4)-(7) define the algorithm, and the paper proves Lemmas B.3-B.5 and Theorems 3.1-3.2 from Assumptions 1.1-1.4. The normal-map stationarity measure F_nor(z)=∇f(prox_γφ(z))+γ^{-1}(z-prox_γφ(z)) is a standard optimality measure, and the bridge to F_nat via inequality (17) is cited from prior work as a known equivalence, not as an assumption equivalent to the desired convergence. No parameter is fitted to the target rate: Theorem 3.1's parameter choices in (15) balance the terms derived in (14), and Theorem 3.2's η_a and m are explicit functions of T,n,Q,σ,Δψ; these are standard way to extract communication complexity, not a renamed fit. The correction-term identities (40)-(41), including c̄_t=0 and the approximate normal-map server update, are algebraic consequences of Algorithm 1, not additional inputs. Self-citations such as [7] and [21] are used for standard normal-map lemmas and Lyapunov-function templates; they are not invoked as uniqueness theorems, and the core recursions are proved in the appendix. The PL parameter concern raised by the skeptic about Theorem 3.2 — m≈O(T) making R=T/m constant and hence the exponential decay not following — is a genuine mathematical correctness issue in the 'in particular' parameterization, but it is not circularity: it is a failure of the stated parameter choice to deliver the claimed decay, not an equivalence-by-construction or a fitted-input-called-prediction. Thus no circular step is present; the central claims have independent content.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The proof assumes standard stochastic/smoothness/weak-convexity conditions plus full participation; there are no invented physical entities. The only hand-chosen quantities are algorithm hyperparameters and the proof block length m, and the nonconvex parameter selection is internally inconsistent.

free parameters (4)
  • γ (proximal parameter) = 1/[5(ρ+L)] in theorems; γ=1 or 2 in experiments
    Chosen by hand to balance prox nonexpansiveness and descent; not fitted to data but critical to all bounds.
  • \hatη = ηa ηs Q (effective server step) = 1/320 sqrt(σ²T(ρ+L)/(nQΔψ)) in Eq (15)
    Optimized in the rate derivation; the stated value violates the proof's own constraints for large T.
  • ηa (local step size) = 1/380 (σ²TQ³(L+ρ)³/(nΔψ))^{1/4} + 240 sqrt((L+ρ)TQσ²/Δψ) in Eq (15)
    The second term grows with T and violates the constraint ηa ≤ (1-γρ)/(70Q√(L²+1/γ²)); this is the main flaw.
  • m (multistep block length) = ceil sqrt(σ²T/(9(L+ρ)Δψ nQ)) in Eq (15)
    Proof artifact controlling the Lyapunov descent; chosen to balance error terms.
assumptions (6)
  • domain assumption Assumption 1.1: unbiased stochastic gradients with bounded variance, independent across clients and rounds.
    Used in every expectation bound, e.g., Lemma B.3 Step V and Lemma B.4.
  • domain assumption Assumption 1.2: each fi is L-smooth and ψ is bounded below.
    Needed for the descent lemma and Lipschitz continuity of the normal map (Lemma B.2).
  • domain assumption Assumption 1.3: φ is proper, lsc, and ρ-weakly convex; proxγφ is computationally tractable.
    Weak convexity gives the prox nonexpansiveness in Lemma B.1; tractability is required by Algorithm 1.
  • domain assumption Assumption 1.4 (PL theorem only): proximal-PL inequality 2µ(ψ-ψ*) ≤ dist(0,∂ψ)².
    Used in Theorem 3.2 to convert stationarity decay into function suboptimality.
  • domain assumption Full client participation and synchronous communication every round.
    Algorithm 1 loops over all n clients; Eq (40) \bar c_t = 0 requires all y_i,t to be included in the average.
  • standard math Second prox theorem and standard proximal calculus: for x=proxγφ(z), γ^{-1}(z-x)∈∂φ(x).
    Used in Eq (45) and in Lemma B.1; cited from [2] and [3].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Achieving Linear Speedup for Composite Federated Learning." pith.science (2026). https://pith.science/paper/PIZAFPZF

@misc{pith2026260203357,
  author       = {Pith},
  title        = {Pith review of: Achieving Linear Speedup for Composite Federated Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PIZAFPZF}},
  note         = {Machine review of arXiv:2602.03357}
}
read the original abstract

This paper proposes FedNMap, a normal map-based method for composite federated learning, where the objective consists of a smooth loss and a possibly nonsmooth regularizer. FedNMap leverages a normal map-based update scheme to handle the nonsmooth term and incorporates a local correction strategy to mitigate the impact of data heterogeneity across clients. Under standard assumptions, including smooth local losses, weak convexity of the regularizer, and bounded stochastic gradient variance, FedNMap achieves linear speedup with respect to both the number of clients and the number of local updates for nonconvex losses, both with and without the Polyak-{\L}ojasiewicz condition. To the best of our knowledge, this is the first algorithm establishing linear speedup for nonconvex composite federated learning. Numerical experiments corroborate our theoretical findings and demonstrate the linear speedup of FedNMap.

Figures

Figures reproduced from arXiv: 2602.03357 by the authors.

Figure 1
Figure 1. An illustration of the subsequence {tj} R j=0. 5 Numerical Experiments In this section, we evaluate the practical performance of FedNMap on composite FL tasks under heterogeneous data settings. All methods use full client participation with the same number of communication rounds and identical model initialization. 5.1 A Simple Neural Network We consider a multi-class classification task on the MNIST dataset [12] us… view at source ↗
Figure 2
Figure 2. Comparison among FedNMap, Zhang [26], and FedCanon [30] for training a one-hidden-layer neural network with an elastic net regularizer on the MNIST dataset. The stepsizes are set to ηa = 0.5/Q for local updates and ηs = 1 for the outer loop across all methods. The parameter γ in FedNMap is set to 1. 5.2 Deep Learning for Image Classification We further evaluate FedNMap on a deep neural network using the SVHN dataset… view at source ↗
Figure 3
Figure 3. Comparison of FedNMap, Zhang [26], and FedCanon [30] for training VGG-16 with an elastic net regularizer on the SVHN dataset. The stepsizes are set to ηa = 1/Q and ηs = 0.5. The number of local updates is Q ∈ {10, 20}, the number of clients is n ∈ {20, 50}, and the parameter γ in FedNMap is set to 2. and the number of local updates, covering both general nonconvex objectives and the PL condition. These results are o… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 4 linked inside Pith

  1. [1]

    Y. BAO, M. CRAWSHAW, S. LUO,ANDM. LIU,Fast composite optimization and statistical recovery in federated learning, in International Conference on Machine Learning, PMLR, 2022, pp. 1508–1536

  2. [2]

    A. BECK,First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2017, https://doi.org/10.1137/1.9781611974997, https://epubs.siam.org/doi/abs/ 10.1137/1.9781611974997, https://arxiv.org/abs/https://epubs.siam.org/doi/pdf/10.1137/ 1.9781611974997

  3. [3]

    DAVIS ANDD

    D. DAVIS ANDD. DRUSVYATSKIY,Stochastic model-based minimization of weakly convex functions, SIAM Journal on Optimization, 29 (2019), pp. 207–239

  4. [4]

    Y. GAO, A. RODOMANOV, J. RACK,ANDS. STICH,Composite optimization with error feedback: the dual averaging approach, arXiv preprint arXiv:2510.03507, (2025)

  5. [5]

    GHADIMI, G

    S. GHADIMI, G. LAN,ANDH. ZHANG,Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, Mathematical Programming, 155 (2016), pp. 267–305

  6. [6]

    HUANG, X

    K. HUANG, X. LI,ANDS. PU,Distributed stochastic optimization under a general variance condition, IEEE Transactions on Automatic Control, 69 (2024), pp. 6105–6120

  7. [7]

    HUANG, S

    K. HUANG, S. PU,ANDA. NEDI ´C,Distributed normal map-based stochastic proximal gradient methods over networks, arXiv preprint arXiv:2412.13054, (2024)

  8. [8]

    KARIMI, J

    H. KARIMI, J. NUTINI,ANDM. SCHMIDT,Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition, in Joint European conference on machine learning and knowledge discovery in databases, Springer, 2016, pp. 795–811

Show all 31 references
  1. [9]

    S. P. KARIMIREDDY, S. KALE, M. MOHRI, S. REDDI, S. STICH,ANDA. T. SURESH,Scaffold: Stochastic controlled averaging for federated learning, in International conference on machine learning, PMLR, 2020, pp. 5132–5143. 26 A Normal Map-based Federated Learning Method for Nonsmooth ...

  2. [10]

    KHALED ANDP

    A. KHALED ANDP. RICHTÁRIK,Better theory for SGD in the nonconvex world, Transactions on Machine Learning Research, (2023),https://openreview.net/forum?id=AU4qHN2VkS. Survey Certification

  3. [11]

    J. M. KÜBLER, Y.-X. WANG, S. SABACH, N. ANSARI, M. KLEINDESSNER, K. BUDHATHOKI, V. CEVHER, ANDG. KARYPIS,A proximal operator for inducing 2: 4-sparsity, arXiv preprint arXiv:2501.18015, (2025)

  4. [12]

    LECUN, L

    Y. LECUN, L. BOTTOU, Y. BENGIO,ANDP. HAFFNER,Gradient-based learning applied to document recognition, Proceedings of the IEEE, 86 (1998), pp. 2278–2324,https://doi.org/10.1109/5.726791

  5. [13]

    Y. LEI, T. HU, G. LI,ANDK. TANG,Stochastic gradient descent for nonconvex learning without bounded gradient assumptions, IEEE transactions on neural networks and learning systems, 31 (2019), pp. 4394–4400

  6. [14]

    T. LI, A. K. SAHU, A. TALWALKAR,ANDV. SMITH,Federated learning: Challenges, methods, and future directions, IEEE Signal Processing Magazine, 37 (2020), pp. 50–60

  7. [15]

    T. LI, A. K. SAHU, M. ZAHEER, M. SANJABI, A. TALWALKAR,ANDV. SMITH,Federated optimization in heterogeneous networks, Proceedings of Machine learning and systems, 2 (2020), pp. 429–450

  8. [16]

    X. LI, K. HUANG, W. YANG, S. WANG,ANDZ. ZHANG,On the convergence of fedavg on non-iid data, arXiv preprint arXiv:1907.02189, (2019)

  9. [17]

    MCMAHAN, E

    B. MCMAHAN, E. MOORE, D. RAMAGE, S. HAMPSON,ANDB. A.YARCAS,Communication-efficient learning of deep networks from decentralized data, in Artificial intelligence and statistics, PMLR, 2017, pp. 1273–1282

  10. [18]

    NETZER, T

    Y. NETZER, T. WANG, A. COATES, A. BISSACCO, B. WU, A. Y. NG,ET AL.,Reading digits in natural images with unsupervised feature learning, in NIPS workshop on deep learning and unsupervised feature learning, vol. 2011, Granada, 2011, p. 7

  11. [19]

    OUYANG ANDA

    W. OUYANG ANDA. MILZAREK,A trust region-type normal map-based semismooth newton method for nonsmooth nonconvex composite optimization: W. ouyang, a. milzarek, Mathematical Programming, 212 (2025), pp. 389–435

  12. [20]

    J. QIU, L. JIANG,ANDA. MILZAREK,A normal map-based proximal stochastic gradient method: Convergence and identification properties, arXiv e-prints, (2023), pp. arXiv–2305

  13. [21]

    J. QIU, X. LI,ANDA. MILZAREK,A new random reshuffling method for nonsmooth nonconvex finite-sum optimization, Journal of Machine Learning Research, 26 (2025), pp. 1–46

  14. [22]

    S. M. ROBINSON,Normal maps induced by linear transformations, Mathematics of Operations Research, 17 (1992), pp. 691–714

  15. [23]

    SIMONYAN ANDA

    K. SIMONYAN ANDA. ZISSERMAN,Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:1409.1556, (2014)

  16. [24]

    A. T. SURESH, X. Y. FELIX, S. KUMAR,ANDH. B. MCMAHAN,Distributed mean estimation with limited communication, in International conference on machine learning, PMLR, 2017, pp. 3329–3337

  17. [25]

    H. YUAN, M. ZAHEER,ANDS. REDDI,Federated composite optimization, in International Conference on Machine Learning, PMLR, 2021, pp. 12253–12266

  18. [26]

    ZHANG, J

    J. ZHANG, J. HU,ANDM. JOHANSSON,Composite federated learning with heterogeneous data, in ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2024, pp. 8946–8950

  19. [27]

    ZHANG, J

    J. ZHANG, J. HU,ANDM. JOHANSSON,Non-convex composite federated learning with heterogeneous data, Automatica, 183 (2026), p. 112695

  20. [28]

    ZHANG, J

    J. ZHANG, J. HU, A. M.-C. SO,ANDM. JOHANSSON,Nonconvex federated learning on compact smooth sub- manifolds with heterogeneous data, Advances in Neural Information Processing Systems, 37 (2024), pp. 109817– 109844

  21. [29]

    ZHANG, M

    X. ZHANG, M. HONG, S. DHOPLE, W. YIN,ANDY. LIU,Fedpd: A federated learning framework with adaptivity to non-iid data, IEEE Transactions on Signal Processing, 69 (2021), pp. 6055–6070

  22. [30]

    Y. ZHOU, J. ZHONG, X. SHI, G. WEN,ANDX. YU,Fedcanon: Non-convex composite federated learning with efficient proximal operation on heterogeneous data, arXiv preprint arXiv:2504.11903, (2025)

  23. [31]

    ZOU ANDT

    H. ZOU ANDT. HASTIE,Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society Series B: Statistical Methodology, 67 (2005), pp. 301–320. 27

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.