Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs

• URL: http://arxiv.org/abs/2111.07394v1
• Date: Sun, 14 Nov 2021 17:32:51 GMT
• Title: Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs
• Abstract summary: We study the statistical properties of Principal Components Regression with Laplacian Eigenmaps (PCR-LE) PCR-LE works by projecting a vector of observed responses onto a subspace spanned by certain eigenvectors of a neighborhood graph Laplacian. We show that PCR-LE achieves minimax rates of convergence for random design regression over Sobolev spaces.
• Score: 25.597646488273558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the statistical properties of Principal Components Regression with Laplacian Eigenmaps (PCR-LE), a method for nonparametric regression based on Laplacian Eigenmaps (LE). PCR-LE works by projecting a vector of observed responses ${\bf Y} = (Y_1,\ldots,Y_n)$ onto a subspace spanned by certain eigenvectors of a neighborhood graph Laplacian. We show that PCR-LE achieves minimax rates of convergence for random design regression over Sobolev spaces. Under sufficient smoothness conditions on the design density $p$, PCR-LE achieves the optimal rates for both estimation (where the optimal rate in squared $L^2$ norm is known to be $n^{-2s/(2s + d)}$) and goodness-of-fit testing ($n^{-4s/(4s + d)}$). We also show that PCR-LE is \emph{manifold adaptive}: that is, we consider the situation where the design is supported on a manifold of small intrinsic dimension $m$, and give upper bounds establishing that PCR-LE achieves the faster minimax estimation ($n^{-2s/(2s + m)}$) and testing ($n^{-4s/(4s + m)}$) rates of convergence. Interestingly, these rates are almost always much faster than the known rates of convergence of graph Laplacian eigenvectors to their population-level limits; in other words, for this problem regression with estimated features appears to be much easier, statistically speaking, than estimating the features itself. We support these theoretical results with empirical evidence.

Related papers

• Minimax Optimal Estimator and Improved Error Rate for the MLE in Logistic Regression with Gaussian Design [28.74829605004241]
  We provide the first minimax optimal estimator, and improve on the best known finite-sample error rate for the maximum likelihood estimator (MLE)<n>We construct an efficient debiased norm estimator that achieves the error rate $O(sqrtR3/n)$ as well as the intrinsic finite-sample error rate $tildeO(sqrtR3/n+sqrtR3/n)$ for the MLE.
  arXiv  Detail & Related papers  (2026-08-18T01:35:11Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design [28.74829605004241]
  We characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss)<n>We show that GD linearly converges to a small neighborhood of $*$ achieving an $ell$ error of order $O(sqrt|*|5d/n)$.<n>We also establish a faster local linear convergence to the same statistical error under a large $(|*|_2)$ stepsize.
  arXiv  Detail & Related papers  (2026-06-19T18:43:41Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• Anchor-MoE: A Mean-Anchored Mixture of Experts For Probabilistic Regression [0.0]
  We present an Anchored Mixture of Experts (Anchor-MoE) model that handles both probabilistic and point regression.<n>We show that Anchor-MoE attains the minimax-optimal $L2$ risk rate.<n>It consistently matches or surpasses the strong NG baseline in RMSE and NLL.
  arXiv  Detail & Related papers  (2025-08-22T21:12:41Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  We consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of 2 sub-gaussian distributions in $mathbbRp$. We use semidefinite programming relaxations of an integer quadratic program that is formulated as finding the maximum cut on a graph.
  arXiv  Detail & Related papers  (2024-01-16T03:14:24Z)
• Relation between PLS and OLS regression in terms of the eigenvalue distribution of the regressor covariance matrix [0.0]
  Partial least squares (PLS) is a dimensionality reduction technique introduced in the field of chemometrics. PLS regression can be formulated as a least squares problem restricted to a Krylov subspace. We analyze the distance between $hatboldsymbolbeta;_mathrmPLSscriptscriptstyle (L)$.
  arXiv  Detail & Related papers  (2023-12-03T13:00:03Z)
• Optimal minimax rate of learning interaction kernels [7.329333373512536]
  We introduce a tamed least squares estimator (tLSE) that attains the optimal convergence rate for a broad class of exchangeable distributions. Our findings reveal that provided the inverse problem in the large sample limit satisfies a coercivity condition, the left tail probability does not alter the bias-variance tradeoff.
  arXiv  Detail & Related papers  (2023-11-28T15:01:58Z)
• Robust Nonparametric Regression under Poisoning Attack [13.470899588917716]
  An adversarial attacker can modify the values of up to $q$ samples from a training dataset of size $N$. Our initial solution is an M-estimator based on Huber loss minimization. The final estimate is nearly minimax optimal for arbitrary $q$, up to a $ln N$ factor.
  arXiv  Detail & Related papers  (2023-05-26T09:33:17Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  We propose a new method for estimating the minimizer $boldsymbolx*$ and the minimum value $f*$ of a smooth and strongly convex regression function $f$. We derive non-asymptotic upper bounds for the quadratic risk and optimization error of $boldsymbolz_n$, and for the risk of estimating $f*$.
  arXiv  Detail & Related papers  (2022-11-29T18:38:40Z)
• Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
  We study synchronous Q-learning with Polyak-Ruppert averaging (a.k.a., averaged Q-leaning) in a $gamma$-discounted MDP. We establish normality for the iteration averaged $barboldsymbolQ_T$. In short, our theoretical analysis shows averaged Q-Leaning is statistically efficient.
  arXiv  Detail & Related papers  (2021-12-29T14:47:56Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  We study the statistical properties of Laplacian smoothing, a graph-based approach to nonparametric regression. We prove that Laplacian smoothing is manifold-adaptive.
  arXiv  Detail & Related papers  (2021-06-03T01:20:41Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.