HOLOGRAPHIC FUNCTIONS AND NEURAL NETWORKS
arXiv:2605.22666v1 [math.CO] 21 May 2026
BALÁZS SZEGEDY
Abstract. A fuzzy Boolean function is a map f : {0, 1}n → [0, 1], where n ∈ N. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value f (x) can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of x. We call this the holographic property. The second is a structural property: f is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational: f is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.
1. Introduction We define a fuzzy Boolean function to be a map f : {0, 1}n −→ [0, 1]. Such functions arise naturally in many contexts. In machine learning, for instance, the value f (x) may be interpreted as the probability that the input string x has a certain learned property. Since many classification problems do not have an intrinsically sharp yes-or-no answer, the fuzzy Boolean framework is a natural one. Artificial neural networks have proved remarkably effective in machine learning and this motivates the following broad question. Is there a mathematically robust complexity theory for fuzzy Boolean functions which reflects their representability, or approximability, by neural networks of bounded complexity? The representability of multivariable functions by neural networks is a broad topic, with a large literature ranging from classical universal approximation theorems [1, 4, 6] to quantitative approximation results for specific architectures and smoothness classes [9], as well as modern studies of expressive power, depth, and complexity. What differentiates our work is a particular dimension-independent structural viewpoint. We study representability questions for fuzzy Boolean functions through a sampling property and a regularization principle related to Szemerédi’s famous regularity lemma [7, 2] and to the more general hypergraph regularity theory [5, 3, 8]. Roughly speaking, we show that bounded random recoverability, which we call the holographic property, is equivalent to approximation by bounded-degree polynomials in boundedly many coordinate linear forms with bounded ℓ1 -norms. We then relate this structural statement to representability by neural networks satisfying strong boundedness conditions. In this way, we isolate one particular regime in which the question above has a rigorous and conceptually transparent answer. In addition, our results suggest how certain characteristic features Date: May 22, 2026. 2020 Mathematics Subject Classification. Primary 68T07, 06E30; Secondary 05C80, 41A10, 60C05. Key words and phrases. Boolean functions, neural networks, hypergraph regularity, sampling, polynomial approximation, graph limits. 1
of neural networks, such as large weighted averages followed by local nonlinearities, can emerge naturally from abstract complexity notions. The guiding observation is that, in many examples related to machine learning, the information determining f (x) is, in a suitable sense, holographically distributed among the bits of x. Roughly speaking, this means that the value of f (x) can be estimated, with high probability and small error, from the values of a bounded number of sampled coordinates, provided that the sampled locations are also known. At first sight this may seem counterintuitive since a bounded sample appears to contain only a negligible fraction of the input when n is large. However, in many high-dimensional data sets the relevant information is highly redundant. For example, if one considers images of increasing resolution, then a sufficiently large but bounded random sample of pixels may already give substantial information about the content of the image, even though it represents only a small fraction of all pixels. The holographic condition is an abstract formalization of this kind of distributed redundancy. We also note a possible connection with statistical physics. Macroscopic states of a system often arise from, and depend on, a very large number of microscopic degrees of freedom. The notions considered here may provide a useful language for studying when such macroscopic observables can be recovered from limited random information about the underlying microstate. The next definition formalizes our main concept. Definition 1.1 (Holographic functions). Let k ∈ N and ε > 0. A function f : {0, 1}n → [0, 1] is called (k, ε)-holographic if there exist probability measures µ1 , . . . , µk on [n] = {1, . . . , n} and functions fs : {0, 1}k → [0, 1], s = (s1 , . . . , sk ) ∈ [n]k , such that for every x ∈ {0, 1}n , if S1 , . . . , Sk are independent random variables with Sj having law µj , and S = (S1 , . . . , Sk ), then P (|f (x) − fS (xS1 , . . . , xSk )| ≤ ε) ≥ 1 − ε. When S = (S1 , . . . , Sk ), we write xS for the tuple (xS1 , . . . , xSk ). The functions fs are called test functions and µ1 , . . . , µk are called sampling measures. The definition intentionally allows the test function to depend on the sampled locations. This is important since the same bit value may have different meanings at different coordinates. Remark 1.2. Interestingly, as we will show in Section 7, the sampling measures in the definition above may be taken to be identical at the qualitative level, at the cost of changing the sample bound and the accuracy parameter. For the precise definition of qualitative equivalence between properties for fuzzy Boolean functions see Definition 1.3. The present formulation, which allows different sampling measures in different query positions, is more convenient for the proof of the main theorem. From a conceptual point of view, however, the formulation with a single common sampling measure is also natural and may be preferable in some applications. The main purpose of this paper is to compare several notions of bounded complexity for fuzzy Boolean functions. The key organizing concept is qualitative equivalence, which formalizes when two such notions can be converted into one another with dimension-independent control of complexity and accuracy. A two-parameter property P of fuzzy Boolean functions assigns, to each pair (K ∈ N, ε > 0), a class P (K, ε) of fuzzy Boolean functions, over all dimensions n, satisfying the corresponding property with complexity parameter K and accuracy ε. The holographic property defined above is an example of such a property. 2
Definition 1.3 (Qualitative implication and equivalence). Let P and Q be two-parameter properties of fuzzy Boolean functions. We say that P qualitatively implies Q, and write P ⪯ Q, if for every ε > 0 there exists δ = δ(ε) > 0 such that for every K ∈ N there exists K ′ = K ′ (K, ε) ∈ N satisfying P (K, δ) ⊆ Q(K ′ , ε). We say that P and Q are qualitatively equivalent if P ⪯ Q and Q ⪯ P . Now we turn to the second property which we call polynomial. The polynomials that appear are not arbitrary polynomials in the n coordinates. They are polynomials in boundedly many bounded linear forms in the coordinates. The coefficient ℓ1 -norm of a polynomial always means the sum of the absolute values of its coefficients in the standard monomial basis. Definition 1.4 (Polynomial property). Let K ∈ N and ε > 0. A function f : {0, 1}n → [0, 1] has the (K, ε)-polynomial property if there exist an integer m with 1 ≤ m ≤ K, linear functions Li (x) =
n X
wij xj
j=1
with
n X
|wij | ≤ K,
j=1
and a polynomial p ∈ R[y1 , . . . , ym ] of degree at most K and coefficient ℓ1 -norm at most K, such that |f (x) − p(L1 (x), . . . , Lm (x))| ≤ ε for every x ∈ {0, 1}n . The third property is neural-network representability. The following model is deliberately broad and somewhat nonstandard. The activation functions are allowed to vary from neuron to neuron, but their Lipschitz constants, ranges, and incoming affine norms are uniformly controlled by the complexity parameter. Definition 1.5 (Bounded Lipschitz neural networks). A bounded Lipschitz neural network on {0, 1}n is a finite directed acyclic graph with exactly n input vertices, one carrying each coordinate function x1 , . . . , xn . Every non-input vertex v carries an affine form X Lv (z) = cv + wv,u zu u≺v
in the values of earlier vertices and an activation function σv : R → [0, 1]. The value at v is zv = σv (Lv (z)). One distinguished non-input vertex is the output vertex. The complexity of the network is at most K if the number of non-input vertices is at most K and, for every non-input vertex v, X |cv | + |wv,u | ≤ K, Lip(σv ) ≤ K. u≺v
A non-input vertex may receive edges from any subset of the input vertices, including a subset whose size depends on n, provided the total incoming ℓ1 -weight is bounded as above. The number of nonzero incoming edges from input vertices is not counted separately. Remark 1.6. Bounded Lipschitz neural networks are not required to have a bounded total number of parameters. Although the number of non-input neurons is bounded, the number of input vertices may grow with the ambient dimension. 3
Definition 1.7 (Bounded neural-network property). Let K ∈ N and ε > 0. A function f : {0, 1}n → [0, 1] has the (K, ε)-bounded neural-network property if there exists a bounded Lipschitz neural network of complexity at most K computing a function F : {0, 1}n → [0, 1] such that ∥f − F ∥∞ ≤ ε. Now we are ready to state the main theorem which establishes qualitative equivalence of the above three properties. Theorem 1.8 (Main theorem). The holographic property, the polynomial property and the bounded neural-network property are qualitatively equivalent in the sense of Definition 1.3. More explicitly: (a) for every k and ε ∈ (0, 1) there is K1 = K1 (k, ε) ∈ N such that every (k, ε)-holographic function has the (K1 , 3ε)-polynomial property; (b) for every K there is K2 = K2 (K) ∈ N such that every function with the (K, ε)-polynomial property has the (K2 , ε)-bounded neural-network property; (c) for every K and ε ∈ (0, 1) there is K3 = K3 (K, ε) ∈ N such that every function with the (K, ε)-bounded neural-network property is (K3 , 3ε)-holographic. The proof of Theorem 1.8 follows directly from three major propositions proved in the subsequent sections of the paper. Proposition 3.4 gives part (a), Proposition 4.2 gives part (b), and Proposition 5.3 gives part (c). The constants in the proof are not optimized. The implication from holography to polynomial structure uses a regularity lemma and therefore has relatively poor quantitative dependence in general. The other two implications have more elementary dependences once the dimension of the polynomial representation or the network complexity is fixed. Remark 1.9. Theorem 1.8 establishes cyclic qualitative implication among the three properties above. Since qualitative implication is transitive, it follows that the three properties are qualitatively equivalent. 2. Elementary examples Example 2.1 (Functions of weighted coordinate averages). Let µ be a probability measure on [n] and let ! n X f (x) = σ µ(i)xi , i=1
where σ : [0, 1] → [0, 1] is 1-Lipschitz. Then, for every ε ∈ (0, 1), f is (r, ε)-holographic with r = O(ε−2 log(1/ε)). Indeed, sample r independent coordinates from µ and use the test function r X 1 αj . fs (α1 , . . . , αr ) = σ r j=1
The empirical average of the sampled bits approximates uniformly in x, by Hoeffding’s inequality.
P
i µ(i)xi with probability at least 1 − ε,
Example 2.2 (Small juntas). If f depends on at most r coordinates i1 , . . . , ir , then f is holographic with k = r by taking µj to be the point mass at ij and using the test function that reads these coordinates. In the more restrictive iid version of the definition one would need a coupon-collector bound, for example k = O(r log(r/ε)) samples from the uniform distribution on the relevant coordinates. 4
Example 2.3 (A non-example). It is easy to see that the parity function x 7→ x1 + · · · + xn (mod 2) is not holographic with bounded k and error below 1/2 as n → ∞. A stronger form of this obstruction follows from Lemma 3.1: if n is large compared with k, then most coordinates must have small influence on any (k, ε)-holographic function. Thus highly sensitive functions such as parity cannot satisfy the holographic property with bounded sample complexity. 3. From holography to polynomials We begin with a simple observation. If a holographic test succeeds with high probability, then its expectation gives a uniformly good approximation. Lemma 3.1 (Averaging the tests). Let f : {0, 1}n → [0, 1] be (k, ε)-holographic with sampling measures µ1 , . . . , µk and test functions fs . Define F (x) = EfS (xS1 , . . . , xSk ), where S1 , . . . , Sk are independent and Sj has law µj . Then ∥f − F ∥∞ ≤ 2ε. Proof. Fix x. With probability at least 1 − ε, the random variable fS (xS ) differs from f (x) by at most ε. On the exceptional event it differs by at most 1. Hence |F (x) − f (x)| ≤ (1 − ε)ε + ε ≤ 2ε. □ For each pattern α = (α1 , . . . , αk ) ∈ {0, 1}k , define a coefficient array gα (s) = fs (α),
s ∈ [n]k .
Then F (x) =
X
E gα (S)
k Y
1xSj =αj .
j=1
α∈{0,1}k
The problem is that the arrays gα may be arbitrary functions on [n]k . The following regularity lemma says that, for the purpose of integration over product boxes, all these arrays can be simultaneously approximated by arrays that are constant on the cells of a bounded partition. Theorem 3.2 (Box regularity lemma). For every η > 0 and k, t ∈ N there exists M = M (k, t, η) ∈ N with the following property. Let µ1 , . . . , µk be probability measures on [n] and let g1 , . . . , gt : [n]k → [0, 1]. Then there is a partition [n] = T1 ∪ · · · ∪ Tm with m ≤ M such that for every i ∈ {1, . . . , t} there is a step array Wi : [m]k → [0, 1] for which, for all product sets A1 × · · · × Ak ⊆ [n]k , k k Y X Y E gi (S) 1Sj ∈Aj − Wi (u) µj (Aj ∩ Tuj ) ≤ η, j=1
u∈[m]k
j=1
where S1 , . . . , Sk are independent and Sj has law µj . One may take, for instance, M (k, t, η) = 2k⌈tη 5
−2 ⌉
.
Remark 3.3. Theorem 3.2 is a standard weak cut-norm, or weak hypergraph-regularity, statement for bounded measurable k-arrays tested against product boxes; it is in the same spirit as weak graph and hypergraph regularity results such as those in [2, 3, 8, ?]. A direct simultaneous energyincrement proof, allowing the coordinate measures µ1 , . . . , µk to be distinct while using one common partition of [n], is included in Section 6. Equivalently, the conditional expectations used there are taken with respect to the product measure µ1 × · · · × µk , so distinct coordinate measures cause no additional difficulty. Cells of measure zero cause no ambiguity in the displayed formula, since all terms involving such cells are multiplied by zero. We now prove the first implication in the main theorem. Proposition 3.4 (Holography implies polynomial structure). For every k ∈ N and ε ∈ (0, 1) there exists K = K(k, ε) ∈ N such that every (k, ε)-holographic function has the (K, 3ε)-polynomial property. Proof. Let f : {0, 1}n → [0, 1] be (k, ε)-holographic. Let µ1 , . . . , µk and fs be as in the definition, and let F be the average test function from Lemma 3.1. For each α ∈ {0, 1}k , let gα (s) = fs (α). Apply Theorem 3.2 to the t = 2k arrays gα with parameter η = ε/2k . We obtain a partition [n] = T1 ∪ · · · ∪ Tq , q ≤ M (k, 2k , η), and step arrays Wα : [q]k → [0, 1]. For ℓ ∈ [k] and u ∈ [q], write X aℓ,u = µℓ (Tu ), Bℓ,u (x) = µℓ (i)xi . i∈Tu
Note that aℓ,u is a constant and Bℓ,u is a linear function in the variable vector x. Each linear form Bℓ,u has coefficient ℓ1 -norm at most 1 and 0 ≤ aℓ,u ≤ 1 holds for every ℓ, u. The kq functions Bℓ,u are precisely the linear forms that will be counted in the polynomial representation, and their number will be absorbed into the final complexity parameter K. Define the linear polynomials Cℓ,u,0 = aℓ,u − Bℓ,u
Cℓ,u,1 = Bℓ,u ,
and the polynomial P in the kq variables (Bℓu )ℓ,u by
P (Bℓ,u )ℓ,u =
X
X
α∈{0,1}k u∈[q]k
Wα (u)
k Y
Cj,uj ,αj .
j=1
Note that there is a slight abuse of notation in the definition of P and Cℓ,u,β . They are treated as polynomials in the formal variables (Bℓ,u )ℓ,u , and their coefficient norms are computed in this polynomial ring. On the other hand, each Bℓ,u represents a linear form on the coordinates of x ∈ {0, 1}n . Thus, after substituting these linear forms into P , we may also evaluate P on Boolean vectors x. The polynomial P has degree at most k. Its coefficient ℓ1 -norm is bounded explicitly by ∥P ∥ℓ1 ≤
X
X
α∈{0,1}k u∈[q]k
Wα (u)
k Y
Cj,uj ,αj ℓ1 ≤ 2k q k · 2k = 4k q k .
j=1
For a fixed x, the set of indices with bit value αj is Aj (αj , x) = {i ∈ [n] : xi = αj }. The regularity lemma gives, for each α, k k Y X Y Cj,uj ,αj (x) ≤ η. E gα (S) 1xSj =αj − Wα (u) j=1
u∈[q]k 6
j=1
Summing over the 2k patterns α shows that ∥F − P ((Bℓ,u )ℓ,u )∥∞ ≤ 2k η = ε. Together with Lemma 3.1, this gives ∥f − P ((Bℓ,u )ℓ,u )∥∞ ≤ 3ε. Taking K to be 4k M (k, 2k , η)k gives a complexity parameter depending only on k and ε. The kq linear functions Bℓ,u , together with the polynomial P , therefore satisfy the formal polynomial property. □ 4. From polynomials to neural networks The second implication is a finite-dimensional algebraic realization statement. Once a function is expressed as a polynomial in boundedly many bounded linear forms, a bounded-size neural network with bounded weights and bounded Lipschitz constants can compute those linear forms and then compute the clipped polynomial. Lemma 4.1 (Exact neural representation of polynomials). Let d, D ∈ N and C ≥ 1. There exists R = R(d, D, C) ∈ N such that for every polynomial Q ∈ R[y1 , . . . , yd ] of degree at most D and coefficient ℓ1 -norm at most C, the function y 7−→ χ(Q(y)),
χ(t) = min(1, max(0, t)),
on [0, 1]d is computed exactly by a bounded Lipschitz neural network of complexity at most R in the auxiliary real-input model. Proof. Let χ(t) = min(1, max(0, t)), ψ(t) = χ(t)2 . Then χ, ψ : R → [0, 1] are Lipschitz, with Lipschitz constants at most 1 and 2, respectively, and on [0, 1] one has χ(t) = t and ψ(t) = t2 . We define a multiplication module consisting of four neurons. Suppose two earlier vertices, or input vertices, carry values u, v ∈ [0, 1]. Add three square vertices carrying u+v , b = ψ(u), c = ψ(v), a=ψ 2 and then add a fourth vertex with activation χ and linear input 1 1 2a − b − c. 2 2 Since u, v ∈ [0, 1], this fourth vertex carries ! u+v 2 1 2 1 2 χ 2 − u − v = χ(uv) = uv. 2 2 2 All incoming linear ℓ1 -norms are at most 3, and all activation Lipschitz constants are at most 2. Using the multiplication module iteratively, every monomial y α = y1α1 · · · ydαd ,
|α| ≤ D,
can be computed exactly by at most 4(|α|−1) non-input vertices when |α| ≥ 2. Note that monomials of degree 0 and 1 require no multiplication vertices, since the constant term is handled by the final affine input and the degree-one monomials are input coordinates. At each stage the computed value lies in [0, 1], so the next multiplication module applies. There are only d+D N (d, D) = D 7
monomials of degree at most D. Compute all monomials of degree at least 2 by the iterative construction above, in any fixed order. Finally add one output vertex with activation χ whose affine input is the linear combination of the available monomial values with the coefficients of Q. The constant coefficient of Q is used as the bias. The affine ℓ1 -norm at this output vertex is at most the coefficient ℓ1 -norm of Q, hence at most C. The output is exactly χ(Q(y)) on [0, 1]d . Thus the number of non-input vertices is bounded by a function of d and D, for instance 1 + 4(D − 1)N (d, D), and every incoming affine ℓ1 -norm and activation Lipschitz constant is bounded by max(C, 3). Taking R to be the ceiling of the maximum of these bounds proves the lemma. □ Proposition 4.2 (Polynomial structure implies neural representation). For every K ∈ N there exists K ′ = K ′ (K) ∈ N such that every function with the (K, ε)-polynomial property has the (K ′ , ε)-bounded neural-network property, for every ε ∈ (0, 1). Proof. Let f : {0, 1}n → [0, 1] have the (K, ε)-polynomial property. Thus there are m ≤ K, linear functions n n X X Li (x) = wij xj , |wij | ≤ K, j=1
j=1
and a polynomial p of degree at most K and coefficient ℓ1 -norm at most K such that |f (x) − p(L1 (x), . . . , Lm (x))| ≤ ε for every x ∈ {0, 1}n . For x ∈ {0, 1}n we have Li (x) ∈ [−K, K]. Define scaled affine forms n
1 X wij Li (x) + K = + xj . Yi (x) = 2K 2 2K j=1
Then Yi (x) ∈ [0, 1] on {0, 1}n , and P n K + j |wij | 1 X wij + ≤ ≤ 1. 2 2K 2K j=1
Hence the first layer of a network may compute the m values Yi exactly on {0, 1}n using the clipped identity activation χ(t) = min(1, max(0, t)). These first-layer vertices may receive edges from all n input vertices; only the total incoming ℓ1 -weight is relevant to the complexity. Define a polynomial Q on [0, 1]m by Q(y1 , . . . , ym ) = p(2Ky1 − K, . . . , 2Kym − K). It has degree at most K. Its coefficient ℓ1 -norm is bounded only in terms of K. Indeed, each monomial of degree at most K in the variables Li = 2Kyi − K expands with coefficient ℓ1 -norm at most (3K)K , and the coefficient ℓ1 -norm of p is at most K. Thus ∥Q∥ℓ1 ≤ K(3K)K . Apply Lemma 4.1 with d = m,
D = K,
C = K(3K)K .
This gives an auxiliary real-input network, of complexity bounded in terms of K only, which computes χ(Q(y)) = min(1, max(0, Q(y))) exactly on [0, 1]m . 8
Composing this real-input network with the first layer computing Y1 , . . . , Ym gives a Booleaninput bounded Lipschitz network whose complexity is bounded by a number depending only on K. The outputs of the first layer lie in [0, 1]m for every Boolean input x, so the composed network evaluates the auxiliary real-input network only on the domain on which Lemma 4.1 gives exact correctness. For every x ∈ {0, 1}n the output is χ(Q(Y1 (x), . . . , Ym (x))) = χ(p(L1 (x), . . . , Lm (x))). Since f (x) ∈ [0, 1] and χ is the metric projection of R onto [0, 1], |f (x) − χ(t)| ≤ |f (x) − t|
for all t ∈ R.
Therefore |f (x) − χ(p(L1 (x), . . . , Lm (x)))| ≤ ε ′ for every x. Choose K to dominate simultaneously the m ≤ K first-layer vertices, the number of non-input vertices in the finite-dimensional realization, all incoming affine ℓ1 -norms in both parts of the composed network, and all activation Lipschitz constants. This K ′ depends only on K, not on ε. This proves the proposition. □ 5. From neural networks to holography We now prove that bounded Lipschitz networks are holographic. The proof is an induction over the computational graph. The basic fact is that a bounded affine average of many bounded quantities can be estimated from a bounded number of random samples. Lemma 5.1 (Sampling a bounded linear form). Let B ≥ 1, let z1 , . . . , zN ∈ [0, 1] and let L=c+
N X
|c| +
wi z i ,
i=1
X
|wi | ≤ B.
i
For every δ, ρ ∈ (0, 1) there is r = raff (B, δ, ρ) and a randomized procedure which queries at most r b such that of the values zi and outputs L b − L ≤ δ) ≥ 1 − ρ. P( L The distribution of the queried indices depends only on the coefficients wi and not on the values zi . P Proof. Let A = i |wi |. If A = 0, then L = c and no query is needed. Otherwise sample indices I1 , . . . , Ir independently with P(Ij = i) = |wi | /A. Set r X b =c+ 1 Yj . Yj = A sgn(wIj )zIj , L r j=1
b = L and Yj ∈ [−B, B]. Hoeffding’s inequality gives Then EL rδ 2 b P( L − L > δ) ≤ 2 exp − 2 . 2B Choosing r ≥ 2B 2 δ −2 log(2/ρ) proves the lemma.
□
Lemma 5.2 (Sampling a network). Let F : {0, 1}n → [0, 1] be computed by a bounded Lipschitz neural network of complexity at most K. For every δ ∈ (0, 1) there exists r = r(K, δ) ∈ N, probability measures ν1 , . . . , νr on [n], and a reconstruction function Φs : {0, 1}r → [0, 1] 9
(s ∈ [n]r )
such that, if S1 , . . . , Sr are independent and Sj has law νj , then, for every x ∈ {0, 1}n , P (|ΦS (xS1 , . . . , xSr ) − F (x)| ≤ δ) ≥ 1 − δ. After the sampled locations s are fixed, Φs is deterministic; there is no additional internal randomness. Proof. Order the non-input vertices as v1 , . . . , vM , where M ≤ K, so that all non-input vertices feeding into vj occur among v1 , . . . , vj−1 . Such an ordering exists because the network graph is acyclic. We prove by induction on this order that, for every non-input vertex vj and every pair of parameters τ, ρ ∈ (0, 1), the value zvj (x) can be estimated to accuracy τ with failure probability at most ρ using a number of independent coordinate samples bounded by a function Rj (τ, ρ) depending only on K, τ, ρ and j. The estimator is specified by a fixed finite list of sampling measures on [n], depending only on the network and on τ, ρ, and by a deterministic reconstruction function depending on the sampled locations and sampled bits. Repeated independent estimates of the same predecessor are allowed. Consider a vertex vj . Write its affine input as Lvj = cvj +
n X
X
αi xi +
βu zu .
u≺vj u noninput
i=1
The sum of the absolute values of all displayed coefficients, together with cvj , is at most K. Put τ . γ= 2K First estimate the direct input affine form cvj +
n X
αi xi
i=1
by Lemma 5.1, with B = K, to accuracy γ and failure probability ρ/2. This uses at most raff (K, γ, ρ/2) independent coordinate samples from the distribution proportional to |αi |, unless all αi vanish, in which case the direct input affine form is the known constant cvj and no such samples are needed. If vj has no non-input predecessors, this direct estimate, followed by the activation σvj , gives an estimate of zvj ; on the success event the error is at most Kγ ≤ τ . This is the base case. In general, for each non-input predecessor u = vh with βu ̸= 0, use the induction hypothesis to estimate zu to accuracy γ/K and failure probability at most ρ/(2K). Zero-coefficient predecessors are ignored, and the number of nonzero non-input predecessors is at most the total number of noninput vertices, hence at most K. Use independent samples for the different predecessor estimators and for the direct input estimator. The complete list of samples for vj is the concatenation, in a predetermined order, of these independent lists. Its sampling measures are therefore fixed in advance and depend only on the network and on the accuracy parameters, not on x or on any sampled values. Once all sampled locations in this concatenated list are fixed, each lower-level reconstruction is deterministic by induction, and the final reconstruction at vj is deterministic as well. On the event that all predecessor estimates and the direct input estimate succeed, the affine form Lvj is estimated within at most X γ ≤ γ + γ = 2γ. γ+ |βu | K u≺v j
u noninput 10
Since Lip(σvj ) ≤ K, the value zvj = σvj (Lvj ) is then estimated within 2Kγ = τ . The union bound gives failure probability at most ρ ρ/2 + K · = ρ. 2K The sample count satisfies the recursive bound γ ρ X ρ Rh , Rj (τ, ρ) ≤ raff K, γ, + , 2 K 2K u=v ≺v h
j
u noninput βu ̸=0
with the sum empty in the base case. Since there are at most K non-input vertices, this recursion depends only on K, τ, ρ and j. The case of zero direct input weights is included by allowing the corresponding affine sample count to be zero. Applying this construction to the output vertex with τ = ρ = δ gives a finite list of coordinatesampling measures of length at most a number depending only on K and δ. Choose a final length r = r(K, δ) ≥ 1 dominating this bound. If fewer than r samples are used in the resulting fixed list, we pad the list with dummy samples from an arbitrary fixed coordinate distribution on [n] and ignore them. This is possible since n ≥ 1. Finally, the reconstruction is clipped to [0, 1], which cannot increase the error because F (x) ∈ [0, 1]. □ Proposition 5.3 (Neural representation implies holography). For every K ∈ N and ε ∈ (0, 1) there exists k = k(K, ε) ∈ N such that every function with the (K, ε)-bounded neural-network property is (k, 3ε)-holographic. Proof. Let f be within ε of a network output F of complexity at most K. Apply Lemma 5.2 to F with δ = ε. We obtain k = k(K, ε) independent coordinate samples, not necessarily identically distributed, and reconstruction functions Φs : {0, 1}k → [0, 1]. Define the holographic test functions by fs = Φs , s ∈ [n]k . Then, for every x, P(|fS (xS ) − F (x)| ≤ ε) ≥ 1 − ε. Since ∥f − F ∥∞ ≤ ε, the same test differs from f (x) by at most 2ε with probability at least 1 − ε. By monotonicity in the error parameter, 2ε ≤ 3ε and 1 − ε ≥ 1 − 3ε, so f is (k, 3ε)-holographic. □ 6. Regularization in detail For completeness, we include a proof of the box regularity lemma in a form sufficient for this paper. This section may be skipped by readers who are willing to use any standard weak hypergraph regularity lemma. For a finite set X with probability measures µ1 , . . . , µk and a function h : X k → R, define the box norm Z k Y ∥h∥□,k = sup h(x1 , . . . , xk ) 1Aj (xj ) dµ1 (x1 ) · · · dµk (xk ) . A1 ,...,Ak ⊆X
Xk
j=1
If P is a partition of X, let E(h | P k ) be the conditional expectation of h with respect to the product partition and the product measure µ1 × · · · × µk . On boxes of product measure zero the value of this conditional expectation may be chosen arbitrarily. 11
Lemma 6.1 (Simultaneous weak box regularity). For every k, t ∈ N, every η > 0, and every M0 ∈ N, there is M = M (k, t, η, M0 ) ∈ N such that for every finite set X, every choice of probability measures µ1 , . . . , µk on X, every h1 , . . . , ht : X k → [0, 1], and every initial partition P0 of X into at most M0 parts, there is a refinement P of P0 into at most M parts with hi − E(hi | P k )
□,k
≤η
for every i ∈ {1, . . . , t}.
One may take, for instance, M = M0 2k⌈tη
−2 ⌉
.
Proof. Start with the initial partition P0 . For a partition P, define the total energy E(P) =
t X
E(hi | P k )
i=1
2 2
,
where the L2 norm is taken with respect to µ1 × · · · × µk . Since 0 ≤ hi ≤ 1, we have 0 ≤ E(P) ≤ t. If the current partition P does not satisfy the conclusion, then for some i there are sets A1 , . . . , Ak ⊆ X such that, with k Y r = hi − E(hi | P k ), ϕ= 1A j , j=1
we have |⟨r, ϕ⟩| > η. In particular ∥ϕ∥2 ̸= 0, so the division by ∥ϕ∥2 below is legitimate. Refine P by all the sets A1 , . . . , Ak , and call the resulting partition Q. Then ϕ is Qk -measurable. Since ∥ϕ∥2 ≤ 1, E(r | Qk )
2
≥
⟨E(r | Qk ), ϕ⟩ |⟨r, ϕ⟩| = ≥ η. ∥ϕ∥2 ∥ϕ∥2
Because Q refines P, the martingale difference identity gives E(hi | Qk )
2 2
− E(hi | P k )
2 2
= E(r | Qk )
2 2
≥ η2.
The energies of the other functions do not decrease under refinement. Hence the total energy increases by at least η 2 . The process therefore stops after at most ⌈tη −2 ⌉ refinement steps. At each step refining by k sets multiplies the number of atoms by at most 2k . Thus the final number of atoms is at most −2 M0 2k⌈tη ⌉ . □ Proof of Theorem 3.2. Apply Lemma 6.1 to g1 , . . . , gt starting with the trivial partition. We obtain a common partition P = {T1 , . . . , Tm } with m ≤ M (k, t, η, 1) = 2k⌈tη
−2 ⌉
and gi − E(gi | P k )
□,k
≤η
for all i. Writing Wi (u) for the value of the conditional expectation on the box Tu1 × · · · × Tuk gives the desired formula. Since each gi is [0, 1]-valued, these conditional expectations may be chosen in [0, 1]. If such a box has product measure zero, choose Wi (u) arbitrarily in [0, 1]; its contribution to Q the formula is zero. Indeed, if kj=1 µj (Tuj ) = 0, then for every product test set A1 × · · · × Ak one has k Y µj (Aj ∩ Tuj ) = 0, j=1 12
so the corresponding summand is unaffected by the chosen value of Wi (u).
□
7. Equivalence of identical and non-identical sampling In the definition of holographic functions used above, the different query positions are allowed to have different sampling measures µ1 , . . . , µk on the coordinate set [n]. In this section we show that, at the qualitative level (see Definition 1.3), this is equivalent to the apparently more restrictive version in which all query positions are sampled independently from one common measure. The identically sampled version is plainly a special case of the non-identically sampled version. The nontrivial direction is that different measures can be simulated by taking more samples from their average. Definition 7.1 (Identically sampled holography). A function f : {0, 1}n → [0, 1] is called identically sampled (k, ε)-holographic if it satisfies the definition of (k, ε)-holography with sampling measures µ1 = · · · = µk = µ for some single probability measure µ on [n]. Proposition 7.2. Let k ∈ N and 0 < ε < 1. Put ε2 ε2 , η= . 4 2 n Suppose that f : {0, 1} → [0, 1] is (k, α)-holographic with non-identical sampling. Then f is identically sampled (r, ε)-holographic for every integer r satisfying α=
ke−r/k ≤ η. In particular, it is enough to take 2k k = k log 2 . η ε Consequently, the identically sampled and non-identically sampled versions of holography define the same qualitative notion after changing the complexity and accuracy parameters. r ≥ k log
Proof. Assume that f is (k, α)-holographic with non-identical sampling. Thus there are probability measures µ1 , . . . , µ k on [n], and test functions fs : {0, 1}k → [0, 1], s ∈ [n]k , such that for every x ∈ {0, 1}n , P (|f (x) − fS (xS1 , . . . , xSk )| ≤ α) ≥ 1 − α, where Si are independent and Si ∼ µi . Define the average measure k
µ=
1X µi . k i=1
A sample from µ may be generated in two steps: first choose a hidden label I ∈ [k] uniformly, and then sample from µI . More precisely, let I1 , . . . , Ir be independent uniform random variables on [k], and, conditional on these labels, let Tj ∼ µIj independently for j = 1, . . . , r. Then the variables T1 , . . . , Tr are independent and each has law µ. 13
Let E be the event that every label 1, . . . , k appears among I1 , . . . , Ir . By the union bound, 1 r c P(E ) ≤ k 1 − ≤ ke−r/k ≤ η. k On the event E, define τi to be the first index j such that Ij = i. Thus Iτi = i,
i = 1, . . . , k.
The selected coordinates Tτ1 , . . . , Tτk are independent and have respective laws µ1 , . . . , µ k . Indeed, conditional on any label sequence for which E holds, the selected coordinate Tτi is sampled from µi , and the selected coordinates for distinct labels are independent. For a fixed input x, define the labelled reconstruction Y = f(Tτ1 ,...,Tτk ) (xTτ1 , . . . , xTτk ) on the event E. On E c , define Y = 0, say. Since on E the selected coordinates have the same joint distribution as the original non-identically sampled tuple, we have P (|Y − f (x)| > α) ≤ α + η. Because Y ∈ [0, 1] and f (x) ∈ [0, 1], it follows that E|Y − f (x)| ≤ α + P(|Y − f (x)| > α) ≤ 2α + η. So far the reconstruction used the hidden labels I1 , . . . , Ir . The definition of identical sampling, however, only permits the test function to depend on the observed locations T1 , . . . , Tr and on the observed bits. We now remove the labels by conditional expectation. This posterior averaging is only part of the construction of the deterministic test functions; the eventual identical-sampling procedure itself samples only the locations from the single measure µ. For t = (t1 , . . . , tr ) ∈ [n]r , define a probability distribution on label tuples i = (i1 , . . . , ir ) ∈ [k]r by the posterior rule P(I1 = i1 , . . . , Ir = ir | T1 = t1 , . . . , Tr = tr ) =
r Y
µij (tj ) Pk ℓ=1 µℓ (tj ) j=1
whenever the denominators are nonzero. This is just Bayes’ formula with respect to the auxiliary hidden-label construction: the factor (1/k)µij (tj ) in the joint law is divided by the mixture mass P µ(tj ) = (1/k) kℓ=1 µℓ (tj ), so the factors 1/k cancel. If a denominator is zero, the value is irrelevant because such a location is never sampled from µ, and we may choose the conditional distribution arbitrarily. Given t ∈ [n]r and a = (a1 , . . . , ar ) ∈ {0, 1}r , define gt (a) to be the conditional expectation, over these posterior labels, of the labelled reconstruction described above, with the observed bits aj substituted for xtj . More explicitly, for each label tuple i, if every label 1, . . . , k occurs among i1 , . . . , ir , let τℓ (i) be the first index j with ij = ℓ, and set Yi (t, a) = f(tτ (i) ,...,tτ (i) ) (aτ1 (i) , . . . , aτk (i) ). 1
k
If not every label occurs, set Yi (t, a) = 0. Then define gt (a) = E YI (t, a) | T = t . 14
This is a deterministic function gt : {0, 1}r → [0, 1]. For the actual input x, the random variable gT (xT1 , . . . , xTr ) is exactly E(Y | T1 , . . . , Tr , xT1 , . . . , xTr ). Therefore, by Jensen’s inequality, |gT (xT1 , . . . , xTr ) − f (x)| = |E(Y − f (x) | T1 , . . . , Tr , xT1 , . . . , xTr )| ≤ E (|Y − f (x)| | T1 , . . . , Tr , xT1 , . . . , xTr ) . Taking expectations gives E |gT (xT1 , . . . , xTr ) − f (x)| ≤ E|Y − f (x)| ≤ 2α + η. By Markov’s inequality, P (|gT (xT1 , . . . , xTr ) − f (x)| > ε) ≤ With our choices α=
ε2 , 4
η=
2α + η . ε
ε2 , 2
we have 2α + η = ε2 . Hence P (|gT (xT1 , . . . , xTr ) − f (x)| > ε) ≤ ε. n This holds for every x ∈ {0, 1} . Therefore f is identically sampled (r, ε)-holographic with identical sampling from the single measure µ.
□ Acknowledgements
The author acknowledges the use of ChatGPT as a writing aid during the preparation of this manuscript, specifically for improving grammar, style, and exposition. All mathematical ideas, statements, and proofs were developed by the author. This research was supported by the NKFIH excellence 154126 grant. References [1] G. Cybenko, Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems 2 (1989), no. 4, 303–314. [2] A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175–220. [3] W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. 166 (2007), 897–946. [4] K. Hornik, Approximation capabilities of multilayer feedforward networks, Neural Networks 4 (1991), no. 2, 251–257. [5] Y. Kohayakawa, B. Nagle, V. Rödl, M. Schacht and J. Skokan, The hypergraph regularity method and its applications, Proc. Natl. Acad. Sci. USA 102 (2005), no. 23, 8109–8113. [6] A. Pinkus, Approximation theory of the MLP model in neural networks, Acta Numerica 8 (1999), 143–195. [7] E. Szemerédi, Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes, Colloques Internationaux CNRS, No. 260, CNRS, Paris, 1978, pp. 399–401. [8] T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257–1280. [9] D. Yarotsky, Error bounds for approximations with deep ReLU networks, Neural Networks 94 (2017), 103–114. Rényi Institute of Mathematics, Budapest, Hungary Email address: [email protected] 15