Approximation errors of online sparsification criteria
This work addresses the need for efficient sparsification in online learning, providing theoretical insights that could improve model performance and computational efficiency, though it appears incremental as it builds on existing criteria.
The paper tackles the problem of approximation errors in online sparsification criteria used in machine learning frameworks like kernel methods, by deriving theoretical bounds on these errors for various criteria such as distance and coherence, and investigates errors for specific features like empirical mean and kernel PCA axes.
Many machine learning frameworks, such as resource-allocating networks, kernel-based methods, Gaussian processes, and radial-basis-function networks, require a sparsification scheme in order to address the online learning paradigm. For this purpose, several online sparsification criteria have been proposed to restrict the model definition on a subset of samples. The most known criterion is the (linear) approximation criterion, which discards any sample that can be well represented by the already contributing samples, an operation with excessive computational complexity. Several computationally efficient sparsification criteria have been introduced in the literature, such as the distance, the coherence and the Babel criteria. In this paper, we provide a framework that connects these sparsification criteria to the issue of approximating samples, by deriving theoretical bounds on the approximation errors. Moreover, we investigate the error of approximating any feature, by proposing upper-bounds on the approximation error for each of the aforementioned sparsification criteria. Two classes of features are described in detail, the empirical mean and the principal axes in the kernel principal component analysis.