Parallel distributed block coordinate descent methods based on pairwise comparison oracle
Parallel distributed block coordinate descent methods based on pairwise comparison oracle
复制标题
DOI：
10.1007/s10898-016-0465-x
复制
发表时间：
2014-09
影响因子：
1.8
通讯作者：
Kota Matsui;Wataru Kumagai;T. Kanamori
中科院分区：
文献类型：
--
作者：
Kota Matsui;Wataru Kumagai;T. Kanamori
提出了一种求解无约束优化问题的块坐标下降算法。我们的算法仅使用函数值的成对比较，这只告诉我们两点上函数值的顺序，并且不需要计算函数值本身或梯度。我们的算法迭代两个步骤：方向估计步骤和搜索步骤。在方向估计步骤中，通过具有成对比较的基于块坐标下降的计算方法来估计牛顿型搜索方向。在搜索步骤中，数值解沿估计方向沿着更新。方向估计步骤的计算可以很容易地并行化，因此，该算法可以有效地找到目标函数的最小值。此外，我们从理论上推导出我们的算法的收敛速度的上界，并表明我们的算法实现了特定情况下的最佳查询复杂度。在数值实验中，我们表明，我们的方法有效地找到最优解相比，一些现有的方法的基础上成对比较。
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. Our algorithm uses only pairwise comparison of function values, which tells us only the order of function values over two points, and does not require computation of a function value itself or a gradient. Our algorithm iterates two steps: the direction estimate step and the search step. In the direction estimate step, a Newton-type search direction is estimated through a block coordinate descent-based computation method with the pairwise comparison. In the search step, a numerical solution is updated along the estimated direction. The computation in the direction estimate step can be easily parallelized, and thus, the algorithm works efficiently to find the minimizer of the objective function. Also, we theoretically derive an upper bound of the convergence rate for our algorithm and show that our algorithm achieves the optimal query complexity for specific cases. In numerical experiments, we show that our method efficiently finds the optimal solution compared to some existing methods based on the pairwise comparison.