  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.
