A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening
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.
Cite
Text
Lin et al. "A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening." Neural Information Processing Systems, 2017.Markdown
[Lin et al. "A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/lin2017neurips-sharp/)BibTeX
@inproceedings{lin2017neurips-sharp,
title = {{A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening}},
author = {Lin, Kevin and Sharpnack, James L and Rinaldo, Alessandro and Tibshirani, Ryan J},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {6884-6893},
url = {https://mlanthology.org/neurips/2017/lin2017neurips-sharp/}
}