A statistical query asks for an expectation rather than an individual labeled example. Independent label flips distort such expectations in a structured way. If the flip rate is known and below one half, every bounded clean query can be converted into a bounded noisy query. The conversion is exact at the level of expectations, but its tolerance becomes smaller as the noise approaches one half.
Definition 7.2.1
(Classification noise with a known rate)
Let on a measurable instance space and let the clean label be for a measurable target . The observed label is , where is independent of , has , and is freshly sampled independently for each example. Assume the known rate satisfies , and put
Definition 7.2.2
(Clean statistical query oracle)
A clean statistical query is a measurable and tolerance . Its oracle may return any value within of . The learner must work for every sequence of valid answers, including adaptively chosen answers.
Simulating an arbitrary query
Theorem 7.2.3
(A bounded noisy query recovers a clean expectation)
Assume the exact flip rate is known. For any clean query , define
and ask the noisy query
Then and
Consequently a noisy SQ answer within of its expectation, divided by , is a valid clean answer with tolerance .
Proof
(Separate the label-independent and label-odd parts)
For , . Moreover
Because , . Independence gives , so
Taking expectations proves (2). In this realizable model, the calculation in fact only needs ; independence is a sufficient assumption. For random clean labels, the corresponding sufficient condition is . If only an upper bound on is known, dividing by the wrong value of generally introduces bias; the unknown-rate case needs a separate estimation or learning argument. If the noisy oracle returns with , then . The divided answer need not lie in ; validity only requires the tolerance inequality. If a convention also requires an answer in , clipping to that interval cannot increase its distance from the clean expectation.
Proof X-ray
Why the entire query must be rescaled
The label-independent part is not changed by noise, while the label-odd part is attenuated by . Multiplying only the latter by could leave the permitted range . Equation (1) instead scales the whole desired expectation by , keeps the query bounded, and pays for inversion through a smaller tolerance.
Worked example 7.2.4
(Correcting a classification-error query)
Let and . Then , , and the bounded query in (1) is
It takes values and and has expectation , where . Equivalently the noisy error obeys . For example, and give . The general construction applies to every bounded query, not just error queries.
Concept lensAlgebraic
Noise as an operator that shrinks the odd part
Write a query as . Since , its noisy expectation is : noise leaves the label-even part alone and multiplies the label-odd part by . Making this equal forces and , which is exactly (1).
Worked example 7.2.5
(A correlation query with a noisy oracle)
Let , so , and let agree with the target on a set of mass and disagree on the rest, so . For we have , and , with expectation . With clean tolerance the noisy oracle may be off by , so it may answer anything in . Suppose it answers . Dividing by gives , which is within of the true value , and the extreme answer gives , also within . The tolerance is therefore met at both ends, as (2) guarantees.
Worked example 7.2.6
(The two edge cases: no noise and heavy noise)
If then and (1) reads , because : the construction returns the clean query unchanged. Take , and in (3). For the batch size is . For we have and , about one hundred times as many, in line with the factor . As the factor grows without bound, which anticipates the lower bound below.
Adaptive queries from fresh noisy examples
Theorem 7.2.7
(A finite adaptive SQ computation can be simulated)
Assume the exact rate is known. Fix one pair throughout, an integer query cap and tolerance in advance. Suppose a deterministic clean SQ algorithm asks at most queries, each with that tolerance, and succeeds for every sequence of answers valid for this same pair. For , answer each noisy query using a fresh independent batch of
noisy examples, and divide its sample mean by . With probability at least , every simulated answer is valid for the clean query, so the clean algorithm succeeds. At most noisy examples are used.
Proof
(Condition on the previous adaptive transcript)
At a given round, condition on all earlier queries and answers. The next query is then fixed, while its fresh batch is independent of that transcript. Its transformed query is bounded in . Hoeffding's inequality therefore bounds the conditional probability that its sample mean misses by more than by
Let be the event that round is reached and its answer is invalid. The estimate holds for every earlier transcript on which that round is reached, so . A union bound over gives the simultaneous event. On it, every divided answer is a valid clean answer by (2), even though later queries depend on earlier answers. The assumption on the clean algorithm then gives success. For randomized clean learners, an analogous conclusion requires a clean guarantee against valid adaptive answer strategies even if they can depend on the learner’s random seed; the clean failure probability then adds to . That stronger quantifier is not silently assumed here.
This is a statistical simulation bound. Efficient computation also requires that the queries and the clean learner be efficiently evaluable. Fresh batches make the conditional concentration argument immediate; reusing one batch for adaptively selected queries needs a separate analysis.
The noise penalty cannot disappear
The upper bound contains . A simple two-target problem shows that is necessary for one clean query at constant tolerance and constant confidence. It does not establish optimal joint dependence on , , or for general SQ computations.
Theorem 7.2.8
(A two-target lower bound for noisy examples)
Suppose . On a one-point instance space, consider the two possible constant targets and , observed through independent flips at rate . Even if it knows , any learner using a fixed worst-case number of noisy labels that, for both targets, outputs the correct label with probability at least must satisfy
The result includes randomized learners with that fixed sample budget; random sample sizes need a separate argument. The clean problem is solved by one query with tolerance , whose answer has the target’s sign. This is an example-based lower bound, not an assertion that every learning class requires that many samples.
Proof
(Two nearby product distributions are hard to distinguish)
Under target , one noisy label is with probability ; under target that probability is . Let and be the two -label laws. Their Hellinger affinity is
Cauchy–Schwarz applied to gives
If a learner is correct with probability at least under both targets, its output tests the two laws with both error probabilities at most . Hence the probability difference of the event “output ” is at least , and total variation is at least . A randomized learner can be handled by adjoining its independent random seed to both laws; the affinity is unchanged. Thus and
because and .
At the two targets induce exactly the same noisy-label distribution, so no number of examples permits success probability greater than on both. This limiting impossibility explains why (1) cannot be inverted when .
Counterexample mode
A known average noise rate is not independent noise
Let be uniform on , take always, and flip the label with probability at and at . The average flip rate is , but flips are not independent of . For the query , the clean expectation is . Using in (1) gives , whose noisy expectation is still , not . Dividing by therefore gives , not : the bias persists with unlimited samples, and the simulated answer is invalid whenever . Here ; failure of the required conditional attenuation is the issue. A purely unlabeled query is unaffected.
Common mistake
(Reading the noisy error as the clean error)
With , a hypothesis whose observed error is does not have error . The observed error is , so the clean error is . Even a perfect hypothesis has observed error . Comparing observed errors across different noise rates, or treating as a floor that has to be beaten, confuses the two quantities.
Common mistake
(Reusing one batch for adaptive queries)
The proof of the adaptive simulation conditions on the transcript so far and then uses a batch that is independent of it. If one batch were used to answer every query, a later query would depend on earlier answers computed from that same batch, the conditional step would no longer be justified, and Hoeffding's inequality could not be applied to it. The sample size pays for fresh batches.
Practice with solutions
Quick check
(Purely unlabeled query. If with , compute .)
Find and first.
Solution · Answer
Here and , so . Then equals . In this special case querying directly is also possible without a noise penalty.
Quick check
(A correlation query. For with , find the transformed query and its expectation.)
Which part of is odd in ?
Solution · Answer
and , so and .
Quick check
(Compute a batch size. If , , and , give the integer prescribed by (3).)
First compute .
Solution · Answer
, so , using the natural logarithm.
Quick check
(Coin-flip noise. Why does the simulation fail at ?)
Look at , then at a one-point instance space.
Solution · Answer
Then and division is impossible. More fundamentally, on a one-point space the two constant targets yield identical independent fair noisy labels, so the two success probabilities sum to at most one and cannot both exceed .
Quick check
(Confidence accounting. If every one of adaptive queries has conditional batch failure probability at most , what is the probability that at least one fails?)
The rounds are not independent.
Solution · Answer
For each round, define failure only when that round is reached. Its unconditional failure probability is at most by averaging the conditional bound. The union bound gives at most ; the round failures need not be independent.