Efficient Parameter-Free Restarted Accelerated Gradient Methods for Convex and Strongly Convex Optimization

This paper develops a new parameter-free restarted method, namely RPF-SFISTA, and a new parameter-free aggressive regularization method, namely A-REG, for solving strongly convex and convex composite optimization problems, respectively. RPF-SFISTA has the major advantage that it requires no knowledge of both the strong convexity parameter of the entire objective and the Lipschitz constant of the gradient of its smooth part. Unlike several other restarted first-order methods which restart an accelerated composite gradient (ACG) method after a predetermined number of ACG iterations, RPF-SFISTA checks a key inequality at each of its iterations to determine whether to restart. Extensive computational experiments show that RPF-SFISTA is roughly 3 to 15 times faster than other state-of-the-art restarted methods on four important classes of problems. The A-REG method, developed for convex composite optimization, solves each of its strongly convex regularized subproblems according to a stationarity criterion by using RPF-SFISTA with an aggressive initial estimate of the strong convexity parameter of the objective. This scheme is thus more aggressive than several other regularization methods which instead solve their subproblems by running a standard ACG method for a predetermined number of iterations.