Random permutations fix a worst case for cyclic coordinate descent
Random permutations fix a worst case for cyclic coordinate descent
复制标题
DOI：
10.1093/imanum/dry040
复制
发表时间：
2016-07
影响因子：
2.1
通讯作者：
Ching-pei Lee;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Ching-pei Lee;Stephen J. Wright
用于最小化非线性函数的坐标下降法的各种变体部分地由考虑坐标松弛的顺序来区分。三种常见的排序是循环（CCD），其中我们按顺序循环遍历$x$的组件；随机化（RCD），在每次迭代中随机独立地选择要更新的组件；随机排列循环（RPCD），它与CCD的不同之处在于在每个循环开始时将随机排列应用于变量。已知的收敛保证CCD和RPCD比RCD弱，尽管在大多数实际情况下，所有这些变体的计算性能是相似的。对于某种二次函数，CCD的速度明显慢于RCD；Sun & Ye最近的一篇论文（2016），循环坐标下降的最坏情况复杂性：随机版本的O(n^2)$缺口。技术报告。斯坦福，加州：斯坦福大学管理科学与工程系。arXiv:1604.07130)探讨了CCD对这类函数的不良行为。RPCD方法在这些功能上执行得很好，在某些情况下甚至比RCD更好。本文对RPCD的良好性能进行了严密的分析。
Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently at each iteration; and random-permutations cyclic (RPCD), which differs from CCD only in that a random permutation is applied to the variables at the start of each cycle. Known convergence guarantees are weaker for CCD and RPCD than for RCD, though in most practical cases, computational performance is similar among all these variants. There is a certain type of quadratic function for which CCD is significantly slower than for RCD; a recent paper by Sun & Ye (2016, Worst-case complexity of cyclic coordinate descent: $O(n^2)$ gap with randomized version. Technical Report. Stanford, CA: Department of Management Science and Engineering, Stanford University. arXiv:1604.07130) has explored the poor behavior of CCD on functions of this type. The RPCD approach performs well on these functions, even better than RCD in a certain regime. This paper explains the good behavior of RPCD with a tight analysis.