Abstract
This manuscript presents some new results on adversarial robustness inmachine learning, a very important yet largely open problem. We show that ifconditioned on a class label the data distribution satisfies the generalizedTalagrand transportation-cost inequality (for example, this condition issatisfied if the conditional distribution has density which is log-concave),any classifier can be adversarially fooled with high probability once theperturbations are slightly greater than the natural noise level in the problem.We call this result The Strong "No Free Lunch" Theorem as some recent results(Tsipras et al. 2018, Fawzi et al. 2018, etc.) on the subject can beimmediately recovered as very particular cases. Our theoretical bounds aredemonstrated on both simulated and real data (MNIST). These bounds readilyextend to distributional ro- bustness (with 0/1 loss). We conclude themanuscript with some speculation on possible future research directions.