Faster and Simpler Sketches of Valuation Functions

We present fast algorithms for sketching valuation functions. Let N (|N|=n) be some ground set and v:2Nrightarrow mathbb R be a function. We say that tilde v:2Nrightarrow mathbb R is an α-sketch of v if for every set S we have that frac v(S) α ≤ tilde v(S) ≤ v(S) and tilde v can be described in poly(n) bits. Goemans et al. [SODA'09] showed that if v is submodular then there exists an tilde O(√ n)-sketch that can be constructed using polynomially many value queries (this is the best possible, as Balcan and Harvey [STOC'11] show that no submodular function admit an nfrac 1 3 - ε-sketch). Based on their work, Balcan et al. [COLT'12] and Badanidiyuru et al. [SODA'12] show that if v is subadditive then there exists an tilde O(√ n)-sketch that can be constructed using polynomially many demand queries. All previous sketches are based on complicated geometric constructions. The first step in their constructions is proving the existence of a good sketch by finding an ellipsoid that ``approximates'' v well (this is done by applying John's theorem to ensure the existence of an ellipsoid that is ``close'' to the polymatroid that is associated with v). The second step is showing this ellipsoid can be found efficiently, and this is done by repeatedly solving a certain convex program to obtain better approximations of John's ellipsoid. In this paper, we give a much simpler, non-geometric proof for the existence of good sketches, and utilize the proof to obtain much faster algorithms that match the previously obtained approximation bounds. Specifically, we provide an algorithm that finds tilde O(√ n)-sketch of a submodular function with only tilde O(n^frac32) value queries, and an algorithm that finds tilde O(√ n)-sketch of a subadditive function with O(n) demand and value queries.