We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in [1] to defend neural networks against @math -norm and @math -norm attacks. Concretely, for a signal that is approximately sparse in some transform domain and has been perturbed with noise, we provide guarantees for accurately recovering the signal in the transform domain. We can then use the recovered signal to reconstruct the signal in its original domain while largely removing the noise. Our results are general as they can be directly applied to most unitary transforms used in practice and hold for both @math -norm bounded noise and @math -norm bounded noise. In the case of @math -norm bounded noise, we prove recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For the case of @math -norm bounded noise, we provide recovery guarantees for BP. These guarantees theoretically bolster the defense framework introduced in [1] for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate this defense framework using both IHT and BP against the One Pixel Attack [21], Carlini-Wagner @math and @math attacks [3], Jacobian Saliency Based attack [18], and the DeepFool attack [17] on CIFAR-10 [12], MNIST [13], and Fashion-MNIST [27] datasets. This expands beyond the experimental demonstrations of [1].
The authors of @cite_0 introduced the CRD framework which inspired this work. The main theorem (Theorem 2.2) of @cite_0 is an analog of our Theorem and provides a similar bound the approximation error for recovery via IHT. First note that the statement of the Theorem 2.2 of @cite_0 is missing the required hypothesis @math . This hypothesis appears in Lemma 3.6 of @cite_0 , which is used to prove Theorem 2.2, but it appears to have been accidentally dropped from the statement of Theorem 2.2. We note that, by making the constants explicit, the proof of Lemma 3.6 of @cite_0 gives the same restricted isometry property that we do in Theorem . Therefore, the guarantees we obtain for IHT are essentially the same as in @cite_0 . The main difference is that, to derive recovery guarantees for IHT from the restricted isometry property, we utilize Theorem below (which is a modified version of Theorem 6.18 of @cite_15 ) while the authors of @cite_0 utilize Theorem 3.4 in @cite_0 (which is taken from @cite_19 ).
@cite_0 @cite_19 @cite_15
2890343472 143004564
I Functional on Stochastic Processes.- 1. Stochastic Processes as Random Functions.- Notes.- Problems.- II Uniform Convergence of Empirical Measures.- 1. Uniformity and Consistency.- 2. Direct Approximation.- 3. The Combinatorial Method.- 4. Classes of Sets with Polynomial Discrimination.- 5. Classes of Functions.- 6. Rates of Convergence.- Notes.- Problems.- III Convergence in Distribution in Euclidean Spaces.- 1. The Definition.- 2. The Continuous Mapping Theorem.- 3. Expectations of Smooth Functions.- 4. The Central Limit Theorem.- 5. Characteristic Functions.- 6. Quantile Transformations and Almost Sure Representations.- Notes.- Problems.- IV Convergence in Distribution in Metric Spaces.- 1. Measurability.- 2. The Continuous Mapping Theorem.- 3. Representation by Almost Surely Convergent Sequences.- 4. Coupling.- 5. Weakly Convergent Subsequences.- Notes.- Problems.- V The Uniform Metric on Spaces of Cadlag Functions.- 1. Approximation of Stochastic Processes.- 2. Empirical Processes.- 3. Existence of Brownian Bridge and Brownian Motion.- 4. Processes with Independent Increments.- 5. Infinite Time Scales.- 6. Functional of Brownian Motion and Brownian Bridge.- Notes.- Problems.- VI The Skorohod Metric on D(0, ?).- 1. Properties of the Metric.- 2. Convergence in Distribution.- Notes.- Problems.- VII Central Limit Theorems.- 1. Stochastic Equicontinuity.- 2. Chaining.- 3. Gaussian Processes.- 4. Random Covering Numbers.- 5. Empirical Central Limit Theorems.- 6. Restricted Chaining.- Notes.- Problems.- VIII Martingales.- 1. A Central Limit Theorem for Martingale-Difference Arrays.- 2. Continuous Time Martingales.- 3. Estimation from Censored Data.- Notes.- Problems.- Appendix A Stocha 1 Preliminaries.- 1.1 Introduction.- 1.2 Measures and Functions.- 1.3 Weak Topologies.- 1.4 Convergence of Measures.- 1.5 Complements.- 1.6 Notes.- I Markov Chains and Ergodicity.- 2 Markov Chains and Ergodic Theorems.- 2.1 Introduction.- 2.2 Basic Notation and Definitions.- 2.3 Ergodic Theorems.- 2.4 The Ergodicity Property.- 2.5 Pathwise Results.- 2.6 Notes.- 3 Countable Markov Chains.- 3.1 Introduction.- 3.2 Classification of States and Class Properties.- 3.3 Limit Theorems.- 3.4 Notes.- 4 Harris Markov Chains.- 4.1 Introduction.- 4.2 Basic Definitions and Properties.- 4.3 Characterization of Harris recurrence.- 4.4 Sufficient Conditions for P.H.R.- 4.5 Harris and Doeblin Decompositions.- 4.6 Notes.- 5 Markov Chains in Metric Spaces.- 5.1 Introduction.- 5.2 The Limit in Ergodic Theorems.- 5.3 Yosida's Ergodic Decomposition.- 5.4 Pathwise Results.- 5.5 Proofs.- 5.6 Notes.- 6 Classification of Markov Chains via Occupation Measures.- 6.1 Introduction.- 6.2 A Classification.- 6.3 On the Birkhoff Individual Ergodic Theorem.- 6.4 Notes.- II Further Ergodicity Properties.- 7 Feller Markov Chains.- 7.1 Introduction.- 7.2 Weak-and Strong-Feller Markov Chains.- 7.3 Quasi Feller Chains.- 7.4 Notes.- 8 The Poisson Equation.- 8.1 Introduction.- 8.2 The Poisson Equation.- 8.3 Canonical Pairs.- 8.4 The Cesaro-Averages Approach.- 8.5 The Abelian Approach.- 8.6 Notes.- 9 Strong and Uniform Ergodicity.- 9.1 Introduction.- 9.2 Strong and Uniform Ergodicity.- 9.3 Weak and Weak Uniform Ergodicity.- 9.4 Notes.- III Existence and Approximation of Invariant Probability Measures.- 10 Existence of Invariant Probability Measures.- 10.1 Introduction and Statement of the Problems.- 10.2 Notation and Definitions For more than three and one-half decades, beginning in the early 1960s, a heavy emphasis on proof finding has been a key component of the Argonne paradigm, whose use has directly led to significant advances in automated reasoning and important contributions to mathematics and logic. The theorems studied range from the trivial to the deep, even including some that corresponded to open questions. Often the paradigm asks for a theorem whose proof is in hand but that cannot be obtained in a fully automated manner by the program in use. The theorem whose hypothesis consists solely of the Meredith single axiom for two-valued sentential (or propositional) calculus and whose conclusion is the Lukasiewicz three-axiom system for that area of formal logic was just such a theorem. Featured in this article is the methodology that enabled the program OTTER to find the first fully automated proof of the cited theorem, a proof with the intriguing property that none of its steps contains a term of the form i>n(i>n(i>t)) for any term i>t. As evidence of the power of the new methodology, the article also discusses OTTER's success in obtaining the first known proof of a theorem concerning a single axiom of Lukasiewicz.