Date : 05 July 2024
Abstract: Submodularity provides a natural context to model a large class of discrete optimization problems including but not limited to influence maximization, mechanism design, resource allocation and several machine learning problems. As a set functional property, submodularity models the notion of diminishing returns in the discrete space. Theoretically, it has intrigued scientists due to strong structural similarity with both convex and concave functions in the continuous space, which has been exploited to derive worst-case performance guarantees for deterministic submodular optimization problems. Distributionally robust submodular optimization, however, seeks to evaluate or approximate the worst-case expected value of a submodular function (subjected to random input) over a set of joint distributions consistent with available information on the marginals, moments or statistical distance from a reference distribution. While computing the worst-case joint distribution or the corresponding expected value is known to be NP-hard, traditional approaches approximate the optimal expected value by assuming the random inputs to be independent. This notion is formalized by the concept of correlation gap which quantifies how much we “lose” in the expectation of the function by ignoring the correlation structure of the random set and assuming independence instead. For monotone submodular set functions, it was shown that the correlation gap is upper bounded by e/(e-1) in Agrawal et.al. (2012). In reality, however, more complex notions of randomness are often encountered, such as when weak correlations coexist with higher-order dependencies. Inspired by the need to incorporate more realistic notions of randomness and driven by the curiosity to understand the interplay between functional properties and randomness, we study the behaviour of monotone submodular set functions with pairwise independent random input. We show that in this scenario, the e/(e-1) bound on the correlation gap can be improved to 4/3 (and that it is tight) in several cases depending on the size of the random inputs, conditions on the marginal probabilities and the type of submodular function considered. Our results illustrate a fundamental difference in the behavior of submodular functions under weaker notions of independence with potential ramifications in improving existing algorithmic approximations. Interestingly, when the pairwise independence condition is relaxed to admit a positively correlated structure, the worst-case expected value can be computed from a compact linear program formulation derived by using results from submodular minimization theory.
(This is joint work with Karthik Natarajan, Singapore University of Technology and Design)
