Global risk bounds and adaptation in univariate convex regression

By Adityanand Guntuboyina, Bodhisattva Sen. 2013

87 citations recorded by the source corpus.

We consider the problem of nonparametric estimation of a convex regression function $$\phi _0$$ϕ0. We study the risk of the least squares estimator (LSE) under the natural squared error loss. We show that the risk is always bounded from above by $$n^{-4/5}$$n-4/5 modulo logarithmic factors while being much smaller when $$\phi _0$$ϕ0 is well-approximable by a piecewise affine convex function with not too many affine pieces (in which case, the risk is at most $$1/n$$1/n up to logarithmic factors). On the other hand, when $$\phi _0$$ϕ0 has curvature, we show that no estimator can have risk smaller than a constant multiple of $$n^{-4/5}$$n-4/5 in a very strong sense by proving a “local” minimax lower bound. We also study the case of model misspecification where we show that the LSE exhibits the same global behavior provided the loss is measured from the closest convex projection of the true regression function. In the process of deriving our risk bounds, we prove new results for the metric entropy of local neighborhoods of the space of univariate convex functions. These results, which may be of independent interest, demonstrate the non-uniform nature of the space of univariate convex functions in sharp contrast to classical function spaces based on smoothness constraints.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3d6e3cd934604e88e564493b7eba1507170ddacd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Least squares estimation in the monotone single index model (2016, result): “Similar (nearly parametric) results for shapeconstrained estimators can be found in Chatterjee et al. (2015); Han and Wellner (2016); Chatterjee and Lafferty (2015); Kim et al. (2016); Guntuboyina and Sen (2015).”
Isotonic regression in general dimensions (2017, methodology): “This line of study was pioneered by Zhang (2002) in the context of univariate isotonic regression, followed by Chatterjee, Guntuboyina and Sen (2015) and most recently Bellec (2017), who proved that R(θ̂n, θ0) ≤ inf θ∈M(GX ) {‖θ − θ0‖22 n + k(θ) n log ( en k(θ) )} , (4) where k(θ) is the number of…”
Generalized additive and index models with shape constraints (2014, methodology): “For the problem of univariate convex regression, see Hanson and Pledger (1976), Groeneboom et al. (2001, 2008) and Guntuboyina and Sen (2013).”
Faithful Variable Screening for High-Dimensional Convex Regression (2014, background): “Guntuboyina and Sen (2013) analyze univariate convex regression and show surprisingly that the risk of the MLE is adaptive to the complexity of the true function.”
Sharp oracle inequalities for Least Squares estimators in shape restricted regression (2015, methodology): “2, these oracle inequalities hold in deviation with exponential probability bounds and in expectation for any μ ∈ R, whereas previously known oracle inequalities from [11, 7] only hold in expectation under the additional assumption that μ ∈ KC x1,.”
Nonparametric Shape-Restricted Regression (2017, background): “This inequality has been proved by [19, Section 4] improving earlier results of [28, 67] which had superfluous multiplicative constants.”
On risk bounds in isotonic and other shape restricted regression problems (2013, background): “A weaker version of this inequality appeared in [19], Theorem 2.”
Bayesian fractional posteriors (2016, background): “It is recent practice in the frequentist literature to avoid additional smoothness assumptions on convex functions while studying rates of convergence [3, 29].”