Entropy and Learning of Lipschitz Functions under Log-Concave Measures

Abstract

We study regression of $1$-Lipschitz functions under a log-concave measure $\hat{I}¼$ on ${\mathbb{R}}^d$. We focus on the high-dimensional regime where the sample size $n$ is subexponential in $d$, in which distribution-free estimators are ineffective. We analyze two polynomial-based procedures: the projection estimator, which relies on knowledge of an orthogonal polynomial basis of $\hat{I}¼$, and the least-squares estimator over low-degree polynomials, which requires no knowledge of $\hat{I}¼$ whatsoever. Their risk is governed by the rate of polynomial approximation of Lipschitz functions in $L^2(\hat{I}¼)$. When this rate matches the Gaussian one, we show that both estimators achieve minimax bounds over a wide range of parameters. A key ingredient is sharp entropy estimates for the class of $1$-Lipschitz functions in $L^2(\hat{I}¼)$, which are new even in the Gaussian setting.

45 pages