# Probably Approximately Correct Constrained Learning

arXiv: https://arxiv.org/abs/2006.05487 · HTML: https://mlsanity.com/paper/2006.05487/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 30 of 47)

- [A Comprehensive Survey of Few-shot Learning: Evolution, Applications, Challenges, and Opportunities](https://mlsanity.com/paper/2205.06743/) (2022)
- [Model-Based Domain Generalization](https://mlsanity.com/paper/2102.11436/) (2021)
- [Towards Principled Disentanglement for Domain Generalization](https://mlsanity.com/paper/2111.13839/) (2021)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [On the Sample Complexity of Stability Constrained Imitation Learning](https://mlsanity.com/paper/2102.09161/) (2021)
- [Universal Approximation Under Constraints is Possible with Transformers](https://mlsanity.com/paper/2110.03303/) (2021)
- [HardNet: Hard-Constrained Neural Networks with Universal Approximation Guarantees](https://mlsanity.com/paper/2410.10807/) (2024)
- [A Lagrangian Duality Approach to Active Learning](https://mlsanity.com/paper/2202.04108/) (2022)
- [Learning Robust Output Control Barrier Functions from Safe Expert Demonstrations](https://mlsanity.com/paper/2111.09971/) (2021)
- [Constrained Diffusion Models via Dual Training](https://mlsanity.com/paper/2408.15094/) (2024)
- [Automatic Data Augmentation via Invariance-Constrained Learning](https://mlsanity.com/paper/2209.15031/) (2022)
- [Resilient Constrained Learning](https://mlsanity.com/paper/2306.02426/) (2023)
- [Learning Robust Hybrid Control Barrier Functions for Uncertain Systems](https://mlsanity.com/paper/2101.06492/) (2021)
- [Training Stable Graph Neural Networks Through Constrained Learning](https://mlsanity.com/paper/2110.03576/) (2021)
- [Constrained Sampling with Primal-Dual Langevin Monte Carlo](https://mlsanity.com/paper/2411.00568/) (2024)
- [Learning (Approximately) Equivariant Networks via Constrained Optimization](https://mlsanity.com/paper/2505.13631/) (2025)
- [Composition and Alignment of Diffusion Models using Constrained Learning](https://mlsanity.com/paper/2508.19104/) (2025)
- [Near-Optimal Solutions of Constrained Learning Problems](https://mlsanity.com/paper/2403.11844/) (2024)
- [VENI, VINDy, VICI: a generative reduced-order modeling framework with uncertainty quantification](https://mlsanity.com/paper/2405.20905/) (2024)
- [Alignment of large language models with constrained learning](https://mlsanity.com/paper/2505.19387/) (2025)
- [Balancing Act: Constraining Disparate Impact in Sparse Models](https://mlsanity.com/paper/2310.20673/) (2023)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Learning Globally Smooth Functions on Manifolds](https://mlsanity.com/paper/2210.00301/) (2022)
- [Loss Shaping Constraints for Long-Term Time Series Forecasting](https://mlsanity.com/paper/2402.09373/) (2024)
- [Solving Differential Equations with Constrained Learning](https://mlsanity.com/paper/2410.22796/) (2024)
- [Constrained Sliced Wasserstein Embedding](https://mlsanity.com/paper/2506.02203/) (2025)
- [AL-CoLe: Augmented Lagrangian for Constrained Learning](https://mlsanity.com/paper/2510.20995/) (2025)
- [CRNNTL: convolutional recurrent neural network and transfer learning for QSAR modelling](https://mlsanity.com/paper/2109.03309/) (2021)
- [Structured Graph Variational Autoencoders for Indoor Furniture layout Generation](https://mlsanity.com/paper/2204.04867/) (2022)

## Abstract (arXiv)

As learning solutions reach critical applications in social, industrial, and medical domains, the need to curtail their behavior has become paramount. There is now ample evidence that without explicit tailoring, learning can lead to biased, unsafe, and prejudiced solutions. To tackle these problems, we develop a generalization theory of constrained learning based on the probably approximately correct (PAC) learning framework. In particular, we show that imposing requirements does not make a learning problem harder in the sense that any PAC learnable class is also PAC constrained learnable using a constrained counterpart of the empirical risk minimization (ERM) rule. For typical parametrized models, however, this learner involves solving a constrained non-convex optimization program for which even obtaining a feasible solution is challenging. To overcome this issue, we prove that under mild conditions the empirical dual problem of constrained learning is also a PAC constrained learner that now leads to a practical constrained learning algorithm based solely on solving unconstrained problems. We analyze the generalization properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.