On biased random walks, corrupted intervals, and learning under adversarial design

Agarwal, A., Duchi, J.C.: The generalization ability of online algorithms for dependent data. IEEE Trans. Inf. Theory 59(1), 573–587 (2013) Anava, O., Hazan, E., Mannor, S., Shamir, O.: Online learning for time series prediction. In: Shalev-shwartz, S., Steinwart, I. (eds.) COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14 Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pp. 172–184, JMLR.org (2013) Angluin, D., Laird, P.D.: Learning from noisy examples. Mach. Learn. 2(4), 343–370 (1987) Audiffren, J., Ralaivola, L.: Cornering stationary and restless mixing bandits with remix-ucb. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, pp. 3339–3347, Montreal, Quebec, Canada (2015) Bateman, H.: Higher Transcendental Functions. Krieger Pub Co. ISBN 0898742064 (1981) Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006) Cover, T.M.: The number of linearly inducible orderings of points in d-space. SIAM J. Appl. Math. 15(2), 434–439 (1967) Gamarnik, D.: Extension of the PAC framework to finite and countable Markov chains. IEEE Trans. Inform. Theory 49(1), 338–345 (2003) Gofer, E.: Machine Learning Algorithms with Applications in Finance. PhD thesis, Tel Aviv University (2014) Gradshteyn, I. S., Ryzhik, I.M.: Table of Integrals, Series, and Products, 7th edn. Elsevier/Academic Press, Amsterdam (2007). ISBN 978-0-12-373637-6; 0-12-373637-4. Translated from the Russian, Translation Edited and with a Preface by Alan Jeffrey and Daniel Zwillinger With One CD-ROM, Windows, Macintosh and UNIX) Harik, G., Cantú-Paz, E., Goldberg, D.E., Miller, B.L.: The gambler’s ruin problem, genetic algorithms, and the sizing of populations. Evol. Comput. 7(3), 231–253 (1999) Herbrich, R., Williamson, R.C.: Algorithmic luckiness. J. Mach. Learn. Res. 3, 175–212 (2002) Karandikar, R.L., Vidyasagar, M.: Rates of uniform convergence of empirical means with mixing processes. Statist. Probab. Lett. 58(3), 297–307 (2002). ISSN 0167-7152 Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983–1006 (1998) Kearns, M.J., Schapire, R.E.: Efficient distribution-free learning of probabilistic concepts. J. Comput. Syst. Sci. 48(3), 464–497 (1994). ISSN 0022-0000 Kearns, M.J., Schapire, R.E., Sellie, L.: Toward efficient agnostic learning. Mach. Learn. 17(2-3), 115–141 (1994) Kearns, M., Vazirani, U.: An introduction to computational learning theory. The MIT press (1997) Koolen, W.M., Vovk, V.: Buy low, sell high. Theor. Comput. Sci. 558, 144–158 (2014). ISSN 0304-3975. https://doi.org/10.1016/j.tcs.2014.09.030, http://www.sciencedirect.com/science/article/pii/S0304397514007087. Algorithmic Learning Theory Koshy, T.: Catalan numbers with applications. Oxford University Press, Oxford (2009). ISBN 978-0-19-533454-8 Kuznetsov, V., Mohri, M.: Learning theory and algorithms for forecasting non-stationary time series. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, pp. 541–549, Montreal, Quebec, Canada (2015) Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Society, Providence (2017). ISBN 978-1-4704-2962-1. Second edition of [ MR2466937], With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson London, B., Huang, B., Getoor, L.: Improved generalization bounds for large-scale structured prediction. In: NIPS Workshop on Algorithmic and Statistical Approaches for Large Social Networks (2012) London, B., Huang, B., Taskar, B., Getoor, L.: Collective stability in structured prediction: Generalization from one example. In: proceedings of the 30th International Conference on Machine Learning (ICML-13) (2013) Massart, P., Nédélec, É., et al.: Risk bounds for statistical learning. Ann. Stat. 34(5), 2326–2366 (2006) Mohri, M., Rostamizadeh, A.: Rademacher complexity bounds for non-i.i.d. processes. In: Neural Information Processing Systems (NIPS) (2008) Mohri, M., Rostamizadeh, A.: Stability bounds for stationary phi-mixing and beta-mixing processes. J. Mach. Learn. Res. 11, 789–814 (2010) Rostamizadeh, A., Mohri, M.: Stability bounds for non-i.i.d. processes. In: Neural Information Processing Systems (NIPS) (2007) Rudelson, M., Vershynin, R.: Smallest singular value of a random rectangular matrix. Commun. Pure Appl. Math. 62(12), 1707–1739 (2009) Shalizi, C.R., Kontorovich, A.: Predictive PAC learning and process decompositions. In: Neural Information Processing Systems (NIPS) (2013) Shawe-Taylor, J., Bartlett, P.L., Williamson, R.C., Anthony, M.: Structural risk minimization over data-dependent hierarchies. IEEE Trans. Inf. Theory 44(5), 1926–1940 (1998) Steinwart, I., Christmann, A.: Fast learning from non-i.i.d. observations. In: NIPS, pp. 1768–1776 (2009) Steinwart, I., Hush, D., Scovel, C.: Learning from dependent observations. J. Multivar. Anal. 100(1), 175–194 (2009) Teichmann, J.: Foundations of martingale theory and stochastic calculus from a finance perspective (2015) Toth, B.: No more than three favorite sites for simple random walk. Ann. Probab. 29(1), 484–503 (2001) Tsybakov, A.B.: Introduction à l’estimation non-paramétrique, volume 41 of Mathématiques & Applications (Berlin) [Mathematics & Applications]. Springer, Berlin (2004). ISBN 3-540-40592-5 Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984) Zimin, A., Lampert, C.H.: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pp. 213–222, PMLR Singh, A., Zhu, X.J. (eds.) (2017) Zou, B., Xu, Z.-B., Xu, J.: Generalization bounds of ERM algorithm with Markov chain samples. Acta Mathematicae Applicatae Sinica (English Series), pp. 1–16 (2014)