Statistical mechanics of sparse generalization and model selection

Abstract

One of the crucial tasks in many inference problems is the extraction of sparse information out of a given number of high-dimensional measurements. In machine learning, this is frequently achieved using, as a penality term, the $L_p$ norm of the model parameters, with $p\le 1$ for efficient dilution. Here we propose a statistical-mechanics analysis of the problem in the setting of perceptron memorization and generalization. Using a replica approach, we are able to evaluate the relative performance of naive dilution (obtained by learning without dilution, following by applying a threshold to the model parameters), $L_1$ dilution (which is frequently used in convex optimization) and $L_0$ dilution (which is optimal but computationally hard to implement). Whereas both $L_p$ diluted approaches clearly outperform the naive approach, we find a small region where $L_0$ works almost perfectly and strongly outperforms the simpler to implement $L_1$ dilution.

18 pages, 9 eps figures

References in corpus (5)

• High-dimensional graphs and variable selection with the Lasso
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Inference algorithms for gene networks: a statistical mechanics analysis
• Gene-network inference by message passing
• Classification and sparse-signature extraction from gene-expression data

Cited by in corpus (6)

• Statistical mechanics of complex neural systems and high dimensional data
• Origin of the computational hardness for learning with binary synapses
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Sparse Hopfield network reconstruction with ${\ell }_1$ regularization
• Stability of the replica symmetric solution in diluted perceptron learning
• Expectation propagation on the diluted Bayesian classifier