Private Geometric Median in Nearly-Linear Time

Chutong Yang; Daogao Liu; Kevin Tian; Syamantak Kumar

REVIEW 4 major objections 5 minor 22 references

Private Geometric Median in Nearly-Linear Time

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.20189 v1 pith:YD2R7N27 submitted 2025-05-26 cs.DS cs.CRcs.LGstat.ML

Syamantak Kumar , Daogao Liu , Kevin Tian , Chutong Yang This is my paper · ORCID

classification cs.DScs.CRcs.LGstat.ML MSC 68W2090C2568P27

keywords DifferentialprivacyGeometricmedianFermat-WeberproblemDP-SGDNearly-lineartimeRobustestimationEffectiveradiusSamplecomplexity

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

The 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.

The 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.

On 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.

Bottom 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.

Referee Report

4 major / 5 minor

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.

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 (4)

[Theorem 4 (Section 4); Lemma 6 (Section 3.1)] 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.
[Theorem 3 (Section 3.2); Lemma 7] 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.
[Lemma 6 (Section 3.1)] 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.
[Corollary 1 (Section 4.1)] 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.

minor comments (5)

[Theorem 4 (Section 4)] 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.
[Lemma 6 (Section 3.1)] 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.
[Algorithm 4, line 3] 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 5] 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.
[Theorems 3 and 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and rests on external standard tools; the flagged sample-complexity gap is a correctness issue, not a circularity.

full rationale

I found no step where a claimed prediction or derived guarantee is equivalent by construction to a fitted parameter or to an input assumption. Algorithm 2's radius guarantee is derived from the external AboveThreshold lemma (Lemma 2), Chernoff bounds, and Lemma 4 of [CLM+16]; the numerical constants are proof artifacts and are not fit to any data. Algorithm 3's privacy proof is a coupling argument (Lemma 1) combined with the bounded Laplace and Gaussian mechanisms, whose hypotheses do not include the geometric-median target. Section 4's boosting analysis uses the FKT20 localization framework and proves a new contractivity bound (Lemma 11) for subgradient steps; the final error expression is standard mirror-descent plus noise accounting, with no output quantity reused as an input. The only self-citations with author overlap ([ALT24] for the bounded Laplace fact and coupling technique) are to general, parameter-free privacy tools, which qualify as independent support rather than load-bearing self-citation. I do explicitly flag a separate correctness gap, located in Theorem 4's statement and proof: Lemma 6 requires n ≥ (2400/ε) log(4T/δ) with T = ceil(log2(R/r)), but Theorem 4's stated sample bound n ≥ C sqrt(d)/(αε) log^{2.5}(log(d/(αδε))/δ) has no dependence on R/r and does not imply the Lemma 6 requirement when R/r is very large. This may invalidate the warm-start guarantee in Theorem 4 in that regime, but it is a missing-support issue, not circularity.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard concentration and privacy tools, a robust geometry lemma, and the user-supplied lower bound r on the effective radius. No new physical or mathematical entities are introduced. The free parameters listed are hand-chosen proof constants, not fitted to data.

free parameters (5)

Quantile 0.9 for effective radius = 0.9
The algorithm assumes a lower bound on r(0.9), the radius around the median containing 90% of points. The quantile is a hand-chosen constant; other values above 0.5 would work with adjusted constants.
Threshold tau = 0.775n in Algorithm 2 = 0.775n
Hand-chosen to make the sparse-vector threshold consistent with the 0.75n and 0.8n cuts used in the Chernoff analysis.
Counting radius factor 2 in Algorithm 3 = 2 * hat r
Weights in FriendlyCore count neighbors within 2*hat r; this factor is a proof constant and is directly implicated in the gap where hat r >= r(0.75) is needed but only hat r >= r(0.75)/4 is shown.
Noise scale constant 1600 in Algorithm 3 = 1600
Chosen to make the sensitivity bound 400*hat r/n and the CDP budget line up; not fitted to data.
Step size schedule in Algorithm 4 = eta * 4^{-k}, noise 3^{-k}
Geometric decay chosen to sum cleanly; hand-picked, not fitted.

assumptions (5)

standard math Chernoff bound, Gaussian and bounded Laplace mechanisms, RDP composition (Facts 1-4)
Used throughout for concentration and privacy.
standard math Projection onto a convex set is non-expansive (Fact 5)
Used in the DP-SGD sensitivity proof.
standard math Mirror descent regret bound (Theorem 3.2, Bub15)
Used in the utility analysis of Algorithm 4.
domain assumption Robustness Lemma 4 from CLM+16
Bounds the median's location relative to a majority ball; taken as a black box.
domain assumption Dataset lies in B_d(R) and r <= 4 r(0.9) is known
The algorithm's input requirements; the runtime and sample complexity depend on the aspect ratio R/r.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Private Geometric Median in Nearly-Linear Time." pith.science (2026). https://pith.science/paper/YD2R7N27

@misc{pith2026250520189,
  author       = {Pith},
  title        = {Pith review of: Private Geometric Median in Nearly-Linear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YD2R7N27}},
  note         = {Machine review of arXiv:2505.20189}
}

abstract

Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, [HSU24] gave an $(\varepsilon, \delta)$-differentially private algorithm obtaining an $\alpha$-multiplicative approximation to the geometric median objective, $\frac 1 n \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$, given a dataset $\mathcal{D} := \{\mathbf{x}_i\}_{i \in [n]} \subset \mathbb{R}^d$. Their algorithm requires $n \gtrsim \sqrt d \cdot \frac 1 {\alpha\varepsilon}$ samples, which they prove is information-theoretically optimal. This result is surprising because its error scales with the \emph{effective radius} of $\mathcal{D}$ (i.e., of a ball capturing most points), rather than the worst-case radius. We give an improved algorithm that obtains the same approximation quality, also using $n \gtrsim \sqrt d \cdot \frac 1 {\alpha\epsilon}$ samples, but in time $\widetilde{O}(nd + \frac d {\alpha^2})$. Our runtime is nearly-linear, plus the cost of the cheapest non-private first-order method due to [CLM+16]. To achieve our results, we use subsampling and geometric aggregation tools inspired by FriendlyCore [TCK+22] to speed up the "warm start" component of the [HSU24] algorithm, combined with a careful custom analysis of DP-SGD's sensitivity for the geometric median objective.

Figures

Figures reproduced from arXiv: 2505.20189 by the authors.

**Figure 1.** Comparison of RadiusFinder and FastRadius across different data distributions. Plots averaged across 100 trials and standard deviations are reported as error bars. We observe that in both cases, across a range of increasingly heavier tails of the distributions, both algorithms achieve reasonable approximation to the true quantile radius, always staying multiplicatively 7We provide code for the experiments in this se… view at source ↗

**Figure 2.** Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across GaussianCluster data over R 50, varying n. Plots averaged across 20 trials and standard deviations are reported as error bars. Across GaussianCluster datasets of size n ∈ {100, 1000, 10000}, we found that FixedOrderDPSGD consistently outperformed StableDPSGD, and consistently outperformed the baseline by a significant margin once dataset sizes were large e… view at source ↗

**Figure 3.** Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across HeavyTailed data over R 50 , varying n. Plots averaged across 20 trials and standard deviations are reported as error bars. We next present our comparisons for the HeavyTailed dataset. Again, our (optimized) method led to similar or better performance than the baseline for larger n. We suspect that the improved performance of the baseline owes to the relati… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across GaussianCluster data over R 50, varying R. Plots averaged across 20 trials and standard deviations are reported as error bars. (a) ν = 2.5 (b) ν = 5 (c) ν = 10 [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]

**Figure 5.** Figure 5: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across HeavyTailed data over R 50 , varying ν. Plots averaged across 20 trials and standard deviations are reported as error bars. Acknowledgments We thank the Texas Advanced Computing Center (TACC) for computing res…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 17 canonical work pages

[1]

Deep learning with differential privacy

[ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318,

2016
[7]

Hopkins, and Adam D

[BHS23] Gavin Brown, Samuel B. Hopkins, and Adam D. Smith. Fast, sample-efficient, affine- invariant private mean and covariance estimation for subgaussian distributions. InThe Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume195ofProceedings of Machine Learning Research, pages 5578–5579. PMLR,

work page 2023
[12]

Differentially-private clustering of easy instances

[CKM+21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially-private clustering of easy instances. InProceedings of the 38th International Conference on Machine Learning, ICML 2021, volume 139 ofProceedings of Machine Learn- ing Research, pages 2049–2059. PMLR,

work page 2021
[13]

Differentially private confidence intervals.arXiv preprint arXiv:2001.02285,

[DFM+20] Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals.arXiv preprint arXiv:2001.02285,

arXiv 2001
[14]

Private stochastic convex optimization: optimal rates in linear time

[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 439–449. ACM,

work page 2020
[15]

Private convex optimization via exponential mechanism

[GLL22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. InConference on Learning Theory, pages 1948–1989. PMLR,

work page 1948
[16]

Private convex optimization in general norms

[GLL+23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimization in general norms. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068–5089. SIAM,

work page 2023
[17]

[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. InConference on Learning Theory, COLT 2019, 25-28 June 2019, volume 99 ofProceedings of Machine Learning Research, pages 1853–1902. PMLR,

work page 2019

Show all 22 references

[21]

[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. InProceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75–84. ACM,

2007
[1991]

Rényi differential privacy

[Mir17] Ilya Mironov. Rényi differential privacy. In30th IEEE Computer Security Foundations Symposium, CSF 2017, pages 263–275. IEEE Computer Society,

2017
[2007]

[NSV16] Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Locating a small cluster privately. In Tova Milo and Wang-Chiew Tan, editors,Proceedings of the 35th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems, PODS 2016, pages 413–427. ACM,

2016
[2012]

Finite sample differentially private confidence intervals

[KV17] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908,

arXiv
[2014]

Coinpress: Practical private mean and covariance estimation

[BDKU20] SouravBiswas, YiheDong, GautamKamath, andJonathanR.Ullman. Coinpress: Practical private mean and covariance estimation. InAdvances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020,

2020
[2015]

Optimal rates for o(1)-smooth dp-sco with a single epoch and large batches.arXiv preprint arXiv:2406.02716,

[CCGT24] Christopher A Choquette-Choo, Arun Ganesh, and Abhradeep Thakurta. Optimal rates for o(1)-smooth dp-sco with a single epoch and large batches.arXiv preprint arXiv:2406.02716,

arXiv
[2016]

Smith, and Abhradeep Thakurta

[BST14] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. In55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 464–473. IEEE Computer Society,

2014
[2017]

DP-PCA: statistically optimal and differentially private PCA

[LKJO22] Xiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. DP-PCA: statistically optimal and differentially private PCA. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022,

2022
[2019]

Concentrated differential privacy: Simplifications, exten- sions, and lower bounds

22 [BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, exten- sions, and lower bounds. InTheory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings, Part I, volume 9985 ofLecture Notes in Computer Science, pages 635–658,

2016
[2020]

More asymmetry yields faster matrix multiplication

[ADV+25] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 2005–2039. SIAM,

2025
[2021]

Privacy and statistical risk: Formalisms and mini- max bounds.arXiv preprint arXiv:1412.4451,

[BD14] Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and mini- max bounds.arXiv preprint arXiv:1412.4451,

arXiv
[2022]

User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates.arXiv preprint arXiv:2311.03797,

[AL23] Hilal Asi and Daogao Liu. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates.arXiv preprint arXiv:2311.03797,

arXiv
[2023]

Private stochastic convex optimization with heavy tails: Near-optimalityfromsimplereductions

[ALT24] Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimalityfromsimplereductions. InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024,

2024
[2024]

Resqueing parallel and private stochastic convex optimization

[CJJ+23] Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 2031–2058. IEEE,

2023

Pith tools

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

[1] [1]

Deep learning with differential privacy

[ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318,

2016

[2] [7]

Hopkins, and Adam D

[BHS23] Gavin Brown, Samuel B. Hopkins, and Adam D. Smith. Fast, sample-efficient, affine- invariant private mean and covariance estimation for subgaussian distributions. InThe Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume195ofProceedings of Machine Learning Research, pages 5578–5579. PMLR,

work page 2023

[3] [12]

Differentially-private clustering of easy instances

[CKM+21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially-private clustering of easy instances. InProceedings of the 38th International Conference on Machine Learning, ICML 2021, volume 139 ofProceedings of Machine Learn- ing Research, pages 2049–2059. PMLR,

work page 2021

[4] [13]

Differentially private confidence intervals.arXiv preprint arXiv:2001.02285,

[DFM+20] Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals.arXiv preprint arXiv:2001.02285,

arXiv 2001

[5] [14]

Private stochastic convex optimization: optimal rates in linear time

[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 439–449. ACM,

work page 2020

[6] [15]

Private convex optimization via exponential mechanism

[GLL22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. InConference on Learning Theory, pages 1948–1989. PMLR,

work page 1948

[7] [16]

Private convex optimization in general norms

[GLL+23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimization in general norms. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068–5089. SIAM,

work page 2023

[8] [17]

[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. InConference on Learning Theory, COLT 2019, 25-28 June 2019, volume 99 ofProceedings of Machine Learning Research, pages 1853–1902. PMLR,

work page 2019