The complexity of gradient descent: CLS = PPAD ∩ PLS
The complexity of gradient descent: CLS = PPAD ∩ PLS
复制标题
梯度下降的复杂度：CLS = PPAD ∩ PLS
DOI：
10.1145/3406325.3451052
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;P. Goldberg;Alexandros Hollender;Rahul Savani
我们研究可以通过在有界凸的多面体域上执行梯度下降来解决的搜索问题，并表明该类别等于两个众所周知的类别的相互作用：PPAD和PLS作为我们的主要基础技术贡献。在域上连续区分函数的Karush-Kuhn-tucker（KKT）点[0,1] 2是PPAD∩pls-complete。在此类中显示完整的结果。 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 ∩ PLS-complete. This is the first natural 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 ∩ PLS and contains many interesting problems - is itself equal to PPAD ∩ PLS.
登录
查看更多内容
DOI：
--
发表时间：
2019
期刊：
COLT 2019 Proceedings
影响因子：
--
作者：
Chatziafratis, Vaggos;Roughgarden, Tim;Wang, Josh
通讯作者：
Wang, Josh
塔斯基定理、超模博弈和均衡的复杂性
DOI：
10.4230/lipics.itcs.2020.18
发表时间：
2020
期刊：
11th Innovations in Theoretical Computer Science Conference
影响因子：
--
作者：
Etessami, Kousha;Papadimitriou, Christos H;Rubinstein, Aviad;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis
势线的独特末端
影响因子：
--
作者：
Fearnley, John;Gordon, Spencer;Mehta, Ruta;Savani, Rahul
通讯作者：
Savani, Rahul
线尾的彩虹 - 彩色卡拉西奥多里定理的 PPAD 公式及其应用
DOI：
10.1137/1.9781611974782.87
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Meunier;Frédéric;Mulzer;Wolfgang;Sarrabezolles;Pauline;Yannik
通讯作者：
Yannik
单纯形算法具有 NP 强大性
DOI：
10.1145/3280847
发表时间：
2018
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Disser;Skutella;Martin
通讯作者：
Martin