Year: 2019

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 inO(Tmax{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(Tmax{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.

text: √ T log(T )). These re-
gret 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(Tmax{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.

heading: 1 INTRODUCTION
text: 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 xi(t) and then experiences a local loss equal to `i,t(xi(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 minx ∑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 ai,t ∈ Rd (according to the “bag-of-words” representation). Unit i applies for this email a filter represented
by a vector xi(t) ∈ X where X is convex compact subset of Rd, returns a label f(a>i,txi(t)), and experiences a loss equal to `i,t(xi(t)) = (f(a>i,txi(t))− yi,t)2 where yi,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.

heading: 1.1 THE DOCO (DISTRIBUTED ONLINE CONVEX OPTIMIZATION) FRAMEWORK
text: 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 Gt = {V, Et} with node set V = {1, . . . , N} and edge set Et at time t. Gt 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 Gt. Each unit i ∈ V is associated with a sequence of convex loss functions {`i,t}Tt=1, where `i,t : Rd → R.
Optimization process. In each time-step t, each unit i ∈ V selects xi(t) ∈ Rd. 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(xi(t)) is revealed only. Unit i finally receives vectors, functions of decisions selected by its neighbors in Gt, i.e., xj(t) for j such that (j, i) ∈ Et, and updates its decision for the next time-step.
Decision constraints. The decisions should be selected in X a convex subset of Rd characterized by a family of inequalities: X = {x ∈ Rd | cs(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 cs(xi(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:
Reg(i, T ) := T∑ t=1 N∑ j=1 `j,t(xi(t))− T∑ t=1 N∑ j=1 `j,t(x ?), (1)
where x? = arg minx∈X ∑T t=1 ∑N j=1 `j,t(x). The system-level regret is defined as the worst pos-
sible regret at all units: SReg(T ) , maxi=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 [cs(xi(t))]+. (2)

heading: 1.2 MAIN RESULTS
text: 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(Tmax{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(d2Tmax{1−c/3,c}) and O(dT 1−c/2), respectively, for any c ∈ (0, 1). For example, when c = 34 , the proposed algorithm attains a regret bound in O(d2T 3/4). The performance guarantees can be improved to O(d2T 2/3 log(T )) and O(d √ T log(T )) in the case of strongly convex losses.

heading: 1.3 RELATED WORK
text: 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 inO(Tmax{c,1−c}) andO(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(d2T 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(d2 √ T ) and O(d2 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(d2T 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 ∈ Rd, respectively. Let ΠX [x] be the Euclidean projection of a vector x onto the set X . Let Rp+ be the nonnegative orthant in Rp: R p + = {x ∈ Rp | [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 {at}∞t=1 and {bt}∞t=1, we write at = O(bt) if lim supt→∞ at/bt <∞.

heading: 2 FULL-INFORMATION FEEDBACK
text: 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 ∈ Rd | ‖x‖ ≤ RX } with RX > 0.
Assumption 2 The functions `i,t and cs 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 ‖∇cs(x)‖ ≤ Gc.
We let G = max{G`, Gc}.
Assumption 3 There exists an integer B ≥ 1 such that the union graph (V, EkB+1∪· · ·∪E(k+1)B) is strongly connected for all k ≥ 0.
Assumption 4 Associated with Gt 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) ∈ Et 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 & Cortés (2010).
Algorithm 1 DOCO-LTC with full-information feedback Input: Step sizes {βt}Tt=1, regularization parameters {ηt}Tt=1 Initialize: xi(1) = 0 ∈ Rd,λi(1) = 0 ∈ Rp,∀i = 1, . . . , N
1: for t = 1 to T do 2: Unit i commits to a decision xi(t), and then after receiving `i,t, compute
yi(t) = xi(t)− βt [ ∇`i,t(xi(t)) +
p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ ] 3: Unit i communicates yi(t) to its neighbors and updates its decision as
xi(t+ 1) = ΠB (pi(t)) , where pi(t) = N∑ j=1 [A(t)]ijyj(t)
4: Unit i updates its dual variable: λi(t+ 1) = arg maxλ∈Rd+ Li,t((xi(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,
Li,t(x,λ) , `i,t(x) + p∑ s=1 [λ]s[cs(x)]+ − ηt 2 ‖λ‖2, (3)
where λ = [[λ]1, . . . , [λ]p]T ∈ Rp+ is the vector of Lagrangian multipliers with [λ]s being associated with the sth inequality constraint cs(x) ≤ 0 and ηt is the regularization parameter. We note that:
∇xLi,t(xi(t),λi(t)) = ∇`i,t(xi(t)) + p∑ s=1 [λi(t)]s∂[cs(xi(t))]+,
where ∂[cs(xi(t))]+ can be calculated as follows for s = 1, . . . , p:
∂[cs(xi(t))]+ = { ∇cs(xi(t)), if cs(xi(t)) > 0 0, otherwise.
Moreover, the dual update λi(t+ 1) in DOCO-LTC can be calculated explicitly as follows:
[λi(t+ 1)]s = [cs(xi(t+ 1))]+
ηt , s = 1, . . . , p. (4)
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 = 1T c and βt =
1 apG2T c for some c ∈ (0, 1), a > 1, and all t ≥ 1, satisfy: for all T ≥ 1,
SReg(T ) ≤ C̃Tmax{1−c,c} and CACV(T ) ≤ C̄T 1−c/2,
where C̃ = 12apNG 2R2X + 1 apN(1 + Ĉ) +
NĈ2 4a(a−1)p with Ĉ = 2N ( 3N ψ2+1/B(1−ψ1/B) + 4 ) and
ψ = ( 1− ζ4N2 )−2 , and C̄ = √ N2 a−1 ( 1 + 2apGRX + 1 2a 2p2G2R2X ) .
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 ( N4
(1−σ2(A))2T 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
log2(N) Tmax{c,1−c} and at most 2 log1+ (N)N vectors are transmitted per round;
ii) k-regular expander graph: σ2(A) is constant, the regret bounds scales as N4Tmax{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 ) ≤ C̃sc log(T ), and CACV(T ) ≤ C̄sc √ T log(T ),
where C̃sc = NG 2 2σ (4 + 4Ĉ + Ĉ 2) (Ĉ is shown in Theorem 1) and C̄sc = 4pNG
3/2
√ σ
(√ RX + √ 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).

heading: 3 ONE-POINT BANDIT FEEDBACK
text: 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 xi(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}Tt=1, regularization parameters {ηt}Tt=1, exploration parameters {εt}Tt=1, and
shrinkage parameter π Initialize: xi(1) = 0 ∈ Rd,λi(1) = 0 ∈ Rp,∀i = 1, . . . , N
1: for t = 1 to T do 2: Unit i commits to a decision xi(t), and then observes the loss `i,t(xi(t) + εtui(t)) where ui(t) is randomly chosen on the unit sphere (‖ui(t)‖ = 1) 3: Unit i builds the following one-point gradient estimator:
∇̃`i,t(xi(t)) = d
εt `i,t(xi(t) + εtui(t))ui(t)
and computes
yi(t) = xi(t)− βt [ ∇̃`i,t(xi(t)) +
p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ ] 4: Unit i updates its decision using yj(t) received from its neighbors as
xi(t+ 1) = ΠB (pi(t)) , where pi(t) = N∑ j=1 [A(t)]ijyj(t)
5: Node i updates its dual variable λi(t+ 1) = arg maxλ∈Rd+ L̃i,t((xi(t+ 1),λ) 6: end for
The design and convergence analysis of our algorithm here rely on the smoothed version L̃i,t(x,λ) of the online augmented Lagrangian function (3), i.e., L̃i,t(x,λ): for t ≥ 1,
L̃i,t(x,λ) , ˜̀i,t(x; ε) + p∑ s=1 [λ]s[cs(x)]+ − ηt 2 ‖λ‖2, (5)
where ˜̀i,t(x; ε) = Ev [`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 xi(t) + εtui(t) belongs to the set B. Indeed, we have:
‖xi(t) + εtui(t)‖ ≤ ‖xi(t)‖+ εt‖ui(t)‖ ≤ (1− π)RX + εt ≤ RX where the second inequality follows from the fact that xi(t) ∈ (1 − π)B and ‖ui(t)‖ = 1 and the last inequality holds when εt ≤ πRX . 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 ) := maxi=1,...,N E[Reg(i, T )] and E-CACV(T ) := ∑T t=1 ∑N i=1 ∑p s=1 E[[cs(xi(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
apG2T c , εt =
1
T b , π =
1
RXT b
for some c ∈ (0, 1), b = c/3 and all t ≥ 1, satisfy: for all T ≥ 1, E-SReg(T ) ≤ C̃§Tmax{1−c/3,c} and E-CACV(T ) ≤ C̄§T 1−c/2,
where C̃§ = 3NG + NCĈdapG + NC2d2 apG2 + 1 2apNG 2R2X + NĈ2 4a(a−1)p (Ĉ is shown in Theorem 1) and C̄§ = √ N2 a−1 ( C2d2 G2 + 2apGRX + 1 2a 2p2G2R2X ) .
Note that DOCO-LTC achieves a regret scaling as T 3/4 when c = 34 , 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 = 2pG2
σt , βt =
1
σt , εt =
1
T b , π =
1
RXT b
for b = 13 , and all t ≥ 1, satisfy: for all T ≥ 3, E-SReg(T ) ≤ C̃§scT 2/3 log(T ) and E-CACV(T ) ≤ C̄§sc √ T log(T ),
where C̃§sc = 3NG + N 2σ
( 4CĈGd+ 4C2d2 + Ĉ2G2 ) (Ĉ is shown in Theorem 1) and C̄§sc =
4pNG√ σ (√ GRX + Cd√ σ ) .

heading: 4 NUMERICAL EXPERIMENT
text: 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 ∑T t=1 ∑N i=1 1 2 ( ai(t) Tx− bi(t) )2
+ ρ‖x‖2 subject to cm(x) = L− [x]m ≤ 0, m = 1, . . . , d
cd+m(x) = [x]m − U ≤ 0, m = 1, . . . , d (6)
where ρ ≥ 0 denotes the regularization parameter. The data (ai(t), bi(t)) ∈ Rd×R is revealed only to unit i at time t.
Results on Synthetic Data. Every entry of ai(t) is generated uniformly at random within the interval [−1, 1] and bi(t) is generated according to
bi(t) = ai(t) Tx̄ + i(t)
where [x̄]i = 1, for all 1 ≤ i ≤ bd/2c 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 are generated according to the maximum-degree weights (see, e.g., Yuan et al. (2019)). We set the parameters as follows: N = 6, d = 4, L = −0.15, U = 0.15, and RX = U √ d. The performance of DOCO-LTC is averaged over 10 runs.
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 maxi∈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 Tmax{1−c,c} in Theorem 1 and 1− c/3 = c in Tmax{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.
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
1https://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/
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.

heading: 5 CONCLUSIONS
text: 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.

heading: A PROOF OF THEOREM 1
text: 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 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2 2βt +NG2 T∑ t=1 βt
+G T∑ t=1 N∑ i=1 ‖xi•(t)− xi(t)‖ − T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ( 1 ηt−1 − pG2 βt η2t−1 ) .
Proof. To simplify the presentation, we write
∇i(t) , ∇xLi,t(xi(t),λi(t)). We study the general evolution of ‖xi(t+ 1)− x?‖2,
‖xi(t+ 1)− x?‖2 = ‖ΠB (pi(t))− x?‖2 ≤ ‖pi(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 ‖xi(t+ 1)− x?‖2 ≤ N∑ i=1 ∥∥∥∥∥∥ N∑ j=1 [A(t)]ij [xj(t)− βt∇j(t)]− x? ∥∥∥∥∥∥ 2
≤ N∑ i=1 N∑ j=1 [A(t)]ij‖xj(t)− x? − βt∇j(t)‖2 ≤ N∑ i=1 ‖xi(t)− x? − βt∇i(t)‖2
= N∑ i=1 ‖xi(t)− x?‖2 + β2t N∑ i=1 ‖∇i(t)‖2 − 2βt N∑ i=1 ∇i(t)T(xi(t)− x?)
≤ N∑ i=1 ‖xi(t)− x?‖2 + β2t N∑ i=1 ‖∇i(t)‖2
− 2βt N∑ i=1 [Li,t(xi(t),λi(t))− Li,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 Li,t(x,λ) with respect to x. Combining the preceding inequality with the definition of online augmented Lagrangian function in (3), yields
N∑ i=1
[ `i,t(xi(t)) +
p∑ s=1 [λi(t)]s[cs(xi(t))]+ − ηt 2 ‖λi(t)‖2
− ( `i,t(x ?) +
p∑ s=1 [λi(t)]s[cs(x ?)]+ − ηt 2 ‖λi(t)‖2
)]
≤ ∑N i=1 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2
2βt + βt 2 N∑ i=1 ‖∇i(t)‖2. (8)
On the other hand, it follows from Assumption 2 that
‖∇i(t)‖2 = ∥∥∥∥∥∇`i,t(xi(t)) + p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ ∥∥∥∥∥ 2
≤ 2‖∇`i,t(xi(t))‖2 + 2p p∑ s=1 [λi(t)] 2 s‖∂[cs(xi(t))]+‖2
≤ 2G2 + 2pG2 p∑ s=1 [λi(t)] 2 s
= 2G2 + 2pG2 p∑ s=1 [cs(xi(t))] 2 + η2t−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
N∑ i=1 [`i,t(xi(t))− `i,t(x?)] ≤ ∑N i=1 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2 2βt +NG2βt
− N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ( 1 ηt−1 − pG2 βt η2t−1 ) . (10)
The left-hand side can be further lower bounded by
`i,t(xi(t)) = `i,t(xi•(t)) + `i,t(xi(t))− `i,t(xi•(t)) ≥ `i,t(xi•(t))−G‖xi(t)− xi•(t)‖ (11)
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 ‖xi•(t)− xi(t)‖ ≤ NĈG T∑ t=1 βt + ĈG T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ βt ηt−1
where Ĉ is given in Theorem 1. Proof. By deriving the general expressions for the average decision x̄(t + 1) = 1N ∑N i=1 xi(t + 1) and xi(t+ 1) it follows that
N∑ i=1 ‖x̄(t+ 1)− xi(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(pj(m))− pj(m)‖ + 2
N∑ i=1 ‖ΠB(pi(t))− pi(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,∣∣[A(t,m)]i,j −N−1∣∣ ≤ (1− ζ
4N2
) t−m B −2
. (13)
Combining the inequalities (12) and (13), we obtain T∑ t=1 N∑ i=1 ‖x̄(t)− xi(t)‖ ≤ ( 3N ψ2+1/B(1− ψ1/B) + 4 ) T−1∑ t=1 βt N∑ i=1 ‖∇i(t)‖. (14)
Then, combining (9) and (14) with the following inequality, N∑ i=1 ‖xi•(t)− xi(t)‖ = N∑ i=1 ‖xi•(t)− x̄(t) + x̄(t)− xi(t)‖
= N∑ i=1 ‖xi•(t)− x̄(t)‖+ N∑ i=1 ‖x̄(t)− xi(t)‖
≤ (N + 1) N∑ i=1 ‖x̄(t)− xi(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
Reg(i•, T ) ≤ T∑ t=1 ∑N i=1 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2 2βt + (1 + Ĉ)NG2 T∑ t=1 βt
+ ĈG2 T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ βt ηt−1
− T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ( 1 ηt−1 − pG2 βt η2t−1 ) . (15)
Substituting ηt = 1T c and βt = 1 apG2T c into the preceding inequality, yields
Reg(i•, T ) ≤ 1 2 apG2 ( N∑ i=1 ‖xi(1)− x?‖2 ) T c + 1 ap N(1 + Ĉ)T 1−c
+ 1
ap Ĉ T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ − ( 1− 1 a ) T c T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 +. (16)
We turn our attention to bound the last two terms. To this end, write
ρ , T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ (17)
which implies that T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ≥ 1 pNT ( T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ )2 = 1 pNT ρ2 (18)
because of the inequality that (a1 + · · ·+ an)2 ≤ n ∑n i=1 a 2 i . Hence, (16) now becomes
Reg(i•, T ) ≤ 1 2 apNG2R2XT c + 1 ap N(1 + Ĉ)T 1−c + 1 ap Ĉρ−
( 1− 1
a
) 1
pNT 1−c ρ2︸ ︷︷ ︸
,f(ρ)
. (19)
where we have used Assumption 1, i.e., ∑N i=1 ‖xi(1) − x?‖2 = ∑N i=1 ‖x?‖2 ≤ NR2X . We can replace the term f(ρ) by the following,
max ρ≥0 f(ρ) =
( Ĉ ap )2 4 ( 1− 1a ) 1 pNT 1−c = NĈ2 4a(a− 1)p T 1−c. (20)
Hence, combining the inequalities (19) and (20), we finally have
Reg(i•, T ) ≤ 1 2 apNG2R2XT c + 1 ap N(1 + Ĉ)T 1−c + max ρ≥0 f(ρ)
≤ 1 2 apNG2R2XT c +
( 1
ap N(1 + Ĉ) +
NĈ2
4a(a− 1)p
) T 1−c. (21)
Therefore, we complete the first statement of Theorem 1.
We are left to bound the CACV. From (10) it follows that
T∑ t=1 N∑ i=1 [`i,t(xi(t))− `i,t(x?)] ≤ T∑ t=1 ∑N i=1 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2 2βt
− T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ( 1 ηt−1 − pG2 βt η2t−1 )
+NG2 T∑ t=1 βt (22)
the right-hand side can be bounded by following similar lines as that of the regret analysis, that is,
r.h.s. of (22) ≤ 1 2 apNG2R2XT c + 1 ap NT 1−c −
( 1− 1
a
) T c T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + (23)
the left-hand side on (22) can be bounded as follows, according to Assumptions 1 and 2:
l.h.s. of (22) ≥ −G T∑ t=1 N∑ i=1 ‖xi(t)− x?‖ ≥ −2NGRXT. (24)
Combining (23) and (24) and regrouping terms, we have
T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + ≤ a2p 2(a− 1) NG2R2X +
N
(a− 1)p T 1−2c +
2a
a− 1 NGRXT
1−c
≤ N a− 1
( 1
p + 2aGRX +
1 2 a2pG2R2X
) T 1−c
the desired bound follows by combining the preceding inequality and (18). The proof is complete.

heading: B PROOF OF THEOREM 2
text: We first derive the bound on CACV. Note that Li,t(x,λ) is σ-strongly convex, according to Assumption 5. This fact, combined with (7), leads to
N∑ i=1 ‖xi(t+ 1)− x?‖2 ≤ N∑ i=1 ‖xi(t)− x?‖2 + β2t N∑ i=1 ‖∇i(t)‖2
− 2βt N∑ i=1 [ Li,t(xi(t),λi(t))−Li,t(x?,λi(t))+ σ 2 ‖xi(t)− x?‖2 ] (25)
regrouping the terms, we further have T∑ t=1 N∑ i=1 [Li,t(xi(t),λi(t))− Li,t(x?,λi(t))]
≤ T∑ t=1 ∑N i=1 ‖xi(t)− x?‖2 − ∑N i=1 ‖xi(t+ 1)− x?‖2 2βt
− σ 2 T∑ t=1 ‖xi(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 ‖xi(t)− x?‖2 + 1 2 ( 1 β1 − σ ) N∑ i=1 ‖xi(1)− x?‖2
− 1 2βT N∑ i=1 ‖xi(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 T∑ t=1 N∑ i=1 [Li,t(xi(t),λi(t))− Li,t(x?,λi(t))] ≤ T∑ t=1 βt 2 N∑ i=1 ‖∇i(t)‖2. (26) Noting that λi(t) is the maximizer of Li,t((xi(t),λ) over λ ∈ Rp+, i.e., Li,t(xi(t),λi(t)) ≥ Li,t(xi(t),λ) for all λ ∈ Rp+, we have the following estimate for all λ ∈ R p +, according to (26),
T∑ t=1 N∑ i=1 [Li,t(xi(t),λ)− Li,t(x?,λi(t))] ≤ T∑ t=1 βt 2 N∑ i=1 ‖∇i(t)‖2. (27)
Expanding the left-hand side by using the definition of online augmented Lagrangian function in (3), we further have
T∑ t=1 N∑ i=1
[ `i,t(xi(t)) +
p∑ s=1 [λ]s[cs(xi(t))]+ − ηt 2 ‖λ‖2
− ( `i,t(x ?) +
p∑ s=1 [λi(t)]s[cs(x ?)]+ − ηt 2 ‖λi(t)‖2
)]
≤ T∑ t=1 βt 2 N∑ i=1 ‖∇i(t)‖2 ≤ NG2 T∑ t=1 βt + pG 2 T∑ t=1 N∑ i=1 βt‖λi(t)‖2 (28)
where we recalled (9). Applying ηt = 2pG2βt to (28), we find that the last terms on both sides will cancel each other out. This leads to
T∑ t=1 N∑ i=1 [`i,t(xi(t))− `i,t(x?)] + p∑ s=1 ( T∑ t=1 N∑ i=1 [c(xi(t))]+ ) [λ]s − p∑ s=1 ( 1 2 N T∑ t=1 ηt ) [λ]2s︸ ︷︷ ︸
,g(λ)
≤ NG2 T∑ t=1 βt (29)
note that (29) holds for all λ ∈ Rd+, and hence we can replace g(λ) by the following,
max λ∈Rp+ g(λ) ≤ T∑ t=1 N∑ i=1 [`i,t(x ?)− `i,t(xi(t))] +NG2 T∑ t=1 βt ≤ 2NGRXT +NG2 T∑ t=1 βt (30)
where the last inequality follows from the same reasoning as that of (24). For the left-hand side on (30), we have
max λ∈Rd+ g(λ) = p∑ s=1
(∑T t=1 ∑N i=1[cs(xi(t))]+ )2 2N ∑T t=1 ηt ≥ (∑T t=1 ∑N i=1 ∑p s=1[cs(xi(t))]+ )2 2pN ∑T t=1 ηt
(31)
Combining the inequalities (30) and (31) with the following estimate, T∑ t=1 1 t = 1 + T∑ t=2 1 t ≤ 1 + ∫ T 1 1 u du = 1 + log(T ) (32)
we further obtain for all T ≥ 3, T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ ≤ √ 16p2N2G3RX σ T log(T ) + 16p2N2G4 σ2 log2(T )
≤ ( 4pNG3/2 √ RX√
σ +
4pNG2
σ
)√ T log(T ). (33)
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
NG2 T∑ t=1 βt − 1 2pN ∑T t=1 ηt ρ2 ≥ T∑ t=1 N∑ i=1 [`i,t(xi(t))− `i,t(x?)]
≥ Reg(i•, T )−G T∑ t=1 N∑ i=1 ‖xi•(t)− xi(t)‖. (34)
Applying Lemma 2 to the preceding inequality gives
Reg(i•, T ) ≤ NG2(1 + Ĉ) T∑ t=1 βt− 1 2pN ∑T t=1 ηt ρ2+ĈG2 T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))]+ βt ηt−1
(35) substituting the expressions for βt and ηt into (35), we have
Reg(i•, T ) ≤ NG2(1 + Ĉ) T∑ t=1 βt + 1 2p Ĉρ− 1 2pN ∑T t=1 ηt
ρ2︸ ︷︷ ︸ ,h(ρ) . (36)
Then, following an argument similar to that of (20) and (21), we get
Reg(i•, T ) ≤ NG2(1 + Ĉ) T∑ t=1 βt + ( 12p Ĉ) 2 4 1 2pN ∑T t=1 ηt ≤ NG2(1 + Ĉ) T∑ t=1 βt + 1 8p NĈ2 T∑ t=1 ηt
≤
( 2NG2(1 + Ĉ)
σ + NĈ2G2 2σ
) log(T ).
(37) The proof is complete.

heading: C PROOF OF THEOREM 3
text: C.1 KEY LEMMA
The proof relies on the properties of the one-point gradient estimator ∇̃`i,t(xi(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) LetG 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(xi(t)) ] = ∇˜̀i,t(xi(t); εt).
(iii) Let Assumption 6 hold, then the one-point gradient estimator satisfies∥∥∥∇̃`i,t(xi(t))∥∥∥ ≤ Cd εt .
C.2 PROOF OF THE THEOREM
Denote
∇̃i(t) , ∇̃`i,t(xi(t)) + p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ (38)
then, it follows from Lemma 3(ii) that
E [ ∇̃i(t) ] = ∇˜̀i,t(xi(t); εt) + p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ = ∇xL̃i,t(xi(t),λi(t)). (39)
Following similar lines as that of Lemma 1, we immediately have
N∑ i=1 ‖xi(t+ 1)− x?π‖2 = N∑ i=1 ‖xi(t)− x?π‖2 + β2t N∑ i=1 ∥∥∥∇̃i(t)∥∥∥2 − 2βt N∑ i=1 ∇̃i(t)T(xi(t)− x?π)
(40) where x?π = (1−π)x? ∈ (1−π)X ⊆ (1−π)B. Taking expectation on both sides of (40) and using (39), yields
N∑ i=1 E [ L̃i,t(xi(t),λi(t))− L̃i,t(x?,λi(t)) ] ≤ ∑N i=1 E[‖xi(t)− x?π‖2]− ∑N i=1 E[‖xi(t+ 1)− x?π‖2]
2βt + βt 2 N∑ i=1 E [∥∥∥∇̃i(t)∥∥∥2] . (41)
Using the definition (5), the left-hand side on (41) becomes
N∑ i=1 E
[ ˜̀ i,t(xi(t); εt) +
p∑ s=1 [λi(t)]s[cs(xi(t))]+ − ηt 2 ‖λi(t)‖2
− ( ˜̀ i,t(x ? π; εt) + p∑ s=1 [λi(t)]s[cs(x ? π)]+ − ηt 2 ‖λi(t)‖2 )]
= N∑ i=1 E [ ˜̀ i,t(xi(t); εt)− ˜̀i,t(x?π; εt) ] + N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 + ] ηt−1
(42)
where the equality follows from [cs(x?π)]+ = 0, because x ? π ∈ (1 − π)X ⊂ X . On the other hand, it follows from (38) and Lemma 3(iii) that
E [∥∥∥∇̃i(t)∥∥∥2] = E ∥∥∥∥∥∇̃`i,t(xi(t)) + p∑ s=1 [λi(t)]s∂[cs(xi(t))]+ ∥∥∥∥∥ 2 
≤ 2E [ ‖∇̃`i,t(xi(t))‖2 ] + 2pG2 p∑ s=1 E [ [λi(t)] 2 s ] ≤ 2C2d2 1
ε2t + 2pG2 p∑ s=1
E [ [cs(xi(t))] 2 + ] η2t−1
(43)
this, combined with equations (41) and (42), gives
N∑ i=1 E [ ˜̀ i,t(xi(t); εt)− ˜̀i,t(x?π; εt) ] ≤ NC2d2 βt
ε2t +
∑N i=1 E [ ‖xi(t)− x?π‖2 ] − ∑N i=1 E [ ‖xi(t+ 1)− x?π‖2 ] 2βt
− N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 + ]( 1 ηt−1 − pG2 βt η2t−1 ) . (44)
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:
˜̀ i,t(xi(t); εt)− ˜̀i,t(x?π; εt) ≥ `i,t(xi(t))− `i,t(x?π)− 2Gεt
≥ `i,t(xi(t))− `i,t(x?)−GRXπ − 2Gεt (45)
where the last inequality follows from the fact that `i,t is G-Lipschitz and ‖x?‖ ≤ RX . Summing the inequalities in (44) over t = 1, . . . , T and using (45), we find that T∑ t=1 N∑ i=1 E [`i,t(xi(t))− `i,t(x?)] ≤ NGRXπT + 2NG T∑ t=1 εt +NC 2d2 T∑ t=1 βt ε2t
+ T∑ t=1 ∑N i=1 E [ ‖xi(t)− x?π‖2 ] − ∑N i=1 E [ ‖xi(t+ 1)− x?π‖2 ] 2βt
− T∑ t=1 N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 + ]( 1 ηt−1 − pG2 βt η2t−1 ) .
(46) On the other hand, we have the following estimate of the disagreement among nodes by resorting to Lemma 2:
T∑ t=1 N∑ i=1 E [‖xi•(t)− xi(t)‖] ≤ Ĉ T−1∑ t=1 βt N∑ i=1 E [∥∥∥∇̃i(t)∥∥∥]
≤ Ĉ T∑ t=1 βt N∑ i=1
( Cd
εt +G p∑ s=1 E [[cs(xi(t))]+] ηt−1
)
≤ NCĈd T∑ t=1 βt εt + ĈG T∑ t=1 N∑ i=1 p∑ s=1 E [ [cs(xi(t))]+ ] βt ηt−1
(47)
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
E [Reg(i•, T )] ≤ NGRXπT + 2NG T∑ t=1 εt +NCĈGd T∑ t=1 βt εt +NC2d2 T∑ t=1 βt ε2t
+ T∑ t=1 ∑N i=1E [ ‖xi(t)− x?π‖2 ] − ∑N i=1 E [ ‖xi(t+ 1)− x?π‖2 ] 2βt
+ ĈG2 T∑ t=1 N∑ i=1 p∑ s=1 E [[cs(xi(t))]+] βt ηt−1
− T∑ t=1 N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 + ]( 1 ηt−1 − pG2 βt η2t−1 ) . (48)
Substituting ηt = 1T c , βt = 1 apG2T c , εt = 1 T b and π = 1 RXT b into the preceding inequality, and following similar lines as that of Theorem 1, yields
E [Reg(i•, T )] ≤ 3NGT 1−b + NCĈd apG T 1+b−c + NC2d2 apG2 T 1+2b−c
+ 1
2 apNG2R2XT
c + NĈ2
4a(a− 1)p T 1−c. (49)
It follows from some simple algebra that the choice of b = c3 yields the optimal regret bound O(Tmax{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(xi(t); εt)− ˜̀i,t(x?π; εt) ] ≥ −G N∑ i=1 E[‖xi(t)− x?π‖] ≥ −2NGRX
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 = 1T c , βt = 1 apG2T c , εt = 1 T b and π = 1 RXT b
, leads to
T∑ t=1 N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 + ] ≤ N a− 1 ( 2aGRXT 1−c + 1 2 a2pG2R2X + C2d2 pG2 T 1+2b−2c ) ≤ N a− 1 ( 2aGRX + 1 2 a2pG2R2X + C2d2 pG2 ) T 1−c (50)
where in the last inequality we used b = c3 . The desired result follows by combining the preceding inequality with the following,
T∑ t=1 N∑ i=1 p∑ s=1 E [[cs(xi(t))]+] ≤ E (pNT T∑ t=1 N∑ i=1 p∑ s=1 [cs(xi(t))] 2 + )1/2 ≤ ( pNT
T∑ t=1 N∑ i=1 p∑ s=1 E [ [cs(xi(t))] 2 +
])1/2 (51)
because of Jensen’s inequality. The proof is complete.

heading: D PROOF OF THEOREM 4
text: 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):
T∑ t=1 N∑ i=1 E [ L̃i,t(xi(t),λi(t))− L̃i,t(x?,λi(t)) ] ≤ T∑ t=1 βt 2 N∑ i=1 E [∥∥∥∇̃i(t)∥∥∥2] . (52)
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 L̃i,t((xi(t),λ) over λ ∈ Rp+:
T∑ t=1 N∑ i=1 E [ L̃i,t(xi(t),λ)− L̃i,t(x?π,λi(t)) ] =
T∑ t=1 N∑ i=1 E
[ ˜̀ i,t(xi(t)) +
p∑ s=1 [λ]s[cs(xi(t))]+ − ηt 2 ‖λ‖2
− ( ˜̀ i,t(x ? π) + p∑ s=1 [λi(t)]s[cs(x ? π)]+ − ηt 2 ‖λi(t)‖2 )]
= T∑ t=1 N∑ i=1 E [ ˜̀ i,t(xi(t))− ˜̀i,t(x?π) ] + E [g(λ)] + 1 2 T∑ t=1 N∑ i=1 ηtE [ ‖λi(t)‖2
] (53)
where g(λ) is defined in (29). On the other hand, using (43) we have E [∥∥∥∇̃i(t)∥∥∥2] ≤ 2C2d2 1
ε2t + 2pG2E
[ ‖λi(t)‖2 ] (54)
Combining the equations (52), (53) and (54), and using ηt = 2pG2βt, we find that for all λ ∈ Rp+ and T ≥ 3,
E [g(λ)] ≤ T∑ t=1 N∑ i=1 E [ ˜̀ i,t(x ? π)− ˜̀i,t(xi(t)) ] +NC2d2 T∑ t=1 βt ε2t
≤ 2NGRXT + NC2d2
σ T 2b T∑ t=1 1 t
≤ 2NGRXT + 2NC2d2
σ T 2b log(T ) (55)
where we recalled (32). Substituting λ = λ?, the maximizer of g(λ) over λ ∈ Rp+, into the (55), the left-hand side on (55) becomes
E [g(λ?)] = p∑ s=1
E [(∑T
t=1 ∑N i=1[cs(xi(t))]+ )2] 2N ∑T t=1 ηt ≥ p∑ s=1 (∑T t=1 ∑N i=1 E [[cs(xi(t))]+] )2 2N ∑T t=1 ηt
≥
(∑T t=1 ∑N i=1 ∑p s=1 E [[cs(xi(t))]+] )2 2pN ∑T t=1 ηt
(56) where the first inequality follows from Jensen’s inequality. Combining the inequalities in (32), (55), and (56), yields
T∑ t=1 N∑ i=1 p∑ s=1 E [[cs(xi(t))]+] ≤ 4pNG3/2 √ RX√ σ √ T log(T ) + 4pNGCd σ T 1/3 log(T )
where we used b = 13 .
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(xi(t))− ˜̀i,t(x?π) ] ≤ NC2d2 T∑ t=1 βt ε2t − (E [ρ]) 2 2pN ∑T t=1 ηt
this, combined with (45), further leads to
T∑ t=1 N∑ i=1 E [`i,t(xi(t))− `i,t(x?)] ≤ NGRXπT+2NG T∑ t=1 εt+NC 2d2 T∑ t=1 βt ε2t − (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
E [Reg(i•, T )] ≤ NGRXπT + 2NG T∑ t=1 εt +NCĈGd T∑ t=1 βt εt +NC2d2 T∑ t=1 βt ε2t
+ ĈG2E [ρ] βt ηt−1
− (E [ρ]) 2 2pN ∑T t=1 ηt︸ ︷︷ ︸
=h(E[ρ])
≤ NGRXπT+2NG T∑ t=1 εt+NCĈGd T∑ t=1 βt εt +NC2d2 T∑ t=1 βt ε2t + 1 8p NĈ2 T∑ t=1 ηt
(58)
where the last inequality follows from the same reasoning as that of (35)–(37). This, combined with ηt = 2pG2 σt , βt = 1 σt , εt = 1 T b and π = 1 RXT b , leads to
E [Reg(i•, T )] ≤ 3NGT 1−b + 2NCĈGd σ T b log(T ) + 2NC2d2 σ T 2b log(T ) + NĈ2G2 2σ log(T ) (59) hence, the optimal regret bound follows by setting b = 13 . The proof is complete.

Review summaries:
This paper considers distributed online convex optimization with long-term constraints, which extends Yuan & Lamperski (2018)’s work to decentralized case with time-varying directed network. The authors propose DOCO frameworks (full-information and one-point bandit feedback) based on augmented Lagrangian functions. They also provide the corresponding regret bounds for both strongly and non-strongly convex cases. The experiments on synthetic data validate the effectiveness of proposed algorithms.