Parallel First-Order Optimization in One Dimension: A Tight Round–Width Tradeoff via Moment Shielding

Abstract

How much can simultaneous queries replace adaptive rounds in optimization? On an interval, gradient signs give a simple benchmark: q queries divide a bracket into q + 1 pieces. Exact numerical replies need not respect this picture; two simultaneous gradients already determine any strongly convex quadratic. We show that the search benchmark is nevertheless minimax optimal over C∞ (infinitely differentiable) objectives with a fixed curvature range. For every fixed κ = L/μ > 1, the optimal number of rounds for δ-accurate minimizer localization is Θ_κ(max{1, log(1/δ)/log(q + 1)}), uniformly in the integer batch width q ≥ 1 at sufficiently small δ, even for randomized algorithms receiving exact function values and gradients. The construction uses a compactly supported smooth perturbation that is linear on the interval reserved for the next level. This preserves curvature bounds at every finite depth and makes all descendants agree exactly outside their active interval. A fixed uniform prior then limits the conditional information of one batch to log₂q + 3 bits. The same tradeoff holds on the larger C² class and for objective-gap accuracy. A known-coordinate restriction transfers the lower bound to every dimension without changing the condition number, but supplies no dimension dependence. The contribution is an exact smooth-oracle realization of the classical parallel-search law, with a self-contained randomized lower-bound proof.