Revisiting stochastic submodular maximization with cardinality constraint: A bandit perspective
Authors: Pratik Jawanpuria
Bamdev Mishra
Karthik S. Gurumoorthy
Venue: Accepted by TMLR ()

Abstract: In this paper, we focus on the problem of maximizing non-negative, monotone, stochastic submodular functions under cardinality constraint. Recent works have explored continuous optimization algorithms via multi-linear extensions for such problems and provided appropriate approximation guarantees. We take a fresh look into this problem from a discrete, (stochastic) greedy perspective under a probably approximately correct (PAC) setting, i.e., the goal is to obtain solutions whose expected objective value is greater than or equal to $(1-1/e-\epsilon){\rm OPT}-\nu$ with at least $1-\delta$ probability, where ${\rm OPT}$ is the optimal objective value. Using the theory of multi-armed bandits, we propose novel bandit stochastic greedy (BSG) algorithms in which selection of the next element at iteration $i$ is posed as a $(\nu_i,\delta_i)$-PAC best-arm identification problem. Given $(\nu,\delta)$-PAC parameters to BSG, we formally characterize a set $\mathcal{A}(\nu,\delta)$ of per-iteration policies such that any policy from this set guarantees a $(\nu,\delta)$-PAC solution for the stochastic submodular maximization problem using BSG. We next discuss the problem of learning a policy in $\mathcal{A}(\nu,\delta)$ by minimizing the computational cost. With our learned policy, we show that BSG has lower computational cost than existing stochastic submodular maximization approaches. An interesting outcome of our analysis is the development of both linear and almost-linear time algorithms for the exemplar based clustering problem with $(1-1/e-\epsilon)$-approximation guarantee under a PAC setting. Lastly, we also study the problem of learning a policy for BSG under  budget setting. Experiments on various problems illustrate the efficacy of our approach in terms of optimization quality as well as computational efficiency.

Published in Transactions on Machine Learning Research (04/2024)
Revisiting stochastic submodular maximization with cardinality constraint: A bandit perspective
Pratik Jawanpuria Microsoft, India
Bamdev Mishra Microsoft, India
bemdeem@mieeroofft.com
Karthik S. Gurumoorthy Walmart Global Tech, India
korthik, wwt.gggummmottttnnaaattttommm
Reviewed OpenReview: https: https:://openrevieau openreview. net/ forum? 5d=57ECCNLAGE
Abstract
In this paper, we focus on the problem of maximizing non-negative, monotone, stochastic submodular functions under cardinality constraint. Recent works have explored continuous optimization algorithms via multi-lincar extensions for such problems and provided appro- priate approximation guarantees. We take fresh look into this problem from a discrete, (stochastic) greedy perspective under probably approximately correct (PAC) setting, i.e., the goal is to obtain solutions whose expected objective value is greater than equal to with at least 1- probability, where OPT is the optimal objective value. Using the theory of multi-armed bandits, we propose novel bandit stochastic greedy (BSG) algorithms in which selection of the next element at iteration is posed as a (vi, PAC best-arm identification problem. Given (v, ()AA) parameters BSG, we formally char- acterize a set A(v, 8) of per-iteration policies such that any policy from this guarantees (v, 8)-PAC solution for the stochastic submodular maximization problem using BSG. We next discuss the problem of learning policy in A(v,d) ò) by minimizing the computational cost. With our learned policy, we show that BSG has lower computational cost than existing stochastic submodular maximization approaches. An interesting outcome of our analysis is the development both linear and almost-lincar time algorithms for the exemplar based clustering problem with (1 - 1/e appppooximationn guarantee under a PAC setting. Lastly, we also study the problem of learning a policy for BSG under budget setting. Experiments various problems illustrate the efficacy of our approach in terms of optimization quality as well computational efficiency.
(1-1/e-c)OPT-
1 Introduction
Submodular functions are those that have the property of diminishing returns, where the incremental gain of adding an element to set decreases as the size of the set increases. They are often regarded as discrete applications such as document summarization (Bairi
analogs of convex functions and arisc naturally
et al.) 2015 Kim et al. 2016
Gurumoorthy et. al. 2019). image summarization (Tschiatschek et al. 2014).
data, feature subset selection (eei et al. 2015).
speech data training (Wei et al. 2014). facility location
MMehrotra & Vishnoi 2023
Karimi et al.
2017 Agarwal et al. 2023), influence maximization in social
networks (Kempe et al. 2003 Chen et al. 2009),
sensor placement, active learning (Wei et al. 2014), and
recommender systems Mehrotra & Vishnoi 2023). to name a few. We refer interested readers to the survey
KKause & Golovin 2014 for further introduction to submodular functions.
Given a ground set S in] consisting of first n natural numbers, a set function F:25 R is submodular if it satisfies F(A) F(B) > F(An B) + F(AU U B) for all A, B C S. Defining ((i F(AU (1)) F(A)

---

Published in Transactions on Machine Learning Research (04/2024)
the incremental gain of adding an element i to the set A, submodular function equivalently satisfies the diminishing returns property: A( 2 B(i for any A S B C S and & B. The function is monotone non-decreasing if g(ilA) 2 0, E S A, and non-negative when F(A) 2 0, C S. The submodular maximization problem is typically stated as identifying the subset s* under some constraints that maximizes the submodular function F. In this regard, a common optimization problem maximizing F under a cardinality constraint, stated as:
max F(s). SSS| S
(1)
As submodular maximization is NP-hard in general, fast algorithms are sought to approximate OPT maxxgs,|s|sk F(s) with theoretical guarantees (Nemhauser et al. 1978).
Problem is classically studied in an oracle model, where the access to F is made available via a black box which when fed a subset S outputs F(s). However, recent works (Karimi el al. 2017; Mokhtari et al. 2018) have also investigated [1 in settings where F is estimated from large amount of data involving stochastic fluctuations, or is not directly accessible and computed only via simulations. Examples of such applications include influence maximization, exemplar-based clustering, recommender systems, protolype selection, etc. In influence maximization, for instance, the goal is to find the most influential seed nodes (of size k) that maximize the propagation of influence through the network (Kempe et al. 2003). The subset of nodes inffuenced from a seed set is modeled as an expectation of a stochastic process, and may not be computable in closed-form. In facility location, the objective may be viewed as an expected value of similarity between a large number of data points and chosen h centers (with respect to the distribution of data points).
In the above applications, the objective function for stochastic submodular maximization (SSM) problems could be expressed as F(s)= == pf where f stochastic function and z E Z is a random variable with distribution P. When F(.) is computed from large number of data points simulations, standard discrete algorithms such as (lazy) Greedy (Minoux 1978) or (lazy) Stochastic Greedy (Mirzasoleiman el al. 2015) incur a high computational cost since and require calling the stochastic function f large number of times for each input subset s. Recent works (Karimi et al., 2017 Hassani et al. 2017 Mokhtari et al. 2018 2020 have proposed stochastic continuous optimization algorithms for SSM which leverage the multi-lincar exlension (Vondrák 2008 Calinescu et al. 2011) of submodular problems.
In this work, we take fresh look into non-negative monotone SSM problems with cardinality constraint from a greedy perspective and under provably approximately correct (PAC) setting. In each iteration of the (stochastic) greedy approach, we view the set of candidate elements arms with expected rewards equaling their incremental gains. Hence, choosing the candidate with the highest incremental gain (highest reward) is similar to the best-arm identification problem in the multi-armed bandit (MAB) literature (Even- -arr let al.] 2006 Audibert et al., 2010). Given (v. 8)C parameters, we first define a (v, 8)PCC solution (5) for the SSM problem (2). We next propose novel bandit stochastic greedy (BSG) algorithm for solving SSM problems with cardinality constraint. The next element selection problem in each iteration i of BSG is posed as (v,, (2,,, P.C best-arm identification problem. The main contributions of this work is the analysis of BSG in the following directions.
1 Correct of BSG: given (v, 8)-PAC parameters, can the proposed BSG algorithm obtain a (v, 6)- PAC solution for the SSM problem ? ? We answer this affirmatively by characterizing a set A(v, 8) of per-iteration policies which guarantee BSG to obtain a (v, 8)C solution. This is discussed in Section 3.2
2 Given (VA parameters for BSG, we note that the set A(v,8) has several (14,,))) per- iteration policies. An immediate question is: what is BSG's computational cost with such policies in terms of the number of stochastic function ff calls (N)? In Section 3.3 we discuss the computational cost. of BSG for a given {(v,, 6,)) policy. We also investigate the problem of learning a policy {(v,, M E A(v, 5) by minimizing the computational cost.
3 Furthermore, we explore the problem of minimizing BSG's error parameter V under a given fixed budget of No stochastic function f calls and a given confidence level 5. In this setting, we learn a policy {14, 8/k)) E A(v, for BSG such that the overall error level is minimized, This is
discussed in Section 3.4
2

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Approximation guarantees and number of stochastic function f calls (N) for various algorithms on the SSM problem calls required to compute the function F(-). In exemplar based clustering, for instance, m n. For discrete stochastic methods (disc. stoch.), the expectation over F(s) over the randomized sampling of the candidate set. For continuous stochastic methods (cont. stoch.), the expectation over F(s) is due to multi-linear extension, stochastic gradients, and randomized pipage rounding. Greedy is the only deterministic method in the table. We observe that the proposed algorithms (BG-ABA, BG-NE, BSG-ABA, and BSG-NE) have lower complexity of N in terms of n.
(2). Let 7(e) 1/e- and m denotes the maximum number of stochastic function f
Algorithm
Type
Approximation guarantee
Number of f calls (N)
Greedy
discrete
F(s) 2 T0)OPT
((nkm)
BG-ABA (this work)
discrete
P(F(s) 2 (0)OPT - v) 2 1
O(nk log (
BG-NE (this work)
discrete
P(F(s) (0)OPT
O(nk log( ( )/v²)
Stochastic Greedy
disc. stoch.
[[F(s) 2 7c)jPP
Mirzasoleiman et al.
2015
BSG-ABA (this work)
disc. stoch. P[E[F(}) 2 (())0(()))-))))) 1 1-6 O(nk² log log(
BSG-NE (this work)
disc. stoch. P[E[F(s) 2 7())0PT - 2 1 5
O(nh2 log( log ()) log( (oe))) ((2))
SGA Hassani et al.
2017]
cont. stoch. [[F(s)] 2 (1/2)OPT
O(1th//v²)
SCG Mokhtari al.
2018
cont. stoch. B[F(s)] 2 (0)0PP -
06120819/0")
SCG++
Hassani et al.
2019 cont. stoch. [[) (0]OPT
OG12A//AA)
In addition to the BSG alg,rithm, we also propose a (non-randomized) variant of BSG, henceforth termed as bandit greedy (BG) algorithm. In BG, all candidate arms are considered in every iteration unlike BSG where only few candidate arms are randomly chosen per iteration. Hence BG has a higher computation cost than BSG, but better approximation guarantee. The approximation guarantees and the computational costs of the proposed the BG and BSG algorithms with learned policies are summarized in Table D
In Table 1 we observe that our proposed algorithms have either linear almost-linear computational cost in n. An interesting implication of our result is that the proposed algorithms reduces the computational cost of each Greedy (or Stochastic Greedy) iteration for the exemplar based clustcring (also known as k-modoids clustering) problem from quadratic to linear or almost-linear and provide similar approximation guarantee as Greedy (or Stochastic Greedy) under a PAC setting.
Empirical results illustrate the efficacy of the proposed approach on applications such as exemplar based clustering and representative sampling from a target set. The proofs of all theoretical results and additional experimental details are provided in the appendix.
2
Related work
This section briefly reviews the literature submodular maximization, stochastic submodular maximization, and the best-arm identification (or pure exploration) problem under the multi-armed bandit framework.
2.1 Submodular maximization
Discrete greedy approaches. For maximizing a monotone, non-negative, deterministic submodular function F under cardinality constraint k, the landmark paper (Nemhauser et al. 1978) employed the Greedy algorithm to oblain the (1 - 1/e) approximation guarantee, and proved that any algorithm that is allowed lo only evaluate at a polynomial number of sets will not be able to obtain an approximation guarantee better than (1 1/e). Exploiting the propertics of submodularity, [Minoxx (1788) proposed an accelerated version of the classical greedy algorithm, popularly known as Lazy Greedy Leskovee et al., 2007). The Stochastic
Greedy algorithm (Mirzasoleiman et. al. 2015) provides (1 1/e approximation in expectation using
3

---

Published in Transactions on Machine Learning Research (04/2024)
On function F evaluations. A deterministic (1 1/c- approximation algorithm requiring (n/cc calls to F has been recently proposed [L. et. al. 2022
Continuous greedy approaches. Existing works (Vondrák 2008
Calinescu el al. 2011 Chekuri el al.
2014) have explored continuous relaxations of submodular functions via multi-linear extension, which lifts [1] into a continuous domain and perform continuous optimization using gradients. Calinescu et al. [001]] showed that the continuous greedy algorithm obtains the tight (1 (1-1/e) approximation bound for monotone submodular functions under a general matroid constraint. Randomized pipage rounding (alineecuu al. 2011 Karimi et al. 2017) is usually employed to obtain discrete solution from fractional
the discrete problem
solution without worsening the objective value in expectation.
2.2 Stochastic submodular maximization (SSM)
While the classical Greedy or the Stochastic Greedy (Mirzasoleiman et al. 2015) algorithms may be employed for solving SSM problem (F's)= = [f z)]) defined over large number data points or simulations, they compute the function F-)) exactly each iteration i. Hence, they roquire the full data at cach itcration and incur high computational cost. Recent works have explored stochastic gradient based continuous greedy approaches for SSM as they require only small batch of data at every iteration.
For maximizing weighted coverage functions, subclass of stochastic submodular functions, Karimi et al. (2017) proposed a concave relaxation scheme and employed projected stochastic gradient ascent (SGA) algorithm. However, for SSM problems, SGA does not provide tight guarantecs as it offers OPT/2 - v lower bound in expectation after O(n" /v²) iterations (Hassaui et al. 2017). Conditional gradient based stochastic continuous greedy (SCG) improves upon SGA and achieves (1
OPT v guarantee in expectation after ( /v²) iterations (Mokhtari et al.) 2020). Hassani al. 2020 proposed variance reduction based SCG, SCG++, which provides the same guarantee as SCG in On
iterations.
Table T summarizes the approximation guarantee and the computational cost (in terms of the number of stochastic function f calls) corresponding to Greedy, Stochastic Greedy, the stochastic gradient based continuous greedy approaches (SGA, SCG, and SCG++), and our proposed algorithms.
2.3 Best- identification problem
Consider set S of arms. When arm S is sampled (i.e., pulled), reward pls) is received. This reward is realization of random variable from an unknown distribution D(s). The pure exploration (or best arm identification) problem (ubeeck et al. 2009 with the highest expected reward: 8* E arg max EES ED(,) [x())]- Thus, estimating the expected reward of an arm involves sampling them sufficiently. Learning a (2, bb-t arm under probably approximately correct (PAC) sctting implics identifying an arm such that uus')= 2 p(s*)= - a with at least 8 probability. Here, y and 5 are usually termed as the error and confidence parameters, respectively. An interesting problem is identify (v, b arm while incurring minimal sampling complexity (Jamieson & Nowak 2014).
Audibert et al. 2010 is defined as identifying arm s*
Elimination strategy is common approach for the (1,8)-PAC problem, with median elimination (Even-Dar et al. 2006) being one of the most popular algorithms. Elimination framework involves sampling from all the non-eliminated arms at each around and eliminating some of the arms at the end of each round. The celebrated Hoeffding bound provides the following simple yet efficient naive elimination (NE) procedure for obtaining a (v, beet arm s' S:
1. Given u, parameters, sample each arm 2 log(n/0)/u2 times and record the mean empirical reward ((ss) for each arm s e S
2. Select the arm s' = arg max ((s).
sE$
Recently, Hassidim et al. (2020 proposed the approzimate best arm (ABA) algorithm that learns (v, 5e-best with lower number of samples than the median elimination algorithm. The ABA algorithm employs two
4

---

Published in Transactions on Machine Learning Research (04/2024)
elimination strategies aggressive elimination (AE) and NE - one after the other. The aim of AE is to use only few samples to eliminate a significant number of potentially uninteresting arms with high confidence. The subsequent NE stage takes the surviving arms from AE as well as a randomly chosen subset of S (to account for the small probability that AE may climinate good arms) and outputs a (v, 6e-sst arm. We detail the steps of the ABA algorithm in Section
Within the best-arm identification framework, another interesting setting is the fixed-budger setting (Audibert et al., 2010: Gabillon et al.) 2012: Karnin et al. 2013 Jamicson & Nowak 2014). Here, the aim is to maximize the confidence (i.e., provide the best guarantee) of selecting the best arm given a fixed number of sampling, i.c., arm pulls.
3 Proposed approach
Given a ground set S = (I....,n) of n elements, we consider the problem of maximizing a non-negative, monotone, stochastic submodular function F 2 + R+, subject to cardinality constraint, in the setting where the function F is defined F(s) == (s) The function : x Z R4 may be given as stochastic function (as part of an implicit stochastic model for which the distribution P may be unknown) could be an empirical function (with possibly large domain 2). Overall, the SSM problem is formalized as follows:
max *CS.|8|R
It should be noted that the stochastic function f(s; need not be submodular (Mokhtari et al. Since our analysis involves application of Hoeffding's inequality, assumne that the range of is 0. for simplified expressions. As with existing works approximate bost-arm identification problem (Bagaria et al. 2018: Hassidim el al. 2020), all Cheoretical results of this paper can be generalized to any sub- Gaussas distribution.
2018 2020
The classical Greedy algorithm Nemmhassrr al. 1978 for 2 begins with the empty set Su 0. In the i-th iteration, it finds the element that maximizes the incremental gain gi, i.e., 8 arg max ge(uss--) 1), where F(s {u}) F(s;-1) is the incremental gain as defined earlier. We then update s; + s U {s}. On the other hand, Stochastic Greedy (Mirzasoleiman ct al. 2015) chooses a smaller (but random) candidate element set R; C S s for the i-th iteration, with
R, S S\ 5 is the candidate element set and g; (0
RR
E (o
Both Greedy and Stochastic Greedy require multiple evaluations of the function F(-), which may be computationally costly or even impractical several real-world applications (Mokhtari al.] 2018 2020). We propose novel discrete stochastic greedy based algorithms that require small number of stochastic function f calls in each itcration and provide approximation guarantces.
3.1 Bandit stochastic greedy (BSG)
Each iteration of the stochastic greedy framework involves greedily selecting an element with the maximum incremental gain. The incremental gain for the SSM problem (2) with respect to an element s E R2 may be written as:
g(sss) = If
- Ex-p(((s;2)
(3)
= Pegplg((sss)
where g(s(s;2) = (s) - f(s is the stochastic marginal gain (corrosponding to the sample P) when an element 8 is added lo 8. Since (3) is an expectation, we may obtain an unbiased estimator of g(sls) as g(s s; 2,) = Σxez, g[s|s; z)/|Z// given a set Z, whose elements are sampled from P. We also note that
the term Ez-P z) in 3 constant with respect to the new element s. Thus, we may equivalently use the estimator h(s)ss; 2,) = Exez, [(s {s}; 2)];2)/|2.1 for greedily selecting the next element.
We now propose to employ the bost arm selection strategies from the stochastic multi-armed bandit (MAB) framework for greedily selecting the next element, We view the different candidates E R, as individual arms (agents) with the corresponding reward given by â(.). Thus, identifying the best element that maximizes the
5

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Proposed bandit greedy (BG) and bandit stochastic greedy (BSG) algorithms
Input: 2, k, v, and c. Select a per-iteration (()) policy satisfying Initialize = o, ====
while i < do
1: BG: R3 = S 8;-1
or
BSG: R. subset of 8 8:-1 with nk n log(1/e) elements which are selected uniformly at random.
2: PAC BEST ARM(s R2, 2, 6,).
3: = 8 U (5), i=
end while Output: 8u-
incremental gain under (v, PAC setting may be viewed a pure exploration problem (Even-Dar et al. 2006 Bubeck et al. 2009). If s is the element with best incremental gain 3 in the i-th iteration of the (stochastic) greedy Tramework, a (vi, 6:)-best element 8, satisfies the following condition:
Pig(s,(s;-1) 2 (s_1) vs 2 8,.
(4)
In Algorithm 1 we formalize both bandit greedy (BG) and bandit stochastic greedy (BSG) approaches. The difference between BG and BSG approaches is only in Step 1, which is in the candidate element set R4, As observed in Step 1 of Algorithm | BG has the candidate element set R, as the set of all the remaining elements (Ra = -1)) ) On the other hand, BSG selects the candidate element set as a random subset of the remaining clements with [R, = nk- log(loogg/// log(1/c), where e is the stochastic greedy parameter (Mirzasolciman) eet al. 2015 This randomll selected candidate set lowers the computalional cost of BSG with respect BG by O(k) (Table D]. The PAC_BEST ARM function in Step of Algorithm denotes a best-arm identification algorithm that returns (v,, -best element at i-th iteration. The set {(1,, ) of PAC parameters employed in Algorithm | is termed as policy. Step 3 of Algorithm 1 [pdaate the solution set s, with the chosen element that is output of Step 2.
In this work, we analyze the proposed BG and BSG approaches with PAC BEST BEST_ARM as the NE or the ABA algorithm (discussed in Section 2.3 If ABA is employed in Algorithm I we term BSG-ABA (or BG-ABA) and if NE employed, we term it BSG-NE (or BG-NE). In the rest. this section, we discuss the approximation guarantees provided by our BSG algorithms. Analogous results for the BG algorithms are C Table summarizes the key theoretical results for the BSG-ABA, BSG-NE, BG-ABA,
discussed in Section and BG-NE algo
In the stochastic greedy framework with the (stochastic greedy) parameter a set s C S (with |s|
S k) is
termed as (v, 8)AAC solution of 2 if the following holds:
P (E
2 1/c c)PPT 1)) 1-
(5)
We next analyze the following questions related to Algorithm 1
1. Given PPAC parameters, can Algorithm Jobbain (1,5)-PAC solution for the SSM problem
2 If yes, can characterize set A(v, 5) of policies such that any policy from this set would ensure Algorithm obtains (v, 8)- solution for ?
2. What is the computational cost of Algorithm for given {(r,, (.)) policy? Can we learn a policy {(v, 6,){ e A(v, 8) by minimizing the computational cost?
Can we learn policy {(v,, 6)) E A(v, 5) by minimizing the overall error level v corresponding Algorithm under given budget of computational cost and a given confidence level 5?

---

Published in Transactions on Machine Learning Research (04/2024)
3.2 Characterizing set of policies which guarantee BSG to learn (1, solution
Our first result shows that the proposed BSG algorithm indeed learns (v,6)-PAC solution of the SSM problem 2) if the {(2,, (1)) policy is designed systematically.
Theorem 3.1. Let be the solution obtained by BSG (BSG-ABA or BSG-NE) for with a given PAC
parameters (u,5) and stochastic greedy parameter (0, 1 1/e)- Then, is (V, 8) -PA solution of if
the per-iteration {(v, 8,) policy belongs to the set
k 0 = 6, (1 c)
(((p),))) A(v, 6) = (1(1s, 6,)3m
Ede
g 3k-iv;
14 S/}.
(6)
2m
where B = 1 (1 -1 kk/
Proof. The proof is provided in Section [.1
Remark 3.2. The ABA algorithm (Hassidim et al. 2020 requires its confidence parameter lie in the range
0.05. Hence, have the following constraint user defined d for BSG-ABA: 8 { (0. 0.05k] k 20
(0,
k 20
Theorem 3.1 provides various options for designing the per-iteration (v, 6,) policios for the SSM problem For example, we model is = vo g. vi and solve for vp (1-e) E 3h up 2) Vi. Alternatively, since B
v, we obtain one upper bound (1 c) Et_, 8k with (1-e) e) E)-) 1/.. If equale the latter with v and solve for v0 (with v, v0), get another feasible policy (v,, 54) (MT-5) () vi. While Theorem 3.1 guarantees that both these example policies would allow BSG to obtain a (v, 6)-PAC solution, the computational cost BSG terms of number of stochastic function f calls (N) would be different. Between the above two example policies, the former will incur lesser cost. Tn the following sections, we investigate learning per-iteration policies while taking the computational cost of BSG into consideration.
(ve, 64) (KI-
3.3 Computational cost of BSG
Theorem 3.1 characterizes set of 6(), policies, A(v,8), which ensure that BSG obtains 8)AC)- solution for the SSM problem (2). However, the computational cost, i.e., the number of stochastic function f calls (N), for obtaining a (,, PA- solution depends on the policy used in BSG. For given policy, the following lemma provides an expression of N for the proposed BSG algorithms.
Lemma 3.3. The number of stochastic function f evaluations NABA and NNE required by BSG-ABA and BSG-NE, respectively, are
k
18n ky
1
NABA
=
log
log
5,
im1
(7)
NNE
Σ
k:
2m
log
log
) log
1
ku
K6;
1=1
Proof. The proof is provided in Section
B.2
Remark 3.4. The proof of computational complexity of BSG-ABA employs the result (Hassidim et al. 2020 Theorem 1) which provides an upper bound on the sample complexity of the ABA algorithm. In this work, we take this upper bound as the overall complexity ABA.
Given (v, PPC parameters for BSG, we now consider the problem of learning policy from the set A(v, by minimizing the computational cost The resulting optimization problem may be simplified as follows:
min 030;
( log(6:))u,
(8)
s.t. {(v,, d.) E A(u,
7

---

Published in Transactions on Machine Learning Research (04/2024)
where 14 == 0 for BSG-ABA and μ log( C log(?)) for BSG-NE. Since 0 < 6, < 1, (μ 1 log().)) 0 Vi. While Problem 8 is non-convex, it is individually strictly convex in (4) and {6 variables and has closed form solutions. This is discussed in Appendix B.3 Hence, alternating minimization algorithm may be employed to solve
In the following, we analyze 8 under the uniform per-iteration confidence setting, i.e., fixing 6, = 6/k Vi. This is motivated from the observation that the error parameters {4r influence the computational cost more significantly than the confidence parameters {6, ) Having uniform per-iteration confidence also leads to simplified expressions.
Theorem 3.5. Given (v, 6)-AA parameters, consider the uniform per-iteralion confidence policies in A(v, 8), i.e., (V,,, 6,)) E Ō(v such that ó; = 8/k. Among such policies, the one corresponding to the mindmum number of stochastic function f calls required by BSG to obtain a (v,6)-PAC solution is given by
w(1 - - Vi.
v (1 (1-c)(1 - /2k/3)
The expressions of NABA and NNE corresponding to {(V7 (u/2,//k))) o/k)) are:
NABA = 18n(1- - 6)3
h log
()) c(k)),
log
22
8
2m(1 =
n
1
1
NNE
log
log
log
c(k),
V2
(1 (1-82k/3p3 k(1 32733 and B 1- c)/k.
where e(k:)
Proof. The proof involves solving (S) only with respect to [1:] by first setting 6; = 6/k and then using the Hölder's inequality. The details are provided in Section B.4
Remark 3.6 (Complexity of BSG-ABA and BSG-NE algorithms). can be shown that c(k) S k2, resulting in linear On)) complexity of BSG-ABA and almost-linear On log(n)) complexity of BSG-NE algorithms (ignoring the constants v2, 6, and and assuming k < n). This result is significant as for popular SSM problems such exemplar-based clustering, both Greedy and Stochastic Greedy have quadratic O(n?) complexity in k & n setting, From Table [ we also observe that continuous stochastic greedy approaches (SGA, SCG, and SCG++) have at least quadratic O(²²) complexity.
Remark 3.7. Compared to Theorem 3.5 the margin of improvement with jointly optimizing both {
and {8, / in (8) is observed to be empirically small. The details are provided in Appendix D
Remark 3.8. Recently, Tiwari et al. (2020) have proposed the BanditPAM algorithm for exemplar-based
clustering (A- (8-medoids) problem. BanditPAM employs a variant of UCB algorithm (Lai & Robbins 1985
Zhang et al. 2019) and provides guarantees under probably correct setting (i.e., error parameter v 0).
Given the confidence parameter 8, BanditPAM has the following guarantee:
(Tiwari et al. 2020 Appendix Remark A1) With probability at least 6, BanditPAM, when restricted to
the BUILD step returns the same set of k points as Greedy, and the required number of pairwise distance computations satislies E[Nnp] = O 5d, (k) + n log(n/5)d2
Tiwari et al. (2020) derive the above result on the computational cost of BanditPAM (NBP) by assuming to to be a constant and does not formally analyze its dependency on k. Hence, we have represented this dependency on as (unknown) functions di (k:) and d2(k) in the above expression. Incidentally, Tiwari et al. (2020) Appendix Section 2.5) observe that BanditPAM's computational cost varies from quadratic to cubic on k for some parameter regime. Empirically, we observe that the computational cost of both BG and BSG algorithms are an order of magnitude lower than BanditPAM.
3.4 BSG in budget setting
We now study BSG in a budget setting. Given a budget of the number of stochastic function calls (No) and the overall confidence parameter 6, the aim is to find the best per-iteration policy in the set A(v, 5). Since
8

---

Published in Transactions on Machine Learning Research (04/2024)
the overall PAC-error parameter for BSG is not provided in this setting and the best policy for BSG is the one which achieves the lowest for the SSM problem 2
The above may be posed as an optimization problem over the policy {(rs, d:) E A(v, such that v is minimized. We begin by noting that given a policy {(v,, 6,) E A(v, 8), the best (lowest) PAC-error parameter (for BSG) is a function of the policy: == (1 Ei= gh- Hence, we propose to minimize V over the set of policies A(v, 5) and under the constraints that the overall budget is No and the overall PAC-confidence parameter for BSG is 6. The resulting optimization problem may be simplified as follows:
min M.b.>0Vi
(1
gh-ivy
i=1
(9)
s.t.
(11 log((:)) Sc,
Σ
6 S
where μ 0, 18n log(1/e]
&No
for BSG-ABA and μ == log( log( ()),
2n log[ for BSG-NE. Since 0 < 6, < 1,
NN
- log(6.)) > O Vi. Problem 9 is a non-convex and we may employ a gradient descent based algorithm.
This is discussed in Appendix B.6
In the following, we analyze 9 under the uniform per-iteration confidence setting, i.e., fixing 6, 6/k Vi. This leads to simple closed-form expression for the optimal policy and has only marginal empirical difference compared to directly optimizing (9). This is discussed in detail in Appendix [
Theorem 3.9. Given a budget No on the number of stochastic function f calls, the confidence parameter 5 for BSG, and under the uniform per-iteration confidence setting (i.e., o, = 6/k Vi), BSG-ABA and BSG-NE obtain (VABA.8) 8)- and (NNE: 8)CPAC solutions, respectivcly, where
--2//
3/2
(1 (1-c)218nleg log(nlog(()) (0 1/2
VAAA =
/2/3
kNo
32K/3
3/2
((1-c) 2m log log (og 1/2
USE= =
1 - 32/3
kNo
and 3 1 (111--1100 e)/k. The corvesponding per-ileration error levels for BSG-ABA is
18n log(k/)) (og(L)))( -122//))))
1/2 g Vi.
kNo -3/33)
Similarly, corresponding per-iteration error levels for BSG-NE is
v 2n lngg [oablo/(nng((//////00///////// 32413) 1/2
g(b- Vi.
1NNo1 52/3)
Proof. The proof involves solving (9] only with respect to {wr) by first setting 6, 8/k and then using the Hölder's incquality. The details are provided in Appendix B.7
3.5 Implementation details
We now discuss few implementaaiion-rellteed aspects of the proposed BSG approach.
Computing rewards for all the arms on the same sample set. In given iteration i of BSG (Algorithm D let Z, be the set of instances z sampled for the first arm. Then, the same set Z, may be used for computing rewards for the remaining candidate arms. This offers several practical advantages without changing any theoretical results: (a) reduces the required mumber of samples in an iteration (by a factor of the number of arms), which becomes important when acquiring samples costly, and (b) helps memory-effiiient parallelized computations. However, we note that using the same set Z, does not reduce the number of calls to the stochastic function f, rewards needs to be computed for all the candidate arms.
9

---

Published in Transactions on Machine Learning Research (04/2024)
observe that BSG-ABA has lower complexity of (n) required number of stochastic function f calls than BSG-NE which has complexity O(n log(n)) for a given (v, 8)-PAC setting. However, from 7 we note that the constant terms hiding in the O notation of BSG-ABA are larger than those of BSG-NE (NA has 18 while NEE has 2). By setting NEE I NABA we can therefore compute the range [1, no] of n over which BSG-NE requires lower number stochastic function f calls than BSG-ABA. We get ng = 6(k: (c)( As discussed in Remark 3.2 8/k - 0.05 for BSG-ABA. Hence, To 2 5.12 10 log(I/e] For reasonable choice of parameter values d 0.001 and e 0.01,
On BSG-ABA versus BSG-NE. In Remark 3.6
8
we get 2 2.3 x 10" Hence, BSG-ABA will have practical runtime advantage over BSG-NE only in very large scale problem setting.
Overall, we observe that BSG-NE is a well-stited algorithm for the SSM problem (2 as it has lower stochastic function calls complexity than existing SSM algorithms like SGA (Hassani et al. 2017). SCG (Mokhtari et al., 2018), and SCG++ (Hassani et al., 2019). BSG-NE is simple to implement, can take advantage of lazy evaluations (Minoux 1978), and can parallelize the reward computation across the candidate arms and samples within each iteration. This allows BSG-NE to exploit modern GPU computing systems, thereby making BSG-NE (and for the same reason BG-NE) our method of choice for experiments discussed in Section 4
4 Experiments
In this section, we show the benefit of the proposed BSG and BG algorithms on the exemplar-basod clustering and representative sampling applications. As discussed, we consider the BSG-NE and BG-NE variants of the proposed Algorithm 1 For both our algorithms, we pick the {(1;, 6:)) policy (Theorem 3.5 that minimize the stochastic function f calls for the given (v,8) parameters. We consider the following baselines.
1. LG:
the deterministic Greedy algorithm with lazy evaluations MMinoux 1978
Leskovec et al. 2007
As it has the best theoretical guarantee, LG is expected to obtain the best generalization performance among the competing methods but with high computational cost.
LSG: the popular Stochastic Greedy algorithm with lazy evaluations (Mirzasoleiman et al. 2015).
3. SCG: the stochastic continuous gradient algorithm proposed in (Mokhlari et al.
2018
2020
BanditPAM: UCB best-arm identification based k-medoids method Tiwari et al.
2020 We run
only the BUILD step of BanditPAM, which corresponds to applying SSM the exemplar-based clustering problem. The authors' C++ code link: httt///tgg///gghhh....////oaaatr wtt.://......oooooaaaaaa//aaaaaa
All the algorithms (except BanditPAM) are implemented in Matlab. The experiments are run on Intel Xeon CPU (3.6 GHz) with 6 cores and 64 GB RAM. The following datasets are considered.
MNIST (LeCun et al. 1998 is handwritten digits dataset with 28 x 28 pixels greyscale images of 10 classes for digits (0, 0......9) 9}. samples (test).
It has two different sets of 60, 000 samples (train) and 10, 000
TinyImageNet (TIN) is a smaller version of the ImageNet dataset (Russkkvsky et al. 2015 with 200 classes and 500 instances per class (Wu al. 2017). consists of images of size 64 64 pixels.
Exemplar-based clustering. Given a dataset X (x+] the aim in exemplar-based clustering is to select & & relevant data points C X' that best represent the datasct X. A popular approach is the k-medoids formulation (Kaufnan & Rousseeuw 2009) that aims to minimize the average distance of the data points to their nearest exemplars, i.e., minimize L(s) = 111 Exex minxes dist(x, z). Here, dist(x, z) computes the distance between the data points x and z. We can pose the above minimization problem as an equivalent monotone (stochastic) submodular maximization problem by introducing a phantom exemplar Zo [Gones & Krause 20100: F(s)= = T(zo) L(s U (2o)). Thus, maximizing F(.) is equivalent to minimizing I(.). We
10

---

Published in Transactions on Machine Learning Research (04/2024)
3.5
10
10
2.5
LG 9:81)
Unityy
8CC 67
S0G [a
Basell Bas
2.85
10"
BCG NZ 6)
Bay PANA 0.01)
E43
PA 0/111
Led (a 0.01)
RGG-N (e (0
BC NT
BSG-NE
10
MCX [M
LAG
DG-NE 30)
ING-NR (-
18)
2.45
SCG ce 10y
Lota
BIG-NE je 101
BSC NmB (- 83
BSGI-NE
100
Bawdit NE 36/1n)
SaadiEPAMM 0.001)
DSG-NE.
DRC.NE
100
DasliPPM 26/n!
BSG-ND
0.5
10
20
30
60
90
120
150
10"
10
20
30
60
120
150
10*
10
10
10
Cost
(a) MNIST: Utility vs Ae
(b) MNIST: Cost vs
(c) MNIST: Ubility vs Cost (A = 150)
3.4
3.2
0.35
10
3.3
1AG
2.8
(UN)
Cost
3.2
500 100
8DG
2.4
166
Banda PAM (6 0
10"*
3.15
BandiPAM
BanduPAM 0.00)
18G 8,01)
RG-NE
01
L8G 0.02)
-GGSE
BG-NE
0.3)
BG.NE
10"
LSG (c 0.3)
-BG-NN 300
HG-NE
2
8CG
BandLPAM 2k/n)
PAM
100
BSC NE
BeG NB
BSG.NB
503
BardhPPMM 20/60
HandiPMM 0.600)
BRG--NT
RSG
DNG--N
100
3.05
BIGG-NE
BRG-NE
60
1.8
10
20
30
60
90
120
150
10a
10
20
120
10"
10
10"1
(d) TIN: Utility vs &
(e) TIN: Cost vs A:
(f) TIN: Utility vs Cost (k- 150)
Figure 1: Performance of various algorithms on the exemplar-based clustering problem. Top row: MNIST dataset, Bottom row: TIN dataset. We observe that the proposed algorithms BSG and BG obtain a good utility versus cost trade-off by varying error parameter and outperforms other SSM methods such as LSG, SCG, and BanditPAM.
select the phantom exemplar as any point 2n satisfying the condition m dist(z',z) 2) S dist(z0, 2) Va E X (Mirzasoleiman et al. 2016). This ensures that L(s U (zo)) L(s). The stochastic function f can then be expressed as [(s z) L(zo) minxxes dist(x, z). In our experiments, we set dist z) = ||x 2/1².
For BSG-NE, BG-NE, and SCG, we experiment with v = {5, 10, 15). As the error parameter v increases, these methods require lesser number of samples (BSG-NE and BG-NE) or itcrations (SCG). The number of iterations for SCG is upper bounded by 20000. We set 8 = 0.001 for BSG-NE and BG-NE and = 0.01 for BSG-NE. We experiment with LSG in two settings: 0.01 and e = 0.1. For BanditPAM, we show results with 8 (0.01, 2k/n]. The per iteration policy of BanditPAM is 8, 5/k TTwari al. 2020
Figure 0 Lop-row and Figure I bottom-row show the results on the MNIST and TIN datasels, respectively. From Figures D aa) & dd), we observe that the proposed BSG-NE and BG-NE algorithms' utility is comparable with LG across k especially at lower values of error parameter v. BSG-NE and BG-NE methods achieve the lowest cost across in both the datasets, ie., in Figures (b) & [e), where cost is the number of stochastic clustering, this cost is the number of pairwise distance computations done by an algorithm. At a high k value of 150, we observe in Figures [c) & [() that BG-NE with v 5 obtains the closest utility to LG and is computationally cheaper than both LG and LSG. On both datasets, across k the proposed BSG-NE and BG-NE methods show good trade-off between utility and cost with varying error parameter v. LSG's cost, on the other hand, varies little across k and is much costlier than the proposed approaches at low h values. SCG obtains the worst utility across k on the MNIST dataset and is lower than the proposed approaches on the TIN dataset. BanditPAM, on the other hand, matches LG's utility at low io values on MNIST, but as k increases, it ends up with utility lower than both BG and BSG algorithms. On the TIN dataset, BanditPAM obtains a competitive utility to BG/BSG (with / 15) till k = 20 but its utility almost flattens for k > 30. The computational cost. of SCG and BanditPAM are also
function f calls. In exemplar-basee
11

---

Published in Transactions on Machine Learning Research (04/2024)
10
80
75
Time (6)
180 0.33
5CG 0)
ESG (r 0.00]
10
No:
13G
BG-NE
100
SCG (+ 10)
80G 53
BC--N [o 301
BG--NE
BIG-NE
PSG Nit
B5G N85 180
BBG NE
BandiPPM M (6 (do1)
rears Nit (1-
NB
RSG (0
66
120
90
(a) TIN: Time vs &
(b) MNIST: prototype sel., 10% skew
(c) MNIST: prototype sel., 50% skew
Figure 2: (a) Time versus k plot for the exemplar-based clustering problem on the TIN dataset; (b)&(c) Generalization performance achieved by nearest protolype classifier corresponding to each method on representative sampling problem.
significantly higher than BSG-NE and BG-NE. In Figures ec) & f)), we observe that SCG and BanditPAM obtain the worst utility versus cost trade-off on the MNIST and TIN datasets, respectively. In Figure 2a), we also plot the time taken for different & values on TIN. We observe that BSG-NE and BG-NE take much less time than the baselines, highlighting their practical usefulness.
Representative sampling from a target set. The previous set of experiments show that the proposed algorithms provide a better utility versus cost trade-off compared to the existing approaches. In the above experiments, the quality of the obtained solution is evaluated only in terms of the achieved (submodular) objective. We now evaluate the quality of the proposed approaches in terms of the generalization performance of the obtained solution in a downstream application).
The aim in this application is to select few h < n data points from a given source set X' that best represents a different given target set 2 {Kim et al. 2016 Tt. can also be viewed as an instance of the facility location problem and is formulated as maximizing Σzez (maxxesx w(x,z)) where w computes the similarity between points from X and 2. Hence, the above representative sampling formulation is an instance of SSM problem. Following (Benn & Tibshirani 2011 Kim et al. 2016), evaluate the quality of the selected representative samples (a.k.a. prototypes) via the performance of the corresponding nearest prototype classifier. This is a 1-NN classifier which is parameterized by the selected prototypes.
We evaluate all the methods on the MNIST dataset using the standard experimental protocol (Gurumoorthy
ct al. 2019 2021). The source set consists of 5, 000 points uniformly sampled from the MNIST test set (of size 10, 000). The targel set constructed from the MNIST train set consisting of 60, 000 points such that class has skewed r% representation and others have (100- r)/9% representation each. We evaluate the methods in two skew settings: 10 and 50. We compare BSG-NE and BG-NE against the baselines LG, LSG, and SCG. BanditPAM is not evaluated as its code is made available only for the k-medoids problem.
The accuracy of the nearest prototype classifier corresponding to each method is plotted in Figures 2 & 2 c). We observe that the prototypes selected by our BSG-NE and BG-NE algorithms show good generalization performance and are comparable LG. This shows that the quality of the solution obtained by the proposed algorithms is similar LG's solution. However, the prototypes selected by SCG are less informative they obtain 8% 15% less accuracy than our approach.
5 Conclusion
In this paper we took a fresh look at the stochastic submodular maximization (SSM) problem from a bandit viewpoint. Each iteration of the greedy framework naturally posed as a best-arm selection (pure exploration) problem. Subsequently, make of the best-arm identification strategy at each iteration i to select
12

---

Published in Transactions on Machine Learning Research (04/2024)
(ve, 6t)-PAC best clement, where 24 is the error parameter and 6, is the confidence parameter. Theoretically, we formalize set of {1),,) policies which ensure that our proposed algorithms obtain a (v, 6)-PAC solution. We next investigate learning policies for: (i) minimizing the computational cost, and (ii) ensuring that the computational cost is within a given budget. With the learned policies, our algorithms have cither linear or almost-linear computations cost in the size of the problem n. Overall, our algorithms offer better utility versus computational cost trade-off than existing SSM approaches in both theory and practice.
References
E. Agarwal, K. S. Gurumoorthy, A. A. Jain, and S. Manchenahally, A scalable solution for the extended multi-channel facility location problem. In ECML, 2023.
J.-Y. Audibert, Bubeck, and R. Munos. Best arm identification multi-armed bandits. In COLT, 2010.
V. Bagaria, G. Kamath, V. Ntranos, M. Zhang, and D. Tse. Medoids in almost-linear time via multi-armed bandits, In AISTATS, 2018.
R. Bairi, R. Iyer, G. Ramakrishuan, and J. Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In ACI, 2015.
J. Bien and R. Tibshirani. Prototype selection for interpretable classification. The Annals of Applied Statistics, 5(4):2403 2424, 2011.
N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 15(1):1455-1459, 2014.
Nicolas Boumal. An introduction. to optimization smooth manifolds. Cambridge University Press, 2023. doi: 10.1017/978 1009166164. URL
htt.://iiclllbbuuula.eee/ooooooo net/book
S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In International Conference on Algorithmic Learning Theory, 2009.
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40:1740 1766, 2011.
C. Chekuri, J. Vondrák, and R. Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 13(1):1881 2014.
Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In SIGKDD International Conference on Knowledge Discovery and Data Minving, 2009.
E. Even-Dar, S. Mannor, and Y. Mansour. Action climination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39):1079 1105, 2006.
V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In NeurIPS, 2012.
R. Gomes and A. Krause. Budgeted nonparametric learning from data streams. In ICML, 2010.
K. S. Gurumoorthy, A. Dhurandhar, G. Cecchi, and C. Aggarwal. Efficient data representation by selecting prototypes with importance weights. In IEEE ICDM, 2019.
K. S. Gurumoorthy, P. Jawanpuria, and B. Mishra. SPOT: A framework for selection of prototypes using optimal transport. In ECML, 2021.
H. Hassani, M. Soltanolkotabi, and A. Karbasi. Gradient methods for submodular maximization. In NewrIPS, 2017.
H. Hassani, A. Karbasi, A. Mokhtari, and Z. Shen. Stochastic continuous greedy ++: When upper and lower bounds match. Tn NewrIPS, 2019.
13

---

Published in Transactions on Machine Learning Research (04/2024)
H. Hassani, A. Karbasi, A. Mokhtari, and Z. Shen. Stochastic conditional gradient++: (non) convex minimization and continuous submodular maximization. STAM Journal on Oplimizalion, (0(4):3315-33444 2020.
A. Hassidim, R. Kupfer, and Y. Singer. An optimal elimination algorithm for learning a best arm. In NewrIPS, 2020.
K. Jamieson and R. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In Conference Information Sciences and Systems, 2014.
M. R. Karimi, M. Lucic, H. Hassani, and A. Krause. Stochastic submodular maximization: The case of coverage functions. In NeurIPS, 2017.
7. Karnin, T. Koren, and O. Somekh. Almost optimal exploration multi-armed bandits. In ICML, 2013.
L. Kaufman and P. Rousseeuw. Finding Groups in Dota: An Introduction to Cluster Analysis. John Wiley & Sons, Inc., 2009.
D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003.
B. Kim, R. Khanna, and O. O. Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. NewrIPS, volume 29, 2016.
A. Krause and D. Golovin. Submodular function maximization. Tractability, 3(71-104):3, 2014.
T.L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-2 22, 1985.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, (2(11):2278-2220 1998.
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007.
W. Li, M. Feldman, E. Kazemi, and Karbasi. Submodular maximization in clean linear time. In NewrIPS, 2022.
Mehrotra and N. K Vishnoi. Maximizing submodular functions for recommendation in the presence of biases. In ACM Web Conference, 2023.
C. A. Micchelli and M. Pontil. Learning the kernel function via regularization. Journal of Machine Learning Research, 6(38):1099 1125, 2005.
M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques, 1978.
B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy. In AAAI, 2015.
B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause. Distributed submodular maximization. Journal of Machine Learning Research, 17(23)):1-44, 2016.
A. Mokhtari, H. Hassani, and A. Karbasi. Conditional gradient method for stochastic submodular maximiza- tion: Closing the gap. In AISTATS, 2018.
A. Mokhtari, H. Hassani, and A. Karbasi. Stochastic conditional gradient methods: From convex minimization submodular maxinization. Journal of Machine Learning Research, 21(105):1-44 2020.
G. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions-i. Mathemalical Programming, 14:265- 294, 1978.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Arghya Roy Chaudhuri, Pratik Jawanpuria, and Bamdev Mishra. ProtoBandit: Efficient prototype selection via multi-armed bandits. In ACML, 2022.
O. Russakovsky, Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and F.-F. Li. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115:211-252. 2015.
Sun, J. Gao, X. Hong, B. Mishra, and B. Yin. Heterogeneous tensor decomposition for clustering via manifold optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):476-489, 2016.
M. Tiwari, M. J. Zhang, J. Mayclin, S. Thrun, C. Piech, and I. Shomorony. BanditPAM: Almost linear time k-medoids clustering via nulti-armed bandits. In NeurIPS, 2020.
S. Tschiatschek, R. K Tyer, H. Wei, and J. A. Bilmes. Learning mixtures of submodular functions for image collection summarization. In NewrIPS, 2014.
J. Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, 2008.
K. Wei, R. lyer, and J. Bilmes. Fast multi-stage submodular maximization. In JCML, 2014.
K. Wei, R. lyer, and J. Bilmes. Submodularity in data subset selection and active learning. In ICML, 2015.
Jiayu Wu, Qixiang Zhang, and Guoxi Xu. Tiny ImageNet challenge. Technical report, 2017.
M. Zhang, J. Zou, and D. Tse. Adaptive Monte Carlo multiple testing via multi-armed bandits. In ICML, 2019.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Appendix
A Organization
The appendix is organized as follows.
Section B gives the proofs the theorems and lemmas mentioned in the main paper.
2. Section discusses the theorems and the proofs related to the correctness of the proposed BG algorithm.
3. Additional discussion on the algorithms is presented in Section
The experimental details are in Section
The bandit algorithms for PAC BEST ARM in Algorithm
| are in Section G
Proofs related to the BSG algorithm
B.1 Proof of Theorem 3.1
We first note the following lemma which adapts (Mirzasoleiman el al. 2015 Lemma 2) to the (v, 8PAA best arm identification setting and then use this result to prove Theorem 3.1
Lemma B.1. Given a current solution s of BSG, let (v0, be the PAC parameters for the next iteration. Then, the following holds with probability - 5,; the expected gain of BSG (Algorithm i in one iteration is at least (1-e] [ - vo) where s* denote the optimal solution of problem
Proof. Let R denote the set of candidate elements the current iteration. We first estimate the probability that (s(s') (s8) is non-empty. The set R has r = log(?) randomly sampled elements from set S\ s (w.lo.g. with repetition). Hence,
(S (8) + Φ]
= 1 P R n (s"
8) = Φ)
= 1
Is
[S
> 1 Tatal
( - S (:18 n).
2 1 e |s
Since 1 - 6 is a concave function and Is* \ ss//
1, we have
((1 jo+ (5 2 ((1
1s*
18* |s - +
))
(1 6 =
k
k
which reduces to Therefore, we have
1s* ||
e
(1
e
k
|s"
s
1s*
PiRn(' (s) (s)
(1
c
=
(1 -
(10)
k
16

---

Published in Transactions on Machine Learning Research (04/2024)
In given iteration, BSG's step 2 (PAC_BEST, _RM) selects Vy-optimal element with probability 1 65. That i8,
g(sls) 2 max g(als) - Vo-
(11)
with probability at least 1 - ō,. In the following, we omit repeating the phrase "with probability at least 5,' with every result cisulliippiaationn for brevily. Equation [11 implies
s 2 g(s|s) - vs Rn (n(s" () (if non-empty) with probability 1 1 8;.
We note that since R is equally likely to contain any element of s* \ s, uniformly random element of R n (s" \ () is uniformly random element of s* (s. Taking expectation on both sides of the incquality in and using the above observation, we get
E[g(s|s) 2 P(Rn (s) + øl \
(g(s/s) vo) Σ SEB" 1
The above inequality holds as the expectation is being taken over the events PRR n (s* \ss * Φ) and Ps s) = Ø] and the product of marginal gain and the latter event is non-negative. By substituting (10) in the right hand side of the above inequality, we get that the following holds with probability at least 6,
1-c Σ (g(s's) vo).
[[g(s|s)
k
sEB
This completes the proof of Lemma B.1
Now, the proof of Theorem 3.1 begins.
Let S; = [=,....,.:: 8t} be the solution of BSG after iterations. Let (M,, 5,) be a feasible per-iteration policy for BSG such that employing it ensures that BSG learns a (y,8)-PAC solution. From Lemma B.1 we have the following result:
Elg((s+1\s:)
2
Σ (o(8)s)) - vi+1),
(12)
k
SE
which holds with probability at least 1- 5, By submodularity, we have the following result: ( N g(s (s;) 2 F(s") ) - F(ss). Applying this in the above result gives
(1((541154)(ss)) 2 1- -F=ss( F(s:)) - (1 e)U++1
Now we take expectation over s; over both the sides and using the law of total expoctation, we have
Elg(si+1 [s)] B[F((H+)) F(s;)) 1 k
"[(((s)) F(s:)) - (1 c)v--1-
Since E[F(s*)] F(s"), get
(F(s*) E(F(s)) - -F(s)) 1 1- (F(s*) - E(F(s:)) - (1 e)
Taking B,+1 F(s*) E[F((H+1) and 3= (1 (1) we get
B S BB, + (1 E)ut+1-
By induction, we have
k
By < 3* By + (1 - c) Σ
gh-
(13)
im
17

---

Published in Transactions on Machine Learning Research (04/2024)
If (1 - -) 3 S v, the inequality 13 implies
E[F(s:)) 2 (1 - E- --e
c) - -
(14)
where we also use the relation that - -1-11-9))) -1- (1--))) Thus, the result
140 is true when both the following conditions hold:
(1 - Ei gh-ip S
2. the result
12 is true for every itcration of BSG (Algorithm
However,
12 depends the validity of 11 Now, BSG's step 2 returns Pe-optimal solution with probability
- 8, The probability that BSG's step 2 does not return v--oplimal solution in any ileration i E (1,...,k) k}
is Σ, 8, = Hence, the probability that BSG's step 2 return vi-optimal solution in every iteration for
.. 1. ...... h is 1 8. Therefor, we prove that (140 is true with probability 1 8 (1 e) Σi= gk S v
and Σ, & 6, which completes the proof.
B.2 Proof of Lemma 3,3
The i-th iteration of BSG-ABA calls the ABA algorithm once obtain a vi, 6PCC solution. For arms, the number of samples required by ABA algorithm Hassidim et al., 2020 Theorem to seleet v,-best arm with probability at least 1 6 is at most 18%
- log( }). One stochastic function f call is required for every sample z. The candidate set R2 in each iteration i of BSG-ABA has [R,]| = f log(?) elements. Hence, total
number of function calls required by BSG-ABA across k iterations is
&
R
k
18n kut
-
NABA
log
log
log
0z
8
For arms, the number of samples z required by the NE algorithm select 1;-best arm with probability at least 1- is 24 log(#) )). This well-known result can be proved using the Hoeffding bound (Hassidim et al, 2020 Appendix A). The i-th iteration of BSG-NE calls the NE algorithm once to obtain Vi P,-PAC solution. Hence, the total number of function calls required by BSG-NE across A iterations is
R log
[ 8;
2n ku?
Y log
- log
:
NNE
log
t=1
B.3 Alternating minimization algorithm for
8
We first state the following result Micchelli & Pontil
2005
Lemma 26).
Lemma B.2. Let r > 0, p= + a. - 1, k. Consider the below optimization problem:
min .y>0,
(15)
37
The optimal objective of the above problem is
i== ai
which occurs at
z
ag
(16)
Proof. Lemma B.2 be proved using the Hölder inequality Miichellli & Pontil
2005 Lemma 26).
7
18

---

Published in Transactions on Machine Learning Research (04/2024)
B.3.1 Solve (8) for given {6.
We first solve for {ui)em can be rewritten as
1 for given {d:) The optimization problem
corresponding to this setting
& Σ
min 9020
(1 log(;:)
1=1
(17)
s.t.
(1 c)
g ih-iv, S v.
i=
To solve this, we first use the substitution
vz+
This leads to the following equivalent optimization problem:
(1 - (L-c)V/ 1 1og(d;)
min 2>>
22
i=1
(18)
Σ Vx 1.
s.t.
We now make use of Lemma B.2 The expression of optimal vf for given {6:)
x
va
V = (1 e) g
(19)
(1 (1-6) -))
where xf given by 116 a; (1-e) (2-e)---lon w-//
1/2, and =
B.3.2
Solve 8 for given {v
We now solve for (6.) in for given {ur Hh The optimization problem can be rewritten as
corresponding to this setting
min 6UV
log(d.)e,*
1m1
(20)
s.t.
d 6.
This can be solved using Lagragian duality and at optimality, o7 -/ (Σ,
B.4 Proof of Theorem 3.5
For this, we simply need to solve Problem S only with respect to {ur fvik and fix 5; = 8/k Vi. Appendix B.3.1 discuss this optimization problem. Hence, we get the expression of optimal of Vi by setting 6, = 6/k vi
in 19h. Plugging these values of { and (5. back in NABA and NNE (7) completes the proof of Theorem 3.5
B.5 More details on c(k) < 22 in Remark 3.6
22/33
The expression of c(k) is c(k)
We consider the function
k(1- 37733-
(1 - /28/3/
G (k) (c(k)/k2)113
k(1 - B(1332/33
19

---

Published in Transactions on Machine Learning Research (04/2024)
It is easy see that if (1) < 1, it implies that c(k) I k?. Hence, aim to prove e1 (1) < 1 in the following way.
The binomial theorem for fractional exponent is given by (1 + x) = + xx
56 11
21
p/q k k
) x². Hence,
1- k
2 2
211 (1 c)
... ) (1-))
k(1
=k 1- =k1
1
(21)
3 k
332! 1
We also note that g2k/3
22/3
is an increasing function of k. bounded above by e25
Hence, C2 (2k (1 -22/33 is decreasing function of k. We note that k = 3, c2 g2k/3
1 1 8² =(1 (1- 11-- (1-e)²
9 + 21 - c)) - [1 -l. c). Thus, we have shown that for 2 3,
(2()) S c2 S 5 c)-
(22)
Using 21 and 12
we have that for k 2 ci (k) < = (k) S
For k B annd get c(1) 1 = =
For k 2, 8 + e)/2 and we get (2)
1-/4/3
1
1 c(2) 2
2(1 2(1-32/3)
2
B.6 Algorithm for solving 9
Using the substitution 4; = (μ - log(d:))u,
> 0, the problem is equivalent to
min 6.0.00%
(1 - c)
(u log (6.))/4
i=1
(23)
s.t.
4 <
6, ò.
Problem (33 is non-convex and can resort to iterative algorithm scheme to empirically solve it. In
particular, we make use of the manifold optimization framework (Bouma] 2023 on the multinomial manifold
(Sun et al. 2016 using the Manopt toolbox [Boumal et al. 2014
B.7 Proof of Theorem 3.9
The proof strategy of this result is similar to that employed for Theorem 3.5
We require solving Problem (9 only with respect to { and fix 6, = 5/k vi. For this, we first apply the following substitution:
2; No
(24)
where = 18m (og()))g((? for BSG-ABA and b 2n log log(?)) log(?) for BSG-NE. &
Following this substitution, Problem 9 with d; 8/k Vi can equivalently rewritten
b 3
min ay 200
(1-6) c)
No
T2
(25)
h
s.f.
x
< 1
20

---

Proof. The proof is similar to the proof of Lemma B.1 except that R. is the entire set S \ In the given iteration, BG's step 2 (PAC_BEST_ _EM) selects a vo-optimal element with probability 1 1 8,. That is, Published in Transactions on Machine Learning Research (04/2024)
We now employ Lemma B.2 to solve the above Problem
25
The expression of optimal iy is
1
(26)
No
where of given by (16, oz = 3) computed as n² (1 -) E) i/.
No r 2, and 3/2. The overall D for BSG algorithms is
C Theorems and proofs related to the proposed BG algorithm
In this section, we re-state the theorems the main paper for the proposed BG algorithm. The proofs follow the proof strategy of Section B
Lemma C.1. Given a current solution of BG and let (vo, 6;) be the PAC parameters for the nert itcration. Then, the following holds with probabilily - ō;: the goān of BG (Algorilhm 7 in one ileration is al least 8. (o(ss)) - vv) where s* denote the optimal solution of problem
g(sis) max g(|s)) vo
Σ (o(s)s) vo) 2 K
Σ (g(s|s) vo).
with probability at least 8, This completes the poof of the lemma.
Theorem C.2. Let s be the solution obtained by BG (BG-ABA or BG-NE) for 2 with given PAC parameters (v, Then, s (v, PPAC solution of (2) if per-iteration (vt, policy is defined as
Σ 8 and
Σ a "-vn 'm Sv.
where = 1=
Proof. The proof follows the proof strategy of Theorem 3.1 and relies on Lemma corresponding to 13 is
C11
The inequality
A.+1 S aA; + 1/+1:
where A4+1 F(s)) - F(4+1) and a = - 1/k. Summing over from = to i = k 1, we get A S a "A + Et= 'v. Finally, we have the inequality F(sx) 2 (1 e1-e- --)===")((s)) - with Σ a 1i Sv. 7
Lemma C.3. Let NABA and NNE be the upper bounds on the number of stochastic function f evaluations required by BG-ABA and BG-NE (Algorithm 71, respeclively. Then,
NABA
Σ log 14
(27)
NNE
2n log
0,
Proof. The proof is similar the proof of Lemma 3.3 except R, is all the remaining candidates set and RR is n whose upper bound is n that is used in the expressions.
Theorem C.4. Let (V7,67 be optimal per-iteration policy corvesponding to the minimrum number of stochastic function ff calls required by BG to obtoin a (v, PPAC solution. Then,
w(1 2/3 8)/3
(1-a2
and 07 = 8/k. The expressions of NARA and NNE corresponding to (vt,ot) are
NABA = 18nk log ($) c(k) and
2nk N = Da
log 5 c(k),
2k/33 k11-07733 and a 1/k.
where e(k)
21

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. We follow the proof of Theorem 3.5 make Lemma B.2
and use the substitution
VJi ak tv/v..
Theorem C.5. Given fired budget No (the marimam number of slochastic funclion J culls allowed) and confidence 6, BG-ABA and BG-NE achieve (VABA, 5)- and (vÑE, 5)-PAC solutions, respectively, where
1-a2k/3
3/2
18n No
(og(k/8) 1/2
VABA
1/a
1-a22/9 1-a2/3
24/3
3/2
2n (k/6)
1/2
VNE
No
and 1- 1/k. The corresponding per-iteration policy of BSG-ABA is given by 62 6/k and
18h (og((
1/2 (i-k)/3
No(1-0273)
Similarly, the per-iteration policy of BSG-NE, corresponding to (U 8), is given by 03 = 6/k and
vf 2n loglnk/ (1) 2k/3g
1/2
(1-3333
Proof.
We need to use Lemma
B.2 after doing the following substitution:
b
2;
No
where b = 18n log(5 k) for BG-ABA and b = 2n log m/) for BG-NE. The above substitution implies of 8
k-j No in Lemma B.2
D Empirical results on optimizing both {u:}/ and {5.) for learning policies
Minimizing computational cost setting. Here, we compare the solution obtained by optimizing problem in two settings: (Policy 1) the policy learned by having uniform per-iteration confidence, as discussed in Theorem 3.5 and (Policy 2) the policy learned by solving S via alternating minimization algorithm
discussed in Appendix B.3
Figure shows the values and the trade-offs obtained by the two policies. Although the alternating minimization approach leads smaller computational cost (in terms of the number of stochastic function calls) than the one proposed in Theorem 3.5 the improvements are only around 0.23%.
Fixed computational cost setting. Here, we compare the solution obtained by optimizing problem 9 in two settings: (Policy 1) the policy learned by having uniform per-iteration confidence, discussed in Theorem 3.9 and (Policy 2) the policy learned by solving g via. Riemannian gradient descent based algorithm discussed in Appendix B.6
Figure 4 shows the values of {vr} and {6,} obtained by solving the problem 9 Although we obtain a smaller v = (1 -) Et gh using joint optimization of {ui} and {5,} than that from Theorem 3.9 the improvement is around 0.17% for the problem setting in Figure 4
the above setting, we are given the confidence parameter along with the cost c. However, it might be interesting look at how the optimized v (i.c., the argmin solution g varies with dif- ferent choices of but fixed c. Figure shows the (v, Pareto optimal curve for given cost Here, 8 {10-8, 10-7 10-6, 10-3 10-1, 10-3 10-2 100101110 10.2,002,,0033 0.3).
22

---

Published in Transactions on Machine Learning Research (04/2024)
Pikee
14
17
values
valuess
14
077
13
4
5
4
indices
indices
(a) [1s] values
(b) {6.] values
Figure 3: We plot the values of {ur} and {6r} for two different policies the fixed (v, 6) setting. The problem
instance has & 10, 10, 5 = 10-3, and c= 10-3 Policy refers the values proposed in Thcorem 3.5
and 8; = 6/k 10 Policy 2 refers to the solutions obtained by solving the problem (8) which optimizes both [v;} and }
1.15g
X10
Pilke
Pilee
vallues
values
1:2
10
0.0
710
5
Aa
V indices
indices
(a) {1 values
(b) {6:) values
Figure 4: We plot the values of {14} and { for two different policies in the fixed cost setting. The problem
instance has to = 10, 8 = 10-3 = 10-3, and c= 100. Policy 1 refers to the values proposed in Theorem 3.9 and 5; = 6/k = 10-1 Policy 2 refers to the solutions obtained by solving the problem 19) which optimizes both {M:} and {
E Additional discussion
In this section, discuss few other details related to the developments in the main paper.
23

---

Published in Transactions on Machine Learning Research (04/2024)
10
8
10
10
10
10a
10
10
102
10
10a
5
Figure 5: Pareto optimal curve in the fixed cost setting.
E.1 On ProtoBandit (Roy Chaudhuri et al. 2022)
The recent work of Roy Chaudhuri et al. 2022) also uses a MAB setting to solve exemplar-basee clustering problem. In particular, they also makes use of the ABA algorithm. However, a number of crucial differences exist that are highlighted below.
The focus in (Roy Chaudhuri et al. 2022 is limited exemplar-based clustering problem. On the other hand, have proposed results for general SSM problems of type (2)
Roy Chaudhuri al. (2022) do not discuss optimizing the (14,6,) policy and use v4 vo (i.e., fixed user-defined v4) every itcration of ProtoBandit. In contrast, propose how to optimize the per-iteration (vi, 5:) policies in different settings.
For the exemplar-based clustering problem, the number of pairwise distance computations required by ProtoBandit is O(nk*), whereas proposed BSG-ABA algorithm require O(nk²) pairwise distance computations. Hence, our algorithms show an improvement of a factor k.
As detailed in (Roy Chaudhuri et al. 2022 Section 3.5), they implement a KL-LUCB algorithm based method with carly stopping hcuristic for empirical study. However, they do not provide any PAC style analysis of their implemented algorithm.
E.2 Regarding Remark 3.8 on BanditPAM (Tiwari et al. 2020
For PaM (Tiwari al. 2020) and the proposed algorithms, the confidence 7 mentioned in our draft. corresponds the 8 confidence of the PC guarantce (BanditPAM) and the 1-8 confidence of the PAC guarantee (proposed algorithms).
The 1aaddiPAAM paper mentions different å parameter, henceforth referred to as бBP. The dBP parameter in BanditPAM's draft (and code) corresponds to 1 - 2n25gp confidence for every BanditPAM iteration. Tiwari et al.) 2020 Remark A1 in the Appendix section) details this. Hence, in terms of the ônP parameler, BanditPAM guarantees the following across iterations. Given the parameter бвP, Tiwari et al. (0200) provide the following guarantce: With probability at least 1 2ndkópp. BanditPAM (restricted the submodular BUILD step) returns the same of & points as Greedy and the required number of stochastic function calls (NBP) satisfies [[[Nr]] O(n (k)örr nd2(k) (gg(1/Br)).
24

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Approximate best arm (ABA) algorithm
Input: 8, R. 2, v
t == R.
if n < (003, J then
4:
naivellimination(s. 2, v.
5: else
6: r + /// elements selected uniformly at random from set R.
7: t1 + aggressiveeliimmnttioas (1 1/e)u,
naiveEliminationss Ur, Z, e
end if
10: Output: s. {s is (v, oe-best element]
E.3 On (Karimi al. 2017 Proposition 3)
We begin by noting that Karimi et al. (0017) have proposed multilinear extension based approach for maximizing weighted coverage functions, which is subclass of the SSM problem (2) As discussed in (Karimi ct al. 2017 Section 3), the multilinear extension G' of a submodular function F lacks concavity guarantee and may suffer from bad local optima. Thus, they consider concave contimuous extensions of G that are efficient. to compute and are at most a constant factor away from to ensure a good quality solution. Weighted coverage functions one such class of (stochastic) submodular functions where such an extension can be efficiently computed.
For weighted coverage functions, the stochastic function is submodular. However, noted in (Mokhtari et al.
2018 2020), the stochastic function f need not be submodular for SSM problems. Overall, Karimi
et al. algorithm. For the SSM problem 2 SGA does not provide tight guarantees as it offers OPT/2 v lower
2017 propose concave relaxation scheme and employed projected stochastic gradient ascent (SGA)
bound in expectation after O(n /= iterations (assaai et al. 2017).
Karimi et al. (2017) have also analyzed vanilla Hoeffding bound based strategy for maximizing weighted coverage functions. Karimi et al. (2017] Proposition 3) crucially assume the submodularity of the stochastic function f. As discussed above, this assumption is not made in the subsequent SSM literature (Mokhtari et al., 2018 2020 Hassani et al. 2019 2020). Following these later works on SSM, we propose approach for the general stochastic submodular function F' in and do not assume submodularity of the stochastic function f.
F
Experiment details
Some additional details regarding experimental settings are below.
For BanditPAM, we use the code from hta.lt/ee.ggttthh.cco/////iirrrt fixes a critical bug empirically do not obscrve much difference in BanditPAM's results with different values of the confidence parameter 8 (0.01, 0.001, 2k/n]. In this last setting, the 5 varies with k.
which In addition, we
For SCG, the error parameter v influences only the number of iterations. In the implementation, we lower bound the number of SCG iterations with 1000 and upper bound it by 20000. With 20000 iterations, SCG takes around 42 minutes on the TIN dataset for k: 2 90 and is the slowest baseline in terms of time). Since the number of iterations for SCG with different v parameters (at high k values) the same (20000), their plots coincide.
G Bandit algorithms for PAC BEST ARM in Algorithm
2 It employs the naive elimination and aggressive elimination strategies, which are detailed in Algorithms
We detail the ABA algorithm (Hassidim et al. 2020 in Algorithm
3 and 4 respectively.
25

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Naive elimination algorithm
1: Input: s, R. 2, v
2: t t= R.
3: Sample a subset 2/ [ 2 with 1=
log [t] 22 8
samples.
8 arg max h(als; 21)-
Output: s. {s (v, best element)
Algorithm Aggressive elimination algorithm
1: Input: s, R. 2, v
2: t R.
3: to = -t, :tt= =
blogt 33/T
[(t)
log log 4 log लम
for EE 20. [T{) do Sample subset Z, Z with = (E + [) log / samples
For each element te, compute h(als; Zi) and sort the elements in descending order based the value of h(ass; 2,)
7: 6e+1 + the Lop-([te]1 + e(())) elements in tz.
8: end for
Output: the set elements tr()++1-
26


Reviews:
[{"review_id": "vt8ZSRlofb", "reviewer": "Reviewer_gLG2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I might have missed something, but I believe that the solution proposed by the authors is not better than the following simple solution:\n\n- Choose $u = {k \\over \\nu^2} \\log({2 n \\over \\delta}) $ samples drawn i.i.d. from $P$, and denote them by $Z_1,...,Z_u$\n- Define the function $\\Phi_u(s) = {1 \\over u} \\sum_{i=1}^u f(s,Z_i)$\n- Maximize $\\Phi_u(s)$ over $s$ under the constraint that $|s| \\le k$ using the basic greedy algorithm\n\nOne can readily check that evaluating $\\Phi_u(s)$ for a given value of $s$ requires $u$ functions evaluations, so that the greedy algorithm will require at most $O(n k u) = O(n {k^2 \\over \\nu^2} \\log({n \\over \\delta}) )$ function evaluations in total.\n\nFurthermore, with probability greater than $1-\\delta$ we have that \n$$\\max_{s: |s| \\le k} |\\Phi_u(s) - F(s)| \\le \\nu$$ \nso that maximizing $\\Phi_u$ will yield the same result as maximizing $F$, up to an additive error of $\\nu$. \n\nIndeed, $\\Phi_u(s)$ is an i.i.d. average of bounded random variables in $[0,1]$ with expectation $F(s)$ so from Hoeffding's inequality\n$$\nP(  |\\Phi_u(s) - F(s)| \\ge \\nu   ) \\le 2 \\exp(- 2 u \\nu^2 )\n$$\nand since there are at most $n^k$ sets $s \\subset [n]$ verifying the constraint $|s| \\le k$,  a union bound yields\n$$\nP( \\max_{s: |s| \\le k} |\\Phi_u(s) - F(s)| \\ge \\nu   ) \\le 2 n^k \\exp(- 2 u \\nu^2 )\n$$\nLetting $u = {k \\over \\nu^2} \\log({2 n \\over \\delta})$ proves that indeed:\n$$\nP( \\max_{s: |s| \\le k} |\\Phi_u(s) - F(s)| \\ge \\nu   ) \\le \\delta\n$$\n\nSo this trivial approach yields the same guarantees as that of the authors: approximation guarantee is $F(s) \\ge \\gamma(0) OPT - \\nu$ with probability greater than $1-\\delta$ and number of function evaluations is $O(n {k^2 \\over \\nu^2} \\log({n \\over \\delta}) )$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of maximizing a submodular function $F(s)$ over the subsets of $[n]$ under the cardinality constraint $|s| \\le k$. They further consider the case in which the evaluation of $F$ might be expensive, because it is given as an expectation $F(s) = E(f(z,s))$ where $z \\in Z$ and has distribution $P$. Denote by $m$ the size of $Z$, in order to compute $F$ exactly one would have to enumerate the elements of $Z$ requiring $m$ evaluations,  which might be infeasible if $Z$ is large. Instead, the authors propose to use sampling strategies, in the sense that one may draw samples from $P$, and the goal is find an approximate maximizer of $F(s)$ with a limited number of samples.\n\nThe authors propose to modify the greedy algorithm for their setting, by running a best arm identification algorithm $k$ times, in order to mimic the way the greedy algorithm would select the successive items added to $s$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should clarify how their approach compares with the simple approach highlighted above.", "broader_impact_concerns": "Not Applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w82oOnNs4H", "reviewer": "Reviewer_6Yj6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is overall easy to follow.\n1. It is great to provide a table to compare the theoretical performance among algorithms in terms of both approximation guarantee and number of calls of function computation.\n\nWeaknesses:\n1. I would appreciate a better comparison between algorithms in Table 1.\n    1. In the discrete setting, the Greedy algorithm provides a deterministic approximation guarantee while the BG algorithm provides a probabilistic one.\n    1. In the stochastic setting, I think it may not be that difficult to extend the results to continuous bandit setting and provide a better comparison to existing algorithms. \n1. Except for Section 3.4, the paper focused on the fixed-confidence setting of best arm identification. In the fixed confidence setting, the BG/BSG algorithm is proved to stop and identify a satisfactory set after a certain number of time steps. However, I doubt if such a fixed-confidence algorithm and analysis can be trivially applied as in Appendix B.5. \n    1. First of all, Algorithm 1 may not terminate within a fixed time horizon with probability 1. Eq. 9 is not the correct definition of best arm identification in multi-armed bandits.\n    1. The authors may consider to revise Algorithm 1 and the analysis for the fixed-budget setting. The theoretical guarantee should be verified.\n1. In the experiment setting, I wonder what is the source of randomness. Why do we need the BSG algorithm? Why not simply the BG algorithm? Besides, what is the function $f$ in the experiment section? \n1. Novelty: I am curious why the author(s) named Algorithm 1 as a bandit-type algorithm instead of a greedy algorithm? As online optimization problem has been studied for years, I suggest the author(s) to highlight their significant contributions or analytical challenges.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considered the submodular maximization problem with a bandit-like algorithm. In detail, it proposed the bandit greedy (BG) and bandit stochastic greedy (BSG) algorithm, where an ABA or NE can be applied as a sub-routine. This work compared its performance to existing algorithms both theoretically and numerically.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the 'Weaknesses' part in the **Strengths And Weaknesses** section.", "broader_impact_concerns": "No ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cqvOIWJ5Bj", "reviewer": "Reviewer_CzSb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe considered problem, stochastic submodular maximization with cardinality constraint, is important and finds many real-world applications, such as social influence maximization, exemplar-based clustering, recommender systems and prototype selection.\n2.\tThe idea of regarding the selection of the next element at each iteration as a best arm identification problem is interesting and novel to the stochastic submodular maximization literature.\n3.\tThe improvement of the number of stochastic function calls ($N$) over existing submodular maximization algorithms is significant, which makes a solid technical contribution to the literature.\n4.\tThe authors also conduct experiments to validate the superiority of their algorithms in terms of optimization quality and computational efficiency.\n\n\n**Weaknesses:**\n\n1.\tIn table 1, it seems that the authors compare the number of f calls mainly with respect to $n$. The authors should give more discussion on other parameters, such as $m$ and $\\nu$. How do the sizes of $n$, $m$ and $\\nu$ influence the performance superiority of the compared algorithms?\n2.\tThe authors should comment more on the theoretical results for the fixed-budget setting (Theorem 3.8) and connect these results to the literature. For example, it would be better to give a comparison between these results and existing fixed-budget results or any applicable lower bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on the problem of maximizing non-negative, monotone, stochastic submodular functions under cardinality constraint. The paper considers a discrete, (stochastic) greedy setting under a probably approximately correct (PAC) setting, i.e., the goal is to obtain solutions whose expected objective value is greater than or equal to $(1-1/e-\\varepsilon)OPT-\\nu$ with at least $1-\\delta$ probability.\nThe authors propose novel bandit stochastic greedy (BSG) algorithms, where the selection of the next element at iteration i is posed as a ($\\nu_i$, $\\delta_i$)-PAC best arm identification problem. \n\nGiven ($\\nu$, $\\delta$)-PAC parameters to BSG, the authors define a set of per-iteration ($\\nu_i$, $\\delta_i$)-policies such that any policy from this set guarantees a ($\\nu$, $\\delta$)-PAC solution for the stochastic submodular maximization problem using BSG. Next, they derive the optimal ($\\nu^*_i$, $\\delta^*_i$)-policy from this set which incurs the least computational cost in terms of the number of stochastic function calls ($N$). With the obtained optimal policy, they show that BSG has better complexity in $N$ than the existing approaches. Lastly, they further analyze the fixed-budget setting. Experiments illustrate the efficacy of the proposed approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the review on weaknesses above.", "broader_impact_concerns": "I do not have ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally agreed that the paper satisfies the criteria of TMLR. The authors adequately addressed reviewer comments. See my comments about claims and evidence for minor concerns that should be addressed in the camera ready.
Decision: Accept (poster)