{"id":"a0101ff8-73d1-470e-852d-fe0464206177","arxiv_id":"2505.20189","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A new (epsilon, delta)-DP algorithm computes an alpha-multiplicative geometric median approximation in O~(nd + d/alpha^2) time, matching the optimal sample complexity of prior work.","lead":"This paper gives a faster differentially private algorithm for computing the geometric median, a robust average that is insensitive to outliers. The new method matches the optimal sample requirement of prior work while cutting runtime from roughly quadratic to nearly linear in the dataset size.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's sample bound is not implied by the radius-estimation analysis: Lemma 6 requires n ≳ (1/ε) log log(R/r), which Theorem 4 omits.","rationale":"After reading the proof, the clearest internal inconsistency is between Theorem 4's sample-complexity statement and the hypothesis of Lemma 6. The paper's own introduction hides R/r in the polylog factor (footnote 2), but the formal theorem does not, and the proof has no place where the T-dependence is eliminated. The reader's weakest assumption about the user-supplied r is related but does not capture this specific formal gap; the reader's rationale flagged the Lemma 7 warm-start condition, which is a genuine but likely repairable proof gap. I focused on the sample bound because a theorem statement that is not implied by its own lemmas is a direct threat to the central quantitative claim, and the fix is not a matter of adjusting constants. I am not claiming the algorithm is wrong; with a corrected sample bound including log log(R/r)/ε, the nearly-linear runtime claim would survive. The verdict remains CONDITIONAL because the issue is a statement/proof mismatch rather than a demonstrated counterexample.","tokens_in":25351,"tokens_out":45859,"duration_ms":498119,"concrete_test":"Analytic check: write out the proof of Theorem 4 and identify every invocation of Lemma 6's sample hypothesis n ≥ 2400/ε log(4T/δ). Show that for d=1, α=1, ε=1, δ=1/2, and R/r = 2^{2^{20}}, the Theorem 4 bound is O(C) while the Lemma 6 bound is about 2.4 × 10^4; hence the former does not imply the latter. Then verify whether any other argument in the paper supplies the radius-estimation guarantee without this hypothesis; if not, the formal statement of Theorem 4 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 6, which analyzes the FastRadius subroutine used in the Theorem 4 pipeline, requires n ≥ 2400/ε · log(4T/δ) with T = ⌈log_2(R/r)⌉ to guarantee that the estimated radius satisfies 1/4 r(0.75) ≤ \\hat r ≤ 4r(0.9). Theorem 4 states a sample bound n ≥ C · sqrt(d)/(αε) · log^{2.5}(log(d/(αδε))/δ) with C a universal constant, and its proof invokes Lemma 6 through Theorem 3. For any fixed d, α, ε, δ, the ratio R/r can be chosen so large that the Lemma 6 requirement exceeds the Theorem 4 bound, since the former grows with log log(R/r) while the latter does not depend on R/r at all. In that regime the proof gives no utility guarantee for the radius estimate, so the warm-start guarantee used by Algorithm 4 is unsupported. The theorem statement must either include the log log(R/r)/ε term, or the paper must supply a radius-estimation analysis whose sample complexity is independent of R/r; neither is present.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies (ε,δ)-differentially private computation of the geometric median. It proposes a pipeline consisting of (i) a subsampled radius-estimation routine (FastRadius, Algorithm 2), (ii) a subsampled FriendlyCore-style centerpoint estimator (FastCenter, Algorithm 3), and (iii) a phased DP-SGD booster (StableDPSGD, Algorithm 4) with a sensitivity analysis tailored to the unit-norm subgradients of the geometric median objective. The main formal claims are Theorem 3 (a constant-factor warm start in nearly-linear time) and Theorem 4 (a (1+α)-multiplicative approximation in time \\tilde{O}(nd + d/α²) under sample complexity roughly √d/(αε)). The paper also reports experiments on Gaussian-cluster and heavy-tailed synthetic data.","tokens_in":25597,"tokens_out":29268,"duration_ms":280311,"significance":"If the main theorems were fully correct, this would be a substantial improvement over the superlinear algorithms of HSU24, achieving the same near-optimal sample complexity in nearly-linear time, and the structural sensitivity analysis for non-smooth DP-SGD would be of independent interest. The paper is unusually self-contained: helper lemmas are proved rather than deferred, and the experimental section is honest about the parts of the pipeline that were not implemented (Algorithm 3). The main caveat is that two load-bearing proof gaps and one sample-complexity omission currently prevent the theorems from being accepted as stated; all appear locally repairable.","major_comments":[{"comment":"The sample bound stated in Theorem 4, n ≥ C·(√d/(αε))·log^{2.5}(log(d/(αδε))/δ), is not sufficient for the proof as written. The proof invokes Theorem 3, whose hypothesis contains the term n ≥ C·log(log(R/r)/δ)/ε inherited from Lemma 6, where Lemma 6 requires n ≥ (2400/ε)log(4T/δ) with T=⌈log₂(R/r)⌉. For fixed d, α, ε, and δ, taking R/r sufficiently large makes the Lemma 6 requirement exceed the Theorem 4 bound, since the latter is independent of R/r. Thus the warm-start guarantee used by Algorithm 4 is unsupported in exactly the regime the theorem claims to cover, and the statement in Section 1.1 that the sample complexity is independent of R/r is not established. The theorem should include the log log(R/r)/ε term (or the paper must provide a radius-estimation analysis whose sample complexity is independent of R/r); neither is currently present.","section":"Theorem 4 (Section 4); Lemma 6 (Section 3.1)"},{"comment":"The proof of Theorem 3 applies Lemma 7 to the output \\hat r of Algorithm 2, but Lemma 7 assumes \\hat r ≥ r(0.75), while Lemma 6 only establishes \\hat r ≥ (1/4)r(0.75). In the display following Eq. (11) the proof says 'Lemma 6 guarantees' \\|\\bar x−x*\\|≤3\\hat r; that conclusion is actually Lemma 7's and requires the stronger assumption. When \\hat r<r(0.75), Lemma 7's conclusions (positive-weight points within B(x*,3\\hat r) and Z≥0.6n) are not guaranteed, and Algorithm 3 may return 0_d on Line 10 with no proven proximity to x*. This invalidates the warm-start bound (10) and propagates to Theorem 4. A constant-inflation fix (e.g., passing 4\\hat r to Algorithm 3 so that the effective counting radius is large enough) appears to repair the argument, but as written the proof is incomplete.","section":"Theorem 3 (Section 3.2); Lemma 7"},{"comment":"The proof of Lemma 6 is not complete in the case where Algorithm 2 returns R without any threshold crossing. The text sets t=T+1 'by default' and then applies the AboveThreshold utility guarantee as though there were a query q_t with q_t≥0.76n; no such lower bound exists when the algorithm never halts. The upper-bound argument for \\hat r≤4r(0.9) must instead use the fact that q_T≤0.79n (hence q*_T≤0.8n) together with r_T≥R/2 to conclude R≤4r(0.9). Also, the sentence 'by the utility guarantees of Lemma 6' should refer to Lemma 2. These are local but necessary corrections to a lemma on which Theorem 3 relies.","section":"Lemma 6 (Section 3.1)"},{"comment":"The induction proving the sensitivity bound (14) is not justified in the case where the differing index n is sampled. If m_t=0, the induction hypothesis gives Φ_t≤3η and the triangle inequality gives Φ_{t+1}≤5η, which exceeds the claimed (2m_{t+1}+1)η=3η. The bound is salvageable by observing that before the first occurrence of n the two runs are identical, so Φ_t=0 in that case; but the proof as written needs this additional argument. Since Corollary 1 supplies the sensitivity bound used in Lemma 12 for the privacy of Algorithm 4, this step should be spelled out.","section":"Corollary 1 (Section 4.1)"}],"minor_comments":[{"comment":"The stated runtime omits log n factors. Because Algorithm 4 sets T = 2^K−1 ≥ n, K is O(log n), so the polylog terms in the runtime should include log n unless the theorem states a looser \\tilde{O} bound; the displayed expression appears to bound log n using the sample-complexity lower bound, which is valid only for the minimal n and not for all n satisfying the theorem's hypothesis.","section":"Theorem 4 (Section 4)"},{"comment":"The Chernoff bound should be applied to the unscaled success count S_t = k·q_t, whose mean is k·q*_t, rather than to n·q_t; as written, the phrase 'n q_t as a random sum of Bernoulli variables' is not literally correct, and the constants in the proof of (5) should be re-derived from this count.","section":"Lemma 6 (Section 3.1)"},{"comment":"The displayed definition of σ^(k) appears to read η√ρ, but the privacy calculation in Lemma 12 requires σ^(k) = 3^{−k}(2m+1)η/√ρ (or an equivalent normalization). Please correct the typesetting.","section":"Algorithm 4, line 3"},{"comment":"The experiments evaluate Algorithm 2 and Algorithm 4 but not Algorithm 3, which the authors disclose; a sentence making explicit that the experimental validation covers only part of the proposed pipeline would be helpful.","section":"Section 5"},{"comment":"Both theorems require a user-supplied lower bound r with r≤4r(0.9), and the runtime degrades polylogarithmically in R/r; a brief remark on the sensitivity of the guarantees to a poor choice of r would help practitioners, especially since no private procedure for choosing r is provided.","section":"Theorems 3 and 4"}],"recommendation":"major_revision","confidential_remarks":"This is a serious contribution in DP convex optimization and robust statistics, and it appears to fit the journal. The issues I raise are local and I expect them to be fixable; however, the misstatement about sample complexity being independent of R/r and the warm-start gap should be addressed honestly in revision. I would not recommend rejection on grounds of novelty or framing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you decide how seriously to take this paper. The core algorithm is a real step forward: it gives a private geometric median in nearly-linear time plus the cost of the best non-private first-order method, with the same optimal sample complexity as HSU24. The centerpiece is a custom sensitivity analysis of DP-SGD on the nonsmooth median objective (Lemma 11, Corollary 1), and the subsampled radius estimation is a clean idea that should be useful elsewhere. This is not a routine extension of prior work; the authors identified the right bottleneck and found a structural argument to break it.\n\nThe soft spots are in the formal statements, not in the intuition. The stress-test note is correct and it matters: Lemma 6, which analyzes FastRadius, requires n ≳ (1/epsilon) log log(R/r) to guarantee the radius estimate. Theorem 4 states a sample bound with no R/r dependence and proves it via Theorem 3, which inherits that log log term through Lemma 6. For an adversarial choice of R/r (which the theorem permits, since r is an input with r ≤ 4 r(0.9)), the stated bound is not implied by the proof. This is a load-bearing gap in the theorem as written, though it is repairable: either add the term to the sample bound or give a radius-estimation analysis whose sample complexity is independent of R/r.\n\nThe reader's other concern is also legitimate. Theorem 3's proof invokes Lemma 7 under the condition rhat ≥ r(0.75), while Lemma 6 only establishes rhat ≥ r(0.75)/4. The proof then asserts the warm-start bound as if the stronger condition held. This looks like a constant-chasing error, but as written it breaks the chain from radius estimation to centerpoint estimation. A careful revision should fix it by adjusting quantiles or re-proving Lemma 7 with the weaker radius lower bound.\n\nOn the experiments: they cover only the radius and boosting subroutines, not the full pipeline, and the paper says so. That is fine as a sanity check, but it is not empirical validation of the end-to-end algorithm. The weak assumption (user must provide a lower bound r on the effective radius) is worth noting but is inherited from the problem setup.\n\nBottom line: the paper deserves a serious referee. The techniques are novel, the result is significant for DP optimization and robust statistics, and the gaps are repairable rather than fatal. Send it to review, but the referees should insist on a corrected Theorem 4 and a reworked warm-start argument before acceptance.","headline":"Real algorithmic contribution with a load-bearing sample-complexity gap in Theorem 4 and a constant-factor mismatch in the warm-start proof; both repairable, but the paper needs revision.","tokens_in":26132,"tokens_out":4489,"would_cite":true,"duration_ms":46925,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","90C25","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the geometric median can be estimated under differential privacy with the optimal number of samples and in nearly-linear time, closing most of the runtime gap between private and non-private solvers.","keywords":["Differential privacy","Geometric median","Fermat-Weber problem","DP-SGD","Nearly-linear time","Robust estimation","Effective radius","Sample complexity"],"falsifier":"Run Algorithm 4 on two neighboring datasets with the same random index sequence, forcing the differing element to appear exactly $m$ times, and measure the distance between the two iterate sequences; if after any single phase the distance exceeds $(2m+1)\\eta^{(k)}$, the sensitivity bound behind the privacy proof is false. Alternatively, on the paper's GaussianCluster data with $n$ just above and below the stated sample threshold, the empirical failure probability should jump near the threshold; a large deviation from this would contradict Theorem 4.","tokens_in":25136,"feed_emoji":"🔒","tokens_out":8629,"duration_ms":75830,"temperature":0.7,"pith_summary":"The paper claims that the geometric median—the point minimizing average Euclidean distance to a dataset—can be estimated under $(\\varepsilon,\\delta)$-differential privacy with the information-theoretically optimal number of samples and in nearly-linear time. Prior work achieved the same sample complexity but ran in superlinear time. The new algorithm splits the task into a fast warm start that privately finds the effective radius and an approximate center, followed by a DP-SGD boosting phase that refines the estimate to a $(1+\\alpha)$-multiplicative approximation. If correct, this removes the main computational gap between private and non-private geometric-median solvers: the runtime is $\\widetilde{O}(nd + d/\\alpha^2)$, matching the fastest non-private first-order methods up to a small additive term.","feed_headline":"Private geometric median now runs in nearly-linear time","feed_subtitle":"Optimal sample complexity is preserved, with runtime matching non-private solvers up to a small additive term.","key_machinery":"The argument is carried by three components. Radius estimation uses the sparse-vector technique with subsampled neighbor counts: a random set of $O(\\log(1/\\delta))$ points per query suffices to distinguish whether many or few points lie within a candidate radius, cutting the pairwise-comparison cost from quadratic to $O(nd \\log(R/r))$. Centerpoint estimation applies a subsampled FriendlyCore-style weighted average, which privately outputs a point within $O(\\hat{r})$ of the median once the effective radius $\\hat{r}$ is known. The boosting phase relies on a contraction lemma specific to the geometric median: if two coupled SGD iterates $z, z'$ both step toward the same data point with step size $\\eta$, then their distance can only grow to $\\max(\\|z-z'\\|, 3\\eta)$; this bounds the sensitivity of every iterate by $(2m+1)\\eta$ in each phase and lets the algorithm use Gaussian noise with geometrically decaying variance across logarithmically many phases. Privacy is concluded by coupling the real algorithm to an idealized one, applying Rényi DP composition, and converting to $(\\varepsilon,\\delta)$-DP.","core_discovery":"The central claim is Theorem 4: given a dataset contained in a ball of radius $R$, a user-supplied lower bound $r$ on the effective radius $r(0.9)$, and $n \\ge C \\cdot \\frac{\\sqrt{d}}{\\alpha\\varepsilon} \\operatorname{polylog}$ samples, there is an $(\\varepsilon,\\delta)$-DP algorithm that with probability at least $1-\\delta$ returns $\\hat{x}$ with $f_D(\\hat{x}) \\le (1+\\alpha) f_D(x^*(D))$, running in time $\\widetilde{O}(nd + d/\\alpha^2)$. The error scales with the effective radius rather than the worst-case diameter, so datasets with outliers do not force the estimator's error to grow with $R$. The paper also establishes a constant-factor warm start that computes an approximate centerpoint in $\\widetilde{O}(nd)$, and a custom stability analysis of DP-SGD showing that the nonsmooth geometric-median objective can be boosted privately in nearly-linear time.","pith_inferences":["The contraction lemma likely extends to other nonsmooth losses whose subgradients are unit vectors pointing toward data points, such as Huber losses or $\\ell_p$ location losses; if so, this nearly-linear DP-SGD template may apply more broadly than the geometric median.","Because the runtime depends only polylogarithmically on $R/r$, a private procedure for choosing the effective-radius lower bound $r$ itself, rather than receiving it as user input, would remove the last user-supplied parameter; the paper does not provide such a procedure.","The experiments show that a parallelized full-batch baseline can beat the fixed-order SGD variant in wall-clock time at moderate dataset sizes, so the practical case for DP-SGD strengthens as $n$ and $d$ grow; benchmarking with minibatches and adaptive step sizes would test that claim.","The authors report that the centerpoint estimation step's constants are loose and that this step was not benchmarked; improving it is a concrete next step before the full pipeline becomes practical."],"forward_implications":["If the theorem is correct, private geometric-median estimation with optimal sample complexity runs in time matching the best non-private first-order solver up to an additive $d/\\alpha^2$ term.","For constant approximation $\\alpha$, the runtime is $O(nd \\log(R/r) \\operatorname{polylog})$, so large datasets with moderate aspect ratios can be handled in nearly-linear time.","The constant-factor warm start can be computed privately in $\\widetilde{O}(nd)$, isolating the remaining computational cost to the boosting phase rather than the radius-search or centerpoint steps.","The stability lemma implies DP-SGD can solve at least one structured nonsmooth empirical risk minimization problem in nearly-linear time, a regime where generic nonsmooth DP-SGD analyses require stronger sample-size assumptions.","The authors explicitly leave removing the additive $d/\\alpha^2$ term, or proving it impossible, as future work."],"supporting_citations":[{"why":"Prior DP geometric-median algorithm with optimal sample complexity and matching lower bound; supplies the warm-start/boosting roadmap and the sample-complexity benchmark this paper improves in runtime.","marker":"[HSU24]"},{"why":"Non-private nearly-linear geometric median solver whose runtime is the additive baseline, and source of Lemma 4 and the quantile-radius notation.","marker":"[CLM+16]"},{"why":"FriendlyCore aggregation framework whose subsampled weighted-average variant the paper adapts for private centerpoint estimation.","marker":"[TCK+22]"},{"why":"Reduction from private optimization to stable optimization and the localized DP-SGD phase framework used by the boosting phase.","marker":"[FKT20]"},{"why":"Provides the bounded Laplace mechanism and the coupling/privacy-loss lemma used to handle privacy when subsampling estimates fail.","marker":"[ALT24]"},{"why":"Supplies the sparse-vector technique, Gaussian mechanism, and composition theorems used throughout the privacy proofs.","marker":"[DR14]"},{"why":"Rényi and concentrated DP definitions and composition properties used to account for privacy across the boosting phases.","marker":"[Mir17]"},{"why":"Projection non-expansiveness used in the per-phase iterate sensitivity bound.","marker":"[Roc76]"},{"why":"Mirror descent convergence analysis used for the per-phase utility guarantee of the boosting algorithm.","marker":"[Bub15]"}],"fun_headline_variants":["Private median in near-linear time","Optimal-sample private median, near-linear speed","Nearly-linear private geometric median","Private median: near-linear and optimal","Speed up private median to near-linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the user supplies a radius $r$ with $0 < r \\le 4r_{(0.9)}(D)$, i.e., a lower bound on the ball around the median that already contains 90% of the data; without such an $r$, the runtime's $\\log(R/r)$ factor and the stated guarantees can degrade.","fun_headline_variants_meta":{"raw":{"variants":["Private median in near-linear time","Optimal-sample private median, near-linear speed","Nearly-linear private geometric median","Private median: near-linear and optimal","Speed up private median to near-linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000275,"raw_usage":{"total_tokens":1691,"prompt_tokens":1042,"completion_tokens":649,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":589}},"tokens_in":658,"tokens_out":649,"duration_ms":6202,"temperature":1.0,"reasoning_tokens":589,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:00:20.195262+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 4 on two neighboring datasets with the same random index sequence, forcing the differing element to appear exactly $m$ times, and measure the distance between the two iterate sequences; if after any single phase the distance exceeds $(2m+1)\\eta^{(k)}$, the sensitivity bound behind the privacy proof is false. Alternatively, on the paper's GaussianCluster data with $n$ just above and below the stated sample threshold, the empirical failure probability should jump near the threshold; a large deviation from this would contradict Theorem 4.","supporting_citations":[],"review_version":1}