Source-linked AI summary
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
TL;DR
The paper addresses decentralized online upper-linearizable optimization under efficient separation access, where agents receive local feedback but are evaluated on network-aggregate objectives. It proposes Dec-BFTRL, combining feasible-action mapping, dual-state communication, and local barrier-FTRL optimization. The method achieves expected network-aggregate regret of O~(sqrt(T)) with T mixing steps and O~(T) separation-oracle calls per agent.
Problem
The paper asks what performance decentralized online upper-linearizable optimization can achieve under separation access and how it applies to decentralized online continuous DR-submodular maximization.
Method
Dec-BFTRL maps internal iterates to feasible actions, communicates cumulative surrogate-gradient dual states, and approximately minimizes local post-communication barrier-FTRL potentials.
Results
Expected per-agent network-aggregate α-regret is O~(sqrt(T)), with T neighbor-mixing operations and O~(T) separation-oracle calls over T rounds.
Takeaways & Limitations
The general payoff theorem yields square-root-T guarantees and supports four wrapper instantiations covering three DR-submodular maximization problems.
Takeaways & Limitations
The guarantees require a known full-dimensional interior point and economical separation access; relative-interior geometries and limited-feedback or non-stationary extensions remain open.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies decentralized online optimization when agents receive local feedback but are evaluated on network-aggregate objectives under separation access. It introduces Dec-BFTRL and establishes square-root regret with linear communication and near-linear separation-oracle use, while addressing first-order coordination, consensus, and approximate optimization challenges.
- 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.
- The setting uses local feedback and evaluates each agent against the aggregate of all local payoff owners’ functions.
- Dec-BFTRL provides decentralized barrier-FTRL for online upper-linearizable maximization under separation access.
- sqrt(T)-scale expected per-agent network-aggregated α-regret is achieved with T neighbor-mixing operations and O(T log(κT)) separation-oracle calls.
- Technical Novelties: The method communicates only dual states, uses row-wise mixing to control specified-agent disagreement, and keeps Hessian and Newton computations local.
- Technical Novelties: HybridNewton uses a self-concordant stopping rule and an accuracy schedule that bounds cumulative local-solver error while guaranteeing finite termination.
2 Preliminaries
The preliminaries define separation-based access, gauge projection, wrapped feedback, upper-linearizable payoffs, and the network and feedback assumptions used by Dec-BFTRL. They also distinguish separation and linear-optimization oracle costs and formalize the decentralized online protocol.
- Separation access: A separation oracle either certifies feasibility or returns a separating normal vector, providing the action-set access model used by the framework.
- Oracle models: Separation and linear-optimization oracles are distinct access models whose call counts do not by themselves determine equal computational cost.
- 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.
- 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.
- 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.
- Assumptions: The protocol assumes conditionally unbiased bounded feedback and uniformly Lipschitz composed payoffs, with each agent’s action generated from its internal state through h.
3 Decentralized Barrier Follow the Regularized Leader (Dec-BFTRL)
Dec-BFTRL combines separation-access feasibility, one dual-state exchange per round, and local HybridNewton solves for decentralized barrier-FTRL optimization. Under the stated assumptions and parameter choices, it provides per-agent regret and separation-oracle guarantees.
- 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.
- 3.1 Main Algorithm: 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.
- 3.1 Main Algorithm: 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.
- 3.1 Main Algorithm: 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.
- 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.
- 3.2 Main Guarantee: 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.
4 Analysis
The analysis bounds network-aggregate regret by connecting local surrogate regret to decentralized feasible-action disagreement. Row-wise mixing controls dual disagreement, while barrier-FTRL stability and solver tolerances control the resulting primal terms.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
5 Conclusion, Limitations, and Future Works
The paper proposes Dec-BFTRL for decentralized online upper-linearizable optimization under separation access and derives regret and resource guarantees. It also identifies domain, feedback, and regret-scope boundaries for the results.
- Dec-BFTRL attains agent-average expected approximate regret with linear communication in the horizon.
- The method uses one first-order dual state and converts dual-state disagreement into a primal regret term through minimizer sensitivity.
- The algorithm requires O(T log(κT)) total separation-oracle calls and uses controlled HybridNewton errors without additional communication.
- The guarantee is limited to domains with a known full-dimensional interior point and economical separation access.
- Extensions to relative-interior geometries, limited-feedback settings, and dynamic or adaptive regret remain open.
A Approximate Gauge Projection
The appendices describe the approximate gauge projection and HybridNewton subroutines used by Dec-BFTRL. Gauge projection provides feasible-action and subgradient guarantees under separation access, while HybridNewton supplies controlled local minimization accuracy.
- Approximate Gauge Projection: GaugeDist first queries the separation oracle and returns zero gauge distance and subgradient when the query is feasible.
- Approximate Gauge Projection: For exterior queries, GaugeDist uses bisection along the query ray to approximate gauge distance and construct a subgradient.
- Approximate Gauge Projection: The gauge function is convex and positively homogeneous, and every gauge subgradient has Euclidean norm at most 1/r.
- HybridNewton: HybridNewton approximately minimizes local barrier-FTRL potentials without communication, feedback-oracle calls, or action-set-oracle calls.
- HybridNewton: HybridNewton terminates finitely, keeps iterates interior, and returns an ε-accurate minimizer under its decrement-based stopping rule.
- HybridNewton: Each exact HybridNewton iteration uses O(d) arithmetic and O(d) working memory, while Dec-BFTRL invokes the solver T−1 times per agent.
C Proof of Lemma 1
The proof establishes that the gauge-based surrogate controls the mapped feasible action and its linearized payoff. It combines approximate gauge inequalities with norm and geometry bounds.
- The gauge projection yields a feasible point p in the translated set and maps it to w = x0 + p in K.
- The proof bounds the projected point, subgradient, and payoff-gradient terms using the action-set radius, interior radius, and gradient bound.
- An auxiliary function L(z) combines the linear payoff term with gauge distance to apply the approximate subgradient inequality.
- Combining the gauge and auxiliary-function bounds controls the discrepancy between the feasible action and the comparison point.
D Proof of Lemma 2
The proof bounds cumulative row-wise network-mixing disagreement using stochastic-matrix properties and the contraction parameter ρ. The resulting order depends on the mixing rate through 1−ρ.
- Each row of W^k and J is a probability vector, so their ℓ1-distance is at most 2.
- For k ≥ 1, double stochasticity gives WJ = JW = J, enabling the disagreement bound in terms of powers of the contraction parameter ρ.
- The proof splits the geometric series at k0 to bound cumulative mixing disagreement for 0 < ρ < 1.
- When ρ = 0, W = J and only the k = 0 term contributes to the bound.
- Using −log ρ ≥ 1−ρ yields the stated order bound, with a separate treatment for ρ = 0.
E Proof of Lemma 3
Lemma 3 derives cumulative network-average dual-state identities from double stochasticity, mixing invariance, and zero initialization, then bounds their growth using norm inequalities.
- Double stochasticity and the update relation imply the network-average state evolves by the average surrogate vector.
- The zero initialization establishes the stated unrolled expression for the average state.
- The mixing matrix preserves the consensus projector because WJ = JW = J.
- Bounding each surrogate vector, summing over rounds, and applying Cauchy–Schwarz yields the lemma’s cumulative estimates.
F Proof of Lemma 4 and Lemma 5
Lemmas 4 and 5 compare local and network-average BFTRL potentials through strong monotonicity and reduce the average iterates to a standard FTRL sequence.
- Proof of Lemma 4: Hessian lower bounds by mT I and strong monotonicity control the difference between local and network-average potential minimizers.
- 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.
- Proof of Lemma 5: The be-the-leader inequality bounds the cumulative average-vector inner products by the averaged regularizer difference.
- Proof of Lemma 5: Strong monotonicity supplies the accompanying iterate-norm bound, and adding the inequalities proves the lemma.
G Proof of Lemma 6
Lemma 6 proves that warm-started damped and full Newton steps remain interior and reach the prescribed accuracy, yielding the cumulative approximation guarantee.
- At t = 1, the local internal point and exact minimizer both equal zero.
- For later rounds, HybridNewton is instantiated with the local BFTRL potential, barrier parameters, warm start, and target accuracy.
- Damped steps preserve interiority while reducing the fixed potential until the Newton decrement is at most 1/4.
- Full-step decrements contract quadratically, so the stopping threshold is reached after finitely many iterations.
- The returned interior point becomes a valid warm start for the next call, and averaging over agents proves the cumulative claim for ET.
H Proof of Lemma 7
Lemma 7 transfers internal BFTRL guarantees to feasible played actions through gauge projection, while wrapper instantiations verify the assumptions needed for decentralized DR-submodular applications.
- Proof of Lemma 7: The action-set geometry rB2 ⊆ C ⊆ RB2 gives the gauge and radial projection the Lipschitz control used in the proof.
- Proof of Lemma 7: Approximate gauge projection and the internal-point bounds allow action deviations to be controlled through the exact projection and local minimization errors.
- Proof of Lemma 7: The resulting payoff-owner deviation bound combines radius, conditioning, and approximation terms before the final regret estimate.
- Application wrappers: Four wrapper pairs cover three application families, each using one base payoff-oracle query and no action-set-oracle call.
- 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.
- Monotone up-concave functions containing the origin: When 0 ∈ K, the boosted wrapper queries at Zw and yields a curvature-independent coefficient 1 −e−γ.
- 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.
- 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.