步子太快容易牺牲精度，梯度下降复杂度获严格数学证明

图片地址：https://img.ithome.com/newsuploadfiles/2021/8/0a5767a8-4d20-4d5f-8c99-e814dbaab808.gif

梯度下降是机器学习中求最小值最常用的一种算法。尽管这种算法应用广泛，但是人们关于它计算复杂度的理论研究却寥寥无几。在今年 ACM 举办的计算机理论顶会 STOC 上，牛津大学和利物浦大学的学者们，给我们证明了这个理论问题的答案。他们得到了梯度下降算法的计算复杂度，等于两类计算机问题的交集。这篇文章也成为了 STOC 2021 的最佳论文。梯度下降的复杂度四位作者研究人员将目光放在了 TFNP 中两个子集问题的交集。第一个子集称为 PLS （多项式局部搜索）。这是一系列问题，涉及在特定区域中寻找函数的最小值或最大值。属于 PLS 的一个典型例子是规划一条路线的任务，以最短的路线经过一些城市，且只能通过切换城市的顺序来改变行程。通过调整顺序可以很容易看出哪些路线缩短了行程，最终你会找到某一条路线，无法进一步缩短路程，这条路线 x 就是你要找到的最小值。用数学公式来表示就是：（p 是求路线总长度的函数，g (x) 表示改变