We consider the problem of maximizing a monotone submodular function under noise. There has been a great deal of work on optimization of submodular functions under various constraints, resulting in algorithms that provide desirable approximation guarantees. In many applications, however, we do not have access to the submodular function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under a cardinality constraint when given access to a noisy oracle of the function. We show that: - For a cardinality constraint @math , there is an approximation algorithm whose approximation ratio is arbitrarily close to @math ; - For @math there is an algorithm whose approximation ratio is arbitrarily close to @math . No randomized algorithm can obtain an approximation ratio better than @math ; -If the noise is adversarial, no non-trivial approximation guarantee can be obtained.
Combinatorial optimization with noisy inputs can be largely studied through consistent (independent noisy answers when querying the oracle twice) and inconsistent oracles. For inconsistent oracles, it usually suffices to repeat every query @math times, and eliminate the noise. To the best of our knowledge, submodular optimization has been studied under noise only in instances where the oracle is inconsistent or equivalently small enough so that it does not affect the optimization @cite_43 @cite_3 . One line of work studies methods for reducing the number of samples required for optimization (see e.g. @cite_1 @cite_5 ), primarily for sorting and finding elements. On the other hand, if two identical queries to the oracle always yield the same result, the noise can not be averaged out so easily, and one needs to settle for approximate solutions, which has been studied in the context of tournaments and rankings @cite_54 @cite_71 @cite_56 .
@cite_54 @cite_1 @cite_3 @cite_56 @cite_43 @cite_71 @cite_5
2155192981 2963922672 1486249389 2089729462
We study the intrinsic limitations of sequential convex optimization through the lens of feedback information theory. In the oracle model of optimization, an algorithm queries an oracle for noisy information about the unknown objective function and the goal is to (approximately) minimize every function in a given class using as few queries as possible. We show that, in order for a function to be optimized, the algorithm must be able to accumulate enough information about the objective. This, in turn, puts limits on the speed of optimization under specific assumptions on the oracle and the type of feedback. Our techniques are akin to the ones used in statistical literature to obtain minimax lower bounds on the risks of estimation procedures; the notable difference is that, unlike in the case of i.i.d. data, a sequential optimization algorithm can gather observations in a controlled manner, so that the amount of information at each step is allowed to change in time. In particular, we show that optimization algorithms often obey the law of diminishing returns: the signal-to-noise ratio drops as the optimization algorithm approaches the optimum. To underscore the generality of the tools, we use our approach to derive fundamental lower bounds for a certain active learning problem. Overall, the present work connects the intuitive notions of “information” in optimization, experimental design, estimation, and active learning to the quantitative notion of Shannon information. We consider the problem of maximizing a monotone submodular function under noise, which to the best of our knowledge has not been studied in the past. There has been a great deal of work on optimization of submodular functions under various constraints, with many algorithms that provide desirable approximation guarantees. However, in many applications we do not have access to the submodular function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under a cardinality constraint when given access to a noisy oracle of the function. We show that: • For a cardinality constraint k ≥ 2, there is an approximation algorithm whose approxima- tion ratio is arbitrarily close to 1− 1 e; • For k = 1 there is an approximation algorithm whose approximation ratio is arbitrarily close to 1 2 in expectation. No randomized algorithm can obtain an approximation ratio better than 1 2 + o(1) in expectation; • If the noise is adversarial, no non-trivial approximation guarantee can be obtained. Given @math noisy samples with @math dimensions, where @math , we show that the multi-step thresholding procedure based on the Lasso -- we call it the Thresholded Lasso , can accurately estimate a sparse vector @math in a linear model @math , where @math is a design matrix normalized to have column @math norm @math , and @math . We show that under the restricted eigenvalue (RE) condition (Bickel-Ritov-Tsybakov 09), it is possible to achieve the @math loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle while selecting a sufficiently sparse model -- hence achieving sparse oracle inequalities ; the oracle would supply perfect information about which coordinates are non-zero and which are above the noise level. In some sense, the Thresholded Lasso recovers the choices that would have been made by the @math penalized least squares estimators, in that it selects a sufficiently sparse model without sacrificing the accuracy in estimating @math and in predicting @math . We also show for the Gauss-Dantzig selector (Cand e s-Tao 07), if @math obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, one will achieve the sparse oracle inequalities as above, while allowing at most @math irrelevant variables in the model in the worst case, where @math is the smallest integer such that for @math , @math . Our simulation results on the Thresholded Lasso match our theoretical analysis excellently. A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". Our main result is that for any fixed instance that exhibits a certain "symmetry gap" in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g. the optimality of (1-1 e)-approximation for monotone submodular maximization under a cardinality constraint, and the impossibility of (1 2+epsilon)-approximation for unconstrained (non-monotone) submodular maximization. It follows from our result that (1 2+epsilon)-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0.309-approximation for this problem, improving the previously known factor of 1 4-o(1).As another application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. A (1 6-o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k≫=2, there is a class of matroids of fractional base packing number nu = k (k-1), such that any algorithm achieving a better than (1-1 nu)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1 2 (1-1 nu-o(1))-approximation algorithm for the same problem. Our hardness results hold in fact for very special symmetric instances. For such symmetric instances, we show that the approximation factors of 1 2 (for submodular maximization subject to a matroid constraint) and 1-1 nu (for a matroid base constraint) can be achieved algorithmically and hence are optimal.