论文标题
一种用于凸优化的新的随机原始二重式算法，并具有最佳的最后迭代速率
A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates
论文作者
论文摘要
我们开发了一种新型的统一随机区块坐标原始偶对算法，以解决一类非平滑限制的凸优化问题，该问题涵盖了文献中不同的现有变体和模型设置。我们证明，我们的算法达到了最佳$ \ MATHCAL {O}（N/K）$和$ \ MATHCAL {O}（n^2/K^2）$收敛率（在两种情况下最高为恒定因素）：在两种情况下：一般的凸度和强质量和强凸度，其中$ k $是$ k $ is the $ k $ is the Iteration Counter和n是block-block-coord block-coord-coord shobord-coord shobord-coord nekord nekord nekord nekord nekord nekord。我们的收敛速率是通过三个标准获得的：违反原始客观残差和原始可行性，双重客观残差和原始的双重预期间隙。此外，我们针对原始问题的速度是最后一个迭代序列。我们的双收敛保证还需要Lipschitz的连续性假设。我们指定算法以处理仍在应用我们的费率的两种重要特殊情况。最后，我们在两个经过良好的数值示例上验证了我们的算法，并将其与两种现有方法进行比较。我们的结果表明，所提出的方法在不同的实验上具有令人鼓舞的性能。
We develop a novel unified randomized block-coordinate primal-dual algorithm to solve a class of nonsmooth constrained convex optimization problems, which covers different existing variants and model settings from the literature. We prove that our algorithm achieves optimal $\mathcal{O}(n/k)$ and $\mathcal{O}(n^2/k^2)$ convergence rates (up to a constant factor) in two cases: general convexity and strong convexity, respectively, where $k$ is the iteration counter and n is the number of block-coordinates. Our convergence rates are obtained through three criteria: primal objective residual and primal feasibility violation, dual objective residual, and primal-dual expected gap. Moreover, our rates for the primal problem are on the last iterate sequence. Our dual convergence guarantee requires additionally a Lipschitz continuity assumption. We specify our algorithm to handle two important special cases, where our rates are still applied. Finally, we verify our algorithm on two well-studied numerical examples and compare it with two existing methods. Our results show that the proposed method has encouraging performance on different experiments.
