Compression and learning in linear regression

We introduce a linear regression regularization method based on the minimum description length principle, which aims at both sparsification and over-fit avoidance. We begin by building compact prefix free encryption codes for both rational-valued parameters and integer-valued residuals, then build smooth approximations to their code lengths, as to provide an objective function whose minimization provides optimal lopression under certain assumptions. We compare the method against the LASSO on simulated datasets proposed by Tibshirani [14], examining generalization and accuracy in sparsity structure recovery.