IMPROVED ESTIMATION OF CONCENTRATION UNDER `p-NORM DISTANCE METRICS USING HALF SPACES
Year: 2021

Abstract:
Concentration of measure has been argued to be the fundamental cause of adversarial vulnerability. Mahloujifar et al. (2019b) presented an empirical way to measure the concentration of a data distribution using samples, and employed it to find lower bounds on intrinsic robustness for several benchmark datasets. However, it remains unclear whether these lower bounds are tight enough to provide a useful approximation for the intrinsic robustness of a dataset. To gain a deeper understanding of the concentration of measure phenomenon, we first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures and arbitrary `p-norms (p ≥ 2). We leverage these theoretical insights to design a method that uses half-spaces to estimate the concentration of any empirical dataset under `p-norm distance metrics. Our proposed algorithm is more efficient than Mahloujifar et al. (2019b)’s, and our experiments on synthetic datasets and image benchmarks demonstrate that it is able to find much tighter intrinsic robustness bounds. These tighter estimates provide further evidence that rules out intrinsic dataset concentration as a possible explanation for the adversarial vulnerability of state-of-the-art classifiers.

heading: 1 INTRODUCTION
text: Despite achieving exceptional performance in benign settings, modern machine learning models have been shown to be highly vulnerable to inputs, known as adversarial examples, crafted with targeted but imperceptible perturbations (Szegedy et al., 2014; Goodfellow et al., 2015). This discovery has prompted a wave of research studies to propose defense mechanisms, including heuristic approaches (Papernot et al., 2016; Mądry et al., 2018; Zhang et al., 2019) and certifiable methods (Wong & Kolter, 2018; Gowal et al., 2019; Cohen et al., 2019). Unfortunately, none of these methods can successfully produce adversarially-robust models, even for classification tasks on toy datasets such as CIFAR-10. To explain the prevalence of adversarial examples, a line of theoretical works (Gilmer et al., 2018; Fawzi et al., 2018; Shafahi et al., 2019; Dohmatob, 2019; Bhagoji et al., 2019) have proven upper bounds on the maximum achievable adversarial robustness by imposing different assumptions on the underlying metric probability space. In particular, Mahloujifar et al. (2019a) generalized the previous results showing that adversarial examples are inevitable as long as the input distributions are concentrated with respect to the perturbation metric. Thus, the question of whether or not natural image distributions are concentrated is highly relevant, as if they are it would rule out any possibility of there being adversarially robust image classifiers.
Recently, Mahloujifar et al. (2019b) proposed an empirical method to measure the concentration of an arbitrary distribution using data samples, then employed it to estimate a lower bound on intrinsic robustness (see Definition 2.2 for its formal definition) for several image benchmarks. By demonstrating the gap between the estimated bounds of intrinsic robustness and the robustness performance achieved by the best current models, they further concluded concentration of measure is not the sole reason behind the adversarial vulnerability of existing classifiers for benchmark image distributions. However, due to the heuristic nature of the proposed algorithm, it remains elusive whether the estimates it produces can serve as useful approximations of the underlying intrinsic robustness limits, thus hindering understanding of how much of the actual adversarial risk can be explained by the concentration of measure phenomenon.
In this work, we address this issue by first characterizing the optimum of the actual concentration problem for general Gaussian spaces, then using our theoretical insights to develop an alternative algorithm for measuring concentration empirically that significantly improves both the accuracy and efficiency of estimates of intrinsic robustness. While we do not demonstrate a specific classifier which achieves this robustness upper bound, our results rule out inherent image distribution concentration as the reason for our current inability to find adversarially robust models.
Contributions. We generalize the Gaussian Isoperimetric Inequality to non-spherical Gaussian distributions and `p-norm distance metrics with p ≥ 2 (including `∞) (Theorem 3.3). Motivated by the optimal concentration results for special Gaussian spaces (Remark 3.4), we develop a samplebased algorithm to estimate the concentration of measure using half spaces that works for arbitrary distribution and any `p-norm distance (Section 4). Compared with prior approaches, we empirically demonstrate the significant increase in efficacy of our method under `∞-norm distance metric (Section 6). Not only does the proposed method converge to its limit with an order of magnitude fewer data (Section 6.2), it also finds a much tighter lower bound of intrinsic robustness for both simulated datasets whose underlying concentration function is analytically derivable and various benchmark image datasets (Section 6.1). In particular, we improve the best current estimated lower bound of intrinsic robustness from approximately 82% to above 93% for CIFAR-10 under `∞-norm bounded perturbations with = 8/255. These tighter concentration estimates produced by our algorithm provide strong evidence that concentration of measure should not be considered as the main cause of adversarial vulnerability, at least for the image benchmarks evaluated in our experiments.
Related Work. Several prior works have sought to empirically estimate lower bounds on intrinsic robustness using data samples. The pioneering work of Gilmer et al. (2018) introduced the connection between adversarial examples and the concentration phenomenon for uniform n-spheres, then proposed a simple heuristic to find a half space that expands slowly under Euclidean distance for the MNIST dataset. Our work can be seen as a strict generalization of Gilmer et al. (2018)’s, which applies to arbitrary `p-norm distance metrics (including `∞). By characterizing the optimal transport cost between conditional distributions, Bhagoji et al. (2019) estimated a lower bound on the best possible adversarial robustness for several image datasets. However, when applied to adversaries beyond `2, such as `∞, the lower bound produced by their method is not informative (that is, it is close to zero). The most relevant previous work is Mahloujifar et al. (2019b), which proposed a general method for measuring concentration using special collections of subsets. Although the optimal value of the considered empirical concentration problem is proven to asymptotically converge to the actual concentration, there is no guarantee that the proposed searching algorithm for solving the empirical problem finds the optimum. Our approach follows the framework introduced by Mahloujifar et al. (2019b)’s, but considers a different collection of subsets for the empirical concentration problem. This not only results in optimality for theoretical Gaussian distributions, but also significantly improves the estimation performance for typical image benchmarks.
Another line of work attempts to provide estimates of intrinsic robustness upper bounds based on generative assumptions. In order to justify the theoretically-derived impossibility results, Fawzi et al. (2018) estimated the smoothness parameters of the state-of-the-art generative models on CIFAR-10 and SVHN datasets, which yield approximated upper bounds on adversarial robustness for any classifiers. Zhang et al. (2020) generalized their results to non-smoothed data manifolds, such as datasets that can be captured by a conditional generative model. However, these methods only work for simulated generative distributions, which may deviate from the actual distributions they are intended to understand.
Notation. For any n ∈ Z+, denote by [n] the set {1, 2, . . . , n}. Lowercase boldface letters denote vectors and uppercase boldface letters represent matrices. For any vector x and p ∈ [1,∞), let xj , ‖x‖p and ‖x‖∞ be the j-th element, the `p-norm and the `∞-norm of x. For any matrix A, B is said to be a square root of A if A = BB, and the induced matrix p-norm of A is defined as ‖A‖p = supx6=0{‖Ax‖p/‖x‖p}. Denote by N (θ,Σ) the Gaussian distribution with mean θ and covariance matrix Σ. Let γn be the probability measure of N (0, In), where In denotes the identity matrix. Let Φ(·) be the cumulative distribution function of N (0, 1) and Φ−1(·) be its inverse. For any set A, let pow(A) and 1A(·) be all measurable subsets and the indicator function of A. Let (X , µ,∆) be a metric probability space, where ∆ : X × X → R≥0 denotes a distance metric on X . Define the empirical measure with respect to a sample set {xi}i∈[m] as µ̂m(A) = 1m ∑ i∈[m] 1A(xi),
∀A ∈ pow(X ). Let B(x, ,∆) = {x′ ∈ X : ∆(x′,x) ≤ } be the ball around x with radius. Define the -expansion of A as A(∆) = {x ∈ X : ∃ x′ ∈ B(x, ,∆) ∩ A}.

heading: 2 PRELIMINARIES
text: In this section, we introduce the problem of measuring concentration and its connection to adversarial robustness. Consider a metric probability space of instances (X , µ,∆). Given parameters ≥ 0 and α > 0, the concentration of measure problem1 can be cast as the following optimization problem:
minimize E∈Pow(X )
µ ( E(∆) ) subject to µ(E) ≥ α. (2.1)
We focus on the case where ∆ is some `p-norm distance metric (including `∞) in this work.
Concentration of measure has been shown to be closely related to adversarial examples (Gilmer et al., 2018; Fawzi et al., 2018; Mahloujifar et al., 2019a). In particular, one can prove that for a given robust learning problem, if the input distribution is concentrated with respect to the perturbation metric, no adversarially robust model exists. The concentration parameter (which corresponds to the optimal value of optimization problem (2.1)) determines an inherent upper bound on the maximum adversarial robustness that any model can achieve for the given problem.
To explain the connection between concentration of measure and robust learning in a more formal way, we lay out the definition of adversarial risk that we work with. We draw this definition from several previous works, including Gilmer et al. (2018); Bubeck et al. (2019); Mahloujifar et al. (2019a;b).2 Definition 2.1 (Adversarial Risk). Let (X , µ,∆) be the input metric probability space. Assume f∗ is the underlying ground-truth classifier that gives labels to any input. Given classifier f and ≥ 0, the adversarial risk of f with respect to -perturbations measured by ∆ is defined as:
AdvRisk (f) = Pr x∼µ
[ ∃ x′ ∈ B(x, ,∆) s.t. f(x′) 6= f∗(x′) ] .
Correspondingly, we define the adversarial robustness of f as AdvRob (f) = 1−AdvRisk (f).
When = 0, adversarial risk degenerates to standard risk. In other words, it holds for any f that AdvRisk0(f) = Risk(f) := Prx∼µ[f(x) 6= f∗(x)]. We remark that this definition assumes the existence of an underlying ground-truth labeling function, which does not apply to the agnostic setting where inputs can have non-deterministic labels.
Initially introduced in Mahloujifar et al. (2019b), intrinsic robustness captures the maximum adversarial robustness that can be achieved by any imperfect classifier for a robust classification problem. Definition 2.2 (Intrinsic Robustness). Consider the same setting as in Definition 2.1. For any α > 0, let Fα = {f : Risk(f) ≥ α} be the set of imperfect classifiers whose risk is at least α. Then the intrinsic robustness of the given robust classification problem with respect to Fα is defined as:
AdvRob (Fα) = 1− inf f∈Fα
{ AdvRisk (f) } = sup f∈Fα {AdvRob (f)}.
It is worth noting that the value of AdvRob (Fα) is only determined by the underlying input data distribution, the perturbation set and the risk threshold parameter α, which is independent of the model class one would choose for learning.
By relating the robustness of a classifier to the -expansion of its induced error region, the following lemma, proved in Mahloujifar et al. (2019a), establishes a fundamental connection between the concentration of measure and the intrinsic robustness one can hope for a robust classification problem.
Lemma 2.3. Consider the same setting as in Definition 2.2. Let h(∆)µ (α, ) be the concentration function that captures the optimal value of the concentration of measure problem (2.1):
h(∆)µ (α, ) = inf { µ ( E(∆) ) : E ∈ pow(X ) and µ(E) ≥ α } .
Then, AdvRob (Fα) = 1− h(∆)µ (α, ) holds for any α > 0 and ≥ 0. 1The standard notion of concentration of measure (Talagrand, 1995) corresponds to the case where α = 0.5. 2Other related definitions, such as the one used in most empirical works for robustness evaluation, are equivalent to this, as long as small perturbations preserve the ground truth. See Diochnos et al. (2018) for a detailed comparison of these and other definitions of adversarial robustness.
Lemma 2.3 suggests that one can characterize the intrinsic robustness limit for a robust classification problem by measuring the concentration of the input data with respect to the perturbation metric.
In this paper, we aim to understand and empirically estimate the intrinsic robustness limit for typical robust classification tasks by measuring concentration. It is worth noting that solving the concentration problem (2.1) itself only shows the existence of an error region E whose -expansion has certain (small) measure. This further implies the possibility of existing an optimally robust classifier (with risk at least α), whose robustness matches the intrinsic robustness limit AdvRob (Fα). However, actually finding such optimal classifier using a learning algorithm might be a much more challenging task, which is beyond the scope of this work.

heading: 3 GENERALIZING THE GAUSSIAN ISOPERIMETRIC INEQUALITY
text: Before proceeding to introduce the proposed methodology for solving the concentration of measure problem, we first present our main theoretical results of generalizing the Gaussian Isoperimetric Inequality. This theoretical result largely motivates our method.
To begin with, we introduce the Gaussian Ispoperimetric Inequality (Sudakov & Tsirelson, 1974; Borell, 1975). It characterizes the optimum of the concentration problem (2.1) with respect to standard Gaussian distribution and `2-distance, where half spaces are proven to be the optimal sets. Definition 3.1 (Half Space). Let w ∈ Rn and b ∈ R. Without loss of generality, assume ‖w‖2 = 1. An n-dimensional half space with parameters w and b is defined as:
Hw,b = {z ∈ Rn : w>z + b ≤ 0}. Lemma 3.2 (Gaussian Isoperimetric Inequality). Consider the standard Gaussian space (Rn, γn) with `2-distance. Let E ∈ pow(Rn) and H be a half space such that γn(E) = γn(H), then for any ≥ 0, it holds that
γn ( E(`2) ) ≥ γn ( H(`2) ) = Φ ( Φ−1 ( γn(E) ) + ) .
The proof of the Gaussian Isoperimetric Inequality can be found in Ledoux (1996). Lemma 3.2 implies the concentration function of (Rn, γn, ‖ · ‖2) is h(`2)γn (α, ) = Φ ( Φ−1(α) + ) , but only applies when the underlying distribution is a spherical Gaussian and the metric function is `2- distance. Thus, it only gives a concentration function for estimating the the intrinsic robustness limit in a very restrictive setting. To understand the concentration of measure for more general problems, we prove the following theorem that extends the standard Gaussian Isoperimetric Inequality (Lemma 3.2) to non-spherical Gaussian measure and general `p-norm distance metrics for any p ≥ 2. Theorem 3.3 (Generalized Gaussian Isoperimetric Inequality). Let ν be the probability measure of N (θ,Σ), where θ ∈ Rn and Σ is a positive definite matrix in Rn×n. Consider the probability space (Rn, ν) with `p-norm distance, where p ≥ 2 (including `∞). For any E ∈ pow(Rn) and ≥ 0,
ν ( E(`p) ) ≥ Φ ( Φ−1 ( ν(E) ) + /‖Σ1/2‖p ) , (3.1)
where Σ1/2 is the square root of Σ, and ‖Σ1/2‖p denotes the induced matrix p-norm of Σ1/2. Remark 3.4. Theorem 3.3 suggests that for general Gaussian distribution N (θ,Σ) and any `pnorm distance (p ≥ 2), the corresponding concentration function is lower bounded by Φ(Φ−1(α) + /‖Σ1/2‖p). Due to the NP-hardness of approximating the matrix p-norm (Hendrickx & Olshevsky, 2010), it is generally hard to infer whether the equality of (3.1) can be attained or not. However, for specific special Gaussian spaces, we can derive optimal subsets that achieve the lower bound. In particular, for the case where Σ = In and p > 2, the optimum is attained when E is a half space with axis-aligned weight vector (that is,w = ej for some j ∈ [n]). For the case where Σ 6= In and p = 2, the optimal solution is a half space Hv1,b, where v1 is the eigenvector with respect to the largest eigenvalue of Σ. The proofs of these optimality results are provided in Appendix A.2.

heading: 4 EMPIRICALLY MEASURING CONCENTRATION USING HALF SPACES
text: Recall that the primary goal of this paper is to measure the concentration of an arbitrary distribution. However, for typical classification problems, we might not know the density function of the underlying
distribution µ, but instead we usually have access to a finite set of m instances {xi}i∈[m] sampled from µ. Following Mahloujifar et al. (2019b), we consider the following empirical counterpart of the actual concentration problem (2.1):
minimize E∈G
µ̂m ( E(∆) ) subject to µ̂m(E) ≥ α, (4.1)
where µ̂m is the empirical measure based on {xi}i∈[m] and G ⊆ pow(X ) denotes a particular collection of subsets. Mahloujifar et al. (2019b) proposed the complement of union of T hyperrectangles as G for `∞ and the union of T balls for `2. They proved that if one increases the complexity parameter T and the sample size m together in a careful way, the optimal value of the empirical concentration problem (4.1) converges to the actual concentration asymptotically. However, it is unclear how quickly it converges and how well the proposed heuristic algorithm in Mahloujifar et al. (2019b) finds the optimum of (4.1).
In this work, we argue that the set of half spaces is a superior choice for G with respect to any `p-norm distance. Apart from achieving the optimality for certain Gaussian spaces as discussed in Remark 3.4, estimating concentration using half spaces has several other advantages including the closed-form solution of `p-distance to half-space (Lemma 4.1) and its small sample complexity requirement for generalization (Theorem 4.2). To be more specific, we focus on the following optimization problem based on the empirical measure µ̂m and the collection of half spacesHS(n):
minimize E∈HS(n)
µ̂m ( E(`p) ) subject to µ̂m(E) ≥ α, (4.2)
whereHS(n) = {Hw,b : w ∈ Rn, b ∈ R, and ‖w‖2 = 1} is the set of all half spaces in Rn. The following lemma, proven in Appendix B.1, characterizes the closed-form solution of the `p-norm distance between a point x and a half space. Such a formulation enables an exact computation of the empirical measure with respect to the -expansion of any half space. Lemma 4.1 (`p-Distance to Half Space). LetHw,b ∈ HS(n) be an n-dimensional half space. For any vector x ∈ Rn, the `p-norm distance (p ≥ 1) from x toHw,b is:
dp(x,Hw,b) = {
0, w>x+ b ≤ 0; (w>x+ b)/‖w‖q, otherwise.
Here, q is a real number that satisfies 1/p+ 1/q = 1.
Lemma 4.1 implies that the -expansion of any half space with respect to the `p-norm is still a half space. Since the VC-dimensions of both the set of half spaces and its expansion are bounded, we can thus apply the generalization theorem in Mahloujifar et al. (2019b), which yields the following theorem, proved in Appendix B.2, that characterizes the generalization of concentration with respect to the collection of half spaces. Theorem 4.2 (Generalization of Concentration of Half Spaces). Consider the metric probability space, (X , µ, ‖ · ‖p), where X ⊆ Rn and p ≥ 1. Let {xi}i∈[m] be a set of m instances sampled from µ, and let µ̂m be the corresponding empirical measure. Define the concentration functions regarding the collection of half spacesHS(n) with respect to µ as:
h(`p)µ ( α, ,HS(n) ) = inf E∈HS(n) { µ ( E(`p) ) : µ(E) ≥ α } ,
and let h(`p)µ̂m (α, ,HS(n)) be its empirical counterpart with respect to µ̂m. For any δ ∈ (0, 1), there exists constants c0 and c1 such that with probability at least 1− c0 · e−n logn,
h (`p) µ̂m
( α− δ, ,HS(n) ) − δ ≤ h(`p)µ ( α, ,HS(n) ) ≤ h(`p)µ̂m ( α+ δ, ,HS(n) ) + δ
holds, provided that the sample size m ≥ c1 · n log n/δ2. Remark 4.3. Theorem 4.2 suggests that for the concentration of measure problem with respect to half spaces, in order to achieve δ estimation error with high probability, it requires Ω(n log(n)/δ2) number of samples. Compared with Mahloujifar et al. (2019b), our method using half spaces requires fewer samples in theory to achieve the same estimation error.3 For standard Gaussian
3The proposed estimators for `∞ and `2 in Mahloujifar et al. (2019b) require Ω(nT log(n) log(T )/δ2) samples to achieve δ approximation, where T is a predefined number of hyperrectangles or balls.
inputs, the empirical concentration with respect to half spaces is guaranteed to converge to the actual concentration as in (2.1), i.e., limm→∞ h
(`p) µ̂m
( α, ,HS(n) ) = h (`p) µ ( α, ) ; whereas for distributions
that are not Gaussian, there might exist a gap. However, this gap of empirical and actual concentration is shown to be uniformly small across various data distributions, as will be discussed in Section 6.2.
Based on Lemma 4.1, estimating the empirical concentration using half spaces as defined in (4.2) is equivalent to solving the following constrained optimization problem:
minimize w∈Rn,b∈R ∑ i∈[m] 1{w>xi + b ≤ ‖w‖q}
subject to 1
m ∑ i∈[m] 1{w>xi + b ≤ 0} ≥ α and ‖w‖2 = 1. (4.3)
The optimal solution to (4.3) would be a half spaceHw,b that satisfies the following two properties: (1) approximately α-fraction of data is covered byHw,b, and (2) most of the remaining data points are at least -away fromHw,b under `p-norm distance metric.
Note that we can always set b to be the α-quantile of the projections {−w>xi : i ∈ [m]} to satisfy the first property. In addition, to satisfy the second condition, inspired by the special case optimality results in Remark 3.4, we propose to search for a weight vector w such that both the `q-norm of w is small and the variation of the given sample set along the direction of w is large. These searching criteria guarantee that the given dataset {xi}i∈[m], when projected onto w then normalized by ‖w‖q , will have a large variance, which implies the second property.
We propose a heuristic algorithm to search for the desirable half space according to the aforementioned criteria (for the pseudocode and a detailed analysis of the algorithm, see Appendix C). It first conducts a principal component analysis with respect to the given empirical dataset, then iterates through all the principal components raised to an arbitrary power with normalization as candidate choices of the weight vectorw. Finally, based on the optimal choice of b, the algorithm outputs the bestHw,b that achieves the smallest empirical measure with respect to the -expansion of Hw,b. As we see in the experiments in the next section, this algorithm is able to find near-optimal solutions to the concentration problem for various datasets.

heading: 5 ERROR ANALYSIS
text: The goal of measuring concentration is to provide an empirical estimate of concentration of measure that minimizes the overall approximation error. Here, we describe the error components based on the general empirical framework for measuring concentration, and then discuss its implications on how to choose the collection of subsets G for the empirical concentration problem (4.1).
Error Decomposition. Let (X , µ,∆) be the underlying input metric probability space and G be the selected collection of subsets for the empirical concentration problem. Suppose an algorithm that aims to solve the empirical concentration problem (4.1) returns E as a solution. For any α ∈ (0, 1) and ≥ 0, the approximation error between the empirical estimate of concentration and the actual concentration can be decomposed into three error terms:
h(∆)µ (α, )− µ̂m(E(∆) )︸ ︷︷ ︸ approximation error = h(∆)µ (α, )− h(∆)µ (α, ,G)︸ ︷︷ ︸ modeling error + h(∆)µ (α, ,G)− h (∆) µ̂m (α, ,G)︸ ︷︷ ︸ finite sample estimation error
+ h (∆) µ̂m (α, ,G)− µ̂m(E(∆) )︸ ︷︷ ︸ optimization error . (5.1)
The modeling error denotes the difference between the actual concentration function and the concentration function with respect to the selected collection of subsets G; the finite sample estimation error represents the generalization gap between the empirical concentration function and its limit; and the optimization error captures how well the algorithm approximates the empirical concentration problem. Such an error decomposition applies to both the empirical method proposed in this work as well as Mahloujifar et al. (2019b)’s, despite the different choices of G.
The complexity of G and the complexity of its -expansion G = {E : E ∈ G} control the finite sample estimation error. So, G should be selected such that the empirical concentration function h
(∆) µ̂m (α, ,G) generalizes. If either G or G is too complex (e.g., it has unbounded VC-dimension), it will be difficult to control the generalization of the empirical concentration function (see Remark 3.4 in Mahloujifar et al. (2019b) for a detailed discussion).
There exist tradeoffs among the three error terms in (5.1), and it is unlikely that there is a uniformly good choice for G that minimizes all these error terms. In particular, increasing the complexity of G typically reduces the modeling error, since the feasible set of the concentration function with respect to G becomes larger. However, according to the generalization of concentration, this will also increase the finite sample estimation error. Therefore, we should consider the effect of all these error terms when choosing G, including the hardness of the optimization problem with respect to the empirical concentration. It is favorable that the distance to any set in G has a closed-form solution, which enables exactly computing the empirical measure of the -expansion of any set in G. In addition, it will be easier to control the optimization error (i.e., develop an algorithm that produces tight estimates), if the empirical concentration problem is simpler. For instance, solving the empirical concentration problem with respect to the set of half spaces should be easier than solving it based on the union of hyperrectangles or balls, since there are more hyperparameters to optimize for the latter problem. Such simplicity further contributes to a tighter empirical estimate produced by our algorithm for the underlying concentration of measure problem.
Depending on the underlying distance metric Mahloujifar et al. (2019b) set G as a collection of the union of complement of hyperrectangles or the union of balls, whereas we choose G as the set of half spaces for any `p-norm distance. In this work, we show that the set of half spaces is a superior choice of G for measuring the concentration of typical image benchmarks. Other choices of G may be preferred for different settings, but the same error decomposition and criteria will apply.

heading: 6 EXPERIMENTS
text: In this section, we evaluate our empirical method for estimating concentration under `∞-norm distance and comparing its performance to that of the method proposed by Mahloujifar et al. (2019b). We first demonstrate that the estimate produced by our algorithm is very close to the actual concentration for a spherical Gaussian distribution, and that our method is able to find much tighter bounds on the best possible adversarial risk for several image benchmarks. We then compare the convergence rates, and show that our method converges with substantially less data. Note that while we only provide results for the most widely-used `∞-norm perturbation metric adopted in the existing adversarial examples literature, our algorithm and experiments can be applied to any other `p-norm.

heading: 6.1 ESTIMATION ACCURACY
text: First, we evaluate the performance of our algorithm under `∞-norm distance metric on a generated synthetic dataset consisting of 30,000 samples from N (0, I784). Since the proposed method follows from the analytical results of concentration of multivariate Gaussian distributions, we expect results produced by our empirical method to closely approach the analytical concentration on this simulated Gaussian dataset. We initially consider the case where = 1.0 and α = 0.5 for the actual concentration problem, requiring that the feasible set contains at least half of the data samples, and the adversary can perturb each entry by precisely the standard deviation of the underlying distribution. Our algorithm is able to produce a half space whose -expansion has mean empirical measure 84.18% over 5 repeated trials. According to Theorem 3.3 and Remark 3.4, the optimal value of the considered concentration problem is 84.13%. This implies that our method performs very well when the underlying distribution is Gaussian, while in stark contrast, the method by Mahloujifar et al. (2019b) is not able to find a region whose expansion has measure less than 1 on the same simulated set. In addition, we consider another setting for this dataset where = 1.0 is set the same and α = 0.05 is set to be much smaller. Similarly, we observe that our method significantly outperforms Mahloujifar et al. (2019b)’s in terms of the estimation accuracy (see Table 1 for the detailed comparison results).
Next, we evaluate our method on several image benchmarks. We set the values of α and to be the same as in Mahloujifar et al. (2019b) for the `∞ case. For example, we use α = 0.01, ∈
{0.1, 0.2, 0.3, 0.4} for MNIST, and α = 0.05, ∈ {2/255, 4/255, 8/255, 16/255} for CIFAR-10. These α values were selected to roughly represent the standard error of the state-of-the-art classifiers.
Table 1 demonstrates the risk and adversarial risk with respect to the best produced subsets using both methods, computed on a separate test dataset. In our context of measuring concentration, risk refers to the empirical measure of the produced subset, while adversarial risk corresponds to the empirical measure of its -expansion. We use a 50/50 train-test split over the whole dataset to perform our evaluation, and determine the best exponent of each principal component based on a brute-force search. Though our method is deterministic for a given pair of training and testing sets, we account for the variance of our method over different train-test splits by repeating our experiments 5 times and reporting the mean and standard deviation of the results for each (α, ). It is worth noting that the randomness of the previous method is derived not only from the selection of the training and test sets, but also from the inherent randomness of the employed k-means algorithm.
We observe from Table 1 that in every case, the estimated adversarial risk is significantly lower for our method than for the one found by Mahloujifar et al. (2019b)’s. Since both methods restrict the search space to some special collection of subsets, these estimates can be viewed as valid empirical upper bounds of the actual concentration as defined in (2.1). Therefore, the fact that our results are significantly lower indicates that our algorithm is able to produce estimates that are much closer to the optimum of the targeted problem. In addition, when translated to adversarial robustness, these tighter estimates prove the existence of a rather robust classifier4 that has risk at least α, which further suggests that the underlying intrinsic robustness limit of each of these image benchmarks is actually much higher than previously thought.
For example, the best classifier produced by Mahloujifar et al. (2019b) has 18.1% adversarial risk under `∞-perturbations bounded by = 8/255 on CIFAR-10. However, our results demonstrate that the adversarial risk of the best possible robust classifier can be as low as 6.3% given the same risk constraint, indicating the underlying intrinsic robustness to be above 93.7%. As the intrinsic robustness limits are shown to be very close to the trivial upper bound 1− α across all the settings, our results reveal that the concentration of measure phenomenon is not an important factor that causes the adversarial vulnerability of existing classifiers on these image benchmarks.
4Based on the ground-truth f∗ and the returned set E of our algorithm, this classifier can be simply constructed by setting f(x) = f∗(x) for x /∈ E and f(x) 6= f∗(x) for x ∈ E . Without knowing the ground-truth, we note that such classifier may or may not be learnable. The learnability of such f is beyond the scope of this paper.

heading: 6.2 CONVERGENCE
text: Figure 6.2 shows the convergence rate of our method compared with that of the method proposed by Mahloujifar et al. (2019b) under `∞-distance for Gaussian data from N (0, I784) (α = 0.05, = 1), as well as for MNIST (α = 0.01, = 0.1) and CIFAR-10 (α = 0.05, = 2/255). We observe similar trends for other settings, thus we defer these results to Appendix D. For each graph, the horizontal x-axis represents the size of the dataset used to train the estimator, and the vertical y-axis shows the concentration bounds estimated for a separate test set, which is of size 30, 000 for each case. We generate the means and standard deviations for these convergence curves by repeating both methods 5 times for different randomly-selected training and test tests. For the proposed algorithm in Mahloujifar et al. (2019b), we tune the number of the hyperrectangles T for the optimal performance based on the empirically-observed adversarial risk.
For the simulated Gaussian datasets, we include a horizontal line at y = 0.2595 to represent the true concentration of the underlying distribution, derived from Theorem 3.3 and Remark 3.4. This allows us to more accurately assess the convergence of our method, as it is the only case for which we know the optimal value that our empirical estimates should be converging to. We see that our estimates approach this line very quickly, coming within 0.01 of the true value given only about 1,000 samples.
While we do not have such a theoretical limit for other datasets, the risk threshold α can be viewed as a lower bound of the actual concentration, which is useful in visually assessing the convergence performance of our method. We can see that for both MNIST and CIFAR-10, our estimates get very close to the horizontal line at y = α given several thousand training samples. Since the actual concentration must be no less than α and our estimated upper bound is approaching α from the above, we immediate infer that the actual concentration of these data distributions with `∞-norm distance should be a value sightly greater than α. These results not only demonstrate the superiority of our method over the method of Mahloujifar et al. (2019b) in estimating concentration, but also show that concentration of measure is not the reason for our inability to find adversarially robust models for these image benchmarks.

heading: 7 CONCLUSION
text: Our results advance understanding of the intrinsic limits of adversarial robustness, strengthening the conclusion from Mahloujifar et al. (2019b) which asserted that concentration of measure is not the sole cause of the vulnerability of existing classifiers to adversarial attacks. We generalized the standard Gaussian Isoperimetric Inequality, and then leveraged theoretical insights from that to construct an efficient method for empirically estimating the concentration of arbitrary data distribution using samples. Our method is able to generalize to any `p-norm distance metric, and surpasses previous approaches in both estimation accuracy and data-efficiency.
AVAILABILITY
An implementation of our method, and code for reproducing our experiments, is available under an open source license from https://github.com/jackbprescott/EMC_HalfSpaces.

heading: ACKNOWLEDGEMENTS
text: This work was partially funded by an award from the National Science Foundation SaTC program (Center for Trustworthy Machine Learning, #1804603). We thank Saeed Mauloujifar and Mohammad Mahmoody for valuable comments and discussions.

heading: A PROOFS OF MAIN RESULTS IN SECTION 3
text: In this section, we provide the detailed proofs of our main theoretical results presented in Section 3.
A.1 PROOF OF THEOREM 3.3
Before proving Theorem 3.3, we first lay out the following lemma regarding the monotonicity of `p-norms. For a rigorous proof of this lemma, see Raıssouli & Jebril (2010). Lemma A.1 (Monotonicity of `p). For any vector x ∈ Rn, the mapping p→ ‖x‖p is monotonically decreasing for any p ≥ 1 (including p =∞). That said, ‖x‖p ≤ ‖x‖q holds for any p ≥ q ≥ 1.
Now, we are ready to prove Theorem 3.3. In particular, we first include a high-level proof sketch, then present the complete proof after.
Proof Sketch of Theorem 3.3. We start with the spherical Gaussian distribution where ν = γn. More specifically, we are going to prove that for any E ⊆ Rn and η ≥ 0,
γn ( E(`p)η ) ≥ Φ ( Φ−1 ( γn(E) ) + η ) holds for p ≥ 2. (A.1)
Note that for any vector x ∈ Rn, the mapping p→ ‖x‖p is monotonically decreasing for any p ≥ 1, thus we can show that E(`q)η ⊆ E(`p)η holds for any p ≥ q ≥ 1. Making use of the standard Gaussian Isoperimetric Inequality (Lemma 3.2), we then immediately obtain
γn ( E(`p)η ) ≥ γn ( E(`2)η ) ≥ Φ ( Φ−1 ( γn(E) ) + η ) , for any p ≥ 2.
Moreover, to prove the concentration bound for general case where ν is the probability measure of N (θ,Σ), we build connections with the spherical Gaussian case by constructing a subset A = {Σ−1/2(x− θ) : x ∈ E}. Based on the affine transformation of Gaussian measure, we then prove:
ν(E) = γn(A) and ν(E(`p) ) ≥ γn(A(`p)η ), where η = /‖Σ1/2‖p. (A.2) Finally, combining (A.1) and (A.2) completes the proof of Theorem 3.3.
Complete Proof of Theorem 3.3. To begin with, we consider the special case where the underlying distribution is standard Gaussian (ν = γn). Specifically, we are going to prove that for any E ⊆ Rn and η ≥ 0,
γn ( E(`p)η ) ≥ Φ ( Φ−1 ( γn(E) ) + η ) holds for any p ≥ 2. (A.3)
Let p ≥ q ≥ 1. According to the definition of -expansion of a subset and Lemma A.1, we have E(`q)η = { x ∈ Rn : ∃ x′ ∈ E s.t. ‖x′ − x‖q ≤ η } ⊆ { x ∈ Rn : ∃ x′ ∈ E s.t. ‖x′ − x‖p ≤ η } = E(`p)η (A.4)
where the inclusion is due to the fact that ‖x′ −x‖p ≤ ‖x′ −x‖q holds for any x′ and x. Therefore, by setting q = 2 in (A.4), we further obtain that for any p ≥ 2,
γn ( E(`p)η ) ≥ γn ( E(`2)η ) ≥ Φ ( Φ−1 ( γn(E) ) + ) ,
where the second inequality is due to the standard Gaussian Isoperimetric Inequality (Lemma 3.2). Thus, we have proven (A.3).
Now we turn to proving the concentration bound for the general Gaussian case. Let UΛU> be the eigenvalue decomposition of Σ, where U ∈ Rn×n is an orthonormal matrix and Λ ∈ Rn×n is a diagonal matrix consisting of all the eigenvalues. Since Σ is positive definite, the square root of Σ can be expressed as Σ1/2 = UΛ1/2U>. Let Σ−1/2 = UΛ−1/2U> be the inverse matrix of Σ1/2.
Construct a subset A in Rn such that A = {Σ−1/2(x− θ) : x ∈ E}. Based on the construction of A, we can then prove the following results for any E ⊆ Rn and ≥ 0:
ν(E) = γn(A) and ν(E(`p) ) ≥ γn(A(`p)η ), where η = /‖Σ1/2‖p. (A.5)
First, we prove the equality ν(E) = γn(A). Since ν is the probability measure of N (θ,Σ), we have
ν(E) = Pr x∼ν [x ∈ E ] = Pr x∼ν [Σ−1/2(x− θ) ∈ A] = Pr u∼γn [u ∈ A] = γn(A), (A.6)
where the third inequality is due to the affine transformation of Gaussian random variables.
Next, we prove the remaining inequality in (A.5). By definition, for any u′ ∈ A(`p)η , there exists u ∈ A such that ‖u′ − u‖p ≤ η. Let x′ = θ + Σ1/2u′ and x = θ + Σ1/2u, then we have∥∥x′ − x∥∥ p = ∥∥Σ1/2(u′ − u)∥∥ p ≤ ‖Σ1/2‖p · ‖u′ − u‖p ≤ η‖Σ1/2‖p ≤ , (A.7)
where the first inequality is due to the definition of induced matrix p-norm and the last inequality holds because η = /‖Σ1/2‖p. By the construction of A and the fact that u ∈ A, we have x ∈ E . Combining (A.7), this further implies that for any u′ ∈ A(`p)η , θ + Σ1/2u′ ∈ E(`p) . Thus, we have
ν ( E(`p) ) ≥ ν ( θ + Σ1/2 · A(`p)η ) = Pr
x∈ν
[ Σ−1/2(x− θ) ∈ A(`p)η ] = γn ( A(`p)η ) , (A.8)
where θ + Σ1/2 · A(`p)η denotes the transformed subset {θ + Σ1/2u : u ∈ A(`p)η }. Therefore, based on (A.6) and (A.8), we prove the soundness of (A.5).
Finally, combining (A.3) and (A.5) completes the proof of Theorem 3.3.
A.2 PROOF OF THE OPTIMALITY RESULTS IN REMARK 3.4
Proof. First, we prove the optimality for the spherical Gaussian case, where ν = γn and p > 2. LetH = Hw,b be a half space with axis-aligned weight vector, that said w = ej for some j ∈ [n]. Intuitively speaking, the -expansion ofH with respect to `p-norm will only happen along the j-th dimension. More rigorously, we are going to prove the following results: for any ≥ 0,
H(`p) = H(`2) holds for any p ≥ 1. (A.9)
By definition,H = {x ∈ Rn : xj + b ≤ 0}. For any x /∈ H, let x̂ ∈ H be the closest point of x in terms of `p-norm. Since the weight vector w ofH is axis-aligned, thus x̂ will only differ from x by
the j-th element. That said, x̂j′ = xj′ for any j′ 6= j and x̂j = −b. Thus for any p ≥ 1, we have ‖x− x̂‖p = ‖x− x̂‖2 = xj + b. Based on this observation, we further obtain that for any p ≥ 1,
H(`p) = {x ∈ Rn : xj + b ≤ } = H(`2) ,
which proves (A.9). According to the Gaussian Isoperimetric Inequality (Lemma 3.2), we obtain γn ( H(`p) ) = γn ( H(`2) ) = Φ(Φ−1(γn(H)) + ).
Therefore, combining this with Theorem 3.3, we prove the optimality for the spherical Gaussian case.
Now we turn to prove the non-spherical Gaussian case with p = 2. Based on Theorem 3.3, the lower bound is Φ(Φ−1(ν(E) + /‖Σ1/2‖2) when p = 2. In the following, we are going to prove: if we choose E = Hv1,b, where v1 is the eigenvector with respect to the largest eigenvalue of Σ, this lower bound is attained. Similarly to the proof of Theorem 3.3, we constructA = {Σ−1/2(x−θ) : x ∈ E}. Note that when E is a half space, the constructed set A is also a half space. In particular, for the case where E = Hv1,b, for any u ∈ A, there exists an x ∈ Rn such that u = Σ−1/2(x − θ) and v>1 x+ b ≤ 0. This implies that v>1 Σ1/2u+v>1 θ+ b ≤ 0 for any u ∈ A. Since v1 is the eigenvector of Σ, we further have that A is a half space with weight vector Σ1/2v1 = ‖Σ1/2‖2 · v1. Note that according to (A.2), as in the proof of Theorem 3.3, for any E ⊆ Rn, we have
ν(E) = γn(A) and ν ( E(`2) ) ≥ γn ( A(`2)η ) , where η = /‖Σ1/2‖2.
For E = Hv1,b, based on the explicit formulation of `2-distance to a half space, we can explicitly compute the η-expansion of A as
A(`2)η = {u ∈ Rn : v>1 Σ1/2u+ v>1 θ + b ≤ η · ‖Σ1/2‖2}.
When we set η = /‖Σ1/2‖2, it further implies that γn ( A(`2)η ) = Pr
u∼γn
[ v>1 Σ 1/2u+ v>1 θ + b ≤ ]
= Pr x∼ν
[ v>1 x+ b ≤ ] = ν ( E(`2) ) .
Finally, according to the optimality of the standard Gaussian Isoperimetric Inequality (Lemma 3.2), this completes the proof.

heading: B PROOFS OF THEORETICAL RESULTS IN SECTION 4
text: In this section, we present the proofs to the theoretical results presented in Section 4.
B.1 PROOF OF LEMMA 4.1
Proof of Lemma 4.1. We only consider the case when w>x+ b > 0, because dp(x,Hw,b) is zero trivially holds ifw>x+ b ≤ 0. The problem of finding the `p-distance from a given point x to a half spaceHw,b can be formulated as the following constrained optimization problem:
min z∈Rn
‖z − x‖p, subject to w>z + b ≤ 0. (B.1)
Let z̃ = z − x, then optimization problem (B.1) is equivalent to
min z̃∈Rn
‖z̃‖p, subject to w>z̃ +w>x+ b ≤ 0. (B.2)
According to Hölder’s Inequality, for any z̃ ∈ Rn we have
−‖w‖q · ‖z̃‖p ≤ w>z̃ ≤ ‖w‖q · ‖z̃‖p,
where 1/p+ 1/q = 1. Therefore, for any z̃ that satisfies the constraint of (B.2), we have
w>x+ b ≤ −w>z̃ ≤ ‖w‖q · ‖z̃‖p. (B.3)
Since ‖w‖2 = 1, we have ‖w‖q > 0, thus (B.3) further suggests ‖z̃‖p ≥ (w>x+ b)/‖w‖q.
Up till now, we have proven that the optimal value of (B.1) is lower bounded by (w>x+ b)/‖w‖q. The remaining task is to show this lower bound can be achieved. To this end, we construct ẑ as
ẑj = xj − w>x+ b ‖w‖q · ( wqj∑ j∈[n]w q j )1/p , for any j ∈ [n],
where 1/p + 1/q = 1. We remark that for the extreme case where p = ∞, such choice of ẑ can be simplified as ẑ = x − (w>x + b) · sgn(w)/‖w‖q, where sgn(·) denotes the sign function for vectors. According to the construction, it can be verified that
w>ẑ + b = (w>x+ b)− w >x+ b ‖w‖q · ∑ j∈[n] wj · ( wqj∑ j∈[d]w q j )1/p = 0,
and ‖ẑ − x‖p = (w>x+ b)/‖w‖q .
B.2 PROOF OF THEOREM 4.2
Proof of Theorem 4.2. We writeHS asHS(n) for simplicity. Let S be a set of size m sampled from µ and µ̂S be the corresponding empirical measure. Note that the VC-dimension ofHS(n) is n+ 1 (see Mohri et al. (2018)), thus according to the VC inequality, we have
Pr S←µm
[ sup
E∈HS(n) ∣∣µ̂S(E)− µ(E)∣∣ ≥ δ] ≤ 8e(n+1) log(m+1)−mδ2/32. In addition, according to Lemma 4.1, the -expansion of any half space is still a half space. Therefore, we can directly apply Theorem 3.3 in Mahloujifar et al. (2019b) to bound the generalization of concentration with respect to half spaces: for any δ ∈ (0, 1), we have
Pr S←µm
[ h
(`p) µ̂S (α− δ, ,HS)− δ ≤ h(`p)µ (α, ,HS) ≤ h (`p) µ̂S
(α+ δ, ,HS) + δ ]
≥ 1− 32e(n+1) log(m+1)−mδ 2/32.
Finally, assuming the sample size m ≥ c0 · n log n/δ2 for some constant c0 large enough, then there exists positive constant c1 such that
h (`p) µ̂S (α− δ, ,HS)− δ ≤ h(`p)µ (α, ,HS) ≤ h (`p) µ̂S (α+ δ, ,HS) + δ
holds with probability at least 1− c1 · e−n logn.

heading: C ALGORITHM FOR ESTIMATING CONCENTRATION
text: Algorithm 1: Heuristic Search for Robust Half Space under `p-distance Input : a set of samples {xi}i∈[m]; strength (in `p-norm); risk threshold α; #iterations S. Q← compute the sample covariance matrix based on {xi}i∈[m]; V ← obtain the set of principal components by eigenvalue decomposition on Q; for v ∈ V do
for s = 1, 2, . . . , S do w ← select from {±pow(v, s)}; // pow() is defined according to (C.1) b← α-quantile of the set {−w>xi : i ∈ [m]}; AdvRisk (Hw,b)← ∑m i=1 1(w
>xi + b ≤ ‖w‖q)/m; end
end (ŵ, b̂)← argmin(w,b) AdvRisk (Hw,b); Output : Hŵ,̂b
To solve the empirical concentration problem (4.3), Algorithm 1 searches for a desirable half space based on the principal components of the empirical dataset and their rotations defined by a power parameter. More specifically, the function pow() takes a vector v ∈ Rn and a positive integer s ∈ Z+, and returns the normalized s-th power of v (with sign preserved):
pow(v, s) = sgn(v) ◦ [abs(v)]s/‖vs‖2 = { vs/‖vs‖2, if s is odd; sgn(v) ◦ vs/‖vs‖2, otherwise.
(C.1)
Note that all the functions used in (C.1) are element-wise operations for vectors, where sgn(v), abs(v), vs represent the sign, absolute value and the s-th power of v respectively, and the operator ◦ denotes the Hardamard product of two vectors.
Connected with the theoretical optimum regarding Gaussian spaces in Remark 3.4, the top principal component corresponds to the optimal choice ofw if the perturbation metric is `2-distance, whereas close-to-axis would be favourable for w when p > 2. In addition, as implied by the empirical concentration problem (4.3) and the monotonicity of `p-mapping (Lemma A.1), the value of ‖w‖q will be more influential in affecting the -expansion of half space as p grows larger. For example, the `∞-norm of w can be as large as √ n for the worst case (n denotes the input dimension), while ‖w‖∞ = 1 if w aligns any axis. By searching through the region between each principal component and the closest axis, the proposed algorithm aims to find the optimal balance between ‖w‖q and the variance of the given data along w that leads to the smallest -expansion. Although there is no theoretical guarantee that our algorithm will find the optimum to (4.3) for an arbitrary dataset, we empirically show (in Section 6) its efficacy in estimating concentration across various datasets.
Moreover, our algorithm is efficient in terms of both time and space complexities. Precomputing the principal components requires O(mn2 + n3) time and O(n2) space to store them, where m denotes the samples size and n is the input dimension. For each iteration step, the time complexity of computing w, b and AdvRisk (Hw,b) is O(mn), while the space complexity for saving the intermediate variables and the best parameters is O(m + n). With n outer iterations and S inner iterations, the total time complexity is O(n3 +mn2S). The total space complexity is O(n2 +mn), where the extra O(mn) denotes the initial space requirement for saving all the input data. For our experiments, we observe AdvRisk (Hw,b) is not sensitive to small increment of the exponent parameter s, thus we choose to increase s in a more aggressive way, which further saves computation.

heading: D ADDITIONAL EXPERIMENTS
text: Figure 2 shows the convergence performance of our algorithm under different experimental settings: α = 0.5, = 1 for the simulated Gaussian dataset, α = 0.01, = 0.4 for MNIST, and α = 0.05, = 16/255 for CIFAR-10. Under these additional settings, the algorithm proposed by Mahloujifar et al. (2019b) either cannot provide meaningful estimates of concentration, or takes a substantial amount of time to run. For instance, our algorithm takes around 2 days to generate the convergence curve on CIFAR-10 (α = 0.05, = 16/255), whereas the previous method is at least 5 times slower, due to the large number of rectangles T needed. Thus, we only report the convergence curves of our method, where the standard deviations are calculated over 3 repeated trials.

Review summaries:
The authors generalized the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures with $\ell_p$ metric structures $p\geq 2$. Building on the generalized inequality, they propose a sample-based algorithm to estimate the concentration of measure using half-spaces. The main contribution is Theorem 3.3 followed by the empirical sample based algorithm for half-spaces that requires $\Omega(n\log(n) /\delta^2)$ samples.

The authors consider the problem of estimating intrinsic robustness using data samples. At a high level, intrinsic robustness is a measure that indicates the probability that a noisy version of a covariate would not be mislabeled. Mahloujifar et al. (2019a) have shown that estimating intrinsic robustness is closely related to the problem of estimating the concentration of measure. This problem focuses on finding a region such that it has the least likely epsilon neighborhood. In this work, the authors provide an efficient algorithm for measuring concentration empirically, which yields a more accurate estimation of the intrinsic robustness compared to the previous results.  

This paper considers the estimation of the concentration of measures, which possibly causes of the vulnerability of machine learning models to adversarial attacks. Towards such a goal, the authors first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures and arbitrary l_p norm. An algorithm that uses half-spaces as feasible set in the concentration of measure problem is then proposed. Empirical studies are conducted to show the efficiency as well as the efficacy of the proposed method when compared to [Mahloujifar et al. (2019b)].