  We address the problem of training models with black-box and hard-to-optimize
metrics by expressing the metric as a monotonic function of a small number of
easy-to-optimize surrogates. We pose the training problem as an optimization
over a relaxed surrogate space, which we solve by estimating local gradients
for the metric and performing inexact convex projections. We analyze gradient
estimates based on finite differences and local linear interpolations, and show
convergence of our approach under smoothness assumptions with respect to the
surrogates. Experimental results on classification and ranking problems verify
the proposal performs on par with methods that know the mathematical
formulation, and adds notable value when the form of the metric is unknown.
