Information theoretic limits of learning of the causal features in a linear model

In this paper, we study the problem of causal features detection in a linear model. In a mathematical model, we consider a dataset of N samples, each represented by a sequence of G binary features. Associated to each sample, there is a binary label. It is assumed that the labels are related to a latent subset of the features, called causal features, via a linear function. More precisely, in our model, each label is the result of a noisy observation of a linear function of the causal features. We assume that the number of the causal features is bounded by L, where L is a given positive integer. In this paper, our objective is to detect the set of the causal features. In this way, at the limits of the parameters N, G and L, we observe a threshold effect at Gh(L/G)/N, where h(.) is the binary entropy function. Hence, we define the rate of the problem of causal features detection as Gh(L/G)/N and we characterize the capacity, using an achievable scheme and a matching converse.