## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction
Even if the graph \(\mathcal{G}\) (and hence the GSO) is time-invariant, then \(\
u_{t}\) will be non-zero especially for small \(t\) since the solution \(\mathbf{S}_{t}^{*}\) may fluctuate due to insufficient data. Much like classic performance results in adaptive signal processing [49], here there is misadjustment due to the \"dynamics-induced noise\" \(\
u_{t}\) and hence the online algorithm will only converge to within a neighborhood of \(\mathbf{S}_{t}^{*}\). To better distill what determines the size of the convergence radius, define \(\tilde{L}_{t}:=\max_{\tau=0,\ldots,t}L_{\tau}\), \(\hat{\
u}_{t}:=\max_{\tau=0,\ldots,t}\
u_{\tau}\) and sum the geometric series in the right-hand side of (17) to obtain the simplified bound

\[\left\|\mathbf{S}_{t}-\mathbf{S}_{t}^{*}\right\|_{F}\leq\left(\tilde{L}_{t-1} \right)^{t}\left\|\mathbf{S}_{0}-\mathbf{S}_{0}^{*}\right\|_{F}+\frac{\hat{ \
u}_{t}}{1-\tilde{L}_{t-1}}. \tag{18}\]Further suppose \(m_{\tau}\geq m\) and \(M_{\tau}\leq M\) and the step-size chosen as \(\gamma_{\tau}=2/(m_{\tau}+M_{\tau})\), for all \(\tau=0,\ldots,t_{\tau}\). Then it follows that \(\hat{L}_{t}\leq(M-m)/(M+m)<1\). The misadjustment \(\hat{v}_{t}/(1-\hat{L}_{t-1})\) in (18) grows with \(\hat{v}_{t}\) as expected, and will also increase when the problem is badly conditioned (\(M\to\infty\) or \(m\to 0\)) because \(\hat{L}_{t}\to 1\). If one could afford taking \(i_{t}\) PG iterations (instead of a single one as in Algorithm 2) per time step \(t\), the performance gains can be readily evaluated by substituting \(\hat{L}_{t}=\prod_{\tau=0}^{t}\hat{L}_{\tau}^{i_{t}}\) in Theorem 1 to use the bound (17). In closing, we state dynamic regret bounds which are weaker than the performance guarantees in (17)-(18), but they do not require strong convexity assumptions. The proof of the following result can be found in [16] and is omitted here in the interest of brevity. **Theorem 2**. : _Let \(\hat{\mathbf{S}}_{t}^{*}=\frac{1}{t}\sum_{\tau=0}^{t-1}\mathbf{S}_{\tau}^{*}\) be the average trajectory of the optimal solutions of (13), and introduce \(\rho_{t}(\tau):=\left\|\hat{\mathbf{S}}_{t}^{*}-\mathbf{S}_{\tau}^{*}\right\|\) to capture the deviation of instantaneous solutions from this average trajectory. Define \(\delta_{t}:=\left\|g_{t+1}-g_{t}\right\|_{\infty}\) as a measure of the variability in \(F_{t}\). Suppose \(M_{\tau}\leq M\) and set the step-size \(\gamma_{\tau}=\frac{1}{M}\), for all \(\tau=0,\ldots,t\). Then for all \(t\geq 1\) the iterates \(\mathbf{S}_{t}\) generated by Algorithm 2 satisfy_

\[\frac{1}{t}\sum_{\tau=0}^{t-1}\left(F_{\tau}\left(\mathbf{S}_{ \tau}\right)-F_{\tau}\left(\mathbf{S}_{\tau}^{*}\right)\right) \leq\frac{M}{2t}\left\|\mathbf{S}_{0}-\hat{\mathbf{S}}_{t}^{*} \right\|_{F}^{2}\] \[\quad+\frac{1}{t}\left[F_{0}\left(\mathbf{S}_{0}\right)-F_{t-1} \left(\mathbf{S}_{t}\right)+\sum_{\tau=0}^{t-2}\delta_{\tau}+\sum_{\tau=0}^{t- 1}\rho_{t}(\tau)\left(N+\frac{M}{2}\rho_{t}(\tau)\right)\right]. \tag{19}\]

To interpret the result of Theorem 2, define \(\hat{\rho}_{t}:=\max_{\tau=0,\ldots,t-1}\rho_{t}(\tau)\) and \(\delta_{t}:=\max_{\tau=0,\ldots,t-2}\delta_{\tau}\). Using these definitions, the following simplified regret bound is obtained immediately from (19)

\[\frac{1}{t}\sum_{\tau=0}^{t-1}\left(F_{\tau}(\mathbf{S}_{\tau})-F_{\tau}( \mathbf{S}_{\tau}^{*})\right)\leq\frac{1}{t}\left[\frac{M}{2}\left\|\mathbf{S }_{0}-\hat{\mathbf{S}}_{t}^{*}\right\|^{2}+F_{0}(\mathbf{S}_{0})-F_{t-1}( \mathbf{S}_{t})\right]+\frac{M\beta_{t}^{2}}{2}+N\beta_{t}+\delta_{t}. \tag{20}\]

If \(\delta_{t}\) and \(\hat{\rho}_{t}\) are well-behaved (i.e., the cost function changes slowly and so does its optimal solution \(\mathbf{S}_{t}^{*}\)) then, on average, \(F_{t}\left(\mathbf{S}_{t}\right)\) hovers within a constant term of \(F_{t}\left(\mathbf{S}_{t}^{*}\right)\). The network size \(N\) and the problem conditioning (as measured by the Lipschitz constant upper bound \(M\)) also play a natural role.