Introduction
We study the finite-sum problem
min x ∈ R d f ( x ) : = 1 n ∑ i = 1 n f i ( x ) , (1) \min_{x\in\mathbb{R}^d} f(x):=\frac{1}{n}\sum_{i=1}^{n}f_i(x), \tag*{(1)} x ∈ R d min f ( x ) := n 1 i = 1 ∑ n f i ( x ) , (1)
where each component f i ( ⋅ ) f_i(\cdot) f i ( ⋅ ) is possibly nonconvex. We seek an approximate local minimum in the sense of Nesterov and Polyak [15 ] : a point x ^ \hat{x} x ^ satisfying
∥ ∇ f ( x ^ ) ∥ ≤ ε and λ min ( ∇ 2 f ( x ^ ) ) ≥ − ρ ε , (2) \lVert\nabla f(\hat{x})\rVert\le\varepsilon\qquad\text{and}\qquad\lambda_{\min}\left(\nabla^2f(\hat{x})\right)\ge-\sqrt{\rho\varepsilon}, \tag*{(2)} ∥ ∇ f ( x ^ )∥ ≤ ε and λ m i n ( ∇ 2 f ( x ^ ) ) ≥ − ρε , (2)
where ρ \rho ρ is the Lipschitz constant of the average Hessian ∇ 2 f ( ⋅ ) \nabla^2f(\cdot) ∇ 2 f ( ⋅ ) . The curvature condition excludes saddle points with sufficiently negative curvature. Each oracle call returns the value, gradient, and one Hessian–vector product of a selected component.
Agarwal et al. [1 ] proposed FastCubic, which approximately solves cubic-regularized Newton subproblems [15 ] using accelerated variance reduction and shift-and-invert eigenvector routines. When every component Hessian is bounded by L L L , it finds a point satisfying (2) with
O ~ ( n ρ 1 / 2 Δ ε − 3 / 2 + n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) (3) \widetilde{O}\left(n\rho^{1/2}\Delta\varepsilon^{-3/2}+n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}\right) \tag*{(3)} O ( n ρ 1/2 Δ ε − 3/2 + n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) (3)
oracle calls, where Δ \Delta Δ bounds the initial objective gap. The first term accounts for full gradients at the cubic steps. The second comes from accelerated variance-reduced solves of shifted Hessian systems and dominates in the high-accuracy regime ε ≤ L 2 / ( n ρ ) \varepsilon\le L^2/(n\rho) ε ≤ L 2 / ( n ρ ) . For n = 1 n = 1 n = 1 , it matches the first-order lower bounds for deterministic [7 , 21 ] and randomized [20 ] algorithms. Our averaged-smoothness adaptation uses Katyusha X [2 ] for these solves. These results leave open whether the finite-sum factor n 3 / 4 n^{3/4} n 3/4 is necessary.
In this paper, we show that the high-accuracy complexity is Θ ~ ( n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) \widetilde{\Theta}(n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}) Θ ( n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) under mean-squared averaged smoothness , a weaker condition than the individual smoothness used by FastCubic. The upper bound follows by adapting its inverse solver and eigenvector routine to a second-moment bound on the component Hessians.
Our lower bound embeds the nested chain of Chen et al. [7 ] into a finite sum. Following Zhou [25 ] , we assign each quadratic bridge edge to a random component. Discovering an edge then costs order n n n queries, while averaged smoothness permits bridges long enough to give the factor n 3 / 4 n^{3/4} n 3/4 (Theorem 3 ). Replicating the spectral construction of Zhang et al. [20 ] extends the bound to unrestricted randomized algorithms (Theorem 4). Under individual smoothness, the bounds differ by at most a factor of n 1 / 4 n^{1/4} n 1/4 up to logarithmic factors for ε ≤ c L 2 / ( n 2 ρ ) \varepsilon\le cL^2/(n^2\rho) ε ≤ c L 2 / ( n 2 ρ ) .
In the complementary low-accuracy regime, we propose PathVR (path-length-based variance reduction), which uses O ~ ( n + n L Δ ε − 2 ) \widetilde{O}(n+\sqrt{n}L\Delta\varepsilon^{-2}) O ( n + n L Δ ε − 2 ) oracle calls. The dense-weak-hiding instances of Peng et al. [18 ] give a matching lower bound (Theorem 5).
Preliminaries and Related Work
We use ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ for the Euclidean norm of vectors and the spectral norm of matrices. We write [ q ] = { 1 , … , q } [q] = \{1,\ldots,q\} [ q ] = { 1 , … , q } , e k e_k e k for the k k k -th standard basis vector, and supp ( v ) \operatorname{supp}(v) supp ( v ) for the set of nonzero coordinates of v v v . The notation O ( ⋅ ) O(\cdot) O ( ⋅ ) , Ω ( ⋅ ) \Omega(\cdot) Ω ( ⋅ ) , and Θ ( ⋅ ) \Theta(\cdot) Θ ( ⋅ ) hides universal constants; O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) and Θ ~ ( ⋅ ) \widetilde{\Theta}(\cdot) Θ ( ⋅ ) also hide logarithmic factors in the problem parameters, accuracy, failure probability, and dimension.
Function Classes and Approximate Local Minima
The components f 1 , … , f n : R d → R f_1,\ldots,f_n:\mathbb{R}^d\to\mathbb{R} f 1 , … , f n : R d → R are twice continuously differentiable. We distinguish the following two smoothness conditions.
Assumption 1. For all x , x ′ ∈ R d x,x'\in\mathbb{R}^d x , x ′ ∈ R d ,
1 n ∑ i = 1 n ∥ ∇ f i ( x ) − ∇ f i ( x ′ ) ∥ 2 ≤ L 2 ∥ x − x ′ ∥ 2 . (4) \frac{1}{n}\sum_{i=1}^{n}\|\nabla f_i(x)-\nabla f_i(x')\|^2\le L^2\|x-x'\|^2. \tag*{(4)} n 1 i = 1 ∑ n ∥∇ f i ( x ) − ∇ f i ( x ′ ) ∥ 2 ≤ L 2 ∥ x − x ′ ∥ 2 . (4)
Assumption 2. For all i ∈ [ n ] i\in[n] i ∈ [ n ] and x ∈ R d x\in\mathbb{R}^d x ∈ R d , we have ∥ ∇ 2 f i ( x ) ∥ ≤ L \|\nabla^2 f_i(x)\|\le L ∥ ∇ 2 f i ( x ) ∥ ≤ L .
We refer to Assumptions 1 and 2 as averaged smoothness (AS) and individual smoothness (IS), respectively. Individual smoothness implies averaged smoothness, whereas (4) allows a component Hessian of norm n L \sqrt{n}L n L . Letting x ′ → x x'\to x x ′ → x in (4) gives, with H i = ∇ 2 f i ( x ) H_i=\nabla^2 f_i(x) H i = ∇ 2 f i ( x ) and H = ∇ 2 f ( x ) H=\nabla^2 f(x) H = ∇ 2 f ( x ) ,
1 n ∑ i = 1 n H i 2 ⪯ L 2 I , 1 n ∑ i = 1 n ( H i − H ) 2 ⪯ L 2 I , ∥ H ∥ ≤ L . (5) \frac{1}{n}\sum_{i=1}^{n}H_i^2\preceq L^2I,\qquad\frac{1}{n}\sum_{i=1}^{n}(H_i-H)^2\preceq L^2I,\qquad\|H\|\le L. \tag*{(5)} n 1 i = 1 ∑ n H i 2 ⪯ L 2 I , n 1 i = 1 ∑ n ( H i − H ) 2 ⪯ L 2 I , ∥ H ∥ ≤ L . (5)
We impose the following condition on the average Hessian and the initial gap.
Assumption 3. For all x , x ′ ∈ R d x,x'\in\mathbb{R}^d x , x ′ ∈ R d , we have ∥ ∇ 2 f ( x ) − ∇ 2 f ( x ′ ) ∥ ≤ ρ ∥ x − x ′ ∥ \|\nabla^2 f(x)-\nabla^2 f(x')\|\le\rho\|x-x'\| ∥ ∇ 2 f ( x ) − ∇ 2 f ( x ′ ) ∥ ≤ ρ ∥ x − x ′ ∥ , and the initial point satisfies f ( 0 ) − inf x f ( x ) ≤ Δ f(0)-\inf_x f(x)\le\Delta f ( 0 ) − inf x f ( x ) ≤ Δ .
As in Agarwal et al. [1 ] , this condition concerns the average Hessian. The component Hessian-Lipschitz constants may be larger, although our high-accuracy hard instances have individually ρ \rho ρ -Hessian-Lipschitz components. We write F A S ( n , L , ρ , Δ ) \mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta) F AS ( n , L , ρ , Δ ) and F I S ( n , L , ρ , Δ ) \mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta) F IS ( n , L , ρ , Δ ) for the classes of finite sums in all finite dimensions that satisfy Assumption 3 together with Assumption 1 and Assumption 2, respectively. Throughout, we assume ϵ ≤ L 2 / ρ \epsilon\le L^2/\rho ϵ ≤ L 2 / ρ , since otherwise the bound ∥ ∇ 2 f ( x ) ∥ ≤ L \lVert\nabla^2 f(x)\rVert\le L ∥ ∇ 2 f ( x )∥ ≤ L already implies the curvature condition in (2) .
Oracle and Algorithm Classes
We count queries to the following component oracle.
Definition 1. Given an index i ∈ [ n ] i \in[n] i ∈ [ n ] , a point x x x , and a direction v v v , the component Hessian–vector oracle returns ( f i ( x ) , ∇ f i ( x ) , ∇ 2 f i ( x ) v ) (f_i(x), \nabla f_i(x), \nabla^2 f_i(x)v) ( f i ( x ) , ∇ f i ( x ) , ∇ 2 f i ( x ) v ) . Each call counts as one query, so a full gradient or a full Hessian–vector product costs n n n queries.
Definition 2. Write g t = ∇ f i t ( x t ) g^t = \nabla f_{i_t}(x^t) g t = ∇ f i t ( x t ) and h t = ∇ 2 f i t ( x t ) v t h^t = \nabla^2 f_{i_t}(x^t)v^t h t = ∇ 2 f i t ( x t ) v t for the responses to the t t t -th query, and let S t = ⋃ s ≤ t ( supp ( g s ) ∪ supp ( h s ) ) S^t = \bigcup_{s\le t}(\operatorname{supp}(g^s)\cup\operatorname{supp}(h^s)) S t = ⋃ s ≤ t ( supp ( g s ) ∪ supp ( h s )) . The first query is at x 1 = 0 x^1=0 x 1 = 0 with v 1 = 0 v^1=0 v 1 = 0 . A zero-respecting algorithm satisfies supp ( x t ) ∪ supp ( v t ) ⊆ S t − 1 \operatorname{supp}(x^t)\cup\operatorname{supp}(v^t)\subseteq S^{t-1} supp ( x t ) ∪ supp ( v t ) ⊆ S t − 1 for every t ≥ 1 t\ge1 t ≥ 1 , and supp ( x ^ t ) ⊆ S t \operatorname{supp}(\widehat{x}^t)\subseteq S^t supp ( x t ) ⊆ S t for every output x ^ t \widehat{x}^t x t after t t t queries.
Query indices, points, directions, and stopping decisions may depend measurably on the transcript and private randomness. Linear-span methods started at the origin satisfy Definition 2. Methods using random starting vectors, including Oja’s iteration and shift-and-invert routines, need not. We call algorithms without the support restriction unrestricted randomized algorithms . For a function class F \mathcal{F} F , let N ϵ ( F ) \mathcal{N}_{\epsilon}(\mathcal{F}) N ϵ ( F ) be the smallest fixed query budget with which some unrestricted randomized algorithm satisfies (2) with probability at least 2 / 3 2/3 2/3 on every instance of F \mathcal{F} F . We define N ϵ z r ( F ) \mathcal{N}_{\epsilon}^{\mathrm{zr}}(\mathcal{F}) N ϵ zr ( F ) in the same way for randomized zero-respecting algorithms, requiring only the gradient condition in (2) , since a zero-respecting algorithm cannot certify curvature at a saddle point with zero gradient. Algorithms may know the class parameters and the dimension. Each of our lower bounds holds in a sufficiently large finite dimension and already prevents the gradient condition.
Related Work
Approximate local minima of finite sums. Perturbed gradient methods [12 ] and negative-curvature extraction [4 ] , combined with nested or recursive variance reduction, find approximate local minima using O ~ ( n ϵ − 2 + n ϵ − 3 / 2 + n 3 / 4 ϵ − 7 / 4 ) \widetilde{O}(\sqrt{n}\epsilon^{-2}+n\epsilon^{-3/2}+n^{3/4}\epsilon^{-7/4}) O ( n ϵ − 2 + n ϵ − 3/2 + n 3/4 ϵ − 7/4 ) oracle calls in normalized parameters [13 , 24 ] . For ϵ ≤ L 2 / ( n ρ ) \epsilon\le L^2/(n\rho) ϵ ≤ L 2 / ( n ρ ) , all of these bounds and (3) are dominated by n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ϵ − 7 / 4 n^{3/4}L^{1/2}\rho^{1/4}\Delta\epsilon^{-7/4} n 3/4 L 1/2 ρ 1/4 Δ ϵ − 7/4 or by the larger term n L Δ ϵ − 2 \sqrt{n}L\Delta\epsilon^{-2} n L Δ ϵ − 2 . To our knowledge, previous lower bounds in this regime gave at most the sum of Ω ( n ) \Omega(n) Ω ( n ) and the single-function rate.
Lower bounds for a single function. Carmon et al. [6 ] established the lower bound Ω ( ϵ − 12 / 7 ) \Omega(\epsilon^{-12/7}) Ω ( ϵ − 12/7 ) for first-order methods on functions with Lipschitz Hessians. Zhou [21 ] obtained the tight deterministic bound Ω ( L 1 / 2 ρ 1 / 4 Δ ϵ − 7 / 4 ) \Omega(L^{1/2}\rho^{1/4}\Delta\epsilon^{-7/4}) Ω ( L 1/2 ρ 1/4 Δ ϵ − 7/4 ) by a block chain, and Chen et al. [7 Section 3.3] gave an alternative proof by a nested chain whose hyper-objective is exactly the nonconvex chain of Carmon et al. [6 ] . Zhang et al. [20 ] proved the same bound for randomized algorithms with values and gradients by a spectral construction. We embed the nested chain of Chen et al. [7 ] into finite sums and extend the construction of Zhang et al. [20 ] to exact Hessian–vector products and replicate it across components.
Table 1. The component-oracle complexity of achieving (2) in the high-accuracy regime ε ≤ c 0 L 2 / ( n ρ ) \varepsilon\le c_0L^2/(n\rho) ε ≤ c 0 L 2 / ( n ρ ) with ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2} \ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 . ZR denotes zero-respecting algorithms (Definition 2); all other rows allow unrestricted randomized algorithms with Hessian–vector products. †The single-function bounds apply to finite sums with identical components and do not grow with n n n . ‡The IS lower bounds hold for ε ≤ c 0 L 2 / ( n 2 ρ ) \varepsilon\le c_0L^2/(n^2\rho) ε ≤ c 0 L 2 / ( n 2 ρ ) . In this regime both FastCubic rows equal (3) up to constants.
Random edge owners and the factor n 3 / 4 n^{3/4} n 3/4 . For strongly convex sums of nonconvex components, the factor n 3 / 4 n^{3/4} n 3/4 appears under averaged smoothness [22 Theorem 4.1] and is attained by Katyusha X [2 ] . Han et al. [11 ] obtain related bounds by partitioning tridiagonal chains among components. For nonconvex–strongly-concave finite sums, Zhou [25 ] assigns the internal edges of dual paths to random components and obtains the factor n 3 / 4 κ n^{3/4}\sqrt{\kappa} n 3/4 κ per primal link. Our construction applies the same assignment to the quadratic bridges of a nested chain. Under individual smoothness, all of these constructions give only n \sqrt{n} n , and whether Katyusha X is optimal in that setting is open.
Low accuracy and dense weak hiding. Without the curvature condition, recursive gradient estimators attain O ( n + n L Δ ε − 2 ) O(n+\sqrt{n}L\Delta\varepsilon^{-2}) O ( n + n L Δ ε − 2 ) oracle calls under averaged smoothness [9 , 14 ] . This rate is optimal under averaged smoothness [9 , 22 ] and, by the dense-weak-hiding construction of Peng et al. [18 ] , under individual smoothness. These results do not control the Hessian-Lipschitz constant at scale ρ \rho ρ . We show that the average of the dense-weak-hiding instances satisfies Assumption 3 when ε ≳ L 2 / ( n ρ ) \varepsilon\gtrsim L^2/(n\rho) ε ≳ L 2 / ( n ρ ) (Theorem 5).
Other oracle models. Arjevani et al. [5 ] study stochastic second-order oracles with fresh samples, whose rates do not transfer to finite sums. Chen et al. [8 ] extend this model to reusable samples with full Hessians and leave the Hessian–vector model open. When each call returns a full component Hessian, cubic regularization [15 ] needs only O ( 1 + ρ 1 / 2 Δ ε − 3 / 2 ) O(1+\rho^{1/2}\Delta\varepsilon^{-3/2}) O ( 1 + ρ 1/2 Δ ε − 3/2 ) full Hessians, which changes the high-accuracy rate (Proposition 2). The matching lower bound uses components whose Hessian-Lipschitz constants grow with n n n , since Assumption 3 constrains only the average Hessian. When every component Hessian is ρ \rho ρ -Lipschitz, the recursive Taylor estimators of Zhou and Gu [23 ] find a point with ∥ ∇ f ( x ˉ ) ∥ ≤ ε \|\nabla f(\bar{x})\| \le\varepsilon ∥∇ f ( x ˉ ) ∥ ≤ ε using O ~ ( n + n 3 / 4 ρ − 1 / 2 Δ ε − 3 / 2 ) \widetilde{O}(n+n^{3/4}\rho^{-1/2}\Delta\varepsilon^{-3/2}) O ( n + n 3/4 ρ − 1/2 Δ ε − 3/2 ) full component Hessians, and Wu et al. [19 ] show that this rate is optimal for unrestricted randomized algorithms when no bound on L L L is imposed; their characterization Θ p ( n + Δ L p 1 / p − 1 n − 1 / ( 2 p ) ε − ( p + 1 ) / p ) \Theta_p(n+\Delta L_p^{1/p-1}n^{-1/(2p)}\varepsilon^{-(p+1)/p}) Θ p ( n + Δ L p 1/ p − 1 n − 1/ ( 2 p ) ε − ( p + 1 ) / p ) covers oracles returning all derivatives through order p ≥ 2 p\ge2 p ≥ 2 . Variance-reduced cubic Newton methods have also been analyzed under averaged Hessian assumptions [16 ] . Tables 1 and 2 compare the known bounds with ours.
Upper Bounds
We first develop a curvature search under averaged smoothness in Section 3.1. We then introduce PathVR, which attains the low-accuracy upper bound, in Section 3.2. Finally, Section 3.3 extends FastCubic to averaged smoothness.
Table 2. The component-oracle complexity of achieving (2) in the low-accuracy regime L 2 / ( n ρ ) ≤ ε ≤ L 2 / ρ L^2/(n\rho)\le\varepsilon\le L^2/\rho L 2 / ( n ρ ) ≤ ε ≤ L 2 / ρ . AS and IS denote averaged and individual smoothness (Assumptions 1 and 2). †These methods only guarantee ∥ ∇ f ( x ^ ) ∥ ≤ ε \|\nabla f(\hat{x})\|\le\varepsilon ∥∇ f ( x ^ ) ∥ ≤ ε . ‡Each oracle call returns the full component Hessian ∇ 2 f i ( x ) \nabla^2 f_i(x) ∇ 2 f i ( x ) . §The bound assumes that every component Hessian is ρ \rho ρ -Lipschitz, a subclass of IS.
Curvature Search under Averaged Smoothness
Given a point x x x and a threshold δ \delta δ , we seek either a unit direction of curvature at most − δ / 2 -\delta/2 − δ /2 or a certificate that λ min ( ∇ 2 f ( x ) ) ≥ − δ \lambda_{\min}(\nabla^2 f(x))\ge-\delta λ m i n ( ∇ 2 f ( x )) ≥ − δ . Algorithm 1 applies Oja’s iteration to the sampled shifted Hessians 2 L I − ∇ 2 f i t ( x ) 2LI-\nabla^2 f_{i_t}(x) 2 L I − ∇ 2 f i t ( x ) . Their mean Σ = 2 L I − ∇ 2 f ( x ) \Sigma=2LI-\nabla^2 f(x) Σ = 2 L I − ∇ 2 f ( x ) satisfies L I ⪯ Σ ⪯ 3 L I LI\preceq\Sigma\preceq3LI L I ⪯ Σ ⪯ 3 L I , and their variance is at most L 2 L^2 L 2 by (5) . A top eigenvector of Σ \Sigma Σ is therefore a bottom eigenvector of ∇ 2 f ( x ) \nabla^2 f(x) ∇ 2 f ( x ) .
We validate each candidate using a median of sample means of its Rayleigh quotient, with fresh indices and the same variance bound. The algorithm returns the candidate with the smallest estimate if that estimate is sufficiently negative, and the zero vector otherwise. We choose the parameters
α = δ 24 L , Λ d = log e d α , a = C 1 Λ d α , T = ⌈ C 2 Λ d 2 α 2 ⌉ , \alpha=\frac{\delta}{24L},\qquad\Lambda_d=\log\frac{ed}{\alpha},\qquad a=\frac{C_1\Lambda_d}{\alpha},\qquad T=\left\lceil\frac{C_2\Lambda_d^2}{\alpha^2}\right\rceil, α = 24 L δ , Λ d = log α e d , a = α C 1 Λ d , T = ⌈ α 2 C 2 Λ d 2 ⌉ ,
R = ⌈ log ( 2 / p ) log 4 ⌉ , m = ⌈ 4096 L 2 δ 2 ⌉ , M = ⌈ C 3 log ( 2 R / p ) ⌉ , (6) R=\left\lceil\frac{\log(2/p)}{\log4}\right\rceil,\qquad m=\left\lceil\frac{4096L^2}{\delta^2}\right\rceil,\qquad M=\lceil C_3\log(2R/p)\rceil, \tag*{(6)} R = ⌈ log 4 log ( 2/ p ) ⌉ , m = ⌈ δ 2 4096 L 2 ⌉ , M = ⌈ C 3 log ( 2 R / p )⌉ , (6)
where C 1 , C 2 , C 3 C_1,C_2,C_3 C 1 , C 2 , C 3 are sufficiently large universal constants. The gap-free analysis of Oja’s iteration by Gu et al. [10 ] requires only the variance bound L 2 L^2 L 2 . It gives the following guarantee, proved in Appendix § 9 .§ 1 .
Proposition 1 (cf. Gu et al. [10 Lemma 10] ). Assume (5) at x x x , and let 0 < δ ≤ L 0<\delta\le L 0 < δ ≤ L and 0 < p < 1 / 2 0<p<1/2 0 < p < 1/2 . Algorithm 1 uses O ( L 2 δ 2 [ log 2 e d L δ + log 2 log ( 2 / p ) p ] log 2 p ) O\left(\frac{L^2}{\delta^2}\left[\log^2\frac{edL}{\delta}+\log\frac{2\log(2/p)}{p}\right]\log\frac{2}{p}\right) O ( δ 2 L 2 [ log 2 δ e d L + log p 2 l o g ( 2/ p ) ] log p 2 ) component Hessian–vector products at x x x . With probability at least 1 − p 1-p 1 − p , its output u u u is either a unit vector with u ⊤ ∇ 2 f ( x ) u ≤ − δ / 2 u^\top\nabla^2f(x)u\le-\delta/2 u ⊤ ∇ 2 f ( x ) u ≤ − δ /2 , or u = 0 u=0 u = 0 and λ min ( ∇ 2 f ( x ) ) ≥ − δ \lambda_{\min}(\nabla^2f(x))\ge-\delta λ m i n ( ∇ 2 f ( x )) ≥ − δ .
Path-Length-Based Variance Reduction
We build on the recursive gradient estimator of SPIDER [9 ] ,
v t + 1 = v t + 1 b t ∑ j ∈ B t ( ∇ f j ( x t + 1 ) − ∇ f j ( x t ) ) , (7) v^{t+1}=v^t+\frac{1}{b^t}\sum_{j\in B^t}\left(\nabla f_j(x^{t+1})-\nabla f_j(x^t)\right), \tag*{(7)} v t + 1 = v t + b t 1 j ∈ B t ∑ ( ∇ f j ( x t + 1 ) − ∇ f j ( x t ) ) , (7)
where B t B^t B t is a mini-batch of b t b^t b t indices drawn uniformly from [ n ] [n] [ n ] . Under Assumption 1, the update (7) adds an error of variance at most L 2 ∥ x t + 1 − x t ∥ 2 / b t L^2\|x^{t+1}-x^t\|^2/b^t L 2 ∥ x t + 1 − x t ∥ 2 / b t . The accuracy of v t v^t v t thus depends on the
Algorithm 1 CurvSearch(x; δ, p)
Input: point x, threshold 0 < δ ≤ L, failure probability 0 < p < 1/2; parameters (6).
1: for r = 1, . . . , R do
2: Draw w_r^0 uniformly from the unit sphere.
3: for t = 0, 1, . . . , T − 1 do
4: Draw i_t uniformly from [n] and set η_t ← a/(3L(T/4 + t)).
5: w̃ ← w_r^t + η_t(2Lw_r^t − ∇²f_{i_t}(x)w_r^t).
6: if ‖w̃‖ = 0 then
7: w_r^T ← e_1; break the inner loop.
8: else
9: w_r^{t+1} ← w̃/‖w̃‖.
10: end if
11: end for
12: λ̂_r ← the median of M independent averages, each of m samples (w_r^T)ᵀ∇²f_i(x)w_r^T with i uniform on [n].
13: end for
14: r^⋆ ← arg min_{r∈[R]} λ̂_r.
15: if λ̂_{r⋆} ≤ −5δ/8 then return u = w_{r⋆}^T else return u = 0.
lengths of the steps since the last full gradient. SPIDER uses a fixed number of iterations between refreshes. A negative-curvature step has length ( ε / ρ ) 1 / 2 (\varepsilon/\rho)^{1/2} ( ε / ρ ) 1/2 , which is much larger than the gradient-step length ε / ( 2 L ) \varepsilon/(2L) ε / ( 2 L ) when ε ≤ L 2 / ρ \varepsilon\le L^2/\rho ε ≤ L 2 / ρ , and forces a full gradient at a cost of n n n oracle calls.
We propose PathVR (path-length-based variance reduction, Algorithm 2), which chooses both the mini-batch size and the refresh interval by step length. Given a window length ℓ > 0 \ell> 0 ℓ > 0 , a step of length s t = ∥ x t + 1 − x t ∥ s^t = \lVert x^{t+1} - x^t \rVert s t = ∥ x t + 1 − x t ∥ uses a mini-batch of size b t = ⌈ n s t / ℓ ⌉ b^t = \lceil ns^t/\ell\rceil b t = ⌈ n s t / ℓ ⌉ . We recompute the full gradient when the accumulated length W t W^t W t of the current window would exceed ℓ \ell ℓ , or after a single step longer than ℓ / 2 \ell/2 ℓ /2 .
At each iteration, the method takes a normalized gradient step of length η \eta η if ∥ v t ∥ > 2 ε \lVert v^t \rVert> 2\varepsilon ∥ v t ∥ > 2 ε . Otherwise, it calls CurvSearch( x t ; δ , p / ( 2 K ) ) (x^t; \delta, p/(2K)) ( x t ; δ , p / ( 2 K )) from Algorithm 1. If the search returns u t = 0 u^t = 0 u t = 0 , the method returns x t x^t x t , an approximate local minimum by Proposition 1. Otherwise, it takes a step of length r r r along the unit vector u t u^t u t , with its sign chosen against v t v^t v t . The tie-breaking rule σ t = 1 \sigma^t = 1 σ t = 1 is necessary: without it, the method stalls at the saddle point of f i ( x ) = cos x f_i(x) = \cos x f i ( x ) = cos x with x 0 = 0 x^0 = 0 x 0 = 0 .
On the event of Theorem 1 below, the method terminates when the curvature search returns zero. The fallback output x 0 x^0 x 0 and the abort when the query budget B B B is exhausted occur only on the failure event. They ensure a deterministic bound on the number of oracle calls.
The following lemma gives uniform accuracy of the estimator along the trajectory. We prove it using the Freedman inequality in Hilbert spaces [17 Theorem 2.1] ; under individual smoothness, the Azuma–Hoeffding inequality suffices.
Lemma 1. Under Assumption 1, run Algorithm 2 with p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , K ≥ 2 K \ge2 K ≥ 2 , c p = 64 log 2 ( 4 K / p ) c_p = 64\log^2(4K/p) c p = 64 log 2 ( 4 K / p ) , and ℓ = n ε / ( 16 c p L ) \ell= \sqrt{n}\varepsilon/(16\sqrt{c_p}L) ℓ = n ε / ( 16 c p L ) . Then with probability at least 1 − p / 2 1-p/2 1 − p /2 , it holds that ∥ v t − ∇ f ( x t ) ∥ ≤ ε / 16 \lVert v^t - \nabla f(x^t)\rVert\le\varepsilon/16 ∥ v t − ∇ f ( x t )∥ ≤ ε /16 for all iterations t t t performed by the algorithm.
We choose the parameters
Algorithm 2 PathVR: Path-Length-Based Variance Reduction
Input: ε , η , δ , r , ℓ , K , B , p \varepsilon,\eta,\delta,r,\ell,K,B,p ε , η , δ , r , ℓ , K , B , p ; initial point x 0 = 0 x^0=0 x 0 = 0 .
1: v 0 ← ∇ f ( x 0 ) v^0 \leftarrow\nabla f(x^0) v 0 ← ∇ f ( x 0 ) , W 0 ← 0 W^0 \leftarrow0 W 0 ← 0 ; abort with output x 0 x^0 x 0 once B B B oracle calls have been made. 2: for t = 0 , 1 , … , K − 1 t=0,1,\ldots,K-1 t = 0 , 1 , … , K − 1 do 3: if ∥ v t ∥ > 2 ε \lVert v^t\rVert>2\varepsilon ∥ v t ∥ > 2 ε then 4: x t + 1 ← x t − η v t / ∥ v t ∥ x^{t+1}\leftarrow x^t-\eta v^t/\lVert v^t\rVert x t + 1 ← x t − η v t / ∥ v t ∥ . 5: else 6: u t ← CurvSearch ( x t ; δ , p / ( 2 K ) ) u^t\leftarrow\operatorname{CurvSearch}(x^t;\delta,p/(2K)) u t ← CurvSearch ( x t ; δ , p / ( 2 K )) by Algorithm 1. 7: if u t = 0 u^t=0 u t = 0 then return x t x^t x t . 8: σ t ← − sign ⟨ v t , u t ⟩ \sigma^t\leftarrow-\operatorname{sign}\langle v^t,u^t\rangle σ t ← − sign ⟨ v t , u t ⟩ , with σ t ← 1 \sigma^t\leftarrow1 σ t ← 1 if ⟨ v t , u t ⟩ = 0 \langle v^t,u^t\rangle=0 ⟨ v t , u t ⟩ = 0 . 9: x t + 1 ← x t + σ t r u t x^{t+1}\leftarrow x^t+\sigma^t r u^t x t + 1 ← x t + σ t r u t . 10: end if 11: s t ← ∥ x t + 1 − x t ∥ s^t\leftarrow\lVert x^{t+1}-x^t\rVert s t ← ∥ x t + 1 − x t ∥ , b t ← ⌈ n s t / ℓ ⌉ b^t\leftarrow\lceil ns^t/\ell\rceil b t ← ⌈ n s t / ℓ ⌉ . 12: if s t > ℓ / 2 s^t>\ell/2 s t > ℓ /2 or W t + s t > ℓ W^t+s^t>\ell W t + s t > ℓ then 13: v t + 1 ← ∇ f ( x t + 1 ) v^{t+1}\leftarrow\nabla f(x^{t+1}) v t + 1 ← ∇ f ( x t + 1 ) , W t + 1 ← 0 W^{t+1}\leftarrow0 W t + 1 ← 0 . 14: else 15: Draw B t = { j 1 t , … , j b t t } B^t=\{j^t_1,\ldots,j^t_{b^t}\} B t = { j 1 t , … , j b t t } uniformly and independently from [ n ] [n] [ n ] . 16: v t + 1 ← v t + 1 b t ∑ j ∈ B t ( ∇ f j ( x t + 1 ) − ∇ f j ( x t ) ) v^{t+1}\leftarrow v^t+\frac{1}{b^t}\sum_{j\in B^t}\left(\nabla f_j(x^{t+1})-\nabla f_j(x^t)\right) v t + 1 ← v t + b t 1 ∑ j ∈ B t ( ∇ f j ( x t + 1 ) − ∇ f j ( x t ) ) , W t + 1 ← W t + s t W^{t+1}\leftarrow W^t+s^t W t + 1 ← W t + s t . 17: end if 18: end for 19: return x 0 x^0 x 0 .
η = ε 2 L , δ = ( ρ ε ) 1 / 2 , r = ( ε ρ ) 1 / 2 , ℓ = n ε 16 c p L , \eta=\frac{\varepsilon}{2L},\qquad
\delta=(\rho\varepsilon)^{1/2},\qquad
r=\left(\frac{\varepsilon}{\rho}\right)^{1/2},\qquad
\ell=\frac{\sqrt{n}\varepsilon}{16\sqrt{c_p}L}, η = 2 L ε , δ = ( ρε ) 1/2 , r = ( ρ ε ) 1/2 , ℓ = 16 c p L n ε ,
K = max { 2 , ⌈ 1 + 32 L Δ 27 ε 2 + 97 ρ 1 / 2 Δ ε − 3 / 2 ⌉ } . (8) K=\max\left\{2,\left\lceil1+\frac{32L\Delta}{27\varepsilon^2}+97\rho^{1/2}\Delta\varepsilon^{-3/2}\right\rceil\right\}. \tag*{(8)} K = max { 2 , ⌈ 1 + 27 ε 2 32 L Δ + 97 ρ 1/2 Δ ε − 3/2 ⌉ } . (8)
with c p = 64 log 2 ( 4 K / p ) c_p=64\log^2(4K/p) c p = 64 log 2 ( 4 K / p ) , and set the query budget to
B = ⌈ C [ n + c p n L Δ ε − 2 + ( 1 + ρ 1 / 2 Δ ε − 3 / 2 ) Q n c ] ⌉ . (9) B=\left\lceil C\left[n+\sqrt{c_p}nL\Delta\varepsilon^{-2}+(1+\rho^{1/2}\Delta\varepsilon^{-3/2})Q_{\mathrm{nc}}\right]\right\rceil. \tag*{(9)} B = ⌈ C [ n + c p n L Δ ε − 2 + ( 1 + ρ 1/2 Δ ε − 3/2 ) Q nc ] ⌉ . (9)
where C C C is a sufficiently large universal constant and Q n c Q_{\mathrm{nc}} Q nc is the number of oracle calls in Proposition 1 with threshold δ \delta δ and failure probability p / ( 2 K ) p/(2K) p / ( 2 K ) . On the event of Lemma 1 and successful curvature searches, each gradient step decreases f f f by at least 27 32 ε 2 / L \frac{27}{32}\varepsilon^2/L 32 27 ε 2 / L and each curvature step by at least ε 3 / 2 / ( 48 ρ 1 / 2 ) \varepsilon^{3/2}/(48\rho^{1/2}) ε 3/2 / ( 48 ρ 1/2 ) . These descent bounds give the following theorem.
Theorem 1. Under Assumptions 1 and 3 , let 0 < ε ≤ L 2 / ρ 0<\varepsilon\le L^2/\rho 0 < ε ≤ L 2 / ρ and p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , and run Algorithm 2 from x 0 = 0 x^0=0 x 0 = 0 with the parameters (8) and the budget (9). Then with probability at least 1 − p 1-p 1 − p , the output x ^ \hat{x} x ^ satisfies
∥ ∇ f ( x ^ ) ∥ ≤ 33 16 ε and λ min ( ∇ 2 f ( x ^ ) ) ≥ − ( ρ ε ) 1 / 2 , \lVert\nabla f(\hat{x})\rVert\le\frac{33}{16}\varepsilon
\qquad\text{and}\qquad
\lambda_{\min}\left(\nabla^2 f(\hat{x})\right)\ge-(\rho\varepsilon)^{1/2}, ∥ ∇ f ( x ^ )∥ ≤ 16 33 ε and λ m i n ( ∇ 2 f ( x ^ ) ) ≥ − ( ρε ) 1/2 , and the algorithm uses at most
O ~ ( n + n L Δ ε − 2 + L 2 ρ ε + L 2 ρ − 1 / 2 Δ ε − 5 / 2 ) \widetilde{O}\left(n+\sqrt{n}L\Delta\varepsilon^{-2}+\frac{L^2}{\rho\varepsilon}+L^2\rho^{-1/2}\Delta\varepsilon^{-5/2}\right) O ( n + n L Δ ε − 2 + ρε L 2 + L 2 ρ − 1/2 Δ ε − 5/2 ) component oracle calls. The number of oracle calls never exceeds B B B , which is of the same order.
An amortized count gives the complexity bound. Both types of step decrease f f f by at least ε s t / 48 \varepsilon s^t/48 ε s t /48 , so the total path length is at most 48 Δ / ε 48\Delta/\varepsilon 48Δ/ ε . A step of length s t s^t s t samples at most 1 + n s t / ℓ 1+ns^t/\ell 1 + n s t / ℓ component indices, each requiring two gradient evaluations. Each refresh costs n n n calls and is triggered only after an accumulated length of at least ℓ / 2 \ell/2 ℓ /2 . The total cost of mini-batches and refreshes is therefore O ( n + K + n Δ / ( ε ℓ ) ) = O ~ ( n + n L Δ ε − 2 ) O(n+K+n\Delta/(\varepsilon\ell))=\widetilde{O}(n+\sqrt{n}L\Delta\varepsilon^{-2}) O ( n + K + n Δ/ ( ε ℓ )) = O ( n + n L Δ ε − 2 ) , giving the first two terms. The remaining two terms come from at most 1 + 48 ρ 1 / 2 Δ ε − 3 / 2 1+48\rho^{1/2}\Delta\varepsilon^{-3/2} 1 + 48 ρ 1/2 Δ ε − 3/2 curvature searches, each using O ~ ( L 2 / ( ρ ε ) ) \widetilde{O}(L^2/(\rho\varepsilon)) O ( L 2 / ( ρε )) Hessian–vector products. In the low-accuracy regime ε ≥ L 2 / ( n ρ ) \varepsilon\ge L^2/(n\rho) ε ≥ L 2 / ( n ρ ) , the third term is absorbed by n n n , and the fourth is at most a constant multiple of the second.
Corollary 1. In the setting of Theorem 1 with ε = 16 ε o u t / 33 \varepsilon=16\varepsilon_{\mathrm{out}}/33 ε = 16 ε out /33 , where L 2 / ( n ρ ) ≤ ε o u t ≤ L 2 / ρ L^2/(n\rho)\le\varepsilon_{\mathrm{out}}\le L^2/\rho L 2 / ( n ρ ) ≤ ε out ≤ L 2 / ρ , Algorithm 2 achieves (2) with tolerance ε o u t \varepsilon_{\mathrm{out}} ε out and probability at least 1 − p 1-p 1 − p within a fixed budget of O ~ ( n + n L Δ ε o u t − 2 ) \widetilde{O}(n+\sqrt{n}L\Delta\varepsilon_{\mathrm{out}}^{-2}) O ( n + n L Δ ε out − 2 ) component oracle calls.
The proofs of Lemma 1, Theorem 1, and Corollary 1 are given in Appendix § 9 .§ 2 .
FastCubic under Averaged Smoothness
To extend FastCubic to averaged smoothness, we replace its inverse solver and eigenvector routine, the only two procedures that use individual smoothness. Both replacements require only the second-moment bound (5). We first give an inverse solver based on a variant of Katyusha X whose analysis depends only on the variance.
Lemma 2. (cf. Allen-Zhu [2, Lemma 3.3]). Let A = n − 1 ∑ i H i + a I ⪰ μ I A=n^{-1}\sum_i H_i+aI\succeq\mu I A = n − 1 ∑ i H i + a I ⪰ μ I with μ > 0 \mu>0 μ > 0 , where H i H_i H i satisfy (5). Let η > 0 \eta>0 η > 0 , p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , and ϰ = ( L + ∣ a ∣ ) / μ \varkappa=(L+|a|)/\mu ϰ = ( L + ∣ a ∣ ) / μ . A randomized algorithm using O ~ ( n + n 3 / 4 ϰ 1 / 2 ) \widetilde{O}(n+n^{3/4}\varkappa^{1/2}) O ( n + n 3/4 ϰ 1/2 ) component matrix–vector products returns z z z with ∥ z − A − 1 b ∥ ≤ η ∥ b ∥ \lVert z-A^{-1}b\rVert\le\eta\lVert b\rVert ∥ z − A − 1 b ∥ ≤ η ∥ b ∥ with probability at least 1 − p 1-p 1 − p .
By (5), the SVRG estimator has centered variance at most L 2 ∥ z − z 0 ∥ 2 L^2\lVert z-z_0\rVert^2 L 2 ∥ z − z 0 ∥ 2 , as required by the variance-only epoch lemma of Allen-Zhu [2 ] . The eigenvector routine applies AppxPCA [3, Theorem 3.1 to the shifted inverses covered by Lemma 2. Since the outer loop of FastCubic uses only the average Hessian [1 Sections 3–7] , these replacements give the following theorem. Its proof is in Appendix § 9 .§ 3 .
Theorem 2. For 0 < ε ≤ L 2 / ρ 0<\varepsilon\le L^2/\rho 0 < ε ≤ L 2 / ρ and p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , a variant of FastCubic achieves (2) on F A S ( n , L , ρ , Δ ) \mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta) F AS ( n , L , ρ , Δ ) with probability at least 1 − p 1-p 1 − p within a fixed budget of
O ~ ( ( 1 + ρ 1 / 2 Δ ε − 3 / 2 ) ( n + n 3 / 4 L 1 / 2 ρ − 1 / 4 ε − 1 / 4 ) ) (10) \widetilde{O}\left(\left(1+\rho^{1/2}\Delta\varepsilon^{-3/2}\right)\left(n+n^{3/4}L^{1/2}\rho^{-1/4}\varepsilon^{-1/4}\right)\right) \tag*{(10)} O ( ( 1 + ρ 1/2 Δ ε − 3/2 ) ( n + n 3/4 L 1/2 ρ − 1/4 ε − 1/4 ) ) (10) queries. If ρ 1 / 2 Δ ε − 3 / 2 ≥ 1 \rho^{1/2}\Delta\varepsilon^{-3/2}\ge1 ρ 1/2 Δ ε − 3/2 ≥ 1 , this bound equals (3).
In the high-accuracy regime ε ≤ L 2 / ( n ρ ) \varepsilon\le L^2/(n\rho) ε ≤ L 2 / ( n ρ ) , the second term of (3) dominates. § 4 gives a matching lower bound.
Lower Bounds at High Accuracy
We next establish lower bounds in the high-accuracy regime. § 4.1 constructs a nested chain with random bridge owners for zero-respecting algorithms. § 4.2 extends the bound to unrestricted randomized algorithms through a replicated spectral construction.
Nested Chain with Random Bridge Owners
Let Υ ( t ) = 120 ∫ 0 t s 2 ( s − 1 ) / ( 1 + s 2 ) d s \Upsilon(t)=120\int_{0}^{t}s^{2}(s-1)/(1+s^{2})\,\mathrm{d}s Υ ( t ) = 120 ∫ 0 t s 2 ( s − 1 ) / ( 1 + s 2 ) d s be the scalar potential of Carmon et al. [6 ] . For integers T , m ≥ 2 T,m\ge2 T , m ≥ 2 , let x ˉ ∈ R T + 1 \bar{x}\in\mathbb{R}^{T+1} x ˉ ∈ R T + 1 and x ( i ) ∈ R m x^{(i)}\in\mathbb{R}^{m} x ( i ) ∈ R m for i ∈ [ T ] i\in[T] i ∈ [ T ] . Following Chen et al. [7, Equation (10)], we define
f ^ ( x ) = ν 2 ( 1 − x ˉ 1 ) 2 + 1 2 ∑ i = 1 T Q ^ m ( x ˉ i , x ( i ) , x ˉ i + 1 ) + ν ∑ i = 1 T Υ ( x ˉ i ) . (11) \hat{f}(x)=\frac{\nu}{2}(1-\bar{x}_{1})^{2}+\frac{1}{2}\sum_{i=1}^{T}\widehat{Q}_{m}(\bar{x}_{i},x^{(i)},\bar{x}_{i+1})+\nu\sum_{i=1}^{T}\Upsilon(\bar{x}_{i}). \tag*{(11)} f ^ ( x ) = 2 ν ( 1 − x ˉ 1 ) 2 + 2 1 i = 1 ∑ T Q m ( x ˉ i , x ( i ) , x ˉ i + 1 ) + ν i = 1 ∑ T Υ ( x ˉ i ) . (11)
Q ^ m ( a , y , b ) = 1 m ( y 1 − θ a ) 2 + ∑ j = 1 m − 1 ( y j + 1 − y j ) 2 + 1 m ( y m − θ b ) 2 , \widehat{Q}_{m}(a,y,b)=\frac{1}{m}(y_{1}-\theta a)^{2}+\sum_{j=1}^{m-1}(y_{j+1}-y_{j})^{2}+\frac{1}{m}(y_{m}-\theta b)^{2}, Q m ( a , y , b ) = m 1 ( y 1 − θ a ) 2 + j = 1 ∑ m − 1 ( y j + 1 − y j ) 2 + m 1 ( y m − θ b ) 2 ,
with m = ⌊ ( 3 ν ) − 1 / 2 ⌋ m=\lfloor(3\nu)^{-1/2}\rfloor m = ⌊( 3 ν ) − 1/2 ⌋ and θ = ( ν ( 3 m − 1 ) ) 1 / 2 \theta=(\nu(3m-1))^{1/2} θ = ( ν ( 3 m − 1 ) ) 1/2 . If ν ≤ 1 / 12 \nu\le1/12 ν ≤ 1/12 , then m ≥ 2 m\ge2 m ≥ 2 and θ m ≤ 1 \theta\sqrt{m}\le1 θ m ≤ 1 . Each bridge Q ^ m \widehat{Q}_{m} Q m connects consecutive outer coordinates and satisfies min y Q ^ m ( a , y , b ) = ν ( a − b ) 2 \min_{y}\widehat{Q}_{m}(a,y,b)=\nu(a-b)^{2} min y Q m ( a , y , b ) = ν ( a − b ) 2 by Chen et al. [7, Lemma 3.4]. Thus, the reduced objective obtained by minimizing over the bridge coordinates is exactly ν \nu ν times the nonconvex chain of Carmon et al. [6 ] . The full gradient norm is at least half the reduced-objective gradient norm [7 Lemma 3.5] . In the coordinate order x ˉ 1 , x 1 ( 1 ) , … , x m ( 1 ) , x ˉ 2 , … , x ˉ T , x 1 ( T ) , … , x m ( T ) , x ˉ T + 1 \bar{x}_{1},x_{1}^{(1)},\ldots,x_{m}^{(1)},\bar{x}_{2},\ldots,\bar{x}_{T},x_{1}^{(T)},\ldots,x_{m}^{(T)},\bar{x}_{T+1} x ˉ 1 , x 1 ( 1 ) , … , x m ( 1 ) , x ˉ 2 , … , x ˉ T , x 1 ( T ) , … , x m ( T ) , x ˉ T + 1 given in (23) , f ^ \hat{f} f ^ is a zero-chain with gradient norm at least ν / 8 \nu/8 ν /8 whenever the last two outer coordinates vanish. Since only the outer coordinates carry non-quadratic terms, extending the quadratic bridges does not increase their contribution to the Hessian-Lipschitz constant.
Write d i , j d_{i,j} d i , j for the vector e k − e k ′ e_{k}-e_{k'} e k − e k ′ that takes the difference of x j ( i ) x_{j}^{(i)} x j ( i ) and x j + 1 ( i ) x_{j+1}^{(i)} x j + 1 ( i ) for j ∈ [ m − 1 ] j\in[m-1] j ∈ [ m − 1 ] . For each bridge i i i , independently draw the owner σ i , 1 \sigma_{i,1} σ i , 1 of its first edge uniformly from [ n ] [n] [ n ] . For j ≥ 2 j\ge2 j ≥ 2 , draw σ i , j \sigma_{i,j} σ i , j uniformly from [ n ] ∖ { σ i , j − 1 } [n]\setminus\{\sigma_{i,j-1}\} [ n ] ∖ { σ i , j − 1 } , so that equal-owner edges have disjoint supports. For scalings δ , β > 0 \delta,\beta>0 δ , β > 0 , let C ( x ) C(x) C ( x ) be δ β 2 \delta\beta^{2} δ β 2 times the terms of f ^ ( x / β ) \hat{f}(x/\beta) f ^ ( x / β ) other than the internal edges, and define
P k = ∑ ( i , j ) : σ i , j = k d i , j d i , j T , f k ( x ) = C ( x ) + n δ 2 x T P k x ( k ∈ [ n ] ) . (12) P_{k}=\sum_{(i,j):\,\sigma_{i,j}=k}d_{i,j}d_{i,j}^{\mathsf{T}},\qquad f_{k}(x)=C(x)+\frac{n\delta}{2}x^{\mathsf{T}}P_{k}x\quad(k\in[n]). \tag*{(12)} P k = ( i , j ) : σ i , j = k ∑ d i , j d i , j T , f k ( x ) = C ( x ) + 2 n δ x T P k x ( k ∈ [ n ]) . (12)
For every assignment, n − 1 ∑ k f k ( x ) = δ β 2 f ^ ( x / β ) n^{-1}\sum_{k}f_{k}(x)=\delta\beta^{2}\hat{f}(x/\beta) n − 1 ∑ k f k ( x ) = δ β 2 f ^ ( x / β ) . The disjoint supports give P k 2 = 2 P k P_{k}^{2}=2P_{k} P k 2 = 2 P k , while ∑ k P k \sum_{k}P_{k} ∑ k P k is a union of path Laplacians with norm at most 4 4 4 .
We specify the parameters in Appendix B.1. Taking δ ν ≍ ( ρ ϵ ) 1 / 2 \delta\nu\asymp(\rho\epsilon)^{1/2} δ ν ≍ ( ρ ϵ ) 1/2 and β ≍ ϵ / ( δ ν ) \beta\asymp\epsilon/(\delta\nu) β ≍ ϵ / ( δ ν ) makes the average ρ \rho ρ -Hessian-Lipschitz and keeps its gradient norm above ϵ \epsilon ϵ until the chain is traversed. Taking T ≍ ρ 1 / 2 Δ ϵ − 3 / 2 T\asymp\rho^{1/2}\Delta\epsilon^{-3/2} T ≍ ρ 1/2 Δ ϵ − 3/2 bounds the initial gap by Δ \Delta Δ . Averaged smoothness permits δ = L / ( 8 n ) \delta=L/(8\sqrt{n}) δ = L / ( 8 n ) , whereas individual smoothness permits only δ = L / ( 8 n ) \delta=L/(8n) δ = L / ( 8 n ) : the former follows from 1 n ∑ k ∥ n δ P k d ∥ 2 ≤ 8 n δ 2 ∥ d ∥ 2 \frac{1}{n}\sum_{k}\lVert n\delta P_{k}d\rVert^{2}\le8n\delta^{2}\lVert d\rVert^{2} n 1 ∑ k ∥ n δ P k d ∥ 2 ≤ 8 n δ 2 ∥ d ∥ 2 , and the latter because ∥ ∇ 2 f k ∥ \lVert\nabla^{2}f_{k}\rVert ∥ ∇ 2 f k ∥ contains the term 2 n δ 2n\delta 2 n δ . The bridge-length condition ν ≤ 1 / 12 \nu\le1/12 ν ≤ 1/12 becomes ϵ ≤ 5 L 2 / ( 768 n ρ ) \epsilon\le5L^{2}/(768n\rho) ϵ ≤ 5 L 2 / ( 768 n ρ ) and ϵ ≤ 5 L 2 / ( 768 n 2 ρ ) \epsilon\le5L^{2}/(768n^{2}\rho) ϵ ≤ 5 L 2 / ( 768 n 2 ρ ) , respectively.
The coordinates are exposed in the order (23) . Since the endpoint terms are common to all components, any query can expose a bridge endpoint. An internal edge can be exposed only by querying its owner at a point or direction that is nonzero at the current frontier. Before the frontier reaches the edge, both endpoints vanish in every query. The transcript therefore gives no information about the owner, which remains conditionally uniform among n n n or n − 1 n-1 n − 1 candidates. Discovering the owner requires order n n n queries.
Reaching x ˉ T \bar{x}_{T} x ˉ T requires traversing ( T − 1 ) ( m − 1 ) (T-1)(m-1) ( T − 1 ) ( m − 1 ) internal edges. A conditional Hoeffding argument converts the discovery costs into a fixed-budget lower bound (Lemma 7). Multiplying the number of bridges, the bridge length, and the search cost gives
Ω ( n T m ) = Ω ( n ⋅ ρ 1 / 2 Δ ε − 3 / 2 ν − 1 / 2 ) = { Ω ( n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) (AS) , Ω ( n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) (IS) . (13) \Omega(nTm)=\Omega\left(n\cdot\rho^{1/2}\Delta\varepsilon^{-3/2}\nu^{-1/2}\right)=
\begin{cases}
\Omega\left(n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}\right) & \text{(AS)},\\
\Omega\left(\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}\right) & \text{(IS)}.
\end{cases} \tag*{(13)} Ω ( n T m ) = Ω ( n ⋅ ρ 1/2 Δ ε − 3/2 ν − 1/2 ) = { Ω ( n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) Ω ( n L 1/2 ρ 1/4 Δ ε − 7/4 ) (AS) , (IS) . (13)
For n = 1 n=1 n = 1 , (13) reduces to the bound of Chen et al. [7 ] . The finite-sum structure has two effects. Discovering each edge costs order n n n queries, and scaling its curvature to L / n L/\sqrt{n} L / n or L / n L/n L / n shortens the bridges by a factor of n − 1 / 4 n^{-1/4} n − 1/4 or n − 1 / 2 n^{-1/2} n − 1/2 . Under averaged smoothness, the resulting factor n ⋅ n − 1 / 4 = n 3 / 4 n\cdot n^{-1/4}=n^{3/4} n ⋅ n − 1/4 = n 3/4 matches (3) .
We formalize this argument in the following theorem and give its proof in Appendix § 10 .
Theorem 3. There are universal constants c 0 , C 0 , c 1 > 0 c_0,C_0,c_1>0 c 0 , C 0 , c 1 > 0 such that, for every n ≥ 1 n\ge1 n ≥ 1 and ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2}\ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 ,
N A S z r ( n , L , ρ , Δ ) ≥ c 1 n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 , 0 < ε ≤ c 0 L 2 n ρ , (14) \mathcal{N}^{\mathrm{zr}}_{\mathrm{AS}}(n,L,\rho,\Delta)\ge c_1 n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4},
\qquad0<\varepsilon\le\frac{c_0L^2}{n\rho}, \tag*{(14)} N AS zr ( n , L , ρ , Δ ) ≥ c 1 n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 , 0 < ε ≤ n ρ c 0 L 2 , (14) N I S z r ( n , L , ρ , Δ ) ≥ c 1 n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 , 0 < ε ≤ c 0 L 2 n 2 ρ . (15) \mathcal{N}^{\mathrm{zr}}_{\mathrm{IS}}(n,L,\rho,\Delta)\ge c_1\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4},
\qquad0<\varepsilon\le\frac{c_0L^2}{n^2\rho}. \tag*{(15)} N IS zr ( n , L , ρ , Δ ) ≥ c 1 n L 1/2 ρ 1/4 Δ ε − 7/4 , 0 < ε ≤ n 2 ρ c 0 L 2 . (15) The hard components share a common non-quadratic part, differ only in quadratic terms, and are individually ρ \rho ρ -Hessian-Lipschitz. The bounds allow adaptive component selection and exact Hessian–vector products.
Replicated Spectra for Unrestricted Algorithms
The nested chain gives a lower bound under the zero-respecting restriction. An unrestricted randomized algorithm can query points with small components on unrevealed coordinates, and an exact reply then reveals their directions. To obtain a lower bound without this restriction, we use the spectral construction of Zhang et al. [20 ] , whose hardness is governed by Krylov degree, and replicate its spectrum across components.
With the parameters of Zhang et al. [20 ] at smoothness level L ⋆ L_\star L ⋆ (Appendix § 11 .§ 1 ), the construction has N N N blocks and a diagonal matrix Λ \Lambda Λ whose inverse cannot be approximated by polynomials of degree below m m m . These parameters satisfy N m ≍ L ⋆ 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 Nm\asymp L_\star^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} N m ≍ L ⋆ 1/2 ρ 1/4 Δ ε − 7/4 in the high-accuracy range. We fix N n Nn N n public, mutually orthogonal owner subspaces, draw independent Haar rotations U s i U_{si} U s i and uniform unit vectors u s i u_{si} u s i , and assign owner i i i in block s s s the matrix A s i = U s i Λ U s i T A_{si}=U_{si}\Lambda U_{si}^{\mathsf{T}} A s i = U s i Λ U s i T and forcing vector b s i ∝ U s i u s i b_{si}\propto U_{si}u_{si} b s i ∝ U s i u s i . We set f i ( z ) = G ( z ) + n 2 ∑ s = 1 n z s i T A s i z s i f_i(z)=G(z)+\frac{n}{2}\sum_{s=1}^{n}z_{si}^{\mathsf{T}}A_{si}z_{si} f i ( z ) = G ( z ) + 2 n ∑ s = 1 n z s i T A s i z s i , where G G G is the gated chain of Zhang et al. [20 ] built from the block averages A s , b s A_s,b_s A s , b s in (29) .
The average F F F is a block-diagonal instance of Zhang et al. [20 ] . Its gap, smoothness, and Hessian-Lipschitz bounds therefore hold for every realization, and an ε \varepsilon ε -stationary point must open every gate. Since the owner Hessians have orthogonal supports, individual smoothness permits L ⋆ = L / ( 2 n ) L_\star=L/(2n) L ⋆ = L / ( 2 n ) , while averaged smoothness permits L ⋆ = L / ( 2 n ) L_\star=L/(2\sqrt{n}) L ⋆ = L / ( 2 n ) . The third derivatives of f i f_i f i and F F F coincide, so the components are individually ρ \rho ρ -Hessian-Lipschitz.
We couple the true oracle with an auxiliary oracle that discloses each block’s rotations and forcing vectors on a fixed schedule and censors couplings beyond the current block. A conditional-Haar argument confines the latent query vectors of owner ( s , i ) (s,i) ( s , i ) to a Krylov span. Its degree is bounded by the number of calls to that owner since disclosure (Lemma 8 ). A phase contains only c d e l a y n m c_{\mathrm{delay}}nm c delay nm calls, so at most c d e l a y n c_{\mathrm{delay}}n c delay n heavy owners receive m m m or more calls. Each heavy owner carries at most 2 / n 2/n 2/ n of the squared readout mass. For the light owners, the projection estimate of Zhang et al. [20 Lemma 7.2] controls the information in their low-degree Krylov spans. Every readout consequently remains below its gate threshold until the phase ends. The censored and true replies coincide, giving a lower bound of Ω ( n N m ) \Omega(nNm) Ω ( n N m ) calls (Appendix § 11 ).
Replicating the full spectrum in every owner is essential to this argument. If each eigenvalue belonged to a single component, one call per owner after disclosure of b b b would reveal that owner’s part of A − 1 b A^{-1}b A − 1 b . A phase would then cost O ( n + m ) O(n+m) O ( n + m ) calls instead of n m nm nm .
The following theorem states the resulting lower bound. We give its proof in Appendix § 11 .
Theorem 4. There are universal constants c , C 0 , c 2 > 0 c, C_0, c_2 > 0 c , C 0 , c 2 > 0 such that, if ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2} \ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 , then
N ε ( F A S ( n , L , ρ , Δ ) ) ≥ c 2 n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 , ε ≤ c L 2 / ( n ρ ) , (16) \mathcal{N}_{\varepsilon}(\mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta)) \ge c_2 n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}, \qquad\varepsilon\le cL^2/(n\rho), \tag*{(16)} N ε ( F AS ( n , L , ρ , Δ )) ≥ c 2 n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 , ε ≤ c L 2 / ( n ρ ) , (16) N ε ( F I S ( n , L , ρ , Δ ) ) ≥ c 2 n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 , ε ≤ c L 2 / ( n 2 ρ ) . (17) \mathcal{N}_{\varepsilon}(\mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta)) \ge c_2\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}, \qquad\varepsilon\le cL^2/(n^2\rho). \tag*{(17)} N ε ( F IS ( n , L , ρ , Δ )) ≥ c 2 n L 1/2 ρ 1/4 Δ ε − 7/4 , ε ≤ c L 2 / ( n 2 ρ ) . (17) The hard components are individually ρ \rho ρ -Hessian-Lipschitz, and the bounds hold for exact Hessian–vector products and arbitrary query points.
Lower Bound at Low Accuracy
For the lower bound in Theorem 5, we use the nonconvex dense-weak-hiding instance of Peng et al. [18 Appendices C.1 and C.4] without modification (Appendix § 12 .§ 1 ). The instance has T T T stages. Each stage hides a sign vector behind an encoding table with rows weakly biased toward that vector. The bias is ϱ ≍ n − 1 / 2 \varrho\asymp n^{-1/2} ϱ ≍ n − 1/2 , so recovering one stage requires order n n n distinct rows. Consecutive stages are linked by the flat gate of Peng et al. [18 Lemma A.1] , whose derivatives vanish below its threshold. The scalings of Peng et al. [18 ] give individual smoothness L L L and gradient norm at least 8 ε 8\varepsilon 8 ε until the final stage is revealed.
We verify class membership and extend the information argument to our oracle. First, the row averages equal the hidden vectors exactly. Thus, the average of the unscaled components is independent of ϱ \varrho ϱ , although the component derivatives scale as 1 / ϱ 1/\varrho 1/ ϱ . A universal bound on the third derivative of the average (Appendix § 12 .§ 2 ) gives
Lip ( ∇ 2 1 n ∑ i f i ) ≤ c H L 2 n ρ ε , c H ≤ 414. \operatorname{Lip}\left(\nabla^2 \frac{1}{n}\sum_i f_i\right) \le c_H\frac{L^2}{n\rho\varepsilon}, \qquad c_H \le414. Lip ( ∇ 2 n 1 i ∑ f i ) ≤ c H n ρε L 2 , c H ≤ 414.
Replacing L L L by L e f f = min { L , ( n ρ ε / c H ) 1 / 2 } L_{\mathrm{eff}}=\min\{L,(n\rho\varepsilon/c_H)^{1/2}\} L eff = min { L , ( n ρε / c H ) 1/2 } places the instance in F I S ( n , L , ρ , Δ ) \mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta) F IS ( n , L , ρ , Δ ) . The bound Ω ( n + n L e f f Δ ε − 2 ) \Omega(n+\sqrt{n}L_{\mathrm{eff}}\Delta\varepsilon^{-2}) Ω ( n + n L eff Δ ε − 2 ) of Peng et al. [18 Theorem 3.1] then yields Theorem 5.
Second, the information argument of Peng et al. [18 Appendix B] requires only that any reply which does not complete the current stage depend on the history and the queried rows of that stage. Every derivative of an unopened link vanishes at such a point. The argument therefore applies to replies containing derivatives of any fixed order, including full Hessians (Lemma 11 ).
Combining the lower bound with Corollary 1 gives the following complexity characterization.
Theorem 5. There are universal constants n 0 , c 3 > 0 n_0, c_3 > 0 n 0 , c 3 > 0 such that, for n ≥ n 0 n \ge n_0 n ≥ n 0 , L 2 / ( n ρ ) ≤ ε ≤ L 2 / ρ L^2/(n\rho) \le\varepsilon\le L^2/\rho L 2 / ( n ρ ) ≤ ε ≤ L 2 / ρ , and ε 2 ≤ c 3 L Δ \varepsilon^2 \le c_3L\Delta ε 2 ≤ c 3 L Δ ,
N ε ( F I S ( n , L , ρ , Δ ) ) = N ε ( F A S ( n , L , ρ , Δ ) ) = Θ ~ ( n + n L Δ ε − 2 ) . (18) \mathcal{N}_{\varepsilon}(\mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta)) = \mathcal{N}_{\varepsilon}(\mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta)) = \widetilde{\Theta}(n+\sqrt{n}L\Delta\varepsilon^{-2}). \tag*{(18)} N ε ( F IS ( n , L , ρ , Δ )) = N ε ( F AS ( n , L , ρ , Δ )) = Θ ( n + n L Δ ε − 2 ) . (18) The upper bound is attained by PathVR (Corollary 1). The lower bound holds even when each call returns the full component Hessian, and more generally equals Ω ( n + min { n L Δ ε − 2 , n ρ 1 / 2 Δ ε − 3 / 2 } ) \Omega(n+\min\{\sqrt{n}L\Delta\varepsilon^{-2}, n\rho^{1/2}\Delta\varepsilon^{-3/2}\}) Ω ( n + min { n L Δ ε − 2 , n ρ 1/2 Δ ε − 3/2 }) (Proposition 4).
For the terms proportional to Δ \Delta Δ , the FastCubic bound exceeds the PathVR bound by a factor of order ( n ρ ε ) 1 / 2 / L (n\rho\varepsilon)^{1/2}/L ( n ρε ) 1/2 / L , up to logarithmic factors.
Near-Optimal Complexity
We now combine the upper and lower bounds. Theorems 2, 3 , and 4 give the following characterization of the high-accuracy regime. The proof is in Appendix § 13 .
Theorem 6. There are universal constants c 0 , C 0 , c 1 > 0 c_0, C_0, c_1 > 0 c 0 , C 0 , c 1 > 0 such that, for every n ≥ 1 n \ge1 n ≥ 1 , 0 < ε ≤ c 0 L 2 / ( n ρ ) 0 < \varepsilon\le c_0L^2/(n\rho) 0 < ε ≤ c 0 L 2 / ( n ρ ) , and ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2} \ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 ,
N ε ( F A S ( n , L , ρ , Δ ) ) = Θ ~ ( n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) , N ε z r ( F A S ( n , L , ρ , Δ ) ) ≥ c 1 n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 . (19) \mathfrak{N}_{\varepsilon}(\mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta)) = \widetilde{\Theta}(n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}), \qquad\mathfrak{N}_{\varepsilon}^{\mathrm{zr}}(\mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta)) \ge c_1n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}. \tag*{(19)} N ε ( F AS ( n , L , ρ , Δ )) = Θ ( n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) , N ε zr ( F AS ( n , L , ρ , Δ )) ≥ c 1 n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 . (19)
The lower bounds in (19) carry no logarithmic factors.
The parameter range in Theorem 6 ensures that the quadratic bridges of § 4.1 contain at least two vertices. In the range covered by the individual-smoothness lower bound, the bounds differ by a factor of n 1 / 4 n^{1/4} n 1/4 .
Theorem 7. Under the conditions of Theorem 4, for ε ≤ c L 2 / ( n 2 ρ ) \varepsilon\le cL^2/(n^2\rho) ε ≤ c L 2 / ( n 2 ρ ) ,
c 2 n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ≤ N ε ( F I S ( n , L , ρ , Δ ) ) ≤ O ~ ( n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) . (20) c_2\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} \le\mathfrak{N}_{\varepsilon}(\mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta)) \le\widetilde{O}(n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}). \tag*{(20)} c 2 n L 1/2 ρ 1/4 Δ ε − 7/4 ≤ N ε ( F IS ( n , L , ρ , Δ )) ≤ O ( n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) . (20)
The gap in (20) is also present for linear systems with individually bounded, possibly indefinite component matrices. Katyusha X uses n + n 3 / 4 κ n+n^{3/4}\sqrt{\kappa} n + n 3/4 κ queries, while the best lower bound under individual smoothness is of order n + n κ n+\sqrt{n\kappa} n + nκ [11 , 22 ] . A solver using n + n 3 / 4 − θ κ n+n^{3/4-\theta}\sqrt{\kappa} n + n 3/4 − θ κ queries would improve the second term of (3) to n 3 / 4 − θ L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 n^{3/4-\theta}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} n 3/4 − θ L 1/2 ρ 1/4 Δ ε − 7/4 .
We also consider two related oracle models (Appendices § 13 and § 13 .§ 3 ). If each call returns the full component Hessian, cubic regularization requires only O ( 1 + ρ 1 / 2 Δ ε − 3 / 2 ) O(1+\rho^{1/2}\Delta\varepsilon^{-3/2}) O ( 1 + ρ 1/2 Δ ε − 3/2 ) full Hessians. The complexity is determined by the better of the cubic-regularization and PathVR bounds.
Proposition 2. Suppose each call may return the full matrix ∇ 2 f i ( x ) \nabla^2 f_i(x) ∇ 2 f i ( x ) . For n ≥ n 0 n \ge n_0 n ≥ n 0 and in either accuracy regime under the corresponding conditions of Theorem 6 or Theorem 5, the fixed-budget complexity over F A S \mathcal{F}_{\mathrm{AS}} F AS or F I S \mathcal{F}_{\mathrm{IS}} F IS is Θ ~ ( n + min { n L Δ ε − 2 , n ρ 1 / 2 Δ ε − 3 / 2 } ) \widetilde{\Theta}(n+\min\{\sqrt{n}L\Delta\varepsilon^{-2},\,n\rho^{1/2}\Delta\varepsilon^{-3/2}\}) Θ ( n + min { n L Δ ε − 2 , n ρ 1/2 Δ ε − 3/2 }) .
The term n ρ 1 / 2 Δ ε − 3 / 2 n\rho^{1/2}\Delta\varepsilon^{-3/2} n ρ 1/2 Δ ε − 3/2 reflects that Assumption 3 constrains only the average Hessian: the dense-weak-hiding components behind Proposition 4 have Hessian-Lipschitz constants of order n \sqrt{n} n times that of their average (Appendix § 12 .§ 1 ). On the subclass of F I S \mathcal{F}_{\mathrm{IS}} F IS whose components are individually ρ \rho ρ -Hessian-Lipschitz, Zhou and Gu [23 ] find a point with ∥ ∇ f ( x ^ ) ∥ ≤ ε \|\nabla f(\hat{x})\| \le\varepsilon ∥∇ f ( x ^ ) ∥ ≤ ε using O ~ ( n + n 3 / 4 ρ 1 / 2 Δ ε − 3 / 2 ) \widetilde{O}(n+n^{3/4}\rho^{1/2}\Delta\varepsilon^{-3/2}) O ( n + n 3/4 ρ 1/2 Δ ε − 3/2 ) full component Hessians, and Wu et al. [19 ] prove the lower bound Ω ( n + n 3 / 4 ρ 1 / 2 Δ ε − 3 / 2 ) \Omega(n+n^{3/4}\rho^{1/2}\Delta\varepsilon^{-3/2}) Ω ( n + n 3/4 ρ 1/2 Δ ε − 3/2 ) for unrestricted randomized algorithms over classes with no bound on L L L . Our high-accuracy hard instances are individually ρ \rho ρ -Hessian-Lipschitz (Theorems 3 and 4), so on this subclass the Hessian–vector complexity n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 exceeds the full-Hessian rate by the factor ( L 2 / ( ρ ε ) ) 1 / 4 ≥ 1 (L^2/(\rho\varepsilon))^{1/4} \ge1 ( L 2 / ( ρε ) ) 1/4 ≥ 1 . For a single function, the replicated spectral construction with n = 1 n=1 n = 1 extends the lower bound of Zhang et al. [20 ] to exact Hessian–vector products.
Proposition 3. For n = 1 n=1 n = 1 , ε ≤ c L 2 / ρ \varepsilon\le cL^2/\rho ε ≤ c L 2 / ρ , and ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2} \ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 , every randomized algorithm with values, gradients, and exact Hessian–vector products needs Ω ( L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) \Omega(L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}) Ω ( L 1/2 ρ 1/4 Δ ε − 7/4 ) queries, which matches FastCubic up to logarithmic factors.
Conclusion
We characterize the component-oracle complexity of finding approximate local minima of nonconvex finite sums under averaged smoothness and a Lipschitz average Hessian. At high accuracy, the minimax complexity is Θ ~ ( n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) \widetilde{\Theta}(n^{3/4}L^{1/2}\rho^{1/4}\Delta_{\varepsilon}^{-7/4}) Θ ( n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 ) , and FastCubic attains the upper bound. The nested-chain construction explains the factor n 3 / 4 n^{3/4} n 3/4 through the cost of discovering randomly owned bridge edges. At low accuracy, PathVR attains O ~ ( n + n L Δ ε − 2 ) \widetilde{O}(n+\sqrt{n}L\Delta\varepsilon^{-2}) O ( n + n L Δ ε − 2 ) , matching the dense-weak-hiding lower bound. In the range covered by the individual-smoothness lower bound, the bounds differ by a factor of n 1 / 4 n^{1/4} n 1/4 . Faster linear-system solvers that exploit individual smoothness would narrow this gap. Other open questions are to remove logarithmic factors from the upper bound, characterize the transition ε ≍ L 2 / ( n ρ ) \varepsilon\asymp L^2/(n\rho) ε ≍ L 2 / ( n ρ ) up to constants, and extend random-owner constructions to finite-sum minimax and bilevel problems with Lipschitz Hessians.
Acknowledgements
The author thanks Lesi Chen of Tsinghua University for helpful discussions of this open problem.
Codex and Claude Science were used to assist with the development of the constructions and proofs, numerical checks of algebraic identities, the review of related literature, and the preparation of this manuscript. The author is responsible for the mathematical claims, references, and final presentation.
Proofs for Section 3
Proof of Proposition 1
Proof. Write H i = ∇ 2 f i ( x ) H_i = \nabla^2 f_i(x) H i = ∇ 2 f i ( x ) , H = ∇ 2 f ( x ) H = \nabla^2 f(x) H = ∇ 2 f ( x ) , A t = 2 L I − H i t A_t = 2LI - H_{i_t} A t = 2 L I − H i t , and Σ = 2 L I − H \Sigma= 2LI - H Σ = 2 L I − H . By (5) ,
L I ⪯ Σ ⪯ 3 L I , E ( A t − Σ ) 2 ⪯ L 2 I , a λ 1 ( Σ ) 3 L ∈ [ a / 3 , a ] . LI \preceq\Sigma\preceq3LI,\qquad\mathbb{E}(A_t-\Sigma)^2 \preceq L^2I,\qquad\frac{a\lambda_1(\Sigma)}{3L} \in[a/3,a]. L I ⪯ Σ ⪯ 3 L I , E ( A t − Σ ) 2 ⪯ L 2 I , 3 L a λ 1 ( Σ ) ∈ [ a /3 , a ] .
Thus Gu et al. [10 Lemma 10] applies to the step sizes in Algorithm 1 for sufficiently large C 1 , C 2 C_1,C_2 C 1 , C 2 . Its good event has a nonzero final unnormalized product, and a zero intermediate update forces a zero final product, so a run assigned e 1 e_1 e 1 lies outside the good event; its validation is unchanged, and the success probability is unaffected. Each run produces a unit vector w r T w_r^T w r T with
( w r T ) ⊤ H w r T ≤ λ min ( H ) + δ 8 (w_r^T)^\top H w_r^T \leq\lambda_{\min}(H) + \frac{\delta}{8} ( w r T ) ⊤ H w r T ≤ λ m i n ( H ) + 8 δ
with probability at least 3 / 4 3/4 3/4 . Independence gives a successful run with probability at least 1 − 4 − R ≥ 1 − p / 2 1-4^{-R} \geq1-p/2 1 − 4 − R ≥ 1 − p /2 .
Conditional on each candidate, fresh validation samples have variance at most L 2 L^2 L 2 . Chebyshev’s inequality gives
P ( ∣ 1 m ∑ j = 1 m ( w r T ) ⊤ H i j w r T − ( w r T ) ⊤ H w r T ∣ ≥ δ 16 ) ≤ 256 L 2 m δ 2 ≤ 1 16 . \mathbb{P}\left(\left|\frac{1}{m}\sum_{j=1}^{m}(w_r^T)^\top H_{i_j}w_r^T-(w_r^T)^\top H w_r^T\right| \geq\frac{\delta}{16}\right)\leq\frac{256L^2}{m\delta^2}\leq\frac{1}{16}. P ( m 1 j = 1 ∑ m ( w r T ) ⊤ H i j w r T − ( w r T ) ⊤ H w r T ≥ 16 δ ) ≤ m δ 2 256 L 2 ≤ 16 1 .
The median and a union bound make all R R R estimates accurate to δ / 16 \delta/16 δ /16 with probability at least 1 − p / 2 1-p/2 1 − p /2 , for sufficiently large C 3 C_3 C 3 . On the intersection, if λ ^ r ∗ ≤ − 5 δ / 8 \hat{\lambda}_{r^*}\leq-5\delta/8 λ ^ r ∗ ≤ − 5 δ /8 , then
u ⊤ H u ≤ λ ^ r ∗ + δ 16 ≤ − 9 δ 16 ≤ − δ 2 . u^\top H u \leq\hat{\lambda}_{r^*}+\frac{\delta}{16}\leq-\frac{9\delta}{16}\leq-\frac{\delta}{2}. u ⊤ H u ≤ λ ^ r ∗ + 16 δ ≤ − 16 9 δ ≤ − 2 δ .
Otherwise u = 0 u=0 u = 0 , and a successful run w r T w_r^T w r T gives
λ min ( H ) ≥ ( w r T ) ⊤ H w r T − δ 8 ≥ λ ^ r − 3 δ 16 ≥ λ ^ r ∗ − 3 δ 16 > − 13 δ 16 > − δ . \lambda_{\min}(H)\geq(w_r^T)^\top H w_r^T-\frac{\delta}{8}\geq\hat{\lambda}_r-\frac{3\delta}{16}\geq\hat{\lambda}_{r^*}-\frac{3\delta}{16}>-\frac{13\delta}{16}>-\delta. λ m i n ( H ) ≥ ( w r T ) ⊤ H w r T − 8 δ ≥ λ ^ r − 16 3 δ ≥ λ ^ r ∗ − 16 3 δ > − 16 13 δ > − δ .
The cost is R T + R M m RT+RMm R T + R M m Hessian–vector products, yielding the stated bound. □
Path-Length-Based Variance Reduction
Use the setting of Theorem 1, with s t = ∥ x t + 1 − x t ∥ s^t=\|x^{t+1}-x^t\| s t = ∥ x t + 1 − x t ∥ and b t = ⌈ n s t / ℓ ⌉ b^t=\lceil ns^t/\ell\rceil b t = ⌈ n s t / ℓ ⌉ . Gradient steps, curvature steps, and refreshes refer to the normalized gradient update, the signed curvature update, and the full-gradient recomputation in Algorithm 2. A window consists of consecutive iterations between refreshes, including the initial window.
Basic Lemmas
Lemma 3 (Peng et al. [17 Theorem 2.1] ). Let { ξ k } k ≥ 1 \{\xi_k\}_{k\geq1} { ξ k } k ≥ 1 be a martingale difference sequence in a Hilbert space with respect to a filtration { F k } k ≥ 0 \{\mathcal{F}_k\}_{k\geq0} { F k } k ≥ 0 such that ∥ ξ k ∥ ≤ M \|\xi_k\|\leq M ∥ ξ k ∥ ≤ M almost surely for all k k k . Let V m = ∑ k = 1 m E [ ∥ ξ k ∥ 2 ∣ F k − 1 ] V_m=\sum_{k=1}^{m}\mathbb{E}[\|\xi_k\|^2\mid\mathcal{F}_{k-1}] V m = ∑ k = 1 m E [ ∥ ξ k ∥ 2 ∣ F k − 1 ] . Then for any a > 0 a>0 a > 0 and V > 0 V>0 V > 0 , we have
P ( ∃ m ≥ 1 : ∥ ∑ k = 1 m ξ k ∥ ≥ a and V m ≤ V ) ≤ 2 exp ( − a 2 2 ( V + a M / 3 ) ) . \mathbb{P}\left(\exists m\geq1:\left\|\sum_{k=1}^{m}\xi_k\right\|\geq a\text{ and }V_m\leq V\right)\leq2\exp\left(-\frac{a^2}{2(V+aM/3)}\right). P ( ∃ m ≥ 1 : k = 1 ∑ m ξ k ≥ a and V m ≤ V ) ≤ 2 exp ( − 2 ( V + a M /3 ) a 2 ) .
Lemma 4. Suppose Assumption 1 holds. For any x , x ′ ∈ R d x, x' \in\mathbb{R}^{d} x , x ′ ∈ R d with s = ∥ x ′ − x ∥ s = \lVert x' - x \rVert s = ∥ x ′ − x ∥ , let d i = ∇ f i ( x ′ ) − ∇ f i ( x ) d_i = \nabla f_i(x') - \nabla f_i(x) d i = ∇ f i ( x ′ ) − ∇ f i ( x ) for i ∈ [ n ] i \in[n] i ∈ [ n ] and d ˉ = ∇ f ( x ′ ) − ∇ f ( x ) \bar{d} = \nabla f(x') - \nabla f(x) d ˉ = ∇ f ( x ′ ) − ∇ f ( x ) . Then we have
(a) ∥ d ˉ ∥ ≤ L s \lVert\bar{d} \rVert\le Ls ∥ d ˉ ∥ ≤ L s and max i ∈ [ n ] ∥ d i ∥ ≤ n L s \max_{i \in[n]} \lVert d_i \rVert\le\sqrt{n}Ls max i ∈ [ n ] ∥ d i ∥ ≤ n L s ;
(b) 1 n ∑ i = 1 n ∥ d i − d ˉ ∥ 2 ≤ L 2 s 2 \frac{1}{n}\sum_{i=1}^{n}\lVert d_i-\bar{d}\rVert^2 \le L^2s^2 n 1 ∑ i = 1 n ∥ d i − d ˉ ∥ 2 ≤ L 2 s 2 ;
(c) f ( x ′ ) ≤ f ( x ) + ⟨ ∇ f ( x ) , x ′ − x ⟩ + L 2 s 2 f(x') \le f(x) + \langle\nabla f(x),x'-x\rangle+ \frac{L}{2}s^2 f ( x ′ ) ≤ f ( x ) + ⟨ ∇ f ( x ) , x ′ − x ⟩ + 2 L s 2 .
Proof. Jensen’s inequality and (4) give (a)–(b):
∥ d ˉ ∥ 2 ≤ 1 n ∑ i ∥ d i ∥ 2 ≤ L 2 s 2 , ∥ d i ∥ 2 ≤ ∑ i ′ ∥ d i ′ ∥ 2 ≤ n L 2 s 2 , \lVert\bar{d}\rVert^2 \le\frac{1}{n}\sum_i\lVert d_i\rVert^2 \le L^2s^2,\qquad\lVert d_i\rVert^2 \le\sum_{i'}\lVert d_{i'}\rVert^2 \le nL^2s^2, ∥ d ˉ ∥ 2 ≤ n 1 i ∑ ∥ d i ∥ 2 ≤ L 2 s 2 , ∥ d i ∥ 2 ≤ i ′ ∑ ∥ d i ′ ∥ 2 ≤ n L 2 s 2 ,
1 n ∑ i ∥ d i − d ˉ ∥ 2 = 1 n ∑ i ∥ d i ∥ 2 − ∥ d ˉ ∥ 2 ≤ L 2 s 2 . \frac{1}{n}\sum_i\lVert d_i-\bar{d}\rVert^2 = \frac{1}{n}\sum_i\lVert d_i\rVert^2-\lVert\bar{d}\rVert^2 \le L^2s^2. n 1 i ∑ ∥ d i − d ˉ ∥ 2 = n 1 i ∑ ∥ d i ∥ 2 − ∥ d ˉ ∥ 2 ≤ L 2 s 2 .
Part (c) follows from ∥ ∇ 2 f ∥ ≤ L \lVert\nabla^2 f\rVert\le L ∥ ∇ 2 f ∥ ≤ L in (5).
Proof of Lemma 1
Lemma 5. Under the setting of Lemma 1, fix a window and let t 0 t_0 t 0 be its first iteration, so that v t 0 = ∇ f ( x t 0 ) v^{t_0}=\nabla f(x^{t_0}) v t 0 = ∇ f ( x t 0 ) . For every iteration t t t of the window that is not a refresh and every k ∈ [ b t ] k\in[b^t] k ∈ [ b t ] , define
ξ k t = 1 b t ( d j k t − d ˉ t ) , d i t = ∇ f i ( x t + 1 ) − ∇ f i ( x t ) , d ˉ t = ∇ f ( x t + 1 ) − ∇ f ( x t ) . \xi_k^t=\frac{1}{b^t}\left(d_{j_k}^t-\bar{d}^t\right),\qquad d_i^t=\nabla f_i(x^{t+1})-\nabla f_i(x^t),\qquad\bar{d}^t=\nabla f(x^{t+1})-\nabla f(x^t). ξ k t = b t 1 ( d j k t − d ˉ t ) , d i t = ∇ f i ( x t + 1 ) − ∇ f i ( x t ) , d ˉ t = ∇ f ( x t + 1 ) − ∇ f ( x t ) . Then, ordering the increments ξ k t \xi_k^t ξ k t lexicographically in ( t , k ) (t,k) ( t , k ) , we have
(a) v t + 1 − ∇ f ( x t + 1 ) = ∑ t ′ ≤ t ∑ k = 1 b t ′ ξ k t ′ v^{t+1}-\nabla f(x^{t+1})=\sum_{t'\le t}\sum_{k=1}^{b^{t'}}\xi_k^{t'} v t + 1 − ∇ f ( x t + 1 ) = ∑ t ′ ≤ t ∑ k = 1 b t ′ ξ k t ′ for every non-refresh iteration t t t of the window;
(b) { ξ k t } \{\xi_k^t\} { ξ k t } is a martingale difference sequence with ∥ ξ k t ∥ ≤ ε / ( 8 c p ) \lVert\xi_k^t\rVert\le\varepsilon/(8\sqrt{c_p}) ∥ ξ k t ∥ ≤ ε / ( 8 c p ) almost surely;
(c) the predictable quadratic variation of the whole window is at most ε 2 / ( 256 c p ) \varepsilon^2/(256c_p) ε 2 / ( 256 c p ) .
Proof. For each non-refresh iteration, the recursive estimator update in Algorithm 2 gives
v t + 1 − ∇ f ( x t + 1 ) = v t − ∇ f ( x t ) + ∑ k = 1 b t ξ k t = ∑ t ′ = t 0 t ∑ k = 1 b t ′ ξ k t ′ , v^{t+1}-\nabla f(x^{t+1})=v^t-\nabla f(x^t)+\sum_{k=1}^{b^t}\xi_k^t=\sum_{t'=t_0}^{t}\sum_{k=1}^{b^{t'}}\xi_k^{t'}, v t + 1 − ∇ f ( x t + 1 ) = v t − ∇ f ( x t ) + k = 1 ∑ b t ξ k t = t ′ = t 0 ∑ t k = 1 ∑ b t ′ ξ k t ′ ,
since v t 0 = ∇ f ( x t 0 ) v^{t_0}=\nabla f(x^{t_0}) v t 0 = ∇ f ( x t 0 ) . Let F k t \mathcal{F}_k^t F k t be the history before sampling j k t j_k^t j k t . The points x t , x t + 1 x^t,x^{t+1} x t , x t + 1 are already fixed, and j k t j_k^t j k t is conditionally uniform and independent of earlier draws. Thus
E [ ξ k t ∣ F k t ] = 1 b t ( 1 n ∑ i d i t − d ˉ t ) = 0. \mathbb{E}[\xi_k^t\mid\mathcal{F}_k^t]=\frac{1}{b^t}\left(\frac{1}{n}\sum_i d_i^t-\bar{d}^t\right)=0. E [ ξ k t ∣ F k t ] = b t 1 ( n 1 i ∑ d i t − d ˉ t ) = 0.
Lemma 4 and b t ≥ n s t / ℓ b^t\ge ns^t/\ell b t ≥ n s t / ℓ give
∥ ξ k t ∥ ≤ ( n + 1 ) L s t b t ≤ 2 L ℓ n = ε 8 c p , E [ ∥ ξ k t ∥ 2 ∣ F k t ] ≤ L 2 ( s t ) 2 ( b t ) 2 . \lVert\xi_k^t\rVert\le\frac{(\sqrt{n}+1)Ls^t}{b^t}\le\frac{2L\ell}{\sqrt{n}}=\frac{\varepsilon}{8\sqrt{c_p}},\qquad\mathbb{E}[\lVert\xi_k^t\rVert^2\mid\mathcal{F}_k^t]\le\frac{L^2(s^t)^2}{(b^t)^2}. ∥ ξ k t ∥ ≤ b t ( n + 1 ) L s t ≤ n 2 L ℓ = 8 c p ε , E [∥ ξ k t ∥ 2 ∣ F k t ] ≤ ( b t ) 2 L 2 ( s t ) 2 .
The refresh rule ensures ∑ t s t ≤ ℓ \sum_t s^t \le\ell ∑ t s t ≤ ℓ over the non-refresh iterations of a window; hence
∑ t ∑ k = 1 b t E [ ∥ ξ k t ∥ 2 ∣ F k t ] ≤ ∑ t L 2 ( s t ) 2 b t ≤ L 2 ℓ n ∑ t s t ≤ L 2 ℓ 2 n = ε 2 256 c p . \sum_t\sum_{k=1}^{b^t}\mathbb{E}[\|\xi_k^t\|^2\mid\mathcal{F}_k^t]\le\sum_t\frac{L^2(s^t)^2}{b^t}\le\frac{L^2\ell}{n}\sum_t s^t\le\frac{L^2\ell^2}{n}=\frac{\varepsilon^2}{256c_p}. t ∑ k = 1 ∑ b t E [ ∥ ξ k t ∥ 2 ∣ F k t ] ≤ t ∑ b t L 2 ( s t ) 2 ≤ n L 2 ℓ t ∑ s t ≤ n L 2 ℓ 2 = 256 c p ε 2 .
Proof of Lemma 1. Condition on a window’s starting history and apply Lemmas 3 and 5 with
a = ε 16 , M = ε 8 c p , V = ε 2 256 c p , q = log 4 K p . a=\frac{\varepsilon}{16},\qquad M=\frac{\varepsilon}{8\sqrt{c_p}},\qquad V=\frac{\varepsilon^2}{256c_p},\qquad q=\log\frac{4K}{p}. a = 16 ε , M = 8 c p ε , V = 256 c p ε 2 , q = log p 4 K .
Since c p = 64 q 2 c_p=64q^2 c p = 64 q 2 and q ≥ log 8 > 1 q\ge\log8>1 q ≥ log 8 > 1 ,
a 2 2 ( V + a M / 3 ) = 1 2 / c p + 4 / ( 3 c p ) = 192 q 2 32 q + 6 ≥ 5 q . \frac{a^2}{2(V+aM/3)}=\frac{1}{2/c_p+4/(3\sqrt{c_p})}=\frac{192q^2}{32q+6}\ge5q. 2 ( V + a M /3 ) a 2 = 2/ c p + 4/ ( 3 c p ) 1 = 32 q + 6 192 q 2 ≥ 5 q .
The probability of an error greater than ε / 16 \varepsilon/16 ε /16 anywhere in the window is therefore at most
2 e − 5 q = 2 ( p 4 K ) 5 ≤ p 2 K . 2e^{-5q}=2\left(\frac{p}{4K}\right)^5\le\frac{p}{2K}. 2 e − 5 q = 2 ( 4 K p ) 5 ≤ 2 K p .
The estimator is exact at initialization and refreshes. A union bound over at most K K K windows proves the claim.
Proof of Theorem 1
Let E \mathcal{E} E be the event that every estimator error is at most ε / 16 \varepsilon/16 ε /16 and every call to CurvSearch is correct. Lemma 1 and a union bound over at most K K K searches of failure probability p / ( 2 K ) p/(2K) p / ( 2 K ) give P ( E ) ≥ 1 − p \mathbb{P}(\mathcal{E})\ge1-p P ( E ) ≥ 1 − p .
Lemma 6. Under the setting of Theorem 1, the following statements hold on the event E \mathcal{E} E :
(a) if iteration t t t is a gradient step, then f ( x t + 1 ) ≤ f ( x t ) − 27 ε 2 32 L f(x^{t+1})\le f(x^t)-\frac{27\varepsilon^2}{32L} f ( x t + 1 ) ≤ f ( x t ) − 32 L 27 ε 2 ;
(b) if iteration t t t is a curvature step, then f ( x t + 1 ) ≤ f ( x t ) − ε 3 / 2 48 ρ 1 / 2 f(x^{t+1})\le f(x^t)-\frac{\varepsilon^{3/2}}{48\rho^{1/2}} f ( x t + 1 ) ≤ f ( x t ) − 48 ρ 1/2 ε 3/2 ;
(c) if the algorithm returns x t x^t x t after the curvature search returns zero, then ∥ ∇ f ( x t ) ∥ ≤ 33 16 ε \|\nabla f(x^t)\|\le\frac{33}{16}\varepsilon ∥∇ f ( x t ) ∥ ≤ 16 33 ε and λ min ( ∇ 2 f ( x t ) ) ≥ − ( ρ ε ) 1 / 2 \lambda_{\min}(\nabla^2f(x^t))\ge-(\rho\varepsilon)^{1/2} λ m i n ( ∇ 2 f ( x t )) ≥ − ( ρε ) 1/2 .
Proof. For a gradient step, Lemma 4(c) gives
⟨ ∇ f ( x t ) , v t ∥ v t ∥ ⟩ ≥ ∥ v t ∥ − ∥ v t − ∇ f ( x t ) ∥ ≥ 2 ε − ε 16 = 31 ε 16 , \left\langle\nabla f(x^t),\frac{v^t}{\|v^t\|}\right\rangle\ge\|v^t\|-\|v^t-\nabla f(x^t)\|\ge2\varepsilon-\frac{\varepsilon}{16}=\frac{31\varepsilon}{16}, ⟨ ∇ f ( x t ) , ∥ v t ∥ v t ⟩ ≥ ∥ v t ∥ − ∥ v t − ∇ f ( x t ) ∥ ≥ 2 ε − 16 ε = 16 31 ε ,
f ( x t + 1 ) − f ( x t ) ≤ − η 31 ε 16 + L η 2 2 = − 27 ε 2 32 L . f(x^{t+1})-f(x^t)\le-\eta\frac{31\varepsilon}{16}+\frac{L\eta^2}{2}=-\frac{27\varepsilon^2}{32L}. f ( x t + 1 ) − f ( x t ) ≤ − η 16 31 ε + 2 L η 2 = − 32 L 27 ε 2 .
For a curvature step, ( u t ) ⊤ ∇ 2 f ( x t ) u t ≤ − δ / 2 (u^t)^\top\nabla^2f(x^t)u^t\le-\delta/2 ( u t ) ⊤ ∇ 2 f ( x t ) u t ≤ − δ /2 and the sign rule yields
σ t ⟨ ∇ f ( x t ) , u t ⟩ ≤ − ∣ ⟨ v t , u t ⟩ ∣ + ∥ ∇ f ( x t ) − v t ∥ ≤ ε 16 . \sigma^t\langle\nabla f(x^t),u^t\rangle\le-|\langle v^t,u^t\rangle|+\|\nabla f(x^t)-v^t\|\le\frac{\varepsilon}{16}. σ t ⟨ ∇ f ( x t ) , u t ⟩ ≤ − ∣ ⟨ v t , u t ⟩ ∣ + ∥∇ f ( x t ) − v t ∥ ≤ 16 ε .
Taylor’s bound from Assumption 3, with r = δ / ρ r = \delta/\rho r = δ / ρ and ε = δ 2 / ρ \varepsilon= \delta^2/\rho ε = δ 2 / ρ , gives
f ( x t + 1 ) − f ( x t ) ≤ r ε 16 − r 2 δ 4 + ρ r 3 6 = δ 3 ρ 2 ( 1 16 − 1 4 + 1 6 ) = − ε 3 / 2 48 ρ 1 / 2 . f(x^{t+1}) - f(x^t) \le\frac{r\varepsilon}{16} - \frac{r^2\delta}{4} + \frac{\rho r^3}{6} = \frac{\delta^3}{\rho^2}\left(\frac{1}{16} - \frac{1}{4} + \frac{1}{6}\right) = -\frac{\varepsilon^{3/2}}{48\rho^{1/2}}. f ( x t + 1 ) − f ( x t ) ≤ 16 r ε − 4 r 2 δ + 6 ρ r 3 = ρ 2 δ 3 ( 16 1 − 4 1 + 6 1 ) = − 48 ρ 1/2 ε 3/2 .
At a return after the curvature search returns zero,
∥ ∇ f ( x t ) ∥ ≤ ∥ v t ∥ + ε 16 ≤ 33 ε 16 , λ min ( ∇ 2 f ( x t ) ) ≥ − δ = − ( ρ ε ) 1 / 2 . \lVert\nabla f(x^t)\rVert\le\lVert v^t\rVert+ \frac{\varepsilon}{16} \le\frac{33\varepsilon}{16}, \qquad\lambda_{\min}(\nabla^2 f(x^t)) \ge-\delta= -(\rho\varepsilon)^{1/2}. ∥ ∇ f ( x t )∥ ≤ ∥ v t ∥ + 16 ε ≤ 16 33 ε , λ m i n ( ∇ 2 f ( x t )) ≥ − δ = − ( ρε ) 1/2 .
Proof of Theorem 1. On E \mathcal{E} E , temporarily ignoring the query cap, Lemma 6 and the gap bound give
N g ≤ 32 L Δ 27 ε 2 , N c ≤ 48 ρ 1 / 2 Δ ε − 3 / 2 , N g + N c + 1 ≤ K . N_g \le\frac{32L\Delta}{27\varepsilon^2}, \qquad N_c \le48\rho^{1/2}\Delta\varepsilon^{-3/2}, \qquad N_g + N_c + 1 \le K. N g ≤ 27 ε 2 32 L Δ , N c ≤ 48 ρ 1/2 Δ ε − 3/2 , N g + N c + 1 ≤ K .
Thus the algorithm returns after the curvature search returns zero with the required guarantees. Both types of step decrease the objective by at least ε s t / 48 \varepsilon s^t/48 ε s t /48 , so its path length satisfies
P : = ∑ t s t ≤ 48 ε ∑ t ( f ( x t ) − f ( x t + 1 ) ) ≤ 48 Δ ε . P := \sum_t s^t \le\frac{48}{\varepsilon}\sum_t\left(f(x^t)-f(x^{t+1})\right) \le\frac{48\Delta}{\varepsilon}. P := t ∑ s t ≤ ε 48 t ∑ ( f ( x t ) − f ( x t + 1 ) ) ≤ ε 48Δ .
and consequently
n P ℓ ≤ 48 Δ ε ⋅ 16 c p L n ε = 768 c p n L Δ ε − 2 . (21) \frac{nP}{\ell} \le\frac{48\Delta}{\varepsilon}\cdot\frac{16\sqrt{c_p}L\sqrt{n}}{\varepsilon} = 768\sqrt{c_p n}L\Delta\varepsilon^{-2}. \tag*{(21)} ℓ n P ≤ ε 48Δ ⋅ ε 16 c p L n = 768 c p n L Δ ε − 2 . (21)
Non-refresh iterations cost 2 b t ≤ 2 + 2 n s t / ℓ 2b^t \le2 + 2ns^t/\ell 2 b t ≤ 2 + 2 n s t / ℓ calls each, totaling at most 2 K + 2 n P / ℓ 2K + 2nP/\ell 2 K + 2 n P / ℓ . Initialization costs n n n . Refreshes with s t > ℓ / 2 s^t > \ell/2 s t > ℓ /2 cost at most 2 n P / ℓ 2nP/\ell 2 n P / ℓ in total. Every other refresh closes a window with W t > ℓ / 2 W^t > \ell/2 W t > ℓ /2 ; at most 2 P / ℓ 2P/\ell 2 P / ℓ such windows cost another 2 n P / ℓ 2nP/\ell 2 n P / ℓ .
There are at most 1 + N c 1 + N_c 1 + N c curvature searches, each costing Q n c = O ~ ( L 2 / ( ρ ε ) ) Q_{\mathrm{nc}} = \widetilde{O}(L^2/(\rho\varepsilon)) Q nc = O ( L 2 / ( ρε )) calls. By (21) , the total is at most
n + 2 K + 6 n P ℓ + ( 1 + 48 ρ 1 / 2 Δ ε − 3 / 2 ) Q n c ≤ n + 2 K + 4608 c p n L Δ ε − 2 + ( 1 + 48 ρ 1 / 2 Δ ε − 3 / 2 ) Q n c . \begin{aligned}
n + 2K + \frac{6nP}{\ell} + (1 + 48\rho^{1/2}\Delta\varepsilon^{-3/2})Q_{\mathrm{nc}} \\
&\le n + 2K + 4608\sqrt{c_p n}L\Delta\varepsilon^{-2} + (1 + 48\rho^{1/2}\Delta\varepsilon^{-3/2})Q_{\mathrm{nc}}.
\end{aligned} n + 2 K + ℓ 6 n P + ( 1 + 48 ρ 1/2 Δ ε − 3/2 ) Q nc ≤ n + 2 K + 4608 c p n L Δ ε − 2 + ( 1 + 48 ρ 1/2 Δ ε − 3/2 ) Q nc .
Since ε ≤ L 2 / ρ \varepsilon\le L^2/\rho ε ≤ L 2 / ρ ,
ρ 1 / 2 Δ ε − 3 / 2 ≤ L Δ ε − 2 , K ≤ 2 + 99 L Δ ε − 2 ≤ 2 + 99 c p n L Δ ε − 2 . \rho^{1/2}\Delta\varepsilon^{-3/2} \le L\Delta\varepsilon^{-2}, \qquad K \le2 + 99L\Delta\varepsilon^{-2} \le2 + 99\sqrt{c_p n}L\Delta\varepsilon^{-2}. ρ 1/2 Δ ε − 3/2 ≤ L Δ ε − 2 , K ≤ 2 + 99 L Δ ε − 2 ≤ 2 + 99 c p n L Δ ε − 2 .
A sufficiently large C C C in (9) therefore makes the total at most
B = O ~ ( n + n L Δ ε − 2 + L 2 ρ ε + L 2 ρ − 1 / 2 Δ ε − 5 / 2 ) . B = \widetilde{O}\left(n + \sqrt{n}L\Delta\varepsilon^{-2} + \frac{L^2}{\rho\varepsilon} + L^2\rho^{-1/2}\Delta\varepsilon^{-5/2}\right). B = O ( n + n L Δ ε − 2 + ρε L 2 + L 2 ρ − 1/2 Δ ε − 5/2 ) .
Thus the cap is not reached on E \mathcal{E} E ; outside E \mathcal{E} E , it enforces the same fixed budget.
Proof of Corollary 1
Proof. Set ε = 16 ε o u t / 33 \varepsilon= 16\varepsilon_{\mathrm{out}}/33 ε = 16 ε out /33 . Theorem 1 gives, with probability at least 1 − p 1-p 1 − p ,
∥ ∇ f ( x ^ ) ∥ ≤ 33 ε 16 = ε o u t , λ min ( ∇ 2 f ( x ^ ) ) ≥ − ( ρ ε ) 1 / 2 ≥ − ( ρ ε o u t ) 1 / 2 . \lVert\nabla f(\hat{x})\rVert\le\frac{33\varepsilon}{16} = \varepsilon_{\mathrm{out}}, \qquad\lambda_{\min}(\nabla^2 f(\hat{x})) \ge-(\rho\varepsilon)^{1/2} \ge-(\rho\varepsilon_{\mathrm{out}})^{1/2}. ∥ ∇ f ( x ^ )∥ ≤ 16 33 ε = ε out , λ m i n ( ∇ 2 f ( x ^ )) ≥ − ( ρε ) 1/2 ≥ − ( ρ ε out ) 1/2 .
Since ε o u t ≥ L 2 / ( n ρ ) \varepsilon_{\mathrm{out}} \ge L^2/(n\rho) ε out ≥ L 2 / ( n ρ ) ,
L 2 ρ ε ≤ 33 n 16 , L 2 ρ − 1 / 2 Δ ε − 5 / 2 = ( L 2 ρ ε ) 1 / 2 L Δ ε − 2 ≤ ( 33 16 ) 1 / 2 n L Δ ε − 2 . \frac{L^2}{\rho\varepsilon} \le\frac{33n}{16}, \qquad L^2\rho^{-1/2}\Delta\varepsilon^{-5/2} = \left(\frac{L^2}{\rho\varepsilon}\right)^{1/2}L\Delta\varepsilon^{-2} \le\left(\frac{33}{16}\right)^{1/2}\sqrt{n}L\Delta\varepsilon^{-2}. ρε L 2 ≤ 16 33 n , L 2 ρ − 1/2 Δ ε − 5/2 = ( ρε L 2 ) 1/2 L Δ ε − 2 ≤ ( 16 33 ) 1/2 n L Δ ε − 2 .
Substitution into Theorem 1 gives the budget O ~ ( n + n L Δ ε o u t − 2 ) \widetilde{O}(n+\sqrt{n}L\Delta\varepsilon_{\mathrm{out}}^{-2}) O ( n + n L Δ ε out − 2 ) .
Proof of Lemma 2 and Theorem 2
Proof of Lemma 2. Apply Katyusha X to
q ( z ) = 1 2 z T A z − b T z , q i ( z ) = 1 2 z T ( H i + a I ) z − b T z . q(z)=\frac{1}{2}z^{\mathsf{T}}Az-b^{\mathsf{T}}z,\qquad q_i(z)=\frac{1}{2}z^{\mathsf{T}}(H_i+aI)z-b^{\mathsf{T}}z. q ( z ) = 2 1 z T A z − b T z , q i ( z ) = 2 1 z T ( H i + a I ) z − b T z .
The snapshot estimator is unbiased and, by (5) ,
E i ∥ ( H i − H ) ( z − z 0 ) ∥ 2 ≤ L 2 ∥ z − z 0 ∥ 2 . \mathbb{E}_i\left\|(H_i-H)(z-z_0)\right\|^2\le L^2\left\|z-z_0\right\|^2. E i ∥ ( H i − H ) ( z − z 0 ) ∥ 2 ≤ L 2 ∥ z − z 0 ∥ 2 .
This verifies Lemma 3.3 of the full version of Allen-Zhu [2 ] ; its acceleration argument uses convexity and smoothness only of the average quadratic. Set
S = L + ∣ a ∣ , m = max { n , 2 } , h = min { 1 2 S , 1 2 L m } . S=L+|a|,\qquad m=\max\{n,2\},\qquad h=\min\left\{\frac{1}{2S},\frac{1}{2L\sqrt{m}}\right\}. S = L + ∣ a ∣ , m = max { n , 2 } , h = min { 2 S 1 , 2 L m 1 } .
By Lemma 4.1 and Theorem 4.3 of the full version of Allen-Zhu [2 ] , for z ⋆ = A − 1 b z_\star=A^{-1}b z ⋆ = A − 1 b and initialization at zero,
τ − 1 = O ( 1 + n − 1 / 4 κ 1 / 2 ) , q ( 0 ) − q ( z ⋆ ) ≤ ∥ b ∥ 2 2 μ , \tau^{-1}=O(1+n^{-1/4}\kappa^{1/2}),\qquad q(0)-q(z_\star)\le\frac{\|b\|^2}{2\mu}, τ − 1 = O ( 1 + n − 1/4 κ 1/2 ) , q ( 0 ) − q ( z ⋆ ) ≤ 2 μ ∥ b ∥ 2 ,
E [ q ( z K ) − q ( z ⋆ ) ] ≤ 2 ( 1 + τ ) − K [ q ( 0 ) − q ( z ⋆ ) ] . \mathbb{E}[q(z_K)-q(z_\star)]\le2(1+\tau)^{-K}[q(0)-q(z_\star)]. E [ q ( z K ) − q ( z ⋆ )] ≤ 2 ( 1 + τ ) − K [ q ( 0 ) − q ( z ⋆ )] .
Return zero if b = 0 b=0 b = 0 or μ η ≥ 1 \mu\eta\ge1 μ η ≥ 1 . Otherwise take
K = ⌈ log ( 4 / ( p μ 2 η 2 ) ) log ( 1 + τ ) ⌉ . K=\left\lceil\frac{\log(4/(p\mu^2\eta^2))}{\log(1+\tau)}\right\rceil. K = ⌈ log ( 1 + τ ) log ( 4/ ( p μ 2 η 2 )) ⌉ .
Strong convexity and Markov’s inequality give
P ( ∥ z K − z ⋆ ∥ > η ∥ b ∥ ) ≤ 2 E [ q ( z K ) − q ( z ⋆ ) ] μ η 2 ∥ b ∥ 2 ≤ p 2 . \mathbb{P}(\|z_K-z_\star\|>\eta\|b\|)\le\frac{2\mathbb{E}[q(z_K)-q(z_\star)]}{\mu\eta^2\|b\|^2}\le\frac{p}{2}. P ( ∥ z K − z ⋆ ∥ > η ∥ b ∥ ) ≤ μ η 2 ∥ b ∥ 2 2 E [ q ( z K ) − q ( z ⋆ )] ≤ 2 p .
Abort when a geometric epoch exceeds ℓ = ⌈ m log ( 2 K / p ) ⌉ \ell=\lceil m\log(2K/p)\rceil ℓ = ⌈ m log ( 2 K / p )⌉ updates. The geometric-tail bound and a union bound give abort probability at most p / 2 p/2 p /2 . Coupling to the ideal execution therefore gives success probability at least 1 − p 1-p 1 − p within
K ( n + 2 ℓ ) = O ~ ( n + n 3 / 4 κ 1 / 2 ) K(n+2\ell)=\widetilde{O}(n+n^{3/4}\kappa^{1/2}) K ( n + 2 ℓ ) = O ( n + n 3/4 κ 1/2 )
queries.
Proof of Theorem 2. The shifts in FastCubicMin have averaged condition number O ( L ( ρ ε ) − 1 / 2 ) O(L(\rho\varepsilon)^{-1/2}) O ( L ( ρε ) − 1/2 ) [1 Appendix G] , so Lemma 2 applies to its inverse–vector products. For the bottom eigenvector, apply AppxPCA [3 Theorem 3.1] with multiplicative and leakage tolerances ξ / ( 8 L ) \xi/(8L) ξ / ( 8 L ) , where
ξ = ( ρ ε ) 1 / 2 300 , P = 3 L I − H 4 L , I 2 ⪯ P ⪯ I . (22) \xi=\frac{(\rho\varepsilon)^{1/2}}{300},\qquad P=\frac{3LI-H}{4L},\qquad\frac{I}{2}\preceq P\preceq I. \tag*{(22)} ξ = 300 ( ρε ) 1/2 , P = 4 L 3 L I − H , 2 I ⪯ P ⪯ I . (22)
Its shifted inverses satisfy
σ I − P = H + ( 4 L σ − 3 L ) I 4 L , λ min ( H + ( 4 L σ − 3 L ) I ) ≥ ξ 48 , \sigma I-P=\frac{H+(4L\sigma-3L)I}{4L},\qquad\lambda_{\min}\left(H+(4L\sigma-3L)I\right)\ge\frac{\xi}{48}, σ I − P = 4 L H + ( 4 L σ − 3 L ) I , λ m i n ( H + ( 4 L σ − 3 L ) I ) ≥ 48 ξ ,
∣ 4 L σ − 3 L ∣ ≤ 3 L , λ min ( σ I − P ) ≥ ξ 192 L . \left|4L\sigma-3L\right|\le3L,\qquad\lambda_{\min}(\sigma I-P)\ge\frac{\xi}{192L}. ∣ 4 L σ − 3 L ∣ ≤ 3 L , λ m i n ( σ I − P ) ≥ 192 L ξ .
Thus Lemma 2 applies without positive semidefinite component matrices. The outer loop uses only the average Hessian, its Lipschitz constant, and the prescribed inverse accuracies [1 Sections 3–7] . It solves
O ( 1 + ρ 1 / 2 Δ ε − 3 / 2 ) O\left(1+\rho^{1/2}\Delta\varepsilon^{-3/2}\right) O ( 1 + ρ 1/2 Δ ε − 3/2 )
cubic subproblems,
O ( n + n 3 / 4 L 1 / 2 ρ − 1 / 4 ε − 1 / 4 ) O\left(n+n^{3/4}L^{1/2}\rho^{-1/4}\varepsilon^{-1/4}\right) O ( n + n 3/4 L 1/2 ρ − 1/4 ε − 1/4 )
queries per subproblem.
Cap the outer steps at a sufficiently large universal multiple of this bound, distribute the failure probability across all subroutine calls, and abort before exceeding the total-query cap. Simultaneous subroutine success guarantees termination within both caps. Along successful descent histories, ∥ ∇ f ( x t ) ∥ ≤ 2 L Δ \lVert\nabla f(x_t)\rVert\le\sqrt{2L\Delta} ∥ ∇ f ( x t )∥ ≤ 2 L Δ controls the auxiliary logarithms. Multiplying the two bounds proves (10) . □
Proof of Theorem 3
Parameters
Use the instance (11)–(12) with coordinate order
x ˉ 1 , x 1 ( 1 ) , … , x m ( 1 ) , x ˉ 2 , … , x ˉ T , x 1 ( T ) , … , x m ( T ) , x ˉ T + 1 . (23) \bar{x}_1,x_1^{(1)},\ldots,x_m^{(1)},\bar{x}_2,\ldots,\bar{x}_T,x_1^{(T)},\ldots,x_m^{(T)},\bar{x}_{T+1}. \tag*{(23)} x ˉ 1 , x 1 ( 1 ) , … , x m ( 1 ) , x ˉ 2 , … , x ˉ T , x 1 ( T ) , … , x m ( T ) , x ˉ T + 1 . (23)
and parameters
δ ν = ( ρ ε 60 ) 1 / 2 , β = 8 ε δ ν , T = ⌊ Δ δ ν 1280 ε 2 ⌋ , δ = { L / ( 8 n ) (AS) , L / ( 8 n ) (IS) . (24) \delta_\nu=\left(\frac{\rho\varepsilon}{60}\right)^{1/2},\qquad\beta=\frac{8\varepsilon}{\delta_\nu},\qquad T=\left\lfloor\frac{\Delta\delta_\nu}{1280\varepsilon^2}\right\rfloor,\qquad\delta=\begin{cases}L/(8\sqrt{n})&\text{(AS)},\\L/(8n)&\text{(IS)}.\end{cases} \tag*{(24)} δ ν = ( 60 ρε ) 1/2 , β = δ ν 8 ε , T = ⌊ 1280 ε 2 Δ δ ν ⌋ , δ = { L / ( 8 n ) L / ( 8 n ) (AS) , (IS) . (24)
Take d = T + 1 + T m d=T+1+Tm d = T + 1 + T m and
c 0 = 1 138240 , C 0 = 12800 60 , c 1 = 27 320 ⋅ 0.6 1280 ⋅ 60 1 / 4 24 ≈ 2.9 × 10 − 6 . c_0=\frac{1}{138240},\qquad C_0=12800\sqrt{60},\qquad c_1=\frac{27}{320}\cdot\frac{0.6}{1280\cdot60^{1/4}\sqrt{24}}\approx2.9\times10^{-6}. c 0 = 138240 1 , C 0 = 12800 60 , c 1 = 320 27 ⋅ 1280 ⋅ 6 0 1/4 24 0.6 ≈ 2.9 × 1 0 − 6 .
Chain certificates
For the nonconvex chain of Carmon et al. [6 ] , write
f ^ n c ( x ˉ ) = 1 2 ( 1 − x ˉ 1 ) 2 + 1 2 ∑ i = 1 T ( x ˉ i − x ˉ i + 1 ) 2 + ∑ i = 1 T Υ ( x ˉ i ) . \hat{f}_{\mathrm{nc}}(\bar{x})=\frac{1}{2}(1-\bar{x}_1)^2+\frac{1}{2}\sum_{i=1}^{T}(\bar{x}_i-\bar{x}_{i+1})^2+\sum_{i=1}^{T}\Upsilon(\bar{x}_i). f ^ nc ( x ˉ ) = 2 1 ( 1 − x ˉ 1 ) 2 + 2 1 i = 1 ∑ T ( x ˉ i − x ˉ i + 1 ) 2 + i = 1 ∑ T Υ ( x ˉ i ) .
We use the following facts:
[7 Lemma 3.4] . If ν = θ 2 / ( 3 m − 1 ) \nu=\theta^2/(3m-1) ν = θ 2 / ( 3 m − 1 ) , then
min y Q ^ m ( a , y , b ) = ν ( a − b ) 2 , F ( x ˉ ) : = min x ( 1 ) , … , x ( T ) f ^ ( x ) = ν f ^ n c ( x ˉ ) . \min_y\widehat{Q}_m(a,y,b)=\nu(a-b)^2,\qquad F(\bar{x}):=\min_{x^{(1)},\ldots,x^{(T)}}\widehat{f}(x)=\nu\hat{f}_{\mathrm{nc}}(\bar{x}). y min Q m ( a , y , b ) = ν ( a − b ) 2 , F ( x ˉ ) := x ( 1 ) , … , x ( T ) min f ( x ) = ν f ^ nc ( x ˉ ) .
[7 Lemma 3.5] . If θ m ≤ 1 \theta\sqrt{m}\le1 θ m ≤ 1 , then ∥ ∇ f ^ ( x ) ∥ ≥ ∥ ∇ F ( x ˉ ) ∥ / 2 \lVert\nabla\hat{f}(x)\rVert\ge\lVert\nabla F(\bar{x})\rVert/2 ∥ ∇ f ^ ( x )∥ ≥ ∥ ∇ F ( x ˉ )∥ /2 .
[6 Lemmas 2 and 3] , restated in Chen et al. [7 Lemma 3.2] .
Υ ′ ( 0 ) = Υ ′ ( 1 ) = 0 , Υ ≥ Υ ( 1 ) = 0 , Υ ( 0 ) ≤ 10 , sup ∣ Υ ′ ′ ∣ ≤ 360 , \Upsilon'(0)=\Upsilon'(1)=0,\qquad\Upsilon\geq\Upsilon(1)=0,\qquad\Upsilon(0)\leq10,\qquad\sup|\Upsilon''|\leq360, Υ ′ ( 0 ) = Υ ′ ( 1 ) = 0 , Υ ≥ Υ ( 1 ) = 0 , Υ ( 0 ) ≤ 10 , sup ∣ Υ ′′ ∣ ≤ 360 ,
sup ∣ Υ ′ ′ ′ ∣ ≤ 480 , x ˉ T = x ˉ T + 1 = 0 ⟹ ∥ ∇ f ^ n c ( x ˉ ) ∥ > 1 4 . \sup|\Upsilon'''|\leq480,\qquad\bar{x}_T=\bar{x}_{T+1}=0\quad\Longrightarrow\quad\lVert\nabla\hat{f}_{\mathrm{nc}}(\bar{x})\rVert>\frac{1}{4}. sup ∣ Υ ′′′ ∣ ≤ 480 , x ˉ T = x ˉ T + 1 = 0 ⟹ ∥ ∇ f ^ nc ( x ˉ )∥ > 4 1 .
Direct differentiation gives
Υ ′ ′ ( t ) = 120 t 4 + 3 t 2 − 2 t ( 1 + t 2 ) 2 , Υ ′ ′ ′ ( t ) = 240 − t 3 + 3 t 2 + 3 t − 1 ( 1 + t 2 ) 3 . \Upsilon''(t)=120\frac{t^4+3t^2-2t}{(1+t^2)^2},\qquad\Upsilon'''(t)=240\frac{-t^3+3t^2+3t-1}{(1+t^2)^3}. Υ ′′ ( t ) = 120 ( 1 + t 2 ) 2 t 4 + 3 t 2 − 2 t , Υ ′′′ ( t ) = 240 ( 1 + t 2 ) 3 − t 3 + 3 t 2 + 3 t − 1 .
The bounds follow from
t 4 ≤ ( 1 + t 2 ) 2 , 3 t 2 ≤ 3 4 ( 1 + t 2 ) 2 , 2 ∣ t ∣ ≤ 1 + t 2 , t^4\leq(1+t^2)^2,\qquad3t^2\leq\frac{3}{4}(1+t^2)^2,\qquad2|t|\leq1+t^2, t 4 ≤ ( 1 + t 2 ) 2 , 3 t 2 ≤ 4 3 ( 1 + t 2 ) 2 , 2∣ t ∣ ≤ 1 + t 2 ,
∣ − t 3 + 3 t 2 + 3 t − 1 ∣ = ∣ Im ( t + i ) 3 − Re ( t + i ) 3 ∣ ≤ 2 ( 1 + t 2 ) 3 / 2 , \left|-t^3+3t^2+3t-1\right|=\left|\operatorname{Im}(t+\mathrm{i})^3-\operatorname{Re}(t+\mathrm{i})^3\right|\leq\sqrt{2}(1+t^2)^{3/2}, − t 3 + 3 t 2 + 3 t − 1 = Im ( t + i ) 3 − Re ( t + i ) 3 ≤ 2 ( 1 + t 2 ) 3/2 ,
Υ ′ ′ ( 0 ) = 0 , Υ ( 0 ) = 120 ∫ 0 1 t 2 ( 1 − t ) 1 + t 2 d t ≤ 120 ∫ 0 1 t 2 ( 1 − t ) d t = 10. \Upsilon''(0)=0,\qquad\Upsilon(0)=120\int_0^1\frac{t^2(1-t)}{1+t^2}\,\mathrm{d}t\leq120\int_0^1t^2(1-t)\,\mathrm{d}t=10. Υ ′′ ( 0 ) = 0 , Υ ( 0 ) = 120 ∫ 0 1 1 + t 2 t 2 ( 1 − t ) d t ≤ 120 ∫ 0 1 t 2 ( 1 − t ) d t = 10.
For the gradient transfer, let H m = ∇ y 2 ( Q ^ m / 2 ) H_m=\nabla_y^2(\hat{Q}_m/2) H m = ∇ y 2 ( Q ^ m /2 ) and let y ∗ ( x ˉ ) y^*(\bar{x}) y ∗ ( x ˉ ) minimize the bridge terms. The two endpoint inverse columns have equal norms, with
( H m − 1 e 1 ) j = m ( 2 m − j ) 3 m − 1 , ∥ H m − 1 e 1 ∥ ≤ 2 3 m 3 / 2 , ∇ y f ^ = H m ( y − y ∗ ) . (H_m^{-1}e_1)_j=\frac{m(2m-j)}{3m-1},\qquad\lVert H_m^{-1}e_1\rVert\leq\frac{2}{3}m^{3/2},\qquad\nabla_y\hat{f}=H_m(y-y^*). ( H m − 1 e 1 ) j = 3 m − 1 m ( 2 m − j ) , ∥ H m − 1 e 1 ∥ ≤ 3 2 m 3/2 , ∇ y f ^ = H m ( y − y ∗ ) .
Each outer coordinate meets at most two endpoints. Hence, for θ m ≤ 1 \theta\sqrt{m}\leq1 θ m ≤ 1 ,
∥ ∇ x ˉ f ^ − ∇ F ∥ ≤ 4 3 θ m ∥ ∇ y f ^ ∥ , ∥ ∇ F ∥ ≤ ∥ ∇ x ˉ f ^ ∥ + 4 3 ∥ ∇ y f ^ ∥ ≤ 5 3 ∥ ∇ f ^ ∥ ≤ 2 ∥ ∇ f ^ ∥ . \lVert\nabla_{\bar{x}}\hat{f}-\nabla F\rVert\leq\frac{4}{3}\theta\sqrt{m}\lVert\nabla_y\hat{f}\rVert,\qquad\lVert\nabla F\rVert\leq\lVert\nabla_{\bar{x}}\hat{f}\rVert+\frac{4}{3}\lVert\nabla_y\hat{f}\rVert\leq\frac{5}{3}\lVert\nabla\hat{f}\rVert\leq2\lVert\nabla\hat{f}\rVert. ∥ ∇ x ˉ f ^ − ∇ F ∥ ≤ 3 4 θ m ∥ ∇ y f ^ ∥ , ∥ ∇ F ∥ ≤ ∥ ∇ x ˉ f ^ ∥ + 3 4 ∥ ∇ y f ^ ∥ ≤ 3 5 ∥ ∇ f ^ ∥ ≤ 2 ∥ ∇ f ^ ∥ .
Membership and stationarity
In either accuracy range of Theorem 3,
ν ≤ 8 ( c 0 60 ) 1 / 2 ≤ 1 12 , 360 δ ν ≤ 360 ( c 0 60 ) 1 / 2 L = L 8 , \nu\leq8\left(\frac{c_0}{60}\right)^{1/2}\leq\frac{1}{12},\qquad360\delta\nu\leq360\left(\frac{c_0}{60}\right)^{1/2}L=\frac{L}{8}, ν ≤ 8 ( 60 c 0 ) 1/2 ≤ 12 1 , 360 δ ν ≤ 360 ( 60 c 0 ) 1/2 L = 8 L ,
m = ⌊ ( 3 ν ) − 1 / 2 ⌋ ≥ 2 , θ 2 m = m ( 3 m − 1 ) ν ≤ 3 m 2 ν ≤ 1. m=\left\lfloor(3\nu)^{-1/2}\right\rfloor\geq2,\qquad\theta^2m=m(3m-1)\nu\leq3m^2\nu\leq1. m = ⌊ ( 3 ν ) − 1/2 ⌋ ≥ 2 , θ 2 m = m ( 3 m − 1 ) ν ≤ 3 m 2 ν ≤ 1.
Since inf f ^ n c = 0 \inf\hat{f}_{\mathrm{nc}}=0 inf f ^ nc = 0 , the gap satisfies
f ( 0 ) − inf f = δ ν β 2 f ^ n c ( 0 ) ≤ δ ν β 2 ( 1 / 2 + 10 T ) ≤ 20 T δ ν β 2 = 1280 T ε 2 δ ν ≤ Δ . f(0)-\inf f=\delta\nu\beta^2\hat{f}_{\mathrm{nc}}(0)\leq\delta\nu\beta^2(1/2+10T)\leq20T\delta\nu\beta^2=\frac{1280T\varepsilon^2}{\delta\nu}\leq\Delta. f ( 0 ) − inf f = δ ν β 2 f ^ nc ( 0 ) ≤ δ ν β 2 ( 1/2 + 10 T ) ≤ 20 T δ ν β 2 = δ ν 1280 T ε 2 ≤ Δ.
In particular,
T = ⌊ ρ 1 / 2 Δ ε − 3 / 2 1280 60 ⌋ ≥ 10 if ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 . (25) T=\left\lfloor\frac{\rho^{1/2}\Delta\varepsilon^{-3/2}}{1280\sqrt{60}}\right\rfloor\geq10\quad\text{if }\rho^{1/2}\Delta\varepsilon^{-3/2}\geq C_0. \tag*{(25)} T = ⌊ 1280 60 ρ 1/2 Δ ε − 3/2 ⌋ ≥ 10 if ρ 1/2 Δ ε − 3/2 ≥ C 0 . (25)
Only the coordinatewise potentials δ ν β 2 Υ ( x ˉ i / β ) \delta\nu\beta^2\Upsilon(\bar{x}_i/\beta) δ ν β 2 Υ ( x ˉ i / β ) are non-quadratic, so
∥ ∇ 3 f k ( x ) ∥ = ∥ ∇ 3 C ( x ) ∥ ≤ 480 δ ν β − 1 = 60 ( δ ν ) 2 ε = ρ . \lVert\nabla^3f_k(x)\rVert=\lVert\nabla^3C(x)\rVert\leq480\delta\nu\beta^{-1}=\frac{60(\delta\nu)^2}{\varepsilon}=\rho. ∥ ∇ 3 f k ( x )∥ = ∥ ∇ 3 C ( x )∥ ≤ 480 δ ν β − 1 = ε 60 ( δ ν ) 2 = ρ .
The common quadratic Hessian is a sub-sum of the positive semidefinite quadratic Hessian in Chen et al. [7 Appendix D] . Equal-owner edges are vertex-disjoint, and ∑ k P k \sum_k P_k ∑ k P k is a union of path Laplacians. Thus
∥ ∇ 2 C ∥ ≤ 4 δ + 360 δ ν , P k 2 = 2 P k , ∥ P k ∥ ≤ 2 , ∥ ∑ k P k ∥ ≤ 4. \lVert\nabla^2 C\rVert\le4\delta+360\delta\nu,\qquad P_k^2=2P_k,\qquad\lVert P_k\rVert\le2,\qquad\left\lVert\sum_k P_k\right\rVert\le4. ∥ ∇ 2 C ∥ ≤ 4 δ + 360 δ ν , P k 2 = 2 P k , ∥ P k ∥ ≤ 2 , k ∑ P k ≤ 4.
For IS, δ = L / ( 8 n ) \delta=L/(8n) δ = L / ( 8 n ) and n ≥ 4 n\ge4 n ≥ 4 give
∥ ∇ 2 f k ∥ ≤ 4 δ + 360 δ ν + 2 n δ ≤ L 8 + L 8 + L 4 < L . \lVert\nabla^2 f_k\rVert\le4\delta+360\delta\nu+2n\delta\le\frac{L}{8}+\frac{L}{8}+\frac{L}{4}<L. ∥ ∇ 2 f k ∥ ≤ 4 δ + 360 δ ν + 2 n δ ≤ 8 L + 8 L + 4 L < L .
For AS, put u = x − y u=x-y u = x − y and g = ∇ C ( x ) − ∇ C ( y ) g=\nabla C(x)-\nabla C(y) g = ∇ C ( x ) − ∇ C ( y ) . Then
1 n ∑ k = 1 n ∥ ∇ f k ( x ) − ∇ f k ( y ) ∥ 2 ≤ 2 ∥ g ∥ 2 + 2 n δ 2 ∑ k ∥ P k u ∥ 2 = 2 ∥ g ∥ 2 + 4 n δ 2 u T ( ∑ k P k ) u ≤ [ 2 ( 4 δ + 360 δ ν ) 2 + 16 n δ 2 ] ∥ u ∥ 2 ≤ ( 9 32 + 1 4 ) L 2 ∥ u ∥ 2 < L 2 ∥ u ∥ 2 , \begin{aligned}
\frac{1}{n}\sum_{k=1}^{n}\lVert\nabla f_k(x)-\nabla f_k(y)\rVert^2\le2\lVert g\rVert^2+2n\delta^2\sum_k\lVert P_k u\rVert^2=2\lVert g\rVert^2+4n\delta^2u^\mathsf{T}\left(\sum_kP_k\right)u \\
&\le\left[2(4\delta+360\delta\nu)^2+16n\delta^2\right]\lVert u\rVert^2\le\left(\frac{9}{32}+\frac{1}{4}\right)L^2\lVert u\rVert^2<L^2\lVert u\rVert^2,
\end{aligned} n 1 k = 1 ∑ n ∥ ∇ f k ( x ) − ∇ f k ( y ) ∥ 2 ≤ 2 ∥ g ∥ 2 + 2 n δ 2 k ∑ ∥ P k u ∥ 2 = 2 ∥ g ∥ 2 + 4 n δ 2 u T ( k ∑ P k ) u ≤ [ 2 ( 4 δ + 360 δ ν ) 2 + 16 n δ 2 ] ∥ u ∥ 2 ≤ ( 32 9 + 4 1 ) L 2 ∥ u ∥ 2 < L 2 ∥ u ∥ 2 ,
using δ = L / ( 8 n ) \delta=L/(8\sqrt{n}) δ = L / ( 8 n ) , 4 δ ≤ L / 4 4\delta\le L/4 4 δ ≤ L /4 , and 360 δ ν ≤ L / 8 360\delta\nu\le L/8 360 δ ν ≤ L /8 . Membership holds for every owner assignment. Finally,
x ˉ T = x ˉ T + 1 = 0 ⟹ ∥ ∇ f ( x ) ∥ = δ β ∥ ∇ f ^ ( x / β ) ∥ > δ β ν 8 = ε . \bar{x}_T=\bar{x}_{T+1}=0\quad\Longrightarrow\quad\lVert\nabla f(x)\rVert=\delta\beta\lVert\nabla\hat{f}(x/\beta)\rVert>\frac{\delta\beta\nu}{8}=\varepsilon. x ˉ T = x ˉ T + 1 = 0 ⟹ ∥ ∇ f ( x )∥ = δ β ∥ ∇ f ^ ( x / β )∥ > 8 δ β ν = ε .
Support propagation and owner search
Index coordinates by (23) . Every coupling joins adjacent coordinates, and Υ ′ ( 0 ) = Υ ′ ′ ( 0 ) = 0 \Upsilon'(0)=\Upsilon''(0)=0 Υ ′ ( 0 ) = Υ ′′ ( 0 ) = 0 . Therefore
supp ( x ) ∪ supp ( v ) ⊆ [ p ] ⟹ supp ( ∇ f k ( x ) ) ∪ supp ( ∇ 2 f k ( x ) v ) ⊆ [ p + 1 ] . \operatorname{supp}(x)\cup\operatorname{supp}(v)\subseteq[p]\quad\Longrightarrow\quad\operatorname{supp}(\nabla f_k(x))\cup\operatorname{supp}(\nabla^2 f_k(x)v)\subseteq[p+1]. supp ( x ) ∪ supp ( v ) ⊆ [ p ] ⟹ supp ( ∇ f k ( x )) ∪ supp ( ∇ 2 f k ( x ) v ) ⊆ [ p + 1 ] .
If the frontier link is an internal edge e e e , position p + 1 p+1 p + 1 can be exposed only when k = σ e k=\sigma_e k = σ e . For the union R t R_t R t of reply supports and p t = max R t p_t=\max R_t p t = max R t , Definition 2 gives
p 0 = 0 , p t ≤ p t − 1 + 1 , p t > p t − 1 ⟹ i t = σ e at an internal frontier edge e . p_0=0,\qquad p_t\le p_{t-1}+1,\qquad p_t>p_{t-1}\Longrightarrow i_t=\sigma_e\quad\text{at an internal frontier edge }e. p 0 = 0 , p t ≤ p t − 1 + 1 , p t > p t − 1 ⟹ i t = σ e at an internal frontier edge e .
Lemma 7 (Owner search). Let E \mathcal{E} E be the internal edges of bridges 1 , … , T − 1 1,\ldots,T-1 1 , … , T − 1 , so J = ∣ E ∣ = ( T − 1 ) ( m − 1 ) J=|\mathcal{E}|=(T-1)(m-1) J = ∣ E ∣ = ( T − 1 ) ( m − 1 ) . For a zero-respecting algorithm, let Y e Y_e Y e be the number of queries made while the frontier link is e e e , with Y e = ∞ Y_e=\infty Y e = ∞ if the frontier never reaches e e e . Then Pr [ ∑ e ∈ E Y e ≤ ( n − 1 ) J / 4 ] ≤ e − J / 8 \Pr[\sum_{e\in\mathcal{E}}Y_e\le(n-1)J/4]\le e^{-J/8} Pr [ ∑ e ∈ E Y e ≤ ( n − 1 ) J /4 ] ≤ e − J /8 .
Proof. Enumerate E \mathcal{E} E as e 1 , … , e J e_1,\ldots,e_J e 1 , … , e J in (23) , and let G r \mathcal{G}_r G r contain the transcript and private randomness when the frontier reaches e r e_r e r . Extend a stopped policy beyond its budget by searching successive frontier owners; its original transcript and output are unchanged. Before reaching e r e_r e r , all endpoints of e r e_r e r and later edges vanish in the query points and directions, so their owners do not affect any reply. Conditionally on G r \mathcal{G}_r G r , σ e r \sigma_{e_r} σ e r is uniform on
S r = { [ n ] , e r is the first edge of a bridge , [ n ] ∖ { σ e r − 1 } , otherwise . S_r=
\begin{cases}
[n], & e_r\text{ is the first edge of a bridge},\\
[n]\setminus\{\sigma_{e_{r-1}}\}, & \text{otherwise}.
\end{cases} S r = { [ n ] , [ n ] ∖ { σ e r − 1 } , e r is the first edge of a bridge , otherwise .
At e r e_r e r , an informative failed query excludes only its queried owner; a point and direction vanishing at the frontier give no information. Hence the owner’s rank U r U_r U r in any adaptive search order is conditionally uniform on [ ∣ S r ∣ ] [|S_r|] [ ∣ S r ∣ ] , is G r + 1 \mathcal{G}_{r+1} G r + 1 -measurable, and satisfies
Y e r ≥ U r , ∣ S r ∣ ∈ { n − 1 , n } , E [ U r ∣ G r ] ≥ n / 2 , 1 ≤ U r ≤ n . Y_{e_r} \ge U_r,\qquad|S_r| \in\{n-1,n\},\qquad\mathbb{E}[U_r\mid\mathcal{G}_r] \ge n/2,\qquad1\le U_r\le n. Y e r ≥ U r , ∣ S r ∣ ∈ { n − 1 , n } , E [ U r ∣ G r ] ≥ n /2 , 1 ≤ U r ≤ n .
Conditional Hoeffding, with s = J n / 2 − ( n − 1 ) J / 4 ≥ ( n − 1 ) J / 4 s=Jn/2-(n-1)J/4\ge(n-1)J/4 s = J n /2 − ( n − 1 ) J /4 ≥ ( n − 1 ) J /4 , gives
Pr [ ∑ r U r ≤ ( n − 1 ) J 4 ] ≤ exp ( − 2 s 2 J ( n − 1 ) 2 ) ≤ e − J / 8 . \Pr\left[\sum_r U_r\le\frac{(n-1)J}{4}\right]\le\exp\left(-\frac{2s^2}{J(n-1)^2}\right)\le e^{-J/8}. Pr [ r ∑ U r ≤ 4 ( n − 1 ) J ] ≤ exp ( − J ( n − 1 ) 2 2 s 2 ) ≤ e − J /8 .
Completion of the proof
Proof. Assume first that n ≥ 4 n\ge4 n ≥ 4 . For a budget N < ( n − 1 ) J / 4 N<(n-1)J/4 N < ( n − 1 ) J /4 , an output with x ˉ T ≠ 0 \bar{x}_T\ne0 x ˉ T = 0 or x ˉ T + 1 ≠ 0 \bar{x}_{T+1}\ne0 x ˉ T + 1 = 0 requires traversing every edge in E \mathcal{E} E . Since J ≥ 9 J\ge9 J ≥ 9 ,
Pr [ ∥ ∇ f ( x ^ ) ∥ ≤ ε ] ≤ Pr [ ∑ e ∈ E Y e ≤ N ] ≤ e − J / 8 ≤ e − 9 / 8 < 1 3 . \Pr[\|\nabla f(\hat{x})\|\le\varepsilon]\le\Pr\left[\sum_{e\in\mathcal{E}}Y_e\le N\right]\le e^{-J/8}\le e^{-9/8}<\frac{1}{3}. Pr [ ∥∇ f ( x ^ ) ∥ ≤ ε ] ≤ Pr [ e ∈ E ∑ Y e ≤ N ] ≤ e − J /8 ≤ e − 9/8 < 3 1 .
Consequently,
N E z r ≥ ( n − 1 ) ( T − 1 ) ( m − 1 ) 4 ≥ 27 320 n T m , \mathcal{N}_{\mathcal{E}}^{\mathrm{zr}}\ge\frac{(n-1)(T-1)(m-1)}{4}\ge\frac{27}{320}nTm, N E zr ≥ 4 ( n − 1 ) ( T − 1 ) ( m − 1 ) ≥ 320 27 n T m ,
using n − 1 ≥ 3 n / 4 n-1\ge3n/4 n − 1 ≥ 3 n /4 , T − 1 ≥ 9 T / 10 T-1\ge9T/10 T − 1 ≥ 9 T /10 , and m − 1 ≥ m / 2 m-1\ge m/2 m − 1 ≥ m /2 . Moreover,
m ≥ 2 3 ( 3 ν ) − 1 / 2 , T ≥ 0.9 ρ 1 / 2 Δ ε − 3 / 2 1280 60 . m\ge\frac{2}{3}(3\nu)^{-1/2},\qquad T\ge\frac{0.9\rho^{1/2}\Delta\varepsilon^{-3/2}}{1280\sqrt{60}}. m ≥ 3 2 ( 3 ν ) − 1/2 , T ≥ 1280 60 0.9 ρ 1/2 Δ ε − 3/2 .
Substitution of (23) yields
n T m ≥ 0.6 1280 ⋅ 60 1 / 4 24 { n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 (AS) , n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 (IS) . nTm\ge\frac{0.6}{1280\cdot60^{1/4}\sqrt{24}}
\begin{cases}
n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} & \text{(AS)},\\
\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} & \text{(IS)}.
\end{cases} n T m ≥ 1280 ⋅ 6 0 1/4 24 0.6 { n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 n L 1/2 ρ 1/4 Δ ε − 7/4 (AS) , (IS) .
For n ≤ 3 n\le3 n ≤ 3 , take identical components f k = δ β 2 f ^ ( ⋅ / β ) f_k=\delta\beta^2\hat{f}(\cdot/\beta) f k = δ β 2 f ^ ( ⋅ / β ) with δ = L / 8 \delta=L/8 δ = L /8 and the other parameters of (23). The Hessian-Lipschitz, gap, and gradient conditions above depend on δ \delta δ only through δ ν \delta\nu δ ν , and ∥ ∇ 2 f k ∥ ≤ 4 δ + 360 δ ν < L \|\nabla^2 f_k\|\le4\delta+360\delta\nu<L ∥ ∇ 2 f k ∥ ≤ 4 δ + 360 δ ν < L since ν ≤ 1 / 90 \nu\le1/90 ν ≤ 1/90 in the stated range. A component query returns a full query, and p t ≤ p t − 1 + 1 p_t\le p_{t-1}+1 p t ≤ p t − 1 + 1 , so an output with x ˉ T ≠ 0 \bar{x}_T\ne0 x ˉ T = 0 or x ˉ T + 1 ≠ 0 \bar{x}_{T+1}\ne0 x ˉ T + 1 = 0 requires at least ( T − 1 ) ( m − 1 ) ≥ 0.45 T m (T-1)(m-1)\ge0.45Tm ( T − 1 ) ( m − 1 ) ≥ 0.45 T m queries. With ν = 8 ( ρ ε / 60 ) 1 / 2 / L \nu=8(\rho\varepsilon/60)^{1/2}/L ν = 8 ( ρε /60 ) 1/2 / L , this exceeds 3 3 / 4 c 1 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ≥ c 1 n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 3^{3/4}c_1L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}\ge c_1n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} 3 3/4 c 1 L 1/2 ρ 1/4 Δ ε − 7/4 ≥ c 1 n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 , so the same constant c 1 c_1 c 1 serves.
Proofs for Unrestricted Randomized Algorithms
The replicated instance
With smoothness budget L ⋆ L_\star L ⋆ and the universal constants of Zhang et al. [20 ] , set
h = H 0 ε , γ = c γ ( ρ h ) 1 / 2 , D 0 = h 2 / γ , h=H_0\varepsilon,\qquad\gamma=c_\gamma(\rho h)^{1/2},\qquad D_0=h^2/\gamma, h = H 0 ε , γ = c γ ( ρ h ) 1/2 , D 0 = h 2 / γ ,
M = ⌊ c M ( L ⋆ / γ ) 1 / 2 ⌋ , N = ⌊ c N Δ / D 0 ⌋ , m = ⌊ M / 2 ⌋ . (26) M=\left\lfloor c_M(L_\star/\gamma)^{1/2}\right\rfloor,\qquad N=\left\lfloor c_N\Delta/D_0\right\rfloor,\qquad m=\lfloor M/2\rfloor. \tag*{(26)} M = ⌊ c M ( L ⋆ / γ ) 1/2 ⌋ , N = ⌊ c N Δ/ D 0 ⌋ , m = ⌊ M /2 ⌋ . (26)
For ε ≤ c 0 L ⋆ 2 / ρ \varepsilon\le c_0L_\star^2/\rho ε ≤ c 0 L ⋆ 2 / ρ and ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2}\ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 , Zhang et al. [20, Lemmas 5.2–5.4] give m , N ≥ 2 m,N\ge2 m , N ≥ 2 and
N m ≍ L ⋆ 1 / 4 ρ 1 / 4 Δ ε − 7 / 4 . (27) Nm\asymp L_\star^{1/4}\rho^{1/4}\Delta\varepsilon^{-7/4}. \tag*{(27)} N m ≍ L ⋆ 1/4 ρ 1/4 Δ ε − 7/4 . (27)
They also provide distinct eigenvalues λ j ∈ [ γ , L ⋆ / 4 ] \lambda_j \in[\gamma, L_{\star}/4] λ j ∈ [ γ , L ⋆ /4 ] , positive weights ν j \nu_j ν j , and a residual
r ( λ ) = λ − 1 − p ⋆ ( λ ) , deg p ⋆ ≤ m − 1 , ∥ r ∥ ν ≥ c / γ r(\lambda) = \lambda^{-1} - p_{\star}(\lambda), \qquad\deg p_{\star} \le m - 1, \qquad\lVert r\rVert_{\nu} \ge c/\gamma r ( λ ) = λ − 1 − p ⋆ ( λ ) , deg p ⋆ ≤ m − 1 , ∥ r ∥ ν ≥ c / γ
orthogonal to polynomials of degree below m m m in the ν \nu ν -weighted spectral inner product. Put Λ = diag ( λ j I K j ) \Lambda= \operatorname{diag}(\lambda_j I_{K_j}) Λ = diag ( λ j I K j ) , with multiplicities specified below.
Fix N n Nn N n public, mutually orthogonal owner subspaces of dimension ∑ j K j \sum_j K_j ∑ j K j . Independently draw Haar rotations U s i U_{si} U s i and uniform unit vectors u s i u_{si} u s i , and define
A s i = U s i Λ U s i T , b s i = h n U s i u s i , a s = r ( A s ) b s ∥ r ( A s ) b s ∥ . (28) A_{si} = U_{si}\Lambda U_{si}^{\mathsf{T}}, \qquad b_{si} = \frac{h}{\sqrt{n}}U_{si}u_{si}, \qquad a_s = \frac{r(A_s)b_s}{\lVert r(A_s)b_s\rVert}. \tag*{(28)} A s i = U s i Λ U s i T , b s i = n h U s i u s i , a s = ∥ r ( A s ) b s ∥ r ( A s ) b s . (28)
where A s , b s A_s,b_s A s , b s collect the owner blocks and z s i z_{si} z s i denotes owner i i i ’s coordinates in block s s s . Choose an arbitrary unit readout on the null event of a zero denominator. Using R B , ϑ , ψ R_B,\vartheta,\psi R B , ϑ , ψ from Zhang et al. [20 ] , with ψ ( k ) = 0 \psi^{(k)} = 0 ψ ( k ) = 0 on ( − ∞ , 1 / 4 ] (-\infty,1/4] ( − ∞ , 1/4 ] for every k ≥ 0 k \ge0 k ≥ 0 , put
v s ( z s ) = a s T R B ( z s ) α 0 , ℓ s ( z s ) = D 0 [ C ℓ + ϑ ( b s T z s / D 0 ) ] , v_s(z_s) = \frac{a_s^{\mathsf{T}}R_B(z_s)}{\alpha_0}, \qquad\ell_s(z_s) = D_0[C_{\ell} + \vartheta(b_s^{\mathsf{T}}z_s/D_0)], v s ( z s ) = α 0 a s T R B ( z s ) , ℓ s ( z s ) = D 0 [ C ℓ + ϑ ( b s T z s / D 0 )] ,
G ( z ) = − ℓ 1 ( z 1 ) − ∑ s = 2 N ψ ( v s − 1 ( z s − 1 ) ) ℓ s ( z s ) , f i ( z ) = G ( z ) + n 2 ∑ s = 1 N z s i T A s i z s i . (29) G(z) = -\ell_1(z_1) - \sum_{s=2}^{N}\psi(v_{s-1}(z_{s-1}))\ell_s(z_s), \qquad f_i(z) = G(z) + \frac{n}{2}\sum_{s=1}^{N}z_{si}^{\mathsf{T}}A_{si}z_{si}. \tag*{(29)} G ( z ) = − ℓ 1 ( z 1 ) − s = 2 ∑ N ψ ( v s − 1 ( z s − 1 )) ℓ s ( z s ) , f i ( z ) = G ( z ) + 2 n s = 1 ∑ N z s i T A s i z s i . (29)
The average
F ( z ) = G ( z ) + 1 2 ∑ s z s T A s z s F(z) = G(z) + \frac{1}{2}\sum_s z_s^{\mathsf{T}}A_sz_s F ( z ) = G ( z ) + 2 1 s ∑ z s T A s z s
uses the same cascade as Zhang et al. [20 ] . Each A s A_s A s has the distinct eigenvalues λ j \lambda_j λ j with multiplicities n K j nK_j n K j . Writing Π j \Pi_j Π j for the latent projector onto the λ j \lambda_j λ j eigenspace of one owner, its normalized spectral weights are
ω s j = 1 n ∑ i = 1 n ∥ Π j u s i ∥ 2 . \omega_{sj} = \frac{1}{n}\sum_{i=1}^{n}\lVert\Pi_j u_{si}\rVert^2. ω s j = n 1 i = 1 ∑ n ∥ Π j u s i ∥ 2 .
Thus the aggregate weights lie within the same relative error of ν j \nu_j ν j whenever every owner’s weights do.
Regularity and spectral certificates
The norm-based bounds of Zhang et al. [20, Proposition 6.1] hold for every realization:
F ( 0 ) − inf F ≤ Δ , ∥ ∇ 2 F ∥ ≤ L ⋆ , Lip ( ∇ 2 F ) ≤ ρ . F(0) - \inf F \le\Delta, \qquad\lVert\nabla^2F\rVert\le L_{\star}, \qquad\operatorname{Lip}(\nabla^2F) \le\rho. F ( 0 ) − inf F ≤ Δ , ∥ ∇ 2 F ∥ ≤ L ⋆ , Lip ( ∇ 2 F ) ≤ ρ .
The owner Hessians Q i Q_i Q i have orthogonal supports, ∥ Q i ∥ ≤ L ⋆ / 4 \lVert Q_i\rVert\le L_{\star}/4 ∥ Q i ∥ ≤ L ⋆ /4 , and ∥ ∇ 2 G ∥ ≤ 5 L ⋆ / 4 \lVert\nabla^2G\rVert\le5L_{\star}/4 ∥ ∇ 2 G ∥ ≤ 5 L ⋆ /4 . Hence
∥ ∇ 2 f i ∥ ≤ n + 5 4 L ⋆ , 1 n ∑ i ∥ ∇ f i ( x ) − ∇ f i ( x ′ ) ∥ 2 ≤ n + 25 8 L ⋆ 2 ∥ x − x ′ ∥ 2 , \lVert\nabla^2f_i\rVert\le\frac{n+5}{4}L_{\star}, \qquad\frac{1}{n}\sum_i\lVert\nabla f_i(x)-\nabla f_i(x')\rVert^2 \le\frac{n+25}{8}L_{\star}^2\lVert x-x'\rVert^2, ∥ ∇ 2 f i ∥ ≤ 4 n + 5 L ⋆ , n 1 i ∑ ∥ ∇ f i ( x ) − ∇ f i ( x ′ ) ∥ 2 ≤ 8 n + 25 L ⋆ 2 ∥ x − x ′ ∥ 2 ,
L ⋆ = { L / ( 2 n ) (AS) , L / ( 2 n ) (IS) . L_{\star} =
\begin{cases}
L/(2\sqrt{n}) & \text{(AS)},\\
L/(2n) & \text{(IS)}.
\end{cases} L ⋆ = { L / ( 2 n ) L / ( 2 n ) (AS) , (IS) .
Since ∇ 3 f i = ∇ 3 F \nabla^3 f_i = \nabla^3 F ∇ 3 f i = ∇ 3 F , every component is individually ρ \rho ρ -Hessian-Lipschitz.
The stationarity and projection certificates of Zhang et al. [20, Lemmas 6.3 and 7.2] require
∥ b s ∥ = h , γ I ⪯ A s ⪯ L ⋆ 4 I . \lVert b_s\rVert= h,\qquad\gamma I \preceq A_s \preceq\frac{L_\star}{4}I. ∥ b s ∥ = h , γ I ⪯ A s ⪯ 4 L ⋆ I .
and spectral weights within 1 ± δ 1 \pm\delta 1 ± δ of ν \nu ν . The first two hold exactly. If J J J is the number of distinct eigenvalues, choose, for the horizon T T T of Lemma 8,
K j ≥ C [ ( 2 T ) 2 + η − 2 ( 2 T ) + δ − 2 ] log 2 J N n ζ , ∣ K j ∑ k K k − ν j ∣ ≤ δ ν j 4 . K_j \ge C\left[(2T)^2+\eta^{-2}(2T)+\delta^{-2}\right]\log\frac{2JNn}{\zeta},\qquad\left\lvert\frac{K_j}{\sum_k K_k}-\nu_j\right\rvert\le\frac{\delta\nu_j}{4}. K j ≥ C [ ( 2 T ) 2 + η − 2 ( 2 T ) + δ − 2 ] log ζ 2 J N n , ∑ k K k K j − ν j ≤ 4 δ ν j .
The multiplicities are chosen after fixing a horizon T ≥ 4 n N M + 1 T \ge4nNM+1 T ≥ 4 n N M + 1 , including one slot for the terminal output. All owner-weight and Gaussian projection bounds then hold with probability at least 1 − ζ 1-\zeta 1 − ζ . The norm and moment arguments of Zhang et al. [20, Lemma 6.3] depend only on these spectral weights and the displayed norm bounds, so they apply to the replicated block. On this event,
∥ ∇ F ( z ) ∥ ≤ ε ⟹ { ψ ( v s ( z s ) ) = 1 1 ≤ s < N , ∥ A N z N − b N ∥ ≤ ε , ∥ z s ∥ ≤ B 1 ≤ s ≤ N . \lVert\nabla F(z)\rVert\le\varepsilon\quad\Longrightarrow\quad
\begin{cases}
\psi(v_s(z_s))=1 & 1\le s<N,\\
\lVert A_Nz_N-b_N\rVert\le\varepsilon,\\
\lVert z_s\rVert\le B & 1\le s\le N.
\end{cases} ∥ ∇ F ( z )∥ ≤ ε ⟹ ⎩ ⎨ ⎧ ψ ( v s ( z s )) = 1 ∥ A N z N − b N ∥ ≤ ε , ∥ z s ∥ ≤ B 1 ≤ s < N , 1 ≤ s ≤ N .
In particular R B ( z N ) = z N R_B(z_N)=z_N R B ( z N ) = z N . The moment bound a N T A N − 1 b N ≥ α 0 a_N^{\mathsf T}A_N^{-1}b_N\ge\alpha_0 a N T A N − 1 b N ≥ α 0 and the fixed choices of c α , H 0 c_\alpha,H_0 c α , H 0 give
a N T z N ≥ a N T A N − 1 b N − ε / γ ≥ 3 α 0 / 4 , v N ( z N ) ≥ 3 / 4. a_N^{\mathsf T}z_N\ge a_N^{\mathsf T}A_N^{-1}b_N-\varepsilon/\gamma\ge3\alpha_0/4,\qquad v_N(z_N)\ge3/4. a N T z N ≥ a N T A N − 1 b N − ε / γ ≥ 3 α 0 /4 , v N ( z N ) ≥ 3/4.
Scheduled disclosure
Set α 0 = c α h / γ \alpha_0=c_\alpha h/\gamma α 0 = c α h / γ and B = C B h / γ B=C_Bh/\gamma B = C B h / γ as in Zhang et al. [20 ] . Choose universal c d e l a y > 0 c_{\mathrm{delay}}>0 c delay > 0 small enough, and the accuracy constant so that m ≥ ⌈ 2 / c d e l a y ⌉ m\ge\lceil2/c_{\mathrm{delay}}\rceil m ≥ ⌈ 2/ c delay ⌉ . Then
q 0 = ⌊ c d e l a y n m ⌋ ≥ 1 2 c d e l a y n m ≥ 1. q_0=\lfloor c_{\mathrm{delay}}nm\rfloor\ge\frac{1}{2}c_{\mathrm{delay}}nm\ge1. q 0 = ⌊ c delay nm ⌋ ≥ 2 1 c delay nm ≥ 1.
Before query selection, the auxiliary oracle discloses ( u s i , b s i ) i (u_{si},b_{si})_i ( u s i , b s i ) i at τ s = 1 + ( s − 1 ) q 0 \tau_s=1+(s-1)q_0 τ s = 1 + ( s − 1 ) q 0 and ( U s i ) i (U_{si})_i ( U s i ) i at σ s = 1 + s q 0 \sigma_s=1+sq_0 σ s = 1 + s q 0 . Each call also reveals the latent coordinates of its point and direction in every owner subspace, and their products with A s i A_{si} A s i for the selected owner. Its censored reply is the value, gradient, and Hessian–vector product of
k ( t ) = min { N , 1 + ⌊ ( t − 1 ) / q 0 ⌋ } , G t ( z ) = − ℓ 1 ( z 1 ) − ∑ s = 2 k ( t ) ψ ( v s − 1 ( z s − 1 ) ) ℓ s ( z s ) , k(t)=\min\{N,1+\lfloor(t-1)/q_0\rfloor\},\qquad G_t(z)=-\ell_1(z_1)-\sum_{s=2}^{k(t)}\psi(v_{s-1}(z_{s-1}))\ell_s(z_s), k ( t ) = min { N , 1 + ⌊( t − 1 ) / q 0 ⌋} , G t ( z ) = − ℓ 1 ( z 1 ) − s = 2 ∑ k ( t ) ψ ( v s − 1 ( z s − 1 )) ℓ s ( z s ) ,
f i , t ( z ) = G t ( z ) + n 2 ∑ s = 1 N z s i T A s i z s i . f_{i,t}(z)=G_t(z)+\frac{n}{2}\sum_{s=1}^{N}z_{si}^{\mathsf T}A_{si}z_{si}. f i , t ( z ) = G t ( z ) + 2 n s = 1 ∑ N z s i T A s i z s i .
Every retained coupling has a disclosed predecessor rotation and successor forcing vector. We show below that omitted couplings are flat at all query points.
Selected-owner information span
Lemma 8. Fix a deterministic policy and a horizon T ≥ 4 n N M + 1 T\ge4nNM+1 T ≥ 4 n N M + 1 , and let the owner dimension be large enough. For every pair ( s , i ) (s,i) ( s , i ) there are 2 T 2T 2 T jointly independent standard Gaussian vectors,
independent of u s i u_{si} u s i , such that for t ≤ T t \le T t ≤ T and t < σ s t < \sigma_s t < σ s both latent query vectors of the t t t th call, restricted to ( s , i ) (s,i) ( s , i ) , lie in
V s i + 1 { t ≥ τ s } span { u s i , Λ u s i , … , Λ q s i ( t ) u s i } . V_{si} + 1\{t \ge\tau_s\}\operatorname{span}\{u_{si},\Lambda u_{si},\ldots,\Lambda^{q_{si}(t)}u_{si}\}. V s i + 1 { t ≥ τ s } span { u s i , Λ u s i , … , Λ q s i ( t ) u s i } .
where V s i V_{si} V s i is the Λ \Lambda Λ -cyclic span of the Gaussian vectors and q s i ( t ) q_{si}(t) q s i ( t ) counts calls to component i i i in [ τ s , t ) [\tau_s,t) [ τ s , t ) . The Gaussian and independence assertions hold also conditional on the raw draws of every other pair. The same conclusion holds for a passive point selected from the preceding transcript and exposed without returning a matrix product or incrementing an owner counter.
Proof. Fix ( s , i ) (s,i) ( s , i ) , condition on the raw draws of all other pairs, and write U = U s i U=U_{si} U = U s i , u = u s i u=u_{si} u = u s i . Before σ s \sigma_s σ s , the retained couplings involve this pair only through its disclosed forcing vector: its outgoing readout is censored, and every retained predecessor readout has a disclosed rotation. The censored replies are therefore computable from the other draws, the disclosed forcing vector, the latent point and direction, and the selected-owner matrix products, which reduces the policy to an adaptive strategy for the single pair. Conditioning on raw independent draws rather than on adaptive transcripts preserves their distribution.
Let L \mathcal{L} L be the span of the latent vectors whose images under U U U have been exposed: earlier latent points and directions, their products with Λ \Lambda Λ on calls to owner i i i , and u u u once disclosed. Conditional on this history, the restriction U : L ⊥ → ( U L ) ⊥ U:\mathcal{L}^{\perp}\to(U\mathcal{L})^{\perp} U : L ⊥ → ( U L ) ⊥ is Haar. Before τ s \tau_s τ s the history does not use u u u , so this also holds conditional on u u u ; at the fixed round τ s \tau_s τ s , disclosing ( u , b s i ) (u,b_{si}) ( u , b s i ) adjoins u u u to L \mathcal{L} L and preserves the conditional Haar law on the complement.
At round t t t , expose the point first, without returning a matrix product. Decompose its physical restriction w = w ∥ + w ⊥ w=w_{\parallel}+w_{\perp} w = w ∥ + w ⊥ relative to U L U\mathcal{L} U L . If w ⊥ ≠ 0 w_{\perp}\ne0 w ⊥ = 0 , then e = U ⊤ w ⊥ / ∥ w ⊥ ∥ e=U^{\top}w_{\perp}/\lVert w_{\perp}\rVert e = U ⊤ w ⊥ / ∥ w ⊥ ∥ is conditionally uniform on the unit sphere of L ⊥ \mathcal{L}^{\perp} L ⊥ , also conditional on u u u . Draw independently a ∼ N ( 0 , P L ) a\sim N(0,P_{\mathcal{L}}) a ∼ N ( 0 , P L ) and a chi radius R R R with dim L ⊥ \dim\mathcal{L}^{\perp} dim L ⊥ degrees of freedom, and put g = a + R e g=a+Re g = a + R e . Then g g g is conditionally N ( 0 , I ) N(0,I) N ( 0 , I ) and U ⊤ w ∈ L + span { g } U^{\top}w\in\mathcal{L}+\operatorname{span}\{g\} U ⊤ w ∈ L + span { g } ; if w ⊥ = 0 w_{\perp}=0 w ⊥ = 0 , a fresh standard Gaussian serves the same purpose. Adjoin U ⊤ w U^{\top}w U ⊤ w to L \mathcal{L} L and treat the direction, which was fixed before the point exposure, in the same way. Each exposure reveals U U U only on the new direction e e e , whose image is the fixed vector w ⊥ / ∥ w ⊥ ∥ w_{\perp}/\lVert w_{\perp}\rVert w ⊥ / ∥ w ⊥ ∥ , and the added Gaussian component and radius are independent. Hence the conditional Haar invariant persists, and the successive conditional laws make all innovations jointly independent and independent of u u u .
Just before call t t t , let q = q s i ( t ) q=q_{si}(t) q = q s i ( t ) and assume inductively that all exposed latent vectors lie in V s i + 1 { t ≥ τ s } span { u , Λ u , … , Λ q u } V_{si}+1\{t\ge\tau_s\}\operatorname{span}\{u,\Lambda u,\ldots,\Lambda^q u\} V s i + 1 { t ≥ τ s } span { u , Λ u , … , Λ q u } . The two exposures add one Gaussian start each and preserve the inclusion. Only afterwards are the products returned. If component i i i was selected, applying Λ \Lambda Λ to both latent vectors raises the marked degree to at most q + 1 q+1 q + 1 , not twice, since neither query vector depends on the current products; the counter increases by one. Otherwise no product for this pair is returned and the counter is unchanged. Gaussian terms stay in V s i V_{si} V s i , which proves the inclusion. A passive exposure is the same argument with no product and no increment. At most 4 T + 1 4T+1 4 T + 1 generators enter L \mathcal{L} L ; pad the Gaussian family with independent draws to length 2 T 2T 2 T . A sufficiently large owner dimension, ensured by the multiplicity choice, completes the construction. □ \square □
Proof of Theorem 4
Proof. On the spectral-weight event, write
a s i = β s i U s i a ~ s i , a ~ s i = r ( Λ ) u s i ∥ r ( Λ ) u s i ∥ , ∑ i β s i 2 = 1 , β s i 2 ≤ 2 n a_{si}=\beta_{si}U_{si}\widetilde{a}_{si},\qquad
\widetilde{a}_{si}=\frac{r(\Lambda)u_{si}}{\lVert r(\Lambda)u_{si}\rVert},\qquad
\sum_i\beta_{si}^{2}=1,\qquad
\beta_{si}^{2}\le\frac{2}{n} a s i = β s i U s i a s i , a s i = ∥ r ( Λ ) u s i ∥ r ( Λ ) u s i , i ∑ β s i 2 = 1 , β s i 2 ≤ n 2
for δ ≤ 1 / 3 \delta\le1/3 δ ≤ 1/3 . At t < σ s t < \sigma_s t < σ s , define the heavy owners by H s ( t ) = { i : q s i ( t ) ≥ m } \mathcal{H}_s(t) = \{i : q_{si}(t) \ge m\} H s ( t ) = { i : q s i ( t ) ≥ m } . Then
∣ H s ( t ) ∣ ≤ q 0 m ≤ c d e l a y n , ∑ i ∈ H s ( t ) β s i 2 ≤ 2 c d e l a y . |\mathcal{H}_s(t)| \le\frac{q_0}{m} \le c_{\mathrm{delay}}n,\qquad\sum_{i\in\mathcal{H}_s(t)} \beta_{si}^{2} \le2c_{\mathrm{delay}}. ∣ H s ( t ) ∣ ≤ m q 0 ≤ c delay n , i ∈ H s ( t ) ∑ β s i 2 ≤ 2 c delay .
The mass bound holds for every subset, including this adaptive choice. For each light owner’s latent query vector x x x , Lemma 8 and Zhang et al. [20, Lemma 7.2] give
∣ a ~ s i T x ∣ ≤ C ( δ + η ) ∥ x ∥ . |\widetilde{a}_{si}^{\mathsf{T}}x| \le C(\delta+\eta)\lVert x\rVert. ∣ a s i T x ∣ ≤ C ( δ + η ) ∥ x ∥ .
Radiality of R B R_B R B and Cauchy–Schwarz across owners yield
∣ a s T R B ( z s ) ∣ ≤ 2 B ( 2 c d e l a y + C ( δ + η ) ) ≤ α 0 4 , (30) |a_s^{\mathsf{T}}R_B(z_s)| \le2B\left(\sqrt{2c_{\mathrm{delay}}}+C(\delta+\eta)\right) \le\frac{\alpha_0}{4}, \tag*{(30)} ∣ a s T R B ( z s ) ∣ ≤ 2 B ( 2 c delay + C ( δ + η ) ) ≤ 4 α 0 , (30)
for sufficiently small universal c d e l a y c_{\mathrm{delay}} c delay , δ \delta δ , η \eta η , since B / α 0 = C B / c α B/\alpha_0=C_B/c_\alpha B / α 0 = C B / c α is universal.
Every omitted coupling has a flat gate, so its value and all derivatives vanish. In particular its Hessian–vector contribution is zero for every queried direction. Induction on rounds couples the censored and true transcripts on the concentration event. For t < τ N = σ N − 1 t<\tau_N=\sigma_{N-1} t < τ N = σ N − 1 , the ( N − 1 ) (N-1) ( N − 1 ) st gate is closed, contradicting the stationarity certificate; for τ N ≤ t < σ N \tau_N\le t<\sigma_N τ N ≤ t < σ N , (29) contradicts its consequence v N ( z N ) ≥ 3 / 4 v_N(z_N)\ge3/4 v N ( z N ) ≥ 3/4 .
To include an arbitrary terminal output, fix a query cap Q Q Q , pad earlier stopping with ignored zero queries, and freeze the output after reply Q Q Q , before any disclosure scheduled for round Q + 1 Q+1 Q + 1 . At that round, expose its latent coordinates as a passive point with zero direction, no matrix product, and no counter increment. The output is measurable with respect to the enlarged history, so Lemma 8 and (29) apply to it. If c ≤ c d e l a y / 4 c\le c_{\mathrm{delay}}/4 c ≤ c delay /4 , then Q < c n N m Q<cnNm Q < c n N m implies Q + 1 ≤ N q 0 < σ N Q+1\le Nq_0<\sigma_N Q + 1 ≤ N q 0 < σ N , by q 0 ≥ c d e l a y n m / 2 q_0\ge c_{\mathrm{delay}}nm/2 q 0 ≥ c delay nm /2 and N ≥ 2 N\ge2 N ≥ 2 , so the output also violates a necessary stationarity condition.
With ζ = 1 / 6 \zeta=1/6 ζ = 1/6 , every deterministic policy with fewer than c n N m cnNm c n N m calls fails with probability at least 5 / 6 5/6 5/6 under the hard distribution, whose multiplicities depend only on the horizon and the class parameters. Fixing the private randomness of a randomized algorithm and integrating gives the same failure probability, so no algorithm succeeds with probability 2 / 3 2/3 2/3 on every instance.
Finally, (26) gives
n N m ≍ { n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 L ⋆ = L / ( 2 n ) , n L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 L ⋆ = L / ( 2 n ) , nNm \asymp
\begin{cases}
n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} & L_\star=L/(2\sqrt{n}),\\
\sqrt{n}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4} & L_\star=L/(2n),
\end{cases} n N m ≍ { n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 n L 1/2 ρ 1/4 Δ ε − 7/4 L ⋆ = L / ( 2 n ) , L ⋆ = L / ( 2 n ) ,
with the accuracy thresholds
c 0 L ⋆ 2 ρ = { c 0 L 2 / ( 4 n ρ ) ( A S ) , c 0 L 2 / ( 4 n 2 ρ ) ( I S ) . \frac{c_0L_\star^2}{\rho}=
\begin{cases}
c_0L^2/(4n\rho) & (\mathrm{AS}),\\
c_0L^2/(4n^2\rho) & (\mathrm{IS}).
\end{cases} ρ c 0 L ⋆ 2 = { c 0 L 2 / ( 4 n ρ ) c 0 L 2 / ( 4 n 2 ρ ) ( AS ) , ( IS ) .
Proofs for the Low-Accuracy Lower Bound
The dense-weak-hiding instance
For j ∈ [ T ] j\in[T] j ∈ [ T ] , take x j ∈ R D x_j\in\mathbb{R}^D x j ∈ R D , a hidden direction Θ ( j ) ∈ { ± 1 } D \Theta^{(j)}\in\{\pm1\}^D Θ ( j ) ∈ { ± 1 } D , and a fixed encoding table S ( j ) ∈ { ± 1 } n × D S^{(j)}\in\{\pm1\}^{n\times D} S ( j ) ∈ { ± 1 } n × D satisfying
1 n ∑ i S i ( j ) = ϱ Θ ( j ) , n − 1 / 2 ≤ ϱ < 17 16 n − 1 / 2 . \frac{1}{n}\sum_i S_i^{(j)}=\varrho\Theta^{(j)},\qquad n^{-1/2}\le\varrho<\frac{17}{16}n^{-1/2}. n 1 i ∑ S i ( j ) = ϱ Θ ( j ) , n − 1/2 ≤ ϱ < 16 17 n − 1/2 .
For Ψ ( z ) = z / ( 1 + ∥ z ∥ 2 ) 1 / 2 \Psi(z)=z/(1+\lVert z\rVert^2)^{1/2} Ψ ( z ) = z / ( 1 + ∥ z ∥ 2 ) 1/2 , define
q j ( z ) = ⟨ Θ ( j ) D , Ψ ( z ) ⟩ , q ~ i j ( z ) = 1 ϱ ⟨ S i ( j ) D , Ψ ( z ) ⟩ , q_j(z)=\left\langle\frac{\Theta^{(j)}}{\sqrt{D}},\Psi(z)\right\rangle,\qquad\widetilde{q}_{ij}(z)=\frac{1}{\varrho}\left\langle\frac{S_i^{(j)}}{\sqrt{D}},\Psi(z)\right\rangle, q j ( z ) = ⟨ D Θ ( j ) , Ψ ( z ) ⟩ , q ij ( z ) = ϱ 1 ⟨ D S i ( j ) , Ψ ( z ) ⟩ ,
R i ( x ) = − q ~ i 1 ( x 1 ) − ∑ j = 2 T G ( q j − 1 ( x j − 1 ) ) ( q ~ i j ( x j ) + 1 ) + 33 32 ∥ x ∥ 2 (31) R_i(x)=-\widetilde{q}_{i1}(x_1)-\sum_{j=2}^{T}G\bigl(q_{j-1}(x_{j-1})\bigr)\bigl(\widetilde{q}_{ij}(x_j)+1\bigr)+\frac{33}{32}\lVert x\rVert^2 \tag*{(31)} R i ( x ) = − q i 1 ( x 1 ) − j = 2 ∑ T G ( q j − 1 ( x j − 1 ) ) ( q ij ( x j ) + 1 ) + 32 33 ∥ x ∥ 2 (31)
where G G G is the gate of Peng et al. [18 Lemma A.1] , with all derivatives zero on ( − ∞ , 5 / 32 ] (-\infty,5/32] ( − ∞ , 5/32 ] . The scaling f i ( y ) = α R i ( β y ) f_i(y)=\alpha R_i(\beta y) f i ( y ) = α R i ( β y ) of Peng et al. [18 Equation (148)] gives individual smoothness L L L and gradient norm at least 8 ε 8\varepsilon 8 ε before the last stage is revealed. Recovering each hidden direction Θ ( j ) \Theta^{(j)} Θ ( j ) requires order min { n , ϱ − 2 } = n \min\{n,\varrho^{-2}\}=n min { n , ϱ − 2 } = n distinct rows.
The average is free of the bias. Since n − 1 ∑ i q ~ i j = q j n^{-1}\sum_i\widetilde{q}_{ij}=q_j n − 1 ∑ i q ij = q j , the average
R ( x ) = − q 1 ( x 1 ) − ∑ j = 2 T G ( q j − 1 ( x j − 1 ) ) ( q j ( x j ) + 1 ) + 33 32 ∥ x ∥ 2 (32) R(x)=-q_1(x_1)-\sum_{j=2}^{T}G\bigl(q_{j-1}(x_{j-1})\bigr)\bigl(q_j(x_j)+1\bigr)+\frac{33}{32}\lVert x\rVert^2 \tag*{(32)} R ( x ) = − q 1 ( x 1 ) − j = 2 ∑ T G ( q j − 1 ( x j − 1 ) ) ( q j ( x j ) + 1 ) + 32 33 ∥ x ∥ 2 (32)
is independent of ϱ \varrho ϱ , whereas component derivatives scale as 1 / ϱ 1/\varrho 1/ ϱ . Appendix D.2 and the scaling relations
sup x ∥ ∇ 3 R ( x ) ∥ ≤ ℓ 3 ≤ 1.23 × 10 9 , α β 2 = L ϱ 341 , α β = 8 ε χ , \sup_x\lVert\nabla^3R(x)\rVert\leq\ell_3\leq1.23\times10^9,\qquad\alpha\beta^2=\frac{L\varrho}{341},\qquad\alpha\beta=\frac{8\varepsilon}{\chi}, x sup ∥ ∇ 3 R ( x )∥ ≤ ℓ 3 ≤ 1.23 × 1 0 9 , α β 2 = 341 L ϱ , α β = χ 8 ε ,
where χ = 0.279247 … \chi=0.279247\ldots χ = 0.279247 … is from Peng et al. [18 Lemma A.6] , give
Lip ( ∇ 2 1 n ∑ i f i ) ≤ α β 3 ℓ 3 = ( α β 2 ) 2 α β ℓ 3 ≤ c H L 2 n ε , c H = ( 17 / 16 ) 2 χ ℓ 3 8 ⋅ 341 2 < 414. (33) \operatorname{Lip}\left(\nabla^2\frac{1}{n}\sum_i f_i\right)\leq\alpha\beta^3\ell_3=\frac{(\alpha\beta^2)^2}{\alpha\beta}\ell_3\leq c_H\frac{L^2}{n\varepsilon},\qquad c_H=\frac{(17/16)^2\chi\ell_3}{8\cdot341^2}<414. \tag*{(33)} Lip ( ∇ 2 n 1 i ∑ f i ) ≤ α β 3 ℓ 3 = α β ( α β 2 ) 2 ℓ 3 ≤ c H n ε L 2 , c H = 8 ⋅ 34 1 2 ( 17/16 ) 2 χ ℓ 3 < 414. (33)
The third derivative of the average
Lemma 9. For a unit vector u u u , the function q u ( x ) = ⟨ u , x ⟩ ( 1 + ∥ x ∥ 2 ) − 1 / 2 q_u(x)=\langle u,x\rangle(1+\lVert x\rVert^2)^{-1/2} q u ( x ) = ⟨ u , x ⟩ ( 1 + ∥ x ∥ 2 ) − 1/2 satisfies sup x ∥ D 3 q u ( x ) ∥ = 3 \sup_x\lVert D^3q_u(x)\rVert=3 sup x ∥ D 3 q u ( x )∥ = 3 , with equality at x = 0 x=0 x = 0 .
Proof. For a unit vector h h h , put S = 1 + ∥ x ∥ 2 S=1+\lVert x\rVert^2 S = 1 + ∥ x ∥ 2 and c = ⟨ x , h ⟩ c=\langle x,h\rangle c = ⟨ x , h ⟩ . Differentiation gives D 3 q u ( x ) [ h , h , h ] = ⟨ u , V ⟩ D^3q_u(x)[h,h,h]=\langle u,V\rangle D 3 q u ( x ) [ h , h , h ] = ⟨ u , V ⟩ , where
V = x ( 9 c S − 5 / 2 − 15 c 3 S − 7 / 2 ) + h ( − 3 S − 3 / 2 + 9 c 2 S − 5 / 2 ) . V=x\left(9cS^{-5/2}-15c^3S^{-7/2}\right)+h\left(-3S^{-3/2}+9c^2S^{-5/2}\right). V = x ( 9 c S − 5/2 − 15 c 3 S − 7/2 ) + h ( − 3 S − 3/2 + 9 c 2 S − 5/2 ) .
Writing x = c h + w x=ch+w x = c h + w , w ⊥ h w\perp h w ⊥ h , z = c 2 / S z=c^2/S z = c 2 / S , and e = ∥ w ∥ 2 / S e=\lVert w\rVert^2/S e = ∥ w ∥ 2 / S , we have z , e ≥ 0 z,e\geq0 z , e ≥ 0 , z + e < 1 z+e<1 z + e < 1 , and
∥ V ∥ 2 9 = ( 1 − z − e ) 3 [ ( − 1 + 6 z − 5 z 2 ) 2 + z e ( 3 − 5 z ) 2 ] ≤ ( 1 − z ) 4 ( 5 z 2 − 2 z + 1 ) ≤ 1. \frac{\lVert V\rVert^2}{9}=(1-z-e)^3\left[(-1+6z-5z^2)^2+ze(3-5z)^2\right]\leq(1-z)^4(5z^2-2z+1)\leq1. 9 ∥ V ∥ 2 = ( 1 − z − e ) 3 [ ( − 1 + 6 z − 5 z 2 ) 2 + z e ( 3 − 5 z ) 2 ] ≤ ( 1 − z ) 4 ( 5 z 2 − 2 z + 1 ) ≤ 1.
The last function is nonincreasing on [ 0 , 1 ] [0,1] [ 0 , 1 ] , with derivative − 2 ( 1 − z ) 3 ( 15 z 2 − 10 z + 3 ) -2(1-z)^3(15z^2-10z+3) − 2 ( 1 − z ) 3 ( 15 z 2 − 10 z + 3 ) . Banach’s theorem for symmetric multilinear forms identifies the norm with the supremum over diagonal unit inputs.
Lemma 10 (Third derivative of the dense-weak-hiding average). The average (31) satisfies sup x ∥ ∇ 3 R ( x ) ∥ ≤ ℓ 3 \sup_x\lVert\nabla^3R(x)\rVert\leq\ell_3 sup x ∥ ∇ 3 R ( x )∥ ≤ ℓ 3 with ℓ 3 ≤ 1.2212 × 10 9 \ell_3\leq1.2212\times10^9 ℓ 3 ≤ 1.2212 × 1 0 9 , independently of n n n , ϱ \varrho ϱ , T T T , and D D D .
Proof. Put Q k = sup x , u ∥ ∇ k q u ( x ) ∥ Q_k = \sup_{x,u}\|\nabla^k q_u(x)\| Q k = sup x , u ∥ ∇ k q u ( x ) ∥ and M k = ∥ G ( k ) ∥ ∞ M_k = \|G^{(k)}\|_\infty M k = ∥ G ( k ) ∥ ∞ . By [18 Lemma A.4] , Lemma 9, and [18 Lemma A.1] ,
Q 1 ≤ 1 , Q 2 ≤ 2 , Q 3 = 3 , M 1 ≤ 17 , M 2 ≤ 259. Q_1 \le1,\quad Q_2 \le2,\quad Q_3 = 3,\quad M_1 \le17,\quad M_2 \le259. Q 1 ≤ 1 , Q 2 ≤ 2 , Q 3 = 3 , M 1 ≤ 17 , M 2 ≤ 259.
For G ( s ) = H 0 ( 8 s − 5 / 4 ) G(s) = H_0(8s - 5/4) G ( s ) = H 0 ( 8 s − 5/4 ) , its derivative is a convolution of a triangular density with the normalized bump ϕ g \phi_g ϕ g of half-width d g = 1 / 512 d_g = 1/512 d g = 1/512 [18 Equations (43)–(46)] . The density’s distributional second derivative has point masses with weights 4 / w g 2 4/w_g^2 4/ w g 2 , − 8 / w g 2 -8/w_g^2 − 8/ w g 2 , 4 / w g 2 4/w_g^2 4/ w g 2 , where w g = 255 / 256 w_g = 255/256 w g = 255/256 . The translated bumps are disjoint, hence
M 3 = 512 ⋅ 8 w g − 2 ∥ ϕ g ∥ ∞ . M_3 = 512 \cdot8w_g^{-2}\|\phi_g\|_\infty. M 3 = 512 ⋅ 8 w g − 2 ∥ ϕ g ∥ ∞ .
For a g = ( 1 − 16 d g 2 ) − 1 a_g = (1 - 16d_g^2)^{-1} a g = ( 1 − 16 d g 2 ) − 1 , normalization yields
∥ ϕ g ∥ ∞ − 1 = d g 2 ∫ − 1 / d g 1 / d g exp ( − t 2 1 − d g 2 t 2 ) d t ≥ d g 2 ∫ − 4 4 e − a g t 2 d t ≥ d g 2 ( π a g − e − 16 a g 4 a g ) , \|\phi_g\|_\infty^{-1} = d_g^2 \int_{-1/d_g}^{1/d_g} \exp\left(-\frac{t^2}{1-d_g^2t^2}\right)\,dt \ge d_g^2\int_{-4}^{4}e^{-a_gt^2}\,dt \ge d_g^2\left(\sqrt{\frac{\pi}{a_g}}-\frac{e^{-16a_g}}{4a_g}\right), ∥ ϕ g ∥ ∞ − 1 = d g 2 ∫ − 1/ d g 1/ d g exp ( − 1 − d g 2 t 2 t 2 ) d t ≥ d g 2 ∫ − 4 4 e − a g t 2 d t ≥ d g 2 ( a g π − 4 a g e − 16 a g ) ,
using the Gaussian-tail bound 2 ∫ 4 ∞ e − a g t 2 d t ≤ e − 16 a g / ( 4 a g ) 2\int_4^\infty e^{-a_gt^2}\,dt \le e^{-16a_g}/(4a_g) 2 ∫ 4 ∞ e − a g t 2 d t ≤ e − 16 a g / ( 4 a g ) . Thus ∥ ϕ g ∥ ∞ < 147904 \|\phi_g\|_\infty< 147904 ∥ ϕ g ∥ ∞ < 147904 and M 3 < 6.10576 × 10 8 M_3 < 6.10576 \times10^8 M 3 < 6.10576 × 1 0 8 .
For A j = g ( x j − 1 ) p ( x j ) A_j = g(x_{j-1})p(x_j) A j = g ( x j − 1 ) p ( x j ) , with g = G ∘ q j − 1 g = G \circ q_{j-1} g = G ∘ q j − 1 and p = q j + 1 ∈ ( 0 , 2 ) p = q_j + 1 \in(0,2) p = q j + 1 ∈ ( 0 , 2 ) , put r j = ∥ h j ∥ r_j = \|h_j\| r j = ∥ h j ∥ and
γ 1 = M 1 Q 1 , γ 2 = M 2 Q 1 2 + M 1 Q 2 , γ 3 = M 3 Q 1 3 + 3 M 2 Q 1 Q 2 + M 1 Q 3 . \gamma_1 = M_1Q_1,\qquad\gamma_2 = M_2Q_1^2 + M_1Q_2,\qquad\gamma_3 = M_3Q_1^3 + 3M_2Q_1Q_2 + M_1Q_3. γ 1 = M 1 Q 1 , γ 2 = M 2 Q 1 2 + M 1 Q 2 , γ 3 = M 3 Q 1 3 + 3 M 2 Q 1 Q 2 + M 1 Q 3 .
Then
∣ D 3 A j [ h , h , h ] ∣ ≤ 2 γ 3 r j − 1 3 + 3 γ 2 Q 1 r j − 1 2 r j + 3 γ 1 Q 2 r j − 1 r j 2 + Q 3 r j 3 . |D^3 A_j[h,h,h]| \le2\gamma_3r_{j-1}^3 + 3\gamma_2Q_1r_{j-1}^2r_j + 3\gamma_1Q_2r_{j-1}r_j^2 + Q_3r_j^3. ∣ D 3 A j [ h , h , h ] ∣ ≤ 2 γ 3 r j − 1 3 + 3 γ 2 Q 1 r j − 1 2 r j + 3 γ 1 Q 2 r j − 1 r j 2 + Q 3 r j 3 .
Using a 2 b ≤ ( 2 a 3 + b 3 ) / 3 a^2b \le(2a^3+b^3)/3 a 2 b ≤ ( 2 a 3 + b 3 ) /3 and a b 2 ≤ ( a 3 + 2 b 3 ) / 3 ab^2 \le(a^3+2b^3)/3 a b 2 ≤ ( a 3 + 2 b 3 ) /3 , and counting each r k r_k r k in at most two links, gives
∣ D 3 R [ h , h , h ] ∣ ≤ ℓ 3 ∑ k r k 3 ≤ ℓ 3 , ℓ 3 = 2 γ 3 + 3 γ 2 Q 1 + 3 γ 1 Q 2 + Q 3 . |D^3 R[h,h,h]| \le\ell_3\sum_k r_k^3 \le\ell_3,\qquad\ell_3 = 2\gamma_3 + 3\gamma_2Q_1 + 3\gamma_1Q_2 + Q_3. ∣ D 3 R [ h , h , h ] ∣ ≤ ℓ 3 k ∑ r k 3 ≤ ℓ 3 , ℓ 3 = 2 γ 3 + 3 γ 2 Q 1 + 3 γ 1 Q 2 + Q 3 .
This constant includes the contribution Q 3 r 1 3 Q_3r_1^3 Q 3 r 1 3 of − q 1 -q_1 − q 1 ; the quadratic contributes zero. Banach’s theorem converts the diagonal bound to the operator norm.
Lemma 11 (Finite-order replies). The conclusion of Peng et al. [18 Theorem 3.1] holds when every call returns all derivatives of f i f_i f i at the query point up to any fixed finite order.
Proof. Conditions (R2)–(R3) of Peng et al. [18 Corollary B.6] require non-completing replies to depend only on the history and queried rows of the current stage, with no contribution from unopened links. Since G ( r ) ( s ) = 0 G^{(r)}(s) = 0 G ( r ) ( s ) = 0 for r ≥ 0 r \ge0 r ≥ 0 and s ≤ 5 / 32 s \le5/32 s ≤ 5/32 , all derivatives of unopened links vanish at query points whose omitted gate inputs lie below the threshold. Completion precedes the reply, so Lemma B.4, Theorem B.5, and Corollary B.6 of that work apply. This concerns finite-order derivatives at the query point, not local germs: a flat gate need not vanish on a neighborhood of its threshold. The auxiliary Ω ( n ) \Omega(n) Ω ( n ) instance [18 Appendix C.5] is quadratic.
Proposition 4 (General form of the low-accuracy lower bound). There are universal constants n 0 , c d > 0 n_0,c_d > 0 n 0 , c d > 0 such that, for n ≥ n 0 n \ge n_0 n ≥ n 0 and ε 2 ≤ c d Δ L e f f \varepsilon^2 \le c_d\Delta L_{\mathrm{eff}} ε 2 ≤ c d Δ L eff with L e f f = min { L , ( n ρ ε / c H ) 1 / 2 } L_{\mathrm{eff}} = \min\{L,(n\rho\varepsilon/c_H)^{1/2}\} L eff = min { L , ( n ρε / c H ) 1/2 } and c H c_H c H as in (33) , every randomized algorithm needs
Ω ( n + min { n L Δ ε − 2 , n ρ 1 / 2 Δ ε − 3 / 2 } ) \Omega\left(n + \min\left\{\sqrt{n}\,L\Delta\varepsilon^{-2},\,n\rho^{1/2}\Delta\varepsilon^{-3/2}\right\}\right) Ω ( n + min { n L Δ ε − 2 , n ρ 1/2 Δ ε − 3/2 } )
queries on F I S ( n , L , ρ , Δ ) \mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta) F IS ( n , L , ρ , Δ ) , even when calls return full component Hessians. Below the crossover ε < L 2 / ( n ρ ) \varepsilon< L^2/(n\rho) ε < L 2 / ( n ρ ) , the initialization condition of Theorem 6 ensures the gap condition for a sufficiently large universal C 0 C_0 C 0 . For the terms proportional to Δ \Delta Δ , the ratio of the FastCubic upper rate to the displayed full-Hessian lower rate is, up to logarithmic factors, of order ( n ρ ε ) 1 / 2 / L (n\rho\varepsilon)^{1/2}/L ( n ρε ) 1/2 / L when ε ≥ L 2 / ( n ρ ) \varepsilon\ge L^2/(n\rho) ε ≥ L 2 / ( n ρ ) and of order ( L 2 / ( n ρ ε ) ) 1 / 4 (L^2/(n\rho\varepsilon))^{1/4} ( L 2 / ( n ρε ) ) 1/4 when ε ≤ L 2 / ( n ρ ) \varepsilon\le L^2/(n\rho) ε ≤ L 2 / ( n ρ ) . The additive n n n term can reduce the ratio of the total query bounds.
Proof of the lower bound in Theorem 5
Proof. Apply Peng et al. [18 Theorem 3.1] and Lemma 11 with L e f f = min { L , ( n ρ ε / c H ) 1 / 2 } L_{\mathrm{eff}}=\min\{L,(n\rho\varepsilon/c_H)^{1/2}\} L eff = min { L , ( n ρε / c H ) 1/2 } . The instance is individually L e f f L_{\mathrm{eff}} L eff -smooth, and (33) gives Lip ( ∇ 2 f ) ≤ c H L e f f 2 / ( n ε ) ≤ ρ \operatorname{Lip}(\nabla^2 f)\le c_H L_{\mathrm{eff}}^2/(n\varepsilon)\le\rho Lip ( ∇ 2 f ) ≤ c H L eff 2 / ( n ε ) ≤ ρ . For n ≥ n 0 n\ge n_0 n ≥ n 0 and ε 2 ≤ c d Δ L e f f \varepsilon^2\le c_d\Delta L_{\mathrm{eff}} ε 2 ≤ c d Δ L eff , the resulting lower bound is
Ω ( n + n L e f f Δ ε − 2 ) = Ω ( n + min { n L Δ ε − 2 , n ρ 1 / 2 Δ ε − 3 / 2 } ) . \Omega\left(n+\sqrt{n}L_{\mathrm{eff}}\Delta\varepsilon^{-2}\right)=\Omega\left(n+\min\left\{\sqrt{n}L\Delta\varepsilon^{-2},n\rho^{1/2}\Delta\varepsilon^{-3/2}\right\}\right). Ω ( n + n L eff Δ ε − 2 ) = Ω ( n + min { n L Δ ε − 2 , n ρ 1/2 Δ ε − 3/2 } ) .
In the low-accuracy regime, L e f f ≥ L / c H L_{\mathrm{eff}}\ge L/\sqrt{c_H} L eff ≥ L / c H , so c 3 ≤ c d / c H c_3\le c_d/\sqrt{c_H} c 3 ≤ c d / c H ensures the gap condition. Below the crossover, it is equivalent to
ρ 1 / 2 Δ ε − 3 / 2 ≥ c H c d n . \rho^{1/2}\Delta\varepsilon^{-3/2}\ge\frac{\sqrt{c_H}}{c_d\sqrt{n}}. ρ 1/2 Δ ε − 3/2 ≥ c d n c H .
which follows from Theorem 6’s initialization condition for sufficiently large universal C 0 C_0 C 0 . Both source instances also satisfy averaged smoothness [18 Corollary 3.2] . This proves Proposition 4 and the lower bound in Theorem 5.
Proofs for Section 6
Proofs of Theorems 6 and 7
Proof. Theorems 3 and 4 give the lower bounds. For the upper bound, apply Theorem 2 and use
n ρ 1 / 2 Δ ε − 3 / 2 ≤ c 0 1 / 4 n 3 / 4 L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 , ε ≤ c 0 L 2 / ( n ρ ) . n\rho^{1/2}\Delta\varepsilon^{-3/2}\le c_0^{1/4}n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4},\qquad\varepsilon\le c_0L^2/(n\rho). n ρ 1/2 Δ ε − 3/2 ≤ c 0 1/4 n 3/4 L 1/2 ρ 1/4 Δ ε − 7/4 , ε ≤ c 0 L 2 / ( n ρ ) .
The condition ρ 1 / 2 Δ ε − 3 / 2 ≥ C 0 \rho^{1/2}\Delta\varepsilon^{-3/2}\ge C_0 ρ 1/2 Δ ε − 3/2 ≥ C 0 absorbs initialization and one cubic subproblem. The individual-smoothness upper bound follows from F I S ⊆ F A S \mathcal{F}_{\mathrm{IS}}\subseteq\mathcal{F}_{\mathrm{AS}} F IS ⊆ F AS .
Proof of Proposition 2
Proof. Proposition 4 gives the lower bound. Cubic regularization [15 ] and PathVR give O ( n + n ρ 1 / 2 Δ ε − 3 / 2 ) O(n+n\rho^{1/2}\Delta\varepsilon^{-3/2}) O ( n + n ρ 1/2 Δ ε − 3/2 ) and O ~ ( n + n L Δ ε − 2 ) \widetilde{O}(n+\sqrt{n}L\Delta\varepsilon^{-2}) O ( n + n L Δ ε − 2 ) , respectively. Taking the smaller bound proves the claim.
Proof of Proposition 3
Proof. Take n = 1 n=1 n = 1 , τ s = 1 + ( s − 1 ) m \tau_s=1+(s-1)m τ s = 1 + ( s − 1 ) m , and σ s = 1 + s m \sigma_s=1+sm σ s = 1 + s m . By Lemma 8, before σ s \sigma_s σ s the latent queries lie in V s + span { u s , … , Λ m − 1 u s } V_s+\operatorname{span}\{u_s,\ldots,\Lambda^{m-1}u_s\} V s + span { u s , … , Λ m − 1 u s } . The projection estimate keeps every predecessor gate flat, so no point queried before 1 + N m 1+Nm 1 + N m is ε \varepsilon ε -stationary. As in the proof of Theorem 4, the terminal output is one passive exposure at round Q + 1 < 1 + N m Q+1<1+Nm Q + 1 < 1 + N m for a budget Q < N m Q<Nm Q < N m , so it obeys the same projection bound. Equation (27) with L ⋆ = L L_\star=L L ⋆ = L gives Ω ( N m ) = Ω ( L 1 / 2 ρ 1 / 4 Δ ε − 7 / 4 ) \Omega(Nm)=\Omega(L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}) Ω ( N m ) = Ω ( L 1/2 ρ 1/4 Δ ε − 7/4 ) .