Abstract
The theory of stochastic approximations forms the theoretical foundation for studying convergence properties of many popular recursive learning algorithms in statistics, machine learning, and statistical physics. Large deviations for stochastic approximations provide asymptotic estimates of the probability that the learning algorithm deviates from its expected path, given by a limit ODE, and the large deviation rate function gives insights into the most likely way that such deviations occur. In this paper, we prove a large deviation principle for general stochastic approximations with state-dependent Markovian noise and decreasing step size. Using the weak convergence approach to large deviations, we generalize previous results and identify the appropriate scaling sequence for the large deviation principle. We also provide a new representation for the rate function, expressed as an action functional involving the family of Markov transition kernels. Examples of learning algorithms covered include stochastic gradient descent, persistent contrastive divergence, and the Wang-Landau algorithm.
Introduction
Stochastic Approximation (SA) algorithms are the workhorses of modern computational science. From training deep neural networks via Stochastic Gradient Descent (SGD) to optimizing reinforcement learning agents, SA provides the framework for iterative learning from noisy data. Traditionally, research has focused on the "learning" aspect: proving that as more data is processed, the algorithm converges to a desired solution—typically the root of an equation or the minimum of a loss function. This behavior is described by a limit Ordinary Differential Equation (ODE).
However, because these processes are inherently random, there exists a small but significant probability that an algorithm will deviate wildly from its expected trajectory. These "large deviations" represent moments where the algorithm effectively "forgets" its progress. Understanding these rare events is critical for ensuring the reliability and safety of AI systems in sensitive applications. In "A weak convergence approach to large deviations for stochastic approximations," Hult et al. provide a rigorous framework for analyzing these deviations in complex, real-world scenarios.
Addressing the Theoretical Gap
Previous mathematical treatments of large deviations in SA often relied on simplifying assumptions that do not hold in practice. Many models assumed that the noise was independent of the algorithm's current state or that the learning rate (step size) remained constant.
In reality, algorithms like SGD exhibit noise that varies depending on the current parameter values (state-dependent noise). Furthermore, to ensure convergence to a precise point, practitioners typically use a decreasing step size ($\epsilon_k \to 0$). This paper bridges the gap by establishing a Large Deviation Principle (LDP) that accounts for both state-dependent Markovian noise and decreasing step sizes.
Methodology: The Weak Convergence Approach
The authors move away from traditional change-of-measure techniques, which can be mathematically cumbersome. Instead, they employ a weak convergence approach based on the Laplace principle. This variational representation allows for a more streamlined analysis of the asymptotic behavior of the stochastic process.
Key Innovations
- State-Dependent Markovian Noise: The noise process ($Y_k$) is allowed to depend on the current state ($X_k$). This accurately models scenarios where the error in a gradient estimate is influenced by the current position in the parameter space.
- Decreasing Step Sizes: By analyzing the case where $\epsilon_k \to 0$, the authors address the standard practice in optimization, identifying the specific scaling sequence ($\beta_n$) that governs the "speed" of the large deviation principle.
- New Rate Function Representation: The "cost" of a deviation is quantified by a rate function. While classical theory defines this via an abstract Hamiltonian, the authors introduce a representation based on Markov transition kernels. This makes the rate function more intuitive and directly relatable to the algorithm's underlying dynamics.
Theoretical Results and Applications
The core contribution of the paper is Theorem 3.1, which proves the LDP for the continuous-time interpolation of the SA algorithm. This theorem provides a formula for the probability of a deviant path:
$$P(\text{Algorithm} \approx \text{deviant path}) \approx \exp(-\beta_n I(\phi))$$
where $I(\phi)$ is the newly derived rate function. The authors further demonstrate that their kernel-based rate function is equivalent to the classical Fenchel-Legendre transform of the limiting Hamiltonian (Proposition 3.3), ensuring consistency with existing theory while offering a more flexible analytical tool.
The framework's utility is demonstrated through several benchmark algorithms:
- Stochastic Gradient Descent (SGD): Specifically applied to logistic regression.
- Persistent Contrastive Divergence (PCD): A staple in training Restricted Boltzmann Machines.
- The Wang-Landau Algorithm: A critical tool in statistical physics for estimating the density of states.
Conclusion
By providing a rigorous LDP for general stochastic approximations, this work offers a deeper understanding of the stability of learning algorithms. The transition from "learning" (convergence) to "forgetting" (deviation) is now characterized by a tangible rate function that accounts for the complexities of state-dependent noise. While calculating these rate functions for high-dimensional neural networks remains a computational challenge, this paper provides the necessary theoretical foundation for future explorations into the reliability of large-scale machine learning models.
Summary updated