Block coordinate descent (BCD), also known as nonlinear Gauss-Seidel, is a simple iterative algorithm for nonconvex optimization that sequentially minimizes the objective function in each block coordinate while the other coordinates are held fixed. It is known that block-wise convexity of the objective is not enough to guarantee convergence of BCD to the stationary points and some additional regularity condition is needed. In this work, we provide a simple modification of BCD that has guaranteed global convergence to the stationary points for block-wise convex objective function without additional conditions. Our idea is to restrict the parameter search within a diminishing radius to promote stability of iterates, and then to show that such auxiliary constraint vanishes in the limit. As an application, we provide a modified alternating least squares algorithm for nonnegative CP tensor factorization that is guaranteed to converge to the stationary points of reconstruction error function. We also provide some experimental validation of our result.
翻译:区块坐标下移 (BCD), 也称为非线性 Gaus- Seidel, 是一个简单的非convex 优化的迭代算法, 其顺序将每个区块坐标的目标函数最小化, 而其他坐标则被固定。 众所周知, 区块坐标的相近性不足以保证 BCD 与固定点的趋同, 并且需要附加一些常规性条件 。 在这项工作中, 我们提供了一种简单的 BCD 修改, 保证了全球与固定点的趋同, 以便不附加条件 。 我们的想法是限制在缩小半径范围内的参数搜索, 以促进迭代点的稳定性, 然后显示这种辅助性限制在限制范围内消失 。 作为应用程序, 我们提供一种修改的交替最小方形算法, 用于保证与重建错误功能的固定点趋同。 我们还提供我们结果的实验性验证 。