Comment by okintheory
11 hours ago
"A strict complexity gap between gradient-based and derivative-free Lipschitz convex optimization" has been known for decades. It's covered in standard textbooks like Nesterov's "Introductory lectures on convex optimization". That AI result is about establishing the gap in a fairly niche accuracy regime.
Thanks for the correction, I had a feeling that should be true but the headline was at top of search results and I'm not close enough to the field to know off the top of my head.