75 citations · 897 across the 91 of their papers we have counts for
11 papers · 1 filter
Adaptivity in Adaptive Submodularity
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni
Adaptive sequential decision making is one of the central challenges in machine learning and artificial intelligence. In such problems, the goal is to design an interactive policy…
Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
Mingrui Zhang, Lin Chen, Hamed Hassani +1
In this paper, we propose three online algorithms for submodular maximisation. The first one, Mono-Frank-Wolfe, reduces the number of per-function gradient evaluations from $T^{1/2…
One Sample Stochastic Frank-Wolfe
Mingrui Zhang, Zebang Shen, Aryan Mokhtari +2
One of the beauties of the projected gradient descent method lies in its rather simple mechanism and yet stable behavior with inexact, stochastic gradients, which has led to its wi…
Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
Lin Chen, Qian Yu, Hannah Lawrence +1
We study the problem of switching-constrained online convex optimization (OCO), where the player has a limited number of opportunities to change her action. While the discrete anal…
Regret Bounds for Batched Bandits
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian +1
We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets t…
Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam +2
Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a mono…