2022/01/26 by Jones, Lee, Rybnikov, Konstantin
#Local learning #convex optimization #estimator #minimax #polynomial #quantifier elimination #ridge regression #semialgebraic #statistical learning
paper · doi:10.4230/dagsemproc.06201.3
Suppose we have a number of noisy measurements of an unknown real-valued function f near point of interest mathbfx0 in mathbbRd. Suppose also that nothing can be assumed about the noise distribution, except for zero mean and bounded covariance matrix. We want to estimate f at mathbfx=x0 using a general linear parametric family f(mathbfx;mathbfa) = a0 h0 (mathbfx) ++ aq hq (mathbfx), where mathbfa in mathbbRq and hi's are bounded functions on a neighborhood B of mathbfx0 which contains all points of measurement. Typically, B is a Euclidean ball or cube in mathbbRd (more generally, a ball in an lp-norm). In the case when the hi's are polynomial functions in x1,ldots,xd the model is called locally-polynomial. In particular, if the hi's form a basis of the linear space of polynomials of degree at most two, the model is called locally-quadratic (if the degree is at most three, the model is locally-cubic, etc.). Often, there is information, which is called context, about the function f (restricted to B ) available, such as that it takes values in a known interval, or that it satisfies a Lipschitz condition. The theory of local minimax estimation with context for locally-polynomial models and approximately locally polynomial models has been recently initiated by Jones. In the case of local linearity and a bound on the change of f on B, where B is a ball, the solution for squared error loss is in the form of ridge regression, where the ridge parameter is identified; hence, minimax justification for ridge regression is given together with explicit best error bounds. The analysis of polynomial models of degree above 1 leads to interesting and difficult questions in real algebraic geometry and non-linear optimization. We show that in the case when f is a probability function, the optimal (in the minimax sense) estimator is effectively computable (with any given precision), thanks to Tarski's elimination principle.