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

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.