SGD with Clipping is Secretly Estimating the Median Gradient
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Robust Federated Learning Over the Air: Combating Heavy-Tailed Noise with Median Anchored Clipping
Leveraging over-the-air computations for model aggregation is an effective approach to cope with the communication bottleneck in federated edge learning. By exploiting the superposition properties of multi-access channel…
Federated LearningA Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks
In distributed training of deep neural networks, people usually run Stochastic Gradient Descent (SGD) or its variants on each machine and communicate with other machines periodically. However, SGD might converge slowly i…
Federated LearningRobust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling
We consider a first order stochastic optimization framework where, at each iteration, $K$ independent identically distributed (i.i.d.) data point samples are drawn, based on which stochastic gradients can be queried. We …
Stochastic OptimizationCan gradient clipping mitigate label noise?
Gradient clipping is a widely-used technique in the training of deep networks, and is generally motivated from an optimisation lens: informally, it controls the dynamics of iterates, thus enhancing the rate of convergenc…
High Probability Analysis for Non-Convex Stochastic Optimization with Clipping
Gradient clipping is a commonly used technique to stabilize the training process of neural networks. A growing body of studies has shown that gradient clipping is a promising technique for dealing with the heavy-tailed b…
Stochastic Optimization