学习理论对机器学习的发展有着重要的指导与支撑作用,可学习性(又称PAC可学习性)是机器学习理论研究中的一个基本问题,探讨学习问题是否存在多项式时间开销和样本复杂度、可获得高精度学习器的学习算法。传统可学习性理论通常基于数据独立同分布的假设,然而数据分布在真实应用中往往随时间、空间变化而改变。本文对非独立同分布可学习性理论与算法进行研究,主要取得了以下创新性成果:1)提出了非独立同分布下平均稳定性理论概念,证明了平均稳定性与可学习性之间的等价性。本文通过平稳β-混合序列刻画非独立同分布中随时间变化而逐渐减弱的依赖关系,利用独立块技术,理论上给出了非独立同分布下可学习性的充要条件,解决了非独立同分布的可学习性问题通过平均稳定性来刻画,使得稳定性理论框架得以发展,可用于更多类型的非独立同分布研究。2)提出了一种基于平均稳定性的重要性采样随机次梯度下降算法IS3D(Importance Sampling Stochastic Subgradient Descent)。该算法通过重要性采样来刻画非独立同分布条件下数据依赖关系随时序间距增大而减小的特性,利用随机次梯度下降方法求解。理论上证明该算法在非独立同分布条件下具有平均稳定性和收敛性,并通过实验验证了方法的有效性。