nips nips2010 nips2010-222 nips2010-222-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hariharan Narayanan, Alexander Rakhlin
Abstract: We propose a computationally efficient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efficient method for implementing mixture forecasting strategies. 1
[1] J. Abernethy, A. Agarwal, P. L. Bartlett, and A. Rakhlin. A stochastic view of optimal regret through minimax duality. In COLT ’09, 2009.
[2] J. Abernethy, P. L. Bartlett, and A. Rakhlin. Multitask learning with expert advice. In Proceedings of The Twentieth Annual Conference on Learning Theory, pages 484–498, 2007.
[3] J. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of The Twenty First Annual Conference on Learning Theory, 2008.
[4] K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43(3):211–246, June 2001.
[5] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3):167–175, 2003.
[6] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities using the entropy method. 31:1583– 1614, 2003.
[7] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[8] V. Dani, T. P. Hayes, and S. Kakade. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems 20. Cambridge, MA, 2008.
[9] M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1–17, 1991.
[10] S. Kakade and A. Ng. Online bounds for Bayesian algorithms. In Proceedings of Neural Information Processing Systems (NIPS 17), 2005.
[11] A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. The Journal of Machine Learning Research, 3:440, 2003.
[12] A.T. Kalai and S. Vempala. Simulated annealing for convex optimization. Mathematics of Operations Research, 31(2):253–266, 2006.
[13] R. Kannan and H. Narayanan. Random walks on polytopes and an affine interior point method for linear programming. In STOC, 2009. Accepted (pending revisions), Mathematics of Operations Research.
[14] V. R. Konda and J. N. Tsitsiklis. Linear stochastic approximation driven by slowly varying markov chains. Systems and Control Letters, 50:95–102, 2003.
[15] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994.
[16] L. Lov´ sz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. a Random Structures and Algorithms, 4(4):359–412, 1993.
[17] L. Lov´ sz and S. Vempala. Simulated annealing in convex bodies and an o∗ (n4 ) volume algorithm. J. a Comput. Syst. Sci., 72(2):392–417, 2006.
[18] L. Lov´ sz and S. Vempala. The geometry of logconcave functions and sampling algorithms. Random a Struct. Algorithms, 30(3):307–358, 2007.
[19] H. Narayanan. Randomized interior point methods for sampling and optimization. CoRR, abs/0911.3950, 2009.
[20] A.S. Nemirovskii. Interior point polynomial time methods in convex programming, 2004.
[21] Y. E. Nesterov and A. S. Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994.
[22] Y.E. Nesterov and MJ Todd. On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Foundations of Computational Mathematics, 2(4):333–361, 2008.
[23] A. Rakhlin. Lecture notes on online learning, 2008. http://stat.wharton.upenn.edu/˜rakhlin/papers/online learning.pdf.
[24] D. Shah and J. Shin. Dynamics in congestion games. In Proceedings of ACM Sigmetrics, 2010.
[25] S. Shalev-Shwartz and Y. Singer. Convex repeated games and fenchel duality. In NIPS. 2007.
[26] S. Vempala. Geometric random walks: A survey. In Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ, 52:577–616, 2005.
[27] V. Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 372–383. Morgan Kaufmann, 1990.
[28] V. Vovk. Competitive on-line statistics. International Statistical Review, 69:213–248, 2001.
[29] K. Yamanishi. Minimax relative loss analysis for sequential prediction algorithms using parametric hypotheses. In COLT’ 98, pages 32–43, New York, NY, USA, 1998. ACM.
[30] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, 2003. 9