Paperlane

no. 14 · Friday 13 November 2026

The Query Complexity of Unknown Sparse Gradient Residuals

Yuriy Dorn

math.OC

Abstract

We study optimization of an average of \(n\) functions when gradient predictions are exact except for at most \(k\) 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 \[ Θ\!\left(\min\left\{nk+\mathcal R,\frac nk\mathcal R\right\}\right), \] where \(\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.

fields
Optimization and Control
pdf ↗ page arXiv:2611.16638 ↗