Efficient Submodular Optimization under Noise: Local Search is Robust
Authors: Lingxiao Huang
Yuyi Wang
Chunxue Yang
Huanjian Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: submodular
optimization
noise
local search

Abstract: The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by Hassidim and Singer (2017). For a cardinality constraint, we propose an algorithm achieving a near-optimal (1-1/e-O(epsilon))-approximation guarantee (for arbitrary epsilon > 0) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of Singer and Hassidim (2018). For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.

Efficient Submodular Optimization under Noise: Local Search is Robust
Lingxiao Huang Huawei TCS Lab >> Nanjing University huanglingxiao www.oo.......... com
Yuyi Wang
Swiss Federal Institute of Technology yuylvangs208gmai1 com
Chunxue Yang Nanyang Technological University chunxue001@e .ntu..uu.. edu. sg
Huanjian Zhou
The University of Tokyo zhou@ms. k. k.u-tokyo ac
Abstract
The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there cases where one only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by [II). For cardinality constraint, propose algorithm achieving a near-optimal (1- - O())) -aprrxximation guarantee (for arbitrary E > 0) with only polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of [20]. For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design novel local search framework that can handle the effect of noise and construct certain smoothing surrogate functions for noise reduction.
Introduction
Consider the following problems in machine learning and operations research: (1) selecting set of locations to open up facilities with the goal of maximizing their overall user coverage [3]; (2) reducing the number of features in machine learning model while retaining much information as possible [23]; and (3) identifying a small set of seed nodes that can achieve the largest overall influence in social network [14). Solving these problems all involves maximizing monotone submodular set function / 2 + IR subject to certain constraints. Intuitively, submodularity captures the property of diminishing returns. For example, newly opened facility will contribute less to the overall user coverage if we have already opened many facilities and more if we have only opened a few. Although the general problem of monotone submodular maximization subject to cardinality or general matroid constraint is NP-hard (5). the greedy algorithm, which selects an element with the largest margin at each step, can approximately solve this problem under cardinality constraint by factor of 1 1/e, and this approximation ratio is tight [18]. Moreover, non-oblivious local search algorithm, which iteratively alters one element improve an auxiliary objective function, is guaranteed to achieve an approximation ratio of 1/e for general matroid constraints (7].
In the literature, the submodular optimization problem usually assumes value oracle the objective function f. which means one is allowed to query the exact value of ((S) for any S C N. However, in many applications, due the uncertain nature of the objective or the errors involved in the evaluation. one can only access the function value in distorted or noisy form. For example, Globerson and Roweis O pointed out that selecting features construct robust learning model is particularly
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

important in domains with non- non-stationary feature distributions or input sensor failures. It is known that without any assumption on the noise, direct adaptions of the greedy and local search methods mentioned above may yield arbitrarily poor performance [12]. To address this issue, Hassidim and Singer 11 introduced and studied the following problem of monotone submodular maximization under noise: For a monotone submodular function f. given a noisy value oracle f satisfying ((S) = =s> (SS) for each set 5 S N, where the noise multiplier {s is independently drawn from certain distribution, the goal is to find set S maximizing (((S) under certain constraints. Some applications of this problem are provided in [20) such as revealed preference theory [3] and active learning [6]. Hassidim and Singer [II] showed that under sufficiently large cardinality constraint, a variant of the greedy algorithm achieves a near-optimal approximation ratio of - _ - O(e) for arbitrary& > O. The problem becomes more challenging when the cardinality constraint is relatively small since there is less room for mistakes. In a subsequent work, Singer and Hassidim [20] developed another greedy- based algorithm for small cardinality constraints and showed near-tight approximation guarantee.
Despite these encouraging results, we want to point out two directions along this line of monotone submodular maximization under noise that still have room for improvements:
In the algorithm from (2)]. the query complexity to the noisy value oracle is exponential in E 11 which is costly when a near-optimal solution is needed, i.c., when the parameter e is close to 0. Is it possible to obtain near-optimal approximations for monotone submodular maximization under cardinality constraints with the number of queries polynomial in e ??
All previous works in submodular maximization under noise consider only the cardinality constraint, and no approximation guarantee is known under other constraints. Is there any algorithm that can achieve a constant approximation for submodular maximization under noise for more general constraints, such as commonly studied matroid constraints [16] 26]
In this paper, we provide answers to both questions above.
1.1 Our contributions
We study the problem of constrained monotone submodular maximization under noise (Problem 2.6). Following prior works [T] 20), we assume generalized exponential tail noises (Definition 2.5) and consider the solutions subject to cardinality constraints (Definition 2.2 and matroid constraints (Definition 2.3 The main contribution of this work is to show that for optimizing monotone submodular function under a cardinality constraint, (1 - - -(s))) ((e)))-aproxiiationn can be obtained with high probability by querying the noisy oracle only Poly (n. ) times.
Theorem 1.1 (Informal, see Theorems 4.1 and 4.6). Let > 0 and assume n is sufficiently large. For any E Q (t). there exists an algorihmm that returns a (1- -()))-(pproxiiii -aproximaation for the monotone submodular maximization problem under a caatrrarccur r-cardinaluty constraint, with probability 1- (1) and query complexity Poly (12, 2) to f.
For a cardinality constraint, this paper and prior works [ 20 all achieve near-optimal ap- proximations. However, our result is applicable for a larger range 2 (t) of cardinalities than Ω (log log n e e-2) in [II]. Moreover, we only require Poly (rt, ! queries to the noisy value oracle, which improves the query complexity Q(n²) of 20)
Our main idea to address this problem is to employ local search procedure, whereas prior methods are all variants of the greedy algorithm. Intuitively, local search is more robust than the greedy since the marginal functions are more sensitive to noise than the value functions. To achieve a sufficient gain in each iteration, the greedy algorithm must identify the element with maximum margin. In contrast, local search only needs to estimate the sets' values. This is why we can improve the query complexity to Poly (n. !) for small cardinality constraints.
We present a unified framework (Algorithm I for enhancing the local search to cope with noise. One of the main differences between our framework and the non-oblivious local search proposed by 7 is that we use an approximation of the auxiliary function (Definition 3.2) rather than the exact
Note that Singer and Hassidim 20 also provide an algorithm to deal with general matroid constraints. However, will argue in Section A that their algorithm fails to obtain the approximation guarantee they claim.

---

one due to the presence of noise. We analyze the impact of the inaccuracies on the approximation performance and query complexity of the local search (Theorem (.3).
Another difference is the construction of the auxiliary functions used to guide the local search. We construct the auxiliary function not based on the objective function but smoothing surrogate functions.
A surrogate function h needs to meet two properties: (i) h should depend
averaging set of size poly(n). such that h(S) and its noisy analogue h(S) close for all sets S considered by local search; (ii) needs to be close to the original function f. such that optimizing h can yield a near-optimal solution optimizing However, large averaging set is more likely to induce large gap between the surrogate and original function, making simultaneous fulfillment of both properties non-trivial.
In this paper we carefully design the smoothing surrogate functions as follows. For a set with size E Q (t) no (n), we define the smoothing surrogate function h as the expectation of f's value when a random element in N is added to the set (Definition 4.2). This surrogate function is robust for a relatively small cardinality as it is based on rather large averaging set with size nearly n, but too concentrated for large cardinality close to n. Thus, we consider another smoothing surrogate function ıи for size E 92 (n)/ defined as the average value combined with all subsets of H (Definition 4.7) The auxiliary functions constructed on both smoothing
certain small-size
surrogates are shown to have almost accurate approximations (Lemma 4.4 and 4.9p. Consequently, we can upply our unified local search framework (Algorithm T) in both cases (Algorithm) 2 and
and guarantee to achieve nearly tight approximate solutions (Theorem 4.1 and 4.6
The other contribution of this paper constant approximation result for maximizing monotone submodular functions with noisy oracles under general matroid constraints.
Theorem 1.2 (Informal, see Theorems 5.1 and 5.2). Let > and assume n is sufficientll
large. For any Ω (E- log(E-")), there exists algorithm that returns (1 (1 (1-1) O(=))- opproximation for the monotone submodular maximization problem under a matroid constraint with rank r, with probability o(1) (1) and query complexity at most Poly (n, 2) to f.
To the best of our knowledge, this is the first result showing that constant approximation guarantees are obtainable under general matroid constraints in the presence of noise. To cope with noise, one common approach for cardinality constraints is to incorporate some extra elements to gain robustness and include these elements in the final solutions. However, for a matroid, additional elements may undermine the independence of set. To address this difficulty, develop technique for comparing the values of independent sets the presence of noise, which allows us to select either the local search solutions or the additional elements for robustness and leads to an approximation ratio of
1.2
Related work
Research has been conducted monotone submodular maximization in the presence of noise. We say a noisy oracle is inconsistent if it returns different answers when repeatedly queried. For inconsistent oracles, noise often does not present barrier optimization, since concentration assumptions can eliminate the noise after sufficient number of queries [21 13]. When identical queries always obtain the same answer, the problem becomes more challenging. Aside from the i.i.d noise adopted in [1 20 and this paper, Horel and Singer [12 study submodular optimization under noise adversarially generated from [1 e/r, 1 1 e/r), where the greedy algorithm achieves ratio of 1 - 1-1/e- (s). No algorithm can obtain a constant approximation if noise is not bounded in this range.
2 The model
This section formally defines our model (Problem 2.6 of maximizing a monotone submodular function (Definition 2.1] under a cardinality constraint (Definition 2.2p or a matroid constraint (Definition 2.3). given access to noisy value oracle (Definition 2.4). Let N be the ground set with size |N] = n, and we use the shorthands + = SU (x) and S---- --r = (xr throughout this paper. We first review the definition of monotone submodular functions.
3

---

Definition 2.1 (Monontone submodular functions). A function f :2N - R>0 is monotone submodular if 1) (monotonicity) f f(A) - f(B) for any A C S N: 2) (submodularity) for any subset A, B S N and I E N: f(A + x) f(A) > / [ + J(B).
There are various examples of monotone submodular functions in optimization, such as budget additive functions, coverage functions, cut functions and rank functions M. Since the description of a submodular function may be exponential in the size N. we usually assume access of a value oracle that answers f(S) for each S S .N. Let I denote collection of feasible subsets S C N. The goal of a constrained monotone submodular maximization is to find a subset S _ I to maximize f(S). The objective f is further assumed to be normalized, i.e., f(2) O. We consider two types of constraints in our models: cardinality constraints and matroid constraints.
Definition 2.2 (Cardinality constraints). Given a ground set N and an integer r 2 1, a cardinality constraint is of the form I(r) = {SS N |S| r).
Definition 2.3 (Matroids and Matroid constraints). Given a ground set N, a matroid M is represented by an ordered pair (N, ((M)) satisfying that 1) Ø I(M); If / E I(M) and I' C then I' E I(M); 3) If I1, I2 C I(M) and | < [I2], then there must exist an element E Iz I1 such that 1 U {e) E I(M). Each I E I(M) is called an independent set. The maximum size of an independent set is called the rank of M. We call the collection [(M) a matroid constraint.
Assume we are given a membership orucle of I(M) that for any set C N answers whether I(M). As widely used combinatorial structure, there is an extensive study on matroids (28 19 27 Common matroids include uniform matroids, partition matroids, regular matroids, etc. See [9] for more discussions. Specifically, uniform matroid constraint is equivalent implying that cardinality constraints are a special case of matroid constraints.
cardinality constraint,
Noisy value oracle. It is well known that given an exact value oracle to f. for any E >> O, there exists a randomized (1 1/c- a) appproximate algorithm for the submodular optimization problem under matroid constraint, i.e., maxsçr (SS 12 77. However, as discussed earlier, the value oracle of may be imperfect, and we may only have noisy value oracle f instead of f. We consider the following noisy value oracle that has also been investigated in 12 11.
Definition 2.4 ((Multiplicative) noisy value oracle (11). We call f 2 + R2o (multiplicattive noisy value oracle of f. if there exists some distribution D s.t. for any S C N. f(S) = (Sf where Es is ii.dd drawn from D.
Throughout this paper, we consider general class of noise distributions, called generalized exponen- tial tail distributions, defined in (00).
Definition 2.5 (Generalized exponential tail distributions (00). A noise distribution D has a generalized exponential tail if there cxists some zo such that for every > zo the probability density function p(x)= = e- e=)( where g(x) = E; c:27 for some (not necessarily integers) no 2 ? 2 8..77 2 1 and co > O. If D has bounded support we only require that either it has an atom at its supremum or that p is continuous and non-zero at the supremum.
W.l.o.g., we assume D = 18 As mentioned in (20), the class of generalized exponential tail distributions contains Gaussian distributions, exponential distributions, and all distributions with bounded support that is independent of n.
The model. We are ready to propose the main problem, which has already been considered in 20
Problem 2.6 (Constrained submodular optimization under noise). Given a noisy value oracle f: 2N + Ro (with a certain generalized exponential tail distribution D) to an underlying monotone submodular function f. and cardinality constraint I = I(r) or a matroid constraint I I(M), the goal is to find S C I to maximize f(S).
3 Local search with approximate evaluation oracles to auxiliary functions
This section proposes a non-oblivious local search framework with noisy value oracle (Algorithm D. and gives an analysis (Theorem 3.3 of its performance. This algorithm is a generalization of that
Otherwiise can scale D be D' D/E[D] = L.
4

---

in [7] and will be used as meta- algorithg for solving Problem 2.6 Sections and Roughly speaking, local search framework first constructs "good" initial solution via a standard greedy algorithm and then iteratively improves the solution w.r.t. to auxiliary function (Definition 3.1
by swapping an element at each step. The following auxiliary function proposed by 7 is linear combination of the original function over all subsets.
Definition 3.1 (Auxiliary function (7]. Given monotone submodular function h 22N R2o-
its auxiliary function (P 2N R20 is defined as (P((S) Ergs 1|s1- h(T",, where
m,,t So (e (((e-1)--p'' 11 pp for all 2 t 0.
We instead of because we may do local search on certain smoothing surrogate function h of (see examples in Definitions 4.2 and 4.7). Note that чP, is also monotone submodular function. Given an exact value oracle of fP, and matroid constraint I(M), Filmus and Ward 7 show that there exists a local search algorithm that outputs a (1 (1-1/ 1--1/)-approoiil problem maXsgz(M) h(S). However, as mentioned before, we do not have an exact value oracle of h. Thus, it may not be possible construct exact value oracle of (ph. To understand how these inaccuracies can affect the performance of the local search algorithm, we introduce the following approximation for the auxiliary function Pi.-
solution for the optimization
Definition 3.2 ((a, 5, ((p))-aaprooiiiation of (hh). Given an auxiliary function Sh. matroid constraint I(M) and constants ā > O, we say randomized function 5hh is an (a, 6, 6,I()))- approximation Ąo, if for any independent set A E I(M).
P (o% (P)) > a. max
(S) S
SET(M)
Intuitively, Ph is a randomized version of Fh with an additive concentration guarantee, where the randomness may come from noise of or sampling error for estimating şh- As a. ô tend to O, 0 and I 2 Sh is exactly equivalent SPa- Now we ready to provide our local search framework (A (Algorithm I which is generalization of 7 Algorithm 2]. The main difference is that we use an approximation 6% instead of ς4, for evaluation at each greedy step (Line 4) and local search step (Line 12). The performance of Algorithm is summarized Theorem 3.3
ihh better approximation of {Ph- Specifically, when a
Algorithm 1: Noisy local search (NLS(P), I(M), A))
Input: A matroid constraint [(M) of rank r 2 1, a value oracle to an (a, ((M)) approximation (p of ph,, stepsize A (0, 1/2).
Set I - logi+
2(1+a) 1-2(++1aa
Initialize: Uo +- Ø, 0
while S do
+ arg max ++eET(M) (U, +c)
U. + Ul-1 +
ititl
So U- for i = 0 to I do for each element x E S, and y E N \ S, do
D Initial solution by greedy & Local search for T iterations
10
5. S. + y
11
S E ((M) then
12
if 9 (5)) (1 A) (S.) then An improved solution S was found
13
S41 + S
break and continue to the next iteration of
15 return S,
Theorem 3.3 (Performance of noisy local search). Let logi+A
I- 1-2(r+1)a With probability
2(1+a]
least (I + 1)rno, the output S₁ of Algorithm 7 is (1 - 1) (1 In(er) ((2 A)a A))-
approximate solution for problem maxsçI(M) h(S), with most (1 + 1) rn calls to Ph-
5

---

We defer the proof to Section C Roughly, given nearly accurate approximation 9h, we can show that the initial solution So is likely to be constant approximation for maxseI(M) Pp (S) (Lemma C.Tp. This guarantees that we will reach local optimal solution w.r.t. yP in iterations with high probability (Claim C.3). Then combining with basic properties of yp shown in 7 and the fact that
(Ph. is "close" to Ph, we obtain Theorem 3.3
Corollary 3.4. Assume n E cxp (()) - Ar Irlo we have I 5r and with
probability at least - (I + 1)rnd, the output S₁ of Algorithm 1 is a (1- 1 - E) approximate
solution for problem maxscI(MO h(S), with at most (T + 1) rn calls to Ph-
Our algorithms and main theorems for cardinality constraints
For different ranges of cardinalities, this section presents algorithms (Algorithm 2 [ 3) that return
(1 - - >approximatiinn for Problem 2.6 with only Poly (n, 1) queries to the noisy oracle f.
The analyses (Theorem 4.1 and 4.6 of the algorithms constitute a proof of Theorem
4.1 Algorithmic results for cardinality constraints when r E Ω
(nz)
We first present algorithm (Algorithm 2 and its analysis (Theorem 4.1 that are applicable for all
r E Ω (t) no n when n is sufficiently large. All missing proofs can be found in Section D
Theorem 4.1 (Algorithmic results for cardinality constraints when E Ω (1) no
n2 (nt)). Let
0 and assume E eQ (exxp ((E) (()) is sufficiently large. For any E (22 no (n)) there exists an algorithm that returns (1 (1- ( capprxxpxxiiiiionn for Problem 2.6 under
r-cardinality constraint, with probability at least O
and query complexity at most log
o (12log" r nie mmx (o,g))))) to
The assumption that n is sufficiently large is necessary and has also been adopted in prior works on noisy submodular optimization [1] 20). We achieve tight approximation ratio of - 1/e Oc).
Furthermore, we only require Poly (n, 1/2) queries to f. in contrast to Ωt (n (n) for the prior greedy algorithm [20].
4.1.1 Useful notations and useful facts for Theorem 4.1
Our algorithm and analysis are based on the following smoothing surrogate function h. Definition 4.2 (Smoothing surrogate function I). For any set S C N, we define the smoothing surrogate function ((S) as the expectation of f(S + e) over a random element e i.e. h(S) 1 E.EN f(S + e).
The surrogate function I(S) is robust to noise when |S] is relatively small since at this time h(S) is based on rather large averaging set with size nearly Note that h(S) becomes concentrated
f(S) as [S] n, and hence, consider this surrogate h for the range O (n²) We now show that h shares some basic properties with f.
Lemma 4.3 (Properties of h). The smoothing surrogate function h is monotone and submodular.
Note that h is implicitly constructed since we only have value oracle to f instead of f. Hence, construct an approximation of its auxiliary function yh; summarized by the following lemma.
Lemma 4.4 (Approximation of (P)). Let a. 8 E 1/2) and assume Q log(5-1)). There exists a value oracle O to an (a, 5, I(r 1)) apporooxxnnttooon Sh of 9h. which answering O(A) queries at most M θ (log r n max(r; logn)) times to f for each set A E I(r-1),
The above lemma indicates that for a sufficiently large we can achieve an arbitrary accurate approximation 6i of (hh, which queries ff only Ö(rn)) times for each (A).

---

More precisely, the relationship among 8 and n can be expressed as a "m((48-)) I c. nu (See Lemma D.5). where is the sub-exponential norm (Definition D.2] of the noise distribution 'D depending on the parameters c; "/ of density function, and c is an absolute constant. A small indicates concentrated noise distribution. Generally speaking, the more concentrated the noise (N > 0), the more accurate approximation we are able to obtain (a, 5 - 0).
4.1.2 Algorithm for Theorem 4.1
Algorithm 2: Noisy local search under small cardinality constraint
Input:a :a value oracle to f, budget Ω (2) no nz and (0,1/2)
Let Ph be aa harr 6 (1+1)1-17021 I 1)) approximation of (ph as in Lemma 4.4
2 St + NLS (fh, 1), A 3rinr
Local search phase
3 SM < Sr. + arg M, f(Sr. +
b f maximizatiion phase
return SM
We present Algorithm that contains two phases: local search phase (Line and a f-maximization phase (Line 3). We first run a non-oblivious local search procedure (Algorithm) [ under the (r 1)- cardinality constraint (Line 2). We set d (T+1)(r-1)x² by Corollary 3.4 when applying Algorithm
to obtain a (1 1 apprroxxinttio solution Sy for f--maximizaiion. At the f-maximization
é
phase (Line 3), we obtain SM by selecting additional element E N \ Sy that maximizes
f(S, e). This guarantees that f(SM) 2 (1 (SL( with high probability (Lemma 4.5). which (E) in Theorem 4.1
results in the approximation ratio 1
Given the smoothing surrogate function h(5) (Definition 4.2), natural idea is to simply apply local search (Algorithm 1) to optimize it under the r-cardinality constraint. However, this idea does not yield provable approximation of maxs:|s]<+ f(S), since it is not easy to control the contribution of the additional element Algorithm| first runs a local search procedure under the (r -aaddinally constraint, and then selects an additional element with a "large enough" margin at the f-maximization phase. This idea enables us to control the loss induced by the surrogate h within maxs: f(S).
N to hSS) and it is possible that h(S) >> f(S). To handle this difficulty,
2
4.1.3 Proof sketch of Theorem
We first analyze the query complexity and then prove the approximation performance.
Query complexity of Algorithm 2 In Line 3, we make (n r + 1) calls to the noisy oracle in total. By Corollary 3.4, the total number of queries to (Ph in Line 2 is at most (I + 1)(r 1)m
and I < lrlar, Combining with Lemma 4.4, the query complexity to f is upper bounded by O (T² log" r - mixe-mmaxxr,eee logn)))) This matches Theorem 4.1
Approximation ratio and success probability of Algorithm 2. Let On E arg max h(S)
represent the (r se- whose value of h is the largest. Following from Theorem 3.3 we
have h(S)) 2 (1 - e) I(OO,) with probability at least 1 +. We denote by O E
arg (aX) f(S) the optimal solution to f. By the submodularity of f, O, has a subset Öy with elements such that f(O,) 2 (1 41- 4) f(O,). Then we have
h(St) 2 1 1 E ( M(O,)) Z 1 -8) ʃ(Ō,)) 1
(1- +) (1---c) SOO (1)
where the first inequality follows from h(S)) 2 (1 (1-1 - --) h(O,) and the second from monotonic-
ity of f. Since is assumed to be Ω (1). h(St)) is (1- - - aaproxxmmaiinn of f(O,).
Recall that (()) is the expectation of ʃ(Sr + e) over a random element E N. Ineq. 1 already proves claim that uniformly randomly adding element E N to St, achieves an approximation ratio of Ogs) expectation for maximizing f. i.e., (Sr +e] 2 (1 Moreover, convert this claim to wuth-high-probabiie claim by the following lemma.
O(e)) f(0r)-
7

---

Lemma 4.5 (Approximation at the f-maximization phase). With probability 0 have (S5)) 2 (1 e)h(St).
logn we
This lemma indicates that had element E N \ St. with f(S + + < (1 (1-e)1(55)) e) is unlikely be chosen at the f-maximization phase. This because the local search procedure guarantees that the number of good elements with s(S2 + e) 2 (1 (){( is almost of the same order as the bad ones. Consequently, we can show that the selected element likely to be good due to the generalized exponential tail noise, using similar proof idea as that of [20] Lemma 3.4]. By Ineq.
and Lemma 4.5 we complete the proof.
4.2 Algorithmic results for cardinality constraints when (n²)
We present in this subsection algorithm (Algorithm B and its analysis (Theorem 4.6) that can be
applied to E Ω n when is sufficiently large. All missing proofs can be found in Section E
Theorem 4.6 (Algorithmic results for cardinality constraints when E Ω (n=))) Let e >> 0 and
assume n. E Ω (+) is sufficiently large. For any r E Ω (n²): there exists an algorithm that returns (1 - - ((e)))((p)))))))))) -aprroximation for Problem 2.6 under r-cardinality constraint, with probability 1 0 nz and query complexity at most Onn to
The above theorem addresses the remaining range of r in Theorem 4.1 and also achieves a tight approximation ratio of 1 1 (E) with Poly(n, 1/E) queries
4.2.1 Useful notations and useful facts for Theorem 4.6
Our algorithm and analysis in this subsection are based on another smoothing surrogate function h.
Definition 4.7 (Smoothing surrogate function IT.. Given subset H S N, for any set S C N \ H, define the smoothing surrogate function (S) as hu (S) En,gh f(S H2)/2 H
Intuitively, if H is sufficiently large, the surrogate function h is robust to noise as it is based large averaging set with size 2 Throughout the rest of this subsection, we consider the case that |H| E (2 n). Similar to Section 4.1.1 we give some basic properties of hg.
Lemma 4.8 (Properties of hz). For any H C N, the smoothing surrogate function h is monotone (f()).
and submodular, and for all S N H. (S) 2 (
Given a cardinality and set H C N, we define (r |H] ) cardinality constraint confined on N as (r) = (S C N H: : |S| = H|]. Similar to Section 4.1.1 we provide the following lemma indicating that the auxiliary function yhu be well approximated.
Lemma 4.9 (Approximation of P.n)) Let E > 0 and assume n E l (E-"). For a set H with | 2 3 Inn, there exists value oracle O to a (a far. 5 = S/. Inr(r) approximation Phu of Pha which answering O(A) queries f's oracle O re log² n log" r) times for each set A E In
The above lemma indicates that for sufficiently large n and [H] we can achieve an almost accurate approximation ςhū of 4hhn, which queries onnyy Ö(ne=1) times for each Ghv (A). By Corollay 3.4
we set 0 = 3 when applying Algorithm
4.2.2 Algorithm for Theorem 4.6
We present Algorithm 3 that mainly contains a local search phase (Line 3). The main difference from Algorithm is that Algorithm arbitrarily select a redundant set H (Line 1), and use this set to construct a smoothing surrogate function he for local search (Line 3). Then Algorithm 3 returns Sr U H directly (Line 4) without f m-maimizzation phase.

---

Algorithm 3: Noisy local search under large cardinality constraint
Input: :a value oracle to f. budget E Ω n and e E (0,
1 Arbitrarily select a subset H S .V with | = [3 In] = 2 Let fhr be a (a 4rlnr: 5= 3
x (r)) -aproxxmmatio of (hy as in Lemma 4.9
3 St + NLS (Phn, (r). 1rlor
Local search phase
4 return S₁ HH
4.2.3 Proof sketch of Theorem
Again, we first analyze the query complexity and then prove the approximation performance.
Query complexity of Algorithm Since E Ω (+), we have / E (n²)
) in Corollary 3.4 Hence
Line 4 calls the oracle of (hh at most ((r")) times by Corollary 3.4 and each call to Gh queries
f at most O (re- log n log" times by Lemma 4.9 Thus we query f at most O times.
Approximation ratio and success probability of Algorithm Corollary 3.4 we have h (Sr.) 2 ( 2) maxssIn(r) h (S) with probability 1 1 Furthermore, f(S, UH) 2 (S,) follows from the monotonicity of f. Then we can demonstrate the approximation performance of Algorithm by the following lemma.
Lemma 4.10. Let O = arg max f(S). We have maxseIN(r) hs( 2 (1- | f(0*).
Roughly speaking, there exists subset A S O of size [H] such that f(O"\A) 2 (1 H f(OO) by submodularity of f. The claim follows from max (S) 2 ((0)(A) 2 f(0') A).
Combining the fact that f(S, U H) 2 (1 - E) maxscIa (S) with Lemma 4.10 we
complete the proof of Theorem 4.6
5 Our algorithms and main theorems for general matroid constraints
In this section, we consider Problem 2.6 under matroid constraints. Similarly, for different ranges of matroid ranks, we prove there are (1 (1- - 2-app)/--ioo algorithms (Theorems 5.1 and 5.2). W.l.o.g., we assume that all single elements are feasible for the given matroid constraints.
Theorem 5.1 (Algorithmic results for matroid constraints with rank r E Ω ( log (o)) (1 (n))).
Let 8 > 0 is sufficiently small and assume n E Ω (exp 2((exp
(())) is sufficiently large. For any 9(= log(E-)) n n there exists an algorithm that returns a ((1 (11-3 /2 -(())-)
approximation for Problem 2.6 under a matroid constraint I(M) with rank r, with probability at
least 1- (E*) and query complexity at most (T2 (,2 log r n maxfr, log m)) to f.
The proof can be found in Section The main difference from Theorem 4. is that the approximation O(s) instead of 1 of the output, we may not be able to add an element to St as Line of Algorithm 2 To address this issue, we design a comparison procedure (Lines 4-8 of Algorithm 7 to evaluate the value of
ratio is (1 11-11 () /2
Oss). The reason is that to maintain the feasibility
f(SL) and fS Sz) and output the larger one, which results a loss on the approximation ratio. Moreover, the failure probability of the comparison procedure is upper bounded by O(Et).
Theorem 5.2 (Algorithmic results for matroid constraints with rank E E (n+)) (n²)). Let
and assume Z (++) is sufficiently large. For r E Ω. (nt)) (nt).. there exists an algorithm returning
((1 -xproxxmatioo for Problem 2.6 under a matroid constraint I(M) with rank
with probability 1 - O (.:2) and query complexity E to Specifically, for a strongly base-orderable matroid (Definition H.l the approximation ratio can be improved to 1 - - O(E).

---

The proof for general matroid constraints can be found in Section G The main difference from Theorem [.6 again the approximation ratio. For maintaing the feasibility, we divide an arbitrary base into two equal-size subsets, apply Algorithm g to both subsets, and output the larger one. Consequently, we achieve a ((1 - 2) /2 - approxxattooiio ratio. Specifically, for a strongly base-orderable matroid, we can use its good exchangable property to maintain the feasibility without sacrificing the approximation ratio; see Section for a complete proof.
Diseussions
For any cardinality r 2 2, Algorithms 2 and return a
(e)) -aprrxxmaaooi
for monotone submodular maximization problem under noise with query complexity Poly (n, 2)- When E 2 (t), the approximation ratio can be written (1 2) - (E)) (Theorem 1.1 However, r E O (t), then this ratio is not close to the optimal one. In this case, Singer and Hassidim
20 provide an algorithm that achieves (1 - aaapproxiimtionnn with query complexity ((x").
remains open whether there is an algorithm that returns (1 (1- - -O()) approximation with query complexity Poly (n. !) for r O (t). The main challenges of our approach to handle this range of that the introduction of surrogates (Definition 4.2) inevitably results in loss of 1 in approximation ratio. For the special case of r 1, one of the few known results is an algorithm by [2)] achieving a --approximation guarantee in expectation, which is information theoretically tight. To the best of our knowledge, there is no with-high -itbbbity-robbbbllityy result for this case.
-
Another limitation of this work is that we only consider independent noise. For non-i..d. noise, Hassidim and Singer [TT] indicate that no algorithm can achieve a constant approximation when the noise multipliers consider special cases of correlated distributions for which optimal guarantees can be obtained. One of them is model called d-correlated noise 11 noise distribution is d-correlated if for any two sets S and 7 such that [5 | |2 > d. the noise is applied independently to S and to T. The noise multipliers can be arbitrarily correlated when S and T are similar in the sense that [ | We notice that our algorithms can be naturally extended to d-correlated noise for d E O(1). In particular, to adapt Algorithm to deal with d-correlated noise, we need to arbitrarily split N into sets Ti.... T I and define the smoothing surrogate function as h(S) 1 J to replace the original surrogate.
arbitrarily correlated across sets. Considering this, it may be worthwhile to
d.
7 Conclusions
In this work, we study the problem of constrained monotone submodular maximization with noisy oracles. We design a unified local search framework that allows for inaccuracy in the objective function. Under this framework, we construct several smoothing surrogate functions average the noise out. For cardinality constraints, the local search framework results in algorithms that achieve a approxxaatonnoo with Poly (n, query complexity. Moreover, for general matroid constraints, the framework obtains an approximation ratio arbitrarily close to (1 2) /2, which is the first constant approximation result our knowledge.
(1
There are many directions which this work could be extended. For submodular maximization with noisy oracles under general matroid constraints, there is gap between the approximation ratio of 1/e) 22- -O() provided in this paper and impossibility results (5] The first open question to close this gap. In addition, it would be interesting to consider more complex constraints under noise including knapsack constraints [4]. is meaningful to investigate submodular maximization with
correlated noise. Moreover, it is also worthwhile to investigate the robustness of other submodular
optimization approaches, e.g., multi- linear extension 225]
Acknowledgements
We are grateful to Dr. Bei Xiaohui for his good counsel and valuable comments the manuscript.
10

---

References
[1] Niv Buchbinder and Moran Feldman. Submodular functions maximization problems. In Handbook Approximation Algorithms and Metaheuristics, page 771-806. Chapman and Hall/CRC, 2018.
[2] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6): 7740-1766, 2011.
[3] Christopher P Chambers and Federico Echenique. Revealed Preference Theory. Cambridge University Press, 2016.
[4] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43 (6):1831-1879, 2014.
[5] Uriel Feige. A threshold of In for approximating set cover. Journal of the ACM (JACM), 45 (4):634-522, 1998.
[6] Vitaly Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Learning Research, 10:163-182, 2009.
[7] Yuval Filmus and Justin Ward. Monotone submodular maximization over matroid via non- oblivious local search. SIAM Journal on Computing, 43(2):514 542,,, 2014.
[8] Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey, An analysis of approximations for maximizing submodular set functions Springer, 1978.
Polyhedral combinatorics, pages 73-87.
[9] Amir Globerson and Sam Roweis. Nightmare test time: robust learning by feature deletion. In Proceedings of the 23rd international conference on Machine learning, pages 353-360, 2006.
[10] Curtis Greene. A multiple exchange property for bases. Proceedings of the American Mathe- matical Society, 39(1):45 50,, 1973.
[11] Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. In Conference on Learning Theory, pages 1069-1 1122. PMLR, 2017.
[12] Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. Ad- vances in neural information processing systems, 29, 2016.
[13] Shinji Ito. Submodular function minimization with noisy evaluation oracle. Advances in Neural Information Processing Systems, 32, 2019.
[14] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[15] Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 134(6):516 526, 2008
[16] Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin. Simultancous placement and scheduling of sensors. In 2009 International Conference on Information Processing in Sensor Networks, pages 181-192. IEEE, 2009.
[17] Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research, 35(4).795-806. 2010.
[18] George I. Nemhauser, Laurence A Wolsey, and Marshall I. Fisher. An analysis of approximations for maximizing submodular set functions-4 Mathematical programming, 14(1):265-294, 1978.

---

[19] James G Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006.
[20] Yaron Singer and Avinatan Hassidim. Optimization for approximate submodularity, Advances Neural Information Processing Systems, 31, 2018.
[21] Adish Singla, Scbastian Tschiatschek, and Andreas Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization, In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[22] Maxim Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32(1))41-43, 2004.
[23] Marisa Thoma, Hong Cheng, Arthur Gretton, Jiawei Han, Hans-Peter Kriegel, Alex Smola, Le Song. Philip S Yu, Xifeng Yan, and Karsten Borgwardt. Near-optimal supervised feature selection among frequent subgraphs. Proceedings of the 2009 SIAM International Conference on Data Mining, pages 1076-1087. SIAM, 2009.
[24] Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018
[25] Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67-74, 2008
[26] Jan Vondrák, Chandra Chekuri, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third anmual ACM symposium on Theory of computing, pages 783-792, 2011.
[27] Dominic JA Welsh. Matroid theory. Courier Corporation, 2010.
[28] Robin J Wilson. An introduction to matroid theory. The American Mathematical Monthly, 80 (5):500-525, 1973.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All missing proofs can be found in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "nJPuGf06puG", "reviewer": "Reviewer_Ccvk", "summary": "This paper considers the problem of maximizing a monotone submodular function under matroid constraints when the value queries have independent random noise drawn from generalized exponential tail distributions. The first result is for uniform matroid constraints (aka cardinality constraints). Here, the new result improves on existing work in that the cardinality range over which it applies is larger than that of previous work while preserving polynomial dependence of query complexity on the approximation parameter $\\epsilon$. Prior work either applied only to larger cardinality values $\\Omega(\\log \\log n/\\epsilon^2)$ against $\\Omega(1/\\epsilon)$ or required exponential dependence of query complexity on $\\epsilon$. The second result is for general matroid constraints and obtains a constant approximation. Prior work had not considered general matroid constraints in maximizing submodular functions in the noisy setting.\n\nThe main technique is to use local search where each step swaps a single element. Prior work for noisy submodular maximization mostly used variants of the greedy algorithm. The local search algorithm is an adaptation of prior work by Filmus and Ward for exact queries, and the optimization function used for local search is also a robust version of the function used by FW.", "questions": "I do not have specific questions.", "limitations": "The paper includes a discussion of limitations at the end, but it seems largely perfunctory. As I mentioned above, it would be interesting to have a longer discussion about the noise model with its application scenarios and limitations, for instance. Also, are the cardinality bounds in this paper tight? If not, what are the challenges in removing this constraint altogether? Discussions of this sort would help make the paper a more engaging read.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Submodular function maximization is an important classical problem with applications spanning many areas.\n\n2. The paper gives the first results for submodular maximization under general matroid constraints in the noisy setting. Without noise, this is a standard setting in which submodular maximization is studied, so this is a good research direction in general. The approximation constant doesn't appear very impressive, but as the first paper considering this problem, it provides a good start.\n\n3. The adaptation of the local search technique to the noisy setting might be useful in general. Local search is used in many contexts and constructing a robust version in the presence of noise might have value beyond the results in this paper.\n\nWeaknesses:\n\n1. The techniques employed in this paper are not very novel. The adaptation of the FW algorithm is fairly straightforward, and as such, the paper does not contribute much in terms of new techniques.\n\n2. The noise model comes across as quite limited, and the paper does not include a discussion on it. It is true that a couple of previous papers also considered the same noise model, but I feel it would be useful to discuss the contexts in which this type of noise distribution is relevant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Z--tItT9Ekv", "reviewer": "Reviewer_ECg7", "summary": "This paper studies the problem of maximizing a submodular set function when function values are given by a noisy oracle. The authors propose 2 novel auxiliary functions which can be queried efficiently in order to improve the algorithms' candidate solutions via local search. The approach for cardinality constraints is then extended to work with matroid constraints.", "questions": "- Can the surrogates be used in the noise-free setting to improve the query complexity of local search? Does this improve on the guarantees in reference [5] or simply generalize them when the oracle has noise?\n- Is there a clear mapping from noise parameters $c_i$, $\\gamma_i$ to auxiliary function constants $\\alpha$, $\\delta$?\n\n[5] Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, 43(2):514–542, 2014.", "limitations": "This paper describes limitations as opportunities for future work, but does not address any potential negative social impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality/ Significance\n- Interesting theoretical contributions which lead to more practical ways to handle noisy function evaluation\n- Cites previous related work where appropriate\n\n## Quality\n- Smoothing surrogate auxiliary functions appear to be a novel, elegant approach that leads to exponential improvement in query complexity compared to previous work\n\n## Clarity\n- This paper is generally well organized. However I have 2 small suggestions:\n    - State the note after Theorem 3.3 as a separate corollary, showing intermediate steps in the Appendix. this is important because subsequent theorems appear to include an extra $\\log r$ term \n    - The second paragraph of related work on noise-free optimization with more complex constraints is not relevant to the paper. This could be moved to the Appendix or removed altogether\n- \"approximate ratio\" is used throughout the paper where \"approximation ratio\" is more standard\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QiPBkN5Ad5c", "reviewer": "Reviewer_6S7j", "summary": "The paper focuses on the problem of monotone submodular maximization subject to matroid constraints, when the function is only accessible through a noisy oracle. In particular, they provide an algorithm that with high probability outputs a solution with near-optimal (1 - 1/e - O(\\epsilon)-approximation guarantee. Notably, they deliver this result with a polynomial computational complexity in 1/\\epsilon, while the current works in the literature have an exponential complexity. ", "questions": "The claims that presented earlier in the paper in a less formal manner can be a bit misleading and undermine the main results of the paper. For example:\n(a) In the abstract, it is stated that the algorithm provides a 1 - 1/e - O(\\epsilon) guarantee without introducing \\epsilon. It is my understanding that this \\epsilon is an arbitrary value (given Theorems 5.1 and 5.2). If so, could the authors please clear this up in the abstract? As otherwise the provided bound can be quite far from the optimal. \n\n(b) In Theorem 1.1, the success probability of the algorithm is stated to be 1 - O(1). However, given Theorems 5.1 and 5.2, it seems that this is not correct as the probability either depends on n or \\epsilon and is not a constant. ", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n(a) The paper studies an interesting generic problem with broad applications in the data mining and machine learning areas. \n(b) The paper is very well-written and easy to follow. In particular, the authors make the transition into their main results smooth by providing sufficient intuitive explanations and motivations. Moreover, they justly credit the related the works and clearly distinguish their contributions from the existing methods or definitions. \n(c) They provide strong results and considerable improvements over the state-of-the-art. \n\nWeaknesses:\nOverall I find the results quite strong. I just have few minor comments on the presentation of the results, which I state under the Questions. \n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept