  We study oracle complexity of gradient based methods for stochastic
approximation problems. Though in many settings optimal algorithms and tight
lower bounds are known for such problems, these optimal algorithms do not
achieve the best performance when used in practice. We address this
theory-practice gap by focusing on instance-dependent complexity instead of
worst case complexity. In particular, we first summarize known
instance-dependent complexity results and categorize them into three levels. We
identify the domination relation between different levels and propose a fourth
instance-dependent bound that dominates existing ones. We then provide a
sufficient condition according to which an adaptive algorithm with moment
estimation can achieve the proposed bound without knowledge of noise levels.
Our proposed algorithm and its analysis provide a theoretical justification for
the success of moment estimation as it achieves improved instance complexity.
