Id: arxiv/2611.16638 Url: https://arxiv.org/abs/2611.16638 Tags: math.OC Score: 0 Title: The Query Complexity of Unknown Sparse Gradient Residuals Domain: math.OC Source: arxiv Authors: Yuriy Dorn Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.16638 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…