From target accuracy to minimum observation cost.

A target accuracy determines a cost boundary.

The observation menu is a known finite collection of linear maps. The target output is also a known linear function of the state. Readings are noiseless; their known nonnegative prices add to give the acquisition cost. The state ranges over a full linear space over a finite field, or a known affine restriction.

We first specify a set of allowed deviations for the entire output. For example, at most one of three output bits may be wrong. The failure probability δ bounds the chance of falling outside that set. Error tolerance and failure probability are separate requirements: for every true state, the probability that the output’s deviation from the true target falls outside the allowed set must be at most δ.

When the requested accuracy is feasible, among all strategies that terminate almost surely and meet this requirement, we determine the exact minimum of the worst-state expected observation cost. The lower bound covers randomization, adaptive selection based on observed values, and stopping. An observation plan achieves the bound.

An optimum can be realized by randomly choosing one of at most two predetermined observation sets. The final output based on the readings may also be randomized as needed. A set may contain many readings: two counts the plans in the mixture, not the number of observations. The risk guarantee applies to the complete randomized execution; it does not impose the same conditional guarantee on every realized stopping branch.

Count learning and production together.

Observation relationships need not all be known in advance. In a separate model, the sensor form is known but contains an unknown fixed shared bias b. A sensor returns xᵢ XOR b at cost c; a reference returns xᵢ directly at cost L. Independent calibration reveals b at nonnegative cost a, with 0 < c < L. Both b and the target values xᵢ are unknown bits, and readings are noiseless.

Pairing a sensor reading with a reference on one production target determines both that target and the shared bias. These are two paid readings, costing c and L. Information acquired for production also calibrates the remaining targets.

The minimum total cost of recovering N ≥ 1 targets with zero error, including learning, is given by the following equality. Its lower bound holds over all admissible strategies.

The amount of uncertainty is not enough to decide when to stop.

Keeping cost down also means stopping once enough information has been obtained. But even with the same single unknown dimension, stopping need not be possible.

Suppose the remaining answers are 000 and 100, and at most one of the three output bits may be wrong. Outputting 000 satisfies the requirement for both targets. No further observation is needed.

If the remaining answers are 000 and 111, no output is within one bit of both. Zero failure therefore requires further observation. The unknown dimension is the same, but the remaining answers have a different geometry. Their shape relative to the error tolerance determines whether we can stop.

Checking the relationships we learn.

We study how actual observations can determine when to stop checking, without assuming that a learned model is correct. For a finite batch, predictions are frozen, and only items with acquired exact reference values are corrected. The allowable number of remaining errors and the probability of exceeding it are specified in advance.

Among all checking strategies in this class that satisfy the accuracy requirement for every possible error pattern—including randomized and adaptive strategies—we determine the minimum expected checking cost when all predictions happen to be correct. A matching strategy attains the lower bound. This identifies the observation expense required to establish how far learned predictions need to be checked.

A bound on additional observation costs.

When reference values purchased for learning also complete outputs in the same batch, each purchase serves both learning and delivery. With equal prices per reference and a cap on training purchases, we construct a learning-and-checking procedure that requires no more reference acquisitions than direct checking under the same accuracy requirement.

Even when the learned relationship is unhelpful, the additional acquisition cost over direct checking stays within the budget allocated to features used for prediction.

Valuing observations through accuracy and price.

Mixtures of fixed observation plans and the two-support structure have a direct precedent in Wasilkowski’s Gaussian average-case analysis (1986). The contribution here is the exact characterization of the specific cost and risk models, the price boundaries at which the optimal way to learn a shared bias changes, and constructions attaining the lower bounds.

This extends the study of observation cost from planning with known relationships to checking predictions learned from data. The goal is to account for acquisition, learning and verification together when designing how to reach a specified accuracy.