{
  "id": "enwiki-001359031055",
  "slug": "stein-discrepancy",
  "title": "Stein discrepancy",
  "qid": "",
  "lead": "A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science.",
  "body": "A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science. (1.1) \\quad d_{\\mathcal{M}}(P , Q) := \\sup_{m \\in \\mathcal{M}} |\\mathbb{E}_{X \\sim P}[m(X)] - \\mathbb{E}_{Y \\sim Q}[m(Y)]| , where for the purposes of exposition we assume that the expectations exist, and that the set \\mathcal{M} is sufficiently rich that (1.1) is indeed a metric on the set of probability distributions on \\mathcal{X} , i.e. d_{\\mathcal{M}}(P,Q) = 0 if and only if P=Q . The choice of the set \\mathcal{M} determines the topological properties of (1.1). However, for practical purposes the evaluation of (1.1) requires access to both P and Q , often rendering direct computation of (1.1) impractical. Stein's method is a theoretical tool that can be used to bound (1.1). Specifically, we suppose that we can identify an operator \\mathcal{A}_{P} and a set \\mathcal{F}_{P} of real-valued functions in the domain of \\mathcal{A}_{P} , both of which may be P -dependent, such that for each m \\in \\mathcal{M} there exists a solution f_m \\in \\mathcal{F}_{P} to the Stein equation (1.2) \\quad m(x) - \\mathbb{E}_{X \\sim P}[m(X)] = \\mathcal{A}_{P} f_m(x) . The operator \\mathcal{A}_{P} is termed a Stein operator and the set \\mathcal{F}_{P} is called a Stein set. Substituting (1.2) into (1.1), we obtain an upper bound d_{\\mathcal{M}}(P , Q) = \\sup_{m \\in \\mathcal{M}} |\\mathbb{E}_{Y \\sim Q}[m(Y)] - \\mathbb{E}_{X \\sim P}[m(X)]| = \\sup_{m \\in \\mathcal{M}} |\\mathbb{E}_{Y \\sim Q}[ \\mathcal{A}_{P} f_m(Y) ]| \\leq \\sup_{f \\in \\mathcal{F}_{P}} |\\mathbb{E}_{Y \\sim Q}[\\mathcal{A}_{P} f(Y)]| . This resulting bound D_P(Q) := \\sup_{f \\in \\mathcal{F}_P} |\\mathbb{E}_{Y \\sim Q}[\\mathcal{A}_P f(Y)]| is called a Stein discrepancy. In contrast to the original integral probability metric d_{\\mathcal{M}}(P , Q) , it may be possible to analyse or compute D_{P}(Q) using expectations only with respect to the distribution Q . For a probability distribution P with positive and differentiable density function p on a convex set \\mathcal{X} \\subseteq \\mathbb{R}^d , whose boundary is denoted \\partial \\mathcal{X} , the combination of the Langevin–Stein operator \\mathcal{A}_{P} f = \\nabla \\cdot f + f \\cdot \\nabla \\log p and the classical Stein set \\mathcal{F}_P = \\left\\{ f : \\mathcal{X} \\rightarrow \\mathbb{R}^d \\,\\Biggl\\vert\\, \\sup_{x \\neq y} \\max \\left( \\|f(x)\\| , \\|\\nabla f(x) \\|, \\frac{\\|\\nabla f(x) - \\nabla f(y) \\|}{\\|x-y\\|} \\right) \\leq 1 , \\; \\langle f(x) , n(x) \\rangle = 0 \\; \\forall x \\in \\partial \\mathcal{X} \\right\\} yields the classical Stein discrepancy. Here \\|\\cdot\\| denotes the Euclidean norm and \\langle \\cdot , \\cdot \\rangle the Euclidean inner product. Here \\| M \\| = \\textstyle \\sup_{v \\in \\mathbb{R}^d, \\|v\\| = 1} \\|Mv\\| is the associated operator norm for matrices M \\in \\R^{d \\times d} , and n(x) denotes the outward unit normal to \\partial \\mathcal{X} at location x \\in \\partial \\mathcal{X} . If \\mathcal{X} = \\R^d then we interpret \\partial \\mathcal{X} = \\emptyset . In the univariate case d=1 , the classical Stein discrepancy can be computed exactly by solving a quadratically constrained quadratic program. The first known computable Stein discrepancies were the graph Stein discrepancies (GSDs). Given a discrete distribution Q = \\textstyle \\sum_{i=1}^n w_i \\delta(x_i) , one can define the graph G with vertex set V = \\{x_1, \\dots, x_n\\} and edge set E \\subseteq V \\times V . From this graph, one can define the graph Stein set as \\begin{align} \\mathcal{F}_P = \\Big\\{ f : \\mathcal{X} \\rightarrow \\mathbb{R}^d & \\,\\Bigl\\vert\\, \\max \\left(\\|f(v)\\|_\\infty, \\|\\nabla f(v)\\|_\\infty, {\\textstyle\\frac{\\|f(x) - f(y)\\|_\\infty}{\\|x - y\\|_1}}, {\\textstyle \\frac{\\|\\nabla f(x) - \\nabla f(y)\\|_\\infty}{\\|x - y\\|_1}}\\right) \\le 1, \\\\[8pt] & {\\textstyle\\frac{\\|f(x) - f(y) - {\\nabla (x)}{(x - y)}\\|_\\infty}{\\frac{1}{2}\\|x - y\\|_1^2} \\leq 1}, {\\textstyle\\frac{\\|f(x) - f(y) -{\\nabla f(y)}{(x - y)}\\|_\\infty}{\\frac{1}{2}\\|x - y\\|_1^2} \\leq 1}, \\; \\forall v \\in \\operatorname{supp}(Q_n), (x,y)\\in E \\Big\\}. \\end{align} The combination of the Langevin–Stein operator and the graph Stein set is called the graph Stein discrepancy (GSD). The GSD is actually the solution of a finite-dimensional linear program, with the size of E as low as linear in n , meaning that the GSD can be efficiently computed. The supremum arising in the definition of Stein discrepancy can be evaluated in closed form using a particular choice of Stein set. Indeed, let \\mathcal{F}_P = \\{f \\in H(K) : \\|f\\|_{H(K)} \\leq 1\\} be the unit ball in a (possibly vector-valued) reproducing kernel Hilbert space H(K) with reproducing kernel K , whose elements are in the domain of the Stein operator \\mathcal{A}_P . Suppose that For each fixed x \\in \\mathcal{X} , the map f \\mapsto \\mathcal{A}_P[f](x) is a continuous linear functional on \\mathcal{F}_P . \\mathbb{E}_{X \\sim Q}[ \\mathcal{A}_P \\mathcal{A}_P' K(X,X) ] . where the Stein operator \\mathcal{A}_P acts on the first argument of K(\\cdot,\\cdot) and \\mathcal{A}_P' acts on the second argument. Then it can be shown that D_P(Q) = \\sqrt{ \\mathbb{E}_{X,X' \\sim Q} [ \\mathcal{A}_P \\mathcal{A}_P' K(X,X') ] } , where the random variables X and X' in the expectation are independent. In particular, if Q = \\sum_{i=1}^n w_i \\delta(x_i) is a discrete distribution on \\mathcal{X} , then the Stein discrepancy takes the closed form D_P(Q) = \\sqrt{ \\sum_{i=1}^n \\sum_{j=1}^n w_i w_j \\mathcal{A}_P \\mathcal{A}_P' K(x_i,x_j) }. A Stein discrepancy constructed in this manner is called a kernel Stein discrepancy and the construction is closely connected to the theory of kernel embedding of probability distributions. Let k : \\mathcal{X} \\times \\mathcal{X} \\rightarrow \\mathbb{R} be a reproducing kernel. For a probability distribution P with positive and differentiable density function p on \\mathcal{X} = \\R^d , the combination of the Langevin—Stein operator \\mathcal{A}_{P} f = \\nabla \\cdot f + f \\cdot \\nabla \\log p and the Stein set \\mathcal{F}_P = \\left\\{f \\in H(k) \\times \\dots \\times H(k) : \\sum_{i=1}^d \\|f_i\\|_{H(k)}^2 \\leq 1\\right\\}, associated to the matrix-valued reproducing kernel K(x,x') = k(x,x') I_{d \\times d} , yields a kernel Stein discrepancy with \\mathcal{A}_P \\mathcal{A}_P' K(x,x') = \\nabla_x \\cdot \\nabla_{x'} k(x,x') + \\nabla_x k(x,x') \\cdot \\nabla_{x'} \\log p(x') +\\nabla_{x'} k(x,x') \\cdot \\nabla_x \\log p(x) + k(x,x') \\nabla_x \\log p(x) \\cdot \\nabla_{x'} \\log p(x') where \\nabla_x (resp. \\nabla_{x'} ) indicated the gradient with respect to the argument indexed by x (resp. x' ). Concretely, if we take the inverse multi-quadric kernel k(x,x') = (1 + (x-x')^\\top \\Sigma^{-1} (x-x') )^{-\\beta} with parameters \\beta > 0 and \\Sigma \\in \\mathbb{R}^{d \\times d} a symmetric positive definite matrix, and if we denote u(x) = \\nabla \\log p(x) , then we have (2.1) \\quad \\mathcal{A}_P \\mathcal{A}_P' K(x,x') = - \\frac{4 \\beta (\\beta + 1) (x-x')^\\top \\Sigma^{-2} (x-x')}{ \\left(1 + (x-x')^\\top \\Sigma^{-1} (x-x') \\right)^{\\beta + 2} } + 2 \\beta \\left[ \\frac{ \\text{tr}(\\Sigma^{-1}) + [u(x) - u(x')]^\\top \\Sigma^{-1} (x-x') }{ \\left(1 + (x-x')^\\top \\Sigma^{-1} (x-x') \\right)^{1+\\beta} } \\right] + \\frac{ u(x)^\\top u(x') }{ \\left(1 + (x-x')^\\top \\Sigma^{-1} (x-x') \\right)^{\\beta} } . Diffusion Stein discrepancies generalize the Langevin Stein operator \\mathcal{A}_{P} f = \\nabla \\cdot f + f \\cdot \\nabla \\log p = \\textstyle\\frac{1}{p}\\nabla \\cdot (f p) to a class of diffusion Stein operators \\mathcal{A}_{P} f = \\textstyle\\frac{1}{p}\\nabla \\cdot (m f p) , each representing an Itô diffusion that has P as its stationary distribution. Here, m is a matrix-valued function determined by the infinitesimal generator of the diffusion. p(x) = \\textstyle \\frac{1}{Z} \\tilde{p}(x) , where \\tilde{p}(x) and its derivative can be numerically evaluated but whose normalisation constant Z is not easily computed or approximated. Considering (2.1), we observe that the dependence of \\mathcal{A}_P \\mathcal{A}_P K(x,x') on P occurs only through the term u(x) = \\nabla \\log p(x) = \\nabla \\log \\left( \\frac{\\tilde{p}(x)}{Z} \\right) = \\nabla \\log \\tilde{p}(x) - \\nabla \\log Z = \\nabla \\log \\tilde{p}(x) which does not depend on the normalisation constant Z . A basic requirement of Stein discrepancy is that it is a statistical divergence, meaning that D_P(Q) \\geq 0 and D_P(Q) = 0 if and only if Q=P . This property can be shown to hold for classical Stein discrepancy and kernel Stein discrepancy a provided that appropriate regularity conditions hold. Given a probability distribution P defined on a measurable space \\mathcal{X} , the quantization task is to select a small number of states x_1,\\dots,x_n \\in \\mathcal{X} such that the associated discrete distribution Q^n = \\frac{1}{n} \\sum_{i=1}^n \\delta(x_i) is an accurate approximation of P in a sense to be specified. Stein points are the result of performing optimal quantisation via minimisation of Stein discrepancy: (3.1) \\quad \\underset{x_1,\\dots,x_n \\in \\mathcal{X}}{\\operatorname{arg\\,min}} \\; D_{P}\\left( \\frac{1}{n} \\sum_{i=1}^n \\delta(x_i) \\right) Under appropriate regularity conditions, it can be shown that D_P(Q^n) \\rightarrow 0 as n \\rightarrow \\infty . Thus, if the Stein discrepancy enjoys convergence control, it follows that Q^n converges to P . Extensions of this result, to allow for imperfect numerical optimisation, have also been derived. Sophisticated optimisation algorithms have been designed to perform efficient quantisation based on Stein discrepancy, including gradient flow algorithms that aim to minimise kernel Stein discrepancy over an appropriate space of probability measures. If one is allowed to consider weighted combinations of point masses, then more accurate approximation is possible compared to (3.1). For simplicity of exposition, suppose we are given a set of states \\{x_i\\}_{i=1}^n \\subset \\mathcal{X} . Then the optimal weighted combination of the point masses \\delta(x_i) , i.e. Q_n := \\sum_{i=1}^n w_i^* \\delta(x_i), \\qquad w^* \\in \\underset{w_1 + \\cdots + w_n = 1}{\\operatorname{arg\\,min}} \\; D_P\\left( \\sum_{i=1}^n w_i \\delta(x_i) \\right), which minimise Stein discrepancy can be obtained in closed form when a kernel Stein discrepancy is used. Some authors consider imposing, in addition, a non-negativity constraint on the weights, i.e. w_i \\geq 0 . However, in both cases the computation required to compute the optimal weights w^* can involve solving linear systems of equations that are numerically ill-conditioned. Interestingly, it has been shown that greedy approximation of Q_n using an un-weighted combination of m \\ll n states can reduce this computational requirement. In particular, the greedy Stein thinning algorithm Q_{n,m} := \\frac{1}{m} \\sum_{i=1}^m \\delta(x_{\\pi(i)}), \\qquad \\pi(m) \\in \\underset{j=1,\\dots,n}{\\operatorname{arg\\,min}} \\; D_P\\left( \\frac{1}{m} \\sum_{i=1}^{m-1} \\delta(x_{\\pi(i)}) + \\frac{1}{m} \\delta(x_j) \\right) has been shown to satisfy an error bound D_P(Q_{n,m}) = D_P(Q_n) + O\\left(\\sqrt{\\frac{\\log m}{m}} \\right). Non-myopic and mini-batch generalisations of the greedy algorithm have been demonstrated to yield further improvement in approximation quality relative to computational cost. Stein discrepancy has been proposed as a tool to fit parametric statistical models to data. Given a dataset \\{x_i\\}_{i=1}^n \\subset \\mathcal{X} , consider the associated discrete distribution Q^n = \\textstyle \\frac{1}{n}\\sum_{i=1}^n \\delta(x_i) . For a given parametric collection \\{P_\\theta\\}_{\\theta \\in \\Theta} of probability distributions on \\mathcal{X} , one can estimate a value of the parameter \\theta which is compatible with the dataset using a minimum Stein discrepancy estimator \\underset{\\theta \\in \\Theta}{\\operatorname{arg\\,min}} \\; D_{P_\\theta}(Q^n). The approach is closely related to the framework of minimum distance estimation, with the role of the \"distance\" being played by the Stein discrepancy. Alternatively, a generalised Bayesian approach to estimation of the parameter \\theta can be considered where, given a prior probability distribution with density function \\pi(\\theta) , \\theta \\in \\Theta , (with respect to an appropriate reference measure on \\Theta ), one constructs a generalised posterior with probability density function \\pi^n(\\theta) \\propto \\pi(\\theta) \\exp\\left( - \\gamma D_{P_\\theta}(Q^n)^2 \\right) , for some \\gamma > 0 to be specified or determined.",
  "categories": [
    "20203235",
    "23603337",
    "25924156",
    "26220375"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1359031055",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1781274412.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001359031055",
    "type": "webpage",
    "title": "Stein discrepancy",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/stein-discrepancy",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001359031055",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1359031055",
    "note": "Immutable snapshot enwiki-001359031055"
  }
}