2025/10/01 by Woojin Kim, James Luedtke, Kim, Woojin +1
Computer Science · Engineering · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Neural Networks and Applications #Optimization and Control (math.OC) #Robot Manipulation and Learning
paper · pdf · doi:10.48550/arxiv.2510.01525
openalex publication_date 2025/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Binarized neural networks (BNNs) are feedforward neural networks with binary weights and activation functions. In the context of using a BNN for classification, the verification problem seeks to determine whether a small perturbation of a given input can lead it to be misclassified by the BNN, and the robustness of the BNN can be measured by solving the verification problem over multiple inputs. The BNN verification problem can be formulated as an integer programming (IP) problem. However, the natural IP formulation is often challenging to solve due to a large integrality gap induced by big-M constraints. We present two techniques to improve the IP formulation. First, we introduce a new method for obtaining a linear objective for the multi-class setting. Second, we introduce a new technique for generating valid inequalities for the IP formulation that exploits the recursive structure of BNNs. We find that our techniques enable verifying BNNs against a higher range of input perturbation than existing IP approaches within a limited time.