English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We improve the effectiveness of propagation- and linear-optimization-basedneural network verification algorithms with a new tightened convex relaxationfor ReLU neurons. Unlike previous single-neuron relaxations which focus only onthe univariate input space of the ReLU, our method considers the multivariateinput space of the affine pre-activation function preceding the ReLU. Usingresults from submodularity and convex geometry, we derive an explicitdescription of the tightest possible convex relaxation when this multivariateinput is over a box domain. We show that our convex relaxation is significantlystronger than the commonly used univariate-input relaxation which has beenproposed as a natural convex relaxation barrier for verification. While ourdescription of the relaxation may require an exponential number ofinequalities, we show that they can be separated in linear time and hence canbe efficiently incorporated into optimization algorithms on an as-needed basis.Based on this novel relaxation, we design two polynomial-time algorithms forneural network verification: a linear-programming-based algorithm thatleverages the full power of our relaxation, and a fast propagation algorithmthat generalizes existing approaches. In both cases, we show that for a modestincrease in computational effort, our strengthened relaxation enables us toverify a significantly larger number of instances compared to similaralgorithms.

The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification