Polynomial-Time Minimax Prediction for Stationary Renewal Processes

Xinyu Chen; Yiming Ma

cs.ITNov 1, 2026

Polynomial-Time Minimax Prediction for Stationary Renewal Processes

Authors: Xinyu Chen, Yiming Ma

Abstract

The minimax next-symbol Kullback-Leibler risk for stationary binary renewal processes is known to have order n^(-1/2). We give a polynomial-time predictor attaining this order for an arbitrary unknown finite-mean interarrival law. The construction uses a classical type-uniform renewal code. Its contribution is an exact dynamic program for censored prefix marginals, avoiding enumeration of gap histograms or binary completions. Combined with an established prediction reduction, it gives risk at most [log M_(n+1)+log(n+2)]/n, where M_N counts renewal types. Shared suffix updates reduce the total computation to O(n^3) arithmetic work and polynomial bit complexity, without tail, mixing, known-mean, or bounded-support assumptions. The statistical rate and its lower bound are prior results; the proposed advance concerns computation.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Horizon $N$	Kernel visits	Visits/ $N^{3}$	Median (ms)
8	812	1.5859	0.217
16	6,680	1.6309	1.573
32	54,064	1.6499	13.488
64	434,784	1.6586	119.323

Appendix

Table 1: Executed kernel visits and untraced elapsed time. Dense all-one histories; five timing repetitions per horizon.

Sequence Prediction

See all 33 papers

Refinement as a Service: Algorithmic Predictor Refinement
Oct 8, 2026Wei Tang, Hanrui Zhang
Chinese University of Hong Kong.
Prediction Is Not a Sufficient Memory State
Oct 9, 2026Robert Jenkinson AlvarezOnline Learning
Efficient Lempel-Ziv Prediction with the Run-Length BWT
Nov 1, 2026Ohad AvnerySequence Prediction Next-Event Prediction
Computational Rational Agents Laboratory (CORAL)

Oct 8, 2026J/K move · Enter open · S save

Refinement as a Service: Algorithmic Predictor Refinement

Wei Tang, Hanrui Zhang

Chinese University of Hong Kong.

Open paper AskPDF arXiv

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.

Abstract

Sequence Prediction

Explore similar work

Refinement as a Service: Algorithmic Predictor Refinement

Prediction Is Not a Sufficient Memory State

Efficient Lempel-Ziv Prediction with the Run-Length BWT