Online Convex Optimization Using Coordinate Descent Algorithms

This paper considers the problem of online optimization where the objective function is time-varying. In particular, we extend coordinate descent type algorithms to the online case, where the objective function varies after a finite number of iterations of the algorithm. Instead of solving the problem exactly at each time step, we only apply a finite number of iterations at each time step. Commonly used notions of regret are used to measure the performance of the online algorithm. Moreover, coordinate descent algorithms with different updating rules are considered, including both deterministic and stochastic rules that are developed in the literature of classical offline optimization. A thorough regret analysis is given for each case. Finally, numerical simulations are provided to illustrate the theoretical results.

1. Introduction. Online learning [22], resource allocation [7], demand response in power systems [14], and localization of moving targets [2] are just a few examples where online convex optimization (OCO) has been applied. In the problem setup of OCO, the objective functions are time-varying and are not available to the decision maker a priori. At each time instance, after an update of the decision variable, new information of the latest cost function is made available to the decision maker. The objective of the decision maker is to minimize the objective function over time. One commonly used performance measure of an online optimization algorithm is the notion of regret which measures the suboptimality of the algorithm compared to the outcome generated by the best decision at each time step.
In the seminal work of [30], the method of online gradient descent is proposed for OCO problems, where at each time step the decision maker performs one gradient descent step using the latest available information. A static regret upper bound that is sublinear in T is proved, where T is the length of the horizon. Under stronger assumptions on the cost functions such as strong convexity, an improved logarithmic regret bound can be achieved [10,18,9]. If future information is available, it can be used to further improve the performance of the online optimization algorithm in terms of regret bounds. The work [13] introduces an additional predictive step following the algorithm developed in [30], if certain conditions on the estimated gradient and descent direction are met. Similar algorithms have also been extended to cases where zeroth order [5,23,27] and second order [15] oracles are used instead of (sub)gradients. The works [5,27] on bandit feedback consider the situation where there are time-varying inequality constraints. In such cases the algorithms proposed in [30] will be hard to implement because of the high computational resource demand of the projection operation. This motivates recent research on online optimization algorithms with time-varying inequality constraints including the primal-dual algorithm proposed in [12], a modified saddle-point method given in [8]. Other algorithms are also proposed to handle stochastic constraints [28] and cover continuous-time applications [19]. In the case where only the values rather than the exact form of the cost function at are revealed to the decision maker, bandit feedback based online algorithms can be used to solve the problem, see [5,27] for example.
Although a lot of results on OCO have been obtained as listed above, most of the online algorithms are based on the idea of gradient descent and are centralized. The need for applications in large scale systems has led to extensive research on distributed OCO. Distributed online algorithms that achieve sublinear regret bound for convex optimization problems with static constraints can be found in [21,11,25]. For instance, [21] proposes a distributed version of the dynamic mirror descent algorithm which is a generalization of the classical gradient descent methods suitable for high-dimensional optimization problems. Furthermore, the work [29] extended the adaptive algorithm proposed in [12] to the distributed setting with a static inequality constraint. By introducing a regularized convex-concave function, the algorithm works without the knowledge of the total number of iterations. Finally, the work [16] proposes distributed online primal-dual algorithms for optimization problems with static coupled inequality constraints while the work [26] studies distributed online convex optimization with time-varying inequality constraints in the discrete-time setting.
To the best of our knowledge, Coordinate descent [24], as an important class of optimization algorithms, is left unanalysed by researchers in the online optimization community. Coordinate descent algorithms have great potential in applications where iteration with full gradient information is computationally expensive. Moreover, it can also be implemented in a parallel fashion as shown in [4]. In this paper, we aim to fill this gap by providing an in-depth regret analysis for different types of online coordinate descent algorithms applied to online convex optimization problems. Moreover, we believe that this work can also be extended to distributed dual iterations as well as those based on operator splitting method. This makes the results applicable to distributed problems.
The main contributions of the paper can be summarized as follows. First, we extend the coordinate descent algorithms considered in [24] to the online case and provide their regret analysis. To the best of our knowledge, this is the first attempt to look at possibilities of using coordinate descent methods to solve OCO problems. Second, we provide an in-depth regret analysis of various coordinate descent algorithms with different rules, such as cyclic updating rules and random updating rules. Specifically, we consider both random and deterministic online coordinate descent algorithms under assumptions commonly used in the literature. Additionally, we show that the regret bounds achieved by our online coordinate descent algorithms are comparable to those achieved by the literature on centralized full-gradient based online algorithms.
The paper is organized as follows. The problem formulation is presented in Section 2. The online coordinate descent algorithm considered in this paper is given in Section 3. Regret bounds for random online coordinate descent algorithms are given in Section 4 followed by regret bounds for deterministic online coordinate descent algorithms. The numerical simulation is given in Section 7. Finally the results presented in this paper is summarized in Section 8.
Notation: Let R be the set of real numbers and R n be the n-dimensional Euclidean space, R ≥0 (resp. R >0 ) be the set of non-negative (resp. positive) real numbers. For x, y ∈ R n , x, y denotes the inner product in R n . The set of natural numbers is denoted by N. The set of non-negative (resp. positive) integers is denoted by Z ≥0 (resp. Z >0 ). Furthermore, | · | denotes the Euclidean norm of a vector x ∈ R n . The matrix I n is used to denote the n-dimensional identity matrix and n will be omitted when the dimension is clear. For a given vector x, x (i) denotes the i-th component of x, x i denotes the value of x at time i, and x (i),j denotes the value of the i-th component of x at time j. All random variables considered in this paper are defined on a probability space (Ω, F , P), where Ω is the sample space, the σ-field F is the set of events and P is the probability measure defined on (Ω, F ).
2. Problem formulation. We consider the following optimization problem where f t : R n → R is the convex cost function at time t, x ∈ R n is the decision variable. For simplicity, we assume f t is continuously differentiable for any t ∈ N. Moreover, let the decision variable x t at any given time t be partitioned as The P components of the vector are assigned to P individual processors. For any integer p ∈ {1, . . . P }, the processor p is responsible for updating its own "local" decision variable x (p),t [4].
Denote the global minimizer of f t (x) at time t by x * t . We use a notion of regret to measure processors' ability to track x * t . Regret refers to a quantity that measures the overall difference between the cost incurred by an algorithm and the cost at the best possible point from an offline view up to a horizon T . Two notions of regret commonly considered in the literature are static regret and dynamic regret. The static regret is defined as: where x * := arg min T t=1 f t (x) for a given T , the subscript T is omitted for convenience. On the other hand, the dynamic regret is defined as: It can be seen from (2.2) and (2.3) that regret captures the accumulation of errors due to the fact that optimization problems are not solved exactly at each step. Moreover, regret keeps growing as the horizon T increases. However, if the regret is sublinear in T , then the average accumulated error R s T /T (or R d T /T ) will converge to zero as T → ∞. If stochastic algorithms are considered, similar notions of regrets can be defined via expectations.
With some abuse of notation, R s T and R d T are used for both random and deterministic cases. However, this would not lead to confusion since it should be clear whether an algorithm is stochastic or not.
3. Online coordinate descent algorithms. We construct our online block coordinate descent algorithms following the setup in [24]. At time t, we select a component of x t to update. The updating component at time t is denoted by i t . If the i-th component is updating, then updating equation for component i is given by where α t is the stepsize at time t and ∇ (i) f t (x t ) is the i-th component of the gradient of f evaluated at x t at time t. For any p = i t , we have Equivalently, we can define the matrix U t = diag(U (1),t , U (2),t , . . . , U (P ),t ). For any t ∈ N and 1 ≤ p ≤ P , U (p),t ∈ {I np , 0 np }, where I np and 0 np denote identity and zero matrices of dimension n p , respectively. Then the updates of the coordinate descent algorithm at time t can be written as In this paper, we consider the following three commonly used schemes of selecting the updating component i t .
• The random coordinate descent algorithm. In this case, i t is selected randomly with equal probability 1 , independently of the selections made at previous iterations. • The cyclic coordinate descent algorithm. In this case, the updating component i t is selected in a pre-determined cyclic fashion: i t+1 = (i t mod P ) + 1. • The coordinate descent algorithm with Gauss-Southwell Rule. In this case, the updating component i t is selected as i t = arg max i |∇ (i) f t (x t )|.

4.
Regret bounds for online coordinate descent algorithms with random coordinate selection rules. The online random coordinate descent algorithm considered in this section is given in Algorithm 4.1.
4.1. Static regret for convex functions. Before we state the main results, we first list the assumptions.
Assumption 4.1. For any given t ∈ Z >0 , x ∈ R n and x * := arg min T t=1 f t (x), the following inequalities hold uniformly in t and T for problem (2.1), Remark 4.2. By [22, Lemma 2.6], Assumption 4.1 (a) implies that f t is also Lipschitz continuous uniformly in t. These assumptions are quite standard in the literature on online optimization [5,6] and can be satisfied if at each step an additional projection step of the decision variable onto a compact constraint set is introduced. This will not limit the applicability of our main results since the exact values of constants G and R will not appear in the exponent of T in the regret bounds established in this paper.
For all i = i t : Before we state the first main result of the paper, we first present the so-called doubling trick scheme stepsize rule which is introduced in [ The following result states that, under . Given x t , denote the σ-field containing past data of Algorithm 4.1 up to time t by F t . Then, by convexity of f t , we have , taking total expectations, and rearranging (4.2) leads to Due to Assumption 4.1 the gradient of f t is uniformly bounded by G and |x t − x * | is upper bounded uniformly by R. Consequently, In the last inequality of (4.5), the property α T ≥ 1/ √ T is used, which is a direct consequence of the definition of the stepsize rule. On the other hand, the remaining term in (4.4) can be upper bounded as follows To derive the regret bound, we again use the properties of the doubling trick scheme. First, we set the horizon to be some known constant T * and the stepsize is chosen as the constant 1 √ T * . Then it is obvious that Since for q = 0, 1, . . . , ⌈log 2 T ⌉ + 1, α t = 1 √ 2 q in each period of 2 q iterations t = 2 q , 2 q + 1, . . . , 2 q+1 − 1. That is T * = 2 q . Then we can sum (4.6) up over any given T as Thus, the proof is complete.
Remark 4.5. In Theorem 4.4, the differentiability of f t is in fact never used. Thus the results apply to the case where subgradients are used when f t is not differentiable for some t as long as item 1 of Assumption 4.1 is satisfied by the subgradients used in the iterations. Moreover, the regret bound established in Theorem 4.4 is of the same order as the one established in [22] for online gradient descent under the same assumptions.
Remark 4.6. The doubling trick scheme of stepsize choices is particularly useful when stepsizes of type 1/T are needed to achieve a desirable regret bound. Since in applications it is often unrealistic to know the horizon T in advance, by using the doubling trick scheme regret bounds of the same order can be achieved without the knowledge of T .

4.2.
Static regret for strongly convex functions. In this part, we show that if the cost functions are strongly convex, then we can achieve an improved static regret bound for the online random coordinate descent algorithms.
Assumption 4.7. For any t, the function f t is uniformly µ-strongly convex, i.e., there exists µ > 0 such that the following inequality holds for any t ∈ N, x, y ∈ R n Proof. Similar to (4.2), given x t , we have the following relationship for any x ∈ R n , (4.10) By substituting x * to (4.10) and rearranging the terms, we have the following inequality Since the gradient of f t is uniformly bounded by G, the following inequality holds (4.11) By choosing α t = P µt , we have the following relationship where the second inequality follows by expanding the sum. Thus, the proof is complete.
By making the extra assumption of strong convexity, the sublinear static regret bound of order O( √ T ) established in Theorem 4.4 is improved to be of order O(log T ) which is consistent with the regret bound for online gradient descent algorithms under the same assumptions established in [10].

4.3.
Dynamic regret for convex functions. Now, we provide an upper bound of the dynamic regret of the online coordinate descent algorithm. First, we define the following measure of variations of the problem (2.1) which is commonly used in the literature [18,21] (4.13) where x * t is a solution to the optimization problem at time t and x * 0 can be arbitrary constant. The term C T captures the accumulated variations of optimal points at two consecutive time instances over time. If the cost functions are general convex functions and an upper bound of C T is known, the following results can be stated.
Proof. Substituting x * t in (4.2) for any t ≥ 2, yields (4.14) Then, Choosing the stepsize to be CT T leads to Remark 4.10. As discussed in Remark 4.6, the choice of stepsize CT T can be replaced by the doubling trick scheme (see Definition 4.3) to derive a regret bound of the same order. Moreover, the exact value of C T is also not necessary to derive the regret bound given in Theorem 4.9. If C T is not available, a stepsize of the same order of CT T can be used with constant factor errors. Lastly, as argued in [6], if C T is sublinear in T , then the overall dynamic regret bound in Theorem 4.9 will be sublinear in T , which is desired and consistent with the dynamic regret bounds established in [6] for full-gradient based online algorithms.

4.4.
Dynamic regret for strongly convex functions. Now, we consider the dynamic regret of the online random coordinate descent algorithm for strongly convex functions. As before, we consider µ-strongly convex functions. In addition, we will use the following result that shows the gradient of f t are Lipschitz uniformly in t.
Corollary 4.11. Suppose Assumption 4.1 (a) holds. For any t, the gradient of f t is uniformly Lipschitz continuous, i.e., there exists L > 0 such that the following inequality holds for any t ∈ N, x, y ∈ R n Proof. The result follows from Assumption 4.1 (a) and taking L = 2G.
It can be easily seen that [3] for a µ-strongly convex function having Lipschitz continuous gradient with constant L, we have µ ≤ L.
The main result regarding the dynamic regret bound of Algorithm 4.1 for strongly convex functions with Lipschitz gradients is stated as follows.
Proof. From (4.8) and (4.15), the following inequality holds [20,Lemma 11] for any t and any x, y ∈ R n Letting y = x * t yields Moreover, Assumption 4.1 (a) implies the following, which holds for any t and any Since the stepsize satisfies α t = α ≤ 2 P (µ+L) , we haveL : . Expanding it and using (4.17) leads to By Jensen's inequality, we have E|x t+1 − x * t | ≤ 1 − 2αµ P + α 2 µ 2 |x t − x * t |. Since P ≥ 1 and µ ≤ L, we have 1 − 2αµ Obviously, the dynamic regret is bounded as Now taking total expectations, using (4.20) and summing up both sides of (4.21) from t = 1 to t = T − 1 yields Note that by definition e = 1 − 2αµ P + α 2 µ 2 − (1 − αµ). Moreover, the condition α ≤ 2 P (µ+L) < 2 µP implies α 2 µ 2 < 2αµ P . Hence, αµ − e = 1 − 1 − 2αµ P + α 2 µ 2 > 0. Consequently, rearranging (4.22) leads to Remark 4.13. By assuming uniform strong convexity and uniform Lipschitz continuity of gradients of f t , Theorem 4.12 improves the order of the theoretical dynamic regret bound from O( √ C T T ) in Theorem 4.9 to O(C T ). This means if problem (2.1) does not change over time i.e. f t = f for any t, C T = 0 and the regret grows at a rate O(1) which is consistent with the convergence result of coordinate descent algorithms in the offline setting [24]. Moreover, if C T grows sublinearly, the dynamic regret bound in Theorem 4.12 is also sublinear in T which is consistent with results shown in [18] for full-gradient based online algorithms.

5.
Regret bounds for online coordinate descent algorithms with deterministic coordinate selection rules. We consider two deterministic online coordinate descent algorithms in this section and they are given in Algorithms 5.1 and 5.2, respectively.
For all i = i t : Note that both Algorithms 5.1 and 5.2 are deterministic and update a component of the decision variable. We can therefore relate the regrets achievable by Algorithms 5.1 and 5.2 to regret achievable by the online gradient descent algorithm which takes the form It can be easily seen that Algorithms 5.1 and 5.2 take the following form where the vector ν t :

Proof. By the definitions of regrets in (2.2) and (2.3), it is obvious that
Thus, if one of the two items is proved, so is the other item. Since Assumption 4.1 holds, from (2.2), we know that R s Thus the proof is complete. By using Proposition 5.1, we can establish regret bounds for Algorithms 5.1 and 5.2 using known regret bounds for online gradient descent algorithms. Moreover, if the regret bounds for online gradient descent are sublinear in T and T t=1 α t is also sublinear in T , then the established regret bounds for Algorithms 5.1 and 5.2 will be sublinear.
The following result on static regret bounds of Algorithms 5.1 and 5.2 is a direct corollary of Proposition 5.1 and Lemma 5.2.
The conclusion follows as a result of Proposition 5.1 and Lemma 5.2.
Proof. Since α t = 1 µt , we have The conclusion follows as a result of Proposition 5.1 and Lemma 5.4.

Dynamic regret for convex functions.
We can adapt the proof of Theorem 4.9 to the deterministic case to derive a dynamic regret bound for convex functions which is given in the following result.
Proof. From (5.1), we have for any Substituting x * t to (5.3) results in the following inequality for any t ≥ 2 Note that, the inequality (4.14) still holds in this case Thus, we havē If we set the stepsize to be CT T , we havē Using Propositions 5.1 and 5.6, we can state the following result on dynamic regret bounds of Algorithms 5.1 and 5.2.
Proof. Since α t = CT T , we have T t=1 α t = √ C T T . The conclusion follows as a result of Propositions 5.1 and 5.6.
As discussed in Remark 4.10, the stepsize choice α t = CT T can be made independent of T by using the doubling trick scheme.

Dynamic regret for strongly convex functions.
Note that when the cost functions are strongly convex and constant stepsizes are used, the result in Proposition 5.1 only gives a dynamic regret bound that is linear in T . Therefore, next we aim to establish the dynamic regret bounds for Algorithms 5.1 and 5.2. In this section we make the following assumption on the problem (2.1).
Assumption 5.8. For any t, the gradient of f t is uniformly block-wise Lipschitz continuous, i.e., for any 1 ≤ i ≤ P , there exists L i > 0 such that the following inequality holds for any t ∈ N, x ∈ R n , and u ∈ R ni where H i ∈ R n×ni is such that [H 1 H 2 · · · H P ] = I n .

The dynamic regret is bounded as
From (5.9), we have the following relationship by summing up both sides of (5.10) from t = 1 to t = T − 1, Since we have shown that L µ (1 − 2µĀ) < 1, Remark 5.10. Note that in Theorem 5.9, we introduce an upper bound that depends on the number of components P which increases to ∞ as B 3 decreases to 0. This is mainly a result of conservatism introduced in the derivation of (5.9) using (5.8). Regret bounds established in Theorems 5.11 and 5.12 that will be given later remove the need of requiring P being sufficiently small if additional updates are performed at each time.
The following two theorems give dynamic regret bounds without assuming an upper bound on the number of components P . However, at each time t, potentially multiple offline steps are needed to guarantee desirable regret bounds.
The modified algorithms are given below For all i = i κ , such that κ ≤ k: x (i),κ =x (i),κ−1 .
It can be seen that in Algorithms 5.3 and 5.4, at each time t, k updates are performed where k is an integer to be chosen. In Algorithms 5.1 and 5.2, however, only one step is performed at each time t. (1 + αL max ) P −1 < 1 holds, then the dynamic regret (2.5) achieved by Algorithm 5.4 Online coordinate descent algorithm with Gauss-Southwell Rule 1: Initialization: x 0 , κ and some integer k ≥ 1. 2: Update: At time t, κ = 1, For all i = i κ , such that κ ≤ k: x (i),κ =x (i),κ−1 .

Algorithm 5.3 satisfies
Proof. By the block descent lemma [1,Lemma 3.2] and the fact that Summing over all P blocks in a full round where all components have been updated exactly once leads to By the update equation and Lipschitz continuity of the gradient, we have |∇f Summing over P blocks leads to Therefore, (5.11) Then, by (5.11), we have (1 + αL max ) P −1 < 1 holds, then the dynamic regret (2.5) achieved by Algorithm 5.4 satisfies Proof. Following similar steps in the proof of Theorem 5.11 and using (5.7) and (5.13) yield    [21] 1 ≤ i ≤ 20, x (i) is a scalar. The horizon length is T = 5000, and the constant stepsize is chosen as α t = α = 0.001. Based on our experience, the exact value of α does not have significant impact on the performance of the algorithm, provided that it is small enough. In addition to the regrets (2.2) and (2.3) considered in the paper,  we also show how the time-average regrets R s T /T and R d T /T change with time in Figure 6.1. In all figures, Algorithms 1-3 refer to Algorithms with random, roundrobin and Gauss-Southwell rules respectively.
It can be seen from Figure 6.1 that when the constant stepsize is chosen sufficiently small, the regrets in all cases have a sublinear growth and therefore their time-averages go to 0 when T is sufficiently large. This is consistent with our results on strongly convex functions.
In order to see how the variation of the problem impact the performance of the algorithms. We add an extra term of 500I 20 such that the matrix Q t is diagonally dominant and therefore being less sensitive to t. We test the online algorithms in this case and the results are shown in Figure 7.1. It can be seen that when problem (7.1) varies slowly with respect to time, the curves of the regrets in Figure 7.1 have a lower growth rate compared to the regrets shown in Figure 6.1 where the diagonally dominant term is absent.
Next, we investigate the effect of the number of blocks P on the performance of the algorithm. We increase the amount of blocks from 20 to 100 and such that the while other settings remain unchanged. The result is shown in Figure 7.2. It can be seen from Figure 7.2 that when P increases, the regrets grow quicker as T increases compared to the results in Figure 6.1. This is to be expected since, it is now required at least 100 updates to ensure all components of the decision variable have been updated once. One interesting feature among Figures 6.1-7.2 is that in all cases for this numerical example, Algorithm 3 which corresponds to the Gauss-Southwell rule gives the best performance in terms of minimizing the regret. We believe one reason for this is that Algorithm 5.2 uses extra information of the norm of the gradients of all components to decide which component to update. An in-depth theoretical analysis of this problem is left for future work.
8. Summary. In this work, we have proposed an online coordinate descent algorithms to deal with optimization problems that may change over time. Three widely used update rules of coordinate descent are considered. Under different assumptions, we have provided different upper bounds on the regrets of these online algorithms. In particular, we have verified that the established regret bounds of these coordinate descent algorithms are of similar orders as those of online gradient descent methods under same settings. The regret bounds proved in this paper are summarized in Table  6.1. Lastly, a numerical example was given to illustrate our main result.