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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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.
- [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.
- [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.
- [Remark 3.1] The normal-map stationarity measure F^γ_nat is used before being defined. Moving its definition to Section 2 would improve readability.
- [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
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
free parameters (4)
- γ (proximal parameter) =
1/[5(ρ+L)] in theorems; γ=1 or 2 in experiments
- \hatη = ηa ηs Q (effective server step) =
1/320 sqrt(σ²T(ρ+L)/(nQΔψ)) in Eq (15)
- ηa (local step size) =
1/380 (σ²TQ³(L+ρ)³/(nΔψ))^{1/4} + 240 sqrt((L+ρ)TQσ²/Δψ) in Eq (15)
- m (multistep block length) =
ceil sqrt(σ²T/(9(L+ρ)Δψ nQ)) in Eq (15)
assumptions (6)
- domain assumption Assumption 1.1: unbiased stochastic gradients with bounded variance, independent across clients and rounds.
- domain assumption Assumption 1.2: each fi is L-smooth and ψ is bounded below.
- domain assumption Assumption 1.3: φ is proper, lsc, and ρ-weakly convex; proxγφ is computationally tractable.
- domain assumption Assumption 1.4 (PL theorem only): proximal-PL inequality 2µ(ψ-ψ*) ≤ dist(0,∂ψ)².
- domain assumption Full client participation and synchronous communication every round.
- standard math Second prox theorem and standard proximal calculus: for x=proxγφ(z), γ^{-1}(z-x)∈∂φ(x).
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
Reference graph
Works this paper leans on
-
[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
2022
-
[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]
DAVIS ANDD
D. DAVIS ANDD. DRUSVYATSKIY,Stochastic model-based minimization of weakly convex functions, SIAM Journal on Optimization, 29 (2019), pp. 207–239
2019
-
[4]
Y. GAO, A. RODOMANOV, J. RACK,ANDS. STICH,Composite optimization with error feedback: the dual averaging approach, arXiv preprint arXiv:2510.03507, (2025)
arXiv 2025
-
[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
2016
-
[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
2024
- [7]
-
[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
2016
Show all 31 references
-
[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 ...
2020
-
[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
2023
-
[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)
2025 arXiv
-
[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
1998 doi
-
[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
2019
-
[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
2020
-
[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
2020
-
[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)
1907 arXiv
-
[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
2017
-
[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
2011
-
[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
2025
-
[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
2023
-
[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
2025
-
[22]
S. M. ROBINSON,Normal maps induced by linear transformations, Mathematics of Operations Research, 17 (1992), pp. 691–714
1992
-
[23]
SIMONYAN ANDA
K. SIMONYAN ANDA. ZISSERMAN,Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:1409.1556, (2014)
2014 arXiv
-
[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
2017
-
[25]
H. YUAN, M. ZAHEER,ANDS. REDDI,Federated composite optimization, in International Conference on Machine Learning, PMLR, 2021, pp. 12253–12266
2021
-
[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
2024
-
[27]
ZHANG, J
J. ZHANG, J. HU,ANDM. JOHANSSON,Non-convex composite federated learning with heterogeneous data, Automatica, 183 (2026), p. 112695
2026
-
[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
2024
-
[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
2021
-
[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)
2025
-
[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
2005
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.