Abstract:  We propose and analyze batch greedy heuristics for cardinality constrained maximization of non-submodular non-decreasing set functions. Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios. We argue how these parameters define tight modular bounds based on incremental gains, and provide a novel reinterpretation of the classical greedy algorithm using the minorize–maximize (MM) principle. Based on that analogy, we propose a new class of methods exploiting any plausible modular bound. In the context of optimal experimental design for linear Bayesian inverse problems, we bound the submodularity and supermodularity ratios when the underlying objective is based on mutual information. We also provide a novel modular bound for the mutual information in this setting, and describe certain connections to polyhedral combinatorics. We demonstrate our theoretical findings on synthetic problems and on a real-world climate monitoring example.

Bio:  Jayanth Jagalur-Mohan is a Research Scientist at MIT affiliated to the Department of Aeronautics and Astronautics. His work and interests are broadly in Experimental Design, Reduced-ordered models, Uncertainty quantification and Bayesian Inference. He obtained an M.S. and Ph.D. from Rensselaer Polytechnic Institute, where his doctoral research focussed on variational multiscale methods, and fast-iterative solvers in distributed computing environments.