A learning algorithm can improve a weak rule by changing which examples matter in subsequent rounds. It can also ask for an average property of a labeled distribution rather than individual labeled examples. These are distinct models: boosting combines hypotheses produced under changing weights, while statistical query learning controls the accuracy of information supplied to a learner. In both, a guarantee is meaningful only after the distribution and error criterion have been specified.
A weighted majority vote
Definition 6.1.1
(Weighted majority vote with exponential reweighting)
Fix a nonempty labeled sample with integer , where , and suppose each base rule takes values in . Start with . At round , choose a rule with weighted training error
When , define
where normalizes the weights. A mistaken example is multiplied by before normalization, and a correctly classified example by . The final score is and the classifier predicts its sign. A tie needs a convention; in the bound below we count a tie as an error, so the result holds for any fixed tie-breaking rule.
The finite update is defined for . If , the current rule already classifies the whole sample correctly and one may stop. At , its weight is zero; above , the weight is negative. Such rounds do not satisfy the positive weak-edge assumption below. If the hypothesis class permits negation, flipping a rule reverses its error. At the displayed finite update is undefined.
Worked example 6.1.2
(Reweighting four examples)
On four equally weighted examples, suppose misses exactly one. Then and . The normalizer is . After the update the mistaken example has weight , while each correct example has weight . A second rule is evaluated against these new weights, not against the original uniform distribution.
A decreasing bound on training error
Theorem 6.1.3
(Training error of the weighted vote)
If every round has and uses the update above, the fraction of sample points with is at most
If every round has for a fixed , this is at most .
Proof
(Exponential loss dominates the error indicator)
For any real , . Iterating the update and using gives
Summing over and using shows that the average exponential loss equals , which bounds the fraction with nonpositive margin. For one round,
Writing , with , gives . Multiplication proves the bound.
Proof X-ray
Where each step of the bound comes from
The proof has one inequality and two identities. The inequality is the only place where information is lost: it replaces a count of mistakes by a smooth loss. The first identity, , holds because each update multiplies a weight by and divides by , so the exponents add up to ; normalization then forces the average of to equal exactly. The second identity evaluates for the chosen , which is the minimizer of , so no other vote weight makes this factor smaller. The weak-edge hypothesis enters only at the end: exactly when and otherwise, so a uniform edge is what makes the product decay geometrically. Nothing in the argument refers to how the examples were generated, which is why the conclusion concerns the sample only.
Worked example 6.1.4
(A round with no edge)
Continue the four-example run. After round one the weights are , the heavy point being the one missed. Let err on exactly that point and be correct on the other three. Its uniform training error is , but the quantity that matters is its error under , namely . Hence , every weight is multiplied by , and . This round leaves the product bound unchanged and adds the term to the score. It is the boundary case allowed by the theorem: it does no harm, but a positive edge is needed for a factor to appear.
Common mistake
(A training bound is not a generalization bound)
It is tempting to read a small as saying that the classifier is accurate on future examples. The theorem is a deterministic statement about the fixed training sample and the hypotheses actually selected, and it does not by itself bound error on future examples; that needs an additional generalization argument, including how the sample and the adaptive choices were generated. Nor does it guarantee that a weak learner with the stated edge exists on every distribution it encounters: that is an assumption of the boosting analysis. The next example shows the gap concretely.
Counterexample mode
Zero training error need not mean zero population error
Let have equal mass, with labels at and at . The rule predicting everywhere has population error . If all independently sampled inputs happen to be , an event of probability , it has zero training error. A generalization bound controls the probability of such misleading samples; it cannot make them impossible.
Statistical queries: averages as an interface
Definition 6.1.5
(Statistical query oracle)
Let be a distribution on labeled pairs with instance space . For any query function and tolerance , a statistical query oracle returns some value satisfying
An SQ algorithm must work for every response within the permitted tolerance, not just for the exact expectation. The query function, tolerance, number of queries and running time are part of the model. An indicator query asks for the error of ; a correlation query asks for when has signs as outputs.
Proposition 6.1.6
(Simulating statistical queries with fresh batches)
Suppose an algorithm makes at most adaptive queries, with an integer, using the same tolerance . Fix . With access to independent identically distributed labeled examples from , answer each query using a fresh batch of
examples. Then, with probability at least , all answers satisfy their tolerances.
Proof
(Conditioning on the transcript, then a union bound)
Conditional on the preceding transcript and any random choices used to select the next query, the query is fixed and its fresh examples are independent draws from . Hoeffding's inequality for values in bounds the probability that the sample mean differs from its expectation by more than by . The bound holds for every preceding transcript, so it also holds unconditionally. A union bound over the at most rounds gives the conclusion. Fresh batches are crucial to this simple adaptive argument: a query chosen after inspecting a reused dataset need not satisfy the fixed-query concentration bound conditionally.
This establishes one direction of simulation: random examples can approximate a bounded number of SQ answers at the displayed sample cost. It does not say that an SQ oracle reveals individual examples or that all algorithms using examples can be implemented efficiently with SQs.
Worked example 6.1.7
(A sample budget for adaptive queries)
An algorithm makes adaptive queries with tolerance and wants every answer correct with probability at least , so . The proposition requires , so fresh examples per query and in total. In the boundary case the union bound is trivial and the requirement is , that is examples. The cost grows only logarithmically in but quadratically in : halving to multiplies the factor by four.
Worked example 6.1.8
(Reading a tolerance reply)
Suppose predicts signs and an SQ reply to is with tolerance . Since the true correlation lies in , its error lies in . The value is only a midpoint estimate; the tolerance must be carried through the conversion.
Common mistake
(A reply is a certificate, not the value)
Given the reply above, it is wrong to report the error as exactly or to feed to later steps as if it were the true error. Every correlation in is consistent with the reply, so only is certified. Because , a tolerance on the correlation is a tolerance on the error. An SQ algorithm must remain correct for every reply inside the tolerance, not for the midpoint.
Practice and solutions
Quick check
(With four equally weighted examples, a rule misses one. Find the updated weight of the missed point and the total weight on the other three.)
Compute first, then and .
Solution · Answer
The missed point receives weight and the correct points together receive . Indeed gives ; before normalization the missed point has and the three correct points together have , so each side gets half of the total.
Quick check
(If a boosting round has error , calculate and give the product bound after ten identical-edge rounds.)
Use .
Solution · Answer
, so the training-error bound is . The weaker exponential bound with gives . These bounds need not be tight.
Quick check
(A tolerance- reply to the indicator error query is . What range for the true error is certified?)
The reply may be off by up to the tolerance in either direction.
Solution · Answer
The true error lies in . Here the endpoints are already valid probabilities; in general intersect the tolerance interval with .
Reusing one sample: where the fixed-query argument breaks
The preceding proof answered each adaptive statistical query with a fresh IID batch. The batch used for query is independent of everything that chose . So we may condition on the transcript, treat as fixed, and apply ordinary concentration for a bounded fixed query. The example below shows that this conditioning step has no automatic analogue when one dataset is reused.
Counterexample mode
Adaptive reuse of a sample
Setup. Let and . Let be uniform on , and set always. Draw one IID sample . Answer every query by its empirical average .
Stage 1 (nonadaptive). Ask the singleton queries , each with expectation . The reply to is positive exactly when occurs in . The replies therefore reveal the set .
Stage 2 (adaptive). Using only these replies, choose . For every sample, . Let be an independent fresh draw. Conditional on the transcript, , so the error is at least . The total number of queries is .
Stage 1 looked harmless. Take a union bound over the pairs. The are then all distinct with probability at least . On that event each singleton reply is or . Each reply therefore differs from by less than , which is within the tolerance . Yet the final reply violates .
Every query takes values in . The choice of uses only previous responses. Each query, if fixed in advance and evaluated on fresh independent data, would enjoy ordinary concentration. What fails is independence: through the transcript, is a function of . On that same it is no longer a fixed query.
Scope. This example does not show that every dataset-reuse method fails. It also does not show that a high-probability uniform guarantee is impossible. It shows only that the simple conditional fixed-query proof cannot be transplanted to this setting. It is not a lower bound against all reusable-data algorithms.
Quick check
(For general and , show that and that the final gap is at least . Explain why this bound is positive only when .)
Compare the empirical average of on with its mean on a fresh draw.
Solution · Answer
There are at most distinct observed inputs, so . Conditional on the transcript, the query's population mean on a fresh draw is , while its empirical average on is . Their difference is . This lower bound is strictly positive exactly when ; when it need not be informative.