论文标题
几何感知通用镜像
Geometry-Aware Universal Mirror-Prox
论文作者
论文摘要
Mirror-Prox（MP）是解决方差不平等问题（VI）问题的众所周知的算法。带有单调操作员的VI涵盖了一大批设置，例如凸最小化，最小值或鞍点问题。为了获得收敛算法，经典MP算法的阶梯大小在很大程度上取决于操作员的问题依赖性知识，例如其平滑度参数，这是很难估计的。最近，引入了用于平滑/有限运算符的MP的通用变体，仅取决于MP中更新的规范。在这项工作中，我们放宽了依赖性，以评估更新之间对布雷格曼（Bregman）差异的更新规范。这种放松使我们能够将通用MP的分析扩展到操作员不平滑或有限的设置。此外，我们在不同的设置中使用随机单调操作员分析了VI问题，并获得最佳速率至对数因子。
Mirror-prox (MP) is a well-known algorithm to solve variational inequality (VI) problems. VI with a monotone operator covers a large group of settings such as convex minimization, min-max or saddle point problems. To get a convergent algorithm, the step-size of the classic MP algorithm relies heavily on the problem dependent knowledge of the operator such as its smoothness parameter which is hard to estimate. Recently, a universal variant of MP for smooth/bounded operators has been introduced that depends only on the norm of updates in MP. In this work, we relax the dependence to evaluating the norm of updates to Bregman divergence between updates. This relaxation allows us to extends the analysis of universal MP to the settings where the operator is not smooth or bounded. Furthermore, we analyse the VI problem with a stochastic monotone operator in different settings and obtain an optimal rate up to a logarithmic factor.
