{"id":"7d880185-9d8c-439d-bf4f-5aad7be219bf","arxiv_id":"1908.01034","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Gaussians with unknown truncation sets, sample-efficient estimation is achieved with sample complexity governed by VC dimension and Gaussian surface area, and a near-matching lower bound is provided.","lead":"This paper gives an algorithm that estimates a Gaussian's mean and covariance from samples that are only shown when they fall inside an unknown set. The required sample count depends on a complexity measure of the set called Gaussian surface area, and a matching lower bound shows the dependence is close to inevitable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's TV-transfer proof uses an inequality that fails on the knapsack set, so the parameter-recovery transfer is not yet established.","rationale":"The reader correctly identified Lemma 3 as the load-bearing transfer step, but the concern is more specific than 'the normalization may not be a valid lower bound.' Minimizing over β is actually the right direction for a lower bound: the relaxed optimum is a lower bound on the true truncated-TV contribution, so the issue is whether the proof lower-bounds that relaxed optimum correctly. The concrete failure is the pointwise inequality |1-e^p|≥|p|/2, which is applied outside its valid regime |p|≤1; the set S defined by the knapsack threshold can contain points with p very negative when T≥1, and for those points the inequality can fail badly. The transfer lemma is used in the VC-dimension theorem and in the diagonal-covariance reduction, so a complete proof of the paper's advertised parameter-recovery scope requires repairing this step. However, I do not see an actual counterexample to the lemma itself, and the spherical-Gaussian algorithm's direct recovery argument in Section 4.2 is less dependent on Lemma 3. The reader's CONDITIONAL verdict remains appropriate: the central algorithmic idea is plausible and largely supported, but the proof of a key transfer inequality is incomplete enough that acceptance without a corrected derivation would be premature.","tokens_in":40621,"tokens_out":40965,"duration_ms":444020,"concrete_test":"Re-derive Lemma 3's knapsack lower bound for the regime where the threshold T exceeds 1, explicitly tracking the set where |p|>1. If the submitted inequality |1-e^p| ≥ |p|/2 is used, replace it with the correct pointwise bound |1-e^p| ≥ min(|p|/2, 1/2) for all real p, and recompute whether the final constant Cα = Ω(α^3) still survives. If no such corrected derivation yields a positive constant independent of the two normalizations, Lemma 3 is unsupported; if the constant does survive, the published proof still needs this correction before the transfer step is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's broadest parameter-recovery claims depend on Lemma 3, which converts total-variation closeness of truncated Gaussians into closeness of the underlying untruncated parameters. The proof in Section 3 relaxes the two truncated densities to an optimization over unnormalized densities with a free parameter β. Since the optimization minimizes over β, the relaxed value can only be smaller than the true contribution, so the proof must show that this relaxed value is itself large. The displayed derivation lower-bounds the relaxed integral by E[|1-exp(p)| 1_{S\\Q}] ≥ E[|p|/2 1_{S\\Q}], using the inequality |1-e^p| ≥ |p|/2 for |p|≤1. But the set S is defined as {x : |1-exp(p(x))| ≤ T}, and for T large enough to collect the required α/2 mass, S contains points with p(x) very negative; for such points |1-exp(p)| is at most 1 while |p|/2 can be arbitrarily large, so the inequality is false exactly on the set S\\Q to which it is applied. This is not a matter of a loose constant: the claimed Ω(α^3) transfer depends on this step. The lemma is used in Theorem 1 and in the reduction from arbitrary diagonal covariance to the isotropic algorithm, so the advertised sample-complexity and parameter-recovery claims for unknown covariance rest on an unverified inequality. The spherical-Gaussian algorithm's direct parameter-space analysis is less exposed, but the paper's full scope, including the VC-dimension result and the diagonal covariance corollary, depends on Lemma 3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies estimation of the mean and covariance of a Gaussian from samples that are observed only if they fall in an unknown truncation set S. It claims two main routes: a VC-dimension-based sample-complexity bound with an ERM/tournament algorithm (Informal Theorem 1, Theorem 1), and a computationally efficient algorithm for spherical and diagonal-covariance Gaussians whose sample complexity is controlled by the Gaussian surface area of the set family (Informal Theorems 2 and 3, Theorem 2). The technical engine is a Hermite-expansion approximation of the weighted indicator function ψ(x)=1_S(x) N*(x)/(α*N0(x)), followed by a convex stochastic-gradient optimization over the Gaussian parameters and a thresholding step to recover the set. The paper also proves a moment-matching identifiability result (Theorem 8) and a lower-bound construction (Theorem 7) intended to show that the surface-area dependence is tight. The proofs are detailed and mostly self-contained, with several technical lemmas deferred to the appendices.","tokens_in":40900,"tokens_out":10644,"duration_ms":114928,"significance":"If the proofs are sound, this is a significant contribution to high-dimensional truncated statistics: it is the first efficient algorithm for unknown truncation sets with guarantees governed by Gaussian surface area, it covers non-ERM families such as convex sets, and it includes a clean set-recovery corollary. The Hermite-concentration analysis of the weighted indicator and the convex SGD formulation are substantial and plausible. The paper is also honest about the distinction between VC-dimension and surface-area approaches. The main technical obstruction is Lemma 3, whose proof is not currently valid; since that lemma is load-bearing for the VC-dimension result and for the diagonal-covariance extension, the full scope of the claims is not yet established. The lower bound in Section 5 is also presented as a heuristic rather than a formal minimax argument. Both issues are fixable in a revision, so the paper merits major revision rather than rejection.","major_comments":[{"comment":"The proof of Lemma 3 does not establish the claimed lower bound. The displayed chain lower-bounds E[|1-exp(p)|1_S] by E[|p|/2 1_{S\\Q}] using |1-e^x|≥|x|/2 for |x|≤1, but the set S is defined by |1-exp(p)|≤T and the argument only shows N0(S\\Q)≥α/4; it does not show that |p|≤1 on S\\Q, and for p very negative the inequality fails since |1-e^p|≤1 while |p|/2 is unbounded. This step is load-bearing: Lemma 3 is used in Theorem 1 to transfer truncated-TV closeness to parameter-TV closeness and in the reduction from arbitrary diagonal covariance to the isotropic algorithm. I recommend replacing the pointwise inequality by the globally valid bound |1-e^p|≥min(1,|p|/2) and then controlling the mass of {p<−1} inside S\\Q, or proving a uniform upper bound on T. In addition, the 'relaxed optimization' objective (1/α)∫|N(0,I;x)-(α/β)N(μ,Λ;x)|1_S(x)dx is not shown to be a lower bound on dTV(D1,D2): the true truncated densities have normalizing constants α1,α2 which need not equal α, and the free parameter β only adjusts the second density. The proof must justify this reduction before the lemma can be used.","section":"Section 3, Lemma 3"},{"comment":"The lower-bound proof is heuristic rather than a formal minimax argument. The claim that distinguishing N+(S+) from the reference density r requires a birthday collision is not supported by a reduction, and the event |Σ(pV−p)|<2^{-d/2} controls only one error term; it does not rule out algorithms that exploit the continuous sample coordinates inside each cube HV or that test other statistics of the sample. To establish the claimed Ω(2^{d/2}) lower bound for mean estimation, the proof should be recast as a two-point or Le Cam/Fano argument over pairs of hypotheses whose means are separated by Ω(1). As written, the tightness claim in the abstract and Section 6 is not established.","section":"Section 5, Theorem 7"}],"minor_comments":[{"comment":"The symbol S is used both for the family of sets and for the intersection set S1∩S2, which makes this proof unnecessarily confusing.","section":"Section 3, Lemma 3 proof"},{"comment":"The equality ∑_{|V|≥k} should be ∑_{|V|>k} (or the definition of Skψ should be made consistent), since Skψ contains all Hermite terms of degree at most k.","section":"Section 4.1, Theorem 3"},{"comment":"The sentence 'Hence we can we lose probability at most δ' contains a typo, and the probability accounting around the median-selection of the SGD runs is compressed; it should be spelled out in full.","section":"Section 4.2, proof of Theorem 2"},{"comment":"The sentence 'Dχ2(N1‖N) Dχ2(N2‖N) are finite' is missing a conjunction and is hard to parse; it should be 'Dχ2(N1‖N) and Dχ2(N2‖N) are finite'.","section":"Section 6, Lemma 14"},{"comment":"Informal Theorem 3 does not mention the affine-invariance assumption Γ(T(S))=O(Γ(S)) that is stated in Theorem 8; without that assumption the informal statement overclaims what is proved.","section":"Introduction, Informal Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The Lemma 3 issue is the key technical blocker: Theorem 1 and the diagonal-covariance reduction depend on it, and the current proof contains a pointwise inequality that fails on the set to which it is applied. I believe the lemma is likely repairable, since the globally valid inequality |1-e^p|≥min(1,|p|/2) plus a tail-mass argument may recover an Ω(α^3)-type constant, but the normalization issue with α1,α2 also needs to be addressed explicitly. The lower bound in Theorem 7 needs to be converted from a birthday heuristic into a formal two-point argument; this is also within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real advance—first efficient algorithm for unknown truncation sets, with sample complexity controlled by Gaussian surface area—but the current write-up has a gap in a load-bearing lemma and a lower bound that is more heuristic than formal. I don't think the advertised parameter-recovery claims are fully proven as written.\n\nWhat's genuinely new and good: the Hermite concentration bound for the weighted characteristic function ψ (Theorems 3–4) is a nice extension of [KOS08] to positive-only samples, and the convex objective Mψk with SGD and strong convexity (Lemmas 10–12) is a clever decoupling trick. The moment-matching lemma (Lemma 15) is also a valuable contribution. The paper is self-contained, and the citations to [DGTZ18] are appropriate.\n\nThe main problem is Lemma 3. The proof relaxes to unnormalized densities and then lower-bounds E[|1−e^p| 1_{S\\Q}] by E[|p|/2 1_{S\\Q}], invoking |1−e^x| ≥ |x|/2 for |x| ≤ 1. But the set S is defined by |1−e^p| ≤ T, and when T > 1 it contains points with p very negative; for those points the inequality fails (LHS ≤ 1, RHS arbitrarily large). The proof never bounds T, so the Ω(α^3) transfer does not follow. Since Lemma 3 is used for the VC-dimension theorem and for the diagonal-covariance corollary, those parts are currently unsubstantiated. The spherical-Gaussian algorithm (Theorem 2) may be salvageable because it goes through parameter-space strong convexity, but that needs checking.\n\nThe lower bound (Theorem 7) is also a sketch: the birthday-problem collision argument is intuitive but not a formal minimax lower bound, and the step from \"expected density equals r\" to \"needs √(2^d) samples\" is not fully justified. It might be right, but it's not proven.\n\nThe simulations are illustrative; no code or details, so they don't add much.\n\nBottom line: this is a paper for TCS/statistics readers working on truncated estimation. It deserves a serious referee, but the referee should insist on a fixed Lemma 3 and a more rigorous lower bound before accepting. I'd send it out.","headline":"Real advance in unknown truncation, but a proof gap in Lemma 3 and a heuristic lower bound mean the advertised guarantees need work before I'd trust them.","tokens_in":41428,"tokens_out":7122,"would_cite":false,"duration_ms":70459,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F10","62H12","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Efficient recovery of Gaussian parameters is possible even when the truncation set is unknown.","keywords":["truncated statistics","unknown truncation set","Gaussian surface area","VC dimension","Hermite polynomials","stochastic gradient descent","Gaussian parameter estimation","moment matching"],"falsifier":"Search in $\\mathbb{R}^2$ for two Gaussians with $\\|\\mu_1-\\mu_2\\|_2>1$ and $\\|\\Sigma_1-\\Sigma_2\\|_F>1$, together with sets $S_1,S_2$ of mass at least $\\alpha=0.1$, such that $d_{\\mathrm{TV}}(\\mathcal{N}(\\mu_1,\\Sigma_1,S_1),\\mathcal{N}(\\mu_2,\\Sigma_2,S_2))$ is smaller than $(\\alpha^3/8)\\,d_{\\mathrm{TV}}(\\mathcal{N}(\\mu_1,\\Sigma_1),\\mathcal{N}(\\mu_2,\\Sigma_2))$. An explicit pair, or a numerical optimizer that drives the ratio to zero while respecting the mass lower bound, would directly falsify Lemma 3 and with it the parameter-recovery chain.","tokens_in":40402,"feed_emoji":"🎯","tokens_out":10071,"duration_ms":91405,"temperature":0.7,"pith_summary":"This paper claims that the parameters of a Gaussian can be recovered efficiently from samples that have been filtered through an unknown set, provided the family of possible truncation sets has bounded complexity. The main result is an algorithm that learns both the mean and the covariance of a spherical or diagonal Gaussian using $d^{\\mathrm{poly}(1/\\alpha,1/\\varepsilon)\\,\\Gamma(\\mathcal{C})^2}$ samples, where $\\Gamma(\\mathcal{C})$ is the Gaussian surface area of the set family, a measure of how much Gaussian mass sits near the set's boundary, and runs in polynomial time. A complementary result shows that, for any family of sets with VC-dimension $\\mathrm{VC}(\\mathcal{C})$, only $\\tilde O(\\mathrm{VC}(\\mathcal{C})/\\varepsilon + d^2/\\varepsilon^2)$ samples suffice, and a lower bound shows the dependence on set complexity is close to necessary. A sympathetic reader would care because this resolves the unknown-truncation case of a classical problem whose known-truncation version was only solved in 2018, and it says that not knowing the truncation set is not a fundamental barrier to estimation.","feed_headline":"Unknown truncation no longer blocks Gaussian recovery","feed_subtitle":"New algorithm recovers mean and covariance from samples truncated by an unknown set, with near-tight sample bounds.","key_machinery":"The load-bearing object is the weighted characteristic function $\\psi(x)=1_S(x)\\alpha_*^{-1}\\mathcal{N}(\\mu_*,\\Sigma_*;x)/\\mathcal{N}(0,I;x)$, which entangles the unknown set with the unknown Gaussian and whose Hermite coefficients are exactly the expectations $\\mathbb{E}_{x\\sim\\mathcal{N}(\\mu_*,\\Sigma_*,S)}[H_V(x)]$ that samples reveal. The argument is carried by three identities: the tail of the Hermite expansion of $\\psi$ is bounded by $\\mathrm{poly}(1/\\alpha)(\\sqrt{\\Gamma(S)}/k^{1/4}+1/k)$; the objective $M_f(u,B)=\\mathbb{E}_{x\\sim\\mathcal{N}(\\mu_*,\\Sigma_*,S)}[e^{h(u,B;x)}\\mathcal{N}(0,I;x)f(x)]$ is convex in $(u,B)$, with minimizer $(\\Sigma_*^{-1}\\mu_*,\\Sigma_*^{-1})$ when $f=\\psi$; and the set can be recovered by thresholding $\\psi_k\\mathcal{N}(0,I;x)/\\mathcal{N}(\\hat\\mu,\\hat\\Sigma;x)$ at $1/2$. The algorithm's steps are therefore: estimate low-degree Hermite coefficients from truncated samples, run projected SGD on the convex objective, then threshold to recover the set.","core_discovery":"The central claim, on the paper's own terms, is that unknown truncation can be decoupled from the Gaussian parameters. The algorithm never learns the truncation set first; instead it estimates a weighted characteristic function $\\psi(x)=1_S(x)\\alpha_*^{-1}\\,\\mathcal{N}(\\mu_*,\\Sigma_*;x)/\\mathcal{N}(0,I;x)$ from truncated samples, relying on the proof that this function has low-degree Hermite concentration when $S$ has bounded Gaussian surface area. Once a low-degree approximation $\\psi_k$ is in hand, the paper defines a convex objective $M_{\\psi_k}(u,B)$ whose unique minimizer is $(\\Sigma_*^{-1}\\mu_*,\\Sigma_*^{-1})$, found by projected stochastic gradient descent. The same function, thresholded against the recovered Gaussian, also identifies the set $S$ up to small Gaussian measure. The abstract's strongest claim is Informal Theorem 2: with $N=d^k$ samples for $k=\\mathrm{poly}(1/\\alpha,1/\\varepsilon)\\,\\Gamma(S)^2$, the output $\\hat\\mu,\\hat\\sigma^2I$ satisfies $d_{\\mathrm{TV}}(\\mathcal{N}(\\mu,\\sigma^2 I),\\mathcal{N}(\\hat\\mu,\\hat\\sigma^2 I))\\le\\varepsilon$.","pith_inferences":["Beyond the paper, the decoupling recipe—weighted indicator, Hermite concentration, convex objective—is not obviously tied to Gaussians; the same outline could be attempted for any exponential family with a quadratic log-density, with Gaussian surface area replaced by that family's isoperimetric profile.","Beyond the paper, the sample bounds make concrete predictions for structured families: for intersections of $k$ halfspaces the bound is $d^{O(\\log k)}$, so experiments on that family could reveal whether the true constant is closer to the bound than the convex-set case suggests.","Beyond the paper, the moment-matching theorem implies truncated Gaussians are identifiable from finitely many moments; checking whether $O(\\Gamma^2/\\varepsilon^4)$ can be replaced by a smaller degree for axis-aligned rectangles or unions of boxes would separate the statistical from the computational content of the result."],"forward_implications":["Any set family with VC-dimension $\\mathrm{VC}(\\mathcal C)$ admits recovery of the Gaussian mean and covariance to total-variation $\\varepsilon$ from $\\tilde O(\\mathrm{VC}(\\mathcal C)/\\varepsilon + d^2/\\varepsilon^2)$ samples.","For spherical and diagonal Gaussians, families with Gaussian surface area $\\Gamma(\\mathcal C)$ can be handled in polynomial time with $d^{\\mathrm{poly}(1/\\alpha,1/\\varepsilon)\\Gamma(\\mathcal C)^2}$ samples; this covers intersections of halfspaces, polynomial threshold functions, and all convex sets.","The same samples suffice to recover the truncation set itself: the algorithm outputs a set whose symmetric difference with the true set has Gaussian mass below $\\varepsilon$.","Moment matching is sufficient for identification: matching moments up to degree $O(\\Gamma(S)/\\varepsilon^4)$ forces the truncated Gaussians, and hence the untruncated parameters, to be $\\varepsilon$-close.","The lower bound shows that some sets with small Gaussian surface area ($\\Gamma(S)=O(d)$) still force $\\Omega(2^{d/2})$ samples, so the polynomial dependence on $\\Gamma$ cannot be replaced by a fixed polynomial in $d$ alone."],"supporting_citations":[{"why":"supplies the known-truncation efficient estimator this paper extends, plus technical lemmas for conditional mean and covariance estimation.","marker":"[DGTZ18]"},{"why":"supplies the Gaussian-surface-area complexity measure and the noise-sensitivity bound used to prove Hermite concentration of the weighted indicator.","marker":"[KOS08]"},{"why":"supplies the polynomial anti-concentration theorem used to lower-bound Gaussian mass of sublevel sets in Lemma 3 and in the strong-convexity argument.","marker":"[CW01]"},{"why":"bounds the Gaussian surface area of polynomial threshold functions, used in the class-complexity table and in the lower-bound construction.","marker":"[Kan11]"},{"why":"supplies the projected SGD convergence theorem and the strong-convexity implication used to analyze the optimization stage.","marker":"[SSBD14]"},{"why":"supplies the tournament procedure used to select among candidate hypotheses in the VC-dimension sample-complexity bound.","marker":"[DK14]"},{"why":"provides the lemma that converts noise stability into Hermite tail bounds, the engine of the low-degree approximation.","marker":"[KKMS05]"},{"why":"supplies the equivalence between Gaussian surface area and Gaussian perimeter used in the lower-bound proof.","marker":"[Naz03]"}],"fun_headline_variants":["Truncation unknown? Gaussian still recoverable","Hidden truncation, recovered Gaussian","Gaussian estimation without the truncation set","Recover Gaussians from samples with unknown cuts","Efficient Gaussian recovery under unknown truncation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 3, which asserts that truncation cannot make two genuinely different Gaussians look alike: two Gaussians at total-variation distance $\\varepsilon$ remain at least $C_\\alpha \\varepsilon$ apart after any truncation to sets of mass at least $\\alpha$, with $C_\\alpha=\\Omega(\\alpha^3)$. If that normalization lower bound fails, closeness of truncated distributions would not certify closeness of the underlying Gaussians, and both the VC-dimension recovery theorem and the abstract's parameter-recovery guarantee would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Truncation unknown? Gaussian still recoverable","Hidden truncation, recovered Gaussian","Gaussian estimation without the truncation set","Recover Gaussians from samples with unknown cuts","Efficient Gaussian recovery under unknown truncation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1748,"prompt_tokens":1006,"completion_tokens":742,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":676}},"tokens_in":622,"tokens_out":742,"duration_ms":7677,"temperature":1.0,"reasoning_tokens":676,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:26:29.781402+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search in $\\mathbb{R}^2$ for two Gaussians with $\\|\\mu_1-\\mu_2\\|_2>1$ and $\\|\\Sigma_1-\\Sigma_2\\|_F>1$, together with sets $S_1,S_2$ of mass at least $\\alpha=0.1$, such that $d_{\\mathrm{TV}}(\\mathcal{N}(\\mu_1,\\Sigma_1,S_1),\\mathcal{N}(\\mu_2,\\Sigma_2,S_2))$ is smaller than $(\\alpha^3/8)\\,d_{\\mathrm{TV}}(\\mathcal{N}(\\mu_1,\\Sigma_1),\\mathcal{N}(\\mu_2,\\Sigma_2))$. An explicit pair, or a numerical optimizer that drives the ratio to zero while respecting the mass lower bound, would directly falsify Lemma 3 and with it the parameter-recovery chain.","supporting_citations":[],"review_version":1}