A question about access to data
A statistical-query learner asks for approximate averages, such as the correlation between a proposed rule and a label. It does not receive the individual examples used to form those averages. Is that restriction important? Parity functions provide a sharp test. An individual labeled example is a linear equation over the two-element field, but an approximate average can conceal the relevant parity among many mutually orthogonal possibilities.
The result below is an information-access lower bound for a specified statistical-query model. It is not a cryptographic hardness theorem and it does not say that parity is hard to learn from ordinary examples. In fact, the final comparison gives an efficient exact algorithm from labeled examples. The lower bound also depends on the query tolerance: allowing extremely accurate answers changes what a query can reveal.
Model and notation
Definition 7.1.1
(Uniform parity targets)
Fix an integer , let , and draw uniformly from . For each subset define
The unknown target is one of these parities and the label is exactly . A classifier is any function , not necessarily a parity. Its population error for target is .
The input distribution is public and fixed; only is unknown. We include the empty parity, the constant-one function, to obtain all characters. Inputs and labels are signs here. Later, when solving linear equations, we will explicitly convert them to bits. The uniform distribution is essential to the orthogonality calculation; no conclusion for arbitrary input distributions is being asserted.
Definition 7.1.2
(Statistical-query access and tolerance)
A query is any function . For a fixed tolerance , an oracle for target may answer with any real number satisfying
The learner knows , the uniform marginal and ; it may choose each query using all previous answers. Each answer costs one query; the bound below is a worst-case cap on every run and every random seed, not an expected query count. A guarantee must hold for every target and every sequence of answers satisfying the tolerance condition, including answers selected adversarially. The learner receives no individual labeled examples in this model. We impose no computational restriction on queries or on the final classifier: the bound counts queries alone.
For an advantage , achieving error at most means doing better than random guessing by at least . With ,
Thus such accuracy requires correlation at least . This identity concerns the uniform population distribution, not the performance of on a particular finite sample.
Orthogonality limits one query
Theorem 7.1.3
(Parity characters and a query-counting lemma)
Under the uniform distribution,
For any query , define
The target- expectation is . At most targets have an expectation farther than from the common value .
Proof
(Orthogonality and Bessel's inequality)
If , the product is the parity of the nonempty symmetric difference . Pick one coordinate in that difference. Its independent uniform sign has mean zero, so the whole product has mean zero. If , the product is identically one.
The functions are an orthonormal family under . For any real , finite-dimensional Bessel's inequality gives
For the query above, , since each of the two query values lies in . Therefore the sum of squared correlations is at most one. If more than of them had magnitude strictly greater than , their squared sum would exceed one. This proves the count.
To see the expectation identity, write for . Substituting gives the result. The common answer is a real number determined by the query and the known uniform marginal; it does not depend on the target.
The same orthogonality also restricts any one final classifier. Since , Bessel's inequality implies
Consequently at most target parities can have . This is a statement about one fixed ; the proof below must also account for the learner choosing after receiving answers.
Concept lensAnalytic
A query reads Fourier coefficients on the cube
Under target the only target-dependent part of the answer is , the coefficient of in the parity basis of functions on . These functions are a basis, so Bessel's inequality is an equality, : a bounded query has total spectral weight at most one, so at most coefficients exceed in absolute value.
An adversarial-answer lower bound
Theorem 7.1.4
(Deterministic finite-query lower bound)
Suppose a deterministic learner makes at most queries of tolerance and must output a classifier with error at most for every target and every tolerance-valid oracle. Then
If the right-hand side is negative, the inequality is merely vacuous. The count is an integer, so a positive noninteger lower bound can be rounded up.
Proof
(A common transcript leaves many targets possible)
Run the deterministic learner against a reference oracle that answers each query with its target-independent value . This fixes a complete sequence of at most queries, their reference answers and one final classifier . The reference oracle is a device for constructing a transcript; its answers need not be valid for every target.
For each query on that transcript, the lemma says that at most targets make the reference answer invalid. Discard the union of those exceptional target sets. At least targets remain. For any one of them, every reference answer is tolerance-valid. Because the learner is deterministic, an oracle giving those answers causes exactly the same subsequent queries and the same output ; adaptivity does not create a different transcript along this path.
The final-classifier bound says has the required advantage for at most targets. If , at least one remaining target both admits the reference transcript and makes fail. This contradicts the required guarantee. Rearranging the negation of that strict inequality proves the theorem.
Proof X-ray
Where adaptivity is handled
The proof does not assume the learner fixes all queries in advance. It follows the one transcript in which every answer is the common baseline. Only after this adaptive transcript is fixed does it count the targets for which every answer on that path is valid. Those targets are indistinguishable to this particular run, even though other answer sequences could lead the algorithm elsewhere.
There is also a randomized version. Suppose success must have probability at least over the learner's random choices, for every target and every valid oracle, where . Then necessarily
Here is the additional argument. For each target use one fixed oracle policy: on query , return if it is within tolerance of the true answer, and otherwise return the exact expectation. The policy is valid for every query. Fix the learner's random seed and compare its run with the baseline transcript for that seed. Under a uniformly random target, the chance of ever deviating from the baseline is at most by the union bound along that transcript. If there is no deviation, the output is fixed and is successful for at most targets. Averaging over random seeds gives average success probability at most
If the claimed guarantee holds for every target against this valid policy, its average must be at least . Rearranging gives the bound. The adversarial policy is fixed before the random seed is drawn; it need not know the seed. This is not a claim that every possible oracle answer is uninformative: exact answers may carry more information than the tolerance guarantee requires.
Worked examples
Worked example 7.1.5
(A single correlation query)
Ask for a fixed subset . Its expectation is one if and zero otherwise. With tolerance below , this query tests that one candidate. It does not automatically reveal which of the other candidates is correct. The lower bound handles much more general bounded queries than this simple test, including queries chosen adaptively.
Worked example 7.1.6
(A finite numerical lower bound)
Take , and . There are targets. A deterministic learner guaranteed error at most for every target and valid oracle must make at least
queries. This is a lower bound, not an algorithm achieving the same number. For fixed positive and , the leading term grows exponentially in . If decreases with , the displayed formula must be evaluated with that dependence rather than called exponential automatically.
Worked example 7.1.7
(Individual labeled examples reveal linear equations)
Write , , and let when and zero otherwise. A labeled example gives
With independent uniform inputs, the matrix of rows has a nonzero kernel vector with probability at most : each fixed nonzero vector is orthogonal to one uniform row with probability , independently across rows, and there are such vectors. Thus makes the probability of nonunique recovery less than , for . Gaussian elimination then recovers exactly on the full-rank event, in polynomial time.
This comparison changes the information supplied to the learner. It does not turn a statistical-query lower bound into a computational hardness claim for the ordinary-example model.
Counterexample mode
A large class alone does not prove an SQ lower bound
The parity targets are numerous, but cardinality alone is not the proof. A single exact real answer can encode many possibilities in some models, and a query can involve all coordinates at once. The lower bound uses the particular uniform-distribution orthogonality, the bounded range of each query, and the oracle's freedom to return any answer within tolerance. Remove one of those conditions and this calculation must be reconsidered.
Common mistakes
Common mistake
(Assuming the oracle always returns the exact mean)
Exact expectations are allowed answers, but the statistical-query guarantee must tolerate every answer within . An algorithm that succeeds only when an oracle happens to reveal exact values does not meet the stated model. Conversely, this adversarial-tolerance lower bound is not a lower bound for an oracle required to return exact expectations.
Common mistake
(Ignoring how tolerance scales)
The deterministic bound contains the factor . For a fixed constant tolerance it is exponential in at fixed advantage, but for exponentially small tolerance it may be weak or vacuous. Query accuracy can itself be costly to obtain from samples; that cost must be analyzed separately rather than silently omitted.
There is a concrete way to see why tolerance is a resource. If independent labeled examples are available only to estimate query means, for a fresh batch of size
per query suffices, by Hoeffding's inequality and a union bound, to answer at most adaptive bounded queries within tolerance simultaneously with probability at least . Each new batch is independent of the preceding transcript. This is a sufficient sample bound for one simulation, not a lower bound on every possible method. If is extremely small, this particular simulation is correspondingly expensive; the query-count theorem alone does not quantify that cost.
Summary
Uniform parity characters are orthogonal. Bounded queries can correlate strongly with only a limited number of them, so tolerance-valid baseline answers keep many targets consistent with one adaptive transcript. A final classifier can have a fixed advantage for only a limited number of those targets. The resulting query bound is model-specific and coexists with efficient exact learning from individual labeled examples.
Exercises
Quick check
(For , let and . Compute and its expectation under uniform .)
Use .
Solution · Answer
, since . Independence and the zero mean of each uniform sign give expectation zero.
Quick check
(For , and , use the deterministic theorem to obtain an integer lower bound on .)
Evaluate and round up.
Solution · Answer
and . The bound is , so the integer count satisfies .
Quick check
(Let and suppose an SQ oracle answers to the query with tolerance . Which parity targets are consistent with this single answer?)
Compute the true expectation of the query for each of the four targets.
Solution · Answer
The query expectation is , which is one for and zero for the other three subsets. Answer zero is outside tolerance for and valid for . This excludes one target; it does not identify which of the remaining three is correct.
Quick check
(For and , how many i.i.d. labeled examples suffice for the stated full-rank probability guarantee? Explain why each is a linear equation.)
Use .
Solution · Answer
The stated sufficient count is . Writing , the label bit obeys modulo two, so each labeled pair contributes a row equation. The probability that the eight rows fail to determine the five-bit vector is at most .