タラグランドの濃度不平等

数学の確率論の分野において、タラグランの集中不等式は積確率空間に対する等周型不等式である。^{[1] [2]これはフランスの数学者}ミシェル・タラグランによって初めて証明された。^{[3]この不等式は}測度の集中現象の現れの一つである。^[2]

大まかに言えば、積空間のあるサブセットにある確率（例えば、ベクトルで記述される状態の集合の1つにある確率）と、そのサブスペースの近傍から少なくとも一定の距離離れたところにある確率の積は、指数係数 によって上限が定められます。積空間内の領域のより大きな近傍の外にある可能性は急速に低くなり、一般的には独立変数で記述される状態の確率密度が非常に集中していることを意味します。この不等式は、分布全体の限られたサブセットをサンプリングし、サンプルの平均から離れた値を見つける確率を制限できるようにすることで、最適化プロトコルを合理化するために使用できます。^[4]${\displaystyle t}$${\displaystyle e^{-t^{2}/4}}$

不等式は、積確率測度が備わった積空間であり、 この空間の部分集合である場合、任意の${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}\times \cdots \times \Omega _{n}}$${\displaystyle A}$${\displaystyle t\geq 0}$

${\displaystyle \Pr[A]\cdot \Pr \left[{A_{t}^{c}}\right]\leq e^{-t^{2}/4}\,,}$

ここで、これは次のように定義される。 ${\displaystyle {A_{t}^{c}}}$${\displaystyle A_{t}}$

${\displaystyle A_{t}=\{x\in \Omega \colon ~\rho (A,x)\leq t\}}$

そしてタラグランドの凸距離は次のように定義される。 ${\displaystyle \rho}$

${\displaystyle \rho (A,x)=\max _{\alpha ,\|\alpha \|_{2}\leq 1}\ \min _{y\in A}\ \sum _{i\colon ~x_{i}\neq y_{i}}\alpha _{i}}$

ここで、はそれぞれ要素を持つ -次元ベクトルで あり、は -ノルムである。つまり、 ${\displaystyle \alpha \in \mathbf {R} ^{n}}$${\displaystyle x,y\in \Omega }$${\displaystyle n}$${\displaystyle \alpha_{i},x_{i},y_{i}}$${\displaystyle \|\cdot \|_{2}}$${\displaystyle \ell^{2}}$

${\displaystyle \|\alpha \|_{2}=\left(\sum _{i}\alpha _{i}^{2}\right)^{1/2}}$