Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations Shijun Zhang

shijun.zhang@polyu.edu.hk

Department of Applied Mathematics Hong Kong Polytechnic University

arXiv:2608.31157v1 [cs.LG] 31 Aug 2026

Abstract Many parameter-efficient methods generate the parameters of a large neural network from a low-dimensional latent representation. Given an architecture Φ with PΦ parameter slots, we write θf = G(ξf ), where G : RM → RPΦ is a parameter generator and ξf ∈ RM is a latent representation of the target function f . The architecture Φ and the generator G are shared across the entire target class, while each target f is represented by its own latent vector ξf , with ΦG(ξf ) approximating f . This framework encompasses hypernetworks, low-dimensional parameterizations, parameter-efficient adaptation, and model compression. Understanding the tradeoff between the latent dimension M and the network budget P is therefore fundamental to characterizing the expressive efficiency of these methods. We study this tradeoff for affine generators and fully connected ReLU architectures. More precisely, optimizing jointly over architectures Φ satisfying PΦ ≤ P and affine generators G : RM → RPΦ , we prove that the optimal worst-case uniform approximation error over the unit ball of α-Hölder functions on [0, 1]d , where 0 < α ≤ 1, has the sharp order
−α/d P min{M, P } . In particular, our result shows that even a fixed-dimensional latent space suffices to achieve vanishing approximation error as the network budget increases.

Keywords: affine latent parameterization, parameter-efficient model, ReLU network approximation, sharp minimax rate, pseudo-dimension

1

Introduction

Modern neural networks are often heavily overparameterized: the number of weights used at inference can far exceed the number of degrees of freedom needed to select a useful model for a particular task. If the full parameter vector can be generated from a much smaller latent vector, one can reduce the storage required for each task and the dimension of the optimization problem without shrinking the deployed architecture. This separation is especially natural when a single generator and network architecture are reused across many targets, tasks, or environments. A substantial body of empirical work indicates that this mechanism can be effective. Particularly direct examples include training in a fixed parameter subspace and reconstructing a full parameter vector from a seeded linear expansion (Li et al., 2018; Nooralinejad et al., 2023). Related methods based on weight tying, structured transforms, hypernetworks, and low-rank updates are reviewed in Section 2. Collectively, these studies suggest that the relevant complexity is not described by a single parameter count: one must distinguish the amount of target-dependent information from the size and complexity of the fixed mechanism that decodes that information. To formalize this separation, consider an architecture Φ with PΦ weight and bias slots and a parameter generator G : RM → RPΦ . The architecture and generator are fixed for an entire target class. For each target f , only a latent vector ξf ∈ RM is selected, and the resulting function is produced by   G Φ ξf ∈ RM 7−−−−→ θf = G(ξf ) ∈ RPΦ 7−−−−→ x 7→ Φθf (x) . 1

Here Φθf denotes the function realized by Φ with complete parameter vector θf , and x denotes its input. We call RM the latent parameter space and ξf the target-dependent latent vector. Because ξf is the only quantity chosen separately for each target, it is also the only targetdependent trainable vector in the model. Its M coordinates carry information about the target, whereas the PΦ slots determine the size of the deployed decoder. Counting only M ignores the decoding mechanism, while counting only PΦ treats all deployed parameters as if they varied independently with the target. A meaningful approximation theory must therefore account for both resources and keep their quantifiers separate. This accounting of two resources is meaningful only if the generator is restricted. If G is arbitrary and its complexity is not charged, then the latent dimension M alone imposes essentially no expressive constraint. Indeed, because R and RPΦ have the same cardinality, an unrestricted generator with M = 1 can be chosen to map onto the full parameter space. Its generated family then coincides with the family obtained by varying all PΦ network parameters independently. Continuity alone does not remove this degeneracy. A continuous surjection from R onto RPΦ can be formed, for example, by joining closed Peano curves whose images cover successively larger parameter cubes. When PΦ > 1, no such space-filling map can be locally Lipschitz, because the image of a locally Lipschitz map from R has Hausdorff dimension at most one. For a finite target collection, even smoothness is insufficient: coordinatewise Lagrange interpolation produces a polynomial curve through any prescribed finite set of realizing parameter vectors. Thus neither continuity for a generator shared across a class nor smoothness for a finite task collection makes the latent dimension alone a meaningful complexity measure. A theory of nonlinear generators must also control, for example, the description or parameter complexity of G, its computational size, regularity, stability, and the precision of the latent code. We therefore study the simplest structured specialization of this framework: an affine generator, G = A, A(ξ) = Aξ + a. (1)

Here A ∈ RPΦ ×M and a ∈ RPΦ are fixed across the target class. After the homogeneous b since A(ξ) = [A, a]ξ. b This model includes lifting ξb := (ξ, 1) ∈ RM +1 , the map is linear in ξ, training in a fixed subspace, fixed weight sharing, and affine expansions based on seeds or fixed transforms. Although hypernetworks, Mapping Networks, and many low-rank adaptation schemes are nonlinear in their latent variables, they motivate the same question concerning both budgets. The affine case is already nontrivial and imposes a transparent geometric restriction: all generated parameter vectors lie in a single affine subspace of dimension at most min{M, PΦ }. Any expressivity beyond this affine dimension must therefore be supplied by the fixed ReLU decoder. Throughout the paper, an affine latent parameterization means precisely the shared map in (1), which takes a latent vector to the complete parameter vector of the realized network. Figure 1 illustrates this setup. generated parameters

latent coordinates

ξf ∈ RM

M target-dependent scalars

realized function

A

θf = A(ξf )

Φ

fixed

∈ R PΦ

fixed

θf

PΦ weights and biases

x 7→ ΦA(ξf ) (x)

Figure 1: An affine latent parameterization. Only the M -dimensional latent vector ξf changes with the target. The shared affine map A generates all PΦ network parameters, and the shared architecture Φ realizes the approximation.

The closest predecessors in approximation theory treat the two endpoints of our resource model separately. Approximation results for very deep networks control the complete network size but allow every parameter to depend on the target (Shen et al., 2022d; Yarotsky, 2018). 2

At the opposite endpoint, intrinsic parameter approximation controls the number of scalars that depend on the target while allowing the fixed decoder to grow without an independent parameter budget; repeated composition of a shared ReLU block provides a complementary fixed-dimensional parameter-sharing construction (Shen et al., 2022b; Zhang et al., 2023). Neither endpoint simultaneously restricts the latent dimension and the number of generated parameter slots. Our goal is to connect these resource models and determine the sharp joint dependence on the two budgets. This leads to the central question: For a single affine latent parameterization shared by a whole function class, how does the optimal worst-case approximation error depend jointly on the latent dimension M and the budget P for all generated weight and bias slots? Our main result gives a sharp answer in both resources, uniformly over the target class. We fix the pair (Φ, A) before the target is selected, count every dense weight and bias slot of the generated network, and allow only the latent vector ξf to depend on f . For the unit ball of α-Hölder functions on [0, 1]d , where 0 < α ≤ 1, once P exceeds the explicit dimension-dependent threshold in Theorem 3.1 and min{M, P } ≥ 4, the optimal worst-case error is, up to constants depending only on d and α, [P min{M, P }]−α/d .

Thus, when M ≤ P , the two resources multiply and the rate is (P M )−α/d . When M ≥ P , the affine image is limited by the ambient parameter dimension, and the rate saturates at P −2α/d . The upper bound is achieved by fully connected ReLU networks whose width depends only on d and whose depth grows at most linearly with P . The matching lower bound holds for every admissible fully connected ReLU architecture with at most P parameter slots, without any further restriction on width or depth. Thus the result characterizes the best use of one affine latent space shared across the target class, rather than the performance of a particular construction. Figure 2 summarizes the two regimes. M M ≥P

M =P

rank saturates at P error P −2α/d

M ≤P

error (P M )−α/d

P

Figure 2: The sharp joint law in P and M in the nondegenerate regime of Theorem 3.1. For M ≤ P , the effective scale is P M ; in particular, each fixed M ≥ 4 yields the rate P −α/d . For M ≥ P , the affine image is limited by the ambient parameter dimension, and the rate saturates at P −2α/d .

The regime of fixed latent dimension is especially noteworthy. If M = M0 ≥ 4 is independent of P , then, whenever the hypotheses of Theorem 3.1 hold and P ≥ M0 , −α/d

[P min{M0 , P }]−α/d = M0

P −α/d .

Consequently, a constant number of target-dependent coordinates is sufficient for the worst-case error to converge algebraically to zero as the shared decoder grows. This decay is driven entirely by growth of the decoder budget, which is shared across targets, rather than by growth of the trainable dimension. Although this rate is slower than the saturated rate P −2α/d available when M ≥ P , it shows that a genuinely low-dimensional affine latent space can support substantial and provably optimal approximation power. The main contributions can be summarized as follows.

3

(i) We introduce a minimax formulation uniform over the target class in which the architecture and affine latent map are fixed before the target is selected, and the latent dimension M and the parameter budget P for the generated slots are accounted for separately. This formulation isolates target-dependent information from shared decoding complexity. (ii) We construct fully connected ReLU networks of fixed width depending only on the dimension. Under the stated nondegenerate conditions, these networks attain the rate [P min{M, P }]−α/d . The construction tracks the depth, every dense parameter slot, and all dimension-dependent constants. More generally, it yields a modulus-of-continuity estimate for arbitrary continuous targets and remains effective even when M is fixed. (iii) We prove a matching lower bound over all fully connected architectures with input dimension d and at most P dense parameter slots, without any additional width or depth restriction. The main ingredient is a pseudo-dimension estimate for ReLU networks with affine parameter tying, derived from affine rank reduction and polynomial sign pattern counting; a Hölder bump packing argument then converts this capacity bound into the matching approximation lower bound. The upper and lower bounds rely on complementary ingredients. The upper bound combines a serialized affine spline loader, fixed binary prefix extraction, a spatial address network, and median boundary repair. For the converse, substituting θ = A(ξ) reduces the effective number of variables to the rank of A, which is at most min{M, PΦ }. A layerwise semialgebraic argument then bounds the pseudo-dimension, and localized Hölder bumps convert this capacity bound into the matching approximation lower bound. The constructive uniform upper bound also implies the same estimate in Lp ([0, 1]d ) for every 1 ≤ p < ∞. The matching lower bound proved here is for the uniform norm. The stated rate relies on exact real arithmetic: a latent coordinate may contain a long binary stream, and the selection f 7→ ξf is discontinuous. The theorem therefore concerns representation power rather than numerical stability or optimization; Section 2.6 discusses this scope in detail. The remainder of the paper is organized as follows. Section 2 reviews empirical evidence for affine and nonlinear latent parameterizations, relates the problem to existing approximation and capacity theory, and explains the interpretation and limitations of the joint law in P and M . Section 3 introduces the network model, the parameter budget classes, and the main upper and lower bounds. Section 4 gives the constructive proof of the upper bound for continuous functions, from the fixed-width modules through the final choice of the integer budgets. Section 5 proves the matching Hölder lower bound through pseudo-dimension and bump packing arguments. Finally, Section 6 summarizes the conclusions and discusses directions for further work.

2

Related work, interpretation, and scope

This section reviews the most closely related empirical and theoretical work, then interprets the joint law in P and M and clarifies its scope. Sections 2.1 and 2.2 distinguish affine parameterizations from their nonlinear relatives. Section 2.3 places the result within approximation and capacity theory, while Sections 2.4 through 2.6 discuss resource accounting, optimization geometry, and the assumptions on exact real arithmetic. None of this background is used as an assumption in the proofs.

2.1

Affine latent parameterizations: parameter prediction, weight tying, and subspace training

The examples in this subsection fall into three broad categories: parameter prediction and weight tying, training in a fixed linear subspace, and training in a subspace learned jointly for a single task. For our theorem, the relevant distinction is whether the same affine map is fixed before the target function is selected. 4

Parameter prediction and weight tying An early parameter-prediction study learned a small subset of the weights and reconstructed the remainder from linear predictors; in its best reported case, more than 95% of the weights were predicted without loss of accuracy (Denil et al., 2013). This finding supports substantial redundancy in trained weight tensors, but the predictors and selected coordinates are taskdependent, and the work gives no uniform approximation guarantee over a function class. HashedNets impose a more rigid form of sharing: a signed hash maps many virtual connections to a smaller collection of trainable scalars (Chen et al., 2015). Once the virtual weights are enumerated, this construction is exactly a sparse affine map, each of whose rows contains one signed nonzero entry. Existing theory addresses approximation by random linear sketches on well-conditioned low-dimensional input manifolds and local recovery for a one-layer hashed model (Lin et al., 2019); it does not give the Hölder-class joint minimax rate considered here. Frequency-sensitive hashing first transforms convolutional filters and then shares their spectral coefficients (Chen et al., 2016). Thus it is close to the present affine viewpoint, but its objective is empirical compression of specific convolutional models rather than a worst-case rate for a prescribed function class. Beyond direct prediction and tying, structured expansions can reduce both storage and multiplication cost. Fastfood supplies a fixed structured random transform built from diagonal matrices, permutations, and Hadamard transforms (Le et al., 2013). Adaptive Deep Fried layers instead learn products of several diagonal factors and are generally nonlinear jointly in those factors (Yang et al., 2015). Discrete cosine transform (DCT) layers with sparse corrections add a fixed dense transform to a very sparse trainable component and retain useful accuracy even at extreme trainable sparsities (Price and Tanner, 2021). FourierFT reconstructs a dense update from selected Fourier coefficients (Gao et al., 2024). Once the transform and coefficient locations are fixed, the latter two constructions are affine parameter maps. Their transforms, sparsity patterns, and statistical tasks are prescribed differently, however, and none proves a joint minimax law in the number of adjustable coefficients and the number of realized network slots. Fixed and learned subspaces Training in fixed random subspaces optimizes θ = Wsub ξ +bsub and defines the empirical intrinsic dimension as the smallest code dimension that attains a chosen fraction of the performance of the full model (Li et al., 2018). Experiments show that networks with hundreds of thousands of weights can sometimes be optimized through only hundreds or thousands of coordinates. Subsequent experiments demonstrate that a single reused random basis can impair optimization, while redrawing the basis at every step and using separate projections for different modules can improve both accuracy and speed (Gressmann et al., 2020). Because the basis changes during training, this method does not use a single fixed map A and therefore lies outside our minimax model. Structured Fastfood projections for fine-tuning language models also reveal small intrinsic dimensions specific to each task and suggest that larger pretrained models can require fewer effective coordinates (Aghajanyan etP al., 2021). PRANC uses the exact linear expansion θ = M m=1 ξm θm , with basis vectors regenerated from pseudorandom seeds (Nooralinejad et al., 2023). It is therefore one of the closest empirical instances of the present algebraic model. Balanced multicomponent and multilayer networks reduce the number of trainable parameters through a structured component decomposition (Zhang et al., 2025). Their Fourier variant represents each component as a trainable linear combination of fixed random sine bases within a low-rank architecture (Zhang et al., 2026). These models further illustrate that the degrees of freedom depending on the target can be much fewer than the parameters in the realized network, but they do not establish a minimax law over an entire function class in the two budgets (M, P ). 5

Other coordinate-restricted approaches include FreezeNet and training restricted to BatchNorm parameters (Frankle et al., 2021; Wimmer et al., 2020); these methods correspond to coordinate projections rather than designed dense affine maps. Sparsity inducing training with ℓ1 regularization for convolutional networks addresses another form of parameter reduction (He et al., 2020). In that setting, however, the active sparse structure is learned for the task rather than generated by one affine map fixed across a target class. A complementary line of expressivity theory shows that training only normalization scales and biases in a sufficiently large random host can reconstruct smaller target networks, with extensions to convolutional and residual architectures (Burkholz, 2024; Giannou et al., 2023). Those theorems exploit the special normalization architecture and address target-network reconstruction rather than uniform approximation of a Hölder ball by one prescribed affine map. Learned solution subspaces provide a further comparison. Lines, curves, and simplices of highly accurate solutions show that useful low-dimensional regions can be optimized jointly with a target network (Wortsman et al., 2021). In that setting, however, the endpoints defining the subspace are themselves trainable objects specific to the task, whereas our affine image is fixed before any target in the Hölder ball is selected. Taken together, these works address task performance, optimization, or reconstruction of prescribed target networks; they do not characterize the worst-case approximation error jointly in (M, P ).

2.2

Nonlinear generators and parameter-efficient adaptation

We now turn from affine maps to generators that are typically nonlinear. The general mechanism remains G : RM → RPΦ , θ = G(ξ), but G need not be affine. Hypernetworks, Mapping Networks, and most low-rank adaptation methods therefore motivate the question of how approximation depends on both budgets, although they do not belong to the affine class studied here. As explained in the Introduction, a sharp minimax theory for such models would require a separate complexity or regularity budget for G; otherwise M alone does not control the generated family. Hypernetworks generate the weights of a primary network from conditioning information or a compact code and have been applied to recurrent and image models (Ha et al., 2017). Theoretical work compares their parameter complexity with that of direct embedding models and identifies settings in which modular weight generation is advantageous (Galanti and Wolf, 2020). Infinite-width analysis shows that widening only the generator does not automatically produce benign kernel dynamics, whereas a joint infinite-width limit yields an explicit hyperkernel (Littwin et al., 2020). Hypernetworks conditioned on graphs can predict millions of weights for architectures unseen during training in a single forward pass (Knyazev et al., 2021). These works study learned nonlinear generators, conditional families, or optimization dynamics. The generator may be frozen after training, but its map G remains nonlinear and is learned for a particular task. Mapping Networks provide a particularly direct recent example of a nonlinear parameter generator (Sen and Mukherjee, 2026). A compact trainable latent vector modulates nontrainable, orthogonally initialized base matrices inside the mapping machinery. Composing these modulated layers produces a nonlinear map from the latent vector to all parameters of a target model. The reported experiments cover image classification, detection of manipulated faces, semantic segmentation, recurrent forecasting, and adaptation of a pretrained model. For one reported classifier, full training uses 537,994 parameters, while latent variants use only a few thousand coordinates and obtain competitive or improved accuracy. In the reported Cityscapes experiment, a target model with 1,734,803 parameters is driven by roughly eight thousand latent coordinates: pixel accuracy increases from 93.21% to 97.92%, while mean intersection-over-union changes from 0.4957 to 0.4623 (and to 0.4823 for the layerwise variant) (Sen and Mukherjee, 2026). These 6

results directly motivate the question involving both budgets, but their generator is nonlinear. The existence theorem based on manifolds, the local solvability result, and the experiments do not establish a worst-case approximation rate over a function class in (M, P ). A closely related nonlinear compression model uses a frozen random generator to constrain the complete parameter vector to a prescribed low-dimensional nonlinear manifold (Thrash et al., 2025). Its experiments support the broader G(ξ) framework, but its generator is nonlinear and random, and its analysis does not establish the class-wide affine minimax law considered here. Low-rank adaptation provides another important class of nonlinear parameterizations. LoRA represents an update as a product of two thin matrices (Hu et al., 2022). VeRA, NOLA, and RandLoRA further reuse fixed random matrices or random bases and train scaling or combination coefficients (Albert et al., 2025; Koohpayegani et al., 2024; Kopiczko et al., 2024). Ordinary two-factor LoRA is nonlinear jointly in its two trainable factors. Even when each NOLA factor is a linear combination of fixed bases, multiplying the two factors again makes the complete update nonlinear in the combined code. A variant in which one factor is fixed, or a direct linear expansion of the complete update in a fixed basis, would instead define an affine map from RM to RPΦ . Kernel analyses explain why low-dimensional update subspaces can preserve fine-tuning dynamics in suitable regimes (Malladi et al., 2023). Separately, theoretical work characterizes reconstruction of target networks by low-rank updates and studies the landscape in neural tangent and local Polyak–Lojasiewicz regimes (Jang et al., 2024; Liu et al., 2025; Zeng and Lee, 2024). These results depend on pretrained weights, low-rank factorization, or local optimization assumptions; they do not yield the global function class rate proved below. Gradient low-rank projection provides a useful contrast: it compresses gradients and optimizer state while retaining full-rank trainable weights (Zhao et al., 2024). It is therefore an optimizationmemory method rather than a low-dimensional parameter map G : RM → RPΦ .

2.3

Approximation theory, coding, and capacity

Three theoretical viewpoints organize the comparison: exact codes with an unbudgeted decoder, networks whose complete parameter vector may depend on the target, and capacity bounds based on polynomial sign patterns. Our theorem draws on all three while budgeting both the code and the decoder. Classical universal approximation theorems establish density on compact sets (Cybenko, 1989; Hornik, 1991; Hornik et al., 1989), while quantitative approximation theory relates the error to width, depth, smoothness, and the total number of network parameters (Yarotsky, 2017, 2018). Related developments include sparse-network and Sobolev-norm estimates (Bölcskei et al., 2019; Chui et al., 2018; Gühring et al., 2020; Petersen and Voigtlaender, 2018), approximation rates for broad classes of activation functions (Siegel and Xu, 2020), and high-order rates for shallow networks (Siegel and Xu, 2022). Recent work gives nearly optimal rates for shallow ReLUk networks on Sobolev spaces through Radon-transform techniques (Mao et al., 2026). Approximation spaces generated by deep networks are characterized in (Gribonval et al., 2022), and further quantitative constructions appear in (Lu et al., 2021; Shen et al., 2019, 2020, 2022d). A closely related approximation result separates parameters that depend on the target from parameters fixed for an entire function class (Shen et al., 2022b, Theorem 2.2 and the discussion immediately following it). For a target on [0, 1]d with Lipschitz constant √ λ, it constructs a ReLU network with n + 2 intrinsic parameters and uniform error at most 5λ d2−n , and it extends the construction to general continuous functions. The decoder size is allowed to grow as required and is not independently budgeted. The present problem asks how that exponential dependence on the code length changes once the decoder is also subject to the budget P . Repeated composition of a single ReLU block of fixed size gives a complementary form of parameter sharing (Zhang et al., 2023). After the composition is unrolled, reuse of the same block parameters becomes an affine tying map from a fixed number of independent coefficients to a number of network slots proportional to the number of repetitions. The resulting O(r−1/d ) error for Lipschitz targets is 7

consistent with the fixed M regime here, but that work does not determine the joint dependence on arbitrary (M, P ) or prove a matching lower bound. At the opposite endpoint, approximation theory for very deep networks with joint width and depth budgets controls the entire network size while allowing every parameter to depend on the target (Lu et al., 2021; Shen et al., 2020, 2022d; Yarotsky, 2018; Yarotsky and Zhevnerchuk, 2020). The joint law in this paper interpolates between these two resource models. Qualitative bounded-width universality also shows that width can be bounded solely in terms of the input dimension when depth is allowed to grow (Lu et al., 2017). Such a theorem neither requires the parameter vector to lie in one fixed affine image nor quantifies the joint code and slot budgets; those are the constraints responsible for the rate studied here. Other constructions of fixed width use depth as a progressive refinement mechanism. Multigrade ReLU networks successively reduce the residual (Zhang et al., 2026b), while shared architectures with intermediate readouts achieve geometrically finer layerwise approximation scales (Zhang et al., 2026a). These results clarify the approximation role of depth, but they do not impose the affine latent budget studied here. Another line interprets deep architectures through dynamical systems and derives approximation results from flows, interpolation, and controllability (Cheng et al., 2025; Cheng et al., 2026; E, 2017; Li et al., 2023). This viewpoint has also been developed for invariant target classes (Li et al., 2022). A complementary computability result constructs a single fixed narrow recurrent ReLU network that receives an encoding of a computable target function as part of its input and approximates it after a controlled number of recurrent iterations (Bournez et al., 2025). That result emphasizes a universal decoder and relates its iteration count to computational complexity. Here, by contrast, the code does not enter as an ordinary network input: it affinely generates the weights and biases of a finite feedforward architecture, and both the code dimension M and the resulting dense parameter count P are optimized explicitly. Random feature approximation provides another relevant affine special case: the features are fixed and only the output coefficients vary. Quantitative results are available for random ReLU features, random neural networks and reservoirs, and networks with sampled weights (Bolager et al., 2023; Gonon et al., 2023; Hsu et al., 2021). The essential differences are that those results typically average over a random draw, use L2 target classes or classes of Barron type, and do not exploit a decoder of length proportional to P to obtain a joint P M law. Lottery ticket results instead encode the target through a discrete pruning mask (Malach et al., 2020; Pensia et al., 2020); their information model is combinatorial rather than based on an affine code in exact real arithmetic. More broadly, Barron spaces and function spaces induced by flows, together with population risk estimates for networks with two layers, provide a related function space perspective (E and Wojtowytsch, 2022; E et al., 2019; E et al., 2022). The theory of nonlinear widths distinguishes arbitrary, continuous, and stable maps from targets to parameters (Cohen et al., 2022; Daubechies et al., 2022; DeVore, 1998; DeVore et al., 1989). Very deep ReLU networks can exceed stable nonlinear width rates by using discontinuous encodings of high precision (Shen et al., 2022d; Yarotsky, 2018; Yarotsky and Zhevnerchuk, 2020). For shallow neural-network variation spaces, sharp approximation rates, metric entropy bounds, and n-width estimates provide a complementary complexity-theoretic perspective (Siegel and Xu, 2024). The upper construction below lies in this exact real regime. For the lower bound, classical counting of polynomial sign patterns for real parameters, together with later nearly tight bounds for piecewise linear networks, provides the relevant capacity tools (Anthony and Bartlett, 1999; Bartlett et al., 1998, 2019; Goldberg and Jerrum, 1995; Warren, 1968). We adapt these arguments to affine parameter tying, so the effective variable count is rank(A) rather than the ambient number PΦ of parameter slots.

8

2.4

Resource accounting and endpoint regimes

Having situated the theorem relative to the most closely related models and theoretical results, we now interpret its two resource budgets. In the nondegenerate regime covered by the main theorem, with 4 ≤ M ≤ P and P sufficiently large, the sharp Hölder rate is (P M )−α/d . The construction explains this product directly: a constant fraction of the M latent coordinates store independent streams of quantized function increments, while a fixed decoder of depth proportional to P reads a number of digits proportional to P from each stream. Consequently, it reconstructs a number of grid values proportional to P M . The result also connects two established endpoint theories. When M is comparable to P , the rate is P −2α/d , matching the optimal rate for very deep networks of fixed width established in (Yarotsky, 2018, Theorems 1(a) and 2(b)) and (Shen et al., 2022d, Theorem 1.1). When M ≥ 4 is fixed and P is sufficiently large, the rate becomes P −α/d and quantifies how a latent vector of fixed dimension over the real numbers can be decoded by a shared decoder of increasing depth, in the spirit of (Shen et al., 2022b). Once M ≥ P , the affine rank is bounded by the ambient parameter dimension, which explains the saturation encoded by min{M, P }. The coefficients of the affine map are shared across the target class rather than selected separately for each target. In the absence of additional structure, A and a contain PΦ M + PΦ fixed scalar entries. These entries are not charged to the target-dependent trainable parameter count M , so the theorem does not automatically imply compression of total storage. Charging them, imposing sparsity or fast transforms, or regenerating them from short random seeds would define different resource models, as in several empirical constructions discussed above. A recent preprint studies a seeded deployment model with finite bit precision in which the stored artifact consists of a short integer seed and a quantized latent vector; the seed regenerates the fixed basis and initialization center (Dhayalkar, 2026). Its resource accounting and experiments complement the minimax theorem over exact real parameters here, but it does not provide a matching approximation law over a function class. Within the deployed network, however, every weight and bias slot, including slots fixed at zero, is counted in PΦ .

2.5

Optimization geometry and conditioning

Beyond resource accounting, the affine map also induces a particular optimization geometry. The approximation problem itself does not prescribe an algorithm for finding ξf , but the affine parameterization makes this geometry explicit. Let
e A(ξ) = Aξ + a and L(ξ) := L A(ξ) , where L(θ) is a twice continuously differentiable loss in the full parameter space and ⊤ denotes transpose. The chain rule gives

e e ∇2ξ L(ξ) ∇ξ L(ξ) = A⊤ ∇θ L A(ξ) , = A⊤ ∇2θ L A(ξ) A. The pullback Hessian is singular whenever rA := rank(A) < M ; hence its ordinary condition number is not meaningful until redundant latent directions are removed. If rA = 0, the affine family contains one parameter vector and there is no latent condition number. Otherwise, choose an orthonormal basis for ker(A)⊥ and place its vectors in the columns of VA ∈ RM ×rA . Define eff := V ⊤ ξ and the effective matrix Aeff := AV . Because the nonredundant coordinates ξA A A A ⊤ eff . Thus θ = Aeff ξ eff + a, and the Euclidean metric ξ − VA VA ξ ∈ ker(A), one has Aξ = Aeff ξ A A A A eff is inherited from the nonredundant directions of the original latent vector. For a local on ξA quadratic model with Hessian H, define eff ⊤ eff HA := (Aeff A ) HAA .

9

When this matrix is positive definite, the local condition number in these effective coordinates is eff cond2 (HA ) :=

eff ) λmax (HA . eff ) λmin (HA

Because a nonorthogonal change of coordinates within the same affine image can alter this condition number, the coordinate system must be specified. Thus dimensional reduction alone neither guarantees nor precludes better conditioning. This conclusion is consistent with empirical comparisons of random bases, general analyses of reparameterization, and studies of low-rank optimization landscapes (Gressmann et al., 2020; Kristiadi et al., 2023; Liu et al., 2025). The reparameterization result in (Kristiadi et al., 2023) concerns invertible coordinate changes; by contrast, a rank-deficient A also restricts the model to a proper affine subspace. Constructing an affine map that is simultaneously optimal for approximation and well conditioned for a prescribed loss is a separate problem.

2.6

Exact real arithmetic, discontinuity, and scope

We next turn to a separate limitation of the upper bound: its use of exact real arithmetic. The construction stores finite but increasingly long binary streams in exact real coordinates. Their useful bit length grows with the depth and hence with P . For a stream of D decoded bits, the fixed prefix gate used later contains a coefficient of size 2D+1 , so the dynamic range of some decoder weights shared across targets also grows exponentially with the number of decoded bits. The selection map f 7→ ξf uses quantization and is discontinuous. These features are standard in the exact real regime with superconvergent approximation rates (Shen et al., 2020, 2021a,b, 2022b,d; Wang et al., 2025; Yarotsky, 2018; Zhang et al., 2023, 2026). If every latent coordinate were restricted to b bits, only 2M b codes would be available, and a standard Hölder packing or entropy argument would impose an additional information obstruction of order (M b)−α/d . A recent bit-complexity framework likewise emphasizes that parameter count and finite-precision information complexity are distinct resource measures (Mao and Xu, 2026). The main theorem therefore concerns expressivity over real parameters, not bit complexity, stability under perturbations or noise, or the behavior of gradient descent. Weight constraints define another complementary resource model: upper and lower approximation bounds are known for norm-constrained ReLU networks on smooth function classes (Jiao et al., 2023b). Here we count all weight and bias slots but impose no uniform bound on their magnitudes. These comparisons are not used in any proof below. A second scope restriction is architectural: we consider only fully connected ReLU networks. Both the architectural class and the activation are substantive restrictions. Approximation and universality for convolutional architectures have their own corresponding theories (Bao et al., 2023; Lin et al., 2022; Zhou, 2020). The role of the activation is also reflected in general activation-dependent approximation rates (Siegel and Xu, 2020), activation-dependent spectral bias (Cao et al., 2021; Hong et al., 2022), and constructions combining ReLU, sine, and exponential activations on Hölder classes (Jiao et al., 2023a). Richer nested ReLU architectures can obey different laws relating the parameter count to the error (Shen et al., 2022c). With specially designed continuous activations, even networks of fixed size can be universal (Shen et al., 2022a), while transfer results extend many ReLU approximation constructions to broad activation families (Zhang et al., 2024). None of these results gives the joint affine minimax law studied here. Finally, the constructive theorem uses width depending only on the dimension, while its depth grows with P and supplies sequential decoding time. The lower bound allows every fully connected architecture with at most P dense parameter slots under the convention of Section 3.1. No theorem is claimed for upper bounds at fixed depth, convolutional architectures, or nonlinear generators. The upper construction applies to every continuous function on the cube, while 10

matching optimality is proved for the normalized Hölder class in the uniform norm. The affine map is also chosen constructively; the result does not assert that a random affine subspace attains the same worst-case rate. In summary, the literature reviewed above motivates the general parameter map G, while the remainder of the paper isolates a precise setting: one affine latent parameterization shared across the target class, latent vectors over exact real numbers, and two independently charged budgets (M, P ). The minimax class imposes no explicit width bound, whereas the optimal upper construction has width depending only on d.

3

Problem formulation and main results

With the setting and scope now fixed, we formulate the precise minimax problem. Section 3.1 introduces the notation, architecture classes, affine latent families, and target class; Section 3.2 states the matching upper and lower bounds.

3.1

Notation and model

Let R and N+ denote the sets of real numbers and positive integers, respectively. For any set X, the notation RX denotes the set of functions from X to R. If m ∈ N+ and X ⊆ Rm has the subspace topology inherited from Rm , then C(X) denotes the space of real-valued continuous functions on X. Bold lowercase and uppercase letters denote column vectors and matrices, respectively, and ⊤ denotes transpose. Thus (a1 , . . . , aq ) is a column vector, whereas [a1 , . . . , aq ] is a row vector. The symbol 0 denotes a zero vector or matrix, with its dimension inferred from context. For q ∈ N+ , Iq is the q × q identity matrix, and ej is the jth coordinate vector whenever its ambient dimension is clear. We use ker(A), Range(A), and rank(A) for the kernel, range, and rank of a matrix. The expression diag(A1 , . . . , AJ ) denotes the corresponding block diagonal matrix, and vec denotes vectorization in the fixed order specified below. Throughout the paper, ϱ(t) := max{t, 0} denotes the ReLU activation and is applied componentwise to vectors. For t ∈ R, set t+ := max{t, 0} = ϱ(t),

t− := max{−t, 0} = ϱ(−t),

t = t+ − t − .

For z = (z1 , . . . , zm ) ∈ Rm , the symbols ∥z∥2 and ∥z∥∞ := max1≤j≤m |zj | denote the Euclidean and maximum norms, respectively. For 1 ≤ p < ∞ and f : [0, 1]d → R, write ∥f ∥Lp ([0,1]d ) :=

Z [0,1]d

1/p |f (x)|p dx ,

∥f ∥L∞ ([0,1]d ) := sup |f (x)|. x∈[0,1]d

The notation |S| denotes the cardinality of a finite set S. We use 1 generically for indicators: 1{E} is the indicator of a statement E, whereas 1S is the indicator function of a set S. The notation med(a, b, c) denotes the median of a, b, c ∈ R. We write ⌊t⌋ for the floor of t; log and ln denote natural logarithms, log2 denotes the logarithm to base two, and e is Euler’s number. For positive quantities a and b, we write a ≍Λ b if there are constants cΛ , CΛ > 0, depending only on the listed parameters Λ, such that cΛ b ≤ a ≤ CΛ b. For a binary function class C, VCdim(C) denotes its VC dimension. For a real-valued class F, Pdim(F) denotes its pseudo-dimension, while VCdim(F) denotes the VC dimension of the class obtained by thresholding F at zero. Formal definitions are given in Section 5.1. For f ∈ C([0, 1]d ), its modulus of continuity is n o ωf (r) := sup |f (x) − f (y)| : x, y ∈ [0, 1]d , ∥x − y∥2 ≤ r , r ≥ 0. (2) 11

In particular, ωf is nondecreasing, ωf (0) = 0, and ωf (r) → 0 as r ↓ 0. It also satisfies ωf (Kr) ≤ Kωf (r) for every r ≥ 0 and K ∈ N+ : subdivide the line segment joining any two admissible points into K equal pieces and use the triangle inequality. Network architectures A fully connected ReLU architecture is denoted by Φ. Its input dimension dΦ is determined by the target function, and its output dimension is one throughout this paper; both dimensions are therefore suppressed in the notation for architecture classes. Thus, when these classes are used for targets on [0, 1]d , the input dimension is understood to be d. Let LΦ ∈ N+ be the number of hidden layers and let n1 , . . . , nLΦ ∈ N+ be their widths. Set n0 = dΦ and nLΦ +1 = 1, and define depth(Φ) := LΦ ,

width(Φ) := max nℓ . 1≤ℓ≤LΦ

Thus every architecture admitted by our convention has at least one hidden ReLU unit. An affine network with no hidden layer could be added as a degenerate case. Doing so would not weaken the lower bound, but excluding it keeps the layer notation uniform throughout the constructive proof. Indeed, after rank reduction, its subgraph predicate is one polynomial inequality of degree one in the effective coordinates, so Proposition 5.5 gives the same capacity estimate under the parameter budget. For N, L ∈ N+ , let Arch(N, L) := {Φ : width(Φ) ≤ N, depth(Φ) ≤ L} . For ℓ = 1, . . . , LΦ + 1, let Aℓ (z) := Wℓ z + bℓ denote the affine map associated with layer ℓ. Vectorizing and concatenating all weight matrices and bias vectors in their natural order yields
θ := vec W1 , b1 , . . . , WLΦ +1 , bLΦ +1 ∈ RPΦ . The function realized by Φ with parameters θ is Φθ := ALΦ +1 ◦ ϱ ◦ ALΦ ◦ · · · ◦ ϱ ◦ A1 ∈ C(RdΦ ). The hidden-unit index set and the number of hidden units are UΦ := {(ℓ, j) : 1 ≤ ℓ ≤ LΦ , 1 ≤ j ≤ nℓ } ,

UΦ := |UΦ | =

LΦ X

nℓ .

(3)

ℓ=1

The total number of scalar weight and bias entries is PΦ :=

LX Φ +1

nℓ (nℓ−1 + 1).

(4)

ℓ=1

After fixing an ordering of these entries, a parameter assignment is identified with θ ∈ RPΦ . All dense weight and bias entries are counted, including those assigned a fixed value, possibly zero. For P ∈ N+ , define Archpar (P ) := {Φ : PΦ ≤ P } . No separate width or depth restriction is imposed in Archpar (P ). Figure 3 summarizes these architectural conventions.

12

LΦ ≤ L hidden layers A1

A2

ALΦ

A3

ALΦ +1

x1

···

x2 n1 ≤ N

n2 ≤ N

Φθ (x1 , x2 )

nLΦ −1 ≤ N

n3 ≤ N

nLΦ ≤ N

Figure 3: An architecture Φ ∈ Arch(N, L). The widths of hidden layers may be smaller than N , and all dense weight and bias entries are counted in PΦ .

Affine latent parameterizations For M, Q ∈ N+ , let  Aff(M, Q) := A : RM → RQ : A(ξ) = Aξ + a, A ∈ RQ×M , a ∈ RQ . The convention M ∈ N+ excludes the degenerate zero-dimensional latent space, whose affine image would consist of a single parameter vector. For an architecture Φ and a map A ∈ Aff(M, PΦ ), the network parameters are generated by θ = A(ξ) = Aξ + a,

ξ ∈ RM .

Here RM is the latent parameter space, while A and a are fixed over the target class. The corresponding realized family is   FΦ,A := ΦA(ξ) : ξ ∈ RM = Φθ : θ ∈ A(RM ) ⊆ C(RdΦ ). (5) Its effective affine dimension is rA := rank(A) ≤ min{M, PΦ }.

(6)

The pair (Φ, A) is chosen independently of the target; only the latent vector ξ may depend on the target function. Target class and minimax error For 0 < α ≤ 1, define the unit Hölder ball n o Hdα := f ∈ C([0, 1]d ) : ∥f ∥L∞ ([0,1]d ) ≤ 1, |f (x) − f (y)| ≤ ∥x − y∥α2 for all x, y ∈ [0, 1]d . We use the following dimension-dependent constants throughout:
Nd := 3d max{20d, 96} + 4 ,

(7)

Bd := (48 + 2d)Nd (Nd + 1) + Nd (d + 2) + 1,

(8)

Pd⋆ := 22d+2 Bd ,

(9)

Cd := 4 · 8

√ 1/d

2/d

dBd .

(10)

All four constants depend only on d. For P ∈ N+ , we also use the depth budget Ld,P := 18⌊P/Bd ⌋ + 30 + 2d. With this notation in place, for an admissible pair (Φ, A) with dΦ = d, define Rα,d (Φ, A) := sup inf

f ∈Hdα ξ∈RM

13

f − ΦA(ξ) L∞ ([0,1]d ) .

(11)

The affine latent minimax error under a parameter budget P is Eα,d (M, P ) :=

inf

inf

Φ∈Archpar (P ) A∈Aff(M,PΦ ) dΦ =d

Rα,d (Φ, A).

(12)

Thus the architecture and affine map are chosen before the target, whereas the latent vector is chosen after the target is given. In (12), the infimum is restricted to architectures with input dimension d and scalar output, as it is whenever an architecture class is used for targets on [0, 1]d . This convention keeps the input dimension determined by the target domain out of the architecture notation while making every difference f − Φθ well defined. As usual, inf ∅ := +∞.

3.2

Main results

With the minimax problem now defined, we state the three main results. Theorem 3.1 gives a modulus-of-continuity bound for every continuous target, Corollary 3.2 specializes it to the Hölder class, and Theorem 3.3 proves the matching lower bound. Consequently, ( (P M )−α/d , M ≤ P, Eα,d (M, P ) ≍α,d P −2α/d , M ≥ P, whenever P ≥ Pd⋆ and min{M, P } ≥ 4. The regime M ≤ P is particularly relevant to parameterefficient approximation: M may remain fixed while the error still decreases algebraically as P grows. Recall the named constants Nd , Bd , Pd⋆ , Cd in (7), (8), (9), and (10), together with the depth budget Ld,P defined in Section 3.1. They are conservative by design so that every dense parameter slot and every estimate involving a floor can be checked without asymptotic notation. We do not optimize their numerical values. Theorem 3.1 (Upper bound for continuous functions). Let d, M, P ∈ N+ satisfy min{M, P } ≥ 4 and P ≥ Pd⋆ . There exist an architecture Φ ∈ Archpar (P ) ∩ Arch(Nd , Ld,P ) with input dimension d and an affine map A ∈ Aff(M, PΦ ), both depending only on (d, M, P ) and not on the target, with the following property. For every f ∈ C([0, 1]d ), there is a target-dependent latent vector ξf ∈ RM such that, with θf := A(ξf ), f − Φ θf

L∞ ([0,1]d )

≤ (d + 2)ωf Cd [P min{M, P }]−1/d .

(13)

Equivalently, every entry of every layer matrix Wℓ and bias vector bℓ is an affine function of ξf . Every dense weight and bias entry is counted in PΦ , including entries assigned the value zero. Theorem 3.1 is proved in Section 4. That section develops the fixed width modules, assembles the construction under integer resources, and then selects these resources in terms of (M, P ). Applying the theorem to Hölder functions gives the following consequence. Corollary 3.2 (Upper bound for Hölder functions). Let d, M, P ∈ N+ satisfy the assumptions of Theorem 3.1, and let (Φ, A) be the single pair supplied by that theorem. Let 0 < α ≤ 1 and λ ≥ 0. If f ∈ C([0, 1]d ) satisfies |f (x) − f (y)| ≤ λ∥x − y∥α2 for all x, y ∈ [0, 1]d , then inf

θ∈A(RM )

∥f − Φθ ∥L∞ ([0,1]d ) ≤ C α,d λ[P min{M, P }]−α/d ,

where C α,d := (d + 2)Cdα . In particular, Eα,d (M, P ) ≤ C α,d [P min{M, P }]−α/d . The same approximants also satisfy this bound in Lp ([0, 1]d ) for every 1 ≤ p < ∞. 14

(14)

Proof. The Hölder condition gives ωf (r) ≤ λrα . Substitution into (13) yields f − Φ θf

L∞ ([0,1]d )

≤ C α,d λ[P min{M, P }]−α/d .

Since θf = A(ξf ), it is admissible for the infimum over A(RM ). For f ∈ Hdα , the estimate applies with λ = 1. Taking the supremum over Hdα and then the two outer infima in the definition of Eα,d (M, P ) proves (14). Finally, since [0, 1]d has measure one, ∥g∥Lp ([0,1]d ) ≤ ∥g∥L∞ ([0,1]d ) for every bounded measurable g. The upper bound is formulated for every continuous target because the construction naturally adapts to the modulus of continuity of the individual function. To determine whether its dependence on (M, P ) can be improved, we consider the normalized Hölder class Hdα . The following lower bound applies uniformly over all admissible architectures and affine parameterizations. Theorem 3.3 (Lower bound for Hölder functions). Let d ∈ N+ and 0 < α ≤ 1. There exists a constant cα,d > 0 such that, for every M, P ∈ N+ , Eα,d (M, P ) ≥ cα,d [P min{M, P }]−α/d .

(15)

The constant is independent of M , P , the network depth, the architecture, and the affine map. Theorem 3.3 is proved in Section 5. The proof first controls the pseudo-dimension of a network family generated by an affine map in terms of its affine rank and the number of ReLU units. It then combines this capacity estimate with a packing of localized Hölder functions. Combining (14) and (15) gives, whenever P ≥ Pd⋆ and min{M, P } ≥ 4, Eα,d (M, P ) ≍α,d [P min{M, P }]−α/d . Thus the upper and lower bounds match up to constants depending only on (α, d). Remark 3.4 (A constant number of latent coordinates). Fix an integer M0 ≥ 4 independently of P . For P ≥ max{M0 , Pd⋆ }, the sharp estimate reduces to −α/d

Eα,d (M0 , P ) ≍α,d (M0 P )−α/d = M0

P −α/d .

Thus the number of target-dependent latent coordinates need not increase with the network budget for the worst-case error to converge to zero. A fixed collection of exact real coordinates, together with an increasingly large decoder shared across the target class, already achieves the algebraic rate P −α/d . By contrast, when M ≥ P , the rate saturates at P −2α/d . The regime with fixed M is therefore genuinely different from the regime in which all P parameter slots can vary independently with the target. When only the dependence on P is displayed, the implied constants may depend on the fixed value M0 .

4

Constructive proof of the upper bound

This section gives a constructive proof of Theorem 3.1. The proof is assembled from elementary fixed-width modules. Details are included because two bookkeeping questions are central: which coefficients may depend on the latent vector, and how signed quantities are transported through a standard fully connected ReLU network without skip connections. Every sparse module below is embedded into a fully connected layer by assigning zero to unused entries. These entries are still included in the dense parameter count PΦ . References below to a “vector-valued module” are shorthand for several channels retained within a single network with scalar output; they do not introduce a separate architecture class. Intermediate affine readouts are either omitted, leaving the relevant coordinates in the hidden 15

state, or merged with an adjacent affine layer only when one side is fixed, as in Lemma 4.3. Every width and depth ledger refers to this single final architecture, and every zero used to embed a sparse state transition is counted as a dense parameter slot. The seven subsections follow the data flow of the construction. Section 4.1 develops serialized hinge sums and safe composition; Sections 4.2 and 4.3 construct the affine loader and fixed decoder; and Section 4.4 combines them into a discrete fitting module. Section 4.5 then supplies spatial addressing, bridge sequences, and boundary repair. Section 4.6 assembles all modules under integer resource budgets, and Section 4.7 converts those resources into the prescribed budgets (M, P ).

4.1

Serialized hinge sums and safe composition

A continuous piecewise linear scalar function can be written as a sum of hinges. The next lemma serializes those hinges so that width is independent of their number. Lemma 4.1 (Serialized hinges). Let J ∈ N+ , let κ1 < · · · < κJ , and let a, b, c1 , . . . , cJ ∈ R. The function J X φ(x) := a + bx + cj ϱ(x − κj ) j=1

is realized by an architecture Φ ∈ Arch(5, 2J + 2). More generally, if a, b, c1 , . . . , cJ are affine functions of a common vector ξ ∈ RMcode for some Mcode ∈ N+ , then Φ can be chosen independently of ξ, and all slot assignments jointly define one affine map A ∈ Aff(Mcode , PΦ ). A target-dependent slot uses only the coordinates that occur in one of the displayed coefficients. Proof. We carry both the input and a running signed sum by their positive and negative parts. For each hinge, one layer computes the hinge and a second layer adds its weighted contribution to the running sum. This organization keeps the width fixed while the depth grows linearly with the number of hinges. The elementary identity ϱ(v) − ϱ(−v) = v, v ∈ R, will be used repeatedly. Write x+ := ϱ(x),

x− := ϱ(−x),

x = x+ − x− .

The first hidden layer produces x+ , x− and a+ := ϱ(a), a− := ϱ(−a). Here a+ is obtained using zero input weight and bias a, while a− uses zero input weight and bias −a. The next hidden layer forms

H0+ := ϱ a+ − a− + b(x+ − x− ) , H0− := ϱ −a+ + a− − b(x+ − x− ) . Hence H0+ − H0− = a + bx. Suppose that after the (j − 1)st update the state contains + − x+ , x− , Hj−1 , Hj−1 ,

+ − Hj−1 − Hj−1 = a + bx +

j−1 X i=1

ci ϱ(x − κi ).

One additional hidden layer computes hj := ϱ(x+ − x− − κj ) = ϱ(x − κj ) while copying the four nonnegative state coordinates. The next layer computes
+ − Hj+ := ϱ Hj−1 − Hj−1 + cj hj ,
+ − Hj− := ϱ −Hj−1 + Hj−1 − cj hj , 16

again copying x+ and x− . Therefore + − Hj+ − Hj− = Hj−1 − Hj−1 + c j hj .

This proves the induction. The affine output HJ+ − HJ− equals φ(x). At most five channels are + − present: x+ , x− , Hj−1 , Hj−1 , hj . Every copied coordinate is nonnegative, so an identity weight and zero bias pass it unchanged through ReLU. There are two initialization layers and two layers for each of the J hinges, so the hidden depth is at most 2J + 2. Only the biases ±a and the weights ±b, ±cj vary with the coefficients. They enter individual network slots without being multiplied by another varying parameter slot. A varying weight such as cj is allowed to multiply the activation hj during the forward pass; the requirement is only that the value assigned to each parameter slot be affine in the latent vector. Consequently, affine dependence of the coefficients on that vector implies affine dependence of every parameter slot. Listing the fixed and varying assignments in the global slot order gives the single affine map asserted in the statement. The preceding lemma applies to every continuous piecewise linear scalar function with finitely many breakpoints, because its slope changes are exactly the hinge coefficients. We record this elementary fact to ensure that the later staircase constructions do not rely on an unstated representation theorem. Lemma 4.2 (Slope-jump representation). Let φ : R → R be continuous and piecewise linear with breakpoints κ1 < · · · < κJ . Suppose its slope is m0 to the left of κ1 , is mj between κj and κj+1 for j = 1, . . . , J − 1, and is mJ to the right of κJ . Then J X φ(x) = φ(κ1 ) + m0 (x − κ1 ) + (mj − mj−1 )ϱ(x − κj ).

(16)

j=1

Consequently, φ is realized by an architecture in Arch(5, 2J + 2). If φ(κ1 ) and all its slopes are affine functions of a latent vector, the realization can be chosen so that every parameter slot is affine in that vector. Proof. Call the right-hand side of (16) ψ(x). When x < κ1 , every hinge vanishes, so ψ has slope m0 . When κk < x < κk+1 , exactly the first k hinges are active, and the slope telescopes: m0 +

k X (mj − mj−1 ) = mk . j=1

The same calculation gives slope mJ for x > κJ . Moreover, ψ(κ1 ) = φ(κ1 ). Starting with the interval containing κ1 and moving across the breakpoints, continuity and equality of the slopes show successively that ψ = φ on every linearity interval. This proves the formula. Lemma 4.1 gives the network realization. Its coefficients are fixed linear combinations of φ(κ1 ), m0 , . . . , mJ , which proves the final affine-dependence statement. The preceding lemmas provide the scalar building blocks. To assemble them into a single network while preserving affine dependence on the code, we next record the required transport and composition rules.

17

Lemma 4.3 (Signed transport and one-side-fixed composition). The following operations preserve affine dependence of network parameters on a common code vector. (i) A signed scalar u may be transported through any number of hidden layers as the nonnegative pair (u+ , u− ) = (ϱ(u), ϱ(−u)), with the fixed identity update (u+ , u− ) 7→ (u+ , u− ) and recovery u = u+ − u− .

(ii) Finitely many networks may be copied or run in parallel. Their widths add. A qdimensional state is transported coordinatewise by 2q nonnegative channels, so shorter branches can be extended to a common depth by fixed signed transport. If a branch already terminates in a nonnegative state or a signed pair, its existing depth gap is filled by fixed identity layers. If only a signed scalar affine readout u = w(ξ)⊤ h + b(ξ) is available, compose that readout with the fixed split map u 7→ (u, −u), whose matrix is [1, −1]⊤ , and merge the two adjacent affine maps. The resulting hidden layer produces (ϱ(u), ϱ(−u)); its two affine rows are sign copies of (w(ξ), b(ξ)), so affine code dependence is preserved. This split layer must be included in the interface depth ledger. (iii) Two adjacent affine layers with no intervening activation may be merged without losing affine code dependence whenever at least one of the two layers is fixed. (iv) Repeating an affine slot assignment in copied branches and padding unused slots by fixed zeros preserve affine code dependence. Zero padding changes the dense parameter count but not the realized function. By contrast, merging two code-dependent affine layers need not preserve affine dependence. Proof. The proof is a coefficientwise calculation. The transport and routing coefficients in parts (i) and (ii) are fixed at 0, 1, or −1. Splitting a code-dependent readout merely copies its coefficient row with both signs, so affine dependence is preserved. For (iii), we expand the merged coefficients and identify exactly where a product of two code-dependent entries could occur. For (i), define
u± := ϱ(u), ϱ(−u) . Every coordinate of u± is nonnegative, and hence each additional hidden layer may copy it by u± 7−→ ϱ(I2 u± ) = u± . The fixed output row [1, −1] gives [1, −1]u± = u. For a vector u = (u1 , . . . , uq ), apply this construction separately to each coordinate. The transported state is (u1,+ , u1,− , . . . , uq,+ , uq,− ) ∈ R2q , and a fixed block row recovers u. This is the vector-valued padding used in part (ii). For (ii), suppose J modules at a common layer have matrices W (1) , . . . , W (J) and biases (1) b , . . . , b(J) . If they receive different state vectors, their parallel layer is

W ∥ := diag W (1) , . . . , W (J) , b∥ := b(1) , . . . , b(J) . Every off-diagonal routing block is fixed at zero; the diagonal blocks may be code dependent. If the matrices and biases of the original modules are affine in ξ, then so are all entries of (W ∥ , b∥ ). A shorter module whose retained state is already nonnegative is padded by the fixed signed-transport update from (i), so unequal depths introduce no new code-dependent coefficient. If its terminal value is available only as a signed affine readout, write u = w(ξ)⊤ h+b(ξ). Merging this readout with the fixed split gives the two affine rows (w(ξ), b(ξ)) and (−w(ξ), −b(ξ)). After ReLU they produce (ϱ(u), ϱ(−u)); subsequent layers copy this pair by fixed identities. The split costs one hidden layer and may duplicate code-dependent slots, but every duplicated slot remains affine and no product of varying coefficients is formed. The final recovery row is fixed. 18

If all branches receive the same input, their first-layer matrices are stacked vertically rather than placed diagonally. In both cases, the widths add. The padded depth is the common target depth when the signed pair is already present; otherwise the one split layer is counted explicitly at the relevant interface. For (iii), let adjacent affine maps be u 7→ W1 (ξ)u + b1 (ξ) and v 7→ W2 (ξ)v + b2 (ξ). With no activation between them, their composition is W2 (ξ)W1 (ξ)u + W2 (ξ)b1 (ξ) + b2 (ξ). If (W1 , b1 ) = (W10 , b01 ) is fixed and W2 (ξ) = W20 +

M X

ξm W2m ,

b2 (ξ) = b02 +

m=1

M X

ξm b m 2 ,

m=1

then the merged matrix and bias are W20 W10 +

M X

ξm W2m W10 ,

W20 b01 + b02 +

m=1

M X

ξm (W2m b01 + bm 2 ),

m=1

which are affine in ξ. If instead (W2 , b2 ) = (W20 , b02 ) is fixed, the merged matrix and bias are W20 W1 (ξ),

W20 b1 (ξ) + b02 ,

which are again affine in ξ. If both layers vary, the product can contain ξm ξm′ ; for example, the scalar composition of the weights w1 (ξ) = w2 (ξ) = ξ has weight ξ 2 . For (iv), copying a module repeats the same affine coordinate function in additional entries of the complete parameter vector. Assigning zero to a new slot gives a constant, hence affine, coordinate function. Neither operation changes an already constructed branch value. Every interface used below has a fixed side: fixed routing precedes an affine loader, and a fixed decoder or median module follows an affine loader. The preceding operations will often be described at the level of retained hidden states rather than by writing a new dense matrix at every interface. The following closure statement makes that shorthand precise and will be used throughout the remainder of the upper construction. Corollary 4.4 (Assembly through retained states and fixed interfaces). Consider finitely many ReLU modules whose parameter slots are affine functions of one common code vector. Form a computation by repeatedly applying the following operations: run modules in parallel; retain a terminal hidden state instead of applying its scalar affine readout; route or split retained states through fixed affine/ReLU layers; merge consecutive affine maps when at least one is fixed; and align depths by fixed signed transport. Then the resulting computation is realized by one fully connected scalar-output ReLU architecture, and every slot of that architecture is affine in the same code vector. If a hidden layer of the resulting architecture is enlarged by adding channels that are identically zero, the enlarged architecture realizes the same function. More precisely, if the original pair is (Ψ, A) with A ∈ Aff(M, PΨ ) and the enlarged architecture is Ψpad , inserting fixed zeros into the new slots defines Apad ∈ Aff(M, PΨpad ) such that Ψpad = ΨA(ξ) for every ξ ∈ RM . Apad (ξ)

19

Proof. Parallelization stacks first-layer matrices when the branches share an input and uses block-diagonal matrices at later layers. Retaining a terminal state simply omits a scalar affine row. Every subsequent substitution of an omitted readout is a composition of two adjacent affine maps, with at least one side fixed by assumption, and is therefore affine in the code by Lemma 4.3(iii). Fixed routing, splitting, and signed transport use only constant coefficients, while copied branches repeat existing affine coordinate functions. Induction over the finite sequence of operations produces a single dense architecture after all unused connections are assigned zero. This proves the first assertion. For padding, keep every old slot assignment in its corresponding position and assign zero to each new incoming weight, outgoing weight, and bias associated with an added channel. This is a fixed affine injection from RPΨ into RPΨpad . Its composition with A is the displayed map Apad , and all added channels remain zero after ReLU. Hence the realized function is unchanged and the codomain agrees with the enlarged architecture. This closure rule separates architectural bookkeeping from the numerical purpose of each module. From now on, saying that a module “returns” several quantities means that they occur in its terminal hidden state as nonnegative channels or signed pairs. Intermediate scalar readouts are attached only conceptually and are eliminated at the next fixed-side interface. We may therefore construct the loader, decoder, and routing modules separately and then combine them without leaving the class of ordinary scalar-output fully connected networks.

4.2

Affine spline loading with serialized hinges

We first use the serialized hinge construction to turn S latent coordinates into interpolation data for a one-dimensional spline while keeping the width independent of S. Lemma 4.5 (Affine spline loader). Let S ∈ N+ and y = (y0 , . . . , yS−1 ) ∈ RS . There exist an architecture Φspl ∈ Arch(5, 2S + 2) and an affine map Aspl ∈ Aff(S, PΦspl ), both independent of y, such that, after setting θ := Aspl (y), one has Φspl θ (m) = ym ,

m = 0, . . . , S − 1.

Every target-dependent slot depends on at most three consecutive entries of y. Proof. We express the linear interpolant through the points (m, ym ) in the hinge basis 1, x, ϱ(x − m). Its coefficients are first and second differences of the data and are therefore linear functions of y. Lemma 4.1 then adds the hinges one at a time while carrying x and a signed running sum through a constant number of channels. For S = 1, let the first hidden layer use zero input weights and the two code-dependent biases y0 , −y0 to produce (ϱ(y0 ), ϱ(−y0 )). Three fixed identity layers transport this pair, and the fixed scalar readout [1, −1] returns y0 . If that readout is omitted, the terminal hidden state still contains the same signed pair, exactly as required by the later loader interface. Fixed zero channels give width at most 5 and hidden depth 4 = 2S + 2. The only varying slots are linear in y. We now assume S ≥ 2. The continuous piecewise linear interpolant, extended constantly outside [0, S − 1], is φy (x) = y0 + (y1 − y0 )ϱ(x) +

S−2 X

(ym+1 − 2ym + ym−1 )ϱ(x − m)

m=1

− (yS−1 − yS−2 )ϱ(x − (S − 1)). 20

(17)

To verify the interpolation, first note that φy (0) = y0 . On the open interval (j, j + 1), j = 0, . . . , S − 2, the slope is (y1 − y0 ) +

j X

(ym+1 − 2ym + ym−1 ) = yj+1 − yj ;

m=1

the sum telescopes. Hence φy (j + 1) − φy (j) = yj+1 − yj , and induction gives φy (j) = yj for every required integer. The final hinge at S − 1 cancels the last slope, so the right extension is constant. The formula is also valid when S = 2, in which case the middle sum is empty. The representation (17) contains exactly S hinges, at 0, 1, . . . , S − 1. Lemma 4.1 therefore gives width at most 5 and hidden depth at most 2S + 2. Its initial value and every hinge coefficient are linear combinations of at most three consecutive entries of y. The vector of all such coefficients is therefore a fixed linear transformation of y. Placing those coefficients into the corresponding network slots defines the fixed affine map Aspl and proves the claimed support bound. We will later use three copies of this loader in parallel. Their combined width is at most 15, their depth is unchanged, and each target-dependent slot still involves at most three consecutive coordinates from its data block.

4.3

Fixed binary prefix decoder

The complementary decoding module is entirely fixed. It reads a prefix of a finite binary string encoded in one real input. The integer D determines the sequential reading time, while only the binary fraction supplied as input changes with the encoded string. For a bit vector ν = (ν1 , . . . , νD ) ∈ {0, 1}D , use the finite binary-fraction notation bin 0.ν1 · · · νD :=

D X

νi 2−i .

i=1

For fixed D, this encoding is injective on {0, 1}D ; the familiar ambiguity of infinite binary expansions does not arise. Lemma 4.6 (Binary prefix extraction). For every D ∈ N+ , there exist a two-input architecture ΨD ∈ Arch(20, 4D + 2) and a fixed parameter vector θD ∈ RPΨD . Denote the resulting function by ED := (ΨD )θD : R2 → R.

Then, for every ν ∈ {0, 1}D ,

k
X ED bin 0.ν1 · · · νD , k = νi ,

k = 0, 1, . . . , D,

i=1

where the sum is understood to be zero when k = 0. The vector θD depends on D, but none of its entries depends on ν. Proof. At stage i, a fixed piecewise linear gate extracts the leading bit of the current binary remainder. We double the remainder, subtract the extracted bit, and add that bit to the accumulator exactly when i ≤ k. Repeating this fixed-width block D times produces the required prefix sum. The details below also verify that no decoder parameter depends on the bit string. The identities proved below are required only on the following finite collection of legal inputs:  (bin 0.ν1 · · · νD , k) : ν ∈ {0, 1}D , k ∈ {0, . . . , D} . 21

The constructed ReLU network is defined on all of R2 , but the lemma makes no assertion away from these inputs. This distinction is useful because some intermediate affine expressions are known to be nonnegative only at the legal inputs. Set δD := 2−(D+1) and define the fixed gate ϱ(t − 1 + δD ) − ϱ(t − 1) . δD

gD (t) :=

(18)

The three ranges can be checked separately. If t ≤ 1 − δD , both ReLU terms vanish. If 1 − δD ≤ t ≤ 1, only the first is active and gD (t) =

t − 1 + δD . δD

If t ≥ 1, their difference is (t − 1 + δD ) − (t − 1) = δD . Hence gD (t) = 0

(t ≤ 1 − δD ),

gD (t) = 1

(t ≥ 1),

with the displayed linear interpolation between the two plateaus. Let r0 = bin 0.ν1 · · · νD . Recursively define ri = 2ri−1 − ei ,

ei = gD (2ri−1 ),

i = 1, . . . , D.

(19)

We first prove the complete remainder invariant ri =

D X

νj 2−(j−i) ,

i = 0, . . . , D,

(20)

j=i+1

where the sum is empty and therefore equal to zero when i = D. For i = 0, (20) is exactly the definition of r0 . Assume it holds at index i − 1. Then ri−1 =

D X

νj 2−(j−i+1) .

j=i

If νi = 0, then 2ri−1 =

D X j=i+1

νj 2−(j−i) ≤ 1 − 2−(D−i) ≤ 1 − 2−(D−1) = 1 − 4δD < 1 − δD ,

where the empty sum for i = D is zero. The second inequality uses D − i ≤ D − 1, and the equality uses δD = 2−(D+1) . Hence ei = 0 = νi . If νi = 1, then 2ri−1 ≥ 1, so ei = 1 = νi . Substitution in (19) gives D X ri = νj 2−(j−i) . j=i+1

This is the invariant at index i. Induction therefore proves both ei = νi ,

ri =

D X

νj 2−(j−i) ,

i = 1, . . . , D.

j=i+1

In particular, every ri lies in [0, 1) at a legal input. For the integer input k, the quantity τi (k) := ϱ(k − i + 1) − ϱ(k − i) 22

(21)

equals 1 if k ≥ i and 0 if k < i. Since ei , τi (k) ∈ {0, 1} at the required inputs, ei τi (k) = ϱ(ei + τi (k) − 1). Thus a running accumulator adds ei exactly when i ≤ k. More formally, define ui := ϱ(ei + τi (k) − 1),

A0 := 0,

Ai := Ai−1 + ui .

The second induction invariant is Ai =

i X j=1

min{i,k}

νj 1{j≤k} =

X

νj ,

i = 0, . . . , D.

(22)

j=1

Here the last sum is understood to be zero when min{i, k} = 0. It holds for i = 0 because both sides vanish. If it holds for i − 1, then (21) and the definition of τi give ui = ei τi (k) = νi 1{i≤k} . Adding this term to Ai−1 proves (22) at index i. At the end of the D stages, AD =

k X

νj ,

j=1

which is the desired output. It remains to realize these recurrences by a ReLU network and verify the resource bounds. One four-layer block can be organized as follows. Its input is the nonnegative state (ri−1 , k, Ai−1 ), whose values are described by (20) and (22): (1) compute the two hinges in (18) and the two hinges defining τi (k), while copying ri−1 , k, Ai−1 ; (2) form the nonnegative values ei , τi (k), and ri = 2ri−1 − ei , while copying k, Ai−1 ;

(3) form ui = ϱ(ei + τi (k) − 1) and copy ri , k, Ai−1 ; (4) set Ai = Ai−1 + ui and copy ri , k.

The four operations above yield the following state and channel ledger. The middle column lists the nonnegative coordinates retained after each layer. layer of block i

state retained after the layer

channels

copied state: (ri−1 , k, Ai−1 ), 1

hinges: ϱ(2ri−1 − 1 + δD ), ϱ(2ri−1 − 1),

7

2

ϱ(k − i + 1), ϱ(k − i) (ri , k, Ai−1 , ei , τi (k))

5

3

(ri , k, Ai−1 , ui )

4

4

(ri , k, Ai )

3

The only point requiring care is layer 2. It computes ei , τi (k), and ri from the hinge channels produced by layer 1, together with the copied value ri−1 . In particular, the computation of ri does not use the layer 2 postactivation ei . All coordinates listed in the state column are nonnegative at the required inputs, so copied coordinates pass unchanged through ReLU. One initial hidden layer creates (r0 , k, A0 ) with A0 = 0; after the D blocks, the scalar output layer reads AD . Thus the hidden depth is at most 1 + 4D ≤ 4D + 2, and the maximum displayed width is 7 ≤ 20. Assigning zero to unused entries of the actual dense layers gives a fully connected realization of width at most 20. All constants depend on D through δD but not on the particular bit string, so the parameter vector is fixed. 23

This construction is the one-dimensional, single-stream specialization of the bit-extraction schemes underlying (Bartlett et al., 1998, Theorem 2) and (Shen et al., 2022d, Lemma 4.5). Since the full recurrence is verified above, neither cited result is invoked as a black box.

4.4

Point fitting with an affine code

The two preceding modules play complementary roles. The spline loader uses S latent entries to select data for each block, and its parameter slots depend affinely on those entries. The fixed prefix decoder uses depth proportional to D to read the data stored in the selected block. We now combine the two modules into a one-dimensional construction that fits up to SD consecutive samples. Here and below, “affine” refers to the parameter map ξ 7→ θ; the target-dependent selection of ξ from the samples need not be affine. Lemma 4.7 (Point fitting with an affine code). Let 1 ≤ S ≤ D, 1 ≤ J ≤ SD, and η ≥ 0. Suppose y0 , . . . , yJ−1 ∈ R satisfy |yj − yj−1 | ≤ η,

j = 1, . . . , J − 1.

Write y := (y0 , . . . , yJ−1 ). There exist a one-input architecture Φfit ∈ Arch(96, 10D + 24) and an affine map Afit ∈ Aff(3S + 1, PΦfit ), both depending only on (S, D), such that one can choose ξ ∈ R3S+1 and set θ := Afit (ξ) so that Φfit θ (j) − yj ≤ η,

j = 0, . . . , J − 1.

(23)

Neither the architecture nor the affine map depends on the samples or on η. Proof. The construction has four stages. First, we pad the sequence and write each index as j = mD + k. Second, within each block, quantization at scale η turns every successive change into −1, 0, or 1; we store the block baseline directly and encode the positive and negative changes in two binary fractions. Third, three affine spline loaders select these blockwise quantities, and two fixed prefix decoders reconstruct the cumulative changes. Finally, the scale η enters through the generated output-layer weights ±η, so no network parameter is a product of two target-dependent quantities. Figure 4 summarizes this data flow. For η > 0, the central reconstruction identity, with notation introduced below, is am + + − η(Um,k − Um,k ) = ηzm,k . The loaders select the baseline and the two bit streams, while the fixed decoders supply only their prefix counts. Multiplication by η occurs only during the forward pass through output weights whose slot values are ±η; no parameter slot contains a product of two latent-dependent coordinates. Define a padded sequence ȳ0 , . . . , ȳSD−1 by ( yj , 0 ≤ j ≤ J − 1, ȳj := yJ−1 , J ≤ j ≤ SD − 1. The original samples are unchanged, and the padding preserves the increment bound because all appended differences vanish: |ȳj − ȳj−1 | ≤ η,

j = 1, . . . , SD − 1.

Every j ∈ {0, . . . , SD − 1} has a unique representation j = mD + k,

0 ≤ m ≤ S − 1,

Assume first that η > 0 and put   zm,k := ȳmD+k /η . 24

0 ≤ k ≤ D − 1.

(24)

For m = 0, . . . , S − 1 and k = 1, . . . , D − 1, (24) implies zm,k − zm,k−1 ∈ {−1, 0, 1}. Indeed, put u = ȳmD+k /η and v = ȳmD+k−1 /η. Then |u − v| ≤ 1. If ⌊u⌋ ≥ ⌊v⌋ + 2, then u ≥ ⌊v⌋ + 2 > v + 1, a contradiction; the opposite inequality is excluded in the same way. Define the two increment bits u+ u− m,k := max{zm,k − zm,k−1 , 0}, m,k := max{zm,k−1 − zm,k , 0} − for k = 1, . . . , D − 1, and append u+ m,D = um,D = 0. These are bits, and telescoping gives

zm,k = zm,0 +

k X i=1

u+ m,i −

k X

u− m,i .

(25)

i=1

For each block, store the three real numbers am := ηzm,0 ,

± ± ζm := bin 0.u± m,1 · · · um,D .

Together with the single scale η, these entries form the latent vector (or code) + − ξ := (a0 , . . . , aS−1 , ζ0+ , . . . , ζS−1 , ζ0− , . . . , ζS−1 , η) ∈ R3S+1 .

(26)

Although am = ηzm,0 in the target-dependent choice of the code, am is stored as a separate latent coordinate. Hence the fixed affine parameter map never needs to form this product. We next construct a fixed routing module that recovers the block index m and the withinblock index k from the input index j. Define a continuous piecewise linear function QS,D that equals m on [mD, (m + 1)D − 1], m = 0, . . . , S − 1, and interpolates linearly from m to m + 1 on [(m + 1)D − 1, (m + 1)D] for m = 0, . . . , S − 2. Extend it constantly to (−∞, 0] and [SD − 1, ∞). Thus QS,D : R → R is globally continuous and, at every required integer j = mD + k, one has QS,D (j) = m,

k = j − DQS,D (j).

The function has at most 2(S − 1) breakpoints when S ≥ 2, since each of the S − 1 transition intervals contributes at most its left and right endpoint. Its only slopes are 0 on the constant pieces and 1 on the transition pieces, and all breakpoints and slopes depend only on (S, D). Lemma 4.2 therefore writes QS,D as a fixed hinge sum and realizes it with width at most 5 and depth at most 4(S − 1) + 2 = 4S − 2. For S = 1, set Q1,D = 0 and use one fixed hidden layer with terminal state (j+ , j− , Q+ , Q− ) := (ϱ(j), ϱ(−j), 0, 0). The fixed scalar readout Q+ − Q− is zero. After omitting this readout, the same routing layer used below gives
m = ϱ(Q+ − Q− ) = 0, k = ϱ j+ − j− − D(Q+ − Q− ) = j at every required integer j = 0, . . . , D − 1. Thus the exceptional case has exactly the same terminal-state interface as the case S ≥ 2, and its two hidden layers, including the routing layer, lie within the bound 4S + 2. For S ≥ 2, apply the construction from Lemma 4.1 to QS,D and omit only its final scalar readout. Its terminal hidden state before that readout contains the transported input pair and the running-sum pair. Together with the explicit construction above for S = 1, we may therefore in every case retain a terminal state containing the signed pairs
(j+ , j− ) and (Q+ , Q− ) := ϱ(QS,D (j)), ϱ(−QS,D (j)) . 25

One fixed routing layer forms m = ϱ(Q+ − Q− ),

k = ϱ j+ − j− − D(Q+ − Q− ) .

At a required integer j = mD + k, both displayed preactivations are nonnegative and equal the desired quotient and remainder. Keeping the signed input is necessary because the architecture has no skip connections. The serialized state together with this routing layer uses at most twelve channels and hidden depth at most 4S + 2. With the quotient and remainder available, we now load the three blockwise code values. To make their common affine domain explicit, let πa , π+ , π− : R3S+1 → RS ,

πη : R3S+1 → R

be the fixed coordinate projections for which πa (ξ) = (am )S−1 m=0 ,

+ S−1 π+ (ξ) = (ζm )m=0 ,

− S−1 π− (ξ) = (ζm )m=0 ,

πη (ξ) = η.

Apply Lemma 4.5 in parallel with parameter maps Aspl ◦ πa , Aspl ◦ π+ , and Aspl ◦ π− . At the + , ζ − . Every generated spline coefficient is therefore integer input m, the outputs are am , ζm m a fixed linear combination of at most three coordinates of (26). The nonnegative remainder k ∈ {0, . . . , D − 1} is copied by fixed identity channels through all loader layers. The three five-channel loaders, together with the transported remainder, use at most sixteen channels. At the interface to the decoders, omit the three scalar output layers and merge their affine readouts with a following ReLU interface layer whose pre-merge coefficients are fixed. That interface converts the possibly signed baseline to am,+ := ϱ(am ),

am,− := ϱ(−am ),

while the two nonnegative binary fractions and k are copied. Thus the state entering the next module can be taken to be + − (am,+ , am,− , ζm , ζm , k). The omitted loader readouts are also fixed when S = 1, because of the signed-pair implementation in Lemma 4.5. Hence their merger with the fixed interface never multiplies two target-dependent coefficients. + , k) and the Next apply two parallel copies of the fixed decoder from Lemma 4.6, one to (ζm − other to (ζm , k). They return + Um,k :=

k X

− Um,k :=

u+ m,i ,

i=1

k X

u− m,i .

i=1

While the fixed decoders run, (am,+ , am,− ) is transported through identity channels. Two width-20 decoders together with these two baseline channels use width at most 42; we retain the looser bound 44 in the ledger below. At the terminal decoder layer, retain the two accumulator + − coordinates Um,k and Um,k and omit the decoders’ fixed scalar readouts. The scalar output layer of the complete network is + − (am,+ − am,− ) + ηUm,k − ηUm,k . (27) The multiplication by η is not part of a nonlinear parameter map: the two varying output-layer weights are πη (ξ) and −πη (ξ). They are therefore affine in the latent vector. By (25), the readout in (27) equals ηzm,k . The defining property of the floor function gives 0 ≤ ȳmD+k − ηzm,k < η. For every original index j < J, one has ȳj = yj , so this proves (23). 26

If η = 0, (24) makes the padded sequence constant. Set every baseline am equal to ȳ0 , set both binary streams to zero, and set the scale coordinate to zero. The same architecture then returns ȳ0 at every required integer and hence reproduces the original data exactly. The baseline coordinates are stored directly in the latent vector, so the affine map never forms a product of η with another latent coordinate. It remains to verify the architecture budget and the affine nature of the complete assignment. At the required integer inputs, the stagewise quantities evolve as + − (m, k) −→ (am , ζm , ζm , k)

+ − −→ (am,+ , am,− , ζm , ζm , k)

+ − −→ (am,+ , am,− , Um,k , Um,k )

+ − −→ (am,+ − am,− ) + ηUm,k − ηUm,k .

The first arrow is implemented by the three parallel loaders while k is copied. Their scalar affine readouts are merged into the fixed split/copy interface layer implementing the second arrow. The third arrow is implemented by two fixed prefix decoders while the baseline pair is copied; their fixed scalar readouts are omitted and their terminal nonnegative accumulators are retained. The last arrow is the single scalar output layer with weights 1, −1, η, −η and zero bias. The corresponding resource ledger is given below. The width budget is the maximum of the modulewise width bounds, whereas the hidden-depth contributions are added sequentially. The target-dependent slots are identified immediately after the table. Module

State at the module output

Width

Hidden depth

Quotient and remainder routing

(m, k)

≤ 12

≤ 4S + 2

Three spline loaders and transported k

terminal states of the three loaders and k (am,+ , am,− ),

≤ 16

≤ 2S + 2

≤5

1

+ − (Um,k , Um,k )

≤ 44

≤ 4D + 2

one scalar

1

0

Loader readout and split/copy interface Two prefix decoders and transported baseline pair Final affine readout

+ − (ζm , ζm , k)

(am,+ , am,− ),

The first module is completely fixed. In the loader module, the three maps Aspl ◦ πa , Aspl ◦ π+ , and Aspl ◦ π− place every varying hinge coefficient into its designated block of network slots; fixed zeros occupy the off-block connections. Hence each affected slot is affine in the common vector ξ. The two prefix decoders and all transport connections are fixed. In the last row, the two varying output weights are πη (ξ) and −πη (ξ), while the coefficients of am,+ − am,− are fixed. Concatenating these blockwise assignments in the fixed global slot order defines a single affine map from R3S+1 into the complete parameter space. Thus every varying slot has been identified explicitly. The width bounds include every signed transport channel. The quotient and remainder routing layer is already included in the first row; the loader readout and split/copy interface is displayed separately; alignment inside a parallel block uses fixed identity/zero padding up to the common block depth and contributes no additional depth beyond the module bounds already listed; and the final affine readout is the network’s scalar output layer, not a hidden layer. The sequential hidden depths therefore add to at most (4S + 2) + (2S + 2) + 1 + (4D + 2) = 6S + 4D + 7 ≤ 10D + 7 ≤ 10D + 24.

27

The maximum used width is 44 ≤ 96, and all unused dense slots are fixed at zero. The slot-by-slot description following the table, together with Lemma 4.3, shows that every parameter assignment is affine in the code and that no product of two target-dependent coefficients is created. Every loader row uses at most three latent coordinates. This defines Afit and completes the proof. fixed index logic

j

fixed quotient–remainder j 7→ (m, k)

k

m

± ζm

affine parameter data

code ξ − (a0 , . . . , ζS−1 , η)

affine spline loaders + − m 7→ (am , ζm , ζm )

am

fixed prefix decoders ± ± (ζm , k) 7→ Um,k ± Um,k

+ − am + η Um,k − Um,k

η

Figure 4: Data flow in affine-coded point fitting. Orange nodes contain the latent vector or values loaded affinely from it; quotient computation, prefix extraction, and routing are fixed.

4.5

Spatial addressing, bridge sequences, and boundary repair

Lemma 4.7 fits a slowly varying table indexed by integers. To transfer this construction to a function on [0, 1]d , we must map each spatial point to a table address, arrange the stored values so that adjacent addresses vary slowly, and repair the thin regions in which a continuous address map transitions between integer values. The next three lemmas carry out these tasks in order. The first is a fixed-width specialization of the step construction in (Shen et al., 2022d, Proposition 3.1). Lemma 4.8 (One-dimensional address map). Let q ∈ N+ , K = q 2 , and 0 < δ ≤ 1/(3K). There exist a one-input architecture Ψ ∈ Arch(20, 8q + 4) and a fixed parameter vector θ ∈ RPΨ such that  k k+1  Ψθ (x) = k for x ∈ K , K − δ1{k≤K−2} , k = 0, . . . , K − 1. (28) All parameters depend only on (K, δ). Moreover, in the realization constructed below, the terminal hidden state contains nonnegative channels from which the address is obtained by a fixed affine readout. Consequently, this readout may be omitted and merged into a following fixed affine layer. Proof. Write the desired address as k = mq + ℓ. The first continuous staircase recovers the coarse index m. After subtracting m/q from the input, a second staircase recovers the fine index ℓ. Both staircases interpolate continuously across gaps of width δ and are serialized at fixed width; the final output is qm + ℓ. If q = 1, then K = 1. Use one fixed hidden layer whose state contains
ϱ(x), ϱ(−x), 0, 0 , and use the fixed scalar readout that subtracts the fourth coordinate from the third. This realizes the required constant address, belongs to Arch(20, 8q + 4), and, after the readout is omitted, leaves an explicit terminal address pair for the later composition. Hence assume q ≥ 2 for the staircase construction. Construct a continuous piecewise linear function φ1 that equals m on  m m+1  m = 0, . . . , q − 2, q , q −δ , 28

and equals q − 1 on the last coarse interval [(q − 1)/q, 1]. On each omitted gap interpolate linearly, and extend φ1 constantly to (−∞, 0] and [1, ∞). Construct φ2 on [0, 1/q] in the same way so that it equals ℓ on   ℓ ℓ+1 , − δ1{ℓ≤q−2} , ℓ = 0, . . . , q − 1. q2 q2 Thus the last plateau extends to the endpoint 1/q. Extend φ2 constantly to (−∞, 0] and [1/q, ∞). Both functions are now continuous piecewise linear functions on all of R. Their breakpoints, values, and slopes depend only on (q, δ), so Lemma 4.2 gives fixed hinge-sum representations for both staircases. The resulting address function is
ιK,δ (x) = qφ1 (x) + φ2 x − φ1q(x) . Let x belong to the interval in (28) and write k = mq + ℓ, with 0 ≤ m, ℓ ≤ q − 1. We first verify explicitly that x lies on the mth coarse plateau. If m ≤ q − 2 and ℓ ≤ q − 2, then k+1 m ℓ+1 m+1 −δ = + 2 −δ ≤ − δ. K q q q If m ≤ q − 2 and ℓ = q − 1, then the right endpoint of the fine interval is exactly (m + 1)/q − δ. Thus in both subcases the full fine interval lies inside  m m+1  q , q −δ . If m = q − 1, every fine interval lies inside the last coarse interval [(q − 1)/q, 1]. We have therefore proved in all cases that φ1 (x) = m. Subtracting m/q gives  ℓ ℓ+1  x− m q ∈ q 2 , q 2 − δ1{k≤K−2} . If ℓ ≤ q − 2, then necessarily k ≤ K − 2, and this is exactly the ℓth plateau interval of φ2 . If ℓ = q − 1 and m ≤ q − 2, the right endpoint is 1/q − δ, which lies in the last plateau. Finally, if m = ℓ = q − 1, then k = K − 1 and the right endpoint is 1/q; the last plateau was defined to include that endpoint. Hence
φ2 x − m q = ℓ, and consequently ιK,δ (x) = qm + ℓ = k. Each staircase has 2(q − 1) breakpoints: the two endpoints of each of its q − 1 transition gaps. By Lemma 4.2, each staircase is a hinge sum with 2(q − 1) hinges, so Lemma 4.1 realizes it with width 5 and depth at most 4(q − 1) + 2 = 4q − 2. We next make the carried states explicit. At the end of the first serialized staircase, retain
(x+ , x− ) and (H1,+ , H1,− ) := ϱ(φ1 (x)), ϱ(−φ1 (x)) . One fixed interface layer forms the signed remainder H1,+ −H1,−
, q H1,+ −H1,−
r− := ϱ −x+ + x− + . q

r+ := ϱ x+ − x− − Therefore

r+ − r− = x − 29

φ1 (x) . q

The pair (H1,+ , H1,− ) is copied by fixed identity channels while the second serialized staircase is evaluated at the signed input (r+ , r− ). A serialized hinge sum uses at most five channels; retaining the two channels for φ1 raises this to at most seven. The interface state itself has only four channels. Hence width 7 already suffices for the described states, and the stated width 20 provides conservative uniform padding. To justify the reuse of a signed input explicitly, every hinge ϱ(r − κ) in the scalar serialization is replaced by ϱ(r+ − r− − κ). The channels (r+ , r− ) are copied by the same fixed identity updates used in Lemma 4.1; its running signed sum is unchanged. Thus the second serializer implements the same hinge formula at r = r+ − r− , without any multiplication or additional target-dependent parameter slot. The displayed interface is one fixed hidden layer. The first initialization layer of the second serializer accepts (r+ , r− ) directly (rather than recomputing them from a scalar input), forms its own fixed initial value channels, and copies (H1,+ , H1,− ). All subsequent layers copy the retained pair produced by the first staircase using fixed identities. Consequently, no additional alignment layer is needed, and the total hidden depth is at most (4q − 2) + 1 + (4q − 2) = 8q − 3 ≤ 8q + 4. At the terminal hidden state, write the second staircase value as the signed pair (H2,+ , H2,− ). The fixed affine output row computes q(H1,+ − H1,− ) + (H2,+ − H2,− ) = qφ1 + φ2 . All coefficients are fixed functions of (q, δ), and the final affine row is fixed as well. This produces Ψθ and proves the lemma without invoking an external network construction for step functions. To combine the coordinate addresses into a single table index while reserving room for bridge values, define, for β = (β1 , . . . , βd ) ∈ {0, . . . , K − 1}d , row(β) :=

d−1 X

βℓ K d−1−ℓ ,

addr(β) := 2K row(β) + βd .

(29)

ℓ=1

The empty sum is zero when d = 1. The factor 2K reserves K unused addresses after each row for bridge values. Lemma 4.9 (Slow bridge sequence). Let f ∈ C([0, 1]d ) and K ∈ N+ . There exist 2K d samples y0 , . . . , y2K d −1 such that yaddr(β) = f (β/K), and |yj − yj−1 | ≤ ωf

√
d K ,

β ∈ {0, . . . , K − 1}d ,

(30)

j = 1, . . . , 2K d − 1.

(31)

Proof. In each row, the first K addresses store grid values, while the next K addresses form a linear bridge from the last value in the current row to the first value in the next row. Each bridge increment is the endpoint difference√divided by K, and the integer scaling property of the modulus bounds it at the desired scale d/K. We now define the sequence explicitly. For every i ∈ {0, . . . , K d−1 −1}, let β ′ (i) ∈ {0, . . . , K −1}d−1 be the unique prefix multi-index with lexicographic number i. Concretely, if β ′ (i) = (β1 , . . . , βd−1 ), then its base-K digits satisfy i=

d−1 X

βℓ K d−1−ℓ .

ℓ=1

30

Consequently, adjoining the last digit k gives addr((β ′ (i), k)) = 2Ki + k. When d = 1, β ′ (i) is the empty vector and there is only one row. Define
vi,k := f K1 (β ′ (i), k) , k = 0, . . . , K − 1, and assign the actual grid values by y2Ki+k := vi,k ,

k = 0, . . . , K − 1.

This is exactly (30). Two consecutive actual values vi,k−1 and vi,k are sampled at√points whose
Euclidean distance is 1/K, and hence their difference is at most ωf (1/K) ≤ ωf Kd . For i < K d−1 − 1, set, for u = 1, . . . , K,
u u y2Ki+K−1+u := 1 − K vi,K−1 + K vi+1,0 . These are the K bridge addresses 2Ki+K, . . . , 2K(i+1)−1. Every consecutive bridge increment, including the first increment from vi,K−1 , has magnitude √
√ 1 1 |vi+1,0 − vi,K−1 | ≤ ωf ( d) ≤ ωf Kd . K K √ The first inequality uses the diameter d of the cube; the second is exactly the integer scaling property recorded after (2), namely √
√
√ ωf ( d) = ωf K Kd ≤ Kωf Kd .

At u = K, the bridge value equals vi+1,0 , so the following transition to the first actual value of row i + 1 has size zero. Let i∗ := K d−1 − 1. For the last row, set y2Ki∗ +K−1+u := vi∗ ,K−1 ,

u = 1, . . . , K.

These are precisely the remaining indices 2Ki∗ + K, . . . , 2K d − 1, and their increments are zero. The preceding cases exhaust all pairs of adjacent addresses: consecutive actual samples within one row, the last actual sample to the first bridge sample, consecutive bridge samples, the final bridge sample to the first actual sample of the next row, and the constant tail after the final row. When K = 1, the within-row and nonconstant-bridge cases are empty, and the same assignments still give the two required samples. Hence these cases prove (31). The address map is constant and correct away from thin transition strips. The boundaryrepair argument below adapts the horizontal shift and median construction in (Lu et al., 2021, Theorem 2.1 and Lemmas 3.2–3.4). We include the proof to verify that, in the present affine latent setting, the repair preserves affine dependence on the code while retaining explicit width and depth bounds. To keep the affine map universal, δ must be fixed independently of f . For positive integers d, K and 0 < δ ≤ 1/(3K), define the transition set ΩK,δ :=

d K−1 o [ [ n x ∈ [0, 1]d : xj ∈ (k/K − δ, k/K) .

j=1 k=1

Thus ΩK,δ is the union of the one-sided strips on which at least one coordinate address may be changing. Figure 5 illustrates the one-dimensional geometry behind the repair.

31

Fj (x) = med(three branch values) confined by the two reliable values

Fj−1 (x − δ) reliable

Fj−1 (x)

Fj−1 (x + δ)

possibly unreliable

reliable

k k transition strip ( K − δ, K )

x−δ

k K

x

x+δ

Figure 5: A representative one-dimensional transition. If x lies in a transition strip, the shifts x − δ and x + δ lie on its two sides. More generally, among the three translated branches at least two are reliable, so the median remains between the two reliable values, regardless of the remaining branch.

e be a Lemma 4.10 (Boundary repair). Let d, K, M, N, L ∈ N+ and 0 < δ ≤ 1/(3K). Let Φ e d-input architecture in Arch(N, L) and A ∈ Aff(M, PΦe ) be given. There are Φ ∈ Arch(3d (N + e A, e K, δ), with the following property. 4), L + 2d) and A ∈ Aff(M, PΦ ), constructed solely from (Φ, d M e f ). If For every f ∈ C([0, 1] ), ε ≥ 0, and ξf ∈ R , set θef := A(ξ e e (x)| ≤ ε, |f (x) − Φ θ f

then, with θf := A(ξf ),

x ∈ [0, 1]d \ ΩK,δ ,

|f (x) − Φθf (x)| ≤ ε + dωf (δ),

x ∈ [0, 1]d .

Proof. We repair one coordinate at a time. For the coordinate currently under consideration, at least two of the three shifted points corresponding to −δ, 0, and +δ remain in the cube and avoid the transition strips in that coordinate. The later coordinates already satisfy the induction-domain restrictions, so these two points belong to the preceding reliable set. Their network values are therefore close to the target at the unshifted point. Taking the median prevents the third, possibly unreliable, value from leaving the interval determined by the two reliable ones. Repeating this argument over all d coordinates adds one modulus term per coordinate. Step 1: Realize the median by two explicit ReLU layers. For real a, b, c, set ha,b := ϱ(a − b),

u := ϱ(b + ha,b − c),

v := ϱ(c − a + ha,b ),

and let t := a + b − c. Thus t+ = ϱ(a + b − c) and t− = ϱ(−a − b + c) under the positive and negative part convention fixed in Section 3.1. Since b + ha,b = max{a, b} and a − ha,b = min{a, b}, med(a, b, c) = t+ − t− − u + v. Indeed, let amax := max{a, b} and amin := min{a, b}. Then t+ − t− − u + v = amax + amin − c − (amax − c)+ + (c − amin )+ = min{amax , c} + (amin − c)+

= med(a, b, c).

The last identity covers simultaneously the three alternatives c ≤ amin , amin ≤ c ≤ amax , and c ≥ amax . We shall also use the following elementary interval consequence. If I ⊆ R is an 32

interval, r ≤ s, and r, s ∈ I, while w is arbitrary, then med(r, s, w) ∈ [r, s] ⊆ I: the median is r, w, or s according as w ≤ r, r ≤ w ≤ s, or w ≥ s. The first hidden layer computes a+ := ϱ(a), a− := ϱ(−a), and analogously b± , c± , together with ha,b , using seven channels. The second computes (t+ , t− , u, v) using four channels, and the final affine row is [1, −1, −1, 1] with respect to the displayed ordering. Thus the median block adds two hidden layers and has width at most seven. Step 2: Set up the induction domains. For j = 0, . . . , d, let n o Dj := x ∈ [0, 1]d : xj+1 , . . . , xd avoid all transition strips . There is no restriction when j = d, so Dd = [0, 1]d , whereas D0 = [0, 1]d \ ΩK,δ . For d = 2, Figure 6 shows how these reliable domains expand as the two coordinates are repaired. reliable region

D0 = [0, 1]2 \ ΩK,δ

restriction not yet repaired

D2 = [0, 1]2

D1 repair x1

both coordinates restricted

repair x2

only x2 restricted

uniformly reliable

Figure 6: Coordinatewise boundary repair in two dimensions. Initially the approximation is reliable outside the vertical and horizontal transition strips. Repairing the first coordinate removes the vertical restrictions, and repairing the second coordinate yields a uniform estimate on the whole square.

We first construct the architecture and affine map independently of the code selected for e A). e Recursively, after (Φj−1 , Aj−1 ) has been constructed, form Φj from f . Set (Φ0 , A0 ) := (Φ, three translated copies of Φj−1 followed by the fixed two-hidden-layer median block from Step 1. For an arbitrary code ξ, define Aj (ξ) by copying the three affine slot assignments of Aj−1 (ξ). In the branches evaluated at x − δej , x, and x + δej , respectively, replace each first-layer bias b(ξ) by b(ξ) − δW (ξ)ej , b(ξ), b(ξ) + δW (ξ)ej . The three scalar branch readouts are merged into the first fixed median layer, and the remaining median parameters are fixed. Every resulting slot is affine in ξ: the translated biases are affine because δ is fixed, and the readout merge has a fixed side. Thus (Φj , Aj ) depends only on e A, e K, δ) and not on f . (Φ, Having fixed these target-independent pairs, for the selected code ξf , put Fj (x) := (Φj )Aj (ξf ) (x),

j = 0, . . . , d.

e e , and the preceding recursion yields Then F0 = Φ θ f

Fj (x) = med (Fj−1 (x − δej ), Fj−1 (x), Fj−1 (x + δej )) .

Assume inductively that |Fj−1 (x) − f (x)| ≤ ε + (j − 1)ωf (δ), 33

x ∈ Dj−1 .

(32)

Here ej is the jth coordinate vector. A neural network is defined on all of Rd , so a branch shifted outside the cube still has a numerical value; that branch will be treated as unreliable. Step 3: Show that two of the three branches are reliable. Fix x ∈ Dj . If K = 1, there are no transition strips and δ ≤ 1/3. If xj < δ, the shifts xj and xj + δ lie in [0, 1]; if xj > 1 − δ, the shifts xj − δ and xj lie in [0, 1]; and if δ ≤ xj ≤ 1 − δ, all three shifts do. Since there are no strips, at least two shifted points belong to Dj−1 = [0, 1]d , which proves the required reliability in this case. Assume henceforth that K ≥ 2. We first isolate the strip geometry. At least two of the three shifted coordinates lie in [0, 1] and outside the jth transition strips. To see this, if xj < δ, then xj and xj + δ are both admissible and lie before the first strip; indeed, xj + δ < 2δ ≤ 1/K − δ because 3δ ≤ 1/K. If xj > 1 − δ, the two admissible values are xj − δ and xj ; both lie beyond the last strip because xj − δ > 1 − 2δ > (K − 1)/K. In the remaining case δ ≤ xj ≤ 1 − δ, all three shifts lie in [0, 1]. One open strip of width δ cannot contain two of the δ-separated shifts. Moreover, points in two distinct open strips are separated by more than 1/K − δ ≥ 2δ, while the three shifts span only 2δ. Hence two different strips cannot contain two of the shifts either. The fact that the strips are open matters only at equality: a shifted coordinate lying exactly on a strip endpoint is reliable. Hence at most one shift is unreliable in every case. For each reliable shift x′ , its jth coordinate avoids every strip, and its coordinates j + 1, . . . , d equal those of x ∈ Dj . Hence x′ ∈ Dj−1 , so the induction hypothesis applies. Together with (2), the induction hypothesis gives |Fj−1 (x′ ) − f (x)| ≤ ε + (j − 1)ωf (δ) + |f (x′ ) − f (x)| ≤ ε + jωf (δ). Both reliable values lie in the interval centered at f (x) with radius ε + jωf (δ). The median of three real numbers lies between the two reliable values by the interval fact proved in Step 1, regardless of the third branch. Thus (32) holds with j in place of j − 1. Induction from D0 to Dd = [0, 1]d proves the error estimate. Step 4: Verify architecture size and affine dependence. Define width bounds recursively by w0 := N,

wj := max{3wj−1 , 7},

j = 1, . . . , d.

The three copies of the previous network run in parallel, while the following median block uses width at most seven. Hence width(Φj ) ≤ wj for every j. Since wj ≤ 3wj−1 + 7, solving the recurrence gives 7 wd ≤ 3d N + (3d − 1) < 3d (N + 4). 2 Each repair adds two hidden layers, so the final depth is at most L + 2d. The recursion for (Φj , Aj ) in Step 2 already specifies every affine slot assignment: translated first-layer biases are affine, copied branches repeat the same coordinate functions, each merge of a branch readout into the median block has one fixed side, and all remaining median parameters are fixed. Lemma 4.3 therefore applies at every interface. Taking (Φ, A) := (Φd , Ad ) gives the asserted target-independent pair, and Fd = ΦA(ξf ) has the error proved in Step 3. Remark 4.11 (Exact real arithmetic). The construction is formulated over exact real arithmetic. The latent vector ξf contains binary fractions whose number of relevant digits increases with −1 P . Moreover, the fixed decoder uses coefficients of size δD = 2D+1 in its bit gate. Accordingly, Theorem 3.1 neither bounds the bit length of the latent scalars nor controls the dynamic range of the fixed decoder weights; it also provides no numerical stability guarantee. If every latent scalar is restricted to b bits, the model is additionally constrained by the total latent information M b. As discussed in Section 2.6, we keep these finite-precision effects separate from the main theorem over exact real parameters. 34

4.6

Construction under integer budgets

All analytic and network-theoretic ingredients are now available. It remains to assemble them and coordinate their integer resources: S counts latent code blocks, D is the number of decoder stages, and q determines the spatial mesh. We first introduce the three abbreviations used below. For d, S, D ∈ N+ , set   b d,D := 18D + 30 + 2d. q := (SD/2)1/(2d) , K := q 2 , L (33) When SD = 1, this formula gives q = K = 0 and therefore does not yield a usable spatial mesh. The proposition below assumes q ≥ 1, while Theorem 3.1 invokes it only with q ≥ 2. It packages the complete construction. For reference, its resource ledger is  2 ξf ∈ R3S+1 , PΦ ≤ Bd D, K = (SD/2)1/(2d) . Thus the product of the number of code blocks and the decoder length determines the approximation scale. The final subsection converts this exact integer form into the prescribed budgets (M, P ). Proposition 4.12 (Universal construction in the regime q ≥ 1). Let d, S, D ∈ N+ with b d,D be the quantities in (33). Assume q ≥ 1. There exist an architecture S ≤ D, and let q, K, L b Φ ∈ Arch(Nd , Ld,D ) with input dimension d and an affine map A0 ∈ Aff(3S + 1, PΦ ), both independent of f . For every f ∈ C([0, 1]d ), there exists ξf ∈ R3S+1 such that, with θf := A0 (ξf ), one has √
f − Φθf L∞ ([0,1]d ) ≤ (d + 2)ωf Kd . (34) Moreover, PΦ ≤ Bd D.

(35)

√
Proof. We now combine the preceding modules. Put δ := 1/(3K) and η := ωf Kd . The grid has K cells per coordinate, and the definition of q ensures that its 2K d target and bridge samples

fit into S blocks of length D. A fixed address network maps points outside the transition strips √
to grid indices, and Lemma 4.7 decodes the corresponding samples with error ωf Kd . Spatial discretization contributes one more copy of this modulus, while Lemma 4.10 contributes at most d additional copies at the smaller scale δ. The point-fitting code uses exactly 3S + 1 coordinates. After composing the modules, we use uniform upper bounds on their actual widths and depths to count all dense slots, including unused connections assigned zero. Figure 7 summarizes the construction. The five steps below implement its arrows and track the associated constants. Step 1: Choose the grid and a transition width fixed across targets. The choice δ = 1/(3K) depends only on (d, S, D) through K and is therefore independent of f . Since K = q 2 and q is defined by (33), 2K d = 2q 2d ≤ SD.

(36)

If q = 1, then K = 1; the constant address module in Lemma 4.8, the bridge construction, and all later estimates remain valid. Thus this edge case requires no separate architecture.

35

target-dependent information

f

grid values and bridges 2K d ≤ SD samples

affine code ξf 3S + 1 coordinates

spatial query

x

fixed spatial address x 7→ addr(β) Error budget:

table decoder Ffpre off strips

median repair Φθf

spatial sampling +η, table decoding +η, median repair +d ωf (δ)

Figure 7: Proof architecture for the constructive upper bound. The target determines only the sampled values and latent vector. The spatial address network, decoder architecture, and affine loading rule are fixed, while the generated decoder parameters vary affinely with the latent vector. The capacity condition 2K d ≤ SD couples the number S of code blocks with the decoder length D.

Step 2: Construct the spatial address. Apply Lemma 4.8 to each coordinate in parallel. Outside ΩK,δ , the retained address channels represent  β β +1  β = (β1 , . . . , βd ), where xj ∈ Kj , jK − δ1{βj ≤K−2} . The d copies run in parallel: their rows in the first layer are stacked vertically, and connections between distinct copies are fixed at zero. Their total width is at most 20d and their depth is at most 8q + 4. The scalar address addr(β) in (29) is a fixed affine function of β, so forming it requires no hidden layer. This parallel construction can still be incorporated into a scalar-output architecture. We omit the d fixed scalar readout rows of the coordinate copies, retain their terminal hidden states, and substitute those readouts into the fixed affine formula for addr(β). That fixed scalar readout is in turn merged into the first fixed affine layer of the quotient and remainder block of Φfit . Both sides of this interface are fixed, so the merger adds neither a hidden layer nor a code-dependent slot. Outside ΩK,δ , the scalar supplied to the table module is exactly addr(β). Step 3: Load and decode the function values.

√
Use Lemma 4.9 to construct 2K d samples. The quantity η = ωf Kd bounds every adjacent increment. Since (36) holds, Lemma 4.7 applies with J = 2K d and gives a latent vector ξf ∈ R3S+1 . Set θffit := Afit (ξf ), Fftab := Φfit . θ fit f

Thus Fftab is the function produced by the point fitting module, and |Fftab (j) − yj | ≤ η,

j = 0, . . . , 2K d − 1.

(37)

The degenerate case η = 0 requires no change in the universal pair. Indeed, f is then constant on the√connected cube: any two points can be joined by finitely many segments of length at most d/K. We keep the same pair (Φfit , Afit ) and use the η = 0 code from Lemma 4.7, namely constant baselines, zero binary fractions, and zero scale. Thus no target-dependent replacement of the architecture or affine map is made. Compose the fixed address module with the universal table pair (Φfit , Afit ) using the addressto-table merger described in Step 2. The address readout and the quotient part of the point fitting network are both fixed, so Lemma 4.3 preserves affine dependence on the latent vector e A). e without an additional interface layer. Denote the resulting target-independent pair by (Φ, For the selected code, set e f ), e pre . θfpre := A(ξ Ffpre := Φ θ f

36

If x ∈ / ΩK,δ and its cell index is β, (30) and (37) imply |f (x) − Ffpre (x)| ≤ |f (x) − f (β/K)| + |f (β/K) − Fftab (addr(β))| √
≤ ωf Kd + η = 2η. Step 4: Repair all transition strips. e A) e with latent-vector dimension 3S + 1. It Apply Lemma 4.10 to the preliminary pair (Φ, produces the architecture Φ and affine map A0 in the proposition. Since √ 1 d δ= ≤ , 3K K monotonicity of the modulus gives ωf (δ) ≤ η. The repaired realized function, with θf := A0 (ξf ), therefore satisfies f − Φθf L∞ ([0,1]d ) ≤ 2η + dωf (δ) ≤ (d + 2)η, which is (34). Step 5: Verify width, depth, affine dependence, and total parameter count. The d coordinate address copies run in parallel, so their widths add to at most 20d while their common depth remains at most 8q + 4. The resulting address module is then composed sequentially with the point fitting module of width 96. Sequential modules take the maximum of their widths and add their depths. Therefore, before boundary repair, the combined module has width at most max{20d, 96} and depth at most (8q + 4) + (10D + 24). Because S ≤ D, one has

q ≤ (D2 /2)1/(2d) ≤ D.

Hence the preliminary depth is at most 18D + 28. Boundary repair increases the width to at most
3d max{20d, 96} + 4 = Nd b d,D . Thus the constructed architecture is fully and the depth to at most 18D + 28 + 2d ≤ L b connected and belongs to Arch(Nd , Ld,D ). Because no further enlargement to the upper bounds b d,D is needed, the architecture and the codomain of its affine parameter map remain Nd and L unchanged. All fixed-zero embeddings within the dense layers are included in the parameter count. For affine dependence, Lemma 4.7 uses 3S +1 target-dependent coordinates, while the address, spatial routing, and transition width are fixed. Every interface has at least one fixed side, as checked in Step 3 and formalized in Corollary 4.4. Thus no product of two target-dependent coefficients is introduced. Under the ordering in (4), these affine assignments of all dense weights and biases define a single universal map A0 ∈ Aff(3S + 1, PΦ ). In particular, its codomain is the parameter space of the same architecture Φ appearing in the proposition. Finally, write N := Nd and use (4). Replacing each actual hidden width and the actual depth b d,D = 18D + 30 + 2d. Since D ≥ 1, the by their upper bounds can only increase the count, and L b d,D − 1 = 18D + 29 + 2d first hidden layer contributes at most N (d + 1) slots, the remaining L hidden-to-hidden layers contribute at most (18D + 29 + 2d)N (N + 1) slots, and the scalar output layer contributes N + 1. To bound this expression by a constant multiple of D, use D ≥ 1 to obtain 18D + 29 + 2d ≤ (47 + 2d)D, 37

and   N (d + 1) + (N + 1) = N (d + 2) + 1 ≤ N (d + 2) + 1 D. Consequently, PΦ ≤ N (d + 1) + (18D + 29 + 2d)N (N + 1) + (N + 1)   ≤ (47 + 2d)N (N + 1) + N (d + 2) + 1 D ≤ Bd D.

This proves (35) and completes the proof.

4.7

Matching the prescribed budgets

Proposition 4.12 is stated in terms of the internal integers (S, D). No further network construction is needed. We now choose these integers from (M, P ), verify the latent-coordinate and parameterslot budgets separately, and translate the product SD into the final mesh scale. The choices and the resulting capacity relation are D = ⌊P/Bd ⌋,

3S + 1 ≤ min{M, P },

SD ≥

P min{M, P } . 4Bd2

Thus the choice of D is governed by the parameter-slot budget, the choice of S by the latentcoordinate budget, and their product determines the spatial resolution. f := min{M, P } be the effective latent coordinate budget. We Proof of Theorem 3.1. Let M f coordinates to S code blocks and choose the decoder length D proportional allocate 3S + 1 ≤ M to P . The explicit threshold Pd⋆ ensures that the grid integer q is at least two. The floor f/(4B 2 ) and therefore bound the mesh size by Cd (P M f)−1/d . estimates below yield SD ≥ P M d Proposition 4.12 then gives the required architecture, while precomposition with a coordinate projection extends its affine map from R3S+1 to the prescribed domain RM . Set  f − 1)/3⌋, D . D := ⌊P/Bd ⌋, S := min ⌊(M f ≥ 4 and P ≥ P ⋆ = 22d+2 Bd . We will repeatedly use the elementary The assumptions give M d estimate z ≥ 2 =⇒ ⌊z⌋ ≥ z − 1 ≥ z/2.

Applying this estimate to P/Bd ≥ 22d+2 ≥ 2 gives D≥

P ≥ 22d+1 . 2Bd

(38)

f ≤ M. Also 1 ≤ S ≤ D and 3S + 1 ≤ M f ≥ 4, We next derive a lower bound for S. Since M f − 1)/3⌋ ≥ ⌊(M

f M . 6

f = 4, 5, 6, 7, this inequality is checked directly; for M f ≥ 8, it follows from ⌊(M f− For M f − 4)/3 ≥ M f/6. Moreover, D ≥ P/(2Bd ) ≥ M f/(2Bd ). Since Nd ≥ 1, (8) yields 1)/3⌋ ≥ (M Bd ≥ (48 + 2d)Nd (Nd + 1) ≥ 100 > 3. Thus the two arguments in the minimum defining S satisfy, respectively, f f f − 1)/3⌋ ≥ M ≥ M , ⌊(M 6 2Bd 38

and D≥

f M . 2Bd

S≥

f M . 2Bd

SD ≥

f PM . 4Bd2

Therefore (39)

Combining (38) and (39) gives

Moreover, since S ≥ 1, (38) gives SD ≥ D ≥ 22d+1 . Therefore x := (SD/2)1/(2d) ≥ 2, so q = ⌊x⌋ ≥ 2 and, by the same floor estimate, q ≥ x/2. With K = q 2 , √ √
d 2 1/d ≤ 4 d SD K √ 2/d f)−1/d ≤ 4 · 81/d dBd (P M f)−1/d . = Cd (P M

(40)

b d,D ) with We may now apply Proposition 4.12, which supplies Φ ∈ Arch(Nd , L PΦ ≤ Bd D ≤ P √
and error at most (d + 2)ωf Kd . Since D = ⌊P/Bd ⌋, the two depth bounds coincide: b d,D = Ld,P . L To obtain an affine map with domain exactly RM , define the fixed coordinate projection πS,M : RM → R3S+1 ,

πS,M (ξ) := (ξ1 , . . . , ξ3S+1 ),

and set A := A0 ◦ πS,M ∈ Aff(M, PΦ ).

If the latent vector supplied by Proposition 4.12 is ξfcore ∈ R3S+1 , take ξf = (ξfcore , 0) ∈ RM , where the appended zero vector has length M − (3S + 1) and may therefore have length zero. Then πS,M (ξf ) = ξfcore . Set θf := A(ξf ). Finally, Proposition 4.12, monotonicity of ωf , and (40) give √

f)−1/d . ∥f − Φθf ∥L∞ ([0,1]d ) ≤ (d + 2)ωf Kd ≤ (d + 2)ωf Cd (P M f = min{M, P }, this is (13). The affine assertion follows from Proposition 4.12 and the Since M fixed projection.

5

Proof of the Hölder lower bound

The lower-bound proof combines a capacity estimate with a packing construction. For every admissible pair (Φ, A) with input dimension d and PΦ ≤ P , recall UΦ from (3) and put e cα := 4−(α+1) 2−α . The first step removes all redundant affine latent coordinate directions: rA = rank(A) ≤ min{M, PΦ }. 39

Counting binary polynomial patterns then gives the capacity estimate Pdim(FΦ,A ) ≤ 8rA (UΦ + 1) ≤ 8P min{M, P }. Finally, binary choices of positive and negative Hölder bumps convert this capacity upper bound into approximation error. With V0 := 8P min{M, P } ≥ 1, the packing lemma gives sup

−α/d

inf ∥f − g∥L∞ ([0,1]d ) ≥ e c α V0

f ∈Hdα g∈FΦ,A

.

The remainder of the section proves these steps in order. Section 5.1 develops the required VC-dimension, pseudo-dimension, and polynomial-pattern tools. Section 5.2 removes redundant latent directions, and Section 5.3 applies the resulting coordinates to the network family. Section 5.4 converts the capacity estimate into a uniform approximation lower bound, and Section 5.5 completes the minimax argument. Throughout the capacity argument, r is the number of effective parameter variables, s bounds the number of Boolean-atom occurrences, dpol bounds their polynomial degree, and m is the number of lifted input and threshold pairs under consideration. The symbol pj is reserved for an atom polynomial, while pi,j denotes that same atom after the ith lifted instance has been fixed.

5.1

VC dimension, pseudo-dimension, and polynomial predicates

To prove the capacity estimate announced above, we first isolate the general combinatorial tools from the network-specific argument. We begin with VC dimension and pseudo-dimension, then develop the Boolean-formula and polynomial sign-pattern bounds used later to analyze FΦ,A . VC dimension and pseudo-dimension The capacity argument concerns binary labelings, although the original function class is realvalued. The required passage has two steps. First, each real-valued function is converted into a binary function on a lifted input (x, t). Second, ordinary VC dimension is applied to the resulting binary class. Pseudo-dimension is exactly the quantity obtained in this way. Let X be a nonempty set, and let C ⊆ {0, 1}X be a binary function class. For a finite set T ⊆ X, its trace is C|T := {c|T : c ∈ C}.

Here c|T is the restriction of c to T , while {0, 1}T denotes the set of all functions from T to {0, 1}. In particular, if |T | = m, then {0, 1}T contains exactly 2m labelings. The set T is shattered by C when every binary labeling of T is realized, that is, C|T = {0, 1}T .

Throughout this section, we use v for binary label vectors. Thus, equivalently, if T = {x1 , . . . , xm } is enumerated without repetition, then for every label vector v = (v1 , . . . , vm ) ∈ {0, 1}m there exists cv ∈ C such that cv (xi ) = vi , i = 1, . . . , m. Let Shat(C) denote the family of finite subsets of X that are shattered by C. The VC dimension is therefore the following quantity: VCdim(C) := sup ({0} ∪ {|T | : T ∈ Shat(C)}) . Thus VCdim(C) is the largest number of points that can be shattered, or +∞ if arbitrarily large finite sets can be shattered. The extra set {0} makes the value equal to zero when no nonempty set is shattered. 40

Now let F ⊆ RX be a real-valued class. Its subgraph class is the binary class  Sub(F) := (x, t) 7→ 1{g(x)>t} : g ∈ F on X × R; in symbols,

Sub(F) ⊆ {0, 1}X×R .

Thus the class to which VC dimension is applied is Sub(F), not the original real-valued class F. Geometrically, for a fixed g, the lifted point (x, t) receives label one exactly when its height t lies strictly below the graph height g(x). Define Pdim(F) := VCdim (Sub(F)) .

(41)

More explicitly, for m ∈ N+ , the inequality m ≤ Pdim(F) holds precisely when there are m distinct lifted points (x1 , t1 ), . . . , (xm , tm ) ∈ X × R

such that, for every label vector v = (v1 , . . . , vm ) ∈ {0, 1}m , there is a function gv ∈ F satisfying 1{gv (xi )>ti } = vi ,

i = 1, . . . , m.

(42)

The base inputs xi must also be pairwise distinct. Otherwise, if xi = xj and ti < tj , the requested label pair (vi , vj ) = (0, 1) would require both g(xi ) ≤ ti and g(xi ) > tj , which is impossible. The case tj < ti is symmetric, while equality would contradict the distinctness of the lifted points. The quantifier order is essential. One first fixes the pairwise distinct lifted instances (xi , ti ); then, for every prescribed label vector v ∈ {0, 1}m , one may choose a function gv ∈ F satisfying (42). In particular, the thresholds ti cannot depend on the desired label vector. For comparison, the zero-threshold class is  Thr0 (F) := x 7→ 1{g(x)>0} : g ∈ F and is obtained by restricting the subgraph class to the slice X × {0}. For a real-valued class, we use the harmless overload VCdim(F ) := VCdim (Thr0 (F)) ,

(43)

where the right-hand side is the ordinary VC dimension of the displayed binary class. Consequently, VCdim(F ) ≤ Pdim(F). (44) Indeed, if Thr0 (F) shatters x1 , . . . , xm , then the lifted points (x1 , 0), . . . , (xm , 0) are shattered by Sub(F). Restricting the allowed lifted points therefore cannot increase VC dimension. The next definition combines two ingredients. A polynomial atom asks one binary question of the form p > 0 and produces one bit; a fixed Boolean rule combines finitely many such bits. We formalize the resulting description in two stages. First, a fixed formula tree is identified with its Boolean map. Definition 5.1 then combines that map with polynomial atoms whose parameter degree is controlled after (x, t) is fixed. The Boolean formula itself need not be a polynomial. Boolean formulas and polynomial predicates Let s0 ∈ N+ . A Boolean formula tree B(Z1 , . . . , Zs0 ) is a finite rooted ordered syntax tree with exactly s0 leaf occurrences. Choose once and for all a bijection between those occurrences and {1, . . . , s0 }, and label the occurrence indexed by j with Zj . Each internal node is one of the fixed operations “not” (¬), “and” (∧), or “or” (∨). If the same polynomial question is used twice in the written formula, its two uses are assigned to two different leaf occurrences 41

and are counted twice. Thus s0 V countsWpositions in the syntax tree, not algebraically distinct polynomials. Whenever a finite or is used below, we fix an ordering of its index set and a binary bracketing. This expands the displayed notation into a formula tree of the preceding kind without changing its truth value or its number of leaf occurrences. We now define the map computed by this tree, rather than leaving the phrase “evaluate the formula” implicit. Let u = (u1 , . . . , us0 ) ∈ {0, 1}s0 . For every subtree ψ, define its value Bψ (u) recursively by BZj (u) := uj , B¬ψ (u) := 1 − Bψ (u). For two subtrees ψ1 and ψ2 , define Bψ1 ∧ψ2 (u) := Bψ1 (u)Bψ2 (u). Also define Bψ1 ∨ψ2 (u) := max{Bψ1 (u), Bψ2 (u)}. Because all subtree values are bits, these equations are exactly the usual truth tables. Applying the recursion at the root defines one map B := BB : {0, 1}s0 → {0, 1}. For example, consider the fixed four-leaf formula Bex := (Z1 ∧ Z2 ) ∨ (Z3 ∧ Z4 ).

(45)

Its associated map is Bex (u1 , u2 , u3 , u4 ) := (u1 ∧ u2 ) ∨ (u3 ∧ u4 ). At u = (1, 0, 1, 1), the recursion gives Bex (1, 0, 1, 1) = (1 ∧ 0) ∨ (1 ∧ 1) = 1. Figure 8 shows the same calculation. Only the four leaf values vary. The connectives, their wiring, and the assignment of the jth input bit to the leaf Zj remain fixed.

0

Bex (µ) = 1

1

∨

µ = (1, 0, 1, 1)

1

∧

∧

Z1

Z2

Z3

Z4

u1 = 1

u2 = 0

u3 = 1

u4 = 1

Figure 8: Evaluation of the fixed formula in (45). The orange boxes supply the changing input bits. The two ∧ gates, the ∨ gate, and every edge of the tree are fixed before the bits are known.

Thus, saying that the Boolean map is fixed means that the formula tree, its connectives, wiring, and leaf labels are all fixed in advance. Once these choices have been made, the recursion above determines B uniquely, and only the s0 leaf bits may vary with (x, t, µ).

42

Definition 5.1 (Boolean-polynomial description). Let d, r, s, dpol ∈ N+ , let X ⊆ Rd , and let F := {gµ : X → R : µ ∈ Rr }. Its joint truth set is S := {(x, t, µ) ∈ X × R × Rr : gµ (x) > t} .

(46)

Choose a number of leaf occurrences s0 with 1 ≤ s0 ≤ s. For each occurrence j = 1, . . . , s0 , choose a polynomial pj ∈ R[x1 , . . . , xd , t, µ1 , . . . , µr ] . We use the standard convention that the zero polynomial has degree −∞; thus identically zero atoms are covered by every nonnegative degree bound below. The jth atom produces the bit Aj (x, t, µ) := 1{pj (x,t,µ)>0} .

(47)

Finally, choose one Boolean formula tree B(Z1 , . . . , Zs0 ) as described above, and let B : {0, 1}s0 → {0, 1} be the map obtained from its recursive evaluation. We say that S has an (s, dpol ) Booleanpolynomial description in the parameter µ when, for every (x, t, µ),
1S (x, t, µ) = B A1 (x, t, µ), . . . , As0 (x, t, µ) , (48) and, for each fixed (x, t), degµ pj (x, t, ·) ≤ dpol ,

j = 1, . . . , s0 .

The integer s is only an upper bound; s0 is the number of leaf occurrences actually used after all comparisons have been written in the strict-positivity form of (47). Every object defining the rule (s0 , the polynomials pj , the formula tree B, its map B, and the assignment of atoms to leaves) is chosen before (x, t, µ) is given. Only the atom bits in (47), and hence the final output bit, vary with the arguments. If the same polynomial comparison is written twice, its two appearances occupy two different leaf slots and count as two atom occurrences. They may produce identical bits, but the formula still has two syntactic leaves. Restricting atoms to strict positivity loses no Boolean expressive power. For any real polynomial p, the other standard comparisons are represented by 1{p≤0} = 1 − 1{p>0} .

1{p<0} = 1{−p>0} , Similarly, 1{p≥0} = 1 − 1{−p>0} ,

1{p=0} = 1 − 1{p>0} 1 − 1{−p>0} .

These are identities for every real value of p, including p = 0. Accordingly, an equality may create two strict-positivity leaf occurrences; the atom count is always taken after this normalization. For example, the predicate   ¬(−p > 0) ∧ (q > 0) ∨ (−p > 0) has three leaf occurrences after normalization, even though only the two polynomials −p and q occur. The strict-positivity question for −p is used twice and is therefore counted twice. This distinction is why the definition counts syntax-tree occurrences rather than distinct polynomial expressions. Here is a concrete instance that also previews the network application. Let
gµ (x) := a(µ)ϱ w(µ)x + b(µ) + c(µ), z(x, µ) := w(µ)x + b(µ),

43

where a, w, b, c are affine functions of µ. The inequality gµ (x) > t is equivalent to     ¬(−z > 0) ∧ (az + c − t > 0) ∨ (−z > 0) ∧ (c − t > 0) ,

(49)

where the arguments have been suppressed inside the formula. Thus its four leaf occurrences may be substituted for Z1 , . . . , Z4 : the question −z > 0 occupies both Z1 and Z3 , while the two output comparisons occupy Z2 and Z4 . The Boolean map is   B(u1 , u2 , u3 , u4 ) := (¬u1 ) ∧ u2 ∨ (u3 ∧ u4 ). It is fixed for every (x, t, µ); only the four supplied bits change. Because ¬(−z > 0) is exactly z ≥ 0, the formula assigns the boundary z = 0 to the active branch, where ϱ(0) = 0. For fixed (x, t), each of the four polynomial-atom occurrences in (49) has degree at most two in µ, so this is a (4, 2) Boolean-polynomial description. The network proof below will use exactly this active-branch/inactive-branch idea for every hidden unit. Polynomial sign-pattern bounds We now state the only external algebraic result used in the capacity part of the lower-bound proof. We use a convenient weakened form of Warren’s standard strict-sign theorem (Warren, 1968, Theorem 3); see also (Goldberg and Jerrum, 1995, Theorem 2.1). The classical estimate 2(2edpol n/r)r implies the slightly looser bound below because r ≥ 1. Theorem 5.2 (Warren’s strict-sign theorem). Let r, n, dpol ∈ N+ with n ≥ r, and let q1 , . . . , qn be n distinct nonzero real polynomials in r variables, each of total degree at most dpol . A vector σ = (σ1 , . . . , σn ) ∈ {−1, 1}n is a consistent nonzero sign assignment if there exists µ ∈ Rr such that σj qj (µ) > 0 for every j. The number of such assignments satisfies    4edpol n r n r σ ∈ {−1, 1} : there exists µ ∈ R such that σj qj (µ) > 0 for every j ≤ . (50) r The strict inequalities in (50) exclude all points at which one of the polynomial values vanishes. The form needed later is the following indexed consequence, which also permits repeated polynomials. Corollary 5.3 (Indexed Warren bound for strict-positivity patterns). Let r, n, dpol ∈ N+ with n ≥ r, and let q1 , . . . , qn be nonzero real polynomials in r variables, each of total degree at most dpol . The number of binary patterns realized at points where none of the evaluated polynomials vanishes satisfies   
4edpol n r 1{q1 (µ)>0} , . . . , 1{qn (µ)>0} : µ ∈ Rr , qj (µ) ̸= 0 for every j ≤ . (51) r Proof. At the parameter points counted in (51), every polynomial value is either positive or negative. The indicator records the positive case by 1 and the negative case by 0. Thus these are precisely the positive/negative sign patterns counted by Warren’s theorem. A polynomial may vanish at other points, and the indexed list need not consist of algebraically distinct polynomials. The displayed statement is formulated for an indexed family and therefore allows algebraic repetitions. To recover it from a version stated for a set of distinct polynomials, retain one representative of each distinct polynomial and let N ≤ n be the number retained. The full indexed vector is determined by the resulting N -vector. If N ≥ r, Theorem 5.2 for the distinct family gives     4edpol N r 4edpol n r ≤ . r r

44

If N < r, the trivial bound gives N

2

r



≤2 ≤

4edpol n r

r ,

because dpol ≥ 1 and n ≥ r. Thus the indexed version follows from Theorem 5.2; the argument also covers repeated polynomials and the endpoint n = r. Closely related binary-threshold formulations appear in (Bartlett et al., 1998, Lemma 1), (Anthony and Bartlett, 1999, Theorem 8.3), and (Bartlett et al., 2019, Lemma 17). The version needed here permits zero values and groups them with the nonpositive outcome. For geometric intuition, each equation pj (µ) = 0 describes an algebraic zero set in parameter space. On every connected component of the complement of their union, the binary positivity vector is constant, but different components may carry the same vector. (51) bounds the number of distinct realized positivity vectors, not the number of connected regions. This geometric picture is not used in the proof. The argument below uses Corollary 5.3, which follows from Theorem 5.2, and does not rely on a count of connected regions. The following lemma establishes this version by choosing a single perturbation size that works simultaneously for every realized binary pattern. Lemma 5.4 (Binary polynomial positivity patterns). Let r, n, dpol ∈ N+ with n ≥ r. Let p1 , . . . , pn be arbitrary real polynomials in r variables, each of total degree at most dpol . Then   
4edpol n r r 1{p1 (µ)>0} , . . . , 1{pn (µ)>0} : µ ∈ R ≤ . (52) r The list may contain repeated polynomials or the zero polynomial. Proof. The idea is to move every polynomial downward by the same small number. At one carefully selected witness for each realized bit vector, positive values remain positive, while zero and negative values become strictly negative. Corollary 5.3, and hence Theorem 5.2, can then count these strict binary patterns. Step 1: Choose one witness for each realized binary pattern. Let B denote the set on the left side of (52). It is finite because B ⊆ {0, 1}n . For every v = (v1 , . . . , vn ) ∈ B, choose one representative µv ∈ Rr such that 1{pj (µv )>0} = vj ,

j = 1, . . . , n.

Step 2: Choose one perturbation size that works for every witness. Consider the finite collection of positive witness values V+ := {pj (µv ) : v ∈ B, 1 ≤ j ≤ n, pj (µv ) > 0} . If V+ is empty, every realized binary pattern is the all-zero vector. Hence |B| = 1, which is no larger than the right side of (52); the proof is complete in this case. Assume that V+ is nonempty. Being a finite set of positive real numbers, it has a positive minimum. Set a∗ a∗ := min V+ > 0, δ := . 2

45

Step 3: Shift every polynomial downward and preserve all witness bits. For j = 1, . . . , n, define qj := pj − δ. Each qj has degree at most dpol . We first check that it is not the zero polynomial. If qj were identically zero, then pj ≡ δ > 0. The value δ would then belong to V+ , so a∗ ≤ δ = a∗ /2, a contradiction. Fix v ∈ B and j ∈ {1, . . . , n}. If vj = 1, then pj (µv ) ∈ V+ and hence pj (µv ) ≥ a∗ = 2δ. Therefore qj (µv ) ≥ δ > 0. If vj = 0, then pj (µv ) ≤ 0, so qj (µv ) ≤ −δ < 0. In both cases, 1{qj (µv )>0} = vj ,

qj (µv ) ̸= 0.

Thus the original bit vector v is reproduced exactly by the shifted polynomials at its selected witness. Step 4: Apply the indexed consequence of Warren’s theorem. The preceding identity shows that distinct vectors in B give distinct strict-positivity patterns of q1 , . . . , qn at parameter points where all qj are nonzero. Consequently, B injects into the set counted in (51). The hypotheses of Corollary 5.3 hold: n ≥ r, every qj is nonzero by Step 3, and its degree is at most dpol . Therefore,   4edpol n r |B| ≤ . r This is (52). Repetitions in the original list and identically zero original polynomials cause no problem: the argument treats the list by indexed occurrences, and the common downward shift makes every qj a nonzero polynomial. From polynomial predicates to pseudo-dimension The following proposition adapts the counting argument underlying (Goldberg and Jerrum, 1995, Theorem 2.2) to subgraph classes instead of invoking that theorem directly. Goldberg and Jerrum formulate an ordinary VC-dimension result, count distinct atomic predicates, and use three-way sign assignments, leading to the constant 8e. Here atoms are normalized to binary strict-positivity tests, syntactic leaf occurrences are counted, and Lemma 5.4 groups zero with the nonpositive outcome. This gives the constant 4e below. The network result in (Bartlett et al., 2019, Theorem 7 and Lemma 17) is not invoked. Proposition 5.5 (Polynomial-predicate pseudo-dimension bound). Let F = {gµ : X → R : µ ∈ Rr }, where X ⊆ Rd and d, r ∈ N+ . If its joint truth set admits an (s, dpol ) Boolean-polynomial description in the sense of Definition 5.1, then Pdim(F) ≤ 2r log2 (4edpol s) .

(53)

Proof. Fix one (s, dpol ) Boolean-polynomial description of the joint truth set. Retain the notation s0 , pj , B, and B from Definition 5.1. In particular, s0 is the actual number of leaf occurrences and s0 ≤ s. Fix m ∈ N+ for which the explicit labeling property in (42) holds. We prove that m satisfies (53). The functions gµ themselves need not be global polynomials in µ. Only the binary predicate gµ (x) > t must have the stated Boolean-polynomial description. Once the lifted instances (xi , ti ) have been fixed, every relevant polynomial depends only on the parameter variable µ.

46

When ms0 ≥ r, the counting argument reduces to the chain  4edpol ms r 2 ≤ |realized polynomial bit patterns| ≤ . |{z} | {z } r all requested labels | {z } information available from the atoms 

m

(54)

binary Warren bound

Steps 1 through 4 justify this chain, and Step 5 solves the remaining scalar inequality for m. The easier case ms0 < r is handled at the beginning of Step 4. Step 1: Fix the lifted instances and take parameter-space sections. The purpose of this step is to turn (42) into a numerical requirement: varying the parameter must produce all 2m binary membership vectors. The joint set S records every triple for which gµ (x) > t is true, while a section fixes (x, t) and keeps only the parameters giving that answer. By the defining property of the selected m, there are fixed lifted instances (x1 , t1 ), . . . , (xm , tm ) ∈ X × R on which all 2m label vectors are realized. For an arbitrary lifted instance (x, t), define the corresponding parameter section of the joint truth set by Sx,t := {µ ∈ Rr : (x, t, µ) ∈ S}. By (46), this section is Sx,t = {µ ∈ Rr : gµ (x) > t}.

It is a semialgebraic subset of Rr , because (48) describes it using finitely many polynomial comparisons in µ. Here “semialgebraic” means a finite Boolean combination of sets defined by polynomial equalities and inequalities. For the fixed lifted instances, write Si := Sxi ,ti ,

i = 1, . . . , m.

Define the label map Lab : Rr → {0, 1}m by Lab(µ) := (1S1 (µ), . . . , 1Sm (µ)) . Equivalently, its ith coordinate is Labi (µ) = 1{gµ (xi )>ti } . For every v ∈ {0, 1}m , (42) supplies a parameter µv ∈ Rr for which Lab(µv ) = v. Consequently, the set of realized label vectors is Y := Lab(Rr ) = {0, 1}m ,

|Y| = 2m .

(55)

Step 2: Collect the parameter polynomials. We now freeze the lifted instances. This removes the input and threshold from the list of variables, leaving a finite family of ordinary polynomials in µ to which a binary pattern theorem can later be applied. For each lifted instance and each atom occurrence, define pi,j (µ) := pj (xi , ti , µ),

i = 1, . . . , m, 47

j = 1, . . . , s0 .

Every pi,j is a polynomial in the r coordinates of µ, and degµ pi,j ≤ dpol . The natural occurrence index set is I := {1, . . . , m} × {1, . . . , s0 }. Its cardinality satisfies |I| = ms0 ≤ ms. There are s0 atom occurrences for each of the m fixed lifted instances; hence the indexed list contains ms0 polynomials. Two members of this list may coincide, and some may be identically zero. This causes no problem: Lemma 5.4 was stated for an indexed list and explicitly allows both possibilities. Step 3: Show that polynomial bits determine every label. This step proves that the labels contain no more combinatorial information than the simultaneous strict-positivity bits of the collected polynomials. Define the simultaneous bit map BitI : Rr → {0, 1}I by   BitI (µ) := 1{pi,j (µ)>0}

(i,j)∈I

.

Let B := BitI (Rr ) be the set of realizable bit patterns. It contains only patterns attained by some parameter and need not equal the full cube {0, 1}I . A fiber of BitI may be disconnected; the proof counts bit patterns, not connected components. We now define, rather than merely assert, the map from atom bits to labels. For χ = (χi,j )(i,j)∈I ∈ {0, 1}I , set Hi (χ) := B (χi,1 , . . . , χi,s0 ) ,

i = 1, . . . , m,

and then set H(χ) := (H1 (χ), . . . , Hm (χ)) . For every parameter µ, (48) gives the exact factorization Lab = H ◦ BitI . In words, the information flows as   µ 7−→ 1{pi,j (µ)>0}

(i,j)∈I

7−→ Lab(µ).

Thus each realized bit pattern determines exactly one label vector, although different bit patterns may determine the same label vector. Therefore |Y| ≤ |B|.

(56)

2m ≤ |B|.

(57)

Combining (55) and (56) gives

48

Step 4: Apply the binary polynomial-pattern estimate. We first remove the only small-count case. If ms0 < r, then s0 ≥ 1 implies m < r. Since dpol , s ≥ 1, we have m < r < 2r log2 (4edpol s), so the desired estimate already holds. Assume from now on that ms0 ≥ r. Apply Lemma 5.4 directly to the indexed list (pi,j )(i,j)∈I . The list has ms0 members, each of degree at most dpol , and the lemma allows repeated polynomials as well as polynomials that are identically zero. We obtain     4edpol ms0 r 4edpol ms r |B| ≤ ≤ . (58) r r The first inequality is precisely where polynomial geometry enters. Lemma 5.4 preserves Warren’s constant 4 because a single downward shift groups zero and negative values into the same binary outcome. (57) and (58) imply   4edpol ms r m 2 ≤ . (59) r Thus (54) has been justified. The sole external algebraic input was Theorem 5.2; the all-points binary lemma used here was derived from it above. Step 5: Solve the resulting scalar inequality. The unknown m still appears on the right side of the counting inequality. We now remove it by an elementary one-variable estimate. Set m u := . r Also put a := 4edpol s. Taking base-two logarithms on both sides of (59) and dividing by r gives   4edpol ms m ≤ r log2 . r Substituting m = ru and a = 4edpol s turns this into u ≤ log2 a + log2 u.

(60)

Notice that a ≥ 4e > 4. If u ≤ a, then log2 u ≤ log2 a, and (60) implies u ≤ 2 log2 a. If u > a, then log2 a < log2 u, so (60) would imply u < 2 log2 u. However, u > a > 4 and the elementary inequality 2 log2 u ≤ u holds for every u ≥ 4. For completeness, define ψ(u) := u − 2 log2 u. Then ψ(4) = 0, and for u ≥ 4, ψ ′ (u) = 1 −

2 1 ≥1− > 0. u ln 2 2 ln 2 49

Hence ψ(u) ≥ 0 on [4, ∞), proving the claimed elementary inequality and contradicting u < 2 log2 u. Thus in all cases m ≤ 2r log2 (4edpol s) . Together with the small-count case handled at the start of Step 4, this bounds every integer m satisfying the explicit labeling property in (42). Taking the supremum in (41) proves (53), without assuming in advance that the pseudo-dimension is finite.

5.2

Effective latent coordinates

Proposition 5.5 measures complexity in terms of the variables that genuinely affect the predicate. In the present model, using the nominal latent dimension M would fail to capture the saturation at M = P , since directions in the kernel of A do not affect the generated parameters. Before analyzing the network computation, we therefore parameterize A(RM ) = Range(A) + a using rA = rank(A) effective coordinates. Lemma 5.6 (Rank reduction for an affine latent parameterization). Let Φ be an architecture and let A ∈ Aff(M, PΦ ) be given by A(ξ) = Aξ + a. Put rA := rank(A). If rA ≥ 1, there is a full-column-rank matrix R ∈ RPΦ ×rA such that A(RM ) = {Rµ + a : µ ∈ RrA } .

(61)

Define the complete parameter vector in effective coordinates by θ(µ) := Rµ + a. Consequently,  FΦ,A = Φθ(µ) : µ ∈ RrA . If rA = 0, the family contains exactly one realized function. Proof. The purpose of the reduction is to replace the nominal latent vector by coordinates on the range of A. We use only an elementary rank factorization and verify surjectivity explicitly, so no matrix-decomposition theorem is needed. Assume first that rA ≥ 1. Choose rA linearly independent columns of A that form a basis of Range(A), and place them in R ∈ RPΦ ×rA . This matrix has full column rank. Every column of A has a unique coordinate vector in the chosen basis. Placing these coordinate vectors side by side produces a matrix C ∈ RrA ×M such that A = RC. The matrix C has rank rA . Indeed, rA = rank(A) ≤ rank(C) ≤ rA . Consequently, C contains an invertible rA × rA submatrix: Gaussian elimination produces rA pivot columns because C has full row rank. Given any µ ∈ RrA , solve the corresponding square system for those rA coordinates of ξ and set all remaining coordinates to zero. This gives Cξ = µ. Hence the map ξ 7→ Cξ is onto RrA .

50

To verify the image identity, we prove the two inclusions separately. If ξ ∈ RM , then Aξ + a = R(Cξ) + a, so the left-hand image is contained in the right-hand image. Conversely, if µ ∈ RrA , surjectivity supplies ξ ∈ RM with Cξ = µ, and hence Rµ + a = Aξ + a. Therefore  Aξ + a : ξ ∈ RM = {Rµ + a : µ ∈ RrA } , which is (61). Substitution into (5) gives the identity of realized function families. If rA = 0, then every column of A is zero, so A = 0 and A(ξ) = a for every ξ ∈ RM . Hence FΦ,A = {Φa } is a singleton.

5.3

Pseudo-dimension under affine parameter tying

The rank reduction identifies the correct parameter space. We next bound the binary complexity generated by the fixed ReLU architecture as the effective coordinates vary. For each activation pattern, the network output is polynomial in those coordinates; we then combine all patterns into a single Boolean formula for the subgraph predicate. Throughout the next lemma, the architecture Φ and the affine map A remain fixed. In the positive-rank case, we also choose once and for all one basis matrix R supplied by Lemma 5.6. This choice is made before the input, threshold, effective parameter vector, or desired labeling is specified. Consequently, the entries of R and a are fixed coefficients; only µ ∈ RrA varies. Lemma 5.7 (Pseudo-dimension after affine parameter tying). Let Φ be a fully connected d-input ReLU architecture with at least one hidden unit, let PΦ be its number of scalar weight and bias entries, and let A ∈ Aff(M, PΦ ). If UΦ is the total number of hidden ReLU units, then VCdim(FΦ,A ) ≤ Pdim(FΦ,A ) ≤ 8rA (UΦ + 1) ≤ 8rA PΦ .

(62)

In particular, if PΦ ≤ P , then Pdim(FΦ,A ) ≤ 8P min{M, P }.

(63)

Proof. The proof has five components. We first pass from the nominal latent vector to rA effective variables. For each fixed global activation pattern, we then define a formal forward pass consisting entirely of polynomials. A layerwise induction controls their degree in the effective parameters after the lifted instance (x, t) is fixed. A second induction verifies an exact, boundary-aware Boolean formula for the subgraph predicate Φθ (x) > t. Finally, Proposition 5.5 converts the number and degree of the polynomial predicates into the claimed pseudo-dimension bound. Figure 9 records this logical chain. affine family A(ξ) ξ ∈ RM

remove redundant directions µ ∈ RrA , rA ≤ min{M, PΦ }

fix (x, t) and induct over layers parameter degree at most LΦ + 1

fix an activation pattern σ formal preactivations and output are polynomials

disjoin all 2UΦ pattern clauses at most (UΦ + 1)2UΦ predicate occurrences

binary polynomial count Pdim ≤ 8rA (UΦ + 1) ≤ 8rA PΦ

Figure 9: From affine parameter tying to the pseudo-dimension bound. Redundant latent-coordinate directions are removed before the network is represented, pattern by pattern, by polynomial predicates in only rA effective variables. The exponential number of activation patterns appears inside a logarithm in Proposition 5.5.

51

Step 1: Reduce to effective affine coordinates. The purpose of this step is to ensure that the number of variables entering the polynomialpattern theorem is the true affine rank, rather than the possibly redundant latent-vector length M. If rA = 0, Lemma 5.6 shows that FΦ,A is a singleton. For any fixed pair (x, t), a singleton realizes only one of the two labels, so the one-point condition in (42) fails. Its pseudo-dimension is zero, and the inequalities are immediate. Assume henceforth that rA ≥ 1. By Lemma 5.6, every parameter vector in the affine image has the form θ(µ) = Rµ + a, µ ∈ Rr A . From this point onward, R denotes the fixed choice made before the proof. Although a basis of Range(A) need not be unique, no later choice of R may depend on (x, t, µ) or on a labeling to be realized. Every scalar layer weight and bias is consequently an affine polynomial in µ. Using the fixed ordering of the PΦ dense parameter entries, denote these coordinate functions by wℓ,j,k (µ)

and

bℓ,j (µ),

ℓ = 1, . . . , LΦ + 1.

Each has total degree at most one in µ. The one-unit calculation in (49) already exhibits the two ideas needed below: fix a branch, on which the ReLU becomes polynomial, and then join the branch clauses by one Boolean formula. We now carry out those two operations simultaneously for every hidden unit of the network. Step 2: Define a formal polynomial forward pass for every activation pattern. The purpose of fixing a pattern is to replace every nonlinear ReLU branch by one polynomial expression. We will later use Boolean logic to combine the finitely many patterns. Let n1 , . . . , nLΦ be the hidden widths, recall that n0 = d, and recall UΦ = |UΦ | from (3). A global activation pattern is a binary array σ = (σℓ,j ) ∈ {0, 1}UΦ ,

1 ≤ ℓ ≤ LΦ ,

1 ≤ j ≤ nℓ .

The entry σℓ,j = 1 will represent an active unit, and σℓ,j = 0 an inactive unit. Fix one pattern σ. We define candidate preactivations and activations recursively without applying the nonlinear ReLU function. At the input, set hσ 0,k (x, µ) := xk ,

k = 1, . . . , d.

For a hidden unit (ℓ, j), define nℓ−1 σ zℓ,j (x, µ) :=

X

wℓ,j,k (µ)hσ ℓ−1,k (x, µ) + bℓ,j (µ).

k=1

Its formal postactivation is σ hσ ℓ,j (x, µ) := σℓ,j zℓ,j (x, µ).

Thus an active formal gate transmits its candidate preactivation, while an inactive formal gate returns the zero polynomial. After the last hidden layer, define the formal scalar output nLΦ

oσ (x, µ) :=

X

wLΦ +1,1,k (µ)hσ LΦ ,k (x, µ) + bLΦ +1,1 (µ).

k=1

For a fixed pattern, every displayed object is now an ordinary polynomial in (x, µ).

52

Step 3: Fix the lifted instance and prove the parameter-degree bound. We now verify the degree condition in Definition 5.1. Once the lifted instance (x, t) is fixed, x1 , . . . , xd , t are constants, and only the effective parameter vector µ remains variable. Therefore degµ hσ 0,k ≤ 0,

degµ wℓ,j,k , degµ bℓ,j ≤ 1.

It follows immediately that σ degµ z1,j , degµ hσ 1,j ≤ 1.

Suppose for some ℓ ≥ 2 that degµ hσ ℓ−1,k ≤ ℓ − 1

(k = 1, . . . , nℓ−1 ).

Then every product in the layer satisfies
degµ wℓ,j,k (µ)hσ ℓ−1,k (x, µ) ≤ 1 + (ℓ − 1) = ℓ. Taking finite sums and adding the affine bias gives σ degµ zℓ,j , degµ hσ ℓ,j ≤ ℓ. σ The last inequality uses only that hσ ℓ,j = σℓ,j zℓ,j and σℓ,j ∈ {0, 1} is fixed. At the output layer, one further multiplication by an affine weight gives

degµ oσ ≤ LΦ + 1. Since t is fixed, subtracting it does not increase the parameter degree: degµ (oσ − t) ≤ LΦ + 1. Collecting the preceding bounds, for every fixed lifted instance (x, t) and activation pattern σ, the relevant polynomials satisfy polynomial in µ

degree bound

hσ 0,k = xk wℓ,j,k (µ), bℓ,j (µ) σ , hσ zℓ,j ℓ,j oσ − t

≤0 ≤1 ≤ℓ ≤ LΦ + 1

Step 4: Encode the exact forward-pass pattern, including zero preactivations. This step combines the separate polynomial pieces into one exact Boolean description and checks the boundary case of a zero preactivation. We use the deterministic convention active if the preactivation is nonnegative,

inactive if it is negative.

The nonnegative/strict-negative convention assigns every preactivation to a unique branch. Since ϱ(0) = 0, treating a zero preactivation as active does not alter the numerical network output. For a bit a ∈ {0, 1} and a Boolean statement E, define the literal ( E, a = 0, Λa (E) := ¬E, a = 1. 53

For a fixed pattern σ, use the strict-positivity statement σ −zℓ,j (x, µ) > 0

at each hidden unit. This statement is true exactly when the formal preactivation is negative. Define the consistency formula ^
σ Cσ (x, µ) := Λσℓ,j −zℓ,j (x, µ) > 0 . (64) (ℓ,j)∈UΦ

σ < 0. When σ Indeed, when σℓ,j = 0, the corresponding literal says zℓ,j ℓ,j = 1, its negation says σ zℓ,j ≥ 0. Thus every consistency leaf is of the required strict-positivity form; weak nonnegativity is supplied by Boolean negation. We verify carefully that this formula is equivalent to σ being the actual activation pattern. σ is exactly the actual preacFirst suppose that Cσ (x, µ) holds. At the first hidden layer, z1,j tivation because both are computed from the same input and generated first-layer parameters. σ ≥ 0, and hence If σ1,j = 1, consistency gives z1,j σ σ ϱ(z1,j ) = z1,j = hσ 1,j . σ < 0, and hence If σ1,j = 0, consistency gives z1,j σ ϱ(z1,j ) = 0 = hσ 1,j .

Thus the formal and actual first-layer states agree. If they agree through layer ℓ − 1, their layer-ℓ affine preactivations also agree. The same two-case argument then shows that their postactivations agree in layer ℓ. Induction proves agreement through the last hidden layer, and the formal output oσ is therefore the actual scalar network output. Conversely, start from the actual forward pass for a fixed (x, µ) and define σℓ,j = 1 exactly when its actual preactivation is nonnegative. The same induction shows that the associated formal preactivations equal the actual ones. They consequently satisfy the appropriate weak or strict inequalities in (64). Hence the actual forward pass produces exactly one consistent pattern. For every pattern, combine consistency and the output comparison into the clause
Dσ (x, t, µ) := Cσ (x, µ) ∧ oσ (x, µ) − t > 0 . For an arbitrary threshold t ∈ R, the exact subgraph predicate is _ Φθ(µ) (x) > t ⇐⇒ Dσ (x, t, µ). σ∈{0,1}UΦ

To connect this predicate explicitly to Definition 5.1, introduce one propositional variable Zσ,ℓ,j for the consistency atom associated with (σ, ℓ, j), and one variable Zσ,out for its output atom. For a propositional variable Z, use the same literal notation ( Z, a = 0, Λa (Z) := ¬Z, a = 1. First define the formula for one pattern by  ^  cσ := Λσℓ,j (Zσ,ℓ,j ) ∧ Zσ,out . (ℓ,j)∈UΦ

54

The single fixed formula for the whole network is then _ cσ . BΦ := σ∈{0,1}UΦ

Fix lexicographic orderings of the pattern set and of UΦ , together with the binary bracketings stipulated above. Enumerate the leaf occurrences of BΦ in that fixed order as 1, . . . , sΦ , where sΦ := (UΦ + 1)2UΦ . σ (x, µ) and with each Associate with each consistency-leaf occurrence its joint polynomial −zℓ,j output-leaf occurrence its joint polynomial oσ (x, µ) − t. Because (Φ, A, R) and all orderings have already been fixed, this produces one indexed list

p 1 , . . . , p sΦ before (x, t, µ) is given. Algebraically identical polynomials arising at different leaf occurrences remain separately indexed. At a triple (x, t, µ), substitute the truth value σ (x,µ)>0} 1{−zℓ,j

for Zσ,ℓ,j . Substitute 1{oσ (x,µ)−t>0} for Zσ,out . The preceding equivalence now says exactly that the indicator of the subgraph predicate equals the evaluation of BΦ at these atom truth values. At every fixed triple (x, t, µ), exactly one consistency formula is true: its pattern declares a zero preactivation active and every negative preactivation inactive. Thus exactly one pattern clause can survive the consistency tests, and the disjunction compares the output polynomial from that unique formal branch with t. This also verifies exactness on activation boundaries, not merely at points where all preactivations are nonzero. The Boolean map associated with this fixed formula is BΦ := BBΦ : {0, 1}sΦ → {0, 1}, where sΦ is the number of leaf occurrences introduced above and counted explicitly in Step 5. After the truth values of all the Z-variables are supplied, BΦ returns 1 exactly when at least one complete pattern clause is true. The formula and its map depend only on the fixed finite index set of the architecture. The atom polynomials also depend on the fixed affine map, but neither the formula nor the polynomial list is selected after seeing (x, t, µ). Equivalently, define the network truth set n o SΦ,A := (x, t, µ) ∈ Rd × R × RrA : Φθ(µ) (x) > t . For each fixed lifted instance (x, t), its parameter section is  (SΦ,A )x,t = µ ∈ RrA : Φθ(µ) (x) > t . The displayed disjunction gives a finite semialgebraic description of this section. The network output need not be one global polynomial in µ: each activation pattern contributes a polynomial piece, and the fixed disjunction combines all pieces into one exact description of membership in SΦ,A . The formula is fixed once (Φ, A) is fixed; it is not chosen after seeing (x, t) or µ.

55

Step 5: Count predicates and apply Proposition 5.5. It remains to identify the two syntactic quantities required by Definition 5.1: the number of atom occurrences and their maximum degree in µ. The pattern set has cardinality {0, 1}UΦ = 2UΦ . Each pattern contributes UΦ consistency-atom occurrences and one output comparison. Hence the complete formula has exactly sΦ = (UΦ + 1)2UΦ leaf occurrences, as introduced in Step 4. Set dnet := LΦ + 1. By Step 3, every atom has degree at most dnet in µ. Since every hidden layer is nonempty, 1 ≤ LΦ ≤ UΦ . It follows that dnet ≤ UΦ + 1.

The occurrence count is syntactic: if the same preactivation polynomial appears in two different pattern clauses, both appearances are counted, as required by Definition 5.1. Applying Proposition 5.5 with r = rA yields Pdim(FΦ,A ) ≤ 2rA log2 (4ednet sΦ ) . Substituting the two preceding bounds gives
Pdim(FΦ,A ) ≤ 2rA log2 4e(UΦ + 1)2 2UΦ . Expanding this logarithm yields Pdim(FΦ,A ) ≤ 2rA [UΦ + log2 (4e) + 2 log2 (UΦ + 1)] . Because the architecture has at least one hidden unit, UΦ ≥ 1. For UΦ ≥ 1, log2 (4e) < 4,

log2 (UΦ + 1) ≤ UΦ .

The bracket is therefore bounded by 3UΦ + 4 ≤ 4(UΦ + 1). Consequently, Pdim(FΦ,A ) ≤ 8rA (UΦ + 1).

Together with (44), this proves the first two inequalities in (62). It remains to express the result using the parameter-slot budget. By the fully connected architecture convention, every hidden unit has its own bias slot. These account for UΦ distinct slots, and the scalar output layer has one further bias slot. All of these slots are counted in PΦ , even when their assigned values are fixed or zero. Therefore UΦ + 1 ≤ PΦ , and the last inequality in (62) follows. Finally, (6) and PΦ ≤ P give rA ≤ min{M, PΦ } ≤ min{M, P }, and hence This is (63).

8rA PΦ ≤ 8P min{M, P }.

56

The preceding proof also explains the form of the result. The factor rA is the number of independent real directions in which the generated parameter vector can move. The factor UΦ +1, and hence the coarser factor PΦ , measures the amount of piecewise-polynomial computation performed by the fixed deployed network. Although there are 2UΦ possible activation patterns, this quantity occurs inside the logarithm in Proposition 5.5, since log2 (2UΦ ) = UΦ . Thus the enumeration of activation patterns does not produce an exponential pseudo-dimension bound. Remark 5.8 (Piecewise-polynomial activations). For context, although this paper uses the ReLU activation ϱ throughout, the same binary-predicate argument extends to any fixed activation ρ with finitely many polynomial pieces. More precisely, suppose that Jρ ∈ N+ intervals partition R, with every breakpoint assigned to exactly one adjacent interval, and that on each interval ρ agrees with a polynomial of degree at most an integer qρ ≥ 0. Consider an architecture with L hidden layers, U hidden units, and positive effective affine parameter dimension r ≥ 1. Define
Dρ,0 := 0, Dρ,ℓ := qρ Dρ,ℓ−1 + 1 , ℓ = 1, . . . , L, Dρ,∗ := Dρ,L + 1. For a fixed global piece pattern, induction over the layers shows that a formal postactivation in layer ℓ has parameter degree at most Dρ,ℓ : forming its affine preactivation raises the degree bound from Dρ,ℓ−1 to at most Dρ,ℓ−1 + 1, and substitution into a polynomial piece of degree at most qρ gives the displayed recursion. The interval-consistency atoms use the preactivations, while the final output atom has degree at most Dρ,L + 1. Hence all atom degrees are bounded by Dρ,∗ . When qρ ≥ 1, the recursion gives Dρ,ℓ ≥ Dρ,ℓ−1 + 1, so Dρ,∗ dominates every preactivation degree from every layer. When qρ = 0, every formal postactivation is constant on its selected piece and every preactivation atom has degree at most one, which is again covered by Dρ,∗ = 1. There are at most JρU global piece patterns. For each unit, membership of its preactivation in the selected interval requires at most two strict-positivity atom occurrences, and the output comparison requires one additional occurrence. Consequently, the same argument gives
Pdim(FΦ,A ) ≤ 2r log2 4eDρ,∗ (2U + 1)JρU . The fixed breakpoint convention keeps the Boolean branch description exact even when a preactivation equals a breakpoint. A formal proof would repeat Steps 2 through 5 above and is omitted because no theorem in this paper uses a non-ReLU activation. For ReLU, the specialized argument above gives the simpler and sharper estimate. If the effective affine dimension is zero, the realized family is a singleton and has pseudo-dimension zero, as in Step 1.

5.4

From pseudo-dimension to a uniform lower bound

This completes the capacity part of the lower bound. We now show that any real-valued function class with this capacity bound must fail to approximate at least one member of the Hölder ball. The mechanism is a family of disjoint tents whose signs can be chosen independently: uniformly accurate approximation of every such choice would force the zero-threshold class to realize too many binary labelings. The construction below yields an explicit constant. A related VC-dimension argument appears in (Shen et al., 2022d, Theorem 2.4); the proof given here is self-contained and does not invoke that result. Lemma 5.9 (Hölder bump packing). Let d ∈ N+ and 0 < α ≤ 1, and let F ⊆ C(Rd ) be a real-valued function class. Let V ∈ [1, ∞) satisfy VCdim(F ) ≤ V. Then sup inf ∥f − g∥L∞ ([0,1]d ) ≥ e cα V −α/d .

f ∈Hdα g∈F

Here, as above, e cα := 4−(α+1) 2−α . 57

(65)

Proof. We place disjoint Hölder tents on a regular grid and choose one binary label at each center. The label determines whether the corresponding tent is positive or negative. Every resulting sum remains in the unit Hölder ball. If every such target admitted an approximation with error less than half its absolute value at the centers, the zero-threshold class would realize every binary labeling of those centers. Choosing more centers than V then gives a contradiction. If F is empty, the inner infimum in (65) is +∞, so the result is immediate. Assume henceforth that F is nonempty. As specified in Section 3.1, the displayed L∞ ([0, 1]d ) norm is the pointwise uniform norm, and the error bound may therefore be evaluated at every grid center. Step 1: Choose more centers than the VC dimension at threshold zero. Set 1 R := ⌊V 1/d ⌋ + 1, h := . 4R Since V ≥ 1, we have R ≥ 2. Moreover, R = ⌊V 1/d ⌋ + 1 > V 1/d , so Rd > V ≥ VCdim(F). Introduce the center index set J := {1, . . . , R}d ,

|J | = Rd .

For every multi-index i = (i1 , . . . , id ) ∈ J , define   2i1 − 1 2id − 1 xi := ,..., . 2R 2R There are exactly |J | = Rd centers. Each center has distance at least 1/(2R) = 2h from the boundary of the cube in the maximum norm. Two distinct centers have distance at least 1/R = 4h in that norm. It follows that the closed balls of radius h in the maximum norm around the centers lie inside [0, 1]d and that any two such balls are separated by distance at least 2h in the maximum norm. Since ∥z∥2 ≥ ∥z∥∞ , their Euclidean separation is also at least 2h. Step 2: Define one tent at each center and verify its Hölder estimate. For each i ∈ J , define ψi : [0, 1]d → R by ψi (x) :=

1 (h − ∥x − xi ∥∞ )α+ . 2

The set on which ψi is nonzero lies in the open ball in the maximum norm of radius h centered at xi , and its closed support lies in the corresponding closed ball. The supports are therefore contained in the cube and are pairwise separated. For 0 < α ≤ 1 and u, v ∈ R, one has α |uα+ − v+ | ≤ |u − v|α .

(66)

To see this, first suppose that u ≥ v ≥ 0. The subadditivity of t 7→ tα gives uα = [v + (u − v)]α ≤ v α + (u − v)α . For completeness, this subadditivity is elementary. If a, b ≥ 0 and a + b > 0, put λ := a/(a + b). Since 0 < α ≤ 1 and 0 ≤ λ ≤ 1, one has λα ≥ λ and (1 − λ)α ≥ 1 − λ. Multiplication by (a + b)α yields aα + bα = (a + b)α (λα + (1 − λ)α ) ≥ (a + b)α . The case a = b = 0 is immediate. The case v ≥ u ≥ 0 is symmetric. If both numbers are nonpositive, both positive parts vanish. If exactly one is nonpositive, the positive part of the other is at most |u − v|, which proves the remaining cases. 58

The reverse triangle inequality for the maximum norm follows by applying the ordinary triangle inequality in both directions, and gives |∥x − xi ∥∞ − ∥y − xi ∥∞ | ≤ ∥x − y∥∞ ≤ ∥x − y∥2 . Combining this estimate with (66) yields 1 |ψi (x) − ψi (y)| ≤ ∥x − y∥α2 . 2 Step 3: Verify that every binary choice produces a target in the Hölder ball. For each binary vector indexed by the centers, v = (vi )i∈J ∈ {0, 1}J , define fv : [0, 1]d → R by

fv (x) :=

X i∈J

(2vi − 1)ψi (x).

The set of binary choices has cardinality d

{0, 1}J = 2|J | = 2R . At any point of the cube, at most one tent is nonzero. We verify the global Hölder estimate by considering the following mutually exclusive possibilities for x and y. (i) If no tent is nonzero at either point, then fv (x) = fv (y) = 0. (ii) If the same tent is nonzero at both points, or if exactly one of the two points has any nonzero tent value, then the signed sum at both points reduces to the same signed tent, with value zero at the inactive point in the latter case. The estimate from Step 2 therefore gives 1 |fv (x) − fv (y)| ≤ ∥x − y∥α2 . 2 (iii) If two different tents are nonzero at the two points, then 1 1 |fv (x) − fv (y)| ≤ hα + hα = hα . 2 2 Their Euclidean distance is at least 2h, and hence hα ≤ (2h)α ≤ ∥x − y∥α2 . This estimate from the triangle inequality also covers the case in which the two active tents carry opposite signs. Thus every fv is a function on [0, 1]d with Hölder constant at most one. Moreover, 1 ∥fv ∥L∞ ([0,1]d ) ≤ hα ≤ 1. 2 Therefore fv ∈ Hdα

for every v ∈ {0, 1}J .

59

Step 4: Show that accurate approximation realizes every binary labeling. At every center, all tents except one vanish and the remaining tent attains its maximum. Hence 1 fv (xi ) = hα (2vi − 1). 2 Write E := sup inf ∥f − g∥L∞ ([0,1]d ) . f ∈Hdα g∈F

Suppose, for contradiction, that E < hα /4. For every binary vector v, the definition of the infimum gives a function gv ∈ F satisfying 1 ∥fv − gv ∥L∞ ([0,1]d ) < hα . 4 No attainment assumption is used: the strict inequality inf g∈F ∥fv − g∥L∞ ([0,1]d ) < hα /4 is enough to select such a gv . If vi = 1, then 1 1 1 gv (xi ) > hα − hα = hα > 0. 2 4 4 If vi = 0, then 1 1 1 gv (xi ) < − hα + hα = − hα < 0. 2 4 4 Thus the approximation margin is strict on both sides of the fixed threshold 0, and 1{gv (xi )>0} = vi for every i ∈ J . As v ranges over {0, 1}J , every binary labeling of the Rd centers is realized by Thr0 (F). Hence those centers are shattered by the zero-threshold class. By (43), this would give Rd ≤ VCdim(F), contradicting Rd > V ≥ VCdim(F). We conclude that 1 E ≥ hα . 4 Step 5: Express the tent height in terms of V . By the definition of R, R ≤ V 1/d + 1 ≤ 2V 1/d , where the last inequality uses V ≥ 1. Since h = 1/(4R), 1 E ≥ hα = 4−(α+1) R−α 4 ≥ 4−(α+1) 2−α V −α/d . This is (65) with the stated value of e cα .

5.5

Completion of the minimax lower bound

Proof of Theorem 3.3. We now combine the two independent parts of the argument. The pseudodimension estimate controls the binary capacity of each fixed pair (Φ, A), while the bump lemma turns that capacity restriction into a quantitative approximation obstruction. The resulting constant is uniform over all admissible pairs, so the estimate survives the two outer infima in (12). The outer infimum in (12) is taken only over architectures whose input dimension is d. Under the convention of Section 3.1, such an architecture has at least one hidden unit and hence at 60

least (d + 1) + 2 = d + 3 parameter slots. Thus the admissible set is empty when P < d + 3. More generally, if {Φ ∈ Archpar (P ) : dΦ = d} = ∅, then the convention inf ∅ = +∞ makes the theorem immediate. We may therefore assume that this d-input admissible set is nonempty. Fix an arbitrary architecture Φ ∈ Archpar (P )

with

dΦ = d,

and an arbitrary map A ∈ Aff(M, PΦ ). The image A(RM ), and hence the realized family FΦ,A , is nonempty. Under the architectural convention fixed in Section 3.1, LΦ ∈ N+ and every hidden width is positive. Thus Φ has at least one hidden unit, and Lemma 5.7 applies. The family  FΦ,A = Φθ : θ ∈ A(RM ) consists of continuous functions on Rd . Set V0 := 8P min{M, P }. Because M, P ∈ N+ , we have V0 ≥ 1. Combining (44) and (63) gives VCdim(FΦ,A ) ≤ Pdim(FΦ,A ) ≤ V0 . Thus Lemma 5.9 applies with V = V0 ; the actual VC or pseudo-dimension need not be positive. By (5), minimizing over functions in FΦ,A is equivalent to minimizing over complete parameters θ ∈ A(RM ) or, equivalently, over latent vectors ξ ∈ RM . Thus the pairwise error in (11) satisfies Rα,d (Φ, A) = sup inf ∥f − g∥L∞ ([0,1]d ) . f ∈Hdα g∈FΦ,A

Lemma 5.9 therefore gives −α/d

Rα,d (Φ, A) ≥ e cα V0

=e cα 8−α/d [P min{M, P }]−α/d .

Thus the arbitrary pair (Φ, A) satisfies Rα,d (Φ, A) ≥ cα,d [P min{M, P }]−α/d , where one may take cα,d := 4−(α+1) 2−α 8−α/d . Since (Φ, A) was arbitrary, the preceding estimate holds for every Φ ∈ Archpar (P ) with dΦ = d and every A ∈ Aff(M, PΦ ). Hence, for each such Φ, inf

A∈Aff(M,PΦ )

Rα,d (Φ, A) ≥ cα,d [P min{M, P }]−α/d .

Taking the infimum over {Φ ∈ Archpar (P ) : dΦ = d} and using (12) proves (15).

6

Conclusion

The matching upper and lower bounds determine the sharp approximation rate of fully connected ReLU networks with affine latent parameterizations. Although the minimax problem ranges over all architectures with input dimension d in Archpar (P ), the upper bound is already attained by

61

networks whose width depends only on d. More precisely, under the assumptions of Theorem 3.1, one fixed pair (Φ, A) satisfies f − ΦA(ξf )

−1/d ≤ (d + 2)ω C [P min{M, P }] , f d d

L∞ ([0,1] )

for every f ∈ C([0, 1]d ), with a suitable target-dependent latent vector ξf . For the unit Hölder ball, combining this construction with the matching lower bound gives Eα,d (M, P ) ≍α,d [P min{M, P }]−α/d . In particular, for fixed M0 ≥ 4, the sharp rate is P −α/d once P ≥ max{M0 , Pd⋆ }. Thus a latent space of constant dimension can already yield a vanishing worst-case error, while the fully saturated regime M ≥ P yields the faster rate P −2α/d . This rate captures a tradeoff between latent information and decoding capacity. The M coordinates of ξf carry target-dependent information, while the fixed architecture uses its PΦ ≤ P parameter slots and budget-dependent depth to decode and route that information. The construction relies on exact real arithmetic for the latent coordinates, a discontinuous targetto-latent encoding, and a decoder whose size grows with the budget but remains independent of the target. Finite-precision coding, stability, and efficient optimization lie outside the scope of this expressivity result. Establishing sharp rates under finite-precision or bounded-weight restrictions, or under explicit stability and optimization requirements, is a natural direction for future work. A second direction is to extend the joint analysis to nonlinear generators under explicit complexity and regularity budgets.

References Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 7319–7328. Association for Computational Linguistics, 2021. DOI: 10.18653/v1/2021.acl-long.568. Paul Albert, Frederic Z. Zhang, Hemanth Saratchandran, Cristian Rodriguez-Opazo, Anton van den Hengel, and Ehsan Abbasnejad. RandLoRA: Full-rank parameter-efficient fine-tuning of large models. In International Conference on Learning Representations, 2025. URL: https://openreview.net/for um?id=Hn5eoTunHN. Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. DOI: 10.1017/CBO9780511624216. Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approximation analysis of convolutional neural networks. East Asian Journal on Applied Mathematics, 13(3):524–549, 2023. ISSN 2079–7370. DOI: 10.4208/eajam.2022-270.070123. Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC-dimension bounds for piecewise polynomial networks. Neural Computation, 10(8):2159–2173, 1998. DOI: 10.1162/089976698300017016. Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1–17, 2019. URL: http://jmlr.org/papers/v20/17-612.html. Erik Lien Bolager, Iryna Burak, Chinmay Datar, Qing Sun, and Felix Dietrich. Sampling weights of deep neural networks. In Advances in Neural Information Processing Systems, volume 36, 2023. URL: https://proceedings.neurips.cc/paper_files/paper/2023/hash/c7201deff8d507a8fe2e86d34 094e154-Abstract-Conference.html. Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 1(1):8–45, 2019. ISSN 2577-0187. DOI: 10.1137/18m118709x.

62

Olivier Bournez, Johanne Cohen, and Adrian Wurm. A universal uniform approximation theorem for neural networks. In 50th International Symposium on Mathematical Foundations of Computer Science, volume 345 of Leibniz International Proceedings in Informatics, pages 29:1–29:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. DOI: 10.4230/LIPIcs.MFCS.2025.29. Rebekka Burkholz. Batch normalization is sufficient for universal function approximation in CNNs. In International Conference on Learning Representations, 2024. URL: https://proceedings.iclr.cc/pa per_files/paper/2024/hash/17f21a0a111c9e3a4cd96708d30064f2-Abstract-Conference.html. Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2205–2211. International Joint Conferences on Artificial Intelligence Organization, 8 2021. DOI: 10.24963/ijcai.2021/304. Main Track. Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2285–2294. PMLR, 2015. URL: https://proceedings.mlr.press/v37/chenc15.html. Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen. Compressing convolutional neural networks in the frequency domain. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1475–1484. ACM, 2016. DOI: 10.1145/2939672.2939839. Jingpu Cheng, Qianxiao Li, Ting Lin, and Zuowei Shen. Interpolation, approximation, and controllability of deep neural networks. SIAM Journal on Control and Optimization, 63(1):625–649, 2025. DOI: 10.1137/23M1599744. Jingpu Cheng, Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning and the rate of approximation by flows. arXiv e-prints, art. arXiv:2603.15363, March 2026. DOI: 10.48550/arXiv.2603.15363. Charles K. Chui, Shao-Bo Lin, and Ding-Xuan Zhou. Construction of neural networks for realization of localized deep learning. Frontiers in Applied Mathematics and Statistics, 4:14, 2018. ISSN 2297-4687. DOI: 10.3389/fams.2018.00014. Albert Cohen, Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk. Optimal stable nonlinear approximation. Foundations of Computational Mathematics, 22:607–648, 2022. DOI: 10.1007/s10208021-09494-z. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems, 2:303–314, 1989. DOI: 10.1007/BF02551274. Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova. Nonlinear approximation and (deep) ReLU networks. Constructive Approximation, 55:127–172, 2022. DOI: 10.1007/s00365-021-09548-z. Misha Denil, Babak Shakibi, Laurent Dinh, Marc’Aurelio Ranzato, and Nando de Freitas. Predicting parameters in deep learning. In Advances in Neural Information Processing Systems, volume 26, pages 2148–2156. Curran Associates, Inc., 2013. URL: https://proceedings.neurips.cc/paper_files/p aper/2013/hash/7fec306d1e665bc9c748b5d2b99a6e97-Abstract.html. Ronald A. DeVore. Nonlinear approximation. 10.1017/S0962492900002816.

Acta Numerica, 7:51–150, 1998.

DOI:

Ronald A. DeVore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta Mathematica, 63:469–478, 1989. DOI: 10.1007/BF01171759. Sahil Rajesh Dhayalkar. Kilobyte models: Neural networks as a seed and a quantized latent. arXiv preprint arXiv:2608.00860, 2026. URL: https://arxiv.org/abs/2608.00860. Weinan E. A proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 5:1–11, 2017. DOI: 10.1007/s40304-017-0103-z. Weinan E and Stephan Wojtowytsch. Representation formulas and pointwise properties for Barron functions. Calculus of Variations and Partial Differential Equations, 61:article 46, 2022. ISSN 0944-2669. DOI: 10.1007/s00526-021-02156-6. Weinan E, Chao Ma, and Lei Wu. A priori estimates of the population risk for two-layer neural networks.

63

Communications in Mathematical Sciences, 17(5):1407–1425, 2019. DOI: 10.4310/CMS.2019.v17.n5.a11. Weinan E, Chao Ma, and Lei Wu. The Barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55:369–406, 2022. DOI: 10.1007/s00365-021-09549-y. Jonathan Frankle, David J. Schwab, and Ari S. Morcos. Training BatchNorm and only BatchNorm: On the expressive power of random features in CNNs. In International Conference on Learning Representations, 2021. URL: https://openreview.net/forum?id=vYeQQ29Tbvx. Tomer Galanti and Lior Wolf. On the modularity of hypernetworks. In Advances in Neural Information Processing Systems, volume 33, pages 10409–10419, 2020. URL: https://proceedings.neurips.cc /paper/2020/hash/75c58d36157505a600e0695ed0b3a22d-Abstract.html. Ziqi Gao, Qichao Wang, Aochuan Chen, Zijing Liu, Bingzhe Wu, Liang Chen, and Jia Li. Parameterefficient fine-tuning with discrete Fourier transform. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 14884–14901. PMLR, 2024. URL: https://proceedings.mlr.press/v235/gao24o.html. Angeliki Giannou, Shashank Rajput, and Dimitris Papailiopoulos. The expressive power of tuning only the normalization layers. In Proceedings of the Thirty-Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4130–4131. PMLR, 2023. URL: https://proceedings.mlr.press/v195/giannou23a.html. Paul W. Goldberg and Mark R. Jerrum. Bounding the Vapnik–Chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2–3):131–148, 1995. DOI: 10.1007/BF00993408. Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pablo Ortega. Approximation bounds for random neural networks and reservoir systems. The Annals of Applied Probability, 33(1):28–69, 2023. DOI: 10.1214/22AAP1806. Frithjof Gressmann, Zach Eaton-Rosen, and Carlo Luschi. Improving neural network training in low dimensional random bases. In Advances in Neural Information Processing Systems, volume 33, pages 12140–12150, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/8dcf2420e78a643 33a59674678fb283b-Abstract.html. Rémi Gribonval, Gitta Kutyniok, Morten Nielsen, and Felix Voigtlaender. Approximation spaces of deep neural networks. Constructive Approximation, 55:259–367, 2022. DOI: 10.1007/s00365-021-09543-4. Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep ReLU neural networks in W s,p norms. Analysis and Applications, 18(5):803–859, 2020. DOI: 10.1142/S0219530519410021. David Ha, Andrew M. Dai, and Quoc V. Le. HyperNetworks. In International Conference on Learning Representations, 2017. URL: https://openreview.net/forum?id=rkpACe1lx. Juncai He, Xiaodong Jia, Jinchao Xu, Lian Zhang, and Liang Zhao. Make ℓ1 regularization effective in training sparse CNN. Computational Optimization and Applications, 77(1):163–182, 2020. DOI: 10.1007/s10589-020-00202-1. Qingguo Hong, Jonathan W. Siegel, Qinyang Tan, and Jinchao Xu. On the activation function dependence of the spectral bias of neural networks. arXiv e-prints, art. arXiv:2208.04924, August 2022. DOI: 10.48550/arXiv.2208.04924. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251–257, 1991. ISSN 0893-6080. DOI: 10.1016/0893-6080(91)90009-T. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359–366, 1989. ISSN 0893-6080. DOI: 10.1016/0893-6080(89)900208. Daniel Hsu, Clayton H. Sanford, Rocco A. Servedio, and Emmanouil Vasileios Vlatakis-Gkaragkounis. On the approximation power of two-layer networks of random ReLUs. In Proceedings of the 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2423–2461. PMLR, 2021. URL: https://proceedings.mlr.press/v134/hsu21a.html. Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022. URL: https://openreview.net/forum?id=nZeVKeeFYf9.

64

Uijeong Jang, Jason D. Lee, and Ernest K. Ryu. LoRA training in the NTK regime has no spurious local minima. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 21306–21328. PMLR, 2024. URL: https: //proceedings.mlr.press/v235/jang24d.html. Yuling Jiao, Yanming Lai, Xiliang Lu, Fengru Wang, Jerry Zhijian Yang, and Yuanyuan Yang. Deep neural networks with ReLU-Sine-Exponential activations break curse of dimensionality in approximation on Hölder class. SIAM Journal on Mathematical Analysis, 55(4):3635–3649, 2023a. DOI: 10.1137/21M144431X. Yuling Jiao, Yang Wang, and Yunfei Yang. Approximation bounds for norm constrained neural networks with applications to regression and GANs. Applied and Computational Harmonic Analysis, 65:249–278, 2023b. ISSN 1063-5203. DOI: 10.1016/j.acha.2023.03.004. Boris Knyazev, Michal Drożdżal, Graham W. Taylor, and Adriana Romero-Soriano. Parameter prediction for unseen deep architectures. In Advances in Neural Information Processing Systems, volume 34, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/f6185f0ef02dcaec414a3171cd01c69 7-Abstract.html. Soroush Abbasi Koohpayegani, K. L. Navaneet, Parsa Nooralinejad, Soheil Kolouri, and Hamed Pirsiavash. NOLA: Compressing LoRA using linear combination of random basis. In International Conference on Learning Representations, 2024. URL: https://proceedings.iclr.cc/paper_files/paper/2024/h ash/66b99dbf9ed172abac5cb5ccfc82d1e2-Abstract-Conference.html. Dawid Jan Kopiczko, Tijmen Blankevoort, and Yuki M. Asano. VeRA: Vector-based random matrix adaptation. In International Conference on Learning Representations, 2024. URL: https://proceedi ngs.iclr.cc/paper_files/paper/2024/hash/1b53ad08de383a049e9668a9d0b6a053-Abstract-C onference.html. Agustinus Kristiadi, Felix Dangel, and Philipp Hennig. The geometry of neural nets’ parameter spaces under reparametrization. In Advances in Neural Information Processing Systems, volume 36, 2023. URL: https://proceedings.neurips.cc/paper_files/paper/2023/hash/395371f778ebd4854b8 8521100af30ad-Abstract-Conference.html. Quoc Le, Tamás Sarlós, and Alexander Smola. Fastfood: Computing Hilbert space expansions in loglinear time. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 244–252. PMLR, 2013. URL: https://proceeding s.mlr.press/v28/le13.html. Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018. URL: https://openreview.net/forum?id=ryup8-WCW. Qianxiao Li, Ting Lin, and Zuowei Shen. Deep neural network approximation of invariant functions through dynamical systems. arXiv e-prints, art. arXiv:2208.08707, August 2022. URL: https: //arxiv.org/abs/2208.08707. Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An approximation perspective. Journal of the European Mathematical Society, 25(5):1671–1709, 2023. DOI: 10.4171/JEMS/1221. Ting Lin, Zuowei Shen, and Qianxiao Li. On the universal approximation property of deep fully convolutional neural networks. arXiv e-prints, art. arXiv:2211.14047, November 2022. URL: https: //arxiv.org/abs/2211.14047. Yibo Lin, Zhao Song, and Lin F. Yang. Towards a theoretical understanding of hashing-based neural nets. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 127–137. PMLR, 2019. URL: https://proceedings.mlr.press/v89/lin19a.html. Etai Littwin, Tomer Galanti, Lior Wolf, and Greg Yang. On infinite-width hypernetworks. In Advances in Neural Information Processing Systems, volume 33, 2020. URL: https://proceedings.neurips. cc/paper/2020/hash/999df4ce78b966de17aee1dc87111044-Abstract.html. Xu-Hui Liu, Yali Du, Jun Wang, and Yang Yu. On the optimization landscape of low rank adaptation methods for large language models. In International Conference on Learning Representations, 2025. URL: https://proceedings.iclr.cc/paper_files/paper/2025/file/c34262c35aa5f8c1a09182

65

2cbb2020c2-Paper-Conference.pdf. Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 53(5):5465–5506, 2021. DOI: 10.1137/20M134695X. Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6231–6239. Curran Associates, Inc., 2017. URL: http://papers.nips.cc/paper/7203-the-e xpressive-power-of-neural-networks-a-view-from-the-width.pdf. Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6682–6691. PMLR, 2020. URL: https://proceedings.mlr.press/v119/malach20a.html. Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 23610–23641. PMLR, 2023. URL: https://proceedings.mlr.press/v202/malladi23a.html. Tong Mao and Jinchao Xu. Do neural networks really beat the curse of dimensionality? A bit-complexity view. arXiv e-prints, art. arXiv:2608.01357, August 2026. DOI: 10.48550/arXiv.2608.01357. Tong Mao, Jonathan W. Siegel, and Jinchao Xu. Approximation rates for shallow ReLUk neural networks on Sobolev spaces via the Radon transform. SIAM Journal on Mathematical Analysis, 58(2):1171–1186, 2026. DOI: 10.1137/24M1686693. Parsa Nooralinejad, Ali Abbasi, Soroush Abbasi Koohpayegani, Kossar Pourahmadi Meibodi, Rana Muhammad Shahroz Khan, Soheil Kolouri, and Hamed Pirsiavash. PRANC: Pseudo RAndom networks for compacting deep models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 17021–17031, 2023. URL: https://openaccess.thecvf.com/content/ICCV2023/htm l/Nooralinejad_PRANC_Pseudo_RAndom_Networks_for_Compacting_Deep_Models_ICCV_2023_pap er.html. Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via SUBSETSUM: Logarithmic over-parameterization is sufficient. In Advances in Neural Information Processing Systems, volume 33, pages 2599–2610, 2020. URL: https://proceedings.ne urips.cc/paper/2020/hash/1b742ae215adf18b75449c6e272fd92d-Abstract.html. Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 108:296–330, 2018. ISSN 0893-6080. DOI: 10.1016/j.neunet.2018.08.019. Ilan Price and Jared Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via a subspace offset. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8620–8629. PMLR, 2021. URL: https://proceedings.mlr.press/v139/price21a.html. Lord Sen and Shyamapada Mukherjee. Mapping networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 36215–36223, 2026. URL: https://openaccess .thecvf.com/content/CVPR2026/html/Sen_Mapping_Networks_CVPR_2026_paper.html. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Nonlinear approximation via compositions. Neural Networks, 119:74–84, 2019. ISSN 0893-6080. DOI: 10.1016/j.neunet.2019.07.011. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation characterized by number of neurons. Communications in Computational Physics, 28(5):1768–1811, 2020. ISSN 1991-7120. DOI: 10.4208/cicp.OA-2020-0149. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network with approximation error being reciprocal of width to power of square root of depth. Neural Computation, 33(4):1005–1036, 2021a. ISSN 0899-7667. DOI: 10.1162/neco a 01364. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Neural network approximation: Three hidden layers are enough. Neural Networks, 141:160–173, 2021b. ISSN 0893-6080. DOI: 10.1016/j.neunet.2021.04.011.

66

Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation: Achieving arbitrary accuracy with fixed number of neurons. Journal of Machine Learning Research, 23(276):1–60, 2022a. URL: http://jmlr.org/papers/v23/21-1404.html. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation in terms of intrinsic parameters. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19909–19934. PMLR, 17–23 Jul 2022b. URL: https://proceedings.mlr.press/v162/shen22g.html. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Neural network architecture beyond width and depth. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 5669–5681. Curran Associates, Inc., 2022c. URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/257be12f31dfa7cc158dda998 22c6fd1-Abstract-Conference.html. Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101–135, 2022d. ISSN 0021-7824. DOI: 10.1016/j.matpur.2021.07.009. Jonathan W. Siegel and Jinchao Xu. Approximation rates for neural networks with general activation functions. Neural Networks, 128:313–321, 2020. ISSN 0893-6080. DOI: 10.1016/j.neunet.2020.05.019. Jonathan W. Siegel and Jinchao Xu. High-order approximation rates for shallow neural networks with cosine and ReLUk activation functions. Applied and Computational Harmonic Analysis, 58:1–26, 2022. ISSN 1063-5203. DOI: 10.1016/j.acha.2021.12.005. Jonathan W. Siegel and Jinchao Xu. Sharp bounds on the approximation rates, metric entropy, and n-widths of shallow neural networks. Foundations of Computational Mathematics, 24(2):481–537, 2024. DOI: 10.1007/s10208-022-09595-3. Chayne Thrash, Reed Andreas, Ali Abbasi, Parsa Nooralinejad, Soroush Abbasi Koohpayegani, Hamed Pirsiavash, and Soheil Kolouri. MCNC: Manifold-constrained reparameterization for neural compression. In International Conference on Learning Representations, 2025. URL: https://proceedings.iclr .cc/paper_files/paper/2025/hash/2f63d2963526bdd9ff1b8bcc2dc9905a-Abstract-Conferenc e.html. Qianchao Wang, Shijun Zhang, Dong Zeng, Zhaoheng Xie, Hengtao Guo, Tieyong Zeng, and Feng-Lei Fan. Don’t fear peculiar activation functions: EUAF and beyond. Neural Networks, 186:107258, 2025. ISSN 0893-6080. DOI: 10.1016/j.neunet.2025.107258. Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167–178, 1968. DOI: 10.1090/S0002-9947-1968-0226281-1. Paul Wimmer, Jens Mehnert, and Alexandru Paul Condurache. FreezeNet: Full performance by reduced storage costs. In Computer Vision – ACCV 2020, volume 12627 of Lecture Notes in Computer Science, pages 685–701. Springer, 2020. DOI: 10.1007/978-3-030-69544-6 41. Mitchell Wortsman, Maxwell C. Horton, Carlos Guestrin, Ali Farhadi, and Mohammad Rastegari. Learning neural network subspaces. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11217–11227. PMLR, 2021. URL: https://proceedings.mlr.press/v139/wortsman21a.html. Zichao Yang, Marcin Moczulski, Misha Denil, Nando de Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried ConvNets. In Proceedings of the IEEE International Conference on Computer Vision, pages 1476–1483, 2015. DOI: 10.1109/ICCV.2015.173. Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103–114, 2017. ISSN 0893-6080. DOI: 10.1016/j.neunet.2017.07.002. Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 639–649. PMLR, 06–09 Jul 2018. URL: http://proceedings.mlr.press/v75/yarotsky18a.html. Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in

67

Neural Information Processing Systems, volume 33, pages 13005–13015. Curran Associates, Inc., 2020. URL: https://proceedings.neurips.cc/paper/2020/file/979a3f14bae523dc5101c52120c535e 9-Paper.pdf. Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. In International Conference on Learning Representations, 2024. URL: https://proceedings.iclr.cc/paper_files/ paper/2024/hash/154926e0b66e2b2a8c1120852f31a12d-Abstract-Conference.html. Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. On enhancing expressive power via compositions of single fixed-size ReLU network. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 41452–41487. PMLR, 23–29 Jul 2023. URL: https://proceedings.mlr.press/v202/zhang23ad.html. Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. Deep network approximation: Beyond ReLU to diverse activation functions. Journal of Machine Learning Research, 25(35):1–39, 2024. URL: http://jmlr.o rg/papers/v25/23-0912.html. Shijun Zhang, Hongkai Zhao, Yimin Zhong, and Haomin Zhou. Structured and balanced multicomponent and multilayer neural networks. SIAM Journal on Scientific Computing, 47(5):C1059–C1090, 2025. DOI: 10.1137/24M1675990. Shijun Zhang, Zuowei Shen, and Yuesheng Xu. Geometric layer-wise approximation rates for deep networks. arXiv e-prints, art. arXiv:2604.20219, April 2026a. DOI: 10.48550/arXiv.2604.20219. Shijun Zhang, Zuowei Shen, and Yuesheng Xu. Multigrade neural network approximation. arXiv e-prints, art. arXiv:2601.16884, January 2026b. DOI: 10.48550/arXiv.2601.16884. Shijun Zhang, Hongkai Zhao, Yimin Zhong, and Haomin Zhou. Fourier multi-component and multi-layer neural networks: Unlocking high-frequency potential. Neural Networks, 204:109268, 2026. ISSN 0893-6080. DOI: 10.1016/j.neunet.2026.109268. Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. GaLore: Memory-efficient LLM training by gradient low-rank projection. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 61121–61143. PMLR, 2024. URL: https://proceedings.mlr.press/v235/zhao24s.html. Ding-Xuan Zhou. Universality of deep convolutional neural networks. Applied and Computational Harmonic Analysis, 48(2):787–794, 2020. ISSN 1063-5203. DOI: 10.1016/j.acha.2019.06.004.

68

Related documents

• Low Rank Based Subspace Inference for the Laplace Approximation of Bayesian Neural Networks#131285
• Sharp approximation rates for shallow ReLU neuralnetworks on critical Besov classes#973997
• Limit theorems for stochastic gradient descent in high-dimensional single-layer networks#675881
• Efficient Approximation of Regularized Relative Entropies and Applications#243792
• How the Hessian-Spectrum of Neural Networks Depends on Data#370354