Near-optimal max-affine estimators for convex regression

[edit]

Gabor Balazs, András György, Csaba Szepesvari ;
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:56-64, 2015.

Abstract

This paper considers least squares estimators for regression problems over convex, uniformly bounded, uniformly Lipschitz function classes minimizing the empirical risk over max-affine functions (the maximum of finitely many affine functions). Based on new results on nonlinear nonparametric regression and on the approximation accuracy of max-affine functions, these estimators are proved to achieve the optimal rate of convergence up to logarithmic factors. Preliminary experiments indicate that a simple randomized approximation to the optimal estimator is competitive with state-of-the-art alternatives.

Related Material