论文标题
基于内核的学习中稀疏近似方法的收敛速率提高了
Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning
论文作者
论文摘要
基于内核的模型，例如内核脊回归和高斯工艺在机器学习应用程序中无处不在用于回归和优化。众所周知，基于内核的模型的主要缺点是高计算成本。给定$ n $样本的数据集，成本增长为$ \ Mathcal {o}（n^3）$。在某些情况下，现有的稀疏近似方法可以大大降低计算成本，从而有效地将实际成本降低至$ \ nathcal {o}（n）$。尽管取得了显着的经验成功，但由于近似值而导致的误差的分析界限，现有结果仍然存在显着差距。在这项工作中，我们为NyStröm方法提供新的置信区间和稀疏的变异高斯过程近似方法，我们使用模型的近似（替代）后方差的新解释来建立。我们的置信区间会导致回归和优化问题的性能界限。
Kernel-based models such as kernel ridge regression and Gaussian processes are ubiquitous in machine learning applications for regression and optimization. It is well known that a major downside for kernel-based models is the high computational cost; given a dataset of $n$ samples, the cost grows as $\mathcal{O}(n^3)$. Existing sparse approximation methods can yield a significant reduction in the computational cost, effectively reducing the actual cost down to as low as $\mathcal{O}(n)$ in certain cases. Despite this remarkable empirical success, significant gaps remain in the existing results for the analytical bounds on the error due to approximation. In this work, we provide novel confidence intervals for the Nyström method and the sparse variational Gaussian process approximation method, which we establish using novel interpretations of the approximate (surrogate) posterior variance of the models. Our confidence intervals lead to improved performance bounds in both regression and optimization problems.
