Att kontrollera robustheten hos ett allmänt rektifierat Linear Unit-nät (ReLU) är ett NPfullständigt problem. Även om det är svårt att hitta den exakta minsta kontradiktoriska förvrängningen, är det möjligt att ge en certifierad nedre gräns för den minsta förvrängningen. Nuvarande tillgängliga metoder för beräkning av en sådan gräns är antingen tidskrävande eller ger låga kvalitetsgränser som är för lösa för att vara användbara. I detta dokument utnyttjar vi den speciella strukturen för ReLU-nätverk och tillhandahåller två beräkningseffektiva algoritmer (Fast-Lin,Fast-Lip) som kan certifiera icke-triviala lägre gränser för minsta kontradiktoriska störningar. Experiment visar att (1) våra metoder levererar gränser nära (gapet är 2-3X) exakt minsta förvrängningar som finns av Reluplex i små nätverk medan våra algoritmer är mer än 10.000 gånger snabbare; (2) våra metoder levererar liknande kvalitet gränser (gapet är inom 35% och vanligtvis runt 10%; ibland våra gränser är ännu bättre) för större nätverk jämfört med de metoder som bygger på att lösa linjära programmering problem men våra algoritmer är 33-14000 gånger snabbare; (3) vår metod är kapabel att lösa stora MNIST och CIFAR nätverk upp till 7 lager med mer än 10.000 neuroner inom tiotals sekunder på en enda CPU kärna. Dessutom visar vi att det inte finns någon polynomalgoritm som ungefär kan hitta minsta 1 kontraarial distorsion av ett ReLU-nätverk med en 0,99 ln n n approximation förhållande om inte NP=P, där n är antalet neuroner i nätverket.
REF ger effektivare algoritmer för beräkning av en certifierad lägre gräns.