mlsanityData to 7 Oct 2026

Global optimization using random embeddings

arXiv 2107.12102 ↗First posted 26 Jul 2021math.OC cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

36 of 73 references.

References · 36

  1. 2021Convex optimizationcited by 2,479
  2. 2018Measuring the Intrinsic Dimension of Objective Landscapescited by 364
  3. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  4. 2015Coordinate Descent Algorithmscited by 218
  5. 2013Bayesian Optimization in a Billion Dimensions via Random Embeddingscited by 178
  6. 2019Subspace Inference for Bayesian Deep Learningcited by 94
  7. 2019Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspacescited by 73
  8. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  9. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  10. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 45
  11. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 42
  12. 2013Active Learning of Linear Embeddings for Gaussian Processescited by 34
24 more
  1. 2019RSN: Randomized Subspace Newtoncited by 34
  2. 2015Global convergence rate analysis of unconstrained optimization methods based on probabilistic modelscited by 27
  3. 2018Scaling Gaussian Process Regression with Derivativescited by 27
  4. 2017On the choice of the low-dimensional domain for global optimization via random embeddingscited by 25
  5. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  6. 2019High Dimensional Bayesian Optimization via Supervised Dimension Reductioncited by 21
  7. 2020Stochastic Subspace Cubic Newton Methodcited by 21
  8. 2017An Investigation of Newton-Sketch and Subsampled Newton Methodscited by 18
  9. 2014A warped kernel improving robustness in Bayesian optimization via random embeddingscited by 17
  10. 2020Semi-supervised Embedding Learning for High-dimensional Bayesian Optimizationcited by 11
  11. 2013Convergence of trust-region methods based on probabilistic modelscited by 10
  12. 2019Stochastic Subspace Descentcited by 10
  13. 2021Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimizationcited by 10
  14. 2020Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimizationcited by 9
  15. 2020An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networkscited by 8
  16. 2020A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionalitycited by 7
  17. 2013Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methodscited by 6
  18. 2017Random projections for linear programmingcited by 6
  19. 2020A supervised learning approach involving active subspaces for an efficient genetic algorithm in high-dimensional optimization problemscited by 6
  20. 2020Constrained global optimization of functions with low effective dimensionality using multiple random embeddingscited by 5
  21. 2021Hashing embeddings of optimal dimension, with applications to linear least squarescited by 4
  22. 2019High-Dimensional Optimization in Adaptive Random Subspacescited by 3
  23. 2020Proximal Gradient methods with Adaptive Subspace Samplingcited by 2
  24. 2021Random projections for conic programscited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 0; 2024: 2; 2025: 1.

6 papers.

  1. 2022Recent Advances in Bayesian Optimizationcited by 74
  2. 2024Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximationcited by 8
  3. 2021Curvature-Aware Derivative-Free Optimizationcited by 7
  4. 2022Optimization on Manifolds via Graph Gaussian Processescited by 4
  5. 2024Dimensionality Reduction Techniques for Global Bayesian Optimisationcited by 1
  6. 2025Nonlinear Dimensionality Reduction Techniques for Bayesian Optimizationcited by 0