Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

• Decentralized online optimization targets large-scale systems where agents adapt to evolving data without a central coordinating server, despite potentially highly non-convex global objectives.Source: §1 · p. 1
• The setting uses local feedback and evaluates each agent against the aggregate of all local payoff owners’ functions.Source: §1 · pp. 1–2
• Dec-BFTRL provides decentralized barrier-FTRL for online upper-linearizable maximization under separation access.Source: §1 · pp. 2–3
• sqrt(T)-scale expected per-agent network-aggregated α-regret is achieved with T neighbor-mixing operations and O(T log(κT)) separation-oracle calls.Source: §1 · p. 3

Technical Novelties

• The method communicates only dual states, uses row-wise mixing to control specified-agent disagreement, and keeps Hessian and Newton computations local.Source: §1 · p. 3
• HybridNewton uses a self-concordant stopping rule and an accuracy schedule that bounds cumulative local-solver error while guaranteeing finite termination.Source: §1 · p. 3

Separation access

• A separation oracle either certifies feasibility or returns a separating normal vector, providing the action-set access model used by the framework.Source: §2.2 · p. 3

Oracle models

• Separation and linear-optimization oracles are distinct access models whose call counts do not by themselves determine equal computational cost.Source: §2.2 · pp. 3–4

Separation access

• Gauge projection translates the set by an interior point, scales infeasible points to the boundary, and can be approximated through the SO-based GaugeDist routine.Source: §2.2 · p. 4

Wrappers and protocol

• Uniform wrappers map internal points to feasible actions and transform base-oracle responses into feedback vectors, potentially using randomness and queries at feasible points.Source: §2.2 · pp. 4–5

Assumptions

• The feasible set is compact and convex with a known full-dimensional interior point and radii ratio κ := R/r, while the network is connected and uses a symmetric doubly stochastic mixing matrix.Source: §2.3 · p. 5
• The protocol assumes conditionally unbiased bounded feedback and uniformly Lipschitz composed payoffs, with each agent’s action generated from its internal state through h.Source: §2.3 · p. 5

3.1 Main Algorithm

• Dec-BFTRL uses GaugeDist to map each interior primal state to a feasible action through approximate radial gauge projection.The resulting action is formed as wa,t = x0 + pa,t, with pa,t obtained by scaling ua,t using the approximate gauge distance.Source: §3 · p. 5, §3.1 · p. 6
• Each agent communicates only its dual state, then injects its current surrogate loss after neighbor mixing.No primal iterate, feasible point, Hessian, or Newton information is exchanged.Source: §3.1 · pp. 6–7
• The feedback received at round t affects the primal state used at round t + 1, not the action already played at round t.The communicated vector is the pre-update dual state and therefore contains only information from earlier rounds.Source: §3.1 · pp. 6–7
• HybridNewton locally computes an approximate minimizer of the post-communication barrier-FTRL potential and returns an interior primal state for the next round.The logarithmic barrier preserves interiority, while strong convexity links the stopping condition to Euclidean accuracy.Source: §3.1 · pp. 6–7

3.2 Main Guarantee

• Theorem 1 guarantees each agent’s stated regret bound under common upper-linearizable payoffs and assumptions 1–4.The theorem applies with the fixed action and query wrappers and the parameter choices specified for the main guarantee.Source: §3.2 · pp. 7–8
• Each agent makes at most T total calls to the action-set separation oracle, excluding calls made by application-specific wrappers.The algorithm uses one round-level GaugeDist invocation per agent-round under the stated gauge precision.Source: §3.2 · p. 8

4 Analysis

• Lemma 1 ensures the gauge-projected points are feasible and bounds the surrogate projection error by eG.This supplies the feasibility and approximation information used in the later regret decomposition.Source: §4.1 · p. 8

4.2 Network Mixing and Dual States

• Lemma 2 controls cumulative row-wise network mixing, while Lemma 3 bounds disagreement between each agent’s dual state and the hypothetical network-average dual state.The analysis introduces hypothetical network-averaged dual and surrogate quantities to make this comparison explicit.Source: §4.2 · pp. 8–9

4.3 Primal and Solver Disagreement

• Strong convexity and minimizer sensitivity convert dual-state disagreement into disagreement between local and hypothetical primal minimizers.Lemma 4 provides the corresponding minimizer-disagreement bridge.Source: §4.2 · p. 8, The agent-average disagreement also… · p. 9

4.4 Proof of the Main Theorem

• The linear surrogate regret is bounded by Blin, with the proof combining gauge errors, local solve tolerances, and the hypothetical average BFTRL regret.The resulting bound is summarized by Dα(T; y) ≤ βBlin.Source: The agent-average disagreement also… · p. 9, §4.3 · p. 9, §4.4 · p. 11

4.3 Local Solve Inaccuracy Tolerance

• Lemma 6 guarantees finite termination of every HybridNewton call under the prescribed tolerance schedule and bounds the accumulated local solve tolerances.The separation-oracle analysis uses εgau = 1/T and applies the GaugeDist domain conditions to each invocation.Source: §4.3 · p. 9, §4.4 · p. 12

4 Analysis

• The analysis separates owner-local surrogate regret from network-aggregate regret, because the two evaluate payoffs at different agents’ actions.The gap is subsequently bounded through disagreement between feasible actions.Source: §4.4 · pp. 10–11

4.4 Proof of the Main Theorem

• Substituting the surrogate bound and feasible-action disagreement into the network decomposition yields the main network-aggregate regret inequality.The final parameter choices bound the tolerance and stability contributions and establish the theorem’s stated result.Source: §4.4 · p. 11

• Dec-BFTRL attains agent-average expected approximate regret with linear communication in the horizon.Source: §5 · p. 12
• The method uses one first-order dual state and converts dual-state disagreement into a primal regret term through minimizer sensitivity.Source: §5 · p. 12
• The algorithm requires O(T log(κT)) total separation-oracle calls and uses controlled HybridNewton errors without additional communication.Source: §5 · p. 12
• The guarantee is limited to domains with a known full-dimensional interior point and economical separation access.Source: §5 · p. 12
• Extensions to relative-interior geometries, limited-feedback settings, and dynamic or adaptive regret remain open.Source: §5 · p. 12

Approximate Gauge Projection

• GaugeDist first queries the separation oracle and returns zero gauge distance and subgradient when the query is feasible.Source: A Approximate Gauge Projection · p. 14
• For exterior queries, GaugeDist uses bisection along the query ray to approximate gauge distance and construct a subgradient.Source: A Approximate Gauge Projection · p. 14
• The gauge function is convex and positively homogeneous, and every gauge subgradient has Euclidean norm at most 1/r.Source: A Approximate Gauge Projection · p. 14

HybridNewton

• HybridNewton approximately minimizes local barrier-FTRL potentials without communication, feedback-oracle calls, or action-set-oracle calls.Source: B HybridNewton: Controlled Approximate… · p. 15
• HybridNewton terminates finitely, keeps iterates interior, and returns an ε-accurate minimizer under its decrement-based stopping rule.Source: B HybridNewton: Controlled Approximate… · pp. 16–17
• Each exact HybridNewton iteration uses O(d) arithmetic and O(d) working memory, while Dec-BFTRL invokes the solver T−1 times per agent.Source: B HybridNewton: Controlled Approximate… · p. 17

• The gauge projection yields a feasible point p in the translated set and maps it to w = x0 + p in K.Source: C Proof of Lemma 1 · p. 17
• The proof bounds the projected point, subgradient, and payoff-gradient terms using the action-set radius, interior radius, and gradient bound.Source: C Proof of Lemma 1 · p. 17
• An auxiliary function L(z) combines the linear payoff term with gauge distance to apply the approximate subgradient inequality.Source: C Proof of Lemma 1 · pp. 17–18
• Combining the gauge and auxiliary-function bounds controls the discrepancy between the feasible action and the comparison point.Source: C Proof of Lemma 1 · p. 18

• Each row of W^k and J is a probability vector, so their ℓ1-distance is at most 2.Source: D Proof of Lemma 2 · p. 18
• For k ≥ 1, double stochasticity gives WJ = JW = J, enabling the disagreement bound in terms of powers of the contraction parameter ρ.Source: D Proof of Lemma 2 · p. 18
• The proof splits the geometric series at k0 to bound cumulative mixing disagreement for 0 < ρ < 1.Source: D Proof of Lemma 2 · p. 18
• When ρ = 0, W = J and only the k = 0 term contributes to the bound.Source: D Proof of Lemma 2 · p. 18
• Using −log ρ ≥ 1−ρ yields the stated order bound, with a separate treatment for ρ = 0.Source: D Proof of Lemma 2 · p. 18

• Double stochasticity and the update relation imply the network-average state evolves by the average surrogate vector.Source: E Proof of Lemma 3 · p. 18
• The zero initialization establishes the stated unrolled expression for the average state.Source: E Proof of Lemma 3 · p. 18
• The mixing matrix preserves the consensus projector because WJ = JW = J.Source: E Proof of Lemma 3 · p. 18
• Bounding each surrogate vector, summing over rounds, and applying Cauchy–Schwarz yields the lemma’s cumulative estimates.Source: E Proof of Lemma 3 · p. 19

Proof of Lemma 4

• Hessian lower bounds by mT I and strong monotonicity control the difference between local and network-average potential minimizers.Source: F Proof of Lemma 4 and Lemma 5 · p. 19

Proof of Lemma 5

• The average initialization and update identities make the average minimizer the FTRL iterate for the averaged regularizer and past averaged vectors.Source: F Proof of Lemma 4 and Lemma 5 · p. 19
• The be-the-leader inequality bounds the cumulative average-vector inner products by the averaged regularizer difference.Source: F Proof of Lemma 4 and Lemma 5 · p. 19
• Strong monotonicity supplies the accompanying iterate-norm bound, and adding the inequalities proves the lemma.Source: F Proof of Lemma 4 and Lemma 5 · p. 19

• At t = 1, the local internal point and exact minimizer both equal zero.Source: G Proof of Lemma 6 · p. 19
• For later rounds, HybridNewton is instantiated with the local BFTRL potential, barrier parameters, warm start, and target accuracy.Source: G Proof of Lemma 6 · p. 19
• Damped steps preserve interiority while reducing the fixed potential until the Newton decrement is at most 1/4.Source: G Proof of Lemma 6 · pp. 19–20
• Full-step decrements contract quadratically, so the stopping threshold is reached after finitely many iterations.Source: G Proof of Lemma 6 · p. 20
• The returned interior point becomes a valid warm start for the next call, and averaging over agents proves the cumulative claim for ET.Source: G Proof of Lemma 6 · p. 20

Proof of Lemma 7

• The action-set geometry rB2 ⊆ C ⊆ RB2 gives the gauge and radial projection the Lipschitz control used in the proof.Source: H Proof of Lemma 7 · p. 20, I Applications to Up-Concave and… · p. 20
• Approximate gauge projection and the internal-point bounds allow action deviations to be controlled through the exact projection and local minimization errors.Source: H Proof of Lemma 7 · p. 20
• The resulting payoff-owner deviation bound combines radius, conditioning, and approximation terms before the final regret estimate.Source: H Proof of Lemma 7 · p. 20

Application wrappers

• Four wrapper pairs cover three application families, each using one base payoff-oracle query and no action-set-oracle call.Source: I Applications to Up-Concave and… · pp. 20–21

Monotone up-concave functions over general sets

• The identity wrapper uses the played action as its query point, producing first-order semi-bandit feedback and the monotone general-set corollary.Source: §I.1 · p. 22

Monotone up-concave functions containing the origin

• When 0 ∈ K, the boosted wrapper queries at Zw and yields a curvature-independent coefficient 1 −e−γ.Source: §I.2 · pp. 22–23

Non-monotone up-concave functions

• For non-monotone payoffs, the anchored wrapper contracts the internal point toward a feasible anchor, with query and played actions generally differing.Source: §I.3 · pp. 23–24

Scope

• The wrappers verify decentralized guarantees but are not new approximation reductions, and limited-feedback and several other objective or domain settings remain outside scope.Source: §I.4 · p. 25