{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}