A simple uniformly optimal method without line search for convex optimization
This work addresses the need for simpler, parameter-free optimization algorithms in machine learning and related fields, offering a novel method that eliminates the overhead of line search while maintaining optimal convergence rates.
The paper tackles the problem of convex optimization without requiring line search or prior knowledge of problem parameters like the Lipschitz constant, presenting the auto-conditioned fast gradient method (AC-FGM) that achieves an optimal O(1/k^2) convergence rate for smooth convex optimization and extends to problems with Hölder continuous gradients, with numerical results showing advantages over existing parameter-free methods.
Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this paper, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fast gradient method (AC-FGM) that can achieve an optimal $\mathcal{O}(1/k^2)$ rate of convergence for smooth convex optimization without requiring the estimate of a global Lipschitz constant or the employment of line search procedures. We then extend AC-FGM to solve convex optimization problems with Hölder continuous gradients and show that it automatically achieves the optimal rates of convergence uniformly for all problem classes with the desired accuracy of the solution as the only input. Finally, we report some encouraging numerical results that demonstrate the advantages of AC-FGM over the previously developed parameter-free methods for convex optimization.