Efficient Tensor Kernel methods for sparse regression

Feliks Hibraj, Marcello Pelillo, Saverio Salzo, Massimiliano PontilarXiv 2020 · OpenReview

Abstract Classical kernel methods have recently been extended through the introduction of tensor kernels to promote sparsity in regression solutions. By solving an $L^p$-norm regularization problem (where $p = m/(m-1)$ and $m$ is an even integer), these methods approximate the behavior of Lasso regression. However, the memory requirements for storing high-order tensors present a significant bottleneck. This work addresses these limitations by introducing a more efficient memory layout for symmetric tensor storage and a Nyström-type subsampling approach. Experimental results on synthetic and real-world datasets demonstrate that these improvements significantly reduce memory overhead and computational cost, enabling the application of tensor kernels to larger datasets.

Introduction

Standard kernel methods, such as Support Vector Machines or Kernel Ridge Regression, typically rely on $L^2$ regularization. While mathematically convenient due to their operation in Hilbert spaces, $L^2$ methods do not produce "sparse" solutions—they utilize all input features rather than selecting a relevant subset.

To achieve sparsity, researchers often look to $L^1$ regularization (Lasso). However, $L^1$ methods are difficult to "kernelize" because they lack the inner-product structure required for the traditional "kernel trick." Recent theory suggests using $L^p$ spaces (where $p$ is slightly larger than 1) as a proxy for $L^1$. This can be achieved using tensor kernels, but there is a significant computational hurdle: a $q$-order tensor for $n$ data points requires $n^q$ entries. For even a modest dataset where $n=100$ and $q=4$, one must store 100 million values, creating a "memory wall" that renders the method impractical for most real-world applications.

Proposed Methodology

This research proposes two primary advances to make tensor kernels computationally feasible:

1. Symmetric Tensor Storage Layout

Tensor kernels are inherently symmetric; the kernel value remains unchanged regardless of the order of input points. By deriving a specific indexing formula, we implemented a system that stores only the unique (non-repeated) elements in a linear array. For a 4th-order tensor, this reduces the number of stored elements from $n^4$ to approximately $n^4/24$. This exploitation of symmetry is the difference between a model fitting in standard RAM or crashing the system.

2. Nyström-type Subsampling

To further reduce computational cost, we applied a Nyström strategy. Instead of training on the full dataset of $n$ points, the model is trained on a randomly sampled subset of $m$ points ($m < n$). This reduces the size of the optimization problem while maintaining high predictive accuracy. Experiments suggest that tensor kernels are highly informative even with fewer points, showing negligible loss in accuracy when reducing training set sizes.

3. C++ Implementation

The core algorithms were implemented in C++ to leverage low-level memory management and compiler optimizations, providing a significant boost in execution speed compared to high-level language implementations.

Experimental Results

The methods were evaluated on synthetic data and real-world benchmarks, including the Wpbc (Breast Cancer Wisconsin) dataset and the Dexter dataset (a high-dimensional feature selection challenge).

  • Memory Efficiency: For $n=100$ points, the new layout requires only ~4.4 million entries compared to 100 million in the naive layout—a 95.58% reduction. On a machine with 8GB RAM, the proposed layout extended the maximum data point capacity from 181 to 399 points.
  • Computational Speedups: On the Wpbc dataset, the new layout achieved a 5.85x speedup in kernel construction. On high-dimensional synthetic data ($d=5000$), the overall speedup reached 14.96x.
  • Scalability: The Dexter dataset, which previously triggered Out-Of-Memory (OOM) errors, was successfully processed in under 30 minutes using the optimized framework.
  • Feature Selection: The model successfully identified relevant features in 5,000-dimensional spaces, effectively "denoising" the weight vector and proving the efficacy of $L^p$ as a sparsity proxy.

Conclusion and Future Work

By combining clever memory management with subsampling techniques, this work demonstrates how to achieve the sparsity benefits of Lasso regression within a kernel framework. While the complexity still scales polynomially ($O(n^q)$), these optimizations provide a practical path forward for high-order kernel methods. Future research will explore more sophisticated sampling techniques and the application of these efficient kernels to non-parametric, infinite-dimensional models.

Summary updated

Abstract

Recently, classical kernel methods have been extended by the introduction of suitable tensor kernels so to promote sparsity in the solution of the underlying regression problem. Indeed, they solve an lp-norm regularization problem, with p=m/(m-1) and m even integer, which happens to be close to a lasso problem. However, a major drawback of the method is that storing tensors requires a considerable amount of memory, ultimately limiting its applicability. In this work we address this problem by proposing two advances. First, we directly reduce the memory requirement, by intriducing a new and more efficient layout for storing the data. Second, we use a Nystrom-type subsampling approach, which allows for a training phase with a smaller number of data points, so to reduce the computational cost. Experiments, both on synthetic and read datasets, show the effectiveness of the proposed improvements. Finally, we take case of implementing the cose in C++ so to further speed-up the computation.
BibTeX
@misc{hibraj2020efficient,
  author = {Feliks Hibraj and Marcello Pelillo and Saverio Salzo and Massimiliano Pontil},
  title = {{Efficient Tensor Kernel methods for sparse regression}},
  year = {2020},
  eprint = {2003.10482},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.10482},
}
Figure