Deep Networks and the Multiple Manifold Problem

Abstract:  Data with low-dimensional nonlinear structure are ubiquitous in engineering and scientific problems. We study a model problem with such structure: a binary classification task that uses a deep fully-connected neural network to classify data drawn from two disjoint smooth curves on the unit sphere. Aside from mild regularity conditions, we place no restrictions on the configuration of the curves. We prove that when (i) the network depth is large relative to certain geometric properties that set the difficulty of the problem and (ii) the network width and number of samples is polynomial in the depth, randomly-initialized gradient descent quickly learns to correctly classify all points on the two curves with high probability. To our knowledge, this is the first generalization guarantee for deep networks with nonlinear data that depends only on intrinsic data properties. Our analysis draws on ideas from harmonic analysis and martingale concentration for handling statistical dependencies in the initial (random) network. We sketch applications to invariant vision, where leveraging low-dimensional structure leads to novel resource-efficient neural network architectures for detecting deformations of visual motifs.

Bio:  Sam Buchanan is a Research Assistant Professor at the Toyota Technological Institute at Chicago. He obtained his Ph.D. in Electrical Engineering from Columbia University in 2022, advised by John Wright. His research interests include the theoretical analysis of deep neural networks, particularly in connection with high-dimensional data with low-dimensional structure, and associated applications. He received the 2017 NDSEG Fellowship, and the Eli Jury Award from Columbia University.

***Event will take place in hybrid format. The location for in-person attendance will be room 1008 EECS.   Attendance will also be available via Zoom.

Join Zoom Meeting https: https://umich.zoom.us/j/91414297851

Meeting ID: 914 1429 7851

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Michele Feldkamp ([email protected]).