Id: arxiv/2611.10296 Url: https://arxiv.org/abs/2611.10296 Tags: math.OC Score: 0 Title: Sample complexity and scalability of adaptive-sampling trust-region methods for zeroth-order stochastic optimization --- Part I: common random numbers meet supermartingales Domain: math.OC Source: arxiv Authors: Joseph Dzahini, Sara Shashaani, Coralia Cartis Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.10296 We analyze adaptive sampling stochastic model-based trust-region methods that build their models in random subspaces and use common random numbers (CRN) within an iteration, and obtain, within a STORM-type analysis, the first $\tilde{\mathcal{O}}(\varepsilon^{-4})$ bound on the number of function evaluations needed to reach $\varepsilon$-stationarity, both almost surely and in expectation. The subspace model reduces the per-iteration computational cost, which allows scalability. The analysis relies on a general framework for the complexity of adaptive stochastic processes that carries the…