Consistency Of ERM Algorithm

Empirical Risk Minimization(ERM)algorithm is a classical learning algorithm in statistical learning theory.It has a very important role in learning theory,and it can solve some conventional problems such as the least-square regression,the maximum likelihood method in probability density estimate.Therefore,research on ERM algorithm is particularly important.Until now,the main study on ERM algorithm are the consistency of algorithm and the rate of convergence.However,the study on the consistency of algorithm and the rate of convergence are often based on the hypothesis that dates are come from independent and identically distributed(i.i.d.)samples.But the assumption of independent is too strict,it is not easy to verify independence of samples in real life.In addition,in some practical problems,such as DNA sequence analysis,market prediction,web search,the samples are not independent.Thus,it is essential to investigative the ERM algorithm on the non-i.i.d.samples.In this paper,we study the consistency of ERM algorithm based on the exponentially strongly mixing observations and uniformly ergodic Markov chain(u.e.M.c.).When we discuss the consistency of ERM algorithm based on exponentially strongly mixing sequences,we first use exponential type inequality to get convergence bound of ERM principle.Then,we study the deviation between the empirical risk and the expected risk.Instead of considering the uniform deviation between the empirical risk and the expected risk,we establish their relative uniform deviation,which can effectively capture the phenomenon that when the expected risk is small,the deviation between the empirical risk and the expected risk is also small with large probability.At the same time,our results have smaller confidence interval than that bound on the rate of uniform convergence.When the complexity of the given function set is high,the ERM algorithm is usually very time-consuming and over-fitting may happen.In this paper,we solve the time-consuming problem of ERM algorithm based on the exponentially strongly mixing sequences.Not like others who frequently adopted regularization techniques,we explore a new method.The main idea of our method is that we skillfully decompose the given target function set into different disjoint compact subsets such that the complexities of all subsets are small.Uniformly ergodic Markov chain is a non-i.i.d sample which is weak than exponentially strongly mixing samples.It has widely use in statistics,queuing theory and signal processing and so on.In the study of the consistency of ERM algorithm based on the uniformly ergodic Markov chain samples,we also make use of exponential inequality to obtain the relative convergence bound of ERM algorithm,just like the exponentially strongly mixing sequences.But the method we adopt is different from others.The method we adopt is to add another term to the denominator to be sure the denominator is non-zero.At the same time,the improved relative uniform deviations can reflect the character of empirical datas successfully.For the improvement of methods,we own a fast convergence rate than that for exponentially strongly mixing observations and other results on uniformly ergodic Markov chain.