  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.
