Robust Residuals as a Search-Radius Signal for Black-Box Metric Optimization

Many deployment metrics are step functions of a model's parameters: F1, precision at a recall break-even point, or a perceptual speech score. Nudging the weights slightly usually leaves the score unchanged, and the metric has no useful gradient. A standard workaround is to estimate a gradient from outside. You evaluate the metric at randomly perturbed copies of the model, then fit a linear model that relates perturbation directions to changes in score. This procedure has two separate weaknesses. Metric evaluations are often noisy or corrupted, so robust regression is needed. And the size of the perturbation has to be chosen well. If it is too small, every probe lands on the same flat step and the estimate is zero. If it is too large, the linear fit is meaningless.

This note proposes that one robust fit can address both weaknesses. A robust regression already separates "inlier" probes from "outlier" probes. The size of the leftover error on the inliers is a nearly free measurement of how well a straight line explains the metric at the current perturbation size. If the inlier error is tiny compared with the signal, the probes are too close together, or the landscape is flat, so the radius should grow. If it is large, the landscape is curved or jagged at that scale, so the radius should shrink. The outlier fraction, measured separately, tells us whether the evaluations themselves are being corrupted. We would build this controller on a cheap robust estimator, adaptive hard thresholding, instead of linear programming. This keeps the cost of robustness close to that of ordinary least squares.

Core Claim

In finite-difference gradient estimation, the robust estimator's by-products are the right control signal for adaptive exploration. Those by-products are the inlier residual scale and the flagged outlier fraction. A search radius driven by these two quantities should match or beat hand-tuned and self-adaptive step-size rules on corrupted black-box metrics, at a small fraction of the compute that linear-programming-based robust estimators need.

Concretely, at iterate $\theta$ with radius $\sigma$, we draw directions $\epsilon_i$ and record $y_i = f(\theta+\sigma\epsilon_i) - f(\theta)$. We then fit

$$y_i = \sigma\, g^\top \epsilon_i + r_i + c_i,$$

where $g$ is the gradient estimate, $r_i$ is the nonlinearity error at scale $\sigma$ (curvature or a step discontinuity), and $c_i$ is a sparse corruption term, nonzero only on corrupted evaluations. The robust fit returns $g$ together with an inlier set $S$. From these we form the linearity ratio

$$\kappa = \frac{\mathrm{median}_{i\in S}\,|y_i - \sigma g^\top\epsilon_i|}{\mathrm{median}_{i\in S}\,|\sigma g^\top \epsilon_i|}.$$

The controller multiplies $\sigma$ up when $\kappa$ sits below a lower band and down when it sits above an upper band. This makes the schedule reversible, unlike monotone decay. The flagged fraction $|S^c|/n$ sets the next iteration's probe count $n$, so that the corruption level stays safely below the estimator's breakdown point. A zero-variance batch, where all $y_i$ equal zero, is treated as maximal flatness and triggers expansion.

Relation to Prior Work

The closest work is When random search is not enough (RBO). RBO recasts derivative-free gradient estimation as regression and replaces least squares with $L_1$ linear-programming decoding, which provably recovers gradients under roughly 23.9% arbitrary corruption. RBO supplies our problem formulation. But it perturbs with a fixed-scale Gaussian, and it discards the residual structure that its decoder computes. We differ in two ways. We feed those residuals back into the radius, and we swap the linear-programming decoder for a near-linear-time estimator.

That estimator comes from Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression (AdaCRR). AdaCRR needs only $\mathcal{O}(\log n)$ least-squares passes, stays consistent when most responses are corrupted, and is reported up to 100x faster than Huber regression. It supplies the method, and its inlier set is exactly the by-product our controller needs. AdaCRR's randomized threshold is a fixed exploratory "jiggle". Here, exploration moves to the outer loop, where it responds to the landscape.

Two lines of work motivate the gap from the non-differentiable side. Optimizing Black-box Metrics with Adaptive Surrogates probes a monotone link between a few convex surrogate losses and the target metric using finite differences with fixed perturbation bounds. It assumes clean validation evaluations. That low-dimensional probe is an ideal place for our estimator, because regression in a $K$-dimensional surrogate space is cheap. EvoGrad weights local gradient samples by CMA-ES's search distribution, a population-based method that adapts its own sampling distribution. EvoGrad has no outlier handling, so heavy-tailed spikes corrupt both its gradient and its curvature estimates. It is the strongest adaptive-but-non-robust competitor.

On PPO's Heavy-tailed Gradients plays a constraining role. It shows that gradient heavy tails drive instability and that block geometric medians can replace clipping. It also documents that robust aggregation carries a real training cost, which is why we reject geometric medians in the inner loop.

The swarm literature is the conceptual precedent for reversible, feedback-driven schedules. Examples include cosine control factors in the barnacle-mating optimizer work and fitness-driven weighting in IGWO. Those feedback signals are heuristic, and IGWO is quadratic in population size. Our signal has a statistical meaning, since $\kappa$ directly measures whether the linear model holds at the current scale.

Learned-surrogate methods such as MetricGAN+ solve a different problem, dense gradients for generators. They are out of scope except as a contrast in how exploration is handled.

Research Program

The first component is the estimator-controller pair. It consists of AdaCRR run on the probe regression, the $\kappa$-band radius rule, and the outlier-fraction probe-count rule. We would also reuse probes across iterations when the radius changes little, following RBO's sample reuse.

The analysis would test one falsifiable prediction. For a piecewise-constant metric with step width $h$, the chosen $\sigma$ should settle near a constant multiple of $h$, because $\kappa$ is small only once probes straddle several steps and remains small until curvature dominates. We would verify this on synthetic step functions with a known $h$.

The second component is a cost accounting. We would report the robustness overhead ratio, meaning the wall-clock time of the robust fit divided by the time of an ordinary least-squares fit on the same probes. We would report it as dimension grows, for AdaCRR and for linear-programming decoding. The goal is to show where RBO's decoder stops being practical.

Baselines

The naive reference is vanilla evolution-strategies gradient estimation. It uses least squares on the probes, a fixed radius tuned by grid search, and no outlier handling. It shows how much damage corruption does.

The strongest robust competitor is RBO with linear-programming decoding at its best fixed radius, per When random search is not enough. It is run on the same MuJoCo tasks with 20% of rewards corrupted, the regime RBO reports. The file gives no numeric returns for RBO, and I found no reported result on Lacuna for RBO returns. We will therefore rerun it under matched evaluation budgets and grid-search its radius with the same number of tuning trials our controller gets for its two band thresholds.

The strongest adaptive competitor is EvoGrad2. On COCO it is reported to solve 94.9% of functions, against 82.1% for explicit gradient learning and 61.2% for CMA-ES, per EvoGrad. We will run the noisy COCO variants with injected heavy-tailed corruption. On the metric side, Surrogate Projected Gradient Descent reports a break-even point of 0.480 on KDD Cup 2008, against 0.441 for the prior surrogate baseline, per Optimizing Black-box Metrics with Adaptive Surrogates. We will substitute our estimator for its fixed-bound finite-difference probe, keeping everything else identical.

Beating the baselines means the following. On MuJoCo, we need higher final return than tuned RBO at equal evaluations. On noisy COCO, we need a higher solved fraction than EvoGrad2. On KDD Cup, we need at least 0.480 with clean labels, and a clear margin once validation labels are corrupted, all at lower wall-clock than linear-programming decoding.

Two ablations isolate the key ingredient. The first keeps AdaCRR but fixes the radius. The second keeps the $\kappa$ controller but computes $\kappa$ from least-squares residuals. Without the robust inlier set, corruption should inflate $\kappa$ and wrongly shrink the radius.

Why not just…?

Why not just use rank-based fitness shaping, as in CMA-ES and OpenAI-style evolution strategies? This is the most serious threat. Ranks bound the influence of any single corrupted evaluation, and they cost almost nothing. However, a corrupted probe that is pushed to the top rank still contributes a full-weight direction. Its bias therefore grows linearly with the corruption fraction instead of vanishing. Ranks also give no linearity signal for setting the radius. We will include rank-shaped evolution strategies with the same step-size adaptation as a baseline. If it matches us at 20% corruption, the contribution narrows to the radius controller. In that case we would report the result honestly and test whether $\kappa$ computed on ranks recovers most of the gain.

Why not just add CMA-ES's own step-size adaptation (cumulative path length, or the 1/5 success rule) to RBO? Both rules react to success rates or path lengths, and both of those are computed from evaluations that corruption distorts. On flat plateaus of step metrics, success is zero regardless of the radius. The RBO-plus-adaptation combination is a baseline. The expected decisive difference is on KDD Cup and on synthetic step functions, where our controller expands on flatness and success-based rules stall.

Why not just use Huber regression or clip the rewards? AdaCRR reports Huber regression up to 100x slower and inconsistent under Cauchy noise. Separately, Choromanski et al. report that clipping-based PPO and TRPO collapse under 20% reward corruption. We still include a Huber-plus-$\kappa$ variant, to check whether the controller rather than the estimator carries the gain.

Proposed Experiments

The decisive checks come in three parts. First, on synthetic step functions of known width $h$, the adapted $\sigma$ should track $h$. A version driven by least-squares residuals should fail once corruption is added. Second, on MuJoCo with 20% corrupted rewards and on noisy COCO, we would show learning curves against evaluation count and wall-clock. We would include the robustness overhead ratio as dimension rises, and carry it toward the more than 30,000-dimensional ImageNet attack setting used by EvoGrad. Third, on KDD Cup 2008, we would measure break-even point and G-mean with 0%, 10%, and 20% of validation labels flipped adversarially.

The whole idea is refuted if the fixed-radius AdaCRR ablation matches the full method. In that case exploration adaptation adds nothing beyond robustness. It is also refuted if rank-shaped evolution strategies match it everywhere, in which case the robust regression is unnecessary.