Probably Approximately Correct Constrained Learning
arXiv:2006.05487
Abstract
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.
References in corpus (16)
- Adam: A Method for Stochastic Optimization
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Understanding deep learning requires rethinking generalization
- Theoretically Principled Trade-off between Robustness and Accuracy
- Counterfactual Fairness
- Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
- Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
- A Closer Look at Memorization in Deep Networks
- Learning with a Strong Adversary
- A Convex Framework for Fair Regression
- Learning One-hidden-layer Neural Networks with Landscape Design
- Constrained Policy Optimization
- Empirical Risk Minimization under Fairness Constraints
- Invariance-Preserving Localized Activation Functions for Graph Neural Networks
- Ray Interference: a Source of Plateaus in Deep Reinforcement Learning
- The Information Autoencoding Family: A Lagrangian Perspective on Latent Variable Generative Models