Timezone: »

 
Poster
Subset Selection under Noise
Chao Qian · Jing-Cheng Shi · Yang Yu · Ke Tang · Zhi-Hua Zhou

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #159
in Posters Mon »
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.
Keywords: Combinatorial Optimization · Submodular Optimization · Computational Complexity
[ Code]  [ Paper] 

Author Information

Chao Qian (University of Science and Technology of China)
Jing-Cheng Shi (Nanjing University)
Yang Yu (Nanjing University)
Ke Tang (University of Science and Technology of China)
Zhi-Hua Zhou (Nanjing University)

More from the Same Authors