  Regularized empirical risk minimization with constrained labels (in contrast
to fixed labels) is a remarkably general abstraction of learning. For common
loss and regularization functions, this optimization problem assumes the form
of a mixed integer program (MIP) whose objective function is non-convex. In
this form, the problem is resistant to standard optimization techniques. We
construct MIPs with the same solutions whose objective functions are convex.
Specifically, we characterize the tightest convex extension of the objective
function, given by the Legendre-Fenchel biconjugate. Computing values of this
tightest convex extension is NP-hard. However, by applying our characterization
to every function in an additive decomposition of the objective function, we
obtain a class of looser convex extensions that can be computed efficiently.
For some decompositions, common loss and regularization functions, we derive a
closed form.
