Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Shijun Zhang

Source-linked AI summary

Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Shijun Zhang

arXiv:2608.31157v1Aug 31, 2026cs.LGstat.ML

TL;DR

The paper asks how approximation error depends jointly on latent dimension and generated-network budget when one affine parameterization is shared across a Hölder function class. It proves sharp rates for fully connected ReLU networks, including vanishing error with fixed-dimensional latent spaces.

Problem
The central question is how optimal worst-case approximation error depends jointly on latent dimension M and parameter budget P for a shared affine latent parameterization.
Method
The paper formulates a minimax problem over fully connected ReLU architectures and affine generators shared across the target class, accounting for both latent coordinates and generated parameter slots.
Results
The sharp rate is (P min{M,P})^-α/d, with regimes (PM)^-α/d for M ≤ P and P^-2α/d for M ≥ P.
Takeaways & Limitations
For fixed M0 ≥ 4, the rate is P^-α/d once P is sufficiently large, so constant-dimensional latent spaces can yield vanishing worst-case error.
Takeaways & Limitations
The theorem uses a ReLU-specific argument; a formal proof for non-ReLU activations is omitted because no theorem in the paper uses them.

Abstract

from arXiv · show

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 $\boldsymbolθ_f=\mathcal{G}(\boldsymbolξ_f)$, where $\mathcal{G}\colon\mathbb{R}^M\to\mathbb{R}^{P_Φ}$ is a parameter generator and $\boldsymbolξ_f\in\mathbb{R}^M$ is a latent representation of the target function $f$. The architecture $Φ$ and the generator $\mathcal{G}$ are shared across the entire target class, while each target $f$ is represented by its own latent vector $\boldsymbolξ_f$, with $Φ_{\mathcal{G}(\boldsymbolξ_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_Φ\leq P$ and affine generators $\mathcal{G}:\mathbb{R}^M\to \mathbb{R}^{P_Φ}$, we prove that the optimal worst-case uniform approximation error over the unit ball of $α$-Hölder functions on $[0,1]^d$, where $0<α\leq1$, has the sharp order $ \bigl(P\min\{M,P\}\bigr)^{-α/d}. $ In particular, our result shows that even a fixed-dimensional latent space suffices to achieve vanishing approximation error as the network budget increases.

1 Introduction

The paper asks how latent dimension M and generated-network budget P jointly determine uniform approximation error when one affine parameterization is shared across a Hölder function class. It proves a sharp two-resource law and shows fixed-dimensional latent spaces can still achieve vanishing error.

Problem formulation: The shared architecture and affine generator are fixed before target selection, while only each target’s latent vector varies.This separates target-dependent information from shared decoding complexity.
Scope and assumptions: An affine restriction is essential because an unrestricted generator with M = 1 can map onto the full parameter space and impose essentially no expressive constraint.Continuity or smoothness alone does not make latent dimension a meaningful complexity measure in the stated settings.
Problem formulation: The central question is the optimal worst-case approximation error as a function of latent dimension M and parameter budget P.The target class is the unit ball of α-Hölder functions on [0,1]^d, with 0 < α ≤ 1.
Main result: (PM)^-α/d is the sharp rate when M ≤ P, whereas the rate saturates at P^-2α/d when M ≥ P.The bounds hold up to constants depending only on d and α under the stated nondegenerate conditions.
Main result: Fixed width depending only on d and depth growing at most linearly with P achieve the upper bound, while the lower bound covers every admissible fully connected ReLU architecture.The construction and converse therefore characterize the optimal use of one shared affine latent space, not a particular architecture.
Fixed latent dimension: For any fixed M0 ≥ 4, the sharp rate becomes P^-α/d, so constant target-dependent dimension still yields algebraically vanishing worst-case error.The faster saturated rate P^-2α/d requires M ≥ P.

2 Related work, interpretation, and scope

The paper situates its result among related empirical and theoretical work, then interprets the joint resource law and clarifies its scope. It distinguishes affine parameterizations from nonlinear relatives and discusses resource accounting, optimization geometry, and exact-real-arithmetic assumptions.

Overview: Section 2 reviews closely related empirical and theoretical work before interpreting the joint law in P and M.It also clarifies the result’s scope.
Overview: Sections 2.1 and 2.2 distinguish affine parameterizations from nonlinear relatives.
Overview: Sections 2.3 through 2.6 cover approximation and capacity theory, resource accounting, optimization geometry, and exact real arithmetic.The background is not used as an assumption in the proofs.

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

Related methods reduce target-dependent parameters through prediction, tying, structured transforms, subspaces, or normalization parameters. These approaches illustrate parameter reduction, but the cited work generally does not establish a uniform two-budget minimax law for one affine map fixed across a function class.

Comparison with this paper: The paper’s distinguishing condition is that the same affine map is fixed before the target function is selected.This separates its theorem from task-specific predictors, learned subspaces, and target-network reconstruction results.
Related parameterizations: Empirical approaches include parameter prediction, weight tying, fixed subspaces, structured transforms, coordinate restrictions, and normalization-only training.They represent several ways to reduce trainable or stored parameters.
Parameter prediction and tying: HashedNets implement a sparse affine map whose rows contain one signed nonzero entry after virtual weights are enumerated.
Structured transforms: Structured expansions such as Fastfood reduce storage and multiplication cost using fixed transforms, while adaptive Deep Fried layers are generally nonlinear jointly in their factors.
Subspace training: Fixed random subspace experiments show that networks with hundreds of thousands of weights can sometimes be optimized through only hundreds or thousands of coordinates.Subsequent work also reports that reusing one random basis can impair optimization.
Comparison with this paper: These methods can use far fewer target-dependent degrees of freedom than realized-network parameters, but they do not establish a minimax law over a function class in (M, P).

2.2 Nonlinear generators and parameter-efficient adaptation

The section distinguishes nonlinear parameter generators from the affine class studied here and explains why both latent dimension and generated-parameter budgets remain relevant.

Nonlinear generators: Nonlinear generators map compact codes to full network parameters and motivate analyzing latent and deployed-model complexity jointly.Hypernetworks and Mapping Networks are examples of learned nonlinear generators; low-rank adaptation can also be nonlinear in its combined trainable factors.
Nonlinear generators: Hypernetworks may be frozen after training, but their learned map G remains nonlinear and task-specific.
Scope of existing theory: Nonlinear-generator results cited here do not establish a worst-case approximation rate over a function class in (M, P).This limitation applies to manifold-based existence and local-solvability results, experiments, and the analyzed frozen random-generator model.
Related parameter-efficient methods: Gradient low-rank projection compresses gradients and optimizer state while retaining full-rank trainable weights, so it is not a parameter map G : R^M → R^PΦ.

2.3 Approximation theory, coding, and capacity

The paper positions its theorem between coding-based parameter sharing and approximation theory, using capacity tools to obtain a joint dependence on latent and network budgets.

Theoretical viewpoints: The theorem budgets both the target code and decoder, combining exact-code, target-dependent-network, and polynomial-sign-pattern viewpoints.
Approximation theory: Classical and quantitative approximation theory relates neural-network error to architecture, smoothness, and parameter count across several activation and target-function settings.
Coding and parameter sharing: Prior intrinsic-parameter constructions achieve exponentially decreasing error in code length but allow decoder size to grow without an independent budget.The present problem studies how this dependence changes when decoder size is also constrained by P.
Coding and parameter sharing: Existing shared-block constructions yield O(r^-1/d) error for Lipschitz targets but do not determine arbitrary joint dependence on (M, P) or provide a matching lower bound.
Capacity analysis: The paper’s capacity argument uses VC-dimension, pseudo-dimension, polynomial-pattern, and metric-entropy perspectives to support approximation bounds.

2.4 Resource accounting and endpoint regimes

The theorem identifies a product-rate regime for jointly budgeted latent codes and decoders, with endpoint behavior differing between fixed-dimensional and fully variable parameterizations.

Resource regimes: (PM)^(-α/d) is the sharp Hölder rate in the nondegenerate regime 4 ≤ M ≤ P with P sufficiently large.The construction stores quantized function-increment streams in latent coordinates and decodes them with depth proportional to P.
Resource regimes: P^(-2α/d) is recovered when M is comparable to P, matching optimal rates for very deep fixed-width networks.
Endpoint regimes: P^(-α/d) is the fixed-M rate for sufficiently large P, while saturation at M ≥ P follows from the affine rank being bounded by ambient parameter dimension.
Resource accounting: The theorem does not automatically imply total-storage compression because fixed affine-generator coefficients contain PΦM + PΦ scalar entries that are not charged to M.Charging those coefficients, imposing sparsity or fast transforms, or regenerating them from seeds would define different resource models.

2.5 Optimization geometry and conditioning

The affine parameterization induces an optimization geometry determined by the generator’s effective rank and coordinate system, separate from the approximation problem itself.

Optimization geometry: The approximation problem does not prescribe an algorithm for finding ξ_f, but the affine parameterization makes its optimization geometry explicit.
Effective coordinates: The pullback Hessian becomes singular when rank(A) < M, so redundant latent directions must be removed before defining an ordinary condition number.If rank(A)=0, the affine family contains only one parameter vector and has no latent condition number.
Effective coordinates: A local condition number is defined in effective coordinates when the reduced matrix is positive definite.
Conditioning caveat: Conditioning depends on the specified coordinates because nonorthogonal changes within the same affine image can alter the condition number.Jointly optimizing approximation quality and conditioning for a prescribed loss is a separate problem.

2.6 Exact real arithmetic, discontinuity, and scope

The theory uses exact real parameters and therefore separates parameter-count expressivity from bit complexity, stability, optimization, and architectural scope. Its guarantees are restricted to affine generators and fully connected ReLU networks, with matching optimality stated for a normalized Hölder class in the uniform norm.

Exact real arithmetic: Exact real arithmetic allows increasingly long binary streams in latent coordinates, with decoder-weight dynamic range growing exponentially in decoded-bit length.The target-to-latent selection map is discontinuous, and finite-precision latent codes introduce an additional information obstruction of order (Mb)^−α/d.
Scope limitations: The main theorem concerns real-parameter expressivity, not bit complexity, perturbation or noise stability, or gradient-descent behavior.Weights are counted by slots, but their magnitudes are not uniformly bounded.
Architectural scope: The architectural theory is restricted to fully connected ReLU networks, excluding claims for convolutional architectures or other activations.The activation and architecture are identified as substantive restrictions with separate corresponding theories.
Theorem boundaries: The upper construction uses width depending only on d and depth growing with P, while no upper-bound theorem is claimed at fixed depth or for nonlinear generators.The lower bound allows every fully connected architecture with at most P dense parameter slots under the paper’s convention.
Theorem boundaries: Matching optimality is proved only for the normalized Hölder class in the uniform norm, and the affine map is chosen constructively rather than randomly.The upper construction itself applies to every continuous function on the cube.
Scope: The paper isolates one affine latent parameterization over exact real numbers with independently charged latent and decoder budgets, while the optimal construction has width depending only on d.The minimax class imposes no explicit width bound.

3 Problem formulation and main results

The paper formulates a minimax problem for affine latent parameterizations shared across a Hölder function class and fully connected ReLU decoders. It establishes matching upper and lower bounds with sharp joint dependence on latent dimension M and parameter budget P, including a fixed-M regime with vanishing error.

3 Problem formulation and main results: The problem formulation fixes notation, architecture classes, affine latent families, and target classes before stating matching upper and lower bounds.The input dimension is tied to the target domain, and the output is scalar.
Network architectures: A fully connected ReLU architecture is specified by hidden-layer widths and depth, with every dense weight and bias entry counted in PΦ.No separate width or depth restriction is imposed in Archpar(P).
Affine latent parameterizations: The affine generator has fixed matrices A and a, while only the latent vector ξ may vary with the target function.The pair (Φ, A) is selected independently of the target.
Target class and minimax error: The minimax error chooses the architecture and affine map before the target, then selects a target-dependent latent vector to approximate each function.This ordering makes the shared decoder and generator explicit in the optimization.
3.2 Main results: Theorem 3.1 supplies a target-independent architecture and affine map achieving the upper bound once min{M, P} ≥4 and P exceeds the dimension-dependent threshold.The construction lies in the prescribed parameter and depth-budget classes.
3.2 Main results: Theorem 3.3 gives a uniform lower bound over all admissible architectures and affine parameterizations, with constants independent of M, P, depth, architecture, and affine map.The converse is established through affine-rank capacity control and localized Hölder-function packing.
3.2 Main results: The upper and lower bounds match up to constants depending only on (α, d), and fixed M still yields algebraically vanishing error as P grows.When M ≥P, the rate instead saturates at P −2α/d; the fixed-M regime is relevant to parameter-efficient approximation.

4 Constructive proof of the upper bound

The constructive upper bound assembles fixed-width ReLU modules that load target data affinely, decode it through fixed components, and repair boundary errors while respecting prescribed budgets. The resulting architecture keeps target dependence affine and achieves the required resource scaling, with exact-arithmetic limitations.

4 Constructive proof of the upper bound: The construction combines serialized hinge sums, an affine spline loader, binary prefix extraction, spatial addressing, and median boundary repair.These modules are assembled through retained states, fixed interfaces, parallel execution, and affine slot assignments.
4 Constructive proof of the upper bound: The serialized hinge representation keeps width fixed while depth grows linearly with the number of hinges.Signed values are transported through positive and negative ReLU channels.
4 Constructive proof of the upper bound: Each target-dependent spline-loader slot depends on at most three consecutive entries of the data vector.The loader uses width at most 5 and hidden depth at most 2S + 2.
4 Constructive proof of the upper bound: Median boundary repair expands reliable regions coordinatewise and yields a uniform estimate after repairing all d coordinates.Each repair adds two hidden layers, so the final depth is at most L + 2d.
4 Constructive proof of the upper bound: The construction assumes exact real arithmetic and provides no bound on latent bit length, decoder dynamic range, or numerical stability.Restricting each latent scalar to b bits additionally limits total latent information to Mb.
4 Constructive proof of the upper bound: The integer budget choices satisfy D = ⌊P/Bd⌋, 3S + 1 ≤ min{M, P}, and SD ≥ P min{M, P}.Thus the product of code blocks and decoder length determines the approximation scale.

5 Proof of the H¨older lower bound

The lower bound reduces affine latent parameterizations to their effective rank, bounds the resulting network family's capacity through polynomial sign patterns, and converts that capacity into uniform approximation error using Hölder bump packings.

5 Proof of the H¨older lower bound: The lower-bound proof applies to every admissible architecture-generator pair with input dimension d and at most P parameter slots.It begins by defining the relevant function family and capacity quantity.
5 Proof of the H¨older lower bound: Affine substitution θ = A(ξ) removes redundant latent directions and leaves at most min{M, PΦ} effective parameter variables.This rank reduction is the key link between latent dimension and ambient network budget.
5 Proof of the H¨older lower bound: Binary polynomial sign-pattern counting yields a capacity estimate for the affine-parameterized ReLU family.The proof develops VC-dimension, pseudo-dimension, Boolean-formula, and polynomial-pattern tools.
5 Proof of the H¨older lower bound: Hölder bump packings convert the capacity upper bound into a uniform approximation lower bound.The construction uses binary choices of positive and negative Hölder bumps with V0 := 8P min{M, P} ≥ 1.

VC dimension and pseudo-dimension

The paper converts real-valued network classes into binary subgraph classes to analyze pseudo-dimension, then bounds affine-tied ReLU networks through effective latent directions and activation-pattern formulas. This capacity bound feeds a H¨older bump-packing argument for the minimax lower bound.

Definitions: Pseudo-dimension is the VC dimension of the lifted subgraph class, obtained by thresholding real-valued functions on pairs (x, t).A lifted point receives label one when t lies strictly below the function value at x.
Definitions: A set is shattered when every binary labeling of its points is realized by some class member.The quantifier order fixes the points first, then permits a different function for each labeling.
Definitions: Pseudo-dimension shattering requires pairwise distinct base inputs, because differing thresholds at the same input can make requested labels inconsistent.The lifted points must be distinct, and the same-input contradiction follows from the threshold inequalities.
Boolean-polynomial descriptions: The fixed Boolean-polynomial description combines polynomial sign tests with a formula tree whose structure is chosen before the arguments are given.Repeated comparisons count as separate syntactic leaf occurrences, even when they produce identical bits.
Affine-tied ReLU networks: Affine rank reduction leaves rA effective variables, while each activation pattern contributes polynomial predicates that are combined into one exact subgraph formula.Formal and actual forward passes agree pattern by pattern, including zero-preactivation boundaries.
Capacity bound: Activation-pattern enumeration is logarithmic in the pseudo-dimension bound, since 2^UΦ patterns contribute log2(2^UΦ)=UΦ rather than an exponential factor.The resulting capacity reflects both independent affine directions and the fixed network’s piecewise-polynomial computation.
Lower bound: The capacity bound yields a uniform approximation lower bound through disjoint H¨older tents whose independently chosen signs would otherwise shatter too many centers.The contradiction compares the number of packed centers with the VC dimension of the zero-threshold class.

6 Conclusion

The conclusion establishes matching sharp rates for fully connected ReLU networks with affine latent parameterizations, with the upper construction attainable using width depending only on input dimension. It also identifies constant-dimensional latent spaces as sufficient for vanishing error and states expressivity limitations involving precision, stability, optimization, and nonlinear generators.

Sharp rate: Matching upper and lower bounds determine the sharp approximation rate for fully connected ReLU networks with affine latent parameterizations.The minimax problem ranges over architectures with input dimension d and budget P.
Construction: A fixed architecture-generator pair attains the upper bound with network width depending only on d.The target dependence remains in a suitable latent vector ξf.
Latent-dimension regimes: For fixed M0 ≥4, the sharp rate is P^-α/d once P exceeds the stated threshold.Thus constant latent dimension still gives vanishing worst-case error as the network budget grows.
Latent-dimension regimes: In the fully saturated regime M ≥P, the rate improves to P^-2α/d.The result captures a tradeoff between target-dependent latent information and fixed decoding capacity.
Scope and limitations: The expressivity result assumes exact real arithmetic, discontinuous target-to-latent encoding, and a decoder whose size grows with the budget.Finite precision, stability, efficient optimization, bounded weights, and nonlinear generators under explicit budgets remain outside the analysis.