2020
Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds
NeurIPS 2020poster
We consider the problem of nonnegative submodular maximization in the online setting. At time step t, an algorithm selects a set S
3 accepted papers
We consider the problem of nonnegative submodular maximization in the online setting. At time step t, an algorithm selects a set S
In online convex optimization (OCO), Lipschitz continuity of the functions is commonly assumed in order to obtain sublinear regret. Moreover, many algorithms have only logarithmic regret when these functions are also strongly convex. Recently, researchers from convex optimization proposed the notion…
We prove that ϴ(k d^2 / ε^2) samples are necessary and sufficient for learning a mixture of k Gaussians in R^d, up to error ε in total variation distance. This improves both the known upper bounds and lower bounds for this problem. For mixtures of axis-aligned Gaussians, we show that O(k d / ε^2) sa…