Computational Hardness Of RepresentAtion Learning

Introduction

Rich internal representations of complex data are crucial to the predictive power of neural networks. Unfortunately, current statistical analyses are restricted to over-simplified networks, whose representations (i.e., weight matrices) are either random, and/or project the data in comparatively very large or very low dimensional spaces; in many applications, the situation is very different. The modelization of realistic data is another issue. There is an urgent need to reconcile theory and practice.

Framework Overview

Based on a synergy of the mathematical physics of spin glasses, matrix-models from physics, and information and random matrix theory, CHORAL’s statistical framework will delimit computational gaps in the learning, from structured data, of much more realistic models of neural networks.

Quantifying Discrepancies

These gaps will quantify the discrepancy between:

1. The statistical cost of learning good representations, i.e., the minimal amount of training data required to reach a satisfactory predictive performance.
2. The cost of efficiency, i.e., the amount of data needed when learning using tractable algorithms, such as approximate message-passing and noisy gradient descents.

Comparing these costs will quantify when learning is computationally hard or not.

Focus Areas

To achieve this, CHORAL will first focus on dictionary learning, another essential task of representation learning, and then move on to multi-layer neural networks, which can be thought of as concatenated dictionary learning problems.

Impact

CHORAL’s ambitious program, by defining benchmarks for algorithms used in virtually all fields of science and technology, will have a direct practical impact. Equally important will be its conceptual impact: the study of information processing systems has become a major source of inspiration for mathematics.