Published on Wed Mar 30 2016

Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint

Nguyen Viet Cuong, Huan Xu

We study the worst-case adaptive optimization problem with budget constraint. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. We also report experiments comparing greedy algorithms on the active learning problem.

0
0
0
Abstract

We study the worst-case adaptive optimization problem with budget constraint that is useful for modeling various practical applications in artificial intelligence and machine learning. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. In both cases, we prove that two simple greedy algorithms are not near-optimal but the best between them is near-optimal if the utility function satisfies pointwise submodularity and pointwise cost-sensitive submodularity respectively. This implies a combined algorithm that is near-optimal with respect to the optimal algorithm that uses half of the budget. We discuss applications of our theoretical results and also report experiments comparing the greedy algorithms on the active learning problem.

Sun Mar 21 2010
Artificial Intelligence
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
The concept of adaptive submodularity is generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy.
0
0
0
Tue Jun 23 2020
Machine Learning
A Parameterized Family of Meta-Submodular Functions
Submodular function maximization has found a wealth of new applications in machine learning models. The related supermodular maximization models (submodular minimization) also offer an abundance of applications. But they appeared to be highly intractable even under simple cardinality constraints.
0
0
0
Fri Jun 08 2018
Machine Learning
An Optimal Algorithm for Online Unconstrained Submodular Maximization
We consider a basic problem at the interface of two fundamental fields: Submodular optimization and online learning. In the online unconstrained.submodular maximization (online USM) problem, there is a universe. of nonnegative (not necessarily.monotone) submodular functions. The goal is to design a
0
0
0
Mon Mar 06 2017
Artificial Intelligence
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
We investigate the performance of the standard Greedy algorithm for maximizing non-submodular nondecreasing set of functions. We prove theoretical guarantees supporting the empirical performance. We experimentally validate our findings for both synthetic and real-world applications.
0
0
0
Wed Apr 24 2019
Machine Learning
Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
The greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems. Its theoretical properties have been analyzed only for a limited class of problems. We narrow the gap between theory and practice by using adaptive submodularity ratio.
0
0
0
Sun Feb 28 2021
Artificial Intelligence
Adaptive Regularized Submodular Maximization
In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and an non-negative modular (cost)function under the adaptive setting. The input of our problem is a set of items, where each item has a particular state drawn from some known prior distribution.
0
0
0