nips nips2012 nips2012-241 nips2012-241-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Brendan Mcmahan, Matthew Streeter
Abstract: Some of the most compelling applications of online convex optimization, including online prediction and classification, are unconstrained: the natural feasible set is Rn . Existing algorithms fail to achieve sub-linear regret in this setting unless constraints on the comparator point ˚ are known in advance. We present algox rithms that, without such prior knowledge, offer near-optimal regret bounds with respect to any choice of ˚. In particular, regret with respect to ˚ = 0 is constant. x x We then prove lower bounds showing that our guarantees are near-optimal in this setting. 1
[1] Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In COLT, 2008.
[2] Amit Agarwal, Elad Hazan, Satyen Kale, and Robert E. Schapire. Algorithms for portfolio management based on the Newton method. In ICML, 2006.
[3] Nicol` Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge Unio versity Press, New York, NY, USA, 2006. ISBN 0521841089.
[4] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In COLT, 2010.
[5] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. In COLT, 2008.
[6] Elad Hazan and Satyen Kale. On stochastic and worst-case models for investing. In Advances in Neural Information Processing Systems 22. 2009.
[7] Robert A. Jacobs. Increased rates of convergence through learning rate adaptation. Neural Networks, 1987.
[8] Jyrki Kivinen and Manfred Warmuth. Exponentiated Gradient Versus Gradient Descent for Linear Predictors. Journal of Information and Computation, 132, 1997.
[9] Todd K. Leen and Genevieve B. Orr. Optimal stochastic search and adaptive momentum. In NIPS, 1993.
[10] H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT, 2010.
[11] Barak Pearlmutter. Gradient descent: Second order momentum and saturating error. In NIPS, 1991.
[12] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012.
[13] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, 2003. 9