Beyond Convexity: Stochastic Quasi-Convex Optimization
Elad Hazan111Princeton University; Kfir Y. Levy222Technion; Shai Shalev-Shwartz333The Hebrew University;
Abstract
Stochastic convex optimization is a basic and well studied primitive in machine learning. It is well known that convex and Lipschitz functions can be minimized efficiently using Stochastic Gradient Descent (SGD).
中文速览
随机梯度下降（SGD）在处理非凸问题时饱受梯度爆炸和平台区域的困扰，而这篇论文提出并分析了一种随机归一化梯度下降算法（Stochastic Normalized Gradient Descent，SNGD），每步只按梯度的方向而非梯度本身来更新参数。作者引入了"局部拟凸性"（local-quasi-convexity）和"局部 Lipschitz"这两个比传统凸性宽松得多的条件，证明 SNGD 在满足这些条件的目标函数上能在 O(1/ε²) 步内收敛到全局最优，同时对光滑情形还能获得更快的 O(1/ε) 速率。理论上还揭示了一个有趣的负面结果：与普通 SGD 不同，SNGD 必须使用超过某个最小阈值的 mini-batch，否则算法会发散。这项工作不仅为深度学习中常见的梯度爆炸和鞍点问题提供了严格的理论保障，还证明了广义线性模型（GLM）回归满足上述条件，从而为该算法在实际机器学习任务中的应用奠定了理论基础。
原文 arXiv:1507.02030;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1507.02030v3