Modern machine learning relies heavily on Automatic Differentiation (AD) to calculate gradients for training. However, AD requires every "node" in a computation graph to have a known gradient routine. In many real-world applications—such as robotics, reinforcement learning, and process control—we frequently encounter "blackboxes." These are opaque pieces of code, like proprietary physics engines or legacy hardware interfaces, that provide outputs for given inputs but offer no internal gradient information.
The standard workaround is finite differencing: wiggling each input one by one to see how the output changes. For a system with $n$ inputs, this requires at least $n$ expensive function calls. When $n$ is large, this becomes computationally prohibitive. Furthermore, if the blackbox is "noisy" (common in physical sensors or stochastic simulations), simple finite differencing fails miserably.
To address this, researchers have developed the Rainbow algorithm, a method that allows for efficient backpropagation through these blackbox components. By combining graph coloring theory with compressed sensing, Rainbow efficiently reconstructs the Jacobian (the matrix of derivatives) using far fewer function calls than traditional methods, even in the presence of significant noise.
The Rainbow Algorithm
The authors treat Jacobian estimation as a structured sensing problem, breaking it down into three main phases:
- Color (Graph Coloring): The algorithm represents input-output dependencies as an "intersection graph." If two input variables do not influence the same output, they can be perturbed simultaneously without their effects interfering. By applying a greedy graph coloring algorithm, inputs are grouped into a small number of "colors" ($l$), where $l \ll n$.
- Optimize (Compressed Sensing): Instead of wiggling every input individually, the algorithm wiggles the groups defined by the colors. It then solves a convex optimization problem (using Linear Programming or ADMM) to recover the Jacobian. This step is crucial because it allows the model to incorporate "structural priors"—knowledge that the Jacobian is sparse, symmetric, or has specific block structures.
- Reconstruct: The solution from the optimization phase is mapped back to the original high-dimensional space to produce the final Jacobian estimate.
This approach is highly "noise-robust" because the optimization framework can account for measurement errors and non-linearities, unlike raw finite differencing.
Experimental Validation and Results
The paper evaluates the Rainbow method across three distinct settings, yielding impressive results:
- Synthetic Sparse Models: Using custom-generated functions to simulate different input-output dependency structures, the algorithm achieved accurate recovery with a number of calls ($k$) significantly lower than the number of inputs ($n$). In some tests, the Jacobian of a 60-input system was recovered with only 15 calls.
- Noisy Neural Networks (MNIST): The authors trained a Convolutional Neural Network (CNN) where a standard ReLU layer was replaced with a "blackbox" version injected with Gaussian noise. The Rainbow-LP method continued to converge and learn even when noise levels were high enough to cause standard linear regression and finite differencing methods to fail completely.
- Robot Dynamics: Using data from a 50-link planar manipulator (149 input variables) generated via MIT’s Drake toolbox, the Rainbow-ADMM solver outperformed standard $l_2$ regularized regression. It effectively exploited the known symmetry and sparsity of the rigid-body dynamics, drastically improving data efficiency.
Key Insights and Limitations
The core "Aha!" moment of this research is the realization that Jacobian recovery is fundamentally linked to the chromatic number of a dependency graph. If a system is sparse, you don't need to wiggle every variable; you just need to wiggle enough independent sets of variables. Furthermore, while Jacobians are technically defined for smooth functions, this method works for non-smooth functions by treating them as noisy versions of smooth approximations.
However, the method does have limitations. It performs best when a "weak intersection graph" (a rough map of which inputs affect which outputs) is known beforehand. While often inferable from the system's structure, it isn't always available. Additionally, solving a Linear Program or ADMM at every step of an optimization loop adds computational overhead, raising questions about its real-time applicability for very high-frequency control loops.
Future work may extend this approach to handle even more complex structural priors and explore its use in "model-free" trajectory optimization where the entire environment acts as the blackbox.
Summary updated