PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

Vaneet Aggarwal

arXiv:2608.26515v1cs.ITcs.LG

TL;DR

The paper asks how approximation and learning costs differ for online prediction with infinite input memory. It analyzes an exogenous lagged logistic source using a lag-resolved redundancy spectrum and a Toeplitz-design converse. The spectrum gives sharp minimax regret rates in canonical exponential and polynomial regimes, while memory profiles alone do not determine regret.

  • Problem

    Finite-context prediction must distinguish approximation error from the difficulty of learning the unknown conditional law, since these costs need not have the same scale.

  • Method

    The paper combines a localized Bayesian mixture upper bound with a finite-sample information converse based on the overlapping Toeplitz design, and gives a scaled online Newton predictor.

  • Results

    Γ_T(r) is the minimax cumulative-regret scale for exponential and polynomial envelopes under the stated conditions, yielding Θ(α^-1 log^2 T) and Θ(T^(1/(2s))), respectively.

  • Takeaways & Limitations

    Regret depends on the lag-resolved complexity of predictive laws, not only on the worst-case cost of truncating memory.

  • Takeaways & Limitations

    The matching converse is specific to the exogenous lagged model and is not claimed for arbitrary stationary infinite-memory sources or profile-only characterizations.

Abstract

from arXiv · show

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.

1 Introduction

The paper separates the cost of approximating infinite-memory sources from the cost of learning their predictive laws, and develops a lag-resolved minimax regret spectrum for an exogenous logistic model.

  • 1 Introduction: Finite context can discard older observations, but approximation error and the difficulty of learning the retained conditional law need not share the same scale.The paper studies both costs under logarithmic loss and defines regret relative to a predictor that knows the source parameter.
  • 1 Introduction: Independent Rademacher inputs drive binary marks whose logits depend on an unknown, summable infinite coefficient sequence, making finite-horizon lag information explicit.The fresh input distribution is known, while infinitely many nonzero coefficients produce no finite input-memory order.
  • 1.2 Main results and technical novelty: The spectrum charges lag-wise learning difficulty, while scaled online Newton prediction attains its upper bound without claiming an efficient Bayesian-mixture implementation.Coordinates with n_T,j r_j^2 ≤ 1 are charged by total signal energy rather than a uniform h log T window cost.
  • 1.2 Main results and technical novelty: The converse uses finite-sample information bounds and conditioning of the overlapping Toeplitz design through forest representations, Hoeffding’s inequality, and Gershgorin’s theorem.The conditioning argument applies when T is at least a constant multiple of J^2 log T.
  • 1.3 Why memory decay does not determine regret: Identical worst-case truncation profiles can yield polynomially different regret, so memory decay alone cannot characterize predictive-law complexity.For polynomial envelopes, the envelope has regret Θ(T^(1/(2s))) while the rank-one subclass has Θ(log T).
  • 1.2 Main results and technical novelty: Γ_T(r) is an upper bound for every summable envelope and the minimax regret scale for canonical exponential and polynomial envelopes under the stated finite-sample condition.The matching rates are Θ(α^-1 log^2 T) for exponential decay and Θ(T^(1/(2s))) for polynomial decay.

2 Related Work

The paper distinguishes its cumulative source-averaged redundancy objective from fixed-dimensional logistic, Markov, compressed-memory, and infinite-order time-series settings. Its central comparison is a lag-resolved minimax characterization whose converse depends on the exogenous Toeplitz design.

  • Objective: The paper studies cumulative expected excess log loss, interpreted as redundancy of the entire sequential law rather than single-prediction risk.This objective differs from final next-symbol prediction after a training trajectory.
  • Contribution: The paper’s lag-resolved spectrum makes each lag’s opportunities and amplitude explicit, and its converse establishes this sum in canonical fading regimes.Prior work had not established this characterization or the polynomial regret separation for classes sharing a truncation profile.
  • Finite-dimensional logistic prediction: Fixed-dimensional logistic results do not extend by simply substituting an effective dimension because relevant coordinates grow with T and features overlap through the source-generated Toeplitz design.The paper uses online Newton steps constructively, while its statistical contribution is the localized spectrum and source-specific converse.
  • Markov and context-tree models: An order-k unrestricted Markov model has redundancy Θ(2^k log T), whereas the tied k-coefficient logistic source has Θ(k log T) under standard interiority conditions.Both models condition on length-k histories, but their parameter structures differ.
  • Unbounded-memory models: Continuity rates measure sensitivity to the remote past but do not specify how many unknown directions generate that sensitivity.The paper instead has one globally shared coefficient per lag.
  • Prediction from compressed memory: Compact filter realizations control representation cost, whereas the redundancy spectrum controls the cost of learning unknown predictive effects.The paper treats these as distinct notions of complexity.

3 Prediction Problem and Long Memory

The paper defines cumulative log-loss regret for an exogenously driven logistic source with potentially infinite input memory and analyzes lag-wise learning and recent-input truncation. Exact two-sided truncation bounds concern input windows, while the minimax spectrum captures the separate cost of learning unknown lag effects.

  • 3.1 Prediction objective and redundancy: The prediction objective is cumulative excess log loss, equal to KL divergence between the true sequential law and the predictor-induced joint law.Minimizing worst-case regret therefore gives average minimax redundancy.
  • 3.2 Canonical source and lag-wise information geometry: Independent Rademacher inputs drive binary marks whose logit is a sum of lagged coefficients, allowing infinitely many nonzero coefficients and hence no finite input-memory order.The output history remains observed but does not enter the conditional law.
  • 3.2 Canonical source and lag-wise information geometry: Lag j appears on n_T,j = T − j + 1 rounds, so its admissible amplitude and statistical lifetime combine into the scale n_T,j r_j^2.The spectrum records both active directions and their resolutions.
  • 3.2 Canonical source and lag-wise information geometry: The quadratic logistic geometry is exactly orthogonal across lags, making the information profile anisotropic and additive.This structure supports both the memory theorem and the localized-mixture upper bound.
  • 3.3 Predictive memory: Truncating after h or using the Bayes-optimal predictor based on the last h inputs has the same cumulative predictive-distortion order.Conditional Bayes optimality makes the recent-input rule optimal among predictors measurable from that input window.
  • 3.3 Predictive memory: The operational memory theorem concerns the last h exogenous inputs, not arbitrary compressed states of the full marked history.Recent marks may carry indirect information about older inputs, so the theorem is specifically an input-window result.
  • 3.3 Predictive memory: For infinitely supported coefficients, finite windows can still be accurate when weighted tail energy is small, but approximation rates do not determine minimax regret.Exponential and polynomial envelopes yield different window scales, while later results separate truncation and learning complexity.

4 Information-Theoretic Minimax Regret and the Redundancy Spectrum

The section establishes the anisotropic redundancy spectrum as an upper-bound scale for every summable envelope and a matching minimax scale for canonical exponential and polynomial envelopes under finite-sample conditions.

  • Sharp canonical rates: Γ_T(r) is the minimax cumulative-regret scale for exponential and polynomial envelopes under the stated finite-sample dimension condition.Matching constants may depend on the fixed decay parameters and logit bound B.
  • Bayesian coding: Γ_T(r) upper-bounds minimax regret for every horizon and every summable envelope via a localized Bayesian mixture.The mixture localizes coordinates above their noise scale and charges weaker coordinates by signal energy.
  • Toeplitz-design converse: The converse combines a conditioned logistic information bound with Toeplitz Gram concentration for the overlapping lag design.The lower bound uses one source-level argument rather than separate lower bounds.
  • Exponential envelope: Θ(α^-1 log^2 T) is the exponential-envelope rate when A and B are fixed.The squared logarithm results from learning each active lag at an amplitude-dependent resolution.

5 Computational Predictors Attaining the Redundancy Spectrum

The section develops explicit online predictors that attain the redundancy spectrum and extends them to profile adaptation, predictable designs, and compressed filter dictionaries.

  • Known envelope: An explicit profile-scaled online Newton predictor attains O(Γ_T(r)) for a known envelope.The construction uses normalized coefficients, horizon-dependent active-lag cutoff, and bounded-logit logistic ONS.
  • Known envelope: The finite-dimensional ONS implementation requires known horizon T, unlike the anytime Bayesian mixture.Naive geometric restarting may repeatedly repay active-coordinate resolution costs; aggregation or time-varying regularization provides alternatives with penalties.
  • Profile adaptation: A log-loss mixture over candidate envelopes adapts simultaneously, adding the explicit penalty log(1/π_k) for candidate k.A polynomial prior on an integer grid gives an O(log k) selection penalty.
  • Predictable designs: The predictable-design oracle inequality applies when features are stochastic, adaptive, and history-dependent, without requiring independent inputs or Toeplitz structure.The deterministic ONS guarantee is conditional on the realized features and labels.
  • Compressed filters: A low-rank filter dictionary reduces computation when coefficient sequences have additional structure, while state-space realizations implement the dictionary rather than define source memory.The filter bank can be updated in O(K) time and O(K) state memory.

6 Conclusion

The conclusion establishes the regret spectrum as the minimax scale in canonical exponential and polynomial regimes, while identifying the exogenous-design scope of the converse.

  • Main conclusion: R_T(r) ≤ CΓ_T(r) for every summable envelope, and R_T(r) ≍ Γ_T(r) for canonical exponential and polynomial envelopes.The matching result holds under stated conditions, with constants depending on fixed model parameters.
  • Main conclusion: Θ(α^-1 log^2 T) and Θ(T^(1/(2s))) are the respective regret rates for exponential and polynomial envelopes.The polynomial rate applies to the canonical envelope with s>1.
  • Main conclusion: A scaled online Newton predictor attains the spectrum upper bound.
  • Scope: The converse relies on the exogenously driven lagged model, so a memory profile alone cannot determine regret.

A.4 Proof of Theorem 3.3: Predictive-memory bounds

The predictive-memory proof compares the full infinite-memory predictor with a recent-input predictor by bounding the effect of the omitted centered contribution, then sums lag-specific costs.

  • Predictive-memory decomposition: R_t,h is the retained recent-input contribution, while W_t,h is the omitted contribution with conditional mean zero and specified variance.
  • Upper bound: The upper bound compares the Bayes-optimal predictor with σ(R_t,h), using the global curvature bound ψ′′ ≤ 1/4.
  • Lower bound: Pinsker’s inequality supplies the lower bound for the Bernoulli prediction loss.
  • Lower bound: Because the logit remains in [−B,B], the lower comparison uses the uniform derivative bound σ′(z) ≥ κ_B.
  • Aggregation: Summing over prediction times and reversing the order of summation yields the lag-resolved predictive-memory bounds.

B.2 Proof of Theorem 4.1: Coordinate localization

The coordinate-localization proof assigns each lag a sample-size-dependent scale, constructs a product localization, and shows its approximation and localization costs sum to Γ_T(r).

  • Proof strategy: The proof proceeds through coordinate scales, a localized product distribution, approximation and localization costs, and comparison with Γ_T(r).
  • Coordinate scales: For lag j, n_j is the number of prediction rounds on which that lag appears, and s_j measures its squared radius at the n_j^-1/2 scale.
  • Localized distribution: Each active coordinate is localized to an interval inside [−r_j,r_j] containing θ_j, while inactive coordinates require no localization.
  • Localization cost: Active-coordinate localization contributes a prior-to-posterior volume ratio 2r_j√n_j.
  • Spectrum comparison: The cases s_j>1 and s_j≤1 are jointly represented by log(1+s_j), yielding d_T(r) ≤ CΓ_T(r).The first case contributes logarithmic localization cost, while the second contributes O(s_j) approximation cost.

Appendix C Proof of Lemma 4.4

The appendix establishes the design-matrix control needed for the converse: Rademacher edge products are independent on forests, enabling concentration and spectral bounds.

  • Forest edge products: Edge products of independent Rademacher variables on a finite forest are independent Rademacher variables.The proof uses a bijection from vertex signs to root signs and edge products.
  • Gram-matrix control: Off-diagonal Toeplitz Gram entries become sums of independent Rademacher variables after organizing indices by residue classes modulo the lag difference.
  • Concentration: Hoeffding’s inequality and a union bound control every off-diagonal entry simultaneously.
  • Spectral conclusion: Every Gram-matrix eigenvalue lies in [N/2, 3N/2] on the controlled event by Gershgorin’s theorem.For J=1, the conclusion is deterministic.
  • Converse framework: The appendix then applies a Bayesian information lower bound and an entropy–MSE bound to the exogenous-design converse.

D.2 Proof of Theorem 4.3: Conditioned-design information bound

The proof restricts the source to a finite active-lag subclass, conditions on lagged Rademacher inputs, and transfers the resulting information bound to the full source family.

  • Finite-dimensional reduction: The converse restricts parameters to the first J lags and sets every later coefficient to zero.A uniform prior is placed on the resulting parameter set, using rounds t = J, ..., T.
  • Conditioned design: The selected feature vectors form a Toeplitz design from the retained input sequence.The vectors are z_i = (U_{J+i−1}, U_{J+i−2}, ..., U_i)^⊤.
  • Conditioned design: Conditional on the inputs, the selected labels are independent under the restricted source model.This supplies the conditional-design structure used by the information lower-bound argument.
  • Finite-sample condition: The conditioning assumption holds with μ = 1/2 under the stated finite-sample dimension condition.The constant is chosen sufficiently large as a function of the logit bound B.
  • Information transfer: Information from the selected data lower-bounds information from the full observations, yielding the lower bound for the full source family.The selected data are a measurable function of the full observation, and the prior is supported on a subclass of Θ(r).

E.2 Proof of Corollary 4.8: Exponential envelope

The exponential-envelope proof bounds the lag-resolved spectrum from above and below, then invokes the general upper bound to establish the stated exponential rate.

  • Upper bound: Λ = log(A^2T) controls the exponential-envelope calculation.Monotonicity and n_{T,j} ≤ T reduce the spectrum upper bound to a tractable logarithmic sum.
  • Upper bound: The logarithmic summand is bounded piecewise for 0 ≤ y ≤ Λ and y > Λ.The bounds are Λ − y + log 2 and e^(Λ−y), respectively.
  • Rate conclusion: For fixed A and α, Λ = log T + O(1), and the dimension condition holds for sufficiently large T.The upper and lower estimates therefore establish the exponential corollary.
  • Lower bound: The lower-bound construction chooses J so that J ≤ T/2 and the dimension condition in Theorem 4.5 holds.Then N = T − J + 1 ≥ T/2.
  • Lower bound: The leading term is of order Λ^2/α, while the quadratic and linear terms are absorbed under the stated conditions.This yields the exponential-envelope lower estimate.

Appendix F Proof of Theorem 5.1

The proof develops a design-sensitive online Newton inequality with explicit anisotropic dependence and applies it to a truncated-source comparator to obtain the oracle bound.

  • Proof strategy: The argument preserves explicit dependence on the anisotropic feature design.It first proves a design-sensitive ONS inequality before applying it to Theorem 5.1.
  • Online Newton update: The scaled ONS recursion starts from H_0 = I_d and uses gradients g_t = ∇ℓ_t(u_t).The predictor is constrained through metric projection onto K.
  • Online Newton update: Summing the potential inequalities telescopes the potential and produces the determinant-based ONS bound.The log-determinant term is controlled using the relation between ξ_t and log det H_t.
  • Spectrum reduction: For K = [−1,1]^h, coordinate j is nonzero on exactly n_{T,j} rounds and has squared magnitude r_j^2.Hadamard’s inequality converts the determinant into a product over coordinate contributions.
  • Oracle bound: The truncated-source comparator yields the oracle inequality, which reduces to C_B Γ_T(r).The comparison subtracts the Bayes loss under the full source and uses the upper half of the stated bound.
Loading 2608.26515v1…