Efficient Learning of Monotone Concepts via Quadratic Optimization

We consider a non-parametric regression model, in which the regression function to be estimated is coordinate-wise monotone. Such functions can model, for example, the dependence of an option price on a strike price, duration and a price of an underlying asset. We propose a simple algorithm based on quadratic optimization, which estimates the regression function in polynomial time. Numerical results are provided, which show that the algorithm is quite robust to possible discontinuities of the regression function. Our main theoretical result shows that the expected VC-entropy of the space of coordinate-wise monotone functions grows exponentially. As a result, the estimating function, constructed by our algorithm, converges to the true regression function, as the number of observations goes to infinity, and the estimating procedure is consistent.