A General Analysis of Example-Selection for Stochastic Gradient Descent
A General Analysis of Example-Selection for Stochastic Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yucheng Lu;S. Meng;Christopher De Sa
中科院分区：
文献类型：
--
作者：
Yucheng Lu;S. Meng;Christopher De Sa
长期以来，已知SGD中的训练示例顺序会影响收敛率。最近的结果表明，在各种基于排列的样本顺序的情况下，可以加速率，其中在重复使用任何示例之前，使用一次训练集中的每个示例。在本文中，我们对SGD使用的示例顺序开发了广泛的条件，这足以证明在强凸和非凸面设置中都存在紧密的收敛速率。我们表明，我们的方法足以恢复，在某些情况下，对以前的四个已知示例选择方案进行了先前的最新分析：（1）洗牌一次；随着数据的回声和（4）马尔可夫链梯度下降。在我们的理论中，我们提出了两种新的示例选择方法。首先，使用准蒙特 - 卡洛方法，我们实现了前所未有的加速收敛速率，以通过数据增强来学习。其次，我们贪婪地选择了一个固定的扫描顺序，以最大程度地减少条件中使用的度量，并表明我们可以从相同数量的SGD时期获得更准确的解决方案。我们通过经验证明了我们对凸线性模型和深度学习任务的方法的实用性来结束。我们的代码可在以下网址提供：https：//github.com/eugenelyc/qmc-ordering。
Training example order in SGD has long been known to affect convergence rate. Recent results show that accelerated rates are possible in a variety of cases for permutation-based sample orders, in which each example from the training set is used once before any example is reused. In this paper, we develop a broad condition on the sequence of examples used by SGD that is sufficient to prove tight convergence rates in both strongly convex and non-convex settings. We show that our approach suffices to recover, and in some cases improve upon, previous state-of-the-art analyses for four known example-selection schemes: (1) shuffle once, (2) random reshuffling, (3) random reshuffling with data echoing, and (4) Markov Chain Gradient Descent. Motivated by our theory, we propose two new example-selection approaches. First, using quasi-Monte-Carlo methods, we achieve unprecedented accelerated convergence rates for learning with data augmentation. Second, we greedily choose a fixed scan-order to minimize the metric used in our condition and show that we can obtain more accurate solutions from the same number of epochs of SGD. We conclude by empirically demonstrating the utility of our approach for both convex linear-model and deep learning tasks. Our code is available at: https://github.com/EugeneLYC/qmc-ordering .