Convexification of Learning from Constraints
This addresses a fundamental optimization bottleneck in machine learning, though it is incremental as it builds on existing convexification techniques.
The paper tackles the non-convex optimization problem in regularized empirical risk minimization with constrained labels by constructing mixed integer programs with convex objective functions, deriving efficient convex extensions for common loss and regularization functions.
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.