EFFICIENCY OF COORDINATE DESCENT METHODS ON HUGE-SCALE OPTIMIZATION PROBLEMS
EFFICIENCY OF COORDINATE DESCENT METHODS ON HUGE-SCALE OPTIMIZATION PROBLEMS
复制标题
DOI：
10.1137/100802001
复制
发表时间：
2012-01-01
影响因子：
3.1
通讯作者：
Nesterov, Yu
中科院分区：
文献类型：
--
作者：
Nesterov, Yu
在本文中，我们提出了解决巨大优化问题的新方法。对于这种大小的问题，即使是最简单的全维矢量操作也非常昂贵。因此，我们建议根据决策变量的随机部分更新应用优化技术。对于这些方法，我们证明了收敛速率的全局估计。令人惊讶的是，对于某些类别的目标函数，我们的结果比确定性算法的标准最坏情况界限更好。我们提出了该方法的受限和不受约束的版本及其加速变体。我们的数值测试证实了该技术在规模很大的问题上的高效率。
In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size.