Lower Bound for Randomized First Order Convex Optimization

Blake Woodworth, Nathan Srebro

We provide an explicit construction and direct proof for the lower bound on the number of first order oracle accesses required for a randomized algorithm to minimize a convex Lipsc…