The complexity of Gradient Descent: CLS = PPAD 交 PLS

[jianlingl]

摘要： 我们研究了梯度下降可以解决的有界凸多边形领域的搜索问题，并且展示了这类问题跟两个著名问题的交集一样，即PPAD和PLS。作为我们主要的基础技术贡献，我们证明了在定义域上计算连续可微函数（Karush-Kuhn-Tuker）KKT点是PPAD∩PLS-complete问题。这是这类问题的第一个完整的自然问题。我们的结果表明，由Daskalakis和Papadimitriou定义的类CLS(连续局部搜索)本身就等于PPAD∩PLS，它是PPAD∩PLS的更自然的对应，包含许多有趣的问题