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

1. Problem Statement

The paper addresses the fundamental challenge of learning the natural parameters $z \in \mathbb{R}^n$ of a discrete Boolean product distribution $\mu_z$ from independent samples constrained to a subset $S \subseteq \{0, 1\}^n$. This is known as learning from truncated samples.

Existing methods, particularly the work of [Fotakis et al., COLT'20, Algorithmica '22], face significant limitations:

1. Dependence on Survival Mass: Their sample complexity scales as $\Omega(2^n)$ if the mass of the truncation set $\mu(S)$ is exponentially small.
2. Stringent Connectivity Assumptions: They require "fatness," a strong local connectivity condition where, for every coordinate $i$, the probability that flipping the $i$-th bit keeps the sample within $S$ is at least $1/\text{poly}(n)$.
3. Anti-Concentration Requirements: They necessitate global anti-concentration conditions (e.g., covariance lower bounds) that often force the survival mass to be constant with respect to $n$.
4. Sampling Constraints: Their stochastic gradient methods require estimating gradients at arbitrary parameterizations of the model, necessitating rejection sampling from the truncated distribution for many nearby parameters—a task that is computationally intractable for general distributions.

The central question posed is whether computationally efficient algorithms exist to learn truncated Boolean product distributions without dependence on the survival mass or stringent local connectivity conditions.

2. Methodology and Framework

The authors propose a framework that circumvents these limitations by analyzing the geometry of the truncation set $S$ under the measure $\mu_z$. Instead of relying on global properties or single-bit flips, the method leverages conditional influence and local signed linear measurements.

2.1 Refinement of Fatness (Single-Bit Flips)

The paper first refines the existing "fatness" assumption. A distribution is $\gamma$-fat in coordinate $i$ if, with probability at least $\gamma$ over samples $x \sim \mu_{z|S}$, the neighbor $(1-x_i, x_{-i})$ also lies in $S$.

• Mechanism: Under this condition, the algorithm estimates each coordinate $z_i$ independently. It filters samples to those where the $i$-th bit is "flippable" (i.e., both $0$ and $1$ are feasible given the other coordinates).
• Estimation: On this filtered subsample, the conditional distribution of $x_i$ remains a Bernoulli distribution with parameter $p_i$. The authors utilize a one-dimensional logistic regression framework (minimizing empirical loss) to estimate $z_i$.
• Improvement: This approach improves the sample complexity for $\ell_\infty$-recovery to $O(\log n / (\gamma \epsilon^2))$, matching the untruncated minimax rate and removing the dependence on the global survival mass.

2.2 Generalization via Conditional Influence (Multi-Bit Flips)

Recognizing that many natural sets (e.g., the parity set) violate single-bit fatness, the authors generalize the concept using Conditional Influence.

• Definition: For a set of coordinates $I \subseteq [n]$, the conditional influence is defined as $\text{Inf}_{\mu_{z|S}}^I := \Pr_{x \sim \mu_{z|S}}[x \oplus I \notin S]$, where $x \oplus I$ flips all bits in $I$.
• Core Idea: Even if single-bit flips are impossible, learning may be possible if there exist small sets $I$ (of size up to $k$) such that flipping all bits in $I$ simultaneously keeps the sample in $S$ with non-negligible probability.
• Linear Form Estimation: When a flip of set $I$ is feasible, the conditional distribution of the signed sum $w_I^\top x$ (where $w_I$ is a vector with $\pm 1$ on $I$ and $0$ elsewhere) reveals information about the linear form $w_I^\top z$.
• Algorithm:
  1. Discovery: Enumerate candidate sets $I$ (up to size $k$) and identify those where the "minimal flip" event (flipping $I$ is feasible, but flipping any proper subset is not) occurs with sufficient probability.
  2. Estimation: For each valid pair $(I, \text{sign})$, estimate the linear form $y_I = w_I^\top z$ using a constrained maximum likelihood estimator on the observed orientations.
  3. Recovery: Assemble these estimates into a linear system $y = Wz$. If the signed design matrix $W$ (formed by the vectors $w_I$) is well-conditioned (Assumption 4.2), solve for $z$ using weighted least squares.

2.3 Structural Assumptions

The method relies on two structural assumptions rather than global mass or anti-concentration:

1. Bounded Influences (Assumption 4.1): There exists a family of sets $\mathcal{F}$ such that for every $I \in \mathcal{F}$, the probability of a minimal flip is at least $\gamma$.
2. Signed Anti-Concentration / Flip Directions (Assumption 4.2): The vectors $w_I$ associated with these sets must span $\mathbb{R}^n$ in a quantitatively stable way (the Gram matrix has a lower bound $\lambda_s$ on its eigenvalues).

3. Key Contributions and Results

3.1 Improved Sample Complexity under Fatness

For distributions satisfying the $\gamma$-fatness condition, the authors provide polynomial-time algorithms that achieve:

• Natural Parameter ($z$) Estimation: Sample complexity $N = O\left(\frac{e^{2R} \log(n/\delta)}{\gamma \epsilon^2}\right)$.
• Probability ($p$) Estimation: Sample complexity $N = O\left(\frac{\log(n/\delta)}{\gamma \epsilon^2}\right)$.
• Significance: These bounds match the minimax rate for untruncated distributions (up to logarithmic factors) and depend only on the local parameter $\gamma$, not the global survival mass $\mu(S)$.

3.2 Efficient Learning Beyond Fatness

The primary contribution is the extension to sets where single-bit connectivity fails.

• Theorem 2 (Informal): For a fixed $k$, if the truncation set satisfies the minimal-flip and signed-design assumptions with parameters $\gamma$ and $\lambda_s$, there exists a polynomial-time algorithm (in $n, 1/\epsilon, \log(1/\delta)$) that estimates $z$ with $\ell_2$-error $\epsilon$.
• Sample Complexity: $N \geq O\left( \frac{2^k e^{2kR}}{\gamma \lambda_s \epsilon^2} \left( k \log(2n) + \log \frac{4k}{\delta} \right) \right)$.
• Key Feature: The method does not require sampling from the untruncated distribution or estimating gradients at arbitrary parameterizations. It operates solely on samples from the truncated distribution.

3.3 Information-Theoretic Lower Bound

The paper establishes a lower bound demonstrating that the exponential dependence on the "width" of the model is intrinsic.

• Theorem 3 (Informal): If the truncation set $S$ has distinct elements separated by Hamming distance at least $k$ (meaning no flip of fewer than $k$ coordinates is feasible), then any estimator requires sample complexity scaling as $\Omega\left( \frac{n \exp(kR/2)}{k^2 \epsilon^2} \right)$.
• Implication: The exponential factor $\exp(kR)$ arises from the local geometry: if transitions between feasible configurations require changing $k$ coordinates, and each coordinate contributes energy up to $R$, the probability of observing informative transitions is exponentially small.

4. Significance and Claims

The paper claims to resolve the open question of whether efficient learning is possible for truncated Boolean product distributions without dependence on survival mass or stringent local connectivity.

• Generalization: By generalizing "fatness" to "conditional influence," the framework captures a much wider range of truncation sets, including those with no single-bit neighbors (like the parity set), provided higher-order flips are feasible.
• Computational Efficiency: Unlike previous stochastic gradient methods, this approach avoids the need for rejection sampling from a family of truncated distributions. It relies on local connectivity and linear algebra, making it applicable even when sampling from the untruncated model is hard.
• Tightness: The authors demonstrate that their sample complexity bounds are tight up to polynomial factors by providing a matching lower bound that highlights the intrinsic difficulty of "wide" truncation sets.
• Future Directions: The work opens questions regarding the precise relationship between influence and Fisher information, the transferability of these techniques to more complex discrete distributions (e.g., Markov Random Fields), and learning when the truncation set is unknown but belongs to a class with low influences.

In summary, the paper provides a theoretically grounded and computationally efficient framework for parameter estimation in truncated Boolean product distributions, moving beyond the limitations of survival mass and single-bit connectivity by leveraging the geometric structure of the truncation set through the lens of Boolean function influence.