Research On The Learnability Of Non-I.I.D.

Learning theory has played a very important role in the development of machine learning.Learnability(or PAC Learnable)has been a foundational problem in learning theory,which explores the existence of learning algorithm with polynomial time and sample compelxity for a learning problem.Taditional learning theory is always based on the assumption of i.i.d.(independently and identically distributed)data,whereas data distribution varies over time and space in many real applications.This thesis presents a full understanding on the learnability of non-i.i.d.The main contributions can be summaried as follows:Propose the theoretical notion of average stability,and prove the equivalence be-tween average stability and learnability in the non-i.i.d.setting.This thesis utilizes theβ-mixing sequence to characterize the dependence of the non-i.i.d.data,and presents the necessary and sufficient condition for learnability based on independent block tech-nique.Relevant work generalizes the statility analysis to other non-i.i.d.settings.Propose the importance sampling stochastic subgradient descent(IS3D)algorithm based on average stability.The basic idea is to utilize importance sampling technique to characterize the data dependence in the non-i.i.d.setting,and then learn by vallina stochastic subgradient descent.This thesis verifies the effectiveness of the proposed algorithm both theoretically and empirically.