Solving lp-norm regularization with tensor kernels

Saverio Salzo, Lorenzo Rosasco, Johan A. K. SuykensAISTATS 2018 · OpenReview

Abstract

This paper explores how a suitable family of tensor kernels can be used to efficiently solve nonparametric extensions of $\ell^p$ regularized learning methods. By exploiting a specific mathematical condition where the conjugate exponent $q$ is an even integer, we propose a fast, dual proximal gradient algorithm that achieves linear convergence, overcoming the traditional restriction of kernel methods to Hilbert spaces.

Introduction

In machine learning, the "kernel trick" is a cornerstone technique that allows algorithms to operate in high-dimensional feature spaces without ever explicitly calculating those coordinates. However, this trick has traditionally been locked to $\ell^2$-regularization (Hilbert spaces), which produces "dense" solutions where every feature gets some weight. Researchers often prefer $\ell^1$-regularization because it promotes sparsity, zeroing out irrelevant features. However, $\ell^1$ does not integrate easily with kernels. $\ell^p$-regularization (for $1 < p < 2$) acts as a smooth proxy for $\ell^1$, offering a balance between sparsity and differentiability. Until now, the consensus was that $\ell^p$ kernels were computationally impractical because their dual problems could not be expressed in a closed, solvable form. This paper challenges that "impossibility" by providing a viable mathematical framework and an efficient algorithm.

Methodology

The authors introduce two main innovations to enable efficient $\ell^p$-norm regularization:

  1. Tensor Kernels: They show that if the conjugate exponent $q$ (where $1/p + 1/q = 1$) is an even integer (e.g., $q=4$, which means $p=4/3$), the dual objective function becomes a convex polynomial of degree $q$. This allows them to define a "tensor kernel" $K(x_1, \dots, x_q)$ that measures group-wise similarity across $q$ data points simultaneously, rather than just pairs.
  2. Dual Proximal Gradient Algorithm: Standard gradient descent fails here because the gradient of a high-degree polynomial isn't "globally Lipschitz continuous." To fix this, the authors propose a dual algorithm with a backtracking linesearch. This ensures the step size is always appropriate, leading to guaranteed linear convergence for common loss functions like least squares and logistic loss.

The beauty of this approach is that the complexity depends on the number of data points ($n$), not the dimensionality of the feature space ($d$), making it ideal for "small $n$, large $d$" problems.

Experimental Results

The paper evaluates the method using simulated datasets to rigorously test convergence rates and feature recovery. In a setup with $n=85$ samples and $d=1500$ features, the dual algorithm demonstrated superior performance.

The dual algorithm shows rapid convergence (left) and accurately recovers the true sparse vector (right) for p=4/3.

As illustrated in the figure above, the dual algorithm converges significantly faster than primal methods like FISTA. Furthermore, it successfully identifies the relevant "spikes" (features) in high-dimensional data, effectively performing variable selection even when the number of features vastly outnumbers the samples.

Quantitative results across various values of $p$ further underscore this efficiency. In head-to-head tests, the proposed dual algorithm reached a relative precision of $10^{-8}$ in just 12 to 258 iterations. In contrast, standard primal methods either failed to converge within 5,000 iterations or took over 1,000.

Number of iterations required to reach a relative precision of 10^-8 for various algorithms and p values.

Conclusion

This work proves that we don't need the rigid structure of a Hilbert space ($\ell^2$) to use kernels. We can move into Reproducing Kernel Banach Spaces (RKBS) and still get the computational benefits of the representer theorem. While the current framework is most efficient when $q$ is a small even integer and building the "Gram tensor" requires $O(n^q)$ operations, this approach breathes new life into kernel methods by making $\ell^p$-norm regularization computationally viable for high-dimensional sparse recovery.

Summary updated

Abstract

In this paper, we discuss how a suitable family of tensor kernels can be used to efficiently solve nonparametric extensions of lp regularized learning methods. Our main contribution is proposing a ...
BibTeX
@inproceedings{salzo2018solving,
  author = {Saverio Salzo and Lorenzo Rosasco and Johan A. K. Suykens},
  title = {{Solving lp-norm regularization with tensor kernels}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=vyIlhkVmxQy},
}

Loading related content...

Figure