Cyclic Coordinate Dual Averaging with Extrapolation
提出一种新的循环块坐标方法，适用于单调算子变分不等式问题，收敛速度匹配全梯度法，并引入方差缩减变体以降低计算成本。
Cyclic block coordinate methods are a fundamental class of optimization methods widely used in practice and implemented as part of standard software packages for statistical learning. Nevertheless, their convergence is generally not well understood and so far their good practical performance has not been explained by existing convergence analyses. In this work, we introduce a new block coordinate method that applies to the general class of variational inequality (VI) problems with monotone operators. This class includes composite convex optimization problems and convex-concave min-max optimization problems as special cases and has not been addressed by the existing work. The resulting convergence bounds match the optimal convergence bounds of full gradient methods, but are provided in terms of a novel gradient Lipschitz condition w.r.t. a Mahalanobis norm. For coordinate blocks, the resulting gradient Lipschitz constant in our bounds is never larger than a factor compared to the traditional Euclidean Lipschitz constant, while it is possible for it to be much smaller. Further, for the case when the operator in the VI has a finite-sum structure, we propose a variance-reduced variant of our method which further decreases the per-iteration cost and has better convergence rates in certain regimes. To obtain these results, we use a gradient extrapolation strategy that allows us to view a cyclic collection of block coordinatewise gradients as one implicit gradient.