Evaluating Robustness of Neural Networks with Mixed Integer Programming

By Vincent Tjeng, Kai Y. Xiao, Russ Tedrake. 2017

967 citations recorded by the source corpus.

Subfields: Safety, Robustness & Interpretability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Safety, Robustness & Interpretability

In Mathematical Optimization

Citations in the corpus

Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, methodology): “, 2018), mixed integer linear programming (Tjeng et al., 2019), and duality (Dvijotham et al.”
Certified Adversarial Robustness via Randomized Smoothing (2019, background): “Unfortunately, no exact methods have been shown to scale beyond moderatesized (100,000 activations) networks (Tjeng et al., 2019), and networks of that size can only be verified when they are trained in a manner that impairs their expressivity.”
Efficient Formal Safety Analysis of Neural Networks (2018, methodology): “Another line of research has used Mixed Integer Linear Programming (MILP) solvers for such analysis [38, 12, 7].”
Robustness May Be at Odds with Accuracy (2018, background): “Only recently, has there been progress towards models that achieve robustness that can be demonstrated empirically and, in some cases, even formally verified (Madry et al., 2018; Wong & Kolter, 2018; Sinha et al., 2018; Tjeng et al., 2019; Raghunathan et al., 2018; Dvijotham et al., 2018a; Xiao et a”
On Evaluating Adversarial Robustness (2019, background): “While work in this space does exist (Katz et al., 2017; Tjeng et al., 2019; Xiao et al., 2019; Gowal et al., 2018), it is often computationally intractable to verify even modestly sized neural networks.”
On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models (2018, methodology): “However, when running a complete solver (using a MIP formulation), we are able to ﬁnd a counter-example that successfully induces the model to misclassify the “eight” as a “two” (as shown in Figure 6c).”
Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (2019, methodology): “Exact methods, usually based on Satisfiability Modulo Theories solvers [18, 11] or mixed integer linear programming [33, 24, 12], are guaranteed to find an adversarial example around a datapoint if it exists.”
Fast is better than free: Revisiting adversarial training (2020, methodology): “We train two convolutional networks with 16 and 32 convolutional ﬁlters followed by a fully connected layer of 100 units, the same architecture used by Tjeng et al. (2017).”
MixTrain: Scalable Training of Formally Robust Neural Networks (2018, background): “MILP solver achieves better performance [60], [61], [62], but they still suffer from high nonlinearity of resulting formulas.”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, background): “There is a deep body of work using mixed-integer programming to verify the robustness of a neural network (Lomuscio & Maganti, 2017; Fischetti & Jo, 2018; Tjeng et al., 2017; Dutta et al., 2017; Cheng et al., 2017; Xiao et al., 2018).”
Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification (2021, background): “Related Work Early complete verifiers relied on existing solvers (Katz et al., 2017; Ehlers, 2017; Huang et al., 2017; Dutta et al., 2018; Tjeng et al., 2019) and were limited to very small problem instances.”
Lipschitz-Certifiable Training with a Tight Outer Bound (2020, methodology): “Thus, many veriﬁcation methods are proposed to guarantee stable prediction of input within a perturbation set [18, 5, 9, 16, 38, 34, 23, 11, 3, 30, 8, 43, 2].”
Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack (2019, background): “…problem (1) is non-convex and NP-hard for non-trivial classifiers (Katz et al., 2017) and, although for some classes of networks it can be formulated as a mixedinteger program (Tjeng et al., 2019), the computational cost of solving it is prohibitive for large, normally trained networks.”
Machine Learning Testing: Survey, Landscapes and Horizons (2019, background): “[137] proposed to use the distance between a test input and its closest adversarial example to measure robustness.”
Overfitting in adversarially robust deep learning (2020, background): “, 2017) and mixed-integer linear programs (Tjeng et al., 2019) for exact certificates, to semi-definite programming (SDP) solvers for relaxed but still accurate certificates (Raghunathan et al.”
Fast and Stable Interval Bounds Propagation for Training Verifiably Robust Models (2019, methodology): “The proposed idea is not limited to IBP and can be incorporated in other robust training methods, such as the convex-optimization-based approaches Wong and Kolter [2017], Dvijotham et al.”
Adversarial Robustness Against the Union of Multiple Perturbation Models (2019, methodology): “, 2018b), and mixed-integer linear programming (Tjeng et al., 2019), the last of which has recently been successfully scaled to reasonably sized networks.”