arXiv：cs.LG· Wei Tang, Hanrui Zhang·· 3 小时前
Refinement as a Service：校准预测器的算法精炼
Refinement as a Service: Algorithmic Predictor Refinement
AI 导读
研究将校准预测器建模为信号方案，用特征无关的 garbling 定义精炼关系，并证明新信号可构造当且仅当其向量落在输入信号向量的线性张成中。对于确定性输出预测器，双边的精炼存在多项式时间算法，而任意数量输入预测器的精炼是 NP-hard 的。
正文
Abstract:Prediction aggregation aims to combine information from multiple predictors into a more informative one. We study this question in the setting of calibrated predictors, where each prediction must equal the conditional expectation of the quantity being predicted given the predictor's signal. Given several calibrated input predictors and the feature distribution, but not the underlying Bayes probabilities, we ask when one can construct refined calibrated predictors that preserve the information in the original predictors and cannot be further refined using the available information.
We formulate calibrated predictors as signaling schemes and define refinement through feature-independent garblings: a predictor refines another if its signal can simulate the other's signal. Constructibility is characterized through observable linear information: each signal corresponds to a vector over the feature space, and a new signal is constructible exactly when its vector lies in the linear span of the input signal vectors. Under this formulation, we establish a sharp algorithmic picture. For deterministic output predictors, bilateral refinement admits a polynomial-time algorithm based on a bipartite graph between the two input signal partitions, while refinement with an arbitrary number of input predictors is $\mathsf{NP}$-hard. In contrast, when randomized output predictors are allowed, we give a polynomial-time algorithm for any number of input predictors by decomposing constructible signal vectors into extreme rays of the associated polyhedral cone.
| Comments: | A more compact version of the paper has been accepted by NeurIPS 2026 |
| Subjects: | Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.11415 [cs.GT] |
| (or arXiv:2610.11415v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2610.11415 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Hanrui Zhang [view email]
[v1]
Thu, 8 Oct 2026 07:45:27 UTC (56 KB)
来源：arXiv：cs.LG · arxiv.org