Stochastic Dual Coordinate Ascent with Adaptive Probabilities
Stochastic Dual Coordinate Ascent with Adaptive Probabilities
复制标题
DOI：
--
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Dominik Csiba;Zheng Qu;Peter Richtárik
中科院分区：
文献类型：
--
作者：
Dominik Csiba;Zheng Qu;Peter Richtárik
本文介绍AdaSDCA：随机对偶坐标上升法（SDCA）的一个自适应变体，用于求解正则化的经验风险最小化问题。我们的修改包括允许该方法自适应地改变整个迭代过程中的对偶变量的概率分布。AdaSDCA实现了比SDCA更好的复杂度界限，具有最佳的固定概率分布，称为重要性抽样。然而，这是一个理论性的特点，因为它是昂贵的实施。我们还提出了AdaSDCA+：一个实用的变体，在我们的实验中优于现有的非自适应方法。
This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method to adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.