  We consider the problem of estimating an unknown coordinate-wise monotone
function given noisy measurements, known as the isotonic regression problem.
Often, only a small subset of the features affects the output. This motivates
the sparse isotonic regression setting, which we consider here. We provide an
upper bound on the expected VC entropy of the space of sparse coordinate-wise
monotone functions, and identify the regime of statistical consistency of our
estimator. We also propose a linear program to recover the active coordinates,
and provide theoretical recovery guarantees. We close with experiments on
cancer classification, and show that our method significantly outperforms
standard methods.
