Optimization of Convex Functions with Random Pursuit

By Sebastian U. Stich, Christian L. Müller, Bernd Gärtner. 2011

58 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “Derivative-free methods were among the earliest algorithms to numerically solve unconstrained optimization problems, and have recently enjoyed increasing interest, being especial useful in black-box situations where gradient information is hard to compute or does not exist [15, 18].”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, background): “However, probabilistic ideas are also increasingly and successfully penetrating “continuous” fields, such as numerical linear algebra [57, 10, 11, 60, 27, 50, 1], optimization [24, 33, 35, 46, 59, 40], control theory [4, 5, 62], machine learning [52, 47, 21, 14, 44], and signal processing [7, 22].”