提出新收敛标准，让投影SGD在非凸优化中无需方差缩减也能高效收敛。
Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
- 用Goldstein次微分距离衡量收敛，与无约束情况兼容。
- 在独立同分布和混合条件下，得到期望误差O(N^{-1/3})的非渐近界。
- 首次实现非凸投影SGD的高概率非渐近收敛分析，适合理论研究者。
随机梯度下降（SGD）是机器学习的核心算法。当约束通过投影施加时，形成投影随机梯度算法。近年来，大量工作研究了非凸损失下投影SGD的收敛性，但现有结果多基于Moreau包络，导致与无约束方法难以比较；而其他常用梯度映射标准又依赖方差缩减技术。本文针对紧凸集上的非凸损失，提出以梯度到Goldstein次微分的距离作为收敛度量，该标准在无约束情形可还原为经典形式，且无需方差缩减即可保证收敛。对于独立同分布（IID）或满足L-混合条件的数据，本文获得渐近收敛性和期望误差为O(N^{-1/3})的非渐近界，其中N为迭代步数。在子高斯数据下，进一步得到几乎必然的渐近收敛及高概率的O(N^{-1/5})非渐近界。这是首个针对非凸投影SGD的高概率非渐近收敛结果。
原文摘要 · Abstract (English)
Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In recent years, a large body of work has examined the convergence properties of projected SGD for non-convex losses in asymptotic and non-asymptotic settings. Strong quantitative guarantees are available for convergence measured via Moreau envelopes. However, these results cannot be compared directly with work on unconstrained SGD, since the Moreau envelope construction changes the gradient. Other common measures based on gradient mappings have the limitation that convergence can only be guaranteed if variance reduction methods, such as mini-batching, are employed. This paper presents an analysis of projected SGD for non-convex losses over compact convex sets. Convergence is measured via the distance of the gradient to the Goldstein subdifferential generated by the constraints. Our proposed convergence criterion directly reduces to commonly used criteria in the unconstrained case, and we obtain convergence without requiring variance reduction. We obtain results for data that are independent, identically distributed (IID) or satisfy mixing conditions ($L$-mixing). In these cases, we derive asymptotic convergence and $O(N^{-1/3})$ non-asymptotic bounds in expectation, where $N$ is the number of steps. In the case of IID sub-Gaussian data, we obtain almost-sure asymptotic convergence and high-probability non-asymptotic $O(N^{-1/5})$ bounds. In particular, these are the first non-asymptotic high-probability bounds for projected SGD with non-convex losses.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。