NIPS Proceedingsβ

A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening

Part of: Advances in Neural Information Processing Systems 30 (NIPS 2017)


[PDF] [BibTeX] [Supplemental] [Reviews]


Conference Event Type: Poster


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.