提出无限记忆逻辑预测的极小极大后悔率精确刻画方法。
Sharp Minimax Regret for Infinite-Memory Logistic Prediction
- 基于局部贝叶斯混合构造上界，匹配谱尺度
- 在指数与多项式衰减下，证明下界与上界同阶
- 适合研究在线预测中长程依赖的理论分析者
我们研究具有无限输入记忆的有限字母、外生驱动源的在线预测问题。独立 Rademacher 输入 $(U_t)$ 逐次观测，下一二元标记的 logit 为 $\sum_{j=1}^{t}θ_jU_{t+1-j}$，其中 $\abs{θ_j}\leq r_j$ 且 $\sum_jr_j\leq B$。后悔定义为期望累积超额对数损失。滞后 $j$ 的影响尺度为 $r_j$，仅在 $n_{T,j}=T-j+1$ 次预测中出现，由此导出滞留解析谱 $Γ_T(r)=\sum_{j=1}^{T}\log\!ig(1+n_{T,j}r_j^2\big)$。对任意可求和包络，局部贝叶斯混合给出 $\cR_T(r)\leq CΓ_T(r)$。在指数与多项式包络下，在给定有限样本维度条件下，通过 Toeplitz 设计反证法得 $\cR_T(r)\geq cΓ_T(r)$，常数依赖于衰减参数与 logit 界。因此 $Γ_T(r)$ 是该源类在典型情形下的极小极大累积后悔尺度，对应 $Θ(α^{-1}\log^2T)$（$r_j=Ae^{-αj}$）与 $Θ(T^{1/(2s)})$（$r_j=Aj^{-s}$，$s>1$）。反证针对外生滞后模型，非任意平稳无限记忆源的普适结论。仅保留最近 $h$ 个输入的代价为 $\sum_{j>h}n_{T,j}θ_j^2$，但相同截断谱可能导致多项式差异的后悔。缩放在线 Newton 预测器可达谱上界。
原文摘要 · Abstract (English)
We study online prediction for a specific finite-alphabet, exogenously driven source with infinite input memory. Independent Rademacher inputs $(U_t)$ are observed sequentially, and the next binary mark has logit $\sum_{j=1}^{t}θ_jU_{t+1-j}$, where $\abs{θ_j}\leq r_j$ and $\sum_jr_j\leq B$. Regret is expected cumulative excess log loss. Lag $j$ can affect prediction by scale $r_j$ and enters only $n_{T,j}=T-j+1$ prediction rounds, leading to the lag-resolved spectrum $Γ_T(r)=\sum_{j=1}^{T}\log\!\left(1+n_{T,j}r_j^2\right)$. For every summable envelope, a localized Bayesian mixture proves $\cR_T(r)\leq CΓ_T(r)$. For exponential and polynomial envelopes, under the stated finite-sample dimension condition, a Toeplitz-design converse proves $\cR_T(r)\geq cΓ_T(r)$, with constants allowed to depend on the fixed decay parameters and the logit bound. Thus $Γ_T(r)$ is the minimax cumulative-regret scale for this source class in these canonical regimes, giving $Θ(α^{-1}\log^2T)$ for $r_j=Ae^{-αj}$ and $Θ(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$. The converse is specific to the exogenous lagged model and is not a profile-only theorem for arbitrary stationary infinite-memory sources. Retaining only the most recent $h$ inputs costs order $\sum_{j>h}n_{T,j}θ_j^2$, yet the same worst-case truncation profile can correspond to polynomially different regret. A scaled online Newton predictor attains the spectrum upper bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。