Near-optimal max-affine estimators for convex regression
AISTATS, page 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.