Hyperellipsoid Density Sampling: Exploitative Sequences to Accelerate High-Dimensional Optimization
Julian Soltes · 2025
Read Hyperellipsoid Density Sampling: Exploitative Sequences to Accelerate High-Dimensional Optimization by Julian Soltes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07836.txt.
Introduction
Julian Soltes tackles optimization where each added dimension thins out trial points. Uniform quasi-random sequences waste samples in high-dimensional spaces, slowing the search for good designs. Hyperellipsoid Density Sampling instead scatters overlapping ellipsoid clouds through the parameter volume.
Unsupervised learning shapes a non-uniform sequence that exploits interior regions where optima are likelier. Prior knowledge about good regions can guide the clouds when available. Denser sampling where it counts should reach strong solutions with fewer expensive evaluations. Engineering design, tuning, and calibration problems with many knobs stand to gain from smarter point placement.
Catalog record
| CREATOR | Julian Soltes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07836
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hyperellipsoid Density Sampling: Exploitative Sequences to Accelerate High-Dimensional Optimization Julian Soltes Abstract . The curse of dimensionality presents a pervasive challenge in optimization problems, with exponential expansion of the search space rapidly causing traditional algorithms to become inefficient or infeasible. An adaptive sampling strategy is presented to accelerate optimization in this domain as an alternative to uniform quasi-Monte Carlo (QMC) methods. This method, referred to as Hyperellipsoid Density Sampling (HDS), generates its sequences by defining multiple hyperellipsoids throughout the search space. HDS uses three types of unsupervised learning algorithms to circumvent high-dimensional geometric calculations, producing an intelligent, non-uniform sample sequence that exploits statistically promising regions of the parameter space and improves final solution quality in high-dimensional optimization problems. A key feature of the method is optional Gaussian weights, which may be provided to influence the sample distribution towards known locations of interest. This capability makes HDS versatile for applications beyond optimization, providing a focused, denser sample distribution where models need to concentrate their efforts on specific, non-uniform regions of the parameter space. The method was evaluated against Sobol, a standard QMC method, using differential evolution (DE) on the 29 CEC2017 benchmark test functions. The results show statistically significant improvements in solution geometric mean error ( p < 0.05 p<0.05 ), with average performance gains ranging from 3 % 3\% in 30 D 30D to 37 % 37\% in 10 D 10D . This paper demonstrates the efficacy of HDS as a robust alternative to uniform QMC sampling for high-dimensional optimization. 1. Introduction High-dimensional optimization poses a significant challenge due to the curse of dimensionality (Peng et al., 2023). This is increasingly relevant as big data tasks become more common. For problems where the global optimum resides within a localized interior region of the parameter space, uniform quasi-Monte Carlo (QMC) methods often prove inefficient (Chen et al., 2025). By sampling uniformly across the entire data hypercube, these methods may consume valuable computational resources exploring irrelevant regions, which can inhibit the identification of global optimal solutions in vast search spaces. Various approaches have been explored to address this inefficiency, such as modifying traditional optimizers and employing data preprocessing methods (Hinz et al., 2018). This paper presents an alternative: an adaptive sampling strategy informed by the parameter space to intelligently guide the optimizer’s search. The proposed strategy, Hyperellipsoid Density Sampling (HDS), focuses a large initial sample sequence to the target sample size by narrowing the search population to statistically promising regions. This is achieved by defining multiple hyperellipsoids over the parameter space, with their centers determined by MiniBatchKMeans clustering of an initial Sobol QMC sequence. The number of ellipsoids is found using Agglomerative Hierarchical Clustering, and their axis dimensions are calculated via Principal Component Analysis. Samples are generated within unit hyperspheres using the Marsaglia polar method to ensure angular uniformity, and are subsequently transformed to fit the hyperellipsoids. Any out-of-bounds samples are redistributed using geometric void filling. The result is a non-uniform sample sequence more concentrated in areas likely to contain the global optimum. For the differential evolution (DE) trials discussed in this paper, it is hypothesized that HDS as an initial sampling strategy will achieve a statistically significant improvement in final solution fitness for high-dimensional evolutionary optimization when compared to QMC sampling methods. Figure 1. HDS sequence (yellow) and a comparison Sobol sequence (red) for 10,000 samples in 2D. A scatter plot showing the resulting sample distribution for two sampling algorithms: HDS and Sobol. The sequences are 2-D with sample sizes of 10,000. The x- and y- axes represent the two dimensional bounds of [0,1]. 2. Methodology 2.1. Experimental Methods This study evaluates the performance of different initial sampling strategies using differential evolution (DE) as the test optimizer. DE is an effective and widely used algorithm for non-differentiable, non-linear, multi-modal, and high-dimensional problems (Stokes et al., 2020). The trials were configured with Scipy Differential Evolution’s default parameters ( strategy=best1bin , F=(0.5,1) , CR=0.7 ). The experimental trials were run against the 29 CEC2017 benchmark test functions, each possessing distinct characteristics to challenge optimizers and are scalable to 10, 30, 50, and 100 dimensions ( D\in\{10,30,50,100\} ). As such, these are the four dimensionalities tested, with bounds of [-100,100]. 50 trials were conducted for two sets of sample sizes, as well as for each combination of test function and dimension, totaling 11,400 DE runs. The sample sizes tested are 64 and 1000; the lower value is chosen for maximal constraints while providing Sobol its power-of-2 uniformity (Joe & Kuo, 2008). The higher value is chosen to represent a more typical problem. The maximum number of iterations n_{iter} for the optimization is fixed at 100; this low number was chosen to highlight the practical benefits of HDS with a limited computational budget. The random seed is set to the experimental trial number for both sampling methods, to ensure a fair independent comparison. The comparison metric used for the analysis is the final solution fitness values for HDS compared to Sobol. Sobol was chosen as the comparison metric due to its high uniformity and low discrepancy in high dimensions (Atanassov & Ivanovska, 2022), as well as its use within the HDS algorithm. Latin Hypercube was considered as an alternative, but does not ensure the same low discrepancy as Sobol in high dimensions (Wang & Sloan, 2007). To ensure a fair comparison, the geometric mean is used to calculate the average improvement factors for each dimension across all test functions. The optimization run times between the two sampling methods are also compared to assess the impact on overall processing time. Additionally, the discrepancies of the resulting HDS sequences are compared against Sobol using L2-Star and Centered L2 metrics. 2.2. Hyperellipsoid Density Sampling The Hyperellipsoid Density Sampling (HDS) method generates N total samples \mathbf{x}\in\mathbb{R}^{D} within a D -dimensional search space (defined by the bounds B ), using a data-driven approach to focus sample density. The resulting sample distribution is highly non-uniform, increasingly resembling a normal distribution as dimensions scale higher. This is an expected consequence of the algorithm accounting for the curse of dimensionality. 2.2.1. Define Normalized Space The D-dimensional search bounds, \mathbf{B} , are normalized to the unit hypercube [0,1]^{D} to simplify clustering and Principal Component Analysis (PCA). 2.2.2. Generate Initial QMC Sequence A large initial set of N_{\text{init}} samples is generated, where N_{\text{init}} is set to the smallest power of 2 greater than or equal to 200\cdot D , ensuring sufficient coverage that scales with dimensionality as N_{\text{init}}=2^{\lceil\log_{2}(200\cdot D)\rceil} . This value is capped at 2^{15} by default for efficiency. These values balance computational efficiency with spatial discrepancy for high sample sizes and dimensions, as well as ensuring power-of-2 QMC sample sizes for maximum uniformity. The initial QMC samples are generated using a Sobol sequence within the normalized unit hypercube. This initial set serves as the basis for determining the geometry of the search space. 2.2.3. Gaussian Weights (Optional) If prior information (such as target distribution or optimal solution region) is known, Gaussian weights may be applied to the initial QMC samples to influence their distributions. As a result, the final sample locations are shifted towards the desired region. An example of an HDS sample sequence with weights applied is shown below. Figure