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

• URL: http://arxiv.org/abs/2106.01529v1
• Date: Thu, 3 Jun 2021 01:20:41 GMT
• Title: Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs
• Authors: Alden Green, Sivaraman Balakrishnan, Ryan J. Tibshirani
• Abstract summary: We study the statistical properties of Laplacian smoothing, a graph-based approach to nonparametric regression. We prove that Laplacian smoothing is manifold-adaptive.
• Score: 25.597646488273558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the statistical properties of Laplacian smoothing, a graph-based approach to nonparametric regression. Under standard regularity conditions, we establish upper bounds on the error of the Laplacian smoothing estimator $\widehat{f}$, and a goodness-of-fit test also based on $\widehat{f}$. These upper bounds match the minimax optimal estimation and testing rates of convergence over the first-order Sobolev class $H^1(\mathcal{X})$, for $\mathcal{X}\subseteq \mathbb{R}^d$ and $1 \leq d < 4$; in the estimation problem, for $d = 4$, they are optimal modulo a $\log n$ factor. Additionally, we prove that Laplacian smoothing is manifold-adaptive: if $\mathcal{X} \subseteq \mathbb{R}^d$ is an $m$-dimensional manifold with $m < d$, then the error rate of Laplacian smoothing (in either estimation or testing) depends only on $m$, in the same way it would if $\mathcal{X}$ were a full-dimensional set in $\mathbb{R}^d$.

Related papers

• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties [21.141544548229774]
  We study the form $min_x max_y f(x, y) where $mathcalN$ are Hadamard. We show global interest accelerated by reducing gradient convergence constants.
  arXiv  Detail & Related papers  (2023-05-25T15:43:07Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  We present a novel map-based algorithm ($mathsfnorMtext-mathsfSGD$) for $symbol$k$ convergence problems.
  arXiv  Detail & Related papers  (2023-05-10T01:12:11Z)
• Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
  This paper considers learning of the graphical structure of a $p$-dimensional random vector $X in Rp$ using both parametric and non-parametric methods. Under mild conditions, we show that our graph-structure estimator can obtain the correct structure.
  arXiv  Detail & Related papers  (2022-05-06T19:24:44Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
  arXiv  Detail & Related papers  (2021-10-28T14:19:30Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
  We consider the problem of estimating a $d$ dimensional sub-manifold of $mathbbRD$ from a finite set of noisy samples. We show that the estimation yields rates of convergence of $n-frack2k + d$ for the point estimation and $n-frack-12k + d$ for the estimation of tangent space.
  arXiv  Detail & Related papers  (2021-05-11T02:29:33Z)
• From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
  We show that $mathsfW_p(sigma)$ is controlled by a $pth order smooth dual Sobolev $mathsfd_p(sigma)$. We derive the limit distribution of $sqrtnmathsfd_p(sigma)(hatmu_n,mu)$ in all dimensions $d$, when $mu$ is sub-Gaussian.
  arXiv  Detail & Related papers  (2021-01-11T17:23:24Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.