The advent of high-performance computing has enabled numerous advances in simulations of physical processes, as well as recent progress in artificial intelligence. As the algorithms used to perform these tasks become increasingly more complex, they involve a growing number of parameters to be calibrated in order to maximize performance. Such a tuning process is generally quite expensive, not only due to the cost of running any given parameter configuration, but also because of the large number of parameters that is typically involved.
Blackbox optimization is a field of applied mathematics concerned with computing the best value of a given objective while solely relying on (expensive) values of this objective. This paradigm is particularly well suited for simulation-based problems, and has contributed to the rise of blackbox optimization and its use in applications [2, 4, 9]. A persistent challenge in developing derivative-free or blackbox algorithms is to design scalable techniques, for which the performance does not worsen as the problem dimension increases. Compared to traditional non-linear optimization, where scalable techniques are well-studied, the lack of derivative information in blackbox optimization makes this situation much more challenging. Potential applications of scalable blackbox optimization methods include machine learning [11, 1] and image analysis [5].

In this project, we aim at building on existing work by the two PIs [7,10] in which the use of random subspaces in blackbox optimization was investigated. This paradigm follows a recent trend of research in the field, where classical deterministic algorithms are modified by performing steps into random subspaces at every iteration. Even though several techniques based on this principle have been proposed, there remains a number of algorithmic variants that have not been revisited from a subspace viewpoint. The goal of this project is to investigate such variants, and to provide theoretical guarantees as well as numerical evidence of the quality of these methods.
Our primary focus will be on developing model-based algorithms using quadratic models in random subspaces. Although those have been partly investigated in practice [3], a complete understanding of random quadratic models in random subspaces remains elusive. We will build on a recent collaboration by both PIs [10] to develop new analyses for randomized model-based schemes using quadratic approximations. An important question of theoretical interest here is whether random subspaces allow for more efficient use of problem information (in terms of progress achieved towards a solution). To this end, we will build on very recent existing work by the two PIs [7] (which covers the simple case of linear approximations) to study the evaluation efficiency of quadratic subspace methods in an average case, rather than the more common worst-case analysis. This would form a basis for motivating the development of theoretically sound and practically performant quadratic-based subspace methods.
Another line of work that we will explore consists in extending our subspace direct-search scheme to account for the presence of constraints. In particular, we will seek new strategies to produce directions generated in random subspace that produce feasible descent directions, in the spirit of direct-search methods for linearly constrained problem studied by PI Royer [6].
Although linear constraints will form our first angle of investigation, we will also investigate the relevance of our approach in the context of convex constraints, recently studied by PI Roberts [8].
Both axes of research are aimed at producing research papers, that will be submitted to international peer-reviewed journals for publication. These papers will be accompanied with open-source code, that will allow for reproducibility of our results.

Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision – LAMDASE

Australia

[1] Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, Huan Zhang, Cho-Jui Hsieh, and Mani B. Srivastava. GenAttack: Practical black-box attacks with gradient-free optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1111–1119, Prague, Czech Republic, 2019. ACM.
[2] C. Audet and W. Hare. Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer International Publishing, 2017.
[3] C. Cartis and L. Roberts. Scalable subspace methods for derivative-free nonlinear least squares optimization. Math. Program., 199:461–524, 2023.
[4] A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, 2009.
[5] Matthias J. Ehrhardt and Lindon Roberts. Inexact derivative-free optimization for bilevel learning. Journal of Mathematical Imaging and Vision, 63(5):580–600, 2020.
[6] S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang. Direct search based on probabilistic feasible descent for bound and linearly constrained problems. Comput. Optim. Appl., 72:525–559, 2019.
[7] W. Hare, L. Roberts, and C. W. Royer. Expected decrease for derivative-free algorithms using random subspaces. arXiv:2308.04734, 2023.
[8] M. Hough and L. Roberts. Model-based derivative-free methods for convex-constrained optimization. SIAM J. Optim., 32(4):2552–2579, 2022.
[9] J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numer., 28:287–404, 2019.
[10] L. Roberts and C. W. Royer. Direct search based on probabilistic descent in reduced subspaces. SIAM J. Optim., 2023 (To appear).
[11] T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv:1703.03864, 2017