Hyperellipsoid Density Sampling: Exploitative Sequences to Accelerate High-Dimensional Optimization

Technical Summary: Hyperellipsoid Density Sampling (HDS)

Problem Statement
The paper addresses the "curse of dimensionality," a persistent challenge in modern optimization where expanding the search space into higher dimensions exponentially increases the difficulty of finding optimal solutions. Traditional uniform sampling methods, such as quasi-Monte Carlo (QMC), ensure full coverage of the search space to maximize stratification and minimize discrepancy. However, in high-dimensional problems where the global optimum resides in an interior region, uniform sampling becomes inefficient. It consumes computational resources exploring irrelevant regions of the data hypercube, thereby inhibiting the identification of global optima. The authors propose an alternative strategy: exploitative initial sampling that intelligently guides the optimizer’s search toward statistically promising regions.

Methodology
The authors introduce Hyperellipsoid Density Sampling (HDS), a method that generates non-uniform sample sequences by defining multiple hyperellipsoids throughout the search space. HDS utilizes three unsupervised learning algorithms to bypass complex high-dimensional geometric calculations:

1. Initialization and Clustering: The process begins by normalizing the $D$-dimensional search bounds to a unit hypercube. A large initial set of samples ($N_{init}$) is generated using a Sobol QMC sequence. These samples are clustered using MiniBatch-KMeans to reduce the data to a computationally efficient set of centroids.
2. Ellipsoid Definition: Agglomerative Hierarchical Clustering (AHC) is performed on the centroids to determine the optimal number of clusters ($K$), which defines the number of hyperellipsoids. The geometry of each hyperellipsoid is determined via Principal Component Analysis (PCA) on the samples within each cluster. PCA defines the orientation of the ellipsoid axes, while the variance along these components determines the semi-axis lengths.
3. Sample Generation: Samples are generated within unit hyperspheres using the Marsaglia polar method to ensure angular uniformity. A radial scaling factor, derived from a $\chi^2$ critical value and an empirically tuned dimension-variant constant, is applied to control the spread. A 1D Sobol sequence is used to scale the radial distance, ensuring uniform distribution within the hypervolume.
4. Transformation and Void Filling: The scaled unit sphere samples are transformed into the final hyperellipsoids via matrix multiplication (scaling and rotation) and shifted to the cluster centroids. Samples falling outside the normalized bounds are rejected. If the target sample count is not met, an adaptive void-filling strategy using k-nearest neighbor (KNN) distances identifies sparse regions, where new points are generated using a truncated normal distribution.
5. Optional Weighting: The method allows for the application of Gaussian weights to shift sample locations toward specific regions of interest if prior information is available.

Experimental Setup
HDS was evaluated against the Sobol QMC method using Differential Evolution (DE) as the optimizer. The experiments utilized the 29 CEC2017 benchmark test functions, scalable to 10, 30, 50, and 100 dimensions ($D \in \{10, 30, 50, 100\}$). Two sample sizes were tested: $N=64$ and $N=1000$. Each configuration underwent 50 independent trials, totaling 11,400 DE runs. The maximum number of iterations was fixed at 100 to highlight benefits under limited computational budgets. Performance was measured by final solution fitness (geometric mean error) and computational run time.

Key Results

• Optimization Fitness: HDS consistently outperformed Sobol QMC across all tested dimensions. For $N=1000$, HDS achieved an overall geometric mean improvement factor of 1.15x (a 15% average improvement in final fitness). Performance gains ranged from 37% in 10D to 11% in 100D. Statistical significance ($p < 0.05$) was observed in most cases, particularly in higher dimensions (50D and 100D). In the $N=64$ trials, improvements were more nuanced, with statistical significance lacking in 10D and 100D.
• Computational Efficiency: HDS sample generation is slower than deterministic QMC methods due to the overhead of machine learning model fits. For $N=1000$, HDS trials were 4.90% slower overall (run time ratio of 0.951). However, the authors note that for higher iteration counts ($n_{iter} > 100$), the sample generation time constitutes a smaller fraction of the total optimization time.
• Discrepancy: HDS inherently sacrifices global uniformity for local density. L2-Star discrepancy values were higher for HDS than Sobol, reflecting less uniform global coverage. However, Centered L2 discrepancy was much lower for HDS, indicating tighter clustering and high local uniformity.

Significance and Contributions
The paper claims HDS as a robust and effective initial sampling strategy for high-dimensional optimization. Its primary contribution is the demonstration that a non-uniform, exploitative sampling approach can significantly improve solution quality compared to uniform QMC methods by focusing computational resources on regions likely to contain global optima. The authors highlight the versatility of HDS, noting that its ability to influence distribution via Gaussian weights extends its utility beyond global optimization to applications such as complex data modeling, experimental design, sensitivity analysis, and the training of deep learning or reinforcement learning models. The method is implemented in the open-source hdim_opt Python package, designed for seamless integration with existing workflows.