Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

• URL: http://arxiv.org/abs/2403.10063v2
• Date: Fri, 26 Apr 2024 21:05:00 GMT
• Title: Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
• Authors: Mohammad Pedramfar, Yididiya Y. Nadew, Christopher J. Quinn, Vaneet Aggarwal,
• Abstract summary: This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial DR-submodular optimization. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $alpha$-regret bounds or have better $alpha$-regret bounds than the state of the art.
• Score: 28.598226670015315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
  This paper introduces the notion of concavity and DR-submodularity in various settings, including monotone non-linear and DR-submodularity. A general meta-algorithmm converts linear/quadratic into ones that optimize upper-linear/quadratizable functions.
  arXiv  Detail & Related papers  (2024-04-27T06:19:30Z)
• A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization [33.38582292895673]
  We show that any algorithm for online linear optimization with fully adaptive adversaries is an algorithm for online convex optimization. We use this to describe general metaalgorithms to convert deterministic algorithms to zeroth order algorithms with comparable regret bounds.
  arXiv  Detail & Related papers  (2024-02-13T17:42:27Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
  A submodular function in the MapReduce (MR) model has received much attention. We show that several sublinearly adaptive algorithms satisfy the consistency property required to work in the MR setting.
  arXiv  Detail & Related papers  (2022-06-20T04:17:32Z)
• Faster First-Order Algorithms for Monotone Strongly DR-Submodular Maximization [11.919431962501479]
  Continuous-submodular functions satisfy the Diminishing Returns (DR) property, which implies that they are concave along non-negative directions. We propose a new algorithm that matches the provably optimal $1-fracce$ approximation ratio after only $lceilfracLmurce$.
  arXiv  Detail & Related papers  (2021-11-15T18:53:14Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs) We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO) PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement.
  arXiv  Detail & Related papers  (2021-10-18T02:33:20Z)
• 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)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  We propose a novel framework that converts streaming for monotone submodular into streaming for non-monotone submodular. We also propose the first algorithm for monotone submodular streaming subject to $k$ible $k$-set system constraints.
  arXiv  Detail & Related papers  (2020-02-09T12:32:14Z)

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.