The Parametric Complexity of Operator Learning

1.1. Context and Literature Review.

• Universal approximation results do not quantify the cost of achieving a small error, motivating explicit complexity analysis for neural operators.Source: §1.1 · p. 2
• The paper names the infinite-dimensional scaling limit of the curse of dimensionality the curse of parametric complexity, distinct from high-but-finite-dimensional approximation.Source: §1.1 · p. 2
• For classes characterized only by Cr- or Lipschitz-regularity, required parametric complexity can grow exponentially in inverse error.Source: §1.1 · pp. 2–3
• For HJ solution operators, characteristic-based additional structure can overcome the general barrier; the spatial dimension d is fixed.Source: §1.1 · pp. 3–4

1.2. Organization.

• Section 2 establishes the general barrier; later sections set up the HJ equation, introduce HJ-Net, prove its approximation result, and conclude, with technical proofs in the appendix.Source: §1.2 · p. 4

2. The Curse of Parametric Complexity.

• Common operator-learning frameworks combine a finite-dimensional input encoder, a neural-network approximation map, and an output reconstruction map.The approximation map typically acts between high-dimensional encoded spaces, motivating the paper’s focus on neural-network approximation theory.Source: §2 · pp. 4–5

2.1.3. Approximation Theory and CoD for ReLU Networks.

• Proposition 2.1 shows that for every dimension D, some C^r function on [0, 1]^D requires neural-network complexity with an algebraic lower-bound exponent proportional to D.The passage relates this lower bound to classical approximation rates and suggests practical efficiency may depend on structure beyond smoothness.Source: §2.1.3 · p. 6

2.2.1. Infinite-dimensional hypercubes.

• Smoothness-constrained compact sets in function spaces can contain infinite-dimensional hypercubes, whose coefficient decay rate α measures their asymptotic size and enters the complexity bounds.For the stated C^s setting with a C^ρ constraint, the set contains such a hypercube for any α > 1 + ρ − s; similar structure is noted for Sobolev and Besov spaces.Source: §2.2.1 · pp. 7–8

2.2.2. Curse of Parametric Complexity.

• The analysis asks how many tunable parameters are needed for accuracy ε and defines neural-network-type functionals as a linear map from X followed by a ReLU network.For function-valued outputs, the corresponding operator class requires each point evaluation to have this form, with the network allowed to depend on the evaluation point.Source: §2.2.2 · pp. 8–10

2.3. Main Theorem on Curse of Parametric Complexity.

• Theorem 2.11 establishes a curse of parametric complexity for approximating some r-times Fréchet differentiable functionals on compact subsets of infinite-dimensional Banach spaces containing an infinite-dimensional hypercube.The theorem’s accuracy constants depend only on the hypercube decay rate α, δ, and r; Corollary 2.12 extends the result to function-space outputs continuously embedded in C(Ω; Rp).Source: §2.3 · p. 10
• The proof reduces operator approximation to finite-dimensional neural-network approximation by embedding rescaled cubes in the input set; sparse concatenation is identified as a key issue in ReLU network calculus.The argument constructs functionals that inherit the finite-dimensional lower bound, while the network-calculus discussion notes that sparse structure must be preserved.Source: §2.1.2 · p. 6, §2.3 · p. 11
• General classes specified only by C^r- or Lipschitz regularity cannot in general achieve better than exponential complexity bounds, an infinite-dimensional analogue of the curse of dimensionality.Theorem 2.11 is derived for ReLU networks; the authors note that non-standard architectures and superexpressive activations with algebraic rates [62] do not contradict it, and may require exponential weight-storage accuracy.Source: §2.3 · p. 12

2.4. Examples of Operators of Neural Network-Type.

• For any r ∈ N and δ > 0, with X and Y Hilbert spaces, some r-times Fréchet differentiable functional forces any PCA-Net network Ψ to satisfy size(Ψ) ≥ exp(c ε^-1/((α+1+δ)r)) for some ε > 0.The constants c and ε depend only on α, δ, r, and p.Source: §2.4 · pp. 13–14
• In the setting of Corollary 2.12, for any r ∈ N and δ > 0, some r-times Fréchet differentiable functional has approximation at accuracy ε imply size(Ψ) + size(φ) ≥ exp(cε^-1/((α+1+δ)r)), with c, ε > 0 depending only on α, δ, and r.Source: §2.4 · pp. 14–15
• In the setting of Corollary 2.12, for any r ∈ N and δ > 0, some r-times Fréchet-differentiable functional requires size(Ψ) + size(Q) ≥ exp(cε−1/(α+1+δ)r) for approximation to accuracy ε ≤ ε.The left-hand expression represents the NOMAD architecture’s total number of non-zero degrees of freedom, which is lower bounded by the stated notion of complexity.Source: §2.4 · p. 15

2.5. The Curse of (Parametric) Complexity for Fourier Neural Operators.

• With ReLU activation on the periodic torus, the FNO is not of neural-network type as defined in the preceding subsection.The paper introduces a separate FNO result because this architecture is outside that framework; the supplied passage states the lemma but does not give its curse bound.Source: §2.5 · p. 17
• For some r-times differentiable functionals on compact input classes containing an infinite-dimensional hypercube, ε-accurate discretized FNO approximation requires exponentially large size or discretization parameter N.Theorem 2.27 gives the lower bound exp(cε^-1/((α+1+δ)r)) for either quantity, for any r ∈ N and δ > 0.Source: §2.5 · p. 18
• The FNO lower bound parallels the curses for DeepONet and PCA-Net, while its computational complexity depends on both its coefficients and the discretization parameter N.The discussion attributes this distinction to FNO not being neural network-type until discretized.Source: §2.5 · p. 19

2.5.1. Discussion.

• Efficient operator learning must leverage structure beyond C^r- or Lipschitz-regularity; the paper identifies such structure in Hamilton-Jacobi equations and proposes a framework to exploit it.The discussion distinguishes this approach from prior work focused on operator holomorphy or emulation of numerical methods.Source: §2.5.1 · p. 19

3. The Hamilton-Jacobi Equation

• The framework studies HJ solution operators on periodic domains and restricts attention to problems with classical C^r solutions, r ≥ 2.The common existence interval for data in compact F is chosen sufficiently small.Source: §3 · pp. 19–20

3.1. Method of Characteristics for (HJ).

• When u is twice continuously differentiable, characteristics determine its values by solving a Hamiltonian ODE and evaluating the action along each trajectory.The equivalent ODE system tracks spatial position, momentum, and the solution value.Source: §3.1 · p. 20

3.2. Short-time Existence of Cr-solutions.

• For compact initial-data sets F in C^r_per(Ω), r ≥ 2, the HJ solution operator is defined over a common sufficiently short time interval.The interval is bounded by T*(F), and the solutions remain uniformly bounded in C^r for every T < T*(F).Source: §3 · p. 20, §3.2 · p. 21

3.3. Limitations of the setting considered in this work.

• Crossing spatial characteristics can make the characteristic solution ill-defined and restrict existence to finite time; extending the approach to nonunique generalized characteristics remains open.The analysis is restricted to smooth solutions and nonintersecting characteristics.Source: §3.3 · pp. 22–23, §3.2 · p. 22

4. Hamilton-Jacobi Neural Operator: HJ-Net

• HJ-Net encodes initial data at fixed points, applies an approximate Hamiltonian flow to the encoded data, then projects and reconstructs an output function.The reconstruction uses moving least squares; the flow can be approximated independently of the underlying solution.Source: §4 · p. 23, §4.2 · p. 24
• The approximation is well-defined on a compact input set only over a sufficiently small time interval, and is for fixed time rather than a semigroup.Iteration is not generally possible unless the approximator maps the input set into itself; periodicity of the reconstruction is not addressed.Source: §4 · p. 23

4.1. Step b) ReLU Network.

• A ReLU network approximates the Hamiltonian flow, with its parameters chosen by minimizing an empirical loss using sampled flow evaluations.The empirical loss is based on i.i.d. samples and can be approximately minimized by stochastic gradient descent.Source: §4.1 · p. 24

4.2. Step c) Moving Least Squares.

• Moving least squares reconstructs the function from scattered input-output data, using polynomial degree r − 1 and a compactly supported weight.Its error depends on point density and function smoothness; in HJ-Net, pruning produces a quasi-uniform set from flow-dependent evaluation points.Source: §4.2 · pp. 24–25

4.3. Summary of HJ-Net.

• The reconstruction has discretization error even with exact data, plus additional error from approximate flow-generated points and values.The final HJ-Net applies the encoder, approximate flow, projection, and pruned moving least squares reconstruction.Source: §4.2 · p. 25, §4.3 · p. 26

5.1. HJ-Net Beats The Curse of Parametric Complexity.

• HJ-Net’s parameterization size grows algebraically with inverse error, overcoming the curse of parametric complexity for the stated Hamilton–Jacobi setting.The theorem assumes periodic-domain initial data in a compact Cr class, a Cr+1 Hamiltonian satisfying the no-blowup assumption, and sufficiently short times.Source: §5 · p. 27, §5.1 · pp. 27, 29
• The analysis uses uniform sampling for simplicity, although input-dependent non-uniform sampling could improve interpolation in some cases.The authors note that such sampling would likely not yield faster asymptotic convergence rates.Source: §5.1 · p. 29
• For moderate d and smoothness r > 3d+1, the overall computational complexity is at most O(ε^-1).The bound accounts for flow-network evaluations, pruning comparisons, and moving least squares reconstruction; the flow network has logarithmic depth and a size bound stated in the theorem.Source: §5.1 · pp. 27, 29

5.2. Approximation of Hamiltonian Flow and Quadrature Map.

• The flow-approximation analysis allows a smaller network size at the cost of increasing depth from logarithmic to algebraic scaling.The alternative size bound neglects logarithmic terms in ε^-1.Source: §5.2 · p. 30

5.3. Moving Least Squares Reconstruction Error.

• The reconstruction error bound covers pruned moving least squares with approximate data, without assuming either exact or approximate point sets are quasi-uniform.The analysis combines reconstruction-error control with a uniform bound on the fill distance of characteristic-mapped evaluation points.Source: §5.3 · pp. 30–31

6. Conclusions

• For general operator classes characterized only by Cr- or Lipschitz-regularity, complexity may grow exponentially in inverse error, and efficient approximation requires additional structure beyond regularity.The lower bound applies to standard feedforward ReLU-based neural operator architectures, including PCA-Net, FNO, DeepONet, and recent nonlinear extensions.Source: §6 · p. 31
• HJ-Net leverages characteristic structure to tame the curse for Hamilton–Jacobi solution operators, but the approach is restricted to finite intervals with classical solutions.The authors identify extension to viscosity solutions after singularity formation as a direction for investigation.Source: §6 · pp. 31–32
• Analyzing symplectic neural networks and extending error estimates to the C1 topology are identified as future steps toward generalizing HJ-Net and iterating the learned operator.The paper says its current analysis is not developed enough to use symplectic neural networks in the complexity analysis.Source: §6 · p. 32

Appendix A. Proof of Curse of Parametric Complexity

• The section sets out to prove Proposition 2.1.The passage provides no further description of the proof or proposition.Source: Appendix A · p. 35

A.1. Preliminaries in Finite Dimensions.

• N(f, ε) counts the fewest hidden computation units in a ReLU feedforward network approximating f uniformly on the unit cube.Although functions are defined on R^D, this complexity measure concerns approximation only on [0, 1]^D.Source: §A.1 · p. 35
• The analysis relates network size to hidden-unit count by embedding networks in a fully connected architecture with a dimension-dependent size bound.Each non-trivial hidden unit contributes at least one connection or bias; the number of computation units counts activation evaluations in a forward pass.Source: §A.1 · p. 35
• For every dimension D, a C^r function requires ReLU network size at least ε^-γD/r for all sufficiently small ε, with the threshold independent of D.This strengthens Yarotsky’s result, which held only along an unspecified sequence of accuracies [67, Thm. 5].Source: §A.1 · pp. 35–36
• The lower bound follows by constructing smooth functions that encode arbitrary Boolean labels, using VC-dimension estimates to constrain network approximation.The construction is adapted to C^r functions vanishing at the origin.Source: §A.1 · pp. 36–37
• The proof constructs one hard function for arbitrary network architectures by combining dimension-specific functions with decreasing weights.The resulting lower-bound exponent is universal, and the final bound applies for every ε below a fixed threshold.Source: §A.1 · pp. 38, 40

A.2. Proof of Lemma 2.7.

• A normalized Fourier sine basis on a cube contained in Ω supplies linearly independent elements with bounded bi-orthogonal functionals.These elements satisfy the assumptions for constructing an infinite-dimensional hypercube.Source: §A.2 · p. 40
• Ordering frequencies by non-decreasing ℓ∞ norm gives an index j(κ) comparable to ||κ||∞^d.The number of frequencies in the corresponding bounded shells grows on the order of K^d.Source: §A.2 · pp. 40–41
• With sufficiently small amplitude A and an appropriate decay rate α, the resulting hypercube Qα lies inside K.The construction uses the Fourier basis elements restricted to Ω.Source: §A.2 · pp. 40–41

A.3. Proof of Theorem 2.11.

• For each D = 2k, K contains a rescaled copy of [0, 1]^D, and the embedded cubes defined by (A.10) for k ∈ N intersect only at the origin.Source: §A.3 · p. 41
• A series functional S† is constructed so its restriction to each embedded cube reproduces the corresponding finite-dimensional hard function fD.The construction uses bounded bi-orthogonal functionals to extract cube coordinates.Source: §A.3 · pp. 41–42
• Restricting a neural-operator approximation to each embedded cube yields a finite-dimensional network approximation, so the finite-dimensional lower bounds constrain operator complexity.The proof combines the resulting bounds and optimizes over admissible dimensions to obtain the claimed complexity lower bound.Source: §A.3 · pp. 42–43
• Uniform convergence of the series and its derivatives through order r ensures that S† is r-times continuously Fréchet differentiable.The differentiability argument assumes α* > 1 + α.Source: §A.3 · pp. 44–45

A.4. Proof of Corollary 2.12.

• Multiplying the scalar functional F† by a fixed nonzero function φ produces an r-times Fréchet differentiable operator S† into Y.The function space Y is continuously embedded in C(Ω), allowing evaluation at a point y where φ(y) = 1.Source: §A.4 · p. 45
• Point evaluation of any neural-operator approximation to S† gives a neural-network-type approximation to F†, transferring its exponential complexity lower bound.The scalar lower bound is at least exp(c ε^-1/(α+1+δ)r) for a constant c depending on α, δ, and r.Source: §A.4 · p. 45

A.5. Proofs of Lemmas 2.18 – 2.7.

• PCA-Net’s linear encoder and output map give a neural-network-type representation, and sparsifying the output matrix bounds its complexity using the network size of Ψ.The proof retains only columns corresponding to nonzero components of Ψ.Source: §A.5.1 · p. 46
• DeepONet is represented as neural-network-type using its linear encoder, with a sparse output matrix whose nonzero entries are bounded by size(φ).The proof counts the nonzero entries indexed by pairs (i, j) for which [φj(y)]i is nonzero.Source: §A.5.2 · p. 46

A.6. Proof of Lemma 2.26.

• Lemma 2.26’s operator is not of neural-network-type: any proposed encoder into R^ℓ has a nontrivial kernel on a D-dimensional sine subspace when D > ℓ.The proof uses a nonzero kernel vector, choosing its sign so the corresponding function is positive somewhere, to contradict the assumed representation.Source: §A.6 · p. 47

A.7. Proof of curse of parametric complexity for FNO, Theorem 2.27.

• No FNO family can satisfy both the stated accuracy and complexity bounds for the selected functional, because that would contradict the neural-network-type lower bound.The assumed family would yield operators with a faster-growing complexity upper bound than the lower bound permits as ε approaches zero.Source: §A.7 · p. 48
• Flattening the discretized FNO yields an ordinary neural network, with each Fourier layer represented using sparse matrices and the input and output layers represented exactly.For the non-local Fourier multiplier layer, the proof bounds the matrix representation’s nonzero components using the number of active channels and multiplier entries.Source: §A.7 · pp. 48–49
• The constructed operator agrees with the discretized FNO on input functions, transferring the assumed FNO accuracy and complexity bounds to the neural-network-type setting.The proof uses point evaluations at the discretization grid to define the linear input map.Source: §A.7 · p. 49

Appendix B. Short-time existence of Cr-solutions

• Assumption 3.1 prevents finite-time blow-up of the Hamiltonian trajectories, so the Hamiltonian flow exists globally in time.The proof bounds the momentum variable and uses periodicity in q to rule out blow-up there as well.Source: Appendix B · p. 50
• The implicit function theorem gives a Cr−1 inverse for the spatial characteristic map locally around each initial point and initial function.The proof combines these local maps into a global inverse over the stated interval.Source: Appendix B · pp. 50–52
• While the spatial characteristic map remains invertible, the characteristic formula defines a classical solution of the Hamilton-Jacobi equation with Cr regularity.For r = 2, the proof obtains the needed identity by approximating H and the initial data with smooth functions.Source: Appendix B · p. 52
• The solution interval ends at the maximal time T* for which the spatial characteristic map is invertible for every initial function in F.The resulting solution belongs to Cr per(Ω × [0, T*)).Source: Appendix B · pp. 52–53

Appendix C. Reconstruction from scattered data

• Pruning the scattered points produces a quasi-uniform subset with fill distance at most 3hQ,Ω and separation distance at least hQ,Ω.Its distortion constant is κ = 3.Source: Appendix C · p. 54
• Moving least squares interpolation has an approximation error bound for Cr functions on quasi-uniform samples, with parameter δ chosen proportional to the fill distance.The constants depend on dimension, regularity, and the quasi-uniformity constant.Source: Appendix C · p. 55
• With noisy point locations and values, the reconstruction argument bounds the preliminary function’s uniform error by ε + ∥f†∥Crρ.Here ε bounds value error and ρ bounds location error; the proposition’s estimate then combines this preliminary error with the interpolation estimate.Source: Appendix C · pp. 55–56

Appendix D. Complexity estimates for HJ-Net approximation

• The HJ-Net complexity analysis combines neural-network approximation of the Hamiltonian flow with reconstruction error from the pruned moving least squares operator.The flow approximation is established on a bounded domain containing trajectories from the specified initial-data domain.Source: Appendix D · p. 56, §D.1 · pp. 56–57

D.1. Approximation of Hamiltonian flow.

• Hamiltonian trajectories from initial momenta in [−M, M]d remain within [−βM, βM]d, enabling a Cr bound for the flow on that domain.β depends on dimension, the growth bound LH, and time; the flow’s Cr norm is bounded using derivatives of H.Source: §D.1 · p. 57

• Pruning yields a set Q′ whose fill and separation distances satisfy ρQ′ ≤ hQ′,Ω ≤ 3ρQ′ and hQ′,Ω ≤ 3hQ,Ω, with hQ,Ω ≤ ρQ′.Source: §D.2 · p. 57
• The perturbed pruned set Q′,† is quasi-uniform with κ = 12.The proof obtains this from bounds on its fill and separation distances, assuming hQ†,Ω ≤ h0 ≤ 1/16.Source: §D.2 · p. 58
• When hQ†,Ω ≤ h0/9, the separation-distance bound permits applying Proposition 4.2 to obtain the claimed result.The argument chooses h0 ≤ 1/16.Source: §D.2 · p. 58
• The Hamiltonian-flow estimate depends on t, H, and F, but not on the particular choice of u0.The proof sets up flows from q0 and eq0 with initial momenta given by ∇qu0 and uses Gronwall’s inequality.Source: §D.2 · pp. 58–59