notebooks/MATH_uniform_concentration_inequality.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "# 時間に一様な集中不等式\n",
                "\n",
                "* [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://arxiv.org/abs/1810.08240)\n",
                "\n",
                "今回は，時間に対して一様な集中不等式について学びます．\n",
                "特に次を考えていきます．\n",
                "\n",
                "---\n",
                "\n",
                "**定義：$(1-\\alpha)$-confidence sequence**\n",
                "\n",
                "$\\alpha \\in (0, 1)$に対して，次を満たすconfidence sets $\\left(\\mathrm{CI}_t\\right)_{t=1}^{\\infty}$を$(1-\\alpha)$-confidence sequenceと呼びます.ここで，confidence sequenceは一般に$\\mathrm{CI}_t=\\left(L_t, U_t\\right) \\subseteq \\mathbb{R}$のような形をしています．\n",
                "\n",
                "* $t$個目の観測の後，知りたい未知の量$\\theta_t$に対して，$\\mathrm{CI}_t$を次のように一様被覆する\n",
                "\n",
                "$$\n",
                "\\mathbb{P}\\left(\\forall t \\geq 1: \\theta_t \\in \\mathrm{CI}_t\\right) \\geq 1-\\alpha\n",
                "$$\n",
                "\n",
                "---\n",
                "\n",
                "今回学ぶ話を使うと例えば次のようなバウンドを出すことができます．\n",
                "\n",
                "---\n",
                "\n",
                "$\\left(X_t\\right)_{t=1}^{\\infty}$ を1-sub-gaussianに従う系列として，その平均$\\mu$を推定したいとします．このとき，推定した$\\mu$について，次の$(1-\\alpha)$-confidence sequenceを得ることができます．\n",
                "\n",
                "$$\n",
                "\\frac{\\sum_{i=1}^t X_i}{t} \\pm 1.7 \\sqrt{\\frac{\\log \\log (2 t)+0.72 \\log (10.4 / \\alpha)}{t}}\n",
                "$$\n",
                "\n",
                "このバウンドは[Law of iterated logarithm](https://en.wikipedia.org/wiki/Law_of_the_iterated_logarithm)で示唆される下界と一致しているので，実質Minimaxです．\n",
                "\n",
                "これはHoeffdingのようなバウンドと何が異なるのでしょうか？\n",
                "Hoeffdingでは固定された$t$についてバウンドを出しており，すべての$t\\in T$について成立させるためには，Union boundを$t$について取る必要があります．\n",
                "つまり，Hoeffdingのバウンドは\n",
                "\n",
                "$$\n",
                "\\frac{\\sum_{i=1}^t X_i}{t} \\pm \\sqrt{\\frac{\\log (T / \\alpha)}{t}}\n",
                "$$\n",
                "\n",
                "のような形になります．これは特に$T\\to \\infty$ではバウンドとして意味がありません．\n",
                "一方で，今回学ぶバウンドはすべての$t$で成立します．\n",
                "\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 準備：$l_0$-sub-$\\psi$条件\n",
                "\n",
                "\n",
                "次を考えましょう\n",
                "\n",
                "* 実数の観測列$\\left(X_t\\right)_{t=1}^{\\infty}$について，$\\mu_t:=t^{-1} \\sum_{i=1}^t \\mathbb{E}_{i-1} X_i$を推定したいとします．\n",
                "* サンプルで期待値：$\\bar{X}_t:=t^{-1} \\sum_{i=1}^t X_i$を推定するとします．\n",
                "* $S_t:=\\sum_{i=1}^t\\left(X_i-\\mathbb{E}_{i-1} X_i\\right)$を期待値と推定値の差とします．\n",
                "* $\\alpha \\in (0, 1)$について，次のuniform upper tail bound $u_\\alpha: \\mathbb{R}_{\\geq 0} \\rightarrow \\mathbb{R}_{\\geq 0}$を構築できるとします：\n",
                "\n",
                "$$\n",
                "\\mathbb{P}\\left(\\exists t \\geq 1: S_t \\geq u_\\alpha\\left(V_t\\right)\\right) \\leq \\alpha\n",
                "$$\n",
                "\n",
                "ここで，$\\left(V_t\\right)_{t=1}^{\\infty}$は$S_t$のズレを測定できるようないい感じの列とします．\n",
                "\n",
                "[PROB_sub_gaussian.ipynb](PROB_sub_gaussian.ipynb)を思い出すと，この$u_\\alpha$を構築するための条件として，subgaussianを考えていました．\n",
                "今回はより一般的な条件として，次を定義します：\n",
                "\n",
                "---\n",
                "\n",
                "**Sub-$\\phi$条件**\n",
                "\n",
                "$\\left(S_t\\right)_{t=0}^{\\infty},\\left(V_t\\right)_{t=0}^{\\infty}$\n",
                "をフィルトレーション$\\left(\\mathcal{F}_t\\right)_{t=0}^{\\infty}$に対しての実数列とします．\n",
                "$S_0=V_0=0$として，$V_t \\geq 0$がすべての$t$で成立するとします．\n",
                "関数$\\psi:\\left[0, \\lambda_{\\max }\\right) \\rightarrow \\mathbb{R}$\n",
                "とスカラー$l_0 \\in[1, \\infty)$について，$(S_t)$は次を満たすときに，$(V_t)$について$l_0$-sub-$\\psi$であるといいます：\n",
                "\n",
                "それぞれの$\\lambda \\in [0, \\lambda_{\\max})$について，\n",
                "次を満たすsupermartingale $\\left(L_t(\\lambda)\\right)_{t=0}^{\\infty} \\text { w.r.t. }\\left(\\mathcal{F}_t\\right)$が存在する：\n",
                "\n",
                "1. $\\mathbb{E} L_0(\\lambda) \\leq l_0$\n",
                "2. $\\exp \\left\\{\\lambda S_t-\\psi(\\lambda) V_t\\right\\} \\leq L_t(\\lambda)$ a.s. for all $t$\n",
                "\n",
                "また，$\\psi$と$l_0$について，$\\mathbb{S}_\\psi^{l_0}$を$l_0$-sub-$\\psi$なペア$\\left(S_t, V_t\\right)$の集合とします：\n",
                "\n",
                "$$\n",
                "\\mathbb{S}_\\psi^{l_0}:=\\left\\{\\left(S_t, V_t\\right):\\left(S_t\\right) \\text { is } l_0 \\text {-sub- } \\psi \\text { with variance process }\\left(V_t\\right)\\right\\}\n",
                "$$\n",
                "\n",
                "---\n",
                "\n",
                "**通常のマルチンゲールの話との比較**\n",
                "\n",
                "よくあるマルチンゲールを扱う場合では，\n",
                "$$\n",
                "\\mathbb{E}_{t-1} \\exp(\\lambda\\left(X_t-\\mathbb{E}_{t-1} X_t\\right)) \\leq \\exp({\\psi(\\lambda) \\sigma_t^2})\n",
                "$$\n",
                "のような形を仮定します．\n",
                "実際，$\\sigma$-subgaussianでは，任意の$\\lambda \\in \\mathbb{R}$について，\n",
                "\n",
                "$$\n",
                "\\mathbb{E}[\\exp (\\lambda X )] \\leq \\exp \\left(\\lambda^2\\sigma^2 / 2\\right)\n",
                "$$\n",
                "\n",
                "であることを条件にしていました．\n",
                "\n",
                "$S_t:=\\sum_{i=1}^t\\left(X_i-\\mathbb{E}_{i-1} X_i\\right)$と$V_t:=\\sum_{i=1}^t \\sigma_i^2$とすれば，$\\exp \\left\\{\\lambda S_t-\\psi(\\lambda) V_t\\right\\}$はそれぞれの$\\lambda$についてsupermartingaleになります．\n",
                "\n",
                "sub-$\\psi$条件では，この指数的な過程を上からsupermartingaleで抑えてるわけですね．\n",
                "\n",
                "---\n",
                "\n",
                "**$\\psi$とキュムラント母関数**\n",
                "\n",
                "* 直感的には$\\exp \\left\\{\\lambda S_t-\\psi(\\lambda) V_t\\right\\}$は$S_t$が$V_t$と比べてどれだけ早く大きくなるか，を測っています．\n",
                "* また，$\\lambda$は$S_t$の挙動の大きさを決めており，$\\psi$はそのときにどれだけ$V_t$を大きくするべきかを決めます．これは$\\psi$によって分布の裾がある程度決められているのと同等なので，$\\psi$はキュムラント母関数のようなものと考えることもできます．\n",
                "\n",
                "代表的な$\\psi$として，一番簡単なのは$0 \\leq \\lambda<\\infty$について\n",
                "\n",
                "$$\\psi_N(\\lambda):=\\lambda^2 / 2$$\n",
                "\n",
                "でしょう．これは標準ガウス分布のキュムラント母関数です．\n",
                "他にもいくつかあります（論文の６ページ参照）．\n",
                "\n",
                "<!-- \n",
                "例えば$X_t$をi.i.d.な期待値ゼロの確率変数とします．このとき，キュムラント母関数$\\psi(\\lambda):=\\log \\mathbb{E}\\exp(\\lambda X_1)$を考えましょう．$V_t=t$とすれば，\n",
                "\n",
                "$$\n",
                "L_t(\\lambda) := \\exp(\\lambda S_t - \\psi(\\lambda) V_t)\n",
                "$$ -->\n",
                "\n",
                "---\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "\n",
                "続いて，この$\\psi$を使って一様なboundaryを形成していきます．\n",
                "まずはCramer-Chernoffのバウンドを思い出してみましょう（TODO:）．\n",
                "\n",
                "$(X_t)$をi.i.d.な期待値ゼロの確率変数として，そのキュムラント母関数が$\\log \\mathbb{E}\\exp(\\lambda X_t)\\leq \\psi (\\lambda)$としてバウンドされているとします．\n",
                "このときCramer-Chernoffのバウンドを使うと，$S_t=\\sum_{i=1}^t X_i$について，\n",
                "\n",
                "$$\n",
                "\\mathbb{P}\\left(S_t \\geq x\\right) \\leq e^{-t \\psi^*(x / t)}\n",
                "$$\n",
                "\n",
                "であることが言えます．ここで$\\psi^*$は$\\psi$のルジャンドル変換です．変形して，\n",
                "\n",
                "$$z_\\alpha(t):=t \\psi^{\\star-1}\\left(t^{-1} \\log \\alpha^{-1}\\right)$$\n",
                "\n",
                "を考えれば，任意の固定された$t$と$\\alpha \\in (0, 1)$について，\n",
                "\n",
                "$$\n",
                "\\mathbb{P}\\left(S_t \\geq z_\\alpha(t)\\right) \\leq \\alpha\n",
                "$$\n",
                "\n",
                "であることと同じです．\n",
                "つまり，$z_\\alpha$は任意の固定された$t$について，高確率のバウンドを与えていることになります．\n",
                "これを固定された$t$ではなくて，一様に拡張していきます．\n",
                "そこで，次を考えます：\n",
                "\n",
                "---\n",
                "\n",
                "**定義**\n",
                "\n",
                "$\\psi: [0, \\lambda_{\\max}) \\to \\mathbb{R}$と$l_0 \\geq 1$について，関数$u: \\mathbb{R} \\to \\mathbb{R}$は次を満たすときに，交差確率$\\alpha$の$l_0$-sub-$\\psi$なboundaryであるといいます：\n",
                "\n",
                "$$\n",
                "\\sup _{\\left(S_t, V_t\\right) \\in \\mathbb{S}_\\psi^{l_0}} \\mathbb{P}\\left(\\exists t \\geq 1: S_t \\geq u\\left(V_t\\right)\\right) \\leq \\alpha .\n",
                "$$\n",
                "\n",
                "---\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": []
        }
    ],
    "metadata": {
        "language_info": {
            "name": "python"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}