Data-dependent Evaluations for Budgeted Submodular Maximization

• URL: http://arxiv.org/abs/2607.05759v1
• Date: Tue, 07 Jul 2026 02:34:10 GMT
• Title: Data-dependent Evaluations for Budgeted Submodular Maximization
• Abstract summary: Submodular is an important building block for developing algorithms in many areas such as machine learning and mining.<n>It is not easy to evaluate how a solution is to an optimal one for a given problem instance.<n>We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages.
• Score: 7.795374338122115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Related papers

• Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective [5.848643785361479]
  We introduce the exponential decay rate of the policy-selection error probability as a principled efficiency metric.<n>We formalize two complementary notions of optimality in terms of the optimal solution of the nested problem.<n>We prove that the resulting reinforcement learning algorithm is near-robustly optimal under our optimality criterion, up to a constant factor.
  arXiv  Detail & Related papers  (2026-05-27T16:08:56Z)
• Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
  Subset selection is a fundamental problem in optimization, which has a wide range of applications such as influence and sparse regression.<n>Previous algorithms, including the greedy algorithm and evolutionary evolutionary POSS, either struggle in noisy environments or consume excessive computational resources.<n>We propose a novel approach based on Pareto Optimization with Robust Evaluation for noisy subset selection (PORE), which maximizes a robust evaluation function and minimizes the subset size simultaneously.
  arXiv  Detail & Related papers  (2025-01-12T14:04:20Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  In episodic Block MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function based on data generated under a fixed behavior policy. We then study the problem of learning near-optimal policies in the reward-free framework.
  arXiv  Detail & Related papers  (2022-08-17T18:49:53Z)
• Data-Driven Minimax Optimization with Expectation Constraints [9.373649142701803]
  We propose a class of efficient primal-dual algorithms to tackle the minimax expectation-constrained problem. We show that our algorithms converge at the optimal rate of $mathcalO(frac1sqrtN)$.
  arXiv  Detail & Related papers  (2022-02-16T05:23:27Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
  arXiv  Detail & Related papers  (2021-11-01T21:06:35Z)
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization [12.742028139557384]
  We propose a random reshuffling-based gradient free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems.
  arXiv  Detail & Related papers  (2021-06-16T18:49:59Z)
• Instance Specific Approximations for Submodular Maximization [45.91235224228292]
  We look for methods to benchmark the performance of algorithms against optimal solutions on real-world instances. A major question is how to measure the performance of an algorithm in comparison to an optimal solution on instances we encounter in practice. Our main contribution is not a new algorithm for submodular minimization but an analytical method that measures how close an algorithm for submodular instance is to optimal.
  arXiv  Detail & Related papers  (2021-02-23T19:39:32Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.