von Neumannのmin-max定理に基づくhardcore lemmaの証明

 Impagliazzoのhardcore lemmaに関する以前の記事ではboosting algorithmとして解釈できる証明を与えました. 本記事ではvon Neumannのmin-max定理に基づく証明を与えます. この証明はImpagliazzo(95)に書いてありますが, アイデア自体はNisanによって与えられたものらしいです. Impagliazzoの元論文やArora--Barakの本にも同様の議論が紹介されていますが, これらを自分なりにかなり噛み砕いて説明していきます.

1. hardcore lemmaの復習

• 関数$f\colon\{0,1\}^n\to\{0,1\}$と入力分布$D$を考える. 任意のサイズ$s$以下の回路$C$に対し $\Pr_{x\sim D}[C(x)=f(x)]\leq 1-\delta$が成り立つとき, $f$は$D$上でサイズ$s$に対して$\delta$-hardであるという.
• 関数$M\colon\{0,1\}^n\to[0,1]$をmeasureと呼ぶ. $|M|:=\sum_{x\in\{0,1\}^n}M(x)\geq \delta 2^n$を満たすとき$M$は$\delta$-denseであるという.
• measure $M$ が誘導する以下の$\{0,1\}^n$上の確率分布を考える: 各$x\in\{0,1\}^n$が選ばれる確率は$M(x)/|M|$. これを$x\sim M$と表す.
• $\{0,1\}^n$上の一様分布を$U_n$で表す.

定理1(hardcore lemma; Impagliazzo 95)

$f\colon\{0,1\}^n\to\{0,1\}$を$U_n$上でサイズ$s$に対し$\delta$-hardな関数とする. あるサイズ$\delta2^n$以上の集合$H\subseteq\{0,1\}^n$が存在して, $f$は$H$上一様分布上でサイズ$O(s\delta^2\epsilon^2)$に対して$(1/2-\epsilon)$-hardである.

定理1は直感的には「$f$が入力全体上でちょっとhardならば多くの難入力からなる集合$H$がとれてその上ではすごくhardである」ということを意味します(この集合$H$をhardcore setといいます). 証明するには最終的に「難入力からなる集合$H$がとれる」ことを言わなければなりませんが, まず集合を01のindicatorとみなしこれの連続緩和であるmeasureに対して, hardcore measureの存在性を証明し, それをrandomized roundingしてhardcore set の存在性を証明します. 前半のステップには大きく分けて二つの証明手法があり, 一つが前回の記事で紹介したboosting algorithmに基づくものです. もう一つが本記事で紹介するvon Neumannのmin-max定理に基づくものです. 具体的には以下の定理を証明します.

定理2(hardcore measure)

$f\colon\{0,1\}^n\to\{0,1\}$を$U_n$上でサイズ$s$に対し$\delta$-hardな関数とする. ある$\delta$-denseなmeasure $M$ が存在して, $f$は$M$上でサイズ$s'=O(s\epsilon^2/\log(\delta^{-1}\epsilon^{-1}))$に対して$(1/2-\epsilon)$-hardである.

定理2の証明の準備としてvon Neumannのmin-max定理の特殊ケースとして得られる以下の補題を述べておきます.

補題3(min-max定理の特殊ケース)

$A,B$を有限集合とし, $x\in[0,1]^A,\,y\in[0,1]^B$をそれぞれ$A$上と$B$上の確率分布とする. $R\colon A\times B\to\mathbb{R}$を関数とし, $c(x,y):=\mathrm{E}_{a\sim x,b\sim y}[R(a,b)]$とする. このとき, $\max_x\min_y c(x,y)=\min_y\max_x c(x,y)$が成り立つ.

上記の補題はしばし二人ゼロ和ゲームの文脈で解釈されます. すなわち二人のプレーヤー1,2がいて, プレーヤー1は戦略として$a\in A$をとることができ, プレーヤー2は戦略として$b\in B$をとることができます. このときにプレーヤー1の報酬を$R(a,b)$とします(同時にプレーヤー2が得る報酬は$-R(a,b)$としてゼロ和ゲームとします). すると$x,y$はそれぞれプレーヤー1,2の混合戦略(戦略集合上の確率分布)とみなすことができ, $c(x,y)$はそれぞれの混合戦略をとった時の期待報酬になります.

定理2の証明

以下の二人ゼロ和ゲームを考えます: プレーヤー1はサイズ$s'$の回路$C$を選び, プレーヤー2は$\delta$-denseな集合$H$を選びます. プレーヤー1が得る報酬は$R(H,C)=\Pr_{x\sim H}[C(x)=f(x)]$とします. つまり, プレーヤー1の目的はできるだけ良い回路を選び$R(H,C)$をできるだけ大きくし, プレーヤー2の目的はできるだけ難しい入力集合$H$を選び$R(H,C)$をできるだけ小さくすることです.

両プレーヤーの混合戦略$\mathcal{C},\mathcal{H}$の期待報酬$c(\mathcal{C},\mathcal{H})$を考えます. 補題3より以下の二つのうちどちらか一方が成り立ちます.

• ケース1: $\min_{\mathcal{H}}\max_{\mathcal{C}} c(\mathcal{H},\mathcal{C})<1/2+\epsilon$.
• ケース2: $\max_{\mathcal{C}}\min_{\mathcal{H}} c(\mathcal{H},\mathcal{C})\geq 1/2+\epsilon$.

ケース1: $\max_\mathcal{C}$の混合戦略の部分を純粋戦略に置き換えても期待報酬は上がらないので, $\min_{\mathcal{H}}\max_{C} c(\mathcal{H},C)<1/2+\epsilon$です (ここで$C$はサイズ$s'$以下の回路全体を動きます). また, $\mathcal{H}$は$\{0,1\}^n$の分布$D$を以下のように誘導します: まず$H$を$\mathcal{H}$に従って選択し, $H$上の一様分布を出力する.

このように定義された$D$に対して$D(x)$を$x$が出力される確率と定義すると, 関数$M(x)=\delta 2^n D(x)$は$[0,1]$上の値をとるためmeasureになっており, しかも$\sum_{x\in\{0,1\}^n}M(x)=\delta 2^n$なので$\delta$-denseです. さらに$x\sim M$と$x\sim D$は同じ分布です. 任意に固定された小さい回路$C$に対し$$c(\mathcal{H},C)=\mathrm{E}_{H\sim\mathcal{H}}[\Pr_{x\sim H}[C(x)=f(x)]]=\Pr_{x\sim M}[C(x)=f(x)]<1/2+\epsilon$$なので, $M$はhardcore measureになっているため定理2の主張が成り立ちます.

ケース2: 回路の良い混合戦略$\mathcal{C}$が存在することになります. 集合$H$の選び方を混合戦略から純粋戦略に置き換えるとプレーヤー2のとれる選択肢の幅が狭まります. つまりある$\mathcal{C}$が存在して任意のサイズ$\geq \delta 2^n$の集合$H$に対し$\mathrm{E}_{C\sim\mathcal{C}}[R(C,H)]=\Pr_{C\sim\mathcal{C},x\sim H}[C(x)=f(x)]\geq 1/2+\epsilon$が成り立ちます.

ここで, 固定した入力$x\in\{0,1\}^n$に対して$\Pr_{C\sim\mathcal{C}}[C(x)=f(x)]\leq 1/2+\epsilon/2$が成り立つときに入力$x$はgoodであるということにします. 直感的にはgoodとはプレーヤー2にとって($\mathcal{C}$の正答率を下げられるという意味で)都合の良い入力です. $S\subseteq \{0,1\}^n$をgoodな入力の全体としましょう. 直感的には$S$が多いと$\mathcal{C}$にとって困難な入力集合を構成できてしまうので$|S|$は小さいはずです. 実際にこの直感は成り立ちます.

主張: $|S|\leq \delta(1-\epsilon)2^n$.

主張の証明. $S$に要素を任意に追加していきサイズ$\delta 2^n$にしたものを$H^*$とします. $H^*$から一様ランダムに入力を選ぶと確率$|S|/\delta 2^n$で$S$上の一様分布, 残りの確率で$H^*\setminus S$上の一様分布で選ばれます. 前者の入力に対する$\mathcal{C}$の正答率は高々$1/2+\epsilon/2$で後者は高々$1$です. よって

$$\frac{1}{2}+\epsilon \leq \mathrm{E}_{C\sim \mathcal{C}}[\Pr_{x\sim H^*}[C(x)=f(x)]] \leq \frac{|S|}{\delta 2^n}\left(\frac{1}{2}+\frac{\epsilon}{2}\right)+\left(1-\frac{|S|}{\delta 2^n}\right)$$

を得ます. これを$|S|$について解くと$|S|\leq \delta 2^n\cdot \frac{1-2\epsilon}{1-\epsilon}\leq \delta (1-\epsilon)2^n$です.

最後に, $\mathcal{C}$から独立に$t$個の回路$C_1,\dots,C_t$をサンプリングしてそれらをmajorityで結合したものを$C'$とします. 任意の$x\not\in S$に対して$t$個のindicator $\mathbf{1}[C_1(x)=f(x)],\dots,\mathbf{1}[C_t(x)=f(x)]$はiidな確率変数であり, これらの期待値は$x\not\in S$より$1/2+\epsilon/2$以上です. 従ってHoeffdingの不等式より

$$\Pr_{C_1,\dots,C_t}[C'(x)\neq f(x)]=\Pr\left[\sum_{i=1}^t\mathbf{1}[C_i(x)=f(x)]\leq t/2\right] \leq \exp(-\epsilon^2t/2). $$

この確率は適当な$t=O(\epsilon^{-2}\log(\epsilon^{-1}\delta^{-1}))$に対して$\leq \delta\epsilon$となります. この$t$に対して$C'$を考えるとそのサイズは$O(ts')<s$となります. また, 固定した$C'$に対して

$$\Pr_{x\sim U_n}[C'(x)\neq f(x)]\leq \Pr_{x\sim U_n}[x\in S]+\Pr_{x\sim \{0,1\}^n\setminus S}[C'(x)\neq f(x)]$$

および$|S|$の上界より,

$$\mathrm{E}_{C'}[\Pr_{x\sim U_n}[C'(x)\neq f(x)]] \leq \delta(1-\epsilon)+\delta\epsilon =\delta.$$

よって$C'$は期待値的には一様分布上で$f$を確率$1-\delta$で計算することになるので, averaging principleにより正の確率でこの性質を満たします. probabilistic methodにより仮定($f$の$\delta$-hardness)に矛盾する回路$C'$の存在性が言えました. (証明終)

証明におけるケース2の$C'$の構成はboostingの時に考えた構成と同様にmajorityをとっていますがここではi.i.d.に$C_1,\dots,C_t$を$\mathcal{C}$からサンプリングしています. ただ, この回路$C'$はランダムに構成された回路であってあくまでもその存在性はprobabilistic argumentに基づいています.