论文标题
最小最大优化算法的限制：融合到虚假的非关键集
The limits of min-max optimization algorithms: convergence to spurious non-critical sets
论文作者
论文摘要
与普通函数最小化问题相比，由于存在周期性周期和类似现象，最小最大优化算法遇到了更大的挑战。即使在凸 - 洞穴制度中可以克服这些行为中的某些行为，但总体案例也更加困难。因此，我们深入研究了一类全面的最新算法和非convex / non-concave问题中普遍的启发式方法，我们确定了以下一般结果：a）a）通常，算法的极限点包含在常见的，平均含量系统的ICT集中； b）该系统的吸引子还以任意较高的可能性吸引了有关算法； c）所有算法避免使用概率1的系统的不稳定集。在表面上，这为最小值算法提供了高度乐观的外观；但是，我们表明，存在未包含所研究问题的任何固定点的伪吸引子。在这方面，我们的工作表明，现有的最小算法可能会遭受不可避免的收敛失败。我们通过简单，二维，几乎双线性问题来说明此类吸引子来补充我们的理论分析。
Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenomena. Even though some of these behaviors can be overcome in the convex-concave regime, the general case is considerably more difficult. On that account, we take an in-depth look at a comprehensive class of state-of-the art algorithms and prevalent heuristics in non-convex / non-concave problems, and we establish the following general results: a) generically, the algorithms' limit points are contained in the ICT sets of a common, mean-field system; b) the attractors of this system also attract the algorithms in question with arbitrarily high probability; and c) all algorithms avoid the system's unstable sets with probability 1. On the surface, this provides a highly optimistic outlook for min-max algorithms; however, we show that there exist spurious attractors that do not contain any stationary points of the problem under study. In this regard, our work suggests that existing min-max algorithms may be subject to inescapable convergence failures. We complement our theoretical analysis by illustrating such attractors in simple, two-dimensional, almost bilinear problems.
