A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality
We investigate the unconstrained global optimization of functions with low effective dimensionality, which are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in Wang et al. (2016, J. Artificial Intelligence Res., 55, 361–387), we s...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Oxford University Press
2021
|
| _version_ | 1797106564131192832 |
|---|---|
| author | Cartis, C Otemissov, A |
| author_facet | Cartis, C Otemissov, A |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | We investigate the unconstrained global optimization of functions with low effective dimensionality, which are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in Wang et al. (2016, J. Artificial Intelligence Res., 55, 361–387), we study a generic Random Embeddings for Global Optimization (REGO) framework that is compatible with any global minimization algorithm. Instead of the original, potentially large-scale optimization problem, within REGO, a Gaussian random, low-dimensional problem with bound constraints is formulated and solved in a reduced space. We provide novel probabilistic bounds for the success of REGO in solving the original, low effective-dimensionality problem, which show its independence of the (potentially large) ambient dimension and its precise dependence on the dimensions of the effective and embedding subspaces. These results significantly improve existing theoretical analyses by providing the exact distribution of a reduced minimizer and its Euclidean norm and by the general assumptions required on the problem. We validate our theoretical findings by extensive numerical testing of REGO with three types of global optimization solvers, illustrating the improved scalability of REGO compared with the full-dimensional application of the respective solvers. |
| first_indexed | 2024-03-07T07:04:17Z |
| format | Journal article |
| id | oxford-uuid:1ea0e4a5-a35c-42db-ba46-a49510f43eb5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:04:17Z |
| publishDate | 2021 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:1ea0e4a5-a35c-42db-ba46-a49510f43eb52022-04-21T08:12:07ZA dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionalityJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1ea0e4a5-a35c-42db-ba46-a49510f43eb5EnglishSymplectic ElementsOxford University Press2021Cartis, COtemissov, AWe investigate the unconstrained global optimization of functions with low effective dimensionality, which are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in Wang et al. (2016, J. Artificial Intelligence Res., 55, 361–387), we study a generic Random Embeddings for Global Optimization (REGO) framework that is compatible with any global minimization algorithm. Instead of the original, potentially large-scale optimization problem, within REGO, a Gaussian random, low-dimensional problem with bound constraints is formulated and solved in a reduced space. We provide novel probabilistic bounds for the success of REGO in solving the original, low effective-dimensionality problem, which show its independence of the (potentially large) ambient dimension and its precise dependence on the dimensions of the effective and embedding subspaces. These results significantly improve existing theoretical analyses by providing the exact distribution of a reduced minimizer and its Euclidean norm and by the general assumptions required on the problem. We validate our theoretical findings by extensive numerical testing of REGO with three types of global optimization solvers, illustrating the improved scalability of REGO compared with the full-dimensional application of the respective solvers. |
| spellingShingle | Cartis, C Otemissov, A A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title | A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title_full | A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title_fullStr | A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title_full_unstemmed | A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title_short | A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| title_sort | dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality |
| work_keys_str_mv | AT cartisc adimensionalityreductiontechniqueforunconstrainedglobaloptimizationoffunctionswithloweffectivedimensionality AT otemissova adimensionalityreductiontechniqueforunconstrainedglobaloptimizationoffunctionswithloweffectivedimensionality AT cartisc dimensionalityreductiontechniqueforunconstrainedglobaloptimizationoffunctionswithloweffectivedimensionality AT otemissova dimensionalityreductiontechniqueforunconstrainedglobaloptimizationoffunctionswithloweffectivedimensionality |