历史上，支持向量机大量地使用一个被称为计算学习理论（computational learning theory)）的理论框架进行分析。这个框架有时候也被称为统计学习理论（statistical learning theory）（Anthony and Biggs, 1992; Kearns and Vazirani, 1994; Vapnik, 1995; Vapnik, 1998）。这个框架起源于Valiant（1984），他建立了概率近似正确（probably approximately correct）或称为PAC的学习框架。PAC学习框架的目标是理解为两个给出较好的泛化能力，需要多大的数据集。这个框架也给出了学习的计算代价的界限，虽然我们不会在这里讨论。
假设我们从联合概率分布中抽取一个大小为的数据集，其中是输入变量，表示类别标签。我们把注意力集中于“无噪声”的情况，即类别标签由某个（未知的）判别函数确定。在PAC学习中，空间是一个以训练集为基础的函数组成的空间，我们从空间中抽取一个函数，如果它的期望错误率小于某个预先设定的阈值，即
那么我们就说函数具有较好的泛化能力。其中是示性函数，期望是关于概率分布的期望。式子左手边的项是一个随机变量，因为它依赖于训练数据集。PAC框架要求，对于从概率分布中随机抽取的数据集，式（7.75）成立的概率要大于。这里是另一个预先设定的参数。术语“概率近似正确”来自于以一个较高的概率（大于），使得错误率较小（小于）这一要求。对于一个给定的模型空间，以及给定的参数，PAC学习的目标是提供满足这个准则所需的最小数据集规模的界限。在PAC学习中，一个关键的量是Vapnik-Chervonenkis维度（Vapnik-Chervonenkis dimension），或者被称为VC维度。它提供了函数空间复杂度的一个度量，使得PAC框架能够扩展到包含无穷多个函数的空间。
在PAC框架中推导出的界限通常被看成是最坏的情况，因为它们适用于概率分布的任意选择，只要训练集和测试集是从相同的概率分布中（独立地）抽取即可，并且它们适用于函数的任意选择，只要它属于即可。在真实世界的机器学习应用中，我们处理的分布通常有着很强的规律性，如输入空间中的大片区域有着相同的类别标签。由于缺少关于分布形式的任何假设，因此PAC边界非常保守，也就是说，它们严重高估了得到给定的泛化性能所需的数据集的规模。因此，PAC界限几乎没有任何实际用处。
一种提升PAC界限的紧致程度的方法是PAC-贝叶斯框架（PAC-Bayesian framework）（McAllester, 2003），它考虑了空间F上的函数的概率分布情况，有些类似于贝叶斯方法中的先验概率。这种方法仍然考虑任意可能的的选择，因此虽然这种方法得到的界限更加紧致，但是它们仍然是非常保守的。