PaperlayerView exact revision on arXiv

Source-linked AI summary

RCShift: Certifying When Partial Linkage Suffices for Finite-Sample Decisions

Shuheng Cao, Ruiqi Chen, Zhenhao Zhang, Renjie Cao, Siyu Zhang, Lingwei Dang, Jiajun Zhang, Tingting Dan

arXiv:2609.26207v1cs.AI

TL;DR

Systems with costly gold outcomes and cheaper auxiliary observations need to choose how much record linkage to retain for a declared finite-sample decision. RCShift characterizes family-exact storage and certifies finite-decision preservation through residual-loss bounds. In a strict witness, one aligned counter preserves a four-record minimum while an equal-cost misaligned counter and margins require eleven.

  • Problem

    It is unresolved which costed joint counters preserve a declared finite-sample threshold after margins are fixed, although complete pairing and separate margins are not calibrated to that decision.

    Source: Introduction · p. 1

  • Method

    RCShift fixes an observation contract and characterizes family-exact storage through LR-visible cycle directions, then bounds reverse deficiency and applies a slack test for finite-decision preservation.

    Source: Introduction · pp. 1–2, Compiler · p. 3

  • Results

    One aligned counter preserves the four-record minimum, while an equal-cost misaligned counter and margins require eleven; universal reconstruction requires two counters.

    Source: Introduction · p. 2, Discussion and Limitations · p. 7, Conclusion · p. 7

  • Takeaways & Limitations

    Counter value depends on direction, and positive information loss need not incur finite-sample decision cost under the declared family, costs, target, and common strictly positive support.

    Source: Conclusion · p. 7, Discussion and Limitations · p. 7

    The guarantees assume a declared LR family, additive costs, common strictly positive support, an exact LR basis, and evaluable deficiency suprema; integer transfer also requires finite t⋆ and the stated slack condition.

    Source: Discussion and Limitations · p. 7

Abstract

from arXiv · show

Systems with costly gold outcomes and cheaper auxiliary observations must decide how much record linkage to retain. Complete pairing retains every joint counter, while separate margins retain none. Neither endpoint is calibrated to a declared finite-sample decision. Universal reconstruction can retain cycle directions invisible to the likelihood-ratio family. Family-exact storage can exceed what the decision requires because certified residual loss may fit within finite-sample slack. We introduce RCShift, which certifies two routes to sufficiency under a declared observation contract. Its exact mode characterizes minimum-cost family-exact storage through LR-visible cycle directions. Its approximate mode bounds reverse Le Cam deficiency. Its integer mode certifies whether a chosen set preserves the full experiment's minimum integer record count at specified size and power. In a rank-two witness, one aligned counter preserves a four-record minimum. An equal-cost misaligned counter and the margins require eleven records, while universal reconstruction requires two counters. A local perturbation has positive reverse deficiency yet retains the four-record minimum. Proof-checked scheduling bounds instantiate the contract before gold computation and yield exact reconstruction on the admitted tree support. RCShift turns partial-linkage storage into decision-calibrated measurement design for the declared family, costs, target, and common strictly positive support.

Introduction

The paper asks which selected joint counters preserve a declared finite-sample decision, rather than requiring complete linkage or retaining only margins. RCShift characterizes family-exact storage and certifies finite-decision preservation, with counter alignment and decision slack distinguishing the two.

Introduction

  • Margins leave unresolved cycle moves, but a certification decision depends only on directions visible to the declared likelihood-ratio family.Thus counter value depends on alignment with those directions, not counter count alone.Source: Introduction · p. 1
  • The paper distinguishes its design problem from universal table reconstruction and from prior task-aware, sufficiency, and feature-acquisition approaches.Those approaches do not separate family-exact storage from finite-decision preservation after margins are fixed.Source: Introduction · p. 1
  • RCShift frames partial-linkage retention as costed measurement design under an observation contract fixed before final gold outcomes are observed.The contract specifies support, released margins, candidate counters, costs, declared laws, and the decision target.Source: Introduction · p. 1
  • Family-exact storage retains LR-visible cycle directions; finite-decision preservation can require less when certified residual loss fits within decision slack.The three modes characterize minimum-cost family-exact storage, bound reverse deficiency, and apply the slack test.Source: Introduction · pp. 1–2
  • One aligned counter preserves the four-record minimum, while an equal-cost misaligned counter and margins require eleven; universal reconstruction requires two counters.A local perturbation also retains the four-record minimum despite positive reverse deficiency.Source: Introduction · p. 2
  • A seven-edge witness establishes direction and threshold separations with a full-rank boundary, while proof-checked scheduling bounds instantiate the contract.The admitted tree support permits exact reconstruction.Source: Introduction · p. 2

Related Work

Related work supplies fixed-margin geometry, family-relative information, cost-aware acquisition, and checkable optimization outputs. RCShift combines these concerns into costed joint-counter selection for a declared decision family and finite-sample target.

Contingency geometry and data linkage

  • Fixed-margin contingency methods describe transportation fibers, while record-linkage methods infer identity correspondences; RCShift instead selects aggregates for a declared decision family.Its design object differs from both identity recovery and universal table reconstruction.Source: Related Work · p. 2

Task-aware sufficiency and representation

  • Classical sufficiency, experiment comparison, and predictive representations make information family-relative, but RCShift selects costed joint counters conditional on released margins.It connects family-relative information to exact finite record requirements at specified size and power.Source: Related Work · p. 2

Cost-aware information acquisition

  • Cost-aware acquisition studies measurements under budgets and partial observation, whereas RCShift fixes cohort-level joint counters before final gold outcomes.Its certificates concern a fixed cohort, not sequential acquisition policies; strict counter complementarity can make singleton scores miss an informative pair.Source: Related Work · p. 2

Learning and certifying scheduling

  • Certified optimization attaches checkable proofs to solver claims, and RCShift uses feasible schedules and analytic lower bounds as auxiliary observations before gold computation.These observations instantiate the declared contract for the analysis.Source: Related Work · p. 2

Synthesis

  • The cited lines do not determine which costed joint counters preserve a declared finite-sample threshold after margins are fixed.They also do not separate family-exact storage from finite-decision preservation.Source: Related Work · p. 2

Compiler

The Compiler formalizes a finite-sample target under a declared observation contract and provides exact, approximate, and integer certification routes. Its reductions distinguish LR-visible cycle information from residual loss that changes the minimum integer record count.

Compiler

  • The observation contract fixes strictly positive laws on a finite bipartite support and records row and column margins plus selected joint counts.It excludes parameter-dependent structural zeros and boundary laws.Source: Compiler · p. 2
  • Released margins leave ambiguity along the support graph’s cycle space; exact family storage resolves only the LR-visible directions, while universal reconstruction removes every residual cycle.The storage requirements are nested from universal reconstruction to family-exact storage to finite-decision preservation.Source: Compiler · p. 3
  • For a declared finite-sample decision, the storage experiment is sufficient when it attains the full experiment’s minimum integer record count at specified size and power; reported counts are Kfull = Kaligned = 4 < 11 = Kmisaligned = Kmargins.Source: Compiler · pp. 2–3
  • The exact mode characterizes cost-minimizing family-exact counter sets through the span of retained coordinate functionals and the LR target subspace.Under unit costs, full LR cycle rank reaches the universal reconstruction budget; a feedback-edge set of size ℓ attains that budget.Source: Compiler · p. 3
  • The integer route transfers a sound loss bound to a full-experiment test at t⋆ and certifies preservation when the stated slack condition holds.The transfer uses randomized thinning to restore size α; finite t⋆ and the required slack condition are assumptions.Source: Compiler · pp. 3–4
  • A full-table likelihood ratio is constant on every stored-statistic fiber exactly when every LR vector annihilates the measurement kernel, yielding family-exact sufficiency.Strictly positive support and integral measurements let an undetected integer kernel move witness failure of universal equivalence at some finite sample size.Source: Compiler · p. 4
  • The approximate route bounds reverse deficiency using low-mass omitted edges whose removal leaves a forest with the stored coordinates.If no sampled record falls on those edges, leaf elimination reconstructs the full table; hockey-stick contraction supplies a lower certificate.Source: Compiler · p. 4
  • The certified budget bcert is an upper bound on bpreserve, while exact finite enumeration separately identifies bpreserve in the seven-edge instance.The certified budget is the minimum cost passing the fixed sufficient certificate.Source: Compiler · p. 4

Certifying the Two Reductions

The two reductions target different needs: exact storage retains family-visible directions, while approximate and integer certification assess whether residual loss affects the decision. Counter contributions can be complementary, and exact minimum-cost search can be computationally hard.

Certifying the Two Reductions

  • For a two-point experiment, a residual move is decision-invisible exactly when it is orthogonal to the edge log-likelihood-ratio vector.Accordingly, the unstored gain graph need only be balanced, not acyclic.Source: Certifying the Two Reductions · pp. 4–5
  • Minimum-cost family-exact storage is simultaneous weighted gain frustration, whose scalar special case is NP-hard.An ILP or branch-and-cut solver can propose a set, and Equation (11) verifies family-exact storage for the returned set.Source: Certifying the Two Reductions · p. 5
  • Counter value can be nonseparable: singleton rankings may miss a pair whose coordinate functionals jointly span an LR-visible target direction.The approximate route uses low-mass omitted edges to bound reconstruction loss, while adjacent NP crossings determine whether that loss changes the minimum integer record count.Source: Certifying the Two Reductions · p. 5

Compiler Procedure

The compiler separates counter search from claim verification, checking exactness, approximate loss, and preservation of the full experiment’s minimum integer record count.

Compiler Procedure

  • The observation contract fixes support, margins, candidate counters, costs, parameter families, and the size-and-power target before exact compilation.Structural zeros belong to the contract, not to a finite pilot table.Source: Compiler Procedure · p. 5
  • Exact mode checks candidate counter sets by elimination and accepts sets that provide family-exact storage.A passing set is verified against the graph-form condition in Equation (18).Source: Compiler Procedure · p. 5
  • For sets failing exactness, approximate mode combines an exception-set mass bound with a hockey-stick contraction bound to certify an interval for reverse deficiency.The exception set is chosen so deleting it leaves a forest.Source: Compiler Procedure · p. 5
  • Integer mode uses a full-test witness and Equation (14) to certify that a passing set preserves the full experiment’s minimum record count.Small finite experiments can instead compute the preservation bound by exact reduced-experiment maximin computation or enumeration.Source: Compiler Procedure · p. 5
  • The verifier checks mode-specific witnesses; a minimum-cost claim additionally requires an optimality witness or exhaustive finite enumeration.Approximate acceptance certifies the integer minimum, while exact acceptance proves equivalence for every record count.Source: Compiler Procedure · p. 5

Controlled Finite-Sample Separations

In the controlled witness, counter alignment changes the finite-sample record requirement, and a small perturbation can preserve that requirement despite positive reverse deficiency.

Direction separation at equal cost

  • With margins and N00 retained, the residual cycle has zero alternating contrast, making the aligned statistic exactly sufficient; equal-cost N22 leaves a contrast.Thus equal counter cardinality does not imply equal decision value.Source: Controlled Finite-Sample Separations · p. 5
  • At α = .05 and β = .30, Kfull = Kaligned = 4 < 11 = Kmisaligned = Kmargins; universal reconstruction requires two counters.The certified adjacent frontiers establish the integer minima.Source: Controlled Finite-Sample Separations · p. 6, Table 1 · p. 6

Family saturation

  • Among singleton counters, exactly N00, N01, and N10 yield family-exact storage; universal reconstruction requires two counters.The rank-two witness has one residual cycle after any of those exact singleton choices.Source: Controlled Finite-Sample Separations · pp. 6–7

Misalignment loss certificate

Threshold separation under positive deficiency

  • The off-subspace perturbation gives positive reverse deficiency, yet the perturbed full and stored experiments both retain a four-record minimum.The result applies for sufficiently small nonzero perturbations; the stated endpoint TV radius is at most 10^-5.Source: Controlled Finite-Sample Separations · p. 6

Cost qualification

  • With nonuniform counter costs, the numerical cardinality identities need not hold; the objectives become weighted gain-frustration and weighted feedback-edge deletion.Cost-based definitions, rather than counter counts, govern the resulting values.Source: Controlled Finite-Sample Separations · p. 7

Proof-Checked Contract Instantiation

Proof-checked scheduling bounds instantiate the auxiliary side of the observation contract, and the admitted tree support permits exact reconstruction from released margins.

Proof-checked bounds

  • For each scheduling instance, a feasible family schedule supplies an upper makespan bound, while independently recomputed job-chain, workload, and release-precedence bounds supply a lower bound.The interval endpoints are checked against the declared constraints and schedule family.Source: Proof-Checked Contract Instantiation · p. 7

Set-valued auxiliary output

  • The checked interval maps to the set of gold-label bins it intersects, and admission requires one class or two adjacent classes.The fixed makespan bins are (−∞, 24], [25, 36], and [37, ∞).Source: Proof-Checked Contract Instantiation · p. 7

Cohort

Admitted support

  • On the admitted cohort’s six-edge tree support, released margins reconstruct every paired count exactly.The paper distinguishes this contract instantiation from the i.i.d. construction used for direction and threshold separations.Source: Proof-Checked Contract Instantiation · p. 7

Discussion and Limitations

RCShift separates family-exact information retention from finite-decision preservation, which can tolerate residual loss within full-experiment slack. Its controlled witnesses distinguish direction value from decision-slack value, while the guarantees depend on stated computational and support conditions.

Discussion and Limitations

  • Family-exact storage retains LR-visible cycle directions, while finite-decision preservation can tolerate residual loss within full-experiment slack.These regimes separate information relevance from the decision cost of residual loss.Source: Discussion and Limitations · p. 7
  • At equal cost, alignment changes the minimum from four records to eleven, while a positive-deficiency perturbation preserves the four-record minimum.The witnesses isolate direction value and threshold value, respectively.Source: Discussion and Limitations · p. 7
  • The discussion connects fixed-margin cycle geometry and family-relative objectives to Hara, Sei, and Takemura (2012) and task-aware representation learning.It also relates cost-aware acquisition to Ma et al. (2019) and Li and Oliva (2021), and independently checkable solver observations to Bogaerts et al. (2022).Source: Discussion and Limitations · p. 7
  • Minimum-cost search can be NP-hard, and certification requires an optimality witness or exhaustive enumeration.Guarantees assume a declared LR family, additive costs, common strictly positive support, an exact LR basis, and evaluable deficiency suprema; integer transfer additionally needs finite t⋆ and the stated slack condition.Source: Discussion and Limitations · p. 7

Reproducibility Statement

Reported finite-enumeration quantities use exact rational arithmetic, and the supplementary package provides data, randomized boundary rules, and executable checks.

Reproducibility Statement

Conclusion

RCShift characterizes family-exact retention through LR-visible cycle directions and certifies finite-decision preservation under a sound loss transfer. Its witnesses show directional value and that positive information loss need not impose finite-sample decision cost, within the declared scope.

Conclusion

  • One aligned counter preserves the four-record minimum, while an equal-cost counter and the margins require eleven records; universal reconstruction requires two counters.Source: Conclusion · p. 7
  • Family-exact retention follows LR-visible cycle directions, and finite-decision preservation is certified under a sound loss transfer.Source: Conclusion · p. 7
  • A local perturbation preserves the four-record minimum despite positive reverse deficiency.Source: Conclusion · p. 7
  • The claims hold for the declared family, costs, target, and common strictly positive support.Source: Conclusion · p. 7

Related papers

Loading 2609.26207v1…