Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks

• URL: http://arxiv.org/abs/2307.15285v2
• Date: Tue, 26 Sep 2023 20:09:43 GMT
• Title: Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks
• Authors: Jonathan W. Siegel
• Abstract summary: We study the following two related problems. The first is to determine what error an arbitrary zonoid in $mathbbRd+1$ can be approximated in the Hausdorff distance by a sum of $n$ line segments. The second is to determine optimal approximation rates in the uniform norm for shallow ReLU$k$ neural networks on their variation spaces.
• Score: 2.7195102129095003
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the following two related problems. The first is to determine to what error an arbitrary zonoid in $\mathbb{R}^{d+1}$ can be approximated in the Hausdorff distance by a sum of $n$ line segments. The second is to determine optimal approximation rates in the uniform norm for shallow ReLU$^k$ neural networks on their variation spaces. The first of these problems has been solved for $d\neq 2,3$, but when $d=2,3$ a logarithmic gap between the best upper and lower bounds remains. We close this gap, which completes the solution in all dimensions. For the second problem, our techniques significantly improve upon existing approximation rates when $k\geq 1$, and enable uniform approximation of both the target function and its derivatives.

Related papers

• Approximation Rates for Shallow ReLU$^k$ Neural Networks on Sobolev Spaces via the Radon Transform [4.096453902709292]
  We consider the problem of how efficiently shallow neural networks with the ReLU$k$ activation function can approximate functions from Sobolev spaces. We provide a simple proof of nearly optimal approximation rates in a variety of cases, including when $qleq p$, $pgeq 2$, and $s leq k + (d+1)/2$.
  arXiv  Detail & Related papers  (2024-08-20T16:43:45Z)
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits [6.844618776091756]
  An approximate unitary $k$-design is an ensemble of unitaries and measure over which the average is close to a Haar random ensemble up to the first $k$ moments. We construct multiplicative-error approximate unitary $k$-design ensembles for which communication between subsystems is $O(1)$ in the system size.
  arXiv  Detail & Related papers  (2024-07-10T17:43:23Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Error Estimates for the Variational Training of Neural Networks with Boundary Penalty [0.0]
  We establish estimates on the error made by the Ritz method for quadratic energies on the space $H1(Omega)$. Special attention is paid to the case of Dirichlet boundary values which are treated with the boundary penalty method.
  arXiv  Detail & Related papers  (2021-03-01T13:55:59Z)
• Optimal Approximation Rates and Metric Entropy of ReLU$^k$ and Cosine Networks [0.0]
  We show that the largest Banach space of functions which can be efficiently approximated by the corresponding shallow neural networks is the space whose norm is given by the gauge of the closed convex hull of the set $pmsigma(omegacdot x + b)$. We establish the precises of the $L2$-metric entropy of the unit ball of these guage spaces and, as a consequence, the optimal approximation rates for shallow ReLU$k$ networks.
  arXiv  Detail & Related papers  (2021-01-29T02:29:48Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• 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)
• Deep Network Approximation for Smooth Functions [9.305095040004156]
  We show that deep ReLU networks of width $mathcalO(Nln N)$ and depth $mathcalO(L L)$ can approximate $fin Cs([0,1]d)$ with a nearly optimal approximation error. Our estimate is non-asymptotic in the sense that it is valid for arbitrary width and depth specified by $NinmathbbN+$ and $LinmathbbN+$, respectively.
  arXiv  Detail & Related papers  (2020-01-09T15:06:10Z)

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.