Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.
more »
« less
Tractability of approximation by general shallow networks
In this paper, we present a sharper version of the results in the paper Dimension independent bounds for general shallow networks; Neural Networks, \textbf{123} (2020), 142-152. Let $$\mathbb{X}$$ and $$\mathbb{Y}$$ be compact metric spaces. We consider approximation of functions of the form $$ x\mapsto\int_{\mathbb{Y}} G( x, y)d\tau( y)$$, $$ x\in\mathbb{X}$$, by $$G$$-networks of the form $$ x\mapsto \sum_{k=1}^n a_kG( x, y_k)$$, $$ y_1,\cdots, y_n\in\mathbb{Y}$$, $$a_1,\cdots, a_n\in\mathbb{R}$$. Defining the dimensions of $$\mathbb{X}$$ and $$\mathbb{Y}$$ in terms of covering numbers, we obtain dimension independent bounds on the degree of approximation in terms of $$n$$, where also the constants involved are all dependent at most polynomially on the dimensions. Applications include approximation by power rectified linear unit networks, zonal function networks, certain radial basis function networks as well as the important problem of function extension to higher dimensional spaces.
more »
« less
- Award ID(s):
- 2012355
- PAR ID:
- 10547036
- Publisher / Repository:
- World Scientific
- Date Published:
- Journal Name:
- Analysis and Applications
- Volume:
- 22
- Issue:
- 03
- ISSN:
- 0219-5305
- Page Range / eLocation ID:
- 535 to 568
- Subject(s) / Keyword(s):
- Tractability neural networks approximation
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We obtain bounds on fractional parts of binary forms of the shape $$\Psi(x,y)=\alpha_k x^k+\alpha_l x^ly^{k-l}+\alpha_{l-1}x^{l-1}y^{k-l+1}+\cdots+\alpha_0 y^k$$ with $$\alpha_k,\alpha_l,\ldots,\alpha_0\in{\mathbb R}$$ and $$l\leq k-2.$$ By exploiting recent progress on Vinogradov’s mean value theorem and earlier work on exponential sums over smooth numbers, we derive estimates superior to those obtained hitherto for the best exponent σ, depending on k and $l,$ such that $$ \min_{\substack{0\leq x,y\leq X\\(x,y)\neq (0,0)}}\|\Psi(x,y)\|\leq X^{-\sigma+\epsilon}. $$more » « less
-
Abstract We obtain new quantitative estimates on Weyl Law remainders under dynamical assumptions on the geodesic flow. On a smooth compact Riemannian manifold ( M , g ) of dimension n , let $$\Pi _\lambda $$ Π λ denote the kernel of the spectral projector for the Laplacian, $$\mathbb {1}_{[0,\lambda ^2]}(-\Delta _g)$$ 1 [ 0 , λ 2 ] ( - Δ g ) . Assuming only that the set of near periodic geodesics over $${W}\subset M$$ W ⊂ M has small measure, we prove that as $$\lambda \rightarrow \infty $$ λ → ∞ $$\begin{aligned} \int _{{W}} \Pi _\lambda (x,x)dx=(2\pi )^{-n}{{\,\textrm{vol}\,}}_{_{{\mathbb {R}}^n}}\!(B){{\,\textrm{vol}\,}}_g({W})\,\lambda ^n+O\Big (\frac{\lambda ^{n-1}}{\log \lambda }\Big ), \end{aligned}$$ ∫ W Π λ ( x , x ) d x = ( 2 π ) - n vol R n ( B ) vol g ( W ) λ n + O ( λ n - 1 log λ ) , where B is the unit ball. One consequence of this result is that the improved remainder holds on all product manifolds, in particular giving improved estimates for the eigenvalue counting function in the product setup. Our results also include logarithmic gains on asymptotics for the off-diagonal spectral projector $$\Pi _\lambda (x,y)$$ Π λ ( x , y ) under the assumption that the set of geodesics that pass near both x and y has small measure, and quantitative improvements for Kuznecov sums under non-looping type assumptions. The key technique used in our study of the spectral projector is that of geodesic beams.more » « less
-
Let $$V_1, V_2, V_3, \dots $$ be a sequence of $$\mathbb {Q}$$-vector spaces where $$V_n$$ carries an action of $$\mathfrak{S}_n$$. Representation stability and multiplicity stability are two related notions of when the sequence $$V_n$$ has a limit. An important source of stability phenomena arises when $$V_n$$ is the $$d^{th}$$ homology group (for fixed $$d$$) of the configuration space of $$n$$ distinct points in some fixed topological space $$X$$. We replace these configuration spaces with moduli spaces of tuples $$(W_1, \dots, W_n)$$ of subspaces of a fixed complex vector space $$\mathbb {C}^N$$ such that $$W_1 + \cdots + W_n = \mathbb {C}^N$$. These include the varieties of spanning line configurations which are tied to the Delta Conjecture of symmetric function theory.more » « less
-
Abstract Let $$V_*\otimes V\rightarrow {\mathbb {C}}$$ V ∗ ⊗ V → C be a non-degenerate pairing of countable-dimensional complex vector spaces V and $$V_*$$ V ∗ . The Mackey Lie algebra $${\mathfrak {g}}=\mathfrak {gl}^M(V,V_*)$$ g = gl M ( V , V ∗ ) corresponding to this pairing consists of all endomorphisms $$\varphi $$ φ of V for which the space $$V_*$$ V ∗ is stable under the dual endomorphism $$\varphi ^*: V^*\rightarrow V^*$$ φ ∗ : V ∗ → V ∗ . We study the tensor Grothendieck category $${\mathbb {T}}$$ T generated by the $${\mathfrak {g}}$$ g -modules V , $$V_*$$ V ∗ and their algebraic duals $$V^*$$ V ∗ and $$V^*_*$$ V ∗ ∗ . The category $${{\mathbb {T}}}$$ T is an analogue of categories considered in prior literature, the main difference being that the trivial module $${\mathbb {C}}$$ C is no longer injective in $${\mathbb {T}}$$ T . We describe the injective hull I of $${\mathbb {C}}$$ C in $${\mathbb {T}}$$ T , and show that the category $${\mathbb {T}}$$ T is Koszul. In addition, we prove that I is endowed with a natural structure of commutative algebra. We then define another category $$_I{\mathbb {T}}$$ I T of objects in $${\mathbb {T}}$$ T which are free as I -modules. Our main result is that the category $${}_I{\mathbb {T}}$$ I T is also Koszul, and moreover that $${}_I{\mathbb {T}}$$ I T is universal among abelian $${\mathbb {C}}$$ C -linear tensor categories generated by two objects X , Y with fixed subobjects $$X'\hookrightarrow X$$ X ′ ↪ X , $$Y'\hookrightarrow Y$$ Y ′ ↪ Y and a pairing $$X\otimes Y\rightarrow {\mathbf{1 }}$$ X ⊗ Y → 1 where 1 is the monoidal unit. We conclude the paper by discussing the orthogonal and symplectic analogues of the categories $${\mathbb {T}}$$ T and $${}_I{\mathbb {T}}$$ I T .more » « less
An official website of the United States government

