CompAdaGrad: A Compressed, Complementary, Computationally-Efficient Adaptive Gradient Method
CompAdaGrad: A Compressed, Complementary, Computationally-Efficient Adaptive Gradient Method
复制标题
DOI：
--
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
Nishant A. Mehta;Alistair P. Rendell;Anish Varghese;C. Webers
中科院分区：
文献类型：
--
作者：
Nishant A. Mehta;Alistair P. Rendell;Anish Varghese;C. Webers
被称为AdaGrad的自适应梯度在线学习方法在机器学习社区中广泛用于随机和对抗性在线学习问题，最近在深度学习方法中得到了广泛应用。该方法的全矩阵化身提供了更好的理论保证和潜在的更好的经验性能比它的对角版本，但是，这个版本是计算禁止，所以更简单的对角版本经常在实践中使用。我们介绍了一种新的方法，CompAdaGrad，导航这两个计划之间的空间，并表明这种方法可以产生比对角AdaGrad更好的结果，同时避免（有效棘手）的全矩阵AdaGrad的计算复杂度为$n$。CompAdaGrad本质上是在低维子空间中执行全矩阵正则化，而在互补子空间中执行对角正则化。我们得出CompAdaGrad的更新复合镜像下降的情况下的平方$\ell_2$范数和$\ell_1$范数，证明其每次迭代的复杂性是线性的维度，并建立保证的方法独立的选择复合正则化。最后，我们展示了几个数据集的初步结果。
The adaptive gradient online learning method known as AdaGrad has seen widespread use in the machine learning community in stochastic and adversarial online learning problems and more recently in deep learning methods. The method's full-matrix incarnation offers much better theoretical guarantees and potentially better empirical performance than its diagonal version; however, this version is computationally prohibitive and so the simpler diagonal version often is used in practice. We introduce a new method, CompAdaGrad, that navigates the space between these two schemes and show that this method can yield results much better than diagonal AdaGrad while avoiding the (effectively intractable) $O(n^3)$ computational complexity of full-matrix AdaGrad for dimension $n$. CompAdaGrad essentially performs full-matrix regularization in a low-dimensional subspace while performing diagonal regularization in the complementary subspace. We derive CompAdaGrad's updates for composite mirror descent in case of the squared $\ell_2$ norm and the $\ell_1$ norm, demonstrate that its complexity per iteration is linear in the dimension, and establish guarantees for the method independent of the choice of composite regularizer. Finally, we show preliminary results on several datasets.