Stochastic subgradient method converges on tame functions
Damek Davis School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14850, USA; people.orie.cornell.edu/dsd95/. Dmitriy Drusvyatskiy Department of Mathematics, University of Washington, Seattle, WA 98195; www.math.washington.edu/∼similar-to\scriptstyle\simddrusv. Research of Drusvyatskiy was supported by the AFOSR YIP award FA9550-15-1-0237 and by the NSF DMS 1651851 and CCF 1740551 awards. Sham Kakade Departments of Statistics and Computer Science, University of Washington, Seattle, WA 98195; homes.cs.washington.edu/∼similar-to\scriptstyle\simsham/. Sham Kakade acknowledges funding from the Washington Research Foundation Fund for Innovation in Data-Intensive Discovery and the NSF CCF 1740551 award. Jason D. Lee Data Science and Operations Department, Marshall School of Business, University of Southern California, Los Angeles, CA 90089; www-bcf.usc.edu/∼similar-to\scriptstyle\simlee715. JDL acknowledges funding from the ARO MURI Award W911NF-11-1-0303.
Abstract
This work considers the question: what convergence guarantees does the stochastic subgradient method have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. In particular, this work endows the stochastic subgradient method, and its proximal extension, with rigorous convergence guarantees for a wide class of problems arising in data science—including all popular deep learning architectures.
中文速览
随机次梯度法（stochastic subgradient method）是深度学习训练的核心算法，但在函数既不光滑也不凸的情况下，它是否真的会收敛到有意义的点，一直缺乏理论保障。本文证明：只要目标函数是"Whitney可分层的"（Whitney stratifiable）——这是一个涵盖了几乎所有数据科学常用函数的大类，包括带ReLU激活函数的深度神经网络——随机次梯度法的所有极限点几乎必然都是一阶稳定点（first-order stationary point），即Clarke次微分包含零。核心技术路线是：利用Whitney分层结构保证链式法则（chain rule）沿任意绝对连续曲线成立，从而确保函数沿次梯度流单调下降，再结合Lyapunov型随机逼近论证完成收敛性分析；结果同时推广到了带近端步骤（proximal）的变体，且对目标函数不施加任何凸性假设。这项工作首次为TensorFlow、PyTorch等框架中大量实际使用的非光滑非凸优化算法提供了严格的收敛理论基础。
原文 arXiv:1804.07795;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1804.07795v3