  Several classical adaptive optimization algorithms, such as line search and
trust region methods, have been recently extended to stochastic settings where
function values, gradients, and Hessians in some cases, are estimated via
stochastic oracles. Unlike the majority of stochastic methods, these methods do
not use a pre-specified sequence of step size parameters, but adapt the step
size parameter according to the estimated progress of the algorithm and use it
to dictate the accuracy required from the stochastic approximations. The
requirements on stochastic approximations are, thus, also adaptive and the
oracle costs can vary from iteration to iteration. The step size parameters in
these methods can increase and decrease based on the perceived progress, but
unlike the deterministic case they are not bounded away from zero due to
possible oracle failures, and bounds on the step size parameter have not been
previously derived. This creates obstacles in the total complexity analysis of
such methods, because the oracle costs are typically decreasing in the step
size parameter, and could be arbitrarily large as the step size parameter goes
to 0. Thus, until now only the total iteration complexity of these methods has
been analyzed. In this paper, we derive a lower bound on the step size
parameter that holds with high probability for a large class of adaptive
stochastic methods. We then use this lower bound to derive a framework for
analyzing the expected and high probability total oracle complexity of any
method in this class. Finally, we apply this framework to analyze the total
sample complexity of two particular algorithms, STORM and SASS, in the expected
risk minimization problem.
