Lower Bound for Randomized First Order Convex Optimization

Abstract

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 Lipschitz function.

8 pages

Cited by in corpus (1)

• Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory