Learning functions varying along a central subspace
This work addresses the challenge of sample complexity in high-dimensional regression for researchers in statistics and machine learning, though it is incremental as it builds on existing GCR methods.
The paper tackles the problem of learning high-dimensional functions with low-dimensional structures by analyzing the Generalized Contour Regression (GCR) algorithm for estimating a central subspace and using piecewise polynomials for approximation. It proves that GCR achieves a mean squared regression error of order (n/log n)^{-2s/(2s+d)}, depending on the subspace dimension d instead of the ambient dimension D, and validates this with numerical experiments.
Many functions of interest are in a high-dimensional space but exhibit low-dimensional structures. This paper studies regression of a $s$-Hölder function $f$ in $\mathbb{R}^D$ which varies along a central subspace of dimension $d$ while $d\ll D$. A direct approximation of $f$ in $\mathbb{R}^D$ with an $\varepsilon$ accuracy requires the number of samples $n$ in the order of $\varepsilon^{-(2s+D)/s}$. In this paper, we analyze the Generalized Contour Regression (GCR) algorithm for the estimation of the central subspace and use piecewise polynomials for function approximation. GCR is among the best estimators for the central subspace, but its sample complexity is an open question. We prove that GCR leads to a mean squared estimation error of $O(n^{-1})$ for the central subspace, if a variance quantity is exactly known. The estimation error of this variance quantity is also given in this paper. The mean squared regression error of $f$ is proved to be in the order of $\left(n/\log n\right)^{-\frac{2s}{2s+d}}$ where the exponent depends on the dimension of the central subspace $d$ instead of the ambient space $D$. This result demonstrates that GCR is effective in learning the low-dimensional central subspace. We also propose a modified GCR with improved efficiency. The convergence rate is validated through several numerical experiments.