Overcoming the Convex Barrier for Simplex Inputs

Harkirat Singh, M. Pawan Kumar, Philip Torr, Krishnamurthy Dj DvijothamNeurIPS 2021 · OpenReview

TL;DR

This paper introduces a novel, efficient method for verifying the robustness of neural networks when inputs are constrained to a probability simplex (common in text processing and $\ell_1$ robustness). By deriving a tight convex relaxation that remains linear in size—unlike the exponential complexity typically required to overcome the "convex barrier"—the authors achieve up to a 25% improvement in verified accuracy over existing state-of-the-art methods.

The Challenge: The Convex Barrier

Neural network verification is the process of mathematically proving that a model will behave correctly under certain conditions (e.g., ensuring an image classifier will never misclassify a specific image if an attacker only changes a limited number of pixels).

The biggest hurdle in this field is the convex barrier. To make verification computationally feasible, researchers often use "convex relaxations"—simplified geometric shapes that wrap around the complex, non-linear behavior of a neural network. However, these shapes are often "loose," meaning they include a lot of "impossible" network outputs. If the relaxation is too loose, we cannot prove robustness even if the network is actually robust.

While recent work has found ways to tighten these relaxations for standard $\ell_\infty$ perturbations (changing every pixel by a tiny amount), doing so for simplex inputs (where inputs must sum to 1, like word counts in text or $\ell_1$ "sparse" perturbations) has remained difficult and computationally expensive.

Introducing Simplex Verify

The authors propose a new framework called Simplex Verify. Their approach consists of three main technical contributions:

  1. Linear-Sized Convex Hull: They prove that for a single neuron with simplex inputs, the "tightest possible" convex relaxation (the convex hull) can be described using a number of constraints that scales linearly with the number of inputs. This is a major surprise, as similar tight relaxations for other input types usually require an exponential number of constraints.
Geometric visualization of the convex relaxation
  1. Simplex Propagation: They develop a method to propagate these simplex constraints through the hidden layers of a deep network, ensuring the tightness isn't lost as you move from the input to the output.
  2. Efficient Solver: Instead of relying on slow, general-purpose commercial solvers (like Gurobi), they created a custom solver that uses a "backward pass" (similar to how neural networks are trained) to optimize the bounds. This makes the method scalable to modern, deep architectures.

Key Insights: Geometry Matters

The core "aha moment" is that the geometry of a simplex is much friendlier to convex analysis than the geometry of a hypercube ($\ell_\infty$ ball). This simplicity allows for a "perfect" relaxation that is still computationally cheap.

By using this tight relaxation, the authors show that the "convex barrier" isn't an inherent dead-end for all verification tasks. For simplex inputs, you can get very close to the ground truth without the math exploding in complexity. Usually, in verification, you have to choose: either a fast but "loose" method (like Interval Bound Propagation) or a slow but "tight" method (like Linear Programming). Simplex Verify manages to be nearly as fast as the loose methods while being as tight as the slow ones.

Empirical Results

The authors evaluated their method on three primary benchmarks: MNIST and CIFAR-10 (for $\ell_1$ robustness) and UPMC Food-101 (a multi-modal dataset for global text robustness).

Verification results on MNIST and CIFAR-10
  • Higher Accuracy: On CIFAR-10 $\ell_1$ robustness, the method improved verified accuracy by up to 14.4% over the previous best approach.
  • Massive Gains in Text: On the multi-modal Food-101 task, it achieved 25% higher verified accuracy than the baseline.
  • Speed: The custom solver is roughly 3 orders of magnitude faster than using a standard commercial solver (Gurobi) to solve the same problem, reducing verification time from minutes to fractions of a second per sample (e.g., dropping from ~72 seconds to just 0.04 seconds).

Limitations and Future Work

  • Activation Functions: The current proof relies on the activation function being convex (like ReLU or SoftPlus). While these are standard, the method might need adjustment for non-convex activations like Sigmoid or Tanh.
  • Architecture Specifics: The multi-modal experiments focused on a "Bag of Words" (BOW) text embedding. Extending this to more complex architectures like Transformers (which use attention mechanisms) is a logical next step but would require handling more complex non-linearities.
  • Input Constraints: The method is specifically designed for simplex-constrained inputs. While many problems can be reformulated this way, it isn't a "universal" verifier for every type of adversarial attack.

Summary updated

Abstract

Recent progress in neural network verification has challenged the notion of a convex barrier, that is, an inherent weakness in the convex relaxation of the output of a neural network. Specifically, there now exists a tight relaxation for verifying the robustness of a neural network to $\ell_\infty$ input perturbations, as well as efficient primal and dual solvers for the relaxation. Buoyed by this success, we consider the problem of developing similar techniques for verifying robustness to input perturbations within the probability simplex. We prove a somewhat surprising result that, in this case, not only can one design a tight relaxation that overcomes the convex barrier, but the size of the relaxation remains linear in the number of neurons, thereby leading to simpler and more efficient algorithms. We establish the scalability of our overall approach via the specification of $\ell_1$ robustness for CIFAR-10 and MNIST classification, where our approach improves the state of the art verified accuracy by up to $14.4\%$. Furthermore, we establish its accuracy on a novel and highly challenging task of verifying the robustness of a multi-modal (text and image) classifier to arbitrary changes in its textual input.
BibTeX
@inproceedings{singh2021overcoming,
  author = {Harkirat Singh and M. Pawan Kumar and Philip Torr and Krishnamurthy Dj Dvijotham},
  title = {{Overcoming the Convex Barrier for Simplex Inputs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=JXREUkyHi7u},
}
Figure