Technical Summary: A Closed-Form Upper Bound for Admissible Learning-Rate Steps in Belief-Space Dynamics

Problem Statement

Learning rates are traditionally treated as hyperparameters tuned via heuristic search. This paper challenges that paradigm by isolating a specific local calculation within belief-space dynamics. The core problem is determining the maximum admissible step size ($\eta$) for an update modeled as a projected forward step on the probability simplex.

The paper posits that just as heuristic search (e.g., A*) requires an admissibility condition ($h(n) \leq h^*(n)$) to preserve optimality guarantees, belief-space updates require a contractivity condition in the natural geometry of probability distributions (KL/Bregman geometry) to preserve stability. Without this condition, aggressive steps can cause the belief distribution to diverge or collapse to the simplex boundary, destroying the guarantee of convergence to a stable point.

Methodology

1. Theoretical Framework

The authors model the local update of a belief state $p \in \Delta_{C-1}^\circ$ (the interior of the probability simplex) as:
$$F_\eta(p) = \Pi_\Delta \left( p - \eta \nabla E(p) \right)$$
where $E(p)$ is the local energy (loss), $\eta$ is the step size, and $\Pi_\Delta$ is the projection onto the simplex.

The analysis relies on Bregman divergence generated by the negative entropy potential $\phi(p) = \sum p_i \log p_i$, which corresponds to the Kullback-Leibler (KL) divergence. The proof utilizes the three-point identity for Bregman divergions and the projected-gradient optimality condition to derive a contraction estimate.

2. Derivation of the Admissible Bound

The proof establishes that the update map $F_\eta$ is a contraction if the step size satisfies a specific gap condition derived from strong convexity ($\mu$) and smoothness ($L$) constants of the energy landscape:
$$D_{KL}(F_\eta(p_1) \| F_\eta(p_2)) \leq D_{KL}(p_1 \| p_2) - \eta(2\mu - \eta L^2) \|p_1 - p_2\|^2$$
For the map to be contractive, the term $(2\mu - \eta L^2)$ must be positive, yielding the general upper bound:
$$0 < \eta < \frac{2\mu}{L^2}$$

3. Application to Cross-Entropy and MSE

• Cross-Entropy (CE): For $E(p) = -\sum q_i \log p_i$, the paper uses a local curvature proxy $\nabla^2 E(p) \approx \text{diag}(1/p_i)$. This yields local constants $\mu(p) = 1/\max_i p_i$ and $L(p) = 1/\min_i p_i$. Substituting these into the general bound produces a closed-form, state-dependent upper bound:
  $$\eta_{CE}^{\max}(p) = \frac{2 \min_i(p_i)^2}{\max_i(p_i)}$$
  This bound is not a fixed scalar but a function of the current belief distribution, shrinking rapidly as the belief approaches the simplex boundary (where some $p_i \to 0$).

• Mean-Squared Error (MSE): The paper treats MSE as a normalized quadratic comparison. On the normalized compensation path $p_\eta = (1-\eta)p + \eta y$, the admissible endpoint is simply $\eta_{MSE}^{\max} = 1$.

4. Entropy-Aware Backoff (ADS)

The paper introduces an adaptive dual search (ADS) mechanism that does not replace the geometric endpoint but acts as a local backoff based on uncertainty.

• Entropy Metric: $B(p) = H(p)/H_{max}$, where $H(p)$ is the entropy and $H_{max} = \log C$.
• Logarithmic Barrier: $\alpha(B) = -\log(1-B)$.
• Final Admissible Step: The entropy-aware step multiplies the geometric endpoint by a factor $\bar{\eta}(B) = 1/(1+\alpha(B))$.
  $$\eta_{CE}(B, p) = \frac{2 \min_i(p_i)^2}{\max_i(p_i)} \cdot \frac{1}{1 + \alpha(B)}$$
  When uncertainty is high ($B \to 1$), the step size is forced toward zero.

Key Results

1. Closed-Form Bound: The paper provides an explicit formula for the maximum admissible learning rate in cross-entropy classification: $\eta_{CE}^{\max}(p) = 2 \min_i(p_i)^2 / \max_i(p_i)$.
2. Geometric Proof: The admissibility is proven via KL contraction, showing that violating the bound breaks the contractivity of the update map.
3. Diagnostic Experiment: A minimal belief-space tracking task (without neural networks) demonstrates that:
   • Steps respecting the bound (low fixed $\eta$ or ADS-aware) allow the belief to track shifting target distributions accurately.
   • Steps violating the bound (high fixed $\eta$) cause the belief to overshoot, collapse to a simplex boundary, and fail to recover, even after the target shifts back.
4. MSE Comparison: The paper clarifies that the normalized MSE endpoint is 1, distinct from the CE endpoint, preventing the conflation of these two geometries.

Significance and Claims

The paper makes modest, specific claims rather than proposing a new state-of-the-art optimizer or benchmarking against existing methods.

• Geometric Contract, Not Tuning Slogan: The primary contribution is isolating a local calculation where the "safe" step size is a formula derived from the current belief state, not a hyperparameter to be tuned.
• Unified View of Training and Inference: The paper argues that the forward pass (inference) and backward pass (training) are two coordinate frames of the same underlying geometry. The forward pass executes Euler steps projected onto the simplex, and the admissible bound governs the stability of this motion regardless of whether it occurs during training or inference.
• Stability vs. Correctness: The paper explicitly distinguishes between stability (convergence to a fixed point) and correctness (convergence to the true answer). The admissible bound guarantees that the system converges to the fixed point of the local energy landscape (the empirical prior), but it does not guarantee that this fixed point is the semantically correct answer.
• Role of Entropy: The entropy term is presented not as a new endpoint, but as a safety brake that restricts the step size when the belief distribution is diffuse, ensuring the step remains within the certified region defined by the curvature.

In summary, the paper claims to replace a heuristic guess ("how large can the step be?") with a geometric upper bound derived from the local curvature and entropy of the belief state, providing a "safety certificate" for belief-space dynamics.