Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network

Biyi Fang, Diego KlabjanarXiv 2019 · arXiv

In the fast-paced world of machine learning, models are frequently trained on static, finite datasets. However, real-world applications—ranging from high-frequency stock trading to real-time social media feeds—often involve data that arrives as an infinite stream. In such environments, traditional optimization theories often fall short. A recent study by Biyi Fang and Diego Klabjan from Northwestern University addresses this gap, providing the first rigorous convergence proofs for Adam-style algorithms in streaming settings for both convex and non-convex models.

The Challenge of Infinite Streams

Standard online learning theory typically assumes a finite horizon. In these scenarios, algorithms often employ a diminishing learning rate, causing the model to become increasingly "stiff" and less responsive to new information over time. While this works for finite data, it is detrimental for infinite streams where the underlying data distribution might shift.

Furthermore, the standard metric for success—regret—is defined as the cumulative difference between the algorithm's performance and that of the best fixed model in hindsight. On an infinite timeline, total regret can grow to infinity, making it a poor measure of ongoing performance.

Algorithm 1: The standard Online Gradient Descent (OGD) baseline.

To address these issues, the authors introduce a new performance metric: regret with rolling window. Instead of measuring cumulative regret from time zero, this metric evaluates the maximum regret over any fixed window of $T$ contiguous samples. This approach allows the model to "forget" outdated data and focuses on its ability to adapt to the current data regime.

Proposed Algorithms: CONVGADAM and DNNADAM

The core contribution of the paper lies in the development and theoretical analysis of two primary algorithms:

1. CONVGADAM (Convergent Adam)

Designed for convex functions, CONVGADAM is a refined version of the Adam optimizer. A critical issue with standard Adam in online settings is that it can "forget" informative gradients too quickly, leading to instability. CONVGADAM incorporates a non-decreasing second-moment estimate, similar to AMSGrad, to ensure a more stable optimization path.

Algorithm 2: The proposed CONVGADAM optimizer, featuring a stabilized second-moment estimate.

2. DNNGD & DNNADAM

Extending the analysis to non-convex landscapes, the authors adapted these methods for two-layer ReLU neural networks. Neural networks present unique challenges due to their non-convexity and the "positive-homogeneity" of ReLU activations (where scaling inputs scales outputs). To maintain stability, the authors introduced a weight-rescaling step in the gradient updates, ensuring the weights do not explode or vanish during the infinite stream.

Theoretical Breakthroughs and Empirical Results

The authors achieved a significant theoretical milestone by proving that CONVGADAM, DNNGD, and DNNADAM all achieve an optimal $O(\sqrt{T})$ regret bound with respect to the rolling window. This was accomplished using constant learning rates, which are essential for maintaining model "freshness" in streaming applications.

Crucially, the researchers also identified and corrected technical flaws in existing proofs for AMSGrad. Their new proof technique provides a more robust foundation for understanding how adaptive optimizers behave over long horizons.

Experimental Validation

The algorithms were tested on three large-scale datasets:

  • MNIST8M: 8.1 million samples of handwritten digits.
  • Yahoo! Targeting User Modeling: 1.5 million samples for user classification.
  • Yahoo! Learn to Rank Challenge: Over 470,000 samples for ranking tasks.

In empirical tests, CONVGADAM consistently outperformed Online Gradient Descent (OGD) across all datasets, demonstrating lower loss and better adaptation. The experiments also confirmed that a rolling window size of $T=1000$ provides a stable balance for performance monitoring.

Insights for Neural Network Convergence

Proving convergence for neural networks is notoriously difficult. The authors found that convergence is guaranteed if the initial weights are sufficiently close to a stationary point and the geometric relationship (angle) between the data samples and the weight error remains bounded. While these conditions are specific, they provide a roadmap for understanding why neural networks often converge in practice despite their theoretical complexity.

Limitations and Future Directions

Despite its contributions, the study notes several limitations. The neural network proofs rely on a "proximity" requirement, meaning they don't yet fully explain "cold starts" from random initialization. Additionally, the analysis uses a probabilistic simplification of ReLU activations. Future research may extend these proofs to deeper architectures and relax the geometric constraints required for non-convex convergence.

By bridging the gap between adaptive optimization and infinite data streams, this work provides both the theoretical tools and practical algorithms necessary for the next generation of real-time machine learning systems.

Summary updated

Abstract

Nowadays, online learning is an appealing learning paradigm, which is of great interest in practice due to the recent emergence of large scale applications such as online advertising placement and online web ranking. Standard online learning assumes a finite number of samples while in practice data is streamed infinitely. In such a setting gradient descent with a diminishing learning rate does not work. We first introduce regret with rolling window, a new performance metric for online streaming learning, which measures the performance of an algorithm on every fixed number of contiguous samples. At the same time, we propose a family of algorithms based on gradient descent with a constant or adaptive learning rate and provide very technical analyses establishing regret bound properties of the algorithms. We cover the convex setting showing the regret of the order of the square root of the size of the window in the constant and dynamic learning rate scenarios. Our proof is applicable also to the standard online setting where we provide the first analysis of the same regret order (the previous proofs have flaws). We also study a two layer neural network setting with ReLU activation. In this case we establish that if initial weights are close to a stationary point, the same square root regret bound is attainable. We conduct computational experiments demonstrating a superior performance of the proposed algorithms.
BibTeX
@misc{fang2019convergence,
  author = {Biyi Fang and Diego Klabjan},
  title = {{Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network}},
  year = {2019},
  eprint = {1905.09356},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.09356},
}
Figure