nips nips2009 nips2009-116 nips2009-116-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alekh Agarwal, Martin J. Wainwright, Peter L. Bartlett, Pradeep K. Ravikumar
Abstract: Despite a large literature on upper bounds on complexity of convex optimization, relatively less attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining a understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight minimax complexity estimates for various function classes. We also discuss implications of these results for the understanding the inherent complexity of large-scale learning and estimation problems. 1
[1] D.P. Bertsekas. Nonlinear programming. Athena Scientific, Belmont, MA, 1995.
[2] L. Birg´ . Approximation dans les espaces metriques et theorie de l’estimation. Z. Wahrsch. e verw. Gebiete, 65:181–327, 1983.
[3] L. Bottou and O. Bousquet. The tradeoffs of large scale learning. In NIPS. 2008.
[4] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, UK, 2004. 8
[5] R. Z. Has’minskii. A lower bound on the risks of nonparametric estimates of densities in the uniform metric. Theory Prob. Appl., 23:794–798, 1978.
[6] J. Matousek. Lectures on discrete geometry. Springer-Verlag, New York, 2002.
[7] A. S. Nemirovski. Efficient methods in convex programming. Lecture notes.
[8] A. S. Nemirovski and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley UK/USA, 1983.
[9] S. Shalev-Shwartz and N. Srebro. SVM optimization: inverse dependence on training set size. In ICML, 2008.
[10] Nesterov Y. Introductory lectures on convex optimization: Basic course. Kluwer Academic Publishers, 2004.
[11] B. Yu. Assouad, Fano and Le Cam. In Festschrift in Honor of L. Le Cam on his 70th Birthday. Springer-Verlag, 1993. 9