Iteration Complexity of a Block Coordinate Gradient Descent Method for Convex Optimization
Iteration Complexity of a Block Coordinate Gradient Descent Method for Convex Optimization
复制标题
DOI：
10.1137/140964795
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Xiaoqin Hua;N. Yamashita
中科院分区：
文献类型：
--
作者：
Xiaoqin Hua;N. Yamashita
在本文中，我们研究了具有循环规则的块坐标梯度下降（BCGD）方法用于解决凸优化问题的迭代复杂度。我们提出了一种新的类似 Lipschitz 连续性的假设，并表明所提出的 BCGD 方法的迭代复杂度可以提高到 $O(\frac{\max\{M, \;{L}\}}{\varepsilon})$，其中 $M$ 是所提出假设中的常数，${L}$ 是目标函数梯度的常用 Lipschitz 常数，$\varepsilon>0$ 是所需的精度。此外，我们分析了$M$和${L}$之间的关系，并证明，在最坏的情况下，$M\leq \sqrt{N}{L}$，其中$N$是块的数量。
In this paper, we study the iteration complexity of a block coordinate gradient descent (BCGD) method with a cyclic rule for solving convex optimization problems. We propose a new Lipschitz continuity-like assumption and show that the iteration complexity for the proposed BCGD method can be improved to $O(\frac{\max\{M, \;{L}\}}{\varepsilon})$, where $M$ is the constant in the proposed assumption, ${L}$ is the usual Lipschitz constant for the gradient of the objective function, and $\varepsilon>0$ is the required precision. In addition, we analyze the relation between $M$ and ${L}$, and prove that, in the worst case, $M\leq \sqrt{N}{L}$, where $N$ is the number of blocks.