Oracle efficient truncated statistics
Authors: Konstantinos Karatapanis
Vasilis Kontonis
Christos Tzamos
Venue: ICLR 2025 Poster (2025)
Keywords: truncated statistics
exponential family
statistical learning
Primary area: learning theory

Abstract: We study the problem of learning from truncated samples: instead of observing
samples from some underlying population $p^\ast$, we observe only the examples that fall in some survival set $S \subset \mathbb{R}^d$ whose probability mass (measured with respect to $p^\ast$) is at least $\alpha$.  Assuming membership oracle access to the truncation set $S$, prior works obtained algorithms for the case where $p^\ast$ is Gaussian or more generally an exponential family with strongly convex likelihood --- albeit with a super-polynomial 
dependency on the (inverse) survival mass $1/\alpha$
both in terms of runtime and in number of oracle calls to the set $S$.  In this work we design a new learning method with runtime and query complexity polynomial in $1/\alpha$.  
Our result significantly improves over the prior works 
by focusing on efficiently solving the underlying optimization problem using a general
purpose optimization algorithm with minimal assumptions.

Published as a conference paper at ICLR 2025
ORACLE EFFICIENT TRUNCATED STATISTICS
Konstantinos Karatapanis Vasilis Kontonis Christos Tzamos 1.4
Archimedes, Athena Research Center, Greece 2 National Technical University of Athens
University of Texas at Austin University of Athens k. ka karaaaaaanannaa wet.apaaanssathhaaaaaaaaa gr, vas .
utexas. edu, chtzamosedi..... uoa.
ABSTRACT
We study the problem of learning from truncated samples: instead of observing samples from some underlying population p- we observe only the examples that fall in some survival set S C Id whose probability mass (measured with respect p²) is at least a. Assuming membership oracle access to the truncation set S. prior works obtained algorithms for the case where p" is Gaussian Daskalakis et al. (2018) or more generally an exponential family with strongly convex likelihood Lee et al. (2023) - albeit with a super-polynomial dependency on the (inverse) survival mass I/a both in terms of runtime and in number of oracle calls the set S. In this work we design new learning method with runtime and query com- plexity polynomial in 1/a. Our result significandly improves over the prior works by focusing on efficiently solving the underlying optimization problem using a general purpose optimization algorithm with minimal assumptions.
INTRODUCTION
We study the problem of inference from truncated samples: assuming an underlying population over data in Rd the learner has access to samples from the conditional measure pd over some survival set S C 12d. This conditioning or truncation of the underlying population data may be the outcome of censorship, imperfect data collection processes, measurement errors, user preferences, etc. Inference from truncated data is central problem in statisties going back to fundamental works in the beginning of the previous century Galton (1898); Pearson (902b); PPaasso & Lee ( (1988)). Due to its practical importance, more recently, the problem inference from truncated data has seen significant developments with focus providing computationally efficient estimation algorithmss
Daskalakis et al. (2018); Kontonis et al. (0019) Ilass et al. 2020); Daskalakis et al. 2020b a 202
Lee et al. (2023).
In this work we consider the problem of fitting a parametric model to truncated data given oracle access to the survival set (i.e., the set of examples that are not truncated). In this model Daskalakis et al. (2018) was the first work that gave a computationally and statistically efficient algorithm for learning truncated Gaussian distributions with membership oracle access to the truncation set. More recently, the work Lee et al. (2023) extended those results and gave efficient algorithms when the underlying population follows an exponential family. In this work we study learning truncated exponential families with computationally and statistically efficient algorithms that perform well even when the fraction of observed data is very small (compared to the full population).
Learning truncated exponential families An exponential family po. parameterized by some k- k-dimensional vector 0 E ④ is density of the form (o(x)) = h(x) exp(0
A(0)), where 1(x)) Rd + [0, bo) a weight function, T(x) : Rd + R is the sufficient statis- tic, A(0) log (ʃ h()) exp T T(x))dd) is the appropriate normalization constant (aka the log- partition function). Given an exponential family pa and a survival set S, we define the corresponding truncated exponential family as r (x) po s Is (x())d,, where (x)) denotes the indi- cator function of whether belongs in S. Given samples from some truncated exponential family PsS the goal of the learner is to identify an approximation to the (unknown) parameter 0*, Given some target accuracy distance over the parameter space, i.e | 8_1 I e (parameter recovery) or over distributions, e.g., that the total variation distance between pe and pe- is at most e. The goal is to find good candi- date parameter 9 with as few (i) samples from p (ii) oracle calls to 1 (x) and (iii) computational resources possible.
O, the approximation guarantees for the learned 0 can either be in some

---

Published as a conference paper at ICLR 2025
The fraction of observed data equivalently the probability that sample from the underlying population pg- truncated, captures the difficulty (both statistical and computational) of inference from truncated data. More precisely, define survival set by the unknown exponential family po-. While previous works Daskalakis et al.] (2018); the Lee al. (2023) learning truncated exponential families have polynomial dependencies parameter dimension & and the accuracy parameter e, their dependency on the survival probability far from optimal. In particular, their runtime, sample complexity, and oracle calls all depend super-polynominn (i.e., (1/ax) (loy)1/(()))) to the survival probability a. In this work our focus will be to provide algorithms that achieve dependencies on the dimension k and accuracy e but also on the survival mass a..
Pg- (S) to be the probability assigned to the
Is there a computationally efficient algorithm that can learn truncated exponential families with polynomial dependence the survival mass 1/a? Can we get state of art dependencies dimension and accuracy parameters at the same time?
Aiming for algorithms with low sample-compp complexcomleexity is perhaps the most well-studied task from statistical perspective and is of great importance for virtually every inference task. We remark that in the context of truncated statistics getting oracle efficient algorithms is also important as the memhership oracle may correspond to costly or complex mechanism (e.g., we may need to find candidates to complete new questionaire, perform new physical experiment, etc.).
Our main contribution is positive answer to the above question by providing a new analysis of the truncated negative log likelihood objective.
1.1 OUR CONTRIBUTIONS
We first formally define the class of exponential family distributions that we consider in our work. Similarly Lee et al. (023), assume that the non-truncated negative log-likelihood of the ponential family is strongly convex and smooth as a function of the parameter 0. Given some ex- ponential family Pa parameterized by R the negative log-likelihood (NLL) over population distribution g is defined as follows:
(())
E [log pa (x)]- amo
In what follows we will refer to L as "noottrunccated. Moreover, for a truncated exponential family pe we define the following "truncated" version of the NLL objective as:
Cs(0)
E [log p (x)] [()) + log (SS). x--
(2)
Definition 1.1 (Strongly convex and smooth exponential families). We assume that L(0) is X- strongly convex and L-smooth as function of 0, i.e,
AI Cov I(=)
Remark 1.2. Lee et al. (2023) further places strong structural assumptions on Pa- In particular, that the underlying non-truncated exponential family is log-concave (ie., its log-density is concave as a function of x:) and also that the sufficient statistic T(x) is a polynomial function of x. As we will see our main learning result is quite general by providing a weaker learning guarantee (than parameter recovery) and therefore requires such assumptions priori. However, given those assumptions we can obtain similar guarantees to the prior works Daskalakis et al. (018)) Lee et al. 2203
We remark that, as observed in Lee et al. (2023) the above assumption is quite general and captures many well-studied exponential families such as Gaussians, Exponentials, Weibull, (Continuous) Poisson, etc.
Since our focus in this work is learning (as opposed to sampling from) exponential families, we treat the sample generation process as a black-box and define the following sampling oracle that returns samples from given exponential family truncated exponential family. For the truncated case, we crucially require that the learner must give the oracle some pe that assigns non-trine con-trivial mass to the survival set S. This is to ensure that our sampling oracle can be readily implemented via rejection sampling without a large number of rejected samples (that would in turn require a large number of calls the membership oracle to S). For example, assume that the survival set is S [0, and
2

---

Published as a conference paper at ICLR 2025
the ground-truth exponential family is normal distribution (not necessarily with unit variance) that assigns a mass to the set S. The learner can request samples from unit variance normal distributions whose means are roughly within O (Vlog(1/a) distance from O but not, for example, from a normal centered at -1/a which puts exponentially small (i.e.2-a(//a))) mass to S. Definition 1.3 (Sample Oracles), Given as input an exponential family pa E F, the noontrruncttd) sample oracle returns a sample po-
Moreover, given input exponential family po E F, the 3-truncuted sumple oracle over survival set S returns a sample x ~ Ph, provided that (S 2 3. In case this construint does not hold the behavior of the oracle is undefined.
Remark 1.4 (Implementing a 3-Truncated Sample Oracle). Given a membership oracle to the set S and a sampler for the non-trume con-truncated exponential family pe, one can directly implement B-truncated sample oracle by rejecting samples until one falls in S.
We now present our main result on learning truncated exponential families that requires roughly & poly(loo(1//)) a)) samples from the unknown truncated density pz- and makes & pooy (log(1/a) sample-one oralle calls to an a-truncated sample oracle of Definition 1.3) to learn a truncated density close to the observed truncated distribution in Kullback- -eibler (KI.) divergence.
Theorem 1.5 (Truncated Exponential Families). Suppose F is an exponential family whose negative log-likelihood (NLL), (()), satisfies the conditions in Definition 1.I Then, there exists an algorithm that uses Ô c log (2)) samples from po- makes Ö (2 log (2) calls to an M2(a)) sample or- acle (of Definition 1.3) runs in time poly(k, (k, 1/e, log( (p (pz) S c with probability at least 99%.
4 and computes an estimate 0, such that
We remark that the fact that our algorithm only requires an a-truncated sample oracle is what enables us to achieve a polynomial number of oracle calls to the membership oracle to S and significantly im- prove over the prior works Daskalakis et al. (2018) Lee et al. (2023) (that required super-pol super-polynomial oracle calls and samples). For instances where truncated sampling can be done more efficiently than rejection sample we even get logarithmic dependence on the mass of the survival set.
Observe that the algorithm of Theorem 1.5 returns a hypothesis Py whose corresponding truncated density p is close in KL divergence. Typically one asks for the learned density pe to be close to the target non-truncated distribution pě. that is to extrapolate and match the density beyond the region of observation given by the survival set S. We phrased our result in terms of KI divergence of the truncated distributions to keep the required assumptions on the exponential families minimal. In particular, by making the assumptions that render the parameter 0* identifiable (as in the prior works) one can readily translate the guarantee of our result to parameter recovery or (learning in KL or total variation) with respect to the target non- truncatedd density. We next present some new results for well-studied special cases of Definition 1.I that we obtain corollaries of Theorem 1.5
We first present our result for learning truncated Gaussian distributions. A truncated Gaussian den- sity is defined A p4, E, S) x 1. (1;)))((( E) where p E Rd, is its mean and Σ R its covariance.
Corollary 1.6 (Gaussians). Let q = N(u", "'n",E', 5) be a truncated normal density. There exists da an algorithm that draws M 2= pooyy (1/o)) samples from q, makes M M-pol poly(1/a)) oracle calls to the set indicator Ls(.), runs poly d, 1/a) and learns parameters fi, E such that dTv (N (R,, E) <
Our next corollary is on the generalization of log-concave exponential families that satify Defini- tion 1. and furthermore have log-concave density and polynomial sufficient statistic (see Lee et al. (2023).
Corollary 1.7 (Log-Concas Exponential Families). Fix O. Let F be a class of log-concave exponential families that satisfy Definition 1.1 and their sufficient statistic T(x) of each po E F
a polynomial of degree E that maps Rdth RR.. Let q = P.g be a truncated normal density in F. There exists an algorithm that draws M = poly (oooy(oog(//))) samples from q, makes M polyy(1 (1/)) oracle calls to the set indicator (-).), runs in poly (aly(M,, d, 1/a), and learns parameter O such that ||0 0* ||2 E and drv drv Po-) S c.
3

---

Published as a conference paper at ICLR 2025
Remark: We refer the reader to Appendix A for detailed discussion comparing our results in Corollaries 1.6 and 1.7 with the corresponding results in the literature.
1.2 OUR TECHNICAL CONTRIBUTION
A common challenge in the line of work truncated statistics is to ensure that during the opti- mization phase the parameters of the distribution remain within region that assigns significantly large mass to the survival set. This is important for many reasons, one being to ensure that gradients remain bounded and another being to ensure that rejection sampling works. As such all prior works restrict the optimization in custom regions of parameters that depend on the class of distributions one trying to learn. For every different setting, learning Gaussian distributions, product distributions on the hypercube, learning permutations and rankings, and log log-concave exponential families, differ- ent algorithms have been provided that focus on the specific intricacies of the setting e.g. discrete domain, polynomial features and so on.
Our main technical contribution is offering unified viewpoint for all those settings as exponential families over an unrestricted domain. Our key technical tool is establishing a very simple region for optimization that ensures the probability of the survival set is bounded and is given directly by the non-truncated loss of the model. More specifically, given an initialization Po. we define the following optimization problem that we aim solve via projected stochastic gradient descent.
min (0) s.t. ((0) < ((0)) + log AEB
Given an initial point 80 whose loss sufficiently close to the minimum non-truncated loss minøee L(0), any point 0 in the feasible region is guaranteed to assign least M(xx mass to the survival set.
Beyond our novel understanding of the optimization and sampling landscape, which enables signifi- cantly faster convergence, introduce much simpler algorithm that makes minimal assumptions about the setting and the distributions involved. Unlike previous works that simultancously bound sample complexity, query complexity, and parameter closeness, achieve tighter analysis by decoupling these terms. Specifically, we demonstrate the following:
We show that the dependence on samples from the true distribution is limited to the esti- mation of the mean sufficient statistic, which requires only a few samples. This is possible due to the good concentration properties of the truncated distribution, which behaves as subexponential distribution.
We adopt an optimization perspective, focusing on minimizing the given objective as ef- ficiently as possible, rather than directly recovering the underlying parameters. Our guar- antees are provided in terms of the closeness between the true truncated density and the learned truncated density.
Leveraging existing statistical results that relate the closeness of truncated densities to the closeness of parameters and non-truncated densities, we derive parameter recovery algo- rithms with polynomial dependence on the mass of the survival set.
1.3 RELATED WORK
The field of truncated statistics has long history, which finds its roots in Bernoulli's analysis of smallpox morbidity and mortality data Bernoulli (1660). and the early works of Galton (187));
Pearson (9922a): Pearson & Lee (1908a): Fisher 1931). Thus, we cannot do justice here and for an overview of the field we refer the reader to Schneider (1986); Cohen (2016); Balakrishnan & Cramer (2014). We also refer the reader Tobin (1958); Amemiya (1973 Hausman & Wise (1977); Heckman (197)): Maddaala (1986); Keane (1993); Hajivassiliou & McFadden (1998), and their references, for further work statistics and econometrics. There still remain numerous out- standing challenges, targeting density estimation, regression and classification tasks. Many recent works have focused on providing computationally efficient algorithms. There has been a large num- ber of recent works dealing inference with truncated data from a Gaussian distribution Daskalakis et al. 2018); Kontonis et al. (2019), mixtures of Gaussians Nagarajan & Panageas (2019), linear regression Daskalakis et al. (211)] Ilyas et al. (2020); Daskalakis al. (2020b), sparse Graphical models Bhattacharyya et al. (2021) or Boolean product distributions Fotakis et al. (2020). non-
parametric estimation Daskalakis al. (2021)
4

---

Published as a conference paper at ICLR 2025
The area of robust statistics Huber & Ronchetti (2009) is closely related to work, it also addresses the challenge of handling biased datasets with the goal of identifying the underlying data-gena generrtiigg distribution. Recently, there has been substantial theoretical progress in develop- ing computationally efficient methods for robustly estimating high-dimensional distributions in the presence of arbitrary corruptions affecting small fraction of the samples Diakonikolas et al. Charikar (Chrikar et al. (2017); Lai et al. (2016); Diakonikolas et al. );;17); Klivans et al. (2018); Diakonikolas al. (2019) Our work contributes this broader field of statistical learning, specifi- cally focusing on cases where certain impediments or biases are present.
One of the most notable works this area is Lee et al. 2023) which introduced efficient algorithms for learning from truncated exponential families. In the following subsection, provide detailed comparison between their results and our improved approach.
1.3.1 COMPARISON TO LEE ET AL. 2023
The work Lee et al. (003) presents framework for learning from truncated samples. We outline the key improvements of our method below:
Oracle Efficiency: A significant part of our improvement arises from requiring only a-truncated sample oracle access (Definition 3.1) throughout our algorithm, whereas Lee et al. (2023) requires access to a (ng(1/))___)))) -truncated sample oracle. Furthermore, any additional improvement on our result unattainable, as all parameters near 0* necessarily require access to an a-truncated sample oracle.
Parameter Estimation: In Lee et al. (002). convergence requires approximately a log(1/a) it- erations, whereas our approach achieves convergence in polynomial time relative 1/a. Both Lee et al. (2023) and our work, as shown in [Corollary 1.7] have iteration counts that depend on poly(1 (olyss/ mass). However, our advantage stems from being able to identify regions of higher mass more effectively.
Mass and Sample Complexity: The guarantees provided in Lee et al. (2023) concern areas of a log(1/a) mass, which can lead to inefficiencies. Our approach, by contrast, offers sharper covari- ance estimates for the truncated distribution, leading to initialization points that are closer to the true truncated parameter 0g = Eu-pj. (T(z)). While Lee et al. (2023)'s 's analysis requires remaining within ball of radius log( (og(1/)) around the parameter 0* effective learning necessitates both proximity to H within this radius and maintaining low negative log- ligeeloddoood (NLL) L(0). Had we used the covariance estimates from Lee al. (2023), our sample complexity would be poly(1/a), but by employing our improved estimates, we achieve poly(log(1//) (1))), matching the sample com-
plexity seen in Lee et al. (003).
While both methods similar initialization points, analysis demonstrates faster convergence. Specifically, we show that the initialization point in our method yields a lower starting value for C(0), ensuring the algorithm focuses high-mass regions more effectively. In contrast, Lee et al. (2023) does not capitalize on this aspect as robustly.
Initialization and Convergence:
Summary of Differences:
Sharper Covariance Estimates: Our approach guarantees that initialization starts within high-mass areas by employing refined covariance estimates.
Higher Mass Guarantees: We emphasize maintaining low NLL values, incrementally
broadening the search radius with controlled increases in NLL, which is critical for efficient
convergence. This perspective is not as effectively addressed in Lee et al. (2023).
2 PRELIMINARIES
A distribution belongs to the exponential family its density is expressed as
po(x) = /(()) exp(0 T(x)) A(0)).
For given set S. denote by pe (S) the probability that the measure pe assigns to S. The function h(z), often referred to as the weight function, is also known by other terms in the literature, such as the carrier measure.
5

---

Published as a conference paper at ICLR 2025
The parameter space of this family is defined θ {8 E R A(0) < 20), which is open set. After potentially reparameterizing, it is assumed that & and T(x) are linearly independent. This form of representation is known the minimal representation. Given a minimal representation, the function A()) is convex. The following properties of an exponential family are standard:
The gradient of A(0). VA()), ,, is the expected value of the sufficient statistic under the distribution: V V())) = Eawpp [T())]-
2. The Hessian of A(0), V (()) is the covariance of the sufficient statistic under the distri- bution: V (()) = Cov [T)))]
We include the definition of univariate sub-exponential random variable, which be used to define a corresponding class for the multivariate case by taking the supremum over the unit sphere. There are many equivalent definitions to choose from, but the most convenient for is by using the moment generating function (MGF). Namely,
Definition 2.1 (Moment Generating Function). The moment generating function (MGF) of a distri-
bution D, denoted by (t)., is defined as
MD(t)
E Te"),
provided this expectation exists. The function (t) is defined for all values of t in some interval containing
We provide a definition of the sub-exponential distribution, which we will rely on throughout. This definition is similar to the one in Vershynin (2010), with a minor adjustment to account for potential restrictions that arise when scaling moves us outside the natural parameter space @ of our model. Note that, aside from some scaling, the definition used here aligns with that in Lee et al. (2023).
Definition 2.2 (Sub-exponential distribution). Let x be a univariate random variable with zero mean. The random variable x is said to belong to the class SE(K,, B) if the following condition holds: E|cx I exp(K?X?), for all such that [>] S
The following proposition provides an equivalent definition for the sub-exponential class, adapted from Vershynin (2010) with slight modifications to suit our needs. However, since the proof remains unchanged, we omit it.
Proposition 2.3 Suub-exponential distribution). Let x be a univariate random variable with zero mean. Fix parameters K, > 0 for 1,2, and 3 O, such that E SE(KK,B). Then, the following two properties are equivalent. Additionally, the quantities max(K1, 3) and K2, which appear in the properties, differ by universal constant.
(a) The moment generating function (MGF) of x satisfies
Elexp(Xx)] exp(K?>²)
for all X such that |>| 3/- (b) The moments of x satisfy
E [E|>)))> < K2p
for all p 1.
This class of functions is typically associated with concentration inequality. The use, which can also be found in Vershynin (2010), is as follows:
Fact 2.4 (Bersttei'' Inequality). Let .1,-.. EN be independent, identically distributed, mean- zero, sub-exponential random variables belonging in the S SF KT, B). Then, for every 2 O, we have
EN
N
t²
t
Pr
Σ
x
21
S
2xep
-cN min
(Hax
max K1,
where is absolute constant.
2.1 TRUNCATED STATISTICS
We begin by defining the notion of a truncated distribution. Namely, let p probability density function on Rdd, For given set S C IR, let ps be the conditional distribution of ~ p given that
S, L.c pd (x) 1(z)) Note that the relative density is ps(z) Ls(w) Po(S)
p(#)
((S)

---

Published as a conference paper at ICLR 2025
In the context of truncated statisties, we engage with oracle, denoted by Ms(x) (z). which represents the indicator function of the set S. This setup is prevalent in scenarios where direct access to the set S is unavailable, yet mechanism exists to verify the membership of elements within S. This method allows for the indirect exploration and analysis of the set through conditional access provided by the oracle.
Non-truncated and Truncated NLL Given exponential family pe parameterized by 0 R& the negative log-likelihood (NLL) over population distribution g is defined as follows:
( =
E [log pe (x)].
(4)
In what follows we will refer to L as "non-truncated". Moreover, for a truncated exponential family po. such that the support of q is contained in S, we define the following "truncated" version of the NLL objective as:
(s(
E [lo pá (x) [()) + log PS(). x-x
(5)
The gradient and Hessian of L.(-) are given below.
VoLs(0)> = E Ea-p [[x)] - Exng [Tx)], ViCs(() = Cov ampp [T())]
LEARNING TRUNCATED DENSITIES
In this section we prove our main result, namely an efficient algorithm for learning truncated expo- nential families.
Definition 3.1 (Sample Oracles). Given as input an exponential family E F, the (non-truncated) sample oracle returns a sample po-
Moreover, given input exponential family po F, the 3-truncated sample oracle over survival set S returns a sample x ~ Po. provided that (S 2 3. In case this constraint does not hold the behavior of the oracle is undefined.
Remark 3.2 (Implementing 3-Truncated Sample Oracle). Given membership oracle the set S and a sampler for the non-truncated exponential family po, one can directly implement B-truncated sample oracle by rejecting samples until one falls in S.
This oracle enables us reduce the inference problem to an optimization that use the gradients as rewards.
Theorem 3.3 (l (Terrning Truncated Exponential Families), Fix > 0. Let F be an exponential family with sufficient statistic T()) such that for any po F, XI Cov (T(:)) < LT. Assume sample access to an unknown distribution pa- E F truncated with survival set S of mass a > 0, and an
sample oracle Q over S. There exists an algorithm that uses Ö ( log (2)) samplex from vg., makes Ö ( log (2)²) calls to the oracle Q, runs in time poly (k: 1/e, log( and computes an estimate 0, such that KL l1ng) S e with probability at least 99%.
Roadmap to the Proof: To prove Theorem 3.3 we proceed as follows:
1. Setup and Definitions:
Our learning algorithm outputs ê by performing PSGD Theo- rem 3.12) starting from an initial point 6n over domain D. The key properties are that E and, for all 0 E D, the bound Praepo [ar E S] 2 -2 holds.
2. Main Argument: The parameter Op serves
good approximation of Eg-pg. [T())] This approximation is achieved through a collection of smoothness results, specifically Lemma 3.5 Lemma 3.11 and Lemma 3.7 This good initialization crucial for defining
D 10: 2(0) ((0)) < () with the necessary properties. As shown in Corol-
lary 3.9 initialization from a point with sufficiently low loss L(0p) < L(80) + allows the
application of Corollary 3.10 where 6 is defined in Corollaryy 3.10
3. PSGD Specifications: We apply Theorem 3.12 with f = Ls. The smoothness parameter Ls is L(1 + log" (1/a)) over the domain D. owing to the smoothness of the truncation (Lemma 3.5) and the sufficient mass within D. Similarly, shown in Lemma 3.13. the gradient variance of Ls is of order ITT log"(1/o) D.
7

---

Published as a conference paper at ICLR 2025
can demonstrate that an tranttrunetedd sample oracle Q over is feasible. Note that since the parameter 6* assigns mass a to S. we cannot hope to achieve something more efficient than (((a)-trunntttdd sample oracle. The main idea for this improvement in Theorem 3.3 is to incremenaally expand the exploration domain to avoid overshooting and inadvertently ending up in low-mass region. We include the theorem statement below; for a detailed proof, along with the necessary apparatus, look at the appendix (Appendxx/ppdiixxxx C
Using the same techniques in Theorem 3.3
Theorem 3.4 (Learning Truncated Exponential Families ). Fix > O. Let F. be an exponential family with sufficient statistic T() such that for any pe E F. Al = Cov [x)] = LL. Assume sample access to an unknown distribution po- E F truncated with a survival set S of mass & > 0, and an ((a))--runcated sample oracle 2 over S. There exists an algorithm that uses 0 ( log (t)
samples from v makes Ö ( log (2)²) calls to the oracle Q, runs in time poly (k. 1 1/e, log( )) and computes an estimate 0, such that (T l1rg) S c with probability at least 99%.
3.1 FINDING A GOOD INITIALIZATION
To demonstrate that a good initialization be found with Ō (.5 log (2)) samples from p leverage the concentration properties of the distribution pg.. This is threefold process, and our end goal is to find in which sub-exponential class p belongs. In order to accomplish that, we have
to bound Cov x-pp (T(X), and in order do that we need || [T(x)] rll2 x
log po(())-
The next lemma will deal with those two latter stepping stones.
Lemma 3.5 (Moment preservation after truncation). Assume that Euppo [(x)]
14, Cov (T(x)) 1 LI. and po(S) > O. Then, [Eggpg [T(x)] - 1ll2 S log ppo(S) Similarly, we have the following covariance estimate: Cov z-g (T(x)) =
(log² (0(10²)) (po(s)) + +L)
The previous lemma gives us a bound on how much the smoothness is affected by the trunca- tion. Hence. tighter bounds guarantee needing fewer samples since the truncated distribution enjoys stronger concentration properties. The analysis is achieved by performing a worst-case analysis.
Next, we see how truncation affects the sub-exponential property that the non-tre un-trunnattd distribution possesses. For the proof we refer to Appendix B
Lemma 3.6 (Truncated density is sub-exponential). Let F. be an expomential family with sufficient stutistic T()) such that for any po E F. we have AF I Covz=po [T())) 3 LI. Let x follow the truncated distribution: p (x) = pola)lg(z), where pa(x) = hs(a)) exp(0
As(O)) and Po( the normalization constant. Then, the random variable T(x), under this truncated distribution, sub-exponential, denoted SE(K2, 3),, with parameters K² (1 + log (1/a))L as K appears in Definition 2.2 and 3 is the reciprocal of the largest rudius of the ball B(O,r). centered that is contained in B(0, r) C O.
Po(3)
Now, we have developed all the tools necessary to find a sharp estimate of the samples needed for the empirical truncated distribution to approximate its mean.
Lemma 3.7 (Empirical estimation of the truncated sufficient statistic). Fix e > O. Let pa- be some exponential family such that pe- a. Moreover, let 0's = =Eg-pg. [T(x)] be the expected
sufficient statistic of the truncated exponential family ps. Moreover, let Ô = N Ein, T(x(() be the corresponding empirical statistic for x!1), ,e!),.... (N) (NN) i.i.d. samples from po.. Using N =
O &4 log (1) log" (2)) samples, with probability at least 1 - 8, it holds ||0 0g < E.
Proof. Our estimator is Ô 1o E T(x:), where x, pg. We have shown that, for any unit vector u, Y, u TTT( u Ex,rpg [I():)] belongs the sub-exponential class with K²
O (T. + log 2 (2)) We fix 1 0, now by using Bernstein's inequality, as seen in Fact 2.4
obtain
S Po-
1
Σ Y3
21
< 2exp (c.N min
12 max² B) max(K K, ) =2exp (-c )
1
No² (-cmax? B)
N
i=1
8

---

Published as a conference paper at ICLR 2025
Since the previous inequality holds for all u, and by the superposition property of sub-exponential random variables, we obtain the previously mentioned bound for the norm, namely:
p (11- Es Exppp (T()))) 2t) - exp
(-c maxx (K,
N
Since b, T. is constant
independent of Therefore, for N 2 O ( log" (a) log (t)),
we
have the following bound:
O (log² (a)) ps (10- E Exirpg (T(x)))
max? (K, B)
we get,
8.
3.2 THE FEASIBLE REGION AROUND INITIALIZATION
To ensure feasiblity we will use the following simple observation.
Observation 3.8 (Mass along the sub-level sets). Let pa be some exponential family and define 6' be minimizer of the constrained objective {ming Cs(0) s.t. [(0) S L} for some L. For any such that (()) S L, it holds Pro[S] 2 Pr (xp((((0)) L())).
Proof. This holds as L6) S (o) which directly gives the required bound.
Using Observation 3.8 we readily obtain the following corollary.
Corollary 3.9 (Mass monotonicity along sub-level thresholds). Let 0" be the minimizer of the trun- cated NLL objective Ls for some exponential family pa- Denote by a Prg- [S] the mass as- signed to the survival set S. Define the following constrained optimization problem: {ming (o())
s.t. ((0) & L} and denote by 01 its solution with L L1 and by 02 its solution of the same opti- mization problem with L L2 where L2 > L1-
1. (Monotonicity) The mass assigned to S is decreasing Pro,[S] [S] 2 a.
function of T.: Pro, [S] >
2. (Exponential decrease) The mass assigned to S by 02 drops exponentially fast, i.e., it holds that Pre,[S] [S] < Pre,[S] e (12--11)
Proof. Notice that by definition of 01, On E {ming Ls( s.t. L(O) T22 Hence, Pro, [S] 2
Pro [S] exp( L - In) 2 Proy [S]. It only remains to show that Prog [}] 2 a. Since, the {mina (s( s.t. C(0) < L2] decreases s.t. (()) I C(0")}. Which means for 0' that is the solution to a constrained optimization problem with lower L = L2, we have 0' E {Ls(0) s.t. s.t. < L()")). Hence,
L2 increases, L(0*) {ming (s)
L(0) <
0o} = min
< (()*) and from the previous part this implies a = Prg- [S] S Pro [S]. Hence, we con- clude.
Given the exponential decrease, i.e. Corollary 3.9 we obtain the following corollary. Which is ensuring that our initialization PSGD close in LLN distance, and that all our parameters inside our projection domain give poly(1/a)) to the survival set S.
Corollary 3.10 (Feasibility of 09), Suppose that 0 is 0 = Egppy. (T(x)). Then, L(O*) s
((80) + log (2). Furthermore, if for any 0 such that C(0) I ((80) + log (2) + e, then (S) 2 Poo (S) (t 2 a2e-
Proof. From Corollary 3.9 holds that Pao (S) > a. Hence, by the exponential decrease, provided by the same corollary, find that L((0) < ((00) log (2). The second part is an immediate consequence of the Oheeeesrvvttion 3.8
3.3 PSGD CONVERGENCE
We prove the following lemma show that the truncated densities are sub-exponential, see Ap-
pendix B
Lemma 3.11 (Sub-exponenill Property for the Truncated Distribution). Let x follow the truncated
distribution: p (x) pa(=)]s(() where pa(z) h(x) exp(0TT(2)) A(()) and Pra [x E S
PS)

---

Published as a conference paper at ICLR 2025
is the normalization constant. Then the random variable T(x) under this truncated distribu- tion is sub-exponential. More specifically. it belongs to the family SE(K?, where K2 L + log" (2) 1-1-------- inf rya + (
The result for PSGD we will use is the following. Its proof is standard, see, e.g. Shalev-Shwartz & Ben-David (2014) or Appendix for a proof.
Theorem 3.12 (Convergence of Projected Stochastic Gradient Descent). Consider the Projected
Stochastic Gradient Descent (PSGD) algorithm for minimizing a convex function f over a convex set K. Assume the following:
1. Lipschitz Continuous Gradients: There exists a constant M > 0 such that for all and y,
(V)( V S M|I - y
2. Bounded Variance: The variance of the stochastic gradients is bounded, i.e., there exists constant 6² such that (1]]) S 62,, where g0 = f(x).
Then, for i
El=r w where the {w(t)) are generated by the PSGD algorithm with step size [1w/ - II
he- ME it holds E [[w")))[(w''>> S
2MT +
12M"T
To apply [heorem 3.12 first show that our unbiased gradients have bounded second moment. The proof can be found in Appendix B
Lemma 3.13 (Bounded variances of stochastic gradients ). Let T(z) : Rd + RR be the sufficient statistic of truncated exponential family pÿ.. We have that v T(z) -(=)-T(a)) where z ~ p and Pø- is unbiased estimator of V (0). Moreover, has bounded second moment, namely,
E B[[a||2] = E Ezppă
E Egnpi
S kL log (1/a).
3.4 THE PROOF THEOREM 3.3
We are now ready prove our main result. Apply Theorem 3.12 (PSGD) the optimization
problem Equation (3) for f Ls and w(O) = 8.. with projecting region D {0 [()) s
(())) + log J. Here, Oo v EN T(x:) for N 2 O k1, 80_ E Ezpp. [T Then, by applying Lemma 3.7 with
2 log (1) log" (2) We also set
f. obtain ||0 10 < 1.-
Observe now, that by the L smoothness L and the fact that VL())) = 0, we have the bound [|V](0)]| < L for all 0 E {0: ||e 801 I r}. hence (C(0)) - C(0 S.
Furthermore, by Corollary 3.10 we get 6" D C {0: L()) (())) I log( [ + c) and po(S) 2
a²e for all 0 E D. By strong convexity of L(0), we have that 1100 0- 2 < O (log (2)).
Hence, Theorem 3.12 in our setup gives an upper bound
C [og(l1/) Hlo
bmT
So, for
6C'log (o (1/a)(L (1g)a))))))) (1/a))²+a +r² Theorem 3.12
gives us an 0 such that [f f(0)) Sc.
(og=
From Markov's inequality, we get Pr [T(0) ((0)) 2 3e] =
We can easily amplify this probability by repeating this process independently and hence obtaining a sequence of 01, 01,02.... .2....,6p, Fm and then choosing = argming, f(O.). Set 0 := and observe that
Pr [(0) f(0")= 2 3e < (1)
Hence by choosing m 2 log(ō)/ log(1 113), we obtain á that
satisfies Pr [()] f(0)) 3e 8. To accomplish this, however, need access to the value of L3(3;) = L(s,) + log (r.., (S)) Since we have access to S only through its oracle, in order to calculate Prw,[S], we use concentration for a Bernoulli random variable. More specifically, by Hoeffding's inequality, we need O ( log (+)) samples to estimate log (Præ, [S]). e-close with probability at least -
Therefore, obtain å with high probability that achieves high precision, namely Ls( (s())) < e or equivalently KL (pn <
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work has been partially supported by project MIS 5154714 of the National Recovery and Re- silience Plan Greece 2.0, funded by the European Union under the NextGeneeaaionfFU Program.
REFERENCES
Takeshi Amemiya. Regression analysis when the dependent variable truncated normal. Econo- metrica: Journal of the Econometric Society, pp. 997-1016, 1973.
Balakrishnan and Erhard Cramer. The art progressive censoring. Springer, 2014.
Daniel Bernoulli. Essai d' d'une nouvelle analyse de mortalité causée par la petite vérole, et des avantages de l'inoculation pour la prévenir. Histoire de l'Acad., Roy. Sci.(Paris) avec Mem, pp- 1-45, 1760.
Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas. Efficient statistics for sparse graphical models from truncated samples. In International Conference on Artificial Intelligence and Statistics, pp. 1450-1458. PMLR, 2021.
M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. In Proceedings of STOC 2017, pp. 47-60, 2017.
A Clifford Cohen. Truncated and censored samples: theory and applications. CRC press, 2016.
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Effi cient statistics, in high dimensions, from truncated samples. 2018 IEEE 59th Annual Sym- https:
posium on Foundations of Computer Science (FOCS), pp. 639-649, 2018. URL
7/api. staii.ssmanticscoolla htt.://aaa..acaccoooss::::::
Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Computa- tionally and statistically efficient truncated regression. In the 32nd Annual Conference on Learn- ing Theory (COLT), 2019.
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Compu- tationally and statistically efficient truncated regression. ArXiv, abs/2010. 122200000.00,, 12000, 2020a. URI. httpss:/eap www.eteett.... icschol ar. wwwparrrrgooooouooeeeeeeo 147702805
Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis. Truncated linear regres- sion in high dimensions. Advances in Neural Information Processing Systems, 33: 13338-177377 2020b.
Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, and Emmanouil Zampetakis. A statis- tical taylor theorem and extrapolation of truncated densities. In Conference on learning theory, pp. 1395-1398 PMLR, 2021.
I. Diakonikolas, D. M. Kane, and A. Stewart. Robust learning of fixed-structure bayesian networks. CoRR, abs/1666.07388. 2016.
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference Machine Learning, ICML 2017, pp. 999-1008, 2017.
I. Diakonikolas, G. Kamath, D. Kane, J. Li, Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, JCMI. 2019, 2019.
RA Fisher. Properties and applications of hh functions. Mathematical tables, 1:815-852. 1931.
Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Efficient parameter estimation truncated boolean product distributions. In Conference Learning Theory, pp. 1586-1600. PMLR, 2020.

---

Published as a conference paper at ICLR 2025
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-315, 1897.
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, 02:310-315, 1898. doi: 10. 10.1098/rspl.1899 1897.01 15. htRp:
org/ 1098/ rspl 1897. 0115
Vassilis A Hajivassiliou and Daniel L McFadden. The method of simulated scores for the estimation of ldy models. Econometrica, pp. 863-894 893,89,,77 1998.
Jerry A Hausman and David Wise. Social experimentation, truncated distributions, and efficient estimation. Econometrica: Journal of the Econometric Society, pp. 919-938, 1977.
James J Heckman. Sample selection bias specification eroor Econometrica: Journal of the econometric society, pp. 153-161, 1979.
P. J. Huber and E. M. Ronchetti. Robust statistics. Wiley New York, 2009.
Andrew Ilyas, Emmanouil Zampetakis, and Constantinos Daskalakis. A theoretical and practical framework for regression and classification from truncated samples. International Conference Artificial Intelligence and Statistics, 2020. URL https: api htttps://ap..smaatteet aemnmaiannnccc
Axg/CorpusID:: /Cooppsss0:2000555500 220095790
Michael P Keane. Simulation estimation for panel data models with limited dependent variables. Elsevier, 1993.
A. R. Klivans, K. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, COLT 2018, pp. 1420-1430, 2018.
V. Kontonis, Tzamos, and M. Zampetakis. Efficient truncated statisties with unknown truncation. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1578- 1595. IEEE, 2019.
K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proceedings of FOCS'16, 2016.
Jane Lee, Andre Wibisono, and Manolis Zampetakis. Learning exponential families from truncated samples. In seiethh Conference on Neural Information Processing Systems, 2023. URL https://openreview
forum? leeee/ooouumm1dPPxceeeeeee
Gangadharrao S Maddala. Limited-dependers and qualitative variables in econometrics. Cambridge university press, 1986.
Sai Ganesh Nagarajan and loannis Panageas. On the Analysis of EM for truncated mixtures of two Gaussians. In 31st International Conference on Algorithmic Learning Theory (ALT), pp. 955-960, 2019.
Karl Pearson. On the systematic fitting of frequency curves. Biometrika, 2:2-7, 1902a.
Karl Pearson. On the systematic fitting of curves to observations and measurments: Part ii Biometrika, 2(1):1-23, 1902b.
Karl Pearson and Alice Lee. On the generalised probable error in multiple normal correlation. Biometrika, 6(1):59-68, 1908a.
Karl Pearson and Alice Lee. On the generalised probable emor in multiple normal correlation. Biometrika, 6(1):59-68, 1908b.
Helmut Schneider. Truncated and censored samples from normal populations. Marcel Dekker, Inc., 1986.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
12

---

Published as a conference paper at ICLR 2025
James Tobin. Estimation of relationships for limited dependent variables. Econometrica: journal of the Econometric Sociery, pp. 24-36, 1958.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices, 2010.
A COMPARISON WITH PREVIOUS WORK
In this appendix, we present the main results from prior research on learning truncated distributions, specifically those Daskalakis et al. (2018) truncated Gaussian distributions and LeeLee et al. (2023) on truncated exponential families. We then compare these results with ours to highlight improve- ments in oracle complexity and dependence on the truncation parameter
A.1 RESULTS FROM DASKALAKIS ET AL. 2018
Daskalakis al. 2018) investigated the problem of learning a Gaussian distribution truncated to measurable set. Their main result can be summarized as follows:
Theorem A.1 (Learning Truncated Gaussians Daskalakis et l 2018)). Let q = -N E",)) S) be Gaussian distribution truncated to measurable set S C IR, with mean μ¹ E RR and covariance Ex E Raxd, Set a = PP=NN( [-) (xr E S). Then, there exists an algorithm that:
Requires a number of samples M = L {poly(log(/aa)) and makes M a polyy(oo(((/)))
oracle calls to the set indicator s-)))
Runs poly(A, d, -pool((lo({//a))
The algorithm computes estimates ja and E. such that, with high probability,
(Tv(N((P,
E²)) <e
The super-polynomin dependence on 1 arises because the mass assigned to the truncation set S within the optimization domain used in their analysis becomes super- saper-polynomially small.
A.2 RESULTS FROM LEE ET AL. (2033)
Lee al. (003) extended the analysis to general exponential families truncated to measurable set 5. Their main result as follows:
Theorem A.2 (Learning Truncated Exponential Families Lee al. (2023)) ). F. be class of log-concave exponential families that satisfy Definition 1.1 and their sufficient statistic T(x) of each pe F is a polynomial of degree that maps K to R" Suppose pa- is the target distribution, and q D-- is its truncation to set S. Set P Parppo [x E S). Then, there exists algorithm that:
Requires a number of samples M poly(log(1/o)) and makes M poly(o log(1/o))
oracle calls to the set indicator s.(.)
Runs in poly(M, M, k; a- log(1/o)).
The algorithm outputs an estimate â such that, with high probability, drv (pv (p S
Again, the super-polynomite dependence on 1 is due to the small probability mass assigned to S, which adversely impacts the optimization landscape.
A.3 COMPARISON AND DISCUSSION
The primary difference between these prior results and our work lies in the dependence on the truncation parameter In both Daskalakis et al. (2018) and Lee et al. (2023). the algorithms require a number of oracle calls, and computational time that are super-polynomial in 1. This is mainly because the probability mass assigned the truncation S as becomes small negatively affects the smoothness and strong convexity properties needed for efficient optimization.
In contrast, our algorithms achieve similar estimation guarantees while requiring a number of calls to the indicator of the truncation set 1g that depends polynomially on 1 Specifically, we ensure that for all parameters 0 in the domain D of our algorithm, the probability mass assigned to S satisfies
PP Papppl (2r S] poly (a:).
13

---

Published as a conference paper at ICLR 2025
This lower bound prevents the mass from becoming negligibly small as decreases. Consequently, the strong convexity constant of the truncated negative log- -eelikelihood (s()) (Equation (3) depends polynomially on a, enabling efficient optimization.
A.4 CONCLUSION
By carefully analyzing the distribution of the mass assigned to the truncation S, we have devel- oped algorithms that reduce the dependence on a from super-polynomial to polynomial in a. This improvement makes methods more efficient for small values of by optimizing the computa- tional landscape and reducing the complexity of implementing the required oracle.
B OMMITED PROOFS
B.
THE PROOF OF LEMMA 3.11
The truncated exponential family distribution be written
pg (x) he (z) exp(0 T(x) - As(O)),
where:
hs(r) (x)) is the modified base measure, zero outside the set S, As( A(0) + (S) the modified log-partition function reflecting truncation.
Define the truncated log- see-pattition funetion:
As(O) log [ h(x) cxp( T(x)) dr.
The expected value and covariance under truncation are given by:
VAs(0),
Cov Cov 1m (T(z)) V As))
Consider the moment generating function (MGF): To simplify the calculations deal with the push- forward measure induced by the mapping x + T(x) and we denote the corresponding density as p (t) hs(() exp(Ot As())).
Erigg [e (1- (t-Ps)] = ~uu ps Zs(ru +
Zs(0)
and to establish subexponentiality, we need to establish an inequality of the form:
7s 7s(ru + 0) -- < TRk
(s(
for y such that both 0 + yu and 0 + yu belong in our parameter space. Using the (L + log" (2))-
smooth property of (0) we find:
As(ru +0) As(O) S qu ps + L + log² (2)) 72.
Hence,
Ei-pg le (e-0" (1-ws)] = To us Zs(ru + < exp g2 (L L log²
Zs(0)
Therefore, T(x) is SE(K2,9) with
( ) g- min (sup(y qu + O), nuu + + log?
K² T. 1og
14

---

Published as a conference paper at ICLR 2025
B.2 THE PROOF OF LEMMA 3.5
First, for convenience, suppose that (S(S) To establish the bound, we will show that for any vector u E RR, the following holds:
B E lu [x)) Ez-po Ju (T((())] 0o log (2)
Indeed, for all vectors w and all norms || |l. there is a linear functional f such that f(w) = ||||| Since every linear functional is of the form proper u, we can get bound for any norm that may be of use.
u²" w,
be sure that, after choosing the
Define CR = {x Tx) > R}. We change the measure the first expectation, so we can compare them more readily, namely,
E xx (u T(x)]
Exaopo
[IT Tx:)ll
p² u T(x))
Eampe
-Ezuno [u"T(x)]
p
Exmpp
1s - a
" T(x))
E Eg-ps
1s - a
" TT()
+ Ex
1g - a
u (TT(()lca")
1g - a
1g a
E Em-pa
" T(x)
Exeop
R
1s a
1s
E Papps
" TT()ll
E Pewps
R
1s a
Ev
[u" [x')()) + Ex
R
Exnpo (x"T(x)lcn)) +R
a
It remains to work on the term Exupo [a:)(a))
Ez-po [u TTx)(c Exapo
u [²T(()]Ca Po(CR)
Exrupo
[log(exp n² T()) (C
= log
Exwpoleep R T(=) Po (CR)
< log
Pempolexp " TT (C
(C(R
< log Ex lexp " T Po (C)) Po(CR)
< log
E EErno /exp u ((x) po (C log (RR)) (CR)
We switch our focus to the term log E Eawpo /cxp u TT:)
log (Erwpo /exp T(())o())))
< log (Earpo [exp((u Egrps (cx)l)
S log EEnapy [exp(2u"T(x)))) log (cw))))
< log (En~po (xx((u"TT(z))] log (po(CR))
E (T(a))) log (Cn))
$ log exp 4L + 22
<
(4L + 2u Emapp (T(x))) log (po(CRR)
2
15

---

Published as a conference paper at ICLR 2025
For convenience, set po(CR) c(R), and by putting everything tögether, obtain
1
E
(u [u Tx))] E Ex [u" Tx))]
(4L + 2u Ep. (x)))) log
2a
log (og(c(()) R)) of Rt) + R
Since (x) is subexponential, we have that Po(CR) S C cexp(-cLR). Where the constant C' == O (log Ex-pe [p(x)]), which is paid since p(x) is not centered. Substituting back into the original inequality, we get bound of the form
o exp exp (-cb (xp( R2) - R.
We used the big O notation to suppress any constants, which we may eliminate by paying only lognssattn Therefore, since the above holds for all R. we may minimize it or choose R that is satisfactory for our purposes. We may choose R = O(log(1/a)). Therefore,
0
- e-pL R) + R 0
0108 (log _ ))
so we conclude the first part.
For the second part similar analysis. To establish the bound, we will bound the correspond- ing quadratic form the matrix Cov z~pp 2 (Tx))). suffices to bound
Bapp
[u T(x) TT (x)u - Ezapo (T'((x) T T (x)ul
To simplify the expression set n² T(x) p(x)) where p(x) is polynomial of degree kt
Exzpğ (uTT(() TT (x)u]
Expep
[u (Tx)) TT' (x))
Exupp
[p2]
Ezzpo [p (x))
1 a
E Egpup
p² (x)
1g - a
(11s- R²
E Ezopp
p² (2:)
+ Exapp
E Eappo [p2cc]] + R²
The term Ex-pp 1c) can be bounded using Cauchy-Schwaer follows
E Egeoo (x) S Egaep (x) Ezwpo [lcl & C Cexp(-cLLR
where C a constant. To obtain the constant C. we use Proposition 2.3 (b), which gives
2.3((b,,
Ex-pe [p'] S (4K2)*
Substituting back into the original inequality, we get bound of the form
o (
exp
cL RR
2R
We used the big notation suppress any constants, which may eliminate by paying only log(con connstaat.) Therefore, since the above holds true for all R, we may minimize it or choose an R that is satisfactory for our purposes. We may choose R = O(log" ((lo))(L/a)) Therefore,
( exp (-ch.R)
cl. .R.)
R² o Loog 1 )2))
conclude.
16

---

Published as a conference paper at ICLR 2025
B.3 THE PROOF OF THEOREM 1.5
Proof. We aim to show that the sequence (w(+) generated by the algorithm converges to optimal point w².
We use the non-expansiveness of the projection operator. Namely, the projection operator onto convex set is non-expansive, meaning for any and y,
[[]x(x>) [xx s || -ll-
Using the convexity and smoothness properties, and the non-expansiveness of the projection opera- tor, we can see the progress achieved after each iteration.
[1 w='1² (t hig w w²1
Expanding the right-hand side, we get:
II w= 11 S [||u(t=1) 112 2g wit w²) + 11
Since f is convex, we have: f(w(l-1)) - f(w") S (V w((111) - w")
Taking expectations conditioned on w(t-1), and noting that E [9 /wolt=1]] v)(wo((-1),, we
get:
E f(w(t-1)) - f(w")
(V((w(t-)) (1--1) w²)
Combining everything together, taking expectations, and summing over / = to T.
E [(ult-)))] Tf((w)
(V w((1-1) w²)
E
T
(0) (0l1--1) - -n0>>
[=1
1 T
[1o(c_11) - -0- 1l:(00 - w 10]
+ +hī E (11))
E
2L t=1
Using the boundedness of E [1]g(*) [2]]
$ b, and that h4
1 have:
b 1
b
π
112 h
1212
12
So.
T
||w|(0)
w 1|2
bn
E Σ
[()((=1))]]
-f(w)) 5
2LT
12L2T
Finally, from convexity we obtain
1 T
Σ ((llt-1))
[colt-11)
E
<
E
T
t=1
hence we conclude.
B.4 THE PROOF OF LEMMA 3.13
Let v denote the output of the rejection sampling procedure to find an unbiased estimate of the gradient. We have
|||
E
E
[[[(()) - [[] [T]
z=pl a-pp-
E
E
[ ||)
zmpp moup'
ET())
| [T()) [ E Eg-pg
[x))
17

---

Published as a conference paper at ICLR 2025
(1 log (1)) log (
$ k(l + log (t)) kI. 0
Since,
E po
[T()]]
E Ex-pg
[T))]] [VL5((0) VLs(0*)I
(( [L+ (1))) |10, - -81l
00
(
0 x-1 T.+ 1o++ log
(1)) )) log
where we used Lemma 3.5 in combination with the assumption of strong convexity of (()) and the upper bound of the smoothness of (0).
C PROOF FOR THEOREM 3.4
To minimize the number of queries the oracle, our approach cautiously progresses towards the optimal parameter 0* Specifically, we incrementally explore increasingly larger convex sets, ensur- ing each set assigns sufficient probability mass the set S. To this end, for given threshold L, formulate and solve the following constrained optimization problem:
0- = arg min (6)
(6)
s.t. (()) S L
Proposition C.1 (Progress of the Truncated Loss along Sublevel Sets). Suppose 0% is the minimizer of the optimization problem {ming Cs(0): s.t. L(0) I for L == L' + m, where E N. More- over, let be the smallest integer, such that 0 is the solution of the same constrained minimization problem for L = L' + Then, for S -
(a) Ls(0")) - (0(00+1)) 2 (=(0m)-Co(0")
1-m
(b) so, particularly, for all m, ((() - L.s Ls(00 2
L8(6", --
log(
Proof of Proposition C.I
-0-0- or Proof. Suppose T a
Then, the functions
g(t) Cs(O%, + tu), w(t) = L(0T, + tu),
are convex. Furthermore, the functions g and w are decreasing and increasing, respectively, for t [0. ||e- 8% l22] Denote by ty the points such that w(tx) L' + mb kb, where k O,..., I lo and f = ||0- 4r lg. Since the function w is convex and increasing, the length of the line segments [4-11, 4x] is decreasing. Also, since g is convex and decreasing,
((vx) g(ta-1) S 1((2-1) g((x-2), for 1, I.....l
Consequently,
Cs(0m)) - Ls(00) = g(0) - g(110" - 12)
1-m
Σ (g(ti-)) g(t:))
==1
$ (1 - m) (g(40) g((1))
< (1 m) (fs( - L (f
Hence, we divide by m and obtain the first part. Also, since m S log (2), we conclude.
18

---

Published as a conference paper at ICLR 2025
C.I ALGRITHTM INVOLVED IN COMPUTING THE OUTPUT O WITH PROPERTIES FROM THEOREM 3.4
In this subsection, we include the algorithms used to obtain the output which satisfies the proper- ties outlined in the statement Theorem 3.4 The purpose twofold: first, simplify the exposi- tion of the proof of Theorem 3.4 and second, to make the implementation of the procedures more accessible for reproduction.
The first Algorithm generates the desired output, 0, while incorporating all subsequent algorithms. The algorithm terminates line 4 when the successive outputs for [Equation (6) corresponding to the sublevel sets L1 and L2 (with L2 11 g), differ by no more than e". The parameter e" is chosen be small enough such that, at termination, we are within of the minimizer of (0) This comparison is justified by PProposition C.I. which compares the successive distances to the distance from the global minimum.
Algorithm Algorithm for Minimizing L- Consttraiee Function
1: for L. E (mmin + 1, Linin + ....... Limin + ([og(()) [ + 2)) do
2: Execute projected stochastic gradient descent Algorithm (For sublevel set T.)
3: Take the output 0r of Algorithm 2 and calculate Ls (#t)
4: if [Cs (fr-1) Ls (0 S c" then
5: Stop and return 8,
6: end if
7: end for
Next, we have the projected stochastic gradient descent (PSGD) algorithm that is performed at each sublevel set.
Algorithm 2 Projected SGD Algorithm Given Truncated Samples and Sublevel Set
Require: L,, { each 24 p Initial Og E RR where 0g 1 Σ T(x,), step size
parameter L
1: for = 1,...,N .N do
2: Sample x(1) from the data distribution
3: h + Lt
4: (()) + Sample Gradient(O,, ,()))
5: 6.41 t 0g (t
6: Project O.+1 onto {0 [()) < L}
7: end for
8: return N
Finally, we have the process where rejection sampling is performed.
Algorithm Sample Gradient
Require: x, 0
while True do
2: Sample Po
3: if Ms(z) = where Ms is the membership oracle then
4: return T(=) T(x)
5: end if
6: end while
C.2 THE PROOF OF THEOREM 3.4
Proof. The parameter & that will satisfy the properties of the theorem will be the output of the Algo-
rithm However, before handling this, first show that there is way amplify the probability
19

---

Published as a conference paper at ICLR 2025
of the output 8r it appears line 3. by running the PSGD independently and then choosing the best output among all the trials.
Apply Theorem 3.12 (PSGD) the optimization problem in Equation (6) for the sublevel sets
N L = Lmin + +m+ cs. where m [0, log (2) +2], Limnn = L E Ezppg. [T(x)]) 8g Di= T(x:),
and |00 B (T())]l22 - cs.
Choose i. which holds for N 2 O ( kL log (1) log" (t)). Given the L-smoothness of L
(2
and the fact that (E m=pp (T(x)]) = O, we obtain the bound |VD - - r for all 0 E {0 ||0 E Exp (=)]l S r).
Therefore, with this choice of cg, we have [(66) - Lunin I c, and thus the following bound holds:
(1) - w=1 1|2 = 110 - 10 s (L(0) - [(())) s = (1 log - ())
Hence, Theorem 3.12 in our setup gives an upper bound:
C' Colog (1/a)
bn
2(L + log(1/a) 12(L + log (
So, for:
C' C'log" C'log"(//a) + + log(1 log(1/a))(m
T2
12(1. + log( (2
Theorem 3.12 gives us a such that:
E [f(0) f(8*) S
From Markov's inequality, we get:
Pr [1(0) 1(0") 3e| S
We can easily amplify this probability by repeating this process independently and hence obtaining a sequence of W1, W2,..., Wm. and then choosing:
w argmin f(w)).
w;
Since 0 satisfies:
m
Pr [f(0] ((0)) 2 3c <
by choosing m 2 log(8)/ log(1/3), we obtain an w that satisfies:
Pr [f(0) - f(0)) 2 3e| s
To accomplish this, however, we need access the value of:
(s(w.) L(w,) + log (Prz~re, [Ir E ST)
Since we have access to S only through its oracle, in order calculate Prasp.., [x E S]. we use concentration for a Bernoulli random variable. More specifically, by Hoeffding 's inequality, we need O ( log (2)) samples estimate log (Praepm,
S]) e-close with probability least 1 8.
Therefore, for each sublevel set Lmin + m + ES, when we perform PSGD, we have an output On such that, with high probability, it achieves high precision:
Ls(0m)) - Ls(0 <'
where 8% the solution to the optimization problem Equation (6) the sublevel set Lmin +m+ jupposs/AAggorine 1 lis terminated when the if statement on line is verified. Then, the 0,, generated
on line 3 satisties (0 - (sr)) < " Fix e > O, and set e" log(i/aj. We claim that for
this choice of Algorithm 1 gives output 0y with high probability, such that Ls(Or) Ls( S
20

---

Published as a conference paper at ICLR 2025
Observe that Algorithm terminates. By Corollary 3.10 and we have
o" E { {((0)- Liiin
log (1) = -(0)) c(0)) = log
Consequently, there are at least two distinct sublevel sets within the range of Algorith 1 Ihat contain 0" Therefore, for each of these optimization problems, if we run PSGD with an accuracy of = ~/2 the stopping criterion on line of Algorithm will be triggered, as both sublevel sets approximate the same minimizer with high probability and accuracy 2
Now that we have established that (Algorithm terminates we distinguish two cases, namely 0* is either in {0: C(0) [(0b) I m is not. Suppose the first case, i.c. 0 {0 [()) [(0)) - m). Since 0* is the minimizer of the convex function (0)),, and is inside the optimization domain
{0: L(0) [(0,) I m) it implies that On the output of the PSGD satisfies L Ls(0)) S é'.
We deal now with the other case, i.e. when 0* & {#: [()) (())) S m) From Proposition C.I
( Ls()))
Cs(())) - (s(0
log (1)
And suppose we get 9 mm+1 From our assumption, recall that [s(0m+1)) - (s(0m)) S se,
where e" is our threshold value for stopping Algorithm
2c
Cs(0%) Ls(0 (fm(mm) - Cs(0m+1)l +
log(1/a)
2c
< e"
log (//a)
Therefore, by our choice of ,²,c" log(1/a) we get that
Ls(0m,) - Ls(0*)
3e
log (2)
log(1/a)
- Ls(0 (s()))) Ls(0") S 3e.
In the previous case, when termination, of Algorithm 1 occurred at line 4, we obtained suitable output by virtue of identifying a threshold value c" so small that if the difference the values of the approximated minima between two successive sets was bounded by e", then even if we had continued our search, our progress terms of reducing the value of Ls would have been negligible.
Finally, it remains to show that throughout the process, we always maintain linear mass in terms of a. This follows directly, since upon termination of Algorithm the output parameter lies in the sublevel L [(O,) + m, which satisfies L < (())) + Therefore, by Observation 3.8 we conclude that all parameters 0' accessed by Algorithm
possess at least ae mass.
21


Reviews:
[{"review_id": "QYKC9h5HSE", "reviewer": "Reviewer_7NRY", "summary": "This paper revisits the problem of learning an exponential family of distributions under truncated samples. The main focus is the dependence of the runtime and sample complexity on the mass of the truncation set. \n\nIn the truncated samples model, the samples are only observed when they fall into a subset S of the domain that has some measure $\\alpha$. Such a sampling oracle can be implemented using a membership oracle for the set S. Although for constant values of the mass $\\alpha$ the sample (and query) complexity asymptotically matches the bounds from prior work on the problem, there is an exponential improvement in the dependence on $1/\\alpha$, when $\\alpha$ gets close to $0$. Another difference from prior work is the use of weaker assumptions, which also leads to a weaker type of learner. More specifically, while prior work by Lee et’ al can estimate the parameter vector of the exponential family up to error $\\varepsilon$, in this paper, the algorithm is a proper learner that outputs an exponential family that has small KL divergence with the true distribution. \n\nFrom a technical standpoint, the novelty lies in the definition of a sequence of constrained optimization problems. Specifically, the authors use projected SGD in a region where the negative log likelihood is not allowed to exceed a certain threshold during each iteration. This prohibits the algorithm from moving to regions in the parameter space that would assign very small mass to the truncation set and seems to be crucial for achieving the exponential improvement in terms of the inverse mass $1/\\alpha$ of that set S. \n\n\n\nMinor comments:\n\n-Line 53: “resoursed”->“resourses”\n\n-Lines 109-114: The example here needs some rephrasing. I get the point you are making, but technically, when you fix a set (S=[0,1] in this case), the mass assigned to it and the variance of the distribution, there is a unique distribution (NOT multiple ones) satisfying these constraints. Maybe you could say $O(\\alpha)$ mass.\n\n-Lines 131 and 371: In the second argument of the KL distance, it should be $\\hat{\\theta}$ in the subscript.\n\n-Line 388: Usually the word “requires” is used for lower bounds. Maybe say “a good initialization can be found”\n\n-Line 399: “estimate of”->”bound on”\n\n-Line 448: Proof of Observation 3.8: The statement seems reasonable,  but I think that the proof is incomplete. You show that the exponential is at most 1, but you need something stronger since it could be that $Pr_{\\theta^\\prime}[S]>Pr_{\\theta}[S]$, right?\n\n-Line 490: “$SE(K,\\beta)$”->“$SE(K^2,\\beta)$”", "questions": "In section 1.1 (line 133), you mention that: “the fact that our algorithm only requires an α-truncated sample oracle is what enables us to achieve a polynomial number of oracle calls to the membership oracle to S”. Can you elaborate on that? Is this not due to the threshold that you introduce in the optimization problems? It seems that assuming the truncated oracle access only allows logarithmic dependence instead of polynomial, which you would get via rejection sampling.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper gives an interesting perspective to an important question in statistics involving data corruption and potentially expands the applicability of state-of-the-art techniques to settings where the corruption is much stronger.", "weaknesses": "I believe the authors should make the assumptions they need to use clearer from the introduction to improve the presentation quality. For example, the strong convexity and smoothness assumption is not mentioned in the statement of Theorem 1.5, which makes it seem too strong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fclTLIRfFH", "reviewer": "Reviewer_3xik", "summary": "The authors address the problem of estimating a parametric distribution from truncated samples. \nThey propose an efficient procedure for parameter estimation within an exponential family under these conditions, improving the dependence on the probability mass of the survival set from a super-polynomial to a polynomial rate.", "questions": "- l.45: the definition of $A(\\theta)$ is wrong given the previous definition of $p_\\theta$;\n\n- Definition 1.1 should not be a definition but a proposition;\n\n- Theorem 3.3 and Theorem 3.4 are nearly identical, differing only in their dependencies on $\\alpha$ and $\\alpha^2$. I find it confusing to present both; what is the rationale behind this choice?;\n\n- In Lemma 3.7, $u$ and $\\hat{u}$ are never defined, I guess that they authors meant $\\theta^*_S$ and $\\hat{\\theta}$?\n\n\n**Proof of Theorem 3.3:**\n\n- Inconsistent notation for $\\theta_0$ that appears as $\\theta_0$ and $\\theta^0$;\n\n- l.519: why is there a $L^3$ term in the lower bound on $N$? It appears as $L$ in Lemma 3.7;\n\n- l.521: the bound on $\\lVert \\theta_0 - \\mathbb{E}[T(x)] \\rVert_2$ holds with probability at least $1-\\delta$ (according to Lemma 3.7). However, the bound is treated as if it hold almost surely in the rest of the proof. I believe that this will cause an issue when bounding the deviation of $f(\\bar{\\theta})$ from $f(\\theta^*)$ (l.529). Can it be easily fixed?\n\n- I do not understand the inequalities l.525. Since it it never defined, I assumed that $w^{(0)} \\coloneqq \\theta_0$. In this case I don't understand where the $1/\\lambda$ multiplicative term comes from in the first inequality. Moreover, I cannot reproduce the second inequality using the current information in the proof. Can the authors clarify this part?\n\n- There are many typos in the proof: $f$ instead of $\\mathcal{L}$, $w$ is not defined, l.525 the bound holds for the norm of the gradient, the index $\\theta$ is not defined l.524...", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "This work fits well within the existing literature; the efficiency problem is well-motivated and clearly defined. \nThe authors present a clear improvement in terms of computational efficiency.", "weaknesses": "The presentation of the paper is poor:\n- The structure of the paper is unclear, the main approach is not even presented in the main body of the paper;\n- There are significant redundancies; for example, Section 2.1 is nearly identical to Section 1.1;\n- There are many typos.\n \nThe proof of the main result contains several gaps (see Questions), and I do not find it convincing at this stage.\n\nThere are no numerical experiments to illustrate their theoretical results or to compare with existing approaches.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1evrdYzpmu", "reviewer": "Reviewer_uTFY", "summary": "This paper studies the problem of learning a high-dimensional probability distribution from \"truncated samples\" -- that is, the goal is to learn a distribution $p$ given samples from $p$ conditioned on some event $S$, called the \"survival set\".This is not possible with reasonable (polynomial) sample complexity for an arbitrary distribution $p$, so, like prior work, the paper focuses on exponential family distributions.\n\nMore concretely, the model is that one gets:\n\n-- samples from $p$ conditioned on $S$; the set $S$ is not known to the algorithm\n-- access to an oracle which takes as input a probability distribution $q$ and returns a samples from $q$ conditioned on $S$\n\nHere $p$ and $q$ should be exponential family distributions so that they have a short description which can be handed to the oracle. There is a further constraint that the probability mass of $S$ under $p$ and $q$ is at least some parameter $\\alpha > 0$. As $\\alpha$ gets small, this problem gets harder, since we are observing only samples from some low-probability event under $p$.\n\nPrior work showed how to accomplish this task for exponential family distributions, with sample complexity and running time depending polynomially on dimension of the distribution and the inverse of the accuracy to which the distribution is learned, but super-polynomially on $1/\\alpha$. (Prior work achieved only quasipolynomial dependence.)\n\nThis dependence on survival probability is important for overall running time, because one way to implement the sampling oracle is via rejection sampling, using a membership oracle for $S$ and a sampling algorithm for $q$. But the running time of such an implementation will be about $1/\\alpha$ to get a single sample.\n\nThe main contribution of this work is to give an algorithm with running time and sample complexity having polynomial dependence on dimension, inverse of the accuracy, and $1/\\alpha$. My understanding is that this result is novel even in the special case of Gaussian distributions.\n\nThe problem is extremely well motivated -- truncation is a common situation for \"in the wild\" datasets. And the technical contribution is certainly sufficient for ICLR. I recommend acceptance.", "questions": "Minor comments:\n\n-- It would be nice if the analogues of 1.6 and 1.7 from prior work were stated formally rather than alluded to in prose, for easier comparison. For example, I am still a little unsure after reading the prose if prior work gives an algorithm with $poly(1/\\alpha)$ dependence for the special case of Gaussians?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "See above", "weaknesses": "See above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uF9ZfZmYDV", "reviewer": "Reviewer_JmS1", "summary": "This paper studies the problem of learning an exponential family with truncated samples. Specifically, for any distribution $p$, the truncated distribution $p^S$ corresponds to the distribution of $p$ restricted to a set $S$. The paper shows that if a distribution $p$ is selected from an exponential family, and we are able to observe samples from $p^S$ and access a membership oracle for $1\\\\{x \\in S\\\\}$, then one can find an estimator $\\hat{p}$ such that $KL(p^S ||\\hat{p}^S) \\leq \\epsilon$. The main technical contribution is to obtain bounds on the sample complexity and oracle complexity that depend poly-logarithmically on $\\alpha:=p^S[S]$, with a computationally efficient estimator $\\hat{p}$.", "questions": "1. I assume you are using $\\theta^*$ to denote the ground truth parameter throughout the paper, but in Corollary 3.9, it seems to be defined differently. Is the $\\theta^*$ in Corollary 3.9 the ground truth as well?\n\n2. In the second assertion of Corollary 3.10, why is the consequence stated for $\\theta^*$ when your condition is for $\\theta^0$?\n\n3. Can you provide a detailed proof of Corollary 3.10? Specifically, it is unclear how the definition $\\theta^0 = \\mathbb{E}_{p}[X]$ plays a role in the proof.\n\n4. In the proof of Theorem 3.3, how do you derive $p_{\\theta}(S) \\ge \\frac{1}{\\alpha^2} e^{-\\epsilon}$? I assume you are referring to Corollary 3.10, not Corollary 3.9? Moreover, what is the significance of this result in the overall proof?\n\n5. Can you clarify the terms $w$ and $f$ in the proof of Theorem 3.3? How do they relate to $\\theta$ and $\\mathcal{L}$?\n\n6. Typos:\n    - Line 466: $\\min\\\\{\\min...\\ \\\\}$\n    - Line 519: It should be \"Here\" instead of \"Where\" to start a new sentence.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of this paper comes from the polylogarithmic dependency on the parameter $\\alpha$ in both the sample and oracle complexities. As far as I'm aware, this seems to be original, at least for bounding the KL-divergence of the truncated distributions themselves. The paper also introduces several new techniques, such as the minimization of the \"truncated\" negative log-likelihood (NLL) constrained by a bound on the original NLL.", "weaknesses": "The main weakness of the paper is its presentation; it is quite difficult to follow the proofs provided in Section 3. I have the following specific comments:\n\n1. The paper emphasizes that its primary contribution is improving the poly($1/\\alpha$) dependency from Lee et al. (2023) to poly-log($1/\\alpha$). However, a quick look at that paper reveals that Lee et al. (2023) focuses on estimating the parameter, not the truncated distribution. Therefore, I am unsure how significant this improvement is.\n\n2. Section 3 is quite dense, and the logical flow of the proof is not well explained. Overall, the section feels extremely unstructured.\n\nI suggest that the authors improve the writing in Section 3 by, for example, providing a clear roadmap of the proof at the beginning of this section and clearly explaining how each lemma contributes to the final proofs. Please also refer to the \"Questions\" section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)