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

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.

References in corpus (9)

• On the Convergence of Adam and Beyond
• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• When is a Convolutional Filter Easy To Learn?
• Online Learning to Rank in Stochastic Click Models
• Adaptive Regret of Convex and Smooth Functions
• Strongly Adaptive Online Learning
• Online Gradient Descent in Function Space

Cited by in corpus (3)

• A Simple Convergence Proof of Adam and Adagrad
• A new regret analysis for Adam-type algorithms
• Parallel and distributed asynchronous adaptive stochastic gradient methods