Chaining Mutual Information and Tightening Generalization Bounds

Emmanuel Abbé
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS), 2018
Conference paper

Abstract

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm's input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou '15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine the chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley's inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.

Official source

https://infoscience.epfl.ch/record/266592?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

The continuous increase, witnessed in the last decade, of both the amount of available data and the areas of application of machine learning, has lead to a demand for both learning and planning algorithms that are capable of handling large-scale problems. Thus scalability has become an important characteristic of modern machine learning algorithms. In this thesis we concentrate on tractable approaches to both learning and planning, capable of solving problems in high-dimensional spaces. We investigate multiple forms of high-dimensionality, where dimensionality can refer to the number of samples to be processed, the number of samples available for training, the dimensionality of the feature space, or even the dimensionality of the state-space. We present work on classifier cascades, developing a novel framework for interpreting, training, and employing such structures of classifiers. A Boosting algorithm developed in this framework highlights its ability to jointly train the classifiers at the cascade nodes. The work presented on goal-planning also results in a novel framework, this time for automatic macro-action discovery in imitation learning, specifically addressing problems with large state-spaces as well as with observation signals of high-dimensionality. The proposed DPBoost algorithm is capable of solving very complex goal-planning tasks where previous state-of-the-art fails. Addressing computer hardware limitations, and in particular memory limitations, we propose a new learning framework, which we call reservoir learning, which attempts to directly account for this limited memory during the training process. In particular we propose to consider learning in the presence of a reservoir in which the learner may store samples. Based on Boosting we develop a novel strategy for populating this reservoir which avoids redundancy by taking into account the joint behavior of samples. Finally high-dimensionality is also addressed in its most typical setting, that is when the feature space is large. We propose novel feature selection algorithms in the context of classification. Based on information theoretic tools, these algorithms attempt to maximize the joint mutual information between the selected, continuous, variables and the, discrete, class label variable.

EPFL2014

Practical Low-Rank Communication Compression in Decentralized Deep Learning

Martin Jaggi, Sai Praneeth Reddy Karimireddy, Thijs Vogels

Lossy gradient compression has become a practical tool to overcome the communication bottleneck in centrally coordinated distributed training of machine learning models. However, algorithms for decentralized training with compressed communication over arbitrary connected networks have been more complicated, requiring additional memory and hyperparameters. We introduce a simple algorithm that directly compresses the model differences between neighboring workers using low-rank linear compressors. We prove that our method does not require any additional hyperparameters, converges faster than prior methods, and is asymptotically independent of both the network and the compression. Inspired the PowerSGD algorithm for centralized deep learning, we execute power iteration steps on model differences to maximize the information transferred per bit. Out of the box, these compressors perform on par with state-of-the-art tuned compression algorithms in a series of deep learning benchmarks.

2020

EPFL2014