Abstract
Recently, Mahloujifar and Mahmoody (TCC'17) studied attacks against learning algorithms using a special case of Valiant's malicious noise, called -tampering, in which the adversary gets to change any training example with independent probability but is limited to only choose malicious examples with correct labels. They obtained -tampering attacks that increase the error probability in the so called targeted poisoning model in which the adversary's goal is to increase the loss of the trained hypothesis over a particular test example. At the heart of their attack was an efficient algorithm to bias the expected value of any bounded real-output function through -tampering. In this work, we present new biasing attacks for increasing the expected value of bounded real-valued functions. Our improved biasing attacks, directly imply improved -tampering attacks against learners in the targeted poisoning model. As a bonus, our attacks come with considerably simpler ana