Learning the subspace of variation for global optimization of functions with low effective dimension

We propose an algorithmic framework, that employs active subspace techniques, for scalable global optimization of functions with low effective dimension (also referred to as low-rank functions). This proposal replaces the original high-dimensional problem by one or several lower-dimensional reduced subproblem(s), capturing the main directions of variation of the objective which are estimated here as the principal components of a collection of sampled gradients. We quantify the sampling complexity of estimating the subspace of variation of the objective in terms of its effective dimension and hence, bound the probability that the reduced problem will provide a solution to the original problem. To account for the practical case when the effective dimension is not known a priori, our framework adaptively solves a succession of reduced problems, increasing the number of sampled gradients until the estimated subspace of variation remains unchanged. We prove global convergence under mild assumptions on the objective, the sampling distribution and the subproblem solver, and illustrate numerically the benefits of our proposed algorithms over those using random embeddings.