  We consider smooth stochastic convex optimization problems in the context of
algorithms which are based on directional derivatives of the objective
function. This context can be considered as an intermediate one between
derivative-free optimization and gradient-based optimization. We assume that at
any given point and for any given direction, a stochastic approximation for the
directional derivative of the objective function at this point and in this
direction is available with some additive noise. The noise is assumed to be of
an unknown nature, but bounded in the absolute value. We underline that we
consider directional derivatives in any direction, as opposed to coordinate
descent methods which use only derivatives in coordinate directions. For this
setting, we propose a non-accelerated and an accelerated directional derivative
method and provide their complexity bounds. Our non-accelerated algorithm has a
complexity bound which is similar to the gradient-based algorithm, that is,
without any dimension-dependent factor. Our accelerated algorithm has a
complexity bound which coincides with the complexity bound of the accelerated
gradient-based algorithm up to a factor of square root of the problem
dimension. We extend these results to strongly convex problems.
