论文标题
一种随机方差降低的加速偶对偶偶联方法，用于有限和鞍点问题
A Stochastic Variance-reduced Accelerated Primal-dual Method for Finite-sum Saddle-point Problems
论文作者
论文摘要
在本文中，我们提出了一种带有Bregman距离的方差降低的原始双算法，用于解决有限的和非线性耦合函数，以求解凸形 - concove鞍点问题。这种类型的问题通常在机器学习和游戏理论中出现。基于一些标准假设，算法被证明是$ o \左（\ frac {\ sqrt n}ε\ right）$和$ o \ left（\ frac {n} {\ frac {n} {\ sqrtsqrtε}+\ frac+\ frac {1} = 1.5参数分别是$ n $是函数组件的数量。与现有方法相比，我们的框架对所需的原始双侧梯度样本的数量有了显着改善，以实现原始偶差距的$ε$ - 准确性。我们测试了解决分布强大的优化问题以显示算法的有效性的方法。
In this paper, we propose a variance-reduced primal-dual algorithm with Bregman distance for solving convex-concave saddle-point problems with finite-sum structure and nonbilinear coupling function. This type of problems typically arises in machine learning and game theory. Based on some standard assumptions, the algorithm is proved to converge with oracle complexity of $O\left(\frac{\sqrt n}ε\right)$ and $O\left(\frac{n}{\sqrt ε}+\frac{1}{ε^{1.5}}\right)$ using constant and non-constant parameters, respectively where $n$ is the number of function components. Compared with existing methods, our framework yields a significant improvement over the number of required primal-dual gradient samples to achieve $ε$-accuracy of the primal-dual gap. We tested our method for solving a distributionally robust optimization problem to show the effectiveness of the algorithm.
