Research map / Learning theory and algorithms / Sample complexity

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

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning under log-concave distributions · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives improved sample complexity for learning truncated Boolean product distributions under fatness (O(log n/ε²) for ℓ∞ on p), and extends to higher-order influence-based sparse signed flip directions, with an exponential lower bound in kR.

Problem

Estimating natural/probability parameters of Boolean product distributions from i.i.d. samples truncated to an arbitrary set S, without dependence on survival mass or strong local connectivity (single-flip fatness) assumptions.

Approach

Replaces single-coordinate fatness with conditional influence of multi-bit flips: estimates sparse signed linear forms w_I^T z from samples where only the flip of set I is feasible (minimal flips), then solves a weighted least-squares inverse problem; also shows an exp(kR) lower bound on sample complexity.

Key results

• Under gamma-fatness, estimating p to l_inf error epsilon needs O(log(n/δ)/(γε²)) samples, improving prior results by a log n factor and matching the minimax rate for constant γ.
• Under higher-order influence assumptions, the estimator needs N = O(2^k e^{2kR}/(γλ_s ε²)(k log(2n)+log(4k/δ))) samples, polynomial when R = Θ(log n).
• A lower bound shows Ω(n exp(kR/2)/(k²ε²)) samples are necessary for a construction with minimal Hamming separation k, exhibiting exponential dependence on kR.

Surprising findings

• Fatness-based sample complexity bound for natural parameters carries an e^{2R} factor, while the lower bound shows exponential dependence on kR is unavoidable for multi-bit flip structure.

Limitations

• Influence-based estimator requires enumerating all sets of size up to k, giving n^{O(k)} runtime.
• Sample complexity is exponential in kR, so only polynomial for R = O(log n) and k constant.
• Requires assumptions on minimal-flip probability gamma and signed design conditioning lambda_s that may be hard to verify.

Experimental setup

Metrics: sample complexity l_infinity error l_2 error

Baselines: Fotakis et al. (COLT'20) fatness-based estimator projected stochastic gradient descent under truncation

Builds on: Fotakis et al. fatness framework (COLT'20/Algorithmica'22) Daskalakis et al. truncated statistics Boolean function influence

Closest papers by meaning

• On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions (ICML 2024 · similarity 0.85)
• Mean Testing under Truncation beyond Gaussian (NeurIPS 2026 · similarity 0.85)
• Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.84)
• Product Distribution Learning with Imperfect Advice (NeurIPS 2025 · similarity 0.84)
• Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.84)
• Sampling Binary Data by Denoising through Score Functions (ICML 2025 · similarity 0.84)