notebooks/BANDIT_Kiefer_Wolfowitz.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kiefer-Wolfowitzの定理\n",
    "\n",
    "参考：\n",
    "* [Bandit Algorithms](https://tor-lattimore.com/downloads/book/book.pdf)のChapter 20と21\n",
    "\n",
    "Kiefer-Wolfowitzの定理は線形バンディットでよく出てきます（統計の分野でもよく出てくるかも）。\n",
    "\n",
    "表記：\n",
    "\n",
    "* $\\eta_1, \\ldots, \\eta_n$：独立した$1$-subgaussianな確率変数\n",
    "* $a_1, \\ldots, a_n \\in \\mathbb{R}^d$：$\\mathbb{R}^d$を張る系列\n",
    "* $\\theta_*\\in \\mathbb{R}^d$：真のパラメータ\n",
    "* $X_1, \\ldots, X_n$：$X_t=\\left\\langle\\theta_*, a_t\\right\\rangle+\\eta_t$\n",
    "* $\\hat{\\theta}$：最小二乗法の推定値 $\\hat{\\theta}=V^{-1} \\sum_{t=1}^n a_t X_t$ with $V=\\sum_{t=1}^n a_t a_t^{\\top}$\n",
    "\n",
    "ここで、適当な$a\\in \\mathbb{R}^d$について\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\left\\langle\\hat{\\theta}-\\theta_*, a\\right\\rangle & =\\left\\langle a, V^{-1} \\sum_{t=1}^n  a_tX_t-\\theta_*\\right\\rangle=\n",
    "\\left\\langle a, V^{-1} \\sum_{t=1}^n a_t\\left(\\left\\langle\\theta_*, a_t\\right\\rangle+\\eta_t\\right)-\\theta_*\\right\\rangle \\\\\n",
    "& =\\left\\langle a, V^{-1} \\sum_{t=1}^n a_t \\eta_t\\right\\rangle\n",
    "=\\sum_{t=1}^n\\left\\langle a, V_t^{-1} a_t\\right\\rangle \\eta_t\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "であり、$\\eta$は$1$-subgaussianなので、簡単な集中不等式から\n",
    "\n",
    "$$\n",
    "\\mathbb{P}\\left(\\left\\langle\\hat{\\theta}_t-\\theta_*, a\\right\\rangle \\geq \\sqrt{2\\|a\\|_{V^{-1}}^2 \\log \\left(\\frac{1}{\\delta}\\right)}\\right) \\leq \\delta\n",
    "$$\n",
    "\n",
    "が成り立ちます。\n",
    "ここから、$\\|a\\|_{V^{-1}}^2$が小さいほうが推定値の精度が高くなることがわかります。\n",
    "\n",
    "$\\|a\\|_{V^{-1}}^2$が小さくなるようにデータセットの重み付けをする問題はG-optimal design問題と呼ばれます（[CVX_minimum_volume_ellipsoids.ipynb](CVX_minimum_volume_ellipsoids.ipynb)参照）。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# G-optimal design問題\n",
    "\n",
    "$\\pi: \\mathcal{A} \\rightarrow[0,1]$とし、$\\sum_{a \\in \\mathcal{A}} \\pi(a)=1$なるデータセットの重みとします。\n",
    "また、\n",
    "\n",
    "$$\n",
    "V(\\pi)=\\sum_{a \\in \\mathcal{A}} \\pi(a) a a^{\\top}, \\quad g(\\pi)=\\max _{a \\in \\mathcal{A}}\\|a\\|_{V(\\pi)^{-1}}^2\n",
    "$$\n",
    "\n",
    "とすれば、$g(\\pi)$を小さくすることで最小二乗法の推定値の精度を上げることができます。\n",
    "\n",
    "$\\varepsilon$以下の精度を達成するために、特に全ての行動$a \\in \\operatorname{Supp}(\\pi)$をそれぞれ\n",
    "\n",
    "$$\n",
    "n_a=\\left\\lceil\\frac{2 \\pi(a) g(\\pi)}{\\varepsilon^2} \\log \\left(\\frac{1}{\\delta}\\right)\\right\\rceil\n",
    "$$\n",
    "\n",
    "回ずつ選択することを考えます。このとき、\n",
    "\n",
    "$$\n",
    "V=\\sum_{a \\in \\operatorname{Supp}(\\pi)} n_a a a^{\\top} \\succeq \\frac{2 g(\\pi)}{\\varepsilon^2} \\log \\left(\\frac{1}{\\delta}\\right) V(\\pi)\n",
    "$$\n",
    "\n",
    "であり、\n",
    "$$\n",
    "\\left\\langle\\hat{\\theta}-\\theta_*, a\\right\\rangle \\leq \\sqrt{2\\|a\\|_{V^{-1}}^2 \\log \\left(\\frac{1}{\\delta}\\right)} \\leq \\varepsilon\n",
    "$$\n",
    "\n",
    "が確率$1-\\delta$以上で保証できます。\n",
    "よって、$\\varepsilon$以下の精度を達成するには全部で\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "n=\\sum_{a \\in \\operatorname{Supp}(\\pi)} n_a & =\\sum_{a \\in \\operatorname{Supp}(\\pi)}\\left\\lceil\\frac{2 \\pi(a) g(\\pi)}{\\varepsilon^2} \\log \\left(\\frac{1}{\\delta}\\right)\\right\\rceil \\\\\n",
    "& \\leq|\\operatorname{Supp}(\\pi)|+\\frac{2 g(\\pi)}{\\varepsilon^2} \\log \\left(\\frac{1}{\\delta}\\right) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "だけサンプルが必要になります。つまり、$|\\operatorname{Supp}(\\pi)|$と$g(\\pi)$が小さければサンプルの数を減らせるわけですね。この$|\\operatorname{Supp}(\\pi)|$はCore setと呼ばれ、Kiefer-Wolfowitzの定理はCore setのサイズと$g(\\pi)$についてのバウンドを与えてくれます。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kiefer-Wolfowitzの定理\n",
    "\n",
    "$\\mathcal{A}\\subset \\mathbb{R}^d$をコンパクトかつ$\\operatorname{span}(\\mathcal{A})=\\mathbb{R}^d$とする。\n",
    "このとき、次は同値である：\n",
    "\n",
    "1. $\\pi^*$は$g$のMinimizer\n",
    "2. $\\pi^*$は$f(\\pi)=\\log\\det V(\\pi)$のMaximizer\n",
    "3. $g(\\pi^*)=d$\n",
    "\n",
    "さらに、$\\left|\\operatorname{Supp}\\left(\\pi^*\\right)\\right| \\leq d(d+1) / 2$を満たすようなminimizer $\\pi^*$が存在する。\n",
    "\n",
    "１はG-optimal design、２はD-optimal designと呼ばれます。よって、G-optimal designとD-optimal designは同じです。\n",
    "証明してみましょう。まず有限集合について証明します。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 有限集合でのKiefer-Wolfowitz\n",
    "\n",
    "まず、$f$は凹関数かつ\n",
    "$$\n",
    "(\\nabla f(\\pi))_a=\\|a\\|_{V(\\pi)^{-1}}^2\n",
    "$$\n",
    "であることに注意しましょう。\n",
    "また、\n",
    "$$\n",
    "\\sum_{a \\in \\mathcal{A}} \\pi(a)\\|a\\|_{V(\\pi)^{-1}}^2=\\operatorname{trace}\\left(\\sum_a \\pi(a) a a^{\\top} V(\\pi)^{-1}\\right)=\\operatorname{trace}(I)=d\n",
    "$$\n",
    "も簡単に成り立ちます。\n",
    "\n",
    "#### $2 \\Rightarrow 1$の証明\n",
    "\n",
    "$\\pi^*$は$f$のMaximizerとします。\n",
    "このとき、凹関数の最適性の性質（[CVX_convex_functions.ipynb](CVX_convex_functions.ipynb)）から、任意の$\\pi$について\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "0 & \\geq\\left\\langle\\nabla f\\left(\\pi^*\\right), \\pi-\\pi^*\\right\\rangle \\\\\n",
    "& =\\sum_{a \\in \\mathcal{A}} \\pi(a)\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2-\\sum_{a \\in \\mathcal{A}} \\pi^*(a)\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2 \\\\\n",
    "& =\\sum_{a \\in \\mathcal{A}} \\pi(a)\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2-d .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます。\n",
    "よって、$\\pi$を$a$でのDirac関数とすると、$\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2 \\leq d$が成り立ちます。\n",
    "一方で、\n",
    "$$\n",
    "\\sum_{a \\in \\mathcal{A}} \\pi(a)\\|a\\|_{V(\\pi)^{-1}}^2=\\operatorname{trace}\\left(\\sum_a \\pi(a) a a^{\\top} V(\\pi)^{-1}\\right)=\\operatorname{trace}(I)=d\n",
    "$$\n",
    "なので、$g(\\pi)\\geq d$です。よって$\\pi^*$は$g$のminimizerであり、$\\min_\\pi g(\\pi)=d$です。\n",
    "\n",
    "#### $2 \\Rightarrow 3$の証明\n",
    "\n",
    "$g(\\pi^*)=d$とします。このとき、\n",
    "$$\n",
    "\\left\\langle\\nabla f\\left(\\pi^*\\right), \\pi-\\pi^*\\right\\rangle=\\sum_{a \\in \\mathcal{A}} \\pi(a)\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}-d \\leq 0\n",
    "$$\n",
    "です。よって、$f$が凹関数であることを踏まえると$\\pi^*$は$f$のmaximizerです。\n",
    "\n",
    "\n",
    "#### $1 \\Rightarrow 3$の証明\n",
    "\n",
    "ほぼ自明なので省略。\n",
    "\n",
    "\n",
    "#### Core setのサイズの証明\n",
    "\n",
    "$S=\\operatorname{Supp}\\left(\\pi^*\\right)$として、$|S|>d(d+1) / 2$とします。\n",
    "ここで、$aa^\\top$は$d\\times d$の対称行列であることを思い出しましょう。よって、\n",
    "$$\n",
    "\\sum_{a \\in S} v(a) a a^{\\top}=\\mathbf{0}\n",
    "$$\n",
    "を満たすような非ゼロの関数$v: \\mathcal{A} \\rightarrow \\mathbb{R}$が$\\operatorname{Supp}(v) \\subseteq S$について存在します（$S$のサイズは$d(d+1)/2$よりでかいので、これが成り立ちます。）\n",
    "\n",
    "また、任意の$a\\in S$について$\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2=d$が成り立つことも示せます（$f$が凹関数であることを使って、$2\\Rightarrow 1$と似たようなことをすれば示せます）\n",
    "\n",
    "よって、\n",
    "$$\n",
    "d \\sum_{a \\in S} v(a)=\\sum_{a \\in S} v(a)\\|a\\|_{V\\left(\\pi^*\\right)^{-1}}^2=0\n",
    "$$\n",
    "が成り立つので、$\\sum_{a \\in S} v(a)=0$です。\n",
    "\n",
    "ここで、$\\pi(t)=\\pi^*+t v$と$\\tau=\\max \\left\\{t>0: \\pi(t) \\in \\Delta_{\\mathcal{A}}\\right\\}$を定義します。これは$v\\neq 0$かつ$\\sum_{a \\in S} v(a)=0$かつ$\\operatorname{Supp}(v) \\subseteq S$なので存在が保証されます。\n",
    "このとき$V(\\pi(t))=V\\left(\\pi^*\\right)$であるから、$f(\\pi(\\tau))=f\\left(\\pi^*\\right)$も成り立ちます。\n",
    "よって$\\pi(\\tau)$も$f$を最大化します。\n",
    "\n",
    "よって、次に$\\pi(\\tau)$を$\\pi^*$と置いて同じことを繰り返すと、$|S| > d(d+1)/2$である限り、$S$の部分集合が台になっている$v$で$\\pi$をどんどん小さくできます。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### コンパクト集合でのKiefer-Wolfowitz\n",
    "\n",
    "これは[Bandit AlgorithmsのExercise 21.3](https://tor-lattimore.com/downloads/book/solutions.pdf)によって証明できます。\n",
    "今回は少し変形した話を証明してみます。\n",
    "\n",
    "まず、Frank-Wolfeアルゴリズムを使うと、有限な$\\mathcal{A}$について\n",
    "* $g(\\pi) \\leq 2d$\n",
    "* $\\operatorname{Supp}(\\pi) \\leq 4d \\log \\log d + 16$\n",
    "\n",
    "なデザイン$\\pi$が獲得できます。これに基づいて、以下を証明してみます。\n",
    "\n",
    "---\n",
    "\n",
    "有限集合について$g(\\pi)\\leq p$かつ$\\operatorname{Supp}(\\pi) \\leq q$なデザイン$\\pi$が存在するなら、コンパクト集合についても存在する。\n",
    "\n",
    "---\n",
    "\n",
    "証明しましょう。\n",
    "まず、$\\mathcal{A}$を$\\mathbb{R}^d$のコンパクトな部分集合とし、$\\left(\\mathcal{A}_n\\right)_n$を次を満たす有限な部分集合とする：\n",
    "\n",
    "1. $\\mathcal{A}_n \\subset \\mathcal{A}_{n+1}$\n",
    "2. $\\operatorname{span}\\left(\\mathcal{A}_n\\right)=\\mathbb{R}^d$\n",
    "3. $\\lim _{n \\rightarrow \\infty} D\\left(\\mathcal{A}, \\mathcal{A}_n\\right)=0$。ここで$D$はハウスドルフ距離\n",
    "\n",
    "ここで、$\\pi_n$を$g(\\pi_n)\\leq p$かつ$\\operatorname{Supp}(\\pi_n) \\leq q$を満たすデザインとする。また、$V_n=V(\\pi_n)=\\sum_{a \\in \\mathcal{A}} \\pi_n(a) a a^{\\top}$と略記する。\n",
    "\n",
    "このとき、任意の$a\\in \\mathcal{A}$について、\n",
    "\n",
    "$$\n",
    "\\|a\\|_{V_n^{-1}} \\leq \\min _{b \\in \\mathcal{A}_n}\\left(\\|a-b\\|_{V_n^{-1}}+\\|b\\|_{V_n^{-1}}\\right) \\leq \\sqrt{p}+\\min _{b \\in \\mathcal{A}_n}\\|a-b\\|_{V_n^{-1}}\n",
    "$$\n",
    "\n",
    "が成り立つ（１つ目は三角不等式、２つ目は仮定）。\n",
    "\n",
    "ここで、$W \\in \\mathbb{R}^{d \\times d}$を、$\\mathbb{R}^d$を張る$A_1$の要素$w_1, \\ldots, w_d$を列に配置して作った行列とする。\n",
    "このとき、\n",
    "\n",
    "$$\n",
    "\\left\\|V_n^{-1 / 2}\\right\\| =\\left\\|W^{-1} W V_n^{-1 / 2}\\right\\| \\leq\\left\\|W^{-1}\\right\\|\\left\\|V_n^{-1 / 2} W\\right\\| \n",
    "$$\n",
    "である（ここで$\\|\\|$は行列のスペクトルノルム）。また、スペクトルノルムの定義から、\n",
    "\n",
    "$$\n",
    "\\left\\|V_n^{-1 / 2} W\\right\\| \n",
    "=\\sup_{\\|x\\|_2=1} \\frac{\\left\\|V_n^{-1 / 2} W x\\right\\|}{\\|x\\|}\n",
    "=\\sup_{\\|x\\|_2=1} {\\left\\|V_n^{-1 / 2} W x\\right\\|}\n",
    "$$\n",
    "\n",
    "であり、\n",
    "$$\n",
    "\\|W x\\|_{V_n^{-1}} = V_n^{-1 / 2} (Wx)\n",
    "$$\n",
    "なので、\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\left\\|V_n^{-1 / 2}\\right\\| &=\\left\\|W^{-1}\\right\\| \\sup \\left\\{\\|W x\\|_{V_n^{-1}}:\\|x\\|_2=1\\right\\} \\\\\n",
    "& \\leq\\left\\|W^{-1}\\right\\| \\sup \\left\\{\\sum_{i=1}^d\\left|x_i\\right|\\left\\|w_i\\right\\|_{V_n^{-1}}:\\|x\\|_2=1\\right\\} \\\\\n",
    "& \\leq\\left\\|W^{-1}\\right\\| \\sqrt{d} \\sup _{x:\\|x\\|_2=1} \\sum_{i=1}^d x_i \\\\\n",
    "& \\leq d\\left\\|W^{-1}\\right\\| .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成立。\n",
    "ここで$n$を無限に飛ばすと\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\limsup _{n \\rightarrow \\infty}\\|a\\|_{V_n^{-1}} & \\leq p+\\limsup _{n \\rightarrow \\infty} \\min _{b \\in \\mathcal{A}}\\|a-b\\|_{V_n^{-1}} \\\\\n",
    "& \\leq p+d\\left\\|W^{-1}\\right\\| \\limsup _{n \\rightarrow \\infty} \\min _{b \\in \\mathcal{A}}\\|a-b\\|_2 \\\\\n",
    "& = p .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "$\\|\\cdot\\|_{V_n^{-1}}: \\mathcal{A} \\rightarrow \\mathbb{R}$は連続かつ$\\mathcal{A}$はコンパクトなので、\n",
    "\n",
    "$$\\limsup _{n \\rightarrow \\infty} \\sup _{a \\in \\mathcal{A}}\\|a\\|_{V_n^{-1}}^2 \\leq p$$\n",
    "\n",
    "よって$g(\\pi) \\leq p$が成立。\n",
    "\n",
    "一方で、$\\operatorname{Supp}(\\pi_n) \\leq q$より、$\\pi_n$は$(a_1, p_1), (a_2, p_2), \\dots$のような（ベクトル、確率）のタプルを$q$個合わせたもので表現できる。\n",
    "このような集合は明らかにコンパクト集合を形成できるので、サポートが$q$個のような$\\mathcal{A}$を表現する分布$\\pi^*$を持つ。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}