A Stochastic Rate-Distortion Approach to Supervised Learning Systems

Machine learning applications have exploded in recent years due to the availability of huge data sets as well as advances in computational and storage capabilities. Although successful methods have been proposed to reduce learning system complexity while maintaining required accuracy levels, theoretical understanding of the underlying trade-offs remains elusive. In this paper, the classical supervised learning problem is reformulated within a rate-distortion framework. It provides insights into crucial accuracy-complexity trade-offs, by considering the overall learning system as consisting of two components. The first is tasked with extracting (learning) from the source the minimal number of information bits necessary to ultimately achieve the prescribed output accuracy. The learned bits are then used to retrieve the desired output from the second component, an appropriately designed codebook. The premise here is that an optimal system is characterized by having to learn the minimum amount of information from the source, just sufficient to yield the system output at the desired precision, which implies efficiency in terms of system complexity, generalization and training data requirements. The design and training of such a reformulated system is detailed in this paper, and asymptotically optimal performance achieving the rate-distortion bound is established.