# Online Forecasting and Anomaly Detection Based on the ARIMA Model
## 2 Materials and Methods
### Online Algorithms Based on the ARIMA Model  
#### 2.2.1 Online Gradient Descent  
Generally, the maximum likelihood (ML) and prediction error (PE) methods with a non-convex error criterion function are used to find the optimal ARMA weights. Other algorithms (interested readers are directed to [18]) are also used to solve this problem, but they all have their drawbacks. For example, they may fail to deliver the global optima.  
The use of classical online algorithms with convex optimization methods, in this case, is impossible since the moving average model is nonlinear in its parameters and, therefore, to estimate the parameters, it is necessary to use nonlinear estimation procedures [6]. In turn, noise components \(\{\epsilon_{t}\}_{t=1}^{T}\) are required at each iteration when updating the model weights \((\alpha,\beta)\) and at each iteration of the prediction procedure.  
The solution to this problem may be the ARMA Online Gradient Descent algorithm (ARMA-OGD) from [12] (see Algorithm 1, where \(TLM_{\text{max}}q\) is the maximum value of the Lagrange multipliers [12]). In this case, all terms of an MA model are replaced by additional autoregressive terms. The ARIMA model (\(p\), \(d\), \(q\)) is converted to the ARIMA model (\(p+m,d,0\)), where \(m\in\mathbb{N}\) is a constant, meaning that the algorithm with the coefficient vector \(\gamma\in\mathbb{R}^{p+m}\) attains a sublinear regret bound against the best ARMA model (\(p\), \(d\), \(q\)) prediction in hindsight, with weak assumptions of the noise terms. The sublinear regret with computational simplicity indicates the acceptableness of this approach. However, this algorithm requires the following assumptions:  
1. Noise components are randomly and independently distributed with zero expectations and satisfy the following conditions: \(\mathbb{E}[|\epsilon_{t}|]<M_{\text{max}}<\infty\) and \(\mathbb{E}[\ell_{t}(X_{t},X_{t}-\epsilon_{t})]<\infty\) for every \(t\).
2. The loss function \(\ell_{t}\) must satisfy a Lipschitz condition [19].
3. Autoregressive weight coefficients \(\alpha_{i}\) satisfy \(|\alpha_{i}|<1\). This assumption is necessary to restrict the decision set [12], but it is not necessary or sufficient for stability. In fact, the absolute values of autoregressive weight coefficients can be bounded to any other real number.
4. Moving average weight coefficients \(\beta_{i}\) satisfy \(\sum_{i=1}^{q}|\beta_{i}|<1-\varepsilon\) for some \(\varepsilon>0\).
5. The signal is bounded by the constant. Without the loss of generality, we assume that \(|X_{t}|<1\) for every \(t\).  
```
Input Hyperparameters \(p,d,q\), learning rate \(\eta\); Set \(m=\text{log}_{\text{max}}\Big{(}(TLM_{\text{max}}q)^{-1}\Big{)}\) For\(t\) from \(1\) to \(T-1\)do: Predict \(\widehat{X}_{t}\big{(}\gamma^{t}\big{)}=\sum_{i=1}^{p+m}\gamma_{i}\
abla^{d}X_ {t-i}+\sum_{i=0}^{d-1}\
abla^{i}X_{t-1}\); Get \(X_{t}\) and \(\ell_{t}^{\prime}\big{(}\gamma^{t}\big{)}=\ell_{t}\big{(}X_{t},\widehat{X}_{t} \big{(}\gamma^{t}\big{)}\big{)}\); Set \(\
abla_{t}=\
abla\ell_{t}^{\prime}\big{(}\gamma^{t}\big{)}\); Update \(\gamma^{t+1}\leftarrow\prod_{K}\Big{(}\gamma^{t}-\frac{1}{\eta}\
abla_{t} \Big{)}\) Endfor
```  
**Algorithm 1** Online Gradient Descent.