The question why deep learning algorithms generalize so well has attracted increasing
 research interest. However, most of the well-established approaches,
 such as hypothesis capacity, stability or sparseness, have not provided complete
 explanations (Zhang et al., 2016; Kawaguchi et al., 2017). In this work, we focus
 on the robustness approach (Xu & Mannor, 2012), i.e., if the error of a hypothesis
 will not change much due to perturbations of its training examples, then it
 will also generalize well. As most deep learning algorithms are stochastic (e.g.,
 Stochastic Gradient Descent, Dropout, and Bayes-by-backprop), we revisit the robustness
 arguments of Xu & Mannor, and introduce a new approach – ensemble
 robustness – that concerns the robustness of a population of hypotheses. Through
 the lens of ensemble robustness, we reveal that a stochastic learning algorithm can
 generalize well as long as its sensitiveness to adversarial perturbations is bounded
 in average over training examples. Moreover, an algorithm may be sensitive to
 some adversarial examples (Goodfellow et al., 2015) but still generalize well. To
 support our claims, we provide extensive simulations for different deep learning
 algorithms and different network architectures exhibiting a strong correlation between
 ensemble robustness and the ability to generalize. Deep Neural Networks (DNNs) have been successfully applied in many artificial intelligence tasks, providing state-of-the-art performance and a remarkably small generalization error. On the other hand, DNNs often have far more trainable model parameters than the number of samples they are trained on and were shown to have a large enough capacity to memorize the training data BID26 . The findings of Zhang et al. suggest that classical explanations for generalization cannot be applied directly to DNNs and motivated researchers to look for new complexity measures and explanations for the generalization deep neural networks BID2 BID16 BID0 BID13 . However, in this work, we focus on a different approach to study generalization of DNNs, i.e., the connection between the robustness of a deep learning algorithm and its generalization performance. Xu & Mannor have shown that if an algorithm is robust (i.e., its empirical loss does not change dramatically for perturbed samples), its generalization performance can also be guaranteed. However, in the context of DNNs, practitioners observe contradicting evidence between these two attributes. On the one hand, DNNs generalize well, and on the other, they are fragile to adversarial perturbation on the inputs BID21 BID8 . Nevertheless, algorithms that try to improve the robustness of learning algorithms have been shown to improve the generalization of deep neural networks. Two examples are adversarial training, i.e., generating adversarial examples and training on them BID21 BID8 BID18 , and Parseval regularization BID5 , i.e., minimizing the Lifshitz constant of the network to guarantee low robustness. While these meth-ods minimize the robustness implicitly, their empirical success Indicates a connection between the robustness of an algorithm and its ability to generalize.To solve this contradiction, we revisit the robustness argument in BID23 and present ensemble robustness, to characterize the generalization performance of deep learning algorithms. Our proposed approach is not intended to give tight bounds for general deep learning algorithms, but rather to pave the way for addressing the question: how can deep learning perform so well while being fragile to adversarial examples? Answering this question is difficult, yet we present evidence in both theory and simulation suggesting that ensemble robustness explains the generalization performance of deep learning algorithms.Ensemble robustness concerns the fact that a randomized algorithm (e.g., Stochastic Gradient Descent (SGD), Dropout BID19 , Bayes-by-backprop BID3 , etc. ) produces a distribution of hypotheses instead of a deterministic one. Therefore, ensemble robustness takes into consideration robustness of the population of the hypotheses: even though some hypotheses may be sensitive to perturbation on inputs, an algorithm can still generalize well as long as most of the hypotheses sampled from the distribution are robust on average. BID13 took a different approach and claimed that deep neural networks could generalize well despite nonrobustness. However, our definition of ensemble robustness together with our empirical findings suggest that deep learning methods are typically robust although being fragile to adversarial examples.Through ensemble robustness, we prove that the following holds with a high probability: randomized learning algorithms can generalize well as long as its output hypothesis has bounded sensitiveness to perturbation in average (see Theorem 1). Specified for deep learning algorithms, we reveal that if hypotheses from different runs of a deep learning method perform consistently well in terms of robustness, the performance of such deep learning method can be confidently expected. Moreover, each hypothesis may be sensitive to some adversarial examples as long as it is robust on average.Although ensemble robustness may be difficult to compute analytically, we demonstrate an empirical estimate of ensemble robustness and investigate the role of ensemble robustness via extensive simulations. The results provide supporting evidence for our claim: ensemble robustness consistently explains the generalization performance of deep neural networks. Furthermore, ensemble robustness is measured solely on training data, potentially allowing one to use the testing examples for training and selecting the best model based on its ensemble robustness. BID23 proposed to consider model robustness for estimating generalization performance for deterministic algorithms, such as for SVM BID25 and Lasso BID24 . They suggest using robust optimization to construct learning algorithms, i.e., minimizing the empirical loss concerning the adversarial perturbed training examples. In this paper, we investigated the generalization ability of stochastic deep learning algorithm based on their ensemble robustness; i.e., the property that if a testing sample is similar to a training sample, then its loss is close to the training error. We established both theoretically and experimentally evidence that ensemble robustness of an algorithm, measured on the training set, indicates its generalization performance well. Moreover, our theory and experiments suggest that DNNs may be robust (and generalize) while being fragile to specific adversarial examples. Measuring ensemble robustness of stochastic deep learning algorithms may be computationally prohibitive as one needs to sample several output hypotheses of the algorithm. Thus, we demonstrated that by learning the probability distribution of the weights of a neural network explicitly, e.g., via variational methods such as Bayes-by-backprop, we can still observe a positive correlation between robustness and generalization while using fewer computations, making ensemble robustness feasible to measure.As a direct consequence, one can potentially measure the generalization error of an algorithm without using testing examples. In future work, we plan to further investigate if ensemble robustness can be used for model selection instead of cross-validation (and hence, increasing the training set size), in particular in problems that have a small training set. A different direction is to study the resilience of deep learning methods to adversarial attacks BID17 . BID20 recently showed that ensemble methods are useful as a mean to defense against adversarial attacks. However, they only considered implicit ensemble methods which are computationally prohibitive. As our simulations show that explicit ensembles are robust as well, we believe that they are likely to be a useful defense strategy while reducing computational cost. Finally, Theorem 2 suggests that a randomized algorithm can tolerate the non-robustness of some hypotheses to certain samples; this may help to explain Proposition 1 in BID13 : "For any dataset, there exist arbitrarily unstable non-robust algorithms such that has a small generalization gap". We leave this intuition for future work.
Explaining the generalization of stochastic deep learning algorithms, theoretically and empirically, via ensemble robustness This paper presents an adaptation of the algorithmic robustness of Xu&Mannor'12 and presents learning bounds and an experimental showing correlation between empirical ensemble robustness and generalization error.  Proposes a study of the generalization ability of deep learning algorithms using an extension of notion of stability called ensemble robustness and gives bounds on generalization error of a randomized algorithm in terms of stability parameter and provides empirical study attempting to connect theory with practice. The paper studied the generalization ability of learning algorithms from the robustness viewpoint in a deep learning context