Voices of CS: Yizhi Huang on Nasty Noise versus Malicious Noise

Machine learning systems often assume that the data they learn from is mostly trustworthy. But what happens when that data is deliberately corrupted?

In their paper “Is Nasty Noise Actually Harder Than Malicious Noise?” CS researchers explored this question by comparing two adversarial noise models that capture different kinds of data corruption: malicious noise, where an attacker corrupts a random portion of the dataset, and nasty noise, where the attacker strategically chooses exactly which examples to manipulate.

At first glance, nasty noise seems obviously worse. Yet Yizhi Huang, who worked with Professors Tal Malkin and Rocco Servedio, and Guy Blanc from Stanford University on the research, shows that the answer is more nuanced. Depending on how a learning algorithm interacts with the data distribution, the two noise models can behave either almost the same or dramatically different. Their work uncovers surprising theoretical connections between machine learning, cryptography, and algorithm design, while also shedding light on modern concerns such as data poisoning attacks. 

Building on these insights and recognizing its impact, the work was honored with a Best Paper award at the ACM-SIAM Symposium on Discrete Algorithms (SODA26). The following Q&A explores the key ideas behind the paper and what they reveal about the limits of robust learning.

Q: What is the core idea of this paper, and why does it matter?

Adversarial noise in data used for machine learning, and the related “data poisoning attack”, have been the subject of much ongoing research in machine learning. We study the relative abilities and limitations of efficient algorithms for learning under two different adversarial noise models, namely malicious noise and nasty noise (which differ in the adversary’s ability to select which part of data to corrupt; adversary is more powerful in nasty noise). We show different results in two different settings (whether the distribution to draw data from is fixed): in one setting (fixed-distribution), it is more difficult to learn under nasty noise than malicious noise, while in the other setting (distribution-free), the difficulty to learn under the two noise models are essentially the same.

Q: Who is this research really for, and how might it be used?

Our result may be used in further theoretical study of noise in data in machine learning. Our study is based on an idealized model of learning, so it might not have a direct impact on empirical machine learning research, but it could provide some theoretical perspective.

Q: How do “malicious” and “nasty” noise connect to real-world data poisoning attacks?

In general, these noise models may be used to characterize certain types of “data poisoning attack” in the real world.

To be more specific, the malicious noise and nasty noise models can be understood as follows. Suppose we have a clean data set. A malicious adversary can add extra corrupted data to the data set, but cannot remove (or modify) any existing clean data (and the difficulty for the learner comes from not knowing which data are clean and which are corrupted). In contrast, a nasty adversary can remove (or modify) data from the data set in addition to adding corrupted data (and the difficulty for the learner may also come from the clean data being unrepresentative as some are removed).

So, malicious noise can characterize a situation where one collects data from different sources, among which some are reliable, but some others intentionally provide corrupted data to reduce the quality of the machine learning model trained on the data. On the other hand, nasty noise can characterize a situation where one trains a machine learning model based on data from one source, but that source selectively withholds or changes some of the data in order to reduce the quality of the model.

Q: What makes this result interesting, and who in the field should care most?

I think it would be interesting for machine learning theory researchers, especially those who study computational learning theory. Before this, I think we didn’t know a lot about the nasty noise model in general—there are people studying nasty noise for efficiently learning specific functions, but there were few general results that hold for every Boolean function.

Q: Does this research have any practical impact beyond theory, or is it mainly conceptual?

We study the problems in an idealized model called PAC (Probably Approximate Correct) learning, which is commonly used for the theoretical analysis of machine learning algorithms but makes strong (and arguably unrealistic) assumptions on the data. In particular, it assumes that each piece of data is independently sampled from the same distribution, and most real-life data do not satisfy this assumption.

Some other catches for our results: For the distribution-free setting, we showed that if a function can be efficiently learned under malicious noise, then it can also be efficiently learned under nasty noise. However, there is a polynomial overhead in the size of the data set needed for the learning algorithm under nasty noise. In theory research, we are mostly happy with polynomial overhead, but in practice that could mean far more data. And for the fixed-distribution setting, we construct a function that can be efficiently learned under malicious noise but not under nasty noise, but that function is unnatural. So, it is still possible that in this setting, for “natural” functions, learning under nasty noise is not much harder than learning under malicious noise.

With all this said, I believe theoretical research may still bring some insight to the actual practice.