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.
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.
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