Projects per year
Abstract / Description of output
We study the fixed design segmented regression problem: Given noisy samples from a piecewise linear function ff, we want to recover ff up to a desired accuracy in mean-squared error. Previous rigorous approaches for this problem rely on dynamic programming (DP) and, while sample efficient, have running time quadratic in the sample size. As our main contribution, we provide new sample near-linear time algorithms for the problem that -- while not being minimax optimal -- achieve a significantly better sample-time tradeoff on large datasets compared to the DP approach. Our experimental evaluation shows that, compared with the DP approach, our algorithms provide a convergence rate that is only off by a factor of 22 to 33, while achieving speedups of two orders of magnitude.
Original language | English |
---|---|
Title of host publication | Proceedings of the 33rd International Conference on Machine Learning (ICML 2016) |
Place of Publication | New York, USA |
Publisher | PMLR |
Pages | 2878-2886 |
Number of pages | 9 |
Publication status | Published - 24 Jun 2016 |
Event | 33rd International Conference on Machine Learning: ICML 2016 - New York, United States Duration: 19 Jun 2016 → 24 Jun 2016 https://icml.cc/Conferences/2016/ |
Publication series
Name | Proceedings of Machine Learning Research |
---|---|
Volume | 48 |
ISSN (Electronic) | 2640-3498 |
Conference
Conference | 33rd International Conference on Machine Learning |
---|---|
Abbreviated title | ICML 2016 |
Country/Territory | United States |
City | New York |
Period | 19/06/16 → 24/06/16 |
Internet address |
Fingerprint
Dive into the research topics of 'Fast Algorithms for Segmented Regression'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research