PaperlayerView exact revision on arXiv

Source-linked AI summary

Overcoming the curse of dimensionality for some Hamilton--Jacobi partial differential equations via neural network architectures

Jerome Darbon, Gabriel P. Langlois, Tingwei Meng

arXiv:1910.09045v2math.OC

TL;DR

Grid-based methods face an exponential growth in required grid points for high-dimensional PDEs. This paper proves that certain neural-network architectures exactly represent viscosity solutions of specified HJ equations, with equation data encoded by network parameters. The architectures permit high-dimensional evaluation without grids, while inverse-problem experiments show that Adam training can nevertheless produce large errors.

  • Problem

    Grid-based PDE algorithms require exponentially more grid points as dimension grows, making accurate high-dimensional solution impractical in practice.

    Source: §1 · p. 1, §5 · p. 18

  • Method

    The authors prove that certain neural-network architectures represent HJ viscosity solutions, with the Hamiltonian and convex initial data obtained from network parameters.

    Source: §1 · p. 2, §5 · p. 18

  • Results

    The architecture represents specified HJ solutions and permits their evaluation in high dimension without grids or numerical approximations.

    Source: §5 · p. 18

  • Takeaways & Limitations

    Under the theorem’s conditions, some neural networks naturally encode the physics of the corresponding HJ equations.

    Source: §5 · p. 18

    Adam training for the inverse problems sometimes gives large errors, so accurate recovery is not guaranteed.

    Source: §1 · p. 3

Abstract

from arXiv · show

We propose new and original mathematical connections between Hamilton-Jacobi (HJ) partial differential equations (PDEs) with initial data and neural network architectures. Specifically, we prove that some classes of neural networks correspond to representation formulas of HJ PDE solutions whose Hamiltonians and initial data are obtained from the parameters of the neural networks. These results do not rely on universal approximation properties of neural networks; rather, our results show that some classes of neural network architectures naturally encode the physics contained in some HJ PDEs. Our results naturally yield efficient neural network-based methods for evaluating solutions of some HJ PDEs in high dimension without using grids or numerical approximations. We also present some numerical results for solving some inverse problems involving HJ PDEs using our proposed architectures.

1. Introduction

The introduction motivates high-dimensional Hamilton–Jacobi equations, for which grid-based solution methods become impractical, and presents neural architectures that exactly represent solutions under stated conditions. It also outlines a one-dimensional conservation-law connection and inverse-problem experiments, while noting that training may be inaccurate.

1. Introduction

  • Grid-based PDE methods become impractical above dimension 4 because the number of grid points needed for accuracy grows exponentially with dimension.The introduction identifies this as the curse of dimensionality, including for high-order HJ methods.Source: §1 · p. 2
  • Certain neural-network architectures exactly represent viscosity solutions of specified HJ equations, with the Hamiltonian and convex initial data determined by network parameters.The result applies when the initial data are convex and the Hamiltonian depends only on the solution gradient.Source: §1 · p. 2
  • In one dimension, a second architecture represents the spatial gradient of the HJ solution and, under conditions, corresponds to entropy solutions of conservation laws.This result is presented as a corollary for the gradient architecture and as Proposition 3.1.Source: §1 · pp. 1–2
  • The proposed architecture supports high-dimensional solution evaluation without grids, and the paper motivates this approach in part through dedicated neural-network hardware.The authors contrast it with the Hopf-formula approach in, which relies on optimization, noting that their approach does not rely on potentially non-convex optimization.Source: §1 · pp. 1–2
  • The work’s results do not rely on universal approximation; instead, the authors frame the architectures as encoding the physics of HJ equations satisfying their conditions.The introduction also situates neural networks among several existing approaches to high-dimensional HJ problems.Source: §1 · pp. 2–3
  • The paper tests recovery of unknown convex initial data from sampled HJ solutions, but Adam training sometimes gives large errors and does not guarantee accurate inverse solutions.Trained parameters provide only partial information about the Hamiltonian, approximating it at certain points.Source: §1 · p. 3

2. Background

This section reviews shallow neural networks and convex-analysis concepts used later in the paper. It describes the network’s affine and activation-function structure, training by weight and bias estimation, and convex tools including subgradients and Fenchel–Legendre transforms.

2.1. Shallow neural networks.

  • A shallow network has one hidden layer of affine functions followed by an output activation applied to their vector form, Wx + b.The hidden units use weights and biases, and the activation maps the affine outputs to a scalar.Source: §2.1 · p. 3
  • Training estimates unknown weights and biases by minimizing mean squared error; finding a global minimizer is generally difficult because the objective is nonconvex.The paper uses the Adam optimizer, a stochastic-gradient-descent-based method with momentum acceleration, in its numerical experiments.Source: §2.1 · pp. 3–4

2.2. Convex analysis.

  • The convex-analysis review defines convex sets and functions, properness, lower semicontinuity, and convex envelopes for later use.It distinguishes the convex envelope from the convex lower-semicontinuous envelope.Source: §2.2 · p. 4
  • Subgradients characterize supporting affine bounds, while Fenchel–Legendre transforms are involutive on the stated function class and satisfy Fenchel’s inequality.Equality in Fenchel’s inequality holds exactly when the vectors satisfy the corresponding subdifferential relation.Source: §2.2 · pp. 4–5

3. Connections between neural networks and Hamilton–Jacobi equations

The section connects parameterized neural networks to first-order Hamilton–Jacobi equations and, in one dimension, to conservation laws. The network parameters determine the initial data and Hamiltonian, and under stated conditions the networks represent the corresponding solutions.

3.1. Set-up.

  • The set-up defines convex polyhedral initial data J and a polyhedral Hamiltonian H from network parameters, with H(pi) = θi.The network output is a maximum of affine terms, and the parameters are subject to assumptions including distinct pi and convex interpolation of γi.Source: §3.1 · pp. 5–7

3.2. Main results: First-order Hamilton–Jacobi equations.

  • The network represents the unique uniformly continuous viscosity solution of a first-order HJ equation, with necessary and sufficient conditions specifying which Hamiltonians it solves.The equation uses the parameter-derived initial function J and Hamiltonian H; other continuous Hamiltonians qualify when they match H at the specified parameter vectors and are no smaller on dom J∗.Source: §3.2 · pp. 7–8
  • For Example 3.3, the parameterized network represents the solution with m = 2n + 5 neurons; at n = 16, the paper illustrates solution slices at t = 0, 1, 2, 3.In this example the constructed J and H coincide with the true initial data and Hamiltonian, and the network evaluates the solution without the curse of dimensionality.Source: §3.2 · p. 9, Figure 2 · p. 10
  • Replacing the maximum activation with a smooth log-exponential activation yields a network that, under θi = −1/2 ∥pi∥2^2, is the unique jointly convex smooth solution to a viscous HJ PDE.The authors note that the required form of the convex initial data restricts the result’s practicality.Source: §3.2 · p. 9

3.3. First-order one-dimensional conservation laws.

  • In one dimension, an argmax-based network represents the entropy solution u = ∇xf to a conservation law whose flux is the parameter-derived Hamiltonian H.The representation holds under the stated assumptions; the proposition characterizes compatible fluxes by their values at the parameter vectors and a lower bound on their convex hull.Source: §3.3 · pp. 9–11

4. Numerical experiments

The experiments test whether the proposed architecture and Adam can recover convex initial data from samples of first-order HJ solutions, and examine its representation of quadratic-Hamiltonian solutions and one-dimensional conservation laws. Adam's recovery is not consistently successful, while representability and approximation depend on the solution's form.

4.1. First-order Hamilton–Jacobi equations.

  • Across 100 repetitions of Cases 1–4, averaged relative mean square errors fell below 10−8 in some m=2 cases, while for m=4 global minimizers were not obtained and error exceeded 10−3.The experiments test Adam with the proposed architecture for recovering unknown convex initial data from samples of the viscosity solution.Source: §4.1 · p. 12, §4.1.1 · p. 15

4.1.2. Quadratic Hamiltonians.

  • In the first quadratic-Hamiltonian example, the solution is exactly representable with zero theoretical loss, but parameter errors were generally large and the trained network had more than 2n effective neurons.In the second example, errors grew with dimension and effective-neuron counts fell below the optimum, indicating Adam did not find global minimizers.Source: §4.1.2 · pp. 15–16

4.2. One-dimensional conservation laws.

  • For one-dimensional conservation laws, the network exactly represents the solution taking values in {±1}, but only approximates the solution spanning [−1, 1].In the latter example, error decreases as neuron count increases; the architecture represents shocks well but needs more neurons for non-constant smooth regions.Source: §4.2 · p. 18

5. Conclusion

The paper connects neural-network parameters to exact representations of viscosity solutions for certain Hamilton–Jacobi equations with convex initial data. It extends the architectures to multi-time equations and identifies high-dimensional evaluation as a potential benefit, while noting limitations in inverse-problem training and multi-time solution conditions.

5. Conclusion

  • The proposed architecture represents viscosity solutions under stated conditions, with the Hamiltonian and convex initial data recoverable from its parameters.The representation does not rely on universal approximation; the network architecture encodes the corresponding HJ problem.Source: §5 · p. 18
  • For one-dimensional HJ equations, a second architecture represents the spatial gradient of the viscosity solution and corresponds to entropy solutions of conservation laws under parameter conditions.The corresponding result is stated for appropriate parameter conditions.Source: §5 · p. 18
  • The architecture can evaluate certain HJ solutions in high dimension without grids or numerical approximations.The paper also points to dedicated neural-network hardware as a route to efficient evaluation.Source: §5 · p. 18
  • Adam generally does not solve the tested inverse problems with high accuracy using the proposed architecture.The experiments motivate further development of training algorithms for these inverse problems.Source: §5 · p. 18
  • The proposed multi-time architecture is a candidate representation for generalized Hopf-formula solutions, but the multi-time equation may lack viscosity solutions.The generalized Hopf formula is a viscosity solution under suitable assumptions; the authors defer a fuller clarification of these connections.Source: §5 · pp. 19, 21
  • The generalized Lax–Oleinik formulation motivates a deep ResNet whose kth layer uses the gradient of Hamiltonian Hk.Figure 9 illustrates two layers; the formulation is presented as a candidate for representing the generalized formula’s minimizers.Source: Figure 9 · p. 20, §5 · p. 21
  • When both the Hamiltonian and initial data are convex, the Hopf and Lax–Oleinik formulas represent the solution under appropriate assumptions.The conclusion uses these formulas to motivate architectures for the solution and its minimizer.Source: §5 · pp. 20–21
  • A ResNet-type architecture implements the Lax–Oleinik minimizer, with an activation composed of an argmax-based function and t∇H.Its layers can be chained using a sequence of time variables.Source: §5 · p. 21

A.1. Proof of Lemma 3.1.

The lemma establishes properties of the convex conjugate and characterizes minimizers of the associated optimization problem. It also identifies a coordinate-vector minimizer at each specified point p_k.

A.1. Proof of Lemma 3.1.

  • The convex conjugate J* is finite and continuous on the convex hull of the listed p_i, and its subdifferential is nonempty there.The passage invokes convex-analysis results to establish these properties.Source: §A.1 · p. 21
  • The constraints characterize minimizers of Eq. (12), with α_i equal to zero whenever i is not active at x.The active indices are those for which J(x)=⟨p_i,x⟩−γ_i.Source: §A.1 · p. 21
  • At each listed point p_k, the coordinate vector with its kth entry equal to one is a minimizer, and J*(p_k)=γ_k.The proof uses convexity of g and Jensen’s inequality.Source: §A.1 · p. 22

A.2. Proof of Lemma 3.2.

The proof establishes boundedness and continuity of H on the domain of J*, then identifies its value and a unique minimizer at each listed p_k. The theorem proof is organized around three supporting lemmas.

A.2. Proof of Lemma 3.2.

  • For p in dom J*, the feasible set A(p) is compact, which gives finite H(p) and existence of a minimizer.The proof also establishes that H is bounded on dom J*.Source: §A.2 · p. 22
  • H is continuous on dom J*, by expressing it as h(p,J*(p)) and using continuity of h and J*.The proof first establishes continuity of h on its domain.Source: §A.2 · p. 22
  • At each listed p_k, the coordinate vector is the unique minimizer and H(p_k)=θ_k.The proof compares it with any distinct feasible vector in A(p_k).Source: §A.2 · pp. 22–23

Appendix B. Proof of Theorem 3.1

  • The proof of Theorem 3.1 relies on three lemmas proved in Appendix B.1–B.3.Source: Appendix B · p. 23

B.1. Statement and proof of Lemma B.1.

Under the stated assumptions, the network output equals a max over parameterized affine terms and represents the associated solution formula. The result permits a continuous Hamiltonian upper bound that agrees with H at the specified points.

B.1. Statement and proof of Lemma B.1.

  • The network f(x,t) equals the solution formula when the continuous Hamiltonian ˜H matches H at each p_i and is at least H throughout dom J*.The theorem also assumes the listed parameters satisfy (A1)–(A3).Source: §B.1 · p. 23
  • The proof uses ˜H(p)≥H(p) to bound the formula’s objective, then applies the parameter constraints and equalities at the listed p_i.Source: §B.1 · p. 23

B.2. Statement and proof of Lemma B.2.

Under assumptions (A1)–(A3), Lemma B.2 shows that each parameter vector p_k occurs as the spatial gradient of f at some x and t > 0. The proof selects a point where the kth affine term uniquely maximizes the network representation.

B.2. Statement and proof of Lemma B.2.

  • For every k, some x and t > 0 make f differentiable with ∇_x f(x, t) = p_k.The proof reduces this to finding a point where the kth affine term strictly dominates all others.Source: §B.2 · pp. 23–24
  • Once the kth affine term strictly dominates, the subdifferential of f(·, t) at x is the singleton {p_k}.The proof uses the convex-hull characterization of the subdifferential of a finite maximum of affine functions.Source: §B.2 · pp. 24–25
  • When p_k is not already a strict maximizer at t = 0, the proof perturbs from a point where it ties with other maximizers.It uses a convex combination of tied parameter vectors and the assumptions to establish strict dominance for sufficiently small positive t.Source: §B.2 · pp. 24–25

B.3. Statement and proof of Lemma B.3.

Lemma B.3 characterizes the convex envelope of F by examining the convex hull of its epigraph. The proof constructs the hull from convex combinations of epigraph points and relates membership to the envelope value.

B.3. Statement and proof of Lemma B.3.

  • The proof computes co(epi F) by representing its points as convex combinations of points in epi F.For each constituent point, the proof applies the conditions defining epi F, including the Hamiltonian constraint and the lower bound from J*.Source: §B.3 · p. 26
  • The proof uses minimizers in the parameterized problem to construct convex combinations satisfying the epigraph constraints.For each q_i in dom J*, the minimization problem has at least one minimizer.Source: §B.3 · p. 26
  • The convex envelope value co F(p, E−) is the infimum of r for which (p, E−, r) belongs to co(epi F).This epigraph characterization links the constructed convex hull to the envelope.Source: §B.3 · p. 26

B.4. Proof of Theorem 3.1.

Theorem 3.1 connects the network’s affine-max form to viscosity solutions of the HJ equation. Its proof establishes joint convexity and characterizes when a Hamiltonian yields the network as the unique uniformly continuous viscosity solution.

B.4. Proof of Theorem 3.1.

  • The network f is jointly convex because it is the pointwise maximum of finitely many affine functions in (x, t).The theorem’s proof also establishes that the network is the unique uniformly continuous viscosity solution under its stated Hamiltonian conditions.Source: §B.4 · p. 27
  • The Hamiltonian must match H at every parameter vector p_k and satisfy ˜H(p) ≥ H(p) throughout dom J* for the stated sufficiency condition.The proof invokes the viscosity-solution result for a continuous ˜H and a convex Lipschitz initial function.Source: §B.4 · pp. 27–28
  • Conversely, if f is the unique uniformly continuous viscosity solution, then ˜H(p_k) = H(p_k) for each k.The proof isolates a point where the spatial subdifferential is {p_k}, so p_k is the only maximizer in the representation.Source: §B.4 · p. 27

Appendix C. Connections between the neural network (17) and the viscous HJ PDE (18)

Appendix C relates a parameterized neural network to a unique smooth, jointly convex solution of a viscous HJ PDE under a specified parameter choice. Appendix D includes a one-dimensional lemma about which parameter slopes maximize the representation.

Appendix C. Connections between the neural network (17) and the viscous HJ PDE (18)

  • With θ_i = −1/2 ∥p_i∥², f_ε solves the viscous HJ PDE and is its unique, jointly convex smooth solution.The proof obtains the PDE solution through the Cole–Hopf transformation of w_ε.Source: Appendix C · p. 29

Appendix D. Proof of Proposition 3.1

  • The proof of Proposition 3.1 is organized around three lemmas whose statements and proofs appear in Sections D.1–D.3.Source: Appendix D · p. 29

D.1. Statement and proof of Lemma D.1.

  • Under assumptions (A1)–(A2), for the one-dimensional function J defined using Eq. (10), any x ∈ R and p ∈ ∂J(x) unequal to every parameter value pi admit k such that pk < p < pk+1.Source: §D.1 · p. 29

D.2. Statement and proof of Lemma D.2.

Under the one-dimensional ordering and assumptions (A1)–(A3), Lemma D.2 establishes that the specified β minimizes Eq. (14) at u0. The proof first verifies β ∈ A(u0), then rules out a different minimizer by contradiction.

D.2. Statement and proof of Lemma D.2.

  • The proof first establishes β ∈ A(u0) using Lemma 3.1(ii) and Lemma D.1.For x ∈ ∂J*(u0), Lemma D.1 places both k and k + 1 among the maximizers defining Ix.Source: §D.2 · p. 30
  • If α ≠ β, the argument yields three cases, each leading to contradiction; therefore β is a minimizer in Eq. (14) evaluated at u0, and Eq. (72) follows from H’s definition.Source: §D.2 · pp. 30, 33
  • Under the lemma’s one-dimensional assumptions, β is a minimizer in Eq. (14) evaluated at u0.The conclusion follows after contradictions are obtained in all three cases.Source: §D.2 · pp. 30, 33

D.3. Statement and proof of Lemma D.3.

The appendix proves a one-dimensional inequality lemma and uses entropy-solution criteria to establish results for the conservation laws considered in Proposition 3.1. It also characterizes when a modified Hamiltonian yields the same entropy solution.

D.3. Statement and proof of Lemma D.3.

  • For ordered p_i in one dimension under (A1)–(A2), Lemma D.3’s proof uses monotonicity of ∂J* to establish its claimed inequality for the specified indices.The proof handles j = k trivially and proceeds for j < k < l.Source: §D.3 · pp. 33–34

D.4. Proof of Proposition 3.1.

  • For Proposition 3.1(i), piecewise-constant u has bounded locally BV initial data, and the proof applies an entropy-solution criterion to conclude u solves conservation law (21).It also uses that H is Lipschitz on dom J* and extends it to R while preserving that property.Source: §D.4 · p. 34, §1 · p. 36

1. The curve ¯x(t) is a straight line with the slope

  • The curve lies on a straight line, the first condition holds, and the text says both conditions are satisfied, applying [36, Prop 2.1] to conclude u is the entropy solution to conservation law (21).Source: §1 · pp. 35–36
  • For Proposition 3.1(ii), u solves conservation law (22) when H̃(pi) = H(pi) + C at each listed state and H̃(p) ≥ H(p) + C on [p1, pm], and the proof establishes this condition is necessary.The necessity argument derives the nodewise equality and the interval inequality.Source: §1 · pp. 36–37

Related papers

Loading 1910.09045v2…