Pith. sign in

REVIEW 2 major objections 4 minor 85 references

The Sketched Gaussian Mechanism makes the sketch dimension itself shrink the privacy noise, with epsilon scaling like 1/sqrt(b).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-04 21:05 UTC pith:IY4OPOCT

load-bearing objection The mechanism-level Rényi analysis is a genuine new result, but Fed-SGM's client-level privacy claim relies on keeping the sketching matrix secret, and Algorithm 2 gives it to every client—so the headline FL privacy amplification doesn't hold as written. the 2 major comments →

arxiv 2509.08195 v1 pith:IY4OPOCT submitted 2025-09-09 cs.LG cs.DC

Sketched Gaussian Mechanism for Private Federated Learning

Qiaobo Li , Zhijie Chen , Arindam Banerjee This is my paper
classification cs.LG cs.DC
keywords federated learningdifferential privacyGaussian mechanismsketchingRényi differential privacyclient-level privacycommunication efficiencyprivacy amplification
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper introduces the Sketched Gaussian Mechanism (SGM), which applies an isometric Gaussian sketch before the usual Gaussian privacy noise. It claims that when analyzed jointly through Rényi differential privacy, the required noise variance for a fixed privacy level decreases as the sketch dimension b grows, roughly as 1/sqrt(b). If true, this means a communication-saving compression step also amplifies privacy, so a system can achieve the same differential privacy guarantee with substantially less added Gaussian noise and without restricting the sketch size to be much smaller than the model dimension. The paper then embeds SGM into federated learning, proves client-level privacy, and gives convergence bounds that grow only logarithmically in the model size.

Core claim

The paper's central claim is that sketching and Gaussian noise act together, not independently: with an isometric Gaussian sketch matrix R and Gaussian noise xi, the SGM output for an aggregate update gamma is a zero-mean Gaussian with covariance (||gamma||^2/b + m sigma_g^2) I_b. Because neighbouring datasets can differ by at most a clipped norm tau, the Rényi divergence between the two output distributions depends only on the ratio of these variances, which is bounded by a term of order tau^2/(b sigma_g^2). Optimizing the Rényi order and composing over T steps yields epsilon = O(1/(sqrt(b) sigma_g^2)), so the privacy loss improves with larger sketch dimension at fixed noise. Applying this

What carries the argument

The load-bearing object is the isometric Gaussian sketching matrix R, a b-by-d matrix whose entries are i.i.d. N(0, 1/sqrt(b)), composed as R theta + xi with Gaussian noise xi. The crucial identity is that, when randomness in R is marginalized out, the sketched output is N(0, (||theta||^2/b + m sigma_g^2) I_b), so the difference between neighbouring datasets appears only through the scalar ratio ||theta(D')||^2 / ||theta(D)||^2. The paper formalizes this as ratio sensitivity, rsens_c(theta) = sup_{D,D'} sqrt((||theta(D')||^2+c^2)/(||theta(D)||^2+c^2)), and shows the Rényi divergence is a monotone function of that ratio, bounded by alpha^2 tau^4 / ((alpha-1) b sigma_g^4). That ratio bound is

Load-bearing premise

The central privacy bound requires that the adversary does not know the sketching matrix: the proof averages over R_t as hidden randomness, but the federated protocol reveals R_t to clients (they need it to invert the aggregate), so the claimed client-level privacy amplification relies on an unstated secrecy assumption that a client adversary likely violates.

What would settle it

Run Fed-SGM with a fixed, known sketching matrix R, pick two neighbouring clipped updates that differ by a vector concentrated in the row space of R, and compute the Rényi divergence between the two revealed sketches N(R gamma, m sigma_g^2 I) and N(R gamma', m sigma_g^2 I). If that divergence exceeds b f_alpha(1 + 2 tau^2/(b sigma_g^2)) for some unit direction, the 1/sqrt(b) amplification bound fails for a known sketch; a small script with d=100, b=10, and tau=1 would settle it.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • For a fixed Gaussian noise budget, the privacy guarantee strictly improves as the sketch dimension b grows, so a communication-compressing sketch also acts as a privacy amplifier.
  • At the same privacy level, SGM needs less added Gaussian noise than the standard Gaussian mechanism whenever b is large enough; the crossover condition is made explicit in the paper.
  • In federated learning, Fed-SGM achieves client-level differential privacy with a noise bound that has no restrictive upper limit on b, covering practical settings where b is a fixed fraction of the model dimension.
  • The optimization analysis shows sketching introduces convergence error that grows only logarithmically in d when the loss Hessian has small absolute intrinsic dimension, so the method scales to high-dimensional models.
  • With a fixed privacy cost, Fed-SGM matches or beats non-sketching private FL baselines in the reported experiments, and adaptive server optimizers add accuracy without weakening the guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The privacy analysis as written treats the sketching matrix R_t as secret randomness that the adversary cannot condition on; the federation protocol in Algorithm 2 broadcasts the aggregate sketch back to clients, and clients use R_t^T to invert it, so a client adversary plausibly knows R_t. Conditioned on a known R_t, the per-step output is N(R_t gamma, m sigma_g^2 I), whose divergence is mean-bas
  • A testable fix would keep R_t secret from everyone except the aggregator (for example via secure aggregation), or redefine the protocol so that R_t is never revealed; then the privacy claim would hold but the communication model would change, since clients could no longer locally desketch.
  • Without such a fix, the honest reading is that the 1/sqrt(b) amplification result is a statement about the randomized mechanism with hidden sketch randomness, and applying it to client-level federated privacy requires an additional and currently unstated secrecy assumption on R_t.
  • A direct empirical check would fix an R_t, pick two neighboring updates differing by a vector aligned with the row space of R_t, compute the actual Rényi divergence of the two revealed sketches, and compare it with b f_alpha(1 + 2 tau^2/(b sigma_g^2)); exceeding that bound would settle whether the amplification survives a known sketch.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. This paper proposes a Sketched Gaussian Mechanism (SGM) that first applies a random Gaussian sketch R ∈ R^{b×d} and then adds Gaussian noise, and analyzes the combined mechanism under Rényi differential privacy. The main theoretical result (Theorem 3.2) states that for Algorithm 1 the noise variance needed for (ε_p, δ_p)-DP scales as σ_g² ≥ c q τ² √T log(2qT/δ_p) / (√b ε_p), giving a 1/√b privacy amplification relative to the standard Gaussian mechanism. The paper then embeds SGM into a federated learning protocol (Fed-SGM, Algorithm 2), claims a client-level privacy guarantee (Theorem 4.1), derives convergence bounds under a Hessian spectral assumption, and reports experiments on EMNIST and SST-2 showing that Fed-SGM requires less Gaussian noise than unsketched DP-FedAvg at the same privacy level.

Significance. Conditional on the RDP computation being valid, the mechanism-level 1/√b scaling is an interesting and non-obvious contribution. The derivation is from first principles and does not appear circular; the subsampling/composition steps are standard. The convergence analysis using the absolute intrinsic dimension of the Hessian is a useful addition, and the experimental study is extensive. However, the central federated-learning claim depends on treating the sketching matrix R_t as secret randomness, while Algorithm 2 reveals R_t to every client for desketching. This makes the client-level privacy guarantee of Theorem 4.1 unsupported. The mechanism-level Theorem 3.2 may still be of independent interest for settings where R_t is genuinely hidden, but the paper's headline claim for private federated learning is not established.

major comments (2)
  1. [§4.1, Theorem 4.1; Algorithm 2; Lemma 3.1] Theorem 4.1 is asserted as a direct application of Theorem 3.2, but Algorithm 2 is not Algorithm 1. In Algorithm 1 the sketch is consumed internally and R_t is never output. In Algorithm 2, every client applies R_t to sketch and later applies R_t^T to the broadcast aggregate to desketch; hence every client knows R_t. Lemma 3.1 marginalizes over R_t, giving divergence b f_α(·) between zero-mean Gaussians. For a client who knows R_t, the per-round aggregate is Gaussian with mean proportional to R_t γ and covariance η_local² σ_g²/N I_b (up to scaling). The conditional Rényi divergence between neighboring client sets is α ||R_t δ||²/(2 σ_eff²), with E||R_t δ||² = ||δ||² ≤ τ². This conditional divergence is independent of b in expectation and unbounded in the worst case, so the 1/√b amplification in Eq. (5) does not hold for the protocol as written. The proof of Theorem 4.1 is missing, and th
  2. [§5, 'Privacy Level and Noise calculation'] The experimental noise levels for Fed-SGM (e.g., σ_g ≈ 0.088–0.258 for the vision task versus 0.8–4 for the unsketched baselines) are computed from the RDP analysis that marginalizes over R_t. Since that marginal analysis is invalid for client adversaries under Algorithm 2, the reported privacy levels for Fed-SGM are not supported. The comparison with DP-FedAvg and the claim that 'Fed-SGM attains the same privacy guarantee with strictly lower Gaussian noise variance' therefore rest on the same invalid privacy accounting. If the intended guarantee is only against an adversary that does not know R_t, the threat model should be stated explicitly and the privacy levels recalculated under that model.
minor comments (4)
  1. [Introduction] Typo: 'cleints' should be 'clients'; also 'Due to space limit, we present our discussion on related works in Appendix 2' should refer to Section 2, not an appendix.
  2. [Section 4] Two theorems are numbered Theorem 4.1: the privacy guarantee and the informal convergence theorem. The second should be renumbered (e.g., Theorem 4.2).
  3. [Algorithm 2] The notation \hatΔ_{c,t}(x_i) in the SGM step is confusing: \hatΔ_{c,t} is a per-client update vector, not a per-example quantity.
  4. [Appendix E] Figures 13 and 14 have identical captions, both reading 'Language task, ε_p = 0.12'. One of the captions is likely incorrect.

Circularity Check

0 steps flagged

No circular derivation: the SGM privacy bound is a self-contained RDP computation; the flagged R_t-secrecy issue is an assumption gap, not circular reasoning.

full rationale

The paper's central result (Theorem 3.2, Eq. 2) is derived from first principles: Lemma 3.1 computes the Rényi divergence between the marginal distributions N(0,(||γ||²/b + mσ_g²)I) and N(0,(||γ'||²/b + mσ_g²)I), Lemma 3.2 bounds this by α²τ⁴/((α−1)bσ_g⁴) using only the clipping bound ||γ||≤mτ, and Theorem B.8 then applies standard RDP-to-DP conversion, subsampling, and composition. No fitted parameter is renamed as a prediction and no target privacy value is fed back into the proof. The convergence analysis is similarly conditional on explicitly stated Assumptions 1–4; the Hessian-spectrum assumption is empirical support, not an input-equivalent conclusion. The paper even states a limitation ('our analysis is currently limited to isotropic Gaussian sketching matrices'), which is not circular. The reader-identified issue is real but different: Algorithm 2 broadcasts the aggregate ('Broadcast ¯˜∆t to the clients') and has clients compute 'θ_{t+1} ← GLOBAL OPT(θ_t, R_t^T ¯˜∆t, η_global)', so R_t is available to clients (and likely the server); Theorem 4.1's client-level guarantee therefore relies on an unstated secrecy assumption on R_t. That is an assumption/validity gap in the reduction from Algorithm 2 to Theorem 3.2, not a case where the conclusion is defined or fitted in terms of the premises. Self-citations ([4], [15]) occur only as related work or empirical support and are not load-bearing. Hence no significant circularity; score 1.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central privacy theorem rests on standard RDP composition tools and on an unstated secrecy assumption for the sketching matrix. The convergence results rest on bounded gradients, sub-Gaussian noise, smoothness, and Hessian intrinsic dimension assumptions. No free parameters are fitted to data. No new physical or conceptual entities are invented. The ratio sensitivity is a new definition but functions as a proof device, not an invented entity.

axioms (5)
  • domain assumption Assumption 1: bounded loss gradients, ||∇L_c(θ)|| ≤ G.
    Used throughout the convergence analysis in Appendices C and D to bound gradient inner products and martingale differences.
  • domain assumption Assumption 2: stochastic noise is sub-Gaussian with parameter σ_s.
    Used for Hoeffding and Azuma bounds on the stochastic gradient noise terms in the convergence proof.
  • domain assumption Assumption 3: each client loss is L-smooth (bounded largest Hessian eigenvalue).
    Used in the Taylor expansion analysis and Hessian term bounds in Appendices C and D.
  • domain assumption Assumption 4: the absolute intrinsic dimension of the Hessian, Σ|λ_i|/max λ_i, is bounded by I.
    Central to the convergence bound's logarithmic dependence on d; the paper cites empirical power-law Hessian spectra to justify it.
  • ad hoc to paper The sketching matrix R_t is secret, i.e., the adversary does not know it, so the marginal distribution over R_t and ξ_t can be used for Rényi divergence.
    Lemma 3.1 computes divergence between marginals over R_t; Algorithm 2 broadcasts the sketch and requires clients to apply R_t^T, so a client adversary would know R_t. This secrecy is not stated or proved.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Sketched Gaussian Mechanism for Private Federated Learning." pith.science (2026). https://pith.science/paper/IY4OPOCT

@misc{pith2026250908195,
  author       = {Pith},
  title        = {Pith review of: Sketched Gaussian Mechanism for Private Federated Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IY4OPOCT}},
  note         = {Machine review of arXiv:2509.08195}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Communication cost and privacy are two major considerations in federated learning (FL). For communication cost, gradient compression by sketching the clients' transmitted model updates is often used for reducing per-round communication. For privacy, the Gaussian mechanism (GM), which consists of clipping updates and adding Gaussian noise, is commonly used to guarantee client-level differential privacy. Existing literature on private FL analyzes privacy of sketching and GM in an isolated manner, illustrating that sketching provides privacy determined by the sketching dimension and that GM has to supply any additional desired privacy. In this paper, we introduce the Sketched Gaussian Mechanism (SGM), which directly combines sketching and the Gaussian mechanism for privacy. Using R\'enyi-DP tools, we present a joint analysis of SGM's overall privacy guarantee, which is significantly more flexible and sharper compared to isolated analysis of sketching and GM privacy. In particular, we prove that the privacy level of SGM for a fixed noise magnitude is proportional to $1/\sqrt{b}$, where $b$ is the sketching dimension, indicating that (for moderate $b$) SGM can provide much stronger privacy guarantees than the original GM under the same noise budget. We demonstrate the application of SGM to FL with either gradient descent or adaptive server optimizers, and establish theoretical results on optimization convergence, which exhibits only a logarithmic dependence on the number of parameters $d$. Experimental results confirm that at the same privacy level, SGM based FL is at least competitive with non-sketching private FL variants and outperforms them in some settings. Moreover, using adaptive optimization at the server improves empirical performance while maintaining the privacy guarantees.

Figures

Figures reproduced from arXiv: 2509.08195 by Arindam Banerjee, Qiaobo Li, Zhijie Chen.

Figure 1
Figure 1. Figure 1: (a)(b) Comparison of Fed-SGM with ADAM, Fed-SGM with GD, DP-FedAvg and its Adam variant [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a)(b) Comparison of Fed-SGM with ADAM, Fed-SGM with GD, DP-FedAvg and its Adam variant [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3-5
Figure 3-5. Figure 3-5: Furthermore, in Figure 6, with a fixed privacy level [PITH_FULL_IMAGE:figures/full_fig_p054_3-5.png] view at source ↗
Figure 3
Figure 3. Figure 3: Vision Task: EMNIST, ϵp = 2.75 54 [PITH_FULL_IMAGE:figures/full_fig_p054_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Vision Task: EMNIST, ϵp = 0.42 0 100 200 300 400 500 Communication Round 20% 40% 60% 80% Train Accuracy sgd-4e5 sgd-no adam-4e5 adam-no DiffSketch (a) Training Accuracy 0 100 200 300 400 500 Communication Round 20% 40% 60% 80% Test Accuracy sgd-4e5 sgd-no adam-4e5 adam-no DiffSketch (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p055_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Vision Task: EMNIST, ϵp = 0.18 100 200 300 400 500 Communication Round 65% 70% 75% 80% 85% 90% Train Accuracy 4e4 4e5 4e6 4e7 (a) Training Accuracy 100 200 300 400 500 Communication Round 65% 70% 75% 80% 85% Test Accuracy 4e4 4e5 4e6 4e7 (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p055_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Vision task: EMNIST, ϵp = 1, 60, Comparison with Different Sketching Dimensions 55 [PITH_FULL_IMAGE:figures/full_fig_p055_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Vision task: MNIST, ϵp = 2.75 0 100 200 300 400 500 Communication Round 65% 70% 75% 80% 85% 90% 95% 100% Train Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (a) Training Accuracy 0 100 200 300 400 500 Communication Round 70% 75% 80% 85% 90% 95% 100% Test Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p056_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Vision task: MNIST, ϵp = 1.60 0 100 200 300 400 500 Communication Round 40% 50% 60% 70% 80% 90% 100% Train Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (a) Training Accuracy 0 100 200 300 400 500 Communication Round 40% 50% 60% 70% 80% 90% 100% Test Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p056_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Vision task: MNIST, ϵp = 0.42 56 [PITH_FULL_IMAGE:figures/full_fig_p056_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Vision task: MNIST, ϵp = 0.18 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Train Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (a) Training Accuracy 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Test Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p057_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Language task, ϵp = 2.45 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Train Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (a) Training Accuracy 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Test Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p057_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Language task, ϵp = 0.35 57 [PITH_FULL_IMAGE:figures/full_fig_p057_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Language task, ϵp = 0.12 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Train Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (a) Training Accuracy 0 50 100 150 200 Communication Round 50% 60% 70% 80% 90% Test Accuracy sgd-2e5 sgd-no adam-2e5 adam-no (b) Test Accuracy [PITH_FULL_IMAGE:figures/full_fig_p058_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Language task, ϵp = 0.12 58 [PITH_FULL_IMAGE:figures/full_fig_p058_14.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

85 extracted references · 59 canonical work pages · 4 internal anchors

  1. [1]

    Understanding clipping for federated learning: Convergence and client-level differential privacy

    Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. InInternational Conference on Machine Learning (ICML), 2022

    2022

  2. [2]

    Private and Communication-Efficient Federated Learning based on Differentially Private Sketches

    Meifan Zhang, Zhanhong Xie, and Lihua Yin. Private and communication-efficient federated learning based on differentially private sketches.arXiv preprint arXiv:2410.05733, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  3. [3]

    Sketching for first order method: efficient al- gorithm for low-bandwidth channel and vulnerability

    Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang. Sketching for first order method: efficient al- gorithm for low-bandwidth channel and vulnerability. InInternational Conference on Machine Learning, pages 32365–32417. PMLR, 2023

    2023

  4. [4]

    Sketching for distributed deep learning: A sharper analysis

    Mayank Shrivastava, Berivan Isik, Qiaobo Li, Sanmi Koyejo, and Arindam Banerjee. Sketching for distributed deep learning: A sharper analysis. InThe Thirty-eighth Annual Conference on Neural Infor- mation Processing Systems (NeurIPS), 2024. 12

    2024

  5. [5]

    Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang

    Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

    2016

  6. [6]

    Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. InConference on Learning Theory, pages 1579–1613. PMLR, 2019

    2019

  7. [7]

    Wainwright, Peter L

    Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947–2997. PMLR, 2020

    work page 2020

  8. [8]

    Finding frequent items in data streams

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 693–703. Springer, 2002

    work page 2002

  9. [9]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography Conference (TCC), pages 265–284. Springer, 2006

    2006

  10. [10]

    Geyer, Tassilo Klein, and Moin Nabi

    Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective.arXiv preprint arXiv:1712.07557, 2017

    Pith/arXiv arXiv 2017

  11. [11]

    D2P-Fed: Differentially private federated learning with effi- cient communication.arXiv preprint arXiv:2006.13039, 2020

    Lun Wang, Ruoxi Jia, and Dawn Song. D2P-Fed: Differentially private federated learning with effi- cient communication.arXiv preprint arXiv:2006.13039, 2020

    Pith/arXiv arXiv 2006

  12. [12]

    Federated learning with Bayesian differential privacy

    Aleksei Triastcyn and Boi Faltings. Federated learning with Bayesian differential privacy. In2019 IEEE International Conference on Big Data (Big Data), pages 2587–2596. IEEE, 2019

    work page 2019

  13. [13]

    Ilse C. F. Ipsen and Arvind K. Saibaba. Stable rank and intrinsic dimension of real and complex matrices.arXiv preprint arXiv:2407.21594, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  14. [14]

    An investigation into neural net optimization via Hessian eigenvalue density

    Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. InInternational Conference on Machine Learning, pages 2232–2241. PMLR, 2019

    work page 2019

  15. [15]

    Hessian based analysis of SGD for deep nets: Dynamics and generalization

    Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of SGD for deep nets: Dynamics and generalization. InProceedings of the 2020 SIAM International Conference on Data Mining, pages 190–198. SIAM, 2020

    work page 2020

  16. [16]

    Sophia: A scalable stochastic second-order optimizer for language model pre-training.arXiv preprint arXiv:2305.14342, 2023

    Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training.arXiv preprint arXiv:2305.14342, 2023

    Pith/arXiv arXiv 2023

  17. [17]

    Eigenvalues of the Hessian in deep learning: Singular- ity and beyond.arXiv preprint arXiv:1611.07476, 2016

    Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the Hessian in deep learning: Singular- ity and beyond.arXiv preprint arXiv:1611.07476, 2016

    Pith/arXiv arXiv 2016

  18. [18]

    Zhenyu Liao and Michael W. Mahoney. Hessian eigenspectra of more realistic nonlinear models. Advances in Neural Information Processing Systems, 34:20104–20117, 2021

    work page 2021

  19. [19]

    On the power-law Hessian spectrums in deep learning.arXiv preprint arXiv:2201.13011, 2022

    Zeke Xie, Qian-Yuan Tang, Yunfeng Cai, Mingming Sun, and Ping Li. On the power-law Hessian spectrums in deep learning.arXiv preprint arXiv:2201.13011, 2022

    Pith/arXiv arXiv 2022

  20. [20]

    Why trans- formers need Adam: A Hessian perspective.arXiv preprint arXiv:2402.16788, 2024

    Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhi-Quan Luo. Why trans- formers need Adam: A Hessian perspective.arXiv preprint arXiv:2402.16788, 2024

    Pith/arXiv arXiv 2024

  21. [21]

    Communication-efficient learning of deep networks from decentralized data

    Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. InArtificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017. 13

    work page 2017

  22. [22]

    FedNL: Making Newton-type meth- ods applicable to federated learning.arXiv preprint arXiv:2106.02969, 2021

    Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richt´arik. FedNL: Making Newton-type meth- ods applicable to federated learning.arXiv preprint arXiv:2106.02969, 2021

    Pith/arXiv arXiv 2021

  23. [23]

    Momentum provably improves error feed- back!Advances in Neural Information Processing Systems, 36, 2024

    Ilyas Fatkhullin, Alexander Tyurin, and Peter Richt ´arik. Momentum provably improves error feed- back!Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  24. [24]

    FetchSGD: Communication-efficient federated learning with sketching

    Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-efficient federated learning with sketching. InInternational Conference on Machine Learning, pages 8253–8265. PMLR, 2020

    work page 2020

  25. [25]

    Diederik P . Kingma. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    Pith/arXiv arXiv 2014

  26. [26]

    Adaptive methods for nonconvex optimization.Advances in Neural Information Processing Systems, 31, 2018

    Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization.Advances in Neural Information Processing Systems, 31, 2018

    2018

  27. [27]

    Improved convergence of differential private SGD with gradient clipping

    Huang Fang, Xiaoyun Li, Chenglin Fan, and Ping Li. Improved convergence of differential private SGD with gradient clipping. InThe Eleventh International Conference on Learning Representations (ICLR), 2023

    work page 2023

  28. [28]

    Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning

    Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In2019 IEEE Symposium on Security and Privacy (SP), pages 739–753. IEEE, 2019

    work page 2019

  29. [29]

    Information leaks in federated learning

    Anastasia Pustozerova and Rudolf Mayer. Information leaks in federated learning. InProceedings of the Network and Distributed System Security Symposium (NDSS), volume 10, page 122, 2020

    work page 2020

  30. [30]

    DBA: Distributed backdoor attacks against federated learning

    Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. DBA: Distributed backdoor attacks against federated learning. InInternational Conference on Learning Representations (ICLR), 2019

    work page 2019

  31. [31]

    IDLG: Improved deep leakage from gradients

    Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. IDLG: Improved deep leakage from gradients. arXiv preprint arXiv:2001.02610, 2020

    Pith/arXiv arXiv 2001

  32. [32]

    Deep leakage from gradients.Advances in Neural Information Processing Systems, 32, 2019

    Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  33. [33]

    Andersen, Jun Woo Park, Alexander J

    Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 583–598, 2014

    work page 2014

  34. [34]

    Brendan McMahan, Brendan Avent, Aur ´elien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al

    Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aur ´elien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning.Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021

    work page 2021

  35. [35]

    Andersen, Alexander J

    Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server.Advances in Neural Information Processing Systems, 27, 2014

    work page 2014

  36. [36]

    Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J. Dally. Deep gradient compression: Re- ducing the communication bandwidth for distributed training.arXiv preprint arXiv:1712.01887, 2017

    Pith/arXiv arXiv 2017

  37. [37]

    Atomo: Communication-efficient learning via atomic sparsification.Advances in Neural In- formation Processing Systems, 31, 2018

    Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-efficient learning via atomic sparsification.Advances in Neural In- formation Processing Systems, 31, 2018. 14

    work page 2018

  38. [38]

    Inan, Berivan Isik, Ayfer Ozgur, and Tsachy Weissman

    Leighton Pate Barnes, Huseyin A. Inan, Berivan Isik, Ayfer Ozgur, and Tsachy Weissman. rTop-k: A statistical estimation approach to distributed SGD.IEEE Journal on Selected Areas in Information Theory, 1(3):897–907, 2020

    work page 2020

  39. [39]

    QSGD: Communication- efficient SGD via gradient quantization and encoding.Advances in Neural Information Processing Sys- tems, 30, 2017

    Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding.Advances in Neural Information Processing Sys- tems, 30, 2017

    work page 2017

  40. [40]

    Communication-efficient federated learning for heteroge- neous edge devices based on adaptive gradient quantization

    Heting Liu, Fang He, and Guohong Cao. Communication-efficient federated learning for heteroge- neous edge devices based on adaptive gradient quantization. InIEEE INFOCOM 2023, pages 1–10. IEEE, 2023

    work page 2023

  41. [41]

    FedPAQ: A communication-efficient federated learning method with periodic averaging and quanti- zation

    Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication-efficient federated learning method with periodic averaging and quanti- zation. InInternational Conference on Artificial Intelligence and Statistics, pages 2021–2031. PMLR, 2020

    work page 2021

  42. [42]

    Communication-efficient distributed SGD with sketching.Advances in Neural Information Processing Systems, 32, 2019

    Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Ion Stoica, Raman Arora, et al. Communication-efficient distributed SGD with sketching.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  43. [43]

    Stich, Jean-Baptiste Cordonnier, and Martin Jaggi

    Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory.Ad- vances in Neural Information Processing Systems, 31, 2018

    work page 2018

  44. [44]

    LDP-Fed: Federated learning with local differential privacy

    Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. LDP-Fed: Federated learning with local differential privacy. InProceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pages 61–66, 2020

    work page 2020

  45. [45]

    A hybrid approach to privacy-preserving federated learning

    Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to privacy-preserving federated learning. InProceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pages 1–11, 2019

    work page 2019

  46. [46]

    Canonne, Gautam Kamath, and Thomas Steinke

    Cl ´ement L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy.Advances in Neural Information Processing Systems, 33:15676–15688, 2020

    work page 2020

  47. [47]

    Sparse communication for distributed gradient descent.arXiv preprint arXiv:1704.05021, 2017

    Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent.arXiv preprint arXiv:1704.05021, 2017

    Pith/arXiv arXiv 2017

  48. [48]

    Yu, Sanjiv Kumar, and H

    Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. InInternational Conference on Machine Learning, pages 3329–

    work page

  49. [49]

    TernGrad: Ternary gradients to reduce communication in distributed deep learning.Advances in Neural Informa- tion Processing Systems, 30, 2017

    Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning.Advances in Neural Informa- tion Processing Systems, 30, 2017

    work page 2017

  50. [50]

    Drive: One-bit distributed mean estimation.Advances in Neural Information Processing Sys- tems, 34:362–377, 2021

    Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzen- macher. Drive: One-bit distributed mean estimation.Advances in Neural Information Processing Sys- tems, 34:362–377, 2021

    work page 2021

  51. [51]

    Masked training of neural networks with partial gradients

    Amirkeivan Mohtashami, Martin Jaggi, and Sebastian Stich. Masked training of neural networks with partial gradients. InInternational Conference on Artificial Intelligence and Statistics, pages 5876–

    work page

  52. [52]

    PowerSGD: Practical low-rank gradient compression for distributed optimization.Advances in Neural Information Processing Systems, 32, 2019

    Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  53. [53]

    SketchML: Accelerating distributed machine learning with data sketches

    Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. SketchML: Accelerating distributed machine learning with data sketches. InProceedings of the 2018 International Conference on Management of Data (SIGMOD), pages 1269–1284, 2018. 15

    work page 2018

  54. [54]

    Sparse random networks for communication-efficient federated learning.arXiv preprint arXiv:2209.15328, 2022

    Berivan Isik, Francesco Pase, Deniz Gunduz, Tsachy Weissman, and Michele Zorzi. Sparse random networks for communication-efficient federated learning.arXiv preprint arXiv:2209.15328, 2022

    Pith/arXiv arXiv 2022

  55. [55]

    LotteryFL: Per- sonalized and communication-efficient federated learning with lottery ticket hypothesis on non-iid datasets.arXiv preprint arXiv:2008.03371, 2020

    Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. LotteryFL: Per- sonalized and communication-efficient federated learning with lottery ticket hypothesis on non-iid datasets.arXiv preprint arXiv:2008.03371, 2020

    Pith/arXiv arXiv 2008

  56. [56]

    FedMask: Joint computation and communication-efficient personalized federated learning via heterogeneous masking

    Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. FedMask: Joint computation and communication-efficient personalized federated learning via heterogeneous masking. InProceedings of the 19th ACM Conference on Embedded Networked Sensor Systems (SenSys), pages 42–55, 2021

    work page 2021

  57. [57]

    An improved data stream summary: the count-min sketch and its applications.Journal of Algorithms, 55(1):58–75, 2005

    Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications.Journal of Algorithms, 55(1):58–75, 2005

    work page 2005

  58. [58]

    Space-efficient online computation of quantile summaries

    Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2):58–66, 2001

    work page 2001

  59. [59]

    Kane and Jelani Nelson

    Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss transforms.Journal of the ACM (JACM), 61(1):1–23, 2014

    work page 2014

  60. [60]

    Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher

    Joel A. Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketching algorithms for low-rank matrix approximation.SIAM Journal on Matrix Analysis and Applications, 38(4):1454–1485, 2017

    work page 2017

  61. [61]

    Graph sketches: sparsification, spanners, and subgraphs

    Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. InProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 5–14, 2012

    work page 2012

  62. [62]

    Asymptotics for sketching in least squares regression.Advances in Neural Information Processing Systems, 32, 2019

    Edgar Dobriban and Sifan Liu. Asymptotics for sketching in least squares regression.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  63. [63]

    FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching

    Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. FedSketch: Communication-efficient and private federated learning via sketching.arXiv preprint arXiv:2008.04975, 2020

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  64. [64]

    Choquette-Choo, Peter Kairouz, and Ananda Theertha Suresh

    Wei-Ning Chen, Christopher A. Choquette-Choo, Peter Kairouz, and Ananda Theertha Suresh. The fundamental price of secure aggregation in differentially private federated learning. InInternational Conference on Machine Learning, pages 3056–3089. PMLR, 2022

    work page 2022

  65. [65]

    The algorithmic foundations of differential privacy.Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014

    Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy.Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014

    work page 2014

  66. [66]

    Yang, Farhad Farokhi, Shi Jin, Tony Q

    Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis.IEEE Transactions on Information Forensics and Security, 15:3454–3469, 2020

    work page 2020

  67. [67]

    Brendan McMahan, Sar- var Patel, Daniel Ramage, Aaron Segal, and Karn Seth

    Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sar- var Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. InProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1175–1191, 2017

    work page 2017

  68. [68]

    1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs

    Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. InInterspeech, volume 2014, pages 1058–1062, 2014

    work page 2014

  69. [69]

    An elementary proof of a theorem of Johnson and Linden- strauss.Random Structures & Algorithms, 22(1):60–65, 2003

    Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Linden- strauss.Random Structures & Algorithms, 22(1):60–65, 2003. 16

    work page 2003

  70. [70]

    Group normalization

    Yuxin Wu and Kaiming He. Group normalization. InProceedings of the European Conference on Com- puter Vision (ECCV), pages 3–19, 2018

    work page 2018

  71. [71]

    Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su. Deep learning with Gaussian differential privacy. Harvard Data Science Review, 2020(23), 2020

    work page 2020

  72. [72]

    Adaptive subgradient methods for online learning and stochastic optimization.Journal of Machine Learning Research, 12(7), 2011

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization.Journal of Machine Learning Research, 12(7), 2011

    2011

  73. [73]

    Divide the gradient by a running average of its recent magni- tude

    Tijmen Tieleman and Geoffrey Hinton. Divide the gradient by a running average of its recent magni- tude. Coursera: Neural networks for machine learning. Technical report, 2017

    work page 2017

  74. [74]

    Matthew D. Zeiler. ADADELTA: An adaptive learning rate method.arXiv preprint arXiv:1212.5701, 2012

    Pith/arXiv arXiv 2012

  75. [75]

    Adaptive gradient methods with dynamic bound of learning rate.arXiv preprint arXiv:1902.09843, 2019

    Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate.arXiv preprint arXiv:1902.09843, 2019

    Pith/arXiv arXiv 1902

  76. [76]

    Brendan McMahan

    Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization.arXiv preprint arXiv:2003.00295, 2020

    Pith/arXiv arXiv 2003

  77. [77]

    R ´enyi differential privacy

    Ilya Mironov. R ´enyi differential privacy. In2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017

    work page 2017

  78. [78]

    Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches

    Tian Li, Zaoxing Liu, Vyas Sekar, and Virginia Smith. Privacy for free: Communication-efficient learning with differential privacy using sketches.arXiv preprint arXiv:1911.00972, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1911

  79. [79]

    On measures of entropy and information

    Alfr ´ed R´enyi. On measures of entropy and information. InProceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961

    work page 1961

  80. [80]

    Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney. PyHessian: Neural networks through the lens of the Hessian. In2020 IEEE International Conference on Big Data (Big Data), pages 581–590. IEEE, 2020

    work page 2020

Showing first 80 references.

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.