Preprint
Jul 2026
Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization
This work proves the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization, and develops a posterior mean energy method for adaptive exact max observations.
Haihan Zhang, Chen-Heng Zhang, Zhiquan Qi et al.
· 1 citation