论文标题
平滑间隙的二次误差和重新开始的平均原始二重混合梯度
Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
论文作者
论文摘要
我们研究了原始双重混合梯度方法的线性收敛。在对当前分析进行了综述之后，我们表明它们也无法正常解释算法的行为，即使在最简单的问题上也是如此。因此，我们介绍了平滑间隙的二次误差界，这是一个新的规律性假设，可用于广泛的优化问题。配备了此工具，我们设法证明了收敛速度更高。然后，我们表明，平均和重新启动原始的双重混合梯度使我们能够更好地利用规律性常数。关于线性和二次程序，脊回归和图像的数值实验说明了论文的发现。
We study the linear convergence of the primal-dual hybrid gradient method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems. Equipped with this tool, we manage to prove tighter convergence rates. Then, we show that averaging and restarting the primal-dual hybrid gradient allows us to leverage better the regularity constant. Numerical experiments on linear and quadratic programs, ridge regression and image denoising illustrate the findings of the paper.
