Gradient Guided Parameter Space Sampling for Knowledge Discovery with Limited Budgets

Many industrial and scientific tasks entail recovery of an unknown function through an ensemble of experiments, each corresponding to a different scenario. This task can generally be abstracted as the task of evaluating an expensive, deterministic black-box function over combinatorial parameter spaces that are much larger than the available evaluation budget-the sampling capacity becoming exponentially sparser with the number of dimensions of the parameter space. In this paper, we note that existing sampling strategies can potentially waste observations at non-interesting regions of the parameter space or, alternatively, may over-focus on regions that are close to a singular 'optimal' point. In contrast, we propose a gradient-guided sampling strategy that aims to obtain samples at the regions of the space where the values of the function are subject to major changes. We present a gradient guided sampler (G2S) that transforms the sampling challenge into a sequence of tractable subspace searches. The proposed method begins with a space-filling design, then iteratively 1) decomposes the full space into low dimensional slices, 2) adaptively selects among three strategies (locally estimated gradient magnitude, reconstruction error, or the estimated gradient of that error) and 3) draws new candidates through a custom kernel density estimation sampler. A multi-armed bandit controller allocates budget across the three strategies, continuously trading off exploration and exploitation, without manual tuning. Experimental results on several benchmarks show that the proposed sampler reduces gradient-weighted prediction error relative to strategies like Latin hypercube sampling as well as state-of-the-art Bayesian optimization techniques.