We propose a novel algorithm that extends themethods of ball smoothing and Gaussian smooth-ing for noisy derivative-free optimization by ac-counting for the heterogeneous curvature of theobjective function. The algorithm dynamicallyadapts the shape of the smoothing kernel to ap-proximate the Hessian of the objective functionaround a local optimum. This approach sig-nificantly reduces the error in estimating thegradient from noisy evaluations through sam-pling. We demonstrate the efficacy of our methodthrough numerical experiments on artificial prob-lems. Additionally, we show improved perfor-mance when tuning NP-hard combinatorial op-timization solvers compared to existing state-of-the-art heuristic derivative-free and Bayesian op-timization methods.