{"id":"cd960f9b-5ee8-4ed3-8a74-0569fca2175f","arxiv_id":"2509.04668","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"DP-SCO with Tsybakov noise and bounded gradient moments is claimed to achieve excess risk ((r(1/sqrt(n)+sqrt(d)/(n eps))^{(k-1)/k}))^{theta/(theta-1)} with high probability, but the lower bound proof violates the paper's own moment assumption.","lead":"Differentially private stochastic convex optimization is analyzed for losses with a Tsybakov noise condition and heavy-tailed gradients, yielding rates that do not depend on the Lipschitz constant. The paper claims both new upper bounds and a matching lower bound, but the lower bound proof contains a mathematical error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bound construction in Theorem 4 violates Assumption 1: the zero atom makes the sup-gradient moment unbounded, so the claimed lower bound is unproven.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing error: the lower bound construction in Theorem 4 uses the false inequality E[sup ||∇f||^k] ≤ E[||2x||^k], which fails because the zero atom contributes a positive sup-gradient. My stress-test confirms this with a concrete numerical check. This error is not a matter of consensus or strength of assumptions; it is an internal inconsistency in the proof of the lower bound. The abstract's claim of a near-optimal private minimax rate depends on this lower bound (in conjunction with the upper bound). Without it, the paper only provides upper bounds and fails to demonstrate optimality. Additional issues (privacy proof's epsilon conversion, the r_{2k} vs r_k gap) further weaken the paper, but the lower bound flaw is sufficient to reject. Therefore the reader's verdict of REJECT is appropriate; no change needed.","tokens_in":31443,"tokens_out":4991,"duration_ms":48335,"concrete_test":"Specialize the construction of Theorem 4 to d=1, θ=2, k=2, r_k=1, p=1/2. Then r = (p^{-1/k} r_k/2)^{1/(θ-1)} = 1/√2. Compute E[sup_{|w|≤r} ||∇f(w,x)||^2] explicitly: for x=0 (prob 1/2), sup = r^2 = 1/2; for x=±1/√2 (prob 1/2), sup = (|x|+r)^2 = 2. The expectation is 1/4 + 1 = 1.25 > 1 = r_k^2, violating Assumption 1. If desired, repeat for p = 1/n, showing the violation worsens as p→0.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim of near-optimal rates rests on both upper and lower bounds. The lower bound (Theorem 4) constructs distributions Q_v supported on {0} ∪ {± p^{-1/k} r_k/(2√d)}^d and loss f(w,x) = -<w,x> + (1/θ)||w||^θ. The proof then asserts (Eq. 16) E[sup_{w∈W} ||∇f(w,x)||^k] ≤ E[||2x||^k] = r_k^k, which is false. For x=0 (probability 1-p), sup_{w∈W} ||∇f(w,0)|| = sup_{w∈W} ||w||^{θ-1} = r^{θ-1} = p^{-1/k} r_k/2, which is positive and growing as p shrinks. For x≠0, the sup is ||x|| + r^{θ-1} = p^{-1/k} r_k. Therefore E[sup ||∇f||^k] = (1-p) p^{-1} r_k^k / 2^k + p·p^{-1} r_k^k = r_k^k [(1-p)/(2^k p) + 1], which exceeds r_k^k for all p<1. Since p = √d/(n√ρ) is typically small, the constructed distribution does not satisfy Assumption 1. Consequently, the lower bound does not hold for the stated function class, and the abstract's claim that the rate is nearly minimax optimal is without support. The upper bounds may be salvageable, but the paper's central contribution—the private minimax rate under TNC—is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies differentially private stochastic convex optimization (DP-SCO) when the population risk satisfies the Tsybakov Noise Condition (TNC) and the loss is not uniformly Lipschitz, but the supremum of the gradient over the domain has a bounded k-th moment (Assumption 1). It proposes localized clipped/noisy SGD algorithms (Algorithms 3--5) giving high-probability excess-population-risk bounds of order (\\tilde{r}_{2k}(1/\\sqrt{n} + (\\sqrt{d}/(n\\varepsilon))^{(k-1)/k}))^{\\theta/(\\theta-1)}, and a shuffled clipped accelerated SGD (Algorithms 6--7) for the non-Lipschitz case when \\varepsilon is small. It also claims a \\rho-zCDP minimax lower bound of order (\\tilde{r}_k(1/\\sqrt{n} + (\\sqrt{d}/(n\\sqrt{\\rho}))^{(k-1)/k}))^{\\theta/(\\theta-1)} for \\theta \\ge 2. The abstract and introduction present the upper and lower bounds as establishing near-optimal private minimax rates under TNC.","tokens_in":31943,"tokens_out":11249,"duration_ms":111306,"significance":"If the results were correct, they would constitute a substantial advance: DP-SCO rates under TNC would no longer depend on the Lipschitz constant, high-probability (rather than expectation) guarantees would be obtained for heavy-tailed gradients, and the rates would match known lower bounds up to the moment-index gap. The algorithmic ideas—localized regularization together with clipping and stability-based privacy analysis—are interesting and potentially useful. However, the lower-bound construction in Theorem 4 fails to satisfy the paper's own Assumption 1, so the claimed near-optimality is not established. Since the lower bound is a central advertised contribution and is used to justify the title's claim, this is a load-bearing error rather than a presentation issue.","major_comments":[{"comment":"The construction does not satisfy Assumption 1. For x=0 (probability 1-p), sup_{w in W} ||∇f(w,0)|| = r^{θ-1} = p^{-1/k} r_k/2, since ∇f(w,0)=||w||^{θ-2}w and W=B_r. Hence E[sup_w ||∇f(w,x)||^k] ≥ (1-p)(p^{-1/k}r_k/2)^k ≈ r_k^k/(2^k p), which blows up as p → 0. For x≠0, sup_w ||∇f(w,x)|| = ||x|| + r^{θ-1} ≈ p^{-1/k}r_k, while ||2x|| = p^{-1/k}r_k/√d, so the inequality in Eq. (16) also fails pointwise on the support. The distribution Q_v therefore does not belong to F^θ_k with parameter r_k, and Theorem 4's Ω((r_k(√d/(n√ρ))^{(k-1)/k})^{θ/(θ-1)}) lower bound is unproven.","section":"Theorem 4, Eq. (16)"},{"comment":"The privacy accounting is internally inconsistent. The proof states that each iterate w_i is ε^2/2-zCDP and hence (2ε√log(1/δ), δ)-DP, then says that by the assumption ε ≤ √log(1/δ) 'the mechanism is (ε^2, δ)-DP, by taking ε'=ε^2.' This does not establish the claimed (ε,δ)-DP guarantee; it redefines the privacy parameter. Since Theorems 1--5 and 7 rely on this privacy guarantee, the proof needs a corrected and unambiguous composition argument.","section":"Theorem 1, privacy proof"},{"comment":"The advertised independence of the Lipschitz constant is qualified in a way that needs stating. The theorems require L_f ≤ n^{p/2} R_{2k,n}(1/√n + (√(d log(1/δ))/(ε n))^{(k-1)/k}) with p a free hyperparameter. Because Algorithm 3 sets T_i = Θ(1/(λ_i η_i)) = Θ(n_i^p), letting p grow with L_f to cover non-polynomial Lipschitz constants makes the iteration count super-polynomial; if p is fixed, L_f is at most polynomial in n. The manuscript should clarify this trade-off explicitly. Separately, Assumption 1 is a sup-over-W moment condition, which is much stronger than pointwise gradient moment bounds; the lower-bound construction shows that this difference is not innocuous.","section":"Theorems 1--3, Assumption on L_f"}],"minor_comments":[{"comment":"The sentence 'A comparison to the non-private setting will be included in the final version of the paper' is a placeholder that should have been resolved before publication; if the comparison is already present elsewhere, it should be cited explicitly.","section":"Section 2"},{"comment":"The lower-bound rows for 'This paper' use ε in the displayed rates, while Theorem 4 is stated for ρ-zCDP with √ρ. The table should consistently use ρ and should indicate that the lower bound is for zCDP rather than (ε,δ)-DP.","section":"Table 1"},{"comment":"Even ignoring the zero-atom issue, E[||2x||^k] for the stated distribution equals r_k^k/d^{k/2}, not r_k^k, because ||2x|| = p^{-1/k}r_k/√d on the nonzero atom. The displayed identity is therefore doubly incorrect.","section":"Theorem 4, Eq. (16)"},{"comment":"The notation is confusing: the statement mixes \tilde r(k), \tilde e_k^1, and r^{(k)}. The intended chain of inequalities should be written as \tilde r(k)=\tilde e_1^{(k)} ≥ \tilde e_2^{(k)} ≥ ... ≥ r^{(k)}.","section":"Proof of Lemma 2"},{"comment":"There are numerous typos and spelling errors ('deomenstrate', 'Thorem', 'especilally', 'paratemter', 'dateset', 'Comparion', 'withour'). A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The paper is already published in TMLR, but as a referee for this version I cannot recommend acceptance. The main reason is the invalid lower-bound construction: Eq. (16) fails on the zero atom, so the claimed ρ-zCDP minimax lower bound is not proven. The upper bounds may be salvageable, but the paper's central near-optimality claim rests on the lower bound. This is more than a local typo; a different construction or a substantial weakening of the stated claim would be required."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper has two halves of unequal quality. The upper-bound half is real work. Nobody had combined the Tsybakov noise condition with bounded-moment heavy-tailed gradients in DP-SCO, and getting the final excess risk to drop the Lipschitz constant — plus the small-ε non-Lipschitz extension — is a legitimate step. The localized clipped-gradient machinery (Algorithms 3, 5, 6, 7) is nontrivial, and the high-probability bounds go beyond the expectation-form results in Lowy-Razaviyayn. Credit where earned: the r_{2k} vs r_k moment gap is stated openly, and Theorem 7 honestly attempts to close it in the shuffling regime.\n\nThe lower-bound half does not survive contact. Theorem 4 puts a zero atom in the data distribution (x = 0 with probability 1-p) and then asserts E[sup_{w∈W} ||∇f(w,x)||^k] ≤ E[||2x||^k] = r_k^k. At x = 0 the gradient is ||w||^{θ-1}, whose supremum over W = B_r is r^{θ-1} = p^{-1/k} r_k / 2 — positive, and growing as p shrinks. So E sup ||∇f||^k ≈ r_k^k / p, which violates Assumption 1 for any p < 1. Since p = d/(n√ρ) is the regime the theorem targets, the privacy term of the claimed minimax lower bound is unproven. The stress-test note is right about this, and it matters: the abstract sells the rate as nearly minimax optimal, and that claim now rests on the upper bounds alone.\n\nTwo smaller soft spots. Assumption 1 is E sup_w ||∇f||^k, stronger than the usual sup_w E ||∇f||^k in the heavy-tailed DP-SCO literature, and the worked example (ℓ4 regression with x truncated at [-n,n]^d) does not obviously satisfy it — the sup-moment there grows with n. The privacy proof in Theorem 1 also contains a conversion that doesn't parse: a (2ε√(log(1/δ)), δ) guarantee becomes (ε², δ) 'by taking ε' = ε²', which is the wrong direction under the stated assumption. Probably a constants fix, but as written it's wrong.\n\nNet: the upper-bound results are novel, substantive, and probably salvageable; the minimax claim in the abstract should not be taken at face value. This deserves a serious referee — the right outcome is a major revision, not a desk reject — but anyone citing it should cite the upper bounds and treat Theorem 4 as open until repaired.","headline":"The upper bounds are a genuine advance in heavy-tailed DP-SCO under TNC, but the Theorem 4 lower bound is broken as written: the zero-atom construction violates the paper's own Assumption 1.","tokens_in":32368,"tokens_out":6523,"would_cite":true,"duration_ms":58476,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For heavy-tailed losses satisfying the Tsybakov Noise Condition, differentially private stochastic convex optimization can achieve rates that do not depend on the Lipschitz constant, with a near-matching private lower bound.","keywords":["differentially private stochastic convex optimization","heavy-tailed gradients","Tsybakov noise condition","gradient moment bounds","minimax rates","zero-concentrated differential privacy","clipped gradient descent"],"falsifier":"A concrete check is to evaluate the lower-bound construction in Theorem 4 for the atom x=0: on that draw, sup_{w in B_r} ||grad f(w,x)|| equals r^{theta-1}, which is positive, so the proof's bound E[sup_W ||grad f||^k] <= E[||2x||^k] does not account for the zero atom's contribution. If that inequality fails for the constructed distributions, the lower-bound theorem needs a corrected construction or a revised moment argument.","tokens_in":31361,"feed_emoji":"🔒","tokens_out":8808,"duration_ms":84659,"temperature":0.7,"pith_summary":"Standard differentially private stochastic convex optimization (DP-SCO) assumes a bounded, often O(1), Lipschitz constant, which excludes heavy-tailed data. This paper tries to remove that assumption: under the Tsybakov Noise Condition (a growth condition on the population risk near its optimum) and a bounded k-th gradient moment, it constructs (epsilon, delta)-DP algorithms whose excess population risk is of order (r_{2k}(1/sqrt(n) + (sqrt(d)/(n eps))^{(k-1)/k}))^{theta/(theta-1)} with high probability, with no factor coming from the Lipschitz constant. For small privacy budget it even drops Lipschitzness entirely, using a shuffled clipped accelerated method; and it proves an Omega((r_k(1/sqrt(n)+(sqrt(d)/(n sqrt(rho)))^{(k-1)/k}))^{theta/(theta-1)}) lower bound for rho-zCDP, leaving only the r_{2k}-versus-r_k moment-index gap between upper and lower bounds. If right, privacy-preserving learning on heavy-tailed data can match the rates previously reserved for nicely bounded gradients whenever the population risk has the TNC structure.","feed_headline":"DP-SCO rates freed from Lipschitz constant under Tsybakov noise","feed_subtitle":"Bounded gradient moments suffice for near-optimal privacy-utility tradeoffs, even for unbounded losses at small epsilon.","key_machinery":"The load-bearing object is the localized noisy clipped gradient method (LNC-GM): data are split into log n disjoint blocks; on block i, a clipped, strongly regularized empirical objective is minimized over a ball of exponentially shrinking radius around the previous iterate, and Gaussian noise is calibrated from the stability of the clipped gradient descent rather than from a Lipschitz constant. The clip threshold is set by r_{2k,n_i} and the privacy budget, so both bias and stability depend on moment terms instead of L_f. The Tsybakov Noise Condition enters through a phase recursion: each phase halves the distance to the optimum, and the distance-accuracy trade-off is converted to excess ri","core_discovery":"The central claim is that DP-SCO rates under the Tsybakov Noise Condition are governed by gradient moments rather than by the Lipschitz parameter. Let r_k denote the k-th root of the k-th moment of the gradient norm. For Lipschitz losses with theta >= 2, the localized noisy clipped gradient method (Algorithm 4) yields F(w)-F(w*) = O~((R_{2k,n}(n^{-1/2}+(sqrt(d log(1/delta))/(eps n))^{(k-1)/k}))^{theta/(theta-1)}) with probability 1-beta, and the Lipschitz constant never appears in the bound. Iterating the same base algorithm (Algorithm 5) extends this to theta >= theta-bar > 1. When eps is small, the non-Lipschitz PNCA-SGD (Algorithm 6) attains the same rate with r_k replacing R_{2k,n}, in e","pith_inferences":["Editorial inference: the remaining gap between r_{2k} in the upper bounds and r_k in the lower bounds suggests the Lipschitz-case upper bound may be improvable to r_k, possibly by a variance-reduced or sharper localization of the base algorithm.","Editorial inference: Assumption 1 places the supremum over the whole parameter space inside the expectation; we suspect the rates still hold under pointwise moment bounds E[||grad f(w,x)||^k] <= r_k for each w, which would cover unbounded domains, but the current proof would need a different high-probability stability argument.","Editorial inference: since TNC with theta near 1 produces very slow rates and the algorithms require a known lower bound theta-bar, a natural extension is an online or adaptive estimator of theta that avoids fixing theta-bar in advance.","Editorial inference: the lower-bound construction uses sparse distributions with an atom at zero, so empirically the rate may be driven by rare large-gradient events; a synthetic experiment with such distributions could test whether the predicted rates appear in practice before deploying on real heavy-tailed data."],"forward_implications":["For theta=2, which covers strongly convex population risks, the bound matches the known nearly optimal heavy-tailed DP-SCO rate while removing the Lipschitz dependence.","Losses such as l1/l4-norm linear regression and l2-regularized logistic regression, which satisfy TNC, inherit these rates even when their gradients are heavy-tailed.","The lower bound shows that any rho-zCDP algorithm must pay at least this rate, so the polynomial structure (1/sqrt(n) + (sqrt(d)/(n eps))^{(k-1)/k}) with the theta/(theta-1) exponent is intrinsic to the problem.","When epsilon is sufficiently small, Lipschitzness is unnecessary; the same rate is achievable for non-Lipschitz smooth losses, removing a long-standing assumption in DP-SCO.","The upper-bound algorithms are one-pass and use Gaussian noise, so they extend to zCDP by replacing sqrt(log(1/delta))/eps with 1/sqrt(rho), as the paper notes."],"supporting_citations":[{"why":"Supplies the base clipped-gradient moment bound, the moment notation (r_k, R_{k,n}), and the non-smooth heavy-tailed DP-SCO rates that the new algorithms start from.","marker":"Lowy & Razaviyayn, 2023"},{"why":"Provides the non-private localized TNC rate and the phased stochastic-approximation template that Algorithms 4 and 5 adapt to privacy and heavy tails.","marker":"Liu et al., 2018"},{"why":"Defines the Tsybakov Noise Condition and supplies the lemma relating Lipschitz constants to distance-to-optimum, used throughout the analysis.","marker":"Ramdas & Singh, 2012"},{"why":"Gives the heavy-tailed DP-SCO upper and lower rates and the private Fano lemma that the lower-bound proofs rely on.","marker":"Kamath et al., 2021"},{"why":"Yields privacy amplification by shuffling, which lets the non-Lipschitz PNCA-SGD algorithm work at small epsilon.","marker":"Feldman et al., 2022"},{"why":"Establishes zCDP and the Gaussian-mechanism and zCDP-to-DP conversions used for the lower-bound definition and the privacy guarantees.","marker":"Bun & Steinke, 2016"},{"why":"Provides the high-probability uniform stability bound used to convert stability of clipped gradient descent into excess risk in the localization proof.","marker":"Feldman & Vondrak, 2019"},{"why":"Represents prior DP-SCO rates under TNC with O(1)-Lipschitz losses; the paper's claim is that the Lipschitz term can be removed from those rates.","marker":"Asi et al., 2021b"}],"fun_headline_variants":["DP-SCO rates escape Lipschitz via Tsybakov noise moments","Tsybakov noise lets DP-SCO drop Lipschitz assumption","Gradient moments, not Lipschitz, dictate private SCO rates","No Lipschitz needed: DP-SCO with Tsybakov noise"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is Assumption 1: the k-th moment of the worst-case gradient over the whole parameter space, E[sup_{w in W} ||grad f(w,x)||^k], must be finite; moreover, in the Lipschitz theorems the Lipschitz constant must grow at most polynomially in n.","fun_headline_variants_meta":{"raw":{"variants":["DP-SCO rates escape Lipschitz via Tsybakov noise moments","Tsybakov noise lets DP-SCO drop Lipschitz assumption","Gradient moments, not Lipschitz, dictate private SCO rates","No Lipschitz needed: DP-SCO with Tsybakov noise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000597,"raw_usage":{"total_tokens":2757,"prompt_tokens":997,"completion_tokens":1760,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":1692}},"tokens_in":741,"tokens_out":1760,"duration_ms":11965,"temperature":1.0,"reasoning_tokens":1692,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:57:49.419760+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check is to evaluate the lower-bound construction in Theorem 4 for the atom x=0: on that draw, sup_{w in B_r} ||grad f(w,x)|| equals r^{theta-1}, which is positive, so the proof's bound E[sup_W ||grad f||^k] <= E[||2x||^k] does not account for the zero atom's contribution. If that inequality fails for the constructed distributions, the lower-bound theorem needs a corrected construction or a revised moment argument.","supporting_citations":[{"cited_title":"Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses","cited_arxiv_id":null,"evidence_quote":"Supplies the base clipped-gradient moment bound, the moment notation (r_k, R_{k,n}), and the non-smooth heavy-tailed DP-SCO rates that the new algorithms start from."},{"cited_title":"Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions","cited_arxiv_id":"1805.04577","evidence_quote":"Provides the non-private localized TNC rate and the phased stochastic-approximation template that Algorithms 4 and 5 adapt to privacy and heavy tails."},{"cited_title":"Optimal rates for first-order stochastic convex optimization under Tsybakov noise condition","cited_arxiv_id":"1207.3012","evidence_quote":"Defines the Tsybakov Noise Condition and supplies the lemma relating Lipschitz constants to distance-to-optimum, used throughout the analysis."},{"cited_title":"Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data","cited_arxiv_id":"2106.01336","evidence_quote":"Gives the heavy-tailed DP-SCO upper and lower rates and the private Fano lemma that the lower-bound proofs rely on."},{"cited_title":"Concentrated differential privacy: Simplifications, extensions, and lower bounds","cited_arxiv_id":null,"evidence_quote":"Establishes zCDP and the Gaussian-mechanism and zCDP-to-DP conversions used for the lower-bound definition and the privacy guarantees."},{"cited_title":"High probability generalization bounds for uniformly stable algorithms with nearly optimal rate","cited_arxiv_id":null,"evidence_quote":"Provides the high-probability uniform stability bound used to convert stability of clipped gradient descent into excess risk in the localization proof."}],"review_version":1}