提出近线性时间的私有几何中位数算法，保持最优样本量。
Private Geometric Median in Nearly-Linear Time
- 用子采样与几何聚合加速初始值生成，提升效率。
- 在样本量满足 $n \gtrsim \sqrt{d} / (\alpha\varepsilon)$ 时实现 $\alpha$-近似。
- 适合对隐私和计算效率要求高的高维数据处理场景。
估算数据集的几何中位数是均值估计的鲁棒替代，是计算几何中的基础问题。近期工作 [HSU24] 提出一种 $(\varepsilon, δ)$-差分隐私算法，可在给定数据集 $\mathcal{D} := \{\mathbf{x}_i\}_{i \in [n]} \subset \mathbb{R}^d$ 时，以 $\alpha$-乘法近似度求解几何中位数目标 $\frac{1}{n} \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$。其算法需满足 $n \gtrsim \sqrt{d} \cdot \frac{1}{\alpha\varepsilon}$ 样本量，且被证明为信息论最优。该结果令人意外，因其误差依赖于数据的有效半径（即容纳多数点的球体半径），而非最坏情况下的半径。本文提出改进算法，在相同样本量下达到相同近似质量，但运行时间降至 $\widetilde{O}(nd + \frac{d}{\alpha^2})$，为近线性时间，仅额外承担 [CLM+16] 中最便宜的非私有一阶方法成本。通过借鉴 FriendlyCore [TCK+22] 的子采样与几何聚合工具，加速了 [HSU24] 算法中的‘热启动’环节，并对差分隐私随机梯度下降（DP-SGD）在几何中位数目标上的敏感性进行了精细定制分析。
原文摘要 · Abstract (English)
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, δ)$-differentially private algorithm obtaining an $α$-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 {α\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 {αε}$ samples, but in time $\widetilde{O}(nd + \frac d {α^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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。