Learning from satisfying assignments under continuous distributions

Anindya De; Cl\'ement L. Canonne; Rocco A. Servedio

arxiv: 1907.01619 · v1 · pith:BAWYVS6Gnew · submitted 2019-07-02 · 💻 cs.DS · cs.CC· cs.LG

Learning from satisfying assignments under continuous distributions

Cl\'ement L. Canonne , Anindya De , Rocco A. Servedio This is my paper

Pith reviewed 2026-05-25 10:28 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.LG

keywords learning theorypolynomial threshold functionslog-concave distributionsGaussian distributionssatisfying assignmentscontinuous distributionscomputational learning

0 comments

The pith

Learning from satisfying assignments of PTFs is efficient for degree-1 under log-concave D but not degree-2, and for degree-2 under Gaussian D but not degree-4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends learning distributions over satisfying assignments of low-complexity functions from the Boolean cube to continuous real space. A known background distribution D is restricted to the set where an unknown low-degree polynomial threshold function f equals 1, and the learner must output a close approximation to this restricted distribution in total variation distance. When D is log-concave the problem admits an efficient algorithm for linear threshold functions but is hard for degree-2 PTFs. When D is Gaussian the efficient regime extends to degree-2 PTFs but hardness appears at degree-4. The contrast shows that both the algebraic degree of f and the analytic properties of D control learnability.

Core claim

When the background distribution D is log-concave, there is an efficient algorithm that learns the restriction of D to the satisfying assignments of any unknown degree-1 PTF, yet no such algorithm exists for degree-2 PTFs under standard cryptographic assumptions. In contrast, when D is a standard Gaussian, the problem is efficiently solvable for degree-2 PTFs but hard for degree-4 PTFs, again under cryptographic assumptions on secure signature schemes.

What carries the argument

Polynomial threshold functions (PTFs) of low degree, together with the geometric or concentration properties of the background distribution D (log-concavity versus Gaussianity), used both to construct learners for the low-degree cases and to reduce from cryptographic problems for the hardness cases.

If this is right

Under any log-concave background, linear threshold functions can be recovered from their satisfying assignments in polynomial time.
Under the same log-concave backgrounds, quadratic PTFs cannot be recovered efficiently unless the underlying signature schemes are insecure.
Under a Gaussian background, quadratic PTFs become efficiently recoverable while degree-4 PTFs remain hard under the same cryptographic assumptions.
The learnable degree threshold therefore jumps when the background distribution changes from log-concave to Gaussian.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same degree-dependent transition may appear for other background families that interpolate between log-concave and Gaussian measures.
The results suggest testing whether uniform distributions over convex bodies behave like log-concave distributions for this learning task.
If the cryptographic assumptions are eventually falsified, the hardness side of the dichotomy would need to be re-established by other means.

Load-bearing premise

The hardness claims for higher-degree PTFs rest on the assumption that certain digital signature schemes remain secure.

What would settle it

An unconditional polynomial-time algorithm that approximates the restriction of a log-concave distribution to the satisfying assignments of an arbitrary degree-2 PTF, or a proof of hardness that does not rely on signature-scheme security, would decide the boundary between tractable and intractable degrees.

read the original abstract

What kinds of functions are learnable from their satisfying assignments? Motivated by this simple question, we extend the framework of De, Diakonikolas, and Servedio [DDS15], which studied the learnability of probability distributions over $\{0,1\}^n$ defined by the set of satisfying assignments to "low-complexity" Boolean functions, to Boolean-valued functions defined over continuous domains. In our learning scenario there is a known "background distribution" $\mathcal{D}$ over $\mathbb{R}^n$ (such as a known normal distribution or a known log-concave distribution) and the learner is given i.i.d. samples drawn from a target distribution $\mathcal{D}_f$, where $\mathcal{D}_f$ is $\mathcal{D}$ restricted to the satisfying assignments of an unknown low-complexity Boolean-valued function $f$. The problem is to learn an approximation $\mathcal{D}'$ of the target distribution $\mathcal{D}_f$ which has small error as measured in total variation distance. We give a range of efficient algorithms and hardness results for this problem, focusing on the case when $f$ is a low-degree polynomial threshold function (PTF). When the background distribution $\mathcal{D}$ is log-concave, we show that this learning problem is efficiently solvable for degree-1 PTFs (i.e.,~linear threshold functions) but not for degree-2 PTFs. In contrast, when $\mathcal{D}$ is a normal distribution, we show that this learning problem is efficiently solvable for degree-2 PTFs but not for degree-4 PTFs. Our hardness results rely on standard assumptions about secure signature schemes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly extends the discrete satisfying-assignments learning model to continuous domains and pins down degree thresholds that flip between log-concave and Gaussian backgrounds.

read the letter

The central contribution is the degree cutoffs: under log-concave backgrounds degree-1 PTFs are efficiently learnable while degree-2 are not, and under Gaussians the threshold moves to degree-2 easy versus degree-4 hard. This is not a trivial lift of the earlier discrete work; the continuous setting requires fresh analysis for both the algorithms and the reductions. The algorithms appear to use standard techniques adapted to the background measure, and the hardness rests on established signature-scheme assumptions rather than ad-hoc fitting. That contrast between the two background families is the part that feels genuinely new and worth knowing. The paper is short on unconditional hardness, which is a limitation but an honest one given the state of the field. The crypto assumptions are standard and clearly flagged, so the intractability claims are appropriately caveated rather than overstated. No obvious circularity or parameter-fitting shows up in the abstract or the stated results. The work sits squarely in distribution learning and computational learning theory. Readers who already follow the discrete results or who care about PTFs over continuous measures will get direct value; outsiders will find the setup narrow. The claims are specific enough and the extension non-trivial enough that it should go to referees rather than desk rejection. I would bring it to a reading group if the group already covers learning distributions, otherwise probably not. I would not cite it in my own work unless I were actively working in this exact corner.

Referee Report

0 major / 2 minor

Summary. The paper extends the DDS15 framework for learning distributions over satisfying assignments of low-complexity Boolean functions from the Boolean hypercube to continuous domains. Given a known background distribution D (log-concave or Gaussian) over R^n, the learner receives i.i.d. samples from D_f (D restricted to the satisfying assignments of an unknown low-degree PTF f) and must output a distribution D' with small total variation distance to D_f. The central claims are that the problem is efficiently solvable for degree-1 PTFs but not degree-2 PTFs when D is log-concave, while it is efficiently solvable for degree-2 PTFs but not degree-4 PTFs when D is Gaussian; hardness results rely on standard cryptographic assumptions on secure signature schemes.

Significance. If the algorithmic and hardness results hold, the work provides a clean separation between learnability thresholds for PTFs under different continuous background distributions, extending prior discrete-domain results with new analysis for the continuous case. The paper ships explicit efficient algorithms for the solvable cases (degree-1 under log-concave, degree-2 under Gaussian) together with matching hardness under standard assumptions; these are falsifiable predictions conditional on the cryptographic hypotheses and constitute a clear contribution to the study of distribution learning from restricted support.

minor comments (2)

[Theorem 1.1 and Theorem 1.3] The abstract and introduction state the contrast between log-concave and Gaussian cases clearly, but the precise sample complexity and runtime bounds for the positive results (e.g., the dependence on dimension n and degree) should be stated explicitly in the theorem statements rather than only in the body of the proofs.
[Section 2] Notation for the total variation distance and the definition of D_f could be introduced once in a preliminary section and then used consistently; several early sections repeat the definition inline.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, accurate summary of our results, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper extends the discrete framework of [DDS15] to continuous domains with new algorithms for degree-1 PTFs under log-concave D and degree-2 PTFs under Gaussian D, plus hardness results for higher degrees conditional on external cryptographic assumptions about secure signature schemes. These results rely on fresh analysis for the continuous setting rather than any reduction to fitted parameters, self-definitions, or load-bearing self-citations. The [DDS15] reference provides background context but is not invoked to justify uniqueness or force the central claims. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the background distribution belonging to the log-concave or Gaussian families and on standard cryptographic assumptions for the hardness side; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard assumptions about secure signature schemes
Invoked to establish hardness for degree-2 (log-concave) and degree-4 (Gaussian) cases.

pith-pipeline@v0.9.0 · 5844 in / 1161 out tokens · 34700 ms · 2026-05-25T10:28:43.904888+00:00 · methodology

Learning from satisfying assignments under continuous distributions

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)