Credible Sample Elicitation by Deep Learning, for Deep Learning
Authors: Yang Liu
Zuyue Fu
Zhuoran Yang
Zhaoran Wang
Venue:  (2020)

Abstract: It is important to collect credible training samples $(x,y)$ for building data-intensive 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  high-dimensional 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 $x_i \sim 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 \emph{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.

Under review as a conference paper at ICLR 2020
CREDIBLE SAMPLE ELICITATION BY DEEP LEARNING, FOR DEEP LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
It is important to collect credible training samples (r,y) for building data- intensive learning systems (e.g., deep learning system). In the literature, there is 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 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 inter- ested in building an image classifier via first collecting a certain category of high- dimensional image data. While classical clicitation results apply to eliciting a complex and generative (and continuous) distribution p(z) for this image data, we are interested in eliciting samples z; ~ p(x) from agents. This paper introduces a deep learning aided method incentivize credible sample contributions from self- ish and rational agents. The challenge to do so is to design an incentive-compptible score function score each reported sample 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 com- patibility in eliciting truthful samples. We then present an efficient estimator with theoretical guarantee via studying the variational forms of f 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 sam- ple elicitation problem and f-GAN, and how this connection can help reconstruct an estimator of the distribution based on collected samples.
INTRODUCTION
The availability of large quantity of credible samples is crucial for building tigh-fideityy 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 training samples to crowdsource from a decen- tralized population of agents who hold relevant sample information. The most popular example is the build of ImageNet (Deng et all, 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 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 (Bried, 1950 Winklen 1969, Savage, 1971; Matheson & Winkler, 1976 llose all 2006; Gnerting Rattery 2007): sup- pose we are interested in eliciting information about a random vector X = (X1, X Y) E Q S Rdd whose probability density function is denoted by p with distribution I.. As the mechanism designer, if we have sample drawn from the true distribution P. we can apply strictly proper scor- ing rules to elicit p: the agent who holds p will be scored using S(p, x). called strictly proper if it holds for any and that Ez-r (S(, > Ex-r[S(q, a)). The above elicitation approach has two main caveats that limited its application:
When the outcome space [S2] is large and is even possibly infinite, it practically impossible for any human agents to report such a distribution with reasonable efforts. This partially inspired 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.

---

Under review as a conference paper at ICLR 2020
In this work we aim to collect credible samples from self- 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 Tp ~ P and iy Q. In analogy to strictly proper scoring rules", we aim to design a score function S s.t. for any q * p. where x' is a reference answer that can be
(x > (g 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 æs, or a randomly selected æt). 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 GLall 200 Steinwarl et all 2014; Frongillo & Kash, 2015B), but we emphasize that our aims are different property elicitation aims to elicit statistical properties of 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 incen- tivizing 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 to estimate the divergence function efficiently using reported samples, via varia- tional form of the f-divergence function, through a deep neutral network. These estimation results help 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 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 the sample complexity.
Our contributions are three-folds. (I) We tackle the problem of eliciting complex distribution via proposing a sample elicitation framework. Our deep learning aided solution concept makes it prac- tical to solicit complex sample information from human agents. (2) Our framework covers the case when the mechanism designer has access to ground truth information, which adds contri- bution 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 approxi- mate incentive-compatibiee 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".
1.1 RELATED WORKS
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: Saaage, [19]] Matheson & Winkler, 11976 [lose et all 201K: Gneiting & Rattery, 2007). Char- acterization results for strictly proper scoring rules are given in McCarthy (1956);; Savage (I9ID; Gneiting & Raftery (20077). Property elicitation notices the challenge of eliciting complex distri- butions (Lambert et al., 2008; Steinwart et all 2014; Frongillo & Kash 2015b). For instance,
Abernethy Frongillg (2012) characterize the score functions for eliciting linear properties, and Frongillo & Kash (2))a) study the complexity of eliciting properties. Another line of relevant research peer prediction, where solutions can help elicit private information when the ground truth verification might be missing (De Alfaro et all 2016, Gao et all, 2016; Kong et al,, 2016
Our specific formulation and goal will be different in details.
2

---

Under review as a conference paper at ICLR 2020
Kong & Schoenebeck, 2018; 20T)). 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 all, 2005; Lee & Park, 2006 Wang et al, 2009: Zhang & Grabchak, 201 Han et all 2016). Another method based on the variational form (Donsker Varadhan, (975)) of the divergence function comes into play (Bronna
lowski & Keziou, 2004 2009; Nguyen el al, 2010: Kanamori et all, 2011; Ruderman et all. 2012: Sugiyama all 20T2), 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) (Goodtellow etall 2014), which learns the dis- tribution by minimizing the Kullback-Leiibee divergence. Follow-up works include Nowozin et all (2016); Arjovsky al (2017); Gulrajani al, (2017) Bellemare et (2017). with theoretical anal- ysis in Lill et al (201 Arora et all (20I)); Liang
Gao et al (2019). See also Gao et al
(2017); Bu et all (2018) for this line work.
1.2 NOTATIONS
For the distribution P, we denote by Pn the empirical distribution given set of samples {2; ) following P, i.e., Pn 1/n th dz,, where dR; is the Dirac measure 24. We denote by ||v||s = EE 1o(0/))1/> the E, norm of the vector E Rd where S 8 < oo and p(0) is the i-th entry v. We also denote by |ollæ = maxigisa |0() the foo norm of v. For any real-valued continuous function f: X + TR, we denote by [[ := Ux [x]) dpjl// the (PP) norm of f and || : [fx [zx)) du/22/> the La(u) norm of [()), where is the Lebesgue measure. Also, denote by Ilf supzex f(x) the Lo norm of f(-). For any real-valued functions g()) and h(-) defined on some unbounded subset of the real positive numbers, such that h((:) strictly positive for all large enough values of a, we write g(a) S h(a) and g(a) = ((h(a)) if [g(a)] I c h(a) for some positive absolute constant e and any a > ag, where ag is real number. denote by [n] the set .., nn..
2 PRELIMINARY
We formulate the question of sample elicitation.
2.1 SAMPLE ELICITATION
We consider two scenarios. We start with easier case where we, the mechanism designer, have access to a certain number of group truth samples. This a setting that resembles similarity to the proper scoring rule setting. Then we move the harder case where the inputs 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 IP, i.e., ~ IP for i E [ni]. The agent can report each sample arbitrarily, which is denoted as ry rx(x)) : Q + Ω. There are n data {z; he(m)) independently drawn from the ground truth distribution Q We are interested designing a score function S(-) that takes inputs of each r-(-) and (ry(#;), x; "f)]) jein]:
((r:(x)), (1,(2) x "JJE))) such that if the
agent believes that xx is drawn from the same distribution x= PP, then for any (r)()))) it holds with probability at least - 8 that
E -P S(r, (I,, 23 a3>em))
Σ Ex (rr
n
interested in, x potentially includes both the feature and labels (xr, y) as in context supervised learning.
TTooggh use denote the samples
'The number of ground truth samples can be different from but keep them the same for simplicity of presentation. It will mainly affect the terms 8 and our estimations.
3

---

Under review as a conference paper at ICLR 2020
We name the above as (ò, -ppoopeesssss (per sample) for sample elicitation. When 6 = 0, is reduced to the one that is similar to the properness definition in scoring rule literature (Gnerting & Rattery, 2007).. We also shorthand r; (2;);) when there is confusion. Agent believes that her samples are generated from the same distribution as of the ground truth samples, i.e., and Q are same distributions.
Sample elicitation with peer samples. Suppose there are agents each holding sample x, Ps- where the distributions [Ps)een)) are not necessarily the same this models the fact that agents can have subjective biases local observation biases. This is more standard peer prediction setting. We denote by their joint distribution as P = P1 x IP2 x ..... x P..
Similar to the previous setting, each agent can report her sample arbitrarily, which is denoted as rs ra:a)) : Q + Ω for any E [n]. We are interested in designing and characterizing a score func- tion S()) that takes inputs of each rı(-) and (ry(z)))) ((ri(z)), (144))a))))) such that for any (ra())) it holds with probability at least 1 - that
Exp (((zi, (ry(2z) - =33)+a)) 2 Ex-P ((((z))) [ (ry(2,) xy x))++
We name the above as eo)e)Byaasian Nash Equilibrium (BNE) in truthful elicitation. We only require that agents are all aware of above information structure 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 JDIIVERGENCE
It is well known that maximizing the expected proper scores is equivalent minimizing corre- sponding Bregman divergence (Gneiting & Rattery, ((NZ)). More generically, we take the perspec- tive that divergence functions have great potentials to serve as score functions for eliciting samples. We define the fddivergence between two distributions TP and Q with probability density function and g, respectively, as
((x) p(x)
Dy(all)= (aol)))-aa p(x)
du.
(2.1)
Here f()) is a function satisfying certain regularity conditions, which will be specified later. Solving elicitation problem involves evaluating the (glgl)) successively based on the distributions P and Q without knowing the probability density functions p and Therefore, we have to resolve to form of (1lp)) which does not involve the analytic forms of p and q, but instead sample forms. Following from Fenchel's convex duality, it holds that
(gll)))) max Ex~c(((x)] [f>=(((((=))) +(-)
(2.2)
where f!(-) is the Fenchel duality of the function f(-), which is defined as f'( suP tuv f())). and the max is taken over all functions t(-): Ω C Rd - R.
3 SAMPLE ELICITATION: A GENERATIVE ADVERSARIAL APPROACH
Recall from (2.2) that (y(llpp) admits the following variational form:
(y(ll))) max Ex-gg((x)]] Emwr En
(3.1)
+(-)
We highlight that via functional derivative, (3.I) is solved by t" (x; = (x; where ('(x;p.g) (<z)/(()) is the density ratio between p and q. Our elicitation builds upon such variational form (6.I) and the following estimators,
((:p.)) argmin E..P, [f En [(x)),
((-)
(all))) = Emnq [x)] EAwP, 1st (cx))
4

---

Under review as a conference paper at ICLR 2020
3.1 ERROR BOUND AND ASSUMPTIONS
Suppose we have the following error bound for estimating Dy(glpp): for any probability density functions p and y, it holds with probability at least 8(n) that
(all)))) Dy(all)) <(n),
(3.2)
where (()) and (n) will be specified later in Section To obtain such an error bound, we need the following assumptions.
Assumption 3.1 (Bounded Density Ratio). The density ratio 0 (z; p. q) (xx)/p(x) is bounded such that 0 < 0o z 0 < 01 holds for positive absolute constants Og and 01.
The above assumption is standard in related literature (Nguyen et al, 2010: Suzuki ct all 2008). which requires that the probability density functions p and lie on same support. For simplicity of presentation, we assume that this support is f2 C Rd. We define the 3-Hölder function class on f2 as follows.
Definition 3.2 (3-Hölder Function Class). The 3-Hölder function class with radius M defined as
[8*((x) t0t(
(2,, M) = t(-): +(:)::0 ACC - R:
Σ ||
|10 +
sup ||a||= ayE
Σ
||
ull
- L0]
S M
where 8 = 00...... gaa with a = (aI,..., aa) E N
We assume that the function to (= q) is 3-Hölder, which guarantees the smoothness of (:iP. 9). Assumption 3.3 (8-Hölder Condition). The function t" (=pp.) E a (9, M) for some positive ab- solute constants and B, where C (2, .)) is the 3-Hölder function class in Definition 5.2
In addition, we assume that the following regularity conditions hold for the function f(-) in the definition of f-divergence in (2.I).
Assumption 3.4 (Regularity of Divergence Function). The function f(-) is smooth on [0u, 01] and f(1) = 0. Also, it holds that
f Ho-strongly convex on [6u, 01), where μo is positive absolute constant:
(ii) f has Ln-Lipschitz continuous gradient on [6u, 01). where Lo is a positve absolute constant.
We highlight that we only require that the conditions in Assumption 3.4 hold on the interval [0o, 01], where the absolute constants 0n and 0 are specified in Assumption 1.l. Thus, Assumption bx! is mild and it holds for many commonly used functions in the definition of f-divergence. For example, Kullback- Leibler (KL) divergence, we take f'u) = log u, which satisfies Assumption B.4. in
Jenson-Shannon divergence, take f(u) = u log u (u 1) log(u 1), which also satisfies Assumption 37!
We will show that under Assumptions 5 5K3 and 3.4 the bound (622) holds. See Theorem 2 in Section for details.
3.2 MULTI-SAMPLE ELICITATION WITH GROUND TRUTH SAMPLES
In this section, focus as a reminder, the agent will report multiple samples. After the agent reported her samples, the mechanism designer obtains a of ground truth samples {x² ]eju) Q serve the purpose of evaluation. This falls into the standard strictly proper scoring rule setting.
elicitation with ground truth samples. Under this setting,
Our mechanism is presented in Algorithm MI
Algorithm II consists of two steps: step 1 is to compute the function 7(: q). which enables us, in step 2, to pay agent using a tmnaa-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 accieves (25(n). 2be (n)))-properness.

---

Under review as a conference paper at ICLR 2020
Algorithm 1 f-scoring mechanism for multiple-sample elicitation with ground truth 1. Compute
(:Pp.)) = argmin Eg (()) -,a -Ba ((==))
+(-)
2. For i [n], pay reported sample r; using
(ri; (1,,-)}}==) == b(Bzaq, Me:....M:p.000 (((ap,))))
for some constants a, >
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 minimize the difference. We defer the proof to Section B
3.3 SINGLE-TASK ELICITATION WITHOUT GROUND TRUTH SAMPLES
The above mechanism in Algorithm M. while intuitive, has the following two caveats:
The agent needs to report multiple samples tasttte elicitation);
Multiple samples from the ground truth distribution are needed.
To deal with such caveats, we consider the single point elicitation an elicitation without verifica- tion setting. Suppose there are 2n agents each holding sample æ; PP B. We randomly partition the agents into two groups, and denote the joint distributions for each group's samples as and Q with probability density functions p and q for each of the two groups. Correspondingly, there are set of n agents for each group, respectively, who are required to report their single data point accord- ing two distributions IP and Q, i.e., each them holds [=]])ej interesting note, this is also similar to the setup of a Generative Adversarial Network (GAN), where one distribution corresponds
and {af Jee[ Q. As an
generative distribution y 1, and another y = 0. This is connection that we will further explore in Section E to recover distributions from elicited samples.
We denote by the joint distribution of p and q as p @ q (distribution as IP @ Q), and the product of the marginal distribution two distributions:
q (distribution as P x Q). We consider the divergence between the
Dy x q) max Exxxxxxee - Exxxxxl (())
Motivated by the connection between mutual information and KL divergence, we define general- ized f-mutual information in the follows, which characterizes the generic connection between generalized f-mutual information and f-divergence.
Definition 3.6 (Kong & Schoenebeck (2019)). The generalized f-mutual information between and @ is defined as
1 4) = Dy @ allp x 4)
Further it is shown in Kong & Schoenebeck (2018; 2019) that the data processing inequality for mutual information holds for (p: q) when f is strietly convex. We define the following estimators.
p::po.pppp ②) argmin E Ex x [f (t(x)) Ex 00. [t(x)],
{))
D q) Ex-r, eq. [ (x;p q.p 4)] Ex x a. (5 (xx: 4))} (3.3)
where Pn and Qn are empirical distributions of the reported samples. We denote ~~ + Qn as the conditional distribution when the first variable is fixed with realization r,. Our mechanism is presented in Algorithm A
*This choice of 2m is for the simplicity of presentation.

---

Under review as a conference paper at ICLR 2020
Algorithm 2 f-scoring mechanism for sample elicitation
1. Compute [(:;p @ p q) argmin(()) Ex-P, xQ. [ (1(x)) Ex-p, 122. [[(x)].
2. Pay each reported sample r; using:
S(ri, (ri)ass) == a b(xxF..x....... Sttp:rr......xeeeppx..... (xpppxx E. (xxxp,
for some constants a, >
Similar to Algorithm MI the main step in Algorithm Ø is to estimate the f-divergence between P,, x Qn and F, Q. using reported samples. Then we pay agents using a linear-transformed form of We have the following result.
Theorem 3.7. The f-scoring mechanism in Algorithm 2 acchieve (26(n), 2be (
The theorem is proved by error bound in estimating ff f-divergence, max argument, and the data processing inequality for f-mutual information. We defer the proof in Section H
The job left for is to establish the error bound in estimating the f-divergence to obtain e(n) and 6(n). Roughly speaking, if we solve the optimization problem ((5.3) via deep neural networks with proper structure, holds that
(n)) exp(-n
(Mcp(-nd-20)/(22-4) (0).4-2))(2200))) log n).
c(n) c. 28/(28+4) log' n,
where e is a positive absolute constant. We state and prove this result formally in Section
Remark 3.8. (1) When the number samples grows, it holds that 8(n) and e(n) decrease to at least polynomially fast, and our guaranteed approximate incentive-compatiblig approaches 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 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 access 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 data-driven mechanism for peer prediction problems.
4 ESTIMATION OF f f-DIVERGENCE
In this section, we introduce an estimator of f-divergence and establish the statistical rate of con- vergence, which characterizes e(n) and 8(n). For the simplicity of presentation, in the sequel, estimate the f-divergence (g(l)p) between distributions TP and Q with probability density functions p and g, respectively. The rate of convergence of estimating f f-divergence can be easily extended to that of mutual information.
By Section estimating fddivergence between P and Q is equivalent solving the following opti- mization problem,
t' (:pp.g) = argmin E Eg. (f - - Ex-ol((x)],
((-)
(g(lp))) Ez~oll" (x:p.g) Ez-r(ft(r" (x; p.)))
(4.1)
In what follows, we propose estimator of (q(lpp). By Assumption B.3. it suffices to solve (LII
on the function class eg (2. M). To this end, approximate solution to (2.l) by the family of deep neural networks.
We now define the family of deep neural networks follows.
Definition 4.1. Given a vector l: family of deep neural networks defined as
E N4+2 where kn d and k = 1, the
(L, k) (sp(;; W, W WL+10 W20,, Wix: W, B R Here we write o, (x) as ar (x v) for notational convenience, where a(-) is the ReLU activation function.
7

---

The following theorem characterizes the statistical rate of convergence of the estimators defined in Under review as a conference paper at ICLR 2020
To avoid overfitting, the sparsity of the deep neural networks is typical assumption in deep learn- ing literature. In practice, such a sparsity property is achieved through certain techniques, c.g., dropout (Snvastava all 2014), certain network architecture, e.g., convolutional neural network (Krizhevsky et all 2012). We now define the family of sparse networks as follows,
LM ki 8) = (a(a; W, 0) E L(L, d): 11 S M,
1W I for j E [L++1,
L++1
I llo + Σ
I|u I 1 for j E [L],
Σ
I
Ilyyllo - 8
(4.2)
j=1
j=1
where 8 is the sparsity. In contrast, another approach to avoid overfitting is to control the norm of parameters. See Section A for details.
We now propose the following estimators
(s;p.9) argmin E (1(x))) R [tx))]: tE.kr(Lnkss)
(y(gl) = B. - If (f(:p.,)))..
(4.3)
Theorem 4.2. Let Olog = O(N log and k (d, d, (dN), O(dN). O(dN), o(dN),. 1)
in (2.22,, where N (23+ Under Assumptions BTL 5,3, and 34 holds with probability least 1 exp(-n (d-22)22228) log 11 n} that
2d (Dy(all)) Dy(alle) S 29nd log' n.
We defer the proof of the theorem in Section B. By Theorem A.2 the estimators in achieve the optimal nonparametric rate of convergence (Stone. 1982) up logarithmic term. By (3.2) and Theorem k we have
((n) exp(-n' (28/(2)+)) (2)) log n},
e(n) = c n 28/(2844) log' n,
where c is a positive absolute constant.
CONNECTION TO GAN AND RECONSTRUCTION OF DISTRIBUTION
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 (gllp))
(5.1)
where Q the probability density function space.
To see the connection between (5_I) and the formulation of f-GAN (Nowozın et all 2016), by combining (2.2) and (D, we have
= argmin max [x)) Re
which is the formulation of f-GAN. Here the probability density function g(-) is the generator, while the function t(-) is the discriminator.
By the non-negativity of f-divergence, q² p solves (5.I). We propose the following estimator
q = argmin Dy (gllp),
(5.2)
where (gll))) is given in (+))
We define covering number as follows.
8

---

Under review as a conference paper at ICLR 2020
Definition 5.1 (Covering Number). Let (V. || -1112) be normed space, and Q C V. We say that
(V1...., Uy } a d-covering over Q of size N if Q C , 6). where B( 5) is the b-ball cen- tered at v2. The covering number is defined as [2 Q) min(N: Be-covering over Q of size N).
We impose the following assumption on the covering number the probability density function space Q
Assumption 5.2. It holds that (6, Q)
Recall that q" = p is the unique minimizer of the problem (5. Therefore, the f f-divergence Dy(ī characterizes the deviation of from p". The following theorem characterizes the error bound of estimating q" by 7.
Theorem 5.3. Under the same assumptions in Theorem + and Assumption 6.2 for sufficiently large sample size n, it holds with probability at least - 1/n that
20 20oa log' 7 min (y(ī)p). TEQ
Dy(p) S
(5.3)
We defer the proof of the theorem in Section
In Theorem the first term on the RHS ) characterizes the generalization error of the estimator in while the second term characterizes the approximation error. If the approximation error in (b.5) vanishes, then the estimator 9 converges to the true density function q" = p at the optimal nonparametric rate of convergence (Stone, (982) up to logarithmic term.
CONCLUDING REMARKS
In this work, we introduce the problem of sample elicitation 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.
REFERENCES
Jacob D Abernethy and Rafael M Frongillo. A characterization scoring rules for linear properties. In Conference on Learning Theory, pp. 27-1, 2012.
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein GAN. arXiv preprint
arXiv:1701.000 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In International Conference on Machine Learning, pp. 224-20 232, 2017.
Mare G Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan. Stephan Hoyer, and Rémi Munos. The Cramer distance as a solution to biased Wasserstein gradi- ents. arXiv preprint arXiv:1705.100 2017.
Glenn W. Brier. Verification of forecasts expressed in terms of probability. Monthly Weather Review, 78(1):1-3, 1950.
Michel Broniatowski and Amor Keziou. Parametric estimation and tests through divergences. Tech- nical report, Citeseer, 2004.
Michel Broniatowski and Amor Keziou. Parametric estimation and tests through divergences and the duality technique. Journal of Multivariate Analysis, 100(1):16-36, 2009.
Yuheng Bu, Shaofeng Zou, Yingbin Liang, and Venugopal V Veeravalli. Estimation of KL di- vergence: Optimal minimax rate. IEEE Transactions on Information Theory, 64(4):2648-22 2674, 2018.

---

Under review as a conference paper at ICLR 2020
Luca De Alfaro, Michael Shavlovsky, and Vassilis Polychronopoulos. Incentives for truthful peer grading. arXiv preprint arXiv:1604.03177 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Conference on Computer Vision and Pattern Recognition, pp. 2009.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain Markov process expectations for large time. I. Communications on Pure and Applied Mathematics, 28(1):1-47, 1975.
Rafael Frongillo and Ian Kash. On elicitation complexity. In Advances in Neural Information Processing Systems, pp. 3258-3266, 2015a.
Rafael Frongillo and lan A Kash. Vector-valued property elicitation. In Conference on Learning Theory, pp. 710-727, 201
Alice Gao, James R Wright, and Kevin Seyton-Brown Incentivizing evaluation via limited access to ground truth: Peer-prediction makes things worse. arXiv preprint arXiv:1606.0704. 070042, 2016.
Chao Gao, Yuan Yao, and Weizhi Zhu. Generative adversarial for robust scatter estimation: A proper scoring rule perspective. arXiv preprint 19X3v01903.011 2019.
Weihao Gao, Sewoong Oh, and Pramod Viswanath. Density functional estimators with k-nearest neighbor bandwidths. In International Symposium on Information Theory, pp. 1351-1355, 2017.
Tilmann Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-375 2007.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pp. 5767-5777, 2017.
Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax rate-optimal estimation of divergences between discrete distributions. arXiv preprint 16Xiv:1605.09124 2016.
Victor Richmond Jose, Robert F. Nau, and Robert L. Winkler. Scoring rules, generalized entropy and utility maximization. Working Paper, Fuqua School of Business, Duke University, 2006.
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama.
fomnaa.-diie f-divergence estimation and two-sample homogeneity test under semiparametric density -atioo models. IEEE Transactions on Information Theory, 58(2):788-775 2011.
Yuqing Kong and Grant Schoenebeck. Water from two rocks: Maximizing the mutual information. In Conference on Economics and Computation, pp. 177-194, 2018.
Yuqing Kong and Grant Schoenebeck. An information theoretic framework for designing informa- tion elicitation mechanisms that reward truth-telling. Transactions on Economics and Computa- tion, 7(1);2, 2019.
Yuqing Kong, Katrina Ligett, and Grant Schoenebeck. Putting peer prediction under the miero (cconomic) scope and making truth-telling focal. In International Conference on Web and Internet Economics, pp. 251-264. Springer, 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
N.S. Lambert, D.M. Pennock, and Y. Shoham. Eliciting propertics of probability distributions. In Conference Electronic Commerce, pp. 129-138. 2008
10

---

Under review as a conference paper at ICLR 2020
Young Kyung Lee and Byeong U Park. Estimation of Becllbacck-eiibble divergence by local likeli- hood. Annals of the Institute of Statistical Mathematics, (8(2):327-344) 2006.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: CNNs, ResNets, and beyond. arXiv preprint arXiv:1806.05/33 2018.
Tengyuan Liang. On how well generative adversarial networks learn densities: Nonparametric and parametric results. arXiv preprint 1811vv18111031111 2018.
Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence proper- ties of generative adversarial learning. In Advances in Neural Information Processing Systems, pp. 5545-5553, 2017.
James E. Matheson and Robert L. Winkler. Scoring rules for continuous probability distributions. Management Science, 22(10):1087-1096 1976.
John McCarthy. Measures of the value of information. Proceedings of the National Academy of Sciences of the United States of America, 42(9):654-655, 1956.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847-586) 2010.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Advances in neural information processing systems, pp. 271-279, 2016.
Avraham Ruderman, Mark Reid, Darío Garela-Garefa, and James Petterson. Tighter varia- tional representations of f-divergences via restriction to probability measures. arXiv:1206.46660 2012.
arXiv preprint
Leonard J. Savage. Elicitation of personal probabilitics and expectations. Journal of the American Statistical Association, 66(336):783-88 801, 1971.
Johannes Schmidt-Hieber Nonparametric regression using deep neural networks with relu activation function. arXiv preprint arXiv:1708.06633, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, (900:1992919933 2014.
Ingo Steinwart, Chloé Pasin, Robert Williamson, and Siyu Zhang. Elicitation and identification of properties. In Conference on Learning Theory, pp. 482-526, 2014.
Charles J Stone. Optimal global rates of convergence for nonparametric regression. The annals of statistics, pp. 1040-104 1053, 1982.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012.
Taiji Suzuki, Masashi Sugiyama, Jun Sese, and Takafumi Kanamori. Approximating mutual infor- mation by maximum likelihood density ratio estimation. In New challenges for feature selection in data mining and knowledge discovery, pp. 5-20, 2008.
Sara van de Geer and Sara van de Geer. Empirical Processes in M-estimation, volume 6. Cam- bridge university press, 2000.
Qing Wang. Sanjeev R Kulkarni, and Sergio Verdú. Divergence estimation of continuous distri- butions based on data-dependent partitions. IEEE Transactions on Information Theory, 51(9): 3064-3074, 2005.
11

---

Under review as a conference paper at ICLR 2020
Qing Wang, Sanjeev R Kulkarni, and Sergio Verdú. Divergence estimation for multidimensional densities via n-eeabest-neighhor distances. IEEE Transactions on Information Theory, 55(5): 2392-2405, 2009.
Robert L. Winkler. Scoring rules and the evaluation of probability assessors. Journal of the American Statistical Association, 64(327):1073-1078, 1969.
Zhiyi Zhang and Michael Grabehak. Nonparametric estimation of Kullback-Leibler divergence. Neural computation, 26(1 1):2570-25592 2014.
Xingyu Zhou. On the Fenchel duality between strong convexity and Lipschitz continuous gradient. arXiv preprint arXiv: 0803 2018.
12

---

Under review as a conference paper at ICLR 2020
A AUXILIARY ANALYSIS
A.1 AUXILIARY RESULTS ON SPARSITY CONTROL
In this section, provide some auxiliary results (4.3) We first state oracle inequality showing the rate of convergence of f(::p. g).
Theorem A.1. Given 0 < < 1, for any sample size n satisfies that n. Z h + 7 log(1/og111// (
under Assumptions T.I. 3.. and BEL,, it holds that
7 - (2 X min (L.kr(L.
|| - ("1)2)()) + + 1/2 log + n "oggo="""" +
with probability at least 1 g- e exp( Here y = log and V =1 (kg + 1).
We defer the proof of to Section
As by-product, note that 1" (x: ("rr
based on the error bound
established in Theorem A.T. we obtain the following result.
Corollary A.2. Given 0 < < 1, for the sample size n h + + lo (1/e)] under Assumptions
and 34 it holds with probability at least -E exp( that
110 12( S min (L,,,)
|| - t" (122(()) + + 1/2 log 1/2 l/ + + 7 (og([//)))
Here y 1/22 log( log(1V L) and V = IT
L+1 (ky 1).
Proof. Note that (f))1 = (fty and fl has Lipschitz continuous gradient with parameter 1/po
from Assumption 3.4 and Lemma D.6. we obtain the result from Theorem A.
A.2 ERROR BOUND USING NORM CONTROL
In this section, we consider using norm of the parameters (specifically speaking, the norm of W and By in ()) to control the error bound, which an alternative of the network model shown in (9.2).
We consider the family of L-layer neural networks with bounded spectral norm for weight matrices
W = [W E IR xky I++1 where Ko d and kL+1 = 1, and vector = {u, R H which
Jj=1
denoted as
$ Dorm norm (L, k, B) (p(0; W, v) L(L, 11yll2 s A, for all j E [L],
[W S B, for all j E [L+ 1]}.
(A.1)
where ue (1) is short for ox vz)) for any j E [L]. We write the following optimization problem,
(x:p,9) = argmin E (t(x))) - E.ne, [(x)),
(y(ll))) E... [(xpp Ey-r, (M),)))))))
(A.2)
Based on this formulation, we derive the eтror 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 L" (x;; p. 4) = f'(((x)//(( (px)) locates within P Before we state the theorem, we first define two parameters for the family of neural networks 4 moomm (L, k. A, B) as follows
L+1
L+1
L. (v Σ 12 ΣØ Aj)
L
B
II
B
Σ
72 =
Σ A
(A.3)
E/t h3 ming B²
J=1
1=
1=1
We proceed to state the theorem.
Theorem A.3. We assume that t* (z; E @norm Then for any 0 < e < 1, with probability
least 1 - E, it holds that
1-1
(Dlal))) - Dy(alp)) $ m n - 1/2 log(12n)
II
By n 1/2 Vlo((1/e)
+ 3
Here 71 and 72 defined in A.
13

---

Under review as a conference paper at ICLR 2020
We defer the proof to Section BG
The next theorem uses the results in Theorem AWC Recall that Section $ we assume that
the minimizer& t* to the population version problem (9 lies within the norm-controlled family of neural networks 1 norn (L, B).
Theorem A.4. Recall that we defined the parameter Y1 and of the family of neural networks P norm [I., k, A, B) (A.3), the estimated distribution q in (5.22), and the ground truth q" = p. We denote the the covering number of the probability distribution function class @ N2 Q), then for any 0 < E < I, with probability at least E, we have
L+1
Dj (r(pp S b2 71, 72) +
II j=1
Bj n 1/2,
(ogg(N)(b21n) (,, 72, 21/E) + min Dy
ge
where (2,n, n1 12) 7/1 1/1 1/2
1og(?2n).
We defer the proof to Section B
B PROOFS OF THEOREMS
B. PROOF OF THEOREM SX
If the player truthfully reports, she will receive the following expected payment per sample with probability at least 1 - d(n),
(lS(r, == b(Ez-Q. [xx] Ex, ER,,P (ft ((z))))
= a (qlpp))
2 b. (Dy(9ll)) + ((n)) (sample complexity guarantee)
2 a b. (Dy("ly)) + <(n)) (agent believes = ②)
be(n)
Similarly, any misreporting according to a distribution I with distribution IP will lead to the following derivation with probability least 8
B[S(ri:)) = a b(E..Q [x)) F2 ( ((x))))
b. by (g1p))
< b. (D <(n))
S a + be(n) nnoa-iegativity D,)
(6<((n)))propemmess Combining above, and using union bound, leads to (26(n), 2be(n)) properness.
B.2 PROOF OF THEOREM
Consider an arbitrary agent i. Suppose every other agent truthfully reports.
E[S(r, (rgh+t)) = a + b(ExxP ad.. ir, [x)] Ex-P, xu. ( (x))))
+ DBBBE.PP,.... [(x)] Ex-P, (f
14

---

Under review as a conference paper at ICLR 2020
Consider the divergence term E[Ex-P, eQa/ [((]]] - Ex-P, /rx (ft (f())) Reporting r; P + (denoting its distribution as p) leads to the following score
F r, F #Q. [x)] Px xQ, (())))
Ex SQ. [x)] - B xx xe. (M(()))) (tower property)
max B x=P, [x)] Xx (1(x)) (max)
D @ qlpp
S Dy(ō alli q) c(n)
()) d()) (definition)
S (y(r:)) e(n) (data processing inequality (Kong Schoeneheck, 2019))
with probability at least 6(n) (the other d(n) probability with maximum score S).
Now we prove that truthful reporting leads at least
[y(p:)) g) e(n)
of the divergence term:
Ex,oP, [xxP eQ [f(x)] Ex XQn ms (f*((()))
= Ex. [(x)] ExNPxx ((x)) (tower property)
= D e 4/lp x q)
2 @ qlp x - c(n)
= (v; - <(n) (definition)
with probability at least 1 8(n) (the other 8(n) probability with score at least 0). Therefore the expected divergence terms differ at most by 2c(n) with probability at least 1 - 25(n) (via union bound). The above combines to establish (25(n). 2B.(B))
B.3 PROOF OF THEOREM
Step 1. We proceed to bound ||t -11,,,,, We first proceed to find some 7 E LM k, s). Note that the ground truth t" lies finite support Ω C [a, bjd. To invoke Theorem D... we denote ('(v) lies in the unit cube [0, 1] We choose L' = (logn). = O(N logn), n), k' (d, O(dN). O(dN).... OddN), 1), and m' log then utilize Theorem D.5 construct some 1' E T (L', W such that
((b - a)y + ala). where 14 = (1.1......1
E Rd. Then the support
+'1lz~((0.1))) & B/d
We further define F(.) = 7o E(-) where E(-) is linear mapping taking the following form
x a
((x) = b-a
1g-
To this end, we know that f 4 (L, k. s), with parameters L, k. and given in the statement of Theorem 2.21 We fix this and invoke Theorem A.l. then with probability least 8 e exp( we have
[| (E-t"Ilaa() S 1 t t']1 + 7n 1/2 logn n + n 1/2 1/ log((//))) + 1 log(1/e)]
$ N 3/d + +mm log n Tog(1/8) + 7 log(1/e)]
(B.1)
Note that 7 takes the form 7 = /1/2 log (2)),, where V = O(d NL) and L, given in the 1/2 log 3/2 n). Moreover, by the choice N =
statement of Theorem it holds that n d/(22++)) combining and taking e = 1/n,, we know that
[ - t" (2]222(1) S n 0/(28++) log" 7/2
(B.2)
15

---

Under review as a conference paper at ICLR 2020
with probability at least - expl (npp[nn//222a00 log n).
Step 2. We denote by C(t) Ex>c Ex-p Pf (f(=)) and 2(t) Ex [e,[((()]]]
Ex-P, [f())) Then from Assumption 3c and Lemma D. we know that 2() is strongly convex with constant coefficient. Note that by triangular inequality, we have
(gl[)))) (a(alp) (2() c(t") [ā(+) 2(0) + -2(t) [(t")) A1 A2.
We proceed bound A1 and A2.
Bound on A1: Recall that Σ(-) is strongly convex. Consequently, have
A E ||e - -i2..P)) S 2o log? 7/2 n.
with probability at least - exp( (22+d) log" n), where the last inequality comes from Bound A2: Note that both the functions t" (-) and (t) bounded, then by Hoeffding's inequality, we obtain that
P(A2 S 2912 log
n 7/2 2 cxp(-n(d-220) (1-22222)//228-0 log n).
Therefore, by combining the above two bounds, we obtain that
DD(alp)) - (y(alp)) S n ze-d log 7/2 228((2 (d122mm2)2222200--0000000-- log 1 n). This concludes the proof of the theorem.
with probability at least 1 - expp (d
B.4 PROOF OF THEOREM
We first need to bound the max deviation of the estimated f-divergence Dy (glll))) among all E Q. The following lemma provides such bound. Lemma B.1. Under the assumptions stated in Theorem S for any fixed density p. if the sample size n is sufficiently large, it holds that
28 sup Dy(glpp (y(ll))) & log' n QEQ
with probability at least 1/n.
We defer the proof Section
Now we turn to the proof of the theorem. We denote by q" = argmingeo Dy(āllp), then with probability at least 1 - 1/n, we have
D (ālp) < (Tlp)))) Dy(Tl)) (ālp)
28 s sup Dy((llp) Dy(alp)) Dy(7'll)) S za+a llog D2 (p). q=
(B.3)
Here in the second line we use the optimality of q among all q while the last inequality uses Lemma B.l and Theorem g Moreover, note that D lIp) mingeo Dy(7lp) combining B.3), holds that with probability at least - 1/n,
the problem (5.2).
( $ auta log" n + min Dy (Tlp).
geQ
This concludes the proof of the theorem.
B.5 PROOF OF THEOREM A
For any real-valued function o. we write Er(e) = Ex-r(e(=)) Eo(e) = Ez-ole(x)) Er, (e) =
Eg-P, [e(x:), and EG.. (e) Eznq, [e(x)) for notational convenience.
For any 7 PM s). establish the following lemma.
16

---

Under review as a conference paper at ICLR 2020
Lemma B.2. Under the assumptions stated in Theorem A. it holds that
1/(LL)) || [1--812.c8 El2,.0) - 1/po 1 -11220 - ||| (2)))) + [Ee.. 1(T-
[f 8) (t] EII (tI)
Here μl and Lo are specified in Assumption 3.4
We defer the proof to Section
Note that by Lemma B and the fact that ft is Lipschitz continuous, we have
|| - 21 S || il 1/
1- (2.(e)) + (Ee., -t Rol f)/2 + -
[Bee
- ((])-
(B.4)
Furthermore, to bound the RHS of the above inequality, we establish the following lemma.
Lemma B.3. We assume that the function &i R + R is Lipschitz continuous and bounded such that [x)) I Mo for any |a| I M. Then under the assumptions stated in Theorem A. for any fixed (x)) E M. n Z ly + y log(1/e)) and < & < 1, we have the follows
[Ep, [bb(t) (5 R (b(()) - -()] S 16M0 2 1 - exp(
P sup (T. (n, x) =)- (t) (t)ll,, 7,),
where 7,6) n 1/211/11 log +
log(1/e)), X(n, logg++-llog((//
n +og2+ and for any real
numbers C and Cg. denote by e Vc2 max
fci o2). Here y takes the form y s1/2 log(V
where 1 + (k: 1).
We defer the proof to Section
Note that the results in Lemma k* also apply to the distribution Q, and by using the fact that the true density ratio 0* pz
g(z)/p(z) is bounded below and above, know that (Q)) is indeed equivalent to (IP). We thus focus on (2P)) here. By (B.2D, Lemma B.3. and the Lipschitz property of ft according Lemma D.d. with probability least 1 exp(-?2). have the following bound
2 - -ll $ ||ē 8 (1))))) || - (1
+ +Onn-1/211 log + 7 log(1/=)] -1--71122()) "
(B.5)
where recall that the notation s// log(V²2) is parameter related with the family of neural networks + a. We proceed to analyze the dominant part on the RHS of (BB.5).
Case 1. the term
[8- 1 (12))))) dominates, then with probability least 1 -x-xxp--xppp- 17 il (.
Case 2. If the term Onn
1/2 log (1/c)] (f (p))) dominates, then with probability at least 1 - exppexxp 2-
[ - - Fll S n- 1/21/2 + +
log(1/=)) -o
Case 3. If the term (12 log(1/e))) dominates, then with probability least 1 exx((_x7]
- S 112(( Vlo((1/e)).
Therefore, by combining the above three cases, we have
11E- - & 1IF--t"lraa (P)) + + 1/2 log n + n 1/2
112 /log(1/E) + + - log(1/])]-
Further the triangular inequality gives us
- $ l - t" t'll + yn
1/2 logn + /o/gl///////
with probability at least 1 - E exp(_>?). Note that the above error bound holds for any 7 E @ ar( [L, kt s), especially for the choice such that minimizes I|ē - t" (1 Therefore, we have n 1/2 min ||t t']ll2(P)) + 7 1 ( /log(1/=) + + -o [ - ('11 (L,kr)
with probability at least exxp(-72) This concludes the proof of the theorem.
17

---

Under review as a conference paper at ICLR 2020
B.6 PROOF OF THEOREM
We follow the proof in Li et all (2018). We denote by the loss function in as [[(()]
(1((()))) ((="), where xt follows the distribution and xt follows Q To prove the theorem, we first link the generalization error in our theorem to the empirical Rademacher complexity (ERC).
Given the data {aa)==1> the ERC related with the class ((Por)) defined as
Ri [ porm))))))))) )] = E sup
Σ E, WW
(B.6)
where ey's are i.idd Rademacher random variables, i.c., P( = =) P(e, -1) 1/2. Here the expectation (-) is taken over the Rademacher random variables HEs))))))
We introduce the following Lemma tion eπrоr bound.
B4
(Mohri al 2013). which links the ERC to the generaliza-
Lemma B.4. Assume that sup pEP 1 E, have
[c(E) < Mi, then for any E > 0, with probability at least
Ex (LlClp(z;W, - Σ Clplan [lo(anWWel]] S Rn M1 n 1/2 -1/2 11//2//oog //lo((//5))
sup 4
where the expectation Eg {-} is taken over x! ~ P and x=" ~ Q
Equipped with the above lemma, we only need to bound the ERC defined in (B.6)) Lemma B.S. Let L be Lipschitz continuous loss function and & Pnomm be the family of networks
defined in (A We assume that the input æ E I2 is bounded such that ||ж||e S B. Then holds that
R2 [C( pmmm))mmm S n n 1/2 log(12n),
where and 7/2 are given in
We defer the proof Section
Now we proceed to prove the theorem. Recall that we assume that t E Pnom- For notational convenience, we denote by
(T()) EgsP, - Be-g,
H(t) Ex-r(f Enw [tx)).
Then [t) (t). We proceed to bound [īy(all)) D = (t) H(t))] Note that if
( 2 H("",, then have
0 H())) H('),
(B.7)
where the second inequality follows from the fact that is the minimizer of ((). On the other hand, if (f) < H(t)), we have
0 - H( 7 ((). -
(B.8)
where the second inequality follows that fact that is the minimizer of H(-). Therefore, by (B (B.8), and the fact that C(p) x II B, for any E T @norm we deduce that
H - H(+)] < sup [Ā()) H() & R. ((( + II B, nn BLgL1////
(B.9)
with probability at least 1 1 s. Here the second inequality follows from Lemma 34 By plugging
the result from Lemma B3.l into (B.H), we deduce that with probability at least s, it holds that
L+1
Py(al))) -Dylall)
i H(!)( n log(72n)
II 1=1
By n 1/2 Vlo((1/s).
This concludes the proof of the theorem.
18

---

Under review as a conference paper at ICLR 2020
B.7 PROOF OF THEOREM A
We first need to bound the max deviation of the estimated f-divergence Dy(lllv) among all 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 (6 2). Then for any target distribution p, have
max Dy(glp)) (gl(l))) & (2 m. 72) + II 4E
B, n 1/2 Vlog(Nalba(n, n, 72), 2
5=1
with probability at least 1 - E. Here by (n, 71: = 71 1/2 log(?2n) and c is a positive absolute constant.
We defer the proof Section
Now we turn to the proof of the theorem. We denote by q" = argminge Dy(īlp). Then with probability least 1 E, we have
(@lp) = (Tl()) Dy(ālp) + (Tlp))
< max DD((llp) - Dy(alle) Dy(7'lp)
1-1
Sb,,n,,1,,2) 12) + II Bj n 1/2 5=1
(1) Dy(T'lp),
where the optimality of 9 among all Q the problem (6:2) in the second inequal- ity, and we uses Lemma BTR and Theorem 2 in the last line. Moreover, note that (y mingeg ( lp), obtain that
(l(l ba + II By.n'" 1/22 1/2
72), 2//e) min Dy (7lp))
gEQ
This concludes the proof of the theorem.
C LEMMAS AND PROOFS
C.1 PROOF LEMMA
Recall that the covering number of Q is N2 Q), thus assume that there exists
41...., (N2(6.2) E Q such that for any g E Q, there exists some lk. where < k < (2
so that |19 9xl12 I 5. Moreover, by taking 5 8, 23/(2(4)) and union bound, we have
P/sup ()((l))--/ppppppp)p Q
- (g(ll)))) 2 c
log' 7 n]
Na(5.. 2)
Σ
20 log" n) PiDy(gall)) (y [p)) 2 c1 nn
< N2(5n, Q expp exp(-n -o 2044 log (gg44)) n):
d-23
where the last line comes from Theorem Combining Assumption 5 when n is sufficiently large, it holds that
P(sup Dy(glpp) - 2 c1 2542 log" n] 1/n,
QEQ
which concludes the proof of the lemma.
19

---

Under review as a conference paper at ICLR 2020
C.2 PROOF OF LEMMA
For any real-valued function g, we write Ep(e) - E>-r(e(>)), Be(e) - Exmele(x)) Bp,(e)
(er=,,,,(()) and E,, (0) Ez [e(x)) for notational convenience.
By the definition of f in have
Ex, [0] Ee. ( S Ep, [f) Ec., (t).
Note that the functional G(t) Ep, [f (t) Ba. (t) is convex in since fl is convex, then have
G( G(i) G(()
i +
G(T
2 S 0.
By re-arranging terms, we have
[Er,,
Ep ((+())))))) (0) {Eg, 10 7)/2] - Eel(T- - -
$ <Eolf - -f)(f=t)/2]- Belf (f))))
(C.1)
We denote by
By([,t) = /Eel (t) B (t -)..
(C.2)
then the RHS of (CII) is exactly - (f) We proceed to establish the lower bound of By t) using L2(P) norm. From (x: p. = f((((=)/p(z)) and (f (f)) = z, we know that q/p = (t*(()) //t. Then by substituting the second term on the RHS of using the above relationship, we have
(t = Eg
0ft (t()) - (+()
(t) (0)(( (t (t-
0t
= EB (
0ft
Ot ( (t (t- 1)
+ Ep
08tt
11 (
aft
(t)
(t (t- 8
Ot
Ot
= A1 + A2-
(C.3)
We lower bound A₁ and Ag in the sequel.
Bound on Ai. Note that by Assumption 3.4 and Lemma D.f. know that the Fenchel duality ft strongly convex with parameter 1/Lo. This gives that
(t(x)) - (f(x)) - ost
Ōt ((x)) [t(x) - [(x)) 2 1/Lo - (t(z) - =(x))²
for any Consequently, it holds that
1 2 1/Lo - ? (
(C.4)
Bound on Ag. By Cauchy- inequality, holds that
0st
0ft ot
(t+) "
A2
E3
VEel(t - 7)2].
0t
Again, by Assumption B44 and Lemma D.A. we know that the Fenchel duality ftt has 1/ps-Lipschtzz gradient, which gives that
0st
Ost
0t (T(x))
(((=)) 1/p0 [T(x) - 1" (xx)
at
for any x. By this, the term A₂ is lower bounded:
A₂ 2 -1/Po ||ō t' -11 (8
(C.5)
Plugging (Cd) and into (MG)) we have
(t, 2 L/Lo ||t ( - 1/40 -| - ('1 111-81
By this, together with (C.I), we conclude that
1/(4T)) || 7IL_(P) 1/po 11 Tlle,T) 110 1" (12,(1) (Bc. (
L, ( - (0) - (e) - ft()].
This concludes the proof of the lemma.
20

---

Under review as a conference paper at ICLR 2020
C.3 PROOF OF LEMMA
For any real-valued function g, we write Ep(e) - E>-rle(x)), Be(e) - Ex-ele(x)] Er, (e)
E,-,,, [e(x)), and E,, (e) Ez-q, [e(x)) for notational convenience.
We first introduce the following concepts. For any > 0, the Bernstein difference (1 of i(-) with respect to the distribution is defined to be
pk. 2K² Ee(exp((tI/K) - 1t
Correspondingly, we denote by HK, B the generalized entropy with bracketing induced by the Bern- stein difference PK.F. We denote by H, the entropy with bracketing induced by L. norm, H, the entropy induced by L, norm, H (P).B the entropy with bracketing induced by (IP) norm, and (P) the regular entropy induced by (IP) norm.
Since we focus on fixed L, k, and s, we denote by PM L s) for notational convenience. We consider the space
V = \
(v(t) : t(xx PMr).
For any 8 >> O, we denote the following space
V M (6) = (v((1) MM (1bb(1) - (00l)2))))) S 5.]
(6) (Av(t)= (tt) (tt) (t)) [M(()}.
Note that supav(())w1,()) ( I 2Mo and supAN(DEW", (Av()) I 8, by Lemma D we have
P&M. P.M.PIAA((t))) S 22..
sup A0(1)"1,
To invoke Theorem D for G (d), we pick K 8M4 and R V25. Note that from the fact that Lipschitz continuous, we have
[+)ll I 2Mo by Lemma D.I. Lemma D221 and the fact that tb is
HsM.,B(u. V (D), S (2) (0)( 2(s + 1) loggoog(22))) (L 1))3
for any u > 0. Then, by algebra, we have the follows
L
R
H BM (u, (O), du S 33 1og(8V
For any 0 & < 1, we take C = 1, and a, C1 and Co in Theorem D33 to be
a 8.M log(cxp(72)//))>>
Co 6.o Vlo''VVoogeiiiiooo (og()))((?))/))
C1 33M3 log(exp(7?
Here > 54/2 L).. Then straightforward to check that our choice above satisfies the conditions in Theorem D for any such that 5 2 yn -1/2 when n is sufficiently large such that n h + 7 + (og( | Consequently, by Theorem D... for 8 2 yn 1n21/2 we have
P( sup (6)
E>, (t) - (f) - (t) & 2ill 2 8M, log(exp(??)/e)) .. -1/23
= =P( sup A
Er, (A) - EM(A(()] 2 8M, 1og(exp(722)//))) . 5.n 1/23
E Se-expo (e-exp(-77]
By taking 8 5, -yn
1/2 112
have
EE,, [t)(t v0) Ep (t) ((]l
P sup (()
s &Mo 21 21-2 expe-xx((-7" (C.6)
n- [ + log (/E)]
21

---

Under review as a conference paper at ICLR 2020
On the other hand, denote that S minfs 1 2:22)( < 6,} O0log((011))))) notational convenience, we denote the set
'n /2). For
A, = (t)(t) e MM (t) E Vas 22 Mo), v (2
(C.7)
Then by the peeling device, have the following
Er, (t) (0) (x(((t) -b)li
2 16M0 }
sup
V (0)) (6..)
(|x(t) + (1)))) T,E,
Be (v)) [[] Eplyb(1) -v(0i
2 16M0 T(m
sup (()EA
2-++1
8
P( sup (())E,
Er (+(1) v00 - (x((((1) -001 2 8Mo -2 (T(n,
8
P(
sup (()) (2- Mo)
IE (1(( x0)) - Ex(v(() +00l > 8Mo (2 (2-+t2Mo) T(n,7,)))
SS- E exp(->²) /log?? log(>~1 'n (2) C. exp(->2),
where e is positive absolute constant, and for notational convenience we denote by T(n, 7,E) y= n-1 log(lo((>="')) 1/3 exp(>>)/e) Here in the second line, use the fact that for any (t) A., we have ||x(()) - (t) (2) > 2 s+1 Mo by the definition of A, in (CM)); in the forth line, we use the argument that since A, S M (2- 2M)
Mo). the probability of supremum taken over V *r (2 (2- Mo) is larger than the one over A.; in the last line we invoke Theorem D Consequently,
this gives
[1)(t) (1)lz((()) n- n-1/2(7 log n + - (1g(1/E)] I 16M0 } 2 1 - - exp(->²))
EE (t) (t) - Ep (t) e0)I
P
sup S(0EVM v6
(C.8)
Combining
(C.)) and (.S), we finish the proof of the lemma.
C.4 PROOF OF LEMMA B
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) E T norm and I1, D2 E Rdd, we have
L+1
(15( W,v) (0 W. v)12 S ||
x2ll2 II B3. 5=1
We defer the proof to Section oGi
The following lemma characterizes the Lipschitz property of p0z; v) in the network parameter pair (W, v).
Lemma C.2. Given any bounded x E Rd such that |||||2 S B, then for any weights (W3) pl. W ..), W2, (22,22) E Paomm we have
W = f=l 2
(u))f (uf)f and functions
11 W1, 10²) - (xx (V2,0²)
B BV2L +1 11, L+1 B₁
L+1
-
Σ Aj
[ - W31R + Σ 10g - 3313.
ming Bj
1=1
==1
1=1
We defer the proof Section tv
22

---

Under review as a conference paper at ICLR 2020
We now turn to the proof of Lemma L Lipschitt in the parameter (W,v) v)
Note that by Lemma CM we know that co(x; W. is E R. where the dimension takes the form
B
L+1
L+1
Kink
(ky + 1)?
(C.9)
==1
1=0
and the Lipschitz constant Tie satisfies
L
BV2L +
j=1
L+1
Bj
Σ Aj-
(C.10)
miny Bj
j=1
In addition, know that the covering number of W {(W,o) R EE WWyle
Σj=1 |lylle S KJ. where
K
B3
Σ Aji
(C.11)
satisfies
N(W,8) S (3K8-1))
By the above facts, we deduce that the covering number of [(P satisfies
N 4 mam))) 6] < (c) KirKLa 6
for some positive absolute constant C1. Then by Dudley entropy integral bound the ERC, know that
Vn [- Vlog log N norm), 8] dó,
1
Rr (C norm))oml))) S inf +
(C.12)
+20
where 0 s W 2zcd) (1(:; W, e)].
Moreover, from Lemma Cill and the fact that the
loss function is Lipschitz continuous, we have
0 B
II B
(C.13)
for some positive absolute constant C2. Therefore, by calculations, we derive from (M that
R, [C (CC()))))) )] =0 (0 b- log
y
KLwyn Ovb
then we conclude the proof of the lemma by plugging in the definition of 71 and 7/2 in 4
and and using
C.5 PROOF OF LEMMA
BIG
Remember that the covering number of Q is N2 2), we assume that there exists 41.... (N2(6.2) E Q such that for any g Q, there exists some yk, where 1 S k s N2(6, Q). so that l|q gull2 < 8. Moreover, by taking 8 ni 7 log(72n) b2(n, 71, 72) and N₂ = (2 71, 72), Q). we have
L+1
Pmmax (D((llp) Dy((le) e (22 m, 12) + II QEQ
By 1/2
(log(N2/e))
j=1
L+1
P(IDy(glp)) By(gl1)) 2 (b2(n,7,77)) )
II Bj 11/
1/2
Vlo((N/88)
N2 e/N2 =,
where the second line comes from union bound, and the last line comes from Theorem A By this, conclude the proof of the lemma.
23

---

Under review as a conference paper at ICLR 2020
C.6 PROOF OF LEMMA
OR
The proof follows by applying the Lipschitz property and bounded spectral norm of W, recursively:
|, W,v) (a2;; W, 2)]l2 [|W++1(0rz W20,, WiT1 Ouz ... W20,, Wiz2)lla
v (WL- ... W20., W121 - W, ... (1a2)ll
$ BL++ |WL W20., W1x1 WL W20 Wia2|12
L+1
$ II By
21 22ll2.
Here in the third line we the fact that ||W B, and the 1-Lipschitz property of ouy (.),)), and in the last line we recursively apply the same argument as in the above lines. This concludes the proof of the lemma.
C.7 PROOF OF LEMMA
Recall that (o;; W; v) takes the form
p(;; w) = WL+10 WL ... de, Wix.
For notational convenience, we denote by (x) = of (Wjx) for i 1, 2. By this, yfa; W; has the form ş(æ; W v²) W Witi o... of (x)). First, note that for any W1, W v2 and v², by triangular inequality, we have
(,x, W x²) pæz, W x²) || [|
vf(x)) W W2+1 (x(x)
$ [ [W7+1pt, 11). .... (x) W7 o.... o
+ || o o 0/) (20))-W21120
W2+1 o.......... o p1(1)112
< h+1
W 1I |l. 1,01 c pf
+ +B++ |111
(i()) v o. ..... (1(1)]12
(C.14)
Moreover, note that for any é [L]. we have the following bound on |1 .... (
11 o . pf S 1 o..... . I|vill
Br 1h-1lpp-11 1oplllppoo.... ..... o (x)]l2 + A
||l|| II E B
(C.15)
1=++1
where the first inequality comes from the triangle inequality, and the second inequality comes from bounded spectral norm W while the last inequality simply applies the previous arguments recursively. Therefore, combining (CT 4), we have
L
L
L
[| w',"') - (1x, W 02) S
B
I
B
+
1I
B,
1+1 - W2
j=1
j=1
i=j+1
+ B1.1 11 o... pp - o o.... (f(()]12
(C.16)
Similarly, by triangular inequality, we have
1442 o.. .... .........0.... of(xx) - vř . of
< 111 o ....
o (((x) - o o
+ +1p2 o -000 o...o o
< o... pl. p())l22
(C.17)
..... + 11/ o... .... pi_, . {
24

---

Under review as a conference paper at ICLR 2020
where the second inequality uses the bounded spectral norm of Wz and 1-Lipschitz property of Ter, (.). For notational convenience, we further denote = P o o up (a)) then
(v) (1)ll llo w1) (W2y - }12
< <1 oř.1 2 || W ||
where the inequality comes from the 1-L.ipschizz property of a.)). Moreover, combining (C.L5) it holds that
L-1 (1) 22 & l0t - villz 1 - W2llF (B B By
Σ A3 II B;
(C.18)
1=1
E=+1
By (C.T7) and
we have
11 o.... (x) o...
$ 1101 - v2212 l2 I| - w21lr B I +
B,
i=+1
+ Br 11911111111//_ 0... (x()) - 0... of
L
B II 1=1 Bj
Σ II
B 10,1 - -1ill +
W
W3llF
min, Bj
J=1 i=j+1
==1
j=l
B
11 L+1 Bj
1
Σ
Σ
(1
3l [[ - Wflle).
miny Bj
j=1
j=1
Here in the second inequality we recursively apply the previous arguments. Further combining (CTG), we obtain that
11 W 0²) (2x W 22)22
B
L+1 1=1 Bj
1.+1
Σ Aj
[
WfllF
+
100
rÿll2
min Bj
j=1
1V22+1.10 11 j= B
L+1
Aj
Σ
Will
Σ
10
miny B₁
where we use Cauchy-Schwarz inequality in the last line. This concludes the proof of the lemma.
D AUXILIARY RESULTS
Lemma D.1. The following statements for entropy hold.
1. Suppose that supyeg al S M, then
HAM,n((22,90 < (2,
for any 5 > O.
2. For 1 S q co, and Q distribution, we have
H Q, < Hzx
for any 8 O. Here Ho the entropy induced by infinity norm.
3. Based on the above two statements, suppose that sup, geg ll S M, we have
HAM.n(VV-6.G.0 )) S Hoe (8/2,9),
by taking p 2.
25

---

Under review as a conference paper at ICLR 2020
Proof. See van de Geer & van de Geei (2000) for a detailed proof.
Lemma D.2. The entropy of the neural network set defined in (A. satisfies
H PM (L, p. s)] & (s + 1) log 26 ( 1)V²),
where V = -I (pr +
Proof. See Schmid (2017) for detailed proof.
Theorem D.3. Assume that supgeg Pk(g) < R. Take a, C. Co. and Ci satisfying that S
C1 CivnR /K, I 8VRR, 2 Co [10 that
1/2 HR,B(u, (K. Pddu V R). and C 2 (2 + 1). It holds
a²
P(sup Ep, (g) Er(g)) 2 a. n 1/2 Cexp Cc(CI++1)
gEg
Proof. See van Geer & van de Geen (2000) for a detailed proof.
Lemma D.4. Suppose that lg lo I K, and Igll| s R. then p2k.((9) 2R?. Morcover, for any K' K, we have P2 s 2R²
Proof. See van de Geer & van de Geen (2000) for a detailed proof.
Theorem D.S. For any function f in the Hölder ball C ((0, 1j4, K) and any integers m and N 2 114 (K + 1), there exists network / LLL, (d, 12dN, 12dN, 1), 8) with number of layers L 8 + (m + 51 + [log, d)) and number of parameters S 94d + 1)2d Nma 6) + [log2 d]), such that
I - 11- & (2K + 1)34+122- + N-8//
Proof. See Schmidt-Hrebei (2017) for detailed proof.
Lemma D.6. If the function f is strongly convex with parameter po 0 and has Lipschitz continu- ous gradient with parameter Lo > 0, then the Fenchel duality f f is 1/ stroslyyy convex and has 1/poo-Lipschine continuous gradient (therefore, ft itself is Lipschitz continuous).
Proof. See Zhou (20)) for detailed proof.
26


Reviews:
[{"review_id": "Skgt6nCCKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- Summary\n\nThis 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.\n\n- Critics\n\nThe paper is globally well written but not well motivated and sometimes difficult to understand.\nIn particular, the notions of \"elicitation\", \"reports\" and \"score function\" should be defined mathematically more clearly.\nMoreover, the deep learning aspect of the paper is not well motivated and is introduced in a very arbitrary way. Why not choosing another parametric family of functions? Is there another (broad) family of functions for which the computation of the argmin in Equation (4.3) is more tractable in practice?\nA convincing way to motivate this deep learning approach would be to include numerical experiments and to compare to other parametric families.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeHgYNhtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n- In (C.15) in Section C.7, why the upper bound is irrelevant to y or W_L^1 or W_L^2? Since we do not have W_L^1 = W_L^2, how to derive the inequality in (C.15)?\n\n- In the proof of Lemma B.2 in Section B.5, why 1/(4L_0) and (1/\\mu_0) are simply removed in the inequality below? \n\n- The inequalities in the proof of Theorem 3.5 in Section B.1 should be further explained. What is the meaning of “agent believes p = q” and how to apply this to the lower bound? What is the meaning of \\bar{S} and how to get these inequalities for the upper bound?\n\nSome minor comments\n- The relation of x’ and x in the first paragraph on page 2 should be further clarified, and some formal definition should be given. The readers who are not familiar with this area would be confused about the problem before reading Section 2.1.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The primary contribution of this manuscript is a conceptual and theoretical solution to the sample elicitation problem, where agents are asked to report samples. The procedure is implemented using score functions to evaluate the quality of the samples.

The reviewers and AC agree that the problem studied is timely and interesting, as there is limited work on credible sample elicitation in the literature. However, the reviewers were unconvinced about the motivation of the work, and the clarity of the conceptual results. There is also a lack of empirical evaluation. IN the opinion of the AC, this manuscript, while interesting, can be improved by significant revision for clarity and context, and revisions should ideally include some empirical evaluation.
Decision: Reject