Shallow neural networks can represent polynomials efficiently.
problem Representing polynomials using shallow neural networks.
method Using shallow neural networks of width 2(R+d)d to represent d-variate polynomials of degree R. result Derives minimax optimal convergence rate for shallow networks to unknown univariate regression functions.
We show that the standard stochastic gradient decent (SGD) algorithm is guaranteed to learn, in polynomial time, a function that is competitive with the best function in the conjugate kernel space of the network, as defined in Daniely, Frostig and Singer. The result holds for log-depth networks from a rich family of ar…
A mathematical framework connects neural networks and polynomial regression for better model understanding.
problem Neural networks are black boxes with challenges in dimensioning and prediction error evaluation.
method Developed a mathematical framework using Taylor expansion to relate neural networks and polynomial regression.
result Polynomial approximations from neural networks trained on polynomial data are accurate locally.
The paper proves deep neural networks with analytic activation can approximate any function.
problem Approximating functions with neural networks using analytic activation functions.
method Elementary proofs for real and complex networks, Stone-Weierstrass theorem, Mergelyan's theorem.
result Closure of neural network classes equals space of polynomials for analytic activation.
We study deep neural networks with polynomial activations, particularly their expressive power. For a fixed architecture and activation degree, a polynomial neural network defines an algebraic map from weights to polynomials. The image of this map is the functional space associated to the network, and it is an irreduci…
Polynomial neural networks explore thresholds for maximum expressiveness.
problem Understanding the limits of polynomial neural networks' expressiveness.
method Introducing activation degree threshold to measure network expressiveness and proving its existence and upper bounds.
result Polynomial neural networks with equi-width architectures achieve the maximum expressiveness.
Researchers compute and predict knot volumes using colored Jones polynomials.
problem Computing and predicting volumes of hyperbolic knots.
method Vertex model approach, neural network training, polynomial evaluations.
result 3-colored Jones polynomials predict knot volumes with high accuracy.
Paper develops exact convex optimization for neural networks with polynomial activations.
problem Training two-layer neural networks with nonlinear polynomial activations.
method Exact convex optimization using semidefinite programming.
result Global optimization of neural networks is polynomial-time computable.
The paper proves barriers to approximating functions with small weights and depth in neural networks.
problem Proving barriers to approximating functions with constant depth neural networks.
method Reduction to open problems and natural-proof barriers in circuit complexity, and a new approach to polynomially-bounded functions.
result There are fundamental barriers to proving results beyond depth 4 for constant-depth neural networks.
Wide networks with polynomial activations have proven asymptotic behavior.
problem Understanding the behavior of neural networks in the large width limit.
method Proving a conjecture for deep networks with polynomial activation functions.
result Tight bounds on the behavior of wide networks during stochastic gradient descent and derivation of their finite-width dynamics.
LiPopt uses polynomial optimization to estimate neural network Lipschitz constants efficiently.
problem Estimating the Lipschitz constant of neural networks efficiently.
method Sparse polynomial optimization, leveraging network connectivity to reduce complexity.
result Superior estimates of the ℓ∞-Lipschitz constant compared to existing methods. Deep neural networks with piecewise-polynomial activations can approximate smooth functions and their derivatives.
problem Approximating smooth functions and their derivatives with neural networks.
method Derives the depth, width, and sparsity required for approximation in Hölder norms.
result Deep neural networks with bounded weights can approximate Hölder smooth functions and their derivatives.
We introduce tensor network contraction algorithms for the evaluation of the Jones polynomial of arbitrary knots. The value of the Jones polynomial of a knot maps to the partition function of a q-state Potts model defined as a planar graph with weighted edges that corresponds to the knot. For any integer q, we cast…
Study the expressivity and training complexity of polynomial neural networks.
problem Understanding the expressivity and training complexity of polynomial neural networks.
method Use algebraic geometry to describe neuromanifolds and neurovarieties, analyzing their dimension and learning degree.
result Characterized the dimension and learning degree of neuromanifolds, providing geometric and complexity measures.
Exact causal network discovery is polynomial for sparse networks.
problem Finding the optimal causal Bayesian network from data is computationally hard.
method Pruning the search space using network properties, combined with dynamic programming and shortest-path searches.
result Exact discovery is polynomial for sparse causal Bayesian networks.
New algorithm speeds up knot polynomial calculations.
problem Computing Reshetikhin--Turaev knot polynomials efficiently.
method Fixed-parameter tractable computation via tensor networks.
result Knot polynomial computations are fixed-parameter tractable.
nn2poly converts neural networks into interpretable polynomial models.
problem Interpreting complex neural networks.
method NN2Poly method for converting neural networks into polynomial models.
result Captures variable interactions and provides interpretable coefficients.
Three-layer neural networks learn hierarchical polynomial functions efficiently.
problem Learning hierarchical polynomial functions with three-layer neural networks.
method Layerwise gradient descent on square loss, focusing on feature learning.
result Achieves optimal sample complexity for learning hierarchical polynomials.
Paper analyzes sample complexity of polynomial neural networks.
problem Understanding the sample complexity of polynomial neural networks.
method Extends previous literature to polynomial neural networks and analyzes sample complexity.
result Obtains novel results on sample complexity of polynomial neural networks.
The paper shows neural networks can approximate functions over non-compact domains with non-polynomial activation.
problem Approximating functions over non-compact domains using neural networks.
method Using single-hidden-layer feedforward neural networks with non-polynomial activation functions over non-compact subsets of Euclidean spaces.
result Neural networks can approximate functions in weighted Ck-spaces and weighted Sobolev spaces over unbounded domains. Invariant polynomials improve machine learning performance.
problem Improving machine learning algorithms using invariant polynomials.
method Developed and implemented Lorentz- and permutation-invariant polynomial generators in neural networks.
result Reduction in loss on training and validation data with Hironaka decompositions.
In this work, we examine the process of Tropical Polynomial Division, a geometric method which seeks to emulate the division of regular polynomials, when applied to those of the max-plus semiring. This is done via the approximation of the Newton Polytope of the dividend polynomial by that of the divisor. This process i…
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
We study computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded factor size and bounded connectivity can be learned in polynomial time and polynomial number of samples, assuming that the data is generated by a netwo…
Bayesian neural networks learn efficiently at infinite width, matching polynomial-width performance.
problem Understanding the inductive bias of infinite-width neural networks.
method Analyzing the reduced entropy and using subsampling techniques.
result The Bayesian mean-field learner generalizes exactly on polynomially-bounded targets.
Hardness proven for learning neural networks with polynomial size and Gaussian inputs.
problem Learning one hidden layer ReLU neural networks with polynomial size and Gaussian inputs.
method Based on the hardness of the Continuous Learning with Errors (CLWE) problem.
result Hardness of learning neural networks is proven under standard cryptographic assumptions.
Proposes polynomial neural networks for improved function approximation in various tasks.
problem Improving function approximation in various tasks like image generation, face verification, and 3D mesh representation learning.
method Introduces polynomial neural networks (Π-Nets) and three tensor decompositions to reduce parameter count and enhance expressiveness. result Demonstrates that Π-Nets can produce state-of-the-art results in challenging tasks without non-linear activation functions. Neural networks learn modular arithmetic but not all, extending known solutions to generalize.
problem Neural networks struggle with modular arithmetic, especially for polynomials.
method Developed analytical solutions for MLP networks to learn modular addition and multiplication, then combined these solutions to generalize on arbitrary modular polynomials.
result Neural networks can learn and generalize solutions to modular polynomials, supporting the hypothesis that some polynomials are learnable.
The paper analyzes tensor recovery from symmetric rank-one measurements using information theory.
problem Recovering tensors with low symmetric rank from symmetric rank-one measurements.
method Covering numbers argument, Carbery-Wright inequality, orthogonal polynomials, Fano's inequality.
result Near-optimal sample complexity bounds for log-concave distributions.
Polynomial networks converge to Gaussian processes at a rate of O(n^(-1/2)).
problem Understanding the convergence rate of polynomial networks to Gaussian processes.
method Examined one-hidden-layer neural networks with random weights, focusing on polynomial activations and their convergence rate in the 2-Wasserstein metric.
result The rate of convergence for polynomial networks to Gaussian processes is $O(n^{- rac{1}{2}})$.
Study shows polynomial-width neural networks can closely approximate infinite-width networks in polynomial time.
problem Approximating dynamics of polynomial-width neural networks with infinite-width networks.
method Bounding approximation gap through a differential equation governed by mean-field dynamics, considering local Hessian.
result Polynomially many neurons are sufficient to closely approximate mean-field dynamics.
There has been a large amount of interest, both in the past and particularly recently, into the power of different families of universal approximators, e.g. ReLU networks, polynomials, rational functions. However, current research has focused almost exclusively on understanding this problem in a worst-case setting, e.g…
Study robustness of polynomial neural networks using algebraic geometry.
problem Certify robustness radius of polynomial neural networks.
method Metric algebraic geometry, Euclidean distance degree, symbolic elimination, homotopy-continuation methods.
result Found decision boundaries with lower ED degree than generic cubic hypersurfaces.
Polynomial-time algorithm learns ReLU networks without assumptions.
problem Learning linear combinations of ReLU activations with Gaussian inputs.
method Random contractions of moment tensors and multi-scale analysis.
result First polynomial-time algorithm without additional assumptions.
NN2Poly converts deep neural networks into polynomial models for better understanding.
problem Improving neural network interpretability and theoretical understanding.
method Taylor expansion on activation functions, combinatorial properties, and polynomial coefficients calculation.
result NN2Poly accurately represents deep feed-forward neural networks as polynomial models.
The paper shows how neural networks can approximate PDEs with polynomial scaling in dimension.
problem Understanding the complexity of approximating PDE solutions with neural networks.
method Developed a proof technique to simulate gradient descent using neural networks.
result Neural network parameters scale polynomially with input dimension for approximating PDE solutions.
Develops exact convex optimization formulations for neural networks.
problem Training two-layer neural networks with rectified linear units.
method Uses semi-infinite duality and minimum norm regularization to develop exact convex optimization formulations.
result Shows equivalence of ReLU networks trained with weight decay to block ℓ1 penalized convex models. Algorithm learns polynomial transformations of Gaussian distributions.
problem Learning high-dimensional polynomial transformations of Gaussian distributions.
method Polynomial-time algorithms for smoothed settings, tensor ring decomposition.
result First end-to-end guarantees for learning pushforwards under neural networks.
Analytic networks with bounded coefficients can't outperform polynomial approximations.
problem Approximation limits of neural networks with analytic activation functions under coefficient constraints.
method Deterministic analysis using comparison argument and Bernstein-type estimates.
result Networks with analytic activation functions and controlled coefficients cannot outperform classical polynomial approximation rates on non-analytic targets.
Many results in recent years established polynomial time learnability of various models via neural networks algorithms. However, unless the model is linear separable, or the activation is a polynomial, these results require very large networks -- much more than what is needed for the mere existence of a good predictor.…
PolyLUT uses polynomials to reduce FPGA latency.
problem Reducing latency in FPGA-based neural network inference.
method Training neural networks using multivariate polynomials as basic building blocks.
result Achieved significant latency and area improvements.
Proposes Π-Nets, polynomial neural networks, for improved representation power.
problem Improving representation power in deep learning models.
method Introduces Π-Nets, a new class of deep polynomial neural networks. result Demonstrates Π-Nets outperform standard DCNNs and achieve state-of-the-art results. Study on identifiability of deep polynomial neural networks.
problem Understanding when polynomial neural networks can be uniquely identified.
method Comprehensive analysis including various architectures, using tensor decompositions and Kruskal-type theorems.
result Identifiability conditions for deep PNNs, including layer width and activation degree constraints.
We prove near-tight concentration of measure for polynomial functions of the Ising model under high temperature. For any degree d, we show that a degree-d polynomial of a n-spin Ising model exhibits exponential tails that scale as exp(−r2/d) at radius r=Ω~d(nd/2). Our concentration radius is opti…
Algorithm efficiently learns deep ReLU networks with polynomial runtime in depth and parameters.
problem Learning deep ReLU networks with polynomial runtime.
method Algorithm using filtered PCA and lattice polynomial analysis.
result First nontrivial results for networks of depth more than two with polynomial runtime.
This paper shows neural networks can solve complex graph problems efficiently.
problem Solving exact maximum flow computation and minimum spanning tree problems.
method Introduces Max-Affine Arithmetic Programs and shows equivalence to neural networks.
result Two combinatorial optimization problems can be solved with polynomial-size neural networks.
Paper revisits graph-CNNs using Laplace-Beltrami spectral filters and polynomials.
problem Improving spectral graph convolutional neural networks (graph-CNNs).
method Developed Laplace-Beltrami CNN (LB-CNN) by replacing graph Laplacian with LB operator and approximating spectral filters using Chebyshev, Laguerre, and Hermite polynomials.
result Classification accuracy of LB-CNN is not dependent on the type of polynomials or operators.
Deep tensor factorization benefits from implicit regularization with polynomial growth.
problem Tensor factorization's implicit regularization effect in deep networks is not well understood.
method Investigated the implicit regularization in deep tensor factorization, showing polynomial growth.
result Implicit regularization in deep tensor factorization grows polynomially with depth, improving estimation accuracy and convergence.