Year: 2019

Abstract:
It is important to collect credible training samples (x, y) for building dataintensive learning systems (e.g., a deep learning system). In the literature, there is a line of studies on eliciting distributional information from self-interested agents who hold a relevant information. Asking people to report complex distribution p(x), though theoretically viable, is challenging in practice. This is primarily due to the heavy cognitive loads required for human agents to reason and report this high dimensional information. Consider the example where we are interested in building an image classifier via first collecting a certain category of highdimensional image data. While classical elicitation results apply to eliciting a complex and generative (and continuous) distribution p(x) for this image data, we are interested in eliciting samples xi ∼ p(x) from agents. This paper introduces a deep learning aided method to incentivize credible sample contributions from selfish and rational agents. The challenge to do so is to design an incentive-compatible score function to score each reported sample to induce truthful reports, instead of an arbitrary or even adversarial one. We show that with accurate estimation of a certain f -divergence function we are able to achieve approximate incentive compatibility in eliciting truthful samples. We then present an efficient estimator with theoretical guarantee via studying the variational forms of f -divergence function. Our work complements the literature of information elicitation via introducing the problem of sample elicitation. We also show a connection between this sample elicitation problem and f -GAN, and how this connection can help reconstruct an estimator of the distribution based on collected samples.

heading: 1 INTRODUCTION
text: The availability of a large quantity of credible samples is crucial for building high-fidelity machine learning models. This is particularly true for deep learning systems that are data-hungry. Arguably, the most scalable way to collect a large amount of training samples is to crowdsource from a decentralized population of agents who hold relevant sample information. The most popular example is the build of ImageNet (Deng et al., 2009).
The main challenge in eliciting private information is to properly score reported information such that the self-interested agent who holds a private information will be incentivized to report truthfully. At a first look, this problem of eliciting quality data is readily solvable with the seminal solution for eliciting distributional information, called the strictly proper scoring rule (Brier, 1950; Winkler, 1969; Savage, 1971; Matheson & Winkler, 1976; Jose et al., 2006; Gneiting & Raftery, 2007): suppose we are interested in eliciting information about a random vector X = (X1, ..., Xd−1, Y ) ∈ Ω ⊆ Rd, whose probability density function is denoted by p with distribution P. As the mechanism designer, if we have a sample x drawn from the true distribution P, we can apply strictly proper scoring rules to elicit p: the agent who holds p will be scored using S(p, x). S is called strictly proper if it holds for any p and q that Ex∼P[S(p, x)] > Ex∼P[S(q, x)]. The above elicitation approach has two main caveats that limited its application:
• When the outcome space |Ω| is large and is even possibly infinite, it is practically impossible for any human agents to report such a distribution with reasonable efforts. This partially inspired a line of follow-up works on eliciting property of the distributions, which we will discuss later.
• The mechanism designer may not possess any ground truth samples.
In this work we aim to collect credible samples from self-interested agents via studying the problem of sample elicitation. Instead of asking each agent to report the entire distribution p, we hope to elicit samples drawn from the distribution P truthfully. We consider the samples xp ∼ P and xq ∼ Q. In analogy to strictly proper scoring rules1, we aim to design a score function S s.t. Ex∼P[S(xp, x′)] > Ex∼P[S(xq, x′)] for any q ̸= p, where x′ is a reference answer that can be defined using elicited reports. Often, this scoring procedure requires reports from multiple peer agents, and x′ is chosen as a function of the reported samples from all other agents (e.g., the average across all the reported xs, or a randomly selected x). This setting will relax the requirements of high reporting complexity, and has wide applications in collecting training samples for machine learning tasks. Indeed our goal resembles similarity to property elicitation (Lambert et al., 2008; Steinwart et al., 2014; Frongillo & Kash, 2015b), but we emphasize that our aims are different - property elicitation aims to elicit statistical properties of a distribution, while ours focus on eliciting samples drawn from the distributions. In certain scenarios, when agents do not have the complete knowledge or power to compute these properties, our setting enables elicitation of individual sample points.
Our challenge lies in accurately evaluating reported samples. We first observe that the f -divergence function between two properly defined distributions of the samples can serve the purpose of incentivizing truthful report of samples. We proceed with using deep learning techniques to solve the score function design problem via a data-driven approach. We then propose a variational approach that enables us to estimate the divergence function efficiently using reported samples, via a variational form of the f -divergence function, through a deep neutral network. These estimation results help us establish an approximate incentive compatibility in eliciting truthful samples. It is worth to note that our framework also generalizes to the setting where there is no access to ground truth samples, where we can only rely on reported samples. There we show that our estimation results admit an approximate Bayesian Nash Equilibrium for agents to report truthfully. Furthermore, in our estimation framework, we use a generative adversarial approach to reconstruct the distribution from the elicited samples.
We want to emphasize that the deep learning based estimators considered above are able to handle complex data. And with our deep learning solution, we are further able to provide estimates for the divergence functions used for our scoring mechanisms with provable finite sample complexity. In this paper, we focus on developing theoretical guarantees - other parametric families either can not handle complex data, e.g., it is hard to handle images using kernel methods, or do not have provable guarantees on the sample complexity.
Our contributions are three-folds. (1) We tackle the problem of eliciting complex distribution via proposing a sample elicitation framework. Our deep learning aided solution concept makes it practical to solicit complex sample information from human agents. (2) Our framework covers the case when the mechanism designer has no access to ground truth information, which adds contribution to the peer prediction literature. (3) On the technical side, we develop estimators via deep learning techniques with strong theoretical guarantees. This not only helps us establish approximate incentive-compatibility, but also enables the designer to recover the targeted distribution from elicited samples. Our contribution can therefore be summarized as
“eliciting credible training samples by deep learning, for deep learning".

heading: 1.1 RELATED WORKS
text: The most relevant literature to our paper is strictly proper scoring rules and property elicitation. Scoring rules were developed for eliciting truthful prediction (probability) (Brier, 1950; Winkler, 1969; Savage, 1971; Matheson & Winkler, 1976; Jose et al., 2006; Gneiting & Raftery, 2007). Characterization results for strictly proper scoring rules are given in McCarthy (1956); Savage (1971); Gneiting & Raftery (2007). Property elicitation notices the challenge of eliciting complex distributions (Lambert et al., 2008; Steinwart et al., 2014; Frongillo & Kash, 2015b). For instance, Abernethy & Frongillo (2012) characterize the score functions for eliciting linear properties, and Frongillo & Kash (2015a) study the complexity of eliciting properties. Another line of relevant research is peer prediction, where solutions can help elicit private information when the ground truth verification might be missing (De Alfaro et al., 2016; Gao et al., 2016; Kong et al., 2016;
1Our specific formulation and goal will be different in details.
Kong & Schoenebeck, 2018; 2019). Our work complements the information elicitation literature via proposing and studying the question of sample elicitation via a variational approach to estimate f -divergence functions.
Our work also extends the line of work on divergence estimation. The simplest way to estimate divergence starts with the estimation of density function (Wang et al., 2005; Lee & Park, 2006; Wang et al., 2009; Zhang & Grabchak, 2014; Han et al., 2016). Another method based on the variational form (Donsker & Varadhan, 1975) of the divergence function comes into play (Broniatowski & Keziou, 2004; 2009; Nguyen et al., 2010; Kanamori et al., 2011; Ruderman et al., 2012; Sugiyama et al., 2012), where the estimation of divergence is modeled as the estimation of density ratio between two distributions. The variational form of the divergence function also motivates the well-know Generative Adversarial Network (GAN) (Goodfellow et al., 2014), which learns the distribution by minimizing the Kullback-Leibler divergence. Follow-up works include Nowozin et al. (2016); Arjovsky et al. (2017); Gulrajani et al. (2017); Bellemare et al. (2017), with theoretical analysis in Liu et al. (2017); Arora et al. (2017); Liang (2018); Gao et al. (2019). See also Gao et al. (2017); Bu et al. (2018) for this line of work.

heading: 1.2 NOTATIONS
text: For the distribution P, we denote by Pn the empirical distribution given a set of samples {xi}ni=1 following P, i.e., Pn = 1/n · ∑n i=1 δxi , where δxi is the Dirac measure at xi. We denote by
∥v∥s = ( ∑d i=1 |v(i)|s)1/s the ℓs norm of the vector v ∈ Rd where 1 ≤ s < ∞ and v(i) is the i-th entry of v. We also denote by ∥v∥∞ = max1≤i≤d |v(i)| the ℓ∞ norm of v. For any real-valued continuous function f : X → R, we denote by ∥f∥Ls(P) := [ ∫ X |f(x)|
s dP]1/s the Ls(P) norm of f and ∥f∥s := [ ∫ X |f(x)|
s dµ]1/s the Ls(µ) norm of f(·), where µ is the Lebesgue measure. Also, we denote by ∥f∥∞ = supx∈X |f(x)| the L∞ norm of f(·). For any real-valued functions g(·) and h(·) defined on some unbounded subset of the real positive numbers, such that h(α) is strictly positive for all large enough values of α, we write g(α) ≲ h(α) and g(α) = O(h(α)) if |g(α)| ≤ c · h(α) for some positive absolute constant c and any α > α0, where α0 is a real number. We denote by [n] the set {1, 2, . . . , n}.

heading: 2 PRELIMINARY
text: We formulate the question of sample elicitation.

heading: 2.1 SAMPLE ELICITATION
text: We consider two scenarios. We start with an easier case where we, as the mechanism designer, have access to a certain number of group truth samples. This is a setting that resembles similarity to the proper scoring rule setting. Then we move to the harder case where the inputs to our mechanism can only be elicited samples from agents.
Multi-sample elicitation with ground truth samples. Suppose that the agent holds n samples, with each of them independently drawn from P, i.e., xi ∼ P 2 for i ∈ [n]. The agent can report each sample arbitrarily, which is denoted as ri(xi) : Ω → Ω. There are n data {x∗i }i∈[n] independently drawn from the ground truth distribution Q3. We are interested in designing a score function S(·) that takes inputs of each ri(·) and {rj(xj), x∗j}j∈[n]: S(ri(xi), {rj(xj), x∗j}j∈[n]) such that if the agent believes that x∗ is drawn from the same distribution x∗ ∼ P, then for any {rj(·)}j∈[n], it holds with probability at least 1− δ that
n∑ i=1 Ex,x∗∼P [ S ( xi, {xj , x∗j}j∈[n] )] ≥ n∑ i=1 Ex,x∗∼P [ S ( ri(xi), {rj(xj), x∗j}j∈[n] )] − n · ϵ.
2Though we use x to denote the samples we are interested in, x potentially includes both the feature and labels (x, y) as in the context of supervised learning.
3The number of ground truth samples can be different from n, but we keep them the same for simplicity of presentation. It will mainly affect the terms δ and ϵ in our estimations.
We name the above as (δ, ϵ)-properness (per sample) for sample elicitation. When δ = ϵ = 0, it is reduced to the one that is similar to the properness definition in scoring rule literature (Gneiting & Raftery, 2007). We also shorthand ri = ri(xi) when there is no confusion. Agent believes that her samples are generated from the same distribution as of the ground truth samples, i.e., P and Q are same distributions.
Sample elicitation with peer samples. Suppose there are n agents each holding a sample xi ∼ Pi, where the distributions {Pi}i∈[n] are not necessarily the same - this models the fact that agents can have subjective biases or local observation biases. This is a more standard peer prediction setting. We denote by their joint distribution as P = P1 × P2 × ....× Pn. Similar to the previous setting, each agent can report her sample arbitrarily, which is denoted as ri(xi) : Ω → Ω for any i ∈ [n]. We are interested in designing and characterizing a score function S(·) that takes inputs of each ri(·) and {rj(xj)}j ̸=i: S(ri(xi), {rj(xj)}j ̸=i) such that for any {rj(·)}j∈[n], it holds with probability at least 1− δ that
Ex∼P [ S ( xi, {rj(xj) = xj}j ̸=i )] ≥ Ex∼P [ S ( r(xi), {rj(xj) = xj}j ̸=i )] −ϵ.
We name the above as (δ, ϵ)-Bayesian Nash Equilibrium (BNE) in truthful elicitation. We only require that agents are all aware of above information structure as common knowledge, but they do not need to form beliefs about details of other agents’ sample distributions. Each agent’s sample is private to herself.
2.2 f -DIVERGENCE
It is well known that maximizing the expected proper scores is equivalent to minimizing a corresponding Bregman divergence (Gneiting & Raftery, 2007). More generically, we take the perspective that divergence functions have great potentials to serve as score functions for eliciting samples. We define the f -divergence between two distributions P and Q with probability density function p and q, respectively, as
Df (q∥p) = ∫ p(x)f ( q(x)
p(x)
) dµ. (2.1)
Here f(·) is a function satisfying certain regularity conditions, which will be specified later. Solving our elicitation problem involves evaluating the Df (q∥p) successively based on the distributions P and Q, without knowing the probability density functions p and q. Therefore, we have to resolve to a form of Df (q∥p) which does not involve the analytic forms of p and q, but instead sample forms. Following from Fenchel’s convex duality, it holds that
Df (q∥p) = max t(·) Ex∼Q[t(x)]− Ex∼P[f†(t(x))], (2.2)
where f†(·) is the Fenchel duality of the function f(·), which is defined as f†(u) = supv∈R{uv − f(v)}, and the max is taken over all functions t(·) : Ω ⊂ Rd → R.

heading: 3 SAMPLE ELICITATION: A GENERATIVE ADVERSARIAL APPROACH
text: Recall from (2.2) that Df (q∥p) admits the following variational form:
Df (q∥p) = max t(·) Ex∼Q[t(x)]− Ex∼P[f†(t(x))]. (3.1)
We highlight that via functional derivative, (3.1) is solved by t∗(x; p, q) = f ′(θ∗(x; p, q)), where θ∗(x; p, q) = q(x)/p(x) is the density ratio between p and q. Our elicitation builds upon such a variational form (3.1) and the following estimators,
t̂(·; p, q) = argmin t(·) Ex∼Pn [f†(t(x))]− Ex∼Qn [t(x)],
D̂f (q∥p) = Ex∼Qn [t̂(x)]− Ex∼Pn [f†(t̂(x))].

heading: 3.1 ERROR BOUND AND ASSUMPTIONS
text: Suppose we have the following error bound for estimating Df (q∥p): for any probability density functions p and q, it holds with probability at least 1− δ(n) that
|D̂f (q∥p)−Df (q∥p)| ≤ ϵ(n), (3.2)
where δ(n) and ϵ(n) will be specified later in Section 4. To obtain such an error bound, we need the following assumptions.
Assumption 3.1 (Bounded Density Ratio). The density ratio θ∗(x; p, q) = q(x)/p(x) is bounded such that 0 < θ0 ≤ θ∗ ≤ θ1 holds for positive absolute constants θ0 and θ1.
The above assumption is standard in related literature (Nguyen et al., 2010; Suzuki et al., 2008), which requires that the probability density functions p and q lie on a same support. For simplicity of presentation, we assume that this support is Ω ⊂ Rd. We define the β-Hölder function class on Ω as follows.
Definition 3.2 (β-Hölder Function Class). The β-Hölder function class with radius M is defined as Cβd (Ω,M) = { t(·) : Ω ⊂ Rd → R : ∑ ∥α∥1<β ∥∂αt∥∞ + ∑ ∥α∥1=⌊β⌋ sup x,y∈Ω,x ̸=y |∂αt(x)− ∂αt(y)| ∥x− y∥β−⌊β⌋∞ ≤M } ,
where ∂α = ∂α1 · · · ∂αd with α = (α1, . . . , αd) ∈ Nd.
We assume that the function t∗(·; p, q) is β-Hölder, which guarantees the smoothness of t∗(·; p, q).
Assumption 3.3 (β-Hölder Condition). The function t∗(·; p, q) ∈ Cβd (Ω,M) for some positive absolute constants M and β, where Cβd (Ω,M) is the β-Hölder function class in Definition 3.2.
In addition, we assume that the following regularity conditions hold for the function f(·) in the definition of f -divergence in (2.1).
Assumption 3.4 (Regularity of Divergence Function). The function f(·) is smooth on [θ0, θ1] and f(1) = 0. Also, it holds that
(i) f is µ0-strongly convex on [θ0, θ1], where µ0 is a positive absolute constant; (ii) f has L0-Lipschitz continuous gradient on [θ0, θ1], where L0 is a positve absolute constant.
We highlight that we only require that the conditions in Assumption 3.4 hold on the interval [θ0, θ1], where the absolute constants θ0 and θ1 are specified in Assumption 3.1. Thus, Assumption 3.4 is mild and it holds for many commonly used functions in the definition of f -divergence. For example, in Kullback-Leibler (KL) divergence, we take f(u) = − log u, which satisfies Assumption 3.4; in Jenson-Shannon divergence, we take f(u) = u log u − (u + 1) log(u + 1), which also satisfies Assumption 3.4.
We will show that under Assumptions 3.1, 3.3, and 3.4, the bound (3.2) holds. See Theorem 4.2 in Section 4 for details.

heading: 3.2 MULTI-SAMPLE ELICITATION WITH GROUND TRUTH SAMPLES
text: In this section, we focus on multi-sample elicitation with ground truth samples. Under this setting, as a reminder, the agent will report multiple samples. After the agent reported her samples, the mechanism designer obtains a set of ground truth samples {x∗i }i∈[n] ∼ Q to serve the purpose of evaluation. This falls into the standard strictly proper scoring rule setting.
Our mechanism is presented in Algorithm 1.
Algorithm 1 consists of two steps: step 1 is to compute the function t̂(·; p, q), which enables us, in step 2, to pay agent using a linear-transformed estimated divergence between the reported samples and the true samples. We have the following result.
Theorem 3.5. The f -scoring mechanism in Algorithm 1 achieves (2δ(n), 2bϵ(n))-properness.
Algorithm 1 f -scoring mechanism for multiple-sample elicitation with ground truth 1. Compute
t̂(·; p, q) = argmin t(·) Ex∼Pn [f†(t(x))]− Ex∗∼Qn [t(x∗)].
2. For i ∈ [n], pay reported sample ri using S ( ri, {rj , x∗j}nj=1 ) := a− b ( Ex∼Qn [t̂(x; p, q)]− f†(t̂(ri; p, q)) ) for some constants a, b > 0.
The proof is mainly based on the error bound in estimating f -divergence and its non-negativity. Not surprisingly, if the agent believes her samples are generated from the same distribution as the ground truth sample, and that our estimator can well characterize the difference between the two set of samples, she will be incentivized to report truthfully to minimize the difference. We defer the proof to Section B.1.

heading: 3.3 SINGLE-TASK ELICITATION WITHOUT GROUND TRUTH SAMPLES
text: The above mechanism in Algorithm 1, while intuitive, has the following two caveats:
• The agent needs to report multiple samples (multi-task/sample elicitation); • Multiple samples from the ground truth distribution are needed.
To deal with such caveats, we consider the single point elicitation in an elicitation without verification setting. Suppose there are 2n agents each holding a sample xi ∼ Pi 4. We randomly partition the agents into two groups, and denote the joint distributions for each group’s samples as P and Q with probability density functions p and q for each of the two groups. Correspondingly, there are a set of n agents for each group, respectively, who are required to report their single data point according to two distributions P and Q, i.e., each of them holds {xpi }i∈[n] ∼ P and {x q i }i∈[n] ∼ Q. As an interesting note, this is also similar to the setup of a Generative Adversarial Network (GAN), where one distribution corresponds to a generative distribution x | y = 1, and another x | y = 0. This is a connection that we will further explore in Section 5 to recover distributions from elicited samples.
We denote by the joint distribution of p and q as p ⊕ q (distribution as P ⊕ Q), and the product of the marginal distribution as p × q (distribution as P × Q). We consider the divergence between the two distributions:
Df (p⊕ q∥p× q) = max t(·) Ex∼P⊕Q[t(x)]− Ex∼P×Q[f†(t(x))].
Motivated by the connection between mutual information and KL divergence, we define generalized f -mutual information in the follows, which characterizes the generic connection between a generalized f -mutual information and f -divergence.
Definition 3.6 (Kong & Schoenebeck (2019)). The generalized f -mutual information between p and q is defined as
If (p; q) = Df (p⊕ q∥p× q)
Further it is shown in Kong & Schoenebeck (2018; 2019) that the data processing inequality for mutual information holds for If (p; q) when f is strictly convex. We define the following estimators,
t̂(·; p⊕ q, p× q) = argmin t(·) Ex∼Pn×Qn [f†(t(x))]− Ex∼Pn⊕Qn [t(x)],
D̂f (p⊕ q∥p× q) = Ex∼Pn⊕Qn [t̂(x; p⊕ q, p× q)]− Ex∼Pn×Qn [f†(t̂(x; p⊕ q, p× q))], (3.3)
where Pn and Qn are empirical distributions of the reported samples. We denote x ∼ Pn ⊕Qn | ri as the conditional distribution when the first variable is fixed with realization ri. Our mechanism is presented in Algorithm 2.
4This choice of 2n is for the simplicity of presentation.
Algorithm 2 f -scoring mechanism for sample elicitation 1. Compute t̂(·; p⊕ q, p× q) = argmint(·) Ex∼Pn×Qn [f†(t(x))]− Ex∼Pn⊕Qn [t(x)]. 2. Pay each reported sample ri using:
S(ri, {rj}j ̸=i) := a+ b ( Ex∼Pn⊕Qn|ri [t̂(x; p⊕ q, p× q)]−Ex∼Pn×Qn|ri [f †(t̂(x; p⊕ q, p× q))] )
for some constants a, b > 0.
Similar to Algorithm 1, the main step in Algorithm 2 is to estimate the f -divergence between Pn × Qn and Pn ⊕Qn using reported samples. Then we pay agents using a linear-transformed form of it. We have the following result. Theorem 3.7. The f -scoring mechanism in Algorithm 2 achieves (2δ(n), 2bϵ(n))-BNE.
The theorem is proved by error bound in estimating f -divergence, a max argument, and the data processing inequality for f -mutual information. We defer the proof in Section B.2.
The job left for us is to establish the error bound in estimating the f -divergence to obtain ϵ(n) and δ(n). Roughly speaking, if we solve the optimization problem (3.3) via deep neural networks with proper structure, it holds that
δ(n) = exp{−n(d−2β)/(2β+d) log14 n}, ϵ(n) = c · n−2β/(2β+d) log7 n, where c is a positive absolute constant. We state and prove this result formally in Section 4. Remark 3.8. (1) When the number of samples grows, it holds that δ(n) and ϵ(n) decrease to 0 at least polynomially fast, and our guaranteed approximate incentive-compatibility approaches a strict one. (2) Our method or framework handles arbitrary complex information, where the data can be sampled from high dimensional continuous space. (3) The score function requires no prior knowledge. Instead, we design estimation methods purely based on reported sample data. (4) Our framework also covers the case where the mechanism designer has no access to the ground truth, which adds contribution to the peer prediction literature. So far peer prediction results focused on eliciting simple categorical information. Besides handling complex information structure, our approach can also be viewed as a data-driven mechanism for peer prediction problems.
4 ESTIMATION OF f -DIVERGENCE
In this section, we introduce an estimator of f -divergence and establish the statistical rate of convergence, which characterizes ϵ(n) and δ(n). For the simplicity of presentation, in the sequel, we estimate the f -divergenceDf (q∥p) between distributions P and Q with probability density functions p and q, respectively. The rate of convergence of estimating f -divergence can be easily extended to that of mutual information.
By Section 3, estimating f -divergence between P and Q is equivalent to solving the following optimization problem,
t∗(·; p, q) = argmin t(·) Ex∼P[f†(t(x))]− Ex∼Q[t(x)],
Df (q∥p) = Ex∼Q[t∗(x; p, q)]− Ex∼P[f†(t∗(x; p, q))]. (4.1) In what follows, we propose an estimator of Df (q∥p). By Assumption 3.3, it suffices to solve (4.1) on the function class Cβd (Ω,M). To this end, we approximate solution to (4.1) by the family of deep neural networks.
We now define the family of deep neural networks as follows. Definition 4.1. Given a vector k = (k0, . . . , kL+1) ∈ NL+2, where k0 = d and kL+1 = 1, the family of deep neural networks is defined as
Φ(L, k) = {φ(x;W, v) =WL+1σvL · · ·W2σv1W1x : Wj ∈ Rkj×kj−1 , vj ∈ Rkj}. Here we write σv(x) as σ(x − v) for notational convenience, where σ(·) is the ReLU activation function.
To avoid overfitting, the sparsity of the deep neural networks is a typical assumption in deep learning literature. In practice, such a sparsity property is achieved through certain techniques, e.g., dropout (Srivastava et al., 2014), or certain network architecture, e.g., convolutional neural network (Krizhevsky et al., 2012). We now define the family of sparse networks as follows,
ΦM (L, k, s) ={φ(x;W, v) ∈ Φ(L, d) : ∥φ∥∞ ≤M, ∥Wj∥∞ ≤ 1 for j ∈ [L+ 1],
∥vj∥∞ ≤ 1 for j ∈ [L], L+1∑ j=1 ∥Wj∥0 + L∑ j=1 ∥vj∥0 ≤ s}, (4.2)
where s is the sparsity. In contrast, another approach to avoid overfitting is to control the norm of parameters. See Section A.2 for details.
We now propose the following estimators
t̂(x; p, q) = argmin t∈ΦM (L,k,s)
Ex∼Pn [f†(t(x))]− Ex∼Qn [t(x)],
D̂f (q∥p) = Ex∼Qn [t̂(x; p, q)]− Ex∼Pn [f†(t̂(x; p, q))]. (4.3)
The following theorem characterizes the statistical rate of convergence of the estimators defined in (4.3). Theorem 4.2. Let L = O(log n), s = O(N log n), and k = (d, d,O(dN),O(dN), . . . ,O(dN), 1) in (4.2), where N = nd/(2β+d). Under Assumptions 3.1, 3.3, and 3.4, it holds with probability at least 1− exp{−n(d−2β)/(2β+d) log14 n} that
|Df (q∥p)− D̂f (q∥p)| ≲ n− 2β 2β+d log7 n.
We defer the proof of the theorem in Section B.3. By Theorem 4.2, the estimators in (4.3) achieve the optimal nonparametric rate of convergence (Stone, 1982) up to a logarithmic term. By (3.2) and Theorem 4.2, we have
δ(n) = exp{−n(d−2β)/(2β+d) · log14 n}, ϵ(n) = c · n−2β/(2β+d) · log7 n,
where c is a positive absolute constant.

heading: 5 CONNECTION TO GAN AND RECONSTRUCTION OF DISTRIBUTION
text: After sample elicitation, a natural question to ask is how to learn a representative probability density function from the samples. Denote the probability density function from elicited samples as p. Then, learning the probability density function p is to solve for
q∗ = argmin q∈Q Df (q∥p), (5.1)
where Q is the probability density function space. To see the connection between (5.1) and the formulation of f -GAN (Nowozin et al., 2016), by combining (2.2) and (5.1), we have
q∗ = argmin q∈Q max t Ex∼Q[t(x)]− Ex∼P[f†(t(x))],
which is the formulation of f -GAN. Here the probability density function q(·) is the generator, while the function t(·) is the discriminator. By the non-negativity of f -divergence, q∗ = p solves (5.1). We now propose the following estimator
q̂ = argmin q∈Q
D̂f (q∥p), (5.2)
where D̂f (q∥p) is given in (4.3). We define covering number as follows.
Definition 5.1 (Covering Number). Let (V, ∥ · ∥L2) be a normed space, and Q ⊂ V . We say that {v1, . . . , vN} is a δ-covering over Q of sizeN if Q ⊂ ∪Ni=1B(vi, δ), whereB(vi, δ) is the δ-ball centered at vi. The covering number is defined as N2(δ,Q) = min{N : ∃ϵ-covering over Q of size N}.
We impose the following assumption on the covering number of the probability density function space Q. Assumption 5.2. It holds that N2(δ,Q) = O(exp{1/δd/(2β)−1}).
Recall that q∗ = p is the unique minimizer of the problem (5.1). Therefore, the f -divergence Df (q̂∥p) characterizes the deviation of q̂ from p∗. The following theorem characterizes the error bound of estimating q∗ by q̂. Theorem 5.3. Under the same assumptions in Theorem 4.2 and Assumption 5.2, for sufficiently large sample size n, it holds with probability at least 1− 1/n that
Df (q̂∥p) ≲ n− 2β 2β+d · log7 n+min q̃∈Q Df (q̃∥p). (5.3)
We defer the proof of the theorem in Section B.4.
In Theorem 5.3, the first term on the RHS of (5.3) characterizes the generalization error of the estimator in (5.2), while the second term characterizes the approximation error. If the approximation error in (5.3) vanishes, then the estimator q̂ converges to the true density function q∗ = p at the optimal nonparametric rate of convergence (Stone, 1982) up to a logarithmic term.

heading: 6 CONCLUDING REMARKS
text: In this work, we introduce the problem of sample elicitation as an alternative to eliciting complicated distribution. Our elicitation mechanism leverages the variational form of f -divergence functions to achieve accurate estimation of the divergences using samples. We provide theoretical guarantee for both our estimators and the achieved incentive compatibility.
It reminds an interesting problem to find out more “organic" mechanisms for sample elicitation that requires (i) less elicited samples; and (ii) induced strict truthfulness instead of approximated ones.

heading: A AUXILIARY ANALYSIS

heading: A.1 AUXILIARY RESULTS ON SPARSITY CONTROL
text: In this section, we provide some auxiliary results on (4.3). We first state an oracle inequality showing the rate of convergence of t̂(x; p, q). Theorem A.1. Given 0 < ε < 1, for any sample size n satisfies that n ≳ [γ + γ−1 log(1/ε)]2, under Assumptions 3.1, 3.3, and 3.4, it holds that
∥t̂− t∗∥L2(P) ≲ min t̃∈ΦM (L,k,s) ∥t̃− t∗∥L2(P) + γn −1/2 log n+ n−1/2[
√ log(1/ε) + γ−1 log(1/ε)]
with probability at least 1− ε · exp(−γ2). Here γ = s1/2 log(V 2L) and V = ∏L+1 j=0 (kj + 1).
We defer the proof of to Section B.5.
As a by-product, note that t∗(x; p, q) = f ′(θ∗(x; p, q)) = f ′(q(x)/p(x)), based on the error bound established in Theorem A.1, we obtain the following result. Corollary A.2. Given 0 < ε < 1, for the sample size n ≳ [γ+ γ−1 log(1/ε)]2, under Assumptions 3.1, 3.3, and 3.4, it holds with probability at least 1− ε · exp(−γ2) that
∥θ̂ − θ∗∥L2(P) ≲ min t̃∈ΦM (L,k,s) ∥t̃− t∗∥L2(P) + γn −1/2 log n+ n−1/2[
√ log(1/ε) + γ−1 log(1/ε)].
Here γ = s1/2 log(V 2L) and V = ∏L+1 j=0 (kj + 1).
Proof. Note that (f ′)−1 = (f†)′ and f† has Lipschitz continuous gradient with parameter 1/µ0 from Assumption 3.4 and Lemma D.6, we obtain the result from Theorem A.1.

heading: A.2 ERROR BOUND USING NORM CONTROL
text: In this section, we consider using norm of the parameters (specifically speaking, the norm ofWj and vj in (4.1)) to control the error bound, which is an alternative of the network model shown in (4.2). We consider the family of L-layer neural networks with bounded spectral norm for weight matrices W = {Wj ∈ Rkj×kj−1}L+1j=1 , where k0 = d and kL+1 = 1, and vector v = {vj ∈ Rkj}Lj=1, which is denoted as
Φnorm = Φnorm(L, k,A,B) = {φ(x;W, v) ∈ Φ(L, k) : ∥vj∥2 ≤ Aj for all j ∈ [L], ∥Wj∥2 ≤ Bj for all j ∈ [L+ 1]}, (A.1)
where σvj (x) is short for σ(x− vj) for any j ∈ [L]. We write the following optimization problem,
t̂(x; p, q) = argmin t∈Φnorm
Ex∼Pn [f†(t(x))]− Ex∼Qn [t(x)],
D̂f (q∥p) = Ex∼Qn [t̂(x; p, q)]− Ex∼Pn [f†(t̂(x; p, q))]. (A.2) Based on this formulation, we derive the error bound on the estimated f -divergence in the following theorem. We only consider the generalization error bound in this setting. Therefore, we assume that the ground truth t∗(x; p, q) = f ′(q(x)/p(x)) locates within Φnorm. Before we state the theorem, we first define two parameters for the family of neural networks Φnorm(L, k,A,B) as follows
γ1 = B L+1∏ j=1 Bj · √√√√L+1∑ j=0 k2j , γ2 = L · ( √∑L+1 j=1 k 2 jB 2 j + ∑L j=1Aj)∑L+1 j=0 k 2 j ·minj B2j · L∑ j=1 Aj . (A.3)
We proceed to state the theorem. Theorem A.3. We assume that t∗(x; p, q) ∈ Φnorm. Then for any 0 < ε < 1, with probability at least 1− ε, it holds that
|D̂f (q∥p)−Df (q∥p)| ≲ γ1 · n−1/2 log(γ2n) + L+1∏ j=1 Bj · n−1/2 √ log(1/ε).
Here γ1 and γ2 are defined in (A.3).
We defer the proof to Section B.6.
The next theorem uses the results in Theorem A.3. Recall that in Section §A.2, we assume that the minimizer t∗ to the population version problem (4.1) lies within the norm-controlled family of neural networks Φnorm(L, k,A,B).
Theorem A.4. Recall that we defined the parameter γ1 and γ2 of the family of neural networks Φnorm(L, k,A,B) in (A.3), the estimated distribution q̂ in (5.2), and the ground truth q∗ = p. We denote the the covering number of the probability distribution function class Q as N2(δ,Q), then for any 0 < ε < 1, with probability at least 1− ε, we have
Df (q̂∥p) ≲ b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 · √ log(N2[b2(n, γ1, γ2),Q]/ε) + min q̃∈Q Df (q̃∥p),
where b2(n, γ1, γ2) = γ1n−1/2 log(γ2n).
We defer the proof to Section B.7.

heading: B PROOFS OF THEOREMS

heading: B.1 PROOF OF THEOREM 3.5
text: If the player truthfully reports, she will receive the following expected payment per sample i: with probability at least 1− δ(n),
E[S(ri, ·)] := a− b(Ex∼Qn [t̂(x)]− Exi∼Pn [f†(t̂(xi))]) = a− b · D̂f (q∥p) ≥ a− b · (Df (q∥p) + ϵ(n)) (sample complexity guarantee) ≥ a− b · (Df (p∥p) + ϵ(n)) (agent believes p = q) = a− bϵ(n)
Similarly, any misreporting according to a distribution p̃with distribution P̃ will lead to the following derivation with probability at least 1− δ
E[S(ri, ·)] := a− b(Ex∼Qn [t̂(x)]− Exi∼P̃n [f †(t̂(xi))])
= a− b · D̂f (q∥p̃) ≤ a− b · (Df (p∥p̃)− ϵ(n)) ≤ a+ bϵ(n) (non-negativity of Df )
Combining above, and using union bound, leads to (2δ(n), 2bϵ(n))-properness.

heading: B.2 PROOF OF THEOREM 3.7
text: Consider an arbitrary agent i. Suppose every other agent truthfully reports.
E[S(ri, {rj}j ̸=i)] = a+ b(Ex∼Pn⊕Qn|ri [t̂(x)]− Ex∼Pn×Qn|ri{f †(t̂(x))})
= a+ bE[Ex∼Pn⊕Qn|ri [t̂(x)]− Ex∼Pn×Qn|ri{f †(t̂(x))}]
Consider the divergence term E[Ex∼Pn⊕Qn|ri [t̂(x)] − Ex∼Pn×Qn|ri{f†(t̂(x))}]. Reporting a ri ∼ P̃ ̸= P (denoting its distribution as p̃) leads to the following score
Eri∼P̃n [Ex∼P̃n⊕Qn|ri [t̂(x)]− Ex∼P̃n×Qn|ri{f †(t̂(x))}]
= Ex∼P̃n⊕Qn [t̂(x)]− Ex∼P̃n×Qn{f †(t̂(x))} (tower property)
≤ max t Ex∼P̃n⊕Qn [t(x)]− Ex∼P̃n×Qn{f †(t(x))} (max)
= D̂f (p̃⊕ q∥p̃× q) ≤ Df (p̃⊕ q∥p̃× q) + ϵ(n) = If (p̃; q) + ϵ(n) (definition) ≤ If (p; q) + ϵ(n) (data processing inequality (Kong & Schoenebeck, 2019))
with probability at least 1− δ(n) (the other δ(n) probability with maximum score S̄). Now we prove that truthful reporting leads at least
If (p; q)− ϵ(n)
of the divergence term:
Exi∼Pn [Ex∼Pn⊕Qn|xi [t̂(x)]− Ex∼Pn×Qn|xi{f †(t̂(x))}]
= Ex∼Pn⊕Qn [t̂(x)]− Ex∼Pn×Qn{f†(t̂(x))} (tower property) = D̂f (p⊕ q∥p× q) ≥ Df (p⊕ q∥p× q)− ϵ(n) = If (p; q)− ϵ(n) (definition)
with probability at least 1 − δ(n) (the other δ(n) probability with score at least 0). Therefore the expected divergence terms differ at most by 2ϵ(n) with probability at least 1 − 2δ(n) (via union bound). The above combines to establish a (2δ(n), 2bϵ(n))-BNE.

heading: B.3 PROOF OF THEOREM 4.2
text: Step 1. We proceed to bound ∥t∗−t̂∥L2(P). We first proceed to find some t̃ ∈ ΦM (L, k, s). Note that the ground truth t∗ lies on a finite support Ω ⊂ [a, b]d. To invoke Theorem D.5, we denote t′(y) = t∗((b − a)y + a1d), where 1d = (1, 1, . . . , 1)⊤ ∈ Rd. Then the support of t′ lies in the unit cube [0, 1]d. We choose L′ = O(log n), s′ = O(N log n), k′ = (d,O(dN),O(dN), . . . ,O(dN), 1), and m′ = log n, we then utilize Theorem D.5 to construct some t̃′ ∈ ΦM (L′, k′, s′) such that
∥t̃′ − t′∥L∞([0,1]d) ≲ N−β/d.
We further define t̃(·) = t̃′ ◦ ℓ(·), where ℓ(·) is a linear mapping taking the following form
ℓ(x) = x b− a − a b− a · 1d.
To this end, we know that t̃ ∈ ΦM (L, k, s), with parameters L, k, and s given in the statement of Theorem 4.2. We fix this t̃ and invoke Theorem A.1, then with probability at least 1− ε · exp(−γ2), we have
∥t̂− t∗∥L2(P) ≲ ∥t̃− t∗∥L2(P) + γn−1/2 log n+ n−1/2[ √ log(1/ε) + γ−1 log(1/ε)]
≲ N−β/d + γn−1/2 log n+ n−1/2[ √ log(1/ε) + γ−1 log(1/ε)]. (B.1)
Note that γ takes the form γ = s1/2 log(V 2L), where V = O(dL · NL) and L, s given in the statement of Theorem 4.2, it holds that γ = O(N1/2 log5/2 n). Moreover, by the choice N = nd/(2β+d), combining (B.1) and taking ε = 1/n, we know that
∥t̂− t∗∥L2(P) ≲ n−β/(2β+d) log7/2 n (B.2)
with probability at least 1− exp{−nd/(2β+d) log5 n}.
Step 2. We denote by L(t) = Ex∼Q[t(x)] − Ex∼P[f†(t(x))] and L̂(t) = Ex∼Qn [t(x)] − Ex∼Pn [f†(t(x))]. Then from Assumption 3.4 and Lemma D.6, we know that L̂(·) is strongly convex with a constant coefficient. Note that by triangular inequality, we have
|D̂f (q∥p)−Df (q∥p)| = |L̂(t̂)− L(t∗)| ≤ |L̂(t∗)− L̂(t̂)|+ |L̂(t∗)− L(t∗)| =: A1 +A2.
We proceed to bound A1 and A2.
Bound on A1: Recall that L̂(·) is strongly convex. Consequently, we have
A1 ≲ ∥t∗ − t̂∥2L2(P) ≲ n − β2β+d log7/2 n,
with probability at least 1− exp{−nd/(2β+d) log5 n}, where the last inequality comes from (B.2). Bound on A2: Note that both the functions t∗(·) and f†(t∗(·)) are bounded, then by Hoeffding’s inequality, we obtain that
P(A2 ≤ n− β 2β+d log7/2 n) ≥ 1− exp{−n(d−2β)/(2β+d) log14 n}.
Therefore, by combining the above two bounds, we obtain that
|D̂f (q∥p)−Df (q∥p)| ≲ n− β 2β+d log7/2 n
with probability at least 1−exp{−n(d−2β)/(2β+d) log14 n}. This concludes the proof of the theorem.

heading: B.4 PROOF OF THEOREM 5.3
text: We first need to bound the max deviation of the estimated f -divergence D̂f (q∥p) among all q ∈ Q. The following lemma provides such a bound. Lemma B.1. Under the assumptions stated in Theorem 5.3, for any fixed density p, if the sample size n is sufficiently large, it holds that
sup q∈Q
|Df (q∥p)− D̂f (q∥p)| ≲ n− 2β 2β+d · log7 n
with probability at least 1− 1/n.
We defer the proof to Section C.1.
Now we turn to the proof of the theorem. We denote by q̃′ = argminq̃∈QDf (q̃∥p), then with probability at least 1− 1/n, we have
Df (q̂∥p) ≤ |Df (q̂∥p)− D̂f (q̂∥p)|+ D̂f (q̂∥p)
≤ sup q∈Q
|Df (q∥p)− D̂f (q∥p)|+ D̂f (q̃′∥p) ≲ n− 2β 2β+d · log7 n+Df (q̃′∥p). (B.3)
Here in the second line we use the optimality of q̂ among all q̃ ∈ Q to the problem (5.2), while the last inequality uses Lemma B.1 and Theorem 4.2. Moreover, note that Df (q̃′∥p) = minq̃∈QDf (q̃∥p), combining (B.3), it holds that with probability at least 1− 1/n,
Df (q̂∥p) ≲ n− 2β 2β+d · log7 n+min q̃∈Q Df (q̃∥p).
This concludes the proof of the theorem.

heading: B.5 PROOF OF THEOREM A.1
text: For any real-valued function ϱ, we write EP(ϱ) = Ex∼P[ϱ(x)], EQ(ϱ) = Ex∼Q[ϱ(x)], EPn(ϱ) = Ex∼Pn [ϱ(x)], and EQn(ϱ) = Ex∼Qn [ϱ(x)] for notational convenience.
For any t̃ ∈ ΦM (L, k, s), we establish the following lemma.
Lemma B.2. Under the assumptions stated in Theorem A.1, it holds that 1/(4L0) · ∥t̂− t̃∥2L2(P) ≤ 1/µ0 · ∥t̂− t̃∥L2(P) · ∥t̃− t ∗∥L2(P) + {EQn [(t̂− t̃)/2]− EQ[(t̂− t̃)/2]} − {EPn [f†((t̂+ t̃)/2)− f†(t̃)]− EP[f†((t̂+ t̃)/2)− f†(t̃)]} Here µ0 and L0 are specified in Assumption 3.4.
We defer the proof to Section C.2.
Note that by Lemma B.2 and the fact that f† is Lipschitz continuous, we have ∥t̂− t̃∥2L2(P) ≲ ∥t̂− t̃∥L2(P) · ∥t̃− t ∗∥L2(P) + {EQn [(t̂− t̃)/2]− EQ[(t̂− t̃)/2]} − {EPn [f†((t̂+ t̃)/2)− f†(t̃)]− EP[f†((t̂+ t̃)/2)− f†(t̃)]}. (B.4) Furthermore, to bound the RHS of the above inequality, we establish the following lemma. Lemma B.3. We assume that the function ψ : R → R is Lipschitz continuous and bounded such that |ψ(x)| ≤ M0 for any |x| ≤ M . Then under the assumptions stated in Theorem A.1, for any fixed t̃(x) ∈ ΦM , n ≳ [γ + γ−1 log(1/ε)]2 and 0 < ε < 1, we have the follows
P {
sup t(·)∈ΦM (L,k,s) |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| η(n, γ, ε) · ∥ψ(t)− ψ(t̃)∥L2(P) ∨ λ(n, γ, ε)
≤ 16M0 } ≥ 1− ε · exp(−γ2),
where η(n, γ, ε) = n−1/2[γ log n+γ−1 log(1/ε)], λ(n, γ, ε) = n−1[γ2+log(1/ε)], and for any real numbers c1 and c2, we denote by c1∨ c2 = max{c1, c2}. Here γ takes the form γ = s1/2 log(V 2L), where V = ∏L+1 j=0 (kj + 1).
We defer the proof to Section C.3.
Note that the results in Lemma B.3 also apply to the distribution Q, and by using the fact that the true density ratio θ∗(x; p, q) = q(x)/p(x) is bounded below and above, we know that L2(Q) is indeed equivalent to L2(P). We thus focus on L2(P) here. By (B.4), Lemma B.3, and the Lipschitz property of f† according to Lemma D.6, with probability at least 1 − ε · exp(−γ2), we have the following bound
∥t̂− t̃∥2L2(P) ≲ ∥t̂− t̃∥L2(P) · ∥t̃− t ∗∥L2(P)
+O(n−1/2[γ log n+ γ−1 log(1/ε)] · ∥t̂− t̃∥L2(P) ∨ n −1[γ2 + log(1/ε)]), (B.5)
where we recall that the notation γ = s1/2 log(V 2L) is a parameter related with the family of neural networks ΦM . We proceed to analyze the dominant part on the RHS of (B.5).
Case 1. If the term ∥t̂−t̃∥L2(P)·∥t̃−t∗∥L2(P) dominates, then with probability at least 1−ε·exp(−γ2) ∥t̂− t̃∥L2(P) ≲ ∥t̃− t∗∥L2(P).
Case 2. If the term O(n−1/2[γ log n+γ−1 log(1/ε)] ·∥t̂− t̃∥L2(P)) dominates, then with probability at least 1− ε · exp(−γ2)
∥t̂− t̃∥L2(P) ≲ n−1/2[γ log n+ γ−1 log(1/ε)].
Case 3. If the term O(n−1[γ2+log(1/ε)]) dominates, then with probability at least 1−ε ·exp(−γ2) ∥t̂− t̃∥L2(P) ≲ n−1/2[γ + √ log(1/ε)].
Therefore, by combining the above three cases, we have ∥t̂− t̃∥L2(P) ≲ ∥t̃− t∗∥L2(P) + γn−1/2 log n+ n−1/2[ √ log(1/ε) + γ−1 log(1/ε)]. Further the triangular inequality gives us
∥t̂− t∗∥L2(P) ≲ ∥t̃− t∗∥L2(P) + γn−1/2 log n+ n−1/2[ √ log(1/ε) + γ−1 log(1/ε)]
with probability at least 1 − ε · exp(−γ2). Note that the above error bound holds for any t̃ ∈ ΦM (L, k, s), especially for the choice t̃ such that it minimizes ∥t̃− t∗∥L2(P). Therefore, we have ∥t̂− t∗∥L2(P) ≲ min
t̃∈ΦM (L,k,s) ∥t̃− t∗∥L2(P) + γn
−1/2 log n+ n−1/2[ √ log(1/ε) + γ−1 log(1/ε)]
with probability at least 1− ε · exp(−γ2). This concludes the proof of the theorem.

heading: B.6 PROOF OF THEOREM A.3
text: We follow the proof in Li et al. (2018). We denote by the loss function in (A.2) as L[t(x)] = f†(t(xI)) − t(xII), where xI follows the distribution P and xII follows Q. To prove the theorem, we first link the generalization error in our theorem to the empirical Rademacher complexity (ERC). Given the data {xi}ni=1, the ERC related with the class L(Φnorm) is defined as
Rn[L(Φnorm)] = Eε [
sup φ∈Φnorm | 1 n n∑ i=1 εi · L[φ(xi;W, v)]|{xi}ni=1 ] , (B.6)
where εi’s are i.i.d. Rademacher random variables, i.e., P(εi = 1) = P(εi = −1) = 1/2. Here the expectation Eε(·) is taken over the Rademacher random variables {εi}i∈[n]. We introduce the following Lemma B.4 (Mohri et al., 2018), which links the ERC to the generalization error bound. Lemma B.4. Assume that supφ∈Φnorm |L(φ)| ≤ M1, then for any ε > 0, with probability at least 1− ε, we have
sup φ∈Φnorm
{ Ex{L[φ(x;W, v)]} − 1
n n∑ i=1 L[φ(xi;W, v)] } ≲ Rn[L(Φnorm)] +M1 · n−1/2 √ log(1/ε),
where the expectation Ex{·} is taken over xI ∼ P and xII ∼ Q. Equipped with the above lemma, we only need to bound the ERC defined in (B.6). Lemma B.5. Let L be a Lipschitz continuous loss function and Φnorm be the family of networks defined in (A.1). We assume that the input x ∈ Rd is bounded such that ∥x∥2 ≤ B. Then it holds that
Rn[L(Φnorm)] ≲ γ1 · n−1/2 log(γ2n), where γ1 and γ2 are given in (A.3).
We defer the proof to Section C.4.
Now we proceed to prove the theorem. Recall that we assume that t∗ ∈ Φnorm. For notational convenience, we denote by
Ĥ(t) = Ex∼Pn [f†(t(x))]− Ex∼Qn [t(x)], H(t) = Ex∼P[f†(t(x))]− Ex∼Q[t(x)].
Then E[Ĥ(t)] = H(t). We proceed to bound |D̂f (q∥p)−Df (q∥p)| = |Ĥ(t̂)−H(t∗)|. Note that if Ĥ(t̂) ≥ H(t∗), then we have
0 ≤ Ĥ(t̂)−H(t∗) ≤ Ĥ(t∗)−H(t∗), (B.7)
where the second inequality follows from the fact that t̂ is the minimizer of Ĥ(·). On the other hand, if Ĥ(t̂) ≤ H(t∗), we have
0 ≥ Ĥ(t̂)−H(t∗) ≥ Ĥ(t̂)−H(t̂), (B.8) where the second inequality follows that fact that t∗ is the minimizer of H(·). Therefore, by (B.7), (B.8), and the fact that L(φ) ≲ ∏L+1 j=1 Bj for any φ ∈ Φnorm, we deduce that
|Ĥ(t̂)−H(t∗)| ≤ sup t∈Φnorm |Ĥ(t)−H(t)| ≲ Rn[L(Φnorm)] + L+1∏ j=1 Bj · n−1/2 √ log(1/ε) (B.9)
with probability at least 1 − ε. Here the second inequality follows from Lemma B.4. By plugging the result from Lemma B.5 into (B.9), we deduce that with probability at least 1− ε, it holds that
|D̂f (q∥p)−Df (q∥p)| = |Ĥ(t̂)−H(t∗)| ≲ γ1 · n−1/2 log(γ2n) + L+1∏ j=1 Bj · n−1/2 √ log(1/ε).
This concludes the proof of the theorem.

heading: B.7 PROOF OF THEOREM A.4
text: We first need to bound the max deviation of the estimated f -divergence D̂f (q∥p) among all q ∈ Q. We utilize the following lemma to provide such a bound.
Lemma B.6. Assume that the distribution q is in the set Q, and we denote its L2 covering number as N2(δ,Q). Then for any target distribution p, we have
max q∈Q |Df (q∥p)− D̂f (q∥p)| ≲ b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 · √ log(N2[b2(n, γ1, γ2),Q]/ε)
with probability at least 1 − ε. Here b2(n, γ1, γ2) = γ1n−1/2 log(γ2n) and c is a positive absolute constant.
We defer the proof to Section C.5.
Now we turn to the proof of the theorem. We denote by q̃′ = argminq̃∈QDf (q̃∥p). Then with probability at least 1− ε, we have
Df (q̂∥p) ≤ |Df (q̂∥p)− D̂f (q̂∥p)|+ D̂f (q̂∥p) ≤ max
q∈Q |Df (q∥p)− D̂f (q∥p)|+ D̂f (q̃′∥p)
≲ b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 · √ log(N2[b2(n, γ1, γ2),Q]/ε) +Df (q̃′∥p),
where we use the optimality of q̂ among all q̃ ∈ Q to the problem (5.2) in the second inequality, and we uses Lemma B.6 and Theorem 4.2 in the last line. Moreover, note that Df (q̃′∥p) = minq̃∈QDf (q̃∥p), we obtain that
Df (q̂∥p) ≲ b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 √ log(N2[b2(n, γ1, γ2),Q]/ε) + min q̃∈Q Df (q̃∥p).
This concludes the proof of the theorem.

heading: C LEMMAS AND PROOFS

heading: C.1 PROOF OF LEMMA B.1
text: Recall that the covering number of Q is N2(δ,Q), we thus assume that there exists q1, . . . , qN2(δ,Q) ∈ Q such that for any q ∈ Q, there exists some qk, where 1 ≤ k ≤ N2(δ,Q), so that ∥q − qk∥2 ≤ δ. Moreover, by taking δ = δn = n−2β/(2β+d) and union bound, we have
P[sup q∈Q
|Df (q∥p)− D̂f (q∥p)| ≥ c1 · n− 2β 2β+d · log7 n]
≤ N2(δn,Q)∑ k=1 P[|Df (qk∥p)− D̂f (qk∥p)| ≥ c1 · n− 2β 2β+d · log7 n] ≤ N2(δn,Q) · exp(−n d−2β 2β+d · log14 n),
where the last line comes from Theorem 4.2. Combining Assumption 5.2, when n is sufficiently large, it holds that
P[sup q∈Q
|Df (q∥p)− D̂f (q∥p)| ≥ c1 · n− 2β 2β+d · log7 n] ≤ 1/n,
which concludes the proof of the lemma.

heading: C.2 PROOF OF LEMMA B.2
text: For any real-valued function ϱ, we write EP(ϱ) = Ex∼P[ϱ(x)], EQ(ϱ) = Ex∼Q[ϱ(x)], EPn(ϱ) = Ex∼Pn [ϱ(x)], and EQn(ϱ) = Ex∼Qn [ϱ(x)] for notational convenience.
By the definition of t̂ in (4.3), we have EPn [f†(t̂)]− EQn(t̂) ≤ EPn [f†(t̃)]− EQn(t̃). Note that the functionalG(t) = EPn [f†(t)]−EQn(t) is convex in t since f† is convex, we then have
G( t̂+ t̃ 2 )−G(t̃) ≤ G(t̂)−G(t̃) 2 ≤ 0.
By re-arranging terms, we have {EPn [f†((t̂+ t̃)/2)− f†(t̃)]− EP[f†((t̂+ t̃)/2)− f†(t̃)]} − {EQn [(t̂− t̃)/2]− EQ[(t̂− t̃)/2]} ≤ EQ[(t̂− t̃)/2]− EP[f†((t̂+ t̃)/2)− f†(t̃)]. (C.1) We denote by Bf (t̃, t) = EP[f†(t)− f†(t̃)]− EQ(t− t̃). (C.2) then the RHS of (C.1) is exactly −Bf (t̃, (t̂ + t̃)/2). We proceed to establish the lower bound of Bf (t̃, t) using L2(P) norm. From t∗(x; p, q) = f ′(q(x)/p(x)) and (f†)′ ◦ (f ′)(x) = x, we know that q/p = ∂f†(t∗)/∂t. Then by substituting the second term on the RHS of (C.2) using the above relationship, we have
Bf (t̃, t) = EP [ f†(t)− f†(t̃)− ∂f †
∂t (t∗) · (t− t̃) ] = EP [ f†(t)− f†(t̃)− ∂f †
∂t (t̃) · (t− t̃)
] + EP {[ ∂f†
∂t (t̃)− ∂f
†
∂t (t∗)
] · (t− t̃) } = A1 +A2. (C.3)
We lower bound A1 and A2 in the sequel.
Bound on A1. Note that by Assumption 3.4 and Lemma D.6, we know that the Fenchel duality f† is strongly convex with parameter 1/L0. This gives that
f†(t(x))− f†(t̃(x))− ∂f †
∂t (t̃(x)) · [t(x)− t̃(x)] ≥ 1/L0 · (t(x)− t̃(x))2
for any x. Consequently, it holds that A1 ≥ 1/L0 · ∥t− t̃∥2L2(P). (C.4)
Bound on A2. By Cauchy-Schwarz inequality, it holds that
A2 ≥ − √ EP {[ ∂f†
∂t (t̃)− ∂f
†
∂t (t∗)
]2} · √ EP[(t− t̃)2].
Again, by Assumption 3.4 and Lemma D.6, we know that the Fenchel duality f† has 1/µ0-Lipschitz gradient, which gives that∣∣∣∣∂f†∂t (t̃(x))− ∂f†∂t (t∗(x)) ∣∣∣∣ ≤ 1/µ0 · |t̃(x)− t∗(x)| for any x. By this, the term A2 is lower bounded:
A2 ≥ −1/µ0 · ∥t̃− t∗∥L2(P) · ∥t− t̃∥L2(P). (C.5)
Plugging (C.4) and (C.5) into (C.3), we have Bf (t̃, t) ≥ 1/L0 · ∥t− t̃∥2L2(P) − 1/µ0 · ∥t̃− t
∗∥L2(P) · ∥t− t̃∥L2(P). By this, together with (C.1), we conclude that 1/(4L0) · ∥t̂− t̃∥2L2(P) ≤ 1/µ0 · ∥t̂− t̃∥L2(P) · ∥t̃− t ∗∥L2(P) + {EQn [(t̂− t̃)/2]− EQ[(t̂− t̃)/2]} − {EPn [f†((t̂+ t̃)/2)− f†(t̃)]− EP[f†((t̂+ t̃)/2)− f†(t̃)]}. This concludes the proof of the lemma.

heading: C.3 PROOF OF LEMMA B.3
text: For any real-valued function ϱ, we write EP(ϱ) = Ex∼P[ϱ(x)], EQ(ϱ) = Ex∼Q[ϱ(x)], EPn(ϱ) = Ex∼Pn [ϱ(x)], and EQn(ϱ) = Ex∼Qn [ϱ(x)] for notational convenience.
We first introduce the following concepts. For any K > 0, the Bernstein difference ρ2K,P(t) of t(·) with respect to the distribution P is defined to be
ρ2K,P(t) = 2K 2 · EP[exp(|t|/K)− 1− |t|/K].
Correspondingly, we denote by HK,B the generalized entropy with bracketing induced by the Bernstein difference ρK,P. We denote by Hs,B the entropy with bracketing induced by Ls norm, Hs the entropy induced by Ls norm, HLs(P),B the entropy with bracketing induced by Ls(P) norm, and HLs(P) the regular entropy induced by Ls(P) norm.
Since we focus on fixed L, k, and s, we denote by ΦM = ΦM (L, k, s) for notational convenience. We consider the space
ΨM = ψ(ΦM ) = {ψ(t) : t(x) ∈ ΦM}.
For any δ > 0, we denote the following space
ΨM (δ) = {ψ(t) ∈ ΨM : ∥ψ(t)− ψ(t̃)∥L2(P) ≤ δ}, Ψ′M (δ) = {∆ψ(t) = ψ(t)− ψ(t̃) : ψ(t) ∈ ΨM (δ)}.
Note that sup∆ψ(t)∈Ψ′M (δ) ∥∆ψ(t)∥∞ ≤ 2M0 and sup∆ψ(t)∈Ψ′M (δ) ∥∆ψ(t)∥∞ ≤ δ, by Lemma D.4 we have
sup ∆ψ(t)∈Ψ′M (δ)
ρ8M0,P[∆ψ(t)] ≤ √ 2δ.
To invoke Theorem D.3 for G = Ψ′M (δ), we pick K = 8M0 and R = √ 2δ. Note that from the fact that sup∆ψ(t)∈Ψ′M (δ) ∥∆ψ(t)∥∞ ≤ 2M0, by Lemma D.1, Lemma D.2, and the fact that ψ is Lipschitz continuous, we have
H8M0,B(u,Ψ′M (δ),P) ≤ H∞(u/(2 √ 2),Ψ′M (δ)) ≤ 2(s+ 1) log(4 √ 2u−1(L+ 1)V 2)
for any u > 0. Then, by algebra, we have the follows∫ R 0 H1/28M0,B(u,Ψ ′ M (δ),P) du ≤ 3s1/2δ · log(8V 2L/δ).
For any 0 < ε < 1, we take C = 1, and a,C1 and C0 in Theorem D.3 to be
a = 8M0 log(exp(γ 2)/ε)γ−1 · δ,
C0 = 6M0γ −1 √ log(exp(γ2)/ε),
C1 = 33M 2 0 γ −2 log(exp(γ2)/ε).
Here γ = s1/2 log(V 2L). Then it is straightforward to check that our choice above satisfies the conditions in Theorem D.3 for any δ such that δ ≥ γn−1/2, when n is sufficiently large such that n ≳ [γ + γ−1 log(1/ε)]2. Consequently, by Theorem D.3, for δ ≥ γn−1/2, we have
P{ sup t(x)∈ΦM (δ) |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| ≥ 8M0 log(exp(γ2)/ε)γ−1 · δ · n−1/2}
= P{ sup ∆ψ(t)∈Ψ′M (δ) |EPn [∆ψ(t)]− EP[∆ψ(t)]| ≥ 8M0 log(exp(γ2)/ε)γ−1 · δ · n−1/2} ≤ ε · exp(−γ2).
By taking δ = δn = γn−1/2, we have P {
sup t(x)∈ΦM (δ)
|EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| n−1[γ2 + log(1/ε)]
≤ 8M0 } ≥ 1− ε · exp(−γ2). (C.6)
On the other hand, we denote that S = min{s > 1 : 2−s(2M0) < δn} = O(log(γ−1n1/2)). For notational convenience, we denote the set
As = {ψ(t) ∈ ΨM : ψ(t) ∈ ΨM (2−s+2M0), ψ(t) /∈ ΨM (2−s+1M0)}. (C.7)
Then by the peeling device, we have the following P {
sup ψ(t)∈ΨM ,ψ(t)/∈ΨM (δn) |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| ∥ψ(t)− ψ(t̃)∥L2(P) · T (n, γ, ε)
≥ 16M0 }
≤ S∑ s=1 P { sup ψ(t)∈As |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| 2−s+1M0 ≥ 16M0 · T (n, γ, ε) }
≤ S∑ s=1 P{ sup ψ(t)∈As |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| ≥ 8M0 · (2−s+2M0) · T (n, γ, ε)}
≤ S∑ s=1 P{ sup ψ(t)∈ΨM (2−s+2M0) |EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| ≥ 8M0 · (2−s+2M0) · T (n, γ, ε)} ≤S · ε · exp(−γ2)/ log(γ−1n1/2) = c · ε · exp(−γ2),
where c is a positive absolute constant, and for notational convenience we denote by T (n, γ, ε) = γ−1 · n−1/2 log(log(γ−1n1/2) exp(γ2)/ε). Here in the second line, we use the fact that for any ψ(t) ∈ As, we have ∥ψ(t) − ψ(t̃)∥L2(Q) ≥ 2−s+1M0 by the definition of As in (C.7); in the forth line, we use the argument that since As ⊆ ΨM (2−s+2M0), the probability of supremum taken over ΨM (2
−s+2M0) is larger than the one overAs; in the last line we invoke Theorem D.3. Consequently, this gives us
P {
sup ψ(t)∈ΨM
ψ(t)/∈ΨM (δn)
|EPn [ψ(t)− ψ(t̃)]− EP[ψ(t)− ψ(t̃)]| ∥ψ(t)− ψ(t̃)∥L2(P) · n−1/2[γ log n+ γ−1 log(1/ε)]
≤ 16M0 } ≥ 1− ε · exp(−γ2).
(C.8)
Combining (C.6) and (C.8), we finish the proof of the lemma.

heading: C.4 PROOF OF LEMMA B.5
text: The proof of the theorem utilizes following two lemmas. The first lemma characterizes the Lipschitz property of φ(x;W, v) in the input x. Lemma C.1. Given W and v, then for any φ(·;W, v) ∈ Φnorm and x1, x2 ∈ Rd, we have
∥φ(x1;W, v)− φ(x2;W, v)∥2 ≤ ∥x1 − x2∥2 · L+1∏ j=1 Bj .
We defer the proof to Section C.6.
The following lemma characterizes the Lipschitz property of φ(x;W, v) in the network parameter pair (W, v). Lemma C.2. Given any bounded x ∈ Rd such that ∥x∥2 ≤ B, then for any weights W 1 = {W 1j } L+1 j=1 ,W 2 = {W 2j } L+1 j=1 , v
1 = {v1j }Lj=1, v2 = {v2j }Lj=1, and functions φ(·,W 1, v1), φ(·,W 2, v2) ∈ Φnorm, we have
∥φ(x,W 1, v1)− φ(x,W 2, v2)∥
≤ B √ 2L+ 1 ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj · √√√√L+1∑ j=1 ∥W 1j −W 2j ∥2F + L∑ j=1 ∥v1j − v2j ∥22.
We defer the proof to Section C.7.
We now turn to the proof of Lemma B.5. Note that by Lemma C.2, we know that φ(x;W, v) is Lw-Lipschitz in the parameter (W, v) ∈ Rb, where the dimension b takes the form
b = L+1∑ j=1 kjkj−1 + L∑ j=1 kj ≤ L+1∑ j=0 (kj + 1) 2, (C.9)
and the Lipschitz constant Lw satisfies
Lw = B √ 2L+ 1 ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj . (C.10)
In addition, we know that the covering number of W = {(W, v) ∈ Rb : ∑L+1 j=1 ∥Wj∥F +∑L
j=1 ∥vj∥2 ≤ K}, where
K = √√√√L+1∑ j=1 k2jB 2 j + L∑ j=1 Aj , (C.11)
satisfies
N(W, δ) ≤ (3Kδ−1)b. By the above facts, we deduce that the covering number of L(Φnorm) satisfies
N [L(Φnorm), δ] ≤ (c1KLwδ−1)b, for some positive absolute constant c1. Then by Dudley entropy integral bound on the ERC, we know that
Rn[L(Φnorm)] ≤ inf τ>0 τ + 1√ n ∫ ϑ τ √ logN [L(Φnorm), δ] dδ, (C.12)
where ϑ = supg(·;W,v)∈L(Φnorm),x∈Rd |g(x;W, v)|. Moreover, from Lemma C.1 and the fact that the loss function is Lipschitz continuous, we have
ϑ ≤ c2 ·B · L+1∏ j=1 Bj (C.13)
for some positive absolute constant c2. Therefore, by calculations, we derive from (C.12) that Rn[L(Φnorm)] = O ( ϑ√ n · √ b · log KLw √ n ϑ √ b ) ,
then we conclude the proof of the lemma by plugging in (C.9), (C.10), (C.11), and (C.13), and using the definition of γ1 and γ2 in (A.3).

heading: C.5 PROOF OF LEMMA B.6
text: Remember that the covering number of Q is N2(δ,Q), we assume that there exists q1, . . . , qN2(δ,Q) ∈ Q such that for any q ∈ Q, there exists some qk, where 1 ≤ k ≤ N2(δ,Q), so that ∥q − qk∥2 ≤ δ. Moreover, by taking δ = γ1n−1/2 log(γ2n) = b2(n, γ1, γ2) and N2 = N2[b2(n, γ1, γ2),Q], we have
P{max q∈Q |Df (q∥p)− D̂f (q∥p)| ≥ c · [b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 · √ log(N2/ε)]}
≤ N2∑ k=1 P{|Df (q∥p)− D̂f (q∥p)| ≥ c · [b2(n, γ1, γ2) + L+1∏ j=1 Bj · n−1/2 · √ log(N2/ε)]}
≤ N2 · ε/N2 = ε, where the second line comes from union bound, and the last line comes from Theorem A.3. By this, we conclude the proof of the lemma.

heading: C.6 PROOF OF LEMMA C.1
text: The proof follows by applying the Lipschitz property and bounded spectral norm of Wj recursively:
∥φ(x1;W, v)− φ(x2;W, v)∥2 = ∥WL+1(σvL · · ·W2σv1W1x1 − σvL · · ·W2σv1W1x2)∥2 ≤ ∥WL+1∥2 · ∥σvL(WL · · ·W2σv1W1x1 −WL · · ·W2σv1W1x2)∥2 ≤ BL+1 · ∥WL · · ·W2σv1W1x1 −WL · · ·W2σv1W1x2∥2
≤ · · · ≤ L+1∏ j=1 Bj · ∥x1 − x2∥2.
Here in the third line we uses the fact that ∥Wj∥2 ≤ Bj and the 1-Lipschitz property of σvj (·), and in the last line we recursively apply the same argument as in the above lines. This concludes the proof of the lemma.

heading: C.7 PROOF OF LEMMA C.2
text: Recall that φ(x;W, v) takes the form
φ(x;W, v) =WL+1σvLWL · · ·σv1W1x.
For notational convenience, we denote by φij(x) = σvij (W i jx) for i = 1, 2. By this, φ(x;W, v) has the form φ(x;W i, vi) = W iL+1φ i L ◦ · · · ◦ φi1(x). First, note that for any W 1,W 2, v1 and v2, by triangular inequality, we have
∥φ(x,W 1, v1)− φ(x,W 2, v2)∥2 = ∥W 1L+1φ1L ◦ · · · ◦ φ11(x)−W 2L+1φ2L ◦ · · · ◦ φ21(x)∥2 ≤ ∥W 1L+1φ1L ◦ · · · ◦ φ11(x)−W 2L+1φ1L ◦ · · · ◦ φ11(x)∥2
+ ∥W 2L+1φ1L ◦ · · · ◦ φ11(x)−W 2L+1φ2L ◦ · · · ◦ φ21(x)∥2 ≤ ∥W 1L+1 −W 2L+1∥F · ∥φ1L ◦ · · · ◦ φ11(x)∥2
+BL+1 · ∥φ1L ◦ · · · ◦ φ11(x)− φ2L ◦ · · · ◦ φ21(x)∥2. (C.14)
Moreover, note that for any ℓ ∈ [L], we have the following bound on ∥φ1L ◦ · · · ◦ φ11(x)∥2:
∥φiℓ ◦ · · · ◦ φi1(x)∥2 ≤ ∥W iℓφiℓ−1 ◦ · · · ◦ φi1(x)∥2 + ∥viℓ∥2 ≤ Bℓ · ∥φiℓ−1 ◦ · · · ◦ φi1(x)∥2 +Aℓ
≤ ∥x∥2 · ℓ∏ j=1 Bj + ℓ∑ j=1 Aj ℓ∏ i=j+1 Bi, (C.15)
where the first inequality comes from the triangle inequality, and the second inequality comes from the bounded spectral norm of W ij , while the last inequality simply applies the previous arguments recursively. Therefore, combining (C.14), we have
∥φ(x,W 1, v1)− φ(x,W 2, v2)∥2 ≤ ( B · L∏ j=1 Bj + L∑ j=1 Aj L∏ i=j+1 Bi ) · ∥W 1L+1 −W 2L+1∥F
+BL+1 · ∥φ1L ◦ · · · ◦ φ11(x)− φ2L ◦ · · · ◦ φ21(x)∥2. (C.16)
Similarly, by triangular inequality, we have
∥φ1L ◦ · · · ◦ φ11(x)− φ2L ◦ · · · ◦ φ21(x)∥2 ≤ ∥φ1L ◦ φ1L−1 ◦ · · · ◦ φ11(x)− φ2L ◦ φ1L−1 ◦ · · · ◦ φ11(x)∥2
+ ∥φ2L ◦ φ1L−1 ◦ · · · ◦ φ11(x)− φ2L ◦ φ2L−1 ◦ · · · ◦ φ21(x)∥2 ≤ ∥φ1L ◦ φ1L−1 ◦ · · · ◦ φ11(x)− φ2L ◦ φ1L−1 ◦ · · · ◦ φ11(x)∥2 (C.17)
+BL · ∥φ1L−1 ◦ · · · ◦ φ11(x)− φ2L−1 ◦ · · · ◦ φ21(x)∥2,
where the second inequality uses the bounded spectral norm of WL and 1-Lipschitz property of σvL(·). For notational convenience, we further denote y = φ1L−1 ◦ · · · ◦ φ11(x), then
∥φ1L(y)− φ2L(y)∥2 = ∥σ(W 1Ly − v1L)− σ(W 2Ly − v2L)}∥2 ≤ ∥v1L − v2L∥2 + ∥W 1L −W 2L∥F · ∥y∥2,
where the inequality comes from the 1-Lipschitz property of σ(·). Moreover, combining (C.15), it holds that
∥φ1L(y)− φ2L(y)∥2 ≤ ∥v1L − v2L∥2 + ∥W 1L −W 2L∥F · ( B · L−1∏ j=1 Bj + L−1∑ j=1 Aj L−1∏ i=j+1 Bi ) . (C.18)
By (C.17) and (C.18), we have
∥φ1L ◦ · · · ◦ φ11(x)− φ2L ◦ · · · ◦ φ21(x)∥2 ≤ ∥v1L − v2L∥2 + ∥W 1L −W 2L∥F · ( B · L−1∏ j=1 Bj + L−1∑ j=1 Aj L−1∏ i=j+1 Bi ) +BL · ∥φ1L−1 ◦ · · · ◦ φ11(x)− φ2L−1 ◦ · · · ◦ φ21(x)∥2
≤ L∑ j=1 L∏ i=j+1 Bi · ∥v1j − v2j ∥2 + B ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj · L∑ j=1 ∥W 1j −W 2j ∥F
≤ B ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj · L∑ j=1 (∥v1j − v2j ∥2 + ∥W 1j −W 2j ∥F).
Here in the second inequality we recursively apply the previous arguments. Further combining (C.16), we obtain that
∥φ(x,W 1, v1)− φ(x,W 2, v2)∥2
≤ B ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj · (L+1∑ j=1 ∥W 1j −W 2j ∥F + L∑ j=1 ∥v1j − v2j ∥2 )
≤ B √ 2L+ 1 ·
∏L+1 j=1 Bj
minj Bj · L∑ j=1 Aj · √√√√L+1∑ j=1 ∥W 1j −W 2j ∥2F + L∑ j=1 ∥v1j − v2j ∥22,
where we use Cauchy-Schwarz inequality in the last line. This concludes the proof of the lemma.

heading: D AUXILIARY RESULTS
text: Lemma D.1. The following statements for entropy hold.
1. Suppose that supg∈G ∥g∥∞ ≤M , then
H4M,B( √ 2δ,G,Q) ≤ H2,B(δ,G,Q)
for any δ > 0.
2. For 1 ≤ q <∞, and Q a distribution, we have
Hp,B(δ,G,Q) ≤ H∞(δ/2,G),
for any δ > 0. Here H∞ is the entropy induced by infinity norm.
3. Based on the above two statements, suppose that supg∈G ∥g∥∞ ≤M , we have
H4M,B( √ 2 · δ,G,Q) ≤ H∞(δ/2,G),
by taking p = 2.
Proof. See van de Geer & van de Geer (2000) for a detailed proof.
Lemma D.2. The entropy of the neural network set defined in (4.1) satisfies
H∞[δ,ΦM (L, p, s)] ≤ (s+ 1) log(2δ−1(L+ 1)V 2),
where V = ∏L+1 l=0 (pl + 1).
Proof. See Schmidt-Hieber (2017) for a detailed proof.
Theorem D.3. Assume that supg∈G ρK(g) ≤ R. Take a, C, C0, and C1 satisfying that a ≤ C1 √ nR2/K, a ≤ 8 √ nR, a ≥ C0 · [ ∫ R 0 H 1/2 K,B(u,G,P)du ∨ R], and C20 ≥ C2(C1 + 1). It holds that
P[sup g∈G
|EPn(g)− EP(g)| ≥ a · n−1/2] ≤ C exp ( − a 2
C2(C1 + 1)R2
) .
Proof. See van de Geer & van de Geer (2000) for a detailed proof.
Lemma D.4. Suppose that ∥g∥∞ ≤ K, and ∥g∥ ≤ R, then ρ22K,P(g) ≤ 2R2. Moreover, for any K ′ ≥ K, we have ρ22K′,P(g) ≤ 2R2.
Proof. See van de Geer & van de Geer (2000) for a detailed proof.
Theorem D.5. For any function f in the Hölder ball Cβd ([0, 1]d,K) and any integers m ≥ 1 and N ≥ (β+1)d ∨ (K +1), there exists a network f̃ ∈ Φ(L, (d, 12dN, . . . , 12dN, 1), s) with number of layers L = 8 + (m + 5)(1 + ⌈log2 d⌉) and number of parameters s ≤ 94d2(β + 1)2dN(m + 6)(1 + ⌈log2 d⌉), such that
∥f̃ − f∥L∞([0,1]d) ≤ (2K + 1)3d+1N2−m +K2βN−β/d.
Proof. See Schmidt-Hieber (2017) for a detailed proof.
Lemma D.6. If the function f is strongly convex with parameter µ0 > 0 and has Lipschitz continuous gradient with parameter L0 > 0, then the Fenchel duality f† of f is 1/L0-strongly convex and has 1/µ0-Lipschitz continuous gradient (therefore, f† itself is Lipschitz continuous).
Proof. See Zhou (2018) for a detailed proof.

Review summaries:
This paper proposes a sample elicitation framework to tackle the problem of eliciting credible samples from agents for complex distributions. The authors suggest that deep neural frameworks can be applied in this framework for sample elicitation through the derivations. The authors also show the connection between the problem of sample elicitation and f-GAN. However, some problems in the proof on sample elicitation should be clarified or carefully explained.

This paper studies the sample elicitation problem where agents are asked to report samples. The goal is then to evaluate the quality of these reported samples by means of a scoring function S. Following previous related works, the authors use the equivalence between maximizing the expected proper score and minimizing some f-divergence. Their approach relies on the dual expression of the f-divergence which writes as a maximum over a set of functions t. Theoretical guarantees are given for f-scorings obtained (with or without ground truth samples) by first computing the empirical optimal function t, then plugged to estimate the f-divergence. Finally, a deep learning approach is proposed by considering functions f parameterized as sparse deep neural networks.