论文标题
梯度下降的复杂性：cls = ppad $ \ cap $ pls
The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
论文作者
论文摘要
我们研究搜索问题，可以通过在有界凸的多面体结构域上执行梯度下降来解决，并表明该类别等于两个众所周知的类别的相交：PPAD和PLS。作为我们的主要基础技术贡献，我们表明，在域上计算一个连续可区分的功能的Karush-Kuhn-tucker（KKT）点$ [0,1]^2 $是PPAD $ \ cap $ pls complete。这是此类显示的第一个非人造问题。我们的结果还暗示，由Daskalakis和Papadimitriou定义为CLS（连续的本地搜索），它是PPAD $ \ CAP $ PLS的更“自然”的对应物，并且包含许多有趣的问题，本身等于PPAD $ \ cap $ pls。
We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain $[0,1]^2$ is PPAD $\cap$ PLS-complete. This is the first non-artificial problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to PPAD $\cap$ PLS and contains many interesting problems - is itself equal to PPAD $\cap$ PLS.
