Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

Yiyang Lu; Mohammad Pedramfar; Vaneet Aggarwal

math.OCJan 30, 2025

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

Authors: Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Abstract

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

Figures & tables

$F$	Set	Feedback		Reference	Appx. ( $\alpha$ )	$\log_{T}(\alpha\text{-Regret})$	$\log_{T}(\text{Communication})$	$\log_{T}(\text{LOO calls})$	Range of $\theta$
Monotone	$0\in{\mathcal{K}}$	$\nabla F$	full information	DMFW ( Zhu et al., 2021 )	$1-e^{-1}$	$1/2$	$5/2$	$5/2$	-
				Mono-DMFW ( Zhang et al., 2023 )	$1-e^{-1}$	$4/5$	$1$	$1$	-
				DOBGA ( Zhang et al., 2023 )	$1-e^{-1}$	$1/2$	$1$	$-$	-
				DPOBGA Liao et al. (2023)	$1-e^{-1}$	$3/4$	$1/2$	$1$	-
				Theorem 2	$1-e^{-\gamma}$	$1-\theta/2$	$\theta$	$2\theta$	[0, 1]
			semi-bandit	Theorem 4	$1-e^{-\gamma}$	$1-\theta/2$	$\theta$	$2\theta$	[0, 2/3]

Table 1: Decentralized Online Up-concave Maximization Algorithms Comparison

\hat{\mathbf{x}}_{t}^{i}=T_{\delta}(\mathbf{x}_{m}^{i})+\delta{\mathbf{v}}_{t}^{i}

Algorithm 2 Bandit Algorithm for Case B.1

Explore similar work

Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
Aug 31, 2026Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular Functions Decentralized Optimization
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization
Sep 30, 2026Vaneet AggarwalSubmodular Functions \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Purdue University
Revisiting Decentralized Online Convex Optimization with Compressed Communication
Jul 2, 2026Hao Zhou, Xiaoyu Wang, Chang Yao +2Decentralized Optimization \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
School of Software Technology, Zhejiang University, Ningbo, China · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China

Aug 31, 2026, math.OCJ/K move · Enter open · S save

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

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Submodular Functions Decentralized Optimization Decentralized Autonomous Organization Optimistic Follow-The-Regularized-Leader Separation

Open paper AskPDF arXiv

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 wrapper instantiations covering four up-concave or DR-submodular maximization problems.

Abstract

Explore similar work

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

Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

Revisiting Decentralized Online Convex Optimization with Compressed Communication