Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
Authors: Alkis Kalavasis
Anay Mehrotra
Manolis Zampetakis
Felix Zhou
Ziyu Zhu
Venue: ICLR 2026 Poster (2026)
Keywords: high dimensional statistics
algorithmic statistics
computational learning theory
coarse observations
mean estimation
linear regression
friction
Primary area: learning theory
TL;DR: We study  Gaussian mean estimation from coarse observations under convex partitions. We give efficient algorithms and characterize identifiability.

Abstract: Coarse data arise when learners observe only partial information about samples; namely, a set containing the sample rather than its exact value. This occurs naturally through measurement rounding, sensor limitations, and lag in economic systems. We study Gaussian mean estimation from coarse data, where each true sample $x$ is drawn from a $d$-dimensional Gaussian distribution with identity covariance, but is revealed only through the set of a partition containing $x$. When the coarse samples, roughly speaking, have ``low'' information, the mean cannot be uniquely recovered from observed samples (i.e., the problem is not *identifiable*). Recent work by Fotakis et al. (2021) established that *sample*-efficient mean estimation is possible when the unknown mean is *identifiable* and the partition consists of only *convex* sets. Moreover, they showed that without convexity, mean estimation becomes NP-hard. However, two fundamental questions remained open: 
1. When is the mean identifiable under convex partitions?
2. Is *computationally* efficient estimation possible under identifiability and convex partitions?

This work resolves both questions. We provide a geometric characterization of when a convex partition is identifiable, showing it depends on whether the convex sets form ``slabs'' in a direction. Second, we give the first polynomial-time algorithm for finding $\varepsilon$-accurate estimates of the Gaussian mean given coarse samples from an unknown convex partition, matching the optimal $\widetilde{O}(d/\varepsilon^2)$ sample complexity. Our results have direct applications to robust machine learning, particularly robustness to observation rounding. As a concrete example, we derive a sample- and computationally- efficient algorithm for linear regression with market friction, a canonical problem in using ML in economics, where exact prices are unobserved and one only sees a range containing the price (Rosett, 1959).

Published as a conference paper at ICLR 2026
MEAN ESTIMATION FROM COARSE DATA: CHARACTERIZATIONS AND EFFICIENT ALGORIHTMM
Alkis Kalavasis
Anay Mehrotra
Yale University
Stanford University ana ymah @gmai i com
alkis waw.skkkllaasssssss.. kalavaaissyaaleeee
Manolis Zampetakis
Felix Zhou
Ziyu Zhu
Yale University
Yale University
IMC Trading zhzy01 20r00117@mmmlll com
mancli is zampetakis@yaler a
felix. zhou@yale.
ABSTRACT
Coarse data arise when learners observe only partial information about samples; namely, set containing the sample rather than its exact value. This occurs nat- urally through measurement rounding, sensor limitations, and lag in economic systems. We study Gaussian mean estimation from coarse data, where each true sample x is drawn from a d-dimensional Gaussian distribution with identity co- variance, but is revealed only through the of partition containing x. When the coarse samples, roughly speaking, have "low"" information, the mean cannot be uniquely recovered from observed samples (i.e., the problem is not identifiable). Recent work by Fotakis et al.] (202T) established that sample-efficient mean esti- mation is possible when the unknown mean is identifiable and the partition con- sists of only convex sets. Moreover, they showed that without convexity, mean es- timation becomes Na-hard. However, two fundamental questions remained open: (1) When is the mean identifiable under convex partitions? (2) Is computation- ally efficient estimation possible under identifiability and convex partitions? This work resolves both questions. We provide a geometric characterization of when a convex partition is identifiable, showing it depends on whether the convex sets form "slabs" in direction. Second, we give the first polynomial-time algorithm for finding E-accurate estimates of the Gaussian mean given coarse samples from an unknown convex partition, matching the optimal (ddE²² sample complex- ity. Our results have direct applications to robust machine learning, particularly robustness observation rounding. and computationally: efficient algorithm for linear regression with market friction, a canonical problem in using ML in economics, where exact prices are unobserved and one only sees range containing the price (Rosett 1959..
concrete example, we derive a sample-
INTRODUCTION
The rapid growth of data-driven inference and decision-making has amplified the need for statisti- cal and algorithmic methods that robustly handle incomplete imperfect data. While large body of statistical literature focuses on the problem of missing data (Little & Rubin 1989 2019),
where observations are either fully precise or totally incomplete, many applications present differ- ent challenge: data are often neither entirely missing nor perfectly observed. For instance, consider healthcare analyties (Chandel al. 2024; Nietert et al. (006)) recommendation systems (Hu al.) 2008), and sensor networks (Jayasekaramudeli et al. [2024] Dogandžić & Qiu 2008), where obser- vations are frequently rounded to some precision. This occurs when a healthcare form, user feedback system, sensor network only records values up the nearest unit (for instance, rating of 4.7 is rounded to 5, only revealing that the true rating lies in [4.5, 5.5)). Economics provides another com- pelling example: market friction (Rosett) 1959). where agent responses to environmental changes exhibit lag. Specifically, small movements in underlying conditions fail to trigger price adjustments; instead, prices remain fixed within "inaction band" (Roseti 1959). Here, the analyst learns only

---

Published as a conference paper at ICLR 2026
that the true, friction-free value lies somewhere within that band, but does not gain any information about the precise value. Similar phenomena arise in physical sciences and survey statistics due to sensor limitations and data aggregation (Wang & Heitjan 2008 Sheppard 1897).
These scenarios share a common structure: the statistician observes a subset S of the space contain- ing the true value but not itself. The missing data framework cannot capture this partial observ- ability, as it assumes that the data is either fully observed or absent. In contrast, coarse data provides an intermediate case: it restricts v to the observed set S, offering some information while still leav- ing some uncertainty. This fundamental distinction motivated extensive works in statistics (Heitjan & Rubin 1990, 1991 Heitjan 1993 Gill al. 1997) (also see the survey by Amemiya (1973)) to model coarse data and study estimation problems in both supervised and unsupervised settings.
Despite this extensive theoretical foundation, statistically and computationally efficient algorithms for even fundamental tasks have remained elusive in the coarse data setup. In this work, we revisit perhaps the most fundamental problem in this area: Gaussian mean estimation from coarse data.
Problem Setup. The problem is parameterized by a (potentially unknown) partition P of R into disjoint sets (Heitjan Rubin 1990). For instance, with = 1, S can be the set of unit intervals formed by the usual grid of ll (namely, .... (-1, 0), [0, 1), [1, 2): .) capturing the coarsening aris- ing from rounding in di different aforementioned domains. The learner observes sets P1, P2, Ps.... from P, where each P. is sampled as follows:
First sample (unseen) 2; N(p", IJ,, then output the unique set P. in S containing 2,. Our goal is to find an estimate jú of the unknown mean μ² in time polynomial in both the dimension d and the inverse desired accuracy l/e.
To gain some intuition, first consider the task without coarsening: given samples T1, F22 ..... ... In from a Gaussian with mean μ²" the empirical mean >: 21/n is ((//ma)-llose to μr with high probability. Under coarsening, however, we observe sets instead of points, making this approach inapplicable. A natural idea is to pick a canonical value for each set P; (such as its centroid) and average these canonical values, but any such choice of canonical value can yield estimates (((r) away from μ", where r is the radius of the sets Thus, Gaussian mean estimation from coarsened data requires more sophisticated methods to achieve vanishing error as the number of samples n - oc.
Coarse samples make mean estimation strictly more challenging. For some extreme partitions P, estimation becomes impossible. Consider e.g., S {Rd),, where the partition consists of only the whole space. The learner observes samples I Rdd ..... which contain no information about μ", making estimation information thheoeetiiotorrriillllylll impossible. A partition is said to be identifiable if the mean '² can be uniquely determined from coarse samples. In the example above, the partition is not identifiable. See Figure I for further examples of partitions and their identifiability properties.
Figure I: Different partitions S0 of IR?. (a) Left: A non-identifiable partition where any μ*' E IR² and its translation along the z-axis induce identical distri- butions of coarse samples. (b) Middle and (c) right: Identifiable partitions of the space.
The Need for Convex Partitions. As mentioned, there are several prior works on learning from coarse data. The key prior work for coarse Gaussian mean estimation is (Fotakis et al. (022). They showed that the partition structure affects both the identifiability and the computational complexity of mean estimation. In particular, they showed that if S contains non-convex sets then Gaussian mean estimation from coarse samples is hard in general. Thus, for computational efficiency, one must focus on convex partitions: partitions whose sets are all convex.
1 'The radius of set is the radius of the smallest ball containing the set. A set S is convex if for any 21, S, the midpoint (z1 + 222)22 is also in S. Convex sets are quite general and include polytopes (boxes, halfspacees and ellipsoids.
2

---

Published as a conference paper at ICLR 2026
Prior Sample Complexity Results. For convex and identifiable partitions. Fotakis et al. (2021)
provided (non-efficient) method achieving an E-accurate estimate using ((4)²)) coarse samples
This only establishes sample complexity guarantees, leaving two fundamental questions open:
Q1. Which convex partitions result in an identifiable instance?
Q2. Is computationally--fiiii -ffficiciet mean estimatiin possible for all identifiable convex partitions?
Answering Q1 contributes to the line of work characterizing identification conditions for missing data problems across statistics (e.g.. Everitt & Hand (2013); TTicher (1963)) statistical learning
theory (e.g./ Angluin & Smith (1983); Cai al. (2025), and econometrics (e.g.. Manski (1990);
Athey & Haile 2202)). Q2 addresses a key computational question: given Fotakis et al. (2021)'s
result on sample-efficiens estimation with convex partitions in high dimensions, is there an efficient
algorithm for coarse Gaussian mean estimation or do face catissticallt--oopuaattttli
gap?
Our Contributions. Our main contribution to completely resolve the above questions:
Identifiability Characterization (Theorem 3.1) We characterize the convex partitions P under which the mean μJ' is identifiable.
Efficient Algorithm (Theorem 3.2): We provide the first polynomial-tin algorithm for estimating n² for any convex, identifiable partition P. The algorithm matches the sample complexity Fotakis et al. 2021), while also being computationally efficient.
These results settle the computational complexity of coarse Gaussian mean estimation under convex partitions. As concrete application of our techniques, we obtain a sample- and computationally- efficient algorithm for linear regression with market friction, a canonical setting where coarsening arises from lag in market participants responses (Theorem
Characterization Techniques. Our first result is a geometric characterization of the sets of the partition @ that allows for identifying the Gaussian mean from coarse observations. Returning to Figure I a), it is not difficult to see that partitions that consist of parallel slabs are not identifiabl.. This gives very natural and intuitive sufficient condition. It remains to argue that this is also necessary, ie., that any non-identifiable partition should look like a collection parallel slabs.
Our main technical contribution in characterization is to show that parallel slabs are also necessary for non-identifiability. To show this, our proof combines tools from optimal transport and variance reduction inequalities (Vempala 2010; Hargé (004); we believe this combination will have broader applications in estimation with coarse samples.
Necessity of Parallel Slabs:
Algorithmic Techniques. Our computationally efficient algorithm performs stochastic gradient de- scent (SGD) on a variant of the log-likelihood objective (Section Obtaining provable guarantees for this approach requires several key innovations (compared to, e.g., Fotakis et al. (202T)):
Controlling Second Moment: Establishing SGD convergence requires bounding the second moment of gradients. which intuitively controls the "noise" in each update. In our setting, the second moment scales with the radius of coarse observations and can unbounded if the parti- tion contains unbounded sets. To overcome this, we introduce an idealized class of local parti- tions (where all sets have a bounded radius; Appendix B.I], develop an algorithm for this class, and then show that general partition can be reduced local one (Appendix B.5).
We refer the reader to Section for further discussion of our techniques and challenges.
1.1 RELATED WORKS
In this section, we provide overview of further related works.
Learning from Coarse Data. Inference from coarse data has been extensively studied in statis- ties (Heitjan & Rubin 1990; 1991: Heitjan 1993] Gill et al. 1997, Gill & Grünwald 2008). The closest to our work is that of Fotakis et al. (2021), who studied coarse estimation in both supervised
TTo he more concrete, the sample complexity scales O(d/s2)-a=* where quantifies how "informative" the partition is (Proposition B.5). The exact details are postponed to Section
3

---

Published as a conference paper at ICLR 2026
and unsupervised settings. For coarse Gaussian mean estimation, they give sample-efficien algo- rithm for identifiable convex partitions. In the absence of convexity, they show that even fitting the true coarse distribution in total variation distance becomes NP-hard. In PAC learning with multiple labels, they show that any SQ algorithm over "fine" (i.e., non-coarse) labels can be simulated using coarse labels, with coarse sample complexity polynomial in the information distortion and number of fine labels. More recently, Diakonikolas et al. (2025) established an SQ lower bound for linear multiclass classification under coarse labels (under a weaker notion of information preservation). As we have mentioned, coarse observations arise in number of natural scenarios. An interesting example of this is given by Kalavasis et al. (2025): They showed that the model of Roy (1951) can be framed as problem of Gaussian mean-estimation with coarse observations arising from non-conver partition. While, general, non-convex partitions are intractable, the partitions arising in Roy 195T)'s model are highly structured and this enables Kalavasis et al. (2025) to develop an efficient local convergence algorithm for the problem.
Sheppard's Corrections. Sheppard's corrections are approximate corrections to estimates of mo- ments computed from binned data (Sheppard, 1897), i.e., 1-dimensional coarse Gaussian samples from equal-length interval partitions. For mean estimation, our model extends Sheppard's correc- tions into the nigh-dimmesional setting with non-uniform convex partitions.. Our work also relates to Sheppard's 's corrections, which are classical bias adjustments for mie-dienniooall coarse data (e.g., values rounded to the nearest integer) that yield asymptotically unbiased moment estimators under certain assumptions on the partition (Sheppard) (897). These corrections are widely used in astron- omy and official statistics, among other fields (Schneeweiss & Komlos 2009. [Schneeweiss et al.) 2010). For mean estimation, our computationally efficient algorithm generalizes Sheppard's 's ap- proach to significantly more complex partitions, including high-dimensional ones (Proposition B.5) In addition, we also characterize the statistical limits of estimation with coarse data by characterizing identifiability (Theorem 3.1).
Learning from Partial Labels. Our problem falls in the broader category of learning from partial
labels. which has been extensively studied in supervised learning (Jin & Ghahramani] [2002] Durand
et al.) [2019; Nguyen & Caruana 20088 Cour et al.) [011:: Ratner et al.] [2017] De Sa et al. 2016
Cauchois et al. 22044 Feng et al., 2020) Liu & Dietterich, 2014] Feng & An 2019). Our work studies the unsupervised version of the problem, as we previously discussed.
2 PRELIMINARIES
In this section, we present the notation we use and introduce the coarse observational model. Notation. We begin by introducing the notation used throughout the paper.
Vectors and Balls. We standard notations for vector norms: For vector v E Rdd use ||la|/ to denote its L--nomm and ||o]|cc its L -nom. We use B(v, R) to denote the La-ball centered at vector with radius R and Bo (v, R) for the associated Loo -bal. Also, for E IRd and i [d]. w- E dRd-1 denotes the vector obtained from v by removing the i-th coordinate.
Partitions. We usually denote by S partition of Rd and by P an element of this partition. We will call a partition convex if each P E P is convex.
Gaussians, Coarse Gaussians, and Distances Between Distributions. We use N(H Σ) to denote the Gaussian distribution with mean μ E IR and covariance Σ E Rd In particu- lar, N(2, Σ) has density N(H, Σ; x) e 1/==-))>1//((x-11 The mass of some set S Rd under this distribution is denoted by N(p, E; More broadly, for a distribution p and set S. p(S) the mass of S under p. For some partition P, we use the notation Ng (14, E) to denote the coarse Gaussian distribution, defined as N (H, E; P) = Sp N(H, E; x) dr for each P E P. For two distributions p.g over Rd. denote their total variation dis- tance as dTv(p.g) = (1/2) fga lp(x) - [dx and their KI. divergence as KL(pl)g) = Emm (lo((p)))//(()))
4

---

Published as a conference paper at ICLR 2026
2.1 THE COARSE OBSERVATIONS MODEL
We now formalize the random process that generates coarse observations in Definition and then discuss what means for problem instance to be identifiable.
Definition 1 (Coarse Mean Estimation (Fotakis et al. 2021)). Let lP be an unknown partition of R. Consider the Gaussian distribution N(u", I)), with mean μ³ E I (unknown to the learner) and identity covariance matrix. A coarse sample is generated as follows:
1. First, nature draws from N(p", .I).
2. Then, it reveals the unique set P P that contains x (but not itself) the learner.
We denote the distribution of the coarse sample P as No ,
Given a desired accuracy & 0 and coarse samples PI, P2.... from the generative process of Definition
[ the learner's goal is to compute an estimate μú of μd that, with high-probability, satisfies || 1²=
2l2 -"==""
in time that is polynomial in 1/e and the dimension d.
Since the learner's goal is to recover the parameter μt, we must at least ensure that the problem is identifiable, which roughly means that parameter recovery is possible for any > O. Recall that there are some extreme partitions, such as sP = [. for which this impossible. The following notion of information preservation is equivalent to identifiability (and explain this after the definition). Definition (Information Preservation (a.k.a. Identifiability)). partition P is said to be informa- tion preserving with respect to μ²" if for any μa + μ", it holds that dTv(Ng (fx*, I) NNg (p, I)) 0.
Recall that the total variation TV distance between two distributions is if and only if the two distributions are identical. Thus if J not informatiin-preservinng preserving. there are two distinet mean val- ues μ² f μ such that the corresponding coarse distributions No (μ²,, I) and No (p, I) are identical, making the two indistinguishable even with infinite coarse samples. Conversely, when a partition is informmttion-preeeviing then the coarse distributions induced by any μ μ² differ in total variation. Thus infinitely many coarse samples suffice to distinguish μ² from any other μl & p².
As examples, we have already seen that some partitions are identifiable; examples include the partition S = [ and the partition in Figure a);; while those in Figure | b,c) are identifiable.
Given the identifiability of an instance, one can study the number of samples and time needed to estimate the mean. For that, one needs to introduce quantitative version of the identification con- dition and, indeed, this end, prior work has introduced the notion of a-information preservation:
Definition (a-Information Preservation; (Fotakis et al. 2021 ). Given a E (0, 1), we say that the partition Si of IRd is a-information preserving with respect to μ² for any μ a p", it holds that
dTv (1c*, No (1s, T)) 2 a deddc(((""", ((,,(1 T))
As sanity check, note that for any ja * ,e", have dTv(N(m" N,, information-presentt preservation for any a > implics information preservation. Fotakis et al. (22T))ss sample-efficient algorithms require this stronger a-information- cinfoomatioonpreseevattoon notion. Our computa- tionally efficient algorithm (Theorem 3.2) will also require this strengthening of identifiability.
I))
0,
OUR RESULTS
In this section, we present main results. Section 3.1 presents the characterization of identifi- ability, Section 3.2 the computationalll--ffiiiii algorithm, and, finally, Section 3.3 presents the application of the compuuationallly-effiiinnn algorithm regression with friction.
3.1 CHARACTERIZATION IDENTIFIABILITY FOR CONVEX PARTITIONS
In this section, we give a geometric characterization of when a convex partition is identifiable. Informally, a partition fails be identifiable if and only if it translation invariant in some direction.
To formally state the characterization (and prove it), we need the following notion of a "slab."
Definition 4 (Slab). Given unit vector Rd (non-empty) set P C Rd is said to be slab in direction u if P is invariant under translations along direction v. That is, a slab in direction u it has the property that if q then I. + to E P for all E TR.
5

---

Published as a conference paper at ICLR 2026
Examples of slabs include all the sets in the partition in Figure () and the sets in Figure 2 Note that because of the translation invariance, any slab in direction must be unbounded in that direction. Hence, bounded sets (such as the unit circle or bounded box) are not slabs in any direction.
Now we are ready to formally state our characterization. Its proof appears in Appendix A
Theorem 3.1 (Characterization of identifiability for convex partitions), Fix any μ E R A convex partition SP of Rd is not information preserving (i.c., not identifiable; Definition 2 with respect to ju" if and only if there is a unit vector v E Rd such that almost ever P E P is a slab in direction v.
We have already seen one example of a non-identifiable partition Figure Ta] in two dimensions. One can also construct examples in higher dimensions, e.g., partitions in three dimensions using the slabs in Figure aa).. Some more remarks are in order.
Information preservation (i.e., identifiability) does not depend on μ²: either P is identifi- able for every μ²' or for none. Hence, the difficulty of coarse Gaussian mean estimation comes from the structure of the coarse samples and not the specific Gaussian distribution.
2. The characterization in Theorem 3.1 is already sufficient to deduce identifiability with re- spect several interesting partitions. For instance, consider the partition induced by round- ing, i.e., the grid partition of Rd formed by axis-aligned boxes of side length, say. 1. This is identifiable by Theorem 3.1 because every P E P is convex and bounded (not slabs).
3. The "almost every" quantifier in Theorem 3.1 is important:
convex partitions P contain non-slabs but are non-identifiable because the non-slabs have zero total vol- ume. For instance, consider the following partition of IR² by (infinite) vertical lines Lo = {(a. y) E R} at each = a for a * 1. and at x = =1 by two half-lines f1+ ((1,)) : y 2 0} and fT.- == g1. y y<
< 0}. Here f1, and f1,- are non-slabs, because these sets together have zero volume. Intu- itively, manipulating zero-vo volu-e sets does not change the coarse distribution in total vari- ation distance (see Definition D.
yet the partition is non-identifiabe
4. Finally, we note that identifiability is purely information-theoreiic Being identifiable does not by itself guarantee sample-efficient estimation. For this, the natural strengthening of information preservation, a-information preservation, is required (Definition 3
Figure 2: An illustration of different slabs in direction e in three dimensions. Intuitively, slab in direction v is formed by tak- ing a 2D shape ((a) square, (b) circle, (c) hexagon in each of the three subfigures) and extending infinitely in direction v (and -)).
3.2 POLYNOMIAL- -IMME GAUSSIAN MEAN ESTIMATION FROM CONVEX PARTITIONS
Next, we present our computationally efficient algorithm showing that polynomial-ting coarse Gaussian mean estimation is possible from convex partitions. The running time of these algorithms degrades naturally with how much information the partition preserves, as captured by the informa- tion preservation parameter (Definition 3)
To be precise about running time, we need specify how the algorithm accesses a coarse sample P. In high dimensions, the representation of the set can dramatically affect the computational complex- ity of a problem, a well-known issue in geometric algorithms (Grötschel et al. 1988). Our algorithm works with natural encodings (e.g., polytopes described explicitly by linear inequalities, or convex bodies implicitly described by a separation oracle and an inner radius) and runs in polynomial time relative to the bit complexity of the encodings of observed sets [
Our computationally-effiiiii result as follows. Its proof appears in Appendix
*I.ct B he the set of non-slabs in P. "Almost every" means that the volume of Urea is Bit complexity measures how many bits are needed to encode the input using the standard binary encoding (which, e.g., maps integers to their binary representation, rational numbers pair of integers, and vectors/- matrices as tuple of their entries) (Grötschel al. 1988 Section 1.3)

---

Published as a conference paper at ICLR 2026
Theorem 3.2 (Coarse Mean Estimation Algorithm). There is algoritim that, for any true mean و & and any partition P that is convex and a-information preserving with respect to μº (Definition 3. gets as input the desired accuracy and confidence e, (0, 1), draws i..d. coarse Gaussian samples from P, and outputs an estimate jo satisfying
y E IR with ||
1p - 1011 S
with probability The algorithms uses
(
[dD2 (dD'log
log 1/6
dllog a²
m Ō
a²
course samples and runs in time polynomial in m and the bit complexity of the coarse samples.
Thus, when the information preservation constant, i.e., a 211), and we provided constant warm-sstar to the mean (i.e.. D = O(1), the above algorithm obtains an E-accurate estimate to μ¹ in O(d/e)) time while using O(f/2)) samples, matching the sample complexity of Fooaaiis et al. (2021) while being computationally efficient. Moreover, we can actually prove stronger guarantee: we can replace || S D in the theorem by the strictly weaker requirement that || ll S (this strictly weaker since ||0/ < 112)
Extension to Mixtures of Partitions Model. Some works on coarse estimation consider an ex- tension of the model in Definition [1] where instead of single partition PP, each coarse sample is drawn from a different partition JP. Formally, there are convex partitions PI..... Pe and the obser- vations are sets P where P E Py for some S j S l, where j is chosen independently by some prior distribution over [e]. The underlying data-generating distribution N( I) remains the same but the observations are created by first drawing a partition index S j I according to some mixture probability, independently drawing
N(u", I). and then outputting P E P, containing x. We remark that our algorithm, like the sample-efficient method of Fotakis et al. (202T), also straightforwardly extends to this model with the same time and sample complexity.
3.3 APPLICATION TO REGRESSION WITH FRICTION
Next, to illustrate the flexibility of our algorithmic techniques, we provide an application to linear regression with market friction, problem dating back to Rosett (1959). We present our main result and an informal description of the model here. The formal statement of the result, its proof, and formal description of the model appear in Appendix
Sctup: Linear Regression with Market Friction. Consider the task of analyzing the relationship between changes in the yield of bond x E IR and the change in an investor's 's bond holdings E R. In an ideal world, we would expect linear relationship between changes in yield and changes in holdings = x w² + { for ~ N(0, 1). However, due to transaction costs, bid-ask spreads, and the time and effort required execute a trade, investors will not adjust their holdings for small changes in the bond's yield. Thus, even if the underlying relationship is linear, only observe transformation (I, z = c(y)) by some friction function e IR + R (Figure 3(a)..
Figure 3: Illustrations of different friction functions c : IR R. (a) Left: monotone with convex pre-images. (b) Middle: not mono- tone but has convex pre-images. (c) Right: not monotone and has non-convex pre-images.
650
Translating Market Friction to Coarsening. To utilize algorithmic techniques, we need to frame the problem as an instance of coarsening. Indeed, we can think an observation pair (z, & = c(y)) the coarse observation (z, S) where 5 c- (2) C R. This gives bridge apply the techniques we developed for coarse mean estimation. As in the case of coarse mean estimation, may be information theoretically impossible estimate w Rdd for all friction functions. Thus,
7

---

Published as a conference paper at ICLR 2026
require analogous notion of information preservation for instances of linear regression with friction (Assumption 4) and design an algorithm for estimating wt when the friction function c is information preserving and also has convex pre-images, i.e., e (2) S I is convex for all 2 E R. This is a large class and includes, egg., monotonically non-decreasing functions as a special case.
Theorem 3.3 (Informal; See Theorem E. There is an algorithm for a-information preserving instances of linear regression with friction that, given observations, outputs an estimate w R satisfying | 11 & 0 (z with probability 0.99 in poly voly(n, d) time.
4 OVERVIEW OF MAIN PROOFS
Next, we overview the proofs of our main results and defer the exact details to Appendices A and
A central component of both the characterization and the algorithmic result is the log- log-likelihood function with respect to coarse data. We refer the reader to Rossi (2018); Cover (1999) for useful preliminaries on the log- likeliiidoood For a partition SP and true mean p*, the negative log- ligeliillhhodd
function arising from the coarse-observations model (Definition [ is as follows
(e) = Ep~Note ./) |- log Na (n, P)]
To illustrate the usefulness of the log- likeliiieiood, we present a short proof connecting a certain prop- erty of the log- lilllikiihood to identifiability; this is the starting point of our characterization.
Proposition 4.1 (Likelihood- Based Characterization of Identifiability). A partition P Tf d is infor- mation preserving (Definition)) 2 with respect to j* E &Rdd if and only if L(()) has a unique minimizer.
Thus, if S is identifiable, then the corresponding negative log-likelihood has unique minimizer (.). Further, one can show that μ²' is always a minimizer of (-)-) Therefore, Proposition 4.1 also tells us that if partition is identifiable, then the unique minimizer of (-) μ itself.
Proof of Proposition 4.1 Suppose the instance is identifiable. The following holds for any μ + n="
-(n)- - -(x))(()-+)))))))'() KL (u*, 7) IINb (n, I)) 2 2dTv(NN (n*, 1)
No (1,, 1))² >
Here, the first equality is a standard property of the log- likelihood (Cover) 1999), the second is Pinsker's inequality, and the third is the definition of identifiability of the instance.
On the other hand, if the instance is not identifiable, (Nv (μ²,, Ng (Hs, I)) = O. Therefore, Ng (n", . = Ng (μ, I), which implies that L(p) L _(xx)) = 0 because KL (p* [|No (n. I)) 0. Hence, μ * 4² also minimizes (-).. O
can find some μ * n² for which
Another useful property of (-)) is that it is convex whenever the partition P is convex. This result is due to Fotakis et al. (202T), who proved it using a variance reduction inequality of Hargé (2004).
Proposition 4.2 (Convexity; (Fotakis et al. 2021 ). If P is a convex partition, then (-) is convex.
Propositions 4.1 and 4.2 suggest a natural approach for both results: For the characterization, we will characterize partitions for which (.)) has a unique minimizer. For the algorithmic result, we will develop a computationally efficient algorithm find (-)'ss minimizer using its convexity (Propo- sition 4.2) Next, we explain how we implement this approach and the corresponding challenges.
4.1
CHARACTERIZATION OF IDENTIFIABILITY (THEOREM 3.1
Now we are ready to give an overview of the proof of Theorem 3.1 This has two directions. The harder direction is to show that when the coarse mean estimation problem is not identifiable under convex partition P. then the sets of S must be parallel slabs.
Since the instance is not identifiable, Proposition 4.1 implies that _-(-) has two distinct minimizers. As we saw above, jr^ is always a minimizer. Now, using the convexity of (-). (Proposition 4.2
TThis follows hecause of the classic equality (n) KL(N2 (n²', [| (j,, T)) const (Cover 1999. Indeed, since the KT. is always non nog-negative and it achieves value 0 J1" must be minimizer of I()).
8

---

Published as a conference paper at ICLR 2026
it can be shown that: there exists unit vector u for which V L(n))u 0. Substituting the formula for the Hessian (derived in Appendix B into the above implies:
Var P= Mer
E
[u T x:]
We divide the rest of the overview into two parts.
Step (Variance Reduction Inequality). From the variance reduction properties of Gaussian distributions (see e.g., Hargé (2004)), we know in addition that Varn>Mae" ax 2]| S 1. But since the expectation Var,~Niu" Muurrru (uTaa æ] over the draw of is 1, it must be the case that almost every set P E OP satisfies
Var N~M .I) 11) zEP [u,
1.
Step II (Combination of Variance Reduction and Prékopa-Leindles Inequalities). We now make use of the above property to show that almost all sets P the partition must be slabs in the same direction. To do this, consider the projection of the points and ut Let y with r ~ N(u", I) (P). First, using variance reduction inequality (Vempala 2010), we show that y has Gaussian distribution despite truncation (Lemma AA.5) Then, using the Prēkopa-Leindler Inequality, we show that this is only possible if P is slab in the direction of tr; in particular, if P is of the form {t-
E R x Cp (Proposition A.6).
We believe that the combination of variance reduction and have further applications in characterizing other coarse estimation problems.
inequalities can
4.2 MAIN ALGORITHMIC IDEAS (THEOREM
Given identifiable convex partition, our goal is to design efficient algorithm to find ğú μ²: From Proposition [. and Theorem D.I] we know that the log-likelihood is convex with unique minimizer μ², Hence, natural approach is to stochastic gradient descent (SGD) to find the minimizer. There are, however, several challenges in implementing this, as we discuss below. Before proceed, note that while et al. (2021) also recognized that the log- likelihood is convex and has unique minimizer, they used brute force search over an (pppdd/)ssizzz g-net (see MeleP 2011 of the domain, yielding sample-efficient but computationally inefficient algorithm.
Challenge and Idea I (Local Strong Convexity). Under some appropriate conditions on the second moment of gradients, SGD find parameter estimates Ji with L < L(x²) + e. However, can still be far from μ²" (-) was strongly convex, then Ā would be close to je" but, unfortunately, in this setting (-)- not strongly convex everywhere. Hence, we need to exploit some additional structure of (-) to translate the optimality in function value to closeness in parameter distance. Toward this, we show that the ligeliilloood is locally strongly convex around the true solution μ²; this means that the function is strongly convex in small ball around μ² To prove this, we make use of a natural connection between information preservation and the log- log-liielihood objective through the KL divergence, together with Pinsker's inequality. These yield the following (Lemma B.3):
((w) - (())) (PN N(:P)
E log N(a':P)
KL (I) (p))
Hence, using information preservation (Definition 3) and lower bounds on the total variation distance between two Gaussians (Arbas et al. 2023) implies that (see Lemma B.3)
L(x) L(xx)))))) 2a dTv(N(()), N(²"))² 2 min( ((aa)) S(a || 1|p-~"1111 --1)
The above ensures that 2(-)) is strongly convex around a small region of the true parameter jt"
Having ensured (i) that approximate minimizers in function value are also good estimators, also need to (ii) bound the second moment of the gradient norm to implement SGD efficiently. To argue about (ii), consider the gradient of (-)-) (see Appendix B.6
L (p)
E
[x]
P~NNot N).
Note that since we do not know 'r" and do not have starting point within this small ball, we cannot simply projected stochastic gradient descent.

---

Published as a conference paper at ICLR 2026
Challenge and Idea II (Bounding the Second Moment of the Gradients). Bounding the second moment of the stochastic gradients is not straightforward since the inner and outer expectations in Equation (2) are not over the same means; in general, these two means can be far as the diameter of P. Because of this, the norm of the gradient can scale with Pss and we must somehow control the gradient norm when the diameter gets large. The key idea here is to the strong concentration properties of the Gaussian measure in high dimensions. In particular, with extremely high proba- bility, collection of i.i.d. draws of the standard normal distribution in dimensions will fall inside a Lo-box of radius (()). This means that if we observe set P from the unknown coarse Gaussian, while we are agnostic the specific Gaussian sample, we can be extremely confident that it belongs to P n xx (0, Rt) for some appropriate radius R. Now, since we will eventually use m samples, we can take
D (llgg(md/6) ( and make the confidence of the learner 1 d. In more detail, conditioning on these high-probability events on the samples, we can replace each observed set P with its intersection with the ball B (0, R), and introduce a new partition of the space (see Appendix [B.I). For this new partition, we can obtain upper bounds the moments of the stochastic gradients and derive an algorithm that recovers the mean. Finally, we show that we can reduce any convex partition to this special case (see Appendix B.4.
CONCLUSION
In this work, study the problem of Gaussian mean estimation from coarse samples. Coarse sam- ples arise in many domains (from healthcare analytics, recommendation systems, physical sciences, economics) and due many reasons (from rounding, sensor limitations, to response-lag). We focus on the setting where all the coarse samples are convex, as otherwise, the problem is NP- hard (Fotakis et al. 202I). In this setting, we completely settle the computational complexity of the problem by characterizing all convex partitions that are identifiable (Theorem 3.1 and giving a polynomial
algorithm for identifiable instances (Theorem 3.2 Both of our results use sev- eral new techniques that we believe would be of broader interest to other estimation problems from coarse samples (see Section 4. As a concrete application of our algorithmic ideas, we show that our computationally efficient algorithm can be adapted to give efficient algorithm for linear regression with market friction (Theorem 3.3) a problem dating back to Rosett (1959).
Our work leaves various open questions for future work: While study Gaussian estimation with a known covariance, understanding the computational complexity of estimation with unknown co- variance is interesting direction. Developing efficient algorithms for this problem would require new ideas since the log-likelihood for this case can be non-convex. Another interesting question is to extend guarantees beyond Gaussians to other distribution families (see Appendix FF for preliminary results in this direction).
LARGE LANGUAGE MODEL USE
After writing a preliminary version of the paper, we used LLMs to help streamline the writing and find typographical errors.
ACKNOWLEDGMENTS
Alkis Kalavasis was supported by the Institute for Foundations of Data Science Yale. Felix Zhou acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror-langevin algorithm. Advances in Neural Information Processing Systems, 34:28405-28411 2021.
Takeshi Amemiya. Regression analysis when the dependent variable truncated normal. Econo- metrica, 41(6)9977-0066, 1973.
Dana Angluin and Carl H. Smith. Inductive inference: Theory and methods. ACM Comput. Surv, 15(3):237-269, September 1983. ISSN 0360-0300. doi: 00.114//35914433699 URL https:
356918
Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded Gaussian mixture models. In Andreas Krause, Emma Brunskill. Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th Interna- tional Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Re- search, pp. 1018-1040. PMLR, 2023. http:/tttt//ppeeeeeeeeeee arbas23a.htm html
mlr pta...p2ss/v2221
Susan Athey and Philip A. Haile. Identification of standard auction models. Econometrica, 70(6): 2107-2140, 2002.
Keith M. Ball and Károly Böröczky. Stability of some versions of the prékopa-leindler incqual- ity. Monatshefte für Mathematik, 163(1):1-14, 2011. doi: 10.1007/50005--0000002222 URL
https://dol.org// http://0....0771110000//00002220
Nicolas Brosse, Alain Durmus, Éric Moulines, and Marcelo Pereyra. Sampling from log-concave distribution with compact support with proximal langevin monte carlo. In Conference on learning theory, pp. 319-342. PMLR, 2017.
Sébastien Bubeck, Ronen Eldan, and Joseph Lehee. Sampling from a log-concave distribution with projected langevin monte carlo. Discret. Comput. Geom,, 59(4)7557783, 2018. doi: 10. 1007/ 500454-018 8-9992-11 httpttttsp//.o..ooeeeoo
1007 0000000000044-0000000 110000-0000000000-------9-9---1-
Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, and Manolis Zampetakis. What makes treatment effects identifiable? characterizations and estimators beyond unconfoundedness (extended abstract). In Nika Haghtalab and Ankur Moitra (eds.), Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 755 PMLR, 30 Jun-04 Jul 2025. URL cai25b. html
mlr press/v291/
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C Duchi. Predictive inference with weak supervision. Journal of Machine Learning Research, 25(1 18):145) 2024.
Tanvi Chandel, Victor Miranda, Andrew Lowe, and Tet Chuan Lee. Zero end-digit preference in blood pressure and implications for cardiovascular disease risk prediction study in new zealand. Journal of Clinical Medicine, 13(22):6846, 2024. doi: 1..3300/jcm13226833
Dario Cordero-Erausquee and Bernard Maurey. Some extensions of the prékopa-leindler incquality using borell's stochastic approach, 2016. /tL/tttsss//rrr/w.rrrr
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12: 12:1501-1536 2011.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Arak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278-53) 2019.
Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Efficient Statistics, in High Dimensions, from Truncated Samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 649, 2018. doi: 10.1109/FOCS.201
00067.
11

---

Published as a conference paper at ICLR 2026
Christopher De Sa, Alex Ratner, Christopher Ré, Jacho Shin, Feiran Wang. Sen Wu, and Ce Zhang. Deepdive: Declarative knowledge base construction. ACM SIGMOD Record, 45(1):60 67, 2016.
Ilias Diakonikolas, Giannis lakovidis, Daniel M Kane, and Nikos Zarifis. Robust learning of multi- index models via iterative subspace approximation. In Proceedings of the 66th Amnual Symposium on Foundations of Computer Science (FOCS 2025). IEEE, 2025. UtLhttps: http::::/axxxv.oxo
abs/ 20s3/2500 2002.5022..0 09525
Aleksandar Dogandžić and Kun Qiu. Decentralized random-field estimation for sensor networks using quantized spatially correlated data and fusion-center feedback. IEEE Transactions on Signal Processing, 56( 11:::66966-0855 2008. doi: 10. 10.11099TSP2000822005555
Serge Dubuc. Critères de convexité et inégalités intégrales. Annales de l'institul Fourier, 27(1): 135-165, 1977. httttt:t:///uummm wr..orggoooo.... wotp////////0000000
Thibaut Durand, Nazanin Mehrasa, and Greg Mori. Learning deep convnet for multi-label classi- fication with partial labels. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 647-657, 2019.
Brian Everitt and David Hand. Finite Mixture Distributions. Springer Science & Business Media, 2013.
Lei Feng and Bo An. Partial label learning with self-guided retraining. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 3542-3549, 2019.
Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Prov- ably consistent partial-label learning. Advances in neural information processing systems, 33: 10948-10960, 2020.
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient Algorithms for Learning from Coarse Labels. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learn- ing Research, pp. 2060-2079. PMLR, 2021. URL
preess
a. html
Richard D Gill and Peter D Grünwald. An algorithmic and geometric characterization of coarsen- ing at random. 2008.
Richard D Gill, Mark J Van Der Laan, and James M Robins. Coarsening at random: Characteriza- tions, conjectures, counter-examples. In Proceedings of the First Seattle Symposium in Biostatis- fies: Survival Analysis, pp. 255-294, Springer, 1997.
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combina- torial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. ISBN 978- 3-642-97883-8, doi: 778-3-642-99888
URL bttps:://dl..org/DD..
Alice Guionnet. Large random matrices, volume 36. Springer Science & Business Media, 2009.
S. Har-Peled. Geometric Approximation Algorithms. Mathematical surveys and monographs. Amer- ican Mathematical Society, 2011. ISBN 9780821849118, URL httptttt/so/ookss..ttssss http://ooooo..ooee..... google.
com/ boooks?id-yySSwwa......
Gilles Hargé. A convex/log concave correlation inequality for gaussian measure and an application to abstract wiener spaces. Probability theory and related fields, 130:415 2004.
Elad Hazan. Introduction online convex optimization. Found. Trends Optim., 203-43:557325,, 2016. doi: 10.1561/2400000013.
Daniel F Heitjan. Ignorability and coarse data: Some biomedical examples. Biometrics, pp. 1099- 1109, 1993.
Daniel F Heitjan and Donald B Rubin. Inference from coarse data via multiple imputation with application to age heaping. Journal of the American Statistical Association, 85(4100:304-144 1990.
12

---

Published as a conference paper at ICLR 2026
Daniel F Heitjan and Donald B Rubin. Ignorability and coarse data. The annals of statistics, pp- 2244-2253, 1991.
Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE International Conference on Data Mining, pp. 263-272, 2008. doi: 10. 1109/CDD..008..2..
Chethaka Jayasekaramudeli, Alex S. Leong, Alexei T. Skvortsov, David J. Nielsen, and Omar llaya. Distributed estimation of fields using a sensor network with quantized measurements. Sensors, 24(16), 2024. ISSN 1424-8220. doi: 10.3390/s24165299, URL https: /wwps:://wwwww// www. mápi com/
0224-8222/24/16//
Rong Jin and Zoubin Ghahramani. Learning with multiple labels. Advances in neural information processing systems, 15, 2002.
Alkis Kalavasis, Anay Mehrotra, and Felix Zhou. Can sgd select good fishermen? local convergence
under self-selection biases and beyond. arXiv preprint arXiv:2504.07/33: 2025. URL. https:
//axxiv.ogg/abs/25530
Andrew Lamperski. Projected stochastic gradient langevin algorithms for constrained sampling and non-convex learning. In Conference on Learning Theory, pp. 2891-2937. PMLR, 2021.
Roderick JA Little and Donald B Rubin. The analysis of social science data with missing values.
Sociological methods research, 18(2-3):22-3326, 1989.
Roderick JA Little and Donald Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
Liping Liu and Thomas Dietterich. Learnability of the superset label learning problem. In Interna- tional conference on machine learning, pp. 1629-1637. PMLR, 2014.
László Lovász and Santosh S. Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In 47th Annual IEEE Symposium on Foundations of
Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceed-
ings, pp. 57-68. IEEE Computer Society, 2006a. doi: 10.1109/FOCS.2006.226 URL https:
7/doi wrg.i.org/1ie /0 11t.:/00111100.600 2006.28
László Lovász and Santosh S. Vempala. Simulated annealing in convex bodics and on(n)) volume algorithm. J. Comput. Syst. Sei., 72(2):392 2006b. doi: 10. 1016. .0.04. URL
https://doi.. htt////o..ogg/////// 1016 css. 2005. 08.08..00 004
Charles F. Manski. Nonparametric bounds on treatment effects. The American Economic Review,,, 80
(2):319-323, 1990. ISSN 00028282. URL /ntp:://t//// jst wttp:r/ableeee/oooee//
Nam Nguyen and Rich Caruana. Classification with partial labels. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 551-559, 2008
Paul J. Nietert, Andrea M. Wessell, Chris Feifer, and Steven M. Ornstein. Effect terminal digit preference blood pressure measurement and treatment in primary care. American Journal of Hypertension, 19(2)147-1522 2006. doi:
Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB en- dowment. International conference on very large data bases, volume 11, pp. 269, 2017.
Richard N. Rosett. A Statistical Model of Friction in Economics. Econometrica, 27(2)263-2677 1959. ISSN 00129682, 14680262. URLhttpp:/www/ /stor.org//ttalle/1990.
Richard J Rossi. Mathematical statistics: an introduction to likelihood based inference. John Wiley & Sons, 2018
Andrew D. Roy. Some thoughts the distribution of carnings. Oxford Economic Papers, 3(2): 135-146, 06 1951. ISSN 0030-7653, doi: 10. 1o..0093.ofotijoommao.oooaaaaa URL https:
org 10. // www.spppppppoooo .
13

---

Published as a conference paper at ICLR 2026
H. Schneeweiss and J. Komlos. Probabilistic rounding and sheppard's correction. Statistical
Methodology, 6(6):577-593, 2009. ISSN 1572-3127. doi: https//dbb.orr//111116..tttaa 2009.06.005. URL $157231270900032X
H. Schneeweiss, J. Komlos, and A. S. Ahmad. Symmetric and asymmetric rounding: a review and some new results. AStA Advances in Statistical Analysis, 94(3):47--271, 2010. doi: 10.1007/ s10182-010-0125-2 URL htt.:t/pp//.oo...r////00000/0010
Ohad Shamir. Without--eplacemmet sampling for stochastic gradient methods. Advances in neural information processing systems, 29, 2016.
W. F. Sheppard. On the calculation of the most probable values of frequency-constants, for data arranged according to equidistant division of scale. Proceedings of the London Mathematical Society, 2911)3333-880 1897. doi: 10.1 10.1112/phin 12ppmmm//1129.1.35555
Henry Teicher. Identifiability of finite mixtures. The Annals of Mathematical Statistics, pp. 1265- 1269, 1963.
Santosh S. Vempala. Learning convex concepts from gaussian distributions with PCA. In 51th Annual IEEE Symposium Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010, pp. 124-130, IEEE Computer Society, 2010. doi: 10.1109/FOCS. 2010.19. URL https: //o.i./ooioo///// org/ 11..1.......11.. 1w11110000SSSS 2010.19
Hao Wang and Daniel F. Heitjan. Modeling heaping in self-reported cigarette counts. Statistics in Medicine, 27(19):378--3044 2008. doi: 10. 1282
Yi Xu, Qihang Lin, and Tianbao Yang. Accelerate stochastic subgradient method by leveraging local growth condition. Analysis and Applications, 17(05):773-818, 2019.
14

---

CONTENTS
Introduction
Related Works
2
Preliminaries
The Coarse Observations Model
3
Our Results
3.1
Characterization of Identifiability for Convex Partitions
3.2
Polynomial-Time Gaussian Mean Estimation from Convex Partitions
6
3.3
Application to Regression with Friction
Overview of Main Proofs
Characterization of Identifiability (Theorem 3.1)
4.2
Main Algorithmic Ideas (Theorem
5
Conclusion
10
Proof of Theorem 3.1 (Characterization of identifiability for convex partitions)
17
A.I
Flatness Variance Projections
17
A.2 From Unit Variance to Slabs (Almost Everywhere)
18
A.3 Converse: Parallel Slabs (Almost Everywhere) Are Identifiiiee
20
Proof of (Theorem 3.2) (Coarse Mean Estimation Algorithm)
B.
Projection Set & Local Partitions
22
Convexity and Local Growth of Log- Likelihood Under Convex Partitions
23
B.3
Bounding the Second Moment of Stochastic Gradients for Local Partitions
24
Projected Stochastic Gradient Descent for Local Partitions
B.5
Reducing General Partitions to Local Partitions
25
B.6
Gradient & Hessian Computations
25
PSGD Convergence for Convex Functions Satisfying Local Growth
26
Log-Concave Sampling over Convex Bodies
27
D.I Removing Assumption for Closed Convex Sets
28
D.2 Removing Assumption I for Polyhedra
28
Algorithm for Linear Regression with Friction
29
E.
Projection Set & Local Partitions
30
Convexity & Local Growth
Bounding the Second Moment of Stochastic Gradients
32

---

E.4
One-Pass Projected Stochastic Gradient Descent for Functions satisfying Quadratic
Growth
33
E.5
Putting It Together
36
Simulations on Variance Reduction
37

---

Published as a conference paper at ICLR 2026
A PROOF OF THEOREM 3.1 (CHARACTERIZATTIO OF IDENTIHABILITY FOR CONVEX PARTITIONS)
In this section, we prove Theorem 3.1 We will begin with a restatement of the result.
Theorem 3.1 (Characterization of identifiability for convex partitions). Fix any μ²' E R2 A convex partition l of Rd not information preserving (i.c., not identifiabl; Definition 2 with respect to μ² if and only if there is unit vector E R such that almost every P P is slab in direction v.
Before outlining the proof, we remark that an equivalent definition of being slab in direction v that more convenient work with is that there rotation (orthogonal linear map) : R2 Rd
with Re such that
RP R S
for some S Rd-1
Outline. We prove Theorem 3.1 by considering both directions of the implication. The first direc- tion shows that if the mean non-identifiable, then, outside a null sub-family sets, each e P must be slab. This can be broken down into two steps.
1. Unit variance on partition P. First, we show that non-identifiann non-identifiability forces the population neg- ative log-likelihood to have a "flat direction"" along which the value of the log-likelihood does not change. Next, we show that along this direction, say the variance of the one-dimensional projection (u, x) under the truncated Gaussian N(u*, P) equals for almost every P (i.e. the union of sets P E S violating this requirement has measure 0).
2. From unit variance to slabs (a.e.). Second, we show that the unit-variance condition implies that almost every E J is a direct sum of the form Ru Cp, i.e., slab. This step uses the equality case of the Prékopa-Leindle inequality established by Dubuc (1977).
The other direction shows the converse (and easy) direction: almost every set is a slab along some v, then the coarse distribution invariant under shifts by lu, identifiability fails.
A.1 FLATNESS VARIACE PROJECTIONS
First, we observe that non-identifiability implies that the population negative log- log-likelihood is "flat" some direction u.
Lemma A.1 (Zero directional Hessian). Let L(x) Ep-No(u log No (m, I; P)). Suppose p²ーp" there exists po F 4² with () = No (n", I). Then = || V ((x(((()))) 0.
Proof. Since J is a convex partition, L is also convex (ootaiis et al. 2021 Hence, the restriction
g(t) L (n= + t(uo 1²)) is convex. Since g(0) = g(),, g is constant over [0, 1]. In particular, (0) O, which is exactly u 2 ((x))u 0.
Next, recall that the Hessian of the negative log- lilkikiiioodd has the following expression (Fotakis ct al. 2021)
E P~Nala .1) L.NN
Cov [x]
(3)
Combining n² with Lemma A.I yields
E P~Na(u Z~N L.P)
Var [(u, x)]
(4)
For convex P, the one-dimensional variance reduction (e.g., via Brascamp-Lie Lieb in ID, see
Lemma A.4) gives
Var N J.P)
(K, x)) S
(5)
Let B he the set of non-slabs in P. "Almost every" means that the volume of Upen P is
17

---

Published as a conference paper at ICLR 2026
Since 4 is the expectation of [0, 1]-valued random variable, conclude that equality in (5) holds for No (μ², almmmosst every set P. Equivalently, the sub-collection sets with strictly smaller variance has mass O. We record this in the following lemma.
Lemma A.2 (Unit variance for almost all sets). Suppose there exists nm + p² with Nz(po, = No (I",I). Then there exists 8 such that
Var [(u, x)) = 1 for almost every P E P. z~N PPP)
Equivalently,
(I =0 where S 5- PEP:
S={PED:
ZmN b [(u, [uu <
Var
A.2 FROM UNIT VARIANCE TO SLABS (ALMOST EVERYWHERE)
Next, we use the observation from the previous step to show that almost all P E must be slabs.
Fix the unit vector furnished by Lemma A.2 Rotate coordinates that e₁ and write (y.z) E R x u=, jtt = (4i, 1.) ). For set PE P, define the set Cp and its Gaussian weight Wp
Wp(v) = J.a (cp(( Pa-1 pT) dz,
Cp(v)= = E EP;
where (w) c - is the (d 1i-mmennsional standard Gaussian density. The law of y = (u, r) under I ~ N(A", ,I has density
Zp / [Wp(t) pi(t -i) mi) dt.
fe(v) = WP()) PI wi), Zp
(6)
We observe that Wp(-) is log-concave function. Lemma A.3. Wp(+) is log-concave.
Proof of Lemma
A.3 Consider the following density over (y: z)
α (y, (F; Td-1)
This is log-concave because both (y, and (-(-) are log-concave; the former because P. is convex set. The log-concavity of Wp follows since is a marginal of the above density on y, and log-concavity is preserved upon taking marginals.
We will need the following one-dimensional variance reduction inequality and its equality case. Lemma A.4 (Lemma 4.8 in (Vempala 2010)). Let N(u, o²) and W R - [0, oo) be log- concave. Let Yw have density proportional W μr, o²). Then
Var (Yw) 2
Moreover, equality holds if and only if supp W IR. and W constant IR.
We note that Vempala (0010) proved the case for = 1, but the proof holds for any a > 0. Moreover, they stated Lemma A.4 for the case Yw centered. This is without loss of generality since the LHS variance is shift-invariant so we can consider the shifted function W + E[Yw]) and
shifted Gaussian Y' ~ N(u E[Yw], We now apply Lemma A.4 to each set in the full-mass sub-family given by Lemma A.2
Lemma A.S (Constant slice weight for a.e. set). Under the assumptions of Lemma A.2 for almost every e P, there exists ep (0, 1] such that Wr(y) = cp for all y E R.
Proof. Fix such P. By 6 and Lemma A.2 Var (y) = 1. Apply Lemma A.4 with W Wp: since Wp is log-concave, equality in Lemma A.4 implies that Wp is constant, and the support must be all of TR. Denote the resulting constant by ep.
18

---

Published as a conference paper at ICLR 2026
Next, show that the fact that Wp(+) being constant forces the set P to be a slab.
Proposition A.6 (Constant sections = slab). Assume P is convex and Wp(+) cp > 0. Then there exists a convex Cp S u such that
Cr(y) = Cp for all R and hence
P Iuu Cr,
i.e. P is a slab along u.
To prove Proposition A.6 we use the following equality case of Prékopa-Leinee inequality due to
Ball & Böröczky 2011 Dubuc 1977).
Theorem A.7 (Prékopa Leindler Inequality, e.g., Theorem 1.1 in Cordero-Erausque & Maurey 2016 Let f,g, h: Rd + [0, oo) be measurable. Suppose that for some (0,1) and for all Rd.
n((1 t)x + ty) 2 f(x)' "(1)"
Then
(z) (L)
(p
Further, if equality holds above, then there exist w E Rdd, a O, and a log-concave &b such that, a.e.,
( -bbxx tw), p(u) = a a'-' + (1 t)wo),
and h(2) = (x2).
=
Proof of Proposition A.6 Fix y1 82 E IR, define yt = (1 f)y1 + ty2. = Cr(y)). B Cr(y2).
and M, (1 - A tB.
First, because convex, we can show the following.
Lemma A.8. Mc S CP()).
Proof. To see this, consider any E Cp(y)) and 22 Cp(u2). then (v1, æ1), (y2, x2) E P; by convexity, (ye, (1 l)z1 (z2) E P. iee. (1 - l)21 + lāg Cp(w).
Next, because Pa-1 is log-concave, Prékopa Prékola-Leindler Leindler (Theorem A.7 yields the following:
Lemma A.9.
f pu-1 2
1-6
[/e
Pd-1
Proof. To see this, let ff 1Afd-1, 1p and h 1M u- For x E A, y E B we have (1- t)r ty E Mc, so 1.M ((1 t)x + ty) 2 1z(z)'
Since Pa-1 is log-concave, (Pa-1((1 t)z + ty) 2 Pa-1 (z) (x)=_(pp---_- "pa-i()) Multiplying
gives the premise of Prékopa-Leindler inequality for h) (see Theorem A.7 and using the Leinder inequality yields the claim.
Combining Lemmas A.8 and A.9 with Pd-1 > everywhere yields
[
Lemma A.S
Lemma A.9
( (a-1))))) 1-1 "/ Cr(vz)
pa-1)²
Pd--
Pd-1
(7)
Cr((e)
Mr
(To the last equality, note that Wp(y) -Scpto Pa-1 and Wp()) cp.)
19

---

Published as a conference paper at ICLR 2026
Since the leftmost and rightmost terms in 7 are equal, both intermediate inequalities equalities. In particular, (B() \ Mt has Gaussian measure (with respect to (P-- dz).
Now use the equality case of Prékopa-Leindlee to conclude. By the equality case (Theorem A.7 there exist w E u a > O, and a log-concave & such that a.c. on u
ʃ = APP-- = A 4/( -ww,,
h = 1M - g = nip = - 1b( (b( -1(1-)(11)))))
(8)
This, in particular, implies that = C - tu and = (---t)) for == supp(())) and, therefore,
M, = (1 A A tB (1 () + tw) t(C (1 (1-t) C.
Hence, by 8 v 1 C (a.e.). Therefore, for any C + tw A,
( f2) a- 00= tw) a² Pa-1(2 tw),
Le. Pd-1 = P (w) on C. + Iwe for a= > O. Hence, the map + log pa-aa-110 (2)
log 12 - (w) must be a constant on C. However, by definition of (p))
- log (d-1(()) log Pa 1 (z-tw) tw) = -1 Tu tuo²) = -t (z - n1, w) |w/2
1-1
w. Thus, if w * O, it cannot be constant on any set with nonempty interior. But C' has nonempty interior: indeed WI(1n) = Scr(p.) Pa-1 cp 0 and Cr(y1) is convex, hence it has positive Lebesgue measure and nonempty interior, so int(C) * Ø. Therefore w 0, and consequently
affine with gradient -t w.
Cp(wn) = C + tw == C 1)w0 = CP(22)
Since this holds for all y1, V2. there exists a convex Cp S with Cp(v) = Cp for all y. This implies the desired claim:
P= (1,,2) y E E Cp} Ru @ Cp.
Combining Lemma A.5 and Proposition A.6 with Lemma A.2 shows that almost every set P is slab along u; equivalently, the sub-family of non-slab sets has coarse mass O.
A.3 CONVERSE: PARALLEL SLABS (ALMOST EVERYWHARE) ARE IONNIEENT
Assume there exists 1 and sub-family n C S with
No (1²', 1) (M)) 0 such that
P is slab along v for every P E P PP An.
We show that Ng (14, 1) = No( + to, T) for all E Rd and f E IR, hence identifiability fails.
Because the Gaussian densities da(- - μ) are strictly positive for all μ., the statement Ng (u",/) (M) = 0 implies that Upen P has Lebesgue measure 0. In particular, No (u, Z) (7) = for every μ.. Thus, intuitively, the sub-family 71 does not affect the population negative-log likeli- hood for any μ. Hence, roughly speaking. checking non con-ideniifiability for P reduces to checking non-identifiability for the sub-pau partition 8 p M1 denoting the slab sub-family, For this sub-famil familymily non-identifiability easily follows due to symmetry along the "slab direction." In the remainder of the proof, we formally prove this.
Towards this, rotate coordinates so that = and write x (y, 2) E R x vー and = (Mey HLL) For any slab cell P = x Cp with Cp C -ー convex, the Gaussian factorizes:
dalI 4) = Φi pw) Φs-1(2 - -M1).
Hence
No I;P) | (i (w)) dy S da-i p1) dz / [cp
Φd-1(= - m1) dz,
which is independent of pv. Therefore, for every E R.
No (1 + tv, I; P) No (1, I; P) for all
PE01 n.
20

---

Published as a conference paper at ICLR 2026
For any (measurable) collection 7 P, set
Ux = PEanS PC Rd Then the Lebesgue measure of Na and, by the product form of the slabs in S,
and
Na == -=UPERM P.
U2 Ru @ (UPExTS CP):
Let UCp denote UPEænS Cp. Thus, for any a and & R.
No + to, = S dalæ (u + tu)) dr + / Nx
ds(x (u+ tt)) da
Jux
/ bily (Mo + +t] dy I dd-1 Mil dz
Jucp
No (1, ()7)
since (1))) dy = Because this holds for every A, the pushforward measures coincide:
N2 (p, for all e R.
Therefore, shifting l along leaves the coarse distribution and, hence, the negative log-likelihood unchanged, leading to the failure of identifiability.
B PROOF OF (THEOREM 3.2) (COARSE MEAN ESTIMATION ALGORITHM)
In this section, we provide our efficient algorithm for coarse Gaussian mean estimation under convex partitions. We begin by formalizing the input of the algorithm more generally sampling oracle, which can be implemented in polynomial time given a set of linear inequalities.
Assumption (Sampling Oracle). There is an efficient sampling oracle that, given R > 0, P E P, and a parameter μ. E2d describing a Gaussian distribution, outputs an unbiased sample N, (0, R)).
In light of Assumption [ we now understand the input size as natural measure of the complexity of the coarse observations (polytopes): the fucet-complexity ? The running time of our algorithm will depend polynomially on the facet complexity of the observations. We note that this recovers the case when the coarse observations are encoded as a set of inequalities since the length of the encoding provides upper bound on the facet complexity.
Next, we restate Theorem 3.2 the desired result, for convenience below.
Theorem 3.2 (Coarse Mean Estimation Algorithm). There is an algorithm that, for any true mean u E dd with ||xt D and any partition P that is convex and a-information preserving with respect to n* (Definition 3 gets as input the desired accuracy and confidence e, (0, 1), draws i..dd coarse Gaussian samples from P, and outputs estimate ç satisfying
1
121 S
with probability The algorithms uses
log 1/8 (dD'log
d log 1/8
m =
a
a=g2
coarse samples and runs in time polynomial in and the bit complexity of the coarse samples.
A few remarks about the assumptions in Theorem 3.2 are in order.
Definition 6.2.2) of a polytope is natural measure of the complexity of the polytope. See Appendix D for the formal definition and more details.
9The facet-complexity (Grötschel al. 1988
21

---

Published as a conference paper at ICLR 2026
Remark B.1. Assumption 1 can be further relaxed and is only stated for the sake of simplifying our presentation. For example, in the case where each P E J is a polyhedron, we can remove Assumption by implementing sampling oracle that terminates in polynomial time with respect to the complexity of the input polyhedron. See Appendix D.I about general convex bodies and Appendix D.2 for more polytope-specific details.
In addition to information preservation of the partition of IR and the simplifying Assumption | our algorithm assumes the given partition is convex and that we are provided bound the norm of the true mean parameter. The convexity of the sets are crucial in order to argue about the convexity of the negative log-likelihood objective, but our algorithm is able to handle the case je¹ E B(u D) via a translation the space. Moreover, our algorithm can tolerate μ** E B (u(0) D), e.g., when we are provided a single fine sample y1()) ~ N(u", ,,,,,, I), but for simplicity, we state our results using the Euclidean distance.
Proof Overview Our main workhorse is variant of projected stochastic gradient descent (Theo- rem C.I. In order to apply call on this general result, we need few ingredients.
Analyzing the likelihood function over all Rd and for all partitions is challenging. Thus, we impose a feasible projection set and consider a slightly restricted class of convex partitions in Appendix I.I The latter is used solely to facilitate analysis, and our final algorithm holds for general convex partitions.
In order to show that the iterates of gradient descent converges Euclidean distance and not just in function value, we show in Appendix [B.2 that our function is convex and satisfies local growth condition. This is a strictly weaker condition than strong convexity.
Next, to bound the number of gradient steps, we design a stochastic gradient oracle and bound its second moment in Appendix B.3 Here, we crucially use properties of the local partition.
Appendix B.4 collects the ingredients we discussed above to derive an algorithm for the afore- mentioned restricted convex partitions.
Finally, Appendix B.5 reduces the case general partitions to the case of restricted partitions.
Appendix B.6 fills in the gradient and Hessian calculations that were deferred in this section.
B. PROJECTION SET & LOCAL PARTITIONS
To be able
PSGD the negative ligllikelihood, we need to obtain stochastic gradients for Lp as well as bound the second moment of the stochastic gradients. This is not straightforward since the inner and outer expectations in the gradient expressions (Appendix B.6 are over different mean parameters.
To facilitate the analysis, first impose projection set K, over which ensure a trivial bound on the distance of the current iterate to the true solution. Our projection set K is defined to be
K K= k== 11Al22 S DD..
where 1) is the assumed bound the norm of the true mean. We certainly have n² E K and can efficiently project onto K.
Furthermore, first analyze idealized class of partitions and derive an algorithm that recovers the mean under this ideal situation. Then we show that we can implement this algorithm using samples from the actual class of observed partitions.
Definition (R- Local Partition), Let R > 0. We say partition O of Rd is R-local for any P e P that not a singleton, C Boo (0, R).
22

---

Published as a conference paper at ICLR 2026
B.2 CONVEXITY AND LOCAL GROWTH OF LOG-LIKELHHOOD UNDER CONVEX PARTITIONS
It can be verified (Appendix [36) that the coarse negative log-likelihood of the mean under canonical parameterization is given by the following
Lo(u)= = Σ N(p" Pp))))))) where Lp(u) = llg (N((,, PP))
(10)
PEN
We also have the following expressions for the gradient and Hessian of Lg.
V Lo (p) = 1
E
E [x],
P-NNop' .)) NP...P)
2 Lo (p) = I
E PoNall .I) pI.IIP
Cov [xr]
Fotakis et al. (2021) show that V2 Lp(u) 2 0 when each P E SP is convex by leveraging a variance reduction inequality, which implied by the Brascamp-Lieh inequality (see e.g., Guionnet (2009;;
Hargé )2004) and showing that each Lp is convex.
Proposition B.2 (Lemma 15 in Fotakis et al. 2021). Let P S Ed be conver. Then CoVNUaIPP)
[x] 3 I, and in consequence, Lr(p) convex as a function of μ.
To recover μ²",, one sufficient condition is to check that Lo satisfies a local growth condition (Defi- 66. We show this in the next lemma via a connection between the log- log-likelihood objective and of P.
Lemma B.3. Let (P be a convex a-information preserving partition of Rdd The negative log- 2n²
likelihood function function Lo( (Equation 10 satisfies
/2a
-local growth condition.
200
6002
We note that similar statement is proven by Kalavasis et al. (2025) However, their definition of information preservation (Definition 3 is slightly different in that they directly assume the coarse total-variation distance is lower bounded by the parameter distance. Thus, their analysis skips the need to relate non-coarse Gaussian total-variation to parameter distances which is necessary for us.
Proof. Assume that a-information preservation (Definition 3 holds. The proof relies on tight characterization between the TV distance of a Gaussian and its parameters due to/Arbas et al. (2023 Theorem 1.8): For any μ1; μ12 E Rdd such that dNv(N( 7) N(u2, 1)) < 1/600.
|| M2ll2 S d N(22, I)) S /2 11 - 122122
200
2a² For any μ E Rdd such that L(x) _(x²))
6002: have
1 "00,"1100 (]) < dTv(NNo (m, D,,oo No (p",1 I)) dTv(N(H,)) N(,"
1
<
KL (1,, T) IIN (wr, T))
(Pinsker's inequality)
a
[1() - 2(1[11
2
600
follows that the characterization above applies and can lower bound the KL-divergence using the parameter distance:
L(w) 2(x)= - KL (u, 1) IINo (p", ,))
(Pinsker's inequality)
2 2 dTv(No (p, 1), (1*, I))² > 2a² dTv(N(u,,) N(x", !))? 2a²
2002 || 11 101132
23

---

Published as a conference paper at ICLR 2026
B.3 BOUNDING THE SECOND MOMENT OF STOCHASTIC GRADIENTS FOR LOCAL PARTITIONS
We will prove the bound on the second moment of the stochastic gradient for R-local partition. We will then show how to deal with a general partition.
Lemma B.4. Suppose I is an R-local partition of Rd and |||^|12 S. D. Given E K in the projection set (Equation (9), there an algorithm that consumes a sample Ng (μ², I) and makes a single call to the sampling oracle (Assumption [ to compute unbiased estimate g(1) of
V Lo (p) (Equation (10) such that E [|((4)]1 = + dR²).
Recall that the gradient of the log-likelihood function is of the form
E
E [x]]
P~Nala JI Mp.PP)
The first term in the gradient expression is simply our current iterate for the mean and we obtain unbiased estimate of the second term by sampling y N(u, T, P) where P is fresh observation.
Proof.
The second moment of the gradient oracle can be upper bounded by
|1 + 2 PaNalja () M).,P)
||0||
The first term is at most 2 and the second term can be upper bounded as follows.
E P~Noll" .I Nu.IPP)
E
||=1]
E
I
||0|| (0.R)
E P~Noluu .I x~.11,
[|al] X
P-NNol .I x Ma.
||0112 (0.
P~Nalu (I) Z~ (.P) ||x11 XB_ (0.
E
P~No(u 1I IPP
In the last step, we use the fact that S is an R-local partition that every set such that Pr (0, R) #
a singleton. This allows us replace the expectation over each N(H, P) in the second term with an expectation over N(H", I, P), as the distribution consists of a single point. We can then bound the first term using a deterministic bound and the second term using the second moment of N(u".. I).
||-1/2 (0.
|1==12 (0.
E P~Nolp' .I) NP..IPP)
E
E
PWNol' D) (IPP)
S dR²
E
[1011]]
N~N
dR² + d 1
O(dR² + D²).
B.4 PROJECTED STOCHASTIC GRADIENT DESCENT FOR LOCAL PARTITIONS
Having ensured bound on the second moment for local partition, we can now run the iterative PSGD algorithm for functions satisfying local growth (Theorem C.I. Applying its analysis with the ingredients above yields the following result.
Proposition B.5. Let E 1). Suppose SP is a convex R-local a-information preserving partition of IRd and ||~") l| < D. There is algorithm that outputs estimate ji satisfying
p 1 112 S
24

---

Published as a conference paper at ICLR 2026
with probability 1 6. Moreover, the algorithm requires
d.R² D
dRD sô
m =
a²
log"
samples from No (u², 1) and poly(m, T.) time, where T. is the time complexity of sampling from Gaussian distribution truncated to P n B (0, R) for some P E P.
Proof. We call Theorem C.T The initial function value bound can be taken as Eo DG with any
initial value Noo E (00, D), where G² =2=0(1) + df²² is an upper bound on the second moment of
the gradient oracle (Lemma B.4]. In order recover μ² up e-Euclidean distance, we would like
an O(a"=")-optime) solution in function value. In order to obtain the high probability bound, we repeat Theorem C.I
few times and apply the clustering trick described in Remark C.2
B.5 REDUCING GENERAL PARTITIONS TO LOCAL PARTITIONS
We describe how to remove the assumption of the partition being R-local and prove Theo- rem
Consider general a-information preserving convex partition s and P Ng (n", .I. Since ||="||> I ||p² |l S D, setting R D + Olog md/s) means that any m-sample
Proof of Theorem 3.2
algorithm will not observe a sample P such that Pn B (0, R) with probability 1 1-8. Define the partition 0 (R) of dRd given by
(R) (Pn B (0, R) : PD: B (0, R) + 2 {{x) : B R))
Since (RR is refinement of P, it must also be a-information preserving. Consider the set-valued algorithm F: 0 > (R) given by
P { Pn B (0, RO, [x) for an arbitrary x E P. Pn B (0, R) Ø
Pn Bx (x, R1) 20
By the choice of R, with probability 1 - 6, any m-sample algorithm will not distinguish between samples from Nœ(R) (u",), () and F(P) for P ~ No (n", I). Moreover, we can sample from P n Bo (0, R) as Assumption [ Thus we can run the algorithm from Proposition B.5 with input samples ((P) for P No (I",
We can further improve the sample complexity by rumning the algorithm in stages. The first stage aims to obtain an ((1) -distdiit warm start and the second stage aims to recover the mean up to accuracy This yields the proof of Theorem 3.2 Indeed, the only missing detail is an efficient implementation of a sampling oracle (Assumption As mentioned, we defer these details Appendix D.2
B.6 GRADIENT & HESSIAN COMPUTATIONS
In this section, we fill in the gradient and Hessian calculations for the log-likelihood function for coarse mean estimation under a general convex partition. Lett L:: Rd 1R20 denote the negative log-likelihood function for an instance of the coarse Gaussian mean estimation problem. Similar calculations are presented by Fotakis et al. (2021); Kalavasis et al. 2202)), but we include a self- contained proof for completeness. L is defined as follows
L (p) P~No(M
E |- log (N(p,
We first compute the function derivatives.
Fact B.6. It holds that
L (1) E [x]]
E
E
[x]
N(a.))
P~No(l" .) N,,,1
2 L (1) = Cov [x]]
Cov
[x]]
-Na.))
25

---

Published as a conference paper at ICLR 2026
Proof. We can write the log- likelihood as follows
L(x)
Σ PED
N(p", T: P: Lr(m), where Lr(n) log (N(H, I; P))
(11)
Due to the linearity of gradients, it suffices to compute V Lp(u, T) and V Lr((()) for each P E P to obtain the gradient and Hessian of (-). Toward this, fix any P E P. Observe that
Er(n) = log SNERd e ((--)) (x-
JZEp - (w- (x-a)dr log JaERU e 111=113 dd
- "dd
Write [(::)) = exp (- |1:11 2/222 + xT x.) follows that
V Lp(u) = Sps [Jan VD(P - S0g VnA
SR
f)
S V
VP
(12)
SR+ S
SP
Simplifying the expression and substituting the values of J, V gives
Lp(n)
E [x]]
E
[r]
Na.1)
Substituting this in Equation gives the desired expression for V Vv,(v.))
To compute V LL(HH, we differentiate Equation 12
V Lr(m) = (pr. V² NWS f) Spe VSU V
Spp (N - (Sp VDU VD
Uga f)2
()
SEs V V Jgs f
(Jzu VN( VUT
VAV'S
Upr VDU VN
Spf [
(gaa
(pp
This simplifies the following
2 Lp(H)=
xx
E N(H.))
[x]]
[xx
"]
E
[x]]
NI,.)
N).
NPP.l)
N.P.H.))
N(P.H..)
final simplification gives
2 Lr(p)
Cov N1,,1)
[x]]
Cov [x]] N(P...1)
Substituting this in Equation
gives the desired expression of (1)).
C PSGD CONVERGENCE FOR CONVEX FUNCTIONS SATISFYING LOCAL GROWTH
In this section, we state the variant of gradient descent we use to optimize the various likelihood functions in our work. In order to establish the sample complexity and computational efficiency of our main algorithms (Theorem 3.2 and Theorem (.3), we require convergence guarantees for projected stochastic gradient descent (PSGD) over functions that lack global strong convexity. To address this, we leverage local growth condition (Definition 6.. which our coarse negative log- likelihood functions satisfy under appropriate information information-preservatioo assumptions. We subse- quently present an iterative PSGD convergence statement (Theorem C.I for convex functions en- dowed with this local growth property.
Before formally doing so, state some useful definitions. Consider convex function F: K - R with a global minimizer w* on convex subset K C Idd. We write
Sp = (w E K: F(w)= F(w") < p}
to denote the e-sublevel set of function F where F is clear from context.
26

---

Published as a conference paper at ICLR 2026
Definition 6 (17Local Growth Condition). condition if
We say that F; K - R satisfies (n, p)--cclll growth
|/e - w w0ll2 = (F(w)) F(w"))
for every w E Sp-
We remark that function satisfying (no, loocll growth condition also satisfies (n) p) local growth for every E 7o). E (0, An]. We also note that our log-likelihood function for a- information preserving partitions satisfy 200 600
2 2n²
)local growth condition (Lemma B.3
Our efficient coarse mean estimation algorithm uses the following result due to Kalavasis et al. 2025
Theorem C.1. Let F: S S Rd + be convex and satisfy (17, El-local growth condition (Defini- tion
Suppose we have acccess an unbiased gradient oracle g (w)) such that [| S
Suppose further that we have access to an 86-optimal solution (() E S. There is an algorithm that queries the gradient oracle
o 'og
(
G 112E
(EE
(EO
times and oulputs 28-optimal solution with probability 0.99.
Remark C.2 (Boosting without Function Evaluation via Clustering). For function satisfying (n.c) local growth condition, it suffices to apply Theorem C.1 and compute O(r) ) --optimal solution w in function value to ensures that w w=112 S E. Note that this procedure succeeds with probability 0.99.
In order to boost the probability of successfully recovering w², a standard trick to repeat the algorithm (loo({/))) times and output the solution with smallest objective value. However, do not have exact evaluation access to the log-likelihood functions we wish to optimize. Daskalakis et al. (2018) Section 3.4.5) demonstrate "clustering" trick to avoid function evaluation. Suppose we repeat the algorithm in Theorem C.1 (1og('/)))) times. A Chernoff bound yields that with high probability, at least 2/3 of the outputted points s-close w* and thus are 2s-close each other. Thus, outputting any point which is at most 2e-close to at least 50% of the points must be at most 3s-close w
D LOG-CONCAVE SAMPLING OVER CONVEX BODIES
In this section, we review well-known results about sampling from log-concave density & e-f constrained convex body K, under mild assumptions. We use these results implement the sampling oracle (Assumption) [ in Appendix B and the friction sampling oracle (Assumption) in Appendix E
Our stochastic gradient descent algorithms for coarse mean estimation (Theorem 3.2) and linear regression with friction (Theorem 3.3 rely on samples from truncated Gaussian distributions to compute stochastic gradients (Appendix B.3 and Appendix E.3 Here, we provide the technical statements that justify these algorithmic sampling oracles. Specifically, we first state a general hit- and-run sampling result for arbitrary convex bodies (Theorem D.I). We then show how to instan- tiate this general result to remove our idealized sampling assumptions for closed convex sets (Ap- pendix D and polyhedra (Appendix D.2). thereby fully validating the computational efficiency of our primary estimation algorithms.
Concretely, we have convex function f: K F that is bounded below, say there is some x* K such that f(x) 2 f(x") for all x E K. Note that x= exists and belongs K since K closed.
One option for this task is the class of Langevin Monte Carlo methods (Brosse et al. 2017 Bubeck et al. 2018 Dalalyan& & Karagulyan 2019 Lamperski, 2021 Ahn & Chewi 2021). 1). which requires first-order gradient access the log-density function. A more general tool for this purpose is the "Hit-And-Re Markov Chain Monte Carlo (MCMC) algorithm due to Lovász Vempala (2006a), which only requires minimal zero-order access.
27

---

Published as a conference paper at ICLR 2026
Theorem D.1 (Mixing- Time of Hit-And-Run Markov Chains; Lovász & Vempala (2006b a)). Con- sider a logconcave distribution ς x e over a convex body K. Suppose we are provided the following.
(S1) Zero-order access to
(S2) Membership access to K.
(S3) A point (0)) and constants R 2 r such that B2(x(0), ,r) C B2(x9,
(S4) A bound M 2 max,EK f(x) - f(x)))(x')
Then, there is algorithm that makes
O polylog(( (d, M, R/r,
membership oracle calls to produce a random vector within 5-TV distance of f-
To implement the desired Markov chain, need Assumptions (S1) (S4)) stated in Theorem D.1
We remark that Assumption (S2) and Assumption (S3) can both be implemented given separation
oracle K. If also know that is L-LLipschizz or f-smooth, we can take M = LR or M 3RR2
respectively, for Assumption (S4) The smallest ratio R/r of values r, R from Assumption (S3)
depends on the structure of K. For the simple case I-dimensional intervals, we trivially have R/r- 1. For all d-dimensional Ly-balls, we have R/r = poly(d).
D.1 REMOVING ASSUMPTION 1 FOR CLOSED CONVEX SETS
For partitions containing general closed convex sets, the sampling oracle assumption (Assumption T from coarse Gaussian mean estimation algorithm (Appendix B) can be relaxed to Assumption below.
Assumption (Well-Bounded Set). Each set P P is closed convex set and is encoded as:
(i) the dimension = dim(P) of the affine hull of P,
(ii) a separation oracle.
(iil) numbers R with the promise that P B R) + Ø, then P contains an inner ball P P2 (k) (z, for some E (k) (0, R).
Here BB (..)) denotes the k-dimensional L.g-ball with given center and radius.
Assumption allows for unbounded convex sets while ensuring that we can call on Theorem D.I with the bounded convex body K P n ((k) (0, R + rvd). which contains most of the mass of P for sufficiently large R. This is because we are guaranteed the existence of an (unknown) inner ball (2(x r) C K. We can further approximately find such a ball using the ellipsoid The overall running time to obtain an 5-approximate sample in total
method (Grötschel et al. 1988).
variation distance is thus
poly (ke, log( (og(R// R/r), log(1/))
In our mean estimation algorithm (Theorem 3.2 we may wish to sample from the set Pn (O, R') for some other R' < R sufficiently large. This can be implemented via rejection sampling from P. (0, R) assuming the mass of B. (0, R') is sufficiently large.
D.2 REMOVING ASSUMPTION FOR POLYHEDRA
In the case the partition consists of polyhedra, the sampling oracle assumption (Assumption T from our coarse Gaussian mean estimation algorithm (Appendix B can be relaxed to Assumption below. Before stating the exact assumption,
state natural notion of the complexity of polytope.
Definition (Facet- Soicet-oomplextt),. We say that a polytope P C Rd has facet- cocct-complextty at most Cp there exists system of inequalities with rational coefficients that has solution set P and such that
the bit-encoding length of each inequality of the system is at most pp case P = Rdd, we require
Pp 2 1
28

---

Published as a conference paper at ICLR 2026
We now ready to replace Assumption 1
Assumption 3 (Well-Described Polyhedron). Each observation P E P is a polyhedron and is provided in the form of a separation oracle and an upper bound pp the facet complexity of P.
The running time of our sampling algorithm then depends polynomially on the running time of the separation oracle as well as the facet-compil facet-complexity yp of the observed samples P. Indeed, let us check that Assumption Blllows us to apply Theorem [D. is clear that Assumption 3 iimeedittlly satisfies Assumptions (S1) and (S2) We sketch how to address Assumptions (S3) and (S4)
First, note that we wish sample from the truncated standard Gaussian N(u, I, P Bx (0, R)). In particular, it has density that is -mmoohh. Since R = poly(d, D, log(//)) is polynomial of the dimension d, the warm-start radius D. and logarithmic in the inverse failure probability we can take M O that Assumption (S4) is satisfied.
Next, we can again use the fact that we sample from polytopes contained in Bx (0, R) to deduce that Pn 8xc (0, RR is contained in an L2 ball of radius Rvd. Moreover, the facel-complexity of P E 3 (0, R) is at most y draw on (Grötschel et al. 1988
pp + log, R). On the other hand, to handle the inner ball, Lemma 6.2.5) which states that a full-dimensional polytope with facet-complexity must contain a ball of radius 2- 7 In the case that P n B0, R) is full- dimensional, this suffices to run the Markov chain from Theorem D.1 in poly (p) time. If P not full-dimensional, we can exactly compute the affine hull in polynomial time using the ellipsoid algorithm (Grötschel et al. 1988 (6.1.2) and then apply the full-dimensional argument on this affine subspace.
E ALGORITHM FOR LINEAR REGRESSION WITH FRICTION
In this section, we prove the main result on linear regression with friction (Theorem presenting the result, we define the formal model and state our assumptions.
Before
Definition 8 (Linear Regression with Friction). Let c R - IR be given friction function and w Idd be the unknown linear regressor. n observations (Is, zi) are produced as follows:
1. The features I; E &R are arbitrary.
fribbserve)fricttoooness 2. Each (unobserved) frictionless output satisfies = x w² + E where & ridd N(O, 1).
3. Observe the outputs with frictfiitiin (I:, 2; = c(y.)).
The goal is to observations (x.,, = E [n] from Definition and estimate w" E Rd up to Lz-error E (the number of observations n will depend on 1/e).
Similar to the of coarse Gaussian friction are information theoretically impossible to solve. Hence, we define the following notion of information preservation that quantifies identifiability.
estimation, some instances of linear regression with
Assumption 4 (Information Preservation). Let P = (2) : 2 R) denote the partition induced by the friction function J is a-information preserving with respect to w* w²,x,,.... .I..... Fn for some 0 if for any w E B(, C),
dNv(No (x. w, 1). N2 (x.Tw, "0w"",)) (1)) 2 a d...dvvv(x( w. Nz, w", 1))
In order to obtain computationally efficient algorithms, we focus on the case where the friction function induces a convex partition of This analogous the case where we require the partition for coarse mean estimation to consist only of convex sets.
Assumption (Friction Function with Convex Pre-Image). The friction function c + R has convex (interval) pre-image c (z) C R for any R and we have access via pre-image oracle that outputs the boundaries a < b E RU { (-o, +oo) of the interval pre-image c (z) given some R.
We also impose the following standard assumptions for fixed-design linear regression, which appears even in the absence of friction.
29

---

Published as a conference paper at ICLR 2026
Assumption (Bounded Parameters). There constants C, EiE()) 2 = 1 ||= S C, and || I D for all i [n].
0 such that
For the sake of simplifying the proof, we further assume without loss of generality in Appendices E.1
E. that || & DVd I 1, by downscaling the covariates + 3i and upscaling the input w
within the loss function ((w)) + li(w Dvd). We undo this assumption in Appendix E.5
With the assumptions in place, we now state the main result this section.
Theorem E.1. Let (0, 1/30).. Consider an instance of linear regression with friction and suppose Assumptions to holds with constants b. C, D > 0. There is an algorithm that outputs an estimate i satisfying [ w" 1 S E with probability 0.98, Moreover, the algorithm requires
CDd ( CAAt
(CDd)
n =
log
observations and terminates in pnly(n, TT) time, where Ta is the time complexity of sampling from 1-dimensional Gaussian distribution truncated to an interval (Assumption 77)
We remark that Theorem recovers the required number of observations for ordinary least squares (OLS) without friction given a well-conditioned design matrix with smallest eigenvalue a²1? More- over, note that when the covariates
sampled from well-behaved distribution, e.g., isotropic Gaussian, we have D, b ((1) with high probability, which recovers the tight O(4/e)) sample complexity for Gaussian linear regression.
To simply our presentation, use the following simplifying assumption.
Assumption 11-Dimensional Sampling Oracle). There is efficient sampling oracle that, given an interval (a, b] C IR, and a parameter μ E TR. describing a Gaussian distribution, outputs an unbiased sample y N(u, 1, [a,
We emphasize that Assumption can be approximately implemented in polynomial time using Markov chains and defer the details to Appendix
Technical Overview Our main algorithm variant of gradient descent. This requires few ingredients, which we collect in the following subsections.
The iteration complexity gradient descent depends on the second moment of our stochas- tic gradient oracle, which is difficult to analyze for general friction functions. In Ap- pendix T. we define a feasible projection set containing w" and consider the slightly restricted class of local friction functions.
To ensure the iterates of gradient descent converge in Euclidean distance and not just in function value, we very that our likelihood function is convex and satisfies a local growth condition that is strictly weaker form of strong convexity.
Appendix E.3 describes a stochastic gradient oracle and develops a bound on its second moment for local friction functions.
Appendix E.4 specifies the one-pass variant of gradient descent we employ for sums of functions and proves its guarantees.
Appendix C.5 combines the ingredients collected throughout this section to derive an algo- rith for local frictions functions, Finally, the case of general friction functions is reduced to the local case.
E. PROJECTION SET & LOCAL PARTITIONS
We take the projection set to be
K = {w E Rd ||lll2 - CC
(13)
where 2 is the known constant in Assumption 6 and this set contains wn by assumption.
We can certainly efficiently project onto K
30

---

Published as a conference paper at ICLR 2026
As in the previous sections, analyze algorithm under the special case of low- low-probability sets being singletons. Then we reduce the general case to this special case. We say that a friction function is R-local for some R > if c (z)1 > implies that c (2) C [-R,, RJ. That is, induces partition of R that R-local in the sense of Definition 5
E.2 CONVEXITY & LOCAL GROWTH
Given n samples (11,21), (I2, 22). ... (Fnr zn), for each 1 S i S n, define
S S(z) = -
Recall that the negative log- likelihood of w: given an observation (z, 2) is
L(w; x, 2) log N ((S(z),x w; w;
Consequently, the log-likelihood of w over all samples
Lo(w) - 71 Σ
|- log N(S,, log (z,, w) 1)] - n1
Σ
E Na w1.1
Write Q(1) = No (ir. w0, 1). One verify that its gradient and hessian follows.
V Lo(w) 1
1
(x w)
I4
E
()
E u M a w.S.S.))
[e]]
24.
9()(()
2 Lg(w)
Σ
(x, T w) I,
Σ
E (()
1
Var u~N(a, w. w.
[u]
These are sufficient show that each and thus (.).) is convex. Indeed, conditioning on convex set S; E (RR) reduces the variance of the Gaussian distribution (Proposition B.2). It thus follows that Var [-> w,) [4] < and hence, V (-)(()) 0.
Lemma E.2. Suppose Assumption 5 holds. Then each and thus Lx(-) convex.
Since L(-) is convex, function value. Our next result shows that any w maximizing 2(-) is also close to w*.
hope to SGD to find parameter that minimizes _(.)) in
Lemma E.3 (Quadratic Local Growth), Suppose Assumptions 5 and 6 hold with constants b, C. 0, D Va and that c(-) is o-iifornatton-preseriinn with respect w and covariates
IT, 22........ Un (Assumption 4). Then L satisfies an (ab/200, /²t//000²) /0000))-occll growth condition (Def-
inilion
Proof. From the definition of the log-likelihooe it can be verified that
L(w) - I(w0)) = Σ KL (1rr, " NN (w),w), 1))
>
Σ dTv(No ((2,, w²) , 1). No ((a,, w) 1))²
(Pinsker's inequality)
n
2a
2 dTv((N ((1,, w*) 1) w) 1))² (a-information preserving)
n
If dT w²) 1). 1,,,N((( (x:,, w) 1)) is close to 0 for each i, then we can lower bound it in terms of the distance between the means (x,, w²) - (I,, w))l which, in turn, will enable us to get the required lower bound with respect to ||w w"ll, using Assumption 6 However, dNv(N(( w*) .1) ,1,, N((r,, w) 1)) is close to for all i. Instead, we show the following claim.
cannot guarantee that
31

---

Published as a conference paper at ICLR 2026
Claim E.4. Suppose Assumption 6 holds with constant b > 0. Fix any satisfying L(w)
L(w*) I 600
a²6". There is set C [n] of size at least (1 - 62 12)2) n. such that for each E
drv(N((zz, N),, w) 1)) v 600
Proof. Let T C [n] be the set of all indices E [n]] such that
1
drv(N( w=), 1) (21,,, w) 1))
600
Toward a contradiction suppose that [T' 2 nb² /2. Our calculations above imply that
2a
(2 a²bb
L(w) -(w")("")))))
|T
n
6002
600
This is contradiction and, hence, it must be the case that [T S / (2C).
Since w satisfies that [(w)- ((w)) We have
<
Goue
2
Claim E,4 is applicable. Fix the set T Claim E.4
2a²
L(w) l(w")
dTv(N(((n) (10,, w²), 1,,1))(((()) ( w.) 1))²
sET
Since for each T, (Tv(N(((;; w*) 1). ( w) 1)) S 600 Theorem 1.8 of Arbas et al. 2023) guarantees that every E (7) satisfies
dTv(N((a,; w²) 1),N)(((a) (,,,, w) 1))² (x.] (w -w"))²
2002
Hence, whenever L(w) [(w() < <0//800c we have
2a²
2a²
L(w) - (((w)) 2
(r_ (w - x²))² = (w - w²) (w))
Σ xeae
(w w²)
20 n
200
iET
İET
Finally, the desired result follows because
Σ
T.T
1
Σ
T
72
n2
ET
ic|n
igT
n [T')
m 62
n
(as max; ||1i112 < 1, x.
3 -110;112
1. and
Eie(n) Iqa! T > no² 1)
8²
(as T = =11- n)
I
2
E.3 BOUNDING THE SECOND MOMENT OF STOCHASTIC GRADIENTS
The objective function L of the form
4(a w) Σ
E
w: S.)]
n :E[n]
n
S.
(e(n)
where the gradient of (x w) = Es, [x] S:)] is of the form
ex w) xi = 8,-0(1)
(w)
[
xz.
= w....
Here Q(1) No (2.7 (w,,)) 1) where P is the partition of IR induced by the friction function
32

---

Published as a conference paper at ICLR 2026
Lemma E.5. Suppose Assumptions 5 andd hold with constants b, C 0, Va and that is
R-local friction function. Given w EE K the projection set (Equation [3) and fixed covariate
Ts there is an algorithm that consumes a sample S; ~ No (ar w*, 1) and makes single call to the sampling oracle [Assumption] 7 to output random variable 9i such that
(i) g: an unbiased estimate of (.()) with Eigl =O(R² C
(ii g: = Ds is an unbiased estimate of V Rgs [x] w; St)] with E [1oc1B3] OR + C²).
Before stating the proof, we note an application of Jensen's inequality yields a corollary that 14 E c O C²). In other words, & is L-Lipschitz for O + C).
Proof. Given S; ~ 2(1), we can obtain a stochastic gradient for E by sampling u ~ N(x] w, 1, 1:), and outputting 9i (x) w w). Moreover, 9i = I2 is a stochastic gradient for Bs,)
[xx w; S:
To bound the second moment of g, we first note that
g' 2 w| + +2 2ulu
The first term can be deterministically bounded.
x w < ||0س| |1=:112 s C².
(|æ2112 S 1)
The second term can be bounded using R-locality as follows.
E
(1)0(1)
N
S.)
<
E
E
12
(Jensen's 's inquality)
(s)
u u w. 1.
E
E
1u12 -R..)
+
E
|n| R))n(-R,
(,0((1
N w1, 1,S))
(.)(() u> xz ,...,
E
E
|u112
E
E
|u|² Xs,n(-
8,~0(1)
8t-0(1)) x-) we 118))
(R-locality)
< R²² +
E
|u 2
u x w
= R +1+
1
w*
(second moment of Gaussian)
R +1+
Hence, the second term can be bounded by O(R² + C²). Combining the two bounds yields a bound on R
The bound on the second moment of gi == g: x; follows since ||0:||2 S 1.
E.4 ONE-PASS PROJECTED STOCHASTIC GRADIENT DESCENT FUNCTIONS SATISFYING QUADRATIC GROWTHI
One subtlety is that we are attempting to minimize an average of functions but we can only use each sample once to compute gradients. This is because only have access to single coarse observation S; for each covariate z, Thus, we need convergence analysis of PSGD under sampling without replacement, or, in other words, one-pass algorithm.
33

---

Published as a conference paper at ICLR 2026
Theorem E.6 (Corollary 1 in Shamir (016) combined with Theorem 3.1 in Hazan 2016)). Let F(w) 1 Lig(n Fi(w) be an average of convex functions F, K - over a closed comvex domain K C R.. Suppose further that F; f((x] w) and
(i) S C)O,C)
(ūi) Ji is I.-iipschitz
(ii)) | S for each E [ya]
(iv) have access unbiased gradient oracles 9i for & such that IE [[1s(())] & G2
Then after 1 < T S n iterations, projected stochastic gradient descent without replacement with constant step size y over a random permuttation of F; outputs an average iterate satisfying
C² + G 2(12 + V2 I
(F F(w)))
Vn
Here, the randomness is taken over the random permutation as well as the stochasticity of gradient oracles.
We take the functions ft [-C, - IR from Theorem
E.6 to be
f((u): (-~No [- log (S;, 1)]
E
For R-local friction function, O(R + C) using a similar calculation as Lemma E.5
bound the Lipschitz constant of each function by
One difference in setting compared to Shamir (2016) is that they assume access deterministic gradient oracles. However, it is not hard to see that the analysis extends to the case of stochastic gradient oracles.
Our first attempt would be to run the PSGD algorithm for sampling without replacement (The- orem E.6 For R-local partitions, we can bound the second moment of the gradient oracle as O + (Lemmal E.5p. In order to recover w up to e-Euclidean distance, we would like an
solution in function value (Claim E.4). Naïvely applying Theorem E.6 would yield an 12(1=)) gradient steps. Instead, we design an alternative one me-ppass iterative PSGD algorithm
(Algorithm 1 which requires O(1/²)) steps instead. We note that the algorithm (Algorithm and accompanying analysis (Theorem E.7) are similar to the PSGD analysis by Kalavasis et al. (025), but need additional ideas to argue that the algorithm converges in the one-pass setting, where can only process each observation once.
Theorem E.7. Let F: K C 12 l; is convex. Suppose that
IR be an average of functions F(w) EE fo w) where
(i) K S B)O,C)
(ii) f. G-Lipschitz
(ii)) | S for each E [n]
(iv) we have access to unbiased gradient oracles gi(w) for (((xTw) such that E2 [19.(xT w)ll G²
(v) F satisfies (n, -local growth condition (Definition 6
(vi) We are given an initial Eu-optimal solution w( K.
There is an iterative PSGD algorithm (Algorithm 7 which proceeds in one pass random per-
mutation of data and outputs a 22-optimal solution with probability 0.98 if n. S2 G²
log" (=)
The proof of Theorem E.7 relies the following result.
34

---

Published as a conference paper at ICLR 2026
Algorithm One-Pass lterative PSGD(K, Wo, Eo. 9, 7)
1: Input: Projection access to feasible region K, initial point w(()) E K, ED 2 F(wl()) - F(w*), gradient oracles 9s for f((x.) ,) E [n] with [|a:11 I G², local growth rate 7) 0, desired
accuracy > 0
2: Output: 2e-optimal solution with probability 0.98
3: Set T + [log, (fo/e)
4: Set Cu f 2čn
TVVE
5: Set 7 3 ?
6: Set T
4'=
7: σ +- uniform random permutation of [x]
8: for l - 1,..... do
9:
9/- + 200
10:
C 2 2-
w(e.0) + w (t-1)
11:
12:
fort 1,..., T do
13:
jt j (O(E((T-))) (1)
b next index of gradient oracles in permutation
(f.t) II [T (w(ft-11) - 7) gj (w((ett-1)
14:
15: end
for
16: w((
1 > wo(ct)
T
end for
18:
Return w((
Proposition E.8 (Lemma in Xu et al. (011)). Suppose F: Rd - TR satisfies (n, p)-local growth condition. Then for any E R
F(w) F(w))
|| woll2
qvP
Proof Theorem E.7 Define & = 2- We will argue that F(w(()) F(w*) S Ee + e with probability 1/100r conditioned on ((w((-1)) - F(w*) S Ex-1 + e. The claim follows then by union bound over stages.
The base case for 0 holds by assumption. We have
Et-1 WE
Et 300G2,
Ce
and
By Proposition E.8 we have
(w w (c-1)
1 (F(((t-)))
((
S
El-1
<
Ce.
me
n/
If f = 1, we can directly apply Theorem
E.6 on the f-th stage of PSGD to deduce that
C
30GC
())
F F((
120 1) <
Vn +
n2 +
TT
E1
E1
Ex
300T
300r
300T
E7
1007
An application Markov's 's inequality would then yield the desired result with probability - 100r
However, analysis conditions each of the previous L (- stages, cannot directly apply Theorem f.6 for since the order of the permutation is not independent when conditioning on prior stages. Instead, we remark that the analysis of Theorem E.6 is equivalent
35

---

On high level, We downscale the covariates T Dvd while taking the scaled function (x w) = (xx] w Dvd). This does not affect information preservation or quadratic growth since (z w) = Lxx]] w) are identical as functions of w. However, this increases the second mo- ment of the gradient oracle by & + G2 D as well as the Lipschitz constant of &, by L + GDVa. that with probability 0.99, the (unobserved) dependents essentially simulate R-local Published as a conference paper at ICLR 2026
1) randomly grouping the n datapoints into v/r subsets of size T by repeating sampling T points without replacement,
2) selecting one such subset uniformly at random, and
3) executing a one-pass PSGD on random permutation of this selected group.
Thus, if 2 100, then at the l stage, we can perform our analysis conditioning selecting any of the at most subsets in the second step of the experiment above. Thus, the f-th stage still succeeds with probability 1 100r'
E.5 PUTTING IT TOGETHER
Applying Theorem E. setting with (n, (ab/200, =²12/e00²) yields the following result.
Note that compared to naively applying Theorem E.6 Theorem requires (1/22) fewer observa- tions.
Proposition E.9. Let (0, 1/300. Consider instance of linear regression with friction and suppose Assumptions 4 to 6 holds with constants b, C 0, t Suppose further that the partition @P of R. induced by the friction function is R-local. There is an algorithu that outputs an estimate w satisfying [| w" 1= S with probability 0.98. Moreover, the algorithm requires
RR2+0 C²
C2
(GC)
n ==
a4b2g2 log"
observations and terminates in poly(n, Ts) time, where Ta the time complexity of sampling from I 1-dimensional Gaussian distribution truncated to a partition P P (Assumption 7
We now explain how to handle the more general condition that |00ll < D as well as remove the assumption of R-locality.
As for the R-locality assumption, without friction will not exceed CDVd + Ollonn). Henee, partition for R DdDd + Ologg)).
We are now ready to prove the more general Theorem E.I The proof details are similar to that of Theorem 3.2, where we approximately implement the algorithm for R-local friction function using samples from a general friction function.
Proof of Theorem E.1 Suppose the friction function f induces general convex partition P. Since (oTw') w*| s CDVd, choosing R CDVV+ (n)) means that any n-sample algorithm will not observe a sample S; ~ N2 (x.J w", 1) such that S, [-RR, R, R] = Ø with probability 0.99 when the hidden constant in is sufficiently large. Define the partition (RR) of given by
(R) [Pn[- R, R) P PEO,PN(RR, Ø) (1x)
RR)
Since (RR) is refinement of P, it must also be a-information preserving with respect to the covariates. Consider the set-valued function HR ((R) given by
P [P]]
Pn Pn R {a} for an arbitrary ZE P. Pn P
By the choice of R, with probability 0.99, any n-sample algorithm cannot distinguish between observations P. NoaRy R2 (z, , and (s,) for S, No (2. w* w*.1). 1). Moreover, we can
sample from Pn[ R, R per Assumption
36

---

Published as a conference paper at ICLR 2026
Thus, simply the algorithm from Proposition E.9 with imput observations (I,, HR (s.))))
given samples (z,, S,) and conclude by applying Markov s inequality to the guarantees of Proposi- tion E.
F SIMULATIONS ON VARIANCE REDUCTION
The proofs of both our primary estimation algorithms, Le., coarse mean estimation (Theorem 3.2 and the linear regression with friction (Theorem (.3). systematically depend on critical theoretical component: the uniform variance reduction exhibited by Gaussian variables upon conditioning on convex truncations (Proposition B.2 We complement our our theoretical analysis with empirical evidence of variance reduction.
Specifically, we empirically test the variance-reduction condition that are used in establishing our algorithm's 's guarantees. To study this, we draw i..d. samples from Beta, Gaussian, Laplace, and Quartic families in ID with interval truncation sets. Then, we compare empirical variances before and after truncation. Across all instances, the variance of the truncated samples consistently smaller, suggesting that our algorithm could, in principle, be extended to other distribution families as well, at least in a single dimension.
12 tache Toaee
Gaussian
peopeeeeaa 2013 WAld
Gaussian
Figure 4: Each row shows distribution (rows and 2: Beta; rows and 4: Gaussian). Columns (1,3): bar plots of empirical variances (red = original, blue = truncated) with variance ratio Varmune/ Varorig annotated. Columns (2,4): histogram overlays (original vs. truncated) for half-line
(col. 2) and interval [L, U] truncations (col. 4). In all displayed runs, < 1, indicating variance reduction under these convex truncations.
37

---

Published as a conference paper at ICLR 2026
Laplace
Laplace
Quartic
20 valent
Quartic
Figure 5: Same layout as Figure 4 Rows and 2: Laplace; rows and Quartic (density xc e (a-x))/s)) Columns (1,3) report variance bars and r; columns (2.4) show the corresponding histogram overlays for half-line and interval [T,, U] truncations. The observed r < 1 across settings provides further evidence practical variance reduction beyond the Gaussian case.
38


Reviews:
[{"review_id": "3Sh5H0YtLb", "reviewer": "Reviewer_RKSz", "summary": "This paper studies the problem of estimating mean $\\mu$ of a Gaussian distribution $\\mathcal{N}(\\mu, I)$ with identity covariance from coarse data, where the learner only observes which cell of a (potentially unknown) partition each sample falls into. The authors resolve two open questions from prior work (Fotakis et al., 2021):\n\n (i) Identifiability Characterization: For convex partitions, they provide a geometric characterization of when an instance is identifiable, i.e., the mean can be uniquely determined from observed samples. They show that an instance is non-identifiable if and only if almost all partition cells are parallel slabs in the same direction.\n\n(ii) Efficient Algorithm:  They provide the first polynomial-time estimator for this problem under the assumptions that a bound $D$ on $\\|| \\mu \\||$ is known and the partition is $\\alpha$-information preserving (a stronger, quantitative version of identifiability assumption).", "questions": "If I understand correctly, the $\\alpha^{-4}$ dependence in the sample complexity appears to stem from two $\\alpha^{-2}$ factors: one from finding an $O(\\alpha^2 \\epsilon^2)$-optimal point in function value, and another from the $\\Omega(\\alpha^2)$ local strong convexity parameter. Do you think this dependence is fundamental for computationally efficient algorithms, or could it potentially be improved to $\\alpha^{-2}$ (matching the sample complexity of Fotakis et al.) through a sharper analysis or an alternative scheme? A discussion on whether this reflects a intrinsic statistical–computational trade-off or an artifact of the current proof technique could be helpful.\n\n\nI believe there is a minor typo in Remark 3. after Theorem 3.1. The sentence should likely be:\n'The \"almost every\" quantifier in Theorem 3.1 is important: some convex partitions P contain non-slabs but are non-identifiable because the *non-slabs* have zero total volume.'", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The coarse-data model is well motivated, and captures realistic phenomena like rounding, sensor quantization, and economic market friction. \n\nThe paper makes theoretical contributions by resolving two questions definitively: the identifiability characterization is clean and geometrically intuitive; while the estimator is both sample and computationally efficient, with time complexity polynomial in dimension $d$ and inverse desired accuracy $1/\\epsilon$, and the bit/facet complexity of the descriptions of the observed partition cells (i.e., coarse samples).\n\nThe main text is well-written overall and easy to follow, and Section 4 provides a helpful overview of the intuition and core ideas behind the technical proofs. \n\nThe appendices appear thorough and the proof strategies combine tools from several areas creatively. For example, the authors use variance reduction and Prekopa-Leindler inequality for the identifiability characterization; as well as local partition reduction trick in bounding the gradient moments for the algorithmic result.", "weaknesses": "The estimator's sample complexity scales as $\\widetilde{O}\\left( \\frac{d}{ \\alpha^4 \\epsilon^2} + \\frac{dD^2}{\\alpha^4} \\right)$, where $D$ is known bound on $\\|| \\mu \\||$. This is strictly worse than Fotakis et al.’s sample complexity of $\\widetilde{O}\\left(\\frac{d }{\\alpha^2 \\epsilon^2}\\right)$, which is independent of $D$. Also, I think claiming the sample complexity in the abstract as $\\widetilde{O}\\left(\\frac{d }{\\epsilon^2}\\right)$ seems a little misleading, since this holds only in the constant regimes of $\\alpha$ and $D$.\n\n\n\nMinor: While each lemma and theorem is clear when read in isolation, I find the overall logical flow in the appendices (particularly from Appendix C onward) is quite dense and technically heavy. This is understandable given the paper’s theoretical depth and the secondary nature of these sections compared to Appendices A and B. But maybe adding a few sentences of contextual reminders or even a brief proof roadmap noting how the later technical lemmas connect back to the main results would help improve readability and navigation\n\n\nVery minor (and less relevant since this is a theory-focused paper): The algorithm’s polynomial-time guarantee depends on access to an efficient sampling oracle. While the authors note in Appendix D that this can be implemented using MCMC schemes such as Hit-and-Run given a separation oracle, the practical runtime of these samplers is a concern. While this yields polynomial-time complexity, the high-degree polynomial dependencies (e.g., $d^{4.5}$) can be prohibitive for large or even moderate dimensions, limiting real-world applicability.", "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": "mKoXCuj1op", "reviewer": "Reviewer_THUX", "summary": "This paper addresses the fundamental problem of Gaussian mean estimation when the observations are coarse data. The key theoretical contributions are resolving two fundamental questions related to identifiability and computational efficiency.\n- Theorem 3.1: Intuitively, non-identifiability occurs if the partition is translation invariant in some direction. A convex partition $\\mathcal{P}$ is not information preserving if and only if there is a unit vector $v \\in \\mathbb{R}^d$ such that almost every set $P \\in \\mathcal{P}$ is a slab in direction $v$.\n- Theorem 3.2 provides a polynomial-time algorithm for finding $\\epsilon$-accurate estimates of $\\hat{\\mu}$ for any convex, $\\alpha$-information preserving partition $\\mathcal{P}$.\n\nThe key assumption enabling the tractability and efficiency of Theorem 3.2 is that the partition $\\mathcal{P}$ is convex and information-preserving.", "questions": "See \"weakness\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper provides novel, complete solutions to the fundamental question in Gaussian mean estimation from coarse data. The proposed algorithm has optimal sample complexity. \n- It establishes that a convex partition is non-identifiable if and only if almost every set is a slab in some common direction.\n- It shows that identifiability is a property of the partition structure itself, as it does not depend on the true mean $\\mu^{*}$.\n- The algorithm achieves the optimal sample complexity of $\\tilde{O}(d/\\epsilon^2)$.\n- $\\mathcal{Z}(\\mu)$ is proven to be convex because the individual component functions, $\\mathcal{Z}_P(\\mu) = -\\log(\\mathcal{N}(\\mu, I; P))$, are convex for any convex set $P$ (Proposition B.2). \n- The $\\alpha$-information preservation assumption is used to prove that $\\mathcal{Z}(\\mu)$ satisfies a local growth condition around $\\mu^{*}$ (Lemma B.3). \n- This effectively means the function is locally strongly convex near the true mean $\\mu^{*}$. \n- This condition guarantees that finding an approximate minimizer $\\hat{\\mu}$ in function value ($\\mathcal{Z}(\\hat{\\mu}) \\approx$ $\\mathcal{Z} (\\mu^{*})$) ensures $\\hat{\\mu}$ is close to $\\mu^{*}$ in $L_2$ distance.\n- The natural gradient expression involves expectations over samples $x$ whose observed sets $P$ can be unbounded, leading to an unbounded variance in the gradient.\n- They resolves this by introducing an idealized R-Local Partition $\\mathcal{P}(R)$ (Definition 5).\n- The final step is to remove the temporary R-Local Partition assumption and prove the theorem for a general convex partition $\\mathcal{P}$.The argument sets the bounding radius $R$ large enough ($R = D + O(\\log(md/\\delta))$) so that the true, unobserved samples $x_i$ fall within $B_{\\infty}(0, R)$ with high probability.\n- The total sample complexity is derived by plugging the calculated local growth parameter ($\\eta$) and the bounded second moment ($G^2$) into the PSGD convergence analysis (Theorem C.1)", "weaknesses": "- The polynomial time complexity relies on the existence of an efficient sampling oracle for a truncated Gaussian over the observed convex set $P$ (or $P \\cap B_{\\infty}(0, R)$). While this is achievable in $poly(d)$ time for polytopes using MCMC (Hit-and-Run) methods, these methods typically have high polynomial dependency and are usually slow in practice.\n- The paper specifies the requirement for an efficient sampling oracle (Assumption 1) that outputs an unbiased sample $y \\sim \\mathcal{N}(\\mu, I, P \\cap B_{\\infty}(0, R))$. This is an oracle for sampling from a truncated Gaussian distribution over a convex set. While the paper explicitly references the Hit-And-Run MCMC in Theorem D.1 as the general tool for implementing log-concave sampling over convex bodies (Appendix D), Langevin Monte Carlo (LMC), specifically Projected Langevin Monte Carlo (PLMC), is a highly relevant alternative method that could potentially be used. State-of-the-art PLMC methods often have better theoretical dependence on the dimension, such as $\\tilde{O}(d)$ under certain conditions.\n- The paper could be clearer on whether the entire partition $\\mathcal{P}$ must have a manageable, unified representation, or just the observed set $P_i$. If the partition is dense (e.g., infinitely many sets), managing the required infrastructure for all $P \\in \\mathcal{P}$ could be impossible.", "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": "Ckt17mNsFu", "reviewer": "Reviewer_wvZN", "summary": "The paper considers the problem of mean estimation from coarse data. Concretely, the goal is to learn the location parameter, $\\mu \\in \\mathbb{R}^d$, of a Normal distribution $\\mathcal{N} (\\mu, I)$ given access to i.i.d coarse samples from the distribution. Here, for a partitioning of $\\mathbb{R}^d$, $\\mathcal{P}$, one observes not a draw $X \\thicksim \\mathcal{N} (\\mu, I)$ but rather the unique partition $P \\in \\mathcal{P}$ containing $X$. Prior work established that sample-efficient estimation is possible when $\\mu$ is identifiable from coarse observations and the partitioning $\\mathcal{P}$ consists only of convex sets. However, this prior work does not characterize \\emph{when} $\\mu$ is identifiable and if it is, when it can be estimated \\emph{computationally} efficiently. The main contribution of this paper is to provide such a characterization. \n\nTo see why identification is not always possible, consider the special case where $d = 2$, and $\\mathcal{P} = \\{P_i\\}_{i \\in \\mathbb{N}}$ with $P_i \\coloneqq \\{(x, y): i < y_i \\leq i + 1\\}$. It is clear that $\\mu_1$ (the first coordinate) is not identifiable as any translation along the $x$ coordinate induces the same distribution over partitions. The main result of the paper establishes that these are the only scenarios where identification is not possible. That is, identification is impossible when the partition consists of a set of cylinders along a particular axis, with identification impossible along the axis. Furthermore, they show that a simple gradient descent-based algorithm on the log-likelihood of our observations enables computationally efficient estimation with a mild strengthening of this condition. \n\nTechnically, the main result follows from analyzing the (strict) convexity of the (log) likelihood function. When the partitions consist only of convex sets, the likelihood function can be easily shown to be convex. However, identification requires strict convexity. To do this, the starting point is an explicit characterization of the Hessian as the difference between $I$ and a weighted sum of conditional covariance matrices, which, from classical results in convex geometry, are dominated by $I$. To further extend these results to strict convexity, the authors carefully analyze when each of these conditional covariance matrices has variance $1$ along a particular direction. This, in turn, relies on more recent results in convex geometry.\n\nOverall, this paper makes substantial progress on an interesting and well-motivated problem. In particular, the identifiability guarantees are natural and surprising. The proof, despite largely relying on classical techniques and results, is also quite non-trivial. I believe this paper would make an excellent contribution to the conference.", "questions": "See main review", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "See main review", "weaknesses": "See main review", "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": "5Sxs5HtWMq", "reviewer": "Reviewer_TRGK", "summary": "This paper studies Gaussian mean estimation when observations are only available through coarse sets rather than exact samples. \nIt resolves two fundamental open questions from Fotakis et al. (2021) by (i) characterizing precisely when convex partitions are identifiable and (ii) providing the first polynomial-time algorithm for mean estimation under such identifiability. \nThe characterization shows that non-identifiability occurs if and only if the partition consists of parallel slabs in some direction. \nThe proposed algorithm performs stochastic gradient descent on a convex log-likelihood objective, with carefully controlled gradient moments and local strong convexity, achieving optimal $\\tilde O(d/\\omega^2)$ sample complexity. \nThe paper also illustrates the approach on linear regression with market friction, demonstrating both the conceptual generality and computational feasibility of learning from coarse data.", "questions": "**Questions:**  \n\n- You write 'making estimation information-theoretically impossible.' What is the precise mathematical meaning of this statement? Please clarify in terms of identifiability or distinguishability of distributions.  \n\n- How can the definition of identifiability on page 2 be verified or practically tested for a given partition? Are there diagnostic criteria or examples that illustrate this?  \n\n- In Figure 1, it is not immediately clear why panel (a) represents a non-identifiable partition while (b) and (c) are identifiable. Could you provide more intuition or explanation for this already when the figure first appears? As it stands, the reader can only fully understand this after reading Theorem 3.1.  \n\n- Theorem 3.2 appears to be stronger than stated: you not only guarantee the existence of a polynomial-time algorithm, but in the proof you actually construct it explicitly. I suggest making this more prominent in the statement and the discussion.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**Strengths:**\n\n– The contributions are very clearly explained and well connected to prior work.\n\n– The introduction is well written, motivating the problem both from statistical and practical perspectives.\n\n– The problem studied is theoretically interesting, addressing a fundamental question at the intersection of statistics and learning theory.\n\n– The characterization of identifiability (Theorem 3.1) is elegant and provides geometric intuition.\n\n– The proposed algorithm is explicit and computationally efficient.\n\n– The paper is well organized and easy to follow despite the technical depth.", "weaknesses": "**Weaknesses:  **\n\n- The assumption to only consider Gaussian distributions is restrictive; it would strengthen the paper to discuss how the techniques might extend to broader exponential families, or to outline obstacles or required modifications.  \n\n- At several places the paper is lacking mathematical rigor. Most crucially, it is not clear what a  'probability distribution of a set' should be; please give a rigorous, measure-theoretic definition of \\(\\mathcal N_{\\mathcal P}(\\mu,I)\\) as the pushforward of \\(N(\\mu,I)\\) under the partition map and specify its sigma-algebra. As written, Definition 1 is hard to parse, and once \\(\\mathcal N_{\\mathcal P}(\\mu,I)\\) is unclear, the meaning of KL divergence and TV distance between such objects is also opaque; moreover, the text sometimes treats distribution and  density as synonyms, which is mathematically incorrect.  \n\n- There seems to be a close relation to the literature on imprecise probability and set-valued observations (credal sets, lower and upper previsions), which is not discussed; adding a short paragraph contrasting your coarse partition with imprecise-probability frameworks would help position the work.  \n\n- The guarantees rely on the \\(\\varepsilon\\)-information preservation, but the paper offers little guidance on verifying or estimating (\\varepsilon\\) in practice for a given partition beyond examples; a diagnostic or sufficient conditions (beyond non-slab or boundedness) would improve applicability.", "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)