  In this paper we consider the unconstrained minimization problem of a smooth
function in ${\mathbb{R}}^n$ in a setting where only function evaluations are
possible. We design a novel randomized derivative-free algorithm --- the
stochastic three points (STP) method --- and analyze its iteration complexity.
At each iteration, STP generates a random search direction according to a
certain fixed probability law. Our assumptions on this law are very mild:
roughly speaking, all laws which do not concentrate all measure on any
halfspace passing through the origin will work. For instance, we allow for the
uniform distribution on the sphere and also distributions that concentrate all
measure on a positive spanning set.
  Given a current iterate $x$, STP compares the objective function at three
points: $x$, $x+\alpha s$ and $x-\alpha s$, where $\alpha>0$ is a stepsize
parameter and $s$ is the random search direction. The best of these three
points is the next iterate. We analyze the method STP under several stepsize
selection schemes (fixed, decreasing, estimated through finite differences,
etc). We study non-convex, convex and strongly convex cases.
