Reviving and Improving Recurrent Back-Propagation

1. Introduction

• BPTT's computation and memory costs scale linearly with unrolling steps, and accumulated numerical error may make it useless for some applications.The passage gives gradient-based hyperparameter optimization as an example.Source: §1 · p. 1
• TBPTT has constant computation and memory cost, but the quality of its approximate gradient is not well understood.The paper asks whether better gradient approximations can use the same computational cost as TBPTT.Source: §1 · p. 1
• For RNNs whose hidden state converges to a steady state, RBP uses the implicit function theorem to compute the exact gradient without unrolling the full forward pass.Its linear-system solve has constant memory and computation time with respect to the number of unrolling steps.Source: §1 · p. 1
• The paper proposes CG-RBP and Neumann-RBP to address cases where original RBP's fixed-point iteration fails to converge within a reasonable number of steps.The authors suggest that multiple fixed points and sensitivity to initialization may contribute to this instability.Source: §1 · p. 1
• Neumann-RBP remains consistently stable across the paper's different applications while retaining the advantages of original RBP.The paper also demonstrates RBP for back-propagating through deep-network optimization to tune hyperparameters.Source: §1 · pp. 1–2

2. Related Work

• For content-addressable memory models, RBP offers an alternative to BPTT for manipulating attractors, which can retrieve memories from corrupted inputs [Hopfield, 1982; 1984].These models have convergent dynamics and Lyapunov functions that guarantee asymptotic stability.Source: §2 · p. 2
• In GNNs, RBP differentiates through converged propagation, which can be enforced with a contraction map or Jacobian regularization and can save computation time and memory.The passage also relates RBP to equilibrium propagation [Scellier & Bengio, 2017a; Scellier & Bengio, 2017b] and implicit differentiation of OptNet's KKT system [Amos & Kolter, 2017].Source: §2 · p. 2
• Implicit differentiation in probabilistic graphical models computes gradients of optimized inference solutions or steady states, and is equivalent to RBP when inference is viewed as an unrolled RNN.The cited examples include log-linear models, continuous MRFs, and generic energy models.Source: §2 · p. 2
• NoBackTrack estimates gradients online using random rank-one reduction, while ARTBP randomizes truncation points and compensates the truncated gradient; both are unbiased estimators.Their gradient variances differ.Source: §2 · p. 2

3.1. Recurrent Back-Propagation

• RBP is formulated for fixed-input RNNs whose hidden state reaches a steady state, from which the output and loss are computed.The update function must be continuously differentiable to differentiate the fixed-point equation with respect to its parameters.Source: §3.1 · pp. 2–3
• RBP introduces an auxiliary variable z to compute the parameter gradient by solving a linear system, using fixed-point iteration when the Jacobian is nonsymmetric.The iteration's most expensive operation is a Jacobian-vector product using the same operator as back-propagation.Source: §3.1 · p. 3

3.2. Assumptions of RBP

• The implicit function theorem requires continuous differentiability and invertibility of I − JF,h*, and a contraction map is one sufficient, but not necessary, way to ensure invertibility.For an L2 norm, the induced matrix norm is the largest singular value.Source: §3.2 · pp. 3–4
• Regularizing the Jacobian at h* encourages local contraction, but does not establish the global contraction property of F; local contraction suffices for invertibility condition II.The authors leave further discussion of condition II to the appendix because their considered applications have converged dynamic systems in practice.Source: §3.2 · p. 4

4.1. Recurrent Back-Propagation based on Conjugate Gradient

• Because general RNN Jacobians are nonsymmetric, CG-RBP applies conjugate gradient to the normal equations, yielding a symmetric system but squaring its condition number.The resulting system may therefore converge more slowly in practice.Source: §4.1 · p. 4

4.2. Recurrent Back-Propagation based on Neumann Series

• A sufficient condition for Neumann-series convergence is that the update Jacobian’s spectral radius is less than 1.The passage says this criterion implies condition II; other convergence cases are outside the paper’s scope.Source: §4.2 · p. 4
• Neumann-RBP approximates the RBP gradient by truncating a Neumann series and can compute the needed products without storing forward hidden states or memory that scales with truncation steps.The method uses reverse- and forward-mode automatic differentiation for Jacobian-vector products, and in-place updates can keep memory constant with respect to truncation steps.Source: §4.2 · pp. 4–5
• When the Neumann series converges, full Neumann-RBP is equivalent to BPTT; if the final K states are identical, K-step Neumann-RBP equals K-step TBPTT.A proposition also bounds the error between K-step and full Neumann-series approximations.Source: §4.2 · p. 5

5. Experiments

• The experiments evaluate RBP variants across diverse applications; Neumann-RBP is simple to implement with automatic differentiation, and the implementation is publicly available.Source: §5 · p. 5

5.1. Associative Memory

• With 20 truncation steps, CG-RBP and Neumann-RBP match BPTT, while original RBP's training curve blows up; at 10 steps, original RBP fails to converge.Source: §5.1 · p. 6

5.3. Hyperparameter Optimization

• Table 2 compares runtime and memory as BPTT-cost-to-Neumann-RBP-cost ratios; even unoptimized Neumann-RBP has significant practical advantages over BPTT.Source: Table 2 · p. 7, §5.3 · p. 8

5.2. Semi-supervised Document Classification

• On Cora and Pubmed, Neumann-RBP is on par with TBPTT and outperforms other variants and the baseline, while BPTT encounters learning issues.Source: §5.2 · p. 7

5.3. Hyperparameter Optimization

• Hyperparameter optimization treats network parameters as recurrent hidden states and learning rates and momenta as learnable meta-parameters, with steady state assumed in expectation for i.i.d. mini-batches.Source: §5.3 · p. 7
• At the end of hyperparameter optimization, Neumann-RBP generally matches BPTT and outperforms other methods; TBPTT tends to oscillate while Neumann-RBP converges.Source: §5.3 · pp. 7–8, Figure 6 · p. 8

• Experiments on diverse tasks support Neumann-RBP as a stable and efficient alternative to original RBP for practical problems.Source: §6 · p. 8
• The paper proposes CG-RBP and Neumann-RBP variants based on conjugate gradient on normal equations and Neumann series, respectively.Source: §6 · p. 8
• The paper establishes connections between Neumann-RBP and TBPTT to shed light on TBPTT gradient approximation quality.Source: §6 · p. 8

1.1. Contraction Map

• Contraction maps can restrict model capacity and are hard to satisfy for general neural networks.Source: §1.1 · p. 11

1.2. Local Regularization At Convergence

• The implicit-function condition requires I − J_F,h* to be invertible, equivalently a nonzero smallest eigenvalue of (I − J_F,h*)⊤(I − J_F,h*).Source: §1.2 · p. 11
• Local regularization can maximize a lower bound on the smallest eigenvalue, while differentiating through Lanczos to maximize it is generally costly and may be impractical at scale.Source: §1.2 · p. 11

• When the RNN converges, full Neumann-RBP is equivalent to original RBP and BPTT.Source: §2 · pp. 11–12
• If the hidden state is already steady for the last K steps, K-step Neumann-RBP is equivalent to K-step TBPTT.Source: §2 · p. 12
• The paper states an error bound for the K-step versus full Neumann series under convergence.Source: §2 · p. 12
• With zero initialization of the original RBP iteration, K + 1-step RBP returns the same gradient as K-step Neumann-RBP.Source: §2 · p. 12

3.1. Example Code

• The appendix presents a PyTorch Neumann-RBP example with fewer than 10 effective lines of code.Source: §3.1 · p. 12

3.2. Continuous Hopfield Network

• In the Hopfield experiments, original RBP almost always fails to converge until truncation reaches 30, while CG-RBP and Neumann-RBP converge without issues.Source: §3.2 · p. 13

3.3. Citation Networks

• On citation networks, both tested ARTBP variants perform worse than Neumann-RBP, while truncated-Poisson ARTBP outperforms uniform ARTBP.Source: §3.3 · p. 13, Table A3 · p. 13