Randomized Learning of the Second-Moment Matrix of a Smooth Function

Abstract

Consider an open set $\mathbb{D}\subseteq {\mathbb{R}}^n$, equipped with a probability measure $\mu$. An important characteristic of a smooth function $f:\mathbb{D}\to \mathbb{R}$ is its \emph{second-moment matrix} ${\Sigma }_{\mu }:=\int \nabla f(x)\nabla f(x{)}^{\ast }\mu (dx)\in {\mathbb{R}}^{n\times n}$, where $\nabla f(x)\in {\mathbb{R}}^n$ is the gradient of $f(\cdot )$ at $x\in \mathbb{D}$ and $\ast$ stands for transpose. For instance, the span of the leading $r$ eigenvectors of ${\Sigma }_{\mu }$ forms an \emph{active subspace} of $f(\cdot )$, which contains the directions along which $f(\cdot )$ changes the most and is of particular interest in \emph{ridge approximation}. In this work, we propose a simple algorithm for estimating ${\Sigma }_{\mu }$ from random point evaluations of $f(\cdot )$ \emph{without} imposing any structural assumptions on ${\Sigma }_{\mu }$. Theoretical guarantees for this algorithm are established with the aid of the same technical tools that have proved valuable in the context of covariance matrix estimation from partial measurements.