Abstract: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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2412.14291 [math.OC] |
| (or arXiv:2412.14291v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2412.14291 arXiv-issued DOI via DataCite |
Submission history
From: Tianjiao Li [view email]
[v1]
Wed, 18 Dec 2024 19:34:16 UTC (573 KB)
[v2]
Thu, 14 May 2026 16:58:17 UTC (596 KB)