extfieldsofstudy:
Computer Science
Mathematics

text:
Learning discrete distributions: user vs item-level privacy

Much of the literature on differential privacy focuses on item-level privacy, where loosely speaking, the goal is to provide privacy per item or training example. However, recently many practical applications such as federated learning require preserving privacy for all items of a single user, which is much harder to achieve. Therefore understanding the theoretical limit of user-level privacy becomes crucial. We study the fundamental problem of learning discrete distributions over $k$ symbols with user-level differential privacy. If each user has $m$ samples, we show that straightforward applications of Laplace or Gaussian mechanisms require the number of users to be $\mathcal{O}(k/(m\alpha^2) + k/\epsilon\alpha)$ to achieve an $\ell_1$ distance of $\alpha$ between the true and estimated distributions, with the privacy-induced penalty $k/\epsilon\alpha$ independent of the number of samples per user $m$. Moreover, we show that any mechanism that only operates on the final aggregate should require a user complexity of the same order. We then propose a mechanism such that the number of users scales as $\tilde{\mathcal{O}}(k/(m\alpha^2) + k/\sqrt{m}\epsilon\alpha)$ and further show that it is nearly-optimal under certain regimes. Thus the privacy penalty is $\mathcal{O}(\sqrt{m})$ times smaller compared to the standard mechanisms. We also propose general techniques for obtaining lower bounds on restricted differentially private estimators and a lower bound on the total variation between binomial distributions, both of which might be of independent interest.

Differential privacy is studied in two scenarios, local differential privacy [Kasiviswanathan et al., 2011, Duchi et al., 2013, and global differential privacy [Dwork et al., 2006]. In this paper, we study the problem under the lens of global differential privacy, where the goal is to protect the privacy of the algorithm outcomes. Before we proceed further, we first define differential privacy.
Definition 1. A randomized mechanism M : D → R with domain D and range R satisfies (ε, δ)differential privacy if for any two adjacent datasets D, D ∈ D and for any subset of output S ⊆ R, it holds that P r[M(D) ∈ S] ≤ e ε P r[M(D ) ∈ S] + δ.
If δ = 0, then the privacy is also referred to as pure differential privacy. An important aspect of the above definition is the notion of neighboring or adjacent datasets. If a dataset D is a collection of n items x 1 , x 2 , . . . x n , then typically adjacent datasets are defined as those that differ in a single item x i [Dwork et al., 2006].
However, in practice, each user may have many items and may wish to preserve privacy for all of them. Hence, this simple definition of item-level neighboring datasets would not be enough. For example, if each user has infinitely many points of the same example, then the bounds become vacuous.
Motivated by this, user-level privacy was proposed recently. Formally, given s users where each user u has m u items x 1 (u), x 2 (u), . . . x mu (u), then two datasets are adjacent if they differ in data of a single user. For example, in the simple setting when each user has m samples, if two datasets are adjacent in user-level privacy, they could differ in at most m items under this definition of item level privacy.
Since user-level privacy is more practical, it has been studied in the context of learning machine learning models via federated learning [McMahan et al., 2017, Wang et al., 2019, Augenstein et al., 2019. The problem of bounding user contributions in user-level privacy in the context of both histogram estimation and learning machine learning models was studied in Amin et al. [2019]. Differentially private SQL with bounded user contributions was proposed in Wilson et al. [2019]. Understanding trade-offs between utility and privacy in the context of user-level global DP is one of the challenges in federated learning [Kairouz et al., 2019, Section 4.3.2].
Our goal is to understand theoretically the utility-privacy trade-off for user-level privacy and compare it to the item-level counterpart. To this end, we study the problem of learning discrete distributions under user and item level privacy.

Learning discrete distributions
Learning discrete distributions is a fundamental problem in statistics with practical applications that include language modeling, ecology, and databases. In many applications, the underlying data distribution is private and sensitive e.g., learning a language model from user-typed texts. To this end, learning discrete distributions under differential privacy has been studied extensively with various loss functions and non-asymptotic convergence rates [Braess and Sauer, 2004, Kamath et al., 2015, Han et al., 2015, with local differential privacy [Duchi et al., 2013, Kairouz et al., 2016, Acharya et al., 2019a, Ye and Barg, 2018, with global differential privacy [Diakonikolas et al., 2015, Acharya et al., 2020, and with communication constraints [Barnes et al., 2019, Acharya et al., 2019a, among others.
Before we proceed further, we first describe the learning scenario. Let p be an unknown distribution over symbols 1, 2, . . . , k i.e., i p i = 1 and p i ≥ 0 for all i ≤ k. Let ∆ k be the set of all discrete distributions over the domain [k] := {1, 2, . . . , k}.
Suppose there are s users indexed by u, and let U denote the set of all users. We assume that each user u has m i.i.d. samples X m (u) = [X 1 (u), X 2 (u), . . . , X m (u)] ∈ X := [k] m from p 1 . Let X s = [(u, X m (u)) : u ∈ U] ∈ X s be the collection of user and sample pairs. The case when each user has samples from different distributions is an interesting open question, but it is not within the scope of this paper.
For an algorithm A, letp A (X s ) be its output, which is a mapping from X s → ∆ k . The performance for a given sample X s is measured in terms of 1 distance, 1 (p,p A ) = k i=1 |p i −p A i (X s )|. We measure the performance of the estimator for a distribution p by its expectation over the algorithm and samples i.e., We define the user complexity of an algorithm A as the minimum number of users required to achieve error at most α for all distributions: The min-max user complexity is Well known results on non-private discrete distribution estimation (see [Kamath et al., 2015, Han et al., 2015) characterize the min-max user complexity as follows: Let A ε,δ be the set of all (ε, δ) differentially private algorithms. Similar to (1), for a differentially private algorithm A, let S A m,α,ε,δ be the minimum of samples necessary to achieve α error for all distributions p ∈ ∆ p with (ε, δ) differential privacy. We are interested in characterizing and developing polynomial-time algorithms that achieve the min-max user complexity of (ε, δ) differentially private mechanisms.

Previous results
The min-max rate of learning discrete distributions for item level privacy, which corresponds to m = 1, was studied by Diakonikolas et al. [2015] and Acharya et al. [2020]. They showed that for any (ε, δ) estimator: The goal of our work is to understand the behavior of S * m,α,ε,δ w.r.t. m. We first discuss a few natural algorithms and analyze their user complexities.
One natural algorithm is for each user to sample one item and use known results from item level privacy. Such a result would yield, . 1 We extend our algorithms to the case when users have different number of samples in Appendix E.

3
The other popular algorithms are Laplace or Gaussian mechanisms that rely on counts of users. For a particular user sample X m (u), let N (u) = [N 1 (u), . . . , N k (u)], be the vector of counts. A natural algorithm is to sum all the user contributions to obtain the overall count vector N , where the count of a symbol i is given by Finally a non-private estimator can be obtained by computing the empirical estimate: To obtain a differentially private version of the empirical estimate, one can add Laplace or Gaussian noise with some suitable magnitude. To this end, we need to compute the sensitivity of the empirical estimate.
Recall that two datasets D, D are adjacent if there exists a single user u such that N (u, D) = N (u, D), and N (v, D) = N (v, D ) for all v ∈ U and v = u. Therefore the 1 sensitivity is and the 2 sensitivity is A widely used method is the Laplace mechanism, which ensures (ε, 0) differential privacy.
Definition 2. Given any function f that maps the dataset to R k , let the 1 sensitivity ∆(f ) = max D,D adjacent ||f (D) − f (D )|| 1 . The Laplace mechanism is defined as: where Y i are i.i.d random variables drawn from Lap(∆f /ε).
The Gaussian mechanism is defined similarly with 2 sensitivity and Gaussian noise. We first analyze Laplace and Gaussian mechanisms under user-level privacy.
Lemma 1. For the Laplace mechanism, given bŷ Similarly if ε ≤ 1, for the Gaussian mechanism, given bŷ The proof follows from the definitions of the Laplace and Gaussian mechanisms, which we provide in Appendix A for completeness. The non-private user complexity term O(k/(mα 2 )) decreases with the number of samples from user m, but somewhat surprisingly the additional term due to privacy O(k/αε) is independent of m. In other words, no matter how many samples each user has, it does not help to reduce the privacy penalty in the user complexity. This could be especially troublesome when m gets large, in which case the privacy term dominates the user complexity.

New results
We first ask if the above results on Laplace and Gaussian mechanisms are tight. We show that they are by proving a lower bound on a wide class of estimators that only rely on the final count. The proof is based on a novel coupling technique with details explained in Section 4 .
Theorem 1. Let ε + δ < c, where c is determined in the proof later. Let A be any (ε, δ) mechanism that only operates on summed counts of all users N = [N 1 , N 2 , . . . N k ] directly. Then, The above lower bound suggests that any algorithm that only operates on the final count aggregate would incur additional cost for user complexity independent of m due to privacy restriction. However it may not apply to algorithms that do not solely rely on the counts, which justifies the need to design algorithms beyond straightforward applications of the Laplace or Gaussian mechanisms.
We proceed to design algorithms that exceed the above user-complexity limit. The first one is for the dense regime where k ≤ m: on average each user sees most of the high-probability symbols. The second one is for the sparse regime where k ≥ m: users don't see many symbols. By combining the two of them, we get the following improved upper bound on min-max user complexity.
Theorem 2. Let ε ≤ 1. There exists a polynomial time algorithm (ε, δ)-differentially private algorithm A such that The algorithm in Theorem 2 assumes that all users have the same number of samples. In Appendix E, we modify it to the setting when users have different number of samples. The sample complexity is similar to (3), with m replaced by m median , the median of number of samples per user.
Finally we provide an information theoretic lower bound for any (ε, 0)− pure differentially private algorithm: Theorems 2 and 3 resolve the user complexity of learning discrete distributions up to log factors and the δ-term in privacy. It would be interesting to see if Theorem 3 can be extended to nonzero values of δ. In the next two sections, we first analyze the lower bounds and then propose algorithms.

Lower bounds
The Ω(k/(mα 2 )) part of the user-complexity lower bounds in Theorem 1 and 3 follows from classic non-private results (2). Therefore in this section we focus on the private part.

(ε, δ)-lower bound for restricted estimators
We first start with the lower bound for algorithms that work directly on the counts vector N = [N 1 , N 2 , . . . , N k ], even though the learner has access to {N (u) : u ∈ U}. This motivates the definition of restricted estimators, which only depends on some function of the observation rather than the observation itself.
Definition 3 (f -restricted estimators). Let f : X s → Y which maps users' data to some domain Y. We say that an estimatorθ is f -restricted if it has the formθ(X s ) =θ (f (X s )) for some functionθ .
We generalize Assouad's lemma [Assouad, 1983, Yu, 1997 with differential privacy and the restricted estimators using the recent coupling methods of Acharya et al. [2018Acharya et al. [ , 2020. These bounds could be of interest in other applications and we describe a general framework where they are applicable.
Let X be some domain of interest and P be any set of distributions over X . Assume that P is parameterized by θ : P → Θ ∈ R d , i.e. each p ∈ P can be uniquely represented by a parameter vector θ(p) ∈ R d . Given s samples from an unknown distribution p ∈ P, an estimator θ : X s → Θ takes in a sample from X s and outputs an estimation in Θ. Let : Θ × Θ → R + be a pseudo-metric that measures estimation accuracy. For a fixed function f , let A f be the class of f -restricted estimators. We are interested in the min-max risk for (ε, δ)-differentially private restricted estimators: We need two more definitions to state our results.
Definition 4 (f -identical in distribution). Given a function f and two random variables X and Y , we say they are f -identical in distribution if f (X) and f (Y ) have the same distributions, denoted by Y ∼ f X. If X ∼ p and Y ∼ p , then we can also say p ∼ f p .
Definition 5 (f -coupling). Given a function f and two distributions p, q, we say that random variables (X, Y ) are an f -coupling of p and q if X ∼ f p and Y ∼ f q. When f is the identity mapping, then an f -coupling is same as standard coupling.
We make the following observation for restricted estimators: since we can only estimate the true parameter θ through some function f of the observation X s , then any random variable Y s such that f (Y s ) has the same distribution as f (X s ) would yield the same distribution for restricted estimatorŝ θ. Thus, ifθ could distinguish two distributions p 1 , p 2 from the space of product distributions P s := {p s : p ∈ P}, then it should also be able to distinguish p 1 ∼ f p 1 and p 2 ∼ f p 2 . We are able to prove tighter lower bounds because p 1 , p 2 (potentially outside of P s ) could be harder to distinguish than the original distributions p 1 , p 2 .
With this intuition, we show a generalization of Assouad's lower bound in Theorem 4. It relies on an extension of the Le Cam's method [Le Cam, 1973, Yu, 1997. The proofs are in Appendix B.1. For two sequences X s and Y s , let d h (X s , Y s ) = s i=1 1 X i =Y i . For a distribution p ∈ ∆ k , let Mul(m, p) denote the multinomial distribution.
Theorem 4 ((ε, δ)-DP Assouad's method for restricted estimators). Let V := {±1} k be a hypercube. Consider a set of distributions P V := {p ν : ν ∈ V} over X . Assume loss satisfies that ∀u, v ∈ V: (4) For each i ∈ [k], define the following mixture of product distributions: The proof of Theorem 1 follows from Theorem 4. We provide a sketch here and details in Appendix B.2. In our problem setting, X = [k] m is the domain and P is the set of multinomial distributions P = {Mul(m, p) : p ∈ ∆ k }. The parameter we are trying to estimate is the underlying p and the loss is 1 distance.

(ε, 0)-lower bound for the general case
We provide the complete proof of Theorem 3 in Appendix B.3 and sketch an outline here. We use [Acharya et al., 2020, Corollary 4], which is based on Fano's method and applies to ε ≤ 1. For each ν ∈ {±1} k/2 we define p ν the same way as (5), except by [Yu, 1997, Lemma 4] we restrict V to be the maximal subset of {±1} k/2 such that each pair u, v ∈ V is at least k/6 apart in Hamming distance, and |V| ≥ exp(c 0 k/2) =: M where c 0 = h(1/3) and h is the binary entropy function.

Algorithms
We first propose an algorithm for the dense regime where k ≤ m. In this regime, on average each user sees most of the high-probability symbols. However, this algorithm does not extend directly to the sparse regime when k ≥ m. In the sparse regime, we augment the dense algorithm regime with another sub-routine for small probabilities. Both algorithms could be extended to the case when users have different number of samples (see Appendix E).

Algorithms for the dense regime
We first motivate our algorithm with an example. Consider a symbol with probability around 1/2. If m is large, then by the Chernoff bound, such a symbol has counts in the range  with probability ≥ 1 − δ. Hence, neighboring datasets differ typically with √ m counts. However, in the worst case, they could differ by m and hence standard mechanisms add noise proportional to m.
We propose the following alternative method. The count for symbol i ∈ [k] can take values from 0, 1, . . . , m and is distributed according to Bin(m, p i ). Thus, we can learn this distribution Bin(m, p i ) itself to a good accuracy and then estimate p i from the estimated density of Bin(m, p i ).
We propose to use the private hypothesis selection algorithm due to Bun et al.
[2019] to learn the density of the Binomial distribution. It gives a score for every hypothesis using the Scheffe algorithm [Scheffé, 1947] and then privately selects a hypothesis using the exponential mechanism based on the score functions. For completeness, we state private hypothesis selection algorithm in Algorithm 1. We state the following guarantee on private hypothesis selection from Bun et al. [2019].
Lemma 2 (Bun et al. [2019]). Given d distributions p 1 , p 2 , . . . , p d and n independent samples from an unknown distribution p, such that min i 1 (p i , p) ≤ α, Algorithm 1 returns a distribution p i such that E[ 1 (p i , p)] ≤ 4α, with probability ≥ 1 − β, if the number of samples satisfies, Furthermore, Algorithm 1 is (ε, 0)-differentially private. Our proposed algorithm for learning Binomial distributions is given in Algorithm 2. We compute a cover of Binomial distributions and use Algorithm 1 to select an estimate of the underlying Binomial distribution. We return the parameter of the Binomial distribution as our estimate for the underlying parameter. Translating the guarantees on total variation distance between binomial distributions to difference of parameters requires a bound on parameter estimation from the binomial density estimation. To this end, we show the following theorem, which might be of independent interest.
Due to space constraints, we provide the proof in Appendix C. We show empirically that the bounds in Theorem 5 should hold by estimating the 1 distance between Bin(m, 0.01) and Bin(m, 0.011). Figure 1 shows that the 1 distance grows linearly with m when m is small, and grows linearly with √ m when m is large, which illustrates our bounds in Theorem 5. Combining Lemma 2 with Theorem 5 yields guarantees for Algorithm 2. Its sample complexity and utility are given by Theorem 6. We provide a proof in Appendix D.1.
Applying Algorithm 2 independently on each symbol i to learn p i , we obtain Algorithm 3, an (ε, δ)-private algorithm that learns unknown multinomial distributions under the dense regime. Its user complexity is given by Theorem 7. We provide the proof in Appendix D.2.
Theorem 7 (Dense regime). Let k ≤ m and ε ≤ 1. Algorithm 3 is (ε, δ)-differentially private and has sample complexity given by, Theorem 7 has a better dependency on m than that of the Laplace or Gaussian mechanism. Furthermore, even if the number of samples tends to infinity, the number of users is least O( √ k).

Algorithms for the sparse regime
We now propose a more involved algorithm for the sparse regime where m ≤ k. In this regime, users will not see samples from many symbols. A direct application of the private hypothesis selection algorithm would not yield tight bounds in this case. We overcome this by proposing a new subroutine for estimating symbols with small probabilities, say p i ≤ 1/m. In this regime, most symbols appear at most once. Hence, we propose each user sends if a symbol appeared or not i.e., Hence, if we get a good estimate for this quantity, then since p i ≤ 1/m, we can use it to get a good estimate of p i . We describe the details of this approach in Algorithm 4. Its user complexity and utility guarantee are given by Lemma 3, whose proof is in Appendix D.3.
Algorithm 4 is (ε, 0)-differentially private and returnsp such that with probability at least 1 − β, Combining the private hypothesis selection algorithm and the subroutine described in Algorithm 4, we obtain an algorithm for the sparse regime, shown in Algorithm 5. We first estimate p using the private hypothesis selection algorithm. If for some i, the estimated probability is too small, we run Algorithm 4 to obtain a more accurate estimate of p i . Theorem 8 gives the user complexity guarantee of Algorithm 5. We provide the proof in Appendix D.4.

Conclusion
We study user-level privacy and its theoretical limit in the context of learning discrete distributions.
We discover a fundamental limit in terms of user complexity for Laplace or Gaussian mechanisms and propose a nearly-optimal algorithm which surpasses this limit. It would be interesting to investigate A Proof of Lemma 1 Note thatp i = (N i + Z i )/(sm). Thus: The first term is upper bounded by k/(sm) from classic learning bounds for discrete distribution, which can be obtained by applying Jensen's and Cauchy-Schwartz inequality, and noting that For Laplace mechanism, Z i ∼ Lap(2m/ε), we have E|Z i | = 2m/ε. Thus: For Gaussian mechanism, Z i ∼ N (0, σ 2 ) where σ 2 = 4 log(1.25/δ)m 2 /ε 2 . Using Jensen's inequality we have E|Z i | ≤ E[Z 2 ] = σ. Thus: Setting the right hand side of the above inequalities to be ≤ α and rearranging the terms we obtain the desired lower bound on s.

B Lower bounds B.1 Proof of Theorem 4
The proof of Assouad's Lemma relies on Le Cam's [Le Cam, 1973, Yu, 1997] method, which provide lower bounds for min-max error in hypothesis testing. Let the hypothesis classes be P 1 ⊆ P and P 2 ⊆ P, which are two disjoint subsets of distributions. Letθ : X s → {1, 2} be an estimator of the indices, which receives s samples and predicts whether the samples come from P 1 or P 2 . We are interested in the worst case error probability: Theorem 9 ((ε, δ)-DP Le Cam's method for restricted tests). Let p s 1 ∈ co(P s 1 ) and p s 2 ∈ co(P s 2 ) where co(P s i ) represents the convex hull of P s i := {p s : p ∈ P i }. Let (X s , Y s ) be an f −coupling between p s 1 and p s 2 with E[d h (X s , Y s )] = D. Then for ε ≥ 0, δ ≥ 0, any f -restricted (ε, δ)-DP hypothesis testing algorithmθ must satisfy: Proof. The first term follows from the classic Le Cam's lower bound (see [Yu, 1997, Lemma 1]). For the second term, let (X s , Y s ) be an f -coupling of p s Pr(X s = x s , Y s = y s ) Pr(θ(X s ) = p 2 |X s = x s ) ≥ x s ,y s ∈W Pr(X s = x s , Y s = y s ) Pr(θ(X s ) = p 2 |X s = x s ).
Adding the two inequalities and rearranging the terms we obtain: which yields the desired lower bound.
We now have the necessary ingredients for the Assouad's lower bound. The final step is to apply the classic Assouad's Lemma [Yu, 1997]: Theorem 10 (Assouad's Lemma). Consider a set of distributions P V indexed by the hypercube V := {±1} k . Using the same definitions as in Theorem 4, ∀i ∈ [k], let φ i : X s → {−1, 1} be test for p s +i and p s −i . Then for any estimatorθ: Note that the summand in (6) is the error probability of hypothesis testing between the mixtures p s +i and p s −i . Applying Theorem 9 completes the proof.

B.2 Detailed proof of Theorem 1
Proof. Using the construction of P V as in (5). For p v ∈ P V , let q v = θ(p v ) be the underlying discrete distribution over k symbols. Then for u, v ∈ V: This is because one different coordinate between q u and q v leads to l 1 distance of 12α/k. Therefore τ = 6α/k. Define the mixtures as: It is helpful to look at the underlying distribution of all samples from users.
Note that p s ±i , q s ±i are not necessarily product distributions. By [Acharya et al., 2020, Lemma 14 ], there exists a coupling (U sm , V sm ) between q sm +i and We construct X s = [X 1 , ..., X s ] and Y s = [Y 1 , ..., Y s ] using this coupling (each X i , Y i ∈ R k which is the count of each symbol).
For each realization of U sm , V sm , suppose there are l different coordinates, i.e. d h (U sm , V sm ) = l, we move all different coordinates to the front so that only the first l/m ≤ l/m + 1 users would have different data. Name the rearranged sequence as (U ) sm , (V ) sm . Then we let user u get data from the m(u − 1) + 1 to mu coordinates of (U ) sm and (V ) sm respectively and compute the counts of each symbol to obtain X s , Y s . Therefore: Rearranging the coordinates of U sm , V sm would not change the total count N , and hence (X s , Y s ) is an N -coupling. As a result: Choose α = min{ 0.1k 60s(ε+δ) , 1 3 }, we have: When ε + δ ≤ 0.07: Setting the left hand side to be at most α and rearranging the terms, we obtain the desired lower bound for s.

B.3 Fano's Lower bound
In this section we provide learning lower bound for pure differential privacy using Fano's method. First we provide a theorem for restricted estimators like the one we proposed for Assouad's, which might be of general interest.
Theorem 11 (ε-DP Fano's lower bound for restricted estimators). Given a family of distributions P over X parameterized by θ : P → Θ, and letθ be an f -restricted estimator. Let V = {p 1 , ..., p M } ⊆ P such that for all i = j: Proof. The first term of (7) follows from the non-private Fano's inequality. We just need to prove the second term.
Proof of Theorem 3. We apply Theorem with f as the identity mapping. In this case it is the same as [Acharya et al., 2020, Theorem 2].
Assume k is even. From Yu [1997], there exists V ⊆ {−1, 1} k/2 and a universal c 0 > 0 such that |V| ≥ exp(c 0 k/2), each pair at least k/6 apart in Hamming distance. Given α ∈ (0, 1/6), define a family of multinomial distributions P ν which consists of the following distributions indexed by ν = (ν 1 , ..., ν k/2 ) ∈ V: For v ∈ V, let q v = θ(p v ) be the underlying k-ary distribution. Thus for each pair of distributions p u , p v from this family we have 1 (θ(p u ), θ(p v )) = 1 (q u , q v ) ≥ 12α/k · k/6 = 2α. Furthermore: Since f is set to be the identity, we just need to design a coupling with appropriate Hamming distance for each pair p s u , p s v , u, v ∈ ν. To this end we need the following lemma from den Hollander [2012]: Lemma 5 (Maximal coupling, den Hollander [2012]). Given distributions q 1 , q 2 over some domain X , there exists a coupling (X s , Y s ) between q s 1 and q s 2 such that From Lemma 5 there exists a coupling (X s , Y s ) between p s u and p s v such that E[d h (X s , Y s )] = s · d T V (p u , p v ). Using Pinsker's inequality, we have: Then apply Lemma 11: Note that this holds for all α. Choose α = min{ 1 6 , k sm } and α = min{ 1 6 , c 0 k 200s √ mε } respectively we get: Given desired accuracy α, setting sup p∈P E[ 1 (p, p)] ≤ α gives the desired user complexity bound.

C Bounds on total variation between binomial distributions
We divide the proof of Theorem 5 into two parts. We prove the upper bound in Lemma 6 and the lower bound in Lemma 9. We first prove an upper bound on the total variation distance between binomial distributions in terms of the parameters.
Secondly, since 1 distance of product distributions is at most the sum of 1 distances, Finally, by Pinkser inequality and the fact that KL divergence of product distributions is the sum of individual KL divergences, where the last inequality follows by observing that D(Ber(q)||Ber(p)) = q log q p Combining (9), (10),and (11) yields the lemma.
Lemma 7. Let c be a constant. If mp < c and p ≤ 1/2, then Proof. By definition, We first consider the case q ≥ p. Simplifying the above bound, ≥ e −1.5c min(m(q − p), 0.5). x ≤ 1/2. (e) follows by the bound on p. For q ≤ p, (a) follows from the Bernoulli inequality: (1 + x) n ≥ 1 + nx for x ≥ −1. The last inequalities are similar to the last two inequalities for q ≤ p case. Combining the above two results, we get Lemma 8. Let c > 2, m ≥ 3, and p ≤ 1/2. If mp ≥ c, then Since q lies in between p and q, 1 (Bin(m, p), Bin(m, q)) ≥ 1 (Bin(m, p), Bin(m, q )). Furthermore, observe that By [Adell and Jodrá, 2006, Proposition 2.3], for any two binomial distributions, Similarly, Since m − k is an integer, m − k ≥ 1. In order to bound the above quantity further, we first lower bound Binomial coeffcients.

D.4 Proof of Theorem 8
Parameters: We first define few parameters. Let ε = ε 8 min(k,m) log 1 240 , and γ = mα 8k . Let c = 4/m. Algorithm: For every symbol we first calculate the probability using the algorithm in Theorem 6 with ε = ε , α = α and error probability β. If the estimated probability is less than 2/m, we use the algorithm from Lemma 3 with ε = ε , α = α , γ = γ, and error probability β. Let p be the output of the first step and the p be the output of Lemma 3. The error of the algorithm is Hence, for a sufficient large constant b, if Note that since k ≥ m, the above bound implies that s ≥ b √ m, hence the bound also satisfies conditions in Lemma 3.
Differential privacy: We first provide the privacy guarantee for this algorithm. First observe that since p , p →p is a Markov chain, by the postprocessing theorem it suffices to provide privacy guarantee for releasing p , p . Consider releasing one of them, say p . For any two neighboring datasets differ in at most min(m, k) symbols. Let these datasets be D and D and S(D, D ) be the set of symbols where they differ. For these datasets, Pr(p k |D) Pr(p k |D ) .
Hence it suffices to apply strong composition theorem for this subset of size min(m, k) and the rest of the proof is similar to that of [Kairouz et al., 2017, Theorem 3.4]). The proof is similar for p and hence the result. Utility: To analyze the utility, we divide the symbols into three sets A 1 = {i : p i ≥ 4 m }, A 2 = {i : 4 m ≥ p i ≥ 1 4m }, and A 3 = {i : p i ≤ 1 4m }. Utility-large: Consider the set A 1 with symbols whose probability is greater than 4/m, for such a symbol, by Theorem 6, with probability ≥ 1 − β, Hence p ≥ p − α p m > 2 m . Hence, for such a symbol with probability ≥ 1 − β, Utility-medium: Consider the set A 2 with symbols whose probability in [1/4m, 4/m]. For such a symbol, then with probability ≥ 1 − 2β, Utility-small: Finally consider symbols whose probabilities are smaller than 1/4m, for these symbols, with probability ≥ 1 − β, and hence p ≤ p + α m ≤ 3/2m ≤ 2/m. Hence only the second algorithm is used. Hence with probability ≥ 1 − 2β, the error is at most, Summing over all symbols yield, Hence, by the union bound, with probability with 1 − 20kβ, Therefore in expectation,

E Extensions
In this section, we modify our algorithms for the scenario when users have different number of samples. Let m max be a known upper bound on the number of samples a user has. For a value m, let s m be the number of users such that m u ≥ m. Letm := m median be the median values of m u . We first state the main result, which is an analog of Theorem 2.
Theorem 12. Let ε ≤ 1. There exists a polynomial time algorithm (ε, δ)-differentially private algorithm A such that First we use ε/2 privacy budget findm, a private estimate ofm, andŝ, an estimate of sm (the quantile ofm). We only keep the users with at leastm samples, and selectm samples from each of them. Hence we reduce the problem to the case when users have the same number of samples. Then we modify the algorithms for both the dense and sparse regimes so that they are differentially private even if the number of samples of a particular user changes. We use the remaining privacy budget for the modified algorithms. The privacy guarantee follows by the composition theorem.
We first provide the algorithm for privately estimatingm and the quantile of estimatedm, which serves as a stepping stone for extending our algorithms to variable number of samples per user.
By the tail bounds of Laplace distribution and the union bound, for each i with probability 1 − β, Furthermore, for any cumulative sets, Let D be a dataset of size sm drawn i.i.d. from P . Define the following quantities which serve as empirical estimates of P (W 1 ): P (W 1 ) :=τ := 1 s |{x ∈ D : x ∈ W 1 }|, Pm(W 1 ) := τm := 1 sm |{x ∈ D : x ∈ W 1 }|.
Let ζ > 0 be the approximation parameter. Consider the following function: Output a random hypothesisĤ according to the following distribution: 2ε .
Proof. We modify the algorithm for the sparse regime as follows.
Let Um be the users who have at leastm samples. Similar to (14), we findp such that, where Z = Lap(1/ε). So we have: From Lemma 10, with probability at least 1 − β, the first term is upper bounded by:


Architectural Analysis of FPGA Technology Impact

The use of high-level languages for designing hardware is gaining popularity since they increase design productivity by providing higher abstractions. However, one drawback of such abstraction level has been the difficulty of relating the low-level implementation problems back to the original high-level design, which is paramount for architectural optimization. In this work (developed between April 2013 and April 2014), we propose a methodology to analyze the effects of technology over the architecture, and to generate architectural-level area, delay and power metrics. Such feedback allows the designer to quickly gauge the impact of architectural decisions on the quality of generated hardware and opens the door to automatic architectural analysis. We demonstrate the use of our technique on three FPGA platforms using two designs: a Reed-Solomon error correction decoder and a 32-bit pipelined processor implementation.

I. INTRODUCTION
In recent years, the automation of digital hardware design has advanced greatly. The industry has concurrent goals of increased designer productivity, shorter design cycles and ambitious area-performance-power constraints. As a consequence designers are increasingly adopting high-level Hardware Description Languages (HDL) [1], [2], [3], [4], [5] to address the challenging design requirements of large systems without losing productivity. These languages provide a higher level of abstraction than traditional languages such as VHDL or Verilog, implicitly hiding some of the low-level details in favor of an explicit system-wide view.
Existing commercial and academic design tools are good at synthesis, placement and routing of hardware designs for different implementation platforms. Usually such tools provide very detailed reports, but only on gross and macro-level resource consumption and performance metrics. Even if the detailed reports are analyzed, the resources are closely tied to the implemented circuit. Therefore, it is difficult to obtain a breakdown of area, delay and power metrics for the modules and sub-modules in the high-level design source.
Architecture designers require tools to automatically generate such a breakdown, as typical design iterations in the design cycle are always limited to specific blocks and modules. FPGAs are an important part of the high-performance ecosystem, as accelerators in heterogeneous architectures or highthroughput custom machines. In both cases they require deep design-space exploration [6] and architectural refinements [7] to appropriately map onto the target technology with the required constraints. There is an urgent need to improve and enhance the feedback from downstream synthesis tools to inform high-level design decisions. 1 This project was started in April 2013.
This work tries to reduce the gap between the target circuits and their high-level architectural descriptions. In addition, bridging these two levels of the design process is the first and necessary step towards automatic architectural optimization.
Our contributions are the following: • We present a novel methodology to analyze highlevel designs and their synthesis reports in order to generate module and sub-module level metrics for area, delay and power. This methodology can be used with existing languages and hardware synthesis tools, and some of its metrics cannot be obtained by the existing design tools. The novelty of this work lies in automatic generation of metrics corresponding to high-level architectural units.
• To demonstrate the applicability of this methodology, we implement it on a rule-based HDL. We use our prototype implementation to extract results for two microarchitectural test cases: a Reed-Solomon decoder and a RISC microprocessor. We demonstrate the use of our tool on three different FPGA platforms.
• The results presented are enriched with architectural information. We propose how they could be used by the designer to take informed architectural decisions in order to optimize the design.
• We also discuss the possibility of automatic architectural optimization using our framework.
Paper Organization: Section II introduces our methodology. In Section III, we apply the methodology to the chosen high-level hardware designs implemented on three FPGA platforms and show three different metrics for each implementation. We consider the possibility of automatic architectural optimization in Section IV. In Section V, we discuss the applicability of our technique to other HLS frameworks, and present recently developed techniques and tools related to this work. Finally, Section VI describes future research directions and concludes the paper.

II. METHODOLOGY
We divided our methodology in two steps. Firstly, the design is analyzed and annotated. Then, after passing through the synthesis flow, the resulting circuit is analyzed and compared to the original, abstract design. The user can apply architectural solutions to implementation problems, or even automatic architectural optimizations could be possible. Also, as the architectural and low-level information is known by the tool, automatic optimizations could be applied.
The analysis starts with the user's description of the architecture. As the needs for large-scale system design increase, several HDLs have been proposed. To implement our   methodology and demonstrate its applicability we have chosen Bluespec SystemVerilog [2], a well-known rule-based HDL. In section V we describe how our methodology can be applied to HLS tools as well.
As an example, consider the traditional swap/subtract greatest common divisor (GCD) Euclidean algorithm. In Figure  1a we show a 32-bit GCD module implemented with two Bluespec rules. This example contains two rules and two 32bit registers. Both guards are mutually exclusive, so at most one rule can be executed every cycle.

A. Analysis of the Architecture
The initial step of our methodology starts with a user description of a hardware architecture. We show the user description of the GCD design in Figure 1a. Instead of directly analyzing the high-level source code, our tool analyzes the intermediate representation to simplify the problem.
Our tool generates an abstract representation of the architecture from the Bluespec description. During the rest of the paper, we term the high-level objects (submodules and rules) as "blocks". In Figure 1a there are four blocks: the rules swap and subtract, and the registers (submodules) x and y. The intermediate representation contains a very simplified model of the operations of the rules. All the algorithmic descriptions are converted into a flat RTL representation.
The intermediate representation is converted into the definitive Verilog description of the hardware, which is functionally equivalent to the architectural description in Bluespec. The main goal of our methodology is to establish relations between the final circuit and the original architecture. The core technique to accomplish this is the annotation method, where innocuous annotations are added to the Verilog files generated by the Bluespec compiler. This annotation process is specially necessary for high-level synthesis, where the generated RTL code does not clearly reflect the original architectural units and the algorithmic semantics.
This extra information will remain during the FPGA circuit synthesis, and consists of unique identifiers that are assigned to each Bluespec block. This prefix is added to the name of each Verilog element that is present in the intermediate model, identifying the block that owns it. An RTL circuit of the GCD design is shown in Figure 1b. The annotations are represented as colors. For example, the subtract arithmetic unit, in blue, corresponds to the subtract rule. Similar units are merged by the Bluespec compiler and may not be identified properly (with a white background in the example). This represents less than 1% of the hardware.

B. Analysis of the Circuit
After the Verilog model is annotated, it gets synthesized into circuits (i.e., mapped, placed and routed) using the FPGA vendor's tools. In this process the architecture is implemented in a particular technology, adapting to its characteristics. The next step is analyzing this circuit and identifying the annotations that remain after the synthesis. This will enrich the available information on area, timing and power characteristics of the circuit, establishing a direct link with the original architecture. During the following sections we will refer to the FPGA electronic elements, i.e., LUTs, registers, etc. as cells or gates as well.
We show a hypothetical synthesis of our GCD model in Figure 1c. The two original registers have been synthesized into flip-flops. We show the input (D) and output (Q) ports of the flip-flops in separated nodes because there is no asynchronous connection between them. The other cells are LUTs with different configurations and number of inputs. Again, the annotations, shown in the example as colors, remain.
The resources and timing information extracted from the final circuit will be used to identify the annotated gates and map them to the original architectural element. In this work, some specialized elements like Block RAMs and DSP slices have been kept outside the scope of our analysis and will need further research.

1) Area estimation:
The area analysis refers to the amount of FPGA resources used. Our tool analyzes the final circuit and represents it as a Directed Acyclic Graph (DAG) for computation purposes. The nodes of the graph are FPGA cells, and the edges are FPGA nets. As we explained previously, after synthesizing the circuit, the FPGA cells are named after the Verilog element that generated them. Our tool looks for prefixes in the names and extracts the unique label that identifies the original Bluespec block.
2) Delay estimation: The delays of the circuit can be represented as weights in the DAG that the tool extracted. Figure 1c  is an example of a DAG, where every node corresponds to a FPGA cell and every edge is a connection between cells. Some of these graphs can be too big to analyze, even for a small design (e.g., 10,000 cells). Our tool partitions the data and reduces the input set of the algorithms as much as possible to optimize the analysis time.
The delay calculation proceeds as follows. Our tool obtains all the combinational paths that cross each block of the original architecture. The example DAG shown in Figure 1c has combinational paths from the output (Q) ports to the input (D) ports of the registers.
In Figure 2a we provide another DAG to describe the delay estimation algorithms more clearly. The tool performs a delay analysis at block level. Using the information collected during the area analysis, all the cells that belong to the current block are identified in the DAG. An initial subgraph is generated with all these nodes. Figure 2b shows the annotated nodes in blue. This way, all the possible combinational paths are identified. In Figure 2c we show how from the 4 original annotated nodes, two "combinational trees" (each with 2 branches) are identified with 7 and 5 nodes. The starting nodes of the paths are clock ports, and the end nodes are the inputs to registers or memories. The middle nodes are logic gates.
This expanded subgraph is then partitioned into connected sets. In Figure 2d the two connected sets, with 7 and 5 nodes are represented. Every connected set is a directed acyclic subgraph without combinational connections to the other sets. Therefore it can be analyzed independently. From all the connected sets, the longest delay is assigned to the block. In the delay report, for every block the critical path is displayed, effectively listing all the nodes.
We devised two weighting functions to obtain different delay metrics: • System delays: all the edges are weighted with the corresponding delay. This weighting function makes the algorithm to choose the longest paths that contain one or more nodes of the current block.
• Block delays: only the nodes that belong to the current block have a positive weight, while the rest have a null weight. With this weighting function, the algorithm will return the paths with the highest delay due to the current block.
The first weighting function allows us to find if a block contributes to the longest (critical) paths of the system, which are the performance bottlenecks of the whole design. This information can be returned by any typical timing analysis tool. The second weighting function allows us to find what we consider is the delay of a design block: among all the combinational paths that cross the block, the longest intrablock segment. This second metric helps the designer to understand the isolated delay of an architectural unit.
We want to note that the results of both metrics can be completely different, because a block's internal maximum path can be longer than the block's contribution to a system critical. Therefore, non-critical optimization opportunities of architectural units (i.e., block delays) are difficult to detect with typical timing analysis, and their effect can be higher than what would be expected [8]. For instance, in Figure 2e the critical paths are shown in red. Using this weighting function, the designer can observe that the block in blue contributes to two system paths that have 5 and 4 nodes. Assuming that in this example all the delays are equal, the path with 5 nodes would be the longest path contributed by this block. Figure 2f shows the result of applying the block contribution delay. Only the delays of the annotated nodes are considered. The paths are 1 and 3 nodes long. In this example the block (in blue) contributes to a critical path of the system with 5 nodes, but the critical delay of the block is 3 nodes long. Thus, the designer could choose a) to optimize the critical path of the system in order to reduce the maximum period and increase the frequency. Another choice could be b) to optimize the delay of the block if it is a functionality used often, or even c) using a different, higher speed clock for it.
3) Power score: As part of the feedback generated by the tool, the component blocks of a design are ranked in the order of their average power consumption. The various parts of power score characterization are individually considered in the following aspects: The static power consumption is directly proportional to the area of the component blocks, weighted by values for varying sizes of LUTs and flip-flops. The dynamic power consumption of a block is directly proportional to the product of the capacitance of the switching elements and the frequency of transitions of block elements. Dynamic activity within the block can either occur when the rule corresponding to the block fires or when the input state for the rule changes as a result of another rule firing. We profile the design to obtain the number of event transitions as measured by the rule-based activity, as well as to obtain the relationship between output state affected by a rule and input state dependence for each rule.
State change in a given cycle leads to dynamic activity in the next cycle in each block, which depends on the changed state. In addition, rules that fire in a given cycle write their state changes in the same cycle, again consuming power. We assume that, whenever a state is updated, its value changes, leading to dynamic transitions in dependent blocks. The dynamic power computed for the design takes into account both of these described components.
The static and dynamic power for each block (P S and P D respectively) is determined using the cell characterization obtained in the area analysis and the FPGA cell power model described in [9]. We then use dependency analysis and profiled rule-firing statistics, to compute the average switching factor (α) for each block of the design. This is then used to compute the average power consumption of each block given by equation 1, where f is the frequency of operation.
This metric is termed as "power score". Though it is not a direct estimate of the exact power consumption due to assumption of upper-bound block-level activity, this metric can still help the designer to compare the relative amount of dynamic and static power of various blocks of the hardware. In addition, the probable hot spots of the architecture can be identified. The value of the metric cannot be used to directly compare the static and dynamic power of a block implemented in the different FPGA technologies as we use the same power model in each case. The main value of the score is that the relative power distribution of the design in each FPGA platform will follow the same pattern as the power score for that platform, and this information can be used to analyze and reduce the power consumption in a customized manner.

III. RESULTS
In this section we describe the architectures chosen to demonstrate our methodology and the results obtained using our tools. The two testcases are: Reed-Solomon: This design is a parameterized Reed-Solomon error correction decoder which meets the throughput requirement for use in an 802.16 wireless receiver. The decoding algorithm is composed of several steps, each of which is implemented as a separate module shown in Figure 3a. Dynamic activity, used for determining the power score metrics of the design, was generated using a testbench that feeds input data with errors at 50% of the maximal correctable rate.
SMIPS: This design is a 32-bit RISC microarchitecture that implements the MIPS I ISA. Figure 3b shows the main components consisting of a multiply unit, coprocessor 0 (implementing data and instruction TLBs), independent instruction/data L1 caches, and a unified, N-way L2 cache. This 5stage processor can boot the GNU/Linux kernel. We used the dynamic activity generated during booting of Linux to generate the power score metrics of the SMIPS design.
We implemented these designs on three different FPGA devices: Spartan 6 XC6SLX45T-3FGG484, Virtex 5 XC5VLX155T-2FF1136 and Virtex 7 XC7VX485T-2FFG1761. We used the Xilinx ISE and Vivado tools 14.4 to synthesize, place and route the Verilog hardware model. We also used these tools to export the EDIF and SDF models. All the designs were targeted at 100 MHz on all the FPGAs.

A. Discussion of the results
The results for both architectures are shown in Figure 4. The bar colors indicate the FPGA device: Spartan 6 -blue, Virtex 5 -red, and Virtex 7 -green. Three metrics are displayed: • The area results show the number of cells per architectural module.
• The delay charts show the longest block delay, as previously explained in section II-B2. This metric measures the maximum contribution of each block to any path that crosses it. The darker components are the network part of the delay, and the lighter are the logic part. The diamond-shaped mark over the columns indicates the maximum delay of the system, and which block or blocks contribute to it. For both designs we can observe the significance of the network in the total delay.
• The power scores are also decomposed in two: static power score (darker shade) and dynamic power score (lighter shade).
Our framework produces results for every module and submodule, but we grouped some results to simplify the charts. Figure 4a shows the breakdown of metrics for modules of the algorithm, as well as for the decoder module (RS) itself, which acts as a wrapper around these component modules, and for the top module which deals with Input-Output to memory. From an algorithmic perspective, Berlekamp step is the most computationally intensive part of the decoding process, and accordingly we see that this module has the maximum area in all three FPGA platforms. Error correction step involves the minimum computation as it simply removes the computed error values from the received data, thus contributing to minimal area. The other three component modules have similar moderate area usage.   modules respectively. However, the Spartan 6 implementation is unable to achieve this due to long computational operations in Berlekamp, Chien and Syndrome, with Syndrome contributing the critical path. The power metrics roughly track in similar ratios as with the area metrics. One important point to notice is that most of the dynamic power consumption in the decoder is contributed by the Berlekamp module. Dynamic power comprises up to 50% of Berlekamp's power consumption (in the case of Virtex 5) while other blocks' power consumption is mainly the static power of the FPGA resources used. This highlights the importance of this module for the decoder design, and suggests design refinement for reduced area as well as the use of power reduction techniques for reducing unnecessary dynamic activity (e.g., clock gating).

1) Reed-Solomon decoder:
2) SMIPS: In SMIPS there are 12 modules. These modules correspond to some of the architectural units shown in Figure 3b. The results of the missing submodule architectural units, such as the pipeline stages, are included in their parent modules. As with the previous case, the area and power metrics are very similar across all tested FPGA platforms, seen in Figure 4b. In general, area metrics seem to follow a descending trend from Spartan 6 to Virtex 7. This is a result of the FPGA architectures being different in these devices. For instance, Spartan 6 slices (a group of two LUTs) have one carry chain output [10], which can be used to implement fast carry chain arithmetic operations. The Virtex 5 and Virtex 7 slices have two independent carry chains [11], which allow implementing more arithmetic operations with fewer LUTs. This is especially clear in the Virtex 7 area results.
The data cache requires more resources in Virtex 5 than in the other devices. The area report showed that the data cache module required 500 more registers in Virtex 5. We observed that while specifying the same architecture, the synthesis tool did not infer the data cache RAM unit correctly for Virtex 5, and implemented the cache memory using registers instead of using efficient on-chip BlockRAMs. We argue that such portability problems make necessary not only the development of platform-neutral synthesis tools and languages, but also cross-platform analysis tools like ours.
The delay results differ for Spartan 6, which was unable to achieve timing closure for a target clock period of 10 ns. The area of the design has an important impact on the performance of the design. High resource usage congests the network and makes it difficult for the router to achieve the timing goals. SMIPS occupies about 30% of the Spartan 6 device, much higher than the other two devices. In a congested device the network delays are high, even if it can fit the design. In addition, the logic delays of Spartan 6 cells are higher than the high-performance Virtex 5 and 7 LUTs. For instance, delay of a 6-input LUT in a Spartan 6 device can be ∼200 ps, whereas in Virtex 5 it is ∼80 ps and in Virtex 7 ∼40 ps. We can observe that the critical path of the Spartan 6 implementation is caused by the instruction TLB. In Virtex 5, we show two maximum delay marks, one over the CPU and another over the multiply unit. This means that the critical delay starts at the execution stage of the CPU and ends at the multiply unit. The delay report, along with the delay value, also includes the path that caused it and which architectural elements contribute to it. In Virtex 7, the maximum delay is caused by the execution stage of the CPU.
For power consumption, it is seen that similar blocks dominate in all three platforms. These are L2 Cache, Execute block and the Multiplier. The dominance of the L2 Cache comes due to it being the largest block by far, thus having the largest static power dissipation. The computationally intensive Execute and Multiply blocks have a lot of logic and see a lot of dynamic activity. Beyond these three blocks we start seeing differences between the platforms. Virtex 5 has the Decode unit at relatively higher power consumption than even the Multiply unit. These differences arise due to the different availability of DSP arithmetic resources in the 3 FPGAs, different number of multiplexers generated for large data storage, and different levels of power and area optimizations implemented in the platforms.

IV. AUTOMATIC ARCHITECTURAL OPTIMIZATION
The architecture defined by the user determines the performance, area and power consumption of the final FPGA circuit. The way that the architecture is synthesized, placed and routed can optimize these metrics, but they are always constrained by the architectural decisions. Thus, we believe that significant changes of these results can only be achieved through high-level, architectural decisions. For instance, the results in Figure 4b suggest several modifications at architectural level: reducing the number of entries of the L2 cache can improve area and power metrics. Splitting the Execute stage of the pipeline in two would break the combinational path crossing the data TLB and the data cache.
Currently these architectural optimizations are performed by the designer, under the guidance of the reports produced by the synthesis tools. Like the designer, our framework has knowledge about the architectural design and the synthesis reports. This knowledge enables the tool to implement technology-guided architectural changes.
The quality and impact evaluation methodology that we present in this work relies on two fundamental components. One is describing the hardware architecture using a highlevel design language, such as Bluespec or another HLS language. The other is the methodology to project the technology problems to the architecture, as we described in the previous sections. But automatic architectural optimization requires additional components. The framework must distinguish the characteristics of each architectural unit, so that these parameters can be modified to meet the constraints imposed by the technology. For instance, the optimization tool should be able to modify the cache policies or the size of some units. The user should be able to put some constraints over those variations, informing what quality minimums must be preserved when modifying the architecture. Information about the target technology can complement these optimization inputs, allowing the tool to apply different strategies.

V. GENERALIZATION OF THE METHODOLOGY AND RELATED WORK
We have shown how to implement our methodology for rule-based languages. In this section we want to discuss the generality of this method, and how it could be applied to HLS languages and tools. Popular HLS tools such as xPilot [4] (later AutoPilot and currently Xilinx Vivado [12]), LegUp [3] and ROCCC [5] convert C programs into synthesizable hardware.
These three examples use LLVM as their C front-end. The intermediate representation is then converted into Verilog or VHDL descriptions. The hardware architecture produced by C-based HLS converts blocks of C code, i.e., functions, into Finite State Machines (FSM). Local and global variables are stored in local (block RAM) or external (DDR) memories. The first step of our methodology, the architectural analysis and annotations, requires augmenting the intermediate representation with architectural information. This can be applied to C programs reusing popular debugging information that most compilers, including LLVM, support (for instance, DWARF for ELF files).
In contrast to RTL or rule-based models, the FSMs generated by HLS require a variable number of cycles to finish not directly known at design time. But the FSMs have start and finish signals. In this sense, performance analysis is similar to the implementation previously shown. In both cases the product is an RTL hardware description, where timing delays can be analyzed and tracked to the original functional blocks. The power analysis is essentially the same, C-based HLS also requiring functional simulation to obtain the execution rates of the architectural blocks.
Regarding related work, Yan et al. [13] presented an estimation model that provides an area-delay tradeoff for chosen applications and FPGA platforms. However, it is aimed primarily at design partitioning of VLIW and Coarse-Grained reconfigurable architectures, while our work aims at modeling any custom hardware design. Modeling frameworks like Mc-PAT [14] are able to estimate design metrics for a wide variety of processor configurations and implementation technologies, but are limited to pre-defined architectural parameters and can not be used on arbitrary designs. Amouri et al. [15] proposed a method to accurately measure and validate the leakage power distribution in FPGA chips using a thermal camera. These extremely accurate results can be used within our methodology for modeling architectural power consumption. Li et al. [9] proposed a fine-grained power model for interconnects and LUTs in an FPGA implementation targeting sub-100 nm technology. However, correlating high-level design blocks to the FPGA power estimates requires additional analysis to keep track of how resources are allocated in each synthesis, placement and routing process, as well as individual activity and trace generation for various component blocks. Our technique provides this analysis.

VI. CONCLUSION AND FUTURE WORK
The increasing use of high-level hardware design languages is enlarging the gap between target technology and architectural specifications. Hardware designers require relevant feedback from post-synthesis tools that inform design decisions in an iterative process. In this paper, we describe a methodology to relate post-synthesis area, delay and power data back to the initial HLS design. This methodology is a novel approach to architecture characterization. Unlike other techniques, it does not need additional user input to analyze the architecture. Instead, it uses the same hardware description used to synthesize the final circuit. The quality of the characteristics extracted from this circuit are backed by the quality of the FPGA vendor's tools. Such feedback allows the designer to quickly gauge the impact of architectural decisions on the quality of generated hardware.
At present, the design changes necessitated by the design constraints and the feedback generated using our technique have to be manually done by the user. Automation of design changes requires appropriate granularity in quantifying the impact of changes on area, performance and power metrics. By satisfying this need, the work presented in this paper can serve as a foundation for Automatic Architectural Optimization. We will investigate this possibility in the future.
To summarize, we have implemented a tool that automates design characterization analysis and shown how it can help to improve the quality of final hardware and meet required goals. For that purpose, we use two designs: a Reed-Solomon error correction decoder and a 32-bit pipelined processor implementation. We implement and characterize these designs on three FPGA platforms: Spartan 6, Virtex 5 and Virtex 7. We discuss the limitations of the analysis and the impact of the final technology on the design, and we show examples of how the information reported by the tool can help to spot architectural problems. Finally, this work has a high potential for use in automatic architectural optimization and cross-platform characterization, and could be applied on other HLS design languages and tools.


text:
Sentimental LIAR: Extended Corpus and Deep Learning Models for Fake Claim Classification

The rampant integration of social media in our every day lives and culture has given rise to fast and easier access to the flow of information than ever in human history. However, the inherently unsupervised nature of social media platforms has also made it easier to spread false information and fake news. Furthermore, the high volume and velocity of information flow in such platforms make manual supervision and control of information propagation infeasible. This paper aims to address this issue by proposing a novel deep learning approach for automated detection of false short-text claims on social media. We first introduce Sentimental LIAR, which extends the LIAR dataset of short claims by adding features based on sentiment and emotion analysis of claims. Furthermore, we propose a novel deep learning architecture based on the DistilBERT language model for classification of claims as genuine or fake. Our results demonstrate that the proposed architecture trained on Sentimental LIAR can achieve an accuracy of 70\%, which is an improvement of ~30\% over previously reported results for the LIAR benchmark.

I. INTRODUCTION
The percolation of social media throughout the world has facilitated unprecedented ease of access to the flow of information. The rise of the internet and its availability have also enabled every user to to not only consume, but also contribute to the information flow. However, the benefits of such ecosystems come at the cost of mistrust in the veracity of information. In recent years, the social media scene has witnessed the proliferation of false information campaigns, in which ordinary users are intentionally or otherwise both consuming false news and also spreading it among their communities.
This phenomenon is commonly referred to asfake news, broadly defined as broadcasting of information that is intentionally and verifiably false [1]. The rise of fake news and its societal impact has been studied in the context of numerous recent events, such as the Brexit referendum and the 2016 US presidential elections [2]. Fake news has thus proven to be a major threat to democracy, journalism, and freedom of expression [1]. The exposure of users to fake news has been shown to have numerous deleterious effects, instances of which include inducing attitudes of inefficacy, alienation, trusting in false propaganda, cynicism toward certain political candidates and communities, that can at times give rise to the violent events. For example, coordinated fake news and propaganda campaigns on Facebook are considered to have been key in inciting the Myanmar genocide in 2016-2017 [3]. Also, the recent proliferation of false information about 5G communication networks being the cause of the novel Coronavirus outbreak has resulted in attacks against the employees and infrastructure of cellular careers in the UK [4]. Fake news can also affect financial markets, as observed in the case of fake news claiming that Barack Obama was injured in an explosion resulting in a loss of $130 billion in stock value [5]. Hence, there is a growing need for effective tools and techniques to detect and control the spread of false information campaigns on social media.
Fake news classification is the process of determining whether the news contains false news and misinformation or not. Traditionally, this classification is performed by subjectmatter experts and journalists via comparing the claims of an article with established facts and cross-checking with trusted and alternative sources. However, the high volume and velocity of information flow on such platforms render such manual approaches infeasible. Therefore, recent efforts of the stakeholders and the research community have been focused on automated techniques for classification and detection of fake news. A promising solution in this domain is to leverage the recent advances in machine learning and Natural Language Processing (NLP) to automated the processing and classification of the high-dimensional and complex text of news articles and posts [6].
While the literature on the applications of machine learning to fake news classification has grown rapidly, the body of work on the classification of short-text claims remains relatively thin. This issue is of paramount importance, as many of the posts on social media such as Twitter contain only a short claim extracted from the longer text of news articles. The short form of such claims poses a challenge to the classification task, as it provides very limited information (i.e., a few sentences or words) and thus constrains the applicability of machine learning models trained on full-length articles and texts. Over the past few years, a number of datasets and models have been proposed for the classification of short-text claims, notable instances of which are the studies based on the LIAR dataset of short statements [7]. However, the performance of machine learning models trained on this dataset remain at impractical levels, with the best accuracy values reported to be41.5% [6].
In this paper, we introduce Sentimental LIAR, which extends the LIAR dataset by including new features based on the sentiment and emotion analysis of claims. Our extended dataset also proposes a modified encoding of textual attributes to mitigate unintended bias in modeling. Furthermore, we propose a novel deep learning architecture based on the DistilBERT language model for the classification of claims as genuine or fake. Our results demonstrate that the proposed architecture trained on Sentimental LIAR can achieve an accuracy of 70%, which is an improvement of 30% over previously reported results for the LIAR benchmark.
The remainder of this paper is organized as follows: Section II presents the technical background and an overview of relevant datasets and literature on false claim classification. Section III describes the extended features of Sentimental LIAR, and details the proposed deep learning architectures for false claim detection. The experimental evaluation of our proposed techniques is reported in Section IV. Finally, V concludes the paper with a discussion on the results and remarks on future directions of work.

A. Fake News
Fake news is defined as "fabricated information that mimics news media content in form but not in organizational process or intent" [8]. Fake news outlets exploit the fact that social media platforms lack the editorial norms and processes of the traditional news media for assuring the accuracy and credibility of the information. Fake news overlaps with other information disorders, such as misinformation (false or misleading information) and disinformation (false information that is purposely spread to deceive people)" [8]. Fake news can also be defined as news that is false based on its authenticity (false or not), intention (bad or not), and whether the information is news or not [1]. Technical approaches to the detection of fake news include fact checking, rumor detection, stance detection, and sentiment analysis [6]. Fact checking is the task of assessing the truthfulness of claims made by public figures such as politicians and pundits [9]. The contents of fake news often lacks pertinent facts, or contain factual representations that are not correct according to the context of the news. Rumor can be defined as the unverified pieces of information at the time of posting, where there is doubt to the truth of the claims. Zubiaga et al. [10] define rumor detection as the task of separating personal statements into rumor or nonrumor. Stance detection refers to the process of automatically detecting whether the author of a piece of text is in favor of the given claim or against it [11]. Sentiment analysis is based on extracting emotions and contextual sentiments from statements to determine whether they are positive, negative or neutral with respect to the subject. It is noteworthy that while stance detection may rely on sentiment analysis, the goal of sentiment analysis is to analyze personal emotions rather than the objective verification of statements. As detailed in Section III, our work leverages a hybrid of stance detection and sentiment analysis to enhance the performance of machine learning models for false claim detection in short text.

B. DATASETS
Recent research on fake claim detection in short text has yielded a number of significant open-source datasets, some of the most notable of which are enumerated as follows: 1) FEVER [12]: Fact Extraction and VERification (FEVER) is a short claim dataset of 185,445 claims. This dataset is annotated with three labels: Supported, Refuted, and Not Enough Info. The claims are curated from Wikipedia. FEVER was constructed in two stages, the first one is Claim Generation, where extracted information Wikipedia is converted into claims. The second stage is Claim Labeling, where each claim is labeled as 'supported' or 'refuted' according to Wikipedia. In cases where information were insufficient for determination, a label of not enough information is assigned.
2) PHEME [10]: is a dataset of 330 rumor threads composed of 4843 tweets associated with 9 newsworthy events. The annotators of this dataset were journalists who tracked the events in real time. Each entry in PHEME is labeled as either true or false.
3) LIAR [7]: is a publicly available short statement dataset that is derived from Politifact.com. Each of the 12,836 statements in LIAR is annotated based on data available on Politifact with one of the following six labels: pants-fire, false, barely true, half-true, mostly-true, and true. The dataset contains the text of a claim, as well as relevant meta-data,  Convolutional Neural Networks (CNNs) are generally known for their applications in image processing, where CNNs can learn representations of localized features from raw input while preserving the relationship between them. However, this capability of CNNs is not constrained to computer vision, and can also be adopted for NLP tasks. Wang et al. [7] demonstrate the performance a CNN architecture [13] trained on LIAR for fake claim classification, and report a test-time accuracy of 27.4%. In a subsequent study, Kirilin et al. [14] extend the LIAR dataset with a larger credibility source using a credibility vectorization technique called Speaker2Credit. Experimental results reported in [6] demonstrate that training a Long Short-Term Memory (LSTM) model on this extended dataset achieved an accuracy of 45.7%.
Also, Long et al. [15] propose another extension of the LIAR dataset by adding more features based on speaker profiles, such as party affiliation, speaker title, location, and credit history. They also report that an attention-based LSTM model trained on this extended dataset results in an improved accuracy of 41.5% compared to the benchmark of 27.4% reported in [7].
Ruchansky et al. [16] propose a hybrid deep model for fake news detection, consisting of three modules: The first module is a Recurrent Neural Network (RNN) that captures the temporal pattern of user activity on a given article, the second module learns the article's source characteristic based on the user response, and the third module integrates the previous modules for the classification task. Their study was based on two datasets curated from Twitter and Weibo, and achieved an accuracy score of 89.2% and 95.3%, respectively.

D. BERT
Bidirectional Encoder Representations from Transformer (BERT) [17] is a state of the art word representation model that uses a transformer to learn the contextual relationships between the given text in a bidrectional manner (i.e., in both left-to-right and right-to-left). The bidirectionality of BERT has made it standout in many NLP tasks, as it improves finetuning based approaches to token level tasks. BERT uses two strategies in training, the first one is Masked Language Model (MLM) and second one is Next Sentence Prediction (NSP). In MLM, the model randomly masks some of the tokens from the input text and then model tries to predict those masked vocabulary id of the word. It does so by looking into the context in both direction. As for Next Sentence Prediction, the pairs of sentences are given input to the model and it tries to predict if the given second sentence is the continuation or the next subsequent sentence to the first one or not. The model uses both MLM and NSP during training to minimize the loss. BERT can be modified to perform many downstream tasks by feeding the task-specific inputs and outputs. For the classification tasks, BERT can be extended by adding a classification layers on the top of the transformer output for the token.

E. DistilBERT
The DistilBERT [18] is a distilled version of BERT. BERT-BASE [17] models are too large and difficult to deploy and train in practice. In practical implementation, these models provide higher accuracy, but at the cost of slower performance due their large memory requirements. To address this issue, DistilBERT [18] was proposed. This model is based on knowledge distillation [19], [20], a compression technique in which a small model is trained to reproduce the behavior of a larger model. The size of DistilBERT is reduced by 40% by removing the token-type embeddings and the poolers from the architecture, as well as reducing the number of layers by a factor of 2. The DistilBERT has 97% of the language understanding capabilities and is 60% faster than the BERT. DistilBERT achieved this by using a triple loss that combines language modeling, distillation, and cosine-distance losses.

III. METHODOLOGY
Fake claims are often written in a style of exaggerated expressions and strong emotions. Style-based classification studies aim to assess news intention, that is to determine whether there is an intention to mislead the reader or not? With the aim of developing a computationally feasible model for fake claim detection, we propose deep neural network architectures based on DistilBERT to analyze the deception in short-text claims. Our proposed models learn to detect deception based on attribute-based language features, such as sentiments and structure-based language features. In our approach, we rely on the representation learning capabilities of transformers to extract features from statements. We also propose an extension to the LIAR dataset that includes additional features based on the sentiment and emotion analysis of the claim. The details of our proposals are presented in the remainder of this section.

A. Sentimental LIAR
Our Sentimental LIAR dataset is a modified and further extended version of the LIAR extension introduced by Kirilin et al. [14]. In our dataset, the multi-class labeling of LIAR is converted to a binary annotation by changing half-true, false, barely-true and pants-fire labels to False, and the remaining labels to True. Furthermore, we convert the speaker names to numerical IDs in order to avoid bias with regards to the textual representation of names.
The binary-label dataset is then extended by adding sentiments derived using the Google NLP API 1 . Sentiment analysis determines the overall attitude of the text (i.e., whether it is positive or negative), and is quantified by a numerical score. If the sentiment score is positive, then we assign Positive for the sentiment attribute, otherwise Negative is assigned. We also introduced a further extension by adding emotion scores extracted using the IBM NLP API 2 for each claim, which determine the detected level of 6 emotional states, namely anger, sadness, disgust, fear and joy. The score for each emotion is between the range of 0 and 1. Table I demonstrates a sample record in Sentimental LIAR for a short claim in the LIAR dataset.

B. Models
We investigate two model architectures based on Distil-BERT [18] for the claim classification task: 1) Model 1: DistilBERT with Feed-Forward Neural Network: This model extends DistilBERT by appending a Feed-Forward neural network for classification, as illustrated in fig.(2). Two variations of the model were investigated: The first variant feed all the input data directly to the DistilBERT, the second variant passes only the TEXT input to DistilBERT, and feeds the SEN, EMO and SPC attributes in parallel to the output of DistilBERT to the feed-forward component, as depicted in fig.(2).
2) Model 2: DistilBERT with CNN: The base model is modified by appending a CNN to DistilBERT, as shown in fig.(3). Similar to the previous model, we investigate two variants of this architecture. In first variant, the TEXT, SPC, SEN and EMO are fed into the DistilBERT, whose output is then passed to the CNN. In the second variant, only the TEXT is fed into DistilBERT, and the EMO, SPC and SEN attributes are concatenated with output of DistilBERT to be fed into the CNN.

IV. EXPERIMENTAL RESULTS
In both experiments, the dataset was split into 80% train set, 10% valid set, and 10% test set. The train batch size and the test batch size were set to 8, with a learning rate of 1e-05. The DistilBERT was configured with a dropout of 0.3 and model used Sigmoid as its activation function. The loss function used in both architectures was the binary cross entropy loss optimized using the Adam optimizer [21].

A. Experiments with DistilBERT + Feed-Forward Neural Network
The first method was used in three experiments with Dis-tilBERT + Feed-Forward NN. The model was composed of DistilBERT layers, a dropout layer, and one feed-forward hidden layer. The TEXT and EMO attributes were first fed into model and the output of DistilBERT (DB OP) was fed into the feedforward component. This model achieved the accuracy score of 64.92% with a F1 Score of 0.6105. The input to DistilBERT was then extended by adding more meta data: TEXT+EMO+SPC and TEXT+EMO+SPC+SEN, yielding an accuracy of 67% and F1 Score of 0.40.
The model-1 was then modified based on the second variant. The hidden layers in neural nets were increased to size six (with dimensions 768, 800, 512, 256, 128, 2). The TEXT attribute was fed into DistilBERT and the DistilBERT's output (DB OP) was concatenated with the EMO, SPC, SEN attributes to be passed to the feedforward NN. The model performed better than the previous variant, with the accuracy score of 69.37% and the F1 Score of 0.57234. The accuracy and F1-score for the experiments performed with DistilBERT

B. Experiments with DistilBERT + CNN
In second model, a CNN component was appended to DistilBERT with 2 1D convolution layers. The first layer input channel size was 1 and output channel size was 50, and the second layer input channel size was 50 and output channel size was 100. The kernel size for both layers was 20 with stride of 1. The 1D max-pooling of size one was used in all the experiments. We started with the first variant, where the TEXT and other attributes were fed directly into DistilBERT, the output (DB OP) of which was passed into the CNN. In our first experiment, only TEXT was given to DistilBERT, yielding an accuracy score of 68.82% with a F1 Score of 0.5308. Both the accuracy and the F1 Score were similar to the best performer of model-I. In the next experiment, only TEXT was fed into DistilBERT and the output of DistilBERT was concatenated with EMO and then fed into CNN. The model produced an accuracy of 65.54% and a F1 Score of 0.608. In the fourth experiment, the TEXT and SPC attributes were fed into DistilBERT and the output was concatenated with EMO to be passed into the CNN. This model performed better with the accuracy of 68.90% and F1 Score of 0.6542. In  This paper introduced Sentimental LIAR as an extension of the LIAR dataset, and proposed novel model architectures based on DistilBERT for fake claim detection in short text. The proposed architectures extend DistilBERT by adding (1) a feedforward neural network, or (2) a CNN. The LIAR dataset is extended by adding emotions anger, sad, fear, anger and disgust by using IBM NLP API and added sentiment score using Google NLP API. We also included speaker credit as an input attribute to our models.
The experiments performed with DistilBERT + feedforward NN, the accuracy ranged from 68.8% to 69% within the five experiments. These experiments were performed by changing the input structure in the first three experiments and by changing the hidden layers in the latter two experiments. An slight improvement of 1% was observed in the accuracy and no improvements in the F1 Score. This suggests that the model may need to be revised to handle the complexity of the input data. Hence, a CNN-based architecture was investigated in our further experiments.
The experiments were performed with DistilBERT + CNN, the accuracy ranged from 68.82% to 70% within six experiments, and also major improvements were observed in the F1 Score (0.5308 to 0.6430). The best performing model is found to be one where the text attribute is fed directly into DistilBERT, and the output of DistilBERT is concatenated with the emotions, speaker's credit and sentiments before being passed to the CNN.
For both models, it can be observed that adding the metadata (i.e., emotions, sentiments, and speakers' credit) increased the accuracy of model. Also, both the model accuracy and the F1 Score improved with the CNN-based architecture.
The training loss VS validation Loss graphs for DistilBERT + feedforward NN is given in Fig.(4), and for DistilBERT + CNN in Fig.(5). These plots suggest that the models were overfitted only after 2 epochs, which is mostly due to the small size of the dataset. Also, it must be noted that the dataset is imbalanced, with 65% of data labeled as false and only 35% labeled as true. These observations demonstrate the need for the curation of larger and more representative datasets of shorttext claims.
Furthermore, our results further verify that fake claims can be detected in short-text according to exaggerated expressions and strong emotions demonstrated in the text. The proposed architecture also sets a new state-of-the-art benchmark for fake claim classification on the LIAR dataset with an accuracy of 70%.