betaFeedback

WorksMathematics

The Query Complexity of Unknown Sparse Gradient Residuals

Abstract

We study optimization of an average of nn functions when gradient predictions are exact except for at most kk unknown components. An initial scan may miss these exceptions. For a class of smooth problems, we prove that the optimal worst-case expected number of component-gradient evaluations needed to find an approximate stationary point is Θ ⁣(min⁡{nk+R,nkR}), Θ\!\left(\min\left\{nk+\mathcal R,\frac nk\mathcal R\right\}\right), where R\mathcal R represents the optimal cost when the exceptional components are known. Prediction evaluations are free. This bound shows that discovering even a few exceptions can cost more than one full scan and can account for most of the gradient evaluations.

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∈RdF(x),F(x)=1n∑i=1nfi(x)=h(x)+1n∑i=1nui(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)}

For component ii, a known differentiable function pip_i predicts the gradient through ∇pi\nabla p_i. Write h=n−1∑ipih=n^{-1}\sum_i p_i, ui=fi−piu_i=f_i-p_i, and ri=∇uir_i=\nabla u_i. We call uiu_i the residual function and rir_i its residual gradient. At most kk residual gradients are nonzero as functions; their coordinates need not be sparse. One query returns ∇fi(x)\nabla f_i(x) at a chosen index and point. Subtracting the known ∇pi(x)\nabla p_i(x) gives ri(x)r_i(x). Predictor evaluations are not counted. Every component retains weight 1/n1/n, including after an exception is found.

We assume that FF is smooth, its initial gap is at most F0F_0, and

∑i∥ri(x)−ri(y)∥2≤kδ2∥x−y∥2,∑iosc⁡(ui)≤2nF0.\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.

Here osc⁡(ui)=sup⁡ui−inf⁡ui\operatorname{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⁡{nk+R,nkR}),R=k3/2δF0nϵ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}.

The theorem covers ϵ2≤δF0k/(4n)\epsilon^2\le\delta F_0\sqrt{k}/(4n). The terms change order at the scales k2k^2 and nknk in R\mathcal{R}. When nn is much larger than kk, these distinguish sampling the population, finding exceptions, and optimizing their sum. If n=kn=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}). Table 1 specifies the information supplied and the queries counted in each comparison.

Residual classInformation and requirementsQuery bound
SmoothIndices unknownΘ(min⁡{nk+R,P})\Theta(\min\{nk+\mathcal{R},\mathcal{P}\})
SmoothIndices suppliedΘ(R)\Theta(\mathcal{R})
SmoothIndices supplied; nn required queriesΘ(n+R)\Theta(n+\mathcal{R})
Real analyticIndices unknownO(n+R)O(n+\mathcal{R})

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 kk 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_* and the number DD of checks that discover new components:

EQ≤(n+2k∗)(ED+1)+8k∗kδ(F0+Ω)nϵ2.\mathbb{E}Q\le(n+2k_*)(\mathbb{E}D+1)+\frac{8k_*\sqrt{k}\delta(F_0+\Omega)}{n\epsilon^2}.

Neither k∗k_* nor DD 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}) upper bound. We also construct predictors with 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 mm components, the residual estimator has mean-square smoothness parameter δmk/n\delta\sqrt{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 fi:Rd→Rf_i:\mathbb{R}^d \to\mathbb{R}, let pi:Rd→Rp_i:\mathbb{R}^d \to\mathbb{R} be a known differentiable function whose gradient predicts ∇fi\nabla f_i. Define

h=1n∑ipi,ui=fi−pi,ri=∇ui,F=h+1n∑iui.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.

The exceptional set, also called the support of the residual gradients, is B={i:ri≠0}\mathcal{B} = \{i:r_i \ne0\}. Even for i∈Bi \in\mathcal{B}, rir_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,F0,δ>0L, F_0, \delta> 0, Ω>0\Omega> 0 and 1≤k≤n1 \le k \le n satisfy F(x0)−inf⁡F≤F0F(x_0)-\inf F \le F_0, ∇F\nabla F is LL-Lipschitz, and ∣B∣≤k|\mathcal{B}| \le k. Writing Wi=sup⁡ui−inf⁡uiW_i = \sup u_i-\inf u_i, assume

1n∑i∈BWi≤Ω,(2)\frac{1}{n}\sum_{i\in\mathcal{B}} W_i \le\Omega, \tag*{(2)}

and, for all x,y∈Rdx,y \in\mathbb{R}^{d},

∑i∈B∥ri(x)−ri(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)}

The individual WiW_i and the set BB are not supplied.

Condition (3) permits an individual residual gradient to have Lipschitz constant as large as δk\delta\sqrt{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 ii and a point xx and returns the exact vector ∇fi(x)\nabla 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 CcalC_{\mathrm{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 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, 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+fi−pi=h+ui\widetilde{f}_i=h+f_i-p_i=h+u_i have the same average FF. One query to fif_i gives a gradient of f~i\widetilde{f}_i through ∇f~i=∇fi−∇pi+∇h\nabla\widetilde{f}_i=\nabla f_i-\nabla p_i+\nabla h. The reverse calculation also uses one query. The residual gradients, exceptional set, smoothness bounds, and oscillations are unchanged. We may therefore use fi=h+uif_i=h+u_i in the analysis even when the original predictors differ.

References

  1. [1]R. Tibshirani, J. Bien, J. Friedman, T. Hastie, N. Simon, J. Taylor, and R. J. Tibshirani, Strong rules for discarding predictors in lasso-type problems, J. R. Stat. Soc. Ser. B Stat. Methodol., 74 (2012), pp. 245–266, https://doi.org/10.1111/j.1467-9868.2011.01004.x.
  2. [2]T. B. Johnson and C. Guestrin, Blitz: A principled meta-algorithm for scaling sparse optimization, Proc. Mach. Learn. Res., 37 (2015), pp. 1171–1179, https://proceedings.mlr.press/v37/johnson15.html.
  3. [3]T. B. Johnson and C. Guestrin, A fast, principled working set algorithm for exploiting piecewise linear structure in convex problems, arXiv:1807.08046, 2018, https://arxiv.org/abs/1807.08046.
  4. [4]A. Rakotomamonjy, R. Flamary, J. Salmon, and G. Gasso, Convergent working set algorithm for Lasso with non-convex sparse regularizers, Proc. Mach. Learn. Res., 151 (2022), pp. 5196–5211, https://proceedings.mlr.press/v151/rakotomamonjy22a.html.
  5. [5]Z. Li, H. Bao, X. Zhang, and P. Richtárik, PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization, Proc. Mach. Learn. Res., 139 (2021), pp. 6286–6295, https://proceedings.mlr.press/v139/li21a.html.arxiv.org/abs/2008.10898
  6. [6]C. Fang, C. J. Li, Z. Lin, and T. Zhang, SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator, Adv. Neural Inf. Process. Syst., 31 (2018). Full version: arXiv:1807.01695v2, 17 October 2018, https://arxiv.org/abs/1807.01695v2.
  7. [7]E. Gorbunov, K. P. Burlachenko, Z. Li, and P. Richtárik, MARINA: Faster non-convex distributed learning with compression, Proc. Mach. Learn. Res., 139 (2021), pp. 3788–3798, https://proceedings.mlr.press/v139/gorbunov21a.html.arxiv.org/abs/2102.07845
  8. [8]D. Kovalev, A. Beznosikov, E. Borodich, A. Gasnikov, and G. Scutari, Optimal gradient sliding and its application to optimal distributed optimization under similarity, Adv. Neural Inf. Process. Syst., 35 (2022), pp. 33494–33507, https://doi.org/10.52202/068431–2427.
  9. [9]A. Khaled and C. Jin, Faster federated optimization under second-order similarity, in Proceedings of the International Conference on Learning Representations, 2023, https://arxiv.org/abs/2209.02257.
  10. [10]D. Lin, Y. Han, H. Ye, and Z. Zhang, Stochastic distributed optimization under average second-order similarity: Algorithms and analysis, Adv. Neural Inf. Process. Syst., 36 (2023), pp. 1849–1862, https://doi.org/10.52202/075280–0089.
  11. [11]X. Jiang, A. Rodomanov, and S. U. Stich, Non-convex federated optimization under cost-aware client selection, in Proceedings of the International Conference on Learning Representations, 2026, https://proceedings.iclr.cc/paper_files/paper/2026/hash/65798a76cc176c29b6bfefe84b0a03ff–Abstract–Conference.html.arxiv.org/abs/2512.05327
  12. [12]Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, Lower bounds for finding stationary points I, Math. Program., 184 (2020), pp. 71–120, https://doi.org/10.1007/s10107–019–01406–y. Full version: arXiv:1710.11606v3, 15 August 2019, https://arxiv.org/abs/1710.11606v3.
  13. [13]Y. Han, G. Xie, and Z. Zhang, Lower complexity bounds of finite-sum optimization problems: The results and construction, J. Mach. Learn. Res., 25 (2024), article 2, pp. 1–86, https://jmlr.org/papers/v25/21–0264.html.
  14. [14]Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth, Lower bounds for non-convex stochastic optimization, Math. Program., 199 (2023), pp. 165–214, https://doi.org/10.1007/s10107–022–01822–7.
  15. [15]O. Marfoq, G. Neglia, A. Bellet, L. Kameni, and R. Vidal, Federated multi-task learning under a mixture of distributions, Adv. Neural Inf. Process. Syst., 34 (2021), pp. 15434–15447, https://arxiv.org/abs/2108.10252.
  16. [16]L. Wang, S. Xu, X. Wang, and Q. Zhu, Addressing class imbalance in federated learning, Proc. AAAI Conf. Artif. Intell., 35 (2021), pp. 10165–10173, https://doi.org/10.1609/aaai.v35i11.17219.
  17. [17]Z. C. Lipton, Y.-X. Wang, and A. J. Smola, Detecting and correcting for label shift with black box predictors, Proc. Mach. Learn. Res., 80 (2018), pp. 3122–3130, https://proceedings.mlr.press/v80/lipton18a.html.arxiv.org/abs/1802.03916
  18. [18]B. S. Mityagin, The zero set of a real analytic function, Math. Notes, 107 (2020), pp. 529–530, https://doi.org/10.1134/S0001434620030189.
  19. [19]Q. Zhou, Near-optimal complexity of finding approximate local minima of nonconvex finite sums, arXiv:2611.05807v1, 2026, https://arxiv.org/abs/2611.05807v1.
  20. [20]Y. Peng, Z. Tang, and W. Jia, Dense weak hiding: Closing complexity gaps in nonconvex and PL finite-sum optimization under individual smoothness, arXiv:2609.00045v3, 2026, https://arxiv.org/abs/2609.00045v3.

Paper details

vlnc:W_552pch2h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

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

  • Mathematics

Generative AI tools

View statement
Looking for related papers…
Contents