  In many real world applications of machine learning, models have to meet
certain domain-based requirements that can be expressed as constraints (e.g.,
safety-critical constraints in autonomous driving systems). Such constraints
are often handled by including them in a regularization term, while learning a
model. This approach, however, does not guarantee 100% satisfaction of the
constraints: it only reduces violations of the constraints on the training set
rather than ensuring that the predictions by the model will always adhere to
them. In this paper, we present a framework for learning models that provably
fulfil the constraints under all circumstances (i.e., also on unseen data). To
achieve this, we cast learning as a maximum satisfiability problem, and solve
it using a novel SaDe algorithm that combines constraint satisfaction with
gradient descent. We compare our method against regularization based baselines
on linear models and show that our method is capable of enforcing different
types of domain constraints effectively on unseen data, without sacrificing
predictive performance.
