Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design
- URL: http://arxiv.org/abs/2006.04554v3
- Date: Tue, 10 Aug 2021 20:17:42 GMT
- Title: Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design
- Authors: Jayanth Jagalur-Mohan, Youssef Marzouk
- Abstract summary: We analyze greedys for cardinality constrained of non-submodular non-decreasing set functions.
Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and analyze batch greedy heuristics for cardinality constrained
maximization of non-submodular non-decreasing set functions. We consider the
standard greedy paradigm, along with its distributed greedy and stochastic
greedy variants. 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 develop novel modular bounds for the mutual
information in this setting, and describe certain connections to polyhedral
combinatorics. We discuss how algorithms using these modular bounds relate to
established statistical notions such as leverage scores and to more recent
efforts such as volume sampling. We demonstrate our theoretical findings on
synthetic problems and on a real-world climate monitoring example.
Related papers
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
We present a novel gradient-free algorithm to solve convex optimization problems.
Such problems are encountered in medicine, physics, and machine learning.
We provide convergence guarantees for the proposed algorithm under both types of noise.
arXiv Detail & Related papers (2024-11-21T10:26:17Z) - Optimal Multi-Distribution Learning [88.3008613028333]
Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.
We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
arXiv Detail & Related papers (2023-12-08T16:06:29Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
We investigate the problem of unconstrained multi-armed bandits with full-bandit feedback and rewards for submodularity.
We show that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.
arXiv Detail & Related papers (2023-02-02T18:52:14Z) - Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback [23.665149409064814]
We extend purely submodular prior work to more general non-submodular objectives.
This allows representing not only competitive (submodular) but also complementary (supermodular) relationships between objects.
arXiv Detail & Related papers (2022-07-07T05:10:15Z) - Supermodular $\mf$-divergences and bounds on lossy compression and
generalization error with mutual $\mf$-information [17.441807469515254]
We introduce super-modular $mf$-divergences and provide three applications for them.
We provide a connection between the generalization error of algorithms with bounded input/output mutual $mf$-information and a generalized rate-distortion problem.
Our bound is based on a new lower bound on the rate-distortion function that strictly improves over previously best-known bounds.
arXiv Detail & Related papers (2022-06-21T09:17:06Z) - Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
A submodular function in the MapReduce (MR) model has received much attention.
We show that several sublinearly adaptive algorithms satisfy the consistency property required to work in the MR setting.
arXiv Detail & Related papers (2022-06-20T04:17:32Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
We study the fundamental problem of selecting optimal features for model construction.
This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants.
We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions.
The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
arXiv Detail & Related papers (2022-02-28T12:26:47Z) - Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian
Modeling [68.69431580852535]
We introduce a novel GP regression to incorporate the subgroup feedback.
Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches.
We execute our algorithm on two disparate social problems.
arXiv Detail & Related papers (2021-07-07T03:57:22Z) - Continuous Submodular Function Maximization [91.17492610120324]
Continuous submodularity is a class of functions with a wide spectrum of applications.
We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
arXiv Detail & Related papers (2020-06-24T04:37:31Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
We propose a novel framework that converts streaming for monotone submodular into streaming for non-monotone submodular.
We also propose the first algorithm for monotone submodular streaming subject to $k$ible $k$-set system constraints.
arXiv Detail & Related papers (2020-02-09T12:32:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.