acceptodds
Under review as a conference paper at ICLR 2027

From Identifiability to Sample Complexity for Discrete Latent Variables Seen Through Known Channels

Abstract

Causal representation learning seeks to recover meaningful hidden variables from observations. When observations merge hidden states, which properties remain recoverable, and how much data is needed to estimate them? We study this question in finite discrete models. A matrix built from the observation process gives an exact test for whether an average hidden property can be recovered. For every recoverable target, we construct an estimator whose mean squared error has an explicit leading term proportional to the inverse of sample size, plus a smaller correction. A matching lower bound shows that no method improves this leading error in the worst case, and the estimator has a normal large sample limit with optimal variance. When the observation process is unknown but belongs to a finite set, indistinguishable processes with different target values make consistent estimation impossible. With sufficient separation, an adaptive estimator matches the same leading error as if the process were known. Under a common support condition, candidate processes whose observed laws are close, at the scale of one over the square root of the sample size, but whose targets differ leave an error that does not vanish. Simulations and a semi-synthetic census study with a randomized-response channel illustrate these predictions.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
causal representation learning, identifiability, finite-sample theory, discrete latent-variable models, coarsened observations, adaptive estimation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EaCaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the identifiability and sample complexity of estimating linear functionals of discrete latent variables observed through a known stochastic channel. Specifically, the authors consider a latent distribution, an observation matrix, and the observed distribution. The goal is to estimate a target functional from independent observations. The key contributions are: 1. characterizes identifiable linear functionals. 2. for identifiable targets, construct a plug-in estimator and asymptotic efficiency and a matching minimax lower bound.

Critical strengths
  1. A unified theoretical characterization of identifiability and estimation efficiency. The paper provides a systematic treatment of identifiable linear functionals, finite-sample estimation error, and asymptotic efficiency under a common observation model. The uniform second-order risk expansion for the feasible plug-in estimator is a useful technical contribution.

  2. Theoretical treatment of uncertainty in the observation channel. The extension to finitely many candidate channels is interesting. The authors identify conditions under which channel uncertainty makes estimation impossible and conditions under which adaptation can achieve the same first-order risk as an oracle with knowledge of the channel.

Critical weaknesses
  1. My major concern is that the foundational results of the paper are closely related to established results in linear inverse problems, generalized least squares, and semiparametric estimation. For example, the identifiability characterization the construction of minimum-variance feasible weights, and the first-order efficiency bound are classical results, as acknowledged by the authors. Although the paper provides additional results concerning second-order risk, calibration uncertainty, and adaptation across candidate channels, it is not sufficiently clear to me whether these extensions constitute a substantial conceptual or methodological advance beyond existing statistical theory.

  2. The paper is motivated by causal representation learning, but the actual setting is substantially more restrictive than the models typically studied in this area. In particular, the framework assumes finite discrete latent and observed spaces, a known deterministic mapping, and a known observation channel. Although the paper considers uncertainty about the channel, this extension still assumes that the true channel belongs to a known finite candidate set. Assuming that the observation process is known removes one of the central challenges of causal representation learning: recovering latent structure and observation mechanisms from data. Moreover, the proposed framework focuses on estimating linear functionals of a latent distribution rather than recovering latent causal variables, their relationships, or causal structure. Consequently, the connection to causal representation learning seems not very strong.

Questions for authors
  1. Could the authors clarify which theoretical contributions go substantially beyond existing results in semiparametric estimation, generalized method of moments, and measurement-error models?

  2. To what extent can the main identifiability and sample-complexity results be extended to settings where the observation channel is unknown and must be estimated from the same observational data?

1 comment

Q1. What goes beyond existing results in semiparametric estimation, GMM, and measurement-error models?

The starting point is classical, and the paper says so: which averages are recoverable, the best weights, the first-order variance VA/nV_A/n, and the normal limit. Our estimator is a version of minimum chi-square, a special case of optimally weighted GMM. Three things go beyond that.

1. The actual mean squared error (MSE) of the estimator one can compute. Classical theory gives a limit: approximately normal with variance VA/nV_A/n, at one fixed truth. That does not bound the MSE at a given nn. We show that the MSE is VA/nV_A/n plus a remainder of at most C/n2C/n^2, with one constant CC (not in closed form) for all priors bounded away from zero, also when the channel merges hidden states. Why: the estimated weights satisfy the same exact constraint as the true ones, so the error splits exactly into (true weights) times (noise) plus (weight error) times (noise). The second piece has size 1/n1/n, and its cross term with the first is a third moment of the noise, of size 1/n21/n^2. A consequence: weights fixed in advance lose at least at order 1/n1/n for some prior, while estimated weights stay within 1/n21/n^2 of the best for every prior.

2. The price of an estimated channel when the channel table is not square. Classical results cover square, invertible tables estimated from a validation sample (Rogan and Gladen). We cover more record types than hidden states, when the whole prior is recoverable. With mm calibration draws per column, the MSE is VA/n+Ccal/mV_A/n+C_{\mathrm{cal}}/m up to smaller terms, where CcalC_{\mathrm{cal}} is the sum over hidden states jj of pj2p_j^2 times the variance of the best weights under state jj. This says how to split a calibration budget, and it checks out: predicted 0.1006, simulated about 0.10.

3. A channel known only up to a list of candidates. The literature treats an uncertain channel mainly by sensitivity analysis and identification bounds; we know of no results there on estimation error. We give three cases. (a) Two candidates can produce the same data but imply different answers: the error stays above a fixed number at every nn. (b) The candidates' data distributions are separated by a gap: the data pick the right one, with error probability falling exponentially in nn, and the estimator is as accurate, to first order, as with a known channel. (c) The gap is at most about 1/n1/\sqrt n and the answers still differ: an error of the size of that difference remains for every estimator. The constants of (b) and (c) do not meet; the paper states the open range.

Stated plainly: items 1 and 2 complete classical theory with standard tools. Item 3 is, as far as we know, new in kind.

Q2. What if the channel is unknown and must be estimated from the same data?

With no extra information the results do not extend, and more data does not help. Example: a survey records yes or no, and each record is flipped with an unknown probability ff. If 40% of records say yes, this fits a true rate of 40% with no flipping, 25% with 30% flipping, or 0% with 40% flipping. One observed number cannot fix two unknowns. In general, with a completely unknown channel only the frequencies of what is recorded without noise (the label) are recoverable: for any prior with the right label frequencies, some channel reproduces the data exactly.

Extra information that is enough:

  • A calibration sample (mm records per hidden state, state known): the error formula holds with the extra term Ccal/mC_{\mathrm{cal}}/m (item 2). Proved for our estimator. We have not proved that no method does better.
  • A finite list of candidates: item 3. Proved.
  • A channel known up to a few unknown numbers: the target is recoverable if it does not change along any small joint change of channel and prior that leaves the data distribution unchanged. The rate then stays 1/n1/n, with a constant at least VAV_A. Expected from standard arguments, not proved.
  • Repeated reports per person: these can make the channel estimable. Example: two reports per person, each flipped independently with the same unknown f<1/2f<1/2. They disagree with probability 2f(1−f)2f(1-f) whatever the true rate π\pi, so the disagreement rate reveals ff. Then π\pi follows, since the share of yes-yes pairs minus the share of no-no pairs is (2π−1)(1−2f)(2\pi-1)(1-2f). The cost of not knowing ff, as the exact ratio of best achievable variances: with π=0.3\pi=0.3, under 1% at f=0.1f=0.1, 4% at f=0.2f=0.2, 24% at f=0.3f=0.3; with π=0.1\pi=0.1 and f=0.2f=0.2, 25%. So one report is not enough and two are, at a cost that grows with the noise and as the true rate moves away from one half.
Reviewer_DBdFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper considers the problem of statistical estimation of the target value from noisy measurements and potentially unknown observation channels. Specifically, they consider the setting where discrete underlying variables can only be observed through certain channels, and each channel may only provide noisy measurements of the variable. The authors first show that, if the channels are known, the target values, represented as a linear combination of the latent variables, can be uniquely identified if and only if a certain condition on the measuring procedure is satisfied. Further, they provide a minimax lower bound for mean-squared error, and construct an estimator achieving this bound. When the observation channel is unknown but belongs to a finite set of channels, they show that the mean-squared error depends on the uncertainty from both observed data and the unknown channel, where the latter cannot be eliminated as the data size increases. The authors evaluate the performance of the provided method through semi-synthetic data.

Critical strengths
  1. This paper provides complete theoretical results on the identifiability of the estimand. Specifically, they provide necessary and sufficient conditions on the identifiability of the target value, a minimax lower bound for mean-squared error, and an estimator that can achieve this bound.
  2. The overall presentation of the paper is clear and easy to follow. All the theoretical results are well-explained with proofs and examples.
Critical weaknesses

One major weakness lies in the connection of the considered problem with the related work. From my understanding, the problem is more related to statistical estimation under measurement error or differential privacy than causal representation learning. Most work on CRL considers identifying pp or ff, not a certain target estimand. Including comparisons with this line of research, both in theory and in practice, would better show the novelty of the results.

Also, assumptions such as knowing the functional form of ff or κ\kappa in advance may be strong in the causal discovery literature. On the contrary, these assumptions are used more often in differential privacy literature, where the noise distribution is known in advance to construct differentially private datasets.

Questions for authors
  1. Can the proposed method be applied to the case when either ZZ or SS is continuous, and where a similar version of the matrix AA is constructed by binning?
1 comment

Question: continuous ZZ or SS, with AA built by binning.

The two cases are different.

Continuous SS, finite ZZ: yes, and with no approximation. If SS is cut into bins, the binned data follow q=Apq=Ap exactly. The entries of AA are the bin probabilities P(S∈bin∣Z=zj)P(S\in\text{bin}\mid Z=z_j), which are known when κ\kappa is known. So every theorem applies to the binned data as stated. Binning can only lose information, so VAV_A can only go up, but the loss is small once the bins are moderately fine. We computed an example for this reply: the running example of the paper with a Gaussian signal, S∣Z=j∼N(μj,1)S\mid Z=j\sim N(\mu_j,1), μ=(0,1.5,0.5)\mu=(0,1.5,0.5), p=(0.3,0.3,0.4)p=(0.3,0.3,0.4), target p1p_1, bins of equal probability.

number of bins24816
VAV_A with binning, divided by the optimal variance without binning1.251.051.011.003

With a single bin (no signal at all) the target fails the rank test, as it should. We will add this as a remark with the example. Binning is in fact not required: with finite ZZ the model stays finite-dimensional, and the sum in VAV_A becomes an integral. The first-order results carry over by the same classical arguments. Our second-order proofs are written for a finite alphabet, and we have not redone them for continuous SS.

Continuous ZZ: only as an approximation, and outside our theory. If ZZ is binned, the channel of a bin is an average of κ(z,⋅)\kappa(z,\cdot) over the unknown distribution of ZZ inside the bin, so AA is no longer known exactly. The effect is that of our misspecified-channel stress test (Appendix E): a bias that grows with how much κ\kappa and the target vary inside a bin, and that does not shrink with nn. Finer bins reduce this bias, but they make neighbouring columns of AA more alike, which can make VAV_A large (Lemma 4). This is the usual trade-off of deconvolution problems, where rates slower than 1/n1/n are typical. We list "alphabets growing with nn" as outside the theory and do not claim more. The exception is when κ\kappa and the target depend on zz only through a finite partition: binning by that partition is then exact.

Reviewer_mVN6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper addresses recoverability in causal representation learning. It introduces a matrix derived from the observation process that serves as an exact algebraic test. If the target property falls within the column space (or appropriate functional range) of this observation matrix, it is provably recoverable, even if individual latent states remain unidentifiable. A finite sample risk (and matching lower bound) is also provided based on second order control.

Critical strengths

Th epaper provides an interesting new view on a causal representation learning in the finite discrete case. The focus on theoretical recoverability rather than recovery itself is valuable.

The paper poses and aswers three fundamental questions about the particular case they are interested in. This is certainly bold, but I think its effective.

Critical weaknesses

I don't think I've ever seen a paper define a variable in the first sentence of the introduction. It's better than a trite explanation of causal representation learning, but it reflects a presentation style that is dense at best. I was hoping that the Related Work section was going to provide a bit more context, and perhaps an explanation of the advantages of the proposed approach as compared to previous work, but instead it gives a very brief justification of teh claim that similar statements about the finitie-sample case have not been made previously.

Questions for authors

See above

1 comment

Thank you. Both criticisms are fair, and we will act on both.

The opening is too dense.

We will open with one concrete case and bring in notation only after it:

A survey asks a sensitive question. To protect the respondents, each answer is randomly changed by a known rule before it is recorded. The analyst sees only the changed answers. Which facts about the true answers can still be recovered? How many respondents are needed to estimate such a fact to a given accuracy? And what if the analyst is not sure which rule was used?

The Related Work section gives no context and no comparison.

We will replace it with a comparison of what each line of work provides:

Line of workWhat it givesWhat it leaves openThis paper
Identifiability in CRL and nonlinear ICAFor rich models with learned decoders: what is recoverable with unlimited dataHow much data is needed, with constants and lower boundsA much simpler model (finite, known observation process), but the full chain: test, sample size with an explicit constant, matching lower bound
Finite-sample results in nonlinear ICA (Lyu and Fu 2022) and in CRL (Acartürk et al. 2024)Upper bounds, on the error or on the sample size, for particular learning methods in continuous modelsLower bounds and exact constants: neither paper proves a lower boundExact leading constant with a matching lower bound, in the finite setting only
Randomized response, diagnostic-test correction, local privacyCorrections and variances for particular channels, usually invertible onesChannels that merge hidden states; an estimated or uncertain channelOne treatment for any finite known channel; the price of estimating the channel; three regimes for an uncertain channel
Semiparametric efficiency theoryThe first-order optimal varianceFinite-sample control; channel uncertaintyWe use it and credit it (Table 1), and add the finite-sample and uncertain-channel parts

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.