# Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 24 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Privately Learning Markov Random Fields](https://mlsanity.com/paper/2002.09463/) (2020)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Efficient Parameter Estimation of Truncated Boolean Product Distributions](https://mlsanity.com/paper/2007.02392/) (2020)
- [On the Analysis of EM for truncated mixtures of two Gaussians](https://mlsanity.com/paper/1902.06958/) (2019)
- [Efficient Truncated Linear Regression with Unknown Noise Variance](https://mlsanity.com/paper/2208.12042/) (2022)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Linear Regression with Unknown Truncation Beyond Gaussian Features](https://mlsanity.com/paper/2602.12534/) (2026)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Influence of a Set of Variables on a Boolean Function](https://mlsanity.com/paper/2107.08676/) (2021)
- [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025)

## Abstract (arXiv)

Learning the natural parameters z ∈ ℝn of discrete distributions μz from independent samples constrained to a subset S subseteq 0,1n is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al' COLT'20, Algorithmica '22], require either strong local connectivity assumptions on S -- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to n. Moreover, the results in [Fotakis et al' COLT'20, Algorithmica '22] suffer from sample complexities that scale as Omega(2n) if the mass of S is exponentially small in n. In this work, we circumvent these limitations by analyzing the geometry of S under the measure μz. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to O( log n / ε2) for ℓ_∞-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.