Abstract
Deep neural networks are susceptible to adversarial attacks, where small input perturbations lead to incorrect classifications. While Randomized Smoothing (RS) provides a probabilistic defense, it suffers from significant natural accuracy degradation and high computational costs. We present a deterministic certification framework using Bernstein polynomial approximation. By transforming the classifier's decision boundary into a smooth, differentiable polynomial function, we achieve deterministic robustness guarantees without stochastic sampling. Our method maintains high natural accuracy and allows for efficient certification via numerical root-finding across various norm constraints.
Introduction
The fragility of deep learning models against adversarial examples remains a critical barrier to their deployment in safety-critical applications. Randomized Smoothing (RS) has emerged as a leading defense, creating a robust classifier by aggregating predictions over noise-perturbed inputs. However, RS is inherently probabilistic, computationally expensive due to the need for thousands of samples, and often results in a substantial "accuracy tax" on clean data.
This work addresses these limitations by proposing a deterministic alternative. Instead of simulating smoothness through empirical sampling, we leverage the Weierstrass Approximation Theorem to construct a smoothed classifier using Bernstein polynomials. This approach provides a stable, norm-independent "safe zone" for predictions while preserving the model's performance on natural images.
Methodology
The proposed deterministic smoothed classifier is built upon a three-stage pipeline designed to control the model's Lipschitz constant and smooth its decision boundaries.
- Spectral Normalization (SN): To ensure stability, SN is applied to the network layers. This bounds the Lipschitz constant, preventing the output from fluctuating wildly in response to small input changes.
- Bernstein Polynomial Approximation: The core innovation involves approximating the classifier's output in a low-dimensional feature space using Bernstein polynomials. This mathematical transformation "smooths out" the sharp, non-differentiable regions of the original decision boundary.
- Numerical Root-Finding: Certification is performed by treating the smoothed decision boundary as a system of nonlinear equations. Solvers such as Levenberg-Marquardt are employed to find the exact nearest point on the boundary, determining the certified radius.
To manage the exponential complexity $O(n^d)$ of Bernstein polynomials, the method utilizes a compressed feature space (typically 3–6 dimensions) before applying the smoothing transformation.
Key Insights
- Functional Smoothing: Unlike RS, which approximates smoothness through noise, this method treats smoothing as a functional transformation, resulting in an infinitely differentiable classifier.
- Norm Independence: By utilizing numerical root-finding on the smoothed boundary, the framework can certify robustness for any distance metric (e.g., $\ell_2, \ell_\infty$), unlike methods tied to specific noise distributions.
- Deterministic Stability: The removal of stochastic sampling ensures that the certified radius for a given input is constant, eliminating the statistical uncertainty inherent in randomized approaches.
Experimental Results
The framework was evaluated on standard benchmarks including CIFAR-10, MNIST, SVHN, and CIFAR-100.
- Natural Accuracy: On CIFAR-10, the model achieved a natural accuracy of 87.4%, significantly outperforming RS-based defenses which typically see drops into the 70% range.
- Efficiency: Certification time was reduced to approximately 6.48 seconds per example on an NVIDIA RTX 2080 Ti, more than twice as fast as comparable RS settings.
- Robustness Profile: As shown in the performance comparison, the certified accuracy curve remains competitive with state-of-the-art $\ell_2$ defenses, particularly at smaller perturbation radii.
Limitations and Conclusion
While promising, the method faces the "curse of dimensionality" due to the $O(n^d)$ complexity of Bernstein polynomials, necessitating aggressive dimensionality reduction. Future research may explore "unfolding" the optimization process into neural architectures to further accelerate certification. Despite these challenges, deterministic smoothing via Bernstein polynomials offers a robust, efficient, and high-accuracy path forward for verifiable deep learning.
Summary updated