提出自适应步长投影梯度法，无需预先知道梯度光滑性参数
Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
- 基于历史梯度信息动态估计光滑性常数，实现自适应步长
- 在非凸与随机优化中均达到最优迭代复杂度
- 适合缺乏梯度光滑性先验的优化场景，如深度学习
针对在凸紧集上最小化光滑但非凸函数的问题，我们提出一类新型投影梯度（PG）方法。首先对固定步长的PG方法进行新分析，首次获得寻找近似驻点的最佳已知迭代复杂度。随后提出一种“自适应条件”投影梯度（AC-PG）变体，无需输入梯度的Lipschitz常数或线搜索，仅通过前序迭代的一阶信息估计该常数，并证明低估带来的误差可被有效控制。进一步将方法推广至随机设置，提出随机投影梯度（SPG）和方差缩减随机梯度（VR-SPG）方法，在不同查询器设置下获得新的复杂度界。同时为两类随机PG方法设计自适应步长策略，并建立可比收敛保证。
原文摘要 · Abstract (English)
We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving the best-known iteration complexity for finding an approximate stationary point of the problem. We then develop an "auto-conditioned" projected gradient (AC-PG) variant that achieves the same iteration complexity without requiring the input of the Lipschitz constant of the gradient or any line search procedure. The key idea is to estimate the Lipschitz constant using first-order information gathered from the previous iterations, and to show that the error caused by underestimating the Lipschitz constant can be properly controlled. We then generalize the PG methods to the stochastic setting, by proposing a stochastic projected gradient (SPG) method and a variance-reduced stochastic gradient (VR-SPG) method, achieving new complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。