There are several applications of stochastic optimization where one can
benefit from a robust estimate of the gradient. For example, domains such as
distributed learning with corrupted nodes, the presence of large outliers in
the training data, learning under privacy constraints, or even heavy-tailed
noise due to the dynamics of the algorithm itself. Here we study SGD with
robust gradient estimators based on estimating the median. We first consider
computing the median gradient across samples, and show that the resulting
method can converge even under heavy-tailed, state-dependent noise. We then
derive iterative methods based on the stochastic proximal point method for
computing the geometric median and generalizations thereof. Finally we propose
an algorithm estimating the median gradient across iterations, and find that
several well known methods - in particular different forms of clipping - are
particular cases of this framework.

基于中位数估计的坚实梯度方法在随机梯度下降算法中能够应对重尾、状态相关性噪声，在分布式学习、隐私约束等领域有广泛应用。本研究在采样、几何中位数计算及迭代中都提出了基于中位数梯度估计的方法，并发现多种已知算法可看作此方法的特例。