Exponential Separations in Symmetric Neural Networks
In this work we demonstrate a novel separation between symmetric neural network architectures. Specifically, we consider the Relational Network~\parencite{santoro2017simple} architecture as a natural generalization of the DeepSets~\parencite{zaheer2017deep} architecture, and study their representational gap. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of size $N$ with elements in dimension $D$, which can be efficiently approximated by the former architecture, but provably requires width exponential in $N$ and $D$ for the latter.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Towards Antisymmetric Neural Ansatz Separation
We study separations between two fundamental models (or \emph{Ans\"atze}) of antisymmetric functions, that is, functions $f$ of the form $f(x_{\sigma(1)}, \ldots, x_{\sigma(N)}) = \text{sign}(\sigma)f(x_1, \ldots, x_N)$,…
FormBeyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models
Understanding the computational power of mobile robot systems is a fundamental challenge in distributed computing. While prior work has focused on pairwise separations between models, we explore how robot capabilities, l…
Arbitrary Polynomial Separations in Trainable Quantum Machine Learning
Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practic…
Quantum Machine LearningExponential separations between learning with and without quantum memory
We study the power of quantum memory for learning properties of quantum systems and dynamics, which is of great importance in physics and chemistry. Many state-of-the-art learning algorithms require access to an addition…
Open-Ended Question AnsweringExponential separations between classical and quantum learners
Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we addres…
Learning TheoryQuantum Machine Learning