A note on the complexity of random subspace model-based methods for derivative-free optimization

@misc{cartis2026note,
  title = {{A note on the complexity of random subspace model-based methods for derivative-free optimization}},
  author = {Coralia Cartis and Lindon Roberts},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2608.17307},
  eprint = {2608.17307},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.17307},
}

TY  - UNPB
TI  - A note on the complexity of random subspace model-based methods for derivative-free optimization
AU  - Coralia Cartis
AU  - Lindon Roberts
PY  - 2026
DA  - 2026/10/18
PB  - arXiv
DO  - 10.48550/arxiv.2608.17307
UR  - https://arxiv.org/abs/2608.17307
AB  - We demonstrate that, with a suitable rescaling, using Johnson-Lindenstrauss transforms (JLTs) in the random subspace model-based derivative-free optimization (DFO) algorithm from [Cartis & Roberts, Math. Prog. 199 (2023)] achieves an improved first-order worst-case evaluation complexity bound compared to 'unscaled' JLTs. This improved bound does not require any modification to the original algorithm or complexity analysis, and matches the best-known bound in terms of dimension dependence for model-based DFO (e.g. achieved by [Scheinberg & Chaudhry, ICM 2026] using Haar matrices in a similar framework). A similarly refined analysis of the analogous second-order subspace method from [Cartis & Roberts, Opt. Meth. & Softw. (2026)] shows that using suitably scaled JLTs to generate the subspaces gives a better complexity bound, which improves over full-space methods only if the problem has low effective rank.
ER  -