Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Authors: Yiyang Lu
Mohammad Pedramfar
Vaneet Aggarwal
Venue: Accepted by TMLR ()

Abstract: We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of $O(T^{1-\theta/2})$ with communication complexity of $O(T^{\theta})$ and number of linear optimization oracle calls of $O(T^{2\theta})$ for decentralized upper-linearizable function optimization, for any $0\le \theta \le 1$. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

Published in Transactions on Machine Learning Research (12/2025)
Decentralized Projection-free Online Upper-Linearizable Op- timization with Applications to DR-Submodular Optimization
Yiyang Lu
hul 202 edu
Purdue University, West Lafayette, IN, USA
Mohammad Pedramfar
hatteammmad..pddrrmfooom @viilaa quebec
Mila Quebec Al MaeiittteMMGill University, Montreal, QC, Canada
Vancet Aggarwal
wanect&pprrbue.c edu
Purdue University, West Lafayette, IN, USA
Reviewed on OpenReview: https: openreview. net/ per/forum? id- b25WD2HUQY
Abstract
We introduce novel framework for decentralized projection-free optimization, extending projection-free methods to broader class of upper- eaper-linearizable functions. Our approach leverages decentralized optimization techniques with the ficxibility of upper-lincarizable function frameworks, effectively generalizing optimization of Iraditional DR-uuboodllar functions, which captures the "diminishing return' property. We obtain the regret of O(T'~0/7 with communication complexity of O(T)) and number of linear optimization oracle calls of O(T²2) for decentralized upper- lincarizable function optimization, for any 0 I 8 I This approach allows for the first. results for monotone up-concave optimization with general convex constraints and non monooon up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.
1 Introduction
Modern machine learning systems, from multi-agent robotics distributed sensor networks, increasingly rely decentralized optimization to handle streaming data and objectives that evolve over time (Li et al. 2002 Xiao et al.) 2007 Mokhtari et al. 2018). A prominent challenge in these systems is the online optimization of non-convex functions that exhibit a "diminishing returns (DR)" property, a characteristic formally captured by DR-uubmodularity For instance, in power network reconfiguration (Mishra et al., 2017), distributed controllers across a smart grid must cooperatively adjust network switches to minimize system-wide power loss. This scenario inherently decentralized: each controller uses local data, like power flow and voltage levels, to adjust its switches, and communicates with its immediate neighbors to coordinate their actions toward the global goal of minimixing system-wide power loss. This communication involves exchanging proposed adjustments and local states, which are then aggregated using weight matrix that determines the influence of each neighbor's input. This weight matrix is predetermined by the physical characteristics of the power network itself, such as the impedance of the power lines and the underlying network topology. The problem is also online because the optimal switch configuration must be continually updated to adapt unpredietable shifts in consumer power demand and intermittent generation from renewable sources. The optimization task, which is to maximize power loss reduction, exhibits diminishing returns property: the first few switch adjustments may yield substantial improvements, but the marginal benefit of each subsequent reconfiguration tends to decrease. This frames the problem as the maximization of a DR-submodular objective whose parameters change over lime, making a decentralized, online solution essential. Such formulations also emerge in a wide array of other applications, including dynamic pricing, recommendation systems, inventory management, and mean-field variational inferences (Bian
2019 Aldrighetti et al., 2021 Ito & Fujimaki, 2016 Hassani al. 2017 Mitra et al. 2021 Gu al. (002)). In all these scenarios, agents must cooperate to maximize a global objective, often with limited communication and time-varying objective functions. To

---

Published in Transactions on Machine Learning Research (12/2025)
provide unified solution for these scenarios, our work addresses y-weakly up-concave functions, class that generalizes both concave and DR-submodular functions!" H The parameter allows for a relaxation of this condition, with standard DR-submodular functions corresponding to the special case where = 1. We introduce these notions formally in Section 3.1
Existing methods for online continuous DR-suboddular optimization often fall into two broad categories: projection-based and projection-free The first category, projection- based strategies (Chen et al. 2018b) Zhang et al. 2022); ; ensure that each decision remains within the feasible set by computing a Euclidean projection in each round, which requires solving quadratic program. The second category, projection-free techniques
(Chen et al. 2018a b Zhang et al., 2019 Liao et al., 2023). replace projection operation with an efficient linear optimization oracle to update decisions. For many complex sets common in machine learning, the projection step is intractable for online settings, and the computational cost of an LOO is often orders of magnitude lower than that of a projection (Hazan 2016 Braun et al. 2025). For instance, BBaun et al. (2025) has shown in Table 1.1 that for problems constrained to a muclcar norm ball, projection requires a full singular value decomposition, whereas linear program only requires finding the top singular veclor pair, which is a much faster operation. Empirically, in our specific scenerio, Table 2 in Zhang et al. (2023) has shown that their projection-free algorithms are up to 6 times faster in practice than a projection- based counterpart for decentralized DR-submodular maximization, which motivate our paper's 's focus on developing a novel, projection-free framework.
However, in the recentralized realm, existing works in this area (Zhu et al., 2021 Zhang et al. 2023 Liao
et al. 2023) often either achieve sub-optimal regret guarantees or require too much communication, and they are all restricted to narrow subclasses of functions, such as monotone 1-weakly up-concave (DR-submodular) functions over convex sets containing the origin, leaving significant gap in the literature. Recently, the theoretical landscape was broadened by Pedramfar & Aggarwal (0024a), which introduced "upper-lineara lineariabee functions", more general class that includes and extends DR-submodular and concave functions. This framework unifics optimization for various settings, including monotone and non-monotonc up-concave functions over general convex sets along with monotone up-concave functions over convex sets containing the origin, and considers diverse feedback types. However, the analysis and algorithms for this powerful tiner-linc optimization framework has so far been confined to centralized scttings, where a single agent has access to all information.
This paper bridges that critical gap by introducing the first framework for decentralized, online optimiza- tion of upper-linearizable functions. Our primary objective is to develop projection-free algorithums that are not only computationally efficient by avoiding projections but are also tailored for the communi- cation constraints inherent in decentralized networks. By extending the analysis from the centralized to the decentralized setting, we provide the first optimization results for several important problem classes, including online monotone and non-monotone up-concave maximization over general convex domains in the decentralized realm. For monotone DR submodular functions over convex sets containing the origin, with first order full-information feedback, which is the premise of prior works, this paper gives an algorithm that achieves a regret of (Vrrl-/2))itth a communication complexity of O(T²) and O(726) calls to a linear optimization oracle, where E [o, 1] is a parameter that allows for an explicit trade-off between regret and communication overhead. Furthermore, our framework is versatile, enabling us to derive new results for various feodback models, including full-information, scmi-bandit, and bandit settings, which were previously unexplored for decentralized DR-uuboddular optimization.
We also summarize our contributions and technical novelties of this work in details as follows.
1. A General Framework for Decentralized Online Optimization of Upper-Linearizable Functions: we introduce the first framework for dccentralized, online optimization for the broad class of upper- lineorizable functions. This function class is a generalization of up-concave (including DR-submodular and concave) functions, providing significant leap over prior works that were restricted to monotone 1-weakly up-concave (i.e., DR-submodular) functions over convex set containing the origin under first-order full-information feedback (See Table I Our framework unifics the analysis of various settings, including
It. is well-known that any Su-uuuuu function up-concave, iee,, concave along positive directions.
2

---

Published in Transactions on Machine Learning Research (12/2025)
Table 1: Decentralized Online Up-concave Maximization Algorithms Comparison
F'
Set
Feedback
Reference
Appx (a)
logy (ar Hegget))
logy Coomommizattion)
(LOO calls)
Range of
DMFW
Zhu
5/2
5/2
full informatioon
Monu-DMF DMT
Ziang
ml
2020
I-
4/5
Monstoue
DODGA
Zhang ct
0
DPOBGA
1o00
8
20233
1-e-
3/4
1/2
1
Hloonen
8/2
20
semi-handii
Teeorom 01
8/2
0
22
10. 2/3
Full informationn
Theoren
1-
8/4
20
10.
bandit
Thevecm 18
8/4
22
00. 476
VF
semai- bandic
Theorenn
71
072
20
10.
banddit
Iheoresn 01
711+0
20
Full information
Theorenn
200
00
sctai bandis
Heeopesu
072
20
00. 2733
Full informatiion
Theorenn
(1
8/4
20
10, 1]
handit
Theosom
M/44
10. 4/6
Table 1 compares the results for different decentralized online up-concave maximization algorithms. V refers to first-order query oracle while I' refers to zeroth-order query oracle. a refers to the approximation coefficient for the regret. The prior works only investigated monotone 1-weakly up-concave functions (i.e., only Su-subuodular functions) over convex set containing the origin, while our results apply to 7-weakly up-concave functions for different scenarios, hence the differences in a. Here p = mingex || // Communication refers to the total number of communications, and LOO calls refers to the total number of calls to the Linear Optimization Oracle. The results hold for any 0 in the range specified in the last column. Note that DOBGA is projection-basee and requires prjection oracle, while all others are projection-fres and utilize linear optimization oracle.
Notably, all prior works are confined to a very narrow subclass of functious: monotone 1-weakly up-concave (i.e., DR- submodular) functions over convex sets containing the origin. In contrast, our framework provides the first guarantees for a much broader range of problems, including general 7-weakly, non-monotone functions, and optimization over general convex domains. It also introduces a flexible trade-off between regret and communication via the parameter 0. Even when specialized, our results are highly competitive: setting 0 = 1/ matches the state-of-the-art projection method (DPOBGA), while A matches the regret of the best projection-baset method (DOBGA).
monotone and non-monotone 7-weakly up-concave functions over various convex sets by treating them as specific instances of the upper-linearizable class.
2. An Efficient Algorithm for the General Framework with a Principled Trade-off: In section ! we propose a single, versatile algorithum, DROCULO (Alg. [], for the general class of upper-linearizable functions. The algorithm operates with either banditandit or first-order inllmmnfoonmtion feedback, depending on the structure of the specific function class being optimizod. It achieves an explicit tradc-off between statistical performance and resource efficiency: for any parameter 0 E [o, IJ, it attains a regret of O(T2-8/2) with communication complexity of O(T") (Theorem 2). Even when applied to up-concave maximization, this provides the first results for several general classes, including monotone and non-monotone y w-aekly up-concave functions over various convex domains.
3. Extension to Different Feedback for Up-Concave Subclasses: In section 5 we demonstrate the practical utility of our framework by applying it to prominent up-concave subclasses. This specialization allows us to develop the first algorithms for these classes under restrictive feedback settings (Alg, 2-5). By extending aega-algorithmic techniques by (Pedramfar & Aggarwal 2024a) from centralized to decentralized setting, we design specialized solutions for:
monotone 7-weakly up-concave functions over general convex sets (Case B.1 We provide Alg. for the restrictive bandit feedback sctting.
monotone up-concave functions over convex sets containing the origin (Cases B.2 & non-monotone
up-concave functions over general convex sets (Cases B.3 We introduce a series of novel extensions for semi-bandät (Alg. 3). zeroth-order full-information (Alg. and bandit feedback (Alg. 5)
In total, our framework yields 10 algorithms for up-concave maximization (two for Case B.1 four for
Case B.2 and four for Case B.3 9 of which are the first results in their respective feedback sengings.
Technical Novelty
3

---

Published in Transactions on Machine Learning Research (12/2025)
1. We note that previous works on decentralized summmouul optimization assumed monotone 1-weakly DR-submodular functions with 0 E K. Thus, we needed non-trivial approach to extend the setup to include non-monotonicity of the function, 7-weakly DR-submodular functions, and general convex set constraints. This is done using the notion of upper-linearizable functions, allowing us to obtaín the first results for (i) monotone 7-weakly up-concave functions with general convex sets, (ii) monotone y-weakly up-concave functions over convex sets with E K, and (iii) non-monotone up-concave functions with general convex sets.
2. We proved that the framework proposed by Pedramfar & Aggarwal (2024a) which was proposed for and examined in the centralized setting, can be extended to the decentralized setting with proper adaptations. The notion of regret changes in the decentralized setting, where we have to consider the average of loss function among all agents instead of just one function, as is the case in the centralized setting. Note that the changes in the definition of online optimization between centralized and decentralized optimization makes applications of meta-algorithms used in Pedramfar & Aggarwal (2024a) non-trivial. The centralized version have no notion of communication between nodes and it requires nuance in how one goes about applying mcta-algorithms designed for centralized sctting to base algorithms that are decentralized.
3.
In the cases of monotone functions over convex sets containing the origin and non-monotone functions, the main algorithm, i.c., DDROCULO, requires first order full-ifoormation feedback. In the centralized setting, the SFTT meta-algorithnn described in Pedramfar & Aggarwal (2024a). is designed to convert the such algorithms into algorithms only requiring semi-bandit foedback. However, this algorithm does not directly work in the decentralized setup. We design A Algorithms 3 and 5 using the idea of SFTT meta-algorithm. The challenge here is to ensure that the SFTT blocking mechanism interacts properly with the existing blocking mechanism of the base algorithm.
The remainder of this paper is organized as follows. In Section 2, we review related work. In Section 3, we establish the necessary preliminarics, including our notation, problem formulation, and key definitions for upper-linearizable functions. In Section 4, we present our main algorithm, DROCULO, with its theoretical guarantees for the general upper-linearizalee class. In Section 5, we extend this framework by developing specialized algorithms for prominent subclasses of up-concave functions under various feedback settings, including semi-bandit and bandit feedback. All detailed proofs are deferred to the appendices.
2 Related Works
Decentralized Online Convex Optimization: Zinkevich et all 2010 presented a decentralized primal- dual gradient method using local communication and dual averaging over static networks, and achieved Ö regret for Lipschitz losses, yet it assumed static connectivity and full gradient access, limiting adaptability in dynamic settings. Yan el. al. (2012) exlended this via distributed projected gradient descent across agents with standard communication steps, proving regret bounds p/15//p-1/22/7
for convex functions, but it suffered from polynomial dependence on n and spoctral gap p. Lee et all (2016) proposed ODA-C and ODA-PS, incorporating Nesterov-style dual-averaging on static and dynamic graphs, achieving similar O(VT) regret; still, its performance degrades in heterogeneous or rapidly changing networks. Wan et al.
(2024) introduced AD-FTGL with online accelerated communication, tightening regret to -ITV") for convex losses, and proved matching lower soaudd--losiig gaps in carlier algorithms' dependence on p and n.
Lincri-liee Function and its Online Algorithm: In late 2024, Podramfar & Aggarwal (2024a) introduced the concept of liper-linearizable functions, a class that generalizes up-concavity (concavity and DR-submodularity) across various settings, including both monotone and non-monotone cases over different convex sets. They also explored projection-free algorithms in centralized settings for these setups. Additionally, they proposed several meta-algorithms that adapt the foodback type, converting full-information queries to trivial queries and transitioning from first-rrder to zeroth-order leedback. These ideas were furt generalized in [Pedramfar et al.) 2025) by using "uniform wrappers"; a framework to convert algorithms for online concave optimization to online upper-Iinaaizaable optimization (in the centralized sctting). PPddamffar & Aggarwal (2024a) demonstrated the generality of this class of functions by showing that includes (i) monotone 7-weakly up-concave functions over general convex sets (Case B.1 (ii) monotone 7-weakly up-concave functions over
4

---

Published in Transactions on Machine Learning Research (12/2025)
convex sets containing the origin (Case B.2 and (iii) non-monotone up-concave optimization over general convex sets (Case B.3 The details of these functions are provided in Appendix B for completeness, and Lemma 5 i demonstrate how these prominent up-concave functions are upper-linearizable However, the framework of Upppe-Linearizable functions' is not restricted to these three examples. While these functions are central to contemporary research in submodular optimization, the "Upper-iineariabbl concept. is relatively new, and its full scope is a subject for future exploration.
Decentralized Online DR-Submodular Maximization: Prior works in decentralized online DR- submodular maximization have largely followed two algorithmic paths. One path, rooted in the Frank- Wolfe method, was initiated by the Decentralized Meta-Frank- Wolfe (DMFW) algorithm from Zhu et al. (2021), which achieved an ((vT) regret but at a high communication cost of O(T5/2). This limitation was later addressed by by the Mono-DMFW from Zhang et al. (2023), which improved regret to O(T4/5) while reducing communication complexity to O(T). The other path leverages boosting gradient ascent, introduced with the projection-based DOBGA algorithm from Zhang et al. (2023). which obtained an O(TI/2) regret with O(T) communication. The principles of this method were subsequently adapted to projection-free context by Liao et al. 2023 in their DPOBGA algorith, reporting ((73/4) regret with 0(T communication.
Notably, these prior works were confined to maximizing monotone DR-submodular functions over convex sets containing the origin. This setting, corresponding to 1-weakly up-concave functions, restricts all prior methods to the same 1 - 1/e approximation ratio, and represents a special instance of the general problem classes we address (Appendix (.2).
In this paper, we present algorithms for optimizing upper-lineaizablle functions, achieving regret bound of O(T1-)/2), in first order foedback case, and O(T1-6/4), in zeroth order feedback case, with communication complexity of O(T9) and number of LOO calls of O In finst order full-inoormation case, for 0 1, we show that the regret and the communication complexity matches the best known projection- based algorithm in Zhang et al. (2023) and for 0 = 1/2, the results match that in Liao et al.] (2023) in the special case of monotone 1-weakly DR-submodular functions with the convex set containing the origin.
3 Preliminaries
3.1 Notations and Definitions
This paper considers decentralized setting involving N agents connected over a network represented by an undirected graph G (V, E), where V (1, [I.... NN is the set of nodes, and E C V x V is the set of edges. Each agent E V acts as local decision maker and can communicate only with its neighbors, defined M = E V (i,j) E E) U (i). To model the communication between agents, we introduce a non-negative weight matrix A = [ary] E R4 N which is supported on the graph G. The matrix A is symmetric and doubly stochastic, with a.j > 0 only if (i,j) E E or i = j. Since A = A and A1 = 1, where 1 denotes the vector of all ones, 1 is the largest eigenvalue of with 1 being the eigenvector. When agent i communicates with its neighbors Ni. it exchanges a local state vector s based on the weight matrix A =a In other words, each agent i receives the weighted average of the local states of its neighbors, i.e., ΣjEN; atys² It is common to assess decentralized optimization algorithms using the total number of commuications with respect to total rounds T, which is denoted as "communication" in Table I These are formally captured in Assumption
Assumption 1.
We assume that the communication weight matrix A is synmetric and doubly stochastic, whose second largest eigenvalue, X2, is strictly less than 1.
Remark 1. As mentioned, A dictates how information is shared and averaged across the network, and its largest cigenvalue is always 1. The rate of convergence, however, is captured by the sccond-largest cigenvalue, X2, which reflects the network's 's connectivily. A smaller X2 implies a belter-connected net work and faster convergence. Assumption [ is standard in decentralized optimization literature (Zhu et al.) 2021 Zhang et al.) 2023 Liao al. 2023). If were violated (i.c. X2 = 1), the network would be disconnectod, composed of least two isolated sub-groups of agents that cannot communicate with each other. In such a scenario, a global agreement is impossible, and the algorithm would fail to find solution for the nid objective.
5

---

Published in Transactions on Machine Learning Research (12/2025)
A set IC Rd is convex if y E K and Va [0.1], 1], we have ax + (1 a)y E K. For constrained set KC, we denote the radius of the set as R A max |x|], Vx E K. For two vectors x,y É K, we say x S y if every element in x is less than or equal to the corresponding element in y. Given a set K, we define a function class F as a subset of all real-valued functions over X. For a set IC _ R we define its affine hull (I) to be the set of ax + (1 - any for all x,y E K and a E IR. The relative interior of K. defined as reCint(K)) = (x E K. Br > O, (x) O (a)f(K)) S K). Assumptions of the feasible set K. 2 given as follows. Assumption 2. We assume the feasible set K. is convex and compact with radius R, i.e., R = maxxex ||x||
Given 0 < < < we say a differentiable function f K + R is y-weakly up- up-concave if it is y-weakly concave along positive directions. Specifically if, Vx S y E K. we have
7 (VV(()) x)) - f(y) f(x) = (VV((x). x)).
(1)
A differentiable function f K. - R is called 7-weakly continuous DR-submodular if Vx I y, have fx(x 2 vVyy). It follows that any y-weakly continuous DR-submodular functions is y-weakly up-coneave. Note that DR-submodular functions are a special case of up-concave fumetions, though the term "DR- submodular" is more common. For generality, this paper will use the broader "up-concave" term, as our results for this class apply directly to DR-submodular functions. In subsequent sections, we will demonstrate that these up-concave functions are prominent examples of the broader upper-linearizable class.
Given a DR-submodular function, even the maximization problem in the centralized offline setup is NP-hard. For example, when f is monotone continuous DR-uubmo function and K. [0, 1]d contains the origin, finding point E IC such that fx) is optimal is Na-hard. More generally, for any 0, finding any point X E IC such that f(x) is at least (1 - ----+ + c) times the optimal value is NP-hard. (See Proposition 3 in Bian et al. (2.17)) However, there are polynomial times algorithms that achieve the ratio of 1 - e-1. The ratio with this property is referred to as the optimal approrimation ratio, in this case being 1 e- In the three settings considered in this paper, (in the special case of 7 = 1) the approximation ratios for monotone function over convex sets containing the origin and non-monotone functions over general convex sets are known to be (Ste Bian al. (2017): Mualem & Feldman (202)) In the case of monotone functions over general convex sets (when 7 = 1), the approximation ratio of 1/2 is the best known in the literature far and it is conjectured to be optimal (Sce Pedramfarr et al. 2023))
Given a function F. + IR, we define a query oracle Q for f to be function on IC that takes a point of query w, and returns a noisy response o. We say Q is a first order oracle if Vw E K, @(w) is a random vector in Id such that [[](w)] = f(w). We say Q is a zeroth order oracle Vw E K, Q(w) is random variable in R such that B[[(w)]= f(w). The role of Q is to provide us information about the function f; in other words, the only way we obtain information about is by querying Q.
3.2 Upper-Linearizable Functions
Recently, Pedramfar & Aggarwal 2024a) proposed the notion of upper-linearizable function, which generalizes the notion of up-concave and DR-submodular. The function class F is soper-linearizable if there exists g F x Fx
Rdd h : K. K. and constant < a S and / > 0 such that Vx,y K. V.FF:
a - f((()) s B ((
(2)
As mentioned in the Section 2 with details in Appendix B Pedramfar & Aggarwal (024a) has demonstrated that three common objectives in the submodular optimization communities are upper-linearizabl
monotone 7-weakly up-coneave functions with general convex sets (Case B.1
(ii)
monotone 7-weakly up-coneave functions over convex sets with 0 E KC (Case B.2
and
(ifi) non-monotone up-concave functions with general convex sets (Case B.3
In our setting, at each round, every agent selects decision from common feasible set K. C Rd, which we refer to as the action set. The detailed problem setting is given below in Section 3.3

---

Published in Transactions on Machine Learning Research (12/2025)
In Appendix B we also provide the corresponding a, B, h(+) and g() mapping, and their linearizable query oracles. As we will see later on, given an upper-linearizable function class F, the constant corresponds to the approximation ratio of our algorithms when the objective functions are in F; specifically, it serves as the approximation coefficient for the regret.
When optimizing upper-linearizable functions, we assume that an oracle g provided, which we call linearizable query oracle, that returns an unbiased estimate of g(f.x). We refer to Appendix B for examples of such oracles for the three cases of upper- lipaariinee functions.
We note that the function h allows us to consider more general functions. For example, 1() takes identity
function for case B.1 and case B.2 while h(x) x+x for some constant x E K. for case B.3 A detailed
2
discussion on the role of the function h is presented in Appendix A
As mentioned, the framework of 'upper-linerizabbe functions' is not limited to these examples, although they are the most well-known function classes to submodular optimization community. The supper-lincarzalee framework is a recent development, and it is anticipated that further applications will be identified as the concept matures.
3.3 Problem Formulation
In decentralized setting, given function class F, the adversary chooses sequence of objective functions ft, E FF and the corresponding query oracles Qt,i, for round t E [T] and agent i E [N]. Note that the query oracle is the only way the agent can get any information on the objective function. In 1th round, agent i selects a pair of points x!, wi E K, plays & queries the provided oracle at w and observes oracle response of = (w!).
The agent may communicate a local state vector st with its neighbors N, as per Section 3.1 i.e., each agent i receives the weighted average of the local states of its neighbors Σjex; 4:y8/-
We say the queries are trivial if w/ xj, otherwise we say they are non-trivial. Note that in the three up-concave functions we mention in Related Works with details in Appendix B case B. has trivial queries while case B.2 and B.3 have non-trivial queries, with Algorithm determining the point of query for case B.2 respectively.
and Algorithm for case B.3
The goal for each agent is to optimize the aggregate function over the network over time: E Ej= fes [Zhu et al. 2021 Zhang et al. 2023). For any approximation coefficient 0 < a S 1, we define the a-regret for agent i to be:
1 T
N
T N ΣΣ 1=1
Rd = a max
Σ
fir fes(u)
1
fee (x)).
DEK N 1=1 1=
N
Remark 2. As per our earlier discussion in Section 3.1 if we set a = 1, obtaining a sublinear a-regret even the offline centralized version of the problem could be NP-hard. Thus, the goal is to find the highest a possible and minimize the a-regret for such a choice of a. As shown in Pedramfar & Aggarwal (2024a). , if a function class upper-linearizable with constant a (as per Equation 2), then there are algorithms obtaining sub-linear a-regret in the corresponding offline (and online) optimization problems. In Cases B.2 and B.3 (in the case
y=1) the optimal approximation coefficient for the offline problem is known (See Bian et al. (2017): Mualem & Feelmaan (2023) and the function classes in B.2 and B.3 are upper-lineane linearizable with these approximation cocfficients. Morcover, for case B.1. the function class is lincarizable with the cocfficient 72/(1 + +cy?) which is
the best known approximation coefficient for the corresponding oflline optimization problem. Thus, among
the results in this work for Cases B.I B.3 it is only for the case B.1 where a higher approximation coefficient is not yet theoretically ruled out.
We say the agent takes semi-bandät fredback if the adversary provides first-order oracle and the agents have trivial queries. More formally, the query oracle returns a noisy response with mean of V ( Similarly,
3I general, the agent may query more than one point; other words, it selects an action point x; and sequence of points (wE), for j [k] for some & 2 which may depend and i, However, in all algorithms considered in this paper, agents only require single query. 4In fact, mentioned earlier, at least in the case == r = 1, this coefficient is conjectured to be optimal. (See Pedramfar et al. (023))
7

---

Published in Transactions on Machine Learning Research (12/2025)
say the agent takes bandit feedback if the oracle is zeroth-order and the agents have trivial queries, i..,, the query oracle returns noisy response with mean of ft,(()). Tf any agent has non-trivial queries, we say the agent requires full-information feedback. More formally, first-order full-information feedback returns a noisy response with mean of f(.((w)) and similar for zeroth-order, ft,(w;))
3.4
Set Oracles
The action set is a given convex set K. However, the way such a set is given could be quite complicated, For example, could be given as intersection of hyperplancs, or balls, or by some more complicated equations. Naturally, obtaining information about X, depends on the way it characterized. In order to abstract away this complexity; the notion of set oracle defined. Besides some general information given at the beginning, the only way the algoritim may obtain information about K. is through such set oracle. The most common set oracles considered in the literature are linear optimization oracle (LOO) and projection oracle. As mentioned in Section | projection oracles could be computationaly costly since such an oracle minimizes Euclidean distance, which is a quadratic optimization problem. To avoid problems caused by projection oracle, we use an infeasible projection oracle which is implemented using an LOO, and we introduce these concepts formally in the following.
A projection oracle Op takes any point Id as input and returns the unique point in K. that is closest to x with respect to the Euclidean norm, formally computing Op(K,x) == arg millue: ||x - ul/2- This oracle is central to projection- projection-based based algorithms,, which ensure feasibility by projecting iterates back onto the set K.. A linear optimization oracle (Olo) takes a linear objective, defined by a vector x E Ed, as input and returns a point in K that maximizes this objective. In other words, for any given x E R4, the oracle solves the problem (,, x) == arg (xx u). This oracle is the core of projection-Iree methods, which avoid costly quadratic projection problems by instead solving a sequence of linear problems over the feasible set.
Given set I. C Rd we define a point ý E Rd to be the infeasible projection of y E Rd onto set K, if Vz K. we have 1 2|2 < lly 211². Given a set K. and an error tolerance parameter e, we define an infeasible projection oracle Onp to be an algorithm that takes a pair of points x E K. and y E Rd returns pair of points x' E K. and y E Rd, where y' is an infeasible projection of y unto set K, and ||x - - < 3e. Specifically, we look at infeasible projection oracles implemented through linear optimization oracles. We also introduce a useful lemma derived from (Liao et al. 2023) for the infcasible projection oracles.
Lemma 1 (Lemma 1 in Liao et al. (2023)). Let B be the unit ball centered at the origin. There exists on algorithm Orp referred to as infensible projection oracle over any conver set K. C RB (where RB means a ball with radius R), which takes the set K,, a pair of points (x) E x R", and an error tolerance parameter e as the input, and can output
(x, OIP(X0, e),
such that (x,y) E IC x RB, ||- |x-111 8/12 < 3e, and Vz E KC, 11 - z1|² < Ilyo zl1². Moreover, such an oracle OIp can be implemented with total LOO calls bounded by
27R²
||xo - yoll (11xo yoll2 - c) +1)
2 max
1,
(3)
4 Main Result for Decentralized Online Upper-Linearizable Optimization
In this section, we introduce our main algorithm, DecentRalized Online Continuous Optimization (DROCULO, like Dracula), which is projection-free method designed for the broad class of upper-lincarizabl functions. The theorctical analysis that establishes the performance guarantoes of our method relies on the following standard assumptions. Note that these assumptions apply specifically to the general analysis in this section; assumptions for the specialized cases in Section 5 will be introduced therein.
Assumption 3. All objective functions fr, E F:: K. + R are Mi-Lipschitz continuous, differentiable, and upper-linearizable with a, 3. g and h as defined in Equation g We also assume that g(f,x) is L Lipschitz with respect to the second term
8

---

Published in Transactions on Machine Learning Research (12/2025)
Note that it is common assumption in the literature (Liao et al. 2023 Fazel & Sadeghi 2023; Zhang et al.
2022 2024h for the underlying up-concave function to be smooth. In the three examples of upper-linearizale
functions we considered, the smoothness of the underlying up-coneave function implies Assumption 3 (See
Lemma Lemma
Assumption Given the upper-linenriabble function class F, The linearizable query oracle G access each fi, E through a first-order query oracle 2 such that its response for on imput x is an unbiased estimate of a(St,,, x;), i.e. [x]( = g(St,,, [i],,,,,xx;....... x;). We further assume that the responses of of the linearizable query oracle G are bounded by G, i.e., ||o||| [9((x)] G.
Note that Assumption 4 holds for the three examples of upper-linearizable functions detailed in Appendix B (see Algorithms 7 and The linearizable query oracle & serves abstraction layer. For given input x G determines the appropriate point wł to query the underlying first-order oracle Q to produce the required unbiased estimate of x.)). Thus, Assumption 4 is satisfied for these cases if the underlying first-order query oracle is bounded.
4.1 Algorithm
The DROCULD algorithm is presented in Algorithm 1 Without loss of generality we assume that T mod K = 0. It operates by partitioning the time horizon T into T/K blocks, namely Tm = {(m 1)K + 1.....mkK] for block 1 1 m < T//K, where is the block size. Each agent maintains a local state vector s constituted of decision variable x K and an auxiliary variable y for the infeasible projection, which are initialized a common point KC (line 2).
The algorithm proceeds in blocks (line 3). For each block m, all agents perform the following steps in parallel. At each lime step L within block m, agent plays the action & h(((.)) (line 6), where h(-) is the transformation map associated with the apper-linearizable function class. Note that the action played, x), may differ from the agent's 's internal decision variable, x The agent then queries the lincarizable oracle G at x to obtain response of (line 7). The specific query point w| is handled internally by the oracle G to produce an unbiased estimate of g(fr,, x
At the end of cach block, agent communicates its local state st = (xx) Fen) with its immodiate neighbors Nú, i.e., it receives aggregated state vector (EJEN; 01yXnn ESENs (155%)) (line 9). This information is used compute an intermediate variable ym+1 (line 10), which incorporates scaled average 1) EieT,, of K ( EiET.. o;) of the oracle responses from the block. Note that this averaging is the main purpose of the blocking mechanism as it allows us to reduce the variance of the estimates obtained from the query oracle. Finally, the agent updates its decision and auxiliary variables for the next block, (x Fi-1), by performing an infeasible projection using the oracle Olp with an error tolerance (line 11).
Algorithm Ralieed Online Continuous Upper-Linearizall Optimization DROCULO
1: Input: decision set K,, horizon T. block size K, step size 7) error tolerance number of agents N, weight matrix A = [aiz], transformation map h(.),, linearizable query oracle g
2: Set x = yi = =CEA K. for any i= -, 1,.................. for m 1.... ,T/K do
for each agent 1,.., N in parallel do for t Tm {(m 1)K 1..... mK} do
6: Play & h(
7: Query the linearizable query oracle G at x and get response of = (xx
8: end for
Communicate local state s = (x Pin) with its neighbors N₁ 10: Y +- EjEN, air5t, + + of
9:
11: (xf (x + (KC, EjeN, aiyx/ 6)
12: end for
13: end for
9

---

Published in Transactions on Machine Learning Research (12/2025)
4.2 Result and Analysis
We will provide the key results for the proposed algorithm, including the regret, communication complexity, and the number of total LOO calls used by the proposed algorithm. The result is given in Theorem D Algorithm
Theorem 1. Given Assumptions
7
ensures that the a-regret for agent i is bounded as
2R
18cT
R
R
S 3
+ 7TTKG
13TGV33
12cT
+
+ +YTTKG 12TGv3e
A2
+ (G + 2L, R) - 1)8 3322++ (3nKG + 22
1 X2
Purther, the communication complerity is O(T/K). Finally, the number of LOO calls are upper bounded as In particular, if we sel K21P02, then we have
27TR²
ck (8.5 5.5 K'ygo")
E [ 0 ( +
and the number of LOO calls is O
Proof. The detailed proof of Theorem is provided in the Appendix C For the completeness of argument, we provide a high-level outline of proof for the regret bound and the commmication complexity.
Regret: Note that instead of 1-weakly DR-submodular function which has the nice property of Vf(x) 2 fly), Vx y, we are dealing with upper linearizable functions, & much more generalized function class that includes any function that satisfies af(y) f(h(x)) s 3 ((g(fxx,, x-,yxx)),) x)) for some functional g. function h, and constants 0 < a < and B > 0 as previously described, of which 1-weakly DR-submodular function is an instance.
As common bound regret of convex algorithm with first order linear approximation (Orabona 2019 we bound the regret using the inner product of the distance in action space and function space to approximate the function value, with the help of law of iterated expectation. Let x" E argmax N Σ Di-1 f1 (1) denote the optimal action, we have
T/K
ERR
Σ
Σ
E -
N
Tm
7/ K
8
M
E( X Ōr.: (x.
1=1
10=1
TET
Rearranging terms to better leverage the communication structure of the decentralized network, have:
N T/K
B
S
(x" Xino (x
Tm
E
Σ (xin x/n (x.e()(m)))
(4)
N
Te
N
T/K
+E
x xin (xim)) :x
N
m=
Tm
10

---

Published in Transactions on Machine Learning Research (12/2025)
Let the three parts in Equation be respectively P1, P2. Ps. Through exploitation of properties of the loss functions and domain, the update rule (line 10) and the infeasible projection operation (line 11) in Algorithm ! we obtain the upper bound of the expectation of each part:
R
1867
E
E
TTTKK + 13TGV3e
Y
nK
1
12cT
9TTKG
12TGV3e
1 X2
nnK
3nKG + 2v
BPP] & G(N1/2 +1)
3v2e+ +
1- A2
33V2++ 3nKG + 2/
B P < 2L +1)
Aa
Adding P3, we obtain the upper bound for a-regret for agent i as given in the statement of the Theorem.
LOO calls: Based on Lemma for the infeasible projection oracle, have the number of LOO calls for agent i in block m as:
27R
(lyimt Σ
((llv Σ -x
(5)
4e2
JEN;
JEN
Through exploitation of the update rule (line 10) and the infeasible projection operation (line 11) in Algorithm I we have
Vm-1
Σ assin
22n G²
(6)
JEN;
Substituting 6 to
5 we obtain the total I,OO calls, ΣT/K my as in the statement of the Theorem.
With appropriate selection of parameters block size K, update step n, and infeasible projection error tolerance E, we have final results for the main Algorithm in Theorem ? Motivated by the trade-off between block size and the time complexity, we introduce a hyper parameter 8, through which users adjust block size accordingly, allowing resilience against practical communication linitations.
VKT: and == K2Tp, we get that for each agent the Theorem For Theorem choosing 1 1j
E R = 0012-012)
(7)
Further, the communication complexity is O(T9) and the number of LOO calls is O(T29).
We note that in the special case of 0 0= 1, there will be no block effect, and we achieve regret of O(VT), with communication complexity of O(T) and number of LOO calls of O(T?). Further, in the special case of = 1/2, we achieve a regret of (T8/4), with a communication complexity of O(VT) and number of LOO calls of O(T).
5 Extension to Different Feedback for Up-Concave (DR-Submodular) Optimization
In Section i we presented DROCULO, a general algorithm for decentralized online optimization of upper- linearizable functions. The analysis assumed access to a linearizable query oracle G built upon a first-order oracle. However, this assumption may not hold in settings with more limited foodback, such as semi-bandit or bandit scenarios. This section extends our framework address these settings for three prominent classes of up-concave functions, which instances of the upper-linearizable class (detailed in Appendix B). We present.
11

---

Published in Transactions on Machine Learning Research (12/2025)
series of new algorithms that adapt DROCULO to handle diverse feedback types. These algorithms provide the first known results for these function classes in their respective leedback settings. Notably, while prior work such as Liao et al. (2023) has addressed monotone up-concave functions over convex sets containing the origin, it was restricted to the 1-weakly up-concave case. Our results apply to the more general y-weakly up-concave, and consider other settings including monotone and non-monotone, general convex set and convex set containing the origin.
The structure of this section results from the nature of the query required by the base algorithm. Section 5.1 addresses monotone up-concave optimization over general convex sets (Case B.J where DROCULO requires only trivial queries (semi-bandit feodback). Section 5.2 addressos the other two cases (B.2 and B.3 where DROCULO requires non-trivial queries (full-iforrmation feedback). To achieve these extensions, we adapt the meta-algors from Pedramfar & Aggarwal (2024a) to the decentralized context, Similar to Section we introduce assumptions about up-concave functions we consider for our extension algorithms. Assumption will reduce to Assumption 3 and Assumption 4 will reduce to Assumption 4
Assumption 3* We assume all 7-weakly up-concave (as defoned in Equation 7 objective functions are continuous, differentiable, Lipschitz continuous, and smooth.
Assumption 4* Ginen the objective functions, we assume. the query orneles, whether zeroth-order or first-onder are bounded.
5.1 Monotone up-concave optimization over general convex set (B.1)
For monotone up-concave functions over a general convex (Caee B.1 the transformation map h(-) is the identity function. Consequently, the lincarizable query oracle g queries the first-order oracle at the point of action (wi = xt), which constitutes a trivial query. This implies that for Case B.1 Algorithm 1 operates under semi-bandit feedback. To handle the more restrictive bandit feedback (when zeroth-order instead of first-order oracle is provided), we adapt the Semi-bandit To Bandit (STB) meta-algorithm from Pedramffr & Aggarwal 2024b) to develop Algorithm
Before detailing steps in Algorithm 2 we introduce several mathematical notations that are being used by the STB meta-algorithm. Recall we have defined alfine hull and relative interior of set K. in Section 3 We choose a point c E relint(AC) and a real number r > 0 such that af) (c) S K. Then, for any shrinking parameter v 8 < r, we define Rs = (1 - 4 + &c. For a function f K. - IR defined on a convex set IC C Rd, its d-smoothed version RR + IR is given as
fx(x) = Ex [f()]] Ev-conn öv)],
where Lo =6==af(]) (X.) x, for any x E K., is the lincar space that is translation of the affine hull of K. and v is sampled uniformly at random from the k = dim(mi (Co))-dimennsoon ball Lo n (O). Thus, the function value fa(x) is obtained by "averaging" f over a sliced ball of radius 5 around For a function class F over K,, we use F3 to denote {ff I e F). We will drop the subscript 8 when there is no ambiguity.
(0).
The important property of this notion is that it allows for construction of one-point gradient estimator.
Specifically, it is known that
k fís(x) CEvxcors1SSxx: + öv)].
This allows us convert Algorithm D to allow for zeroth order feodback. Specifically, we run Algorithm [ on functions füs instead of fi, and when it requires an unbiased estimate of the gradient of ft,( we use [1x(x + ōv) where v is sampled uniformly from Lo ns!. More generally, if we have access to or,i, an unbiased estimate of Jr,j + dv), then for, is an unbiased estimnte of (xx(()). If the zeroth order oracle, from which or is sampled, is bounded by Bg, then we see that this new onc-point gradient estimator of f(, is
When k and therefore Co Rd, this equality well known, e.g. see Nemirovski füdin 1983): Flaxman al. 2005 The more general case where &e may be found in Remark in Pedramfar al. (2023)
12

---

Published in Transactions on Machine Learning Research (12/2025)
bounded by G' / Bo. Therefore, if set c= (3)) may use Theorem see that the regret is bounded by O ( ( and the number of LOO calls is O (x)) However, it should be noted that the functions fe, are defined over K&s and this regret computed against the best point in Ks which can be (() away from the best point in K. Hence, we see that
[ o +I+IKKG)+++ - -
Putting these results together, we obtain the following result, with detailed discussion and proof in Appendix D
Algorithm Bandit Algorithm for Case B.1
1: Input: decision set K,, horizon T, block size K, step size 7, error tolerance number agents N, weight matrix A = [ay]] transformation map l(()); smoothing parameler 8 S a, shrunk set Rs, linear space Co;
zeroth order oracle Q
Let k dim(Co)
Set x yi
Kg for any = 1, N
4: for m = 1.... TT/K do
5: for each node i = 1, 1,-.. N in parallel do
6: for t= (m - K)K + 1,.... mK do
7:
Sample v; e n Co uniformly
Play x h(x(,)) Query the oracle Q at &j and get response of Let of + à
10:
11:
end for Commiicaate xmm and y with neighbors
12:
13:
y +- Σ Sn m +1 Σ of
JENr
tETm
14:
(x OIp
R6, Σ JEN;
ais X yf m
15:
end for end for
16:
Theorem 3. For Case B.1 under Assumption a regret bound of
1
3
if we set e K2128-2 then Algorithm
ensures
+ TTKK" - (orx00==0)))) +ST)
E [
O
with at most O T(T) LOO calls and O(T/K) communication complexity. In particular, if we set K = T1 = T-011 and 1 VKT ue see that E. [ O(T1-0/4) with at most O(T29) LOO calls and ( communication complexity.
Remark 3. Our approach to gradient estimation from zeroth-order feedback relies on the one-point gradient estimator (Flaxman et al. 2005). An alternative, common in the bandit optimization literature (Agarwal et al. 2010 Shamir 2017]) is use two-point estimator, which queries the function at two points (e.g., f(x ov) and f(x ov)) to construct a finit--iffereen approximation of the true gradient. While two-point estimator provide better estimate of the gradient, it requires access to exact value oracle, which is often an impractical assumption. If an exact value oracle is available, one could use an approach similar to Pedramfar & Aggarwal (2024a] Algorithm 7) to develop a counterpart, of Algorithm 2 using the two-point gradient estimator. Note that such an algorithm will not be bandit, as it requires two queries per timestep. However, we may use arguments similar Pedramfar & Aggarwal 22024 Corollary 5) to see that such an algorithm has the same order of regret as the first-order algorithm based on. In other words, we obtain a regret. bound with the same order as Theorem 2
13

---

Published in Transactions on Machine Learning Research (12/2025)
5.2 Monotone up-concave optimization over convex set containing the origin (Appendix B.2 and Non-monotone up-concave optimization over general convex set (Appendix B.3
We now consider monotone up-concave optimization over convex sets containing the origin (Case B.2 and non-monotone up-concave optimization over general convex sets (Case B.3). In both cases, the lincarizable query oracle G must query the first-order query oracle at a point wi that is different from the action point x hxx,)) This constitutes a non-trivial query, meaning that Algorithm [ requires first-order full-information feedback for these function classes. The remainder of this section will introduce algorithms that extend our framework to handle other feedback settings for these two cases, including semi-bandit, zeroth-order full-information, and bandit. feedback.
5.2.1 Semi-bandit Feedback
As established, Algorithm [ requires first order full-information feedback for Case B.2 and Case B.3 To handle semi-bandit leedback (when first-order query oracle only allow trivial queries), Full-information To Trivial query" (SFTT) meta-algorithm from Pedramfar & Aggarwal (2024a). The key challenge lies in composing the SFTT blocking mechanism with the existing block structure of DROCULO and its inder-node communccttion protocol. The resulting method is presented in Algorithm 3
the "Stochastic
Algorithm Beni-Bandit Algorithm for Case B.2 and B.3
1: Input: decision set XC, horizon T, DROCULO block size K, step size 7), error tolerance e, number of agents
N, weight matrix A = [a:y], map h(-), SFTT block size 1, first-order oracle Q
2: Set x = yf = c E KC for any i= 1.
for m 1,... LR do
for each node
1, ................................ N in parallel do
for q (m 1)K
,k mm do
6: Play &
h(xx))
7: For B.2 we sample as described in Lemma and for B.3 we sample z as described in Lemma
8: For case B.2
let w = x and for case B.3 let w * (xi, uu) + u {u is a given constant) Sample 4 uniformly from ((1-1)A 1,....9
10:
for t= ( 1)- 1.......4. .L do
11:
if == t2 then
12:
Play the action 2 w
13:
Query the oracle Q at w and get response of else
14:
15:
Play the action zi- end if
16:
17:
end for
18:
end for
19:
Communicate x and yin with neighbors mk
20:
y' + Σ aigit +
Σ
o
JEN.
g=(m-1)K+1
21:
S sn+1) t OI(,K, Σ arj x yd k
JEN,
22: end for
23: end for
Let L 2 1 be an integer. The main idea here is to consider the functions (fA where J, = + Lisg St.i. We want to run Algorithm against this sequence of functions. To do this, we need to construct unbiased estimates of the gradient of J,.. This can be achieved by considering a random permutation ... Ht - feedback, at timo-step E we select the point where the original algorithm, i.c., Algorithm 1 needed to query. In the other L time-steps within this block, we pick the action that Algorithm D wants take and ignore the returned value of the query function. Thus, at one time-step per each block of length I,
1..... 1) gL and picking fe.... Since we want an algorithm with semi- bandit
14

---

Published in Transactions on Machine Learning Research (12/2025)
have no control over the regret, which adds OTT/L) to the total regret. In the remaining time-steps, the behavior is similar to Algorithm D with each action repeated I, - 1 times. We note that we are running
Algorithm 1 against fa with a horizon of T" T= Hence, using the discussion above and Theorem if
we set c = G², then we see that the regret is bounded by E [R.] = (L 1)0 (+ + nTT + O
the number of LOO calls is ((5)), and the communication complexity is bounded by O(T/KK) The key result is summarized in Theorem and the detailed discussion and proof can be found in Appendix
Theorem 4. For Case B.2 and B.
under Assumption
if we set e = K2 then Algorithm
ensures a regnet bound of
- + +
E [ = =
with at most ( T cKI) LOO calls and O
communication complexity. In particulor, if S S 2/3 and we see that IE [ O(T2-0/2) with at most O LOO calls
KL set K = 72-36/2 L- -= 18/2, and 1j 1 and O(T*) commanication complerily.
5.2.2 Zeroth-order Full-information Feedback
To adapt DROCULO for zeroth-order full-information feedback, where only function values can be queried, we employ a strategy analogous to the one in Section 5.1 Specifically, we adapt the "First Order To Zeroth Order" (FOTZO) meta-algorithm from Pedramfar & Aggarwal (2024a).
The core of this method is function smoothing. Instead of operating on the original functions fú,, the algorithm operates on their smoothed versions, ft.- This allows us to construct a one-point gradient estimator. By querying the function value at randomly perturbed point w + ōvद. we can obtain an unbiased estimate of the gradient (w.)) This estimated gradient can then be used in place of the true gradient required by the original DROCULO algorithm. The resulting procedure is detailed in Algorithın 4 The introduction of the smoothing parameter 8 affects the regret analysis, adding terms dependent on account for the approximation error. A full analysis and proof are provided in Appendix F leading to the regret bound
stated in Thcorem 5
Algorithm Zeroth-order Full-information Algorithm for Case B.2 and B.3
Input: decision set K, horizon T, DROCULO block size K, step size n, error tolerance e, number of agents N, weight matrix A = [aty]. map h(-), smoothing parameter 8 s a, shrunk set C&, linear space Co, zeroth-order query oracle Q
2: Let & = dim(Co)
Set x yi E Rs for any 1,...,,,, for m 1,... .T/K do
for cach node 1, N in parallel do mK
for t= (m - 1)K 1,
+,...,,m mKK do
7:
Play hxx )
8: Sample v E n Lo uniformly
9: For case B.2 let w = 2 x and for case B.3 let w =
* +x), u
10:
Query the oracle Q at w| + óv; and get response o
11: Let of + off/
12:
end for
13:
Communicate x and y with neighbors y + Σ an + Σ of JEN.
14:
1ETm
15:
Orp(Rs, Σ aizxi y m+)1 jEN,
16: end for
17: end for
15

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem 5. For Case 2.2 and B.3. under Assumption 1 3
we set K22/28- then Algorithm
ensures a regret bound of
0 =0 +TKK 1 +8T)
E [R:]]
with at most O ( LOO calls and O(T/K) communication complexity. In particular, if we set K = T k = T- and 1, /KT' we see that E [R 0(/4))/4) with at most O(T29) LOO calls and O(TD)
commumication complerity.
Similar to Remark if an exact value oracle for the objective function is available, one can develop an counterpart of Algorit hm using two-point query instead of one-point query, and obtain a regret the
order of Theorem 2
Algorithm Bandit Algorithm for Case B.2 and B.3
1: Input: decision set X,, horizon T, DROCULO block size K, step size 7) error tolerance e, number of agents N, weight matrix A = [aiz], map h(-), SFTT block size 1, smoothing parameter S a, shrunk set K&, linear space Lu, zeroth-order query oracle Let & dim(Lo)
Set x yi = E Rs for any i= -. N
4: for m = 1.... , do
5: for each node = =1. 1,.., N in parallel do
6: for q =
1,2,..., 1,
K do
7: Let x h(x,),
8: Sample v E S
nLo uniformly
For case B.2 let w = x and for case
B.3 let w = * (x - u)
10:
Let w w + gv
11:
Sample 1 uniformly from {(m - 1)KL + (1 1)L + 1,..., (m
12:
for t = (m 10)-1)KL-- (q - 1)L + I,..., (m K)LL + 9L do
13:
if t tt then
14:
Play the action z, = w
15:
Query the oracle Q at w and get response of Let of + v
16:
17:
elsc
18:
Play the action 2, = &
19:
end if
20:
end for
21:
end for
22:
Communicate x and yú, with neighbours
23:
y +- E an + Σ JEN.
4=1 o
24:
(x 1n41) +- OIr(Rs, Σ aiz arjx y m+) jEN,
25:
end for
26:
end for
5.2.3 Bandit Feedback
Finally, to design an algorithm that can operate under bandit feedback (i.e., zeroth-order, trivial queries) for case [B.2] and [B.]] we combine the strategies from the preceding two subsections. The process involves a two-step adaptation of the original DROCULO algorithm. First, we apply the FOTZO meta-algorithm handle zeroth-order foedback, resulting in Algorithm Second, we apply the SFTT meta-algorithm Algorithm to convert its non-trivial queries into trivial ones. The resulting method, presented in Algorithm effectively
16

---

Published in Transactions on Machine Learning Research (12/2025)
applics the SFTT blocking mechanism the smoothed-functinn approach of Algorithm 4 The analysis of this composite algorithm must. therefore account for error terms from both adaptations: the function smoothing (parameterized by 5) and the SFTT blocking (parameterized by L). This leads to the final regret bound
presented Thcorem with a detailed proof available in Appendix
Theorem 6. For Case B.2 and B.3
under Assumption
1
if we set e K2 then Algorithm
ensures a regret bound of
E [2 = -0
+ nTTK + ST + 4
with at most (1 ( LOO calls and O (
TT.) communication complezity. In particular, if S S 4/5 and 8 = T-0/4, L = T / and n = T0/2-1, we see that E [R. = O(T1-0/4) with at most 2 LOO calls and O(T9) communicaaton complezity.
ETT,
we set K = T 50
6 Conclusions
In this paper, we presented a decentralized, projection-free approach to optimizing upper-iicarizzble functions, which extends the analysis of classical DR-submodular and concave functions. By incorporating project ion-free projection-free methods, our framework provides efficient. regret bounds of O(T1-0/2), in first order feedback case, O(T1-9/4) in zeroth order feedback case, with a communication complexity O and number linear optimization oracle calls of O(T²") for suitable choices of 0 S 0 < 1, making it scalable for large decentralized networks. This illustrates tradeoff between the regret and the communication complexity. The versatility of our approach allows it to handle variety of feedback models, including full information, semi-bandit, and bandit settings. This is the first known result that provides such generalized guarantees for monotone and non-monotone up- concave functions over general convex sets. Finally, an important next step is the empirical validation of our theoretical guarantecs to explore the practical performance our framework real-world scenarios.
References
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Anmual Conference on Learning Theory, 2010.
Riccardo Aldrighetti, Daria Battini, Dmitry Ivanov, and Ienia Zennaro. Costs of resilience and disruptions in supply chain network design models: review and future research directions. International Journal of Production Economics, 235:108103, 2021.
Andrew An Bian, Baharan Mirzasoeimman, Joachim Buhmann, and Andreas Krause. Guaranteed Non- convex Optimization: Submodular Maximization over Continuous Domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, April 2017.
Yatao Bian, Joachim Buhmann, and Andreas Krause. Optimal continuous DR-uubmodular maximization and applications to provable mean field inference. In Proceedings of the 36th International Conference on Machine Learning, June 2019.
Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional Gradient Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2025.
Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. In International Conference on Machine Learning, pp. 814 823. PMLR, 2018a.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In International Conference Artificial Intelligence and Statistics, pp. 1896-1905. PMT.R, 2018b.
17

---

Published in Transactions on Machine Learning Research (12/2025)
Maryam Fazel and Omid Sadeghi. Fast first-order methods for monotone strongly dr-submodular maximization. In STAM Conference on Applied and Computational Discrele. Algorithms (ACDA23), pp. 169-179. STAM, 2023.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the siateenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385-394, 2005.
Shuyang Gu, Chuangen Gao, Jun Huang, and Weili Wu. Profit maximization in social networks and non-monotone DR-submodular maximization. Theoreticol Computer Science, 957:113847, 2023.
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Newral Information Processing Systems, 2017.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, ((3-4): 157-325, 2016.
Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. In Advances in Neural Information Processing Systems, 2016.
Soomin Lee, Angelia Nedić, and Maxim Raginsky. Coordinate dual averaging for decentralized online optimization with nonseparable global objectives. JEEE Transactions on Control of Network Systems, 5(1): 34-44, 2016.
Dan Li, Kerry D Wong, Yu Hen Hu, and Akbar M Sayeed. Detection, classification, and tracking of targets. IEEE signal processing magazine, 19(2):17-25 2002.
Yucheng Liao, Ynanyu Wan, Chang Yao, and Mingli Song. Improved projection-free online continuous submodular maximization. arXiv preprint arXiv:2305.184 18442, 2023.
Sivkumar Mishra, Debapriya Das, and Subrata Paul. A comprehensive review on power distribution network reconfiguration. Energy Systems, 8:227 284, 2017.
Siddharth Mitra, Moran Feldman, and Amin Karbasi. Submodular+ concave. In Advances in Newral Information Processing Systems, 2021.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp. 3616-3625, 2018.
Loay Mualem and Moran Feldman. Resolving the approximability of offline and online non non-monotone DR- submodular maximization over general convex sets. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, April 2023.
Arkadii Semenovich Nemirovski and David Berkovich füdin. Problem Complerity and Method Efficiency in Optimization. Wiley, 1983.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.1321: 2019.
Mohammad Pedramfar and Vaneet Aggarwal. From linear to linearizable optimization: A novel framework with applications to stationary and non-stationary dr-submodular optimization. In Advances in Newral Information Processing Systems, 2024a.
Mohammad Pedramfar and Vaneet Aggarwal. A unified framework for analyzing meta-algorithms in online convex optimization. arXio preprint arXiv:2402.00 08621, 2024b.
Mohammad Podramfar, Christopher John Quinn, and Vaneet Aggarwal. unified approach for maximizing continuous DR-submodular functions. In Thirty-seventh Conference on Neurol Information Processing Systems, 2023.
18

---

Published in Transactions on Machine Learning Research (12/2025)
Mohammad Pedramfar, Christopher J. Quinn, and Vancet Aggarwal. Uniform wrappers: Bridging concave to quadratizable functions in online optimization. In Advances in Newral Information Processing Systems, 2025.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Yuanyu Wan, Tong Wei, Mingli Song, and Lijun Zhang. Nearly optimal regret for decentralized online convex optimization. In The Thirty Seventh Annual Conference on Learning Theory, pp. 4862-4888. PMLR, 2024.
Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed average consensus with least-mean-square deviation. Journal of parallel and distribuled computing, 67(1):33 46, 2007.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Dula Engineering, 25(11):2483 2493, 2012.
Mingrui Zhang, Lin Chen, Hamed Hassami, and Amin Karbasi. Online continuous submodular maximization: From full-information to bandit feedback. In Advances in Neural Information Processing Systems, volume 32, 2019.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In International Conference on Machine Learning, pp. 26116-26134, 2022.
Qixin Zhang, Zengde Deng, Xiangru Jian, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Communication-effiicttt decentralized online continuous dr-submodular maximization. Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3330-3339, 2023.
Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint arXiv:2401.088 083330 2024.
Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, and Keqin Li. Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 22(51):1 42, 2021.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Tn Advances in neurol information processing systems, volume 23, 2010.
19

---

Published in Transactions on Machine Learning Research (12/2025)
A From concavity to upper-linearizabiity
In this section, provide alternative definition of upper-linearizabiliyy to further clarify the connection between this notion and that of concavity.
We start with a definition. Let F be a class of functions over a convex set K. C Rd and let L be a functional such that, for any f E and x K, Lixx an affine map over R4. Let us call such a functional a linear assignment for F.
Lemma 2. continuously differentiable function class consists only of concave functions if and only if it has linear assignment L such that, for all f E and x,y K. we have
- and Lxx(y)) 2 fly).
Proof. We provide the proof for the case where dim(K)- = d, the more general case is similar.
If f is concave, then we may choose the linear assignment (zx(x) = f(x) + (Vf(x), - x). The fact that (y) f(y) for all y follows from the definition of concavity.
On the other hand, if such a linear assignment exists for f F, then we have
fly) S Lzx(y) ()) Lsx(y) (0).
Since L is affine, the expression (yx - (() is linear. Therefore, there is vector A E Rd such that Lyxx(y) - (0) = y), Thus
f(y) S (yx = (xxxxx + (L/x(r)) - -sx(()) (L)x(x) L)xx(0)) = f(x) + (A,y x).
Thercfore, by setting h y and u1 = [|b]] E Sd, we see that
f(x + h) f(x) (Vf(z). (A (f-V)()), (A (A-V// Vf(x)
If we keep u fixed and take the limit ||b]| + O, the hand side of the above expression tends to zero, while the right-hand side remains constant. Thus, we that
A- Vf()),
If x E relint (K),, then there exists a d-dimensional ball around x that is contained in K. Thus, the above inequality holds for any choice of u. In particular, it also holds for uu which implies that (A- V 0, for all Sd. Hence, we conclude that A Vf(x). Therefore, for all x E relint(XC), we have
Lyx(x) (xx(x) (L)x((y) (0) - (L)x(xx) - ()) f(x) (V/(x), x),,
Hence f(y) S (V) x) for all x E (KC)nt((C) and y E K. Since f is continuously differentiable, this inequality holds for all x,y E and therefore concave.
Now we may phrase the definition upper- linearizability in a way that is similar to the above lemma. We can also see clearly why such function classes are called "upper-lincariablee.
Lemma 3. A function class F is called upper-lineurizable if and only if it has a linear assignment such that, for all f E F and x,y E K. we have
[xx(x) = f(((x)) and Lイx(x) 2 f(y),
for some function h : K. K.C. and some E (0.
The proof is clear from the definition.
20

---

Published in Transactions on Machine Learning Research (12/2025)
B Up-concave Functions are Linearizable
In this section, we provide for completeness that three cases of common up-coneave functions can be formulated as upper-linearizable functions, and we give the exact query algorithm to obtain estimates of g functions. We further show that given by these algorithms Lipschitz-contimmous, f L-smooth.
B.1 Monotone Up-concave optimization over general convex set
Following Lemma 1 by Pedramfar & Aggarwal 2024a), we note that monotone up-concave optimization over general convex set can be formulated an online maximization by quantization algorithm with trivial query (xx) x.
Lemma (Pedramfar & Aggarwal ).024a)) Let f [0, 11 - R de a non-negative monotone y-weakly up-concave function with curvature bounded by Then, for all x, [0, 1]4, we have
72
1 op tz [(y) - [(x)
1+ op ((VS(x), - x)).
7
where f is the gradient of f.
Algorithm BQK: Boosted Query Oracle for Monotone up-coneave functions general convex sets
Input: First order query oracle Q, point
Return: the output of the first-order query oracle Q at
B.2 Monotone up-concave optimization over convex set containing the origin
Following Lemma 2 by Pedramfar & Aggarwal 2024ab, we note that monotone up-concave optimization over convex set containing the origin can be formulated as an online maximization by quantization algorithm with non-trivial query BQMO, which is described in Algorithm
Lemma (Pedramfar & Aggarwal (2024a)) ). Let f [0, 11 + R be non-negative monotone y-weakly
up-comcave differentiable function and let F 10. + IR be the function defined by
F(x) = L'' (1 (1 (f(2 x f(0))dz.
(=-(=-1)
Then F is differentiable and, if the random variable 2 E [0, 1] is defined by the law
V2 E P(Z = / (u--1)
e- du,
(8)
then we have [Vf( = (x(x). Moreover, we have
(1 (1x) - s(x) 1-e77 V
7
Algorithm 7 BQMO: Boosted Query Oracle for Monotone up-concave functions over convex sets containing the origin
1: Input: First order qucry oracle Q, point x
Sample E [o, 1] according to Equation (8) Lemin
Return: the output of the first-order query oracle at x*x
In this case, = VF(x), h(x) = Id. Further, if ff is smooth, is Lipschitz continuous, as shown in the following Lemma.
Lemma (Theorem (iii,, Zhang et al. 2022 If is L-smooth and satisfies other assumptions of Lemma 7(1- " i.c., VF(x) is L'-Lipschitz continuous.
5 F is L' L'sothh,, where L' L 2ie
21

---

Published in Transactions on Machine Learning Research (12/2025)
B.3 Non-monotone up-concave optimization general convex set
Following Lemma 3 by Pedramfarr & Aggarwal 2024a), we note that non-monotone up-concave optimization over general convex set can be formulated an online maximization by quantization algorithm with non-trivial query EQN, described in Algorithm
Lemma 7 PPedramfar & Aggarwal (2024a)) ) Let f: 10, 1] R be a non-negative con-monotone continuous up-conoave differentiable function and let K. Define F (0, 1] IR. as the function
F(x) = /
3z(1 2)3 (5(2 * (x x + f(x)) dz,
Then F is differentiable and, if the random variable Z E [0, is defined by the law
V2 E [0.1] P(2 = J /
3(1 / du,
(9)
then have E [Vf 2 (x x) + x]] Vx()). Moreover, we have
1 - | f(y)
x +
S 3 -
v xx..
Algorithm BQN: Boosted Query Algorithm for non-monotone up-concave functions over general convex sets
1: Input: First order query oracle Q, point x
2: Sample E [0, 1] according to Equation
3: Return: the output of first-order query oracle Q at _ * (x x x
In this case, = VF(x), h(x) x xx+x Furthor, if f is L-smooth, Lipschitz continuous, as given in 2
the following Lemma.
Lemma (Theorem 18, Zhang et al. 2024 ) If f is L-smooth, L1 Lipischhttz and f satisfies assumptions in Lemma
V Fxx) is T-ssoothh and Lipschill confinmous.
C Proof of Theorem 1
Suppose for agent at round t, we denote the output of ((x as (xi.)) Let x"
argmax Dr EN (u), Ti {(m 1)K + 1,... mKK. By the definition of a-regret for agent j,
22

---

Published in Transactions on Machine Learning Research (12/2025)
have
T
N
E
1
E
[aff(xx)- (c(((((22)]
N
N T/K
Σ
Σ
[afi,((e') - ((x(((())))))
M=lteTm.
N T/K
Σ
B[[xx*
X/n De. (x2x))
TETm
T/K
Σ
Σ
Bl(x
x E 0r. x 1)]
TT
N T/K
Σ
[ x (x.; [
N
m=1 TET
8 T/K
B B
Xm (xhm))]
1=1 LETm
T/K
T/K
E
x x (x(t))
+E
Σ
(x
x Fr. (x
N
N
TETm
i=1
LET
P2
T/K
E
Σ
Σ TTT
xx
x (x
Ōe.i (x
(10)
where step (a) is because fe,''s are upper linearizable, step (b) is because (r,,(-) is unbiased, step (c) is due to the linearity conditional expectation, step (d) is due to law of iterated expectation, and step (e) rewrites (x* x as [[x" x + (x'. x and (x,((x as (x(,, - (x.. (x..))
As illustrated in step (e) in Equation TO total regret can be divided into three parts, Pt, Pg, P3, and provide respectivcly. In Section C.1 we introduce some auxiliary variables and lemuaa that are useful to the following proof.
upper bound for cach of these three parts with proof in the following sections,
C.2
C.1 Auxiliary variables and lemmas
In this section, introduce some auxiliary variables and lemmas to better present the proof of bound for each of the three parts of the total regret presented in Equation TO
Let yi = Vin = c, for any E [N], since Algorithm would only generate y for m = 2, ... ,.TKK Let
r = y y"m for any E [N] and m E [T/K]. For any m E [T/K], we denote the averages by:
ΣM
ΣN 8m.
Σ V and F.,
A. r
X
ym
N
N
N
N
There are two lemmas that would be useful to the proofs, and we provide proof of each of these in the following appendices.
Lemma 9. For any i E [N] and m E [T/K], Algorithm
ensures
|
2v + 2nKG.
23

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. See Appendix C.7 for complete proof for Lemma 9
Lemma 10. For any i [M] and m [T/K], Algorithm
ensures
N
VN + +233E)
(11)
1-12 A2
VN(3KKG + 2v
11
ym+tll²
and
(12)
12
(3nKG + +233e) (N N).
| x ll
3322++
(13)
X2
Proof. See Appendix C.8 for complete proof of Lemma I0
C.2 Bound of P1
By replacing (x* ( with [xx' - 9m) (8m - y'm) + +y x, Pi can be decomposed as:
T/K
T/K
E
Σ
(m yi (x +
Σ
Σ
Σ
F
X
(x,
mm
m=1.eTm
N T/K
Σ
Σ
Mm (x(x))
TE
N T/K Σ
N T/K 18 s'ull ΣΣΣ m= 1ETm
G
Σ
y m x
+ Pa
N
mi TETm
T/K Σ
N 1i5m - Fmm TV
3
+ Ra
N
m=1 EET
i=1
3nKG 2V
TGG
3 R4
(14)
A2
where step (a) follows from Cauchy-Schwarde inequality and the bound of (. function, step (b) follows from Arithmetic Mean-Quadratic Mean inequality and Lemma 1 and step (c) follows from Equation 11 in
Lemma 10
To attain upper bound on Ps, we notice that,
N
Ym+1-
N
m++1
N
Σ
Snn +1
Σ
1=1
JENr
EET
N
N
N
(a)
Σ
(x(
N
N
iml TET
N
9
7
(x.))
(15)
TT
where step (a) is because di 0 for any agent & Ns, and step (b) is because A1 1.
24

---

Published in Transactions on Machine Learning Research (12/2025)
Substituting Mm+1 using Equation 14 we have for any E [T/K],
mm+1 -8m+ -5m+1 8m++1
Tm+1 8m +
E Σ (x,)(mm)
(16)
N
because Fm-1 = 8m+1 mm+1-
By replacing 8m+1 with Equation
16 and then expand the equation, have
118 18m+1
x²1
16
Tm+1 + pm
+
(x.i(x
- x²
N
1=1
TE
N
= 118m x²1 x2122+2
Fm x
Σ (x,(((
TET
N
+ 2(ym x", Fm+1) +
Fm+1 +
(x,
(17)
N
1=1 TETm
Following Lemma 1 we deduce that for any m [T/K]:
18 m+1 - -x11 < lly - x"1 112 = Ily 1n - Vm+1 + sn - =x"1
lym+1 5m+1ll 2(y fym++1 8 Im+1. Fm+1 x") + 115 11 x=1
||r 112 1 2(r' Vm+1 - -x") + 11 - x1
where the last equality is due to the definition of r Omitting 1| x²1 on both sides and moving (V x*, r .rmta) the left, we have
Ynat x", Fm S
2 |1 ||rm 11?
1
(18)
Thus, we can bound the term (Am x", Fm+t) in Equation
17 as follows
N
(m x", Fmm+1)
Pmm - x", ,
N
1 N
N
(Im
y
mm+1+
m++1) +
N
m+1
x"
1=1
y
+
Σ
|rm+tall 112
2N
Kg + 2/
N 11
1
y
1
VN
2N
1=1
KT + 10n 12e
+ (1222222 2nKGV3e +3c
(19)
where step (a) replaces ym - (fm--- - + (ym+1 ymm 1 x*) and omits (y 3ym+1-90 y y S
0, step (b) due to Schwartz inequality and Equation (18). step (c) comes from Lemma
and
Arithmetic Mean-Quadratic Mean inequality, and step (d) follows from Equation 11 in Lemma 10
25

---

Published in Transactions on Machine Learning Research (12/2025)
Also, can bound the last term in Equation 17
follows
mm++1
7
(xm)
2
r m++1
2
+
Σ
B (x
N
1=1
i=1
TET
(b) 2 N
N
2K
| m++1
112
+
( 11
N
N
t=1 tETm
(c)
88
3e + nkG)
+ +222
24 + 10n) K² 16nKGV3e
(20)
where both step (a) and step (b) utilize Cauchy-Schwartz inequality and step (c) is due to Lemma and the bound of (+) functions.
Substitute Equation have
19 and Equation
20
into Equation
17 and taking expectation on both sides, we
2n
E
[|xx 8mm111
113]
<
E |||x*
9m
E [(x"
m, (x,)((
1ETm
1
(1212 + +2nn + 24c)
(21)
A2
(14
+ 24nKGV + 36c))
Moving terms to different sides in Equation
21 we have
N
T/K
E
E [xx"
8m. (x.:
N
im
m= 1 TET
T/K
119m
111
E |11 m+11 - 1+1mmm+1-- x1
21
T
18E
Tn + 12KGV33
K
7
T
1
(6nk2 10KGV3E + 12c
K
[
A2
(6)
2R
18cT
TrJKKG2 + 12TGV3E
11
1
12cT
GnTKG + 10TGV3E
(22)
1
Az
where the last inequality is due to E [[]ST)K+1 - x1 2 and - - x²1 < 4R2, which derived by combining 81 = K., K. and maxxex ||x||, and Cauchy-Schwarz Inequality.
Therefore, plugging the result for term E [[Pa] from Equation
22 into Equation
14 we have
Kg + +2
E|P < TG3
+
V
(23)
1
23R
183eT
+ +7BTTKG2 + 12TGBV +
nK
3
12eT
BnTKK² + 10TGV3e
(24)
X
K
26

---

Published in Transactions on Machine Learning Research (12/2025)
C.3 Bound of P2 Next, we bound P3 in
10
T/K
E
P2
10
3
X Xn Be. (x,))
m== tETm
T/K
| - 110
m= T
GB T/K
x -x
N
m= TET
i=1
& GB(NI/- (3V2++ 3gKG + 2/3c
(25)
A2
where step (a) is due Cauchy-Schwartz incquality, step (b) follows from the bound of gr.s()) functions, and step (c) uses the inequality 13 in Lemma 10
C.4 Bound of Pa
Recall that (.) are Li-Lissciitz continuous, i.c.,
(x)a)) - Dr, (x Il S L1|1x x2/11-
Thus, we have
N T/K
E
P3
10
3
E(x" x/, De. 0c. (xx(x
N
TE..
T/K E
x/n E [ōr. (xxm) E [ 1x
N
TET
T/K
B x (xhh)) (xh.))
m= TET
T/K M
M5
E [[[xx*
x/ (x(.)..)x(),) (x(,
m= TET
T/K Σ
E [[|x
x [11
x
N
IET
T/K
N ΣΣ
2I, R3
x
N
1= 1=1
S
2T, R3(N1/2 +1) (3V2c+
Kt + 2/33 1- Ag
(26)
where step (a) and (b) is due the law of iterated expectations, step (c) comes from Cauchy-Schwartz
inequality, step (d) follows from continuity of (.)(()) functions, step (e) follows from the bound on I. and Cauchy-Schwartz inequality, and step (f) is due to Equation (13 in Lemma 10
27

---

Published in Transactions on Machine Learning Research (12/2025)
C.5
Final Regret Bound
Plugging Equation
23
Equation
25
and Equation
26
into Equation 10 for any E [N], we have
2312
18E3T
E
RTa
TM + 13TG3V3
n
7
B
12ET
+9iTKG + 12TGV33
A2
niK
33/20+ (3nKG + 2/
+ G3(N1/2 +1)
1- +1)(3/2e+ (3V2E+
22, +1) +1)
(3nKG + 2V
1 1-
C.6 Number of Linear Optimization Oracle Calls
Finally, analyze the total number of linear optimization oracle calls for each agent In Lemma the term R₂= = ym++ - -EjEN, axpx
can be bounded as follows
(0)
R3² = ym+11 Σ
Oig x
<
2
y
m+11
Σ
aisSt
+
Σ
Σ
Bty
x
JEN.
JEN.
JEN,
JEN.
(6)
5
2
17
De. (x
+ Σ
ais
||
x 11
BE AE
jEN,
(c)
21 K2 6c
(27)
where both step (a) follows from Cauchy-Schwarde incquality, step (b) follows from Cauchy-Schwartz incquality and Line (10) in Algorithu I
From Equation
3 in Lemma in each block each agent i in Algorithm at most utilizes
27
Ily't1 - EJEN; ais dizx (1ly - ESEN, 22x//11= E) 1,
max
c
4e2
27R²
Rs RR c))
+ +1,1
max
462
27R
K2 + 62) K22 K2G G2 + 66 6)) +1.1)
max
4e2
27R
+ (en K2 + 5c) +
(28)
4.2
linear optimization oracle calls, where the last equality is due to the fact that (2
0.
Thus, by summing Equation
28 over blocks, we have that the total number of linear optimization steps
required by each agent Algorithm is at most
T/K 27TR² Σ m=l
K2T
1 <
8.5
ck
6
28

---

Published in Transactions on Machine Learning Research (12/2025)
C.7 Proof of Lemma 9
(a)
|| 1m+1ll ||
ymtill
I
Fm+1 Σ
aiszen
+
Σ
aisx
-m+11
JEN,
iEN
(6)
-
Σ
azjxm
m
Mm+1
(c)
Σ
Σ
Fijyn
71
m2 K
Σ
De. (xx(
iEN;
JEN
JEN
tm (m - 17K+1
(d)
a:j |
Sm + +n
JEN.
(c)
S 2v 3e + k
where step (a) comes from triangle inequality, step (b) follows by Lemma D update rule described in Algorithm 1
step (c) replaces y with
step (d) comes from triangle inoquality, and step (c) follows by Lemma
Moreover, if m I, we can verify that
||||| = ||o|| s 2v3c + 2nKG.
C.8 Proof of Lemma 10
To prove Lemma 10 we introduce additional auxiliary variables as follows:
X [x] N .d y'm lyti:... y E R.dd y'm = -Iih:... s R.v
and
I'm [rh: m
E Nd g'n
[ōr, (xx)): (x Nd.
(mm-1))K+
According to step 10 in Algorithm I for any m f...... T/K}, we have
ym+1 (A D) ngm
(A (A
Σ A I)
7gk
(29)
where the notation indicates the Kronecker product and denotes the identity matrix of size In the same manner, for any [T/K], we have
y y T'+t1 + y ym+
r' r + (A & 1)5 + 7g'
A k+1
Σ AA 2 m 7g
(30)
R=1
where the second equality follows the fact that r = y - y = 0. By the definition of 8m+1, for any m E [T/K], we have
11
Am :
@ 11)
(31)
N
where the second equality comes from A = IT.
A
29

---

Published in Transactions on Machine Learning Research (12/2025)
C.8.1 Proof of Equation 11
For any m [T/K], we have
11 1m+11=
mm+il??
31
11
8
8m+1|
N
30
11T
m-
69
I
r
+
11
Am-
60
78
N
N
k=1
11
11
A
m
2
I
FE+1
A
m
I
ngi
N
N
k=
11
T
11
m-
|
F
+
A m-
|1
N
N
VN + 2V
th (3 +
)2
where step (a) is due to triangle inequality, and step (b) due to Cauwhy-Schwartz inequality and triangle
inequality, step (c) comes from Lemma and the fact that vk E [m], 11 - A A s X2 m-- (see Mokhtari
ct al. 2018) for details), and step (d) is due to the property of geometric series.
By noticing 81- = y1 c, we complete the proof of Equation
11 in Lemnna 10
C.8.2 Proof of Equation 12
Similarly, for any m E -.. T/KK, we have
N
11sT
19
2
I
F'm
ym++l
N
11T
m-1
111
A
m
I
r/411
A
m-
ngl
ng.
N
N
WV
11T
m-1
111
A
m
8
rk41
+
Σ
Am
m-
2 ngi
+
||
N
N
k=
IAB
11T
1 T
A
-
||
+
A mm
|!gg/l + ||
N
N
VN + +2/3))
N
(3nKG + 2/3ce)
1-X2
where step (a) is due to triangle incquality, and step (b) due to Cauchy-Schwand incquality and triangle inequality, step (c) comes from Lemma and the fact that Vk E [m], ll 11
N A Am-
< X mm-k (see Mokhtari
ct al. 2018 for details), and stop (d) is due to the property of geometric scries.
When m = 1, &1 y = ΣjEN, F = c. Due to Line (10) in Algorithm we have
N
1 v
Σ JEN.
andy
y
Σ
D (xtma)
VNNKG
By noticing that VNnKG<
(3, 1-X2
we complete the proof of Equation
12
30

---

Published in Transactions on Machine Learning Research (12/2025)
C.8.3 Proof of Equation
13
For any m [T/K], we notice that
N
N
N
|x
xm1l
-
xx
Xm + Xm
Xm S
x
Xm + 21 X
im
mm0
s V N + N)
[VN+N)
Σ x &111?
(32)
Moreover, for any i E [N] and m E : T/K}, we have
|| 1mm=
1
xm 8m + 9m - y + y - x 12
(a)
1
3 Xm 8mll2 +31lmmm v/ +-111%m x,,"1*
IA
3
| Small 1| + 31 m y 11 + 3115 x 11?
N
18c 311 m y 113
where step (a) utilizes Cauchy-Schware inequality, step (b) utilizes Cauchy-Schward inequality and the
definition of Fm and Rm, and step (c) comes from Lemma When m 1, || x 12 0 I 18c 18c+31 +6l++1. 8m 8 11?
which leads us to conclude that for any m E [T/K],
8mm 12 < 18c + 3 - 82
Thus, for any m E [T/K], we have
Xm
12
(18 + 31 -
1=1
1/ 3v +
(0)
N
3
115 5
(6) < 3v
(3N + 2V3c)
(33)
A2
where step (a) is due to triangle inequality and step (b) follows by Equation in Lemma 10 Finally, by substituting Equation into Equation for any m [T/K], we have
N
x x (V N)
Σ x xmm
m
(3nKG 2V32)
< 33/2 +
(N3/2+N) N).
1 Xa
Bandit Feedback for Trivial Query Functions
In this section, we describe and discuss the variation DOCLO to handle bandit feedback for functions with trivial query oracle. The detailed implementation given the Algorithm / and here we provide proof of Theorem 3. This algorithm requires additional input from the user: smoothing parameter a, shrunk set Rs, linear space Lo-
31

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. Let A' denote Algorithm 2 and A denote Algorithm
1 Let fus denote 8-smoothed version of fi.s
Let x" E argmax م N (x) and x* E argmax xER,
2i t-l
T MN (x). Following our description
in Section 5.1 Algorithm 2 is equivalent to running Algorithm on fr, ô smoothed version of fe, over a shrunk set K.g-
By the definition of regret, we have
T
T Σ
E REd
E
[
E
[x)(x))
E
(b(x))))))))))))))))))))))))(( +
tvv))
5m1
N
N
1
E
(8))
ΣΣ
(es((((()))
N
E
P (m(x))))
Σ
(k)()(())++ + oV2) +o0))
N
f (x*) )
T
N
T N
ta
(x)
Σ [=
fes
(34)
Based on Lemma 3 proved by Pedramfar et al. (2023), we have (h(x()())) - -es Mi-Lisschitz continuous as well. Thus, we have
S 8M1, and feg is
(fe5(h(x)) + ov1) - (bxx)() s (Mxx) + ov.) - + (l,((((x))) fa,(((x))) s - 28M1.
(35)
Meanwhile, for the second part of Equation
34
we have
T N
N
ΣΣ
(x)
(x)
= max *ek.
t=1 1=1
-N8MT max
(x)
1=1
T
5) fes (11-))
x + 6 _c
- + max xeX
t=1
T
N
-NNMMT + max
fri
x p
(c x))
x
(c)
48M,R
2 -N8MT + max x
Σ
F()(x)
4R
NOMI
Σ
(xs(x))
where step (a) follows from Lemma by Pedramfar et al. 2023), and step (c) is due to the Mı-Lipschitz continuity of fi,'s.
step (b) follows from the definition of Cs,
Putting it herether with Equation 34 and Equation
35 we have
1 N 2N5MMT+ + (1 4R
NOMT)= -(3 4R r SM,T.
Ridd'
R.AAA
3+
32

---

Published in Transactions on Machine Learning Research (12/2025)
Thus we have
4R
RAA S Rind + 3
8M, T.
Assuming the zeroth order oracle is bounded by Bo, from Line 10 of Algorithm 2 that the gradient sample that is being passed to A is bounded by G $ Bo = 0(8 )). Substituting results from Theorem we see that.
+ nTKK5 ( +8T)
REA = =0 (R + +8T) =
Since we are doing same amount of infeasible projection operation and communication operation in Algorithm LOO calls and communication complexity for Algorithm 2
2
remains the same as Algorithm
E
Semi-Bandit Feedback for Non- Trivial Query Functions
To transform DOCLO into an algorithm that can handle semi-bandis feedback when we are dealing with functions with non-trivial queries, we pass I time horizon to DOCLO. In each of those I blocks, we consider functions
(faz) 150SS/LL.SS where fg. Li=(g- ft.. We note that in Algorithm for any x K. and 15 S T,L, we have Elfe, (x)] = (x), and if ft are differentiable, V (x)] = V (x). This way, the transformed algorithm only queries once at the point of action per block, thus semi-bandit.
Proof of Theorem Let A' denote Algorithm and A denote Algorithm 1 Following our description in Section 5.2.1. Algorithm is equivalent to running Algorithm on f (x) = J, aa - (x), an average fr, over block q. In consistence with Algorithm 3 description, we let zi denote the action taken by agent i at time-step whether it be &g. point of action selected by DOCLO, or 8 point of query selected by DOCLO. Thus, the regret of Algorithm over horizon T is
T
N (u)
E
R
A
1 E
max ueK.
ΣΣ> t=1==1
fed (zt)
N
j=1
L
1 Σ
E
Σ (u)(u)
N
ueK
I
T/L
qb.
N T/L
L
E
max nek
ΣΣΣ
Σ
fej (u)
Σ
Σ fzs
N
(1
N T/L
4l.
T/L
N T/L
1
E
ΣΣ
Σ
(fog(2))
(e,(
+ L
a max
ΣV
Pas(u) (u)
Σ Σ
(2,)
N
uek
j=1
g=1
(36)
Algorithm 3 ensures that in each block with a given g, there is only iteration where 2f * & otherwise 2 = . Since faj are Mı-Lipschitz continuous, we have ( fe,( I M - 8i1 < 2M, R where the second equation comes from the restraint on K. Since Es C K., we have max ||x|| S maxxex ||x|| = R. Thus, we have
N T/L
(0 (L- 1) 2M, 2NTMR
ΣΣ Σ
(1
fx,(
ΣΣ>
(37)
==
9=1
33

---

Published in Transactions on Machine Learning Research (12/2025)
The second part of Equation 36 can be seen as the regret of running Algorithm against (fax) 1S0ST/LAISSN over horizon T/L instead of T. We denote it with a,T/L. Applying Theorem we have
0 +++
nTKK2
E
R
o.T/T.
Putting together with Equation
36 and Equation 37 we have
R
E
+ LE R
L
which means
T -.) + +
E R
Based on the implementation described Algorithm g and make updates with infeasible projection operation every KL iteration. Thus, communication complexity for Algorithm 3 is O ) while LOO calls are 0 ((xL))
queries oracle every L iterations, and communicate
F Zeroth Order Full-Information Feedback for Non-Trivia Query Functions
In this scction, we describe and discuss the variation of DOCLO to handle zeroth-order full-information feedback for functions with non-trivial query oracle. The detailed implementation is given in the Algorithm ! table, followed by proof of Theorem 5] Per request of FOTZO, Algorithm || requires additional input from the user: smoothing parameter d < a, shrunk set Ks; linear space Co. In the case of non-trivial query oracle, h(-) is not necessarily an identity function. In the following, we give proof of Theorem
Proof of Theorem Let A' denote Algorithm and A denote Algorithm Let fis denote a 8-smoothed version of fex- Let x" E argmax Et= Σx (x) and & E argmax Ei=1 Σ j==1 (x) Following
our description in Section 5.2.2. Algorithm is equivalent to running Algorithm on fe 8 smoothed version of fa, over shrunk set Rs.
By the definition of regret, we have
T (x) - Σ
E Rhadd
E
R
E
Se (x(x)))
N
[=1 1=1
T N
T N
18))
Σ
(es()())))
N
T' N
E
(h)()())))
Σ
feg(h((())
N
1=1
T
T
N
+
(x²)
Σ
Pe. (x*)
(38)
1=1
Based on Lemma 3 proved by Pedramfar et al. (023), we have ( fi,, (h(x)))))) & 8M1 < 28M
It can be shown that the second part of Equation follows the same upper bound as Equation 35 Thus, putting it together, we have for Algorithm
the regret
34

---

Published in Transactions on Machine Learning Research (12/2025)
+ N (2N0MT++ + (1+ (1++7 4R NOMIT) Rid + 3 8M.T
4R
Rad
S Raa+
Assuming the zeroth order oracle is bounded by Bo, from Line 10 of Algorithm sample that is being passed to A is bounded by G k Bo = 0(8-)) Substituting results from Theorem we see that.
that the gradient
[ -0 1)TK5 + +88) +8)
Since we are doing same amount of infeasible projection operation and communication operation in Algorithm LOO calls and communication complexity for Algorithm f remains the same as Algorithm T
G Bandit Feedback for Non-trivial Query Function
In this section, we extend DOCLO over functions with nontrivial query oracle to handle bandit feedback, i.e., trivial query and zero-order foodback. We achieve this by applying FOTZO handle zero-order full-information leedback, then applying SFTT to transform the algorithm into trivial queries. In the following, we provide proof of Theorem
Proof of Theorem Let A' denote Algorithm 5 and A denote Algorithm 4 Following our description in Section 5.2.3 Algorithm is equivalent to rumning Algorithm 4 on fx. 2 (x), an average of fis over block q, where fis is d-smoothed version of Jr,g- In consistence with Algorithm description, we let x; denote the action taken by agent i at iteration t, whether it be & point of action sclected by DOCLO, or 9g, point of query selected by DOCLO. Thus, the regret of Algorithm over horizon T:
E
RhA
E
max nek
Σ
(u)
Σ>
1=1
T
1 T
N
E
a max
uek
T,
1
Σ
Pus(()
-
Σ
j=
1=1 j=1
N T/L
qL
T/L
E
at max uek
fus(u) ΣΣ
Σ
N
L
19441
N T/L
gh Σ
ΣΣ
(Fo - fi))
N
1)1+)
N T/L - -
N T/L
+L
a max Dek
fns(
(39)
1=1
j=1qm1
Algorithm 3 ensures that in each block g, there is only Based on Lemma 3 proposed by Pedramfar et al. (022 continuous, i.e,, (&t)) Ses(( & M restraint on K. Since Rs S JC, we have max maxxeR, ||x||
iteration where zi - + xj, otherwise x xj. fu, is M1 Mı-Lipscitz continuous if ft, is Mi-Lipscitz < 2.,RR where the second equation comes from the
< maxxex |x|| = R. Thus, we have
N T/L ΣΣ
ΣΣ Σ
(Fa)(&)) f()(xt))
(0 (L 1) 2M, 2NTMR
(40)
y= 1)
j=1
35

---

Published in Transactions on Machine Learning Research (12/2025)
The second part of Equation 39 can be seen as the regret running Algorithm 4 against (fat) 1S0ST/LISSSN
over horizon T/L instead of T. We denote it with Ru a,T/E Applying Theorem
5 we have
E
A a.T/L
- 0
nTKK 2
81
L
T,
Putting it together with Equation 36 and Equation 37
we have
E
R.
S.A
MTM R
+ LE
R i.A L.T/L
which means that
E R2 O
(
L
NTK 8T + + 7.
Based on the implementation described in Algorithm it queries oracle every L iterations, and communicate and make updates with infeasible projection operation every KL iteration. Thus, communccttion complexity for Algorithm is O R while LOO calls are 0 cKL )
((T
36


Reviews:
[{"review_id": "aZmGVsv3Be", "reviewer": "Reviewer_Quag", "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": "", "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 decentralized projection-free online convex optimization for DR-submodular functions. Previous work assumes 1-weakly DR-submodular functions with 0 in the feasible set, while this paper extends the analysis to the more general class of upper-linearizable functions, which includes many underexplored settings as special cases. To address this class of problems, the authors extend the centralized counterpart (Pedramfar & Aggarwal, 2024a) to the decentralized setting and provide corresponding theoretical guarantees. They further extend their approach to more general settings, such as the BCO setting and semi-bandit feedback.", "claims_and_evidence_yn": "Yes", "claims_explanation": "This paper is generally well-written, and I especially appreciate that the authors state all notations and claims in a clear and rigorous manner. I also went through the proof of the main theorem and did not find any significant errors. However, I did notice quite a few typos, which I have listed at the end.", "audience_yn": "Yes", "audience_explanation": "This paper studies decentralized DR-submotular OCO, which I think is a intereting topic and is relvernt to audience in online learning, distributed optimization, and submotular optimization.", "requested_changes": "This paper is well-written in general and I find the claims are rigorous. However, there exist lots of typos and some of which I listed below. More specfically:\n\nPage 5, Section 3.1: A set ${K}\\in \\mathbb{R}^d$ should be  ${K}\\subseteq \\mathbb{R}^d$ (also happens in footnote 2);\n\nPage 5, Section 3.1: Same paragraph, aff(D) and relint(D): should be  aff(K) and relint(K);\n\nPage 6, Line 1: \\forall x\\leq y \\in K;\n\nSection 3.3, paragraph 3: it should be \\hat{x} not x, as \\hat{x} is what is played by the learner;\n\nPage 8, paragraph 3, line 2: y' should be \\widetilde{y}\n\nPage 8, paragraph 3, line 4: unto->onto\n\nSection 4.1, paragraph 1: We should assume without loss of generality that T mod K =0; in line 2, i should be $i$\n\nAlgorithm 1, Step 1: mathbf{A} should be A\n\nTheorem 1: regret R should be \\mathcal{R}\n\nOther questions:\n\nIn this work, the authors consider both projection-free methods and dealing with broder class of dunctions (i.e., upper-linearizable). While it is a great contribution, I wonder if there is a deeper connection beteen projection-free and upper-linearizable functions? In other words, how do we deal with upper-linearizable functions in projection based setting? Are the oracle in the projection-free setting necessary for dealing with upper-linearizable functions?\n\nThe authors considered using one-point feedback to estimte the graident. In classical BCO (e.g., Flexman et al., 2005), people have also consdered using 2-point feedback. Can these methods also applible to this setting (Note that I am not asking for a full extension, a short discussion would be enough)? \n\nWhat is the paramter $\\beta$ in the upper bound in Thoerm 1?\n\nCould the authors define the function $h$ is a more clear way?\n\nUnder Table 1, could the authors add more discussion on the comparsion between guruantees of the proposed methods with that of the existing work?", "broader_impact_concerns": "N/A", "additional_comments": "I would like to apologize to the authors and AE for the delay in submitting my review.", "extra_scores": {}, "extra_text": {}}, {"review_id": "miN7dyOOVA", "reviewer": "Reviewer_81GD", "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": "", "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": "I reviewed this paper for its first submission, and felt that there were genuine technical contributions, but the technical presentation was quite lacking. Here I re-use parts of my original review that remain relevant, with updates made according to changes made by the authors in their revised version.\n\nThe broad context for this paper is online learning, where the typical \"regret\" notion is formulated using a sum of loss functions which are not convex, but fall into the category of \"weakly up-concave functions\". The particular focus of this paper is that of the *decentralized* setting, where there are $N$ separate agents, each of which receives their own (potentially adversarial) loss function at each round, and the ultimate goal is to obtain a small regret, having aggregated over all agents, noting that communication between agents is allowed.\n\nTo the best of my understanding, the main results are chiefly technical developments building directly upon existing work, in particular the algorithm design strategy of Pedramfar and Aggarwal (2024) used for \"upper-linearizable\" functions, originally in the centralized setting. Their results take the form of upper bounds on the (expected) regret associated with a general-purpose algorithm (their Algorithm 1), with different algorithmic settings used for different problem settings (e.g., different types of feedback availability), and they \"parameterize\" these bounds (see for example $\\\\theta$ in Table 1) to emphasize how regret bound and communication cost tradeoffs interact.\n\nIt should also be noted that another important trait of their approach is that it is \"projection free\"; the cost that is incurred instead is reflected via the \"LOO calls\" cost, namely the number of calls to a linear optimization oracle.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors are quite methodical in organizing their exposition of previous literature and describing its relation to the new results obtained in this paper. The overall structure of the paper is good, with a key proof sketch, and highlights of key results summarized in a concise and fairly effective way. I do feel that the technical exposition could be made more accessible, but overall, the authors have addressed the key points I raised in my review for the first version of the paper.\n\nBelow are just a couple minor comments.\n\n- In the key regret definition on p.7, $\\\\hat{\\\\mathbf{x}}\\_{t}^{i}$ appears (note the hat), but this notation is undefined. I know it appears later in Algorithm 1 and is probably just a placeholder, but some this should not be left without mention.\n\n- Regarding the following comment to the original submission, the authors responded to my comment, and there is a brief mention of the role of the two alphas in section 3.2, but I think this needs to be emphasized when defining the regret. *The notion of $\\\\alpha$-regret is given here without additional comment; does this $\\\\alpha$-based generality have any meaning in this paper whatsoever? It doesn't appear anywhere else. Furthermore, in the critical definition of upper-linearizable functions, once again \"$\\\\alpha$\" appears, but it is not clear if the authors intend this $\\\\alpha$ to align with the $\\\\alpha$ that appears in the regret definition. All this is sloppy formulation.*", "audience_yn": "Yes", "audience_explanation": "While somewhat technical and terse, there are many readers in de-centralized extensions of general-purpose online learning algorithms, and since the authors are quite methodical in describing what is technically new and of interest here, I believe there is an audience for this paper.", "requested_changes": "Please see the comments raised above. Overall, I think the re-submitted paper addresses the main concerns I had with the original submission.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QskNdjrHIY", "reviewer": "Reviewer_1K9M", "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": "", "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": "Recently, Pedramfar and Aggrawal (2024) introduced upper linearizable functions which generalizes a collection of functions including DR-submodular and concave functions. This paper, extends this work by introducing decentralized online algorithms for upper linearizable functions which are additionally more efficient by being projection-free. In particular, the algorithm involves a parameter $\\theta$ that enables the trade-off between regret vs communication complexity and calls to a linear optimization oracle. Extensions are also shown to settings with different feedback types.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides mathematical proofs for the theorems.", "audience_yn": "Yes", "audience_explanation": "I think the problem was not solved before and that the technical content is dense enough.", "requested_changes": "-I don't specialize in this area and did not find this paper easy to follow. Additionally, the paper's main contribution is technical and calibrating for the level of novelty requires good background in the existing literature. The paper has many technical definitions/terminology, e..g., up-concave, \\gamma-weakly monotone. These definitions are given only later. Even in the abstract, it was not clear what DR means.  \n\n-The algorithm makes call to linear optimization oracles, but aren't these calls expensive?\n\n-are simulation results important in this area? Would the paper benefit by showing empirical results that prove the performance of the algorithm? I did not see any included.\n\n-the action set is introduced before assumption 2 on page 5, but what is the action set?\n\n-were projection-based algorithms considered? Is there a theoretical or empirical result that makes it clear that projection-free algorithms would always be faster?", "broader_impact_concerns": "I don't think that there are any ethical concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)