Advances in Neural Information Processing Systems 22 (NIPS 2009) The papers below appear in Advances in Neural Information Processing Systems 22 edited by Y. Bengio and D. Schuurmans and J.D. Lafferty and C.K.I. Williams and A. Culotta. They are proceedings from the conference, "Neural Information Processing Systems 2009." Information-theoretic lower bounds on the oracle complexity of convex optim