Dual Free Adaptive Minibatch SDCA for Empirical Risk Minimization
Dual Free Adaptive Minibatch SDCA for Empirical Risk Minimization
复制标题
DOI：
10.3389/fams.2018.00033
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Xi He;R. Tappenden;Martin Takác
中科院分区：
文献类型：
--
作者：
Xi He;R. Tappenden;Martin Takác
本文提出了一种求解正则化经验风险最小化问题的自适应对偶自由随机对偶坐标递增算法(AdfSDCA)。这是由Shalev-Shwartz(2016)最近关于双重自由SDCA的工作所推动的。我们方法的新奇之处在于，在每次迭代中要更新的坐标是从自适应概率分布中非均匀地选择的，这扩展了前面提到的工作，即只允许从固定的概率分布中均匀地选择“对偶”坐标。我们描述了一种生成非均匀样本的有效迭代过程，其中该方案选择具有最大潜力的坐标来降低当前迭代的次优性。我们还提出了一种比标准方法更具侵略性的adfSDCA的启发式变体。此外，为了利用多核机器，我们考虑了一种小批量adfSDCA算法，并给出了保证算法收敛的复杂性结果。最后，通过几个数值实验验证了该方法的有效性。
In this paper we develop an adaptive dual free Stochastic Dual Coordinate Ascent (adfSDCA) algorithm for regularized empirical risk minimization problems. This is motivated by the recent work on dual free SDCA of Shalev-Shwartz (2016). The novelty of our approach is that the coordinates to update at each iteration are selected non-uniformly from an adaptive probability distribution, and this extends the previously mentioned work which only allowed for a uniform selection of "dual" coordinates from a fixed probability distribution. We describe an efficient iterative procedure for generating the non-uniform samples, where the scheme selects the coordinate with the greatest potential to decrease the sub-optimality of the current iterate. We also propose a heuristic variant of adfSDCA that is more aggressive than the standard approach. Furthermore, in order to utilize multi-core machines we consider a mini-batch adfSDCA algorithm and develop complexity results that guarantee the algorithm's convergence. The work is concluded with several numerical experiments to demonstrate the practical benefits of the proposed approach.