A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Control
Preprint
Abstract
We consider the problem of unconstrained minimization of a smooth objective function in $\R^n$ in a setting where only function evaluations are possible. While importance sampling is one of the most popular techniques used by machine learning practitioners to accelerate the convergence of their models when applicable, there is not much existing theory for this acceleration in the derivative-free setting. In this paper, we propose the first derivative free optimization method with importance sampling and derive new improved complexity results on non-convex, convex and strongly convex functions. We conduct extensive experiments on various synthetic and real LIBSVM datasets confirming our theoretical results. We further test our method on a collection of continuous control tasks on MuJoCo environments with varying difficulty. Experiments suggest that our algorithm is practical for high dimensional continuous control problems where importance sampling results in a significant sample complexity improvement.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketchingMathematical Programming, 2020
- On optimal probabilities in stochastic coordinate descent methodsOptimization Letters, 2015
- Worst case complexity of direct searchEURO Journal on Computational Optimization, 2013
- Smoothing and worst-case complexity for direct-search methods in nonsmooth optimizationIMA Journal of Numerical Analysis, 2012
- A computational framework for derivative-free optimization of cardiovascular geometriesComputer Methods in Applied Mechanics and Engineering, 2008
- Trailing-edge noise reduction using derivative-free optimization and large-eddy simulationJournal of Fluid Mechanics, 2007
- Optimal Aeroacoustic Shape Design Using the Surrogate Management FrameworkOptimization and Engineering, 2004
- Shape optimization by the homogenization methodNumerische Mathematik, 1997
- On the convergence of the Baba and Dorea random optimization methodsJournal of Optimization Theory and Applications, 1990
- Convergence of a random optimization method for constrained optimization problemsJournal of Optimization Theory and Applications, 1981