Introduction
We consider unconstrained simulation optimization problems of the form
min x ∈ R d f ( x ) : = E [ F ( x , ξ ) ] = ∫ Ξ F ( x , ξ ) d P ( ξ ) , (1) \min_{x\in\mathbb{R}^{d}} f(x) := \mathbb{E}[F(x,\xi)] = \int_{\Xi} F(x,\xi)\,dP(\xi), \tag*{(1)} x ∈ R d min f ( x ) := E [ F ( x , ξ )] = ∫ Ξ F ( x , ξ ) d P ( ξ ) , (1)
where f : R d → R f:\mathbb{R}^{d}\to\mathbb{R} f : R d → R is smooth, possibly nonconvex and bounded below, and F : R d × Ξ → R F:\mathbb{R}^{d}\times\Xi\to\mathbb{R} F : R d × Ξ → R is observable only through a Monte Carlo oracle: a call at x x x returns F ( x , ξ ) = f ( x ) + E ( x , ξ ) F(x,\xi)=f(x)+E(x,\xi) F ( x , ξ ) = f ( x ) + E ( x , ξ ) for a fresh ξ \xi ξ , with no derivative. The estimator of f ( x ) f(x) f ( x ) from n n n calls and its estimated variance are
F ‾ ( x , n ) = 1 n ∑ j = 1 n F ( x , ξ j ) , σ ^ F 2 ( x , n ) = 1 n ∑ j = 1 n ( 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)} F ( x , n ) = n 1 j = 1 ∑ n F ( x , ξ j ) , σ F 2 ( x , n ) = n 1 j = 1 ∑ n ( F ( x , ξ j ) − F ( x , n ) ) 2 . (2)
The oracle call is the expensive unit, and W ϵ W_{\epsilon} W ϵ 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 ξ 1 , ξ 2 , … of independent replications. Evaluating several points on the same stream means evaluating F ( ⋅ , ξ j ) F(\cdot,\xi_j) F ( ⋅ , ξ j ) at each of them with the same ξ j \xi_j ξ j , j = 1 , … , n j=1,\ldots,n j = 1 , … , 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 { X k } \{X_k\} { X k } , one sequence of sample sizes { N k } \{N_k\} { N k } , and one first hitting time T ϵ : = inf { k : ∥ ∇ f ( X k ) ∥ ≤ ϵ } T_\epsilon:= \inf\{k : \lVert\nabla f(X_k)\rVert\le\epsilon\} T ϵ := inf { k : ∥ ∇ f ( X k )∥ ≤ ϵ } , 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 , or P ( 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}}. E [ T ϵ ] ≤ c ϵ − 2 , or P ( T ϵ ≤ c ϵ − 2 ) ≥ 1 − e − c ′ ϵ − 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 T ϵ 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 ϵ 0 ( ω ) > 0 and a constant R ( ω ) < ∞ R(\omega)<\infty R ( ω ) < ∞ such that T ϵ ( ω ) ≤ R ( ω ) ϵ − 2 T_\epsilon(\omega)\le R(\omega)\epsilon^{-2} T ϵ ( ω ) ≤ R ( ω ) ϵ − 2 for all ϵ ≤ ϵ 0 ( ω ) \epsilon\le\epsilon_0(\omega) ϵ ≤ ϵ 0 ( ω ) . Equivalently, along every deterministic sequence ϵ ℓ ↓ 0 \epsilon_\ell\downarrow0 ϵ ℓ ↓ 0 ,
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)} P ( T ϵ ℓ ϵ ℓ 2 > R infinitely often ) = 0. (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) O ( Δ k ) ; the difference of estimation errors between incumbent and trial point is O ( Δ k 2 ) O(\Delta_k^2) O ( Δ k 2 ) ; the sketch is well aligned with the gradient) is an event E k \mathcal{E}_k E k of iteration k k k . If its failure probability is summable, ∑ k P ( E k c ) < ∞ \sum_k\mathbb{P}(\mathcal{E}_k^c)<\infty ∑ k P ( E k c ) < ∞ , then by the first Borel–Cantelli lemma E k \mathcal{E}_k E k holds for all k ≥ K ( ω ) k\ge K(\omega) k ≥ K ( ω ) on almost every path, for a random, almost surely finite K ( ω ) K(\omega) K ( ω ) . From K ( ω ) K(\omega) K ( ω ) 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) K ( ω ) is finite and, as Section 7.3 shows, has finite moments, but the bound holds only beyond a random threshold ϵ 0 ( ω ) \epsilon_0(\omega) ϵ 0 ( ω ) , and no expected bound follows.
The cost of making failure probabilities summable is paid in two places. The sample size at iteration k k k must be inflated by a slowly growing factor λ k \lambda_k λ k , so that the estimation failure probability is e − c λ k e^{-c\lambda_k} e − c λ k and λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ \lambda_k=\lambda_0(\log(k+2))^{1+\epsilon} λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ suffices, and it is the price of adaptive sampling known from sequential estimation [8 , 16 ] . And the subspace dimension p k p_k p k must grow so that the misalignment probability e − c p k e^{-cp_k} e − c p k is summable; p k p_k p k of order log k \log k log k , capped at d d d , suffices. Section 8 quantifies what happens if one refuses to pay the second price: at a fixed p p p the argument of this paper gives ϵ − 2 O ( 1 / p ) \epsilon^{-2}O(1/p) ϵ − 2 O ( 1/ p ) , where Part I’s per-iteration probability bound gives ϵ − 2 \epsilon^{-2} ϵ − 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} Δ k − 4 to Δ k − 2 \Delta_k^{-2} Δ k − 2 , and the sample complexity from order ϵ − 6 \epsilon^{-6} ϵ − 6 to ϵ − 4 \epsilon^{-4} ϵ − 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}) T ϵ = O ( ϵ − 2 ) and W ϵ = O ~ ( ϵ − 4 ) W_\epsilon= \widetilde{O}(\epsilon^{-4}) W ϵ = O ( ϵ − 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 N k N_k N 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 N k N_k N 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 p p p and misalignment probability β ˉ Q \bar{\beta}_{Q} β ˉ Q below an explicit threshold, the radius satisfies Δ k ≥ θ k − ϱ \Delta_k \ge\theta k^{-\varrho} Δ k ≥ θ k − ϱ eventually with ϱ = O ( 1 / log ( 1 / β ˉ Q ) ) \varrho= O(1/\log(1/\bar{\beta}_{Q})) ϱ = O ( 1/ log ( 1/ β ˉ Q )) , which gives almost sure liminf convergence when ϱ ≤ 1 2 \varrho\le\frac{1}{2} ϱ ≤ 2 1 and T ϵ = O ( ϵ − 2 / ( 1 − 2 ϱ ) ) T_\epsilon= O(\epsilon^{-2/(1-2\varrho)}) T ϵ = O ( ϵ − 2/ ( 1 − 2 ϱ ) ) . The exponent tends to 2 as p p p grows, and p k = O ( log k ) p_k = 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 d d d , p p p 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}) O ( d ϵ − 2 ) iterations, the sketch of [14 ] scaled by d / p \sqrt{d/p} d / p gives O ~ ( d p − 1 ϵ − 2 ) \widetilde{O}(d p^{-1}\epsilon^{-2}) O ( d p − 1 ϵ − 2 ) , and a scale balancing model bias against estimation error gives O ~ ( d p − 1 / 2 ϵ − 2 ) \widetilde{O}(d p^{-1/2}\epsilon^{-2}) O ( d p − 1/2 ϵ − 2 ) . The price of reuse in our bounds is a factor p p p in the sample size per iteration: the accuracy must hold at every point of the p p p -dimensional trust region at once, and the nets that cover it have a number of points exponential in p p p . With p k = O ( log k ) p_k = O(\log k) p k = O ( log k ) this factor is logarithmic; in the full space, p = d p = d p = d , it is a factor d d d . This scale, κ Q ≍ p − 1 / 4 \kappa_Q \asymp p^{-1/4} κ Q ≍ p − 1/4 , is the best over the sketch scale in our bounds and gains a factor p \sqrt{p} 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, κ e d F ≍ p − 1 / 2 \kappa_{\mathrm{edF}} \asymp p^{-1/2} κ edF ≍ p − 1/2 , which costs a factor p \sqrt{p} 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}) O ( ϵ − 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 1 2 \frac{1}{2} 2 1 ; 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 δ > 1 in (28) , Remark 9), the subspace dimension must grow, and nothing is obtained in expectation.
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 β Q is the misalignment probability; here β Q , k \beta_{Q,k} β Q , k is the alignment probability (Assumption 6).
Both routes use Assumptions 1–5, 6(b) and, for the sample complexity bound, 7. The supermartingale route of Part I asks in addition that the conditional probability of a good iteration be bounded below, at every iteration beyond a deterministic index, by a level exceeding one half (its Assumption 2.1(i)), which with its sketch is a misalignment probability below 1 − γ ^ r / π min < 1 2 1-\hat{\gamma}_r/\pi_{\min}<\frac{1}{2} 1 − γ ^ r / π m i n < 2 1 that a fixed p p p must meet; that π ⋆ γ − 2 r + ( 1 − π ⋆ ) γ 2 r < 1 \pi_\star\gamma^{-2r}+(1-\pi_\star)\gamma^{2r}<1 π ⋆ γ − 2 r + ( 1 − π ⋆ ) γ 2 r < 1 (its Assumption 2.2), which couples the expansion factor of the trust region to the reliability of the sketch; and, for its expected sample bound under the logarithmic inflation, a moment condition on S Δ S_\Delta S Δ beyond E [ S Δ ] ≤ ∞ \mathbb{E}[S_\Delta]\leq\infty E [ S Δ ] ≤ ∞ that it assumes rather than derives (its Theorem 6.4). The pathwise route asks none of these when p k p_k p k grows: alignment need only fail summably often, nothing couples γ \gamma γ to the sketch, and no moment of S Δ S_\Delta S Δ enters; the only probabilistic input is the unconditional summability ∑ k P ( U k ) < ∞ \sum_k \mathbb{P}(U_k)<\infty ∑ k P ( U k ) < ∞ . It asks instead for λ k → ∞ \lambda_k\to\infty λ k → ∞ and for p k → ∞ p_k\to\infty p k → ∞ , the latter at the price of Section 8 if refused, and it gives up statements in expectation. It also admits constants that vary with k k k , which the framework of Part I does not, and this is how a growing subspace dimension enters at all.
Notation
Deterministic scalars are lower case (κ \kappa κ , c c c , θ \theta θ , λ \lambda λ , r F r_F r F ), random scalars are upper case (Δ k \Delta_k Δ k , N k N_k N k , T k T_k T k , the burn-in indices K U K_U K U , K A K_A K A , K W K_W K W and the constants R R R , S Δ S_\Delta S Δ below are random). Vectors are bold, random vectors bold upper case (X k \mathbf{X}_k X k ), matrices sans serif (Q k \mathsf{Q}_k Q k ), sets and σ \sigma σ -fields script. Hatted symbols live in the subspace. Constants depending on the subspace dimension are written as functions of p p p , as κ g ( p ) \kappa_g(p) κ g ( p ) , and evaluated at p k p_k p k when used at iteration k k k . We write a ∧ b = min { a , b } a \wedge b = \min\{a,b\} a ∧ b = min { a , b } , a ∨ b = max { a , b } a \vee b = \max\{a,b\} a ∨ b = max { a , b } , { E k i . o . } = lim sup k E k \{E_k\ \mathrm{i.o.}\} = \limsup_k E_k { E k i.o. } = lim sup k E k , and O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) for an order up to a factor polylogarithmic in the argument. All random quantities live on one probability space ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) .
The algorithm
Interpolation on a coordinate design in a subspace
At iteration k k k the method holds an incumbent X k 0 ∈ R d X_k^0 \in\mathbb{R}^d X k 0 ∈ R d , a radius Δ k > 0 \Delta_k > 0 Δ k > 0 , and draws a sketch Q k ∈ R d × p k Q_k \in\mathbb{R}^{d \times p_k} Q k ∈ R d × p k . It searches the affine subspace { X k 0 + Q k s ^ : s ^ ∈ R p k } \{X_k^0 + Q_k\hat{s}: \hat{s} \in\mathbb{R}^{p_k}\} { X k 0 + Q k s ^ : s ^ ∈ R p k } within ∥ s ^ ∥ ≤ Δ k \|\hat{s}\| \le\Delta_k ∥ s ^ ∥ ≤ Δ k , and writes f ^ k ( s ^ ) : = f ( X k 0 + Q k s ^ ) \hat{f}_k(\hat{s}) := f(X_k^0 + Q_k\hat{s}) f ^ k ( s ^ ) := f ( X k 0 + Q k s ^ ) , so that ∇ f ^ k ( s ^ ) = Q k T ∇ f ( X k 0 + Q k s ^ ) \nabla\hat{f}_k(\hat{s}) = Q_k^\mathsf{T}\nabla f(X_k^0 + Q_k\hat{s}) ∇ f ^ k ( s ^ ) = Q k T ∇ f ( X k 0 + Q k s ^ ) . The design is the coordinate design of the subspace,
S ^ k = { 0 p k , ± Δ k e 1 , … , ± Δ k e p k } , X k i : = X k 0 + Q k S ^ k i , i = 0 , 1 , … , 2 p k , (4) \hat{\mathcal{S}}_k = \{0_{p_k}, \pm\Delta_k e^1, \ldots, \pm\Delta_k e^{p_k}\}, \qquad X_k^i := X_k^0 + Q_k\hat{S}_k^i, \qquad i=0,1,\ldots,2p_k, \tag*{(4)} S ^ k = { 0 p k , ± Δ k e 1 , … , ± Δ k e p k } , X k i := X k 0 + Q k S ^ k i , i = 0 , 1 , … , 2 p k , (4)
with S ^ k i = Δ k e i \hat{S}_k^i = \Delta_k e^i S ^ k i = Δ k e i and S ^ k p k + i = − Δ k e i \hat{S}_k^{p_k+i}=-\Delta_k e^i S ^ k p k + i = − Δ k e i for i ∈ { 1 , … , p k } i \in\{1,\ldots,p_k\} i ∈ { 1 , … , p k } . In the ambient space the design points lie within ∥ Q k ∥ Δ k \|Q_k\|\Delta_k ∥ Q k ∥ Δ k of X k 0 X_k^0 X k 0 . The full-space method is Q k = I d Q_k=I_d Q k = I d , p k = d p_k=d p k = d .
The model is quadratic with diagonal Hessian, and it is determined by the 2 p k + 1 2p_k+1 2 p k + 1 estimates at the design points: with F ˉ k i : = F ˉ ( X k i , N k ) \bar{F}_k^i := \bar{F}(X_k^i,N_k) F ˉ k i := F ˉ ( X k i , N k ) ,
[ G ^ k ] i = F ˉ k i − F ˉ k p k + i 2 Δ k , [ H ^ k ] i i = κ H ∧ ( ( − κ H ) ∨ F ˉ k i − 2 F ˉ k 0 + F ˉ k p k + i Δ k 2 ) , i = 1 , … , p k , (5) [\widehat{G}_k]_i = \frac{\bar{F}_k^i-\bar{F}_k^{p_k+i}}{2\Delta_k}, \qquad[\widehat{H}_k]_{ii} = \kappa_H \wedge\left((-\kappa_H)\vee\frac{\bar{F}_k^i-2\bar{F}_k^0+\bar{F}_k^{p_k+i}}{\Delta_k^2}\right), \qquad i=1,\ldots,p_k, \tag*{(5)} [ G k ] i = 2 Δ k F ˉ k i − F ˉ k p k + i , [ H k ] ii = κ H ∧ ( ( − κ H ) ∨ Δ k 2 F ˉ k i − 2 F ˉ k 0 + F ˉ k p k + i ) , i = 1 , … , p k , (5)
and
M ^ k ( s ^ ) = F ˉ k 0 + s ^ T G ^ k + 1 2 s ^ T H ^ k s ^ . (6) \widehat{M}_k(\hat{s})=\bar{F}_k^0+\hat{s}^{\mathsf{T}}\widehat{G}_k+\frac{1}{2}\hat{s}^{\mathsf{T}}\widehat{H}_k\hat{s}. \tag*{(6)} M k ( s ^ ) = F ˉ k 0 + s ^ T G k + 2 1 s ^ T H k s ^ . (6)
The gradient is a central finite difference along the columns of Q k Q_k Q k , and the diagonal Hessian is a second difference truncated to [ − κ H , κ H ] [-\kappa_H,\kappa_H] [ − κ H , κ H ] , that is, each diagonal entry is replaced by the nearest point of that interval, for a constant κ H ≥ 1 \kappa_H \ge1 κ H ≥ 1 , so that ∥ H ^ k ∥ ≤ κ H \|\widehat{H}_k\|\le\kappa_H ∥ H k ∥ ≤ κ H surely. The truncation is a safeguard for inaccurate iterations, on which a second difference of noisy estimates, an estimation error divided by Δ k 2 \Delta_k^2 Δ k 2 , can be arbitrarily large. On the good event of § 4 it changes nothing once κ H ≥ κ L g κ Q 2 + 2 κ e d F \kappa_H \ge\kappa_{Lg}\kappa_Q^2+2\kappa_{edF} κ H ≥ κ Lg κ Q 2 + 2 κ e d F (Lemma 5.5 ), so the model is eventually the plain interpolation model; it replaces the bounded-Hessian assumption of [18 ] . The second difference is taken in subspace coordinates, divided by Δ k 2 \Delta_k^2 Δ k 2 and not by ∥ Q k e i ∥ 2 Δ k 2 \|Q_ke^i\|^2\Delta_k^2 ∥ Q k e i ∥ 2 Δ k 2 , because H ^ k \widehat{H}_k H k approximates Q k T ∇ 2 f Q k Q_k^\mathsf{T}\nabla^2 f Q_k Q k T ∇ 2 f Q k and not ∇ 2 f \nabla^2f ∇ 2 f ; the other normalization makes the estimation part of the Hessian bound grow as the sketch is scaled down and spoils the accounting of § 9 .
One stream, one rule, full reuse
All estimates at iteration k k k use the same replications ξ k , 1 , ξ k , 2 , … \xi_{k,1},\xi_{k,2},\ldots ξ k , 1 , ξ k , 2 , … , and sampling stops at
N k = min { n ∈ N : σ 0 ∨ σ ^ F max ( k , n ) n ≤ κ s Δ k λ k } , σ ^ F max ( k , n ) : = max 0 ≤ i ≤ 2 p k σ ^ F ( X k i , n ) , (7) N_k=\min\left\{n\in\mathbb{N}:\frac{\sigma_0\vee\widehat{\sigma}_F^{\max}(k,n)}{\sqrt{n}}\le\kappa_s\frac{\Delta_k}{\sqrt{\lambda_k}}\right\}, \qquad\widehat{\sigma}_F^{\max}(k,n):=\max_{0\le i\le2p_k}\widehat{\sigma}_F(X_k^i,n), \tag*{(7)} N k = min { n ∈ N : n σ 0 ∨ σ F m a x ( k , n ) ≤ κ s λ k Δ k } , σ F m a x ( k , n ) := 0 ≤ i ≤ 2 p k max σ F ( X k i , n ) , (7)
with λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ λ \lambda_k=\lambda_0(\log(k+2))^{1+\epsilon_\lambda} λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ λ , ϵ λ ∈ ( 0 , 1 ) \epsilon_\lambda\in(0,1) ϵ λ ∈ ( 0 , 1 ) , and constants σ 0 , κ s > 0 \sigma_0,\kappa_s>0 σ 0 , κ s > 0 . The rule compares the largest observed standard error over the design with a threshold set by the algorithm’s own radius; it requires no knowledge of the noise level, no Lipschitz constant and no target accuracy. Since σ 0 ∨ σ ^ F max ≥ σ 0 \sigma_0\vee\widehat{\sigma}_F^{\max}\ge\sigma_0 σ 0 ∨ σ F m a x ≥ σ 0 , any n n n meeting the criterion satisfies
N k ≥ n k : = ⌈ σ 0 2 λ k κ s 2 Δ k 2 ⌉ , (8) N_k\ge n_k:=\left\lceil\frac{\sigma_0^2\lambda_k}{\kappa_s^2\Delta_k^2}\right\rceil, \tag*{(8)} N k ≥ n k := ⌈ κ s 2 Δ k 2 σ 0 2 λ k ⌉ , (8)
a floor that is determined before the first replication of the iteration is drawn. The floor is the only property of the rule that the accuracy analysis uses; what the rule adds to the floor is efficiency, see Remark 6.
The trial point is evaluated on the same replications: F ˉ k s : = F ˉ ( X k s , N k ) \bar{F}_k^s:=\bar{F}(X_k^s,N_k) F ˉ k s := F ˉ ( X k s , N k ) with X k s = X k 0 + Q k S ^ k s X_k^s=X_k^0+Q_k\hat{S}_k^s X k s = X k 0 + Q k S ^ k s , and no further sampling takes place in the iteration. This is what an implementation does, and it is the cheapest of the three schemes of Remark 4 at equal sample sizes: ( 2 p k + 2 ) N k (2p_k+2)N_k ( 2 p k + 2 ) N k calls per iteration. It is also what the existing supermartingale analyses (prior to Part I) exclude, since they require the trial estimates to be accurate conditionally on the σ \sigma σ -field generated by the model, which the trial point depends on [7 , 14 ] , and what the pathwise analysis of [18 ] treated with a pointwise inequality, which § 4.3 revisits.
Algorithm 1 ASTRO-DF in random subspaces with fully reused CRN
Require: x 0 ∈ R d x_0 \in\mathbb{R}^d x 0 ∈ R d ; radii Δ max > Δ 0 > 0 \Delta_{\max} > \Delta_0 > 0 Δ m a x > Δ 0 > 0 ; thresholds η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) , μ > 0 \mu> 0 μ > 0 ; expansion and contraction constants γ i n c > 1 > γ d e c > 0 \gamma_{\mathrm{inc}} > 1 > \gamma_{\mathrm{dec}} > 0 γ inc > 1 > γ dec > 0 ; Hessian clip κ H ≥ 1 \kappa_H \ge1 κ H ≥ 1 ; inflation λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ λ \lambda_k = \lambda_0(\log(k+2))^{1+\epsilon_\lambda} λ k = λ 0 ( log ( k + 2 ) ) 1 + ϵ λ ; sampling constants σ 0 , κ s > 0 \sigma_0,\kappa_s > 0 σ 0 , κ s > 0 ; subspace dimensions { p k } \{p_k\} { p k } .
for k = 0 , 1 , 2 , … k = 0,1,2,\ldots k = 0 , 1 , 2 , … do
Sketch: draw Q k ∈ R d × p k Q_k \in\mathbb{R}^{d\times p_k} Q k ∈ R d × p k independently of the past and of all replications.
Model: evaluate the design points (4) on one stream ξ k , 1 , ξ k , 2 , … \xi_{k,1},\xi_{k,2},\ldots ξ k , 1 , ξ k , 2 , … ; stop at N k N_k N k from (7) ; form G ^ k , H ^ k \widehat{G}_k,\widehat{H}_k G k , H k by (5) and M ^ k \widehat{M}_k M k by (6) .
Subproblem: compute S ^ k ∗ ≈ a r g m i n ∥ s ^ ∥ ≤ Δ k M ^ k ( s ^ ) \widehat{S}_k^* \approx\mathop{\rm argmin}_{\|\widehat{s}\|\leq\Delta_k}\widehat{M}_k(\widehat{s}) S k ∗ ≈ argmin ∥ s ∥ ≤ Δ k M k ( s ) satisfying Assumption 5; set X k s = X k 0 + Q k S ^ k ∗ X_k^s = X_k^0 + Q_k\widehat{S}_k^* X k s = X k 0 + Q k S k ∗ .
Trial evaluation: evaluate X k s X_k^s X k s on ξ k , 1 , … , ξ k , N k \xi_{k,1},\ldots,\xi_{k,N_k} ξ k , 1 , … , ξ k , N k , set F ‾ k s : = F ‾ ( X k s , N k ) \overline{F}_k^s := \overline{F}(X_k^s,N_k) F k s := F ( X k s , N k ) and
ρ ^ k = F ‾ k 0 − F ‾ k s M ^ k ( 0 ) − M ^ k ( S ^ k ∗ ) . \widehat{\rho}_k =
\frac{\overline{F}_k^0-\overline{F}_k^s}
{\widehat{M}_k(0)-\widehat{M}_k(\widehat{S}_k^*)}. ρ k = M k ( 0 ) − M k ( S k ∗ ) F k 0 − F k s .
Update: ( X k + 1 0 , Δ k + 1 ) = ( X k s , γ i n c Δ k ∧ Δ max ) (X_{k+1}^0,\Delta_{k+1}) = (X_k^s,\gamma_{\mathrm{inc}}\Delta_k \wedge\Delta_{\max}) ( X k + 1 0 , Δ k + 1 ) = ( X k s , γ inc Δ k ∧ Δ m a x ) if ρ ^ k ≥ η \widehat{\rho}_k \geq\eta ρ k ≥ η and μ ∥ G ^ k ∥ ≥ Δ k \mu\|\widehat{G}_k\| \geq\Delta_k μ ∥ G k ∥ ≥ Δ k (success); otherwise ( X k 0 , γ d e c Δ k ) (X_k^0,\gamma_{\mathrm{dec}}\Delta_k) ( X k 0 , γ dec Δ k ) (failure).
end for
Filtrations
Let F k − 1 \mathcal{F}_{k-1} F k − 1 be the σ \sigma σ -field generated by everything determined by the end of iteration k − 1 k-1 k − 1 , so that X k 0 X_k^0 X k 0 and Δ k \Delta_k Δ k are F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable, and set
F k − 1 Q : = F k − 1 ∨ σ ( Q k ) , G k , n : = F k − 1 Q ∨ σ ( ξ k , 1 , … , ξ k , n ) , G k , 0 = F k − 1 Q , (9) \mathcal{F}_{k-1}^Q := \mathcal{F}_{k-1} \vee\sigma(Q_k), \qquad
\mathcal{G}_{k,n} := \mathcal{F}_{k-1}^Q \vee\sigma(\xi_{k,1},\ldots,\xi_{k,n}), \qquad
\mathcal{G}_{k,0} = \mathcal{F}_{k-1}^Q, \tag*{(9)} F k − 1 Q := F k − 1 ∨ σ ( Q k ) , G k , n := F k − 1 Q ∨ σ ( ξ k , 1 , … , ξ k , n ) , G k , 0 = F k − 1 Q , (9)
with F k = G k , N k \mathcal{F}_k = \mathcal{G}_{k,N_k} F k = G k , N k . The sketch, the design points and the alignment event of Assumption 6 are F k − 1 Q \mathcal{F}_{k-1}^Q F k − 1 Q -measurable; the model, the step, the trial point and ρ ^ k \widehat{\rho}_k ρ k are G k , N k \mathcal{G}_{k,N_k} G k , N k -measurable. No σ \sigma σ -field generated by the model appears anywhere in the analysis, and this is not an accident: under reuse the summands of the trial estimate are not centered conditionally on the replications already drawn, so no accuracy statement conditional on the model is available, and the analysis must be organized so as never to need one.
The primitive object
Common random numbers act on the paired increment
D ( x , y ; ξ ) : = ( F ( y , ξ ) − f ( y ) ) − ( F ( x , ξ ) − f ( x ) ) , E ξ [ D ] = 0 , (10) D(x,y;\xi) := (F(y,\xi)-f(y))-(F(x,\xi)-f(x)), \qquad\mathbb{E}_{\xi}[D] = 0, \tag*{(10)} D ( x , y ; ξ ) := ( F ( y , ξ ) − f ( y )) − ( F ( x , ξ ) − f ( x )) , E ξ [ D ] = 0 , (10)
and for ∥ s ^ ∥ ≤ Δ k \|\widehat{s}\| \leq\Delta_k ∥ s ∥ ≤ Δ k we write
D ‾ k ( s ^ , n ) : = 1 n ∑ j = 1 n D ( X k 0 , X k 0 + Q k s ^ ; ξ k , j ) , (11) \overline{D}_k(\widehat{s},n) := \frac{1}{n}\sum_{j=1}^{n}D(X_k^0,X_k^0+Q_k\widehat{s};\xi_{k,j}), \tag*{(11)} D k ( s , n ) := n 1 j = 1 ∑ n D ( X k 0 , X k 0 + Q k s ; ξ k , j ) , (11)
so that D ‾ k ( S ^ k i , N k ) = E ‾ k i − E ‾ k 0 \overline{D}_k(\widehat{S}_k^i,N_k)=\overline{E}_k^i-\overline{E}_k^0 D k ( S k i , N k ) = E k i − E k 0 at a design point and D ‾ k ( S ^ k ∗ , N k ) = E ‾ k s − E ‾ k 0 \overline{D}_k(\widehat{S}_k^*,N_k)=\overline{E}_k^s-\overline{E}_k^0 D k ( S k ∗ , N k ) = E k s − E k 0 at the trial point, where E ‾ k i : = F ‾ k i − f ( X k i ) \overline{E}_k^i:=\overline{F}_k^i-f(X_k^i) E k i := F k i − f ( X k i ) . The identity
D ( x , y ; ξ ) − D ( x , y ′ ; ξ ) = D ( y ′ , y ; ξ ) (12) D(x,y;\xi)-D(x,y';\xi)=D(y',y;\xi) \tag*{(12)} D ( x , y ; ξ ) − D ( x , y ′ ; ξ ) = D ( y ′ , y ; ξ ) (12)
says that increments of s ^ ↦ D ‾ k ( s ^ , n ) \widehat{s}\mapsto\overline{D}_k(\widehat{s},n) s ↦ D k ( s , n ) are themselves paired increments; it is what makes the process chainable.
Assumptions
We use the final assumptions of Part I, and we state them in full so that this part can be read alone.
Assumption 1 (smooth f f f ). f f f is continuously differentiable on R d \mathbb{R}^d R d and bounded below by f ∗ : = inf x f ( x ) > − ∞ f^* := \inf_x f(x) > -\infty f ∗ := inf x f ( x ) > − ∞ , and ∇ f \nabla f ∇ f is κ L g \kappa_{L_g} κ L g -Lipschitz.
Assumption 2 (finite variance). For all x ∈ R d x \in\mathbb{R}^d x ∈ R d , σ F 2 ( x ) : = Var ( F ( x , ξ ) ) ≤ v F < ∞ \sigma_F^2(x) := \operatorname{Var}(F(x,\xi)) \leq v_F < \infty σ F 2 ( x ) := Var ( F ( x , ξ )) ≤ v F < ∞ .
Assumption 3 (Bernstein condition on the paired increment). There are constants b D , σ D > 0 b_D,\sigma_D > 0 b D , σ D > 0 such that for all x , y ∈ R d x,y \in\mathbb{R}^d x , y ∈ R d with ∥ y − x ∥ ≤ κ Q Δ max \|y-x\| \leq\kappa_Q\Delta_{\max} ∥ y − x ∥ ≤ κ Q Δ m a x and every integer m ≥ 2 m \geq2 m ≥ 2 ,
E [ ∣ D ( x , y ; ξ ) ∣ m ] ≤ m ! 2 ( b D ∥ y − x ∥ ) m − 2 ( σ D ∥ y − x ∥ ) 2 . (13) \mathbb{E}\left[|D(x,y;\xi)|^m\right] \leq\frac{m!}{2}(b_D\|y-x\|)^{m-2}(\sigma_D\|y-x\|)^2. \tag*{(13)} E [ ∣ D ( x , y ; ξ ) ∣ m ] ≤ 2 m ! ( b D ∥ y − x ∥ ) m − 2 ( σ D ∥ y − x ∥ ) 2 . (13)
Assumption 4 (continuous sample paths). The sample paths x ↦ F ( x , ξ ) x \mapsto F(x,\xi) x ↦ F ( x , ξ ) are continuous almost surely.
Assumption 5 (Cauchy decrease in the subproblem). For some κ f c d ∈ ( 0 , 1 ] \kappa_{\mathrm{fcd}}\in(0,1] κ fcd ∈ ( 0 , 1 ] and all k k k ,
M ^ k ( 0 ) − M ^ k ( S ^ k ∗ ) ≥ 1 2 κ f c d ∥ G ^ k ∥ ( ∥ G ^ k ∥ ∥ H ^ k ∥ ∨ 1 ∧ Δ k ) . \widehat{M}_k(0)-\widehat{M}_k(\widehat{S}_k^*)\ge\tfrac{1}{2}\kappa_{\mathrm{fcd}}\lVert\widehat{G}_k\rVert\left(\frac{\lVert\widehat{G}_k\rVert}{\lVert\widehat{H}_k\rVert\vee1}\wedge\Delta_k\right). M k ( 0 ) − M k ( S k ∗ ) ≥ 2 1 κ fcd ∥ G k ∥ ( ∥ H k ∥ ∨ 1 ∥ G k ∥ ∧ Δ k ) .
Assumption 6 (well-aligned sketches). The matrices { Q k } \{Q_k\} { Q k } are drawn independently of { ξ k , j } \{\xi_{k,j}\} { ξ k , j } and satisfy, for constants α Q ∈ ( 0 , 1 ] \alpha_Q\in(0,1] α Q ∈ ( 0 , 1 ] , κ Q < ∞ \kappa_Q<\infty κ Q < ∞ and a deterministic sequence β Q , k ∈ [ 0 , 1 ] \beta_{Q,k}\in[0,1] β Q , k ∈ [ 0 , 1 ] :
(a) P ( ∥ Q k V ∥ ≥ α Q ∥ V ∥ ∣ F k − 1 ) ≥ β Q , k \mathbb{P}\left(\lVert Q_kV\rVert\ge\alpha_Q\lVert V\rVert\mid\mathcal{F}_{k-1}\right)\ge\beta_{Q,k} P ( ∥ Q k V ∥ ≥ α Q ∥ V ∥ ∣ F k − 1 ) ≥ β Q , k almost surely, for every F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable random vector V ∈ R d V\in\mathbb{R}^d V ∈ R d ;
(b) ∥ Q k ∥ ≤ κ Q \lVert Q_k\rVert\le\kappa_Q ∥ Q k ∥ ≤ κ Q almost surely.
We write
A k : = { ∥ Q k ∇ f ( X k 0 ) ∥ ≥ α Q ∥ ∇ f ( X k 0 ) ∥ } ∈ F k − 1 Q A_k:=\{\lVert Q_k\nabla f(X_k^0)\rVert\ge\alpha_Q\lVert\nabla f(X_k^0)\rVert\}\in\mathcal{F}_{k-1}^Q A k := {∥ Q k ∇ f ( X k 0 )∥ ≥ α Q ∥ ∇ f ( X k 0 )∥} ∈ F k − 1 Q
and β ‾ Q : = sup k ( 1 − β Q , k ) \overline{\beta}_Q:=\sup_k(1-\beta_{Q,k}) β Q := sup k ( 1 − β Q , k ) for the misalignment probability.
Part (a) is stated conditionally, and for F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable V V V , because it is applied to ∇ f ( X k 0 ) \nabla f(X_k^0) ∇ f ( X k 0 ) , which depends on Q 0 , … , Q k − 1 Q_0,\ldots,Q_{k-1} Q 0 , … , Q k − 1 ; the conditional form follows from the unconditional one for fixed v v v because Q k Q_k Q k is independent of F k − 1 \mathcal{F}_{k-1} F k − 1 . Note that β Q , k \beta_{Q,k} β Q , k is a success probability, whereas Part I and [14 ] parametrize by the failure probability. The pathwise route uses (a) in one of two regimes: ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ , achieved by a growing subspace dimension (Sections 6–7), or β ‾ Q < 1 \overline{\beta}_Q<1 β Q < 1 fixed (Section 8). Which ensembles satisfy (a) and (b), and with which constants, is the subject of Section 3.1.
Assumption 7 (fourth moment; used for the sample complexity bound only). There is c 4 < ∞ c_4<\infty c 4 < ∞ with
sup x ∈ R d E [ ∣ F ( x , ξ ) − f ( x ) ∣ 4 ] ≤ c 4 . \sup_{x\in\mathbb{R}^d}\mathbb{E}[|F(x,\xi)-f(x)|^4]\le c_4. x ∈ R d sup E [ ∣ F ( x , ξ ) − f ( x ) ∣ 4 ] ≤ c 4 .
Sketch ensembles
The analysis uses the sketch only through Assumption 6. The design is the coordinate design of the subspace, that is, the points X k 0 ± Δ k Q k e ^ i X_k^0\pm\Delta_kQ_k\widehat{e}^i X k 0 ± Δ k Q k e i along the columns of Q k Q_k Q k , and nothing is assumed about those columns beyond (a) and (b). Two consequences deserve to be made explicit. First, (a), (b) and the constants κ g , κ a \kappa_g,\kappa_a κ g , κ a below are invariant under rotations within the subspace (the iterates are not, since the coordinate design turns with the basis): replacing Q k Q_k Q k by Q k V k Q_kV_k Q k V k for an F k − 1 Q \mathcal{F}_{k-1}^Q F k − 1 Q -measurable orthogonal V k ∈ R p k × p k V_k\in\mathbb{R}^{p_k\times p_k} V k ∈ R p k × p k composes f ^ k \widehat{f}_k f k with a rotation and changes neither (a) nor (b); the factor p \sqrt{p} p in the gradient error (Lemma 5.2) comes from the 2 p 2p 2 p rows of the design matrix in subspace coordinates and is rotation invariant. Second, sketches with orthonormal columns are a special case, and the convenient one.
Proposition 3.1 (orthonormal columns). Let U k ∈ R d × p k U_k \in\mathbb{R}^{d\times p_k} U k ∈ R d × p k consist of the first p k p_k p k columns of a matrix drawn from the Haar measure on the orthogonal group O ( d ) \mathrm{O}(d) O ( d ) , independently of F k − 1 \mathcal{F}_{k-1} F k − 1 and of all replications, and let Q k : = c U k Q_k := cU_k Q k := c U k for a constant c > 0 c > 0 c > 0 . Then ∥ Q k ∥ = c \lVert Q_k\rVert= c ∥ Q k ∥ = c surely, so (b) holds with κ Q = c \kappa_Q = c κ Q = c . Moreover, for every α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and every F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable V V V , almost surely,
P ( ∥ Q k V ∥ ≥ c ( 1 − α ) p k / d ∥ V ∥ | F k − 1 ) ≥ { 1 − e − p k α 2 / 4 , p k < d , 1 , p k = d . (14) \mathbb{P}\left(\left\lVert Q_kV\right\rVert\ge c\sqrt{(1-\alpha)p_k/d}\left\lVert V\right\rVert\,\middle|\, \mathcal{F}_{k-1}\right) \ge
\begin{cases}
1-e^{-p_k\alpha^2/4}, & p_k<d,\\
1, & p_k=d.
\end{cases} \tag*{(14)} P ( ∥ Q k V ∥ ≥ c ( 1 − α ) p k / d ∥ V ∥ F k − 1 ) ≥ { 1 − e − p k α 2 /4 , 1 , p k < d , p k = d . (14) Consequently, if p k ≥ p 0 p_k \ge p_0 p k ≥ p 0 for all k k k and c ≤ d / ( ( 1 − α ) p 0 ) c \le\sqrt{d/((1-\alpha)p_0)} c ≤ d / (( 1 − α ) p 0 ) , then (a) holds with α Q = c ( 1 − α ) p 0 / d ∈ ( 0 , 1 ] \alpha_Q = c\sqrt{(1-\alpha)p_0/d} \in(0,1] α Q = c ( 1 − α ) p 0 / d ∈ ( 0 , 1 ] , with 1 − β Q , k = e − p k α 2 / 4 1-\beta_{Q,k}=e^{-p_k\alpha^2/4} 1 − β Q , k = e − p k α 2 /4 when p k < d p_k<d p k < d and 1 − β Q , k = 0 1-\beta_{Q,k}=0 1 − β Q , k = 0 when p k = d p_k=d p k = d .
Proof. Orthonormality of the columns gives ∥ Q k s ^ ∥ = c ∥ s ^ ∥ \lVert Q_k\hat{s}\rVert= c\lVert\hat{s}\rVert ∥ Q k s ^ ∥ = c ∥ s ^ ∥ for every s ^ \hat{s} s ^ , hence ∥ Q k ∥ = c \lVert Q_k\rVert= c ∥ Q k ∥ = c . Fix α \alpha α and V V V . On { V = 0 } \{V=0\} { V = 0 } the event in (14) holds trivially. If p k = d p_k=d p k = d , U k U_k U k is orthogonal, so ∥ Q k V ∥ = c ∥ V ∥ \lVert Q_kV\rVert= c\lVert V\rVert ∥ Q k V ∥ = c ∥ V ∥ and the event holds surely. Let p k < d p_k<d p k < d . Since U k U_k U k is independent of F k − 1 \mathcal{F}_{k-1} F k − 1 and V V V is F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable, the conditional probability in (14) equals h ( V ) h(V) h ( V ) with
h ( v ) : = P ( ∥ U k T v ∥ 2 ≥ ( 1 − α ) ( p k / d ) ∥ v ∥ 2 ) . h(v):=\mathbb{P}\left(\lVert U_k^{\mathsf{T}}v\rVert^2 \ge(1-\alpha)(p_k/d)\lVert v\rVert^2\right). h ( v ) := P ( ∥ U k T v ∥ 2 ≥ ( 1 − α ) ( p k / d ) ∥ v ∥ 2 ) .
for deterministic v v v . For v ≠ 0 v\ne0 v = 0 , rotation invariance of the Haar measure shows that ∥ U k T v ∥ 2 / ∥ v ∥ 2 \lVert U_k^{\mathsf{T}}v\rVert^2/\lVert v\rVert^2 ∥ U k T v ∥ 2 / ∥ v ∥ 2 has the law of the squared norm of the first p k p_k p k coordinates of a uniformly distributed point on the unit sphere of R d \mathbb{R}^d R d , and [10 Lemma 2.2] gives
1 − h ( v ) ≤ exp ( p k 2 ( α + log ( 1 − α ) ) ) ≤ e − p k α 2 / 4 , 1-h(v)\le\exp\left(\frac{p_k}{2}\left(\alpha+\log(1-\alpha)\right)\right)\le e^{-p_k\alpha^2/4}, 1 − h ( v ) ≤ exp ( 2 p k ( α + log ( 1 − α ) ) ) ≤ e − p k α 2 /4 ,
because log ( 1 − α ) ≤ − α − α 2 / 2 \log(1-\alpha)\le-\alpha-\alpha^2/2 log ( 1 − α ) ≤ − α − α 2 /2 . This proves (14) . Finally, p k ≥ p 0 p_k\ge p_0 p k ≥ p 0 , so the event in (14) is contained in { ∥ Q k V ∥ ≥ c ( 1 − α ) p 0 / d ∥ V ∥ } \{\lVert Q_kV\rVert\ge c\sqrt{(1-\alpha)p_0/d}\lVert V\rVert\} {∥ Q k V ∥ ≥ c ( 1 − α ) p 0 / d ∥ V ∥} , which is (a) with the stated constants.
We now make three remarks:
Proposition 3.1 makes (b) hold surely ; for a Gaussian Johnson–Lindenstrauss transform ∥ Q k ∥ \lVert Q_k\rVert ∥ Q k ∥ is unbounded and (b) holds only with high probability, so the orthonormal construction is the one for which the analysis applies without a further union bound. Hashing transforms satisfy (b) surely as well [5 ] .
The design points then lie at exact distance c Δ k c\Delta_k c Δ k from X k 0 X_k^0 X k 0 , and f ^ k \hat{f}_k f ^ k is f f f restricted to a p k p_k p k -plane and dilated by c c c .
The ensemble-intrinsic quantity is κ Q 2 / α Q 2 ≍ d / p \kappa_Q^2/\alpha_Q^2\asymp d/p κ Q 2 / α Q 2 ≍ d / p : for orthonormal columns κ Q = c \kappa_Q=c κ Q = c and α Q ≍ c p / d \alpha_Q\asymp c\sqrt{p/d} α Q ≍ c p / d , and for a Gaussian or hashing transform S T ∈ R d × p S^{\mathsf{T}}\in\mathbb{R}^{d\times p} S T ∈ R d × p one has κ Q ≍ c d / p \kappa_Q\asymp c\sqrt{d/p} κ Q ≍ c d / p and α Q ≍ c \alpha_Q\asymp c α Q ≍ c [5 ] . The two ensembles enter the analysis through this quantity alone, and the remaining freedom is the scale c c c . The next proposition says what that freedom is.
Proposition 3.2 (rescaling the sketch is a reparametrization). Fix c > 0 c>0 c > 0 . Run Algorithm 1 once with sketches { Q k } \{Q_k\} { Q k } and parameters ( Δ 0 , Δ max , μ , κ s , κ H ) (\Delta_0,\Delta_{\max},\mu,\kappa_s,\kappa_H) ( Δ 0 , Δ m a x , μ , κ s , κ H ) , and once with sketches { c Q k } \{cQ_k\} { c Q k } , the same replications, and parameters
( Δ 0 / c , Δ max / c , μ / c 2 , c κ s , c 2 κ H ) , (\Delta_0/c,\ \Delta_{\max}/c,\ \mu/c^2,\ c\kappa_s,\ c^2\kappa_H), ( Δ 0 / c , Δ m a x / c , μ / c 2 , c κ s , c 2 κ H ) , and a subproblem solver that commutes with dilation of the subspace coordinates (the exact minimizer, the Cauchy point, dogleg and truncated CG do). The two runs produce the same iterates X k 0 X_k^0 X k 0 , trial points X k s X_k^s X k s , sample sizes N k N_k N k , ratios ρ ^ k \hat{\rho}_k ρ ^ k and success indicators for every k k k , and their radii satisfy Δ k ′ = Δ k / c \Delta'_k=\Delta_k/c Δ k ′ = Δ k / c . Moreover the event u k u_k u k of (20) for the second run with accuracy constant c 2 κ e d F c^2\kappa_{\mathrm{ed}F} c 2 κ ed F is the event u k u_k u k of the first run with constant κ e d F \kappa_{\mathrm{ed}F} κ ed F .
Proof. Induction on k k k , with primes for the second run and Δ 0 ′ = Δ 0 / c \Delta'_0=\Delta_0/c Δ 0 ′ = Δ 0 / c . With Δ k ′ = Δ k / c \Delta'_k=\Delta_k/c Δ k ′ = Δ k / c the design points coincide, X k 0 ± Δ k ′ ( c Q k ) e ^ i = X k 0 ± Δ k Q k e ^ i X_k^0\pm\Delta'_k(cQ_k)\hat{e}^i=X_k^0\pm\Delta_kQ_k\hat{e}^i X k 0 ± Δ k ′ ( c Q k ) e ^ i = X k 0 ± Δ k Q k e ^ i , so the estimates coincide; the rule (7) reads
σ ^ / n ≤ c κ s Δ k ′ / λ k = κ s Δ k / λ k , \hat{\sigma}/\sqrt{n}\le c\kappa_s\Delta'_k/\sqrt{\lambda_k}=\kappa_s\Delta_k/\sqrt{\lambda_k}, σ ^ / n ≤ c κ s Δ k ′ / λ k = κ s Δ k / λ k ,
so N k ′ = N k N'_k=N_k N k ′ = N k . By (5) , G ^ k ′ = c G ^ k \hat{G}'_k=c\hat{G}_k G ^ k ′ = c G ^ k and the unclipped second differences scale by c 2 c^2 c 2 , which the clip level c 2 κ H c^2\kappa_H c 2 κ H preserves; hence M ^ k ′ ( s ^ ′ ) = M ^ k ( c s ^ ′ ) \hat{M}'_k(\hat{s}')=\hat{M}_k(c\hat{s}') M ^ k ′ ( s ^ ′ ) = M ^ k ( c s ^ ′ ) , minimizing over ∥ s ^ ′ ∥ ≤ Δ k ′ \lVert\hat{s}'\rVert\le\Delta'_k ∥ s ^ ′ ∥ ≤ Δ k ′ is minimizing M ^ k \hat{M}_k M ^ k over ∥ s ^ ∥ ≤ Δ k \lVert\hat{s}\rVert\le\Delta_k ∥ s ^ ∥ ≤ Δ k with s ^ = c s ^ ′ \hat{s}=c\hat{s}' s ^ = c s ^ ′ , so the trial points coincide, and Assumption 5 holds in the second run with κ H \kappa_H κ H read as c 2 κ H ∨ 1 c^2\kappa_H\vee1 c 2 κ H ∨ 1 . The ratios coincide, and ( μ / c 2 ) ∥ G ~ k ′ ∥ ≥ Δ k ′ (\mu/c^2)\lVert\widetilde{G}'_k\rVert\ge\Delta'_k ( μ / c 2 ) ∥ G k ′ ∥ ≥ Δ k ′ is μ ∥ G ~ k ∥ ≥ Δ k \mu\lVert\widetilde{G}_k\rVert\ge\Delta_k μ ∥ G k ∥ ≥ Δ k . Both runs take the same decision and Δ k + 1 ′ = Δ k + 1 / c \Delta'_{k+1}=\Delta_{k+1}/c Δ k + 1 ′ = Δ k + 1 / c since Δ max ′ = Δ max / c \Delta'_{\max}=\Delta_{\max}/c Δ m a x ′ = Δ m a x / c . Finally
sup ∥ s ^ ′ ∥ ≤ Δ k ′ ∣ D ‾ k ′ ( s ^ ′ , N k ) ∣ = sup ∥ s ^ ∥ ≤ Δ k ∣ D ‾ k ( s ^ , N k ) ∣ \sup_{\lVert\widehat{s}'\rVert\le\Delta'_k}\left|\overline{D}'_k(\widehat{s}',N_k)\right|
=
\sup_{\lVert\widehat{s}\rVert\le\Delta_k}\left|\overline{D}_k(\widehat{s},N_k)\right| ∥ s ′ ∥ ≤ Δ k ′ sup D k ′ ( s ′ , N k ) = ∥ s ∥ ≤ Δ k sup D k ( s , N k )
while c 2 κ e d F Δ k ′ 2 = κ e d F Δ k 2 c^2\kappa_{\mathrm{ed}F}\Delta_k'^2=\kappa_{\mathrm{ed}F}\Delta_k^2 c 2 κ ed F Δ k ′2 = κ ed F Δ k 2 .
The proposition is elementary, but it shows how the rescaling of [5 ] is to be read. Passing from S T S^T S T to S T / d S^T/\sqrt{d} S T / d improves the evaluation bound by a factor of order d / p d/p d / p , from O ( d 2 ϵ − 2 ) O(d^2\epsilon^{-2}) O ( d 2 ϵ − 2 ) to O ( p d ϵ − 2 ) O(pd\epsilon^{-2}) O ( p d ϵ − 2 ) in the accounting of Table 3, and the improvement is obtained with the trust-region, criticality and Hessian-bound parameters held fixed in subspace coordinates; by the proposition this is the same as running the unscaled algorithm with an ambient trust region smaller by d \sqrt{d} d , a criticality constant μ \mu μ smaller by d d d and a Hessian bound larger by d d d . Neither reading is wrong, but a table of complexity against sketch scale is a table over parametrizations, and it is meaningful based on which parameters are held fixed. We follow [5 ] and Part I and hold ( Δ 0 , Δ max , μ , κ s , κ H , κ e d F ) (\Delta_0,\Delta_{\max},\mu,\kappa_s,\kappa_H,\kappa_{\mathrm{ed}F}) ( Δ 0 , Δ m a x , μ , κ s , κ H , κ ed F ) fixed in subspace coordinates; § 9 is written under that convention. What pins the scale in the bounds is the additive term coming from μ − 1 \mu^{-1} μ − 1 and from the floor κ H ≥ 1 \kappa_H\ge1 κ H ≥ 1 , which do not rescale.
Estimation error at a stopping-time sample size
This section contains the probabilistic content concerning the estimates. It has four parts: the sample size is an almost surely finite stopping time (§ 4.1 ); a Bernstein inequality holds at that stopping time by optional stopping (§ 4.2 ); the pointwise route of [18 ] has two steps that read differently from the stopping-time viewpoint (§ 4.3 ); and the bound is made uniform over the trust region, which is what admits reuse and what Borel–Cantelli then turns into an eventual statement (§ 4.4 ).
The sample size is a finite stopping time
Lemma 4.1 (freezing). Conditionally on F k − 1 Q \mathcal{F}^{Q}_{k-1} F k − 1 Q , the radius Δ k \Delta_k Δ k , the sketch Q k Q_k Q k , the design points { X k i } i ≤ 2 p k \{X_k^i\}_{i\le2p_k} { X k i } i ≤ 2 p k and the floor n k n_k n k are fixed, and the replications ξ k , 1 , ξ k , 2 , … \xi_{k,1},\xi_{k,2},\ldots ξ k , 1 , ξ k , 2 , … are i.i.d. with the law of ξ \xi ξ . In particular, for each i i i , { F ( X k i , ξ k , j ) } j ≥ 1 \{F(X_k^i,\xi_{k,j})\}_{j\ge1} { F ( X k i , ξ k , j ) } j ≥ 1 are i.i.d. under the conditional law with mean f ( X k i ) f(X_k^i) f ( X k i ) and variance σ F 2 ( X k i ) ≤ v F \sigma_F^2(X_k^i)\le v_F σ F 2 ( X k i ) ≤ v F .
Proof. The design points are F k − 1 Q \mathcal{F}^{Q}_{k-1} F k − 1 Q -measurable, and σ ( ξ k , 1 , ξ k , 2 , … ) \sigma(\xi_{k,1},\xi_{k,2},\ldots) σ ( ξ k , 1 , ξ k , 2 , … ) is independent of F k − 1 Q \mathcal{F}^{Q}_{k-1} F k − 1 Q because the replications of iteration k k k are fresh. The conditional law of a family independent of a σ \sigma σ -field is its unconditional law.
Proposition 4.2 (the sample size is a finite stopping time). Under Assumption 2, N k N_k N k is a stopping time with respect to { G k , n } n ≥ 0 \{\mathcal{G}_{k,n}\}_{n\ge0} { G k , n } n ≥ 0 , satisfies N k ≥ n k N_k\ge n_k N k ≥ n k with n k n_k n k as in (8), and P ( ⋂ k { N k < ∞ } ) = 1 \mathbb{P}\left(\bigcap_k\{N_k<\infty\}\right)=1 P ( ⋂ k { N k < ∞ } ) = 1 .
Proof. For each n n n the criterion in (7) is a function of Δ k \Delta_k Δ k , λ k \lambda_k λ k , the design points and ξ k , 1 , … , ξ k , n \xi_{k,1},\ldots,\xi_{k,n} ξ k , 1 , … , ξ k , n , so { N k ≤ n } ∈ G k , n \{N_k\le n\}\in\mathcal{G}_{k,n} { N k ≤ n } ∈ G k , n . The floor is (8). For finiteness, fix k k k and argue under the conditional law given F k − 1 Q \mathcal{F}^{Q}_{k-1} F k − 1 Q of Lemma 4.1: the ordinary strong law of large numbers gives σ ^ F ( X k i , n ) → σ F ( X k i ) \widehat{\sigma}_F(X_k^i,n)\to\sigma_F(X_k^i) σ F ( X k i , n ) → σ F ( X k i ) as n → ∞ n\to\infty n → ∞ for each of the 2 p k + 1 2p_k+1 2 p k + 1 indices, and a maximum over finitely many almost surely convergent sequences converges, so
σ 0 ∨ σ ^ F max ( k , n ) → σ 0 ∨ max i σ F ( X k i ) ≤ σ 0 ∨ v F < ∞ . \sigma_0\vee\widehat{\sigma}^{\max}_F(k,n)\to\sigma_0\vee\max_i\sigma_F(X_k^i)\le\sigma_0\vee\sqrt{v_F}<\infty. σ 0 ∨ σ F m a x ( k , n ) → σ 0 ∨ i max σ F ( X k i ) ≤ σ 0 ∨ v F < ∞.
The left side of the criterion tends to zero while the right side is a fixed positive number, so the criterion is met for all large n n n and N k < ∞ N_k<\infty N k < ∞ under the conditional law; integrating gives P ( N k < ∞ ) = 1 \mathbb{P}(N_k<\infty)=1 P ( N k < ∞ ) = 1 , and a countable intersection of almost sure events is almost sure.
Finiteness matters for two reasons beyond bookkeeping. The estimates F ‾ ( X k i , N k ) \overline{F}(X_k^i,N_k) F ( X k i , N k ) presuppose a finite N k N_k N k , so without the proposition the algorithm might, with positive probability, sample forever and never reach the subproblem. And the optional stopping argument of the next subsection is an argument about L N k L_{N_k} L N k , which exists only when N k < ∞ N_k<\infty N k < ∞ ; this is the point at which the present route uses finiteness explicitly, see § 4.3 . The conditional strong law of Majerek, Nowak and Zięba used in [14 ] is not needed: the freezing lemma makes the replications i.i.d. under the conditional law, and the ordinary strong law applies. The rule (7) is, conditionally, a purely sequential rule of Chow–Robbins type [8 ] , and its finiteness and moments are classical [15 , 16 , 21 , 25 ] ; only the finiteness is used here.
Bernstein's inequality at the stopping time, by optional stopping
Lemma 4.3 (stopped Bernstein inequality). Let { G j } j ≥ 0 \{\mathcal{G}_j\}_{j\ge0} { G j } j ≥ 0 be a filtration and { Z j } j ≥ 1 \{Z_j\}_{j\ge1} { Z j } j ≥ 1 be adapted to it (Z j Z_j Z j is G j \mathcal{G}_j G j -measurable) with E [ Z j ∣ G j − 1 ] = 0 \mathbb{E}[Z_j \mid\mathcal{G}_{j-1}] = 0 E [ Z j ∣ G j − 1 ] = 0 and, for every integer m ≥ 2 m \ge2 m ≥ 2 ,
E [ ∣ Z j ∣ m ∣ G j − 1 ] ≤ m ! 2 B m − 2 V 2 almost surely, (15) \mathbb{E}\left[|Z_j|^m \mid\mathcal{G}_{j-1}\right] \le\frac{m!}{2}B^{m-2}V^2 \quad\text{almost surely,} \tag*{(15)} E [ ∣ Z j ∣ m ∣ G j − 1 ] ≤ 2 m ! B m − 2 V 2 almost surely, (15) with B , V > 0 B,V > 0 B , V > 0 G 0 \mathcal{G}_0 G 0 -measurable. Let A > 0 A > 0 A > 0 and a positive integer N \mathfrak{N} N be G 0 \mathcal{G}_0 G 0 -measurable, and let N N N be a stopping time for { G j } \{\mathcal{G}_j\} { G j } with N ≤ N < ∞ \mathfrak{N} \le N < \infty N ≤ N < ∞ almost surely. Then, almost surely,
P ( 1 N ∣ ∑ j = 1 N Z j ∣ ≥ A | G 0 ) ≤ 2 exp ( − N A 2 2 ( V 2 + B A ) ) . (16) \mathbb{P}\left(\frac{1}{N}\left|\sum_{j=1}^{N} Z_j\right| \ge A \,\middle|\, \mathcal{G}_0\right) \le2\exp\left(-\frac{\mathfrak{N}A^2}{2(V^2+BA)}\right). \tag*{(16)} P ( N 1 j = 1 ∑ N Z j ≥ A G 0 ) ≤ 2 exp ( − 2 ( V 2 + B A ) N A 2 ) . (16)
Proof. Set S n : = ∑ j ≤ n Z j S_n := \sum_{j\le n} Z_j S n := ∑ j ≤ n Z j and Υ : = A / ( V 2 + B A ) \Upsilon:= A/(V^2+BA) Υ := A / ( V 2 + B A ) , a G 0 \mathcal{G}_0 G 0 -measurable random variable with 0 < Υ < B − 1 0 < \Upsilon< B^{-1} 0 < Υ < B − 1 . For z ∈ R z \in\mathbb{R} z ∈ R ,
e Υ z ≤ 1 + Υ z + ∑ m ≥ 2 Υ m ∣ z ∣ m m ! . e^{\Upsilon z} \le1+\Upsilon z+\sum_{m\ge2}\frac{\Upsilon^m|z|^m}{m!}. e Υ z ≤ 1 + Υ z + m ≥ 2 ∑ m ! Υ m ∣ z ∣ m .
Taking conditional expectations and using (15) and monotone convergence,
E [ e Υ Z j ∣ G j − 1 ] ≤ 1 + Υ 2 V 2 2 ∑ m ≥ 2 ( Υ B ) m − 2 = 1 + Υ 2 V 2 2 ( 1 − Υ B ) ≤ e ψ \mathbb{E}\left[e^{\Upsilon Z_j}\mid\mathcal{G}_{j-1}\right]\le1+\frac{\Upsilon^2V^2}{2}\sum_{m\ge2}(\Upsilon B)^{m-2}=1+\frac{\Upsilon^2V^2}{2(1-\Upsilon B)}\le e^\psi E [ e Υ Z j ∣ G j − 1 ] ≤ 1 + 2 Υ 2 V 2 m ≥ 2 ∑ ( Υ B ) m − 2 = 1 + 2 ( 1 − Υ B ) Υ 2 V 2 ≤ e ψ
where
ψ : = Υ 2 V 2 2 ( 1 − Υ B ) = A 2 2 ( V 2 + B A ) . \psi:=\frac{\Upsilon^2V^2}{2(1-\Upsilon B)}=\frac{A^2}{2(V^2+BA)}. ψ := 2 ( 1 − Υ B ) Υ 2 V 2 = 2 ( V 2 + B A ) A 2 .
Hence L n : = exp ( Υ S n − n ψ ) L_n:=\exp(\Upsilon S_n-n\psi) L n := exp ( Υ S n − n ψ ) is a nonnegative supermartingale with L 0 = 1 L_0=1 L 0 = 1 :
E [ L n ∣ G n − 1 ] = L n − 1 e − ψ E [ e Υ Z n ∣ G n − 1 ] ≤ L n − 1 . \mathbb{E}[L_n\mid\mathcal{G}_{n-1}]=L_{n-1}e^{-\psi}\mathbb{E}[e^{\Upsilon Z_n}\mid\mathcal{G}_{n-1}]\le L_{n-1}. E [ L n ∣ G n − 1 ] = L n − 1 e − ψ E [ e Υ Z n ∣ G n − 1 ] ≤ L n − 1 .
For each n n n , N ∧ n N\wedge n N ∧ n is a bounded stopping time, so the optional stopping theorem for supermartingales gives
E [ L N ∧ n ∣ G 0 ] ≤ L 0 = 1. \mathbb{E}[L_{N\wedge n}\mid\mathcal{G}_0]\le L_0=1. E [ L N ∧ n ∣ G 0 ] ≤ L 0 = 1.
Since N < ∞ N<\infty N < ∞ almost surely, L N ∧ n → L N L_{N\wedge n}\to L_N L N ∧ n → L N almost surely, and Fatou’s lemma gives E [ L N ∣ G 0 ] ≤ 1 \mathbb{E}[L_N\mid\mathcal{G}_0]\le1 E [ L N ∣ G 0 ] ≤ 1 . On the event { S N ≥ N A } \{S_N\ge NA\} { S N ≥ N A } ,
L N ≥ exp ( N ( Υ A − ψ ) ) = exp ( N A 2 2 ( V 2 + B A ) ) ≥ exp ( N A 2 2 ( V 2 + B A ) ) , L_N\ge\exp(N(\Upsilon A-\psi))=\exp\left(N\frac{A^2}{2(V^2+BA)}\right)\ge\exp\left(\mathfrak{N}\frac{A^2}{2(V^2+BA)}\right), L N ≥ exp ( N ( Υ A − ψ )) = exp ( N 2 ( V 2 + B A ) A 2 ) ≥ exp ( N 2 ( V 2 + B A ) A 2 ) ,
using N ≥ N N\ge\mathfrak{N} N ≥ N and Υ A − ψ = A 2 / ( 2 ( V 2 + B A ) ) > 0 \Upsilon A-\psi=A^2/(2(V^2+BA))>0 Υ A − ψ = A 2 / ( 2 ( V 2 + B A )) > 0 . The conditional Markov inequality then gives
P ( S N ≥ N A ∣ G 0 ) ≤ e − N A 2 / ( 2 ( V 2 + B A ) ) . \mathbb{P}(S_N\ge NA\mid\mathcal{G}_0)\le e^{-\mathfrak{N}A^2/(2(V^2+BA))}. P ( S N ≥ N A ∣ G 0 ) ≤ e − N A 2 / ( 2 ( V 2 + B A )) .
The same argument applied to { − Z j } \{-Z_j\} { − Z j } bounds P ( S N ≤ − N A ∣ G 0 ) \mathbb{P}(S_N\le-NA\mid\mathcal{G}_0) P ( S N ≤ − N A ∣ G 0 ) , and the two together give (16) .
:::
Two steps of the pointwise route, seen from the stopping time
The estimation-error theorem of [18 ] asserts, for its zeroth-order common-random-number cases (B-0) and (C-0), that P ( ∣ E ˉ k s − E ˉ 0 ∣ > κ e d F Δ k 2 i . o . ) = 0 \mathbb{P}(|\bar{E}^{s}_{k}-\bar{E}^{0}|>\kappa_{\mathrm{edF}}\Delta_{k}^{2}\ \mathrm{i.o.})=0 P ( ∣ E ˉ k s − E ˉ 0 ∣ > κ edF Δ k 2 i.o. ) = 0 . That is the conclusion needed here, and Corollary 4.8 delivers it. The argument there reaches it through a pointwise inequality at a fixed sample size, summed over sample sizes. Two of its steps read differently once the sample size is treated as the stopping time, and we set them out. This is where the present analysis departs from its predecessor.
Proposition 4.4 (the union bound over sample sizes). Let Z j Z_j Z j , B B B , V V V , ℵ \aleph ℵ be as in Lemma 4.3, and let A > 0 A>0 A > 0 . Bounding P ( sup n ≥ ℵ ∣ S n ∣ / n ≥ A ∣ G 0 ) \mathbb{P}(\sup_{n\geq\aleph}|S_n|/n\geq A\mid\mathcal{G}_0) P ( sup n ≥ ℵ ∣ S n ∣/ n ≥ A ∣ G 0 ) by ∑ n ≥ ℵ P ( ∣ S n ∣ / n ≥ A ∣ G 0 ) \sum_{n\geq\aleph}\mathbb{P}(|S_n|/n\geq A\mid\mathcal{G}_0) ∑ n ≥ ℵ P ( ∣ S n ∣/ n ≥ A ∣ G 0 ) and applying Bernstein’s inequality at each n n n gives
∑ n ≥ ℵ 2 e − n c = 2 e − ℵ c 1 − e − c , c : = A 2 2 ( V 2 + B A ) . (17) \sum_{n\geq\aleph}2e^{-nc}=\frac{2e^{-\aleph c}}{1-e^{-c}},\qquad c:=\frac{A^2}{2(V^2+BA)}. \tag*{(17)} n ≥ ℵ ∑ 2 e − n c = 1 − e − c 2 e − ℵ c , c := 2 ( V 2 + B A ) A 2 . (17) In the application of [18 ] , A = κ e d F Δ k 2 A=\kappa_{\mathrm{edF}}\Delta_k^2 A = κ edF Δ k 2 , V ≻ Δ k V\succ\Delta_k V ≻ Δ k and B ≻ Δ k B\succ\Delta_k B ≻ Δ k (case (C-0)), so c = c k ≻ Δ k 2 c=c_k\succ\Delta_k^2 c = c k ≻ Δ k 2 , while n k ≻ λ k Δ k − 2 n_k\succ\lambda_k\Delta_k^{-2} n k ≻ λ k Δ k − 2 . Hence e − n k c k = e − Θ ( λ k ) e^{-n_kc_k}=e^{-\Theta(\lambda_k)} e − n k c k = e − Θ ( λ k ) is summable, but
( 1 − e − c k ) − 1 ≥ c k − 1 ≻ Δ k − 2 → ∞ (1-e^{-c_k})^{-1}\geq c_k^{-1}\succ\Delta_k^{-2}\to\infty ( 1 − e − c k ) − 1 ≥ c k − 1 ≻ Δ k − 2 → ∞ almost surely, and the product is not summable in general. Bounding the prefactor through the worst-case contraction Δ k ≥ γ d e c k Δ 0 \Delta_k\geq\gamma_{\mathrm{dec}}^{k}\Delta_0 Δ k ≥ γ dec k Δ 0 , as in [18 ] , gives ( 1 − e − x k ) − 1 ∼ x − k (1-e^{-x^{k}})^{-1}\sim x^{-k} ( 1 − e − x k ) − 1 ∼ x − k for x < 1 x<1 x < 1 , which grows geometrically in k k k ; a stopped inequality is the natural way to keep the bound summable.
Proof. Only the last sentence requires comment: 1 − e − y ≤ y 1-e^{-y}\leq y 1 − e − y ≤ y for y ≥ 0 y\geq0 y ≥ 0 , so ( 1 − e − c k ) − 1 ≥ c k − 1 (1-e^{-c_k})^{-1}\geq c_k^{-1} ( 1 − e − c k ) − 1 ≥ c k − 1 , and c k → 0 c_k\to0 c k → 0 because Δ k → 0 \Delta_k\to0 Δ k → 0 almost surely (Lemma 6.1).
The point is not cosmetic: along the path, Δ k − 2 \Delta_k^{-2} Δ k − 2 grows as fast as the sample size itself. Its origin is that a union bound treats every n ≥ n k n\geq n_k n ≥ n k as a sample size the algorithm might use, whereas the algorithm uses exactly one, N k N_k N k , and that one is a stopping time. Lemma 4.3 bounds the deviation at N k N_k N k with the single exponential 2 e − n k c k 2e^{-n_kc_k} 2 e − n k c k and no prefactor, because optional stopping replaces the sum over n n n by the evaluation of one supermartingale at one random time; Ville’s inequality does the same with a supremum. Either serves the pointwise statements of [18 ] for every point that is fixed before sampling, namely the design points in all cases and the trial point whenever it is evaluated on replications drawn after the model is built.
Proposition 4.5 (the trial point is not fixed before sampling). Under common random numbers with reuse, X k s X_k^s X k s is a measurable function of ( F k − 1 Q , ξ k , 1 , … , ξ k , N k ) (\mathcal{F}_{k-1}^{Q},\xi_{k,1},\ldots,\xi_{k,N_k}) ( F k − 1 Q , ξ k , 1 , … , ξ k , N k ) . Consequently the summands D ( X k 0 , X k s ; ξ k , j ) D(X_k^0,X_k^s;\xi_{k,j}) D ( X k 0 , X k s ; ξ k , j ) , j ≤ N k j\leq N_k j ≤ N k , need not be adapted to { G k , j } \{\mathcal{G}_{k,j}\} { G k , j } , need not satisfy E [ D ( X k 0 , X k s ; ξ k , j ) ∣ G k , j − 1 ] = 0 \mathbb{E}[D(X_k^0,X_k^s;\xi_{k,j})\mid\mathcal{G}_{k,j-1}]=0 E [ D ( X k 0 , X k s ; ξ k , j ) ∣ G k , j − 1 ] = 0 , and the hypotheses of Lemma 4.3, of Ville’s inequality and of Bernstein’s inequality for martingales are not available.
Proof. X k s = X k 0 + Q k S k ∗ X_k^s=X_k^0+Q_kS_k^* X k s = X k 0 + Q k S k ∗ and S k ∗ S_k^* S k ∗ is computed from M ^ k \widehat{M}_k M k , which is a function of the estimates at the design points, which are functions of ξ k , 1 , … , ξ k , N k \xi_{k,1},\ldots,\xi_{k,N_k} ξ k , 1 , … , ξ k , N k . For j ≤ N k j\leq N_k j ≤ N k the summand therefore depends on ξ k , j + 1 , … , ξ k , N k \xi_{k,j+1},\ldots,\xi_{k,N_k} ξ k , j + 1 , … , ξ k , N k through X k s X_k^s X k s , and its conditional mean given G k , j − 1 \mathcal{G}_{k,j-1} G k , j − 1 is E [ D ( X k 0 , y ; ξ ) ] \mathbb{E}[\mathit{D}(X_k^0,y;\xi)] E [ D ( X k 0 , y ; ξ )] evaluated not at a fixed y y y but at a y y y correlated with ξ k , j \xi_{k,j} ξ k , j , which is not zero in general.
In cases (B-0) and (C-0) of [18 ] the candidate shares the sample size N k N_k N k of the design, and whether a pointwise inequality applies to it depends on which replications it is evaluated on. If the candidate and the incumbent are evaluated together on a stream drawn after the model is built, the pointwise inequality applies conditionally on the σ \sigma σ -field at the end of the model step, under which X k s X_k^s X k s is fixed, and the within-stream pairing keeps the variance proxy at the order that gives the rates of that paper. Cases (A-0), (A-1) and (C-1) use independent streams or a deterministic sample size, and case (B-1) needs only O ( Δ k ) O(\Delta_k) O ( Δ k ) accuracy along the segment, which a single net and a union bound supply uniformly (Remark 5). Under full reuse, the scheme of Algorithm 1, no pointwise statement is available at the trial point, and what is needed instead is a bound holding simultaneously at every point of the trust region, which is indifferent to how the point was selected. The following remark places the three schemes side by side; the uniform bound is the content of the next subsection.
point” by itself. Lemma 4.3 requires that the threshold A A A and the parameters B B B , V V V be measurable with respect to the conditioning σ \sigma σ -field G 0 \mathcal{G}_0 G 0 and that the summands be a martingale difference sequence for { G j } \{\mathcal{G}_j\} { G j } . A random evaluation point is harmless if it is G 0 \mathcal{G}_0 G 0 -measurable; what is fatal is a point that is a function of the very replications being averaged. Three sampling schemes illustrate this.
(i) No common random numbers. Each design point and the candidate are evaluated on mutually independent streams. Let H k \mathcal{H}_k H k be the σ \sigma σ -field generated by F k − 1 Q \mathcal{F}_{k-1}^{Q} F k − 1 Q and the replications used to build M ^ k \widehat{M}_k M k . Then M ^ k \widehat{M}_k M k , S ^ k ∗ \widehat{S}_k^* S k ∗ and X k s ^ X_k^{\widehat{s}} X k s are H k \mathcal{H}_k H k -measurable and the candidate replications are independent of H k \mathcal{H}_k H k , so Lemma 4.3 applies with G 0 = H k \mathcal{G}_0=\mathcal{H}_k G 0 = H k and no uniformity in s ^ \widehat{s} s is needed. It is also unavailable: without shared randomness the field s ^ ↦ D ‾ k ( s ^ , n ) \widehat{s}\mapsto\overline{D}_k(\widehat{s},n) s ↦ D k ( s , n ) of (11) is not defined, and its natural substitute, the difference of two averages on independent streams, is as a function of s ^ \widehat{s} s a family of independent variables with no modulus of continuity. There is nothing to chain. The scheme pays for this in the variance: the difference of estimation errors between incumbent and candidate has standard deviation of order σ F / n \sigma_F/\sqrt{n} σ F / n with no factor Δ k \Delta_k Δ k , so the tolerance κ e d F Δ k 2 \kappa_{\mathrm{ed}}F\Delta_k^2 κ ed F Δ k 2 costs n ≳ Δ k − 4 n\gtrsim\Delta_k^{-4} n ≳ Δ k − 4 in place of the Δ k − 2 \Delta_k^{-2} Δ k − 2 of (8).
(ii) Common random numbers, with a separate stream for the candidate. The design points share one stream; the incumbent and the candidate are then re-evaluated together on a second, independent stream. Pairing is preserved within each stream, so the variance proxy is again of order κ Q 2 Δ k 2 \kappa_Q^2\Delta_k^2 κ Q 2 Δ k 2 and n ≳ Δ k − 2 n\gtrsim\Delta_k^{-2} n ≳ Δ k − 2 suffices; and X k s ^ X_k^{\widehat{s}} X k s is measurable with respect to the σ \sigma σ -field generated by the first stream, from which the second is independent, so Lemma 4.3 applies as in (i). The cost is in the count, not the exponent: the incumbent is evaluated twice, ( 2 p k + 1 ) N k + 2 N k s (2p_k+1)N_k+2N_k^s ( 2 p k + 1 ) N k + 2 N k s calls in place of ( 2 p k + 2 ) N k (2p_k+2)N_k ( 2 p k + 2 ) N k . Re-evaluating the incumbent is not optional, since pairing an estimate from the second stream with one from the first would break the coupling and return the variance proxy to order one. This is the scheme of [18 ] and of the supermartingale analyses [7 , 14 ] , and Table 2 shows why: it is the cheapest scheme for which a pointwise inequality suffices.
Table 2. Sampling schemes at iteration k k k . “Uniformity” refers to whether the accuracy statement must hold simultaneously over ∥ s ^ ∥ ≤ Δ k \lVert\widehat{s}\rVert\le\Delta_k ∥ s ∥ ≤ Δ k .
(iii) Full reuse, as in Algorithm 1. One stream serves everything. Pairing is retained, the extra evaluations are avoided, and X k s ^ X_k^{\widehat{s}} X k s is a function of the replications being averaged. There is no σ \sigma σ -field containing X k s ^ X_k^{\widehat{s}} X k s from which the replications are independent, so Lemma 4.3 cannot be applied at S ^ k ∗ \widehat{S}_k^* S k ∗ , and a bound holding simultaneously over the trust region is needed; Lemma 4.6 supplies one, and the continuity that makes it possible is exactly the continuity supplied by the shared randomness.
Uniformity in s ^ \widehat{s} s is therefore required precisely when the evaluation point fails to be measurable with respect to a σ \sigma σ -field from which the replications are independent. Common random numbers within an iteration make the error field continuous, hence chainable; reuse across model and candidate destroys the measurability, hence makes chaining necessary. Scheme (i) has neither property, (ii) the first only, (iii) both. The saving of (iii) over (ii) is 2 N k s − N k 2N_k^s-N_k 2 N k s − N k calls, one evaluation of the incumbent when the two rules stop at the same size, a factor ( 2 p k + 3 ) / ( 2 p k + 2 ) (2p_k+3)/(2p_k+2) ( 2 p k + 3 ) / ( 2 p k + 2 ) in the oracle count, and, more to the point of the analysis, the removal of a second sampling phase, a second stopping rule and a third σ \sigma σ -field. Whether that is worth the chaining argument is a matter of taste; that (iii) is what an implementation does is not.
Uniform accuracy over the trust region, and the pathwise step
The uniform statement is obtained by chaining: the unit ball is covered by nets at geometrically decreasing scales, the increment of D ‾ k ( ⋅ , n ) \overline{D}_k(\cdot,n) D k ( ⋅ , n ) along each edge is a paired increment by (12) and satisfies a Bernstein condition by Assumption 3, and a union bound over the countably many edges controls them all at once. Part I gives the argument in full (its Lemma 4.3). We only need it at the stopping time.
Lemma 4.6 (chained Bernstein inequality at a stopping time). Let B p : = { t ∈ R p : ∥ t ∥ ≤ 1 } \mathbb{B}_p:=\{t\in\mathbb{R}^p:\lVert t\rVert\le1\} B p := { t ∈ R p : ∥ t ∥ ≤ 1 } , { G j } j ≥ 0 \{\mathcal{G}_j\}_{j\ge0} { G j } j ≥ 0 a filtration, Δ > 0 \Delta>0 Δ > 0 G 0 \mathcal{G}_0 G 0 -measurable, and { Z j ( t ) } j ≥ 1 , t ∈ B p \{Z_j(t)\}_{j\ge1,t\in\mathbb{B}_p} { Z j ( t ) } j ≥ 1 , t ∈ B p an adapted random field (Z j ( t ) Z_j(t) Z j ( t ) is G j \mathcal{G}_j G j -measurable) satisfying, almost surely:
(i) Z j ( 0 ) = 0 Z_j(0)=0 Z j ( 0 ) = 0 and t ↦ Z j ( t ) t\mapsto Z_j(t) t ↦ Z j ( t ) is continuous on B p \mathbb{B}_p B p ;
(ii) E [ Z j ( t ) ∣ G j − 1 ] = 0 \mathbb{E}[Z_j(t)\mid\mathcal{G}_{j-1}]=0 E [ Z j ( t ) ∣ G j − 1 ] = 0 for every t ∈ B p t\in\mathbb{B}_p t ∈ B p ;
(iii) for all t , t ′ ∈ B p t,t'\in\mathbb{B}_p t , t ′ ∈ B p with ∥ t − t ′ ∥ ≤ 1 \lVert t-t'\rVert\le1 ∥ t − t ′ ∥ ≤ 1 and integers m ≥ 2 m\ge2 m ≥ 2 ,
E [ ∣ Z j ( t ) − Z j ( t ′ ) ∣ m ∣ G j − 1 ] ≤ m ! 2 ( B Δ ∥ t − t ′ ∥ ) m − 2 ( V Δ ∥ t − t ′ ∥ ) 2 \mathbb{E}[|Z_j(t)-Z_j(t')|^m\mid\mathcal{G}_{j-1}]\le\frac{m!}{2}(B\Delta\lVert t-t'\rVert)^{m-2}(V\Delta\lVert t-t'\rVert)^2 E [ ∣ Z j ( t ) − Z j ( t ′ ) ∣ m ∣ G j − 1 ] ≤ 2 m ! ( B Δ ∥ t − t ′ ∥ ) m − 2 ( V Δ ∥ t − t ′ ∥ ) 2
with B , V > 0 B,V>0 B , V > 0 G 0 \mathcal{G}_0 G 0 -measurable.
Let ℵ \aleph ℵ be a positive integer G 0 \mathcal{G}_0 G 0 -measurable random variable and N N N a stopping time with ℵ ≤ N < ∞ \aleph\le N<\infty ℵ ≤ N < ∞ almost surely. Then for every ϑ > 0 \vartheta>0 ϑ > 0 , almost surely,
P ( sup t ∈ B p 1 N ∣ ∑ j = 1 N Z j ( t ) ∣ ≥ 15 V Δ p + ϑ ℵ + 72 B Δ p + ϑ ℵ | G 0 ) ≤ e − ϑ . (18) \mathbb{P}\left(\sup_{t\in\mathbb{B}_p}\frac{1}{N}\left|\sum_{j=1}^{N}Z_j(t)\right|\ge15V\Delta\sqrt{\frac{p+\vartheta}{\aleph}}+72B\Delta\frac{p+\vartheta}{\aleph}\,\middle|\,\mathcal{G}_0\right)\le e^{-\vartheta}. \tag*{(18)} P ( t ∈ B p sup N 1 j = 1 ∑ N Z j ( t ) ≥ 15 V Δ ℵ p + ϑ + 72 B Δ ℵ p + ϑ G 0 ) ≤ e − ϑ . (18)
Proof. Take from the proof of Part I, Lemma 4.3, the nets N m \mathcal{N}_m N m of B p \mathbb{B}_p B p at scale 2 − m 2^{-m} 2 − m (N 0 = { 0 } \mathcal{N}_0=\{0\} N 0 = { 0 } , ∣ N m ∣ ≤ ( 3 ⋅ 2 m ) p |\mathcal{N}_m|\le(3\cdot2^m)^p ∣ N m ∣ ≤ ( 3 ⋅ 2 m ) p ), the nearest-point maps π m \pi_m π m , the sets E m ⊂ N m − 1 × N m \mathcal{E}_m\subset\mathcal{N}_{m-1}\times\mathcal{N}_m E m ⊂ N m − 1 × N m of edges of length at most min { 3 ⋅ 2 − m , 1 } \min\{3\cdot2^{-m},1\} min { 3 ⋅ 2 − m , 1 } , which contain every pair ( π m − 1 ( t ) , π m ( t ) ) (\pi_{m-1}(t),\pi_m(t)) ( π m − 1 ( t ) , π m ( t )) , and the levels ϑ m : = ϑ + 4 p ( m + 1 ) \vartheta_m:=\vartheta+4p(m+1) ϑ m := ϑ + 4 p ( m + 1 ) , for which 4 ∣ E m ∣ ≤ 2 − m e ϑ m − ϑ 4|\mathcal{E}_m|\le2^{-m}e^{\vartheta_m-\vartheta} 4∣ E m ∣ ≤ 2 − m e ϑ m − ϑ .
Set S n ( t ) : = ∑ j ≤ n Z j ( t ) S_n(t):=\sum_{j\le n}Z_j(t) S n ( t ) := ∑ j ≤ n Z j ( t ) and R m : = 3 ⋅ 2 − m Δ R_m:=3\cdot2^{-m}\Delta R m := 3 ⋅ 2 − m Δ . For an edge ( u , v ) ∈ E m (u,v)\in\mathcal{E}_m ( u , v ) ∈ E m the increments Z j ( v ) − Z j ( u ) Z_j(v)-Z_j(u) Z j ( v ) − Z j ( u ) are adapted, conditionally centered by (ii) and satisfy (15) with B R m BR_m B R m , V R m VR_m V R m by (iii), so Lemma 4.3 with A m : = R m ( 2 ϑ m / ℵ + 2 B ϑ m / ℵ ) A_m:=R_m\left(\sqrt{2\vartheta_m/\aleph}+2B\vartheta_m/\aleph\right) A m := R m ( 2 ϑ m /ℵ + 2 B ϑ m /ℵ ) gives
P ( ∣ S N ( v ) − S N ( u ) ∣ ≥ N A m ∣ G 0 ) ≤ 2 e − ϑ m , \mathbb{P}(|S_N(v)-S_N(u)|\ge NA_m\mid\mathcal{G}_0)\le2e^{-\vartheta_m}, P ( ∣ S N ( v ) − S N ( u ) ∣ ≥ N A m ∣ G 0 ) ≤ 2 e − ϑ m ,
the exponent being at least ϑ m \vartheta_m ϑ m by the computation in Part I. A union bound over the countably many edges of all levels gives total conditional probability at most ∑ m ≥ 1 2 ∣ E m ∣ e − ϑ m ≤ e − ϑ \sum_{m\ge1}2|\mathcal{E}_m|e^{-\vartheta_m}\le e^{-\vartheta} ∑ m ≥ 1 2∣ E m ∣ e − ϑ m ≤ e − ϑ . Outside that event, for every t t t and ϕ ≥ 1 \phi\ge1 ϕ ≥ 1 , telescoping along the edges ( π m − 1 ( t ) , π m ( t ) ) (\pi_{m-1}(t),\pi_m(t)) ( π m − 1 ( t ) , π m ( t )) , m ≤ ϕ m\le\phi m ≤ ϕ , and using S N ( 0 ) = 0 S_N(0)=0 S N ( 0 ) = 0 gives ∣ S N ( π ϕ ( t ) ) ∣ ≤ N ∑ m ≤ ϕ A m |S_N(\pi_\phi(t))|\le N\sum_{m\le\phi}A_m ∣ S N ( π ϕ ( t )) ∣ ≤ N ∑ m ≤ ϕ A m ; S N ( ⋅ ) S_N(\cdot) S N ( ⋅ ) is continuous by (i), π ϕ ( t ) → t \pi_\phi(t)\to t π ϕ ( t ) → t , and
∑ m ≥ 1 A m ≤ 15 V Δ ( p + ϑ ) / ℵ + 72 B Δ ( p + ϑ ) / ℵ \sum_{m\ge1}A_m\le15V\Delta\sqrt{(p+\vartheta)/\aleph}+72B\Delta(p+\vartheta)/\aleph m ≥ 1 ∑ A m ≤ 15 V Δ ( p + ϑ ) /ℵ + 72 B Δ ( p + ϑ ) /ℵ
by Part I’s summation. So here, only the time N N N enters: no statement at any other sample size is used. □
Remark 5 (why a single net does not suffice). One might try to avoid chaining by covering the ball with one net at the target scale and applying Lemma 4.3 at each net point. Since the target accuracy is κ e d F Δ k 2 \kappa_{\mathrm{ed}F}\Delta_k^2 κ ed F Δ k 2 and the process is Lipschitz in s ^ \hat{s} s ^ with modulus of order κ Q \kappa_Q κ Q , the net must have mesh ≍ Δ k \asymp\Delta_k ≍ Δ k in the coordinates where the accuracy is Δ k 2 \Delta_k^2 Δ k 2 , that is, Δ k − p \Delta_k^{-p} Δ k − p points; the union bound then costs log ( Δ k − p ) = p log ( 1 / Δ k ) \log(\Delta_k^{-p})=p\log(1/\Delta_k) log ( Δ k − p ) = p log ( 1/ Δ k ) in the exponent, so the sample size would need λ k ≳ p log ( 1 / Δ k ) ≍ p k \lambda_k\gtrsim p\log(1/\Delta_k)\asymp pk λ k ≳ p log ( 1/ Δ k ) ≍ p k for a radius contracting geometrically. Chaining pays p \sqrt{p} p in a constant instead. The difficulty arises precisely because the accuracy threshold Δ k 2 \Delta_k^2 Δ k 2 is one power of Δ k \Delta_k Δ k finer than the modulus Δ k \Delta_k Δ k of the process; a threshold of order Δ k \Delta_k Δ k is met by a net of O ( 1 ) p O(1)^p O ( 1 ) p points and a union bound. This is why only the zeroth-order regimes that both use common random numbers and require O ( Δ k 2 ) O(\Delta_k^2) O ( Δ k 2 ) accuracy of the estimate differences are affected: the first-order regime needs only O ( Δ k ) O(\Delta_k) O ( Δ k ) along the segment.
We now apply Lemma 4.6 to the paired increment. Define
r F : = min { 1 , ( σ 0 κ e d F 30 κ s σ D κ Q ) 2 , σ 0 2 κ e d F 144 κ s 2 b D κ Q Δ max } , c F : = r F 2 , (19) r_F:=\min\left\{1,\left(\frac{\sigma_0\kappa_{\mathrm{ed}F}}{30\kappa_s\sigma_D\kappa_Q}\right)^2,\frac{\sigma_0^2\kappa_{\mathrm{ed}F}}{144\kappa_s^2b_D\kappa_Q\Delta_{\max}}\right\},\qquad c_F:=\frac{r_F}{2}, \tag*{(19)} r F := min { 1 , ( 30 κ s σ D κ Q σ 0 κ ed F ) 2 , 144 κ s 2 b D κ Q Δ m a x σ 0 2 κ ed F } , c F := 2 r F , (19)
and the accuracy event
U k : = { sup ∥ s ^ ∥ ≤ Δ k ∣ D ‾ k ( s ^ , N k ) ∣ ≤ κ e d F Δ k 2 } . (20) \mathcal{U}_k:=\left\{\sup_{\lVert\hat{s}\rVert\le\Delta_k}|\overline{D}_k(\hat{s},N_k)|\le\kappa_{\mathrm{ed}F}\Delta_k^2\right\}. \tag*{(20)} U k := { ∥ s ^ ∥ ≤ Δ k sup ∣ D k ( s ^ , N k ) ∣ ≤ κ ed F Δ k 2 } . (20)
Theorem 4.7 (uniform weak accuracy; Part I). Let Assumptions 2, 3, 4 and 6(b) hold. If λ k ≥ 2 p k / r F \lambda_k\ge2p_k/r_F λ k ≥ 2 p k / r F , then almost surely
P ( U k c ∣ F k − 1 Q ) ≤ e − c F λ k . (21) \mathbb{P}(\mathcal{U}_k^c\mid\mathcal{F}_{k-1}^{Q})\le e^{-c_F\lambda_k}. \tag*{(21)} P ( U k c ∣ F k − 1 Q ) ≤ e − c F λ k . (21)
Proof. Apply Lemma 4.6 conditionally on F k − 1 Q \mathcal{F}_{k-1}^{Q} F k − 1 Q with G j = G k , j \mathcal{G}_j=\mathcal{G}_{k,j} G j = G k , j , p = p k p=p_k p = p k , Δ = Δ k \Delta=\Delta_k Δ = Δ k , ℵ = n k \aleph=n_k ℵ = n k , N = N k N=N_k N = N k (a finite stopping time with N k ≥ n k N_k\ge n_k N k ≥ n k by Proposition 4.2 ) and the field Z j ( t ) : = D ( X k 0 , X k 0 + Q k Δ k t ; ξ k , j ) Z_j(t):=D(X_k^0,X_k^0+Q_k\Delta_k t;\xi_{k,j}) Z j ( t ) := D ( X k 0 , X k 0 + Q k Δ k t ; ξ k , j ) on B p k \mathbb{B}_{p_k} B p k , so that 1 n ∑ j ≤ n Z j ( s ^ / Δ k ) = D ‾ k ( s ^ , n ) \frac{1}{n}\sum_{j\le n}Z_j(\hat{s}/\Delta_k)=\overline{D}_k(\hat{s},n) n 1 ∑ j ≤ n Z j ( s ^ / Δ k ) = D k ( s ^ , n ) for ∥ s ^ ∥ ≤ Δ k \lVert\hat{s}\rVert\le\Delta_k ∥ s ^ ∥ ≤ Δ k . The field is adapted; (i) holds by (10), Assumption 4 and the continuity of f f f ; (ii) and (iii) hold with B = b D κ Q B=b_D\kappa_Q B = b D κ Q and V = σ D κ Q V=\sigma_D\kappa_Q V = σ D κ Q , because by (12) Z j ( t ) − Z j ( t ′ ) Z_j(t)-Z_j(t') Z j ( t ) − Z j ( t ′ ) is the paired increment at displacement
∥ Q k Δ k ( t − t ′ ) ∥ ≤ κ Q Δ k ∥ t − t ′ ∥ ≤ κ Q Δ max \lVert Q_k\Delta_k(t-t')\rVert\le\kappa_Q\Delta_k\lVert t-t'\rVert\le\kappa_Q\Delta_{\max} ∥ Q k Δ k ( t − t ′ )∥ ≤ κ Q Δ k ∥ t − t ′ ∥ ≤ κ Q Δ m a x
for ∥ t − t ′ ∥ ≤ 1 \lVert t-t'\rVert\le1 ∥ t − t ′ ∥ ≤ 1 , to which Assumption 3 applies conditionally on G k , j − 1 \mathcal{G}_{k,j-1} G k , j − 1 by Lemma 4.1. Take ϑ = c F λ k \vartheta=c_F\lambda_k ϑ = c F λ k . Substituting n k ≥ σ 0 2 λ k / ( κ s 2 Δ k 2 ) n_k\ge\sigma_0^2\lambda_k/(\kappa_s^2\Delta_k^2) n k ≥ σ 0 2 λ k / ( κ s 2 Δ k 2 ) and Δ k ≤ Δ max \Delta_k\le\Delta_{\max} Δ k ≤ Δ m a x into (18), the threshold is at most
Δ k 2 [ 15 κ s σ D κ Q σ 0 p k + ϑ λ k + 72 κ s 2 b D κ Q Δ max σ 0 2 p k + ϑ λ k ] . \Delta_k^2\left[\frac{15\kappa_s\sigma_D\kappa_Q}{\sigma_0}\sqrt{\frac{p_k+\vartheta}{\lambda_k}}+\frac{72\kappa_s^2b_D\kappa_Q\Delta_{\max}}{\sigma_0^2}\frac{p_k+\vartheta}{\lambda_k}\right]. Δ k 2 [ σ 0 15 κ s σ D κ Q λ k p k + ϑ + σ 0 2 72 κ s 2 b D κ Q Δ m a x λ k p k + ϑ ] .
and ( p k + ϑ ) / λ k ≤ r F (p_k+\vartheta)/\lambda_k\le r_F ( p k + ϑ ) / λ k ≤ r F by λ k ≥ 2 p k / r F \lambda_k\ge2p_k/r_F λ k ≥ 2 p k / r F and ϑ / λ k = r F / 2 \vartheta/\lambda_k=r_F/2 ϑ / λ k = r F /2 , so (19) bounds each term by κ e d F Δ k 2 / 2 \kappa_{\mathrm{ed}F}\Delta_k^2/2 κ ed F Δ k 2 /2 . Hence U k c U_k^c U k c is contained in the event of (18), whose conditional probability is at most e − c F λ k e^{-c_F\lambda_k} e − c F λ k . This is Part I’s Theorem 4.2 with the stopped lemma in place of the time-uniform one; only r F r_F r F , c F c_F c F and λ k ≥ 2 p k / r F \lambda_k\ge2p_k/r_F λ k ≥ 2 p k / r F are used below.
The constants r F , c F r_F,c_F r F , c F do not depend on p k p_k p k ; the dependence on the subspace dimension sits entirely in the hypothesis λ k ≥ 2 p k / r F \lambda_k\ge2p_k/r_F λ k ≥ 2 p k / r F , which is the cost of uniformity over a p k p_k p k -dimensional ball (Section 9). Since p k = O ( log k ) p_k=O(\log k) p k = O ( log k ) while λ k / log k → ∞ \lambda_k/\log k\to\infty λ k / log k → ∞ , that hypothesis holds for all k ≥ k λ k\ge k_\lambda k ≥ k λ with k λ k_\lambda k λ deterministic; it is a condition on an index, not on λ 0 \lambda_0 λ 0 , and this is one of the things λ k → ∞ \lambda_k\to\infty λ k → ∞ buys.
Corollary 4.8 (the pathwise step: accuracy holds eventually). Under the hypotheses of Theorem 4.7 , P ( U k c i . o . ) = 0 \mathbb{P}(U_k^c\ \mathrm{i.o.})=0 P ( U k c i.o. ) = 0 . Equivalently, there is an almost surely finite random index K U K_U K U such that U k U_k U k holds for all k ≥ K U k\ge K_U k ≥ K U , and on U k U_k U k ,
∣ E ˉ k i − E ˉ k 0 ∣ ≤ κ e d F Δ k 2 ( i = 1 , … , 2 p k ) , ∣ E ˉ k s − E ˉ k 0 ∣ ≤ κ e d F Δ k 2 . (22) \left|\bar{E}_k^i-\bar{E}_k^0\right|\le\kappa_{\mathrm{ed}F}\Delta_k^2\quad(i=1,\ldots,2p_k),\qquad\left|\bar{E}_k^s-\bar{E}_k^0\right|\le\kappa_{\mathrm{ed}F}\Delta_k^2. \tag*{(22)} E ˉ k i − E ˉ k 0 ≤ κ ed F Δ k 2 ( i = 1 , … , 2 p k ) , E ˉ k s − E ˉ k 0 ≤ κ ed F Δ k 2 . (22)
Proof. For k ≥ k λ k\ge k_\lambda k ≥ k λ , taking expectations in (21) gives
P ( U k c ) ≤ exp ( − c F λ 0 ( log ( k + 2 ) ) 1 + ϵ λ ) , \mathbb{P}(U_k^c)\le\exp\left(-c_F\lambda_0(\log(k+2))^{1+\epsilon_\lambda}\right), P ( U k c ) ≤ exp ( − c F λ 0 ( log ( k + 2 ) ) 1 + ϵ λ ) ,
which is summable in k k k because c F λ 0 ( log ( k + 2 ) ) 1 + ϵ λ ≥ 2 log k c_F\lambda_0(\log(k+2))^{1+\epsilon_\lambda}\ge2\log k c F λ 0 ( log ( k + 2 ) ) 1 + ϵ λ ≥ 2 log k for all large k k k , whatever λ 0 > 0 \lambda_0>0 λ 0 > 0 . The first Borel–Cantelli lemma gives the claim; no independence among the U k U_k U k is used, and none is available, since U k U_k U k depends on X k 0 X_k^0 X k 0 and Δ k \Delta_k Δ k and hence on all previous replications. The consequences (22) are the specializations of U k U_k U k to s ^ = S ^ k i \hat{s}=\hat{S}_k^i s ^ = S ^ k i and s ^ = S ^ k ∗ \hat{s}=\hat{S}_k^* s ^ = S ^ k ∗ , both admissible since ∥ S ^ k i ∥ = Δ k \lVert\hat{S}_k^i\rVert=\Delta_k ∥ S ^ k i ∥ = Δ k and ∥ S ^ k ∗ ∥ ≤ Δ k \lVert\hat{S}_k^*\rVert\le\Delta_k ∥ S ^ k ∗ ∥ ≤ Δ k .
Corollary 4.8 is the whole pathwise device in one statement: on almost every path there is a random, finite K U ( ω ) K_U(\omega) K U ( ω ) past which the estimates are accurate at every design point and at the trial point simultaneously, and the constant κ e d F \kappa_{\mathrm{ed}F} κ ed F can be any positive number (a smaller κ e d F \kappa_{\mathrm{ed}F} κ ed F only moves K U K_U K U ). Once alignment also holds eventually (Section 6.1), everything after this point is deterministic along the path. The corollary is also the form that [18 Theorem 3.2] takes for cases (B-0) and (C-0) once the sample size is used as a stopping time: so no sum over n n n or pointwise statement at the trial point is needed.
Remark 6 (what the adaptive rule buys). Theorem 4.7 uses the rule (7) only through the floor N k ≥ n k N_k\ge n_k N k ≥ n k , which follows from the guard σ 0 \sigma_0 σ 0 alone; no empirical standard deviation appears in any hypothesis. A rule calibrated instead to a global bound σ F , max \sigma_{F,\max} σ F , m a x would meet the same accuracy guarantee while expending a factor ( σ F , max / σ k , + ) 2 (\sigma_{F,\max}/\sigma_{k,+})^2 ( σ F , m a x / σ k , + ) 2 more samples at every iteration, where σ k , + : = σ 0 ∨ max i σ F ( X k i ) \sigma_{k,+}:=\sigma_0\vee\max_i\sigma_F(X_k^i) σ k , + := σ 0 ∨ max i σ F ( X k i ) is the noise level at the current design. What the rule buys is efficiency: conditionally on F k − 1 Q \mathcal{F}_{k-1}^Q F k − 1 Q it is a Chow–Robbins rule and N k / ( n k σ k , + 2 / σ 0 2 ) → 1 N_k/(n_k\sigma_{k,+}^2/\sigma_0^2)\to1 N k / ( n k σ k , + 2 / σ 0 2 ) → 1 as λ k → ∞ \lambda_k\to\infty λ k → ∞ [8 , 15 ] , so it attains the sample size on a random scale knowing σ k , + \sigma_{k,+} σ k , + would prescribe. This factor is invisible in an almost sure statement with a random constant and visible only in an expectation with deterministic constants, which is why it is displayed in Part I and not here.
Model quality: the pathwise interface
This section extracts from U k U_k U k the three deterministic inequalities that the trust-region argument consumes, and nothing else. Set
a : = 1 2 κ L g κ Q 2 + κ e d F , κ g ( p ) : = p a , κ m f ( p ) : = 2 κ g ( p ) + κ L g κ Q 2 + κ H . (23) a:=\frac{1}{2}\kappa_{L_g}\kappa_Q^2+\kappa_{\mathrm{ed}F},\qquad\kappa_g(p):=\sqrt{p}\,a,\qquad\kappa_{mf}(p):=2\kappa_g(p)+\kappa_{L_g}\kappa_Q^2+\kappa_H. \tag*{(23)} a := 2 1 κ L g κ Q 2 + κ ed F , κ g ( p ) := p a , κ m f ( p ) := 2 κ g ( p ) + κ L g κ Q 2 + κ H . (23)
Lemma 5.1 (reduced gradient). ∇ f ^ k ( s ^ ) = Q k T ∇ f ( X k 0 + Q k s ^ ) \nabla\hat{f}_k(\hat{s})=Q_k^{\mathsf{T}}\nabla f(X_k^0+Q_k\hat{s}) ∇ f ^ k ( s ^ ) = Q k T ∇ f ( X k 0 + Q k s ^ ) , and ∇ f ^ k \nabla\hat{f}_k ∇ f ^ k is κ L g κ Q 2 \kappa_{L_g}\kappa_Q^2 κ L g κ Q 2 -Lipschitz on R p k \mathbb{R}^{p_k} R p k . Consequently, for ∥ s ^ ∥ ≤ Δ k \lVert\hat{s}\rVert\le\Delta_k ∥ s ^ ∥ ≤ Δ k ,
∣ f ^ k ( s ^ ) − f ^ k ( 0 ) − ∇ f ^ k ( 0 ) T s ^ ∣ ≤ 1 2 κ L g κ Q 2 ∥ s ^ ∥ 2 . \left|\hat{f}_k(\hat{s})-\hat{f}_k(0)-\nabla\hat{f}_k(0)^{\mathsf{T}}\hat{s}\right|\le\frac{1}{2}\kappa_{L_g}\kappa_Q^2\lVert\hat{s}\rVert^2. f ^ k ( s ^ ) − f ^ k ( 0 ) − ∇ f ^ k ( 0 ) T s ^ ≤ 2 1 κ L g κ Q 2 ∥ s ^ ∥ 2 .
Proof. The chain rule, then
∥ Q k T ( ∇ f ( x 1 ) − ∇ f ( x 2 ) ) ∥ ≤ κ Q κ L g ∥ Q k ( s ^ 1 − s ^ 2 ) ∥ ≤ κ L g κ Q 2 ∥ s ^ 1 − s ^ 2 ∥ , \left\|Q_k^{\mathsf{T}}\left(\nabla f(x_1)-\nabla f(x_2)\right)\right\| \le\kappa_Q\kappa_{L_g}\left\|Q_k(\hat{s}_1-\hat{s}_2)\right\| \le\kappa_{L_g}\kappa_Q^2\left\|\hat{s}_1-\hat{s}_2\right\|, Q k T ( ∇ f ( x 1 ) − ∇ f ( x 2 ) ) ≤ κ Q κ L g ∥ Q k ( s ^ 1 − s ^ 2 ) ∥ ≤ κ L g κ Q 2 ∥ s ^ 1 − s ^ 2 ∥ ,
then the integral form of Taylor’s theorem.
Lemma 5.2 (model gradient at the center). On U k U_k U k , ∥ G ^ k − ∇ f ^ k ( 0 ) ∥ ≤ κ g ( p k ) Δ k \left\|\hat{G}_k-\nabla\hat{f}_k(0)\right\|\le\kappa_g(p_k)\Delta_k G ^ k − ∇ f ^ k ( 0 ) ≤ κ g ( p k ) Δ k .
Proof. Fix i ∈ { 1 , … , p k } i\in\{1,\ldots,p_k\} i ∈ { 1 , … , p k } . By (5),
[ G ^ k ] i = g k , i + ( E ˉ k i − E ˉ k p k + i ) / ( 2 Δ k ) [\hat{G}_k]_i=g_{k,i}+\left(\bar{E}_k^i-\bar{E}_k^{p_k+i}\right)/(2\Delta_k) [ G ^ k ] i = g k , i + ( E ˉ k i − E ˉ k p k + i ) / ( 2 Δ k ) with
g k , i : = ( f ^ k ( Δ k e ^ i ) − f ^ k ( − Δ k e ^ i ) ) / ( 2 Δ k ) = 1 2 Δ k ∫ − Δ k Δ k ∂ i f ^ k ( t e ^ i ) d t , g_{k,i}:=\left(\hat{f}_k(\Delta_k\hat{e}^i)-\hat{f}_k(-\Delta_k\hat{e}^i)\right)/(2\Delta_k)=\frac{1}{2\Delta_k}\int_{-\Delta_k}^{\Delta_k}\partial_i\hat{f}_k(t\hat{e}^i)\,\mathrm{d}t, g k , i := ( f ^ k ( Δ k e ^ i ) − f ^ k ( − Δ k e ^ i ) ) / ( 2 Δ k ) = 2 Δ k 1 ∫ − Δ k Δ k ∂ i f ^ k ( t e ^ i ) d t , so by Lemma 5.1
∣ g k , i − ∂ i f ^ k ( 0 ) ∣ ≤ 1 2 Δ k ∫ − Δ k Δ k κ L g κ Q 2 ∣ t ∣ d t = 1 2 κ L g κ Q 2 Δ k . \left|g_{k,i}-\partial_i\hat{f}_k(0)\right|\le\frac{1}{2\Delta_k}\int_{-\Delta_k}^{\Delta_k}\kappa_{L_g}\kappa_Q^2|t|\,\mathrm{d}t=\frac{1}{2}\kappa_{L_g}\kappa_Q^2\Delta_k. g k , i − ∂ i f ^ k ( 0 ) ≤ 2 Δ k 1 ∫ − Δ k Δ k κ L g κ Q 2 ∣ t ∣ d t = 2 1 κ L g κ Q 2 Δ k . On U k U_k U k , by (22),
∣ E ˉ k i − E ˉ k p k + i ∣ ≤ ∣ E ˉ k i − E ˉ k 0 ∣ + ∣ E ˉ k p k + i − E ˉ k 0 ∣ ≤ 2 κ e d F Δ k 2 , \left|\bar{E}_k^i-\bar{E}_k^{p_k+i}\right|\le\left|\bar{E}_k^i-\bar{E}_k^0\right|+\left|\bar{E}_k^{p_k+i}-\bar{E}_k^0\right|\le2\kappa_{\mathrm{edF}}\Delta_k^2, E ˉ k i − E ˉ k p k + i ≤ E ˉ k i − E ˉ k 0 + E ˉ k p k + i − E ˉ k 0 ≤ 2 κ edF Δ k 2 , so
∣ [ G ^ k ] i − ∂ i f ^ k ( 0 ) ∣ ≤ ( 1 2 κ L g κ Q 2 + κ e d F ) Δ k = a Δ k . \left|[\hat{G}_k]_i-\partial_i\hat{f}_k(0)\right|\le\left(\frac{1}{2}\kappa_{L_g}\kappa_Q^2+\kappa_{\mathrm{edF}}\right)\Delta_k=a\Delta_k. [ G ^ k ] i − ∂ i f ^ k ( 0 ) ≤ ( 2 1 κ L g κ Q 2 + κ edF ) Δ k = a Δ k . Summing the squares of the p k p_k p k coordinates gives the claim.
Lemma 5.3 (trial-point difference). On U k U_k U k , ∣ E ˉ k s − E ˉ k 0 ∣ = ∣ D ˉ k ( S ^ k ∗ , N k ) ∣ ≤ κ e d F Δ k 2 \left|\bar{E}_k^s-\bar{E}_k^0\right|=\left|\bar{D}_k(\hat{S}_k^*,N_k)\right|\le\kappa_{\mathrm{edF}}\Delta_k^2 E ˉ k s − E ˉ k 0 = D ˉ k ( S ^ k ∗ , N k ) ≤ κ edF Δ k 2 .
Proof. Immediate from (20), since ∥ S ^ k ∗ ∥ ≤ Δ k \left\|\hat{S}_k^*\right\|\le\Delta_k S ^ k ∗ ≤ Δ k .
Lemma 5.4 (model against function). On U k U_k U k , for every ∥ s ^ ∥ ≤ Δ k \|\hat{s}\|\le\Delta_k ∥ s ^ ∥ ≤ Δ k ,
∣ ( M ^ k ( s ^ ) − M ^ k ( 0 ) ) − ( f ^ k ( s ^ ) − f ^ k ( 0 ) ) ∣ ≤ 1 2 κ m f ( p k ) Δ k 2 . (24) \left|\left(\hat{M}_k(\hat{s})-\hat{M}_k(0)\right)-\left(\hat{f}_k(\hat{s})-\hat{f}_k(0)\right)\right|\le\frac{1}{2}\kappa_{mf}(p_k)\Delta_k^2. \tag*{(24)} ( M ^ k ( s ^ ) − M ^ k ( 0 ) ) − ( f ^ k ( s ^ ) − f ^ k ( 0 ) ) ≤ 2 1 κ m f ( p k ) Δ k 2 . (24) Proof. By Lemma 5.1
M ^ k ( s ^ ) − M ^ k ( 0 ) = G ^ k T s ^ + 1 2 s ^ T H ^ k s ^ \hat{M}_k(\hat{s})-\hat{M}_k(0)=\hat{G}_k^{\mathsf{T}}\hat{s}+\frac{1}{2}\hat{s}^{\mathsf{T}}\hat{H}_k\hat{s} M ^ k ( s ^ ) − M ^ k ( 0 ) = G ^ k T s ^ + 2 1 s ^ T H ^ k s ^ and
f ^ k ( s ^ ) − f ^ k ( 0 ) = ∇ f ^ k ( 0 ) T s ^ + ϱ \hat{f}_k(\hat{s})-\hat{f}_k(0)=\nabla\hat{f}_k(0)^{\mathsf{T}}\hat{s}+\varrho f ^ k ( s ^ ) − f ^ k ( 0 ) = ∇ f ^ k ( 0 ) T s ^ + ϱ with ∣ ϱ ∣ ≤ 1 2 κ L g κ Q 2 Δ k 2 |\varrho|\le\frac{1}{2}\kappa_{L_g}\kappa_Q^2\Delta_k^2 ∣ ϱ ∣ ≤ 2 1 κ L g κ Q 2 Δ k 2 . The difference is at most
∥ G ^ k − ∇ f ^ k ( 0 ) ∥ Δ k + 1 2 κ H Δ k 2 + 1 2 κ L g κ Q 2 Δ k 2 , \left\|\hat{G}_k-\nabla\hat{f}_k(0)\right\|\Delta_k+\frac{1}{2}\kappa_H\Delta_k^2+\frac{1}{2}\kappa_{L_g}\kappa_Q^2\Delta_k^2, G ^ k − ∇ f ^ k ( 0 ) Δ k + 2 1 κ H Δ k 2 + 2 1 κ L g κ Q 2 Δ k 2 , and Lemma 5.2 gives (24).
Lemma 5.5 (the clip is eventually inactive). On U k U_k U k the unclipped second differences in (5) are bounded in absolute value by κ L g κ Q 2 + 2 κ e d F \kappa_{L_g}\kappa_Q^2+2\kappa_{\mathrm{edF}} κ L g κ Q 2 + 2 κ edF ; hence if κ H ≥ κ L g κ Q 2 + 2 κ e d F \kappa_H\ge\kappa_{L_g}\kappa_Q^2+2\kappa_{\mathrm{edF}} κ H ≥ κ L g κ Q 2 + 2 κ edF the clipping in (5) has no effect for k ≥ K U k\ge K_U k ≥ K U .
Proof. The second difference of f ^ k \hat{f}_k f ^ k along e ^ i \hat{e}^i e ^ i divided by Δ k 2 \Delta_k^2 Δ k 2 is bounded by κ L g κ Q 2 \kappa_{L_g}\kappa_Q^2 κ L g κ Q 2 by Lemma 5.1, and the estimation part is
( D ˉ k ( Δ k e ^ i , N k ) + D ˉ k ( − Δ k e ^ i , N k ) ) / Δ k 2 , \left(\bar{D}_k(\Delta_k\hat{e}^i,N_k)+\bar{D}_k(-\Delta_k\hat{e}^i,N_k)\right)/\Delta_k^2, ( D ˉ k ( Δ k e ^ i , N k ) + D ˉ k ( − Δ k e ^ i , N k ) ) / Δ k 2 , bounded by $2\kappa_{\mathrm{edF}}o n on o n U_k.
Lemmas 5.2–5.4 are the entire interface between the probabilistic and the deterministic parts of the paper. No bound on ∇ M ^ k ( s ^ ) − ∇ f ^ k ( s ^ ) \nabla\hat{M}_k(\hat{s})-\nabla\hat{f}_k(\hat{s}) ∇ M ^ k ( s ^ ) − ∇ f ^ k ( s ^ ) away from s ^ = 0 \hat{s}=0 s ^ = 0 is used, so the models are neither assumed nor shown to be fully linear; the supremum in Theorem 4.7 is over a single scalar process and is there only because the point at which Lemma 5.3 is applied was selected by the replications being averaged.
Remark 7 (the role of the quadratic term). H ^ k \widehat{H}_k H k enters the analysis in exactly two places: through 1 2 κ H Δ k 2 \frac{1}{2}\kappa_H\Delta_k^2 2 1 κ H Δ k 2 in Lemma 5.4, and through ∥ H ^ k ∥ ∨ 1 ≤ κ H \lVert\widehat{H}_k\rVert\vee1\le\kappa_H ∥ H k ∥ ∨ 1 ≤ κ H in Assumption 5. Neither uses what H ^ k \widehat{H}_k H k approximates. The central-difference gradient (5) is the same whether or not a diagonal Hessian is fitted, and in Lemma 5.2 the pairs ± Δ k e ^ i \pm\Delta_k\widehat{e}^i ± Δ k e i cancel the quadratic term exactly, so κ g \kappa_g κ g is free of κ H \kappa_H κ H . Every statement of Sections 6–7 therefore holds verbatim for the linear model F ‾ k 0 + G ^ k T s ^ \overline{F}_k^0+\widehat{G}_k^{\mathsf T}\widehat{s} F k 0 + G k T s , with κ H \kappa_H κ H replaced by 1 in (23) and (27) and the subproblem solved exactly by s ^ k ∗ = − Δ k G ^ k / ∥ G ^ k ∥ \widehat{s}_k^*=-\Delta_k\widehat{G}_k/\lVert\widehat{G}_k\rVert s k ∗ = − Δ k G k / ∥ G k ∥ , for which Assumption 5 holds with κ f c d = 1 \kappa_{\mathrm{fcd}}=1 κ fcd = 1 . This is the stochastic form of the classical fact that first-order convergence of model-based trust-region methods needs gradient accuracy and a bounded Hessian, never Hessian accuracy [9 Ch. 10] . Only O ( Δ k ) O(\Delta_k) O ( Δ k ) gradient accuracy is consumed, so forward differences on p k + 1 p_k+1 p k + 1 points would suffice for the theory; the symmetric design is kept because the second differences it yields cost nothing, having been paid for by the gradient. What the quadratic term buys is not visible in first-order rates: a step that uses curvature and need not be the Cauchy direction, a step that can be shorter than Δ k \Delta_k Δ k , and, under a Lipschitz Hessian, a central-difference bias of order Δ k 2 \Delta_k^2 Δ k 2 that a decoupled interpolation radius could exploit [17 ] .
Remark 8 (Hessians in random subspaces). It is often observed that curvature is hard to maintain in random subspace methods: the reduced Hessian Q k T ∇ 2 f Q k Q_k^{\mathsf T}\nabla^2 f Q_k Q k T ∇ 2 f Q k lives in a subspace redrawn at every iteration, so curvature estimated at k k k cannot be carried to k + 1 k+1 k + 1 by the least-change updates of full-space methods [22 ] , and a full quadratic interpolation model in the subspace costs ( p + 1 ) ( p + 2 ) / 2 (p+1)(p+2)/2 ( p + 1 ) ( p + 2 ) /2 points rather than O ( p ) O(p) O ( p ) . Both observations are correct and neither affects the present model. The diagonal H ^ k \widehat{H}_k H k is computed from the 2 p k + 1 2p_k+1 2 p k + 1 points already used for the gradient, at no additional oracle cost and with no attempt to carry it across iterations; the analysis uses it only as a bounded perturbation, and Remark 7 shows the analysis asks nothing more of it. The difficulty would become a disadvantage only for a second-order guarantee or for curvature reuse, which we do not study here.
Convergence
Fix the sufficient-decrease constant of a successful iteration,
θ a : = η κ f c d 2 μ min { 1 , 1 μ κ H } , and assume throughout κ e d F < θ a . (25) \theta_a := \frac{\eta\kappa_{\mathrm{fcd}}}{2\mu}\min\left\{1,\frac{1}{\mu\kappa_H}\right\},
\qquad\text{and assume throughout}\qquad\kappa_{\mathrm{edF}}<\theta_a. \tag*{(25)} θ a := 2 μ η κ fcd min { 1 , μ κ H 1 } , and assume throughout κ edF < θ a . (25)
The condition is on κ e d F \kappa_{\mathrm{edF}} κ edF , a design constant we are free to choose small, and it is the same as in [18 ] .
Lemma 6.1 (radii are square summable). Under the hypotheses of Corollary 4.8, Assumption 5 and (25) S Δ : = ∑ k ≥ 0 Δ k 2 < ∞ S_\Delta:=\sum_{k\ge0}\Delta_k^2<\infty S Δ := ∑ k ≥ 0 Δ k 2 < ∞ almost surely; in particular Δ k → 0 \Delta_k\to0 Δ k → 0 almost surely.
Proof. Fix ω \omega ω outside the null set of Corollary 4.8. If k ≥ K U k\ge K_U k ≥ K U is successful then ρ ^ k ≥ η \widehat{\rho}_k\ge\eta ρ k ≥ η and μ ∥ G ^ k ∥ ≥ Δ k \mu\lVert\widehat{G}_k\rVert\ge\Delta_k μ ∥ G k ∥ ≥ Δ k , so by Assumption 5 and ∥ H ^ k ∥ ∨ 1 ≤ κ H \lVert\widehat{H}_k\rVert\vee1\le\kappa_H ∥ H k ∥ ∨ 1 ≤ κ H ,
F ‾ k 0 − F ‾ k s ≥ η ( M ^ k ( 0 ) − M ^ k ( s ^ k ∗ ) ) ≥ η κ f c d 2 Δ k μ min { Δ k , Δ k μ κ H } = θ a Δ k 2 . \overline{F}_k^0-\overline{F}_k^{\mathsf s}\ge\eta\bigl(\widehat{M}_k(0)-\widehat{M}_k(\widehat{s}_k^*)\bigr)\ge\frac{\eta\kappa_{\mathrm{fcd}}}{2}\frac{\Delta_k}{\mu}\min\left\{\Delta_k,\frac{\Delta_k}{\mu\kappa_H}\right\}=\theta_a\Delta_k^2. F k 0 − F k s ≥ η ( M k ( 0 ) − M k ( s k ∗ ) ) ≥ 2 η κ fcd μ Δ k min { Δ k , μ κ H Δ k } = θ a Δ k 2 .
Since
F ‾ k 0 − F ‾ k s = f ( X k 0 ) − f ( X k s ) − D ‾ k ( s ^ k ∗ , N k ) , \overline{F}_k^0-\overline{F}_k^{\mathsf s}=f(X_k^0)-f(X_k^{\mathsf s})-\overline{D}_k(\widehat{s}_k^*,N_k), F k 0 − F k s = f ( X k 0 ) − f ( X k s ) − D k ( s k ∗ , N k ) ,
Lemma 5.3 gives
f ( X k 0 ) − f ( X k s ) ≥ ( θ a − κ e d F ) Δ k 2 f(X_k^0)-f(X_k^{\mathsf s})\ge(\theta_a-\kappa_{\mathrm{edF}})\Delta_k^2 f ( X k 0 ) − f ( X k s ) ≥ ( θ a − κ edF ) Δ k 2
on every successful k ≥ K U k\ge K_U k ≥ K U . Let K = { k 1 < k 2 < ⋯ } \mathcal{K}=\{k_1<k_2<\cdots\} K = { k 1 < k 2 < ⋯ } be the successful iterations with k 1 ≥ K U k_1\ge K_U k 1 ≥ K U . The iterate moves only on successes, so X k i s = X k i + 1 0 X_{k_i}^{\mathsf s}=X_{k_{i+1}}^0 X k i s = X k i + 1 0 and, summing,
( θ a − κ e d F ) ∑ k ∈ K Δ k 2 ≤ f ( X k 1 0 ) − f ∗ < ∞ . (26) (\theta_a-\kappa_{\mathrm{edF}})\sum_{k\in\mathcal{K}}\Delta_k^2\le f(X_{k_1}^0)-f^*<\infty. \tag*{(26)} ( θ a − κ edF ) k ∈ K ∑ Δ k 2 ≤ f ( X k 1 0 ) − f ∗ < ∞. (26)
Between consecutive successes the radius expands once by at most γ i n c \gamma_{\mathrm{inc}} γ inc and then contracts geometrically, so
∑ k = k i + 1 k i + 1 Δ k 2 ≤ γ i n c 2 Δ k i 2 1 − γ d e c 2 ; \sum_{k=k_i+1}^{k_{i+1}}\Delta_k^2\le\frac{\gamma_{\mathrm{inc}}^2\Delta_{k_i}^2}{1-\gamma_{\mathrm{dec}}^2}; k = k i + 1 ∑ k i + 1 Δ k 2 ≤ 1 − γ dec 2 γ inc 2 Δ k i 2 ;
the iterations before k 1 k_1 k 1 are finitely many, and if K \mathcal{K} K is finite the radii decrease geometrically after its last element. Hence S Δ < ∞ S_\Delta<\infty S Δ < ∞ . □ \square □
Lemma 6.2 (a small radius forces success). Set
κ s u c ( p ) : = min { μ , 1 κ H , κ f c d ( 1 − η ) 2 ( κ m f ( p ) + 2 κ e d F ) } . (27) \kappa_{\mathrm{suc}}(p) := \min\left\{\mu,\frac{1}{\kappa_{\mathrm{H}}},\frac{\kappa_{\mathrm{fcd}}(1-\eta)}{2(\kappa_{\mathrm{mf}}(p)+2\kappa_{\mathrm{edF}})}\right\}. \tag*{(27)} κ suc ( p ) := min { μ , κ H 1 , 2 ( κ mf ( p ) + 2 κ edF ) κ fcd ( 1 − η ) } . (27) On U k U_k U k , if Δ k ≤ κ s u c ( p k ) ∥ G ^ k ∥ \Delta_k \le\kappa_{\mathrm{suc}}(p_k)\lVert\widehat{G}_k\rVert Δ k ≤ κ suc ( p k ) ∥ G k ∥ then iteration k k k is successful. Consequently
P ( { Δ k ≤ κ s u c ( p k ) ∥ G ^ k ∥ } ∩ { k fails i.o. } ) = 0. \mathbb{P}\left(\{\Delta_k \le\kappa_{\mathrm{suc}}(p_k)\lVert\widehat{G}_k\rVert\}\cap\{k\text{ fails}\text{ i.o.}\}\right)=0. P ( { Δ k ≤ κ suc ( p k ) ∥ G k ∥} ∩ { k fails i.o. } ) = 0. Proof. The criticality test μ ∥ G ^ k ∥ ≥ Δ k \mu\lVert\widehat{G}_k\rVert\ge\Delta_k μ ∥ G k ∥ ≥ Δ k holds by the first term of (27). Write
ρ ^ k − 1 = ( f ( X k s ) − f ( X k 0 ) ) − ( M ^ k ( S ^ k ∗ ) − M ^ k ( 0 ) ) + D ‾ k ( S ^ k ∗ , N k ) M ^ k ( S ^ k ∗ ) − M ^ k ( 0 ) . \widehat{\rho}_k-1=\frac{\left(f(X_k^{s})-f(X_k^0)\right)-\left(\widehat{M}_k(\widehat{S}_k^*)-\widehat{M}_k(0)\right)+\overline{D}_k(\widehat{S}_k^*,N_k)}{\widehat{M}_k(\widehat{S}_k^*)-\widehat{M}_k(0)}. ρ k − 1 = M k ( S k ∗ ) − M k ( 0 ) ( f ( X k s ) − f ( X k 0 ) ) − ( M k ( S k ∗ ) − M k ( 0 ) ) + D k ( S k ∗ , N k ) . The numerator is bounded in absolute value by ( 1 2 κ m f ( p k ) + κ e d F ) Δ k 2 \left(\frac{1}{2}\kappa_{\mathrm{mf}}(p_k)+\kappa_{\mathrm{edF}}\right)\Delta_k^2 ( 2 1 κ mf ( p k ) + κ edF ) Δ k 2 by Lemmas 5.4 and 5.3. For the denominator, Δ k ≤ ∥ G ^ k ∥ / κ H \Delta_k\le\lVert\widehat{G}_k\rVert/\kappa_{\mathrm{H}} Δ k ≤ ∥ G k ∥ / κ H by the second term, so Assumption 5 gives
M ^ k ( 0 ) − M ^ k ( S ^ k ∗ ) ≥ 1 2 κ f c d ∥ G ^ k ∥ Δ k ≥ κ f c d 2 κ s u c ( p k ) Δ k 2 . \widehat{M}_k(0)-\widehat{M}_k(\widehat{S}_k^*)\ge\frac{1}{2}\kappa_{\mathrm{fcd}}\lVert\widehat{G}_k\rVert\Delta_k\ge\frac{\kappa_{\mathrm{fcd}}}{2\kappa_{\mathrm{suc}}(p_k)}\Delta_k^2. M k ( 0 ) − M k ( S k ∗ ) ≥ 2 1 κ fcd ∥ G k ∥ Δ k ≥ 2 κ suc ( p k ) κ fcd Δ k 2 . Hence
∣ ρ ^ k − 1 ∣ ≤ κ s u c ( p k ) ( κ m f ( p k ) + 2 κ e d F ) κ f c d ≤ 1 2 ( 1 − η ) \lvert\widehat{\rho}_k-1\rvert\le\frac{\kappa_{\mathrm{suc}}(p_k)(\kappa_{\mathrm{mf}}(p_k)+2\kappa_{\mathrm{edF}})}{\kappa_{\mathrm{fcd}}}\le\frac{1}{2}(1-\eta) ∣ ρ k − 1 ∣ ≤ κ fcd κ suc ( p k ) ( κ mf ( p k ) + 2 κ edF ) ≤ 2 1 ( 1 − η ) by the third term, so ρ ^ k ≥ η \widehat{\rho}_k\ge\eta ρ k ≥ η . The last claim is Corollary 4.8.
Alignment holds eventually when the subspace dimension grows
Lemma 6.3 (alignment eventually). If ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ then P ( A k c i . o . ) = 0 \mathbb{P}(A_k^c\ \mathrm{i.o.})=0 P ( A k c i.o. ) = 0 : there is an almost surely finite random index K A K_A K A with A k A_k A k for all k ≥ K A k\ge K_A k ≥ K A .
Proof. Observe that
P ( A k c ) = E [ P ( A k c ∣ F k − 1 ) ] ≤ 1 − β Q , k \mathbb{P}(A_k^c)=\mathbb{E}[\mathbb{P}(A_k^c\mid\mathcal{F}_{k-1})]\le1-\beta_{Q,k} P ( A k c ) = E [ P ( A k c ∣ F k − 1 )] ≤ 1 − β Q , k is summable; so apply the first Borel–Cantelli lemma. The events are not independent, since ∇ f ( X k 0 ) \nabla f(X_k^0) ∇ f ( X k 0 ) depends on Q 0 , … , Q k − 1 Q_0,\ldots,Q_{k-1} Q 0 , … , Q k − 1 , and the first lemma does not require it.
For the ensembles of Section 3.1, 1 − β Q , k = e − c Q p k 1-\beta_{Q,k}=e^{-c_Qp_k} 1 − β Q , k = e − c Q p k with c Q = α 2 / 4 c_Q=\alpha^2/4 c Q = α 2 /4 for orthonormal columns and a similar constant for Gaussian or hashing transforms [5 , 14 ] , so summability is achieved with
p k = min { d , ⌈ ( 1 + δ ) log ( k + 2 ) c Q ⌉ } = O ( log k ) , δ > 0 , (28) p_k=\min\left\{d,\left\lceil\frac{(1+\delta)\log(k+2)}{c_Q}\right\rceil\right\}=O(\log k),\qquad\delta>0, \tag*{(28)} p k = min { d , ⌈ c Q ( 1 + δ ) log ( k + 2 ) ⌉ } = O ( log k ) , δ > 0 , (28) which, with the capped bound of Proposition 3.1, gives
1 − β Q , k ≤ ( k + 2 ) − ( 1 + δ ) 1-\beta_{Q,k}\le(k+2)^{-(1+\delta)} 1 − β Q , k ≤ ( k + 2 ) − ( 1 + δ ) while p k < d p_k<d p k < d and 0 0 0 afterwards. A fixed p p p gives a fixed β Q < 1 \beta_Q<1 β Q < 1 , for which alignment need not hold eventually; what that costs is the subject of Section 8.
Lemma 6.4 (radius bounded below). Set
κ a ( p ) : = γ d e c α Q κ s u c ( p ) 1 + κ s u c ( p ) κ g ( p ) , (29) \kappa_a(p):=\frac{\gamma_{\mathrm{dec}}\alpha_Q\kappa_{\mathrm{suc}}(p)}{1+\kappa_{\mathrm{suc}}(p)\kappa_g(p)}, \tag*{(29)} κ a ( p ) := 1 + κ suc ( p ) κ g ( p ) γ dec α Q κ suc ( p ) , (29) which is nonincreasing in p p p . Under Assumptions 1–6 with ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ with { p k } \{p_k\} { p k } nondecreasing and (25), almost surely there is a finite random index K : = K U ∨ K A K:=K_U\vee K_A K := K U ∨ K A such that, for every ϵ > 0 \epsilon>0 ϵ > 0 with Δ K ≥ κ a ( p K ) ϵ \Delta_K\ge\kappa_a(p_K)\epsilon Δ K ≥ κ a ( p K ) ϵ and every integer k ˉ ≥ K \bar{k}\ge K k ˉ ≥ K ,
∥ ∇ f ( X k 0 ) ∥ ≥ ϵ for all K ≤ k ≤ k ˉ ⟹ Δ k ≥ κ a ( p k ) ϵ for all K ≤ k ≤ k ˉ . (30) \lVert\nabla f(X_k^0)\rVert\ge\epsilon\text{ for all }K\le k\le\bar{k}\quad\Longrightarrow\quad\Delta_k\ge\kappa_a(p_k)\epsilon\text{ for all }K\le k\le\bar{k}. \tag*{(30)} ∥ ∇ f ( X k 0 )∥ ≥ ϵ for all K ≤ k ≤ k ˉ ⟹ Δ k ≥ κ a ( p k ) ϵ for all K ≤ k ≤ k ˉ . (30)
Proof. Fix ω \omega ω outside the null sets of Corollary 4.8 and Lemma 6.3. The base case k = K k=K k = K is the hypothesis on ϵ \epsilon ϵ . Suppose Δ k − 1 ≥ κ a ( p k − 1 ) ϵ \Delta_{k-1}\ge\kappa_a(p_{k-1})\epsilon Δ k − 1 ≥ κ a ( p k − 1 ) ϵ for some K < k ≤ k ˉ K<k\le\bar{k} K < k ≤ k ˉ and, for contradiction, Δ k < κ a ( p k ) ϵ \Delta_k<\kappa_a(p_k)\epsilon Δ k < κ a ( p k ) ϵ . Since κ a ( p k ) ≤ κ a ( p k − 1 ) \kappa_a(p_k)\le\kappa_a(p_{k-1}) κ a ( p k ) ≤ κ a ( p k − 1 ) we have Δ k < Δ k − 1 \Delta_k<\Delta_{k-1} Δ k < Δ k − 1 , so iteration k − 1 k-1 k − 1 failed and Δ k = γ d e c Δ k − 1 \Delta_k=\gamma_{\mathrm{dec}}\Delta_{k-1} Δ k = γ dec Δ k − 1 . As k − 1 ≥ K U k-1\ge K_U k − 1 ≥ K U , Lemma 6.2 gives
Δ k − 1 > κ s u c ( p k − 1 ) ∥ G ^ k − 1 ∥ . \Delta_{k-1}>\kappa_{\mathrm{suc}}(p_{k-1})\lVert\widehat{G}_{k-1}\rVert. Δ k − 1 > κ suc ( p k − 1 ) ∥ G k − 1 ∥ .
As k − 1 ≥ K A k-1\ge K_A k − 1 ≥ K A , A k − 1 A_{k-1} A k − 1 holds, so by Lemmas 5.1 and 5.2
∥ G ^ k − 1 ∥ ≥ ∥ ∇ f ^ k − 1 ( 0 ) ∥ − κ g ( p k − 1 ) Δ k − 1 ≥ α Q ϵ − κ g ( p k − 1 ) Δ k − 1 . \lVert\widehat{G}_{k-1}\rVert\ge\lVert\nabla\widehat{f}_{k-1}(0)\rVert-\kappa_g(p_{k-1})\Delta_{k-1}\ge\alpha_Q\epsilon-\kappa_g(p_{k-1})\Delta_{k-1}. ∥ G k − 1 ∥ ≥ ∥ ∇ f k − 1 ( 0 )∥ − κ g ( p k − 1 ) Δ k − 1 ≥ α Q ϵ − κ g ( p k − 1 ) Δ k − 1 .
Combining,
Δ k − 1 ( 1 + κ s u c ( p k − 1 ) κ g ( p k − 1 ) ) > κ s u c ( p k − 1 ) α Q ϵ ⇒ Δ k − 1 > κ a ( p k − 1 ) ϵ / γ d e c , \Delta_{k-1}(1+\kappa_{\mathrm{suc}}(p_{k-1})\kappa_g(p_{k-1}))>\kappa_{\mathrm{suc}}(p_{k-1})\alpha_Q\epsilon\ \Rightarrow\ \Delta_{k-1}>\kappa_a(p_{k-1})\epsilon/\gamma_{\mathrm{dec}}, Δ k − 1 ( 1 + κ suc ( p k − 1 ) κ g ( p k − 1 )) > κ suc ( p k − 1 ) α Q ϵ ⇒ Δ k − 1 > κ a ( p k − 1 ) ϵ / γ dec ,
whence
Δ k = γ d e c Δ k − 1 > κ a ( p k − 1 ) ϵ ≥ κ a ( p k ) ϵ , \Delta_k=\gamma_{\mathrm{dec}}\Delta_{k-1}>\kappa_a(p_{k-1})\epsilon\ge\kappa_a(p_k)\epsilon, Δ k = γ dec Δ k − 1 > κ a ( p k − 1 ) ϵ ≥ κ a ( p k ) ϵ ,
which is a contradiction.
The induction runs on every index k − 1 ≥ K k-1\ge K k − 1 ≥ K , and it needs alignment at every one of them; that is exactly why ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ is the natural hypothesis of this route.
Theorem 6.5 (strong consistency). Under Assumptions 1–6 with { p k } \{p_k\} { p k } nondecreasing, p k ≤ d p_k\le d p k ≤ d , and ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ (which (28) achieves for the ensembles of Section 3.1), almost surely
lim k → ∞ ∥ ∇ f ( X k 0 ) ∥ = 0. \lim_{k\to\infty}\lVert\nabla f(X_k^0)\rVert=0. k → ∞ lim ∥ ∇ f ( X k 0 )∥ = 0.
Proof. Fix ω \omega ω outside the relevant null sets.
Suppose ∥ ∇ f ( X k 0 ) ∥ ≥ ϵ \lVert\nabla f(X_k^0)\rVert\ge\epsilon ∥ ∇ f ( X k 0 )∥ ≥ ϵ for all k ≥ k ˉ k\ge\bar{k} k ≥ k ˉ and some ϵ > 0 \epsilon>0 ϵ > 0 . Enlarging K K K to K ∨ k ˉ K\vee\bar{k} K ∨ k ˉ and shrinking ϵ \epsilon ϵ so that the base case of Lemma 6.4 holds, Δ k ≥ κ a ( p k ) ϵ \Delta_k\ge\kappa_a(p_k)\epsilon Δ k ≥ κ a ( p k ) ϵ for all k ≥ K k\ge K k ≥ K . By (23), (27), and (29), since κ a \kappa_a κ a is nonincreasing and p k ≤ d p_k\le d p k ≤ d , κ a ( p k ) ≥ κ a ( d ) > 0 \kappa_a(p_k)\ge\kappa_a(d)>0 κ a ( p k ) ≥ κ a ( d ) > 0 , so ∑ k ≥ K Δ k 2 ≥ ϵ 2 ∑ k ≥ K κ a 2 ( d ) = ∞ \sum_{k\ge K}\Delta_k^2\ge\epsilon^2\sum_{k\ge K}\kappa_a^2(d)=\infty ∑ k ≥ K Δ k 2 ≥ ϵ 2 ∑ k ≥ K κ a 2 ( d ) = ∞ , contradicting Lemma 6.1. So
∑ k ≥ K Δ k 2 ≥ ϵ 2 ∑ k ≥ K κ a 2 ( p k ) = ∞ , \sum_{k\ge K}\Delta_k^2\ge\epsilon^2\sum_{k\ge K}\kappa_a^2(p_k)=\infty, k ≥ K ∑ Δ k 2 ≥ ϵ 2 k ≥ K ∑ κ a 2 ( p k ) = ∞ ,
contradicting Lemma 6.1. Hence lim inf k ∥ ∇ f ( X k 0 ) ∥ = 0 \liminf_k\lVert\nabla f(X_k^0)\rVert=0 lim inf k ∥ ∇ f ( X k 0 )∥ = 0 .
Now, suppose lim sup k ∥ ∇ f ( X k 0 ) ∥ > 2 ϵ > 0 \limsup_k\lVert\nabla f(X_k^0)\rVert>2\epsilon>0 lim sup k ∥ ∇ f ( X k 0 )∥ > 2 ϵ > 0 . Then there are infinitely many t j t_j t j with ∥ ∇ f ( X t j 0 ) ∥ > 2 ϵ \lVert\nabla f(X_{t_j}^0)\rVert>2\epsilon ∥ ∇ f ( X t j 0 )∥ > 2 ϵ and, by the first part, for each t j t_j t j a first ℓ j > t j \ell_j>t_j ℓ j > t j with ∥ ∇ f ( X ℓ j 0 ) ∥ ≤ ϵ \lVert\nabla f(X_{\ell_j}^0)\rVert\le\epsilon ∥ ∇ f ( X ℓ j 0 )∥ ≤ ϵ . On the window t j ≤ k < ℓ j t_j\le k<\ell_j t j ≤ k < ℓ j we have ∥ ∇ f ( X k 0 ) ∥ > ϵ \lVert\nabla f(X_k^0)\rVert>\epsilon ∥ ∇ f ( X k 0 )∥ > ϵ . Since κ g ( p k ) ≤ κ g ( d ) \kappa_g(p_k)\le\kappa_g(d) κ g ( p k ) ≤ κ g ( d ) and Δ k → 0 \Delta_k\to0 Δ k → 0 , κ g ( p k ) Δ k → 0 \kappa_g(p_k)\Delta_k\to0 κ g ( p k ) Δ k → 0 ; hence for all large j j j and all k k k in the window,
∥ G ^ k ∥ ≥ α Q ϵ − κ g ( p k ) Δ k ≥ 1 2 α Q ϵ \lVert\widehat{G}_k\rVert\ge\alpha_Q\epsilon-\kappa_g(p_k)\Delta_k\ge\frac{1}{2}\alpha_Q\epsilon ∥ G k ∥ ≥ α Q ϵ − κ g ( p k ) Δ k ≥ 2 1 α Q ϵ
by Lemma 5.2 and A k A_k A k . On a successful k k k in the window, Assumption 5, Lemma 5.3 and ρ ^ k ≥ η \widehat{\rho}_k\ge\eta ρ k ≥ η give
f ( X k 0 ) − f ( X k s ) ≥ η ( M ^ k ( 0 ) − M ^ k ( S ^ k ∗ ) ) − κ e d F Δ k 2 ≥ η κ f c d α Q ϵ 4 min { Δ k , α Q ϵ 2 κ H } − κ e d F Δ k 2 ≥ c ϵ Δ k f(X_k^0)-f(X_k^s)\ge\eta(\widehat{M}_k(0)-\widehat{M}_k(\widehat{S}_k^*))-\kappa_{\mathrm{ed}F}\Delta_k^2\ge\frac{\eta\kappa_{fcd}\alpha_Q\epsilon}{4}\min\left\{\Delta_k,\frac{\alpha_Q\epsilon}{2\kappa_H}\right\}-\kappa_{\mathrm{ed}F}\Delta_k^2\ge c_\epsilon\Delta_k f ( X k 0 ) − f ( X k s ) ≥ η ( M k ( 0 ) − M k ( S k ∗ )) − κ ed F Δ k 2 ≥ 4 η κ f c d α Q ϵ min { Δ k , 2 κ H α Q ϵ } − κ ed F Δ k 2 ≥ c ϵ Δ k
with c ϵ : = η κ f c d α Q ϵ / 8 c_\epsilon:=\eta\kappa_{fcd}\alpha_Q\epsilon/8 c ϵ := η κ f c d α Q ϵ /8 , once
Δ k ≤ min { α Q ϵ 2 κ H , c ϵ κ e d F } , \Delta_k\le\min\left\{\frac{\alpha_Q\epsilon}{2\kappa_H},\frac{c_\epsilon}{\kappa_{\mathrm{ed}F}}\right\}, Δ k ≤ min { 2 κ H α Q ϵ , κ ed F c ϵ } ,
which holds for large j j j because Δ k → 0 \Delta_k\to0 Δ k → 0 . The iterate moves only on successes and ∥ X k s − X k 0 ∥ ≤ κ Q Δ k \lVert X_k^s-X_k^0\rVert\le\kappa_Q\Delta_k ∥ X k s − X k 0 ∥ ≤ κ Q Δ k , so
∥ X ℓ j 0 − X t j 0 ∥ ≤ κ Q ∑ t j ≤ k < ℓ j k s u c c e s s f u l Δ k ≤ κ Q c ϵ ( f ( X t j 0 ) − f ( X ℓ j 0 ) ) . \lVert X_{\ell_j}^0-X_{t_j}^0\rVert\le\kappa_Q\sum_{\substack{t_j\le k<\ell_j\\ k\ \mathrm{successful}}}\Delta_k\le\frac{\kappa_Q}{c_\epsilon}\left(f(X_{t_j}^0)-f(X_{\ell_j}^0)\right). ∥ X ℓ j 0 − X t j 0 ∥ ≤ κ Q t j ≤ k < ℓ j k successful ∑ Δ k ≤ c ϵ κ Q ( f ( X t j 0 ) − f ( X ℓ j 0 ) ) .
By (26), f ( X k 0 ) f(X_k^0) f ( X k 0 ) is nonincreasing along successes from K U K_U K U on and bounded below, hence convergent, so the right side tends to zero as j → ∞ j\to\infty j → ∞ . But ∥ ∇ f ( X t j 0 ) − ∇ f ( X ℓ j 0 ) ∥ > ϵ \lVert\nabla f(X_{t_j}^0)-\nabla f(X_{\ell_j}^0)\rVert>\epsilon ∥ ∇ f ( X t j 0 ) − ∇ f ( X ℓ j 0 )∥ > ϵ and Assumption 1 give ∥ X ℓ j 0 − X t j 0 ∥ > ϵ / κ L g \lVert X_{\ell_j}^0-X_{t_j}^0\rVert>\epsilon/\kappa_{Lg} ∥ X ℓ j 0 − X t j 0 ∥ > ϵ / κ Lg , which is a contradiction.
Complexity
Let T ϵ : = inf { k : ∥ ∇ f ( X k 0 ) ∥ ≤ ϵ } T_{\epsilon} := \inf\{k : \lVert\nabla f(X_k^0)\rVert\le\epsilon\} T ϵ := inf { k : ∥ ∇ f ( X k 0 )∥ ≤ ϵ } , finite almost surely by Theorem 6.5 , and W ϵ : = ∑ k < T ϵ ( 2 p k + 2 ) N k W_{\epsilon} := \sum_{k<T_{\epsilon}} (2p_k+2)N_k W ϵ := ∑ k < T ϵ ( 2 p k + 2 ) N k .
A first statement, with no machinery
The following is the fixed-threshold bound that the pathwise route gives immediately.
Theorem 7.1 (fixed-threshold iteration bound). Under the hypotheses of Theorem 6.5 , for every ϵ > 0 \epsilon> 0 ϵ > 0 there is an almost surely finite random integer N ϵ \mathcal{N}_{\epsilon} N ϵ such that
P ( T ϵ ϵ 2 ≤ S Δ + N ϵ ϵ 2 ) = 1. (31) \mathbb{P}\left(T_{\epsilon}\epsilon^2 \le S_{\Delta}+\mathcal{N}_{\epsilon}\epsilon^2\right)=1. \tag*{(31)} P ( T ϵ ϵ 2 ≤ S Δ + N ϵ ϵ 2 ) = 1. (31)
Proof. Every k < T ϵ k<T_{\epsilon} k < T ϵ has ∥ ∇ f ( X k 0 ) ∥ > ϵ \lVert\nabla f(X_k^0)\rVert> \epsilon ∥ ∇ f ( X k 0 )∥ > ϵ . Split these indices into
L ϵ : = { k < T ϵ : Δ k < ϵ } and G ϵ : = { k < T ϵ : Δ k ≥ ϵ } . \mathcal{L}_{\epsilon}:=\{k<T_{\epsilon}:\Delta_k<\epsilon\}
\qquad\text{and}\qquad
\mathcal{G}_{\epsilon}:=\{k<T_{\epsilon}:\Delta_k\ge\epsilon\}. L ϵ := { k < T ϵ : Δ k < ϵ } and G ϵ := { k < T ϵ : Δ k ≥ ϵ } .
By Theorem 6.5 and Lemma 6.1, both ∥ ∇ f ( X k 0 ) ∥ → 0 \lVert\nabla f(X_k^0)\rVert\to0 ∥ ∇ f ( X k 0 )∥ → 0 and Δ k → 0 \Delta_k\to0 Δ k → 0 , so N ϵ : = ∣ { k : ∥ ∇ f ( X k 0 ) ∥ > ϵ , Δ k < ϵ } ∣ < ∞ \mathcal{N}_{\epsilon}:=\lvert\{k:\lVert\nabla f(X_k^0)\rVert>\epsilon,\ \Delta_k<\epsilon\}\rvert<\infty N ϵ := ∣{ k : ∥ ∇ f ( X k 0 )∥ > ϵ , Δ k < ϵ }∣ < ∞ almost surely and ∣ L ϵ ∣ ≤ N ϵ \lvert\mathcal{L}_{\epsilon}\rvert\le\mathcal{N}_{\epsilon} ∣ L ϵ ∣ ≤ N ϵ ; and ϵ 2 ∣ G ϵ ∣ ≤ ∑ k ∈ G ϵ Δ k 2 ≤ S Δ \epsilon^2\lvert\mathcal{G}_{\epsilon}\rvert\le\sum_{k\in\mathcal{G}_{\epsilon}}\Delta_k^2\le S_{\Delta} ϵ 2 ∣ G ϵ ∣ ≤ ∑ k ∈ G ϵ Δ k 2 ≤ S Δ . Adding gives (31).
The statement is honest about what the pathwise route gives for free: the constant N ϵ \mathcal{N}_{\epsilon} N ϵ is finite for each ϵ \epsilon ϵ but may depend on ϵ \epsilon ϵ , so (31) is not yet a rate. Making N ϵ \mathcal{N}_{\epsilon} N ϵ independent of ϵ \epsilon ϵ is exactly what the radius lower bound of Lemma 6.4 does, at the price of κ a − 2 \kappa_a^{-2} κ a − 2 and of alignment at every iteration.
Iteration and sample complexity
Theorem 7.2 (iteration complexity). Under the hypotheses of Theorem 6.5 there is an almost surely finite random variable R > 0 R>0 R > 0 such that, for every deterministic sequence ϵ ℓ ↓ 0 \epsilon_{\ell}\downarrow0 ϵ ℓ ↓ 0 ,
P ( T ϵ ℓ ϵ ℓ 2 κ a 2 ( p T ϵ ℓ ) > R i . o . ) = 0. (32) \mathbb{P}\left(T_{\epsilon_{\ell}}\epsilon_{\ell}^2\kappa_a^2(p_{T_{\epsilon_{\ell}}})>R\ \mathrm{i.o.}\right)=0. \tag*{(32)} P ( T ϵ ℓ ϵ ℓ 2 κ a 2 ( p T ϵ ℓ ) > R i.o. ) = 0. (32)
With p k p_k p k as in (28) this implies
T ϵ = O ( π a ϵ − 2 log ( 1 / ϵ ) ) = O ~ ( π a ϵ − 2 ) T_{\epsilon}=O\left(\pi_a\epsilon^{-2}\log(1/\epsilon)\right)=\widetilde{O}\left(\pi_a\epsilon^{-2}\right) T ϵ = O ( π a ϵ − 2 log ( 1/ ϵ ) ) = O ( π a ϵ − 2 )
almost surely, where
π a : = sup p κ a − 2 ( p ) / p \pi_a:=\sup_p\kappa_a^{-2}(p)/p π a := p sup κ a − 2 ( p ) / p
collects the dependence on the remaining constants.
Proof. Fix ω \omega ω outside the relevant null sets, let K K K be as in Lemma 6.4 . If T ϵ T_{\epsilon} T ϵ stays bounded as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 (an exact stationary point is reached), T ϵ ϵ 2 → 0 T_{\epsilon}\epsilon^2\to0 T ϵ ϵ 2 → 0 and there is nothing to prove; otherwise take ϵ \epsilon ϵ small enough that K < T ϵ K<T_{\epsilon} K < T ϵ and the base case holds. For K ≤ k < T ϵ K\le k<T_{\epsilon} K ≤ k < T ϵ , ∥ ∇ f ( X k 0 ) ∥ > ϵ \lVert\nabla f(X_k^0)\rVert>\epsilon ∥ ∇ f ( X k 0 )∥ > ϵ , so Δ k ≥ κ a ( p k ) ϵ ≥ κ a ( p T ϵ ) ϵ \Delta_k\ge\kappa_a(p_k)\epsilon\ge\kappa_a(p_{T_{\epsilon}})\epsilon Δ k ≥ κ a ( p k ) ϵ ≥ κ a ( p T ϵ ) ϵ by monotonicity, and
( T ϵ − K ) κ a 2 ( p T ϵ ) ϵ 2 ≤ ∑ k = K T ϵ − 1 Δ k 2 ≤ S Δ ⇒ T ϵ ≤ S Δ κ a − 2 ( p T ϵ ) ϵ − 2 + K . (T_{\epsilon}-K)\kappa_a^2(p_{T_{\epsilon}})\epsilon^2
\le\sum_{k=K}^{T_{\epsilon}-1}\Delta_k^2\le S_{\Delta}
\quad\Rightarrow\quad
T_{\epsilon}\le S_{\Delta}\kappa_a^{-2}(p_{T_{\epsilon}})\epsilon^{-2}+K. ( T ϵ − K ) κ a 2 ( p T ϵ ) ϵ 2 ≤ k = K ∑ T ϵ − 1 Δ k 2 ≤ S Δ ⇒ T ϵ ≤ S Δ κ a − 2 ( p T ϵ ) ϵ − 2 + K .
Since the first term tends to infinity as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 , K K K is absorbed and (32) holds with R : = S Δ + K κ a 2 ( p K ) R:=S_{\Delta}+K\kappa_a^2(p_K) R := S Δ + K κ a 2 ( p K ) . For the rate, T ϵ ϵ 2 ≤ R π a p T ϵ T_{\epsilon}\epsilon^2\le R\pi_ap_{T_{\epsilon}} T ϵ ϵ 2 ≤ R π a p T ϵ and p T ϵ ≤ c log ( T ϵ + 2 ) p_{T_{\epsilon}}\le c\log(T_{\epsilon}+2) p T ϵ ≤ c log ( T ϵ + 2 ) ; with t : = T ϵ ϵ 2 t:=T_{\epsilon}\epsilon^2 t := T ϵ ϵ 2 this means t ≤ c π a log ( t ϵ − 2 ) t\le c\pi_a\log(t\epsilon^{-2}) t ≤ c π a log ( t ϵ − 2 ) , which forces t = O ( π a log ( 1 / ϵ ) ) t=O(\pi_a\log(1/\epsilon)) t = O ( π a log ( 1/ ϵ )) .
Lemma 7.3 (realized sample size). Let Assumptions 2 and 7 hold, and S Δ < ∞ S_{\Delta}<\infty S Δ < ∞ almost surely. Suppose further that p k / λ k p_k/\lambda_k p k / λ k is bounded. There are a deterministic n W < ∞ n_W<\infty n W < ∞ and an almost surely finite random index K W K_W K W such that N k ≤ n W λ k Δ k − 2 N_k\le n_W\lambda_k\Delta_k^{-2} N k ≤ n W λ k Δ k − 2 for all $k\ge K_W.
Proof. Fix ε ′ ∈ ( 0 , 1 ) \varepsilon' \in(0,1) ε ′ ∈ ( 0 , 1 ) and let
n k † : = ⌈ ( 1 + ε ′ ) λ k κ a − 2 Δ k − 2 ( σ 0 2 ∨ c 4 1 / 2 ) ⌉ . n_k^\dagger:= \left\lceil(1+\varepsilon')\lambda_k\kappa_a^{-2}\Delta_k^{-2}\left(\sigma_0^2 \vee c_4^{1/2}\right)\right\rceil. n k † := ⌈ ( 1 + ε ′ ) λ k κ a − 2 Δ k − 2 ( σ 0 2 ∨ c 4 1/2 ) ⌉ .
Since σ F 2 ( x ) ≤ c 4 1 / 2 \sigma_F^2(x) \le c_4^{1/2} σ F 2 ( x ) ≤ c 4 1/2 by Jensen, the event { N k > n k † } \{N_k > n_k^\dagger\} { N k > n k † } forces
σ ^ F 2 ( X k i , n k † ) − σ F 2 ( X k i ) > ε ′ σ 0 2 \widehat{\sigma}_F^2(X_k^i,n_k^\dagger)-\sigma_F^2(X_k^i)>\varepsilon'\sigma_0^2 σ F 2 ( X k i , n k † ) − σ F 2 ( X k i ) > ε ′ σ 0 2
at one of the 2 p k + 1 2p_k+1 2 p k + 1 design points. Conditionally on F k − 1 Q \mathcal{F}_{k-1}^{Q} F k − 1 Q (Lemma 4.1 ), a union bound and Chebyshev’s inequality with E ∣ σ ^ n 2 − σ 2 ∣ 2 ≤ c ′ / n \mathbb{E}|\widehat{\sigma}_n^2-\sigma^2|^2\le c'/n E ∣ σ n 2 − σ 2 ∣ 2 ≤ c ′ / n , valid under a fourth moment with c ′ c' c ′ depending only on c 4 c_4 c 4 , give
P ( N k > n k † ∣ F k − 1 Q ) ≤ ( 2 p k + 1 ) c ′ ( ε ′ σ 0 2 ) 2 n k † ≤ c ′ ′ 2 p k + 1 λ k Δ k 2 . \mathbb{P}\left(N_k>n_k^\dagger\mid\mathcal{F}_{k-1}^{Q}\right)\le\frac{(2p_k+1)c'}{(\varepsilon'\sigma_0^2)^2n_k^\dagger}\le c''\frac{2p_k+1}{\lambda_k}\Delta_k^2. P ( N k > n k † ∣ F k − 1 Q ) ≤ ( ε ′ σ 0 2 ) 2 n k † ( 2 p k + 1 ) c ′ ≤ c ′′ λ k 2 p k + 1 Δ k 2 .
The right side is F k − 1 \mathcal{F}_{k-1} F k − 1 -measurable so the same bound holds conditionally on F k − 1 \mathcal{F}_{k-1} F k − 1 by the tower property. Moreover, ( 2 p k + 1 ) / λ k (2p_k+1)/\lambda_k ( 2 p k + 1 ) / λ k is bounded because p k = O ( log k ) p_k=O(\log k) p k = O ( log k ) , so its sum over k k k is at most a constant times S Δ < ∞ S_\Delta<\infty S Δ < ∞ . Lévy’s extension of the Borel–Cantelli lemma for { F k − 1 } \{\mathcal{F}_{k-1}\} { F k − 1 } gives N k ≤ n k † N_k\le n_k^\dagger N k ≤ n k † for all k ≥ K W k\ge K_W k ≥ K W with K W K_W K W almost surely finite, and n k † ≤ n W λ k Δ k − 2 n_k^\dagger\le n_W\lambda_k\Delta_k^{-2} n k † ≤ n W λ k Δ k − 2 after absorbing the ceiling with λ k Δ k − 2 ≥ λ 0 Δ max − 2 \lambda_k\Delta_k^{-2}\ge\lambda_0\Delta_{\max}^{-2} λ k Δ k − 2 ≥ λ 0 Δ m a x − 2 .
Theorem 7.4 (sample complexity). Under the hypotheses of Theorem 6.5 and Assumption 7 , there is an almost surely finite random variable R W > 0 R_W>0 R W > 0 such that, for every deterministic ϵ ℓ ↓ 0 \epsilon_\ell\downarrow0 ϵ ℓ ↓ 0 ,
P ( W ϵ ℓ > R W ( 2 p T ϵ ℓ + 2 ) λ T ϵ ℓ κ a − 4 ( p T ϵ ℓ ) ϵ ℓ − 4 i . o . ) = 0 , (33) \mathbb{P}\left(W_{\epsilon_\ell}>R_W(2p_{T_{\epsilon_\ell}}+2)\lambda_{T_{\epsilon_\ell}}\kappa_a^{-4}(p_{T_{\epsilon_\ell}})\epsilon_\ell^{-4}\ \mathrm{i.o.}\right)=0, \tag*{(33)} P ( W ϵ ℓ > R W ( 2 p T ϵ ℓ + 2 ) λ T ϵ ℓ κ a − 4 ( p T ϵ ℓ ) ϵ ℓ − 4 i.o. ) = 0 , (33) and hence W ϵ = O ~ ( π a 2 ϵ − 4 ) W_\epsilon=\widetilde{O}(\pi_a^2\epsilon^{-4}) W ϵ = O ( π a 2 ϵ − 4 ) almost surely.
Proof. Fix ω \omega ω and let K W : = K ∨ K W K_W:=K\vee K_W K W := K ∨ K W . If T ϵ T_\epsilon T ϵ stays bounded as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 (an exact stationary point is reached), T ϵ ϵ 2 → 0 T_\epsilon\epsilon^2\to0 T ϵ ϵ 2 → 0 and there is nothing to prove; otherwise take ϵ \epsilon ϵ small enough that K < T ϵ K<T_\epsilon K < T ϵ . Split
W ϵ = ∑ k < K W ( 2 p k + 2 ) N k + ∑ k = K W T ϵ − 1 ( 2 p k + 2 ) N k , W_\epsilon=\sum_{k<K_W}(2p_k+2)N_k+\sum_{k=K_W}^{T_\epsilon-1}(2p_k+2)N_k, W ϵ = k < K W ∑ ( 2 p k + 2 ) N k + k = K W ∑ T ϵ − 1 ( 2 p k + 2 ) N k ,
the first sum a finite random number Q W Q_W Q W . For K W ≤ k < T ϵ K_W\le k<T_\epsilon K W ≤ k < T ϵ , Lemma 7.3 and Lemma 6.4 give
N k ≤ n W λ k κ a − 2 ( p k ) ϵ − 2 , N_k\le n_W\lambda_k\kappa_a^{-2}(p_k)\epsilon^{-2}, N k ≤ n W λ k κ a − 2 ( p k ) ϵ − 2 ,
and p k , λ k , κ a − 2 ( p k ) p_k,\lambda_k,\kappa_a^{-2}(p_k) p k , λ k , κ a − 2 ( p k ) are nondecreasing, so the second sum is at most
( 2 p T ϵ + 2 ) n W λ T ϵ κ a − 2 ( p T ϵ ) ϵ − 2 T ϵ . (2p_{T_\epsilon}+2)n_W\lambda_{T_\epsilon}\kappa_a^{-2}(p_{T_\epsilon})\epsilon^{-2}T_\epsilon. ( 2 p T ϵ + 2 ) n W λ T ϵ κ a − 2 ( p T ϵ ) ϵ − 2 T ϵ .
Substituting T ϵ ≤ S Δ κ a − 2 ( p T ϵ ) ϵ − 2 + K T_\epsilon\le S_\Delta\kappa_a^{-2}(p_{T_\epsilon})\epsilon^{-2}+K T ϵ ≤ S Δ κ a − 2 ( p T ϵ ) ϵ − 2 + K from the proof of Theorem 7.2 gives (33) with R W : = 2 n W S Δ + Q W R_W:=2n_WS_\Delta+Q_W R W := 2 n W S Δ + Q W , the additive terms being absorbed as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 . For the rate, p T ϵ p_{T_\epsilon} p T ϵ , λ T ϵ \lambda_{T_\epsilon} λ T ϵ and κ a − 2 ( p T ϵ ) / π a \kappa_a^{-2}(p_{T_\epsilon})/\pi_a κ a − 2 ( p T ϵ ) / π a are polylogarithmic in 1 / ϵ 1/\epsilon 1/ ϵ by Theorem 7.2 .
Remark 9 (on the form of the statements). Both results are almost sure, with a random constant valid for ϵ \epsilon ϵ below a random threshold, and they are stated in the "infinitely often along a deterministic sequence" form because ϵ 0 ( ω ) \epsilon_0(\omega) ϵ 0 ( ω ) is random. This is the natural currency of the route, and we do not present the absence of expected bounds as a deficiency: the accuracy guarantee itself is an eventual statement, and everything downstream is deterministic along a fixed path. R R R and R W R_W R W contain the burn-in indices. Proposition 7.5 gives K U K_U K U moments of every order and K A K_A K A moments of order below δ \delta δ ; since S Δ ≤ a 1 + a 2 K U S_\Delta\le a_1+a_2K_U S Δ ≤ a 1 + a 2 K U under the hypotheses of Theorem 7.6 , R R R is integrable when δ > 1 \delta>1 δ > 1 , while nothing is claimed for R W R_W R W , as no tail bound for K W K_W K W is given. What prevents a bound in expectation is not the constant but the random threshold ϵ 0 ( ω ) \epsilon_0(\omega) ϵ 0 ( ω ) : the threshold-free form (35) carries the factor γ d e c − 2 K / Δ 0 2 \gamma_{\mathrm{dec}}^{-2K}/\Delta_0^2 γ dec − 2 K / Δ 0 2 , which is not integrable. Part I obtains expected bounds, for fixed p p p , from its per-iteration probability bound.
The burn-in is not arbitrarily late: tails and a finite-time bound
A natural objection to almost sure statements is that they are asymptotic: the good events hold from some K ( ω ) K(\omega) K ( ω ) on, and nothing seems to be said about how late K ( ω ) K(\omega) K ( ω ) can be, whereas an expected bound controls the tail of T ϵ T_{\epsilon} T ϵ through Markov’s inequality. The objection does not survive a look at how K ( ω ) K(\omega) K ( ω ) was constructed. It is the last index at which an event with an explicitly summable failure probability fails, so its tail is bounded by the tail of the series one sums in Borel–Cantelli, which is deterministic and available.
Proposition 7.5 (tail of the burn-in). Under the hypotheses of Theorem 6.5 , for every k ≥ k λ k \ge k_{\lambda} k ≥ k λ and K U : = 1 + sup { k : U k c } K_U := 1 + \sup\{k : U_k^c\} K U := 1 + sup { k : U k c } and K A : = 1 + sup { k : A k c } K_A := 1 + \sup\{k : A_k^c\} K A := 1 + sup { k : A k c } ,
P ( K U > k ) ≤ ∑ j ≥ k e − c F λ j , P ( K A > k ) ≤ ∑ j ≥ k ( 1 − β Q , j ) , (34) \mathbb{P}(K_U > k) \le\sum_{j \ge k} e^{-c_F\lambda_j}, \qquad\mathbb{P}(K_A > k) \le\sum_{j \ge k}(1-\beta_{Q,j}), \tag*{(34)} P ( K U > k ) ≤ j ≥ k ∑ e − c F λ j , P ( K A > k ) ≤ j ≥ k ∑ ( 1 − β Q , j ) , (34) and P ( K A > k ) = 0 \mathbb{P}(K_A > k)=0 P ( K A > k ) = 0 for k ≥ k d : = min { k : p k = d } k \ge k_d := \min\{k : p_k=d\} k ≥ k d := min { k : p k = d } for the ensemble of Proposition 3.1 with (28). With λ j = λ 0 ( log ( j + 2 ) ) 1 + ϵ λ \lambda_j=\lambda_0(\log(j+2))^{1+\epsilon_{\lambda}} λ j = λ 0 ( log ( j + 2 ) ) 1 + ϵ λ the first series is at most $2k e^{-c_F\lambda_k}∗ f o r a l l l a r g e ∗ *for all large* ∗ f or a l l l a r g e ∗ k, which decays faster than any power of $k, so E [ K U m ] < ∞ \mathbb{E}[K_U^m]<\infty E [ K U m ] < ∞ for every $m; with p k p_k p k as in (28), the second is at most k − δ / δ k^{-\delta}/\delta k − δ / δ , so E [ K A ] < ∞ \mathbb{E}[K_A]<\infty E [ K A ] < ∞ when δ > 1 \delta>1 δ > 1 .
Proof. By Theorem 4.7
{ K U > k } = { ∃ j ≥ k : U j c } ⊆ ⋃ j ≥ k U j c \{K_U>k\}=\{\exists j\ge k:U_j^c\}\subseteq\bigcup_{j\ge k}U_j^c { K U > k } = { ∃ j ≥ k : U j c } ⊆ j ≥ k ⋃ U j c
and
P ( U j c ) ≤ e − c F λ j \mathbb{P}(U_j^c)\le e^{-c_F\lambda_j} P ( U j c ) ≤ e − c F λ j
for j ≥ k λ j\ge k_{\lambda} j ≥ k λ ; likewise for K A K_A K A with Lemma 6.3 . Writing e − c F λ j = ( j + 2 ) − a j e^{-c_F\lambda_j}=(j+2)^{-a_j} e − c F λ j = ( j + 2 ) − a j with
a j : = c F λ 0 ( log ( j + 2 ) ) ϵ λ → ∞ , a_j:=c_F\lambda_0(\log(j+2))^{\epsilon_{\lambda}}\to\infty, a j := c F λ 0 ( log ( j + 2 ) ) ϵ λ → ∞ ,
for k k k large enough that a k ≥ 2 a_k\ge2 a k ≥ 2 one has
∑ j ≥ k ( j + 2 ) − a j ≤ ∑ j ≥ k ( j + 2 ) − a k ≤ k − a k ( 1 + k a k − 1 ) ≤ 2 k e − c F λ k . \sum_{j\ge k}(j+2)^{-a_j}\le\sum_{j\ge k}(j+2)^{-a_k}\le k^{-a_k}\left(1+\frac{k}{a_k-1}\right)\le2k e^{-c_F\lambda_k}. j ≥ k ∑ ( j + 2 ) − a j ≤ j ≥ k ∑ ( j + 2 ) − a k ≤ k − a k ( 1 + a k − 1 k ) ≤ 2 k e − c F λ k .
The moments follow from E [ K m ] = ∑ k P ( K m > k ) \mathbb{E}[K^m]=\sum_k\mathbb{P}(K^m>k) E [ K m ] = ∑ k P ( K m > k ) . For K A K_A K A ,
∑ j ≥ k ( j + 2 ) − ( 1 + δ ) ≤ k − δ / δ . \sum_{j\ge k}(j+2)^{-(1+\delta)}\le k^{-\delta}/\delta. j ≥ k ∑ ( j + 2 ) − ( 1 + δ ) ≤ k − δ / δ .
The proposition converts the almost sure statements into finite-time ones. We record the iteration bound.
Theorem 7.6 (finite-time, high-probability iteration bound). Let the hypotheses of Theorem 6.5 hold and let in addition f f f be κ L f \kappa_{L_f} κ L f -Lipschitz. Set c Δ : = γ i n c 2 / ( 1 − γ d e c 2 ) c_{\Delta}:=\gamma_{\mathrm{inc}}^2/(1-\gamma_{\mathrm{dec}}^2) c Δ := γ inc 2 / ( 1 − γ dec 2 ) and
a 1 : = c Δ ( Δ 0 2 γ d e c 2 + f ( x 0 ) − f ∗ θ a − κ e d F ) , a 2 : = c Δ ( Δ max 2 + κ L f κ Q Δ max θ a − κ e d F ) , a_1:=c_{\Delta}\left(\frac{\Delta_0^2}{\gamma_{\mathrm{dec}}^2}+\frac{f(x_0)-f^*}{\theta_a-\kappa_{\mathrm{ed}}F}\right),\qquad
a_2:=c_{\Delta}\left(\Delta_{\max}^2+\frac{\kappa_{L_f}\kappa_Q\Delta_{\max}}{\theta_a-\kappa_{\mathrm{ed}}F}\right), a 1 := c Δ ( γ dec 2 Δ 0 2 + θ a − κ ed F f ( x 0 ) − f ∗ ) , a 2 := c Δ ( Δ m a x 2 + θ a − κ ed F κ L f κ Q Δ m a x ) , both deterministic. Then, almost surely, for every ϵ > 0 \epsilon>0 ϵ > 0 and with K = K U ∨ K A K=K_U\vee K_A K = K U ∨ K A ,
T ϵ ≤ K + ( a 1 + a 2 K U ) ( γ d e c − 2 K Δ 0 2 + 1 κ a 2 ( p T ϵ ) ϵ 2 ) , (35) T_{\epsilon}\le K+(a_1+a_2K_U)\left(\frac{\gamma_{\mathrm{dec}}^{-2K}}{\Delta_0^2}+\frac{1}{\kappa_a^2(p_{T_{\epsilon}})\epsilon^2}\right), \tag*{(35)} T ϵ ≤ K + ( a 1 + a 2 K U ) ( Δ 0 2 γ dec − 2 K + κ a 2 ( p T ϵ ) ϵ 2 1 ) , (35) and consequently, for every ϵ > 0 \epsilon>0 ϵ > 0 and every k 0 ≥ k λ k_0\ge k_{\lambda} k 0 ≥ k λ ,
P ( T ϵ > k 0 + ( a 1 + a 2 k 0 ) ( γ d e c − 2 k 0 Δ 0 2 + 1 κ a 2 ( d ) ϵ 2 ) ) ≤ ∑ j ≥ k 0 ( e − c F λ j + 1 − β Q , j ) . (36) \mathbb{P}\left(T_{\epsilon}>k_0+(a_1+a_2k_0)\left(\frac{\gamma_{\mathrm{dec}}^{-2k_0}}{\Delta_0^2}+\frac{1}{\kappa_a^2(d)\epsilon^2}\right)\right)
\le\sum_{j\ge k_0}\left(e^{-c_F\lambda_j}+1-\beta_{Q,j}\right). \tag*{(36)} P ( T ϵ > k 0 + ( a 1 + a 2 k 0 ) ( Δ 0 2 γ dec − 2 k 0 + κ a 2 ( d ) ϵ 2 1 ) ) ≤ j ≥ k 0 ∑ ( e − c F λ j + 1 − β Q , j ) . (36)
Proof. Fix ω \omega ω outside the relevant null sets. First, S Δ ≤ a 1 + a 2 K U S_{\Delta} \le a_1+a_2K_U S Δ ≤ a 1 + a 2 K U : in the proof of Lemma 6.1,
S Δ ≤ c Δ ( Δ 0 2 γ d e c 2 + ∑ k ∈ K Δ k 2 ) ; S_{\Delta} \le c_{\Delta}\left(\frac{\Delta_0^2}{\gamma_{\mathrm{dec}}^2}+\sum_{k\in\mathcal{K}}\Delta_k^2\right); S Δ ≤ c Δ ( γ dec 2 Δ 0 2 + k ∈ K ∑ Δ k 2 ) ;
the successes before K U K_U K U number at most K U K_U K U and each contributes at most Δ max 2 \Delta_{\max}^2 Δ m a x 2 ; the successes from K U K_U K U on contribute at most ( f ( X k 1 0 ) − f ∗ ) / ( θ a − κ e d F ) (f(X_{k_1}^0)-f^*)/(\theta_a-\kappa_{\mathrm{ed}}F) ( f ( X k 1 0 ) − f ∗ ) / ( θ a − κ ed F ) by (26) ; and
f ( X k 1 0 ) ≤ f ( x 0 ) + K U κ L F κ Q Δ max f(X_{k_1}^0)\le f(x_0)+K_U\kappa_{L_F}\kappa_Q\Delta_{\max} f ( X k 1 0 ) ≤ f ( x 0 ) + K U κ L F κ Q Δ m a x
since each of the at most K U K_U K U moves before K U K_U K U has length at most κ Q Δ max \kappa_Q\Delta_{\max} κ Q Δ m a x . Second, the induction of Lemma 6.4 with the base case replaced by min { Δ K , κ a ( p K ) ϵ } \min\{\Delta_K,\kappa_a(p_K)\epsilon\} min { Δ K , κ a ( p K ) ϵ } gives
Δ k ≥ min { Δ K , κ a ( p k ) ϵ } \Delta_k\ge\min\{\Delta_K,\kappa_a(p_k)\epsilon\} Δ k ≥ min { Δ K , κ a ( p k ) ϵ }
for all K ≤ k < T ϵ K\le k<T_{\epsilon} K ≤ k < T ϵ and every ϵ > 0 \epsilon>0 ϵ > 0 , with no threshold: if
Δ k < min { Δ K , κ a ( p k ) ϵ } ≤ Δ k − 1 \Delta_k<\min\{\Delta_K,\kappa_a(p_k)\epsilon\}\le\Delta_{k-1} Δ k < min { Δ K , κ a ( p k ) ϵ } ≤ Δ k − 1
then k − 1 k-1 k − 1 failed and the contradiction is reached exactly as there. Since Δ K ≥ γ d e c K Δ 0 \Delta_K\ge\gamma_{\mathrm{dec}}^K\Delta_0 Δ K ≥ γ dec K Δ 0 , summing Δ k 2 \Delta_k^2 Δ k 2 over K ≤ k < T ϵ K\le k<T_{\epsilon} K ≤ k < T ϵ gives
( T ϵ − K ) min { γ d e c 2 K Δ 0 2 , κ a 2 ( p T ϵ ) ϵ 2 } ≤ S Δ , (T_{\epsilon}-K)\min\{\gamma_{\mathrm{dec}}^{2K}\Delta_0^2,\kappa_a^2(p_{T_{\epsilon}})\epsilon^2\}\le S_{\Delta}, ( T ϵ − K ) min { γ dec 2 K Δ 0 2 , κ a 2 ( p T ϵ ) ϵ 2 } ≤ S Δ ,
which is (35) after 1 / min { a , b } ≤ 1 / a + 1 / b 1/\min\{a,b\}\le1/a+1/b 1/ min { a , b } ≤ 1/ a + 1/ b . On { K ≤ k 0 } \{K\le k_0\} { K ≤ k 0 } the right side of (35) is at most the threshold in (36) , so the event there is contained in { K > k 0 } \{K>k_0\} { K > k 0 } , and Proposition 7.5 bounds its probability.
We note three remarks here. First, (36) is not asymptotic in any variable: for a given ϵ \epsilon ϵ and a given k 0 k_0 k 0 it is a numerical statement about the run, with a deterministic right-hand side that can be evaluated from the algorithm’s parameters and the constants c F c_F c F , c Q c_Q c Q ; the almost sure Theorem 7.2 is its limit as k 0 → ∞ k_0\to\infty k 0 → ∞ along ϵ ℓ ↓ 0 \epsilon_\ell\downarrow0 ϵ ℓ ↓ 0 . Second, the term γ d e c − 2 k 0 / Δ 0 2 \gamma_{\mathrm{dec}}^{-2k_0}/\Delta_0^2 γ dec − 2 k 0 / Δ 0 2 is the price of not knowing the radius at the end of the burn-in, and it is what prevents integrability of the constant in (35) ; in the regime of interest, ϵ ≪ Δ 0 γ d e c k 0 κ a \epsilon\ll\Delta_0\gamma_{\mathrm{dec}}^{k_0}\kappa_a ϵ ≪ Δ 0 γ dec k 0 κ a , it is dominated by the ϵ − 2 \epsilon^{-2} ϵ − 2 term, and it disappears from the almost sure statement because the random threshold ϵ 0 ( ω ) \epsilon_0(\omega) ϵ 0 ( ω ) absorbs it. Third, the tail in (36) is superpolynomial in k 0 k_0 k 0 on the estimation side and polynomial, of order k 0 − δ k_0^{-\delta} k 0 − δ , on the alignment side; the latter is set by the growth constant in (28) and can be made as fast as one likes at a constant-factor cost in p k p_k p k . A Markov bound from an expected iteration bound, by contrast, gives a tail of order t − 1 t^{-1} t − 1 in the deviation t t t ; the expectation route gets sharper tails only through the high-probability arguments it also contains.
Fixed subspace dimension: what the pathwise route can and cannot do
Sections 6–7 required p k = O ( log k ) p_k=O(\log k) p k = O ( log k ) . This section keeps p k = p p_k=p p k = p fixed, so that the misalignment probability β ˉ Q = 1 − β Q \bar{\beta}_Q=1-\beta_Q β ˉ Q = 1 − β Q is a fixed positive number, and asks what survives. The answer is quantitative and, we think, the most instructive point of the paper for a reader used to statements in expectation: the liminf and the complexity bounds survive with a worse exponent, and the loss is exactly the difference between the mean of a geometric random variable and the running maximum of a sequence of them. Part I obtains ϵ − 2 \epsilon^{-2} ϵ − 2 at fixed p p p through its per-iteration probability bound; what follows is what the eventual-accuracy argument obtains without it.
Throughout the section κ g \kappa_g κ g , κ m f \kappa_{\mathrm{mf}} κ mf , κ s u c \kappa_{\mathrm{suc}} κ suc , κ a \kappa_a κ a are the constants of (23) , (27) , (29) at the fixed p p p , and we write
b ϵ : = α Q κ s u c ϵ 1 + κ s u c κ g = κ a ϵ γ d e c , c γ : = log γ i n c log ( 1 / γ d e c ) , ρ Q : = e ( 1 + c γ ) c γ β ˉ Q . (37) b_{\epsilon}:=\frac{\alpha_Q\kappa_{\mathrm{suc}}\epsilon}{1+\kappa_{\mathrm{suc}}\kappa_g}=\frac{\kappa_a\epsilon}{\gamma_{\mathrm{dec}}},\qquad
c_{\gamma}:=\frac{\log\gamma_{\mathrm{inc}}}{\log(1/\gamma_{\mathrm{dec}})},\qquad
\rho_Q:=\frac{e(1+c_{\gamma})}{c_{\gamma}}\bar{\beta}_Q. \tag*{(37)} b ϵ := 1 + κ suc κ g α Q κ suc ϵ = γ dec κ a ϵ , c γ := log ( 1/ γ dec ) log γ inc , ρ Q := c γ e ( 1 + c γ ) β ˉ Q . (37)
The threshold b ϵ b_{\epsilon} b ϵ is the radius below which alignment and accuracy force success when ∥ ∇ f ( X k 0 ) ∥ ≥ ϵ \|\nabla f(X_k^0)\|\ge\epsilon ∥∇ f ( X k 0 ) ∥ ≥ ϵ on U k ∩ A k U_k\cap A_k U k ∩ A k , Lemma 5.2 gives
∥ G ^ k ∥ ≥ α Q ϵ − κ g Δ k , \|\widehat{G}_k\|\ge\alpha_Q\epsilon-\kappa_g\Delta_k, ∥ G k ∥ ≥ α Q ϵ − κ g Δ k ,
and Δ k ≤ b ϵ \Delta_k\le b_{\epsilon} Δ k ≤ b ϵ is equivalent to
Δ k ≤ κ s u c ( α Q ϵ − κ g Δ k ) , \Delta_k\le\kappa_{\mathrm{suc}}(\alpha_Q\epsilon-\kappa_g\Delta_k), Δ k ≤ κ suc ( α Q ϵ − κ g Δ k ) ,
so Lemma 6.2 applies. The constant c γ c_{\gamma} c γ converts expansions into units of contraction; c γ = 1 c_{\gamma}=1 c γ = 1 when γ i n c = 1 / γ d e c \gamma_{\mathrm{inc}}=1/\gamma_{\mathrm{dec}} γ inc = 1/ γ dec .
Lemma 8.1 (misaligned iterations in a window). Let I i : = 1 { A i c } I_i := 1\{A_i^c\} I i := 1 { A i c } . Under Assumption 6(a) with sup k ( 1 − β Q , k ) ≤ β ˉ Q \sup_k(1-\beta_{Q,k}) \le\bar{\beta}_Q sup k ( 1 − β Q , k ) ≤ β ˉ Q , for all integers j ≥ − 1 j \ge-1 j ≥ − 1 (with F − 1 \mathcal{F}_{-1} F − 1 trivial), j ′ ≥ 1 j' \ge1 j ′ ≥ 1 and all real t ≥ j ′ β ˉ Q t \ge j'\bar{\beta}_Q t ≥ j ′ β ˉ Q , almost surely
P ( ∑ i = j + 1 j + j ′ I i ≥ t | F j ) ≤ ( e j ′ β ˉ Q t ) t . (38) \mathbb{P}\left(\sum_{i=j+1}^{j+j'} I_i \ge t \,\middle|\, \mathcal{F}_j\right) \le\left(\frac{e j'\bar{\beta}_Q}{t}\right)^t. \tag*{(38)} P i = j + 1 ∑ j + j ′ I i ≥ t F j ≤ ( t e j ′ β ˉ Q ) t . (38)
Proof. For $\theta > 0,
E [ e θ I i ∣ F i − 1 ] = 1 + P ( A i c ∣ F i − 1 ) ( e θ − 1 ) ≤ 1 + β ˉ Q ( e θ − 1 ) ≤ exp ( β ˉ Q ( e θ − 1 ) ) , \mathbb{E}[e^{\theta I_i}\mid\mathcal{F}_{i-1}] = 1+\mathbb{P}(A_i^c\mid\mathcal{F}_{i-1})(e^\theta-1) \le1+\bar{\beta}_Q(e^\theta-1) \le\exp(\bar{\beta}_Q(e^\theta-1)), E [ e θ I i ∣ F i − 1 ] = 1 + P ( A i c ∣ F i − 1 ) ( e θ − 1 ) ≤ 1 + β ˉ Q ( e θ − 1 ) ≤ exp ( β ˉ Q ( e θ − 1 )) ,
so by iterated conditioning
E [ e θ ∑ i = j + 1 j + j ′ I i ∣ F j ] ≤ exp ( j ′ β ˉ Q ( e θ − 1 ) ) . \mathbb{E}\left[e^{\theta\sum_{i=j+1}^{j+j'} I_i}\mid\mathcal{F}_j\right] \le\exp(j'\bar{\beta}_Q(e^\theta-1)). E [ e θ ∑ i = j + 1 j + j ′ I i ∣ F j ] ≤ exp ( j ′ β ˉ Q ( e θ − 1 )) .
Markov’s inequality gives
P ( ∑ I i ≥ t | F j ) ≤ exp ( − θ t + j ′ β ˉ Q ( e θ − 1 ) ) , \mathbb{P}\left(\sum I_i \ge t \,\middle|\, \mathcal{F}_j\right) \le\exp(-\theta t+j'\bar{\beta}_Q(e^\theta-1)), P ( ∑ I i ≥ t F j ) ≤ exp ( − θ t + j ′ β ˉ Q ( e θ − 1 )) ,
and the choice e θ = t / ( j ′ β ˉ Q ) ≥ 1 e^\theta=t/(j'\bar{\beta}_Q)\ge1 e θ = t / ( j ′ β ˉ Q ) ≥ 1 gives
exp ( − t log ( t / ( j ′ β ˉ Q ) ) + t − j ′ β ˉ Q ) ≤ ( e j ′ β ˉ Q / t ) t . \exp(-t\log(t/(j'\bar{\beta}_Q))+t-j'\bar{\beta}_Q)\le(e j'\bar{\beta}_Q/t)^t. exp ( − t log ( t / ( j ′ β ˉ Q )) + t − j ′ β ˉ Q ) ≤ ( e j ′ β ˉ Q / t ) t .
Lemma 8.2 (depth of an excursion below b ϵ b_\epsilon b ϵ ). Fix ω \omega ω outside the null set of Corollary 4.8, integers k ˉ ≥ K U \bar{k}\ge K_U k ˉ ≥ K U and k > k ˉ k>\bar{k} k > k ˉ , an integer r ≥ 0 r\ge0 r ≥ 0 , and ϵ > 0 \epsilon>0 ϵ > 0 with γ i n c b ϵ ≤ Δ max \gamma_{\mathrm{inc}}b_\epsilon\le\Delta_{\max} γ inc b ϵ ≤ Δ m a x . Suppose that ∥ ∇ f ( X i 0 ) ∥ ≥ ϵ \lVert\nabla f(X_i^0)\rVert\ge\epsilon ∥ ∇ f ( X i 0 )∥ ≥ ϵ for all k ˉ ≤ i < k \bar{k}\le i<k k ˉ ≤ i < k and that Δ k < min { γ d e c b ϵ , Δ k ˉ } γ d e c \Delta_k<\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}} Δ k < min { γ dec b ϵ , Δ k ˉ } γ dec . Then there is j ′ ∈ { 1 , … , k − k ˉ } j'\in\{1,\ldots,k-\bar{k}\} j ′ ∈ { 1 , … , k − k ˉ } such that the window { k − j ′ , … , k − 1 } \{k-j',\ldots,k-1\} { k − j ′ , … , k − 1 } contains more than
t j ′ ( r ) : = r + c γ j ′ 1 + c γ (39) t_{j'}(r):=\frac{r+c_\gamma j'}{1+c_\gamma} \tag*{(39)} t j ′ ( r ) := 1 + c γ r + c γ j ′ (39) misaligned iterations.
Proof. Let j 0 : = max { i ∈ [ k ˉ , k ) : Δ i ≥ b ϵ } j_0:=\max\{i\in[\bar{k},k):\Delta_i\ge b_\epsilon\} j 0 := max { i ∈ [ k ˉ , k ) : Δ i ≥ b ϵ } if this set is nonempty and j 0 : = k ˉ − 1 j_0:=\bar{k}-1 j 0 := k ˉ − 1 otherwise, and let j ′ : = k − j 0 − 1 j':=k-j_0-1 j ′ := k − j 0 − 1 , so that the window is { j 0 + 1 , … , k − 1 } ⊂ [ k ˉ , k ) \{j_0+1,\ldots,k-1\}\subset[\bar{k},k) { j 0 + 1 , … , k − 1 } ⊂ [ k ˉ , k ) . In the first case Δ j 0 + 1 ≥ γ d e c Δ j 0 ≥ γ d e c b ϵ \Delta_{j_0+1}\ge\gamma_{\mathrm{dec}}\Delta_{j_0}\ge\gamma_{\mathrm{dec}}b_\epsilon Δ j 0 + 1 ≥ γ dec Δ j 0 ≥ γ dec b ϵ , since the radius decreases by at most the factor γ d e c \gamma_{\mathrm{dec}} γ dec in one iteration; in the second Δ j 0 + 1 = Δ k ˉ \Delta_{j_0+1}=\Delta_{\bar{k}} Δ j 0 + 1 = Δ k ˉ . Either way
Δ j 0 + 1 ≥ min { γ d e c b ϵ , Δ k ˉ } > Δ k , \Delta_{j_0+1}\ge\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}>\Delta_k, Δ j 0 + 1 ≥ min { γ dec b ϵ , Δ k ˉ } > Δ k ,
so j 0 + 1 < k j_0+1<k j 0 + 1 < k , that is, j ′ ≥ 1 j'\ge1 j ′ ≥ 1 . For every i i i in the window, Δ i < b ϵ ≤ Δ max / γ i n c \Delta_i<b_\epsilon\le\Delta_{\max}/\gamma_{\mathrm{inc}} Δ i < b ϵ ≤ Δ m a x / γ inc by the choice of j 0 j_0 j 0 , so a success multiplies the radius by exactly γ i n c \gamma_{\mathrm{inc}} γ inc and a failure by γ d e c \gamma_{\mathrm{dec}} γ dec . With J J J the number of failures in the window, Δ k = Δ j 0 + 1 γ d e c J γ i n c j ′ − J \Delta_k=\Delta_{j_0+1}\gamma_{\mathrm{dec}}^J\gamma_{\mathrm{inc}}^{j'-J} Δ k = Δ j 0 + 1 γ dec J γ inc j ′ − J , and the hypothesis gives γ d e c J γ i n c j ′ − J < γ d e c r \gamma_{\mathrm{dec}}^J\gamma_{\mathrm{inc}}^{j'-J}<\gamma_{\mathrm{dec}}^r γ dec J γ inc j ′ − J < γ dec r . Taking logarithms and dividing by log ( 1 / γ d e c ) \log(1/\gamma_{\mathrm{dec}}) log ( 1/ γ dec ) ,
J − c γ ( j ′ − J ) > r , that is, J > r + c γ j ′ 1 + c γ = t j ′ ( r ) . J-c_\gamma(j'-J)>r,\qquad\text{that is,}\qquad J>\frac{r+c_\gamma j'}{1+c_\gamma}=t_{j'}(r). J − c γ ( j ′ − J ) > r , that is, J > 1 + c γ r + c γ j ′ = t j ′ ( r ) .
Finally, every failure in the window is a misaligned iteration: for such i i i we have i ≥ k ˉ ≥ K U i\ge\bar{k}\ge K_U i ≥ k ˉ ≥ K U , so U i U_i U i holds, Δ i < b ϵ \Delta_i<b_\epsilon Δ i < b ϵ and ∥ ∇ f ( X i 0 ) ∥ ≥ ϵ \lVert\nabla f(X_i^0)\rVert\ge\epsilon ∥ ∇ f ( X i 0 )∥ ≥ ϵ , and by the discussion after (37) the iteration would be successful if A i A_i A i held.
Theorem 8.3 (fixed subspace dimension). Let the hypotheses of Corollary 4.8, Assumptions 1, 5 and 6 and (25) hold with p k = p p_k=p p k = p fixed and sup k ( 1 − β Q , k ) ≤ β ˉ Q \sup_k(1-\beta_{Q,k})\le\bar{\beta}_Q sup k ( 1 − β Q , k ) ≤ β ˉ Q , where 0 < β ˉ Q < c γ / ( e ( 1 + c γ ) ) 0<\bar{\beta}_Q<c_\gamma/(e(1+c_\gamma)) 0 < β ˉ Q < c γ / ( e ( 1 + c γ )) , so that ρ Q < 1 \rho_Q<1 ρ Q < 1 . Fix δ ′ > 0 \delta'>0 δ ′ > 0 and set
ϱ : = ( 1 + c γ ) ( 1 + δ ′ ) log ( 1 / γ d e c ) log ( 1 / ρ Q ) . (40) \varrho:=\frac{(1+c_\gamma)(1+\delta')\log(1/\gamma_{\mathrm{dec}})}{\log(1/\rho_Q)}. \tag*{(40)} ϱ := log ( 1/ ρ Q ) ( 1 + c γ ) ( 1 + δ ′ ) log ( 1/ γ dec ) . (40) Then almost surely there is a finite random index K 2 > K U K_2>K_U K 2 > K U such that, for every k ˉ ≥ K U \bar{k}\ge K_U k ˉ ≥ K U , every k ≥ K 2 k\ge K_2 k ≥ K 2 with k > k ˉ k>\bar{k} k > k ˉ , and every ϵ > 0 \epsilon>0 ϵ > 0 with γ i n c b ϵ ≤ Δ max \gamma_{\mathrm{inc}}b_\epsilon\le\Delta_{\max} γ inc b ϵ ≤ Δ m a x ,
∥ ∇ f ( X i 0 ) ∥ ≥ ϵ for all k ˉ ≤ i < k ⟹ Δ k ≥ min { γ d e c b ϵ , Δ k ˉ } γ d e c k − k ˉ . (41) \lVert\nabla f(X_i^0)\rVert\ge\epsilon\text{ for all }\bar{k}\le i<k\quad\Longrightarrow\quad\Delta_k\ge\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}}^{k-\bar{k}}. \tag*{(41)} ∥ ∇ f ( X i 0 )∥ ≥ ϵ for all k ˉ ≤ i < k ⟹ Δ k ≥ min { γ dec b ϵ , Δ k ˉ } γ dec k − k ˉ . (41) Consequently:
(i) if ϱ ≤ 1 2 \varrho\le\frac{1}{2} ϱ ≤ 2 1 then lim inf k ∥ ∇ f ( X k 0 ) ∥ = 0 \liminf_k \lVert\nabla f(X_k^0)\rVert= 0 lim inf k ∥ ∇ f ( X k 0 )∥ = 0 almost surely;
(ii) if ϱ < 1 2 \varrho< \frac{1}{2} ϱ < 2 1 then there is an almost surely finite R ˉ > 0 \bar{R} > 0 R ˉ > 0 with P ( T ϵ ℓ > R ˉ ϵ ℓ − 2 / ( 1 − 2 ϱ ) i . o . ) = 0 \mathbb{P}\left(T_{\epsilon_\ell} > \bar{R}\epsilon_\ell^{-2/(1-2\varrho)}\ \mathrm{i.o.}\right) = 0 P ( T ϵ ℓ > R ˉ ϵ ℓ − 2/ ( 1 − 2 ϱ ) i.o. ) = 0 along every deterministic ϵ ℓ ↓ 0 \epsilon_\ell\downarrow0 ϵ ℓ ↓ 0 , and under Assumption 7, W ϵ = O ~ ( ϵ − 4 / ( 1 − 2 ϱ ) ) W_\epsilon= \widetilde{O}(\epsilon^{-4/(1-2\varrho)}) W ϵ = O ( ϵ − 4/ ( 1 − 2 ϱ ) ) almost surely.
Proof. The radius bound. For k ≥ 1 k \ge1 k ≥ 1 let
r k : = ⌈ ( 1 + c γ ) ( 1 + δ ′ ) log k log ( 1 / ρ Q ) ⌉ , r_k := \left\lceil(1+c_\gamma)(1+\delta')\frac{\log k}{\log(1/\rho_Q)}\right\rceil, r k := ⌈ ( 1 + c γ ) ( 1 + δ ′ ) log ( 1/ ρ Q ) log k ⌉ ,
so that γ d e c r k ≥ γ d e c k − ϱ \gamma_{\mathrm{dec}}^{r_k} \ge\gamma_{\mathrm{dec}} k^{-\varrho} γ dec r k ≥ γ dec k − ϱ , and let E k \mathcal{E}_k E k be the event that for some j ′ ∈ { 1 , … , k } j' \in\{1,\ldots,k\} j ′ ∈ { 1 , … , k } the window { k − j ′ , … , k − 1 } \{k-j',\ldots,k-1\} { k − j ′ , … , k − 1 } contains at least t j ′ ( r k ) t_{j'}(r_k) t j ′ ( r k ) misaligned iterations. Fix j ′ j' j ′ . Since
t j ′ ( r k ) ≥ c γ j ′ 1 + c γ > j ′ β ˉ Q , t_{j'}(r_k) \ge\frac{c_\gamma j'}{1+c_\gamma} > j'\bar{\beta}_Q, t j ′ ( r k ) ≥ 1 + c γ c γ j ′ > j ′ β ˉ Q ,
Lemma 8.1 applies with j = k − j ′ − 1 j=k-j'-1 j = k − j ′ − 1 (F − 1 \mathcal{F}_{-1} F − 1 being the trivial σ \sigma σ -field) and t = t j ′ ( r k ) t=t_{j'}(r_k) t = t j ′ ( r k ) , and since
e j ′ β ˉ Q / t j ′ ( r k ) ≤ e ( 1 + c γ ) β ˉ Q / c γ = ρ Q < 1 , e^{j'\bar{\beta}_Q/t_{j'}(r_k)} \le e(1+c_\gamma)\bar{\beta}_Q/c_\gamma= \rho_Q < 1, e j ′ β ˉ Q / t j ′ ( r k ) ≤ e ( 1 + c γ ) β ˉ Q / c γ = ρ Q < 1 ,
the probability that the window contains at least t j ′ ( r k ) t_{j'}(r_k) t j ′ ( r k ) misaligned iterations is at most ρ Q t j ′ ( r k ) \rho_Q^{t_{j'}(r_k)} ρ Q t j ′ ( r k ) . Summing over j ′ j' j ′ ,
P ( E k ) ≤ ρ Q r k / ( 1 + c γ ) ∑ j ′ ≥ 1 ρ Q c γ j ′ / ( 1 + c γ ) ≤ k − ( 1 + δ ′ ) 1 − ρ Q c γ / ( 1 + c γ ) , \mathbb{P}(\mathcal{E}_k) \le\rho_Q^{r_k/(1+c_\gamma)} \sum_{j'\ge1}\rho_Q^{c_\gamma j'/(1+c_\gamma)}
\le\frac{k^{-(1+\delta')}}{1-\rho_Q^{c_\gamma/(1+c_\gamma)}}, P ( E k ) ≤ ρ Q r k / ( 1 + c γ ) j ′ ≥ 1 ∑ ρ Q c γ j ′ / ( 1 + c γ ) ≤ 1 − ρ Q c γ / ( 1 + c γ ) k − ( 1 + δ ′ ) ,
which is summable. By the first Borel–Cantelli lemma there is an almost surely finite K 2 ′ K'_2 K 2 ′ with E k c \mathcal{E}_k^c E k c for all k ≥ K 2 ′ k \ge K'_2 k ≥ K 2 ′ ; set K 2 : = K 2 ′ ∨ ( K U + 1 ) K_2 := K'_2 \vee(K_U+1) K 2 := K 2 ′ ∨ ( K U + 1 ) . Now fix ω \omega ω outside the null sets, k ˉ ≥ K U \bar{k} \ge K_U k ˉ ≥ K U , k ≥ K 2 k \ge K_2 k ≥ K 2 with k > k ˉ k > \bar{k} k > k ˉ and ϵ \epsilon ϵ as in the statement, and suppose the hypothesis of (41) holds while
Δ k < min { γ d e c b ϵ , Δ k ˉ } γ d e c k − ϱ ≤ min { γ d e c b ϵ , Δ k ˉ } γ d e c r k . \Delta_k < \min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}}k^{-\varrho} \le\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}}^{r_k}. Δ k < min { γ dec b ϵ , Δ k ˉ } γ dec k − ϱ ≤ min { γ dec b ϵ , Δ k ˉ } γ dec r k .
Lemma 8.2 with r = r k r=r_k r = r k gives a window { k − j ′ , … , k − 1 } \{k-j',\ldots,k-1\} { k − j ′ , … , k − 1 } , 1 ≤ j ′ ≤ k 1\le j'\le k 1 ≤ j ′ ≤ k , with more than t j ′ ( r k ) t_{j'}(r_k) t j ′ ( r k ) misaligned iterations, so E k \mathcal{E}_k E k occurs, contradicting k ≥ K 2 ′ k\ge K'_2 k ≥ K 2 ′ .
(i). Suppose ϱ ≤ 1 2 \varrho\le\frac{1}{2} ϱ ≤ 2 1 and that, on a path outside the null sets, ∥ ∇ f ( X k 0 ) ∥ ≥ ϵ \lVert\nabla f(X_k^0)\rVert\ge\epsilon ∥ ∇ f ( X k 0 )∥ ≥ ϵ for all k ≥ k ˉ k \ge\bar{k} k ≥ k ˉ , for some ϵ > 0 \epsilon>0 ϵ > 0 and k ˉ \bar{k} k ˉ . Decreasing ϵ \epsilon ϵ and increasing k ˉ \bar{k} k ˉ we may assume γ i n c b ϵ ≤ Δ max \gamma_{\mathrm{inc}}b_\epsilon\le\Delta_{\max} γ inc b ϵ ≤ Δ m a x and k ˉ ≥ K U \bar{k}\ge K_U k ˉ ≥ K U . Then (41) gives
Δ k ≥ min { γ d e c b ϵ , Δ k ˉ } γ d e c k − ϱ \Delta_k \ge\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}}k^{-\varrho} Δ k ≥ min { γ dec b ϵ , Δ k ˉ } γ dec k − ϱ
for all k ≥ K 2 ∨ ( k ˉ + 1 ) k\ge K_2\vee(\bar{k}+1) k ≥ K 2 ∨ ( k ˉ + 1 ) , so
∑ k Δ k 2 ≥ ( min { γ d e c b ϵ , Δ k ˉ } γ d e c ) 2 ∑ k ≥ K 2 ∨ ( k ˉ + 1 ) k − 2 ϱ = ∞ , \sum_k\Delta_k^2 \ge\left(\min\{\gamma_{\mathrm{dec}}b_\epsilon,\Delta_{\bar{k}}\}\gamma_{\mathrm{dec}}\right)^2
\sum_{k\ge K_2\vee(\bar{k}+1)} k^{-2\varrho}=\infty, k ∑ Δ k 2 ≥ ( min { γ dec b ϵ , Δ k ˉ } γ dec ) 2 k ≥ K 2 ∨ ( k ˉ + 1 ) ∑ k − 2 ϱ = ∞ ,
contradicting Lemma 6.1.
(ii). Let ϱ < 1 2 \varrho< \frac{1}{2} ϱ < 2 1 ; by (i), T ϵ < ∞ T_\epsilon<\infty T ϵ < ∞ for every ϵ > 0 \epsilon>0 ϵ > 0 . Fix ω \omega ω . If T ϵ T_\epsilon T ϵ stays bounded as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 there is nothing to prove. Otherwise take ϵ ≤ 1 \epsilon\le1 ϵ ≤ 1 small enough that γ i n c b ϵ ≤ Δ max \gamma_{\mathrm{inc}}b_\epsilon\le\Delta_{\max} γ inc b ϵ ≤ Δ m a x , γ d e c b ϵ ≤ Δ K U \gamma_{\mathrm{dec}}b_\epsilon\le\Delta_{K_U} γ dec b ϵ ≤ Δ K U and T ϵ > K 2 T_\epsilon>K_2 T ϵ > K 2 . For K 2 ≤ k < T ϵ K_2\le k<T_\epsilon K 2 ≤ k < T ϵ , (41) with k ˉ = K U \bar{k}=K_U k ˉ = K U and b ϵ = κ a ϵ / γ d e c b_\epsilon=\kappa_a\epsilon/\gamma_{\mathrm{dec}} b ϵ = κ a ϵ / γ dec gives Δ k ≥ γ d e c κ a ϵ k − ϱ \Delta_k\ge\gamma_{\mathrm{dec}}\kappa_a\epsilon k^{-\varrho} Δ k ≥ γ dec κ a ϵ k − ϱ , hence
S Δ ≥ ∑ k = K 2 T ϵ − 1 Δ k 2 ≥ γ d e c 2 κ a 2 ϵ 2 ∫ K 2 T ϵ x − 2 ϱ d x = γ d e c 2 κ a 2 ϵ 2 T ϵ 1 − 2 ϱ − K 2 1 − 2 ϱ 1 − 2 ϱ , S_\Delta\ge\sum_{k=K_2}^{T_\epsilon-1}\Delta_k^2 \ge\gamma_{\mathrm{dec}}^2\kappa_a^2\epsilon^2\int_{K_2}^{T_\epsilon}x^{-2\varrho}\,dx
=\gamma_{\mathrm{dec}}^2\kappa_a^2\epsilon^2\frac{T_\epsilon^{1-2\varrho}-K_2^{1-2\varrho}}{1-2\varrho}, S Δ ≥ k = K 2 ∑ T ϵ − 1 Δ k 2 ≥ γ dec 2 κ a 2 ϵ 2 ∫ K 2 T ϵ x − 2 ϱ d x = γ dec 2 κ a 2 ϵ 2 1 − 2 ϱ T ϵ 1 − 2 ϱ − K 2 1 − 2 ϱ ,
so that
T ϵ 1 − 2 ϱ ≤ ( ( 1 − 2 ϱ ) γ d e c − 2 κ a − 2 S Δ + K 2 1 − 2 ϱ ) ϵ − 2 , T_\epsilon^{1-2\varrho}\le\left((1-2\varrho)\gamma_{\mathrm{dec}}^{-2}\kappa_a^{-2}S_\Delta+K_2^{1-2\varrho}\right)\epsilon^{-2}, T ϵ 1 − 2 ϱ ≤ ( ( 1 − 2 ϱ ) γ dec − 2 κ a − 2 S Δ + K 2 1 − 2 ϱ ) ϵ − 2 ,
which is the claim with
R ˉ : = ( ( 1 − 2 ϱ ) γ d e c − 2 κ a − 2 S Δ + K 2 1 − 2 ϱ ) 1 / ( 1 − 2 ϱ ) . \bar{R}:=\left((1-2\varrho)\gamma_{\mathrm{dec}}^{-2}\kappa_a^{-2}S_\Delta+K_2^{1-2\varrho}\right)^{1/(1-2\varrho)}. R ˉ := ( ( 1 − 2 ϱ ) γ dec − 2 κ a − 2 S Δ + K 2 1 − 2 ϱ ) 1/ ( 1 − 2 ϱ ) .
For the sample complexity, let K 3 : = K 2 ∨ K W K_3:=K_2\vee K_W K 3 := K 2 ∨ K W and Q W : = ∑ k < K 3 ( 2 p + 2 ) N k Q_W:=\sum_{k<K_3}(2p+2)N_k Q W := ∑ k < K 3 ( 2 p + 2 ) N k . For K 3 ≤ k < T ϵ K_3\le k<T_\epsilon K 3 ≤ k < T ϵ , Lemma 7.3 gives
N k ≤ n W λ k Δ k − 2 ≤ n W λ T ϵ γ d e c − 2 κ a − 2 ϵ − 2 k 2 ϱ , N_k\le n_W\lambda_k\Delta_k^{-2}\le n_W\lambda_{T_\epsilon}\gamma_{\mathrm{dec}}^{-2}\kappa_a^{-2}\epsilon^{-2}k^{2\varrho}, N k ≤ n W λ k Δ k − 2 ≤ n W λ T ϵ γ dec − 2 κ a − 2 ϵ − 2 k 2 ϱ ,
so
W ϵ ≤ Q w + ( 2 p + 2 ) n W λ T ϵ γ d e c − 2 κ a − 2 ϵ − 2 T ϵ 1 + 2 ϱ , W_{\epsilon} \le Q_w + (2p+2)n_W\lambda_{T_\epsilon}\gamma_{\mathrm{dec}}^{-2}\kappa_a^{-2}\epsilon^{-2}T_\epsilon^{1+2\varrho}, W ϵ ≤ Q w + ( 2 p + 2 ) n W λ T ϵ γ dec − 2 κ a − 2 ϵ − 2 T ϵ 1 + 2 ϱ ,
and
ϵ − 2 T ϵ 1 + 2 ϱ ≤ R ˉ 1 + 2 ϱ ϵ − 2 − 2 ( 1 + 2 ϱ ) / ( 1 − 2 ϱ ) = R ˉ 1 + 2 ϱ ϵ − 4 / ( 1 − 2 ϱ ) , \epsilon^{-2T_\epsilon^{1+2\varrho}} \le\bar{R}^{1+2\varrho}\epsilon^{-2-2(1+2\varrho)/(1-2\varrho)} = \bar{R}^{1+2\varrho}\epsilon^{-4/(1-2\varrho)}, ϵ − 2 T ϵ 1 + 2 ϱ ≤ R ˉ 1 + 2 ϱ ϵ − 2 − 2 ( 1 + 2 ϱ ) / ( 1 − 2 ϱ ) = R ˉ 1 + 2 ϱ ϵ − 4/ ( 1 − 2 ϱ ) ,
while λ T ϵ \lambda_{T_\epsilon} λ T ϵ is polylogarithmic in 1 / ϵ 1/\epsilon 1/ ϵ .
Remark 10 (the exponent). For the ensembles of § 3.1 , β ˉ Q = e − c Q p \bar{\beta}_Q=e^{-c_Qp} β ˉ Q = e − c Q p , so log ( 1 / ρ Q ) = c Q p − log ( e ( 1 + c γ ) / c γ ) \log(1/\rho_Q)=c_Qp-\log(e(1+c_\gamma)/c_\gamma) log ( 1/ ρ Q ) = c Q p − log ( e ( 1 + c γ ) / c γ ) and
ϱ = ( 1 + c γ ) ( 1 + δ ′ ) log ( 1 / γ d e c ) c Q p − log ( e ( 1 + c γ ) / c γ ) = O ( 1 p ) , 2 1 − 2 ϱ = 2 + O ( 1 p ) . \varrho=\frac{(1+c_\gamma)(1+\delta')\log(1/\gamma_{\mathrm{dec}})}{c_Qp-\log(e(1+c_\gamma)/c_\gamma)}=O\left(\frac{1}{p}\right),\qquad\frac{2}{1-2\varrho}=2+O\left(\frac{1}{p}\right). ϱ = c Q p − log ( e ( 1 + c γ ) / c γ ) ( 1 + c γ ) ( 1 + δ ′ ) log ( 1/ γ dec ) = O ( p 1 ) , 1 − 2 ϱ 2 = 2 + O ( p 1 ) .
There are three consequences. First, a fixed subspace dimension is admissible on the pathwise route once p p p exceeds the explicit threshold making ϱ < 1 2 \varrho<\frac{1}{2} ϱ < 2 1 ; the argument of this section then gives exponent 2 + O ( 1 / p ) 2+O(1/p) 2 + O ( 1/ p ) . Second, p k p_k p k of order log k \log k log k is the growth at which k − ϱ k k^{-\varrho k} k − ϱ k becomes a constant and the exponent is exactly 2, which is Theorem 7.2 . Third, the threshold β ˉ Q < c γ / ( e ( 1 + c γ ) ) \bar{\beta}_Q<c_\gamma/(e(1+c_\gamma)) β ˉ Q < c γ / ( e ( 1 + c γ )) comes from the crude Chernoff bound of Lemma 8.1 ; replacing ( e j ′ β ˉ Q / t ) t (e j'\bar{\beta}_Q/t)^t ( e j ′ β ˉ Q / t ) t by the binomial Chernoff bound exp ( − j ′ KL ( t / j ′ ∥ β ˉ Q ) ) \exp(-j'\operatorname{KL}(t/j'\mathbin\Vert\bar{\beta}_Q)) exp ( − j ′ KL ( t / j ′ ∥ β ˉ Q )) extends the argument to β ˉ Q < c γ / ( 1 + c γ ) \bar{\beta}_Q<c_\gamma/(1+c_\gamma) β ˉ Q < c γ / ( 1 + c γ ) , which for γ i n c = 1 / γ d e c \gamma_{\mathrm{inc}}=1/\gamma_{\mathrm{dec}} γ inc = 1/ γ dec is β ˉ Q < 1 2 \bar{\beta}_Q<\frac{1}{2} β ˉ Q < 2 1 , the same threshold as Part I.
Remark 11 (why expectation gets ϵ − 2 \epsilon^{-2} ϵ − 2 with fixed p p p and the path does not). The proof shows where the exponent comes from. Given the past, the depth of an excursion of the radius below b ϵ b_\epsilon b ϵ has a geometric tail: P ( d e p t h ≥ r ) ≤ c ρ Q r / ( 1 + c γ ) \mathbb{P}(\mathrm{depth}\ge r)\le c\rho_Q^{r/(1+c_\gamma)} P ( depth ≥ r ) ≤ c ρ Q r / ( 1 + c γ ) .
In expectation this is harmless: E [ Δ k − 2 1 { k < T ϵ } ] \mathbb{E}[\Delta_k^{-2}\mathbf{1}_{\{k<T_\epsilon\}}] E [ Δ k − 2 1 { k < T ϵ } ] is bounded by a geometric series in r r r as soon as γ d e c ρ Q 1 / ( 1 + c γ ) < 1 \gamma_{\mathrm{dec}}\rho_Q^{1/(1+c_\gamma)}<1 γ dec ρ Q 1/ ( 1 + c γ ) < 1 , the mean depth is O ( 1 ) O(1) O ( 1 ) , and one recovers E [ T ϵ ] = O ( ϵ − 2 ) \mathbb{E}[T_\epsilon]=O(\epsilon^{-2}) E [ T ϵ ] = O ( ϵ − 2 ) ; this is the mechanism behind the expected bounds of [2 , 7 ] and of Part I, whose Assumption 2.2 is the corresponding contraction condition for its inverse-radius sums. Along a path, however, the statement must hold for all k k k at once, so what matters is not the mean depth but the maximum depth over the first k k k iterations, which for a geometric tail is ≍ log k / log ( 1 / ρ Q ) \asymp\log k/\log(1/\rho_Q) ≍ log k / log ( 1/ ρ Q ) . That logarithm, exponentiated by γ d e c \gamma_{\mathrm{dec}} γ dec , is the factor k ϱ k^{\varrho} k ϱ . Nothing is lost when the depth’s logarithm is beaten by the growth of p k p_k p k , which is what ∑ k ( 1 − β Q , k ) < ∞ \sum_k(1-\beta_{Q,k})<\infty ∑ k ( 1 − β Q , k ) < ∞ achieves: then there are eventually no misaligned iterations at all, and the depth is zero.
Dimension dependence
All statements about d d d , p p p and the sketch scale are confined to this section; § 4 –§ 8 are written in the named constants κ Q \kappa_Q κ Q , α Q \alpha_Q α Q , κ e d F \kappa_{\mathrm{ed}F} κ ed F , κ H \kappa_H κ H , κ g \kappa_g κ g , κ m f \kappa_{mf} κ m f , κ s u c \kappa_{\mathrm{suc}} κ suc , κ a \kappa_a κ a , r F r_F r F . We take p p p fixed for the accounting; with p k p_k p k as in (28) every power of p p p below is a power of log ( 1 / ϵ ) \log(1/\epsilon) log ( 1/ ϵ ) , and α Q \alpha_Q α Q is evaluated at p 0 p_0 p 0 as in Proposition 3.1 . We hold ( Δ 0 , Δ max , μ , κ s , κ H , κ e d F ) (\Delta_0,\Delta_{\max},\mu,\kappa_s,\kappa_H,\kappa_{\mathrm{ed}F}) ( Δ 0 , Δ m a x , μ , κ s , κ H , κ ed F ) fixed in subspace coordinates, as discussed after Proposition 3.2 , and drop absolute constants and the fixed problem constants κ L g , σ D , b D , σ 0 , Δ max , η , κ Q , γ i n c , γ d e c \kappa_{Lg},\sigma_D,b_D,\sigma_0,\Delta_{\max},\eta,\kappa_Q,\gamma_{\mathrm{inc}},\gamma_{\mathrm{dec}} κ Lg , σ D , b D , σ 0 , Δ m a x , η , κ Q , γ inc , γ dec from the ≲ \lesssim ≲ relations. The random quantities S Δ S_\Delta S Δ and the burn-in indices also depend on d d d , p p p and the scale; only the deterministic prefactors are tracked here, and the table takes p 0 = p p_0=p p 0 = p , since α Q \alpha_Q α Q is evaluated at p 0 p_0 p 0 .
The chain of constants. From (23) , (27) and (29) , using κ s u c − 1 ( p ) ≲ κ m f ( p ) ∨ κ H ∨ μ − 1 \kappa_{\mathrm{suc}}^{-1}(p)\lesssim\kappa_{mf}(p)\vee\kappa_H\vee\mu^{-1} κ suc − 1 ( p ) ≲ κ m f ( p ) ∨ κ H ∨ μ − 1 ,
κ g ( p ) ≲ p ( κ Q 2 + κ e d F ) , κ a − 2 ( p ) ≲ α Q − 2 ( p ( κ Q 2 + κ e d F ) + 1 ) 2 , (42) \kappa_g(p)\lesssim\sqrt{p}\left(\kappa_Q^2+\kappa_{\mathrm{ed}F}\right),\qquad\kappa_a^{-2}(p)\lesssim\alpha_Q^{-2}\left(\sqrt{p}\left(\kappa_Q^2+\kappa_{\mathrm{ed}F}\right)+1\right)^2, \tag*{(42)} κ g ( p ) ≲ p ( κ Q 2 + κ ed F ) , κ a − 2 ( p ) ≲ α Q − 2 ( p ( κ Q 2 + κ ed F ) + 1 ) 2 , (42)
the additive 1 coming from κ H ≥ 1 \kappa_H\ge1 κ H ≥ 1 and μ − 1 \mu^{-1} μ − 1 , which do not rescale with the sketch. For the ensembles of § 3.1 , α Q − 2 ≲ d / ( p κ Q 2 ) \alpha_Q^{-2}\lesssim d/(p\kappa_Q^2) α Q − 2 ≲ d / ( p κ Q 2 ) . On the sampling side, (19) gives
1 r F ≲ max { 1 , ( κ Q κ e d F ) 2 , κ Q κ e d F } , (43) \frac{1}{r_F}\lesssim\max\left\{1,\left(\frac{\kappa_Q}{\kappa_{\mathrm{ed}F}}\right)^2,\frac{\kappa_Q}{\kappa_{\mathrm{ed}F}}\right\}, \tag*{(43)} r F 1 ≲ max { 1 , ( κ ed F κ Q ) 2 , κ ed F κ Q } , (43)
and Theorem 4.7 consumes λ k ≥ 2 p / r F \lambda_k\ge2p/r_F λ k ≥ 2 p / r F . Whether this is met by the burn-in index κ λ \kappa_\lambda κ λ or by choosing λ 0 ≥ 2 p / r F \lambda_0\ge2p/r_F λ 0 ≥ 2 p / r F , the sample size that the accuracy guarantee requires per iteration is of order ( p / r F ) Δ k − 2 (p/r_F)\Delta_k^{-2} ( p / r F ) Δ k − 2 , and this is the quantity to track: hidden in the index it reappears as a burn-in of order exp ( ( p / r F ) 1 / ( 1 + ϵ ) ) \exp((p/r_F)^{1/(1+\epsilon)}) exp (( p / r F ) 1/ ( 1 + ϵ ) ) , which for the unscaled sketch below is exponential in d d d . With Δ k ≥ κ a ϵ \Delta_k\ge\kappa_a\epsilon Δ k ≥ κ a ϵ before T ϵ T_\epsilon T ϵ ,
T ϵ ≲ κ a − 2 ϵ − 2 , N k ≲ p r F κ a − 2 ϵ − 2 , W ϵ ≲ p N k T ϵ ≲ p 2 r F κ a − 4 ϵ − 4 , (44) T_\epsilon\lesssim\kappa_a^{-2}\epsilon^{-2},\qquad N_k\lesssim\frac{p}{r_F}\kappa_a^{-2}\epsilon^{-2},\qquad W_\epsilon\lesssim pN_kT_\epsilon\lesssim\frac{p^2}{r_F}\kappa_a^{-4}\epsilon^{-4}, \tag*{(44)} T ϵ ≲ κ a − 2 ϵ − 2 , N k ≲ r F p κ a − 2 ϵ − 2 , W ϵ ≲ p N k T ϵ ≲ r F p 2 κ a − 4 ϵ − 4 , (44)
all up to polylogarithmic factors.
Where the factor p p p in N k N_k N k comes from. Lemma 4.6 controls sup ∥ s ^ ∥ ≤ Δ k ∣ D ^ k ( s ^ , n ) ∣ \sup_{\|\hat{s}\|\leq\Delta_k}|\hat{D}_k(\hat{s},n)| sup ∥ s ^ ∥ ≤ Δ k ∣ D ^ k ( s ^ , n ) ∣ at the scale κ Q Δ k ( p + ϑ ) / n \kappa_Q\Delta_k\sqrt{(p+\vartheta)/n} κ Q Δ k ( p + ϑ ) / n , the p \sqrt{p} p being the Gaussian width of the p p p -dimensional ball, and this must be brought below κ e d F Δ k 2 \kappa_{\mathrm{ed}F}\Delta_k^2 κ ed F Δ k 2 . The factor is intrinsic to a uniform certificate: the supremum of a linear functional over a p p p -ball is the norm of a p p p -vector of averaged noise, of order p / d \sqrt{p/d} p / d . It is what certifying accuracy at a point selected by the replications costs in the analysis; a pointwise bound at an independently evaluated trial point does not pay it, and whether the algorithm pays it is a different question, since the factor enters a sufficient condition and no lower bound is given. In a subspace with p k = O ( log k ) p_k=O(\log k) p k = O ( log k ) the factor is polylogarithmic, so the certificate for reuse is essentially free there. In the full space, p = d p=d p = d , it is a factor d d d in the sample size of our bound, or an exponential-in-d d d burn-in if hidden in k λ k_\lambda k λ , so our bound for the reuse variant is one power of d d d worse than for a fresh-stream variant while the saving in oracle calls per iteration is a factor ( 2 d + 3 ) / ( 2 d + 2 ) (2d+3)/(2d+2) ( 2 d + 3 ) / ( 2 d + 2 ) . We read this as a limitation of the certificate rather than as advice against reuse, which is what ASTRO-DF has always done in the full space.
Choosing the scale. With κ e d F \kappa_{\mathrm{ed}F} κ ed F fixed and c ˉ : = κ Q 2 \bar{c}:=\kappa_Q^2 c ˉ := κ Q 2 , (42) implies κ a − 2 ≍ d ( c ˉ + κ e d F + p − 1 / 2 ) 2 / c ˉ \kappa_a^{-2}\asymp d(\bar{c}+\kappa_{\mathrm{ed}F}+p^{-1/2})^2/\bar{c} κ a − 2 ≍ d ( c ˉ + κ ed F + p − 1/2 ) 2 / c ˉ , minimized at c ˉ = κ e d F + p − 1 / 2 \bar{c}=\kappa_{\mathrm{ed}F}+p^{-1/2} c ˉ = κ ed F + p − 1/2 with value ≍ d ( κ e d F + p − 1 / 2 ) \asymp d(\kappa_{\mathrm{ed}F}+p^{-1/2}) ≍ d ( κ ed F + p − 1/2 ) ; lowering κ e d F \kappa_{\mathrm{ed}F} κ ed F therefore helps down to κ e d F ≍ p − 1 / 2 \kappa_{\mathrm{ed}F}\asymp p^{-1/2} κ ed F ≍ p − 1/2 , beyond which the additive term dominates. The optimum is
κ e d F ≍ p − 1 / 2 , κ Q ≍ p − 1 / 4 , κ a − 2 ≍ d p − 1 / 2 , 1 r F ≍ p 1 / 2 . (45) \kappa_{\mathrm{ed}F}\asymp p^{-1/2},\qquad
\kappa_Q\asymp p^{-1/4},\qquad
\kappa_a^{-2}\asymp d p^{-1/2},\qquad
\frac{1}{r_F}\asymp p^{1/2}. \tag*{(45)} κ ed F ≍ p − 1/2 , κ Q ≍ p − 1/4 , κ a − 2 ≍ d p − 1/2 , r F 1 ≍ p 1/2 . (45)
The tolerance κ e d F \kappa_{\mathrm{ed}F} κ ed F is a parameter of the analysis, not of the algorithm: every result holds for each κ e d F ∈ ( 0 , θ a ) \kappa_{\mathrm{ed}F}\in(0,\theta_a) κ ed F ∈ ( 0 , θ a ) , and a smaller value is paid for through (43) , by the factor 1 / r F ≍ p 1 / 2 1/r_F\asymp p^{1/2} 1/ r F ≍ p 1/2 in the sample size or by a later burn-in k λ k_\lambda k λ . In the deterministic analysis of [5 ] the corresponding constant is κ d ≍ p κ Q 2 \kappa_d\asymp\sqrt{p}\kappa_Q^2 κ d ≍ p κ Q 2 with no estimation term, and the same balance against the additive 1 gives κ Q ≍ p − 1 / 4 \kappa_Q\asymp p^{-1/4} κ Q ≍ p − 1/4 there too; [5 Remark 2.5] treats p = O ( 1 ) p=O(1) p = O ( 1 ) and so records only that scales below d − 1 / 2 d^{-1/2} d − 1/2 gain nothing, which is correct when p p p is not tracked.
Table 3. Dimension dependence up to polylog factors, with ( Δ 0 , Δ max , μ , κ s , κ H , κ e d F ) (\Delta_0,\Delta_{\max},\mu,\kappa_s,\kappa_H,\kappa_{\mathrm{ed}F}) ( Δ 0 , Δ m a x , μ , κ s , κ H , κ ed F ) fixed in subspace coordinates. Deterministic columns from [5 , 6 ] with O ( p ) O(p) O ( p ) evaluations per iteration; stochastic columns from (44) . The unscaled sketch d / p U p \sqrt{d/p}\,U_p d / p U p has the same constants as an unscaled Gaussian or hashing transform, and S T / d S^\mathsf{T}/\sqrt{d} S T / d the same as U p / p U_p/\sqrt{p} U p / p .
Insights from the results
In d d d , every subspace scale with κ Q = O ( 1 ) \kappa_Q=O(1) κ Q = O ( 1 ) gives T ϵ = O ~ ( d ϵ − 2 ) T_\epsilon=\widetilde{O}(d\epsilon^{-2}) T ϵ = O ( d ϵ − 2 ) and W ϵ = O ~ ( d 2 ϵ − 4 ) W_\epsilon=\widetilde{O}(d^2\epsilon^{-4}) W ϵ = O ( d 2 ϵ − 4 ) , against d d d and d 4 d^4 d 4 in the full space: a factor d 2 d^2 d 2 in the sample complexity, one d d d from the point count and one from the entropy of the trust region.
The unscaled sketch d / p U p \sqrt{d/p}\,U_p d / p U p is worse than the full space by d / p d/p d / p in iterations and in samples, and its sample size carries a factor d d d through 1 / r F ≍ d / p 1/r_F\asymp d/p 1/ r F ≍ d / p ; this is the case in which hiding 2 p / r F 2p/r_F 2 p / r F in the burn-in index conceals an exponential-in-d d d burn-in. The one-line change to orthonormal columns removes all of this.
The Curtis–Roberts scale S T / d S^\mathsf{T}/\sqrt{d} S T / d shrinks the bias below the estimation error and, with κ e d F \kappa_{\mathrm{ed}F} κ ed F fixed, loses a factor p p p in iterations relative to orthonormal columns; matching κ e d F ≍ κ Q 2 \kappa_{\mathrm{ed}F}\asymp\kappa_Q^2 κ ed F ≍ κ Q 2 restores d d d at a cost in 1 / r F 1/r_F 1/ r F . This is the stochastic form of Proposition 3.2: the scale is a parameter choice, and in the stochastic setting it must be made jointly with the accuracy demanded of the estimates.
The balanced scale (45) gains p \sqrt{p} p in iterations over every other row, deterministically and stochastically.
The empirical preference for small p p p observed in experiments is not explained by any row; every bound prefers large p p p in T ϵ T_{\epsilon} T ϵ and penalizes it only through the polynomial prefactors of W ϵ W_{\epsilon} W ϵ .
Concluding remarks
The paper set out to make the pathwise reading of a stochastic trust-region algorithm available, with its assumptions, outputs and limits stated plainly, to readers accustomed to the expectation reading. In that reading the requirements are summability of failure probabilities, obtained here by inflating the sample size logarithmically and growing the subspace dimension logarithmically; the device is the first Borel–Cantelli lemma, which needs no independence and is why common random numbers cause no trouble; the outputs are almost sure statements with random constants and random thresholds; and the limit is that nothing is said in expectation, though § 7.3 shows the burn-in has an explicit, superpolynomially small tail, so finite-time high-probability statements come from the same computation. Within that reading we have shown that the sample size being a stopping time is a property to be used, by optional stopping, rather than worked around by a union bound, which is also where the pathwise analysis of [18 ] is sharpened here; that a data-dependent trial point calls for a uniform bound, not a pointwise one, while a trial point evaluated on its own stream does not; that at a fixed subspace dimension the eventual-accuracy argument gives exponent 2 + O ( 1 / p ) 2 + O(1/p) 2 + O ( 1/ p ) , with the loss traced to the running maximum of a geometric depth; that the quadratic term of the model is a bounded perturbation in the first-order theory; and that the dimension dependence of the constants, once the sketch scale is understood as a parametrization, favors orthonormal columns and a balanced scale, with reuse costing, in our bounds, a factor p p p that is polylogarithmic in a subspace and a genuine d d d in the full space. Two things remain open: an explanation for the empirical preference for very small p p p , and whether the framework of Part I can be extended to slowly varying constants so as to give the pathwise route expected bounds as well.
Acknowledgments
This material was based upon work supported by National Science Foundation Grant CMMI-2226347, OAC-2410949 and Office of Naval Research Grant N000142412398. The first author gratefully acknowledges the discussions with Javier Madariaga regarding the finite-time high-probability bounds.