# Testing Convex Truncation

arXiv: https://arxiv.org/abs/2305.03146 · HTML: https://mlsanity.com/paper/2305.03146/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2023.

## Built on by (most cited first, 8 of 8)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)

## Abstract (arXiv)

We study the basic statistical problem of testing whether normally distributed n-dimensional data has been truncated, i.e. altered by only retaining points that lie in some unknown truncation set S subseteq ℝn. As our main algorithmic results, (1) We give a computationally efficient O(n)-sample algorithm that can distinguish the standard normal distribution N(0,In) from N(0,In) conditioned on an unknown and arbitrary convex set S. (2) We give a different computationally efficient O(n)-sample algorithm that can distinguish N(0,In) from N(0,In) conditioned on an unknown and arbitrary mixture of symmetric convex sets. These results stand in sharp contrast with known results for learning or testing convex bodies with respect to the normal distribution or learning convex-truncated normal distributions, where state-of-the-art algorithms require essentially n^√n samples. An easy argument shows that no finite number of samples suffices to distinguish N(0,In) from an unknown and arbitrary mixture of general (not necessarily symmetric) convex sets, so no common generalization of results (1) and (2) above is possible. We also prove that any algorithm (computationally efficient or otherwise) that can distinguish N(0,In) from N(0,In) conditioned on an unknown symmetric convex set must use Omega(n) samples. This shows that the sample complexity of each of our algorithms is optimal up to a constant factor.