# Gradient Estimation with Simultaneous Perturbation and Compressive Sensing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2015.

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

- [Online Multi-Agent Decentralized Byzantine-robust Gradient Estimation](https://mlsanity.com/paper/2209.15274/) (2022)
- [CONGO: Compressive Online Gradient Optimization](https://mlsanity.com/paper/2407.06325/) (2024)

## Abstract (arXiv)

This paper aims at achieving a "good" estimator for the gradient of a function on a high-dimensional space. Often such functions are not sensitive in all coordinates and the gradient of the function is almost sparse. We propose a method for gradient estimation that combines ideas from Spall's Simultaneous Perturbation Stochastic Approximation with compressive sensing. The aim is to obtain "good" estimator without too many function evaluations. Application to estimating gradient outer product matrix as well as standard optimization problems are illustrated via simulations.