Source-linked AI summary
Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
Mahesh Chandra Mukkamala, Matthias Hein
TL;DR
Adaptive gradient methods lack equally strong guarantees across convexity regimes despite their practical popularity. The paper analyzes RMSProp in online convex optimization and proposes SC-Adagrad and SC-RMSProp, showing logarithmic regret for strongly convex functions and favorable experimental performance.
Problem
Adaptive gradient methods are popular in deep neural-network training, while strongly convex problems offer logarithmic regret guarantees beyond the general convex setting.
Method
The paper analyzes RMSProp in online convex optimization and proposes SC-Adagrad and SC-RMSProp for strongly convex functions.
Results
RMSProp receives a convex-case regret analysis, while SC-Adagrad and SC-RMSProp achieve logarithmic regret bounds for strongly convex functions.
Takeaways & Limitations
In experiments, SC-Adagrad and SC-RMSProp outperform the other methods across the considered datasets in online regret evaluations.
Takeaways & Limitations
For 0 < γ < 1, the SC-RMSProp and SC-Adagrad bounds cannot be straightforwardly compared because their v_t,i terms differ.
Abstract
from arXiv · showhide
Adaptive gradient methods have become recently very popular, in particular as they have been shown to be useful in the training of deep neural networks. In this paper we have analyzed RMSProp, originally proposed for the training of deep neural networks, in the context of online convex optimization and show $\sqrt{T}$-type regret bounds. Moreover, we propose two variants SC-Adagrad and SC-RMSProp for which we show logarithmic regret bounds for strongly convex functions. Finally, we demonstrate in the experiments that these new variants outperform other adaptive gradient techniques or stochastic gradient descent in the optimization of strongly convex functions as well as in training of deep neural networks.
1. Introduction
The paper addresses adaptive gradient methods for online convex optimization, focusing on the gap between general convex and strongly convex regret guarantees. It proposes strongly convex variants and analyzes RMSProp theoretically and empirically.
- Adagrad achieves optimal O(√T) regret for general convex functions, while strongly convex functions permit logarithmic regret bounds.
- SC-Adagrad adapts Adagrad to strongly convex optimization and achieves a data-dependent logarithmic regret bound.The paper motivates data-dependent bounds as potentially better in practice than data-independent bounds.
- RMSProp achieves a data-dependent O(√T) regret bound under conditions on its weighting scheme.RMSProp contains Adagrad as a special case for a particular weighting choice.
- SC-RMSProp extends the strongly convex approach to RMSProp and is reported as competitive with or better than other adaptive methods and stochastic gradient descent.
2. Problem Statement
The paper studies online convex optimization, where iterates incur losses from sequential convex functions and are compared with the best decision in hindsight. It reviews adaptive and projected-gradient methods under convex and strongly convex settings.
- Online convex optimization supplies gradients of sequential convex losses, and the algorithm predicts within a convex set while accumulating regret against the best decision in hindsight.
- The analysis covers arbitrary convex functions and specializes parts of the setting to strongly convex functions.
- Strong convexity is formulated component-wise through positive parameters µ_i, with ζ = min_i µ_i yielding usual ζ-strong convexity.
- The assumptions bound gradient norms and distances between iterates and the optimal decision.
- Projected gradient descent attains O(log(T)) regret for strongly convex problems, whereas Adagrad attains optimal O(√T) regret for general convex problems.
- Adagrad uses accumulated squared gradients to form coordinate-specific effective step lengths that decay with observed gradient magnitudes.
- The paper motivates SC-Adagrad because strongly convex logarithmic regret requires the effective stepsize to decay faster than in standard Adagrad.
3. Strongly convex Adagrad (SC-Adagrad)
SC-Adagrad modifies Adagrad for strongly convex functions by using a time-varying damping factor. The analysis establishes data-dependent logarithmic regret under monotone damping, while noting unresolved comparisons between decay schemes.
- SC-Adagrad: The resulting effective stepsize is O(1/T), matching the decay needed for logarithmic regret in strongly convex optimization.
- SC-Adagrad: SC-Adagrad changes Adagrad’s diagonal matrix by replacing constant damping with a coordinate-wise, nonincreasing damping factor δ_t.
- Damping design: The damping factor should initially be roughly order 1 and then decay as accumulated squared gradients grow, preventing unstable early updates.
- Damping design: A decay scheme δ_t,i = ξ_2e^(-ξ_1v_t,i) satisfies the proposed properties for suitable positive parameters, while ξ_1 = 0 gives constant damping.
- Regret analysis: The bound depends on the observed gradient sequence and is therefore described as typically tighter than a data-independent bound.
- Regret analysis: SC-Adagrad achieves a data-dependent O(log(T)) regret bound for strongly convex functions, including under constant damping.
- Open limitation: The paper does not establish that the decaying damping bound is better than the constant-damping bound and leaves an optimal decay scheme for future work.
4. RMSProp and SC-RMSProp
The paper analyzes RMSProp for online convex optimization, establishes a regret bound under conditions on its weighting scheme, and identifies Adagrad as a special case. It also introduces SC-RMSProp, which achieves a data-dependent logarithmic regret bound for strongly convex functions.
- RMSProp: The weighting scheme matters: the analysis contrasts its required condition with the original suggestion β_t = 0.9.The experiments report that constant β_t can sometimes lead to divergence, whereas the theoretically derived choice leads to convergence even for deep neural networks.
- RMSProp: RMSProp reduces to Adagrad for a particular choice of its parameters, recovering Adagrad’s convex-case regret bound up to a damping factor.The paper presents this correspondence as a previously unobserved connection between the two methods.
- RMSProp: RMSProp is analyzed in online convex optimization, with a regret bound established under conditions on its weighting scheme.The analysis requires constraints involving the weighting parameters β_t and a stepsize of the form α_t = α√t.
- SC-RMSProp: SC-RMSProp extends RMSProp to strongly convex functions and achieves a data-dependent logarithmic regret bound.The method uses a decreasing damping sequence δ_t,i satisfying δ_t,i ≤ δ_t−1,i.
- SC-RMSProp: The SC-RMSProp regret bound reduces to the SC-Adagrad bound when γ = 1, but comparing the methods is not straightforward for 0 < γ < 1.The paper identifies comparison under general γ as an open question because the v_t,i terms cannot be directly compared.
5. Experiments
The experiments evaluate adaptive gradient methods on strongly convex problems and several deep-learning architectures across MNIST, CIFAR10, and CIFAR100. SC-Adagrad, SC-RMSProp, and the paper’s RMSProp variant show strong results, with performance depending on architecture and dataset.
- Setup: The experiments use MNIST, CIFAR10, and CIFAR100, selected to represent differing difficulty in achieving good test performance.
- Strongly Convex Case: SC-Adagrad and SC-RMSProp outperform all other methods in regret across the considered strongly convex datasets.The online experiments plot regret against the fraction of training points seen.
- Strongly Convex Case: RMSProp (Ours) has lower regret than the original RMSProp.
- Convolutional Neural Networks: SC-RMSProp is competitive in training objective across CNN datasets, while SGD achieves the best training-objective performance.The 4-layer CNN uses two convolutional layers, one fully connected layer, ReLU activations, dropout, max-pooling, and cross-entropy loss.
- Convolutional Neural Networks: RMSProp diverges on CIFAR10, whereas RMSProp (Ours) converges on all datasets and matches Adagrad in training objective.
- Convolutional Neural Networks: Both RMSProp (Ours) and SC-Adagrad outperform the other methods in CIFAR10 test accuracy for the 4-layer CNN.
- Residual Network: In the ResNet-18 CIFAR10 experiment, SC-Adagrad, SC-RMSProp, and RMSProp (Ours) have the best test accuracy.RMSProp (Ours) has the best training objective together with Adagrad.
6. Conclusion
The paper analyzes RMSProp in online convex optimization and introduces SC-Adagrad and SC-RMSProp for strongly convex settings. It establishes regret guarantees and reports strong performance across network models and datasets, while leaving the reason for the deep-learning behavior open for future work.
- Conclusion: The paper analyzes RMSProp in online convex optimization and finds convergence conditions for the convex case that differ from the original method’s usage.
- Conclusion: SC-Adagrad and SC-RMSProp achieve logarithmic regret bounds for strongly convex problems.
- Conclusion: SC-Adagrad, SC-RMSProp, and RMSProp (Ours) perform well across different network models and datasets.
- Conclusion: The paper identifies explaining their strong deep-learning performance despite their strongly convex design as a future research direction.