次指数过程上确界的多项式时间逼近算法

Polynomial Time Approximation Algorithm for Supremum of Sub-Exponential Processes

摘要: 本文提出了一个用于逼近一类次指数过程上确界的算法，具体来说，给定一个有限的向量集合$V\subseteq {ℝ}^d$ ，对于集合上密度函数对称单峰的次指数过程X，我们能够在多项式时间内确定性地计算出其上确界的期望，即$\mathbb{E}\left[su{p}_{v\in V}\left|\langle v,X\rangle \right|\right]$ 的$\left(1+\epsilon \right)$ 阶的近似值，其中X服从d维正态分布，$\epsilon$ 是一个大于0的常数。在此前，相关的工作只研究了高斯过程的上确界的算法，而次指数过程作为高斯过程的扩展，在泛函分析、凸几何以及有限图上的随机游走等领域有着广泛的应用，其上确界的近似算法在高斯假设过强的场景下具有重要的研究价值，可以提供的合理的理论保证。

Abstract: This paper proposes an algorithm for approximating the upper bound of a class of sub-exponential processes. Specifically, given a finite set of vectors $V\subseteq {ℝ}^d$ , for a sub-exponential process X with a density function that is symmetric and unimodal on the set, we can deterministically compute the expected upper bound in polynomial time, that is, the $\left(1+\epsilon \right)$ -th order approximation of ${\mathbb{E}}_{X\leftarrow {\mathcal{N}}^d}\left[su{p}_{v\in V}\left|\langle v,X\rangle \right|\right]$ , where X follows a d-dimensional normal distribution, and $\epsilon$ is a constant greater than 0. Prior to this, related work has only studied algorithms for the upper bounds of Gaussian processes, while sub-exponential processes, as an extension of Gaussian processes, have a wide range of applications in functional analysis, convex geometry, and random walks on finite graphs, among other fields. The approximation algorithm for the upper bound has significant research value in scenarios where the Gaussian assumption is too strong, providing a reasonable theoretical guarantee.

1. 引言

高斯过程的上确界研究是概率论和泛函分析的一个重要领域，给定一个任意的度量空间$\left(T,d\right)$ ，对于该空间上的高斯过程$\left\{X_t,t\in T\right\}$ ，我们希望研究$\mathbb{E}{\sup }_{t\in T}{X}_t$ 的上界，这是Fernique和Talagrand的著名的占优测度定理研究的重要内容，具体为

$\frac{1}{L}{\gamma }_2\left(T,d\right)\le \mathbb{E}{\sup }_{t\in T}{X}_t\le L{\gamma }_2\left(T,d\right)$

其中${\gamma }_2\left(T,d\right)$ 是只跟度量空间有关的泛函，L是一个常数因子，有兴趣的读者可以参见Ledoux和Talagrand [1]，Talagrand [2]的相关工作及其参考文献获得更多的细节。这是一个非常强的结论。到目前为止，已经有大量关于获得高斯过程上确界紧密估计和特征化的工作，这些工作在压缩感知Krahmer [3]等人，凸几何Pisier [4]等领域有多项应用，可以将具体的量转化为这种形式的上界并加以控制。

我们主要关注的问题在于Ding, Lee和Peres [5]在图论中的重大进展，即使用强大的Dynkin同构理论和占优测度定理建立了有限联通随机图G的覆盖时间与G上的高斯自由场相关的高斯过程的上确界之间的结构联系。然后，他们利用这个联系解决了Winkler-Zuckerman [6]毯(blanket)时间猜想，并获得了第一个确定性多项式时间内常数因子逼近算法来计算随机图的覆盖时间。这个结果解决了Aldous和Fill [7] 1994年以来的一个长期开放问题。上确界的计算时间是关于概率和泛函分析中高斯过程的丰富文献中较少研究的一个方面。从算法的角度看，Talagrand的占优测度定理本质上是有限制的，因为其得到的上界中的 常数因子L的大小在理论研究中并不是关心的问题，所以在某些应用中它可能取值较大，而一个好的逼近算法则希望可以足够接近这个量本身，即在算法具体实现时，这个常数因子越趋近于1越好，因此，Ding [5]等人提出了有关该问题计算性的另一个开问题，具体而言，对于任意的$\epsilon >0$ ，是否存在一个确定性的多项式算法，使得对于向量集合$v_1,\cdots ,v_m\in {ℝ}^d$ ，对于$\mathbb{E}\left[{\sup }_i\left|\langle v_i,X\rangle \right|\right]$ 有一个$\left(1+\epsilon \right)$ 阶的逼近算法，而Meka [8]通过借助凸几何中经典的比较不等式成功的解决了这一问题，此后越来越多的工作开始关注占优测度定理在算法上的定量研究，例如Borst [9]等人提供了一种基于凸优化的观点来看待占优测度，他们通过求解一个凸规划问题找到最佳的测度，还给出了一个组合的证明方法，用于构建与占优测度相联系的上下界的证明。此外，该方法将原始的占优测度理论应用于各种非高斯过程，以示了其一般性和通用性。

受到Meka [8]工作的启发，我们尝试考虑一类次指数过程上确界问题的多项式时间内的逼近算法，众所周知，次指数随机变量都是次指数的，作为高斯过程的自然推广，其随机变量的分布比正态分布更集中，即其尾部概率衰减速度比正态分布更快。具体来说，如果一个随机变量X满足对于任意的$t>0$ ，都有$P\left(\left|X\right|>t\right)\le C\exp \left(-t\right)$ ，其中C是常数，则称X为次指数随机变量，而如果一个随机过程的所有随机变量都是次指数的，但是其随机变量的矩母函数可能是不收敛的，这相较高斯分布在直观上以更大概率产生异常值，其分布的行为更难以预测，对于d维随机向量，若对于任意的$v\in V$ ，$\langle v,X\rangle$ 都为次指数随机变量，则称X为次指数随机向量。次指数过程在在信号处理、通信领域、机器学习与数据挖掘等领域都有着广泛的应用，显然，估计次指数过程上确界的期望的难度在于，更复杂的分布特性对于估计$\mathbb{E}{\sup }_{t\in T}{X}_t$ 上界的精准度有着更高的要求，而对于高斯过程上界$\left(1+\epsilon \right)$ 阶矩的结果在此并不适用，而目前次指数过程$\left(1+\epsilon \right)$ 阶矩的逼近算法尚未有相关工作涉及，本文将在适当的假设下针对一部分次指数过程解决这一问题。

2. 预备知识和主要结果

2.1. 降维

本文的核心想法是一个去随机化版本的Johnson-Lindenstrauss引理(参见Engebretsen等人[10])的降维操作，对于固定的向量集合$V=\left\{v_1,\cdots ,v_m\right\}\subseteq {ℝ}^d$ 和$\epsilon >0$ ，不失一般性，我们假设${\max }_{v\in V}{\Vert v\Vert }_2=1$ ，我们将V投影到$O\left(\left(\log m\right)/{\epsilon }^2\right)$ 维度的空间中，并且在Johnson-Lindenstrauss引理中保持所有的成对(欧氏距离)在$\left(1+\epsilon \right)$ 阶内，此时我们将说明投影后的次指数过程的期望上确界与原始的期望上确界保持在$\left(1+\epsilon \right)$ 内，我们通过经典的Fernique-Slepian引理来量化这一个事实，通过比较随机过程成对的相关性来关联两个次指数过程的上确界，以下结果参见van Handel [11]。

引理1.1. 令${\left\{X_t\right\}}_{t\in T}$ 和${\left\{Y_t\right\}}_{t\in T}$ 为两个$\left(T,d\right)$ 上的次指数随机过程，则对于一个通用常数C，有

$E\left[\underset{t\in T}{\text{sup}}{X}_t\right]\le CE\left[\underset{t\in T}{\text{sup}}{Y}_t\right]$

此时，我们给出下面去随机的Johnson-Lindenstrauss引理，因此降维可以在$O\left(\left(\log m\right)/{\epsilon }^2\right)$ 时间内确定性的完成。

定理1.1. 对于任意的$\epsilon >0$ ，存在一个计算时间为$\left({\text{dm}}^2{\left(\log m+1/\epsilon \right)}^{O\left(1\right)}\right)$ 的算法，给定向量$v_1,\cdots ,v_m\in {ℝ}^d$ ，计算一个线性映射$A:{ℝ}^d\to {ℝ}^k$ ，其中$k=O\left(\left(\log m\right)/{\epsilon }^2\right)$ ，使得对于任意$i,j\in \left[m\right]$ ，都有${\Vert v_i-v_j\Vert }_2\le {\Vert A\left(v_i\right)-A\left(v_j\right)\Vert }_2\le \left(1+\epsilon \right){\Vert v_i-v_j\Vert }_2$ 。

结合上面两个结果，我们可以得到

定理1.2. 对于任意的$\epsilon >0$ ，存在一个计算时间为$\left({\text{dm}}^2{\left(\log m+1/\epsilon \right)}^{O\left(1\right)}\right)$ 的算法，给定向量$v_1,\cdots ,v_m\in {ℝ}^d$ ，计算一个线性映射$A:{ℝ}^d\to {ℝ}^k$ ，其中$k=O\left(\left(\log m\right)/{\epsilon }^2\right)$ ，则对于d维次指数随机向量X和k维随机向量Y，有下式成立

$\mathbb{E}\left[\underset{i}{\sup }\left|\langle v_i,X\rangle \right|\right]\le \mathbb{E}\left[\underset{i}{\sup }\left|\langle A,\left(v_i\right),Y\rangle \right|\right]\le \left(1+\epsilon \right)\mathbb{E}\left[\underset{i}{\sup }\left|\langle v_i,X\rangle \right|\right]$ 。

证明

令$V=\left\{v_1,\cdots ,v_m\right\}\cup \left\{-v_1,\cdots ,-v_m\right\}$ ，并令${\left\{X_v\right\}}_{v\in V}$ 是次指数过程，其中$X_v\equiv \langle v,X\rangle$ ，则有$\mathbb{E}\left[{\sup }_i\left|\langle v_i,X\rangle \right|\right]=\mathbb{E}\left[{\sup }_v{X}_v\right]$ ，令$A:{ℝ}^d\to {ℝ}^k$ 是按照定理2.1作用于V的线性映射，${\left\{Y_v\right\}}_{v\in V}$ 是对应的次指数过程，有$Y_v\equiv \langle A,\left(v\right),Y\rangle$ ，即$\mathbb{E}\left[{\sup }_i\left|\langle v_i,Y\rangle \right|\right]=\mathbb{E}\left[{\sup }_v{Y}_v\right]$ 。观察到，对于任意的$u,v\in V$ ，

$\begin{array}{c}\mathbb{E}\left[{\left(X_u-X_v\right)}^2\right] ={\Vert u-v\Vert }_2^2\le {\Vert A\left(u\right)-A\left(v\right)\Vert }_2^2\\ =\mathbb{E}\left[{\left(Y_u-Y_v\right)}^2\right]\le {\left(1+\epsilon \right)}^2\mathbb{E}\left[{\left(X_u-X_v\right)}^2\right]\end{array}$

则上述不等式结合引理2.1应用与过程$\left({\left\{X_v\right\}}_{v\in V},{\left\{Y_v\right\}}_{v\in V}\right)$ 和$\left({\left\{Y_v\right\}}_{v\in V},{\left\{\left(1+\epsilon \right)X_v\right\}}_{v\in V}\right)$ ，我们可以得到

$\mathbb{E}\left[\underset{v}{\sup }\left|X_v\right|\right]\le \mathbb{E}\left[\underset{v}{\sup }\left|Y_v\right|\right]\le \mathbb{E}\left[\underset{v}{\sup }\left(1+\epsilon \right)\left|X_v\right|\right]=\left(1+\epsilon \right)\mathbb{E}\left[\underset{v}{\sup }\left|X_v\right|\right]$ 。

2.2. 多项式时间内的半范数估计量

在上一节中，我们将d维次指数过程的上确界转化为$O\left(\left(\log m\right)/{\epsilon }^2\right)$ 维，我们接下来将提供逼近次指数过程上确界的这一算法。这个算法一般的适用于所有的半范数的结果，我们假设$\phi :{ℝ}^k\to {ℝ}_{+}$ 是一个半范数，即我们只要求$\phi$ 满足齐次性以及三角不等式，为了归一化，我们假设$1\le \mathbb{E}\left[\phi \left(x\right)\right]$ ，其中x满足k维的次指数过程，我们用${\mathcal{N}}^k$ 表示k维的次指数分布，并且$\phi$ 的Lipschitz常数至多为$k^{O\left(1\right)}$ ，这个假设在很多种情况下都可以满足，特别的，${\phi }_V\left(x\right)={\text{sup}}_{v\in V}\left|\langle v,x\rangle \right|$ 满足这一假设，满足上述假设后，我们有如下结果成立。

定理1.3. 对于任意$\epsilon >0$ ，存在一个集合$S\subseteq {ℝ}^k$ ，其基数为$\left|S\right|={\left(1/\epsilon \right)}^{O\left(k\right)}$ ，函数$p:{ℝ}^k\to {ℝ}_{+}$ ，可以在多项式时间poly $\left(k,1/\epsilon \right)$ 内得到，使得对于任意半范数$\phi :{ℝ}^k\to {ℝ}_{+}$ ，都有下面结果成立

$\left(1-\epsilon \right)\left({\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)\right)\le \mathbb{E}\left[\phi \left(X\right)\right]\le \left(1+\epsilon \right)\left({\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)\right).$

该算法的思路是非常自然的，即我们尝试对于次指数分布的密度函数以均匀分布进行离散化，构造$ℝ$ 上的一个对称分布$\mu$ ，这可以看做一个分段函数，并且在以下意义上夹住次指数分布；设v是$\mu$ 的一个收缩，再通过乘积分布${\mu }^k$ 来计算期望，在对称性和单峰性的假设下，我们可以得到一个不依赖维度k的误差界，其概率密度函数为$\left(1-\epsilon \right)x$ ，当$x\leftarrow \mu$ 时，我们将证明，如果$\mu$ 以${\epsilon }^{3/2}$ 维标准进行分段划分，则对于任意的对称凸集$I\subseteq ℝ$ ，我们有$\mu \left(I\right)\le \mathcal{N}\left(I\right)\le v\left(I\right)$ 。简而言之，半范数不能区分${\mu }^k$ 和${\mathcal{N}}^k$ ，即对于任意的半范数$\phi$ ，${\mathbb{E}}_{{\mu }^k}\left[\phi \left(x\right)\right]=\left(1\pm \epsilon \right){\mathbb{E}}_{{\mathcal{N}}^k}\left[\phi \left(x\right)\right]$ 。首先我们给出如下定义：

定义1.1. 定义在${ℝ}^n$ 上的分布f成为单峰的，若f可以写成一个序列的递增极限，每个分布都是对称凸集上的均匀分布的有限正权重和。

显然，通过对于集合S进行枚举，通过在S上的点来查询$\phi$ ，本文的主要结果可以得出。

定理1.4. 对于d维，密度函数对称单峰的次指数过程X，对于任意的$\epsilon >0$ ，都存在一个非随机的算法，在多项式时间${\left(1/\epsilon \right)}^{O\left(k\right)}$ ，空间复杂度poly $\left(k,1/\epsilon \right)$ ，并且仅使用$\phi$ 得到$\mathbb{E}\left[\phi \left(X\right)\right]$ 的$\left(1+\epsilon \right)$ 阶近似。

3. 证明

从现在起，我们令$\gamma$ 为次指数分布的对称函数，如之前假设，$\gamma$ 为对称单峰的，固定$\epsilon >0$ ，并令$\delta >0$ 是一个参数，我们将在后文选择，令$\mu \equiv {\mu }_{\delta }$ 是对于$\gamma$ 在区间$I=\left[i\delta ,\left(i+1\right)\delta \right)$ 上用均匀分布进行质量近似得到的分段近似分布，并令$\mu \left(z\right)=\mu \left(-z\right)$ ，则对于$z>0,z\in \left[i\delta ,\left(i+1\right)\delta \right)$ ，我们有

$\mu \left(z\right)=\frac{\gamma \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)}{\delta }.$

显然，$\mu$ 是$ℝ$ 上的对称分布，此处，如我们之前所提，如果参数$\delta \ll \epsilon$ 足够的小，半范数不能够区分${\mu }^k$ 和${\mathcal{N}}^k$ 。

引理2.2 令$\delta ={\left(2\epsilon \right)}^{3/2}$ ，则对于k维次指数向量Z，和分布为${\mu }^k$ 的随机向量X，对于任意半范数$\phi :{ℝ}^k\to ℝ$ ，有

$\left(1-\epsilon \right)\mathbb{E}\left[\phi \left(X\right)\right]\le \mathbb{E}\left[\phi \left(Z\right)\right]\le \mathbb{E}\left[\phi \left(X\right)\right].$

在给出引理2.2的证明之前，我们首先引入如下定义，帮助我们通过凸集的体积比较两个多变量分布的大小，该定义是来自Ball [12]。

定义2.2. 给定两个对称的${ℝ}^k$ 上的概率密度函数$f,g$ ，称f峰值比g小，记为$\left(f\underset{\_}{\prec }g\right)$ ，若对于任意凸集$K\subseteq {ℝ}^k$ ，有$f\left(K\right)\le g\left(K\right)$ 。

在如上定义下，我们有对于任意的半范数$\phi :{ℝ}^k\to ℝ$ ，若$f\underset{\_}{\prec }g$ ，则${\mathbb{E}}_f\left[\phi \left(x\right)\right]\ge {\mathbb{E}}_g\left[\phi \left(x\right)\right]$ 。

引理2.4. (Kanter’s 引理[13]). 令${\mu }_1,{\mu }_2$ 是${ℝ}^n$ 上的对称分布，满足${\mu }_1\underset{\_}{\prec }{\mu }_2$ ，令v是${ℝ}^m$ 上的单峰分布，则${\mu }_1\times v,{\mu }_2\times v$ 在${ℝ}^n\times {ℝ}^m$ 上的乘积分布满足${\mu }_1\times v\underset{\_}{\prec }{\mu }_2\times v$ 。

引理2.5. 令$\gamma$ 是如上定义的次指数分布，设随机变量X分布是$\mu ,v$ 是随机变量$Y=\left(1-\epsilon \right)X$ 的分布，则若$\delta \le {\left(2\epsilon \right)}^{3/2}$ ，我们有$\mu \underset{\_}{\prec }\gamma \underset{\_}{\prec }v$ 。

证明

由于上文已经有$\mu \underset{\_}{\prec }\gamma$ ，我们只需证明$\gamma \underset{\_}{\prec }v$ ，我们直观上来看，v是通过将$\gamma$ 在区间$I=\left[i\delta ,\left(i+1\right)\delta \right)$ 上的质量均匀分布在较小的区间$\left(1-\epsilon \right)I$ 上获得的，对于足够小的$\delta$ ，我们固定区间$I=\left[-i\delta \left(1-\epsilon \right)-\theta ,i\delta \left(1-\epsilon \right)+\theta \right]$ ，其中$0\le \theta <\delta \left(1-\epsilon \right)$ ，则

$\begin{array}{c}v\left(I\right)=v\left(\left[-i\delta \left(1-\epsilon \right),i\delta \left(1-\epsilon \right)\right]\right)+2v\left(\left[i\delta \left(1-\epsilon \right),i\delta \left(1-\epsilon \right)+\theta \right]\right)\\ =\gamma \left(\left[-i\delta ,i\delta \right]\right)+\frac{2\theta \cdot \gamma \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)}{\delta \left(1-\epsilon \right)}\end{array}$

现在存在两种情况：

1. 令$i\ge \left(1-\epsilon \right)/\epsilon$ 使得$i\delta \left(1-\epsilon \right)+\theta \le i\delta$ ，则由上式，我们有

$\nu \left(I\right)\ge \gamma \left(\left[-i\delta ,i\delta \right]\right)\ge \gamma \left(\left[-i\delta \left(1-\epsilon \right)-\theta ,i\delta \left(1-\epsilon \right)+\theta \right]\right)=\gamma \left(I\right).$

2. 若$i<\left(1-\epsilon \right)/\epsilon$ 。我们令$\alpha =\left(i+1\right)\delta =\delta /\epsilon$ 。则由于次指数分布的定义，$1-x\le {\text{e}}^{-x}\le 1$ ，

$\gamma \left(\left(i\delta ,i\delta +\theta \right]\right)\le \theta \cdot \gamma \left(0\right),\gamma \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)\ge \delta \cdot \gamma \left(0\right)\cdot \left(1-\alpha \right).$

因此我们有

$\begin{array}{c}v\left(I\right)=\gamma \left(I\right)-2\gamma \left(\left(i\delta ,i\delta \left(1-\epsilon \right)+\theta \right]\right)+\frac{2\theta \cdot \gamma \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)}{\delta \left(1-\epsilon \right)}\\ \ge \gamma \left(I\right)-2\gamma \left(\left(i\delta ,i\delta +\theta \right]\right)+\frac{2\theta \cdot \gamma \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)}{\delta \left(1-\epsilon \right)}\\ \ge \gamma \left(I\right)-2\theta \gamma \left(0\right)+\frac{2\theta \cdot \delta \cdot \gamma \left(0\right)\cdot \left(1-\alpha \right)}{\delta \left(1-\epsilon \right)}\\ =\gamma \left(I\right)+\frac{2\theta \gamma \left(0\right)}{1-\epsilon }\cdot \left(\epsilon -\alpha \right)\ge \gamma \left(I\right).\end{array}$

对于${\alpha }^2\le 2\epsilon$ ，证毕。

现在我们来给出引理2.2的证明

证明.

显然，由假设，$\mu ,v,\gamma$ 都是单峰的，而单峰分布的乘积分布依旧是单峰分布，则由如上引理并反复应用Kanter引理，最后我们有${\mu }^k\underset{\_}{\prec }{\gamma }^k\underset{\_}{\prec }{\nu }^k$ ，因此对于任意的半范数$\phi$ ，

$\underset{{\mu }^k}{\mathbb{E}}\left[\phi \left(X\right)\right]\ge \underset{{\gamma }^k}{\mathbb{E}}\left[\phi \left(Y\right)\right]\ge \underset{v^k}{\mathbb{E}}\left[\phi \left(X\right)\right]=\underset{{\mu }^k}{\mathbb{E}}\left[\phi \left(\left(1-\epsilon \right)X\right)\right]=\left(1-\epsilon \right)\underset{{\mu }^k}{\mathbb{E}}\left[\phi \left(X\right)\right]$

最后我们给出，本文主要结果定理1.3的证明。

证明.

令$\widehat{\mu }$ 是$\delta \left(\mathbb{Z}+1/2\right)$ 上的对称分布，定义如下，对于$i\ge 0$ ，

$\widehat{\mu }\left(\delta \left(i+1/2\right)\right)=\mu \left(\left[i\delta ,\left(i+1\right)\delta \right)\right)$

再令$X\leftarrow {\mu }^k,\widehat{X}\leftarrow {\widehat{\mu }}^k,Z\leftarrow {\mathcal{N}}^k$，我们首先往证$\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]=\left(1\pm \epsilon \right)\mathbb{E}\left[\phi \left(Z\right)\right]$ ，令Y是${\left[-\delta ,\delta \right]}^k$ 上的均匀分布，并且观察到$X\equiv \widehat{X}+Y$ ，因此我们有

$\begin{array}{c}\mathbb{E}\left[\phi \left(X\right)\right]=\mathbb{E}\left[\phi \left(\widehat{X}+Y\right)\right]=\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]\pm \mathbb{E}\left[\phi \left(Y\right)\right]\\ =\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]\pm \delta \mathbb{E}\left[\phi \left(Y/\delta \right)\right]\\ =\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]\pm \delta \underset{Z^{\prime }{\in }_u{\left[-1,1\right]}^k}{\mathbb{E}}\left[\phi \left(Z^{\prime }\right)\right]\\ =\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]\pm \delta \mathbb{E}\left[\phi \left(Z\right)\right] \end{array}$

最后一个等式是由于Y是均匀分布，从Kanter引理和单峰的性质而来。

因此由于引理2.5，我们有

$\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]=\left(1\pm O\left(\epsilon \right)\right)\mathbb{E}\left[\phi \left(Z\right)\right]$ 。

我们接下来处理${\widehat{\mu }}^k$ ，由$p\left(x\right)={\widehat{\mu }}^k\left(x\right)$ 定义$p:{ℝ}^k\to {ℝ}_{+}$ ，此处显然，$p\left(x\right)$ 是一个可以在poly $\left(k,1/\epsilon \right)$ 时间内遍历的乘积分布。

再令区间$S={\left(\delta \left(\mathbb{Z}+1/2\right)\right)}^k\cap B_2\left(3\sqrt{k}\right)$ ，其中$B_2\left(r\right)\subseteq {ℝ}^k$ 表示半径为r的欧式球，由于半范数$\phi$ 的Lipschitz常数被$k^{O\left(1\right)}$ 控制，所以我们在$\widehat{X}$ 的支撑之外丢弃所有的点不会对$\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]$ 产生很大影响，并且由次指数分布的定义，可以很容易看出对于$x\notin S$ ，有着$p\left(x\right)\le \text{exp}\left(-{\Vert x\Vert }_2^2/4\right)/{\left(2\pi \right)}^{k/2}$ ，因此，

$\begin{array}{c}\mathbb{E}\left[\phi \left(\widehat{X}\right)\right]={\displaystyle \sum }_{x}p\left(x\right)\phi \left(x\right)={\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)+{\displaystyle \sum }_{x\notin S}p\left(x\right)\phi \left(x\right)\\ ={\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)\pm {\displaystyle \sum }_{x\notin S}\frac{\text{exp}\left(-{\Vert x\Vert }_2^2/4\right)}{{\left(2\pi \right)}^{k/2}}\cdot \left(k^{O\left(1\right)}{\Vert x\Vert }_2\right)\\ ={\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)\pm o\left(1\right).\end{array}$

由于归一化假设$\mathbb{E}\left[\phi \left(Z\right)\right]\ge 1$ ，集合这几个等式，我们立刻有

$\mathbb{E}\left[\phi \left(Z\right)\right]=\left(1\pm O\left(\epsilon \right)\right)\left({\displaystyle \sum }_{x\in S}p\left(x\right)\phi \left(x\right)\right),$

我们现在考虑集合S的复杂度，这涉及到单纯的体积计算，

$\frac{\text{Vol}\left(B_2\left(3\sqrt{k}\right)+{\left[-\delta ,\delta \right]}^k\right)}{\text{Vol}\left({\left[-\delta ,\delta \right]}^k\right)}={\left(1/\delta \right)}^{O\left(k\right)}={\left(1/\epsilon \right)}^{O\left(k\right)}$

其中对于集合$A,B\subseteq {ℝ}^k$ ，$A+B$ 表示其Minkowski和，而Vol表示其Lebesgue体积，不失一般性，我们假设$R=3\sqrt{n}/\delta$ 是个整数，那么枚举集合S中的元素相当于，按照顺序枚举半径为R的n维球的整数点，这可以通过遍历S中的格点来完成，S中的每个点需要poly $\left(k,1/\epsilon \right)$ 时间以及$O\left(k\log \left(1/\epsilon \right)\right)$ 的空间，证毕。

4. 总结

本文通过假设次指数过程的概率密度函数为对称单峰，从而运用降维技术在低维空间得到了一个多项式时间内的逼近算法，来近似这类次指数过程的上确界的期望。而以往的经典的方法在处理这类上界时，一般根据次指数过程的定义，放缩为高斯过程的尾概率，随后通过占优测度定理获得，由于占优测度定理会忽略掉一个通用常数，我们的结果显然是更紧致的，而对于一般的次指数过程，如何一个紧致的上界，是一个很有趣的问题，我们将考虑在之后的工作中解决。

基金项目

山东省自然科学基金(ZR2023QA033)一类抛物型积分微分方程的高阶差分方法；山东大学实验研究项目(sy20233204)机器学习与微分方程实验教学课程研究。