Adaptive Quantile Clipping under Heavy-Tailed Noise and Differential Privacy

Gradient clipping plays an important role in stochastic optimization with heavy-tailed noise or under differential privacy constraints, but its performance depends heavily on the choice of its threshold. In this paper, we study \emph{quantile clipping}, a scale-independent alternative that sets the clipping threshold to a fixed quantile of the gradient-norm distribution. We show that in the heavy-tailed noise setting, quantile clipping achieves the optimal convergence rate of $\mathcal{O}(T^{\frac{-2(p - 1)}{3p - 2}})$. Furthermore, we consider its practical implementation in the form of \emph{online quantile clipping} \citep{andrew2021differentially}, and show that it achieves the same convergence rate. Finally, we derive a formal differential privacy stationarity floor for online quantile clipping, providing a utility--privacy tradeoff guarantee.