Linear-Time Algorithms for Adaptive Submodular Maximization

• URL: http://arxiv.org/abs/2007.04214v1
• Date: Wed, 8 Jul 2020 15:54:28 GMT
• Title: Linear-Time Algorithms for Adaptive Submodular Maximization
• Authors: Shaojie Tang
• Abstract summary: First, we develop a well-studied adaptive submodular problem subject to a cardinality constraint. Second, we introduce the concept of fully adaptive submodularity. Our algorithm achieves a $frac1-1/e-epsilon4-2/e-2epsilon$ approximation ratio using only $O(nlogfrac1epsilon)$ number of function evaluations.
• Score: 17.19443570570189
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we develop fast algorithms for two stochastic submodular maximization problems. We start with the well-studied adaptive submodular maximization problem subject to a cardinality constraint. We develop the first linear-time algorithm which achieves a $(1-1/e-\epsilon)$ approximation ratio. Notably, the time complexity of our algorithm is $O(n\log\frac{1}{\epsilon})$ (number of function evaluations) which is independent of the cardinality constraint, where $n$ is the size of the ground set. Then we introduce the concept of fully adaptive submodularity, and develop a linear-time algorithm for maximizing a fully adaptive submoudular function subject to a partition matroid constraint. We show that our algorithm achieves a $\frac{1-1/e-\epsilon}{4-2/e-2\epsilon}$ approximation ratio using only $O(n\log\frac{1}{\epsilon})$ number of function evaluations.

Related papers

• Fast algorithms for k-submodular maximization subject to a matroid constraint [10.270420338235237]
  We apply a Threshold-Decreasing Algorithm to maximize $k$-submodular functions under a matroid constraint. We give a $(frac12 - epsilon)$-approximation algorithm for $k$-submodular function.
  arXiv  Detail & Related papers  (2023-07-26T07:08:03Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  This work introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular over a ground set of size $n$ subject to a knapsack constraint. $mathsfDLA$ is a deterministic algorithm that provides an approximation factor of $6+epsilon$ while $mathsfRLA$ is a randomized algorithm with an approximation factor of $4+epsilon$.
  arXiv  Detail & Related papers  (2023-05-17T15:27:33Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  We present and parallelizable for a submodular function, not necessarily a monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal complexity query to $0.193 - varepsilon$.
  arXiv  Detail & Related papers  (2020-09-03T22:43:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time [17.19443570570189]
  We study the non-monotone adaptive submodular problem subject to a cardinality constraint. We show that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio under adaptive submodularity. We propose a faster algorithm that achieves a $1-1/e-epsilon$ approximation ratio in expectation with $O(nepsilon-2log epsilon-1)$ value oracle queries.
  arXiv  Detail & Related papers  (2020-08-11T21:06:52Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  We provide the first deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for submodularimation under a cardinality (size) constraint. We show that when the cardinality allowed for a solution is constant, no algorithm making a sub-linear number of function evaluations can guarantee any constant ratio. We extensively evaluate our algorithms on multiple real-life machine learning applications, including movie recommendation, location summarization, twitter text summarization and video summarization.
  arXiv  Detail & Related papers  (2020-06-16T17:06:45Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.