Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets
This work addresses optimization problems for researchers and practitioners in machine learning and optimization, offering efficient methods for a less-explored class of sets, though it is incremental in extending acceleration techniques to new settings.
The paper tackles feasibility and constrained optimization over smooth and/or strongly convex sets by proposing new projection-free, accelerated first-order methods that use only linesearches and normal vector computations, achieving optimal accelerated convergence rates such as O(1/T) for strongly convex problems and O(1/T^2) for smooth problems.
We consider feasibility and constrained optimization problems defined over smooth and/or strongly convex sets. These notions mirror their popular function counterparts but are much less explored in the first-order optimization literature. We propose new scalable, projection-free, accelerated first-order methods in these settings. Our methods avoid linear optimization or projection oracles, only using cheap one-dimensional linesearches and normal vector computations. Despite this, we derive optimal accelerated convergence guarantees of $O(1/T)$ for strongly convex problems, $O(1/T^2)$ for smooth problems, and accelerated linear convergence given both. Our algorithms and analysis are based on novel characterizations of the Minkowski gauge of smooth and/or strongly convex sets, which may be of independent interest: although the gauge is neither smooth nor strongly convex, we show the gauge squared inherits any structure present in the set.