Efficient Submodular Optimization under Noise Local Search is Robust Lingxiao HuangYuyi WangChunxue YangHuanjian Zhou

2025-05-03 0 0 964.12KB 35 页 10玖币
侵权投诉
Efficient Submodular Optimization under Noise: Local Search
is Robust
Lingxiao Huang∗Yuyi Wang †Chunxue Yang ‡Huanjian Zhou§
October 24, 2022
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 [
11
]. For a cardinality constraint, we propose an algorithm achieving a
near-optimal
1−
1
e
−O(ε)
-approximation guarantee (for arbitrary
ε >
0) with only a 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 a novel local search framework that
can handle the effect of noise and to construct certain smoothing surrogate functions for noise
reduction.
∗huanglingxiao1990@126.com. Huawei TCS Lab →Nanjing University.
†yuyiwang920@gmail.com. Swiss Federal Institute of Technology.
‡chunxue001@e.ntu.edu.sg. Nanyang Technological University.
§zhou@ms.k.u-tokyo.ac.jp. The University of Tokyo.
1
arXiv:2210.11992v1 [cs.DS] 21 Oct 2022
Contents
1 Introduction 3
1.1 Ourcontributions........................................ 3
1.2 Relatedwork .......................................... 4
2 The model 5
3 Local search with approximate evaluation oracles to auxiliary functions 6
4 Our algorithms and main theorems for cardinality constraints 10
4.1 Algorithmic results for cardinality constraints when r∈Ω1
ε∩On1
3......... 10
4.1.1 Useful notations and useful facts for Theorem 4.1 . . . . . . . . . . . . . . . . . . 10
4.1.2 Algorithm for Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.3 ProofofTheorem4.1 ................................. 15
4.2 Algorithmic results for cardinality constraints when r∈Ωn1
3.............. 18
4.2.1 Useful notations and useful facts for Theorem 4.16 . . . . . . . . . . . . . . . . . 18
4.2.2 Algorithm for Theorem 4.16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.3 ProofofTheorem4.16................................. 21
5 Our algorithms and main theorems for general matroid constraints 23
5.1 Algorithmic results for matroid constraints with rank r∈Ω1
ε∩On1
3........ 23
5.1.1 Useful notations and useful facts for Theorem 5.1 . . . . . . . . . . . . . . . . . . 23
5.1.2 Algorithm for Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.1.3 ProofofTheorem5.1 ................................. 24
5.2 Algorithmic results for matroid constraints with rank r∈Ωn1
3............. 26
5.2.1 Useful facts for Theorem 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2.2 Algorithm for Theorem 5.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2.3 ProofofTheorem5.7 ................................. 27
6 Discussions 28
7 Conclusions 29
A The Invalid Result for General Matroid Constraints in [20] 31
B More Related Work 32
C Approximation algorithm for strongly base-orderable matroid constraints 32
C.1 AlgorithmforTheoremC.2 .................................. 33
C.2 ProofofTheoremC.2 ..................................... 33
2
1 Introduction
Consider the following problems in machine learning and operations research: (1) selecting a set
of locations to open up facilities with the goal of maximizing their overall user coverage [
15
]; (2)
reducing the number of features in a machine learning model while retaining as much information as
possible [
23
]; and (3) identifying a small set of seed nodes that can achieve the largest overall influence
in a social network [
14
]. Solving these problems all involves maximizing a monotone submodular set
function
f
: 2
N7→ R
subject to certain constraints. Intuitively, submodularity captures the property
of diminishing returns. For example, a 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 a 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 a cardinality constraint by a factor of 1
−
1
/e
,
and this approximation ratio is tight [
18
]. Moreover, a non-oblivious local search algorithm, which
iteratively alters one element to improve an auxiliary objective function, is guaranteed to achieve an
approximation ratio of 1−1/e for general matroid constraints [7].
In the literature, the submodular optimization problem usually assumes a value oracle to the
objective function
f
, which means one is allowed to query the exact value of
f
(
S
)for any
S⊆N
.
However, in many applications, due to the uncertain nature of the objective or the errors involved in
the evaluation, one can only access the function value in a distorted or noisy form. For example, [
9
]
pointed out that selecting features to construct a robust learning model is particularly important in
domains with 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, [
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
˜
f
(
S
) =
ξSf
(
S
)for each set
S⊆N
, where the noise multiplier
ξS
is independently drawn from a certain distribution, the goal is to find a set
S
maximizing
f
(
S
)under
certain constraints. Some applications of this problem are provided in [
20
] such as revealed preference
theory [
3
] and active learning [
6
]. [
11
] showed that under a sufficiently large cardinality constraint,
a variant of the greedy algorithm achieves a near-optimal approximation ratio of 1
−1
e−O
(
ε
)for
arbitrary
ε >
0. The problem becomes more challenging when the cardinality constraint is relatively
small since there is less room for mistakes. In a subsequent work, [
20
] developed another greedy-based
algorithm for small cardinality constraints and showed a 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 [
20
], the query complexity to the noisy value oracle is exponential in
ε−1
,
which is costly when a near-optimal solution is needed, i.e., when the parameter
ε
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 ε−1?
•
All previous works in submodular maximization under noise consider only the cardinality con-
straint, and no approximation guarantee is known under other constraints.
1
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 [
11
,
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 a monotone submodular function
under a cardinality constraint,
1−1
e−O(ε)
-approximations can be obtained with high probability
by querying the noisy oracle only Poly n, 1
εtimes.
1
Note that [
20
] also provide an algorithm to deal with general matroid constraints. However, we will argue in Section A
that their algorithm fails to obtain the approximation guarantee they claim.
3
Theorem 1.1
(
Informal, see Theorems 4.1 and 4.16
)
.
Let
ε >
0and assume
n
is sufficiently
large. For any
r∈
Ω
1
ε
, there exists an algorithm that returns a
1−1
e−O(ε)
-approximation for the
monotone submodular maximization problem under a
r
-cardinality constraint, with probability 1
−o
(1)
and query complexity Poly n, 1
εto ˜
f.
For a cardinality constraint, this paper and prior works [
11
,
20
] all achieve near-optimal approximations.
However, our result is applicable for a larger range Ω
1
ε
of cardinalities than Ω
log log n·ε−2
in [
11
].
Moreover, we only require
Poly n, 1
ε
queries to the noisy value oracle, which improves the query
complexity Ω(
n1
ε
)of [
20
]. Our main idea to address this problem is to employ a 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, 1
εfor small cardinality constraints.
We present a unified framework (Algorithm 1) 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 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.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 on smoothing surrogate functions. A surrogate function
h
needs to
meet two properties: (i)
h
should depend on an averaging set of size
poly
(
n
), such that
h
(
S
)and
its noisy analogue
˜
h
(
S
)are close for all sets
S
considered by local search; (ii)
h
needs to be close
to the original function
f
, such that optimizing
h
can yield a near-optimal solution to optimizing
f
.
However, a large averaging set is more likely to induce a 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
r∈
Ω
1
ε∩On1/3
, 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 a rather large averaging set with size nearly
n
, but too concentrated for
a large cardinality close to
n
. Thus, we consider another smoothing surrogate function
hH
for size
r∈
Ω
n1/3
, defined as the average value combined with all subsets of a certain small-size set
H
(Definition 4.17). The auxiliary functions constructed on both smoothing surrogates are shown to have
almost accurate approximations (Lemma 4.4 and 4.19). Consequently, we can apply our unified local
search framework (Algorithm 1) in both cases (Algorithm 3 and 5), and guarantee to achieve nearly
tight approximate solutions (Theorem 4.1 and 4.16). The other contribution of this paper is a 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.7
)
.
Let
ε >
0and assume
n
is sufficiently large.
For any
r∈
Ω
ε−1log(ε−1)
, there exists an algorithm that returns a
1
21−1
e−O(ε)
-approximation
for the monotone submodular maximization problem under a matroid constraint with rank
r
, with
probability 1−o(1) and query complexity at most Poly n, 1
ε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 a set. To address this difficulty, we develop a technique for comparing
the values of independent sets in 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
21−1
e.
1.2 Related work
Research has been conducted on 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 a barrier to optimization, since concentration assumptions can
eliminate the noise after a sufficient number of queries [
21
,
13
]. When identical queries always obtain the
4
same answer, the problem becomes more challenging. Aside from the i.i.d noise adopted in [
11
,
20
] and
this paper, [
12
] study submodular optimization under noise adversarially generated from [1
−ε/r,
1+
ε/r
],
where the greedy algorithm achieves a ratio of 1
−
1
/e −O
(
ε
). 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.2) or a matroid constraint (Definition 2.3),
given access to a noisy value oracle (Definition 2.4). Let
N
be the ground set with size
|N|
=
n
, and
we use the shorthands
S
+
x
=
S∪ {x}
and
S−x
=
S\{x}
throughout this paper. We first review the
definition of monotone submodular functions.
Definition 2.1
(
Monontone submodular functions).
A function
f
: 2
N→R≥0
is monotone
submodular if 1) (monotonicity) f(A)≤f(B)for any A⊆B⊆N; 2) (submodularity) for any subset
A, B ⊆Nand x∈N:f(A+x)−f(A)≥f(B+x)−f(B).
There are various examples of monotone submodular functions in optimization, such as budget additive
functions, coverage functions, cut functions and rank functions [
1
]. 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⊆N
. Let
I
denote a collection of feasible subsets
S⊆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
(
∅
) = 0. 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≥
1, a cardinality
constraint is of the form I(r) = {S⊆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, I
(
M
)) satisfying that 1)
∅∈ I
(
M
); 2) If
I∈ I
(
M
)and
I0⊆I
,
then
I0∈ I
(
M
); 3) If
I1, I2⊆ I
(
M
)and
|I1|<|I2|
, then there must exist an element
e∈I2\I1
such that
I1∪ {e} ∈ I
(
M
). Each
I∈ I
(
M
)is called an independent set. The maximum size of an
independent set is called the rank of M. We call the collection I(M)a matroid constraint.
Assume we are given a membership oracle of
I
(
M
)that for any set
S⊆N
answers whether
S∈ I
(
M
).
As a 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 [
19
] for more
discussions. Specifically, a uniform matroid constraint is equivalent to a cardinality constraint, implying
that cardinality constraints are a special case of matroid constraints.
Noisy value oracle.
It is well known that given an exact value oracle to
f
, for any
ε >
0, there
exists a randomized (1
−
1
/e −ε
)-approximate algorithm for the submodular optimization problem
under a matroid constraint, i.e.,
maxS⊆I f
(
S
)[
2
,
7
]. However, as discussed earlier, the value oracle
of
f
may be imperfect, and we may only have a 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
N→R≥0
a (multiplicative)
noisy value oracle of
f
, if there exists some distribution
D
s.t. for any
S⊆N
,
˜
f
(
S
) =
ξSf
(
S
)where
ξS
is i.i.d. drawn from D.
Throughout this paper, we consider a general class of noise distributions, called generalized exponential
tail distributions, defined in [20].
Definition 2.5
(
Generalized exponential tail distributions [20]).
A noise distribution
D
has a
generalized exponential tail if there exists some
x0
such that for every
x>x0
the probability density
function
ρ
(
x
) =
e−g(x)
, where
g
(
x
) =
Picixγi
for some (not necessarily integers)
γ0≥γ1≥. . . , s.t.γ0≥
1and
c0>
0. If
D
has bounded support we only require that either it has an atom at its supremum or
that ρis continuous and non-zero at the supremum.
5
摘要：

EcientSubmodularOptimizationunderNoise:LocalSearchisRobustLingxiaoHuang*YuyiWang„ChunxueYang…HuanjianZhouŸOctober24,2022AbstractTheproblemofmonotonesubmodularmaximizationhasbeenstudiedextensivelyduetoitswiderangeofapplications.However,therearecaseswhereonecanonlyaccesstheobjectivefunctioninadistort...

展开>> 收起<<
Efficient Submodular Optimization under Noise Local Search is Robust Lingxiao HuangYuyi WangChunxue YangHuanjian Zhou.pdf

共35页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：35 页 大小：964.12KB 格式：PDF 时间：2025-05-03

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 35
评分 收藏
分享
立即下载
客服
关注