SDPRLayers: Certifiable Backpropagation through Polynomial Optimization Problems in Robotics
Connor Holmes, Frederike Dümbgen, Timothy Barfoot
AI summary
Problem
Differentiable optimization layers in robotics often converge to spurious local minima in nonconvex problems, causing corrupted gradients that disrupt end-to-end training.
Approach
The authors introduce SDPRLayer, which embeds convex semidefinite programming relaxations into neural networks and computes gradients via implicit differentiation to guarantee globally optimal solutions and accurate backpropagation.
Key results
- Introduction of SDPRLayer, a differentiable optimization layer for polynomial optimization problems
- Theoretical conditions guaranteeing correct and efficient gradient computation
- Demonstration of training failures caused by local minima in existing differentiable solvers
- Successful training of a deep neural network for robot localization in challenging lighting
Why it matters
Provides robotics researchers with a robust tool for end-to-end learning that avoids the pitfalls of local optima, improving reliability in perception and control pipelines.
Abstract
A recent set of techniques in the robotics community, known as certifiably correct methods, frames robotics problems as polynomial optimization problems and applies convex, semidefinite programming (SDP) relaxations to either find or certify their global optima. In parallel, differentiable optimization allows optimization problems to be embedded into end-to-end learning frameworks and has received considerable attention in the robotics commu- nity. In this article, we consider the ill effect of convergence to spurious local minima in the context of learning frameworks that use differentiable optimization. We present SDPRLayers, an ap- proach that seeks to address this issue by combining convex re- laxations with implicit differentiation techniques to provide cer- tifiably correct solutions and gradients throughout the training process. We provide theoretical results that outline conditions for the correctness of these gradients and provide efficient means for their computation. Our approach is first applied to two simple- but-demonstrative simulated examples, which expose the potential pitfalls of reliance on local optimization in existing, state-of-the-art, differentiable optimization methods. We then apply our method in a real-world application: we train a deep neural network to detect image keypoints for robot localization in challenging lighting conditions. We provide our open-source, PyTorch implementation of SDPRLayers and our differentiable localization pipeline.