More Like this

1. Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

   Fourati, Fares; Aggarwal, Vaneet; Quinn, Christopher John; Alouini, Mohamed-Slim (April 2023, Proceedings of the International Workshop on Artificial Intelligence and Statistics)

   We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a $$\frac{1}{2}$$-regret upper bound of $$\Tilde{\mathcal{O}}(n T^{\frac{2}{3}})$$ for horizon $$T$$ and number of arms $$n$$. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings. 

   more » « less
2. Differentially Private Decomposable Submodular Maximization

   Chaturvedi, Anamay; Nguyễn, Huy Lê; Zakynthinou, Lydia (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance. 

   more » « less
3. Submodular maximization with matroid and packing constraints in parallel

   https://doi.org/10.1145/3313276.3316389  

   Ene, Alina; Nguyen, Huy L.; Vladu, Adrian (June 2019, ACM SIGACT Symposium on Theory of Computing)

   We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $$1-1/e-\epsilon$$ approximation for monotone functions and a $$1/e-\epsilon$$ approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $$O(\log^2{n}/\epsilon^3)$$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a $$1/e-\epsilon$$ approximation using $$O(\log(n/\epsilon) \log(1/\epsilon) \log(n+m)/ \epsilon^2)$$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $$1-1/e-\epsilon$$ approximation in $$O(\log(n/\epsilon)\log(m)/\epsilon^2)$$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function. 

   more » « less
4. A Local Search Algorithm for the Min-Sum Submodular Cover Problem

   https://doi.org/10.4230/LIPIcs.ISAAC.2022.3  

   Hellerstein, Lisa; Lidbetter, Thomas; Witter, R Teal (January 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bae, Sang Won; Park, Heejin (Ed.)

   We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets. 

   more » « less
5. An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization

   Roughgarden, Tim; Wang, Joshua R. (July 2018, 31st Annual Conference on Learning Theory (COLT))

   This paper considers a basic problem at the interface of submodular optimization and online learning. In the online unconstrained submodular maximization problem, there is a universe [n] = {1, 2, . . . , n} and a sequence of T nonnegative (not necessarily monotone) submodular functions arrive over time. The goal is to design a computationally efficient online algorithm, which chooses a subset of [n] at each time step as a function only of the past, such that the accumulated value of the chosen subsets is as close as possible to the maximum total value of a fixed subset in hindsight. Our main result is a polynomial time no-1/2-regret algorithm for this problem, meaning that for every sequence of nonnegative submodular functions, the algorithm’s expected total value is at least 1/2 times that of the best subset in hindsight, up to an error term sublinear in T. The factor of 1/2 cannot be improved upon by any polynomial-time online algorithm when the submodular functions are presented as value oracles. 

   more » « less