Locally Differentially Private Online Federated Learning With Correlated Noise

Dominik Fay; Jiaojiao Zhang; Linglingzhi Zhu; Mikael Johansson

REVIEW 3 major objections 4 minor 41 references

Locally Differentially Private Online Federated Learning With Correlated Noise

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper claims that temporally correlated noise, generated by a matrix-factorization mechanism, yields the first dynamic regret bound for locally differentially private online federated learning with local updates over a class of…

desk verdict A genuinely new dynamic regret guarantee for LDP online federated learning with correlated noise; the main argument holds up, but the privacy proof is too terse and Assumption IV.3 needs empirical grounding. read the letter →

arxiv 2411.18752 v3 pith:Y2AJ2IML submitted 2024-11-27 cs.LG cs.DCstat.ML

Jiaojiao Zhang , Linglingzhi Zhu , Dominik Fay , Mikael Johansson This is my paper · ORCID

classification cs.LGcs.DCstat.ML

keywords onlinefederatedlearninglocaldifferentialprivacycorrelatednoisematrixfactorizationmechanismdynamicregretnonconvexoptimizationadaptivecontinualreleaseupdates

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 tries to show that temporally correlated noise can protect privacy in online federated learning without wrecking performance. In this setting, data arrives as a stream and is used once, and each learner performs several local updates before communicating with a server; adding fresh independent noise at every step would swamp the learning signal. The paper's algorithm lets each learner add correlated Gaussian noise through a matrix-factorization mechanism, and the authors prove that under an $(\epsilon,\delta)$-local-differential-privacy budget the released global models still enjoy a sublinear dynamic regret bound, even for a class of nonconvex loss functions. If correct, this gives the first dynamic regret guarantee for locally private online federated learning with local updates and correlated noise, and it shows correlated noise provably beats independent noise in a certain step-size regime.

What carries the argument

The machinery is the matrix-factorization (MF) mechanism combined with a perturbed-iterate analysis. The prefix-sum matrix $A$, a lower-triangular matrix of ones, is factored as $A = B C$; each learner adds Gaussian noise $\xi_i$ to $C G_i$ and releases $B(C G_i + \xi_i)$, which is post-processing of a single Gaussian mechanism and hence private under adaptive continual release. The row norms of $B$ and $C$ control both the noise needed and its effect on utility. To keep the correlated noise from dominating, the paper defines a virtual iterate $x_r^\xi = x_r + \frac{\tilde\eta}{\tau} b_{r-1,\tau-1}\xi$ that removes the accumulated noise from the released global model; its recursion is noise-free, and the distance between $x_r^\xi$ and the optimal set is what the regret proof tracks. Assumption IV.3 transfers the resulting bound from the virtual iterate to the actually released model.

What would settle it

Compute the Lipschitz constant of the map $x \mapsto P_{X_\star}(x)$ for the logistic-regression and CNN losses used in the experiments; if it is not bounded by a moderate $\sqrt{\sigma}$ along the algorithm's iterates, Assumption IV.3 is violated and the stated regret bound for the released model does not follow.

Watch

Extended reading notes

Core claim

The central claim is Theorem IV.10: under smoothness, bounded gradients, a projection regularity condition on the optimal set, and a structural inequality on the aggregated loss, Algorithm 1 satisfies $(\epsilon,\delta)$-LDP under adaptive continual release and achieves dynamic regret $\mathrm{Regret}_d/(R\tau) \leq O\big((\ln(R\tau))^{2/3}/R^{2/3} + B_g^2/(\eta_g^2 R^{2/3}(\ln(R\tau))^{4/3}) + (1 + n/\eta_g^2)(\ln(R\tau))^{2/3} d B_g^2 \ln(1/\delta)/(R^{2/3} n \tau^2 \epsilon^2) + C_R/R\big)$ when $\tilde\eta = O(R^{-1/3}(\ln(R\tau))^{-2/3})$. Here $C_R$ measures how much the optimal solution set moves over time, and the bound is sublinear in the number of communication rounds when $C_R = o(R)$. The paper reads this as the first dynamic regret guarantee for locally differentially private online federated learning with local updates, correlated noise, and nonconvex losses.

Load-bearing premise

The load-bearing premise is Assumption IV.3, which says the projection of any point onto the (possibly nonconvex) optimal set $X_\star$ is Lipschitz with a moderate constant $\sqrt{\sigma}$; if this projection is ill-behaved, the paper's regret bound for the released model does not follow, and the paper does not verify it for the experimental problems.

Editorial extensions

If this is right

For step sizes below $\tau / ((1 + n/\eta_g^2)(\ln(R\tau))^2)$, the correlated-noise regret bound is smaller than the independent-noise bound, so the paper predicts a strict utility win for correlated noise in that regime.
The privacy-noise term decays like $(\ln(R\tau))^{2/3}/R^{2/3}$, so privacy protection does not change the sublinear order of the regret under slow environmental drift.
The dynamic-regret bound scales with $C_R/R$; when optimal points move slowly ($C_R = o(R)$), regret is sublinear, and when the environment changes too fast the bound degrades gracefully rather than failing.
Under strong convexity, the static-regret version improves the environment-change dependence to $(\ln(R\tau))^{1/2} C_R / R^{3/2}$.
Multiple local updates per communication round make the drift error scale like $\tau^2 \eta^2 B_g^2$, so the bound quantifies a limit on how large $\tau$ can be before drift dominates.

Reading between the lines

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

Because the noise construction only depends on the horizon $R$ and the number of local steps $\tau$, the same privacy argument would carry over to other factorizations of the prefix-sum matrix; tighter row-norm bounds would directly improve the regret constants, a connection the paper does not quantify.
The projection regularity assumption (IV.3) is the least checked; replacing it with a checkable condition on the gradient map, or verifying it for the experimental losses, would put the numerical results on the same footing as the theorem.
The analysis predicts an experimentally testable scaling: with a fixed privacy budget, the gap between correlated and independent noise should widen as the horizon grows and the step size shrinks, since the independent-noise bound carries an extra factor of $\tau$ in the noise term.
A parallel mechanism could release noisy model differences rather than noisy prefix sums, which would let the perturbed-iterate technique handle aggregation rules that are not prefix sums, such as momentum or adaptive steps.

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.

Desk Editor's Note

read the letter

The paper does something real: it gives the first dynamic regret bound for locally differentially private online federated learning with local updates, correlated noise, and nonconvex losses. The perturbed-iterate analysis is a legitimate new technique that lets the authors control the interaction between correlated DP noise and drift from local updates. The bound in Theorem IV.10 is explicit about how the privacy budget, number of learners, local steps, and environment drift enter, and the comparison with independent noise in Corollary IV.11 makes a clear practical point. I checked the main algebra in Lemma IV.9; the Young's inequality applications, the drift bound, and the choice theta = alpha/(12L) all line up. There are no fitted constants, and the result is not carried by self-citations.

The soft spots are real but not fatal. First, the privacy proof in Lemma IV.8 is written as if only the changed gradient's row contributes to sensitivity. In the actual trajectory, changing one client sample shifts every later local model, so the row difference is not zero. The paper's escape hatch is the citation to [8, Theorem 2.1], which can justify analyzing the non-adaptive sensitivity under adaptive continual release via composition. But the proof doesn't say that, and the reader is left to guess whether the theorem's hypotheses are met. This is a presentation gap that needs fixing: state the theorem, verify its per-step sensitivity condition under Assumption IV.2, and explain why the adaptive composition argument avoids trajectory-level sensitivity. The stress-test's stronger claim that LDP is unproven only lands if the theorem in [8] does not apply; the paper should make the application explicit enough to settle that.

Second, Assumption IV.3 is a Lipschitz condition on projections onto a possibly nonconvex optimal set. It is not implied by smoothness, and the paper gives no verification for the logistic regression or CNN experiments. The theory is conditional on it; the authors should either verify it for their test problems or label the experiments as heuristic. Third, Remark IV.13 overstates the improvement over [24, 25]: the O(R^{1/3}) rate is for the structured class satisfying Assumptions IV.3 and IV.4, not for general nonconvex problems. The remark should be tempered. Fourth, no code is released, which limits reproducibility but is not disqualifying for a theory paper.

Overall: this is a solid paper with a new and likely correct result. It deserves a serious referee. The revisions I would demand are about clarity and honesty of presentation, not about redoing the math. Yes, send it to peer review, and ask for a rewritten privacy proof and a more careful statement of what the assumptions buy.

Referee Report

3 major / 4 minor

Summary. The paper proposes an algorithm for online federated learning with local updates that adds temporally correlated Gaussian noise via a matrix factorization mechanism to guarantee local differential privacy. The central theoretical claim is Theorem IV.10: under Assumptions IV.1–IV.4 and a suitable choice of the global step size, Algorithm 1 satisfies (ε,δ)-LDP under adaptive continual release and achieves a sublinear dynamic regret bound over a class of nonconvex loss functions. The authors introduce a perturbed iterate analysis that compares the actual released models to a 'virtual' iterate from which the DP noise has been removed, and they provide numerical experiments on logistic regression and CNN training comparing binary-tree, optimized, and Toeplitz matrix factorization mechanisms.

Significance. If the main result were correct, this would be the first dynamic regret guarantee for locally differentially private online federated learning with multiple local updates and correlated noise under nonconvex losses, and the perturbed-iterate technique would be a useful contribution. The appendices contain detailed algebraic derivations, and the regret analysis in Lemma IV.9 appears internally consistent given its assumptions. However, the privacy proof contains a load-bearing gap: the sensitivity calculation treats the gradient stream as non-adaptive, whereas the local-update feedback loop in Algorithm 1 makes every later gradient depend on earlier data, so the claimed (ε,δ)-LDP guarantee and, consequently, Theorem IV.10 are not established as written.

major comments (3)

[Section IV.B, Lemma IV.8, and Appendix B] The privacy analysis computes the sensitivity as Δ = ||C(G_i−G'_i)||_F = ||c^{0,0}(∇f^{0,0}_i − ∇f^{0,0'}_i)||, arguing that changing one client sample changes only the gradient at that time step. In Algorithm 1, however, the local update in Eq. (2) is a feedback loop: replacing one sample changes z^{r,t}_i for all subsequent t in the round, changes the transmitted ĝ^r_i, changes the global model x_{r+1}, and therefore changes every later gradient for every learner. Under only Assumptions IV.1 and IV.2 (L-smoothness and bounded gradients, with no convexity or contraction), the difference between two neighboring trajectories need not decay and can grow with the horizon; the L2 sensitivity of the prefix sums can then scale with Rτ, not with max_{r,t}||c_{r,t}||. The appeal to [8, Theorem 2.1] for adaptive continual release is therefore insufficient: that theorem requires a bound on the sensitivity of the adaptive stream, and the proof does not establish such a bound—it simply assumes the one-row non-adaptive calculation. As a result, the variance V_i² in Lemma IV.8 may be too small, and the (ε,δ)-LDP claim for Algorithm 1 is unproven. This gap directly undermines Theorem IV.10, since its privacy component rests entirely on Lemma IV.8. A correct privacy argument for this algorithm must either bound the propagation of a single data change through the local-update and global-update recursion, or modify the algorithm/analysis to avoid the feedback issue (e.g., by treating the noisy prefix sums released per learner as the private outputs and analyzing the sensitivity of the entire trajectory under the assumed function class).
[Section IV.A, Assumption IV.3] Assumption IV.3 asserts a uniform bound ||P^{x_r}_{X*} − P^{x^ξ_r}_{X*}|| ≤ √σ||x_r − x^ξ_r|| for the projection onto the possibly nonconvex optimal set X*. This is used in Lemma IV.9 to transfer the distance bound from the virtual iterate x^ξ_r to the actually released model x_r, and thus the regret bound in Theorem IV.10 for the released global model depends on it. The assumption is not implied by L-smoothness and bounded gradients, and the paper does not verify it for the logistic regression or CNN problems used in the experiments. While the paper cites [31], [32] for examples, the absence of a concrete check for the actual experimental losses leaves a gap between the theory and the empirical validation. The authors should either verify this condition for the problem classes they experiment on, or state clearly that the regret bound applies only to problems satisfying this regularity condition.
[Section IV.B, proof of Lemma IV.8, line beginning 'As shown in [8, Theorem 2.1]'] The sentence claiming that the MF technique 'can protect privacy under adaptive continual release, and the parameters are the same as in the non-adaptive continual release setting' is too strong. The theorem in [8] concerns adaptive streams whose sensitivity is bounded in the appropriate sense; it does not assert that the non-adaptive sensitivity calculation automatically applies to a stream generated by a closed-loop algorithm with local updates. The proof here does not demonstrate that the hypotheses of the cited theorem are met, so the privacy guarantee cannot be treated as a corollary of [8, Theorem 2.1]. This is not merely a presentational issue; it is the logical step that connects the noise variance to (ε,δ)-LDP.

minor comments (4)

[Notation section] The definition of the matrices A, B, C, and G_i is dense and somewhat difficult to parse; a small example or a more explicit statement of the flattened indexing of the Rτ steps would help readability.
[Table I] The table uses the same bracket labels [1], [2], [3], [4], [5] both as row markers and as footnote references, which is confusing because the bibliography also has numbered entries. Please use separate labels for the footnotes.
[Section V.A, logistic regression experiments] The text says the data is generated using the method described in [38], which allows control of heterogeneity via parameters α and β; it would be helpful to report the exact values of α and β used in Figure 3, since the reader cannot infer them from the figure alone.
[Corollary IV.11] The condition for correlated noise to achieve a smaller bound than independent noise is stated as a simple inequality on η̃, but the two bounds have quite different functional forms; a short derivation of this comparison would make the claim easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem IV.10 is derived from stated structural assumptions and external, non-overlapping prior results, with no fitted parameter renamed as a prediction.

full rationale

The regret bound in Theorem IV.10 is derived from Assumptions IV.1-IV.4 through Lemmas IV.8 and IV.9. Lemma IV.8 sets the noise variance from the privacy budget and a sensitivity bound, not from the regret target; there is no fitted input called a prediction. Lemma IV.9 introduces the virtual iterate x_r^xi = x_r + (eta_tilde/tau) b_{r-1,tau-1} xi as an analytical device, not as an assumption that presupposes the regret bound. Assumption IV.4 is a structural condition on the loss functions, and the paper proves in Corollary IV.7 that it is implied by QSC, PL, EB, or QG plus weak convexity, so it is not defined in terms of the conclusion. The matrix-factorization privacy guarantee is imported from Denisov et al. [8], and the Toeplitz bounds from Henzinger et al. [15]; neither work shares authors with this paper, so no load-bearing self-citation chain is present. The skeptical concern about the privacy proof, namely that the sensitivity calculation in Lemma IV.8 considers only a single changed gradient while the local-update feedback loop in (2) could amplify sensitivity, is a potential correctness or verification gap in the adaptive continual-release argument, not a circularity: even if valid, it would invalidate the theorem rather than making the result equivalent to its own inputs by construction. No step in the derivation reduces to its inputs by definition, and no known empirical pattern is merely renamed as a contribution.

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

The regret bound is derived analytically; the only user-chosen numbers are step sizes (standard hyperparameters for which the theorem states conditions). The main load-bearing premises are the explicit assumptions IV.1-IV.4 and the cited zCDP/adaptive-MF privacy results. No new physical or mathematical entities are introduced; the virtual iterate x^ξ_r is a proof device, not a model entity.

free parameters (1)

step size η̃ (and local steps η, η_g) = O(R^{-1/3}(ln Rτ)^{-2/3})
Algorithm hyperparameters chosen by the user; the theorem states the bound for any η̃ satisfying the conditions. They are not fitted to data and not ad hoc; they are standard optimization step sizes.

assumptions (6)

domain assumption Assumption IV.1: each loss f^{r,t}_i is L-smooth.
Standard smoothness used throughout the proof of Lemma IV.9 to bound drift and gradient norms.
domain assumption Assumption IV.2: each loss has bounded gradient with norm ≤ B_g.
Used for DP sensitivity (Lemma IV.8) and for local drift bounds.
domain assumption Assumption IV.3: projection onto the optimal set X* is σ-Lipschitz in the sense of the displayed inequality.
Needed to transfer the virtual-iterate analysis to the released model; not implied by other assumptions and not verified empirically.
domain assumption Assumption IV.4: aggregated loss satisfies the inequality α(f^r(x)-(f^r)*)+<∇f^r(x),P-x>+μ/2||P-x||²≤0.
Defines the class of nonconvex losses; shown to hold for QSC and for weak convexity plus QG/PL/EB conditions (Corollary IV.7).
standard math Cited result [8, Thm 2.1]: MF mechanisms preserve privacy under adaptive continual release with the same parameters as non-adaptive release.
Basis for Lemma IV.8's claim that the LDP guarantee holds even though the gradients are adaptively computed from previous outputs.
standard math zCDP to (ε,δ)-DP conversion and Gaussian mechanism bounds [40, Prop 1.3,1.6].
Used to set the noise variance V_i² in Lemma IV.8; standard background.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Locally Differentially Private Online Federated Learning With Correlated Noise." pith.science (2026). https://pith.science/paper/Y2AJ2IML

@misc{pith2026241118752,
  author       = {Pith},
  title        = {Pith review of: Locally Differentially Private Online Federated Learning With Correlated Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y2AJ2IML}},
  note         = {Machine review of arXiv:2411.18752}
}

abstract

We introduce a locally differentially private (LDP) algorithm for online federated learning that employs temporally correlated noise to improve utility while preserving privacy. To address challenges posed by the correlated noise and local updates with streaming non-IID data, we develop a perturbed iterate analysis that controls the impact of the noise on the utility. Moreover, we demonstrate how the drift errors from local updates can be effectively managed for several classes of nonconvex loss functions. Subject to an $(\epsilon,\delta)$-LDP budget, we establish a dynamic regret bound that quantifies the impact of key parameters and the intensity of changes in the dynamic environment on the learning performance. Numerical experiments confirm the efficacy of the proposed algorithm.

Figures

Figures reproduced from arXiv: 2411.18752 by the authors.

**Figure 1.** OFL framework Traditional FL operates in an offline setting, where data is stored on learners and can be sampled IID (e.g., through This work is supported in part by the funding from Digital Futures and VR under the contract 2019-05319. Parts of the material in this paper have been published at the 63rd IEEE Conference on Decision and Control. Jiaojiao Zhang, Dominik Fay, and Mikael Johansson are with the Division o… view at source ↗

**Figure 1.** To protect privacy, each learner adds temporally cor [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Binary tree mechanism estimate the prefix sum ∇f 0,0 i +· · ·+ ∇f r,t i , which is at most log2 (Rτ ). This leads to the bounds: ∥c r,t∥ 2≤ log2 (Rτ ) + 1, ∥b r,t∥ 2≤ log2 (Rτ ), ∀r, t. (6) From C, we can calculate the noise variance V 2 i added to each node in the tree to satisfy a fixed privacy budget, while B allows us to quantify the impact of noise on the utility. Remark III.1 (Comparison with independent noise… view at source ↗

Figures from the paper (2 more)

**Figure 3.** Figure 3: Comparison on logistic regression in [38], which allows us to control the degree of heterogeneity using two parameters, α and β. In our first set of experiments, we set the dimensionality to d = 100 and use n = 20 learners. Each learner is responsible for 4000 clients,…

**Figure 4.** Figure 4: Ablation and comparison on CNN classification under [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 36 canonical work pages

[8]

Improved differential privacy for SGD via optimal private linear oper- ators on adaptive streams,

S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta, “Improved differential privacy for SGD via optimal private linear oper- ators on adaptive streams,” Advances in Neural Information Processing Systems, vol. 35, pp. 5910–5924, 2022

work page 2022
[31]

A unified approach to error bounds for structured convex optimization problems,

Z. Zhou and A. M.-C. So, “A unified approach to error bounds for structured convex optimization problems,” Mathematical Programming, vol. 165, pp. 689–728, 2017

work page 2017
[32]

Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods,

G. Li and T. K. Pong, “Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods,” Foundations of Computational Mathematics , vol. 18, no. 5, pp. 1199–1232, 2018

work page 2018
[1]

Online federated learning,

A. Mitra, H. Hassani, and G. J. Pappas, “Online federated learning,” in 2021 60th IEEE Conference on Decision and Control , 2021, pp. 4083– 4090

work page 2021
[2]

Linear speedup of incremental aggregated gradient methods on streaming data,

X. Wang, C. Jin, H.-T. Wai, and Y . Gu, “Linear speedup of incremental aggregated gradient methods on streaming data,” in 2023 62nd IEEE Conference on Decision and Control , 2023, pp. 4314–4319

work page 2023
[3]

Differentially private distributed online convex optimization towards low regret and communication cost,

J. Liu, L. Zhang, X. Yu, and X.-Y . Li, “Differentially private distributed online convex optimization towards low regret and communication cost,” in Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2023, pp. 171–180

work page 2023
[4]

Advances and open problems in federated learning,

P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings et al. , “Advances and open problems in federated learning,” Foundations and Trends® in Machine Learning , vol. 14, no. 1–2, pp. 1–210, 2021

2021
[5]

A communication-efficient adaptive algorithm for federated learning under cumulative regret,

S. Salgia, T. Gabay, Q. Zhao, and K. Cohen, “A communication-efficient adaptive algorithm for federated learning under cumulative regret,”IEEE Transactions on Signal Processing , 2024

work page 2024

Show all 41 references

[6]

Federated online deep learning for CSIT and CSIR estimation of FDD multi-user massive MIMO systems,

X. Zheng and V . Lau, “Federated online deep learning for CSIT and CSIR estimation of FDD multi-user massive MIMO systems,” IEEE Transactions on Signal Processing , vol. 70, pp. 2253–2266, 2022

2022
[7]

Practical and private (deep) learning without sampling or shuffling,

P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu, “Practical and private (deep) learning without sampling or shuffling,” in International Conference on Machine Learning , 2021, pp. 5213–5225

2021
[9]

Differential privacy: A survey of results,

C. Dwork, “Differential privacy: A survey of results,” in International Conference on Theory and Applications of Models of Computation , 2008, pp. 1–19

2008
[10]

On the tradeoff between privacy preser- vation and Byzantine-robustness in decentralized learning,

H. Ye, H. Zhu, and Q. Ling, “On the tradeoff between privacy preser- vation and Byzantine-robustness in decentralized learning,” in ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing, 2024, pp. 9336–9340

2024
[11]

Differential private discrete noise- adding mechanism: Conditions, properties and optimization,

S. Qin, J. He, C. Fang, and J. Lam, “Differential private discrete noise- adding mechanism: Conditions, properties and optimization,” IEEE Transactions on Signal Processing , 2023

2023
[12]

Private empirical risk mini- mization: Efficient algorithms and tight error bounds,

R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk mini- mization: Efficient algorithms and tight error bounds,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , 2014, pp. 464–473. 10

2014
[13]

Convergence of gradient descent with linearly correlated noise and applications to differentially private learning,

A. Koloskova, R. McKenna, Z. Charles, K. Rush, and B. McMa- han, “Convergence of gradient descent with linearly correlated noise and applications to differentially private learning,” arXiv preprint arXiv:2302.01463, 2023

2023 arXiv
[14]

Gradient descent with linearly correlated noise: Theory and applications to differential privacy,

A. Koloskova, R. McKenna, Z. Charles, J. Rush, and H. B. McMahan, “Gradient descent with linearly correlated noise: Theory and applications to differential privacy,” Advances in Neural Information Processing Systems, vol. 36, 2024

2024
[15]

Almost tight error bounds on differentially private continual counting,

M. Henzinger, J. Upadhyay, and S. Upadhyay, “Almost tight error bounds on differentially private continual counting,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2023, pp. 5003–5039

2023
[16]

Differential privacy under continual observation,

C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum, “Differential privacy under continual observation,” in Proceedings of the Forty-second ACM Symposium on Theory of Computing , 2010, pp. 715–724

2010
[17]

The price of differential privacy under continual observation,

P. Jain, S. Raskhodnikova, S. Sivakumar, and A. Smith, “The price of differential privacy under continual observation,” in International Conference on Machine Learning , 2023, pp. 14 654–14 678

2023
[18]

Federated learning with formal differ- ential privacy guarantees,

B. McMahan and A. Thakurta, “Federated learning with formal differ- ential privacy guarantees,” Google AI Blog , 2022

2022
[19]

The ma- trix mechanism: optimizing linear counting queries under differential privacy,

C. Li, G. Miklau, M. Hay, A. McGregor, and V . Rastogi, “The ma- trix mechanism: optimizing linear counting queries under differential privacy,” The VLDB journal , vol. 24, pp. 757–781, 2015

2015
[20]

Differentially private distributed online learning,

C. Li, P. Zhou, L. Xiong, Q. Wang, and T. Wang, “Differentially private distributed online learning,” IEEE transactions on knowledge and data engineering, vol. 30, no. 8, pp. 1440–1453, 2018

2018
[21]

Privacy-preserving distributed online optimization over unbalanced digraphs via subgradient rescaling,

Y . Xiong, J. Xu, K. You, J. Liu, and L. Wu, “Privacy-preserving distributed online optimization over unbalanced digraphs via subgradient rescaling,” IEEE Transactions on Control of Network Systems , vol. 7, no. 3, pp. 1366–1378, 2020

2020
[22]

Distributed online private learning of convex nondecomposable objectives,

H. Cheng, X. Liao, and H. Li, “Distributed online private learning of convex nondecomposable objectives,” IEEE Transactions on Network Science and Engineering , 2023

2023
[23]

Communication-efficient learning of deep networks from decentralized data,

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial Intelligence and Statistics , 2017, pp. 1273–1282

2017
[24]

Online non-convex learning: Following the perturbed leader is optimal,

A. S. Suggala and P. Netrapalli, “Online non-convex learning: Following the perturbed leader is optimal,” in Algorithmic Learning Theory, 2020, pp. 845–861

2020
[25]

Online learning with non-convex losses and non-stationary regret,

X. Gao, X. Li, and S. Zhang, “Online learning with non-convex losses and non-stationary regret,” in International Conference on Artificial Intelligence and Statistics , 2018, pp. 235–243

2018
[26]

Improved dynamic regret for non-degenerate functions,

L. Zhang, T. Yang, J. Yi, R. Jin, and Z.-H. Zhou, “Improved dynamic regret for non-degenerate functions,” Advances in Neural Information Processing Systems, vol. 30, 2017

2017
[27]

Distributed online non-convex optimization with composite regret,

Z. Jiang, A. Balu, X. Y . Lee, Y . M. Lee, C. Hegde, and S. Sarkar, “Distributed online non-convex optimization with composite regret,” in 2022 58th Annual Allerton Conference on Communication, Control, and Computing, 2022, pp. 1–8

2022
[28]

Improving dynamic regret in distributed online mirror descent using primal and dual information,

N. Eshraghi and B. Liang, “Improving dynamic regret in distributed online mirror descent using primal and dual information,” in Learning for Dynamics and Control Conference , 2022, pp. 637–649

2022
[29]

Personalized federated learning with differential privacy and convergence guarantee,

K. Wei, J. Li, C. Ma, M. Ding, W. Chen, J. Wu, M. Tao, and H. V . Poor, “Personalized federated learning with differential privacy and convergence guarantee,” IEEE Transactions on Information Forensics and Security, 2023

2023
[30]

Wireless federated learning with local differential privacy,

M. Seif, R. Tandon, and M. Li, “Wireless federated learning with local differential privacy,” in 2020 IEEE International Symposium on Information Theory, 2020, pp. 2604–2609

2020
[33]

Linear convergence of first order methods for non-strongly convex optimization,

I. Necoara, Y . Nesterov, and F. Glineur, “Linear convergence of first order methods for non-strongly convex optimization,” Mathematical Programming, vol. 175, pp. 69–107, 2019

2019
[34]

Gradient methods for convex minimization: better rates under weaker conditions,

H. Zhang and W. Yin, “Gradient methods for convex minimization: better rates under weaker conditions,” arXiv preprint arXiv:1303.4645 , 2013

2013 arXiv
[35]

Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condi- tion,

H. Karimi, J. Nutini, and M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condi- tion,” in Machine Learning and Knowledge Discovery in Databases , 2016, pp. 795–811

2016
[36]

Interplay between optimization and generalization of stochastic gradient descent with covariance noise,

Y . Wen, K. Luk, M. Gazeau, G. Zhang, H. Chan, and J. Ba, “Interplay between optimization and generalization of stochastic gradient descent with covariance noise,” arXiv preprint arXiv:1902.08234, p. 312, 2019

1902 arXiv
[37]

(Nearly) optimal algorithms for private online learning in full-information and bandit settings,

A. Guha Thakurta and A. Smith, “(Nearly) optimal algorithms for private online learning in full-information and bandit settings,” Advances in Neural Information Processing Systems , vol. 26, 2013

2013
[38]

Federated optimization in heterogeneous networks,

T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V . Smith, “Federated optimization in heterogeneous networks,” Proceedings of Machine Learning and Systems , vol. 2, pp. 429–450, 2020

2020
[39]

Secure and decentralized federated learning framework with non-iid data based on blockchain,

F. Zhang, Y . Zhang, S. Ji, and Z. Han, “Secure and decentralized federated learning framework with non-iid data based on blockchain,” Heliyon, vol. 10, no. 5, 2024

2024
[40]

Concentrated differential privacy: Simplifi- cations, extensions, and lower bounds,

M. Bun and T. Steinke, “Concentrated differential privacy: Simplifi- cations, extensions, and lower bounds,” in Theory of Cryptography Conference, 2016, pp. 635–658. APPENDIX A. Proof of Corollary IV .7 On the one hand, by weak convexity of f r, we have f r(y) ≥ f r(x) + ⟨∇f r...

2016
[41]

Mutiplying (12) by α ∈ (0, (c − µWC)/L) and adding the resulting inequality to (11) yields 0 ≥ α(f r(x) − (f r)⋆) + ⟨∇f r(x), Px X ⋆r −x⟩ + c − µWC − αL 2 ∥Px X ⋆r −x∥2

(11) On the other hand, we know from Assumption IV .1 that 0 ≥ 1 nτ nX i=1 τ −1X t=0 (f r,t i (x) − f r,t i (Px X ⋆r )) − L 2 ∥x − Px X ⋆r ∥2 2 = f r(x) − (f r)⋆ − L 2 ∥x − Px X ⋆r ∥2 2, (12) where we used ∇f r(Px X ⋆ r ) = 0 in the first inequality. Mutiplying (12) by α ∈ (0,...

Pith tools

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

[1] [8]

Improved differential privacy for SGD via optimal private linear oper- ators on adaptive streams,

S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta, “Improved differential privacy for SGD via optimal private linear oper- ators on adaptive streams,” Advances in Neural Information Processing Systems, vol. 35, pp. 5910–5924, 2022

work page 2022

[2] [31]

A unified approach to error bounds for structured convex optimization problems,

Z. Zhou and A. M.-C. So, “A unified approach to error bounds for structured convex optimization problems,” Mathematical Programming, vol. 165, pp. 689–728, 2017

work page 2017

[3] [32]

Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods,

G. Li and T. K. Pong, “Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods,” Foundations of Computational Mathematics , vol. 18, no. 5, pp. 1199–1232, 2018

work page 2018

[4] [1]

Online federated learning,

A. Mitra, H. Hassani, and G. J. Pappas, “Online federated learning,” in 2021 60th IEEE Conference on Decision and Control , 2021, pp. 4083– 4090

work page 2021

[5] [2]

Linear speedup of incremental aggregated gradient methods on streaming data,

X. Wang, C. Jin, H.-T. Wai, and Y . Gu, “Linear speedup of incremental aggregated gradient methods on streaming data,” in 2023 62nd IEEE Conference on Decision and Control , 2023, pp. 4314–4319

work page 2023

[6] [3]

Differentially private distributed online convex optimization towards low regret and communication cost,

J. Liu, L. Zhang, X. Yu, and X.-Y . Li, “Differentially private distributed online convex optimization towards low regret and communication cost,” in Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2023, pp. 171–180

work page 2023

[7] [4]

Advances and open problems in federated learning,

P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings et al. , “Advances and open problems in federated learning,” Foundations and Trends® in Machine Learning , vol. 14, no. 1–2, pp. 1–210, 2021

2021

[8] [5]

A communication-efficient adaptive algorithm for federated learning under cumulative regret,

S. Salgia, T. Gabay, Q. Zhao, and K. Cohen, “A communication-efficient adaptive algorithm for federated learning under cumulative regret,”IEEE Transactions on Signal Processing , 2024

work page 2024