The Isotron Algorithm: High-Dimensional Isotonic Regression

The Perceptron algorithm elegantly solves binary classification problems that have a margin between positive and negative examples. Isotonic regression (fitting an arbitrary increasing function in one dimension) is also a natural problem with a simple solution. By combining the two, we get a new simple regression algorithm in high dimensions, with strong guarantees.