论文标题
非lipschitz优化的随机布雷格曼协调下降方法
Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization
论文作者
论文摘要
我们提出了一种新的\ textit {随机布雷格曼（块）坐标下降}（rbcd）方法，以最大程度地减少复合问题，其中目标函数可以是凸或非凸，并且平滑部分从全局LipsChitz-chitz-chitz-conchitz-conthiul（部分）梯度假设中释放。在基于Bregman距离的相对平滑度的概念下，我们证明生成序列的每个限制点都是固定点。此外，我们表明所提出的方法的迭代复杂性为$ O（n \ varepsilon^{ - 2}）$以实现$ε$ - 稳定点，其中$ n $是坐标块的数量。如果假定目标是凸，则迭代复杂性将提高到$ O（Nε^{ - 1}）$。此外，如果目标是强凸（相对于参考函数），则恢复了全局线性收敛速率。我们还介绍了RBCD方法的加速版本，该版本获得了$ o（n \ varepsilon^{ - 1/γ}）$迭代复杂性的复杂性，其中标量$γ\ in [1,2] $由Bregman距离的\ textit {gentriant transporation Translation varriant}确定。融合分析不假设全球Lipschitz-连续（部分）梯度使我们的结果与复合问题的现有作品不同。
We propose a new \textit{randomized Bregman (block) coordinate descent} (RBCD) method for minimizing a composite problem, where the objective function could be either convex or nonconvex, and the smooth part are freed from the global Lipschitz-continuous (partial) gradient assumption. Under the notion of relative smoothness based on the Bregman distance, we prove that every limit point of the generated sequence is a stationary point. Further, we show that the iteration complexity of the proposed method is $O(n\varepsilon^{-2})$ to achieve $ε$-stationary point, where $n$ is the number of blocks of coordinates. If the objective is assumed to be convex, the iteration complexity is improved to $O(nε^{-1} )$. If, in addition, the objective is strongly convex (relative to the reference function), the global linear convergence rate is recovered. We also present the accelerated version of the RBCD method, which attains an $O(n\varepsilon^{-1/γ} )$ iteration complexity for the convex case, where the scalar $γ\in [1,2]$ is determined by the \textit{generalized translation variant} of the Bregman distance. Convergence analysis without assuming the global Lipschitz-continuous (partial) gradient sets our results apart from the existing works in the composite problems.
