Physarum Powered Differentiable Linear Programming Layers and Applications
This provides a plug-and-play solution for incorporating LP layers into neural networks, addressing a bottleneck in differentiable optimization for tasks like video segmentation and meta-learning, though it is incremental relative to existing differentiable optimization methods.
The paper tackles the challenge of integrating linear programming (LP) as a differentiable layer within deep neural networks by proposing an efficient and differentiable solver inspired by slime mold dynamics. It shows comparable performance to a customized gradient descent method on video segmentation and outperforms the differentiable CVXPY-SCS solver on meta-learning for few-shot learning, with experiments indicating quick convergence without a feasible initial point.
Consider a learning algorithm, which involves an internal call to an optimization routine such as a generalized eigenvalue problem, a cone programming problem or even sorting. Integrating such a method as a layer(s) within a trainable deep neural network (DNN) in an efficient and numerically stable way is not straightforward -- for instance, only recently, strategies have emerged for eigendecomposition and differentiable sorting. We propose an efficient and differentiable solver for general linear programming problems which can be used in a plug and play manner within DNNs as a layer. Our development is inspired by a fascinating but not widely used link between dynamics of slime mold (physarum) and optimization schemes such as steepest descent. We describe our development and show the use of our solver in a video segmentation task and meta-learning for few-shot learning. We review the existing results and provide a technical analysis describing its applicability for our use cases. Our solver performs comparably with a customized projected gradient descent method on the first task and outperforms the differentiable CVXPY-SCS solver on the second task. Experiments show that our solver converges quickly without the need for a feasible initial point. Our proposal is easy to implement and can easily serve as layers whenever a learning procedure needs a fast approximate solution to a LP, within a larger network.