  We study local complexity measures for stochastic convex optimization
problems, providing a local minimax theory analogous to that of H\'{a}jek and
Le Cam for classical statistical problems. We give complementary optimality
results, developing fully online methods that adaptively achieve optimal
convergence guarantees. Our results provide function-specific lower bounds and
convergence results that make precise a correspondence between statistical
difficulty and the geometric notion of tilt-stability from optimization. As
part of this development, we show how variants of Nesterov's dual averaging---a
stochastic gradient-based procedure---guarantee finite time identification of
constraints in optimization problems, while stochastic gradient procedures
fail. Additionally, we highlight a gap between problems with linear and
nonlinear constraints: standard stochastic-gradient-based procedures are
suboptimal even for the simplest nonlinear constraints, necessitating the
development of asymptotically optimal Riemannian stochastic gradient methods.
