Machine learning models often need to satisfy many real-world policy goals and capture some kinds of side information. We show that many such goals can be mathematically expressed as constraints on the model’s predictions on the data, which we call rate constraints. In this paper, we study the specific problem of training non-convex models subject to these rate constraints (which are non-convex and non-differentiable), and the general problem of constrained optimization of possibly non-convex objectives with possibly non-convex and non-differentiable constraints. In the non-convex setting, the Lagrangian may not have an equilibrium to converge to, and thus using the standard approach of Lagrange multipliers may fail as a deterministic solution may not even exist. Furthermore, if the constraints are non-differentiable, then one cannot optimize the Lagrangian with gradient-based methods by definition. To solve these issues, we present the proxy-Lagrangian, which leads to an algorithm that produces a stochastic classifier with theoretical guarantees by playing a two-player non-zero-sum game. The first player minimizes external regret in terms of a differentiable relaxation of the constraints and the second player enforces the original constraints by minimizing swap-regret: this leads to finding a solution concept which we call a semi-coarse correlated equilibrium which we interestingly show corresponds to an approximately optimal and feasible solution to the constrained optimization problem. We then give a procedure which shrinks the randomized solution down to one that is a mixture of at most m + 1 deterministic solutions. This culminates into end-to-end procedures which can provably solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints. We provide extensive experimental results on benchmark and real-world problems, enforcing a broad range of policy goals including different fairness metrics, and other goals on accuracy, coverage, recall, and churn.