Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization
The objective of a two-stage submodular maximization problem is to reduce the ground set using provided training functions that are submodular, with the aim of ensuring that optimizing new objective functions over the reduced ground set yields results comparable to those obtained over the original ground set. This problem has applications in various domains including data summarization. Existing studies often assume the monotonicity of the objective function, whereas our work pioneers the extension of this research to accommodate non-monotone submodular functions. We have introduced the first constant-factor approximation algorithms for this more general case.
Code (0)
등록된 구현이 없습니다.
Tasks
Data SummarizationSimilar Papers 제목 키워드 기반
Spingarn's Method and Progressive Decoupling Beyond Elicitable Monotonicity
Spingarn's method of partial inverses and the progressive decoupling algorithm address inclusion problems involving the sum of an operator and the normal cone of a linear subspace, known as linkage problems. Despite thei…
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight $63\%$ approximation. But many p…
Counterfactual identifiability beyond global monotonicity: non-monotone triangular structural causal models
Structural causal models provide a unified semantics for interventions and counterfactuals, but most identifiability results rely on restrictive assumptions like global monotonicity, which are often violated in embodied …
Testing $k$-Monotonicity
A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natura…
Learning TheoryLabel Noise Filtering Techniques to Improve Monotonic Classification
The monotonic ordinal classification has increased the interest of researchers and practitioners within machine learning community in the last years. In real applications, the problems with monotonicity constraints are v…
ClassificationGeneral ClassificationOrdinal Classification