Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

Benjamin Grimmer, Ning Liu

We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smo…