← All AI/ML open problems

RNNs & sequence learning · Optimization & optimizers / Open question

How Far Must Credit Assignment Reach?

A learner must connect present errors to past decisions without replaying its entire history. This is a statistical and computational bottleneck in sequence learning.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For differentiable recurrent models with bounded per-step parameter derivatives and loss gradients, let Jt,t−j=∂ht/∂ht−jJ_{t,t-j}=\partial h_t/\partial h_{t-j} satisfy E∥Jt,t−j∥op2≤C(1+j)−2α\mathbb E\|J_{t,t-j}\|_{\mathrm{op}}^2\leq C(1+j)^{-2\alpha} for α>0\alpha>0. Determine the bias, variance and stored-bit frontier for online estimators of the length-HH training gradient under this polynomial-decay class. Seek an adaptive truncation/compression scheme with a population-stationarity guarantee, and matching lower bounds as α\alpha and HH vary.

Assumptions and scope

  • Fix the recurrent model, target loss, data stream and horizon; count stored states and per-step arithmetic, including any sensitivity estimates.
  • Specify how truncation or compression is selected from past information and account for selection-induced dependence and estimator bias.
  • Declare a nonuniform sensitivity envelope or other structural condition; unbiasedness alone is insufficient if estimator variance grows prohibitively.

What would settle it?

Matching resource/error bounds with a trainable adaptive estimator for the declared slow-decay class, or a lower bound ruling out cheap credit assignment despite compact state storage.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Adaptive TBPTT already controls bias under expected geometric decay, and Kronecker-factored RTRL already gives unbiased memory-efficient estimators with variance analysis. The residual target is a sharp slow/nonuniform-decay frontier, not an unbiased-gradient existence result. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Aicher, Foti and Fox — Adaptively Truncating Backpropagation Through Time to Control Gradient Bias ↗partial theory · source checked 2026-11-19

    Primary search abstract checked: adaptive truncation under expected geometric lag decay, bias control and nonconvex SGD convergence consequences. Adaptive truncation itself is established.

  2. Mujika, Meier and Steger — Approximating Real-Time Recurrent Learning with Random Kronecker Factors ↗partial theory · source checked 2026-11-19

    Primary search abstract checked: unbiased memory-efficient recurrent gradients with stability/variance analysis under stated assumptions. Unbiased online recurrent estimation is not a new existence target.

  3. Allen-Zhu and Li — Can SGD Learn Recurrent Neural Networks with Provable Generalization? ↗partial theory · source checked 2026-11-19

    Primary search abstract checked: efficient RNN learning for a stated sequence concept class with polynomial or almost-polynomial length dependence. Trainability of all RNNs is not an open yes/no question.