Abstract
Adding constraint support in Machine Learning has the potential to address outstanding issues in data-driven AI systems, such as safety and fairness. Existing approaches typically apply constrained optimization techniques to ML training, enforce constraint satisfaction by adjusting the model design, or use constraints to correct the output. Here, we investigate a different, complementary, strategy based on "teaching" constraint satisfaction to a supervised ML method via the direct use of a state-of-the-art constraint solver: this enables taking advantage of decades of research on constrained optimization with limited effort. In practice, we use a decomposition scheme alternating master steps (in charge of enforcing the constraints) and learner steps (where any supervised ML model and training algorithm can be employed). The process leads to approximate constraint satisfaction in general, and convergence properties are difficult to establish; despite this fact, we found empirically that even a na"ive setup of our approach performs well on ML tasks with fairness constraints, and on classical datasets with synthetic constraints.
Introduction
Standard Machine Learning (ML) models excel at pattern recognition but often fail to adhere to explicit rules, such as fairness or physical laws. Traditional approaches to constraint enforcement—modifying loss functions, specialized architectures, or post-hoc output correction—often suffer from inflexibility or failure to truly "teach" the model the underlying rules. This challenge is particularly acute for relational constraints, which involve multiple data points at once, such as population-level fairness metrics. This paper explores "Moving Targets," a framework designed to decouple learning from constraint satisfaction by iteratively adjusting target labels using a constraint solver.
The Moving Targets Framework
The core innovation is a decomposition-based approach that separates the learning process from rule enforcement. The algorithm iterates between a Master Step and a Learner Step.
In the Master Step, a dedicated constraint solver (such as a Mixed-Integer Linear Programmer) takes the current predictions and the original ground-truth labels to calculate a new set of "adjusted targets" ($z$) that satisfy constraints while remaining close to the original labels. In the Learner Step, a standard ML model is trained on these shifted targets. This decoupling allows for the use of non-differentiable constraints and any supervised learning model.
Experimental Evaluation
The framework was evaluated on several datasets from the UCI Machine Learning repository, focusing on two types of constraints:
- Balance Constraints: Ensuring classes are predicted in a roughly uniform distribution (tested on iris, redwine, whitewine, shuttle, and dota2).
- Fairness Constraints: Using the DIDI indicator to minimize disparate impact on protected groups in the adult (Census Income) and crime (Communities and Crime) datasets.
Results and Discussion
Empirical results demonstrate that Moving Targets effectively drives constraint violations toward zero while maintaining high predictive scores. The method proved to be model-agnostic, working well across diverse architectures including Neural Networks and Tree Ensembles.
Key findings include:
- Constraint Satisfaction: The method consistently achieves feasibility where traditional regularization methods struggle.
- Scalability: Despite the use of exact solvers, the approach scales to datasets with tens of thousands of examples, such as dota2.
- Generalization: The constraint satisfaction properties held up well when evaluated on unseen test data, indicating the model learned the underlying rules rather than just memorizing training targets.
Conclusion
Moving Targets provides a flexible, model-agnostic way to inject complex constraints into supervised learning. By decoupling learning from rule enforcement, it allows researchers to leverage decades of progress in constraint optimization to address critical issues like safety and fairness in modern AI systems. While formal convergence proofs for non-convex models remain a challenge, the empirical success across diverse tasks suggests a powerful new tool for the ML practitioner's toolkit.
Summary updated