On Blackbox Backpropagation and Jacobian Sensing
Abstract
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.