Department of Computer Science | Institute of Theoretical Computer Science

We consider unconstrained randomized optimization of convex objective
functions. We analyze the Random Pursuit algorithm, which iteratively
computes an approximate solution to the optimization problem by
repeated optimization over a randomly chosen one-dimensional
subspace. This randomized method only uses zeroth-order information
about the objective function and does not need any problem-specific
parametrization. We prove convergence and give convergence rates for
smooth objectives assuming that the one-dimensional optimization can
be solved exactly or approximately by an oracle. A convenient property
of Random Pursuit is its invariance under strictly monotone
transformations of the objective function. It thus enjoys identical
convergence behavior on a wider function class. To support the
theoretical results we present extensive numerical performance results
of Random Pursuit, two gradient-free algorithms recently proposed by
Nesterov, and a classical adaptive step-size random search scheme. We
also present an accelerated heuristic version of the Random Pursuit
algorithm which significantly improves standard Random Pursuit on all
numerical benchmark problems. A general comparison of the experimental
results reveals that (i) standard Random Pursuit is effective on
strongly convex functions with moderate condition number, and (ii) the
accelerated scheme is comparable to Nesterov's fast gradient method
and outperforms adaptive step-size strategies. The appendix contains
additional supporting online material.