On Blackbox Backpropagation and Jacobian Sensing

From a small number of calls to a given “blackbox"" on random input perturbations,
we show how to efficiently recover its unknown Jacobian, or estimate the left action
of its Jacobian on a given vector. Our methods are based on a novel combination of
compressed sensing and graph coloring techniques, and provably exploit structural
prior knowledge about the Jacobian such as sparsity and symmetry while being
noise robust. We demonstrate efficient backpropagation through noisy blackbox
layers in a deep neural net, improved data-efficiency in the task of linearizing the
dynamics of a rigid body system, and the generic ability to handle a rich class of
input-output dependency structures in Jacobian estimation problems.

• Machine Intelligence