Tight Lower Bounds for Binary First-Order Oracles for Convex Optimization

Amitabh Basu, Phillip Kerger, Marco Molinaro

We establish new lower-bounds for the information complexity of mixed-integer convex optimization under two "bit-wise" oracles. The first oracle provides bits of first-order inform…