计算的度量集中度：最佳界限，减少量等

作者：Omid Etesami,Saeed Mahloujifar,Mohammad Mahmoody

摘要：已知维度的乘积度量集中在汉明距离：对于任何集合，在概率ε的乘积空间中，空间中的随机点，概率为1-δ，其邻域与唯一的原点不同（nln（1 / （εδ））---------√）坐标。我们得到了这个结果的严格计算版本，显示了如何给定一个随机点和访问一个s-membership oracle，我们可以在多项式时间内找到这样一个接近点。这解决了[Mahloujifar和Mahmoody，ALT 2019]的一个悬而未决的问题。作为推论，当原始漏洞具有任何加密不可忽略的概率时，我们获得多项式时间中毒和（在某些情况下）对学习算法的规避攻击。

我们将算法称为MUCIO（“多重条件影响优化器”），因为它继续通过坐标，它决定根据该坐标影响的乘法版本改变给定点的每个坐标，其中影响是根据先前更新的坐标计算的。

我们还定义了在不同度量概率空间中度量的计算集中度之间的算法减少的新概念。作为一个应用，我们得到了在l1metric下高维高斯分布的度量计算集中。

我们证明了上述结果的几个扩展：（1）当汉明距离加权时，我们的计算集中结果也是如此。 （2）我们获得了一个围绕均值的浓度算法版本，更具体地说，是McDiarmid的不等式。 （3）我们的结果推广到离散随机过程，这导致了集体抛硬币协议的新篡改算法。 （4）我们证明了非自适应查询算法平均运行时间的指数下界。

原文标题：Computational Concentration of Measure: Optimal Bounds, Reductions, and More

原文摘要：Product measures of dimensionnare known to be concentrated in Hamming distance: for any setSin the product space of probabilityϵ, a random point in the space, with probability1−δ, has a neighbor inSthat is different from the original point in onlyO(nln(1/(ϵδ))−−−−−−−−−√)coordinates. We obtain the tight computational version of this result, showing how given a random point and access to anS-membership oracle, we can find such a close point in polynomial time. This resolves an open question of [Mahloujifar and Mahmoody, ALT 2019]. As corollaries, we obtain polynomial-time poisoning and (in certain settings) evasion attacks against learning algorithms when the original vulnerabilities have any cryptographically non-negligible probability.

We call our algorithm MUCIO ("MUltiplicative Conditional Influence Optimizer") since proceeding through the coordinates, it decides to change each coordinate of the given point based on a multiplicative version of the influence of that coordinate, where influence is computed conditioned on previously updated coordinates.

We also define a new notion of algorithmic reduction between computational concentration of measure in different metric probability spaces. As an application, we get computational concentration of measure for high-dimensional Gaussian distributions under theℓ1metric.

We prove several extensions to the results above: (1) Our computational concentration result is also true when the Hamming distance is weighted. (2) We obtain an algorithmic version of concentration around mean, more specifically, McDiarmid's inequality. (3) Our result generalizes to discrete random processes, and this leads to new tampering algorithms for collective coin tossing protocols. (4) We prove exponential lower bounds on the average running time of non-adaptive query algorithms.

地址：https://arxiv.org/abs/1907.05401