REVIEW 4 major objections 5 minor 16 references
On the Inherent Privacy of Zeroth Order Projected Gradient Descent
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper shows that the randomness built into zeroth-order gradient estimators does not make projected gradient descent differentially private, and that privacy loss grows superlinearly with the number of iterations.
desk verdict A likely-correct negative answer to the open question about inherent privacy of ZO-GD, with a fixable but real flaw in Theorem 4.1 that needs referee attention before the claims are stated cleanly. 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 load-bearing object is the oracle abstraction. A zero-preserving noisy oracle (Definition 3.1) returns the exact zero vector with probability 1 whenever the loss is identically zero, and returns a continuous probability measure at nonzero points of a quadratic loss; this atom-versus-continuous asymmetry is what makes the fixed-initialization counterexample work. The random-initialization result uses a $C_s$-anti-concentrated oracle (Definition 4.2), which requires that for linear losses with nonzero slope the update's distinguished coordinate is strictly negative with probability 1, has expectation at most the true gradient coordinate, and has second moment bounded by $C_s$ times squared mean; these properties produce a guaranteed drift away from the origin that Paley-Zygmund turns into the $T^{4/3}$ lower bound. The paper verifies that SPSA and finite-difference estimators are both zero-preserving and 3-anti-concentrated, with the coordinate distribution being a scaled $\chi^2(1)$, and that the properties are preserved under mean extensions used to reduce variance.
What would settle it
Run Algorithm 1 with SPSA or finite-difference updates on the two paired losses $L(w;X)=0$ and $L(w;X')=(L/n)\lVert w\rVert^2$, starting from a fixed $w_0$ inside the ball, and estimate the final-iterate distribution for $T=1$. The theorem predicts a point mass under $X$ and a continuous distribution with no atom at $w_0$ under $X'$; if the zero-loss run ever moves or the neighbor run puts positive probability on $w_0$, the construction fails. For the random-initialization claim, simulate the separation event $\{w_T\}_{i^*} \ge \min\{\eta L T^{2/3}/(2n), D\}$ with $w_0 \sim N(0,\sigma^2 I)$ and verify the predicted probability lower bound of order $T^{-2/3}$; a polynomially smaller observed probability would falsify the anti-concentration argument.
Extended reading notes
Core claim
The central claim is that projected zeroth-order gradient descent without additive noise has no differential privacy guarantee, no matter how the estimator is randomized. The paper defines zero-preserving noisy oracles, which return exactly $0_d$ with probability $1$ when the loss is identically zero and return a continuous distribution when queried on a nonzero quadratic loss, and proves that any such oracle already violates $(\varepsilon,\delta)$-DP for one pair of neighboring datasets (Theorem 3.3). For the full algorithm with fixed initialization, Theorem 4.1 shows the final iterate alone is enough to break privacy for any finite $\varepsilon$ and $\delta<1$: under one dataset the trajectory is deterministic, under the neighbor it is continuous, so the point mass at the initial point separates the two distributions. For random initialization, Theorem 4.5 shows that under a slightly stronger class of anti-concentrated oracles the privacy loss grows at least as $T^{4/3}$, meaning more iterations actively worsen privacy rather than helping through iteration privacy amplification.
Load-bearing premise
The entire negative result rests on the requirement that a zeroth-order estimator returns exactly the zero vector, with probability one and with no added noise, when the loss function is identically zero; if a real estimator always injects independent noise that does not vanish on zero functions, the counterexamples collapse.
Editorial extensions
If this is right
- Methods that privatize zeroth-order fine-tuning by relying on estimator randomness alone do not have a privacy guarantee; the additive Gaussian noise step in algorithms such as DPZero is load-bearing, not a technical convenience.
- Increasing the number of iterations does not amortize the privacy loss of projected ZO-GD: even with hidden iterates and random initialization, the lower bound grows superlinearly as $T^{4/3}$.
- Taking means of several zeroth-order estimates, a standard variance-reduction trick, does not restore privacy because the zero-preserving and anti-concentration properties survive mean extensions.
- In federated or distributed settings where gradient estimates are shared as updates, each zero-preserving noisy oracle query is itself non-private, so the privacy risk exists even before the optimization trajectory is aggregated.
Reading between the lines
- A cautious reading is that the zero-preserving assumption is doing essentially all the work: estimators that inject independent noise that never vanishes on zero functions fall outside the class, so the paper leaves open whether always-on noise of small variance can salvage a privacy guarantee of a different form.
- The $T^{4/3}$ lower bound is reminiscent of burn-in results for noisy SGD that say privacy loss saturates after many iterations; a natural next step, which the paper itself notes, is to determine whether projected ZO-GD has a matching upper bound under the same oracle assumptions.
- The worst-case constructions are highly separated (zero loss versus one strongly convex or linear term), so they establish impossibility of a guarantee rather than predicting typical-case leakage on realistic LLM objectives.
- The single-point SP estimator fails the anti-concentration property used in the random-initialization theorem, so a precise privacy profile for single-point methods remains an open, testable sub-question.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies whether the inherent randomness of zeroth-order gradient estimators can provide differential privacy for projected zeroth-order gradient descent without additive noise. It introduces two oracle classes: zero-preserving noisy oracles (Definition 3.1) and anti-concentrated oracles (Definition 4.2). It proves that popular estimators (SPSA, FD, SP, and their mean extensions) satisfy these properties, and then derives lower bounds: with fixed initialization, the final iterate of projected ZO-GD is not differentially private for any finite epsilon and delta < 1 (Theorem 4.1), and with random initialization the privacy loss grows at least like T^{4/3} for convex objectives (Theorem 4.5). The paper concludes that additive noise is necessary for privacy in this algorithmic family, answering an open question posed by Tang et al. (2024) and Zhang et al. (2024a).
Significance. If the results hold after necessary corrections, this is a valuable negative answer to a timely open question in private zeroth-order optimization. The oracle abstractions are a useful way to separate the privacy analysis from specific estimators, and the verification that SPSA, FD, SP, and their mean extensions belong to the proposed classes is a concrete strength. The lower-bound constructions are explicit and do not rely on fitted parameters. The paper also correctly notes that estimators with independent additive noise are outside the class, so the negative result is scoped rather than overclaimed. However, the current version contains several load-bearing mismatches between theorem statements and proofs, so the advertised conclusions are not yet established as written.
major comments (4)
- [Theorem 4.1] The theorem quantifies over all fixed initializations w0 with ||w0||_2 < D, but the proof invokes Definition 3.1(2) at w0 to conclude that the update under the neighboring dataset is continuous. Definition 3.1(2) is only asserted for w != 0. When w0 = 0, a zero-preserving oracle such as SPSA returns 0 deterministically at w = 0 for the quadratic loss (L/n)||w||^2, so both neighboring trajectories remain at w0 = 0 and the singleton {w0} has probability 1 under both datasets. The theorem is therefore false as stated; it needs an explicit w0 != 0 hypothesis.
- [Theorem 4.1 statement] The theorem promises an L-Lipschitz linear loss, but the proof constructs the strongly convex quadratic (L/n)||w||^2; the abstract and the proof agree on strong convexity. Moreover, on the constraint set [-D,D]^d, the quadratic (L/n)||w||^2 has Lipschitz constant 2LD/n, which is not L unless D <= n/2. The theorem and proof need to be aligned, for example by stating a strongly convex quadratic and scaling its coefficient so that the Lipschitz constant over the domain is L.
- [Theorem 3.3] The proof asserts that R_X' is a continuous random variable, citing Definition 3.1(2), but the query point w is never specified. Since Definition 3.1(2) excludes w = 0, the argument is invalid at w = 0; for an SPSA-like oracle the output at w = 0 is deterministic 0 for both datasets. The theorem needs a quantified w != 0 in its statement (or 'for every w != 0') to be true. As written, the universal claim about the oracle class is false.
- [Appendix C.1, proof of Theorem 4.5] The displayed application of Paley-Zygmund gives (1-alpha)^2 (E[Z])^2 / E[Z^2] >= (1-alpha)^2 / Cs; with alpha = 1/(2T^{1/3}) this is at least 1/(4Cs), not 1/(4Cs T^{2/3}), so the T^{-2/3} factor in inequality (2) does not follow. In addition, the line 'E[Z] = E[-sum {U_j}_i*] <= -sum {grad L(W_j)}_i*' has the wrong inequality: Definition 4.2(3) gives E[{U_j}_i*] <= -L/n, hence E[Z] >= LT/n, which is the direction needed for the Paley-Zygmund step. A few lines later, the inequality 'P[X'] - 1/(16CsT^{2/3}) >= sqrt(2pi)L eta/(32 n sigma Cs) e^{eta^2 L^2 T^{4/3}/(8 n^2 sigma^2)}' is not a consequence of the preceding bounds and is false for large T. These issues mean the proof does not currently establish the quantitative statement of Theorem 4.5; they need to be repaired.
minor comments (5)
- [Section 1.1] The word 'existance' should be 'existence'.
- [Theorem 3.3] The set 'LB_d' appears in the statement without definition; it should presumably be 'DB_d' matching the rest of the paper.
- [Appendix C.1, Case 2] The display 'P[W_t^{X'} /∈ S] >= ...' should be 'P[W_t^{X'} ∈ S] >= ...' based on the subsequent derivation and the definition of S.
- [Definition 4.2] Property 4 is written with 'Cs E[sum {U_j}_i*]^2'; for clarity it should be 'Cs (E[sum {U_j}_i*])^2', and the proof in Appendix D would benefit from the same explicit parentheses.
- [Theorem 4.5 discussion] The sentence after Theorem 4.5 about 'large enough D >= T^{2/3}/200' does not explain how the constants arise; the bound should be derived or the parameters should be stated more precisely.
Circularity Check
No circularity: the paper's lower bounds are explicit worst-case constructions; the oracle-class definitions are hypotheses with independent proofs for concrete estimators, not fitted or self-cited predictions.
full rationale
No significant circularity. The paper's central claims are worst-case lower bounds proved by explicit constructions (L(w;X)=0 vs L(w;X')=(L/n)||w||^2 in Theorem 3.3 and Theorem 4.1; L(w;X)=0 vs L(w;X')=-(L/n)w_i* in Theorem 4.5). The zero-preserving and anti-concentrated oracle classes are stated as hypotheses, and the paper separately proves that concrete estimators such as SPSA, FD, SP, and their mean extensions satisfy them (Lemmas 3.2, 4.3, 4.4, B.2, D.1, D.2), so the properties are not assumed as the desired conclusion. No parameter is fitted to data, no prediction is statistically forced by a fitted value, and the self-citations that do appear (e.g., Lowy and Razaviyayn 2023; Lowy et al. 2023) are contextual remarks about federated learning, not load-bearing evidence for the main theorem. The mismatch between Theorem 4.1's stated linear loss and the quadratic loss used in its proof, together with the missing w0 != 0 hypothesis, is a correctness concern rather than a circularity concern: it does not make the derivation reduce to its own inputs. Therefore no circular step can be quoted, and the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math Gaussian concentration inequality (Lemma A.1) and Paley-Zygmund inequality (Lemma A.2) hold as stated.
- domain assumption The zero-preserving noisy oracle class (Definition 3.1) captures the privacy-relevant behavior of popular ZO estimators such as SPSA, FD, and SP.
- domain assumption The anti-concentrated oracle class (Definition 4.2) captures two-point ZO estimators such as SPSA and FD under linear losses.
- domain assumption The constructed loss functions are L-Lipschitz and convex (or strongly convex) over the bounded domain.
- standard math Standard properties of chi-squared and Gaussian random variables, including the distribution of a sum of i.i.d. chi-squared(1) variables.
invented entities (2)
-
Zero-preserving noisy oracle
-
Anti-concentrated (AC) oracle
Cite this review
Pith. "Pith review of On the Inherent Privacy of Zeroth Order Projected Gradient Descent." pith.science (2026). https://pith.science/paper/2H6ODNWU
@misc{pith2026250705610,
author = {Pith},
title = {Pith review of: On the Inherent Privacy of Zeroth Order Projected Gradient Descent},
year = {2026},
howpublished = {\url{https://pith.science/paper/2H6ODNWU}},
note = {Machine review of arXiv:2507.05610}
}
read the original abstract
Differentially private zeroth-order optimization methods have recently gained popularity in private fine tuning of machine learning models due to their reduced memory requirements. Current approaches for privatizing zeroth-order methods rely on adding Gaussian noise to the estimated zeroth-order gradients. However, since the search direction in the zeroth-order methods is inherently random, researchers including Tang et al. (2024) and Zhang et al. (2024a) have raised an important question: is the inherent noise in zeroth-order estimators sufficient to ensure the overall differential privacy of the algorithm? This work settles this question for a class of oracle-based optimization algorithms where the oracle returns zeroth-order gradient estimates. In particular, we show that for a fixed initialization, there exist strongly convex objective functions such that running (Projected) Zeroth-Order Gradient Descent (ZO-GD) is not differentially private. Furthermore, we show that even with random initialization and without revealing (initial and) intermediate iterates, the privacy loss in ZO-GD can grow superlinearly with the number of iterations when minimizing convex objective functions.
Reference graph
Works this paper leans on
-
[1]
{∇h(w)}i∗ = 0 implies U = 0d w.p. 1 i.e. P [U = 0d] = 1 13
-
[2]
{∇h(w)}i∗ ̸= 0 implies P [{U }i∗ < 0] = 1
-
[3]
E [{U }i∗ ] ≤ {∇h(w)}i∗
-
[4]
Then E PN j=1{Uj}i∗ 2 ≤ CsE hPN j=1{Uj}i∗ i2 Theorem C.2
For any set of {w1, w2, ..., wN } ⊂ Rd, let Uj ∼ O(h, wj) independently for all j ∈ [N ]. Then E PN j=1{Uj}i∗ 2 ≤ CsE hPN j=1{Uj}i∗ i2 Theorem C.2. (Restated Theorem 4.5) Consider running T steps of Algorithm 1 using a Cs-AC oracle O, as defined in Definition 4.2, with D >ηL 2n and Rinit is N (0, σ2I). Assume that the algorithm only returns the final iter...
-
[10]
Using, the second property of Cs-AC oracle, we have Z = − PT j=1{Uj}i∗ ≥ 0
In the fourth inequality, we used the third property of the Cs-AC oracle in Definition 4.2 which (with linearity of expectation) implies that E [Z] = E h − PT j=1{Uj}i∗ i ≤ −PT j=1{∇L(W χ′ j ; χ′)}i∗ and the fact that {∇L(w; χ′)}i∗ = − L n for all w ∈ Rd, by our construction. Using, the second property of Cs-AC oracle, we have Z = − PT j=1{Uj}i∗ ≥ 0. Thus...
-
[11]
In the third inequality, we used the third property of the Cs-AC oracle where {∇L(·; χ′)}i∗ T ≥ E hPT j=1{Uj}i∗ i and {∇L(·; χ′)}i∗ = − L n , by our construction. In the fourth inequality, using the sec- ond property of the Cs-AC oracle, we get − PT j=1{Uj}i∗ ≥ 0, T ≥ 1. Hence, we apply Paley-Zygmund on 16 − PN j=1{Uj}i∗ and then use the fourth property o...
-
[12]
Thus, combining inequalities (d) and (e), we get that P h W X ′ t /∈ S i ≥ 1 16 ηL Dn 1 Cs (F1) Computing P W X T ∈ S This argument follows exactly from the first case. We get that P W X T ∈ S = P [{w0}i∗ ≥ D] ≤ σ√ 2πD e− D2 2σ2 (F1) Hence, using inequalities F1 and F2, we get P h W X ′ t ∈ S i − ηL 32CsDn P W X T ∈ S ≥ √ 2πηL 32Csnσ e D2 2σ2 Therefore, P...
-
[13]
Observe that when |{∇f }i∗ | = g = 0 which implies that E(f, w) = 0d, satisfying property 1
Show all 16 references
-
[14]
For the second property, V ≥ 0 which implies that gV ≤ 0 for all
-
[15]
E [V ] = 1 which implies that E {U (f )}i∗ = gE [V ] = g = |{∇f }i∗ |
-
[16]
1 m mX u=1 S2 u # = Ks Using property 4 of E, we have Ks ≤ CsK 2 f . Thus, substituting the original terms, we have E 1 m NX k=1 mX j=1 {U (f,wk) j }i∗ 2 ≤ CsE
R = PN j=1 Vj ∼ χ2(N ). Hence, we know that E [R] = N and V ar[R] = 2N, which implies that E R2 = N 2 + 2N. We also have that PN j=1{U (f ) j }i∗ = g PN j=1 Vj, which implies that E PN j=1{U (f ) j }i∗ 2 = g2(N 2 + 2N ) and E h PN j=1{U (f ) j }i∗ i2 = g2N 2. Using N ≥ 1 gives...
-
[2014]
Andrew Lowy, Jonathan Ullman, and Stephen Wright
doi: 10.1109/FOCS.2014.56. Andrew Lowy, Jonathan Ullman, and Stephen Wright. How to make the gradients small privately: Improved rates for differentially private non-convex optimization. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonat...
2014
-
[2015]
Pengyun Yue, Long Yang, Cong Fang, and Zhouchen Lin
doi: 10.1109/TIT.2015.2409256. Pengyun Yue, Long Yang, Cong Fang, and Zhouchen Lin. Zeroth-order optimization with weak dimension depen- dency. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of ...
2015
-
[2021]
Qinzi Zhang, Hoang Tran, and Ashok Cutkosky
URL https://proceedings.mlr.press/v139/asi21b.html. Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Private zeroth-order nonsmooth nonconvex optimization. In The Twelfth International Conference on Learning Representations, 2024c. URL https://openreview.net/forum? id=IzqZbNMZ0M. ...
2015 arXiv
-
[2022]
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu
URL https://openreview.net/forum?id=nZeVKeeFYf9. Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. In M. Ran- zato, A. Beygelzimer, Y . Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Pro...
2021
-
[2024]
Cynthia Dwork, Guy N
URL https://arxiv.org/abs/2406.02913. Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , FOCS ’10, page 51–60, USA, 2010a. IEEE Computer Society. ISBN 9...
2010 arXiv
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.