{'fraction_non_alphanumeric': 0.04405964608862548, 'fraction_numerical': 0.01444751439478624, 'mean_word_length': 4.287020517395183, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm

Multi-agent systems are being increasingly deployed in challenging environments for performing complex tasks such as multi-target tracking, search-and-rescue, and intrusion detection. Notwithstanding the computational limitations of individual robots, such systems rely on collaboration to sense and react to the environment. This paper formulates the generic target tracking problem as a time-varying optimization problem and puts forth an inexact online gradient descent method for solving it sequentially. The performance of the proposed algorithm is studied by characterizing its dynamic regret, a notion common to the online learning literature. Building upon the existing results, we provide improved regret rates that not only allow non-strongly convex costs but also explicating the role of the cumulative gradient error. Two distinct classes of problems are considered: one in which the objective function adheres to a quadratic growth condition, and another where the objective function is convex but the variable belongs to a compact domain. For both cases, results are developed while allowing the error to be either adversarial or arising from a white noise process. Further, the generality of the proposed framework is demonstrated by developing online variants of existing stochastic gradient algorithms and interpreting them as special cases of the proposed inexact gradient method. The efficacy of the proposed inexact gradient framework is established on a multi-agent multi-target tracking problem, while its flexibility is exemplified by generating online movie recommendations for Movielens $10$M dataset.


I. INTRODUCTION
Multi-agent systems involve teams of robots capable of accomplishing complex tasks in a coordinated manner [1]- [3]. Fueled by advances in sensing and communications, multi-agent systems are increasingly being used for challenging tasks such as multi-target tracking [4], [5], planetary exploration and mapping [6], search-and-rescue, and intrusion detection [7]. Achieving such team-based goals requires the robotic platforms to not only sense and understand the environment, but also cooperate among themselves through judicious data exchange and fusion.
Consequently, resource allocation and optimization becomes an important aspect of the overall motion planning problem. Indeed, the recent trend is to formulate target tracking as a constrained convex optimization problem that must be solved at every time step [8]- [12] .
Such time-varying optimization problems have their origins in the control theory literature, where they have been applied to path planning [13] and dynamic parameter tracking problems [14], [15]. Given the limited computational and communications capabilities of the mobile robots, solving the full per-time instant optimization problem before taking the action may not necessarily be viable. Instead, recent works have advocated the use of simpler one-iteration algorithms such as the online interior point, prediction-correction, online ADMM, and gradient descent methods, that have been shown to approach the optimal asymptotically. Leveraging the tools from classical optimization theory, these dynamic optimization algorithms not only admit low-complexity distributed implementations, but are also amenable to analytical performance guarantees.
Online machine learning represents a parallel but closely related development that has been widely applied to solve problems in Big Data [16]. First proposed by [8], the online convex optimization framework models the agents as learners and targets as adversaries. Within this sequential learning paradigm, the learner performs an action and the adversary reveals a corresponding loss function at each time step. The eventual goal of the learner is to minimize the cumulative loss. Recent year have witnessed the development of theoretical guarantees in form of dynamic regret, where the performance of the learner is measured against that of an adaptive and time-varying adversary [11], [17], [18]. This paper studies the multi-agent multi-target tracking problem from the lens of online convex optimization. Prompted by the noisy and possibly incorrect target position information available to the agents, we put forth the inexact online gradient descent (IOGD) algorithm. The key theoretical contribution is the development of improved dynamic regret bounds for non-strongly convex objective functions. Improving the existing results for general convex problems, it is shown that the dynamic regret is bounded by the path length of the target. Different from the existing literature, the gradient errors are not required to be unbiased, independent, or identically distributed, and can even be adversarial. The cumulative impact of such errors on the dynamic regret is explicitly studied and characterized. Regret bounds are developed for two classes of problems, namely the ones where the objective function follows the quadratic growth property (P 1 ), and the ones where the function is convex but with a compact domain (P 2 ). Interestingly, it is shown that for P 1 with linearly growing path lengths and cumulative errors, target tracking is still possible, albeit with non-vanishing steady state error. Additionally, we provide further motivation for the IOGD algorithm, by developing online variants of the incremental algorithm from [19] and the proximal gradient method [20], that may still be analyzed within the current framework. Finally, the flexibility of the IOGD algorithm is demonstrated by applying it to the multi-agent multi-target tracking problem from [21] and the online matrix completion problem [22].
The rest of the paper is organized as follows. We begin with a brief review of literature on the areas of target tracking and online optimization. Sec.II formulates the problem at hand and provides a succinct comparison of the existing results and those developed in this paper. The required regularity conditions and assumptions, as well as the proposed IOGD algorithm are stated in Sec.II-B and Sec.III. Regret bounds for the two classes of problems are developed in Sec.IV and Sec.V. In the general case when the path lengths or the cumulative errors are not sublinear, bounds on the steady state tracking error are developed in Sec.VI. The IOGD algorithm is also shown to subsume the online variants of two of the existing gradient algorithms in Sec.VII.
Finally, numerical tests on real and synthetic data are provided in Sec.VIII.

A. Related work
Inexact gradient methods have been widely used to solve a variety of optimization problems, especially in the context of machine learning [19], [23]- [25]. Since calculating an approximate gradient is often cheap, recent years have witnessed the development of several variants, such as the incremental aggregated gradient method [26], stochastic average gradient method [27], [28], stochastic variance reduced gradient method [29], SAGA [30]. For static optimization problems, the inexact gradient methods are known to converge at a linear rate even for non-strongly convex objectives [31], [32]. It is remarked that the present work considers an online setting characterized by streaming or sequentially arriving data. Therefore, the performance of the proposed algorithm is measured against that of a slowly moving clairvoyant. In contrast, the inexact gradient methods (IGM) developed in [19], [23], [24], [31]are essentially offline algorithms that are meant to be applied when full data is available. The claims in [19], [23], [24], [31] therefore concern the asymptotic behavior of the iterates {x k } and are quite different from those in the present paper. For instance, the dynamic regret bounds obtained here do not directly follow from the convergence results in these works.
Time-varying optimization problems have classically been studied in the context of optimal control [33], target tracking [34], [35], non-stationary optimization [36], and parametric programming [37]. First order gradient based methods have been advocated as efficient solvers for such problems [8]- [12], [17], [38]- [41], and will be discussed in detail in Sec. II-C. When the dynamics of the target are partially known and the cost function is sufficiently smooth, it may be possible to use second order methods, such as those proposed in [42]- [46]. On the other hand, tracking is possible even for non-differentiable but strongly convex function using the subgradient and alternating directions method of multiplier methods [47]. It is remarked that an underlying assumption in all these papers is that of strong convexity of the cost function. Such an assumption is quite strong and is not satisfied by several problems, such as least squares and logistic regression [31].
Dynamic regret for analyzing tracking problems was first introduced in [8]. As compared to the weaker notion of static regret, the idea here is to compare the performance of the tracker against that of an adaptive and time-varying adversary [11], [12], [17]. Dynamic regret bounds for the gradient descent and related first order methods have been reported in [8], [9], [11], [12], [17], [39], [41]. An even stronger notion of offline regret has recently been introduced in [48].
The present work builds upon the dynamic regret and steady state tracking results reported in [10], [11], [47]. As compared to existing results, the bounds provided here are not only stronger but also require minimal assumptions on the cost function.
Notations: Scalars are denoted by letters in regular font, while vectors (matrices) are denoted by bold face (capital) letters. The (i, j)-th element of a matrix E is denoted by [E] ij . The allone vector of size n × 1 is represented by 1 n , while I n denotes identity matrix of size n × n.
The notation · represents the Euclidean norm. The Kronecker product operator is denoted by ⊗. The expectation operator is symbolized by E. Finally, σ max (E) and σ min (E) represent the November   maximum and minimum non-zero singular values of matrix E, respectively.

II. PROBLEM FORMULATION
This section details the target tracking problem and formulates it within the online learning framework. An example is also provided to motivate the setting.

A. System Model
We consider the general problem of tracking a time-varying parameter that evolves according to an unknown dynamic model. The general setting considered here subsumes the target tracking application of interest, where the parameter may represent the location(s) of the target(s) being pursued by one or more agents. As motivated in [11], [18], [47], the parameter at time k can be written as the solution of the following (discrete) time-varying convex optimization problem where f k is a smooth convex function and X ⊂ R n is a convex set. The set notation in (1) emphasizes the fact that in general, the minimizer of f k may not necessarily be unique. The parameter estimate at time k is denoted by x k . The agents do not know the full functional form of f k but are only revealed an inexact version of the gradient∇f (x k ) := ∇f k (x k ) + e k for some e k ∈ R n . The agents make use of these inexact gradients to improve their estimates of x ⋆ k in an online manner. This paper considers the problem from an online convex optimization perspective, viewing the agents as learners and targets as adversaries. Specifically, at time k, the online learner selects an action x k ∈ X and incurs a cost f k (x k ), where f k : R n → R are smooth convex functions selected by the adversary. In response to the agent's action, the adversary also reveals an inexact gradient∇f k (x k ) to the learner. The goal of the learner is to minimize its cumulative loss K k=1 f k (x k ) over K time slots. Of particular interest is to characterize the so-called dynamic regret of the learner, that measures the cumulative mismatch between the learner's action and the optimal action [9], [11], [17]: where x ⋆ k is as defined in (1). In order for the tracking to be successful, the dynamic regret must be upper bounded by a sublinear function of K.

B. Parameter variations and error bounds
It is well known that a sublinear dynamic regret may not always be achievable, e.g., if the parameter variations or the gradient errors are too large [12], [17]. The goal of the current paper will therefore be to bound the dynamic regret using functions of the cumulative parameter variations and errors. For the target tracking setting at hand, it makes sense to characterize the parameter variations using the path length, defined as for some sequence of parameter values {x ⋆ k } k≥1 . More generally there exist a class of related complexity measures that can be used to characterize the parameter variations [11]. Examples include the functional variation V K := K k=2 sup x∈X |f k (x) − f k−1 (x)| and the gradient variation The gradient errors e k can be modeled either as being deterministic with bounded norms or stochastic with bounded variance. Deterministic errors may be of interest in adversarial settings while stochastic errors are useful for modeling communication and computational noise. In order to unify the subsequent development, a generic stochastic error model is considered that subsumes that deterministic case. Let F k denote the sigma field generated by the random sequence {e τ } k−1 τ =1 . The following assumption bounds the second moment of the error.

A1. Error bound:
The stochastic sequence {e k } K k=1 adheres to the following bound on the second moment: with ε k ≤ ε < ∞ for all k ≥ 1, and ν ≥ 0 and ε ≥ 0 are constants.
When the errors are deterministic, (4) is equivalent to a worst-case bound on the error norm.
In the general case, the goal will be to establish the sublinearity of the expected dynamic regret The specific form of the bounds in (A1) is inspired from [49], [50] and allows for errors that are proportional to the gradient norm in addition to an additive term. It is remarked that from Jensen's inequality, (4) implies that E [ e k | F k ] ≤ ε k + ν ∇f k (x k ) . The required dynamic regret bounds will be developed in terms of the path length W K and the cumulative error bound E K := K k=1 ε k . A particular case of interest is when the gradient errors constitute a white noise process as specified in the following assumption.
A2. White noise: The zero-mean error sequence {e k } K k=1 is independent identically distributed, i.e., Assumption (A2) may be applicable, for instance, when the gradient errors arise from communication errors. The requirement in (5) is more restrictive than that in (4), but also results in improved regret bounds.
The dynamic regret bounds will only be meaningful when the quantities W K and E K are sublinear in K. In the context of target tracking, a sublinear W K is obtained, for instance, if the speed of the target goes to zero as K increases. Such situations are commonly encountered for targets with finite total operational energy. Likewise, E K may be sublinear in scenarios where the gradient error goes to zero with K. Again, such situations may arise if the noise can be filtered out with increasingly higher accuracy. Finally, for the case when the W K and E K are linear functions of K, it makes sense to instead characterize the tracking performance x k − x ⋆ k of the proposed algorithm. Different from regret, the goal here is to simply ensure that the asymptotic tracking performance is not too large; see Sec. VI.

C. Related work and problem statement
Before detailing the problem statement, the existing literature on dynamic regret bounds is briefly reviewed. In [8], an online gradient descent algorithm is considered and shown to achieve regret bound under diminishing step size. Similar regret bounds are shown to exist for the online mirror descent algorithm in [9]. The online gradient descent with stochastic error is considered in [17] and regret bounds for both convex and strongly convex case are provided as O(K 2/3 (1 + V K ) 1/3 ) and O( K(1 + V K )), respectively. It is remarked that these results cannot be practically applied to tracking problems since they assume a priori knowledge of the functional variation V K . A regret bound in terms of all the three measures W K , V K and D K is obtained in [39] for optimistic mirror descent algorithm. In succession to these works, authors in [11], [12] achieved the O(1 + W K ) dynamic regret bound for online gradient descent algorithm under constant step size and strongly convex functions. The case of non-strongly convex functions has been recently considered in [12] and a regret bound of O(1 + W ′′ K ) is obtained for deterministic time-varying problems. The present results generalize those in [12] to stochastic problems with adversarial gradient errors, unbounded domain X , and a stronger path length definition (3). Finally, the case of noisy gradient is also considered in [41] for general convex functions and dynamic regret bounds are obtained while assuming the knowledge of K.
The results in the present work improve upon those in [41], in addition to allowing gradient errors that are not necessarily independent or identically distributed (cf. (A1). Moreover, the impact of gradient errors on the regret is explicitly specified, allowing us to develop IOGD variants that cannot be analyzed as special cases of the noisy OGD proposed in [41]. Table I summarizes the regret bounds obtained in the existing literature. Next, we briefly remark on the path length definitions used in [12], [41]. (3) applies to an arbitrary sequence of true parameter values {x ⋆ k } and does not depend on X ⋆ k . Consequently, the path length definition in (3) is stronger than those used in [12], [41]. In particular, the definitions in [12], [41] take the following form

Remark 1. The path length definition used in
respectively, where P k (u) := arg min y∈X ⋆ k y − u . Observe that in both cases, the path length could become unbounded if the set X ⋆ k is not compact, as is the case in P 1 . For example, the path lengths W ′ K and W ′′ K turn out to be infinite for the least squares example discussed in Sec. VIII-A. The use of an arbitrary trajectory in (3) allows us handle such unbounded sets while also ensuring that The present work considers the online inexact gradient descent method and develops various regret and tracking bounds for the case when the cost function f k is not strongly convex. The bounds developed here are efficient, and match the existing bounds in the cases when the gradient is exact. Keeping the tracking application in mind, the algorithms developed here will not require any prior knowledge of K. To this end, we consider two broad classes of non-strongly convex functions.
where E is an arbitrary m × n matrix and the function g k is strongly convex with parameter µ > 0.
The functional form required in P 1 is significantly more general than the strong convexity condition for f k . Since g k is strongly convex, there exists a unique u ⋆ = arg min y∈X g k (y).
Consequently, the set of minimizers of f k is given by The key property of f k that will subsequently be utilized is the so-called quadratic growth condition y − x and σ min (E) denotes the smallest non-zero singular value of E. The quadratic growth condition for convex problems is weaker than the standard assumption of strong convexity [51]. For instance, P 1 is applicable to common machine learning and signal processing problems such as least squares, support vector machines, and logistic regression, none of which are strongly convex [31].
It is remarked that the bounds developed for P 2 are directly proportional to the diameter R, and may therefore be quite loose. Before concluding, a remark on the possible generalization of P 1 is due.
The results developed here can be extended to the generalized version of P 1 where f k (x) = g k (h(x)) satisfies the QG condition, h is a smooth function, and g k is strictly convex.
Alternatively, it is also possible to consider convex QG functions f k that have a unique minimum.
The extensions can be incorporated via minor modifications in the proofs, but are not pursued here in order to keep the exposition succinct.

III. PROPOSED ALGORITHM AND ASSUMPTIONS
The online gradient descent algorithm has been widely used to solve online learning problems owing to its flexibility and simplicity [8], [9], [11], [17], [39]. This work considers the inexact online gradient descent (IOGD) method that takes the form: where P X (·) denotes the projection onto the set X and is defined as P X (u) := arg min y∈X y − u .
The IOGD method has also been applied to static and online problems [31]. The IOGD method is also closely related to the incremental and variance reduced variants of the gradient descent algorithm. The full algorithm is summarized in Algorithm 1. Perform action x k

4:
Observe inexact gradient ∇f k (x k ) + e k at x k

5:
Compute next action In addition to Assumptions (A1) and (A2) stated in Sec. II, the subsequent analysis will also require the following regularity conditions.
A3. Lipschitz continuity: The function ∇f k is Lipschitz continuous with parameter L: for all k ≥ 1 and u, v ∈ X .
A4. Vanishing gradient: The optimum x ⋆ k lies in the relative interior of the set X , that is, Of these, both (A3) and (A4) are standard and apply to large class of online learning problems.
Likewise, the requirement in (A5) imposes a limit on the maximum velocity of the target and is therefore applicable to most target tracking problems. The bounded variation condition is also satisfied, for instance, if W K is sublinear or linear and the target motion is not too 'jumpy'.
The subsequent two sections develop the dynamic regret bounds stated in Table I. As stated earlier, these bounds are meaningful when the variations W K and error bounds E K are sublinear in K. Development of the tracking error bounds for linear W K and E K is deferred to Sec. VI.

IV. REGRET BOUNDS FOR P 1
This section develops the dynamic regret bounds for P 1 for the case when W K and E K are sublinear in K. As discussed earlier, a simple example is that of a target that eventually stops, either upon exhausting its energy or upon reaching its destination. For such targets, there exists Likewise, the term ε k in the gradient error bound may decrease over time resulting in a sublinear E K .
Interestingly however, the gradient error is allowed to be proportional to the gradient norm, and the factor ν need not be diminishing with k.
The section proceeds by developing regret bounds for the general case in (A1), while the special case when the gradient errors constitute a white noise process as in (A2) is treated towards the end. The mathematical analysis for these two cases is unified using an indicator where, ℓ 2 is obtained from (77) using 1 d = 1 as and ζ is obtained from (79) using 1 d = 1 as The step size α is chosen such that It is remarked that an appropriate value of α satisfying the conditions required in Lemma 1 . For example, in the case when E is an identity matrix, the condition becomes µ > 2νL, while in the case when ν = 0, the condition translates to Interestingly, the selection of α does not require the prior information about K.
As also detailed in [11], [52], target tracking algorithms are generally required to run indefinitely or until the some stopping criteria such as the 'distance to target is sufficiently small' is met. In either case, the number of iterations K is generally not known or fixed in advance.
Among the bounds developed in Lemma 1, the gradient bound in (13) is particularly interesting. Different from the vast majority of literature on online convex optimization, the gradient bound allows us to forgo the assumption on the boundedness of the set X [8], [9], [17]. Further, such a result is useful even when the set X is compact but has a large diameter R, for the dynamic regret results presented here will not depend on R. Having stated the intermediate lemma, the main result of this section can finally be stated as the following theorem.
Proof: The proof follows from the first order convexity condition for f k and the use of the bounds in (12) and (13). Given a sequence {x ⋆ k } with sublinear path length W K , it holds that where we have used the first order convexity condition and the Cauchy-Schwarz inequality.
Taking expectation and using the bounds in (12) and (13), it follows that which is the required result.
The behavior of regret bound for the IOGD algorithm is governed by the target trajectory {x ⋆ k } and the error sequence e k . The results provided here subsume the OGD results in [11] where f k is strongly convex and the exact gradient is available, i.e., E K = 0. Interestingly, this theorem establishes that an O(1 + W K ) is still obtainable for P 1 with inexact gradients as long Finally, we provide the dynamic regret bounds for the case when the gradient errors follow a white noise process as in (A2).  (15), the dynamic regret for the IOGD iterates is bounded as follows where ℓ is obtained from (77) with 1 d = 0 given by ℓ := 1 − µα(1 − αL(1 + ν 2 )) and ℓ < χ.
The value of α is chosen such that Proof: As shown in Appendix B, the intermediate results for (A1)-(A2) take the form where ℓ is as defined in Corollary 1. The required dynamic regret bounds can be obtained by proceeding along the lines of proof of Theorem 1.
It is remarked that valid values of α exist if µ > 4L(1 − χ 2 )(1 + ν 2 ). It can be observed that the additional assumption in (A2) does not provide any improvement in the asymptotic regret rate, but only in the associated constants.
V. REGRET BOUND FOR P 2 Having established the regret rates for P 1 with a special QG structure, we now move to the more general problem in P 2 . However, for this case, it would not be possible to develop the results for generic stochastic errors following (A1). Instead, the results will be presented here for two specific scenarios, namely (a) gradient errors following (A1) with ν = 0, and (b) gradient errors following (A1)-(A2) but possibly non-zero value of ν. We begin with stating the following intermediate lemma whose proof is deferred to Appendix C.
Proof: Using triangle inequality and result of lemma 2 for k ≥ 1, we have that It is now possible to apply the relationship in (26) recursively for k = 1, . . . , K, so as to obtain Since the left hand side is positive by definition, it follows that where we have that Substituting the result in (32) into (28) yields the required result where the inequality in (33) follows since √ KE K > E K whenever E K is sublinear.
The results can be improved for the case when the gradient errors follow a white noise process.
Specifically, the following corollary holds as shown in Appendix C.

VI. TRACKING PERFORMANCE
Departing from the regret analysis pursued in Sections IV and V, we now consider the asymptotic tracking performance for the scenarios when W K or E K are not sublinear in K.
As a practical example, consider a target that continues to move with a constant velocity in an adversarial manner. Likewise, we may consider the scenario when errors are unpredictably random with constant variance. More generally, this section will only assume that the variations and the gradient errors terms are bounded as follows where realistically, the terms σ and ε should not be too large. In both cases, it may not be possible for the agents to reduce their distance from the target beyond a certain value [47], [52].
The goal of this section will be to characterize the tracking performance E [ x k − x ⋆ k ]. Towards this end, only the problem P 1 will be considered. As before, we begin with analyzing the general case when (A1) is in effect, and specialize the results later to the case when both (A1)-(A2) are in effect. The main result is provided in the subsequent lemma, whose proof is provided in Appendix B.
Lemma 3 establishes that the tracking error decreases exponentially with k, and is ultimately bounded by a steady state value of σ+ζε χ−ℓ . Alternatively, if it holds that ∆ 1 := dist(x 1 , X ⋆ 1 ) > ǫ, then the number of iterations required for the tracking error is to satisfy is O(log(⌈1/ǫ⌉)).
For the case when errors constitute a white noise process, the following corollary provides the required result.
for all k ≥ 1 and ℓ is as defined in Corollary 1 and α should be chosen in same manner as in Corollary 1.
The proof of Corollary 3 follows from the analysis provided in Appendix B. Likewise, the iteration complexity of the tracking error for this case is also O(log(⌈1/ǫ⌉)).

VII. IMPLICATIONS OF PROPOSED RESULTS
This section provides two online algorithms that can be interpreted as variants of the proposed IOGD algorithm.

1) Incremental OGD with increasing sample size:
Consider a scenario where the target trajectory can be expressed as the solution to the following composite function optimization problem where the objective function adheres to either P 1 or P 2 . Inspired by the sampling-based gradient methods [19], consider the following online algorithm: where N k = |N k | and N k is a random subset of {1, . . . , N}. In order to view (41) as an IOGD variant, observe that the gradient error is given by e k := 1 where Λ 2 is a bound on the sample variance of the gradients Defining ε k := (1/N k − 1/N), it can be seen that E K is sublinear, for instance when N k = Nk ρ /(N + k ρ ) with ρ > 0.
2) Proximal OGD methods for composite minimization: Next, consider a scenario where the target trajectory is given by the solution of the following composite function minimization problem: where h k is a differentiable regularization function. We propose the proximal OGD algorithm for solving (44) that takes the form where the proximal function is defined as prox αh k (z) = arg min x αh k (x) + 1 2 x − z 2 . Equivalently, it is possible to write the update in (45) as Recall that the IOGD algorithm for (44) takes the form x k+1 = x k − α(∇g k (x) + ∇f (x) + e k ).
Therefore, the error term becomes: where L is the Lipschitz constant of ∇h k . Consequently, as long as ν = αL 1−αL is sufficiently small and subject to the assumptions (A1)-(A5), the proximal OGD algorithm adheres to the O(1 + W K ) bound developed earlier. In other words, the inexact gradient used in (46) does not have any effect on the dynamic regret rate.

VIII. NUMERICAL TESTS
This section provides detailed numerical tests that demonstrate the usefulness and applicability of the proposed IOGD framework to three different applications.

A. Time varying parameter estimation
Consider a network of N nodes placed over a planar region A ⊆ R 2 . The nodes seek to cooperatively estimate (track) a time-varying parameter x ⋆ k ∈ R n using observations b i,k ∈ R m made at each node i and time k. The measurements follow the linear model b i,k = E i x ⋆ k + n i,k where E i is a node-dependent measurement matrix and the noise n i,k ∼ N (0, σ 2 I) is independent identically distributed across nodes and time. At time k, the least squares estimate for x k is given by Here, the measurement matrices {E i } N i=1 may not necessarily be full rank and therefore the optimum x ⋆ k may not be unique. In this case, the path length in (3) is well-defined for a given trajectory {x ⋆ k }, while the path lengths in (6) and (7) turn out to be infinite. Towards estimating x k in an efficient manner, we make use of the incremental OGD algorithm proposed in (41). Letting N k be a random subset of {1, . . . , N}, the incremental OGD updates take the form:  Fig. 1(a) plots the dynamic regret, Fig.   1(b) plots the cumulative error E K , and Fig. 1(c) shows the sublinear behavior of path length W K as a function of the total number of iterations K.
and N k := |N k |. As detailed in Sec. VII, the incremental OGD is a special case of the proposed IOGD algorithm if N k increases to N as k goes from 1 to K. Observe that the gradient error for this case is not independent or identically distributed.
Therefore, for this case, assumptions (A1) and (A3)-(A5) are satisfied and the results of Sec. IV are applicable.
In order to validate the performance of the proposed algorithm, we consider a network with N = 100 nodes and for m = 2 and n = 3. The subset N k is selected uniformly without replacement from {1, . . . , N} and following the rule N k = Nk/(N + k) as stated in Sec. VII.
The step size is set to α = 0.1 for all iterations and irrespective of K. The algorithm is run for different values of K and the resulting dynamic regret, error bound, and the path length are shown in Figs. 1(a), 1(b), and 1(c). For the purposes of comparison, the regret obtained when full data is used (i.e. N k = N for all k ≥ 1) is also shown (exact gradient). It can be seen that although proposed incremental IOGD does not make use of the full data, its regret is not too far from that of the classical OGD algorithm. Further, as expected from the analytical results, the dynamic regret is clearly sublinear.

B. Multi-target tracking
This section develops a low-complexity online multi-target tracking algorithm inspired from the convex optimization-based target tracking framework developed in [4]. Specifically, a team of n agents at locations {x i k } n i=1 is tasked with tracking a set of m targets at locations {y j k } m j=1 . The discretized problem is formulated as the following convex optimization that must be solved where ψ i k (·) is a time-varying cost function and v is the square of the maximum distance that an agent may cover within a single time slot. For this paper, the following cost function is used: where γ > 0 is a regularization parameter. The objective function encourages agent i to remain close to the other agents. At the same time, the regularization term forces the agents to not move around unnecessarily. The constraint in (50c) is the linearized version of the original constraint obtained from using the process described in [4,Chap. 3]. A sigmoidal weight function is utilized that takes the form: where ϑ and ǫ are positive parameters. Observe that the weights are small for agent-target pairs that are far from each other. In other words, the constraint in (50c) encourages the set of agents tracking a target j to stay close to it. The weights are normalized so that n i=1 w ij k = 1 in order to ensure that each target is tracked by at least one agent. Finally, it is remarked that the agents may only know the estimated target locations {ŷ j k } m j=1 instead of the true locations required for (50c).
Different from [21], where interior point methods are proposed towards solving (50) at each time instant, the goal here is to track the targets at a significantly low complexity. To this end, we propose an IOGD-based low-complexity algorithm capable of tracking high speed targets in large multi-agent networks. Since the constrained optimization problem in (50) is not of the form required in (1), the IOGD algorithm will instead be applied in the dual domain. It can be verified that (50) satisfies the Slater's conditions, and therefore has zero duality gap.
To this end, associate dual variables {λ i } n i=1 and {ν j } m j=1 with (50b) and (50c), respectively. Collecting the primal and dual variables {λ i }, {ν j }, and {x i } into vectors λ, ν, and x respectively, the Lagrangian can be written as Thus the dual function can be written as Since the dual function is always concave, the proposed IOGD algorithm can be utilized to maximize ̺ k in an online fashion. In particular, for a given λ and ν, the gradient of the dual function is given by where {x i (λ, ν)} n i=1 = arg min x L(x, λ, ν). In order to evaluate the minimization, observe that the condition ∇ x i L k (x, λ, ν) = 0 is equivalent to for i = 1, . . . , n. Let D k be a diagonal matrix with (i, i)-th element [D k ] ii = n + 2γ + 2λ i + 2 m j=1 ν j w ij k and let the right-hand side of (57) be denoted by the i-th element of the vector ϕ k . Then the solution to (57) can be written as x = (D k − 11 T ) −1 ϕ k where 1 is an all-one vector of appropriate dimension. Observe further that the solution is unique for all λ and ν since L k (x, λ, ν) is strongly convex in x. Using the matrix inversion lemma, it is possible to calculate x with O(n) complexity as follows: Since the target location is not known exactly, the estimated target location must be used in (56), making the gradient inexact. The agent location is determined from the current primal iterate x k which serves as a proxy for the primal solution x ⋆ k at time k. Consequently, the results of Sec. VI will be applicable here. The full IOGD-based multi-target tracking algorithm is summarized in Algorithm 2.

2:
Compute weights {w ij k } from (52) 3: Calculate the next location as Update for all agents and targets: The performance of the proposed multi-target tracking algorithm is studied on a number of simulated planar environments. The agent velocities are restricted to 0.2 m/s and a target is assumed covered if it is within η = 0.54 m from at least one agent. Consider first a simple scenario consisting of three targets (m = 3) and three agents n = 3. The targets are co-located at time k = 1 and start moving away from each other along the paths shown in Fig. 2. It can be seen that the proposed algorithm works as expected, and the agent team splits up in order to track the three targets. On the other hand, the algorithm in [21] does not necessarily exhibit such a behavior and requires careful parameter tuning so as to allow tracking with reasonable accuracy; see Fig. 2. Indeed, since [21] entailed solving a constrained convex optimization problem at every time instant, it was observed that unless the parameters are not selected carefully, the problem could become infeasible. It was however possible to circumvent this behavior to a certain extent by explicitly adding noise to the output of the optimization problem. In contrast, no such issue was present in the proposed IOGD algorithm, whose performance was quite robust to the choice of parameters. It is observed from the figure that the trajectory of the solution of (50) using [21] is a bit away from the target trajectory because the formulation in (50) does not incentivize the agents to come too close to target. On the other hand, the IOGD algorithm over-tracks to a certain extent, thereby coming close to the target but at the same time yielding a higher objective value. Fig. 3 shows the error performance x k − x ⋆ k for the IOGD algorithm. As expected from the results of Sec. VI, the tracking error remains bounded. It is remarked that for tracking error is small initially while the agents are close to each other and increases when they split up to track the diverging targets. the IOGD algorithm is capable of tracking most of the targets at low complexity; see Figs. 4 and 5. As with the smaller system considered earlier, the splitting of the agent teams is observed in Fig. 4d. The splitting behavior is also evident from the supplementary video included with this paper 1 . It is important to emphasize that the tracking performance of the IOGD is at par with the convex optimization approach of [21]. In contrast, solving a general convex optimization problem as required in [21] incurs a complexity of at least O(n 3 ) as opposed to the O(n) complexity incurred in the calculation of the inexact gradient in (59)-(60). For the sake of comparison, both algorithms were implemented in MATLAB and their run-times measured on an Intel Xeon E3-1226 3.30GHz CPU machine. The resulting per-iteration run-time for the proposed algorithm was 49 ms, as compared to that of 974 ms required by [21].

C. Tracking movie ratings
This section considers the problem of tracking movie ratings in recommender systems. Traditionally, the problem has been posed as that of completing a low-rank matrix and solved using a variety of offline or incremental algorithms. In many applications however, the dataset grows over time, necessitating a real-time recommendation engine that predicts the missing ratings in an online manner; see e.g. [22]. This section advocates an IOGD-inspired algorithm that can predict and track missing ratings at low complexity. optimization problem: Following the notation of [54, Sec. III-D], ⊙ denotes the Hadamard product while X ⋆ denotes the nuclear norm of X. In order to obtain X k in an online fashion, we utilize the proximal OGD algorithm introduced in (45), that takes the form: where, D λ (·) is the singular value thresholding operator. Given the singular value decomposition of a matrix Y = Udiag(σ 1 , . . . , σ r )V T , the singular value thresholding operation is defined as It is remarked that although the proximal OGD in Sec. VII is motivated as an IOGD variant for differentiable regularizers, it is applied and will be shown to work even for the non-differentiable regularizer X ⋆ . The other assumptions, namely (A1), (A4), and (A5) are however satisfied for this case.
Towards testing the performance of the proposed algorithm, we consider the Movielens 10M dataset, consisting of about 10 million ratings. The time-stamp associated with each rating is utilized to obtain 40 matrices {M k } 40 k=1 , each consisting of new ratings added over the last 30 days. Fig. 6 shows the evolution of the root mean-square error over time for the step size parameter α = 1. Interestingly, the regularized mean square error (RMSE) decays quickly over time and attains a value competitive with the benchmark [22]. Indeed, the proximal algorithm in (59) can be viewed as a generalization of the Soft-Impute method for the dynamic matrix completion problem. The tracking MSE for a class of related adaptive matrix completion algorithms is provided in [54].

IX. CONCLUSION AND FUTURE WORK
This paper considered the problem of tracking time-varying and possibly adversarial targets.
An inexact gradient descent method is proposed, that is applicable to non-strongly convex acterizing the performance of the algorithms using the dynamic regret as defined in (2). In the context of target tracking however, it may be useful to consider a more appropriate exponentially weighted dynamic regret, defined as Reg ω := K k=1 ω K−k (f k (x k ) − f k (x ⋆ k )) for 0 < ω < 1. By assigning higher weights to the decisions made in the recent past, such a definition is apposite for tracking problems with shorter memory. Such an exponential window function is also reminiscent of the classical adaptive filtering algorithms such as the recursive least squares algorithm.

PRELIMINARIES
To begin with, several preliminary results required for establishing various bounds are derived.
Observe that for P 1 , it follows from the convexity and quadratic growth property of f k that for all x ∈ X , Likewise, the following gradient bounds follow from (A3)-(A4): Note that f ⋆ k = f k (P k (x k )) and this term will be used interchangeably throughout the analysis. The following inequality will be utilized towards obtaining the bounds in Sec. V. For positive scalars u, v, and w that satisfy APPENDIX B PROOF OF LEMMA 1, COROLLARY 1, AND LEMMA 3 Proof of (11): The proof begins by expanding the expression for x k+1 − P k (x k ) 2 in terms of dist(x k , X ⋆ k ). Specifically, since P X (P k (x k )) = P k (x k ), it follows from the non-expansiveness property of the projection P X (·) that, where the inequality in (69) follows from (64).
The next step is different, depending on the gradient error model in effect. In the general case (cf. (A1)), the last two terms in (69) can be bounded from the use of the Cauchy-Schwarz inequality as Taking the conditional expectation E k [·] := E [· | F k ], we obtain On the other hand, when the errors are zero-mean and i.i.d. (cf. (A2)), we have that x k is independent of e k , implying that The inequalities in (71) where we have used the error bound in (A1). Next using the inequality 2uv ≤ u 2 + v 2 , and the inequalities in (65) and (66), we obtain where for the second term on the right of (75) to be positive, it is required that αL(1+ν 2 +2ν1 d ) < 1. Next, the QG property of f k implies that where Note that it is always possible to find an appropriate α if µ > 2νL. The use of Jensen's inequality yields Observe that for the case when 1 d = 0, the right hand side is upper bounded by ℓ x k − P k (x k ) + αε k from the triangle inequality. In order to obtain a compact expression for the general case, and observe that ζ > α since ℓ < 1. Therefore, it follows from (78) that which is the required expression.
Proof of (12): This proof will make use of the following bounds, that hold for any x ⋆ ∈ X ⋆ , where σ max := σ max (E) and σ min := σ min (E).
Using the lower bound in (82a) and from the triangle inequality, it holds for any sequence Next, since all points in X ⋆ k map to a unique point u ⋆ k , it holds that Ex ⋆ k = EP k (x k ). Therefore, the upper bound in (82b) implies that While the result in (85) holds for any arbitrary {x ⋆ k }, of particular interest is a sequence with sublinear path length, as defined in (3). Multiplying both sides of (85) by χ = σ min σmax , taking expectations, and substituting the result from (81), we obtain Since ℓ < χ, it therefore holds that Proof of Lemma 3 and equation (13): Using the bounds in (82) and the triangle inequality, it follows that where the equality in (90) holds since Ex ⋆ k = EP k (x k ) and the last inequality makes use of the bounded variation property in (A5). Taking expectation, substituting the result in (81), and using the bounds is (36), we obtain Recursive use of (92) yields E dist(x k+1 , X ⋆ k+1 ) ≤ (ℓ/χ) k dist(x 1 , X ⋆ 1 ) which is the required result in the statement of Lemma 3. The result in (13) can be obtained by using the upper bound ℓ χ < 1 in (93), resulting in which, along with (65), yields the required result.
APPENDIX C PROOF OF LEMMA. 2 AND COROLLARY 2 As earlier, the proofs of Lemma 2 and Corollary 2 will be developed in a unified manner. To this end, we will again make use of the indicator function 1 d that takes values 0 or 1, depending on the assumption under effect. In particular, the following two cases are considered: (a) the general case under (A1) with ν = 0 for which 1 d = 1 (Lemma 2); and (b) the white noise error case under (A1)-(A2) for which 1 d = 0 Corollary 2.
Proof of Lemma 2: Given a sequence {x ⋆ k } satisfying (3), and using the first order convexity property of f k , we obtain Next, we take conditional expectation given F k in (96), and consider the two cases separately.
In the general case under (A1) with ν = 0, the last two terms can be bounded as in (71) to yield ≤ α 2 (ε 2 k + ∇f k (x k ) 2 ) + 2αε k R where recall that R := diam(X ). Inequality in (99) follows from 2uv ≤ u 2 + v 2 . Finally, it follows from (66) that In the second case, when gradient errors are zero mean and i.i.d., it can be seen from (97) that the right-hand side is zero. Combining the two cases within (96), it follows that where we have again used (66) and the bounds in (A1) and for the two cases. It is remarked that the last term in (102) is negative for αL < 1/(1 + ν 2 + 1 d (1 − ν 2 )). Henceforth, denote ξ :=2α(1 − αL(1 + ν 2 + 1 d (1 − ν 2 ))) (103) Using (67), it follows that Taking full expectation and using the Jensen's inequality, it follows that which is the required result.