pith. sign in

arxiv: 2607.00680 · v1 · pith:HXGVIUQGnew · submitted 2026-07-01 · 💻 cs.LG

Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

Bin Du , Chang Liu , Dingqi Zhu , Lintao Ye , Dengfeng Sun This is my paper

Pith reviewed 2026-07-02 15:45 UTC · model grok-4.3

classification 💻 cs.LG
keywords distributed optimizationonline submodular maximizationbandit feedbackpartition matroidpipage roundingregret boundssampling violations
0
0 comments X

The pith

Multiple agents achieve sublinear (1-1/e)-regret in distributed online submodular maximization under partition matroids while keeping sampling violations sublinear.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops algorithms for multiple agents that each select a limited number of actions from local subsets to maximize the sum of values from a sequence of objective functions. It supplies a unified framework that works for both full-information and bandit feedback and proves sublinear (1-1/e)-regret bounds that match existing centralized results. To handle the violations that arise when relaxing the discrete problem and rounding the solution, the authors introduce a bounded stochastic pipage rounding procedure whose violation probability goes to zero, keeping the total number of violations sublinear in the horizon T.

Core claim

Under partition matroid constraints the proposed distributed algorithms attain sublinear (1-1/e)-regret for both feedback models, and the bounded stochastic pipage rounding scheme drives the probability of sampling violation to zero so that the cumulative violation stays sublinear in T and is not improvable under certain conditions.

What carries the argument

Bounded stochastic pipage rounding scheme that forces the probability of a sampling violation to vanish asymptotically after continuous relaxation and rounding.

If this is right

  • Regret is sublinear in T under full-information feedback.
  • Regret is sublinear in T under bandit feedback.
  • Cumulative sampling violation remains sublinear in T.
  • The sublinear violation bound cannot be improved under the stated conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same rounding technique might be reused in other online combinatorial problems that rely on continuous relaxation.
  • The distributed structure could reduce the communication cost of solving large-scale submodular problems compared with a single central coordinator.
  • Similar violation-control arguments may apply when the constraint is a more general matroid or intersection of matroids.

Load-bearing premise

Each objective function is monotone submodular and the feasible sets form a partition matroid.

What would settle it

An explicit sequence of monotone submodular functions on a partition matroid where the total number of sampling violations grows linearly with T would falsify the sublinear-violation claim.

Figures

Figures reproduced from arXiv: 2607.00680 by Bin Du, Chang Liu, Dengfeng Sun, Dingqi Zhu, Lintao Ye.

Figure 1
Figure 1. Figure 1: Simulation setup: 4 agents connected via a ring graph, where each agent selects at most one retrieval point from its candidate set Bi for device deployment. The retrieval points are partitioned into four clusters. To maximize the overall objective value, agents are encouraged to cooperatively avoid overlap, i.e., to avoid selecting retrieval points from the same cluster. In this simulation, we consider |D|… view at source ↗
Figure 2
Figure 2. Figure 2: Performance of the proposed algorithms against centralized baselines: (a) cumulative [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Effect of the communication topology on Algorithm [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
read the original abstract

We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear $(1-1/e)$-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in $T$, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops a unified algorithmic framework for distributed online submodular maximization under partition matroid constraints, supporting both full-information and bandit feedback. The algorithms are shown to achieve sublinear (1-1/e)-regret bounds comparable to centralized methods. A bounded stochastic pipage rounding scheme is introduced to control sampling violations from continuous relaxation, with the probability of violation shown to vanish asymptotically, yielding sublinear cumulative violations in T that are not improvable under stated conditions. Numerical results are provided for validation.

Significance. If the regret and violation analyses hold, the work provides a distributed extension of centralized submodular maximization results while addressing a practical sampling issue via a new rounding procedure whose violation bound is shown to be tight. This is relevant for multi-agent online learning applications involving monotone submodular objectives and matroid constraints. The matching lower bound on violations strengthens the contribution.

major comments (2)
  1. [§4] §4 (Regret Analysis): the (1-1/e)-regret bound for the bandit-feedback algorithm is stated to match centralized counterparts, but the additional communication or coordination terms arising from the distributed setting must be shown not to degrade the leading constant or the o(T) terms; an explicit reduction or comparison lemma is needed to confirm comparability.
  2. [§5] §5 (Violation Analysis): the proof that the cumulative sampling violation is sublinear relies on the probability of violation vanishing asymptotically under the bounded stochastic pipage rounding; the argument must explicitly bound the effect of any residual violation probability on the overall regret to ensure it remains o(T).
minor comments (2)
  1. [§2] Notation for the partition matroid and per-agent feasible sets should be introduced with an explicit example in §2 to clarify the distributed constraint structure.
  2. [Numerical experiments] The numerical experiments section would benefit from reporting standard deviations over multiple runs to support the validation claims.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and the recommendation for minor revision. We address each major comment below and will incorporate the suggested clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Regret Analysis): the (1-1/e)-regret bound for the bandit-feedback algorithm is stated to match centralized counterparts, but the additional communication or coordination terms arising from the distributed setting must be shown not to degrade the leading constant or the o(T) terms; an explicit reduction or comparison lemma is needed to confirm comparability.

    Authors: We appreciate this point. The regret analysis in Section 4 decomposes the distributed regret into a centralized (1-1/e)-regret term plus coordination overhead. The overhead arises only from local decisions and synchronous sharing of gradient estimates or function values, which contributes at most O(log T) per agent due to the fixed number of agents and the bounded stochastic pipage rounding. These terms are absorbed into the o(T) remainder without affecting the leading constant. To address the request explicitly, we will insert a comparison lemma (new Lemma 4.3) that formally reduces the distributed bound to the centralized one, confirming no degradation. This addition will appear in the revised Section 4. revision: yes

  2. Referee: [§5] §5 (Violation Analysis): the proof that the cumulative sampling violation is sublinear relies on the probability of violation vanishing asymptotically under the bounded stochastic pipage rounding; the argument must explicitly bound the effect of any residual violation probability on the overall regret to ensure it remains o(T).

    Authors: We agree that the interaction between residual violations and regret requires an explicit bound. In the current proof, the per-round violation probability is o(1/T), so the expected number of violations up to T is o(T). Each violation perturbs the selected set by at most one element, which changes the objective value by at most the maximum marginal gain (bounded by the problem assumptions). Consequently, the total additive effect on cumulative regret is o(T) and does not alter the (1-1/e) leading term. We will add this short calculation as a new paragraph at the end of the proof of Theorem 5.2 in the revised manuscript to make the argument self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper claims sublinear (1-1/e)-regret bounds and sublinear cumulative sampling violation for distributed online submodular maximization under partition matroid constraints, using a bounded stochastic pipage rounding scheme. These follow from the standard assumptions of monotone submodular objectives, partition matroids, and bounded independent feedback, plus the new rounding procedure. No equations, fitted parameters, or self-citations are shown that reduce the claimed bounds to definitions or inputs by construction. The derivation is self-contained against external benchmarks and standard results in submodular optimization.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no explicit free parameters, axioms, or invented entities are stated; the work relies on standard submodularity and matroid assumptions from prior literature.

pith-pipeline@v0.9.1-grok · 5675 in / 1165 out tokens · 32442 ms · 2026-07-02T15:45:47.531929+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Approximate supermodularity of Kalman filter sensor selection.IEEE Trans

    Luiz FO Chamon, George J Pappas, and Alejandro Ribeiro. Approximate supermodularity of Kalman filter sensor selection.IEEE Trans. Autom. Control, 66(1):49–63, 2020

    2020

  2. [2]

    Utility design for distributed resource allocation—part ii: Applications to submodular, covering, and supermodular problems.IEEE Trans

    Dario Paccagnan and Jason R Marden. Utility design for distributed resource allocation—part ii: Applications to submodular, covering, and supermodular problems.IEEE Trans. Autom. Control, 67(2):618–632, 2021

    2021

  3. [3]

    Risk-aware submodular optimization for multirobot coordina- tion.IEEE Trans

    Lifeng Zhou and Pratap Tokekar. Risk-aware submodular optimization for multirobot coordina- tion.IEEE Trans. Robot., 38(5):3064–3084, 2022

    2022

  4. [4]

    A threshold of ln n for approximating set cover.J

    Uriel Feige. A threshold of ln n for approximating set cover.J. ACM, 45(4):634–652, 1998

    1998

  5. [5]

    An analysis of approximations for maximizing submodular set functions—I.Math

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—I.Math. Program., 14(1):265–294, 1978

    1978

  6. [6]

    An analysis of approximations for maximizing submodular set functions—II

    Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functions—II. InPolyhedral Combinatorics, pages 73–87. Springer, 1978

    1978

  7. [7]

    A performance bound for the greedy algorithm in a generalized class of string optimization problems.IEEE Trans

    Brandon Van Over, Bowen Li, Edwin KP Chong, and Ali Pezeshki. A performance bound for the greedy algorithm in a generalized class of string optimization problems.IEEE Trans. Autom. Control, 2025

    2025

  8. [8]

    Distributed submodular maximization with limited information.IEEE Trans

    Bahman Gharesifard and Stephen L Smith. Distributed submodular maximization with limited information.IEEE Trans. Control Netw. Syst., 5(4):1635–1645, 2017

    2017

  9. [9]

    Optimality gap of decentralized submodular maximization under probabilistic communication

    Joan Vendrell and Solmaz Kia. Optimality gap of decentralized submodular maximization under probabilistic communication. InProc. IEEE Conf. Decis. Control, pages 5387–5392. IEEE, 2024

    2024

  10. [10]

    Decentralized submodular maximization: Bridging discrete and continuous settings

    Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. InInt. Conf. Mach. Learn., pages 3616–3625, 2018

    2018

  11. [11]

    Jacobi-style iteration for distributed submodular maximization.IEEE Trans

    Bin Du, Kun Qian, Christian Claudel, and Dengfeng Sun. Jacobi-style iteration for distributed submodular maximization.IEEE Trans. Autom. Control, 67(9):4687–4702, 2022

    2022

  12. [12]

    Optimal algorithms for submodular maximization with distributed constraints

    Alexander Robey, Arman Adibi, Brent Schlotfeldt, Hamed Hassani, and George J Pappas. Optimal algorithms for submodular maximization with distributed constraints. InLearn. Dyn. Control, pages 150–162, 2021

    2021

  13. [13]

    Distributed strategy selection: A submodular set function maximization approach.Automatica, 153, 2023

    Navid Rezazadeh and Solmaz S Kia. Distributed strategy selection: A submodular set function maximization approach.Automatica, 153, 2023

    2023

  14. [14]

    An online algorithm for maximizing submodular functions

    Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Adv. Neural Inf. Process. Syst., 21, 2008

    2008

  15. [15]

    Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments

    Daniel Golovin, Andreas Krause, and Matthew Streeter. Online submodular maximization under a matroid constraint with application to learning assignments.arXiv preprint arXiv:1407.1082, 2014. 18

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  16. [16]

    Online continuous submodular maximization

    Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. InInt. Conf. Artif. Intell. Stat., pages 1896–1905, 2018

    1905

  17. [17]

    Projection-free online optimization with stochastic gradient: From convexity to submodularity

    Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. InInt. Conf. Mach. Learn., pages 814–823, 2018

    2018

  18. [18]

    Online continuous submodular maximization: From full-information to bandit feedback.Adv

    Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization: From full-information to bandit feedback.Adv. Neural Inf. Process. Syst., 32, 2019

    2019

  19. [19]

    Introduction to online convex optimization.Found

    Elad Hazan et al. Introduction to online convex optimization.Found. Trends Optim., 2(3- 4):157–325, 2016

    2016

  20. [20]

    Stochastic continuous submodular maximization: Boosting via non-oblivious function

    Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. InInt. Conf. Mach. Learn., pages 26116–26134, 2022

    2022

  21. [21]

    A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback

    Guanyu Nie, Yididiya Y Nadew, Yanhui Zhu, Vaneet Aggarwal, and Christopher John Quinn. A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. InInt. Conf. Mach. Learn., pages 26166–26198, 2023

    2023

  22. [22]

    Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits

    Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits. InInt. Conf. Mach. Learn., pages 35491–35524, 2023

    2023

  23. [23]

    Communication-efficient decentralized online continuous DR-submodular maximization

    Qixin Zhang, Zengde Deng, Xiangru Jian, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Communication-efficient decentralized online continuous DR-submodular maximization. In ACM Int. Conf. Inf. Knowl. Manag., pages 3330–3339, 2023

    2023

  24. [24]

    Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination.IEEE Robot

    Zirui Xu, Hongyu Zhou, and Vasileios Tzoumas. Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination.IEEE Robot. Autom. Lett., 8(4):2261–2268, 2023

    2023

  25. [25]

    Offline and online distributed submodular maximization under a partitioned matroid constraint

    Lintao Ye, Bin Du, and Zhi-Wei Liu. Offline and online distributed submodular maximization under a partitioned matroid constraint. InProc. IEEE Conf. Decis. Control. IEEE, 2025

    2025

  26. [26]

    Optimal approximation for the submodular welfare problem in the value oracle model

    Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. InAnnu. ACM Symp. Theory Comput., pages 67–74, 2008

    2008

  27. [27]

    Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms).Res

    Jan Vondrák. Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms).Res. Inst. Math. Sci., Kyoto Univ., 23:253–266, 2010

    2010

  28. [28]

    Maximizing a monotone submodular function subject to a matroid constraint.SIAM J

    Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint.SIAM J. Comput., 40(6):1740–1766, 2011

    2011

  29. [29]

    Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. InAnnu. ACM Symp. Theory Comput., pages 783–792, 2011. 19

    2011

  30. [30]

    An algorithm for quadratic programming.Nav

    Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming.Nav. Res. Logist. Q., 3(1-2):95–110, 1956

    1956

  31. [31]

    Guaranteed non-convex optimization: Submodular maximization over continuous domains

    Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non-convex optimization: Submodular maximization over continuous domains. InArtif. Intell. Stat., pages 111–120, 2017

    2017

  32. [32]

    Following the perturbed leader for online structured learning

    Alon Cohen and Tamir Hazan. Following the perturbed leader for online structured learning. InInt. Conf. Mach. Learn., pages 1034–1042, 2015

    2015

  33. [33]

    Online convex programming and generalized infinitesimal gradient ascent

    Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Int. Conf. Mach. Learn., pages 928–936, 2003

    2003

  34. [34]

    Stochastic conditional gradient methods: From convex minimization to submodular maximization.J

    Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization.J. Mach. Learn. Res., 21(105):1–49, 2020

    2020

  35. [35]

    Black box submodular maxi- mization: Discrete and continuous settings

    Lin Chen, Mingrui Zhang, Hamed Hassani, and Amin Karbasi. Black box submodular maxi- mization: Discrete and continuous settings. InInt. Conf. Artif. Intell. Stat., pages 1058–1070, 2020

    2020

  36. [36]

    On the distribution of the number of successes in independent trials.Ann

    Leon Jay Gleser. On the distribution of the number of successes in independent trials.Ann. Probab., pages 182–188, 1975

    1975

  37. [37]

    On the distribution of the number of successes in independent trials.Ann

    Wassily Hoeffding. On the distribution of the number of successes in independent trials.Ann. Math. Stat., pages 713–721, 1956. 20 Appendix Contents 1 Introduction 1 2 Problem Statement and Preliminaries 4 2.1 Distributed Online Submodular Maximization . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Multi-Linear Extension . . . . . . . . . . . . . . . . ...

    1956