Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
Authors: Guanghui Lan, Tianjiao Li, Yangyang Xu
Organizations: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332. · Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180.
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 a unified iteration complexity for finding an approximate stationary point for convex and nonconvex problems. 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 unified complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.
Figure 1: Average and standard deviation results by the PG and AC-PG methods on solving 10 independently generated instances of box-constrained quadratic programming. Left: norm of projected gradient mapping at each iteration; Right: estimated local gradient Lipschitz constants by AC-PG starting from different initial estimates.
Figure 2: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=10 with pre-generated data sets for u1 and u2 .
Figure 3: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=100 with pre-generated data sets for u1 and u2 .
Figure 4: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=10 in an online manner, i.e., with samples generated for u1 and u2 while needed.
Figure 5: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=100 in an online manner, i.e., with samples generated for u1 and u2 while needed.