Learn through approximate expectations of bounded functions: understand oracle tolerance, query cost, sample implementation and the limits of noise robustness.
Statistical query model
The statistical query (SQ) model is a model of learning in which an algorithm accesses approximate population expectations of bounded functions instead of individual observations. For a quant researcher, it provides a way to ask how much information a learning procedure needs from aggregate statistics, and how precisely those statistics must be known.
The oracle's contract
Let D be a distribution over an example space Z. In supervised learning, Z=(X,Y) contains features and a label. The learner submits a function ϕ:Z→[−1,1] and a positive tolerance τ. The oracle returns a number v satisfying
∣v−ED[ϕ(Z)]∣≤τ.
This is the bounded-expectation convention in Feldman's definition of STAT, §2.2. The expectation is over the underlying distribution, rather than a particular stored dataset. The tolerance limits absolute error in that expectation; it is not the final predictor's error rate.
The algorithm must work for every permitted answer, including answers chosen adversarially within the tolerance. There is no requirement that the response be unbiased, Gaussian, independent across calls or centred randomly around the truth. An oracle can consistently return the same permissible offset. Averaging repeated calls therefore need not improve accuracy.
One query, an entire interval of valid answers
Consider a fictional directional classifier h(X) and a label Y, each taking values −1 or +1. Query the signed agreement score
ϕ(X,Y)=h(X)Y.
It equals +1 for agreement and −1 for disagreement. Suppose the stipulated population has agreement probability 0.6 and disagreement probability 0.4. Then
ED[ϕ]=0.6(1)+0.4(−1)=0.20.
With τ=0.05, the oracle may return any value in [0.15,0.25], including both endpoints. In particular,
∣0.24−0.20∣=0.04≤0.05,∣0.26−0.20∣=0.06>0.05.
Thus 0.24 is valid and 0.26 violates the contract. Returning 0.24 on every repetition remains valid. These are invented population probabilities, not a measured forecast accuracy or evidence of trading profitability; the score ignores payoff sizes and costs.
Synthetic statistical query: true expectation 0.20 and tolerance 0.05 permit all answers from 0.15 through 0.25 inclusive. The answer 0.24 has error 0.04 and is allowed; 0.26 has error 0.06 and is outside the guarantee.
Original theoretical illustration, with a zoomed dimensionless axis. The blue band is the set of allowable oracle answers, not a confidence interval or a probability distribution over answers.
Where the model came from
Kearns introduced SQ learning as a restriction of PAC learning. His original queries were Boolean predicates χ(X,Y)∈{0,1}: the answer approximated the probability that the predicate is true. The signed bounded-function form above is a common later formulation. For a bounded function, rescaling to (ϕ+1)/2∈[0,1] halves its expectation tolerance; that function need not be Boolean.
The original motivation was classification noise. In Kearns's model, clean binary labels come from a target function; each is independently flipped with a constant probability η<1/2, independent of the input. Efficient SQ learners can be simulated using such noisy examples, with cost worsening as noise approaches one half. The paper initially assumes a known upper bound below one half. This result does not cover arbitrary input corruption, input-dependent label errors or shifting market regimes. See Kearns, §§3–5.
An SQ oracle is a mathematical information interface. SQL is a database query language. Computing a database average with SQL can help implement an estimator, but does not by itself guarantee population accuracy within an SQ tolerance.
Count precision as well as queries
Query complexity counts oracle calls at a specified tolerance. Smaller tolerances give more informative answers, so two algorithms with the same call count may demand very different resources. The work required to evaluate each query function also matters: an oracle call does not make an expensive statistic free. An SQ lower bound constrains algorithms using that information interface; it is not automatically a lower bound for every algorithm with raw samples. Feldman's framework formalises the separation between query and estimation complexity.
Replacing an oracle with data
For one fixed query and n independent and identically distributed observations, an empirical mean estimates its expectation. Since ϕ∈−1,1], [Hoeffding's inequality gives
P(n1i=1∑nϕ(Zi)−ED[ϕ]>τ)≤2e−nτ2/2.
For τ=0.05 and failure probability δ=0.05, this bound is at most δ when
n≥0.0522ln(0.052)=2951.1035…;n=2952 suffices.
This is a sufficient worst-case bound, not a necessary sample size. Unlike the ideal oracle's unconditional tolerance promise, a sample implementation can fail.
Queries may be adaptive: later functions can depend on earlier answers. Reusing one dataset for an unrestricted adaptive search does not inherit a fixed-query guarantee. Fresh independent batches with an allocated failure budget are one solution; uniform bounds over an appropriate predeclared query class are another. Duchi's notes, §4.1.1 and §5.3.1, develop the concentration and interaction issues.
Financial rows with overlapping labels, serial dependence or changing distributions do not automatically satisfy the IID assumption. Reporting an exact historical average answers a question about that dataset; claiming an accurate population expectation needs a justified sampling model.
For the foundation behind the oracle contract, Expectation, Variance and Covariance develops probability-weighted averages. The full lesson is available with a free signed-in account; its preview is public.
