Bootstrap method for opitmization

简单直观的给出我们的方法一致性定理如下：

Theorem(consistant of bootstrap method for optimization)

Optimazation problem \[\mathop{ess.inf} \limits_{x \in R^n} f(x) \; s.t. \; g(x) \in B_{\delta}(r) = B.\] where \(B_{\delta}(r) = [r-\delta, r+\delta]\), \(X_1,...,X_m\) is sampled with uniform distribution in \(\{x: g(x) \in B_{\delta}(r)\}\), then under some conditons, we have that the under part \(\hat{h}_m(s)\) of 凸包 of set \(\{(f(X_k), g(X_k))\}_{k = 1, ..., m}\) satisfies that \(Pr(|\hat{h}(r) - h(r)| > \varepsilon) \rightarrow 0, as \; m \rightarrow \infty\).

需要满足的条件是如下：

1. 存在一个有限矩形包含集合\(\{x: g(x) \in B_{\delta}(r)\}\)。
2. 存在\(h(s)\) 使得 \(\mathop{Ess.inf}\limits_{x \in R^n} [f(x)|g(x) = s] = h(s)\) 在 \(B_{\delta}(r)\) 上是个连续的凸函数。
3. \(T:x \rightarrow (g(x),f(x))\) is continous.

其他说明：

• 二元平面上任何点集合都会有一个凸包函数，而凸包函数可以分成上半部分和下半部分，我们的条件本质下却界估计取的是凸包函数的下半部分。它有很多性质：
  • \(\hat{h}_m(s)\) 的定义域集合是单调递增的，并且m足够大时, 一定包含 r的某个邻域。
  • \(\hat{h}_m(s) \leq \hat{h}_{m+1}(s)\) for any \(s\in B_{\delta^{'}}(r)\)。
• f关于g的条件本质下却界是指几乎出处不超过f的\(\sigma(g)\)可测函数。可以参看条件期望的定义。

Proof. For any \(\varepsilon > 0\), we want to prove \(Pr(|\hat{h}_m(r) - h(r)| > \varepsilon) \rightarrow 0\) as \(m \rightarrow \infty\). 由于凸包估计的单调性，我们只需要证明以概率为1，存在某个\(m\),使得 \(|\hat{h}_m(r) - h(r)| < \varepsilon\) 成立。

Obvious, there is a 凸包估计 function of \(h(s)\), whose definition range contain \(r\) with probability 1, denoted as \(h_{m_0}(s)\). 下面我们根据这个估计，继续抽样构造出符合条件\(|\hat{h}_{m_1}(r) - h(r)| < \varepsilon\)的估计。

We find surport points for \(\hat{h}_{m_0}(s)\), and denote it as \(\{r_j\}_{j = 1,..., I_{m_0}}\) with increasing order, find the interval \([r_j, r_{j+1}]\) which contains r.

If \(|\hat{h}_{m_0}(r) - h(r)| < \varepsilon\), then \(\hat{h}_{m_0}(r)\), 令 \(m_1 = m_0\) 就是我们需要的 \(m\);

Else continue to sample, 我们说明抽样次数m,足够大的时候，以概率 \(1\) 存在某个样本\(X_{m_1}\)，使得 \(T(X_{m_1}) \in B_d(r,h(r))\)(其中d 是\((r_j, \hat{h}_{m_0}(r_j)), (r_{j+1}, \hat{h}_{m_0}(r_{j+1}))\)之间连线和 \(y\)轴心的夹角）, 在这种情况下，会有\(\hat{h}_{m_1}(r) - h(r) < d = \varepsilon |sin(\theta)| \leq \varepsilon\)

那么为什么能以概率1抽到这样的样本呢？注意到在\(R^2\)中矩形区域抽样，它落在任何面积开集中的概率非零，那么我们可以抽取到此开集中的样本 with probability 1。对于本定理，我需要抽取的集合是 \(T^{-1}(A)\), where \(A = B_d(r,h(r)) \bigcap \bigtriangleup, \; \bigtriangleup\) 是三个点 \((r_j, \hat{h}_{m_0}(r_j)), (r_{j+1}, \hat{h}_{m_0}(r_{j+1})),(r, {h}(r))\) 构成的三角形。三角形内部点集合和球形邻域都是开集，那么他们的交也是开集，根据连续性，那么\(T^{-1}(A)\)是一个开集。

所以随着抽样次数趋近于无穷，以概率1会得到一个样本 \(X_{m_1}\), 此样本下的估计 \(\hat{h}_{m_1}(r) - h(r) < \varepsilon\). 得证。