On best approximation by multivariate ridge functions with applications to generalized translation networks

• URL: http://arxiv.org/abs/2412.08453v1
• Date: Wed, 11 Dec 2024 15:16:16 GMT
• Title: On best approximation by multivariate ridge functions with applications to generalized translation networks
• Authors: Paul Geuchen, Palina Salanevich, Olov Schavemaker, Felix Voigtlaender,
• Abstract summary: We show that the order of approximationally behaves as $n-r/(d-ell)$, where $r$ is the regularity of the Sobolev functions to be approximated. Our lower bound even holds when approxing $Linfty$-Sobolev functions of regularity $r$ with error measured in $L1$, while our upper bound applies to the approximation of $Lp$-Sobolev functions in $Lp$ for any $1 leq p leq infty$.
• Score: 0.0
• License:
• Abstract: We prove sharp upper and lower bounds for the approximation of Sobolev functions by sums of multivariate ridge functions, i.e., functions of the form $\mathbb{R}^d \ni x \mapsto \sum_{k=1}^n h_k(A_k x) \in \mathbb{R}$ with $h_k : \mathbb{R}^\ell \to \mathbb{R}$ and $A_k \in \mathbb{R}^{\ell \times d}$. We show that the order of approximation asymptotically behaves as $n^{-r/(d-\ell)}$, where $r$ is the regularity of the Sobolev functions to be approximated. Our lower bound even holds when approximating $L^\infty$-Sobolev functions of regularity $r$ with error measured in $L^1$, while our upper bound applies to the approximation of $L^p$-Sobolev functions in $L^p$ for any $1 \leq p \leq \infty$. These bounds generalize well-known results about the approximation properties of univariate ridge functions to the multivariate case. Moreover, we use these bounds to obtain sharp asymptotic bounds for the approximation of Sobolev functions using generalized translation networks and complex-valued neural networks.

Related papers

• Uniform $\mathcal{C}^k$ Approximation of $G$-Invariant and Antisymmetric Functions, Embedding Dimensions, and Polynomial Representations [0.0]
  We show that the embedding dimension required is independent of the regularity of the target function, the accuracy of the desired approximation, and $k$. We also provide upper and lower bounds on $K$ and show that $K$ is independent of the regularity of the target function, the desired approximation accuracy, and $k$.
  arXiv  Detail & Related papers  (2024-03-02T23:19:10Z)
• Noncompact uniform universal approximation [0.0]
  The universal approximation theorem is generalised to uniform convergence on the (noncompact) input space $mathbbRn$. All continuous functions that vanish at infinity can be uniformly approximated by neural networks.
  arXiv  Detail & Related papers  (2023-08-07T08:54:21Z)
• Tractability of approximation by general shallow networks [0.0]
  We consider approximation of functions of the form $ xmapstoint_mathbbY G( x, y)dtau( y)$, $ xinmathbbX$, by $G$-networks of the form $ xmapsto sum_k=1n a_kG( x, y_k)$. We obtain independent dimension bounds on the degree of approximation in terms of $n$, where also the constants involved are all dependent on the dimensions.
  arXiv  Detail & Related papers  (2023-08-07T00:14:46Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  We show that $d$-variables of degreeR$ can be represented on $[0,1]d$ as shallow neural networks of width $d+1+sum_r=2Rbinomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1d-1[binomr+d-1d-1d-1d-1
  arXiv  Detail & Related papers  (2022-08-17T08:14:52Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Deep neural network approximation of analytic functions [91.3755431537592]
  entropy bound for the spaces of neural networks with piecewise linear activation functions. We derive an oracle inequality for the expected error of the considered penalized deep neural network estimators.
  arXiv  Detail & Related papers  (2021-04-05T18:02:04Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev [31.57723436316983]
  One approach to sample from a high dimensional distribution matrix for some function is the Langevin Algorithm. Our work generalizes the results of [53] where $mathRn$ is defined on af$ rather than $bbRn$.
  arXiv  Detail & Related papers  (2020-10-11T15:02:12Z)
• A Canonical Transform for Strengthening the Local $L^p$-Type Universal Approximation Property [4.18804572788063]
  $Lp$-type universal approximation theorems guarantee that a given machine learning model class $mathscrFsubseteq C(mathbbRd,mathbbRD)$ is dense in $Lp_mu(mathbbRd,mathbbRD)$. This paper proposes a generic solution to this approximation theoretic problem by introducing a canonical transformation which "upgrades $mathscrF$'s approximation property"
  arXiv  Detail & Related papers  (2020-06-24T17:46:35Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

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.