Sparse High-Dimensional Isotonic Regression
David Gamarnik · Julia Gaudio

Wed Dec 11th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #22

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 several standard methods.

Author Information

David Gamarnik (Massachusetts Institute of Technology)
Julia Gaudio (Massachusetts Institute of Technology)

I am a third-year PhD student at the MIT Operations Research Center, as well as LIDS (Laboratory for Information and Decision Systems). My main research interest is in applied probability. I am a Microsoft Research PhD fellow. Prior to coming to MIT, I completed an ScB in Applied Mathematics and an ScM in Computer Science concurrently at Brown University.

More from the Same Authors