  Though learning has become a core technology of modern information
processing, there is now ample evidence that it can lead to biased, unsafe, and
prejudiced solutions. 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
learning problems is only exacerbated by the introduction of constraints.
Whereas good unconstrained solutions can often be learned using empirical risk
minimization (ERM), 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, finite dimensional, 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 of classical
learning theory and enable the explicit use of constraints in learning. We
illustrate this algorithm and theory in rate-constrained learning applications.
