Subset Selection under Noise
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.
This paper considers the problem of maximizing a monotone set function subject to a cardinality constraint. The authors consider a novel combination of functions with both bounded submodularity ratio and additive noise. These setting have been considered separately before, but a joint analysis leads to a novel algorithm PONSS. This has improved theoretical guarantees and experimental performance when compared to previous noise-agnostic greedy algorithms. The paper flows well and is generally a pleasure to read.
Clarity
Small typo: "better on subclass problems" on line 26
The paper could benefit from a more thorough literature survey, including more recent results on the tightness of the submodularity ratio and applications to sparse regression [1] [2].
One comment on the beginning of Section 2: in this setting minimizing f subject to a cardinality constraint is not the same as maximizing -f subject to a cardinality constraint. Generally if -f is (weakly) submodular then f is (weakly) supermodular, and -f will not have the same submodularity ratio as f.
I would suggest including "i.i.d. noise distribution" when the assumptions for PONSS instead are first mentioned on page 2 ("fixed noise distribution"), instead of waiting until Section 5.
Impact
Influence maximization is an interesting application of noisy submodular optimization, since the objective function is often hard to compute exactly.
The authors should address that the PONSS guarantees hold with probability < 1/2 while the other guarantees are deterministic, and explain whether this affects the claim that the PONSS approximation ratio is "better".
O(Bnk^2) iterations can be prohibitive for many applications, and approximate/accelerated versions of the standard greedy algorithm can run in sublinear time.
Experiments
Most of my concerns are with the experiments section. In the sparse regression experiment, the authors report final performance on the entire dataset. They should explain why the did not optimize on a training set and then report final performance on a test set. Typically the training set is used to check how algorithms perform on the optimization, and the test set is used to check whether the solution generalizes without overfitting. Additionally, it appears that all of the R^2 values continue to increase at the largest value k. The authors should continue running for larger k or state that they were limited by large running times of the algorithms.
It would be more interesting to compare PONSS with other greedy algorithms (double greedy, random greedy, forward backward greedy, etc.), which are known to perform better than standard greedy on general matroid constraints
Questions
-What is the meaning of multiplicative domination in PONSS experiments if the noise estimate parameter \theta is set to 1? It would be interesting to quantify the drop in performance when 1 > \theta^' > \epsilon is used instead of \epsilon.
-For what range of memory B do the claims on line 170 hold?
-Could PONSS be parallellized or otherwise accelerated to reduce running time?
[1] A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications, ICML 2017.
[2] E. R. Elenberg, R. Khanna, A. G. Dimakis, and S. Negahban. Restricted strong convexity implies weak submodularity, https://arxiv.org/abs/1612.00804