Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks

• URL: http://arxiv.org/abs/2608.27113v1
• Date: Thu, 27 Aug 2026 13:26:10 GMT
• Title: Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks
• Abstract summary: Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstants with a generic of sufficiently large degree yields linearly independents.<n>We show how the conjecture implies a complete understanding of the identifiability of deep fully connected network architectures.
• Score: 5.869449310299287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.

Related papers

• Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects [0.6554326244334868]
  The tree-width of a multivariate is the tree-width of the hypergraph with hyperedges corresponding to its terms.<n>A representation of a Boolean function as the sign of a bounded tree-width is called a threshold representation.
  arXiv  Detail & Related papers  (2025-01-14T18:28:08Z)
• Equivariant Graph Network Approximations of High-Degree Polynomials for Force Field Prediction [62.05532524197309]
  equivariant deep models have shown promise in accurately predicting atomic potentials and force fields in molecular dynamics simulations. In this work, we analyze the equivariant functions for equivariant architecture, and introduce a novel equivariant network, named PACE. As experimented in commonly used benchmarks, PACE demonstrates state-of-the-art performance in predicting atomic energy and force fields.
  arXiv  Detail & Related papers  (2024-11-06T19:34:40Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Algebraic Complexity and Neurovariety of Linear Convolutional Networks [0.0]
  We study linear convolutional networks with one-dimensional and arbitrary strides. We generate equations whose common zero locus corresponds to the Zariski closure of the corresponding neuromanifold. Our findings reveal that the number of all complex critical points in the optimization of such a network is equal to the generic Euclidean distance of a Segre variety.
  arXiv  Detail & Related papers  (2024-01-29T23:00:15Z)
• Structure of universal formulas [13.794391803767617]
  We introduce a hierarchy of classes connecting the global approximability property to the weaker property of infinite VC dimension. We show that fixed-size neural networks with not more than one layer of neurons having activations cannot approximate functions on arbitrary finite sets. We give examples of functional families, including two-hidden-layer neural networks, that approximate functions on arbitrary finite sets, but fail to do that on the whole domain of definition.
  arXiv  Detail & Related papers  (2023-11-07T11:50:25Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Qualitative neural network approximation over R and C: Elementary proofs for analytic and polynomial activation [0.0]
  We prove approximations in classes of deep and shallow neural networks with analytic activation functions. We show that fully connected and residual networks of large depth with activation functions can approximate any under certain width requirements.
  arXiv  Detail & Related papers  (2022-03-25T01:36:13Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.