Stochastic Gradient Descent (SGD) is a central tool in machine learning. We
prove that SGD converges to zero loss, even with a fixed (non-vanishing)
learning rate - in the special case of homogeneous linear classifiers with
smooth monotone loss functions, optimized on linearly separable data. Previous
works assumed either a vanishing learning rate, iterate averaging, or loss
assumptions that do not hold for monotone loss functions used for
classification, such as the logistic loss. We prove our result on a fixed
dataset, both for sampling with or without replacement. Furthermore, for
logistic loss (and similar exponentially-tailed losses), we prove that with SGD
the weight vector converges in direction to the $L_2$ max margin vector as
$O(1/\log(t))$ for almost all separable datasets, and the loss converges as
$O(1/t)$ - similarly to gradient descent. Lastly, we examine the case of a
fixed learning rate proportional to the minibatch size. We prove that in this
case, the asymptotic convergence rate of SGD (with replacement) does not depend
on the minibatch size in terms of epochs, if the support vectors span the data.
These results may suggest an explanation to similar behaviors observed in deep
networks, when trained with SGD.

本文探讨了采用 SGD 进行机器学习的收敛性问题，特别是在采用线性可分数据及单调函数损失函数的情况下，证明了 SGD 在固定非零学习率的条件下可以收敛至零损失，对于分类问题中的单调函数损失函数（例如对数损失），每次迭代权重向量趋向于 $L_2$ 最大裕度向量，且损失以 $O (1/t)$ 的速率收敛。