Smoothed Analysis [Translation]

我的经验总是不断证实我之前的观点：最好的理论总是从实践中得到灵感，最好的实践总是来源于理论。
————Donald E. Knuth, “Theory and Practice”,
Theoretical Computer Science, 1991.

算法是用来详细描述计算任务的方式。工程师和实验者设计和应用算法，并且归纳的思考算法是否会在工作和实践中取得成功。然而，一个工作的很好的算法并不一定能在另一个地方表现的很好。带着为了提供有理论保证的算法的目的，理论科学家同样设计和分析算法。传统的理论计算机科学试图证明一个算法在最坏情况下表现优异：如果一个算法可以被证明在最坏情况下表现优异，那么这种算法可以被自信的运用于每一个可以运用的领域。然而，有很多算法可以在实践中工作的很好，但是并不能在最坏情况下有好的表现。平滑分析提供了一种理论框架去解释为什么这些算法可以在实践中工作的很好。

衡量算法的标准往往是一个算法的运行时间，表现为一个函数解决一定规模的输入。一个算法需要面对差异巨大的输入，有些可以非常的不规则。一些算法可以在线性的时间里解决所有输入，一些需要花费平方级别乃至更高的多项式的时间，而有些则需要花费指数级别的时间解决问题。

传统上，一个算法的时间复杂度是通过算法在最坏情况下的表现来确定的。如果一个输入能够触发算法指数级别的运行时间，这个算法就会被称作指数级的算法。一个多项式级别的算法会在所有输入下通过多项式级别的时间去解决问题。多项式级的算法大多被视为高效的，我们跟喜欢花费时间在多项式级别、甚至线性的算法。

如果所有算法都可以很快的在多项式级别内出解，那将是很完美的。但是在很多情况下，一个不足够好的算法在理论评估和实际表现上差异巨大。

一般人普遍相信在实践中的输入往往是比最坏情况下的例子更重要的。举个例子，很有名的Knapsack问题，这个问题是指，对于$n$个数，是否能够分成两个和相等的部分，这个问题没有多项式算法，除非NP=P。NBC著名新闻评论员Tim Russert在2008大选的时候提出了共和党和民主党候选人有最后同票的可能。也就是说，他解决了51个元素（TIP：美国有51个州）的Snapsack问题，而且是在很短的时间内通过手动计算得到的，也就是说这很可能没有使用我们熟知的“伪多项式动态规划”（TIP：即背包问题，背包问题的复杂度与元素大小有关，称之为“伪多项式”算法）解决了Knapsack问题！

另外，著名的单纯形（Simplex）算法是一个经典的例子，单纯形算法在在实践的时候表现的非常好，但是在最坏情况下表现的很差。单纯形算法解决了线性规划问题，举个例子，对于以下公式：

$$\max {\bf c}^T{\bf x}~~\text{subject to}~~{\bf Ax}\leqslant {\bf b}$$

其中$A$是一个$m\times n$的矩阵，$b$是一个长度为$m$的向量，而$c$是一个长度为$n$的向量。在最坏情况下，单纯形算法需要指数级的时间。

算法的行为

假设$A$是一种算法，用来解决问题$P$，我们让$T_A[{\bf x}]$来表示算法$A$在输入为${\bf x}$时运行时间。然后我们可以用基于输入的衡量方法$T_{A_1}[{\bf x}]$和$T_{A_2}[{\bf x}]$来决定$A_1$和$A_2$两个算法哪一个更加高效。

假设$\Omega$表示两个输入$\bf x$和$\bf y$，然后基于输入的衡量方法对于$A$决定了一个二维向量$(T_{A}[{\bf x}],T_{A}[{\bf y}])$。可能会出现$T_{A_1}[{\bf x}]<T_{A_2}[{\bf x}]$但是 $T_{A_1}[{\bf y}]>T_{A_2}[{\bf y}]$。

然而，严格的来说，这两种算法并不能比较。更多时候，输入应该更多更复杂一些。这种instance-based complexity measure $T_A[\cdot]$决定了一个$|\Omega|$维的向量（当$\Omega$是有限的时候）。更一般的，可以看作一个函数从$\Omega$映射到${\bf R}_+^1$，但是很粗糙。为了比较两个算法，我们需要一些更加精确复杂度测量方法。

一个输入域$\Omega$经常被看作一些子域的合集的并集$\{\Omega_1,...,\Omega_n,...\}$，这里$\Omega_n$代表所有在$\Omega$中规模为$n$的输入。举个例子，在排序中，$\Omega_n$是所有$n$个元素的合集；在图论算法中，$\Omega_n$则是所有大小大为$n$的图。为了简洁的表述算法$A$在$\Omega_n$下的表现，我们定义$T_A(n)$表示囊括了所有instance-based complexity measure $T_A[\cdot]$在$\Omega_n$下的值。一个更加简化的表述是用big-O或者big-$\Theta$来表示$T_A(n)$的渐进值。

传统的分析

我们可以理解，对于不同的方法，估计出来的在$\Omega_n$下算法的表现是不一样的。在理论计算机科学中，最普通的方法是测量算法在最坏情况下的水平和在平均情况下的水平。

最坏情况下的测量定义如下：

$$WC_A(n)=\max_{x\in \Omega_n}{T_A[{\bf x}]}$$

至于平均情况下的测量则需要更多的参数。在每个平均情况下的测量，首先要确定输入的分布，假设输入服从这样的分布，然后测量算法的期望表现。令$S$表示每个$\Omega_n$的分布，那么依据$S$平均情况下测量的定义如下：

$$Ave_A^S(n)=E_{x\in_S\Omega_n}[T_A[{\bf x}]]$$

其中我们用${\bf x}\in_S\Omega_n$表示$\bf{x}$是在$\Omega_n$中依据$S$随机选取的。

传统的分析的不足之处

低的最坏复杂度是一个算法重要标准。当最坏复杂度很低的时候，它保证了算法的表现在任何输入下都会很好。有一个在最坏情况下表现很好的算法解决了很多的问题。

然而，依旧有很多问题需要被解决在实际中，而这些问题我们不知道有很好的最坏复杂度的算法。取而代之的是很多科学家和工程师选择了启发式的算法去解决这些问题。很多这些算法在实际中工作的很好，尽管有一些情况下他们工作的不好，甚至是指数级的。

为了克服这种困难，平均情况下的分析被提了出来。在平均情况分析下， 一个算法的期望运行时间被计算了出来。但是这需要拥有读入数据非常理想的分布，很多情况下这是很困难的，而且这种分布在不同应用下通常是差别很大的。

平滑分析：对实际数据建立模型

由于决定实际分布是十分困难的，我们选择另一种方式去对实际数据建立模型。其中比较基础的idea是识别实际数据的特性，确定一个识别这些特性并严密地分析算法在这些输入下的表现的输入模型。

平滑分析向这一方向迈出了一步，它观察到实际数据通常会受到一些随机噪声的影响。

【三个例子】

严格地说，每个输入的生成经过了一个有两个阶段的模型：在第一个阶段，一个数据生成，在第二个阶段，这个数据收到了一些轻微扰动。这个经受过扰动的数据最后作为算法的输入。

因此在平滑分析中，我们假设一个算法的输入受到了随机的扰动。定义平滑测量(smooted measure)表示在扰动数据下的期望表现。定义平滑复杂度（smoothed complexity）表示所有的输入数据中平滑测量的最大值。

具体而言，考虑这样的情况$\Omega_n={\bf R}^n$，也计算几何中的输入相同。对这样的连续的输入和应用，高斯分布（也就是正态分布）提供了噪声或扰动的分布。

回忆单因子高斯分布（也就是平均值$\mu=0$，标准差$\sigma$不确定）：

$$\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}}$$

其中标准差衡量了扰动的程度。对于一个向量$\bar {\bf x}\in {\bf R}^n$，经过高斯扰动后的向量${\bf x}={\bf\bar x}+{\bf g}$，其中$g$是一个方差为$\sigma$的高斯随机向量。

定义1(Smoothed Complexity平滑复杂度，下称SC). 假设$A$是一个输入为$\Omega_n={\bf R}^n$的算法。那么算法$A$在$\sigma$-Gaussian扰动下的Smoothed Complexity为

$$Smoothed^\sigma_A(n)=\max_{\bar x\in [-1,1]^n}{\textbf{E}_g[T_A({\bf \bar x}+{\bf g})]}$$

其中$g$是一个方差为$\sigma$的高斯随机向量。这个最大值是最坏初始输入下的期望效率。

SC衡量了一个算法在大小为$n$、扰动程度为$\sigma$的数据下的表现。通过改变$\sigma$从0到无穷，我们可以利用平滑分析计算最坏情况和平均情况之间的情况。当$\sigma=0$的时候，这个式子就是最坏情况下的分析。当$\sigma$不断变大，式子就变了平均情况下的分析。但我们通常更关心$\sigma$相对于$||{\bf \bar x}||$较小的情况，这样${\bf \bar x}+{\bf g}$会被看作$\bf \bar x$的轻微扰动。对$\sigma$的依赖非常重要，在工作中经常会显示出噪音会让问题变得更容易解决。

定义2(Polynomial smoothed complexity多项式平滑复杂度，下称PSC). 如果存在正常量$n_0,\sigma_0,c,k_1,and~k_2$满足$\forall n\geqslant n_0~and~0\leqslant\sigma\leqslant\sigma_0$,

$$Smoothed^\sigma_A(n)\leqslant c\cdot\sigma^{-k_2}\cdot n^{k_1}$$

通过马尔可夫不等式，如果一个算法$A$有平滑复杂度$T(n,\sigma)$，那么

$$\max_{\bar x\in[-1,1]^n}{\textbf{Pr}_g[T_A({\bf \bar x}+{\bf g})}\leqslant \delta^{-1}T(n,\sigma)]\geqslant 1-\delta$$

因此，如果算法$A$有PSC，那么对于任意$\bf\bar x$，有至少$(1-\delta)$的概率能在带有随机扰动的输入下在多项式参数为$n,\frac{1}{\sigma},\frac{1}{\delta}$的时间内解决问题。然而这并不意味$A$的SC就是$O(T(n,\sigma))$。Blum和Dunagan以及接下来的Beier和Vöcking提出了PSC的松散形式。

定义3(Probably polynomial smoothed complexity，下称PPSC). 如果存在正常量$n_0,\sigma_0,c,a$满足$\forall n\geqslant n_0~and~0\leqslant\sigma\leqslant\sigma_0$,

$$\max_{\bar x\in[-1,1]^n}{\textbf{E}_g[T_A({\bf \bar x}+{\bf g})^\alpha]}\leqslant c\cdot\sigma^{-1}\cdot n$$

这表明，尽管定义1表明他们的复杂度是无界的，但是一些算法可能具有PPSC。

平滑分析的例子

在这一部分，我们会给出一些平滑分析的例子。我们组织了五个部分：数学规划，机器学习，数值分析，离散数学以及组合优化。对于每个例子，我们会给出问题的定义，陈述最坏复杂度，解释扰动模型，并且陈述在扰动模型下的SC。

数学规划

一个数学规划中的典型问题是在一系列约束下寻找一个函数的最优解。由于这个问题在经济学、工业和军事计划很重要，很多最优算法和启发式算法得到了发展，并且应用在实际问题中。因此，这个领域提供了大量算法去应用平滑分析。

线性规划

线性规划是最基础的最优化问题。最常用来解决线性规划问题的算法是Simplex单纯形算法以及内点算法。

单纯形算法，由Dantzig在1951年第一次提出，属于迭代算法。大部分迭代算法有两个部分（TIP：实际上在介绍单纯形算法）：第一部分是确定给出的线性程序是否不可行，在目标方向无界，或者可行，在目标方向有界（TIP：就是判断最优值是否存在），在这种情况下，在合法区域上的某个顶点$v_0$会被计算出来。第二部分是迭代的：在第$i$次迭代中，算法会去寻找顶点$v_{i-1}$的相邻顶点$v_i$，其中$v_i$顶点有着更优的目标值。当不存在更优的相邻顶点的时候，算法终止并返回$v_{i-1}$。一些单纯形算法在转轴(pivot)操作上不一样，当有多个相邻顶点比当前顶点更优的时候。一些转轴策略已经被提出。然而几乎所有现存的转轴策略在最坏情况下都是指数复杂度的！

Spielman和Teng思考了应用shadow-vertex转轴策略的单纯形算法的SC，并由Gass和Saaty发展。他们使用了高斯扰动模型去生成输入数据，并且证明了这种算法的SC是多项式级别的。Vershynin改进了他们的结果，其中SC是

$$O(\max\{n^5\log^2m,n^9\log^4n,n^3\sigma^{-4}\})$$

之后Blum和Dunagan分析了其他线性规划算法例如内点算法以及感知器算法。

Quasi-Concave Minimization(QCM)

另一个基本的最优化问题是QCM。定义函数$f:\textbf{R}^n\rightarrow \textbf{R}$是伪凹的（quasi-concave，下称QC函数），当且仅当$\forall \gamma$，${\bf L}_\gamma=\{x|f(x)\geqslant \gamma\}$是凸集。在QCM中，要求出最小的QC函数使得满足一些线性约束。即使限制都是在超立方体上的凹二次函数，QCM依旧是NP-hard问题。

在应用中，诸如随机和多目标优化（多用来解决低维子空间上的问题）。也就是说，我们需要用low-rank的QC函数去解决QCM问题。对于rank为$k$的QC函数$f:\textbf{R}^n\rightarrow \textbf{R}$可以被写成

$$f(x)=g(a_1^Tx,a_2^Tx,...,a^T_kx)$$

其中$a_1,a_2,...,a_k$是线性无关的。

Kelner和Nikolova证明了，在一些合法凸集上的温和的假设下，如果$k$是一个常数，且$f$经过一些扰动，那么QCM的SC是多项式级别的。分析的关键是高维多面体的$k$维投影大小上的平滑界限，其定义了可行的凸集。他们（Kelner, Spielman, Spielman and Teng）的结论是分析二维投影的平凡拓展后得到的。

机器学习

机器学习为平滑分析提供了很多自然的问题。许多启发式算法在实践中都很有效，但是在最坏情况下表现的不好，然而大多数机器学习问题的数据本身就有很多噪音。

K-means

机器学习的一个基本问题时k-means分类：把一个$d$维向量集合$Q=\{q_1,...,q_n\}$分成$k$个集合$\{Q_1,...,Q_k\}$，要求集合内方差

$$V=\sum_{i=1}^{k}\sum_{q_j\in Q_i}{||q_j-\mu(Q_i)||^2}$$

最小化，其中$\mu(Q_i)$为$Q_i$的平均数。

一个被广泛应用的算法是Lloyd算法(IEEE Transaction on Information Theory, 1982)。流程如下：首先任选$k$个节点作为$k$个集合的中心，然后用建立V图（TIP：将平面氛围$k$块，每块包含一个中心，每块中的任意一点到该块中心的距离比到其他块中心的距离都要短），然后对于每一块找到$Q$中所有属于这一块的点，找到它的中心点$\mu(Q_i)$，重新做一遍V图，一直迭代下去。

对于这个算法，有两个问题，第一个就是，需要迭代多少次才能到停止？第二个就是，这个算法找到的解有多优？平滑分析曾被用来分析第一个问题。Arthur和Vassilvitskii证明了在最坏情况下，Lloyd算法需要$2^{\Omega(\sqrt{n})}$次迭代。但是SC是多项式级别的：$\max\{n^k,\sigma_{-1}\}$。Manthey和Röglin最近把这个上界缩小到了$\max\{n^{\sqrt{k}},\sigma^{-1}\}$。

感知器、间隔、以及支持向量机

Blum和Dunagan对感知器的线性规划算法的分析隐含了对机器学习的兴趣。最普通的感知器解决了一个基本问题：给出一些点$x_1,...,x_n\in \textbf{R}^d$和一些label $b_1,...,b_n\in\{\pm 1\}^n$，找到一个超平面把这些点分为两种label，或者确定不存在这样的超平面。在平滑模型下，$x_1,…,x_n$经过了$\sigma$-高斯扰动，Blum和Dunagan证明了感知器算法有SC是多项式级别的。他们的证明来自一个证明，即如果正面点可以与负面点分开，那么它们可能会被很大的间隔分离。 也就是说，可能存在一个平面，将没有点过于靠近分离平面的点分开。

众所周知，感知器算法在这种情况下很快收敛。 而且，这个间隔恰恰是支持向量机最大化的。

PAC Learning

Probably approximately correct learning (PAC learn- ing)是一个由Valiant提出的的机器学习模型，学习者被提供来自给定分布的标记示例的多项式数字，然后必须产生高正确率的分类器。在标准PAC learning中，绘制的示例分布是固定的。最近，Kalai和Teng对被扰动过的输入分布应用平滑分析。他们证明了在扰动的分布下，多项式级别的决策树可以被PAC在多项式时间内学会。相比之下，在不扰动的分布下，即使是常量大小的决策树，PAC也可能不能在多项式时间内学会。

组合最优化

Beier,Vöcking,Röglin考虑了整数线性规划的SC，也就是

$$\max {\bf c}^T{\bf x}~~\text{subject to}~~{\bf Ax}\leqslant {\bf b}~and~{\bf x}\in \mathcal{D}^n$$

其中$\bf A$是一个$m\times n$的实矩阵，${\bf b}\in {\bf R}^m$，并且$\mathcal{D}\subset {\bf Z}$.

讨论

平滑分析的主题

有一个观点普遍出现在了很多平滑分析中：扰动的输入很少有病态（构造）的数据。严格地说，一个问题的condition number衡量了答案在输入进行微小的改变下会改变多少。很多著名算法在好的数据下运行的很快。一些平滑的分析，比如Blum和Dunagan明确地利用了这种关系。很多人继承了这种方法。

对于很多问题，一个输入的condition number大约和输入和退化的数据的距离成反比。当退化数据在所有数据中占比很小（零测度）的时候，那么扰动数据不太可能会很接近退化数据，也是可以理解的。

其他Performance Measures

虽然我们通常通过一个算法的运行时间去考量它的表现，其他表现的因素也常常是很重要的。这些因素包括：空间需求，输出精度要求，缓存命中要求，算法的错误率，随机算法中需要随机多少位，对特定子程序的调用次数，以及在机器学习算法中对数据量的要求。近似算法是否优秀可能取决于它的近似率；一个在线算法是否优秀可能取决于它的（？）竞争比（competitive ratio）;我们预计会对这些Performance Measure进行平滑分析。

平滑分析的来源

很多之前的概率模型都结合了最坏情况和平均情况进行分析。

（？）Haimovich和Adler考虑了如下的概率分析：给出一个线性程序$\mathcal{L}=({\bf A},{\bf b},{\bf c})$，他定义$\mathcal{L}$的期望复杂度EC为每个约束条件的不等号均匀剔除时单纯形算法的预期复杂度。 他们证明了最坏情况下的L的预期复杂性是多项式。

对于特殊输入的算法设计和分析

概率方法不是表示实际输入的唯一方法。 很多工作花费了大量时间去设计和分析确定性的实际输入。我们将提到一些激发我们的例子。

In parallel scienti c computing, one may often assume that the input graph is a well-shaped nite element mesh. In VLSI layout, one often only considers graphs that are planar or nearly planar. In geometric modeling, one may assume that there is an upper bound on the ratio among the distances between points. In Web analysis, one may assume that the input graph satis es some powerlaw degree distribution or some small-world properties. When analyzing hash functions, one may assume that the data being hashed has some nonnegligible entropy.

平滑分析的局限性

平滑分析的目的是用来解释为什么一些算法在实际运用中的表现比在最坏情况下要好很多。但是并不能对所有的问题都给出非常好的解释，因为很难抓住输入实例的关键方面。

例如计算市场均衡问题，平滑复杂度和最坏复杂度基本一样。

因此，理解实际情况下算法行为的一个关键步骤是要建立一个可分析的模型，这个模型能够抓住实例输入的一些关键方面。

基于扰动和平滑分析的算法设计

希望这种扰动给算法设计带来一些灵感

例如在计算几何的某些算法中，通过实现可变精度算术，来正确处理由几何退化产生的异常。但是，这种退化情况通常只有极低概率才会发生。

一个例子：计算${\bf Ax}={\bf b}$

首先使用标准的列主元高斯消元法，得到结果$x^*$，如果$||{\bf b}-{\bf Ax}^*||$足够小，那么$x^*$即为所求

否则，我们可以设一个$\varepsilon$，产生一个新的线性系统$({\bf A}+ \varepsilon {\bf G}){\bf y}={\bf b}$，其中${\bf G}$是标准正态分布的矩阵。在$\varepsilon \ll \kappa({\bf 𝐴})$的情况下，那么这个线性系统的结果和原来的结果误差会在理想的范围之内。

---

$$\spadesuit$$