Generalization Bounds of ERM Algorithm with Markov Chain Samples  

作　　者：Bin ZOU Zong-ben XU Jie XU 

机构地区：[1]Faculty of Mathematics and Computer Science,Hubei University [2]Institute for Information and System Science,School of Mathematics and Statistics,Xi’an Jiaotong University

出　　处：《Acta Mathematicae Applicatae Sinica》2014年第1期223-238,共16页应用数学学报（英文版）

基　　金：Supported by National 973 project(No.2013CB329404);Key Project of NSF of China(No.11131006);National Natural Science Foundation of China(No.61075054,61370000)

摘　　要：One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed （i.i.d.） samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization （ERM） algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain samples is consistent. The established theory underlies application of ERM type of learning algorithms.One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed （i.i.d.） samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization （ERM） algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain samples is consistent. The established theory underlies application of ERM type of learning algorithms.

关 键 词：generalization bounds ERM algorithm relative uniform convergence uniformly ergodic Markovchain learning theory 

分 类 号：O211.62[理学—概率论与数理统计] TP181[理学—数学]