@incollection{NIPS2009_1005,
 title = {Information-theoretic lower bounds on the oracle complexity of convex optimization},
 author = {Alekh Agarwal and Peter  Bartlett and Pradeep Ravikumar and Martin Wainwright},
 booktitle = {Advances in Neural Information Processing Systems 22},
 editor = {Y. Bengio and D. Schuurmans and J. Lafferty and C. K. I. Williams and A. Culotta},
 pages = {1--9},
 year = {2009}
}