Many black-box optimization problems have a useful property and a nasty one. The useful property is that only a few of the millions of input coordinates change the objective much at any point, so the gradient is sparse. That lets compressed-sensing estimators recover it from a few dozen function evaluations instead of one evaluation per coordinate. The nasty property is that real evaluations of latency, price, or simulator output come with heavy-tailed noise, whose occasional huge outliers can make the variance, or even the mean, infinite. The fastest sparse estimators assume this noise away. The methods built for heavy-tailed noise ignore sparsity and pay a query cost that grows with the square of the dimension.
This note proposes an estimator meant to work under both conditions. It also argues that the place where they collide most sharply is the start of a nonconvex optimization run. Near a random starting point the gradient is tiny, so heavy-tailed noise swamps the few measurements a sparse estimator takes. Whether a run escapes the flat starting region then depends on luck rather than on the algorithm. The estimator is a sparse regression of raw function values on query locations, with three choices that work together. It fits with an absolute-value loss. It estimates a free offset term instead of subtracting a single shared base evaluation. It pools every past query within a small radius of the current point. Together these make recovery depend on the noise's median rather than its moments, remove the need for symmetric noise, and add measurements exactly where gradients are smallest.
Core Claim
Sparse zeroth-order estimators work from finite differences $f(x+u_i)-f(x)$ against one shared base value $f(x)$, where "zeroth-order" means the algorithm sees only function values, never gradients. Under heavy-tailed noise this design fails in a specific way. One outlier in the base evaluation shifts every measurement by the same amount. That is a dense corruption, and no robust regression that tolerates a fraction of bad rows can undo it. We instead estimate, at iterate $x_t$,
$$(\hat c_t,\hat g_t)=\arg\min_{c,\,g}\ \sum_{j\in\mathcal{P}_t}\big|\,f_j - c - \langle g,\ z_j - x_t\rangle\big| + \lambda\|g\|_1 .$$
Here $z_j$ is a past or current query location and $f_j$ the noisy value observed there. $\mathcal{P}_t$ is the set of queries with $\|z_j-x_t\|\le r$. The scalar $c$ is a free offset, $g$ is the gradient estimate, and $\lambda$ sets the sparsity penalty.
The free offset absorbs both $f(x_t)$ and the noise's median. So the estimator needs only independent noise with a common median and positive density at that median. It needs neither symmetry nor any finite moment, including the infinite-mean regime where tail index $\kappa\le 1$. Pooling within radius $r$ adds a curvature bias of order $Lr^2$, where $L$ is the gradient's Lipschitz constant, because a smooth function deviates from its linear approximation quadratically.
On flat starting regions, step sizes are small, so many past queries fall inside the ball. The effective number of measurements grows exactly when the signal is weakest. Our central empirical claim is that this turns escape from random initialization under heavy-tailed noise from a dimension-dependent, high-variance event into one whose query cost scales roughly as $s\log d$, where $s$ is the sparsity.
Relation to Prior Work
Three groups of papers frame the problem.
The sparse zeroth-order estimators supply the measurement model, and their stated limitation motivates this work. Simultaneous perturbation with Lasso recovery (Borkar et al.; Stochastic Zeroth-order Optimization in High Dimensions) and CONGO recover gradients from $O(s\log(d/s))$ queries with least-squares-type recovery under light-tailed noise. CONGO's regret proofs also assume convexity. GraCe reaches $O(s\log\log d)$ with combinatorial recovery, but its authors state that it assumes noise-free evaluations. We keep the sparse measurement idea, replace the squared loss with an absolute loss plus a free offset, and drop the convention of treating each step as an isolated recovery problem.
The heavy-tailed methods supply robustness and show its cost. Median Clipping for zeroth-order optimization handles noise with $\kappa>0$ through coordinatewise medians and clipping. It needs symmetric noise, convexity, and $\tilde O(d^2\varepsilon^{-2})$ iterations. Our offset term targets the symmetry requirement, and sparsity targets the $d^2$ cost. Robust gradient estimation in the presence of heavy-tailed noise is first-order only. It shows that componentwise clipping beats vector clipping as tails get heavier, and that larger batches do not fix heavy tails. That result constrains our design: plain averaging cannot be the answer. Liu and Zhou show that normalized momentum handles heavy-tailed first-order noise in nonconvex problems without clipping. We test whether normalization applied after sparse recovery is enough, and we expect it is not, because the corruption happens before recovery.
The initialization literature defines the regime we test. Fast Escape, Slow Convergence describes the phases of phase-retrieval dynamics, including escape from a near-zero-correlation plateau, for exact gradient flow. Tractable heavy-tailed phase retrieval shows that ordinary spectral warm starts break under heavy-tailed noise and repairs them with truncation and robust principal component analysis, using dense first-order measurements. PhaseMax shows that the quality of the starting anchor alone moves sample cost from $O(n)$ to $O(n^{1.5})$.
None of these papers studies what a query-limited, noise-corrupted sparse estimator does during escape. That is the question this note addresses.
Research Program
The work has three parts.
The first part builds and analyzes the estimator. The objective above is a linear program. We solve it with a warm-started first-order solver whose cost is linear in $d$ times the size of $\mathcal{P}_t$. This places the method at $d$ up to roughly $10^5$. GraCe's $10^8$ regime is out of scope.
For theory, we aim to prove support recovery and an $\ell_2$ error bound for $\hat g_t$ with fresh Gaussian perturbations. The bound would depend on the noise density at its median, not on its moments, using $m=O(s\log d)$ queries. We then extend it to pooled queries. Pooling introduces the main technical risk. Past iterates move along past gradient estimates, so the displacements $z_j-x_t$ are correlated with the true support, and the usual compressed-sensing conditions on the design need not hold. We will measure the conditioning of the pooled design directly. If it degrades, we restrict pooling to the random-perturbation part of each query, which discards the iterate drift.
The second part tests escape. We build a hidden-subspace phase-retrieval objective, $f(x)=\tfrac1n\sum_i(\langle a_i,x_S\rangle^2-y_i)^2$, with $d=10^4$ and an unknown support $S$ of size $s\in\{10,50\}$. Its gradient is exactly $s$-sparse, and it has a flat region at the origin. We also build a power-law variant with $\lambda_i\propto i^{-a}$, following Fast Escape, Slow Convergence. On these objectives we measure three things: the probability that a random start escapes within a query budget, the number of queries until the iterate's correlation with the truth exceeds 0.5, and the variance of that number across starts. Separately, we test whether sparse thresholding wrongly zeroes out the slow, low-variance directions late in the run.
The third part checks transfer to the noisy benchmarks listed below.
Baselines
The naive reference is a single-sample averaged estimator: spherical-perturbation finite differences against one base query, plain mean, no clipping, no sparsity. It shows how badly heavy-tailed noise breaks the unprotected pipeline.
The strongest heavy-tailed competitor is the dense median-clipping method of Median Clipping. It is the only method in the file with guarantees for zeroth-order noise with $\kappa\le1$. Its reported result is an iteration complexity of $\tilde O(d^2\varepsilon^{-2})$ for any $\kappa>0$. Its experiments report only that non-median methods fail to converge when $\kappa\le1$, and no reported numerical result was found on Lacuna for its final accuracy.
The strongest sparse competitor is CONGO-style Lasso or CoSaMP recovery from CONGO. It reports about 45% system-cost reduction on DeathStarBench for fixed workloads. We also run GraCe, which reports near-optimal solutions within 1,000 queries on noise-free DISTANCE where 12 baselines failed after 5,000 (GraCe). We give it repeated-query averaging so that it can run under noise at all. No reported result was found on Lacuna for any sparse zeroth-order method under heavy-tailed noise.
All methods get the same total function-evaluation budget, not the same iteration count. All use the same noise draws per seed. Each gets an equal hyperparameter search of 30 configurations over step size, clipping or sparsity level, and batch size, tuned on held-out seeds.
Three ablations isolate the ingredients: absolute loss without the free offset (shared base difference), absolute loss with the offset but no pooling, and offset plus pooling with squared loss. We count the method as beating the baselines only if it reaches the correlation-0.5 threshold with at least 3× fewer queries than the best baseline at $\kappa\le1$. It must do so with lower across-start variance, and without losing more than 10% to Lasso under Gaussian noise.
Why not just…?
Why not just use larger perturbation batches and average? For $\alpha$-stable noise with $\alpha\le1$, the mean of many draws is as spread out as a single draw. Robust gradient estimation shows that larger batches do not fix heavy-tailed gradients. Our naive baseline at matched budget will show this directly.
Why not just take the median of repeated queries at each point and then run Lasso? This is the real threat. For symmetric noise, a median of $k$ repeats has light tails, and ordinary Lasso then works. It differs from our method in two ways. It spends $k$ evaluations per measurement where the absolute-loss fit uses each evaluation once with fresh directions. It also cannot reuse queries from earlier iterates, because those were taken at different points. With an asymmetric noise median it also needs the base point repeated, or it keeps a bias. We include it as a baseline at $k\in\{3,5,9\}$, at matched budget, under both symmetric and asymmetric (skewed-stable) noise. If it matches us on escape cost under symmetric noise, we will report that the gain comes from the offset term and pooling in the asymmetric and flat-region regimes only.
Why not just recover with Lasso and then normalize or clip the estimate? Normalized momentum (Liu and Zhou) and componentwise clipping act after recovery. A base-query outlier, however, has already moved the recovered support. Clipping cannot restore coordinates that recovery never selected. We test Lasso combined with normalized momentum and Lasso combined with componentwise clipping, measuring support-recovery accuracy per step alongside optimization progress.
Why not just use a robust warm start and skip escape entirely? Truncated robust spectral initialization (Tractable heavy-tailed phase retrieval) needs dense first-order access to measurements, which a black-box oracle does not give. Where a structured problem does allow it, we report it as an upper reference for how fast escape could be.
Proposed Experiments
The synthetic suite has three parts. It runs DISTANCE and MAGNITUDE from GraCe at $d=10^4$. It runs the hidden-subspace phase-retrieval objective with isotropic and power-law ($a\in\{1.5,2.5\}$) designs. It adds Lévy $\alpha$-stable noise with $\alpha\in\{0.75,1.0,1.5,2.0\}$ as in Median Clipping, in symmetric and skewed versions, over 50 random starts per setting.
On real workloads, we run the ATTACK graph benchmark ($d=13{,}225$) with injected heavy-tailed evaluation noise. We run DeathStarBench SocialNetwork resource allocation, where tail latency is itself heavy-tailed, following CONGO. We also run a sparse version of the Binance Spot 2023 portfolio task, padded with many irrelevant assets.
The decisive checks are three.
The first is a scaling test. On the phase-retrieval objective at $\alpha=1$, does the escape query cost grow with $s\log d$ as $d$ moves from $10^3$ to $10^5$, while dense median clipping grows with $d$?
The second is a symmetry test. Under skewed noise, does the no-offset ablation develop a persistent bias that the offset version lacks?
The third is a pooling test. Does adding pooling reduce the across-start variance of escape time, which is the operational meaning of reduced initialization sensitivity? Does it leave late-phase accuracy unharmed on the power-law variant? If pooling hurts late-phase accuracy there, the pooling radius must shrink as the run proceeds, and we will report that schedule as part of the method.
References
- Gradient Estimation with Simultaneous Perturbation and Compressive Sensing
- Stochastic Zeroth-order Optimization in High Dimensions
- CONGO: Compressive Online Gradient Optimization
- Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization
- Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise
- Robust gradient estimation in the presence of heavy-tailed noise
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
- Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
- Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity
- PhaseMax: Convex Phase Retrieval via Basis Pursuit