Numerical approximation of McKean-Vlasov SDEs via stochastic gradient descent

Technical Summary: Numerical Approximation of McKean-Vlasov SDEs via Stochastic Gradient Descent

Problem Statement
The paper addresses the numerical approximation of McKean-Vlasov stochastic differential equations (MV-SDEs). These equations, which feature coefficients depending on the law of the solution, are fundamental in fields ranging from kinetic theory and population dynamics to finance and machine learning. The standard numerical approach involves simulating an $N_0$-dimensional interacting particle system (IPS) and relying on "propagation of chaos" results, where the empirical law of the particles converges to the law of the MV-SDE as $N_0 \to \infty$. However, the computational cost of simulating IPS scales poorly (often $O(N_0^2)$ or worse depending on the interaction kernel), making it expensive for high-precision requirements or large time horizons. The authors propose an alternative method that avoids the simulation of interacting particles entirely.

Methodology
The core contribution is a novel algorithm that casts the solution of the MV-SDE as a minimization problem solvable via Stochastic Gradient Descent (SGD). The methodology proceeds through the following steps:

1. Fixed-Point Reformulation: The authors consider a class of MV-SDEs with separable coefficients (Equation 1), where the drift and diffusion depend on the state and the measure separately. They define a functional $\Psi$ such that the solution to the MV-SDE corresponds to a fixed point $\bar{\gamma} = \Psi(\bar{\gamma})$, where $\bar{\gamma}(t)$ represents the expected values of specific functions of the process (e.g., $\mathbb{E}[\phi(X_t)]$).
2. Minimization Formulation: Finding this fixed point is reformulated as minimizing the objective function $F(\gamma) = \|\Psi(\gamma) - \gamma\|_{L^2}^2$ over the space of continuous functions.
3. Finite-Dimensional Projection: Since the domain of continuous functions is infinite-dimensional, the authors project the search space onto a finite-dimensional subspace $S_n$, typically chosen as the space of polynomials of degree $n$ (using Lagrange polynomials at Chebyshev nodes). The unknown function is approximated as $L a = \sum a_i g_i$, where $a$ is a vector of coefficients in Euclidean space.
4. SGD Algorithm: The minimization of the resulting finite-dimensional objective function $G(a)$ is performed using an SGD algorithm.
   • Gradient Computation: The gradient of the loss function is computed using the tangent processes (sensitivity equations) of an associated Markovian SDE. Specifically, the gradient involves the solution to the original SDE and its derivative with respect to the parameters $a$.
   • Mini-batch Version: A "mini-batch" version of the algorithm is introduced, averaging gradients over $M$ independent samples of Brownian motions and initial conditions to improve efficiency and stability.
   • Penalization: To ensure boundedness of the coefficients during optimization, the authors introduce a truncation map $h$ and a penalization function $H(a)$ that grows to infinity outside a specific ball, ensuring the existence of a minimizer.

Key Theoretical Contributions
The paper establishes a theoretical foundation for applying SGD to MV-SDEs, focusing on convergence and stability:

• Well-Posedness: Under standard Lipschitz and boundedness assumptions on the coefficients, the authors prove the existence and uniqueness of the solution to the MV-SDE and the associated fixed-point problem.
• Regularity: They establish higher-order time-regularity properties for the map $t \mapsto \mathbb{E}[\phi(X_t)]$, which is crucial for the convergence rates of the polynomial approximation.
• Convergence Analysis: The authors prove that the SGD iterates converge almost surely to a stationary point of the objective function $G$.
  • They acknowledge that the problem is non-convex; thus, they rely on existing results for non-convex SGD (citing [6] and [41]) rather than claiming convergence to a global minimum.
  • The proof relies on establishing stability estimates for the underlying Markovian SDE and its tangent processes, as well as the Lipschitz continuity of the gradient of the loss function.
• Error Bounds: An upper bound for the error incurred by solving the problem on the reduced finite-dimensional domain is provided, showing that the error decays as $O(n^{-N})$ where $N$ relates to the smoothness of the solution.

Numerical Results
Extensive numerical experiments validate the method against Monte Carlo IPS benchmarks:

1. Kuramoto-Shinomoto-Sakaguchi Model: The algorithm successfully approximates the solution with high accuracy. The authors observe that the method converges rapidly (often in fewer than 10 iterations for mini-batch sizes of 1000) and that the approximation quality does not deteriorate significantly over longer time horizons.
2. Polynomial Drift Model: The method is tested on a model with super-linear growth coefficients (outside the strict theoretical assumptions). The algorithm converges efficiently for small to moderate time horizons, though some loss of accuracy near the interval boundaries is noted, attributed to the $L^2$ norm used in the loss function.
3. Convolution-Type Model: The authors demonstrate the method's applicability to non-separable coefficients by first projecting the interaction kernel onto a Fourier basis (generalized Hermite polynomials) to fit the separable form. The resulting approximation of the solution's density matches the IPS benchmark closely.

Significance and Claims
The paper positions itself as a "proof of concept" for using SGD as a valid tool for numerically approximating MV-SDEs without the computational burden of interacting particle systems.

• Efficiency: The method avoids the "curse of dimensionality" associated with particle interactions, offering a computational cost that scales linearly with the number of particles in the mini-batch rather than quadratically with the system size.
• Theoretical Foundation: Unlike many machine learning approaches that rely on neural networks as black boxes, this work provides a rigorous analytical framework, including stability estimates and convergence proofs for the specific SGD algorithm applied to MV-SDEs.
• Limitations and Scope: The authors are modest in their claims. They note that the convergence analysis is currently restricted to bounded coefficients, though they argue it can be extended to sub-linear growth. They explicitly state that they prove convergence to a stationary point in a non-convex setting, not necessarily a global minimum. Furthermore, they identify future work regarding Hölder continuous drifts and jump-diffusion frameworks.

In summary, the paper proposes a decoupled, optimization-based approach to MV-SDEs that replaces particle simulation with a gradient-based learning of the law-dependent coefficients, supported by theoretical convergence guarantees and competitive numerical performance.