Adaptive Linear Embedding for Nonstationary High-Dimensional Optimization
Yuejiang Wen, Paul D. Franzon · 2025
Read Adaptive Linear Embedding for Nonstationary High-Dimensional Optimization by Yuejiang Wen, Paul D. Franzon (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-2505-11281.txt.
Introduction
Wen and Franzon present a method, published in 2025, for optimizing designs with very many variables when the goal itself shifts over time. A popular strategy projects the big problem into a small random subspace and searches there. That works badly when one fixed subspace must serve a moving target. Different corners of the problem favor different subspaces. The authors let the search keep several projections alive at once.
A switch variable picks which projection is active, and a statistical surrogate models the switch together with the design. The optimizer thus learns which local view of the problem pays off where. Tests target high-dimensional problems whose best answer drifts. The method adapts its embedding instead of assuming one global simplification. It aims at engineering tuning tasks where the objective will not sit still.
Catalog record
| CREATOR | Yuejiang Wen, Paul D. Franzon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11281
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Linear Embedding for Nonstationary High-Dimensional Optimization Yuejiang Wen, Paul D. Franzon Abstract BO ( BO ) in high-dimensional spaces remains fundamentally limited by the curse of dimensionality and the rigidity of global low-dimensional assumptions. While REMBO ( REMBO ) mitigates this via linear projections into low-dimensional subspaces, it typically assumes a single global embedding and a stationary objective. In this work, we introduce Self-Adaptive cross embedding REMBO (SA-cREMBO), a novel framework that generalizes REMBO to support multiple random Gaussian embeddings, each capturing a different local subspace structure of the high-dimensional objective. An index variable governs the embedding choice and is jointly modeled with the latent optimization variable via a product kernel in a Gaussian Process surrogate. This enables the optimizer to adaptively select embeddings conditioned on location, effectively capturing locally varying effective dimensionality, nonstationarity, and heteroscedasticity in the objective landscape. We theoretically analyze the expressiveness and stability of the index-conditioned product kernel and empirically demonstrate the advantage of our method across synthetic and real-world high-dimensional benchmarks, where traditional REMBO and other low-rank BO methods fail. Our results establish SA-cREMBO as a powerful and flexible extension for scalable BO in complex, structured design spaces. 1 Introduction BO is a useful method in many ubiquitous problems such as circuit design optimization [ 1 , 2 , 3 ] , machine learning [ 4 , 5 ] , computer graphics and visual design [ 6 ] . It has shown promise in optimizing expensive black-box functions in low-dimensional spaces. However, its applicability to high-dimensional problems remains limited due to the exponential growth of sample complexity with input dimensionality. REMBO [ 7 ] addresses this by assuming the function of interest lies in a low-dimensional subspace and performing optimization in a projected space defined by a random linear embedding matrix A\in\mathbb{R}^{D\times d} , where d\ll D . Despite its theoretical foundations, the performance of REMBO is highly sensitive to the choice of embedding matrix. A single random embedding may fail to intersect with the effective subspace of the objective function. To mitigate this, ensemble REMBO methods [ 8 , 9 ] explore multiple embeddings in parallel. However, training a separate Gaussian Process (GP) surrogate for each embedding leads to high computational cost, fragmented information, and reduced sample efficiency. [ 10 ] introduces an additional expansion projection method in addition to the existing projection. However, the In this chapter, we propose a unified framework that enables multiple embeddings to be modeled jointly within a single GP surrogate. By introducing an additional discrete input dimension representing the embedding index, the surrogate model can share information across embeddings while retaining their individual characteristics. This design significantly improves model efficiency, adaptability, and generalization. 1.1 REMBO REMBO is a Bayesian optimization algorithm that uses random embeddings to transform the input space into a lower-dimensional space. The key idea behind REMBO is that embedding the input space in a lower-dimensional space can reduce the number of function evaluations required to find the optimal solution, especially for high-dimensional problems. The theoretical foundation of REMBO is based on the idea of using random embeddings to preserve the pairwise distances between points in the input space. Specifically, REMBO uses a random linear projection to embed the input space into a lower-dimensional space, such that the distances between points in the embedded space approximate the distances between points in the original space. The embedding is designed to preserve the relative distances between points, while reducing the dimensionality of the problem. Once the input space has been embedded, REMBO uses Bayesian optimization to search for the optimal solution in the lower-dimensional space. The algorithm maintains a probabilistic model of the objective function, which is updated after each evaluation. The model is then used to generate a set of candidate points, which are evaluated to obtain new function values. The key advantage of REMBO over other optimization algorithms is that it can efficiently search high-dimensional input spaces with fewer function evaluations, thanks to the embedding. The embedding reduces the curse of dimensionality, making it possible to search the space more efficiently. Additionally, the probabilistic model of the objective function enables REMBO to balance exploration and exploitation, allowing it to quickly identify promising regions in the search space. Although Random Embedding BO is a simple method to optimize high dimensional problems, its efficiency is low due to both embedding distortion and the over-exploration of boundary issues. Since in high dimensions data points typically lie mostly on the boundary, and anyways far away from each other, the predictive variance tends to be higher in the regions near the boundary. This is a waste of computation effort assuming the global minimum is not on the boundary [ 11 ] . Let f:\mathbb{R}^{D}\rightarrow\mathbb{R} be the objective function in a high-dimensional space D . The goal is to find (1) \bm{x}^{*}=\arg\min_{\bm{x}\in\mathcal{X}}f(\bm{x}) (2) where \mathcal{X}\subset\mathbb{R}^{D} is the feasible set. In REMBO , the high-dimensional vector \mathbf{x} is expressed as \mathbf{x}=\mathbf{A}\mathbf{z} , where \mathbf{z}\in\mathbb{R}^{d} (with d\ll D ) is a lower-dimensional representation, and \mathbf{A} is a D\times d random matrix used to embed \mathbf{z} into the higher-dimensional space. The optimization problem then becomes \bm{z}^{*}=\arg\min_{\bm{z}\in\mathcal{Z}}f(\bm{A}\bm{z}) (3) where \mathcal{Z}=\bm{A}^{-1}(\mathcal{X}) is the projection of the feasible set \mathcal{X} into the lower-dimensional subspace. 2 Theoretical Foundations of REMBO REMBO leverages the fact that many high-dimensional optimization problems have an effective low-dimensional structure . While the true dimension of the search space is high, the objective function f often depends on only a few key directions. REMBO exploits this property by searching in a randomly projected low-dimensional subspace, where the optimization process is computationally feasible. However, this random projection introduces challenges that require careful consideration. Two important theoretical results are crucial in understanding the behavior of REMBO. These theorems provide guarantees about the effectiveness of random projections in preserving the structure of the function within a low-dimensional subspace, and the ability to optimize in that space while ensuring that the global optimum is not missed. 2.1 Theorem 1: Effective Dimensionality and Decomposition Suppose we want to optimize a function f:\mathbb{R}^{D}\rightarrow\mathbb{R} with effective dimension d_{e}\leq d subject to the box constraint X\subset\mathbb{R}^{D} , where X is centered around 0. Suppose further that the effective subspace T of f is such that T is the span of d_{e} basis vectors, and let x^{*}_{\top}\in T\cap X be an optimizer of f inside T . If A is a D\times d random matrix with independent standard Gaussian entries, there exists an optimizer y^{*}\in\mathbb{R}^{d} such that f(Ay^{*})=f(x^{*}_{\top}) and \|y^{*}\|_{2}\leq\sqrt{d_{e}}\epsilon\|x^{*}_{\top}\|_{2} with probability at least 1-\epsilon . Theorem 1. [ 7 ] Let f:\mathbb{R}^{D}\to\mathbb{R} be a function with effective dimensionality d_{e} . There exists a subspace T\subset\mathbb{R}^{D} , such that \text{rank}(T)=d_{e} . For any \bm{x}\in\mathbb{R}^{D} , we can decompose \bm{x} as \bm{x}=\bm{x}_{\top}+\bm{x}_{\perp} , where \bm{x}_{\top}\in T and \bm{x}_{\perp}\in T^{\perp} . Furthermore, f(\bm{x})=f(\bm{x}_{\top}) , meaning that the objective function depends only on the projection of \bm{x} onto T . The proof of this theorem shows that without loss of generality, we can restrict the optimization process to the subspace T , while ensuring that the global optimum can still be found by searching within this subspace. This theorem establishes that, due to the effective dimensionality d_{e} of the objective function f , it is sufficient