We study the problem of differentially private stochastic convex optimization
(DP-SCO) with heavy-tailed gradients, where we assume a $k^{\text{th}}$-moment
bound on the Lipschitz constants of sample functions rather than a uniform
bound. We propose a new reduction-based approach that enables us to obtain the
first optimal rates (up to logarithmic factors) in the heavy-tailed setting,
achieving error $G_2 \cdot \frac 1 {\sqrt n} + G_k \cdot (\frac{\sqrt
d}{n\epsilon})^{1 - \frac 1 k}$ under $(\epsilon, \delta)$-approximate
differential privacy, up to a mild $\textup{polylog}(\frac{1}{\delta})$ factor,
where $G_2^2$ and $G_k^k$ are the $2^{\text{nd}}$ and $k^{\text{th}}$ moment
bounds on sample Lipschitz constants, nearly-matching a lower bound of [Lowy
and Razaviyayn 2023].
We further give a suite of private algorithms in the heavy-tailed setting
which improve upon our basic result under additional assumptions, including an
optimal algorithm under a known-Lipschitz constant assumption, a near-linear
time algorithm for smooth functions, and an optimal linear time algorithm for
smooth generalized linear models.

我们研究了具有重尾梯度的差分隐私随机凸优化（DP-SCO）问题，在这里我们假设样本函数的 Lipschitz 常数具有 k 次矩界而不是统一界。我们提出了一种新的基于约束的方法，使我们能够在重尾设置中获得首个最优速率（达到对数因子），在（ε，δ）- 近似差分隐私下，实现误差 G2⋅1/√n+Gk⋅(√d/nε)^(1-1/k)，几乎匹配于 [Lowy and Razaviyayn 2023] 的下界。在额外假设下，我们进一步给出了一套重尾设置的私有算法，包括在已知 Lipschitz 常数假设下的最优算法，平滑函数的近线性时间算法以及平滑广义线性模型的最优线性时间算法。

简化的简单降维的大尾部私密随机凸优化近乎最优解

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality  from Simple Reductions

Gradient compression has surfaced as a key technique to address the challenge
of communication efficiency in distributed learning. In distributed deep
learning, however, it is observed that gradient distributions are heavy-tailed,
with outliers significantly influencing the design of compression strategies.
Existing parameter quantization methods experience performance degradation when
this heavy-tailed feature is ignored. In this paper, we introduce a novel
compression scheme specifically engineered for heavy-tailed gradients, which
effectively combines gradient truncation with quantization. This scheme is
adeptly implemented within a communication-limited distributed Stochastic
Gradient Descent (SGD) framework. We consider a general family of heavy-tail
gradients that follow a power-law distribution, we aim to minimize the error
resulting from quantization, thereby determining optimal values for two
critical parameters: the truncation threshold and the quantization density. We
provide a theoretical analysis on the convergence error bound under both
uniform and non-uniform quantization scenarios. Comparative experiments with
other benchmarks demonstrate the effectiveness of our proposed method in
managing the heavy-tailed gradients in a distributed learning environment.

我们提出了一种专门针对重尾梯度进行压缩的新方案，该方案将梯度截断和量化有效地结合在一起，并在通信受限的分布式随机梯度下降框架中进行了巧妙实现，我们通过理论分析和与其他基准的比较实验证明了该方法在管理分布式学习环境中的重尾梯度方面的有效性。