# A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Control

arXiv: https://arxiv.org/abs/1902.01272 · HTML: https://mlsanity.com/paper/1902.01272/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2019.

## Built on by (most cited first, 9 of 9)

- [L2ight: Enabling On-Chip Learning for Optical Neural Networks via Efficient in-situ Subspace Optimization](https://mlsanity.com/paper/2110.14807/) (2021)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networks](https://mlsanity.com/paper/2308.09858/) (2023)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/2209.07883/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Optimization with Random Search](https://mlsanity.com/paper/2510.15610/) (2025)
- [Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02190/) (2026)
- [TACO: Ternary Absolute-max Column-wise One-sparse Optimizer for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02199/) (2026)

## Abstract (arXiv)

We consider the problem of unconstrained minimization of a smooth objective function in Rn 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.