Many optimization problems give you only function values and no gradients. Examples are tuning a solver's continuous settings, training a policy from rewards, or attacking a model you can only query. The standard trick is Gaussian smoothing: evaluate the function at randomly jittered points and turn the differences into a gradient estimate. Its weak spot is one number, the jitter size, also called the smoothing radius. Too small and measurement noise swamps the estimate. Too large and the estimate is biased by curvature. Worse, the right size usually differs by orders of magnitude from one coordinate to another.
We propose an optimizer that sets a separate jitter size for every coordinate. It does this from two quantities it measures for free from queries it already makes: the local noise level and the curvature along that coordinate. A distance-based adaptive stepsize removes the remaining step-size knob. The method uses memory linear in the dimension. The claim we test is not mainly that it reaches lower loss. It is that the optimizer's performance becomes nearly flat across its own remaining settings on non-convex problems with hundreds to hundreds of thousands of coordinates. We measure that robustness directly with the sensitivity and tunability games from the hyperparameter-importance literature.
Core Claim
Two lines of work each solve half of the problem. Dynamic Anisotropic Smoothing (DAS) proves that the error of the gradient estimate is minimized when the jitter distribution is an ellipse aligned with the local curvature, with radii shrinking along steep directions. It learns that ellipse with coupled stochastic differential equations over a full $d\times d$ matrix, so its experiments stop at eight dimensions. It also adds its own integration and damping settings. POEM removes the stepsize and a scalar radius as knobs and shows flat performance across orders of magnitude of its initial-scale parameter on LIBSVM. However, its theory is convex-only and its jitter is isotropic.
Generalizing Gaussian Smoothing for Random Search derives an optimal radius shrinkage with dimension, but only as one shared scale. The "smoothing anomaly" in Coherent Coordinate Descent (CoCD) shows that on rugged losses a larger finite-difference interval acts as a low-pass filter and stabilizes training. It applies one uniform interval to all coordinates.
Our claim is that the radius of each coordinate can be set by a classical bias–noise balance computed online, with no hyperparameter. That rule explains the smoothing anomaly as a special case, since ruggedness registers as high measured noise and pushes the radius up. Combined with a distance-over-gradients stepsize, it yields an optimizer whose sensitivity to its residual settings is measurably lower than that of isotropic or step-preconditioned alternatives.
Mechanism
We perturb with $u \sim \mathcal{N}(0, \mathrm{diag}(\mu_1^2,\dots,\mu_d^2))$ and use the symmetric estimator $\hat g_i = \frac{f(x+u)-f(x-u)}{2}\,u_i/\mu_i^2$. The same function values also give a diagonal curvature estimate through the second-order Stein identity listed in the research file. In our notation it is
$$\hat h_i = \frac{f(x+u)+f(x-u)-2f(x)}{2\mu_i^2}\left(\frac{u_i^2}{\mu_i^2}-1\right),$$
where $\hat h_i$ estimates the $i$-th diagonal Hessian entry. This costs one extra query at $x$, which we also repeat occasionally to estimate the evaluation noise standard deviation $\hat\sigma$. Both $\hat h_i$ and $\hat\sigma$ are averaged with exponential moving averages.
The per-coordinate radius then follows from minimizing the sum of squared bias $(\mu_i |h_i|)^2$ and noise variance $\sigma^2/\mu_i^2$ along that coordinate:
$$\mu_i^{\star} = c\,\sqrt{\hat\sigma / \max(|\hat h_i|, h_{\min})}.$$
Here $c$ is a constant fixed once from the scalar optimum. The floor $h_{\min}$ handles flat and negative-curvature directions in non-convex problems, and we deliberately study it as a residual knob. This is the diagonal, $O(d)$-memory analogue of DAS's optimal ellipse. Unlike DAS, it is computed in closed form rather than integrated as dynamics.
The stepsize follows POEM's distance-over-gradients rule, extended heuristically to the non-convex case. POEM's impossibility result for unbounded domains constrains us here. We therefore work on bounded boxes and report the box size as one of the residual settings whose sensitivity we measure. We do not claim non-convex convergence theory beyond what the bias–noise balance gives locally.
Research Program
The work has three parts. First, we build the optimizer and verify on synthetic problems that $\mu_i^\star$ tracks the true per-coordinate optimum. We use quadratics and Rosenbrock variants with known, deliberately rescaled curvature (factors from $10^{-3}$ to $10^3$) and controlled additive noise, at $d$ from 4 to $10^5$.
Second, we measure tuning sensitivity as a first-class outcome. For every optimizer, we define its residual settings: initial scale, $h_{\min}$, averaging rates, box size, and number of directions per step. We sample them over log-ranges spanning two orders of magnitude each. Following HyperSHAP, we then compute the sensitivity game, which is the variance of final performance over the setting space. We also compute the tunability game, which is the gain of the best setting over the default. HyperSHAP's argument that these are different quantities matters here. An optimizer can be insensitive because it is uniformly mediocre, so we report both, and "robust" means low sensitivity with low tunability at a competitive default.
Third, we test the smoothing-anomaly explanation. We check whether the radius chosen automatically on CoCD's neural-network setting lands in the large-interval regime CoCD found beneficial. We also check whether coordinates with high measured ruggedness receive large radii.
Baselines
The naive reference point is isotropic two-point Gaussian smoothing with a fixed scalar radius and fixed stepsize at a textbook default, with no tuning. This shows how bad untuned behaviour is.
The strongest isotropic competitor is the same method with radius and stepsize grid-searched on a log grid. We charge the grid's queries to its budget, and also report it with tuning given for free as an upper bound. On any comparison, beating the free-tuning version at equal optimization queries is the bar for "better". Beating the charged version is the bar for "cheaper to use".
POEM is the strongest parameter-free competitor. We run it with its published rules and its own initial-scale parameter swept the same way. For POEM's LIBSVM experiments the file gives only qualitative statements ("matches well-tuned" baselines, flat across parameter range), so for LIBSVM there is no reported result found on Lacuna for a numeric POEM value. We reproduce it ourselves. Beating POEM on convex LIBSVM is not required; matching it there while staying flat on non-convex tasks where it degrades is the success criterion.
DAS is the strongest anisotropic method and defines the low-dimensional ceiling. On the 4-dimensional modified Rosenbrock it reports mean fitness 0.981, against 0.304 for SPSA and 0.586 for BOHB (DAS). We expect to come within a few hundredths of 0.981 at equal queries. A diagonal method cannot capture rotated curvature, so we also run a rotated variant where DAS should win. Reporting that loss honestly bounds the claim.
At high dimension, CoCD is the strongest lightweight competitor. It reports 95.48% MNIST accuracy versus 27.03% for block cyclic coordinate descent at the same query budget (CoCD). We match its model, query budget and wall-clock accounting. Beating it means equal or higher accuracy with lower sensitivity to its interval and decay settings versus ours to ours. GS-shrinkage and Bernoulli shrinkage from Generalizing Gaussian Smoothing serve as the dimension-aware isotropic baselines on MuJoCo Ant. There the file states they beat all baselines "by a large margin" but gives no reward figure, so there is no reported result found on Lacuna for Ant returns.
Separable CMA-ES, which adapts a diagonal search distribution by ranking, is the obvious external competitor. It is not in the file and has no reported result found on Lacuna on these benchmarks, but we include it at matched queries.
The key ablations isolate the ingredient. The first uses the same diagonal curvature estimate only to precondition the step while keeping isotropic jitter. The second uses it only to shape the jitter with a plain stepsize. The third uses per-coordinate radii from a one-time pre-run calibration that is then frozen.
Why not just…?
Why not just precondition the step, Adam-style, and leave the jitter isotropic? This is the most serious threat, because diagonal step scaling is cheap and familiar. DAS's analysis says the estimator's error itself depends on the jitter shape: with isotropic jitter, flat coordinates are buried in noise before any step scaling can help. Rescaling the step only amplifies that noise. The first ablation settles it. If step-only preconditioning matches the full method in both loss and sensitivity, the jitter-shaping claim fails and we would report that.
Why not just normalize each coordinate once before optimizing? One-time rescaling fixes static unit mismatches, and on problems with constant curvature it may suffice. The third ablation is exactly this. On Rosenbrock-type valleys, where curvature along a coordinate changes along the trajectory, and on neural-network training, where it drifts during training, we expect frozen radii to lose. If they do not, the online part is unnecessary and the contribution shrinks to a calibration recipe.
Why not just grid-search one isotropic radius? With enough budget a tuned scalar can be strong. POEM's experiments show tuned theoretical baselines work only in a narrow window, and DAS shows one scalar cannot serve coordinates whose sensitivities differ. Our charged-versus-free tuning comparison quantifies how much of the grid's advantage is paid for in hidden queries.
Why not just use Bayesian optimization? It is excellent in very low dimension. However, DAS reports it struggling by eight dimensions and confined to its initial box on SAT tuning, and its surrogate cost grows cubically with evaluations. We include it only on the low-dimensional tasks and the continuous part of the JAHS-Bench-201 search space (JAHS-Bench-201).
Proposed Experiments
The low-dimensional sanity check is the 4-dimensional modified Rosenbrock from DAS, plus its rotated and coordinate-rescaled variants. The scaling study uses rescaled noisy Rosenbrock and quadratics at $d = 10^2$ to $10^5$, where the true optimal radii are known. Here the primary metric is the correlation between $\mu_i^\star$ and the true optimum, alongside final loss.
Convex parity uses LIBSVM a9a, w8a and mushrooms against POEM. The non-convex, high-dimensional tests are zeroth-order MNIST training (CoCD's setting), ResNet-20 on CIFAR-10 at about 270,000 parameters, and MuJoCo Ant against the shrinkage methods.
On every task, the headline metric is a pair. The first element is final performance at the default settings. The second is the HyperSHAP sensitivity and tunability values over each optimizer's residual-setting space, computed from 64 or more sampled configurations and 5 seeds each.
The decisive checks are three. First, the full method should beat step-only preconditioning in sensitivity on the rescaled problems; if it does not, the core claim fails. Second, on MNIST its sensitivity should be lower than CoCD's while accuracy stays within about a point of 95.48%. Third, its automatically chosen radii should fall in CoCD's large-interval regime exactly on the coordinates where measured noise is high. That would give one bias–noise rule that covers both the classical "shrink the radius" advice and the observed benefit of large radii.
References
- Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization
- A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
- Generalizing Gaussian Smoothing for Random Search
- Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization
- HyperSHAP: Shapley Values and Interactions for Explaining Hyperparameter Optimization
- JAHS-Bench-201: A Foundation For Research On Joint Architecture And Hyperparameter Search