{'fraction_non_alphanumeric': 0.03416322429384839, 'fraction_numerical': 0.011767332812325556, 'mean_word_length': 4.375825231064698, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network

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.


Introduction
Online learning is the process of dynamically incorporating knowledge of the geometry of the data observed in earlier iterations to perform more informative learning in later iterations, as opposed to standard machine learning techniques which provide an optimal predictor after training over the entire dataset. Online learning is a preferred paradigm in situations where the algorithm has to dynamically adapt to new patterns in the dataset, or when the dataset itself is generated as a function of time, i.e. stock price prediction. Online learning is also used when the dataset itself is computationally infeasible to be trained over the entire dataset.
In standard online learning it is assumed that a finite number of samples is encountered however in real world streaming setting an infinite number of samples is observed (e.g., Twitter is streaming since inception and will continue to do so for foreseeable future). The performance of an online learning algorithm on early examples is negligible when measuring the performance or making predictions and decisions on the later portion of a dataset (the performance of an algorithm on tweets from ten years ago has very little bearing on its performance on recent tweets). The problem can be tackled by restarting, however, it is challenging to determine when to restart. For this reason we propose a metric which forgets about samples encountered a long time ago. Consequently, we introduce a performance metric, regret with rolling window, which measures the performance of an online learning algorithm over a possible infinite size dataset. This metric also requires an adaptation of prior algorithms, because, for example, a diminishing learning rate has poor performance on an infinite data stream.
Stochastic gradient descent (Sgd) [27] is a widely used approach in areas of online machine learning, where the weights are updated each time a new sample is received. Furthermore, it requires a diminishing learning rate in order to achieve a high-quality performance. It has been empirically observed that, in order to reduce the impact of the choice of the learning rate and conduct stochastic optimization more efficiently, the adaptive moment estimation algorithm (Adam) [16] and its extensions ([20], [22]) are another type of popular methods, which store an exponentially decaying average of past gradients and squared gradients and applies adaptive learning rate. (In standard gradient descent algorithms we use the term learning rate, while in adaptive learning rate algorithms we call stepsize the hyperparameter that governs the scale between the weights and the adjusted gradient.) In spite of this, no contribution has been made to the case where the regret is computed in a rolling window. Moreover, applying a diminishing learning rate or stepsize to regret with rolling window is not a good strategy, otherwise, the performance is heavily dependent on the learning rate or stepsize and the rank of a sample. Namely, regret with rolling window requires a constant learning rate or stepsize.
Standard online setting has been studied in the convex setting. With improvements in computational power resulting from GPUs, deep neural networks have been very popular in a variety of AI problems recently. A core application of online learning is online web search and recommender systems [28] where deep learning solutions have recently emerged. At the same time, online learning based on deep neural networks has become an integral role in many stages in finance, from portfolio management, algorithmic trading, to fraud detection, to loan and insurance underwriting. To this end we focus not only on convex loss functions, but also on deep neural networks.
In this work, we propose a new family of efficient online subgradient methods for both general convex functions and a two-layer ReLU neural network based on regret with rolling window metric. More precisely, we first present an algorithm, namely convergent Adam (convgAdam), designed for general strictly convex functions based on gradient descent using adaptive learning rate and inspired by the work of [22]. convgAdam is a more general algorithm that can dynamically adapt to an arbitrary sequence of strictly convex functions. In the meanwhile, we experimentally show that convgAdam outperforms state-of-the-art, yet non-adaptive, online gradient descent (OGD) [27]. Then, we propose an algorithm, called deep neural network gradient descent (dnnGd), for a two-layer ReLU neural network. dnnGd takes standard gradient first, then it rescales the weights upon receiving each new sample. Lastly, we introduce a new algorithm, deep neural network Adam (dnnAdam), which uses an adaptive learning rate for the two-layer ReLU neural network. dnnAdam is first endowed with long-term memory by using gradient updates scaled by square roots of exponential decaying moving averages of squared past gradients and then it rescales weights with every new sample.
In this paper, we not only propose a new family of gradient-based online learning algorithms for both convex and non-convex loss functions, but also present a complete technical proof of regret with rolling window for each of them. For strongly convex functions, given a constant learning rate, we show that convgAdam attains regret with rolling window which is proportional to the square root of the size of the rolling window, compared to the true regret O(log(T ) √ T ) of AMSGrad [22]. Besides, we not only point out but also fix the problem in the proof of regret for AMSGrad later in this paper. Table 1 in Appendix A.2 summarizes all regret bounds in various settings, including the previous flawed analyses. Furthermore, we prove that both dnnGd and dnnAdam attain the same regret with rolling window under reasonable assumptions for the two-layer ReLU neural network. The strongest assumption requires that the angle between the current sample and weight error is bounded away from π/2. Although dnnGd and dnnAdam require some assumptions, these two algorithms have a higher probability to converge than other flavors of Adam due to the convergence analyses provided in Section 5. In summary, we make the following five contributions.
• We introduce regret with rolling window that is applicable in data streaming, i.e., infinite stream of data.
• We provide a proof of regret with rolling window which is proportional to the square root of the size of the rolling window when applying OGD to an arbitrary sequence of convex loss functions.
• We provide a convergent first-order gradient-based algorithm, i.e. convgAdam, employing adaptive learning rate to dynamically adapt to the new patterns in the dataset. Furthermore, given strictly convex functions and a constant stepsize, we provide a complete technical proof of regret with rolling window. Besides, we point out a problem with the proof of convergence of AMSGrad [22], which eventually leads to O(log(T ) √ T ) regret in the standard online setting, and we provide a different analysis for AMSGrad which obtains O( √ T ) regret in standard online setting by using our proof technique.
• We propose a first-order gradient-based algorithm, called dnnGd, for the two-layer ReLU neural network. Moreover, we show that dnnGd shares the same regret with rolling window with OGD when employing a constant learning rate.
• We further develop an algorithm, i.e. dnnAdam, based on adaptive estimation of lower-order moments for the two-layer ReLU neural network. At the same time, we argue that dnnAdam shares the same regret with rolling window with convgAdam when employing a constant stepsize.
• We present numerical results showing that convgAdam outperforms state-of-art, yet not adaptive, OGD.
The paper is organized as follow. In the next section, we review several works related to Adam, analyses of two-layer neural networks and regret in online convex learning. In Section 3, we state the formal optimization problem in streaming, i.e., we introduce regret with rolling window. In the subsequent section we propose the two algorithms in presence of convex loss functions and we provide the underlying regret analyses. In Section 5 we study the case of deep neural networks as the loss function. In Section 6 we present experimental results comparing convgAdam with OGD.

Related Work
Adam and its variants: Adam [16] is one of the most popular stochastic optimization methods that has been applied to convex loss functions and deep networks which is based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients. In many applications, e.g. learning with large output spaces, it has been empirically observed that it fails to converge to an optimal solution or a critical point in nonconvex settings. A cause for such failures is the exponential moving average, which leads Adam to forget about the influence of large and informative gradients quickly [4]. To tackle this issue, AMSGrad [22] is introduced which has long-term memory of past gradients. AdaBound [20] is another extension of Adam, which employs dynamic bounds on learning rates to achieve a gradual and smooth transition from adaptive methods to stochastic gradient. Though both AMSGrad [22] and AdaBound [20] provide theoretical proofs of convergence in a convex case, very limited further research related to Adam has be done in a non-convex case while Adam in particular has become the default algorithm leveraged across many deep learning frameworks due to its rapid training loss progress. Unfortunately, there are flaws in the proof of AMSGrad, which is explained in a later section and articulated in Appendix A.
Two-layer neural network: Deep learning achieves state-of-art performance on a wide variety of problems in machine learning and AI. Despite its empirical success, there is little theoretical evidence to support it. Inspired by the idea that gradient descent converges to minimizers and avoids any poor local minima or saddle points ([18] [24] prove that there is no spurious local minima in a two-hidden-unit ReLU network. However, Luo & Wu make an assumption that the 2 nd layer is fixed, which does not hold in applications. Li & Yuan [19] also make progress on understanding algorithms by providing a convergence analysis for Sgd on special two-layer feedforward networks with ReLU activations, yet, they specify the 1 st layer as begin offset by "identity mapping" (mimicking residual connections) and the 2 nd layer as the 1 -norm function. Additionally, based on their work [10], Du et al [9] give the 2 nd layer more freedom in the problem of learning a two-layer neural network with a non-overlapping convolutional layer and ReLU activation. They prove that although there is a spurious local minimizer, gradient descent with weight normalization can still recover the true parameters with constant probability when given Gaussian inputs. Nevertheless, the convergence is guaranteed when the 1 st layer is a convolutional layer.
Online convex learning: Many successful algorithms and associated proofs have been studied and provided over the past few years to minimize regret in online learning setting. Zinkevich [27] shows that the online gradient descent algorithm achieves regret O( √ T ), for an arbitrary sequence of T convex loss functions (of bounded gradients) and given a diminishing learning rate. Then, Hazan et al [13] improve regret to O(log(T )) when given strictly convex functions and a diminishing learning rate. The idea of adapting first order optimization methods is by no means new and is also popular in online convex learning. Duchi,Hazan & Singer [11] present AdaGrad, which employs very low learning rates for frequently occurring features and high learning rates for infrequent features, and obtain a comparable bound by assuming 1-strongly convex proximal functions. In a similar framework, Zhu & Xu [26] extend the celebrated online gradient descent algorithm to Hilbert spaces (function spaces) and analyzed the convergence guarantee of the algorithm. The online functional gradient algorithm they propose also achieves regret O( √ T ) when given convex loss functions. In all these algorithms, the loss function is required to be convex or strongly convex and the learning rate or step size must diminish. However, no work about regret analyses of online learning applied on deep neural networks (non-convex loss functions) has been done. Adaptive regret: Recently, adaptive regret has been studied in the setting of prediction with expert advice (PEA) in online learning. Adaptive regret measures the maximum difference of the performances of an online algorithm and the offline optimum for any consecutive τ samples in total T rounds, while our regret measures the maximum difference of the performances in the whole history. Existing online algorithms are closely related in the sense that adaptive algorithms designed are usually built upon the PEA algorithms. The concept of adaptive regret is formally introduced by Hazan and Seshadhri [14]. They also propose a new algorithm named follow the leading history (FLH), which contains an expert-algorithm, a set of intervals and a meta-algorithm. Then Daniely in [7] extends this idea by introducing strongly adaptive algorithms, which provide a regret bound O(log(s + 1) |I| where s is the end point of the rolling window and |I| is the size of the window. Later on, Zhang in [25] applies the concept of the adaptive learning rate to adaptive regret and proposes adaptive algorithms for convex and smooth functions, and finally obtains a regret bound O( ( s t=r f t (ω)) log(s) log(s − r)), where f t (ω) is the loss function for the t'th sample given any ω in the corresponding domain, and r and s are the starting and ending data points of the interested sequence. Notice that in conjunction with infinite streaming, s blows up and eventually dominates the regret bound. Although the concept of the adaptive regret is similar to our regret with rolling window, adaptive regret relies on other existing online algorithms which not only use diminishing learning rate but also bring extra error. In regret with rolling window, we consider these two aspects together (infinite time stream and the issue of learning rates) and propose a new family of online algorithms which use a constant learning rate and achieve a more robust regret. Specifically, our regret bound is O( √ T ), which does not depend of the position of the window.

Regret with Rolling Window
We consider the problem of optimizing regret with rolling window, inspired by the standard regret ([27], [1], [21]). The problem with the traditional regret is that it captures the performance of an algorithm only over a fixed number of samples or loss functions. In most applications data is continuously streamed with an infinite number of future loss functions. The performance over any finite number of consecutive loss functions T is of interest. The concept of regret is to compare the optimal offline algorithm with access to T contiguous loss functions with the performance of the underlying online algorithm. Regret with rolling window is to find the maximum of all differences between the online loss and the loss of the offline algorithm for any T contiguous samples. More precisely, for an infinite sequence {z t , y t } ∞ t=1 , where each feature vector z t ∈ R d is associated with the corresponding label y t , given fixed T and any p, we first define ω * p ∈ argmin ω p+T t=p f t (ω), which corresponds to the optimal solution of the offline algorithm. In general, f t (ω) = loss(x t , y t ; ω), e.g. f t (ω) = ω T x t − y t 2 if the linear regression model is applied and the mean square error is used. Then, we consider where f t is a function of sample z t . The regret with rolling window metric captures regret over every T consecutive loss functions and it is aiming to assess the worst possible regret over every such sequence. Note that if we have only T loss functions corresponding only to p = 1, then this is the standard regret definition in online learning. The goal is to develop algorithms with low regret with rolling window. We prove that regret with rolling window can be bounded by O( √ T ). In other words, the average regret with rolling window approaches zero.

Convex Setting
In the convex setting, we propose two algorithms with a different learning rate or stepsize strategy and analyze them with respect to (1) in the streaming setting.

Algorithms
Algorithms in standard online setting are almost all based on gradient descent where the parameters are updated after each new loss function is received based on the gradient of the current loss function. A challenge is the strategy to select an appropriate learning rate. In order to guarantee good regret the learning rate is usually decaying. In the streaming setting, we point out that a decaying learning rate is improper since far away samples (very large p) would get a very small learning rate implying low consideration to such samples. In conclusion, the learning rate has to be a constant or it should follow a dynamically adaptive learning algorithm, i.e. ADAM. The algorithms we provide for solving (1) in the streaming setting are based on gradient descent and one of the just mentioned learning rate strategies.
In order to present our algorithms, we first need to specify notation and parameters. In each algorithm, we denote by η and g t the learning rate or stepsize and a subgradient of loss function f t associated with sample (z t , y t ), respectively. Additionally, we employ to represent the element-wise multiplication between two vectors or matrices (Hadamard product). However, for other operations we do not introduce new notation, e.g., for elementwise division (/) and square root ( √ ), since these two operations are written differently when representing standard matrix or vector operations. We start with OGD which mimics gradient descent in online setting and achieves O( √ T ) regret with rolling window when given constant learning rate. Algorithm 1 is a twist on Zinkevich's Online Gradient Descent [27]. OGD updates its weight when a new sample is received in step 4. In addition, OGD uses constant learning rate in the streaming setting so as to efficiently and dynamically learn the geometry of the dataset. Otherwise, if a diminishing learning rate is applied, OGD misses informative samples which arrive late due to the extremely small learning rate and leads to O(T ) regret with rolling window (this is trivial to observe if the loss functions are bounded). Regret of O( √ T ) is achieved in the streaming setting if learning rate η = 1/ √ T . Constant learning rates have a drawback by treating all features equally. Consequently, we adapt ADAM to online setting and further extend it to streaming. Algorithm 2, inspired by ADAM [16] and AMSGrad [22], has regret with rolling window also of the order O( √ T ) given constant stepsize η as shown in the next section. The key difference of convgADAM with AMSGrad is that it maintains the same ratio of the past gradients and the current gradient instead of putting more and more weight on the current gradient and losing the memory of the past gradients fast. In Algorithm 2, convgAdam records exponential moving average of gradients and moments in step 5 and 6.
Step 7 guarantees thatv t is the maximum of all v t until the present time step. Then, step 8 gives the adaptive update rule by using the maximum value of v t to normalize the running average of the gradient at time t. Besides, constant stepsize η is crucial to make convgAdam well-performed due to the aforementioned reason with a potential decaying learning rate or stepsize.
In step 8, we observe thatv ti = 0 for a feature i implies m ti = 0, therefore, we retain the foregoing weight ω ti as the succeeding weight ω t+1,i . In other words, in this case we define Algorithm 1 Online Gradient Descent 1: Positive parameter η 2: for t = 0, 1, 2, · · · do 3:

Analyses
In this section, we provide regret analyses of OGD and convgAdam showing that both of them attain regret with rolling window which is proportional to the square root of the size of the rolling window given a constant learning rate or stepsize in the streaming setting. For inner (scalar) products, given the fact that a, b = a T b = b T a for two vectors a and b, in the rest of the paper, for short expressions we use a T b, but for longer we use a, b .
We require the following standard assumptions.
Assumption 1: 1. There exists a constant D ∞ , such that ω t ∞ ≤ D∞ 2 , for any t ∈ N. 2. The loss gradients f t (ω t ) are bounded, i.e., for all ω t such that 3. Functions f t (ω) are convex and differentiable with respect to ω for every t ∈ N.
4. Functions f t (ω) are strongly convex with parameter H, i.e., for allω andω, and for The first condition in Assumption 1 assumes that ω t are bounded. This assumption can be removed by further complicating certain aspects of the upcoming proofs. This extension is discussed in Appendix A.1 for the sake of clarity of the algorithm. In 2 from Assumption 1, the gradient of the loss function is requested to be upper bounded. Notice that each loss function f t is enforced to be differentiable and convex in 3, whereas f t is required to be strictly convex with parameter H in 4. All these are standard assumptions.
We first provide the regret analysis of OGD.
Theorem 1. If 1-3 in Assumption 1 hold, and η = η 1 √ T for any positive constant η 1 , the sequence ω t generated by OGD achieves The proof is provided in Appendix B. Under the assumptions in Assumption 1, by finding a relationship for the sequence of the weight error ω t − ω * p and employing the property of convexity from condition 3 from Assumption 1, we prove that OGD obtains the regret with rolling window which is proportional to the square root of the size of the rolling window when given the constant learning rate. This is consistent with the regret of OGD in the standard online setting.
The analysis of OGD is not totally new but still has some important differences. Also, when using a diminishing learning rate, given strongly convex f t , it has been proven in [13] by Hazan that OGD obtains logarithmic regret. However, this is not possible even given strongly convex f t when using a constant learning rate, which should be clear after reading our regret analysis of OGD and comparing it with the regret analysis in [13].
If OGD is an analogue to the Gradient Descent optimization method for the online setting, then convgAdam is an online analogue of Adam, which dynamically incorporates knowledge of the characteristics of the dataset received in earlier iterations to perform more informative gradient-based learning. Next, we show that convgAdam achieves the same regret with rolling window given a constant stepsize.
Theorem 2. If Assumption 1 holds, and β 1 and β 2 are two constants between 0 and 1 such that λ := β 1 √ β 2 < 1 and β 1 ≤ Hη 1+Hη , then for η = η 1 √ T for any positive constant η 1 , the sequence ω t generated by convgAdam achieves The proof is provided in Appendix C. The very technical proof follows the following steps. Based on the updating procedure in steps 4-8, we establish a relationship for the sequence of the weight error ω t − ω * p . Meanwhile, considering condition 4 in Assumption 1, we obtain another relationship between the loss function error f t (ω t ) − f t (ω * p ) and ω t − ω * , f t (ω t ) . Assembling these two relationships provide a relationship between the weight error ω t − ω * and the loss function error f t (ω t ) − f t (ω * ). By deriving upper bounds for all of the remaining terms based on conditions from Assumption 1, we are able to argue the same regret with rolling window of O( √ T ). In the regret analysis of AMSGrad [22], the authors forget that the stepsize is 1 √ t and take the hyperparameter η to be exponentially decaying for granted without assumptions which eventually leads to O(T √ T ) regret in standard online setting. Our analysis is flexible enough to extend to AMSGrad and a slight change to our proof yields the O( √ T ) regret for AMSGrad. The changes in our proof to accommodate standard online setting and AMSGrad are stated in Appendix A.2. Moreover, the proof of convergence of AMSGrad in [22] uses a diminishing stepsize while our proof is valid for both constant and diminishing stepsizes. Likewise, for AdaBound [20], the right scale of the stepsize is also missed and the regret should be O(T ), which is discussed in more detail in Appendix A.2. In this section we also discuss how to amend our proof to provide the O( √ T ) regret bound in standard online setting for AdaBound.
Theorem 2 guarantees that convgAdam achieves the same regret with rolling window as OGD for convex loss functions. On the other hand, very limited work has been done about regret for nonconvex loss functions, e.g. the loss function of a two-layer ReLU neural network. In the following section, we argue that both dnnGD and dnnAdam attain the same regret with rolling window if the initial starting point is close to an optimal offline solution and by using a constant learning rate or stepsize. In addition to a favorable starting point, further assumptions are needed.

Two-Layer ReLU Neural Network
In this section we consider a two layer neural network with the first hidden layer having an arbitrary number of neurons and the second hidden layer has a single neuron. The underlying activation function is a probabilistic version of ReLU and minimum square error is considered as the loss function. First of all, the optimization problem of such a two-layer ReLU neural network is neither convex nor convex (and clearly non linear), therefore, it is very hard to find a global minimizer. Instead, we show that our algorithms achieve O( √ T ) regret with rolling window when the initial point is close enough to an optimal solution.
Neural networks as classifiers have a lot of success in practice, whereas a formal theoretical understanding of the mechanism of why they work is largely missing. Studying a general neural network is challenging, therefore, we focus on the proposed two-layer ReLU neural network. For a dataset {z t , y t } ∞ t=1 , the standard loss function of the two-layer neural network , where σ represents the ReLU activation function applied element-wise, ω 1,t is the parameter vector, and ω 2,t is the parameter matrix. It turns out that ReLU is challenging to analyze since nesting them yields many combinations of the various values being below zeros. One way to get around this is to consider a probabilistic version of ReLU and capturing expected loss, Luo & Wu [24].
To this end we treat ReLU as a random Bernoulli variable in the sense that Pr(σ( Wu [24] in the standard offline setting analyze f t (ω 1,t , ω 2,t ) for the probabilistic version of ReLU. For our online analyses we need to slightly alter the setting by introducing two independent identically distributed random variables σ 1 and σ 2 and the loss function as follows There is a crucial property of f t which is positive-homogeneity. That is, for any c > 0, f t (cω 1 , ω 2 c ) = f t (ω 1 , ω 2 ). This property allows the network to be rescaled without changing the function computed by the network.
For two-layer ReLU neural network, given (ω p 1, * , ω p 2, * ) ∈ argmin ω p+T t=p E σ 1 ,σ 2 f t (ω 1,t , ω 2,t ), we consider regret with rolling window as Next, we propose two algorithms with different learning rates or stepsizes for the two-layer neural network and analyze them with respect to (3).

Algorithms
In order to present the algorithms, let us first introduce notation and parameters. For any matrix A and vector x, let [A] ij and [x] i denote the element in the i th row and j th column of matrix A and i th coordinate of vector x, respectively. Similarly, we use [A] ·j ([A] i· ) to represent the j th column (i th row) of matrix A. Next, in order to be consistent, we also denote η and g 1,t , g 2,t as the learning rate or stepsize and a subgradient of loss function f t associated with sample (z t , y t ), respectively. Let ξ 1 and ξ 2 be constants. Lastly, in order to be consistent with the notation in the convex setting, we employ to represent the element-wise multiplication between vectors or matrices while using standard division and square root notation for the corresponding operations element-wise in vectors and matrices.
We start with dnnGd which is the algorithm with a fixed learning rate, Algorithm 3. We show later that its regret with rolling window is O( √ T ). dnnGD is an analogue of the gradient descent optimization method for the online setting with the two-layer ReLU neural network, and at the same time it is an extension of OGD. Different from OGD, dnnGD not only modifies weights at a given iteration by following the gradient direction, but it also rescales weights based on the domain constraint in step 6, i.e. ω 1,t has a fixed norm. Then, ω 2,t is rescaled at the same time to impose positive-homogeneity in step 7.
Algorithm 3 Deep NN Gradient Descent 1: Positive parameter η > 0 2: for t = 0, 1, 2, · · · do 3: Sample σ 1 , σ 2 4: Taking the drawbacks of a constant learning rate into consideration, we propose Algorithm 4, which is an extension of convgAdam for the two-layer ReLU neural network and likewise attains O( √ T ) regret with rolling window. In dnnAdam, the stochastic gradients computed in steps 4 and 5 are different than those in dnnGD. This is due to challenges in establishing the regret bound. Nevertheless, the stochastic gradients are unbiased estimators of gradients of the loss function. An alternative is to have four samples, two per gradient group. This would also enable the regret analysis, however we only employ two of them so as to reduce the variance of the algorithm. dnnAdam records exponential moving average of gradients and moments in steps 6 -9.
Step 10 modifies v 2,t to be a matrix with same value in the same column. This is a divergence from standard ADAM which does not have this requirement. The modification is required for the regret analysis. Then, steps 11 and 12 guarantee that {v 1,t } and {v 2,t } are nondecreasing sequences element-wise. Lastly, we update weights and also perform the rescaling modification to dnnAdam in steps 13 and 14. Additionally, we apply the same strategy as we mention in convgAdam when . Thus, we define m 1,t / v 1,t i = 0 0 = 0 and m 2,t / v 2,t ij = 0 0 = 0. Therefore, we maintain the weights from the last iteration.

Analyses
In this section, we discuss regret with rolling window bounds of dnnGd and dnnAdam showing that both of them attain regret with rolling window proportional to the square root of the size of the rolling window. Before establishing the regret bounds, we first require the following assumptions.
4. There exists 0 < < π/2 such that 5. There exits a positive constant µ such that µ ≤ min i,t, As Kawaguchi assumed in [15] and other works ([8], [5], [6]), we also assume that σ's are Bernoulli random variables with the same probability of success and are independent from input z t 's and weights ω's in 1 from Assumption 2. 1 Condition in 2 from Assumption 2 states that the optimal expected loss is zero. This is also assumed in other prior work in offline, e.g.
[24], [9]. The 3 rd condition in Assumption 2 is an extension of 1 in Assumption 1. Likewise, the constraints on ω 1,t and ω 2,t can be removed by further introducing technique discussed in Appendix A.1, and consequently, g 1,t and g 2,t are bounded due to steps 4 and 5. The next to the last condition in Assumption 2 requires that a new coming sample has to be beneficial to improve current weights. More precisely, we interpret the difference between the current weights and optimal weights as an error that needs to be corrected. Then, a new sample which is not relevant to the error vector is not allowed. In other words, we assume that the algorithm does not receive any uninformative samples. Condition 5 from Assumption 2 assumes that any nonzero |[v 1,t ] i | is lower bounded by a constant µ for all t and i. It is a weak constraint since [v 1,t ] i ≥ [v 1,t−1 ] i for any t and i. In practice, we can modify it by only memorizing the first nonzero value in each coordinate and finding the smallest among these values. Otherwise, if all of [v 1,t ] i = 0, then we can set µ = 1 by default.
The regret statement for dnnGd is as follows.
At the same time, our proof is flexible enough to extend to standard online setting. For a constant learning rate, Appendix D provides the necessary details for the standard case.
1 In general, the distribution of the Bernoulli random variable representing the ReLU activation function is not required to be stationary for all t.
In summary, regret of O( √ T ) is achieved. We note that such a result has only been known for the diminishing learning rate and thus we extend the prior knowledge by covering the constant learning rate case.
The adaptive learning setting algorithm dnnAdam has the same regret bound as stated in the following theorem.
The structure of the technical proof is similar to that of Theorem 3. We first establish a relationship for the sequence of the weight error ω T 1,t ω 2,t − ω T 1, * ω 2, * by multiplying 4 v 2,t . Then, using the definitions of β's, λ's and γ's, we bound all the terms without the stepsize by constants except those which potentially can contribute to the loss function. To this end, we obtain a relationship between the weight error ω T 1,t ω 2,t − ω T 1, * ω 2, * and the loss function. Finally, combined with step12 and the law of iterated expectation, we are able to argue O( √ T ) regret with rolling window for dnnAdam. Likewise, we are able to extend the proof of Theorem 4 to the standard online setting for dnnAdam. We do not need to make any change to establish O( √ T ). For diminishing stepsize µ, a slight change to the proof is indeed. Details are provided in Appendix A.2.

Numerical Study
In this section, we compare the convgAdam method with OGD [27] for solving problem (1) with a long sequence of data points (mimicking streaming). We conduct experiments on the MNIST8M dataset and two other different-size real datasets from the Yahoo! Research Alliance Webscope program. For all of these datasets, we train multi-class hinge loss support vector machines (SVM) [23] and we assume that the samples are streamed one by one based on a certain random order. For all the figures provided in this section, the horizontal axis is in 10 5 scale. Moreover, we set β 1 = 0.8 and β 2 = 0.81 in convgAdam. We mostly capture the log of the loss function value which is defined as max p∈N min (ωt) t∈N T +p t=p f t (ω t ).

Multiclass SVM with Yahoo! Targeting User Modeling Dataset
We first compare convgAdam with OGD using the Yahoo! user targeting and interest prediction dataset consisting of Yahoo user profiles 2 . It contains 1,589,113 samples (i.e., user profiles), represented by a total of 13,346 features and 380 different classification problems (called labels in the supporting documentation) each one with 3 classes.
First, we pick the first label out and conduct a sequence of experiments with respect to this label. The most important results are presented in Figure 1 for OGD and Figure 2 for convgAdam. In Figures 1(a) and 2(a), we consider the cases when the learning rate or step size varies from 0.1 to 5 · 10 −6 while keeping the order and T fixed at 1,000. Figures 1(b) and 2(b) provide the influence of the order of the sequence. Figures 1(c) and 2(c) represent the case where T varies from 10 to 10 5 with a fixed learning rate or step size. Lastly, in Figure  2(d), we compare the performance of convgAdam and OGD with certain learning rates and step sizes.
In these plots, we observe that convgAdam outperforms OGD for most of the learning rates and step sizes, and definitely for promissing choices. More precisely, in Figure 1(a) and 2(a), we discover that 0.1/1000 and 3/ √ 1000 are two high-quality learning rate and stepsize values which have relatively low error and are learning for OGD and convgAdam, respectively. Therefore, we apply those two learning rates for the remaining experiments on this dataset. In Figures 1(b) and 2(b), we observe that the perturbation caused by the change of the order is negligible especially when compared to the loss value, which is a positive characteristic. Thus, in the remaining experiments, we no longer need to consider the impact of the order of the sequence. From Figure 1(c) and Figure 1(d), we discover that the loss and T have a significantly positive correlation as we expect. Notice that changing T but fixing the learning rate or stepsize essentially means containing more samples in the regret, in other words, the regret for T = 100 is roughly 10 times the regret for T = 10. Since the pattern in the figures is preserved for the different T values for OGD and convgAdam, in the remaining experiments we fix T . In Figure 2(c), we discover that too big T or too small T causes poor performance and therefore, for the remaining experiments, we set T = 1, 000 whenever T is fixed. From Figure 2(d), we observe that convgAdam outperforms OGD. After studying the algorithms on the first label, we test them on the next four labels. In Figure 3, we compare the performance of convgAdam for different T and the difference with OGD on the four labels. In these plots, we observe that T = 1000 provides a more stable and better performance than the other two values. Moreover, convgAdam outperforms OGD for all considered learning rates and step sizes.  [2] Baldi, P. and Hornik, K. (1989). Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58.

A Extensions
We first introduce techniques to guarantee boundedness of the weight ω, i.e. how to remove condition 1 in Assumption 1. We then point out problems in the proofs of AMSGrad [22] and AdaBound [20] and provide a different proof for AMSGrad.

A.1 Unbounded Case
Projection is a popular technique to guarantee that a weight does not exceed a certain bound ([3], [13], [11], [20]). For unbounded weightω, we introduce the following notation. Given convex sets P 1 , P 2 , vectors ω 1 , ω 1 , g 1 and matrixv, we define projections Projection Π is the standard projection which maps vectorω into set P 1 . If an optimal weight ω * is such that ω * ∈ P 1 , then we have which could be directly applied in the proofs of Theorem 1 and 2. For Π 1 and Π 2 , we could regard them as a combination of two standard projections. Note that, for the outer projection, we require that it does not affect the product of ω T 1 ω 2 , which could be done by projection methods for linear equality constraints. In this way, we have which could also be directly applied in the proofs of Theorem 3 and 4. Without assuming that β 1t is exponentially decaying, it is questionable to establish O( √ T )

A.2 Standard setting of Adam
. Although this questionable term can be bounded by assumptions on β 1t , the last term in Theorem 4 is O(log(T ) d i=1 g 1:T,i 2 ) = O(log(T ) √ T ) since g 1:T,i is the concatenation of the gradients from 0 to current time T in the i th coordinate. Moreover, the authors argue that decaying β 1t is crucial to guarantee the convergence, however, our proof shows O( √ T ) regret for AMSGrad with constant β and both constant and diminishing stepsizes, which is more practically relevant. For a diminishing stepsize, the slight change we need to make in the proof is that η t needs to be considered together with v t,j in (14) and the rest of proof of Theorem 2. Applying the fact that   Proof. For any p ∈ N and fixed T , from step 4 in Algorithm 1, for any ω * , we obtain which in turn yields Applying convexity of f t yields Inserting (4) into (5) gives By summing up all differences, we obtain The second inequality holds due to 2 in Assumption 1 and the last inequality uses 4 in Assumption 1 and the definition of η. Since (6) holds for any p and ω * , setting ω * = ω * p for each p yields the statement in Theorem 1. Proof of Lemma 1. By the definition ofv t , for any t = p, p + 1, · · · , T + p, we obtain

C Regret with Rolling Window Analyses of convgAdam
The second equality follows from the updating rule of Algorithm 2. The second inequality follows from the Cauchy-Schwarz inequality, while the third inequality follows from the inequality t i=1 β t−i 1 ≤ 1 1−β 1 . Using (7) for all time steps yields We first bound the first term in (8) for each j as follows, The first inequality follows from the fact that T +p t=i λ T +p−t < 1 1−λ and the last inequality is due to 2 in Assumption 1. Using a similar argument, we further bound the second term in (8) as follows, Inserting (9) and (10) into (8) implies This completes the proof of the lemma.
In order to establish the regret analysis of Algorithm 2, we further need the following intermediate result. ( The first inequality follows from the Cauchy-Schwarz inequality. The second and the last inequalities use the fact that t i=1 β t−i 1 ≤ 1 1−β 1 . The third inequality is due to 2 in Assumption 1. This completes the proof of the lemma.

Proof of Theorem 2
Proof. Based on the update step 8 in Algorithm 2 and given any ω * ∈ R d , we obtain (11) The first inequality uses the same argument as those used in Theorem 1. Rearranging (11) gives From the strong convexity property of f t in 4 in Assumption 1, we obtain Using (12) in the above inequality and summing up over all time steps yields We proceed by separating (13) into 3 parts and find upper bounds for each one of them. Considering the first part in (13), we have T +p Sincev t,j is maximum of all v t,j for each j until the current time step, i.e. v t,j − v t−1,j ≥ 0, by using 1 in Assumption 1, (14) can be further bounded as follows, By the definition ofv t in step 6 in Algorithm 2, for any t and j, we have The last equality is due to the setting of the stepsize, i.e. η = η 1 √ T . For the second term in (13), from the relationship between β 1 and H, we obtain which in turn yields Thus, (16) guarantees negativity of the second term in (13). For the third term in (13), by using Lemmas 1 and 2, we assert The desired result follows directly from (13), (15), (16) and (17).

D Regret with Rolling Window Analysis of dnnOGD for Two-Layer ReLU Neural Network
For a two-layer ReLU neural network, we first introduce F t that records all previous iterates up until t.
Lemma 3. If conditions 1 and 2 hold from Assumption 2, we have Proof of Lemma 3. Based on condition 2 in Assumption 2, we obtain On the other hand, we get which in turn yields This completes the proof of the lemma.
Lemma 4. Under the conditions assumed in Theorem 3, we have Proof of Lemma 4. From steps 4 and 5, we have Similarly, This completes the proof of the lemma.
Therefore, it is sufficient to show thatv 2,t is bounded for all t. For each entry in the matrix, By combining with the fact that g 2 is bounded due to step 5 and the boundedness of ω 1,t , ω 2,t , z t and y t from condition 3 in Assumption 2, Lemma 5 follows.