We approach the following two fundamental problems in deep learning: (a) how can over-parameterized models generalize well in neural networks? (b) how does deep learning achieve the robustness against adversarial samples?
For problem (a), Max-Margin has been an important strategy since perceptrons in machine learning for the purpose of boosting the robustness of classifiers toward a good generalization ability, which experienced a renaissance lately to explain the success in deep learning. However, Leo Breiman pointed out a dilemma in 1999 that margin increase over training data results in a decrease in generalization performance, that will be shown ubiquitous in neural networks as well. In particular, we propose a new method to explain the mechanism of Breiman’s Dilemma, using phase transitions of normalized margin dynamics.
For problem (b), we revisit Huber’s contamination model in robust statistics, from a perspective of generative adversarial networks (GAN). When the outlier examples are fully agnostic in distributions, GANs are shown in both theory and experiment to achieve robust estimates at information-theoretically optimal rates, equivalent in statistical precision to the Tukey median estimate that is NP-hard to compute though. GANs may have wider adaptation than other polynomial algorithms proposed lately based on moment methods. Hence, by playing some zero-sum differential games, GANs provides us provable guarantees on robustness under Huber’s model.