English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose and analyze batch greedy heuristics for cardinality constrainedmaximization of non-submodular non-decreasing set functions. We consider thestandard greedy paradigm, along with its distributed greedy and stochasticgreedy variants. Our theoretical guarantees are characterized by thecombination of submodularity and supermodularity ratios. We argue how theseparameters define tight modular bounds based on incremental gains, and providea novel reinterpretation of the classical greedy algorithm using theminorize-maximize (MM) principle. Based on that analogy, we propose a new classof methods exploiting any plausible modular bound. In the context of optimalexperimental design for linear Bayesian inverse problems, we bound thesubmodularity and supermodularity ratios when the underlying objective is basedon mutual information. We also develop novel modular bounds for the mutualinformation in this setting, and describe certain connections to polyhedralcombinatorics. We discuss how algorithms using these modular bounds relate toestablished statistical notions such as leverage scores and to more recentefforts such as volume sampling. We demonstrate our theoretical findings onsynthetic problems and on a real-world climate monitoring example.

Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design