Computational Concentration of Measure: Optimal Bounds, Reductions, and More

Product measures of dimension n are known to be "concentrated" under Hamming distance. More precisely, for any set S in the product space of probability Pr[S] ≥ ε, a random point in the space, with probability 1 -δ, has a neighbor in S that is different from the original point in only O( n • ln( 1 /εδ)) coordinates (and this is optimal). In this work, we obtain the tight computational (algorithmic) version of this result, showing how given a random point and access to an S-membership query oracle, we can find such a close point of Hamming distance O( n • ln( 1 /εδ)) in time poly(n, 1/ε, 1/δ). This resolves an open question of [MM19] who proved a weaker result (that works only for ε ≫ 1/ √ n). 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 (short for "MUltiplicative Conditional Influence Optimizer") since proceeding through the coordinates of the product space, it decides to change each coordinate of the given point based on a multiplicative version of the influence of a variable, where the influence is computed conditioned on the value of all previously updated coordinates. MUCIO is an online algorithm in that it decides on the i'th coordinate of the output given only the first i coordinates of the input. It also does not make any convexity assumption about the set S.

Motivated by obtaining algorithmic variants of measure concentration in other metric probability spaces, we define a new notion of algorithmic reduction between computational concentration of measure in different probability metric spaces. This notion, whose definition has some subtlety, requires two (inverse) algorithmic mappings one of which is an algorithmic Lipschitz mapping and the other one is an algorithmic coupling connecting the two distributions. As an application, we apply this notion of reduction to obtain computational concentration of measure for high-dimensional Gaussian distributions under the ℓ 1 distance.

We further prove several extensions to the results above as follows. (1) Generalizing in another dimension, our computational concentration result is also true when the Hamming distance is weighted.

(2) As measure concentration is usually proved for concentration around mean, we show how to use our results above to obtain algorithmic concentration for that setting as well. In particular, we prove a computational variant of McDiarmid's inequality, when properly defined. (3) Our result generalizes to discrete random processes (instead of just product distributions), and this generalization leads to new tampering algorithms for collective coin tossing protocols. (4) Finally, we prove exponential lower bounds on the average running time of non-adaptive query algorithms for proving computational concentration for the case of product spaces. Perhaps surprisingly, such lower bound shows any efficient algorithm must query about S-membership of points that are not close to the original point even though we are only interested in finding a close point in S.