Prediction sets

The cell: eight atoms of equal mass 1/8, three labels, every posterior set by hand as an exact rational. Seven atoms are peaked, their best labels running from 0.80 up to 0.86; the eighth is flat, at (0.40, 0.32, 0.28). Against a bar of 0.70, the smallest average set size any rule can reach while covering 0.70 marginally is exactly 7/8 of a label, and the rule that reaches it is seven singletons and the EMPTY SET at the eighth atom. Those seven best labels sum to 5.81, which over eight atoms is a marginal coverage of 0.72625 — past the bar on their own — so abandoning the eighth is the cheapest way to meet the constraint rather than a failure to meet it.

Which atom that happens to is fixed exactly, and not by degree. Where every atom carries the same mass, minimizing expected set size subject to marginal coverage is a pointwise problem once the constraint is priced: a label enters the set at an atom when its conditional probability clears one operative level, the same level at every atom, set by the whole population. At the level itself the objective is indifferent to taking the label or leaving it, so a label sitting exactly there may go either way. The rule that threshold builds is an optimum, and it gives an atom the empty set precisely when that atom's own best label falls strictly below the level — but being an optimum is not being the only one. A rule clearing the bar with surplus can spend it: drop a label sitting at the level, buy a cheaper one below it, and the average size is unchanged. Where that trade is available a below-level atom is served by some optimum, so the level fixes what the threshold rule abandons rather than what every optimum does. Here the level is 4/5 and the trade is unavailable — this cell's optimum is unique. The seventh atom peaks at exactly 4/5 and is kept; the eighth peaks at 2/5 and is not. That eighth atom is not rare, not down-weighted and not adversarial. It is outnumbered.

That equal mass is a hypothesis and not a convenience. Off it the abandonment condition just stated is not merely underived, it is refuted, and in both directions: a sweep of 38,500 designed cells turns up 3,154 atoms peaking strictly above the operative level that every optimum abandons, and, among the 634 atoms lying wholly below it, 24 that every optimum serves — exact rationals throughout, the optimum unique at each of those 24. The failures are a minority and a minority is enough: 3,879 of the sweep's 38,250 weighted cells break the condition at some optimum, and what a single one of those cells ends is its standing as a law. And nothing of its form stands in its place: a rule of that form reads an atom's own mass and posterior against the operative level and nothing else, and of the 444 distinct readings the sweep produces, 55 are carried by an atom that every optimum abandons in one cell and every optimum serves in another: mass 1/20 with posterior (3/5, 1/5, 1/5) against a level of 1/5 is abandoned in the cell whose heaviest atom covers the bar alone, and served in the cell where the heaviest falls short and this one's best label is the cheapest way to close the gap. Once purchases are lumpy the problem stops being pointwise, and what decides an atom is what the rest of the cell leaves owed — which is nothing the atom carries.

Split conformal thresholds a posterior at one global level, so this is the rule it converges to. At this cell its exact worst-atom coverage is 0.0000 at every sample size, while its marginal coverage holds between 0.7262 and 0.7275 across them; sixteen-fold more data does not move the zero. Its mean set size sits 0.003 above the optimum at the smallest sample and on it at the two larger. The zero is the method meeting its specification, not missing it. Here one subpopulation handed nothing at all belongs to the constraint the tool is sold on, and nothing meeting that constraint more cheaply removes it.

Scope. Property, and the derivation is the equal-weight one: every label costs the same, so a rule's cost is that constant times the NUMBER of labels it takes, and for a fixed number the most coverage available is that many largest posteriors anywhere — which is the threshold structure, and the abandonment condition with it. That argument uses nothing about this cell but the equal masses, and it holds at any number of atoms, any number of labels and any marginal coverage asked of it (rule). Where atoms carry unequal weight it does not merely go unfinished, it fails, and densely: over a designed sweep of weighted cells the same recipe — every label above the level, plus the ones sitting exactly at it, filled in as cheaply as they close the coverage still owed — costs strictly more than the true optimum at 5,447 of 19,125. A cheap label below the level bought in place of a dearer one above it is one of the two routes to that overspend, and 2,463 of those cells have no optimum that avoids it. Equal masses are what this cell has, so its level, its condition and its abandoned eighth atom stand; what has moved is the boundary drawn around them. That boundary is proved, by exhibited cells of exact rationals — one to each direction of the condition, and a pair of them to the whole per-atom class; the failure counts and the 55 readings beside them are observations over that 38,500-cell sweep. This cell's optimum is also an exact computation in rational arithmetic, confirmed against an exhaustive search over per-atom size vectors — exhaustive over the rules that can be optimal, cost at an atom depending only on how many labels are taken there. The coverage and set-size figures beside it are observations: one set-valued protocol at sample sizes 2000, 8000 and 32000, 40 trials each, one seed stream, every coverage summed from the true masses so that no held-out estimate enters the quantity the guarantee is about. Hand-set categorical cells, three labels. Toy scale.

verifiers: explore_ruler_barecell.py, explore_ruler_exchange.py, explore_ruler_abandon.py, explore_ruler_dual.py

The recipe closes the coverage still owed with labels sitting exactly at the operative level, and such a label covers its own cost times that level — so the fill generally lands PAST the bar rather than on it. Write D for that overshoot, the marginal coverage the recipe delivers above the bar it was asked for, and t* for the operative level. Then the recipe costs at most D/t* more than the cheapest rule meeting the same bar, at every cell, equal weights or not.

An overshoot of zero therefore certifies the recipe optimal: a fill landing exactly on the bar cannot be beaten. So the recipe's failure at unequal weights needs a positive overshoot to happen at all, and a small one caps how far off the recipe can be. The cap is nowhere tight: over the 15,799 unequal-weight cells carrying a positive overshoot, the share of D/t* the recipe actually overspends averages 0.18 and reaches 1 at none of them.

Where the atoms carry equal weight the bound forces exactness outright, which is the equal-weight derivation the abandoned atom rests on, reached a second way. Every label costs the same there, so any two rules' costs differ by a whole multiple of that one cost; and a fill that closes the coverage as cheaply as it can carries no removable label, so dropping any one of its labels would leave the bar unmet — which puts the overshoot below the coverage that label carried, and D/t* below one label's cost. A non-negative whole multiple of a cost, smaller than that cost, is zero.

Scope. Rule: proved for any finite set of weighted atoms, any labels and any bar. What is new is the answer and not the machinery — both steps behind it are standard. Relax the minimization of set size under the coverage constraint to let a label be taken in part: the recipe's cost sits exactly D/t* above the relaxed value, which is complementary slackness, and no rule costs less than it. The identity is checked in exact rational arithmetic at 19,270 scorings over 19,269 cells and no cell disagrees. The overspend share is an observation over the same designed sweep of weighted cells, exhaustive over the ones carrying a positive overshoot — the exact ones among them included, which is what makes 0.18 a reading on the cap and not on a failure rate.

verifier: explore_ruler_surplus.py

The overshoot bound is one reading of an identity, and the identity says exactly what any rule pays for departing from the recipe. A pair is an atom r together with a label y taken there; it costs w_r and covers w_rp(y|r). At the operative level t* that coverage is worth w_rp/t* of cost, so the pair's cost splits into its coverage over the level and a remainder, w_r(t* − p)/t*. Call w_r|t* − p| the pair's level-excess: zero for a pair sitting at the level; for a pair above it, the coverage it delivers beyond what its cost buys at the level, and for a pair below, the shortfall. Summing over the pairs of any rule R that drops the set X of above-level pairs and buys the set Y of below-level ones,

where E_A is the level-excess of every pair above the level, e(X) that of the pairs dropped and f(Y) that of the pairs bought, the last two non-negative. The recipe drops and buys nothing and covers the bar, call it T, plus its overshoot, so t*·cost(recipe) = T + D − E_A, and with D_R for the rule's own overshoot,

A rule beats the recipe exactly when the level-excess of what it drops and buys, plus its own overshoot, falls under the recipe's overshoot; the recipe is optimal exactly when no rule's does. The overshoot bound is the right side read at its least, and the identity is what the bound loses: how far the recipe overspends is not capped by D/t* but equal to (D − e − f − D_R)/t* at any optimum.

Two things read off it. Where the overshoot is smaller than the least level-excess of any single pair off the level, no rule that drops or buys anything can beat the recipe, and a rule doing neither differs from it only in the labels it takes at the level, which the recipe already fills as cheaply as they close the coverage owed: the recipe is an optimum. That is a second test needing no optimum, and it is not the exactness threshold's — the threshold bounds the recipe's error from below, by the arithmetic of the weights; this bounds the improvement any rule can reach from above, by a level-excess; and neither implies the other. On a fortieth-grid sweep of three-atom cells it fires at between 12 and 25 percent of all cells across the five three-atom sweeps, and neither test fires at every cell of any one weight vector.

The second is what the abandonment condition's below half rests on. An atom lying wholly under the level contributes nothing at it, and the level is by definition the highest at which the labels at or above it clear the bar — so the other atoms clear it among themselves, each delivering at most the largest share s any posterior row the cell draws from carries at or above the level, and the atom weighs at most 1 − T/s. Over the posterior rows the sweep draws from the ceiling comes to 4/40 at a bar of 3/4, 7/40 at 7/10, 11/40 at 3/5 and 16/40 at 1/2, and to 8/40 at 7/10 on a second family of rows; the heaviest below-level atom found equals it in each case. So the 634 atoms the earlier sweep found lying wholly under the level are as few as they are because each had to fit under its own cell's ceiling, and a set of weights none of which fits under the ceiling carries no such atom at all: on the first family of rows, where the ceiling at 3/4 and at 7/10 sits under a fifth, every weight vector in fifths or quarters, at three atoms and at four. There the condition's below half holds with nothing for it to hold on, and whatever the condition's failures are, they are failures of its above half. On the second family the ceiling at 7/10 is a fifth exactly, and the fifths carry such atoms there.

Scope. Property for the identity: algebra at any cell — any weighted atoms, any labels, any bar — with the recipe's fill entering only through its overshoot; the machinery is complementary slackness at the dual price t*, as at the overshoot bound. It is checked in exact integer arithmetic at the recipe and at every optimum of every one of 5,559,375 cells: the 741 three-atom weight vectors on a fortieth grid, each against 625 posterior row choices, at bars 3/4, 7/10, 3/5 and 1/2 and at 7/10 on the second family of rows, and 519 four-atom vectors against 3,125 row choices at 3/4 and 7/10. The second test is a rule, proved from the identity; its firing rates are observations over the three-atom sweeps. The mass bound is a property, derived from the level's definition, asserted at every below-level atom of the same run and attained at every bar. Toy scale.

verifier: explore_ruler_excess.py

A positive overshoot bounds the recipe's overspend without deciding it. What decides it is the arithmetic of the weights. A rule's cost is Σ s_rw_r over its per-atom set sizes, and the sizes are integers — so if the recipe is not optimal, its cost above the optimum is a nonzero element of the cost lattice, the set of values Σ c_rw_r over integer coefficients — a discrete set, the weights being rationals — hence at least that lattice's smallest positive value g. With the overspend capped at D/t*, that is the test: D/t* < g proves the recipe optimal, with no optimum computed and nothing searched. The equal-weight derivation above is this test's special case — there g is one label's cost, and a fill that closes the coverage as cheaply as it can keeps D/t* under it — so at equal weights the test fires everywhere.

The threshold can be raised without touching the proof. The overspend is not an arbitrary lattice element: it is Σ (s_r − s'_r)w_r over the recipe's own sizes and some optimal rule's, and a size lies between 0 and the number of labels — so each coefficient lies in a box the recipe's own sizes pin, and the threshold rises to the anchored gap g_A, the smallest positive value over that box, never below g and still needing no optimum. Over the designed sweep the plain test decides 55.9% of the cells where the recipe is exact and the anchored one 59.5%, and neither ever fires at any of the 5,447 cells where the recipe overstates.

Where the atom weights are geometric the test decides nothing, and structurally rather than by a loose constant. On a family of cells holding one posterior menu over fifteen atoms with weights proportional to θ^r, θ rising toward 1, the lattice's g collapses across thirty-six orders of magnitude while g_A decouples from it and declines just five — and still sits at least 4.8 orders under D/t* at every member. What holds it down is difference vectors of small support: vectors on six consecutive atoms alone land under every member's D/t*, whatever sizes the recipe carries. At the one member whose recipe is exact — the one place a firing would have been correct — the anchoring raises the threshold six orders and D/t* still sits five above it; at the other eight the recipe overstates, so no sound test could fire and their silence measures nothing. And at a second geometric cell, 105 atoms wide, where the recipe is again exact and the box is too large for any enumeration, one small-support vector at 1.8·10⁻⁷ against a D/t* of 4.3·10⁻⁶ proves outright that the test cannot fire there either.

Scope. The test, its anchored raise and the monotonicity g_A ≥ g are rules, proved; the machinery is standard — the cap behind the test is complementary slackness for the relaxed program, the step from threshold to exactness is the usual rounding argument, and a feasible solution matching the relaxation's bound rounded to the cost lattice is the round-up certificate the cutting-stock literature studies as the integer round-up property and solvers deploy as an objective-integrality reduction; at this shape the relaxation's value is one greedy scan. The reach figures are exhaustive, exact in rational arithmetic, over the same designed sweep as above — 125 posterior menus crossed with 153 weight vectors — with zero firings at the overstating cells; across everything the two rigs run, 19,270 scorings over 19,269 cells, no scoring fires where the recipe overstates and none contradicts the cap. The geometric family is read at nine members with θ = (n−1)/n, n = 3 to 1000, the anchored gap enumerated exactly by meet-in-the-middle at fifteen atoms; the gap's decline over that family is derived at the flattening law. Toy scale.

verifiers: explore_ruler_surplus.py, explore_ruler_boundedgap.py

The decline the geometric family forces on the anchored gap is not only measured; past a crossover it is derived. Read a vector of the box as the polynomial P(x) = Σ c_rx^r. With weights proportional to θ^r, its value Σ c_rw_r is P(θ) times the weights' normalizing factor (1−θ)/(1−θ¹⁵) — near 1/15 for θ near 1 — and at θ = (n−1)/n, expanding P in powers of x−1 makes each order of vanishing at 1 worth a factor of n. Write flattening for the multiplicity of the root 1: for a vector flattened to depth J, P(θ) is ±m·n^−J up to a tail the same expansion bounds, m the expansion's first nonzero coefficient. So the anchored gap is the normalizing factor times min over J of A_J·n^−J, up to that tail, where J ranges over the depths the box admits and A_J — the least size of that coefficient over depth-J vectors whose leading term is positive — is an integer computed from the recipe's sizes alone, still with no optimum computed.

On this family the constants are explicit. From n = 175 on the minimizing vector is the coefficient vector of the product (x−1)(x²−1)(x³−1)² — flattened to depth 4 with m = 18, one vector sliding along the atoms as the recipe's sizes move — so the anchored gap is 18·n⁻⁴(1+o(1)) times the normalizing factor: the slow decline, given its closed rate, with D/t* not shrinking alongside it. The box pins the law's jumps too. Admissibility reads per coordinate: a vector's coefficient at an atom pins a window the recipe's size there must sit in, so a jump in the law is the recipe's sizes stepping out of the last window at some depth. The depth-5 vectors, at A₅ = 30, thread a window up to n = 150 and lose their last at 175 — the one inversion in the measured decline — and vectors of any deeper flattening are denied at every member scored, n = 100 up. The recipe's own sizes are what deny them, which is the comparison worth keeping: the sizes make the test stronger, not weaker. Below the crossover, near n = 50, none of this binds — the minimum there is a cancellation across depths that no leading term governs, priced only by scanning the box.

What those sizes deny is reachable without them. The free box at height k is the box no recipe pins: every coefficient ranges over [−k, k], the height of a vector being its largest |c_r|. On fifteen atoms at height 3 — a box containing every anchored box the recipe's sizes can pin there — the free box reaches flattening exactly 6, against the depth 4 the recipe's sizes leave standing from n = 175 on. So against a box of the same height freed of the sizes, the anchoring is worth two orders of n on the threshold — a second reading of the raise, counted this time against the sizes' own absence rather than against the plain lattice gap. And the free ceiling is an instance of a general law. A pure product is a product of factors x^d − 1: with J factors it is flattened to depth exactly J, and the size of its expansion's first nonzero coefficient is the product of the d's, exactly. Charted in width and height together — widths 4 to 24 atoms at height 1, narrowing to 8 atoms as the height rises to 10, plus the fifteen-atom cells at heights 2 and 3, 94 cells each searched exhaustively — the deepest flattening the free box reaches and the least first-coefficient size at that depth are a pure product's at every cell. The ceiling of 6 is that law's instance: the six-factor product (x−1)³(x²−1)(x³−1)² has height exactly 3, and its coefficient 18 is the part product 1·1·1·2·3·3.

At height 1 the chart runs widest, and inverted it is a classical table. The least width whose free box reaches flattening 2, 3, 4, 5, 6 steps up at 4, 7, 12, 16, 23 atoms — equivalently, the least degree of a height-1 polynomial vanishing to that order at 1 runs 3, 6, 11, 15, 22. That is the problem of Borwein and Mossinghoff, whose abstract states the least degree determined for orders up to 10 with every extremal polynomial a pure product; the overlap, orders 2 through 6, is computed independently here and agrees. The attaining products inside this chart carry distinct factors — (x−1)(x²−1)(x³−1) at degree 6 through (x−1)(x²−1)(x³−1)(x⁴−1)(x⁵−1)(x⁷−1) at degree 22 — each of height exactly 1.

Scope. Property for the identity and its tail bound — algebra, holding at any cell of this shape. The constants are exact rational computations: at seventeen members of the family, n = 3 to 100000, the nine above among them, the law's min over J reproduces the measured flattening at every member from n = 100 up, and the gap sits at 0.956 of its leading term there and within 3.5·10⁻⁵ of it at n = 100000. The recipe's sizes — and with them the constant 18 — are unchanged from n = 2000 to 100000, and nothing proves they stay fixed beyond; the crossover's location is an observation. The pure-product reading of the free box is a rule, exhaustive over its own chart: 94 cells in exact integer arithmetic, the search route checked against full brute force at widths up to 7 and heights up to 3, and the attaining products named above checked in the record. Nothing here proves the products extremal — the classical determination reaches order 10 at height 1, every row of this chart is exhaustive computation in its own range, and the contact with the classical paper is its abstract plus the independently computed overlap. What prices the least height a flattening demands at a given width stays open: on nine atoms it runs 2, 3, 9, 14 at depths 4 through 7, whose jumps rule out log-convexity in the depth. Same cells, box and machinery as the exactness threshold for the family; the chart is the free box's own. Toy scale.

verifiers: explore_ruler_gaplaw.py, explore_flatten_height.py