Research map / Optimization / Optimizers
Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Dynamic Anisotropic Smoothing (DAS), a derivative-free method that adapts a Gaussian smoothing kernel's shape toward the objective's Hessian, and applies it to tuning noisy combinatorial-optimization (SAT/Ising) heuristic solvers.
Problem
Derivative-free optimization of expensive, noisy objectives whose curvature is heterogeneous (anisotropic), such as hyperparameter and heuristic-solver parameter tuning where function evaluations are random and costly.
Approach
Extends ball and Gaussian smoothing by jointly adapting the kernel's location and full covariance (matrix L) via SDE-based gradient dynamics, so the smoothing window converges toward the local Hessian and reduces gradient-estimation variance.
Key results
- On the 4-dimensional modified Rosenbrock function with beta=0.5 at n_s=10^5, DAS reaches mean fitness 0.981 versus 0.586 for BOHB, 0.304 for SPSA, and 0.280 for Gasnikov ball smoothing.
- DAS finds the best parameters for tuning a differential 3-SAT solver (N=150, alpha=4.0), outperforming the compared tuners, though BOHB's search box excluded the optimum found by DAS.
- The error of DAS asymptotically scales as O(D/n_s^{1/2}) in numerical experiments with kappa=1.0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DAS instead of Gasnikov fixed-window smoothing | Derivative-free optimization · Modified Rosenbrock D=4, β=0.5, n_s=10^5 | mean fitness: 0.280 -> 0.981 | Helped |
| Use DAS instead of SPSA | Derivative-free optimization · Modified Rosenbrock D=4, β=0.5, n_s=10^5 | mean fitness: 0.304 -> 0.981 | Helped |
| Use DAS instead of BOHB | Derivative-free optimization · Modified Rosenbrock D=4, β=0.5, n_s=10^5 | mean fitness: 0.586 -> 0.981 | Helped |
| Use DAS rather than BOHB | Modified Rosenbrock D=2 · Modified Rosenbrock D=2 | fitness | Hurt |
| Use DAS rather than BOHB | Modified Rosenbrock D=4 · Modified Rosenbrock D=4 | fitness | Helped |
| Use DAS rather than BOHB | Derivative-free optimization · Modified Rosenbrock D=8, with enough samples | fitness | Helped |
| Replace a fixed sampling window with dynamic window size (ablation) | Ball smoothing · Asymmetric artificial fitness function | fitness | Helped |
| Use a dynamic anisotropic window instead of a circular window (ablation) | Derivative-free optimization · Heterogeneous-curvature function f(x,y)=e^{-100x^2-y^2} | fitness | Helped |
| Set the batch-size exponent κ to 1.0 rather than 0.5 (ablation) | DAS · Asymmetric artificial fitness function | normalized error convergence: O(D/n_s^{1/2}) | Helped |
Surprising findings
- BOHB, the strongest baseline in 2D, is outperformed in higher dimensions where gradient-based methods do better.
- The optimal parameters found by DAS lie outside the [0,1]^4 search box given to BOHB, so the comparison is partly constrained by search bounds.
Limitations
- Restricted to continuous search spaces, as noted in the paper's comparison table.
- Derivation of the optimal kernel shape relies on approximations near the maximum and on a constant-norm assumption; the Gaussian fixed-point result is proven only for Gaussian objectives.
- Experiments use few runs (5) and artificial functions plus a single solver family, limiting generality.
Experimental setup
Datasets: modified Rosenbrock function random 3-SAT instances
Benchmarks: modified Rosenbrock function 3-SAT solver parameter tuning Ising solver parameter tuning
Metrics: fitness success probability gradient estimation error
Baselines: BOHB SPSA Gasnikov ball smoothing Optuna HyperOpt
Builds on: ball smoothing Gaussian smoothing BOHB
Closest papers by meaning
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.87)
- Automatic Differentiation of Optimization Algorithms with Time-Varying Updates (ICML 2025 · similarity 0.86)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.86)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.86)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.