论文标题
非convex-concove minimax问题的混合方差降低的SGD算法
Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
论文作者
论文摘要
我们开发了一种新颖的单环差异算法，以求解一类随机的非convex-convex minimax问题，该问题涉及非凸线线性目标函数，该问题在机器学习和强大的优化等不同领域中具有各种应用。该问题类别由于其非平滑度，非概念性，非线性和目标函数的不可分割性而面临一些计算挑战。我们的方法取决于最近的想法的新组合，包括平滑和混合偏见的差异技术。我们的算法及其变体可以实现$ \ MATHCAL {O}（t^{ - 2/3}）$ - 收敛速率和在标准假设下的最著名的Oracle复杂性，其中$ t $是迭代计数器。与现有方法相比，它们具有几个计算优势，例如易于实现和参数调整要求。它们还可以在衍生估计器上与单个样本或小批量一起工作，并且步骤尺寸恒定或减小。我们通过两个数值示例，包括非平滑和非convex-non-tronglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglongy minimax模型，证明了算法对现有方法的好处。
We develop a novel and single-loop variance-reduced algorithm to solve a class of stochastic nonconvex-convex minimax problems involving a nonconvex-linear objective function, which has various applications in different fields such as machine learning and robust optimization. This problem class has several computational challenges due to its nonsmoothness, nonconvexity, nonlinearity, and non-separability of the objective functions. Our approach relies on a new combination of recent ideas, including smoothing and hybrid biased variance-reduced techniques. Our algorithm and its variants can achieve $\mathcal{O}(T^{-2/3})$-convergence rate and the best known oracle complexity under standard assumptions, where $T$ is the iteration counter. They have several computational advantages compared to existing methods such as simple to implement and less parameter tuning requirements. They can also work with both single sample or mini-batch on derivative estimators, and with constant or diminishing step-sizes. We demonstrate the benefits of our algorithms over existing methods through two numerical examples, including a nonsmooth and nonconvex-non-strongly concave minimax model.
