The Theory and Practice of MAP Inference over Non-Convex Constraints
This addresses the challenge of making reliable predictions under safety-critical constraints for applications like autonomous systems, though it appears incremental in extending constrained MAP inference to non-convex settings.
The paper tackles the problem of computing constrained maximum a posteriori (MAP) predictions for probabilistic ML systems under non-convex constraints, such as predicting trajectories that avoid obstacles. It develops both exact and approximate methods that outperform constraint-agnostic baselines and scale to complex densities intractable for state-of-the-art exact solvers.
In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction efficiently and reliably extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our approaches outperform constraint-agnostic baselines, and scale to complex densities intractable for SoTA exact solvers.