Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
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 Õ(√T). Over T rounds, each agent uses T neighbor-mixing steps and Õ(T) separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.
Related
- Hybrid Sequential Feedback Optimization for Wind Farm Power Maximization
- Expected Hypervolume Maximization for Multiobjective Optimization under Uncertainties
- Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization
- Decentralized Optimization with Cross-Coupled Mixed Affine Constraints
- DOFFO_TR: a Decentralized Objective Function-Free Optimization method with Trust-Region
BibTeX
@misc{lu2026decbftrl,
title = {{Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization}},
author = {Yiyang Lu and Mohammad Pedramfar and Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.30271},
eprint = {2608.30271},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30271},
}
RIS
TY - UNPB
TI - Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
AU - Yiyang Lu
AU - Mohammad Pedramfar
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.30271
UR - https://arxiv.org/abs/2608.30271
AB - 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 Õ(√T). Over T rounds, each agent uses T neighbor-mixing steps and Õ(T) separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.
ER -