Random-subspace Ellipsoidal Trust-region Methods for Derivative-free Optimization
Abstract
Random-subspace model-based methods offer a promising approach to solving derivative-free optimization (DFO) problems in high dimensions. However, the usual ratio of actual to predicted reduction assesses model agreement at the trial point without directly measuring subspace quality. An accurate prediction in a poorly aligned subspace may therefore trigger trust-region expansion in all directions. We introduce Random-subspace Ellipsoidal TRust-region Optimization (RETRO), a framework for unconstrained DFO using ellipsoidal trust regions. Its trust-region updates combine global size changes with additional expansion or contraction within the sampled subspace, reflecting where the trial step was computed. We define an ellipsoidal subspace alignment measure that accounts for both the subspace and trust-region shape, and analyze Haar-uniform sampling and metric-guided sampling based on the current shape matrix. We establish almost-sure first-order liminf convergence and an 𝒪(ε−2) bound on the expected number of iterations required to reach an iterate with gradient norm at most ε. Numerical experiments on projected low-rank problems in dimension $1000$ show that using ellipsoidal shape information in subspace selection can reduce function evaluation costs relative to ball-based QARSTA, with the most pronounced improvements occurring when the solver subspace dimension matches the projection rank.
Related
- A note on the complexity of random subspace model-based methods for derivative-free optimization
- Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization
- Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
- MpSub: A Momentum p-Dimensional Subspace Trust-Region Method for Derivative-Free Fine-Tuning of Large Language Models
- Factorized Krylov subspace methods for solving large Sylvester equations
BibTeX
@misc{chen2026randomsubspace,
title = {{Random-subspace Ellipsoidal Trust-region Methods for Derivative-free Optimization}},
author = {Yiwen Chen and Pengcheng Xie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24866},
eprint = {2610.24866},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24866},
}
RIS
TY - UNPB
TI - Random-subspace Ellipsoidal Trust-region Methods for Derivative-free Optimization
AU - Yiwen Chen
AU - Pengcheng Xie
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24866
UR - https://arxiv.org/abs/2610.24866
AB - Random-subspace model-based methods offer a promising approach to solving derivative-free optimization (DFO) problems in high dimensions. However, the usual ratio of actual to predicted reduction assesses model agreement at the trial point without directly measuring subspace quality. An accurate prediction in a poorly aligned subspace may therefore trigger trust-region expansion in all directions. We introduce Random-subspace Ellipsoidal TRust-region Optimization (RETRO), a framework for unconstrained DFO using ellipsoidal trust regions. Its trust-region updates combine global size changes with additional expansion or contraction within the sampled subspace, reflecting where the trial step was computed. We define an ellipsoidal subspace alignment measure that accounts for both the subspace and trust-region shape, and analyze Haar-uniform sampling and metric-guided sampling based on the current shape matrix. We establish almost-sure first-order liminf convergence and an 𝒪(ε^−2) bound on the expected number of iterations required to reach an iterate with gradient norm at most ε. Numerical experiments on projected low-rank problems in dimension $1000$ show that using ellipsoidal shape information in subspace selection can reduce function evaluation costs relative to ball-based QARSTA, with the most pronounced improvements occurring when the solver subspace dimension matches the projection rank.
ER -