In this paper, we study differentially private (DP) algorithms for computing
the geometric median (GM) of a dataset: Given $n$ points, $x_1,\dots,x_n$ in
$\mathbb{R}^d$, the goal is to find a point $\theta$ that minimizes the sum of
the Euclidean distances to these points, i.e., $\sum_{i=1}^{n} \|\theta -
x_i\|_2$. Off-the-shelf methods, such as DP-GD, require strong a priori
knowledge locating the data within a ball of radius $R$, and the excess risk of
the algorithm depends linearly on $R$. In this paper, we ask: can we design an
efficient and private algorithm with an excess error guarantee that scales with
the (unknown) radius containing the majority of the datapoints? Our main
contribution is a pair of polynomial-time DP algorithms for the task of private
GM with an excess error guarantee that scales with the effective diameter of
the datapoints. Additionally, we propose an inefficient algorithm based on the
inverse smooth sensitivity mechanism, which satisfies the more restrictive
notion of pure DP. We complement our results with a lower bound and demonstrate
the optimality of our polynomial-time algorithms in terms of sample complexity.

本文研究了差分隐私算法在计算数据集的几何中位数方面的应用，提出了一对多项式时间的差分隐私算法，并证明其在样本复杂性方面的最优性。

私密几何中位数

Private Geometric Median

We show that weights learned by AdamW can be understood as an exponential
moving average (EMA) of recent updates. This gives critical insights for how to
set the weight decay in AdamW, and how the weight decay should scale with model
and dataset size. In particular, the key hyperparameter for an exponential
moving average is the EMA timescale. Intuitively, the EMA timescale can be
understood as the number of recent iterations the EMA averages over. Given a
fixed learning rate, there is a one-to-one mapping from the EMA timescale to
the usual weight decay hyperparameter. Thus, choosing an EMA timescale
implicitly sets the weight decay. Importantly, there are natural guidelines for
sensible values for the EMA timescale: we need to average over all datapoints,
so the EMA timescale should not be (much) smaller than 1 epoch, and we need to
forget early updates, so the EMA timescale should not be (much) bigger than the
total number of training epochs. In our experiments, we find that optimal EMA
timescales are consistent with these guidelines, as are the hyperparameters
chosen in recent large-scale LLM pretraining runs (e.g.\ Llama 1+2 and Stable
LM). Critically, these guidelines suggest that the optimal EMA timescale should
not change (much) as we scale the model and dataset. That implies that as the
dataset size increases, the optimal weight decay should fall. Moreover, as the
model size increases, the optimal weight decay should also increase (if we
follow the muP recommendation for scaling the learning rate).

AdamW 算法中的权重可以理解为近期更新的指数移动平均 (EMA)，通过 EMA 时间尺度选择合适的权重衰减，以确保权重衰减与模型和数据集的规模相匹配，并得出 EMA 时间尺度的合理取值范围。