Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems
Authors: Ting-Jui Chang
Sapana Chaudhary
Dileep Kalathil
Shahin Shahrampour
Venue: Accepted by TMLR ()

Abstract: This paper addresses safe distributed online optimization over an unknown set of linear safety constraints. A network of agents aims at jointly minimizing a global, time-varying function, which is only partially observable to each individual agent. Therefore, agents must engage in local communications to generate a safe sequence of actions competitive with the best minimizer sequence in hindsight, and the gap between the two sequences is quantified via dynamic regret. We propose distributed safe online gradient descent (D-Safe-OGD) with an exploration phase, where all agents estimate the constraint parameters collaboratively to build estimated feasible sets, ensuring the action selection safety during the optimization phase. We prove that for convex functions, D-Safe-OGD achieves a dynamic regret bound of $O(T^{2/3} \sqrt{\log T} + T^{1/3}C_T^*)$, where $C_T^*$ denotes the path-length of the best minimizer sequence. We further prove a dynamic regret bound of $O(T^{2/3}{\color{black} \sqrt{\log T}} + T^{2/3}C_T^*)$ for certain non-convex problems, which establishes the first dynamic regret bound for a safe distributed algorithm in the non-convex setting.

Published in Transactions on Machine Learning Research (10/2023)
Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems
Ting-Jui Chang
chang tin @ wwwe@@oooooehaeeeeceee
Department of Mechanical and Industrial Engineering
Northeastern University
Sapana Chaudhary
sapanac @ tamu, edu
Department of Electrical and Computer Engineering Texas A&M University
Dileep Kalathil
dileep.kalathie @ tamu. edu
Department of Electrical and Computer Engineering Texas A&M University
Shahin Shahrampour
.shchhamppur@@norlessseeeedddddd
Department Mechanical and Industrial Engineering Northeastern University
Reviewed on Ottpptew....ttpe...cccc/ee/////e
Abstract
This paper addresses safe distributed online optimization over an unknown set of linear safety con- straints. A network of agents aims at jointly minimizing a global, time-varying function, which only partially observable each individual agent. Therefore, agents must engage in local com- munications to generate safe sequence of actions competitive with the best minimizer sequence in hindsight, and the gap between the performance of two sequences is quantified via dynamic re- gret. We propose distributed safe online gradient descent (D-Safe-OGDD with an exploration phase, where all agents estimate the constraint parameters collaboratively to build estimated feasible sets, ensuring the action selection safety during optimization phase. We prove that for convex func- tions, D-Safe OGD achieves dynamic regret bound of O denotes the path-length of the best minimizer sequence. We further prove dynamic regret bound of OTT2/3 /log T + T2/3C7) for certain non-convex problems, which establishes the first dynamic regret bound for safe distributed algorithm in the non-convex setting.
T1/344), where Gj
1 Introduction
Online learning (or optimization) is sequential decision-making problem modeling repeated game between learner and an adversary (Hazan, 2016). At each round E [T'] (1...., T), the learner chooses action x, in convex set X' C Rd using the information from previous observations and suffers the loss fx(x)), where the function f X' + R is chosen by the adversary. Due to the sequential nature of the problem, a commonly used performance metric is regret, defined as the difference between the cumulative loss incurred by the learner and that a benchmark comparator sequence. When the comparator sequence is fixed, this metric called static regret, defined follows
T
Rege Σ f((x)) min
f(x). XEX
(1)
Static regret is well-studied in the online optimization literature. In particular, it is well-known that online gradient descent (OGD) achieves O(VT) (respectively, O(log T)) static regret bound for convex (respectively, exp-concave

---

Published in Transactions on Machine Learning Research (10/2023)
and strongly convex) problems (Zinkevich, 2003; Hazan et al., 2007), and these bounds are optimal in the sense of matching the lower bound of regret in the respective problems (Hazan, 2016).
For non-convex problems, however, we expect that the standard regret notion used in the convex setting may not be a tractable measure for gauging the algorithm performance. For example, in the context of online non-convex optimization, Hazan et al. (2017) quantified the regret in terms of norm of (projected) gradients, consistent with the stationarity measure in offline optimization. More recently, Ghai al. (2022) showed that under certain geometric and smoothness conditions, OGD applied to non-convex functions is approximation of online mirror descent (OMD) upplied to convex functions under reparameterization. In view of this equivalence, OGD achieves ( static regret that is defined in (1).
A more stringent benchmark for measuring the performance of online optimization algorithms is the dynamic regret
(Besbes et al., 2015; Jadbabaie et al., 2015), defined as
T Regt E Σ [xx));
(2)
where x A (xg is well-known that dynamic regret scales linearly with T in the worst-case scenario, when the function sequence fluctuates drastically over time. Therefore, various works have adopted number of variation measures to characterize the dynamic regret bound. We provide a detailed review of these measures in Section 2 and describe the safe distributed online optimization problem (which is the focus of this work) in the next section.
1.1 Safe Distributed Online Optimization
There are two distinctive components that make "safe distributed online optimization" more challenging than the standard centralized online optimization:
Distributed online optimization has been widely applied to robot formation control (Dixit et al., 2019b), distributed target tracking (Shahrampour & Jadbabaie, 2017), and localization in sensor networks (Ak- bari et al., 2015). In this setting, network of m agents aims at solving the online optimization problem collectively, The main challenge is that the time-varying function sequence is only partially observable to each individual agent. Each agent j E [m]] receives (gradient) information about the "local" function fz,x()), .) but the objective is to control the dynamic regret of each agent with respect to the global function fe(-) = E fa,((), i.c..
(i) Distributed Setting:
T
T fx)) = Σ> (x,,) - Σ f((x)). t=1
T
d Reg J.T
Σ f((x).))
(3)
Therefore, despite availability of only local information, the action sequence of agent is evaluated in the global function and compared the global minimizer sequence. is evident that agents must communicate with each other (subject graph//ntwork constraint) approximate the global function, which is common to distributed problems. The discussion on the network structure and communication protocols is provided in Section 3.3.
(ii) Safety Constraints: The literature on distributed online optimization has mostly focused on problems where the constraint set X' is known, and less attention has been given to problems with unknown feasible sets (see Section 2 for a comprehensive literature review). However, in many real-world applications, this set represents certain safety constraints that are unknown in advance. Examples include voltage regulation constraints in power systems (Dobbe et al., 2020), transmission bandwidth in communication networks due to human safety considerations (Luong et al., 2019) and stabilizing action set in roboties applications (Áström & Murray, 2010). In these scenarios, one needs to perform parameter estimation to learn the safety constraints while ensuring that the regret is small possible.
1.2 Contributions
In this work, we address the problem of distributed online optimization with unknown linear safety constraints. particular, the constraint set
x fx E Rd Ax < b),
2

---

Published in Transactions on Machine Learning Research (10/2023)
is linear, where A is unknown and must be learned by agents to subsequently choose their actions from this set. The superscript in X alludes to safety. Our specific objective is to study dynamic regret (2) for both convex and non-convex problems when the set X is unknown to agents. Our contributions are three-fold:
We propose and analyze safe distributed online gradient descent (D-Safe-OGD) algorithm, which has two phases (exploration and optimization). In the exploration phase, agents individually explore and jointly es- timate the constraint parameters in distributed fashion. Then, each agent constructs a feasible set with its own estimate, which ensures the action selection safety with high probability (Lemma 2). Since the estimates are only local, in the optimization phase, agents apply distributed OGD projected to different feasible sets, which brings forward an additional technical challenge. We tackle this using the geometric property of linear constraints (Fereydounian et al., 2020) as well as the sensitivity analysis of perturbed optimization problems with second order regular constraints (Bonnans al., 1998), which allows us to quantify the distance between projections of point to different sets that "close enough" to each other (Lemma 12).
2)
We analyze D-Safe-OGD in the convex setting. Due to the challenge discussed in the previous item, we cannot directly apply existing results on distributed online optimization with common feasible set. The agents must use the exploration time to estimate their own feasible sets, during which they incur linear regret. Therefore, after striking trade-off between the exploration and optimization phases, we prove (Theorem 3) a dynamic regret bound of O Vlog T + T1/$C7), where
O E x|- t=2
(4)
is the path-length, defined with respect to the global minimizer sequence (Mokhtari et al., 2016; Jadbabaie et al., 2015). If the problem is centralized (single agent) and the comparator sequence is fixed, i.c., x; = x. our result recovers the static regret bound of Chaudhary & Kalathil (2022).
3) We further analyze D-Safe-OGD in the non-conver setting, We draw upon the idea of the algorithmic equiv- alence between OGD and OMD (Ghai et al., 2022) to establish that in certain problem geometries (Assump- tions 6-9), D-Safe-OGD can approximated by a distributed OMD algorithm applied to a reparameterized "convex" problem. We prove that the dynamic regret is upper bounded by O vlog + T2/3C7) in Theorem 5, which is the first dynamic regret bound for a safe distributed algorithm the non-convex setting, If the problem is centralized (single agent) and the comparator sequence is fixed, i.e., x x, result recovers the static regret bound of Ghai et al. (2022) (disregarding log factors).
1.3 Summary of the Technical Analysis
We now elaborate on the technical contribution of this work:
1) Estimation Error
To learn the constraint parameters distributed way, in the early stage of D-Safe-OGD (i.e., Algorithm
1), agents apply random actions to collectively form a least squares (LS) problem. Then, distributed opti- mization algorithm is applied to jointly learn the constraint parameters. Though we apply EXTRA (Shi et al., 2015) in this work, we note that this part can be replaced by other distributed optimization methods suitable for smooth, strongly convex problems. Based on existing results on LS estimators (Theorem 7), matrix con- centration inequalities for random matrices (Theorem 8), and the convergence rate of EXTRA (Theorem 10), we quantify the estimation error bound for each agent in Lemma
2) Gap between Projections on Two Estimated Feasible Sets As mentioned earlier, since the estimated feasible sets are different across agents, in our technical analysis we need to quantify the gap between projections on different estimated sets to derive the final regret bounds. To tackle this, in Lemma 12 we show that if we consider the projection problem for one agent as quadratic programming with second-order cone constraints, the projection problem for any other agent can be cast as a perturbed version of the first problem. Then, we build on the sensitivity analysis of optimization problems (Theorem 13) to show that the difference between the projected points (optimal solutions of the original
3

---

Published in Transactions on Machine Learning Research (10/2023)
and perturbed problems) is of the same order as the difference between agents estimates of the constraint parameters.
3) Regret Bounds for Convex and Non-convex Cases
Building the previous points, extend the analysis of the distributed OGD in Yan al. (2012) to the safe setup (Lemma 14), from which we derive dynamic regret bounds for both convex and non-convex cases, We note that for the non-convex (centralized) case, Ghai et al. (2022) showed that if certain geometric prop- erties are satisfied, OGD on non-convex costs can be well-approximated as OMD on convex costs through reparamcterization (Lemma 15). We establish in Lemma 17 that this approximation also holds for the safe, distributed setup with an extra error term due to the fact that the estimated feasible sets are different across agents.
The proofs of our results are provided the Appendix.
2 Related Literature
1) Centralized Online Optimization: For static regret, as defined in (1), it is well-known that the optimal re- gret bound is OVVT) (respectively, O(log for convex (respectively, exp-coneave and strongly convex) problems (Hazan, 2016). For dynamic regret, various regularity measures have been considered. Let us first define the dy- namic regret with respect general comparator sequence {u, [ and the corresponding regularity measure called path-length follows
T
Reg (u)..... UT)
A
f (x,) - Σ fe(w))
1=1
t=1
(5)
Cr(u UT)
|
U1 1
The regret definition above is widely known as universal dynamic regret. Zinkevich (2003) showed that for the convex functions, OGD attains an upper bound of ((V((1 + CT)) on the universal dynamic regret (as defined in (5)). This universal dynamic regret bound was later improved to ((VT(((() More recently, for the class of comparator sequences with path length Σi ||u, u-1 S C, Baby & Wann (2021) presented, for exp-concave losses, universal dynamic regret bounds of (max is the problem dimension and Ö(-) hides the logarithmic factors when C. 2 1/T and of O log(T)) otherwise. Later Baby & Wang (2022) presented Ómaxx ((max(d2/33)) (d///T1/3 (2/33 universal dynamic regret bound for strongly convex losses. For dynamic regret defined with respect the minimizer sequence (as in (2)). Mokhtari et al. (2016) showed regret bound of O(C)) for strongly convex and smooth functions with OGD. A related notion of higher-order path- length defined as GpTr & Eiz |x; x Il has also been considered by several works. When the minimizer sequence {x; |T= is uniformly bounded, O implies O ( for < Zhang et al. (2017a) proved that with multiple gradient queries per round, the dynamic regret is improved to O(min (C7, 12
Cr)) using expert advice by Zhang et al. (2018a).
17)). where d
(mmin(C,
II) Distributed Online Optimization: Yan et al. (2012) studied distributed OGD for online optimization and proved static regret bound of O(VT) (respectively, Ologg T)) for convex (respectively, strongly-convex functions. Dis- tributed online optimization for time-varying network structures was then considered in (Mateos-Nánez Cortés, 2014; Akbari al., 2015; Hosseini et al., 2016). Shahrampour & Jadbabaie (2018) proposed distributed OMD algorithm with a dynamic regret bound of O (VVT(1 + Ct)). Dixit al. (2019a) considered time-varying network structures and showed that distributed proximal OGD achieves dynamic regret of Olog T + C+) for strongly convex functions. Zhang et al. (2019) developed a method based on gradient tracking and derived regret bound in terms of C and a gradient path-length. More recently, Eshraghi & Liang (2022) showed that dynamic regret for strongly convex and smooth functions can be improved to O(1+ CC+ using both primal and dual information boosted with multiple consensus steps. The non-convex case is also recently studied by Lu & Wang (2021), where the regret is characterized by the first-order optimality condition. On the other hand, for the projection free setup. Zhang et al. (2017b) 7b) presented distributed online conditional gradient algorithm with static regret bound of ( and
4

---

Published in Transactions on Machine Learning Research (10/2023)
communication complexity of OT). The communication complexity was further improved to O(VT) in (Wan et al., 2020).
Nevertheless, the works mentioned in (I) and (II) do not consider neither long-term nor safety constraints, which are discussed next.
Table 1: Related works centralized and distributed constrained online optimization for general functions with regret and con- straint violation (CV) guarantees. Let 9(x) = (g) (x): 9x (x)) be the vector formed by n convex constraints. Let and [a]+ max(0, a). Problem type 'C" stands for centralized, 'D' stands for distributed (or decentralized). 'CNX' stands for convex cost functions, and 'N-CNX' stands for non-convex cost functions. Notes: f The CV bound in (Yu & Neely, 2020) can be further reduced O(1) under Slater's condition assumption.
E (0, 1), orp
CV Type
Problem
Reference
Regret Type
Regret Bound
CV Bound
(xe) E [n]
C, CNX
(Mahdavi al., 2012)
Static
OlvT)
O(T9))
maxie()) & (x.)
C, CNX
(Jenatton et al., 2016)
Static
O[Tmadee--o
O
(x))l. Vi (n)
C, CNX
(Yuan & amperski, 2018)
Static
O
2 (xx]], II
C, CNX
et al., 2021)
Static
0 O
o a/2)
(xx1++ II
CN
(Yi et al., 2021)
Dynamic
O Ol TVI Or) OlvT)
O(vT)
Ei-19 (xx) (xx)) Vie In]
CNX
(Yu & Neely. 2020)
Static
O
Ei 9 (x51)] 1.j e [m]
D. CNX
(Yuan et al., 2017)
Static
O(T4/2 (s/2)
O(T way
Ei E Limi xxd+
D. CNX
(Yuan et al., 2020)
Static
OlvT)
El Li E Is (ssa))l
D. CNX
(Yuan 2021)
Static
Ofrmastot-oh
OCTi-w3)
Em Σim [Lox (x.)ll,)
CNX
eYi al., 2022)
Dynamic
O( + ( Crl)/aa)
Oly Moylo + 1)
Yx ||Ax bl+
C,CNX
(Chaudhary & Kalathil 2022)
Static
O Olylog(T) /1)
L A|x b)+
CNX
This work
Dynamic
0 Togg T +T
Σ 1
||x,,
b)+
D.N-CXX
This work
Dynamic
o (To C2
IIII Constrained Online Optimization: Practical systems come with inherent system imposed constraints the decision variable. Some examples of such constraints are inventory/budget constraints in one-way trading problem (Lin et al., 2019) and time coupling constraints in networked distributed energy systems (Fan et al., 2020). For a known constraint set, projecting the decisions back to the constraint set is a natural way to incorporate constraints in online convex optimization (OCO). Here, projected OGD for general cost functions achieves O(VT) static regret. However, for complex constraints, projection can induce computational burden. An early work by Hazan & Kale (2012) solves the constrained optimization problem by replacing the quadratic convex program with simpler linear program using Trank-Wolfe, For understanding the following references better, let X' = {x E X C Rd g(x) s 0} where s(x)= = (gi (x), (x)) ...,, , In (x)) is the vector formed by n convex constraints, and X is closed convex set. The work by Mahdavi et al. (2012) proposed to use simpler closed form projection in place of true desired projec- tion attaining ((VT) static regret with Σ Ji (xx) S (T3/44 constraint violation Vi E [n]. Thus, their method achieves optimal regret with lesser computation burden at the cost of incurring constraint violations. The follow up work by Jenatton et al. (2016) proposed adaptive step size variant of Mahdavi et al. (2012) with O (7,
static regret and O (Ti-c/2) constraint violation for e E (0, 1). These bounds were further improved in Yu & Neely (2020) with static regret bound of O(VT) and constraint violation bound of O(T Here, the constraint violation is further reduced to O(1) when (x( satisfy Slater's condition. The work by Yuan & Lamperski (2018) consid- ered stricter "cumulative" constraint violations of the form ΣT= [9: (x:)1+ Vi E [r]] and proposed algorithms with O (Immax(e.1-e) static regret and O (TI-c/2) 'cumulative' constraint violation for e E (0, 1). For strongly convex functions, Yuan & Lamperski (2018) proved (log(TT) static regret and the constraint violation of respective form is O( (lVlog(T)T) More recently, the work by Yi et al. (2021) proposed an algorithm with O (7.ma((..--o) regret and ΣT ||ls (x.)]+1 < O (T())))/2 'cumulative" constraint violation. For strongly convex functions. Yi et al. (2021) reduced both static regret and constraint violation bounds to OloggT)). Further, Yi et al. (2021) presented a bound of ( T(( + Cr)) for dynamic regret with an O(VT) 'cumulative' constraint violation. The algorithms in Mahdavi et al. (2012); Jenatton et al. (2016); Yu & Neely (2020); Yuan & Lamperski (2018); Yiet et al. (2021) employ some flavor of online primal-dual algorithms. A series of recent works (Sun et al., 2017: Chen et al., 2017: Neely & Yu, 2017; Yu et al., 2017; Cao Liu, 2018; Liu al., 2022) have also dealt with timevaryiig constraints. Yu et al. (2017) specifically work with 'stochastic' time varying constraints.
5

---

Published in Transactions on Machine Learning Research (10/2023)
More recent works (Yuan al., 2017; 2020; 2021; Yi et al., 2022) have looked at distributed OCO with long temm constraints. The work by Yuan et al. (2017) proposed a consensus based primal-dual sub-gradient algorithm with 0(T1/2+8) regret and O(r1-86/3) constraint violation for 30 E 0.5). Single constraint function was considered in (Yuan et al., 2017), where constraint violation is of the form |E 9 (xx,))+++ 1, [ma]. Yuan al. (2020) proposed algorithms for distributed online linear regression with (VVT) regret and O(Tă/4) constraint violation. Here, constraint violation takes the form E Σj= Ei=1 [a Xg.+ where a, E [nx] is a constraint vector. An- other primal-dual algorithm was presented in Yuan al. (2021) with (I regret and ((T)))/2) constraint violation of the form Σ En= Ei= la: (x,,)] for c E (0,1) 1). In all (Yuan et al., 2017; 2020; 2021) constraint functions are known priori. More recently, Yi et (2022) proposed algorithms for distributed OCO with time- varying constraints, and for stricter 'network' constraint violation metric of the form J.
32 E Σ || (xx,))]]|
The algorithm in eY al., 2022) gives a dynamic regret of +T
with O O(v(au + 1)72-9)
constraint violation for ao > and c E (0, 1). Additionally, constrained distributed OCO with coupled inequality constraints considered in (Yi et al., 2020a;b); with bandit feedback on cost function considered in (Li et al., 2020);
with partial constraint feedback is studied in (Sharma al., 2021). For more references in this problem space, we refer the readers to the survey in (Li et al., 2022).
IV) Safe Online Optimization: Safe online optimization is fairly nascent field with only few works studying per-time safety in optimization problems. Amani al. (2019); Khezeli & Bitar (2020) study the problem of safe linear bandits giving O(log(T)) VT)) regret with no constraint violation, albeit under an assumption that a lower bound on the distance between the optimal action and safe set's boundary is known. Without the knowledge of such lower bound, Amani et al. (2019) show Ollog(T)T2/) regret. Safe convex and non-convex optimization is studied in (Usmanova et al., 2019; Fereydounian al., 2020). Safety in the context of OCO is studied Chaudhary Kalathil (2022) with regret of O(y ( 2
Remark 1. Different from the works listed above, we study the problem of safe distributed online optimization with unknown linear constraints. We consider both convex and non-convex cost functions.
3 Preliminaries
3.1 Notation
m
The set (1,2...., m. for any integer m
Frobenius norm of a matrix
X
v Vtrace(X (X VX), for a matrix X and positive-definit matrix V
x
The operator for the projection
X
A Ki
The entry in the i-th row and j-th column of A
A j,:
The i-th row of A
A R
The j-th column of A
The vector of all ones
e;
The i-th basis vector
(x)
The Jacobian of mapping f(.) x
3.2 Strong Convexity and Bregman Divergence
Definition A function X + R p-strrongyy convex (μ > 0) over the convex set X' if
f(x) 2 f(y) + (x-)) (x x
Vx,y XX
Definition 2. For strongly convex function (6.). the Bregman divergence w.E.t. Φ(-) over X is defined
D) A x(x) Φ(y) Tx X.

---

Published in Transactions on Machine Learning Research (10/2023)
3.3 Network Structure
The underlying network topology is governed by symmetric doubly stochastic matrix P. i.e., [Plj 0, Vi, [m]] and each row (or column) is summed to one. If [P], > O, agents and are considered neighbors, and agent assigns the weight [Ply to agent when they communicate with each other. We assume that the graph structure captured by P is connected, i.e., there is a (potentially multi-hop) path from any agent to another agent j * i. Each agent is considered as a neighbor itself, i.c., [| > for any i E [m]] These constraints on the communication protocol imply a geometric mixing bound for P (Liu, 2008), such that | 1/m S /m3*, for any E [m]] where I the second largest singular value of P.
Remark In all of the algorithms proposed the paper, we will see P as an input. This does not contradict the decentralized nature of the algorithmss, as agent i only requires the knowledge of [P]be > for any J neighborhood. The knowledge of not global, and each agent only has local information about it.
4 Safe Set Estimation
To keep the regret small, we first need to identify the linear safety constrains. It is impossible to learn the safety constraints if the algorithm receives information that can be used to estimate the unknown constraints (Chaudhary & Kalathil, 2022). In our problem setup, we assume that the algorithm receives noisy observations of the form
R Axi, + Wi.
E [m]]
at every time step f, where the nature of noise wa, is described below. Here, E Raad d b E R", and is the number of constraints. Note that all agent updates are synchronous.
4.1 Assumptions
We make the following assumptions common to both the convex and the non-convex problem settings. Vx E X and
Assumption 1. The set X is closed polytope, hence, convex and compact. Also, |||||
maxie[j] ||A|]: LA
with respect to the filtration (Fi,t [ ie.. Vt E Vi E [m], E[wi,]Fees-il = O and we have for any a R
Assumption 2. The constraint noise sequence (Wi,r E [T] is
Elexp(ox w.,))) Ft-1l s exp(o² R2(((x11//2)
Assumption 3. Every agent has knowledge of safe baseline action x" E X such that Ax" b² < b. The agents are aware x" and ba and thus, the safety gap A minie(m)(bb - b;), where by (respectively, by) denotes the i-th element of b (respectively, b*).
The first assumption is typical to online optimization, and the second assumption on the noise is standard. The third assumption stems from the requirement to be absolutely safe at every time step. The assumption warrants the need for a safe starting point which is readily available in most practical problems of interest. Similar assumptions can be found in previous literature on safe linear bandits (Amani et al., 2019; Khezeli & Bitar, 2020), safe convex and non-convex optimization (Usmanova et al., 2019; Fereydounian al., 2020), and safe online convex optimization (Chaudhary & Kalathil, 2022).
4.2 Explore and Estimate
In this section, we present an algorithmic subroutine, Algorithm 1, for agents to obtain sufficiently good local estimates of X before beginning to perform OGD. For the first To time steps, each agent safely explores around the baseline action x Each exploratory action is a w-weighted combination the baseline action and an i.i.d random vector Ç..- Here, for the agent E [m] at time step & E [To]. 7 E [0, 1), and G,, is zero mean i.i.d random vector with ||G., S L and Cov(Cr.) I²I. Performing exploration in this manner ensures per time step safety requirement as noted in Lemma 1. The proof of lemma immediate from the assumptions.

---

Published in Transactions on Machine Learning Research (10/2023)
Lemma 1. (Lemma I in Chaudhary & Kalathil (2022)) Let Assumptions 1-3 hold. With 7 each Xi (1 7)xx + * Vi E [m]. & E [To].
A" LLa' Axi, b for
Once the data collection phase is finished, each agent i E [m] constructs local function 4(A) of the form
(A)
To
Ax
& 1|
A m |
Then, for time steps E [To 1, + Ti), Alg. EXTRA (Shi et al., 2015) used solve the global Least Squares (LS) estimation problem E (AA in distributed fashion with a proper choice a.
Lemma 2. Suppose Assumptions 1-2 hold. Let Algorithm
with To 22( .و
L3 log( ()) for data collection and
Ti (log T,), where p is positive constant. Denote the final output of the algorithm A, for agent E [m]] Then, with probability at least (1 - 26), we have vk E [n]] and ji E [m]
R dlog
11mTh12/A
+ VLLA
[[A:],; [A] S Tp
6/n
22
(6)
|| Jk. - [Asle.ll S
Tp
where [As) and [A] are the k-th rows of A and A, respectively.
It is worth noting that the safety gap A affects the estimation error according to Lemma 2. As we mentioned earlier, A' the exploratory action X,, (1 -))x* + YGia, where the coefficient y LLA Intuitively, if A is larger, we can put more weight the exploration through Çi,t, which is beneficial the estimation accuracy. We from Equation (6) that when is larger, the estimation error bound is tighter.
Let us also discuss the computational complexity of Algorithm 1. The time cost of the data-collection phase is OmdTo), assuming that it takes ((d) time to compute each action. For the estimation phase, to perform sin- gle update, each agent spends (mmd) time for the calculation of the weighted average and O(Tond) time for the gradient computation. Accordingly, the total time cost of Algorithm O (mad + Tind)).
Let now define the estimated safe set for each agent [m]] Let the parameter estimate for agent E [m] at the end of Ty + Ti time step be denoted by A, For each row & E [n]] of A, a ball centered at [Ai]e, with a radius B, can defined follows
C. (a E Rdd
[A.]. $ B,),
Ry log
L4 L2/A 8/n
+VÄLA
where B, A T +
The true parameter [A]R,: lies inside the set Ci with high proba-
Topo bility. Now, using (7) the safe estimated set for agent E [m] can be constructed as follows:
a < bk. Vāg E C. Vk [n]]. 8 - fx Rd
(8)
The safe estimated set above will be used by each agent for the projection step in subsequent algorithms.
5 Dynamic Regret Analysis for the Convex Setting
During the first Tp + Ti time steps in Algorithm I agents do not expend any effort to minimize the regret. This is due to the fact that without the knowledge of the feasible set, they cannot perform any projection. In this section, we propose D-Safe-OGD, which allows agents to carry out safe distributed online optimization, and we analyze D-Safe-OGD in the convex setting.
D-Safe- D.Saee-GDDii is summarized in Algorithm 2, where the exploration phase, all agents collaboratively estimate the constraint parameters based on Algorithm and then each agent constructs the feasible set based on its own estimate.
8

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 1 Distributed Constraint Parameter Estimation
1: Require: number of agents m, doubly stochastic matrix P Rmxx, P & LtP, hyper-parameters a, y and X,
2-
data-collection duration To, constraint-estimation duration Ti, a strictly feasible point x (safe baseline action).
Explore around baseline action:
for / 1,2,.... To do
4: for i
1......... do
5: Select action x = 7)- + TSi
6: Receive noisy observation & = Ax,, + Wi
7: end for
8:
end for
Form local functions using collected data:
To Σ Ax &cell
(AA)
||
m
10: Use EXTRA (Shi et al., 2015) to solve global LS problem Σm14(() 4(A) distributed fashion:
11: Randomly generate A E Raxd for all E [m].
12: Vi E [m], Ao+t m A (A!"), where the gradient is computed based on the following
expression:
To VI(A)= Σ
2x
|A 28,
A.
m
13: for f = .......Ty + Ti do
14: for i = 1, 1,2....,
......,,, m7 do
15:
A 1+ = j=1 2[P] A
A 1+1
EE= [P
A a(V4(A;+)))
-V((()))))))))))))
16: end for
17:
end for
In the optimization phase, the network applies distributed OGD, where all agents first perform gradient descent with their local gradients, and then they communicate their iterates with neighbors based on the network topology imposed by P. We note that the projection operator of each agent is defined w.r.t. the local estimated feasible (line 8 of Algorithm 2), thereby making the feasible sets close enough but slightly different from each other. Therefore, previous regret bounds for distributed online optimization over common feasible set (c.g.. (Yan et al., 2012: Hosseini et al., 2016; Shahrampour & Jadbabaie, 2018 8; Eshraghi & Liang, 2022)) are not immediately applicable. We tackle this challenge by exploiting the geometric property of linear constraints (Fereydounian et al., 2020) as well as the sensitivity analysis of perturbed optimization problems with second order regular constraints (Bonnans et al., 1998), and we present an upper bound on the dynamic regret in terms of the path-length regularity measure.
We adhere the following standard assumption in the context of OCO:
Assumption The cost functions f(. are convex Vi E [m]] and Vt E [T], and they have a bounded gradient, i.e..
(x)]] s G for any X
Theorem Suppose Assumptions 1-4 hold and T Ω ( (f log( By running Algorithm 2 with 7 S
A' I 1133) To = (TT233) and T Oloog T), we have with probability at least (1 (1-25)
Xi,t X Vi E [m], [T), and
B T2/3 + T1/3C* Vi [m].
Reg. O T2/3 (og(TT/)) +
(1 (1- -
Theorem 3 establishes dynamic regret bound for --fee-OGD that least 2/T 2/o T), and for a large enough path-length the bound becomes OTT1/3 Cf We also the impact of network topology through B, the second

---

Remark In the proof of Theorem 3, the regret bound is shown be O + Tolog VTo improved to Published in Transactions on Machine Learning Research (10/2023)
Algorithm 2 Distributed Safe OGD with linear constraints
Require: number of agents m, doubly stochastic matrix P Rmxx. hyper-parameters o, 7, 7; 0, X, time horizon T, a strictly feasible point x".
2: Specify To and Ti based on given hyper-paraman parameters and run Algorithm I to learn agents estimates (Ailie(m) in a distributed fashion.
3: For all i E [m]] construct the safe set X from the estimate A,
4: Distributed online gradient descent over different feasible sets:
Let T. A (To Ti- + 1) and initialize all agents at the same point X,T. Xy, chosen randomly. for .,...., do
for i 1........ do
8:
Vi II [ (V.
9:
end for
10: For all [m].
11:
X = -00 P Ji
5=1
12: end for
largest singular value of P. When the network connectivity is stronger (i.e., B is smaller), the regret bound is tighter. For the dependence on other parameters, we refer readers to the exact upper bound expression (Equation (38)).
Corollary 4. Suppose that the comparator sequence is fixed over time, i.e., x = Vt E [T]. Then, the individual regret bound is (TT233 Vlog which recovers the static regret bound of the centralized case in (Chaudhary & Kalathil, 2022) terms of order.
Remark 3. Note that when A is known, there is estimation error, and the trade-off in terms of n and To longer exists. In other words, the agents do not incur the initial regret To + O(T2/3), caused by estimation. Then, by choosing 1) = 0 (7), the resulting bound is O(vT(1 + CT), which recovers the result of Shahrampour & Jadbabaie (2018) in terms of order.
+ BTT
(1-B)
If agents have the knowledge of Cū by setting 1/ OTT-1/2 ((T-1//2/OT)) /CT), the regret bound in Theorem (TT2/3 VogT + + /TCT), which enjoys better dependence on Cy. Though this choice of step size is non-adaptive, we conjecture that using techniques such as expert advice (Zhang et al. (2018a)) or adaptive step sizes (Jadbabuie et al. (2015)), one can improve the regret bound, which an interesting future direction.
6 Dynamic Regret Analysis for the Non-convex Setting
In this section, we study the non-convex setting for safe distributed online optimization. Even for offline optimization in the non-convex setting, the standard metric for the convergence analysis often stationarity, i.e., characterizing the decay rate of the gradient norm. In online optimization, we can also expect that standard regret notions, used in the convex setting, may not be tractable for understanding the algorithm performance. However, recent work by Ghai et al. (2022), the authors studied an algorithmic equivalence property between OGD and OMD for certain problem geometries, in the sense that OGD applied to non-convex problems can be approximated by OMD applied to convex functions under reparameterization, using which sub-linear static regret bound is guaranteed.
More specifically, for a centralized problem, suppose that there is a bijective non-linear mapping 9, such that u, = q(x;), and consider the OGD and OMD updates
Centralized OGD:
X argminxcc
([((()) xe) + 1 - x.l
(9)
10

---

Published in Transactions on Machine Learning Research (10/2023)
Centralized OMD:
1111 argmin NE ((n) (u- (1:--))) + 1 (u)
(10)
where X²' the image of X under the mapping q. Ghai et al. (2022) quantified the deviation || - ((x++1]] as (178/2) under the following technical assumptions (together with boundedness of gradient norms):
Assumption 5. There exists a bijective mapping q : : + X' such that [V] (x)) where u = q(x).
Assumption 6. Let > be a constant. Assume that q(-) is W- -Lipschitz, o(-) is 1-strongly convex and smooth with its first and third derivatives upper bounded by W. The first and second derivatives of (-) are also bounded by W. For all X", (u( is W -Lisschhizz over X".
Examples that satisfy these assumptions provided in Section 3.1 of Ghai al. (2022). For example, if ø is the negative entropy (respectively, log barrier), we can use quadratic (respectively, exponential) reparameterization for g. Amid & Warmuth (2020) showed that in the continuous-time setup when Assumption 5 holds, the mirror descent regularization induced by & can be transformed back to the Euclidean regularization by q-', which implies the equiv- alence between OMD for convex functions and OGD for non-convex functions. This due to the fact that higher than second order factors vanish in continuous time, and this assures that the mirror flow and the reparameterized gradient flow coincide. Though in the discrete-time case, the exact equivalence does not hold, Ghai et al. (2022) showed that OGD for non-convex functions can still be approximated as OMD for convex functions, and the corresponding static regret bound is O under the assumption that ft (x) (g())), where f((-) is convex. However, we need more technical assumptions to handle the discrete-time setup as higher order terms are relevant and must be judiciously
analyzed. Ghai et al. (2022) characterized the sufficient condition to achieve Assumption 5, which entails an implicit OMD reparameterization for a non-convex OGD. We state these (two assumptions) by tailoring them to our problem setting:
Assumption 7. (u) for all u E x and supu,eEx" Dø(u, 2) S D'.
Assumption 8. Properties of the mapping q()):
There exists mapping g(-) such that fi,(x)= = fralg(x)), where feal.) is corvex.
q(-) is CD diffeommorphism. and (x)x) is diagonal.
For any X C X2 which is compact and convex, X' 2 q(X) is convex and compact.
We again refer the reader to Section 3.1 of Ghai al. (2022) for examples related to Assumption
In this work, we extend this equivalence to "distributed" variants of OGD and OMD under the additional complexity that the constraint set is unknown, and it can only be approximated via Algorithm 1. Our focus is on analyzing the effect of (i) the constraint estimation as well as (ii) the distributed setup in non-convex online learning, and we also generalize the analysis of Ghai et al. (2022) to the dynamic regret. For the technical analysis of the non-convex setting, we also use the following assumption.
Assumption 9. Let u and {y.]m be vectors in Rd, The Bregman divergence satisfies the separate convexity in the following sense
(u Σ oay.) s Σ as Dol.
where E Am is on the m m-dimensional simplex.
This assumption is satisfied by commonly used Bregman divergences, e.g., Euclidean distance and KL divergence. We refer interested readers to (Bauschke & Borwein, 2001; Shahrampour & Jadbabaie, 2018) for more information.
In the following theorem, we prove that with high probability, the dynamic regret bound of D-Safe-OGD is O(12/3 D(12/3//ooTT +
Theorem 5. Suppose Assumptions 1-3 and 6-9 hold and T St (1=1f log(()) By running Algorithm 2 with A' < LLA' 2/3-) To = 233233) and Ti = =Olog T), we have with probability at least (1 1--00 26)
X E X2, Vi [m], (T). and
11

---

Published in Transactions on Machine Learning Research (10/2023)
Reg (1og//////g(///0/ - CT), vi E [m].
The complete proof is provided in the Appendix, and the dependence on other problem parameters can be found in Equation (54). The idea is to show that distributed OMD and distributed OGD iterates are close enough to each other if the reference points of both updates are identical, i.e., u x(xx,)) for all i E [m]] Then, distributed OGD can be viewed as a perturbed version of distributed OMD, and under the assumption of convexity of fr.: the regret bound can be established. Also, as mentioned in the convex case (Remark 4), we conjecture that the dependence of regret bound to the path-length can be improved to VCr-
We further have the following corollary that shows our result is a valid generalization of Ghai et al. (2022) to the distributed, dynamic setting.
Corollary 6. Suppose that the comparator sequence is static over time, i.e., x x Vt E [7]. Then, the individual regret bound becomes O(T2/3 VTog ), which recovers the static regret bound of Ghai et al. (2022) up to log factors
It is worth noting that though in the convex case, the estimation of unknown constraints exacerbates the regret bound (due to O time spent on exploration), for the non-convex case, the resulting bound still matches the static regret of Ghai et al. (2022), where there is no estimation error. In other words, there no trade-off in this case as the static regret (without estimation error) is ((72/3) (Ghai al., 2022) (disregarding log factors).
7 Discussion on Regret Bounds in Terms of Other Regularity Measures
In this work, we focused on dynamic regret bounds characterized by Cj, the path length of the minimizer se- quence. It is worth noting that existing works also presented regret bounds in terms of other regularity measures, which capture the properties of the function sequence from different perspectives. Such measures include (1) the A E supxEx [xx(x) fx-1(x) (Besbes et al., 2015), (2) the predictive path-length Cl UT) 2 u (r,-)) |)| (Hall & Willett, 2013), where Vr is a given dynamics, and (3) the gradient variation Dy A E t= by the learner. Besbes et al. (2015) proposed restarting OGD algorithm and showed that when the learner has ac- cess to only noisy gradients, the expected dynamic regret is bounded by O(T2233 + 1)3 for convex functions and Ollog TT((1 Vir) for strongly convex functions. The above mentioned regularity measures are not directly comparable to each other. In this regard, Jadbabaie et al. (2015) provided a dynamic regret bound in terms of Ci,, Dr and Vr for the adaptive optimistic OMD algorithm. Also, Chang & Shahrampour (2021) revisited OGD with multiple gradient queries per iteration (in the unconstrained setup) and established the regret bound of Ommi (Vr, Cjt, C2.r)) for strongly convex and smooth functions. Dynamic regret has also been studied for functions with a parameterizable structure (Ravier et al., 2019) as well as composite convex functions (Ajalloeian et al., 2020).
function variation VT
T
[xxx)) m: (Rakhlin & Sridharan, 2013), where m, is predictable sequence computed
Besides the dynamic regret, a relevant regret measure called adaptive regret (Hazan & Seshadhri, 2009) for a contigu- ous time interval T.ub is defined as follows
Reg (Tant) A
max
Σ f((x;) - min
mx(x)
(11)
[1.++Tbb Tuob Jc|
XEX
Zhang et al. (2018b) analyzed the connection between adaptive regret and dynamic regret and provided adaptive algorithms with provably small dynamic regret for convex, exponentially concave, and strongly convex functions.
In contrast to aforementioned works, where a projection operator needed, Wan et al. (2021) proposed projection free online method replacing the projection step with multiple linear optimization steps. Without assuming smooth- ness, they proved dynamic regret bounds of O(mxx(T2/3v] and strongly convex functions, respectively. On the other hand, Wan et al. (2023) considered the case of smooth convex functions and improved the dynamic regret bound from O(VT(1 + Vi + /Dr)) O((T(1++v)))
vT)) and O(max( /TV, T, log for convex
Conclusion
In this work, we considered safe distributed online optimization with an unknown set of linear constraints. The goal of the network is to ensure that the action sequence selected by each agent, which only has partial information
12

---

Published in Transactions on Machine Learning Research (10/2023)
about the global function, is competitive to the centralized minimizers in hindsight without violating the safety con- straints. To address this problem, we proposed D-Safe-OGD,, where starting from safe region, it allows all agents to perform exploration to estimate the unknown constraints in distributed fashion. Then, distributed OGD is ap- plied over the feasible sets formed by agents estimates. For convex functions, we proved a dynamic regret bound of O Vlog CT-) which recovers the static regret bound of Chaudhary Kalathil (2022) for the central- ized case (single agent). Then, we showed that for the non-convex setting, the dynamic regret upper bounded by O Vlog T2/3 C;), which recovers the static regret bound of Ghai et al. (2022) for the centralized case (sin- gle agent) up to log factors. Possible future directions include improving the regret using adaptive techniques and/or deriving comprehensive regret bounds in terms of other variation measures, such as Vr.
Acknowledgements
The authors gratefully acknowledge the support of National Science Foundation (NSF). 'T-. Chang and S. Shahram- pour were supported by NSF ECCS-2136206. The work S. Chaudhary and D. Kalathil was supported part by grants NSF
and NSF 1955699..96.
References
Yasin Abbasi Yadkoi,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Amirhossein Ajallocian, Andrea Simonetto, and Emiliano Dall' Anese. Inexact online time-varying convex optimization. In American Control Conference (ACC), pp. 2850-28551 2020.
method for
Mohammad Akbari, Bahman Gharesifard, and Tamás Linder. Distributed online convex optimization on time-varying directed graphs. IEEE Trunsactions Control of Network Systems, 4(3):417-422, 2015.
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
Ehsan Amid and Manfred KK Warmuth. Reparameterizing mirror descent gradient descent. Advances in Neural Information Processing Systems, 33:8430-8439, 2020.
Karl Johan Äström and Richard M Murray, Feedback systems. Princeton university press, 2010.
Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. Conference on Learn- ing Theory, pp. 359-409. PMLR, 2021.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Statistics, pp. 1805-1845, PMLR, 2022.
Heinz H Bauschke and Jonathan M Borwein. Joint and separate convexity of the bregman distance. Computational Mathematics, volume 8, pp. 23-36. Elsevier, 2001.
In Studies in
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 63(5): 1227-1244, 2015.
Frédéric Bonnans, Roberto Cominetti, and Alexander Shapiro. Sensitivity analysis optimization problems under second order regular constraints. Mathematics of Operations Research, 23(4):8068831, 1998.
Xuanyu Cao and KJ Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on automatic control, 64(7):2665-2680, 2018.
Ting-Jui Chang and Shahin Shahrampour, On online optimization: Dynamic regret analysis of strongly convex and smooth problems. Proceedings of the AAAI Conference on Artificial Intelligence, (5(8):696666977) 2021.
Sapana Chaudhary and Dileep Kalathil Safe online convex optimization with unknown linear safety constraints, Proceedings of the AAAI Conference Artificial Intelligence (AAAI), 3666)61766) 2022.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Tianyi Chen, Qing Ling, and Georgios B Giannakis. An online convex optimization approach to proactive network resource allocation. IEEF Transactions on Signal Processing, 65(24):6350-63344 2017.
Rishabh Dixit, Amrit Singh Bedi, Ketan Rajawat, and Alec Koppel. Distributed online learning over time-varying graphs via proximal gradient descent. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 2745- 2751. IEEE, 2019a.
Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, and Ketan Rajawat. Online learning with inexact proximal online gradient descent algorithms. IEEE Transactions on Signal Processing, 6338-1133- 2019b.
Roel Dobbe, Patricia Hidalgo-Gonzalez, Stavros Karagiannopoulos, Rodrigo Henriquez-Auba, Gabriela Hug, Dun- can Callaway, and Claire Tomlin. Learning to control in power systems: Design and analysis guidelines for concrete safety problems. Electric Power Systems Research, 189:106615, 2020.
Nima Eshraghi and Ben Liang. Improving dynamic regret in distributed online mirror descent using primal and dual information. Learning for Dynamics and Control Conference, pp. 637-649, PMLR, 2022.
Shuai Fan, Guangyu He, Xinyang Zhou, and Mingjian Cui. Online optimization for networked distributed energy resources with time-coupling constraints. IEEE Transactions on Smart Grid, 12(1):251-26 2020.
Mohammad Fereydounian, Zebang Shen, Aryan Mokhtari, Amin Karbasi, and Hamed Hassani. Safe learning under uncertain objectives and constraints. arXiv preprint vrXiv2206.133266 2020.
Udaya Ghai, Zhou Lu, and Elad Hazan. Non-convex online learning via algorithmic equivalence. Advances in Neural Information Processing Systems (NeurIPS), 35:22161-22172. 2022.
Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex programming. In International Conference Machine Learning, pp. 579-587. PMLR 2013.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
Elad Hazan and Satyen Kale. Projection-free online learning. In International Coference on International Conference Machine Learning (ICML), pp. 1843-1850, 2012.
Flad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments. Conference on Machine Learning (ICML), pp. 393-400, 2009.
International
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-19)) 2007.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. Conference on Machine Learning (ICML), pp. 1433-1441. PMLR, 2017.
International
Saghar Hosseini, Airlie Chapman, and Mehran Mesbahi. Online distributed convex optimization dynamic networks. IEEE Transactions on Automatic Control, 61(11):355-3350, 2016.
Ali Jadbahaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. Artificial Intelligence and Statistics, pp. 398-406, 2015.
Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pp. 402-411. PMLR, 2016.
Kia Khezeli and Eilyan Bitar. Safe linear stochastic bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06): 2020.
Jueyou Li, Chuanye Gu, Zhiyou Wu, and Tingwen Huang. Online learning algorithm for distributed convex optimiza- tion with varying coupled constraints and bandit feedback. IEEE transactions on cybernetics, 2020.
Xiuxian Li, Lihua Xie, and Na Li. A survey of decentralized online learning. arXiv preprint arXiv:2205. 022200000033... 2022.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Qiulin Lin, Hanling Yi, John Pang. Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. Compet- itive online optimization under inventory constraints. Proceedings of the ACM Measurement and Analysis of Computing Systems, 3(1):1-28, 2019.
Jun S Liu. Monte Carlo strategies in scientific computing. Springer Science & Business Media, 2008.
Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultancously achieving sublinear regret and con- straint violations for online convex optimization with time-varying constraints. ACM SIGMETRICS Performance Evaluation Review, 49(3):4-5, 2022.
Kaihong Lu and Long Wang. Online distributed optimization with nonconvex objective functions: Sublinearity of first-order optimality condition-based regret. IEFE Transactions on Automatic Control, 67(6):322--3355, 2021.
Nguyen Cong Luong, Dinh Thai Hoang, Shimin Gong, Dusit Niyato, Ping Wang, Ying-Chang Liang, and Dong Kim. Applications deep reinforcement learning in communications and networking: A survey. IEEE Communi- cations Surveys & Tutorials, 21(4):3133 117-3344333 2019.
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Reseurch, 13(1):2503-2528, 2012.
David Mateos-Nánez and Jorge Cortés. Distributed online convex optimization over jointly connected digraphs. IEEE Trunsactions on Network Science and Engineering, 1(1):23-37, 2014.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic envi-
ronments: Improved regret rates for strongly convex problems. In JEEE 55th Conference on Decision and Control (CDC), pp. 7195-7201, 2016.
Michael Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv: 2017.
arXiv preprint
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pp. 993-1019. PMLR, 2013.
Robert Ravier, Robert Calderbank, and Vahid Tarokh. Prediction in online convex optimization for parametrizable objective functions. In IEEE 58th Conference on Decision and Control (CDC), pp. 2455-2460, 2019.
Shahin Shahrampour and Ali Jadbabaie. An online optimization approach for multi-agent tracking of dynamic param- eters in the presence of adversarial noise. American Control Conference (ACC), pp. 3306-3311, 2017.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror de- scent. IEEE Transactions Automatic Control, 63(3):114-725, 2018.
Pranay Sharma, Prashant Khanduri, Lixin Shen, Donald J Bucci, and Pramod K Varshney. On distributed online
convex optimization with sublinear dynamic regret and In 202/ 55th Asilomar Conference on Signals, Systems, and Computers, pp. 1013-1017. IEEE, 2021.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, (52))99449666 2015.
Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In Inter- national Conference Machine Learning, pp. 3280-3288. PMLR, 2017.
Joel Tropp et al. An introduction to matrix concentration inequalitics. Foundations and Trends@ in Machine Learning, 8(1-2):1-230 2015.
Inuur Usmanova, Andreas Krause, and Maryam Kamgarpour. Safe convex learning under uncertain constraints. In
The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2106-2116 2114, PMLR, 2019.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Projection freee free distributed online convex optimization with of o(VT)
communication complexity. In International Conference Machine Learning, pp. 9818-9822 PMLR, 2020.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Yuanyu Wan, Bo Xue, and Lijun Zhang. Projection-free online learning in dynamic environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10067-10075, 2021.
Yuanyu Wan, Lijun Zhang, and Mingli Song. Improved dynamic regret for online frank-wolfe. arXiv preprint wrXiv:2302.05620, 2023.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic preeeriiin properties. IEEE Transactions on Knowledge and Data Engineering, 25(1 1):2483- 2493, 2012.
Xinlei Yi, Xiuxian Li, Lihua Xie, and Karl H Johansson. Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Signal Processing, 68:731-746, 2020a.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Henrik Johansson. Distributed bandit online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Automatic Control, (110)))4220-46333 2020b.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint vio- lation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pp. 12008. PMLR, 2021.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and H Karl. Regret and cumulative constraint violation analysis for distributed online constrained convex optimization. IEEE Transactions on Automatic Control, 2022.
Hao Yu and Michael J Neely. A Low Complexity Algorithm with O( Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints. Journal of Machine Learning Research, 21(1): 2020.
Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
Deming Yuan, Daniel WC Ho, and Guo-Ping Jiang. An adaptive primal-dual subgradient algorithm for online dis- tributed constrained optimization. IEEE transactions on cybernetics, 48(11))3045-306 2017.
Deming Yuan, Alexandre Proutiere, and Guodong Shi. Distributed online linear regressions. IEEE Transactions Information Theory, 67(1):616 639, 2020.
Deming Yuan, Alexandre Proutiere, and Guodong Shi. Distributed online optimization with long-term constraints. IEEE Transactions on Automatic Control, 1789)1009911144 2021. 2021.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advances in Neural Information Processing Systems, pp. 732-741, 2017a
Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou. Adaptive online learning in dynamic enviromments. In Advances in neural information processing systems, pp. 1323-1333, 2018a.
Lijun Zhang, Tianbao Yang. Zhi-Hua Zhou, et al. Dynamic regret of strongly adaptive methods. In International conference machine learning, pp. 3882-5891. PMLR, 2018b.
Wenpeng Zhang, Peilin Zhao, Wenwu Zhu, Steven CH Hoi, and Tong Zhang. Projection-free distributed online learning in networks. In International Conference Machine Learning, pp. 4054-4062. PMLR, 2017b.
Yan Zhang, Robert J Ravier, Michael M Zavlanos, and Vahid Tarokh. A distributed online convex optimization algorithm with improved dynamic regret. In 2019 IEEE 58th Conference Decision and Control (CDC), pp. 2449-248 2454. IEEE, 2019.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning, pp. 928-936, 2003.
16

---

Published in Transactions on Machine Learning Research (10/2023)
A Appendix
In this section, we provide the proofs of our theoretical results. In Section A.1, we state the results we use in our analysis. Section A.2 includes the proof of estimation error bound in Lemma 2. In Sections A.3 and A.4, we provide the proofs for Theorem (convex case) and Theorem 5 (non-convex case), respectively.
A.1 Preliminaries:
Theorem 7. (Theorem 2 in Abbasi- Yadkori et al. (2011)). Let (FitEo be filtration and (we)e1 be real-valued stochastic process. Here, is F--maaurrbble and we is conditionally R-sub Gaussian for some R Z O. Let {x be an R -vauue stochastic process such that x is Fe-1-maaurralle. Let Vr - Et= xix =I À > 0. Define y/: = a "xx we, then ât V It=1 yt is the fz-regularized least squares estimate of a. Assume ||a|| S La and |x $ I,, Vt. Then, for any E (0,1) with probability (1 - 8), the true parameter a lies in the following set:
a Rd; a åT lIv, $ RV dlog 1+ TTT/1
VALAA
for all T 2 1.
Theorem (Theorem 5.1.1 Tropp et al. (2015)). Consider a finite sequence {Xt} of independent, random and positive semi-definite matrices of dimension d. Assume that Xmax (X.) L, WI. Define Y E. Xt and denote Amia (E( μ. Then, we have
P(Amin Y) S qp) S dexp (- 2)2 11
2L for any c E (0,
Now, let us define the shrunk version of the polytope as follows
X - ex Rd [A],, Tm S bx, Ak [n]}, for some Tha 0.
(12)
Lemma 9 (Lemma Fereydounian et al. (2020)), Consider a positive constant Tin such that X is non-emply. Then, for any x E X
Vdri
(x)
(13)
C(A,b)"
where C(A,b) b) a positive constant that depends only on the matrix and the vector b. Theorem 10. (Theorem 3.7 in Shi et al. (2015)) Let us consider the following notation for EXTRA algorithm
the Xi.k The iterate of agent i at time ls of the EXTRA algorithum,
11,b
k
X
x Xm,k
Σ f((x) )
x" = argmin x
x
X'
T
f(X) = Σ f(xx).
A convex function h(-) is restricted strongly convex w.r.t. a point y if there exists μ O such that
(V)(x) Vhly), x x- -y) 2 n||/x v
Vx.
17

---

Published in Transactions on Machine Learning Research (10/2023)
Suppose that the gradient of w.E.t X is Lipschitz continuous with constant L and f(X) + X
X"
P-P
is restricted strongly convex W.E.t. X with a constant Hg- Then, with a proper step size a < 2pgAmin (P)
there exists
bi
> such that
|
X
converges to O at the R-linear rate of of + +))
A.2 Safe Distributed Set Estimation
Proof of Lemma Let VIa - Ei=1 Ei x and V Vz. + AI. Let À be the solution of argmin Σx=1 (A). Let [ k.: and [A] be the k-th rows of A and A, respectively. Based on Theorem 7, we have with probability at least (1 -),
mToLi//
[A]a - [AJailly s Sdlloo
+ VALA, Ak E [n].
(14)
8/n
Knowing that Vi [m]] Vi E [To]. X (1 (1-7)x* + 7hise we have A s L and E[x;,x
(1 xx-xx" + o ž I Therefore, we have
722
Ama (E(Viol)) Amin
[|xxxx 2Tor2og
(15)
Based on (15) and Theorem 8, we have
(Amii((Vs S Edmiia (1.l)) (L S dexp (- - =)² of
(16)
21
By setting and To 2 mmnoo (og($)) from (16), we have
81.3
1
1 m 2 6).
P(Amiu (V) m 2 P(Amin (Vr.) 2 2
(17)
Combining equations (14) and (17), we have with probability at least (1 26),
B Rydloy dlog
[1mTob+1/>
VÀLA
8/n
k. [A],.
Vk [n].
(18)
Let agent i's local estimate of A at time t E [To 1,70 Til returned by the EXTRA algorithm (Shi et al., 2015) be denoted by A.. Next, upper bound the distance between À argmin Σm 4, (A) and A based on Theorem 10 follows. Based the definition of (A), considering the vectorized version of A, the Hessian matrix has the following expression
X
To Σ 2
X
V4,(A)=
+ 2 m
I x 2(T
m I,
x
where the inequality is due to the boundedness the baseline action and the noise vector. From above, we know EE,, ((A)) is Lipschitz smooth with the constant 2 A) and strongly convex with the constant 2 by (0, 1) such that
selecting step size (A/m) (PP suggested by Theorem 10, there exists (ToL. 21²
||) AJeall & (t-To) Vi [m], k [n),1 [To + 1,... To + Ti]
(19)
18

---

Published in Transactions on Machine Learning Research (10/2023)
where 0 is constant. Based (18), (19) and our choice of Ti (T1 (-log r) llg((/T))), for k E [n].
E [To + 1...., To + Ti] and i, E [m], we have
R d log ( (1mTTLI2/
+ VALA
Ja, [A]a.]] S [|]]]. [A]a. + ||| [A]
1 Tp +
6/n1
(20)
12m0
and
2
||A])) - [AS]a.ll S ||A - [A]a: + ||A]| 12/]a.11 S Tp
(21)
Lemma 11. Define
R doog
1+mToL2/A
+ VALA
1 T
6/n
B,
+
For each agent i, construct Xe based on (8) with Ci,k following from (7). By running Algorithm I with user-specified L² log( )) and Ti (log T there exists mutual shrunk polytope (see the definition in (12)) subset
To 5 Mmpgao
X (Tmm L)r for R7 Vi [m] with probability least (1 -25).
Proof of Lemma 11. Consider a mutual shrunk polytope subset X (Tim 2B, L). Based on Lemma 2, with probability at least 26, we have for any x E X
[A, B, /,|
[A,, + ([A.),, [A]R,)) + BB
< Ak,, + |||A,lk. - [A]k,]]] |atl|||||| + B, B,
(22)
< A K + 2B,1|x|| S [[A,,, + +BB,L s dy, Ak E [m] and Vi E [m],
which implies that X Lq, Vi.
Lemma 12. For each agent i, construct &e based on (8) with Ci,k following from (7). By running Algorithm I with 1,a
user-specified To 22 my
50(miog log( and Ti O(log TP), we have for any point x,
| p. (x) - 2g (x)l s 0 ( Vi,j E [m].
(23)
Before we discuss the proof of Lemma 12, for the sake of completeness, we provide the formal statement of Theorem 3.1 in Bonnans et al. (1998), used in the derivation of Lemma 12.
We first define the notations used in (Bonnans al., 1998). Note that the notations here only locally de- fined for the statement of Theorem 3.1 in Bonnans al. (1998). The work of Bonnans al. (1998) focuses the sensitivity analysis of parametric optimization problems of the form
(Pw)
min f fx, u) subject to G(x, u) E IC, xEX
where X' finite dimensional space, U/ is a Banach space, I. is a closed subset Banach space y and f and G are twice continuously differentiable mappings from X 1 to and V, respectively. The optimization problem is considered to be unperturbed when u
Given the feasible set, optimal value and set of optimal solutions of (P.) are denoted as follows
(uu) fx X: G(x, e K}),
m(u) e inf u): x (u))), S(u) argmin (f u) x e ((u)).
19

---

Published in Transactions on Machine Learning Research (10/2023)
A point X' is called an e-optimal solution of (Pu) if @(u) and f(x, u) & e(u)) +c.
We also define the following notations to present the theorem statement.
Dual space of y
dist(y, 2) Tk(())
The minimum distance from point y to set A:: inf - : :xE
The tangent cone to the set IC at the point E K: {h E y: -is
Nxcly)
The normal cone to the set K. at the point K: [y" E )" (y 50, Tk(y))
Df(x, u)
Derivative of f
(x)
Partial derivative of f w.r.t X
Dxx u)
Second order derivative of w.r.t.
Df(x', u')(x, u)
The linear function based on the derivative at (x', u')
L(x, u.
The Lagrangian f(x, u) + (A, G u)). A y
(x)
{A [G,, u)) Dx
u) 0}
{Xi + 22
U(xi + x2), X E X1, X2 E 26
())
The interior of the set A'
To study the first order differentiaailittiy of the optimal value function vu)), for given direction d E U and the optimal solution of the unperturbed problem X E S(0), Bonnans et al. (1998) consider the linearization of the family of problems (Pta) and its dual as follows
(PLa) min f(xo, (), d) subject to DG 0),, d) E (x(((xx,,)) h
(DLa): max XEAa(Xa)
DuL(xo, X, O...
Theorem 13. (Theorem 3.1 in Bonnans el al. (1998)) Let x(1) be an O(())-optimal trajectory of (Psa) converging to a point Xg E @(0) as + 0. Assume v(PLa) to be finite. Suppose that the following conditions hold:
1. Xo satisfies the directional constraint qualification, which is implied if
O E (G 0) DxG(xx, 0) - K.}.
2. v(Id) S v(0) + te(PLa) + O(P), t 1 0 (Equation 3.4 in (Bonnans et al., 1998)).
The strong second order sufficient condition (Equation 3. I in (Bonnans et al., 1998)) holds, which implied
D2x X, O,,) h) > 0, Yh E C(x))(())
sup XeS(DLa)
where C(xo) denotes the critical cone.
Then x(t) is Lipschitz stable Xo, i.e., for 2 0. [xx(t) xol O(t).
Proof. (Proof of Lemma 12) The key idea is to leverage Theorem 13, which quantifies the sensitivity of the optimal solution "perturbed" optimization problem. More specifically, is shown that the distance between the original optimal solution and the optimal solution of the perturbed problem upper-bounded by the magnitude of the perturbation.
First, we show that Vi E [m]. the projection problem II (x) can be formulated as a quadratic programming with second-order cone constraints. The definition of XG has the following equivalent expression
8 Rd a. S bR, Vä, C...s Ak [n]] E
a T - bu. Vk [n]] a.ECE
(24)
= EXERR 2d [A.]a.x + B,||x|| S dR. Vk E [n]),
20

---

Published in Transactions on Machine Learning Research (10/2023)
where each second-order cone inequality: [A,],,x B-|| inequality (LMI):
bys can be equivalently written as linear matrix
A. x 1,|1x// $ by e (x, (x) - (bx - (.)),
B,
= 0.
(25)
B,
(bn
For simplicity, we define the following matrix
G (x,
G)(
g(x, A,)
G'(
Considering the intersection of all LMIs, we have
X a (xE : A,) = 0}.
(26)
Based on (26), for point Rd, we have II IT (x) xt where & is derived by solving the following optimization problem
X3
Gx
c
argming 8 &TE, s.I.
2 0.
(27)
(.A)).
Based on Lemma 2, we have ||A - |A,l = O Vi,j E [m] and Ak [n]. Therefore, [A,]k, can be expressed as [A,], + the where |/ ( With this expression, the projection xx) & can be formulated perturbed version of the optimization (27), where the perturbation is parameterized in terms of db |1), va] as follows:
G &.
G(
6 = argming 5. s.t.
= 0.
(28)
G" + E, + +b)
To show that |1 (x) (x) - = 0(1+]) O we apply Theorem 13, where three conditions need be satisfied: directional constraint qualification (DCQ), Equation 3.4 in Bonnans al. (1998) and strong second-order sufficient conditions (we refer readers to Bonnans al. (1998) for detailed definitions).
DCQ:
sufficient condition for DCQ is constraint qualification (CQ) (see the definition in Bonnans al. (1998)), which is satisfied in our problem formulation if the first-order approximation of G(x + E, A; + v) w.r.t. the variable can be positive-defintt. Noting that G(x + E, A, + v) is an affine function &, the first-order approximation is exactly the original function. Now suppose that [m]] X has a strictly feasible point (this is implied by the existence of the mutual shrunk polytope), which means there exists & such that (xx + ç, A, v/) is positive-definit, and then CQ is satisfied.
Equation 3.4 in Bonnans et al. (1998):
In Bonnans al. (1998), the authors provided the sufficient conditions for Equation 3.4: DCQ and second- order regularity (Definition 2.2 Bonnans et (1998)). DCQ, mentioned previously, holds in our case, and second-order regularity holds for semi-definite optimization, which is the case for our problem setup.
21

---

Published in Transactions on Machine Learning Research (10/2023)
Second-order sufficient conditions:
The strong second-order sufficient condition (Equation 3.1 in Bonnans et al. (1998)) has an alternative form (Equation 3.3 in Bonnans et al. (1998)), which is satisfied in our problem setup since the Hessian of the Lagrangian is 2I, which is positive-definite
Since all the conditions above are met, the lemma is proved by applying Theorem 13.
A.3 Convex Part
Lemma 14. Let Algorithm 2 run with step size rj O and define X, m E x and yı -E= Li=1 Under Assumptions I to 3 and the fact that gradients are bounded, i.e., V ( S G for any x X², we have that
vi E [m]
[x+ xI,1 / (0( + 2n/ vm3
1-
Proof. For the presentation simplicity, we define the following matrices
X, 2 X1,t X,, Y, 2 Yme,l,, G, - (V,,.(x1.))...... (xmm)() and R2 & .mm,l
where Ft, - Vt.t (Xi, V V(.((()))) Then, the update can be expressed as X, = Y.-IP- = (X,-1 - G + P.
Expanding the update recursively, we have
1-P, P +
L-,
X, = =x, X(--P)) - Σ Iml
Σ R R
(29)
Since P is doubly stochastic, we have p²1 = 1 for all k 2 1. Based on the geometric mixing bound of P and the above equation we get
X - - --
|x, -x--x
T-T R
< <||x7,
Xr. p((
kall +
G
- 1
(P]
m
m
1=1
L-
T
Σ
(mB'
+
(0(
GG
Vm
1=1
mm3
<(0( + 21)
1-B² B
where |x,, - Xx,, 1 = 0 by the identical initialization of all agents with the same action at T., and the other
inequality based on Lemma 12 as follows
Fa.
yi,
(xi, T/V (x.(x.)))
P Pll:l[ x [y..-1)]
Σ P - (V(().((x))))
s P) + +.G.
22

---

Published in Transactions on Machine Learning Research (10/2023)
Proof of Theorem 3. First, decompose the individual regret of agent into three terms:
T Σ [=1
T
T
ΣΣ -((x))))))))))))
E
(x,( +
Σ
-
- (x,
+
Σ
f(() - f((x)),
T
Term 11
Term III
(30)
where x is the projection of x on A which mutual subset of (A/) Jeeml with Tin 2B, based on Equation (22) in Lemma 11. We now proceed bound each term.
The upper bound of Term I: A Note that by choosing 7 S I.T.A' we have vi E [m]] and E [ + Til
[A] ((1 7)x" + 75,,)) S (1 b3 A S 11--7/ (1-7)bb + (bs - -b%) < bbs
(31)
which implies the safeness of the action.
Based on the Lipschitz property of the function sequence, we have
T
Σ
<
Σ G||x3 -x1l= $ + Ti).
(32)
The upper bound of Term II: Based on the update rule, vi e [m] and E [Te..... I'Il we have
f1,())))) - -r. SV ( (x,((()))))
(xx,ee (x
2"' |
||x,,0- x11 2 2 x x - (
< 122 12l
x
11
||xa,e - x;112
2 ||yse - xx11
(33)
11
- Σ buy j xi|| - 1 Ily - =x11²]
||
+ +
E Pb x;11
- x;11²]
2""
where the second inequality is due to the projection property that | - x Xi,t - - -x, -x:l1 third inequality due to the convexity the square function.
and and the
Based on Equation (33) and Lemma 14, we have
(x,(xx))) - (x)) fr,((x,)) fx,((x,,) + St,((x),)) (x,)
s0l|x xx,1ll + fx.e( (x.)
(34)
22G(0 1
2n) 1-3 + 1 (xxx,,)
mmg
1
yi. x;
2n
2n
23

---

Published in Transactions on Machine Learning Research (10/2023)
Summing Equation (34) over i, get
Σ ( - -f.((())))
<2mG(0( TT/) + 2n/ vm3
(x
+
1
Σ
1yy.e-1 -x;111
x;l1²
2n1 Σ
Yost - xil1
3
2
2n 3
=2mG(O( TP + 2m)
mm3
!
Σ
1
Σ
+ + - -1,c-1) x;)
3
2
2n
(35)
Summing Equation (35) over / E [Ts....; .T, we have
T
Σ
-
Te
1 Σ Vi.T. -1 -1|²+ 1 Vir
[ex,(x))))
(36)
2n
t=
1
x(+1) ye. 2TmG 1
vmB
Σ
Σ
x
+ 2m)
Tp
1-
The upper bound of Term III:
Based on Lemma 9, we have for any X E 2 and its projection to X denoted by X;, that
T ΣΣ (fu(t)) (x,)) <
T
S mTG G 2v
Σ Σ G
x
xxi
(37)
C)A,b)
t=
[=T.
Substituting Equations (32), (36) and (37) into Equation (30), we get
ΣΣ (ho()e)))) fi,((xi)
22GLm + +Ti)+ + mmTG2
Σ
yi.T. TT.T.111 11|++ -+=- 5
( Vi -
+ 2m
(38)
77
Σ
T-1
Σ
x
x Vi, + 2T
T
- + 2n))
mm3 1- +
MTG
2vdBB
To
C(A.b)*
t=
which is OT, + + " of n and To into above.
+ 1 7
To
ByT (1-9)
and the final regret bound is derived by substituting the choices
Vio
A.4 Non-convex Part
Lemma 15 (Lemma 4 in Ghai et al. (2022)). Suppose Assumptions 5, 6, 7 hold and u, q(xx). then [la(x(+1)
4++1 = O(W 3/2 pp2p)) based on the following update rule:
Se((u)) u Tu+ 1 1)
u = argmmn X
Do, uz)
1 || Xx (12)
X = argmmnnxxx
Vi(((;))
x
2n
24

---

Published in Transactions on Machine Learning Research (10/2023)
Theorem 16 (Theorem 7 in Ghai et al. (2022)). Civen convex and compact domain X' X", and not necessarily convex loss fe(-) satisfying Assumption 7. When Assumption 8 is met, there exists an OMD object with convex loss f((-), convex domain and strongly convex regularization & satisfying Assumption 5. Lemma 17. Suppose Assumptions 5-7 hold and uie q(xx,,), ; Vi E [m]; then
[19(x4,4+1) -aap)))-_(,,4 u',4tal
1 0 T2p + 1//)))
based on the following update rules:
Zi,t = argmin u. Viiluua) u+ 1 Pola,mad
/ 1,1+1 -[Pliie Li
(39)
Vira(xit) x 2 1|| xi.e| }.
Vi, = argmin xEX;
2n
Xi++1 = Ep
Proof. We first upper bound [l((x;,++1 u//etall as follows
[(((x)+11) u/, S
- Ellls + Σ Plag(ysa) - - Pl
(40)
To bound the second term, we consider the Taylor expansion of q(y) w.r.. a point y in the convex hull of {yrahe
|| Σ P beg(ys))) al < Play Plass,)) 0.0l $|| Σ PI Pla (9()) + J, 3) + Ollxs, -s113)
(1(3)+ Pl - 8)) ΣIP) 1 - -313)11
00
PI
Plallyy, - 8|13) + +0 Σ 8113)
<O(D²),
(41)
where D denotes the diameter of the convex hull of (yrt) and is upper bounded as follows
D e max
yzell
(b.f)
max
|T x (xx,t - 1) V.
[x (x,, - 1) (
(i.j)
max
[| x (xi,t fi.
-11 (xi, - 17 f(,((),)))
(1.3)
+ x (x,, V/ (x..,) - u2 (x 17 (xxx,)))))
(42)
max (1.3)
||| و (xx,t v/ (x),,))))) 11 (xi,e - 1/ V fx,((x)))))
+ +x - ((((e(())))) - (xx,, - " (
<0 - + 2((01 + 2n)
vm3
1
1
+ +Gn = 0
Tp + +n)
25

---

Published in Transactions on Machine Learning Research (10/2023)
The first inequality follows from the non-expansive property of projection, where [x) - II - ||--||
for any x,y and closed convex set X, and the last inequality is based on Lemma 12, Lemma 14 and the Lipschitz continuity of the function sequence.
Substituting Equations (41) and (42) into Equation (40) and based on Lemma 15, we have
[((x),011) ufle ا|| Σ Pl Plizz EP Ploalyys))) + ++1 (PI bol(ys))) al 2 P Plaiaaa)l
(43)
2/ ///)) ) + 0 T2p
+ +n22) = 0 T20
+ 11 1))12),
when is small enough.
Proof of Theorem 5. As for the proof of Theorem 3, we decompose the individual regret into three terms:
fx(()))
Σ Σ fu(xx,)
- (x,()) +
-
- (x, +
Σ f(())) - f(()),
T=
Term 1
Term
Term
(44)
where X is the projection of x; on Nú which a mutual subset of {&, hie(m) with Tin 25, based on Equation (22).
The upper bound of Term I:
Similar the proof of convex part, during the estimation phase, y is less than agent's 's action, and based on the Lipschitz property we have
LLs ensure the safeness of each
A'
T
T.-1
Σ Σ fu,(x)) = Σ Σ - - fr(()())))
[=1
T.
GeWiix3. xx11 22 + T2).
(45)
1=1
The upper bound of Term II:
Define X,¹' A {x(x)]x E Xf), (same for X and X²). Then, for any q(x;) U, E Ag based Equation (39),
26

---

Published in Transactions on Machine Learning Research (10/2023)
have
77 (f((()))))))) - = 1) (f.,lu.t)) - (ū;))
VVfuu(u,.) (us,) - ūi})
(Vo(ure) - Vo(z()) - -V (..,.()))))) (ūū -z,,)
(Vo(z))) vo(u.)) (ū; - -z,)) 1 V ((.e( T (ui.e - -Zip))
$ (Vo(z..) Vo(u,))) (ū) 2,,1) + V ((, (ui.e %i,e)
Do u.,:) D Do(ū, D (z u. + (u:,)) (uust - zi,e)
< Do up:s) Do(ūi 21,1) Do(Zi, up
2| | -1,el 2.,112+
1
1/²
2
2
$ <Dolin Up.e) Do(ūi,,211 + 11² V (i.e()))))
2
7² [i.
= =Do(ūf ug!s) - Do(ūū uk,,) + Do(ū; uk,,) - D 2i,1) +
2
n
s Dol(i, u.,)) Do(ūū, + Σ Pl 2,,-1) Dz(ū 2.,)
V
fu.
(46)
where the second inequality is based on the optimality of Z the fourth inequality is due to the strong convexity of (b()) and the fifth inequality is based on Assumption
Based on Theorem 16, Lemma 17, and the Lipschitz assumption on Da,, have
[ u..) - D v(,,)l S W u'aal s O(((( 1 T2p + 1/2
(47)
And based on Lemma 14, we get
max JJEmm]
| u,,
max [((x),)) - g(x),,)) = O(Wn). JJ(m
(48)
With Equations (46), (47) and (48), we derive
fu,((,,)) fū,( -
- fr,( + fu.((u..)) - (ū;)
< &Flluu, -u,'l + +O(W( 1
+ 12))
1/120p
+ 1 Σ Do (1,,2)11)) _
1
Do (i,
24,e) + す/ V (t,,,)))
17
(49)
1
< O(rWw)) + O(W
+ 12))
T/T20
+ 1 Σi Do Po
1
+ 2/2 V (u.
11
Based on the definition of Bregman divergence, we have the following relationship
Dolūi, 2i,,,) Dus zi,z)
(Vo(zi)) Vo(zi,-1)) (ū) -i,r) + Do (Zi,t, Zi,z-1)
(50)
=VV((z))) vo((z,--1) ūt + (Ø(2).) (ol(z.)) 24,1) (0(2),-1) Vob(z,0-1) 21.111)- T2a,.-1))
27

---

Published in Transactions on Machine Learning Research (10/2023)
Summing Equation (49) over i, based on Equation (50) get
Σ F(e(()
- (())
<0(mGrWn) mmm 1
? + +1) 12) + Σ //2 fi
1/T2p
(51)
Σ (Volzz.)) vo(zu,-1)) T iž + (o(z,,) Vo(z,,)) T 21,1) - (0(z),)1)) Vo(z).1-1) 2,0-1)] (
Then, by summing Equation (51) over (Ta...., Ty, we have
Σ ΣΣ
EEh (1l(u)))) Seo(1;)
T
<OmmIGpWn) +
1
+ 11/1/1)
+
?
(u.)))
1/T2p
2
T=
(52)
T-1
Σ
Σ ( - ui+1) " Vel(z,)) + Σ Vol((.))
T up Σ
T-
1 Σ [(b(Zc)) Vd(Z,))) (oox:))T2.p) (1.T) - (0(Z)T,-1) -Vo(2.,T-1) 21,T, -1=,,,,-))) 2i,TT-1)]
The upper bound of Term III: Based on Lemma 9, we have for any x3 E x and its projection x xÇ
T
& Σ EGEW - xill mTGFW W 2VdLB,
- Fl.(((()))) Σ Σ -
(53)
C(A,b)
T=
T=
Substituting Equations (45), (52) and (53) into Equation (44), the final regret bound is as
ΣΣ (fil(x),)) - fx,((x))
T
<0(mTGrWn) + (mTW( 2/ + +z)l12)
+ Σ
Σ T
1
2
T-1
Σ T--1
Σ ij 1 T Vo(z).)) Σ Volz.T) ui Σ Vo(ZI,.-11) ui.-1
Vo Lm Ti)
2VdLB,
Σ [(o(Z.T) Vo(z.T) ZT.)) (o(z,,,,-1) Vo(Z,,,--1) 2,,,,,,) +mGGFW C(A,b)
Too To
1
T
=0 +T + +
+ + Σ
|u - 1)
VT
" T=
(54)
where the final regret bound is proved by applying the specified and To. By choosing p as a large enough number. a7 is dominated by 1/22
28


Reviews:
[{"review_id": "F6GqHiF7Lp", "reviewer": "Reviewer_J4zV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The constraint information is unknown, which is different from most of the existing literature on online distributed optimization under inequality constraints.\n\nThe regret bounds are in dynamic setting and match those of the centralized counterpart.\n\nSome details regarding the computational complexity, learning rate, and non-convexity need to further clarified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies safe distributed online optimization over an unknown set of linear constraints. Dynamic regrets for convex and non-convex loss functions have been established. Overall the topic of the paper is interesting and the paper is well written.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is suggested to provide the explicit expression of $\\nabla l_{i}(\\widehat{A}_{i}^{t}) $ in Algorithm 1 and perform a detailed analysis of the computational complexity of Algorithm 1.\n2. Please specify the choice of the step size $\\alpha$ in Lemma 2.\n3. The learning rate $\\eta$ in Algorithm 2 requires the information of $T$, which is global, is it possible to adopt adaptive learning rate that depends only on $t$?\n4. The authors should specify what type of non-convexity is considered in Section 6. In addition, why is the definition of the dynamic regret identical to that of the convex setting?\n5. Does the safe baseline action in Assumption 3 affect the accuracy of the parameter estimation? I think more lines should be added to discuss about this assumption.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v8k4M528Eo", "reviewer": "Reviewer_YPwj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work provides the first algorithm for distributed safe optimization that guarantees that the constraints are not violated at any round with high probability. However, from the technical point of view, it is not clear which are the main contributions of the paper since most of the results are heavily based on previous work. \n\nRegarding Algorithm 1. The use of a convex combination between a known safe action and a zero-mean random vector is not novel, and the second part of the parameter estimation algorithm uses a known algorithm. \n\nRegarding Algorithm 2. The analysis seems quite close to previous work, once you notice the existence of a mutual shrunk polytope.\n\nRegarding the non-convex setting. The main goal of the study of this setting is to understand why online gradient descent works well in some specific non-convex settings. It is not clear which is the significance of extending the analysis to distributed algorithms with unknown safety constraints.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies safe distributed online optimization. In particular, a network of agents optimizes a global, time-varying function subject to linear unknown constraints. Each agent observes only local information about the objective function and can communicate with their neighbors. Differently from the objective function, the linear safety constraints are common to all the agents. The authors provide an algorithm that provides a $O(T^{2/3} \\sqrt{\\log T}+ T^{1/3} C^*_T))$ dynamic regret bound for convex functions, where $C_T^*$ denotes the path length of the best minimizer sequence. Moreover, they provide an algorithm for some non-convex problems.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please highlight the technical challenges you face to extend distributed algorithms with known constraints to your setting.\n ", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tNjowVjVmD", "reviewer": "Reviewer_dTFm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1) To the best of my knowledge, this paper is the first work to study the problem of safe distributed online optimization.\n2) Compared with existing studies on centralized safe online optimization, this paper provides a more careful analysis to handle the difference of safe sets estimated by these local learners.\n3) The dynamic regret analysis and the distributed extension of the existing non-convex online optimization are new to me.\n\n# Weaknesses\n1) The main idea to handle the unknown safety constraints almost is the same as that of Chaudhary & Kalathil (2022), though they only consider the centralized setting. It seems that the distributed setting does not bring some significant challenges for satisfying the unknown safety constraints, which makes this paper incremental to some extent.\n2) This paper only provides the upper bounds on dynamic regret. It is not clear whether these bounds are optimal or not. \n3) In the theoretical analysis, the authors have utilized some useful conclusions from previous studies, but the introduction about these results is not easy for readers to check, e.g., the application of Theorem 3.1 in Bonnans et al. (1998) (below Eq. (27) in this submission), the application of Theorem 3.7 in Shi et al. (2015) (below Eq. (17) in this submission).\n\nMoreover, as listed below, this paper needs to make some important modifications, and the current version cannot be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the problem of safe distributed online optimization, in which all local learners need to satisfy an unknown set of linear safety constraints. Both convex functions and a certain type of non-convex functions are considered, and an algorithm called D-Safe-OGD is proposed. Moreover, the authors prove that it can attain a dynamic regret bound of $O(T^{2/3}\\sqrt{\\log T}+T^{1/3}C_T^\\ast)$ for convex functions, and a dynamic regret bound of $O(T^{2/3}\\sqrt{\\log T}+T^{2/3}C_T^\\ast)$ for the certain type of non-convex functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The authors should provide a more formalized introduction to Theorem 3.1 in Bonnans et al. (1998) and Theorem 3.7 in Shi et al. (2015) before using them.\n2) In the first inequality of Eq. (41), the authors have utilized $\\\\|\\Pi_{X}(x)-\\Pi_{X}(y)\\\\|\\leq\\\\|x-y\\\\|$ for any $x,y$, which is not very straightforward. So, it would be better if the authors could provide detailed explanations.\n3) In page 3, Besbes et al. (2015) only establish an $O(\\sqrt{T(1+V_T)}\\log T)$ dynamic regret bound for strongly convex functions.\n4) Lemma 1 is almost the same as Lemma 1 in Chaudhary & Kalathil (2022). So, the authors should also give some credit to Chaudhary & Kalathil (2022) when introducing this lemma.\n5) The upper bounds presented by this paper ignore all other constants except $T$, $\\delta$, and $C_T^\\ast$. It would be better if the authors could also provide these omitted constants.\n6) When discussing the related work on dynamic regret, the authors should clearly distinguish the general dynamic regret with respect to any sequence of comparators and the worst-case one studied in this paper.\n7) Some related studies on the worse-case dynamic regret [1][2][3] are missed, and should also be discussed.\n8) Some related studies on distributed online optimization with complex constraints [5][6] are missed, and should also be discussed.\n\n[1] Zhang et al. Dynamic Regret of Strongly Adaptive Methods. In ICML, 2018.\n\n[2] Wan et al. Projection-Free Online Learning in Dynamic Environments. In AAAI, 2021.\n\n[3] Wan et al. Improved Dynamic Regret for Online Frank-Wolfe. In arXiv:2302.05620, 2023.\n\n[4] Zhang et al. Projection-free Distributed Online Learning in Networks. In ICML, 2017.\n\n[5] Wan et al. Projection-free Distributed Online Convex Optimization with $O(\\sqrt{T})$ Communication Complexity. In ICML, 2020.", "broader_impact_concerns": "I have no concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The problem being studied and the technical results are new. The majority of the reviewers found the results of interest. One expert reviewer has concerns about the "relatively weak technical contribution" of the work as most of the techniques used for the algorithm and its analysis are from the existing work. The authors highlighted the challenges they had to overcome but the reviewer's concern on significance remains.

As per TMLR evaluation criteria https://jmlr.org/tmlr/editorial-policies.html#evaluation, the work meets both the "soundness" rule and the "interest" rule.   The "interest" is clear from the positive subset of the reviewers and I went through the paper with interest too. Overall, I am happy to recommend the paper for publication at TMLR.

I have some more comments for the authors consideration as a minor revision

1. The optimality in each parameter of the problem should be discussed more clearly.  The authors are frank that the regret bound they obtained might not be optimal in $C_T^*$. But is the $T^{1/3}$ term from Theorem 3 optimal (when the third term dominates)?  I am not sure if the conjecture that the optimal dependence on $C_T^*$ should be $\sqrt{C_T^*}$ in Remark 4 makes sense because when $C_T^* = T$ the expression is superlinear. 

2. I encourage the authors to add a "technical summary" after the summary of results at the end of the introduction, to comment on the proof techniques (which are new from this paper, which ones are adapted from existing work, and which ones are borrowed directly from existing work). An upfront discussion of the techniques helps the theoretical audience to quickly understand the "meat" of the work and determine whether some of the techniques from this paper can be useful for them elsewhere. 

3. The literature review on dynamic regret is a bit messy.  It introduced too many different versions of "path lengths" and different settings.  It might make sense to categorize the discussion a bit, and also to defer very involved discussion to the end of the paper (or even in the appendix). 

For example, the dynamic regret guarantee for the pointwise minimizer sequence C* is very different from (and much weaker than) that of the universal dynamic regret that competes with all sequences (Universal dynamic regret). Recent work has obtained optimal universal dynamic regret bounds for strongly convex / exp-concave losses (e.g., Baby and Wang, COLT'2021; AISTATS'2022) which is qualitatively very different compared to those of O(C_T^*) from Mokhtari et al. (2016). Generally speaking, in almost all stochastic / adversarial cases $C_T^* = O(T)$, e.g., linear regression, logistic regression, universal portfolio... the comparator sequence is not instantiated as pointwise optimal sequence, but rather another more slowly changing sequence for the interest of a better bias/variance tradeoff. 

 Related to the above, the authors also introduced many other variants of pathlength:  V_T,  C'_T, and squared variants. These are all good but dumping them on the readers when they are still trying understand what *this paper* is about is a bit distracting.  This is especially so because none of these alternative pathlengths were used in this paper.    Usually such literature discussion should focus on work that is directly relevant to the current work, e.g. either those that provide lower bounds for this setting, or those that the authors have borrowed settings / techniques / algorithmic ideas.  A longer discussion of the related work can be deferred to the end after the main results are presented.
Decision: Accept (poster)