PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning via Dynamical Systems: An Approximation Perspective

Qianxiao Li, Ting Lin, Zuowei Shen

arXiv:1912.10382v2cs.LGmath.OCstat.ML

TL;DR

Deep learning theory still needs to explain the role of sequential function composition. This paper studies continuous-time residual networks through their dynamical-system flow maps and gives sufficient conditions for universal approximation. Its approximation conclusions apply in Lp over compact sets, subject to the stated conditions.

  • Problem

    A theoretical framework is needed to understand deep learning's effectiveness by capturing sequential function composition in neural networks.

    Source: §1 · p. 1, §1.2 · p. 4

  • Method

    The paper analyzes continuous-time residual networks as ODE flow maps and establishes sufficient conditions on control and terminal families for approximation.

    Source: §1.3 · p. 5, §2.2 · p. 7

  • Results

    Under sufficient conditions on the control and terminal families, the continuous-time hypothesis space approximates continuous functions in Lp on compact sets.

    Source: §2.2 · p. 8

  • Takeaways & Limitations

    The results characterize when structurally constrained dynamical-system flow maps provide universal approximation.

    Source: §2.2 · pp. 7–8

    The ODE analysis assumes each vector field is Lipschitz continuous so that solutions are unique.

    Source: §1.3 · p. 5

Abstract

from arXiv · show

We build on the dynamical systems approach to deep learning, where deep residual networks are idealized as continuous-time dynamical systems, from the approximation perspective. In particular, we establish general sufficient conditions for universal approximation using continuous-time deep residual networks, which can also be understood as approximation theories in $L^p$ using flow maps of dynamical systems. In specific cases, rates of approximation in terms of the time horizon are also established. Overall, these results reveal that composition function approximation through flow maps present a new paradigm in approximation theory and contributes to building a useful mathematical framework to investigate deep learning.

1 Introduction and Problem Formulation

The section frames approximation by continuous-time dynamical systems as a way to study the composition central to deep residual networks, and distinguishes approximation from exact representation.

1 Introduction and Problem Formulation

  • A theoretical account of deep learning must address sequential function composition, and this paper studies approximation properties that remain underexplored in the dynamical-systems approach.Earlier work developed algorithms, architectures, applications, and optimization analyses, while this paper turns to function approximation.Source: §1 · pp. 1–2

1.3 The Dynamical Systems Viewpoint

  • The dynamical-systems idealization treats a deep network as a discretization of an ODE, making continuous-time analysis tools available for studying composition and approximation.A precise limit uses increments δf_{θ_s}(z_s), with δ→0 while T=Sδ remains fixed.Source: §1 · pp. 1–2, §1.3 · pp. 4–5

1.1 The Supervised Learning Setting

  • Supervised learning seeks a hypothesis-space function approximating a target mapping from inputs to outputs, typically by minimizing expected loss or its empirical counterpart.When the input distribution is unavailable explicitly, observed input-output samples define the empirical measure used for training.Source: §1.1 · pp. 2–3

1.2 Deep Residual Neural Networks

  • A residual network iterates z_{s+1}=z_s+f_{θ_s}(z_s), then composes the resulting flow map with a terminal output map.The layer functions may vary in form; the analysis assumes common parameter dimensions for simplicity.Source: §1.2 · pp. 3–4

1.3 The Dynamical Systems Viewpoint

  • The continuous-time viewpoint replaces discrete layer indices with an ODE whose flow map is composed with a terminal family to form the hypothesis space.The paper assumes Lipschitz-continuous vector fields and essentially bounded time-dependent parameters.Source: §1.3 · pp. 4–5

1.4 The Problem of Approximation

  • The paper asks what functions the continuous-time hypothesis space can approximate, seeking approximation sets with useful computational structure rather than density alone.The distinction matters because inability to represent a function exactly does not rule out arbitrary-accuracy approximation.Source: §1.3 · p. 5, §1.4 · pp. 5–6
  • Approximation asks whether functions can be approached arbitrarily closely, whereas representation requires exact membership in the hypothesis space.Flow maps are orientation-preserving, yet orientation-preserving diffeomorphisms are dense in Lp in dimensions above one; the paper seeks density with structural constraints.Source: §1.4 · pp. 5–6
  • For finite time and a fixed compact domain, Euler discretization has O(T/S) global truncation error in supremum norm, linking continuous-time approximation to sufficiently deep residual networks.Thus, a function approximable by the ODE hypothesis space is also approximable by a sufficiently deep discretized residual network.Source: §1.4 · p. 6

2 Main Results and Implications

This section establishes sufficient conditions for universal approximation by continuous-time deep residual networks and examines how flow maps compose simple transformations across neural-network architectures. It also recasts linear approximation compositionally and connects flow-map approximation to controllability and density in Lp.

2.2 Approximation Results

  • For n≥2, Hode is universally approximating in Lp on compact sets when terminal outputs cover target ranges, CH(F) contains a well function, and F is restricted-affine-invariant.The theorem applies for any p∈[1, ∞), compact K, and ε>0; its range condition requires a Lipschitz terminal function g whose range covers the target values on K.Source: §2.2 · p. 8
  • In one dimension, only continuous increasing targets are approximable; the result assumes increasing controls and also allows C(K) approximation with symmetry and translation invariance.Flow maps and their closure remain increasing, so they cannot approximate a function strictly decreasing on an open interval.Source: §2.2 · pp. 8–9
  • Fully connected residual networks with ReLU, sigmoid, or tanh activations have the universal approximation property, with the framework requiring relatively little effort for activation variations.For sigmoid, the soft-threshold approximation error can be made arbitrarily small by taking M=N^2 to infinity.Source: §2.2 · pp. 9–11
  • Residual blocks with multiple fully connected layers also yield universal approximation when the activation satisfies a non-degeneracy condition and the control family contains a non-negative well function.The non-degeneracy condition requires a closed interval whose pre-image under the activation is also a closed interval.Source: §2.2 · pp. 11–12
  • Linear activations do not yield universal approximation: their flow maps remain linear, and the control family lacks a well function in CH(F).Source: §2.2 · p. 12

2.3 Approximation of Functions by Composition

  • Linear N-term approximation is recast compositionally as a linear terminal family composed with a transformation whose coordinates are the first N dictionary functions.Source: §2.3 · p. 13
  • Hode achieves universal approximation with fixed-dimensional terminal outputs because its complexity arises from composing simple transformations, not from linear combinations.Flow maps can be decomposed into near-identity compositions generated by a control family, and the approximation result holds under the assumptions of Theorem 2.3.Source: §2.3 · pp. 14–15

2.4 Approximation Theory of Deep Neural Networks

  • For n ≥ 2, the results do not require embedding the dynamical system in higher dimensions to achieve universal approximation.Although ODE flow maps are orientation-preserving, such maps can approximate any L∞ function on open bounded domains in dimensions at least two.Source: §2.4 · p. 16
  • Sufficient conditions on control family F and terminal family G yield universal approximation without requiring a preset architecture or universal-approximating controls.This separates approximation power due to composition from that due to architectural choices and allows applicability to diverse architectures.Source: §2.4 · pp. 16–17

2.5 Control Theory and Dynamical Systems

  • Flow-map approximation is a function-space controllability problem: one control steers an entire input set, and the paper gives sufficient conditions for flow-map density in Lp.The paper offers an alternative construction to prior approximation by orientation-preserving diffeomorphisms; exact-representation restrictions do not contradict approximation results.Source: §2.5 · pp. 17–18

3 Preliminaries

The preliminaries establish ODE and flow-map properties, reduce function approximation to approximating domain transformations, and characterize approximation through attainable sets and control-family closures.

3.1 Background Results on Ordinary Differential Equations

  • For Lipschitz vector fields, ODE solutions exist uniquely and depend continuously on initial conditions; with additional smoothness, flow maps are orientation-preserving diffeomorphisms.In one dimension, flow maps remain increasing, including in the stated setting without differentiability.Source: §3.1 · pp. 19–20
  • In one dimension, uniqueness preserves the order of trajectories, so flow maps are increasing homeomorphisms even without differentiability.The paper uses this orientation-preserving property in its subsequent results.Source: §3.1 · p. 20
  • On a compact set of initial values, the finite-time solution’s modulus of continuity tends uniformly to zero as the input perturbation vanishes.This is stated as a practical consequence of classical ODE results.Source: §3.1 · p. 20
  • For a one-dimensional well function that is negative to the right of x0, a trajectory starting at x2 can reach any x1 between x0 and x2 in finite time.For f(z) = −ReLU(z − x0), the example gives T = ln((x2 − x0)/(x1 − x0)).Source: §3.1 · p. 21

3.2 From Approximation of Functions to Approximations of Domain Transformations

  • Under Proposition 3.8’s conditions, approximating continuous domain transformations in Lp suffices to approximate continuous target functions after composition with a Lipschitz terminal map.The conditions include that the terminal map’s range contains the target’s image on the compact input set.Source: §3.2 · pp. 22–23

3.3 Properties of Attainable Sets and Approximation Closures

  • The attainable set comprises flow maps generated up to a finite horizon by piecewise-constant controls, and approximating these transformations suffices for the stated universal-approximation goal.The paper restricts attention to piecewise-constant-in-time controls for its approximation results.Source: §3.3 · pp. 23–24
  • For driving a dynamical system, a Lipschitz control family has the same approximation ability as its convex hull, which may be a much larger function family.The paper presents this as a consequence of continuous evolution viewed as a family of compositions.Source: §3.3 · p. 24

4 Proof of Main Results

The proofs develop flow-map constructions for approximation, beginning with well-function rearrangement dynamics in one dimension and extending to higher-dimensional universal approximation and time-horizon-dependent rates. They also establish finite-point constructions leading to Lp approximation and, under stated conditions, results for tensor-product systems and finitely many distinct inputs.

4.1 Approximation Results in One Dimension and the Proof of Theorem 2.4

  • In one dimension, ReLU-driven flows approximate every continuous increasing function uniformly on compact sets, while attainable maps are increasing and cannot approximate a function decreasing on an interval.The approximation result holds for any ε > 0 and compact K ⊂ R.Source: §4.1 · p. 27
  • The one-dimensional approximation conclusion also holds for symmetric, translation-invariant control families when CH(F) contains a well function.These family properties provide sufficient conditions without requiring a specific architecture.Source: §4.1 · p. 29

4.2 Approximation Rates in One Dimension

  • Bounding |v| and |w| by 1 removes ReLU positive homogeneity’s time-rescaling effect, making the time horizon a meaningful approximation budget.The analysis focuses on targets on [0, 1] with the ReLU control family.Source: §4.2 · p. 30
  • For targets with ∥ln ϕ′∥TV ≤ T, the approximation space can be constrained to flow maps with horizon up to finite T0; this variation measures complexity under the compositional approximation procedure.Source: §4.2 · p. 32
  • When T < ∥ln ϕ′∥TV, ET(ϕ) is given by an optimization problem; for increasing u, (4.14) has solution 1/2(∥u∥TV − T), and for u increasing on [0, s] then decreasing on [s, 1], 1/4(∥u∥TV − T).Source: §4.2 · pp. 32–33

4.3 Approximation Results in Higher Dimensions and the Proof of Theorem 2.3

  • For n ≥ 2, restricted affine invariance and a well function in CH(F) suffice to approximate every continuous target in Lp on compact sets, for any finite p.For every compact K and ε > 0, some mapping in AF has Lp(K) error at most ε.Source: §4.3 · p. 34

4.3.1 Preliminaries

  • With a well function, finitely many distinct source points can be mapped by an attainable flow to target points within any prescribed ε, even when targets coincide.The result applies to x1, …, xm distinct and arbitrary targets y1, …, ym in Rn.Source: §4.3.1 · p. 34
  • For distinct points, flow maps can stay arbitrarily close to identity while separating their coordinate values, then approximately transport them to arbitrary targets.The separation construction reduces the number of coordinate collisions; target coordinates are assigned sequentially by composing transformations.Source: §4.3.1 · pp. 34–36

4.3.2 Proof of Proposition 4.11.

  • Proposition 4.11’s proof approximates Lp functions by contracting grid cells toward points, then transporting those points to the piecewise-constant targets.An approximate contraction is constructed in the flow-map family, and the resulting composition achieves any prescribed Lp error.Source: §4.3.2 · pp. 37–38

4.4 Approximation Results in Tensor-Product Type Dynamical Systems

  • Under Proposition 4.15’s conditions, tensor-product flow maps approximate continuous functions on compact sets in Lp for 1 < p ≤ ∞.The result is not a corollary of Proposition 4.11 because the tensor-product well function may have an unbounded zero set.Source: §4.4 · p. 39
  • In the tensor-product family, if g is a one-dimensional flow map, the shear (x1, x2, …, xn) ↦ (x1 + g(x2), x2, …, xn) is also a flow map.The proof constructs it using transformations that preserve x1 − x2, together with a map applying g^-1 to the second coordinate.Source: §4.4 · p. 40
  • Under Proposition 4.15’s conditions, tensor-product flow maps can approximately separate distinct points coordinatewise and then transport them to arbitrary target points.The target-transport result assumes the input points already have distinct values in every coordinate.Source: §4.4 · pp. 40–41
  • For any ε > 0, distinct x1, …, xm ∈ R^n, and targets y1, …, ym ∈ R^n, some ψ ∈ AF(n) satisfies |ψ(xk) − yk| ≤ ε for every k.This result applies when F^(n) and F satisfy the conditions in Proposition 4.15.Source: §4.4 · p. 41

Related papers

Loading 1912.10382v2…