NeurIPS 2017poster77 citations
A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening
Kevin Lin, James L Sharpnack, Alessandro Rinaldo, Ryan J Tibshirani
Abstract
In the 1-dimensional multiple changepoint detection problem, we derive a new fast error rate for the fused lasso estimator, under the assumption that the mean vector has a sparse number of changepoints. This rate is seen to be suboptimal (compared to the minimax rate) by only a factor of $\log\log{n}$. Our proof technique is centered around a novel construction that we call a lower interpolant. We extend our results to misspecified models and exponential family distributions. We also describe the implications of our error analysis for the approximate screening of changepoints.
BibTeX
@inproceedings{NIPS2017_5abdf8b8,
author = {Lin, Kevin and Sharpnack, James L and Rinaldo, Alessandro and Tibshirani, Ryan J},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/5abdf8b8520b71f3a528c7547ee92428-Paper.pdf},
volume = {30},
year = {2017}
}