Distributed Online Optimization with Long-Term Constraints
Authors: Deming Yuan
Alexandre Proutiere
Guodong Shi
Venue:  (2020)

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 ${\cal O}(T^{\max\{c,1-c\} })$ and ${\cal O}(T^{1-c/2})$, respectively, for any $c\in (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 ${\cal O}(\log(T))$ and ${\cal O}(\sqrt{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 ${\cal O}(T^{\max\{c,1-c/3 \} })$ and ${\cal O}(T^{1-c/2})$ for any $c\in (0,1)$. We numerically illustrate the performance of our algorithms for the particular case of distributed online regularized linear regression problems.

Under review as a conference paper at ICLR 2020
DISTRIBUTED ONLINE OPTIMIZATION WITH LONG-TERM CONSTRAINTS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider distributed online convex optimization problems, where the distribut- ed system consists of various computing units connected through time-varying communication graph. each time step, each computing unit selects a con- strained 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 minimize the system-wide loss accumulated over time. We propose decentral- ized algorithm with regret and cumulative constraint violation in ((7maxxee11-8 and O respectively, for any (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 (log((T) and (( (Tg) These re- gret scalings match those obtained by ttate-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problem (for both con- vex and strongly convex loss functions). In the case of bandit feedback, the pro- posed algorithms achieve regret and constraint violation in O(Tmax(c,1-e/3) and O(Tl-e/2) for any c (0. 1). We numerically illustrate the performance our algorithms for the particular case distributed online regularized linear regression problems.
INTRODUCTION
The Online Convex Optimization (OCO) paradigm Hazan (016) has recently become prominent in various areas of machine learning where the environment sequentially generating data is too complex be efficiently modeled. OCO portrays optimization 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, convex function of the decision. The successive loss functions are unknown beforchand and may vary arbitrarily over time. At the end of each step, the loss function may 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 ((VT) (resp. Oloo T)) for convex (resp. strongly convex) loss functions Zinkevich (2003); Hazan et al. (2007); Abernethy et al. (2009).
process, and applies robust and
This paper extends the OCO framework to distributed setting where (different) data is collect- ed and processed at N computing units in a network. More precisely, we consider scenarios where in each time-step, each unit i commits loss equal to (1)).. Units update their decision based on previously observed local loss- es and messages received from neighboring units with the objective of identifying the decision x = arg miny ΣT, MN (x) minimizing the accumulated system-wide loss. Many tradition- al 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 description of the spam filter design problem in centralized setting). In each time-step. each unit (here an email server) receives an email characterized by a vector a,, e Rd (according the "bog-of-words" representation). Unit i applies for this email filter represented
decision (1) and then experiences a local

---

Under review as a conference paper at ICLR 2020
by vector (t) E X' where X' is convex compact subset of R returns label ((,)),((t)) and experiences a loss equal (t)((x(tt)) = xx(()) yr,t)² where Vi.t is the true email label (-1 for spam or I 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 iden- tify and apply as fast as possible the filter minimizing the system-wide loss, i.e., 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 adversary also modifying in online manner spam emails. More generally the distributed OCO framework can be applied to networks of learning a- gents, where each agent wishes to take advantage of what other agents have learnt 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 network of N computing units described by a sequence of directed graphs G. (V, with node set y ... and edge set & at time t. Ge represents the communication constraints at the end of time-step t: each unit is allowed to send its decision at time & to its neighbors in G. Each unit i E V is associated with a sequence of convex loss functions {fr+)(=1 where E,, Rd - R.
Optimization process. each time-step 4, each unit E selects x; (() E Rd. Then, in case of full information feedback, the loss function & is revealed to unit i, whereas in case of bandit feedback, the loss (t))) is revealed only. Unit finally receives vectors, functions of decisions selected by its neighbors in Go, i... (t(t) for j such that (j,i) E &,, and updates its decision for the next time-step.
Decision constraints. The decisions should be selected in X' convex subset of RR character- ized by a family of inequalities: X' {x E Rd (x( I 0, 8 = ,.). Imposing such constrained decisions implies that each unit should be able in each time-step perform projec- tion 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, only impose that the constraints are satisfied in a long run rather than in each time-step, i.c., that En > Ex=10a Cs (()) S O. This relaxation allows units to violate the constraints by pro- jecting 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 se- quential decision selection algorithms that each unit identifies the decision minimizing the accu- mulated 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:
N
Reg(i. T) = Σ (x,((.))) - Σ (x((x))
where x* = arg minxEx ΣLe Ej=r The system-level regret is defined as the worst pos- sible regret at all units: SReg(T) & max;=1.....N Reg(i, Now since we allow units to select decisions outside X, the performance of algorithm is further characterized by the so-called cu- mulative absolute constraint violation defined by: (here [a]+ = max a))
CACV(T)=
Ics (x)(
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 algorithm- achieve system-level regret and cumulative constraint violation in O O(Tmax(1-ce)) and
2

---

Under review as a conference paper at ICLR 2020
O(T)=) respectively and for any E (0. 1) (c expresses the trade-off between regret and cumula- tive constraint violation). Theses bounds match those of centralized online optimization algorithms in Mahdavi et al. (2012):eenatoon Jenatton et al. 2016); Yuan & Lamperski (0018). When 1/2, we get
regret scaling in O(VT), which corresponds 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 cu- mulative connstraint violation in (log((T) and Ol (og(()) 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 system- level regret and cumulative constraint violation in O (dd2Tmmax(1 spectively, for any e E (0, 1). For example, when 4. the proposed algorithm attains a re- gret bound in (dPT8/4). The performance guarantees can be improved to Odd log(T)) and in the case of strongly convex losses.
and (dT))==/3) re-
1.3 RELATED WORK
Early work online convex optimization in centralized setting include Zinkevich (200): Flax- man et al. 2005). Today we know that regret in O(VT) 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 OT e) and (TT-=s/2) (c E (0, 1)) in case of full information feed-
back Yuaan& & Lamperski (2018) uses the cumulative squared constraint violation). Our algorithms achieve the same guarantees in distributed setting.
is worth zooming into the rich literature on centralized online convex optimization with bandit feedback. In the seminal work Flaxman al. (2005), the authors designed an algorithm with one- point bandit feedback and regret in Odd733/ 1). 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 (TP and (d log 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(VT) and (LLT3/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 al. 2005).
Over the last few years, there have been a rising interest for the Distributed OCO framework. Par- ticularly. SShhrrampuur Jadbabaie (0177); Lee et al. (2117) propose distributed algorithms with ((VT) regret, but require an exact projection onto the decision set in each time-step. Zhang et al. (2117) presents distributed online conditional gradient algorithm, replacing the projection steps by much simpler linear optimization steps, but at the expense of worse and sub-optimal regret guarantees, scaling in (114/4. The other approach to avoid projections to allow the algorithm to violate the constraints, and has been studied in Yuan et al. (2018). The problem studied in Yuan let al. (2018) is 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 [i al. (2018;; Yi 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] to denote the Euclidean norm and the ith component of a vector E Rd, respectively. Let x1x [x] be the Euclidean projection of a vector onto the set X. Let IR be the nonnegative orthant in IR:: R = {x E Rp [x|; 2 = 1,..., P). Denote the (i.j)-th element of a matrix A by [A] For convex function f. a subgradient (resp. gradient when f is differentiable) at a point x is denoted by fx(x) (resp. V fx)). Given two positive sequences (ar and (b. 1 we write a = (bb)) if lim sup 01/b /b < co.
3

---

Under review as a conference paper at ICLR 2020
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 f,, is revealed to unit i. More precisely, unit has access to the gradient of the loss function t at any query point. We make the following assumptions, which are standard in the literature e.g., Mahdavi et al. (2012) (0002);Jenae JJentton et al. (2016); Yuan & Lamperski (2018); Nedic & Ozdaglar 2009): Yan et al. (2013) ): Duchi et al. 2012); : Hosseini et al. (2013); Nedic et al. (010).
Assumption X C (x
||x|| S Rx} with Rx > O.
Assumption The functions li, and cs are convex with bounded gradients:
max max max [[)) S Ge. im I...,N N I.....T xEB
max max [V,((x)] S Ge. s=I...p XEB
We let G = max Ge)-
Assumption There exists an integer B 2 1 such that the union graph is strongly connected for all k 2 O.
Assumption 4 Associated with G. there is the weight matrix (t)) which satisfies for all 2 1:
(i) A(t) is doubly stochastic for all t 2 i.e. E)=lA(()]s 1 and Ei=IA((t]] Vi,j E V;
(ii) There exists a scalar C > such that [A(t)]a 2 for all and 2 1, and [A())ss 2 Ç if
(j.i) E & and [A(t)]; 0 for all j otherwise.
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
Assumption
stochastic matrices for a network, see, e.g.. Garin & Schenato (2010): Gharesifard & Cortés 2010
Algorithm DOCO-LTC with full-information feedback
Input: Step sizes { [ regularization parameters { T Initialize: x; 0 IR (1) = 0 E RP, Vi 1, I....,N
I: for / to T do
2:
Unit commits to decision (t), and then after receiving l,c, compute
(t) (t) Be ((,,(xx(()) + E((00))000000000))))
3: Unit communicates y:(1) to its neighbors and updates its decision as
(t + 1) = П3 (p)( where p.(() = E(A(0)S5(())
j=1
4: Unit updates its dual variable: >z(1 + 1) arg maNXERs Lea((xi(1+ (1){)
5: end for
The pseudo-code of our algorithm, DOCO-LTC (LTC stands for Long- Constraints), is pre- sented in Algorithm [ It generalizes the algorithm in Yuan & Lamperski (2018) 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 (016). the algorithm does not need 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 La- grangian functionn associated with unit i E V: for t Z 1.
Lis(x, A) 2 (xx(x) + Σ (x)+ - 7h - ||
(3)
4

---

Under review as a conference paper at ICLR 2020
where x [[ APplT E R is the vector of Lagrangian multipliers with [A] being associated with the sth inequality constraint C2 (x) I 0 and 77, is the regularization parameter. We note that:
(xL,, = (x,, (t)) + Σ (x(tt))))lc((((())))+))
where (t)))+ can be calculated as follows for s I.....p:
(x. { (xi(())))) if (x, >
otherwise.
Moreover, the dual update A.(L in DOCO-LTC be calculated explicitly follows: (t + 1)], (x, + 1))l+
=
(4)
Theorem (Convex loss functions and full-information feedback) Under Assumptions 7 the regret and cumulative constraint violation of DOCO-LTC with parameters d) T and pt =
op for some с E (0, 1). a > 1, and all t 2 1, satisfy: for all T 2
ST)g(T) S ČTmax/1-cee and CACV(T) S CT1-c/2
where 2appNG Rx + 1. N(1 + +0) + 4a(a-1)p 1)p with I = 2.V
NC
(2+1/"(--017)) + +4) and
3N
22
and Č = e-1 (1 2apGRx + d2
1N2
Theorem shows that DOCO-LTC has the same guarantees as those of the centralized algorithms in Mahdavi et al. (201 2); Jenatton et al. (2016); Yuan & Lamperski (0018. The user-defined parameter tunes the trade-off between SHeg and CACV (for e 1/2, we get a regret and constraint violation in (VVT) and (T331)).
Communication cost 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,
establish that the regret bound T_max(e,1-e) where (A( is the second largest singular (1==x(())==Tmxxxx11--))
in Theorem scales O (1-o2(A))=
value the weight matrix A. If we choose the weight matrix as the maximum-degree weights (see, e.g., Yuan et al. (019)). we have the following conclusions: i) Random geometric graph: the regret
bound scales (og
No (c,1xx,1-cc) and at most log + (N)N vectors are transmitted per round;
ii) k-regular expander graph: o2(A) is constant, the regret bounds scales as N+Trmax(c. and 2kN vectors are transmitted per round; and iii) complete graph: (2(A) and N 1) vectors are transmitted per round.
Next we improve DOCO-LTC performance guarantees when the loss functions are strongly convex.
Assumption The loss function l,, is a-strongly convex over B, that is, for any x,y E B,
(x) 2 (x,(x) + (xx (x- 2 x
Theorem (Strongly convex loss functions and full-information feedback) Under Assumptions
the regret and cumulative constraint violation of DOCO-LTC with parameters T}: 2pG and d for all t. 2 1, satisfy: for all 3,
SReg(T) (T) S Esn log(T), and CACV(T) S Can Vloo(T))
where Cap
NG² 20
(4 4C + (2) (C is shown in Theorem T and Coc 1pNG (vRx +
v C
Vo
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 better regret scaling, even in the centralized setting /Abernethy al. (2009).
5

---

Under review as a conference paper at ICLR 2020
3 ONE-POINT BANDIT FEEDBACK
This section is devoted to the case of bandit feedback. where at the end of each time-step, unit can observe the value of the loss function l, only point around x; (t). The pseudo-code of our algorithm adapted to this feedback is presented in Algorithm
Algorithm 2 DOCO-LTC with one-point bandit feedback
Input: Step sizes {Be | regularization parameters {m Y exploration parameters ( and shrinkage parameter π Initialize: (1) 0 IR IR (.) 0 R2, Vi L...,
1: for t = to T do
2: Unit commits
decision x; (t),,, and then observes the loss (xx((x(t)) (t);(t)) where u,(t) is randomly chosen on the unit sphere (|]u;(t)]] 1)
3: Unit builds the following one-point gradient estimator:
d (l,,((x((1)) = (x,)(x)(()+ (tu()))
and computes
vz(() x,(1) Be ((),((x(1)) + P [0000).00((000))
4: Unit updates its decision using y, received from its neighbors
N
(1 + 1) = Ds (P:())), where p;(() = Σ [(A())5)))))
==1
5: Node updates its dual variable >, + 1) arg max (tx
6: end for
The design and convergence analysis of our algorithm here rely on the smoothed version L,, A) of the online augmented Lagrangian function i... (,, A): for t 1,
L,,(x, A) A (x;e) Σ (l)c - T1 ||
(5)
where Ex; E, (x EV]] is the smoothed loss function, and v vector uniformly distributed over the unit sphere. As the case of full information feedback, the dual update Ax(++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, (t) (t) belongs the set B. Indeed, we have:
(t) + (t)l < (+)l + sa|lu, I| S (1 - T7) R) + Rx
where the second inequality follows from the fact that xt) (1 T) and [t:[l]] = 1 and the last inequality holds when &, S n Rxx-
To establish upper bounds on the regret and cumulative constraint violation of our algorithm, we make the following standard assumption on the loss functions (x) (commonly adopted even in centralized online bandit optimization Flaxman et al. (2005)).
Assumption 6
The loss functions ti (x) are uniformly bounded over B:
sup x N...NN T...TT [x), C.
Since algorithms for bandit feedback are inherently randomized, investigate averaged versions of the regret and the cumulative constraint violation: E-SReg(T) = max;=l...... [B[Reg(i, T)) and E-CACV(T) = D'' EN E. (())))

---

Under review as a conference paper at ICLR 2020
Theorem (Convex functions with bandit feedback) Under Assumptions and cumulative constraint violation of DOCO-LTC with parameters
4 and 6 the regret
T T 3t apGeTe'
Et To T6 n
RxT
for some E (0.1), b c/3 and all t 2 1, satisfy: for all T
E-SReg(T) < I c/3,cc and E-CACV(T), S C//11-002
where
8 3NG + NCCd apG + &
apG + 23pNN R2 Jala-IIp (C is shown in Theorem 1 and
NC²
C
N2
C2
2apGRx + G2)
Note that DOCO-LTC achieves a regret scaling as 7 when e 3 which is identical to that of centralized online bandit optimization Flaxman 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.
1.
Theorem (Strongly convex functions with bandit feedback) Under Assumptions 7 gret and cumulative constraint violation of DOCO-LTC with parameters
the re-
2pG²
1
1
ot B1 ot'
El Tb
RxT
for 3. and all 1, satisfy: for all T23
E-SReg(T) S C 2/33 log(T) and E-CACV(T) S C. TTVlollggg (Tg((T)
where C 3NG + N
(4CCGd 402 + (²G²) (Ò is shown in Theorem I and C
20
ADNG Vo
(VGRx* + Cdd
4
NUMERICAL EXPERIMENT
We illustrate the performance of the proposed algorithms using simple experiment. Specifically, we consider distributed online regularized linear regression problem over a network, formulated as follows:
minimize subject to
E Σ (t, Cm -x)= x)m
b,(1)) + ||
00, m = 1,...,d
Cd+m (x) = | U S 0,
m l,.....,
where p 2 0 denotes the regularization parameter. The data (a,(t), b.)) E IRd x R is revealed only unit time f.
Results on Synthetic Data. Every entry of (t(t) is generated uniformly at random within the interval 1, and (t) is generated according to
bx(t) (t) (x) ct))
where [x]; = 1, for all 1 <is [d/2] and 0 otherwise, and the noise ct ~ (0, 1). Throughout the experiments, we implement our algorithms over a time-varying directed network depicted in Fig. I: the network is not connected in every time-step, but the union graph of any two consecutive time instances strongly connected. that is, we have B in Assumption! The weight matrices associated with the networks in Fig. 1 are generated according to the maximum-degre weights (see, e.g., Yuan al. (019)). We set the parameters as follows: N = 6, 4, T. 0.15. U 0.15, and Rxx = dd. The performance of DOCO-LTC is averaged over 10 runs.
2
2
5
5
(a)
(b)
(d)
Figure I: The network switches sequentially in round robin manner between (a), (b), (c), and (d).
7

---

Under review as a conference paper at ICLR 2020
To get (not strongly) convex loss functions, set p 0. We run Algorithm D and Algorithm with c = 1/2 and c = 3/4 and plot the maximum regret maxęv Reg(i. 7), and CACV 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 smaller for c = 1 1/2, while in bandit feedback setting, the regret is smaller for = 3/4. This because c= 1/2 and to a balanced regret in the full-information setting and bandit feedback setting. By balanced, we mean that c= c in m (omxx(1-o0 (1-oc) Theorem | and - c/3 = c [
3/4 correspond
Theorem 3
respectively. From Fig. 2(b) we also observe that for both feedback models, CACV is smaller for larger value of c, i.e., e = 3/4. This is in compliance with the results established in Theorems and
3 Finally, the performance is really degraded when going from full information to bandit feedback.
This was also expected.
600
18
.0.0--.--... .... 0..00..--
121 max righet Miloo 112) mac rag
CACV ful 12)
16
bandBlc
600
mec turdht
CAGV band8 [o
54)
Me-mmu teght
CACV
200
100
2-
200
400
600
800
1000
230
600
D00
1000
Time horizon T
Time horizon
Figure 2: SReg and CACV vs. time for convex costs.
In the case of strongly convex losses, we run Algorithm [ and Algorithm 2 with > 0, namely o == and p 2. We plot the performance of the algorithms as function the time horizon in Fig. 3(a) and Fig. 3(b), respectively. From Fig. 3, we confirm that the cost of bandit feedback rather high. We also observe the regret and the violation constraint are smaller and flatter than those achieved of non-strongly convex loss functions (p = 0), for both feedback models. All these observations comply with the results established in Theorems and
-40
CACY All
120
CACH bandktum a
80
ruc righrt Mil. 2) rix on b.
Mochumm
60
DACV
20
200
400
000
000
1000
100
200
300
400
500
600
700
800
900
1000
Time horbzon
Time hordzon
(a)
(b)
Figure 3: SReg and CACV vs. time for strongly convex costs.
Results on Real Datasets. We demonstrate the efficiency of our proposed algorithms on two real datasets selected from the LIBSVM! 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 1/2. For each dataset, we run Algorithm and Algorithm 2 with p and p 1, respectively. We plot
httpp::/ hetps://www.cr csie. ntu. ntw..edu.ww...
8

---

Under review as a conference paper at ICLR 2020
Table Summary of datasets
dataset # features
# of instances
mg
1385
bodyfat 14
252
the performance of the algorithms as function the time horizon in Fig. (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 Theorems 1-4. Finally, the performance is really degraded when going from strongly convex loss functions to convex loss functions.
mg
O- aggnt
bands
Nexemmm mmpittAC
200
10
Vexres nevet bando DAS bert
80
40
10
10
-100
700
1000
100
300
500
700
500
Time horace
Tine horaon
(a)
(b)
Figure 4: SReg and CACV vs. time for mg dataset.
daleael budtplet
daleael taxtyiit
M
Vatre sigit bunds
000
-0
Nodium EgrerCac
700
200
000
100
-Bh Vacima in right
100
CACK kel
300
110
-0--000--- 0000-0000000-00 -000000---0000 250
Time
(a)
(b)
Figure 5: SReg and CACV vs. time for bodyfat dataset.
dososet mg p
400
detapet bodyltt 1
250
15
150
0-000 wes.rrannnniiieeeegg
3000 eas can sipecbunnc
-0 D-0G DICYIBEE
3000 CACY
6 O
Tim
(b)
Figure 6: Comparison of the proposed algorithms with D-OCG mg and bodyfat datasets.

---

Under review as a conference paper at ICLR 2020
We finally make comparisons with standard distributed online projection- free algorithm (D-OCG in Zhang et al. (2017) using mng and bodyfat real datasets. The detailed results are provided in Fig. 6. From these plots one 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.
CONCLUSIONS
In this paper, consider the distributed online convex optimization problem with long-term straints 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 con- sensus 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 each time-step.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jacob D. Abernethy, Alekh Agarwal. Peter L. Bartlett, and Alexander Rakhlin. A stochastic view of optimal regret through minimax duality. In COLT, 2009. URL de/ab/ http:/oonc/oooo httpb//ooon/ooo/coto//00000
html wwttmlAAbbreeeee. #AbernethyABRCS
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In COLT, pp. 28-40. Citeseer, 2010.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 72-85, 2017. doi: 10.1145/90553993335540..
John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimiza- tion: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592-606, 2012.
Abraham Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385-394, Society for Industrial and Applied Mathematics, 2005.
Federica Garin and Luca Schenato. survey on distributed estimation and control applications using linear consensus algorithms. In Networked control systems, pp. 75-107. Springer, 2010.
Bahman Gharesifard and Jorge Cortés. When does a digraph admit doubly stochastic adjacency matrix? In Proceedings of the 2010 American Control Conference, pp. 2440-2445. IEEE, 2010.
Elad Hazan. Introduction online convex optimization. Found. Trends Optim.,, 2(3-3):157-3555 August 2016. ISSN 2167-3888. doi: 10.1561/2400000013. URL
1561/2400000113
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-199) 2007.
Saghar Hosseini, Airlie Chapman, and Mehran Meshahi. Online distributed optimization via dual averaging. In 52nd IEEE Conference on Decision and Control, pp. 1484-1489. IEEF, 2013.
Rodolphe Jenatton, Jim C Huang, and Cedrie Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 48, pp. 402-411. JMLR. org, 2016.
Masoud Badiei Khuzani and Na Li. Distributed regularized primal-dual method: Convergence anal- ysis and trade-offs. arXiv preprint arXiv: 1009. 1609.0822,, 2016.
Soomin Lee, Angelia Nedić, and Maxim Raginsky. Stochastic dual averaging for decentralized online optimization varyiig communication graphs. IEEE Transactions Automatic Control, 62112))4407-6414 2017.
Xiuxian Li, Xinlei Yi, and Lihua Xie. Distributed online optimization for multi-agent networks with coupled inequality constraints. arXiv preprint arXiv: 055533.....5..... 2018.
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex opti- mization with long term constraints. Journal of Machine Learning Research, 130$-2)2503- 2012.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48, 2009.
Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N Tsitsiklis. Distributed subgradient methods and quantization effects. In 2008 47th IEEE Conference on Decision and Control, pp- 4177-4184, IEEF, 2008.

---

Under review as a conference paper at ICLR 2020
Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-933 2010.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 63(3):714-725, 2017.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic and Data Engineering. 25(1 (1(11):220 11:23333--232 2-934, 2013.
properties. IEEE Transactions on Knowledge
Xinlei Yi, Xiuxian Li, Lihua Xie, and Karl Johansson. Distributed online convex optimization with time-varying coupled inequality constraints. arXiv preprint /93.04790,, 2019.
Deming Yuan, Daniel WC Ho, and Guo-Ping Jiang. An adaptive primal-dual subgradient algorithm for online distributed constrained optimization. IEEE Transactions on Cybernetics, 48(1 48(11):3045 3055, 2018
Deming Yuan, Alexandre Proutiere, and Guodong Shi. Distributed online linear regression. arXiv preprint 1xXiv:1902.04777 2019.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. In Advances in Neural Information Processing Systems, pp. 1140-614, 2018,
Wenpeng Zhang, Peilin Zhao, Wenwu Zhu, Steven CH Hoi, and Tong Zhang. Projection-free dis- tributed online learning in networks. In Proceedings of the 34th International Conference on Machine Boarning-Volumm 70, pp. 4054-4062. JMLR. org, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, pp. 928-935, AAAI Press, 2003. ISBN 189-4. URL http://
dl. acm. org/ ctt.:itiiiiiooooo wfw.ddd 3041955
12

---

Under review as a conference paper at ICLR 2020
APPENDIX
A PROOF OF THEOREM
A.1 KRY LEMMAS
The following two lemmas are crucial to the convergence analysis of Algorithm T establishes the basic convergence results of Algorithm T
The first lemma
Lemma (Basic Convergence) Let Assumptions we have
and hold. For every node i E V and T 2 1,
xt, x+1 - -E [|x + -) 1x11
Reg( 1
()
S
i=
+
NG
B1
23r
1=1
1=1
N
T N
pG2 Br
G (t) xx(1
Σ
Σ
Σ
(x,(x
77-1
m/-
1=1
Proof. To simplify the presentation, we write
v.(() A (xLi,((x(()) A,(1)).
We study the general evolution of ||x; (t + x 1.
()) x+1 [[ (p:(1) - x < (1)
where the inequality is based on the non-expansiveness of the Euclidean projection and x* E X S B. Expanding the right-hand side, we further obtain
(t+(t+1) + 111
(t)x (x)(1) (.) x
(())),,)), (t)2
[x,(1) - V.V1111
[xx(1) 12 83 Σ
12,01-2- 23, Σ (x)()(((()) xx')
-x))
||x;(1) - 11 (V,11)22
N
23,
Σ (x), - Lx,(x", ((00))
(7)
where the second and third inequalities follow from the doubly stochasticity of A(t) and the last inequality from the convexity of (x, A) with respect to x. Combining the preceding inequality with the definition of online augmented Lagrangian function in 3 yields
(x)()())) + [()))
Th T (1)l2
The Σ A((0)]][aaxx))) - (A((O)P)) ]
(x((x*)= +
N [Ix 1x EN [xx + 112
3, N
+
Σ (t)
(8)
23
i=1
13

---

Under review as a conference paper at ICLR 2020
On the other hand, it follows from Assumption 2 that
V.(1)
Ve, (x,,((x((1)) + Σ (((
s (x) + 2p > (((0))11000((((())11111
2G + 2pG2
(x,(11)
2G + 2pG2
Th11
where the last equality follows from the dual update 4 Combining the inequalities ( and 9 and using the fact that [A)( [=,(xx(t)]l (cf. 44). we obtain
M--1
(x)) - (x,((x)] Li=l (t) 111 N
E (t+
11
N
2
1
Br
c. (x)((())
PG2
(10)
71-1
11-
The left-hand side can be further lower bounded by
(x)) = l,, (x,+ (f)) + (x) f2, (xx (f)) 2 (x,=
G((x;()) x. (t)l
(11)
summing the inequalities (T0) over = =,.... T, and using the bound 11 and definition of regret
①1. we arrive at the desired conclusion.
The first two terms in Lemma 7 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 the penalty incurred by the violation of constraints.
Remark
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 (Disagreement) Let Assumptions
hold. For every node i V and T 1, we have
T
N
x (t)
xx0 & NÒG B, + ÒG
Σ ΣΣ
T N
(x,(x((t))
Se
7/-1
t=
where Ò is given in Theorem
Proof. By deriving the general expressions for the average decision X(t +(++1) = N EE (t++1) and x; (I + 1) it follows that
x + (x
8m
- (V,,
M=1
N
t-1
N
[(t m + 1)1k, - 1116----1-- [ (py(m)]
m= 1 j=1
N
+2
[a(p:(t)) - -(((()
(12)
14

---

Under review as a conference paper at ICLR 2020
where (t, m) = Att) A (m). vi 2 2 1 and (t.t) (t). On the other hand, by resorting
to Corollary Nedic et al. 2008 we have that, for all 2 m 1
5
A ()).m) N S
(13)
4N2
Combining the inequalities
12 and (13). we obtain
T
N
T-1 +4)
3N
xx())
x, (t)
12 BB +4
11
V.(t)]
(14)
t=1
t=1
1=1
==1
Then, combining
and 14 with the following inequality,
N
xx (t) xx(1)l =
xx (t) - x(t) + x(1) - x;(1)ll
Σ (1x x(11l + Σ x((1) (1)I
N
S (N
[x(1) - xx(1)Il
we arrive the conclusion. The proof complete.
A.2 PROOF THE THEOREM
We consider an arbitrary unit i E V and establish regret bound for that unit. Combining the results in Lemmas and 2 we have
ii= (1x
12 Σ [|x(1++))
1x
x21 + (1 C)NG Σ
T
Reg(i* (i" ,7) s
B
28
T
N
P
Be
CG Σ
(x)(t
17-1
1
Be mi-1
c. (t))
pG2
(15)
77-1
i=1 a=1
Substituting 1): and Be
apG2Te into the preceding inequality, yields
Reg(i",
2 apG2
Σ (1)
x112 ((1p)ro
T + 1
+ N(1 + Cyri-c
ap
T
N
(c.(x) - (1 (1- T
T N
3F (cx(
(16)
op
2m
We turn our attention to bound the last two terms. To this end, write
T
N
Ica (x,(1++))
(17)
which implies that
ΣΣ>N (x(22
p
1
ΣΣ
P c (x4())
(18)
PNT
pNT
because of the inequality that (a1 + ... + an
S n Σn= a3. Hence,
16
now becomes
FapNG2222 + 1
1
N(1 ČTT - + 1 _cp
11_
Reg(i* (T) < 2
(19)
PNTI-c
ap
ap
Af(e)
15

---

Under review as a conference paper at ICLR 2020
where we have used Assumption i.e, Σi= [x;(1) replace the term f() by the following,
x+1
E ||x1|2 &
NR
We can
NC TT-
max f(p) #20
ap
(20)
4
4(1
4a(a
1)p
PNT
Hence, combining the inequalities
19 and
20
we finally have
Reg(2" ( - =
T +
N(1 + Cyr
+ max (() P20
2
op
1 N(1+0)++
NC
- aapNG R3 +
T
(21)
4a(a - 1)p
Therefore, we complete the first statement of Theorem We are left to bound the CACV. From
10
follows that
N
N 1= (t) x²1 EE
||x((t + 1) 12
(t) 1
23,
N (xx(1111
(
Br
PG
17--1
T +
N
Be
(22)
the right-hand side can be bounded by following similar lines that of the regret analysis, that is,
FapNC R&T 1 NT -(1 -1-
I
T
r.h.s. of 22
Co (x,
(23)
the left-hand side on (2 can be bounded as follows, according to Assumptions and
T
1.s.s. of 22
(x,(t) x -2NGRX..
(24)
Combining (33
and 24 and regrouping terms, have
Σ ΣΣΣN c. (x. (1)) < 2aa
T N
a²p
NG
R2
20 -1
+
2a
NGRyT
(a- 1)p
a a
+ 2aGRx + a2 Rxx
TI-0
a-1
2
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 Lx, A) is o-strongly convex, according to As- sumption 5 This fact, combined with 77) leads to
N
N
(x(++ x
(t)(t)
1|
8
[+)
N Σ
2,
(x,, Ax(t)) - Lx,(x,, (xt))) |xx(()) - x*|]] (25)
16

---

Under review as a conference paper at ICLR 2020
regrouping the terms, we further have
(x (1), (t)) - Li,(X* x:(())
-= [1, x* 11 Σi
||x:(1 + 1)
2/
T
T
[1((1) x+112+
Σ
V.(1))?
2
2
i=1
T
N
N (x:(1)
0
[x:(1) - x=1
+
Σ
121
2
3
31-1
31
t=2
1=1
1
3 Σ
|x, +1)
2
2
t=1
i=1
Substituting 8z
= into the preceding inequality and dropping the negative term, yields
T
8 N
ΣΣ (x, (()) L.,(x*, (()1 S
(26)
1=1
Noting that (t) is the maximizer of (t,e((x A) over RT, i... (t),
(t)
N
(t), A) for all A 1R4, we have the following estimate for all X E R., according 26).
T N
T
N
ΣΣ
(z),()(()))) - L,, A.)) <
Σ
(27)
[=1
Expanding the left-hand side by using the definition of online augmented Lagrangian function in 3). we further have
(x((x(())) + Σ (x))1 " |111
(l((x") + [A00)0))) Th (1(())))))) ]
<
Σ
T'
3
N
|+O1P NG Σ Be + p
T
ΣΣ
T N
(28)
2
[=1
where we recalled ( Applying cancel each other out. This leads
2pG 3r to 28). we find that the last terms on both sides will
T
N
p
T
(x)(((() - (x)) +
le( (e(x;(1)))
[2]s
Σ
qt
2
1=1
Ag(A)
T
< N Σ 3e
(29)
note that 29 holds for all À E Rq. and hence we can replace g(A) by the following,
T
T
max g(A)
(x, (x,((x + 2
Σ
B.
2NGRAT + NG
Σ
3
(30)
XER"
t=1 1=1
t=1
[=1
where the last inequality follows from the same reasoning as that of 24 For the left-hand side on 30 we have
T EN (cx(x)())))²²
[EL EN
N
E Cc (x)(
1=
max g(A) AERd
=
(31)
2NN ΣT=1" 11
2pN Σ
s=l
17

---

Under review as a conference paper at ICLR 2020
Combining the inequalities 30 and
31
with the following estimate,
Σ Σ S1+
E7
T
T /
ddu + log(T)
(32)
1
we further obtain for all T 2 3.
Rx (lg((T) +
16p2N2C*
(x,(x:())++
log (T)
4pNG3/2 /xx
4p.
T Togg(T).
(33)
Next, attention the first statement, i.e., the regret bound. Again We consider
arbitrary unit i E V. Combining the inequalities 30 obtain
and 31 and using the notation (17) we
N
NG
Σ
Bt 2pN Ei= 1
1 (x,( - (,,((x')]
1=1
N
Reg(i T) Σ
| (t) xx(1)l
(34)
Applying Lemma
to the preceding inequality gives
T N
Reg(i", (", ,T) s NG C)
B Σ
ΣΣΣ
le (x,(xx1))]++
Be
2pN E
7
t=1
Am 2m
(35)
substituting the expressions for B, and tp into (3
we have
T
Reg(i" .T) S NG C)
Σ
Be
Cp
1
p²
(36)
2p
2p. Σ
t=1
170
((()
Then, following an argument similar that of 20
and
21 we get
T
1
T
T
( + C)
Σ
3e +
NG + C) Σ
Be
+
N2
Σ
8p
1=1
2pN ΣE T
1=1
1=1
2NG (1
C)
NO2G2
log
20
(37)
The proof is complete.
C PROOF OF THEOREM 3
C.I KEY LEMMA
The proof relies on the properties of the one-point gradient estimator (t,,(xx(t)), which can be viewed distributed version of the one in Flaxman al. (2005). In particular, we have the following lemma that characterizes the properties of the one-point gradient estimator and the relation between &, (x) and its smoothed version l,, (x;
Lemma 3
(i) Let G be the uniform Lipschitz constant of the loss functions (x,(()) over B, then the smoothed loss functions (x) are Lipschitz continuous with the same constant and we have that, for all x E 13,
(x,((x))) exx((3) Ge.
18

---

Under review as a conference paper at ICLR 2020
(ii) The one one-point gradient estimator satisfies
[(),,(x((()) (x)))x
(iii) Let Assumption hold, then the one-point gradient estimator satisfies
Ve,, (x,,(x((0)]]
Cd
Et
C.2 PROOF OF THE THEOREM
Denote
P v.(1) - (x,s(x()))
(38)
then, follows from Lemma iii that
E [.(00] (x,,,x)(()ee))) +
(39)
Following similar lines as that of Lemma] I we immediately have
N x;
N
N
[t
+ (t
(t)
x
V
233
Σ
(x;(() x(x)
2=1
t=1
1=1
(40)
where x = (1- E (1 T) c (1 BB Taking expectation both sides of 40 and using
yields
E (x, (t)) - L,,(x* A.(1))
E
x 121
EE= N E |x;
(t
x
1191
NV E
(41)
23,
Using the definition
5 the left-hand side on becomes
N
E (c((x;(1):))) + (0()((xx(00) Th
2
( + IIA(O)) - (10)1)))))
N E (x)))())) (x)(x)
P E (x)
Σ
(42)
7--1
where the equality follows from lc. (xx ] = O, because x E (1- - T)X c X. On the other hand, it follows from 38) and Lemma lii that
[ B (EL. Σ ((00)))((((()((00010
P
E
2 [ (x, (t)) + GpG
E [+)
(x. (+)]
2 <
+ 22
Σ
(43)
1/-1
19

---

Under review as a conference paper at ICLR 2020
this, combined with equations (41 and 42 gives
E (xx(x)();)))) (x
Bt s NC Em E (t) - -x,133 - -E= E |||x (t + - -x,1 x
E7
2/58
p
(x, (
1
pG2
Be
(44)
Th-1
nz-
the left-hand side on 444 can be further lower bounded by utilizing the relation between the losses la and their smoothed variants Es, (cf. Lemmal ()). given as follows:
(1)(()) (x)(x()))) 2 (t)( (xx(xx)) - -2Get
2 (x) (x((x*)) -GRx-- - -2Ge
(45)
where the last inequality follows from the fact that bi is G-Lipschitz and ||x||| Rx. Summing the inequalities in (44) over t. = 1,..., T and using (45) we find that
T
T E (x))(xx(()) - (x,(xx)) s NGRXT + 2NG
T
B
Σ
E + NC
d2
Es
t=1
Di=1 (1)
x ||
-
E
|||x;
(1
+
1)
x
2.3
N 8
Be
E (x;
pG2
7--1
(46)
On the other hand, we have the following estimate of the disagreement among nodes by resorting to Lemma
2
T N
T-1
N
Σ
E [|xx; (t)
xx)(
3
E
((t
|]
1=1
i=1
T
N
Cd
E (x, (+)]+]
3
+ +G}
E1
n--1
1=1
1=1
a=1
31
N ΣΣΣ
P
3e. E [l. (1)+4]
NCCd
ČG
(47)
Et
9h-1
where the second inequality is based an argument similar to that of Theorem we obtain
43
Combining inequalities
46 and
47 and following
E |eg((" TT) S NGRxXT + 2NG Σ
T
c + NCOGd Be NC
T 62
3
E1
1=1
i=
E ||x (1) 11
i-1
E
X
+
x
2,3
T N P
B.
E [xc,
77t-1
T
N
P
(
3r
ΣV
[x.
PG
(48)
72-1
mp
20

---

into the preceding inequality, and Under review as a conference paper at ICLR 2020
Substituting 7/2 7 Ar apG2fe:
T6 and
1 RxTO
following similar lines that of Theorem 1
yields
NCOd apG
NC
E [Reg(i", T)] S 3NGT
(eeg(i")))
T1+26-c
apGz
1 RT + 4a(a 1)p
NC²
T
(49)
2
follows from some simple algebra that the choice of = 3 yields the optimal regret bound O(Tmax(1-e/3.c))
The bound CACV can be derived by lower bounding the left-hand side on 44 that is,
Σ E (x.1(((00))) - (x
Σ
[lIxx(1) x; -NGRRx
where the first inequality follows from Lemma i and the last one from Assumption combined with (44) and the expressions T}: Te Br apG E and π Rx leads
I This,
(x,((x
a 2aGRx + 20
N
C2
T1-20-20
pG²
N
C2
2aGRx
Ti-e
(50)
pG?
where in the last inequality we used inequality with the following,
5.
The desired result follows by combining the preceding
T
N
1/27
ΣΣΣ E (()))((
PNT
c (x
(0)
T
N
1/2
pNT
E
(x.(12
(x
(51)
because of Jensen's 's inequality. The proof complete.
D PROOF OF THEOREM
We first claim that the strongly convexity of the loss functions bú, implies the strongly convexity of their smoothed variants t,, with the same constant a. This fact leads us the following bound that analogous to (26):
N
ΣΣ
E
(x. - L,,, x1)1))
Σ
Σ t=1
E
|
(52)
1=1
t=1
Following an argument similar to that of Theorem 2 we can replace the left-hand side on the following, due to the fact that (t) is the maximizer of (t) A) over A E RP:
52 by
E [L,())(0)))
Lx,(x x.))))
M
(x(x(())) + (x.. Tht - 11112
(53)
(2.((xt) + Σ [AA0))a(()))))++ Th (10001P)) }
T N
T N
ΣΣ
- - + ([(((A)]
'Σ t=1
EE [1AA
1=
21

---

Under review as a conference paper at ICLR 2020
where g()) is defined in
29 On the other hand, using 43 have
||]
1
(+)
- 20 2pG [t)(
(54)
Et
Combining the equations and T 3.
(52).
53) and (54). and using = 2pG2 Be, we find that for all A E R.
T N
T
3
[[g(A)
-
I0 (x,) (x,)(()(())
2C
< 2NGRRTT + NC T Σ
T
< 2 + dN
T (T)
(55)
where we recalled (32 the left-hand side on (5 becomes
Substituting
Xt, the maximizer of g(>) over E R2, into the
55
[T 1=1 N (x0)0((((00)))+ 21
E
T N
E (x)(+))))
#
P
L1=1
Li=1
E [gg(A)))
Σ
2N 2N Ei=1 a
2N Σ n
N
E.=1 E (xx,(xx
1=
i=
2p.N Σ 17c
(56)
where the first inequality follows from Jensen's inequality. Combining the inequalities in and (56) yields
32
555)
ΣΣΣ
N
E [c.((x
4pNG5/2//Rx
(Tlog(T)
4pNGCd T log
Va
where we used b 1
We now turn our attention to the regret bound. It follows from
(55)
and (56) that
N
T
3
(E
(p)
E
-
-
< 2
2p Ei=
this, combined with
45 further leads to
8
(
[p))
E (x,((()x((t) (x,((x*)) NGR Σ
NC d
2p
Σ
n
(57)
Then, following the similar lines as that of Theorem find that
2 and using the disagreement estimate
47
we
T
T B 2f
T Σ
3
Reg(( (1 (,T) < NGRXTT + +2N
Σe
Et + NCOGd
2
1=1
1=1
1=1
CGGE B.
(p))
1/-1
2pN Σi= 17
=h([[p))
T
T
3
T N
< NGGR&T+22G EL+NCGGd 2 df
Σ
8p
1=1
(58)
22

---

Under review as a conference paper at ICLR 2020
where the last inequality follows from the same reasoning that of (35 37 This, combined with 2pG² ?) at
Br of
Et
f 7t and π ,xgリ. leads to
E Reg(( , ,)] - 3NGT 2NCCGd T (T) +
d T
NC
log(T) +
log(T)
20
(59)
hence, the optimal regret bound follows by setting b 3/- The proof is complete.
23


Reviews:
[{"review_id": "Skek9hvCKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\n[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.]", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJxEdyinFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe problem setting of this paper is interesting and the theoretical contribution is nice, but the empirical studies could be improved:\n\n1. It is prefer to append some experiments on real-world applications.\n\n2. Although the regret bound of DOCO is better, the projection step is expensive. Can you compare the running time of DOCO with projection-free algorithms?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeydF1zqr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe paper considers a distributed variant of online convex optimization problem over multiple players, where, at each trial t, convex loss_l_t.i is revealed to player i and but evaluated by sum of loss functions sum_i=1^n l_t,i. The players can communicate with their neighborhood and share their decisions. Under the problems setting and some assumption on the neighborhood graph structure, the authors prove regret bounds for convex/strongly-convex losses and full-info/bandit settings. Specifically, the paper allows the algorithm to violate domain constraints but the sum of violation has to be sublinear in the number of trials. They also show the violation bounds simultaneously. \n\n\nComments:\nThe key assumption is Assumption 4, that the players share a doubly-stochastic matrix which is used to mix neighbors’ decisions. This assumption allows to mix all players’ decisions in a long run and the derived regret bounds make sense. The theoretical results are non-trivial. \n\nAs a summary, I feel the results are beyond standard previous work and has certain values. Note that I have not evaluated correctness of the results, but the results are likely under Assumption 4. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes  a decentralized algorithm with regret for distributed online convex optimization problems. The reviewers worry about the assumptions and the theoretical settings, they also find that the experimental evaluation  is insufficient.
Decision: Reject