Higher-Order Regret Bounds with Switching Costs
作者： Eyal Gofer
DOI:
关键词:
摘要: This work examines online linear optimization with full information and switching costs (SCs) focuses on regret bounds that depend properties of the loss sequences. The SCs considered are bounded functions a pair decisions, is augmented total SC. We show under general conditions for any normed SC,σ(x,x ' ) = kx−xk, cannot be given only bound Q quadratic variation losses. With an additional � length losses, we prove O( √ + �) Regularized Follow Leader (RFTL). Furthermore, Q) holds RFTL cost kx − xk 2 . By generalizing Shrinking Dartboard algorithm, also expected best expert setting SC, expert. As vanish, all our purely variation. apply results to pricing options in arbitrage-free market proportional transaction costs. In particular, upper price "at money" call options, assuming stock minimum summed gains
参考文章(38)
Eyal Gofer, Yishay Mansour, Lower bounds on individual sequence regret algorithmic learning theory. pp. 275- 289 ,(2012) , 10.1007/978-3-642-34106-9_23
Sascha Geulen, Melanie Winkler, Berthold Vöcking, Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm. conference on learning theory. pp. 132- 143 ,(2010)
A. Philip Dawid, Peter Grunwald, Nikolai Vereshchagin, Wouter M. Koolen, Vladimir Vovk, Alexander Shen, Glenn Shafer, Steven de Rooij, Probability-free pricing of adjusted American lookbacks arXiv: Pricing of Securities. ,(2011)
Avrim Blum, Carl Burch, On-line Learning and the Metrical Task System Problem Machine Learning. ,vol. 39, pp. 35- 58 ,(2000) , 10.1023/A:1007621832648
Elad Hazan, Satyen Kale, Extracting certainty from uncertainty: regret bounded by variation in costs Machine Learning. ,vol. 80, pp. 165- 188 ,(2010) , 10.1007/S10994-010-5175-X
Peter DeMarzo, Ilan Kremer, Yishay Mansour, Online trading algorithms and robust option pricing Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. pp. 477- 486 ,(2006) , 10.1145/1132516.1132586
Eyal Gofer, Yishay Mansour, Regret Minimization Algorithms for Pricing Lookback Options Lecture Notes in Computer Science. pp. 234- 248 ,(2011) , 10.1007/978-3-642-24412-4_20
Yoav Freund, Robert E Schapire, A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting conference on learning theory. ,vol. 55, pp. 119- 139 ,(1997) , 10.1006/JCSS.1997.1504
Nicolò Cesa-Bianchi, Yishay Mansour, Gilles Stoltz, Improved second-order bounds for prediction with expert advice Machine Learning. ,vol. 66, pp. 321- 352 ,(2007) , 10.1007/S10994-006-5001-7
Marek Rutkowski, Marek Musiela, Martingale Methods in Financial Modelling ,(2002)