Research map / Learning theory and algorithms / Sample complexity

Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Robust and surrogate-loss learning bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies misspecified autoregressive learning under joint KL, showing horizon-free approximation for KL (vs Omega(H) for Hellinger), upper bounds O~(H) estimation for ERM/Bayesian posterior, and an Omega(H) information-theoretic estimation lower bound.

Problem

Learning long-horizon sequence distributions with autoregressive policies under model misspecification, measured by joint KL; how horizon H enters approximation and estimation error.

Approach

Uses the exact chain rule of KL to show approximation ratio is horizon-free under joint KL (unlike squared Hellinger's pseudo chain rule), and proves a matching Omega(H) estimation lower bound even for fully shared policy classes.

Key results

• Under joint KL, ERM and Bayesian posterior achieve approximation ratio (1+epsilon), independent of H, with estimation term O~(H log|Pi0|/n) for decomposable and fully shared classes.
• An Omega(H) lower bound on estimation error under joint KL holds even for fully shared policy classes (Theorem: c H G^2 log|Pi| / n).
• A high-probability oracle bound with leading constant 1 is shown impossible in the misspecified regime, with an Omega(H/sqrt(n)) gap.

Surprising findings

• Even with fully shared policy classes, the joint-KL estimation error must scale linearly in H, unlike squared Hellinger where sharing removes the H factor.
• Sharp high-probability oracle inequalities with leading constant 1 are impossible under joint KL in the misspecified regime.

Limitations

• Analysis is for finite or log-covered policy classes and bounded log density (Assumption with constant G), not transformer architectures.
• Lower bounds and upper bounds are up to logarithmic factors (H log H vs H).
• No empirical experiments; results are purely theoretical.

Experimental setup

Metrics: joint KL divergence estimation error scaling in H and n approximation ratio C_apx

Baselines: Hellinger-based autoregressive learning (Foster et al.-style analysis) TV-based autoregressive density estimation analysis

Builds on: squared Hellinger autoregressive learning analyses Freedman inequality mixability of log-loss

Closest papers by meaning

• Autoregressive Language Models are Secretly Energy-Based Models: Insights into the Lookahead Capabilities of Next-Token Prediction (ICML 2026 · similarity 0.86)
• SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with Backtracking (ICLR 2024 · similarity 0.86)
• Theoretical guarantees on the best-of-n alignment policy (ICML 2025 · similarity 0.86)
• Architectural and Inferential Inductive Biases for Exchangeable Sequence Modeling (NeurIPS 2025 · similarity 0.85)
• Better Estimation of the Kullback--Leibler Divergence Between Language Models (NeurIPS 2025 · similarity 0.85)
• Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities (NeurIPS 2026 · similarity 0.85)