Title: DISTRIBUTED ONLINE OPTIMIZATION WITH LONG-TERM CONSTRAINTS

Abstract: We consider distributed online convex optimization problems, where the distributed system consists of various computing units connected through a time-varying communication graph. In each time step, each computing unit selects a constrained vector, experiences a loss equal to an arbitrary convex function evaluated at this vector, and may communicate to its neighbors in the graph. The objective is to minimize the system-wide loss accumulated over time. We propose a decentralized algorithm with regret and cumulative constraint violation in O(T max{c,1-c} ) and O(T 1-c/2 ), respectively, for any c ∈ (0, 1), where T is the time horizon. When the loss functions are strongly convex, we establish improved regret and constraint violation upper bounds in O(log(T )) and O( T log(T )). These regret scalings match those obtained by state-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problem (for both convex and strongly convex loss functions). In the case of bandit feedback, the proposed algorithms achieve a regret and constraint violation in O(T max{c,1-c/3} ) and O(T 1-c/2 ) for any c ∈ (0, 1). We numerically illustrate the performance of our algorithms for the particular case of distributed online regularized linear regression problems.

1. INTRODUCTION:

The Online Convex Optimization (OCO) paradigm Hazan (2016) has recently become prominent in various areas of machine learning where the environment sequentially generating data is too complex to be efficiently modeled. OCO portrays optimization as a process, and applies a robust and sequential optimization approach where one learns from experiences as time evolves. Specifically, under the OCO framework, at each time-step the learner commits to a decision and suffers from a loss, a convex function of the decision. The successive loss functions are unknown beforehand and may vary arbitrarily over time. At the end of each step, the loss function may be revealed (a scenario referred to as full information). Alternatively, the experienced loss only might be available (bandit feedback). The objective of the decision maker is to minimize the loss accumulated over time. The performance of an algorithm in OCO is assessed through the notion of regret, comparing the accumulated loss under the algorithm and that achieved by an Oracle always selecting the best fixed decision. In case of full information feedback, it is known that the best possible regret scales in O( √ T ) (resp. O(log T )) for convex (resp. strongly convex) loss functions Zinkevich (2003) ; Hazan et al. (2007) ; Abernethy et al. (2009) .

This paper extends the OCO framework to a distributed setting where (different) data is collected and processed at N computing units in a network. More precisely, we consider scenarios where in each time-step, each unit i commits to a decision x i (t) and then experiences a local loss equal to i,t (x i (t)). Units update their decision based on previously observed local losses and messages received from neighboring units with the objective of identifying the decision x = arg min x T t=1 N i=1 i,t (x) minimizing the accumulated system-wide loss. Many traditional applications of the centralized OCO framework Hazan (2016) naturally extend to this distributed setting. As a motivating example, consider the following distributed online spam filtering task (refer to Hazan (2016) for a description of the spam filter design problem in a centralized setting). In each time-step, each unit i (here an email server) receives an email characterized by a vector a i,t ∈ R d (according to the "bag-of-words" representation). Unit i applies for this email a filter represented by a vector x i (t) ∈ X where X is convex compact subset of R d , returns a label f (a i,t x i (t)), and experiences a loss equal to i,t (x i (t)) = (f (a i,t x i (t)) -y i,t ) 2 where y i,t is the true email label (-1 for spam or 1 for valid). Note that the sequences of loss functions are inherently different at various units because the latter receive different emails. Nevertheless, each unit would ideally wish to identify and apply as fast as possible the filter minimizing the system-wide loss, i.e., a filter that exploits the knowledge extracted from all emails, including those received at other units. By leveraging this knowledge, each unit would adapt faster to an adversary also modifying in an online manner spam emails. More generally the distributed OCO framework can be applied to networks of learning agents, where each agent wishes to take advantage of what other agents have learnt to speed up and robustify its own learning process.

1.1. THE DOCO (DISTRIBUTED ONLINE CONVEX OPTIMIZATION) FRAMEWORK:

We describe here our distributed optimization problem in more detail. We consider a network of N computing units described by a sequence of directed graphs G t = {V, E t } with node set V = {1, . . . , N } and edge set E t at time t. G t represents the communication constraints at the end of time-step t: each unit is allowed to send its decision at time t to its neighbors in G t . Each unit i ∈ V is associated with a sequence of convex loss functions { i,t } T t=1 , where i,t : R d → R. Optimization process. In each time-step t, each unit i ∈ V selects x i (t) ∈ R d . Then, in case of full information feedback, the loss function i,t is revealed to unit i, whereas in case of bandit feedback, the loss i,t (x i (t)) is revealed only. Unit i finally receives vectors, functions of decisions selected by its neighbors in G t , i.e., x j (t) for j such that (j, i) ∈ E t , and updates its decision for the next time-step.

Decision constraints. The decisions should be selected in X a convex subset of R d characterized by a family of inequalities:

X = {x ∈ R d | c s (x) ≤ 0, s = 1, . . . , p}.

Imposing such constrained decisions implies that each unit should be able in each time-step to perform a projection onto X , which can be extremely computationally expensive. To circumvent this difficulty, we adopt the notion of long-term constraints introduced in Mahdavi et al. (2012) . Specifically, we only impose that the constraints are satisfied in a long run rather than in each time-step, i.e., that T t=1 N i=1 p s=1 c s (x i (t)) ≤ 0. This relaxation allows units to violate the constraints by projecting onto a simpler set that contains X . Our results can be modified to account for the actual constraints (but using projection steps).

Regrets and cumulative absolute constraint violation. The objective is to design distributed sequential decision selection algorithms so that each unit identifies the decision minimizing the accumulated system-wide loss. The performance of such an algorithm is hence captured by the regrets at the various units. The regret at unit i is:

EQUATION

where x = arg min x∈X T t=1 N j=1 j,t (x). The system-level regret is defined as the worst possible regret at all units: SReg(T ) max i=1,...,N Reg(i, T ). Now since we allow units to select decisions outside X , the performance of an algorithm is further characterized by the so-called cumulative absolute constraint violation defined by: (here [a] + = max{0, a})

CACV(T ) := T t=1 N i=1 p s=1 [c s (x i (t))] + .

(2)

1.2. MAIN RESULTS:

We propose simple distributed algorithms where in each time-step, each unit combines information received from its neighbors to update its decision and its local dual variable. Our algorithms enjoy the following performance guarantees:

Full Information feedback. In the case of full information feedback, the proposed algorithms achieve a system-level regret and a cumulative constraint violation in O(T max{1-c,c} ) and O(T 1-c/2 ), respectively and for any c ∈ (0, 1) (c expresses the trade-off between regret and cumulative constraint violation). Theses bounds match those of centralized online optimization algorithms in Mahdavi et al. (2012) ; Jenatton et al. (2016) ; Yuan & Lamperski (2018) . When c = 1/2, we get a regret scaling in O( √ T ), which corresponds to the fundamental regret limits for centralized online problems Abernethy et al. (2009) , which is rather surprising in view of the dynamically changing environment, the decentralized structure of the algorithm, and the presence of the constraints. When the loss functions are strongly convex, we establish improved upper bounds on the regret and cumulative connstraint violation in O(log(T )) and O( T log(T )). These bounds generalize to our distributed setting those derived in Yuan & Lamperski (2018) for centralized problems.

Bandit feedback. In the case of bandit feedback, the proposed algorithms achieve a systemlevel regret and a cumulative constraint violation in O(d 2 T max{1-c/3,c} ) and O(dT 1-c/2 ), respectively, for any c ∈ (0, 1). For example, when c = 3 4 , the proposed algorithm attains a regret bound in O(d 2 T 3/4 ). The performance guarantees can be improved to O(d 2 T 2/3 log(T )) and O(d T log(T )) in the case of strongly convex losses.

1.3. RELATED WORK:

Early work on online convex optimization in a centralized setting include Zinkevich (2003) ; Flaxman et al. (2005) . Today we know that a regret in O( √ T ) is achievable in both full information and bandit feedback, see e.g. Bubeck et al. (2017) . Projection-free algorithms have been also developed Mahdavi et al. (2012) ; Jenatton et al. (2016) ; Yuan & Lamperski (2018) with regret and cumulative constraint violation in O(T max{c,1-c} ) and O(T 1-c/2 ) (c ∈ (0, 1)) in case of full information feedback (Yuan & Lamperski (2018) uses the cumulative squared constraint violation). Our algorithms achieve the same guarantees in a distributed setting.

It is worth zooming into the rich literature on centralized online convex optimization with bandit feedback. In the seminal work Flaxman et al. (2005) , the authors designed an algorithm with onepoint bandit feedback and regret in O(d 2 T 3/4 ). The work Agarwal et al. (2010) extended this algorithm to multi-point bandit feedback setting, where multiple points around the decision can be queried for the loss function; they established O(d 2 √ T ) and O(d 2 log(T )) regret bounds for general convex and strongly convex loss functions, respectively. The work Mahdavi et al. (2012) studied the online bandit optimization with long-term constraints under two-point bandit feedback for domain. They established O( √ T ) and O(d 2 T 3/4 ) bounds on the regret and the cumulative constraint violations, respectively. In this paper, we design distributed algorithms with one-point bandit feedback only, and with the same regret guarantees as the centralized algorithm in Flaxman et al. (2005) .

Over the last few years, there have been a rising interest for the Distributed OCO framework. Particularly, Shahrampour & Jadbabaie (2017); Lee et al. (2017) propose distributed algorithms with O( √ T ) regret, but require an exact projection onto the decision set in each time-step. Zhang et al. (2017) presents a distributed online conditional gradient algorithm, replacing the projection steps by a much simpler linear optimization steps, but at the expense of worse and sub-optimal regret guarantees, scaling in O(T 3/4 ). The other approach to avoid projections is to allow the algorithm to violate the constraints, and has been studied in Yuan et al. (2018) . The problem studied in Yuan et al. (2018) is a special case of our problem (where only one inequality constraint is considered), and the regret and cumulative constraint violation guarantees obtained there are much worse than ours. The authors of Li et al. (2018) ; Yi et al. (2019) also use the long-term constraints approach to avoid projections, but analyze a very different optimization problem where units have different decision variables, and no consensus among units is required. Finally it is worth mentioning that all the aforementioned papers are restricted to full information feedback.

Notation and Terminology. Let x and [x] i to denote the Euclidean norm and the ith component of a vector x ∈ R d , respectively. Let Π X [x] be the Euclidean projection of a vector x onto the set X . Let R p + be the nonnegative orthant in R p : R p + = {x ∈ R p | [x] i ≥ 0, i = 1, . . . , p}. Denote the (i, j)-th element of a matrix A by [A] ij . For a convex function f , a subgradient (resp. gradient when f is differentiable) at a point x is denoted by ∂f (x) (resp. ∇f (x)). Given two positive sequences {a t } ∞ t=1 and {b t } ∞ t=1 , we write

a t = O(b t ) if lim sup t→∞ a t /b t < ∞.

2. FULL-INFORMATION FEEDBACK:

In this section, we focus on the case of full-information feedback, where at the end of each time-step, the entire loss function i,t is revealed to unit i. More precisely, unit i has access to the gradient of the loss function i,t at any query point. We make the following assumptions, which are standard in the literature e.g., Mahdavi et al. (2012) ; Jenatton et al. (2016) ; Yuan & Lamperski (2018) ; Nedic & Ozdaglar (2009) ; Yan et al. (2013); Duchi et al. (2012) ; Hosseini et al. (2013) ; Nedic et al. (2010) .

Assumption 1 X ⊆ B := x ∈ R d | x ≤ R X with R X > 0.

Assumption 2 The functions i,t and c s are convex with bounded gradients:

max i=1,...,N max t=1,...,T max x∈B ∇ i,t (x) ≤ G , max s=1,...,p max x∈B ∇c s (x) ≤ G c .

We let G = max{G , G c }.

Assumption 3 There exists an integer B ≥ 1 such that the union graph (V,

E kB+1 ∪ • • • ∪ E (k+1)B )

is strongly connected for all k ≥ 0.

Assumption 4 Associated with G t there is the weight matrix A(t) which satisfies for all t ≥ 1:

(i) A(t) is doubly stochastic for all t ≥ 1, i.e., N j=1 [A(t)] ij = 1 and N i=1 [A(t)] ij = 1, ∀i, j ∈ V; (ii) There exists a scalar ζ > 0 such that [A(t)] ii ≥ ζ for all i and t ≥ 1, and [A(t)] ij ≥ ζ if (j, i) ∈ E t and [A(t)] ij = 0 for all j otherwise.

Assumption 4 is quite standard in the literature on distributed online or offline optimization, and easy to achieve in a distributed manner in real-world networks. For example, when bidirectional communication between nodes is allowed, we can enforce symmetry on the node interaction matrix, which immediately makes it doubly stochastic. There are also other methods to construct doubly stochastic matrices for a network, see, e.g., Garin & Schenato (2010) ; Gharesifard & Cortés (2010) .

Algorithm 1 DOCO-LTC with full-information feedback Input:

Step sizes {β t } T t=1 , regularization parameters {η t } T t=1

Initialize:

x i (1) = 0 ∈ R d , λ i (1) = 0 ∈ R p , ∀i = 1, . . . , N 1: for t = 1 to T do 2:

Unit i commits to a decision x i (t), and then after receiving i,t , compute

y i (t) = x i (t) -β t ∇ i,t (x i (t)) + p s=1 [λ i (t)] s ∂[c s (x i (t))] + 3:

Unit i communicates y i (t) to its neighbors and updates its decision as

x i (t + 1) = Π B (p i (t)) , where p i (t) = N j=1 [A(t)] ij y j (t) 4:

Unit i updates its dual variable:

λ i (t + 1) = arg max λ∈R d + L i,t ((x i (t + 1), λ) 5: end for

The pseudo-code of our algorithm, DOCO-LTC (LTC stands for Long-Term Constraints), is presented in Algorithm 1. It generalizes the algorithm in Yuan & Lamperski (2018) to our distributed setting. In contrast to the literature on (online) distributed optimization with inequality constraints Yuan et al. (2018) ; Li et al. (2018); Khuzani & Li (2016) , the algorithm does not need to maintain an iterative dual update process for every unit, which can be computed locally and explicitly. Moreover, no consensus updates on the dual variables are necessary, reducing the communication complexity.

The design and convergence analysis of DOCO-LTC rely on the following online augmented Lagrangian function associated with unit i ∈ V: for t ≥ 1,

EQUATION

) where λ = [[λ] 1 , . . . , [λ] p ] T ∈ R p

+ is the vector of Lagrangian multipliers with [λ] s being associated with the sth inequality constraint c s (x) ≤ 0 and η t is the regularization parameter. We note that:

∇ x L i,t (x i (t), λ i (t)) = ∇ i,t (x i (t)) + p s=1 [λ i (t)] s ∂[c s (x i (t))] + ,

where ∂[c s (x i (t))] + can be calculated as follows for s = 1, . . . , p:

∂[c s (x i (t))] + = ∇c s (x i (t)), if c s (x i (t)) > 0 0, otherwise.

Moreover, the dual update λ i (t + 1) in DOCO-LTC can be calculated explicitly as follows:

EQUATION

Theorem 1 (Convex loss functions and full-information feedback) Under Assumptions 1-4, the regret and cumulative constraint violation of DOCO-LTC with parameters η t = 1 T c and β t = 1 apG 2 T c for some c ∈ (0, 1), a > 1, and all t ≥ 1, satisfy: for all T ≥ 1,

SReg(T ) ≤ CT max{1-c,c} and CACV(T ) ≤ CT 1-c/2 , where C = 1 2 apN G 2 R 2 X + 1 ap N (1 + Ĉ) + N Ĉ2 4a(a-1)p with Ĉ = 2N 3N ψ 2+1/B (1-ψ 1/B ) + 4 and ψ = 1 -ζ 4N 2 -2

, and C =

N 2 a-1 1 + 2apGR X + 1 2 a 2 p 2 G 2 R 2 X .

Theorem 1 shows that DOCO-LTC has the same guarantees as those of the centralized algorithms in Mahdavi et al. (2012) ; Jenatton et al. (2016) ; Yuan & Lamperski (2018) . The user-defined parameter c tunes the trade-off between SReg and CACV (for c = 1/2, we get a regret and constraint violation in O( √ T ) and O(T 3/4 )).

Communication cost vs. regret. The communication cost, i.e., the number of vectors transmitted per round in the network, is simply equal to the number of edges in the network. Taking the case of B = 1 (i.e., the graph is fixed and connected) as an example, we can establish that the regret bound in Theorem 1 scales as O N 4

(1-σ2(A)) 2 T max{c,1-c} , where σ 2 (A) is the second largest singular value of the weight matrix A. If we choose the weight matrix as the maximum-degree weights (see, e.g., Yuan et al. ( 2019)), we have the following conclusions: i) Random geometric graph: the regret bound scales as N 6 log 2 (N ) T max{c,1-c} and at most 2 log 1+ (N )N vectors are transmitted per round; ii) k-regular expander graph: σ 2 (A) is constant, the regret bounds scales as N 4 T max{c,1-c} and 2kN vectors are transmitted per round; and iii) complete graph: σ 2 (A) = 0 and N (N -1) vectors are transmitted per round.

Next we improve DOCO-LTC performance guarantees when the loss functions are strongly convex.

Assumption 5:

The loss function i,t is σ-strongly convex over B, that is, for any x, y ∈ B,

i,t (x) ≥ i,t (y) + ∇ i,t (y) T (x -y) + σ 2 x -y 2 .

Theorem 2 (Strongly convex loss functions and full-information feedback) Under Assumptions 1-5, the regret and cumulative constraint violation of DOCO-LTC with parameters η t = 2pG 2 σt and β t = 1 σt for all t ≥ 1, satisfy: for all T ≥ 3, SReg(T ) ≤ Csc log(T ), and CACV(T ) ≤ Csc T log(T ),

where

Csc = N G 2 2σ (4 + 4 Ĉ + Ĉ2 ) ( Ĉ is shown in Theorem 1) and Csc = 4pN G 3/2 √ σ √ R X + G σ .

In the case of strongly convex loss functions, the regret and constraint violation guarantees of DOCO-LTC also match those obtained by the centralized algorithm in Yuan & Lamperski (2018) . Note that one cannot actually get a better regret scaling, even in the centralized setting Abernethy et al. (2009) .

3. ONE-POINT BANDIT FEEDBACK:

This section is devoted to the case of bandit feedback, where at the end of each time-step, unit i can observe the value of the loss function i,t at only one point around x i (t). The pseudo-code of our algorithm adapted to this feedback is presented in Algorithm 2.

Algorithm 2 DOCO-LTC with one-point bandit feedback Input:

Step sizes {β t } T t=1 , regularization parameters {η t } T t=1 , exploration parameters {ε t } T t=1 , and shrinkage parameter π Initialize:

x i (1) = 0 ∈ R d , λ i (1) = 0 ∈ R p , ∀i = 1, . . . , N 1: for t = 1 to T do 2:

Unit i commits to a decision x i (t), and then observes the loss i,t (x i (t) + ε t u i (t)) where u i (t) is randomly chosen on the unit sphere ( u i (t) = 1)

3:

Unit i builds the following one-point gradient estimator:

∇ i,t (x i (t)) = d ε t i,t (x i (t) + ε t u i (t))u i (t)

and computes

y i (t) = x i (t) -β t ∇ i,t (x i (t)) + p s=1 [λ i (t)] s ∂[c s (x i (t))] + 4:

Unit i updates its decision using y j (t) received from its neighbors as

x i (t + 1) = Π B (p i (t)) , where p i (t) = N j=1 [A(t)] ij y j (t) 5:

Node i updates its dual variable λ i (t + 1) = arg max λ∈R d + Li,t ((x i (t + 1), λ) 6: end for

The design and convergence analysis of our algorithm here rely on the smoothed version Li,t (x, λ) of the online augmented Lagrangian function (3), i.e., Li,t (x, λ):

EQUATION

where

˜ i,t (x; ε) = E v [ i,t (x + εv)]

is the smoothed loss function, and v is a vector uniformly distributed over the unit sphere. As in the case of full information feedback, the dual update λ i (t+1) can be calculated explicitly according to (4).

In the case of bandit feedback, we need to introduce the shrinkage parameter π to ensure that the random query point x i (t) + ε t u i (t) belongs to the set B. Indeed, we have:

x i (t) + ε t u i (t) ≤ x i (t) + ε t u i (t) ≤ (1 -π)R X + ε t ≤ R X

where the second inequality follows from the fact that x i (t) ∈ (1 -π)B and u i (t) = 1 and the last inequality holds when ε t ≤ πR X .

To establish upper bounds on the regret and cumulative constraint violation of our algorithm, we make the following standard assumption on the loss functions i,t (x) (commonly adopted even in centralized online bandit optimization Flaxman et al. ( 2005)).

Assumption 6:

The loss functions i,t (x) are uniformly bounded over B:

sup x∈B max i=1,...,N max t=1,...,T | i,t (x)| ≤ C.

Since algorithms for bandit feedback are inherently randomized, we investigate averaged versions of the regret and the cumulative constraint violation: E-SReg(T ) := max i=1,...,N E[Reg(i, T )] and E-CACV(T ) :=

T t=1 N i=1 p s=1 E[[c s (x i (t))] + ].

Theorem 3 (Convex functions with bandit feedback) Under Assumptions 1-4 and 6, the regret and cumulative constraint violation of DOCO-LTC with parameters

η t = 1 T c , β t = 1 apG 2 T c , ε t = 1 T b , π = 1 R X T b for some c ∈ (0, 1), b = c/3 and all t ≥ 1, satisfy: for all T ≥ 1, E-SReg(T ) ≤ C § T max{1-c/3,c} and E-CACV(T ) ≤ C § T 1-c/2 , where C § = 3N G + N C Ĉd apG + N C 2 d 2 apG 2 + 1 2 apN G 2 R 2 X + N Ĉ2 4a(a-1)p ( Ĉ is shown in Theorem 1) and C § = N 2 a-1 C 2 d 2 G 2 + 2apGR X + 1 2 a 2 p 2 G 2 R 2 X .

Note that DOCO-LTC achieves a regret scaling as T 3/4 when c = 3 4 , which is identical to that of centralized online bandit optimization Flaxman et al. (2005) . This is rather remarkable considering the decentralized nature of the algorithm. Again, we can improve our bounds in the case of strongly convex loss functions.

Theorem 4 (Strongly convex functions with bandit feedback) Under Assumptions 1-6, the regret and cumulative constraint violation of DOCO-LTC with parameters

η t = 2pG 2 σt , β t = 1 σt , ε t = 1 T b , π = 1 R X T b for b = 1

3 , and all t ≥ 1, satisfy: for all T ≥ 3,

E-SReg(T ) ≤ C § sc T 2/3 log(T ) and E-CACV(T ) ≤ C § sc T log(T ), where C § sc = 3N G + N 2σ 4C ĈGd + 4C 2 d 2 + Ĉ2 G 2 ( Ĉ is shown in Theorem 1) and C § sc = 4pN G √ σ √ GR X + Cd √ σ .

4. NUMERICAL EXPERIMENT:

We illustrate the performance of the proposed algorithms using a simple experiment. Specifically, we consider distributed online regularized linear regression problem over a network, formulated as follows: minimize

EQUATION

where ρ ≥ 0 denotes the regularization parameter. The data

(a i (t), b i (t)) ∈ R d × R is revealed only to unit i at time t.

Results on Synthetic Data. Every entry of a i (t) is generated uniformly at random within the interval [-1, 1] and b i (t) is generated according to b i (t) = a i (t) T x + i (t) where [x] i = 1, for all 1 ≤ i ≤ d/2 and 0 otherwise, and the noise i (t) ∼ N (0, 1). Throughout the experiments, we implement our algorithms over a time-varying directed network depicted in Fig. 1 : the network is not connected in every time-step, but the union graph of any two consecutive time instances is strongly connected, that is, we have B = 2 in Assumption 3. The weight matrices associated with the networks in Fig. 1 To get (not strongly) convex loss functions, we set ρ = 0. We run Algorithm 1 and Algorithm 2 with c = 1/2 and c = 3/4 and plot the maximum regret max i∈V Reg(i, T ), and CACV(T ) as a function of the time horizon T in Fig. 2 (a) and Fig. 2 (b), respectively. It can be seen from Fig. 2 (a) that in the case of full-information feedback, the regret is smaller for c = 1/2, while in bandit feedback setting, the regret is smaller for c = 3/4. This is because c = 1/2 and c = 3/4 correspond to a balanced regret in the full-information setting and bandit feedback setting. By balanced, we mean that 1 -c = c in T max{1-c,c} in Theorem 1 and 1 -c/3 = c in T max{1-c/3,c} in Theorem 3, respectively. From Fig. 2 (b) we also observe that for both feedback models, CACV is smaller for a larger value of c, i.e., c = 3/4. This is in compliance with the results established in Theorems 1 and 3. Finally, the performance is really degraded when going from full information to bandit feedback. This was also expected.

Figure 2 : SReg and CACV vs. time for convex costs.

In the case of strongly convex losses, we run Algorithm 1 and Algorithm 2 with ρ > 0, namely ρ = 1 and ρ = 2. We plot the performance of the algorithms as a function the time horizon in Fig. 3 (a) and Fig. 3 (b), respectively. From Fig. 3 , we confirm that the cost of bandit feedback is rather high. We also observe the regret and the violation constraint are smaller and flatter than those achieved of non-strongly convex loss functions (ρ = 0), for both feedback models. All these observations comply with the results established in Theorems 2 and 4. Results on Real Datasets. We demonstrate the efficiency of our proposed algorithms on two real datasets selected from the LIBSVM1 repository. The details of the datasets are summarized in Table 1 .

We use the same network and parameters as those used in the synthetic data and let c = 1/2. For each dataset, we run Algorithm 1 and Algorithm 2 with ρ = 0 and ρ = 1, respectively. We plot the performance of the algorithms as a function the time horizon in Fig. 4 (mg dataset) and Fig. 5 (bodyfat dataset), respectively. These numerical experiments on real-world datasets show the convergence of the proposed algorithms and are consistent with the results established in Theorems 1-4. Finally, the performance is really degraded when going from strongly convex loss functions to convex loss functions. We finally make comparisons with a standard distributed online projection-free algorithm (D-OCG in Zhang et al. ( 2017)) using mg and bodyfat real datasets. The detailed results are provided in Fig. 6 . From these plots one can confirm that: (i) Our DOCO algorithm achieves better performance than D-OCG under the same information feedback (of course, D-OCG exhibits no constraint violations); and (ii) For both algorithms, the performance is degraded from full information to bandit feedback.

5. CONCLUSIONS:

In this paper, we consider the distributed online convex optimization problem with long-term constraints under full-information and bandit feedback. By introducing and exploiting the notion of online augmented Lagrangian function, we develop distributed algorithms that are based on consensus algorithms. For the case of full-information feedback, we establish sub-linear regret and cumulative absolute constraint violations that match those of centralized online optimization in the literature. Moreover, we also establish sub-linear regret and constraint violation in the case of bandit feedback, where the loss function can be locally evaluated at one point in each time-step.

APPENDIX A PROOF OF THEOREM 1:

A.1 KEY LEMMAS

The following two lemmas are crucial to the convergence analysis of Algorithm 1. The first lemma establishes the basic convergence results of Algorithm 1.

Lemma 1 (Basic Convergence) Let Assumptions 1 and 2 hold. For every node i • ∈ V and T ≥ 1, we have

Reg(i • , T ) ≤ T t=1 N i=1 x i (t) -x 2 - N i=1 x i (t + 1) -x 2 2β t + N G 2 T t=1 β t + G T t=1 N i=1 x i • (t) -x i (t) - T t=1 N i=1 p s=1 [c s (x i (t))] 2 + 1 η t-1 -pG 2 β t η 2 t-1

.

Proof. To simplify the presentation, we write

∇ i (t) ∇ x L i,t (x i (t), λ i (t)).

We study the general evolution of

x i (t + 1) -x 2 , x i (t + 1) -x 2 = Π B (p i (t)) -x 2 ≤ p i (t) -x 2

where the inequality is based on the non-expansiveness of the Euclidean projection and x ∈ X ⊆ B. Expanding the right-hand side, we further obtain

N i=1 x i (t + 1) -x 2 ≤ N i=1 N j=1 [A(t)] ij [x j (t) -β t ∇ j (t)] -x 2 ≤ N i=1 N j=1 [A(t)] ij x j (t) -x -β t ∇ j (t) 2 ≤ N i=1 x i (t) -x -β t ∇ i (t) 2 = N i=1 x i (t) -x 2 + β 2 t N i=1 ∇ i (t) 2 -2β t N i=1 ∇ i (t) T (x i (t) -x ) ≤ N i=1 x i (t) -x 2 + β 2 t N i=1 ∇ i (t) 2 -2β t N i=1 [L i,t (x i (t), λ i (t)) -L i,t (x , λ i (t))]

(7) where the second and third inequalities follow from the doubly stochasticity of A(t) and the last inequality from the convexity of L i,t (x, λ) with respect to x. Combining the preceding inequality with the definition of online augmented Lagrangian function in (3), yields

EQUATION

)

On the other hand, it follows from Assumption 2 that

∇ i (t) 2 = ∇ i,t (x i (t)) + p s=1 [λ i (t)] s ∂[c s (x i (t))] + 2 ≤ 2 ∇ i,t (x i (t)) 2 + 2p p s=1 [λ i (t)] 2 s ∂[c s (x i (t))] + 2 ≤ 2G 2 + 2pG 2 p s=1 [λ i (t)] 2 s = 2G 2 + 2pG 2 p s=1 [c s (x i (t))] 2 + η 2 t-1 (9)

where the last equality follows from the dual update (4). Combining the inequalities ( 8) and ( 9), and using the fact that

[λ i (t)] s = [cs(xi(t))]+ ηt-1

(cf. ( 4)), we obtain

EQUATION

)

The left-hand side can be further lower bounded by

EQUATION

summing the inequalities in (10) over t = 1, . . . , T , and using the bound ( 11) and definition of regret (1), we arrive at the desired conclusion.

Remark 1 The first two terms in Lemma 1 are optimization errors that are common in the analysis of online optimization algorithms, the third term is the cost of aligning the decisions of nodes, and the last term is the penalty incurred by the violation of constraints.

The second lemma establishes a bound on the disagreement among all the nodes, which is measured by the difference between the norms of decisions of nodes.

Lemma 2 (Disagreement) Let Assumptions 1-4 hold. For every node i • ∈ V and T ≥ 1, we have

T t=1 N i=1 x i • (t) -x i (t) ≤ N ĈG T t=1 β t + ĈG T t=1 N i=1 p s=1 [c s (x i (t))] + β t η t-1

where Ĉ is given in Theorem 1.

Proof. By deriving the general expressions for the average decision

x(t + 1) = 1 N N i=1 x i (t + 1) and x i (t + 1) it follows that N i=1 x(t + 1) -x i (t + 1) ≤ N i=1 t m=1 β m N j=1 [A(t, m)] i,j -N -1 ∇ j (m) + N i=1 t-1 m=1 N j=1 [A(t, m + 1)] i,j -N -1 • Π B (p j (m)) -p j (m) + 2 N i=1 Π B (p i (t)) -p i (t) (12) where A(t, m) = A(t) • • • A(m), ∀t ≥ m ≥ 1 and A(t, t) = A(t).

On the other hand, by resorting to Corollary 1 in Nedic et al. (2008) , we have that, for all t ≥ m ≥ 1,

EQUATION

)

Combining the inequalities ( 12) and ( 13), we obtain

EQUATION

)

Then, combining ( 9) and ( 14) with the following inequality,

N i=1 x i • (t) -x i (t) = N i=1 x i • (t) -x(t) + x(t) -x i (t) = N i=1 x i • (t) -x(t) + N i=1 x(t) -x i (t) ≤ (N + 1) N i=1 x(t) -x i (t)

we arrive at the conclusion. The proof is complete.

A.2 PROOF OF THE THEOREM:

We consider an arbitrary unit i • ∈ V and establish a regret bound for that unit. Combining the results in Lemmas 1 and 2, we have

EQUATION

Substituting η t = 1 T c and β t = 1 apG 2 T c into the preceding inequality, yields

EQUATION

)

We turn our attention to bound the last two terms. To this end, write

EQUATION

which implies that

EQUATION

because of the inequality that (a

1 + • • • + a n ) 2 ≤ n n i=1 a 2 i .

Hence, (16) now becomes

EQUATION

)

where we have used Assumption 1, i.e.,

N i=1 x i (1) -x 2 = N i=1 x 2 ≤ N R 2 X .

We can replace the term f (ρ) by the following,

EQUATION

Hence, combining the inequalities ( 19) and ( 20), we finally have

EQUATION

Therefore, we complete the first statement of Theorem 1.

We are left to bound the CACV. From (10) it follows that

EQUATION

the right-hand side can be bounded by following similar lines as that of the regret analysis, that is,

EQUATION

)

the left-hand side on ( 22) can be bounded as follows, according to Assumptions 1 and 2:

EQUATION

Combining ( 23) and ( 24) and regrouping terms, we have

T t=1 N i=1 p s=1 [c s (x i (t))] 2 + ≤ a 2 p 2(a -1) N G 2 R 2 X + N (a -1)p T 1-2c + 2a a -1 N GR X T 1-c ≤ N a -1 1 p + 2aGR X + 1 2 a 2 pG 2 R 2 X T 1-c

the desired bound follows by combining the preceding inequality and ( 18). The proof is complete.

B PROOF OF THEOREM 2:

We first derive the bound on CACV. Note that L i,t (x, λ) is σ-strongly convex, according to Assumption 5. This fact, combined with (7), leads to

N i=1 x i (t + 1) -x 2 ≤ N i=1 x i (t) -x 2 + β 2 t N i=1 ∇ i (t) 2 -2β t N i=1 L i,t (x i (t), λ i (t))-L i,t (x , λ i (t))+ σ 2 x i (t) -x 2 (25)

regrouping the terms, we further have

T t=1 N i=1 [L i,t (x i (t), λ i (t)) -L i,t (x , λ i (t))] ≤ T t=1 N i=1 x i (t) -x 2 - N i=1 x i (t + 1) -x 2 2β t - σ 2 T t=1 x i (t) -x 2 + T t=1 β t 2 N i=1 ∇ i (t) 2 = 1 2 T t=2 1 β t - 1 β t-1 -σ N i=1 x i (t) -x 2 + 1 2 1 β 1 -σ N i=1 x i (1) -x 2 - 1 2β T N i=1 x i (T + 1) -x 2 + T t=1 β t 2 N i=1 ∇ i (t) 2 . Substituting β t = 1

σt into the preceding inequality and dropping the negative term, yields

EQUATION

)

Noting that λ i (t) is the maximizer of L i,t ((x i (t), λ) over λ ∈ R p + , i.e., L i,t (x i (t), λ i (t)) ≥ L i,t (x i (t), λ) for all λ ∈ R p + , we have the following estimate for all λ ∈ R p + , according to (26),

EQUATION

)

Expanding the left-hand side by using the definition of online augmented Lagrangian function in (3), we further have

EQUATION

where we recalled (9). Applying η t = 2pG 2 β t to (28), we find that the last terms on both sides will cancel each other out. This leads to

EQUATION

note that (29) holds for all λ ∈ R d + , and hence we can replace g(λ) by the following,

EQUATION

)

where the last inequality follows from the same reasoning as that of (24). For the left-hand side on (30), we have

EQUATION

Under review as a conference paper at ICLR 2020

Combining the inequalities ( 30) and ( 31) with the following estimate,

EQUATION

we further obtain for all T ≥ 3,

EQUATION

Next, we turn our attention to the first statement, i.e., the regret bound. Again We consider an arbitrary unit i • ∈ V. Combining the inequalities ( 30) and ( 31), and using the notation (17), we obtain

EQUATION

)

Applying Lemma 2 to the preceding inequality gives

EQUATION

substituting the expressions for β t and η t into (35), we have

EQUATION

Then, following an argument similar to that of ( 20) and ( 21), we get

Reg(i • , T ) ≤ N G 2 (1 + Ĉ) T t=1 β t + ( 1 2p Ĉ) 2 4 1 2pN T t=1 ηt ≤ N G 2 (1 + Ĉ) T t=1 β t + 1 8p N Ĉ2 T t=1 η t ≤ 2N G 2 (1 + Ĉ) σ + N Ĉ2 G 2 2σ log(T ).

(37) The proof is complete.

C PROOF OF THEOREM 3 C.1 KEY LEMMA:

The proof relies on the properties of the one-point gradient estimator ∇ i,t (x i (t)), which can be viewed as a distributed version of the one in Flaxman et al. (2005) . In particular, we have the following lemma that characterizes the properties of the one-point gradient estimator and the relation between i,t (x) and its smoothed version ˜ i,t (x; ε).

Lemma 3:

(i) Let G be the uniform Lipschitz constant of the loss functions i,t (x) over B, then the smoothed loss functions ˜ i,t (x) are Lipschitz continuous with the same constant G and we have that, for all x ∈ B, ˜ i,t (x; ε)i,t (x) ≤ Gε.

(ii) The one-point gradient estimator satisfies

E ∇ i,t (x i (t)) = ∇ ˜ i,t (x i (t); ε t ).

(iii) Let Assumption 6 hold, then the one-point gradient estimator satisfies

EQUATION

then, it follows from Lemma 3(ii) that

EQUATION

Following similar lines as that of Lemma 1, we immediately have

N i=1 x i (t + 1) -x π 2 = N i=1 x i (t) -x π 2 + β 2 t N i=1 ∇i (t) 2 -2β t N i=1 ∇i (t) T (x i (t) -x π ) (40) where x π = (1 -π)x ∈ (1 -π)X ⊆ (1 -π)B.

Taking expectation on both sides of (40) and using (39), yields

EQUATION

)

Using the definition (5), the left-hand side on (41) becomes

EQUATION

where the equality follows from [c s (x π )] + = 0, because x π ∈ (1 -π)X ⊂ X . On the other hand, it follows from (38) and Lemma 3(iii) that

EQUATION

this, combined with equations ( 41) and ( 42), gives

EQUATION

)

the left-hand side on (44) can be further lower bounded by utilizing the relation between the losses i,t and their smoothed variants ˜ i,t (cf. Lemma 3(i)), given as follows:

EQUATION

)

where the last inequality follows from the fact that i,t is G-Lipschitz and x ≤ R X . Summing the inequalities in (44) over t = 1, . . . , T and using (45), we find that

T t=1 N i=1 E [ i,t (x i (t)) -i,t (x )] ≤ N GR X πT + 2N G T t=1 ε t + N C 2 d 2 T t=1 β t ε 2 t + T t=1 N i=1 E x i (t) -x π 2 - N i=1 E x i (t + 1) -x π 2 2β t - T t=1 N i=1 p s=1 E [c s (x i (t))] 2 + 1 η t-1 -pG 2 β t η 2 t-1

.

(46) On the other hand, we have the following estimate of the disagreement among nodes by resorting to Lemma 2:

EQUATION

where the second inequality is based on (43). Combining inequalities ( 46) and ( 47), and following an argument similar to that of Theorem 1, we obtain

EQUATION

) Substituting η t = 1 T c , β t = 1 apG 2 T c , ε t = 1 T b and π = 1 R X T b

into the preceding inequality, and following similar lines as that of Theorem 1, yields

EQUATION

It follows from some simple algebra that the choice of b = c 3 yields the optimal regret bound O(T max{1-c/3,c} ).

The bound on CACV can be derived by lower bounding the left-hand side on (44), that is,

N i=1 E ˜ i,t (x i (t); ε t ) -˜ i,t (x π ; ε t ) ≥ -G N i=1 E[ x i (t) -x π ] ≥ -2N GR X

where the first inequality follows from Lemma 3(i) and the last one from Assumption 1. This, combined with (44) and the expressions of

η t = 1 T c , β t = 1 apG 2 T c , ε t = 1 T b and π = 1 R X T b , leads to T t=1 N i=1 p s=1 E [c s (x i (t))] 2 + ≤ N a -1 2aGR X T 1-c + 1 2 a 2 pG 2 R 2 X + C 2 d 2 pG 2 T 1+2b-2c ≤ N a -1 2aGR X + 1 2 a 2 pG 2 R 2 X + C 2 d 2 pG 2 T 1-c (50)

where in the last inequality we used b = c 3 . The desired result follows by combining the preceding inequality with the following, 

D PROOF OF THEOREM 4:

We first claim that the strongly convexity of the loss functions i,t implies the strongly convexity of their smoothed variants ˜ i,t with the same constant σ. This fact leads us to the following bound that is analogous to (26):

EQUATION

)

Following an argument similar to that of Theorem 2, we can replace the left-hand side on (52) by the following, due to the fact that λ i (t) is the maximizer of Combining the equations ( 52), ( 53) and (54), and using η t = 2pG 2 β t , we find that for all λ ∈ R p + and T ≥ 3,

EQUATION

where we recalled (32). Substituting λ = λ , the maximizer of g(λ) over λ ∈ R p + , into the (55), the left-hand side on ( 55 where we used b = 1 3 . We now turn our attention to the regret bound. It follows from ( 55) and (56) that

T t=1 N i=1 E ˜ i,t (x i (t)) -˜ i,t (x π ) ≤ N C 2 d 2 T t=1 β t ε 2 t - (E [ρ]) 2 2pN

T t=1 η t this, combined with (45), further leads to

T t=1 N i=1 E [ i,t (x i (t)) -i,t (x )] ≤ N GR X πT +2N G T t=1 ε t +N C 2 d 2 T t=1 β t ε 2 t - (E [ρ]) 2 2pN T t=1 η t .

(57) Then, following the similar lines as that of Theorem 2 and using the disagreement estimate (47), we find that

EQUATION

where the last inequality follows from the same reasoning as that of ( 35)-( 37). This, combined with η t = 2pG 2 σt , β t = 1 σt , ε t = 1 T b and π = 1 R X T b , leads to

EQUATION

) hence, the optimal regret bound follows by setting b = 1 3 . The proof is complete.

:

https://www.csie.ntu.edu.tw/ ˜cjlin/libsvmtools/datasets/

Figures and Tables:

Figure 1: The network switches sequentially in a round robin manner between (a), (b), (c), and (d).

Figure 3: SReg and CACV vs. time for strongly convex costs.

Figure 4: SReg and CACV vs. time for mg dataset.

Figure 5: SReg and CACV vs. time for bodyfat dataset.

's inequality. The proof is complete.

[c s (x i (t))] + ] inequality follows from Jensen's inequality. Combining the inequalities in (32), (55

Summary of datasets dataset # of features # of instances

Table content: <table><tr><td>mg</td><td>6</td><td>1385</td></tr><tr><td>bodyfat</td><td>14</td><td>252</td></tr></table>

Li,t ((x i (t), λ) over λ ∈ R p + : is defined in (29). On the other hand, using (43) we have

Table content: <table><tr><td colspan="5">where g(λ) E ∇i (t)</td><td>2</td><td colspan="2">≤ 2C 2 d 2 1 t ε 2</td><td colspan="2">+ 2pG 2 E λ i (t) 2</td><td>(54)</td></tr><tr><td>T</td><td/><td>N</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td colspan="6">E Li,t (x i (t), λ) -Li,t (x π , λ i (t))</td></tr><tr><td colspan="2">t=1</td><td colspan="2">i=1</td><td/><td/><td/><td/><td/></tr><tr><td>=</td><td colspan="2">T t=1</td><td>N i=1</td><td colspan="2">E ˜ i,t (x i (t)) +</td><td>p s=1</td><td colspan="2">[λ] s [c s (x i (t))] + -</td><td>η t 2</td><td>λ 2</td><td>(53)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>T</td><td>N</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>η t E λ i (t) 2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>t=1</td><td>i=1</td></tr></table>

Peer review (iclr2020):
The authors study distributed online convex optimization where the distributed system consists of various computing units connected by a time varying graph. The authors prove optimal regret bounds for a proposed decentralized algorithm and experimentally evaluate the performance of their algorithms on distributed online regularized linear regression problems. The paper seems well written and well researched and places itself well in context of current literature. The authors also improve the state of the art in the field. The main weakness of the paper is the limited experimental evaluation and applicability of the assumptions and the theoretical setting that underpins this work. [Edit: After going through the other reviews, I have downgraded my score. The revised version of the paper the authors uploaded is 23 pages long with the main paper body being 10 pages. The CFP instructs reviewers to apply a higher standard to judge such long papers. I am not convinced that the paper is solving an important problem that merits such a long paper.]