{"id":"a4b0502b-9261-4ecb-acb6-d60d133b0052","arxiv_id":"2505.05819","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Learning junta distributions is computationally equivalent to LPN, and a new algorithm achieves near-optimal sample complexity O((k/epsilon^2)(2^k + log n)).","lead":"This paper shows that learning junta distributions, where a probability mass depends on only k of n variables, is computationally equivalent to learning parity functions with noise, a landmark hard problem. It also gives a new algorithm that learns such distributions with a near-optimal number of samples.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2 reuses the same m samples across adaptively chosen LearnFourier calls; Lemma 4.6 union-bounds over actual calls rather than over all possible selections, leaving the Fourier-estimation failure probability uncontrolled and the N subset of J* invariant unproven.","rationale":"The reader correctly identified adaptive sample reuse as the most fragile point, but the specific mechanism they named - the closeness tester - is actually safe. Lemma 4.3's estimator error is controlled by S_D(X), the empirical l1 distance to the target D, which is independent of the tested distribution Q|S. Therefore the tester's guarantee holds simultaneously for every Q, and the union bound over tester calls is not the issue. The real gap is the analogous reuse for LearnFourier. The algorithm selects S because the same empirical sample makes Q|S look far; then it estimates Fourier coefficients of P|S from that same sample. The conditional distribution of the sample given that S was selected can be badly tilted, and Lemma 4.4's fixed-S guarantee does not apply to that conditional distribution. Lemma 4.6 unions over the calls the algorithm happens to make, but a union bound over actual calls is only valid if the choice of S is independent of the failure event; here it is data-dependent. A correct proof would need either fresh samples for the Fourier step or a uniform bound over all k-subsets S. The latter appears to require an extra k log n factor on the 2^k term, which the claimed sample complexity does not include. This is a proof gap rather than a demonstrated counterexample; the algorithm may still be correct, and the rest of the paper's reductions appear structurally sound modulo typographical inconsistencies. The reader's CONDITIONAL verdict remains appropriate: the sample-optimality claim needs a repaired adaptive-analysis argument before the theorem is fully established.","tokens_in":1095,"tokens_out":1361,"duration_ms":432137,"concrete_test":"Recompute Lemma 4.6 with a uniform-convergence bound: for every k-subset S and every A subset of S, bound Pr(|(1/m) sum_{t<=m} 2^{-|S|} chi_A(x_t|S) - Phat|S(A)| > eps * 2^{-3k/2}) using the shared m samples, then union over all (n choose k) * 2^k events. If the required m is k * eps^{-2} * (2^k * (k log n + k)) rather than k * eps^{-2} * (2^k + log n), the adaptive LearnFourier call is not covered by the paper's sample bound; optionally, run a small instance (k=3, n=128) comparing the original algorithm with one that draws fresh samples for every LearnFourier call to confirm a discrepancy.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's identified weakness - sample reuse in the closeness tests - is largely mitigated: Lemma 4.3 proves |S_P(X) - ||P - D||_1| <= S_D(X), so the tester's error is uniform in the tested distribution P, even if P = Q|S is chosen adaptively from X. The genuinely unsupported reuse is in the Fourier-estimation step. In Algorithm 2, after Tester selects an S using the same m samples, LearnFourier(P|S) is run on those very samples. Lemma 4.4 certifies failure probability k^{-2} only for any fixed S under the original i.i.d. distribution; it does not certify the conditional distribution of the sample given the event that S was selected. That event is correlated with the empirical marginal on S - it is precisely the event that the same data make Q|S look far - and therefore with the empirical Fourier coefficients. Lemma 4.6 unions over the at most k calls actually made instead of over all candidate S, so the selection bias is not charged. A uniform bound over all S in the k-subsets of [n] and A subset of S would require a Hoeffding tail with exponent roughly m * eps^2 * 2^{-k} to dominate k log n + k; the theorem's m = k * eps^{-2} * (2^k + log n) provides k + k log n * 2^{-k}, which is too small when 2^k is not much larger than log n. Hence Lemmas 4.7-4.10, which rely on LearnFourier never failing on the selected S, do not follow from the stated sample complexity.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning k-junta distributions over {±1}^n from i.i.d. samples. It claims two main results. First, the computational complexity of learning k-junta distributions is equal, up to poly(2^k,n) factors, to that of learning k-parities with noise at rate 1/2 - 2^{-O(k)}; the proof proceeds by reducing LPN to LJD via a filtering construction and LJD to LPN through an intermediate class of noisy parity distributions. Second, it presents an algorithm that properly learns k-junta distributions to TV error ε using O(k ε^{-2}(2^k + log n)) samples and O(min(2^n,n^k) · k ε^{-2}(2^k + log n)) time, based on a high-confidence tolerant identity tester that pays additively in log(1/δ) and on a Fourier-coefficient learning subroutine applied to marginals. The sample complexity is claimed to be optimal up to polylogarithmic factors, matching the lower bound of Chen et al. [15].","tokens_in":19824,"tokens_out":28256,"duration_ms":297661,"significance":"If the proofs are completed, Theorem 1 is a significant conceptual contribution: it ties the complexity of junta distribution learning to LPN, a central computational learning assumption, and strengthens the earlier one-way reduction of [1] into a two-way equivalence. The algorithmic result would improve the sample complexity of [19] by replacing the multiplicative k log n term with k + log n, and the additive-log high-confidence tester is an elegant and potentially reusable ingredient. The paper is careful in setting up the evaluator model and the reductions are genuine two-way reductions with no circularity. However, as written, the proof of Theorem 2 has a load-bearing gap concerning the reuse of samples for adaptively chosen Fourier-learning calls, and Lemma 3.12 contains incorrect formulas. These issues need to be resolved before the results are fully established.","major_comments":[{"comment":"Lemma 4.6 does not control the failure probability of LearnFourier in Algorithm 2. The m samples are drawn once, and the set S on which LearnFourier(P|S) is run is selected by Tester from these same samples. Lemma 4.4 guarantees accuracy only for i.i.d. samples from a fixed distribution P|S; conditioned on the event that Tester selected S, the empirical marginal on S is biased, and the conditional failure probability of LearnFourier need not be k^{-2}. The union bound in Lemma 4.6 over the at most k calls actually made does not charge the exponentially many S that could have been selected. Lemmas 4.7-4.10 all invoke this unconditional success event E, so Theorem 2 is not established by the current argument. A valid repair would be either to use fresh samples for every LearnFourier call and include the resulting sample cost, or to prove a uniform-convergence statement over all candidate S; the latter would require a tail exponent roughly m ε^2 2^{-k} exceeding k log n + k, while the stated m = O(k ε^{-2}(2^k + log n)) provides only k + k log n / 2^k, which is insufficient when 2^k is not much larger than log n. The paper should supply one of these arguments explicitly.","section":"Section 4.2, Lemma 4.6 and Algorithm 2"},{"comment":"Lemma 3.12 contains incorrect formulas for the filtered distribution. Conditioning on y=1 in the resampling procedure yields D = (1-2η)P + 2η U_n, not D = (1-2η)/(1+2η) P + 4η/(1+2η) U_n. Consequently the stated Fourier coefficients are also inconsistent: for S nonempty one should have \\hat D(H) = 2^{-n} and \\hat D(S) = (1-2η)2^{-n}; the bullet '2η, if A=H' is incompatible with \\hat D(H)=2^{-n} for any probability distribution. The subsequent rounding argument uses the correct PMF values, so the error is repairable, but the lemma as written is internally inconsistent and should be corrected before the proof of Theorem 1 is accepted.","section":"Section 3.3, Lemma 3.12"}],"minor_comments":[{"comment":"In the proof of Lemma 4.3, the sentence explaining Equation (3) says the concave function D ↦ Σ_i sqrt(D_i) is minimized at the uniform distribution; it is actually maximized there. The needed bound follows from Cauchy-Schwarz. Also, the bounded-differences constant is 2/m, not 1/m, since changing one sample can move one unit of mass between two histogram bins. These corrections do not change the stated sample complexity, but the proof should be fixed.","section":"Section 4.1, Lemma 4.3"},{"comment":"The statement of Lemma 4.4 promises sample complexity O(ε^{-2}(k + log δ^{-1})), but the proof takes m = O(ε^{-2} 2^k (k + log δ^{-1})). The displayed m is looser than necessary; the stated bound is achievable by applying Hoeffding to the average of χ_J with error ε and union-bounding over the 2^k coefficients. The proof should be aligned with the statement, since Algorithm 2 relies on the stated bound.","section":"Section 4.2, Lemma 4.4"},{"comment":"There are several small notational and typographical issues. In Algorithm 1, the comment that A is 'PAC if its input has noise of rate 1 - O(2^{-k/2})' should presumably read '1/2 - O(2^{-k/2})'. In Lemma 4.4's proof, 'for each J⊆{±1}^k' should be 'for each J⊆[k]'. In the time-complexity discussion of Algorithm 2, the per-call running time of Tester and of the enumeration over all S is not specified; the time bound in Theorem 2 should state these costs explicitly.","section":"Algorithm 1 and Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid conceptual core and the reductions are interesting, but the proof of Theorem 2 currently has a genuine gap in the treatment of adaptively reused samples, and Lemma 3.12 contains false formulas. Both appear repairable within the scope of the manuscript, so I recommend major revision rather than rejection. A careful proofreading pass is also needed for the smaller technical inaccuracies in Lemmas 4.3 and 4.4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a serious paper and the main conceptual result—LJD is computationally equivalent to LPN up to poly(2^k,n) factors—looks right and is worth citing. The sample-optimal algorithm is plausible, but as written the proof has a genuine hole in the reuse of the same m samples for the adaptive Fourier-estimation calls. I would not take Theorem 2's sample complexity as proven yet.\n\nWhat's new: the two-way reduction is new. The LPN-to-LJD direction is a clean rejection-sampling trick, and the LJD-to-LPN direction via noisy-parity distillation reuses Feldman et al.'s noise injection plus a coupon-collector search. The algorithm's improvement from 2^k·log n to 2^k + log n is a real contribution, and the high-confidence identity tester in Lemma 4.3 is a nice adaptation of the Diakonikolas et al. tester, paying only additive log(1/δ).\n\nSoft spots. Lemma 3.12 has an incorrect mixture coefficient—the denominator 1+2η does not match the rejection sampler—and the Fourier table lists the H coefficient as 2η·2^{-n} instead of 2^{-n}. These look like fixable algebra slips, not a broken reduction. Lemma 4.3 says the concave sum ∑√p_i is minimized at the uniform distribution; it is maximized there. The McDiarmid Lipschitz constant should be 2/m, not 1/m. Both are minor, because the desired bound still holds after the obvious correction.\n\nThe real problem is sample reuse in Algorithm 2. The closeness tester is fine: Lemma 4.3's error is uniform in the tested distribution, so the adaptive choice of S does not hurt the tester. But LearnFourier(P|S) is run on the same samples that were used to select S as \"far,\" and Lemma 4.4 only certifies failure probability for a fixed S under the original i.i.d. measure. Lemma 4.6 unions over the calls actually made, not over all possible S, so it does not charge the selection bias. A uniform bound over all k-subsets would need m·ε²·2^{-k} ≳ k·log n, while the claimed m = k·ε^{-2}(2^k + log n) gives only about k + k·log n / 2^k, which is too small when 2^k is not much larger than log n. Since Lemmas 4.7–4.10 all rely on LearnFourier never failing on the selected S, this gap is load-bearing. It may be repairable—fresh samples per iteration, or a more careful uniform-convergence argument—but the version I read does not establish Theorem 2.\n\nCitation pattern looks fine: Feldman et al. and Diakonikolas et al. get proper credit. This paper is for anyone working on junta learning, LPN hardness, or sample-optimal distribution learning. The LPN equivalence alone merits a serious referee. I would send it out, with instructions to fix the algebra slips and either fix or weaken the sample-complexity claim.","headline":"The LJD/LPN equivalence is new and likely correct, but the paper's sample-optimality proof has a real gap in the adaptive reuse of samples for LearnFourier.","tokens_in":20323,"tokens_out":8209,"would_cite":true,"duration_ms":86526,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Learning junta distributions is computationally equivalent to learning noisy parities, and the paper gives a nearly sample-optimal learner.","keywords":["junta distributions","learning parities with noise","LPN","Fourier analysis of Boolean functions","distribution learning","sample complexity","tolerant identity testing","computational equivalence"],"falsifier":"Simulate Algorithm 2 on the uniform distribution over $\\{\\pm1\\}^{100}$ with $k=2$ and $\\varepsilon=0.1$, using the prescribed $m = O(k\\varepsilon^{-2}(2^k+\\log n))$ samples; because the true distribution is uniform, the tester should return 'close' for every size-$k$ marginal, and the analysis allows total failure probability $o(1)$. If the maximum over the $k n^k$ tester calls of the empirical $\\ell_1$ distance to the uniform marginal exceeds the 'far' threshold with probability noticeably larger than the union-bound value, then reusing one sample batch across adaptively chosen tests is the cause and Lemma 4.6's coverage of the algorithm is incomplete.","tokens_in":1801,"feed_emoji":"🎲","tokens_out":5951,"duration_ms":179957,"temperature":0.7,"pith_summary":"This paper studies distributions on the Boolean cube whose probability mass depends on at most $k$ of the $n$ coordinates. It proves that learning such $k$-junta distributions from independent samples is computationally equivalent, up to factors polynomial in $2^k$ and $n$, to learning $k$-parity functions under the uniform distribution with noise rate $\\eta = 1/2 - 2^{-O(k)}$, the well-known LPN problem. It also designs a learner using $O(k\\varepsilon^{-2}(2^k+\\log n))$ samples and running in $O(\\min(2^n,n^k)\\cdot k\\varepsilon^{-2}(2^k+\\log n))$ time, which matches the known statistical lower bound up to polylogarithmic factors. Together these results mean the new algorithm cannot be substantially improved, in samples or runtime, unless there is a breakthrough for noisy parity learning.","feed_headline":"Junta distributions are as hard as noisy parity learning","feed_subtitle":"A nearly sample-optimal learner matches the lower bound; only an LPN breakthrough could improve it.","key_machinery":"The argument runs through the Fourier transform on $\\{\\pm1\\}^n$: for a junta distribution, the probability mass function is itself a junta function, so its Fourier coefficients are supported on subsets of the $k$ relevant variables. The load-bearing identity is the noise-injection formula $D_A(x) = \\mathbb{E}_{p}[D(x \\oplus Ap)]$, which, for a random matrix $A$, survives with probability about $2^{-k}$ as a noisy parity distribution with exactly one non-empty Fourier coefficient alive. On the algorithmic side, the key mechanism is a tolerant identity tester that estimates $\\ell_1$ distance by the empirical histogram's $\\ell_1$ deviation from the candidate distribution and, via a Bernstein-form bounded-differences inequality, pays only an additive $\\log(1/\\delta)$ samples for high confidence; this lets the learner reuse one batch of samples across $k n^k$ tester calls without a multiplicative $\\log n$ penalty.","core_discovery":"The central discovery is that learning $k$-junta distributions with sample access has exactly the same computational difficulty, up to $\\mathrm{poly}(2^k,n)$ factors, as learning $k$-parities with noise rate $\\eta = 1/2 - 2^{-O(k)}$. The proof supplies explicit reductions in both directions: accepting only samples with label $+1$ converts noisy parity samples into a junta distribution whose Fourier coefficients reveal the parity, while a random linear noise-injection operator $D_A(x) = \\mathbb{E}_{p}[D(x \\oplus Ap)]$ collapses all but one non-zero Fourier coefficient of a junta distribution, producing a noisy parity distribution that a parity learner can handle. A coupon-collector loop then recovers all heavy Fourier coefficients. The second result is an algorithm that improves the sample bound from $2^k\\log n$ to $2^k+\\log n$ while keeping $n^k$-type time, using a high-confidence tolerant identity tester whose sample cost scales additively rather than multiplicatively in $\\log(1/\\delta)$.","pith_inferences":["The noise-injection reduction uses only the bound $2^k$ on the number of non-zero Fourier coefficients, so it should extend to any class of distributions over $\\{\\pm1\\}^n$ whose probability mass functions have at most $2^k$ non-zero Fourier coefficients, not just junta PMFs.","A natural extension would be to learn junta distributions with respect to a non-uniform base distribution; the Fourier basis changes to the characters of that base distribution, but the noise-injection identity and the additive-log tester appear to survive.","The computational equivalence suggests that other structured-distribution learning problems, such as testing junta truncations or low-degree truncations, could be reduced to LJD and thereby inherit LPN hardness, offering a new route to conditional lower bounds in distribution testing."],"forward_implications":["Any junta-distribution learner running in time substantially below $n^k$ would translate, through the reductions, into a new algorithm for very noisy parity learning; Theorem 1 therefore transfers the conjectured hardness of LPN to LJD.","The sample complexity $O(k\\varepsilon^{-2}(2^k+\\log n))$ meets the known lower bound $\\Omega(\\varepsilon^{-2}(2^k+\\log(n/k)))$ up to polylogarithmic factors, essentially closing the statistical question for junta distributions.","For $k = \\log\\log n$, the improvement from $2^k\\log n$ to $2^k+\\log n$ samples is a quadratic reduction in sample complexity.","The mutual reductions connect distribution learning to the LPN literature: future progress on sparse LPN algorithms transfers to junta-distribution learning, and hardness evidence against LPN applies to LJD as well."],"supporting_citations":[{"why":"introduced the learning junta distributions problem, gave the cover-method baseline, and proved the reduction from junta-function learning that motivates conditional hardness.","marker":"[1]"},{"why":"previous algorithm with roughly $2^k\\log n$ samples and thresholded Fourier coefficients, which this work improves to $2^k+\\log n$.","marker":"[19]"},{"why":"supplied the $\\Omega(\\varepsilon^{-2}(2^k+\\log(n/k)))$ statistical lower bound that the new algorithm matches up to polylog factors.","marker":"[15]"},{"why":"provided the random noise-injection technique and the reductions involving noisy parities that the LJD-to-LPN direction builds on.","marker":"[21]"},{"why":"supplies the low-degree Fourier algorithm used to estimate coefficients on small marginals over $\\{\\pm1\\}^k$.","marker":"[31]"},{"why":"sample-optimal identity testing with high probability, whose empirical $\\ell_1$ estimator the tolerant tester imitates.","marker":"[18]"},{"why":"supplies the Bernstein-form bounded-differences inequality used to prove concentration of the empirical $\\ell_1$ estimator in the tester.","marker":"[38]"}],"fun_headline_variants":["Junta learning meets LPN: same hardness, near-optimal samples","Optimal sample complexity for juntas, but LPN wall remains","Junta distributions: match LPN hardness, cut sample cost","Learning juntas: nearly sample-optimal, computationally tied to LPN","Junta learning: near-optimal samples, LPN-hard to improve"],"cache_read_input_tokens":22400,"weakest_assumption_plain":"The algorithm reuses the same $m$ samples for all closeness tests and Fourier estimates, while the tester's failure bound is proven for a fixed candidate distribution; the paper does not supply a uniform-convergence or net argument covering the candidate distributions $Q$ that the algorithm constructs adaptively from those same samples.","fun_headline_variants_meta":{"raw":{"variants":["Junta learning meets LPN: same hardness, near-optimal samples","Optimal sample complexity for juntas, but LPN wall remains","Junta distributions: match LPN hardness, cut sample cost","Learning juntas: nearly sample-optimal, computationally tied to LPN","Junta learning: near-optimal samples, LPN-hard to improve"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2885,"prompt_tokens":895,"completion_tokens":1990,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":1897}},"tokens_in":511,"tokens_out":1990,"duration_ms":14345,"temperature":1.0,"reasoning_tokens":1897,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:58:23.510598+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 2 on the uniform distribution over $\\{\\pm1\\}^{100}$ with $k=2$ and $\\varepsilon=0.1$, using the prescribed $m = O(k\\varepsilon^{-2}(2^k+\\log n))$ samples; because the true distribution is uniform, the tester should return 'close' for every size-$k$ marginal, and the analysis allows total failure probability $o(1)$. If the maximum over the $k n^k$ tester calls of the empirical $\\ell_1$ distance to the uniform marginal exceeds the 'far' threshold with probability noticeably larger than the union-bound value, then reusing one sample batch across adaptively chosen tests is the cause and Lemma 4.6's coverage of the algorithm is incomplete.","supporting_citations":[{"cited_title":"Learning and testing junta distri- butions","cited_arxiv_id":null,"evidence_quote":"introduced the learning junta distributions problem, gave the cover-method baseline, and proved the reduction from junta-function learning that motivates conditional hardness."},{"cited_title":"Learning and testing junta distributions with sub cube conditioning","cited_arxiv_id":null,"evidence_quote":"supplied the $\\Omega(\\varepsilon^{-2}(2^k+\\log(n/k)))$ statistical lower bound that the new algorithm matches up to polylog factors."},{"cited_title":"New results for learning noisy parities and halfspaces","cited_arxiv_id":null,"evidence_quote":"provided the random noise-injection technique and the reductions involving noisy parities that the LJD-to-LPN direction builds on."},{"cited_title":"Constant depth circuits, Fourier trans- form, and learnability","cited_arxiv_id":null,"evidence_quote":"supplies the low-degree Fourier algorithm used to estimate coefficients on small marginals over $\\{\\pm1\\}^k$."},{"cited_title":"Sample-optimal identity testing with high probability","cited_arxiv_id":null,"evidence_quote":"sample-optimal identity testing with high probability, whose empirical $\\ell_1$ estimator the tolerant tester imitates."},{"cited_title":"McDiarmid’s inequalities of Bernstein and Bennett forms","cited_arxiv_id":null,"evidence_quote":"supplies the Bernstein-form bounded-differences inequality used to prove concentration of the empirical $\\ell_1$ estimator in the tester."}],"review_version":1}