Subset selection under noise

Qian，Chao1; Shi，Jing Cheng2; Yu，Yang2; Tang，Ke1,3; Zhou，Zhi Hua2

2017

1049-5258

Advances in Neural Information Processing Systems

2017-December

3561-3571

Long Beach, CA, United states

Neural information processing systems foundation

The problem of selecting the best k-element subset from a universe is involved in many applications. While previous studies assumed a noise-free environment or a noisy monotone submodular objective function, this paper considers a more realistic and general situation where the evaluation of a subset is a noisy monotone function (not necessarily submodular), with both multiplicative and additive noises. To understand the impact of the noise, we firstly show the approximation ratio of the greedy algorithm and POSS, two powerful algorithms for noise-free subset selection, in the noisy environments. We then propose to incorporate a noise-aware strategy into POSS, resulting in the new PONSS algorithm. We prove that PONSS can achieve a better approximation ratio under some assumption such as i.i.d. noise distribution. The empirical results on influence maximization and sparse regression problems show the superior performance of PONSS.

非南科大

英语

EI

[BK20170013] ; [NA150123] ; National Natural Science Foundation of China[61603367] ; [2016QNRC001]

20182105216086

Additive noise ; Approximation algorithms

Electric Circuits:703 ; Mathematics:921 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4

2-s2.0-85047002202

Scopus

1.Anhui Province Key Lab. of Big Data Analysis and Application,USTC,China
2.National Key Lab. for Novel Software Technology,Nanjing University,China
3.Shenzhen Key Lab of Computational Intelligence,SUSTech,China

Qian，Chao,Shi，Jing Cheng,Yu，Yang,et al. Subset selection under noise[C]:Neural information processing systems foundation,2017:3561-3571.