We survey results on neural network expressivity described in "On the Expressive Power of Deep Neural Networks". The paper motivates and develops three natural measures of expressiveness, which all display an exponential dependence on the depth of the network. In fact, all of these measures are related to a fourth quan…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Exponential expressive power”
It is well-known that neural networks are universal approximators, but that deeper networks tend in practice to be more powerful than shallower ones. We shed light on this by proving that the total number of neurons required to approximate natural classes of multivariate polynomials of variables grows only line…
Higher granularity in MoE models boosts expressivity exponentially.
problem Expressivity of Mixture-of-Experts models with varying granularity.
method Comparing models with different numbers of active experts (granularity).
result Exponential separation in network expressivity based on granularity.
Develops European power option pricing under correlated interest rate and asset processes.
problem Pricing European power options under correlated interest rate and asset processes.
method Martingale method and Girsannov transform.
result Derives European power option pricing formulae under two market assumptions.
Paper explains why robust generalization is hard in deep learning models.
problem Difficulty in achieving robust generalization despite good training accuracy.
method Theoretical analysis of expressive power for deep neural networks.
result Expressive power of neural networks affects robust generalization.
Expressive efficiency refers to the relation between two architectures A and B, whereby any function realized by B could be replicated by A, but there exists functions realized by A, which cannot be replicated by B unless its size grows significantly larger. For example, it is known that deep networks are exponentially…
Improved bounds on neural network expressivity.
problem Understanding neural network expressivity and approximation capabilities.
method Improved bounds on the maximal number of linear regions of ReLU-networks.
result New insights into the expressivity of neural networks.
We combine Riemannian geometry with the mean field theory of high dimensional chaos to study the nature of signal propagation in generic, deep neural networks with random weights. Our results reveal an order-to-chaos expressivity phase transition, with networks in the chaotic phase computing nonlinear functions whose g…
Hierarchical neural networks are exponentially more efficient than their corresponding "shallow" counterpart with the same expressive power, but involve huge number of parameters and require tedious amounts of training. Our main idea is to mathematically understand and describe the hierarchical structure of feedforward…
We present a novel tractable generative model that extends Sum-Product Networks (SPNs) and significantly boosts their power. We call it Sum-Product-Quotient Networks (SPQNs), whose core concept is to incorporate conditional distributions into the model by direct computation using quotient nodes, e.g. $P(A|B) = \frac{P(…
MoEs can efficiently model complex tasks with low-dimensionality and sparsity.
problem Understanding the theoretical foundations of MoEs for complex tasks.
method Systematic study of MoEs with two structural priors: low-dimensionality and sparsity.
result MoEs can approximate functions on low-dimensional manifolds and exhibit exponential structured tasks.
Graph Neural Networks (graph NNs) are a promising deep learning approach for analyzing graph-structured data. However, it is known that they do not improve (or sometimes worsen) their predictive performance as we pile up many layers and add non-lineality. To tackle this problem, we investigate the expressive power of g…
Enhanced GNN with expanded attention window and partially random embeddings.
problem Limited expressivity of traditional GNNs in distinguishing non-isomorphic graphs.
method Graph attention network with expanding attention window and partially random initial embeddings. Head dropout for regularization.
result Improved ability to differentiate between non-isomorphic graphs.
Attention-based GNNs can't prevent oversmoothing, leading to homogeneous node representations.
problem The issue of oversmoothing in attention-based GNNs.
method Viewed attention-based GNNs as nonlinear time-varying dynamical systems and used tools from the theory of products of inhomogeneous matrices and the joint spectral radius.
result Graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially.
We propose a new approach to the problem of neural network expressivity, which seeks to characterize how structural properties of a neural network family affect the functions it is able to compute. Our approach is based on an interrelated set of measures of expressivity, unified by the novel notion of trajectory length…
This study compares GNNs and GA-MLPs, finding GA-MLPs can distinguish graphs but not count walks.
problem Comparing expressive power and graph isomorphism testing capabilities of GNNs and GA-MLPs.
method GA-MLPs augment node features with multi-hop operators and apply MLPs node-wise; GNNs are compared as a baseline.
result GA-MLPs can distinguish almost all non-isomorphic graphs but cannot count attributed walks, unlike GNNs.
Sequence models assign probabilities to variable-length sequences such as natural language texts. The ability of sequence models to capture temporal dependence can be characterized by the temporal scaling of correlation and mutual information. In this paper, we study the mutual information of recurrent neural networks …
Study shows shallow ReLU networks struggle with high-dimensional Lipschitz functions.
problem Expressing high-dimensional Lipschitz functions with shallow ReLU networks.
method Established lower bounds on shallow network complexity for polynomial approximation.
result Shallow ReLU networks suffer from the curse of dimensionality for Lipschitz functions.
We show that there is a simple (approximately radial) function on , expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-layer network, to more than a certain constant accuracy, unless its width is exponential in the dimension. The result holds for virtually all kn…
Additive Gaussian Processesstat.ML
We introduce a Gaussian process model of functions which are additive. An additive function is one which decomposes into a sum of low-dimensional functions, each depending on only a subset of the input variables. Additive GPs generalize both Generalized Additive Models, and the standard GP models which use squared-expo…
This work analyzes how deep neural networks' expressiveness increases with depth and width.
problem Understanding the expressiveness of deep neural networks (DNNs) based on their Lipschitz constants.
method Leveraging random matrix theory, the study characterizes the expressiveness of DNNs by their Lipschitz constant, showing exponential and polynomial increases with depth and width, respectively.
result The expressiveness of DNNs increases exponentially with depth and polynomially with width, consistent with function approximation benefits.
Graphical notation simplifies complex polynomial constraints in linear models.
problem Complex polynomial constraints in linear structural equation models are impractical.
method Developed a graphical notation to represent these constraints.
result The graphical notation simplifies the representation of many polynomial constraints.
New random feature maps for Laplacian and related kernels.
problem Challenges in approximating the Laplacian kernel and its generalizations.
method Developed random feature maps for Laplacian and related kernels, providing efficient sampling schemes.
result Demonstrated the efficacy of these random feature maps on real datasets.
The study examines cryptocurrency market activity, revealing multifractal inter-transaction times and challenging traditional statistical models.
problem Analyzing long-range autocorrelations and multifractality in cryptocurrency market activity.
method Analysis of tick-by-tick data from multiple cryptocurrency trading platforms, focusing on inter-transaction times, transaction volumes, and volatility.
result Inter-transaction times exhibit multifractality, indicating periods of increased market activity are more complex than quiet periods.
FMMNN combines sine activations with multi-component, multi-layer structure for high-frequency function approximation.
problem Effective representation and learning of high-frequency features in neural networks.
method Introduces FMMNN with sine-type activations and multi-component, multi-layer structure.
result FMMNN achieves strong accuracy and favorable convergence on oscillatory function-approximation benchmarks.
Paper proposes neural networks for learning functions from sets to graphs.
problem Challenges in learning Set2Graph functions, including computational and memory complexity.
method Develops a family of neural network models that are practical and of maximal expressive power, approximating arbitrary continuous Set2Graph functions.
result Models can approximate arbitrary continuous Set2Graph functions over compact sets.
This work analyzes neural scaling laws using power-law data spectra and derives analytical expressions for generalization error.
problem Understanding how neural network performance scales with key factors like data size and model complexity.
method Statistical mechanics techniques applied to one-pass stochastic gradient descent in a student-teacher framework.
result Derivation of analytical expressions for generalization error under power-law data spectra and identification of conditions for power-law scaling.
Improved GNN simulation of WL test with exponentially lower complexity.
problem Improving the complexity of simulating the Weisfeiler-Lehman test with GNNs.
method Exponentially lower complexity simulation of WL test using GNNs with polylogarithmic parameters and O(log n) bits feature vectors.
result Near-optimal construction with logarithmic lower bounds for feature vector length and neural network size.
Space exploration technology advances exponentially, consistent with Moore's and Wright's laws.
problem Predicting the advancement of space exploration technology.
method Analysis of Moore's and Wright's laws applied to space exploration technology.
result Spacecraft technology advances exponentially, consistent with Moore's and Wright's laws.
Survey on GNNs' power and limitations.
problem Theoretical limitations of GNNs.
method Comprehensive overview of GNNs and their variants.
result Provably powerful variants of GNNs.
The paper explores risk-minimization for exponential additive models, providing mathematical expressions and numerical examples.
problem Risk-minimization in incomplete markets for exponential additive models.
method Derive explicit mathematical expressions for local risk-minimization strategies in exponential additive models.
result Provide necessary conditions for deriving expressions and confirm integrability conditions for specific models.
This paper explores how enforcing equivariance constraints limits neural network expressivity and proposes compensatory model size increases.
problem The impact of enforcing equivariance constraints on the expressive power of neural networks.
method Examined 2-layer ReLU networks, analyzed boundary hyperplanes and channel vectors, and constructed upper bounds on model size required for compensation.
result Enforcing equivariance constraints reduces the expressive power of neural networks, but this can be compensated by increasing model size.
kth-order invariant graph networks are as powerful as kth-order WL in distinguishing graphs.
problem Measuring the expressive power of graph neural network formalisms.
method Considered kth-order invariant graph networks (k-IGNs) and compared their expressive power to kth-order WL.
result k-IGNs and k-WL are equally powerful in distinguishing graphs.
The abstract discusses parallels between Galois theory and Stone-Weierstrass theorem in various fields.
problem Connecting distinguishing power and expressive power in different fields.
method Elementary theorem connecting distinguishing power and expressive power.
result Foundational principle in linguistics linking distinguishing power and expressive power.
New MPNNs match 2-WL, faster distinguishing graphs.
problem Improving graph neural network expressiveness.
method Introducing -walk MPNNs and second-order GNNs.
result Walk MPNNs match 2-WL and can distinguish graphs faster.
Optimal approximations of power-laws with exponentialsphysics.data-an
We propose an explicit recursive method to approximate a power-law with a finite sum of weighted exponentials. Applications to moving averages with long memory are discussed in relationship with stochastic volatility models.
Study shows limits of certain normalizing flows in higher dimensions.
problem Understanding the representation power of normalizing flows in different dimensions.
method Rigorously established bounds on expressive power of basic normalizing flows.
result Limited representation power in higher dimensions, especially with moderate depth.
CoT improves transformer sample efficiency by reducing input token dependencies and attention sparsity.
problem Transformer sample inefficiency in simple tasks.
method Demonstrated through parity-learning setup, showing CoT reduces required samples from exponential to polynomial.
result Transformer learns function within polynomial samples with CoT, requiring exponential samples without CoT.
A new method approximates tangent spaces to simplify neural networks.
problem Efficiency of hierarchical neural networks is hindered by their complexity and training requirements.
method Approximates tangent subspace to enable sparse representation and switch to shallow networks.
result The method improves and sometimes surpasses the performance of original networks after a few epochs.
In this paper we consider the cohomology of a closed arithmetic hyperbolic 3-manifold with coefficients in the local system defined by the even symmetric powers of the standard representation of SL(2,C). The cohomology is defined over the integers and is a finite abelian group. We show that the order of the 2nd cohomol…
Study reveals Transformer's expressive power and mechanisms.
problem Understanding the approximation properties of Transformer for sequence modeling.
method Systematic study of Transformer's components and their combined effects, establishing approximation rates.
result Reveals roles of critical parameters in Transformer, such as number of layers and attention heads.
A new complexity measure for neural networks improves upon classical methods.
problem Lack of a refined complexity measure for comparing different neural network architectures, especially permutation-invariant ones.
method Introduced an equivalence relation among linear functions and counted them relative to this relation.
result The new complexity measure clearly distinguishes between different models and increases exponentially with depth.
We introduce a new statistical tool (the TP-statistic and TE-statistic) designed specifically to compare the behavior of the sample tail of distributions with power-law and exponential tails as a function of the lower threshold u. One important property of these statistics is that they converge to zero for power laws o…
The distribution of recurrence times or return intervals between extreme events is important to characterize and understand the behavior of physical systems and phenomena in many disciplines. It is well known that many physical processes in nature and society display long range correlations. Hence, in the last few year…
Modelling High-Frequency Data with Bivariate Hawkes Processes: Power-Law vs. Exponential Kernelsq-fin.MF
Study compares exponential and power-law kernels in modeling high-frequency trading data.
problem Modeling high-frequency trading data with specific kernel types.
method Proposes and analyzes two bivariate Hawkes processes with exponential and power-law kernels.
result Identifies strengths and limitations of exponential and power-law kernels for high-frequency trading data.
Ormerod and Mounfield analysed GDP data of 17 leading capitalist economies from 1870 to 1994 and concluded that the frequency of the duration of recessions is consistent with a power-law. But in fact the data is consistent with an exponential (Boltzmann-Gibbs) law.
Geometric GNNs improve graph discrimination through GWL.
problem Discriminating geometric graphs embedded in Euclidean space.
method Proposed a geometric version of the Weisfeiler-Leman test (GWL) for geometric graphs.
result Characterized the expressive power of geometric GNNs based on physical symmetries.
Paper explores how GNNs can learn graph biconnectivity, finding ESAN is the only known expressive framework.
problem Understanding the expressive power of GNNs beyond the WL test.
method Introduces a novel class of expressivity metrics via graph biconnectivity and develops the GD-WL approach.
result GD-WL consistently outperforms prior GNN architectures in learning biconnectivity metrics.