Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Resource model

• The framework counts both M target-dependent coordinates and P generated weight-and-bias slots, because counting either resource alone can misrepresent expressive complexity.Only the latent vector is selected separately for each target; the architecture and generator are shared across the target class.Source: §1 · pp. 1, 2, 4

Limitations

• Unrestricted generators make latent dimension meaningless: even M = 1 can continuously surject onto the full parameter space, while finite task sets can be interpolated smoothly.Meaningful nonlinear-generator theory would additionally need controls on generator complexity, regularity, stability, computational size, or latent precision.Source: §1 · p. 2

Main result

• The main theorem establishes optimal error order (P min{M, P})^-α/d for the unit ball of α-Hölder functions, under its stated conditions on P and M.The architecture and affine generator are fixed before the target is selected, while only the latent vector depends on the target.Source: §1 · p. 3
• The rate is (PM)^-α/d when M ≤ P and saturates at P^-2α/d when M ≥ P.The upper bound uses fixed-width fully connected ReLU networks with depth growing at most linearly in P, while the matching lower bound covers all admissible architectures.Source: §1 · p. 3, Figure 2 · p. 3

Fixed latent dimension

• A fixed latent dimension M = M0 ≥ 4 still yields algebraically vanishing error as P grows, driven entirely by the shared decoder budget.This fixed-dimensional rate is slower than the saturated regime available when M ≥ P, but remains optimal for the stated resource model.Source: §1 · p. 3

Proof strategy

• The upper construction uses affine spline loading, binary prefix extraction, spatial addressing, and boundary repair, while the lower bound combines affine-rank reduction, pseudo-dimension control, and Hölder bump packing.The stated rate relies on exact real arithmetic and concerns representation power rather than numerical stability or optimization; the constructive upper estimate also extends to every finite Lp norm.Source: §1 · p. 4

• The section reviews closely related empirical and theoretical work before interpreting the joint dependence on P and M.Source: §2 · p. 4

Related parameterizations and theory

• Sections 2.1–2.2 distinguish affine parameterizations from nonlinear relatives, while Section 2.3 places the result within approximation and capacity theory.Source: §2 · p. 4

Scope and assumptions

• Sections 2.4–2.6 discuss resource accounting, optimization geometry, and exact real arithmetic, and the background is not used as a proof assumption.Source: §2 · p. 4

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

• The framework distinguishes task-specific parameterization methods from a single affine map fixed across an entire target class.This distinction determines whether existing approaches fall within the minimax model.Source: §2.1 · p. 4

Parameter prediction and weight tying

• More than 95% of weights were predicted without accuracy loss in Denil et al. (2013), but the predictors and selected coordinates were task-dependent and lacked uniform approximation guarantees.HashedNets, frequency-sensitive hashing, DCT layers, and FourierFT likewise use structured sharing or affine maps for empirical compression rather than joint minimax rates.Source: Parameter prediction and weight tying · p. 5

Fixed and learned subspaces

• Fixed random-subspace experiments achieved full-model performance using hundreds or thousands of coordinates, while changing bases or module projections could improve optimization.Because some methods regenerate or learn task-specific subspaces, they do not establish a two-budget minimax law over a function class.Source: Fixed and learned subspaces · p. 5
• Coordinate-restricted training, sparse regularization, and normalization-only adaptation reduce trainable parameters, but their structures are task-selected or rely on special architectures rather than one prescribed affine map.These theories address parameter reduction or target-network reconstruction, not uniform approximation of a Hölder ball.Source: Fixed and learned subspaces · p. 6
• Learned lines, curves, and simplices can contain highly accurate task-specific solutions, yet their defining endpoints are trainable and therefore do not characterize worst-case error jointly in (M, P).Across these approaches, the common focus is task performance, optimization, or reconstruction rather than a class-wide minimax rate.Source: Fixed and learned subspaces · p. 6

Scope and limitation

• Nonlinear generators require a separate complexity or regularity budget for G, because latent dimension M alone does not control the generated family.This limitation applies to hypernetworks, Mapping Networks, and most low-rank adaptation methods.Source: §2.2 · p. 6

Hypernetworks

• Hypernetworks generate primary-network weights from compact codes, but existing work studies conditional families, modular complexity, or kernel dynamics rather than the affine minimax rate.Relevant examples include recurrent and image models, modular weight generation (Galanti and Wolf, 2020), and hyperkernel limits (Littwin et al., 2020).Source: §2.2 · p. 6

Mapping Networks

• Mapping Networks use nonlinear latent modulation of frozen base matrices; in Cityscapes, roughly 8,000 latent coordinates drive 1,734,803 parameters, raising pixel accuracy from 93.21% to 97.92%.Mean intersection-over-union changes from 0.4957 to 0.4623, or 0.4823 for the layerwise variant.Source: §2.2 · p. 6

Low-rank adaptation

• LoRA and related methods are generally nonlinear in their combined low-rank factors, while fixed-factor or direct-basis variants can instead define affine parameter maps.Their analyses depend on pretrained weights, factorization, or local optimization assumptions and do not yield the global function-class rate proved below (Hu et al., 2022; Albert et al., 2025; Kopiczko et al., 2024).Source: §2.2 · p. 7

Related methods

• Gradient low-rank projection compresses gradients and optimizer state while retaining full-rank weights, so it is an optimization-memory method rather than a low-dimensional parameter map.This distinction separates it from parameter generators of the form G: R^M → R^PΦ (Zhao et al., 2024).Source: §2.2 · p. 7

Core framework

• The theorem combines exact coding, target-dependent network parameters, and polynomial sign-pattern capacity while explicitly budgeting both code dimension and decoder size.These viewpoints organize the comparison and underpin the paper’s joint resource analysis.Source: §2.3 · p. 7

Related approximation results

• Shen et al. (2022b) construct a ReLU decoder with n + 2 target-dependent parameters and error at most 5λd^(2−n), but its decoder size is not independently budgeted.The present problem asks how this exponential code-length dependence changes when the decoder is also constrained by P.Source: §2.3 · p. 7

Parameter sharing

• Repeated composition of a fixed ReLU block yields O(r^−1/d) error for Lipschitz targets, consistent with the fixed-M regime, but does not characterize arbitrary (M, P) or prove a matching lower bound.After unrolling, block reuse becomes an affine tying map from fixed coefficients to network slots proportional to the repetition count.Source: §2.3 · pp. 7–8

Resource-model comparison

• The paper interpolates between fixed-code constructions with growing decoders and fully target-dependent networks constrained only by total size, while affine tying and joint code-slot budgets impose the studied regime.Bounded-width universality and depth-based refinement clarify depth’s role but do not quantify the affine latent constraint.Source: §2.3 · p. 8

Capacity and lower bounds

• For the lower bound, polynomial sign-pattern arguments are adapted to affine parameter tying, so effective capacity depends on rank(A), not the ambient number P_Φ of parameter slots.The upper construction operates in the exact-real regime, alongside nonlinear-width and discontinuous-encoding perspectives.Source: §2.3 · p. 8

Nondegenerate regime

• For 4 ≤ M ≤ P and sufficiently large P, the sharp Hölder approximation rate is (PM)^−α/d because the decoder reconstructs proportional to PM grid values.Latent coordinates store quantized increment streams, while a depth-proportional-to-P decoder reads proportional-to-P digits from each stream.Source: §2.4 · p. 9

Endpoint regimes

• When M is comparable to P, the rate becomes P^−2α/d, matching optimal very-deep fixed-width network rates established in (Yarotsky, 2018, Theorems 1(a) and 2(b)) and (Shen et al., 2022d, Theorem 1.1).Source: §2.4 · p. 9
• With fixed M ≥ 4 and sufficiently large P, the rate is P^−α/d; for M ≥ P, affine rank saturation explains the factor min{M, P}.This quantifies decoding a fixed-dimensional real latent vector with an increasingly deep shared decoder, in the spirit of (Shen et al., 2022b).Source: §2.4 · p. 9

Resource accounting

• The shared affine generator contains P_ΦM + P_Φ fixed scalar entries that are excluded from the target-dependent count M, so the theorem does not automatically establish total-storage compression.Alternative accounting could charge these coefficients or impose sparsity, fast transforms, or seeded regeneration; Dhayalkar (2026) studies a finite-precision seeded deployment model without a matching function-class approximation law.Source: §2.4 · p. 9

Optimization geometry

• The affine map makes the latent optimization geometry explicit through the loss pullback and its Hessian.For a twice continuously differentiable full-parameter loss, the chain rule relates latent derivatives to full-parameter derivatives.Source: §2.5 · p. 9

Effective coordinates

• When rank(A) < M, the pullback Hessian is singular, so ordinary conditioning is meaningful only after removing redundant latent directions.If rank(A) = 0, the affine family contains a single parameter vector and has no latent condition number; otherwise, effective coordinates are formed from an orthonormal basis of ker(A)⊥.Source: §2.5 · p. 9

Condition number

• In effective coordinates, local conditioning is defined from the Hessian restricted to the nonredundant affine directions and requires positive definiteness.The relevant matrix is inherited from the nonredundant directions of the original latent vector under a local quadratic model with Hessian H.Source: §2.5 · pp. 9–10

Limitations

• Conditioning depends on the specified coordinate system: nonorthogonal changes can alter it, while dimensional reduction alone neither guarantees nor precludes improvement.Rank-deficient maps additionally restrict optimization to a proper affine subspace, so jointly optimizing approximation quality and conditioning for a prescribed loss remains a separate problem; related discussions include Gressmann et al. (2020), Kristiadi et al. (2023), and Liu et al. (2025).Source: §2.5 · p. 10

Arithmetic and information limits

• Exact-real encoding uses increasingly long binary streams, exponentially growing decoder-weight dynamic range, and a discontinuous target-to-latent selection map.With b-bit latent coordinates, only 2^(Mb) codes are available, creating an additional obstruction of order (Mb)^(-α/d).Source: §2.6 · p. 10
• The theorem concerns expressivity over real parameters, not bit complexity, perturbation or noise stability, gradient descent, or uniformly bounded weights.Parameter count and finite-precision information complexity are distinct resources, while this work counts weight and bias slots without bounding magnitudes.Source: §2.6 · p. 10

Architectural scope

• The analysis restricts architectures to fully connected ReLU networks, whereas convolutional, activation-dependent, nested, and fixed-size universal constructions can obey different approximation laws.The cited alternatives do not establish the joint affine minimax law studied here.Source: §2.6 · p. 10

Theorem scope

• The upper construction uses width depending only on d and depth growing with P for sequential decoding, while the lower bound covers every fully connected architecture with at most P dense slots.No upper-bound theorem is claimed at fixed depth, for convolutional architectures, or for nonlinear generators.Source: §2.6 · p. 10
• Matching optimality holds for the normalized Hölder class in uniform norm, with a constructively chosen affine map rather than a guarantee for random affine subspaces.The upper construction itself applies to every continuous function on the cube.Source: §2.6 · p. 11

Network architectures

• A fully connected ReLU architecture is specified by its hidden-layer widths and depth, with every dense weight and bias entry counted toward the parameter budget P.The architecture class imposes no separate width or depth restriction beyond the total number of scalar parameter slots.Source: Network architectures · p. 12, Figure 3 · p. 13

Affine latent parameterizations

• An affine latent parameterization has the form A(ξ)=Aξ+a, with A and a fixed across the target class and only ξ allowed to depend on the target.Its effective dimension is governed by the affine map’s rank, while the latent space has positive integer dimension M.Source: Affine latent parameterizations · p. 13

Target class and minimax error

• The minimax problem chooses the architecture and affine generator before seeing the target, while selecting the latent vector after the target is given.The parameter budget restricts architectures with input dimension d and scalar output, and the approximation error is measured uniformly over the target class.Source: Target class and minimax error · p. 14

3.2 Main results

• The upper-bound construction works for every continuous target, using a single architecture and affine map depending only on (d, M, P), with target-specific latent vectors producing the approximants.The construction is organized under explicit parameter and depth budgets, and affine dependence holds for every layer weight and bias.Source: §3.2 · p. 14
• For 0 < α ≤ 1, Corollary 3.2 provides an upper bound for Hölder functions in uniform error, and the same approximants satisfy this bound in every Lp([0, 1]d), 1 ≤ p < ∞.Source: §3.2 · pp. 14–15
• A matching lower bound holds uniformly over all admissible architectures and affine parameterizations, with a constant independent of M, P, depth, architecture, and affine map.The proof combines pseudo-dimension control for affine-generated ReLU families with packings of localized Hölder functions.Source: §3.2 · p. 15
• The upper and lower bounds match up to constants depending only on (α,d), so fixed latent dimension M0≥4 still yields error decaying as P^-α/d.When M≥P, the rate instead saturates at P^-2α/d, distinguishing fixed-latent and fully variable-parameter regimes.Source: §3.2 · pp. 14–15

4 Constructive proof of the upper bound

• The construction assembles serialized hinges, affine loading, fixed decoding, fitting, spatial addressing, and budget conversion into one fully connected architecture.Every sparse module is embedded by zero-padding, with unused entries counted in the dense parameter budget.Source: §4 · p. 16

4.1 Serialized hinge sums and safe composition

• Fixed-width serialized hinges represent continuous piecewise-linear functions, transport signed states, and preserve affine code dependence under parallelization and fixed-side composition.Merging two code-dependent affine layers is excluded because it can create products such as ξ^2.Source: §4.1 · pp. 16–19

4.2 Affine spline loading with serialized hinges

• The affine spline loader uses width at most 5 and hidden depth at most 2S + 2, with each target-dependent slot depending on at most three consecutive data coordinates.The interpolant is expressed in a hinge basis whose coefficients are linear combinations of local spline data.Source: §4.2 · pp. 20–21

4.3 Fixed binary prefix decoder

• The fixed binary prefix decoder uses architecture ΨD ∈ Arch(20, 4D + 2) whose parameters are independent of the encoded bit vector.A fixed-width gate repeatedly extracts bits from the binary remainder, updates that remainder, and accumulates the requested prefix over legal finite inputs.Source: §4.3 · p. 21
• The decoder maintains a complete remainder invariant, ensuring every legal-input remainder r_i lies in [0,1), and its accumulator outputs the desired prefix sum after D stages.The construction is valid only on the designated inputs, where the ReLU recurrences extract bits and add e_i precisely when i≤k.Source: §4.3 · pp. 22–23
• The decoder is realized by repeated four-layer blocks with fixed parameters, hidden depth proportional to D, and maximum displayed width 7, padded to a fully connected width of at most 20.All constants depend on D through δ_D but not on the encoded bit string, so the decoder parameter vector is fixed.Source: §4.3 · p. 23

4.4 Point fitting with an affine code

• The affine code stores each block baseline, positive and negative binary increment streams, and the scale η separately, so target-dependent parameter slots never multiply two latent coordinates.The scale enters only through output weights ±η, while loader coefficients are fixed affine combinations of at most three latent coordinates.Source: §4.4 · pp. 25–27
• For every original index j < J, the point-fitting construction exactly reproduces y_j, uses an affine code, and has maximum used width 44 ≤96.It stores block baselines and binary increment streams, uses three affine spline loaders and two fixed prefix decoders, and avoids products of target-dependent quantities.Source: §4.4 · pp. 24, 26, 28

4.5 Spatial addressing, bridge sequences, and boundary repair

• The spatial-addressing construction uses two continuous staircases to recover coarse and fine indices, realizing a fixed address network with depth at most 8q + 4.The staircases interpolate across gaps of width δ, retain signed intermediate states, and use fixed affine readouts depending only on (q, δ).Source: §4.5 · pp. 28, 30
• The slow bridge sequence stores grid samples at table addresses and inserts K linear bridge values between rows, keeping consecutive increments at the modulus-controlled scale.The construction uses 2K^d samples and reserves K addresses after each row for bridges, with the endpoint transition to the next row equal to zero.Source: §4.5 · pp. 30–31
• Boundary repair applies coordinatewise median operations to shifted branches, yielding a uniform error estimate on the whole cube while preserving affine latent dependence and explicit architecture bounds.At least two of the three shifts are reliable; the median remains between their values, adding one modulus term per repaired coordinate, while the final depth is at most L + 2d and width is below 3^d(N + 4).Source: §4.5 · pp. 32, 34
• The exact-real construction does not bound latent bit lengths, decoder dynamic range, or numerical stability, while b-bit latent scalars impose an additional information limit of Mb.These finite-precision effects are deliberately separated from the main theorem over exact real parameters.Source: §4.5 · p. 34

4.6 Construction under integer budgets

• The integer-budget assembly introduces S latent code blocks, D decoder stages, and a mesh parameter q, together with K = q^2 and b_Ld,D = 18D + 30 + 2d.These abbreviations coordinate the integer resources used in the remaining construction.Source: §4.6 · p. 35
• A universal architecture and affine map encode every continuous target using 3S + 1 latent coordinates, with fixed addressing and affine parameter dependence across targets.The construction loads sampled values through a fixed address network and point-fitting decoder, while transition-strip repair preserves the universal architecture.Source: §4.6 · pp. 35–37
• The sampled-value decoder approximates all grid and bridge samples within the target modulus, while spatial interpolation and boundary repair add only controlled modulus contributions.The point-fitting code uses exactly 3S + 1 coordinates, and monotonicity gives ω_f(δ) ≤ η during transition-strip repair.Source: §4.6 · pp. 35–37
• The address module runs d coordinate copies in parallel, and the composed network remains fully connected within the prescribed width and depth bounds, including fixed-zero slots.Before repair, width is at most max{20d, 96} and depth at most 18D + 28; after repair, the architecture belongs to Arch(Nd, bL_d,D).Source: §4.6 · pp. 36–37

4.7 Matching the prescribed budgets

• The construction achieves SD ≥ P min{M, P} with 3S + 1 ≤ min{M, P}, converting code-block capacity and decoder length into the prescribed budget-dependent mesh scale.D = floor(P/B_d), while S is chosen within the latent-coordinate budget; their product controls spatial resolution.Source: §4.6 · p. 35, §4.7 · p. 38
• The prescribed-domain affine generator is obtained by projecting the first 3S + 1 coordinates from R^M, and the resulting construction proves the theorem’s final budget-dependent bound.The projection appends zeros when M exceeds the core latent dimension, preserving affine dependence and the same architecture.Source: §4.7 · pp. 38–39

5 Proof of the H¨older lower bound

• The proof combines a capacity estimate with a packing construction for every admissible architecture-generator pair with P_Φ ≤ P.This establishes the two main ingredients of the lower-bound argument before the section develops them in sequence.Source: §5 · p. 39
• Redundant affine latent coordinate directions are removed before analyzing the effective parameterization.The section then applies the resulting coordinates to the network family.Source: §5 · pp. 39–40

5.1 VC dimension, pseudo-dimension, and polynomial predicates

• Counting binary polynomial patterns supplies the capacity estimate used in the network-specific argument.The combinatorial analysis is organized around VC dimension, pseudo-dimension, Boolean formulas, and polynomial sign-pattern bounds.Source: §5 · p. 40, §5.1 · p. 40

5 Proof of the H¨older lower bound

• Binary positive and negative Hölder bumps convert the capacity upper bound into a uniform approximation lower bound using V_0 := 8P min{M, P} ≥ 1.The packing step completes the transition from capacity control to approximation error.Source: §5 · p. 40
• The proof is completed through sequential subsections covering combinatorial tools, latent-direction reduction, network analysis, packing, and the minimax argument.Throughout, r, s, d_pol, and m track effective variables, Boolean-atom occurrences, polynomial degree, and lifted input-threshold pairs.Source: §5 · p. 40

VC dimension and pseudo-dimension

• Pseudo-dimension is obtained by lifting each real-valued function to a binary subgraph class on (x, t) and applying ordinary VC dimension.A lifted point (x, t) is labeled one precisely when the function value exceeds t.Source: VC dimension and pseudo-dimension · pp. 40–41

Boolean formulas and polynomial predicates

• The Boolean-polynomial framework represents subgraph membership using fixed Boolean formulas over strict-positivity polynomial atoms, with parameter degree bounded after fixing (x, t).Leaf occurrences count syntactic uses, and the active-branch/inactive-branch construction yields a (4, 2) description for the network example.Source: Boolean formulas and polynomial… · pp. 43–44

Polynomial sign-pattern bounds

• Lemma 5.4 handles zeros, repeated polynomials, and zero polynomials by shifting all predicates downward by one common perturbation before applying Warren’s indexed sign-pattern bound.The shift preserves every realized binary pattern while making all shifted polynomial values nonzero at selected witnesses.Source: Polynomial sign-pattern bounds · pp. 45–46

From polynomial predicates to pseudo-dimension

• Proposition 5.5 converts an (s, dpol) Boolean-polynomial description of a parameterized class into a pseudo-dimension bound via normalized binary atoms and Lemma 5.4.The proof adapts the counting strategy of Goldberg and Jerrum, 1995, Theorem 2.2, while obtaining a 4e constant instead of 8e.Source: From polynomial predicates to… · p. 46
• The polynomial-predicate argument shows that every labeling pattern is controlled by finitely many parameter polynomials, yielding m ≤ 2r log2(4edpols).The proof factors labels through simultaneous polynomial positivity bits, applies a binary polynomial-pattern estimate, and solves the resulting scalar inequality.Source: From polynomial predicates to… · pp. 48–50

5.2 Effective latent coordinates

• Only the effective affine rank rA matters: the latent family is reparameterized over Range(A), while rA = 0 yields a singleton realized-function family.A rank factorization gives a surjective effective-coordinate map and preserves the affine image and realized functions.Source: §5.2 · pp. 50–51

5.3 Pseudo-dimension under affine parameter tying

• For affine parameter tying, fixed ReLU activation patterns become polynomial forward passes in rA effective variables, and Boolean logic combines them into the subgraph predicate.The architecture and affine map are fixed; after lifting an input-threshold pair, only the effective parameter vector varies, with affine parameter entries of degree at most one.Source: §5.3 · pp. 51–52
• The fixed activation-pattern formula exactly represents network threshold predicates, including zero-preactivation boundaries, through a unique consistent branch.The resulting semialgebraic description is fixed by the architecture and affine map rather than chosen after observing inputs or latent parameters.Source: §5.3 · p. 55
• The pseudo-dimension bound scales with the effective affine parameter dimension and network computation size, while activation-pattern enumeration contributes only logarithmically.The factor rA measures independent parameter directions, whereas UΦ+1 captures piecewise-polynomial computation; 2^UΦ patterns yield log2(2^UΦ)=UΦ.Source: §5.3 · pp. 56–57

5.4 From pseudo-dimension to a uniform lower bound

• A Hölder bump-packing lemma converts finite threshold capacity into a uniform lower bound by placing disjoint tents whose signs encode independently chosen binary labelings.If every signed tent sum were approximated sufficiently accurately at its centers, the zero-threshold class would realize more labelings than its VC dimension permits.Source: §5.4 · pp. 57–58
• The construction uses separated grid centers and tent supports contained in the cube, ensuring every binary signed sum remains in the unit Hölder ball.At most one tent is nonzero at any point, allowing the global Hölder estimate to follow from the individual tent bound.Source: §5.4 · pp. 58–59
• Accurate approximation of the tent family would realize every binary labeling of the centers, contradicting the assumed VC-dimension bound.The contradiction uses a strict error threshold, so no infimum-attainment assumption is needed.Source: §5.4 · p. 60
• The tent construction yields a quantitative lower-bound constant after expressing its height in terms of the capacity parameter V.The resulting estimate is identified as equation (65) with the stated constant ecα.Source: §5.4 · p. 60

5.5 Completion of the minimax lower bound

• For every admissible architecture-generator pair, setting V0 = 8P min{M, P} enables the lower-bound lemma, and taking both outer infima proves the minimax lower bound.The bound is uniform over pairs; if P < d + 3, the admissible class is empty and the convention inf ∅ = +∞ applies.Source: §5.5 · p. 61

• Matching upper and lower bounds determine the sharp approximation rate for fully connected ReLU networks with affine latent parameterizations.The upper bound is attained by architectures whose width depends only on the input dimension d.Source: §6 · pp. 61–62
• For fixed M0 ≥ 4 and sufficiently large P, the sharp rate is P^-α/d.A single fixed architecture-generator pair works for every continuous target function with a suitable target-dependent latent vector.Source: §6 · p. 62
• When M ≥ P, the fully saturated regime achieves the faster rate P^-2α/d.Thus constant-dimensional latent spaces suffice for vanishing worst-case error, although saturation improves the rate.Source: §6 · p. 62
• The tradeoff reflects target information stored in M latent coordinates and decoding performed by a fixed architecture with PΦ ≤ P slots and budget-dependent depth.The construction uses exact real arithmetic, discontinuous target-to-latent encoding, and a target-independent decoder; finite precision, stability, optimization, and nonlinear-generator extensions remain future directions.Source: §6 · p. 62