betaFeedback

WorksMathematics

The Manifold-Index Model: provably and efficiently avoiding the statistical and computational curse of dimensionality

Abstract

We study vector-valued regression with predictors filling a tube around an unknown mm-dimensional manifold M\mathcal{M} in RD\mathbb{R}^D. In the Manifold-Index Model, the mean response is F=f∘ΠMF=f\circΠ_{\mathcal{M}}, where ΠMΠ_{\mathcal{M}} is the nearest-point projection onto M\mathcal{M} and f:M→Rpf:\mathcal{M}\to\mathbb{R}^p is a possibly non-injective link function. Multiscale ANisotropic lOcal Regression (MANOR) estimates tangent planes by multiscale PCA of predictors with similar responses, then refines them by pooling outer products of local slopes. The neighborhoods narrow tangentially while retaining complete normal fibers. We assume a Lipschitz link differential and bounded response noise. For p≥mp\ge m, under our geometric and sampling conditions, nn independent observations give mean tangent-space error of order n−2/(m+4)n^{-2/(m+4)} and integrated squared prediction error at the mm-dimensional nonparametric rate n−4/(m+4)n^{-4/(m+4)}, up to logarithmic factors. In a scaling regime with fixed intrinsic dimension, model and scale parameters, and ratio of manifold volume to the mm-th power of its reach, the required sample size grows polynomially in D+pD+p, and computation is polynomial in nn, DD and pp. Numerical experiments on curves with non-monotone links and surfaces with vector-valued responses compare observed convergence rates with the theoretical bounds; a Langevin dynamics example tests prediction of hitting probabilities under an approximate manifold-index model.

Introduction

We seek to estimate a function FF from nn independent observations

(Xi,Yi),Yi=F(Xi)+ζi,i=1,…,n,(X_i,Y_i), \qquad Y_i=F(X_i)+\zeta_i, \qquad i=1,\ldots,n,

where the predictors Xi∈RDX_i\in\mathbb{R}^{D} are independent copies of a random vector XX, the responses YiY_i take values in Rp\mathbb{R}^{p}, and the noise vectors ζi\zeta_i are centered and independent of each other and of the predictors. We write (X,Y,ζ)(X,Y,\zeta) for a generic observation and its noise. Suppose that all we know about FF is that it is of Hölder smoothness ss on a full-dimensional region of RD\mathbb{R}^{D}. The best achievable accuracy is then governed by a simple bias–variance trade-off. A local estimator F^\widehat{F} of suitable order on a neighborhood of width bb has a squared bias of order b2sb^{2s}, and its variance is inversely proportional to the number of observations in the neighborhood, which is of order nbDnb^D at a typical interior point when the predictors have a locally bounded positive ambient density. Balancing the two terms gives

b2s≍1nbD⟹b≍n−1/(2s+D),E∥F^(X)−F(X)∥2≍n−2s/(2s+D),(1)b^{2s} \asymp\frac{1}{nb^D} \quad\Longrightarrow\quad b \asymp n^{-1/(2s+D)}, \qquad\mathbb{E}\lVert\widehat{F}(X)-F(X)\rVert^2 \asymp n^{-2s/(2s+D)}, \tag*{(1)}

or n−s/(2s+D)n^{-s/(2s+D)} for the root mean squared error. This is the minimax rate over the class of ss-smooth functions ([94, 45, 98]), and kernel, Fourier and multiscale estimators attain it ([45, 14, 15, 16]). The learning rate 2s/(2s+D)2s/(2s+D) degrades quickly as DD grows. This is an instance of the curse of dimensionality. Since the rate is minimax, it cannot be improved uniformly over all ss-smooth functions; it can only be improved for regression problems with additional structure. Even when additional assumptions on FF give a learning rate with exponent independent of DD, the constants in the bounds on the estimation error may grow exponentially with DD, so that the sample size sufficient to guarantee a prescribed accuracy still grows exponentially with DD: this is also part of the curse of dimensionality. When the existence of an estimator that attains a learning rate independent of DD is proven, the next problem becomes to produce an algorithm for constructing the estimator at computational cost not exponential in DD.

It is natural to ask which kind of special structure in FF is both plausible in applications and exploitable by estimators so that the statistical and computational costs do not grow exponentially with DD. This of course has been subject of much research, and we discuss some of the ideas most related to the present work in § 1.4.

As we discuss at length in § 1.4, we are interested in understanding when additional structure in FF helps avoid the curse of dimensionality; and in particular when FF has compositional structure. We study the Manifold-Index Model: the predictors fill a tube around an unknown mm-dimensional manifold in RD\mathbb{R}^D, and their mean responses depend only on their nearest points on the manifold. We discuss the detail momentarily in § 1.1. This model extends multi-index regression by replacing the linear projection onto a fixed linear subspace with the nonlinear nearest-point projection onto the manifold. For curves, this construction is essentially the Nonlinear Single-Variable Model of Wu and Maggioni [102]. From nn observations, Multiscale Anisotropic IOcal Regression (MANOR) attains the rate of mm-dimensional nonparametric regression without knowledge of the manifold or the link. At fixed model scales, normalized response range and ratio of the manifold’s volume to the mm-th power of its reach, which are natural scalings of the problem, the sample requirement grows polynomially with DD; the computational cost is polynomial in DD and nn (§ 1.2). MANOR initializes the tangent spaces by multiscale local principal component analysis (PCA) ((Little et al., 2009a,b; Chen et al., 2011; Little et al., 2017)) of predictors with similar responses, blending inverse regression ([69, 37, 28]) ideas with geometric analysis of the (approximate) level sets. It refines these estimated tangent spaces by pooling outer products of local regression slopes to form adapted, anisotropic neighborhoods ([52, 104, 31]), and finally uses them for prediction with highly anisotropic local kernels.

We next define the Manifold-Index Model and state our main results informally; § 1.4 reviews related models and estimators and puts this work in a broad context.

The Manifold-Index Model

Let M⊂RD\mathcal{M} \subset\mathbb{R}^{D} be an mm-dimensional submanifold whose reach reach⁡M\operatorname{reach}_{\mathcal{M}} is positive ([39, 82]). Every point at distance less than reach⁡M\operatorname{reach}_{\mathcal{M}} from M\mathcal{M} has a unique nearest point on M\mathcal{M}, so the nearest-point projection

ΠM(x)=arg min⁡q∈M∥x−q∥\Pi_{\mathcal{M}}(x) = \underset{q \in\mathcal{M}}{\operatorname{arg\,min}} \lVert x-q \rVert

is well defined on the tube of radius reach⁡M\operatorname{reach}_{\mathcal{M}} around M\mathcal{M}. Every XX in this tube decomposes as

X=Q+Z,Q=ΠMX∈M,(2)X=Q+Z,\qquad Q=\Pi_{\mathcal{M}}X\in\mathcal{M}, \tag*{(2)}

where the manifold index QQ is the base point, the nearest point of M\mathcal{M} to XX, and Z=X−QZ=X-Q is the displacement from it (Figure 1). Write TQMT_Q\mathcal{M} for the tangent space at QQ and NQM=(TQM)⊥N_Q\mathcal{M}=(T_Q\mathcal{M})^\perp for its normal space.

Figure 1. Geometry, response values and gradients in the Manifold-Index Model. All panels use a cylindrical surface patch M\mathcal{M} with m=p=2m=p=2, D=3D=3, and f(s,a)=((s+a)/2,a)f(s,a)=((s+a)/\sqrt{2},a), where ss is circumferential arc length and aa is the axial coordinate. (a) Normal fibers and nearest-point projection. The arrows project X=Q+ZX=Q+Z and X′=Q−ZX'=Q-Z to QQ, so F(X)=F(X′)=f(Q)F(X)=F(X')=f(Q). The orange plane is TQMT_Q\mathcal{M}; the dashed grey boundary encloses a tube of diameter O(σND−m)O(\sigma_N\sqrt{D-m}) (Assumption (A2)). (b) Component level sets. The purple sheet F1=0F_1=0 and teal sheet F2=0F_2=0 meet M\mathcal{M} along the curves s+a=0s+a=0 and a=0a=0, respectively, and extend along normal fibers. Their intersection is the normal fiber through QQ, where F=(0,0)F=(0,0). The orange, black and red arrows show ∇F1\nabla F_1 at XX, QQ, X′X', respectively; the grey-green arrow shows ∇F2\nabla F_2. (c) The same gradients translated to a common origin in TQMT_Q\mathcal{M} (orange). For a unit-radius cylinder and signed outward normal offset rr, ∇F1=(es/(1+r)+ea)/2\nabla F_1=(e_s/(1+r)+e_a)/\sqrt{2} and ∇F2=ea\nabla F_2=e_a, where es,eae_s,e_a are the unit circumferential and axial tangent vectors at QQ. Thus ∇F1\nabla F_1 changes along the fiber, while ∇F2\nabla F_2 is unchanged; each gradient is orthogonal to its component level surface in (b), and the two gradients span TQMT_Q\mathcal{M} at each location.

Definition 1.1 (Manifold-Index Model). A random pair (X,Y)∈RD×Rp(X,Y)\in\mathbb{R}^{D}\times\mathbb{R}^{p} follows the Manifold-Index Model if

E[Y∣X]=F(X)=f(ΠMX),\mathbb{E}[Y\mid X]=F(X)=f(\Pi_{\mathcal{M}}X),

where M⊂RD\mathcal{M}\subset\mathbb{R}^{D} is an mm-dimensional submanifold with reach⁡M>0\operatorname{reach}_{\mathcal{M}}>0, f:M→Rpf:\mathcal{M}\to\mathbb{R}^{p} is the link function, and XX has distance at most RR from M\mathcal{M}, for some R<reach⁡MR<\operatorname{reach}_{\mathcal{M}}.

Throughout, the normal fiber over q∈Mq\in\mathcal{M} is the affine disk {q+z:z∈NqM, ∥z∥≤R}\{q+z:z\in N_q\mathcal{M},\ \lVert z\rVert\le R\} in the predictor tube. Write DfDf for the differential of ff, represented by a p×mp\times m matrix in orthonormal tangent coordinates, and ∇F(x)∈RD×p\nabla F(x)\in\mathbb{R}^{D\times p} for the matrix whose columns are the gradients of the pp components of FF. We call Df(q)Df(q) rank deficient when rank⁡Df(q)<m\operatorname{rank}Df(q)<m; isolation of such points always refers to the base manifold M\mathcal{M}. It is partially rank deficient if 0<rank⁡Df(q)<m0<\operatorname{rank}Df(q)<m. For a matrix MM, Ran⁡M\operatorname{Ran}M denotes its range and MTM^{T} its transpose.

Problem statement. Under the Manifold-Index Model, the manifold M\mathcal{M}, the link ff and the distribution of XX are unknown. Our goal is to estimate FF from independent observations (Xi,Yi)(X_i,Y_i) with Yi=F(Xi)+ζiY_i=F(X_i)+\zeta_i, where the centered noise vectors are independent of the predictors and of one another; they are sub-Gaussian, and on the initialization sample their norms are at most one eighth of the response-window width ((Assumption (A5))).

Three features of the model deserve emphasis.

The predictors are full-dimensional. The normal displacement ZZ ranges over a (D−m)(D-m)-dimensional ball of radius RR, and the distribution of XX does not concentrate on M\mathcal{M} as nn grows. If XX has a locally bounded positive ambient density, a Euclidean ball of sufficiently small radius bb around a typical interior data point contains of order nbDnb^{D} observations, and the covariance of the predictors in such a ball does not reveal the tangent space of M\mathcal{M}. This contrasts with models in which the data concentrate near a low-dimensional manifold, and it parallels the single-index model, in which the predictors typically have large variance orthogonally to the index.

The regression function is intrinsically mm-dimensional. It is constant on each normal fiber and is determined by its values on M\mathcal{M}. The responses reveal tangential directions wherever DfDf has full rank.

The model interpolates between index models and general compositions. If M\mathcal{M} is an affine subspace, ΠM\Pi_{\mathcal{M}} is an affine orthogonal projection and the model is a multi-index model: FF depends only on the projection onto that affine subspace. Its index space is the direction space of M\mathcal{M}. For a curved M\mathcal{M}, the inner map ΠM\Pi_{\mathcal{M}} is nonlinear as well, but it has a precise geometric form. § 2 shows that this form is what makes the problem learnable: the gradient of FF at Q+ZQ+Z lies in the tangent space TQMT_Q\mathcal{M}, so the fixed index space is replaced by a field of tangent spaces that moves with the base point.

Main result

For Q∈MQ\in\mathcal{M}, let PQP_Q denote the orthogonal projector onto TQMT_Q\mathcal{M}. At an independent query XX, we assess estimates P^(x)\widehat{P}(x) of PΠMxP_{\Pi_{\mathcal{M}}x} and F^\widehat{F} of the regression function by

Etan(P^):=E∥P^(X)−PΠMX∥,Epred(F^):=E∥F^(X)−F(X)∥2E∥F(X)−EF(X)∥2.(3)\mathcal{E}_{\mathrm{tan}}(\widehat{P}) := \mathbb{E}\left\|\widehat{P}(X)-P_{\Pi_{\mathcal{M}}X}\right\|,\qquad\mathcal{E}_{\mathrm{pred}}(\widehat{F}) := \frac{\mathbb{E}\left\|\widehat{F}(X)-F(X)\right\|^2}{\mathbb{E}\left\|F(X)-\mathbb{E}F(X)\right\|^2}. \tag*{(3)}

The expectation averages over the training sample, the random split used for initialization, and an independent query. The first error is the mean sine of the largest principal angle between the estimated and true tangent spaces; the second is the mean squared prediction error relative to the variance of the signal.

Theorem (informal). Under (A1)(A1)–(A5)(A5), let p≥mp \ge m, D>mD > m, with a tube-to-reach ratio 0<R/reach⁡M<2/30 < R/\operatorname{reach}_{\mathcal{M}} < 2/3. The differential DfDf may be rank deficient at finitely many points. With the scales and construction of Theorem 3.5, and positive signal variance,

References

  1. [1]Eddie Aamari and Clément Levrard. Nonasymptotic rates for manifold, tangent space and curvature estimation. The Annals of Statistics, 47(1):177–204, 2019. doi: 10.1214/18-AOS1685.DOI
  2. [2]Rie Kubota Ando and Tong Zhang. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research, 6:1817–1853, 2005.DOI
  3. [3]Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Convex multi-task feature learning. Machine Learning, 73(3):243–272, 2008. doi: 10.1007/s10994-007-5040-8.
  4. [4]Gennady I. Arkhipov, Vladimir N. Chubarikov, and Anatoly A. Karatsuba. Trigonometric Sums in Number Theory and Analysis, volume 39 of De Gruyter Expositions in Mathematics. Walter de Gruyter, Berlin, 2004. Translated from the 1987 Russian original.
  5. [5]Anil Aswani, Peter Bickel, and Claire Tomlin. Regression on manifolds: Estimation of the exterior derivative. The Annals of Statistics, 39(1):48–81, 2011.
  6. [6]Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1–53, 2017.
  7. [7]Andrew R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993. doi: 10.1109/18.256500.DOI
  8. [8]Benedikt Bauer and Michael Kohler. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. The Annals of Statistics, 47(4):2261–2285, 2019.DOI
  9. [9]Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149–198, 2000. doi: 10.1613/jair.731.DOI
  10. [10]Gérard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1–51, 2021.arxiv.org/abs/2003.10409
  11. [11]Peter J. Bickel and Bo Li. Local polynomial regression on unknown manifolds. In Complex Datasets and Inverse Problems: Tomography, Networks and Beyond, volume 54 of IMS Lecture Notes–Monograph Series, pages 177–186. Institute of Mathematical Statistics, 2007.DOI
  12. [12]Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. In Advances in Neural Information Processing Systems 35, pages 9768–9783, 2022.arxiv.org/abs/2210.15651
  13. [13]Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning Gaussian multi-index models with gradient flow, 2023. arXiv:2310.19793.arxiv.org/abs/2310.19793
  14. [14]Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore, and Vladimir Temlyakov. Universal algorithms for learning theory. Part I: Piecewise constant functions. Journal of Machine Learning Research, 6:1297–1321, 2005.
  15. [15]Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore, and Vladimir Temlyakov. Universal algorithms for learning theory. Part II: Piecewise polynomial functions. Constructive Approximation, 26(2):127–152, 2007.DOI
  16. [16]Peter Binev, Andrea Bonito, Ronald DeVore, and Guergana Petrova. Optimal learning, 2023. arXiv:2203.15994.arxiv.org/abs/2203.15994
  17. [17]Olivier Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathématique, 334(6):495–500, 2002. doi: 10.1016/S1631-073X(02)02292-6.DOI
  18. [18]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. URL https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf.
  19. [19]Luca Brandolini, Giacomo Gigante, Allan Greenleaf, Alexander Iosevich, Andreas Seeger, and Giancarlo Travaglini. Average decay estimates for Fourier transforms of measures supported on curves. The Journal of Geometric Analysis, 17(1):15–40, 2007. doi: 10.1007/BF02922080.DOI
  20. [20]Leo Breiman and Jerome H. Friedman. Estimating optimal transformations for multiple regression and correlation. Journal of the American Statistical Association, 80(391):580–598, 1985. doi: 10.1080/01621459.1985.10478157.DOI
  21. [21]Robert A. Bridges, Anthony D. Gruber, Christopher Felder, Miki Verma, and Chelsey Hoff. Active manifolds: A non-linear analogue to active subspaces. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 764–772. PMLR, 2019.arxiv.org/abs/1904.13386
  22. [22]Raymond J. Carroll, Jianqing Fan, Irène Gijbels, and Matt P. Wand. Generalized partially linear single-index models. Journal of the American Statistical Association, 92(438):477–489, 1997. doi: 10.1080/01621459.1997.10474001.DOI
  23. [23]Rich Caruana. Multitask learning. Machine Learning, 28(1):41–75, 1997. doi: 10.1023/A:1007379606734.DOI
  24. [25]Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Proceedings of the Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research. PMLR, 2020.arxiv.org/abs/2004.13748
  25. [26]Ming-Yen Cheng and Hau-Tieng Wu. Local linear regression on manifolds and its geometric interpretation. Journal of the American Statistical Association, 108(504):1421–1434, 2013.arxiv.org/abs/1201.0327
  26. [27]Ronald R. Coifman, Ioannis G. Kevrekidis, Stéphane Lafon, Mauro Maggioni, and Boaz Nadler. Diffusion maps, reduction coordinates, and low dimensional representation of stochastic systems. Multiscale Modeling & Simulation, 7(2):842–864, 2008. doi: 10.1137/070696325.DOI
  27. [28]R. Dennis Cook. SAVE: A method for dimension reduction and graphics in regression. Communications in Statistics – Theory and Methods, 29(9–10):2109–2121, 2000. doi: 10.1080/03610920008832598.DOI
  28. [29]Raphaël Coudret, Benoit Liquet, and Jérôme Saracco. Comparison of sliced inverse regression approaches for underdetermined cases. Journal de la Société Française de Statistique, 155(2):72–96, 2014.
  29. [30]Miles Crosskey and Mauro Maggioni. ATLAS: A geometric approach to learning high-dimensional stochastic systems near manifolds. Multiscale Modeling & Simulation, 15(1):110–156, 2017.arxiv.org/abs/1404.0667
  30. [31]Arnak S. Dalalyan, Anatoli Juditsky, and Vladimir Spokoiny. A new algorithm for estimating the effective dimension-reduction subspace. Journal of Machine Learning Research, 9(53):1647–1678, 2008.
  31. [32]Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna. Computational-statistical gaps in Gaussian single-index models (extended abstract). In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, page 1262. PMLR, 2024.DOI
  32. [33]Chandler Davis and William M. Kahan. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1–46, 1970. doi: 10.1137/0707001.DOI
  33. [34]Michel Delecroix and Marian Hristache. M-estimateurs semi-paramétriques dans les modèles à direction révélatrice unique. Bulletin of the Belgian Mathematical Society Simon Stevin, 6(2):161–186, 1999.DOI
  34. [35]Michel Delecroix, Wolfgang Härdle, and Marian Hristache. Efficient estimation in conditional single-index regression. Journal of Multivariate Analysis, 86(2):213–226, 2003.DOI
  35. [36]Michel Delecroix, Marian Hristache, and Valentin Patilea. On semiparametric M-estimation in single-index regression. Journal of Statistical Planning and Inference, 136:730–769, 2006. doi: 10.1016/j.jspi.2004.09.006.
  36. [37]Naihua Duan and Ker-Chau Li. Slicing regression: A link-free regression method. The Annals of Statistics, 19(2):505–530, 1991.DOI
  37. [38]Weinan E and Eric Vanden-Eijnden. Towards a theory of transition paths. Journal of Statistical Physics, 123(3):503–523, 2006. doi: 10.1007/s10955-005-9003-9.DOI
  38. [39]Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418–491, 1959. doi: 10.1090/S0002-9947-1959-0110078-1.DOI
  39. [40]Kenji Fukumizu, Francis R. Bach, and Michael I. Jordan. Kernel dimension reduction in regression. The Annals of Statistics, 37(4):1871–1905, 2009.DOI
  40. [41]Stéphane Gaïffas and Guillaume Lecué. Optimal rates and adaptation in the single-index model using aggregation. Electronic Journal of Statistics, 1, 2007. doi: 10.1214/07-EJS077.DOI
  41. [42]Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. Minimax manifold estimation. Journal of Machine Learning Research, 13:1263–1291, 2012.
  42. [43]Evarist Giné and Armelle Guillou. Rates of strong uniform consistency for multivariate kernel density estimators. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 38(6):907–921, 2002. doi: 10.1016/S0246-0203(02)01128-7. URL https://www.numdam.org/item/AIHPB_2002__38_6_907_0/.
  43. [44]Paul W. Goldberg and Mark R. Jerrum. Bounding the Vapnik–Chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2–3):131–148, 1995. doi: 10.1007/BF0093408. URL https://www.cs.ox.ac.uk/people/paul.goldberg/papers/GJ-ML95.pdf.
  44. [45]László Györfi, Michael Kohler, Adam Krzyżak, and Harro Walk. A Distribution-Free Theory of Nonparametric Regression. Springer, New York, 2002. doi: 10.1007/b97848.DOI
  45. [46]Wolfgang Härdle and Thomas M. Stoker. Investigating smooth multiple regression by the method of average derivatives. Journal of the American Statistical Association, 84(408):986–995, 1989.DOI
  46. [47]Wolfgang Härdle, Peter Hall, and Hidehiko Ichimura. Optimal smoothing in single-index models. The Annals of Statistics, 21(1):157–178, 1993.DOI
  47. [48]Trevor Hastie and Robert Tibshirani. Generalized additive models. In Wiley StatsRef: Statistics Reference Online. John Wiley & Sons, 2014. doi: 10.1002/9781118445112.stat03141.DOI
  48. [49]Marc Hoffmann and Oleg Lepski. Random rates in anisotropic regression. The Annals of Statistics, 30(2):325–396, 2002.
  49. [50]Joel L. Horowitz. Semiparametric Methods in Econometrics. Springer, New York, 1998. doi: 10.1007/978-1-4612-0621-7.DOI
  50. [51]Joel L. Horowitz and Enno Mammen. Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions. The Annals of Statistics, 35(6):2589–2619, 2007.
  51. [52]Marian Hristache, Anatoli Juditsky, and Vladimir Spokoiny. Direct estimation of the index coefficient in a single-index model. The Annals of Statistics, 29(3):595–623, 2001.DOI
  52. [53]Hidehiko Ichimura. Semiparametric least squares (SLS) and weighted SLS estimation of single-index models. Journal of Econometrics, 58(1):71–120, 1993. doi: 10.1016/0304-4076(93)90114-K.DOI
  53. [54]Anatoli B. Juditsky, Oleg V. Lepski, and Alexandre B. Tsybakov. Nonparametric estimation of composite functions. The Annals of Statistics, 37(3):1360–1404, 2009.
  54. [55]Michael Kohler and Adam Krzyżak. Nonparametric regression based on hierarchical interaction models. IEEE Transactions on Information Theory, 63(3):1620–1630, 2017.DOI
  55. [56]Alex Kokot, Anand Hemmady, Vydhourie Thiyageswaran, and Marina Meila. Local EGOP for continuous index learning, 2026. URL https://arxiv.org/abs/2601.07061v4. arXiv:2601.07061v4.
  56. [57]Andrey N. Kolmogorov and Vladimir M. Tikhomirov. ε-entropy and ε-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3–86, 1959. English translation: American Mathematical Society Translations, Series 2, 17:277–364, 1961.
  57. [58]Samory Kpotufe. k-NN regression adapts to local intrinsic dimension. In Advances in Neural Information Processing Systems 24, pages 729–737, 2011.arxiv.org/abs/1110.4300
  58. [59]Samory Kpotufe and Vikas Garg. Adaptivity to local smoothness and dimension in kernel regression. In Advances in Neural Information Processing Systems 26, 2013.
  59. [60]Ming-Jun Lai and Zhaiming Shen. The Kolmogorov superposition theorem can break the curse of dimensionality when approximating high-dimensional functions, 2021. arXiv:2112.09963.arxiv.org/abs/2112.09963
  60. [61]Alessandro Lanteri, Željko Kereta, Timo Klock, Mauro Maggioni, Valeriya Naumova, and Stefano Vignona. Thinking geometrically in regression with structured models: Linear and nonlinear single-index models. Unpublished manuscript, 2018.
  61. [62]Alessandro Lanteri, Mauro Maggioni, and Stefano Vignona. Conditional regression for single-index models. Bernoulli, 28(4):3051–3078, 2022. doi: 10.3150/22-BEJ1482.
  62. [63]Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. In Advances in Neural Information Processing Systems 37, pages 58716–58756, 2024.arxiv.org/abs/2406.01581
  63. [64]John M. Lee. Introduction to Riemannian Manifolds, volume 176 of Graduate Texts in Mathematics. Springer, Cham, 2 edition, 2018. doi: 10.1007/978-3-319-91755-9.DOI
  64. [65]Kuang-Yao Lee, Bing Li, and Francesca Chiaromonte. A general theory for nonlinear sufficient dimension reduction: Formulation and estimation. The Annals of Statistics, 41(1):221–249, 2013. doi: 10.1214/12-AOS1071.DOI
  65. [66]Bing Li and Shaoli Wang. On directional regression for dimension reduction. Journal of the American Statistical Association, 102(479):997–1008, 2007.DOI
  66. [67]Bing Li, Hongyuan Zha, and Francesca Chiaromonte. Contour regression: A general approach to dimension reduction. The Annals of Statistics, 33(4):1580–1616, 2005.
  67. [68]Bing Li, Andreas Artemiou, and Lexin Li. Principal support vector machines for linear and nonlinear sufficient dimension reduction. The Annals of Statistics, 39(6):3182–3210, 2011. doi: 10.1214/11-AOS932.DOI
  68. [69]Ker-Chau Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 86(414):316–327, 1991.
  69. [70]Wenjing Liao, Mauro Maggioni, and Stefano Vigogna. Learning adaptive multiscale approximations to data and functions near low-dimensional sets. In 2016 IEEE Information Theory Workshop (ITW), pages 226–230, 2016. doi: 10.1109/ITW.2016.7606829.DOI
  70. [71]Wenjing Liao, Mauro Maggioni, and Stefano Vigogna. Multiscale regression on unknown manifolds. Mathematics in Engineering, 4(4):1–25, 2022. doi: 10.3934/mine.2022028.DOI
  71. [72]Anna V. Little, Yoon-Mo Jung, and Mauro Maggioni. Multiscale estimation of intrinsic dimensionality of data sets. In AAAI Fall Symposium: Manifold Learning and Its Applications, 2009a.
  72. [74]Anna V. Little, Mauro Maggioni, and Lorenzo Rosasco. Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature. Applied and Computational Harmonic Analysis, 43(3):504–567, 2017. doi: 10.1016/j.acha.2015.09.009.DOI
  73. [75]Hao Liu, Jiahui Cheng, and Wenjing Liao. Deep neural networks are adaptive to function regularity and data distribution in approximation and estimation, 2024a. arXiv:2406.05320.arxiv.org/abs/2406.05320
  74. [76]Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljačić, Thomas Y. Hou, and Max Tegmark. KAN: Kolmogorov–Arnold networks, 2024b. arXiv:2404.19756.arxiv.org/abs/2404.19756
  75. [78]Nicholas F. Marshall. Approximating mixed Hölder functions using random samples. The Annals of Applied Probability, 29(5):2988–3005, 2019b. doi: 10.1214/19-AAP1471.DOI
  76. [79]Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1–32, 2016.arxiv.org/abs/1505.06279
  77. [80]Alireza Mousavi-Hosseini, Denny Wu, and Murat A. Erdogdu. Learning multi-index models with neural networks via mean-field Langevin dynamics, 2024. arXiv:2408.07254.
  78. [81]Sayan Mukherjee, Qiang Wu, and Ding-Xuan Zhou. Learning gradients on manifolds. Bernoulli, 16(1):181–207, 2010.DOI
  79. [82]Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39 (1–3):419–441, 2008. doi: 10.1007/s00454-008-9053-2.DOI
  80. [83]Nikita Puchkin and Vladimir Spokoiny. Structure-adaptive manifold estimation. Journal of Machine Learning Research, 23(40):1–62, 2022.
  81. [84]Adityanarayanan Radhakrishnan, Daniel Beaglehole, Parthe Pandit, and Mikhail Belkin. Mechanism for feature learning in neural networks and backpropagation-free machine learning models. Science, 383(6690):1461–1467, 2024. doi: 10.1126/science.adi5639.
  82. [85]Yunwei Ren and Jason D. Lee. Learning orthogonal multi-index models: A fine-grained information exponent analysis, 2024. arXiv:2410.09678.arxiv.org/abs/2410.09678
  83. [86]Mary A. Rohrdanz, Wenwei Zheng, Mauro Maggioni, and Cecilia Clementi. Determination of reaction coordinates via locally scaled diffusion map. The Journal of Chemical Physics, 134(12):124116, 2011. doi: 10.1063/1.3569857.DOI
  84. [87]Paul Rosa and Judith Rousseau. Nonparametric regression on random geometric graphs sampled from submanifolds. Journal of Machine Learning Research, 26(164):1–65, 2025.arxiv.org/abs/2405.20909
  85. [88]Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4):1875–1897, 2020. doi: 10.1214/19-AOS1875.DOI
  86. [89]Ohad Shamir. Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”. The Annals of Statistics, 48(4):1911–1915, 2020. doi: 10.1214/19-AOS1915.DOI
  87. [90]Guohao Shen, Yuling Jiao, Yuanyuan Lin, Joel L. Horowitz, and Jian Huang. Deep quantile regression: Mitigating the curse of dimensionality through composition, 2021. arXiv:2107.04907.arxiv.org/abs/2107.04907
  88. [91]Zhaiming Shen, Alex Havrilla, Rongjie Lai, Alexander Cloninger, and Wenjing Liao. Transformers for learning on noisy and task-level manifolds: Approximation and generalization insights, 2025. URL https://arxiv.org/abs/2505.03205. arXiv:2505.03205.
  89. [92]G. W. Stewart and Ji-guang Sun. Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press, Boston, 1990.
  90. [93]Thomas M. Stoker. Consistent estimation of scaled coefficients. Econometrica, 54(6):1461–1481, 1986.DOI
  91. [94]Charles J. Stone. Optimal global rates of convergence for nonparametric regression. The Annals of Statistics, 10(4):1040–1053, 1982.DOI
  92. [95]Charles J. Stone. Additive regression and other nonparametric models. The Annals of Statistics, 13(2):689–705, 1985. doi: 10.1214/aos/1176349548.DOI
  93. [96]Jan-Olov Strömberg. Computation with wavelets in higher dimensions. In Proceedings of the International Congress of Mathematicians, volume 3, pages 523–532, 1998.DOI
  94. [97]Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. In Advances in Neural Information Processing Systems 34, 2021.
  95. [98]Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009. doi: 10.1007/b13794.DOI
  96. [99]R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2 edition, 2026. URL https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-2.pdf.
  97. [100]Zihao Wang, Eshaan Nichani, and Jason D. Lee. Learning hierarchical polynomials with three-layer neural networks. In The Twelfth International Conference on Learning Representations, 2024.arxiv.org/abs/2311.13774
  98. [101]Qiang Wu, Sayan Mukherjee, and Feng Liang. Localized sliced inverse regression. In Advances in Neural Information Processing Systems 21, 2008.
  99. [102]Yantao Wu and Mauro Maggioni. Conditional regression for the nonlinear single-variable model. Journal of Machine Learning Research, 27(155):1–75, 2026.
  100. [103]Yingcun Xia. A constructive approach to the estimation of dimension reduction directions. The Annals of Statistics, 35(6):2654–2690, 2007.arxiv.org/abs/math/0701761
  101. [104]Yingcun Xia, Howell Tong, W. K. Li, and Li-Xing Zhu. An adaptive estimation of dimension reduction space. Journal of the Royal Statistical Society: Series B, 64(3):363–410, 2002.
  102. [105]Yuhong Yang and Andrew Barron. Information-theoretic determination of minimax rates of convergence. The Annals of Statistics, 27(5):1564–1599, 1999.DOI

Paper details

vlnc:W_b4aenmhs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, Claude, Grok (multiple versions)

View statement
Looking for related papers…
Contents