核函数方法、局部回归、和密度估计都是基于记忆的方法：模型就是全部训练样本，拟合是在取值或预测时完成的。这类方法对于很多实时的使用场景是不可行的。
除一些过度简化的例子之外（比如平方的核函数），在一个点 $x_0$ 上拟合的计算成本是 $O(N)$ 次运算，相比之下，$M$ 个基函数的展开的一次求值计算成本是 $O(M)$，而且典型的场景中 $M\sim O(\log N)$。基函数方法的计算成本不小于 $O(NM^2+M^3)$。
核方法的平滑参数（可能多个）$\lambda$ 通常离线（off-line）确定，例如通过交叉验证，其计算成本为 $O(N^2)$。常见的局部回归实现，比如 S-PLUS 和 R 中的 loess 函数以及 locfit 方法（Loader, 1999），使用三角剖分（triangulation）来减少计算量。其方法是在 $M$ 个精确挑选出的位置上拟合（$O(NM)$），然后在其他位置的求值使用混合方法对已有的拟合进行插值（$O(M)$）。