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

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 information in the standard
coordinate model, and the second oracle answers whether the inner product of a specified vector with the gradient of the function at a point or
the normal vector of a separating hyperplane for the feasible region is
positive or non-positive, thus also providing one bit of first-order information. The new contribution is that under such oracles, the complexity is quadratic in the number of continuous decision variables, which
was not known before even for continuous convex optimization. These
new lower-bounds are tight (up to a logarithmic term), matched by a
natural discretization of standard cutting-plane methods for convex optimization. These reveal that using a standard bit-representation of the
first-order information is, in general, the best one can do with respect
to the number of bits of information needed to solve constrained convex
optimization problems.