Name
Abstract | ||
|---|---|---|
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms We study the problem of robustly learning multi-dimensional histograms. A (d)-dimensional function (h: D mathbb{R}) is called a (k)-histogram if there exists a partition of the domain (D subseteq mathbb{R}^d) into (k) axis-aligned rectangles such that (h) is constant within each such rectangle. Let (f: D mathbb{R}) be an arbitrary (d)-dimensional probability density function, and suppose that (f) is (mathrm{OPT})-close, in (L_1)-distance, to an unknown (k)-histogram (with unknown partition). Our goal is to output a hypothesis that is (O(mathrm{OPT}) + varepsilon) close to (f), in (L_1)-distance. We give an efficient algorithm for this learning problem that, for any fixed dimension, uses near-optimal sample complexity (up to logarithmic factors), and runs in sample near-linear time. Prior to our work, the case of (d=1) was well-understood, but vast gaps in our understanding remained even for (d=2). |
Year | Venue | DocType |
|---|---|---|
2018 | COLT | Conference |
Volume | Citations | PageRank |
abs/1802.08513 | 3 | 0.41 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilias Diakonikolas | 1 | 776 | 64.21 |
| Jerry Li | 2 | 229 | 22.67 |
| Ludwig Schmidt | 3 | 684 | 31.03 |