Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Near-Polynomially Competitive Active Logistic Regression
CriticLean: Critic-Guided Reinforcement Learning for Mathematical Formalization
Active Learning for Manifold Gaussian Process Regression
The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learning
Info-Coevolution: An Efficient Framework for Data Model Coevolution
ALINE: Joint Amortization for Bayesian Inference and Active Data Acquisition
토론
이 논문과 연결된 포럼 글이 아직 없습니다.