# Global optimization using random embeddings

arXiv: https://arxiv.org/abs/2107.12102 · HTML: https://mlsanity.com/paper/2107.12102/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 73 references that are in the map.
- First posted on arXiv 26 Jul 2021.

## Builds on (most cited first, 30 of 36)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Subspace Inference for Bayesian Deep Learning](https://mlsanity.com/paper/1907.07504/) (2019)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Active Learning of Linear Embeddings for Gaussian Processes](https://mlsanity.com/paper/1310.6740/) (2013)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Scaling Gaussian Process Regression with Derivatives](https://mlsanity.com/paper/1810.12283/) (2018)
- [On the choice of the low-dimensional domain for global optimization via random embeddings](https://mlsanity.com/paper/1704.05318/) (2017)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [High Dimensional Bayesian Optimization via Supervised Dimension Reduction](https://mlsanity.com/paper/1907.08953/) (2019)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [A warped kernel improving robustness in Bayesian optimization via random embeddings](https://mlsanity.com/paper/1411.3685/) (2014)
- [Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization](https://mlsanity.com/paper/2005.14601/) (2020)
- [Convergence of trust-region methods based on probabilistic models](https://mlsanity.com/paper/1304.2808/) (2013)
- [Stochastic Subspace Descent](https://mlsanity.com/paper/1904.01145/) (2019)
- [Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization](https://mlsanity.com/paper/2102.12016/) (2021)
- [Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization](https://mlsanity.com/paper/2006.05874/) (2020)
- [An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networks](https://mlsanity.com/paper/2012.01901/) (2020)
- [A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality](https://mlsanity.com/paper/2003.09673/) (2020)
- [Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods](https://mlsanity.com/paper/1310.1826/) (2013)
- [Random projections for linear programming](https://mlsanity.com/paper/1706.02768/) (2017)

## Built on by (most cited first, 6 of 6)

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation](https://mlsanity.com/paper/2410.16893/) (2024)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Optimization on Manifolds via Graph Gaussian Processes](https://mlsanity.com/paper/2210.10962/) (2022)
- [Dimensionality Reduction Techniques for Global Bayesian Optimisation](https://mlsanity.com/paper/2412.09183/) (2024)
- [Nonlinear Dimensionality Reduction Techniques for Bayesian Optimization](https://mlsanity.com/paper/2510.15435/) (2025)

## Abstract (arXiv)

We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, that only vary over a low-dimensional subspace, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem.