Abstract
Product measures of dimension $n$ are known to be concentrated in Hamming distance: for any set $S$ in the product space of probability $\epsilon$, a random point in the space, with probability $1-\delta$, has a neighbor in $S$ that is different from the original point in only $O(\sqrt{n\ln(1/(\epsilon\delta))})$ coordinates. We obtain the tight computational version of this result, showing how given a random point and access to an $S$-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 $\ell_1$ metric. 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.
Introduction
The "Concentration of Measure" (CoM) phenomenon is a cornerstone of modern probability theory, particularly in high-dimensional spaces. It suggests that in a product space of dimension $n$, any set $S$ with non-negligible probability $\epsilon$ is "close" to almost every point in the space. Specifically, for a random point, there exists a neighbor in $S$ within a Hamming distance of $O(\sqrt{n\ln(1/(\epsilon\delta))})$ with probability $1-\delta$.
While mathematicians have long known that these neighbors exist, traditional proofs are information-theoretic and non-constructive. They guarantee the existence of such neighbors without providing a method to find them. This paper bridges the gap between pure probability and computer science by introducing the first optimal polynomial-time algorithm to find these neighbors, transforming a "paper tiger" existence proof into a practical computational tool.
The MUCIO Algorithm
The core contribution of this work is the MUltiplicative Conditional Influence Optimizer (MUCIO). Previous attempts to find neighbors in $S$ often relied on additive updates to probability, which fail to make progress when the target set $S$ is very small. MUCIO overcomes this by focusing on multiplicative influence.
Key Mechanics
- Online Processing: MUCIO is an "online" algorithm that processes coordinates one by one. For each coordinate, it decides whether to keep the original value or change it to a value that maximizes the conditional probability of ending up in $S$, based on the changes made so far.
- Multiplicative Gain: Instead of looking at how much a change increases the absolute probability of hitting $S$, MUCIO maximizes the multiplicative increase in conditional probability (related to log-likelihood ratios). This ensures the algorithm maintains progress even when the initial probability $\epsilon$ is cryptographically small.
- Potential Function Analysis: The efficiency of MUCIO is proven using a potential function analysis, demonstrating that the algorithm converges to a neighbor in $S$ within the optimal Hamming distance bounds in $poly(n, 1/\epsilon, 1/\delta)$ time.
Algorithmic Reductions and Extensions
Beyond the Hamming cube, the authors introduce a framework for algorithmic reductions. This allows computational concentration results to be transferred between different metric probability spaces using "algorithmic Lipschitz mappings."
- Gaussian Distributions: By applying their reduction framework, the authors achieve the first computational concentration results for high-dimensional Gaussian distributions under the $\ell_1$ metric.
- Weighted Hamming Distance: The results extend to scenarios where different coordinates have different "costs" or weights, proving the algorithm's versatility.
- Discrete Random Processes: The algorithm generalizes to discrete processes, enabling new tampering strategies for collective coin-tossing protocols.
Security Implications: Poisoning and Evasion
The computational feasibility of finding "close" neighbors directly translates to vulnerabilities in machine learning and security. If a vulnerability exists with even a tiny (but non-negligible) probability, an attacker can use MUCIO to efficiently find a nearby "adversarial example" to exploit it.
- Poisoning Attacks: The paper demonstrates that learning algorithms can be "poisoned" in polynomial time. An attacker can find a small set of training data perturbations that force a model to adopt a "bad" hypothesis, even if the initial probability of such a failure was low.
- Evasion Attacks: In specific settings, MUCIO allows an attacker to efficiently find adversarial examples—minimal perturbations to an input that cause a classifier to misidentify it—by treating the set of misclassified points as the target set $S$.
The Necessity of Adaptivity
A significant theoretical finding is the proof of an exponential lower bound for non-adaptive query algorithms. Any algorithm that decides which coordinates to change before seeing any results is doomed to fail; they would take exponential time to find the same neighbors that MUCIO identifies in polynomial time. This highlights that MUCIO’s adaptive, conditional approach is not just an implementation choice, but a requirement for computational efficiency in high-dimensional concentration.
Conclusion
By providing a constructive, polynomial-time algorithm for the Concentration of Measure, this research establishes that "robustness" in high-dimensional systems is harder to achieve than previously thought. If a target set is reachable in principle, MUCIO proves it is reachable in practice, provided the attacker has oracle access to the target set membership.
Summary updated