analiza aiqbench
This research advances neural network verification by introducing a dynamic programming algorithm that optimizes piecewise affine abstractions for non-linear activation functions, including Kolmogorov-Arnold Networks. By treating the allocation of approximation pieces as an optimization problem similar to knapsack solving, the method achieves tighter output bounds without significantly increasing computational overhead compared to uniform approaches. This work directly addresses safety and reliability concerns in deploying complex AI models where rigorous range verification is critical.
Optimized Piecewise Affine Abstractions of Neural Networks with Learnable Activation Functions
arXiv:2602.06737v2 Announce Type: replace-cross Abstract: We present a generalized framework for the range verification of neural networks featuring non-linear activation functions. Our approach first constructs an ``optimized piecewise affine abstraction" of the network that replaces each non-linear activation function by a piecewise affine (PWA) function plus a bounded error. Such PWA functions are readily amenable to existing neural network verification techniques using specializations of linear arithmetic SMT solvers and mixed-integer optimization approaches. However, there are infinitely many ways to abstract each node, with a natural tradeoff between the number of pieces used, the global error bound, and the complexity of the resulting verification problem. We propose a dynamic programming (DP) algorithm to systematically compute the optimized PWA abstraction for general activation functions, guaranteeing tighter output bounds. The algorithm combines a local DP approximation at each node with a global error bound, yielding a variant of the knapsack problem for deciding how to allocate a fixed budget on the total number of pieces across units so as to minimize the worst-case error bound between the network and its approximation. Although the knapsack problem is itself NP-hard, we can use pseudo-polynomial DP algorithms as well as approximation schemes to solve it efficiently. Crucially, our approach is broadly applicable to diverse networks consisting of non-linear activations, including standard Multi-Layer Perceptrons (MLPs) and recently proposed architectures such as Kolmogorov-Arnold Networks (KANs). Over a series of KAN benchmarks spanning 20 to 22,000 parameters, our approach yields output bounds that are consistently of smaller width than uniform PWA allocation. The overall time taken is roughly comparable while the overhead for computing the optimized abstraction is subsumed by the time taken to compute output bounds.
Abstract:We present a generalized framework for the range verification of neural networks featuring non-linear activation functions. Our approach first constructs an ``optimized piecewise affine abstraction" of the network that replaces each non-linear activation function by a piecewise affine (PWA) function plus a bounded error. Such PWA functions are readily amenable to existing neural network verification techniques using specializations of linear arithmetic SMT solvers and mixed-integer optimization approaches. However, there are infinitely many ways to abstract each node, with a natural tradeoff between the number of pieces used, the global error bound, and the complexity of the resulting verification problem. We propose a dynamic programming (DP) algorithm to systematically compute the optimized PWA abstraction for general activation functions, guaranteeing tighter output bounds. The algorithm combines a local DP approximation at each node with a global error bound, yielding a variant of the knapsack problem for deciding how to allocate a fixed budget on the total number of pieces across units so as to minimize the worst-case error bound between the network and its approximation. Although the knapsack problem is itself NP-hard, we can use pseudo-polynomial DP algorithms as well as approximation schemes to solve it efficiently. Crucially, our approach is broadly applicable to diverse networks consisting of non-linear activations, including standard Multi-Layer Perceptrons (MLPs) and recently proposed architectures such as Kolmogorov-Arnold Networks (KANs). Over a series of KAN benchmarks spanning 20 to 22,000 parameters, our approach yields output bounds that are consistently of smaller width than uniform PWA allocation. The overall time taken is roughly comparable while the overhead for computing the optimized abstraction is subsumed by the time taken to compute output bounds.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO)
arXiv:2602.06737 [cs.LG]
(or arXiv:2602.06737v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2602.06737 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 373 cuvinte
Subiecte conexe
Learnable Spectral Activations
arXiv · 7 oct. 2026
NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
arXiv · 9 oct. 2026
Multi-Level-Set-Based Physics-Driven Neural Network to Solve 3-D Inverse Scattering Problems
arXiv · 9 sept. 2026
Efficient Representation of multicategorical local Hilbert spaces: nonlinear Restricted Boltzmann Machines to Kolmogorov-Arnold Networks
arXiv · 9 sept. 2026