Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods
This work provides a parameter-free and optimal restart scheme for first-order methods, addressing a key bottleneck in optimization for applications like compressive imaging and machine learning, though it is incremental in extending sharpness theory.
The authors tackled the problem of accelerating first-order optimization methods via restarts under approximate sharpness, a robust generalization of sharpness that handles unknown constants, noise, and infeasible iterates, achieving optimal convergence rates without prior knowledge of problem-specific parameters.
Sharpness is an almost generic assumption in continuous optimization that bounds the distance from minima by objective function suboptimality. It facilitates the acceleration of first-order methods through restarts. However, sharpness involves problem-specific constants that are typically unknown, and restart schemes typically reduce convergence rates. Moreover, these schemes are challenging to apply in the presence of noise or with approximate model classes (e.g., in compressive imaging or learning problems), and they generally assume that the first-order method used produces feasible iterates. We consider the assumption of approximate sharpness, a generalization of sharpness that incorporates an unknown constant perturbation to the objective function error. This constant offers greater robustness (e.g., with respect to noise or relaxation of model classes) for finding approximate minimizers. By employing a new type of search over the unknown constants, we design a restart scheme that applies to general first-order methods and does not require the first-order method to produce feasible iterates. Our scheme maintains the same convergence rate as when the constants are known. The convergence rates we achieve for various first-order methods match the optimal rates or improve on previously established rates for a wide range of problems. We showcase our restart scheme in several examples and highlight potential future applications and developments of our framework and theory.