  Though learning has become a core component of modern information processing,
there is now ample evidence that it can lead to biased, unsafe, and prejudiced
systems. The need to impose requirements on learning is therefore paramount,
especially as it reaches critical applications in social, industrial, and
medical domains. However, the non-convexity of most modern statistical problems
is only exacerbated by the introduction of constraints. Whereas good
unconstrained solutions can often be learned using empirical risk minimization,
even obtaining a model that satisfies statistical constraints can be
challenging. All the more so, a good one. In this paper, we overcome this issue
by learning in the empirical dual domain, where constrained statistical
learning problems become unconstrained and deterministic. We analyze the
generalization properties of this approach by bounding the empirical duality
gap -- i.e., the difference between our approximate, tractable solution and the
solution of the original (non-convex) statistical problem -- and provide a
practical constrained learning algorithm. These results establish a constrained
counterpart to classical learning theory, enabling the explicit use of
constraints in learning. We illustrate this theory and algorithm in
rate-constrained learning applications arising in fairness and adversarial
robustness.
