Exact oracle complexity for function-value suboptimality under weighted initial conditions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.33360
curl -X POST /api/v1/records/arxiv/2609.33360/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.33360/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'