Information-theoretic lower bounds on the oracle complexity of sparse convex optimization
Published on Jan 13, 20114028 Views
Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Recent years have seen a surge in