按年被提到
20202021 · 2 次2026
机器学习与深度学习›优化与可微编程·arXiv:2011.01929 · cs.CC

The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani · 2020
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2021-08-20 · 最近 2023-07-30
2不同的人
2活跃月份
2讨论串
32被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论belter · 2021-08

“"...It is hard to overstate the importance of Gradient Descent. As noted by Jin et al. [2021], “Machine learning algorithms generally arise via formulations as optimization problems, and,despite a massive classical toolbox of sophisticated optimization algorithms and a major modern effort to further develop that toolbox, the simplest algorithms—gradient d…”

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS原评论 ↗
评论eterevsky · 2023-07

“Here's the original paper: https://arxiv.org/abs/2011.01929 And here are the complexity classes that are mentioned in the abstract: https://complexityzoo.net/Complexity_Zoo:P#ppad and https://complexityzoo.net/Complexity_Zoo:P#pls.”

Computer Scientists Discover Limits of Gradient Descent原评论 ↗
被提交为 story · 1 次