Notes on: Gorham, J., & Mackey, L. (2015): Measuring Sample Quality With Stein's Method

Table of Contents

Overview

  1. Motivates Steins method
  2. Steins method
    • gorham15_measur_sampl_qualit_with_stein_method_bed561b338628a088ae69301d4bba9fd83a70bd2.png, the function selected in the maximization process of the Stein Discrepancy gives us a method, can be intuitively thought of as being a feature selection function which finds the features producing the most discrepancy between our approx. density gorham15_measur_sampl_qualit_with_stein_method_ab437e1f9b3376761b155efe111c9860607c4b86.png and the actual density gorham15_measur_sampl_qualit_with_stein_method_fefe9e556d399665a26a37824ec578cbffb0cabe.png
  3. Classical Stein Set and Discrepancy
    • Methods for constructing a Stein operator for sufficiently smooth functions
    • Proves upper bound for classical Stein Discrepancy
  4. Methods for computing Stein Discrepancies
    • Graph Stein set
    • Spanner Stein discrepancies using spanner graphs
    • Linear programs used to solve the finite-dimensional subproblems of maximizing the function in each of the components to obtain the Stein discrepancy
  5. Experiments

Notation

  • Often refer to a generic norm gorham15_measur_sampl_qualit_with_stein_method_019c17c1114318b29385b2ec79601e8f5caa6dcf.png on gorham15_measur_sampl_qualit_with_stein_method_de0b57391ed8b0d9becf399c343de2bf83467ce1.png with associated dual norms gorham15_measur_sampl_qualit_with_stein_method_9a3ce321748fa9b9c6e164f328e9ca4b84462f75.png for vectors gorham15_measur_sampl_qualit_with_stein_method_df353e38f1a6ec7f81abc7f40f604c84402ca1c3.png
  • gorham15_measur_sampl_qualit_with_stein_method_fd9fe5003b5dfa76cd57dccf213781e787a553d0.png is target distribution with open convex support gorham15_measur_sampl_qualit_with_stein_method_d7a4b051cf533eb41125357d5039ccb5b24758e1.png
  • gorham15_measur_sampl_qualit_with_stein_method_fefe9e556d399665a26a37824ec578cbffb0cabe.png continuously differentiable density
  • probability mass function gorham15_measur_sampl_qualit_with_stein_method_ab437e1f9b3376761b155efe111c9860607c4b86.png induces a discrete distribution gorham15_measur_sampl_qualit_with_stein_method_88c6e1c008509ea8de35316286b272c4107bed01.png and approx.

    gorham15_measur_sampl_qualit_with_stein_method_34055b97536485475a2aa1fb9956b55a1344145c.png

    for any target expHectation gorham15_measur_sampl_qualit_with_stein_method_998bfc9e466de7bd1827e0aa5bb9fcf65a742752.png.

  • weighted sample of distinct sample points gorham15_measur_sampl_qualit_with_stein_method_354f6e3dc0a22d5b1b7c36e09c7ebe3dd90d8df4.png with weights gorham15_measur_sampl_qualit_with_stein_method_ed9682476da1291c8204c3e063ce5dc991f1aaab.png encoded in the probability mass function gorham15_measur_sampl_qualit_with_stein_method_ab437e1f9b3376761b155efe111c9860607c4b86.png
  • gorham15_measur_sampl_qualit_with_stein_method_84330df7405a53721417a49b78e298fafe4a4dc1.png real-valued operator
  • gorham15_measur_sampl_qualit_with_stein_method_968aae4e9a48f70992d7a484a93d5dda62f8b266.png set of gorham15_measur_sampl_qualit_with_stein_method_de0b57391ed8b0d9becf399c343de2bf83467ce1.png valued functions
  • gorham15_measur_sampl_qualit_with_stein_method_6d34f4723ff83ab5bacd10810cc0f0d125b4b16b.png
  • gorham15_measur_sampl_qualit_with_stein_method_360b460cbcb52827b3c2a97a9f362233e0cb4e01.png

Stuff

Construct quality of measure with following properties:

  1. detects when a sequence of samples is converging to the target
  2. detects when a sequence of sample is not converging to the target
  3. computationally feasible

First consider expected deviation between sample and target expectations over a class of real-valued test functions gorham15_measur_sampl_qualit_with_stein_method_04016c2db0a754f30f8b3b0b87bb4fa9ea1528a8.png:

gorham15_measur_sampl_qualit_with_stein_method_35989f134d72654ba092cf954e913bb61a6f9600.png

  • If class of test functions is sufficiently large => gorham15_measur_sampl_qualit_with_stein_method_770b2059509476628fb711f7ad41cff15e1ea709.png implies that the seuqence of sample measures gorham15_measur_sampl_qualit_with_stein_method_174a681a01b2c57242f21a9c4fe39d929f37d040.png converges weakly to gorham15_measur_sampl_qualit_with_stein_method_fd9fe5003b5dfa76cd57dccf213781e787a553d0.png

Varying class of test functions gorham15_measur_sampl_qualit_with_stein_method_04016c2db0a754f30f8b3b0b87bb4fa9ea1528a8.png of IPM we recover many well-known probability metrics:

Stein's method

  1. Identify a real-valued operator gorham15_measur_sampl_qualit_with_stein_method_84330df7405a53721417a49b78e298fafe4a4dc1.png acting on a set gorham15_measur_sampl_qualit_with_stein_method_968aae4e9a48f70992d7a484a93d5dda62f8b266.png of gorham15_measur_sampl_qualit_with_stein_method_de0b57391ed8b0d9becf399c343de2bf83467ce1.png valued functions of gorham15_measur_sampl_qualit_with_stein_method_76879b948635123ecd29d7cd65a1060145ba040e.png for which

    gorham15_measur_sampl_qualit_with_stein_method_7eb46204ae008a7c569e00f220169d212a320689.png

    Together, gorham15_measur_sampl_qualit_with_stein_method_84330df7405a53721417a49b78e298fafe4a4dc1.png and gorham15_measur_sampl_qualit_with_stein_method_968aae4e9a48f70992d7a484a93d5dda62f8b266.png define the Stein discrepancy,

    gorham15_measur_sampl_qualit_with_stein_method_f422d398857f25b4705d925f567a009c137fd3fe.png

    an IPM quality measure with no explicit integration under gorham15_measur_sampl_qualit_with_stein_method_fd9fe5003b5dfa76cd57dccf213781e787a553d0.png.

  2. Lower bound the Stein discrepancy by a familiar convergence-determining IPM gorham15_measur_sampl_qualit_with_stein_method_833adac66caba2f80b4954ff8202b81b85008076.png
    • Can be perforemd once, in advance, for alrge classes of target distributions and ensures that, for any sequence of probability measures gorham15_measur_sampl_qualit_with_stein_method_28c4f707fe0db38c27adedce03d3cc4ebffd5f4e.png, gorham15_measur_sampl_qualit_with_stein_method_63cb0103fc4fd39f168e3c100f9568131a5dac27.png converges to zero if and only if gorham15_measur_sampl_qualit_with_stein_method_d9fce8dd47b4b5dca018baa5426fb60ef1b4fa30.png
  3. Upper bound the Stein discrepancy by any means necessary to demonstrate convergence to zero under suitable conditions.

Challenges

  • Constructing a Stein operator gorham15_measur_sampl_qualit_with_stein_method_84330df7405a53721417a49b78e298fafe4a4dc1.png which produce mean-zero functions under gorham15_measur_sampl_qualit_with_stein_method_fd9fe5003b5dfa76cd57dccf213781e787a553d0.png

Identifying a Stein operator

If we let:

  • gorham15_measur_sampl_qualit_with_stein_method_48ac57a7488875b64086ca544e81362170855fbd.png denote the boundary of gorham15_measur_sampl_qualit_with_stein_method_76879b948635123ecd29d7cd65a1060145ba040e.png (an empty set when gorham15_measur_sampl_qualit_with_stein_method_5d59e3707e2ff34519b6322d77f049b0a1612c60.png
  • gorham15_measur_sampl_qualit_with_stein_method_8790ae0174127c257c40bac96d778d9139bc5bcd.png represent the outward unit normal vector to the boundary at gorham15_measur_sampl_qualit_with_stein_method_3c314f80373742988ad542a6d4ce66a111b17847.png

then we may define the classical Stein set

gorham15_measur_sampl_qualit_with_stein_method_89566ec80b132a0429468b594c5c19fe7a244a1d.png

of sufficiently smooth functions satisfying a Neumann-type boundary condition (referring to the inner product of the function gorham15_measur_sampl_qualit_with_stein_method_ae4a11ca5205e001bcbb42f1c4723700979fd5fc.png and the outward unit vector gorham15_measur_sampl_qualit_with_stein_method_8790ae0174127c257c40bac96d778d9139bc5bcd.png).

From this they get the following proposition

If gorham15_measur_sampl_qualit_with_stein_method_c72567188e738e3620b87e4b3ea91d1f808c9710.png, then gorham15_measur_sampl_qualit_with_stein_method_4d1cc5765f62834372c3724a9c558eb025d21193.png for all gorham15_measur_sampl_qualit_with_stein_method_35f011b00a15ed4a7123579fe15edb2193b59956.png.

Together, gorham15_measur_sampl_qualit_with_stein_method_ee8bbb961127b2009d062de9830880105fdf83ad.png and gorham15_measur_sampl_qualit_with_stein_method_16d67c4ea49b0384276debc9f5fc88996ed720e5.png form the classical Stein discrepancy gorham15_measur_sampl_qualit_with_stein_method_f8826478be1855887f7d5e7ae78a68382b06294c.png, which is the main study of the paper.