Optimization of convex functions with random pursuit
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(20)- Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions
- Variable metric random pursuit
- Linearly convergent adjoint free solution of least squares problems by random descent
- Methods to compare expensive stochastic optimization algorithms with random restarts
- Global optimization using random embeddings
- Small errors in random zeroth-order optimization are imaginary
- Curvature-aware derivative-free optimization
- Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Almost sure hypothesis testing and a resolution of the Jeffreys-Lindley paradox
- Stochastic three points method for unconstrained smooth minimization
- An accelerated method for derivative-free smooth stochastic convex optimization
- Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling
- A simple randomised algorithm for convex optimisation
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Random gradient-free minimization of convex functions
- Randomized Hessian estimation and directional search
- Randomized iterative methods for linear systems
- A count column sketch method for tensor auto-regression parameter estimation
- Derivative-free optimization methods
This page was built for publication: Optimization of convex functions with random pursuit
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848195)
