Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization

• URL: http://arxiv.org/abs/2405.17049v1
• Date: Mon, 27 May 2024 11:03:48 GMT
• Title: Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization
• Authors: Jianting Yang, Srećko Ðurašinović, Jean-Bernard Lasserre, Victor Magron, Jun Zhao,
• Abstract summary: This paper explores methods for verifying the properties of Binary Neural Networks (BNNs) BNNs, like their full-precision counterparts, are also sensitive to input perturbations. We introduce an alternative approach using Semidefinite Programming relaxations derived from sparse Polynomial Optimization.
• Score: 8.323690755070123
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper explores methods for verifying the properties of Binary Neural Networks (BNNs), focusing on robustness against adversarial attacks. Despite their lower computational and memory needs, BNNs, like their full-precision counterparts, are also sensitive to input perturbations. Established methods for solving this problem are predominantly based on Satisfiability Modulo Theories and Mixed-Integer Linear Programming techniques, which are characterized by NP complexity and often face scalability issues. We introduce an alternative approach using Semidefinite Programming relaxations derived from sparse Polynomial Optimization. Our approach, compatible with continuous input space, not only mitigates numerical issues associated with floating-point calculations but also enhances verification scalability through the strategic use of tighter first-order semidefinite relaxations. We demonstrate the effectiveness of our method in verifying robustness against both $\|.\|_\infty$ and $\|.\|_2$-based adversarial attacks.

Related papers

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Verifying message-passing neural networks via topology-based bounds tightening [3.3267518043390205]
  We develop a computationally effective approach towards providing robust certificates for message-passing neural networks (MPNNs) Because our work builds on mixed-integer optimization, it encodes a wide variety of subproblems. We test on both node and graph classification problems and consider topological attacks that both add and remove edges.
  arXiv  Detail & Related papers  (2024-02-21T17:05:27Z)
• Dynamically configured physics-informed neural network in topology optimization applications [4.403140515138818]
  The physics-informed neural network (PINN) can avoid generating enormous amounts of data when solving forward problems. A dynamically configured PINN-based topology optimization (DCPINN-TO) method is proposed. The accuracy of the displacement prediction and optimization results indicate that the DCPINN-TO method is effective and efficient.
  arXiv  Detail & Related papers  (2023-12-12T05:35:30Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• Targeted Attack against Deep Neural Networks via Flipping Limited Weight Bits [55.740716446995805]
  We study a novel attack paradigm, which modifies model parameters in the deployment stage for malicious purposes. Our goal is to misclassify a specific sample into a target class without any sample modification. By utilizing the latest technique in integer programming, we equivalently reformulate this BIP problem as a continuous optimization problem.
  arXiv  Detail & Related papers  (2021-02-21T03:13:27Z)
• Gradient-Free Adversarial Attacks for Bayesian Neural Networks [9.797319790710713]
  adversarial examples underscore the importance of understanding the robustness of machine learning models. In this work, we employ gradient-free optimization methods in order to find adversarial examples for BNNs.
  arXiv  Detail & Related papers  (2020-12-23T13:19:11Z)
• Efficient and Sparse Neural Networks by Pruning Weights in a Multiobjective Learning Approach [0.0]
  We propose a multiobjective perspective on the training of neural networks by treating its prediction accuracy and the network complexity as two individual objective functions. Preliminary numerical results on exemplary convolutional neural networks confirm that large reductions in the complexity of neural networks with neglibile loss of accuracy are possible.
  arXiv  Detail & Related papers  (2020-08-31T13:28:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.