Exact oracle complexity for function-value suboptimality under weighted initial conditions
Abstract
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≥2N+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 bound and a constant-memory first-order method, ITEM-wf (previously called ITEM-w), whose worst-case performance matches this lower bound. On the standard initial conditions, the result recovers the exact convex bound attained by the Optimized Gradient Method of Kim and Fessler, and establishes the minimax optimality of the recently introduced ITEM-f method of Kim, Ryu, and Das Gupta for the initial function-value condition.
Related
- An adaptive weighted extrapolation neural network for dispersive shock waves generated by square-root initial condition of the KdV equation
- Maximal Monotone Differential Inclusions with Volterra and One-Sided Lipschitz Perturbations under Nonlocal Initial Conditions and Applications
- Randomness from initial conditions: The challenge of incompleteness
- Edge complexity of weighted graphs: involutory symmetries and NP-hardness
- Polynomial Initial-State Jumps and Christoffel Transforms in Krylov Complexity
BibTeX
@misc{drori2026exact,
title = {{Exact oracle complexity for function-value suboptimality under weighted initial conditions}},
author = {Yoel Drori},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.33360},
eprint = {2609.33360},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33360},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact oracle complexity for function-value suboptimality under weighted initial conditions
AU - Yoel Drori
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2609.33360
UR - https://arxiv.org/abs/2609.33360
AB - 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≥2N+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 bound and a constant-memory first-order method, ITEM-wf (previously called ITEM-w), whose worst-case performance matches this lower bound. On the standard initial conditions, the result recovers the exact convex bound attained by the Optimized Gradient Method of Kim and Fessler, and establishes the minimax optimality of the recently introduced ITEM-f method of Kim, Ryu, and Das Gupta for the initial function-value condition.
ER -