Hilbert curves for efficient exploratory landscape analysis neighbourhood sampling

• URL: http://arxiv.org/abs/2408.00526v1
• Date: Thu, 1 Aug 2024 12:57:35 GMT
• Title: Hilbert curves for efficient exploratory landscape analysis neighbourhood sampling
• Abstract summary: Hilbert space-filling curves are proposed as a method to efficiently obtain high-quality ordered samples. We study the effectiveness of Hilbert curves as samplers, and discover that they are capable of extracting salient features at a fraction of the computational cost.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Landscape analysis aims to characterise optimisation problems based on their objective (or fitness) function landscape properties. The problem search space is typically sampled, and various landscape features are estimated based on the samples. One particularly salient set of features is information content, which requires the samples to be sequences of neighbouring solutions, such that the local relationships between consecutive sample points are preserved. Generating such spatially correlated samples that also provide good search space coverage is challenging. It is therefore common to first obtain an unordered sample with good search space coverage, and then apply an ordering algorithm such as the nearest neighbour to minimise the distance between consecutive points in the sample. However, the nearest neighbour algorithm becomes computationally prohibitive in higher dimensions, thus there is a need for more efficient alternatives. In this study, Hilbert space-filling curves are proposed as a method to efficiently obtain high-quality ordered samples. Hilbert curves are a special case of fractal curves, and guarantee uniform coverage of a bounded search space while providing a spatially correlated sample. We study the effectiveness of Hilbert curves as samplers, and discover that they are capable of extracting salient features at a fraction of the computational cost compared to Latin hypercube sampling with post-factum ordering. Further, we investigate the use of Hilbert curves as an ordering strategy, and find that they order the sample significantly faster than the nearest neighbour ordering, without sacrificing the saliency of the extracted features.

Related papers

• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  We show that high-accuracy guarantees for log-concave sampling are achievable using iteration gradients with subexponential tails.<n>Our framework also provides similar high accuracy guarantees under zeroth order (value) queries.
  arXiv  Detail & Related papers  (2026-02-15T23:19:07Z)
• Coreset selection for the Sinkhorn divergence and generic smooth divergences [0.8594140167290099]
  CO2 is an efficient algorithm to produce convexly-weighted coresets with respect to generic smooth divergences. We show a local equivalence between sufficiently regular losses and their second order approximations, reducing the coreset selection problem to maximum mean discrepancy minimization. We apply CO2 to the Sinkhorn divergence, providing a novel sampling procedure that requires logarithmically many data points to match the approximation guarantees of random sampling.
  arXiv  Detail & Related papers  (2025-04-28T18:54:53Z)
• Optimal sampling for least-squares approximation [0.8702432681310399]
  We introduce the Christoffel function as a key quantity in the analysis of (weighted) least-squares approximation from random samples. We show how it can be used to construct sampling strategies that possess near-optimal sample complexity.
  arXiv  Detail & Related papers  (2024-09-04T00:06:23Z)
• Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency [18.17090625880964]
  We study the methodology of exploring the domain using random samples drawn from a distribution. We show that this random exploration approach achieves the optimal error rates.
  arXiv  Detail & Related papers  (2023-10-23T20:30:44Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
  We introduce a suite of new particle-based algorithms for sampling in constrained domains which are entirely learning rate free. We demonstrate the performance of our algorithms on a range of numerical examples, including sampling from targets on the simplex.
  arXiv  Detail & Related papers  (2023-05-24T09:31:18Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• Mean shift cluster recognition method implementation in the nested sampling algorithm [0.0]
  Nested sampling is an efficient algorithm for the calculation of the Bayesian evidence and posterior parameter probability distributions. Here we present a new solution based on the mean shift cluster recognition method implemented in a random walk search algorithm.
  arXiv  Detail & Related papers  (2020-01-31T15:04:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.