Paper deep dive
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/15/2026, 8:18:24 AM
Summary
The paper introduces Dec-BFTRL, a decentralized online optimization algorithm for upper-linearizable payoffs under separation access, achieving square-root regret ($\widetilde{O}(\sqrt{T})$) for continuous DR-submodular maximization. It utilizes a first-order dual-state communication layer and local HybridNewton procedures to minimize BFTRL potentials, offering improved oracle efficiency compared to prior methods.
Entities (12)
Relation Signals (9)
Dec-BFTRL → achieves → square-root regret
confidence 95% · For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$.
Mohammad Pedramfar → affiliatedwith → Mila - Quebec AI Institute
confidence 95% · Mohammad Pedramfar ... Affiliation: Mila - Quebec AI Institute/McGill University
Vaneet Aggarwal → affiliatedwith → Purdue University
confidence 95% · Vaneet Aggarwal ... Affiliation: Purdue University
Mohammad Pedramfar → affiliatedwith → McGill University
confidence 95% · Mohammad Pedramfar ... Affiliation: Mila - Quebec AI Institute/McGill University
Yiyang Lu → affiliatedwith → Purdue University
confidence 95% · Yiyang Lu ... Affiliation: Purdue University
Dec-BFTRL → solves → DR-submodular maximization
confidence 95% · We study decentralized online optimization ... with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL)
Dec-BFTRL → uses → Separation Oracle
confidence 95% · decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access
Separation Oracle → comparedto →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$. Over $T$ rounds, each agent uses $T$ neighbor-mixing steps and $\widetilde O(T)$ separation-oracle calls. We give four wrapper instantiations covering three DR-submodular maximization problems.
Tags
Links
- Source: https://arxiv.org/abs/2608.30271v1
- Canonical: https://arxiv.org/abs/2608.30271v1
Trouble viewing inline? Open PDF directly →
Full Text
93,643 characters extracted from source content.
Expand or collapse full text
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization Yiyang Lu yiyanglu@purdue.edu Affiliation: Purdue University, West Lafayette, IN, USA Mohammad Pedramfar mohammad.pedramfar@mila.quebec Affiliation: Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada Vaneet Aggarwal vaneet@purdue.edu Affiliation: Purdue University, West Lafayette, IN, USA Abstract We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent’s played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of O~(T) O( T). Over T rounds, each agent uses T neighbor-mixing steps and O~(T) O(T) separation-oracle calls. We give four wrapper instantiations covering three DR-submodular maximization problems. 1 Introduction The demand for real-time decision-making in large-scale systems, such as autonomous robotic swarms and networked sensor arrays, has driven the rapid development of decentralized online optimization (Li et al., 2002; Xiao et al., 2007; Mokhtari et al., 2018). In these distributed frameworks, individual agents must collaboratively process continuous data streams and adapt to evolving environments without relying on a central coordinating server. A fundamental theoretical and practical problem arises when the time-varying global objectives are highly non-convex. Fortunately, a wide array of critical network applications, including dynamic pricing, recommendation algorithms, inventory routing, mean-field variational inference, and power grid reconfiguration (Bian et al., 2019; Aldrighetti et al., 2021; Ito and Fujimaki, 2016; Hassani et al., 2017; Mitra et al., 2021; Gu et al., 2023; Mishra et al., 2017), exhibit structural regularities, most notably the economic property of diminishing returns (DR). In these scenarios, the marginal benefit of an agent’s action naturally decreases as the global system approaches optimality, making cooperative online learning essential. Although much of the literature models such objectives through continuous DR-submodularity or weak up-concavity, upper-linearizability provides a broader abstraction for designing unified algorithms across non-concave function classes. Problem Setting and Metric. We consider N agents connected by a fixed, connected, undirected communication network. The agents share a compact convex action set K, which is accessed through a separation oracle and contains a known interior point. Before the game begins, an oblivious adversary fixes local payoff functions ft,j∈ℱ:t∈[T],j∈[N]\f_t,j :t∈[T],\,j∈[N]\, where j indexes the owner of a local payoff. At round t, each agent a selects an action xa,t∈x_a,t , receives feedback about its locally owned payoff ft,af_t,a (which is not necessarily incurred at xa,tx_a,t), and exchanges information once with its neighbors before the next round. Define the network-aggregate payoff t(x):=1N∑j=1Nft,j(x). F_t(x):= 1N _j=1^Nf_t,j(x). Although each agent receives only local feedback, its performance is measured using the aggregate payoff. For α∈(0,1]α∈(0,1], the per-agent network-aggregate expected α-regret is ℜαa(T):=[αmax∑t=1Tx∈t(x)−∑t=1Tt(xa,t)]. R_α^a(T):=E\! [α _x _t=1^T F_t(x)- _t=1^T F_t(x_a,t) ]. The expectation is over the randomness of the algorithm and its feedback. Section 2 specifies the feedback interface, action-set geometry, and network assumptions. Table 1: Summary of Decentralized Online Continuous DR-Submodular Maximization (D-OCSM) Algorithms. Let x¯∈ x denote the fixed feasible anchor used by Corollary 3, with ‖x¯‖∞<1\| x\|_∞<1. ‘(Smooth)’ means additional smoothness condition on the objective functions. Oracle-call counts follow the access model of each cited result, and SO and LOO calls should not be treated as equal-cost operations. The notation O~(T) O(T) suppresses logarithmic dependence on T and the set-conditioning parameters. Setting/Function Class Reference/Algorithm Approx. Ratio (α) logT(αCLOSE _T(α-Regret) logT _T(Comm.) Oracle Type Total Oracle Calls Monotone, 0∈0 11 1 The same results also work for general convex sets. DMFW (Zhu et al., 2021) 1−e−11-e^-1 1/21/2 5/25/2 LOO O(T5/2)O(T^5/2) Mono-DMFW (Zhang et al., 2023) 1−e−11-e^-1 4/54/5 11 LOO O(T)O(T) DOBGA (Zhang et al., 2023) 1−e−11-e^-1 1/21/2 11 Projection - DPOBGA (Liao et al., 2023) 1−e−11-e^-1 3/43/4 1/21/2 LOO O(T)O(T) DROCULO (θ=1θ=1) (Lu et al., 2025) 1−e−11-e^-1 1/21/2 11 LOO O(T2)O(T^2) DROCULO (θ=1/2θ=1/2) (Lu et al., 2025) 1−e−11-e^-1 3/43/4 1/21/2 LOO O(T)O(T) Corollary 2 (this work) 1−e−11-e^-1 1/21/2 11 SO O~(T) O(T) Non-monotone, General K DROCULO (θ=1θ=1) (Lu et al., 2025) 1−‖¯‖∞4 1-\| x\|_∞4 1/21/2 11 LOO O(T2)O(T^2) DROCULO (θ=1/2θ=1/2) Lu et al. (2025) 1−‖¯‖∞4 1-\| x\|_∞4 3/43/4 1/21/2 LOO O(T)O(T) Wan et al. (2026) 1−‖¯‖∞4 1-\| x\|_∞4 3/43/4 11 LOO O(T)O(T) Wan et al. (2026) (Smooth) 1−‖¯‖∞4 1-\| x\|_∞4 2/32/3 11 LOO O(T)O(T) Corollary 3 (this work) 1−‖¯‖∞4 1-\| x\|_∞4 1/21/2 11 SO O~(T) O(T) Non-monotone, Down-closed K Wan et al. (2026) 1/e1/e 3/43/4 11 LOO O(T)O(T) Wan et al. (2026) (Smooth) 1/e1/e 2/32/3 11 LOO O(T)O(T) Corollary 4 (this work) 1/e1/e 1/21/2 11 SO O~(T) O(T) Related Work. Recent development in decentralized online continuous submodular maximization has produced several distinct regret-communication-computation tradeoffs (Zhu et al., 2021; Zhang et al., 2023; Liao et al., 2023; Lu et al., 2025; Wan et al., 2026). Early algorithms focused on monotone continuous DR-submodular rewards, while Lu et al. (2025) provided a decentralized framework for the broader upper-linearizable interface. Recent reductions sharpen several application-specific results for non-monotone continuous DR-submodular rewards (Wan et al., 2026), specifically for smooth objectives. In the centralized setting, upper-linearizable algorithms and uniform wrappers provide the translation from online linear regret to a range of non-concave payoff models (Pedramfar and Aggarwal, 2024; Pedramfar et al., 2025), and are recently extended to down-closed DR-submodular maximization (Lu et al., 2026). For online convex optimization (OCO) over difficult action sets, another line of work replaces Euclidean projection with weaker action-set access (Hazan and Kale, 2012; Garber and Hazan, 2016; Levy and Krause, 2019; Mhammedi, 2022; Garber and Kretzu, 2022; Mhammedi, 2025) and proposed projection-free algorithms. Of particular relevance, Mhammedi (2025) combine a separation-to-gauge reduction with a centralized Taylor Barrier-ONS analysis. This naturally motivates an oracle-specific question: What performance can decentralized online upper-linearizable optimization achieve under separation access, and what is the resulting application in Decentralized Online Continuous Submodular Maximization? We attain O~(T) O( T) regret, O(T)O(T) communication, and O~(T) O(T) separation-oracle calls per agent under the assumptions made precise in Section 2. Table 1 reports the regret, communication, and action-set-oracle calls of the relevant methods under their respective access models. Because SO and LOO calls are distinct operations, the table compares asymptotic resource profiles rather than equal-cost operations or wall-clock performance. For a detailed discussion on oracle efficiency we refer to Remark 1 and the relevant projection-free OCO literature. Contributions. We introduce Dec-BFTRL, a decentralized barrier-FTRL algorithm with a first-order dual-state communication layer for online upper-linearizable maximization under separation access, and prove O~(T) O ( T ) per-agent network-aggregated expected α-regret. Over T rounds, each agent uses T neighbor-mixing operations, communicates one d-dimensional state per operation, and makes O(Tlog(κT))O(T (κ T)) calls to the action-set separation oracle. The number of HybridNewton updates is explicitly bounded for the controlled accuracy schedule. The general payoff theorem yields square-root-T α-regret guarantees for three well known DR-submodular maximization problems. Technical Novelties. Our main challenges and technical novelties are as follow: 1. A first-order communication interface for a curved local map. The barrier-FTRL map (4) has agent-dependent curvature, so directly coordinating Newton updates would require more than first-order messages (e.g., the Hessian). Our design instead communicates only the dual state through (5), and the exact-average identity (8) makes this state sufficient to define the hypothetical network average problem, while every Hessian and Newton step remains local. 2. Coupling row-wise network mixing with barrier-FTRL stability. The network-aggregate metric evaluates every payoff owner’s function ft,jf_t,j at one specified agent a’s action, whereas the surrogate analysis initially controls each payoff at its owner’s iterate. To bridge this gap, we retain the cumulative row-wise mixing coefficient Ma(W)M_a(W) (Lemma 2) and use it to control the specified agent’s dual-state disagreement (Lemma 3). Strong convexity of the barrier-FTRL potentials and stability of the composed payoffs ft,j∘hf_t,j h then convert this row-wise dual control into feasible-action disagreement and bound the resulting owner-action cross terms (Lemma 4, 7 and (19)). Without this row-wise refinement, a direct global-ℓ2 _2 consensus bound would yield square-root regret with a N N factor in place of 1+logN1+ N. 3. Controlled approximate local barrier-FTRL potential solver: Exact local minimization is unrealistic, but uncontrolled errors could accumulate linearly with the horizon. The HybridNewton subroutine uses the self-concordant stopping rule (22), and its computable Newton-decrement test guarantees the Euclidean error bound (Lemma 11). The accuracy schedule in Lemma 6 keeps the cumulative error bounded by ET≤RE_T≤ R, while the warm-start analysis yields the finite iteration bound given by Proposition 1. 2 Preliminaries 2.1 Notations Let =(,ℰ) G=(V,E) denote an undirected communication network of N agents, where =1,…,NV=\1,…,N\ is the set of agents and ℰE is the set of communication links. We associate the network with a mixing matrix W∈ℝN×NW ^N× N, specified formally in Assumption 2. We denote the Euclidean norm by ∥⋅∥2\|·\|_2. For a positive definite matrix Σ∈ℝd×d ^d× d, the induced local norm is ‖x‖Σ:=x⊤Σx\|x\|_ := x x. We write 2:=u∈ℝd:‖u‖2≤1B_2:=\u ^d:\|u\|_2≤ 1\ for the closed Euclidean unit ball. 2.2 Definitions Separation oracle access and gauge projection. Given a closed convex set ⊆ℝdK ^d and a query point x∈ℝdx ^d, a separation oracle (SO) Sep(x)Sep_K(x) either certifies that x∈x or returns a nonzero normal vector s∈ℝds ^d such that ⟨s,x−z⟩>0,∀z∈ s,x-z >0,∀ z , and we call s a hyperplane separating x from K. We say an algorithm is under separation access when the algorithm can access the action set via a separation oracle, and when such separation oracle is indeed efficient over the action set. Remark 1 (Two access oracle models). A separation oracle (SO) and a linear optimization oracle (LOO) expose complementary forms of action-set access, so their call counts do not by themselves determine computational cost. Separation is particularly natural for sets described by convex inequalities or intersections of simple constraints, where an infeasible query can be separated by returning a violated constraint and its normal, whereas linear optimization requires optimizing over the full intersection. For example, for a full-dimensional packing region =x∈[0,1]d≤b,A≥0K=x∈[0,1]^d≤ b,A≥ 0, with a known strictly feasible point, an SO scans the box and resource constraints and returns a violated inequality, while an LOO solves the associated packing linear program. In matrix domains, separation over the spectral-norm ball requires only a leading singular-vector pair, whereas linear optimization generally requires a full-rank SVD; the ordering reverses for the nuclear-norm ball (Garber and Kretzu, 2022). Thus neither oracle model uniformly dominates the other. Under Assumption 1, a separation oracle for K also gives one for the translated set =−x0C=K-x_0 by translation. For the closed convex set C containing the origin in its interior, the Minkowski gauge function is γ(u):=infa>0:u∈a, _C(u):= \a>0:u∈ aC\, and gauge distance is defined as S(u):=max0,γ(u)−1S_C(u):= \0, _C(u)-1\. Using the gauge function and gauge distance, the exact gauge projection scales an infeasible point along the ray from the origin: p(u):=u1+S(u)∈,w(u):=x0+p(u)∈. p_C(u):= u1+S_C(u) , w_K(u):=x_0+p_C(u) . Thus a feasible point is unchanged, while an infeasible point is scaled to the boundary. Specifically, we use the SO-based gauge subroutine of Mhammedi (2025), GaugeDist, which uses an approximate gauge projection controlled by a precision parameter εgau _gau, rather than the exact gauge projection. For completeness, we include the implementation along with useful properties and SO-complexity in Appendix A, and discuss how it interacts with our main algorithm in Section 3.1. Linearizable Framework and Uniform Wrappers. Pedramfar and Aggarwal (2024) first develops the linearizable framework in centralized setting, providing a clean reduction from online linearizable optimization to online linear optimization. Pedramfar et al. (2025) further refines the reduction process by formulating the uniform wrappers for action, query and function. Pedramfar and Aggarwal (2024) also identifies two well known problems, namely monotone and non-monotone DR-submodular functions over general convex set as application of linearizable framework, which is later extended to non-monotone DR-submodular maximization over down-closed convex set with better approximation ratio and regret guarantee (Lu et al., 2026). Moving beyond centralized setting, Lu et al. (2025) uses linearizable framework as engine for decentralized setting and obtain results for the former two classes of DR-submodular maximization problems. Similarly, this work leverages it as a powerful interface so that as more function classes being added to the linearizable framework (Lu et al., 2026), this will automatically create a compounding impact with our meta-algorithm to unlock online decentralized optimization of such functions. We formally introduce the definition of upper-linearizable functions. Definition 1 (Upper-linearizable function). A function class ℱF over K is upper-linearizable with structural parameters (α,β)∈(0,1]×(0,∞)(α,β)∈(0,1]×(0,∞) and action map h:→h:K if there exists an linearization proxy :ℱ×→ℝd g:F×K ^d such that, for every f∈ℱf and w,y∈w,y , αf(y)−f(h(w))≤β⟨(f,w),y−w⟩.α f(y)-f(h(w))≤β g(f,w),y-w . (1) Following Pedramfar et al. (2025), we associate the upper-linearizable representation and its base oracle with a fixed abstract uniform wrapper =(act,qry)W=(W^act,W^qry). For each f∈ℱf , let fO_f denote the base oracle22 2 A base oracle may, for example, be a first-order oracle returning a possibly noisy gradient estimate, or a value oracle returning a possibly noisy function value. through which f is accessed. The action component is act=hW^act=h, while the query component transforms fO_f into a wrapped vector-valued oracle ^f:=qry(f). O_f:=W^qry(O_f). When invoked at an internal point w, the wrapped oracle may use auxiliary randomness, query fO_f at one or more feasible points potentially different from both w and h(w)h(w), and transforms the resulting responses into a feedback vector. The wrapper pair associated with each function class and base oracle combination is specified in the applications. Online Protocol. We consider an oblivious adversarial model. Before the game begins, the adversary fixes a sequence of local payoff functions ft,j∈ℱ:t∈[T],j∈[N]\f_t,j :t∈[T],\,j∈[N]\, where j indexes the owner of a local payoff. The future payoff functions and their oracle responses are not revealed to the agents in advance. At round t, each agent a∈[N]a∈[N], using only the information available before the current feedback is observed, computes an internal feasible point wa,t∈w_a,t and plays act(wa,t)=h(wa,t).W^act(w_a,t)=h(w_a,t). The agent then obtains access to the base oracle t,a:=ft,aO_t,a:=O_f_t,a, invokes the corresponding wrapped oracle at wa,tw_a,t, and receives qa,t∼^t,a(wa,t),q_a,t O_t,a(w_a,t), where ^t,a:=qry(t,a). O_t,a:=W^qry(O_t,a). The randomness in qa,tq_a,t may arise from the base oracle, the Query Wrapper, or both. Its required conditional mean and boundedness properties are given in Assumption 3. Regret. Under such protocol, the action xa,tx_a,t appearing in the regret definition from the Introduction is instantiated as xa,t=act(wa,t)=h(wa,t)x_a,t=W^act(w_a,t)=h(w_a,t), and the α-regret33 3 The coefficient α first appears as a structural parameter of the upper-linearization inequality, and it is not a tuning parameter of Dec-BFTRL. The payoff-lifting argument shows that this same coefficient scales the hindsight benchmark in the resulting regret guarantee, which motivates the common notation Rαa(T)R_α^a(T). of agent a becomes ℜαa(T):=[αmax∑t=1Ty∈t(y)−∑t=1Tt(h(wa,t))]. R_α^a(T):=E\! [α _y _t=1^T F_t(y)- _t=1^T F_t\! (h(w_a,t) ) ]. (2) where t(⋅)=1N∑j=1Nft,j(⋅), F_t\! (· )= 1N _j=1^Nf_t,j\! (· ), so the action-agent index a is held fixed while j ranges over all local-payoff owners, including j≠aj≠ a. Remark 2 (Role of the approximation coefficient). Even in the centralized offline setup, DR-submodular maximization could be NP-hard. As an example, Bian et al. (2017) shows that for monotone DR-submodular functions f over convex set containing the origin K, it is NP-hard to find any point any point x∈x such that f(x)f(x) is at least (1−e−1+ϵ)(1-e^-1+ε) times the optimal value for any ϵε. There are polynomial times algorithms that achieve the ratio of 1−e−11-e^-1, and such a number is referred to as the approximation coefficient, indicating the proportion of the optimal value we can achieve with polynomial time algorithms. 2.3 Assumptions Assumption 1 (Translated geometry and separation access). The feasible set ⊆ℝdK ^d is compact and convex. A point x0∈int()x_0 (K) and radii 0<r≤R0<r≤ R are known such that, with :=−x0C:=K-x_0, r2⊆R2.rB_2 RB_2. The set is accessed through a separation oracle for K and hence, by translation, for C. We set κ:=R/rκ:=R/r. Assumption 2 (Network topology and communication matrix). The communication network =(,ℰ) G=(V,E) is undirected and connected. Agents form convex combinations of their local states using a matrix W∈ℝN×NW ^N× N satisfying: 1) Graph compatibility: Wij=0W_ij=0 whenever i≠ji≠ j and i,j∉ℰ\i,j\ ; 2) Symmetry and double stochasticity: W=W⊤W=W , Wij≥0W_ij≥ 0, and W=W1=1; 3) Contraction: with J:=⊤/NJ:=11 /N, ρ:=‖W−J‖2<1.ρ:=\|W-J\|_2<1. Thus ρ is the disagreement contraction factor and 1−ρ1-ρ is the absolute spectral gap. Assumption 3 (Conditionally unbiased bounded feedback). Let ℱt−F_t^- denote the sigma-field generated by the fixed payoff sequence and all algorithmic and oracle randomness revealed before the round-t wrapped-oracle responses are generated, including the current wrapper inputs wa,ta=1N\w_a,t\_a=1^N. For every agent a and round t, the wrapped feedback vector satisfies [qa,t∣ℱt−]=(ft,a,wa,t),‖qa,t‖2≤G.E[q_a,t _t^-]= g(f_t,a,w_a,t), \|q_a,t\|_2≤ G. Assumption 4 (Uniform composed-payoff stability). There is a horizon-independent constant Lϕ≥0L_φ≥ 0 such that, almost surely, for every round t, payoff owner j, and w,v∈w,v , |ft,j(h(w))−ft,j(h(v))|≤Lϕ‖w−v‖2. |f_t,j(h(w))-f_t,j(h(v)) |≤ L_φ\|w-v\|_2. (3) Equivalently, each composed payoff ft,j∘hf_t,j h is uniformly LϕL_φ-Lipschitz on K. 3 Decentralized Barrier Follow the Regularized Leader (Dec-BFTRL) Having specified the online protocol and assumptions, we now present Dec-BFTRL and its main guarantee. The method combines three components: GaugeDist uses separation access to form a feasible wrapper input and the associated gauge correction; the agents convert their wrapped feedback into local surrogate losses and exchange only a single dual state; and HybridNewton locally computes an approximate minimizer of the resulting barrier-FTRL potential. Thus all feasibility and second-order computations remain local, while the network interaction is confined to one dual-state exchange per round. Subsection 3.1 gives a round-by-round description of the method and its subroutines, while Subsection 3.2 states the main regret guarantee and provides a proof sketch. The supporting intermediate results and complete proof are deferred to Section 4. 3.1 Main Algorithm At the beginning of round t, each agent a holds two local states. The dual state θa,t∈ℝd _a,t ^d contains a mixed history of earlier surrogate losses and is the only state communicated to neighboring agents. The primal state ua,t∈int(R2)u_a,t (RB_2) is kept locally and approximately minimizes the BFTRL potential Ψa,t(u):=−νlog(R2−‖u‖22)+μT2‖u‖22+⟨θa,t,u⟩. _a,t(u):=-ν \! (R^2-\|u\|_2^2 )+ _T2\|u\|_2^2+ _a,t,u . (4) and we denote its unique exact minimizer by ua,t⋆:=argminu∈int(R2)Ψa,t(u).u_a,t := _u (RB_2) _a,t(u). The barrier and quadratic terms together make Ψa,t _a,t strongly convex, with parameter mT:=μT+2νR2.m_T:= _T+ 2νR^2. Initially, θa,1=0 _a,1=0 and ua,1=0=ua,1⋆u_a,1=0=u_a,1 . More generally, (θa,t,ua,t)( _a,t,u_a,t) depends only on feedback from rounds preceding t. Round t produces (θa,t+1,ua,t+1)( _a,t+1,u_a,t+1), which is used at round t+1t+1. Algorithm 1 summarizes this recursion. Algorithm 1 Dec-BFTRL: decentralized barrier-FTRL under separation access 0: Horizon T; separation-oracle access to K; known x0,r,Rx_0,r,R; symmetric doubly stochastic mixing matrix W; abstract uniform wrapper =(act,qry)W=(W^act,W^qry); parameters ν≥1ν≥ 1, μT>0 _T>0; local solve tolerances εa,ta∈[N],t=2,…,T\ _a,t\_a∈[N],\,t=2,…,T 1: Set ←−x0C -x_0 and εgau←1/T _gau← 1/T 2: For every agent a∈[N]a∈[N], initialize θa,1←0 _a,1← 0 and ua,1←0u_a,1← 0 3: for t=1,…,Tt=1,…,T do 4: for every agent a∈[N]a∈[N] in parallel do 5: (Sa,t,sa,t)←GaugeDist(,ua,t,εgau,r)(S_a,t,s_a,t)← GaugeDist(C,u_a,t, _gau,r) 6: pa,t←ua,t/(1+Sa,t)p_a,t← u_a,t/(1+S_a,t) and wa,t←x0+pa,tw_a,t← x_0+p_a,t 7: Play xa,t←act(wa,t)=h(wa,t)x_a,t ^act(w_a,t)=h(w_a,t); 8: Invoke the wrapped oracle qry(t,a)W^qry(O_t,a) at wa,tw_a,t and receive qa,tq_a,t 9: Let ℓa,t←−qa,t _a,t←-q_a,t and ℓ~a,t←ℓa,t−⟨ℓa,t,ua,t⟩<0⟨ℓa,t,pa,t⟩sa,t _a,t← _a,t-1\! \ _a,t,u_a,t <0 \ _a,t,p_a,t s_a,t 10: Exchange the dual state θa,t _a,t with neighbors and update θa,t+1←∑b=1NWabθb,t+ℓ~a,t _a,t+1← _b=1^NW_ab _b,t+ _a,t 11: if t<Tt<T then 12: Form Ψa,t+1 _a,t+1 from (4) 13: ua,t+1←HybridNewton(Ψa,t+1,ua,t,εa,t+1) u_a,t+1← HybridNewton( _a,t+1,u_a,t, _a,t+1) 14: end if 15: end for 16: end for Gauge projection. The primal state ua,tu_a,t lies in the simple barrier domain R2RB_2, but it need not belong to the translated feasible set =−x0C=K-x_0. The call to GaugeDist returns an approximate gauge distance Sa,tS_a,t and an approximate subgradient sa,ts_a,t, moderated by the gauge precision parameter εgau _gau. Because Sa,tS_a,t upper bounds the true gauge distance, the radial scaling pa,t=ua,t1+Sa,tp_a,t= u_a,t1+S_a,t belongs to C, and therefore wa,t=x0+pa,tw_a,t=x_0+p_a,t belongs to K. The vector sa,ts_a,t is retained for the surrogate-loss correction in the next step. This construction allows the barrier-FTRL update to operate on a Euclidean ball while producing a feasible input for the Action Wrapper. The corresponding feasibility, approximation, and separation-oracle guarantees are established in Section 4.1. Feedback and surrogate loss. After constructing wa,tw_a,t, the agent plays xa,t=act(wa,t)=h(wa,t)x_a,t=W^act(w_a,t)=h(w_a,t) and invokes the wrapped oracle qry(t,a)W^qry(O_t,a) at wa,tw_a,t, receiving the payoff-side vector qa,tq_a,t. Because the barrier-FTRL update is written as a loss-minimization procedure, the agent first sets ℓa,t=−qa,t _a,t=-q_a,t. It then combines ℓa,t _a,t with the gauge information pa,tp_a,t and sa,ts_a,t to form the corrected surrogate loss ℓ~a,t _a,t, and the correction is activated only when ⟨ℓa,t,ua,t⟩<0 _a,t,u_a,t <0. Its role is to relate linear loss at the feasible point wa,tw_a,t to a bounded linear surrogate evaluated at the internal state ua,tu_a,t. The precise comparison inequality and norm bound for ℓ~a,t _a,t are given in Section 4.1. The implementation and query cost of the wrapped oracle are specified separately for each application. Communication and dual update. Once the current surrogate has been formed, each agent exchanges only its dual state θa,t _a,t with its neighbors. Although this exchange appears after the feedback step in Algorithm 1, the communicated vector is the pre-update state and therefore contains only information from earlier rounds. Agent a first mixes these dual states and then injects its current local surrogate: θa,t+1=∑b=1NWabθb,t+ℓ~a,t. _a,t+1= _b=1^NW_ab _b,t+ _a,t. (5) Thus the feedback received at round t affects the primal state used at round t+1t+1, not the action already played at round t. Graph compatibility of W makes the displayed sum implementable through neighbor communication. No primal iterate, feasible point, Hessian, or Newton information is exchanged. Section 4.2 analyzes the evolution of the average dual state and controls disagreement through the network spectral gap. HybridNewton update. The new dual state θa,t+1 _a,t+1 defines the next local potential Ψa,t+1 _a,t+1. Agent a warm-starts HybridNewton from ua,tu_a,t and computes an interior point satisfying ‖ua,t+1−ua,t+1⋆‖2≤εa,t+1.\|u_a,t+1-u_a,t+1 \|_2≤ _a,t+1. The logarithmic barrier keeps the Newton iterates inside R2RB_2, while strong convexity converts the solver’s Newton-decrement stopping condition into the stated Euclidean accuracy. The solver first uses damped Newton steps and then switches to full Newton steps once it enters the local convergence region. This computation is entirely local, and the returned point ua,t+1u_a,t+1 begins the next round. The post-round solve is omitted when t=Tt=T, since no subsequent action is needed. Section 4.3 establishes the accuracy guarantee and iteration complexity. Each online round requires one exchange of a d-dimensional dual state per agent, and all gauge computations, wrapped-oracle operations, and HybridNewton updates remain local. 3.2 Main Guarantee Let δ:=1−ρ,δ:=1-ρ,, G~:=2κG G:=2κ G. For main guarantee, we set ν=1ν=1, μT=G~R2T(1+1δ) _T= GR 2T (1+ 1δ ), and mT=μT+2R2m_T= _T+ 2R^2. We use gauge precision εgau=1/T _gau=1/T and local solve inaccuracy tolerances εa,1:=0 _a,1:=0, and εa,t:=RT _a,t:= RT for 2≤t≤T2≤ t≤ T. For each agent a∈[N]a∈[N], define its row-mixing coefficient Ma(W):=∑k=0∞∑b=1N|(Wk)ab−1N|.M_a(W):= _k=0^∞ _b=1^N |(W^k)_ab- 1N |. (6) Assumption 2 ensures that Ma(W)<∞M_a(W)<∞. Define also ℬT:=β[3GR+G~R+logT+G~R2T(1+1δ)].B_T:=β [3GR+ GR+ T+ GR 2T (1+ 1δ ) ]. Theorem 1 (Dec-BFTRL: per-agent regret and total SO calls). Let t(⋅)=1N∑j=1Nft,j(⋅) F_t\! (· )= 1N _j=1^Nf_t,j\! (· ). Suppose every ft,jf_t,j belongs to the common (α,β)(α,β)-upper-linearizable class of Definition 1, equipped with the fixed Action and Query Wrappers used by Algorithm 1. Suppose Assumptions 1, 2, 3, and 4 hold with constants G>0G>0 and Lϕ≥0L_φ≥ 0. For every agent a∈[N]a∈[N], running Algorithm 1 with the above parameters choices ensures [αmax∑t=1Ty∈t(y)−∑t=1Tt(h(wa,t))]≤ℬT+2LϕR(2+κ)+Lϕ(1+κ)RTδ2(1+δ)(Ma(W)+1δ). \! [α _y _t=1^T F_t(y)- _t=1^T F_t\! (h(w_a,t) ) ]≤B_T+2L_φR(2+κ)+L_φ(1+κ)R Tδ2(1+δ) (M_a(W)+ 1δ ). (7) and each agent makes at most T(1+⌈log2(4κ2T)⌉)T (1+ _2(4κ^2T) ) total calls to the action-set separation oracle. This count excludes any action-set-oracle calls, if any, made by an application-specific wrapper. Section 4.2 shows that Ma(W)=O(1+logN1−ρ)M_a(W)=O\! ( 1+ N1-ρ ). Therefore, Theorem 1 implies for every agent a ℜαa(T)=O(βlogT+[βκGR+Lϕ(1+κ)R(1+logN)]T1−ρ)=O~(T) R_α^a(T)=O\! (β T+ [βκ GR+L_φ(1+κ)R(1+ N) ] T1-ρ )= O( T) 4 Analysis Throughout this section, we work under the hypotheses and parameter choices of Theorem 1. All pathwise statements are understood on the probability-one event on which the almost-sure feedback bounds in Assumption 3 hold simultaneously for all agents and rounds. In the Analysis, we extend the parameter setup and notations used in section 3.2. We defer the detailed proof of each Lemma in this section to the Appendices. 4.1 Gauge Projection and Surrogate Loss Lemma 1 provides all the necessary information we need from the gauge projection subroutine, and its proof utilizes Lemma 8 and Lemma 9 in Appendix A. Lemma 1 (Gauge projection and surrogate bound). For every payoff owner j and round t, the point constructed by Algorithm 1 satisfies wj,t∈w_j,t , and ‖ℓ~j,t‖2≤G~.\| _j,t\|_2≤ G. Moreover, for every v∈v , ⟨ℓj,t,wj,t−(x0+v)⟩≤⟨ℓ~j,t,uj,t−v⟩+2GRT. _j,t,w_j,t-(x_0+v) ≤ _j,t,u_j,t-v + 2GRT. 4.2 Network Mixing and Dual States Recall from (6), Ma(W)=∑k=0∞∑b=1N|(Wk)ab−1N|.M_a(W)= _k=0^∞ _b=1^N |(W^k)_ab- 1N |. Lemma 2 is a useful technical lemma for the row mixing operation of the communication matrix and does not concern the dual state. Lemma 2 (Row mixing). For every agent a∈[N]a∈[N] and k≥0k≥ 0, ∑b=1N|(Wk)ab−1N|≤min2,Nρk. _b=1^N |(W^k)_ab- 1N |≤ \2, N\,ρ^k\. Consequently, Ma(W)<∞M_a(W)<∞. Moreover, Ma(W)=O(1+logN1−ρ).M_a(W)=O\! ( 1+ N1-ρ ). At round t, define the hypothetical network-averaged dual state as θ¯t:=1N∑j=1Nθj,t θ_t:= 1N _j=1^N _j,t for 1≤t≤T+11≤ t≤ T+1. For 1≤t≤T1≤ t≤ T define the hypothetical network-averaged surrogate loss ℓ¯t:=1N∑j=1Nℓ~j,t. _t:= 1N _j=1^N _j,t. Also denote the norm of dual disagreement for agent a as da,t:=‖θa,t−θ¯t‖2.d_a,t:=\| _a,t- θ_t\|_2. Lemma 3 analyzes the disagreement in dual space, Lemma 4 builds a bridge between primal space and dual space, and Lemma 5 provides the surrogate regret bound for hypothetical network average BFTRL primal problem. Lemma 3 (Dual-state averages and disagreement). For every 1≤t≤T+11≤ t≤ T+1, θ¯t=∑s<tℓ¯s. θ_t= _s<t _s. (8) Moreover, (∑b=1N‖θb,t−θ¯t‖22)1/2≤NG~(1−ρt−1)δ. ( _b=1^N\| _b,t- θ_t\|_2^2 )^1/2≤ N\, G(1-ρ^t-1)δ. (9) For every agent a, ∑t=1Tda,t≤TG~Ma(W), _t=1^Td_a,t≤ T GM_a(W), (10) The agent-average disagreement also satisfies ∑t=1T1N∑b=1Ndb,t≤TG~δ. _t=1^T 1N _b=1^Nd_b,t≤ T Gδ. (11) With the hypothetical network average dual state θ¯t θ_t, define the hypothetical network average potential Ψ¯t(u):=−νlog(R2−‖u‖22)+μT2‖u‖22+⟨θ¯t,u⟩, _t(u):=-ν (R^2-\|u\|_2^2)+ _T2\|u\|_2^2+ θ_t,u , (12) and the minimizer of the average potential u¯t⋆:=argminu∈int(R2)Ψ¯t(u). u_t := _u (RB_2) _t(u). Lemma 4 (Minimizer disagreement). For every agent a and round t, ‖ua,t⋆−u¯t⋆‖2≤‖θa,t−θ¯t‖2mT.\|u_a,t - u_t \|_2≤ \| _a,t- θ_t\|_2m_T. Lemma 5 (Network-average BFTRL regret). ∀v∈int(R2)∀ v (RB_2), ∑t=1T⟨ℓ¯t,u¯t⋆−v⟩≤Ψ¯1(v)−Ψ¯1(0)+TG~2mT. _t=1^T _t, u_t -v ≤ _1(v)- _1(0)+ T G^2m_T. 4.3 Local Solve Inaccuracy Tolerance Given the local solve inaccuracy tolerances εa,ta∈[N],t=2,…,T\ _a,t\_a∈[N],\,t=2,…,T, we define the total tolerance for agent a over horizon T as Ea,T:=∑t=1Tεa,t,E_a,T:= _t=1^T _a,t, and the average per-agent tolerance over horizon T as ET:=1N∑a=1NEa,T.E_T:= 1N _a=1^NE_a,T. Lemma 6 (Local solve tolerance). Given the tolerance schedule in Subsection 3.2, every call to HybridNewton terminates after finitely many Newton steps and returns an interior point satisfying ‖ua,t−ua,t⋆‖2≤εa,t.\|u_a,t-u_a,t \|_2≤ _a,t. (13) Moreover, Ea,T=(T−1)RT<R,ET<R.E_a,T= (T-1)RT<R, E_T<R. (14) We define the common feasible point zt:=x0+p(u¯t⋆)z_t:=x_0+p_C( u_t ), where p_C is the exact gauge projection from Section 2, and u¯t⋆ u_t is the minimizer of hypothetical average potential (12). Lemma 7 (Feasible-point disagreement). For every agent a and round t, the average internal primal state disagreement is bounded by ∑t=1T1N∑j=1N‖wa,t−wj,t‖2≤2R+(1+κ)(Ea,T+ET)+(1+κ)G~TmT(Ma(W)+1δ). _t=1^T 1N _j=1^N\|w_a,t-w_j,t\|_2≤2R+(1+κ)(E_a,T+E_T)+ (1+κ) GTm_T (M_a(W)+ 1δ ). 4.4 Proof of the Main Theorem Proof of Theorem 1. Define the owner-local payoff term Dα(T,y):=[1N∑j=1N∑t=1T(αft,j(y)−ft,j(h(wj,t)))].D_α(T;y):=E [ 1N _j=1^N _t=1^T (α f_t,j(y)-f_t,j(h(w_j,t)) ) ]. Lemma 1 gives wj,t∈w_j,t . By the definition of ℱt−F_t^-, wj,tw_j,t is ℱt−F_t^--measurable, while ft,jf_t,j and y are fixed. Moreover, qj,tq_j,t, and hence ℓj,t=−qj,t _j,t=-q_j,t, is integrable by Assumption 3. Therefore, conditional on ℱt−F_t^-, Definition 1 and Assumption 3 imply αft,j(y)−ft,j(h(wj,t)) α f_t,j(y)-f_t,j(h(w_j,t)) ≤β⟨(ft,j,wj,t),y−wj,t⟩ ≤β g(f_t,j,w_j,t),y-w_j,t =β[⟨ℓj,t,wj,t−y⟩∣ℱt−]. =β\,E [ _j,t,w_j,t-y _t^- ]. Taking total expectations yields Dα(T,y)≤βN∑j=1N∑t=1T⟨ℓj,t,wj,t−y⟩,D_α(T;y)≤ βN _j=1^N _t=1^T _j,t,w_j,t-y , and we call 1N∑j=1N∑t=1T⟨ℓj,t,wj,t−y⟩ 1N _j=1^N _t=1^T _j,t,w_j,t-y on the right hand side the linear surrogate regret. Note that compared with the network aggregate regret, the owner-local payoff terms use the action for the agent of the payoff function, while the network regret fix the agent of the action. The gap between these two will be bounded in the second step after bounding the linear surrogate regret. After that, we will present parameter tuning to obtain best result, and analyze the total SO calls. Linear Surrogate regret. Fix y∈y , let v0:=y−x0∈v_0:=y-x_0 , and set v:=(1−1T)v0.v:= (1- 1T )v_0. By Assumption 1, v∈∩int(R2)v (RB_2) and ‖x0+v−y‖2≤R/T\|x_0+v-y\|_2≤ R/T. Since ‖ℓj,t‖2=‖qj,t‖2≤G\| _j,t\|_2=\|q_j,t\|_2≤ G by Assumption 3, 1N∑j=1N∑t=1T⟨ℓj,t,x0+v−y⟩≤GR. 1N _j=1^N _t=1^T _j,t,x_0+v-y ≤ GR. Applying Lemma 1 and summing its 2GR/T2GR/T error over t gives 1N∑j=1N∑t=1T⟨ℓj,t,wj,t−y⟩≤3GR+1N∑j=1N∑t=1T⟨ℓ~j,t,uj,t−v⟩. 1N _j=1^N _t=1^T _j,t,w_j,t-y ≤ 3GR+ 1N _j=1^N _t=1^T _j,t,u_j,t-v . (15) The remaining term has the exact decomposition 1N∑j=1N∑t=1T⟨ℓ~j,t,uj,t−v⟩=1N∑j,t⟨ℓ~j,t,uj,t−uj,t⋆⟩+1N∑j,t⟨ℓ~j,t,uj,t⋆−u¯t⋆⟩+∑t=1T⟨ℓ¯t,u¯t⋆−v⟩. 1N _j=1^N _t=1^T _j,t,u_j,t-v = 1N _j,t _j,t,u_j,t-u_j,t + 1N _j,t _j,t,u_j,t - u_t + _t=1^T _t, u_t -v . (16) The first term on the right is bounded by 1N∑j,t⟨ℓ~j,t,uj,t−uj,t⋆⟩≤1N∑j,t‖ℓ~j,t‖2‖ua,t−ua,t⋆‖2=G~1N∑j,t‖ua,t−ua,t⋆‖2=G~ET, 1N _j,t _j,t,u_j,t-u_j,t ≤ 1N _j,t\| _j,t\|_2\|u_a,t-u_a,t \|_2= G 1N _j,t\|u_a,t-u_a,t \|_2= GE_T, where the first inequality is due to cauchy-shwarz inequality, the second equation comes from Lemmas 1 and the third equation comes from Lemma 6. The second term is bounded by 1N∑j,t⟨ℓ~j,t,uj,t⋆−u¯t⋆⟩≤1N∑j,t‖ℓ~j,t‖2‖ua,t⋆−u¯t⋆‖2≤G~mT∑t=1T1N∑j=1Ndj,t≤TG~2mTδ. 1N _j,t _j,t,u_j,t - u_t ≤ 1N _j,t\| _j,t\|_2\|u_a,t - u_t \|_2≤ Gm_T _t=1^T 1N _j=1^Nd_j,t≤ T G^2m_Tδ. where the first inequality is due to cauchy-shwarz inequality, the second inequality comes from Lemma 1 and Lemma 4, the third and forth inequality come from Lemma 3. The third term is directed bounded by Lemma 5 with ∑t=1T⟨ℓ¯t,u¯t⋆−v⟩ _t=1^T _t, u_t -v ≤Ψ¯1(v)−Ψ¯1(0)+TG~2mT ≤ _1(v)- _1(0)+ T G^2m_T =−νlog(1−‖v‖22R2)+μT2‖v‖22+TG~2mT =-ν (1- \|v\|_2^2R^2 )+ _T2\|v\|_2^2+ T G^2m_T ≤νlogT+μTR22+TG~2mT ≤ν T+ _TR^22+ T G^2m_T where the first inequality is from Lemma 5, the second equation is because (8) gives θ¯1=0 θ_1=0, and the third inequality is because ‖v‖2≤(1−1/T)R\|v\|_2≤(1-1/T)R and 1−(1−1/T)2≥1/T1-(1-1/T)^2≥ 1/T. Substitution of the three partial bounds back into (15) bounds the linear surrogate regret: 1N∑j=1N∑t=1T⟨ℓj,t,wj,t−y⟩≤Blin:=3GR+νlogT+μTR22+G~ET+TG~2mT(1+1δ). 1N _j=1^N _t=1^T _j,t,w_j,t-y ≤ B_lin:=3GR+ν T+ _TR^22+ GE_T+ T G^2m_T (1+ 1δ ). (17) Thus, we have Dα(T,y)≤βBlinD_α(T;y)≤β B_lin. Network-aggregate regret. For a fixed comparator y∈y , write ℜαa(T,y):=[∑t=1T(αt(y)−t(h(wa,t)))], R_α^a(T;y):=E [ _t=1^T (α F_t(y)- F_t(h(w_a,t)) ) ], where t(y)=1N∑j=1Nft,j(y) F_t\!(y)= 1N _j=1^Nf_t,j\!(y) and let ϕt,j:=ft,j∘h _t,j:=f_t,j h. Expanding the aggregate payoff gives the exact identity ℜαa(T,y) R_α^a(T;y) =[∑t=1T(αt(y)−t(h(wa,t)))]=[1N∑j=1N∑t=1T(αft,j(y)−ft,j(h(wa,t)))] =E [ _t=1^T (α F_t(y)- F_t(h(w_a,t)) ) ]=E [ 1N _j=1^N _t=1^T (α f_t,j(y)-f_t,j(h(w_a,t)) ) ] =[1N∑j=1N∑t=1T(αft,j(y)−ft,j(h(wj,t)))]+[1N∑j=1N∑t=1T(ft,j(h(wj,t))−ft,j(h(wa,t)))] =E [ 1N _j=1^N _t=1^T (α f_t,j(y)-f_t,j(h(w_j,t)) ) ]+E [ 1N _j=1^N _t=1^T (f_t,j(h(w_j,t))-f_t,j(h(w_a,t)) ) ] =Dα(T,y)+[∑t=1T1N∑j=1N(ϕt,j(wj,t)−ϕt,j(wa,t))]. =D_α(T;y)+E [ _t=1^T 1N _j=1^N ( _t,j(w_j,t)- _t,j(w_a,t) ) ]. (18) Recall Lemma 1 ensures that both wj,tw_j,t and wa,tw_a,t belong to K, so Assumption 4 applies. Since ϕt,j=ft,j∘h _t,j=f_t,j h, ϕt,j(wj,t)−ϕt,j(wa,t)≤|ϕt,j(wj,t)−ϕt,j(wa,t)|≤Lϕ‖wj,t−wa,t‖2. _t,j(w_j,t)- _t,j(w_a,t)≤ | _t,j(w_j,t)- _t,j(w_a,t) |≤ L_φ\|w_j,t-w_a,t\|_2. Thus, substituting the linear surrogate regret of the local-owner payoffs Dα(T,y)≤βBlinD_α(T;y)≤β B_lin and the above inequality into (18) we have ℜαa(T,y) R_α^a(T;y) ≤βBlin+Lϕ[∑t=1T1N∑j=1N‖wj,t−wa,t‖2] ≤β B_lin+L_φ\,E [ _t=1^T 1N _j=1^N\|w_j,t-w_a,t\|_2 ] ≤βBlin+Lϕ[2R+(1+κ)(Ea,T+ET)+(1+κ)G~TmT(Ma(W)+1δ)]. ≤β B_lin+L_φ [2R+(1+κ)(E_a,T+E_T)+ (1+κ) GTm_T (M_a(W)+ 1δ ) ]. (19) where the second inequality comes from Lemma 7. The payoff sequence is fixed before the learner’s randomness, and the hindsight maximum is attained. We may therefore select y⋆∈argmax∑t=1Ty∈t(y)y ∈ _y _t=1^T F_t(y), then ℜαa(T)=ℜαa(T,y⋆) R_α^a(T)= R_α^a(T;y ). Parameter choices and separation-oracle calls. Lemma 6 gives Ea,T,ET≤RE_a,T,E_T≤ R. Since mT≥μTm_T≥ _T, μTR22+TG~2mT(1+1δ)≤μTR22+TG~2μT(1+1δ)=G~R2T(1+1δ). _TR^22+ T G^2m_T (1+ 1δ )≤ _TR^22+ T G^2 _T (1+ 1δ )= GR 2T (1+ 1δ ). Using ν=1ν=1, it follows that βBlin≤ℬT.β B_lin _T. Furthermore, G~TmT≤G~TμT=RTδ2(1+δ). GTm_T≤ GT _T=R Tδ2(1+δ). Substituting these bounds back to (19), and observing that 2R+(1+κ)(Ea,T+ET)≤2R(2+κ),2R+(1+κ)(E_a,T+E_T)≤ 2R(2+κ), we have (7): ℜαa(T)≤ℬT+2LϕR(2+κ)+Lϕ(1+κ)RTδ2(1+δ)(Ma(W)+1δ). R_α^a(T)≤B_T+2L_φR(2+κ)+L_φ(1+κ)R Tδ2(1+δ) (M_a(W)+ 1δ ). where ℬT=β[3GR+G~R+logT+G~R2T(1+1δ)].B_T=β [3GR+ GR+ T+ GR 2T (1+ 1δ ) ]. Finally, ua,1=0u_a,1=0, and Lemma 6 ensures that ua,t∈int(R2)u_a,t (RB_2) for 2≤t≤T2≤ t≤ T. Thus every GaugeDist query satisfies the domain hypothesis of Lemma 9. Since εgau=1/T∈(0,1] _ gau=1/T∈(0,1], that lemma gives at most 1+⌈log2(4κ2T)⌉1+ _2(4κ^2T) separation-oracle calls per invocation. There is one invocation per agent-round. By translation, each call to SepSep_C is implemented by one call to SepSep_K, proving the stated per-agent GaugeDist total. ∎ 5 Conclusion, Limitations, and Future Works We proposed Dec-BFTRL, for decentralized online upper-linearizable optimization under separation-oracle access. The algorithm attains agent-average expected approximate regret O~(T) O\! ( T ) with linear communication in horizon and O(Tlog(κT))O(T (κ T)) total separation-oracle calls. Our analysis avoids distributed curvature tracking. The agents mix a single first-order dual state, and minimizer sensitivity converts disagreement in that state into a primal regret term. A controlled approximate hybrid Newton procedure supplies summable local error without adding communication. The guarantee in this work is specific to domains with a known full-dimensional interior point and economical separation access. It does not impose a universal computational ordering between separation and linear-optimization oracles. Extension to relative-interior geometries such as matroid basis polytopes remains open, and it is necessary before incorporating application to other classes such as the one-sided smooth functions. Separately, for the applications to DR-submodular classes, this work only discusses static regret under the natural first-order feedback setting. Extensions to limited feedback setting, including zeroth-order and bandit feedback, and the investigation of non-stationary environment like dynamic and adaptive regret, remain open. References Aldrighetti et al. (2021) R. Aldrighetti, D. Battini, D. Ivanov, and I. Zennaro Costs of resilience and disruptions in supply chain network design models: a review and future research directions. International Journal of Production Economics 235, p. 108103. Cited by: §1. Bian et al. (2017) A. A. Bian, B. Mirzasoleiman, J. Buhmann, and A. Krause Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Cited by: Remark 2. Bian et al. (2019) Y. Bian, J. Buhmann, and A. Krause Optimal continuous DR-submodular maximization and applications to provable mean field inference. In Proceedings of the 36th International Conference on Machine Learning, Cited by: §1. Garber and Hazan (2016) D. Garber and E. Hazan A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization 26 (3), p. 1493–1528. Cited by: §1. Garber and Kretzu (2022) D. Garber and B. Kretzu New projection-free algorithms for online convex optimization with adaptive regret guarantees. In Conference on Learning Theory, p. 2326–2359. Cited by: §1, Remark 1. Gu et al. (2023) S. Gu, C. Gao, J. Huang, and W. Wu Profit maximization in social networks and non-monotone DR-submodular maximization. Theoretical Computer Science 957, p. 113847. Cited by: §1. Hassani et al. (2017) H. Hassani, M. Soltanolkotabi, and A. Karbasi Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, Cited by: §1. Hazan and Kale (2012) E. Hazan and S. Kale Projection-free online learning. In Proceedings of the 29th International Coference on Machine Learning, Cited by: §1. Ito and Fujimaki (2016) S. Ito and R. Fujimaki Large-scale price optimization via network flow. In Advances in Neural Information Processing Systems, Cited by: §1. Levy and Krause (2019) K. Y. Levy and A. Krause Projection free online learning over smooth sets. In The 22nd International Conference on Artificial Intelligence and Statistics, p. 1458–1466. Cited by: §1. Li et al. (2002) D. Li, K. D. Wong, Y. H. Hu, and A. M. Sayeed Detection, classification, and tracking of targets. IEEE signal processing magazine 19 (2), p. 17–29. Cited by: §1. Liao et al. (2023) Y. Liao, Y. Wan, C. Yao, and M. Song Improved projection-free online continuous submodular maximization. arXiv preprint arXiv:2305.18442. Cited by: §1, Table 1. Lu et al. (2026) Y. Lu, H. Jadav, M. Pedramfar, R. Singh, and V. Aggarwal Upper-linearizability of online non-monotone dr-submodular maximization over down-closed convex sets. In Proceedings of the 43rd International Conference on Machine Learning, Cited by: §I.4, §1, §2.2, Proposition 5. Lu et al. (2025) Y. Lu, M. Pedramfar, and V. Aggarwal Decentralized projection-free online upper-linearizable optimization with applications to DR-submodular optimization. Transactions on Machine Learning Research. Cited by: Appendix I, §1, Table 1, Table 1, Table 1, Table 1, §2.2. Mhammedi (2022) Z. Mhammedi Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, p. 5314–5390. Cited by: §1. Mhammedi (2025) Z. Mhammedi Online convex optimization with a separation oracle. In Proceedings of the 38th Annual Conference on Learning Theory, p. 1–45. Cited by: Appendix A, Appendix A, Appendix A, §1, §2.2. Mishra et al. (2017) S. Mishra, D. Das, and S. Paul A comprehensive review on power distribution network reconfiguration. Energy Systems 8, p. 227–284. Cited by: §1. Mitra et al. (2021) S. Mitra, M. Feldman, and A. Karbasi Submodular+ concave. In Advances in Neural Information Processing Systems, Cited by: §1. Mokhtari et al. (2018) A. Mokhtari, H. Hassani, and A. Karbasi Decentralized submodular maximization: bridging discrete and continuous settings. In International conference on machine learning, p. 3616–3625. Cited by: §1. Nemirovski and Todd (2008) A. S. Nemirovski and M. J. Todd Interior-point methods for optimization. Acta Numerica 17, p. 191–234. Cited by: Appendix B. Pedramfar and Aggarwal (2024) M. Pedramfar and V. Aggarwal From linear to linearizable optimization: a novel framework with applications to stationary and non-stationary dr-submodular optimization. In Advances in Neural Information Processing Systems, Cited by: Appendix I, §I.1, §I.2, §I.3, §1, §2.2, Proposition 2, Proposition 3, Proposition 4. Pedramfar et al. (2025) M. Pedramfar, C. Quinn, and V. Aggarwal Uniform wrappers: bridging concave to quadratizable functions in online optimization. In Advances in Neural Information Processing Systems, Cited by: Appendix I, §1, §2.2, §2.2. Wan et al. (2026) Y. Wan, Y. Shen, D. Yu, B. Xue, and M. Song Improved approximate regret for decentralized online continuous submodular maximization via reductions. arXiv preprint arXiv:2602.09502. Cited by: §1, Table 1, Table 1, Table 1, Table 1. Xiao et al. (2007) L. Xiao, S. Boyd, and S. Kim Distributed average consensus with least-mean-square deviation. Journal of parallel and distributed computing 67 (1), p. 33–46. Cited by: §1. Zhang et al. (2023) Q. Zhang, Z. Deng, X. Jian, Z. Chen, H. Hu, and Y. Yang Communication-efficient decentralized online continuous dr-submodular maximization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, p. 3330–3339. Cited by: §1, Table 1, Table 1. Zhu et al. (2021) J. Zhu, Q. Wu, M. Zhang, R. Zheng, and K. Li Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research 22 (51), p. 1–42. Cited by: §1, Table 1. Appendix A Approximate Gauge Projection This appendix records the separation-based approximate gauge projection subroutine (Algorithm 2) used by the main algorithm, whose construction and guarantees are illustrated by Mhammedi [2025], and no novelty is claimed for this subroutine. We state it for the translated set =−x0C=K-x_0, for which r2⊆R2rB_2 RB_2. Lemma 8 describes useful properties of the gauge function and gauge distance, and Lemma 9 describes the feasibility guarantee and budget of calls to the SO. Algorithm 2 GaugeDist: approximate gauge distance and subgradient 0: Separation oracle SepSep_C, query u∈ℝdu ^d, precision εgau∈(0,1] _ gau∈(0,1], and inner radius r 1: (b,v)←Sep(u)(b,v) _C(u) 2: if b=1b=1 then 3: return (S,s)=(0,0)(S,s)=(0,0) 4: end if 5: α←0α← 0, β←1β← 1, ζ←(α+β)/2ζ←(α+β)/2 6: while β−α>r2εgau/(2‖u‖22)β-α>r^2 _ gau/(2\|u\|_2^2) do 7: (b,vnew)←Sep(ζu)(b,v_ new) _C(ζ u) 8: if b=1b=1 then 9: α←ζα←ζ 10: else 11: β←ζβ←ζ and v←vnewv← v_ new 12: end if 13: ζ←(α+β)/2ζ←(α+β)/2 14: end while 15: S←α−1−1S←α^-1-1 and s←v/(β⟨v,u⟩)s← v/(β v,u ) 16: return (S,s)(S,s) As introduced in Preliminaries, this algorithm is built on gauge function and gauge distance Lemma 8 (Gauge properties). The function γ _C is convex and positively homogeneous. Moreover, γ(u)≤‖u‖2r,S(u)=max0,γ(u)−1. _C(u)≤ \|u\|_2r, S_C(u)= \0, _C(u)-1\. Every subgradient s of γ _C has Euclidean norm at most 1/r1/r. Proof. These are the standard gauge properties collected in Mhammedi [2025, Lemma 2.1 and Appendix G]. They apply to C because the translated geometry places the origin in its interior and contains r2rB_2. ∎ Lemma 9 (Approximate gauge guarantee and SO call budget). For any u∈R2u∈ RB_2 and precision εgau∈(0,1] _ gau∈(0,1], Algorithm 2 returns (S,s)(S,s) satisfying S(u)≤S≤S(u)+εgau,and‖s‖2≤1r,andS(v)≥S(u)+⟨s,v−u⟩−εgau,∀v∈ℝd. S_C(u)≤ S≤ S_C(u)+ _ gau, \|s\|_2≤ 1r, S_C(v)≥ S_C(u)+ s,v-u - _ gau,∀ v ^d. If u∈u , the algorithm terminates after one separation-oracle call. If u∉u , it makes at most 1+⌈log2(4‖u‖22r2εgau)⌉≤1+⌈log2(4κ2εgau)⌉1+ _2\! ( 4\|u\|_2^2r^2 _ gau ) ≤ 1+ _2\! ( 4κ^2 _ gau ) (20) separation-oracle calls. In particular, the right hand side expression is a uniform upper bound in either case. Proof. The three approximation properties and the exterior-query call count are exactly Mhammedi [2025, Lemma 2.2], applied to C. An interior query returns immediately. For an exterior query, ‖u‖2>r\|u\|_2>r, so the displayed logarithm is positive; its second inequality follows from ‖u‖2≤R\|u\|_2≤ R and κ=R/rκ=R/r. ∎ At the precision εgau=1/T _ gau=1/T used by Dec-BFTRL, the per-agent budget over the horizon is therefore T(1+⌈log2(4κ2T)⌉)=O(Tlog(κT)).T (1+ _2(4κ^2T) )=O\! (T (κ T) ). The network-wide budget is N times this quantity. Appendix B HybridNewton: Controlled Approximate Local Barrier-FTRL Solver This appendix defines and analyzes HybridNewton, the local subroutine used by Dec-BFTRL to approximately minimize a local barrier-FTRL potential. The subroutine is a damped/full Newton implementation equipped with control over a computable Euclidean-accuracy. Its role here is to provide the local-solve guarantee required by the regret analysis, and it uses no communication, feedback-oracle calls, or action-set-oracle calls. For a target dual vector θ∈ℝdθ ^d, regularization parameters μ>0μ>0 and ν≥1ν≥ 1, and radius R>0R>0, define the generic barrier-FTRL potential for u∈int(R2)u (RB_2) by F(u):=−νlog(R2−‖u‖22)+μ2‖u‖22+⟨θ,u⟩.F(u):=-ν (R^2-\|u\|_2^2)+ μ2\|u\|_2^2+ θ,u . (21) Set m:=μ+2ν/R2m:=μ+2ν/R^2. Then ∇2F(u)⪰mI∇^2F(u) mI. Since F diverges at the boundary, it has a unique interior minimizer u⋆:=argminu∈int(R2)F(u).u := _u (RB_2)F(u). For an interior point u, define the Newton decrement of F at u by λ(u):=‖∇F(u)‖[∇2F(u)]−1.λ(u):=\|∇ F(u)\|_[∇^2F(u)]^-1. Given a prescribed Euclidean accuracy ε>0 >0, define the stopping threshold τε:=mε1+mε. _ := m\, 1+ m\, . (22) We record the standard self-concordant facts used in the solver analysis. For H(u):=∇2F(u)H(u):=∇^2F(u), write ‖h‖u:=h⊤H(u)h,‖z‖u,∗:=z⊤H(u)−1z.\|h\|_u:= h H(u)h, \|z\|_u,*:= z H(u)^-1z. Thus λ(u)=‖∇F(u)‖u,∗λ(u)=\|∇ F(u)\|_u,*, and the unit Dikin ellipsoid at u is given by ℰu:=u+h:‖h‖u<1.E_u:=\u+h:\|h\|_u<1\. For ν≥1ν≥ 1, the logarithmic term in (21) is self-concordant on int(R2)int(RB_2). Adding the convex quadratic and linear terms preserves self-concordance on the same open domain, and the resulting F still diverges at the boundary [Nemirovski and Todd, 2008]. Standard self-concordant analysis gives ℰu⊆domFE_u . If λ(u)<1λ(u)<1, then ‖u−u⋆‖u≤λ(u)1−λ(u).\|u-u \|_u≤ λ(u)1-λ(u). (23) Moreover, the damped update in (26) satisfies F(u+)≤F(u)−(λ(u)−log(1+λ(u))),F(u^+)≤ F(u)- (λ(u)- (1+λ(u)) ), (24) and the full update in (27), whenever λ(u)<1λ(u)<1, satisfies λ(u+)≤(λ(u)1−λ(u))2.λ(u^+)≤ ( λ(u)1-λ(u) )^2. (25) These are cited standard properties rather than new claims of this paper. The computable stopping test λ(u)≤τελ(u)≤ _ guarantees the requested Euclidean accuracy, as shown below. Algorithm 3 HybridNewton: Local Barrier-FTRL Solver with Guaranteed Accuracy 0: Potential F of the form (21), interior initialization u0u_0, and accuracy ε>0 >0 0: u+u^+ satisfying λ(u+)≤τελ(u^+)≤ _ and hence ‖u+−u⋆‖2≤ε\|u^+-u \|_2≤ 1: u←u0u← u_0 2: τε←mε/(1+mε) _ ← m /(1+ m ) 3: while λ(u)>1/4λ(u)>1/4 do 4: u←u−11+λ(u)[∇2F(u)]−1∇F(u)u← u- 11+λ(u)[∇^2F(u)]^-1∇ F(u) 5: end while 6: while λ(u)>τελ(u)> _ do 7: u←u−[∇2F(u)]−1∇F(u)u← u-[∇^2F(u)]^-1∇ F(u) 8: end while 9: u+←u^+← u 10: return u+u^+ The next two lemmas isolate the safety and accuracy facts used in the main analysis. Proposition 1 then summarizes finite termination and the guaranteed output of the complete subroutine. The final lemma records the cost of one exact Newton iteration. Lemma 10 (Interior safety). Suppose ν≥1ν≥ 1 and u∈int(R2)u (RB_2). The damped Newton update u+=u−[∇2F(u)]−1∇F(u)1+λ(u)u^+=u- [∇^2F(u)]^-1∇ F(u)1+λ(u) (26) remains in int(R2)int(RB_2). The full Newton update u+=u−[∇2F(u)]−1∇F(u)u^+=u-[∇^2F(u)]^-1∇ F(u) (27) also remains in the domain whenever λ(u)<1λ(u)<1. Proof. If d is the damped displacement, then ‖d‖∇2F(u)=λ(u)1+λ(u)<1.\|d\|_∇^2F(u)= λ(u)1+λ(u)<1. Hence u+d∈ℰu⊆domFu+d _u . For the full step, the displacement has local norm λ(u)<1λ(u)<1, and the same argument applies. ∎ Lemma 11 (Euclidean accuracy from the decrement). If u is interior and λ(u)≤δ<1λ(u)≤δ<1, then ‖u−u⋆‖2≤δ(1−δ)m.\|u-u \|_2≤ δ(1-δ) m. In particular, setting δ=τεδ= _ from (22) gives ‖u+−u⋆‖2≤ε.\|u^+-u \|_2≤ . (28) Proof. The bound (23) and monotonicity of x/(1−x)x/(1-x) on [0,1)[0,1) give ‖u−u⋆‖∇2F(u)≤δ/(1−δ)\|u-u \|_∇^2F(u)≤δ/(1-δ). Since ∇2F(u)⪰mI∇^2F(u) mI, this implies the displayed Euclidean bound. Substitution of (22) gives (28). ∎ Proposition 1 (Guaranteed finite termination). For every potential F of the form (21), every interior initialization u0u_0, and every accuracy ε>0 >0, Algorithm 3 is well defined and terminates after finitely many Newton updates. Every iterate remains in int(R2)int(RB_2), and its output satisfies λ(u+)≤τε,‖u+−u⋆‖2≤ε.λ(u^+)≤ _ , \|u^+-u \|_2≤ . Proof. Let ω(s):=s−log(1+s)ω(s):=s- (1+s). During the first loop, Lemma 10 makes every damped update well defined and keeps the new iterate interior. By (24), each such update with λ(u)>1/4λ(u)>1/4 decreases F by at least ω(1/4)>0ω(1/4)>0. Since F is bounded below by F(u⋆)F(u ), the first loop terminates after finitely many updates with λ(u)≤1/4λ(u)≤ 1/4. If τε≥1/4 _ ≥ 1/4, the second loop is skipped. Otherwise, every full update in that loop remains interior by Lemma 10, and (25) yields λ(u+)≤(λ(u)1−λ(u))2≤2λ(u)2whenever λ(u)≤14.λ(u^+)≤ ( λ(u)1-λ(u) )^2≤ 2λ(u)^2 λ(u)≤ 14. Writing bk:=2λ(uk)b_k:=2λ(u_k) for the full-step iterates gives bk+1≤bk2b_k+1≤ b_k^2 and b0≤1/2b_0≤ 1/2, hence bk≤2−2kb_k≤ 2^-2^k. Therefore the positive threshold τε _ is reached after finitely many full steps. The stopping test gives λ(u+)≤τελ(u^+)≤ _ , and Lemma 11 gives ‖u+−u⋆‖2≤ε\|u^+-u \|_2≤ . ∎ For the calls made by Dec-BFTRL, take F=Ψa,tF= _a,t, ν=1ν=1, μ=μTμ= _T, m=mTm=m_T, θ=θa,tθ= _a,t, u0=ua,t−1u_0=u_a,t-1, and ε=R/T =R/T for a∈[N]a∈[N] and t=2,…,Tt=2,…,T. The convention εa,1=0 _a,1=0 is only bookkeeping: no solver call is made at t=1t=1, where ua,1=0u_a,1=0 is the exact minimizer of the initial potential. Thus each agent invokes HybridNewton exactly T−1T-1 times. Lemma 12 (Structured Newton direction). For u∈int(R2)u (RB_2), set D(u):=R2−‖u‖22,a(u):=μ+2νD(u),b(u):=4νD(u)2.D(u):=R^2-\|u\|_2^2,a(u):=μ+ 2νD(u),b(u):= 4νD(u)^2. Then ∇F(u)=a(u)u+θ,∇2F(u)=a(u)I+b(u)uu⊤,∇ F(u)=a(u)u+θ, ∇^2F(u)=a(u)I+b(u)u , and, for every v∈ℝdv ^d, [∇2F(u)]−1v=va(u)−b(u)u⟨u,v⟩a(u)(a(u)+b(u)‖u‖22).[∇^2F(u)]^-1v= va(u)- b(u)u u,v a(u) (a(u)+b(u)\|u\|_2^2 ). Taking v=∇F(u)v=∇ F(u), both the Newton direction and λ(u)2=∇F(u)⊤[∇2F(u)]−1∇F(u)λ(u)^2=∇ F(u) [∇^2F(u)]^-1∇ F(u) use O(d)O(d) arithmetic and O(d)O(d) working memory. Thus one exact HybridNewton iteration has those costs. Proof. Differentiate the potential in (21). The inverse formula is the Sherman-Morrison identity applied to a(u)I+b(u)uu⊤a(u)I+b(u)u . ∎ Appendix C Proof of Lemma 1 Proof of Lemma 1. Suppress j,tj,t, and write u,S,s,p,ℓu,S,s,p, for the corresponding quantities. Lemma 8 and 9 give, by positive homogeneity, γ(p)=γ(u)1+S≤1+S(u)1+S≤1. _C(p)= _C(u)1+S≤ 1+S_C(u)1+S≤ 1. Thus p∈p , w=x0+p∈w=x_0+p , and, by Assumption 1, ‖p‖2≤R\|p\|_2≤ R. Moreover, ‖ℓ‖2=‖q‖2≤G\| \|_2=\|q\|_2≤ G by Assumption 3. Let χ:=⟨ℓ,u⟩<0.χ:=1\ ,u <0\. Because p is a positive multiple of u, −χ⟨ℓ,p⟩≥0-χ ,p ≥ 0. Hence ‖ℓ~‖2≤‖ℓ‖2+|⟨ℓ,p⟩|‖s‖2≤G+GRr≤2κG, \| \|_2≤\| \|_2+| ,p |\|s\|_2≤ G+ GRr≤ 2κ G, where ‖s‖2≤1/r\|s\|_2≤ 1/r follows from Lemma 9, and r≤Rr≤ R follows from Assumption 1. Define L(z):=⟨ℓ,z⟩−χ⟨ℓ,p⟩S(z).L(z):= ,z -χ ,p S_C(z). Since S(v)=0S_C(v)=0 for v∈v , the approximate subgradient inequality for s in Lemma 9 implies L(u)−L(v)≤⟨ℓ~,u−v⟩+|⟨ℓ,p⟩|T.L(u)-L(v)≤ ,u-v + | ,p |T. (29) We also have L(u)≥⟨ℓ,p⟩−GRT.L(u)≥ ,p - GRT. (30) because if S=0S=0, then p=up=u. If S>0S>0 and χ=0χ=0, then ⟨ℓ,u⟩≥0 ,u ≥ 0 and ⟨ℓ,p⟩≤L(u) ,p ≤ L(u). If S>0S>0 and χ=1χ=1, then L(u)−⟨ℓ,p⟩=⟨ℓ,p⟩(S−S(u))≥−GRT.L(u)- ,p = ,p (S-S_C(u) )≥- GRT. Combining (29) and (30), using |⟨ℓ,p⟩|≤GR| ,p |≤ GR and w−(x0+v)=p−vw-(x_0+v)=p-v, we have ⟨ℓ,w−(x0+v)⟩=⟨ℓ,p−v⟩≤⟨ℓ~,u−v⟩+2GRT. ,w-(x_0+v) = ,p-v ≤ ,u-v + 2GRT. ∎ Appendix D Proof of Lemma 2 Proof of Lemma 2. By Assumption 2, the a-th rows of WkW^k and J are probability vectors, so their ℓ1 _1-distance is at most 22. Also, by Cauchy–Schwarz, ∑b=1N|(Wk)ab−1N|≤N(∑b=1N|(Wk)ab−1N|2)1/2≤N‖Wk−J‖2, _b=1^N |(W^k)_ab- 1N |≤ N ( _b=1^N |(W^k)_ab- 1N |^2 )^1/2≤ N\,\|W^k-J\|_2, where J:=⊤/NJ:=11 /N. For k=0k=0, ‖W0−J‖2≤1\|W^0-J\|_2≤ 1. For k≥1k≥ 1, double stochasticity gives WJ=JW=JWJ=JW=J, and hence Wk−J=(W−J)k,‖Wk−J‖2≤ρk.W^k-J=(W-J)^k, \|W^k-J\|_2≤ρ^k. Combining the two conditions of k, ∑b=1N|(Wk)ab−1N|≤min2,Nρk _b=1^N |(W^k)_ab- 1N |≤ \2, N\,ρ^k\ For 0<ρ<10<ρ<1, split the series in (6) at k0:=⌈[log(N/2)]+−logρ⌉k_0:= [ ( N/2)]_+- ρ to obtain Ma(W)≤2k0+N∑k=k0∞ρk≤2k0+21−ρ.M_a(W)≤ 2k_0+ N _k=k_0^∞ρ^k≤ 2k_0+ 21-ρ. If ρ=0ρ=0, then W=JW=J, so only k=0k=0 contributes and Ma(W)=∑b=1N|a=b−1N|=2(1−1N).M_a(W)= _b=1^N |1\a=b\- 1N |=2 (1- 1N ). Finally, −logρ≥1−ρ- ρ≥ 1-ρ for 0<ρ<10<ρ<1, which gives the stated order bound together with the separate ρ=0ρ=0 case. ∎ Appendix E Proof of Lemma 3 Proof of Lemma 3. Double stochasticity in Assumption 2 and (5) give θ¯t+1=θ¯t+ℓ¯t θ_t+1= θ_t+ _t. The zero initialization proves (8). Stack θb,t⊤ _b,t as the rows of t _t, and stack ℓ~b,t⊤ _b,t as the rows of t L_t. With J=⊤/NJ=11 /N, Lemma 1 gives ‖t‖F≤NG~\| L_t\|_F≤ N\, G. Moreover, WJ=JW=JWJ=JW=J by Assumption 2, so (I−J)t+1=(W−J)(I−J)t+(I−J)t.(I-J) _t+1=(W-J)(I-J) _t+(I-J) L_t. Therefore ‖(I−J)t+1‖F≤ρ‖(I−J)t‖F+NG~.\|(I-J) _t+1\|_F≤ρ\|(I-J) _t\|_F+ N\, G. Unrolling from 1=0 _1=0 proves (9). The same recursion gives t=∑s<tWt−1−ss,Jt=∑s<tJs, _t= _s<tW^t-1-s L_s, J _t= _s<tJ L_s, and therefore θa,t−θ¯t=∑s<t∑b=1N((Wt−1−s)ab−1N)ℓ~b,s. _a,t- θ_t= _s<t _b=1^N ((W^t-1-s)_ab- 1N ) _b,s. Using ‖ℓ~b,s‖2≤G~\| _b,s\|_2≤ G, summing over t, and changing the order of summation give ∑t=1Tda,t _t=1^Td_a,t ≤G~∑t=2T∑k=0t−2∑b=1N|(Wk)ab−1N| ≤ G _t=2^T _k=0^t-2 _b=1^N |(W^k)_ab- 1N | =G~∑k=0T−2(T−1−k)∑b=1N|(Wk)ab−1N| = G _k=0^T-2(T-1-k) _b=1^N |(W^k)_ab- 1N | ≤TG~Ma(W), ≤ T GM_a(W), which proves (10). By Cauchy–Schwarz and (9), 1N∑b=1Ndb,t≤G~(1−ρt−1)δ, 1N _b=1^Nd_b,t≤ G(1-ρ^t-1)δ, and summing over t proves (11). ∎ Appendix F Proof of Lemma 4 and Lemma 5 Proof of Lemma 4. The local and network-average potentials have Hessians bounded below by mTIm_TI, and their gradients differ only by θa,t−θ¯t _a,t- θ_t. Strong monotonicity of ∇Ψa,t∇ _a,t, together with the first-order conditions at ua,t⋆u_a,t and u¯t⋆ u_t , gives mT‖ua,t⋆−u¯t⋆‖2≤‖∇Ψa,t(u¯t⋆)−∇Ψa,t(ua,t⋆)‖2=‖θa,t−θ¯t‖2.m_T\|u_a,t - u_t \|_2≤\|∇ _a,t( u_t )-∇ _a,t(u_a,t )\|_2=\| _a,t- θ_t\|_2. ∎ Proof of Lemma 5. Equations (8) and (12) give θ¯1=0 θ_1=0 and u¯1⋆=0 u_1 =0, and make u¯t⋆ u_t the FTRL iterate generated by the regularizer Ψ¯1 _1 and the past vectors ℓ¯1,…,ℓ¯t−1 _1,…, _t-1. The be-the-leader inequality gives ∑t=1T⟨ℓ¯t,u¯t+1⋆−v⟩≤Ψ¯1(v)−Ψ¯1(0). _t=1^T _t, u_t+1 -v ≤ _1(v)- _1(0). The same strong-monotonicity argument as in Lemma 4 yields ‖u¯t⋆−u¯t+1⋆‖2≤‖ℓ¯t‖2mT.\| u_t - u_t+1 \|_2≤ \| _t\|_2m_T. Lemma 1 gives ‖ℓ¯t‖2≤1N∑j=1N‖ℓ~j,t‖2≤G~.\| _t\|_2≤ 1N _j=1^N\| _j,t\|_2≤ G. Therefore, ⟨ℓ¯t,u¯t⋆−u¯t+1⋆⟩≤G~2mT. _t, u_t - u_t+1 ≤ G^2m_T. Adding these inequalities proves the lemma. ∎ Appendix G Proof of Lemma 6 Proof of Lemma 6. At t=1t=1, θa,1=0 _a,1=0 and ua,1=0=ua,1⋆u_a,1=0=u_a,1 . Consider a call at t≥2t≥ 2, and instantiate Appendix B with F=Ψa,tF= _a,t, ν=1ν=1, μ=μTμ= _T, m=mTm=m_T, θ=θa,tθ= _a,t, and ε=εa,t = _a,t. Write λ for the corresponding Newton decrement. Its stopping threshold (22) is τa,t:=mTεa,t1+mTεa,t∈(0,1). _a,t:= m_T\, _a,t1+ m_T\, _a,t∈(0,1). By induction, the warm start ua,t−1u_a,t-1 is interior. While λ>1/4λ>1/4, Lemma 10 keeps each damped step interior, and (24), together with monotonicity of ω(s):=s−log(1+s)ω(s):=s- (1+s), decreases the fixed potential Ψa,t _a,t by at least ω(1/4)>0ω(1/4)>0. Since Ψa,t _a,t is bounded below by its minimum, this phase is finite. Once λ≤1/4λ≤ 1/4, Lemma 10 keeps every full step interior, and (25) gives λ+≤(λ1−λ)2≤2λ2.λ^+≤ ( λ1-λ )^2≤ 2λ^2. If τa,t≥1/4 _a,t≥ 1/4, the stopping condition already holds. Otherwise, for the full-step decrements set bk:=2λkb_k:=2 _k. Then bk+1≤bk2b_k+1≤ b_k^2 and b0≤1/2b_0≤ 1/2, so bk≤2−2kb_k≤ 2^-2^k; hence λk≤τa,t _k≤ _a,t after finitely many steps. Lemma 11, applied with m=mTm=m_T and its threshold variable δ=τa,tδ= _a,t, now gives (13). The returned point is interior and is therefore a valid warm start for the next call. Finally, εa,1=0 _a,1=0 and εa,t=R/T _a,t=R/T for 2≤t≤T2≤ t≤ T, so Ea,T=(T−1)RT<R.E_a,T=(T-1) RT<R. Averaging over agents proves the claim for ETE_T. ∎ Appendix H Proof of Lemma 7 Proof of Lemma 7. We first derive the two properties of the exact radial projection needed below. By Lemma 8, the inclusion r2⊆rB_2 in Assumption 1 makes γ _C, and hence S_C, 1/r1/r-Lipschitz. For u,v∈R2u,v∈ RB_2, set A:=1+S(u),B:=1+S(v).A:=1+S_C(u), B:=1+S_C(v). Since p(v)∈⊆R2p_C(v) RB_2, ‖p(u)−p(v)‖2≤‖u−v‖2A+‖v‖2|A−B|AB≤(1+κ)‖u−v‖2. \|p_C(u)-p_C(v)\|_2≤ \|u-v\|_2A+ \|v\|_2|A-B|AB≤(1+κ)\|u-v\|_2. (31) By initialization and Lemma 6, ua,t∈R2u_a,t∈ RB_2. Therefore, Lemma 9 with εgau=1/T _ gau=1/T gives ‖pa,t−p(ua,t)‖2=‖ua,t‖2|Sa,t−S(ua,t)|(1+Sa,t)(1+S(ua,t))≤RT. \|p_a,t-p_C(u_a,t)\|_2= \|u_a,t\|_2|S_a,t-S_C(u_a,t)|(1+S_a,t)(1+S_C(u_a,t))≤ RT. (32) Equations (31) and (32), followed by Lemmas 6 and 4, imply ‖wa,t−zt‖2 \|w_a,t-z_t\|_2 ≤‖pa,t−p(ua,t)‖2+‖p(ua,t)−p(u¯t⋆)‖2 ≤\|p_a,t-p_C(u_a,t)\|_2+\|p_C(u_a,t)-p_C( u_t )\|_2 ≤RT+(1+κ)(εa,t+da,tmT). ≤ RT+(1+κ) ( _a,t+ d_a,tm_T ). Applying the triangle inequality through ztz_t, averaging over payoff owners j, and summing over t gives ∑t=1T1N∑j=1N‖wa,t−wj,t‖2≤ _t=1^T 1N _j=1^N\|w_a,t-w_j,t\|_2≤ 2R+(1+κ)(Ea,T+ET)+1+κmT(∑t=1Tda,t+∑t=1T1N∑j=1Ndj,t). 2R+(1+κ)(E_a,T+E_T)+ 1+κm_T ( _t=1^Td_a,t+ _t=1^T 1N _j=1^Nd_j,t ). Using Equations (10) and (11) to bound ∑t=1Tda,t _t=1^Td_a,t and ∑t=1T1N∑j=1Ndj,t _t=1^T 1N _j=1^Nd_j,t respectively to obtain the final bound as stated. ∎ Appendix I Applications to Up-Concave and DR-Submodular Maximization We instantiate Theorem 1 through four wrapper pairs covering three standard application families. The upper-linearization inequalities are inherited from prior work; our consequence is their combination with the per-agent decentralized separation-oracle guarantee. Throughout this section, the action set also satisfies Assumption 1: for a known x0∈int()x_0 (K), =−x0,r2⊆R2,κ=R/r.C=K-x_0, rB_2 RB_2, κ=R/r. Thus an application-specific requirement that ∈0 does not replace the interior center x0x_0 used by the gauge algorithm. Function classes. For vectors, x≤yx≤ y denotes coordinatewise order, and ‖x‖∞:=maxk|xk|\|x\|_∞:= _k|x_k|. A differentiable function f is γ-weakly up-concave, for γ∈(0,1]γ∈(0,1], if for every x≤yx≤ y in its domain, γ⟨∇f(y),y−x⟩≤f(y)−f(x)≤1γ⟨∇f(x),y−x⟩.γ ∇ f(y),y-x ≤ f(y)-f(x)≤ 1γ ∇ f(x),y-x . We use up-concave when γ=1γ=1. For a continuous monotone function, its curvature is the smallest c∈[0,1]c∈[0,1] such that f(y+z)−f(y)≥(1−c)(f(x+z)−f(x))f(y+z)-f(y)≥(1-c) (f(x+z)-f(x) ) whenever x,y,z≥x,y,z 0 and all four displayed arguments belong to the domain. These conventions follow Pedramfar and Aggarwal [2024]. A differentiable function is continuous DR-submodular if ∇f(x)≥∇f(y)∇ f(x)≥∇ f(y) coordinatewise whenever x≤yx≤ y. A set ⊆ℝ≥0dK _≥ 0^d is down-closed if x∈x and ≤y≤x0≤ y≤ x imply y∈y . Assumption 5 (One-query first-order base oracle). There exists L>0L>0 such that, for every differentiable payoff f and query point z∈z , the base oracle f(z)O_f(z) returns a random vector Vf(z)V_f(z) satisfying, conditional on the previously revealed information and on the chosen query point, [Vf(z)∣past and z]=∇f(z),‖Vf(z)‖2≤L.E[V_f(z) and z]=∇ f(z), \|V_f(z)\|_2≤ L. The auxiliary randomness used by the Query Wrapper is sampled as part of the wrapped-response generation, after conditioning on ℱt−F_t^-, and independently of the subsequent base-oracle noise. Each wrapper below invokes its base oracle exactly once. Following the feedback terminology of Pedramfar et al. [2025] and Lu et al. [2025], the feedback is first-order semi-bandit when the base-oracle query point equals the played action act(w)W^act(w), and first-order full-information when the query point may differ from that action. Here full-information means that one first-order query may be placed at another feasible point; it does not mean that the entire payoff function is revealed. We do not use blocking, smoothing, zeroth-order estimators, or other limited-feedback conversions. For a wrapper =(act,qry)W=(W^act,W^qry), write ^f:=qry(f),q∼^f(w). O_f:=W^qry(O_f), q O_f(w). When the wrapper is applied to ft,jf_t,j at wj,tw_j,t, its proxy is (ft,j,wj,t):=[qj,t∣ℱt−]. g(f_t,j,w_j,t):=E[q_j,t _t^-]. The tower property over the wrapper and base-oracle randomness verifies the conditional-mean requirement in Assumption 3. All four wrapped outputs satisfy ‖q‖2≤L\|q\|_2≤ L, so G=LG=L. Moreover, ‖∇f(z)‖2=‖[Vf(z)∣past and z]‖2≤L.\|∇ f(z)\|_2=\|E[V_f(z) and z]\|_2≤ L. Hence f is L-Lipschitz on the convex action set. If the Action Wrapper h=acth=W^act is LhL_h-Lipschitz, then |f(h(w))−f(h(v))|≤LLh‖w−v‖2.|f(h(w))-f(h(v))|≤ L_h\|w-v\|_2. (33) so Assumption 4 holds with Lϕ=LLhL_φ=L_h. Substituting G=LG=L and Lϕ=LLhL_φ=L_h into Theorem 1 gives, for every agent a, ℜαa(T)=O~(β+LR[βκ+Lh(1+κ)(1+logN)]T1−ρ). R_α^a(T)= O\! (β+LR [βκ+L_h(1+κ)(1+ N) ] T1-ρ ). (34) In each corollary below, every local payoff ft,jf_t,j is assumed to satisfy the corresponding proposition with common class and oracle constants, and the same wrapper is used by every agent and round. In the anchored non-monotone case, the anchor x¯ x is also fixed and shared. Every wrapper makes one local payoff-oracle query and no action-set-oracle call. Thus the application instantiations retain one neighbor exchange per round and the per-agent O(Tlog(κT))O(T (κ T)) separation-oracle count of Theorem 1. I.1 Monotone Up-Concave Functions over General Convex Sets Proposition 2 (Identity wrapper for monotone weakly up-concave functions; adapted from Pedramfar and Aggarwal [2024]). Let f:[0,1]d→ℝ≥0f:[0,1]^d _≥ 0 be differentiable, monotone, and γ-weakly up-concave for γ∈(0,1]γ∈(0,1], with curvature at most c∈[0,1]c∈[0,1], and let ⊆[0,1]dK [0,1]^d be convex. Define act(w)=h(w)=w,^f(w)=qry(f)(w):=f(w).W^act(w)=h(w)=w, O_f(w)=W^qry(O_f)(w):=O_f(w). Thus q=Vf(w)q=V_f(w) and (f,w)=∇f(w) g(f,w)=∇ f(w). The base-oracle query equals the played action, so this is first-order semi-bandit feedback. For all w,y∈w,y , γ21+cγ2f(y)−f(h(w))≤γ1+cγ2⟨(f,w),y−w⟩. γ^21+cγ^2f(y)-f(h(w))≤ γ1+cγ^2 g(f,w),y-w . Consequently, this wrapper instantiates (α,β,G,Lϕ)=(γ21+cγ2,γ1+cγ2,L,L).(α,β,G,L_φ)= ( γ^21+cγ^2, γ1+cγ^2,L,L ). Proof. The action and query point both equal w∈w . Assumption 5 gives (f,w)=∇f(w) g(f,w)=∇ f(w) and ‖q‖2≤L\|q\|_2≤ L. The upper-linearization inequality, including its curvature-dependent constants, is Pedramfar and Aggarwal [2024, Lemma 1, specialized to = μ 0 ]. Finally, the identity Action Wrapper is 11-Lipschitz, so (33) gives Lϕ=L_φ=L. ∎ Corollary 1 (Monotone up-concave regret on a general set). Under Proposition 2 and the remaining assumptions of Theorem 1, every agent a∈[N]a∈[N] satisfies ℜγ2/(1+cγ2)a(T)=O~(γ1+cγ2+LR[γκ1+cγ2+(1+κ)(1+logN)]T1−ρ). R_γ^2/(1+cγ^2)^a(T)= O\! ( γ1+cγ^2+LR [ γκ1+cγ^2+(1+κ)(1+ N) ] T1-ρ ). Proof. Apply (34) with the tuple in Proposition 2 and Lh=1L_h=1. ∎ I.2 Monotone Up-Concave Functions over Convex Sets Containing the Origin When ∈0 , a randomized Query Wrapper yields the curvature-independent coefficient 1−e−γ1-e^-γ. Proposition 3 (Boosted wrapper for monotone weakly up-concave functions; adapted from Pedramfar and Aggarwal [2024]). Let f:[0,1]d→ℝ≥0f:[0,1]^d _≥ 0 be differentiable, monotone, and γ-weakly up-concave for γ∈(0,1]γ∈(0,1], and let ⊆[0,1]dK [0,1]^d be convex with ∈0 . Define act(w)=h(w)=wW^act(w)=h(w)=w. The Query Wrapper draws Z∈[0,1]Z∈[0,1] with density pγ(z)=γeγ(z−1)1−e−γp_γ(z)= γ e^γ(z-1)1-e^-γ and returns q∼^f(w):=qry(f)(w),q=Vf(Zw).q O_f(w):=W^qry(O_f)(w), q=V_f(Zw). Then (f,w)=∫01pγ(z)∇f(zw)dz. g(f,w)= _0^1p_γ(z)∇ f(zw)\,dz. The query ZwZw generally differs from the played action w, so this is first-order full-information feedback. For all w,y∈w,y , (1−e−γ)f(y)−f(h(w))≤1−e−γ⟨(f,w),y−w⟩.(1-e^-γ)f(y)-f(h(w))≤ 1-e^-γ g(f,w),y-w . Consequently, (α,β,G,Lϕ)=(1−e−γ,1−e−γ,L,L).(α,β,G,L_φ)= (1-e^-γ, 1-e^-γ,L,L ). Proof. Convexity and ∈0 imply Zw∈Zw . Conditional unbiasedness of the base oracle followed by the tower property over Z gives the displayed proxy, while ‖q‖2≤L\|q\|_2≤ L. The boosted upper-linearization inequality is Pedramfar and Aggarwal [2024, Lemma 2 and Algorithm 2]. The identity Action Wrapper has Lh=1L_h=1, so Lϕ=L_φ=L. ∎ Corollary 2 (Monotone up-concave regret when ∈0 ). Under Proposition 3 and the remaining assumptions of Theorem 1, every agent a∈[N]a∈[N] satisfies ℜ1−e−γa(T)=O~(1−e−γ+LR[(1−e−γ)κγ+(1+κ)(1+logN)]T1−ρ). R_1-e^-γ^a(T)= O\! ( 1-e^-γ+LR [ (1-e^-γ)κγ+(1+κ)(1+ N) ] T1-ρ ). Proof. Apply (34) with the tuple in Proposition 3 and Lh=1L_h=1. ∎ I.3 Non-Monotone Up-Concave Functions over General Convex Sets For a non-monotone payoff, the Action Wrapper contracts the internal point toward a fixed feasible anchor. Proposition 4 (Anchored wrapper for non-monotone up-concave functions; adapted from Pedramfar and Aggarwal [2024]). Let f:[0,1]d→ℝ≥0f:[0,1]^d _≥ 0 be differentiable and up-concave, without a monotonicity assumption, and let ⊆[0,1]dK [0,1]^d be convex. Fix a known x¯∈ x with ‖x¯‖∞<1\| x\|_∞<1 and define act(w)=h(w)=w+x¯2.W^act(w)=h(w)= w+ x2. The Query Wrapper draws Z∈[0,1]Z∈[0,1] with density pnm(z)=13(1−z/2)3p_ nm(z)= 13(1-z/2)^3 and returns q∼^f(w):=qry(f)(w),q=Vf(x¯+Z2(w−x¯)).q O_f(w):=W^qry(O_f)(w), q=V_f\! ( x+ Z2(w- x) ). Then (f,w)=∫01pnm(z)∇f(x¯+z2(w−x¯))dz. g(f,w)= _0^1p_ nm(z)∇ f\! ( x+ z2(w- x) )\,dz. The query point generally differs from the played action (w+x¯)/2(w+ x)/2, so this is first-order full-information feedback. For all w,y∈w,y , 1−‖x¯‖∞4f(y)−f(h(w))≤38⟨(f,w),y−w⟩. 1-\| x\|_∞4f(y)-f(h(w))≤ 38 g(f,w),y-w . Consequently, (α,β,G,Lϕ)=(1−‖x¯‖∞4,38,L,L2).(α,β,G,L_φ)= ( 1-\| x\|_∞4, 38,L, L2 ). Under Assumption 1, the known interior point x0x_0 is an admissible choice of x¯ x. Proof. The played action and the query point are convex combinations of w and x¯ x, hence both belong to K. The density is normalized because ∫01dz3(1−z/2)3=1. _0^1 dz3(1-z/2)^3=1. Conditional unbiasedness followed by the tower property over Z gives the displayed proxy without increasing the almost-sure norm bound. The structural inequality is Pedramfar and Aggarwal [2024, Lemma 3 and Algorithm 3]. The Action Wrapper is 1/21/2-Lipschitz, so Lϕ=L/2L_φ=L/2. Finally, because ⊆[0,1]dK [0,1]^d is full-dimensional and x0∈int()x_0 (K), every coordinate of x0x_0 is strictly below 11, and hence ‖x0‖∞<1\|x_0\|_∞<1. ∎ Corollary 3 (Non-monotone up-concave regret on a general set). Under Proposition 4 and the remaining assumptions of Theorem 1, every agent a∈[N]a∈[N] satisfies ℜ(1−‖x¯‖∞)/4a(T)=O~(38+LR[3κ8+(1+κ)(1+logN)2]T1−ρ). R_(1-\| x\|_∞)/4^a(T)= O\! ( 38+LR [ 3κ8+ (1+κ)(1+ N)2 ] T1-ρ ). Proof. Apply (34) with the tuple in Proposition 4 and Lh=1/2L_h=1/2. ∎ I.4 Non-Monotone DR-Submodular Functions on Down-Closed Sets Proposition 5 (Exponential wrapper for non-monotone DR-submodular functions; adapted from Lu et al. [2026]). Let f:[0,1]d→ℝ≥0f:[0,1]^d _≥ 0 be differentiable, non-monotone, and DR-submodular, and let ⊆[0,1]dK [0,1]^d be convex, down-closed, and contain the origin. Define act(w)=h(w)=−e−w.W^act(w)=h(w)=1-e^-w. The Query Wrapper draws Z∈[0,1]Z∈[0,1] with density p(z)=ez−11−e−1,p(z)= e^z-11-e^-1, sets z∘=−e−Zwz =1-e^-Zw, and returns q∼^f(w):=qry(f)(w),q=Vf(z∘)⊙e−Zw.q O_f(w):=W^qry(O_f)(w), q=V_f(z ) e^-Zw. Define Ff(w)=∫01ez−1(1−e−1)z(f(−e−zw)−f())z.F_f(w)= _0^1 e^z-1(1-e^-1)z (f(1-e^-zw)-f(0) )\,dz. The integrand at z=0z=0 is interpreted by its continuous extension. Then (f,w)=Z[∇f(−e−Zw)⊙e−Zw]=∇Ff(w). g(f,w)=E_Z\! [∇ f(1-e^-Zw) e^-Zw ]=∇ F_f(w). The query z∘z generally differs from the played action −e−w1-e^-w, so this is first-order full-information feedback. For all w,y∈w,y , 1ef(y)−f(h(w))≤(1−e−1)⟨(f,w),y−w⟩. 1ef(y)-f(h(w))≤(1-e^-1) g(f,w),y-w . Consequently, (α,β,G,Lϕ)=(1e,1−e−1,L,L).(α,β,G,L_φ)= ( 1e,1-e^-1,L,L ). Proof. For w∈[0,1]dw∈[0,1]^d and Z∈[0,1]Z∈[0,1], −e−Zw≤Zw≤w,−e−w≤w1-e^-Zw≤ Zw≤ w, 1-e^-w≤ w coordinatewise. Down-closedness therefore gives z∘,h(w)∈z ,h(w) . Since the coordinates of e−Zwe^-Zw lie in (0,1](0,1], ‖q‖2≤‖Vf(z∘)‖2≤L.\|q\|_2≤\|V_f(z )\|_2≤ L. Conditional unbiasedness and the tower property over Z give the displayed proxy. The bounded-gradient condition supplies an integrable dominating function, so differentiation under the integral gives (f,w)=∇Ff(w) g(f,w)=∇ F_f(w). The 1/e1/e upper-linearization inequality is Lu et al. [2026, Theorem 1], and its expectation representation and one-query estimator appear in that paper’s Remark 3, Algorithm 1, and Lemma 2. Finally, the Jacobian of h(w)=−e−wh(w)=1-e^-w is diagonal with operator norm at most 11 on [0,1]d[0,1]^d, so Lϕ=L_φ=L is valid. ∎ Corollary 4 (Non-monotone DR-Submodular over Down-closed Set). Under Proposition 5 and the remaining assumptions of Theorem 1, every agent a∈[N]a∈[N] satisfies ℜ1/ea(T)=O~(1−e−1+LR[(1−e−1)κ+(1+κ)(1+logN)]T1−ρ). R_1/e^a(T)= O\! (1-e^-1+LR [(1-e^-1)κ+(1+κ)(1+ N) ] T1-ρ ). Proof. Apply (34) with the tuple in Proposition 5 and Lh=1L_h=1. ∎ The four wrappers above are not new approximation reductions. Their role here is to provide the exact Action and Query Wrappers, verify the feedback and payoff-stability assumptions of Theorem 1, and obtain the corresponding decentralized guarantees. This work does not develop results for limited-feedback reductions and applications to one-sided-smooth objectives, approximately convex objectives, and relative-interior domains such as matroid basis polytopes.