Pith. sign in

REVIEW 1 major objections 6 minor 1 cited by

Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency

T0 review · 1 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Two decentralized algorithms hit a tight approximation for multi-agent submodular coordination on sparse networks.

desk verdict A solid curvature-aware surrogate for multi-agent submodular coordination with a fixable gap in Lemma 12; the main result likely survives. read the letter →

arxiv 2502.05028 v1 pith:Q3FHRWQ6 submitted 2025-02-07 cs.MA cs.LGmath.OC

Qixin Zhang , Zongqi Wan , Yu Yang , Li Shen , Dacheng Tao This is my paper · ORCID
classification cs.MAcs.LGmath.OC MSC 90C2768W27
keywords multi-agentsubmodularcoordinationonlinemaximizationmultilinearextensionsurrogategradientdynamicregretdecentralizedoptimizationprojection-freemirrorascentcurvature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks whether a team of agents jointly maximizing a sequence of unknown submodular utility functions can reach the tight $(1-e^{-c})/c$ approximation ratio over a connected, sparse communication graph, instead of requiring full connectivity. The authors propose two algorithms, MA-OSMA and its projection-free variant MA-OSEA, and prove that both achieve dynamic regret $\widetilde{O}(\sqrt{C_T T/(1-\beta)})$ against a $(1-e^{-c})/c$ fraction of the best hindsight action set, where $C_T$ measures drift of the optimal set and $\beta$ is the spectral gap of the network. This improves the previous $1/(1+c)$ guarantee of the OSG algorithm and removes the complete-graph requirement. Simulations on multi-target tracking show the new methods outperforming OSG even over random graphs with average degree four.

What carries the argument

The load-bearing object is the surrogate function $F^s(x)=\int_0^1 e^{c(z-1)}F(z*x)\,dz$, where $F$ is the multilinear extension of the submodular objective and $*$ denotes scalar multiplication of the vector $x$. Its gradient is a weighted average of gradients of $F$ along the ray from the origin to $x$, and Theorem 2 shows that stationary points of $F^s$ satisfy the tight $(1-e^{-c})/c$ approximation inequality. The algorithms combine this surrogate with Bregman-divergence mirror ascent (Euclidean for MA-OSMA, KL for MA-OSEA), consensus averaging over a doubly stochastic weight matrix for information aggregation, and a divide-and-conquer coordinate update that only evaluates marginal gains on each agent's own action set; MA-OSEA mixes in a uniform distribution to make the KL update closed-form and projection-free.

What would settle it

Take a two-element coverage function $f(\{1\})=f(\{2\})=1$, $f(\{1,2\})=2$, which has curvature $c=1$, and compare $x=(\epsilon,0)$ with $y=(0,0)$. Then $F(x)-F(y)=\epsilon$ while $G=(1-e^{-1})\approx 0.632$, so the claimed bound $G\|x-y\|$ is violated for every $\epsilon>0$. Directly computing $\|\nabla F(x)\|_\infty = 1$ contradicts the value $G=(1-e^{-c})/c$ used in Assumption 5 in the proof of Lemma 12.

Watch

Extended reading notes

Core claim

The central claim is that a curvature-aware surrogate gradient for the multilinear extension converts stationary points into $(1-e^{-c})/c$-approximate maximizers, and that this surrogate can be optimized in a decentralized online manner over any connected undirected graph. The key inequality (Theorem 2) reads $\langle y-x, \nabla F^s(x)\rangle \ge \frac{1-e^{-c}}{c}F(y) - F(x)$ for $F^s(x)=\int_0^1 e^{c(z-1)}F(z*x)\,dz$, where $F$ is the multilinear extension of the monotone submodular objective with curvature $c$. Combining this surrogate with consensus averaging, Bregman-divergence mirror ascent, and a coordinate-wise update that uses only each agent's own marginal gains, the paper proves regret bounds for MA-OSMA (Theorem 3) and MA-OSEA (Theorem 5) against the best dynamic comparator. The projection-free MA-OSEA achieves the same approximation while replacing the mirror projection with a closed-form KL-divergence update obtained by mixing a uniform distribution, at the cost of only logarithmic factors.

Load-bearing premise

The proof that the regret bound holds (Lemma 12, Appendix D) uses a Lipschitz bound $|F_t(x)-F_t(y)| \le G\|x-y\|$, but Assumption 5 only bounds the surrogate gradient and its smoothness; the multilinear extension $F_t$ itself is Lipschitz with constant $m_f=\max_a f(\{a\})$, which can exceed $G$ when $c<1$, so the regret decomposition as written is not established.

Editorial extensions

If this is right

  • If the bounds hold, multi-agent online submodular coordination is solvable with the tight curvature-aware approximation on connected sparse graphs, removing the complete-DAG requirement of OSG.
  • The regret rate $\widetilde{O}(\sqrt{C_T T/(1-\beta)})$ degrades gracefully with network spectral gap $\beta$, so the method remains useful on poorly connected topologies.
  • The projection-free MA-OSEA achieves the same approximation guarantee with $O(n\log(1/\epsilon)/\epsilon^2)$ value queries in the offline setting, improving on the $O(n\log(1/\epsilon)/\epsilon^3)$ query complexity of distributed continuous greedy.
  • The curvature-aware surrogate construction extends non-oblivious boosting from single-agent continuous submodular maximization to decentralized multi-agent settings.
  • Numerical experiments on multi-target tracking show that both algorithms outperform the OSG baseline on running-average utility, target coverage, and average distance, even on random communication graphs with average degree 4.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The regret decomposition suggests that in slowly drifting environments (small $C_T$), the tight approximation ratio dominates the error, so the $(1-e^{-c})/c$ improvement over $1/(1+c)$ is most visible precisely when the environment is nearly static.
  • The same surrogate-plus-consensus recipe could be applied to other discrete constraints, such as matroid or partition matroid constraints, where each agent controls a block of elements and consensus replaces global information sharing.
  • Combining the surrogate gradient with variance-reduced estimators, as done in recent decentralized DR-submodular work, may reduce the number of value queries per round while preserving the same regret rate.
  • A parameter-free variant that adapts to unknown curvature $c$ online would make the method directly deployable without prior curvature knowledge, a direction the paper explicitly leaves open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies multi-agent online monotone submodular maximization, where each of N agents selects one action per round and the team observes a sequence of submodular objectives. It proposes two algorithms: MA-OSMA, a consensus-based online mirror ascent using a curvature-aware surrogate gradient for the multilinear extension, and MA-OSEA, a projection-free entropic variant obtained by mixing a uniform distribution. The central theoretical claims are that both algorithms achieve regret O~(sqrt(C_T T/(1-beta))) against a ((1-e^{-c})/c)-approximation to the best action set in hindsight, improving the (1/(1+c))-approximation of OSG and removing the complete-graph requirement. The proof architecture is: Theorem 2 derives the surrogate inequality from curvature, Lemmas 8-9 control consensus error, Lemma 10-12 translate continuous progress into regret against the discrete comparator, and Lemma 13 links the rounded actions to the multilinear extension. Experiments on simulated multi-target tracking compare the two proposals with OSG over complete and sparse random graphs.

Significance. If the proof gap identified below is repaired, this is a substantial advance over the previous state of the art: it gives the tight curvature-dependent approximation ratio instead of (1/(1+c)), it replaces the complete directed graph with a connected undirected graph, and it makes the regret depend explicitly on the spectral gap beta. The paper also derives the surrogate inequality from first principles rather than importing it as an assumption, and it gives concrete closed-form updates for the projection-free variant. The claimed rates and approximation ratios are falsifiable and clearly stated. The main weakness is a local but load-bearing Lipschitz claim in Lemma 12 that is not implied by Assumption 5; the defect appears fixable within the manuscript's scope.

major comments (1)
  1. [Appendix D, Lemma 12; Assumption 5; Appendix A.2] The proof of Lemma 12 asserts: "From Assumption 5, we also can show that |F_t(x)-F_t(y)| <= G||x-y||." This is not implied by Assumption 5, which bounds the stochastic surrogate gradient and the smoothness of the surrogate gradient, not the Lipschitz constant of the multilinear extension F_t itself. Appendix A.2 explicitly sets G = ((1-e^{-c})/c) max_{a,t} f_t({a}), while the natural Lipschitz constant of F_t under the l1 norm is m_f = max_a f_t({a}). Since (1-e^{-c})/c < 1 for every c>0, the displayed bound is false under the paper's own choice of G; for example, f(S)=min(|S|,1) on a two-element ground set has m_f=1, c=1, and G=1-1/e, while F(x1,x2)=x1+x2-x1x2 has Lipschitz constant 1. This Lipschitz step controls the consensus-error term |F_t(sum_i x_{t,i} ⊙ 1_{V_i}) - F_t(bar{x}_t)|, so Theorem 3 and, via Lemma 21, Theorem 5 are not fully proved as written. The gap is local and repairable: taking G = m_f in Assumption 5 makes the Lipschitz bound valid and preserves the O~(sqrt(C_T T/(1-beta))) rate with larger constants, so the overall contribution remains credible.
minor comments (6)
  1. [Assumption 5] Assumption 5 says "Ft is also L-smooth" but then bounds ||nabla F^s_t(x) - nabla F^s_t(y)||; the notation conflates the multilinear extension F_t with its surrogate F^s_t. The statement should distinguish the two functions, especially because Lemma 12 needs a Lipschitz property of F_t while Appendix A.2 computes smoothness of F^s_t.
  2. [Algorithm 2, Line 9] Line 9 aggregates y_{t,i} = sum_j w_{ij} x_{t,j}, but the exchange step in Line 8 exchanges hat{x}_{t,i} and the proof in Eq. (30) uses hat{x}_{t,j}. This is inconsistent; Line 9 should presumably read y_{t,i} = sum_j w_{ij} hat{x}_{t,j}.
  3. [Lemma 8, Appendix D] The proof states that 1-strong convexity gives D_phi(y,x+) + D_phi(x+,y) >= ||x+ - y||; the correct consequence is >= ||x+ - y||^2 (up to the strong-convexity constant). The subsequent Young-inequality step then yields ||r|| <= eta ||g||, so the lemma's conclusion is standard, but the displayed chain should be corrected.
  4. [Equation (7)] The mirror-projection update in Eq. (7) omits the box constraint b in [0,1]^{n_i}; the box constraint appears later in Lemma 7 and in the surrounding text, so this is a presentation issue rather than a substantive one.
  5. [Theorem 5 vs. Theorem 3] The constant C1 in Theorem 5 is (4G^2 + LDG)N^{3/2}, while the corresponding constant in Theorem 3 is (4G + LDG)N^{3/2}. The proof of Lemma 21 indeed produces G^2 terms, so the dimensionally different expressions should be reconciled in the statement.
  6. [Figure 3] Several legends and captions are inconsistent: for example, panel (e) lists "MA-OSMA-r" twice and omits "MA-OSEA-r", and some subcaptions say "MA-OSEA-c" twice. These should be corrected for reproducibility.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: surrogate bound is proved from curvature, not imported from cited work; self-citations are non-load-bearing.

full rationale

The core approximation inequality (Theorem 2, Eq. (4)) is established in Appendix C: it follows from the definition of curvature c, Lemma 4, and standard monotone-submodular multi-linear extension properties (Lemmas 1-3). The citations to Zhang et al. (2022, 2024) and Wan et al. (2023) only motivate the surrogate-family ansatz; the specific curvature-weighted surrogate and its inequality are derived in the paper, so the (1-e^{-c})/c approximation is not imported by citation. The regret theorems (Theorem 3, Remark 8; Theorem 5, Remark 9) are likewise self-contained given Assumptions 1-5; no parameter is fitted to the target regret and then renamed a prediction. G and L are explicit, norm-dependent constants computed in Appendix A.2 from m_f and c. The only self-citation of note is 'In line with the works (Zhang et al., 2022; 2024; Wan et al., 2023)' (Section 3.1), which is motivational and not load-bearing. One genuine support gap exists, unrelated to circularity: Lemma 12 (Appendix D) asserts 'From Assumption 5... |F_t(x)-F_t(y)| ≤ G||x-y||', but Assumption 5 bounds the surrogate gradient, and the natural Lipschitz constant of F_t is m_f (or its l1/l2 rescaled version), not the smaller surrogate constant G = ((1-e^{-c})/c) m_f; the consensus-error step is therefore not established as written, though the regret rate survives with m_f. This is a correctness issue, not a circular reduction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central result is derived from the curvature definition, standard submodularity lemmas, and consensus assumptions. No new physical entities and no fitted constants are introduced. The main caveat is that the step size and mixing parameter are set using unknown problem-dependent quantities C_T and beta, and the proof contains an unproven Lipschitz step.

free parameters (2)
  • step size eta_t = 1/sqrt(T) in experiments; O(sqrt((1-beta) C_T / T)) in theory
    The regret bound requires eta_t to depend on the unknown path length C_T and spectral gap beta; in simulations it is set by hand to 1/sqrt(T). This is a tunable hyperparameter, not fitted to the data.
  • mixing parameter gamma = O(T^{-2}) in theory
    Used only in MA-OSEA to keep the KL divergence well-defined; chosen by theory, not fitted to data.
assumptions (5)
  • domain assumption The communication graph G is connected and W is symmetric, doubly stochastic, with positive diagonal (Assumption 2).
    Used to guarantee consensus averaging and beta<1; standard in decentralized optimization.
  • domain assumption Bregman divergence satisfies separate convexity (Assumption 3).
    Used in Lemma 11 to cancel consensus errors; holds for Euclidean and KL divergences.
  • domain assumption Bregman divergence is K-Lipschitz (Assumption 4).
    Used for the dynamic-comparator term in Theorem 3; not satisfied by KL, which is why MA-OSEA needs the mixing modification.
  • domain assumption The stochastic surrogate gradient is unbiased and bounded, and the surrogate function is L-smooth (Assumption 5).
    Derived in Appendix A.2 for submodular functions with curvature c; bounds G and L in terms of the maximum singleton value.
  • standard math The optimal value of the continuous relaxation Eq. (3) equals that of the discrete problem Eq. (1).
    Invoked in Appendix D and E via Calinescu et al. and Chekuri et al.; standard for monotone submodular maximization under matroid-type constraints.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency." pith.science (2026). https://pith.science/paper/Q3FHRWQ6

@misc{pith2026250205028,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q3FHRWQ6}},
  note         = {Machine review of arXiv:2502.05028}
}
abstract

Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications in machine learning, robot planning and control. The existing approaches, such as the OSG algorithm, are often hindered by their poor approximation guarantees and the rigid requirement for a fully connected communication graph. To address these challenges, we firstly present a $\textbf{MA-OSMA}$ algorithm, which employs the multi-linear extension to transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, $\textbf{MA-OSMA}$ leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations in $\textbf{MA-OSMA}$, we also introduce a projection-free $\textbf{MA-OSEA}$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms achieve a regret bound of $\widetilde{O}(\sqrt{\frac{C_{T}T}{1-\beta}})$ against a $(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximizer sequence, $\beta$ is the spectral gap of the network and $c$ is the joint curvature of submodular objectives. This result significantly improves the $(\frac{1}{1+c})$-approximation provided by the state-of-the-art OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-based multi-target tracking.

Figures

Figures reproduced from arXiv: 2502.05028 by the authors.

Figure 1
Figure 1. Left: Multi-target tracking with 4 mobile sensors over a complete directed acyclic commu￾nication network. Right: Multi-target tracking with 4 sensors over a connected undirected graph. To tackle the aforementioned MA-OSM problem, Xu et al. (2023) have recently proposed an online sequential greedy (OSG) algorithm, building upon the foundations of the classical greedy method (Fisher et al., 1978). Nevertheless, this … view at source ↗
Figure 2
Figure 2. 1 1+c v.s. 1−e−c c . Theorem 1 suggests that applying various gradient-based methods directly to multi-linear extension only can ensure a 1 1+c -approximation guarantee. However, the known tight approximation ratio for maximizing a monotone submodular function with curvature c is 1−e −c c (Vondrak´ , 2010; Bian et al., 2017a). As depicted in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Comparison of average cumulative utility, average number of targets within 5 units, average [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization

    eess.SY 2026-02 conditional novelty 7.0 of 10

    ANACONDA lets each agent jointly learn its action and its one-hop communication neighborhood via bandit exploration, with suboptimality bounds that stay positive even for disconnected networks.

Reference graph

Works this paper leans on

92 extracted references · 69 canonical work pages · cited by 1 Pith paper

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Finding approximate local minima faster than gradient descent

    Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 1195--1199, 2017

    2017

  3. [3]

    New local search approximation techniques for maximum generalized satisfiability problems

    Paola Alimonti. New local search approximation techniques for maximum generalized satisfiability problems. In Italian Conference on Algorithms and Complexity, pp.\ 40--53. Springer, 1994

    1994

  4. [4]

    Decentralized active information acquisition: Theory and application to multi-robot slam

    Nikolay Atanasov, Jerome Le Ny, Kostas Daniilidis, and George J Pappas. Decentralized active information acquisition: Theory and application to multi-robot slam. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp.\ 4775--4782. IEEE, 2015

    2015

  5. [5]

    Diverse client selection for federated learning via submodular maximization

    Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022

    2022

  6. [6]

    Joint and separate convexity of the bregman distance

    Heinz H Bauschke and Jonathan M Borwein. Joint and separate convexity of the bregman distance. In Studies in Computational Mathematics, volume 8, pp.\ 23--36. Elsevier, 2001

    2001

  7. [7]

    Guarantees for greedy maximization of non-submodular functions with applications

    Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In International conference on machine learning, pp.\ 498--507. PMLR, 2017 a

    2017

  8. [8]

    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. In Artificial Intelligence and Statistics, pp.\ 111--120. PMLR, 2017 b

    2017

Show all 92 references
  1. [9]

    Continuous submodular function maximization

    Yatao Bian, Joachim M Buhmann, and Andreas Krause. Continuous submodular function maximization. arXiv preprint arXiv:2006.13474, 2020

    2006 arXiv

  2. [10]

    An o (n) algorithm for quadratic knapsack problems

    Peter Brucker. An o (n) algorithm for quadratic knapsack problems. Operations Research Letters, 3 0 (3): 0 163--166, 1984

    1984

  3. [11]

    Maximizing a monotone submodular function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondr \'a k. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40 0 (6): 0 1740--1766, 2011

    2011

  4. [12]

    Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chandra Chekuri, Jan Vondr \'a k, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43 0 (6): 0 1831--1879, 2014

    2014

  5. [13]

    Convergence analysis of a proximal-like minimization algorithm using bregman functions

    Gong Chen and Marc Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3 0 (3): 0 538--543, 1993

    1993

  6. [14]

    Online continuous submodular maximization

    Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In International Conference on Artificial Intelligence and Statistics, pp.\ 1896--1905. PMLR, 2018

    1905

  7. [15]

    Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem

    Michele Conforti and G \'e rard Cornu \'e jols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete applied mathematics, 7 0 (3): 0 251--274, 1984

    1984

  8. [16]

    Scalable distributed planning for multi-robot, multi-target tracking

    Micah Corah and Nathan Michael. Scalable distributed planning for multi-robot, multi-target tracking. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp.\ 437--444. IEEE, 2021

    2021

  9. [17]

    Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection

    Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19 0 (3): 0 1--34, 2018

    2018

  10. [18]

    Jacobi-style iteration for distributed submodular maximization

    Bin Du, Kun Qian, Christian Claudel, and Dengfeng Sun. Jacobi-style iteration for distributed submodular maximization. IEEE transactions on automatic control, 67 0 (9): 0 4687--4702, 2022

    2022

  11. [19]

    Turning down the noise in the blogosphere

    Khalid El-Arini, Gaurav Veda, Dafna Shahaf, and Carlos Guestrin. Turning down the noise in the blogosphere. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp.\ 289--298, 2009

    2009

  12. [20]

    Combatting dimensional collapse in llm pre-training data via diversified file selection

    Ziqing Fan, Siyuan Du, Shengchao Hu, Pingjie Wang, Li Shen, Zhang Ya, Dacheng Tao, and Yanfeng Wang. Combatting dimensional collapse in llm pre-training data via diversified file selection. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  13. [21]

    Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018

    2018

  14. [22]

    The power of local search: Maximum coverage over a matroid

    Yuval Filmus and Justin Ward. The power of local search: Maximum coverage over a matroid. In 29th Symposium on Theoretical Aspects of Computer Science, volume 14, pp.\ 601--612. LIPIcs, 2012

    2012

  15. [23]

    Monotone submodular maximization over a matroid via non-oblivious local search

    Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, 43 0 (2): 0 514--542, 2014

    2014

  16. [24]

    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. In Polyhedral Combinatorics, pp.\ 73--87. Springer, 1978

    1978

  17. [25]

    On the convergence of distributed stochastic bilevel optimization algorithms over a network

    Hongchang Gao, Bin Gu, and My T Thai. On the convergence of distributed stochastic bilevel optimization algorithms over a network. In International Conference on Artificial Intelligence and Statistics, pp.\ 9238--9281. PMLR, 2023

    2023

  18. [26]

    Distributed submodular maximization with limited information

    Bahman Gharesifard and Stephen L Smith. Distributed submodular maximization with limited information. IEEE transactions on control of network systems, 5 0 (4): 0 1635--1645, 2017

    2017

  19. [27]

    Cvx: Matlab software for disciplined convex programming, version 2.1, 2014

    Michael Grant and Stephen Boyd. Cvx: Matlab software for disciplined convex programming, version 2.1, 2014

    2014

  20. [28]

    The impact of information in distributed submodular maximization

    David Grimsman, Mohd Shabbir Ali, Joao P Hespanha, and Jason R Marden. The impact of information in distributed submodular maximization. IEEE Transactions on Control of Network Systems, 6 0 (4): 0 1334--1343, 2018

    2018

  21. [29]

    Gradient methods for submodular maximization

    Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pp.\ 5841--5851, 2017

    2017

  22. [30]

    Introduction to online convex optimization

    Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization , 2 0 (3-4): 0 157--325, 2016

    2016

  23. [31]

    Matrix analysis

    Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012

    2012

  24. [32]

    Online optimization: Competing with dynamic comparators

    Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pp.\ 398--406. PMLR, 2015

    2015

  25. [33]

    Metaxas, and Marco Pavone

    Can Jin, Tong Che, Hongwu Peng, Yiyuan Li, Dimitris N. Metaxas, and Marco Pavone. Learning from teaching regularization: Generalizable correlations should be easy to imitate. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 a

    2024

  26. [34]

    Visual prompting upgrades neural network sparsification: A data-model perspective

    Can Jin, Tianjin Huang, Yihua Zhang, Mykola Pechenizkiy, Sijia Liu, Shiwei Liu, and Tianlong Chen. Visual prompting upgrades neural network sparsification: A data-model perspective. In The 39th Annual AAAI Conference on Artificial Intelligence, 2024 b

    2024

  27. [35]

    Apeer: Automatic prompt engineering enhances large language model reranking

    Can Jin, Hongwu Peng, Shiyu Zhao, Zhenting Wang, Wujiang Xu, Ligong Han, Jiahui Zhao, Kai Zhong, Sanguthevar Rajasekaran, and Dimitris N Metaxas. Apeer: Automatic prompt engineering enhances large language model reranking. arXiv preprint arXiv:2406.14449, 2024 c

    2024 arXiv

  28. [36]

    How to escape saddle points efficiently

    Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pp.\ 1724--1732. PMLR, 2017

    2017

  29. [37]

    Playing games with approximation algorithms

    Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp.\ 546--555, 2007

    2007

  30. [38]

    Maximizing the spread of influence through a social network

    David Kempe, Jon Kleinberg, and \'E va Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.\ 137--146, 2003

    2003

  31. [39]

    On syntactic versus computational views of approximability

    Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. SIAM Journal on Computing, 28 0 (1): 0 164--191, 1998

    1998

  32. [40]

    Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies

    Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9 0 (2), 2008

    2008

  33. [41]

    An end-to-end submodular framework for data-efficient in-context learning

    Lilly Kumari, Shengjie Wang, Arnav Das, Tianyi Zhou, and Jeff Bilmes. An end-to-end submodular framework for data-efficient in-context learning. In Findings of the Association for Computational Linguistics: NAACL 2024, pp.\ 3293--3308, 2024

    2024

  34. [42]

    Convergence rate of frank-wolfe for non-convex objectives

    Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXiv:1607.00345, 2016

    2016 arXiv

  35. [43]

    Functional analysis

    Peter D Lax. Functional analysis. John Wiley & Sons, 2014

    2014

  36. [44]

    Submodularity of optimal sensor placement for traffic networks

    Ruolin Li, Negar Mehr, and Roberto Horowitz. Submodularity of optimal sensor placement for traffic networks. Transportation research part B: methodological, 171: 0 29--43, 2023

    2023

  37. [45]

    Improved projection-free online continuous submodular maximization

    Yucheng Liao, Yuanyu Wan, Chang Yao, and Mingli Song. Improved projection-free online continuous submodular maximization. arXiv preprint arXiv:2305.18442, 2023

    2023 arXiv

  38. [46]

    Multi-document summarization via budgeted maximization of submodular functions

    Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp.\ 912--920, 2010

    2010

  39. [47]

    A class of submodular functions for document summarization

    Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp.\ 510--520, 2011

    2011

  40. [48]

    Distributed resilient submodular action selection in adversarial environments

    Jun Liu, Lifeng Zhou, Pratap Tokekar, and Ryan K Williams. Distributed resilient submodular action selection in adversarial environments. IEEE Robotics and Automation Letters, 6 0 (3): 0 5832--5839, 2021

    2021

  41. [49]

    The role of information in distributed resource allocation

    Jason R Marden. The role of information in distributed resource allocation. IEEE Transactions on Control of Network Systems, 4 0 (3): 0 654--664, 2016

    2016

  42. [50]

    Fast constrained submodular maximization: Personalized data summarization

    Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning, pp.\ 1358--1367. PMLR, 2016 a

    2016

  43. [51]

    Distributed submodular maximization

    Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization. The Journal of Machine Learning Research, 17 0 (1): 0 8330--8373, 2016 b

    2016

  44. [52]

    Decentralized submodular maximization: Bridging discrete and continuous settings

    Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp.\ 3616--3625. PMLR, 2018

    2018

  45. [53]

    Distributed optimization over time-varying directed graphs

    Angelia Nedi \'c and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60 0 (3): 0 601--615, 2014

    2014

  46. [54]

    Distributed subgradient methods for multi-agent optimization

    Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54 0 (1): 0 48--61, 2009

    2009

  47. [55]

    Achieving geometric convergence for distributed optimization over time-varying graphs

    Angelia Nedi \'c , Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27 0 (4): 0 2597--2633, 2017

    2017

  48. [56]

    An analysis of approximations for maximizing submodular set functions—i

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming, 14 0 (1): 0 265--294, 1978

    1978

  49. [57]

    Nemirovsky and D.B

    A.S. Nemirovsky and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience series in discrete mathematics. Wiley, 1983

    1983

  50. [58]

    Introductory Lectures on Convex Optimization: A Basic Course, volume 87

    Y Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013

    2013

  51. [59]

    An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

    Panos M Pardalos and Naina Kovoor. An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Mathematical Programming, 46: 0 321--328, 1990

    1990

  52. [60]

    A unified approach for maximizing continuous dr-submodular functions

    Mohammad Pedramfar, Christopher Quinn, and Vaneet Aggarwal. A unified approach for maximizing continuous dr-submodular functions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp.\ 6...

    2023

  53. [61]

    Nadew, Christopher John Quinn, and Vaneet Aggarwal

    Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, and Vaneet Aggarwal. Unified projection-free algorithms for adversarial dr-submodular optimization. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024 , 2024

    2024

  54. [62]

    Near-optimal multi-agent learning for safe coverage control

    Manish Prajapat, Matteo Turchetta, Melanie Zeilinger, and Andreas Krause. Near-optimal multi-agent learning for safe coverage control. Advances in Neural Information Processing Systems, 35: 0 14998--15012, 2022

    2022

  55. [63]

    Distributed stochastic gradient tracking methods

    Shi Pu and Angelia Nedi \'c . Distributed stochastic gradient tracking methods. Mathematical Programming, 187 0 (1): 0 409--457, 2021

    2021

  56. [64]

    Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions

    Guannan Qu, Dave Brown, and Na Li. Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica, 105: 0 206--215, 2019

    2019

  57. [65]

    Decomposable submodular maximization in federated setting

    Akbar Rafiey. Decomposable submodular maximization in federated setting. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27 , 2024

    2024

  58. [66]

    Distributed strategy selection: A submodular set function maximization approach

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

    2023

  59. [67]

    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. In Learning for Dynamics and Control, pp.\ 150--162. PMLR, 2021

    2021

  60. [68]

    Resilient active information acquisition with teams of robots

    Brent Schlotfeldt, Vasileios Tzoumas, and George J Pappas. Resilient active information acquisition with teams of robots. IEEE Transactions on Robotics, 38 0 (1): 0 244--261, 2021

    2021

  61. [69]

    Distributed online optimization in dynamic environments using mirror descent

    Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 63 0 (3): 0 714--725, 2017

    2017

  62. [70]

    Efficient informative sensing using multiple robots

    Amarjeet Singh, Andreas Krause, Carlos Guestrin, and William J Kaiser. Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34: 0 707--755, 2009

    2009

  63. [71]

    An online algorithm for maximizing submodular functions

    Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems, pp.\ 1577--1584, 2008

    2008

  64. [72]

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

    Jan Vondr \'a k. Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms). RIMS Kokyuroku Bessatsu B, 23:253–266,, 23: 0 253--266, 2010

    2010

  65. [73]

    Symmetry and approximability of submodular maximization problems

    Jan Vondr \'a k. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42 0 (1): 0 265--304, 2013

    2013

  66. [74]

    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. In International Conference on Machine Learning, pp.\ 35491--35524. PMLR, 2023

    2023

  67. [75]

    An empirical study of user engagement in influencer marketing on weibo and wechat

    Jun Wang, Yu Yang, Qi Liu, Zheng Fang, Shujuan Sun, and Yabo Xu. An empirical study of user engagement in influencer marketing on weibo and wechat. IEEE Transactions on Computational Social Systems, 10 0 (6): 0 3228--3240, 2022

    2022

  68. [76]

    Using document summarization techniques for speech data subset selection

    Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, ...

    2013

  69. [77]

    Submodularity in data subset selection and active learning

    Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pp.\ 1954--1963. PMLR, 2015

    1954

  70. [78]

    Decentralized gradient tracking for continuous dr-submodular maximization

    Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, and Hui Qian. Decentralized gradient tracking for continuous dr-submodular maximization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp.\ 2897--2906. PMLR, 2019

    2019

  71. [79]

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

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

    2023

  72. [80]

    On the convergence of decentralized gradient descent

    Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26 0 (3): 0 1835--1854, 2016

    2016

  73. [81]

    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. In International Conference on Machine Learning, pp.\ 26116--26134. PMLR, 2022

    2022

  74. [82]

    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 Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp.\ 3330--3339, 2023

    2023

  75. [83]

    Boosting gradient ascent for continuous dr-submodular maximization

    Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint arXiv:2401.08330, 2024

    2024 arXiv

  76. [84]

    Minimax optimal q learning with nearest neighbors

    Puning Zhao and Lifeng Lai. Minimax optimal q learning with nearest neighbors. IEEE Transactions on Information Theory, 2024

    2024

  77. [85]

    A huber loss minimization approach to mean estimation under user-level differential privacy

    Puning Zhao, Lifeng Lai, Li Shen, Qingming Li, Jiafei Wu, and Zhe Liu. A huber loss minimization approach to mean estimation under user-level differential privacy. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 a

    2024

  78. [86]

    A huber loss minimization approach to byzantine robust federated learning

    Puning Zhao, Fei Yu, and Zhiguo Wan. A huber loss minimization approach to byzantine robust federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp.\ 21806--21814, 2024 b

    2024

  79. [87]

    Risk-aware submodular optimization for multirobot coordination

    Lifeng Zhou and Pratap Tokekar. Risk-aware submodular optimization for multirobot coordination. IEEE Transactions on Robotics, 38 0 (5): 0 3064--3084, 2022

    2022

  80. [88]

    Resilient active target tracking with multiple robots

    Lifeng Zhou, Vasileios Tzoumas, George J Pappas, and Pratap Tokekar. Resilient active target tracking with multiple robots. IEEE Robotics and Automation Letters, 4 0 (1): 0 129--136, 2018

    2018

  81. [89]

    Projection-free decentralized online learning for submodular maximization over time-varying networks

    Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, and Keqin Li. Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 22 0 (51): 0 1--42, 2021

    2021

  82. [90]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  83. [91]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  84. [92]

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.