Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order QueriesResearch Paper
Classical oracle complexity counts how many exact first-order answers — a value and a subgradient — a method needs to minimize a convex function. With exact real answers, queries suffice in dimension , attained by the center of gravity method and by modern cutting-plane methods. A computer, however, reads…