Introduction
A component gradient may be expensive to evaluate even when a useful approximation is available. If that approximation is exact for most components, repeated evaluations of those components are unnecessary. The difficulty is to identify the exceptions. A gradient prediction can agree with the true gradient at every point queried so far and still differ elsewhere. Agreement at finitely many points therefore does not establish that the two gradients agree everywhere.
We consider
min x ∈ R d F ( x ) , F ( x ) = 1 n ∑ i = 1 n f i ( x ) = h ( x ) + 1 n ∑ i = 1 n u i ( x ) . (1) \min_{x\in\mathbb{R}^d} F(x), \qquad F(x)=\frac{1}{n}\sum_{i=1}^{n}f_i(x)=h(x)+\frac{1}{n}\sum_{i=1}^{n}u_i(x). \tag*{(1)} x ∈ R d min F ( x ) , F ( x ) = n 1 i = 1 ∑ n f i ( x ) = h ( x ) + n 1 i = 1 ∑ n u i ( x ) . (1)
For component i i i , a known differentiable function p i p_i p i predicts the gradient through ∇ p i \nabla p_i ∇ p i . Write h = n − 1 ∑ i p i h=n^{-1}\sum_i p_i h = n − 1 ∑ i p i , u i = f i − p i u_i=f_i-p_i u i = f i − p i , and r i = ∇ u i r_i=\nabla u_i r i = ∇ u i . We call u i u_i u i the residual function and r i r_i r i its residual gradient. At most k k k residual gradients are nonzero as functions; their coordinates need not be sparse. One query returns ∇ f i ( x ) \nabla f_i(x) ∇ f i ( x ) at a chosen index and point. Subtracting the known ∇ p i ( x ) \nabla p_i(x) ∇ p i ( x ) gives r i ( x ) r_i(x) r i ( x ) . Predictor evaluations are not counted. Every component retains weight 1 / n 1/n 1/ n , including after an exception is found.
We assume that F F F is smooth, its initial gap is at most F 0 F_0 F 0 , and
∑ i ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ k δ 2 ∥ x − y ∥ 2 , ∑ i osc ( u i ) ≤ 2 n F 0 . \sum_i \lVert r_i(x)-r_i(y)\rVert^2 \le k\delta^2\lVert x-y\rVert^2,\qquad\sum_i \operatorname{osc}(u_i)\le2nF_0. i ∑ ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ k δ 2 ∥ x − y ∥ 2 , i ∑ osc ( u i ) ≤ 2 n F 0 .
Here osc ( u i ) = sup u i − inf u i \operatorname{osc}(u_i)=\sup u_i-\inf u_i osc ( u i ) = sup u i − inf u i . This bound limits the change in the partial objective when a newly discovered residual function is added. It is a global assumption in addition to gradient or Hessian similarity. The individual oscillations and the exceptional indices are unknown. We compare optimization when these indices are supplied with optimization when the algorithm must find them.
Contributions
The cost of unknown exceptional indices For the parameter range in Theorem 2.2 , we establish
Θ ( min { n k + R , n k R } ) , R = k 3 / 2 δ F 0 n ϵ 2 . \Theta\left(\min\left\{nk+\mathcal{R},\frac{n}{k}\mathcal{R}\right\}\right), \qquad\mathcal{R}=\frac{k^{3/2}\delta F_0}{n\epsilon^2}. Θ ( min { nk + R , k n R } ) , R = n ϵ 2 k 3/2 δ F 0 .
The theorem covers ϵ 2 ≤ δ F 0 k / ( 4 n ) \epsilon^2\le\delta F_0\sqrt{k}/(4n) ϵ 2 ≤ δ F 0 k / ( 4 n ) . The terms change order at the scales k 2 k^2 k 2 and n k nk nk in R \mathcal{R} R . When n n n is much larger than k k k , these distinguish sampling the population, finding exceptions, and optimizing their sum. If n = k n=k n = k , supplying the indices does not improve the order. The explicit lower-bound constants are conservative and do not identify numerical crossover points. If the exceptional indices are supplied, the order reduces to Θ ( R ) \Theta(\mathcal{R}) Θ ( R ) . Table 1 specifies the information supplied and the queries counted in each comparison.
Table 1. Query bounds under the parameter range of Theorem 2.2. Supplied indices are known before any query. The smooth rows give matching lower and upper bounds; the analytic row gives the upper bound of Proposition 5.2. All component-gradient evaluations are counted.
Algorithms and stopping rules We estimate either the full residual gradient sum or its sum over a growing set of discovered exceptions, called the working set. After recomputing the working-set sum exactly, we check the full gradient if the gradient of the partial objective is small. A failed check adds at least one exception; a successful check returns a point with gradient norm at most ϵ \epsilon ϵ . There are at most k k k failed checks. A common potential is nonincreasing when the working set expands and satisfies a descent estimate during optimization. We bound the estimator error up to the random stopping time to obtain the expected query count. Sampling several differences per iteration permits stepsizes determined by smoothness alone, while retaining the same order of query cost. For sampling from all components or from a supplied exceptional set, we also prove that the algorithm may stop at the first successful exact gradient check. The adaptive method in Theorem 3.3 uses the number of discovered components to choose its expected batch size and omits differences that an exact recomputation would replace. Its bound depends on the actual support size k ∗ k_* k ∗ and the number D D D of checks that discover new components:
E Q ≤ ( n + 2 k ∗ ) ( E D + 1 ) + 8 k ∗ k δ ( F 0 + Ω ) n ϵ 2 . \mathbb{E}Q\le(n+2k_*)(\mathbb{E}D+1)+\frac{8k_*\sqrt{k}\delta(F_0+\Omega)}{n\epsilon^2}. E Q ≤ ( n + 2 k ∗ ) ( E D + 1 ) + n ϵ 2 8 k ∗ k δ ( F 0 + Ω ) .
Neither k ∗ k_* k ∗ nor D D D is supplied to the method.
Lower bounds and classes with simpler identification We combine an optimization lower bound with smooth functions whose successive informative gradients belong to components with unknown indices. Independent copies give the accuracy-dependent discovery bound. An interrupted-search inequality permits arbitrary interleaving of those copies, including chains of length one. Convex objectives with bounded sinusoidal residuals cover the remaining accuracy range. The bounds allow query points and indices to depend on previous observations, and the output need not have been queried. For real analytic residuals, querying each component at one independently sampled point identifies all exceptions almost surely, giving an O ( n + R ) O(n+\mathcal{R}) O ( n + R ) upper bound. We also construct predictors with O ( n ) O(n) O ( n ) queries under a finite-dimensional mixture assumption. Our numerical comparisons include exceptions that first become visible at successive partial stationary points. Every competitive baseline may use the exceptional indices that its own queries identify; supplied-support methods are reported separately.
Related work
Working-set methods alternate optimization over a restricted set of variables and checks of the full optimality conditions [1 , 2 , 3 , 4 ] . Our working set records component indices whose residual gradients have been observed to be nonzero. Those gradients may vanish at earlier query points. A bound on the sum of their oscillations controls changes of the partial objective as this set grows.
PAGE, SPIDER, and MARINA alternate exact gradient recomputations with updates based on sampled gradient differences [5 , 6 , 7 ] . We use this estimator structure and also account for queries used to find the exceptional components and check the full gradient. On a known set of m m m components, the residual estimator has mean-square smoothness parameter δ m k / n \delta\sqrt{mk}/n δ mk / n ; applying the usual variance-reduction balance gives the optimization term in our upper bound. Our additional analysis concerns the changing partial objective, the queries used to discover exceptions, and termination after an exact check. Similarity-based methods exploit small differences between component gradient increments [8 , 9 , 10 ] . Jiang, Rodomanov, and Stich [11 ] study functional similarity while assigning different costs to arbitrary, random, and delegated component selection. Their bounds concern communication and local computation. We count exact component-gradient evaluations. We assume that residual gradients vanish identically outside a small exceptional set and bound the sum of the residual oscillations. Predictor evaluations are not counted. These assumptions specify both the function class and the cost measured by our comparison.
The lower bounds use smooth chains and random rotations [12 , 6 ] , together with searches for informative component indices. Han, Xie, and Zhang [13 ] study component proximal queries with restrictions on sampling and on the span of allowable query points. Arjevani et al. [14 ] use searches over random seeds to obtain informative gradient observations. Our bounds allow arbitrary adaptive component-gradient queries and compare known and unknown exceptional indices within the same function class. Recent preprints also study adaptive information acquisition in finite sums. Zhou [19 ] assigns successive chain edges to random components in lower bounds for approximate local minima. Peng, Tang, and Jia [20 ] distribute hidden information across components to obtain lower bounds under individual smoothness. Our use of unknown component indices is related to these constructions. The distinction is the comparison between supplied and unknown indices under exact residual sparsity and a bound on residual oscillations; neither of those papers states that comparison.
Model and complexity statement
For each differentiable component f i : R d → R f_i:\mathbb{R}^d \to\mathbb{R} f i : R d → R , let p i : R d → R p_i:\mathbb{R}^d \to\mathbb{R} p i : R d → R be a known differentiable function whose gradient predicts ∇ f i \nabla f_i ∇ f i . Define
h = 1 n ∑ i p i , u i = f i − p i , r i = ∇ u i , F = h + 1 n ∑ i u i . h = \frac{1}{n}\sum_i p_i,\qquad u_i = f_i-p_i,\qquad r_i = \nabla u_i,\qquad F = h + \frac{1}{n}\sum_i u_i. h = n 1 i ∑ p i , u i = f i − p i , r i = ∇ u i , F = h + n 1 i ∑ u i .
The exceptional set, also called the support of the residual gradients, is B = { i : r i ≠ 0 } \mathcal{B} = \{i:r_i \ne0\} B = { i : r i = 0 } . Even for i ∈ B i \in\mathcal{B} i ∈ B , r i r_i r i may vanish at all points queried so far. A constant residual function affects neither the gradient nor the objective gap. All vector norms are Euclidean, and matrix operator norms are induced by them.
Assumption 2.1 (Objective and sparse residuals). The supplied constants L , F 0 , δ > 0 L, F_0, \delta> 0 L , F 0 , δ > 0 , Ω > 0 \Omega> 0 Ω > 0 and 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n satisfy F ( x 0 ) − inf F ≤ F 0 F(x_0)-\inf F \le F_0 F ( x 0 ) − inf F ≤ F 0 , ∇ F \nabla F ∇ F is L L L -Lipschitz, and ∣ B ∣ ≤ k |\mathcal{B}| \le k ∣ B ∣ ≤ k . Writing W i = sup u i − inf u i W_i = \sup u_i-\inf u_i W i = sup u i − inf u i , assume
1 n ∑ i ∈ B W i ≤ Ω , (2) \frac{1}{n}\sum_{i\in\mathcal{B}} W_i \le\Omega, \tag*{(2)} n 1 i ∈ B ∑ W i ≤ Ω , (2)
and, for all x , y ∈ R d x,y \in\mathbb{R}^{d} x , y ∈ R d ,
∑ i ∈ B ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ k δ 2 ∥ x − y ∥ 2 . (3) \sum_{i\in B} \lVert r_i(x)-r_i(y)\rVert^2 \le k\delta^2\lVert x-y\rVert^2. \tag*{(3)} i ∈ B ∑ ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ k δ 2 ∥ x − y ∥ 2 . (3)
The individual W i W_i W i and the set B B B are not supplied.
Condition (3) permits an individual residual gradient to have Lipschitz constant as large as δ k \delta\sqrt{k} δ k . Condition (2.1) bounds changes of the partial objective. Both conditions apply to all points. They cannot be established solely by observing that gradient predictions agree with queried gradients at finitely many points. Section 5 gives assumptions under which finitely many queries determine the predictors.
Queries and the required output A query selects an index i i i and a point x x x and returns the exact vector ∇ f i ( x ) \nabla f_i(x) ∇ f i ( x ) . We do not count predictor evaluations or other computation. Evaluating a residual gradient difference at two points costs two queries. The count includes all component evaluations used to construct predictors or check the output. We denote the cost of constructing predictors, when needed, by C c a l C_{\mathrm{cal}} C cal . If a component averages data losses, one query may require evaluating the gradient on every example in that component.
Algorithms may randomize. They may choose indices and points using all previous responses, with no bound on the norm of a query point, and return a point that has never been queried. An admissible algorithm terminates almost surely and satisfies E ∥ ∇ F ( x ^ ) ∥ 2 ≤ ϵ 2 \mathbb{E}\lVert\nabla F(\widehat{x})\rVert^2 \le\epsilon^2 E ∥ ∇ F ( x ) ∥ 2 ≤ ϵ 2 on every instance. For each algorithm, take the supremum of its expected query count over all instances and finite dimensions. The infimum of this quantity over admissible algorithms is the minimax query cost. Our algorithms satisfy the stronger condition ∥ ∇ F ( x ^ ) ∥ ≤ ϵ \lVert\nabla F(\widehat{x})\rVert\le\epsilon ∥ ∇ F ( x )∥ ≤ ϵ , verified by an exact gradient check before returning. When the exceptional set is supplied before any query, this check requires only gradients from that set.
Reduction to a common reference function The transformed components f ~ i = h + f i − p i = h + u i \widetilde{f}_i=h+f_i-p_i=h+u_i f i = h + f i − p i = h + u i have the same average F F F . One query to f i f_i f i gives a gradient of f ~ i \widetilde{f}_i f i through ∇ f ~ i = ∇ f i − ∇ p i + ∇ h \nabla\widetilde{f}_i=\nabla f_i-\nabla p_i+\nabla h ∇ f i = ∇ f i − ∇ p i + ∇ h . The reverse calculation also uses one query. The residual gradients, exceptional set, smoothness bounds, and oscillations are unchanged. We may therefore use f i = h + u i f_i=h+u_i f i = h + u i in the analysis even when the original predictors differ.
Theorem 2.2 (Query complexity with unknown and supplied exceptional indices). Let 16 ≤ k ≤ n 16 \le k \le n 16 ≤ k ≤ n be integers, δ , F 0 > 0 \delta, F_0 > 0 δ , F 0 > 0 , and
L 0 = δ k n , L ≥ L 0 , c 0 = 1 4 . L_0 = \frac{\delta\sqrt{k}}{n}, \qquad L \ge L_0, \qquad c_0 = \frac{1}{4}. L 0 = n δ k , L ≥ L 0 , c 0 = 4 1 . Consider the class in Assumption 2.1 with Ω = 2 F 0 \Omega= 2F_0 Ω = 2 F 0 , using the queries and output requirement defined above. The reference function is supplied. If constructing it instead costs O ( n ) O(n) O ( n ) queries, this cost does not change the order of the bound for unknown exceptional indices. For
0 < ϵ 2 ≤ c 0 δ F 0 k n , R = k 3 / 2 δ F 0 n ϵ 2 , P = k δ F 0 ϵ 2 = n k R , 0 < \epsilon^2 \le c_0 \frac{\delta F_0\sqrt{k}}{n}, \qquad\mathcal{R} = \frac{k^{3/2}\delta F_0}{n\epsilon^2}, \qquad\mathcal{P} = \frac{\sqrt{k}\delta F_0}{\epsilon^2} = \frac{n}{k}\mathcal{R}, 0 < ϵ 2 ≤ c 0 n δ F 0 k , R = n ϵ 2 k 3/2 δ F 0 , P = ϵ 2 k δ F 0 = k n R , the minimax expected query complexity with unknown exceptional indices is
Θ ( min { n k + R , P } ) = Θ ( R + min { n k , P } ) . (4) \Theta(\min\{nk+\mathcal{R},\mathcal{P}\}) = \Theta(\mathcal{R}+\min\{nk,\mathcal{P}\}). \tag*{(4)} Θ ( min { nk + R , P }) = Θ ( R + min { nk , P }) . (4) The constants are independent of n , k , L , δ , F 0 , ϵ n,k,L,\delta,F_0,\epsilon n , k , L , δ , F 0 , ϵ . The algorithm attaining the upper bound terminates almost surely and returns a point that passes an exact gradient check. The lower bound applies to every admissible algorithm defined above; the dimension of its hard instance may depend on the problem parameters.
If the exceptional set is supplied and there is no requirement to query all components to construct predictors or check the output, the complexity is Θ ( R ) \Theta(\mathcal{R}) Θ ( R ) . A requirement of n n n additional component queries changes this to Θ ( n + R ) \Theta(n+\mathcal{R}) Θ ( n + R ) .
Table 1 compares the information available to the algorithm. When the exceptional indices of smooth residuals are unknown, the bound contains the additional term min { n k , P } \min\{nk,\mathcal{P}\} min { nk , P } . Since P ≥ R \mathcal{P} \ge\mathcal{R} P ≥ R , the two expressions in (4) agree within a factor of two. The number of iterations depends on L L L . The choices of recomputation probabilities and expected batch sizes remove this dependence from the total query bounds. Sections 3 and 4 prove the upper and lower bounds, respectively.
Accuracy range For example, let n = k 2 n = k^2 n = k 2 and ϵ 2 = δ F 0 k / ( n k ) \epsilon^2 = \delta F_0\sqrt{k}/(nk) ϵ 2 = δ F 0 k / ( nk ) . Then R = k 2 \mathcal{R} = k^2 R = k 2 and P = n k = k 3 \mathcal{P} = nk = k^3 P = nk = k 3 . As k k k grows, the unknown-index cost is Θ ( k 3 ) \Theta(k^3) Θ ( k 3 ) and the supplied-index cost is Θ ( k 2 ) \Theta(k^2) Θ ( k 2 ) . The additional cost therefore exceeds the n = k 2 n = k^2 n = k 2 queries needed for a single scan.
Put G = δ F 0 k / n G = \delta F_0\sqrt{k}/n G = δ F 0 k / n . The theorem covers 0 < ϵ 2 ≤ G / 4 0 < \epsilon^2 \le G/4 0 < ϵ 2 ≤ G /4 , or equivalently R ≥ 4 k \mathcal{R} \ge4k R ≥ 4 k . The two transition scales are ϵ 2 ≍ G / k \epsilon^2 \asymp G/k ϵ 2 ≍ G / k and ϵ 2 ≍ G / n \epsilon^2 \asymp G/n ϵ 2 ≍ G / n , corresponding to R ≍ k 2 \mathcal{R} \asymp k^2 R ≍ k 2 and R ≍ n k \mathcal{R} \asymp nk R ≍ nk . The corresponding intervals fit inside the stated range when 16 ≤ k < n 16 \le k < n 16 ≤ k < n . Their separation is informative when n n n is much larger than k k k ; at n = k n = k n = k , the whole bound has order R \mathcal{R} R .
The proof uses two kinds of examples. Smooth chains establish the accuracy-dependent discovery cost at sufficiently small ϵ \epsilon ϵ . Bounded sinusoidal residuals establish linear query costs for the remaining accuracies. Combining the two gives the stated uniform order, with explicit constants in Section 4.
Those constants remain conservative: the theorem does not locate numerical crossover points for a fixed moderate n n n and k k k . Since P ≥ 4 n P \ge4n P ≥ 4 n and n k ≥ n nk \ge n nk ≥ n , adding O ( n ) O(n) O ( n ) queries to construct predictors does not change the order.
Upper bounds with bounded residual oscillation
We work under Assumption 2.1. If the predictors must be constructed from queries, their construction costs C c a l C_{\mathrm{cal}} C cal . This cost is added once to each bound in this section.
A working-set method with exact gradient checks
The working set S S S contains components whose residual gradients have been observed to be nonzero. For S ⊆ B S \subseteq\mathcal{B} S ⊆ B , define the partial objective and its residual gradient sum by
Φ S = h + 1 n ∑ i ∈ S u i , R S = 1 n ∑ i ∈ S r i , H = k δ n , Γ = F 0 + Ω . \Phi_S = h + \frac{1}{n}\sum_{i\in S}u_i,\qquad R_S = \frac{1}{n}\sum_{i\in S}r_i,\qquad\mathcal{H} = \frac{k\delta}{n},\qquad\Gamma= F_0+\Omega. Φ S = h + n 1 i ∈ S ∑ u i , R S = n 1 i ∈ S ∑ r i , H = n k δ , Γ = F 0 + Ω.
Each partial objective Φ S \Phi_S Φ S is ( L + H ) (L+\mathcal{H}) ( L + H ) -smooth. Its gradient differs from ∇ F \nabla F ∇ F by the sum of the omitted residual gradients, divided by n n n . By Cauchy–Schwarz and (3) , this difference has Lipschitz constant at most H \mathcal{H} H . Choose
η = 1 2 ( L + H ) , p = 2 η H k , τ = η H k , b = ⌈ τ ⌉ , s = τ b . (5) \begin{aligned}
\eta&= \frac{1}{2(L+\mathcal{H})},\qquad p = \frac{2\eta\mathcal{H}}{\sqrt{k}},\\
\tau&= \eta\mathcal{H}\sqrt{k},\qquad b = \lceil\tau\rceil,\qquad s = \frac{\tau}{b}. \tag*{(5)}
\end{aligned} η τ = 2 ( L + H ) 1 , p = k 2 η H , = η H k , b = ⌈ τ ⌉ , s = b τ . (5)
These parameters satisfy 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 and 0 < s ≤ 1 0 < s \le1 0 < s ≤ 1 . At each visit, we recompute R S ( x ) R_S(x) R S ( x ) exactly with probability p p p . After each executed step, we estimate its change. When S ≠ ∅ S \ne\varnothing S = ∅ , this estimate uses τ \tau τ differences of residual gradients on average. The batch size b b b allows this expected count to exceed one.
Algorithm 3.1 Working-set method with exact gradient checks
Input: x 0 , ϵ x_0,\epsilon x 0 , ϵ and ( η , p , τ , b , s ) (\eta,p,\tau,b,s) ( η , p , τ , b , s ) from (5) ; the known gradient ∇ h \nabla h ∇ h and access to queries of the residual gradients. Initialize S = ∅ S=\varnothing S = ∅ , x = x 0 x=x_0 x = x 0 , and v ˉ = 0 \bar{v}=0 v ˉ = 0 . A visit consists of one pass through the following operations. The last visit may return a point before taking a step.
Independently of the past, recompute R S ( x ) R_S(x) R S ( x ) with probability p p p by querying every i ∈ S i\in S i ∈ S , and set v = R S ( x ) v=R_S(x) v = R S ( x ) . If no recomputation is made, set v = v ˉ v=\bar{v} v = v ˉ .
If step 1 recomputed R S ( x ) R_S(x) R S ( x ) and ∥ ∇ h ( x ) + v ∥ ≤ ϵ / 2 \lVert\nabla h(x)+v\rVert\le\epsilon/2 ∥ ∇ h ( x ) + v ∥ ≤ ϵ /2 , query all components. Return x x x if ∥ ∇ F ( x ) ∥ ≤ ϵ \lVert\nabla F(x)\rVert\le\epsilon ∥ ∇ F ( x )∥ ≤ ϵ . Otherwise add every i ∉ S i\notin S i ∈ / S with r i ( x ) ≠ 0 r_i(x)\ne0 r i ( x ) = 0 to S S S and reset v = R S ( x ) v=R_S(x) v = R S ( x ) using the responses from this check.
Set x + = x − η ( ∇ h ( x ) + v ) x^+=x-\eta(\nabla h(x)+v) x + = x − η ( ∇ h ( x ) + v ) . If S = ∅ S=\varnothing S = ∅ , set v ˉ + = 0 \bar{v}^+=0 v ˉ + = 0 without a query. Otherwise, after fixing x + x^+ x + , draw mutually independent Z j ∼ Bernoulli ( s ) Z_j\sim\operatorname{Bernoulli}(s) Z j ∼ Bernoulli ( s ) and I j ∼ Uniform ( S ) I_j\sim\operatorname{Uniform}(S) I j ∼ Uniform ( S ) , j = 1 , … , b j=1,\ldots,b j = 1 , … , b . For each j j j with Z j = 1 Z_j=1 Z j = 1 , query component I j I_j I j at x x x and x + x^+ x + . Set
v ˉ + = v + 1 b ∑ j = 1 b Z j s ∣ S ∣ n ( r I j ( x + ) − r I j ( x ) ) . (6) \bar{v}^+ = v + \frac{1}{b}\sum_{j=1}^{b}\frac{Z_j}{s}\frac{|S|}{n}\left(r_{I_j}(x^+)-r_{I_j}(x)\right). \tag*{(6)} v ˉ + = v + b 1 j = 1 ∑ b s Z j n ∣ S ∣ ( r I j ( x + ) − r I j ( x ) ) . (6)
If every Z j Z_j Z j is zero, retain v v v without querying residual gradients. Set ( x , v ˉ ) = ( x + , v ˉ + ) (x,\bar{v})=(x^+,\bar{v}^+) ( x , v ˉ ) = ( x + , v ˉ + ) .
Recomputing the sum over S S S costs at most k k k queries. Each sampled difference costs two queries, and checking the full gradient costs n n n . When S ≠ ∅ S \ne\varnothing S = ∅ , the expected cost of the sampled differences is 2 b ς = 2 τ 2b\varsigma= 2\tau 2 b ς = 2 τ . Indices remain in the working set after they are added. The tests for a zero residual gradient and for the final gradient norm use exact component-gradient responses.
Theorem 3.1 (Query bound for the working-set method). Under Assumption 2.1, Algorithm 3.1 terminates almost surely and returns a point satisfying ∥ ∇ F ( x ) ∥ ≤ ϵ \lVert\nabla F(x)\rVert\le\epsilon ∥ ∇ F ( x )∥ ≤ ϵ . If V V V counts all visits, including the terminal visit, and Q Q Q counts all queries, then
E V ≤ 8 Γ η ϵ 2 + k + 1 p , (7) \mathbb{E}V \le\frac{8\Gamma}{\eta\epsilon^2}+\frac{k+1}{p}, \tag*{(7)} E V ≤ η ϵ 2 8Γ + p k + 1 , (7) E Q ≤ ( n + 2 k ) ( k + 1 ) + 32 k 3 / 2 δ Γ n ϵ 2 . (8) \mathbb{E}Q \le(n+2k)(k+1)+\frac{32k^{3/2}\delta\Gamma}{n\epsilon^2}. \tag*{(8)} E Q ≤ ( n + 2 k ) ( k + 1 ) + n ϵ 2 32 k 3/2 δ Γ . (8) In particular, if Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 and R = k 3 / 2 δ F 0 / ( n ϵ 2 ) \mathcal{R}=k^{3/2}\delta F_0/(n\epsilon^2) R = k 3/2 δ F 0 / ( n ϵ 2 ) , then E Q ≤ ( n + 2 k ) ( k + 1 ) + 96 R \mathbb{E}Q \le(n+2k)(k+1)+96\mathcal{R} E Q ≤ ( n + 2 k ) ( k + 1 ) + 96 R .
Proof. We first restrict each sum to a fixed finite number of visits. After the algorithm terminates, we set all further movements and estimator errors to zero and include no further descent terms. Whether a visit is reached is determined before deciding whether to recompute the residual gradient sum. These finite sums let us bound the expected stopping time without assuming in advance that it is finite.
A potential for all working sets Put W i = osc ( u i ) W_i=\operatorname{osc}(u_i) W i = osc ( u i ) . Add constants to the residual functions so that 0 ≤ u i ≤ W i 0 \le u_i \le W_i 0 ≤ u i ≤ W i , and subtract their average from h h h . These additive constants affect no gradient or objective gap. Define
Ψ S ( x ) = Φ S ( x ) + 1 n ∑ i ∈ B ∖ S W i . \Psi_S(x)=\Phi_S(x)+\frac{1}{n}\sum_{i\in B\setminus S}W_i. Ψ S ( x ) = Φ S ( x ) + n 1 i ∈ B ∖ S ∑ W i .
Then Ψ S ≥ F ≥ inf F \Psi_S \ge F \ge\inf F Ψ S ≥ F ≥ inf F and Ψ ∅ ( x 0 ) − inf F ≤ Γ \Psi_{\varnothing}(x_0)-\inf F\le\Gamma Ψ ∅ ( x 0 ) − inf F ≤ Γ . Adding a set A A A at a fixed point changes this potential by n − 1 ∑ i ∈ A ( u i ( x ) − W i ) ≤ 0 n^{-1}\sum_{i\in A}(u_i(x)-W_i)\le0 n − 1 ∑ i ∈ A ( u i ( x ) − W i ) ≤ 0 . Adding components therefore contributes no increase when we sum the descent inequalities. The initial difference remains bounded by Γ \Gamma Γ .
Estimator error up to termination Let e ˉ = v ˉ − R S ( x ) \bar e=\bar v-R_S(x) e ˉ = v ˉ − R S ( x ) before the recomputation decision, and let e = v − R S n e w ( x ) e=v-R_{S_{\mathrm{new}}}(x) e = v − R S new ( x ) after that decision and any addition to S S S . An exact recomputation gives e = 0 e=0 e = 0 , including on the last visit. If the sum is not recomputed, then e = e ˉ e=\bar e e = e ˉ . New components are added only when their contributions have been evaluated exactly. Conditional on the history before this decision, E ∥ e ∥ 2 = ( 1 − p ) ∥ e ˉ ∥ 2 \mathbb{E}\lVert e\rVert^2=(1-p)\lVert\bar e\rVert^2 E ∥ e ∥ 2 = ( 1 − p ) ∥ e ˉ ∥ 2 . For fixed x x x and x + x^+ x + , the sampled sum added to v v v in (3.2) is an unbiased estimate of the change in R S R_S R S . Independence of its b b b terms bounds its conditional variance by
∣ S ∣ b ς n 2 ∑ i ∈ S ∥ r i ( x + ) − r i ( x ) ∥ 2 ≤ H 2 τ ∥ x + − x ∥ 2 . \frac{|S|}{b\varsigma n^2}\sum_{i\in S}\lVert r_i(x^+)-r_i(x)\rVert^2\le\frac{\mathcal{H}^2}{\tau}\lVert x^+-x\rVert^2. b ς n 2 ∣ S ∣ i ∈ S ∑ ∥ r i ( x + ) − r i ( x ) ∥ 2 ≤ τ H 2 ∥ x + − x ∥ 2 .
The indicators Z j Z_j Z j are independent; using a single indicator for the whole batch would not give the factor 1 / b 1/b 1/ b . Subtracting the true change in R S R_S R S from the sampled sum gives an error whose inner product with e e e has conditional expectation zero. Writing a t = E ∥ e t ∥ 2 a_t=\mathbb{E}\lVert e_t\rVert^2 a t = E ∥ e t ∥ 2 and taking the movement to be zero when no step executes gives a 0 = 0 a_0=0 a 0 = 0 and
a t + 1 ≤ ( 1 − p ) a t + ( 1 − p ) H 2 τ E ∥ x t + 1 − x t ∥ 2 . a_{t+1}\le(1-p)a_t+\frac{(1-p)\mathcal{H}^2}{\tau}\mathbb{E}\lVert x^{t+1}-x^t\rVert^2. a t + 1 ≤ ( 1 − p ) a t + τ ( 1 − p ) H 2 E ∥ x t + 1 − x t ∥ 2 .
Summing this recursion over the fixed finite number of visits yields
∑ t E ∥ e t ∥ 2 ≤ C ∑ t E ∥ x t + 1 − x t ∥ 2 , C = ( 1 − p ) H 2 p τ ≤ 1 2 η 2 . (9) \sum_t \mathbb{E}\lVert e_t\rVert^2 \le C\sum_t \mathbb{E}\lVert x^{t+1}-x^t\rVert^2,\qquad C=\frac{(1-p)\mathcal{H}^2}{p\tau}\le\frac{1}{2\eta^2}. \tag*{(9)} t ∑ E ∥ e t ∥ 2 ≤ C t ∑ E ∥ x t + 1 − x t ∥ 2 , C = p τ ( 1 − p ) H 2 ≤ 2 η 2 1 . (9)
The recursion is conditioned only on the history available before each draw.
Descent and the number of visits. For an executed step, smoothness and the identity x + − x = − η ( ∇ Φ S ( x ) + e ) x^+-x=-\eta(\nabla\Phi_S(x)+e) x + − x = − η ( ∇ Φ S ( x ) + e ) give
Φ S ( x + ) ≤ Φ S ( x ) − η 2 ∥ ∇ Φ S ( x ) ∥ 2 − ( 1 2 η − L + H 2 ) ∥ x + − x ∥ 2 + η 2 ∥ e ∥ 2 . \Phi_S(x^+) \le\Phi_S(x)-\frac{\eta}{2}\lVert\nabla\Phi_S(x)\rVert^2-\left(\frac{1}{2\eta}-\frac{L+\mathcal{H}}{2}\right)\lVert x^+-x\rVert^2+\frac{\eta}{2}\lVert e\rVert^2. Φ S ( x + ) ≤ Φ S ( x ) − 2 η ∥ ∇ Φ S ( x ) ∥ 2 − ( 2 η 1 − 2 L + H ) ∥ x + − x ∥ 2 + 2 η ∥ e ∥ 2 .
Sum these inequalities over the executed steps, using Ψ S \Psi_S Ψ S to account for additions to S S S , and apply (9) . The coefficient multiplying the sum of squared movements is nonnegative because 1 / ( 2 η ) − ( L + H ) / 2 − η C / 2 ≥ 0 1/(2\eta)-(L+\mathcal{H})/2-\eta C/2\ge0 1/ ( 2 η ) − ( L + H ) /2 − η C /2 ≥ 0 . Consequently
E ∑ executed visits ∥ ∇ Φ S n e w ( x ) ∥ 2 ≤ 2 Γ η . (10) \mathbb{E}\sum_{\text{executed visits}}\lVert\nabla\Phi_{S_{\mathrm{new}}}(x)\rVert^2\le\frac{2\Gamma}{\eta}. \tag*{(10)} E executed visits ∑ ∥ ∇ Φ S new ( x ) ∥ 2 ≤ η 2Γ . (10)
If the full gradient check fails, at least one new exceptional component is added. Otherwise all omitted residual gradients would vanish at that point, and the gradient of the partial objective would equal the full gradient. There are therefore at most k k k failed checks.
Separate visits according to the exact gradient norm of the partial objective before the recomputation decision. If ∥ ∇ Φ S ( x ) ∥ > ϵ / 2 \lVert\nabla\Phi_S(x)\rVert>\epsilon/2 ∥ ∇ Φ S ( x )∥ > ϵ /2 , no full gradient check can occur, S S S stays unchanged, and a step is taken. Equation (10) bounds the expected number of these visits by 8 Γ / ( η ϵ 2 ) 8\Gamma/(\eta\epsilon^2) 8Γ/ ( η ϵ 2 ) . Let V l o w V_{\mathrm{low}} V low count visits with ∥ ∇ Φ S ( x ) ∥ ≤ ϵ / 2 \lVert\nabla\Phi_S(x)\rVert\le\epsilon/2 ∥ ∇ Φ S ( x )∥ ≤ ϵ /2 . Each such visit leads to a full gradient check with probability p p p . There are at most k + 1 k+1 k + 1 full checks on every run, including the last one. Both arrival at a visit and the gradient threshold condition are determined before the independent recomputation decision. Hence p E V l o w ≤ k + 1 p\mathbb{E}V_{\mathrm{low}}\le k+1 p E V low ≤ k + 1 for every finite limit on the visit count. Adding the two bounds and applying monotone convergence proves (7) and almost-sure termination. The algorithm returns only after checking the exact gradient norm.
Query count. Full gradient checks cost at most n ( k + 1 ) n(k+1) n ( k + 1 ) . Conditional on reaching a visit, exact recomputation uses at most k p kp k p queries in expectation. Each executed step uses at most 2 b s = 2 τ 2bs=2\tau 2 b s = 2 τ queries in expectation for differences of residual gradients, because the samples are drawn after x x x and x + x^+ x + are fixed. Therefore
E Q ≤ n ( k + 1 ) + ( k p + 2 τ ) E V ≤ n ( k + 1 ) + 4 η H k ( 8 Γ η ϵ 2 + k + 1 p ) , \mathbb{E}Q\le n(k+1)+(kp+2\tau)\mathbb{E}V\le n(k+1)+4\eta\mathcal{H}\sqrt{k}\left(\frac{8\Gamma}{\eta\epsilon^2}+\frac{k+1}{p}\right), E Q ≤ n ( k + 1 ) + ( k p + 2 τ ) E V ≤ n ( k + 1 ) + 4 η H k ( η ϵ 2 8Γ + p k + 1 ) ,
which is (8) .
Effect of batching on the visit bound. The stepsize in (5) depends on the smoothness of the partial objective. To use at most one sampled difference per step, we may choose η o n e = min { 1 / [ 2 ( L + H ) ] , 1 / ( 2 H k ) } \eta_{\mathrm{one}}=\min\{1/[2(L+\mathcal{H})],1/(2\mathcal{H}\sqrt{k})\} η one = min { 1/ [ 2 ( L + H )] , 1/ ( 2 H k )} . This gives the same query bound. Allowing several differences improves the corresponding bound on visits by the factor η / η o n e = max { 1 , H k / ( L + H ) } ≤ k \eta/\eta_{\mathrm{one}}=\max\{1,\mathcal{H}\sqrt{k}/(L+\mathcal{H})\}\le\sqrt{k} η / η one = max { 1 , H k / ( L + H )} ≤ k . This compares the proved bounds on visits. The numbers observed in a run also depend on the objective and random samples.
Checking omitted components one at a time
Suppose an exact recomputation at x x x gives g S = ∇ Φ S ( x ) g_S = \nabla\Phi_S(x) g S = ∇ Φ S ( x ) with ∥ g S ∥ ≤ ϵ / 2 \lVert g_S\rVert\le\epsilon/2 ∥ g S ∥ ≤ ϵ /2 . The check of all components can be replaced as follows. If ∣ S ∣ = k |S| = k ∣ S ∣ = k , return x x x . Otherwise, query [ n ] ∖ S [n] \setminus S [ n ] ∖ S at x x x in a fresh uniformly random order. At the first nonzero residual gradient, add its index to S S S , reset v = R S ( x ) v = R_S(x) v = R S ( x ) using the recomputed sum and the new response, and resume optimization. If all components outside S S S have zero residual gradient at x x x , return x x x . Every query is counted. A zero response at x x x does not permanently exclude the component from later checks.
Returning immediately when ∣ S ∣ = k |S| = k ∣ S ∣ = k is valid: S ⊆ B S \subseteq B S ⊆ B and ∣ B ∣ ≤ k |B| \le k ∣ B ∣ ≤ k then imply S = B S = B S = B . This stopping condition cannot occur if the exceptional set has fewer than k k k members.
Proposition 3.2 (Query bound for sequential gradient checks). Replace the full gradient checks in Theorem 3.1 by this procedure. The method terminates almost surely with ∥ ∇ F ( x ) ∥ ≤ ϵ / 2 \lVert\nabla F(x)\rVert\le\epsilon/2 ∥ ∇ F ( x )∥ ≤ ϵ /2 and retains the visit bound (7) . Its expected query count satisfies
E Q ≤ C s c a n + 2 k ( k + 1 ) + 32 k 3 / 2 δ Γ n ϵ 2 , (11) \mathbb{E}Q \le C_{\mathrm{scan}} + 2k(k+1) + \frac{32k^{3/2}\delta\Gamma}{n\epsilon^2}, \tag*{(11)} E Q ≤ C scan + 2 k ( k + 1 ) + n ϵ 2 32 k 3/2 δ Γ , (11) where C s c a n ≤ n ( k + 1 ) C_{\mathrm{scan}} \le n(k+1) C scan ≤ n ( k + 1 ) is the expected total number of queries to components outside S S S . A scan queries these components in random order until the first nonzero response, or until all have been queried. Conditional on the history when a scan starts, put
N = ∣ [ n ] ∖ S ∣ , a = ∣ { i ∉ S : r i ( x ) ≠ 0 } ∣ . N = |[n] \setminus S|,\qquad a = |\{i \notin S : r_i(x) \ne0\}|. N = ∣ [ n ] ∖ S ∣ , a = ∣ { i ∈ / S : r i ( x ) = 0 } ∣. The expected query count of that scan is
{ ( N + 1 ) / ( a + 1 ) , a ≥ 1 , N , a = 0. (12) \begin{cases}
(N+1)/(a+1), & a \ge1,\\
N, & a = 0. \tag*{(12)}
\end{cases} { ( N + 1 ) / ( a + 1 ) , N , a ≥ 1 , a = 0. (12) Returning when ∣ S ∣ = k |S| = k ∣ S ∣ = k requires no queries outside S S S .
Proof. Each interrupted scan adds one new member of B \mathcal{B} B . If the scan finishes without a nonzero response, then g S = ∇ F ( x ) g_S = \nabla F(x) g S = ∇ F ( x ) . The same equality holds when ∣ S ∣ = k |S| = k ∣ S ∣ = k . At most k k k scans add a component, and at most one further check returns the final point.
Each addition to S S S follows an exact recomputation and introduces no estimator error. It cannot increase the potential Ψ S \Psi_S Ψ S from Theorem 3.1 . That proof therefore gives the same error recursion, bound on the sum of squared gradient norms, and count of visits with gradient norm above ϵ / 2 \epsilon/2 ϵ /2 . At a visit with gradient norm at most ϵ / 2 \epsilon/2 ϵ /2 , a check occurs with conditional probability p p p ; there are at most k + 1 k+1 k + 1 checks. This proves the same visit bound and almost-sure termination. Exact recomputations and sampled differences cost at most ( k p + 2 τ ) E V (kp+2\tau)\mathbb{E}V ( k p + 2 τ ) E V . Substituting the visit bound and adding the queries outside S S S proves (3.7).
For a ≥ 1 a \ge1 a ≥ 1 , the positions with nonzero responses divide the N − a N-a N − a zero-response positions into a + 1 a+1 a + 1 gaps with the same expected length. The expected first gap is ( N − a ) / ( a + 1 ) (N-a)/(a+1) ( N − a ) / ( a + 1 ) ; the first nonzero response adds one query. If a = 0 a=0 a = 0 , all N N N queries are required. These conditional expectations may be summed over all scans that occur, even though earlier responses determine when a new scan starts. □ \square □
The cost of stopping a scan early A complete scan can discover several components at once. Stopping at the first nonzero response discovers one component and may require further optimization before the next scan. Consequently (12) does not imply a smaller total cost. For example, suppose exactly b b b exceptional components have nonzero residual gradients at every point checked until all are discovered, starting with S = ∅ S = \emptyset S = ∅ . The b b b interrupted scans have expected total cost
∑ j = 0 b − 1 n − j + 1 b − j + 1 = b + ( n − b ) ( H b + 1 − 1 ) , H q = ∑ j = 1 q 1 j . \sum_{j=0}^{b-1} \frac{n-j+1}{b-j+1} = b + (n-b)(H_{b+1}-1), \qquad H_q = \sum_{j=1}^{q} \frac{1}{j}. j = 0 ∑ b − 1 b − j + 1 n − j + 1 = b + ( n − b ) ( H b + 1 − 1 ) , H q = j = 1 ∑ q j 1 .
A final scan confirming that all omitted residual gradients are zero adds n − b n-b n − b queries when b < k b < k b < k . It is unnecessary when b = k b = k b = k . A complete initial scan identifies all b b b indices for n n n queries. Conversely, when exactly one omitted residual gradient is nonzero at the point being checked, stopping at the first nonzero response discovers the same index for ( N + 1 ) / 2 (N+1)/2 ( N + 1 ) /2 expected queries. These counts cover only the queries used to discover components. The total cost also includes the optimization steps between checks.
Adapting the work to the discovered components
The preceding methods use a batch size determined by the supplied upper bound k k k , even when few components have been discovered. They also sample a difference before learning whether the next exact recomputation will replace it. We can avoid both costs. The resulting bound depends on the number of checks that discover new components and on the actual support size, which may be smaller than k k k .
Let L ˉ \bar{L} L ˉ be a supplied smoothness bound for every partial objective the method can form. The choice L ˉ = L + H \bar{L} = L + \mathcal{H} L ˉ = L + H always suffices under Assumption 2.1; a smaller bound may follow from additional structure. Choose
0 < η ≤ 1 2 L ˉ , p = min { 1 , 2 η δ k n } . 0 < \eta\le\frac{1}{2\bar{L}}, \qquad p = \min\left\{1, \frac{2\eta\delta\sqrt{k}}{n}\right\}. 0 < η ≤ 2 L ˉ 1 , p = min { 1 , n 2 η δ k } .
For a nonempty working set of size m m m , use
τ m = η δ k n m , b m = ⌈ τ m ⌉ , s m = τ m b m . (13) \tau_m = \frac{\eta\delta\sqrt{k}}{n}m, \qquad b_m = \lceil\tau_m \rceil, \qquad s_m = \frac{\tau_m}{b_m}. \tag*{(13)} τ m = n η δ k m , b m = ⌈ τ m ⌉ , s m = b m τ m . (13)
When p < 1 p < 1 p < 1 , τ m = p m / 2 \tau_m = pm/2 τ m = p m /2 . When p = 1 p = 1 p = 1 , every sum is recomputed and no differences are sampled. No differences are sampled when m = 0 m = 0 m = 0 . Algorithm 3.2 draws the recomputation decision before paying for a difference. It uses the same tolerance ϵ \epsilon ϵ for the exact partial gradient and the full gradient: if the latter check fails, at least one omitted residual gradient must be nonzero.
Algorithm 3.2 Adaptive working-set method
Input: x 0 x_0 x 0 , ϵ \epsilon ϵ , the preceding parameters η \eta η , p p p , the known gradient ∇ h \nabla h ∇ h , and residual-gradient queries. Initialize S = ∅ S = \varnothing S = ∅ , x = x 0 x = x_0 x = x 0 , x p r e v = x 0 x_{\mathrm{prev}} = x_0 x prev = x 0 , and v p r e v = 0 v_{\mathrm{prev}} = 0 v prev = 0 . At each visit:
Put m = ∣ S ∣ m = |S| m = ∣ S ∣ and draw an independent Bernoulli variable with success probability p p p . On success, query every component in S S S at x x x and set v = R S ( x ) v = R_S(x) v = R S ( x ) . On failure, if m = 0 m = 0 m = 0 set v = 0 v = 0 v = 0 ; otherwise draw independent Z j ∼ Bernoulli ( s m ) Z_j \sim\operatorname{Bernoulli}(s_m) Z j ∼ Bernoulli ( s m ) and I j ∼ Uniform ( S ) I_j \sim\operatorname{Uniform}(S) I j ∼ Uniform ( S ) for j = 1 , … , b m j = 1,\ldots,b_m j = 1 , … , b m , and set
v = v p r e v + 1 b m ∑ j = 1 b m Z j s m m n ( r I j ( x ) − r I j ( x p r e v ) ) . v = v_{\mathrm{prev}} + \frac{1}{b_m}\sum_{j=1}^{b_m}\frac{Z_j}{s_m}\frac{m}{n}\left(r_{I_j}(x)-r_{I_j}(x_{\mathrm{prev}})\right). v = v prev + b m 1 j = 1 ∑ b m s m Z j n m ( r I j ( x ) − r I j ( x prev ) ) .
Query both endpoints only for terms with Z j = 1 Z_j = 1 Z j = 1 .
If step 1 was an exact recomputation and ∥ ∇ h ( x ) + v ∥ ≤ ϵ \lVert\nabla h(x) + v\rVert\le\epsilon ∥ ∇ h ( x ) + v ∥ ≤ ϵ , do the following. If m = k m = k m = k , return x x x . Otherwise query every component outside S S S and put w = n − 1 ∑ i ∉ S r i ( x ) w = n^{-1}\sum_{i\notin S}r_i(x) w = n − 1 ∑ i ∈ / S r i ( x ) . Return x x x if ∥ ∇ h ( x ) + v + w ∥ ≤ ϵ \lVert\nabla h(x) + v + w\rVert\le\epsilon ∥ ∇ h ( x ) + v + w ∥ ≤ ϵ . If the check fails, add all omitted indices with r i ( x ) ≠ 0 r_i(x) \ne0 r i ( x ) = 0 to S S S and replace v v v by v + w v + w v + w .
Store x p r e v = x x_{\mathrm{prev}} = x x prev = x and v p r e v = v v_{\mathrm{prev}} = v v prev = v , then set x = x − η ( ∇ h ( x ) + v ) x = x - \eta(\nabla h(x) + v) x = x − η ( ∇ h ( x ) + v ) and begin the next visit.
Theorem 3.3 (Cost in terms of discoveries and support size). Under Assumption 2.1 and the preceding choices of L ‾ , η , p \overline{L},\eta,p L , η , p , Algorithm 3.2 terminates almost surely and returns a point with exact gradient norm at most ϵ \epsilon ϵ . Put k ∗ = ∣ B ∣ k_* = |\mathcal{B}| k ∗ = ∣ B ∣ . Let D D D be the number of failed full gradient checks, and let m j m_j m j be the working-set size immediately before check j j j , for j = 0 , … , D j = 0,\ldots,D j = 0 , … , D , including the terminal check. Then D ≤ k ∗ D \le k_* D ≤ k ∗ , and the total number of queries to omitted components is
C = ∑ j = 0 D ( n − m j ) 1 { m j < k } . C = \sum_{j=0}^{D}(n-m_j)\mathbf{1}_{\{m_j<k\}}. C = j = 0 ∑ D ( n − m j ) 1 { m j < k } . The numbers V V V of visits and Q Q Q of queries satisfy
E V ≤ 2 Γ n ϵ 2 + E D + 1 p , (14) \mathbb{E}V \le\frac{2\Gamma}{n\epsilon^2}+\frac{\mathbb{E}D+1}{p}, \tag*{(14)} E V ≤ n ϵ 2 2Γ + p E D + 1 , (14) E Q ≤ E [ C + ( 2 − p ) ∑ j = 0 D m j ] + 4 ( 2 − p ) k ∗ k δ Γ n ϵ 2 . (15) \mathbb{E}Q \le\mathbb{E}\left[C+(2-p)\sum_{j=0}^{D}m_j\right]+\frac{4(2-p)k_*\sqrt{k}\delta\Gamma}{n\epsilon^2}. \tag*{(15)} E Q ≤ E [ C + ( 2 − p ) j = 0 ∑ D m j ] + n ϵ 2 4 ( 2 − p ) k ∗ k δ Γ . (15) In particular,
E Q ≤ ( n + 2 k ∗ ) ( E D + 1 ) + 8 k ∗ k δ Γ n ϵ 2 . (16) \mathbb{E}Q \le(n+2k_*)(\mathbb{E}D+1)+\frac{8k_*\sqrt{k}\delta\Gamma}{n\epsilon^2}. \tag*{(16)} E Q ≤ ( n + 2 k ∗ ) ( E D + 1 ) + n ϵ 2 8 k ∗ k δ Γ . (16) No value of D D D , k ∗ k_* k ∗ , or the individual residual oscillations is needed by the method.
The first term in (3.11) charges the components actually queried at checks. In particular, a check can discover many components at once. The second term scales with k ∗ k_* k ∗ rather than the supplied support bound k k k . Setting D ≤ k ∗ ≤ k D \le k_* \le k D ≤ k ∗ ≤ k and Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 gives the worst-case bound ( n + 2 k ) ( k + 1 ) + 24 R (n+2k)(k+1)+24R ( n + 2 k ) ( k + 1 ) + 24 R . The order of the minimax bound is unchanged.
For k ∗ > 0 k_* > 0 k ∗ > 0 , write the residual smoothness bound as k ∗ δ ∗ 2 = k δ 2 k_*\delta_*^2 = k\delta^2 k ∗ δ ∗ 2 = k δ 2 , where δ ∗ = δ k / k ∗ \delta_* = \delta\sqrt{k/k_*} δ ∗ = δ k / k ∗ . The optimization term with supplied support then scales as k ∗ 3 / 2 δ ∗ = k ∗ k δ k_*^{3/2}\delta_* = k_*\sqrt{k}\delta k ∗ 3/2 δ ∗ = k ∗ k δ . The adaptive method obtains this dependence without knowing k ∗ k_* k ∗ , while also paying for discovery and replacing F 0 F_0 F 0 by F 0 + Ω F_0+\Omega F 0 + Ω . This statement concerns the working-set bound; selection between it and population sampling still uses the supplied parameters.
Proof. The set before a visit is exactly the set used for the preceding step. All components added at the preceding visit were included in the exact estimate before that step. Thus the deferred difference estimates the change of one fixed residual sum, even when the preceding visit enlarged the set. Both endpoints and this set are fixed before the current recomputation decision and difference samples.
For m > 0 m > 0 m > 0 , the conditional variance of the sampled difference is at most
m n 2 τ m ∑ i ∈ S ∥ r i ( x + ) − r i ( x ) ∥ 2 ≤ δ k η n ∥ x + − x ∥ 2 . \frac{m}{n^{2}\tau_m}\sum_{i\in S}\left\lVert r_i(x^{+})-r_i(x)\right\rVert^{2}\leq\frac{\delta\sqrt{k}}{\eta n}\left\lVert x^{+}-x\right\rVert^{2}. n 2 τ m m i ∈ S ∑ r i ( x + ) − r i ( x ) 2 ≤ η n δ k x + − x 2 .
For m = 0 m = 0 m = 0 , the error is zero. With a t a_t a t denoting the expected squared estimator error after any additions at visit t t t , independence and unbiasedness give
a t + 1 ≤ ( 1 − p ) a t + ( 1 − p ) δ k η n E ∥ x t + 1 − x t ∥ 2 , a 0 = 0. a_{t+1}\leq(1-p)a_t+\frac{(1-p)\delta\sqrt{k}}{\eta n}\mathbb{E}\left\lVert x^{t+1}-x^t\right\rVert^{2},\qquad a_0=0. a t + 1 ≤ ( 1 − p ) a t + η n ( 1 − p ) δ k E x t + 1 − x t 2 , a 0 = 0.
As before, first sum over a fixed finite number of visits and set errors and movements after termination to zero. If p < 1 p<1 p < 1 , the sum of expected squared errors is at most ( 1 − p ) / ( 2 η 2 ) (1-p)/(2\eta^2) ( 1 − p ) / ( 2 η 2 ) times the sum of expected squared movements, because p = 2 η δ k / n p=2\eta\delta\sqrt{k}/n p = 2 η δ k / n . If p = 1 p=1 p = 1 , every error is zero. Use L ‾ \overline{L} L in the smoothness inequality and η ≤ 1 / ( 2 L ‾ ) \eta\leq1/(2\overline{L}) η ≤ 1/ ( 2 L ) in its movement coefficient. The common potential Ψ S \Psi_S Ψ S therefore gives (10) without change.
Classify a reached visit before drawing its recomputation decision. If the exact partial gradient norm exceeds ϵ \epsilon ϵ , no check or set enlargement occurs. The gradient-energy bound limits the expected number of these visits to 2 Γ / ( η ϵ 2 ) 2\Gamma/(\eta\epsilon^2) 2Γ/ ( η ϵ 2 ) . At any other visit, a check occurs with probability p p p . A failed check adds a new component, so there are at most k ∗ + 1 k_*+1 k ∗ + 1 checks. Finite truncation and monotone convergence first prove almost-sure termination. Summing the conditional check probabilities then gives p E V l o w = E D + 1 p\mathbb{E}V_{\mathrm{low}}=\mathbb{E}D+1 p E V low = E D + 1 , which proves (14) . Returning when m = k m=k m = k is valid because S ⊆ B S\subseteq B S ⊆ B and ∣ B ∣ ≤ k |B|\leq k ∣ B ∣ ≤ k . Every other return uses the full gradient obtained from the complementary queries and the exact sum on S S S .
Conditional on reaching a visit with working-set size m m m , updating the residual estimate costs at most
p m + 2 ( 1 − p ) τ m = ( 2 − p ) p m pm+2(1-p)\tau_m=(2-p)pm p m + 2 ( 1 − p ) τ m = ( 2 − p ) p m
queries in expectation. The identity holds for p < 1 p<1 p < 1 by τ m = p m / 2 \tau_m=pm/2 τ m = p m /2 , and for p = 1 p=1 p = 1 because no differences are sampled. This also holds at the initial visit, where no difference is sampled. On visits with partial gradient norm above ϵ \epsilon ϵ , use m ≤ k ∗ m\leq k_* m ≤ k ∗ , the preceding bound on their number, and p / η ≤ 2 δ k / n p/\eta\leq2\delta\sqrt{k}/n p / η ≤ 2 δ k / n . On the remaining visits, both their classification and m m m are determined before the recomputation decision. Consequently
p E ∑ l o w v i s i t s ∣ S ∣ = E ∑ j = 0 D m j . p\mathbb{E}\sum_{\mathrm{low\ visits}}|S|=\mathbb{E}\sum_{j=0}^{D}m_j. p E low visits ∑ ∣ S ∣ = E j = 0 ∑ D m j .
Adding the C C C complementary queries proves (15) . Finally, C ≤ n ( D + 1 ) C\leq n(D+1) C ≤ n ( D + 1 ) and ∑ j m j ≤ k ∗ ( D + 1 ) \sum_jm_j\leq k_*(D+1) ∑ j m j ≤ k ∗ ( D + 1 ) give (16) . □
Comparison with exact working-set gradients An exact-gradient version uses the same discovery rule and x + = x − ∇ Ψ S ( x ) / L ‾ x^{+}=x-\nabla\Psi_S(x)/\overline{L} x + = x − ∇ Ψ S ( x ) / L . The usual smoothness inequality gives a decrease of at least ∥ ∇ Ψ S ( x ) ∥ 2 / ( 2 L ‾ ) \lVert\nabla\Psi_S(x)\rVert^2/(2\overline{L}) ∥ ∇ Ψ S ( x ) ∥ 2 / ( 2 L ) at each executed step. After a failed full check, the enlarged partial gradient equals the full gradient and has norm greater than ϵ \epsilon ϵ . Thus every executed step has partial gradient norm greater than ϵ \epsilon ϵ . Using the common potential, the step count is at most 2 L ‾ Γ / ϵ 2 2\overline{L}\Gamma/\epsilon^2 2 L Γ/ ϵ 2 . Its query count is therefore at most
C + k ∗ + 2 k ∗ L ‾ Γ ϵ 2 . C+k_*+\frac{2k_*\overline{L}\Gamma}{\epsilon^2}. C + k ∗ + ϵ 2 2 k ∗ L Γ .
where C C C is its own complementary-scan count. The two optimization terms compare the residual scale δ k / n \delta\sqrt{k}/n δ k / n with the partial-objective smoothness L ‾ \overline{L} L . Small batches alone do not imply a lower total cost when the exact-gradient method can take larger steps.
Estimation over all components or a known support
The same estimator can sample all components or a known set containing every exceptional component. Let A ⊆ [ n ] A\subseteq[n] A ⊆ [ n ] be a known set containing B \mathcal{B} B , put m = ∣ A ∣ ≥ 2 m=|A|\geq2 m = ∣ A ∣ ≥ 2 , and define
R = 1 n ∑ i ∈ A r i , ℓ A = δ m k n . R=\frac{1}{n}\sum_{i\in A}r_i,\qquad\ell_A=\frac{\delta\sqrt{mk}}{n}. R = n 1 i ∈ A ∑ r i , ℓ A = n δ mk .
Choose
0 < η A ≤ 1 2 L ‾ , p A = min { 1 , 2 η A ℓ A m } , τ A = η A ℓ A m , 0<\eta_A\leq\frac{1}{2\overline{L}},\qquad
p_A=\min\left\{1,\frac{2\eta_A\ell_A}{\sqrt{m}}\right\},\qquad
\tau_A=\eta_A\ell_A\sqrt{m}, 0 < η A ≤ 2 L 1 , p A = min { 1 , m 2 η A ℓ A } , τ A = η A ℓ A m ,
and set b A = ⌈ τ A ⌉ b_A=\lceil\tau_A\rceil b A = ⌈ τ A ⌉ and s A = τ A / b A s_A=\tau_A/b_A s A = τ A / b A . The largest allowed stepsize is η A = 1 / ( 2 L ‾ ) \eta_A=1/(2\overline{L}) η A = 1/ ( 2 L ) . The smaller choice η A = min { 1 / ( 2 L ‾ ) , 1 / ( ℓ A m ) } \eta_A=\min\{1/(2\overline{L}),1/(\ell_A\sqrt{m})\} η A = min { 1/ ( 2 L ) , 1/ ( ℓ A m )} has τ A ≤ 1 \tau_A\leq1 τ A ≤ 1 and b A = 1 b_A=1 b A = 1 , so each step samples at most one difference. If p A = 1 p_A=1 p A = 1 , the sum is recomputed at every step and no differences are sampled.
Query every component in A A A at x 0 x_0 x 0 to initialize v 0 = R ( x 0 ) v_0=R(x_0) v 0 = R ( x 0 ) , and return x 0 x_0 x 0 if ∥ ∇ h ( x 0 ) + v 0 ∥ ≤ ϵ \lVert\nabla h(x_0)+v_0\rVert\leq\epsilon ∥ ∇ h ( x 0 ) + v 0 ∥ ≤ ϵ . Otherwise execute x t + 1 = x t − η A ( ∇ h ( x t ) + v t ) x_{t+1}=x_t-\eta_A(\nabla h(x_t)+v_t) x t + 1 = x t − η A ( ∇ h ( x t ) + v t ) . After computing x t + 1 x_{t+1} x t + 1 , independently recompute R ( x t + 1 ) R(x_{t+1}) R ( x t + 1 ) with probability p A p_A p A . In this case, query every component in A A A , set v t + 1 = R ( x t + 1 ) v_{t+1}=R(x_{t+1}) v t + 1 = R ( x t + 1 ) , and return x t + 1 x_{t+1} x t + 1 if ∥ ∇ h ( x t + 1 ) + v t + 1 ∥ ≤ ϵ \lVert\nabla h(x_{t+1})+v_{t+1}\rVert\leq\epsilon ∥ ∇ h ( x t + 1 ) + v t + 1 ∥ ≤ ϵ . If no recomputation is made, draw mutually independent Z j ∼ Bernoulli ( s A ) Z_j\sim\operatorname{Bernoulli}(s_A) Z j ∼ Bernoulli ( s A ) and I j ∼ Uniform ( A ) I_j\sim\operatorname{Uniform}(A) I j ∼ Uniform ( A ) , j = 1 , … , b A j=1,\ldots,b_A j = 1 , … , b A , and set
v t + 1 = v t + 1 b A ∑ j = 1 b A Z j m s A n ( r I j ( x t + 1 ) − r I j ( x t ) ) . v_{t+1}=v_t+\frac{1}{b_A}\sum_{j=1}^{b_A}\frac{Z_jm}{s_An}\left(r_{I_j}(x_{t+1})-r_{I_j}(x_t)\right). v t + 1 = v t + b A 1 j = 1 ∑ b A s A n Z j m ( r I j ( x t + 1 ) − r I j ( x t ) ) .
For each j j j with Z j = 1 Z_j=1 Z j = 1 , query component I j I_j I j at x t x_t x t and x t + 1 x_{t+1} x t + 1 . If every Z j Z_j Z j is zero, retain v t v_t v t . Continue until an exact recomputation shows that the gradient norm is at most ϵ \epsilon ϵ . The choice A = [ n ] A=[n] A = [ n ] requires no support information. If the exceptional set is supplied, take it as A A A and, if necessary, add known indices whose residual gradients vanish identically to make m ≥ 2 m\geq2 m ≥ 2 ; for k ≥ 2 k\geq2 k ≥ 2 this keeps m ≤ k m\leq k m ≤ k .
Proposition 3.4 (Query bounds with and without supplied support). Suppose 2 ≤ k ≤ n 2\leq k\leq n 2 ≤ k ≤ n and Assumption 2.1 holds, except that the oscillation condition (2.1) is not required. The preceding method terminates almost surely and returns a point whose exact gradient norm has been checked to be at most ϵ \epsilon ϵ . Its number T A T_A T A of executed steps satisfies
E T A ≤ 2 F 0 η A ϵ 2 + 1 p A . \mathbb{E}T_A\leq\frac{2F_0}{\eta_A\epsilon^2}+\frac{1}{p_A}. E T A ≤ η A ϵ 2 2 F 0 + p A 1 . Its expected query cost, including initialization, satisfies
E Q ≤ 3 m + 8 m m k δ F 0 n ϵ 2 . (17) \mathbb{E}Q\leq3m+\frac{8m\sqrt{mk}\delta F_0}{n\epsilon^2}. \tag*{(17)} E Q ≤ 3 m + n ϵ 2 8 m mk δ F 0 . (17) Sampling all components costs O ( n + P ) O(n+\mathcal{P}) O ( n + P ) , where P = k δ F 0 / ϵ 2 \mathcal{P}=\sqrt{k}\delta F_0/\epsilon^2 P = k δ F 0 / ϵ 2 . Sampling a supplied support costs O ( k + R ) O(k+\mathcal{R}) O ( k + R ) . The final gradient checks query n n n and at most k k k components, respectively. If the protocol also requires queries to all n n n components, their cost is added to the bound with supplied support.
Proof. Because A A A contains every component with a nonzero residual gradient, ∇ h + R = ∇ F \nabla h + R = \nabla F ∇ h + R = ∇ F . If the initial gradient check succeeds, the claims hold with T A = 0 T_A = 0 T A = 0 and Q = m Q = m Q = m . Otherwise ∥ ∇ F ( x 0 ) ∥ > ϵ \lVert\nabla F(x_0)\rVert> \epsilon ∥ ∇ F ( x 0 )∥ > ϵ . First sum over at most N N N steps, where N N N is fixed, and set movements and estimator errors after termination to zero. Independence of the sampled terms and their inclusion indicators bounds the conditional variance of the difference estimate by
m b A s A n 2 ∑ i ∈ A ∥ r i ( x t + 1 ) − r i ( x t ) ∥ 2 ≤ ℓ A 2 τ A ∥ x t + 1 − x t ∥ 2 . \frac{m}{b_A s_A n^2}\sum_{i\in A}\lVert r_i(x_{t+1})-r_i(x_t)\rVert^2 \le\frac{\ell_A^2}{\tau_A}\lVert x_{t+1}-x_t\rVert^2. b A s A n 2 m i ∈ A ∑ ∥ r i ( x t + 1 ) − r i ( x t ) ∥ 2 ≤ τ A ℓ A 2 ∥ x t + 1 − x t ∥ 2 .
For e t = v t − R ( x t ) e_t=v_t-R(x_t) e t = v t − R ( x t ) , every exact recomputation makes the error zero, including the recomputation at termination. If the sum is not recomputed, the algorithm continues. The error in the sampled difference has inner product with e t e_t e t of conditional expectation zero. Consequently a t = E ∥ e t ∥ 2 a_t=\mathbb{E}\lVert e_t\rVert^2 a t = E ∥ e t ∥ 2 satisfies a 0 = 0 a_0=0 a 0 = 0 and
a t + 1 ≤ ( 1 − p A ) a t + ( 1 − p A ) ℓ A 2 τ A E ∥ x t + 1 − x t ∥ 2 . a_{t+1}\le(1-p_A)a_t+\frac{(1-p_A)\ell_A^2}{\tau_A}\mathbb{E}\lVert x_{t+1}-x_t\rVert^2. a t + 1 ≤ ( 1 − p A ) a t + τ A ( 1 − p A ) ℓ A 2 E ∥ x t + 1 − x t ∥ 2 .
Summing this recursion over the first N N N steps gives
∑ t < N E ∥ e t ∥ 2 ≤ C A ∑ t < N E ∥ x t + 1 − x t ∥ 2 , C A = ( 1 − p A ) ℓ A 2 p A τ A ≤ 1 2 η A 2 . \sum_{t<N}\mathbb{E}\lVert e_t\rVert^2\le C_A\sum_{t<N}\mathbb{E}\lVert x_{t+1}-x_t\rVert^2,\qquad C_A=\frac{(1-p_A)\ell_A^2}{p_A\tau_A}\le\frac{1}{2\eta_A^2}. t < N ∑ E ∥ e t ∥ 2 ≤ C A t < N ∑ E ∥ x t + 1 − x t ∥ 2 , C A = p A τ A ( 1 − p A ) ℓ A 2 ≤ 2 η A 2 1 .
For p A < 1 p_A<1 p A < 1 , use p A τ A = 2 η A 2 ℓ A 2 p_A\tau_A=2\eta_A^2\ell_A^2 p A τ A = 2 η A 2 ℓ A 2 ; for p A = 1 p_A=1 p A = 1 , the errors and C A C_A C A vanish. At each executed step, smoothness yields
F ( x t + 1 ) ≤ F ( x t ) − η A 2 ∥ ∇ F ( x t ) ∥ 2 − ( 1 2 η A − L 2 ) ∥ x t + 1 − x t ∥ 2 + η A 2 ∥ e t ∥ 2 . F(x_{t+1})\le F(x_t)-\frac{\eta_A}{2}\lVert\nabla F(x_t)\rVert^2-\left(\frac{1}{2\eta_A}-\frac{L}{2}\right)\lVert x_{t+1}-x_t\rVert^2+\frac{\eta_A}{2}\lVert e_t\rVert^2. F ( x t + 1 ) ≤ F ( x t ) − 2 η A ∥ ∇ F ( x t ) ∥ 2 − ( 2 η A 1 − 2 L ) ∥ x t + 1 − x t ∥ 2 + 2 η A ∥ e t ∥ 2 .
Let J N = min { T A , N } J_N=\min\{T_A,N\} J N = min { T A , N } . Sum the descent inequalities through x J N x_{J_N} x J N , use F ≥ inf F F\ge\inf F F ≥ inf F , and apply the error bound. Since η A ≤ 1 / ( 2 L ) \eta_A\le1/(2L) η A ≤ 1/ ( 2 L ) , the coefficient multiplying the sum of squared movements is nonnegative. Hence
E ∑ t < J N ∥ ∇ F ( x t ) ∥ 2 ≤ 2 F 0 η A . \mathbb{E}\sum_{t<J_N}\lVert\nabla F(x_t)\rVert^2\le\frac{2F_0}{\eta_A}. E t < J N ∑ ∥ ∇ F ( x t ) ∥ 2 ≤ η A 2 F 0 .
Consider the point reached after each executed step, before deciding whether to recompute the residual gradient sum. Let L N L_N L N count such points with true gradient norm at most ϵ \epsilon ϵ , and let H N H_N H N count those with larger norm. At a point counted in L N L_N L N , the algorithm terminates with conditional probability p A p_A p A . It can terminate only once, so p A E L N ≤ 1 p_A\mathbb{E}L_N\le1 p A E L N ≤ 1 . The number of steps that end with gradient norm above ϵ \epsilon ϵ minus the number that start above this threshold is
H N − ∑ t < J N 1 { ∥ ∇ F ( x t ) ∥ > ϵ } = 1 { ∥ ∇ F ( x J N ) ∥ > ϵ } − 1 ≤ 0 , H_N-\sum_{t<J_N}\mathbf{1}\{\lVert\nabla F(x_t)\rVert>\epsilon\}=\mathbf{1}\{\lVert\nabla F(x_{J_N})\rVert>\epsilon\}-1\le0, H N − t < J N ∑ 1 {∥ ∇ F ( x t )∥ > ϵ } = 1 {∥ ∇ F ( x J N )∥ > ϵ } − 1 ≤ 0 ,
because ∥ ∇ F ( x 0 ) ∥ > ϵ \lVert\nabla F(x_0)\rVert>\epsilon ∥ ∇ F ( x 0 )∥ > ϵ . The bound on the sum of squared gradient norms therefore gives E H N ≤ 2 F 0 / ( η A ϵ 2 ) \mathbb{E}H_N\le2F_0/(\eta_A\epsilon^2) E H N ≤ 2 F 0 / ( η A ϵ 2 ) . Since J N = L N + H N J_N=L_N+H_N J N = L N + H N , monotone convergence proves the step bound and almost-sure termination. Every returned point passes an exact gradient check.
Initialization costs m m m queries. Conditional on reaching a step, the expected cost of updating the residual estimate is c A = m p A + 2 ( 1 − p A ) τ A c_A=mp_A+2(1-p_A)\tau_A c A = m p A + 2 ( 1 − p A ) τ A . Whether that step is reached is determined before the recomputation decision and samples are drawn. Therefore
E Q ≤ m + c A E T A . \mathbb{E}Q\le m+c_A\mathbb{E}T_A. E Q ≤ m + c A E T A .
For p A < 1 p_A < 1 p A < 1 , τ A / p A = m / 2 \tau_A/p_A = m/2 τ A / p A = m /2 and c A = 2 η A ℓ A m ( 2 − p A ) c_A = 2\eta_A\ell_A\sqrt{m}(2-p_A) c A = 2 η A ℓ A m ( 2 − p A ) . Substitution gives
E Q ≤ m ( 3 − p A ) + 4 ( 2 − p A ) ℓ A m F 0 ϵ 2 ≤ 3 m + 8 ℓ A m F 0 ϵ 2 . \mathrm{EQ} \le m(3-p_A) + \frac{4(2-p_A)\ell_A\sqrt{m}F_0}{\epsilon^2} \le3m + \frac{8\ell_A\sqrt{m}F_0}{\epsilon^2}. EQ ≤ m ( 3 − p A ) + ϵ 2 4 ( 2 − p A ) ℓ A m F 0 ≤ 3 m + ϵ 2 8 ℓ A m F 0 .
For p A = 1 p_A = 1 p A = 1 , c A = m c_A = m c A = m and m / η A ≤ 2 ℓ A m m/\eta_A \le2\ell_A\sqrt{m} m / η A ≤ 2 ℓ A m , giving the stronger bound 2 m + 4 ℓ A m F 0 / ϵ 2 2m + 4\ell_A\sqrt{m}F_0/\epsilon^2 2 m + 4 ℓ A m F 0 / ϵ 2 . Using ℓ A m = m k δ / n \ell_A\sqrt{m}=m\sqrt{k\delta/n} ℓ A m = m k δ / n proves (3.13).
Using support information acquired during population sampling If queries identify k k k distinct components with nonzero residual gradients, they identify the complete exceptional set. At the next exact recomputation, the population method may restrict its sampling set to those indices. The recomputation resets the estimator exactly. Its probability p A = min { 1 , 2 η A δ k / n } p_A=\min\{1,2\eta_A\delta\sqrt{k}/n\} p A = min { 1 , 2 η A δ k / n } does not depend on the sampling set size. The conditional variance bound and the proof of the stopping-time bound are unchanged, while the cost per step can only decrease. Thus the population query bound remains valid with this change.
Selecting an upper bound When Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 , select the smaller of the valid bounds
U g a t e = ( n + 2 k ) ( k + 1 ) + 24 R , U p o p = 3 n + 8 P . U_{\mathrm{gate}}=(n+2k)(k+1)+24\mathcal{R}, \qquad U_{\mathrm{pop}}=3n+8\mathcal{P}. U gate = ( n + 2 k ) ( k + 1 ) + 24 R , U pop = 3 n + 8 P .
Here U g a t e U_{\mathrm{gate}} U gate uses Theorem 3.3 . Under Assumption 2.1, both methods check the exact gradient norm before returning. This yields O ( n + min { n k + R , P } ) O(n+\min\{nk+\mathcal{R},\mathcal{P}\}) O ( n + min { nk + R , P }) queries. A predictor-construction cost of O ( n ) O(n) O ( n ) leaves this order unchanged when P ≳ n \mathcal{P}\gtrsim n P ≳ n . The smoothness bound L L L affects the number of optimization steps, but does not appear in either query term that depends on ϵ \epsilon ϵ .
Lower bounds
The proof uses chain constructions and bounded sinusoidal residuals. When the exceptional indices are known, independent chains give Ω ( R ) \Omega(\mathcal{R}) Ω ( R ) . When the component assigned to each link is unknown, a single chain gives Ω ( n k ) \Omega(nk) Ω ( nk ) at fine accuracy. Several such chains in orthogonal coordinate blocks give Ω ( P ) \Omega(\mathcal{P}) Ω ( P ) at coarser accuracy: each unfinished chain contributes to the squared gradient norm. The sinusoidal examples cover the remaining coarse-accuracy range with linear lower bounds in n n n and k k k .
A bounded smooth chain
The accuracy-dependent constructions use the smooth chain of Carmon et al. [12 ] . A chain is a sum of links, each depending on at most two successive coordinates. We first define the chain and prove the gradient bound used below. Let
Ψ ( t ) = { 0 , t ≤ 1 / 2 , exp ( 1 − ( 2 t − 1 ) − 2 ) , t > 1 / 2 , Φ ( t ) = e ∫ − ∞ t e − s 2 / 2 d s . \Psi(t)=
\begin{cases}
0, & t\le1/2,\\
\exp\left(1-(2t-1)^{-2}\right), & t>1/2,
\end{cases}
\qquad
\Phi(t)=\sqrt{e}\int_{-\infty}^{t}e^{-s^2/2}\,ds. Ψ ( t ) = { 0 , exp ( 1 − ( 2 t − 1 ) − 2 ) , t ≤ 1/2 , t > 1/2 , Φ ( t ) = e ∫ − ∞ t e − s 2 /2 d s .
For z ∈ R K z\in\mathbb{R}^{K} z ∈ R K put
d 1 ( z ) = − Φ ( z 1 ) , c K ( z ) = ∑ j = 1 K d j ( z ) , d_1(z)=-\Phi(z_1), \qquad c_K(z)=\sum_{j=1}^{K}d_j(z), d 1 ( z ) = − Φ ( z 1 ) , c K ( z ) = j = 1 ∑ K d j ( z ) ,
d j ( z ) = Ψ ( − z j − 1 ) Φ ( − z j ) − Ψ ( z j − 1 ) Φ ( z j ) , j ≥ 2. d_j(z)=\Psi(-z_{j-1})\Phi(-z_j)-\Psi(z_{j-1})\Phi(z_j), \qquad j\ge2. d j ( z ) = Ψ ( − z j − 1 ) Φ ( − z j ) − Ψ ( z j − 1 ) Φ ( z j ) , j ≥ 2.
The function Ψ \Psi Ψ and all its derivatives vanish when t ≤ 1 / 2 t\le1/2 t ≤ 1/2 . Thus a link with preceding coordinate of magnitude below 1 / 2 1/2 1/2 has zero value and gradient in a neighborhood. A query at such a point reveals no information about that link. The radial map below sends all query points into a bounded ball. The added quadratic term keeps the gradient norm large outside the part of the domain used by the construction.
Lemma 4.1 (Bounds for the chain and its gradient). For K ≥ 1 K \ge1 K ≥ 1 , the links satisfy ∣ d j ∣ < 12 |d_j| < 12 ∣ d j ∣ < 12 , osc ( d j ) ≤ 24 \operatorname{osc}(d_j) \le24 osc ( d j ) ≤ 24 , ∥ ∇ d j ∥ ≤ 23 \lVert\nabla d_j\rVert\le23 ∥ ∇ d j ∥ ≤ 23 and ∥ ∇ 2 d j ∥ o p ≤ 410 \lVert\nabla^2 d_j\rVert_{\mathrm{op}} \le410 ∥ ∇ 2 d j ∥ op ≤ 410 . Moreover,
c K ( 0 ) − inf c K ≤ 12 K , ∥ ∇ c K ∥ ≤ 23 K , ∥ ∇ 2 c K ∥ o p < 154. c_K(0) - \inf c_K \le12K,\qquad\lVert\nabla c_K\rVert\le23\sqrt{K},\qquad\lVert\nabla^2 c_K\rVert_{\mathrm{op}} < 154. c K ( 0 ) − inf c K ≤ 12 K , ∥ ∇ c K ∥ ≤ 23 K , ∥ ∇ 2 c K ∥ op < 154. Let U U U have K K K orthonormal columns, set R = 230 K R = 230\sqrt{K} R = 230 K , and define
ρ ( y ) = y 1 + ∥ y ∥ 2 / R 2 , q U ( y ) = c K ( U T ρ ( y ) ) , H U ( y ) = q U ( y ) + ∥ y ∥ 2 10 . \rho(y) = \frac{y}{\sqrt{1+\lVert y\rVert^2/R^2}},\qquad q_U(y) = c_K(U^{\mathsf{T}}\rho(y)),\qquad H_U(y) = q_U(y) + \frac{\lVert y\rVert^2}{10}. ρ ( y ) = 1 + ∥ y ∥ 2 / R 2 y , q U ( y ) = c K ( U T ρ ( y )) , H U ( y ) = q U ( y ) + 10 ∥ y ∥ 2 . Then ∥ D ρ ∥ o p ≤ 1 \lVert D\rho\rVert_{\mathrm{op}} \le1 ∥ D ρ ∥ op ≤ 1 , ∥ D 2 ρ [ v , w ] ∥ ≤ 6 ∥ v ∥ ∥ w ∥ / R \lVert D^2\rho[v,w]\rVert\le6\lVert v\rVert\lVert w\rVert/R ∥ D 2 ρ [ v , w ]∥ ≤ 6 ∥ v ∥ ∥ w ∥ / R , and both q U , H U q_U,H_U q U , H U have Hessian norm at most 512 512 512 . If the last coordinate of U T ρ ( y ) U^{\mathsf{T}}\rho(y) U T ρ ( y ) has magnitude below 1 / 2 1/2 1/2 , then ∥ ∇ H U ( y ) ∥ > 1 / 2 \lVert\nabla H_U(y)\rVert> 1/2 ∥ ∇ H U ( y )∥ > 1/2 .
Proof. The scalar factors satisfy 0 ≤ Ψ < e 0 \le\Psi< e 0 ≤ Ψ < e , Ψ ( 1 ) = 1 \Psi(1) = 1 Ψ ( 1 ) = 1 , 0 < Φ < 2 π e 0 < \Phi< \sqrt{2\pi e} 0 < Φ < 2 π e , ∣ Φ ′ ∣ ≤ e |\Phi'| \le\sqrt{e} ∣ Φ ′ ∣ ≤ e , ∣ Φ ′ ′ ∣ ≤ 1 |\Phi''| \le1 ∣ Φ ′′ ∣ ≤ 1 , and ∣ Ψ ′ ∣ ≤ 54 / e |\Psi'| \le\sqrt{54/e} ∣ Ψ ′ ∣ ≤ 54/ e . At most one of Ψ ( t ) , Ψ ( − t ) \Psi(t),\Psi(-t) Ψ ( t ) , Ψ ( − t ) is nonzero. On t > 1 / 2 t > 1/2 t > 1/2 , writing a = ( 2 t − 1 ) − 2 a = (2t-1)^{-2} a = ( 2 t − 1 ) − 2 gives Ψ ′ ′ ( t ) = 8 e e − a a 2 ( 2 a − 3 ) \Psi''(t) = 8e e^{-a}a^2(2a-3) Ψ ′′ ( t ) = 8 e e − a a 2 ( 2 a − 3 ) ; its nonzero extrema at a = ( 9 ± 33 ) / 4 a = (9 \pm\sqrt{33})/4 a = ( 9 ± 33 ) /4 have magnitude below 33. Each gradient coordinate of the chain is consequently bounded by 108 π + e 3 / 2 < 23 \sqrt{108\pi} + e^{3/2} < 23 108 π + e 3/2 < 23 , and each Hessian row sum by 33 2 π e + 2 54 + e < 154 33\sqrt{2\pi e} + 2\sqrt{54} + e < 154 33 2 π e + 2 54 + e < 154 . For an individual link, the squared gradient norm is at most 108 π + e 3 < 23 2 108\pi+ e^3 < 23^2 108 π + e 3 < 2 3 2 . We use the looser Hessian bound 410 when combining the bounds for several links. The value bound follows from e 2 π e < 12 e\sqrt{2\pi e} < 12 e 2 π e < 12 . Since c K ( 0 ) = − Φ ( 0 ) < 0 c_K(0) = -\Phi(0) < 0 c K ( 0 ) = − Φ ( 0 ) < 0 and c K ≥ − 12 K c_K \ge-12K c K ≥ − 12 K , the gap bound follows. Direct differentiation proves the two bounds for ρ \rho ρ . The chain rule then bounds the Hessians of q U , H U q_U,H_U q U , H U by 154 + 0.6 154+0.6 154 + 0.6 and 154 + 0.8 154+0.8 154 + 0.8 .
To prove the lower bound on the gradient norm, put z = U T ρ ( y ) z = U^{\mathsf{T}}\rho(y) z = U T ρ ( y ) , r = ∥ y ∥ r = \lVert y\rVert r = ∥ y ∥ , and a = ( 1 + r 2 / R 2 ) − 1 / 2 a = (1+r^2/R^2)^{-1/2} a = ( 1 + r 2 / R 2 ) − 1/2 . Every coordinate of g = ∇ c K ( z ) g = \nabla c_K(z) g = ∇ c K ( z ) is nonpositive. If ∣ z K ∣ < 1 / 2 |z_K| < 1/2 ∣ z K ∣ < 1/2 , let j j j be the first index with ∣ z j ∣ < 1 |z_j| < 1 ∣ z j ∣ < 1 . The link ending at this coordinate has derivative at most − 1 -1 − 1 : for j = 1 j=1 j = 1 this uses Φ ′ ( z 1 ) > 1 \Phi'(z_1) > 1 Φ ′ ( z 1 ) > 1 , and otherwise ∣ z j − 1 ∣ ≥ 1 |z_{j-1}| \ge1 ∣ z j − 1 ∣ ≥ 1 , Ψ ( 1 ) = 1 \Psi(1)=1 Ψ ( 1 ) = 1 , and Φ ′ ( ± z j ) > 1 \Phi'(\pm z_j)>1 Φ ′ ( ± z j ) > 1 . The next link can only decrease this derivative. Writing v j v_j v j for column j j j of U U U gives
∇ H U ( y ) = a U g − a 3 R 2 ⟨ y , U g ⟩ y + y 5 . \nabla H_U(y) = aUg - \frac{a^3}{R^2}\langle y,Ug\rangle y + \frac{y}{5}. ∇ H U ( y ) = a U g − R 2 a 3 ⟨ y , U g ⟩ y + 5 y . If r ≤ R / 2 r \le R/2 r ≤ R /2 , then a ≥ 2 / 5 a \ge2/\sqrt{5} a ≥ 2/ 5 and ∣ ⟨ v j , y ⟩ ∣ = ∣ z j ∣ / a < 1 / a ≤ 5 / 2 |\langle v_j,y\rangle| = |z_j|/a < 1/a \le\sqrt{5}/2 ∣ ⟨ v j , y ⟩ ∣ = ∣ z j ∣/ a < 1/ a ≤ 5 /2 . The radial correction in that direction is at most a 2 r ∥ g ∥ / R 2 ≤ 1 / 20 a^2r\lVert g\rVert/R^2 \le1/20 a 2 r ∥ g ∥ / R 2 ≤ 1/20 . The component of the sum of the three terms in this direction has magnitude at least 2 / 5 − 1 / 20 − 5 / 10 > 1 / 2 2/\sqrt{5}-1/20-\sqrt{5}/10 > 1/2 2/ 5 − 1/20 − 5 /10 > 1/2 . If r ≥ R / 2 r \ge R/2 r ≥ R /2 , use the triangle inequality and ∥ D ρ ∥ o p ≤ a \lVert D\rho\rVert_{\mathrm{op}} \le a ∥ D ρ ∥ op ≤ a to obtain ∥ ∇ H U ( y ) ∥ ≥ r / 5 − 23 a K ≥ ( 23 − 46 / 5 ) K > 1 / 2 \lVert\nabla H_U(y)\rVert\ge r/5-23a\sqrt{K} \ge(23-46/\sqrt{5})\sqrt{K} > 1/2 ∥ ∇ H U ( y )∥ ≥ r /5 − 23 a K ≥ ( 23 − 46/ 5 ) K > 1/2 .
An accuracy lower bound when the exceptional indices are known
We first bound the queries needed to achieve the required accuracy when the exceptional indices are supplied. We place independent smooth chains in known coordinate blocks. Their directions are unknown, so the algorithm must query each block repeatedly. The construction follows the finite-sum chain argument in [6 ] . We prove directly that it applies to adaptively chosen query points and indices.
Theorem 4.2 (Accuracy lower bound for bounded residual gradients). Let 2 ≤ k ≤ n 2 \le k \le n 2 ≤ k ≤ n , δ , F 0 , ϵ > 0 \delta,F_0,\epsilon> 0 δ , F 0 , ϵ > 0 , C = 512 C = 512 C = 512 , and
A : = δ F 0 k 768 C n ϵ 2 ≥ 4. A := \frac{\delta F_0\sqrt{k}}{768Cn\epsilon^2} \ge4. A := 768 C n ϵ 2 δ F 0 k ≥ 4.
There is a finite-dimensional family with a known quadratic reference h h h proportional to the squared Euclidean norm, predictors p i = h p_i=h p i = h , and a known exceptional set B \mathcal{B} B of size k k k such that F ( 0 ) − inf F ≤ F 0 F(0)-\inf F\le F_0 F ( 0 ) − inf F ≤ F 0 , the objective is L 0 L_0 L 0 -smooth with L 0 = δ k / n L_0=\delta\sqrt{k}/n L 0 = δ k / n , nonexceptional residual gradients vanish, and
1 k ∑ i ∈ B ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ δ 2 ∥ x − y ∥ 2 , sup i , x ∥ r i ( x ) ∥ 2 ≤ 529 δ n F 0 12 C k . \frac{1}{k}\sum_{i\in\mathcal{B}}\lVert r_i(x)-r_i(y)\rVert^2\le\delta^2\lVert x-y\rVert^2,\qquad\sup_{i,x}\lVert r_i(x)\rVert^2\le\frac{529\,\delta nF_0}{12C\sqrt{k}}. k 1 i ∈ B ∑ ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ δ 2 ∥ x − y ∥ 2 , i , x sup ∥ r i ( x ) ∥ 2 ≤ 12 C k 529 δ n F 0 .
For every randomized algorithm using exact component-gradient queries that terminates almost surely and guarantees E ∥ ∇ F ( x ˉ ) ∥ 2 ≤ ϵ 2 \mathbb{E}\lVert\nabla F(\bar{x})\rVert^2\le\epsilon^2 E ∥ ∇ F ( x ˉ ) ∥ 2 ≤ ϵ 2 on every member of the family, some member has an expected query count satisfying
E N ≥ 2 − 23 k 3 / 2 δ F 0 n ϵ 2 . (18) \mathbb{E}N\ge2^{-23}\frac{k^{3/2}\delta F_0}{n\epsilon^2}. \tag*{(18)} E N ≥ 2 − 23 n ϵ 2 k 3/2 δ F 0 . (18)
The exceptional residual functions also satisfy osc ( u i ) ≤ 2 n F 0 / k \operatorname{osc}(u_i)\le2nF_0/k osc ( u i ) ≤ 2 n F 0 / k , so this family belongs to the objective class of Theorem 2.2 .
Proof of Theorem 4.2. Use the chain and radial map of § 4.1 . Set
K = 2 ⌊ A / 2 ⌋ , R = 230 K , α = n F 0 12 k K , ℓ 0 2 = C α δ k , Q = ⌊ k K / 4 ⌋ . K=2\lfloor A/2\rfloor,\qquad R=230\sqrt{K},\qquad\alpha=\frac{nF_0}{12kK},\qquad\ell_0^2=\frac{C\alpha}{\delta\sqrt{k}},\qquad Q=\lfloor kK/4\rfloor. K = 2 ⌊ A /2 ⌋ , R = 230 K , α = 12 k K n F 0 , ℓ 0 2 = δ k C α , Q = ⌊ k K /4 ⌋ .
Choose the integer dimension of each block to satisfy
m ≥ K + 1 + 8 R 2 log ( 16 k K ( Q + 1 ) ) , d = k m . (19) m\ge K+1+8R^2\log(16kK(Q+1)),\qquad d=km. \tag*{(19)} m ≥ K + 1 + 8 R 2 log ( 16 k K ( Q + 1 )) , d = k m . (19)
Let C i : R m → R d C_i:\mathbb{R}^m\to\mathbb{R}^d C i : R m → R d , i ∈ [ k ] i\in[k] i ∈ [ k ] , be known isometric coordinate embeddings with mutually orthogonal ranges. Independently draw U i = [ v i , 1 , … , v i , K ] U_i=[v_{i,1},\ldots,v_{i,K}] U i = [ v i , 1 , … , v i , K ] uniformly from the m m m -by-K K K matrices with orthonormal columns. We call such matrices frames. Define
h ( x ) = α 10 n ℓ 0 2 ∥ x ∥ 2 , f i = h + u i , h(x)=\frac{\alpha}{10n\ell_0^2}\lVert x\rVert^2,\qquad f_i=h+u_i, h ( x ) = 10 n ℓ 0 2 α ∥ x ∥ 2 , f i = h + u i ,
u i ( x ) = α q U i ( C i T x / ℓ 0 ) ( i ≤ k ) , u i = 0 ( i > k ) . u_i(x)=\alpha q_{U_i}(C_i^\mathsf{T}x/\ell_0)\quad(i\le k),\qquad u_i=0\quad(i>k). u i ( x ) = α q U i ( C i T x / ℓ 0 ) ( i ≤ k ) , u i = 0 ( i > k ) .
Thus B = [ k ] \mathcal{B}=[k] B = [ k ] is known and F ( x ) = n − 1 ∑ i = 1 k α H U i ( C i T x / ℓ 0 ) F(x)=n^{-1}\sum_{i=1}^k\alpha H_{U_i}(C_i^\mathsf{T}x/\ell_0) F ( x ) = n − 1 ∑ i = 1 k α H U i ( C i T x / ℓ 0 ) . All quantities in this construction other than the random frames are known to the algorithm.
Verifying the objective assumptions By orthogonality and Lemma 4.1 ,
1 k ∑ i = 1 k ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ C 2 α 2 k ℓ 0 4 ∥ x − y ∥ 2 = δ 2 ∥ x − y ∥ 2 . \frac{1}{k}\sum_{i=1}^k\lVert r_i(x)-r_i(y)\rVert^2\le\frac{C^2\alpha^2}{k\ell_0^4}\lVert x-y\rVert^2=\delta^2\lVert x-y\rVert^2. k 1 i = 1 ∑ k ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ k ℓ 0 4 C 2 α 2 ∥ x − y ∥ 2 = δ 2 ∥ x − y ∥ 2 .
The block-diagonal objective Hessian has norm at most C α / ( n ℓ 0 2 ) = δ k / n C\alpha/(n\ell_0^2)=\delta\sqrt{k}/n C α / ( n ℓ 0 2 ) = δ k / n . The initial objective gap is at most 12 k α K / n = F 0 12k\alpha K/n=F_0 12 k α K / n = F 0 , and
∥ r i ( x ) ∥ 2 ≤ 529 K α 2 / ℓ 0 2 = 529 δ n F 0 12 C k . \lVert r_i(x)\rVert^2\le529K\alpha^2/\ell_0^2=\frac{529\,\delta nF_0}{12C\sqrt{k}}. ∥ r i ( x ) ∥ 2 ≤ 529 K α 2 / ℓ 0 2 = 12 C k 529 δ n F 0 .
Each link has absolute value below 12. Composing the chain with the radial map cannot enlarge its range. Hence osc ( u i ) ≤ 24 K α = 2 n F 0 / k \operatorname{osc}(u_i)\le24K\alpha=2nF_0/k osc ( u i ) ≤ 24 K α = 2 n F 0 / k globally.
Comparing actual and auxiliary responses Fix the algorithm’s random seed. For the proof, define an auxiliary oracle that has revealed the first s i s_i s i columns in each block, initially none. On a query to i ≤ k i \le k i ≤ k , it reveals the next column if s i < K s_i < K s i < K and increases s i s_i s i by one. It then returns the gradient of h h h plus that of the truncated residual function
α ∑ j = 1 s i d j ( U i T ρ ( C i T x / ℓ 0 ) ) . \alpha\sum_{j=1}^{s_i} d_j\left(U_i^{\mathsf T}\rho\left(C_i^{\mathsf T}x/\ell_0\right)\right). α j = 1 ∑ s i d j ( U i T ρ ( C i T x / ℓ 0 ) ) .
This expression uses only the revealed columns. The radius in ρ \rho ρ remains R = 230 K R = 230\sqrt{K} R = 230 K , regardless of how many columns have been revealed. A query to i > k i > k i > k receives the gradient of the known reference. The algorithm uses only the returned gradients; the additional column information is used in the analysis. Define the auxiliary process on all outcomes. We next construct an event on which every returned gradient equals the actual one.
Condition on the auxiliary history, including all revealed columns, before a query. Every unrevealed column is uniform in the orthogonal complement of the columns already revealed in its block. This space has dimension at least m − K m-K m − K . Applying the radial map to the query in that block gives a vector of norm at most R R R , so
Pr { ∣ ⟨ v i , j , ρ ( C i T x / ℓ 0 ) ⟩ ∣ ≥ 1 2 | preceding auxiliary history } ≤ 2 exp ( − m − K − 1 8 R 2 ) . \Pr\left\{\left|\left\langle v_{i,j},\rho\left(C_i^{\mathsf T}x/\ell_0\right)\right\rangle\right|\ge\frac{1}{2}\,\middle|\,\text{preceding auxiliary history}\right\}\le2\exp\left(-\frac{m-K-1}{8R^2}\right). Pr { ⟨ v i , j , ρ ( C i T x / ℓ 0 ) ⟩ ≥ 2 1 preceding auxiliary history } ≤ 2 exp ( − 8 R 2 m − K − 1 ) .
The same estimate holds for every unrevealed column at an arbitrary output measurable from the final history of the auxiliary process. There are at most k K ( Q + 1 ) kK(Q+1) k K ( Q + 1 ) tests over Q Q Q queries and that output. Equation (19) therefore bounds the probability of any failed test by 1 / 8 1/8 1/8 . This bound does not condition the distribution of the frame on earlier successful tests.
If all tests succeed, every omitted link vanishes in a neighborhood of each query. The first link omitted after a column is revealed depends on the newly revealed coordinate. That coordinate was still unknown and was tested before the query. The preceding coordinates of all later links were also tested. Thus the truncated and actual gradients agree. Induction shows that the actual and auxiliary processes have identical queries, responses, and outputs on this event. This argument permits arbitrary adaptive indices, unbounded query points, and an unqueried output. Each query reveals at most one column in one block. After at most Q Q Q calls, at least k / 2 k/2 k /2 blocks still have unrevealed columns. Their last columns are therefore unrevealed, and the corresponding coordinates have magnitude below one half at the output. Lemma 4.1 and orthogonality then give, with probability at least 7 / 8 7/8 7/8 ,
∥ ∇ F ( x ^ ) ∥ 2 ≥ k α 2 8 n 2 ℓ 0 2 = δ F 0 k 96 C n K ≥ 8 ε 2 . \left\|\nabla F(\widehat{x})\right\|^2 \ge\frac{k\alpha^2}{8n^2\ell_0^2} = \frac{\delta F_0\sqrt{k}}{96CnK} \ge8\varepsilon^2. ∥ ∇ F ( x ) ∥ 2 ≥ 8 n 2 ℓ 0 2 k α 2 = 96 C n K δ F 0 k ≥ 8 ε 2 .
Averaging over the algorithm’s seed gives the same conclusion for any algorithm limited to this number of queries.
Algorithms with a random stopping time Run a general stopping algorithm until it returns or is about to request its ( Q + 1 ) (Q+1) ( Q + 1 ) st gradient; in the latter case return zero. Denote this truncated output by x ^ Q \widehat{x}_Q x Q . It agrees with the original output x ^ \widehat{x} x on { N ≤ Q } \{N \le Q\} { N ≤ Q } . Averaging over the family drawn before the queries and the algorithm’s seed, the preceding bound and the assumed bound on the expected squared gradient norm imply
7 8 ≤ Pr { ∥ ∇ F ( x ^ Q ) ∥ 2 ≥ 8 ε 2 } ≤ Pr ( N > Q ) + Pr { ∥ ∇ F ( x ^ ) ∥ 2 ≥ 8 ε 2 } ≤ Pr ( N > Q ) + 1 8 . \begin{aligned}
\frac{7}{8} &\le\Pr\left\{\left\|\nabla F(\widehat{x}_Q)\right\|^2 \ge8\varepsilon^2\right\} \\
&\le\Pr(N>Q)+\Pr\left\{\left\|\nabla F(\widehat{x})\right\|^2 \ge8\varepsilon^2\right\} \\
&\le\Pr(N>Q)+\frac{1}{8}.
\end{aligned} 8 7 ≤ Pr { ∥ ∇ F ( x Q ) ∥ 2 ≥ 8 ε 2 } ≤ Pr ( N > Q ) + Pr { ∥ ∇ F ( x ) ∥ 2 ≥ 8 ε 2 } ≤ Pr ( N > Q ) + 8 1 .
Therefore E N ≥ 3 Q / 4 \mathbb{E}N \ge3Q/4 E N ≥ 3 Q /4 . Since Q ≥ k K / 8 Q \ge kK/8 Q ≥ k K /8 and K ≥ A / 2 K \ge A/2 K ≥ A /2 ,
E N ≥ 3 k A 64 = k 3 / 2 δ F 0 16384 C n ϵ 2 . \mathbb{E}N \ge\frac{3kA}{64} = \frac{k^{3/2}\delta F_0}{16384Cn\epsilon^2}. E N ≥ 64 3 k A = 16384 C n ϵ 2 k 3/2 δ F 0 .
With C = 512 C = 512 C = 512 , this proves (4.1) for some member of the family. The query count includes any queries used to construct the predictors.
The cost of discovering exceptional components
We assign successive links of a smooth chain to components whose indices are unknown. The next direction is revealed only when the algorithm queries the component holding that link. We account both for adaptively chosen query points and for the search over component indices.
Theorem 4.3 (Lower bound for discovering the exceptional components). Let 16 ≤ k ≤ n 16 \le k \le n 16 ≤ k ≤ n , δ \delta δ , F 0 > 0 F_0 > 0 F 0 > 0 , and C ∗ = 1024 C_* = 1024 C ∗ = 1024 . Define
B 2 = δ n F 0 k , W = 2 n F 0 k , L 0 = δ k n , ϵ 0 2 = δ F 0 768 C ∗ n k . B^2 = \frac{\delta n F_0}{\sqrt{k}}, \qquad W = \frac{2nF_0}{k}, \qquad L_0 = \frac{\delta\sqrt{k}}{n}, \qquad\epsilon_0^2 = \frac{\delta F_0}{768C_*n\sqrt{k}}. B 2 = k δ n F 0 , W = k 2 n F 0 , L 0 = n δ k , ϵ 0 2 = 768 C ∗ n k δ F 0 . There is a finite-dimensional family with a known quadratic reference proportional to the squared Euclidean norm, predictors p i = h p_i = h p i = h , and exactly k k k unknown exceptional components. Every member satisfies F ( 0 ) − inf F ≤ F 0 F(0) - \inf F \le F_0 F ( 0 ) − inf F ≤ F 0 and is L 0 L_0 L 0 -smooth. Its residual functions u i u_i u i and residual gradients r i r_i r i satisfy
sup i , x ∥ r i ( x ) ∥ ≤ B , osc ( u i ) ≤ W , 1 k ∑ i ∈ B ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ δ 2 ∥ x − y ∥ 2 . \sup_{i,x}\|r_i(x)\| \le B,\qquad\operatorname{osc}(u_i) \le W,\qquad\frac{1}{k}\sum_{i\in B}\|r_i(x)-r_i(y)\|^2 \le\delta^2\|x-y\|^2. i , x sup ∥ r i ( x ) ∥ ≤ B , osc ( u i ) ≤ W , k 1 i ∈ B ∑ ∥ r i ( x ) − r i ( y ) ∥ 2 ≤ δ 2 ∥ x − y ∥ 2 . For every 0 < ϵ ≤ ϵ 0 0 < \epsilon\le\epsilon_0 0 < ϵ ≤ ϵ 0 and every randomized algorithm using exact component-gradient queries that terminates almost surely and guarantees E ∥ ∇ F ( x ^ ) ∥ 2 ≤ ϵ 2 \mathbb{E}\|\nabla F(\widehat{x})\|^2 \le\epsilon^2 E ∥∇ F ( x ) ∥ 2 ≤ ϵ 2 on every family member, some member has an expected query count satisfying
E N ≥ 13 2048 n k . (20) \mathbb{E}N \ge\frac{13}{2048}nk. \tag*{(20)} E N ≥ 2048 13 nk . (20) The algorithm may choose arbitrary component indices and query points, and may return an unqueried point. Queries used to construct predictors are included. The exceptional indices are not supplied.
Proof of Theorem 4.3. We draw the objective before any queries, verify its assumptions, and bound the queries needed to find the component assigned to each successive link. An auxiliary process lets us compare this search with the actual oracle.
Assigning chain links to unknown component indices Use the links d 1 , … , d k d_1,\ldots,d_k d 1 , … , d k and radial map ρ \rho ρ of Section 4.1 with chain length K = k K = k K = k . Set
R = 230 k , α = n F 0 12 k , ℓ 2 = C ∗ α δ k . R = 230\sqrt{k},\qquad\alpha= \frac{nF_0}{12k},\qquad\ell^2 = \frac{C_*\alpha}{\delta\sqrt{k}}. R = 230 k , α = 12 k n F 0 , ℓ 2 = δ k C ∗ α .
Draw a uniformly random orthonormal frame U = [ v 1 , … , v k ] ∈ R d × k U = [v_1,\ldots,v_k] \in\mathbb{R}^{d\times k} U = [ v 1 , … , v k ] ∈ R d × k and, independently, a uniformly random ordered list ( λ 1 , … , λ k ) (\lambda_1,\ldots,\lambda_k) ( λ 1 , … , λ k ) of distinct indices in [ n ] [n] [ n ] . Define
h ( x ) = α 10 n ℓ 2 ∥ x ∥ 2 , u λ j ( x ) = α d j ( U ⊤ ρ ( x / ℓ ) ) , h(x) = \frac{\alpha}{10n\ell^2}\|x\|^2,\qquad u_{\lambda_j}(x) = \alpha d_j(U^\top\rho(x/\ell)), h ( x ) = 10 n ℓ 2 α ∥ x ∥ 2 , u λ j ( x ) = α d j ( U ⊤ ρ ( x / ℓ )) ,
u i ( x ) = 0 ( i ∉ { λ 1 , … , λ k } ) , f i = h + u i . u_i(x) = 0\quad(i \notin\{\lambda_1,\ldots,\lambda_k\}),\qquad f_i = h + u_i. u i ( x ) = 0 ( i ∈ / { λ 1 , … , λ k }) , f i = h + u i .
The complete objective is exactly
F ( x ) = α n ( c k ( U ⊤ ρ ( x / ℓ ) ) + 1 10 ∥ x / ℓ ∥ 2 ) . F(x) = \frac{\alpha}{n}\left(c_k(U^\top\rho(x/\ell)) + \frac{1}{10}\|x/\ell\|^2\right). F ( x ) = n α ( c k ( U ⊤ ρ ( x / ℓ )) + 10 1 ∥ x / ℓ ∥ 2 ) .
All quantities other than the random frame and the ordered assignment of component indices are known to the algorithm.
Bounds on residual gradients and the objective Lemma 4.1 gives ∣ d j ∣ ≤ 12 |d_j| \le12 ∣ d j ∣ ≤ 12 , osc ( d j ) ≤ 24 \operatorname{osc}(d_j) \le24 osc ( d j ) ≤ 24 , ∥ ∇ d j ∥ ≤ 23 \|\nabla d_j\| \le23 ∥∇ d j ∥ ≤ 23 and ∥ ∇ 2 d j ∥ o p ≤ 410 \|\nabla^2 d_j\|_{\mathrm{op}} \le410 ∥ ∇ 2 d j ∥ op ≤ 410 . Each link depends on at most two adjacent coordinates. Hence for every vector v v v ,
∑ j ∥ ∇ 2 d j ( z ) v ∥ 2 ≤ 2 ⋅ 410 2 ∥ v ∥ 2 . \sum_j \|\nabla^2 d_j(z)v\|^2 \le2\cdot410^2\|v\|^2. j ∑ ∥ ∇ 2 d j ( z ) v ∥ 2 ≤ 2 ⋅ 41 0 2 ∥ v ∥ 2 .
Let q j ( y ) = d j ( U ⊤ ρ ( y ) ) q_j(y)=d_j(U^\top\rho(y)) q j ( y ) = d j ( U ⊤ ρ ( y )) . Since ∥ D ρ ∥ o p ≤ 1 \|D\rho\|_{\mathrm{op}}\le1 ∥ D ρ ∥ op ≤ 1 and ∥ D 2 ρ [ v , w ] ∥ ≤ 6 ∥ v ∥ ∥ w ∥ / R \|D^2\rho[v,w]\|\le6\|v\|\|w\|/R ∥ D 2 ρ [ v , w ] ∥ ≤ 6∥ v ∥∥ w ∥/ R , the chain rule and Minkowski’s inequality for the Euclidean norm of the concatenated Hessian-vector products give
( ∑ j ∥ ∇ 2 q j ( y ) v ∥ 2 ) 1 / 2 ≤ ( 2 410 + 6 ⋅ 23 k R ) ∥ v ∥ < C ∗ ∥ v ∥ . \left(\sum_j\|\nabla^2q_j(y)v\|^2\right)^{1/2}
\le\left(\sqrt{2}\,410+\frac{6\cdot23\sqrt{k}}{R}\right)\|v\|<C_*\|v\|. ( j ∑ ∥ ∇ 2 q j ( y ) v ∥ 2 ) 1/2 ≤ ( 2 410 + R 6 ⋅ 23 k ) ∥ v ∥ < C ∗ ∥ v ∥.
Integrating along a line segment and substituting the chosen scale gives the stated root-mean-square smoothness bound for the residual gradients. Also
∥ r i ( x ) ∥ 2 ≤ 529 α 2 ℓ 2 = 529 δ n F 0 12 C ∗ k ≤ B 2 , osc ( u i ) ≤ 24 α = W . \|r_i(x)\|^2\le\frac{529\alpha^2}{\ell^2}=\frac{529\,\delta nF_0}{12C_*\sqrt{k}}\le B^2,\qquad\operatorname{osc}(u_i)\le24\alpha=W. ∥ r i ( x ) ∥ 2 ≤ ℓ 2 529 α 2 = 12 C ∗ k 529 δ n F 0 ≤ B 2 , osc ( u i ) ≤ 24 α = W .
By Lemma 4.1, the chain composed with the radial map, plus the quadratic term, has initial gap at most 12 k 12k 12 k and Hessian norm at most 512 512 512 . Thus F ( 0 ) − inf F ≤ F 0 F(0)-\inf F\le F_0 F ( 0 ) − inf F ≤ F 0 and its smoothness is at most 512 α / ( n ℓ 2 ) = δ k / ( 2 n ) ≤ L 0 512\alpha/(n\ell^2)=\delta\sqrt{k}/(2n)\le L_0 512 α / ( n ℓ 2 ) = δ k / ( 2 n ) ≤ L 0 . All these bounds hold globally. At the origin only the first link has a nonzero residual gradient.
Revealing successive links with an auxiliary oracle Fix the algorithm and its random seed. Let m m m be the number of successive links whose component indices and frame columns have been revealed, initially zero. At query ( i , x ) (i,x) ( i , x ) , if i = λ j i=\lambda_j i = λ j for some j ≤ m j\le m j ≤ m , return the exact gradient. If m < k m<k m < k and i = λ m + 1 i=\lambda_{m+1} i = λ m + 1 , reveal that index and v m + 1 v_{m+1} v m + 1 , increase m m m by one, and return the exact gradient. This revelation occurs regardless of whether the gradient itself determines the new direction. For every other component index not yet revealed, return only ∇ h ( x ) \nabla h(x) ∇ h ( x ) .
Define this process on all outcomes. Its replies depend only on the columns already revealed. Conditional on the queries, responses, and revealed columns, the unrevealed columns therefore form a uniformly distributed orthonormal frame in the orthogonal complement of the revealed columns. The assignment of component indices is independent of the frame and preserves this conditional distribution. The search argument allows the algorithm to use all revealed indices and columns. To compare with the actual oracle, run the given algorithm while withholding these additional revelations. The comparison below bounds the probability that the two processes return different gradients.
Agreement at the queries and at the output At any auxiliary query, condition on the preceding history. Each currently unrevealed frame column is a uniform unit vector in a subspace of dimension at least d − k d-k d − k , and ∥ ρ ( x / ℓ ) ∥ ≤ R \lVert\rho(x/\ell)\rVert\le R ∥ ρ ( x / ℓ )∥ ≤ R . The concentration bound for a uniformly distributed unit vector gives
Pr { ∣ ⟨ v j , ρ ( x / ℓ ) ⟩ ∣ ≥ 1 2 | preceding auxiliary history } ≤ 2 exp ( − d − k − 1 8 R 2 ) . \Pr\left\{\left|\langle v_j,\rho(x/\ell)\rangle\right| \ge\frac{1}{2}\,\middle|\,\text{preceding auxiliary history}\right\} \le2\exp\left(-\frac{d-k-1}{8R^2}\right). Pr { ∣ ⟨ v j , ρ ( x / ℓ )⟩ ∣ ≥ 2 1 preceding auxiliary history } ≤ 2 exp ( − 8 R 2 d − k − 1 ) .
The same statement applies to an arbitrary final output measurable from that history, before any further direction is revealed. A sufficient dimension is
d ≥ k + 1 + 8 R 2 log ( 32 k ( Q + 1 ) ) , Q = ⌊ n k / 64 ⌋ . d \ge k+1+8R^2\log(32k(Q+1)),\qquad Q=\lfloor nk/64\rfloor. d ≥ k + 1 + 8 R 2 log ( 32 k ( Q + 1 )) , Q = ⌊ nk /64 ⌋ .
A union bound over at most k ( Q + 1 ) k(Q+1) k ( Q + 1 ) tests, covering all queries and the output, bounds the failure probability by 1 / 16 1/16 1/16 . We evaluate this probability in the auxiliary process without conditioning the frame distribution on the projection bounds at earlier queries.
If all tests succeed, every auxiliary response equals the actual gradient. It remains only to check an index λ j \lambda_j λ j , j ≥ m + 2 j\ge m+2 j ≥ m + 2 , assigned to a later link. Its preceding coordinate has magnitude less than 1 / 2 1/2 1/2 , so Ψ \Psi Ψ and all its derivatives vanish there. Its link is identically zero near the query point, and its true residual gradient is zero. Queries to revealed indices and to the next index return exact gradients by definition. Consequently an ordinary algorithm and its auxiliary simulation have identical queries, responses, and outputs whenever all tests succeed. The frame and component assignment were drawn before any query, so the objective is fixed throughout.
Cost of finding each successive component index At the start of stage j j j , the next index is uniform among n − j + 1 n-j+1 n − j + 1 remaining indices. A failed query within that stage excludes only the queried index from being the next one. Previous stages impose no further ordering restrictions on the remaining indices once their successful indices are known. A query to a component already revealed, or excluded during the current stage, cannot reveal the next link.
Fix the history at the start of a stage and the algorithm’s randomness. Consider the order in which it would query distinct remaining indices if every query to an unrevealed component returned the gradient of the known reference. Responses at revealed components remain unchanged. Append any indices it would not query, in a fixed order. This order is independent of the next unknown index. Until that index is queried, these hypothetical responses and the actual auxiliary responses coincide. The rank of the next index is conditionally uniform on { 1 , … , n − j + 1 } \{1,\ldots,n-j+1\} { 1 , … , n − j + 1 } . After the index is found, the remaining assignment is again uniform. By induction, the total query count needed to reveal every link stochastically dominates
D = ∑ j = 1 k U j , U j independent , U j ∼ Uniform { 1 , … , n − j + 1 } . D=\sum_{j=1}^{k}U_j,\qquad U_j\text{ independent},\qquad U_j\sim\operatorname{Uniform}\{1,\ldots,n-j+1\}. D = j = 1 ∑ k U j , U j independent , U j ∼ Uniform { 1 , … , n − j + 1 } .
This remains true with arbitrary adaptive point choices, repeated indices, and the algorithm’s randomization. Each stage still requires finding its component index even when all previously revealed directions are available.
For j ≤ ⌈ k / 2 ⌉ j\le\lceil k/2\rceil j ≤ ⌈ k /2 ⌉ , the range size n − j + 1 n-j+1 n − j + 1 is at least n / 2 n/2 n /2 . Comparing the exponential sum to its integral gives
E e − 2 U j / n ≤ 1 − e − 2 ( n − j + 1 ) / n 2 ( n − j + 1 ) / n ≤ 1 − e − 1 . \mathbb{E}e^{-2U_j/n}\le\frac{1-e^{-2(n-j+1)/n}}{2(n-j+1)/n}\le1-e^{-1}. E e − 2 U j / n ≤ 2 ( n − j + 1 ) / n 1 − e − 2 ( n − j + 1 ) / n ≤ 1 − e − 1 .
Thus
Pr ( D ≤ Q ) ≤ e 2 Q / n ( 1 − e − 1 ) ⌈ k / 2 ⌉ ≤ e k / 32 ( 1 − e − 1 ) k / 2 < 1 16 , k ≥ 16. \Pr(D\le Q)\le e^{2Q/n}(1-e^{-1})^{\lceil k/2\rceil}\le e^{k/32}(1-e^{-1})^{k/2}<\frac{1}{16},\qquad k\ge16. Pr ( D ≤ Q ) ≤ e 2 Q / n ( 1 − e − 1 ) ⌈ k /2 ⌉ ≤ e k /32 ( 1 − e − 1 ) k /2 < 16 1 , k ≥ 16.
With probability at least 7 / 8 7/8 7/8 , both processes have the same output and the last frame column remains unrevealed after at most Q Q Q queries.
The gradient bound and random stopping times The gradient bound in Lemma 4.1 applies whenever the last coordinate of the chain argument has magnitude below 1 / 2 1/2 1/2 . Thus the common output of the two processes on the event above satisfies
∥ ∇ F ( x ^ ) ∥ 2 > α 2 4 n 2 ℓ 2 = δ F 0 48 C ∗ n k ≥ 16 ϵ 2 . \left\lVert\nabla F(\widehat{x}) \right\rVert^2 > \frac{\alpha^2}{4n^2\ell^2} = \frac{\delta F_0}{48C_* n\sqrt{k}} \ge16\epsilon^2. ∥ ∇ F ( x ) ∥ 2 > 4 n 2 ℓ 2 α 2 = 48 C ∗ n k δ F 0 ≥ 16 ϵ 2 .
The output test was already included in the union bound, so the output need not have been queried.
For an arbitrary almost-surely terminating algorithm, write x ^ \widehat{x} x for its output. Run it until return or immediately before a requested ( Q + 1 ) (Q+1) ( Q + 1 ) st gradient, returning zero in the latter case; denote this output by x ^ Q \widehat{x}_Q x Q . They agree on { N ≤ Q } \{N \le Q\} { N ≤ Q } . Averaging over the objective family and the algorithm’s seed, the bound for at most this many queries and the assumed bound on the expected squared gradient norm give
7 8 ≤ Pr { ∥ ∇ F ( x ^ Q ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr ( N > Q ) + Pr { ∥ ∇ F ( x ^ ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr ( N > Q ) + 1 16 . \begin{aligned}
\frac{7}{8} \le\Pr\left\{\left\lVert\nabla F(\widehat{x}_Q) \right\rVert^2 \ge16\epsilon^2\right\} \\
&\le\Pr(N > Q) + \Pr\left\{\left\lVert\nabla F(\widehat{x}) \right\rVert^2 \ge16\epsilon^2\right\} \\
&\le\Pr(N > Q) + \frac{1}{16}.
\end{aligned} 8 7 ≤ Pr { ∥ ∇ F ( x Q ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr ( N > Q ) + Pr { ∥ ∇ F ( x ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr ( N > Q ) + 16 1 .
Therefore E N ≥ 13 Q / 16 ≥ 13 n k / 2048 \mathbb{E}N \ge13Q/16 \ge13nk/2048 E N ≥ 13 Q /16 ≥ 13 nk /2048 , since n k ≥ 256 nk \ge256 nk ≥ 256 . Averaging implies that some fixed family member attains this expected lower bound. This count includes every query used to construct the predictors.
Search cost under adaptive allocation
The following estimate permits chains of any positive length. It accounts for an algorithm that switches between searches and stops unsuccessful searches early.
Lemma 4.4 (Cost of an interrupted search). Suppose a stage has one successful index, uniform among M M M candidates conditional on the history when the stage begins. Before success, responses from this stage give no information except whether the queried index is successful. Randomness used in other searches is independent of that index conditional on this history. For any adaptive allocation of a finite query budget, let Z Z Z count distinct candidates queried during this stage and let J J J indicate that the stage succeeds. Then
E Z ≥ M + 1 2 E J . \mathbb{E}Z \ge\frac{M+1}{2}\mathbb{E}J. E Z ≥ 2 M + 1 E J . For m m m chains, independently draw a uniform ordered list of q ≤ N q \le N q ≤ N distinct successful indices from N N N candidates in each chain. At each stage use the same response rule: before its successful index is queried, responses give no information about the remaining order beyond excluding the current query from being that stage’s successful index. Let C Q C_Q C Q be the number of completed chains after at most Q Q Q queries. Arbitrary adaptive interleaving is allowed. Then
E C Q ≤ 4 Q q ( 2 N − q + 3 ) ≤ 4 Q N q . (21) \mathbb{E}C_Q \le\frac{4Q}{q(2N-q+3)} \le\frac{4Q}{Nq}. \tag*{(21)} E C Q ≤ q ( 2 N − q + 3 ) 4 Q ≤ N q 4 Q . (21)
Proof. Condition on entry into a stage and expose the independent randomness of the algorithm and the other searches. Consider its continuation if every candidate tested in this stage fails. Let t ≤ M t \le M t ≤ M be the number of distinct candidates it would test before the global budget expires, and append untested candidates in a fixed order. The successful index has a uniform rank U U U in this order, independent of this continuation. The actual and hypothetical histories coincide until that index is tested. Thus J = 1 { U ≤ t } J = \mathbf{1}_{\{U \le t\}} J = 1 { U ≤ t } and Z = min { U , t } Z = \min\{U,t\} Z = min { U , t } . Consequently
E [ Z ∣ t ] = t ( 2 M − t + 1 ) 2 M ≥ M + 1 2 t M = M + 1 2 E [ J ∣ t ] . \mathbb{E}[Z \mid t] = \frac{t(2M-t+1)}{2M} \ge\frac{M+1}{2}\frac{t}{M} = \frac{M+1}{2}\mathbb{E}[J \mid t]. E [ Z ∣ t ] = 2 M t ( 2 M − t + 1 ) ≥ 2 M + 1 M t = 2 M + 1 E [ J ∣ t ] .
Repeated queries only increase the paid cost. If a stage is never entered, both variables are zero, so the inequality also holds without conditioning on entry. For distinct successive labels, failures in previous stages impose no restrictions on the remaining order after their successful labels have been revealed. Hence stage j j j has M = N − j + 1 M=N-j+1 M = N − j + 1 candidates.
Apply the first inequality to every stage in each chain. Every completed chain has completed all its stages. The queried candidates in these stages use disjoint portions of the total budget. Therefore
Q ≥ ∑ a = 1 m ∑ j = 1 q N − j + 2 2 Pr { stage ( a , j ) completes } ≥ q ( 2 N − q + 3 ) 4 E C Q ≥ N q 4 E C Q . \begin{aligned}
Q \ge\sum_{a=1}^{m}\sum_{j=1}^{q}\frac{N-j+2}{2}\Pr\{\text{stage }(a,j)\text{ completes}\} \\
&\ge\frac{q(2N-q+3)}{4}\mathbb{E}C_Q \ge\frac{Nq}{4}\mathbb{E}C_Q.
\end{aligned} Q ≥ a = 1 ∑ m j = 1 ∑ q 2 N − j + 2 Pr { stage ( a , j ) completes } ≥ 4 q ( 2 N − q + 3 ) E C Q ≥ 4 N q E C Q .
The conditional argument includes information obtained in other chains; it does not condition on the set of chains that eventually complete.
Lower bounds at coarse accuracy
A one-dimensional family gives an explicit lower bound when the target accuracy is a fixed fraction of the objective’s smoothness times its initial gap. The residuals in this family are analytic and the objective is convex. Thus these bounds do not require the delayed revelation used by the longer smooth chains.
Proposition 4.5 (Coarse-accuracy lower bounds). Let 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n , G = δ F 0 k / n G = \delta F_0\sqrt{k}/n G = δ F 0 k / n , and 0 < ϵ 2 < G / 2 0 < \epsilon^2 < G/2 0 < ϵ 2 < G /2 . Under Assumption 2.1 with Ω = 2 F 0 \Omega= 2F_0 Ω = 2 F 0 and L ≥ δ k / n L \ge\delta\sqrt{k}/n L ≥ δ k / n , the worst-case expected query cost of an admissible algorithm is at least
n + 1 2 ( 1 − 2 ϵ 2 G ) for unknown exceptional indices, \frac{n+1}{2}\left(1-\frac{2\epsilon^2}{G}\right) \qquad\text{for unknown exceptional indices,} 2 n + 1 ( 1 − G 2 ϵ 2 ) for unknown exceptional indices, k ( 1 − 2 ϵ 2 G ) for supplied exceptional indices. (22) k\left(1-\frac{2\epsilon^2}{G}\right) \qquad\text{for supplied exceptional indices.} \tag*{(22)} k ( 1 − G 2 ϵ 2 ) for supplied exceptional indices. (22) The bounds hold for convex objectives with analytic residual functions.
Proof. Put L 0 = δ k / n L_0 = \delta\sqrt{k}/n L 0 = δ k / n . First choose an index λ \lambda λ uniformly in [ n ] [n] [ n ] and, independently, a sign σ \sigma σ uniformly in { − 1 , 1 } \{-1,1\} { − 1 , 1 } . In one dimension define
A = n F 0 , b 2 = 2 A δ k , h ( x ) = L 0 x 2 4 , A = nF_0,\qquad b^2 = \frac{2A}{\delta\sqrt{k}},\qquad h(x) = \frac{L_0x^2}{4}, A = n F 0 , b 2 = δ k 2 A , h ( x ) = 4 L 0 x 2 ,
u λ ( x ) = − σ A sin ( x / b ) , u i = 0 ( i ≠ λ ) . u_\lambda(x) = -\sigma A\sin(x/b),\qquad u_i = 0\ (i \ne\lambda). u λ ( x ) = − σ A sin ( x / b ) , u i = 0 ( i = λ ) .
The objective Hessian is ( L 0 / 2 ) ( 1 + σ sin ( x / b ) ) (L_0/2)(1+\sigma\sin(x/b)) ( L 0 /2 ) ( 1 + σ sin ( x / b )) , which lies in [ 0 , L 0 ] [0,L_0] [ 0 , L 0 ] . The initial objective gap is at most A / n = F 0 A/n = F_0 A / n = F 0 , the total residual oscillation is 2 A = 2 n F 0 2A = 2nF_0 2 A = 2 n F 0 , and the residual gradient has Lipschitz constant A / b 2 = δ k / 2 A/b^2 = \delta\sqrt{k}/2 A / b 2 = δ k /2 . Thus every member belongs to the stated class.
We may give the algorithm the sign as additional information whenever it queries the exceptional component, including at a point where the queried residual gradient vanishes. Before this event all responses equal ∇ h \nabla h ∇ h , so the sign remains independent of its observations and its output. Write a = A / ( n b ) a=A/(nb) a = A / ( nb ) and y = x / b y=x/b y = x / b . Since L 0 b / 2 = a L_0b/2=a L 0 b /2 = a ,
E σ ∣ F ′ ( x ) ∣ 2 = a 2 ( y 2 + cos 2 y ) ≥ a 2 = G 2 , \mathbb{E}_{\sigma}|F'(x)|^2=a^2(y^2+\cos^2 y)\ge a^2=\frac{G}{2}, E σ ∣ F ′ ( x ) ∣ 2 = a 2 ( y 2 + cos 2 y ) ≥ a 2 = 2 G ,
where sin 2 y ≤ y 2 \sin^2 y\le y^2 sin 2 y ≤ y 2 . This inequality holds at every point. It therefore applies conditionally at any output returned before the exceptional index is queried. The required expected squared gradient norm implies that the probability of querying this index is at least 1 − 2 ϵ 2 / G 1-2\epsilon^2/G 1 − 2 ϵ 2 / G . Apply Lemma 4.4 with M = n M=n M = n to this search. The lemma extends to a random finite stopping time by applying it to finite budgets and taking monotone limits. This proves the first bound in (22) .
For supplied indices, use k k k scalar coordinates, independent signs σ 1 , … , σ k \sigma_1,\ldots,\sigma_k σ 1 , … , σ k , A = n F 0 / k A=nF_0/k A = n F 0 / k , and b 2 = 2 A / ( δ k ) b^2=2A/(\delta\sqrt{k}) b 2 = 2 A / ( δ k ) . Set
h ( x ) = L 0 4 ∥ x ∥ 2 , u i ( x ) = − σ i A sin ( x i / b ) ( i ≤ k ) , u i = 0 ( i > k ) . h(x)=\frac{L_0}{4}\lVert x\rVert^2,\qquad u_i(x)=-\sigma_i A\sin(x_i/b)\quad(i\le k),\qquad u_i=0\quad(i>k). h ( x ) = 4 L 0 ∥ x ∥ 2 , u i ( x ) = − σ i A sin ( x i / b ) ( i ≤ k ) , u i = 0 ( i > k ) .
The same calculations, now using orthogonal coordinates, verify all assumptions. Supply the exceptional indices and reveal a component’s sign on its first query. Conditional on the complete history, each unqueried sign remains independent and uniform. The expected squared gradient in its coordinate is at least G / ( 2 k ) G/(2k) G / ( 2 k ) , for any value of that coordinate at the output. If J J J distinct exceptional components are queried, then
E ∥ ∇ F ( x ^ ) ∥ 2 ≥ G 2 k ( k − E J ) . \mathbb{E}\lVert\nabla F(\widehat{x})\rVert^2\ge\frac{G}{2k}(k-\mathbb{E}J). E ∥ ∇ F ( x ) ∥ 2 ≥ 2 k G ( k − E J ) .
Since the query count is at least J J J , this proves the second bound. Both arguments average over fixed objective families; hence each expected lower bound is attained by some fixed member. □ \square □
Combining the bounds over the full accuracy range
Proposition 4.6 (Explicit minimax lower bounds). In the setting of Theorem 2.2 , put D = 1536 ⋅ 1024 D=1536\cdot1024 D = 1536 ⋅ 1024 . Write C u n k n o w n \mathcal{C}_{\mathrm{unknown}} C unknown and C s u p p l i e d \mathcal{C}_{\mathrm{supplied}} C supplied for the two minimax costs. For 0 < ϵ 2 ≤ δ F 0 k / ( 4 n ) 0<\epsilon^2\le\delta F_0\sqrt{k}/(4n) 0 < ϵ 2 ≤ δ F 0 k / ( 4 n ) ,
C s u p p l i e d ≥ 2 − 23 R , \mathcal{C}_{\mathrm{supplied}}\ge2^{-23}\mathcal{R}, C supplied ≥ 2 − 23 R , C u n k n o w n ≥ max { n + 1 4 , 2 − 23 R , 17 8192 D min { n k , P } } . (23) \mathcal{C}_{\mathrm{unknown}}\ge\max\left\{\frac{n+1}{4},2^{-23}\mathcal{R},\frac{17}{8192D}\min\{nk,\mathcal{P}\}\right\}. \tag*{(23)} C unknown ≥ max { 4 n + 1 , 2 − 23 R , 8192 D 17 min { nk , P } } . (23)
Proof of Proposition 4.6 and Theorem 2.2. Write C ∗ = 1024 C_*=1024 C ∗ = 1024 , D = 1536 C ∗ D=1536C_* D = 1536 C ∗ , and
G = δ F 0 k n , T = G ϵ 2 = R k , ϑ = k T = n k ϵ 2 δ F 0 = k 2 R = n k P . G=\frac{\delta F_0\sqrt{k}}{n},\qquad T=\frac{G}{\epsilon^2}=\frac{\mathcal{R}}{k},\qquad\vartheta=\frac{k}{T}=\frac{n\sqrt{k}\epsilon^2}{\delta F_0}=\frac{k^2}{\mathcal{R}}=\frac{nk}{\mathcal{P}}. G = n δ F 0 k , T = ϵ 2 G = k R , ϑ = T k = δ F 0 n k ϵ 2 = R k 2 = P nk .
The assumed accuracy range is T ≥ 4 T\ge4 T ≥ 4 . Larger ϑ \vartheta ϑ corresponds to coarser accuracy.
Selecting an upper bound Choosing the smaller of the two upper bounds in Section 3 gives O ( n + min { n k + R , P } ) O(n+\min\{nk+\mathcal{R},\mathcal{P}\}) O ( n + min { nk + R , P }) when Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 . Both terms in the minimum are at least of order n n n in the stated range. Adding the cost of constructing the predictors therefore preserves this order. Since P ≥ R \mathcal{P}\ge\mathcal{R} P ≥ R ,
min { n k + R , P } ≤ R + min { n k , P } ≤ 2 min { n k + R , P } . \min\{nk+\mathcal{R},\mathcal{P}\}\le\mathcal{R}+\min\{nk,\mathcal{P}\}\le2\min\{nk+\mathcal{R},\mathcal{P}\}. min { nk + R , P } ≤ R + min { nk , P } ≤ 2 min { nk + R , P } .
The accuracy lower bound If T ≥ D T \ge D T ≥ D , the parameter controlling chain length in Theorem 4.2 satisfies
A = T 768 ⋅ 512 = 4 T D ≥ 4. A = \frac{T}{768\cdot512} = \frac{4T}{D} \ge4. A = 768 ⋅ 512 T = D 4 T ≥ 4.
That theorem gives the bound 2 − 23 R 2^{-23}\mathcal{R} 2 − 23 R , even when the exceptional indices are supplied. Its residual functions have total oscillation at most 2 n F 0 2nF_0 2 n F 0 , as required. If 4 ≤ T < D 4 \le T < D 4 ≤ T < D , Proposition 4.5 gives a supplied-index lower bound of at least k / 2 k/2 k /2 . Since R = k T < D k \mathcal{R}=kT<Dk R = k T < D k and 1 / ( 2 D ) > 2 − 23 1/(2D)>2^{-23} 1/ ( 2 D ) > 2 − 23 , the same bound 2 − 23 R 2^{-23}\mathcal{R} 2 − 23 R follows. Supplying additional information cannot increase the minimax cost, so this lower bound also applies when the indices are unknown.
Coarse accuracy Proposition 4.5 gives C u n k n o w n ≥ ( n + 1 ) / 4 \mathcal{C}_{\mathrm{unknown}}\ge(n+1)/4 C unknown ≥ ( n + 1 ) /4 throughout the stated range. If T < 2 D T<2D T < 2 D , then P = n T < 2 D n \mathcal{P}=nT<2Dn P = n T < 2 D n , and hence
C u n k n o w n ≥ P 8 D ≥ 17 8192 D min { n k , P } . \mathcal{C}_{\mathrm{unknown}}\ge\frac{\mathcal{P}}{8D}\ge\frac{17}{8192D}\min\{nk,\mathcal{P}\}. C unknown ≥ 8 D P ≥ 8192 D 17 min { nk , P } .
It remains to prove the discovery term for T ≥ 2 D T\ge2D T ≥ 2 D , or equivalently ϑ ≤ k / ( 2 D ) \vartheta\le k/(2D) ϑ ≤ k / ( 2 D ) .
Fine and intermediate accuracy If ϑ ≤ 2 / D = 1 / ( 768 C ∗ ) \vartheta\le2/D=1/(768C_*) ϑ ≤ 2/ D = 1/ ( 768 C ∗ ) , the preceding discovery theorem gives C u n k n o w n ≥ 13 n k / 2048 \mathcal{C}_{\mathrm{unknown}}\ge13nk/2048 C unknown ≥ 13 nk /2048 . This implies the claimed discovery term in (4.6).
Parallel chains at coarser accuracy Suppose ϑ > 2 / D \vartheta>2/D ϑ > 2/ D , and choose
m = ⌈ D ϑ ⌉ , N = ⌊ n / m ⌋ , q = ⌊ k / m ⌋ . m=\lceil D\vartheta\rceil,\qquad N=\lfloor n/m\rfloor,\qquad q=\lfloor k/m\rfloor. m = ⌈ D ϑ ⌉ , N = ⌊ n / m ⌋ , q = ⌊ k / m ⌋ .
Here m m m is the number of parallel chains, N N N is the number of component indices available to each chain, and q q q is its length. The inequalities m N ≤ n mN\le n m N ≤ n and m q ≤ k mq\le k m q ≤ k preserve the upper bounds on the numbers of components and exceptions. Then
m ≤ 3 2 D ϑ , m ≤ k / 2 + 1 ≤ k , N ≥ q ≥ 1. m\le\frac{3}{2}D\vartheta,\qquad m\le k/2+1\le k,\qquad N\ge q\ge1. m ≤ 2 3 D ϑ , m ≤ k /2 + 1 ≤ k , N ≥ q ≥ 1.
Assign each chain a known group of N N N component indices and a known orthogonal coordinate block. Residual gradients at unused indices vanish identically. In block a a a , independently draw a uniformly distributed orthonormal q q q -frame V a V_a V a and a uniform ordered list ( λ a , 1 , … , λ a , q ) (\lambda_{a,1},\ldots,\lambda_{a,q}) ( λ a , 1 , … , λ a , q ) of distinct indices in its component group. There are k ′ = m q ≤ k k'=mq\le k k ′ = m q ≤ k exceptions.
Let d 1 , … , d q d_1,\ldots,d_q d 1 , … , d q be the links of Section 4.1 with chain length K = q K=q K = q , so c q = ∑ j d j c_q=\sum_jd_j c q = ∑ j d j . Set
α = n F 0 12 k , b 2 = C ∗ α δ k , R q = 230 q , ρ a ( y ) = y 1 + ∥ y ∥ 2 / R q 2 . \alpha=\frac{nF_0}{12k},\qquad b^2=\frac{C_*\alpha}{\delta\sqrt{k}},\qquad R_q=230\sqrt{q},\qquad\rho_a(y)=\frac{y}{\sqrt{1+\|y\|^2/R_q^2}}. α = 12 k n F 0 , b 2 = δ k C ∗ α , R q = 230 q , ρ a ( y ) = 1 + ∥ y ∥ 2 / R q 2 y .
and define the fixed random family
h ( x ) = α ∥ x ∥ 2 10 n b 2 , u λ a , j ( x ) = α d j ( V a T ρ a ( x a / b ) ) , h(x)=\frac{\alpha\|x\|^2}{10nb^2},\qquad u_{\lambda_{a,j}}(x)=\alpha d_j\left(V_a^{\mathsf T}\rho_a(x_a/b)\right), h ( x ) = 10 n b 2 α ∥ x ∥ 2 , u λ a , j ( x ) = α d j ( V a T ρ a ( x a / b ) ) ,
u i = 0 otherwise , f i = h + u i . u_i=0\ \text{otherwise},\qquad f_i=h+u_i. u i = 0 otherwise , f i = h + u i .
The objective still assigns weight one over n n n to every component. In particular,
F ( x ) = α n ∑ a = 1 m [ c q ( V a T ρ a ( x a / b ) ) + ∥ x a / b ∥ 2 10 ] . F(x)=\frac{\alpha}{n}\sum_{a=1}^{m}\left[c_q\left(V_a^{\mathsf T}\rho_a(x_a/b)\right)+\frac{\|x_a/b\|^2}{10}\right]. F ( x ) = n α a = 1 ∑ m [ c q ( V a T ρ a ( x a / b ) ) + 10 ∥ x a / b ∥ 2 ] .
Verifying the assumptions after rounding. The elementary link bounds from Lemma 4.1 are ∥ ∇ d j ∥ ≤ 2 3 \lVert\nabla d_j\rVert\le2^3 ∥ ∇ d j ∥ ≤ 2 3 , osc ( d j ) ≤ 2 4 \operatorname{osc}(d_j) \le2^4 osc ( d j ) ≤ 2 4 , and ∥ ∇ 2 d j ∥ o p ≤ 4 10 \lVert\nabla^2 d_j\rVert_{\mathrm{op}} \le4^{10} ∥ ∇ 2 d j ∥ op ≤ 4 10 ; each coordinate occurs in at most two links. Within each block, the chain-rule calculation used above bounds the Euclidean norm of the concatenated Hessian-vector products by
( 2 4 10 + 6 ⋅ 2 3 q R q ) ∥ v a ∥ < C ∗ ∥ v a ∥ . \left(\sqrt{2}\,4^{10}+\frac{6\cdot2^3\sqrt{q}}{R_q}\right)\lVert v_a\rVert< C_\ast\lVert v_a\rVert. ( 2 4 10 + R q 6 ⋅ 2 3 q ) ∥ v a ∥ < C ∗ ∥ v a ∥ .
The coordinate blocks are orthogonal, so summing ∥ v a ∥ 2 \lVert v_a\rVert^2 ∥ v a ∥ 2 across blocks gives ∥ v ∥ 2 \lVert v\rVert^2 ∥ v ∥ 2 , without a factor m m m . The chosen scale therefore gives the required residual smoothness bound k δ 2 ∥ x − y ∥ 2 k\delta^2\lVert x-y\rVert^2 k δ 2 ∥ x − y ∥ 2 with the supplied k k k , although only k ′ k' k ′ components are exceptional. The gap is at most 12 m q α / n = F 0 k ′ / k ≤ F 0 12mq\alpha/n=F_0k'/k\le F_0 12 m q α / n = F 0 k ′ / k ≤ F 0 . The objective Hessian is block diagonal and has norm at most 512 α / ( n b 2 ) ≤ L 0 512\alpha/(nb^2)\le L_0 512 α / ( n b 2 ) ≤ L 0 . Moreover
∥ r i ( x ) ∥ 2 ≤ 529 α 2 b 2 = 529 12 C ∗ δ n F 0 k , osc ( u i ) ≤ 24 α = 2 n F 0 k . \lVert r_i(x)\rVert^2\le\frac{529\alpha^2}{b^2}=\frac{529}{12C_\ast}\frac{\delta nF_0}{\sqrt{k}},
\qquad
\operatorname{osc}(u_i)\le24\alpha=\frac{2nF_0}{k}. ∥ r i ( x ) ∥ 2 ≤ b 2 529 α 2 = 12 C ∗ 529 k δ n F 0 , osc ( u i ) ≤ 24 α = k 2 n F 0 .
Consequently ∑ i osc ( u i ) ≤ 2 n F 0 k ′ / k ≤ 2 n F 0 \sum_i\operatorname{osc}(u_i)\le2nF_0k'/k\le2nF_0 ∑ i osc ( u i ) ≤ 2 n F 0 k ′ / k ≤ 2 n F 0 . All bounds hold on the whole space. The algorithm may know the partition, the unused indices, and the quadratic reference; this information does not change the argument.
Agreement for adaptively chosen queries. In each block, keep track of the successive links already revealed. The auxiliary oracle returns exact gradients on revealed indices and on the next index in each incomplete block, revealing its index and frame column on that query; for all other indices not yet revealed, it returns only ∇ h ( x ) \nabla h(x) ∇ h ( x ) . Define this process on all outcomes, and run the given algorithm while withholding the additional revelations. We next give an event on which its gradient responses agree with those of the actual oracle.
Let Q = ⌊ m N q / 64 ⌋ Q=\lfloor mNq/64\rfloor Q = ⌊ m N q /64 ⌋ . Give every coordinate block dimension
d 0 ≥ q + 1 + 8 R q 2 log ( 128 k ( Q + 1 ) ) . d_0\ge q+1+8R_q^2\log(128k(Q+1)). d 0 ≥ q + 1 + 8 R q 2 log ( 128 k ( Q + 1 )) .
Conditional on the auxiliary history, the unrevealed columns form a uniformly distributed orthonormal frame in the complement of the columns already revealed in their block. Under this conditioning, the frame is independent of the ranks of the unknown component indices. We do not condition this distribution on successful projection tests. At each query and at the output, test the projections onto the unrevealed columns. There are at most k ( Q + 1 ) k(Q+1) k ( Q + 1 ) tests. For each test, concentration for a uniformly distributed unit vector bounds the probability of projection magnitude at least 1 / 2 1/2 1/2 by 2 exp [ − ( d 0 − q − 1 ) / ( 8 R q 2 ) ] 2\exp[-(d_0-q-1)/(8R_q^2)] 2 exp [ − ( d 0 − q − 1 ) / ( 8 R q 2 )] . The probability that any test fails is at most 1 / 64 1/64 1/64 . If all tests succeed, the coordinate preceding each later link is unrevealed and has magnitude below 1 / 2 1/2 1/2 . That link and its gradient vanish near the query. The actual and auxiliary processes then have identical queries, responses, and outputs. This includes an arbitrary unqueried output and permits unbounded adaptive query points.
Searching across blocks in any adaptive order. Within a block, each successive label is conditionally uniform among its remaining indices. The all-failure continuation in Lemma 4.4 is independent of that label: replies from earlier links use already revealed directions, and other blocks have independent assignments and frames. The lemma therefore applies to the auxiliary process, including arbitrary switches between blocks. With C Q C_Q C Q the number of completed blocks, it gives
E C Q ≤ 4 Q N q ≤ m 16 , Pr { C Q ≥ m / 2 } ≤ 1 8 . \mathbb{E}C_Q\le\frac{4Q}{N_q}\le\frac{m}{16},
\qquad
\Pr\{C_Q\ge m/2\}\le\frac{1}{8}. E C Q ≤ N q 4 Q ≤ 16 m , Pr { C Q ≥ m /2 } ≤ 8 1 .
This argument holds for every q ≥ 1 q\ge1 q ≥ 1 . In particular, it does not require a union bound over subsets of completed blocks.
The gradient bound and random stopping times With probability at least 55/64, the actual and auxiliary processes agree and at least m / 2 m/2 m /2 blocks have unrevealed links. In each such block, the gradient bound of Lemma 4.1 gives ∥ ∇ a F ( x ^ ) ∥ > α / ( 2 n b ) \lVert\nabla_a F(\widehat{x})\rVert> \alpha/(2nb) ∥ ∇ a F ( x )∥ > α / ( 2 nb ) . Orthogonality yields
∥ ∇ F ( x ^ ) ∥ 2 > m α 2 8 n 2 b 2 = m δ F 0 96 C ∗ n k = 16 ϵ m 2 , ϵ m 2 = m δ F 0 D n k ≥ ϵ 2 . \lVert\nabla F(\widehat{x})\rVert^2 > \frac{m\alpha^2}{8n^2b^2} = \frac{m\delta F_0}{96C_*n\sqrt{k}} = 16\epsilon_m^2,\qquad\epsilon_m^2 = \frac{m\delta F_0}{Dn\sqrt{k}} \ge\epsilon^2. ∥ ∇ F ( x ) ∥ 2 > 8 n 2 b 2 m α 2 = 96 C ∗ n k m δ F 0 = 16 ϵ m 2 , ϵ m 2 = D n k m δ F 0 ≥ ϵ 2 .
Write N p a i d N_{\mathrm{paid}} N paid for the original algorithm’s total number of component-gradient queries. Let x ^ Q \widehat{x}_Q x Q denote the output of an almost-surely terminating algorithm run until return or immediately before a requested ( Q + 1 ) (Q+1) ( Q + 1 ) st gradient, with zero returned in the latter case. It agrees with the original output x ^ \widehat{x} x on { N p a i d ≤ Q } \{N_{\mathrm{paid}} \le Q\} { N paid ≤ Q } . The assumed bound on the expected squared gradient norm at x ^ \widehat{x} x and Markov’s inequality give
55 64 ≤ Pr { ∥ ∇ F ( x ^ Q ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr { N p a i d > Q } + 1 16 . \frac{55}{64} \le\Pr\{\lVert\nabla F(\widehat{x}_Q)\rVert^2 \ge16\epsilon^2\} \le\Pr\{N_{\mathrm{paid}} > Q\} + \frac{1}{16}. 64 55 ≤ Pr {∥ ∇ F ( x Q ) ∥ 2 ≥ 16 ϵ 2 } ≤ Pr { N paid > Q } + 16 1 .
Hence Pr { N p a i d > Q } ≥ 51 / 64 \Pr\{N_{\mathrm{paid}} > Q\} \ge51/64 Pr { N paid > Q } ≥ 51/64 . Using the integer query count avoids a restriction on the size of m N q mN_q m N q :
E N p a i d ≥ ( Q + 1 ) Pr { N p a i d > Q } ≥ 51 m N q 4096 . \mathbb{E}N_{\mathrm{paid}} \ge(Q+1)\Pr\{N_{\mathrm{paid}} > Q\} \ge\frac{51mN_q}{4096}. E N paid ≥ ( Q + 1 ) Pr { N paid > Q } ≥ 4096 51 m N q .
Since m N ≥ n / 2 mN \ge n/2 m N ≥ n /2 , m q ≥ k / 2 mq \ge k/2 m q ≥ k /2 , and m ≤ 3 D ϑ / 2 m \le3D\vartheta/2 m ≤ 3 D ϑ /2 , we obtain
E N p a i d ≥ 51 n k 16384 m ≥ 17 8192 D n k ϑ = 17 8192 D P . \mathbb{E}N_{\mathrm{paid}} \ge\frac{51nk}{16384m} \ge\frac{17}{8192D}\frac{nk}{\vartheta} = \frac{17}{8192D}\mathcal{P}. E N paid ≥ 16384 m 51 nk ≥ 8192 D 17 ϑ nk = 8192 D 17 P .
Averaging over the objective family gives a fixed member attaining this cost. Together with the coarse-accuracy and single-chain cases, this proves (23) . The maximum of its accuracy and discovery terms bounds a positive constant times R + min { n k , P } \mathcal{R} + \min\{nk,\mathcal{P}\} R + min { nk , P } , completing the lower bound in the main theorem. Different families may attain its separate terms; all belong to the same objective class.
Known exceptional indices and the accuracy ranges When the exceptional indices are supplied, the residual estimator costs O ( k + R ) O(k+\mathcal{R}) O ( k + R ) . It checks the exact gradient using only those indices, since all omitted residual gradients vanish identically. Since R ≥ 4 k \mathcal{R} \ge4k R ≥ 4 k , this is O ( R ) O(\mathcal{R}) O ( R ) ; the accuracy lower bound above gives a matching lower bound. If the query convention also requires querying all n n n components, the total cost is Θ ( n + R ) \Theta(n+\mathcal{R}) Θ ( n + R ) . Otherwise, this additional cost is absent. Finally, P = ( n / k ) R \mathcal{P}=(n/k)\mathcal{R} P = ( n / k ) R crosses n k nk nk at R = k 2 \mathcal{R}=k^2 R = k 2 , and R \mathcal{R} R crosses n k nk nk at R = n k \mathcal{R}=nk R = nk , which gives the stated accuracy ranges.
Constructing predictors from known loss functions
We construct predictors as mixtures of known loss gradients. This construction is related to mixture models for client distributions [15 ] , estimation from reference gradients [16 ] , and the use of moment equations to identify label shift [17 ] . The mixture assumption must hold at every point; the queries determine its coefficients.
Proposition 5.1 (Constructing predictors under a mixture assumption). Let r r r be a known differentiable regularizer and ψ 1 , … , ψ m \psi_1,\ldots,\psi_m ψ 1 , … , ψ m known differentiable losses, where m ≥ 2 m \ge2 m ≥ 2 . Write G ( x ) = [ ∇ ψ 1 ( x ) , … , ∇ ψ m ( x ) ] G(x)=[\nabla\psi_1(x),\ldots,\nabla\psi_m(x)] G ( x ) = [ ∇ ψ 1 ( x ) , … , ∇ ψ m ( x )] and Δ m = { θ ≥ 0 : 1 m T θ = 1 } \Delta_m=\{\theta\ge0:\mathbf{1}_m^{\mathsf{T}}\theta=1\} Δ m = { θ ≥ 0 : 1 m T θ = 1 } . Suppose that, outside an unknown set of at most k k k components,
∇ f i ( x ) = ∇ r ( x ) + G ( x ) θ i + e i ( x ) , θ i ∈ Δ m , sup x ∥ e i ( x ) ∥ ≤ ζ . \nabla f_i(x)=\nabla r(x)+G(x)\theta_i+e_i(x),\qquad\theta_i\in\Delta_m,\qquad\sup_x\lVert e_i(x)\rVert\le\zeta. ∇ f i ( x ) = ∇ r ( x ) + G ( x ) θ i + e i ( x ) , θ i ∈ Δ m , x sup ∥ e i ( x )∥ ≤ ζ .
For specified points z 1 , … , z q z_1,\ldots,z_q z 1 , … , z q and an orthonormal basis U ∈ R m × ( m − 1 ) U \in\mathbb{R}^{m \times(m-1)} U ∈ R m × ( m − 1 ) of 1 m ⊥ 1_m^\perp 1 m ⊥ , assume
D = q − 1 / 2 stack ℓ = 1 q G ( z ℓ ) , κ = σ min ( D U ) > 0 , H D = sup x ∥ G ( x ) U ∥ o p < ∞ . D=q^{-1/2}\operatorname{stack}_{\ell=1}^{q}G(z_\ell), \qquad\kappa=\sigma_{\min}(DU)>0, \qquad H_D=\sup_x\lVert G(x)U\rVert_{\mathrm{op}}<\infty. D = q − 1/2 stack ℓ = 1 q G ( z ℓ ) , κ = σ m i n ( D U ) > 0 , H D = x sup ∥ G ( x ) U ∥ op < ∞.
Here stack denotes vertical concatenation. Query every component at these points and set
y i = q − 1 / 2 stack ℓ = 1 q [ ∇ f i ( z ℓ ) − ∇ r ( z ℓ ) ] , θ ^ i = argmin θ ∈ Δ m ∥ D θ − y i ∥ 2 . y_i=q^{-1/2}\operatorname{stack}_{\ell=1}^{q}[\nabla f_i(z_\ell)-\nabla r(z_\ell)], \qquad\widehat{\theta}_i=\underset{\theta\in\Delta_m}{\operatorname{argmin}}\lVert D\theta-y_i\rVert^2. y i = q − 1/2 stack ℓ = 1 q [ ∇ f i ( z ℓ ) − ∇ r ( z ℓ )] , θ i = θ ∈ Δ m argmin ∥ D θ − y i ∥ 2 .
Set p i = r + ∑ j θ ^ i j ψ j p_i=r+\sum_j\widehat{\theta}_{ij}\psi_j p i = r + ∑ j θ ij ψ j , so that ∇ p i = ∇ r + G θ ^ i \nabla p_i=\nabla r+G\widehat{\theta}_i ∇ p i = ∇ r + G θ i . These predictors satisfy
∥ θ ^ i − θ i ∥ ≤ ζ / κ , sup x ∥ ∇ f i ( x ) − ∇ p i ( x ) ∥ ≤ ζ ( 1 + H D / κ ) \lVert\widehat{\theta}_i-\theta_i\rVert\leq\zeta/\kappa, \qquad\sup_x\lVert\nabla f_i(x)-\nabla p_i(x)\rVert\leq\zeta(1+H_D/\kappa) ∥ θ i − θ i ∥ ≤ ζ / κ , x sup ∥ ∇ f i ( x ) − ∇ p i ( x )∥ ≤ ζ ( 1 + H D / κ )
on every component satisfying the mixture assumption. Constructing these predictors costs C c a l = n q C_{\mathrm{cal}}=nq C cal = n q queries. In particular, ζ = 0 \zeta=0 ζ = 0 gives exact predictors outside at most k k k components.
Proof. Write θ = 1 m / m + U c \theta=1_m/m+Uc θ = 1 m / m + U c and let C C C denote the simplex in these coordinates. The least-squares fit projects y i − D 1 m / m y_i-D1_m/m y i − D 1 m / m onto the closed convex set D U C DUC D U C . The stacked observation error has norm at most ζ \zeta ζ . Projection does not increase Euclidean distances, so comparison with the true coefficient gives ∥ D U ( c ^ i − c i ) ∥ ≤ ζ \lVert DU(\widehat{c}_i-c_i)\rVert\leq\zeta ∥ D U ( c i − c i )∥ ≤ ζ . The smallest singular value of D U DU D U bounds the coefficient error, and e i ( x ) + G ( x ) U ( c i − c ^ i ) e_i(x)+G(x)U(c_i-\widehat{c}_i) e i ( x ) + G ( x ) U ( c i − c i ) is the prediction error. □
The condition κ > 0 \kappa>0 κ > 0 requires q d ≥ m − 1 qd\geq m-1 q d ≥ m − 1 , but this dimension inequality alone does not ensure that the coefficients can be recovered. With θ ‾ = n − 1 ∑ i θ ^ i \overline{\theta}=n^{-1}\sum_i\widehat{\theta}_i θ = n − 1 ∑ i θ i , the average predictor is ∇ h = ∇ r + G θ ‾ \nabla h=\nabla r+G\overline{\theta} ∇ h = ∇ r + G θ . Evaluating it uses m m m known loss gradients, which are uncharged in our query model. A component query may still require a full pass through that component’s data. The n q nq n q queries used to construct the predictors do not change the order of the main complexity bound when q q q is bounded independently of the problem parameters.
Bounds on residual oscillation and smoothness Suppose f i = r + L i f_i=r+L_i f i = r + L i for every component, with 0 ≤ L i , ψ j ≤ M 0\leq L_i,\psi_j\leq M 0 ≤ L i , ψ j ≤ M and L ℓ L_\ell L ℓ -Lipschitz loss gradients. Then
u i = L i − ∑ j θ ^ i j ψ j , osc ( u i ) ≤ 2 M , Lip ( ∇ u i ) ≤ 2 L ℓ . u_i=L_i-\sum_j\widehat{\theta}_{ij}\psi_j,\qquad\operatorname{osc}(u_i)\leq2M,\qquad\operatorname{Lip}(\nabla u_i)\leq2L_\ell. u i = L i − j ∑ θ ij ψ j , osc ( u i ) ≤ 2 M , Lip ( ∇ u i ) ≤ 2 L ℓ .
For ζ = 0 \zeta=0 ζ = 0 , only the exceptional components have nonconstant residual functions, giving Ω = 2 M k / n \Omega=2Mk/n Ω = 2 M k / n and δ = 2 L ℓ \delta=2L_\ell δ = 2 L ℓ . For ζ > 0 \zeta>0 ζ > 0 , the uniform prediction bound remains valid, but more than k k k residual gradients may be nonzero.
For example, take d ≥ m d\geq m d ≥ m , ψ j ( x ) = 1 2 ( tanh x j − 1 ) 2 \psi_j(x)=\frac{1}{2}(\tanh x_j-1)^2 ψ j ( x ) = 2 1 ( tanh x j − 1 ) 2 , and z 1 = 0 z_1=0 z 1 = 0 . Then G ( 0 ) = − [ e 1 , … , e m ] G(0)=-[e_1,\ldots,e_m] G ( 0 ) = − [ e 1 , … , e m ] , κ = 1 \kappa=1 κ = 1 , and H D ≤ 2 H_D\leq2 H D ≤ 2 . If every component loss, apart from its regularizer, is an average of 1 2 ( tanh ( a ⊤ x ) − y ) 2 \frac{1}{2}(\tanh(a^\top x)-y)^2 2 1 ( tanh ( a ⊤ x ) − y ) 2 with ∥ a ∥ ≤ 1 \lVert a\rVert\leq1 ∥ a ∥ ≤ 1 and y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } , valid bounds are M = 2 M=2 M = 2 and L ℓ = 5 L_\ell=5 L ℓ = 5 . With r = λ ∥ x ∥ 2 / 2 r=\lambda\lVert x\rVert^2/2 r = λ ∥ x ∥ 2 /2 , λ ≥ 0 \lambda\geq0 λ ≥ 0 , and x 0 = 0 x_0=0 x 0 = 0 , we may take L = λ + 5 L=\lambda+5 L = λ + 5 , F 0 = 1 / 2 F_0=1/2 F 0 = 1/2 , and δ = 10 \delta=10 δ = 10 . If the exact mixture assumption holds outside at most k ≤ n / 4 k\leq n/4 k ≤ n /4 components, then ∑ i osc ( u i ) ≤ 4 k ≤ 2 n F 0 \sum_i\operatorname{osc}(u_i)\leq4k\leq2nF_0 ∑ i osc ( u i ) ≤ 4 k ≤ 2 n F 0 .
Proposition 5.2 (Identifying analytic residuals with one query per component). Suppose the residual gradients r i r_i r i are real analytic on R d \mathbb{R}^d R d . Query every component at a common independent point drawn from a distribution with a Lebesgue density. Testing r i ( x ) = 0 r_i(x)=0 r i ( x ) = 0 identifies B B B almost surely. Under the other assumptions of Theorem 2.2, optimization then costs O ( C c a l + n + R ) O(C_{\mathrm{cal}}+n+\mathcal{R}) O ( C cal + n + R ) queries.
Proof. Each residual gradient that is not identically zero has a scalar coordinate that is a nonzero analytic function. Its zero set has Lebesgue measure zero [18 ] . The finite union of these zero sets also has measure zero. Proposition 3.4 then applies to the identified exceptional set, including the final exact gradient check. □
This result uses exact arithmetic. A positive detection threshold or noisy response does not give the same guarantee. The preceding analytic example therefore illustrates optimization after the exceptional components have been identified. The mixture assumption must still hold globally; these finitely many queries do not establish it.
A smooth loss with flat regions The same predictor construction permits smooth losses that are constant on open sets. Define
ℓ ( s ) = { exp ( 1 − ( 1 − 2 s ) − 2 ) , s < 1 / 2 , 0 , s ≥ 1 / 2. \ell(s) =
\begin{cases}
\exp\left(1 - (1 - 2s)^{-2}\right), & s < 1/2,\\
0, & s \ge1/2.
\end{cases} ℓ ( s ) = { exp ( 1 − ( 1 − 2 s ) − 2 ) , 0 , s < 1/2 , s ≥ 1/2.
This C ∞ C^{\infty} C ∞ loss takes values in [ 0 , e ] [0,e] [ 0 , e ] and satisfies ℓ ( 0 ) = 1 \ell(0)=1 ℓ ( 0 ) = 1 , ℓ ′ ( 0 ) = − 4 \ell'(0)=-4 ℓ ′ ( 0 ) = − 4 , ∥ ℓ ′ ′ ∥ ∞ ≤ 54 / e \|\ell''\|_{\infty} \le\sqrt{54/e} ∥ ℓ ′′ ∥ ∞ ≤ 54/ e , and ∥ ℓ ′ ′ ′ ∥ ∞ < 33 \|\ell'''\|_{\infty} < 33 ∥ ℓ ′′′ ∥ ∞ < 33 . For ψ j ( x ) = ℓ ( x j ) \psi_j(x)=\ell(x_j) ψ j ( x ) = ℓ ( x j ) and d ≥ m d \ge m d ≥ m , the origin gives κ = 4 \kappa=4 κ = 4 and H D ≤ 54 / e H_D \le\sqrt{54/e} H D ≤ 54/ e . Let each L i L_i L i be an average of ℓ ( y a ⊤ x ) \ell(y a^\top x) ℓ ( y a ⊤ x ) with ∥ a ∥ ≤ 1 \|a\| \le1 ∥ a ∥ ≤ 1 and y ∈ { − 1 , 1 } y \in\{-1,1\} y ∈ { − 1 , 1 } . Assume that each L i L_i L i is an exact mixture of the known losses, except on at most k k k components. With f i = λ ∥ x ∥ 2 / 2 + L i f_i=\lambda\|x\|^2/2+L_i f i = λ ∥ x ∥ 2 /2 + L i , λ ≥ 0 \lambda\ge0 λ ≥ 0 , valid bounds at x 0 = 0 x_0=0 x 0 = 0 are
C c a l = n , L = λ + 33 , δ = 66 , F 0 = 1 , ∑ i osc ( u i ) ≤ 2 e k . \mathcal{C}_{\mathrm{cal}}=n,\qquad L=\lambda+33,\qquad\delta=66,\qquad F_0=1,\qquad\sum_i \operatorname{osc}(u_i)\le2ek. C cal = n , L = λ + 33 , δ = 66 , F 0 = 1 , i ∑ osc ( u i ) ≤ 2 e k .
Thus k ≤ n / e k \le n/e k ≤ n / e gives the required bound on the sum of residual oscillations. For an exceptional component, take m = d = 2 m=d=2 m = d = 2 and
L i ( x ) = ℓ ( x 1 + x 2 2 ) , u i ( x ) = L i ( x ) − ℓ ( x 1 ) + ℓ ( x 2 ) 2 . L_i(x)=\ell\left(\frac{x_1+x_2}{2}\right),\qquad u_i(x)=L_i(x)-\frac{\ell(x_1)+\ell(x_2)}{2}. L i ( x ) = ℓ ( 2 x 1 + x 2 ) , u i ( x ) = L i ( x ) − 2 ℓ ( x 1 ) + ℓ ( x 2 ) .
Fitting the coefficients from a query at the origin gives ( 1 / 2 , 1 / 2 ) (1/2,1/2) ( 1/2 , 1/2 ) and ∇ u i ( 0 ) = 0 \nabla u_i(0)=0 ∇ u i ( 0 ) = 0 . Although ∇ u i ( 2 , 0 ) = 2 e 2 \nabla u_i(2,0)=2e_2 ∇ u i ( 2 , 0 ) = 2 e 2 , both u i u_i u i and its gradient vanish on { x 1 > 1 / 2 , x 2 > 1 / 2 } \{x_1>1/2,x_2>1/2\} { x 1 > 1/2 , x 2 > 1/2 } . A random query point that has positive probability of lying in this open set can fail to detect the exception. Thus a smooth mixture model can have residual gradients for which the identification guarantee for analytic functions does not apply.
Numerical experiments
We examine delayed identification of exceptional components and optimization once their indices have been found. The first study below tests the adaptive working-set method against baselines that use all support information they acquire. A separate regression study changes the representation of a fixed objective after its exceptional indices are identified. We distinguish component queries, optimization steps, and private gradient work.
Delayed discovery with nonzero estimator error
We first examine whether adapting the batch size helps when exceptions become visible at different stages of optimization. Every method starts without the exceptional indices, except for a separately reported supplied-support comparison. The component residuals vanish at the initial point, so an initial scan cannot identify them.
Objective and valid bounds Let x ∈ R x \in\mathbb{R} x ∈ R , x 0 = 0 x_0 = 0 x 0 = 0 , and h ( x ) = ( x − 1 ) 2 / 2 h(x) = (x-1)^2/2 h ( x ) = ( x − 1 ) 2 /2 . Define
q ( z ) = { 0 , z ≤ 0 , 10 z 3 − 15 z 4 + 6 z 5 , 0 < z < 1 , 1 , z ≥ 1. q(z) =
\begin{cases}
0, & z \le0, \\
10z^3 - 15z^4 + 6z^5, & 0 < z < 1, \\
1, & z \ge1.
\end{cases} q ( z ) = ⎩ ⎨ ⎧ 0 , 10 z 3 − 15 z 4 + 6 z 5 , 1 , z ≤ 0 , 0 < z < 1 , z ≥ 1.
The k k k exceptional components form J J J equal groups, with indices chosen uniformly without replacement from [ n ] [n] [ n ] . For group j ∈ { 0 , … , J − 1 } j \in\{0,\ldots,J-1\} j ∈ { 0 , … , J − 1 } , put
t j = j + 1 2 , T j = j + J + 3 , g j ( x ) = q ( 4 ( x − t j ) ) − q ( 4 ( x − T j ) ) . t_j = j + \frac{1}{2}, \qquad T_j = j + J + 3, \qquad g_j(x) = q(4(x-t_j))-q(4(x-T_j)). t j = j + 2 1 , T j = j + J + 3 , g j ( x ) = q ( 4 ( x − t j )) − q ( 4 ( x − T j )) .
Within each group, components occur in pairs. Draw a weight in [ 0.9 , 1.1 ] [0.9,1.1] [ 0.9 , 1.1 ] and a phase in [ 0 , 2 π ] [0,2\pi] [ 0 , 2 π ] uniformly and independently for each pair. Give its two members equal weights and phases and opposite signs σ i ∈ { − 1 , 1 } \sigma_i \in\{-1,1\} σ i ∈ { − 1 , 1 } . Normalize the weights w i w_i w i to sum to one in each group. For a component in group j j j , set
r i ( x ) = − n w i g j ( x ) ( 1 + β σ i sin ( x + ϕ i ) ) , β = 0.3 , (24) r_i(x) = -n w_i g_j(x)(1+\beta\sigma_i \sin(x+\phi_i)), \qquad\beta= 0.3, \tag*{(24)} r i ( x ) = − n w i g j ( x ) ( 1 + β σ i sin ( x + ϕ i )) , β = 0.3 , (24)
and let u i u_i u i be its integral, equal to zero below t j t_j t j . Other residual functions vanish. All predictors are p i = h p_i=h p i = h . The paired sine terms cancel in the group sum. Consequently
F ′ ( x ) = x − 1 − ∑ j = 0 J − 1 g j ( x ) . F'(x) = x-1-\sum_{j=0}^{J-1}g_j(x). F ′ ( x ) = x − 1 − j = 0 ∑ J − 1 g j ( x ) .
which is independent of n n n , the hidden indices, the weights, and the phases. Exceptions in group j j j are zero for x ≤ t j x \le t_j x ≤ t j and become visible near the partial stationary point j + 1 j+1 j + 1 . The later decrease of g j g_j g j to zero makes each residual potential bounded.
The following global bounds are supplied to the methods:
L = 8.5 , δ = n k 11 9 [ 7.5 ( 1 + β ) J + β J ] , L = 8.5, \qquad\delta= \frac{n}{k}\frac{11}{9}\left[7.5(1+\beta)\sqrt{J}+\beta J\right], L = 8.5 , δ = k n 9 11 [ 7.5 ( 1 + β ) J + β J ] ,
Ω = ( 1 + β ) J ( J + 2.5 ) , F 0 = 1 2 + Ω . (25) \Omega= (1+\beta)J(J+2.5), \qquad F_0 = \frac{1}{2}+\Omega. \tag*{(25)} Ω = ( 1 + β ) J ( J + 2.5 ) , F 0 = 2 1 + Ω. (25)
Indeed, 0 ≤ q ′ ≤ 15 / 8 0 \le q' \le15/8 0 ≤ q ′ ≤ 15/8 , the transition intervals are disjoint, and w i ≤ ( 11 / 9 ) J / k w_i \le(11/9)J/k w i ≤ ( 11/9 ) J / k . The derivative of the stacked residual vector has norm at most n ( 11 / 9 ) [ 7.5 ( 1 + β ) J / k + β J / k ] n(11/9)[7.5(1+\beta)\sqrt{J/k}+\beta J/\sqrt{k}] n ( 11/9 ) [ 7.5 ( 1 + β ) J / k + β J / k ] , which gives the stated δ \delta δ . Each residual function is nonpositive and monotone, with oscillation at most ( 1 + β ) n w i ( T j − t j ) (1+\beta)nw_i(T_j-t_j) ( 1 + β ) n w i ( T j − t j ) . Summing gives Ω \Omega Ω , and F ≥ − Ω F \ge-\Omega F ≥ − Ω gives F 0 F_0 F 0 . Thus Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 . Every full-complement check adds complete groups because the factors in parentheses in (6.1) lie in [ 0.7 , 1.3 ] [0.7,1.3] [ 0.7 , 1.3 ] . Each working set is therefore a union of complete groups. The sine terms cancel in every partial objective the working-set methods can form, giving the global bound L ‾ = 8.5 \overline{L}=8.5 L = 8.5 for these objectives. Arbitrary subsets would instead require the larger valid bound 1 + 7.5 ( 1 + β ) + β J 1+7.5(1+\beta)+\beta J 1 + 7.5 ( 1 + β ) + β J .
Methods and information The adaptive method A is Theorem 3.3 with η = 1 / ( 2 L ‾ ) = 1 / 17 \eta=1/(2\overline{L})=1/17 η = 1/ ( 2 L ) = 1/17 and p = min { 1 , 2 η δ k / n } p=\min\{1,2\eta\delta\sqrt{k}/n\} p = min { 1 , 2 η δ k / n } . Its expected batch size is η δ k ∣ S ∣ / n \eta\delta\sqrt{k}|S|/n η δ k ∣ S ∣/ n . F uses the same working set, recomputation probability, stepsize, and exclusive choice between recomputation and sampled differences, with the fixed expected batch size η δ k k / n \eta\delta\sqrt{kk}/n η δ k k / n . GD recomputes the working-set gradient at every step. The final comparison uses its standard full step η = 1 / L ‾ = 1 / 8.5 \eta=1/\overline{L}=1/8.5 η = 1/ L = 1/8.5 , justified by the exact-gradient descent bound in § 3.3 . These three methods use the same full-complement discovery rule, the threshold ϵ \epsilon ϵ , reuse of already queried gradients, and immediate certification once ∣ S ∣ = k |S|=k ∣ S ∣ = k . P uses population sampling from Proposition 3.4 , with η = 1 / 17 \eta=1/17 η = 1/17 . It records every observed nonzero residual, including both endpoints of sampled differences, and restricts sampling to the support at the next exact recomputation once k k k exceptions are known. The supplied-support method O is given the true indices before its first query; it is excluded from comparisons between methods with equal information. We also rerun A with the more conservative choice η = 1 / [ 2 ( L + H ) ] \eta= 1/[2(L + H)] η = 1/ [ 2 ( L + H )] to measure the effect of the supplied partial smoothness bound.
Study sequence and measurement We conducted five sequential studies, fixing each source, protocol, and set of evaluation seeds before running that study. The first used constant residual gradients between discoveries: eight settings, eight methods, and twelve seeds gave 768 outcomes. The second introduced the paired sine terms and retained the conservative tracking stepsize: five settings, five methods, and twelve new seeds gave 300 outcomes. Its estimator errors were nonzero, and its adaptive method used more queries than GD in all five settings. The third used the supplied partial smoothness bound: six methods on another twelve seeds gave 360 outcomes. That comparison used η = 1 / 17 \eta= 1/17 η = 1/17 for both tracking and GD. We then added GD with its larger valid step 1 / 8.5 1/8.5 1/8.5 on the same sixty instances. This changed the comparison: full-step GD used fewer queries than A in every instance. All preceding protocols and results are retained.
The first three studies use k = 32 k = 32 k = 32 . The third has n ∈ { 256 , 2048 } n \in\{256, 2048\} n ∈ { 256 , 2048 } crossed with J ∈ { 4 , 8 } J \in\{4, 8\} J ∈ { 4 , 8 } , together with n = k = 32 n = k = 32 n = k = 32 , J = 4 J = 4 J = 4 . Its development seeds are 51410, 51411 and its evaluation seeds are 51600, … \ldots … , 51611; the GD addendum uses the same evaluation seeds. The earlier studies have disjoint seed sets.
The remaining study tests the predicted dependence on support size. At fixed J J J and n / k = 8 n/k = 8 n / k = 8 , the residual scale δ k / n \delta\sqrt{k/n} δ k / n and recomputation probability are proportional to k − 1 / 2 k^{-1/2} k − 1/2 , while L = 8.5 L = 8.5 L = 8.5 stays fixed. Before running new evaluation seeds, we fixed k ∈ { 128 , 512 } k \in\{128, 512\} k ∈ { 128 , 512 } , n = 8 k n = 8k n = 8 k , J ∈ { 4 , 8 } J \in\{4, 8\} J ∈ { 4 , 8 } , and the four methods A, F, full-step GD, and P. Twelve new seeds, 51700, … \ldots … , 51711, give 192 outcomes. No parameter grid was tuned on those outcomes. For J = 8 J = 8 J = 8 , the recomputation probabilities at k = 32 , 128 , 512 k = 32, 128, 512 k = 32 , 128 , 512 are approximately 0.762, 0.381, and 0.191. Their expected update costs per visit, as fractions of exact recomputation on S S S , are ( 2 − p ) p (2 - p)p ( 2 − p ) p , approximately 0.943, 0.617, and 0.345. The total cost also depends on the steps and discovery checks.
Across all studies, ϵ = 10 − 4 \epsilon= 10^{-4} ϵ = 1 0 − 4 and the optimizer’s random seed is the instance seed plus 9871. Each run allows 10 5 10^5 1 0 5 steps and 2000 n 2000n 2000 n queries. No method uses momentum or line search. All 1680 outcomes pass a paid full-gradient certificate; none reaches a limit. Independent evaluation of the explicit formula for F ′ F' F ′ verifies every returned point. The code, protocols, seeds, and individual outcomes accompany the manuscript.
Every component query is charged, including initial queries, both endpoints of a sampled difference, repeated indices, and final certificates. We separately count evaluations of residual gradients on exceptional components as private work. This count assumes no caching and does not measure execution time. Clipped polynomial evaluations give exact zeros in the designed inactive regions; the implementation tests a response against zero in double precision. Estimator-error calculations are performed only after a run and do not inform optimization.
Results and limits Table 2 reports all nine settings with full-step GD. Adaptive batching reduces mean queries relative to fixed batching in every setting. Its comparison with GD depends on the residual scale. GD uses fewer queries in all five k = 32 k = 32 k = 32 settings and at k = 128 k = 128 k = 128 , J = 8 J = 8 J = 8 , where A costs 23.9% more. A uses 3.4% fewer queries at k = 128 k = 128 k = 128 , J = 4 J = 4 J = 4 , and 41.7% and 23.0% fewer at k = 512 k = 512 k = 512 , J = 4 J = 4 J = 4 and J = 8 J = 8 J = 8 , respectively. Each comparison holds in all twelve paired runs of its setting. P costs least in the dense case. These results distinguish the benefit of adapting the batch from the separate choice between stochastic estimation and exact gradients.
Table 2. Paid queries with full-step GD: mean (empirical standard deviation), rounded to the nearest query, over twelve paired seeds per setting. A adapts the batch size, F fixes it, GD uses exact working-set gradients, and P samples the population and then the identified support. A, F, and P use η = 1 / 17 \eta= 1/17 η = 1/17 ; GD uses η = 1 / 8.5 \eta= 1/8.5 η = 1/8.5 . The five k = 32 k = 32 k = 32 rows combine the third study with its paired GD addendum; the four larger-support rows use new seeds in the final study. All returned points have gradient norm at most 10 − 4 10^{-4} 1 0 − 4 .
Every run of A discovers one complete group at each failed check, so the observed number of discovery stages is D = J D = J D = J . Its complementary scans use exactly J n − k ( J − 1 ) / 2 Jn - k(J - 1)/2 J n − k ( J − 1 ) /2 queries. Individual sampled differences and estimator errors are nonzero. The exact recomputations and terminal checks remain essential even on this controlled family. The preceding studies retain both the common-stepsize results and the unfavorable results for the conservative tracking stepsize.
Figure 1 compares query and private-work costs at fixed n / k = 8 n/k = 8 n / k = 8 . At n = 4096 n = 4096 n = 4096 , k = 512 k = 512 k = 512 , J = 8 J = 8 J = 8 , A averages 155,118.3 queries and 126,446.3 private residual evaluations, compared with 262,789.0 queries and 58,041.7 private evaluations for P. A saves 41.0% of the requests while performing 2.18 times as much private residual work. It averages 1409.8 steps, compared with 324.2 for P and 666 for full-step GD. Against GD, A reduces queries by 23.0% and private residual evaluations by 26.8%. The supplied-support comparison remains separate: for example, at n = 2048 n = 2048 n = 2048 , k = 32 k = 32 k = 32 , J = 8 J = 8 J = 8 , O averages 9728.3 queries when its exceptional indices are supplied initially.
Figure 1. Queries and private residual work divided by the cost of full-step working-set GD, for all settings with n / k = 8 n/k = 8 n / k = 8 . Bars show arithmetic means over twelve paired seeds; error bars show one empirical standard deviation divided by the deterministic GD cost. Ratios below one indicate lower cost. A and F use η = 1 / 17 \eta= 1/17 η = 1/17 ; GD uses η = 1 / 8.5 \eta= 1/8.5 η = 1/8.5 . Population sampling may use fewer private evaluations even when it makes more component requests. The table also includes the dense case and the two settings with n / k = 64 n/k = 64 n / k = 64 .
These examples satisfy the main theorem’s accuracy condition, but do not approximate its worst-case high-dimensional constructions. They are one-dimensional, use exact gradient access and a supplied partial smoothness bound, and have a partial residual sum that is constant between activation intervals. The sine terms test nonzero component differences and estimator error while cancelling in the full objective. The results establish a benefit for the specified discovery mechanism and parameter choice; they do not establish performance on general regression data, noisy residuals, or distributed implementations.
Regression objective and protocol
Proposition 6.1 (Changing the components without changing the objective). Let ∥ a j ∥ ≤ 1 \lVert a_j\rVert\le1 ∥ a j ∥ ≤ 1 , ϕ j ( x ) = 1 2 tanh 2 ( a j T x − b j ) \phi_j(x) = \frac{1}{2}\tanh^2(a_j^\mathsf{T}x - b_j) ϕ j ( x ) = 2 1 tanh 2 ( a j T x − b j ) , and h ( x ) = μ 2 ∥ x − c ∥ 2 h(x) = \frac{\mu}{2}\lVert x - c\rVert^2 h ( x ) = 2 μ ∥ x − c ∥ 2 , where μ > 1 / 3 \mu> 1/3 μ > 1/3 . For 2 ≤ k ≤ n 2 \le k \le n 2 ≤ k ≤ n with k ∣ M k \mid M k ∣ M , choose A ⊆ [ n ] A \subseteq[n] A ⊆ [ n ] , ∣ A ∣ = k |A| = k ∣ A ∣ = k , and partition M M M examples into equal blocks ( B i ) i ∈ A (B_i)_{i\in A} ( B i ) i ∈ A . Define
φ i = k M ∑ j ∈ B i ϕ j , u i = n k φ i ( i ∈ A ) , u i = 0 ( i ∉ A ) . \varphi_i = \frac{k}{M}\sum_{j\in B_i}\phi_j,\qquad u_i = \frac{n}{k}\varphi_i\quad(i\in A),\qquad u_i = 0\quad(i\notin A). φ i = M k j ∈ B i ∑ ϕ j , u i = k n φ i ( i ∈ A ) , u i = 0 ( i ∈ / A ) .
The true exceptional set satisfies B ⊆ A \mathcal{B} \subseteq A B ⊆ A . With p i = h p_i = h p i = h , the objective F = h + M − 1 ∑ j ϕ j F = h + M^{-1}\sum_j \phi_j F = h + M − 1 ∑ j ϕ j is independent of n n n , k k k , and the partition. Valid bounds are
L = μ + 1 , δ = n / k , Ω = 1 / 2 , F 0 = μ 2 ∥ x 0 − c ∥ 2 + 1 / 2. L = \mu+ 1,\qquad\delta= n/k,\qquad\Omega= 1/2,\qquad F_0 = \frac{\mu}{2}\lVert x_0-c\rVert^2 + 1/2. L = μ + 1 , δ = n / k , Ω = 1/2 , F 0 = 2 μ ∥ x 0 − c ∥ 2 + 1/2.
The objective is ( μ − 1 / 3 ) (\mu- 1/3) ( μ − 1/3 ) -strongly convex, and the partial objective for every working set is ( μ + 1 ) (\mu+ 1) ( μ + 1 ) -smooth.
Proof. The scalar loss has range [ 0 , 1 / 2 ) [0,1/2) [ 0 , 1/2 ) and second derivative ( 1 − t 2 ) ( 1 − 3 t 2 ) ∈ [ − 1 / 3 , 1 ] (1-t^2)(1-3t^2) \in[-1/3,1] ( 1 − t 2 ) ( 1 − 3 t 2 ) ∈ [ − 1/3 , 1 ] , where t = tanh z t=\tanh z t = tanh z . Hence − I / 3 ⪯ ∇ 2 ϕ j ⪯ I -I/3 \preceq\nabla^2\phi_j \preceq I − I /3 ⪯ ∇ 2 ϕ j ⪯ I ; averaging proves the objective and smoothness statements. Each residual function has oscillation at most n / ( 2 k ) n/(2k) n / ( 2 k ) and gradient Lipschitz constant at most n / k n/k n / k . Summing these bounds proves the residual assumptions. Nonnegativity of F F F gives the bound on the initial objective gap.
We use M = 1024 M=1024 M = 1024 , d = 4 d=4 d = 4 , μ = 0.5 \mu=0.5 μ = 0.5 , c = x 0 = 0 c=x_0=0 c = x 0 = 0 , and ϵ = 10 − 4 \epsilon=10^{-4} ϵ = 1 0 − 4 . Each feature is the vector e 1 + 0.25 z j e_1+0.25z_j e 1 + 0.25 z j , z j ∼ N ( 0 , I ) z_j\sim N(0,I) z j ∼ N ( 0 , I ) , normalized to have unit norm. Half the targets have mean 0.05 and half have mean 0.7, with independent N ( 0 , 0.015 2 ) N(0,0.015^2) N ( 0 , 0.01 5 2 ) perturbations. Thus L = 1.5 L=1.5 L = 1.5 and F 0 = Ω = 0.5 F_0=\Omega=0.5 F 0 = Ω = 0.5 . Outputs that pass the gradient check lie within 6 × 10 − 4 6\times10^{-4} 6 × 1 0 − 4 of the unique minimizer and have objective gap at most 3 × 10 − 8 3\times10^{-8} 3 × 1 0 − 8 .
A clustered partition sorts the examples by target value and divides them into consecutive blocks. A mixed partition assigns the sorted examples to blocks in cyclic order. We vary n ∈ { 128 , 512 , 2048 , 8192 } n\in\{128,512,2048,8192\} n ∈ { 128 , 512 , 2048 , 8192 } with k = 64 k=64 k = 64 and clustered blocks, and compare both partitions for k ∈ { 16 , 64 , 256 } k\in\{16,64,256\} k ∈ { 16 , 64 , 256 } at n = 2048 n=2048 n = 2048 . One configuration occurs in both comparisons, giving nine distinct settings. For each data seed, all settings use the same examples and objective. Increasing n n n adds components whose residual gradients vanish and rescales the nonzero residual functions. The bound δ = n / k \delta=n/k δ = n / k therefore changes with the number of components.
Methods and stopping. This regression comparison fixes each method’s sampling domain to separate the cost of estimating a residual sum from the cost of querying zero residuals. Its population methods continue to sample all components even after the initial scan identifies the support. The comparison in § 6.1 allows population sampling to use that information and switch to the identified support. Every method first queries all n n n components at x 0 x_0 x 0 . P-GD applies gradient descent using all components at each step; S-GD applies gradient descent using the identified exceptions. S-Track and P-Track use the estimator in Proposition 3.4 , sampling from the k k k identified exceptions and all n n n components, respectively. Between exact recomputations, they update an estimate of the residual gradient sum using sampled differences. These four methods use η = 1 / ( 2 L ) = 1 / 3 \eta=1/(2L)=1/3 η = 1/ ( 2 L ) = 1/3 . The fifth method, P-One, uses the same population estimator with at most one sampled difference per step and η = min { 1 / ( 2 L ) , 1 / ( ℓ A n ) } \eta=\min\{1/(2L),1/(\ell_A\sqrt{n})\} η = min { 1/ ( 2 L ) , 1/ ( ℓ A n )} . For a sampling set of size m m m , the estimator parameters are
ℓ A = m k δ / n , p A = min { 1 , 2 η ℓ A / m } , τ A = η ℓ A m . \ell_A=\sqrt{mk\delta}/n,\qquad p_A=\min\{1,2\eta\ell_A/\sqrt{m}\},\qquad\tau_A=\eta\ell_A\sqrt{m}. ℓ A = mk δ / n , p A = min { 1 , 2 η ℓ A / m } , τ A = η ℓ A m .
The samples and independent Bernoulli variables that decide which differences to evaluate follow Proposition 3.4 . S-GD and S-Track use the identified set only if the initial scan finds k k k nonzero residual gradients, reaching the supplied upper bound on their number. Otherwise, they use all components. The initial queries identify all k k k exceptions in every run. The threshold for detecting a nonzero residual gradient is 10 − 13 10^{-13} 1 0 − 13 . A method stops only after an exact gradient check finds a norm at most ϵ \epsilon ϵ , initially or after a later exact recomputation. No method uses momentum or line search. We count evaluations at both points of every sampled difference, including repeated component indices. The final check uses the gradient already computed.
Repetitions and resources We evaluate all five methods in all nine settings with the same eight data seeds, 43100, . . . , 43107. The protocol was fixed using the separate seeds 42100, 42101. NumPy 2.0.2’s default generator draws features followed by target noise. For data seed s s s , another generator with seed s + 1009 k s + 1009k s + 1009 k randomly permutes max { 128 , 2 k } \max\{128, 2k\} max { 128 , 2 k } component positions and assigns the data blocks to the first k k k positions in that permutation. The optimizer knows neither these positions nor the restriction used to choose them. Random choices within each method use seed s + 781 s + 781 s + 781 . Each run allows 200,000 steps and 2000 n 2000n 2000 n queries. All 360 runs pass the stopping gradient check. Full gradients computed after each run independently verify the outputs and do not inform any iteration. We report arithmetic means and observed ranges across seeds; these summaries are descriptive.
A query to a component containing a data block requires M / k M/k M / k example gradient evaluations. A query to a component containing no data block evaluates only the known gradient ∇ h \nabla h ∇ h . We count repeated evaluations separately even when the simulator combines repeated requests to the same index. This count describes the computations required when each request is evaluated separately; it does not measure simulator runtime, communication, or evaluations of the known functions.
Query savings after identifying the exceptions
Table 3 includes the common initial scan. After these initial 2048 queries, the mean additional counts are 43,264 for P-GD, 1352 for S-GD, and 603.5 for S-Track. The first reduction avoids queries to zero residual gradients. The second avoids repeatedly summing all exceptional residual gradients. S-Track uses 22.0% fewer total queries than S-GD and 86.7% fewer than P-Track, with more steps than S-GD. Its mean count of example-gradient evaluations is 52.9% lower than that of S-GD.
Table 3. Clustered blocks, n = 2048 n = 2048 n = 2048 , k = 64 k = 64 k = 64 : means [minimum–maximum] over eight seeds. Queries include the initial scan and final gradient check. The last column gives the mean count of example-gradient evaluations, counting repeated evaluations separately.
For each data seed, adding components whose residual gradients vanish leaves the iterates and query count of S-GD unchanged after the initial scan. The same statement holds separately for S-Track. The mean total counts are n + 1352 n + 1352 n + 1352 for S-GD and n + 603.5 n + 603.5 n + 603.5 for S-Track. The relative saving therefore decreases from 50.6% at n = 128 n = 128 n = 128 to 7.8% at n = 8192 n = 8192 n = 8192 , where the initial scan accounts for 93.1% of S-Track’s cost.
Both estimators recompute their complete residual gradient sums with probability p = min { 1 , 2 n / k } p = \min\{1, 2n/\sqrt{k}\} p = min { 1 , 2 n / k } . Conditional on making no exact recomputation, their expected numbers of sampled differences are τ s = n k \tau_s = n\sqrt{k} τ s = n k and τ p = n / k \tau_p = n/\sqrt{k} τ p = n / k . Thus the expected query counts per step satisfy c s = k p + 2 ( 1 − p ) τ s c_s = kp + 2(1-p)\tau_s c s = k p + 2 ( 1 − p ) τ s and c p = ( n / k ) c s c_p = (n/k)c_s c p = ( n / k ) c s . Each exact recomputation evaluates all M M M examples. A component sampled uniformly from all n n n components contains a data block with probability k / n k/n k / n . The two methods therefore have the same expected count of example-gradient evaluations per step. Their total counts can differ because they stop at different times.
Effects of partitioning and batching
Table 4 reports all nine settings. Both gradient descent methods take 21.125 steps on average in every setting, giving mean query costs 22.125 n 22.125n 22.125 n for P-GD and n + 21.125 k n + 21.125k n + 21.125 k for S-GD. Across the six partition settings, S-Track reduces mean total queries relative to S-GD by 6.9–46.6%.
Table 4. All nine settings: mean queries for S-Track and P-Track; q q q is the ratio of mean P-Track to P-One queries, and t t t is the ratio of mean P-One to P-Track steps. C and M denote clustered and mixed blocks. V V V measures variation among component gradient changes, as defined in the text; its entries are averaged over seeds.
To compare gradient changes across components at a fixed pair of points, set x = 0 x = 0 x = 0 , y = 0.2 e 1 y = 0.2e_1 y = 0.2 e 1 , D i = ∇ ϕ i ( y ) − ∇ ϕ i ( x ) D_i = \nabla\phi_i(y) - \nabla\phi_i(x) D i = ∇ ϕ i ( y ) − ∇ ϕ i ( x ) , and V = k − 1 ∑ i ∥ D i − k − 1 ∑ j D j ∥ 2 V = k^{-1}\sum_i \lVert D_i - k^{-1}\sum_j D_j \rVert^2 V = k − 1 ∑ i ∥ D i − k − 1 ∑ j D j ∥ 2 . Mixing reduces mean V V V by factors of 9.5–151.7, but at k = 256 k = 256 k = 256 raises S-Track’s mean queries from 3985.0 to 4126.5. The estimator randomly omits some candidate differences. Its variance therefore also depends on the squared norms of the individual gradient changes, before their mean is subtracted. Its stopping time depends on when exact recomputations occur. A smaller value of V V V at this pair of points consequently need not give a smaller total query count.
For the clustered setting with n = 2048 n = 2048 n = 2048 and k = 64 k = 64 k = 64 , batching allows the stepsize to increase from 1/256 to 1/3 and reduces mean steps from 6551.1 to 53.5. It reduces mean steps in every setting, by factors of 4.8–399.4, and mean queries in seven settings. Queries instead increase by 3.9% and 5.0% at n = 128 n = 128 n = 128 and n = 512 n = 512 n = 512 . The theorem permits larger steps while retaining the same order of query bound. The experiments show that the number of queries can nevertheless increase on some instances.
In these analytic, strongly convex instances, the initial scan identifies all exceptional components. The results illustrate optimization after this identification and the effect of dividing an objective among components. They do not test the worst-case cost of finding exceptions in the broader smooth class, noisy gradients, data from applications, or the running time of a distributed implementation.
Conclusion
We characterize the query cost of finite-sum optimization when at most k k k residual gradients are nonzero functions and their total oscillation is bounded. Unknown exceptional indices contribute the additional term min { n k , P } \min\{nk, \mathcal{P}\} min { nk , P } to the optimization cost R \mathcal{R} R . A common potential controls changes of the partial objective, and an adaptive working-set method chooses its batch size from the components already discovered. Its bound depends on the actual support size and number of discovery stages, without requiring either quantity as input. The lower bounds permit arbitrary adaptive queries. Interrupted searches handle parallel chains of any positive length, while bounded sinusoidal examples. extend the matching-order result to ϵ 2 ≤ δ F 0 k / ( 4 n ) \epsilon^2 \le\delta F_0\sqrt{k}/(4n) ϵ 2 ≤ δ F 0 k / ( 4 n ) .
The delayed-discovery experiments give every competitive method access to the support information that its queries acquire. Adaptive batches reduce queries relative to fixed batches in every setting of the final comparison. Their advantage over exact gradients appears when the residual scale is sufficiently small relative to partial-objective smoothness; full-step gradient descent wins several other settings. Population sampling costs less in the dense setting and uses less private residual work. The separate regression study illustrates optimization after the indices are identified. These resource comparisons do not imply faster distributed execution.
The complexity characterization assumes exact residual gradients, free predictor evaluations, and Ω ≤ 2 F 0 \Omega\le2F_0 Ω ≤ 2 F 0 . The lower-bound dimension may grow with the parameters, and its explicit constants do not determine numerical crossover points. The delayed examples are one-dimensional and have structured partial objectives; their sharper smoothness bound is supplied. Questions remaining include approximate or noisy residuals, unknown partial smoothness, dependence on Ω \Omega Ω independently of F 0 F_0 F 0 , and the cost of evaluating the predictors.
Declarations
Generative AI tools assisted literature search, formulation and revision of mathematical arguments, implementation of research checks, and manuscript editing. The authors assume responsibility for all content.
References