Learning Exponential Families from Truncated Samples
Authors: Jane Lee
Andre Wibisono
Manolis Zampetakis
Venue: NeurIPS 2023 poster (2023)
Keywords: truncated statistics
robustness
exponential families
extrapolation
TL;DR: We provide the first efficient algorithm for estimating parameters of general exponential families in high dimensions using samples truncated to very general sets.

Abstract: Missing data problems have many manifestations across many scientific fields. A fundamental type of missing data problem arises when samples are \textit{truncated}, i.e., samples that lie in a subset of the support are not observed. Statistical estimation from truncated samples is a classical problem in statistics which dates back to Galton, Pearson, and Fisher. A recent line of work provides the first efficient estimation algorithms for the parameters of a Gaussian distribution and for linear regression with Gaussian noise.

In this paper we generalize these results to log-concave exponential families. We provide an estimation algorithm that shows that \textit{extrapolation} is possible for a much larger class of distributions while it maintains a polynomial sample and time complexity on average. Our algorithm is based on Projected Stochastic Gradient Descent and is not only applicable in a more general setting but is also simpler and more efficient than recent algorithms. Our work also has interesting implications for learning general log-concave distributions and sampling given only access to truncated data.

Learning Exponential Families from Truncated Samples
Jane H. Lee
Andre Wibisono
Department of Computer Science Yale University jane lee@yale. edu
Department of Computer Science
Yale University
andre wi wibisono@yale.eet edu
Manolis Zampetakis
Department of Computer Science
Yale University
rmmanouil.zampettatee .ddu
Abstract
Missing data problems have many manifestations across many scientific fields. A fundamental type of missing data problem arises when samples are truncated, i.c., samples that lie in a subset of the support are not observed. Statistical estimation from truncated samples is classical problem in statistics which dates back to Galton, Pearson, and Fisher. recent line of work provides the first efficient estimation algorithms for the parameters of Gaussian distribution []O] and for linear regression with Gaussian noise
In this paper we generalize these results to log-concave exponential families. We provide estimation algorithm that shows that extrapolation is possible for much larger class of distributions while it maintains a polynomial sample and time complexity on average. Our algorithm is based Projected Stochastic Gradient Descent and is not only applicable in a more general setting but is also simpler than the recent algorithms of [10 26 14 37). Our work also has interesting implications for learning general log-concave distributions and sampling given only access to truncated data.
Introduction
In many statistical estimation and inference problems, have access only limited part of the data that would be necessary for the classical statistical methods to work, which motivates the development of statistical methods that are resilient missing data [29]. Truncation [32 g is fundamental and
frequent type of missing data and arises when samples that lie outside a subset the support are not observed and their count also not observed. Statistical estimation from truncated samples the focus of the field of truncated statistics, which was developed since the beginning of the twentieth century starting with the work of Galton [9]] Pearson and Lee 34 35), and Fisher [16]. Truncated statistics is widely applicable in Econometrics and many other theoretical and applied fields (32
A recent line of work establishes the first sample optimal and computationally efficient methods for fundamental statistical estimation problems from truncated samples [10] 26 [1 [4] 24
(37]. All the aforementioned works though heavily rely the Gaussianity of the distribution of data the Gaussianity of the noise in regression problems. Gaussianity is an idealized assumption and the question of generalizing truncated statistics beyond Gaussianity has been explored in many existing works, e.g., [ 122 38). The only results in this regime though are for single dimensional problems and truncations that can be deseribed as intervals.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

0.10
0.08
2.00
0.04
150
0.02
125
100
0.50
2.5
2.0
X2
0.5
0.5 1.0
0.00
0.00
Figure I: Visualizing the density and truncation set for 2-dimensional exponential distribution. The plot on the left is the density of p(21, x exp(- =- $2 ). On the right is contour plot of the truncation set [0, 2] x [0, 2] under p(æ); 22). Note that E[Xi] ] and IE[ [x2] 2, so the truncation set excludes the mean in one direction and includes it only as boundary point in the other.
In this work we provide statistically and computationally efficient methods for estimating the param- eters of exponential families from truncated samples. Our results generalize the recent work of [TO] and are the first to provide an estimation algorithm for this problem for general class of exponential families and for general class of truncation biases.
Exponential families are one of the most influential type of distribution classes since they include many fundamental distributions such normal, exponential, beta, gamma, chi- chi-squared, and Weibull distributions. They were first introduced by Fisher [17] and later generalized by 9 27 (3).. The estimation of the parameters of exponential families over continuous domains the subject of many classical and recent results; starting from the work of Fisher [17] until the recent results of [25] 41 This line of work has also found applications in many
of statistics including causal inference Our work contributes in this line of research well since we show how to estimate exponential families even when we only have access truncated samples.
40
1.1 Our Results
For every distribution p. we define the truncated version p as the distribution with density that satisfies pd (x) 1(x S) -xx) We consider distributions po with support X C R parameterized by vector of parameters 0 E I that can be written in the following form:
(e(x) x h(x) exp TOTTTTTXX T(x))
where h and 7 are known functions and T is called the sufficient statistics the exponential family. Our goal is estimate the vector of parameters 0 up error la distance using only samples from P when we have oracle access to S, i.e., there is an oracle that for every x E X' can answer not.
whether
Without any further assumptions estimation from truncated samples is impossible as shown In this paper use the following assumptions to get our estimation guarantees:
10
Assumption I:
We assume a lower bound and an upper bound on the variance of the sufficient statistics in any direction. This assumption is used in estimation of the parameters of exponential families even without truncated samples, e.g., Assumption 4.1 (4T.
Assumption II:
We assume that the exponential families contain log- log-concave distributions. We use this assumption in two places: (1) to show our extrapolation result, our distributions must satisfy anti-concentration property; this is property that is heavily utilized even in estimating a Gaussian distribution [T0), (2) we require access to a sampling oracle for the underlying distributions; this sampling oracle can be implemented efficiently using Langevin dynamics if we have cog-cincavity.
Assumption III: We assume that the sufficient statistics 7 are bounded degree polynomials. This assumption combined with log-concyvity provides the anti-concentration property that

---

Another interesting corollary of our result that we can combine it with the ideas of [1] and get a general method for learning log-concave distributions from truncated samples. In particular, assume that we want to learn from truncated samples a distribution that can be written in the form p(x) exp(-f(x)) where f is convex function. Now under mild assumptions, we can replace f(x) with a finite Taylor approximation, i.c., we have that estimate need. Alternativll,, we can assume that the sufficient statistics belongs to a function class that satisfies unti-concentration but for simplicity of exposition we focus on the case where 7 7(x) is polynomial.
Our main result is the following.
Informal Theorem 1.1 (See Theorem 3.1 for the formal statement). Under Assumptions I, II, III, and given samples n (at least (k)e²) for some c) from p where S measurable set which we have oracle access, there exists estimation algorithm with (expected) running time poly k. n) that outputs 0 such that with probability at least 99%, it holds that 100 0" <.
Our main result has the following important implications:
We show that our assumptions are satisfied from exponential distributions, Weibull distribu- tions, continuous Bernoulli, continuous Poisson, Gaussian distributions, and generalized linear models. Hence, our result implies an efficient method for estimation from truncated samples for all these distribution classes.
f(x) 2 axt,(x) for some polynomials t, (x). Then, using our method the parameters a, and output an estimation of p.
In the context of sampling, the gradient of the log-likelihood is the score function that is needed to run Langevin dynamics (e.g., see 30 7). Our result also says that we are able to sample from the original distribution, given that only observe truncated samples.
Technical Contributions. Our algorithm is projected stochastic gradient descent (PSGD) on the negative log-likelihood function and is the same algorithm that is used in many of the recent works truncated statistics. As in the previous work though, the main challenge is to show that PSGD will converge in our general setting. The previous analysis of the convergence of PSGD was based on exact properties of the Gaussian distribution. When we move away from Gaussianity every step of the convergence analysis becomes much more technical and we need to make sure to only use properties that generalize to exponential families beyond Gaussian distributions. In particular, certain results such as that of Lemma 3.6 and its related quantities in C.I can be generalized even beyond exponential families, holding for any density.
1.2
Related Work
Our most related literature is the recent series of works on truncated statistics which includes the following results: estimation of multivariate normal distributions [TO), linear regression with
Gaussian noise [10 [T] [4 37]. estimation of product distributions over the hypercube [18), non-parametric density estimation [1]. All of these works heavily rely on properties of the Gaussian distributions, or product distributions over the hypercube, or their dependence in the number of dimensions is not efficient, e.g.. [12]. our work we identify the properties of exponential families that are only required to get the efficient estimation results and we show that linear dependence on the dimension achievable in settings that are more general than the Gaussian case.
Another related work is that of 30 that solves parameter estimation of a truncated density given samples through the score matching technique. To derive tractable objective, we need appropriate boundary conditions which are not satisfied by truncated densities, but (30 instead uses a modified weighted Fisher distance given that the truncation set S is a Lipschitz domain (a type of open and connected set). On the other hand, our work assumes no particular structure about S and hence our results are more general and applicable in much more complicated settings for exponential families.
2 Preliminaries
Notation. Lowercase bold letters will denote real-valued vectors, e.g., x E TRm and uppercase bold letters will denote matrices with real values, c.g., A ga For random vector ~ p.
3

---

is its covariance matrix, and Var(x) is the trace of the covariance matrix scalar value). Depending on whether it is clear from context, Cov and Var may include subscripts to indicate the distribution p. The notation B(c, R) is the Euclidean ball centered at e with radius R >
Covix] Covix,x] -
Exponential Families. form,
Letx X R We are interested in a class of densities which have the (x(x) = l((x) exp T'x(' - A(0)),
where h 1 HyR, R4 the base or carrier measure, E with {0 E R A(0)) < oo) the natural parameter space, T 1mmm + IR the sufficient statisfic for 0, and A(O) log Z(0) the log-partition function, where ( = (x(xxxx.
A regular exponential family is where @ is an open set. It is minimal if the 0 and T(x) are each linearly independent. Any non-minimal family can be made minimal by appropriate reparametrization. In any regular exponential family, A()) is convex. It is strictly convex if the representation is minimal. Exponential families have several nice properties (e.g., see Theorem of 4), among which are that (A(0) =
Ep. [T()) and (()) Cov pa [x))].
Truncated Distributions. Let p probability distribution on IR We represent p as a probability density function with respect the Lebesgue measure dx on RT. Let C Ih be such that p(S) for some a (0, 1]. Let n == pl. E 5) be the conditional distribution of x ~ P given that x E Concretely, the density of p² is
px(x) p(x) 1 S
p(S)
For exponential families, have the truncated density p (x) is:
(x) 1 E) Ig h(x) exp(@ T(x))
h(x) exp (0 T T(x))
(x) Is (x (x)
1(x E S}.
See Figure ! for an illustration.
Sub- Jub-Exponential Distributions. Although the term sub-exponential has been overloaded (c.g.. 21 v.s. the definition we will use describes a class of distributions whose tails decay at least as fast as an exponential, but with potentially heavier tails than Gaussians (4).
There several equivalent characterizations of sub-exponential random variables (e.g., see Prop. 2.7.1 of [44)), one of which uses the moment generating function.
Definition (Sub-exponential random variable). A centered, real-valued random variable X
SE () is sub-exponential with parameters 2² 2,3 > 0 if
E EleA S
AY: | 1/B.
Membership Oracle of a Set. Let S C RT. A membership oracle is an efficient procedure which computes 1(x E S}.
3 Projected Stochastic Gradient Descent Algorithm
Problem Setup. We are given truncated samples {x with each x; ph.. where Po- (S) > O. Without knowledge of the truncation set S beyond access to membership oracle, can one recover 0* and thus po- efficiently?
We answer this question positively, under the following assumptions: Assumption A1 (Strong Convexity, Smoothness of Non-truncated Negative Log-liikelhhod over +).
AI < Cov CoVz~ppll [(z), T(z) = LI 4O E θ
for some X, L > Here, we've abused notation rameter space. As mentioned earlier, this is always at least convex for exponential families and strictly convex in minimal representation. Thus the negative log-likelihood (of the non-truncated density) can be made strongly convex and smooth by restricting the natural parameter space appropriately.
which can a subset
entire natural pa-

---

Assumption A2 [Log-Concave Density), The density pe(x) is log-concave in x. Assumption A3 (Sufficient Statistics T(x) is polynomial in x). T(x) E R has components which polynomial in x, with degree most d.
Assumptions and A3 allow to use the anti-concentration result needed for Lemma 3.2 which is heavily utilized even in the Gaussian case. While A2 also allows for efficient sampling via Langevin dynamics, the latter is only used in Lemma 3.2 Refer back to [.I for discussion of these assumptions.
Main Result.
Theorem 3.1 (Main). Given membership oracle access a measurable set S whose measure is some constant a E (0, 1] under an unknown exponential family distribution pø which satisfies A1 A2
A3 and given samples X,,..., ,, from Po that truncated to this set, there exists expected polynomial-time algorithm that recovers an estimate 0. That is, for any > the algorithm
Uses expected Ō(k/c²) truncated samples and queries to the membership oracle,
Runs in expected (mly(m, k, 1/c) time.
Produces an estimate 0 such that with probability at least 99%,
0 0 <.
In order the solve this problem, we need to define an objective whose optimum is 0" and we need to be able recover it uniquely. To maximum likelihood estimation (or minimize the negative log-likelihood), we have to be able to compute gradients which depend on the truncation set S, which we cannot do directly without more knowledge about S. However, we can sample unbiased estimates of the gradient, as long we have non-trivial mass on S at a current parameter estimate (otherwise the truncated likelihood function at that parameter is not well-defined and rejection sampling would take infinite time). To address all of these issues, the organization of this section is as follows:
Section 3.] establishes that after truncation, the negative log-likelihood remains strongly convex and smooth (in 0) over a subset parameters which have non-trivial mass on the truncation set.
In Section
3.3 we show that while we do not know the truncation set, we can solve the non-truncated MLE problem with truncated samples to find an initial parameter Ou which assigns non-trivial mass to the truncation set.
Then given this 0g, in Section 3.2 we show that we can construct set of parameters K which all assign non-trivial mass to the truncation set (and contains the true parameter O*).
In Section 3.4 we use results from the previous sections to prove that we can efficiently recover the true parameter 0" using a stochastic gradient descent procedure minimizing the truncated negative log-likelihood, which projects to the parameter space K.
3.1 Strong Convexity and Smoothness of Truncated Negative Log--Likelihond
Without truncation, recovering the true parameter 0* for any parameterized distribution given samples classical problem solved by maximizing the likelihood (or minimizing its negation). Here, state the main objective we will minimize through a stochastic gradient descent procedure as well as the properties of this objective that will allow us recover 0". Define:
?(0) == E Ex-
[log (på (x))]
Vo((O) E Eg [T())] E Exxpg. [T())
Vge(0) Cov 2 [T(z), T())]
Note that since the Hessian covariance matrix which at least PSD, this objective is always convex in O. Thus 6" is minimizer since it satisfies the first-order optimality condition. (These caleulations can be found Appendix A.I However, if the objective is too flat, we may not be able to recover 0" even after sufficiently reducing the objective value. For this, we prove that if the original non-truncated covariance has bounded eigenvalues, the truncated one does as well under AT
A2 and A3 at parameters which assign non-trivial mass to S.
5

---

Lemma 3.2 (Preservation of Strong Convexity under Truncation). Assume the lower bound in Al
A2 A3
If po 0, then
(o((S
2d
Cov Coverieg 2ー (T(z).T(z) = 2 4Cd
XI,
where C' is universal constant guaranteed by Theorem 8 of [5] and d is the maximum degree of T(x). See proof in Appendix A.2 which follows that of [10].
Lemma 3.3 (Preservation of Smoothness under Truncation), Assume the upper bound in A1 Suppose
(S) 0, then
L1. Cov zov [T(), T()) LI.
(S)
See proof in Appendix A.3 The proof is simple and can be done similarly to the previous lemma.
Thus, we have shown that as long as we optimize over a parameter space where every 0 assigns non-trivial mass to the truncation set, our objective is both strongly convex and smooth. The following sections will help us determine and then construct this set given samples.
Remark. Note that the upper bound increased and the lower bound decreased for the eigenvalues of the truncated covariance matrix. Even in one-dimensional simple case like (O, 1), it is easy to construct examples of both increasing the shrinking the variance given freedom to place mass anywhere under .V (0. 1). Thus, it may be natural that the eigenvalue range expands after truncation. Remark. Lemma 3.2 and the ligelikeldhood caleulations the Gaussian case, where we can recover the results [10] by noting that the re-parameterization of Gaussian parameters (n. Σ) as V = Σ- ' and T = Σ is the natural parameterization of multivariate Gaussian distributions in exponential family form (up to constants). The sufficient statistics here Txx) x [x, xx" has components which are polynomial in x with degree at most 2, and plugging in d 2 Lemma 3.2 recovers Lemma 4 in 10] Appendix B includes other examples
direct generalizations of prior work in
beyond Gaussians which satisfy A1
A2 and A3
Parameter Space with Non-Trivial Mass on Truncation Set
The prior section established that the strong convexity and smoothness parameter of the truncated objective controlled by the mass that Po assigns to the truncation set for any given this section, we will prove lower bounds the mass that pa assigns to the truncation set, given that the parameter distance to the optimum ||0 0- is bounded.
Lemma 3.4 (Lower bound for mass truncation set under smoothness given parameter distance).
Assume A1
Let 0, 0' e. Then for two distributions from the same exponential family
3L Por (S)2 exp (- - 10 0¹13)
(o(S) 2 Por
Proof is provided in Appendix CK and only needs smoothness. Thus, we can lower bound the mass that a parameter @ assigns to given its distance | 0*1 from 0" which assumed have Po- (S)
Thus, make of this property want establish procedure initialize parameter Og such that its distance to the optimum 0* is bounded. Then during the optimization procedure we will make sure make progress toward 0* The following is the result will be able prove after proving some results between truncated and non-truncated quantities in the following Section (33
Corollary 3.5 (Parameter space with non-trivial mass on truncation set). Given O, such that Eop, [T()) = T where T Σ" T(x;) is the empirical mean sufficient statistics given samples [x for each x; ~ po- if we define
+ Olog 1/a) n n
K = B 0o.
X
then (o( 2 a² exp (- (es + Ollog 1 1/a))²) > 0 holds v0 E K (with probability at least 1
for n 2 (((log(1/))). Furthermore, 0* E K (as long as 0" E O satisfies conditions of Claim
This result will follow from Lemma 3.4 Claim
Lemma 3.7 and Lemma 3.9 in the next section.

---

3.3 Initialization with Empirical Samples and Non-truncated MLE
Given samples from the truneated density pa-. one may first try solve the non-truncated empirical MLE problem to find a parameter 9g without truncation and hope that it is good enough. (We will show that it is.) In order to understand how good this initial guess is, we need to establish some relationships between the truncated and non-truncated density.
Lemma 3.6 (Truncated vs. Non-truncated Mean Sufficient Statistics for General Densities). Let p be a probability distribution on Rd (not necessarily from exponential family). Let S C R2 with p(5) > 0. Then
1 1-p(S) V ((S) V Vxr,(x).
p x
Rx[xI| S
Proof of this lemma and several related quantities for general truncated densities is in Appendix C.I In low dimensions, this variance term may effectively be constant; however, in high-dimensional settings this term can grow with dimension (which undesirable if we want an efficient algorithm). Given more assumptions about the density, we can get better dimension-free bounds which generalize the results from the Gaussian case.
Claim 1. Let 0 O such that 0 + y θ for some B 0 for all unit vectors u and such that Assumption A1 holds for from an exponential family. Then X == u (T(x) - Ex- [x)]) is SE 3). (Proof provided Appendix C.2)
Remark. This claim allows us to have concentration of the empirical mean sufficient statistics to its population mean for the non-truncated distribution. The prior work [TO] analyzed the mean and covariance of Gaussian separately, but for instance to establish bounds on distances between the truncated and non-trun non-truncated mean parameter, made use of Gaussian concentration inequalities (which are tighter than uubeexponential ones). The relationship between the truncated density and the non truncraced one will allow us to say that the empirical truncated mean sufficient statistics is also somewhat close to the non-truncated population mean.
Lemma 3.7 (Concentration of Empirical vs. Non-truncated Mean Sufficient Statistics). Suppose 0r satisfies the conditions of Claim and pe- (S) a 0. Let T 1 - T(x;) be the empirical mean sufficient statistics given our samples {x, j= each x; po. Let cs > 0. For
n Ω 23 log (t)) with probability least 1 1,
T Eyo- [Tx))] S cs O(log//0)
It should be noted that it suffices to consider es as some independent constant (and not related to the accuracy parameter in the main theorem). However, by taking at least (k+/e?) (2) stated in the main theorem, this will be small. See proof in Appendix[C.4
Remark. At a high level, the truncated samples can be thought of as ((n/a) samples from the non-truncated distribution (keeping only those S), and each are "not too far" (depending how much mass the set S has under the non-truncated distribution) from the non-truncated mean due to concentration. Note that the (log 1/a) term will never disappear even as we increase n, which quantifies the inherent bias that the truncated mean sufficient statistics will have with respect to the non-truncated one (and is large if the mass a is small). From this, we can also say something about the population mean sufficient statistics, one on the truncated distribution and one on the non-truncated.
Corollary 3.8 (Truncated vs. Non-truncated Mean Sufficient Statistics). Let satisfy the conditions of Claim and (S)) >> 0. Then
| (T(x) - Ex-po [T())]] S O(lg (S)).
The proof follows from the preceding lemma, replacing a with (S) and taking n - co. Compare
this to the Gaussian case [10), where the mean and truncated means were bounded | Msl <
OVVlog 1Spe(S)) and separately the covariances were bounded as | 1/ 1/2
I| F <
(log 1 (S)) Note the smaller O (SP) quantity due to tighter Gaussian concentration vs. the sub-exponential rate.
Once we have bounds on the norm of the difference between the truncated and non-truncated mean sufficient statistics, we can bound distance in parameter space. The following completes this.
7

---

Lemma 3.9 (Non-truncated MLE Solution Distance to 8*). Suppose 0" satisfies the conditions of
Claim and Pe- (5) = a > Let 0, be such that Expo [T(x) where 7 -i=1 T(x,) given
each p Let >> 0 and 52
28
log(1/6)). Then w.p. least 1 - 6,
Es
0, - 0* - X (O 1/a) +
Proof. Define ( ( Ex- Po (x)]. Its gradient and Hessian calculations can be done similarly to E(0), the truncated version, but with $ = X' the full support of the distribution.
Since Ex-pa- [T)) Ex- [xx)] = Ve(0") )umtr is the gradient of the untruncated negative
log-likelihood whose optimum is at 8. by Al this gives
unir (0)) Ve (0o) 2 1110 0* = 110n 001 S untr (0")
where the result follows from the fact that Exzpo [T()] = T and |ixppor (T(2)) TI| < Olog 1/a + es) w.p. 1 - 5 from Lemma 3.7
Note that this result combined with Lemma 3.4 gives Corollary 3.9
3.4 Analysis of Projected Stochastic Gradient Descent Algorithm
Now we have all the tools we need to analyze the main algorithm. For ease of notation, define d(a) = es + Olog 1/a) which is constant that depends projected stochastic gradient descent algorithm referenced by Theorem 3.1
The following describes the
Algorithm Projected SGD Algorithm Given Truncated Samples
Given [x: [x:}==r each x; ~ pg.
Initial Op R& s.t. Ex-pe, [T(z)] = T, where = -, T(x:).
for i 0, ...... do
V; Sanpleerrddien(( 0,)
0;+1 0: 1/V.
Project 0 onto K = B(0o, d(a) x n.. end for Return 0r
Algorithm SampleGradient
Input: x, 0 while True do
Sample z ~ Pe
if (z E 8) via membership oracle then
Return T(z) - Tx))
end if end while
Given the results from the previous sections, we can now prove the main result. The analysis based on that of Chapter (Theorem 5.7) of [20] which we modify and state below:
Theorem 3.10 (SGD Convergence). Let f be a A-strongly convex function. Let
arg min k (0). Consider the sequence (0, ) generated by SGD (Algorithm 3) and [vr).
the sequence random vectors satisfying E[v; 0.] = v (0.) and [[[[v, 0.] p for all t, with
a constant step size 7) satisfying < 17 < It follows that for 2 0.
0* ||2 < (1 2n 0 7 02 0,
x

---

The proof is adapted and reproduced in Appendix D.1 for completeness. To apply the above theorem we need to take care of statistical problems:
(i) strong convexity f is strongly convex function over K convex set
(ii) smoothness / is a Lipschitz-smooth function over K
(iii) feasibility of optimal solution 0" E K.
(iv) bounded variance step for all 1, v.l 0.] < p² for some p²
and algorithmic ones:
(a) initial feasible point efficiently compute an initial feasible point Oo
(b) unbiased gradient estimation efficiently sample an unbiased estimate f (=VE)
efficient projection efficiently project parameter space K
Statistical problems. Firstly, (iii) is assumed. (i-ii) is addressed by Lemmas 3.2 3.3
3.6
3.9
3.7
3.4 In particular,
initialize with 0, such that 1 0" || v d(a)) by Lemmas 3.6
3.9
3.7
with probability at least 1 - ó. Given this On. we can construct K = B(O,, X nne O which has the property that
dia)
|0 - 0 1 A d(aa, vo e K.
Thus by Lemma 3.4 we will also have
(o( 2 exp (-6 (d(a)) > O, v0 K
where T is the condition number. Since are projecting to K in which all parameters have non-trivial mass, our objective remains strongly convex. In particular, our objective ((0) has
AsI = v 1 LsI, VO E K,
2deg
where As a² exp( 67 (d(a)))
À and Ls exp (6p (dla)))) L some constants which
4Cddgg
depend on a, A, L. and the maximum degree, deg, of the sufficient statistics. It remains to address (iv), which is done by the following lemma.
Lemma 3.11 (Bounded variance step). Let v, denote the output of SampleCradient(x,, (x, 0,) at any iteration E [N]. Provided that | [x)) - Ep [xx)]] < O(lo 1/pe for all 0 E K,
BiIlv; 0+11 &
kLs kL + (1 + (O
Proof. At any iteration (arbitrary).
E B|[[v:||
2
0:]
E (x sn
[I[((2) T(x)
E (ex) Spÿ- [1] 2(T()), [[
Tr
(CCo + (E[II 2(E(T(z)), [x(()))
(TT
(Cov (r + |E [T())] - E,g. [Tx)]]|
< kLs + KL + (1 +
In the last step, we' 've used the fact that
|Bpg [T()]] - Egg [T()]]] < ||B [T(z)] Eye, [T()]] + Epe, [[()]] Epg. [T()]]]
| Pg.
[T()] Epp, [T))]] Epp [z))] Epo, [())]]
(log 1/ (S)) + (2L/)) 1/Po, (S)) cs)
by assumption, smoothness, Cor. 3.8 and Lemma
3.9

---

we can address (a) by solving the empirical MLE problem with no truncation. Given that we can efficiently sample exactly (or approximately see Appendix (.2) from the non-truncated po for any 0, we can sample unbiased gradients via Algorithm 2 with expected O(1/Po, (5)) = O exp(sx:(a/aa)))
Algorithmic problems. For the algorithmic problems, by Cor. 3.8 and Lemmas 3.9 3.7
a²
samples each step address (b). Point (c) can be done efficiently, since our parameter space is simple intersection of Euclidean balls if we choose & to be Euclidean ball that sits inside the whole parameter space which contains 0"
((4++))((+2+))) (( (ox(d(a)) a)². Putting everything together, to get
Let (k, L, a) E - 0 112 2 e,, the number of iterations and samples should be
Age²
N 2 max { D(k, 1, 1 }) log
(2d(a) Xe?
provided that 1j = min Age 1 h. applying Lemma D.1 to the bound from Theorem 3.10 with 2p
Ag
A = As
C = As p 2Xs, and p² = kLs + kL + (1 + (O l/po by Lemma 3.11
Further, Lemma 3.4 guarantees (log 1/pe(11pppp ( ()) S O (lo explox-(dla))) for all K.
In probability, we get O 1| 2 3x2) f 1/3 by Markov's inequality. Then can amplify the probability of success to 1 - 5 by repeating the procedure from scratch log 1/5 times, as in 10] Given polynomial time (poly k, 1/c)) algorithm As to sample from po for all 0, each
iteration takes expected (LL/po, (S)) O (xp(6*-(d(a))) times the running time of As plus the
projection step (which is also efficient). This completes the result of Theorem 3.1
Remark. In the Gaussian case, the sample complexity was given in terms of m, the dimension of the and was stated in [10 as O(m² / For multivariate Gaussian, the dimension k of 0 is the dimension of [x, xx (vectorized) which is m + m², thus we can recover the previous result.
Numerical example. While lot of the analyses shown can seem complicated, they give some guarantees for rather simple algorithm: simply initialize your parameters using MLE as if there is no truncation at all, then run projected stochastic gradient descent using rejection sampling. We do not even need to describe the truncation set S as long as we can query whether point is inside S or not efficiently. As proof of concept for the use of this algorithm, we've implemented our simple projected SGD algorithm to learn the parameters of multivariate exponential distributions, given truncated samples. To save space in the main body for exposition of the theoretical results, we ve included the results and details in Appendix E
4
Discussion
To our knowledge, this work is the first which develops computationally and statistically efficient algorithm for learning from samples truncated to very general sets S of the form in [10] in high di- mensions whose distribution does not rely on Gaussianity. This work also has interesting implications for learning general log-coneave distributions through applying the Taylor theorem to the log density as in [12] and for sampling (e.g., as in (30). Through generalizing the previous Gaussian results to general exponential families, we also extract the broader abstract properties (c.g., concentration and anti-concentration) of distributions for which the previously proposed projected stochastic gradient descent procedure still applies. It would be interesting to understand how much these results can be generalized to densities beyond exponential families, or even to extend the current work presented from expected polynomial running time deterministic polynomial running time. We hope that our work provides the foundation for future work in this direction.
5 Acknowledgements
We thank Tim Kunisky for insightful discussions during the preparation of this work. Jane Lee was supported by GFSD fellowship sponsored by the U.S. National Security Agency (NSA).
10

---

References
[1] MA Beg. Optimal tests and estimators for truncated exponential families. Metrika, 2901):103- 113, 1982.
[2] Daniel Bernoulli. Essai d'une nouvelle analyse de mortalité causée par la petite vérole, et des avantages de I' l'inoculation pour la prévenir. Histoire de I'Acad., Roy. Sci.(Paris) avec Mem, pages 1-45, 1760.
[3] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with projected langevin monte carlo. Discrete Computational Geometry, 59, 06 2018.
[4] Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis. Optimal learning of mallows block model. ArXiv, abs/1906.0 190090000,00, 2019.
[5] Carbery and Wright. Distributional and l-q norm inequalities for polynomials over convex bodies in r-n. Mathematical research letters, 8(3):233-244 May 2001.
[6] Yeshwanth Cherapanamjeri, Constantinos Duskalakis, Andrew Ilyas, and Manolis Zampetakis. What makes good fisherman? linear regression under self-selection bias, 2022.
[7] Sinho Chewi. Log-concave sampling. Book draft available at htts:://cewissino. github. io, 2022.
[8] Clifford Cohen. Truncated and censored samples: theory and applications. CRC press, 2016.
[9] Georges Darmois. Sur les lois de probabilitéa estimation exhaustive. CR Acad. Sci. Paris, 260 (555)888 1935.
[10] C. Daskalakis, T. Gouleakis, C. Tzamos, and M. Zampetakis. Efficient statistics, in high dimensions, from truncated samples. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages Society.
Los Alamitos, CA, USA, oct 2018. IEEE Computer
[11] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Com- putationally and statistically efficient truncated regression. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secons Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 955-960 PMLR, 25-28 Jun 2019.
[12] Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, and Emmanouil Zampetakis. statistical taylor theorem and extrapolation of truncated densities. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings Thirty Fourth Conference on Learning Theory, volume I 134 of Proceedings of Machine Learning Research, pages 1395-1398. PMLR, 15-19 Aug 2021.
[13] Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis. Truncated linear regres- sion in high dimensions. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 10338-10347. Curran Associates, Inc., 2020.
[14] Constantinos Daskalakis, Patroklos Stefanou, Rui Yao, and Emmanouil Zampetakis. Efficient truncated linear regression with unknown noise variance. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1952-1963. Curran Associates, Inc., 2021.
[15] Raaz. Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Log-concave sampling: Metropolis-hastings algorithms are fast. Journal of Machine Learning Research, (188))11-42. 2019.
[16] RA Fisher. Properties and applications of Hh functions. Mathematical tables, 1:815-852. 1931.
[17] Ronald Aylmer Fisher. Two new properties of mathematical likelihood. Proceedings of the Royal Society of London. Series A, Containing Pupers of Mathematical and Physical Character, 144(852):285-307 1934.

---

[18] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Efficient parameter estimation of truncated boolean product distributions. In Conference on Learning Theory, pages 1586-1600. PMLR, 2020.
[19] Francis Galton. An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data. Proceedings of the Royal Society of London, 62(379- 387):310-3155 1897.
[20] Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods, 2023.
[21] Charles M. Goldie and Claudia Klüppelberg. Subexponential Distributions, page 435-459. Birkhauser Boston Inc., USA, 1998.
[22] Patrick M Hannon and Ram Dahiya. Estimation of parameters for the truncated exponential distribution. Communications in Moaistics-Theory and Methods, 28(11):2511-2611 1999.
[23] Andrii Ilienko. Continuous counterparts of poisson and binomial distributions and their proper- ties. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Computatorica, 39, 03 2013.
[24] Andrew Ilyas, Emmanouil Zampetakis, and Constantinos Daskalakis. theoretical and practical framework for regression and classification from truncated samples. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4463-4473. PMLR, 26-28 Aug 2020.
[25] Sham Kakade, Ohad Shamir, Karthik Sindharan, and Ambuj Tewari. Learning exponential families in high-dimensions: Strong convexity and sparsity. In Yee Whye Teh and Mike Titterington, editors. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 381-388, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
[26] V. Kontonis, C. Tzamos, and M. Zampetakis. Efficient truncated statistics with unknown truncation. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1578-1595, Los Alamitos, CA, USA, nov 2019. IEEE Computer Society.
[27] Bernard Osgood Koopman. On distributions admitting sufficient statistic. Transactions of the American Mathematical society, 39(3):399-40) 1936.
[28] Alice Lee. Table of the Gaussian "Tail" Functions; When the "Tail" is Larger than the Body. Biometrika, 10(2/3):208-211 1914.
[29] Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
[30] Song Liu, Takafumi Kanamori, and Daniel J. Williams. Estimating density models with truncation boundaries using score matching. Journal of Machine Learning Research, 23(166):1 38, 2022.
[31] Gabriel Loaiza-Ganem and John P. Cunningham. The continuous bernoulli: fixing a pervasive error variational autoencoders. ArXiv, abs/
2019.
[32] Gangadharrao S Maddala. Limited Limited-dependen dependent and qualitative variables in econometrics. Num- ber 3. Cambridge university press, 1986.
[33] Oren Mangoubi and Nisheeth Vishnoi. Sampling from log-coneave distributions with infinity- distance guarantees. Advances in Neural Information Processing Systems, 15:326311, 2022.
[34] Karl Pearson. On the systematic fitting of frequency curves. Biometrika, 2:2-7, 1902.
[35] Karl Pearson and Alice Lee. On the generalised probable error multiple normal correlation. Biometrika, 6(1):59-68, 1908.
12

---

[36] Edwin James George Pitman. Sufficient statistics and intrinsic accuracy. In Mathematical Proceedings of the cambridge Philosophical society, volume 32, pages 567-579, Cambridge University Press, 1936.
[37] Orestis Plevrakis. Learning from censored and dependent data: The case of linear dynamics. CoRR, abs/2104.05087, 2021. 2021.
[38] Mathias Raschke. Inference for the truncated exponential distribution. Stochastic environmental research and risk assessment, 26(1):127-138, 2012.
[39] Adrien Saumard and Jon A. Wellner. Log-concavity and strong log-concavity: A review. Statistics Surveys, 8(none):45 - 114, 2014.
[40] Abhin Shah, Raaz Dwivedi, Devavrat Shah, and Gregory W Wornell. On counterfactual inference with unobserved confounding. arXiv preprint arXiv:221 1,02209, 2022.
[41] Abhin Shah, Devavrat Shah, and Gregory Wornell. computationally efficient method for learning exponential family distributions. Advances in neural information processing systems, 34:15841-15854, 2021.
[42] Shai Shalev- Shwalv-Shwartz and Shai Ben- Den-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
[43] John W Tukey. Sufficiency, truncation and selection. The Annals of Mathematical Statistics, pages 309-311, 1949.
[44] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
13

---

A Proofs and Calculations Regarding the Objective
A.1 The Truncated Negative Expected Log-Likelihood Function
The negative log- log-likelihood that x E S is a sample of px(x) is
( x) = - -lg h(x) T(x) + log / h(x') exp(0) Tomp((TT(x)) T((e)))
log P8 (x)
Its gradient w.r.t. 0 is
ve(0,x)= = -T((x) + Is T(x (((x))
Jg h(x') exp(1) (0 T(x'))dx'
-T(()) + [s T( ((xx)) exp(0) (Tp(TT(xx) T(x') - A(0))
Is 1(xx) exp(0 T(x) - A(0))dxx'
-T((x) + E2 [T())
The Hessian is
(2((0) ((sT())((x) ((x) exp(0 T(x) A()))
(Ss h(x))( exp(O T(x) - A(0))
(Ss T())l(x) (xs)))(xxxxx""""")))))
A(0))dx)
(Us (() exp ((x))TT())))))) A(())
( (Ss h(x) exp(@ T(x) - d()))
(Sg hxx) exp(@ T(x) - A()))
= Cov x-p (T(x),
We can similarly define the population negative log-likelihood as
| log -logh(x) h(x) 0 @T((x)) + log / exp(@ Txx)))xx)
?(0)= ExapI
vi( Expp..
[-T(x)] + Exppp [T(x)],
V (()(0)
A.2 Proof of Lemma 3.2
Proof. Define the following quantities:
(T(x) Exxpo [Tx))) (T(x) Exxpo [Tx)))) |
Rd Exxop
R' Exapp
(T(x) Ex [(x))) (T(x) T Ex (T(x))
(T(x): Ex Ex-py (T())) Ex-ng(((x))) (T(x) - Ex-pg (x())
Ex-nÿ
Claim 2. R' 2 R" (Proof Appendix A.4
Now, let & & with |El1 arbitrary. Then
< R = Exxxpo ((T(x) - Ex [(())) (T(x) -Ex~po (Tx))) = =Exxpo [pe(x))
R'R' = Ex-po [x)]
<RR RE Exmp (x)]
where Pe (x)x,, p'c (x) are polynomials of degree at most 2d whose coefficients depend on (under A3 Furthermore, note that for any & R Pe (x) 2 0 and p 0 (due to the rank one matrix inside the expectation being PSD).
14

---

First, since R' = R
R'R 2 R we have
Ex~pe [b((2)] 2 Eumpo [pe(z)] 2 A.
(18 400
2d
Now define the set A = {x px((x) 5 for yor
X where po(S) = B > 0. Theorem 8 of
says
C212/112))
20d 1/(2d)
2Cd . g1/(20) A1/(2d) 2
(A(
S
Ezzpp (p((c)))r 9/2d 1/9
1/(2d)
Ba-po [x)
2X
Now split Ezppp
[x) into the part on S A and S A Note that if pe(S) 3 and
(o(A)= S B. this implies po (S n A 2 as
3 2
B
8
(o(S po( + (o( (o(SUAA) 3+
1
-1
Then
Exupgna [p(( + + Fanagna [F{(2)] 2 po(S n A)
Po (S A²)
1
33 4Cd
(S( -04
17
2
= E Ex [P((Z)]
2
A
Po(S)
2
and the claim follows.
A.3 Proof of Lemma
Proof. Similar to the proof of the previous lemma, define the following quantities:
R Exupa
(T(x) Ex-po [x)))) (T(x) Ex po [T))))
R" Ex
(T(x) Ex~po [Tx))) (T(x) Ex~po (xx) ]
(T(x)) Ex [T()]) (T(x) Ex [Txx))
R B Exp
Claim 3. It holds that R"
R. (Similar proof Claim 2
Let & e R with [|E| = arbitrary. Then
< $ R & Ex [f [x))
{ R Ex [ (x)
{ R = Exxpi (x)]
where fe(x), f/ (x) are some functions which depend on x and (c.g., polynomials of degree at most
2d under A3). By the previous claim, we also have
E px [xe(x))
Exppg [[((x)]
Note that
E Exppp [fe / vx()) fx(x)dx
/ (0 po((x) fe(x) 1(x E S]dx S (S(S)
/
fe
=Bx-no [fc(x]]
Since AI 3 R < LT by A1 it holds that TR Ex S L, thus the following inequalities hold:
E RR = Ex-nglf((xx) S Ex-pi (fe())] po(S) L.
15

---

A.4 Proof of Claim 2
will prove a general claim which should take care both claims Lemmas 3.2 and 3.3
Claim 4. Let x ~ p be random vector with mean μ.. Let be another vector such that + p.
Then
Covx~p(x,X) x] Ex 1x 10)1 Exmol(x b) b) (b =)((b 14)
Proof.
E[(x - +)(xx 11)1
=E((x - b + b 11)(x b b -1)
Bl((x b)(x -bi + E[(( b)(b 11)
B[(b xx(x b)
E[(b μ n1
=(-1)-B((b-+1Q) 4)(b-+)
=(-I)-Ei(b--llC
=B[(b- (a((bb+))(bl wbا ]
E[(x b)(x b) E[(b pb - [
As a corollar, since the second term a rank-1 matrix (thus PSD), we have that (x(x-b((xDD)) El(x (x J.
B Examples of Other Distributions which Satisfy Assumptions
Example 1 (Exponential Distribution). The exponential distribution density can be written
(x(x) cxxp(-xxx Az) = exp( + log(A)),
defined +R+ which is convex set and for À > 0. In natural form, it is
po( exp(Ox + log(-0)))
defined for 9 < Note that
T T(x) is polynomial in s.
This log log-linear in x (so log-concave in .))
Variance of the sufficient statistic is simply the variance, which 1/02; > 0 any If we restrict / in bounded set, the negative log-likelihood will be strongly convex and smooth
Example 2 (Weibull Distribution with known shape k). The Weibull distribution with known shape k > 0 has density
(x exp((I: 1) log + (- 1 x² log k 1 log A) 2/
defined + and À > We can re-parameterize this in terms of 0 --- t with 0
(a * eexp(0 . + -log log(-0)):
Then
T(w)= * is polynomial in s.
Po (x) is log-concave in x if k: (where recall I and 0
The variance of the sufficient statistic can also be found by taking the second derivative of A(0) log log(-0) w.r.t. 0, which is also 1/0² 0.
16

---

Example 3 (Continuous Bernoulli). The continuous Bernoulli density
[3
can be written
1 - 2X
px(x) exp log -
log (1 A) log -
with support [0, 1] and À E (0, 1). We re-parameterize this in terms of 0 log A
I-X with
0 E [0,
Or log c² )
po(z) exp
Then
(a) = x is polynomial in æ.
(z) is log-linear in æ (so log-concave).
The variance of sufficient statistic is simply the variance again, which is given by
1/12 (A-1)A
Var(X)
otherwise
(1- (1-2A)2
(2tanh (1-nh-"(1-2A)>
This strictly positive and bounded for all values of (thus all values of 0).
Example 4 (Continuous Poisson). A continuous version of the Poisson distribution (although there can be others (23) can be written
1 AM
(x(x) = Z(A) +1
with support x E [0, 2o) and X E (0, oo). We can write this with = log so
1 po(x) [(x + 1) exp(@x A(0)).
Then
(œx) = x: is polynomial in s.
po (z) is log-concave in x for x E R
In parameters, the mean of this distribution through usual calculations (e.g., similar to those of the Gamma distribution). Note: absorb the e term into the partition function.
1
0
xd²
E|X]
dx
7(X)
JO
T(x + 1) x>x²
1
dæ
T(x + + x x =-.x((((())) l(xx
Z(A)
Jo
x- I(()
A 000
dx
Partition function, change var. 2 = x
7())
T(x)
Similarly, should be able to show the variance is À usual. In 0 space, this means the variance is exp(O) for 0 e R which is always positive. Again, we can make it bounded by restricting 0 some
Example 5 (Multivariate Gaussian). The multivariate Gaussian also satisfies all of these properties. Recall that the sufficient statistics of the multivariate Gaussian has
T (xx) |x, xx ] is polynomial in the components of with degree most 2 (where the xx term can be thought of as the vector after standard vectorization).
The multivariate Gaussian density is strongly log-concave.
17

---

The covariance matrix (of the sufficient statistics) has complicated form, which the authors of [TO] have analyzed the lower bound for, e.g., in their Claims and 2. As before, we can restrict our parameter space to ensure upper bounds.
Example 6 (Generalized Linear Models). This example is the same as the one given in 25 for generalized linear models. It is restated here for completeness.
Consider when we have some covariance, response pair (X,Y) drawn from some distribution D. Suppose that have family of distributions P(- 0; X)) such that, for each X, it is exponential family with sufficient statistic yy.X
P X) h(y) exp ((0, ty.x) A(0,
We consider one- one-dimensional exponential family qu with parameterization (0, X), then
P(y X) h(v) exp (v(0, log X)))
where we see that fy.x = yX and the log partition function A(0, X) = log Z(00, When qu is
Bernoulli family unit variance Gaussian family, this corresponds logistic regression or least squares regression, respectively.
We can appropriately generalize this to beyond linear models (e.g.. polynomials) provided that we can keep the distribution log-concave.
Comment on A3 We mentioned in the main paper that this assumption combined with log- concavity provides the ootiiconcentration property that we need for Lemma (32 We assume it for simplicity of exposition, but it should be noted that long property to control how much the covariance can shrink under truncation, we do not necessarily need T(x) to be polynomial. However, we' 'e provided examples of exponential families which already satisfy this above (and there are potentially more which can addressed by this framework that do not have polynomial sufficient statistics but nonetheless exhibit similar anti-concentration properties).
have the type of anti-concentration
C Proofs Relating Truncated and Non- Von-Truncated Quantities
C.1 General Truncated Densities
Let p be a probability distribution on Rdd Let S C Idd be such that p(S) for some a (0, Let p p(( S) be the conditional distribution of x ~ P given that x E S.
0. (x())= p(x) 1(x E S}
P(S)
Note that the relative density is
8 (x)
1 E S}
p(x)
P(S)
Then compute that the Rényi divergence is constant for any order 1 S.q q S co.
<L(p*1lp)
Ep
log E ps
log
log
P
((S)
8
1
(10))lp)
1.
p
P(S)
a
1
s
9-17
1
1
(p0)))))
log Eps
log
log
log
9-1
q
p(S)0-
P(S)
1 (xx)
Rzo (x (10)) log sup
loo
log
p(x)
P(S)
0
Note R2 (pp) log(1 + (2 ((p0((p))) [|p))-
We recall the following general estimates.
18

---

Lemma C.I. For any probability distributions (such that the quantities below are finite):
1. [Bp[x] - E. x & (x (x)x
2. [=][|x]]]] - F ||| | S
3. Var, Var, (x) S (x) v 2E Rg [x]|
Proof. The first claims are immediate by Cauchy-Schwarz. For the third one, recall can write
Var, = 2 E B0p |||x-|||| -y|l".
-
Then by applying part (1) 002 and (T) 82, get
[Var,(x) (ar=(x)] _
x | 232)
,2, 02 xx - y/1$]
= (x>((pl=))
+ 1)3 v 2E ||x - E, [x]]]]]
6. x|x E x |
2
$
8 -,, [x|14]
For our application, we have the following. Given probability distribution P on Rd, we let p(p) Ep[x] be its mean, and for &s E
Ma(p) == EpIlx p(P))1+
So for example we have M2(p) v (x), We also have M&(p) & Me(p) if S.. Lemma C.2. Let p be a probability distribution on Rd Let S S R2 with p(S) = a E (0, 1]. Then
1. E [x] [x]]]|| S V
I-n (x),
2. Var e (x) (ar,(x))
2(1-a*
Mr(p)
Ma(e) for some 0 S < 1, then
In particular, a (0, 1] is such that
2 + 2Mx(p)*
Var (x) 2 (1 - c) (x),
Note that the constraint on a above implies 1 < 2. so so 1 - a will be very small.
22/3. But M2(p) < M1(p), then
Recall also that under conditions, e.g. if p log-concave, then have the reverse bound that
M2(p) 2 C2,1
for a universal constant C2.1. so the constraint above is not too restrictive, as it allows of constant size.
C.2 Exponential Families with Strongly Convex and Smooth Log-Partition Functions Sub-Exponential
Let 0 such that 0 3u θ for some 8 > 0 for all unit vectors and such that Assumption A1 holds for Pg- Then X = u (T(()) Ex~po [x))]) is SE(L, 8).
Proof. WLOG, consider pe in the transformed space x
x + T(x) so that
(t) hh()) exp A(O))dt,
19

---

[T and by A1 A(0) a X-strongly convex where 0 E θ and A()) log ((()) log (Trox) h(t) exp(0 t)dt
is the log- partitariionnn function.
Note that V A(0)= = Covt-po(t)
and L-smooth function in 0.
To show that (t) is sub-exponential with parameters (v², we need show that its moment generating function satisfies Ele?" (t (t-r)) I erP2212, where μ = Ep [t], u is a unit vector, for |7| < 1/3.
Blezu((t- (t-1)) = / ( (enu"t-mn'r) 1(t)c (
exp(->uT|p 14)
/ h(t))xp((( + TTt t)
Z(0)
Z + -xp(-nu' m1)
7(0)
The inequality we need to show is equivalent to proving
Eiezu' (t- (t-w)] S 69
(ru +
E -m S 6591v9 2/222
Z(0)
Z(nu + 0)
S n 1222
Z(0)
A(yu + 0) A(0) S ru²? μ + 7²22
2
Since A(0) is L-smooth, we have that
I²L A(yu + 0) A(0) - VA yu) + 2 1/ 11 +
L
2
where we've used the property of exponential families that the gradient of the log partition function is the mean sufficient statistic. Now we can see that the appropriate parameter for 2² is L and must be small enough so that yu E O i.e., hy 1 for some 3 0. This is possible if is bounded away from the boundary of θ
Remark: In the above, only needed log ieg-patiition function A()) is smooth. is also possible to show that pe has exponentially decreasing tails (in quantities involving rather than T(x)) if it is log-concave in (assumption A2). e.g., by
that pe is exponential family distribution and that its
39
C.3 Proof of Lemma 3.4
Let (x( 1xx) exp T(x)) - A(0)) and A: θ + R is the log seg--aatition function:
A(O) / exx))xx((0)) (xx))x))
Lemma C.3. For any g > 1,0,0' E e
97
Epo
Pa'
= exp ((q 1)A(0) qA((')) + +A (g - 1)0))
pe
Proof.
(200)
)
/ h(x)) exp A())) exp (g 0, 0,T(z)) qA((") + qA(()) dr
Epo
pe
exp
((g ()) qA(0') + A (g0' - -q- -q-11)0)
20

---

Lemma C.4. Assume A is convex and L-smooth on Q For any S S X, and 0, 0' O:
(-
31. - 000 0112
Po( 2 Por cxp
(- 2
Proof. By Cauchy-Schwarz,
Per (5)² = Ep
Po' Po
1s
27
Po'
$ po((S) Ep
Pe
Po( exp
(A(O) 2A(0') + A (20' -0)
Since A is convex and L-smooth,
A(O) < A(0') + (VA(O),, 0 0')
L A(20' 0) S A(0') (VA(0'), 0' 0) 1 012
Therefore,
L
A(0) 20( + A (20' 0) s (V VA(0). 0' 0)
0 011
2
3L
< 0' 012
Compare this to the Gaussian case (e.g., see H.8 of 37 where this was po
exp - ( 2og 1/a- 1r²² for |0 0' <r.
C.4 Proof of Lemma 3.7
Let = 1 Em T(x;) be the empirical mean sufficient statistics given our samples {x; each
X;
Po.
Let Es > 0. For 2 Ω log (t)
IT Epg. [Tx)]]l < cs + O(log 1/a)
with probability at least 8.
Proof. Let D² = Exxppa- (x)]. For any event A, have that
[A] = / HW (w) = a li A}1(We e Stdpe (w) S P pa- [A] P.
and for the product measure with independent components F P So we can bound the probability of events on P with those on pø- In particular, by Claim and by the composition property of independent sub-exponential random variables, have that
[A] S (2) FI. | Pe- [A].
P
u T
Σ T(x)) - -0¹
2 < exp
nn
for any unit vector
Po-
2,8
+P po-
1
Σ T(x;) - 12¹
2t
S exp
nt
2
21

---

To translate this to the probability of the same event on pă.. note that
(1)
nt
exp
S 8
exp n log 1/a
23
23
which holds when 2/3 (log 1/0 + #/ log 1/6)- Thus for n >
29
log 1/6 samples from the
ce
truncated pÿ- we have that with probability at least 1 6, the quantity
[T
--v"l S 2/ 1/a) t
D Additional Proofs for Algorithm Analysis
Algorithm 3 Stochastic Gradient Descent
Initialize some 0g E K.
for iteration = 1.2..... do
Compute V, such that E[(v 0.] v.((O.)
0111 f 02 7/V:
0,-1- x (0.-1)
(Project onto K)
end for Return 0r
D.1 SGD Algorithm and its Analysis
Although the setting of Theorem 5.7 of (20 is when the objective is a sum of many functions, the proof and its result can be easily adapted to setting.
Theorem. Let f be a A-strongly convex function. Let 0* E arg mingee f(0). Consider the
sequence {0,} [====11 generated by SGD (Algorithm and {vrhez the sequence random vectors 6e < p² for all t, with a constant step size
satisfying E[v; 0,] = f((e,) and B[llve|l
1
satisfying < x- follows that for O,
0 11 s 1I 021 " N
Proof. At any iteration i
0 111 0; r|v;
1+1 0" 0 0" -iv,
(I)
00 00 || 0, 111 2n 0, 0-) + 1
where the last line comes from multiplying the line ① with the transpose of the same equation on
either side. After projecting to the set K to obtain 0,+1 = arg mingek ||0+11 0 and given that
0" E K, we have that ||0,+1 0²1 1| > 0 ;+ 11 so
|10+11 0" 1| < 00, 0-1 2n)(v., 0, 0-) + 1v
Fixing 0, in the 7th iteration and taking the conditional expectation in 2 gives
0 1 0.1 < |10, 10 ( 0, - 0") + r7 E
0
< (1 |0 - 0- + "| v |
where the last line due to strong convexity. (V. 0: 00) 2 aleo, 0" 12. By taking iterated
expectations and recursively applying the above, we get that
T
Bil r- [ 2n)
0 1-
+ 17 p
(1 22/22²
1
< (1 2nd) 100 1 + n
7
= (1 - 2md) 100 00
1|
" X
22

---

where in the second line we used that E (1-2nA)² 1-(1-2p1) 1-(1-2nA) 2nd provided 1) 1/2.
We can derive the complexity (number of iterations) to get Bill0r 0 < using the following Lemma from (20]. Lemma D.1 (Lemma A.2 of 20) Consider the recurrence given by
S (1 -mm))aa am + An,
where a > 0, and A, C' 2 0 are given constants and f < 1/C. If
E 24 C
" = min
then
1124 C 6 J
2000
t 12 max
log
+ az S.
11
Note that to get bounds on ||0r 0*1l rather than ||0r 11 we can solve the number of iterations we need to get e² on the right hand side, and we will get the number of iterations for ||0 0'| < e. Then the resulting complexity bounds will replace 1/c with 1/e².
D.2 Approximate Sampling of Non-Truncated Distribution
Many analyses of stochastic gradient descent assume unbiased directions at every iteration of the algorithm, but since we need to be able to sample from Po. multiple times at each iteration until we get a sample in S, our directions only unbiased if we can indeed sample exactly from po, each time for all i.
However if Pe. is complicated, exact sampling can be difficult or take too long. Since we assume that Pe is log-concave in x for all E O, we can at least approximately sample from efficiently via Langevin Monte Carlo, MALA, or other algorithms with convergence guarantees for log-concave densities.
Lemma D.2 (SGD Analysis with Biased Directions). Let f be a A-strongly convex function. Let f()). Consider the sequence {0r] generated by SGD but with the sequence random vectors satisfying Blv, 0,] = b, - vf(())) with |b, < and x- It follows that for
O"
arg min
(v
Nittel
E
0.] < p² for all f, with constant step size 7 satisfying
t t 0,
- + 2BD
0 0 s (1 - 2mA) 00,
Proof. Define b, Eb, 0 f f0:)) the bias for each t 2 0. The analysis of Theorem 3.10 can
be applied generically to get Eq. 2
|0++1 0- 00 1²1 2n 0 0-) + v1
Now when taking the conditional expectation, we get
0
12 0,] $ 10, 1- (n, 0 0-) 2m (V,) 0 0-) n [ [0,]
< (1 0, 1- + 11 2 + b,llb,11l0 - 0"
Taking iterated expectations and recursively applying this gives now
T-1
OT - 0" 0-1 < (1- (1-2n)) 10, - 1² + > (1- 2n (1²p²² + 2n| b: -0
i=0
< (1 (1-2nd)² |00 - 1- |/2+ p²pp² + BmBD
yr
(1 20-22n7 10 - 0- np² 2BD
X
where the second line holds if |lb.|| < B, 0. - 0- < D, Vi (which holds under the assumptions).
Note that in our Algorithm 1 the following.
D here simply d() by construction. We can also control B through
23

---

Bounding the bias. can write
Fix some t. Let V. = T(z) T(x where ~ Pé, and x ~ pg. Then we
b = Ezmpa [[))] Exap [T(x)] + +Ezpp8 [T()]] Exppg. [T(x)]
= Pi [T(z)] - Bumpi [T()]
= - T(x) (Po, (x) - Po. (x))
(3)
If we know that (x) is bounded over 5, we can upper-bound this given the TV distance between Ss and po.:
Po;
||bll| s sup
[TX()]]
pa. Po, lIv.
xES
Since we assume that Ev, [T()) is finite, it should be the case that T(x) is bounded over its support
except potentially on some negligible sets. that case, we can replace T(x) with T(x) which replaces those potentially infinite values negligible sets with 0 and the integral expression in (3) would be equal to which uses (xx) instead of (xx), and the bound its norm holds given that T(x) is bounded.
Otherwise we can use bounds from Lemma C.1 to bound this as
|b: $
/x (p,,) Var pa, (T(x))
we have control over the chi chi-square divergence (see Section C.I for definitions).
If we know that (ar) is a 1-Lipschitz, real-valued function (e.g., when T(x) =), we can use the dual representation of W1 distance to bound this as
/ [(x))dp) - -f {(w))dn = W1 (7
(xx)) < sup
fEFFue
Proposition D.3 (Bounds truncated total variation, given bounds non-truncated). Suppose le.. Po. lv - S eTV for some eTV > 0. Then
&r
v0lllvv S pe, (S) 6TV
Proof. First, given that ll Po. Po. lrv S ETV, we have by one characterization of the total variation distance (the supremum of the difference in mass over all measurable sets)
po, (o, (S) 2 po. (S) crV.
Now for the truncated densities,
/
Pr. - P3. 11r 11rv=
2 170 (x)
Pr, (x))dxx
1
po, (x)
Po: (x)
1(x S)
po. (5) dx
2
po. (S)
CTV
po. (x) Po. (x) dxx
pe. (S) CTV
ēy
po; po, (S) CTV
Efficient, Approximate Sampling. There exist several results in sampling which give bounds in TV distance in polynomial time (mixing time bounds) for log-concave distributions, e.g., [[5].
B. but which also usually require that the log density also smooth (in x, not 0). There are also proofs for Langevin Monte Carlo when the log density is convex and Lipschtiz, not necessarily smooth (e.g., see Chapter of 77, or under LSI (which implied by strong log-concavity) with convergence in Renyi divergence (e.g., Chapter 5 of 77). We can also use the proximal sampler to achieve convergence in KI. divergence under log-concavity (e.g., Chapter 8.4 of (7), which by Pinsker's inequality can bound the TV distance.
24

---

Proposition D,4 (Bounded variance step with bias). If EE| [|| v; |0,] p² where = =T(z) - Tx)
with z Pră. and then Blll; 0,1 S p² for v; T(z) T(x) with z Prs. and
x po. where
p²
Var po.
(T(z))
Var (T(z)) + p² + B
ró.
where
|b,
E2 2xpp
[T)
E Egppy [T())]l < B.
Proof. As in the proof of the exact sampling version, we can write
0,]
Varps, Pa. (T(z)) + Var pg- (T(x)) + |Bg [T()) Byg. [Tx)]]
Varps. Po: (T(z)) + Var Pg- (T(x)) + || [T(z)] Byg. [T(x)]] |b,l1
Varps (T(z) Varpi P0; (T(z))
+ Var pa;
(T(z)) + Var p.
(T(x)) + || [T())] - B [T())]12++ + |
B2
Sp²
Var (T(z)) Var po.
(T(z)) + p² - B²
We can bound the difference Var (T())) Var (T(z)) if have bounds Var (T(z)). r.
Pg.
through bounds like in Lemma C. if we can say something about the chi-square divergence, or through similar arguments to the bias bound if we assume some bounds on [x]] over its support.
E Numerical Example
To illustrate how the algorithm performs in different dimensions, we implemented our algorithm for 2-, 5-, 10-, and 20-dimensional exponential distributions. In all cases, the truncation set is the (hyper-)cube [0, 2) We chose true parameters in all cases which resulted in an initial error at most 2.5. In all cases, have (average) 1.2 error at most 0.15. For stability (and to bypass repeating the algorithm multiple times stated in the analysis), we instead calculated gradients using the average of 10 samples which was sufficient to have stable training results. See Figure]
1500 iterations and step size 0.01, each repeated 10 times. In the end, all
Learning Multi-Dim Exponential Distribution w/ Truncated Data
2D
5D
10D
20D
1.5
Error
1.0
0.5
0
2
4
10
12
14
Iterations % 100
Figure 2: Learning 2-, 5-, 10-, and 20-dimensional truncated exponential distributions, In all cases, the truncation set the (hyper-)eube [0, 2|d
25

---

The wall clock time to finish all 1500 iterations of training for 5-, 10-, and 20-dimensions was 42.9 + 2.2, 49.1 = 6.5, and 61.2 + 3.0 seconds, respectively. We can see that the running time not doubling with the doubling of dimensions.
26


Reviews:
[{"review_id": "ZMOmCMr0QM", "reviewer": "Reviewer_Dgrb", "summary": "The paper proves the convergence of projected stochastic gradient descent (SGD) on the maximum-likelihood problem associated with estimating the parameters of an exponential family given truncated samples.\nThis result generalises previous work that shows similar results for Gaussian distributions to exponential families. To this end, the paper assumes bounded variance, log-concavity, sufficient statistics being polynomials, and bounded conditional expectation in the tails of the distributions.\nThese assumptions imply the convergence of SGD and, thereby, the existence of a polynomial-time algorithm for parameter estimation given truncated samples.\n", "questions": "Covered by \"Weaknesses\" above.", "limitations": "Limitations appear to be discussed wherever appropriate.\n", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am writing this review as an outsider to truncated statistics.\n\nThat said, even as an outsider, I find this submission well-organised and readable despite its technicality, which speaks for the clarity of the exposition. I feel a little less like an outsider after studying this work.\n\nThe results appear to be novel, and I have the impression that constructing an algorithm that estimates any (sufficiently well-behaved) exponential family from truncated samples (and not \"just\" a Gaussian; quotation marks because this kind of analysis requires non-trivial work even for Gaussian distributions, see [10]) is a significant result.\n", "weaknesses": "As mentioned above, I am not an expert in truncated statistics. \n\nEven though, overall, I think this is a nice paper, I would like to comment on some potential weaknesses:\n\n1. Without having studied reference [10] in full detail, it seems that the analysis in the submitted paper mirrors that in [10] rather closely. A similarly structured analysis can be fine, but a more specific contextualisation of Section 3 may be warranted. I would like to hear what the authors think about this.\n\n\n2. Although I am fully aware that this paper is theoretical, reading about the efficiency of the proposed algorithm makes me want to see the algorithm \"in action\". Numerical demonstrations only appear to be optional in this line of work: some related works include them (e.g. [15, 31]), and some do not (e.g. [10, 12, 14]). But I think the present paper would appeal to a broader audience if it contained a few demonstrations of projected SGD for learning parameters of exponential families (maybe including, but not restricted to, Gaussians). \n\n\n3. I found the appendices really helpful in understanding this work (some contain crucial information for proving some of the results). However, it did not help the readability of this manuscript, having to jump back and forth between the appendix and the main paper. Some parts must inevitably move to the appendix to condense such a comprehensive analysis into nine pages. But this makes me wonder whether a conference with a page limit of nine pages is the appropriate venue for this work. (For context: since related work of comparable volume (e.g. [14, 15]) has been published at Neurips, there seems to be a precedence for accepting this submission despite its length).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Firstly, we thank the reviewer for the careful reading of our paper. We are very happy to hear that the reviewer found the submission well-organized and readable despite the technicality. We will use this space to address the main weaknesses mentioned in your review:\n\n1. _\"Without having studied reference [10] in full detail, it seems that the analysis in the submitted paper mirrors that in [10] rather closely. A similarly structured analysis can be fine, but a more specific contextualisation of Section 3 may be warranted. I would like to hear what the authors think about this.\"_\n\n**Answer:** Thank you for your comments! We had structured the analysis in this way because it is a common structure used in the related works, and we felt that familiarity in presentation may help with the readability of the results. We agree though that perhaps we can compare/contrast the parts of the analysis which differ from the Gaussian case much more clearly in the main content. Perhaps in the line with the remarks in Section 3.1, we can include more remarks in Sections 3.2 and 3.3, such as expanding on the comment made after Lemma 3.5 to contrast that in [10], the mean and covariance are analyzed separately whereas in our setting we consider them together (as $\\theta$).\n\n2. _\"Although I am fully aware that this paper is theoretical, reading about the efficiency of the proposed algorithm makes me want to see the algorithm \"in action\". Numerical demonstrations only appear to be optional in this line of work: some related works include them (e.g. [15, 31]), and some do not (e.g. [10, 12, 14]). But I think the present paper would appeal to a broader audience if it contained a few demonstrations of projected SGD for learning parameters of exponential families (maybe including, but not restricted to, Gaussians).\"_\n\n**Answer:** We did not include numerical demonstrations due to (1) the theoretical results already taking a lot of space to present (including the appendices) and as you mention (2) it is not usually included in similar/related works. We also believe that the current work is a stand-alone result of its own value, and that much more can be done (beyond the scope of this work) to make this algorithm perform much better in practice using domain knowledge. We agree that real-world application of our work would be very valuable, but may be more appropriate to include in a significant extension of the current work. \n\n3. _\"I found the appendices really helpful in understanding this work (some contain crucial information for proving some of the results). However, it did not help the readability of this manuscript, having to jump back and forth between the appendix and the main paper. Some parts must inevitably move to the appendix to condense such a comprehensive analysis into nine pages. But this makes me wonder whether a conference with a page limit of nine pages is the appropriate venue for this work. (For context: since related work of comparable volume (e.g. [14, 15]) has been published at Neurips, there seems to be a precedence for accepting this submission despite its length).\"_\n\n**Answer:** Thank you for your careful reading and feedback! We also had a hard time with deciding how best to write the current paper so that the reader can get the main ideas but without eliding the necessary technical results. Perhaps we can even move some of the technical lemmas to the Appendix to improve readability, and include more intuition and exposition in their stead. We would like to hear any feedback on this suggestion (from all reviewers)."}, {"review_id": "sbwfIBSGQ3", "reviewer": "Reviewer_P6iL", "summary": "The paper proposes a new general method for estimating the parameters of exponential-family (EF) distributions from truncated samples. The method is presented as an algorithm, which allow us to obtain good estimates of $\\theta$ in polynomial time and certain accuracy conditions. The whole methodology extends previous advances in parameter estimation from truncated samples (these last ones mainly with Gaussian densities and regression problems). The formal results included seem to be theoretically well grounded on the properties of exponential families, exploiting previous methods to both lower and upper bound the covariance of the sufficient statistics given the truncated samples. \n\nIn practice, the algorithm looks efficient (to me), as it seems to compute a certain gradient step given a measure of distance between the sufficient statistic functions of the truncated samples and the true samples of the formal EF distribution. Later, this parameter update is corrected (as it was only computed from a truncated sample that might guide it towards bad locations), and in particular, projected into the \"correct\" parameter space where it will finally converge to the desired estimate.", "questions": "**Q1** -- Is there any sort of truncation effect on the samples that the given algorithm could not deal with properly?\n\n**Q2** -- Is there any fundamental difference between $\\rho$ and $p_\\theta$ in the Equations below L138, L139 and the probability distribution mentioned in L230?\n\n**Q3** -- In L122, the Cov[x,x] is described as a matrix, later for the Lemmas 3.2 and 3.3, the same covariance is upper and lower bounded using scalars. How this bound of a matrix with scalars work? Are we bounding all elements in the matrix?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Despite some points and details that I will later add, I liked the paper quite a lot, in my opinion, the construction of the theory around exponential families is clear and strong. This last point is indeed not easy, as EF have very good properties that are however not that easy to exploit without the proper experience. In that sense, I also found very strong the use of such properties to build the main properties of the objective in section 3.1 (the three equations behind the first paragraph) which to me seem to open the door to the main result provided in the algorithm. Also surprisingly, the algorithm for estimation seems easy and direct to use, even if theory is a bit more complex. To me the paper has several strengths that is worth remarking: 1) the generalisation of the previous theory on estimation from truncated samples to exponential families, 2) the clarity and utility of the exponential family principles to make the parameter estimation possible and 3) the final result provided in the algorithm which makes the estimation possible.", "weaknesses": "In my opinion, there are two lingering points that makes me think the paper is perhaps weak in some degree..\n\n**Point 1.** First, even if I liked the idea, the utility, the algorithm and the results provided in a significant way, I had a hard time reading it and kind of building myself the answers to what the main contributions and strengths of the work are. What I want to say is that somehow the synthesis of the work has been led to the readers, instead of building the story of the paper in a direct and more clear way. I'm not saying that the theoretical results should not be included in the main manuscripts, but some of the proofs could be perhaps moved to the appendix and glue all technical details a bit better to understand where the contribution of each one is important for the final algorithm. In this way I'm referring to the sections 3.2, 3.3 and 3.4 mainly. On the other hand I think that the presentation of the algorithm is great and it seems to be a fabulous result (at least to me), but one has to dig quite a lot to find what it the role of the previous elements in that one. This is important, particularly for a submission of this type, for reproducibility and clarity -- which in the end leads to impact, of course. \n\n**Point 2.** The second one is related to the lack of empirical results. As I said, even being a paper with relevant contributions and technical discoveries, I had the feeling once I finished to read it that I would have liked to see some empirical results. Mainly on the performance on the algorithm for different sets  of truncated samples, dimensionality and types of probability distributions. I understand the class of paper that this one is, mostly theoretical, and that once one proves such good estimates of parameters on exponential family distributions, which are super general, but to me it does not prevent the benefits that empirical results could produce on the clarity and quality of the manuscript. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and for appreciating our results despite the weaknesses stated! We will use this space to address the main weaknesses and answer the questions you listed.\n\n### **Weaknesses:**\n\n1. _\"First, even if I liked the idea, the utility, the algorithm and the results provided in a significant way, I had a hard time reading it and kind of building myself the answers to what the main contributions and strengths of the work are. What I want to say is that somehow the synthesis of the work has been led to the readers, instead of building the story of the paper in a direct and more clear way... In this way I'm referring to the sections 3.2, 3.3 and 3.4 mainly. On the other hand I think that the presentation of the algorithm is great and it seems to be a fabulous result (at least to me), but one has to dig quite a lot to find what it the role of the previous elements in that one. This is important, particularly for a submission of this type, for reproducibility and clarity -- which in the end leads to impact, of course.\"_\n\n**Answer:** We apologize if the presentation of the results were not clear. We can (as suggested in response to Review Dgrb and the one to all reviewers) instead think of moving some less essential technical lemmas to the Appendix and use the main content pages to write more intuition and explanations. We can also re-organize the sections: the strong convexity and smoothness parameters in 3.1 depend on $p_\\theta(S)$. After this, perhaps we can introduce the results for section 3.3 (to bound $p_\\theta(S)$), and then 3.2. We welcome any feedback here!\n\n2. _\"The second one is related to the lack of empirical results... I understand the class of paper that this one is, mostly theoretical, and that once one proves such good estimates of parameters on exponential family distributions, which are super general, but to me it does not prevent the benefits that empirical results could produce on the clarity and quality of the manuscript.\"_\n\n**Answer:** Thank you for your feedback! As we also mentioned in other responses, we did not include numerical demonstrations due to (1) the theoretical results already taking a lot of space to present (including the appendices), (2) it is not usually included in similar/related works. It is also our opinion that while simple simulated experiments may be less helpful for this paper than using the limited space for more intuition and exposition, real-world application may be beyond the scope of the current work. \n\n### **Questions:**\n\n1. _\"Is there any sort of truncation effect on the samples that the given algorithm could not deal with properly?\"_\n\n**Answer:** In general, the algorithm can deal with arbitrary truncations of the support of the data generating distribution as long as the truncation set has a non-zero measure. For instance, if the truncation set lies in some lower dimension with zero mass under the data generating distribution, this cannot be dealt with (although any zero-mass set cannot have a truncated density written in the form in L138). If we cannot even decide whether a point is inside the set or not efficiently, this would also be an issue.\n\n2. _\"Is there any fundamental difference between_ $\\rho$ _and_ $p_\\theta$ _in the Equations below L138, L139 and the probability distribution mentioned in L230?\"_\n\n**Answer:** The distinction between $\\rho$ and $p_\\theta$ are just for differentiating any density $\\rho$ and an exponential family distribution parameterized by $\\theta$. Thus the result in L230 holds for any density, not necessarily even an exponential family distribution.\n\n3. _\"In L122, the Cov[x,x] is described as a matrix, later for the Lemmas 3.2 and 3.3, the same covariance is upper and lower bounded using scalars. How this bound of a matrix with scalars work? Are we bounding all elements in the matrix?\"_\n\n**Answer:** Since the covariance matrix is PSD, we are using the Loewner order to express its eigenvalue bounds (notice that the constants are multiplied by the identity matrix so it is indeed a matrix). We should have made bold the ‘I’ for the identity matrix; after making this change, we hope the statement will be clearer. "}, {"review_id": "oK0jIEjkM8", "reviewer": "Reviewer_UJWe", "summary": "This paper focuses on estimating a parametric family of distributions using a truncated sample, i.e.  the sample can only be collected within a subset of the data domain. The primary objective is to develop efficient algorithms for estimating the parameters of this family. To achieve this, previous findings on truncated samples from the Gaussian case are extended to exponential families.", "questions": "You mentioned that \"Some intermediate results can even be generalized to distributions beyond exponential families.\"  What are the key factors that are needed for such an extension?  Can you provide some concrete examples where such extensions are feasible?  \n", "limitations": "I haven’t come across any stated limitations, but it’s possible that I may have overlooked them.\n\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nThis is a theoretical paper that offers valuable support for the proposed algorithms. The extension to exponential families is significant. \n\t\t", "weaknesses": "This paper is solely theoretical and lacks numerical support for the proposed algorithms and theorems. It does not provide concrete examples to motivate the study. For instance, it would be helpful to provide real-world examples where the oracle property holds. \n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback! We will take care to use this space to address your main concerns and questions:\n\n1. _\"This paper is solely theoretical and lacks numerical support for the proposed algorithms and theorems. It does not provide concrete examples to motivate the study. For instance, it would be helpful to provide real-world examples where the oracle property holds.\"_\n\n**Answer:** \n * Thank you for your feedback. As we also mentioned in our other responses, we did not include numerical demonstrations due to (1) the theoretical results already taking a lot of space to present (including the appendices), (2) it is not usually included in similar/related works. \n\n* The membership oracle assumption has been shown to be necessary to solve this problem even in the Gaussian case (the previous work shows an impossibility result without even membership oracle access to the set S). We will make this more clear and add more explanation after this assumption. Practically, the membership oracle is an abstract but weak access to the set S; even if we know what S is, in practice it can be difficult to (mathematically) describe it yet much easier to decide whether a point is inside it or not.\n\n* In the response to all reviewers, we also give more concrete examples (please see above).\n\n2. _\"You mentioned that \"Some intermediate results can even be generalized to distributions beyond exponential families.\" What are the key factors that are needed for such an extension? Can you provide some concrete examples where such extensions are feasible?\"_\n\n**Answer:** \n\n* We apologize if the wording was not very clear. Some results like that of Lemma 3.4 (and Appendix C.1) hold very generally for any distribution over $\\mathbb{R}^m$. For instance, the KL divergence between (any) density and its truncation is $\\log 1 / \\alpha$, if $\\alpha$ is the mass of the truncation set under the density. We hope that these kinds of intermediate results can be used in the future to solve more general problems.\n\n* While we do have some of these lemmas which hold in general cases, to have a full comprehensive analysis we had to use properties of exponential families (e.g., Section 3.1, Lemma 3.7, Lemma 3.9). We leave for future work understanding precisely the limits of how much more this framework can be extended to general densities."}, {"review_id": "eEAYHulBri", "reviewer": "Reviewer_SUu1", "summary": "This paper considers a case where one has observations from a censored exponential family (i.e., an exponential family, but each distribution is conditioned to lie within a particular set) and wants to estimate the parameters of that exponential family.  An additional complication in the setup is that one does not have access to the set that observations are conditioned to lie within, but instead one has access to an oracle that can by queried and will tell you whether any given point lies within the truncation set or not.  This exact setting has been considered previously but restricted to less general families of distributions (e.g., multivariate Gaussians).  The authors develop a provably accurate estimator for the parameters of the exponential family that runs in polynomial time in all of the relevant parameters.  The main idea is to first perform maximum likelihood as if the data were not censored, and then perform projected stochastic gradient descent.  Stochastic gradient estimates can be obtained in this setting by using the oracle to perform rejection sampling using the non-truncated distribution defined by the current parameter estimate as a proposal distribution.", "questions": "* The wording of assumption II is ambiguous.  Do the exponential families need to contain _exclusively_ log-concave distributions?  Seems like yes from Assumption A2.\n\n* Does assumption A4 require additional assumptions on $g(s)$ (e.g., being finite)?  It seems like one could _define_ g(s) as $\\mathbb{E}[X | X \\ge s]$ and then the condition vacuously holds.\n\n* The informal version of the main result has a dependence on sample size, but the formal version does not.  I believe that the dependence on $n$ comes from $\\epsilon$ but in the setup of the theorem, it says we are given samples $\\mathbf{x}_1, \\ldots, \\mathbf{x}_n$ which makes $n$ seem fixed.", "limitations": "The authors do not include a broader impact statement.  I don't believe the work has any direct negative societal impacts, but it would be good for the authors to say so.  Additionally, I could imagine that estimating population parameters from censored data could, in principle, pose privacy risks, and so the authors may wish to make some minor comments along these lines.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "* The proofs are thorough, and, as far as I can tell, correct.\n* The authors make an admirable attempt to first discuss their assumptions and results at a non-technical level before present the more technical formal results.\n* The results are quite general, and the proposed algorithm is exceptionally simple and straightforward, making the approach appealing and elegant.", "weaknesses": "* The flow of the technical part of the paper was very difficult to follow.  The major presentation aspect that I felt was missing was a big picture overview of both the algorithm and the proof technique.  I felt like there was too large a disconnect between the informal statement of the results, and then diving directly into technical assumptions and lemmas without giving any intuition about why they were important or where they would be used.  I realize that space is limited in this venue, but perhaps more of the technical results could be moved to the supplement to make more room.\n* I also feel that the paper is missing some motivation.  To me, generalizing existing results is not in itself interesting to a broad audience.  I could imagine that the generalization presented in this paper is broadly useful, but some additional context would go a long way toward proving that point.  In particular, I am having trouble imagining a scenario where one has access to an oracle that can tell whether a given point would have been censored or not, but one does not have access to knowledge of the censoring set itself.  Just listing some specific, motivating real world examples would be useful.  I am not embedded in the truncated statistics community, so perhaps such motivation is obvious, but to a broader community I think additional motivation would be useful. \n* Lastly, some numerical examples checking the proof results would be useful.  How does running projected SGD on truncated data perform in some real world cases?  A comprehensive application or simulation study is obviously beyond the scope of this paper (and not necessary) but just a few toy examples would go a long way in giving an independent check of the analytical results.\n\nTypos / minor comments:\n* Line 34: \"is the first to provide\" --> \"are the first to provide\"\n* Line 76: Totally up to the authors, but it may be helpful to remind the reader that $m$ is the dimension of $\\theta$ here.\n* Line 192: \"log likelihood\" --> \"log-likelihood\"\n* Line 271: this sentence is not grammatically correct\n* Equation following Line 272: The \"$B$\" notation has not been defined.  Presumably it's an ($\\ell_2$?) ball centered at the first argument with radius the second argument.\n* In the equations around lines 458-460, it would be good to use a different dummy variable than $\\mathbf{x}$ in the integral as $\\mathbf{x}$ is already being used outside of the integral.\n* Equation after line 469: $p_\\xi^*$ is not defined, but based on the argument it matches the definition of $p_\\xi$ in the text above line 469.\n* Line 575: I believe that instead of $\\rho^S$ it should be $\\pi$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for a thorough and careful treatment in reviewing our work! We will do our best to address all of the weaknesses and questions listed in your review.\n\n### **Weaknesses:**\n\n1. _\"The flow of the technical part of the paper was very difficult to follow... I realize that space is limited in this venue, but perhaps more of the technical results could be moved to the supplement to make more room.\"_\n\n**Answer:** We apologize if the paper was not written clearly enough initially – as we’ve mentioned in our other responses, we will make efforts to reorganize the presentation of the technical results specifically by (1) moving some less essential lemmas to the Appendix and (2) moving Section 3.3 after 3.1, followed by 3.2, explaining why we need these lemmas along the way (e.g., Section 3.1 establishes that the strong convexity and smoothness parameters depend on $p_\\theta(S)$, which we bound in Section 3.3 as a function of parameter distances, after which 3.2 provides a good initialization). We are happy to hear any other suggestions.\n\n2. _\"I also feel that the paper is missing some motivation... In particular, I am having trouble imagining a scenario where one has access to an oracle that can tell whether a given point would have been censored or not... Just listing some specific, motivating real world examples would be useful...\"_\n\n**Answer:** Thank you for the feedback! We agree that it would strengthen the paper to better present the motivation. We had focused a lot of efforts in just presenting the main result. \n* To the point about generalizing results, while estimation from truncated data is a very classical problem with a long history in statistics, only recently did we have efficient algorithms to solve the problem in high dimensions for Gaussian distributions. Since many practical manifestations of missing data problems may not always have Gaussianity in the data generating distribution or the noise, any generalization gives the user more degrees of freedom to model real problems. It would be great to understand more completely how to solve these problems for even more general distributions beyond exponential families, but even this extension beyond Gaussians is quite new (and all prior results use properties of Gaussian distributions).\n* We also provide some more motivation/examples in the general response to all reviewers (please see above). \n\n3. _\"Lastly, some numerical examples checking the proof results would be useful...\"_\n\n**Answer:** As mentioned in our responses to the other reviewers, we did not include numerical demonstrations due to (1) the theoretical results already taking a lot of space to present (including the appendices), (2) it is not usually included in similar/related works. It is also our opinion that while simple simulated experiments may be less helpful for this paper than using the limited space for more intuition and exposition, real-world application may be beyond the scope of the current work.\n\n### **Questions:**\n\n1. _\"The wording of assumption II is ambiguous. Do the exponential families need to contain exclusively log-concave distributions? Seems like yes from Assumption A2.\"_\n\n**Answer:** Yes, the exponential families (before truncation) need to contain exclusively log-concave distributions. We will rewrite the assumption to make it more clear (perhaps instead of writing $p_\\theta$ we will write “the exponential family distributions we consider before truncation are log-concave”). \n\n2. _\"Does assumption A4 require additional assumptions on $g(s)$ (e.g., being finite)? It seems like one could define $g(s)$ as $E[X \\mid X \\geq s]$ and then the condition vacuously holds.\"_ \n\n**Answer:** Thank you for catching this, and we apologize that the wording was ambiguous. But yes we need $g(s)$ to be a uniform upper bound on $E[X | X \\geq s]$ for all distributions in the exponential family that we consider and should be finite for finite $s$, i.e., it should be that for every finite $s$: $\\sup_{p \\in \\mathcal{P}} E_p[X | X \\geq s] \\leq g(s) < \\infty$ if $\\mathcal{P}$ is the class of exponential families we consider. The second important property of $g(s)$ is that it should not increase as the dimension increases. We commit to rephrasing this assumption to clarify this in the final version of the paper.\n\n3. _\"The informal version of the main result has a dependence on sample size, but the formal version does not. I believe that the dependence on $n$ comes from $\\epsilon$ but in the setup of the theorem, it says we are given samples $x_1,…,x_n$ which makes $n$ seem fixed.\"_\n\n**Answer:** Sorry for the confusion here. Once we choose an $\\epsilon$, this determines how many samples ($O(k/\\epsilon^2)$) we will need (and iterations) to get the $\\epsilon$ error in parameters. The informal version simply wrote it the other way: given $n$, the error in parameters is $O(\\sqrt{k/n})$ (solving for $n = k/\\epsilon^2$). The informal one is missing some technical details, for instance $n$ needs to be at least a certain value for this to make sense. Thank you for catching this and we will update the informal version to match the notation of our main theorem.\n\n### **Other:**\n\n1. _\"The authors do not include a broader impact statement. I don't believe the work has any direct negative societal impacts, but it would be good for the authors to say so. Additionally, I could imagine that estimating population parameters from censored data could, in principle, pose privacy risks, and so the authors may wish to make some minor comments along these lines.\"_\n\n**Answer:** This is a good point! Our results indeed illustrate that just hiding some part of the space might not suffice to guarantee the privacy of that space. We commit to adding this in the final version of this manuscript.\n\n2. Typos\n\n**Answer:** Thank you so much for your careful reading! We will fix the various typos you have kindly taken the time to point out. Thank you again."}]

Author rebuttal:
# **Response to all reviewers**

Firstly, we want to sincerely thank all the reviewers for their time and careful feedback. We also want to thank all the reviewers for appreciating our results and recognising the significance of our work!

We start with addressing some common questions and concerns and then we will respond to the individual questions of the reviewers.

### **Difficulty following flow of technical results (Section 3), presentation.**
* We appreciate all of the feedback and suggestions to improve the presentation of the technical results. We are happy to move some technical lemmas to the Appendix and add more intuition and explanations in Sections 3.2 and 3.3, which we hope will improve the readability of the paper and it is a minor change to the submitted paper. We are also happy to take any other suggestions that the reviewers believe will help the readability of the paper without excluding important details. 

### **Practical motivations and examples.**
* We are happy to include additional examples and clarifications below, which should also be a minor change provided that we have the space to do so.
* We’d like to highlight several practical examples with important societal implications which can fall under this kind of framework:
    * **Healthcare.** In many healthcare applications, the source of truncation in data can arise from patient deaths, prohibitive costs, and other variables. For example, one can estimate the mean health care cost for patients with cancer, given that some patients cannot completely follow up due to costs or death. Here, the truncation set would be the patient covariates and realized health care costs; things lying outside of the truncation set would be the patient covariates and unrealized health care costs (which we do not observe). It may be reasonable to have an oracle provided by an expert (who can determine how many more visits and costs a patient with particular covariates should have had). 
    * **Discrimination.** In other settings with systematic bias, such as those considered by the Stanford Open Policing Project, we can consider the truncation set to be the realized outcomes across different groups of people. For instance, one could try to estimate search thresholds (probabilities) across different races given the realized data from traffic stops; here, the data lying outside of the truncation set could be considered the unrealized stops that would have occurred for each group if all standards for search are held equal. In this case, we may need to consider the oracle to be based on the given, realized data.
    * **Geographic boundaries.** In [31], the Chicago crime data was used to demonstrate the use of TruncSM because the city boundary was expressed as a polygon in $\mathbb{R}^2$. We can also use this data but deciding that a point is in the set or not is easier than describing the complicated boundary that one needs to calculate the weight functions in [31]. In addition we can handle more complicated cases that [31] cannot handle such as if the truncation set has holes or “cracks” in it as can be the case for complicated geographic boundaries (e.g., with islands, lakes) or political ones (e.g., result of gerrymandering).

* Regarding the membership oracle access to the set, we would like to clarify that in practice we may even know what the set S is (but which can be arbitrarily complicated or hard to describe mathematically), but we only need to be able to decide whether a point is inside the set or not as far as the algorithm is concerned. In contrast, e.g., [31] requires the set to be a Lipschitz domain and needs a description of its boundary to compute a weighting function. We would like to point out that integration and sampling are difficult even knowing S if it is very complex (e.g., not convex, not connected), and argue that membership oracle access to S is a weak requirement. Furthermore, the prior work [10] shows that without even membership oracle access to a set, recovery of parameters is (information theoretically) impossible from truncated data. 

### **Numerical demonstration.**
We had decided not to include numerical demonstrations due to:
* The scope of the paper is to provide provably correct algorithms for estimating exponential families from truncated data.
* Our theoretical results already take a lot of space to present and draw a complete enough picture on the provable guarantees that we can get. We believe that adding simple simulated experiments that just certify the theoretical results would add less value than making use of the space to add more intuition and details on the theoretical result which is the goal of this paper.
* While a real-world application, on the contrary to simple simulated experiments, would add great value to our results, we believe that such practical implementation will need a careful application of our algorithm and many details will depend on the domain knowledge of each particular application. We hence believe that such real-world experiments is a very interesting future direction but it lies beyond the scope of the current work.
* Numerical demonstrations are not always included in the prior literature and related papers in this line of work (e.g., [10, 12, 14, 26, 38]).

Meta-review: The reviewers have reached a positive consensus on this novel work in extending results in the Gaussian setting to exponential families. They propose to use projected SGD and analyze the algorithm adequately, and the contributions are relevant to the NeurIPS readership. The authors should consider the reviewer recommendations, especially with respect to numerical examples, in preparing the next iteration of the manuscript
Decision: Accept (poster)