betaFeedback

WorksMathematics

Sample complexity and scalability of adaptive-sampling trust-region methods for zeroth-order stochastic optimization — Part~II: a new pathwise analysis with randomized subspaces

Abstract

Stochastic trust-region methods are usually analyzed in expectation or with high probability: the guarantee is about the law of the algorithm, not about the run in hand. This paper analyzes the adaptive sampling stochastic trust-region method ASTRO-DF (which is the reuse variant ASTRA-R in Part I) in random subspaces along almost every sample path. The route has one probabilistic ingredient, the accuracy of the common-random-number estimates at the adaptive sample size, uniformly over the trust region; Part~I established it by chaining, here it is obtained at the stopping time by optional stopping and converted, by the first Borel–Cantelli lemma, into an accuracy that holds from a random index on, after which the deterministic trust-region argument applies. We prove almost sure convergence and almost sure iteration and sample complexity of orders O~(dε−2)\tilde{\mathcal{O}}(dε^{-2}) and O~(d2ε−4)\tilde{\mathcal{O}}(d^2ε^{-4}), with a subspace dimension growing logarithmically; we show that at a fixed subspace dimension the eventual-accuracy argument yields O~(ε−2−O(1/p))\tilde{\mathcal{O}}(ε^{-2-\mathcal{O}(1/p)}) iterations and O~(ε−4−O(1/p))\tilde{\mathcal{O}}(ε^{-4-\mathcal{O}(1/p)}) samples; we show that the random index after which the rates hold cannot be too large and has an explicit, rapidly decaying tail. Compared with the supermartingale route, the pathwise route needs no lower bound on the per-iteration probability of a good iteration, no coupling between the trust-region expansion factor and the sketch, and no moment condition on the summed squared radii.

Introduction

We consider unconstrained simulation optimization problems of the form

min⁡x∈Rdf(x):=E[F(x,ξ)]=∫ΞF(x,ξ) dP(ξ),(1)\min_{x\in\mathbb{R}^{d}} f(x) := \mathbb{E}[F(x,\xi)] = \int_{\Xi} F(x,\xi)\,dP(\xi), \tag*{(1)}

where f:Rd→Rf:\mathbb{R}^{d}\to\mathbb{R} is smooth, possibly nonconvex and bounded below, and F:Rd×Ξ→RF:\mathbb{R}^{d}\times\Xi\to\mathbb{R} is observable only through a Monte Carlo oracle: a call at xx returns F(x,ξ)=f(x)+E(x,ξ)F(x,\xi)=f(x)+E(x,\xi) for a fresh ξ\xi, with no derivative. The estimator of f(x)f(x) from nn calls and its estimated variance are

F‾(x,n)=1n∑j=1nF(x,ξj),σ^F2(x,n)=1n∑j=1n(F(x,ξj)−F‾(x,n))2.(2)\overline{F}(x,n)=\frac{1}{n}\sum_{j=1}^{n}F(x,\xi_j),\qquad\widehat{\sigma}^{2}_{F}(x,n)=\frac{1}{n}\sum_{j=1}^{n}\left(F(x,\xi_j)-\overline{F}(x,n)\right)^{2}. \tag*{(2)}

The oracle call is the expensive unit, and WϵW_{\epsilon} counts oracle calls. A replication is one draw ξ\xi of the oracle’s randomness, and a stream is a sequence ξ1,ξ2,…\xi_1,\xi_2,\ldots of independent replications. Evaluating several points on the same stream means evaluating F(⋅,ξj)F(\cdot,\xi_j) at each of them with the same ξj\xi_j, j=1,…,nj=1,\ldots,n; this is what common random numbers means here. A block is a finite stretch of a stream, and a stream or block is fresh if it is independent of everything drawn before it.

This is Part II of a two-part study of one algorithm: the adaptive sampling stochastic trust-region method in random subspaces of Part I [13], in the variant in which the trial point is evaluated on the replications already drawn to build the model. Part I analyzed it through a supermartingale framework and obtained complexity bounds in expectation and almost surely along deterministic sequences, with a fixed subspace dimension. This part analyses the same algorithm along almost every sample path. The two parts share one probabilistic result, the uniform accuracy theorem of Part I, and differ in everything built on top of it.

Two ways to evaluate efficiency in a stochastic algorithm A stochastic optimization algorithm run produces one sequence of iterates {Xk}\{X_k\}, one sequence of sample sizes {Nk}\{N_k\}, and one first hitting time Tϵ:=inf⁡{k:∥∇f(Xk)∥≤ϵ}T_\epsilon:= \inf\{k : \lVert\nabla f(X_k)\rVert\le\epsilon\}, which are all random. There are two ways to make a statement about them.

The first, which is the common approach in the literature on stochastic trust-region methods [2, 7, 14, 20], is to average over runs:

E[Tϵ]≤cϵ−2,orP(Tϵ≤cϵ−2)≥1−e−c′ϵ−2.\mathbb{E}[T_\epsilon] \le c\epsilon^{-2}, \qquad\text{or} \qquad\mathbb{P}(T_\epsilon\le c\epsilon^{-2}) \ge1-e^{-c'\epsilon^{-2}}.

Such a statement is about the law of the algorithm. It is obtained by exhibiting a supermartingale in the iteration counter whose drift is negative as long as the algorithm has not stopped, and it requires that the good events of each iteration have conditional probability bounded below by a fixed constant, at every iteration. Its constants are deterministic. A run with TϵT_\epsilon ten times the expected value is not excluded, only made unlikely.

The second is to fix the sample path and make a statement about it: for almost every ω\omega, there is a threshold ϵ0(ω)>0\epsilon_0(\omega)>0 and a constant R(ω)<∞R(\omega)<\infty such that Tϵ(ω)≤R(ω)ϵ−2T_\epsilon(\omega)\le R(\omega)\epsilon^{-2} for all ϵ≤ϵ0(ω)\epsilon\le\epsilon_0(\omega). Equivalently, along every deterministic sequence ϵℓ↓0\epsilon_\ell\downarrow0,

P(Tϵℓϵℓ2>R  infinitely often)=0.(3)\mathbb{P}\left(T_{\epsilon_\ell}\epsilon_\ell^2>R\ \text{ infinitely often}\right)=0. \tag*{(3)}

Such a statement is about the run. Its constant is random, and it says that on the run one did, beyond some random step (the “burn-in”) the deterministic rate holds. In simulation optimization, where one typically gets a single optimization run with an expensive model, this is a guarantee worth having.

The two readings are obtained by different devices. Part I obtains both: expected bounds, and almost-sure bounds of the form (3) with an integrable constant, from a lower bound on the conditional probability of a good iteration holding at every iteration. This paper is about a different device for the second. The device is elementary. Every accuracy requirement of the deterministic trust-region theory (the model gradient is accurate to O(Δk)O(\Delta_k); the difference of estimation errors between incumbent and trial point is O(Δk2)O(\Delta_k^2); the sketch is well aligned with the gradient) is an event Ek\mathcal{E}_k of iteration kk. If its failure probability is summable, ∑kP(Ekc)<∞\sum_k\mathbb{P}(\mathcal{E}_k^c)<\infty, then by the first Borel–Cantelli lemma Ek\mathcal{E}_k holds for all k≥K(ω)k\ge K(\omega) on almost every path, for a random, almost surely finite K(ω)K(\omega). From K(ω)K(\omega) onwards every hypothesis of the deterministic theory is in force, and the deterministic proof applies verbatim to the tail of the path. The first Borel–Cantelli lemma requires no independence, which is why common random numbers cause no difficulty on this route; and summability, not a lower bound at every iteration, is the only thing asked of the probabilities. What is lost is the expectation: K(ω)K(\omega) is finite and, as Section 7.3 shows, has finite moments, but the bound holds only beyond a random threshold ϵ0(ω)\epsilon_0(\omega), and no expected bound follows.

The cost of making failure probabilities summable is paid in two places. The sample size at iteration kk must be inflated by a slowly growing factor λk\lambda_k, so that the estimation failure probability is e−cλke^{-c\lambda_k} and λk=λ0(log⁡(k+2))1+ϵ\lambda_k=\lambda_0(\log(k+2))^{1+\epsilon} suffices, and it is the price of adaptive sampling known from sequential estimation [8, 16]. And the subspace dimension pkp_k must grow so that the misalignment probability e−cpke^{-cp_k} is summable; pkp_k of order log⁡k\log k, capped at dd, suffices. Section 8 quantifies what happens if one refuses to pay the second price: at a fixed pp the argument of this paper gives ϵ−2O(1/p)\epsilon^{-2}O(1/p), where Part I’s per-iteration probability bound gives ϵ−2\epsilon^{-2}.

It is fair to ask why one would take this route when the supermartingale route gives, for a fixed subspace dimension and correctly set constants, a stronger statement. The answer is in what each route asks of the algorithm rather than in what it delivers. The supermartingale route needs the good event of every iteration to have conditional probability above a fixed level; in particular the sketch must be well aligned with probability above one half at every iteration. The pathwise route needs only summability, so a sketch that is unreliable early and reliable late is admissible. The same feature admits components whose reliability improves with the iteration counter rather than being bounded below from the start, of which a growing subspace dimension is the instance treated here. And once the good events hold, the deterministic proof applies, so any result of the deterministic trust-region theory transfers to the stochastic setting by changing only the accuracy events; the supermartingale route re-derives a potential and a drift for each variant. Section 7.3 adds that the burn-in is not an unquantified random time: its tail is bounded by the tail of the series one sums in Borel–Cantelli, which is explicit, so finite-time, high-probability bounds are available from the same computation.

Related work

Stochastic trust-region methods with random models are analyzed through supermartingales in the STORM line of work [2, 7] and, in random subspaces, in [14]; these analyses, and the high-probability ones of [3], bound the number of iterations. The total sample complexity of STORM was obtained in [20], for sample sizes prescribed by the step size and a known variance bound. Adaptive sampling, in which the sample size is a stopping time driven by the observed variance, originates with ASTRO-DF [26]; its pathwise complexity analysis [18] showed that common random numbers reduce the sample size per iteration from order Δk−4\Delta_k^{-4} to Δk−2\Delta_k^{-2}, and the sample complexity from order ϵ−6\epsilon^{-6} to ϵ−4\epsilon^{-4}. The same per-iteration reduction is obtained in [12, 23] under a tail condition on the estimates, with deterministic sample sizes and no sample complexity bound. Part I [13] brought adaptive sampling and common random numbers into the supermartingale framework, including the reuse of replications at the trial point, with a fixed subspace dimension. Random-subspace model-based methods and their dimension dependence in the deterministic case are studied in [4, 5]. The present paper is the pathwise counterpart of Part I, with a subspace dimension that may grow, and it tracks the dimension dependence in the stochastic case.

Contributions

Pathwise analysis of the reuse algorithm. Sections 4–7 give strong consistency and almost sure iteration and sample complexity, Tϵ=O~(ϵ−2)T_\epsilon= \widetilde{O}(\epsilon^{-2}) and Wϵ=O~(ϵ−4)W_\epsilon= \widetilde{O}(\epsilon^{-4}), for the algorithm of Part I with fully reused common random numbers and a logarithmically growing subspace dimension. The analysis uses only three deterministic consequences of one probabilistic event (Section 5); it does not assume or prove full linearity of the model, and it does not use the accuracy of the model Hessian.

Concentration tailored to a stopping-time sample size. The adaptive sample size NkN_k is a stopping time for the within-iteration filtration. Section 4.2 obtains the Bernstein tail of the averaged common-random-number increment at NkN_k by optional stopping of the exponential supermartingale, with no statement at other sample sizes and no time-uniform maximal inequality. Part I obtained the same tail by Ville’s inequality, which is the stronger statement; we use the weaker one deliberately, because it uses exactly the property the algorithm supplies, and because it displays the mechanism behind the two steps discussed next. The chaining argument of Part I, which makes the bound uniform over the trust region and is what permits reuse, is cited and not reproved; the one place where its proof changes is identified.

Relation to the pathwise analysis of ASTRO-DF. This paper descends from [18], which gave the pathwise analysis of ASTRO(-DF) in the full space and identified the sample-size scalings that common random numbers make possible. Two steps of its estimation-error argument are sharpened here, and both are instructive from the stopping-time viewpoint. Here we obtain the tail bound at the adaptive sample size by evaluating the exponential supermartingale at the stopping time itself (Section 4.2). And when incumbent and candidate share replications, the candidate is a function of the replications being averaged; a pointwise inequality applies to it when it is evaluated on a random number stream drawn after the model is built, with the pairing kept within that stream, while full reuse calls for the uniform bound of Section 4.4. Section 4.3 sets out both points and the three sampling schemes they distinguish.

Fixed versus growing subspace dimension. Section 8 proves that with a fixed pp and misalignment probability βˉQ\bar{\beta}_{Q} below an explicit threshold, the radius satisfies Δk≥θk−ϱ\Delta_k \ge\theta k^{-\varrho} eventually with ϱ=O(1/log⁡(1/βˉQ))\varrho= O(1/\log(1/\bar{\beta}_{Q})), which gives almost sure liminf convergence when ϱ≤12\varrho\le\frac{1}{2} and Tϵ=O(ϵ−2/(1−2ϱ))T_\epsilon= O(\epsilon^{-2/(1-2\varrho)}). The exponent tends to 2 as pp grows, and pk=O(log⁡k)p_k = O(\log k) is the threshold at which the exponent is exactly 2. The growth is what the eventual-accuracy argument needs to reach exponent 2 without Part I’s per-iteration probability bound.

Dimension dependence. Section 9 discusses all statements about dd, pp and the sketch scale. Rescaling the sketch is shown to be a reparametrization of the algorithm (Proposition 3.2), so that the improvement of Cartis and Roberts [5] is the improvement of one parametrization over another; under their convention orthonormal columns give O~(dϵ−2)\widetilde{O}(d\epsilon^{-2}) iterations, the sketch of [14] scaled by d/p\sqrt{d/p} gives O~(dp−1ϵ−2)\widetilde{O}(d p^{-1}\epsilon^{-2}), and a scale balancing model bias against estimation error gives O~(dp−1/2ϵ−2)\widetilde{O}(d p^{-1/2}\epsilon^{-2}). The price of reuse in our bounds is a factor pp in the sample size per iteration: the accuracy must hold at every point of the pp-dimensional trust region at once, and the nets that cover it have a number of points exponential in pp. With pk=O(log⁡k)p_k = O(\log k) this factor is logarithmic; in the full space, p=dp = d, it is a factor dd. This scale, κQ≍p−1/4\kappa_Q \asymp p^{-1/4}, is the best over the sketch scale in our bounds and gains a factor p\sqrt{p} over orthonormal columns in both the iteration and the sample bound. It requires the tolerance on the estimation error to shrink with the subspace dimension, κedF≍p−1/2\kappa_{\mathrm{edF}} \asymp p^{-1/2}, which costs a factor p\sqrt{p} in the sample size at a given radius.

During the writing of this work, a recent survey [11] appeared that formalizes common random numbers as a multi-point stochastic zeroth-order oracle. The ASTRO-DF [18] and ASTRA [13] sample complexity bounds of order O(ϵ−4)O(\epsilon^{-4}) are achieved in [1] in expectation, for a fixed-step randomized finite-difference method. Here and in [13], we address the more analytically-challenging and practically-useful framework of stochastic trust region methods with parameter-free adaptive sampling, with fresh, or even re-used, objective estimates. The dimension dependence of our bounds here matches the ones in [1].

Relation to Part I

Both parts analyze Algorithm 1 below. Table 1 records what each requires and delivers. Part I asks that the good event of each iteration have conditional probability above a fixed level at every iteration, and needs the misalignment probability of the sketch below 12\frac{1}{2}; from this it obtains, through the supermartingale on the radius exponent, constants with finite expectation and bounds in expectation. Part II asks that the failure probabilities be summable and obtains, through Borel–Cantelli, that the good events hold eventually; the constants are random (integrable when δ>1\delta> 1 in (28), Remark 9), the subspace dimension must grow, and nothing is obtained in expectation.

Part I (supermartingale)Part II (pathwise)
within an iterationVille’s inequalityoptional stopping (Lemma 4.3)
across iterationscount of favorable events, each of conditional probability ≥π⋆>12\ge\pi_\star> \frac{1}{2}first Borel–Cantelli; summable failure probabilities
subspace dimensionfixed pp, with βQ<1−γ^r/πmin⁡\beta_Q < 1 - \hat{\gamma}_r/\pi_{\min}pk=O(log⁡k)p_k = O(\log k) nondecreasing; fixed pp at a cost (§ 8)
parameter couplingπ⋆γ−2r+(1−π⋆)γ2r<1\pi_\star\gamma^{-2r} + (1-\pi_\star)\gamma^{2r} < 1none
inflation λk→∞\lambda_k \to\inftyoptional; a constant inflation needs thresholds on λ0\lambda_0 set by unknown constantsrequired
constants κa,κg\kappa_a,\kappa_gfixedmay vary with kk
iteration boundO~(ϵ−2)\widetilde{O}(\epsilon^{-2}) a.s. and in expectationO~(ϵ−2)\widetilde{O}(\epsilon^{-2}) a.s.
constantsdeterministic, but through the index beyond which its probability bounds hold, which unknown problem constants fixrandom; integrable when pkp_k grows a little faster than the minimum ((28) with δ>1\delta> 1, Remark 9)
range in ϵ\epsilonexpectation only below a threshold exponentially small in that indexevery ϵ\epsilon below a random threshold ϵ0(ω)\epsilon_0(\omega)
sample boundO~(ϵ−4)\widetilde{O}(\epsilon^{-4}) a.s.; in expectation under a moment condition on SΔS_\DeltaO~(ϵ−4)\widetilde{O}(\epsilon^{-4}) a.s.
tail of the burn-inMarkov from the expectation, order t−1t^{-1}explicit, superpolynomial (§ 7.3)
noise momentsfourthfourth
dimension dependencenot treated§ 9

Table 1. Requirements and outputs of the two routes. Both use Algorithm 1 and the uniform accuracy bound of Theorem 4.7 (Part I, Theorem 4.2). In Part I, βQ\beta_Q is the misalignment probability; here βQ,k\beta_{Q,k} is the alignment probability (Assumption 6).

References

  1. [1]Albert S Berahas, Liyuan Cao, and Katya Scheinberg. Stochastic and noisy oracles in smooth continuous optimization. arXiv preprint arXiv:2610.41086, 2026.arxiv.org/abs/2610.41086
  2. [2]Jose Blanchet, Coralia Curtis, Matt Menickelly, and Katya Scheinberg. Convergence rate analysis of a stochastic trust-region method via supermartingales. INFORMS journal on optimization, 1(2):92–119, 2019.DOI
  3. [3]Liyuan Cao, Albert S Berahas, and Katya Scheinberg. First-and second-order high probability complexity bounds for trust-region methods with noisy oracles. Mathematical Programming, 207(1):55–106, 2024.arxiv.org/abs/2205.03667
  4. [4]C. Curtis and L. Roberts. Scalable subspace methods for derivative-free nonlinear least-squares optimization. Mathematical Programming, pages 1–64, 2022.
  5. [5]Coralia Curtis and Lindon Roberts. A note on the complexity of random subspace model-based methods for derivative-free optimization. arXiv preprint arXiv:2608.17307, 2026.
  6. [6]Abraar Chaudhry and Katya Scheinberg. Powell-style model-based derivative-free optimization with complexity guarantees. arXiv preprint arXiv:2609.09441, 2026.arxiv.org/abs/2609.09441
  7. [7]Ruobing Chen, Matt Menickelly, and Katya Scheinberg. Stochastic optimization using a trust-region method and random models. Mathematical Programming, 169(2):447–487, 2018.arxiv.org/abs/1504.04231
  8. [8]Y. S. Chow and H. Robbins. On the asymptotic theory of fixed-width sequential confidence intervals for the mean. Annals of Mathematical Statistics, 36:457–462, 1965.
  9. [9]Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009.DOI
  10. [10]S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, 22(1):60–65, 2003.DOI
  11. [11]V. H. de la Peña, M. J. Klass, and T. L. Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Annals of Probability, 32:1902–1933, 2004.
  12. [12]Anjie Ding, Francesco Rinaldi, and Luis Nunes Vicente. Sequential test sampling for stochastic derivative-free optimization. arXiv preprint arXiv:2509.14505, 2025.arxiv.org/abs/2509.14505
  13. [13]Kwassi Joseph Dzahini, Sara Shashaani, and Coralia Cartis. Sample complexity and scalability of adaptive-sampling trust-region methods for zeroth-order stochastic optimization — Part I: common random numbers meet supermartingales. arXiv preprint arXiv:2611.10296, 2026.arxiv.org/abs/2611.10296
  14. [14]Kwassi Joseph Dzahini and Stefan M Wild. Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses. SIAM Journal on Optimization, 34(3):2671–2699, 2024.DOI
  15. [15]M. Ghosh and N. Mukhopadhyay. Consistency and asymptotic efficiency of two-stage and sequential estimation procedures. Sankhyā Series A, 43:220–227, 1981.
  16. [16]M. Ghosh, N. Mukhopadhyay, and P. K. Sen. Sequential Estimation. Wiley, New York, 1997.
  17. [17]Geovany Nunes Grapiglia. Quadratic regularization methods with finite-difference gradient approximations. Computational Optimization and Applications, 85(3):683–703, 2023.DOI
  18. [18]Yunsoo Ha, Sara Shashaani, and Raghu Pasupathy. Complexity of zeroth-and first-order stochastic trust-region algorithms. SIAM Journal on Optimization, 35(3):2098–2127, 2025.arxiv.org/abs/2405.20116
  19. [19]S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257–317, 2020.DOI
  20. [20]Billy Jin, Katya Scheinberg, and Miaolan Xie. Sample complexity analysis for adaptive optimization algorithms with stochastic oracles. Mathematical Programming, 209(1):651–679, 2025.arxiv.org/abs/2303.06838
  21. [21]N. Mukhopadhyay. Sequential point estimation of the mean when the distribution is unspecified. Technical Report 312, University of Minnesota, 1978.DOI
  22. [22]M. J. D. Powell. The NEWUOA software for unconstrained optimization without derivatives. Technical Report DAMTP 2004/NA08, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, UK, 2004.
  23. [23]Francesco Rinaldi, Luis Nunes Vicente, and Damiano Zeffiro. Stochastic trust-region and direct-search methods: A weak tail bound condition and reduced sample sizing. SIAM Journal on Optimization, 34(2):2067–2092, 2024.arxiv.org/abs/2202.11074
  24. [24]H. Robbins. Statistical methods related to the law of the iterated logarithm. Annals of Mathematical Statistics, 41:1397–1409, 1970.
  25. [25]S. Shashaani. Adaptive Sampling Trust-Region Methods for Derivative-Based and Derivative-Free Simulation Optimization Problems. PhD thesis, Purdue University, 2016.
  26. [26]S. Shashaani, F.S. Hashemi, and R. Pasupathy. ASTRO-DF: A class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization. SIAM Journal on Optimization, 28(4):3145–3176, 2018.arxiv.org/abs/1610.06506

Paper details

vlnc:W_j7g9axb2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents