We introduce a clipping strategy for Stochastic Gradient Descent (SGD) which
uses quantiles of the gradient norm as clipping thresholds. We prove that this
new strategy provides a robust and efficient optimization algorithm for smooth
objectives (convex or non-convex), that tolerates heavy-tailed samples
(including infinite variance) and a fraction of outliers in the data stream
akin to Huber contamination. Our mathematical analysis leverages the connection
between constant step size SGD and Markov chains and handles the bias
introduced by clipping in an original way. For strongly convex objectives, we
prove that the iteration converges to a concentrated distribution and derive
high probability bounds on the final estimation error. In the non-convex case,
we prove that the limit distribution is localized on a neighborhood with low
gradient. We propose an implementation of this algorithm using rolling
quantiles which leads to a highly efficient optimization procedure with strong
robustness properties, as confirmed by our numerical experiments.

引入了一种剪裁策略，使用梯度范数的分位数作为剪裁阈值，为平滑目标（凸或非凸）提供鲁棒且高效的优化算法，容忍重尾样本和数据中的异常值，数学分析说明了其收敛性质以及对初始估计误差的高概率界限，并通过实验证实了其高效性和鲁棒性。

基于梯度分位数截断的鲁棒随机优化

Robust Stochastic Optimization via Gradient Quantile Clipping

We study Nesterov's accelerated gradient method with constant step-size and
momentum parameters in the stochastic approximation setting (unbiased gradients
with bounded variance) and the finite-sum setting (where randomness is due to
sampling mini-batches). To build better insight into the behavior of Nesterov's
method in stochastic settings, we focus throughout on objectives that are
smooth, strongly-convex, and twice continuously differentiable. In the
stochastic approximation setting, Nesterov's method converges to a neighborhood
of the optimal point at the same accelerated rate as in the deterministic
setting. Perhaps surprisingly, in the finite-sum setting, we prove that
Nesterov's method may diverge with the usual choice of step-size and momentum,
unless additional conditions on the problem related to conditioning and data
coherence are satisfied. Our results shed light as to why Nesterov's method may
fail to converge or achieve acceleration in the finite-sum setting.

研究了 Nesterov 加速梯度方法在随机逼近和有限和设置下的表现，发现使用通常的步长和动量参数，该方法在后者可能发散，进而阐明了这种方法在此情况下可能失败的原因。