40 citations · 242 across the 33 of their papers we have counts for
6 papers · 1 filter
Submodular Maximization Through Barrier Functions
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi +1
In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves t…
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Vitaly Feldman, Jan Vondrak
Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generaliz…
Generalization Bounds for Uniformly Stable Algorithms
Vitaly Feldman, Jan Vondrak
Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elis…
Lazier Than Lazy Greedy
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi +2
Is it possible to maximize a monotone submodular function faster than the widely used lazy greedy algorithm (also known as accelerated greedy), both in theory and practice? In this…
Tight Bounds on Approximation and Learning of Self-Bounding Functions
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube . Informally, a function $f:{0,1}^n…
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Vitaly Feldman, Pravesh Kothari, Jan Vondrak
We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube . Our main result is th…