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

# Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
Source: [https://arxiv.org/html/2607.22889](https://arxiv.org/html/2607.22889)
Ioannis Panageas222University of California, Irvine,[ipanagea@uci\.edu](https://arxiv.org/html/2607.22889v1/[email protected]), Supported by NSF grant CCF\-2454115 University of California, Irvine

###### Abstract

Learning the natural parametersz∈ℝnz\\in\\mathbb\{R\}^\{n\}of discrete distributionsμz\\mu\_\{z\}from independent samples constrained to a subsetS⊆\{0,1\}nS\\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 onSS– a property denotedfatness– or stringent anti\-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect tonn\. Moreover, the results in \[Fotakis et al’ COLT’20, Algorithmica ’22\] suffer from sample complexities that scale asΩ​\(2n\)\\Omega\(2^\{n\}\)if the mass ofSSis exponentially small innn\.

In this work, we circumvent these limitations by analyzing the geometry ofSSunder the measureμz\\mu\_\{z\}\. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to𝒪​\(log⁡n/ϵ2\)\\mathcal\{O\}\(\\log n/\\epsilon^\{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\.

## 1Introduction

Learning fromtruncated samplesis a storied and challenging problem within the field of statistics, wherein the objective is to estimate the model parameters of the underlying true distribution given samples which lie on a subsetSSof the support of the measure\. Truncated samples appear in many fields, such as economics, engineering, biological sciences, and networks, among others, with classical examples including sampling bias when gathering subjects for medical experiments and survivor bias in actuarial analysis\. Rigorous statistical estimation from truncated samples dates back at least to 1760, with Daniel Bernoulli’s analysis of the efficacy of smallpox treatmentsbernoulli1760essai\. This analysis initiated a line of work investigated by Pearson, Galton, and Fisher\(galton1898examination;pearson1902systematic;pearson1908generalised;fisher1931properties\), which aimed to develop techniques to robustly estimate and test in truncated environments\.

In recent years, there has been a flurry of activity in developing computationally and statistically efficient algorithms for learning both continuous and discrete distributions under truncation\. Beginning with the work ofdaskalakis2018efficientwhich analyzed the proper learning of multivariate Gaussians under aknowntruncation set, provably efficient learning guarantees have been extended to multivariate Gaussians under unknown truncationkontonis2019efficient, linear regression with truncated datadaskalakis2019computationally, and exponential families with known or unknown truncationlee2023learning;lee2024efficientas well as other continuous settings\.

Motivated by the numerous examples of complex discrete truncated distributions in genomicseng2019transcriptome;ghosh2001lateraland networksdurvy2006packing;zafer2006blocking, among others,fotakis2022efficientparameterestimationtruncatedinitiated the study of estimating parameters ofdiscretemodels from truncated samples, developing efficient algorithms for inference in truncated Boolean product distributions\. Similar to the techniques used in the aforementioned works concerning truncated estimation in continuous settings, the authors demonstrated that a nontrivial survival mass,μ​\(S\)⩾α\\mu\(S\)\\geqslant\\alpha, and a global anti\-concentration condition, such asCov𝒙∼μ⁡\(𝒙\)⪰λ​I\\operatorname\{Cov\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\}\(\{\\boldsymbol\{x\}\}\)\\succeq\\lambda I, withα,λ\\alpha,\\lambdabeingΘ​\(1\)\\Theta\(1\), are sufficient for inference\. Yet, under these assumptions, the resulting sample complexity can scale as𝗉𝗈𝗅𝗒​\(1/α\)𝗉𝗈𝗅𝗒​\(1/λ\)\\mathsf\{poly\}\(1/\\alpha\)^\{\\mathsf\{poly\}\(1/\\lambda\)\}333See Theorem 4 \(p\. 20\) in the arXiv version \(arXiv:2007\.02392v3\) offotakis2022efficientparameterestimationtruncated\., which becomes prohibitive whenλ=o​\(1\)\\lambda=o\(1\)scales with the problem parameters\. This stands in stark contrast to the associated lower bound found infotakis2022efficientparameterestimationtruncated, which has no dependence onα\\alphaand scales on the order of𝗉𝗈𝗅𝗒​\(1/λ\)\\mathsf\{poly\}\(1/\\lambda\)\. Finding efficient algorithms which operate in this regime is a tantalizing open question\. Moreover, the associated stochastic gradient methods require estimating gradients not only at the true parameter but throughout a neighborhood of candidate models, which entails rejection sampling from a family of truncated distributionsμS\\mu\_\{S\}for many nearby parameters\. Such a requirement is already delicate for product distributions and becomes substantially more untenable for general Markov random fields, where sampling is provably hard\.

The algorithmic guarantees offotakis2022efficientparameterestimationtruncatedwhich do not depend on the survival mass rely on local information; given samples𝒙∼μ\{\\boldsymbol\{x\}\}\\sim\\muthat lie inSS, the authors aim to estimate the underlying parameters via the conditional density𝐏𝐫𝒙∼μ​\(xi∣𝒙−i\)\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\}\(x\_\{i\}\\mid\{\\boldsymbol\{x\}\}\_\{\-i\}\)\. The idea of good “average” local connectivity for any given sample was formalized by\(fotakis2022efficientparameterestimationtruncated\)into the notion offatness, which deems a distributionγ\\gamma\-fat if𝐏𝐫𝒙∼μ​\(\(1−xi,𝒙−i\)∈S\)⩾1/𝗉𝗈𝗅𝗒​\(n\)=γ\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\}\(\(1\-x\_\{i\},\{\\boldsymbol\{x\}\}\_\{\-i\}\)\\in S\)\\geqslant 1/\\mathsf\{poly\}\(n\)=\\gammafor alli∈\[n\]i\\in\[n\]\. The authors then demonstrate efficient parameter estimation and sampling under this condition\. However, in many sets of interest, such as the set of all Boolean vectors with an even number of ones \(the parity set\), no element has a single\-flip neighbor, which violates the assumption and causes the conditional distributions to collapse\.

Remedying this difference, in this work, we examine the task of efficient recovery of the parameters oftruncatedproduct distributions over the hypercube\{0,1\}n\\\{0,1\\\}^\{n\}– the simplest class of discrete distributions – given independent and identically distributed \(i\.i\.d\.\) samples from the underlying model\. We wish to develop a framework to analyze these distributions beyond restrictions on the mass ofSS, strong anti\-concentration assumptions and single\-flip local connectivity, leading to the following question:

Are there computationally efficient algorithms that can learn truncated Boolean product distributions without dependence on the survival mass and stringent local connectivity conditions?

Our primary contribution in this work is a positive answer to the above question by generalizing the notion offatnessto capture a much wider range of truncation sets\.

### 1\.1Our Results

Departing from approaches that require sampling from the untruncated distribution or estimating global gradients of the truncated likelihood, we instead exploit the local structure of the truncation set under the product measure\. Letμ𝒑\\mu\_\{\\boldsymbol\{p\}\}be a Boolean product measure on\{0,1\}n\\\{0,1\\\}^\{n\}, that is, a distribution whose coordinates are independent and𝐏𝐫𝒙∼μ𝒑​\(xi=1\)=pi∈\(0,1\)\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{p\}\}\}\(x\_\{i\}=1\)=p\_\{i\}\\in\(0,1\)\. We assume oracle access to a truncation setS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}and observe samples fromμ𝒑∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}, namely,μ𝒑\\mu\_\{\\boldsymbol\{p\}\}conditioned onSS\. Our primary goal is to compute an estimator𝒑^\\widehat\{\\boldsymbol\{p\}\}of the true parameter vector𝒑\\boldsymbol\{p\}such that, with probability at least1−δ1\-\\delta,‖𝒑^−𝒑‖∞⩽ϵ\\\|\\widehat\{\\boldsymbol\{p\}\}\-\\boldsymbol\{p\}\\\|\_\{\\infty\}\\leqslant\\epsilon, in time polynomial innn,1/ϵ1/\\epsilon, andlog⁡\(1/δ\)\\log\(1/\\delta\)\. We also consider estimation of the corresponding natural parameters𝒛\\boldsymbol\{z\}, defined coordinatewise byzi=log⁡\(pi/\(1−pi\)\)z\_\{i\}=\\log\(p\_\{i\}/\(1\-p\_\{i\}\)\)fori∈\[n\]i\\in\[n\]\. Learning in the𝒑\\boldsymbol\{p\}\-parameterization corresponds to additive error in the Bernoulli probabilities, whereas learning in the𝒛\\boldsymbol\{z\}\-parameterization corresponds to controlling errors in the log\-odds, and hence gives a relative\-error notion for the underlying probabilities\.

Our first contribution is improving the sample complexity of estimation under the assumption that the truncated measureμ𝒑∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}isγ\\gamma\-fat\. Roughly speaking,μ𝒑∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}isγ\\gamma\-fat in coordinateiiif, with probability at leastγ\\gammaover𝒙∼μ𝒑∣S\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{p\}\\mid S\}, the neighboring point\(1−xi,𝒙−i\)\(1\-x\_\{i\},\{\\boldsymbol\{x\}\}\_\{\-i\}\)also lies inSS\. This implies that on aγ\\gamma\-fraction of truncated samples, both values of theii\-th coordinate are feasible while the remaining coordinates are fixed, so the conditional distribution ofxix\_\{i\}reveals the corresponding one\-dimensional marginal information of the original product distribution\. In this sense, fatness is a conditional internal\-connectivity condition onSS\.

###### Informal Theorem 1\(Learning underγ\\gamma\-fatness\)\.

Let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\dots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be i\.i\.d\. samples from aγ\\gamma\-fat truncated Boolean product distributionμ\\mu, and suppose‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. There are polynomial\-time algorithms which estimate the probability vector toℓ∞\\ell\_\{\\infty\}\-errorϵ\\epsilonfrom

N=𝒪​\(log⁡\(n/δ\)γ​ϵ2\)N=\\mathcal\{O\}\\left\(\\frac\{\\log\(n/\\delta\)\}\{\\gamma\\epsilon^\{2\}\}\\right\)samples and estimate the natural parameter vector toℓ∞\\ell\_\{\\infty\}\-errorϵ\\epsilonfrom

N=𝒪​\(e2​R​log⁡\(n/δ\)γ​ϵ2\)N=\\mathcal\{O\}\\left\(\\frac\{e^\{2R\}\\log\(n/\\delta\)\}\{\\gamma\\epsilon^\{2\}\}\\right\)samples, each with probability at least1−δ1\-\\delta\.

This sample complexity improves over previous work by a factor oflog⁡\(n\)\\log\(n\)and matches the minimax rate for estimating truncated Boolean product distributions whenγ∈Θ​\(1\)\\gamma\\in\\Theta\(1\), since estimating each coordinate to accuracyϵ\\epsilonrequires order1/ϵ21/\\epsilon^\{2\}samples and alog⁡\(n/δ\)\\log\(n/\\delta\)factor for uniformℓ∞\\ell\_\{\\infty\}control\. Moreover, this bound depends only on the local fatness parameterγ\\gamma, and has no dependence on the global survival massμ𝒑​\(S\)\\mu\_\{\\boldsymbol\{p\}\}\(S\)\. Assuming fatness, these algorithms give polynomial sample complexity even when the aforementioned anti\-concentration parameterλ∈o​\(1\)\\lambda\\in o\(1\)444The relationship between the width of the modelRRand the anti\-concentration parameter offotakis2022efficientparameterestimationtruncatedis expounded on in Appendix[A](https://arxiv.org/html/2607.22889#A1)\.\.

However, the notion of fatness is too restrictive for many natural truncation sets\. For example, the parity setS=\{x∈\{0,1\}n:∑ixi≡0\(mod2\)\}S=\\\{x\\in\\\{0,1\\\}^\{n\}:\\sum\_\{i\}x\_\{i\}\\equiv 0\\pmod\{2\}\\\}has no single\-coordinate connectivity\. For everyi∈\[n\],𝒙∈Si\\in\[n\],\{\\boldsymbol\{x\}\}\\in S,𝐏𝐫𝒙∼μ𝒛∣S​\(\(1−xi,𝒙−i\)∈S\)=0\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\(\(1\-x\_\{i\},\{\\boldsymbol\{x\}\}\_\{\-i\}\)\\in S\)=0implying any analysis based solely on single\-bit flips is vacuous\. Nevertheless, parity is preserved by two\-bit flips, and conditioning on all coordinates outside\{i,j\}\\\{i,j\\\}yields a nontrivial one\-dimensional Bernoulli problem whose natural parameter is one ofzi\+zjz\_\{i\}\+z\_\{j\}orzi−zjz\_\{i\}\-z\_\{j\}\. This suggests replacing direct coordinate\-wise estimation ofziz\_\{i\}with the estimation of sparse linear forms𝒘I⊤​𝒛\\boldsymbol\{w\}\_\{I\}^\{\\top\}\\boldsymbol\{z\}, where𝒘I∈\{−1,0,1\}n\\boldsymbol\{w\}\_\{I\}\\in\\\{\-1,0,1\\\}^\{n\}is supported on a small coordinate setII\. Formalizing the existence of such higher\-order moves, we use the following notion ofconditional influence\.

###### Definition 1\.1\(Conditional Influence\)\.

Given a truncated Boolean product distributionμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}and a coordinate setI⊆\[n\]I\\subseteq\[n\], define the conditional influence ofIIby

InfIμ𝒛∣S:=𝐏𝐫𝒙∼μ𝒛∣S​\[𝒙⊕I∉S\],\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}:=\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\\!\\left\[\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\notin S\\right\],where𝐱⊕I=\(1−𝐱I,𝐱−I\)\{\\boldsymbol\{x\}\}^\{\\oplus I\}=\(1\-\{\\boldsymbol\{x\}\}\_\{I\},\{\\boldsymbol\{x\}\}\_\{\-I\}\)denotes the vector obtained fromxxby flipping all coordinates inII\.

Thus,InfIμ𝒛∣S\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}is the probability that a sample from the truncated distribution becomes infeasible after the simultaneous flip of the coordinates inII; equivalently, the feasibility probability of this flip is1−InfIμ𝒛∣S1\-\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\. We recall that the conventional notion of Boolean influence records the probability that the value of a Boolean function changes under a specified flip\. In the present setting, Definition[1\.1](https://arxiv.org/html/2607.22889#S1.Thmdefinition1)is the one\-sided version of this notion for the indicator ofSS, conditional on the original point lying inSS\.

Moreover,γ\\gamma\-fatness is equivalent toInf\{i\}μ𝒛∣S⩽1−γ\\textrm\{Inf\}\_\{\\\{i\\\}\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\leqslant 1\-\\gammafor every coordinateii\. Our framework replaces this single\-coordinate requirement by a higher\-order condition: even if every single\-coordinate flip is infeasible, learning may remain possible provided that sufficiently many small setsIIhave feasibility probability1−InfIμ𝒛∣S1\-\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}bounded away from zero and the associated vectors𝒘I\\boldsymbol\{w\}\_\{I\}spanℝn\\mathbb\{R\}^\{n\}in a quantitatively stable way\.

For the model to be identifiable \(see Assumption 1 offotakis2022efficientparameterestimationtruncated\), we require that the affine span ofSSisℝn\\mathbb\{R\}^\{n\}\. This implies that there are feasible flip directions spanningℝn\\mathbb\{R\}^\{n\}\(see Lemma[A\.3](https://arxiv.org/html/2607.22889#A1.Thmlemma3)\)\. Without any quantitative condition beyond identifiability, however, the corresponding feasibility probabilities can be exponentially small and the signed design can be arbitrarily ill\-conditioned\. We therefore impose two structural assumptions\. The first ensures that a family of coordinate setsℱ\\mathcal\{F\}gives minimal feasible flips with probability at leastγ\\gamma\. The second, signed anti\-concentration, ensures that the induced quantities𝒘I⊤​𝒛\\boldsymbol\{w\}\_\{I\}^\{\\top\}\\boldsymbol\{z\}collectively identify every direction of the parameter vector in a quantitatively stable manner\.

Under these assumptions, the inference problem decomposes into three primary steps\. First, using samples, we determine which sets of indices are feasible\. Then, we select the sign of these feasible indices to provide estimates which are assembled into the linear inverse problem𝒚^=W​𝒛\\widehat\{\\boldsymbol\{y\}\}=W\\boldsymbol\{z\}\. IfWWis well conditioned, solving this system yields a stable estimate𝒛^\\widehat\{\\boldsymbol\{z\}\}\. In this sense, higher\-order influence generalizes fatness by replacing direct access to individual coordinates with stable access to sufficiently many local signed linear measurements of the natural parameter\.

###### Informal Theorem 2\.

For fixedkk, letℱ⊆\{I⊆\[n\]:1⩽\|I\|⩽k\}\\mathcal\{F\}\\subseteq\\\{I\\subseteq\[n\]:1\\leqslant\|I\|\\leqslant k\\\}satisfy the minimal\-flip and signed\-design assumptions with parametersγ\\gammaandλs\\lambda\_\{s\}, and suppose‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. There is a polynomial\-time algorithm which, from

N⩾𝒪​\(2k​e2​k​Rγ​λs​ϵ2​\(k​log⁡\(2​n\)\+log⁡4​kδ\)\)N\\geqslant\\mathcal\{O\}\\left\(\\frac\{2^\{k\}e^\{2kR\}\}\{\\gamma\\lambda\_\{s\}\\epsilon^\{2\}\}\\left\(k\\log\(2n\)\+\\log\\frac\{4k\}\{\\delta\}\\right\)\\right\)i\.i\.d\. samples fromμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, returns𝐳^\\hat\{\\boldsymbol\{z\}\}satisfying‖𝐳−𝐳^‖2⩽ϵ\\\|\\boldsymbol\{z\}\-\\hat\{\\boldsymbol\{z\}\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

We again note that our result does not depend on the survival mass of the setSS, and instead leverages information found in the neighborhood of Hamming distance555The Hamming distance metric counts the number of differing indices between two vectors\. Thus, a neighbor at Hamming distancekkis obtained by flipping exactlykkindices of𝒙\{\\boldsymbol\{x\}\}\.kk\. The polynomial sample requirement derives from the regression problem of using the sparse linear forms to estimate the underlying parameters, and depends on the condition number of the matrixW=\[w1w2⋯wm\]W=\\begin\{bmatrix\}w\_\{1\}&w\_\{2\}&\\cdots&w\_\{m\}\\end\{bmatrix\}; this is discussed in greater detail in Section[4](https://arxiv.org/html/2607.22889#S4)\. Moreover, our sample complexity remains polynomial as long asR∈Θ​\(log⁡\(n\)\)R\\in\\Theta\(\\log\(n\)\), making our methods effective for truncated Boolean product distributions beyond constant width\.

Finally, we establish an information\-theoretic lower bound showing that whenInfIμ⁡\(S\)=1\\operatorname\{Inf\}\_\{I\}^\{\\,\\mu\}\(S\)=1uniformly over all subsetsI⊆\[n\]I\\subseteq\[n\]with\|I\|=k\|I\|=k, the sample complexity of learning necessarily scales exponentially inkk\.

###### Informal Theorem 3\.

For every separation scalekkwith2​k∣n2k\\mid n, there exists a truncation setS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}whose distinct elements have Hamming distance at leastkk, and hence no nonempty flip of fewer thankkcoordinates is feasible\. For this set and0<ϵ⩽R​n/160<\\epsilon\\leqslant R\\sqrt\{n\}/16, there is a family of parameter vectors𝐳∗\\boldsymbol\{z\}^\{\*\}with‖𝐳∗‖∞⩽R\\\|\\boldsymbol\{z\}^\{\*\}\\\|\_\{\\infty\}\\leqslant Rsuch that any estimator achieving‖𝐳^−𝐳∗‖2⩽ϵ\\\|\\hat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}^\{\*\}\\\|\_\{2\}\\leqslant\\epsilonwith constant probability requires

N⩾Ω​\(n​exp⁡\(k​R/2\)k2​ϵ2\)N\\geqslant\\Omega\\left\(\\frac\{n\\exp\(kR/2\)\}\{k^\{2\}\\epsilon^\{2\}\}\\right\)samples\.

The lower\-bound construction consists of independent blocks of coordinates, each containing only a few admissible configurations, with any two admissible configurations separated in Hamming distance byΩ​\(k\)\\Omega\(k\)\. When the true parameter𝒛∗\\boldsymbol\{z\}^\{\*\}is aligned with one admissible configuration, the conditional distribution places nearly all its mass on that configuration, while each informative alternative has probability at mostexp⁡\(−Θ​\(k​R\)\)\\exp\(\-\\Theta\(kR\)\)\. Samples therefore rarely visit the configurations required to distinguish nearby parameters\. The obstruction is the local geometry: if transitions between feasible configurations require changingkkcoordinates and each coordinate contributes energy up toRR, then the effective barrier isk​RkR, yielding anexp⁡\(Θ​\(k​R\)\)\\exp\(\\Theta\(kR\)\)sample\-complexity penalty\.

### 1\.2Related Work

Inference and estimation under truncation have long been subjects of interest in statistics\(galton1898examination;pearson1902systematic;pearson1908generalised;fisher1931properties\)\. More recently, numerous efficient algorithms have been developed for statistical learning in this challenging setting, from learning Gaussians\(daskalakis2018efficient;kontonis2019efficient;diakonikolas2024statistical\), to exponential familieshannon1999estimation;lee2023learning;lee2024efficient;lee2025learning;karatapanis2025oracle, linear regression under truncationdaskalakis2019computationally;daskalakis2021efficient;kouridakis2026linear, non\-parametric density estimationdaskalakis2021statistical, mixtures of Gaussiansnagarajan2020analysis;nagarajan2023mean;tai2023learning, the Ising modelchauhan2026learning, and, of particular interest to this work, Boolean product distributionsfotakis2022efficientparameterestimationtruncated; Galaniset al\.\([2024](https://arxiv.org/html/2607.22889#bib.bib3)\);galanis2025oneshotlearningksat, which have formalized the single\-flip local connectivity of samples asfatnessandflippability, respectively\. Many of these works leverage projected stochastic gradient descent to learn the parameters of the model and utilize rejection sampling to compute an unbiased estimate of the gradient\.

In the realm of discrete distributions and graphical models, there has been a parallel line of work leveraging logistic regression for parameter estimation in the Ising modelWuet al\.\([2019](https://arxiv.org/html/2607.22889#bib.bib20)\);gaitonde2023unifiedapproachlearningising; Klivans and Meka \([2017](https://arxiv.org/html/2607.22889#bib.bib21)\);chandrasekaran2025learningand higher\-order Markov random fieldszhang2020privately; Gaitondeet al\.\([2024](https://arxiv.org/html/2607.22889#bib.bib22)\)\. More generally, there have been works on estimating product distributions truncated to the hard\-core gas model and graph coloringsBhattacharya and Ramanan \([2021](https://arxiv.org/html/2607.22889#bib.bib17)\); Galaniset al\.\([2024](https://arxiv.org/html/2607.22889#bib.bib3)\), as well as learning constraint\-satisfaction problems from positive examplesfeng2025learning\. Likewise, the literature on the analysis of Boolean functions over the hypercube is fundamental to theoretical computer scienceo2014analysis\. The notion of influence was introduced bypenrose1946elementaryin the context of genetics and brought to the computer science literature byben1987collective\. Building on this,kahn1989influenceconnected the notion to harmonic analysis on the hypercube, thereby demonstrating that “Boolean functions always have small sets of variables\.” More recently,diakonikolas2010boundinginvestigated the influence of bounded\-degree polynomial truncation functions over the uniform hypercube,KELLER\_2011studied the influence of biased distributions over the hypercube, andbiswas2023influencedeveloped a novel formulation of influence to better represent multi\-bit flips in applications to cryptography\.

## 2Preliminaries

### 2\.1Notation

We denote the set\{1,2,…,n\}\\\{1,2,\\ldots,n\\\}by\[n\]\[n\]\. Vectors𝒙∈ℝn\{\\boldsymbol\{x\}\}\\in\\mathbb\{R\}^\{n\}are denoted with boldface, and matricesM∈ℝm×nM\\in\\mathbb\{R\}^\{m\\times n\}with capital letters\. Given a vector𝐚=\(a1,a2,…,an\)\\mathbf\{a\}=\(a\_\{1\},a\_\{2\},\\dots,a\_\{n\}\)and a subsetI⊆\[n\]I\\subseteq\[n\], let𝐚I\\mathbf\{a\}\_\{I\}denote the length\-\|I\|\|I\|coordinate vector\{ai:i∈I\}\\\{a\_\{i\}:i\\in I\\\}, and𝐚−i\\mathbf\{a\}\_\{\-i\}denote the vector𝐚\\mathbf\{a\}with theii\-th element removed\. For𝒙∈\{0,1\}n\{\\boldsymbol\{x\}\}\\in\\\{0,1\\\}^\{n\}, define its signed encoding by

𝒔​\(𝒙\):=2​𝒙−𝟏∈\{±1\}n\.\\boldsymbol\{s\}\(\{\\boldsymbol\{x\}\}\):=2\{\\boldsymbol\{x\}\}\-\\mathbf\{1\}\\in\\\{\\pm 1\\\}^\{n\}\.Thus,si​\(𝒙\)=2​xi−1s\_\{i\}\(\{\\boldsymbol\{x\}\}\)=2x\_\{i\}\-1throughout the paper\. We write𝒙⊕I\{\\boldsymbol\{x\}\}^\{\\oplus I\}for the vector obtained from𝒙\{\\boldsymbol\{x\}\}by flipping the coordinates inII, i\.e\.,\(x⊕I\)j=1−xj\(x^\{\\oplus I\}\)\_\{j\}=1\-x\_\{j\}ifj∈Ij\\in I, and\(x⊕I\)j=xj\(x^\{\\oplus I\}\)\_\{j\}=x\_\{j\}otherwise\. We denote the family of nonempty coordinate subsets of size at mostkkbyℐ⩽k:=\{I⊆\[n\]:1⩽\|I\|⩽k\}\\mathcal\{I\}\_\{\\leqslant k\}:=\\\{I\\subseteq\[n\]:1\\leqslant\|I\|\\leqslant k\\\}\.

### 2\.2Boolean Product Distributions

In this work, we studyBoolean product distributionson the binary hypercubeΠn=\{0,1\}n\\Pi\_\{n\}=\\\{0,1\\\}^\{n\}, parameterized by𝒑=\(p1,…,pn\)\\boldsymbol\{p\}=\(p\_\{1\},\\ldots,p\_\{n\}\)\. This model is the product ofnnindependent Bernoulli distributions666A Bernoulli distribution with parameterp∈\[0,1\]p\\in\[0,1\]assigns probabilitypx​\(1−p\)1−xp^\{x\}\(1\-p\)^\{1\-x\}tox∈\{0,1\}x\\in\\\{0,1\\\}\.,ℬ​\(p1\)⊗⋯⊗ℬ​\(pn\)\\mathcal\{B\}\(p\_\{1\}\)\\otimes\\cdots\\otimes\\mathcal\{B\}\(p\_\{n\}\), and can be written as the following exponential family:

𝐏𝐫μ𝒛​\(𝒙\)=exp⁡\(𝒙⊤​𝒛\)∏i∈\[n\]\(1\+exp⁡\(zi\)\),\\mathbf\{Pr\}\_\{\\mu\_\{\\boldsymbol\{z\}\}\}\(\{\\boldsymbol\{x\}\}\)=\\frac\{\\exp\(\{\\boldsymbol\{x\}\}^\{\\top\}\\boldsymbol\{z\}\)\}\{\\prod\_\{i\\in\[n\]\}\(1\+\\exp\(z\_\{i\}\)\)\},where𝒛=\(z1,…,zn\)\\boldsymbol\{z\}=\(z\_\{1\},\\ldots,z\_\{n\}\)is the natural parameter vector of the model, withzi=log⁡\(pi/\(1−pi\)\)z\_\{i\}=\\log\(p\_\{i\}/\(1\-p\_\{i\}\)\)\. Moreover,σ​\(𝒛\)=𝒑\\sigma\(\\boldsymbol\{z\}\)=\\boldsymbol\{p\}, whereσ​\(x\)=1/\(1\+exp⁡\(−x\)\)\\sigma\(x\)=1/\(1\+\\exp\(\-x\)\)is the sigmoid function\. Given a subsetS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}of the Boolean hypercube, the mass thatμ𝒛\\mu\_\{\\boldsymbol\{z\}\}assigns toSSisμ𝒛​\(S\)=∑𝒙∈Sμ𝒛​\(𝒙\)\\mu\_\{\\boldsymbol\{z\}\}\(S\)=\\sum\_\{\{\\boldsymbol\{x\}\}\\in S\}\\mu\_\{\\boldsymbol\{z\}\}\(\{\\boldsymbol\{x\}\}\)\. Throughout this work, we refer to the Boolean product distribution interchangeably asμ𝒑\\mu\_\{\\boldsymbol\{p\}\},μ𝒛\\mu\_\{\\boldsymbol\{z\}\}andμ\\mu, depending on whether the probability parameter𝒑\\boldsymbol\{p\}or the natural parameter𝒛\\boldsymbol\{z\}is the focus or understood by context\.

Given a Boolean product distributionμ𝒛\\mu\_\{\\boldsymbol\{z\}\}and a setS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}withμ𝒛​\(S\)\>0\\mu\_\{\\boldsymbol\{z\}\}\(S\)\>0, we define thetruncatedBoolean product distribution by

μ𝒛∣S​\(𝒙\):=μ𝒛​\(𝒙\)​𝟏​\{𝒙∈S\}μ𝒛​\(S\)\.\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}\):=\\frac\{\\mu\_\{\\boldsymbol\{z\}\}\(\{\\boldsymbol\{x\}\}\)\\mathbf\{1\}\\\{\{\\boldsymbol\{x\}\}\\in S\\\}\}\{\\mu\_\{\\boldsymbol\{z\}\}\(S\)\}\.We refer toSSas thetruncation set\. We say thatμ𝒛\\mu\_\{\\boldsymbol\{z\}\}isidentifiablefromμ𝒛∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}if the map𝒛↦μ𝒛∣S\\boldsymbol\{z\}\\mapsto\\mu\_\{\\boldsymbol\{z\}\\mid S\}is injective\. Likewise,μ𝒛\\mu\_\{\\boldsymbol\{z\}\}isefficiently learnablefromμ𝒛∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}if there is an algorithm which, using samples only fromμ𝒛∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, returns an estimate𝒛^\\hat\{\\boldsymbol\{z\}\}satisfying‖𝒛−𝒛^‖2⩽ϵ\\\|\\boldsymbol\{z\}\-\\hat\{\\boldsymbol\{z\}\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta, in time and sample complexity polynomial innn,1/ϵ1/\\epsilon, andlog⁡\(1/δ\)\\log\(1/\\delta\)\.

### 2\.3Distances between Distributions

Let𝒫,𝒬\\mathcal\{P\},\\mathcal\{Q\}be probability measures over a discrete probability space\(Ω,ℱ\)\(\\Omega,\\mathcal\{F\}\)\. Two quantities of interest are thetotal variation distance,

DTV​\(𝒫,𝒬\):=12​∑𝒙∈Ω\|𝒫​\(𝒙\)−𝒬​\(𝒙\)\|,D\_\{\\mathrm\{TV\}\}\(\\mathcal\{P\},\\mathcal\{Q\}\):=\\frac\{1\}\{2\}\\sum\_\{\{\\boldsymbol\{x\}\}\\in\\Omega\}\|\\mathcal\{P\}\(\{\\boldsymbol\{x\}\}\)\-\\mathcal\{Q\}\(\{\\boldsymbol\{x\}\}\)\|,and theKullback–Leibler divergence,

DKL​\(𝒫∥𝒬\):=𝔼𝒙∼𝒫​\[log⁡𝒫​\(𝒙\)𝒬​\(𝒙\)\]\.D\_\{\\mathrm\{KL\}\}\(\\mathcal\{P\}\\\|\\mathcal\{Q\}\):=\\mathbb\{E\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mathcal\{P\}\}\\left\[\\log\\frac\{\\mathcal\{P\}\(\{\\boldsymbol\{x\}\}\)\}\{\\mathcal\{Q\}\(\{\\boldsymbol\{x\}\}\)\}\\right\]\.For Boolean product distributions, both quantities can be controlled directly through the natural parameters\.

###### Proposition 2\.1\.

Letμ𝐳\\mu\_\{\\boldsymbol\{z\}\}andμ𝐳′\\mu\_\{\\boldsymbol\{z\}^\{\\prime\}\}be two Boolean product distributions with natural parameters𝐳\\boldsymbol\{z\}and𝐳′\\boldsymbol\{z\}^\{\\prime\}, respectively\. Then

- •DKL​\(μ𝒛∥μ𝒛′\)⩽18​‖𝒛−𝒛′‖22D\_\{\\mathrm\{KL\}\}\(\\mu\_\{\\boldsymbol\{z\}\}\\\|\\mu\_\{\\boldsymbol\{z\}^\{\\prime\}\}\)\\leqslant\\frac\{1\}\{8\}\\\|\\boldsymbol\{z\}\-\\boldsymbol\{z\}^\{\\prime\}\\\|\_\{2\}^\{2\}\.
- •DTV​\(μ𝒛,μ𝒛′\)⩽14​‖𝒛−𝒛′‖2D\_\{\\mathrm\{TV\}\}\(\\mu\_\{\\boldsymbol\{z\}\},\\mu\_\{\\boldsymbol\{z\}^\{\\prime\}\}\)\\leqslant\\frac\{1\}\{4\}\\\|\\boldsymbol\{z\}\-\\boldsymbol\{z\}^\{\\prime\}\\\|\_\{2\}\.

###### Proof\.

The log\-partition function of the product family isA​\(𝒛\)=∑i=1nlog⁡\(1\+ezi\)A\(\\boldsymbol\{z\}\)=\\sum\_\{i=1\}^\{n\}\\log\(1\+e^\{z\_\{i\}\}\), and

∇2A​\(𝒛\)=diag⁡\(σ​\(zi\)​\(1−σ​\(zi\)\):i∈\[n\]\)⪯14​In\.\\nabla^\{2\}A\(\\boldsymbol\{z\}\)=\\operatorname\{diag\}\\bigl\(\\sigma\(z\_\{i\}\)\(1\-\\sigma\(z\_\{i\}\)\):i\\in\[n\]\\bigr\)\\preceq\\frac\{1\}\{4\}I\_\{n\}\.The KL divergence is the Bregman divergenceA​\(𝒛′\)−A​\(𝒛\)−⟨∇A​\(𝒛\),𝒛′−𝒛⟩A\(\\boldsymbol\{z\}^\{\\prime\}\)\-A\(\\boldsymbol\{z\}\)\-\\langle\\nabla A\(\\boldsymbol\{z\}\),\\boldsymbol\{z\}^\{\\prime\}\-\\boldsymbol\{z\}\\rangle\. Taylor’s theorem therefore gives the first claim\. The second follows from Pinsker’s inequality,DTV​\(𝒫,𝒬\)⩽DKL​\(𝒫∥𝒬\)/2D\_\{\\mathrm\{TV\}\}\(\\mathcal\{P\},\\mathcal\{Q\}\)\\leqslant\\sqrt\{D\_\{\\mathrm\{KL\}\}\(\\mathcal\{P\}\\\|\\mathcal\{Q\}\)/2\}\. ∎

## 3Boolean Product Distributions Truncated byγ\\gamma\-Fat Sets

As a warm\-up to the techniques we introduce for learning truncated Boolean product distributions, we study how the notion offatnessintroduced by\(fotakis2021efficient\)can guarantee efficient parameter estimation\. We give the formal definition as follows\.

###### Assumption 3\.1\(Fatness\)\.

A truncated distributionμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}isγ\\gamma\-fat in coordinateiiif

𝐏𝐫𝒙∼μ𝒛∣S​\(𝒙⊕i∈S\)⩾γ\.\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\(\{\\boldsymbol\{x\}\}^\{\\oplus i\}\\in S\)\\geqslant\\gamma\.We call a distributionμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}γ\\gamma\-fat if it isγ\\gamma\-fat in every coordinate\.

Remark:Ifμ𝒛∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}is fat in coordinateii, then both\(𝒙−i,0\)\(\{\\boldsymbol\{x\}\}\_\{\-i\},0\)and\(𝒙−i,1\)\(\{\\boldsymbol\{x\}\}\_\{\-i\},1\)lie in the truncation setSSwith nontrivial probability\. This notion is already quite general and includes halfspacesS⩽k=\{𝒙∈\{0,1\}n:∑i=1nxi⩽k\}S\_\{\\leqslant k\}=\\\{\{\\boldsymbol\{x\}\}\\in\\\{0,1\\\}^\{n\}:\\sum\_\{i=1\}^\{n\}x\_\{i\}\\leqslant k\\\}anddownward\-closedsets, among others\.

We give efficient parameter estimation algorithms for𝒛\\boldsymbol\{z\}and𝒑\\boldsymbol\{p\}under this assumption\.

###### Theorem 3\.1\(Learningμ\\muin Relative Error\)\.

Let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be independent random variables drawn from aγ\\gamma\-fat distributionμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, where‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. For everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\), if

N⩾C​n​e2​Rγ​ϵ2​log⁡\(2​nδ\)N\\geqslant C\\frac\{ne^\{2R\}\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\)for a universal constantC\>0C\>0, then there is an algorithm that returns an estimate𝐳^\\hat\{\\boldsymbol\{z\}\}satisfying‖𝐳−𝐳^‖2⩽ϵ\\\|\\boldsymbol\{z\}\-\\hat\{\\boldsymbol\{z\}\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

The relationship between natural\-parameter error and distributional distance yields the following corollary for learning in total variation distance\.

###### Corollary 3\.1\(Learningμ\\muin Total Variation Distance\)\.

Under the assumptions of Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1), there is a universal constantC\>0C\>0such that

N⩾C​n​e2​Rγ​ϵ2​log⁡\(2​nδ\)N\\geqslant C\\frac\{ne^\{2R\}\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\)samples suffice to return a Boolean product distributionμ^\\hat\{\\mu\}satisfyingDTV​\(μ𝐳,μ^\)⩽ϵD\_\{\\mathrm\{TV\}\}\(\\mu\_\{\\boldsymbol\{z\}\},\\hat\{\\mu\}\)\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

###### Proof\.

Forϵ⩽1/4\\epsilon\\leqslant 1/4, apply Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1)with target natural\-parameter error4​ϵ4\\epsilonand setμ^:=μ𝒛^\\hat\{\\mu\}:=\\mu\_\{\\hat\{\\boldsymbol\{z\}\}\}\. The proposition in Section 2 gives

DTV​\(μ𝒛,μ^\)⩽14​‖𝒛−𝒛^‖2⩽ϵ\.D\_\{\\mathrm\{TV\}\}\(\\mu\_\{\\boldsymbol\{z\}\},\\hat\{\\mu\}\)\\leqslant\\frac\{1\}\{4\}\\\|\\boldsymbol\{z\}\-\\hat\{\\boldsymbol\{z\}\}\\\|\_\{2\}\\leqslant\\epsilon\.Absorbing the numerical factor intoCCgives the stated sample bound\. Forϵ\>1/4\\epsilon\>1/4, run Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1)with natural\-parameter target error1/21/2; this yields TV error at most1/8<ϵ1/8<\\epsilon, and the stated sample bound follows after increasingCC\. ∎

Lastly, we give estimation results for learning the underlying probabilities𝒑\\boldsymbol\{p\}; note that the sample complexity depends only onϵ\\epsilonand the fatness of the distribution\.

###### Theorem 3\.2\(Learningμ\\muin Absolute Error\)\.

Let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be independent random variables drawn from aγ\\gamma\-fat distributionμ𝐩∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}\. For everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\), there is an algorithm returning𝐩^∈\[0,1\]n\\hat\{\\boldsymbol\{p\}\}\\in\[0,1\]^\{n\}such that‖𝐩−𝐩^‖2⩽ϵ\\\|\\boldsymbol\{p\}\-\\hat\{\\boldsymbol\{p\}\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta, provided

N⩾C​nγ​ϵ2​log⁡\(2​nδ\)\.N\\geqslant C\\frac\{n\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\)\.Moreover, the same algorithm satisfies‖𝐩−𝐩^‖∞⩽ϵ\\\|\\boldsymbol\{p\}\-\\hat\{\\boldsymbol\{p\}\}\\\|\_\{\\infty\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta, provided

N⩾C​1γ​ϵ2​log⁡\(2​nδ\)\.N\\geqslant C\\frac\{1\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\)\.

We next give a brief overview of the algorithms used to find these estimators and the theoretical analysis underpinning their success, deferring additional details to the appendix\.

### 3\.1Learningμ\\muin Relative Error

In order to learn the underlying natural parameter𝒛\\boldsymbol\{z\}, we utilize a one\-dimensional version of the logistic regression framework introduced byWuet al\.\([2019](https://arxiv.org/html/2607.22889#bib.bib20)\)\. For each coordinateii, let

𝒥i:=\{j∈\[N\]:\(𝒙\(j\)\)⊕i∈S\},Mi:=\|𝒥i\|,yi\(j\):=2​xi\(j\)−1\.\\mathcal\{J\}\_\{i\}:=\\\{j\\in\[N\]:\(\{\\boldsymbol\{x\}\}^\{\(j\)\}\)^\{\\oplus i\}\\in S\\\},\\qquad M\_\{i\}:=\|\\mathcal\{J\}\_\{i\}\|,\\qquad y\_\{i\}^\{\(j\)\}:=2x\_\{i\}^\{\(j\)\}\-1\.WhenMi\>0M\_\{i\}\>0, the estimator minimizes the conditional empirical loss

z^i∈arg​minw∈\[−R,R\]⁡ℒ^i​\(w\),ℒ^i​\(w\):=1Mi​∑j∈𝒥ilog⁡\(1\+exp⁡\(−yi\(j\)​w\)\)\.\\hat\{z\}\_\{i\}\\in\\operatorname\*\{arg\\,min\}\_\{w\\in\[\-R,R\]\}\\widehat\{\\mathcal\{L\}\}\_\{i\}\(w\),\\qquad\\widehat\{\\mathcal\{L\}\}\_\{i\}\(w\):=\\frac\{1\}\{M\_\{i\}\}\\sum\_\{j\\in\\mathcal\{J\}\_\{i\}\}\\log\\left\(1\+\\exp\(\-y\_\{i\}^\{\(j\)\}w\)\\right\)\.Conditional on a sample being flippable in coordinateii, its signed coordinateyiy\_\{i\}has logistic natural parameterziz\_\{i\}\. Hence the corresponding population loss is minimized atziz\_\{i\}\.

To demonstrate that the minimizer of the empirical loss is close to the population minimizer, we show two key facts for alli∈\[n\]i\\in\[n\]:

- •Conditional on flippability,minw∈\[−R,R\]​∇2ℒi​\(w\)⩾Ω​\(e−R\)\\min\_\{w\\in\[\-R,R\]\}\\nabla^\{2\}\\mathcal\{L\}\_\{i\}\(w\)\\geqslant\\Omega\(e^\{\-R\}\); the factorγ\\gammadoes not enter this conditional curvature\.
- •A Chernoff bound givesMi⩾γ​N/2M\_\{i\}\\geqslant\\gamma N/2, and conditional on this event Hoeffding’s inequality ensures∇ℒ^i​\(zi−ϵ\)<0<∇ℒ^i​\(zi\+ϵ\)\\nabla\\widehat\{\\mathcal\{L\}\}\_\{i\}\(z\_\{i\}\-\\epsilon\)<0<\\nabla\\widehat\{\\mathcal\{L\}\}\_\{i\}\(z\_\{i\}\+\\epsilon\)whenever the displayed endpoints lie in\[−R,R\]\[\-R,R\]\.

Strong convexity provides a gradient signal of ordere−R​ϵe^\{\-R\}\\epsilonat distanceϵ\\epsilonfrom the true parameter\. Concentration on the flippable subsample then shows that the empirical minimizer lies withinϵ\\epsilonofziz\_\{i\}\. Since the flippable subsample has orderγ​N\\gamma Nobservations, the resulting dependence is1/γ1/\\gamma, rather than1/γ21/\\gamma^\{2\}\.

To find𝒛^\\hat\{\\boldsymbol\{z\}\}, the algorithm estimates each coordinateziz\_\{i\}independently by using only samples flippable in coordinateii, minimizing the resulting one\-dimensional convex empirical logistic loss via bisection on its derivative, and returning the coordinate\-wise minimizers\.

### 3\.2Learningμ\\muin Absolute Error

To learn the probabilities𝒑\\boldsymbol\{p\}of the underlying model, wesimplytake the sample average of each coordinate over all samples that have that index flippable\. On such samples, both values of theii\-th coordinate are feasible while the other coordinates are fixed, so the conditional distribution ofxix\_\{i\}is still Bernoulli with parameterpip\_\{i\}, and the empirical average ofxix\_\{i\}is an unbiased estimator ofpip\_\{i\}\. Repeating this procedure independently for each coordinate gives an estimate𝒑^=\(p^1,…,p^n\)\\hat\{\\boldsymbol\{p\}\}=\(\\hat\{p\}\_\{1\},\\dots,\\hat\{p\}\_\{n\}\)\. The fatness assumption ensures that each coordinate has sufficiently many flippable samples\.

## 4Estimation Beyond Fatness

Our primary idea for learning guarantees that do not rely on the survival mass of the underlying domain is to extend fatness from single\-coordinate flips to multi\-bit flips\. In this sense, the generalized notion of fatness measures internal connectivity with respect toSSunder the measureμ𝒛∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}\. For estimation, we consider feasible moves along subsets of coordinates and learn linear forms of the natural parameter vector\. Specifically, for vectors𝒘∈\{−1,0,1\}n\\boldsymbol\{w\}\\in\\\{\-1,0,1\\\}^\{n\}with sparse supportI=supp⁡\(𝒘\)I=\\operatorname\{supp\}\(\\boldsymbol\{w\}\), we aim to estimate quantities of the form𝒘⊤​𝒛\\boldsymbol\{w\}^\{\\top\}\\boldsymbol\{z\}\. The conditionInfIμ<1\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\}<1asserts that the truncation set has nontrivial internal variation along the coordinates inII, implying that the conditional distribution of𝒘I⊤​𝒙I\\boldsymbol\{w\}\_\{I\}^\{\\top\}\{\\boldsymbol\{x\}\}\_\{I\}given𝒙−I\{\\boldsymbol\{x\}\}\_\{\-I\}yields information about the corresponding linear form\. If we collect such estimates for a family of directions𝒘1,…,𝒘m\\boldsymbol\{w\}\_\{1\},\\dots,\\boldsymbol\{w\}\_\{m\}, and denoteyℓ=𝒘ℓ⊤​𝒛y\_\{\\ell\}=\\boldsymbol\{w\}\_\{\\ell\}^\{\\top\}\\boldsymbol\{z\}forℓ=1,…,m\\ell=1,\\dots,m, then the problem reduces to recovering𝒛\\boldsymbol\{z\}from an approximately observed linear system𝒚=W​𝒛\\boldsymbol\{y\}=W\\boldsymbol\{z\}, whereW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}has rows𝒘ℓ⊤\\boldsymbol\{w\}\_\{\\ell\}^\{\\top\}\. IfWWis well conditioned onℝn\\mathbb\{R\}^\{n\}, then accurate estimatesy^ℓ\\widehat\{y\}\_\{\\ell\}of the linear forms yield an accurate estimate of𝒛\\boldsymbol\{z\}by solving the inverse problem\. For example, whenm=nm=nandWWis invertible, one may take𝒛^=W−1​𝒚^\\widehat\{\\boldsymbol\{z\}\}=W^\{\-1\}\\widehat\{\\boldsymbol\{y\}\}, and the resulting parameter error is controlled by the conditioning ofWW\. With this framework in mind, we now demonstrate structural conditions on the influences\{InfIμ𝒛∣S\}I⊆\[n\]\\\{\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\\}\_\{I\\subseteq\[n\]\}and the underlying setSSthat provide estimation guarantees\.

The first step is to guarantee the existence of local two\-point conditional distributions which can be reliably estimated by probing minimal feasible flips\. For a nonemptyI⊆\[n\]I\\subseteq\[n\], define

BI:=\{𝒙⊕I∈S​and​𝒙⊕J∉S​for every​∅≠J⊊I\}\.B\_\{I\}:=\\left\\\{\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S\\text\{ and \}\{\\boldsymbol\{x\}\}^\{\\oplus J\}\\notin S\\text\{ for every \}\\varnothing\\neq J\\subsetneq I\\right\\\}\.OnBIB\_\{I\}, the only feasible configurations obtained by flipping a subset ofIIare𝒙\{\\boldsymbol\{x\}\}and𝒙⊕I\{\\boldsymbol\{x\}\}^\{\\oplus I\}\. Thus, after conditioning on the coordinates outsideII, these two orientations form a Bernoulli experiment\. The following condition ensures that this minimal\-flip event has probability at leastγ\\gamma\.

###### Assumption 4\.1\(Bounded Influences\)\.

Letℱ⊆\{I⊆\[n\]:1⩽\|I\|⩽k\}\\mathcal\{F\}\\subseteq\\\{I\\subseteq\[n\]:1\\leqslant\|I\|\\leqslant k\\\}\. We assume there existsγ\>0\\gamma\>0such that, for everyI∈ℱI\\in\\mathcal\{F\},

InfIμ𝒛∣S⩽1−2​γ,InfJμ𝒛∣S⩾1−γ2\|I\|−2∀∅≠J⊊I,\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\leqslant 1\-2\\gamma,\\qquad\\textrm\{Inf\}\_\{J\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\geqslant 1\-\\frac\{\\gamma\}\{2^\{\|I\|\}\-2\}\\quad\\forall\\emptyset\\neq J\\subsetneq I,where the second condition is vacuous when\|I\|=1\|I\|=1\.

ForI∈ℱI\\in\\mathcal\{F\}andt∈\{±1\}It\\in\\\{\\pm 1\\\}^\{I\}, define the joint one\-sided mass

mI​\(t\):=𝐏𝐫​\(BI,𝒔I​\(𝒙\)=t\)\.m\_\{I\}\(t\):=\\mathbf\{Pr\}\(B\_\{I\},\\ \\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=t\)\.ChoosetIt\_\{I\}maximizingmI​\(t\)m\_\{I\}\(t\), and letsIs\_\{I\}be the canonical representative of the antipodal pair\{tI,−tI\}\\\{t\_\{I\},\-t\_\{I\}\\\}, with\(sI\)min⁡I=\+1\(s\_\{I\}\)\_\{\\min I\}=\+1\. ExtendsIs\_\{I\}by zero outsideIIto obtain𝒘I∈\{0,±1\}n\\boldsymbol\{w\}\_\{I\}\\in\\\{0,\\pm 1\\\}^\{n\}\. The choice betweensIs\_\{I\}and−sI\-s\_\{I\}is immaterial below because only𝒘I​𝒘I⊤\\boldsymbol\{w\}\_\{I\}\\boldsymbol\{w\}\_\{I\}^\{\\top\}appears\.

We next require that these signed directions contain enough geometric information to recover the full parameter vector𝒛\\boldsymbol\{z\}\. Without such a condition, the accessible linear forms may fail to identify certain coordinates; for example, the available measurements may reveal onlyzi\+zjz\_\{i\}\+z\_\{j\}, rather than the two coordinates separately\. Even when identifiability holds, recovery may be unstable if the signed design matrix is poorly conditioned\.

###### Assumption 4\.2\(Flip Directions\)\.

There is a parameterλs\>0\\lambda\_\{s\}\>0such that, for everyv∈ℝnv\\in\\mathbb\{R\}^\{n\},

1\|ℱ\|​∑I∈ℱ⟨𝒘I,v⟩2⩾λs​‖v‖22\.\\frac\{1\}\{\|\\mathcal\{F\}\|\}\\sum\_\{I\\in\\mathcal\{F\}\}\\langle\\boldsymbol\{w\}\_\{I\},v\\rangle^\{2\}\\geqslant\\lambda\_\{s\}\\\|v\\\|\_\{2\}^\{2\}\.

The quantityλs\\lambda\_\{s\}measures the least visible direction of𝒛\\boldsymbol\{z\}under the available linear forms, a control over the sample complexity required to solve the inverse problem\.

###### Theorem 4\.1\.

Fixkk, and let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be independent random variables drawn fromμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, whereμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}satisfies Assumptions[4\.1](https://arxiv.org/html/2607.22889#S4.Thmassumption1)and[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2), and‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. There is a universal constantC\>0C\>0such that, for everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\), if

N⩾C​2k​e2​k​Rγ​λs​ϵ2​\(k​log⁡\(2​n\)\+log⁡4​kδ\),N\\geqslant C\\frac\{2^\{k\}e^\{2kR\}\}\{\\gamma\\lambda\_\{s\}\\epsilon^\{2\}\}\\left\(k\\log\(2n\)\+\\log\\frac\{4k\}\{\\delta\}\\right\),then a polynomial\-time algorithm returns an estimate𝐳^\\widehat\{\\boldsymbol\{z\}\}satisfying‖𝐳^−𝐳‖2⩽ϵ\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

Remark:The support\-estimation step enumerates all nonemptyI⊆\[n\]I\\subseteq\[n\]with\|I\|⩽k\|I\|\\leqslant k, and therefore for constantkkits runtime isnO​\(k\)n^\{O\(k\)\}, up to the cost of membership queries and logarithmic factors\. The remaining steps are polynomial provided the relevant conditioning parameters are not too small\. In particular, ifγ⩾1/poly⁡\(n\)\\gamma\\geqslant 1/\\operatorname\{poly\}\(n\)andλs⩾1/poly⁡\(n\)\\lambda\_\{s\}\\geqslant 1/\\operatorname\{poly\}\(n\), then the sample complexity and runtime are polynomial innn,1/ϵ1/\\epsilon, andlog⁡\(1/δ\)\\log\(1/\\delta\)for constantkkandR=O​\(1\)R=O\(1\)\. Since each signed row satisfies‖𝒘I‖22=\|I\|⩽k\\\|\\boldsymbol\{w\}\_\{I\}\\\|\_\{2\}^\{2\}=\|I\|\\leqslant k, the population signed Gram matrix has trace at mostkk, and hence average eigenvalue at mostk/nk/n\. Thus the assumptionλs⩾1/poly⁡\(n\)\\lambda\_\{s\}\\geqslant 1/\\operatorname\{poly\}\(n\)is the standard polynomial\-conditioning requirement for the inverse problem\. We further note that the exponential dependence onkkarises from searching over and estimating signed flips of size at mostkk, and we show in the next section that this dependence is endemic through a corresponding lower bound\.

### 4\.1Proof Sketch

Before describing the proof, we make precise which signed directions are learned\. For every nonemptyI⊆\[n\]I\\subseteq\[n\]with\|I\|⩽k\|I\|\\leqslant k, we pair each sign patterns∈\{±1\}Is\\in\\\{\\pm 1\\\}^\{I\}with its antipode−s\-sand keep one canonical representative\. We write𝒘I,s∈\{0,±1\}n\\boldsymbol\{w\}\_\{I,s\}\\in\\\{0,\\pm 1\\\}^\{n\}for the extension ofssby zero outsideII\. A sample contributes to the pair\(I,s\)\(I,s\)when its signed coordinates onIIhave orientationssor−s\-s, the fullII\-flip remains inSS, and every proper nonempty subflip leavesSS\. We denote this paired event byEI,sE\_\{I,s\}and its probability bypI,sp\_\{I,s\}\.

The bounded\-influence assumption guarantees that the minimal\-flip event for everyI∈ℱI\\in\\mathcal\{F\}has probability at leastγ\\gamma\. Pairing antipodal sign patterns and applying the pigeonhole principle shows that the selected pair\(I,sI\)\(I,s\_\{I\}\)has mass at leastγ/2\|I\|⩾γ/2k\\gamma/2^\{\|I\|\}\\geqslant\\gamma/2^\{k\}\. The flip\-direction assumption then says that these selected signed vectors collectively see every direction in parameter space\. Equivalently, there is a well\-conditioned distribution over sufficiently frequent candidate pairs\. This distribution is used only in the analysis; the learner does not need to know it\.

The proof is organized around two main lemmas\.

- •Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1)shows that the learner finds all informative signed directions and estimates their corresponding linear forms uniformly well\.
- •Lemma[C\.3](https://arxiv.org/html/2607.22889#A3.Thmlemma3)shows that these estimated directions form a sufficiently well\-conditioned linear system and that weighted least squares stably recovers𝒛\\boldsymbol\{z\}\.

For the first lemma, the learner enumerates the candidate pairs, estimates the masspI,sp\_\{I,s\}of each paired event, and retains those whose empirical mass exceeds the threshold used in Appendix C\. The threshold has two roles: it keeps every pair from the hidden well\-conditioned family and discards pairs whose true mass is too small to estimate reliably\. Conditional on a retained paired event, flipping all coordinates inIIexchanges the two orientationsssand−s\-s\. Their density ratio depends only on the signed linear formyI,s:=⟨𝒘I,s,𝒛⟩y\_\{I,s\}:=\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\. In particular, ifAArecords the observed orientation, then

𝐏𝐫​\(A=a\)=ea​yI,s/22​cosh⁡\(yI,s/2\),a∈\{±1\}\.\\mathbf\{Pr\}\(A=a\)=\\frac\{e^\{ay\_\{I,s\}/2\}\}\{2\\cosh\(y\_\{I,s\}/2\)\},\\qquad a\\in\\\{\\pm 1\\\}\.Thus every retained direction gives a one\-dimensional logistic estimation problem\. A Chernoff bound supplies enough observations from each retained event, and the curvature of this logistic loss gives a uniform estimate of all retained linear forms\. A union bound over the at mostk​\(2​n\)kk\(2n\)^\{k\}candidate pairs produces the first main lemma\.

For the second lemma, observe that once all pairs in the hidden well\-conditioned family have been retained, their population weights give a feasible design over the observed directions\. The learner finds such weights by a semidefinite feasibility problem and then performs weighted least squares on the estimated linear forms\. The Gram lower bound prevents errors in the individual linear forms from being amplified in poorly observed directions\. The deterministic stability argument in Appendix C yields

‖𝒛^−𝒛‖2⩽η​2λs,\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\},whereη\\etais the uniform error in the estimated linear forms\.

Finally, takingη=ϵ​λs/2\\eta=\\epsilon\\sqrt\{\\lambda\_\{s\}/2\}and using the lower boundγ/2k\\gamma/2^\{k\}on the mass of each informative pair gives the sample complexity in Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1)\. For constantkk, enumerating candidate pairs, solving the one\-dimensional logistic problems, finding the design weights, and performing weighted least squares all take polynomial time\.

## 5Lower Bound on the Sample Complexity of Estimation under Truncation

In this section, we prove that the sample complexity of estimating truncated Boolean product distributions depends exponentially on thelocal connectivityof the space, namely, the average number of neighbors of a sampled point\.

###### Theorem 5\.1\(Sample Complexity Lower Bound\)\.

Fix integersn,kn,ksuch that2​k∣n2k\\mid n, and letR\>0R\>0and0<ϵ⩽R​n/160<\\epsilon\\leqslant R\\sqrt\{n\}/16\. There is a truncation setS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}whose distinct elements have Hamming distance at leastkksuch that the following holds\. Any estimator which, for every𝐳\\boldsymbol\{z\}in the constructed family with‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R, satisfies‖𝐳^−𝐳‖2⩽ϵ\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least0\.990\.99requires

N⩾c​n​exp⁡\(k​R/2\)k2​ϵ2N\\geqslant c\\frac\{n\\exp\(kR/2\)\}\{k^\{2\}\\epsilon^\{2\}\}samples, wherec\>0c\>0is a universal constant\.

Remark:The lower bound demonstrates the intrinsic hardness of this construction is governed by the productk​RkR: the block separation parameterkkcontrols how many coordinates must change to move between admissible states, while the parameter boundRRcontrols how strongly the distribution can concentrate on any given state\. Together, they produce an exponentially small probability of observing informative alternative block states, of orderexp⁡\(−Θ​\(k​R\)\)\\exp\(\-\\Theta\(kR\)\), and hence anexp⁡\(Θ​\(k​R\)\)\\exp\(\\Theta\(kR\)\)contribution to the sample complexity\. In particular, ifk​R∈Θ​\(log⁡n\)kR\\in\\Theta\(\\log n\), then this exponential factor is only polynomial innn, so the lower bound remains polynomial\.

### 5\.1Construction of the AdversarialSS

We construct the truncation setSSby first defining a small, highly separated set of admissible configurations inside each block\. Assume for simplicity that2​k∣n2k\\mid n, and partition the coordinates\[n\]\[n\]intoB=n/\(2​k\)B=n/\(2k\)disjoint blocksB1,…,BBB\_\{1\},\\dots,B\_\{B\}, each of size2​k2k\. Within a single block, let

V:=\{𝟎2​k,𝟏2​k,\(𝟎k,𝟏k\),\(𝟏k,𝟎k\)\}⊆\{0,1\}2​k\.V:=\\left\\\{\\mathbf\{0\}^\{2k\},\\mathbf\{1\}^\{2k\},\(\\mathbf\{0\}^\{k\},\\mathbf\{1\}^\{k\}\),\(\\mathbf\{1\}^\{k\},\\mathbf\{0\}^\{k\}\)\\right\\\}\\subseteq\\\{0,1\\\}^\{2k\}\.Every two distinct elements ofVVhave Hamming distance eitherkkor2​k2k\. The full truncation set is the Cartesian productS:=VBS:=V^\{B\}\. Equivalently, a vectorx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}lies inSSif and only if, after decomposing it into blocksx=\(xB1,…,xBB\)x=\(x\_\{B\_\{1\}\},\\dots,x\_\{B\_\{B\}\}\), every block belongs toVV\. This product structure makes the conditional distribution onSSfactor into the corresponding blockwise conditional laws onVV\. Moreover the Hamming separation insideVVimplies that no single\-bit flip, and more generally no small Hamming perturbation of radius less thankk, can move between distinct admissible states in the same block\.

## Conclusion and Future Work

In this paper, we present a novel framework for parameter estimation in truncated Boolean product distributions beyond assumptions on the survival mass of the domain or stringent local\-connectivity assumptions\. We give algorithms with improved sample complexities for learning underfatnessand extend this notion using influence to provide efficient guarantees beyond bounded width\.

The present work opens the door to important future questions: \(i\) What is the precise relationship between the influence and the Fisher information matrix used in the anti\-concentration condition offotakis2022efficientparameterestimationtruncated? \(ii\) As our framework does not require sampling from arbitrary parameterizations of the underlying model, do our techniques transfer to more complex discrete distributions where sampling is known to be difficult? \(iii\) Lastly, is it possible to learn truncated Boolean product distributions when the truncation set is unknown but lies in a class with sufficiently low influences?

## References

- \[1\]B\. B\. Bhattacharya and K\. Ramanan\(2021\)Parameter estimation for undirected graphical models with hard constraints\.External Links:2008\.09925,[Link](https://arxiv.org/abs/2008.09925)Cited by:[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p2.1)\.
- \[2\]S\. P\. Boyd and L\. Vandenberghe\(2004\)Convex optimization\.Cambridge University Press,Cambridge, UK\.Cited by:[§B\.1\.2](https://arxiv.org/html/2607.22889#A2.SS1.SSS2.p2.13)\.
- \[3\]J\. Gaitonde, A\. Moitra, and E\. Mossel\(2024\)Bypassing the noisy parity barrier: learning higher\-order markov random fields from dynamics\.External Links:2409\.05284,[Link](https://arxiv.org/abs/2409.05284)Cited by:[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p2.1)\.
- \[4\]A\. Galanis, A\. Kalavasis, and A\. V\. Kandiros\(2024\)Learning hard\-constrained models with one sample\.InProceedings of the 2024 Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\),pp\. 3184–3196\.Cited by:[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p1.1),[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p2.1)\.
- \[5\]A\. Klivans and R\. Meka\(2017\)Learning graphical models using multiplicative weights\.External Links:1706\.06274,[Link](https://arxiv.org/abs/1706.06274)Cited by:[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p2.1)\.
- \[6\]S\. Wu, S\. Sanghavi, and A\. G\. Dimakis\(2019\)Sparse logistic regression learns all discrete pairwise graphical models\.External Links:1810\.11905,[Link](https://arxiv.org/abs/1810.11905)Cited by:[§1\.2](https://arxiv.org/html/2607.22889#S1.SS2.p2.1),[§3\.1](https://arxiv.org/html/2607.22889#S3.SS1.p1.2)\.

## Appendix AFurther Analysis of\[fotakis2022efficientparameterestimationtruncated\]

In this section, we discuss the assumptions of\[fotakis2022efficientparameterestimationtruncated\]in greater detail and explain how they relate to the width of the Boolean product distribution\. To review, the authors make the following anti\-concentration assumption on this measure\.

###### Assumption A\.1\(Assumptions 3 and 4 of\[fotakis2022efficientparameterestimationtruncated\]\)\.

Assume the following is true,

- •The mass of the truncation setμ𝒛​\(S\)⩾α∈Θ​\(1\)\\mu\_\{\\boldsymbol\{z\}\}\(S\)\\geqslant\\alpha\\in\\Theta\(1\)\.
- •There exists aλ∈Θ​\(1\)\\lambda\\in\\Theta\(1\)such that for all unit vectors𝒘∈ℝn\\boldsymbol\{w\}\\in\\mathbb\{R\}^\{n\},‖𝒘‖2=1\\\|\\boldsymbol\{w\}\\\|\_\{2\}=1, and allc∈ℝc\\in\\mathbb\{R\},𝐏𝐫𝒙∼μ𝒛∣S​\[𝒘⊤​𝒙∉\(c−λ,c\+λ\)\]⩾λ\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\[\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\\not\\in\(c\-\\lambda,c\+\\lambda\)\]\\geqslant\\lambda\.

This statement can be translated directly into a lower bound on the variance of linear forms under this measure\.

###### Lemma A\.1\.

Letμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}satisfy Assumption[A\.1](https://arxiv.org/html/2607.22889#A1.Thmassumption1)with parametersα,λ\\alpha,\\lambda\. It follows that for all𝐰∈ℝn\\boldsymbol\{w\}\\in\\mathbb\{R\}^\{n\}with‖𝐰‖2=1\\\|\\boldsymbol\{w\}\\\|\_\{2\}=1,𝐕𝐚𝐫​\(𝐰⊤​𝐱\)⩾λ3\\mathbf\{Var\}\(\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\)\\geqslant\\lambda^\{3\}\. Moreover, for alli∈\[n\]i\\in\[n\],𝐕𝐚𝐫​\(𝐱i\)⩾λ3\\mathbf\{Var\}\(\{\\boldsymbol\{x\}\}\_\{i\}\)\\geqslant\\lambda^\{3\}\.

###### Proof\.

Fix𝒘∈ℝn\\boldsymbol\{w\}\\in\\mathbb\{R\}^\{n\}with‖𝒘‖2=1\\\|\\boldsymbol\{w\}\\\|\_\{2\}=1, and setc=𝔼𝒙∼μ𝒛∣S​\[𝒘⊤​𝒙\]c=\\mathbb\{E\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\[\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\]\. The assumption, combined with Chebyshev’s inequality, implies that

λ⩽𝐏𝐫𝒙∼μ𝒛∣S​\[\|𝒘⊤​𝒙−𝔼𝒙∼μ𝒛∣S​\[𝒘⊤​𝒙\]\|⩾λ\]⩽𝐕𝐚𝐫​\(𝒘⊤​𝒙\)λ2\\lambda\\leqslant\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\[\|\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\-\\mathbb\{E\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\[\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\]\|\\geqslant\\lambda\]\\leqslant\\frac\{\\mathbf\{Var\}\(\\boldsymbol\{w\}^\{\\top\}\{\\boldsymbol\{x\}\}\)\}\{\\lambda^\{2\}\}Rearranging yields the desired result\. Next, taking𝒘=𝒆i\\boldsymbol\{w\}=\\boldsymbol\{e\}\_\{i\}, theii\-th standard basis vector inℝn\\mathbb\{R\}^\{n\}, gives𝐕𝐚𝐫​\(𝒙i\)⩾λ3\\mathbf\{Var\}\(\{\\boldsymbol\{x\}\}\_\{i\}\)\\geqslant\\lambda^\{3\}for everyi∈\[n\]i\\in\[n\]\. ∎

Recall further the relationship between the natural parameters𝒛\\boldsymbol\{z\}and the underlying probabilities of the model𝒑\\boldsymbol\{p\}\. Aszi=log⁡\(pi/\(1−pi\)\)z\_\{i\}=\\log\(p\_\{i\}/\(1\-p\_\{i\}\)\)it follows that if𝒑\\boldsymbol\{p\}is a constant with respect tonn, so is𝒛\\boldsymbol\{z\}, and if𝒑⩾1/𝗉𝗈𝗅𝗒​\(n\)\\boldsymbol\{p\}\\geqslant 1/\\mathsf\{poly\}\(n\)then‖𝒛‖∞∈𝒪​\(log⁡\(n\)\)\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\in\\mathcal\{O\}\(\\log\(n\)\)\.

We also recall their associated lower bound\.

###### Lemma A\.2\(Lemma 4\[fotakis2022efficientparameterestimationtruncated\]\)\.

Letμ𝐩\\mu\_\{\\boldsymbol\{p\}\}be a Boolean product distribution and letμ𝐩∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}be a truncation ofμ𝐩\\mu\_\{\\boldsymbol\{p\}\}\. Assume that the anti\-concentration parameterλ∗\\lambda^\{\*\}satisfies1/λ∗=ω​\(𝗉𝗈𝗅𝗒​\(n\)\)1/\\lambda^\{\*\}=\\omega\(\\mathsf\{poly\}\(n\)\)\. Then, computing an estimation𝐩^\\hat\{\\boldsymbol\{p\}\}of the parameter vector𝐩\\boldsymbol\{p\}ofμ𝐩\\mu\_\{\\boldsymbol\{p\}\}such that‖𝐩−𝐩^‖2⩽o​\(1\)\\\|\\boldsymbol\{p\}\-\\hat\{\\boldsymbol\{p\}\}\\\|\_\{2\}\\leqslant o\(1\)requires an expected number ofΩ​\(1/λ∗\)\\Omega\(1/\\lambda^\{\*\}\)samples fromμ𝐩∣S\\mu\_\{\\boldsymbol\{p\}\\mid S\}\.

We note that, given their approach, which uses projected gradient descent, it is infeasible to estimate beyond the barrier ofλ∈Θ​\(1\)\\lambda\\in\\Theta\(1\), as the strong convexity of the maximum likelihood objective in the ball around the parameters decays at a rate ofα𝗉𝗈𝗅𝗒​\(1/λ\)\\alpha^\{\\mathsf\{poly\}\(1/\\lambda\)\}\.

### A\.1Universality of Influence

We now give a short proof of the fact that, given any set whose affine span isℝn\\mathbb\{R\}^\{n\}, the influence sequence\{InfIμ𝒛∣S\}I⊆\[n\]\\\{\\textrm\{Inf\}\_\{I\}^\{\\,\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\\\}\_\{I\\subseteq\[n\]\}is nonempty, and the weighted matrix found in Assumption[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2)is positive definite\.

###### Lemma A\.3\.

LetS⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}satisfyaff⁡\(S\)=ℝn\\operatorname\{aff\}\(S\)=\\mathbb\{R\}^\{n\}, and assumeμ𝐳∣S​\(𝐱\)\>0\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}\)\>0for every𝐱∈S\{\\boldsymbol\{x\}\}\\in S\. For eachI⊆\[n\]I\\subseteq\[n\], defineαI:=𝐏𝐫𝐱∼μ𝐳∣S​\(𝐱⊕I∈S\)\\alpha\_\{I\}:=\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}\(\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S\)andInfIμ𝐳∣S:=1−αI\\textrm\{Inf\}\_\{I\}^\{\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}:=1\-\\alpha\_\{I\}\. Then there exist nonempty setsI1,…,In⊆\[n\]I\_\{1\},\\dots,I\_\{n\}\\subseteq\[n\]such thatαIr\>0\\alpha\_\{I\_\{r\}\}\>0, equivalentlyInfIrμ𝐳∣S<1\\textrm\{Inf\}\_\{I\_\{r\}\}^\{\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}<1, and signed vectorswr∈\{0,±1\}nw\_\{r\}\\in\\\{0,\\pm 1\\\}^\{n\}supported onIrI\_\{r\}such thatw1,…,wnw\_\{1\},\\dots,w\_\{n\}are linearly independent\. Consequently, the signed influence matrix

MS:=∑𝒙,𝒚∈Sμ𝒛∣S​\(𝒙\)​μ𝒛∣S​\(𝒚\)​\(𝒚−𝒙\)​\(𝒚−𝒙\)⊤M\_\{S\}:=\\sum\_\{\{\\boldsymbol\{x\}\},\\boldsymbol\{y\}\\in S\}\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}\)\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\\boldsymbol\{y\}\)\(\\boldsymbol\{y\}\-\{\\boldsymbol\{x\}\}\)\(\\boldsymbol\{y\}\-\{\\boldsymbol\{x\}\}\)^\{\\top\}is positive definite\.

###### Proof\.

Sinceaff⁡\(S\)=ℝn\\operatorname\{aff\}\(S\)=\\mathbb\{R\}^\{n\}, there exist points𝒙\(0\),𝒙\(1\),…,𝒙\(n\)∈S\{\\boldsymbol\{x\}\}^\{\(0\)\},\{\\boldsymbol\{x\}\}^\{\(1\)\},\\dots,\{\\boldsymbol\{x\}\}^\{\(n\)\}\\in Ssuch thatwr:=𝒙\(r\)−𝒙\(0\)w\_\{r\}:=\{\\boldsymbol\{x\}\}^\{\(r\)\}\-\{\\boldsymbol\{x\}\}^\{\(0\)\},r=1,…,nr=1,\\dots,n, are linearly independent\. For eachrr, letIr:=\{i:xi\(r\)≠xi\(0\)\}I\_\{r\}:=\\\{i:x\_\{i\}^\{\(r\)\}\\neq x\_\{i\}^\{\(0\)\}\\\}\. ThenIr≠∅I\_\{r\}\\neq\\emptysetand𝒙\(r\)=\(𝒙\(0\)\)⊕Ir\{\\boldsymbol\{x\}\}^\{\(r\)\}=\(\{\\boldsymbol\{x\}\}^\{\(0\)\}\)^\{\\oplus I\_\{r\}\}\. Sinceμ𝒛∣S​\(𝒙\(0\)\)\>0\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}^\{\(0\)\}\)\>0, we haveαIr⩾μ𝒛∣S​\(𝒙\(0\)\)\>0\\alpha\_\{I\_\{r\}\}\\geqslant\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}^\{\(0\)\}\)\>0, and thereforeInfIrμ𝒛∣S<1\\textrm\{Inf\}\_\{I\_\{r\}\}^\{\\mu\_\{\\boldsymbol\{z\}\\mid S\}\}<1\. Moreover, eachwr=𝒙\(r\)−𝒙\(0\)w\_\{r\}=\{\\boldsymbol\{x\}\}^\{\(r\)\}\-\{\\boldsymbol\{x\}\}^\{\(0\)\}is supported onIrI\_\{r\}, belongs to\{0,±1\}n\\\{0,\\pm 1\\\}^\{n\}, and the vectorsw1,…,wnw\_\{1\},\\dots,w\_\{n\}are linearly independent by construction\.

It remains to show thatMS≻0M\_\{S\}\\succ 0\. For anyv∈ℝnv\\in\\mathbb\{R\}^\{n\},v⊤​MS​v=∑𝒙,b​y∈Sμ𝒛∣S​\(𝒙\)​μ𝒛∣S​\(𝒚\)​⟨v,𝒚−𝒙⟩2⩾0v^\{\\top\}M\_\{S\}v=\\sum\_\{\{\\boldsymbol\{x\}\},by\\in S\}\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}\)\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\\boldsymbol\{y\}\)\\langle v,\\boldsymbol\{y\}\-\{\\boldsymbol\{x\}\}\\rangle^\{2\}\\geqslant 0\. Ifv⊤​MS​v=0v^\{\\top\}M\_\{S\}v=0, then⟨v,𝒚−𝒙⟩=0\\langle v,\\boldsymbol\{y\}\-\{\\boldsymbol\{x\}\}\\rangle=0for every𝒙,b​y∈S\{\\boldsymbol\{x\}\},by\\in S, since all weights are positive\. Thusvvis orthogonal tospan⁡\{𝒚−𝒙:𝒙,𝒚∈S\}\\operatorname\{span\}\\\{\\boldsymbol\{y\}\-\{\\boldsymbol\{x\}\}:\{\\boldsymbol\{x\}\},\\boldsymbol\{y\}\\in S\\\}\. Becauseaff⁡\(S\)=ℝn\\operatorname\{aff\}\(S\)=\\mathbb\{R\}^\{n\}, this span is all ofℝn\\mathbb\{R\}^\{n\}, sov=0v=0\. HenceMSM\_\{S\}is positive definite\. ∎

## Appendix BOmitted Proofs of Section[3](https://arxiv.org/html/2607.22889#S3)

### B\.1Proof of Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1)

In this section, we prove Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1), which provides parameter\-estimation guarantees for learning under the fatness condition and is restated below for reference\.

###### Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1)\.

Let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be independent random variables drawn from aγ\\gamma\-fat distributionμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, where‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. For everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\), if

N⩾C​n​e2​Rγ​ϵ2​log⁡\(2​nδ\),N\\geqslant C\\frac\{ne^\{2R\}\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\),then there is an algorithm that returns an estimate𝐳^\\hat\{\\boldsymbol\{z\}\}satisfying‖𝐳−𝐳^‖2⩽ϵ\\\|\\boldsymbol\{z\}\-\\hat\{\\boldsymbol\{z\}\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

We first isolate the one\-dimensional estimation problem on the selected subsample\.

###### Lemma B\.1\.

Let\(Fj,Xj\)j=1N\(F\_\{j\},X\_\{j\}\)\_\{j=1\}^\{N\}be independent and identically distributed, whereFj∈\{0,1\}F\_\{j\}\\in\\\{0,1\\\}is observed,𝐏𝐫​\(Fj=1\)⩾γ\\mathbf\{Pr\}\(F\_\{j\}=1\)\\geqslant\\gamma, and

Xj∣\{Fj=1\}∼Bernoulli⁡\(σ​\(z\)\)for some​\|z\|⩽R\.X\_\{j\}\\mid\\\{F\_\{j\}=1\\\}\\sim\\operatorname\{Bernoulli\}\(\\sigma\(z\)\)\\qquad\\text\{for some \}\|z\|\\leqslant R\.LetM:=∑j=1NFjM:=\\sum\_\{j=1\}^\{N\}F\_\{j\}, setYj:=2​Xj−1Y\_\{j\}:=2X\_\{j\}\-1, and, whenM\>0M\>0, define

z^∈arg​minw∈\[−R,R\]⁡1M​∑j:Fj=1log⁡\(1\+e−Yj​w\)\.\\widehat\{z\}\\in\\operatorname\*\{arg\\,min\}\_\{w\\in\[\-R,R\]\}\\frac\{1\}\{M\}\\sum\_\{j:F\_\{j\}=1\}\\log\(1\+e^\{\-Y\_\{j\}w\}\)\.IfM=0M=0, setz^:=0\\widehat\{z\}:=0\. There is a universal constantC\>0C\>0such that, for everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\),

N⩾C​e2​Rγ​ϵ2​log⁡\(4δ\)N\\geqslant C\\frac\{e^\{2R\}\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{4\}\{\\delta\}\\right\)implies\|z^−z\|⩽ϵ\|\\widehat\{z\}\-z\|\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

###### Proof of Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1)\.

For each coordinateii, takeFj=𝟏​\{\(𝒙\(j\)\)⊕i∈S\}F\_\{j\}=\\mathbf\{1\}\\\{\(\{\\boldsymbol\{x\}\}^\{\(j\)\}\)^\{\\oplus i\}\\in S\\\}andXj=xi\(j\)X\_\{j\}=x\_\{i\}^\{\(j\)\}\. The fatness assumption gives𝐏𝐫​\(Fj=1\)⩾γ\\mathbf\{Pr\}\(F\_\{j\}=1\)\\geqslant\\gamma\. Moreover, the eventFj=1F\_\{j\}=1depends only on𝒙−i\(j\)\{\\boldsymbol\{x\}\}\_\{\-i\}^\{\(j\)\}: it holds precisely when both completions\(0,𝒙−i\(j\)\)\(0,\{\\boldsymbol\{x\}\}\_\{\-i\}^\{\(j\)\}\)and\(1,𝒙−i\(j\)\)\(1,\{\\boldsymbol\{x\}\}\_\{\-i\}^\{\(j\)\}\)belong toSS\. The product structure therefore implies

xi\(j\)∣\{Fj=1\}∼Bernoulli⁡\(pi\)=Bernoulli⁡\(σ​\(zi\)\)\.x\_\{i\}^\{\(j\)\}\\mid\\\{F\_\{j\}=1\\\}\\sim\\operatorname\{Bernoulli\}\(p\_\{i\}\)=\\operatorname\{Bernoulli\}\(\\sigma\(z\_\{i\}\)\)\.Thus Lemma[B\.1](https://arxiv.org/html/2607.22889#A2.Thmlemma1)applies to every coordinate\.

Apply the lemma with target accuracyϵ/n\\epsilon/\\sqrt\{n\}and failure probabilityδ/n\\delta/n\. A union bound gives

𝐏𝐫​\(maxi∈\[n\]⁡\|z^i−zi\|\>ϵn\)⩽∑i=1n𝐏𝐫​\(\|z^i−zi\|\>ϵn\)⩽δ\.\\mathbf\{Pr\}\\left\(\\max\_\{i\\in\[n\]\}\|\\widehat\{z\}\_\{i\}\-z\_\{i\}\|\>\\frac\{\\epsilon\}\{\\sqrt\{n\}\}\\right\)\\leqslant\\sum\_\{i=1\}^\{n\}\\mathbf\{Pr\}\\left\(\|\\widehat\{z\}\_\{i\}\-z\_\{i\}\|\>\\frac\{\\epsilon\}\{\\sqrt\{n\}\}\\right\)\\leqslant\\delta\.On the complementary event,‖𝒛^−𝒛‖2⩽n​‖𝒛^−𝒛‖∞⩽ϵ\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\sqrt\{n\}\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant\\epsilon\. The asserted sample bound is exactly the resulting requirement from Lemma[B\.1](https://arxiv.org/html/2607.22889#A2.Thmlemma1)\. ∎

#### B\.1\.1Proof of Lemma[B\.1](https://arxiv.org/html/2607.22889#A2.Thmlemma1)

###### Proof of Lemma[B\.1](https://arxiv.org/html/2607.22889#A2.Thmlemma1)\.

Let

ℓy​\(w\):=log⁡\(1\+e−y​w\),ℒ​\(w\):=𝐄​\[ℓY​\(w\)∣F=1\]\.\\ell\_\{y\}\(w\):=\\log\(1\+e^\{\-yw\}\),\\qquad\\mathcal\{L\}\(w\):=\\mathbf\{E\}\[\\ell\_\{Y\}\(w\)\\mid F=1\]\.SinceY∣\{F=1\}Y\\mid\\\{F=1\\\}has logistic natural parameterzz,

ℒ′\(z\)=0,ℒ′′\(w\)=σ\(w\)\(1−σ\(w\)\)⩾eR\(1\+eR\)2=:κRfor allw∈\[−R,R\]\.\\mathcal\{L\}^\{\\prime\}\(z\)=0,\\qquad\\mathcal\{L\}^\{\\prime\\prime\}\(w\)=\\sigma\(w\)\(1\-\\sigma\(w\)\)\\geqslant\\frac\{e^\{R\}\}\{\(1\+e^\{R\}\)^\{2\}\}=:\\kappa\_\{R\}\\quad\\text\{for all \}w\\in\[\-R,R\]\.In particular,κR⩾e−R/4\\kappa\_\{R\}\\geqslant e^\{\-R\}/4\. Wheneverz\+ϵ⩽Rz\+\\epsilon\\leqslant R, strong convexity givesℒ′​\(z\+ϵ\)⩾κR​ϵ\\mathcal\{L\}^\{\\prime\}\(z\+\\epsilon\)\\geqslant\\kappa\_\{R\}\\epsilon; wheneverz−ϵ⩾−Rz\-\\epsilon\\geqslant\-R, it givesℒ′​\(z−ϵ\)⩽−κR​ϵ\\mathcal\{L\}^\{\\prime\}\(z\-\\epsilon\)\\leqslant\-\\kappa\_\{R\}\\epsilon\.

Condition on the selected index set and onM=m⩾1M=m\\geqslant 1\. The selected variables are independent draws from the conditional Bernoulli law\. Furthermore,ℓY′​\(w\)=−Y​σ​\(−Y​w\)∈\[−1,1\]\\ell\_\{Y\}^\{\\prime\}\(w\)=\-Y\\sigma\(\-Yw\)\\in\[\-1,1\]\. Hoeffding’s inequality therefore yields

𝐏𝐫​\(ℒ^′​\(z\+ϵ\)⩽0∣M=m\)⩽exp⁡\(−m​κR2​ϵ22\)\\mathbf\{Pr\}\\left\(\\widehat\{\\mathcal\{L\}\}^\{\\prime\}\(z\+\\epsilon\)\\leqslant 0\\mid M=m\\right\)\\leqslant\\exp\\left\(\-\\frac\{m\\kappa\_\{R\}^\{2\}\\epsilon^\{2\}\}\{2\}\\right\)whenever the upper endpoint lies in\[−R,R\]\[\-R,R\], and the same bound holds for𝐏𝐫​\(ℒ^′​\(z−ϵ\)⩾0∣M=m\)\\mathbf\{Pr\}\(\\widehat\{\\mathcal\{L\}\}^\{\\prime\}\(z\-\\epsilon\)\\geqslant 0\\mid M=m\)\. If an endpoint lies outside\[−R,R\]\[\-R,R\], the corresponding eventz^\>z\+ϵ\\widehat\{z\}\>z\+\\epsilonorz^<z−ϵ\\widehat\{z\}<z\-\\epsilonis impossible\. By convexity, the two gradient bounds thus imply\|z^−z\|⩽ϵ\|\\widehat\{z\}\-z\|\\leqslant\\epsilon\.

Writingq:=𝐏𝐫​\(F=1\)⩾γq:=\\mathbf\{Pr\}\(F=1\)\\geqslant\\gamma, we haveM∼Bin⁡\(N,q\)M\\sim\\operatorname\{Bin\}\(N,q\), and the multiplicative Chernoff bound gives

𝐏𝐫​\(M<γ​N2\)⩽𝐏𝐫​\(M<q​N2\)⩽exp⁡\(−γ​N8\)\.\\mathbf\{Pr\}\\left\(M<\\frac\{\\gamma N\}\{2\}\\right\)\\leqslant\\mathbf\{Pr\}\\left\(M<\\frac\{qN\}\{2\}\\right\)\\leqslant\\exp\\left\(\-\\frac\{\\gamma N\}\{8\}\\right\)\.Consequently,

𝐏𝐫​\(\|z^−z\|\>ϵ\)⩽exp⁡\(−γ​N8\)\+2​exp⁡\(−γ​N​κR2​ϵ24\)\.\\mathbf\{Pr\}\(\|\\widehat\{z\}\-z\|\>\\epsilon\)\\leqslant\\exp\\left\(\-\\frac\{\\gamma N\}\{8\}\\right\)\+2\\exp\\left\(\-\\frac\{\\gamma N\\kappa\_\{R\}^\{2\}\\epsilon^\{2\}\}\{4\}\\right\)\.UsingκR2⩾e−2​R/16\\kappa\_\{R\}^\{2\}\\geqslant e^\{\-2R\}/16shows that the sample size in the lemma makes the right\-hand side at mostδ\\delta, after increasing the universal constantCC\. ∎

#### B\.1\.2Bisection Algorithm for Learning in Relative Error

Recall that in the previous section, we proved that the empirical lossℒ^i\\hat\{\\mathcal\{L\}\}\_\{i\}is convex for everyi∈\[n\]i\\in\[n\]\. For each coordinatei∈\[n\]i\\in\[n\], the empirical objective is a one\-dimensional convex function\. It is therefore unnecessary to run a general high\-dimensional convex optimization method\. Instead, we minimize each coordinate\-wise empirical loss by bisection on its derivative\. Letyi\(j\):=2​xi\(j\)−1∈\{−1,1\}y\_\{i\}^\{\(j\)\}:=2x\_\{i\}^\{\(j\)\}\-1\\in\\\{\-1,1\\\}, and letFLIP​\(𝒙\(j\),i\)\\textsf\{FLIP\}\(\{\\boldsymbol\{x\}\}^\{\(j\)\},i\)denote whether thejj\-th sample is flippable in coordinateii\. Our goal is then to minimize

∇ℒ^i​\(w\)=−1Mi​∑j∈𝒥iyi\(j\)​σ​\(−yi\(j\)​w\),\\nabla\\hat\{\\mathcal\{L\}\}\_\{i\}\(w\)=\-\\frac\{1\}\{M\_\{i\}\}\\sum\_\{j\\in\\mathcal\{J\}\_\{i\}\}y\_\{i\}^\{\(j\)\}\\sigma\(\-y\_\{i\}^\{\(j\)\}w\),whereσ​\(t\)=1/\(1\+e−t\)\\sigma\(t\)=1/\(1\+e^\{\-t\}\)\.

Algorithm 1Coordinate\-wise minimization of the empirical logistic loss1:Samples

𝒙\(1\),…,𝒙\(N\)∼μ𝒛∣S\{\\boldsymbol\{x\}\}^\{\(1\)\},\\dots,\{\\boldsymbol\{x\}\}^\{\(N\)\}\\sim\\mu\_\{\\boldsymbol\{z\}\\mid S\}, truncation set

SS, radius

RR, optimization tolerance

τ\>0\\tau\>0
2:Estimate

𝒛^∈\[−R,R\]n\\hat\{\\boldsymbol\{z\}\}\\in\[\-R,R\]^\{n\}
3:for

i=1,…,ni=1,\\dots,ndo

4:

𝒥i←\{j∈\[N\]:\(𝒙\(j\)\)⊕i∈S\}\\mathcal\{J\}\_\{i\}\\leftarrow\\\{j\\in\[N\]:\(\{\\boldsymbol\{x\}\}^\{\(j\)\}\)^\{\\oplus i\}\\in S\\\},

Mi←\|𝒥i\|M\_\{i\}\\leftarrow\|\\mathcal\{J\}\_\{i\}\|
5:if

Mi=0M\_\{i\}=0then

6:

z^i←0\\hat\{z\}\_\{i\}\\leftarrow 0
7:else

8:Define

gi​\(w\):=∇ℒ^i​\(w\)g\_\{i\}\(w\):=\\nabla\\hat\{\\mathcal\{L\}\}\_\{i\}\(w\)
9:if

gi​\(−R\)⩾0g\_\{i\}\(\-R\)\\geqslant 0then

10:

z^i←−R\\hat\{z\}\_\{i\}\\leftarrow\-R
11:elseif

gi​\(R\)⩽0g\_\{i\}\(R\)\\leqslant 0then

12:

z^i←R\\hat\{z\}\_\{i\}\\leftarrow R
13:else

14:

a←−Ra\\leftarrow\-R,

b←Rb\\leftarrow R
15:while

b−a\>τb\-a\>\\taudo

16:

m←\(a\+b\)/2m\\leftarrow\(a\+b\)/2
17:if

gi​\(m\)⩽0g\_\{i\}\(m\)\\leqslant 0then

18:

a←ma\\leftarrow m
19:else

20:

b←mb\\leftarrow m
21:endif

22:endwhile

23:

z^i←\(a\+b\)/2\\hat\{z\}\_\{i\}\\leftarrow\(a\+b\)/2
24:endif

25:endif

26:endfor

27:return

𝒛^=\(z^1,…,z^n\)\\hat\{\\boldsymbol\{z\}\}=\(\\hat\{z\}\_\{1\},\\dots,\\hat\{z\}\_\{n\}\)

Remarks:For a fixed coordinateii, evaluatinggi​\(w\)g\_\{i\}\(w\)requires summing over theNNsamples, and therefore costs𝒪​\(N\)\\mathcal\{O\}\(N\)arithmetic operations\. Bisection over an interval of length2​R2Rto accuracyτ\\taurequires𝒪​\(log⁡\(R/τ\)\)\\mathcal\{O\}\(\\log\(R/\\tau\)\)operations\[[2](https://arxiv.org/html/2607.22889#bib.bib18)\]\. Therefore, running the bisection over all coordinates yields a total runtime of𝒪​\(n​N​log⁡Rτ\)\.\\mathcal\{O\}\\left\(nN\\log\\frac\{R\}\{\\tau\}\\right\)\.The statistical proof shows that the exact empirical minimizerz~i\\widetilde\{z\}\_\{i\}lies withinϵ\\epsilonofziz\_\{i\}with high probability\. The algorithm returnsz^i\\hat\{z\}\_\{i\}satisfying\|z^i−z~i\|⩽τ\|\\hat\{z\}\_\{i\}\-\\widetilde\{z\}\_\{i\}\|\\leqslant\\tau\. Therefore,

\|z^i−zi\|⩽\|z^i−z~i\|\+\|z~i−zi\|⩽τ\+ϵ\.\|\\hat\{z\}\_\{i\}\-z\_\{i\}\|\\leqslant\|\\hat\{z\}\_\{i\}\-\\widetilde\{z\}\_\{i\}\|\+\|\\widetilde\{z\}\_\{i\}\-z\_\{i\}\|\\leqslant\\tau\+\\epsilon\.Thus choosing, for example,τ=ϵ\\tau=\\epsilononly changes constants in the final estimation guarantee\. For anℓ2\\ell\_\{2\}guarantee, one may instead takeτ=ϵ/n\\tau=\\epsilon/\\sqrt\{n\}, giving total runtime𝒪​\(n​N​log⁡R​nϵ\)\.\\mathcal\{O\}\\left\(nN\\log\\frac\{R\\sqrt\{n\}\}\{\\epsilon\}\\right\)\.

### B\.2Proof of Theorem[3\.2](https://arxiv.org/html/2607.22889#S3.Thmtheorem2)

In this brief section, we prove Theorem[3\.2](https://arxiv.org/html/2607.22889#S3.Thmtheorem2)\. Our estimator𝒑^\\hat\{\\boldsymbol\{p\}\}is constructed coordinate by coordinate by taking the empirical average of all samples that are flippable in coordinateii\.

Algorithm 2Learning Bernoulli Probabilities from Flippable Samples1:Samples

𝒙\(1\),…,𝒙\(N\)∼μ𝒑∣S\{\\boldsymbol\{x\}\}^\{\(1\)\},\\dots,\{\\boldsymbol\{x\}\}^\{\(N\)\}\\sim\\mu\_\{\\boldsymbol\{p\}\\mid S\}, truncation set

S⊆\{0,1\}nS\\subseteq\\\{0,1\\\}^\{n\}
2:Estimate

𝒑^∈\[0,1\]n\\hat\{\\boldsymbol\{p\}\}\\in\[0,1\]^\{n\}
3:for

i=1,…,ni=1,\\dots,ndo

4:

Ni←0N\_\{i\}\\leftarrow 0,

Si←0S\_\{i\}\\leftarrow 0
5:for

j=1,…,Nj=1,\\dots,Ndo

6:if

FLIP​\(𝒙\(j\),i\)\\textsf\{FLIP\}\(\{\\boldsymbol\{x\}\}^\{\(j\)\},i\)then

7:

Ni←Ni\+1N\_\{i\}\\leftarrow N\_\{i\}\+1⊳\\trianglerightNumber of samples flippable inii

8:

Si←Si\+xi\(j\)S\_\{i\}\\leftarrow S\_\{i\}\+x\_\{i\}^\{\(j\)\}⊳\\trianglerightRunning sum of flippable samples

9:endif

10:endfor

11:if

Ni=0N\_\{i\}=0then

12:

p^i←1/2\\hat\{p\}\_\{i\}\\leftarrow 1/2
13:else

14:

p^i←Si/Ni\\hat\{p\}\_\{i\}\\leftarrow S\_\{i\}/N\_\{i\}
15:endif

16:endfor

17:return

𝒑^=\(p^1,…,p^n\)\\hat\{\\boldsymbol\{p\}\}=\(\\hat\{p\}\_\{1\},\\dots,\\hat\{p\}\_\{n\}\)

###### Proof of Theorem[3\.2](https://arxiv.org/html/2607.22889#S3.Thmtheorem2)\.

For each coordinatei∈\[n\]i\\in\[n\], let

qi:=𝐏𝐫𝒙∼μ𝒑∣S​\(𝒙⊕i∈S\)⩾γ,q\_\{i\}:=\\mathbf\{Pr\}\_\{\{\\boldsymbol\{x\}\}\\sim\\mu\_\{\\boldsymbol\{p\}\\mid S\}\}\(\{\\boldsymbol\{x\}\}^\{\\oplus i\}\\in S\)\\geqslant\\gamma,and letNiN\_\{i\}be the number of samples flippable in coordinateii\. ThenNi∼Bin⁡\(N,qi\)N\_\{i\}\\sim\\operatorname\{Bin\}\(N,q\_\{i\}\), so the multiplicative Chernoff bound gives

𝐏𝐫​\(Ni<γ​N2\)⩽𝐏𝐫​\(Ni<qi​N2\)⩽exp⁡\(−γ​N8\)\.\\mathbf\{Pr\}\\left\(N\_\{i\}<\\frac\{\\gamma N\}\{2\}\\right\)\\leqslant\\mathbf\{Pr\}\\left\(N\_\{i\}<\\frac\{q\_\{i\}N\}\{2\}\\right\)\\leqslant\\exp\\left\(\-\\frac\{\\gamma N\}\{8\}\\right\)\.WheneverNi\>0N\_\{i\}\>0, define

p^i:=1Ni​∑j∈\[N\]:\(𝒙\(j\)\)⊕i∈Sxi\(j\)\.\\hat\{p\}\_\{i\}:=\\frac\{1\}\{N\_\{i\}\}\\sum\_\{\\begin\{subarray\}\{c\}j\\in\[N\]:\\\\ \(\{\\boldsymbol\{x\}\}^\{\(j\)\}\)^\{\\oplus i\}\\in S\\end\{subarray\}\}x\_\{i\}^\{\(j\)\}\.As in the proof of Theorem[3\.1](https://arxiv.org/html/2607.22889#S3.Thmtheorem1), conditional on flippability the selected coordinates are independentBernoulli⁡\(pi\)\\operatorname\{Bernoulli\}\(p\_\{i\}\)variables\. Thus, conditional onNi=m⩾γ​N/2N\_\{i\}=m\\geqslant\\gamma N/2, Hoeffding’s inequality gives

𝐏𝐫​\(\|p^i−pi\|\>ϵ∣Ni=m\)⩽2​e−2​m​ϵ2⩽2​e−γ​N​ϵ2\.\\mathbf\{Pr\}\\left\(\|\\hat\{p\}\_\{i\}\-p\_\{i\}\|\>\\epsilon\\mid N\_\{i\}=m\\right\)\\leqslant 2e^\{\-2m\\epsilon^\{2\}\}\\leqslant 2e^\{\-\\gamma N\\epsilon^\{2\}\}\.Combining the two bounds and taking a union bound overi∈\[n\]i\\in\[n\]yields

𝐏𝐫​\(‖𝒑^−𝒑‖∞\>ϵ\)⩽n​e−γ​N/8\+2​n​e−γ​N​ϵ2\.\\mathbf\{Pr\}\\left\(\\\|\\hat\{\\boldsymbol\{p\}\}\-\\boldsymbol\{p\}\\\|\_\{\\infty\}\>\\epsilon\\right\)\\leqslant ne^\{\-\\gamma N/8\}\+2ne^\{\-\\gamma N\\epsilon^\{2\}\}\.Forϵ∈\(0,1\)\\epsilon\\in\(0,1\), the right\-hand side is at mostδ\\deltawhen

N⩾C​1γ​ϵ2​log⁡\(2​nδ\)N\\geqslant C\\frac\{1\}\{\\gamma\\epsilon^\{2\}\}\\log\\left\(\\frac\{2n\}\{\\delta\}\\right\)for a sufficiently large universal constantCC\. This proves theℓ∞\\ell\_\{\\infty\}statement\. Applying it with target accuracyϵ/n\\epsilon/\\sqrt\{n\}gives‖𝒑^−𝒑‖2⩽ϵ\\\|\\hat\{\\boldsymbol\{p\}\}\-\\boldsymbol\{p\}\\\|\_\{2\}\\leqslant\\epsilonand the assertedℓ2\\ell\_\{2\}sample complexity\. ∎

## Appendix COmitted Proofs of Section[4](https://arxiv.org/html/2607.22889#S4)

Before proving Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1), we introduce some notation\.

For every nonemptyI⊆\[n\]I\\subseteq\[n\]with\|I\|⩽k\|I\|\\leqslant kand everys∈\{±1\}Is\\in\\\{\\pm 1\\\}^\{I\}satisfyingsmin⁡I=\+1s\_\{\\min I\}=\+1, we call\(I,s\)\(I,s\)acandidate pair\. Thus, for each suchII, the candidates contain exactly one representative of every antipodal pair\{s,−s\}\\\{s,\-s\\\}\. For a candidate\(I,s\)\(I,s\), let𝒘I,s∈\{0,±1\}n\\boldsymbol\{w\}\_\{I,s\}\\in\\\{0,\\pm 1\\\}^\{n\}be the extension ofssby zero outsideII, and define the paired minimal\-flip set

EI,s:=\{𝒙∈S:𝒔I​\(𝒙\)∈\{s,−s\},𝒙⊕I∈S,𝒙⊕J∉Sfor every​∅≠J⊊I\},E\_\{I,s\}:=\\left\\\{\{\\boldsymbol\{x\}\}\\in S:\\begin\{array\}\[\]\{l\}\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)\\in\\\{s,\-s\\\},\\quad\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S,\\\\\[2\.84526pt\] \{\\boldsymbol\{x\}\}^\{\\oplus J\}\\notin S\\quad\\text\{for every \}\\varnothing\\neq J\\subsetneq I\\end\{array\}\\right\\\},and its probability

pI,s:=𝐏𝐫​\(𝒙∈EI,s\)\.p\_\{I,s\}:=\\mathbf\{Pr\}\(\{\\boldsymbol\{x\}\}\\in E\_\{I,s\}\)\.
###### Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1)\.

Fixkk, and let𝐱\(1\),…,𝐱\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}be independent random variables drawn fromμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}, whereμ𝐳∣S\\mu\_\{\\boldsymbol\{z\}\\mid S\}satisfies Assumptions[4\.1](https://arxiv.org/html/2607.22889#S4.Thmassumption1)and[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2), and‖𝐳‖∞⩽R\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}\\leqslant R\. There is a universal constantC\>0C\>0such that, for everyϵ,δ∈\(0,1\)\\epsilon,\\delta\\in\(0,1\), if

N⩾C​2k​e2​k​Rγ​λs​ϵ2​\(k​log⁡\(2​n\)\+log⁡4​kδ\),N\\geqslant C\\frac\{2^\{k\}e^\{2kR\}\}\{\\gamma\\lambda\_\{s\}\\epsilon^\{2\}\}\\left\(k\\log\(2n\)\+\\log\\frac\{4k\}\{\\delta\}\\right\),then a polynomial\-time algorithm returns an estimate𝐳^\\widehat\{\\boldsymbol\{z\}\}satisfying‖𝐳^−𝐳‖2⩽ϵ\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\epsilonwith probability at least1−δ1\-\\delta\.

The proof is organized around two main lemmas, \(i\) ensuring there are sufficiently many flip directions to learn the underlying parameters, and \(ii\) ensuring that the linear system formed by these directions is well\-conditioned\.

The final subsection first verifies \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex55)\) directly from Assumptions[4\.1](https://arxiv.org/html/2607.22889#S4.Thmassumption1)and[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2), and then proves Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1)by combining these results\.

### C\.1The Algorithm

The estimator never needs to know or sample from the hidden support family\. It works only with candidate pairs observed in the data and computes well\-conditioned design weights over those pairs\. For the remainder of this section, set

p0:=γ2k\.p\_\{0\}:=\\frac\{\\gamma\}\{2^\{k\}\}\.The analysis uses the following informative\-design condition: there is an unknown distributionπ⋆\\pi\_\{\\star\}over the candidate pairs\(I,s\)\(I,s\)such that

pI,s⩾p0for every​\(I,s\)∈supp⁡\(π⋆\),𝐄\(I,s\)∼π⋆​\[𝒘I,s​𝒘I,s𝖳\]⪰λs​In\.p\_\{I,s\}\\geqslant p\_\{0\}\\quad\\text\{for every \}\(I,s\)\\in\\operatorname\{supp\}\(\\pi\_\{\\star\}\),\\qquad\\mathbf\{E\}\_\{\(I,s\)\\sim\\pi\_\{\\star\}\}\\\!\\left\[\\boldsymbol\{w\}\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}\\right\]\\succeq\\lambda\_\{s\}I\_\{n\}\.The inputsk,R,p0k,R,p\_\{0\}, andλs\\lambda\_\{s\}are known to the learner:RRis a valid upper bound on‖𝒛‖∞\\\|\\boldsymbol\{z\}\\\|\_\{\\infty\}, whilep0p\_\{0\}andλs\\lambda\_\{s\}are valid lower bounds in \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex55)\)\. The witnessπ⋆\\pi\_\{\\star\}is not known\.

Given samples𝒙\(1\),…,𝒙\(N\)\{\\boldsymbol\{x\}\}^\{\(1\)\},\\ldots,\{\\boldsymbol\{x\}\}^\{\(N\)\}, we estimate each paired\-event mass by

p^I,s:=1N​∑ℓ=1N𝟏​\{𝒙\(ℓ\)∈EI,s\}\.\\widehat\{p\}\_\{I,s\}:=\\frac\{1\}\{N\}\\sum\_\{\\ell=1\}^\{N\}\\mathbf\{1\}\\\{\{\\boldsymbol\{x\}\}^\{\(\\ell\)\}\\in E\_\{I,s\}\\\}\.For each supportII, a sample can contribute to only one canonical sign pair\. Thus the implementation need only materialize pairs that actually appear; every unobserved pair hasp^I,s=0\\widehat\{p\}\_\{I,s\}=0\. Retain

ℛ^:=\{\(I,s\):p^I,s⩾3​p04\}\.\\widehat\{\\mathcal\{R\}\}:=\\left\\\{\(I,s\):\\widehat\{p\}\_\{I,s\}\\geqslant\\frac\{3p\_\{0\}\}\{4\}\\right\\\}\.For every candidate\(I,s\)\(I,s\)that occurs at least once in the sample, definey^I,s\\widehat\{y\}\_\{I,s\}to be the constrained maximum\-likelihood estimator

y^I,s∈arg​min\|u\|⩽\|I\|​R​∑ℓ:𝒙\(ℓ\)∈EI,s\[log⁡\(2​cosh⁡u2\)−u2​\(2​𝟏​\{𝒔I​\(𝒙\(ℓ\)\)=s\}−1\)\]\.\\widehat\{y\}\_\{I,s\}\\in\\operatorname\*\{arg\\,min\}\_\{\|u\|\\leqslant\|I\|R\}\\sum\_\{\\ell:\\,\{\\boldsymbol\{x\}\}^\{\(\\ell\)\}\\in E\_\{I,s\}\}\\left\[\\log\\left\(2\\cosh\\frac\{u\}\{2\}\\right\)\-\\frac\{u\}\{2\}\\left\(2\\mathbf\{1\}\\\{\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}^\{\(\\ell\)\}\)=s\\\}\-1\\right\)\\right\]\.If the pair never occurs, sety^I,s:=0\\widehat\{y\}\_\{I,s\}:=0\. The algorithm computes and uses this quantity only for retained pairs; the threshold in \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex57)\) ensures that their defining sums are nonempty\.

Next, find weightsqqonℛ^\\widehat\{\\mathcal\{R\}\}satisfying

qI,s\\displaystyle q\_\{I,s\}⩾0\\displaystyle\\geqslant 0for every​\(I,s\)∈ℛ^,\\displaystyle\\text\{for every \}\(I,s\)\\in\\widehat\{\\mathcal\{R\}\},∑\(I,s\)∈ℛ^qI,s\\displaystyle\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}q\_\{I,s\}=1,\\displaystyle=1,∑\(I,s\)∈ℛ^qI,s​𝒘I,s​𝒘I,s𝖳\\displaystyle\\qquad\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}q\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}⪰λs2​In\.\\displaystyle\\succeq\\frac\{\\lambda\_\{s\}\}\{2\}I\_\{n\}\.We then solve the following minimization problem\.

𝒛^∈arg​min𝒖∈ℝn​∑\(I,s\)∈ℛ^qI,s​\(y^I,s−⟨𝒘I,s,𝒖⟩\)2\.\\widehat\{\\boldsymbol\{z\}\}\\in\\operatorname\*\{arg\\,min\}\_\{\\boldsymbol\{u\}\\in\\mathbb\{R\}^\{n\}\}\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}q\_\{I,s\}\\left\(\\widehat\{y\}\_\{I,s\}\-\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{u\}\\rangle\\right\)^\{2\}\.

### C\.2Finding Directions

In this section, we wish to demonstrate that given Assumptions[4\.1](https://arxiv.org/html/2607.22889#S4.Thmassumption1),[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2), we can find sufficiently many well conditioned directions to learn the underlying parameters\. We note that there are at most

∑r=1k2r−1​\(nr\)⩽k​\(2​n\)k\\sum\_\{r=1\}^\{k\}2^\{r\-1\}\\binom\{n\}\{r\}\\leqslant k\(2n\)^\{k\}candidate pairs\. This elementary count is the only combinatorial factor in the concentration arguments below\. Our primary result in this section is demonstrating the following sample complexity bound on estimating linear forms\.

###### Lemma C\.1\(Uniform data event\)\.

There is a universal constantC\>0C\>0such that, if

N⩾C​\(1p0\+e2​k​Rp0​η2\)​\(k​log⁡\(2​n\)\+log⁡4​kδ\),N\\geqslant C\\left\(\\frac\{1\}\{p\_\{0\}\}\+\\frac\{e^\{2kR\}\}\{p\_\{0\}\\eta^\{2\}\}\\right\)\\left\(k\\log\(2n\)\+\\log\\frac\{4k\}\{\\delta\}\\right\),then, with probability at least1−δ1\-\\delta, all three statements below hold simultaneously:

1. 1\.supp⁡\(π⋆\)⊆ℛ^\\operatorname\{supp\}\(\\pi\_\{\\star\}\)\\subseteq\\widehat\{\\mathcal\{R\}\};
2. 2\.every\(I,s\)∈ℛ^\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}satisfiespI,s\>p0/2p\_\{I,s\}\>p\_\{0\}/2;
3. 3\.every\(I,s\)∈ℛ^\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}satisfies \|y^I,s−⟨𝒘I,s,𝒛⟩\|⩽η\.\\left\|\\widehat\{y\}\_\{I,s\}\-\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\\right\|\\leqslant\\eta\.

Towards demonstrating the above lemma, we first show that the linear form⟨𝒘I,s,𝒛⟩\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\ranglecan be estimated with high probability from the samples inEI,sE\_\{I,s\}\.

###### Lemma C\.2\(Estimation of one linear form\)\.

For every candidate\(I,s\)\(I,s\)withpI,s\>0p\_\{I,s\}\>0, conditional on𝐱∈EI,s\{\\boldsymbol\{x\}\}\\in E\_\{I,s\}, the orientation

A:=\{\+1,𝒔I​\(𝒙\)=s,−1,𝒔I​\(𝒙\)=−sA:=\\begin\{cases\}\+1,&\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=s,\\\\ \-1,&\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=\-s\\end\{cases\}has distribution

𝐏𝐫u​\(A=a\)=ea​u/22​cosh⁡\(u/2\),a∈\{±1\},u:=⟨𝒘I,s,𝒛⟩\.\\mathbf\{Pr\}\_\{u\}\(A=a\)=\\frac\{e^\{au/2\}\}\{2\\cosh\(u/2\)\},\\qquad a\\in\\\{\\pm 1\\\},\\qquad u:=\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\.Moreover, for every candidate\(I,s\)\(I,s\)and everyη\>0\\eta\>0,

𝐏𝐫​\(\|y^I,s−⟨𝒘I,s,𝒛⟩\|\>η\)⩽exp⁡\(−N​pI,s8\)\+2​exp⁡\(−N​pI,s​η216​e\|I\|​R\)\.\\mathbf\{Pr\}\\left\(\\left\|\\widehat\{y\}\_\{I,s\}\-\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\\right\|\>\\eta\\right\)\\leqslant\\exp\\left\(\-\\frac\{Np\_\{I,s\}\}\{8\}\\right\)\+2\\exp\\left\(\-\\frac\{Np\_\{I,s\}\\eta^\{2\}\}\{16e^\{\|I\|R\}\}\\right\)\.

#### C\.2\.1Proof of Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1)

###### Proof\.

Fix a candidate withpI,s⩾p0p\_\{I,s\}\\geqslant p\_\{0\}\. A multiplicative Chernoff bound gives

𝐏𝐫​\(p^I,s<3​p04\)⩽𝐏𝐫​\(p^I,s<3​pI,s4\)⩽exp⁡\(−N​p032\)\.\\mathbf\{Pr\}\\left\(\\widehat\{p\}\_\{I,s\}<\\frac\{3p\_\{0\}\}\{4\}\\right\)\\leqslant\\mathbf\{Pr\}\\left\(\\widehat\{p\}\_\{I,s\}<\\frac\{3p\_\{I,s\}\}\{4\}\\right\)\\leqslant\\exp\\left\(\-\\frac\{Np\_\{0\}\}\{32\}\\right\)\.Conversely, ifpI,s⩽p0/2p\_\{I,s\}\\leqslant p\_\{0\}/2, then stochastic monotonicity of the binomial distribution and the upper\-tail Chernoff bound give

𝐏𝐫​\(p^I,s⩾3​p04\)\\displaystyle\\mathbf\{Pr\}\\left\(\\widehat\{p\}\_\{I,s\}\\geqslant\\frac\{3p\_\{0\}\}\{4\}\\right\)⩽𝐏𝐫​\(1N​Bin⁡\(N,p02\)⩾3​p04\)\\displaystyle\\leqslant\\mathbf\{Pr\}\\left\(\\frac\{1\}\{N\}\\operatorname\{Bin\}\\left\(N,\\frac\{p\_\{0\}\}\{2\}\\right\)\\geqslant\\frac\{3p\_\{0\}\}\{4\}\\right\)⩽exp⁡\(−N​p020\)⩽exp⁡\(−N​p032\)\.\\displaystyle\\leqslant\\exp\\left\(\-\\frac\{Np\_\{0\}\}\{20\}\\right\)\\leqslant\\exp\\left\(\-\\frac\{Np\_\{0\}\}\{32\}\\right\)\.There are at mostk​\(2​n\)kk\(2n\)^\{k\}candidate pairs\. Therefore a union bound shows that the probability that either the first or second conclusion of the lemma fails is at most

2​k​\(2​n\)k​exp⁡\(−N​p032\)\.2k\(2n\)^\{k\}\\exp\\left\(\-\\frac\{Np\_\{0\}\}\{32\}\\right\)\.
For the third conclusion, apply Lemma[C\.2](https://arxiv.org/html/2607.22889#A3.Thmlemma2)to every candidate withpI,s⩾p0/2p\_\{I,s\}\\geqslant p\_\{0\}/2\. A second union bound shows that the probability that any such estimate has error greater thanη\\etais at most

k​\(2​n\)k​\[exp⁡\(−N​p016\)\+2​exp⁡\(−N​p0​η232​ek​R\)\]\.k\(2n\)^\{k\}\\left\[\\exp\\left\(\-\\frac\{Np\_\{0\}\}\{16\}\\right\)\+2\\exp\\left\(\-\\frac\{Np\_\{0\}\\eta^\{2\}\}\{32e^\{kR\}\}\\right\)\\right\]\.The sample\-size condition \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex62)\), for a sufficiently large universal constantCC, makes the sum of the two displayed failure probabilities at mostδ\\delta\.

The estimation event is uniform over the deterministic collection of all candidate pairs withpI,s⩾p0/2p\_\{I,s\}\\geqslant p\_\{0\}/2\. On the screening event, every data\-dependent retained pair belongs to this collection\. Consequently, the same samples may be used for screening and estimation; no sample splitting or independence between the two events is required\. ∎

#### C\.2\.2Proof of Lemma[C\.2](https://arxiv.org/html/2607.22889#A3.Thmlemma2)

###### Proof\.

We first establish the asserted conditional law\. The mapTI​\(𝒙\):=𝒙⊕IT\_\{I\}\(\{\\boldsymbol\{x\}\}\):=\{\\boldsymbol\{x\}\}^\{\\oplus I\}is a bijection between the points inEI,sE\_\{I,s\}satisfying𝒔I​\(𝒙\)=s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=sand those satisfying𝒔I​\(𝒙\)=−s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=\-s\. Indeed, if𝐲=TI​\(𝒙\)\\mathbf\{y\}=T\_\{I\}\(\{\\boldsymbol\{x\}\}\), then𝐲∈S\\mathbf\{y\}\\in Sand𝐲⊕I=𝒙∈S\\mathbf\{y\}^\{\\oplus I\}=\{\\boldsymbol\{x\}\}\\in S\. Moreover, for every∅≠J⊊I\\varnothing\\neq J\\subsetneq I,

𝐲⊕J=𝒙⊕\(I∖J\)∉S,\\mathbf\{y\}^\{\\oplus J\}=\{\\boldsymbol\{x\}\}^\{\\oplus\(I\\setminus J\)\}\\notin S,becauseI∖JI\\setminus Jis again a nonempty proper subset ofII\. ThusTIT\_\{I\}preserves the defining conditions ofEI,sE\_\{I,s\}and is an involution\.

For every matched pair𝒙,TI​\(𝒙\)\{\\boldsymbol\{x\}\},T\_\{I\}\(\{\\boldsymbol\{x\}\}\)with𝒔I​\(𝒙\)=s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=s,

μ𝒛∣S​\(𝒙\)μ𝒛∣S​\(TI​\(𝒙\)\)=exp⁡\(⟨𝒛,𝒙−TI​\(𝒙\)⟩\)=exp⁡\(∑i∈Isi​zi\)=exp⁡\(⟨𝒘I,s,𝒛⟩\)\.\\frac\{\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(\{\\boldsymbol\{x\}\}\)\}\{\\mu\_\{\\boldsymbol\{z\}\\mid S\}\(T\_\{I\}\(\{\\boldsymbol\{x\}\}\)\)\}=\\exp\\left\(\\langle\\boldsymbol\{z\},\{\\boldsymbol\{x\}\}\-T\_\{I\}\(\{\\boldsymbol\{x\}\}\)\\rangle\\right\)=\\exp\\left\(\\sum\_\{i\\in I\}s\_\{i\}z\_\{i\}\\right\)=\\exp\\left\(\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\\right\)\.Summing over the points with𝒔I​\(𝒙\)=s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=sand normalizing by the total mass ofEI,sE\_\{I,s\}gives the stated logistic law\.

LetMMbe the number of observations falling inEI,sE\_\{I,s\}\. IfpI,s=0p\_\{I,s\}=0, then \([C\.2](https://arxiv.org/html/2607.22889#A3.Ex66)\) is immediate, so assumepI,s\>0p\_\{I,s\}\>0\. ThenM∼Bin⁡\(N,pI,s\)M\\sim\\operatorname\{Bin\}\(N,p\_\{I,s\}\)\. Conditional on the set of indices counted byMM, the corresponding observations are independent draws from the law of𝒙\{\\boldsymbol\{x\}\}given𝒙∈EI,s\{\\boldsymbol\{x\}\}\\in E\_\{I,s\}\. WhenM=0M=0, the conditional bound below is trivial; hence fixM=m⩾1M=m\\geqslant 1and associate to each of thesemmobservations the orientationA=\+1A=\+1when𝒔I​\(𝒙\)=s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=sandA=−1A=\-1when𝒔I​\(𝒙\)=−s\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=\-s\. By the first part of the lemma, these orientations are i\.i\.d\. from𝐏𝐫u\\mathbf\{Pr\}\_\{u\}, whereu:=⟨𝒘I,s,𝒛⟩u:=\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\. Moreover,\|u\|⩽\|I\|​R\|u\|\\leqslant\|I\|R, and \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex58)\) is the maximum\-likelihood estimator ofuuconstrained to this interval\.

As a function of the log\-odds parameter, the log\-partition function isψ​\(v\):=log⁡\(2​cosh⁡\(v/2\)\)\\psi\(v\):=\\log\(2\\cosh\(v/2\)\), and

ψ′′​\(v\)=14​sech2⁡\(v/2\)⩾14​e\|I\|​Rfor every​\|v\|⩽\|I\|​R\.\\psi^\{\\prime\\prime\}\(v\)=\\frac\{1\}\{4\}\\operatorname\{sech\}^\{2\}\(v/2\)\\geqslant\\frac\{1\}\{4e^\{\|I\|R\}\}\\qquad\\text\{for every \}\|v\|\\leqslant\|I\|R\.Ifu\+η⩽\|I\|​Ru\+\\eta\\leqslant\|I\|R, the eventy^I,s⩾u\+η\\widehat\{y\}\_\{I,s\}\\geqslant u\+\\etaimplies that the empirical mean of the orientations is at leasttanh⁡\(\(u\+η\)/2\)\\tanh\(\(u\+\\eta\)/2\)\. The exponential\-family Chernoff bound therefore gives

𝐏𝐫​\(y^I,s⩾u\+η∣M=m\)⩽exp⁡\(−m​D​\(𝐏𝐫u\+η∥𝐏𝐫u\)\)\.\\mathbf\{Pr\}\\left\(\\widehat\{y\}\_\{I,s\}\\geqslant u\+\\eta\\mid M=m\\right\)\\leqslant\\exp\\left\(\-mD\(\\mathbf\{Pr\}\_\{u\+\\eta\}\\\|\\mathbf\{Pr\}\_\{u\}\)\\right\)\.WritingD\(⋅∥⋅\)D\(\\cdot\\\|\\cdot\)for Kullback–Leibler divergence, for this family

D​\(𝐏𝐫v∥𝐏𝐫u\)=ψ​\(u\)−ψ​\(v\)−ψ′​\(v\)​\(u−v\)\.D\(\\mathbf\{Pr\}\_\{v\}\\\|\\mathbf\{Pr\}\_\{u\}\)=\\psi\(u\)\-\\psi\(v\)\-\\psi^\{\\prime\}\(v\)\(u\-v\)\.The displayed lower bound onψ′′\\psi^\{\\prime\\prime\}implies

D​\(𝐏𝐫u\+η∥𝐏𝐫u\)⩾η28​e\|I\|​R\.D\(\\mathbf\{Pr\}\_\{u\+\\eta\}\\\|\\mathbf\{Pr\}\_\{u\}\)\\geqslant\\frac\{\\eta^\{2\}\}\{8e^\{\|I\|R\}\}\.Ifu\+η\>\|I\|​Ru\+\\eta\>\|I\|R, the upper\-tail event is empty because the estimator is constrained\. Applying the same argument to the lower tail gives

𝐏𝐫​\(\|y^I,s−u\|\>η∣M=m\)⩽2​exp⁡\(−m​η28​e\|I\|​R\)\.\\mathbf\{Pr\}\\left\(\\left\|\\widehat\{y\}\_\{I,s\}\-u\\right\|\>\\eta\\mid M=m\\right\)\\leqslant 2\\exp\\left\(\-\\frac\{m\\eta^\{2\}\}\{8e^\{\|I\|R\}\}\\right\)\.Finally, the multiplicative Chernoff bound gives

𝐏𝐫​\(M<N​pI,s2\)⩽exp⁡\(−N​pI,s8\)\.\\mathbf\{Pr\}\\left\(M<\\frac\{Np\_\{I,s\}\}\{2\}\\right\)\\leqslant\\exp\\left\(\-\\frac\{Np\_\{I,s\}\}\{8\}\\right\)\.On the complementary event, substitutem⩾N​pI,s/2m\\geqslant Np\_\{I,s\}/2into the preceding conditional bound to obtain \([C\.2](https://arxiv.org/html/2607.22889#A3.Ex66)\)\. ∎

### C\.3Least\-Squares Recovery

We now demonstrate that given the inputs of the previous section, the linear system formed by the retained candidate pairs is well\-conditioned and can be solved to recover the underlying parameters\. The following two lemmas formalize this argument\.

###### Lemma C\.3\(Designed recovery\)\.

On the event of Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1), the feasibility problem \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\) has a solution and the estimator \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex60)\) satisfies

‖𝒛^−𝒛‖2⩽η​2λs\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\}\.

Towards proving this lemma, we first show that the weighted least\-squares problem is stable to perturbations in the linear forms\.

###### Lemma C\.4\(Weighted least\-squares stability\)\.

Supposeqqsatisfies \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\) and

\|y^I,s−⟨𝒘I,s,𝒛⟩\|⩽ηwhenever​qI,s\>0\.\\left\|\\widehat\{y\}\_\{I,s\}\-\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\\right\|\\leqslant\\eta\\qquad\\text\{whenever \}q\_\{I,s\}\>0\.Then the minimizer in \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex60)\) is unique and

‖𝒛^−𝒛‖2⩽η​2λs\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\}\.

#### C\.3\.1Proof of Lemma[C\.3](https://arxiv.org/html/2607.22889#A3.Thmlemma3)

###### Proof\.

On the event of Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1),supp⁡\(π⋆\)⊆ℛ^\\operatorname\{supp\}\(\\pi\_\{\\star\}\)\\subseteq\\widehat\{\\mathcal\{R\}\}\. Extendπ⋆\\pi\_\{\\star\}toℛ^\\widehat\{\\mathcal\{R\}\}by assigning zero mass to every retained pair outside its support\. By \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex55)\),

∑\(I,s\)∈ℛ^π⋆​\(I,s\)​𝒘I,s​𝒘I,s𝖳⪰λs​In\.\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}\\pi\_\{\\star\}\(I,s\)\\boldsymbol\{w\}\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}\\succeq\\lambda\_\{s\}I\_\{n\}\.Thus the feasibility problem \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\) has a solution; indeed,π⋆\\pi\_\{\\star\}is feasible even withλs​In\\lambda\_\{s\}I\_\{n\}in place of\(λs/2\)​In\(\\lambda\_\{s\}/2\)I\_\{n\}\.

The third conclusion of Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1)controls every retained row and therefore every row receiving positiveqq\-mass\. Lemma[C\.4](https://arxiv.org/html/2607.22889#A3.Thmlemma4)now gives

‖𝒛^−𝒛‖2⩽η​2λs\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\}\.∎

#### C\.3\.2Proof of Lemma[C\.4](https://arxiv.org/html/2607.22889#A3.Thmlemma4)

###### Proof\.

For this proof only, define

G:=∑\(I,s\)∈ℛ^qI,s​𝒘I,s​𝒘I,s𝖳\.G:=\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}q\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}\.By \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\),G⪰\(λs/2\)​InG\\succeq\(\\lambda\_\{s\}/2\)I\_\{n\}, so the weighted least\-squares objective is strictly convex and has a unique minimizer\.

LetAAbe the matrix whose row indexed by\(I,s\)\(I,s\)isqI,s​𝒘I,s𝖳\\sqrt\{q\_\{I,s\}\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}, omitting rows of zero weight\. Let𝐞\\mathbf\{e\}be the vector whose corresponding entry is

qI,s​\(y^I,s−⟨𝒘I,s,𝒛⟩\)\.\\sqrt\{q\_\{I,s\}\}\\left\(\\widehat\{y\}\_\{I,s\}\-\\langle\\boldsymbol\{w\}\_\{I,s\},\\boldsymbol\{z\}\\rangle\\right\)\.ThenA𝖳​A=GA^\{\\mathsf\{T\}\}A=Gand

‖𝐞‖22⩽∑\(I,s\)∈ℛ^qI,s​η2=η2\.\\\|\\mathbf\{e\}\\\|\_\{2\}^\{2\}\\leqslant\\sum\_\{\(I,s\)\\in\\widehat\{\\mathcal\{R\}\}\}q\_\{I,s\}\\eta^\{2\}=\\eta^\{2\}\.The normal equation\*s give

𝒛^−𝒛=\(A𝖳​A\)−1​A𝖳​𝐞\.\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}=\(A^\{\\mathsf\{T\}\}A\)^\{\-1\}A^\{\\mathsf\{T\}\}\\mathbf\{e\}\.Sinceσmin​\(A\)⩾λs/2\\sigma\_\{\\min\}\(A\)\\geqslant\\sqrt\{\\lambda\_\{s\}/2\}, the norm of the left pseudoinverse is at most2/λs\\sqrt\{2/\\lambda\_\{s\}\}\. Therefore

‖𝒛^−𝒛‖2⩽η​2λs\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\}\.∎

### C\.4Proof of Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1)

###### Proof of Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1)\.

For everyI∈ℱI\\in\\mathcal\{F\}, Assumption[4\.1](https://arxiv.org/html/2607.22889#S4.Thmassumption1)gives

𝐏𝐫​\(𝒙⊕I∈S\)⩾2​γand∑∅≠J⊊I𝐏𝐫​\(𝒙⊕J∈S\)⩽γ,\\mathbf\{Pr\}\(\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S\)\\geqslant 2\\gamma\\quad\\text\{and\}\\quad\\sum\_\{\\varnothing\\neq J\\subsetneq I\}\\mathbf\{Pr\}\(\{\\boldsymbol\{x\}\}^\{\\oplus J\}\\in S\)\\leqslant\\gamma,where the sum is empty if\|I\|=1\|I\|=1\. The union bound therefore gives

𝐏𝐫​\(𝒙⊕I∈S,𝒙⊕J∉S​for every​∅≠J⊊I\)⩾γ\.\\mathbf\{Pr\}\\left\(\{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S,\\ \{\\boldsymbol\{x\}\}^\{\\oplus J\}\\notin S\\text\{ for every \}\\varnothing\\neq J\\subsetneq I\\right\)\\geqslant\\gamma\.The events obtained by specifying𝒔I​\(𝒙\)=t\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=tpartition this minimal\-flip event\. Hence, for everyI∈ℱI\\in\\mathcal\{F\}, there is a sign patterntI∈\{±1\}It\_\{I\}\\in\\\{\\pm 1\\\}^\{I\}such that

𝐏𝐫​\(𝒔I​\(𝒙\)=tI,𝒙⊕I∈S,𝒙⊕J∉S​for every​∅≠J⊊I\)⩾γ2\|I\|\.\\mathbf\{Pr\}\\left\(\\boldsymbol\{s\}\_\{I\}\(\{\\boldsymbol\{x\}\}\)=t\_\{I\},\\ \{\\boldsymbol\{x\}\}^\{\\oplus I\}\\in S,\\ \{\\boldsymbol\{x\}\}^\{\\oplus J\}\\notin S\\text\{ for every \}\\varnothing\\neq J\\subsetneq I\\right\)\\geqslant\\frac\{\\gamma\}\{2^\{\|I\|\}\}\.By the definition of the canonical maximizersIs\_\{I\}preceding Assumption[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2), the paired event therefore satisfies

pI,sI⩾γ2\|I\|⩾γ2k=p0\.p\_\{I,s\_\{I\}\}\\geqslant\\frac\{\\gamma\}\{2^\{\|I\|\}\}\\geqslant\\frac\{\\gamma\}\{2^\{k\}\}=p\_\{0\}\.Letπ⋆\\pi\_\{\\star\}be the uniform distribution on\{\(I,sI\):I∈ℱ\}\\\{\(I,s\_\{I\}\):I\\in\\mathcal\{F\}\\\}\. Assumption[4\.2](https://arxiv.org/html/2607.22889#S4.Thmassumption2)gives

𝐄\(I,s\)∼π⋆​\[𝒘I,s​𝒘I,s𝖳\]=1\|ℱ\|​∑I∈ℱ𝒘I,sI​𝒘I,sI𝖳⪰λs​In\.\\mathbf\{E\}\_\{\(I,s\)\\sim\\pi\_\{\\star\}\}\\left\[\\boldsymbol\{w\}\_\{I,s\}\\boldsymbol\{w\}\_\{I,s\}^\{\\mathsf\{T\}\}\\right\]=\\frac\{1\}\{\|\\mathcal\{F\}\|\}\\sum\_\{I\\in\\mathcal\{F\}\}\\boldsymbol\{w\}\_\{I,s\_\{I\}\}\\boldsymbol\{w\}\_\{I,s\_\{I\}\}^\{\\mathsf\{T\}\}\\succeq\\lambda\_\{s\}I\_\{n\}\.Thus \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex55)\) holds withp0=γ/2kp\_\{0\}=\\gamma/2^\{k\}and design parameterλs\\lambda\_\{s\}\.

Set

η:=ϵ​λs2\.\\eta:=\\epsilon\\sqrt\{\\frac\{\\lambda\_\{s\}\}\{2\}\}\.Under the event of Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1), Lemma[C\.3](https://arxiv.org/html/2607.22889#A3.Thmlemma3)gives

‖𝒛^−𝒛‖2⩽η​2λs=ϵ\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}\\\|\_\{2\}\\leqslant\\eta\\sqrt\{\\frac\{2\}\{\\lambda\_\{s\}\}\}=\\epsilon\.
It remains to verify the sample bound\. Sinceη2=ϵ2​λs/2\\eta^\{2\}=\\epsilon^\{2\}\\lambda\_\{s\}/2,

e2​k​Rp0​η2=2​e2​k​Rp0​λs​ϵ2\.\\frac\{e^\{2kR\}\}\{p\_\{0\}\\eta^\{2\}\}=\\frac\{2e^\{2kR\}\}\{p\_\{0\}\\lambda\_\{s\}\\epsilon^\{2\}\}\.Moreover, taking traces in \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex55)\) gives

n​λs⩽𝐄\(I,s\)∼π⋆​‖𝒘I,s‖22=𝐄\(I,s\)∼π⋆​\|I\|⩽k⩽n\.n\\lambda\_\{s\}\\leqslant\\mathbf\{E\}\_\{\(I,s\)\\sim\\pi\_\{\\star\}\}\\\|\\boldsymbol\{w\}\_\{I,s\}\\\|\_\{2\}^\{2\}=\\mathbf\{E\}\_\{\(I,s\)\\sim\\pi\_\{\\star\}\}\|I\|\\leqslant k\\leqslant n\.Thusλs⩽1\\lambda\_\{s\}\\leqslant 1\. Because alsoϵ⩽1\\epsilon\\leqslant 1ande2​k​R⩾1e^\{2kR\}\\geqslant 1, the sample\-size condition in Theorem[4\.1](https://arxiv.org/html/2607.22889#S4.Thmtheorem1), for a sufficiently large universal constantCC, implies \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex62)\)\. The statistical claim follows from Lemma[C\.1](https://arxiv.org/html/2607.22889#A3.Thmlemma1)and Lemma[C\.3](https://arxiv.org/html/2607.22889#A3.Thmlemma3)\.

Finally, for each sample the learner queries𝟏​\{\(𝒙\(ℓ\)\)⊕J∈S\}\\mathbf\{1\}\\\{\(\{\\boldsymbol\{x\}\}^\{\(\\ell\)\}\)^\{\\oplus J\}\\in S\\\}once for every nonemptyJJwith\|J\|⩽k\|J\|\\leqslant kand caches the answers\. This uses exactly

N​∑r=1k\(nr\)N\\sum\_\{r=1\}^\{k\}\\binom\{n\}\{r\}membership queries\. The screening and likelihood calculations have sizeN​nO​\(k\)Nn^\{O\(k\)\}\. The feasibility problem \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\) has at mostk​\(2​n\)kk\(2n\)^\{k\}scalar weights and onen×nn\\times nsemidefinite constraint\. The hidden design satisfies the stronger inequality withλs​In\\lambda\_\{s\}I\_\{n\}, giving slackλs/2\\lambda\_\{s\}/2relative to \([C\.1](https://arxiv.org/html/2607.22889#A3.Ex59)\); hence a standard polynomial\-time semidefinite\-programming method can return a certified feasible solution to the required accuracy\. Weighted least squares is polynomial time as well\.

∎

## Appendix DOmitted Proofs of Section[5](https://arxiv.org/html/2607.22889#S5)

In this section, we prove an information\-theoretic lower bound for estimation under sparse truncation\. To this end, we introduce Assouad’s lemma, a key tool used extensively in statistical decision theory to prove minimax lower bounds for estimation\.

###### Lemma D\.1\(Assouad’s Lemma\[yu1997assouad\]\)\.

Let\{Pω:ω∈\{0,1\}B\}\\\{P\_\{\\omega\}:\\omega\\in\\\{0,1\\\}^\{B\}\\\}be a family of distributions indexed by the binary hypercube, and let\{θω:ω∈\{0,1\}B\}⊆Θ\\\{\\theta^\{\\omega\}:\\omega\\in\\\{0,1\\\}^\{B\}\\\}\\subseteq\\Thetabe the corresponding parameters\. Suppose that, for someρ\>0\\rho\>0and a pseudo\-metricddonΘ\\Theta,

d2​\(θω,θω′\)⩾ρ2​dH​\(ω,ω′\)for all​ω,ω′∈\{0,1\}B,d^\{2\}\(\\theta^\{\\omega\},\\theta^\{\\omega^\{\\prime\}\}\)\\geqslant\\rho^\{2\}d\_\{H\}\(\\omega,\\omega^\{\\prime\}\)\\qquad\\text\{for all \}\\omega,\\omega^\{\\prime\}\\in\\\{0,1\\\}^\{B\},wheredHd\_\{H\}denotes Hamming distance\. Then, for any estimatorθ^\\widehat\{\\theta\},

supω∈\{0,1\}B𝔼ω​d2​\(θ^,θω\)⩾ρ28​∑b=1B\(1−TV⁡\(Pω:b=0,Pω:b=1\)\),\\sup\_\{\\omega\\in\\\{0,1\\\}^\{B\}\}\\mathbb\{E\}\_\{\\omega\}d^\{2\}\(\\widehat\{\\theta\},\\theta^\{\\omega\}\)\\geqslant\\frac\{\\rho^\{2\}\}\{8\}\\sum\_\{b=1\}^\{B\}\\left\(1\-\\operatorname\{TV\}\\\!\\left\(P\_\{\\omega:b=0\},P\_\{\\omega:b=1\}\\right\)\\right\),wherePω:b=aP\_\{\\omega:b=a\}denotes the mixture distribution obtained by drawingω\\omegauniformly over\{0,1\}B\\\{0,1\\\}^\{B\}conditional onωb=a\\omega\_\{b\}=a\.

### D\.1Proof of Theorem[5\.1](https://arxiv.org/html/2607.22889#S5.Thmtheorem1)

###### Proof of Theorem[5\.1](https://arxiv.org/html/2607.22889#S5.Thmtheorem1)\.

Letv1:=𝟎2​k∈Vv\_\{1\}:=\\mathbf\{0\}^\{2k\}\\in Vandr:=2​v1−𝟏=−𝟏∈\{±1\}2​kr:=2v\_\{1\}\-\\mathbf\{1\}=\-\\mathbf\{1\}\\in\\\{\\pm 1\\\}^\{2k\}\. Set

η:=8​ϵn\.\\eta:=\\frac\{8\\epsilon\}\{\\sqrt\{n\}\}\.The assumed rangeϵ⩽R​n/16\\epsilon\\leqslant R\\sqrt\{n\}/16ensuresη⩽R/2\\eta\\leqslant R/2\. For each blockbb, define

𝒛b\(0\):=\(R−η\)​r,𝒛b\(1\):=R​r,Δ:=𝒛b\(1\)−𝒛b\(0\)=η​r\.\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}:=\(R\-\\eta\)r,\\qquad\\boldsymbol\{z\}\_\{b\}^\{\(1\)\}:=Rr,\\qquad\\Delta:=\\boldsymbol\{z\}\_\{b\}^\{\(1\)\}\-\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}=\\eta r\.Both parameters belong to\[−R,R\]2​k\[\-R,R\]^\{2k\}, and

‖Δ‖22=2​k​η2\.\\\|\\Delta\\\|\_\{2\}^\{2\}=2k\\eta^\{2\}\.
We first bound the KL divergence between the two one\-block conditional distributions\. Fort∈\[0,1\]t\\in\[0,1\], let𝒛b\(t\):=𝒛b\(0\)\+t​Δ\\boldsymbol\{z\}\_\{b\}^\{\(t\)\}:=\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}\+t\\Delta\. Everyvj∈V∖\{v1\}v\_\{j\}\\in V\\setminus\\\{v\_\{1\}\\\}has Hamming weight at leastkk\. Hence

𝒛b\(t\)⊤​\(v1−vj\)=\(R−η\+t​η\)​dH​\(v1,vj\)⩾k​R2\.\\boldsymbol\{z\}\_\{b\}^\{\(t\)\\top\}\(v\_\{1\}\-v\_\{j\}\)=\(R\-\\eta\+t\\eta\)d\_\{H\}\(v\_\{1\},v\_\{j\}\)\\geqslant\\frac\{kR\}\{2\}\.Comparing the mass ofvjv\_\{j\}to that ofv1v\_\{1\}gives

μ𝒛b\(t\)∣V​\(vj\)⩽exp⁡\(−k​R/2\)for all​j≠1,t∈\[0,1\]\.\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(t\)\}\\mid V\}\(v\_\{j\}\)\\leqslant\\exp\(\-kR/2\)\\qquad\\text\{for all \}j\\neq 1,\\ t\\in\[0,1\]\.Since the conditional law onVVis an exponential family, the integral form of Taylor’s theorem gives

DKL\(μ𝒛b\(0\)∣V∥μ𝒛b\(1\)∣V\)\\displaystyle D\_\{\\mathrm\{KL\}\}\\left\(\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}\\mid V\}\\middle\\\|\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(1\)\}\\mid V\}\\right\)=∫01\(1−t\)​𝐕𝐚𝐫μ𝒛b\(t\)∣V​\(Δ⊤​X\)​𝑑t\\displaystyle=\\int\_\{0\}^\{1\}\(1\-t\)\\mathbf\{Var\}\_\{\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(t\)\}\\mid V\}\}\(\\Delta^\{\\top\}X\)\\,dt⩽12​supt∈\[0,1\]𝐄μ𝒛b\(t\)∣V​\[\(Δ⊤​\(X−v1\)\)2\]\.\\displaystyle\\leqslant\\frac\{1\}\{2\}\\sup\_\{t\\in\[0,1\]\}\\mathbf\{E\}\_\{\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(t\)\}\\mid V\}\}\\left\[\(\\Delta^\{\\top\}\(X\-v\_\{1\}\)\)^\{2\}\\right\]\.There are three alternatives tov1v\_\{1\}, and for each of them\|Δ⊤​\(vj−v1\)\|⩽2​k​η\|\\Delta^\{\\top\}\(v\_\{j\}\-v\_\{1\}\)\|\\leqslant 2k\\eta\. Therefore

DKL\(μ𝒛b\(0\)∣V∥μ𝒛b\(1\)∣V\)⩽6η2k2e−k​R/2\.D\_\{\\mathrm\{KL\}\}\\left\(\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}\\mid V\}\\middle\\\|\\mu\_\{\\boldsymbol\{z\}\_\{b\}^\{\(1\)\}\\mid V\}\\right\)\\leqslant 6\\eta^\{2\}k^\{2\}e^\{\-kR/2\}\.The same calculation, with the interpolation traversed in the opposite direction, gives the identical bound for the reverse KL divergence\.

Now letB:=n/\(2​k\)B:=n/\(2k\)\. Forω∈\{0,1\}B\\omega\\in\\\{0,1\\\}^\{B\}, define

𝒛ω:=\(𝒛1\(ω1\),…,𝒛B\(ωB\)\),\\boldsymbol\{z\}^\{\\omega\}:=\\left\(\\boldsymbol\{z\}\_\{1\}^\{\(\\omega\_\{1\}\)\},\\ldots,\\boldsymbol\{z\}\_\{B\}^\{\(\\omega\_\{B\}\)\}\\right\),and letPωP\_\{\\omega\}be the corresponding conditional distribution onS=VBS=V^\{B\}\. The block\-product structure and \([D\.1](https://arxiv.org/html/2607.22889#A4.Ex107)\) imply that neighboring hypotheses satisfy

DKL\(Pω⊗N∥Pω⊕eb⊗N\)⩽6Nη2k2e−k​R/2\.D\_\{\\mathrm\{KL\}\}\\left\(P\_\{\\omega\}^\{\\otimes N\}\\middle\\\|P\_\{\\omega\\oplus e\_\{b\}\}^\{\\otimes N\}\\right\)\\leqslant 6N\\eta^\{2\}k^\{2\}e^\{\-kR/2\}\.Thus, if

N⩽c0​ek​R/2η2​k2N\\leqslant c\_\{0\}\\frac\{e^\{kR/2\}\}\{\\eta^\{2\}k^\{2\}\}for a sufficiently small universal constantc0\>0c\_\{0\}\>0, Pinsker’s inequality bounds the total variation distance in \([D\.1](https://arxiv.org/html/2607.22889#A4.Ex109)\) by1/41/4\. By convexity of total variation, the same bound holds between the two mixtures obtained by fixingωb=0\\omega\_\{b\}=0andωb=1\\omega\_\{b\}=1and averaging uniformly over the remaining bits\.

It remains to convert this testing obstruction into the claimed high\-probability estimation obstruction\. Given an arbitrary estimator𝒛^\\widehat\{\\boldsymbol\{z\}\}, defineω^b\\widehat\{\\omega\}\_\{b\}by choosing the closer of𝒛b\(0\)\\boldsymbol\{z\}\_\{b\}^\{\(0\)\}and𝒛b\(1\)\\boldsymbol\{z\}\_\{b\}^\{\(1\)\}to thebb\-th block of𝒛^\\widehat\{\\boldsymbol\{z\}\}\. The two\-point testing inequality and the preceding mixture\-TV bound imply, for uniformω\\omega,

𝐄ω​dH​\(ω^,ω\)⩾3​B8\.\\mathbf\{E\}\_\{\\omega\}d\_\{H\}\(\\widehat\{\\omega\},\\omega\)\\geqslant\\frac\{3B\}\{8\}\.SincedH​\(ω^,ω\)⩽Bd\_\{H\}\(\\widehat\{\\omega\},\\omega\)\\leqslant B, it follows that

𝐏𝐫ω​\(dH​\(ω^,ω\)⩾B8\)⩾27\.\\mathbf\{Pr\}\_\{\\omega\}\\left\(d\_\{H\}\(\\widehat\{\\omega\},\\omega\)\\geqslant\\frac\{B\}\{8\}\\right\)\\geqslant\\frac\{2\}\{7\}\.Whenever blockbbis decoded incorrectly, the triangle inequality and the nearest\-neighbor definition give

‖𝒛^b−𝒛b\(ωb\)‖2⩾12​‖Δ‖2\.\\\|\\widehat\{\\boldsymbol\{z\}\}\_\{b\}\-\\boldsymbol\{z\}\_\{b\}^\{\(\\omega\_\{b\}\)\}\\\|\_\{2\}\\geqslant\\frac\{1\}\{2\}\\\|\\Delta\\\|\_\{2\}\.Consequently, on the preceding event,

‖𝒛^−𝒛ω‖22⩾B8⋅‖Δ‖224=n​η232=2​ϵ2\.\\\|\\widehat\{\\boldsymbol\{z\}\}\-\\boldsymbol\{z\}^\{\\omega\}\\\|\_\{2\}^\{2\}\\geqslant\\frac\{B\}\{8\}\\cdot\\frac\{\\\|\\Delta\\\|\_\{2\}^\{2\}\}\{4\}=\\frac\{n\\eta^\{2\}\}\{32\}=2\\epsilon^\{2\}\.After averaging overω\\omega, there must therefore be at least oneω\\omegafor which the estimator has error greater thanϵ\\epsilonwith probability at least2/72/7\. In particular, uniform success probability0\.990\.99is impossible under \([D\.1](https://arxiv.org/html/2607.22889#A4.Ex110)\)\. Substitutingη2=64​ϵ2/n\\eta^\{2\}=64\\epsilon^\{2\}/ninto the negation of \([D\.1](https://arxiv.org/html/2607.22889#A4.Ex110)\) proves

N⩾c​n​ek​R/2k2​ϵ2N\\geqslant c\\frac\{ne^\{kR/2\}\}\{k^\{2\}\\epsilon^\{2\}\}for a universal constantc\>0c\>0\. ∎