{"id":"arxiv/2609.33360","url":"https://arxiv.org/abs/2609.33360","tags":["math.OC"],"score":0,"title":"Exact oracle complexity for function-value suboptimality under weighted initial conditions","domain":"math.OC","source":"arxiv","authors":["Yoel Drori"],"reviews":0,"subject":"math.OC","summary":"We determine the exact worst-case function-value suboptimality after $N$ first-order oracle calls on $L$-smooth, $μ$-strongly convex functions under a nonnegative weighted combination of the initial squared distance, function-value suboptimality, and squared gradient norm. Excluding the case where no strict improvement in function-value suboptimality can be guaranteed, the exact deterministic minimax risk in dimension $d\\geq2N+1$ is characterized by the unique solution of a single scalar equation involving an $N$-step recurrence. The proof constructs an explicit hard instance for the lower…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}