  The last decade witnessed a rise in the importance of supervised learning
applications involving {\em big data} and {\em big models}. Big data refers to
situations where the amounts of training data available and needed causes
difficulties in the training phase of the pipeline. Big model refers to
situations where large dimensional and over-parameterized models are needed for
the application at hand. Both of these phenomena lead to a dramatic increase in
research activity aimed at taming the issues via the design of new
sophisticated optimization algorithms. In this paper we turn attention to the
{\em big constraints} scenario and argue that elaborate machine learning
systems of the future will necessarily need to account for a large number of
real-world constraints, which will need to be incorporated in the training
process. This line of work is largely unexplored, and provides ample
opportunities for future work and applications. To handle the {\em big
constraints} regime, we propose a {\em stochastic penalty} formulation which
{\em reduces the problem to the well understood big data regime}. Our
formulation has many interesting properties which relate it to the original
problem in various ways, with mathematical guarantees. We give a number of
results specialized to nonconvex loss functions, smooth convex functions,
strongly convex functions and convex constraints. We show through experiments
that our approach can beat competing approaches by several orders of magnitude
when a medium accuracy solution is required.
