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

• URL: http://arxiv.org/abs/2607.22889v1
• Date: Fri, 24 Jul 2026 20:01:15 GMT
• Title: Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
• Abstract summary: Learning the natural parameters $z in mathbbRn$ from independent samples constrained to a subset $S subseteq 0,1n$ is a foundational challenge in high-dimensional statistics.<n>We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( log n / 2)$ for $ell_infty$-recovery, matching the untruncated minimax rate.
• Score: 17.761018390014602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $μ_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ 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 $Ω(2^n)$ 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 $\ell_\infty$-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.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Breaking the Finite-Sample Barrier in Entropy Coupling [9.251944578856843]
  Dependence among marginally constrained observations can break a finite-sample barrier.<n>We formalize this phenomenon by introducing the emphminimum list entropy coupling $H(P|Q_1,dots,Q_m)$.<n>We show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction.
  arXiv  Detail & Related papers  (2026-05-15T17:39:57Z)
• Generalization Properties of Score-matching Diffusion Models for Intrinsically Low-dimensional Data [32.72306410557258]
  We study the statistical convergence of score-based diffusion models for learning an unknown distribution $$ from finitely many samples.<n>Our results demonstrate that diffusion models naturally adapt to the intrinsic geometry of data.<n>Our theory conceptually bridges the analysis of diffusion models with that of GANs and the sharp minimax rates established in optimal transport.
  arXiv  Detail & Related papers  (2026-03-04T03:59:02Z)
• Locally minimax optimal confidence sets for the best model [40.60301522036206]
  This paper tackles a fundamental inference problem: given $n$ observations from a distribution $P$ over $mathbbRd$ with unknown mean $boldsymbolmu$, we must form a confidence set for the index corresponding to the smallest component of $boldsymbolmu$.<n>We propose "dimension-agnostic" tests that maintain validity regardless of how $d$ scales with $n$, and regardless of arbitrary ties in $boldsymbolmu$.
  arXiv  Detail & Related papers  (2025-03-27T16:06:07Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
  We consider a reinforcement learning setting in which the deployment environment is different from the training environment. Applying a robust Markov decision processes formulation, we extend the distributionally robust $Q$-learning framework studied in Liu et al. This is the first sample complexity result for the model-free robust RL problem.
  arXiv  Detail & Related papers  (2023-02-26T01:15:32Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Efficient Parameter Estimation of Truncated Boolean Product Distributions [26.396901523831534]
  This is the first time that the computational and statistical complexity of learning from truncated samples is considered in a discrete setting. We show that if the truncation set is sufficiently fat, samples from the true distribution can be generated from truncated samples.
  arXiv  Detail & Related papers  (2020-07-05T17:20:39Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Optimal rates for independence testing via $U$-statistic permutation tests [7.090165638014331]
  We study the problem of independence testing given independent and identically distributed pairs taking values in a $sigma$-finite, separable measure space. We first show that there is no valid test of independence that is uniformly consistent against alternatives of the form $f: D(f) geq rho2 $.
  arXiv  Detail & Related papers  (2020-01-15T19:04:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.