Do Compressed Representations Generalize Better?

One of the most studied problems in machine learning is finding reasonable constraints that guarantee the generalization of a learning algorithm. These constraints are usually expressed as some simplicity assumptions on the target. For instance, in the V apnik-Chervonenkis (VC) theory the space of possible hypotheses is considered to have a limited VC dimension and in kernel methods there are assumptions on the spectrum of the operator in the Hilbert space. One way to formulate the simplicity assumption is via information theoretic concepts. In this paper, the constraint on the entropy H ( X) of the input variable X is studied as a simplicity assumption. It is proven that the sample complexity to achieve an null -δ Probably Approximately Correct (P AC) hypothesis is bounded by 2 2 H ( X) / null log 1 δ null 2 which is sharp up to the 1 null 2 factor. Morever, it is shown that if a feature learning process is employed to learn the compressed representation from the dataset, this bound no longer exists. These findings have important implications on the Information Bottleneck (IB) theory which had been utilized to explain the generalization power of Deep Neural Networks (DNNs), but its applicability for this purpose is currently under debate by researchers. In particular, this is a rigorous proof for the previous heuristic that compressed representations are expnentially easier to be learned. However, our analysis pinpoints two factors preventing the IB, in its current form, to be applicable in studying neural networks. Firstly, the exponential dependence of sample complexity on 1 / null, which can lead to a dramatic e ff ect on the bounds in practical applications when null is small. Secondly, our analysis reveals that arguments based on input compression are inherently insu fficient to explain generalization of methods like DNNs in which the features are also learned using available data. Keywords: Compressed Representation; Generalization Bound; Information Bottleneck. 1. Introduction The main objective of learning is to develop algorithms which can learn general patterns by using a finite number of samples drawn from a target distribution. The "no free lunch" theorem states that if there is no constraint on the distribution, it is impossible to say anything about the samples not seen in the training set (Wolpert, 1996b).