Deep learning models are notoriously vulnerable to adversarial attacks—tiny, calculated perturbations that can completely flip a model's prediction. While researchers have developed formal verification tools to mathematically prove a model's robustness within a specific perturbation range (an $\epsilon$-ball), the vast majority of these tools are tailored for standard neural networks relying on piecewise linear activation functions like ReLUs.
Recently, Polynomial Networks (PNs) have emerged as a powerful alternative, achieving state-of-the-art results in tasks like face recognition. Instead of standard activation functions, PNs utilize multiplicative interactions (Hadamard products). Because PNs lack the piecewise linearity of ReLUs, standard verification algorithms fail to apply. This paper introduces VPN (Verification of Polynomial Networks), the first sound and complete framework designed specifically to certify the robustness of these non-linear, polynomial-based architectures.
The VPN Framework
To provide formal safety guarantees for PNs, the authors propose a method that integrates into the classical Branch and Bound (BaB) global optimization framework. The verification objective for PNs is inherently non-convex, making it difficult to solve directly. VPN overcomes this through several core innovations:
- $\alpha$-Convexification: The authors transform the non-convex verification objective into a convex lower-bounding function. They achieve this by adding a quadratic penalty term scaled by a parameter $\alpha$, which is derived from the minimum eigenvalue of the model's Hessian matrix.
- Efficient Hessian Bounding: Computing a full $d \times d$ Hessian matrix for high-dimensional image inputs is computationally intractable. VPN utilizes Interval Bound Propagation (IBP) combined with a recursive power method to estimate the necessary bounds efficiently.
- Low-Rank Exploitation: A key technical breakthrough in VPN is performing matrix-vector products for the power method without ever explicitly storing or calculating the massive Hessian matrix. By exploiting the low-rank factorization inherent in the PN architecture, memory usage remains strictly controlled.
The resulting method is both sound (it never falsely claims a model is robust) and complete (it is guaranteed to find an adversarial example if one exists, given sufficient time).
Key Insights
- Differentiability as an Asset: While ReLU networks are difficult to verify due to their lack of smoothness, the twice-differentiable nature of PNs allows the application of classical second-order optimization theory (like $\alpha$-convexification) that is impossible for ReLUs.
- Tighter Bounds: Standard IBP is notoriously "loose," often providing bounds too pessimistic to be useful. VPN generates significantly tighter bounds, particularly for lower-degree polynomials.
- Implicit Computation: The realization that the full Hessian matrix is unnecessary—only its effect on a vector is needed—allowed the authors to scale verification to the 27,000+ input dimensions of the STL10 dataset.
Experimental Results
The authors evaluated VPN on three standard image classification benchmarks: MNIST ($28 \times 28$), CIFAR10 ($32 \times 32$), and STL10 ($96 \times 96$). The inclusion of STL10 is notable, as its high resolution often causes standard verifiers to run out of memory.
- Superior Scalability: Compared to a standard black-box solver (Gurobi), VPN is significantly faster and more memory-efficient. On STL10, Gurobi ran out of memory, whereas VPN successfully verified the networks.
- Tight Verification Gaps: On MNIST, VPN achieved a "verified accuracy" (the percentage of images proven robust) of 96.3%, nearly identical to the empirical upper bound of 96.4%. This highlights the extreme precision of the method.
- Outperforming Baselines: VPN outperformed DeepT-Fast (a zonotope-based method), providing tighter bounds across various perturbation levels ($\epsilon$) and polynomial degrees. For instance, on CIFAR10 at $\epsilon = 2/255$, VPN achieved 25.4% verified accuracy compared to just 1.4% for DeepT-Fast.
Limitations and Future Work
While VPN represents a significant leap forward, challenges remain. As the degree of the polynomial increases, the verification problem becomes exponentially harder, and the bounds can loosen. Furthermore, formal verification remains computationally expensive; verifying STL10 images took an average of over 40 minutes per image in some configurations. Future work aims to extend these techniques to a broader class of twice-differentiable architectures and deeper polynomial structures.
Summary updated