{"id":"fe97fbe8-7386-4d2c-affc-e4f3d39648d6","arxiv_id":"2504.19446","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Efficient algorithms recover the mean and covariance of a high-dimensional Gaussian from samples censored by known self-censoring or linear-thresholding missingness rules.","lead":"This paper gives polynomial-time algorithms for recovering a high-dimensional Gaussian distribution from samples in which some coordinates are hidden by rules that depend on the sample's own values. It matters because real-world missing data is often self-censored, and this work shows when the full distribution can still be estimated efficiently.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Gradient-sampler runtime unproven: Assumption 1.4 bounds pattern probabilities given the anchor set C, but the Langevin sampler requires a lower bound on the measure of K = {y_{\\bar A}: S(y)=A, y_A=x}, which can be arbitrarily small even when Assumption 1.4 holds.","rationale":"The paper presents a genuine attempt at efficient MNAR mean estimation under linear thresholding, and the self-censoring result is a plausible extension of prior work. The strongest claim, Theorem 1.5, is conditional on Assumptions 1.3 and 1.4, and the proof builds a projected stochastic gradient descent with Langevin gradient sampling. After reading in good faith, I find that the most load-bearing weakness is not simply that Assumption 1.4 is strong, but that the proof derives from it a conclusion it does not justify: Lemma C.1 requires the measure of the feasible set K to be at least γ under the Gaussian relevant to the sampler, whereas Assumption 1.4 only gives a lower bound on the pattern probability conditioned on the anchor set C. The gap is concrete: the conditional probability given the full observed vector y_A=x can be exponentially smaller than that given y_C, and no argument in the paper prevents this from occurring with probability large enough to break the polynomial runtime. This is an internal correctness risk, not a disagreement with prior consensus. The paper also contains a garbled character string in the proof of Lemma 4.5 and an unstated projection-oracle runtime, but those are secondary. A revision that adds an explicit high-probability bound on the conditional pattern probabilities given the observed coordinates, or that modifies the sampler to handle arbitrarily small feasible-set measures without exponential cost, would address the concern. Pending such a fix, the appropriate disposition is CONDITIONAL rather than ACCEPT or REJECT, because the underlying mathematical idea may be sound but the currently stated runtime guarantee is not fully supported.","tokens_in":24531,"tokens_out":30354,"duration_ms":291493,"concrete_test":"Analytically verify the following: in the 3D linear-thresholding model with C={1}, v_1=v_2=0, v_3=(0,0,1), b_3=0, and Σ having σ_13=0, σ_23=-0.9, compute the distribution of the conditional probability p(A,x) = Pr[S(y)=A | y_A=x] under the true censored distribution. Show whether p(A,x) is bounded below by a constant multiple of γ on a set of probability 1-δ, and compute the number of Langevin steps needed by [BEL18] Theorem 1 to achieve TV error ε if p(A,x) = exp(-t^2). If the step count is not poly(d,1/γ,1/ε,log(1/δ)), then the proof of Theorem 4.6 collapses. This check isolates whether Lemma C.1's uniform-ball-radius conclusion follows from Assumption 1.4.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central runtime claim of Theorem 1.5 rests on Theorem 4.6, which bounds the mixing time of the projected Langevin sampler in Algorithm 5. The proof of Theorem 4.6 invokes Lemma C.1, which asserts that K ∩ BΣ(0,R_1) contains a ball of radius r = Ω(γ/d^2) whenever the Gaussian measure of K is at least γ. But for an observed sample (A,x), the set K = {z : S(x∘z)=A} is exactly the set of completions of the unobserved coordinates, and its measure under the relevant conditional Gaussian N(μ_cond, Σ_cond) is Pr[S(y)=A | y_A=x]. Assumption 1.4 only guarantees Pr[S(y)=A | y_C] ≥ γ for the anchor set C ⊆ A; it does not imply any lower bound on Pr[S(y)=A | y_A=x]. Because x_A includes coordinates outside C, the conditional probability can be arbitrarily small. For example, take d=3, C={1}, S(y)={1,2} iff y_3 > 0, and let Corr(y_2,y_3)=-0.9. Then Pr[S(y)=A | y_1] = 1/2, so Assumption 1.4 holds with γ=1/2, but for an observed sample with A={1,2} and x_2 = t, the measure of K is Φ(-0.9·t/√0.19), which decays as exp(-Ω(t^2)). The proof does not show that such t cannot occur with non-negligible probability, nor does it adapt the Langevin radius to the actual measure of K. Consequently, the polynomial bound on the Langevin step count is not established. This is not a mere presentation gap: the claimed running time poly(d,1/α,1/β,1/γ,λmax/λmin,1/ε,log(1/δ)) contains no term that could absorb an exp(t^2) dependence. The garbled string in the proof of Lemma 4.5 and the unstated projection-oracle runtime are additional issues, but the above is the load-bearing one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies high-dimensional Gaussian estimation from missing-not-at-random (MNAR) data under two missingness models. In the self-censoring model, coordinate i is observed exactly when the underlying value lies in a known set S_i; the authors reduce estimation to one- and two-dimensional truncated-Gaussian subroutines from DGTZ18 and prove poly(d,1/epsilon) sample complexity under a pairwise-observation assumption. In the linear-thresholding model, coordinate i is observed when v_i^T y <= b_i, the covariance is known, and the goal is mean estimation; the paper proposes a projected stochastic gradient descent on the negative log-likelihood, with gradients sampled by a projected Langevin algorithm, and claims poly(d,1/alpha,1/beta,1/gamma,lambda_max/lambda_min,1/epsilon,log(1/delta)) samples and time under Assumptions 1.3 and 1.4.","tokens_in":24953,"tokens_out":25754,"duration_ms":252152,"significance":"If the linear-thresholding result were fully established, it would be a substantial advance: it would give the first polynomial-time algorithm for high-dimensional MNAR mean estimation under explicit, non-asymptotic conditions, going beyond the all-or-nothing censoring of DGTZ18. The self-censoring part is a clean and mostly convincing reduction that leverages published external subroutines, so it is not circular. The paper is commendably explicit about its assumptions and gives concrete pseudocode. However, the proof of the central runtime claim for the Langevin gradient sampler has a serious gap, so the main advertised theorem (Theorem 1.5) is not established as written.","major_comments":[{"comment":"The proof that Algorithm 5 mixes in polynomial time is not sound. In the notation of Algorithm 5, K={z in R^{d-|A|} : S(x∘z)=A} is an affine slice of the missingness pattern; hence the probability Pr_{w∼N(0,Sigma)}[w in K] used in the proof of Lemma C.2 is zero, and if K is instead interpreted in the conditional space N(mu_cond,Sigma_cond), Assumption 1.4 gives no lower bound on its probability, since it conditions on the anchor set C rather than on the full observed vector y_A=x. For example, take d=3, C={1}, S(y)={1,2} iff y_3>0 (and {1} otherwise), and Corr(y_2,y_3)=-0.9. Then Assumption 1.4 holds with gamma=1/2, but for an observed sample with A={1,2} and x_2=t, the measure of K under the conditional Gaussian is Phi(-0.9t/sqrt(0.19)), which decays as exp(-Omega(t^2)). The proof does not show that such t cannot occur with non-negligible probability, nor does it adapt the Langevin radius to the actual measure of K. Consequently the polynomial bound on the number of Langevin steps in Theorem 4.6 is not established, and the running time claimed in Theorem 1.5 has no term that could absorb this exponential degradation.","section":"C.3, Lemma C.2 and Theorem 4.6"},{"comment":"The strong-convexity proof is incomplete as printed. The text contains the garbled string 'enecccfckgvkkjlfnlclcggguvjldtdurlrlltnecnid' and skips the block-matrix manipulations needed to pass from Eq. (14) to the final inequality v^T nabla^2 ell(mu) v >= alpha v_H^T Sigma_HH^{-1} v_H. The displayed formulas suggest the identity may be correct, but a referee cannot verify the lemma without the missing algebra, and strong convexity is load-bearing for the SGD convergence argument. The proof needs to be rewritten with the omitted steps supplied.","section":"4.3.1, Lemma 4.5"}],"minor_comments":[{"comment":"Lemma C.2 is stated twice with the same label; the second occurrence should be renumbered or removed to avoid confusion.","section":"Appendix C.3"},{"comment":"Line 4 uses B_Sigma(W^{-1}mu_cond,R), but B_Sigma is a ball in R^d while the argument W^{-1}mu_cond lies in R^{d-|A|}; the intended metric for the projected Langevin dynamics should be clarified.","section":"Algorithm 5"},{"comment":"Line 7 says to remove rows containing at least one '*' but a missing entry is not previously defined; the intended definition of a missing-value indicator should be stated.","section":"Algorithm 2"},{"comment":"The lower-bound proof concludes that o(max{1/epsilon, sqrt(lambda)/epsilon}) samples are insufficient, but the lemma statement is phrased as o(1/sqrt(lambda_min)) for epsilon = Omega(sqrt(lambda_min)); the relationship between these parameters should be spelled out for the reader.","section":"Lemma 3.4"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the main advertised result (Theorem 1.5) is not established by the current proof. If the authors cannot repair the gradient-sampler argument or must strengthen Assumption 1.4 to condition on the full observed vector, the paper should be reframed accordingly; the self-censoring portion appears sound and could stand as a separate contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The self-censoring part is the cleaner of the two results. Reducing coordinate-wise missingness to a collection of 1D and 2D truncated problems via DGTZ18 works, and the pairwise visibility assumption (Assumption 1.1) is a sensible way to get polynomial samples even when no small subset is always fully observed. I credit the authors for not over-claiming here: the algorithm is a direct composition of known subroutines, and the sample bounds follow from a straightforward union bound. This part should survive review, modulo the presentation issues you noted (the garbled string in Lemma 4.5's proof, the duplicated Lemma C.2, and a few terse proofs).\n\nThe linear-thresholding result is more genuinely new — the model itself, with coordinate-specific halfspace visibility, is a reasonable MNAR abstraction, and the anchoring assumption is explicitly stated. But the stress-test concern is real and load-bearing. The runtime of Theorem 1.5 depends on Theorem 4.6, which needs a lower bound on the measure of the completion set K = {z : S(x∘z)=A} given only y_A = x. Assumption 1.4 bounds pattern probabilities conditioned on the anchor coordinates C, not on the full observed set A. As the stress-test example shows, those two conditionings can differ exponentially in the observed values of non-anchor coordinates. The proof of Lemma C.1 does not bridge this gap, and the stated poly(1/γ) runtime cannot absorb an exp(t^2) factor. This is not a cosmetic issue; it undermines the claimed polynomial time for the gradient sampler. A serious revision needs either a stronger anchoring condition, a more refined argument controlling the conditional measure, or a proof that bad observed values occur with negligible probability.\n\nOther soft spots: the strong convexity proof (Lemma 4.5) skips exactly the matrix algebra that would let a reader verify the key step, and the projection oracle in Algorithm 4 is assumed efficient without discussion. Lemma 3.4's lower bound is terse to the point of being hard to check.\n\nWho gets value: anyone working on truncated or missing-data Gaussian estimation will want the self-censoring construction, and the linear-thresholding model is worth knowing about even if the current proof is incomplete. The paper deserves a serious referee — it is not a desk reject — but the referee should ask for the gradient-sampling gap to be fixed before the main theorem is trusted.","headline":"The self-censoring result is a solid extension of DGTZ18, but the linear-thresholding half has a real gap in the Langevin gradient-sampling analysis that needs to be fixed before the runtime claim is credible.","tokens_in":25541,"tokens_out":1953,"would_cite":true,"duration_ms":22104,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H12","62F10","62G07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two censored-Gaussian models are learnable with polynomial samples","keywords":["missing not at random","Gaussian distribution learning","censored data","truncated samples","self-censoring","linear thresholding","projected stochastic gradient descent","Langevin Monte Carlo"],"falsifier":"Instantiate the linear-thresholding model with $d=2$, $\\Sigma=I$, coordinate 2 always observed, coordinate 1 observed when $y_1 \\le t$, and run Algorithm 3 as $t$ sweeps from 0 toward infinity. The theorem predicts the sample bound grows polynomially in $1/\\alpha$ and $1/\\gamma$; if the observed degradation in reaching $\\|\\hat\\mu - \\mu^*\\|_\\Sigma \\le \\varepsilon$ is exponential in $1/\\gamma$, the assumptions as stated are not sufficient.","tokens_in":24296,"feed_emoji":"🧩","tokens_out":7707,"duration_ms":75861,"temperature":0.7,"pith_summary":"The paper asks when a high-dimensional Gaussian can be recovered from samples in which coordinates are missing not at random, with the missingness rule known. It answers for two mechanisms. Under self-censoring, where coordinate $i$ is seen iff $y_i$ satisfies a known predicate, if every pair of coordinates is jointly observed with probability at least $\\alpha$, both mean and covariance can be estimated to small total-variation error using $\\tilde{O}(d^2(\\lambda_{\\max}/\\lambda_{\\min})^2/(\\alpha\\varepsilon^2))$ samples. Under linear-thresholding missingness, where coordinate $i$ is seen iff $v_i^\\top y \\le b_i$, the mean can be estimated in polynomial time with known covariance, provided any small subset of coordinates is observed with probability at least $\\alpha$ and a $\\gamma$-anchoring set of always-observed coordinates exists. If these results hold, MNAR corruption is not inherently an obstacle to efficient Gaussian estimation.","feed_headline":"Two censored-Gaussian models are learnable with polynomial samples","feed_subtitle":"Explicit observability and anchoring conditions turn missing-not-at-random Gaussian data into a tractable estimation problem.","key_machinery":"For self-censoring, the machinery is coordinate-pair decomposition plus the truncated-Gaussian SGD used in dimensions 1 and 2, with Assumption 1.1 ensuring enough complete pairs. For linear thresholding, the machinery is the negative log-likelihood $\\ell(\\mu)$ whose gradient requires sampling from the conditional Gaussian $N(\\mu,\\Sigma)$ restricted to $\\{y: S(y)=A,\\, y_A=x\\}$; because linear thresholds define convex sets, conditioning a Gaussian on a convex set can only reduce variance, which yields strong convexity of $\\ell$. The gradient samples are obtained by projected Langevin Monte Carlo rather than rejection sampling, since rejection costs would grow exponentially when $\\mu$ drifts from $\\mu^*$; the anchoring assumption bounds the conditional pattern probabilities and keeps the sampler polynomial. A projection step keeps iterates in a Mahalanobis ball so the stochastic gradients have bounded centralized second moment.","core_discovery":"The central claim is that estimation under MNAR Gaussian data is computationally tractable exactly when the missingness rule has a decomposable or anchored structure. For self-censoring, the paper shows the $d$-dimensional problem reduces to one- and two-dimensional truncated-Gaussian subproblems, one per coordinate or coordinate pair; each subproblem is solved with the known truncated-sample SGD, and the pieces are assembled into a consistent covariance matrix. For linear-thresholding missingness with known $\\Sigma$, the paper defines the population negative log-likelihood as a function of $\\mu$ and proves it is $\\lambda$-strongly convex with $\\lambda = \\alpha\\beta/\\lambda_{\\max}(\\Sigma)$, so projected SGD converges. The key algorithmic step is a projected Langevin Monte Carlo sampler that draws approximately from the conditional Gaussian over unseen coordinates given the observed pattern, with bias and second-moment bounds that make the PSGD convergence theorem applicable. The result is Theorem 1.5: with $\\mathrm{poly}(d, 1/\\alpha, 1/\\beta, 1/\\gamma, \\lambda_{\\max}/\\lambda_{\\min}, 1/\\varepsilon, \\log(1/\\delta))$ samples, the estimator meets $\\|\\hat\\mu - \\mu^*\\|_\\Sigma \\le \\varepsilon$.","pith_inferences":["A natural next step, left open by the paper, is unknown $\\Sigma$ under linear-thresholding missingness; the Hessian then involves a fourth moment, but the anchoring condition may still make a second-order method or a moment-based correction work.","The anchoring assumption is reminiscent of anchor words in topic modeling; if anchor coordinates are domain-known, the algorithm applies directly, and the dependence on $1/\\gamma$ makes it worth measuring $\\gamma$ in practice before deployment.","The coordinate-pair reduction for self-censoring suggests a general principle: when a missingness model factorizes over small subsets, estimation can be assembled from small truncated subproblems, potentially extending to other exponential families with pairwise-sufficient statistics.","For practical deployment, the $\\mathrm{poly}(1/\\gamma)$ and $\\mathrm{poly}(1/\\alpha)$ factors mean the algorithm's usefulness depends on how large these probabilities are; identifying real missingness mechanisms where $\\gamma$ is not tiny would be a valuable empirical study."],"forward_implications":["Under self-censoring with every pair observed with probability at least $\\alpha$, both mean and covariance are recoverable to TV error $O(\\varepsilon)$ with $\\tilde{O}(d^2(\\lambda_{\\max}/\\lambda_{\\min})^2/(\\alpha\\varepsilon^2))$ samples, so heavy coordinate-wise missingness is not a barrier.","Under linear-thresholding missingness with known covariance, the mean can be found in polynomial time whenever small subsets are observed with probability at least $\\alpha$ and a $\\gamma$-anchor set exists, giving a finite-sample MNAR guarantee without an all-or-nothing observation model.","The self-censoring result needs only pairwise observation, not a constant fraction of fully observed samples, so it strictly extends the earlier truncated-Gaussian setting.","The $\\Omega(1/\\sqrt{\\lambda_{\\min}})$ lower bound shows some eigenvalue dependence is unavoidable for self-censoring, even when uncensored distributions are far apart in TV distance.","Because the likelihood is strongly convex only for linear-thresholding missingness, the same optimization route will not directly work for general self-censoring rules."],"supporting_citations":[{"why":"Provides the univariate and bivariate truncated-Gaussian SGD subroutines and the truncated-mean bound used by the self-censoring algorithm.","marker":"[DGTZ18]"},{"why":"Corollary 2.1 shows conditioning a Gaussian on a convex set reduces variance, giving the Hessian lower bound used for strong convexity.","marker":"[KP77]"},{"why":"Projected Langevin Monte Carlo mixing bound used to sample the gradient in SampleGradient.","marker":"[BEL18]"},{"why":"Supplies the projected-SGD convergence lemma and the initialization bounds used in the linear-thresholding analysis.","marker":"[CDIZ22]"}],"fun_headline_variants":["Polynomial-time learning of censored Gaussians","Censored Gaussians: efficient recovery despite MNAR","Missing data? Still learn Gaussians efficiently","High-dim Gaussians from censored observations","Poly-sample learnable: censored Gaussian estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 1.4: there must be an anchoring set of coordinates that is observed in every sample and whose values make every missingness pattern occur with probability either 0 or at least $\\gamma$; without such a set, the gradient sampler's cost becomes exponential and the strong-convexity estimate depending on pattern probabilities collapses.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time learning of censored Gaussians","Censored Gaussians: efficient recovery despite MNAR","Missing data? Still learn Gaussians efficiently","High-dim Gaussians from censored observations","Poly-sample learnable: censored Gaussian estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000311,"raw_usage":{"total_tokens":1893,"prompt_tokens":1185,"completion_tokens":708,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":801,"completion_tokens_details":{"reasoning_tokens":637}},"tokens_in":801,"tokens_out":708,"duration_ms":6444,"temperature":1.0,"reasoning_tokens":637,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:52:13.767569+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instantiate the linear-thresholding model with $d=2$, $\\Sigma=I$, coordinate 2 always observed, coordinate 1 observed when $y_1 \\le t$, and run Algorithm 3 as $t$ sweeps from 0 toward infinity. The theorem predicts the sample bound grows polynomially in $1/\\alpha$ and $1/\\gamma$; if the observed degradation in reaching $\\|\\hat\\mu - \\mu^*\\|_\\Sigma \\le \\varepsilon$ is exponential in $1/\\gamma$, the assumptions as stated are not sufficient.","supporting_citations":[],"review_version":1}