  It is known that the curvature of the feasible set in convex optimization
allows for algorithms with better convergence rates, and there has been renewed
interest in this topic both for offline as well as online problems. In this
paper, leveraging results on geometry and convex analysis, we further our
understanding of the role of curvature in optimization:
  - We first show the equivalence of two notions of curvature, namely strong
convexity and gauge bodies, proving a conjecture of Abernethy et al. As a
consequence, this show that the Frank-Wolfe-type method of Wang and Abernethy
has accelerated convergence rate $O(\frac{1}{t^2})$ over strongly convex
feasible sets without additional assumptions on the (convex) objective
function.
  - In Online Linear Optimization, we identify two main properties that help
explaining \emph{why/when} Follow the Leader (FTL) has only logarithmic regret
over strongly convex sets. This allows one to directly recover a recent result
of Huang et al., and to show that FTL has logarithmic regret over strongly
convex sets whenever the gain vectors are non-negative.
  - We provide an efficient procedure for approximating convex bodies by
strongly convex ones while smoothly trading off approximation error and
curvature. This allows one to extend the improved algorithms over strongly
convex sets to general convex sets. As a concrete application, we extend the
results of Dekel et al. on Online Linear Optimization with Hints to general
convex sets.
