Abstract
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a semi-random noise regime that generalizes both the random and worst-case noise regimes. We propose the first quantitative analysis of the robustness of nonlinear classifiers in this general noise regime. We establish precise theoretical bounds on the robustness of classifiers in this general regime, which depend on the curvature of the classifier's decision boundary. Our bounds confirm and quantify the empirical observations that classifiers satisfying curvature constraints are robust to random noise. Moreover, we quantify the robustness of classifiers in terms of the subspace dimension in the semi-random noise regime, and show that our bounds remarkably interpolate between the worst-case and random noise regimes. We perform experiments and show that the derived bounds provide very accurate estimates when applied to various state-of-the-art deep neural networks and datasets. This result suggests bounds on the curvature of the classifiers' decision boundaries that we support experimentally, and more generally offers important insights onto the geometry of high dimensional classification problems.
Introduction
Deep neural networks exhibit a striking paradox: while they are remarkably resilient to random Gaussian noise, they remain highly vulnerable to small, carefully crafted adversarial perturbations. This gap between random and worst-case robustness has been a central mystery in deep learning. This paper addresses this by proposing a "semi-random" noise regime that generalizes both extremes and provides a quantitative analysis based on the geometry of the classifier's decision boundary.
Methodology: Curvature and Semi-Random Noise
The authors introduce a semi-random noise regime, where the goal is to find the worst-case perturbation within a randomly chosen subspace of dimension $m$. This framework allows for a smooth interpolation between the purely random case ($m=1$) and the fully adversarial case ($m=d$).
A key contribution is the formalization of decision boundary curvature. For nonlinear classifiers, curvature is quantified by the radius of the largest ball that can be inscribed within a class region at a boundary point. A smaller inscribed ball indicates higher local curvature, while a larger ball suggests a flatter boundary.
Theoretical Insights
The analysis reveals that for linear (affine) classifiers, robustness to random noise scales with $\sqrt{d}$ relative to the distance to the nearest boundary. In high-dimensional spaces, a random vector is statistically likely to be nearly orthogonal to the boundary normal, explaining the "blessing of dimensionality."
In the semi-random regime, robustness scales by $\sqrt{d/m}$. This interpolation property demonstrates that even restricted access to a small fraction of input dimensions can significantly reduce the perturbation magnitude required to fool a model. As $m$ increases, the noise required to flip a prediction decreases rapidly, bridging the gap between random and adversarial regimes.
Experimental Results
The theoretical bounds were validated on MNIST, CIFAR-10, and ImageNet using architectures like LeNet and VGG. The researchers defined a ratio $\beta$ to compare theoretical estimates to empirical robustness; across all datasets, $\beta \approx 1.0$ with very low standard deviation, indicating that the derived bounds are highly accurate in practice.
Empirical evidence suggests that state-of-the-art deep neural networks have surprisingly flat decision boundaries in most directions. This flatness explains why linear-based approximations often hold true even for complex, non-linear models. Visual confirmation via 2D cross-sections shows that boundaries are mostly straight lines, curving significantly only at "junctions" where multiple classes meet.
Conclusion
This work provides a rigorous geometric foundation for understanding classifier robustness. By linking robustness to the curvature of decision boundaries and the dimensionality of the noise subspace, it offers a clear explanation for the discrepancy between adversarial and random noise sensitivity. Future work may leverage these insights to develop training objectives that explicitly minimize boundary curvature to enhance overall model reliability.
Summary updated