Comment by okintheory

"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.