有别于其他的学习理论和方法，学习的计算理论是通过“计算”来进行学习的理论。致力于通过机器学习算法的设计与分析，识别有效学习过程的基本方法，以理解学习问题/任务的固有难度或困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

学习的计算理论是一种多学科的理论，集计算机科学、统计学和应用数学等于一体。以计算复杂性理论、形式语言理论、统计推断理论等为工具，通过对学习过程进行建模，设计能够进行学习的计算机程序，利用程序与模型探寻能够高效学习的内容，分析学习所需的计算机时间、空间和信息资源等，以此来判定学习对象的可学习性和学习效率。

学习的计算理论是对认知过程进行数学建模的第一次尝试，最早可追溯至1984年英国计算机科学家L.G.瓦利安特（Leslie Gabriel Valiant）建立的概率近似正确（Probably Approximately Correct, PAC）模型。学习的计算理论是为从理论上回答机器学习所需要的时间、空间、信息资源等问题，阐明机器学习的本质，分析学习的可能性及其效率，将计算复杂性、算法、形式语言以及统计推断等理论和机器学习的研究进行融合，在PAC学习模型的基础上形成的一种宏观理论。为精确制定和解决不同学习算法的性能问题，提供了一个正式的指导框架，据此可以比较不同学习算法的预测能力和计算效率。

在学习的计算理论中，PAC模型与V-C Dimension（Vapnik-Chervonenkis Dimension）模型是两个主要的模型，后者最初由俄罗斯统计学家V.N.瓦普尼克（Vladimir Naumovich Vapnik）与俄罗斯数学家A.Y.切沃嫩基斯（Alexey Yakovlevich Chervonenkis）联合提出。其中，PAC模型在学习的计算理论中处于相对核心的地位，它使量化可学性成为了可能，但是其应用受限于数据是离散属性的相关领域。在数据是连续属性的相关领域，则主要应用V-C Dimension模型。在学习的计算理论领域，早期研究主要是证明PAC模型与V-C Dimension模型二者对于数据的需求。除PAC、V-C Dimension两种模型之外，还有归纳学习模型、EXACT学习模型、模式识别和人工神经网络中的参数学习模型等。此外，由学习的计算理论还发展出一些实用的算法。例如，支持PAC理论的boosting算法，基于VC理论的支持向量机，以及由贝叶斯推断发展出的信度网络等。