Deep Networks Provably Classify Data on Curves

In applied machine learning, engineering, and the sciences, we are frequently confronted with the problem of identifying low-dimensional structure in high-dimensional data. In certain well-structured data sets, identifying a good low-dimensional model is the principal task: examples include convolutional sparse models in microscopy [43] and neuroscience [13, 19], and low-rank models in collaborative filtering [8, 11]. Even more complicated datasets from problems such as image classification exhibit some form of low-dimensionality: recent experiments estimate the effective dimension of CIFAR-10 as 26 and the effective dimension of ImageNet as 43 [60]. The variability in these datasets can be thought of as comprising two parts: a "probabilistic" variability induced by the distribution of geometries associated with a given class, and a "geometric" variability associated with physical nuisances such as pose and illumination. The former is challenging to model analytically; virtually all progress on this issue has come through the introduction of large datasets and high-capacity learning machines. The latter induces a much cleaner analytical structure: transformations of a given image lie near a low-dimensional submanifold of the image space (Figure 1). The celebrated successes of convolutional neural networks in image classification seem to derive from their ability to simultaneously handle both types of variability.